nftl算法分析

NFTL

From ESSLabWiki

Jump to:??navigation?,??search

Independent Stuedy: NFTL

1??摘要

目前的随身电子产品，如手机、随身听所用的储存装置大都是flash memory，但因为flash?的特性，是无法重复写同一块记忆体位置做写入的动作，必须事先erase?该块记忆体位置（将其充电）才能再做写入的动作，因此一般我们所使用的档案系统，如FAT16?、FAT32?、NTFS?、ext2?等…?，将无法直接用在flash memory?上。若我们想要沿用这些档案系统，则必须透过一层Translation Layer?来将Logical Block Address?对应到实体的flash memory?的位置，并透过一些机制能让系统能把flash memory?当作一般的硬碟一样处理，我们称这层为FTL（Flash Translation Layer?）。

?

2??动机

因为FTL是用在NOR Flash?上的机制，而NOR Flash?在大容量的应用上并不如NAND flash?划算，因此有NFTLNAND Flash Translation Layer?）的产生，NFTL?主要想法与FTL?相似，主要差别在于是用在NAND Flash上，以支援目前随身电子产品对于容量上的需求。

目前对于NFTL的文件、系统架构并没有相当足够的资讯，因此我们借此机会来trace NFTL?的原始码来了解，NFTL?详细的运作细节及系统架构，本文件将介绍NFTL?在Flash?上的Data structure?、RAM?上的Data structure?、NFTL?的READ / WRITE?动作、Garbage Collection?、Block management?。（图一）为NFTL?在整个档案系统中所扮演角色。

（图一）

3??NAND flash?的特性

在介绍NFTL之前，必须先对NAND?有一些基本的了解，会帮助我们了解NFTL?以及知道为什么一般的file system?无法用在flash?上。以下是一个NAND flash memory?的架构图（图二）

（图二）NAND flash memory的架构图

NAND flash?由很多层的block?组成，而block是erase?的最小单位。一个Block?通常包含了32?个page?，而page是read / write?的单位，一个page?的大小为512bytes(user space) + 16bytes(spare area)?。其中user space?是用来存放一般的data?，spare area?是用来储存一些meta data?作为管理file system?用。

4??Major RAM-resident data structures and on-flash data structures employed by NFTL

NFTL?主要的功能是将Logical Block Address?对应到实体的flash memory address?（物理块地址），借此来达到能让flash?使用FAT?等用在block device?一类的file system?。因为NAND flash?的一些特性，必须在RAM?上建构一些data structure?及algorithm?，并且在flash?上储存metadata?作为NFTL?初始时建构RAM?中的data structure?所用，才能达到此目的。因此在此我们要介绍NFTL?在RAM?上及flash?上的data structure?。

（1?）.??Terminologies?及NFTL?之基本架构

????因为NFTL的code?中，用了许多term?，在此必须先定义一些Terminologies?，来帮助之后的说明。(?可参考图三)

·??Erase Unit?：erase的基本单位，即flash?中的block?。?（物理块）

·??Virtual Unit?：RAM中对应flash?中block?的单位。实际上只储存对应的block?在flash?上的physical address（逻辑块）。

·??Block Chain?：NFTL将资料存在由block?所组的chain?中，该chain?则称作block chain?。透过存放在erase unit?上的metadata?资讯来达成。

·??Replace Unit?：在block chain中，接在第一个block?后的block?都称作Replace Unit??（块链第一物理块之后块）。

·??Virtual Unit Chain?：在RAM中，透过EUNtalble?、ReplUnitTable?可以找到每个virtual unit?属于哪个block chain?及他的replace unit?之physical address?。??（块链）

?

说明：一个逻辑块上对应一个??块链，具体的逻辑块上的各个扇区分别对应块链中最后物理块的相应扇区

（2?）.??RAM-resident data structures??（内存描述）

RAM?上主要的data structure?有下列几项：

struct NFTLrecord??{

????????????__u16 lastEUN;

?	__u16 numfreeEUNs;
?	__u16 LastFreeEUN;
?	__u16 *EUNtable;
?	__u16 *ReplUnitTable;
??????????????unsigned int nb_blocks;
??????????????struct nand_oobinfo oobinfo;

};

其中：

·??LastEUN?代表flash中最后一个block?的physical adderss?（物理块号）。

·??numfreeEUNs?代表目前共有几个free blocks。

·??LastFreeEUN?代表最后一个被找到的free block? ·??*EUNtable?是一个logical to physical?的table?，纪录每个block?所属的chain?的起始physical address。其index item?代表logical address?；data item?代表physical address?。而透过EUNtable?我们可以找到该virtual unit?对应的block?所属block chain?的起始physical address?。此table?是存在RAM?中。参考下图。

·??*ReplUnitTable?是一个physical to physical?的table?，纪录每个在chain?中的block?，其之后的block之physical adderss?，以维持Virtual Unit Chain?的结构。其index item?代表目前的block?的physical address；data item?代表串在他后面的block?的physical address?。此table?存在RAM?中。

·??nb_blocks?代表Flash中共有几个block?。参考下图。

·??oobinfo?则是用来储存自flash中读出的oob?的information?。

（3?）.??on-flash data structures??（介质存贮格式）

在Flash上的data structure?主要则是存在Spare Area?的oobinfo?。OOB则是由bci??(block control information)?及uci(uni control information)?组成，bci?记录每个page?的status?，uci?则记录每个block?的information?，详细内容如下图（图四）：

（图四）oob中所有的资料

·??nftl_bci?内包含ECC(error correct code)及Status?、Status1?，而bci(block control information)?，是每个page一个，主要用来记录每个page?的status?。

????ECC?是用来预防资料存取发生错误时所需的错误更正码。

????Status?、Status1?则是记录每个sector的状态。当写入资料到user area?时，同时将此资讯写入spare area的oob.b?中。而Status?、Status1?所存的资料是一样的，其目的是避免在资料写入时发生非预期的bit?由1?变成0?。在uci?方面也是相同的道理，之后不再赘述。

????其状态有下列四种：

??????SECTOR_FREE 0xff

??????SECTOR_USED 0x55

??????SECTOR_IGNORE 0x11???？

??????SECTOR_DELETED 0x00??？

·??nftl_uci?内包含nftl_uci0、nftl_uci1?、nftl_uci2?，而uci(unit control information)?是记录整个block?的资讯，是每个block?一个，他们在flash?上的储存方式如（图五）

???nftl_uci0?包含VirtUnitNum及ReplUnitNum?。

??????VirtUnitNum?存每个block的Virtual address?，以便在初始时建立EUNtable?。

??????ReplUnitNum?存接在此block之后的Replace Unit?的physical address?。

写入flash的时机有下列几种可能：1.?在新增block?到block chain?中时写入oob.u?中。2.folding?完成后，重新设定其??VirtUnitNum?、ReplUnitNum?等…?。

???nftl_uci1?包含WearInfo、EraseMark?。

??????WearInfo?记录该block?被erase?过的次数。

??????EraseMark?则是用来确定该Block?是否被erase?过。在成功erase block?后会将其内容写为ERASE_MARK 0x3c69?。

???nftl_uci2?包含FoldMark、unused?。

???????FoldMark?：我们在做Fold Chain时(?从一个最长块链,各扇区合成一个块，擦除回收可用块)?，若要做inplace?不需另找中间空闲块，out?place?需另找中间空闲块）时会先将其目标erase unit?的FoldMark设为FOLD_MARK_IN_PROGRESS?。

???????Unused?决定做inplace fold chain后将此栏位全设为1?。

（图五）oob在block?中存放的方式

其中，oob.ua、oob.ub?、oob.uc?需要放在不同的page?主要原因是，我们不一定会同时存取这三样资讯，如果我们把他放在同一个page?中，若我们先写入oob.ua?，之后又想写oob.uc?，此时我们就无法将oob.uc?写入，除非我们将该block rease??（1?个扇区擦完后只能写一次）。

（4?）?.??初始构建?（从介质存贮格式构建内存描述）

???接着介绍NFTL的基本架构，在NFTL?初始时，会读取每个block?中的metadata?（oobinfo?），然后在RAM中建构出一个EUNtalble?、ReplUnitTable?(?稍后我们会详细介绍)?来模拟成一个Virtual Unit??Chain?。Virtual Unit Chain则是由一个以上的Virtual Unit?所组成，virtual unit则是在RAM?中用来对应flash?中的erase unit?，实际上virtual unit?并不储存资料，他只储存所对应的erase unit?的physical address?，即ReplUnitTable?的entry?，而Virtual unit chain?则是一个logical address?指着virtual unit chain?的第一个virtual unit?的位置。如下图（图三）所示：

（图三）Virtual Unit Chain与Block Chain?的关系

5??Blocks management of NFTL

因为NAND flash的erase?单位是block?，所以对大多数的flash file system?而言，管理block?是主要的课题之一，以下介绍NFTL?管理block?的方式、如何找到free block?以及如何选择block?去erase?。

（1?）.??How blocks are managed by NFTL?

主要透过RAM中的两个table?：EUNtable?、ReplUnitTable?来完成（EUNtable、ReplUnitTable?的介绍可参考图三及section4.1?）其用法如图七。

而ReplUnitTable另外记录了每个Block?的状态，当我们想要知道某个block?的状态是FREE?或是RESERVED?时都是透过ReplUnitTable?。而该资讯是在系统起始时所建立的。以下为ReplUnitTable?所能记录的状态。

·??BLOCK_NIL??????????????（＝0xffff?）???表示该block后面没有串连别的block

·??BLOCK_FREE????????????（＝0xfffe?）?表示该为free block

·??BLOCK_NOTEXPLORED??（＝0xfffd?）只有在mounting NFTL时才用到。

·??BLOCK_RESERVED???????（＝0xfffc?）表示该block坏掉或是为bios block?。

·??非以上为下一块的物理块号

ReplUnitTable?最主要的功能是当run time?时，我们可以透过在RAM?中的ReplUnitTable?知道哪些block?是属于同一个chain?中的，也可以用来计算每个chain?的长度等….

（图七）Virtual Add.指的是Virtual unit?在RAM?中所在的位置。透过EUNtable?找到Chain?的实体起始位置，再透过ReplUnitTable?找到Repl unit?。在RAM?中，整个chain?的架构都是靠ReplUnitTable?维持的。

（2?）.??How to select free block in NFTL?

选择free block对于wear-leveling?是相当重要的一个动作，若我们一直选择到相同的block?来做读写其相对被抹除的次数也会大大提升，造成erase?次数不平均的现象。

在MOUNT NFTL时，我们会将最后读到的free block?的physical address?存到??LastFreeEUN?，而我们在找Free Block?时，会先看LastFreeEUN?是否真的可用，若可用则使用该block?；否则循序找其他free block?。程式码（NFTL_findfr?eeblock?（））简述如下：

（3?）.??How blocks are chosen to be erased?

如何选择block被erase?是个重要的问题，他不仅影响整个系统的效率，也可能造成erase?次数不平均的现象，在此我们介绍NFTL?的选择block?被erase?的方法。

NFTL?认为，最长的chain?能够free?最多的block?，并不理会block?的erase?次数。而找最长的chain?也是以greedy的方式将整个flash?找一次（在RAM?中透过ReplUnitTable?找），程式码简述如下：

6??NFTL initializes,handles reads,and handles writes

这边介绍NFTL在系统初始时，如何将存在spare area?的资讯键构成run time?时RAM?使用的资讯。

1.??NFTL initializes

·??Ini the EUNtable?、ReplUnitTable

·??一个chain一个chain?的循序读取每个block?的oob (oob.ua/oob.ub)?。

·??建构??ReplUnitTable

·??将block status存到ReplUnitTable?中。

·??Erase unreferenced block?（不在Chain?中的Block?）、计算free block?个数

·??如果unreferenced block无法erase

?????ReplUnitTable[block] = BLOCK_RESERVED;

·??否则

????ReplUnitTable[block] = BLOCK_FREE;

·??numfreeEUNs++;

·??LastFreeEUN= block

2.??handles reads

直接找latest version的page?做read?，如何找latest version?请参考section.?9?。

3.??handles writes

·??Findwriteunit?()

??????若在所属的Chain中后面的Block?对应的page?状态为free?则回传该block?的physical address?。

?????若无法在所属的Chain写入则???Find free block?，参考section.?5?.2??，链入chain?中。

??????若没有free block则做fold chain?，参考section.?8?。

·??找到可写入的block则将对应的page?之oob.b.status?设为SECTOR_USED?。

·??最后将Data及ECCinfo?写入

（图九）当我们要更新block 11的第4?个page?时，我们会先看看他之后的block 22?的第4?个page?是否为free。是则写入；不是则找free block?串在block 22?，然后把资料写到新的block?的第4?个page?。(?最后一版最新)

7??About wear-leveling algorithm of NFTL

因为flash的每个block?有erase?次数的限制，当某个block erase?次数过多，可能会造成该block?存取速度变慢，严重时甚至会造成该block?毁损。因此我们希望能够平均每个block erase?的的次数，此机制称为wear-leveling?。

此版本的NFTL并没有实作Wear-Leveling?，只有预留一些资讯，如WearInfo?等…?，我想Wear-Leveling?能够在find free block?时作free block?的选择来达到平均抹除次数的目的。

8??Garbage-collection algorithm of NFTL?(?垃圾回收)

由于flash在更新资料时，无法将资料重新写回相同的位置，除非先将该位置erase?才能再写入，所以必须采用outplace?的方式写回资料，因此会产生许多不同版本的资料，存放在不同的block?中，而旧版本的资料则是无用的，所以必须要有garbage-collection?的机制，以下是garbage-collection?在NFTL?中的作法。（NFTL_makefreeblock?（）函数）

??Find longest chain??

???在NFTL中，GC?（garbage-collection?）主要目的是要回收最多的invalid block?，而NFTL greedy?的认为最长的chain?中，能回收最多的block?。而找最长的chain?是透过ReplUnitTable?找出最长的Chain?并将该起始位置传给NFTL_foldchain()?做回收的动作。

???NFTL_foldchain()

????判断是否可做inplace fold chain?

有时我们是在write时发现chain?中所对应的page?皆已使用，所以必须先判断是否可以做inplace fold?其步骤如下。

???读取Chain中Block?的每个page?的oob.b?，以每个page?的sector??的status?判断可否inplace?。

???若可做inplace将targetEUN?设为Chain?的最后一个block?之physical?位置（物理块号）；反之找一个free block?当作targetEUN?。

??将last version的page?对应其位置复制到targetEUN?中，如（图六）。

?????NFTL_formatblock?()

?????Erase??没用的Blocks

????????先读出将被erase的block?的oob information?。

???????????Erase?该block?。

???????????????将oob.ucWearInfo+1，写回该block?的spare area?。

??????????????将此block在ReplUnitTable?中的栏位设成BLOCK_NIL?，并将numfreeEUNs+1

?????????完成fold动作后，更新oob.uaVirtUnitNum?、oob.uaReplUnitTable?。

??????????????oob.uaVirtUnitNum = thisVUC?（该Chain?原本的virtual address?）。

??????????????oob.uaReplUnitNum =??0xffff??(?BLOCK_NIL?)

??

?????更新EUNtable、ReplUnitTable

??????????????ReplUnitTable[targetEUN]=block_NIL

??????????????EUNtable[thisVUC] = targetEUN

（图六）??fold chain示意图，targetEUN?的page?一开始全为free

9??How do NFTL tell the latest version of a piece of data from the old versions of the data (ie,dead data)?

前面我们提到，flash上更新data?大都是使用outplace?的方法，所以在我们读取资料时可能会有许多不同版本的资料，而读取最新版本的data?对于大多数的flash file system?都是很重要的问题。在此我们介绍NFTL?读取最新版本资料的方法。

当我们在要更新DATA(sector中的资料)?时，会将block?中第n?个page?写到他的replace unit?的第n?个page?，所以我们只需要找chain?中最后一个状态是SECTOR_USED?的page?就能够保证他是latest version?。如下图（图八）所示：

（图八）图中红色粗体的page的资料为latest version

10??Partial page programming

Partial page programming?是指flash?上的page?在还没被erase?前，又将其中某些bit?由1?改为0?,如下图（图十）。这在flash?上容易造成partial page programming?后的资料不正确，而且对于flash?的制造上会提高其成本，所以在新一代的flash?是不支援partial page programming?的。因此一个flash?的file system?是否有使用partial page programming?是一项值得拿来评估file system?的指标。

(?图十) partial page programming

在NFTL上，由4.3?时提到NFTL on-flash data structures?，NFTL?将每个flash?上的block?的前三个page?的spare area分为oob.b?、oob.u?使用。其中第一个page?的oob.u?存VUN / RUN?、第二个page?的oob.u?存erasemark?、第三个page?的oob.u?存foldmark?。而当NFTL?完成garbage collection?时，会将erase?的block?的erasemark?写为0x3c69?，而当NFTL?要将资料写入第二个page?时，会一起将该page?的oob.b.status?状态改为SECTOR_USED?，此时NFTL便做了partial page programming?了。另外NFTL?在产生一个新的chain?或是将block?加到chain?后面时，会先将资料写入page?并在该page?的oob.b?中写入status?与ECC?，最后才将VUN / RUN?写入oob. u..a?中，因此若第二的page?有使用到话，也会发生partial page programming?。如下（图十一）

（图十一）oob.b、oob.u?在block?中所摆放方式及partial page programming?所发生情况。

图片网址：http://www.voidcn.com/article/p-ggfbeobq-ov.html