7.3古尔丹之眼:UBIFS文件系统设计

为flashmemory设计的文件系统要求异地更新。这是因为flashmemory在可写之前必须要先擦除,且擦除之前只能写一次。如果eraseblocks很小且可以快速擦除，那么可以将它们看作disksector，但是实际上不是那种情况。读出一个整块的eraseblock，擦除它，再回写更新的的数据，所花时间比单独在其它已经擦除了的不同的eraseblock更新数据长100倍。换句话说，对于一个小的updates，in-place比out-of-place更新时间长100倍。

out-of-place更新要求垃圾回收。当有数据out-of-place更新时，原来的eraseblocks就包含了有效数据和绝对数据（在别的地方已经更新）。这样到最后，文件系统将用完所有空的eraseblocks，以至于每个eraseblocks包括有效数据和绝对数据。为了在别的地方写新的数据，必须有一个eraseblock是空的以至于可以擦除和重新使用。确认包含许多绝对数据的eraseblock，移动有效数据其它eraseblock，这个过程叫垃圾回收(garbagecollection)。

垃圾回收提议node-structure的好处。为了能回收一块eraseblock，文件系统必须能确认存储在那的数据。这是文件系统面对的一般索引问题的矛盾。文件系统通常以一个文件名开始和必须找到属于这个文件的数据。垃圾回收可以开始于任何一个文件的数据且必须发现这个文件属于哪个文件。解决这个问题的一个方法是根据文件的数据存储元数据(metadata)。数据和元数据的组合称为一个节点(node)。每一个节点记录着其属于哪个文件和这个节点包含着什么数据。JIFFS2和UBIFS都是按照一个node-structured设计的，它使能它们的垃圾回收者直接读eraseblocks,决定哪些data需要移动，哪些要丢弃，根据实际情况去改变索引。

JIFFS2和UBIFS之间最大的不同就是UBIFS将索引存储在flash上，而JIFFS2存储在mainmemory中，当文件系统被挂载的时候，mainmemory将重新建立。JIFFS2这样就潜在地给自己最大尺寸放了一个限制，因为挂载时间和memory使用随着flash的大小线性增长。

UBIFS被特地的设计去克服这个限制。

不幸的是，存储索引在flash上是非常复制的，因为所以本身必须异地更新。当索引的一部分被异地更新，那么相关更新索引的任何其它部分也必须要被更新。然后，依次地，相关部分的部分必须被更新。这样看起来好像永无止境地更新下去，一个解决的办法就是使用wanderingtree。

对于UBIFSwandering tree,只有树上的叶子包含文件信息。他们是文件系统的有效节点。树的内部元素是索引节点（indexnodes）和包含相关的子节点。也就是说，一个node记录着它的子节点的位置。所以UBIFSwandering tree可以看成两个部分。顶部分由创建树结构的索引节点组成，底部分由指向实际数据的leafnode组成。顶部分可以简单地看作索引index。一个文件系统的更新过程由创建一个新的leafnode和添加node（或者代替原来的到wanderingtree）组成。为了能做到，父索引节点必须也要被代替，如此，父节点的父节点，一直到tree的根（root），都必须要被代替。要被代替的索引节点数等于树的高度。这里留下的问题就是怎么知道tree的根在哪里。在UBIFS中，根索引节点的位置存储在主节点（masternode）里。

主节点存储着所有flash上没有固定逻辑位置的结构的位置。主节点自身被重复写到logicaleraseblocks(LEBs) one and two.LEBs是UBI创建的一种抽象。UBI将physicaleraseblocks(PEBs)映射到LEBs，所以LEBsone andtwo可以是flash介质上的任何地方（严格来说是UBI设备），无论如何，UBI都记录着他们在哪里。两个eraseblocks被使用，是为了保证有两个masternode的拷贝。这个是为了恢复着想，因为有两种情况会导致主节点损坏或丢失。第一种情况就是当masternode正在被写入的时候突然断电；第二种情况是可能是flash介质自身损坏。对于第一种情况恢复是可以的因为先前的主节点还可以使用。对于第二种情况恢复是不可能的因为无法确定哪一个主节点是可靠的。在后者情况中，一个用户空间的有用的程序将会用到，用来分析所有介质上的节点和修复或重建损坏或丢失的nodes。有了两个主节点的拷贝，就可以知道发生了哪种情况，根据情况去回复。

LEBszero存储着超级块的节点。超级块包含着极少改变的文件系统的参数。比如说，flash的几何尺寸（eraseblock大小、数目等）存储在超级块中。到目前为止，只有一种超级块重写的情况，那就是当自动改变尺寸发生。UBIFS目前只有一个非常有限的能力去改变尺寸，只能当文件系统创建时改变到最大的尺寸。这个特性是需要的，因为flash分区的实际大小是不同的，因为有变化数量的坏块存在。所以当文件系统镜像通过mkfs.ubifs创建时，最大数量的eraseblock被指定，镜像在超级块中记录这个数值和被用的实际eraseblocks数量。当UBIFS被挂载到一个分区（实际上是一个UBI卷），如果卷中的eraseblock数量比记录在超级块中的大而比最大值（也记录在超级块中）小，那么ubifs自动改变大小以适应这个卷。

实际上在UBIFS中有6个areas，它们的位置当文件系统创建时候确定。前两个areas已经描述过了。LEB0是超级块区。超级块通常是偏移0，超级块被写入使用UBI的原子LEB改变的能力。下一个区域是主节点区，其占有了LEB1和LEB2。一般来说，这两个LEB包含着指定的data。主节点被写到每个LEB中连续不断的位置直到没有空间为止，在这个点，LEBs被unmapped，主节点被写入到0偏移的位置（自动使UBIFSmap一个擦除过的LEB）。注意，主节点LEBs不是同时被unmapped，因为那将会导致文件系统临时没有有效的主节点。其它的UBIFS区域是thelog area, the LEB properties tree(LPT)area, the orphan area 和the main area。

log是UBIFS日志的一部分。UBIFS使用日志的目的是为了减少对falshindex的更新频率。回忆一下，index组成了wanderingtree（只由indexnode组成）的顶部分，更新文件系统时，一个leafnode必须被添加或者替代到wanderingtree，还有所有的祖先索引节点根据情况地更新。这个将会非常没有效率的如果index被更新当每次leafnode被写入，因为多数相同的索引节点被反复地写入，尤其tree的头部。作为代替，UBIFS定义了一个日志，树叶节点被写到这个日志里但是不立即添加到flashindex中。注意在memory中的index被更新。定期地，当日志被认为差不多full，它将会被提交。提交过程由写新版本index和相符合的主节点。

日志的存在意味着当UBIFS被挂载时，on-flashindex已经过时。为了将它更新，日志中的页节点必须被读和重新索引。这个过程叫replay。注意，日志越大，replay花的时间越长，挂载UBIFS文件系统的时间也会越长。另一方面，一个大的日志很少被提交，这会是文件系统很有效率。日志的大小是mkfs.ubifs的一个参数，所以它可以被选择，以至于来满足文件系统的需要。无论怎么样，UBIFS默认不使用fastunmount选项，取而代之的是unmount前会运行一次提交。这样当文件系统再次被挂载时，日志几乎是空的，这确实使挂载非常快速。这是一个很好的权衡协调，因为提交过程本身一般是非常快的，只花费一点点时间。

注意提交过程不会从日志中移走leafnodes，而是日志移走。记录日志的地方是log的目的。log包含两种nodes。一个是提交开始节点（commitstart node），记录着一个提交已经开始。另一个节点是相关节点（referencenode），记录着组成余下的日志的主区域（mainarea）的LEB的数量。这些LEBs叫做芽（buds），所以日志由log和buds组成。log大小是有限的，可以认为是一个环形bufer。提交过后，记录着日志的先前位置的相关节点已经不再需要了，所以log的尾部被擦除，同时log的头部被延长。相对于commit-startnode记录提交的开始，masternode的写入表示提交的结束，因为主节点指向新的log的尾部。如果因为文件系统被不干净地卸载导致提交没有完成，然后replayprocess replays both the old and new journal。

由于几种情况使replayprocess变得复杂。第一种情况是leafnodes 必须按顺序replay。因为UBIFS使用一个多头日志（multiheadedjournal），写leafnodes顺序不是简单的跟log中涉及到的buderaseblocks的顺序一致。为了有序地排列leafnodes，每个nodes包含了一个64-bit序列号，该号在文件系统的活动期内会增加。Replay把日志中的所有leafnodes都读出来，然后把他们放到一个RB-tree中，这个RB-tree是按照序列号存储的。然后按顺序的压缩RB-tree，根据实际情况更新内存中的index。

第二个复杂情况就是replay必须管理删除和截断。有两种删除。节点删除跟文件和目录删除是一致的，目录项删除跟解开连接和重命名是一致的。在UBIFS中，inodes有一个一致的inodenode，inodenode记录了目录项连接号，更多地简单认为是连接数目。当一个inode被删除，一个连接数目为0的inodenode被写入到日志中。在这种复杂情况下，不是将那个leafnodes添加到index中，而是根据inode号沿着所有indexentries，将它移除。

如果删除目录项，一个目录项的节点被写到日志中，但是先前目录项涉及到的inode号被设为0。注意目录项中有inode号。一个是其父目录项的号，一个是其文件或子目录项的号。删除目录项是后者被设置为0。当replay处理一个inode号为0的目录项时，它将把那个目录项从index中移除。

截断，当然是改变文件的大小。事实上，截断既可以延长文件的长度又可以缩短文件的长度。对于UBIFS，延长文件的长度不需要特殊的控制。用文件系统的说法，延长文件的长度通过截断建立一个hole去延长，这个hole是不能被写入的，文件的这部分被假设为0。UBIFS不索引holes，也不存储任何对应于holes的nodes。代替一个hole是indexentry。当UBIFS寻找index，发现没有indexentry，那么它将定义为hole，并创建0数据。另外一方面，缩短文件长度的截断要求新文件长度以外的datanodes要从index中移除。为了这种情况发生，截断节点被写到日志中，截断节点记录着老的和新的文件长度。Replay通过一致的indexentry处理这些节点。

第三个复杂情况是repaly必须使LEBproperties tree(LPT)区更新。LEBproperties是三个对于mainarea的所有LEB要知道的值。这些值分别是：剩余空间，脏空间和该eraseblock是否是indexeraseblock。注意indexnodes和 non-indexnodes永远不在同一块eraseblock中，因此一个indexeraseblock只包含indexnodes，一个non-indexeraseblock也只包含non-indexnodes.剩余空间是指到eraseblock的结尾还没被写，还可以填充更多的nodes的字节数。脏空间是指过时节点和填料（潜在可以被垃圾回收的）的字节数。对于发现空间加到日志或者索引，对于发现最脏的eraseblock去垃圾回收，LEBproperties是必要的。每当一个节点被写入，那个eraseblock剩余空间就会被减少。每当一个节点过时或者填料节点被写入或者一个截断（或删除）节点被写入，那个eraseblock的脏空间会增加。当一个eraseblock被申请为index，那必须要记录一下。例如，一个有剩余空间的indexeraseblock没有被申请到日志，那么它将会导致index和non-indexnodes混合于一个eraseblock。后面预算章节将会进一步讲述index和non-indexnodes不能混合的理由。

一般来说，index子系统自己负责通知LEBproperties子系统LEBproperties改变。在replay中LEBproperties增加的复杂度发生在当一个垃圾回收的eraseblock添加到日志中。像索引一样，LPT区域只有提交时才能被更新。和所以一样，on-flashLPT在挂载时已经过时，必须通过replayprocess更新。所以on-flashLEB properties只反映出最后一次提交的状态。Replay将开始更新LEBproperties,无论有的改变发生在垃圾回收之前还是在垃圾回收之后。根据垃圾回收点的不同，最终的LEBproperty的值将会是不同的。为了控制这个，replay插入一个涉及到它的RB-tree去描绘LEB添加到日志时候的点。这使replay能正确地适应LEBproperty值当RB-tree被应用到index中。

第四个复杂情况是恢复的效果。UBIFS记录着主节点无论文件系统是否被干净地卸载。如果不是干净的，某个错误条件翻转recovery，使之适应文件系统。replay被两种情况影响。第一，一个buderaseblock可能损坏，因为它正在写的时候被不干净地卸载了。第二，同样理由，logeraseblock也可能被损坏。replay通过这个eraseblock到recovery试图适应这些nodes在这些eraseblocks中来处理这些情况。如果文件系统被挂载成可读写，那么recovery将做一些必要的fixes。在这中情况下，完整的被恢复的UBIFS文件系统和没有遭遇过不干净卸载一样的完美。如果文件系统被挂载成只读，恢复将会被延期直到文件系统被挂载成可读写。

最后一个复杂情况是有些相关的leafnodes可能已经不存在了。这个发生在当nodes已经被删除，包含它的eraseblock随后已经被垃圾回收了。一般来说，已删除的leafnodes不会影响replay,因为它们不是index的一部分。不管怎么样，index结构一方面要求leafnodes有时候被读以更新index。这个发生是因为目录项nodes（扩展的属性项nodes）。在UBIFS中，一个目录由一个inodenode和一个目录项结构组成。通向index是一个nodekey，它是一个确认node的64-bit的值。在大多数情况下，这个nodekey唯一确认这个node，所以index被更新用的就是这个key。不幸的是，目录项的指定信息是名字，它是一个很长的字符（在ubifs中达到255个字符）。为了将该信息挤到64-bit中，它的名字被hash到一个29-bit的值中，这个不是唯一地对于名字。当两个名字给出来相同的hash值，这叫哈希相撞（hashcollision）。在这种情况下，leafnodes必须被读出来，通过比较存储在leafnodes中的名字来解决相撞。所以如果因为上述原因，leafnodes将会发生什么，这个不会太糟糕。目录项节点曾经被添加和移除，他们永远也不会被代替，因为他们包含的信息永远不改变。当增加一个hashkey节点，将不会有匹配。当移除一个hashed-key节点，通常会有一个匹配无论是已经存在的node或者对一个有正确key丢掉的node。为了提供这个特殊的索引更新replay，一个独立设置的功能被使用。

Log区后面是LPTarea。log区的大小当文件系统被创建的时候定义创建的，也就是顺序地就是LPT区的开始。目前，LPT区的大小是基于LEB大小和当文件系统创建时指定的最大的LEB数目自动计算的。和log区一样，LPT区必须永不超出空间。不像log区是，LPT区更新不是自然顺序的，他们是随机的。另外，LEBproperties 数据的数量潜在地非常巨大的，通过它必须是可量的。解决方法是存储LEBproperties 到一个wanderingtree。实际上LPT区非常像一个微型的文件系统。它有自己的LEBproperties，那就是LEBproperties 区的LEBproperties（称着ltab）。它有自己的垃圾回收。它有自己的节点结构。无论如何，和index一样，LPT区只在提交时更新。因此on-flashindex和on-flashLPT描绘最后一次提交文件系统是什么样的。和文件系统的实际状态不同点被日志中的节点描述。

LPT实际上有两个稍微不同的形式，称为小模式和大模式。当整个LEBproperties table可以写到一个eraseblock，小模式被使用。在那种情况下，LPT垃圾回收就是写整个表，这因此导致所以其他LPT区eraseblocks可重复使用。在大模式下，脏LPTeraseblocks被选择为垃圾回收，由记录LEB的节点脏和写脏节点组成。当然，在大模式下，LEB号的表被存储以至于当UBIFS第一次挂载时，寻找空eraseblock不会搜寻整个LPT。在小模式，它是假设搜寻整个表不是很慢的，因为它很小。

UBIFS的一个主要任务是通向index，它是一个wanderingtree。为了使其更有效，indexnodes被缓存在内存中一个叫treenode cache(TNC)的结构里。TNC是一个B+tree，和on-flashindex相同的node fornode,添加自从上次以来的所有改动。TNC的nodes称为znodes。另外一种看法是一个znode，当on-flash被称为一个indexnode，一个indexnode在内存中称为一个znode。最初是没有znode的。当在index上搜寻时，indexnodes需要读出来，将他们当作znodes添加到TNC。当一个znode需要改变，就将其标记为脏放在内存中直到下一次提交它又再一次变为干净。在任何时候，UBIFS内存shrinker可能决定释放TNC中的干净的znodes，以至于大量需要的内存和部分使用的index大小相称，注意是全部大小。另外，放开TNC的底部是一个leafnodecache(LNC),它是只用来为目录项的。LNC需要缓存被读的节点是碰撞解决或是目录读操作的结果。因为LNC依附于TNC，这个有效地得到收缩（shrink）当TNC做此操作时。

进一步描述TNC复杂性使提交和其它UBIFS操作产生尽可能少的冲突。为了做这个，提交被分成两个主要部分。第一个部分叫提交开始（commitstart）。在提交开始期间，提交写信号量down，这防止期间对日志的更新。在这期间，TNC子系统产生很多脏的znodes和找到他们将被写入flash的位置。然后提交释放信号量，一个新的日志开始被使用，同时提交的过程在继续。第二部分叫提交结束（commitend）。在提交结束期间，TNC写新的indexnodes，但是不带任何锁（即类似前面的信号量）的。也就是TNC可以被更新同时新的index可以被写到flash中。这是通过标记znodes完成的，称为copy-on-write。如果一个znode提交时需要被改变，那么将拷贝一份，以至于提交看到的仍然是没改变的znode。另外，提交是UBIFS的后台线程运行的，这样用户进程对于提交的只需等待尽可能少的时间。

接下来LPT和TNC采用了相同的提交策略，他们都是B+tree组成的wanderingtrees。这导致了代码方面很多的相似性。

UBIFS和JFFS2之间有三个重要的不同点。第一个已经提到过了：UBIFS有on-flashindex而JFFS2没有。第二个不同点是暗含的：UBIFS运行在UBI层（运行在MTD层）上的，而JFFS2直接运行在MTD层。UBIFS得益于UBI的损益平衡和错误管理，这些占用的flash空间、内存和其它资源都是有UBI分配。第三个重要的不同点是UBIFS允许回写（writeback）.

Writeback是VFS的一个特征，它允许写data到缓存中不立即写到介质中。这是系统更好潜在地更有效，因为对同一个文件的更新可以一块分组。支持writeback的困难是这个要求文件系统知道有多少剩余空间是有效的以至于缓存永远不要大于介质的空间。对于UBIFS，这点是非常困难决定的，所以一个整个称为预算（budgeting）的子系统专门做这个事情。困难有好几个理由。

第一个理由就是UBIFS支持透明的压缩。因为压缩的数量是不知道的，需要的空间的数量是不知道的。预算必须假设最糟的情况，假设没有压缩。无论怎么样，多数情况下是一个不好的假设。为了克服这个，当察觉到空间不足时预算开始强制回写。

第二个理由是垃圾回收不保证能收回所有的脏空间。UBIFS垃圾回收一次处理一个eraseblock。如果是NANDflash，只有完整的NAND页可以写。一个NANDeraseblock由固定数量的nandpages组成。UBIFS称nandpage大小为最小的I/O单元。因为UBIFS一次处理一个eraseblock，如果脏空间少于最小的I/O大小，它是不能被回收的，它将以填料结束。当一个eraseblock的脏空间少于最小I/O大小，那个空间称为死区（deadspace）。死区是不回收的。

类似于死区，还有一个叫暗区（darkspace）。暗区是一个eraseblock的脏空间少于最小node大小。最坏的情况，文件系统满是最大大小的nodes，垃圾回收将没有结果在多片剩余空间。所以在最坏的情况下，暗区是不回收的。在最好的情况下，它是可以回收的。UBIFS预算必须假设最坏的情况，所以死区和暗区都被假设为无效的。无论如何，如果有不充足的空间，但是有很多暗区，预算自身运行垃圾回收看是否能释放更的空间。

第三个理由是缓冲数据可能是存储在flash上的过时数据。是否是这种情况通常是不知道的，压缩中有什么不同点一般也是不知道的。预算强制回写当它计算不充足空间时。只有试着回写、垃圾回收和提交日志后，预算将放弃并返回ENOSPC（没有空间错误码）。

当然，那就意味着当文件系统接近满时，UBIFS将变得很无效。实际上，所有falsh文件系统都是这样。

第四个理由是删除和截断需要写新节点。因此如果文件系统真的没空间了，它将不可能删除任何东西的因为已经没有空间来写删除节点的节点或者截断节点了。为了防止这种情况，UBIFS经常保留一些空间，允许删除和截断。

下一个UBIFS区是孤立区（orphanarea）。一个orphan是一个节点号，该节点号的节点的节点已经被提交到index，但link数为0。这个发生在当一个打开的文件被删除，然后允许了提交。正常情况下，该inode应该被删除当文件被关闭的时候。无论如何，在不干净卸载的情况下，orphans需要被记录。不干净卸载后，无论是搜寻整个index还是保持一个list在flash的某处，orphans'inodes必须被删除。

孤立区是一个固定数量的LEBs，位于LPTarea和mainarea。孤立区LEBs的数量当文件系统创建时指定。最小数量是1。孤立区的大小可以适应在一个LEB中：(leb_size-32)/8

例如，一个15872字节的LEB可以适应1980个orphans所以一个LEB已经足够了。

orphans被累积在一个RB-tree。当节点的link数变为0，这个inode号被添加到这个RB-tree。当inode被删除，它将从tree中移除。当提交运行时，任何orphans树中新orphans被写到orphan区。如果orphan区已经满，空间将被扩大。通常会有足够大的空间的因为通常会防止用户创建多于允许的最大数目的orphans。

最后一个UBIFS区是主存储区（mainarea）。Mainarea包含由文件系统数据和index组成的节点。一个mainarea LEB可能是一个indexeraseblock或者是一个non-indexeraseblock。一个non-indexeraseblock可能是一个芽或者已经被提交。一个芽可能是当前日志头中的一个。一个包含提交节点LEB仍然可以变成一个芽如果它还有剩余空间。因此一个芽LEB从日志开始的地方有一个偏移，尽管偏移通常为0。