Benchmarking JFFS2

[David Woodhouse]

dwmw2 at infradead.org said:
> 2. We have a 'dirty_list' containing blocks which have _any_ dirty space, 
>    and we pick blocks from the to garbage-collect from. If there's only a 
>    few bytes of dirty space, we GC the whole block just to gain a few 
>    bytes. We should keep a 'very_dirty_list' of blocks with _significant_ 
>    amounts of dirty space and favour that even more when picking blocks
>    to GC, especially when doing just-in-time GC rather than from the 
>    background thread. 

I've done this, and every block with more than 50% dirty space now goes on
the 'very_dirty_list'. With the file system snapshot I'd taken from my iPAQ
to investigate what turned out to the double-free bug, the garbage collect 
thread was GC'ing 6 blocks immediately after mounting before it stopped. 
With the very_dirty_list optimisation, that dropped to two.

I'm beginning to wonder whether we should actually abolish the separate
clean/dirty/very_dirty lists and keep a single used_list in decreasing 
order of dirty space, then in jffs2_find_gc_block just pick the block 
number $N in that list, where N is exponentially distributed -- high 
chance of being '1', small but non-negligible chance of being near the end 
of the list.

Keeping the used_list sorted should be fairly simple and cheap - each time 
you make a block slightly dirtier you just do a little bit of bubble-sort, 
and moving nextblock onto the used_list is fairly rare so it doesn't matter 
too much that it's a bit slower.

Does anyone have any ideas on how we'd generate the random number N for 
jffs2_find_gc_block() though?

--
dwmw2