一种支持FAT文件系统的Flash转换层设计

匡 伟，吕霞付，陈 勇，郑思远

(重庆邮电大学网络化控制与智能仪器仪表教育部重点实验室，重庆 400065)

0 引言

Nand Flash因其非易失性、存取速度快、存储密度高、功耗低、芯片引脚兼容性高和成本低等优点［1-2］，作为一种可替代磁盘的存储介质，广泛应用于手机、数码相机和平板电脑等嵌入式设备中。文档分配表文件(file allocation table，FAT)系统具有高效，实现逻辑简单，兼容性高等特性，在嵌入式系统中得到了广泛应用［3］。

Nand Flash存储器具有先擦除后写入的硬件特性［1，4］，FAT 文件系统是专门针对磁盘等存储介质而设计的，不适合直接应用于Nand Flash，直接在Flash上应用FAT会很快让Flash局部老化而丢失数据［3，5］，必须为 Nand Flash 提供一个适配软件闪存转换层(flash translation layer，FTL)，将 Nand Flash模拟成一个与磁盘的特性兼容的块设备［6］。

目前针对FTL的研究主要集中在坏块管理、负载均衡和垃圾回收等方面，最大可能的将存储块以均等的机会分配给文件［5，7］。关于如何的减轻Nand Flash负载，减少Flash的擦除次数的研究却很少。

本文提出一种基于缓冲机制应用于FAT文件系统的FTL，在RAM中为Flash分配一个用于读写的缓冲区，将一部分关于Flash的读写操作转移到RAM上，减少Flash存储块的擦除次数，延长Flash的寿命，提高数据的读写速度，本系统在ARM9和hynix公司H8BCS0QG0芯片上得到验证。

1 Nand Flash简介

1.1 Nand Flash存储结构

Nand Flash存储结构如图1所示，Nand Flash由多个块(block)组成，每个block又是由多个页(page)组成。

其中page是Nand Flash的最小读写单位，block是 Nand Flash 的最小擦除单位［5，8］。每个 block 都有10 000－100 000次的擦除次数限制。

图1 Nand Flash的结构Fig.1 Structure of Nand Flash

1.2 Spare area信息

由于Nand Flash的工艺不能保证Flash存储块在其生命周期中保持性能的可靠，有可能出现坏块，所以Nand Flash的每个page分为main和spare区，main区存储数据信息，spare区保存坏块信息和错误检查和纠正(error correcting code，ECC)信息等。Spare区存储内容的格式如图2所示，BI是芯片出厂时的坏块标志，ECC存储main区数据的ECC校验码，Reserved为保留字节。

图2 Nand Flash存储页的结构Fig.2 Page structure of Nand Flash

2 FTL设计

2.1 Nand Flash的软件构架

Nand Flash模块的软件分为3层，本文主要讲述FTL层的设计与实现。如图3所示，FAT文件系统以sector为单位读写和删除文件，管理存储在Flash的文件。Flash分区与Nand Flash的硬件通信，FTL层通过映射算法将FAT中的逻辑sector转换成物理存储块，再从对应的物理块中读/写/擦除数据。

2.2 坏块检测与存储块管理

由于Nand Flash的工艺不能保证NAND的存储块在其生命周期中保持性能的可靠，在NAND的生产中及使用过程中都可能会产生坏块［6，8］。坏块可以分为两大类:1)固有坏块:芯片生产过程中产生的坏块，一般芯片厂商都会在出厂时将每个坏块第一个page的spare area的BI标记为一个不等于0xff的值;2)使用坏块:Nand Flash使用过程中产生的坏块，如果block擦除或者page写入错误，就可以简单地将这个块作为坏块来处理。

图3 Nand Flash的软件构架Fig.3 Software structure of Nand Flash

系统初始化时，FTL依次读取各个block的状态，使用数组phy_blk_status［］来记录各个物理块的状态。数组成员变量的可能值见表1。

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

物理块状态检测:1)读取block的spare area的第1个字节，如果此字节不为0xff，将block标记为坏块;2)如果block第一个page和最后一个page都为0xff，表示当前block已被擦除，将block标记为空闲状态;3)如果当前block的第一个page或者最后一个page还没有被编程，或者ECC校验错误，擦除整个 block，block状态标记为空闲状态;4)如果block的第一个page和最后一个page都已被编程，并且ECC校验正确，将block标记为应用状态，如(1)式所示，将逻辑块与物理块建立一个映射关系保存在数组l2p_map［］中。其中lbn表示逻辑块地址，pbn表示物理块地址。

5)如果某个page编程失败，则擦除当前page所在block，如果擦除也失败就将当前block标志为坏块，同时将block第一个page的spare area的BI标记为非0xff，和固有坏块信息保持一致，更新block状态表。

2.3 逻辑块与物理块之间的映射

由于坏块的存在，Nand Flash的由一系列不连续的物理块组成。FTL通过一个映射算法将物理块映射成逻辑块，将不连续的物理块转换成像磁盘一样连续的逻辑块，FAT可以像管理磁盘中的文件一样来管理Flash中的文件。

FTL使用数组l2p_map［］来管理逻辑块与物理块的映射关系，如果文件系统中有m个逻辑块，n个物理块(n＞m)，则l2p_map［］数组的成员变量个数等于逻辑块的个数m。Flash的每个page中有16字节的非易失性spare data，其中的最后2个字节为保留字节。又因为Nand Flash以block为单位进行擦除，FTL使用block的最后一个page的spare data的保留字节byte15和byte16存储当前物理块所对应的逻辑块，spare区和main区数据在page编程时同时写入。

逻辑块和物理块的映射算法如图4所示，系统上电时，首先遍历所有的物理块，如果存储块j不是坏块，则从物理块j的spare区的保留字节中读取逻辑块号 k，按式(1)所示的关系令 l2p_map［k］=j，建立映射表l2p_map［］。

图4 逻辑块和数据块的映射表Fig.4 Logical and physical block map

为了保持FTL的稳定性，某个block成为坏块后，FTL也可以继续读相应的block，写操作将无法完成，从而保证Nand Flash的数据不会丢失，保持系统的稳定性和可靠性。

3 FTL缓冲机制设计

3.1 缓冲机制

FAT对存储介质以sector为单位进行读写。而Nand Flash只能按page为单位进行读写，以block为单位进行擦除，page的大小一般为2 KBbyte，sector大小一般为512 Byte。由于Flash先擦后写的特性，文件系统每更新一个存储单元，就需要将存储单元对应page的内容读出，擦除对应的block，再将修改过的内容写回。Nand Flash各个block的擦除次数是有限，对block的频繁擦除，不但会缩短Flash的寿命，而且效率非常低。

针对此问题，FTL参照Linux虚拟盘的思想在RAM中分配一块空间作为Nand Flash的缓存区，通过缓存区向文件系统提供读写功能。对文件系统而言，缓冲区是一片连续的字节空间，对其读写就好像对通用的按字节读写的存储设备进行操作一样。如果文件系统需要往Flash中写入数据，首先将待写入的数据写入缓冲区，待数据写入操作都已写完或者缓冲区已满，FTL将缓冲区的数据回写到Flash中，从而减少多个小文件频繁写入而造成Flash存储块的多次擦除。

3.2 缓冲区设计

FTL缓冲区(cache)针对sectors和pages而设计，逻辑扇区号与逻辑块号的对应关系如下

(2)，(3)式中:ps表示每个page的字节数;ss表示每个sector的字节数;spp表示每个page对应的扇区数;sn表示扇区号;ppb表示每个block的page数。根据式(2)，(3)可得出如式(4)所示的逻辑sector与物理块号的对应关系，sector在当前block的page偏移量如式(5)所示。其中lbn表示逻辑块号;pbn表示逻辑块对应的物理块号;poffset表示sector在block中page的偏移量。

本系统采用的Nand Flash的page的大小为2 KByte，FAT文件系统中sector的大小为512 Byte，FTL cache的结构如图5所示。系统分配3个block大小的缓存区供FTL使用，每个cache块的大小为512 Byte，与sector大小相同，将(ss×ppb)个 cache块用链表链接起来就可以缓存一个block大小的数据。block_cache结构体中，block表示着当前缓存物理块的逻辑块号，count表示当前block中缓存的sector个数，dirty表示当前缓存block是否已被使用，age表示缓存block的年龄。sector_cache中sect表示当前缓存的sector号，dirty表示它是否被使用，next指向下一个sector，buffer是一个512 Byte的缓冲块。

3.3 FTL数据的读写

1)数据读取

FAT的最小读写单位为sector，当FAT读取数据时，首先将根据(4)，(5)式计算出sector对应的block号和page号，然后从block中读取对应 page的数据，如果当前sector已被缓存则更新cache的数据，如果sector未被缓存则从cache中寻找一个空闲的cache块，将当前sector缓存到cache中，然后再从cache中读取相应的数据。

图5 FTL cache设计Fig 5 FTL cache design

2)数据写入

sector_cache和block_cache都有一个成员dirty来指示它是否已被使用，数据写入cache时，FTL依次搜索各个sector_cache，如果当前sector已被缓存，则直接将cache的数据更新，如果sector未被缓存，则从cache中搜索一个空闲sector_cache，再将sector的数据缓存到cache中，同时将dirty标志置1，表示当前sector_cache已被应用。如果当前block的sector_cache已被分配完，则申请一个新的 block_cache，将dirty标志置1，再从新的block_cache中分配sector_cache。

3)Cache块的管理和数据回写

block_cache有一个成员age用来表示它的年龄，当读写时，FTL首先将age等于0的sector_cache分配出来使用，每次从block_cache中分配一个sector_cache，block_cache的年龄加1，年龄最大的block_cache就是更新数据最多的block。如果当前所有的cache块都被使用，FTL将年龄最大的block的数据回写到 Flash中，清除 dirty和 age标志。再将block对应的cache释放出来供新的sector缓存。

文件系统写入的数据都缓存在cache中，而cache位于RAM中，系统掉电后cache的数据都会丢失，因此写cache完成后必须按照一定的算法将cache的数据回写到Flash中。因此文件系统开始写入数据时，首先启动一个周期为T的定时器，定时器溢出时如果cache中有需要回写的数据，则将block_cache的数据写入Flash，如果cache还有数据需要回写，则再次启动定时器，直到写完为止。

定时器T控制着缓冲数据的回写周期，如果T较小，缓冲区数据回写较频繁，可以降低系统意外掉电等原因造成的数据丢失的可能性，但存储块被擦除的次数增加，负载增大;如果T较大，Flash负载减小，数据丢失的可能性增大。通过多次实验将T设置为5 s，系统的负载和稳定性可以达到一个较好的效果。

3.4 效率分析

Nand Flash与SRAM的读写时间如表2所示，SRAM中的读写速度为ns级，比Flash读写速度快很多。

表2 Nand Flash的读写时间Tab.2 Time of operation in Nand Flash

如表3所示，FTL将Nand Flash的读写转移到RAM上执行。以读写一个1 MByte的文件，文件系统读写1 MByte的文件需要访问32次FAT表。如果没有采用缓冲机制，文件系统需要从Flash中读32次FAT表，需要花800 μs;采用FTL时，只有3－6次读FAT表需要从Flash中读取，其余的直接从RAM中读取，需要花费的时间为100～200 μs。

写入1 MByte的文件时，文件系统会对FAT表更新32次;添加FTL缓冲功能后，只有当1个Block的 cache满了，才会对 FAT表进行更新，写入1 MByte的文件只会更新8次 FAT表，大大减少Flash的擦除次数。

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

4 负载/耗损均衡

4.1 耗损平衡概述

Nand Flash的每个块擦除超过10万次后就可能变成坏块，因此擦除和写入应尽可能地平均分配到整个Flash的所有块中，从而提高整块Flash的寿命，这就叫做负载平衡［2-5］。

在FAT文件系统中，如果每次为文件分配空间时，都按照FAT默认方式从前往后寻找空闲簇，那么处于前面的簇所在的块将被频繁的分配出去，处于后面的簇所在的区块被分配次数很少。这就导致flash中前面的block擦除次数过多，后面的block擦除次数较少，导致了严重的负载不平衡。

为了提高Flash的寿命，必须修改FAT分配空闲簇的方法，不能使用FAT默认方法去寻找空闲簇。而是采用一种负载平衡的算法，让每一个空闲簇有均等的机会被分配出去。这些空闲簇所在的块也有均等的机会被擦除，从而使各个块的寿命均等，有效的实现磨损平衡。

4.2 CRC负载平衡算法

循环冗余码校验算法(cyclical redundancy check，CRC)是一种在数据存储和数据通讯领域广泛使用的编码算法，具有强力的检错和纠错能力，开销小。CRC算法不仅是一种高效的检错算法，也是一种高效的随机数生成算法，对于一个输入的n位二进制码序列，根据CRC-CCITT生成多项式，产生一段16位的校验码。不同二进制序列生成同一个校验码的几率为0.004 7%以下。

FTL的负载算法采用CRC-CCITT算法来生成随机数。由2.1节可知，Flash中任何存储块状态改变，逻辑块和物理块的映射表l2p_map［］同时也发生了变化，FTL使用l2p_map［］数组作为二进制序列，根据CRC-CCITT生成多项式求其校验码crc。按照式(6)所示的规则获取一个随机数random_num

当文件系统需要分配一个空间时，从第random_num个block处开始搜索空闲块，使空闲块有均等的机会被分配使用。

系统上电时，如果flash中存储的内容发生改变，随机数random_num的值也发生了变化，文件系统从另一个块开始搜索空闲簇，所有的空闲块也会均等机会的被擦除，从而有效的实现了数据区各个块的磨损平衡。

5 结束语

本文设计了一种基于缓冲机制的应用于FAT文件系统的FTL，提供了一种缓冲区机制和一种逻辑块物理块的映射机制，解决了Nand Flash必须先擦除后写入、只能以块为单位擦除的问题，提高系统的读写速度，减轻Flash的总体负载，提供CRC负载平衡算法改善Flash的负载平衡，延长Flash总体寿命。然而FTL的缓冲区占用了一定的RAM资源，数据写入Flash的过程不是实时的，有5 s左右的缓冲时间。整个方案在ARM9和Nand Flash芯片H8BCS0上进行了验证，测试证明，该FTL可以有效地管理Nand Flash，并能有效地进行坏块处理和磨损平衡，应用于普通磁盘的FAT文件系统只需要做很小的修改就可以移植到Nand Flash上，下阶段的工作有:1)优化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文件系统［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文件系统的研究与设计［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.