5142010,31(3)计算机工程与设计ComputerEngineeringandDesign
嵌入式系统工程
0引言
嵌入式系统主要由微处理器、存储设备、总线标准、I/O外设等几大部分构成。随着制造工艺的成熟和体系结构的不断优化，如今无论面向低端应用还是高端应用，从8位到位，都有很大的选择范围，能够很好的完成复杂的数据信息处理。现在需要的更多的是如何有效的存储和管理越来越多的数据，随着对大容量存储需求的日益迫切，NANDFlash因为其自身的特点成为了嵌入式设备，特别是消费类手持嵌入式设备的最主要存储解决方案。目前针对NANDFlash的研究主要集中在硬件和软件两大块，硬件方面的研究主要希望尽一步加大存储容量，提高读写速度及数据可靠性，降低制造成本，统一各厂家的标准等；软件方面的研究主要集中在如何实现一个更优秀NANDFlash的驱动程序。NANDFlash的驱动程序中牵涉到很多问题，比如如何更好的进行垃圾收集，负载均衡，坏块管理等等。本文主要介绍我们的NANDFlash存储系统的驱动程序设计，主要是基于Linux操作系统。
1NANDFlash存储系统的总体设计
NANDFlash存储系统的分层结构如图1所示。它由用户
层、内核层与硬件层组成：用户层就是直接与用户联系，实际
收稿日期：2009-05-08；修订日期：2009-08-05。
对存储器提出读写请求的应用程序，比如cp、rm等命令，比如对存储器有读写请求的应用程序；内核层主要包括文件系统，比如EXT3、EXT2、FAT32等文件系统，由于我们在接下来的块设备层中实现了闪存翻译层(FTL)，所以文件系统可以采用任何通用的文件系统，而不需要采用特殊的针对NANDFlash的文件系统，比如JFFS2等，块设备驱动层，主要实现统一的Linux块设备驱动，主要完成块设备注册、定义块设备操作、请求处理等工作，NANDFlash设备驱动层，在这里NANDFlash设备驱动又分为FTL(flashtranslationlayer)层与LLD(lowleveldriver)层，由于NANDFlash是一个特殊的存储设备，具有自身的特点，不同于一般的块设备，所以需要FTL层来进行一个转换和翻译的功能，使得上层可以像对一般块设备进行操作那样来对NANDFlash进行操作，使得NANDFlash的特殊性对于FTL层以上是透明的不可见的，LLD层主要用来直接驱动控制器来完成底层的具体操作，例如最基本的页读、页写、块擦除等操作；硬件层由NANDFlash控制器和具体的NANDFlash芯片构成。
2块设备驱动层
一个块设备驱动主要通过传输固定大小的随机数据来访
问设备。在块设备的I/O子系统中，读和写操作是由request函
秦晓康，徐惠民：嵌入式设备NANDFlash存储系统的设计与实现2010,31(3)515
数处理的。每个设备都有一个请求队列，这是因为对磁盘数据实际的传入和传出发生的时间，与内核请求的时间相差很大，因此内核需要有一定的灵活性，以安排在适当时刻(比如
把影响相邻磁盘扇区的请求分成一组)调用驱动来进行传输。块设备驱动层的结构如图2所示。
每个块设备驱动程序的核心是它的请求函数。实际的工作，都是在这个函数里完成的。但是这个有个很大的弊端，就是如果响应速度较慢的话，特别是没有采用DMA，会长期占用CPU，如果使用了互斥锁，可能会因为锁超时而产生BUG，所以我们的设计采用一种目前较为流行的解决办法，Linux中MTD设备驱动正是采用了这种方法。就是当内核产生对NANDFlash的读写请求，请求函数Request获得这个请求，然后启用传输进程来响应请求。
在处理请求的时候我们采用一个进程来处理，当我们的设备不采用DMA，每个传输请求都需要通过中断占用处理器，有可能占用很长时间，采用这样一个进程的方式可以防止占用时间过长。
3FTL层
由于NANDFlash具有按页写，按块擦除，单块擦除次数有限，一般为百万次，比特反转现象较为频繁等特点，不能像操作其它块设备一样对NANDFlash进行操作，所以就需要
FTL层进行转换，使得对于FTL层以上看来，NANDFlash就是一个普通的块设备。FTL层主要完成的功能是地址映射、缓存、坏块管理、负载均衡、垃圾收集、ECC纠错。
一般的磁盘存储器写操作和擦除操作是等价的，但是由于NANDFlash是按页写，按块擦除，一个已用块在写之前必须擦除，所以NANDFlash的写操作比较特殊，必须擦后写，但擦除操作占用大量的时间，如果每次更新都是擦了再写，肯定会大大降低性能，故通常都采用如下的策略，如果一个写操作的地址上有旧的内容，那么驱动会自己找一个干净的块去完成这次写操作，而将原来的块标记为脏块，并改变地址映射关系，将逻辑地址由对应原来的脏块物理地址改为对应现在的新块地址，在恰当的时候调用垃圾收集来擦除掉脏块。
这就引入了地址映射的概念，地址映射就是将上层操作的逻辑地址映射为实际NANDFlash中的物理地址。地址映射可以分为页映射、块映射、混合映射3种。
页映射就是映射每一页，每个物理页都对应一个逻辑页
地址，好处是可以方便的对每个物理页进行操作，弊端是随着NANDFlash容量的不断扩大，总的页数的增加，存储这样一个页映射表需要占用大量的资源，包括内存和NANDFlash。
块映射就是映射每一块，每个物理块对应一个逻辑块地址，页地址由块地址和偏移量构成，同一页在逻辑块和在物理块中具有相同的偏移量。这样一个只存储块地址映射的映射表的体积比页映射要小的多，不过会增加NANDFlash物理块的擦写次数，因为对页的更新会造成对整个块的更新擦写。随着随机写、页更新的频繁发生，NAND的擦写次数会急剧增加，性能也会下降的比较明显。
混合映射就是基本遵从块映射的规则，对部分块进行页映射，当写回发生时，只是先更新需要更新的页，而不是整块更新，就避免了整块更新带来的擦写次数的增加。
但是混合映射设计十分困难需要根据不同的应用来具体分析设计，增大了算法的复杂度，而且随机写和频繁更新在我们设备的主要应用场景中并不经常发生，故这里还是采用了块映射的策略。一个典型的块地址映射表如图3所示。
一个请求要操作的块逻辑地址是10，到地址映射表中找到块逻辑地址对应的是块物理地址8，所以这个操作实际的对象是块物理地址8。逻辑地址10的块中的各页的偏移量和物理地址8中的各页的偏移量是相同的。
每次地址映射关系的改变都必须更新地址映射表，并且要将地址映射表写回到NANDFlash中，并在页空闲区做上标
5162010,31(3)计算机工程与设计ComputerEngineeringandDesign
记表明这个块中的内容是地址映射表。由于可能的突然断电和非正常关机现象的发生，但对NANDFlash进行操作前，必须将地址映射表读入内存中才可能进行下一步的操作，所以必须可以保证驱动初始化的时候可以找到最新的那张地址映射表。我们采取将地址映射表编号的方式，每次初始化遍历所有的物理块，找到编号最新的地址映射表。
但如果每次NANDFlash初始化都需要挨个物理块去寻找最后保存的那张地址映射表，而遍历所有的物理块，大大增加了初始化的时间。为了缩小初始化的时间，我们将一固定物理块用来存放正常卸载NANDFlash模块前最后的地址映射表，并做上标记，表明是正常卸载这个块中存放的是最新的地址映射表。这样在初始化中只需要先读这个物理块看是否正确标记，如果是则叫地址映射表读入内存完成初始化，如果不是代表非正常卸载，则继续挨个物理块去寻找最新的地址映射表。这样在正常卸载模块的情况下，大大缩短了初始化的时间。
为了减少对物理块的频繁读写并且加快读写速度，我们采用缓存，我们在内存中申请数块大小的空间来作为缓存。实际驱动中，任一读写操作其实都是对缓存的操作，当要读写的物理块在缓存中时，直接对缓存进行操作，当要读写的物理块不在缓存中时，将现有缓存中的块写回对应的物理块中，再将请求的块读入缓存进行操作。按块缓存是最方便也是最容易实现的一种缓存方式，也是我们这次设计中采用的方法。但是随着NANDFlash单块存储容量的增加，势必会增加因为使用缓存而带来的内存开销，所以我们还可以考虑只缓存固定页数的内容，而不是按块缓存。
由于NANDFlash的固有原因，坏块不可避免，所以我们的驱动必须具有坏块管理功能，坏块分为出厂坏块和使用中产生的坏块，NANDFlash出厂时都会由生产厂商标记出出厂坏块，驱动的设计中在初始化的过程中会读对应的标记位，如果是坏块就会记录下来，以后的使用中不再使用这个坏块；当我们在操作过程中，对一个块的操作出现3次失败，我们就认为这个块坏了，这就是使用中坏块，将这个块标记为坏块，并从预留的块中找一块来替换它，预留块是事先预留用来进行坏块替换的块，预留的块不直接参加读写，仅用来进行负载均衡，所以预留块的大小不算在整个NANDFlash可以使用的存储空间中，这样设计的原因是避免了因为坏块而造成的存储容量的不断减小，对于用户更容易接受，预留块的多少可以在驱动中根据需求来调整。
因为NANDFlash单块擦写次数有限，我们应当尽量避免对部分块的频繁擦写，导致超过擦写寿命，成为坏块。就必须采用负载均衡算法，使各块的擦写次数基本一致，相差不大。负载均衡算法主要分两大类，一类是动态负载均衡，即每次挑最小擦写次数的可用块来写；一类是静态负载均衡，即交换最多擦写次数的块与最少擦写次数块上的内容。因此，我们必须保存每块的擦写次数用来进行负载均衡。静态负载均衡机制如图4所示。
在我们的驱动中，采用8bit的数来保存单块擦写次数，因此这个擦写次数最多只能是255，所以这里我们采用相对值，当一个块的擦写次数达到254次时，所有块的擦写次数分别减去最小擦写次数。采用相对值既反应出各块擦写次数的差异，同时又最大限度节省了用来保存各块擦写次数的开销。当
开始
求相对值
擦除请求
>Gate
=254
静态负载均衡
结束图4静态负载均衡流程
最大擦写次数减去最小擦写次数超过我们定义的一个阈值的时候，我们就进行静态负载均衡，将具有最大擦写次数块中的内容与最小擦写次数块中的内容互换，以达到负载均衡的目的。
垃圾收集就是对标记为脏块的块进行擦除，使之成为一个新的可用的块。在恰当的时候进行垃圾收集也是影响驱动性能的重要因素，这次设计中采取两个阈值来判断是否进行垃圾收集，一个阈值是现有脏块的数量，如果超过一个固定阈值，则进行垃圾收集；另一个阈值是现存空闲块的数量，如果可以使用的空闲块的数量低于一个限定的阈值，说明可用块不足，也进行垃圾收集，来擦除脏块释放成可用块。
ECC纠错则是采用ECC算法来尽量避免比特反转带来的不利影响。这次设计中采用的是硬件进行ECC纠错，如果检测到有错误，NAND控制器会产生中断，通知驱动有错误，并自动进行纠错，如果超出纠错范围则报告错误无法纠正。
4LLD层
LLD层负责联系FTL层与顶层硬件层，它提供最基本的操作，例如：块擦除、页写、页读。
不同的LLD层支持不同的NAND控制器，为了提供一种标准的接口，采用了如图5所示的结构。
LLD.C向上提供统一的接口，下面由不同的驱动程序来实现各自的功能，LLD_NAND.C实现NAND驱动，LLD_EMU.C实现利用内存来模拟NAND设备的驱动，用内存模拟NAND对于测试负载均衡算法有十分重要的意义，图6就是利用内存模拟得出的结果所绘制的。
5结果与分析
经过大量的实际读写和压力测试，在块设备驱动层所采
用的利用进程响应读写请求的设计几乎避免了所有因为不采用DMA而带来的读写占用互斥锁过长产生的内核BUG。在
秦晓康，徐惠民：嵌入式设备NANDFlash存储系统的设计与实现
2010,31(3)517
正常关闭系统再次启动的情况下，由于使用了上文中提及采用的从固定地址读取地址映射表的方法大大提高了启动速度，系统启动过程中几乎不会在存储系统初始化这里等待，相反如果不采用这种方法，可以明显观察到在系统启动过程中在初始化存储系统这步发生等待，等待时间可能随着NANDFlash的进一步使用而提高，我们的方法在保证正常关闭系统的情况下，大大提高了启动的速度。为了测试负载均衡算法，将100MB的文件反复擦写3万次，统计各块的擦写次数，结果如图6所示。从图6中可以得出我们的负载均衡算法是十分有效的。
6结束语
通过测试，所设计的NAND存储系统数据读写速率在2MB/s
左右，拥有较好的负载均衡和垃圾收集机制，基本可以适应现今嵌入式设备的主流存储容量对读写速率的要求；由于整个驱动程序按层次按功能进行设计，比较容易进行后续的维
护和优化升级工作，今后优化的方向主要集中在地址映射和缓存；而且，由于整个NAND存储系统的驱动程序设计是一个的设计，具有很强的可移植性，可扩展性，有很好的应用价值。
参考文献:
[1]
STMicroelectronicsCoLtd.BadblockmanagementinsinglelevelcellNANDflashmemories[Z].STMicroelectronicsAppli-cationNote(AN1819),2006.
[2]
STMicroelectronicsCoLtd.GarbagecollectioninsinglelevelcellNANDflashmemories[Z].STMicroelectronicsApplicationNote(AN1821),2004.[3]
STMicroelectronicsCoLtd.WearlevelinginsinglelevelcellNANDflashmemories[Z].STMicroelectronicsApplicationNote(AN1822),2004.[4]Li-PinChang.Onefficientwearlevelingforlargescaleflashmemorystoragesystems[C].SAC'07,2007.
[5]
HyojunKim,SeongjunAhn.Abuffermanagementschemeforimprovingrandomwritesinflashstorage[C].The6thUSENIXSymposiumonFileandStorageTechnologies,2008:239-252.[6]JonathanCorbet,AlessandroRubini,GregKroah-Hartman.Linuxdevicedrivers[M].3rded.O'Reilly,2005.
[7]王标,周新志,罗志平.嵌入式系统中NandFlash写平衡的研究[J].微计算机信息,2008(14):8-9.
[8]
宋宝华.LINUX设备驱动开发详解[M].北京:人民邮电出版社,2008.
