鞠高明　俞建新

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

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

中圖分類號：TP334 文獻標識碼：A 文章編號：1009-3044（2014）04-0749-06

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

NAND型閃存具有擦除速度快、批量寫入速度快、容量大等優(yōu)點，所以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ū)動直接管理閃存。

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

由于采用FTL加傳統(tǒng)磁盤文件系統(tǒng)這種設(shè)計方法增加了中間轉(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è)計。日志結(jié)構(gòu)文件系統(tǒng)并不采用本地更新的方式，而是采用異步更新的方式，即當某個數(shù)據(jù)塊需要更新時，先找一個新塊將新數(shù)據(jù)寫入，再將舊塊擦除。不過舊數(shù)據(jù)并不馬上在閃存中擦除，而是以日志方式作為歷史記錄保存下來，這為文件系統(tǒng)的恢復(fù)操作打下了基礎(chǔ)。

從圖1中可以看出一般的閃存文件系統(tǒng)都是建立在MTD層的基礎(chǔ)上，UBIFS是建立在UBI層的基礎(chǔ)上，這是一種比較好的數(shù)據(jù)抽象方式。UBIFS模塊包含不易變化運作空間的代碼。回寫、垃圾回收、日志等都屬于這部分；UBI模塊包含了未來可能會變化運作空間的代碼和對下層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)存在的掛載時間長、內(nèi)存消耗大、可擴展性差、損耗均衡處理能力差等問題。JFFS2的掛載時間是跟Flash大小成線性比的，UBIFS克服了這一弱點（UBI子模塊掛載時間還是與Flash大小成線性比的）。

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

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

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

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

3）回寫。回寫顯著地提高了文件系統(tǒng)的吞吐量。

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

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

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

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

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

2 MTD簡介

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

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

3 UBI模塊

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

UBI模塊功能主要是如下：

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

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

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

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

5）UBI對掉電情況進行處理，包括復(fù)制卷表，自動更換LEB，檢驗要寫入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)卷和動態(tài)卷，靜態(tài)卷是只讀的，由CRC-32校驗和保護；動態(tài)卷是可讀寫的，該數(shù)據(jù)完整性由上層負責。根據(jù)用途，UBI卷可分為用戶卷和內(nèi)部卷，內(nèi)部卷外部不可見，僅供UBI內(nèi)部使用，現(xiàn)在UBI中只有一個內(nèi)部卷：布局（layout）卷，其余都是用戶卷。

2）PEB頭部

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

3.2 UBI中的表

UBI模塊需要管理三張表：

1） volume表：包含每個卷信息，比如卷的大小、卷更新標記、卷號等。

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

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

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

EBA和EC表是在每次掛載MTD設(shè)備時建立，這意味著UBI必須掃描整個Flash，從每個PEB讀取VID和EC頭部以構(gòu)造EBA和EC表。相對于volume表，EBA和EC表變動較大，因為每次對PEB寫時都有可能修改表。每個UBI卷都有一個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)度擦除該PEB，unmap并不會等到擦除完成，該擦除由UBI后臺進程負責。

3.3 損耗均衡

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

可以根據(jù)數(shù)據(jù)類型將損耗均衡分為靜態(tài)損耗均衡和動態(tài)損耗均衡，靜態(tài)損耗均衡對象是Flash上的靜態(tài)數(shù)據(jù)，如文件系統(tǒng)、操作系統(tǒng)鏡像等；動態(tài)損耗均衡對象是Flash上的動態(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重新封裝，主要是加入擦除計數(shù)值，并將該PEB加入到紅黑樹中。損耗均衡紅黑樹分為以下四種類型[2]：

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

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

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

4）用erroneous紅黑樹組織錯誤使用的PEB。

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

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

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

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

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

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

3.4 快速映射

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

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

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

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

3.5 壞塊管理

UBI在兩種情況下標記PEB為壞塊：

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

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

4 UBIFS模塊

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

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

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

因為UBIFS模塊面向的是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é)點存放數(shù)據(jù)：LEB屬性，與索引樹不同的是，LPT中有三種節(jié)點：內(nèi)節(jié)點、外節(jié)點、公共節(jié)點。

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

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

4.1 UBIFS的分區(qū)

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

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

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

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

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

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

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

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

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

4.2 垃圾回收

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

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

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

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

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

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

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

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

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

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

⑥函數(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 實驗結(jié)果

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

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

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

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

該實驗結(jié)果如圖6。

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

參考文獻：

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

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

[3] 韋斯，丁志剛，張偉宏. LINUX 下 UBI 子系統(tǒng)的研究與應(yīng)用[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.