UBIFS闪存文件系统分析与研究

鞠高明　俞建新

摘要：该文详细介绍了无序区块映像文件系统（Ubifs）三个组成模块，并对其中使用的垃圾回收和损耗均衡算法做了深入分析。同时介绍了一个新特性：快速映射。随后对快速映射进行实验分析，证明快速映射的确可以大幅降低挂载时间。

关键词： UBIFS；UBI；快速映射；垃圾回收；损耗均衡

中图分类号：TP334 文献标识码：A 文章编号：1009-3044（2014）04-0749-06

闪速存储器（Flash Memory）是一种非易失性存储器，简称闪存。闪存的不易挥发性、抗震性、灵活性、低功耗以及高速的读写速度等特点使之常用于嵌入式平台和移动计算机。现在有两种主流的闪存，分别是NOR型和NAND型。NOR型和NAND型闪存的主要差别之一是IO接口不同。NOR型闪存采用总线接口，允许随机读写任意位置的存储数据。NAND型闪存采用多路复用的IO接口，串行地存取数据，它虽然能以字节或字为单位寻址，但最小存取单元是页（Page）。NAND型闪存的擦除操作以块（block）为最小单位进行，一个块又由若干页构成。NAND型闪存有三个主要物理特性：页块结构、先擦后写、擦除限制。页块结构使得闪存文件系统的数据访问管理围绕（Erase Blocks，简称EB）擦除块展开；先擦后写使闪存文件系统需要支持异步更新（out of update），因为一般擦除一个块的时间是写一个块的时间的100倍[5]；擦除次数限制使得闪存文件系统必须使用损耗均衡算法，力求做到各个块擦除次数基本差不多，实现延长闪存寿命。

NAND型闪存具有擦除速度快、批量写入速度快、容量大等优点，所以NAND型闪存具有更加广泛的应用前景。UBIFS闪存文件系统主要用于NAND型闪存。

目前Linux系统中使用闪存的方法主要有两种：

1）采用闪存转化层（Flash Translation Layer，FTL）。主要思想是通过该层将闪存硬件模拟成普通磁盘文件。

2）采用闪存文件系统，如JFFS2、YAFFS2、UBIFS等。闪存文件系统管理通过硬件驱动直接管理闪存。

闪存文件系统层次结构图如图1所示[4]。

由于采用FTL加传统磁盘文件系统这种设计方法增加了中间转换环节，工作效率低，并且不能发挥闪存固有优势，所以开发了专门面向闪存的文件系统。具有代表性的文件系统有Cramfs、YAFFS/YAFFS2、JFFS/JFFS2、UBIFS等。面向Linux的闪存文件系统绝大部分都是基于日志结构文件系统设计。日志结构文件系统并不采用本地更新的方式，而是采用异步更新的方式，即当某个数据块需要更新时，先找一个新块将新数据写入，再将旧块擦除。不过旧数据并不马上在闪存中擦除，而是以日志方式作为历史记录保存下来，这为文件系统的恢复操作打下了基础。

从图1中可以看出一般的闪存文件系统都是建立在MTD层的基础上，UBIFS是建立在UBI层的基础上，这是一种比较好的数据抽象方式。UBIFS模块包含不易变化运作空间的代码。回写、垃圾回收、日志等都属于这部分；UBI模块包含了未来可能会变化运作空间的代码和对下层MTD的封装。损耗均衡等属于易变化部分，坏块管理等属于对下层MTD的封装。

从图1中可以看出UBIFS主要与三大模块相关：UBIFS、UBI、MTD。MTD层主要是面向物理擦除块（Physical Erase Block，PEB），UBI模块抽象出逻辑擦除块（Logical Erase Block，LEB），并且UBI模块封装管理LEB到PEB的映射，这样UBI上层模块（UBIFS）只需要使用LEB，而不需要关心PEB。该文源码分析对象是Linux3.8.8内核。UBIFS模块相关代码集中在fs/ubifs目录下[6]，UBI模块相关代码集中在drivers/mtd/ubi目录下，而MTD模块相关代码集中在drivers/mtd目录下。

1 UBIFS简介

UBIFS（Unsorted Block Image File System，无序区块映像文件系统）是Linux上正在研发的新一代闪存文件系统，目前由Nokia公司和匈牙利赛格德大学（Szeged University）共同开发，UBIFS是JFFS2的后继闪存文件系统，有代替JSSF2的趋势。UBIFS的出现主要是解决JFFS2文件系统存在的挂载时间长、内存消耗大、可扩展性差、损耗均衡处理能力差等问题。JFFS2的挂载时间是跟Flash大小成线性比的，UBIFS克服了这一弱点（UBI子模块挂载时间还是与Flash大小成线性比的）。

UBIFS与JFFS2有三个主要的区别：JFFS2将索引（inode）存储在RAM上，UBIFS将索引存储在Flash上；JFFS2运行在MTD设备层之上，UBIFS运行在UBI层的基础上；JFFS2不支持回写，UBIFS支持回写（write-back）。

总的来说，UBIFS文件系统具有如下特点：

1）可扩展性强。UBIFS挂载时间、内存消耗以及I/O速度不依赖与Flash大小。当后续需要修改UBIFS闪存文件系统时，只需要修改UBI模块即可。

2）挂载速度快。不同于JFFS2，UBIFS在挂载阶段不需要扫描整个文件系统，挂载时间是毫秒级的。

3）回写。回写显著地提高了文件系统的吞吐量。

4）异常恢复。即使不干净（unclean）重启或者掉电，UBIFS文件系统都可以恢复。

5）快速I/O技术。即使禁用回写，UBIFS的I/O性能也接近JFFS2。

6）灵活的压缩技术。UBIFS可以对单个文件打开、关闭压缩功能。

7）可恢复性。如果文件系统索引信息被破坏，UBIFS可以通过扫描整个闪存来恢复文件系统。

8）完整性。UBIFS通过将校验和写到Flash介质来保证数据的完整性。

2 MTD简介

MTD（Memory Technology Device，内存技术设备）是用于访问存储设备（ROM、Flash）的Linux硬件抽象，它隐藏了Flash的许多硬件特性，为上层提供一个统一的抽象接口。MTD是一组底层驱动的集合，它抽象出文件系统所需的接口函数[6]，包括闪存物理块的读、写、擦除等操作，即mtd_read（）、mtd_write（）、mtd_erase（）等。一般而言，MTD代码由各个具体的Flash芯片生产商编写和提供。

MTD层提供了对擦除块的读写、擦除、判断是否为坏块、对坏块进行标记等功能。不过MTD并不对上层隐藏坏块信息，MTD只是将坏块进行标记。同时MTD不对擦除块做任何损耗均衡处理。

3 UBI模块

UBI（ Unsorted Block Images）是工作在MTD之上的卷管理系统，它管理Flash设备上的多个逻辑卷，并能够将I/O负载均匀的分布到Flash上。一个UBI卷，就是由一组连续的LEB组成的。

UBI模块功能主要是如下：

1）提供对Flash的卷式管理，包括管理PEB到LEB的映射管理。

2）对上层隐藏坏的擦除块，1%的PEB将保留作为UBI坏块管理使用，如果一个PEB变成坏块，相应的LEB就会被重新映射到另一个PEB。

3）提供对擦除块的损耗均衡处理。

4）使位反转造成的数据丢失的概率降低最低，UBI使用ECC（Error Correcting Code）处理位反转。

5）UBI对掉电情况进行处理，包括复制卷表，自动更换LEB，检验要写入Flash的数据。

3.1 UBI模块中重要数据结构

1）UBI卷

UBI卷类似于MTD的分区，都是用来存放文件系统数据的容器，支持读、写、擦除。和MTD不同的是，UBI卷由LEB组成，而MTD分区由PEB组成。

UBI卷根据数据类型可分为静态卷和动态卷，静态卷是只读的，由CRC-32校验和保护；动态卷是可读写的，该数据完整性由上层负责。根据用途，UBI卷可分为用户卷和内部卷，内部卷外部不可见，仅供UBI内部使用，现在UBI中只有一个内部卷：布局（layout）卷，其余都是用户卷。

2）PEB头部

UBI模块在每个PEB的起始区域存放了两个大小为64字节的头部信息：ECH（Erase Count Header，擦除计数头）、VIDH（Volume IDentifier Header，卷ID头）。UBI使用CRC-32校验和保护这两个头。其中ECH保存PEB擦除次数，VIDH保存PEB所属的卷ID号、卷类型等信息。

3.2 UBI中的表

UBI模块需要管理三张表：

1） volume表：包含每个卷信息，比如卷的大小、卷更新标记、卷号等。

2） EBA（Erase Block Association，擦除块关联）表：EBA表包含所有LEB到PEB的映射信息。

3）EC（Erase Counter，擦除计数）表：EC表包含着每一个PEB的擦写次数。

volume表维护在Flash上，volume表存储在前面提到的layout内卷中，layout内卷包含两个LEB，每个LEB都包含一份volume表。volume表仅仅在UBI卷被创建、删除和重定义大小时改变。

EBA和EC表是在每次挂载MTD设备时建立，这意味着UBI必须扫描整个Flash，从每个PEB读取VID和EC头部以构造EBA和EC表。相对于volume表，EBA和EC表变动较大，因为每次对PEB写时都有可能修改表。每个UBI卷都有一个EBA表，用eba_tbl结构表示。

对EBA表最重要的操作是map和unmap， map过程是首先找到相应的PEB，然后将VID头写入PEB，然后修改内存中相应的EBA表。unmap首先解除LEB与相应PEB的映射，然后调度擦除该PEB，unmap并不会等到擦除完成，该擦除由UBI后台进程负责。

3.3 损耗均衡

损耗均衡（wear-leveling，简称WL）指的是Flash中的各个擦除块在整个寿命周期内得到平衡的使用，而不会出现部分擦除块寿命耗尽而其余擦除块尚未的到充分使用的情况。

可以根据数据类型将损耗均衡分为静态损耗均衡和动态损耗均衡，静态损耗均衡对象是Flash上的静态数据，如文件系统、操作系统镜像等；动态损耗均衡对象是Flash上的动态数据。

内核使用的损耗均衡主要原理是：将擦除次数较少的used PEB中的数据搬移到擦除次数较多的free PEB中，从而平衡所有PEB的擦除次数。

损耗均衡模块工作的对象是PEB，它并不关心上层的逻辑卷和LEB，所有UBIFS系统上的PEB管理都交给了该模块。损耗均衡模块将PEB分为两类：used、free。损耗均衡模块使用ubi_wl_entry结构体对PEB重新封装，主要是加入擦除计数值，并将该PEB加入到红黑树中。损耗均衡红黑树分为以下四种类型[2]：

1）用free红黑树组织空闲的PEB；

2）用used红黑树组织含有效数据的PEB；

3）用scrub红黑树组织出现位反转的PEB；

4）用erroneous红黑树组织错误使用的PEB。

损耗均衡模块核心函数是wear_leveling_worker（），该函数主要是选择磨损均衡操作的源PEB和目的PEB，将源块的有效数据复制到目的块，并更新LEB和PEB之间的关系，然后源块可成为可用的free PEB。主要步骤如下[1]：

①如果srub红黑树不为空，则选择一个出现位反转的块作为源块，并从free红黑树中选择擦除次数较多的擦除块作为目的擦除块，然后进行磨损均衡操作。因为出现位反转的块急需通过擦除操作来恢复，所以此时不检查两个块EC的差值是否超过阀值。

②如果①条件不满足，则从used红黑树中选择擦除次数最少的擦除块作为源擦除块，从free红黑树中选择擦除次数较多的擦除块作为目的擦除块，比较这两个擦除块的EC的差值是否大幅预设的阀值，如果超过，则进行磨损均衡操作，否则退出。

③检查源擦除块的VIDH信息，如果VIDH不存在，则表示其他线程已经将该擦除块插入used或scrub红黑树还没来得及写入VIDH信息，处理方法是：将此擦除块插入保护队列中，然后结束磨损均衡操作。

④如果③检查VIDH完好，则将源擦除块的VIDH信息和用户有效数据搬移到目的块，然后更新EBA表。

⑤如果数据搬移成功，则将目的块插入used红黑树，然后申请源块的擦除操作。

3.4 快速映射

UBI快速映射（fastmap）是一个可选特性，从Linux3.7开始加入内核。快速映射主要思想：将UBI抽象的卷分成引用（reference）卷和数据卷，引用卷存放在闪存的前面部分（前64个PEB中的某个），引用卷所在区域称为超级块，数据卷所在位置称为快速映射池（fastmap pool）。超级块包含快速映射池位置，快速映射池中包含所有闪存物理信息和所以压缩的PEB头部（ECH和VIDH）。

快速映射池使用闪存上已删除的卷，所以并不会与之前的源码发生冲突。快速映射中包含所有挂载时需要的信息，如每个PEB擦除计数值、PEB状态、所有卷的状态等。快速映射池中包含了在挂载时可能需要修改的PEB以及需要扫描全部空间的PEB（一般的PEB只需要扫描头部）。一般快速映射池占所有闪存空间的5%，未来可能只需要一个PEB就可以装下整个快速映射模块。

UBI运行过程中可能会对快速映射模块进行修改，如快速映射池满、UBI卸载、EBA表变动等情况。加载了快速映射挂载UBI时，需要保证没有修改EBA表的I/O操作，该保护机制可能会花费掉一秒时间，所以快速映射在小容量的闪存上不具有优势。一般闪存容量越大，快速映射加速效果越明显。

目前UBI模块挂载过程：首先尝试寻找超级块（引用卷所在PEB），如果没有找到，则使用传统方法，扫描整个闪存；如果找到，则扫描超级块指向的快速映射池中的PEB即可。详情见图2 快速映射下UBI挂载时需要扫描的部分。

3.5 坏块管理

UBI在两种情况下标记PEB为坏块：

①写PEB失败，此时，UBI把这个PEB的数据搬移到其他的PEB，然后诊断该PEB是否出现为坏块，如果是，标记为坏块。

②擦除操作出现I/O错误，在这种情况下，直接把PEB标记为坏块。

4 UBIFS模块

UBIFS模块运行在UBI模块之上，即UBIFS面向的是LEBs，该模块涉及到PEB部分都会下放给UBI模块。

UBIFS模块功能主要有如下几点：灵活的压缩技术、回写（write-back）、日志（journal）、TNC（Tree Node Cache）、LPT（LEB Properties Tree）、大块读（bulk-read）。

前面介绍过，UBIFS的索引节点是存放在Flash上的，这样做的好处是可以很容易恢复文件系统，但同时也带来了问题。假设某PEB p1索引存放在PEB p2中，同时p2的索引在p3中，当修改p1就需要修改p2，当修改p2就需要修改p3，这可能会无穷无尽的修改下去。为了解决这个问题，使用B+树存放索引节点，该B+树中叶子节点存放数据，内节点都是索引信息，当修改叶子节点时只需要更新该B+树高度次即可。当然一次性写这么多次Flash是比较低效的，这个问题主要通过TNC（Tree Node Cache）解决，TNC是存放在RAM中的索引树，当需要修改索引树时，只是在TNC中做标记，然后再一次性写入Flash中。TNC同时还方便了对索引节点的读取，不需要从Flash中读取数据。UBIFS的索引号是不能复用的，即如果删除了索引号为100的文件，整个文件系统周期不能使用该索引号。在Flash中的索引节点在TNC树中称为znode。

因为UBIFS模块面向的是LEB，所以该模块有很多对LEB的操作，如读、写、申请LEB、回收LEB等。这些操作都建立在LEB属性的基础上。LEB属性包括LEB类型（索引或者数据）、dirty空间大小、free空间的大小。UBIFS使用链表结构管理LEB属性，分别为[6]：

1）用uncat_list链表管理未分类的LEB。

2）用empty_list链表管理空的LEB。

3）用freeable_list链表管理类型为数据的LEB。

4）用frdi_idx_list链表管理类型为索引的LEB。

LPT（LEB Properties Tree，LEB属性树）是以B+树形式管理LEB属性。使用B+树来管理LEB属性是为了提高对LEB属性操作的效率。LPT与索引树类似，只有叶子节点存放数据：LEB属性，与索引树不同的是，LPT中有三种节点：内节点、外节点、公共节点。

前面提过闪存文件系统基本都是基于日志文件系统的，UBIFS也不例外，当日志中内容达到一定程度时就需要将数据写回到到Flash，并修改主节点（主节点分区中的节点，具体见下节），这个过程称为commit（提交更新）。日志区就是记载上一次commit之后这一次commit之前这段时间中，操作了哪些LEB，这些LEB就称之为bud（芽）。

前面介绍过回写是UBIFS与JFFS2的三个主要区别之一，回写的好处很明显的，回写可以提高文件系统吞吐量，但是同时也带来了技术难题，即文件系统需要确认RAM中将要写入Flash的数据的大小不能超过空闲的闪存空间。UBIFS中的budget模块就是专门处理这个难题的。

4.1 UBIFS的分区

超级块分区（superblock area）使用LEB0。该区域保存文件系统配置相关信息，如：LEB大小、最大LEB数、日志区域占用的LEB数等。在UBIFS运行期间，超级块几乎不会改变，只有resize时才会导致超级块重写。之所以需要resize是因为创建UBIFS文件系统时，并不知道将要挂载的UBI卷的大小。

主节点分区（master area）使用LEB1和LEB2。主分区中包含两个主节点，主节点保存索引树根节点位置、为垃圾回收保留的LEB号、LPT管理的所有LEB脏空间总和等，

一般情况下，两个主节点保存着相同数据，主节点大小为512 byte，每次写入主节点会顺序地使用LEB的空闲页，直到没有空闲页时，再从偏移0开始写主节点，这时会重新映射LEB。不会同时重新映射两个主节点，因为这会导致文件系统没有有效主节点，如果此时掉电，系统无法找到有效主节点。

日志分区（journal area）从LEB3开始。为了降低节点的更新频率，UBIFS中创建了journal区，在其中缓存对节点的修改，然后一次写到Flash上去，这样就降低了更新的频率。当需要修改索引树叶节点时并不会马上更新闪存上的索引树，首先更新RAM中的TNC，同时将更新信息以日志方式记录在内存中，等到commit时再更新闪存上的索引树。

日志由log和bud组成。log记录日志位置，log包含两种类型的节点：commit开始节点、引用节点。commit开始节点记录commit过程的开始，引用节点记录bud的数量。

LEB属性树分区（LEB Properties Tree area，简称LPT area），跟随在日志之后，LPT的大小在创建文件系统时确定，LPT使用B+树结构。该区域除了包含LEB属性树外，还维护一张擦除块表LTAB（LPT area erase blocks）和一张LEB数量信息表LSAVE。LTAB是LPT所在LEB的属性组成的表，因为LPT分区只占一两个LEB，所以LTAB很小。

LPT有两种不同的表现方式：小模型、大模型[8]。当整个LEB属性表可以写在一个LEB上时，就使用小模型，垃圾回收时会重写整个表，这样所有其他擦除块都变得可用了。相反，对于大模型，就是整个LEB属性表不能写在一个LEB上时，垃圾回收时仅仅选择一个脏擦除块，并将该块上的干净数据标记为脏，然后将该块上的数据全部回写后擦除。

孤儿分区（orpan area）在log area和main area之间，使用固定数目的LEBs。一般来说，占用一个LEB，debug时会额外占用一个LEB。孤儿区域记录已经删除的文件的索引号，孤儿区域的作用是当擦除操作进行到一半，卸载了文件系统时，该区域可以在下次挂载文件系统时将孤儿索引找到并删除，UBIFS在孤儿区域中存储了一张表保存孤儿索引。

主分区（main area）是最后一个分区，存放文件系统数据和索引。

4.2 垃圾回收

因为Flash需要先擦除再写，所以闪存文件系统需要支持异步更新。如果不使用异步更新，每次对Flash块写的时候都需要先擦除，这就会增加大量读写时间。同时异步更新需要垃圾回收（garbage collection，简称GC）的支持。GC是一个回收无效块的过程（无效块中包含了一些无效数据），回收过程包括将有效数据移动到新块，然后擦除无效块从而使它变为可用。如果文件系统的可用空间较少，那么通常将在后台执行这一过程（或者根据需要执行）。

对于索引类型和数据类型的LEB，GC的处理方式区别较大。对应数据类型的LEB，GC找到一个脏数据很多的LEB，并将其中有效数据拷贝到日志，此时这个LEB就可以重新使用了；对应索引类型的LEB，GC在TNC中将该LEB有效的索引节点标记为脏，下一次commit（提交更新）之后该LEB就可以重新使用了[6]。

GC可能由日志或者budget调用。UBIFS对文件系统的每次更新都会先作用在日志模块上，类似函数ubifs_write_inode（）会调用ubifs_jnl_write_inode（）。所有日志模块的读、更新函数最后都会调用函数make_reservation（）预约日志空间，该函数首先调用函数reserve_space（），reserve_space（）首先会试着找free LEB，如果找不到就会调用ubifs_garbage_collect（）进行垃圾回收。类似的，budegt首先会调用函数ubifs_budget_space（）来确认是否有足够的空间，如果该函数觉得空余空间不够，会调用函数make_free_space（）产生新的空间，该函数会调用run_gc（）开始垃圾回收，run_gc（）则会调用ubifs_garbage_collect（）函数进行真正的垃圾回收，具体如图4所示。

图4 垃圾回收触发结构图

从上面分析可以看出GC核心部分就是函数ubifs_garbage_collect（），该函数主要步骤如下：

①首先检查是否需要commit（提交更新），当日志大小超过限制可能就需要commit，如果需要commit，则返回错误码给commit。

②检查在准备GC这段时间是否有空余LEB出现，即调用函数ubifs_find_dirty_leb（），它分别调用ubifs_fast_find_empty（）和ubifs_fast_find_freeable（）查找空的或者空余的LEB，如果有，则返回这个LEB，如果没有则返回脏空间最多的LEB。

③如果②中有返回，说明没有出现无脏LEB可回收的情况，此时ubifs_garbage_collect_leb（）会被调用，该函数用来回收一个LEB。

④函数 ubifs_garbage_collect_leb（）首先检查是否直接有一个空闲的LEB，如果有，则跳到⑥。

⑤扫描整个LEB，并将扫描结果放在相关结构中（ubifs_scan_leb和ubifs_scan_node）。如果扫描的节点是索引节点则ubifs_dirty_idx_node（）会被调用，将索引节点标记为脏；如果是数据节点则会调用move_nodes（）函数搬移节点。

⑥函数ubifs_garbage_collect_leb（）调用函数gc_sync_wbufs（）同步缓冲区，再调用ubifs_change_one_lp（）修改LEB属性，最后调用函数ubifs_leb_unmap（）卸载LEB。

⑦ubifs_garbage_collect（）最后同步自己的缓冲区，即调用ubifs_wbuf_sync_nolock（）函数。

函数ubifs_garbage_collect（）调用函数如图5所示。

5 实验结果

通过自编的脚本测试文件，利用精确到毫秒的系统时钟进行挂载时间测试，比较在不同大小闪存时，加载快速映射挂载UBI与不加载快速映射挂载UBI的时间。实验环境：

CPU：Intel（R） Core（TM） i7-2600，3.4G HZ。

Flash：使用nandsim模拟的闪存，页大小为2Mb。

内核版本：Linux3.8.8。

该实验结果如图6。

从图6可以看出加载快速映射的UBI模块挂载时间基本是固定的；不加载快速映射的UBI模块挂载时间与闪存大小成线性比。该实验证明快速映射确实可以减少UBI模块挂载时间。

参考文献：

[1] 樊进，江敏.UBI损耗均衡机制简析[J].电脑知识与技术，2010，6（25）：7125-7126.

[2] 韩春晓，陈香兰，李曦，等.UBIFS损耗均衡对系统I/O性能的影响[J].计算机工程，2009，35（6）：260-262.

[3] 韦斯，丁志刚，张伟宏. LINUX 下 UBI 子系统的研究与应用[J].计算机应用与软件，2010，27（10）： 69-72.

[4] Olivier P， Boukhobza J， Senn E. Micro-benchmarking Flash Memory File-System Wear leveling and Garbage Collection：a Focus on Initial State Impact [C]// Bob Werner.Computational Science and Engineering （CSE）. Proceedings of 2012 IEEE 15th International Conference， 2012：437-444.

[5] Adrian Hunter. A Brief Introduction to Design of UBIFS[EB/OL].http：//www.linux-mtd.infradead.org/doc/ubifs_whitepaper.pdf. 2008 March.

[6] Linux3.8.8 Source Code[EB/OL]. https：//www.kernel.org/pub/linux/kernel/v3.x/linux-3.8.8.tar.gz.