第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)
此标志表示包含此依赖关系结构的缓冲区尚未被写盘。当包括必须回滚的依赖关系的缓冲区写盘之前，这一标志将被清零，以体现在缓冲区中的回滚。当写盘完成时，此标志被清零的那些依赖关系结构对应的缓冲区将恢复原状。所以，如果此标志复位，则绝不能释放对应的依赖关系，因为它包括需要进行恢复操作，此时释放将造成这些信息丢失。