作者及顾问：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-节点指向新分配的块之前，相关位映射表块以及新块本身都必须首先写入磁盘。
两个更新依赖关系的完成顺序并不重要。图4介绍了allocdirect结构，这一结构追踪直接被i-节点引用的块。其中的3个最近分配的逻辑块(1, 2和3)每一个都在不同的状态中。对于逻辑块1，位映射表依赖关系已经完成(如所示的那样，DEPCOMPLETE标志被置位)，但块本身还没有被写入(COMPLETE标志复位)。对于逻辑块2，两个依赖关系都已经完成。对于逻辑块3，两个依赖关系都没有完成，因而相关的allocdirect结构被附加到一个bmsafemap"allocdirect head"表(前面提到，这个表在位映射表写盘之后被遍历以设置DEPCOMPLETE标志)。逻辑块1和3的COMPLETE标志将在他们的初始化好的数据块被写入磁盘之后设置。图中也说明了逻辑块1存在于VOP_UPDATE被调用的时刻，这也是它的allocdirect结构驻留在inodedep "buffer update"表中的原因。逻辑块2和3在最近的那次VOP_UPDATE之后调用，因而它们的结构将驻留在inodedep"incore update"表中。对于缓慢增大的文件，直接块指针可能首先指向一个片断，而这个片断随后将升格为更大的片断，直到最终成为一个全长的块。当片断被更大的片断或全长块替换时，它必须被释放回文件系统。不过，旧块在新的片断或块的位映射表项、内容，以及声明它们的i-节点被写入之前不能被释放。将被释放的片断由一个freefrag结构描述(图未提及)。freefrag结构被保存在即将替换掉它的那个块的allocdirect结构中的"freefrag"表中，直到新块的对应位映射表项和内容都被写入完成。随后，结构被移动到在调用VOP_UPDATE时，进入"buf wait"表中的那个与它的allocdirect相关的那个inodedep的"inode wait"表中。当保存i-节点块的缓冲区被写入磁盘之后，freefrag结构最终被加入tasklist中。当轮到tasklist处理时，由freefrag结构列出的片断将被返还给空闲块位映射表。
3.5 间接块依赖关系追踪
图5体现了间接块分配时需要的更新依赖结构。其中也包括直接块相关的那些依赖关系。图中引入了两个新的依赖关系结构。一个单独的用于追踪每个独立的间接块指针的allocindir结构，管理所有与间接块相关的allocindir结构的indirdep结构。图中表示了一个刚刚分配了逻辑块14，15(第3和第4项，偏移量8和12，在第一间接块上)的文件。与逻辑块14相关的分配位映射表已经被写入磁盘(如图，它的DEPCOMPLETE已被置位)，但块15的还没有。因此，bmsafemap结构将追踪逻辑块15的allocindir结构。逻辑块15的内容已经被写入磁盘(如图，它的COMPLETE标志被置位)，而逻辑块14还没有。块14 allocindir结构的COMPLETE标志将在块被写入磁盘之后置位。 allocdir结构的表被indirdep结构追踪，这个表可能很长(对于一个8KB的间接块，最多可能有2048个项)。为了防止在I/O子程序中遍历如此长的依赖关系结构表，indirdep结构将维护两个间接块的副本："saved data ptr[已保存的数据指针]"指向缓冲区的最新副本，而"safe copy ptr[安全副本指针]"指向只包括可以被安全写入磁盘的指针子集(其他以NULL表现)。前一个用于所有的文件系统操作，而后一个则用来进行磁盘写入。当"allocindir head"表变为空时，"已保存数据指针"和"安全副本指针"将指向相同的块，而indirdep结构(以及安全副本)则可以释放了。
3.6 新间接块依赖关系追踪
图 6 表现了刚扩展到单级间接块的文件的相关依赖关系。这包括了inodedep和indirdep结构，用以管理i-节点和间接块的依赖结构，一个用于追踪间接块的分配的allocdirect结构，一个用于追踪间接块指向的新分块的allocindir结构。这些结构如前述的那样使用。间接块和数据块都不设置相应的位映射表项，因此他们的DEPCOMPLETE标志不被设置，也没有bmsafemap结构跟踪。i-节点的位映射表项被写入之后，inodedep结构的DEPCOMPLETE被设置。inodedep结构对"buffer update[缓冲区更新]"表的使用标志着在核心内存中的i-节点于VOP_UPDATE调用中被复制到对应的缓冲区中。依赖关系指针(从i-节点到间接块，以及从间接块到数据块)还不能被安全地写入磁盘，因为相应的COMPLETE和DEPCOMPLETE均处于清零状态。只有当位映射表及块内容都被写入之后，才能置这些标志位，从而完成依赖更新。
3.7 新目录项依赖关系追踪
图7表现了在目录中创建两个新项，foo和bar时的依赖关系结构。图中引入了两个新的依赖关系结构。独立的diradd结构追踪目录块中的每个项，而pagedep则管理目录块中的所有与diradd关联的依赖关系。每个新文件都会有一个inodedep结构，以及一个diradd结构。两个文件的i-节点对应的位映射表项目已经被写入磁盘，如图，它们的inodedeps中的DEPCOMPLETE标志已被置位。foo的i-节点已经通过VOP_UPDATE更新，但还没有被写盘，即inodedep中的COMPLETE还没置1，而它的diradd结构仍挂在"buf wait"表中。在i-节点被写磁，并增加了引用计数前，目录项不可以出现在盘上。如果目录页需要写盘，SoftUpdates代码将通过把i-节点数置零来回滚为foo新创建的目录项。写盘完成后，将把foo的i-节点数恢复成正确的值。
与此同时，bar的i-节点已被写盘，如图，它的inodedep和diradd结构的COMPLETE已置位。当i-节点写入完成之后， bar的diradd结构将从inodedep的"buf wait"表移动到"pending ops[待完成操作]"表中。此外，它也从pagedep"diradd"表移到"pending ops"表。由于i-节点已经被写入，写目录项将是安全的。inodedep和pagedep的"pending ops"表中的diradd项将保留到在新的目录项写到磁盘上为止。diradd结构最终在目录项写入之后释放。维护"pending ops"表的理由在于，当对一个文件作完"fsync"系统调用之后，内核能确认文件的内容和目录引用都被写盘了。此时，内核需要通过对"fsync"的i-节点的inodedep结构作查找来确认目录引用已经被写到磁盘上。如果发现了inodedep，则将检查是否有diradd依赖关系存在于"pending ops"甚至"buf wait"表中。如果找到了diradd结构，则将顺着指针找出相关的pagedep结构，并将关联的目录i-节点写盘。这一反向追踪将在目录inodedep中迭代进行。
3.8 创建新目录时的依赖关系追踪
图8表现了另两个在创建新的目录时需要的依赖结构。对于普通文件，目录项可以在新引用的i-节点，以及相应的连接计数增加写盘之后立即写盘。而对于新目录，则还有另外两个附加的依赖关系：写入包含"."和".."项(MKDIR_BODY)的目录数据块，以及重写父i-节点的引用计数，以反映".."项(MKDIR_PARENT)。这些附加的依赖关系由连接到相关diradd上的两个mkdir结构来追踪。BSD SoftUpdates设计规定，任何给定的依赖关系需要在任何时刻都与一个单独的缓冲区相符。
因而使用了两个结构来追踪不同缓冲区的动作。每个缓冲区完成操作之后，它将清除与之关联的diradd的相关标志。MKDIR_PARENT将被连接到inodedep结构父目录的inodedep结构上。当那个目录的i-节点被写入之后，相应地写入连接计数。MKDIR_BODY则关联到包含了新目录内容的缓冲区上。当缓冲区被写入时，"."和"..."目录项将同时被写盘。最后的mkdir将设置diradd结构的DEPCOMPLETE标志，diradd得知额外的依赖关系已经做完。一旦完成，对目录的diradd结构的处理就和普通文件一样了。系统中所有的mkdir结构都被连到一个表中。需要这个表的原因在于它的存在可以让diradd找到与它相关的mkdir结构，如果它们被过早地释放(例如，mkdir系统调用之后马上对同一个对象作rmdir)，则可以释放这些mkdir结构。释放diradd结构必须遍历这个表，以找出引用它的mkdir结构。假如不使用这个表，也可简单地让diradd包括两个到相关mkdir结构的指针，这也会加快删除，然而，额外的指针会使diradd结构增大一倍，而这一额外的付出只加速一种不会频繁发生的操作。
3.9 目录项删除依赖关系追踪
图9展示了与目录项删除相关的依赖关系结构。这张图引入了一个新的结构--dirrem和pagedep结构的新用法。独立的dirrem结构追踪目录块中每一个将被删除的项。除前述的pagedep用法外，它还能管理所有与目录块相关的dirrem结构。在目录块被写盘之后，dirrem请求将被加入工作守护进程的tasklist表中。对文件删除，工作守护进程将把i-节点的连接计数减1；对目录删除，工作守护进程将把i-节点的连接计数减2，并把父目录的连接计数减1。如果i-节点的连接计数下降到0，将开始3.11节描述的的资源回收。
3.10 文件截断
在未启用SoftUpdates的FFS中，当文件截断为0字节长时，i-节点中的块指针将被保存到一个临时的表中，i-节点中指向它们的指针被清零，随后i-节点被同步地写入磁盘。当i-节点写入完成时，它曾用过的块被加入空闲块位映射表中。启用SoftUpdates后，将被截断的i-节点的块指针被复制到一个freeblks结构中，随后这些指针被清零，同时i-节点被标记为"未写入"。freeblks结构随后被加入到"inode wait"表中，随后，当调用VOP_UPDATE时它将迁移到"buf wait"表中。最终，在保存i-节点块的缓冲区被写盘后，freeblks结构会加入到tasklist中。而处理tasklist时，freeblks结构中列出的块最终还给空闲块位映射表。
