為什么要損耗平衡（wear-leveling）？ Flash上的每一位(bit)可以被寫操作置成邏輯0。 可是把邏輯 0 置成邏輯 1 卻不能按位(bit)來操作，而只能按擦寫塊（erase block）為單位進(jìn)行擦寫操作。一般來說，“NOR flash擦寫塊的大小是128K，Nand flash擦寫塊的大小是8K”【2】。從上層來看，擦寫所完成的功能就是把擦寫塊內(nèi)的每一位都重設(shè)置（reset）成邏輯 1。 Flash的使用壽命是有限的。“具體來說，flash的使用壽命由擦寫塊的最大可擦 寫次數(shù)決定。超過了最大可擦寫次數(shù)，這個(gè)擦寫塊就成為壞塊(bad block)了。因此為了避免某個(gè)擦寫塊被過度擦寫，以至于它先于其他的擦寫塊達(dá)到最大可擦寫次數(shù)，我們應(yīng)該在盡量小的影響性能的前提下，擦寫操作均勻的 分布在每個(gè)擦寫塊上。這個(gè)過程叫做損耗平衡（wear leveling）”【1】。按照現(xiàn)在的技術(shù)水平，一般來說NOR flash擦寫塊的最大可擦寫次數(shù)在十萬次左右，NAND flash擦寫塊的最大可擦寫次數(shù)在百萬次左右。 而傳統(tǒng)文件系統(tǒng)對于損耗平衡，以及嵌入式系統(tǒng)的掉電保護(hù)都沒有很好的考慮，所以需要專門的文件系統(tǒng)來讀寫FLASH。 現(xiàn)有的嵌入式文件系統(tǒng)主要有哪些? JFFS2（The Journaling Flash File System 2）, YAFFS2 (Yet Another Flash File System 2)等，對于其文件系統(tǒng)的具體分析，不再過多敘述，有興趣的話可以看看我的參考文獻(xiàn)，上面均有詳細(xì)的分析。本文也就這兩種算法的損耗算法進(jìn)行分析。正文 JFFS2的損耗平衡算法：在JFFS2中，Flash被分成一個(gè)個(gè)擦寫塊。NOR flash 讀/寫操作的基本單位是字節(jié)；而 NAND flash 又把擦寫塊分成頁(page), 頁是寫操作的基本單位，一般一個(gè)頁的大小是 512 或 2K 字節(jié)，另外每一頁還有16 字節(jié)的備用空間（SpareData, OOB）。 JFFS2 維護(hù)了幾個(gè)鏈表來管理擦寫塊，根據(jù)擦寫塊上內(nèi)容的不同情況，擦寫塊會在不同的鏈表上。具體來說，當(dāng)一個(gè)擦寫塊上都是合法(valid)的節(jié)點(diǎn)時(shí)，它會在 clean_list 上；當(dāng)一個(gè)擦寫塊包含至少一個(gè)過時(shí)(obsolete)的節(jié)點(diǎn)時(shí)，它會在 dirty_list 上；當(dāng)一個(gè)擦寫塊被擦寫完畢，并被寫入 CLEANMARKER 節(jié)點(diǎn)后，它會在 free_list 上。下表表示了具體鏈表名： 表1 JFFS2的鏈表中擦除塊名稱一覽表【3】 鏈表 鏈表中擦除塊的性質(zhì) clean_list 只包含有效數(shù)據(jù)結(jié)點(diǎn) very_dirty_list 所含數(shù)據(jù)結(jié)點(diǎn)大部分都已過時(shí) dirty_list 至少含有一個(gè)過時(shí)數(shù)據(jù)結(jié)點(diǎn) erasable_list 所有的數(shù)據(jù)結(jié)點(diǎn)都過時(shí)需要擦除。但尚未“調(diào)度”到erase_pending_list erasable_pending_wbuf_list 同erase_pending_list，但擦除必須等待wbuf沖刷后 erasing_list 當(dāng)前正在擦除 erase_pending_list 當(dāng)前正等待擦除 erase_complete_list 擦除已完成，但尚未寫入CLEANMARKER free_list 擦除完成，且已經(jīng)寫入CLEANMARKER bad_list 含有損壞單元 bad_used_list 含有損壞單元，但含有數(shù)據(jù)現(xiàn)在開始分析具體源代碼，源程序文件路徑為：uClinux-dist/linux-2.6.x/fs/jffs2 >jffs2/fs.c 在掛載jffs2文件系統(tǒng)時(shí)，在jffs2_do_fill_super函數(shù)的最后創(chuàng)建并啟動(dòng)GC內(nèi)核線程，相關(guān)代碼如下： if (!(sb->s_flags & MS_RDONLY))jffs2_start_garbage_collect_thread(c);return 0; 如果jffs2文件系統(tǒng)不是以只讀方式掛載的，就會有新的數(shù)據(jù)實(shí)體寫入flash。而 且jffs2文件系統(tǒng)的特點(diǎn)是在寫入新的數(shù)據(jù)實(shí)體時(shí)并不修改flash上原有數(shù)據(jù)實(shí)體，而只是將其內(nèi)核描述符標(biāo)記為“過時(shí)”。系統(tǒng)運(yùn)行一段時(shí)間后若空白 flash擦除塊的數(shù)量小于一定閾值，則GC被喚醒用于釋放所有過時(shí)的數(shù)據(jù)實(shí)體【3】。 為了盡量均衡地使用flash分區(qū)上的所有擦除塊，在選擇有效數(shù)據(jù)實(shí)體的副本所寫入的擦除塊時(shí)需要考慮Wear Leveling算法，jffs2_find_gc_block()即Wear Leveling算法的關(guān)鍵函數(shù)： >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的隨機(jī)數(shù)/* Pick an eraseblock to garbage collect next. This is where we'llput the clever wear-levelling algorithms. Eventually. *//* We possibly want to favour the dirtier blocks more when thenumber 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; //含有損壞單元，但含有數(shù)據(jù)的塊中先回收} 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;// 如果有已過時(shí)，但尚未擦除的塊，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;//如果有大部分?jǐn)?shù)據(jù)已經(jīng)過時(shí)的塊，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;//如果有部分?jǐn)?shù)據(jù)已經(jīng)過時(shí)的塊，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;//回收只含有有效數(shù)據(jù)的塊} 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;//回收有部分?jǐn)?shù)據(jù)已經(jīng)過時(shí)的塊} 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;//回收大部分?jǐn)?shù)據(jù)已經(jīng)過時(shí)的塊} 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;//回收已過時(shí)，但尚未擦除的塊} 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;//已經(jīng)無可調(diào)度的塊 } 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。當(dāng)然從程序中也可以看出，回收后一條鏈表塊，是要在一定概率以及前面的塊鏈表為空的情況下。 JFFS2 對損耗平衡是用概率的方法來解決的，這很難保證損耗平衡的確定性。在某些情況下，可能造成對擦寫塊不必要的擦寫操作；在某些情況下，又會引起對損耗平衡調(diào)整的不及時(shí)。 “據(jù)說后來，JFFS2有改進(jìn)的損耗平衡補(bǔ)丁程序，這個(gè)補(bǔ)丁程序的基本思想是，記錄每 個(gè)擦寫塊的擦寫次數(shù)，當(dāng)flash上各個(gè)擦寫塊的擦寫次數(shù)的差距超過某個(gè)預(yù)定的閥值，開始進(jìn)行損耗平衡的調(diào)整。調(diào)整的策略是，在垃圾回收時(shí)將擦寫次數(shù)小的 擦寫塊上的數(shù)據(jù)遷移到擦寫次數(shù)大的擦寫塊上。這樣一來我們提高了損耗平衡的確定性，我們可以知道什么時(shí)候開始損耗平衡的調(diào)整，也可以知道選取哪些擦寫塊進(jìn) 行損耗平衡的調(diào)整”【1】。 現(xiàn)在，JFFS3也正在開發(fā)中，在垃圾回收一章中，作者有 這樣的話：“JFFS3 Garbage Collection is currently under development and this chapter may be changed. Any suggestions and ideas are welcome.”【4】，還沒有發(fā)布具體的設(shè)計(jì)（05年寫得啊。。。）。我期待Artem B. Bityutskiy能設(shè)計(jì)出更加巧妙而高效的平衡算法。YAFFS2的損耗平衡算法：YAFFS是專門針對Nand flash的文件系統(tǒng)，YAFFS1只能支持每頁為512B。而YAFFS2則另外也支持2K的頁面， 其他方面變化見網(wǎng)頁介紹：www.aleph1.co.uk/node/38。 YAFFS 對文件系統(tǒng)上的所有內(nèi)容（比如正常文件，目錄，鏈接，設(shè)備文件等等）都統(tǒng)一當(dāng)作文件來處理，每個(gè)文件都有一個(gè)頁面專門存放文件頭，文件頭保存了文件的模 式、所有者id、組id、長度、文件名、Parent Object ID 等信息。因?yàn)樾枰谝豁搩?nèi)放下這些內(nèi)容，所以對文件名的長度，符號鏈接對象的路徑名等長度都有限制。 前面說到對于Nand flash上的每一頁數(shù)據(jù)，都有額外的空間用來存儲附加信息，通常Nand flash 驅(qū)動(dòng)只使用了這些空間的一部分，YAFFS正是利用了這部分空間中剩余的部分來存儲文件系統(tǒng)相關(guān)的內(nèi)容。以512+16B為一個(gè)PAGE 的Nand flash芯片為例, YAFFS 文件系統(tǒng)數(shù)據(jù)的存儲布局如下所示： 表2 YAFFS的存儲布局【5】 0-511 Data 512-515 YAFFS TAG 516 Data status byte 517 Block status byte 518-519 YAFFS TAG 520-522 后256字節(jié)的ECC 523-524 YAFFS TAG 525-527 前256字節(jié)的ECC 可以看到在這里YAFFS 一共使用8個(gè)BYTE 用來存放文件系統(tǒng)相關(guān)的信息（yaffs_Tags）。這8 個(gè)Byte 的具體使用情況按順序如下： 表3 yaffs_Tags的具體使用情況【5】 位 屬性 20 ChunkID，該page 在一個(gè)文件內(nèi)的索引號 2 2 bits serial number 10 ByteCount 該page 內(nèi)的有效字節(jié)數(shù) 18 ObjectID 對象ID 號，用來唯一標(biāo)示一個(gè)文件 12 Ecc, Yaffs_Tags 本身的ECC 校驗(yàn)和 2 保留其中Serial Number 在文件系統(tǒng)創(chuàng)建時(shí)都為0，以后每次寫具有同一ObjectID 和ChunkID 的page 的時(shí)候都 加1， 因?yàn)閅AFFS 在更新一個(gè)PAGE 的時(shí)候總是在一個(gè)新的物理Page 上寫入數(shù)據(jù)，再將原先的物理Page 刪除，所以該serial number 可以在斷電等特殊情況下，當(dāng)新的page 已經(jīng)寫入但老的page 還沒有被刪除的時(shí)候用來識別正確的Page，保證數(shù)據(jù)的正確性。這對保存數(shù)據(jù)的完整性是很有用的。 YAFFS按順序分配當(dāng)前塊中的頁。當(dāng)該塊中所有的頁都用光后，另外一個(gè)干凈的塊將會 被選擇分配。至少保留2到3個(gè)塊用于垃圾塊收集。當(dāng)沒有足夠的干凈塊的時(shí)候，臟塊（比如只包含丟棄數(shù)據(jù)）將會被擦除成干凈塊。如果沒有臟塊，那些特別臟的 塊（含有丟棄數(shù)據(jù)特別多的塊）也會被垃圾塊回收算法選中。 作者也指出，YAFFS的損耗平衡是塊分配策略的副產(chǎn)品，數(shù)據(jù)總是被寫在下一個(gè)空閑塊 中，所有的塊都是被平等對待的。但是包含那些永久數(shù)據(jù)的塊卻不會再回收到空閑塊中，所以他所說的損耗平衡也僅僅指那些已經(jīng)空閑或者有可能變空閑的塊。假設(shè) 在一塊8M的NAND器件上，有2M空間用來存放相對固定，不經(jīng)常修改的數(shù)據(jù)文件，則經(jīng)常修改的文件只能在剩下的6M空間上重復(fù)擦寫。只在這6M空間上做 到均勻損耗，而沒有包括剩余的2M。“對整個(gè)器件來說，系統(tǒng)并沒有合適的搬移策略對固定文件進(jìn)行搬移，整個(gè)器件做不到均勻損耗，在實(shí)時(shí)記錄信息量比較大的 應(yīng)用環(huán)境中，應(yīng)編寫相應(yīng)的搬移策略函數(shù)，對固定文件進(jìn)行定期的搬移，以確保整個(gè)NAND器件的均勻損耗”【7】。 下面開始分析源代碼，其公司的主頁上可以下到最新源代碼：www.aleph1.co.uk/node/ 可以看下它回收算法的關(guān)鍵函數(shù)yaffs_CheckGarbageCollection()： >fs/yaffs/yaffs_guts.c /* 如果可用的擦除塊很少，我們就采用“主動(dòng)模式”來收集垃圾塊，否則我們就采用“被動(dòng)模式”。“主動(dòng)模式”中將會查看整個(gè)Flash的塊，就算只有少量過時(shí)數(shù)據(jù)的塊也會被回收。“被動(dòng)模式”只會查收少量區(qū)域，然后回收那些過時(shí)數(shù)據(jù)特別多的塊。*/ static int yaffs_CheckGarbageCollection(yaffs_Device * dev) {int block;int aggressive;int gcOk = YAFFS_OK;int maxTries = 0; int checkpointBlockAdjust;if (dev->isDoingGC) {return YAFFS_OK;} do {maxTries++; checkpointBlockAdjust = (dev->nCheckpointReservedBlocks - dev->blocksInCheckpoint);if(checkpointBlockAdjust < 0)checkpointBlockAdjust = 0;if (dev->nErasedBlocks < (dev->nReservedBlocks + checkpointBlockAdjust)) { /* 跟需要保留的塊數(shù)和自定義校準(zhǔn)塊的和作比較，如果少于這個(gè)值，就直接選擇主動(dòng)模式*/aggressive = 1;} else {/* 否則，選擇被動(dòng)模式 */aggressive = 0;} /*根據(jù)模式查找，回收相應(yīng)的塊*/block = yaffs_FindBlockForGarbageCollection(dev, aggressive);if (block > 0) {dev->garbageCollections++;if (!aggressive) {dev->passiveGarbageCollections++;}T(YAFFS_TRACE_GC,(TSTR("yaffs: GC erasedBlocks %d aggressive %d" TENDSTR),dev->nErasedBlocks, aggressive));gcOk = yaffs_GarbageCollectBlock(dev, block);}if (dev->nErasedBlocks < (dev->nReservedBlocks) && block > 0) {T(YAFFS_TRACE_GC,(TSTR("yaffs: GC !!!no reclaim!!! erasedBlocks %d after try %d block %d"TENDSTR), dev->nErasedBlocks, maxTries, block));}} while ((dev->nErasedBlocks < dev->nReservedBlocks) && (block > 0)&& (maxTries < 2));return aggressive ? gcOk : YAFFS_OK; }從上面的算法也可以看出，其實(shí)YAFFS的損耗平衡算法也沒什么可講的，主要是由于設(shè)計(jì)的原因，導(dǎo)致其平等地回收每一個(gè)空閑塊。如果空閑塊比較少，就加緊回收稍微有空閑的塊。因?yàn)樵O(shè)計(jì)簡單，所以效率還是不錯(cuò)的，下表是其測試結(jié)果，結(jié)果還是相當(dāng)不錯(cuò)： 表4 Times for 1MB of garbage collection at 50% dirty (單位1uS).【6】 Operation YAFFS1 YAFFS2(512b pages) YAFFS2 (2kB pages) YAFFS2(2kB pages, x16) Delete 1MB 558080 128000 16000 16000 Write 0.5MB 337920 337920 168960 112640 Total 896000 465920 184960 128640 MB/s 1.1 2.1 5.4 7.7 Relative speed 1 1.9 4.9 7總結(jié)及展望： 通過閱讀JFFS2和YAFFS的文獻(xiàn)的代碼，我覺得誰優(yōu)誰劣很難講。JFFS的文件 系統(tǒng)開發(fā)要比YAFFS要早得多，現(xiàn)在應(yīng)用范圍也比YAFFS廣。可以說YAFFS就是相當(dāng)于JFFS的“另一種文件系統(tǒng)”，所以YAFFS一開始就是從 借鑒JFFS開始的，避免了JFFS啟動(dòng)速度過慢和損耗不平衡等明顯的缺點(diǎn)，當(dāng)然后來JFFS2也進(jìn)行了改進(jìn)，如把數(shù)據(jù)移動(dòng)到頁的末尾（而YAFFS是放 在頁的前面），而不再是鏈表式在頁中隨便亂放，導(dǎo)致裝載速度巨慢。在YAFFS公司網(wǎng)頁的開發(fā)內(nèi)容中也可以看到，YAFFS和JFSS2的開發(fā)人員經(jīng)常進(jìn) 行交流。從我個(gè)人的角度來看，YAFFS2要比JFFS2好些，當(dāng)然這是僅限于Nand flash來說。在閱讀YAFFS2的源代碼時(shí)我發(fā)現(xiàn)，最新的更新日期是07年3月，而就我所看到的JFFS2代碼是04年5月，而JFFS3的設(shè)計(jì)草案 【4】的發(fā)布日期也是05年11月。兩種文件系統(tǒng)的維護(hù)速度可見一斑。 以上的分析我也只能定性得說下，如果有Flash芯片可以測試，那就可以定量的分析了。如果有時(shí)間，我想再深入看下兩類文件系統(tǒng)的源代碼，順便推薦下，參考文獻(xiàn)【3】確實(shí)寫得很認(rèn)真，值得一看。參考文獻(xiàn)： 【1】、JFFS2文件系統(tǒng)及新特性介紹：www.sqlus.com/Columns/LinuxSkill/012108669.html 【2】、David Woodhouse, JFFS : The Journalling Flash File System 【3】、shrek2（www.linuxforum.net的一個(gè)ID），《JFFS2源代碼情景分析（Beta2）》 【4】、Artem B. Bityutskiy, JFFS3 design issues(Version 0.32 (draft)) 【5】、Raymond（skyflame@hotmail.com），《Yaffs文件系統(tǒng)結(jié)構(gòu)及應(yīng)用》 【6】、YAFFS Development Notes：http://www.aleph1.co.uk/node/39 【7】、胡一飛，徐中偉，謝世環(huán)，《NAND flash上均勻損耗與掉電恢復(fù)在線測試》

?

總結(jié)

以上是生活随笔為你收集整理的嵌入式文件系统损耗平衡算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。