一種支持FAT文件系統(tǒng)的Flash轉(zhuǎn)換層設計

匡 偉，呂霞付，陳 勇，鄭思遠

(重慶郵電大學網(wǎng)絡化控制與智能儀器儀表教育部重點實驗室，重慶 400065)

0 引言

Nand Flash因其非易失性、存取速度快、存儲密度高、功耗低、芯片引腳兼容性高和成本低等優(yōu)點［1-2］，作為一種可替代磁盤的存儲介質(zhì)，廣泛應用于手機、數(shù)碼相機和平板電腦等嵌入式設備中。文檔分配表文件(file allocation table，F(xiàn)AT)系統(tǒng)具有高效，實現(xiàn)邏輯簡單，兼容性高等特性，在嵌入式系統(tǒng)中得到了廣泛應用［3］。

Nand Flash存儲器具有先擦除后寫入的硬件特性［1，4］，F(xiàn)AT 文件系統(tǒng)是專門針對磁盤等存儲介質(zhì)而設計的，不適合直接應用于Nand Flash，直接在Flash上應用FAT會很快讓Flash局部老化而丟失數(shù)據(jù)［3，5］，必須為 Nand Flash 提供一個適配軟件閃存轉(zhuǎn)換層(flash translation layer，F(xiàn)TL)，將 Nand Flash模擬成一個與磁盤的特性兼容的塊設備［6］。

目前針對FTL的研究主要集中在壞塊管理、負載均衡和垃圾回收等方面，最大可能的將存儲塊以均等的機會分配給文件［5，7］。關于如何的減輕Nand Flash負載，減少Flash的擦除次數(shù)的研究卻很少。

本文提出一種基于緩沖機制應用于FAT文件系統(tǒng)的FTL，在RAM中為Flash分配一個用于讀寫的緩沖區(qū)，將一部分關于Flash的讀寫操作轉(zhuǎn)移到RAM上，減少Flash存儲塊的擦除次數(shù)，延長Flash的壽命，提高數(shù)據(jù)的讀寫速度，本系統(tǒng)在ARM9和hynix公司H8BCS0QG0芯片上得到驗證。

1 Nand Flash簡介

1.1 Nand Flash存儲結(jié)構(gòu)

Nand Flash存儲結(jié)構(gòu)如圖1所示，Nand Flash由多個塊(block)組成，每個block又是由多個頁(page)組成。

其中page是Nand Flash的最小讀寫單位，block是 Nand Flash 的最小擦除單位［5，8］。每個 block 都有10 000－100 000次的擦除次數(shù)限制。

圖1 Nand Flash的結(jié)構(gòu)Fig.1 Structure of Nand Flash

1.2 Spare area信息

由于Nand Flash的工藝不能保證Flash存儲塊在其生命周期中保持性能的可靠，有可能出現(xiàn)壞塊，所以Nand Flash的每個page分為main和spare區(qū)，main區(qū)存儲數(shù)據(jù)信息，spare區(qū)保存壞塊信息和錯誤檢查和糾正(error correcting code，ECC)信息等。Spare區(qū)存儲內(nèi)容的格式如圖2所示，BI是芯片出廠時的壞塊標志，ECC存儲main區(qū)數(shù)據(jù)的ECC校驗碼，Reserved為保留字節(jié)。

圖2 Nand Flash存儲頁的結(jié)構(gòu)Fig.2 Page structure of Nand Flash

2 FTL設計

2.1 Nand Flash的軟件構(gòu)架

Nand Flash模塊的軟件分為3層，本文主要講述FTL層的設計與實現(xiàn)。如圖3所示，F(xiàn)AT文件系統(tǒng)以sector為單位讀寫和刪除文件，管理存儲在Flash的文件。Flash分區(qū)與Nand Flash的硬件通信，F(xiàn)TL層通過映射算法將FAT中的邏輯sector轉(zhuǎn)換成物理存儲塊，再從對應的物理塊中讀/寫/擦除數(shù)據(jù)。

2.2 壞塊檢測與存儲塊管理

由于Nand Flash的工藝不能保證NAND的存儲塊在其生命周期中保持性能的可靠，在NAND的生產(chǎn)中及使用過程中都可能會產(chǎn)生壞塊［6，8］。壞塊可以分為兩大類:1)固有壞塊:芯片生產(chǎn)過程中產(chǎn)生的壞塊，一般芯片廠商都會在出廠時將每個壞塊第一個page的spare area的BI標記為一個不等于0xff的值;2)使用壞塊:Nand Flash使用過程中產(chǎn)生的壞塊，如果block擦除或者page寫入錯誤，就可以簡單地將這個塊作為壞塊來處理。

圖3 Nand Flash的軟件構(gòu)架Fig.3 Software structure of Nand Flash

系統(tǒng)初始化時，F(xiàn)TL依次讀取各個block的狀態(tài)，使用數(shù)組phy_blk_status［］來記錄各個物理塊的狀態(tài)。數(shù)組成員變量的可能值見表1。

表 1 phy_blk_status［］可能的值Tab.1 Possible value of phy_blk_status［］

物理塊狀態(tài)檢測:1)讀取block的spare area的第1個字節(jié)，如果此字節(jié)不為0xff，將block標記為壞塊;2)如果block第一個page和最后一個page都為0xff，表示當前block已被擦除，將block標記為空閑狀態(tài);3)如果當前block的第一個page或者最后一個page還沒有被編程，或者ECC校驗錯誤，擦除整個 block，block狀態(tài)標記為空閑狀態(tài);4)如果block的第一個page和最后一個page都已被編程，并且ECC校驗正確，將block標記為應用狀態(tài)，如(1)式所示，將邏輯塊與物理塊建立一個映射關系保存在數(shù)組l2p_map［］中。其中l(wèi)bn表示邏輯塊地址，pbn表示物理塊地址。

5)如果某個page編程失敗，則擦除當前page所在block，如果擦除也失敗就將當前block標志為壞塊，同時將block第一個page的spare area的BI標記為非0xff，和固有壞塊信息保持一致，更新block狀態(tài)表。

2.3 邏輯塊與物理塊之間的映射

由于壞塊的存在，Nand Flash的由一系列不連續(xù)的物理塊組成。FTL通過一個映射算法將物理塊映射成邏輯塊，將不連續(xù)的物理塊轉(zhuǎn)換成像磁盤一樣連續(xù)的邏輯塊，F(xiàn)AT可以像管理磁盤中的文件一樣來管理Flash中的文件。

FTL使用數(shù)組l2p_map［］來管理邏輯塊與物理塊的映射關系，如果文件系統(tǒng)中有m個邏輯塊，n個物理塊(n＞m)，則l2p_map［］數(shù)組的成員變量個數(shù)等于邏輯塊的個數(shù)m。Flash的每個page中有16字節(jié)的非易失性spare data，其中的最后2個字節(jié)為保留字節(jié)。又因為Nand Flash以block為單位進行擦除，F(xiàn)TL使用block的最后一個page的spare data的保留字節(jié)byte15和byte16存儲當前物理塊所對應的邏輯塊，spare區(qū)和main區(qū)數(shù)據(jù)在page編程時同時寫入。

邏輯塊和物理塊的映射算法如圖4所示，系統(tǒng)上電時，首先遍歷所有的物理塊，如果存儲塊j不是壞塊，則從物理塊j的spare區(qū)的保留字節(jié)中讀取邏輯塊號 k，按式(1)所示的關系令 l2p_map［k］=j，建立映射表l2p_map［］。

圖4 邏輯塊和數(shù)據(jù)塊的映射表Fig.4 Logical and physical block map

為了保持FTL的穩(wěn)定性，某個block成為壞塊后，F(xiàn)TL也可以繼續(xù)讀相應的block，寫操作將無法完成，從而保證Nand Flash的數(shù)據(jù)不會丟失，保持系統(tǒng)的穩(wěn)定性和可靠性。

3 FTL緩沖機制設計

3.1 緩沖機制

FAT對存儲介質(zhì)以sector為單位進行讀寫。而Nand Flash只能按page為單位進行讀寫，以block為單位進行擦除，page的大小一般為2 KBbyte，sector大小一般為512 Byte。由于Flash先擦后寫的特性，文件系統(tǒng)每更新一個存儲單元，就需要將存儲單元對應page的內(nèi)容讀出，擦除對應的block，再將修改過的內(nèi)容寫回。Nand Flash各個block的擦除次數(shù)是有限，對block的頻繁擦除，不但會縮短Flash的壽命，而且效率非常低。

針對此問題，F(xiàn)TL參照Linux虛擬盤的思想在RAM中分配一塊空間作為Nand Flash的緩存區(qū)，通過緩存區(qū)向文件系統(tǒng)提供讀寫功能。對文件系統(tǒng)而言，緩沖區(qū)是一片連續(xù)的字節(jié)空間，對其讀寫就好像對通用的按字節(jié)讀寫的存儲設備進行操作一樣。如果文件系統(tǒng)需要往Flash中寫入數(shù)據(jù)，首先將待寫入的數(shù)據(jù)寫入緩沖區(qū)，待數(shù)據(jù)寫入操作都已寫完或者緩沖區(qū)已滿，F(xiàn)TL將緩沖區(qū)的數(shù)據(jù)回寫到Flash中，從而減少多個小文件頻繁寫入而造成Flash存儲塊的多次擦除。

3.2 緩沖區(qū)設計

FTL緩沖區(qū)(cache)針對sectors和pages而設計，邏輯扇區(qū)號與邏輯塊號的對應關系如下

(2)，(3)式中:ps表示每個page的字節(jié)數(shù);ss表示每個sector的字節(jié)數(shù);spp表示每個page對應的扇區(qū)數(shù);sn表示扇區(qū)號;ppb表示每個block的page數(shù)。根據(jù)式(2)，(3)可得出如式(4)所示的邏輯sector與物理塊號的對應關系，sector在當前block的page偏移量如式(5)所示。其中l(wèi)bn表示邏輯塊號;pbn表示邏輯塊對應的物理塊號;poffset表示sector在block中page的偏移量。

本系統(tǒng)采用的Nand Flash的page的大小為2 KByte，F(xiàn)AT文件系統(tǒng)中sector的大小為512 Byte，F(xiàn)TL cache的結(jié)構(gòu)如圖5所示。系統(tǒng)分配3個block大小的緩存區(qū)供FTL使用，每個cache塊的大小為512 Byte，與sector大小相同，將(ss×ppb)個 cache塊用鏈表鏈接起來就可以緩存一個block大小的數(shù)據(jù)。block_cache結(jié)構(gòu)體中，block表示著當前緩存物理塊的邏輯塊號，count表示當前block中緩存的sector個數(shù)，dirty表示當前緩存block是否已被使用，age表示緩存block的年齡。sector_cache中sect表示當前緩存的sector號，dirty表示它是否被使用，next指向下一個sector，buffer是一個512 Byte的緩沖塊。

3.3 FTL數(shù)據(jù)的讀寫

1)數(shù)據(jù)讀取

FAT的最小讀寫單位為sector，當FAT讀取數(shù)據(jù)時，首先將根據(jù)(4)，(5)式計算出sector對應的block號和page號，然后從block中讀取對應 page的數(shù)據(jù)，如果當前sector已被緩存則更新cache的數(shù)據(jù)，如果sector未被緩存則從cache中尋找一個空閑的cache塊，將當前sector緩存到cache中，然后再從cache中讀取相應的數(shù)據(jù)。

圖5 FTL cache設計Fig 5 FTL cache design

2)數(shù)據(jù)寫入

sector_cache和block_cache都有一個成員dirty來指示它是否已被使用，數(shù)據(jù)寫入cache時，F(xiàn)TL依次搜索各個sector_cache，如果當前sector已被緩存，則直接將cache的數(shù)據(jù)更新，如果sector未被緩存，則從cache中搜索一個空閑sector_cache，再將sector的數(shù)據(jù)緩存到cache中，同時將dirty標志置1，表示當前sector_cache已被應用。如果當前block的sector_cache已被分配完，則申請一個新的 block_cache，將dirty標志置1，再從新的block_cache中分配sector_cache。

3)Cache塊的管理和數(shù)據(jù)回寫

block_cache有一個成員age用來表示它的年齡，當讀寫時，F(xiàn)TL首先將age等于0的sector_cache分配出來使用，每次從block_cache中分配一個sector_cache，block_cache的年齡加1，年齡最大的block_cache就是更新數(shù)據(jù)最多的block。如果當前所有的cache塊都被使用，F(xiàn)TL將年齡最大的block的數(shù)據(jù)回寫到 Flash中，清除 dirty和 age標志。再將block對應的cache釋放出來供新的sector緩存。

文件系統(tǒng)寫入的數(shù)據(jù)都緩存在cache中，而cache位于RAM中，系統(tǒng)掉電后cache的數(shù)據(jù)都會丟失，因此寫cache完成后必須按照一定的算法將cache的數(shù)據(jù)回寫到Flash中。因此文件系統(tǒng)開始寫入數(shù)據(jù)時，首先啟動一個周期為T的定時器，定時器溢出時如果cache中有需要回寫的數(shù)據(jù)，則將block_cache的數(shù)據(jù)寫入Flash，如果cache還有數(shù)據(jù)需要回寫，則再次啟動定時器，直到寫完為止。

定時器T控制著緩沖數(shù)據(jù)的回寫周期，如果T較小，緩沖區(qū)數(shù)據(jù)回寫較頻繁，可以降低系統(tǒng)意外掉電等原因造成的數(shù)據(jù)丟失的可能性，但存儲塊被擦除的次數(shù)增加，負載增大;如果T較大，F(xiàn)lash負載減小，數(shù)據(jù)丟失的可能性增大。通過多次實驗將T設置為5 s，系統(tǒng)的負載和穩(wěn)定性可以達到一個較好的效果。

3.4 效率分析

Nand Flash與SRAM的讀寫時間如表2所示，SRAM中的讀寫速度為ns級，比Flash讀寫速度快很多。

表2 Nand Flash的讀寫時間Tab.2 Time of operation in Nand Flash

如表3所示，F(xiàn)TL將Nand Flash的讀寫轉(zhuǎn)移到RAM上執(zhí)行。以讀寫一個1 MByte的文件，文件系統(tǒng)讀寫1 MByte的文件需要訪問32次FAT表。如果沒有采用緩沖機制，文件系統(tǒng)需要從Flash中讀32次FAT表，需要花800 μs;采用FTL時，只有3－6次讀FAT表需要從Flash中讀取，其余的直接從RAM中讀取，需要花費的時間為100～200 μs。

寫入1 MByte的文件時，文件系統(tǒng)會對FAT表更新32次;添加FTL緩沖功能后，只有當1個Block的 cache滿了，才會對 FAT表進行更新，寫入1 MByte的文件只會更新8次 FAT表，大大減少Flash的擦除次數(shù)。

表3 FTL效率分析Tab.3 Efficiency of FTL

4 負載/耗損均衡

4.1 耗損平衡概述

Nand Flash的每個塊擦除超過10萬次后就可能變成壞塊，因此擦除和寫入應盡可能地平均分配到整個Flash的所有塊中，從而提高整塊Flash的壽命，這就叫做負載平衡［2-5］。

在FAT文件系統(tǒng)中，如果每次為文件分配空間時，都按照FAT默認方式從前往后尋找空閑簇，那么處于前面的簇所在的塊將被頻繁的分配出去，處于后面的簇所在的區(qū)塊被分配次數(shù)很少。這就導致flash中前面的block擦除次數(shù)過多，后面的block擦除次數(shù)較少，導致了嚴重的負載不平衡。

為了提高Flash的壽命，必須修改FAT分配空閑簇的方法，不能使用FAT默認方法去尋找空閑簇。而是采用一種負載平衡的算法，讓每一個空閑簇有均等的機會被分配出去。這些空閑簇所在的塊也有均等的機會被擦除，從而使各個塊的壽命均等，有效的實現(xiàn)磨損平衡。

4.2 CRC負載平衡算法

循環(huán)冗余碼校驗算法(cyclical redundancy check，CRC)是一種在數(shù)據(jù)存儲和數(shù)據(jù)通訊領域廣泛使用的編碼算法，具有強力的檢錯和糾錯能力，開銷小。CRC算法不僅是一種高效的檢錯算法，也是一種高效的隨機數(shù)生成算法，對于一個輸入的n位二進制碼序列，根據(jù)CRC-CCITT生成多項式，產(chǎn)生一段16位的校驗碼。不同二進制序列生成同一個校驗碼的幾率為0.004 7%以下。

FTL的負載算法采用CRC-CCITT算法來生成隨機數(shù)。由2.1節(jié)可知，F(xiàn)lash中任何存儲塊狀態(tài)改變，邏輯塊和物理塊的映射表l2p_map［］同時也發(fā)生了變化，F(xiàn)TL使用l2p_map［］數(shù)組作為二進制序列，根據(jù)CRC-CCITT生成多項式求其校驗碼crc。按照式(6)所示的規(guī)則獲取一個隨機數(shù)random_num

當文件系統(tǒng)需要分配一個空間時，從第random_num個block處開始搜索空閑塊，使空閑塊有均等的機會被分配使用。

系統(tǒng)上電時，如果flash中存儲的內(nèi)容發(fā)生改變，隨機數(shù)random_num的值也發(fā)生了變化，文件系統(tǒng)從另一個塊開始搜索空閑簇，所有的空閑塊也會均等機會的被擦除，從而有效的實現(xiàn)了數(shù)據(jù)區(qū)各個塊的磨損平衡。

5 結(jié)束語

本文設計了一種基于緩沖機制的應用于FAT文件系統(tǒng)的FTL，提供了一種緩沖區(qū)機制和一種邏輯塊物理塊的映射機制，解決了Nand Flash必須先擦除后寫入、只能以塊為單位擦除的問題，提高系統(tǒng)的讀寫速度，減輕Flash的總體負載，提供CRC負載平衡算法改善Flash的負載平衡，延長Flash總體壽命。然而FTL的緩沖區(qū)占用了一定的RAM資源，數(shù)據(jù)寫入Flash的過程不是實時的，有5 s左右的緩沖時間。整個方案在ARM9和Nand Flash芯片H8BCS0上進行了驗證，測試證明，該FTL可以有效地管理Nand Flash，并能有效地進行壞塊處理和磨損平衡，應用于普通磁盤的FAT文件系統(tǒng)只需要做很小的修改就可以移植到Nand Flash上，下階段的工作有:1)優(yōu)化Flash的負載平衡;2)添加垃圾回收機制。

［1］TAE S，DONG P，SANGWON P.A survey of Flash Translation Layer［J］.Journal of Systems Architecture，2009，55(5):332-343.

［2］LEE Y G，DAWOON Jung，DONGWON Kang，et al.u-FTL:A Memory-Efficient Flash Translation Layer Supporting Multiple Mapping Granularities［C］//ACM.In Proceedings of EMSOFT'2008.New York:ACM New，2008:21-30.

［3］趙挺竹.基于Nand Flash的FAT16文件系統(tǒng)［J］.電子元器件應用，2009，11(9):92-95.ZHAO Ting-zhu.An FAT16 File System base Nand Flash［J］.The Application of the Electronic Components，2009，11(9):92-95.

［4］JESUNG K，JONG M，SAMAM H.A Space-Efficient Flash Translation Layer for Compact Flash［J］.IEEE Transactions on Consumer Electronics，2002，48(2):366-375.

［5］MUHAMMAD N，JAMSHID D.Software Based NAND Flash Management Techniques［C］//IEEE.Computing，Engineering and Information(ICC 2009).Washington，DC:IEEE Press，2009:168-171.

［6］KWON S，CHUNG T.An efficient and advanced spacemanagement technique for flash memory using reallocation blocks［J］.IEEE Transactions on Consumer Electronics，2008，54(2):631-638.

［7］KANG Jeong-Uk，HEESEUNG Jo，KIN Jin-Soo，et al.A superblock-based flash translation layer for nand flash memory［C］//ACM.In Proceedings of EMSOFT'2006.New York:ACM，2006:161-170.

［8］沈建華，羅悅懌.Flash文件系統(tǒng)的研究與設計［J］.計算機應用研究，2004，24(12):246-248.SHEN Jian-hua，LUO Yue-yi.Research and Algorithm of Flash File System［J］.Application Research of computers，2004，24(12):246-248.