SoftUpdates一项消除大多数同步写操作的技术(2)
作者及顾问：Marshall Kirk McKusick；卡内基梅隆大学 Gregory R. Ganger中文翻译：北京工业大学计算机学院李鑫 < delphij@cnfug.org >
--------------------------------------------------------------------------
这篇论文最初发表于1999年6月6日至11日举行的USENIX年度技术会议中，Freenix会议
录的第1-17页。其版权归Marshall Kirk McKusick和Greg Ganger所有，作者保留所有
权力。这篇论文在作者的许可下被翻译和重新发布。在保持此版权宣示完整的前提下，
允许对本文进行非商业目的的重新发布。
--------------------------------------------------------------------------
第3节 跟踪并确保更新依赖关系
本节描述BSD Soft Updates数据结构，以及它在保证第二节中描述的更新依赖关系中发挥的作用。这里描述的数据结构和算法能在除文件截断和fsync系统调用以外的所有情况中完全消除BSD FFS的同步写入操作。
SoftUpdates的关键特性是在缓存块中追踪每个更改之间的更新依赖关系。于是，对包括64个i-节点的块，系统可能会为缓冲区中的这些i-节点维护最多64个依赖关系结构。类似地，对包含50个名字的目录块，系统也会为这些名字维护最多50个依赖关系结构。
拥有如此详细的依赖关系信息，块之间的循环依赖将不再是问题。无论何时系统希望在缓冲区中写i-节点，它们都能安全地写入，并最终进入磁盘。一时不能安全写入的i-节点将在缓冲区同步时被暂时回滚到过去的某个安全的值，待写盘完成后再恢复当前值。缓冲区在回滚的这段时间被锁定，待内容恢复后再解锁。请求写缓冲区的进程将被阻塞，直到缓冲区恢复原状。
3.1 依赖关系数据结构
我们的实现使用了多种数据结构在文件系统结构中追踪未决的更新依赖关系。表1列了使用的依赖关系结构、主要功能，以及与它们关联的块。这些依赖依赖关系数据结构在文件操作完成时被分配并关联到块上。在内核内存中的副本中它们使用指针关联到对应块的头。所有列出的依赖关系结构的两种一般的样式是工作表(worklist)结构和保存追踪依赖关系状态的结构。
表1 BSD SoftUpdates实现中使用的依赖关系结构
worklist结构作为所有依赖关系结构首项的公共头。它包含了一系列连接指针，以及一个表示它被嵌入的结构类型的字段。worklist结构使得将不同类型的依赖关系结构连到同一链表中成为可能。SoftUpdates代码能够遍历这种异质链表，使用类型字段判别它遇到的依赖关系结构，并据此进行相应的操作。
对worklist的典型应用是将一系列依赖关系关联到缓冲区上。整个系统中的每个缓冲区都附加了一个worklist头指针。任何与缓冲区关联的更新依赖关系都被接到这个链表中。缓冲区锁定后，在写开始前，I/O系统把缓冲区送给相关代码，SoftUpdates从而得知将开始一次写操作并遍历关联到缓冲区上的依赖关系，以便进行适当的数据回滚。磁盘写入完成后，在解除对缓冲区的锁定之前，I/O子系统会再次调用SoftUpdates代码，告知写操作完成。这些代码将进行适当的前滚操作，释放已完成写入的那些依赖关系结构。
另一个SoftUpdates代码维护的表是tasklist，它指明了工作守护进程需要进行的后台任务。已经可以安全地写入，但由于某种原因(如锁或I/O)而被阻塞的那些依赖关系由写盘子程序追加到tasklist中来描述。每秒syncer守护进程都会被唤醒(这一进程也是SoftUpdates的工作进程)，它调用SoftUpdates代码以处理tasklist中的项目。在表中进行的操作与项目类型有关。例如，freeblks结构列出的块将在块位映射表中被标记为空闲；对dirrem结构，相关i-节点的引用计数将被减少，并可能触发文件删除操作。
依赖关系的状态。绝大多数依赖关系结构拥有一系列标志来描述相关关系的完成状态。被改动过的缓存块可能在任何时刻写入磁盘。I/O系统将缓冲区交给SoftUpdates程序(在磁盘写入之前和之后)时，与之关联的状态将确定将进行的操作。尽管不同的结构有不同意义的状态，但三个主要的、普适的状态是：
附着(ATTACHED)
此标志表示包含此依赖关系结构的缓冲区尚未被写盘。当包括必须回滚的依赖关系的缓冲区写盘之前，这一标志将被清零，以体现在缓冲区中的回滚。当写盘完成时，此标志被清零的那些依赖关系结构对应的缓冲区将恢复原状。所以，如果此标志复位，则绝不能释放对应的依赖关系，因为它包括需要进行恢复操作，此时释放将造成这些信息丢失。
依附更新已完成(DEPCOMPLETE)
此标志表示是否所有关联的依赖关系已完成。写盘开始前，如果此标志被复位，则依赖关系描述的更新应被回滚。例如，在与新分配的i-节点或数据块关联的依赖关系中这个标志被置位而相关的位映射表被写盘时。
完成(COMPLETE)
此标志表示当前依赖关系结构所追踪的所有更新都已经写盘。对某些依赖关系，此标志被复位时，则写入磁盘之前相关更新会回滚。例如，新分配的数据块写入完成时，这个标志将被置位。
最后，写盘完成，并且ATTACHED、DEPCOMPLETE和COMPLETE三个标志都被置位时，这个结构就可以释放了。考虑处理由allocdirect结构所追踪的新分配数据块的过程的例子。ATTACHED标志将在分配结构时作为初值置位。在反映这一情况的位映射表写盘之后，DEPCOMPLETE标志将置位，而COMPLETE标志将在新块内容写盘后被置位。如果声明这个块的i-节点的DEPCOMPLETE和COMPLETE标志中至少有一个没有被置位时系统发出同步请求，则ATTACHED标志将被复位并进行适当的回滚操作；i-节点写入之后，缓冲区数据将恢复。不同依赖关系中的不同标志将在后文描述。
3.2 追踪位映射表依赖关系
图1 描述了bmsafemap结构，它追踪位映射表更新。每个包含柱面组块的缓冲区都有自己的bmsafemap结构。和其他依赖关系结构一样，bmsafemap结构的第一项是一个worklist结构。当从柱面组中分配i-节点、直接块或间接块时，将创建一个相应的依赖关系结构，并连接到相应的bmsafemap表中。新分配的i-节点将由接到bmsafemap inodedep链表头指针的一个inodedep表示。类似地，直接、间接引用的新分块将分别通过接到bmsafemap上的allocdirect和allocindir表示。由于FFS代码的设计，块成功分配到代码的其余部分了解此情况有间隔。这段时间块将被一个连到bmsafemap newblk链表头指针的newblk结构描述。内核选定写入的柱面组块之后，SoftUpdates在写入完成时得到通知。它于是遍历i-节点和直接、间接块以及新分块链表，为每个依赖结构设置DEPCOMPLETE标志，并将依赖关系从表中删去。当所有的依赖关系表被清空之后，bmsafemap结构就可以被释放了。使用了多个表，因为这样更快，且能提供更好的类型-安全特性。
br>3.3 i-节点依赖关系追踪
我们将通过inodedep结构来追踪i-节点更新。基本上，worklist以及"状态"字段被用来描述依赖关系结构。"filesystem ptr[文件系统指针]"和"inode number[i-节点编号]"字段用来唯一标示i-节点。当新分配一个i-节点时，它的inodedep将被挂接到bmsafemap结构的"inodedep链表"上。在那里，"deps list[依赖关系列表]"将链接新的inodedeps以及指向柱面组块的"dep bp[依赖关系块指针]"。其它inodedep字段将在后续的小节中解释。
在详细介绍i-节点所关联的其他依赖关系之前，需要描述一下图3介绍的和更新i-节点有关的步骤。步骤1：内核调用vnode操作，VOP_UPDATE。这将产生通过适当的磁盘缓冲机制把i-节点驻留在磁盘上的部分(称为dinode)复制到内存中的vnode结构的请求。
这个磁盘缓冲保持整个盘块的内容。它通常足以保存64个dinode。某些依赖关系只有在i-节点被写盘后才被满足。对于这些关系，依赖关系结构需要追踪i-节点的写入过程。因此，在步骤1中，一个SoftUpdate例程， "softdep_update_inodeblock"将被调用，以从"incore update"表中把allocdirect结构移动到"buffer update"，以及把freefile, freeblks, freefrag, diradd, 或mkdir结构(后文介绍)从"inode wait"中移动到"buf wait"表中。步骤2：内核将调用vnode操作，VOP_STRATEGY，它将为写入包含指向dinode的bp指针的缓冲区做准备。SoftUpdate例程，"softdep_disk_io_initiation"，将识别inodedep依赖关系，并调用"initiate_write_inodeblock"以便作适当的回滚。步骤3：完成缓冲区输出之后系统将调用"biodone"，以通知等待的进程当前写入已经完成。"biodone"例程将随后调用SoftUpdate例程"softdep_disk_write_complete"，这一例程将识别inodedep依赖关系，并调用"handle_written_inodeblock"， 以便恢复回滚所做的操作，并清除"buf wait"和"buffer update"表中的依赖关系。
3.4 追踪直接块依赖关系
图4描绘了由直接块分配使用的依赖关系结构。考虑最关键的依赖关系：盘上的i-节点指向新分配的块之前，相关位映射表块
