引言
为什么要损耗平衡（wear-leveling）？
Flash上的每一位(bit)可以被写操作置成逻辑0。 可是把逻辑 0 置成逻辑 1 却不能按位(bit)来操作，而只能按擦写块（erase block）为单位进行擦写操作。一般来说，“NOR flash擦写块的大小是128K，Nand flash擦写块的大小是8K”【2】。从上层来看，擦写所完成的功能就是把擦写块内的每一位都重设置（reset）成逻辑 1。
Flash的使用寿命是有限的。“具体来说，flash的使用寿命由擦写块的最大可擦 写次数决定。超过了最大可擦写次数，这个擦写块就成为坏块(bad block)了。因此为了避免某个擦写块被过度擦写，以至于它先于其他的擦写块达到最大可擦写次数，我们应该在尽量小的影响性能的前提下，擦写操作均匀的 分布在每个擦写块上。这个过程叫做损耗平衡（wear leveling）”【1】。按照现在的技术水平，一般来说NOR flash擦写块的最大可擦写次数在十万次左右，NAND flash擦写块的最大可擦写次数在百万次左右。
而传统文件系统对于损耗平衡，以及嵌入式系统的掉电保护都没有很好的考虑，所以需要专门的文件系统来读写FLASH。
现有的嵌入式文件系统主要有哪些?
JFFS2（The Journaling Flash File System 2）, YAFFS2 (Yet Another Flash File System 2)等，对于其文件系统的具体分析，不再过多叙述，有兴趣的话可以看看我的参考文献，上面均有详细的分析。本文也就这两种算法的损耗算法进行分析。
正文
JFFS2的损耗平衡算法：
在JFFS2中，Flash被分成一个个擦写块。NOR flash 读/写操作的基本单位是字节；而 NAND flash 又把擦写块分成页(page), 页是写操作的基本单位，一般一个页的大小是 512 或 2K 字节，另外每一页还有16 字节的备用空间（SpareData, OOB）。
JFFS2 维护了几个链表来管理擦写块，根据擦写块上内容的不同情况，擦写块会在不同的链表上。具体来说，当一个擦写块上都是合法(valid)的节点时，它会在 clean_list 上；当一个擦写块包含至少一个过时(obsolete)的节点时，它会在 dirty_list 上；当一个擦写块被擦写完毕，并被写入 CLEANMARKER 节点后，它会在 free_list 上。下表表示了具体链表名：
表1 JFFS2的链表中擦除块名称一览表【3】
|
链表 |
链表中擦除块的性质 |
|
clean_list |
只包含有效数据结点 |
|
very_dirty_list |
所含数据结点大部分都已过时 |
|
dirty_list |
至少含有一个过时数据结点 |
|
erasable_list |
所有的数据结点都过时需要擦除。但尚未“调度”到erase_pending_list |
|
erasable_pending_wbuf_list |
同erase_pending_list，但擦除必须等待wbuf冲刷后 |
|
erasing_list |
当前正在擦除 |
|
erase_pending_list |
当前正等待擦除 |
|
erase_complete_list |
擦除已完成，但尚未写入CLEANMARKER |
|
free_list |
擦除完成，且已经写入CLEANMARKER |
|
bad_list |
含有损坏单元 |
|
bad_used_list |
含有损坏单元，但含有数据 |
现在开始分析具体源代码，源程序文件路径为：uClinux-dist/linux-2.6.x/fs/jffs2
>jffs2/fs.c
在挂载jffs2文件系统时，在jffs2_do_fill_super函数的最后创建并启动GC内核线程，相关代码如下：
if (!(sb->s_flags & MS_RDONLY))
jffs2_start_garbage_collect_thread(c);
return 0;
如果jffs2文件系统不是以只读方式挂载的，就会有新的数据实体写入flash。而 且jffs2文件系统的特点是在写入新的数据实体时并不修改flash上原有数据实体，而只是将其内核描述符标记为“过时”。系统运行一段时间后若空白 flash擦除块的数量小于一定阈值，则GC被唤醒用于释放所有过时的数据实体【3】。
为了尽量均衡地使用flash分区上的所有擦除块，在选择有效数据实体的副本所写入的擦除块时需要考虑Wear Leveling算法，jffs2_find_gc_block()即Wear Leveling算法的关键函数：
>jffs2/gc.c
static struct jffs2_eraseblock *jffs2_find_gc_block(struct jffs2_sb_info *c)
{
struct jffs2_eraseblock *ret;
struct list_head *nextlist = NULL;
int n = jiffies % 128; //0~127的随机数
/* Pick an eraseblock to garbage collect next. This is where we'll
put the clever wear-levelling algorithms. Eventually. */
/* We possibly want to favour the dirtier blocks more when the
number of free blocks is low. */
if (!list_empty(&c->bad_used_list) && c->nr_free_blocks > c->resv_blocks_gcbad) {
D1(printk(KERN_DEBUG "Picking block from bad_used_list to GC next\n"));
nextlist = &c->bad_used_list; //含有损坏单元，但含有数据的块中先回收
} else if (n < 50 && !list_empty(&c->erasable_list)) {
/* Note that most of them will have gone directly to be erased.
So don't favour the erasable_list _too_ much. */
D1(printk(KERN_DEBUG "Picking block from erasable_list to GC next\n"));
nextlist = &c->erasable_list;// 如果有已过时，但尚未擦除的块，50/128的概率回收 } else if (n < 110 && !list_empty(&c->very_dirty_list)) {
/* Most of the time, pick one off the very_dirty list */
D1(printk(KERN_DEBUG "Picking block from very_dirty_list to GC next\n"));
nextlist = &c->very_dirty_list;//如果有大部分数据已经过时的块，110/128的概率回收 } else if (n < 126 && !list_empty(&c->dirty_list)) {
D1(printk(KERN_DEBUG "Picking block from dirty_list to GC next\n"));
nextlist = &c->dirty_list;//如果有部分数据已经过时的块，126/128的概率回收
} else if (!list_empty(&c->clean_list)) {
D1(printk(KERN_DEBUG "Picking block from clean_list to GC next\n"));
nextlist = &c->clean_list;//回收只含有有效数据的块
} else if (!list_empty(&c->dirty_list)) {
D1(printk(KERN_DEBUG "Picking block from dirty_list to GC next (clean_list was empty)\n"));
nextlist = &c->dirty_list;//回收有部分数据已经过时的块
} else if (!list_empty(&c->very_dirty_list)) {
D1(printk(KERN_DEBUG "Picking block from very_dirty_list to GC next (clean_list and dirty_list were empty)\n"));
nextlist = &c->very_dirty_list;//回收大部分数据已经过时的块
} else if (!list_empty(&c->erasable_list)) {
D1(printk(KERN_DEBUG "Picking block from erasable_list to GC next (clean_list and {very_,}dirty_list were empty)\n")
); nextlist = &c->erasable_list;//回收已过时，但尚未擦除的块
} else {
/* Eep. All were empty */
D1(printk(KERN_NOTICE "jffs2: No clean, dirty _or_ erasable blocks to GC from! Where are they all?\n"));
return NULL;//已经无可调度的块
}
ret = list_entry(nextlist->next, struct jffs2_eraseblock, list);
list_del(&ret->list);
c->gcblock = ret;
ret->gc_node = ret->first_node;
if (!ret->gc_node) {
printk(KERN_WARNING "Eep. ret->gc_node for block at 0x%08x is NULL\n", ret->offset);
BUG();
}
/* Have we accidentally picked a clean block with wasted space ? */
if (ret->wasted_size) {
D1(printk(KERN_DEBUG "Converting wasted_size %08x to dirty_size\n", ret->wasted_size));
ret->dirty_size += ret->wasted_size;
c->wasted_size -= ret->wasted_size;
c->dirty_size += ret->wasted_size;
ret->wasted_size = 0;
}
D1(jffs2_dump_block_lists(c));
return ret;
}
由上可见，JFFS2的处理方式是以 50/128的概率回收erasable_list，以110/128概率回收 very_dirty_list，以126/128概率回收 dirty_list，剩下概率回收 clean_list。当然从程序中也可以看出，回收后一条链表块，是要在一定概率以及前面的块链表为空的情况下。
JFFS2 对损耗平衡是用概率的方法来解决的，这很难保证损耗平衡的确定性。在某些情况下，可能造成对擦写块不必要的擦写操作；在某些情况下，又会引起对损耗平衡调整的不及时。
“据说后来，JFFS2有改进的损耗平衡补丁程序，这个补丁程序的基本思想是，记录每 个擦写块的擦写次数，当flash上各个擦写块的擦写次数的差距超过某个预定的阀值，开始进行损耗平衡的调整。调整的策略是，在垃圾回收时将擦写次数小的 擦写块上的数据迁移到擦写次数大的擦写块上。这样一来我们提高了损耗平衡的确定性，我们可以知道什么时候开始损耗平衡的调整，也可以知道选取哪些擦写块进 行损耗平衡的调整”【1】。
现在，JFFS3也正在开发中，在垃圾回收一章中，作者有 这样的话：“JFFS3 Garbage Collection is currently under development and this chapter may be changed. Any suggestions and ideas are welcome.”【4】，还没有发布具体的设计（05年写得啊。。。）。我期待Artem B. Bityutskiy能设计出更加巧妙而高效的平衡算法。
