基于嵌入式Linux的YAFFS2文件系統(tǒng)研究與改進(jìn)

朱紹英，查啟鵬

（中國(guó)電子科技集團(tuán)公司第三十二研究所，上海200233）

基于嵌入式Linux的YAFFS2文件系統(tǒng)研究與改進(jìn)

朱紹英，查啟鵬

（中國(guó)電子科技集團(tuán)公司第三十二研究所，上海200233）

YAFFS2文件系統(tǒng)是針對(duì)NAND Flash按塊擦寫(xiě)特點(diǎn)設(shè)計(jì)的一種專(zhuān)用Flash文件系統(tǒng)，其存在加載時(shí)間長(zhǎng)和NAND Flash專(zhuān)用的局限性。為此，從Flash存儲(chǔ)器管理和文件管理2個(gè)方面分析該系統(tǒng)的設(shè)計(jì)原理及特性，提出一種新的文件系統(tǒng)信息存儲(chǔ)方式，并從文件系統(tǒng)初始化、垃圾回收、斷電保護(hù)等方面對(duì)YAFFS2文件系統(tǒng)進(jìn)行改進(jìn)，減少加載時(shí)間，使之能應(yīng)用于多種Flash存儲(chǔ)器。測(cè)試結(jié)果表明，與原系統(tǒng)相比，改進(jìn)系統(tǒng)的安裝時(shí)間減少25%，并可實(shí)現(xiàn)Flash各存儲(chǔ)扇區(qū)的均衡使用。

YAFFS2文件系統(tǒng)；NAND存儲(chǔ)器；嵌入式Linux系統(tǒng)；垃圾回收策略；損耗平衡

1 概述

Flash存儲(chǔ)器由于具有存儲(chǔ)容量大、掉電數(shù)據(jù)不丟失以及可多次擦寫(xiě)等許多優(yōu)點(diǎn)而被廣泛應(yīng)用于各類(lèi)電子產(chǎn)品中，其存儲(chǔ)特性決定了已有的磁盤(pán)文件系統(tǒng)不能直接用于Flash存儲(chǔ)器，而必須采用專(zhuān)用的Flash文件系統(tǒng)。Flash文件系統(tǒng)除了要滿(mǎn)足一般文件系統(tǒng)的基本要求外，還要根據(jù)其自身的一些特性實(shí)現(xiàn)對(duì)Flash的有效管理。如廣泛應(yīng)用于NOR Flash的JFSS2（Journalling Flash File System）專(zhuān)用文件系統(tǒng)，而有些Flash存儲(chǔ)器如MMC卡、SD卡，由于內(nèi)嵌了各自的FTL（Flash Translation Layer）固件，使得傳統(tǒng)的磁盤(pán)文件系統(tǒng)可以直接使用。YAFFS2文件系統(tǒng)是A leph One公司針對(duì)NAND Flash的特點(diǎn)而設(shè)計(jì)的一種專(zhuān)用Flash文件系統(tǒng)［1］。它主要是通過(guò)NAND Flash每頁(yè)的OOB（Out of Band）區(qū)存儲(chǔ)文件系統(tǒng)信息而實(shí)現(xiàn)的，具有效率高、占用資源較少等特點(diǎn)［2］。本文分析YAFFS2文件系統(tǒng)的基本工作原理，包括存儲(chǔ)器管理和文件管理，針對(duì)其加載時(shí)間隨文件系統(tǒng)分區(qū)增大而線(xiàn)性增大和僅限于NAND Flash的局限性，提出一種新的文件系統(tǒng)信息存儲(chǔ)方式，避免使用OOB區(qū)，并改進(jìn)文件系統(tǒng)初始化時(shí)的掃描方式以及垃圾回收和掉電保護(hù)機(jī)制，實(shí)現(xiàn)在NAND Flash、MMC卡和NOR Flash等Flash存儲(chǔ)器上搭建YAFFS2文件系統(tǒng)的目的。

2 YAFFS2文件系統(tǒng)分析

Linux下的文件系統(tǒng)一般設(shè)計(jì)一個(gè)文件系統(tǒng)信息組成的“超級(jí)塊”，存放在存儲(chǔ)器的特定位置，其中包含了存儲(chǔ)器空間大小、存儲(chǔ)器使用情況和各個(gè)文件的存放信息等，并在文件系統(tǒng)安裝時(shí)被讀入以建立VFS（Virtual File System）層的super_block結(jié)構(gòu)實(shí)例［3-4］。然而，YAFFS2文件系統(tǒng)中存儲(chǔ)器上并沒(méi)有類(lèi)似的超級(jí)信息塊，在加載文件分區(qū)時(shí)，通過(guò)掃描存儲(chǔ)分區(qū)來(lái)得到相應(yīng)的文件系統(tǒng)信息并建立super_ block結(jié)構(gòu)實(shí)例，包括一些其他的信息，例如文件節(jié)點(diǎn)等。對(duì)于用戶(hù)，文件系統(tǒng)就是要實(shí)現(xiàn)按名字存取文件，以及文件和目錄的一些的管理操作，如創(chuàng)建、刪除、讀寫(xiě)等［5-6］。下面分別從存儲(chǔ)器管理和文件管理與來(lái)具體分析YAFFS2文件系統(tǒng)的設(shè)計(jì)原理。

2.1 NAND存儲(chǔ)器管理

YAFFS2文件系統(tǒng)以扇區(qū)為單位在NAND Flash存儲(chǔ)數(shù)據(jù)，即NAND Flash的頁(yè)，頁(yè)的大小主要有512 Byte，2 KB和4 KB等。若頁(yè)大小為2 KB，則每頁(yè)有64 Byte大小的OOB區(qū)，而所有頁(yè)的分配與讀寫(xiě)是以塊為單位進(jìn)行管理的，YAFFS2文件系統(tǒng)通過(guò)將存儲(chǔ)器的每個(gè)存儲(chǔ)塊分成為各種不同的狀態(tài)進(jìn)行組織管理，實(shí)現(xiàn)中使用共用體結(jié)構(gòu)yaffs_ BlockState來(lái)標(biāo)識(shí)，分別有初始、掃描、空閑、分配中、滿(mǎn)、臟6種狀態(tài)［7］。其中掃描狀態(tài)是指在加載文件系統(tǒng)時(shí)，正在讀該存儲(chǔ)塊的數(shù)據(jù)，并對(duì)其數(shù)據(jù)進(jìn)行分析處理，在整個(gè)文件系統(tǒng)分區(qū)的所有存儲(chǔ)塊的數(shù)據(jù)處理完之后，這些狀態(tài)的存儲(chǔ)塊分別會(huì)設(shè)置最后的使用狀態(tài)；當(dāng)存儲(chǔ)塊中所有的扇區(qū)都被使用時(shí)，會(huì)被標(biāo)記為滿(mǎn)或者直接標(biāo)記為臟狀態(tài)，后者是指存儲(chǔ)塊中所有扇區(qū)的數(shù)據(jù)都被標(biāo)記為無(wú)效數(shù)據(jù)，必須將這個(gè)存儲(chǔ)塊擦除為空狀態(tài)，加入到可分配列表中，供后面分配使用；在任何時(shí)刻，一個(gè)文件系統(tǒng)分區(qū)中有且只有一個(gè)存儲(chǔ)塊被標(biāo)記為分配狀態(tài)，在寫(xiě)文件或者垃圾回收時(shí)，先找到當(dāng)前分配狀態(tài)的存儲(chǔ)塊，然后順序分配一個(gè)扇區(qū)進(jìn)行寫(xiě)入，當(dāng)該存儲(chǔ)的所有扇區(qū)都寫(xiě)完后，就要再在空閑狀態(tài)列表中找到一個(gè)塊作為當(dāng)前分配塊。

為了更有效地使用Flash的各個(gè)存儲(chǔ)塊，實(shí)現(xiàn)中使用yaffs_Block Info結(jié)構(gòu)來(lái)詳細(xì)地描述每個(gè)塊的使用情況：

在上述結(jié)構(gòu)中，sequenceNum是記錄在該分區(qū)內(nèi)此塊的使用順序，在文件系統(tǒng)分區(qū)中是全局遞增的，主要在垃圾回收算法中用于判斷數(shù)據(jù)有效性；deletion表示該塊內(nèi)被刪除的頁(yè)數(shù)；needsRetiring指使用過(guò)程中讀寫(xiě)或者擦除出錯(cuò)，不能繼續(xù)被讀寫(xiě)和使用。在YAFFS2文件系統(tǒng)中，NAND Flash每頁(yè)的OOB區(qū)域用來(lái)存儲(chǔ)文件和頁(yè)使用信息，如文件系統(tǒng)結(jié)構(gòu)信息包括頁(yè)號(hào)、文件號(hào)、有效數(shù)據(jù)字節(jié)數(shù)等，以及該頁(yè)全部數(shù)據(jù)的ECC校驗(yàn)碼。比如頁(yè)大小為2 KB時(shí)，其具體每個(gè)頁(yè)的數(shù)據(jù)存儲(chǔ)布局如表1所示。

表1 數(shù)據(jù)存儲(chǔ)格式

2.2 文件表示與管理

從使用者的角度看，文件系統(tǒng)就是要實(shí)現(xiàn)文件的按名存取，即文件管理，其關(guān)鍵是文件的表示、組織和文件的索引、定位。文件的表示主要包括用于描述每個(gè)文件的各種屬性數(shù)據(jù)以及這些數(shù)據(jù)如何在設(shè)備上存儲(chǔ)，而文件的定位主要涉及到如何索引存儲(chǔ)該文件數(shù)據(jù)的所有頁(yè)。

在具體文件系統(tǒng)的實(shí)現(xiàn)中，文件的表示一般包括靜態(tài)存儲(chǔ)和動(dòng)態(tài)操作的數(shù)據(jù)，實(shí)現(xiàn)對(duì)文件的組織管理，其中在設(shè)備上靜態(tài)存儲(chǔ)的數(shù)據(jù)主要有3種：文件描述信息，包括名字、數(shù)據(jù)長(zhǎng)度、存儲(chǔ)地址、創(chuàng)建者、訪(fǎng)問(wèn)權(quán)限、使用情況等；文件內(nèi)容本身的數(shù)據(jù)；存儲(chǔ)空閑空間統(tǒng)計(jì)信息。而在內(nèi)存中動(dòng)態(tài)操作的數(shù)據(jù)管理信息主要有內(nèi)存文件描述信息、內(nèi)存文件系統(tǒng)分區(qū)信息等，在內(nèi)存中建立這些數(shù)據(jù)信息是為了提高文件系統(tǒng)運(yùn)行的效率和文件系統(tǒng)的各種性能。Linux操作系統(tǒng)在上層統(tǒng)一在虛擬文件系統(tǒng)VFS實(shí)現(xiàn)統(tǒng)一的接口，各個(gè)具體文件系統(tǒng)實(shí)現(xiàn)VFS定義的各個(gè)接口。在VFS層用struct inode統(tǒng)一描述各種文件系統(tǒng)中的文件，該結(jié)構(gòu)定義了各種文件的一些共同屬性信息，還包括了各種具體文件系統(tǒng)用于描述文件的各自私有的屬性信息，如EXT4文件系統(tǒng)的ext4_inode結(jié)構(gòu)。

在YAFFS2文件系統(tǒng)中，F(xiàn)lash存儲(chǔ)器上并沒(méi)有定義和存儲(chǔ)這類(lèi)信息，它是通過(guò)在文件系統(tǒng)加載時(shí)掃描文件系統(tǒng)分區(qū)，然后為設(shè)備上每個(gè)文件分別建立文件描述信息，即yaffs_Object結(jié)構(gòu)。在YAFFS2文件系統(tǒng)中，每個(gè)文件都用一個(gè)頁(yè)來(lái)存儲(chǔ)所有屬性信息，如名字、文件號(hào)、大小、父目錄的文件號(hào)、創(chuàng)建時(shí)間和用戶(hù)等，其描述結(jié)構(gòu)為yaffs_ObjectHeader，該對(duì)象主要是根據(jù)文件頭數(shù)據(jù)而創(chuàng)建的，當(dāng)掃描某個(gè)頁(yè)時(shí)，先讀取該頁(yè)的OOB的標(biāo)志，從而判斷該頁(yè)數(shù)據(jù)是一個(gè)文件頭，如果是，就在內(nèi)存中新建一個(gè)文件對(duì)象，再在后面的讀取過(guò)程中將該文件數(shù)據(jù)所在頁(yè)號(hào)記錄到其variant域中，后面定位文件數(shù)據(jù)時(shí)會(huì)使用該對(duì)象［8］。NAND Flash每頁(yè)的OOB中存放的文件定位信息是用yaffs_PackdTags2Part結(jié)構(gòu)描述的，其具體組織如下：

其中，objectId用于唯一標(biāo)識(shí)該文件的文件號(hào)；chunKId表示文件的數(shù)據(jù)頁(yè)號(hào)。從這2個(gè)ID就知道文件系統(tǒng)分區(qū)中各個(gè)頁(yè)與各個(gè)文件的一一對(duì)應(yīng)關(guān)系。YAFFS2文件系統(tǒng)中定義了文件樹(shù)來(lái)記錄各個(gè)文件的各個(gè)設(shè)備頁(yè)號(hào)，其文件樹(shù)的結(jié)構(gòu)如圖1所示。

圖1 YAFFS2文件樹(shù)

文件樹(shù)的最底層存放屬于該文件的所有設(shè)備頁(yè)號(hào)，是16維數(shù)組，而其他層都是8維，存放下層的指針，每個(gè)文件需要的層數(shù)根據(jù)文件所占的頁(yè)數(shù)確定。例如：若文件的數(shù)據(jù)扇區(qū)數(shù)少于16×8個(gè)，則總共只需2層便可。其結(jié)構(gòu)定義如下：

在進(jìn)行文件數(shù)據(jù)讀寫(xiě)時(shí)，根據(jù)文件名字找到文件對(duì)象yaffs_Object，然后得到文件樹(shù)結(jié)構(gòu)域variant，這樣就知道了該文件數(shù)據(jù)存放在Flash上的所有頁(yè)號(hào)，然后調(diào)用底層驅(qū)動(dòng)讀寫(xiě)頁(yè)內(nèi)的數(shù)據(jù)，在寫(xiě)文件時(shí)，還要將新的扇區(qū)號(hào)更新到文件樹(shù)結(jié)構(gòu)中。

3 改進(jìn)的YAFFS2文件系統(tǒng)

YAFFS2是針對(duì)NAND Flash專(zhuān)門(mén)設(shè)計(jì)的文件系統(tǒng)，它必須使用NAND Flash每頁(yè)的OOB區(qū)存儲(chǔ)文件系統(tǒng)信息，而NOR Flash、MMC卡等Flash存儲(chǔ)器上并沒(méi)有OOB區(qū)，所以，YAFFS2不能在NOR Flash等上使用OOB區(qū)實(shí)現(xiàn)存儲(chǔ)器管理和文件管理；其次YAFFS2文件系統(tǒng)加載過(guò)程中需要讀文件系統(tǒng)分區(qū)每頁(yè)的OOB數(shù)據(jù)，會(huì)導(dǎo)致加載時(shí)間隨NAND變大而加長(zhǎng)。

針對(duì)這2個(gè)問(wèn)題，本文設(shè)計(jì)了一種新的文件節(jié)點(diǎn)存儲(chǔ)方式，將文件系統(tǒng)信息存放到Flash頁(yè)內(nèi)，使得文件系統(tǒng)能正常運(yùn)行于NAND Flash，NOR Flash， MMC卡等Flash存儲(chǔ)器。

3.1 文件屬性信息的存儲(chǔ)方式

如前文所述，YAFFS2文件系統(tǒng)信息存放在NAND Flash上的OOB區(qū)域，其描述結(jié)構(gòu)為yaffs_ PackdTags2Part，改進(jìn)后使用下述的fat結(jié)構(gòu)描述，并且將每個(gè)塊內(nèi)的fat結(jié)構(gòu)統(tǒng)一存放在塊的前面2個(gè)數(shù)據(jù)頁(yè)中，而不再存放在OOB區(qū)內(nèi)。這樣在文件系統(tǒng)加載時(shí)，只要讀取每個(gè)塊的前2個(gè)頁(yè)的數(shù)據(jù)，減少了加載時(shí)間。

該數(shù)據(jù)結(jié)構(gòu)中的inodeId用于唯一標(biāo)識(shí)分區(qū)內(nèi)某個(gè)文件的ID，serialNum在斷電保護(hù)實(shí)現(xiàn)中用于標(biāo)識(shí)數(shù)據(jù)存儲(chǔ)的先后順序，chunKIn Inode表示文件數(shù)據(jù)的第n個(gè)扇區(qū)號(hào)，chunKInFlash表示存儲(chǔ)位置即頁(yè)號(hào)。從中可以看出，每個(gè)fat對(duì)象的大小是4 Byte，加載文件系統(tǒng)時(shí)，通過(guò)讀取各個(gè)存儲(chǔ)塊起始處的fat對(duì)象，就可以知道每個(gè)扇區(qū)的數(shù)據(jù)所對(duì)應(yīng)的文件信息，為每個(gè)文件建立一個(gè)文件樹(shù)成員，用于記錄該文件數(shù)據(jù)的所有扇區(qū)。與YAFFS2原有的存儲(chǔ)方式相比較，重復(fù)存放在每個(gè)扇區(qū)的OOB區(qū)域的序列號(hào)和字節(jié)數(shù)信息就不再需要了，因?yàn)樾蛄刑?hào)是描述整個(gè)存儲(chǔ)塊的，每個(gè)存儲(chǔ)塊只需要記錄一次。而原有的字節(jié)數(shù)是用于記錄某個(gè)文件的最后一個(gè)扇區(qū)數(shù)據(jù)的字節(jié)數(shù)，不適合存儲(chǔ)在每個(gè)扇區(qū)的OOB區(qū)域中，所以這個(gè)可以被優(yōu)化處理，改進(jìn)后在yaffs_Object結(jié)構(gòu)中增加描述信息，記錄存放某個(gè)文件的最有一個(gè)扇區(qū)的有效數(shù)據(jù)的字節(jié)數(shù)。如圖2描述了改進(jìn)后的Flash存儲(chǔ)器的每個(gè)塊存儲(chǔ)的數(shù)據(jù)信息，第1個(gè)頁(yè)存放的是序列號(hào)和該存儲(chǔ)塊的所有fat信息，其余各頁(yè)是數(shù)據(jù)區(qū)，存儲(chǔ)文件內(nèi)容或文件屬性，而fat結(jié)構(gòu)包含了所有頁(yè)到文件的索引信息。

圖2 Flash存儲(chǔ)塊

當(dāng)需要分配空閑塊存儲(chǔ)數(shù)據(jù)時(shí)，將文件系統(tǒng)當(dāng)前的序列號(hào)加1，記錄到新分配的空閑塊的開(kāi)始4 Byte，設(shè)置該塊為分配狀態(tài)，第一個(gè)頁(yè)被用作存儲(chǔ)fat索引信息，從第2個(gè)頁(yè)開(kāi)始可以用于存儲(chǔ)文件數(shù)據(jù)，分配和寫(xiě)入必須嚴(yán)格按照順序，當(dāng)文件系統(tǒng)將某文件的數(shù)據(jù)寫(xiě)入到某個(gè)頁(yè)時(shí)，同時(shí)要構(gòu)造好相應(yīng)的fat索引結(jié)構(gòu)，寫(xiě)入第1個(gè)頁(yè)的相應(yīng)位置。在實(shí)現(xiàn)中yaffs_AllocChunK（）用于分配存儲(chǔ)頁(yè)，在該分配算法中，首先從當(dāng)前分配狀態(tài)塊中分配頁(yè)，若全部已分配，就從分區(qū)的空閑列表中找到一個(gè)空閑塊，繼續(xù)上述過(guò)程。在使用過(guò)一段時(shí)間后，系統(tǒng)中所有的空閑狀態(tài)的塊都是由垃圾回收而來(lái)的，所以合適的磨損平衡和垃圾回收策略［9］可以以類(lèi)似的概率處理分區(qū)中的各個(gè)存儲(chǔ)塊，從而均衡地使用各個(gè)存儲(chǔ)塊，這樣各存儲(chǔ)塊的扇區(qū)的擦寫(xiě)次數(shù)均勻，能有效地延長(zhǎng)存儲(chǔ)器的壽命。

3.2 文件系統(tǒng)的加載過(guò)程

改進(jìn)后，加載某個(gè)文件系統(tǒng)分區(qū)時(shí)，其主要操作分2個(gè)步驟：首先，依次讀每個(gè)存儲(chǔ)塊開(kāi)始處的序列號(hào)，其有效值范圍為0x1000-0xefffff00，還有一些特殊的值用于標(biāo)記特殊狀態(tài)的塊。序列號(hào)在斷電保護(hù)和垃圾回收過(guò)程中都會(huì)被用到；然后，將分區(qū)內(nèi)的所有存儲(chǔ)塊以其相應(yīng)的序列號(hào)進(jìn)行排序，依次讀取其數(shù)據(jù)并進(jìn)行分析處理，其主要流程如圖3所示。

圖3 初始化加載流程

每個(gè)存儲(chǔ)塊的第1個(gè)頁(yè)存儲(chǔ)了該塊所有頁(yè)的fat結(jié)構(gòu)，每個(gè)fat實(shí)例是相應(yīng)存儲(chǔ)頁(yè)的索引信息，包含了其所屬文件信息，文件序列號(hào)等，當(dāng)某個(gè)fat對(duì)象中的文件頁(yè)號(hào)為0時(shí)，標(biāo)識(shí)該fat索引的存儲(chǔ)頁(yè)存儲(chǔ)的是該文件的文件頭，獲得相應(yīng)的存儲(chǔ)頁(yè)號(hào)，調(diào)用驅(qū)動(dòng)讀取文件頭信息，使用該文件頭構(gòu)造完整的文件屬性信息。當(dāng)文件頁(yè)號(hào)為其他值時(shí)，則表明其索引的存儲(chǔ)頁(yè)存放的是文件數(shù)據(jù)，記錄該頁(yè)號(hào)到文件的索引樹(shù)中，用于后面對(duì)文件數(shù)據(jù)的讀寫(xiě)操作。當(dāng)所有的存儲(chǔ)塊處理完之后，文件系統(tǒng)的加載過(guò)程就基本完成了，分區(qū)上所有文件和目錄的信息都被完整的建立了，后面通過(guò)文件系統(tǒng)提供的接口對(duì)文件的讀、寫(xiě)與管理等操作是基于這些信息實(shí)現(xiàn)的。

3.3 斷電保護(hù)機(jī)制

便攜式電子設(shè)備使用過(guò)程中，如果突然斷電，且此時(shí)有應(yīng)用在進(jìn)行文件的更新，就可能導(dǎo)致操作中止，文件系統(tǒng)信息由于沒(méi)有同步地進(jìn)行更新而不完整，進(jìn)而導(dǎo)致重啟系統(tǒng)加載分區(qū)時(shí)失敗。

所以，YAFFS2文件系統(tǒng)在實(shí)現(xiàn)各種文件操作時(shí)，就要考慮到各種文件操作的原子性，其實(shí)現(xiàn)方法主要就是存儲(chǔ)一些冗余信息保證文件系統(tǒng)的完整性。例如，在實(shí)現(xiàn)文件刪除操作時(shí)，為每個(gè)分區(qū)定義一個(gè)delete目錄，當(dāng)刪除某個(gè)文件時(shí)，僅修改目錄樹(shù)結(jié)構(gòu)，使該文件掛在該目錄下；當(dāng)需要更新文件的目錄信息和文件數(shù)據(jù)時(shí)，只是將新的數(shù)據(jù)寫(xiě)入一個(gè)新的頁(yè)，然后將原有數(shù)據(jù)頁(yè)的OOB的標(biāo)志位設(shè)置為無(wú)效。在更新文件數(shù)據(jù)時(shí)，會(huì)同時(shí)更新頁(yè)的數(shù)據(jù)區(qū)和OOB區(qū)，若在這個(gè)過(guò)程中任何時(shí)候斷電，就會(huì)導(dǎo)致最后寫(xiě)入的OOB區(qū)域數(shù)據(jù)不完整，該寫(xiě)入操作就不會(huì)破壞分區(qū)數(shù)據(jù)的完整性，下次加載時(shí)，原有數(shù)據(jù)會(huì)被作為有效數(shù)據(jù)處理，不完整的新數(shù)據(jù)會(huì)被當(dāng)作無(wú)效數(shù)據(jù)頁(yè)被丟棄掉。

改進(jìn)后，當(dāng)要改變文件的目錄樹(shù)結(jié)構(gòu)時(shí)，會(huì)為該文件寫(xiě)入新的文件頭，其中包含了該文件新的父目錄的ID等目錄結(jié)構(gòu)信息，在寫(xiě)入時(shí)，并不是更新原有的數(shù)據(jù)頁(yè)，而是寫(xiě)入一個(gè)新的數(shù)據(jù)頁(yè)，由于寫(xiě)任何數(shù)據(jù)頁(yè)都需要構(gòu)造fat索引結(jié)構(gòu)，并將該索引結(jié)構(gòu)寫(xiě)入同一個(gè)存儲(chǔ)塊的第1頁(yè)，這樣就存在2個(gè)寫(xiě)操作，且一個(gè)是寫(xiě)入第1頁(yè)，一個(gè)是寫(xiě)入另外一個(gè)頁(yè)，當(dāng)在這2個(gè)頁(yè)的寫(xiě)操作中間意外斷電時(shí)，重啟后加載文件系統(tǒng)時(shí)，會(huì)發(fā)現(xiàn)2個(gè)存儲(chǔ)頁(yè)包含相同相同的文件頭信息。所以必須進(jìn)行特別的處理來(lái)保證斷電保護(hù)性能，在實(shí)現(xiàn)中，為了能從這2個(gè)沖突的存儲(chǔ)頁(yè)中區(qū)分開(kāi)來(lái)，就需要用到上述的每個(gè)fat結(jié)構(gòu)中的序列號(hào)和每個(gè)存儲(chǔ)塊起始處的序列號(hào)，其設(shè)計(jì)原理如圖4所示。當(dāng)需要將某存儲(chǔ)塊中比較新的數(shù)據(jù)寫(xiě)入新的存儲(chǔ)頁(yè)時(shí)，就將相應(yīng)的fat結(jié)構(gòu)中的序列號(hào)遞增，并隨之寫(xiě)進(jìn)存儲(chǔ)塊中，若這時(shí)意外斷電，就可以根據(jù)兩個(gè)存儲(chǔ)頁(yè)對(duì)應(yīng)的fat結(jié)構(gòu)中的序列號(hào)來(lái)判斷哪個(gè)是原有數(shù)據(jù)，哪個(gè)是新的數(shù)據(jù)，從而保證文件系統(tǒng)的完整性；如果只是更新數(shù)據(jù)頁(yè)，fat結(jié)構(gòu)中的序列號(hào)不用遞增，因?yàn)榧词挂馔鈹嚯?，重啟加載時(shí)，根據(jù)存儲(chǔ)塊的序列號(hào)就可以知道哪個(gè)是最后寫(xiě)入的有效存儲(chǔ)頁(yè)，哪個(gè)是舊的需要更新的數(shù)據(jù)頁(yè)，這是因?yàn)槊總€(gè)存儲(chǔ)塊的序列號(hào)代表了其上面存儲(chǔ)的文件的先后順序，它是文件系統(tǒng)在分配塊時(shí)計(jì)算并寫(xiě)入的。

圖4 斷電保護(hù)原理

3.4 垃圾回收策略

使用過(guò)程中，修改文件內(nèi)容、刪除文件會(huì)使得Flash存儲(chǔ)塊的部分扇區(qū)不再包含有效的數(shù)據(jù)，F(xiàn)lash存儲(chǔ)器的特性決定了這些區(qū)域在整個(gè)塊被擦除之前不可重寫(xiě)，將這些扇區(qū)所在的塊內(nèi)的有效數(shù)據(jù)重新存儲(chǔ)然后擦除該塊，并將其再次作為空閑塊，這個(gè)過(guò)程便稱(chēng)為垃圾回收。

在現(xiàn)有YAFFS2文件系統(tǒng)的垃圾回收處理過(guò)程中，當(dāng)文件系統(tǒng)需要向Flash存儲(chǔ)器中寫(xiě)入數(shù)據(jù)時(shí)，先檢查分區(qū)內(nèi)的空閑擦除塊的個(gè)數(shù)，若低于設(shè)定的文件系統(tǒng)的保留值，便啟動(dòng)垃圾回收線(xiàn)程，調(diào)用垃圾回收處理函數(shù)找出無(wú)效數(shù)據(jù)頁(yè)最多的存儲(chǔ)塊，然后將該存儲(chǔ)塊內(nèi)的所有有效數(shù)據(jù)寫(xiě)入當(dāng)前正在使用的塊，最后調(diào)用驅(qū)動(dòng)將該存儲(chǔ)塊擦除，供以后分配使用［10］。

在改進(jìn)后的垃圾回收處理過(guò)程中，垃圾回收操作的實(shí)現(xiàn)是用一個(gè)線(xiàn)程Garbage Collection線(xiàn)程實(shí)現(xiàn)的，并將它放入一個(gè)信號(hào)量的等待隊(duì)列中，或當(dāng)需要向設(shè)備寫(xiě)數(shù)據(jù)時(shí)，或者每隔一段設(shè)置好的時(shí)間，去喚醒該線(xiàn)程。該線(xiàn)程首先統(tǒng)計(jì)分區(qū)內(nèi)空閑存儲(chǔ)塊的數(shù)量，決定是否要啟動(dòng)回收處理，如果空閑塊數(shù)少于預(yù)設(shè)的保留塊數(shù)，則從分區(qū)的處于使用狀態(tài)的列表中找出無(wú)效數(shù)據(jù)最多的存儲(chǔ)塊，并進(jìn)行回收，否則從整個(gè)分區(qū)中找到最臟塊進(jìn)行回收。

回收的主要過(guò)程如圖5所示，回收過(guò)程中找最臟塊的2個(gè)策略包括無(wú)效數(shù)據(jù)扇區(qū)最多和序列號(hào)最小，即效率原則和均衡原則結(jié)合使用，達(dá)到存儲(chǔ)塊的均衡使用。從圖5中可以看出，主要根據(jù)每個(gè)存儲(chǔ)塊開(kāi)始4 Byte序列號(hào)知道存儲(chǔ)塊的使用順序，序列號(hào)越大表明越早被使用，從而垃圾回收處理應(yīng)該越早地回收該存儲(chǔ)塊，不會(huì)導(dǎo)致某個(gè)塊對(duì)應(yīng)的文件數(shù)據(jù)被頻繁的更改而重復(fù)擦寫(xiě)，一定程度上保證了存儲(chǔ)塊的均衡使用。當(dāng)回收某個(gè)臟塊時(shí)，將該存儲(chǔ)塊中所有有效數(shù)據(jù)讀出，復(fù)制到分區(qū)的分配存儲(chǔ)塊，對(duì)于每個(gè)扇區(qū)數(shù)據(jù)都要構(gòu)造相應(yīng)的fat索引結(jié)構(gòu)，如文件頁(yè)號(hào)、Flash頁(yè)號(hào)等，并將其順序地寫(xiě)入相應(yīng)存儲(chǔ)塊的第一個(gè)頁(yè)，這樣就完成了數(shù)據(jù)的復(fù)制。最后將原來(lái)的臟塊加入回收列表，觸發(fā)驅(qū)動(dòng)的擦除操作，將整個(gè)塊擦除，并標(biāo)記該塊為空閑塊，加入到分區(qū)的空閑列表，供后面分配使用。

圖5 垃圾回收算法

4 性能測(cè)試

下面基于一款數(shù)字電視平臺(tái)對(duì)文件系統(tǒng)的安裝時(shí)間，讀寫(xiě)速度和損耗平衡性能進(jìn)行測(cè)試和分析，該硬件平臺(tái)同時(shí)支持NAND、NOR存儲(chǔ)器并有MMC控制器支持MMC卡，由于它們的存儲(chǔ)空間不同，在下面的測(cè)試中統(tǒng)一格式化一個(gè)8 MB的分區(qū)，并進(jìn)行相應(yīng)測(cè)試。

4.1 文件系統(tǒng)加載時(shí)間

YAFFS2文件系統(tǒng)分區(qū)加載時(shí)，讀取每個(gè)存儲(chǔ)塊的狀態(tài)信息，然后根據(jù)其狀態(tài)分別讀取文件系統(tǒng)信息，對(duì)于原有的YAFFS2，是通過(guò)讀存儲(chǔ)塊的每個(gè)頁(yè)的OOB區(qū)域，而改進(jìn)后的YAFFS2只是讀取每個(gè)存儲(chǔ)塊的第一個(gè)頁(yè)，它包含了當(dāng)前塊所有頁(yè)的索引fat結(jié)構(gòu)。在測(cè)試過(guò)程中，選擇一些隨機(jī)文件做一個(gè)YAFFS2鏡像文件，通過(guò)各自的格式化工具寫(xiě)到存儲(chǔ)分區(qū)上，然后加載相應(yīng)的分區(qū)，對(duì)于NOR Flash和MMC卡，分別采用各自的格式化工具格式化為JFFS2和FAT32文件系統(tǒng)［11］。

測(cè)試的加載時(shí)間如表2所示，從中可以看出，對(duì)于NAND分區(qū)，改進(jìn)后的安裝時(shí)間減少約25%；對(duì)于NOR分區(qū)，加載時(shí)間明顯減少，這是因?yàn)镴FFS2文件系統(tǒng)加載時(shí)需要以字節(jié)為單位掃描解析每個(gè)存儲(chǔ)頁(yè)，是JFFS2的主要缺點(diǎn)；而對(duì)于MMC分區(qū)，F(xiàn)AT32只需要讀取fat表就完成加載，所以時(shí)間明顯減少。

表2 分區(qū)加載時(shí)間 s

4.2 文件讀寫(xiě)速度

安裝文件系統(tǒng)后，分別進(jìn)行文件讀、寫(xiě)、刪除操作的性能測(cè)試，其中讀速度是通過(guò)將文件拷貝到系統(tǒng)的tmpfs分區(qū)得到的，寫(xiě)速度是通過(guò)將文件從tmpfs分區(qū)寫(xiě)入YAFFS2分區(qū)。讀寫(xiě)tmpfs分區(qū)的時(shí)間可以忽略，所以測(cè)試數(shù)據(jù)基本等于文件的讀寫(xiě)速度。

測(cè)試時(shí)使用tim e命令來(lái)記錄讀寫(xiě)100 KB文件的時(shí)間，改進(jìn)前后的YAFFS2測(cè)試結(jié)果如表3和表4所示。

表3 改進(jìn)前文件存取時(shí)間 s

表4 改進(jìn)后文件存取時(shí)間 s

測(cè)試結(jié)果表明，對(duì)于NAND存儲(chǔ)器，改進(jìn)前后文件的讀寫(xiě)速度差別很小，而NOR，MMC卡的讀寫(xiě)速度與NAND的差別大。這是因?yàn)槲募x寫(xiě)速度主要由存儲(chǔ)器驅(qū)動(dòng)的讀寫(xiě)速度決定，這些存儲(chǔ)器的讀寫(xiě)速度差別大，對(duì)于文件刪除操作，其速度相似是由于在實(shí)現(xiàn)刪除操作時(shí)，只是在文件系統(tǒng)信息中做一些標(biāo)志的更新，不需要同步寫(xiě)入存儲(chǔ)器，所以其速度快，即使文件大小不同，其刪除速度也較為接近。

4.3 損耗平衡性能

由于Flash存儲(chǔ)器的每個(gè)塊的擦除次數(shù)是有限的，因此應(yīng)可能地均衡擦除分區(qū)的每個(gè)存儲(chǔ)塊，延長(zhǎng)存儲(chǔ)器的整體使用壽命。為了統(tǒng)計(jì)每個(gè)存儲(chǔ)塊的擦除次數(shù)，使用一個(gè)全局列表來(lái)記錄每個(gè)塊的擦除次數(shù)，并在驅(qū)動(dòng)的擦除操作中更新該列表，當(dāng)擦除某個(gè)塊時(shí)，就將相應(yīng)的計(jì)數(shù)遞增。然后，通過(guò)文件拷貝和刪除命令，對(duì)測(cè)試分區(qū)上的文件進(jìn)行大量的改寫(xiě)操作，并做一些壓力測(cè)試。最后統(tǒng)計(jì)得出各存儲(chǔ)塊的擦除次數(shù)分布，實(shí)際測(cè)試結(jié)果表明，分區(qū)上的各存儲(chǔ)塊被均衡地使用，垃圾回收操作的2個(gè)回收策略達(dá)到了預(yù)期的效果。

5 結(jié)束語(yǔ)

本文從Flash存儲(chǔ)器管理、文件的創(chuàng)建和讀寫(xiě)的實(shí)現(xiàn)分析YAFFS2文件系統(tǒng)的設(shè)計(jì)原理，提出一種新的存儲(chǔ)方式，分別從文件系統(tǒng)安裝過(guò)程、垃圾回收、掉電保護(hù)機(jī)制方面對(duì)YAFFS2進(jìn)行改進(jìn)，并設(shè)計(jì)文件系統(tǒng)鏡像格式化工具。在系統(tǒng)平臺(tái)上進(jìn)行了安裝時(shí)間、讀寫(xiě)速度和損耗平衡性能的測(cè)試，結(jié)果表明改進(jìn)的文件系統(tǒng)安裝時(shí)間有所減少，并能使Flash各存儲(chǔ)扇區(qū)被均衡使用。但由于各種Flash存儲(chǔ)器每個(gè)塊的存儲(chǔ)頁(yè)數(shù)差別較大，可能會(huì)導(dǎo)致fat結(jié)構(gòu)未必能全部存儲(chǔ)在首頁(yè)，因此下一步將針對(duì)一些特殊的Flash存儲(chǔ)器要求改進(jìn)fat結(jié)構(gòu)，使其具有更廣泛的適用性。

［1］ W okey.YAFFS NAND Flash Filesystem［EB/OL］.（2007-03-05）.http：//www.aleph1.co.uk/yaffs/.

［2］ A leph One Ltd..Yaffs2 Specification［EB/OL］.（2007-06-08）.http：//www.yaffs.net/yaffs-2-specification.

［3］ 毛德操，胡希明.Linux內(nèi)核源代碼情景分析［M］.杭州：浙江大學(xué)出版社，2001.

［4］ 郭玉東.Linux操作系統(tǒng)結(jié)構(gòu)分析［M］.西安：西安電子科技大學(xué)出版社，2004.

［5］ Manning C.Flash File System Considerations［EB/OL］.（2009-02-03）.http：//www.yaffs.net/sites/yaffs.net.

［6］ 陳莉君.Linux操作系統(tǒng)內(nèi)核分析［M］.北京：人民郵電出版社，2003.

［7］ Manning C.How YAFFSWorks［EB/OL］.（2010-09-05）. http：//www.yaffs.net/sites/yaffs.net/files/How Yaffs W orks.pdf.

［8］ Hoog A.Android YAFFS2 Support［EB/OL］.（2014-10-08）. http：//www.basistech.com/wp-content/uploads/2014/04.

［9］ Zimmermann C.Forensic Analysis of YAFFS2［EB/OL］.（2012-04-09）.http：//aleph1.co.uk/gitweb？p=yaffs2.git.

［10］ Pooters I.Yaffs Object Header［EB/OL］.（2010-06-08）. http：//sandbox.dfrws.org/2011/fox-it/DFRWS2011_results/ Report.

［11］ 宋 聿，蔣烈輝，董衛(wèi)宇，等.一種獨(dú)立式I/O虛擬化方法研究［J］.計(jì)算機(jī)工程，2014，40（10）：81-85.

編輯 金胡考

Research and ImProvement of YAFFS2 File System Based on Em bedded Linux

ZHU Shaoying，ZHA Qipeng
（The 32nd Research Institute of China Electronics Technology Group Corporation，Shanghai 200233，China）

YAFFS2 file system is NAND Flash only file system.This paper analyzes the design principle of YAFFS2 based on embedded Linux in two aspects of Flash storage and filemanagement.Aiming at two limitations of long mount time and applicable only on NAND Flash，it proposes a new layout of file system key data and structure，and improves YAFFS2 in aspects of storage management，file system initialization，garbage collection and power off protection to reduce mount time and to make it applicable on other Flash.Test result show s that it can reducemount time by 25%and balance erasure of every block as expected.

YAFFS2 file system；NAND Flash；embedded Linux system；garbage collection strategy；wear-leveling

朱紹英，查啟鵬.基于嵌入式Linux的YAFFS2文件系統(tǒng)研究與改進(jìn)［J］.計(jì)算機(jī)工程，2015，41（9）：292-297，302.

英文引用格式：Zhu Shaoying，Zha Qipeng.Research and Improvement of YAFFS2 File System Based on Embedded Linux［J］.Computer Engineering，2015，41（9）：292-297，302.

1000-3428（2015）09-0292-06

A

TP391

10.3969/j.issn.1000-3428.2015.09.054

朱紹英（1983-），女，工程師，主研方向：嵌入式Linux系統(tǒng)；查啟鵬，工程師。

2015-04-07

2015-05-19 E-m ail：zhushaoying181@163.com