一、Flash文件系统设计思路
为flash 设计的文件系统要求异地更新(out-of-place update)。这是因为flash在写之前必须要先擦除,且再次擦除之前只能写一次。如果擦除块(eraseblocks)很小且可以快速擦除,那么可以将它们看作磁盘扇区(disksector),但是实际上不是那种情况。读出一个整块的擦除块,擦除它,再回写更新的数据,所花时间比单独在其它已经擦除了的擦除块更新数据长100倍。换句话说,对于一个小的更新,在本地更新比异地更新更新时间长100倍。
异地更新要求垃圾回收(GarbageCollection)。当有数据异地更新时,原来的擦除块就可能同时包含有效数据和废弃数据(这些数据在别的地方已经更新)。这样到最后,文件系统将用完所有空的擦除块,以至于每个擦除块包括有效数据和废弃数据。为了在别的地方写新的数据,必须有一个擦除块是空的以至于可以擦除和重新使用。查找包含许多废弃数据的擦除块,并移动有效数据至其它擦除块,这个过程叫垃圾回收。
垃圾回收让我们想起节点结构的好处。为了能回收一块擦除块,文件系统必须能确认存储的数据。这是文件系统面对的一般索引问题的矛盾。文件系统通常以一个文件名开始和必须找到属于这个文件的数据。垃圾回收可以开始于任何数据且必须发现这些数据属于哪个文件。解决这个问题的一个方法是根据文件的数据存储元数据(metadata)。数据和元数据结合在一起称为一个节点(node)。每一个节点记录着其属于哪个文件和这个节点包含着什么数据。JFFS2和UBIFS都是按照一个节点结构设计的,节点结构使能它们的垃圾回收器直接读擦除块,决定哪些数据需要移动,哪些要丢弃,根据实际情况去改变索引。
二、UBIFS设计简介
JFFS2和UBIFS之间最大的不同就是UBIFS将索引存储在flash上,而JFFS2存储在内存中,当文件系统被挂载的时候,内存将重新建立索引。JFFS2这样就潜在地给自己最大尺寸做了一个限制,因为挂载时间和内存使用情况都随着flash的大小而线性增长,BUIFS就是被设计用来克服这个限制。
不幸的是,将索引存储在flash上是非常复杂的,因为索引本身也需要异地更新。当索引的一部分被异地更新,那么与更新的索引相关的其它部分索引也必须要更新。然后,依次地,相关部分的相关部分也必须被更新。这样看起来好像永无止境地更新下去,一个解决的办法就是使用游离树(wanderingtree)。
对于UBIFS,游离树(wanderingtree,实际上是一个B+树)只有树上的叶子包含文件信息。他们是文件系统的有效节点。树的内部元素是索引节点(indexnodes)并包含相关的子节点。也就是说,一个节点记录着它的子节点的位置。所以UBIFS的游离树可以看成两个部分。顶部分由创建树结构的索引节点组成,底部分由指向实际数据的叶子节点组成。顶部分可以简单地看作索引index。一个文件系统的更新过程由创建一个新的叶子节点和添加该节点到树上(或者代替原来的树中的节点)组成。之后,其父索引节点必须也要被代替,从而父节点的父节点,一直到树的根(root),都必须要被代替。要被代替的索引节点数等于树的高度。这里留下的问题就是怎么知道tree的根在哪里。在UBIFS中,根索引节点的位置存储在主节点(masternode)里。
2.1 主节点区
主节点存储着所有flash上没有固定逻辑位置的结构的位置。主节点自身被重复写到LEB1和LEB2(LEB,logicaleraseblocks逻辑擦除块)。LEBs是UBI创建的一种抽象。UBI将PEBs(physicaleraseblocks,物理擦除块)映射到LEBs,所以LEB1和LEB2可以是flash介质上的任何地方(严格来说是UBI设备),无论如何,UBI都记录着他们在哪里。两个擦除块被使用,是为了保证有两个主节点的拷贝。这个是为了恢复着想,因为有两种情况会导致主节点损坏或丢失。第一种情况就是当主节点正在被写入的时候突然断电;第二种情况是可能是flash介质自身损坏。对于第一种情况是可以的恢复,因为先前的主节点还可以使用。对于第二种情况是不能的恢复,因为无法确定哪一个主节点是可靠的。在后者情况中,将会用到一个用户空间的程序,用来分析所有介质上的节点并修复或重建损坏或丢失的节点。有了两个主节点的拷贝,就可以知道发生了哪种情况,根据情况去恢复。
2.2 超级块区
LEB0存储着超级块的节点。超级块包含着一些文件系统的极少改变的参数。比如说,flash的几何尺寸(擦除块大小、数目等)就存储在超级块中。到目前为止,只有一种情况需要重写超级块,那就是当发生自动改变尺寸。UBIFS目前只有一个非常有限的能力去改变尺寸,只能在文件系统创建时改变到最大的尺寸。这个特性是需要的,因为有不定数量的坏块导致flash分区的实际大小不同。所以当通过mkfs.ubifs创建文件系统镜像时,最大数量的擦除块需要被指定,镜像在超级块中记录这个最大数以及被实际使用的擦除块数量。当UBIFS被挂载到一个分区(实际上是一个UBI卷),如果卷中的擦除块数量比记录在超级块中的擦除块数大并比最大擦除块数(也记录在超级块中)小,那么ubifs自动改变大小以适应这个卷。
实际上在UBIFS中有6个区域,它们的位置在文件系统创建时候确定。前两个区域已经描述过了。LEB0是超级块区,超级块通常是偏移0,写超级块区时通常用的是LEB的原子修改功能,从而保证LEB要么成功修改要么未成功。下一个区域是主节点区,其占有了LEB1、LEB2。一般来说,这两个LEB包含着相同的数据。主节点通常被连续写到LEB直到该LEB写满,这时候,该LEBs被取消映射(unmap),主节点被写入到0偏移的位置(自动使UBIFS映射到一个擦除过的LEB)。注意,主节点LEBs不是同时被取消映射,因为那将会导致文件系统临时没有有效的主节点。其它的UBIFS区域是log日志区(thelog area),LPT区(the LEB properties tree area), 孤儿区(the orphanarea)和主存储区(the main area)。
2.3 log日志区
log是UBIFS日志的一部分。UBIFS使用日志的目的是为了减少对falsh索引的更新频率。回忆一下,索引组成了游离树的顶部分(只由索引节点组成),更新文件系统时,添加或者替代游离树中的一个叶子节点时,该叶子节点的所有祖先索引节点都需要根据情况更新。如果当每次叶子节点被写入索引都需要更新将会导致效率非常低下,因为多数相同的索引节点被反复地写入,尤其树的头部。所以,UBIFS定义了一个日志,叶子节点被写到这个日志里而不是立即添加到flash索引中。注意此时在内存中的索引需要更新(见TNC)。定期地,日志差不多满了,它将会被提交。提交过程包括写新的索引和主节点。
日志的存在意味着当UBIFS被挂载时,存在flash的索引已经过时。为了更新它,必须读日志中的叶子节点并重新索引。这个过程叫回放(replay)。注意,日志越大,回放花的时间越长,挂载UBIFS文件系统的时间也会越长。另一方面,一个大的日志很少被提交,这会使文件系统很有效率。日志的大小是mkfs.ubifs的一个参数,所以它可以被修改,从而满足文件系统的需要。无论怎么样,UBIFS默认不使用快速卸载(fastunmount)选项,取而代之的是卸载前会运行一次提交。这样,当文件系统再次被挂载时,日志几乎是空的,使挂载非常快速。这是一个很好的权衡协调,因为提交过程本身一般是非常快的,只花费一点点时间。
注意提交过程不是从日志中移走叶子节点,而是移动日志。log的目的就是记录日志的位置。log包含两种节点:一个是提交开始节点(commitstart node),记录着一个提交已经开始。另一个节点是相关节点(referencenode),记录着组成余下的日志的主存储区(mainarea)的LEB数量。这些LEBs叫做芽(buds),所以日志由log和芽组成。log的大小是有限的,可以认为是一个环形缓冲区。提交过后,记录着先前日志位置的相关节点已经不再需要了,所以log的尾部被擦除,同时log的头部被延长。相对于提交开始节点记录提交的开始,主节点的写入表示提交的结束,因为主节点指向新的log的尾部。如果因为文件系统被不干净地卸载导致提交没有完成,然后回放操作会回放老的和新的日志(从而使得日志一致)。
由于几种情况使回放操作变得复杂:
>>第一种情况是叶子节点必须按顺序回放。因为UBIFS使用一种多头日志(multiheadedjournal),写入叶子节点的顺序不是简单的跟log中涉及到的芽擦除块的顺序一致。为了给叶子节点排序,每个节点包含了一个64bit的序列号,该号在文件系统活动时会增加。回放把日志中的所有叶子节点都读出来,然后把他们放到一个红黑树中,这个红黑树是按照序列号存储的。之后会按顺序地处理红黑树,并实际情况更新内存中的索引。
>>第二个复杂情况就是回放必须管理删除和截断。有两种删除。Inode节点删除相当于删除文件和目录,以及目录项删除即删除连接和重命名。在UBIFS中,inodes有一个一致的inode节点,inode节点记录了目录项连接号,更多地简单认为是连接数目。当一个inode被删除,一个连接数目为0的inode节点被写入到日志中。在这种复杂情况下,不是将那个叶子节点添加到索引中,而是根据inode号沿着所有索引项,将它移除。如果删除目录项,一个目录项的节点被写到日志中,但是先前目录项涉及到的inode号被设为0。注意目录项中有两个inode号。一个是其父目录项的号,一个是其文件或子目录项的号。删除目录项是后者被设置为0。当回放处理一个inode号为0的目录项时,它会直接将那个目录项从索引中移除而不是添加。
截断即是改变文件的大小。事实上,截断既可以延长文件的长度又可以缩短文件的长度。对于UBIFS,延长文件的长度不需要特殊的控制。
用文件系统的说法,通过截断延长文件的长度会创建一个hole,这个hole在文件中是不能被写入的,而且是全0位。UBIFS不索引holes,也不存储任何对应于holes的节点。代替一个hole是不在那的索引项。当UBIFS寻找index,发现没有索引项,那么它将定义为hole,并创建0数据。另外一方面,缩短文件长度的截断需要将多余的节点从索引中移除。为了这种情况发生,截断节点被写到日志中,截断节点记录着老的和新的文件长度。回放通过删除相关的索引项处理这些节点。
>>第三个复杂情况是回放必须更新LPT区(LEB properties tree 逻辑擦除块属性树)。LEB属性是在主存储区中对于所有LEB都要知道三个值。这些值分别是:空闲空间,脏空间以及该擦除块是否是索引擦除块。注意索引节点和非索引节点永远不在同一块擦除块中,因此一个索引擦除块是一个只包含索引节点的擦除块,一个非索引擦除块也只包含非索引节点。空闲空间是指该擦除块的结尾还没被写还可以填充更多的节点的区域的字节数。脏空间是指废弃节点和填充的字节数,它们都是潜在可以被垃圾回收的。对于查找空闲空间用作日志或者索引,以及查找最脏的擦除块做垃圾回收,LEB属性是必要的。每写入一个节点,就会减少那个擦除块的空闲空间。每当废弃一个节点或者填充节点以及截断(或删除)节点时,那个擦除块的脏空间都需要增加。当一个擦除块被申请为索引擦除块,那必须要记录一下。例如,一个有空闲空间的索引擦除块就不会被申请用作日志,因为那样它将会导致索引和非索引节点混合在一个擦除块。后面预算章节将会进一步讲述索引节点和非索引节点不能混合的理由。
一般来说,索引子系统自己负责将其LEB属性改变通知LEB属性子系统。当一个回收过的擦除块被添加到日志后在回放时LEB属性的复杂度会增加。像索引一样,LPT区域只在提交时才被更新。和索引一样,存在flash上的LPT在挂载时已经过时,必须通过回放处理进行更新。所以flash上的LEB 属性反映的是最后一次提交时的状态。回放将开始更新LEB属性,虽然有的改变发生在垃圾回收之前有的在垃圾回收之后。
根据垃圾回收点的不同,最终的LEB属性的值将会是不同的。为了控制这个,回收插入一个引用到它的红黑树去描绘LEB添加到日志时候的点(使用log引用节点序列号)。当回放红黑树被应用到索引中时回放能正确地调整LEB属性值。
>>第四个复杂情况是回放时恢复的效果。UBIFS在主节点记录这文件系统是否被成功地卸载。如果是不干净的卸载(uncleanunmount),一定的错误条件会触发文件系统的恢复。回放被两种情况影响。第一,一个芽擦除块正在写的时候被不干净地卸载了,它可能损坏。第二,同样,log擦除块可能在写的时候被不干净地卸载导致被损坏。回放会通过恢复这个擦除块试图修复其中的节点来处理这些情况。如果文件系统被挂载成可读写,那么恢复将做一些必要的修复。在这种情况下,被恢复的UBIFS文件系统的完整性和没有遭遇过不干净卸载一样的完美。如果文件系统被挂载成只读,恢复将一直等到文件系统被挂载成可读写才做恢复。
>>最后一个复杂情况是索引中引用的相关的叶子节点可能已经不存在了。这个发生在当节点被删除而且它所在的擦除块随后被垃圾回收处理了。一般来说,已删除的叶子节点不会影响回放,因为它们不是索引的一部分。但是,索引结构一方面有时候更新索引时会读叶子节点。在UBIFS中,一个目录由一个inode节点和一个目录项组成。可以使用一个节点密钥(key)获得索引,密钥是一个64-bit的值来识别节点。在大多数情况下,这个节点密钥可以用来唯一确认这个节点,所以索引更新用的就是密钥。不幸的是,目录项的指定信息是名字,它是一个很长的字符(在ubifs中达到255个字符)。为了将该信息挤到64-bit中,它的名字被hash到一个29-bit的值中,这个对于名字不是唯一地。当两个名字给出来相同的hash值,这叫哈希冲突(hashcollision)。在这种情况下,叶子节点必须被读出来,通过比较存储在叶子节点中的名字来解决冲突。如果因为上述原因,叶子节点丢失将会发生什么?实际上这个不会太糟糕。目录项节点只会被添加和删除,它们永远不会被代替因为他们包含的信息永远不改变。当增加一个hash密钥节点,将不会有匹配。当移除一个hash密钥节点,通常会有一个匹配可能是已经存在的节点或者对一个有正确key丢掉的节点。为了提供更新这个特殊的索引用于回放,需要使用一个独立设置的功能(表示在代码的前缀“犯错”)。
2.4 LPT区
Log区后面是LPT区。log区的大小在文件系统被创建的时候被定义,也就是LPT区的开始在文件系统创建时也固定了(因为它就跟在log区后)。目前,LPT区的大小是基于在文件系统创建时指定的LEB大小以及最大的LEB数目自动计算的。和log区一样,LPT区也不超出空间。不像log区的是,LPT区的更新不是连续的,它们是随机的。另外,LEB属性数据的数量潜在地非常巨大的,而且它必须是可扩展的。
解决方法是存储LEB 属性到一个游离树。实际上LPT区非常像一个微型的文件系统。它有自己的LEB属性,那就是LEB 属性区的LEB属性(称为ltab)。它还有自己的垃圾回收。它有自己的节点结构--是一个很小的bit级别的。而且,和索引一样,LPT区只在提交时更新。因此flash上的索引和flash上的LPT描绘的是最后一次提交文件系统时的状况。
它和真正的文件系统的不同点是被日志中的节点描述。
LPT实际上有两个稍微不同的形式,称为小模式(small mode)和大模式(big model)。使用小模式时。整个LEB属性表可以写到一个擦除块。在那种情况下,LPT垃圾回收就是写整个表,这导致所有其他LPT区擦除块可重复使用。在大模式下,垃圾回收仅选用脏LPT擦除块,垃圾回首标记LEB的节点为脏并写脏节点。当然,在大模式下,会存储一个LEB数量的表之后UBIFS第一次挂载时,寻找空擦除块不会搜寻整个LPT。在小模式下,我们假设搜寻整个表不是很慢的,因为它很小。