[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: JFFS2 number of reserved blocks for GC?
On Wed, 28 Mar 2001, Finn Hakansson wrote:
> Can't someone find a mathematician to make a formal proof of how
> much space is needed by the GC once and for all?
Would be nice. In the meantime, I'll throw in an approximation off the
top of my head to get the ball rolling and for people to pick holes in...
To ensure that we can complete garbage collection from the 'gcblock',
which is the one we're currently garbage collecting, we have to be able to
obsolete every node. The na´ve estimate of that is that we need as much
free space as we have used space in 'gcblock'. But that's not enough,
a) We might have overwritten part of the data, and the newly-combined
page doesn't compress as well as the original.
b) We might have to split a node over the end of one block and onto
the next, which again means it won't compress as well, as well
as the overhead of the extra node header.
The former is easily fixed - if we're short of space and the node would
expand more than we can spare, we just write out the _same_ data again
with the original version number (so it's still partially obsoleted by the
later nodes which overlap it). We do this for hole nodes already, rather
than splitting them.
The latter we just have to deal with. Ignoring the compression, the
expansion would be the size of one node header (68 bytes). With the
resulting reduction in compression, I'm not sure - I certainly can't prove
it. But let's call it 256 bytes for the sake of argument.
In the worst case, we start with a filesystem where all nodes are
perfectly aligned, and garbage-collect every block on the filesystem
making it unaligned - taking those 256 bytes for _every_ erase block on
So assuming, not unreasonably, that we're not going to try to keep track
of how many blocks are perfectly aligned, we have to assume that they all
are, and that we're about to GC till they're all not. So the amount of
space we need to keep available to ensure GC can continue is....
c->nr_blocks * MAGIC_NUMBER_256_WHICH_IS_WRONG
That's the amount of space we _must_ have available at all times. We
should probably allow deletion nodes to be written, and merge data nodes
into one, right up to that threshold, as they're going to make space for
us in the long run. And allow new data nodes when we have a reasonable
margin over that - maybe another sector_size.
The difficult part here is working out the amount by which a compressed
page can expand when you split it into two. It's fairly suboptimal at the
moment because of the way we use zlib when we're short of destination
space. It would be _really_ useful to be able to tell zlib 'please
compress as much as you can of these data into a buffer this size, and
tell me how much you managed and how much space you took. As it is, we
have to keep doing partial flushes which degrades the compression even
To unsubscribe from this list: send the line "unsubscribe jffs-dev" in
the body of a message to firstname.lastname@example.org