关于一篇yaffs2很好的文章

1、 装置为硬碟及快闪记忆体（FlashMemory），虽然硬碟的容量相当大，但是其执行速度相当的慢、体积大且不耐震，较不适用于需要效率、体积及耐震考量的EmbeddedSystem，因为FlashMemory速度快，体积小及耐震的特性，大部份的EmbeddedSystem皆使用FlashMemory做为其内部储存装置。如市面上最常见到的行动电话、PDA（PersonalDigitalAssistant）内部储存装置等或是数位相机所使用的记忆卡，皆使用FlashMemory。因此该怎么操作或更有效率的使用FlashMemory，都是我们所要去关注的。二、动机FlashMemory目前分为两种：NO

2、RFlashMemory及NANDFlashMemory，尤于NANDFlashMemory有较快的EraseTime、SmallSize及成本较低的特性下，使得NAND更适用于EmbeddedSystem。FlashMemory是一储存装置，若要使用此储存装置，亦须要在FlashMemory上使用FileSystem。在一般的BlockDevice（e.g.Disk）上使用的FileSystem，如：NTFS、FAT32和ext2等等，都可用于FlashMemory上，但是这些FileSystem并非专为Flash所设计的，所以无针对Flash的特性去操作，因些需要透用FTL（FlashTr

3、anslationLayer）将其做转换的动作，如下图所示图一使用非专为Flash所设计的FileSystem（Flash-SpecificFileSystem），则需要透过FTL做转换，才能存取FlashMemory，但使用FTL会多了一个转换的过程，会浪费转换的时间，对于相当要求效率的EmbeddedSystem来说，不太适用，因此则有专为FlashMemory所设计（Flash-SpecificFileSystem）的FileSystem，如：JFFS、JFFS2和YAFFS等等。使用此种Flash-SpecificFileSystem则不再需要透过FTL来做转换，如图二所示3. Yaf

4、fs2基本框架以及运作 YAFFS为一ForNANDFlashMemory的Flash-SpecificFileSystem，它在设计上必会针对NANDFlashMemory的特性来设计，如在DataStructure的设计上与平常的FileSystem必定不同，还有专为FlashMemory设计的wear-levelingAlgorithm以避免同一区块过度存取而造成毁损等等。接下来则会介绍YAFFS所使用的DataStructures、GarbageCollection及Wear-Leveling等的基本架构及运作。3.1YAFFSDataStructure在一般的作业系统中，会使用Dis

5、k或其他储存装置以储存档案，并使用较快速度的RAM（RandomAccessMemory），将欲存取使用的档案复制至RAM中，再进行存取，最后再写回储存装置。利用RAM可加速整体的执行速度及效能。另外我们会设计一些DataStructure，包括在储存装置上使用的DataStructure及在RAM上使用的DataStructure。在储存装置上使用的DataStructure是为了管理在储存装置上所储存的资料及其属性（如UserID、GroupID及存取权限等）等，而RAM-Resident用以管理从储存装置所读出来的档案及资料或是逻辑位址（LogicalAddress）对应到储存装置实体位

6、址（PhysicalAddress）的记录表格等，如图三及图四。如此系统可在RAM中迅速找到欲存取的资料或从储存装置中读出资料到RAM中。图三-从储存装置读取资料至RAM中而YAFFS也有使用RAM-ResidentDataStructure和On-FlashDataStructure。以下列几个YAFFS主要的物件（Object）皆属于RAM-ResidentDataStructure：yaffs_Object：一个yaffs_Object可以是档案（File）、目录（Directory）、SoftLink或是Hardlink其中一种，而每一个yaffs_Object都会对应到一个yaffs

7、_ObjectHeader，而yaffs_ObjectHeader则是用以储存此yaffs_Object的一些属性值，例如该yaffs_Object是File或是Directory，此yaffs_Object的parentObjectId为何等等。yaffs_Object亦有如下的目录结构：parent：此栏位用以指向其父目录（parentDirectory）。siblings：此栏位用以连结同一个目录下的所有yaffs_Objectchildren：若此yaffs_Object为一个目录，则此栏位会指向此目录下的yaffs_Object集合。yaffs_Tnode：yaffs_Tnodes构

8、成一棵TreeStructure，此TreeStructure可加速搜寻一个File中的DataChunk。当其FileSize愈来愈大时，其TreeStructure的也会跟着长高，而其最高限制的Level为。详细资讯在接下来的部份会加以介绍。yaffs_Device：yaffs_Device储存装置的相关资讯，类似于VFS（VirtualFileSystem）的SuperBlock。储存着用来存取MTD（MemoryTechnologyDevice）的资料或存取NANDData的函数（Function）。每个yaffs_Object都会有一个yaffs_ObjectHeader，yaffs

9、_ObjectHeader为On-FlashDataStructure。存在于Flash上，当Flash挂载上时，会为每个yaffs_Object找寻该物件的yaffs_ObjectHeader，读出yaffs_Object的相关资讯。yaffs_ObjectHeader所储存的资讯如下：图四-yaffs_ObjectHeader记录内容Name：yaffs_Object的名称。ParentObjectID：此栏位记录yaffs_Object的父ObjectID。Type：说明此yaffs_Object是File、Directory、SoftLink或是HardLink。Protection（

10、OnlyForFile）：表示此yaffs_Object的权限为何。UID（FileOnly）：属于哪个UserID。GID（FileOnly）：属于哪个GroupIDTimeofLastAccess（FileOnly）：最后存取时间。TimeofLastModification（FileOnly）：最后修改时间。TimeofLastChange（FileOnly）：FileSize（FileOnly）：档案大小。equivalentObjectID（HardLinkOnly）：仅用于HardLink。Alias（SoftLinkOnly）：仅用于SoftLink。CheckSum：Name的

11、Checksum，计算Name避免不一致。YAFFS的最小储存单位为一个Page或Chunk，在YAFFS中Page及Chunk所占的大小相同，因此可视为相同的东西，但实际上两个名词所表示的意义不同，Page所指的是NANDFlashMemory上的实体资料储存区，而Chunk所表示的是yaffs_Object所配置到的逻辑资料储存区，Chunk的Size可以和Page不同，但在YAFFS中是相同的。如图五、图六，当Page与ChunkSize相同时，为一对一的关系，此时Logical-to-PhysicalAddressTranslation的MappingTable则会占去不少RAM的空间

12、，Page和Chunk大小不同时，假设为一对二时，此时Logical-to-PhysicalAddressTranslation的MappingTableSize则可减少为一半，如此可有效减少MappingTable在RAM中所占的空间。图五-Page与ChunkSize相同时的对应关系图六-Page与ChunkSize不同时的对应关系（一个Chunk对应两个Page）资料储存时是以一个Page一个Page的方式写入。Block为多个Page所组成的一个单位，一个Block中有32个Page，Block亦为一个EraseUnit（即是以一个Block为单位做清除的动作）。如图七示：图七在Fla

13、shMemory挂载上时，其会先扫瞄过所有中的Block所有Pages，以便把所有的yaffs_Object在RAM中建立起来。根据读到的Page其SpareArea中Tag的chunkID值的不同，会有下列不同的处理方法：1.chunkID>0：表示该Page为储存某个yaffs_Object的Data，并根据该Tag中的ObjectID到RAM中寻找该yaffs_Object是否在RAM中已建立，若建立则将该Page加入至所属的yaffs_Object中，若未建立则根据ObjectID去建立一个对应的yaffs_Object，并将该Page加入至对应的yaffs_Object中。2.

14、chunkID=0：表示该Page为yaffs_ObjectHeader，并根据此Page的SpareArea中Tag的ObjectID到RAM中寻找该yaffs_Object是否在RAM中已建立，若建立则将该Page加入至所属的yaffs_Object中，若未建立则根据ObjectID去建立一个对应的yaffs_Object。建立完后再根据yaffs_ObjectHeader中的ParentObjectID到RAM中寻找对应的Parentyaffs_Object，并将原yaffs_Object中的Parent指向Parentyaffs_Object。在扫描完所有的Block后，会把Flash

15、Memory上的所有File、Directory、SoftLink或HardLink建立成对应的yaffs_Object，以便修改其属性值。在建立完所有yaffs_Object及其与目录之间的关系后，会在RAM中形成一种阶层式（Hierarchy）的架构，如图八所示：图八在YAFFS中，File中的Data是储存在固定大小的Page中，其大小为512Bytes，每一个Page亦会有一个对应的Spare，其大小为16Bytes，用以储存该Page的相关资料。图九Spare所储存的资料如下所示图十Tags：chunkID：指相对于此yaffs_Object的第几个Chunk。当ChunkID为0时

16、，则表此Chunk所储存的是yaffs_ObjectHeader。serialNumber：用以辨别哪个Chunk为最新的Chunk。当更新此Chunk时，其serialNumber会加1并写入至其他Block的Chunk中，并将原Chunk的设为Invalid（表此DataChunk已无效），但若在将该Chunk设为Invalid之前则发生了断电（PowerLost）的突发事件，当电源回复并再重新扫描FlashMemory时，会检查某一yaffs_Object到有两个一样的Chunk（其ChunkID相同），但其serialNumber不同，则会比较此二Chunk的serialNumber，

17、以辨别出哪个Chunk为较新的Data，并将较旧Data的Chunk设为 Invalid。如下表所示：*byteCount：表示该yaffs_Object占此Chunk多少个Byte。objectID：此Chunk属于哪个Object的ObjecctID。ECC：Tags的ErrorCorrectionCode。unusedStaff：保留未使用的栏位。ECCData：DataChunk的ErrorCorrectionCode。PageStatus：当值为0时，表示此值为Invalid。BlockStatus：保留未使用的栏位。3.2TreeNodeStructure(TnodeStructu

18、re)系统欲存取装置上的Data时是以LogicalAddress（相对于该File所产生出来的偏移位址）的方式到所指定的位址进行存取，若欲到实体储存装置上取得Data，则须再经过一个机制的转换，将LogicalAddress转换为PhysicalAddress（实际储存装置的位址），才可从储存装置上读出Data至RAM中。这个机制最简单的方法就是在RAM上建立一个LogicalAddress到PhysicalAddress的对映表格（MappingTable）。直接将LogicalAddress对映至PhysicalAddress。如图十一所示图十一-在RAM中建立LogicalAddres

19、s对应至PhysicalAddress的对映表格在YAFFS中也使用了LogicalAddress到PhysicalAddress的对映机制。所使用的机制称之为TreeNodeStructure或TnodeStructure。FlashMemory挂载时，YAFFS会为每个File在RAM中建立一个Tree，当有一个要求要存取某个Chunk（或LogicalAddress）时，则会经由TreeNodeStructure的转换方式，找到Chunk的PhysicalAddress。使用TreeNodeStructure的优点为位址转换时间较迅速。TreeNodeStructure的转换TimeCo

20、mplexity为O(logN)，若是直接使用LogicalAddresstoPhysicalAddress的MappingTable，则位址转换为线性搜寻（LinearSearch），此种搜寻方式的TimeComplexity为O(N)。YAFFS采用此种方式来做为位址转换的机制可提升整体的存取速度。TreeNodeStructure是由多个TreeNode（或Tnode）所组成。依据Level的不同而分成两个部份：InternalTnode：每个InternalTnode由8个Pointers所组成。Lowest-LevelTnode（Level0Tnode）：每个Lowest-Level

21、Tnode由16个Entries所组成。图十二在Tree建立好后，当系统发出要存取该File的某个Chunk时，例如：Chunk0x235，就要在Tree上做Traverse的动作，以找寻到要求的Chunk。Traverse的步骤如下：1.将十六进制转化为二进制：0x235è00000010001101012.将二进制切割成000.000.100.011.0101，每一个切割区代表一个Level，由于Lowest-Level包含有16个Entries，因此切割出4个Bit（Bit3to0）。InternalLevel的Tnode皆包含8个Pointer，因此其余皆切割为3个Bit。S

22、tep3：Level0à0101=5当TreeNodeStructure刚开始建立时，仅会建立Lowest-LevelTnode，当File所配置的Chunk数超过16个时，则此Tree会建立一个internalTnode，并将其第0个Pointer指向原本的Lowest-LevelTnode。当读取到的Chunk数愈来愈多时，会一直新增Tnode，且Tree亦会愈来愈高，其Max-Level最大为6。在File已在RAM建立好TreeNodeStructure后，若此File的Size变大时，则会再多配置Chunk给此File，在将Data写入至Page后，则会去更新File的Tr

23、eeNodeStructure，将新配置到的Chunk加入至TreeNodeStructure中，更改步骤如下：1.搜寻新配置到的ChunkID。2.若在Internal-Level搜寻的过程中，发现没有Tnode，则建立一个Internal-Level的Tnode。3.当搜寻到Lowest-Level时，若也无Tnode存在，则建立一个Lowest-Level的Tnode。4.根据ChunkID中Level0所代表的值x，到Lowest-LevelTnode中的第x个Entry中检查有无该Chunk的实体位址存在，若没有则将实体位址填入该Entry，若已存在则将比较两Chunk在Spare中

24、的serialNumber，将较新的Chunk的实体位址写入该Entry中，并将旧的Chunk设为Invalid。3.在搜寻过程中，发现无Lowest-LevelTnode存在，则建立一Lowest-LevelTnode，并将该ChunkID写入对应的Entry中3.3YAFFSGarbageCollectionGarbageCollection主要是用于将已不必要存在且浪费空间的Block做回收的动作，以增加可用的Block数。而GarbageCollection只有某些事件发生时才会执行。在YAFFS中只有在下列事件发生时会执行GarbageCollection：将Data写入FlashM

25、emory更新yaffs_ObjectHeader而YAFFS的GarbageCollection又分成两种Mode：AggressiveMode及PassiveMode，其相异点如下表所示：AggressiveModePassiveMode执行条件ErasedBlocks<=(PreservedBlocks+1)ErasedBlocks：空Block数PreservedBlocks：保留Block数ErasedBlocks>(PreservedBlocks+1)检查回合数Iterations=(EndBlock-StartBlock)+11.Iterations=(EndBloc

26、k-StartBlock)+12.Iterations=Iterations/163.Iterations=200ifIterations>200YAFFS的GarbageCollection执行步骤如下：1. 从currentDirtyChecker到EndBlock之间寻找DirtiestBlock（包含最多InvalidChunk的Block）图十三2. 将currentDirtyChecker重置至所发现的DirtiestBlock的位置图十六3.4Wear-Leveling当FlashMemory在使用时，常常会对FlashMemory内的某个档案做修改的动作，若此时档案的大小

27、更动而需要更多Page时，且在FlashMemory内仍有空的Block，则会配置空的Block给该档案，若FlashMemory内已无空的Block，则会执行GarbageCollection的动作，清出空的Block以供使用。而在挑选空Block或使用GarbageCollection时挑选DirtiestBlock时，可能会造成部份的Block常常被挑选，而其他Block则很少被挑选配置。图十八在YAFFS中并没有明确的使用Wear-Leveling，而是以下面两种策略取代：1.保留部份Block，若部份Block毁损时可使用保留的Block取代。2.使用随机挑选Block（Random

28、BlockSelection），如此可避免不常被挑选的Block一直没人使用。但是实际在观察YAFFS的原始码时，并未发现有使用"RandomBlockSelection"，在询问YAFFS作者CharlesManning是否有将"RandomBlockSelection"实作出来后，其回信如下： Noitisnot.Forthemostpartwearlevellingisnotaproblemforalog-structuredfilesystemlikeyaffsbecauseusagecyclestendtoclearoutandreuseare

29、as.WearlevellingismuchmoreanissueforfilesystemslikeFATwhichuseblocklocations.Someblocks(eg.thoseusedforstoringtheFATtables)getheavilyused.Ihavedonesomeveryheavyacceleratedlifetimetesting(egwritingover150Gbytesofdataintoadevice)withnoindicationsofanywearlevellingissues.Veryfewblockshadreachedevenonet

30、enthoftheirlifetime在CharlesManning信中提到YAFFS实际上并未使用"RandomBlockSelection"，因此YAFFS的Wear-Leveling所依赖的只有第一个策略而已。3.5PartialPageProgramming当我们要将Data写入某个Page时，会先将该Page清除（Erase），即该Page的内容全为1，因为在FlashMemory中，仅能将Bit1改成Bit0，所以在清除过后所有的Bits皆会为1。在清除Page后才能将资料写入，例如Page内的Data为10111010，要将之改成01010101，则会先将Pa

31、ge清除为11111111，再更改成01010101图十九在NANDFlashMemory中，存取资料的最小单位为一个Page。若使用PartialPageProgramming则修改Page中的Data时可以更改部份的Bit而不需要将PageErase后才更改。例如Page中的Data为10111010，要将该Data改成10100010则只需将其中两个Bit更改为0即可，不需先Erase再写入。图二十使用PartialPageProgramming常会发生一种问题，即是在更改Bit的时候可能会有"走样"的情况而有没有完全更改过来，例如Page中的Data为1111111

32、1，欲将之改成00000000，但在更改的时候却未完全更改过来，而使的更改后的资料可能变为00111101，仍有部份的Bit未更改为0。图二十一在YAFFS中也使用了PartialPageProgramming，主要用于将某个Page设为Invalid，即更改该Page的Spare中pageStatus。当Page为Valid时，其Spare内的pageStatus内容为全1的状态，即未更改pageStatus，若要将近改为Invalid，则将pageStatus内容改为0（即全为0）即可。但是由于PartialPageProgramming会导致的错误，使得pageStatus的内容可能会无

33、法更改为0，因此在YAFFS中则采用了一种方法，即更改后的值，其值的二进制中，Bit为1的个数若小于6，则表示该Page为Invalid。否则视为ValidPage。图二十二4. PerformanceMeasurementsFlash-SpecificFileSystem有相当多的选择，欲使用何种FileSystem端看于设计者的需求，但在相同的需求下，该挑选何种FileSystem则可依其执行效能及该FileSystem可能额外所耗去的资源来做考量，在此则会评估使用yaffs在nandsim上时的效能及其可能所耗用的额外资源等。4.1环境建置测试yaffs与nandsim的效能之Hardw

34、are及Software环境如下：HardwareSoftwareCPUIntelDualCore3.0GHzRAM1.0GHzDualChannelNumberofCPUs1DisksubsystemSATAOSWindowsXPSP2OtherVMWare5.0（FedoraCore5+512MB+yaffs2+LinuxKernel2.6.17.9+nandsim）在FedoraCore5的NANDSim挂载时，亦需加入参数如下：modprobenandsimsecond_id_byte=0x71access_delay=180programm_delay=520erase_delay=

35、1.85second_id_byte：设定Nandsim大小，其参数值参考nand_ids.caccess_delay：Initialpageaccessdelay（microsecond）programm_delay：PageProgramDelay（microsecond）erase_delay：Sectorerasedelay（millisecond）4.2AndrewBenchmarkAndrewBenchmark主要的测试步骤分为五个阶段：Phase1：CreatingDirectories使用指令为：mkdirPhase2：CopyingFiles使用指令为：cpPhase3：Re

36、cursiveDirectoryStats使用指令为：ls-lPhase4：Scanningeachfile使用指令为：grep+wcPhase5：Compilation使用指令为：make使用AndrewBenchmark会挑选一合适的SourceTree来做Benchmark，其中会包含多个档案以供执行AndrewBenchmark的时候使用，在此测试中共有71个档案。其FileSizeRange所占的百分比如下：图二十四在执行AndrewBenchmark时，其执行过程中会将其SourceTree的内容复制至目的地，在此我们则要测试除了原本的SourceTree所占的空间外，yaffs额

37、外所使用的管理空间约占多少。在执行完AndrewBenchmark后，算出原本AndrewBenchmarkSourceTree所占的空间及执行后SourceTree在nandsim上所占的空间如下图所示：图二十五在执行完AndrewBenchmark后发现，在nandsim上一模一样的SourceTree却比原本的SourceTree多出了59.47k，这是yaffs在管理档案所花费的额外成本，例如每个档案所占的SpareArea等等，都会耗用额外的空间。4.3Multiprogrammingwith/withouthot/coldData在此测试中，会包含两种Task：TaskA：Sequ

38、entiallyWrite16KBytesofData（HotData）TaskB：RepeatedlyUpdate16BytesofData（ColdData）根据上述Tasks，执行下列六种执行方式，并会在各个方式下产生ResponseTime及Throughput，其中(x,y)表示有x个TaskA及y个TaskB同时执行：(0,1)：Update16BytesofData(1,0)：Write16KBytesofData(1,1)：MixtureofHotDataandColdData(2,2)：MultiprogrammingTesting(4,4)：Multiprogramming

39、Testing(8,8)：MultiprogrammingTesting在执行完后，针对TaskA及TaskB观察在各种执行方式下的ResponseTime及Throughput。针对ResponseTime的部份，是以RDTSC的方式取得暂存器中的Clock数，Clock数愈多，表示其所花费的时间愈长。TaskAResponseTime图二十六-ResponseTimeofTaskA在TaskA的ResponseTime中，在各种执行方式下，由于其TaskA的数量是以指数递增，而其RespnoseTime在统计图中亦以指数呈现上升的趋势，可知在TaskA数量愈多的情况下，其回应时间愈长Thr

40、oughput图二十七-ThroughputofTaskA在TaskA的Throughput中，其统计图与TaskA的ResponseTime呈现相反的情况，亦即其图形是以指数递减的趋势，表示当TaskA的数量愈来愈多时，其Throughput愈低。TaskBResponseTime图二十八-ResponseTimeofTaskB在统计图中TaskB的ResponseTime亦与TaskA相同，当TaskB数量愈多，其RespnoseTime亦愈高（表示愈慢）。Throughput图二十九-ThroughputofTaskBTaskB的Throughput亦会因为TaskB的个数增加而逐渐降低，表示当系统对na