[PATCH]enhanced wear-leveling algorithm based on erase count

[Jörn Engel]

On Fri, 9 September 2005 17:17:10 +0800, zhao forrest wrote:
> >
> >I had the same idea:
> >
> >static int pick_used_block(void)
> >{
> >	static atomic_t seqno = 99;
> >
> >	if ((index_of_highest_filled_bucket - index_of_lowest_filled_bucket) 
> >	< 2)
> >		return 0;
> >
> >	/* it is time to pick a used block - just not too often */
> >	atomic_inc(seqno);
> >	if (atomic_read(seqno) != 0)
> >		return 0;
> >
> >	/* first pick after mount and every 100th pick afterwards */
> >	return 1;
> >}
> 
> But it'll pick a block from used_block_hash_table only with 1% possibility.
> Do you think this 1% possibility is too small? How about 10% or 20%?

1% should be good enough.  That's about what we use now, after all.

We need to make sure that static blocks that never accumulate much
garbage and thus never get GC'd otherwise get shaken up once in a
while.  After such a shakeup, they get filled with other data.  Data
that is obsoleting faster, so the erase block in question will
naturally get reused again.

In the worst case, the filesystem has 5 blocks to accumulate garbage
(the spare ones) and everything else static.  That means, each of the
5 blocks will get erased 20 times until a static block gets mixed into
the bunch and one of the dynamic blocks turns static.  More than good
enough, .1% would still be plenty.

What you could do to improve things further is seperate data between
probably-static and probably-dynamic.  Then have two erase blocks to
write into, one for static data, one for dynamic.  Always pick the
highest erase count free block for static data - it will likely not
get reused for a while.  Whenever picking a used block, fill it with
dynamic data.

Jörn

-- 
"[One] doesn't need to know [...] how to cause a headache in order
to take an aspirin."
-- Scott Culp, Manager of the Microsoft Security Response Center, 2001