[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, 
because:
 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
the medium.

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->gcblock?c->gcblock->used_size:c->sector_size +
	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 
more. 


To unsubscribe from this list: send the line "unsubscribe jffs-dev" in
the body of a message to majordomo@xxxxxxx.com