鞠高明　俞建新

摘要：該文詳細(xì)介紹了無序區(qū)塊映像文件系統(tǒng)（Ubifs）三個(gè)組成模塊，并對其中使用的垃圾回收和損耗均衡算法做了深入分析。同時(shí)介紹了一個(gè)新特性：快速映射。隨后對快速映射進(jìn)行實(shí)驗(yàn)分析，證明快速映射的確可以大幅降低掛載時(shí)間。

關(guān)鍵詞： UBIFS；UBI；快速映射；垃圾回收；損耗均衡

中圖分類號(hào)：TP334 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）04-0749-06

閃速存儲(chǔ)器（Flash Memory）是一種非易失性存儲(chǔ)器，簡稱閃存。閃存的不易揮發(fā)性、抗震性、靈活性、低功耗以及高速的讀寫速度等特點(diǎn)使之常用于嵌入式平臺(tái)和移動(dòng)計(jì)算機(jī)?，F(xiàn)在有兩種主流的閃存，分別是NOR型和NAND型。NOR型和NAND型閃存的主要差別之一是IO接口不同。NOR型閃存采用總線接口，允許隨機(jī)讀寫任意位置的存儲(chǔ)數(shù)據(jù)。NAND型閃存采用多路復(fù)用的IO接口，串行地存取數(shù)據(jù)，它雖然能以字節(jié)或字為單位尋址，但最小存取單元是頁（Page）。NAND型閃存的擦除操作以塊（block）為最小單位進(jìn)行，一個(gè)塊又由若干頁構(gòu)成。NAND型閃存有三個(gè)主要物理特性：頁塊結(jié)構(gòu)、先擦后寫、擦除限制。頁塊結(jié)構(gòu)使得閃存文件系統(tǒng)的數(shù)據(jù)訪問管理圍繞（Erase Blocks，簡稱EB）擦除塊展開；先擦后寫使閃存文件系統(tǒng)需要支持異步更新（out of update），因?yàn)橐话悴脸粋€(gè)塊的時(shí)間是寫一個(gè)塊的時(shí)間的100倍[5]；擦除次數(shù)限制使得閃存文件系統(tǒng)必須使用損耗均衡算法，力求做到各個(gè)塊擦除次數(shù)基本差不多，實(shí)現(xiàn)延長閃存壽命。

NAND型閃存具有擦除速度快、批量寫入速度快、容量大等優(yōu)點(diǎn)，所以NAND型閃存具有更加廣泛的應(yīng)用前景。UBIFS閃存文件系統(tǒng)主要用于NAND型閃存。

目前Linux系統(tǒng)中使用閃存的方法主要有兩種：

1）采用閃存轉(zhuǎn)化層（Flash Translation Layer，F(xiàn)TL）。主要思想是通過該層將閃存硬件模擬成普通磁盤文件。

2）采用閃存文件系統(tǒng)，如JFFS2、YAFFS2、UBIFS等。閃存文件系統(tǒng)管理通過硬件驅(qū)動(dòng)直接管理閃存。

閃存文件系統(tǒng)層次結(jié)構(gòu)圖如圖1所示[4]。

由于采用FTL加傳統(tǒng)磁盤文件系統(tǒng)這種設(shè)計(jì)方法增加了中間轉(zhuǎn)換環(huán)節(jié)，工作效率低，并且不能發(fā)揮閃存固有優(yōu)勢，所以開發(fā)了專門面向閃存的文件系統(tǒng)。具有代表性的文件系統(tǒng)有Cramfs、YAFFS/YAFFS2、JFFS/JFFS2、UBIFS等。面向Linux的閃存文件系統(tǒng)絕大部分都是基于日志結(jié)構(gòu)文件系統(tǒng)設(shè)計(jì)。日志結(jié)構(gòu)文件系統(tǒng)并不采用本地更新的方式，而是采用異步更新的方式，即當(dāng)某個(gè)數(shù)據(jù)塊需要更新時(shí)，先找一個(gè)新塊將新數(shù)據(jù)寫入，再將舊塊擦除。不過舊數(shù)據(jù)并不馬上在閃存中擦除，而是以日志方式作為歷史記錄保存下來，這為文件系統(tǒng)的恢復(fù)操作打下了基礎(chǔ)。

從圖1中可以看出一般的閃存文件系統(tǒng)都是建立在MTD層的基礎(chǔ)上，UBIFS是建立在UBI層的基礎(chǔ)上，這是一種比較好的數(shù)據(jù)抽象方式。UBIFS模塊包含不易變化運(yùn)作空間的代碼?；貙?、垃圾回收、日志等都屬于這部分；UBI模塊包含了未來可能會(huì)變化運(yùn)作空間的代碼和對下層MTD的封裝。損耗均衡等屬于易變化部分，壞塊管理等屬于對下層MTD的封裝。

從圖1中可以看出UBIFS主要與三大模塊相關(guān)：UBIFS、UBI、MTD。MTD層主要是面向物理擦除塊（Physical Erase Block，PEB），UBI模塊抽象出邏輯擦除塊（Logical Erase Block，LEB），并且UBI模塊封裝管理LEB到PEB的映射，這樣UBI上層模塊（UBIFS）只需要使用LEB，而不需要關(guān)心PEB。該文源碼分析對象是Linux3.8.8內(nèi)核。UBIFS模塊相關(guān)代碼集中在fs/ubifs目錄下[6]，UBI模塊相關(guān)代碼集中在drivers/mtd/ubi目錄下，而MTD模塊相關(guān)代碼集中在drivers/mtd目錄下。

1 UBIFS簡介

UBIFS（Unsorted Block Image File System，無序區(qū)塊映像文件系統(tǒng)）是Linux上正在研發(fā)的新一代閃存文件系統(tǒng)，目前由Nokia公司和匈牙利賽格德大學(xué)（Szeged University）共同開發(fā)，UBIFS是JFFS2的后繼閃存文件系統(tǒng)，有代替JSSF2的趨勢。UBIFS的出現(xiàn)主要是解決JFFS2文件系統(tǒng)存在的掛載時(shí)間長、內(nèi)存消耗大、可擴(kuò)展性差、損耗均衡處理能力差等問題。JFFS2的掛載時(shí)間是跟Flash大小成線性比的，UBIFS克服了這一弱點(diǎn)（UBI子模塊掛載時(shí)間還是與Flash大小成線性比的）。

UBIFS與JFFS2有三個(gè)主要的區(qū)別：JFFS2將索引（inode）存儲(chǔ)在RAM上，UBIFS將索引存儲(chǔ)在Flash上；JFFS2運(yùn)行在MTD設(shè)備層之上，UBIFS運(yùn)行在UBI層的基礎(chǔ)上；JFFS2不支持回寫，UBIFS支持回寫（write-back）。

總的來說，UBIFS文件系統(tǒng)具有如下特點(diǎn)：

1）可擴(kuò)展性強(qiáng)。UBIFS掛載時(shí)間、內(nèi)存消耗以及I/O速度不依賴與Flash大小。當(dāng)后續(xù)需要修改UBIFS閃存文件系統(tǒng)時(shí)，只需要修改UBI模塊即可。

2）掛載速度快。不同于JFFS2，UBIFS在掛載階段不需要掃描整個(gè)文件系統(tǒng)，掛載時(shí)間是毫秒級(jí)的。

3）回寫?；貙戯@著地提高了文件系統(tǒng)的吞吐量。

4）異常恢復(fù)。即使不干凈（unclean）重啟或者掉電，UBIFS文件系統(tǒng)都可以恢復(fù)。

5）快速I/O技術(shù)。即使禁用回寫，UBIFS的I/O性能也接近JFFS2。

6）靈活的壓縮技術(shù)。UBIFS可以對單個(gè)文件打開、關(guān)閉壓縮功能。

7）可恢復(fù)性。如果文件系統(tǒng)索引信息被破壞，UBIFS可以通過掃描整個(gè)閃存來恢復(fù)文件系統(tǒng)。

8）完整性。UBIFS通過將校驗(yàn)和寫到Flash介質(zhì)來保證數(shù)據(jù)的完整性。

2 MTD簡介

MTD（Memory Technology Device，內(nèi)存技術(shù)設(shè)備）是用于訪問存儲(chǔ)設(shè)備（ROM、Flash）的Linux硬件抽象，它隱藏了Flash的許多硬件特性，為上層提供一個(gè)統(tǒng)一的抽象接口。MTD是一組底層驅(qū)動(dòng)的集合，它抽象出文件系統(tǒng)所需的接口函數(shù)[6]，包括閃存物理塊的讀、寫、擦除等操作，即mtd_read（）、mtd_write（）、mtd_erase（）等。一般而言，MTD代碼由各個(gè)具體的Flash芯片生產(chǎn)商編寫和提供。

MTD層提供了對擦除塊的讀寫、擦除、判斷是否為壞塊、對壞塊進(jìn)行標(biāo)記等功能。不過MTD并不對上層隱藏壞塊信息，MTD只是將壞塊進(jìn)行標(biāo)記。同時(shí)MTD不對擦除塊做任何損耗均衡處理。

3 UBI模塊

UBI（ Unsorted Block Images）是工作在MTD之上的卷管理系統(tǒng)，它管理Flash設(shè)備上的多個(gè)邏輯卷，并能夠?qū)/O負(fù)載均勻的分布到Flash上。一個(gè)UBI卷，就是由一組連續(xù)的LEB組成的。

UBI模塊功能主要是如下：

1）提供對Flash的卷式管理，包括管理PEB到LEB的映射管理。

2）對上層隱藏壞的擦除塊，1%的PEB將保留作為UBI壞塊管理使用，如果一個(gè)PEB變成壞塊，相應(yīng)的LEB就會(huì)被重新映射到另一個(gè)PEB。

3）提供對擦除塊的損耗均衡處理。

4）使位反轉(zhuǎn)造成的數(shù)據(jù)丟失的概率降低最低，UBI使用ECC（Error Correcting Code）處理位反轉(zhuǎn)。

5）UBI對掉電情況進(jìn)行處理，包括復(fù)制卷表，自動(dòng)更換LEB，檢驗(yàn)要寫入Flash的數(shù)據(jù)。

3.1 UBI模塊中重要數(shù)據(jù)結(jié)構(gòu)

1）UBI卷

UBI卷類似于MTD的分區(qū)，都是用來存放文件系統(tǒng)數(shù)據(jù)的容器，支持讀、寫、擦除。和MTD不同的是，UBI卷由LEB組成，而MTD分區(qū)由PEB組成。

UBI卷根據(jù)數(shù)據(jù)類型可分為靜態(tài)卷和動(dòng)態(tài)卷，靜態(tài)卷是只讀的，由CRC-32校驗(yàn)和保護(hù)；動(dòng)態(tài)卷是可讀寫的，該數(shù)據(jù)完整性由上層負(fù)責(zé)。根據(jù)用途，UBI卷可分為用戶卷和內(nèi)部卷，內(nèi)部卷外部不可見，僅供UBI內(nèi)部使用，現(xiàn)在UBI中只有一個(gè)內(nèi)部卷：布局（layout）卷，其余都是用戶卷。

2）PEB頭部

UBI模塊在每個(gè)PEB的起始區(qū)域存放了兩個(gè)大小為64字節(jié)的頭部信息：ECH（Erase Count Header，擦除計(jì)數(shù)頭）、VIDH（Volume IDentifier Header，卷ID頭）。UBI使用CRC-32校驗(yàn)和保護(hù)這兩個(gè)頭。其中ECH保存PEB擦除次數(shù)，VIDH保存PEB所屬的卷ID號(hào)、卷類型等信息。

3.2 UBI中的表

UBI模塊需要管理三張表：

1） volume表：包含每個(gè)卷信息，比如卷的大小、卷更新標(biāo)記、卷號(hào)等。

2） EBA（Erase Block Association，擦除塊關(guān)聯(lián)）表：EBA表包含所有LEB到PEB的映射信息。

3）EC（Erase Counter，擦除計(jì)數(shù)）表：EC表包含著每一個(gè)PEB的擦寫次數(shù)。

volume表維護(hù)在Flash上，volume表存儲(chǔ)在前面提到的layout內(nèi)卷中，layout內(nèi)卷包含兩個(gè)LEB，每個(gè)LEB都包含一份volume表。volume表僅僅在UBI卷被創(chuàng)建、刪除和重定義大小時(shí)改變。

EBA和EC表是在每次掛載MTD設(shè)備時(shí)建立，這意味著UBI必須掃描整個(gè)Flash，從每個(gè)PEB讀取VID和EC頭部以構(gòu)造EBA和EC表。相對于volume表，EBA和EC表變動(dòng)較大，因?yàn)槊看螌EB寫時(shí)都有可能修改表。每個(gè)UBI卷都有一個(gè)EBA表，用eba_tbl結(jié)構(gòu)表示。

對EBA表最重要的操作是map和unmap， map過程是首先找到相應(yīng)的PEB，然后將VID頭寫入PEB，然后修改內(nèi)存中相應(yīng)的EBA表。unmap首先解除LEB與相應(yīng)PEB的映射，然后調(diào)度擦除該P(yáng)EB，unmap并不會(huì)等到擦除完成，該擦除由UBI后臺(tái)進(jìn)程負(fù)責(zé)。

3.3 損耗均衡

損耗均衡（wear-leveling，簡稱WL）指的是Flash中的各個(gè)擦除塊在整個(gè)壽命周期內(nèi)得到平衡的使用，而不會(huì)出現(xiàn)部分擦除塊壽命耗盡而其余擦除塊尚未的到充分使用的情況。

可以根據(jù)數(shù)據(jù)類型將損耗均衡分為靜態(tài)損耗均衡和動(dòng)態(tài)損耗均衡，靜態(tài)損耗均衡對象是Flash上的靜態(tài)數(shù)據(jù)，如文件系統(tǒng)、操作系統(tǒng)鏡像等；動(dòng)態(tài)損耗均衡對象是Flash上的動(dòng)態(tài)數(shù)據(jù)。

內(nèi)核使用的損耗均衡主要原理是：將擦除次數(shù)較少的used PEB中的數(shù)據(jù)搬移到擦除次數(shù)較多的free PEB中，從而平衡所有PEB的擦除次數(shù)。

損耗均衡模塊工作的對象是PEB，它并不關(guān)心上層的邏輯卷和LEB，所有UBIFS系統(tǒng)上的PEB管理都交給了該模塊。損耗均衡模塊將PEB分為兩類：used、free。損耗均衡模塊使用ubi_wl_entry結(jié)構(gòu)體對PEB重新封裝，主要是加入擦除計(jì)數(shù)值，并將該P(yáng)EB加入到紅黑樹中。損耗均衡紅黑樹分為以下四種類型[2]：

1）用free紅黑樹組織空閑的PEB；

2）用used紅黑樹組織含有效數(shù)據(jù)的PEB；

3）用scrub紅黑樹組織出現(xiàn)位反轉(zhuǎn)的PEB；

4）用erroneous紅黑樹組織錯(cuò)誤使用的PEB。

損耗均衡模塊核心函數(shù)是wear_leveling_worker（），該函數(shù)主要是選擇磨損均衡操作的源PEB和目的PEB，將源塊的有效數(shù)據(jù)復(fù)制到目的塊，并更新LEB和PEB之間的關(guān)系，然后源塊可成為可用的free PEB。主要步驟如下[1]：

①如果srub紅黑樹不為空，則選擇一個(gè)出現(xiàn)位反轉(zhuǎn)的塊作為源塊，并從free紅黑樹中選擇擦除次數(shù)較多的擦除塊作為目的擦除塊，然后進(jìn)行磨損均衡操作。因?yàn)槌霈F(xiàn)位反轉(zhuǎn)的塊急需通過擦除操作來恢復(fù)，所以此時(shí)不檢查兩個(gè)塊EC的差值是否超過閥值。

②如果①條件不滿足，則從used紅黑樹中選擇擦除次數(shù)最少的擦除塊作為源擦除塊，從free紅黑樹中選擇擦除次數(shù)較多的擦除塊作為目的擦除塊，比較這兩個(gè)擦除塊的EC的差值是否大幅預(yù)設(shè)的閥值，如果超過，則進(jìn)行磨損均衡操作，否則退出。

③檢查源擦除塊的VIDH信息，如果VIDH不存在，則表示其他線程已經(jīng)將該擦除塊插入used或scrub紅黑樹還沒來得及寫入VIDH信息，處理方法是：將此擦除塊插入保護(hù)隊(duì)列中，然后結(jié)束磨損均衡操作。

④如果③檢查VIDH完好，則將源擦除塊的VIDH信息和用戶有效數(shù)據(jù)搬移到目的塊，然后更新EBA表。

⑤如果數(shù)據(jù)搬移成功，則將目的塊插入used紅黑樹，然后申請?jiān)磯K的擦除操作。

3.4 快速映射

UBI快速映射（fastmap）是一個(gè)可選特性，從Linux3.7開始加入內(nèi)核?？焖儆成渲饕枷耄簩BI抽象的卷分成引用（reference）卷和數(shù)據(jù)卷，引用卷存放在閃存的前面部分（前64個(gè)PEB中的某個(gè)），引用卷所在區(qū)域稱為超級(jí)塊，數(shù)據(jù)卷所在位置稱為快速映射池（fastmap pool）。超級(jí)塊包含快速映射池位置，快速映射池中包含所有閃存物理信息和所以壓縮的PEB頭部（ECH和VIDH）。

快速映射池使用閃存上已刪除的卷，所以并不會(huì)與之前的源碼發(fā)生沖突?？焖儆成渲邪袙燧d時(shí)需要的信息，如每個(gè)PEB擦除計(jì)數(shù)值、PEB狀態(tài)、所有卷的狀態(tài)等?？焖儆成涑刂邪嗽趻燧d時(shí)可能需要修改的PEB以及需要掃描全部空間的PEB（一般的PEB只需要掃描頭部）。一般快速映射池占所有閃存空間的5%，未來可能只需要一個(gè)PEB就可以裝下整個(gè)快速映射模塊。

UBI運(yùn)行過程中可能會(huì)對快速映射模塊進(jìn)行修改，如快速映射池滿、UBI卸載、EBA表變動(dòng)等情況。加載了快速映射掛載UBI時(shí)，需要保證沒有修改EBA表的I/O操作，該保護(hù)機(jī)制可能會(huì)花費(fèi)掉一秒時(shí)間，所以快速映射在小容量的閃存上不具有優(yōu)勢。一般閃存容量越大，快速映射加速效果越明顯。

目前UBI模塊掛載過程：首先嘗試尋找超級(jí)塊（引用卷所在PEB），如果沒有找到，則使用傳統(tǒng)方法，掃描整個(gè)閃存；如果找到，則掃描超級(jí)塊指向的快速映射池中的PEB即可。詳情見圖2 快速映射下UBI掛載時(shí)需要掃描的部分。

3.5 壞塊管理

UBI在兩種情況下標(biāo)記PEB為壞塊：

①寫PEB失敗，此時(shí)，UBI把這個(gè)PEB的數(shù)據(jù)搬移到其他的PEB，然后診斷該P(yáng)EB是否出現(xiàn)為壞塊，如果是，標(biāo)記為壞塊。

②擦除操作出現(xiàn)I/O錯(cuò)誤，在這種情況下，直接把PEB標(biāo)記為壞塊。

4 UBIFS模塊

UBIFS模塊運(yùn)行在UBI模塊之上，即UBIFS面向的是LEBs，該模塊涉及到PEB部分都會(huì)下放給UBI模塊。

UBIFS模塊功能主要有如下幾點(diǎn)：靈活的壓縮技術(shù)、回寫（write-back）、日志（journal）、TNC（Tree Node Cache）、LPT（LEB Properties Tree）、大塊讀（bulk-read）。

前面介紹過，UBIFS的索引節(jié)點(diǎn)是存放在Flash上的，這樣做的好處是可以很容易恢復(fù)文件系統(tǒng)，但同時(shí)也帶來了問題。假設(shè)某PEB p1索引存放在PEB p2中，同時(shí)p2的索引在p3中，當(dāng)修改p1就需要修改p2，當(dāng)修改p2就需要修改p3，這可能會(huì)無窮無盡的修改下去。為了解決這個(gè)問題，使用B+樹存放索引節(jié)點(diǎn)，該B+樹中葉子節(jié)點(diǎn)存放數(shù)據(jù)，內(nèi)節(jié)點(diǎn)都是索引信息，當(dāng)修改葉子節(jié)點(diǎn)時(shí)只需要更新該B+樹高度次即可。當(dāng)然一次性寫這么多次Flash是比較低效的，這個(gè)問題主要通過TNC（Tree Node Cache）解決，TNC是存放在RAM中的索引樹，當(dāng)需要修改索引樹時(shí)，只是在TNC中做標(biāo)記，然后再一次性寫入Flash中。TNC同時(shí)還方便了對索引節(jié)點(diǎn)的讀取，不需要從Flash中讀取數(shù)據(jù)。UBIFS的索引號(hào)是不能復(fù)用的，即如果刪除了索引號(hào)為100的文件，整個(gè)文件系統(tǒng)周期不能使用該索引號(hào)。在Flash中的索引節(jié)點(diǎn)在TNC樹中稱為znode。

因?yàn)閁BIFS模塊面向的是LEB，所以該模塊有很多對LEB的操作，如讀、寫、申請LEB、回收LEB等。這些操作都建立在LEB屬性的基礎(chǔ)上。LEB屬性包括LEB類型（索引或者數(shù)據(jù)）、dirty空間大小、free空間的大小。UBIFS使用鏈表結(jié)構(gòu)管理LEB屬性，分別為[6]：

1）用uncat_list鏈表管理未分類的LEB。

2）用empty_list鏈表管理空的LEB。

3）用freeable_list鏈表管理類型為數(shù)據(jù)的LEB。

4）用frdi_idx_list鏈表管理類型為索引的LEB。

LPT（LEB Properties Tree，LEB屬性樹）是以B+樹形式管理LEB屬性。使用B+樹來管理LEB屬性是為了提高對LEB屬性操作的效率。LPT與索引樹類似，只有葉子節(jié)點(diǎn)存放數(shù)據(jù)：LEB屬性，與索引樹不同的是，LPT中有三種節(jié)點(diǎn)：內(nèi)節(jié)點(diǎn)、外節(jié)點(diǎn)、公共節(jié)點(diǎn)。

前面提過閃存文件系統(tǒng)基本都是基于日志文件系統(tǒng)的，UBIFS也不例外，當(dāng)日志中內(nèi)容達(dá)到一定程度時(shí)就需要將數(shù)據(jù)寫回到到Flash，并修改主節(jié)點(diǎn)（主節(jié)點(diǎn)分區(qū)中的節(jié)點(diǎn)，具體見下節(jié)），這個(gè)過程稱為commit（提交更新）。日志區(qū)就是記載上一次commit之后這一次commit之前這段時(shí)間中，操作了哪些LEB，這些LEB就稱之為bud（芽）。

前面介紹過回寫是UBIFS與JFFS2的三個(gè)主要區(qū)別之一，回寫的好處很明顯的，回寫可以提高文件系統(tǒng)吞吐量，但是同時(shí)也帶來了技術(shù)難題，即文件系統(tǒng)需要確認(rèn)RAM中將要寫入Flash的數(shù)據(jù)的大小不能超過空閑的閃存空間。UBIFS中的budget模塊就是專門處理這個(gè)難題的。

4.1 UBIFS的分區(qū)

超級(jí)塊分區(qū)（superblock area）使用LEB0。該區(qū)域保存文件系統(tǒng)配置相關(guān)信息，如：LEB大小、最大LEB數(shù)、日志區(qū)域占用的LEB數(shù)等。在UBIFS運(yùn)行期間，超級(jí)塊幾乎不會(huì)改變，只有resize時(shí)才會(huì)導(dǎo)致超級(jí)塊重寫。之所以需要resize是因?yàn)閯?chuàng)建UBIFS文件系統(tǒng)時(shí)，并不知道將要掛載的UBI卷的大小。

主節(jié)點(diǎn)分區(qū)（master area）使用LEB1和LEB2。主分區(qū)中包含兩個(gè)主節(jié)點(diǎn)，主節(jié)點(diǎn)保存索引樹根節(jié)點(diǎn)位置、為垃圾回收保留的LEB號(hào)、LPT管理的所有LEB臟空間總和等，

一般情況下，兩個(gè)主節(jié)點(diǎn)保存著相同數(shù)據(jù)，主節(jié)點(diǎn)大小為512 byte，每次寫入主節(jié)點(diǎn)會(huì)順序地使用LEB的空閑頁，直到?jīng)]有空閑頁時(shí)，再從偏移0開始寫主節(jié)點(diǎn)，這時(shí)會(huì)重新映射LEB。不會(huì)同時(shí)重新映射兩個(gè)主節(jié)點(diǎn)，因?yàn)檫@會(huì)導(dǎo)致文件系統(tǒng)沒有有效主節(jié)點(diǎn)，如果此時(shí)掉電，系統(tǒng)無法找到有效主節(jié)點(diǎn)。

日志分區(qū)（journal area）從LEB3開始。為了降低節(jié)點(diǎn)的更新頻率，UBIFS中創(chuàng)建了journal區(qū)，在其中緩存對節(jié)點(diǎn)的修改，然后一次寫到Flash上去，這樣就降低了更新的頻率。當(dāng)需要修改索引樹葉節(jié)點(diǎn)時(shí)并不會(huì)馬上更新閃存上的索引樹，首先更新RAM中的TNC，同時(shí)將更新信息以日志方式記錄在內(nèi)存中，等到commit時(shí)再更新閃存上的索引樹。

日志由log和bud組成。log記錄日志位置，log包含兩種類型的節(jié)點(diǎn)：commit開始節(jié)點(diǎn)、引用節(jié)點(diǎn)。commit開始節(jié)點(diǎn)記錄commit過程的開始，引用節(jié)點(diǎn)記錄bud的數(shù)量。

LEB屬性樹分區(qū)（LEB Properties Tree area，簡稱LPT area），跟隨在日志之后，LPT的大小在創(chuàng)建文件系統(tǒng)時(shí)確定，LPT使用B+樹結(jié)構(gòu)。該區(qū)域除了包含LEB屬性樹外，還維護(hù)一張擦除塊表LTAB（LPT area erase blocks）和一張LEB數(shù)量信息表LSAVE。LTAB是LPT所在LEB的屬性組成的表，因?yàn)長PT分區(qū)只占一兩個(gè)LEB，所以LTAB很小。

LPT有兩種不同的表現(xiàn)方式：小模型、大模型[8]。當(dāng)整個(gè)LEB屬性表可以寫在一個(gè)LEB上時(shí)，就使用小模型，垃圾回收時(shí)會(huì)重寫整個(gè)表，這樣所有其他擦除塊都變得可用了。相反，對于大模型，就是整個(gè)LEB屬性表不能寫在一個(gè)LEB上時(shí)，垃圾回收時(shí)僅僅選擇一個(gè)臟擦除塊，并將該塊上的干凈數(shù)據(jù)標(biāo)記為臟，然后將該塊上的數(shù)據(jù)全部回寫后擦除。

孤兒分區(qū)（orpan area）在log area和main area之間，使用固定數(shù)目的LEBs。一般來說，占用一個(gè)LEB，debug時(shí)會(huì)額外占用一個(gè)LEB。孤兒區(qū)域記錄已經(jīng)刪除的文件的索引號(hào)，孤兒區(qū)域的作用是當(dāng)擦除操作進(jìn)行到一半，卸載了文件系統(tǒng)時(shí)，該區(qū)域可以在下次掛載文件系統(tǒng)時(shí)將孤兒索引找到并刪除，UBIFS在孤兒區(qū)域中存儲(chǔ)了一張表保存孤兒索引。

主分區(qū)（main area）是最后一個(gè)分區(qū)，存放文件系統(tǒng)數(shù)據(jù)和索引。

4.2 垃圾回收

因?yàn)镕lash需要先擦除再寫，所以閃存文件系統(tǒng)需要支持異步更新。如果不使用異步更新，每次對Flash塊寫的時(shí)候都需要先擦除，這就會(huì)增加大量讀寫時(shí)間。同時(shí)異步更新需要垃圾回收（garbage collection，簡稱GC）的支持。GC是一個(gè)回收無效塊的過程（無效塊中包含了一些無效數(shù)據(jù)），回收過程包括將有效數(shù)據(jù)移動(dòng)到新塊，然后擦除無效塊從而使它變?yōu)榭捎?。如果文件系統(tǒng)的可用空間較少，那么通常將在后臺(tái)執(zhí)行這一過程（或者根據(jù)需要執(zhí)行）。

對于索引類型和數(shù)據(jù)類型的LEB，GC的處理方式區(qū)別較大。對應(yīng)數(shù)據(jù)類型的LEB，GC找到一個(gè)臟數(shù)據(jù)很多的LEB，并將其中有效數(shù)據(jù)拷貝到日志，此時(shí)這個(gè)LEB就可以重新使用了；對應(yīng)索引類型的LEB，GC在TNC中將該LEB有效的索引節(jié)點(diǎn)標(biāo)記為臟，下一次commit（提交更新）之后該LEB就可以重新使用了[6]。

GC可能由日志或者budget調(diào)用。UBIFS對文件系統(tǒng)的每次更新都會(huì)先作用在日志模塊上，類似函數(shù)ubifs_write_inode（）會(huì)調(diào)用ubifs_jnl_write_inode（）。所有日志模塊的讀、更新函數(shù)最后都會(huì)調(diào)用函數(shù)make_reservation（）預(yù)約日志空間，該函數(shù)首先調(diào)用函數(shù)reserve_space（），reserve_space（）首先會(huì)試著找free LEB，如果找不到就會(huì)調(diào)用ubifs_garbage_collect（）進(jìn)行垃圾回收。類似的，budegt首先會(huì)調(diào)用函數(shù)ubifs_budget_space（）來確認(rèn)是否有足夠的空間，如果該函數(shù)覺得空余空間不夠，會(huì)調(diào)用函數(shù)make_free_space（）產(chǎn)生新的空間，該函數(shù)會(huì)調(diào)用run_gc（）開始垃圾回收，run_gc（）則會(huì)調(diào)用ubifs_garbage_collect（）函數(shù)進(jìn)行真正的垃圾回收，具體如圖4所示。

圖4 垃圾回收觸發(fā)結(jié)構(gòu)圖

從上面分析可以看出GC核心部分就是函數(shù)ubifs_garbage_collect（），該函數(shù)主要步驟如下：

①首先檢查是否需要commit（提交更新），當(dāng)日志大小超過限制可能就需要commit，如果需要commit，則返回錯(cuò)誤碼給commit。

②檢查在準(zhǔn)備GC這段時(shí)間是否有空余LEB出現(xiàn)，即調(diào)用函數(shù)ubifs_find_dirty_leb（），它分別調(diào)用ubifs_fast_find_empty（）和ubifs_fast_find_freeable（）查找空的或者空余的LEB，如果有，則返回這個(gè)LEB，如果沒有則返回臟空間最多的LEB。

③如果②中有返回，說明沒有出現(xiàn)無臟LEB可回收的情況，此時(shí)ubifs_garbage_collect_leb（）會(huì)被調(diào)用，該函數(shù)用來回收一個(gè)LEB。

④函數(shù) ubifs_garbage_collect_leb（）首先檢查是否直接有一個(gè)空閑的LEB，如果有，則跳到⑥。

⑤掃描整個(gè)LEB，并將掃描結(jié)果放在相關(guān)結(jié)構(gòu)中（ubifs_scan_leb和ubifs_scan_node）。如果掃描的節(jié)點(diǎn)是索引節(jié)點(diǎn)則ubifs_dirty_idx_node（）會(huì)被調(diào)用，將索引節(jié)點(diǎn)標(biāo)記為臟；如果是數(shù)據(jù)節(jié)點(diǎn)則會(huì)調(diào)用move_nodes（）函數(shù)搬移節(jié)點(diǎn)。

⑥函數(shù)ubifs_garbage_collect_leb（）調(diào)用函數(shù)gc_sync_wbufs（）同步緩沖區(qū)，再調(diào)用ubifs_change_one_lp（）修改LEB屬性，最后調(diào)用函數(shù)ubifs_leb_unmap（）卸載LEB。

⑦ubifs_garbage_collect（）最后同步自己的緩沖區(qū)，即調(diào)用ubifs_wbuf_sync_nolock（）函數(shù)。

函數(shù)ubifs_garbage_collect（）調(diào)用函數(shù)如圖5所示。

5 實(shí)驗(yàn)結(jié)果

通過自編的腳本測試文件，利用精確到毫秒的系統(tǒng)時(shí)鐘進(jìn)行掛載時(shí)間測試，比較在不同大小閃存時(shí)，加載快速映射掛載UBI與不加載快速映射掛載UBI的時(shí)間。實(shí)驗(yàn)環(huán)境：

CPU：Intel（R） Core（TM） i7-2600，3.4G HZ。

Flash：使用nandsim模擬的閃存，頁大小為2Mb。

內(nèi)核版本：Linux3.8.8。

該實(shí)驗(yàn)結(jié)果如圖6。

從圖6可以看出加載快速映射的UBI模塊掛載時(shí)間基本是固定的；不加載快速映射的UBI模塊掛載時(shí)間與閃存大小成線性比。該實(shí)驗(yàn)證明快速映射確實(shí)可以減少UBI模塊掛載時(shí)間。

參考文獻(xiàn)：

[1] 樊進(jìn)，江敏.UBI損耗均衡機(jī)制簡析[J].電腦知識(shí)與技術(shù)，2010，6（25）：7125-7126.

[2] 韓春曉，陳香蘭，李曦，等.UBIFS損耗均衡對系統(tǒng)I/O性能的影響[J].計(jì)算機(jī)工程，2009，35（6）：260-262.

[3] 韋斯，丁志剛，張偉宏. LINUX 下 UBI 子系統(tǒng)的研究與應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2010，27（10）： 69-72.

[4] Olivier P， Boukhobza J， Senn E. Micro-benchmarking Flash Memory File-System Wear leveling and Garbage Collection：a Focus on Initial State Impact [C]// Bob Werner.Computational Science and Engineering （CSE）. Proceedings of 2012 IEEE 15th International Conference， 2012：437-444.

[5] Adrian Hunter. A Brief Introduction to Design of UBIFS[EB/OL].http：//www.linux-mtd.infradead.org/doc/ubifs_whitepaper.pdf. 2008 March.

[6] Linux3.8.8 Source Code[EB/OL]. https：//www.kernel.org/pub/linux/kernel/v3.x/linux-3.8.8.tar.gz.