匡 偉，呂霞付，陳 勇，鄭思遠(yuǎn)

(重慶郵電大學(xué)網(wǎng)絡(luò)化控制與智能儀器儀表教育部重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

0 引言

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

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

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

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

1 Nand Flash簡(jiǎn)介

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

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

其中page是Nand Flash的最小讀寫單位，block是 Nand Flash 的最小擦除單位［5，8］。每個(gè) 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存儲(chǔ)塊在其生命周期中保持性能的可靠，有可能出現(xiàn)壞塊，所以Nand Flash的每個(gè)page分為main和spare區(qū)，main區(qū)存儲(chǔ)數(shù)據(jù)信息，spare區(qū)保存壞塊信息和錯(cuò)誤檢查和糾正(error correcting code，ECC)信息等。Spare區(qū)存儲(chǔ)內(nèi)容的格式如圖2所示，BI是芯片出廠時(shí)的壞塊標(biāo)志，ECC存儲(chǔ)main區(qū)數(shù)據(jù)的ECC校驗(yàn)碼，Reserved為保留字節(jié)。

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

2 FTL設(shè)計(jì)

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

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

2.2 壞塊檢測(cè)與存儲(chǔ)塊管理

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

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

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

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

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

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

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

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

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

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

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

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

3 FTL緩沖機(jī)制設(shè)計(jì)

3.1 緩沖機(jī)制

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

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

3.2 緩沖區(qū)設(shè)計(jì)

FTL緩沖區(qū)(cache)針對(duì)sectors和pages而設(shè)計(jì)，邏輯扇區(qū)號(hào)與邏輯塊號(hào)的對(duì)應(yīng)關(guān)系如下

(2)，(3)式中:ps表示每個(gè)page的字節(jié)數(shù);ss表示每個(gè)sector的字節(jié)數(shù);spp表示每個(gè)page對(duì)應(yīng)的扇區(qū)數(shù);sn表示扇區(qū)號(hào);ppb表示每個(gè)block的page數(shù)。根據(jù)式(2)，(3)可得出如式(4)所示的邏輯sector與物理塊號(hào)的對(duì)應(yīng)關(guān)系，sector在當(dāng)前block的page偏移量如式(5)所示。其中l(wèi)bn表示邏輯塊號(hào);pbn表示邏輯塊對(duì)應(yīng)的物理塊號(hào);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個(gè)block大小的緩存區(qū)供FTL使用，每個(gè)cache塊的大小為512 Byte，與sector大小相同，將(ss×ppb)個(gè) cache塊用鏈表鏈接起來就可以緩存一個(gè)block大小的數(shù)據(jù)。block_cache結(jié)構(gòu)體中，block表示著當(dāng)前緩存物理塊的邏輯塊號(hào)，count表示當(dāng)前block中緩存的sector個(gè)數(shù)，dirty表示當(dāng)前緩存block是否已被使用，age表示緩存block的年齡。sector_cache中sect表示當(dāng)前緩存的sector號(hào)，dirty表示它是否被使用，next指向下一個(gè)sector，buffer是一個(gè)512 Byte的緩沖塊。

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

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

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

圖5 FTL cache設(shè)計(jì)Fig 5 FTL cache design

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

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

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

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

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

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

3.4 效率分析

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

表2 Nand Flash的讀寫時(shí)間Tab.2 Time of operation in Nand Flash

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

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

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

4 負(fù)載/耗損均衡

4.1 耗損平衡概述

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

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

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

4.2 CRC負(fù)載平衡算法

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

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

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

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

5 結(jié)束語

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

［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］.電子元器件應(yīng)用，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)的研究與設(shè)計(jì)［J］.計(jì)算機(jī)應(yīng)用研究，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.