一種基于虛擬頁地址映射的NAND Flash管理算法*

許 娜，彭 飛，譚彥亮，苗志富，曹夢丹

0 引 言

隨著航天電子技術(shù)的發(fā)展，航天器的功能和原理變得日益復(fù)雜，也需要性能更好的存儲器.近年來，由于NAND Flash具有訪問速度快、體積小、防震抗摔、非易失性，以及安全可靠等特征，使得其成為嵌入式系統(tǒng)的首選存儲介質(zhì)[1]，尤其是在航天領(lǐng)域.現(xiàn)有的磁盤存儲技術(shù)不能直接運(yùn)行在NAND Flash設(shè)備上.為了使得現(xiàn)有的磁盤存儲技術(shù)能夠應(yīng)用于該設(shè)備，需要在NAND Flash存儲系統(tǒng)中引入了存儲轉(zhuǎn)換層，實(shí)現(xiàn)對NAND Flash的管理.

本文提出一種基于虛擬映射的頁級地址轉(zhuǎn)換算法實(shí)現(xiàn)對NAND Flash的管理.通過合理使用SRAM資源以及減少映射信息的存儲容量，通過構(gòu)架一層虛擬層，實(shí)現(xiàn)采用虛擬地址對NAND Flash的訪問和管理.本文首先對地址轉(zhuǎn)換和壞塊管理進(jìn)行了分析，然后對提出的基于虛擬頁地址映射的NAND Flash管理算法進(jìn)行了詳細(xì)描述，最后對該算法進(jìn)行了總結(jié)和展望.

1 NAND Flash的主要特性

Flash存儲器，簡稱閃存，是日本東芝公司于上世紀(jì)80年代末期發(fā)明的一種新型存儲器，具有體積小、重量輕、低功耗、低噪音、集成度高、防震抗摔、訪問速度快的長壽命非易失等特性.

NAND Flash和NOR Flash是兩種主要的非易失閃存技術(shù).NOR Flash的地址線和數(shù)據(jù)線是相互獨(dú)立的，存取方式是以字節(jié)為單位，NOR Flash容量較小，成本很高，但由于其數(shù)據(jù)線和地址線是獨(dú)立的，且存取以字節(jié)為單位，因而NOR Flash的讀取速度較快，是隨機(jī)讀取速度，且具有特別高的可靠性.NOR Flash的這些特性使其適合用于經(jīng)常隨機(jī)性讀寫的地方，一般用于存儲代碼.NAND Flash的地址線和數(shù)據(jù)線是共用I/O線，讀寫是以頁為單位進(jìn)行操作，擦除則是以塊為單位進(jìn)行操作，所以NAND Flash的擦除寫入速度也很快.NAND Flash的容量可以很大，其單位價(jià)格要遠(yuǎn)低于NOR Flash.因此，NAND Flash支持大容量數(shù)據(jù)存儲.圖1是一種典型的NAND Flash的邏輯單元結(jié)構(gòu).

圖1 NAND Flash邏輯結(jié)構(gòu)Fig.1 Nand Flash array organization

NAND Flash的組織存儲結(jié)構(gòu)在容量層級上從大到小依次為芯片(Flash Chip)、顆粒(Die)、平面(Plane)、塊(Biock)、頁(Page)，其中頁是閃存的最小組織存儲單位.一個(gè)頁是由數(shù)據(jù)區(qū)和冗余區(qū)兩部分組成.其中，數(shù)據(jù)區(qū)是用來存放所要存儲的數(shù)據(jù)，冗余區(qū)則是用來記錄映射邏輯信息和數(shù)據(jù)ECC校驗(yàn)碼的元數(shù)據(jù).

區(qū)別于傳統(tǒng)設(shè)備以扇區(qū)(Sector)為單位進(jìn)行讀寫擦，NAND Flash工作是以頁為單位進(jìn)行讀寫，以塊為單位進(jìn)行擦除.NAND Flash的最大特性就是不支持原地更新，當(dāng)需要對一塊數(shù)據(jù)進(jìn)行更新時(shí)，需要將更新的數(shù)據(jù)寫入到其他的空白地方，也就是所謂的異地更新.如果向已經(jīng)存在數(shù)據(jù)的地方寫入新的數(shù)據(jù)，需要先將這個(gè)地方所在的物理塊先進(jìn)行擦除，然后再進(jìn)行寫入需要寫入的數(shù)據(jù)，可以把這個(gè)特性叫做“先擦除后寫入”.

對于閃存的讀操作，上層系統(tǒng)會發(fā)出讀操作命令和所要讀的數(shù)據(jù)所在的邏輯地址，閃存控制器將數(shù)據(jù)讀取到頁寄存器，然后選擇讀取上層系統(tǒng)所需要的數(shù)據(jù)到SRAM中，最后供上層系統(tǒng)來使用.對于寫操作，其操作方式和讀操作相反，上層系統(tǒng)會發(fā)出一個(gè)寫命令，并且會帶要寫入的數(shù)據(jù)，通過閃存控制器，將數(shù)據(jù)經(jīng)過一些ECC校驗(yàn)等物理操作寫入到頁寄存器中，最后寫入到要寫入的閃存設(shè)備上.當(dāng)系統(tǒng)做擦除操作的時(shí)候，系統(tǒng)會發(fā)出相應(yīng)的擦除命令和所要擦除的地址，當(dāng)擦除執(zhí)行成功后，原先所要擦除的塊都會復(fù)位為1[2].

綜上所述，NAND Flash的主要特性可以歸結(jié)為4點(diǎn)：1) 需要先擦除再寫入；2) 異地更新；3) 以頁為單位讀寫，以塊為單位擦除；4) 可擦寫次數(shù)受到限制.

2 NAND Flash管理的相關(guān)工作

2.1 地址轉(zhuǎn)換和映射機(jī)制

為了更好的對NAND Flash設(shè)備進(jìn)行管理，提高其可靠性以及讀寫速度等性能，需要根據(jù)其特性，通過設(shè)計(jì)硬件管理層對設(shè)備進(jìn)行管理，通過相應(yīng)的算法設(shè)計(jì)軟件管理層對存儲器進(jìn)行管理.

地址轉(zhuǎn)換是NAND Flash管理策略中的一種基本操作.軟件通過地址轉(zhuǎn)換方法將上層邏輯地址轉(zhuǎn)換成實(shí)際存儲在閃存設(shè)備上的物理地址.這種轉(zhuǎn)換需要映射表來管理.

映射機(jī)制根據(jù)映射信息顆粒的大小可以分為頁級映射和塊級映射[3].塊級映射的特點(diǎn)是地址映射顆粒相對比較大，以塊為映射單位，以邏輯塊到物理塊進(jìn)行地址轉(zhuǎn)換.當(dāng)系統(tǒng)要讀取一個(gè)邏輯頁數(shù)的數(shù)據(jù)，為了確定請求的數(shù)據(jù)所在的具體物理頁數(shù)，需要通過邏輯塊號和塊內(nèi)頁偏移以及塊級映射轉(zhuǎn)換表來確定數(shù)據(jù)所在的具體位置.對于塊級地址映射，其地址映射表只保存邏輯塊號到物理塊號的地址映射.因?yàn)檫壿媺K和物理塊的塊內(nèi)頁偏移是一致的，所以偏移值不需要做額外的保存，通過計(jì)算就可以知道偏移的大小.對于塊級地址映射，其優(yōu)點(diǎn)是地址映射表的開銷非常小，一般可以全部加載SRAM上，因此其讀取速度相對也比較快.但其缺點(diǎn)也是因?yàn)槠溆成漕w粒太大，造成系統(tǒng)的垃圾回收的高開銷，空間不能得到充分的利用，因此其寫性能會因?yàn)閷懬跋炔脸膯栴}被極大的降低[4].頁級地址映射以頁作為映射轉(zhuǎn)換的基本單位，一個(gè)邏輯頁可以與物理塊上任何一個(gè)物理頁形成映射，然后建立一一對應(yīng)關(guān)系.這種地址映射相對于塊級映射具有很強(qiáng)的靈活性，也使得系統(tǒng)塊能夠得到充分的利用，不會造成很大的垃圾回收開銷，同時(shí)其映射算法也是最快的[5].但其缺點(diǎn)就是更加小顆粒的映射關(guān)系增加了地址映射表的容量開銷，隨著NAND Flash容量的不斷變大，其本身在閃存中占用的空間開銷也會變得很大，同時(shí)也需要很大的SRAM來加載頁映射表，而有限的SRAM空間也將不能滿足其不斷增大的映射表所帶來的需求[6].

2.2 壞塊管理策略

壞塊管理策略也是NAND Flash管理中不能缺少的一個(gè)組成部分.由于NAND Flash的工藝不能對NAND Flash存儲隊(duì)列在其生命周期中一直保持性能的可靠，因此在NAND Flash生產(chǎn)過程以及使用中都會有壞塊的出現(xiàn).因此，壞塊可分為兩類，一種是由于生產(chǎn)過程中產(chǎn)生的壞塊，稱為出廠壞塊，也稱為初始無效塊，另一種則是在使用過程產(chǎn)生的壞塊，可以稱之為使用壞塊.初始無效塊被定義為包含一個(gè)或者更多的無效比特的塊，這些比特的可靠性不被保證.包含初始無效塊的信息被稱為初始無效塊信息.和所有塊都為有效塊的器件相比，包含了初始無效塊的器件擁有相同的質(zhì)量等級以及相同的AC和DC特性.初始無效塊不會影響有效塊的性能，因?yàn)檫@些壞塊通過位線和共源線選擇管隔離.系統(tǒng)設(shè)計(jì)必須能夠通過地址映射將這些初始無效塊進(jìn)行標(biāo)識.使用壞塊是在芯片的生命周期內(nèi)，隨著NAND閃存的操作，會產(chǎn)生額外的無效塊.NAND Flash的壞塊管理策略需要對出現(xiàn)的這兩種壞塊進(jìn)行有效管理.

NAND Flash管理中還包括壞塊的替換策略.在使用過程中，為了使用戶看到的存儲設(shè)備都像正?？捎玫囊粯樱到y(tǒng)需要對訪問到的所有NAND Flash壞塊進(jìn)行替換，包括初始壞塊和使用過程中產(chǎn)生的壞塊.NAND Flash壞塊管理方法可分為4類：1)基于FTL芯片的壞塊管理，它使用一個(gè)額外的芯片對NAND Flash進(jìn)行管理，對外屏蔽了壞塊信息；2)基于NAND Flash文件系統(tǒng)的壞塊管理，JFFS2、YAFFS2、FlashFx這些專門針對NAND Flash的文件系統(tǒng)可以對壞塊進(jìn)行管理；3)NAND Flash管理中間件，比如UBI；4)輕量級NAND Flash壞塊管理.

為了實(shí)現(xiàn)高可靠性系統(tǒng)，壞塊管理還需要針對NAND Flash的失效模式做出處理.在編程或者擦除后，如果狀態(tài)位讀出錯(cuò)誤狀態(tài)，必須進(jìn)行塊替換.由于在編程操作時(shí)，編程錯(cuò)誤狀態(tài)位不會影響同一個(gè)塊中的其他頁數(shù)據(jù)，需要通過基于頁緩存的回拷貝操作將當(dāng)前目標(biāo)數(shù)據(jù)以及該塊中的其他數(shù)據(jù)拷貝至一個(gè)全新的擦除塊中.在讀操作中，一定要采用ECC.為了提高存儲空間的利用率，由于一個(gè)比特錯(cuò)誤造成的讀操作或者校驗(yàn)操作失效能夠通過ECC 位進(jìn)行糾正，而不需要任何塊替換.額外的壞塊率不包括這些糾正的塊.比如前面說的當(dāng)塊被擦除到一定次數(shù)時(shí)就會成為壞塊，對于使用過程中產(chǎn)生的壞塊也需要通過壞塊表對其做記錄，以至于不會將數(shù)據(jù)寫入到這些壞塊中[6].

3 基于虛擬頁地址映射的算法設(shè)計(jì)

本文設(shè)計(jì)了一種基于虛擬頁地址映射的高效地址映射算法，具有壞塊管理功能，能高效地對數(shù)據(jù)進(jìn)行索引，使系統(tǒng)達(dá)到高性能和損耗均衡，使用更加穩(wěn)定持久.本方法也可以看作是在NAND Flash上實(shí)現(xiàn)了一種簡單的文件系統(tǒng)功能.

3.1 建立壞塊表

一般來說，在出廠前，除了初始無效塊信息區(qū)域外，全芯片其他區(qū)域都被置為擦除態(tài)(FFh).初始無效塊狀態(tài)被定義在額外區(qū)域的第一個(gè)字節(jié).芯片確保每個(gè)初始無效塊的第一個(gè)或者第二個(gè)頁的列地址為頁大小的區(qū)域?yàn)榉荈Fh數(shù)據(jù).由于初始塊信息在大多數(shù)情況下同樣能夠被擦除，所以一旦被擦除后，初始塊信息就不能恢復(fù).壞塊管理程序必須能夠基于原始的初始無效塊信息識別初始無效塊，并且能夠通過以下流程圖建立初始無效塊信息表.禁止任何對于初始無效塊的擦除操作.由于NAND Flash有出廠壞塊，所以在對NAND Flash進(jìn)行擦除前要先將出廠壞塊信息讀出并保存，避免出廠壞塊信息丟失.

為了提高對出廠壞塊信息的存儲效率，本算法采用在一個(gè)比特位對應(yīng)存儲一個(gè)塊是否為壞塊的信息，默認(rèn)值為1，表示好塊.如果該塊為壞塊，則將該比特位設(shè)置為0.當(dāng)需要查詢某一塊是否為壞塊，只需要對塊號做簡單的位移映射操作，就可以訪問到壞塊信息.

建立壞塊表的算法如下.

Create-BadBlock-Table(table,blocksize)

1boack-address= 0

2IFthe-first-column[pagesize] <> 0xFF

OR

the-second-column[pagesize] <> 0xFF

3THEN

4Set-BadBlock-Flag-in-Sram(table,boack-address)

5IFblock-address

6THEN

7boack-address=boack-address+1

8GOTO2

9ELSE

10Copy-BadBlock-Table-to-Flash(table)

3.2 建立對應(yīng)表

本文提出的基于虛擬頁地址映射的算法所采用的映射方法是一種包含頁級映射和塊級映射的混合映射.映射信息存儲在NAND Flash中.當(dāng)系統(tǒng)上電時(shí)，需要將映射表加載到SRAM中.對映射信息變化的處理方式是先在SRAM中修改映射關(guān)系，再將映射信息寫回到NAND Flash中.

為了給上層應(yīng)用軟件提供一個(gè)可以連續(xù)訪問的虛擬存儲空間，并對上層應(yīng)用軟件屏蔽壞塊信息.上層對NAND Flash的所有訪問都采用虛擬頁地址.假設(shè)：物理上的NAND Flash存儲器包括CN個(gè)基片，每個(gè)基片有BN個(gè)塊，每塊有PN個(gè)頁.該算法將每片的第0塊作為保留塊，用于存儲初始化標(biāo)志、壞塊表和塊對應(yīng)表.NAND Flash生產(chǎn)廠商會保證第0塊絕對不是壞塊.

為了實(shí)現(xiàn)對壞塊的替換，該算法將每片的第1塊到第n塊之間的塊作為替換塊區(qū)域(n由Nand Flash的壞塊率確定)，用于作為應(yīng)用軟件訪問塊中壞塊的替換塊.因此，替換塊區(qū)域的總塊數(shù)為(n*CN).除保留塊和替換塊區(qū)域之外的塊，都可以作為虛擬存儲空間對應(yīng)的實(shí)際物理空間，用于應(yīng)用軟件的訪問，存儲數(shù)據(jù)和代碼信息.因此，可用的數(shù)據(jù)塊數(shù)為((BN-n)*CN)，其有效使用率的計(jì)算公式為((BN-n)/BN)，記為Fapp.

3.3 管理信息初始化

在系統(tǒng)首次訪問NAND Flash時(shí)，需要先讀取壞塊信息并存儲到SRAM中；然后根據(jù)壞塊信息建立出廠壞塊和替換塊之間的對應(yīng)關(guān)系，即出現(xiàn)壞塊則從替換塊區(qū)中按順序選擇好塊建立對應(yīng)關(guān)系，生成對應(yīng)表存儲到SRAM中；最后，將壞塊表和對應(yīng)表回寫入NAND Flash中，并設(shè)置完成標(biāo)志到NAND Flash中.壞塊表、對應(yīng)表和完成標(biāo)志都是存儲在NAND Flash的保留塊中，分頁存儲.NAND Flash的邏輯功能分區(qū)如圖2所示.

圖2 NAND Flash的邏輯功能分區(qū)Fig.2 NAND Flash logic function area

1.6 地址映射流程

上層軟件對NAND Flash的訪問只有頁讀和頁寫兩種.該算法提供給上層軟件的接口如下：

unsigned int

SYS_NandFlash_Page_Operation(

unsigned intviPageAddr,

unsigned intramAddr,

unsigned intmode,

unsigned intbyteLength)

在讀寫NAND Flash時(shí)，上層軟件使用連續(xù)的虛擬頁地址viPageAddr，范圍是[0，((BN-n)*CN*PN)]，ramAddr是SRAM地址，mode是操作標(biāo)志(0為讀，1為寫)，byteLength是讀寫的字節(jié)長度，默認(rèn)為頁大小.

從虛擬頁地址到默認(rèn)實(shí)際物理頁地址的計(jì)算公式為：

cs=viPage/((BN-B_START)*PN)

clPage=viPage+((cs+1)*B_START*PN)

其中：viPage-輸入的虛擬頁地址；cs-默認(rèn)頁地址所在的片號；B_START-每片中應(yīng)用軟件可用塊的開始塊號；clPage-默認(rèn)實(shí)際頁地址.

需要注意的是，在某些型號的NAND Flash芯片中，要求在一個(gè)塊內(nèi)，必須按照從塊內(nèi)的最低頁地址連續(xù)編程至塊內(nèi)的最高頁地址.隨機(jī)的頁地址編程是被禁止的.在這種情況下，最低頁地址被定義為需要編程的頁中的最低頁，而不是頁0.因此，本算法也保證了從以PN對齊的虛擬頁地址開始的連續(xù)PN個(gè)虛擬頁一定是從實(shí)際塊內(nèi)最低頁地址到最高頁地址的.

為了快速在對應(yīng)表中找到壞塊對應(yīng)的替換塊的塊號，該算法將對應(yīng)表定義為一個(gè)無符號的16位數(shù)組空間.數(shù)組元素大小為全部塊數(shù)，下標(biāo)為塊號，元素的值為用于替換的塊的塊號(數(shù)組下標(biāo)對應(yīng)塊為壞塊)或是一個(gè)常量(數(shù)組下標(biāo)對應(yīng)塊不為壞塊).由于保留塊位于每片的首塊，而出廠規(guī)范保證每片的首塊一定不是壞塊，所以將保留塊的首頁用于存儲標(biāo)志，之后的頁依次用于存儲壞塊表和對應(yīng)表.其定義如下：

∥壞塊表,bit: 1好塊,0壞塊

unsigned int

SYS_NF_BadBlockTable[(BN*CN)/32]

∥ 對應(yīng)表, 對應(yīng)的替換塊號,默認(rèn)0xffff

unsigned short SYS_NF_BlockMap[BN*CN]

在對應(yīng)表中，應(yīng)用軟件使用塊中，壞塊塊號下標(biāo)的數(shù)據(jù)是好塊的塊號，其他為0xffff；替換塊使用塊中，好塊用于替換后，其塊號下標(biāo)的數(shù)據(jù)為0，其他為0xffff.

圖3是從虛擬頁地址到實(shí)際頁地址的計(jì)算流程.

圖3 從虛擬頁地址到實(shí)際頁地址的計(jì)算流程Fig.3 Calculatation flow from virtual page address to real phyical page address

由于本算法通過公式計(jì)算來實(shí)現(xiàn)頁地址的轉(zhuǎn)換，不會占用SRAM空間，而且轉(zhuǎn)換效率很高.如果在NAND Flash的使用過程中出現(xiàn)新的壞塊，還需要及時(shí)對壞塊表和對應(yīng)表進(jìn)行更新.更新對應(yīng)表時(shí)，選擇新的替換塊的原則是從替換塊區(qū)中選擇離上個(gè)替換塊最近的下一個(gè)地址的好塊.并且需要將壞塊中的之前的數(shù)據(jù)全部復(fù)制到用于替換的好塊中，步驟如下：

① 檢測到編程或者擦除操作時(shí)，在塊A的第n個(gè)頁出現(xiàn)了錯(cuò)誤；

② 根據(jù)壞塊替換原則，找到用于替換塊A的好塊B，更新對應(yīng)表；

③ 將塊A中第0至(n-1)頁中的數(shù)據(jù)拷貝至塊B的相同的頁位置；

④ 將拷貝在控制器中的緩存區(qū)域內(nèi)的塊A的第n頁數(shù)據(jù)拷貝至塊B的第n頁；

⑤ 將塊A增加至壞塊表，并且不對塊A進(jìn)行編程或者擦除.

3.5 測試驗(yàn)證

根據(jù)實(shí)際芯片手冊中有效塊的闕值[7]，結(jié)合NAND Flash 駐留錯(cuò)誤率存在顯著頁耐受力差異的特征研究[8]，建立針對本文提出的NAND Flash管理算法的測試驗(yàn)證仿真環(huán)境.為了模擬出真實(shí)環(huán)境下算法的性能，輸入文件采用Financial(F)和Websearch(WS)，這兩種負(fù)載文件的工作負(fù)載特性如表1所示[9].

表1 負(fù)載文件的工作負(fù)載特性Tab.1 The load characteristics of the load files in work

通過對虛擬頁地址到實(shí)際頁地址的轉(zhuǎn)換效率進(jìn)行仿真，發(fā)現(xiàn)轉(zhuǎn)換效率與NAND Flash的使用時(shí)長和應(yīng)用軟件對虛擬頁地址存儲空間的使用方式相關(guān).由于應(yīng)用軟件對存儲空間的使用特點(diǎn)影響著物理層對NAND Flash芯片的塊擦除和寫入的頻率，隨著NAND Flash使用時(shí)間的延長，轉(zhuǎn)換效率會出現(xiàn)降低.但是，隨著NAND Flash的剩余容量逐漸減小，存儲系統(tǒng)的寫性能也會有所下降，而NAND Flash的使用壽命隨著塊內(nèi)好頁的逐漸消耗而逐漸增加.隨著后續(xù)塊內(nèi)壞頁數(shù)的繼續(xù)增加，壞塊替換表逐漸完善，NAND Flash的虛擬頁轉(zhuǎn)換效率變化也趨于平緩.仿真結(jié)果中虛擬頁地址的一次地址映射命中率如下所示.

表2 虛擬頁地址一次地址映射的命中率Tab.2 First hit-rate of virtual page addressmapping to physical address

如果因?yàn)槟撤N外部故障導(dǎo)致系統(tǒng)沒有及時(shí)將修改后的映射信息回寫到NAND Flash中，則當(dāng)再次上電時(shí)，會因?yàn)樵却鎯Φ挠成浔砑航?jīng)不可信，而需要構(gòu)建出掉電前的信息映射表，實(shí)現(xiàn)掉電保護(hù)操作.如果不能構(gòu)建出最新的映射信息表，就會面臨數(shù)據(jù)丟失，這將影響到系統(tǒng)的可靠性.

4 結(jié) 論

本文提出一種基于虛擬頁地址映射的NAND Flash管理算法，實(shí)現(xiàn)了上層軟件采用虛擬地址對NAND Flash的無壞塊連續(xù)頁地址訪問.該算法已作為一種簡單文件管理系統(tǒng)應(yīng)用于航天器上的NAND Flash訪問.盡管本方法具有映射地址計(jì)算時(shí)間短，命中率高，占用內(nèi)存空間少的特點(diǎn)，但是在本方法在系統(tǒng)損耗均衡等方面還有很大的改進(jìn)空間，后續(xù)將繼續(xù)探索和完善.