UBIFS文件系统设计(二)

原始英文文档a brief introduction to the design of UBIFS

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

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

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

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

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

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

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

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

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

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

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

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