毕设论文范文——F2FS文件系统实现分析及其在移动设备上的优化

本 科 生 毕 业 论 文（设计）题目F2FS文件系统实现分析及其在移动设备上的优化姓名与学号 指导教师 年级与专业 信息与通信工程所在学院 信息与电子工程学系 1摘 要随着移动设备产品的不断普及和闪存容量的增大，闪存文件系统类型成为一个越来越影响产品性能的因素。2012年三星公司发布闪存友好型文件系统F2FS，其对NAND闪存存储介质做了友好设计，不仅加快了数据的存取速度，而且解决了旧式日志结构文件系统存在的问题。但由于移动设备的存储空间十分有限，F2FS在数据存储上存在的空间浪费在一定程度上影响了其在移动设备上的应用。因此本文通过深入分析F2FS的实现以及其文件索引方式，设计并完成普通文件和目录文件的内联技术，解决F2FS在数据存储上的空间浪费问题，以进一步提升该文件系统的性能。关键词：F2FS，存储空间浪费，数据内联，目录内联AbstractWith the rapidly increasing requirement of mobile devices and the larger and larger capacity of Flash memory , flash file system plays a more and more important role in product performance. In 2012, Samsung released a new flash-friendly file system based on Log-Structured, namely F2FS. F2FS, which is specially designed for NAND flash, not only speeds up the data access, but solves the two problems arose in the traditional LFS. Due to the limited storage space of mobile devices, however, the application of F2FS on mobile devices is limited by its waste of storage space to some extent. So according to the implementation of F2FS, this paper works out the function called inline data and inline directory to reduce the waste and improve the performance.Key words:F2FS，waste of storage space，inline data，inline directory目录第一章 引言11.1 背景11.2 已往的研究闪存文件系统11.2.1 闪存文件系统JFFS21.2.2 闪存文件系统JFFS221.2.3 闪存文件系统YAFFS31.3 最新的研究成果F2FS31.4 本文的主要内容51.4.1 论文的主要内容51.4.2 论文的结构5第二章 F2FS概述及实现分析62.1 F2FS概述文件系统的基本功能62.1.1 磁盘资源管理功能62.1.2 文件管理和操作的实现62.1.3 文件系统实现需求82.2 F2FS概述磁盘布局和主要数据结构82.2.1 F2FS的磁盘布局82.2.2 F2FS主要数据结构92.3 F2FS实现分析recovery和checkpoint机制122.3.1 磁盘写入与checkpoint机制132.3.2 recovery机制14第三章 F2FS在移动设备上的优化普通文件数据内联163.1 普通文件数据内联技术概述163.1.1 普通文件数据存储存在的问题163.1.2 普通文件数据内联技术的基本思路173.2 普通文件数据内联技术实现183.2.1 设置支持数据内联的标志位及宏定义183.2.2 处理数据内联的关键函数203.2.3 增加普通文件内联数据的文件操作253.3 普通文件数据内联技术测试273.3.1 存储性能测试273.3.2 I/O性能测试29第四章 F2FS在移动设备上的优化目录文件数据内联344.1 目录文件数据内联技术概述344.1.1 目录文件数据存储的问题344.1.2 目录文件数据内联技术的基本思路344.2 目录文件数据内联技术实现354.2.1 目录文件数据内联的宏定义354.2.2 更新room_for_filename函数364.2.3 更新处理数据内联的关键函数374.2.4 增加目录文件内联数据的文件操作394.3 目录文件内联数据技术测试414.3.1 存储性能测试414.3.2 I/O存储测试44第五章 总结475.1 遇到的问题475.2 取得的成果485.3 后期展望48参考文献49附录A F2FS内联代码（部分）51附录B 文件读写过程代码流程分析56B1 文件读过程56B2 文件写过程56附录C 文件系统性能测试57C1 iozone测试内容57C2 iozone测试方法58第1章 引言1.1 背景随着移动设备的普及，智能手机和平板电脑的出货量都呈现两位数的增长，人们已经越来越依赖于移动设备上的图片、视频功能来记录信息。根据Display Search的预测，2014年全球手机市场的出货量将由2013年的近17.5亿台增长至近18.7亿台，其中随着智能手机需求量的不断攀升，智能手机的出货量相较2013年增长25%，将从2013年的9.6亿台增长到2014年的近12亿台1。而平板电脑的出货量也将从2013年的2.5亿台增长至2014年的3.2亿台，增长近28%。面对如此大的需求，各移动设备商家除了增加自身产品的出货量，更应该不断提升产品性能，以抢占消费者换机消费的商机。提升移动设备产品的性能，需重点关注的是数据的存储策略和读写速度。在存储方面，移动设备绝大部分采用了闪存存储方式，随着闪存容量的不断扩大，选择一个适合闪存的文件系统成为了提升产品性能的关键。闪存文件系统是一种设计用于在闪存上存储文件的文件系统2。随着移动设备产品的不断普及，加之闪存容量的不断增大，闪存文件系统已经被广泛地应用于移动设备存储。在移动设备存储上应用闪存文件系统的理由有三：（1） 擦除区块：由于闪存存储的特性，数据块在重新写入数据前需要进行擦除操作。擦除数据块的操作可能造成长延时，闪存文件系统对用户隐藏这一过程能够很大程度上提升设备性能。（2） 随机访问：由于随机访问的特性，闪存避免了费时的寻址过程，不存在寻址延迟。（3） 写入平衡：由于闪存存储的写前擦除性能，导致经常写入的区块容易损坏，而闪存文件系统能够使数据均匀地写到整个存储设备3。1.2 已往的研究闪存文件系统目前研究的闪存文件系统大多基于日志文件系统（LFS），这是因为日志文件系统可以实现闪存文件系统所需的上述三个特点。这类文件系统主要有JFFS，JFFS2和YAFFS。1.2.1 闪存文件系统JFFS闪存设备日志型文件系统（JFFS），由瑞典的AXIS Communication AB开发，是最早的闪存文件系统之一4。JFFS文件系统根据NOR闪存的存储特性进行设计，采用日志结构，解决了很大闪存设备存在的问题。tailheadJFFS作为日志文件系统，将闪存存储设备看作一个大的循环日志，文件的更新数据会被写入日志末尾的数据块中，同时日志最前面无效的数据块将被回收5。在处理垃圾回收时，JFFS采用这样一种策略：将所有有效的数据块移至日志末尾，并对无效数据块进行擦除，其大致过程如图1.1所示。垃圾回收前垃圾回收tailhead无效块未使用块垃圾回收后有效块图1.1 JFFS在垃圾回收前后磁盘情况1.2.2 闪存文件系统JFFS2顾名思义，JFFS2是JFFS的继承者，但它是一款专门针对NAND闪存存储设计的日志文件系统，在设计时修改了JFFS的底层算法，剔除了循环日志结构，并改善了读写平衡和压缩性能6。在实现过程中，JFFS2对每个数据块单独操作，并维护node和log的实例链表。其中节点块包含了文件实际的数据，日志则用来保存更新的数据信息。文件的数据从第一个数据块按顺序读入，当文件数据被更新时，更新的数据 通过日志形式写入其他区域，这种处理方式的缺点是可能导致文件数据块分散在闪存设备的整个空间7。在垃圾回收方面，JFFS2通过合理的算法智能地判别需要被回收的数据块，将有效数据移出至另外一个数据块中，并将该数据块擦除后供后续写入使用。该算法的大致思路如图1.2所示。块分配机制CLEAN 链表DIRTY 链表FREE 链表垃圾回收P(0.01)P(0.99)图1.2 JFFS2垃圾回收机制尽管JFFS2相对于JFFS而言进行了不少的改进和提升，但应用于在NAND闪存时仍存在许多不足之处。如（1）由于node和log分开，需要频繁的擦除操作，导致挂载时间过长；（2）随着闪存容量增加，仍会出现内存消耗过大的问题。1.2.3 闪存文件系统YAFFSYAFFS是第一款严格意义上专门针对NAND闪存开发的文件系统，该文件系统存在两个版本：YAFFS和YAFFS2，两者差别在于缓存页的大小，前者仅支持512bytes，而后者则支持2KB8。YAFFS并没有像其他闪存文件系统那样使用闪存转换层（FTL）来模拟块设备，而是直接在闪存设备上应用文件系统。该文件系统一般仅用于小的NAND闪存设备。在垃圾回收方面，YAFFS处理方式与其他闪存文件系统不同，其使用单调递增的序列号额外对数据块进行标记，使得文件系统可以快速找到标识有效索引节点inode9。YAFFS通过保存在缓存中的树结构来表示闪存设备的块结构，以实现快速挂载。1.3 最新的研究成果F2FS尽管已往对闪存文件系统的研究层出不穷，但目前存在的闪存文件系统在应用于移动设备的NAND闪存上时仍会存在很多不足。此外，基于日志结构的闪存文件系统还存在着两个方面的普遍问题，一是wandering tree引起的滚雪球效应（更新信息的传播）问题，二是cleaning process可能产生的不可预料的长延时10。为此，三星公司在2012年提出一款专门为NAND闪存设计的文件系统闪存友好型文件系统（F2FS）。该文件系统不仅解决了上述日志文件系统存在的两个问题，而且其特有的数据恢复机制实现了数据恢复的最大化，大大地提升了系统性能。在摩托罗拉公司公布的对摩托罗拉Moto X的评测报告中，对F2FS文件系统进行的相关测试很好地体现了该文件系统的优点。测试时Moto X对系统分区采用常见的ext4文件系统，而用户数据分区则采用F2FS。具体测试情况如图1.3a、b、c、d所示。图1.3 Moto X对F2FS测试报告a) 4K随机读性能；b)2 4K随机写性能；c) 256K连续读性能;d)256K连续写性能。从上述测试报告可以看出，F2FS使得Moto X在4K随机写入时有着非常出色的表现，远远超过了其他测试设备，而在其他几项测试中也位居前列11。此外该测试还表明在内存空间几乎占满的情况下F2FS的读写性能依然良好。1.4 本文的主要内容1.4.1 论文的主要内容一方面，尽管F2FS发布已经超过一年，但针对F2FS的解析说明文档少之又少。而F2FS在移动设备上优越的性能使得研究F2FS成为必要。因此本文首先对F2FS进行概述，讨论其磁盘布局和重要的数据结构并对F2FS如何实现数据的最大化恢复进行实现分析。另一方面，在实现过程中，F2FS并未采用extents 的方法来减少数据块的总索引大小，而采用文件索引树的策略，这使得F2FS 的索引节点（inode）要比Ext4 的索引节点大得多。在默认情况下，F2FS 的每个inode 占用4KB 大小的块（block），这为文件索引提供了大量的空间，简化了文件系统出现意外情况时数据的恢复操作。但在给数据恢复和文件索引带来方便的同时，也同时造成了这样一个问题：4KB 大小的inode 块可以索引将近4TB 的数据，而现实情况这么大的文件很少出现，因此4KB 大小的索引块造成了存储空间的浪费。基于这一点，本文对F2FS 文件系统进行优化实现普通文件和目录文件内联技术，以降低存储空间的浪费并进一步提高文件系统的性能。1.4.2 论文的结构第1章 引言：该部分介绍本课题的研究背景、研究现状和主要研究内容；第2章 F2FS概述及实现分析：该部分阐述了F2FS的磁盘布局以及本文涉及的主要数据结构，并分析了其数据最大化恢复机制的实现；第3章 F2FS在移动设备上的优化普通文件数据内联：该部分通过技术概述、技术实现和技术测试三部分进行阐述，对普通文件数据内联技术的算法原理和结构进行了详细分析；第4章 F2FS在移动设备上的优化目录文件数据内联：该部分通过技术概述、技术实现和技术测试三部分进行阐述，对目录文件数据内联技术的算法原理和结构进行了详细分析；第5章 总结：该部分通过遇到的问题、取得的成果及后期展望对本文进行总结。63第2章 F2FS概述及实现分析2.1 F2FS概述文件系统的基本功能在Linux体系中，文件系统担当着最重要的作用，Linux内核的应用层就是以文件系统为核心而展开的。文件系统主要实现两个功能：磁盘资源管理和文件管理操作的实现12。2.1.1 磁盘资源管理功能所谓磁盘资源管理，指的是文件系统需要对磁盘（存储设备）的使用情况进行记录，这些记录使用情况的信息称为元数据（meta data）。举例而言，在F2FS文件系统中，有两个数据结构主要记录这些元数据超级块（super block）和检测点（checkpoint）。其中super block记录了整个磁盘的静态信息，如磁盘的总数据块数，数据块的大小以及其他数据结构的存储位置。而checkpoint则记录动态变化的数据信息，如已经被使用的数据块数，空闲的数据块数以及下一次将被分配的地址等。2.1.2 文件管理和操作的实现所谓文件管理，指的是文件系统如何进行文件数据的存储和实现文件系统调用的接口。例如，在F2FS文件系统中，一方面，文件的存储使用多级node索引和node地址映射实现。即读写一个文件需要访问node和node address table(NAT)结构。另一方面，由用户层发起的文件操作，会通过虚拟文件系统（VFS）调用相应的函数进行实际的实现。一般而言，文件系统的功能可以用图2.1进行描述。图2.1描述了这样一个流程：一个用户空间发起的文件操作命令首先会被解析成相应的系统调用。相应的系统调用传递给内存中的虚拟文件系统（VFS），虚拟文件系统提供了一个通用的接口，其根据相应的系统调用和所处的文件系统，调用文件系统特有的实现函数。在这个例子中，特有的文件系统是本文研究的F2FS文件系统。而真正对磁盘（存储设备）进行操作的是三个层：F2FS、page cache和block layer。准备操作所需的数据创建新的页缓存向磁盘发生读请求将数据读至页缓存页缓存准备就绪数据在cache中NY执行特定的操作更新索引信息设置脏页将脏页同步至磁盘保证一致性处理请求，调用F2FS特定函数返回操作结果至VFS读过程用户空间发起操作解析为系统调用将请求传递至VFS用户获得操作结果写过程(注：从上至下分别为用户层，VFS层，F2FS层，页缓存层和磁盘层)图2.1 文件系统功能实现流程以文件的写操作为例，F2FS为首先根据所写数据的大小和位置找到相应的页缓存，页缓存是磁盘中数据块在内存中的缓存。如果在处理操作过程中，该页已经存在于页缓存中，则无需再次进行读取。否则便要在页缓存中生成一个新页, 并从磁盘中读出数据写入该页中。需要处理的页准备就绪后, 便可以把要写入磁盘的数据复制到该页的相应位置, 并更新相应索引节点（inode）的元数据(如文件大小，修改时间等)，同时将该页标记为脏。当页缓存中的脏页累积到一定数目，这些页便会被写入到磁盘里(这一操作也可以用sync系统调用触发)，至此数据便被从用户空间写入磁盘。2.1.3 文件系统实现需求（1） 碎片问题随着文件的移动和新文件的增加，磁盘中可以使用的空间变得越来越分散，特别是存储的文件都比较小的情况下。由于这对磁盘访问速度有很大的负面影响，文件系统应尽可能减少碎片的产生。（2） 有效利用存储空间在处理这一问题时，文件系统必须作出相应的折中。要充分利用存储空间，文件系统必须将大量管理元数据存储在磁盘上，这就抵消了更紧凑的数据存储带来的好处，甚至可能产生负面影响13。（3） 文件数据的一致性对于一个系统而言，即使再稳定的内核也会存在突发性的停止工作，这可能是软件错误，也可能是断电、硬件故障等其他原因。这类事故可能造成不可恢复的错误，文件系统必须尽可能地快速全面纠正可能出现的损坏，使文件系统还原至一个可用的状态14。2.2 F2FS概述磁盘布局和主要数据结构2.2.1 F2FS的磁盘布局F2FS文件系统的磁盘布局与常规的日志文件系统基本一致。其磁盘布局如图2.2所示。元数据信息节点数据信息Super BlockSBCheckpointCPSegmentInfo.TableSITNodeAddressTableNATSegmentSummaryAreaSSAMain图2.2 F2FS文件系统磁盘布局示意图在F2FS中，磁盘区域依照block，segment，section和zone进行功能上的划分。下面分别对这几个结构进行简单的介绍。（1） BlockBlock是磁盘数据写入的最小单位，在系统默认情况下1 block = 4096 bytes = 4KB。该结构与内存中的page一一对应。（2） SegmentSegment是写日志的最小单位。在系统默认情况下1 segment = 512 blocks = 2048 KB =2MB。文件系统在同一时刻维护2/4/6个segment用于数据写入。每个segment用于如下6种不同类型的数据hot, warm, cold * node, data。其中用于保存目录信息的data/node标记为hot，因为其访问程度最为频繁。其他保存普通文件信息的data/node标记为warm，而间接的data/node标记为cold。进行数据分类的目的一方面是用于确定数据的写入顺序，另一方面是当系统发生崩溃时，对不同的数据采用不同方式的恢复机制。在实现过程中，若想获得当前使用的segment，可以调用CURSEG_I函数获取。（3） SectionSection由多个segments组成，是进行垃圾回收的基本单位，在进行垃圾回收时，一次只对一个section进行操作。在系统默认情况下，1 section = 1 segment。该值可在磁盘格式化时进行修改。（4） ZoneZone由多个连续section组成，这是为进行并发写操作而特意划分的。一个固态硬盘SSD的多个FLASH原则上可以进行并发写的操作。如上所述，F2FS在一个时刻会维护6个不同的segments用于日至写入。F2FS在选取时，会尽量从不同的zone中选取6个segments，这就大大提高了写入性能。在系统默认情况下，1 zone = 1 section。2.2.2 F2FS主要数据结构在F2FS文件系统中，数据结构主要分为磁盘数据结构和内存数据结构。由于涉及到的数据结构过多，此处主要针对第三四章会涉及的数据结构进行简单的阐述，以方便后续讨论。（1）磁盘数据结构1. 索引文件数据的节点f2fs_node对于F2FS文件系统，在索引文件数据时，其采用的节点类型有f2fs_inode，direct_node以及indirect_node。而每个节点块都拥有一个node_footer结构用以记录节点的索引节点编号和节点编号等信息。下面对这三种node block类型进行简单的介绍。其数据结构如表2.1所示（有所简化，列出主体信息）。node_block类型数据结构f2fs_inode（索引节点）struct f2fs_inode _le16 i_mode;./*省略部分元数据*/./*数据块指针*/_le32 i_addrDEF_ADDR_PER_BLOCK;/*直接节点(2)间接节点(2)次间接节点(1)*/_le32 i_nid5;_packed;direct_node（直接节点）struct direct_node /*1018个数据块指针*/_le32 addrADDRS_PER_BLOCK;_packed;indirect_node（间接节点）struct indirect_node /*1018个直接节点*/ _le32 nidNID_PER_BLOCK;_packed;struct f2fs_node union struct f2fs_inode i; struct direct_node dn; struct indirect_node in; ; struct node_footer footer;_packed;表2.1 三种类型的f2fs_node的数据结构从表2.1中可见，在索引节点f2fs_inode中，在数据块指针后有5个节点编号。其中包括2个直接节点（即direct_node），2个间接节点（即indirect_node）和1个次间接节点（double_indirect node）。所谓次间接节点即有两级间接节点。再来研究几个宏定义的数据来源。DEF_ADDR_PER_BLOCK=923，ADDRS_PER_BLOCK=NID_PER_BLOCK=1018。这需要从数据结构出发。首先一个node block的大小为4096Bytes，而node_footer占用的空间24Bytes，则三种节点还剩4072Bytes可用。对于间接节点和直接节点，其结构成员只有一个。因此很容易计算得ADDRS_PER_BLOCK=NID_PER_BLOCK=4072/4=1018。由此可知，一个直接节点块可索引1018个数据块，而一个间接节点块可以索引1018个直接节点块。至于索引节点块，除去元数据占用360Bytes，5个节点编号占用20Bytes，因此可用空间为3692Bytes。由此可得DEF_ADDR_PER_BLOCK=923，即一个索引节点包含923个数据块索引指针。综上所述，可以得到一个索引节点块可以索引的文件大小为：一个次间接节点（包含1018个间接节点/节点）两个间接节点（包含1018个直接节点/节点）两个直接节点（包含1018个数据块指针/节点）2. 目录文件的数据块f2fs_dentry_block目录文件的索引方式和普通文件一致，索引节点分析不再赘述。而与普通文件不同的是，目录文件的数据块存储的不是普通数据，而是目录项(f2fs_dir_entry)。其数据结构如下所示：struct f2fs_dir_entry _le32 hash_code; /*目录文件名的哈希值*/ _le32 ino; /*目录文件的节点号*/ _le16 name_len; /*目录文件名长度*/ _u8 file_type; /*文件类型*/_packed;struct f2fs_dentry_block /*有效目录项的位图*/ _u8 dentry_bitmapSIZE_OF_DENTRY_BITMAP; _u8 reservedSIZE_OF_RESERVED; struct f2fs_dir_entryNR_DENTRY_IN_BLOCK; _u8 filenameNR_DENTRY_IN_BLOCKF2FS_SLOT_LEN;_packed;具体f2fs_dentry_block的分析将在第四章详细展开，此处只做最简单的说明，给出其数据结构已保证有一个简单的印象。（2） 内存数据结构对第三章、第四章内联技术涉及的内存数据结构最主要的是f2fs_inode_info，该结构是对VFS数据结构inode的补充，该结构包括了f2fs_inode结构的私有数据。其数据结构为（仅列出相关的成员）：struct f2fs_inode_info struct inode vfs_inode; /*VFS inode结构*/ . /*相关元数据*/ /*F2FS私有数据*/ unsigned long flags; /*读取和传递磁盘文件的标志*/ .由f2fs_inode_info的数据结构成员可知，f2fs_inode_info是内存中用以完全表现f2fs_inode的结构体，首先通过通用的vfs_inode结构来存储相关信息，不能通过inode涵盖的信息则由f2fs_inode_info的其他信息补充。2.3 F2FS实现分析recovery和checkpoint机制在2.1文件系统的基本功能文件系统实现需求中提到一点，维护文件内容数据的一致性是一个关键问题。而F2FS在这方面有着优越的表现。当数据写入磁盘时，系统发生意外（掉电崩溃等）导致数据没有正常写入，即可能导致文件系统数据的不一致。对日志文件系统，NODE和DATA都以日志的形式写入磁盘，元数据（META）在磁盘上也有两个备份（确保一个是正确的），这样的机制就确保了无论系统何时发生意外，文件系统都能使用磁盘上的冗余数据恢复到一致状态，保证数据的一致性。数据恢复机制和数据写入磁盘的方式密切相关。对于Linux系统，其页缓存机制采用推迟写入的方式写入数据，以确保系统的性能15。这就是说，在内存中被标记为脏的页并不会立即写回磁盘，直至发生以下三种情况：（1） 页缓存（page cache）过大或脏页过多；（2） 某些页处于脏的状态时间过长；（3） 特定的系统调用要求数据立刻写回磁盘（sync, fsync和fdatasync）。因此，存在于内存页中的数据在系统发生意外情况时就会丢失。而对于一种情况，即sync操作时发生在数据写入磁盘后而在元数据写入磁盘前的系统意外，其数据已经写入磁盘但由于没有索引而无法找回，而F2FS提供了相应的恢复机制找回这些文件数据。2.3.1 磁盘写入与checkpoint机制对上述列出的三种数据写入的情况，为简化讨论，下面以sync( )为例说明F2FS的磁盘写入机制。F2FS通过调用f2fs_sync_fs( )实现sync操作，该函数检测sbi（内存数据结构，存储磁盘超级块的信息）是否为脏，如果为脏则冻结文件系统并调用write_checkpoint( )将数据写入磁盘。Checkpoint机制实现示意图如图2.3所示。图2.3 F2FS的checkpoint机制函数write_checkpoint完成以下几个操作：（1） 按照DATA -NODE-META的顺序，将数据和元数据从内存页中同步写入至磁盘（其中META包括SIT/NAT/checkpoint）：f2fs_submit_bio(sbi, DATA, true);f2fs_submit_bio(sbi, NODE, true);f2fs_submit_bio(sbi, META, true);（2） 完成数据写入后更新checkpoint版本（checkpoint_ver）：ckpt_ver = cur_cp_version(ckpt);ckpt-checkpoint_ver = cpu_to_le64(+ckpt_ver);（3） 将最新的SIT/NAT从cache刷入page：flush_nat_entries(sbi);flush_sit_entries(sbi);（4） 完成上述工作后调用do_checkpoint进行真正的checkpoint，即将最新的元数据写入磁盘。函数do_checkpoint完成以下几个操作：（1）将NAT/SIT 内存页写入磁盘；（2）更新checkpoint中的元数据；（3）将checkpoint block写入page；（4）将orphan blocks写入page；（5）将SAT写入page；（6）将上述操作的内存页写入磁盘。2.3.2 recovery机制由上述checkpoint机制可以发现，当系统发生意外而崩溃时，只需退回到最新并没有损坏的checkpoint，文件系统的一致性即可保证。但这里存在一个问题，如果仅仅依赖checkpoint，对于发生在fsync/fdatasync与checkpoint事件之间发生的系统崩溃，数据虽然已经写入磁盘但无法使用。而recovery机制正是用于解决这一问题的机制，以实现数据恢复的最大化。Recovery与checkpoint机制的区别在于，checkpoint机制仅仅保证了文件系统的一致性，即保证磁盘上所有的元数据能够正确描述（索引）磁盘上索所有的数据块，在系统崩溃时，文件系统只要退回至checkpoint的上一个版本即可保证系统的一致性，而系统崩溃发生前成功写入磁盘的数据无法恢复。Recovery机制则是实现这种恢复，利用最近并没损坏的checkpoint，通过roll forwad恢复这部分数据。实现上述这一机制需要涉及两个数据结构，其在recovery机制的作用如图2.4所示。1. checkpoint：checkpoint保存了当前使用的segments地址信息，同时也保存了下一个将被使用的segment地址。而通过后者就可知道在checkpoint后数据写入的磁盘位置。2. node_footer：node_footer是node block中的一个结构体成员，通过该结构，所有的直接节点形成一个链表，即通过当前的直接节点可以获取下一个被使用的直接节点。同时该结构包含了该节点的checkpoint版本号，可以通过该版本号判断该节点是否是需要被恢复的节点。图2.4 F2FS的recovery机制上图说明了如何通过node_footer和checkpoint结构找出需要恢复的节点。一个可以被恢复的节点需要满足以下两个条件：（1） cpver_of_node = cp_ver;（2） 检测标志位判断该节点是否是通过fsync写入磁盘。第3章 F2FS在移动设备上的优化普通文件数据内联3.1 普通文件数据内联技术概述3.1.1 普通文件数据存储存在的问题根据第二章分析的f2fs_inode和f2fs_node结构，可得到索引节点块的结构示意图（如图3.1所示）。在一个索引节点块中，底部是一个node_footer结构，包含该节点块的节点号、索引节点号等信息，上面则是一个f2fs_inode结构。在f2fs_inode结构中的数据索引指针区有923个数据块指针，可索引923个数据块。默认情况下，数据块的大小为4KB，其可索引的文件大小接近4TB（见2.2节），但正常情况下，一般的文件都不可能达到这个值。考虑最极端的情况，在文件大小小于4KB时，仅有一个数据块被使用，图中f2fs_node块中阴影部分区域的存储空间均是未被使用的，也就是说F2FS在存储小文件方面是存在存储空间浪费的。数据索引指针区923个数据块指针直接间接节点区node_footer数据块data blocknode_footerf2fs_inode图3.1 f2fs_node block结构示意图此外在文件系统性能方面，对小文件（大小小于4KB）进行读写操作时，通过数据索引指针间接访问数据块在一定程度上降低了文件数据的访问效率，影响了文件系统的性能。3.1.2 普通文件数据内联技术的基本思路对于3.1.1节中提及的两个问题，本文提出了普通文件数据内联技术（data inline），该技术一方面解决了F2FS存在的存储浪费现象，另一方面提高了对小文件数据的访问效率。其实现的基本思路是将文件大小小于某一定值的文件数据直接存储在索引节点块中未使用的区域，而不重新分配新的数据块，如图3.2所示。即将图3.2中数据块中的阴影部分存储到索引节点块的阴影部分区域，从而达到节省存储空间和提高数据访问效率。i_addr0数据内联小文件数据数据索引指针区923个数据块指针直接间接节点区node_footer数据块data block图3.2 普通文件数据内联示意图上文提到文件大小小于某一个值的文件可以实现数据内联，这里给出该定值的定义。由图3.2所示以及f2fs_inode的结构可知，索引节点块中有923个数据块指针，首先，第一个数据块索引指针作为保留地址，用于特定的目的（将在下文详细阐述）。其次，F2FS对文件系统的附加属性xattr也可以实现内联技术，该技术在F2FS发布时已经实现，其实现占用了923个地址中的50个地址。因此，可用于数据内联的地址总共为872（923-1-50）个，而每个地址占用4bytes，由此得出可存储，即文件大小小于3.488KB的文件可以实现数据内联。3.2 普通文件数据内联技术实现3.2.1 设置支持数据内联的标志位及宏定义标志位分为磁盘部分和内存部分。对于内存部分，主要是对f2fs_inode_info这一数据结构进行操作。该数据结构存放的数据大多为f2fs_inode的私有信息。（1）设置数据内联的挂载选项如果要启用数据内联功能，必须设置相应的挂载选项，用户可以选择是否启用数据内联的功能。具体见代码清单3-1。代码清单3-1： #define F2FS_MOUNT_INLINE_XATTR 0x00000080+#define F2FS_MOUNT_INLINE_DATA 0x00000100通过添加这一挂载选项后，用户即可通过“mount -t f2fs -o inline_data 设备名 挂载点”挂载F2FS文件系统并启用数据内联（inline data）。（2） 设置内存数据结构的数据内联标志首先将数据内联标志加入枚举数据结构中，使之成为内存数据的一种可选标志。该标志是对f2fs_inode_info设置的，涉及该数据结构中的flags成员（即fi-flags）。具体实现见代码清单3-2。代码清单3-2： -899,6 +900,7 enum FI_DELAY_INPUT, /*used for recovery*/ FI_NO_EXTENT, /*not to use extent cache*/ FI_INLINE_XATTR, /*used for inline xattr*/+ FI_INLINE_DATA, /*used for inline data*/; 内存数据内联标志的设置起初需要根据磁盘数据来确定，即当某个文件数据从磁盘读入内存时，如果该文件索引节点f2fs_inode设置了数据内联标志，则内存数据结构也将相应的设置标志FI_INLINE_DATA。而反过来，如果数据在写回磁盘前检测到可以实现数据内联，则会设置内存数据内联标志，在数据写回时如果检测到设置了该标志，则对应地也会将磁盘数据结构设置相应标志。具体见代码清单3-3。代码清单3-3： -936,6 +938,8 static inline void get_inline_info ( /*从磁盘中获取内联信息*/+ if(ri-inline & F2FS_INLINE_DATA)+ set_inode_flag(fi, FI_INLINE_DATA); -945,6 +949,8 static inline void set_raw_inline ( /*将内联信息传回磁盘*/+ if(is_inode_flag_set(fi, FI_INLINE_DATA)+ ri-inline |= F2FS_INLINE_DATA;（3） 获取内联数据的起始地址内联数据存储在f2fs_inode对应的索引节点数据块中，而在内存中数据块均以页（page）的形式存在。通过获得f2fs_inode对应的页的首地址，再进行偏移最终获取内联数据的起始地址i_addr1。具体实现代码见代码清单3-4。代码清单3-4： -970,6 +976,13 +static inline void *inline_data_addr(struct page *page)+ struct f2fs_inode *ri = F2FS_INODE(page);+ return (void *)&(ri-i_addr1);+（4） 设置磁盘内联数据标志和相关宏定义首先设置内联数据的标志，即上述代码均有提到的F2FS_INLINE_DATA。其次是在3.1.2节中提到的内联数据的大小和内联数据在索引节点块中的偏移，此处给出的宏定义为MAX_INLINE_DATA和INLINE_DATA_OFFSET。具体见代码清单3-5。代码清单3-5： -153,6 +153,14 #define F2FS_INLINE_XATTR 0x01 /*file inline xattr flag*/+#define F2FS_INLINE_DATA 0x02 /*file inline data flag*/+#define MAX_INLINE_DATA (sizeof(_le32) *(DEF_ADDRS_PER_INODE - F2FS_INLINE_XATTR_ADDRS -1)+#define INLINE_DATA_OFFSET (PAGE_CACHE_SIZE - sizeof(struct node_footer)- sizeof(_le32)*(DEF_ADDRS_PER_INODE+5-1)其中MAX_INLINE_DATA的计算方法在3.1节中已经说明，此处不再赘述。对于INLINE_DATA_OFFSET，为方便定义，内联数据的地址偏移从索引节点块底部开始计算，PAGE_CACHE_SIZE即为1024，根据图3.1所示，底部为node_footer，其上是5个直接间接节点索引号，再上面即是923个数据索引指针的地址，而偏移起始地址为i_addr1，因此定义即如上述代码所示。3.2.2 处理数据内联的关键函数在处理数据内联时，需要考虑的主要有内联数据的读写、内联数据的恢复以及当内联条件不满足时，将内联文件转化为普通文件等操作。主要涉及的函数在f2fs.h的头文件中声明。具体见代码清单3-6。代码清单3-6：+ inline int f2fs_has_inline_data(struct inode *);+ bool f2fs_may_inline(struct inode *);+ int f2fs_read_inline_data(struct inode *, struct page *)+ int