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

[zhao forrest]

Hi

This is the patch for enhanced wear-leveling algorithm, which is
based on previous erase_count_tracking patch. So please apply
"erase_count_tracking" patch before applying this patch.

I'd give my appreciation to Gleixner and Artem. They gave me many
inspiration and insightful ideas about the design of this patch.

The following is a brief description of this patch.

* The problem to be resolved by this patch
The current wear spread is of random nature. On filesystems with
unchanged files the wear almost never touches blocks which
contain solely unchanged data. This patch will try to limit the
gap between max_erase_count and min_erase_count within WL_DELTA.

* Data structure
two hash tables are defined and added to struct jffs2_sb_info:
struct jffs2_blocks_bucket used_blocks[HASH_SIZE];
struct jffs2_blocks_bucket free_blocks[HASH_SIZE];
In current patch, WL_DELTA is 1024, HASH_SIZE is 512.

* Operation
1 The blocks, that are added to dirty, very_dirty and clean list,
are also added to used_blocks[HASH_SIZE]; the blocks, that are
added to free list, are also added to free_blocks[HASH_SIZE].
The index in hash table is got by shifting the erase count
9 times right. And put the block at the end of the hash entry
list.

2 When a free_block is needed, it's got from the entry list of
free_blocks[HASH_SIZE]. Sure, we should choose one from lowest
entry list.

3 when (max_erase_count - average_erase_count)*2 > WL_DELTA,
a block is got from the entry list of used_blocks[HASH_SIZE].
Sure, we should choose one from lowest entry list.

4 when (max_erase_count - average_erase_count)*2 <= WL_DELTA,
the current wear-leveling algorithm is used.

5 Here we use (max_erase_count - average_erase_count) instead
of (max_erase_count - min_erase_count), because min_erase_count
can't be got by O(1) algorithm. So I choose average_erase_count
for approximation.

>From the above description, we know that this is only an
evolutional instead of revolutional change to current WL
algorithm. So the rationale is same as the current WL: prefer
performance and adjust WL when necessary.

Thanks,
Forrest

-------------- next part --------------
A non-text attachment was scrubbed...
Name: wear_leveling.patch
Type: application/octet-stream
Size: 15691 bytes
Desc: not available
Url : http://lists.infradead.org/pipermail/linux-mtd/attachments/20050906/633b1610/attachment.obj