一种基于虚拟页地址映射的NAND Flash管理算法*

许 娜，彭 飞，谭彦亮，苗志富，曹梦丹

0 引 言

随着航天电子技术的发展，航天器的功能和原理变得日益复杂，也需要性能更好的存储器.近年来，由于NAND Flash具有访问速度快、体积小、防震抗摔、非易失性，以及安全可靠等特征，使得其成为嵌入式系统的首选存储介质[1]，尤其是在航天领域.现有的磁盘存储技术不能直接运行在NAND Flash设备上.为了使得现有的磁盘存储技术能够应用于该设备，需要在NAND Flash存储系统中引入了存储转换层，实现对NAND Flash的管理.

本文提出一种基于虚拟映射的页级地址转换算法实现对NAND Flash的管理.通过合理使用SRAM资源以及减少映射信息的存储容量，通过构架一层虚拟层，实现采用虚拟地址对NAND Flash的访问和管理.本文首先对地址转换和坏块管理进行了分析，然后对提出的基于虚拟页地址映射的NAND Flash管理算法进行了详细描述，最后对该算法进行了总结和展望.

1 NAND Flash的主要特性

Flash存储器，简称闪存，是日本东芝公司于上世纪80年代末期发明的一种新型存储器，具有体积小、重量轻、低功耗、低噪音、集成度高、防震抗摔、访问速度快的长寿命非易失等特性.

NAND Flash和NOR Flash是两种主要的非易失闪存技术.NOR Flash的地址线和数据线是相互独立的，存取方式是以字节为单位，NOR Flash容量较小，成本很高，但由于其数据线和地址线是独立的，且存取以字节为单位，因而NOR Flash的读取速度较快，是随机读取速度，且具有特别高的可靠性.NOR Flash的这些特性使其适合用于经常随机性读写的地方，一般用于存储代码.NAND Flash的地址线和数据线是共用I/O线，读写是以页为单位进行操作，擦除则是以块为单位进行操作，所以NAND Flash的擦除写入速度也很快.NAND Flash的容量可以很大，其单位价格要远低于NOR Flash.因此，NAND Flash支持大容量数据存储.图1是一种典型的NAND Flash的逻辑单元结构.

图1 NAND Flash逻辑结构Fig.1 Nand Flash array organization

NAND Flash的组织存储结构在容量层级上从大到小依次为芯片(Flash Chip)、颗粒(Die)、平面(Plane)、块(Biock)、页(Page)，其中页是闪存的最小组织存储单位.一个页是由数据区和冗余区两部分组成.其中，数据区是用来存放所要存储的数据，冗余区则是用来记录映射逻辑信息和数据ECC校验码的元数据.

区别于传统设备以扇区(Sector)为单位进行读写擦，NAND Flash工作是以页为单位进行读写，以块为单位进行擦除.NAND Flash的最大特性就是不支持原地更新，当需要对一块数据进行更新时，需要将更新的数据写入到其他的空白地方，也就是所谓的异地更新.如果向已经存在数据的地方写入新的数据，需要先将这个地方所在的物理块先进行擦除，然后再进行写入需要写入的数据，可以把这个特性叫做“先擦除后写入”.

对于闪存的读操作，上层系统会发出读操作命令和所要读的数据所在的逻辑地址，闪存控制器将数据读取到页寄存器，然后选择读取上层系统所需要的数据到SRAM中，最后供上层系统来使用.对于写操作，其操作方式和读操作相反，上层系统会发出一个写命令，并且会带要写入的数据，通过闪存控制器，将数据经过一些ECC校验等物理操作写入到页寄存器中，最后写入到要写入的闪存设备上.当系统做擦除操作的时候，系统会发出相应的擦除命令和所要擦除的地址，当擦除执行成功后，原先所要擦除的块都会复位为1[2].

综上所述，NAND Flash的主要特性可以归结为4点：1) 需要先擦除再写入；2) 异地更新；3) 以页为单位读写，以块为单位擦除；4) 可擦写次数受到限制.

2 NAND Flash管理的相关工作

2.1 地址转换和映射机制

为了更好的对NAND Flash设备进行管理，提高其可靠性以及读写速度等性能，需要根据其特性，通过设计硬件管理层对设备进行管理，通过相应的算法设计软件管理层对存储器进行管理.

地址转换是NAND Flash管理策略中的一种基本操作.软件通过地址转换方法将上层逻辑地址转换成实际存储在闪存设备上的物理地址.这种转换需要映射表来管理.

映射机制根据映射信息颗粒的大小可以分为页级映射和块级映射[3].块级映射的特点是地址映射颗粒相对比较大，以块为映射单位，以逻辑块到物理块进行地址转换.当系统要读取一个逻辑页数的数据，为了确定请求的数据所在的具体物理页数，需要通过逻辑块号和块内页偏移以及块级映射转换表来确定数据所在的具体位置.对于块级地址映射，其地址映射表只保存逻辑块号到物理块号的地址映射.因为逻辑块和物理块的块内页偏移是一致的，所以偏移值不需要做额外的保存，通过计算就可以知道偏移的大小.对于块级地址映射，其优点是地址映射表的开销非常小，一般可以全部加载SRAM上，因此其读取速度相对也比较快.但其缺点也是因为其映射颗粒太大，造成系统的垃圾回收的高开销，空间不能得到充分的利用，因此其写性能会因为写前先擦除的问题被极大的降低[4].页级地址映射以页作为映射转换的基本单位，一个逻辑页可以与物理块上任何一个物理页形成映射，然后建立一一对应关系.这种地址映射相对于块级映射具有很强的灵活性，也使得系统块能够得到充分的利用，不会造成很大的垃圾回收开销，同时其映射算法也是最快的[5].但其缺点就是更加小颗粒的映射关系增加了地址映射表的容量开销，随着NAND Flash容量的不断变大，其本身在闪存中占用的空间开销也会变得很大，同时也需要很大的SRAM来加载页映射表，而有限的SRAM空间也将不能满足其不断增大的映射表所带来的需求[6].

2.2 坏块管理策略

坏块管理策略也是NAND Flash管理中不能缺少的一个组成部分.由于NAND Flash的工艺不能对NAND Flash存储队列在其生命周期中一直保持性能的可靠，因此在NAND Flash生产过程以及使用中都会有坏块的出现.因此，坏块可分为两类，一种是由于生产过程中产生的坏块，称为出厂坏块，也称为初始无效块，另一种则是在使用过程产生的坏块，可以称之为使用坏块.初始无效块被定义为包含一个或者更多的无效比特的块，这些比特的可靠性不被保证.包含初始无效块的信息被称为初始无效块信息.和所有块都为有效块的器件相比，包含了初始无效块的器件拥有相同的质量等级以及相同的AC和DC特性.初始无效块不会影响有效块的性能，因为这些坏块通过位线和共源线选择管隔离.系统设计必须能够通过地址映射将这些初始无效块进行标识.使用坏块是在芯片的生命周期内，随着NAND闪存的操作，会产生额外的无效块.NAND Flash的坏块管理策略需要对出现的这两种坏块进行有效管理.

NAND Flash管理中还包括坏块的替换策略.在使用过程中，为了使用户看到的存储设备都像正常可用的一样，系统需要对访问到的所有NAND Flash坏块进行替换，包括初始坏块和使用过程中产生的坏块.NAND Flash坏块管理方法可分为4类：1)基于FTL芯片的坏块管理，它使用一个额外的芯片对NAND Flash进行管理，对外屏蔽了坏块信息；2)基于NAND Flash文件系统的坏块管理，JFFS2、YAFFS2、FlashFx这些专门针对NAND Flash的文件系统可以对坏块进行管理；3)NAND Flash管理中间件，比如UBI；4)轻量级NAND Flash坏块管理.

为了实现高可靠性系统，坏块管理还需要针对NAND Flash的失效模式做出处理.在编程或者擦除后，如果状态位读出错误状态，必须进行块替换.由于在编程操作时，编程错误状态位不会影响同一个块中的其他页数据，需要通过基于页缓存的回拷贝操作将当前目标数据以及该块中的其他数据拷贝至一个全新的擦除块中.在读操作中，一定要采用ECC.为了提高存储空间的利用率，由于一个比特错误造成的读操作或者校验操作失效能够通过ECC 位进行纠正，而不需要任何块替换.额外的坏块率不包括这些纠正的块.比如前面说的当块被擦除到一定次数时就会成为坏块，对于使用过程中产生的坏块也需要通过坏块表对其做记录，以至于不会将数据写入到这些坏块中[6].

3 基于虚拟页地址映射的算法设计

本文设计了一种基于虚拟页地址映射的高效地址映射算法，具有坏块管理功能，能高效地对数据进行索引，使系统达到高性能和损耗均衡，使用更加稳定持久.本方法也可以看作是在NAND Flash上实现了一种简单的文件系统功能.

3.1 建立坏块表

一般来说，在出厂前，除了初始无效块信息区域外，全芯片其他区域都被置为擦除态(FFh).初始无效块状态被定义在额外区域的第一个字节.芯片确保每个初始无效块的第一个或者第二个页的列地址为页大小的区域为非FFh数据.由于初始块信息在大多数情况下同样能够被擦除，所以一旦被擦除后，初始块信息就不能恢复.坏块管理程序必须能够基于原始的初始无效块信息识别初始无效块，并且能够通过以下流程图建立初始无效块信息表.禁止任何对于初始无效块的擦除操作.由于NAND Flash有出厂坏块，所以在对NAND Flash进行擦除前要先将出厂坏块信息读出并保存，避免出厂坏块信息丢失.

为了提高对出厂坏块信息的存储效率，本算法采用在一个比特位对应存储一个块是否为坏块的信息，默认值为1，表示好块.如果该块为坏块，则将该比特位设置为0.当需要查询某一块是否为坏块，只需要对块号做简单的位移映射操作，就可以访问到坏块信息.

建立坏块表的算法如下.

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 建立对应表

本文提出的基于虚拟页地址映射的算法所采用的映射方法是一种包含页级映射和块级映射的混合映射.映射信息存储在NAND Flash中.当系统上电时，需要将映射表加载到SRAM中.对映射信息变化的处理方式是先在SRAM中修改映射关系，再将映射信息写回到NAND Flash中.

为了给上层应用软件提供一个可以连续访问的虚拟存储空间，并对上层应用软件屏蔽坏块信息.上层对NAND Flash的所有访问都采用虚拟页地址.假设：物理上的NAND Flash存储器包括CN个基片，每个基片有BN个块，每块有PN个页.该算法将每片的第0块作为保留块，用于存储初始化标志、坏块表和块对应表.NAND Flash生产厂商会保证第0块绝对不是坏块.

为了实现对坏块的替换，该算法将每片的第1块到第n块之间的块作为替换块区域(n由Nand Flash的坏块率确定)，用于作为应用软件访问块中坏块的替换块.因此，替换块区域的总块数为(n*CN).除保留块和替换块区域之外的块，都可以作为虚拟存储空间对应的实际物理空间，用于应用软件的访问，存储数据和代码信息.因此，可用的数据块数为((BN-n)*CN)，其有效使用率的计算公式为((BN-n)/BN)，记为Fapp.

3.3 管理信息初始化

在系统首次访问NAND Flash时，需要先读取坏块信息并存储到SRAM中；然后根据坏块信息建立出厂坏块和替换块之间的对应关系，即出现坏块则从替换块区中按顺序选择好块建立对应关系，生成对应表存储到SRAM中；最后，将坏块表和对应表回写入NAND Flash中，并设置完成标志到NAND Flash中.坏块表、对应表和完成标志都是存储在NAND Flash的保留块中，分页存储.NAND Flash的逻辑功能分区如图2所示.

图2 NAND Flash的逻辑功能分区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时，上层软件使用连续的虚拟页地址viPageAddr，范围是[0，((BN-n)*CN*PN)]，ramAddr是SRAM地址，mode是操作标志(0为读，1为写)，byteLength是读写的字节长度，默认为页大小.

从虚拟页地址到默认实际物理页地址的计算公式为：

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

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

其中：viPage-输入的虚拟页地址；cs-默认页地址所在的片号；B_START-每片中应用软件可用块的开始块号；clPage-默认实际页地址.

需要注意的是，在某些型号的NAND Flash芯片中，要求在一个块内，必须按照从块内的最低页地址连续编程至块内的最高页地址.随机的页地址编程是被禁止的.在这种情况下，最低页地址被定义为需要编程的页中的最低页，而不是页0.因此，本算法也保证了从以PN对齐的虚拟页地址开始的连续PN个虚拟页一定是从实际块内最低页地址到最高页地址的.

为了快速在对应表中找到坏块对应的替换块的块号，该算法将对应表定义为一个无符号的16位数组空间.数组元素大小为全部块数，下标为块号，元素的值为用于替换的块的块号(数组下标对应块为坏块)或是一个常量(数组下标对应块不为坏块).由于保留块位于每片的首块，而出厂规范保证每片的首块一定不是坏块，所以将保留块的首页用于存储标志，之后的页依次用于存储坏块表和对应表.其定义如下：

∥坏块表,bit: 1好块,0坏块

unsigned int

SYS_NF_BadBlockTable[(BN*CN)/32]

∥ 对应表, 对应的替换块号,默认0xffff

unsigned short SYS_NF_BlockMap[BN*CN]

在对应表中，应用软件使用块中，坏块块号下标的数据是好块的块号，其他为0xffff；替换块使用块中，好块用于替换后，其块号下标的数据为0，其他为0xffff.

图3是从虚拟页地址到实际页地址的计算流程.

图3 从虚拟页地址到实际页地址的计算流程Fig.3 Calculatation flow from virtual page address to real phyical page address

由于本算法通过公式计算来实现页地址的转换，不会占用SRAM空间，而且转换效率很高.如果在NAND Flash的使用过程中出现新的坏块，还需要及时对坏块表和对应表进行更新.更新对应表时，选择新的替换块的原则是从替换块区中选择离上个替换块最近的下一个地址的好块.并且需要将坏块中的之前的数据全部复制到用于替换的好块中，步骤如下：

① 检测到编程或者擦除操作时，在块A的第n个页出现了错误；

② 根据坏块替换原则，找到用于替换块A的好块B，更新对应表；

③ 将块A中第0至(n-1)页中的数据拷贝至块B的相同的页位置；

④ 将拷贝在控制器中的缓存区域内的块A的第n页数据拷贝至块B的第n页；

⑤ 将块A增加至坏块表，并且不对块A进行编程或者擦除.

3.5 测试验证

根据实际芯片手册中有效块的阙值[7]，结合NAND Flash 驻留错误率存在显著页耐受力差异的特征研究[8]，建立针对本文提出的NAND Flash管理算法的测试验证仿真环境.为了模拟出真实环境下算法的性能，输入文件采用Financial(F)和Websearch(WS)，这两种负载文件的工作负载特性如表1所示[9].

表1 负载文件的工作负载特性Tab.1 The load characteristics of the load files in work

通过对虚拟页地址到实际页地址的转换效率进行仿真，发现转换效率与NAND Flash的使用时长和应用软件对虚拟页地址存储空间的使用方式相关.由于应用软件对存储空间的使用特点影响着物理层对NAND Flash芯片的块擦除和写入的频率，随着NAND Flash使用时间的延长，转换效率会出现降低.但是，随着NAND Flash的剩余容量逐渐减小，存储系统的写性能也会有所下降，而NAND Flash的使用寿命随着块内好页的逐渐消耗而逐渐增加.随着后续块内坏页数的继续增加，坏块替换表逐渐完善，NAND Flash的虚拟页转换效率变化也趋于平缓.仿真结果中虚拟页地址的一次地址映射命中率如下所示.

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

如果因为某种外部故障导致系统没有及时将修改后的映射信息回写到NAND Flash中，则当再次上电时，会因为原先存储的映射表己经不可信，而需要构建出掉电前的信息映射表，实现掉电保护操作.如果不能构建出最新的映射信息表，就会面临数据丢失，这将影响到系统的可靠性.

4 结 论

本文提出一种基于虚拟页地址映射的NAND Flash管理算法，实现了上层软件采用虚拟地址对NAND Flash的无坏块连续页地址访问.该算法已作为一种简单文件管理系统应用于航天器上的NAND Flash访问.尽管本方法具有映射地址计算时间短，命中率高，占用内存空间少的特点，但是在本方法在系统损耗均衡等方面还有很大的改进空间，后续将继续探索和完善.