Soft Updates and Dependency Ordering Without a Journal

Journaling and copy-on-write both avoid the subset problem by changing where the data goes: into a log, or into fresh blocks. Soft updates keeps the data exactly where it was and changes only the order in which the writes are issued, plus what the filesystem does when a crash interrupts them. It is the third answer to the same question, and it is the cheapest in steady-state write traffic, with no double write and no path copying, at the cost of the most intricate reasoning of the three.

The design originated with the Berkeley Fast File System work and was developed into a complete system by McKusick and Ganger. Its central claim is that the on-disk state after a crash need not be consistent, only repairable, and that a careful choice of write order guarantees the repair is bounded and cheap: no full scan, no double write, and no operation that requires information the crash destroyed.

The rule that makes an ordering safe

The key insight is that of two dependent updates, one order is safe and the other is not, and the safe order is the one that leaves a resource over-allocated rather than under-allocated. Consider allocating a block to a file: the bitmap must mark the block used, and the inode must point at it. If the inode write lands first and the crash happens, the block is owned by a file but marked free, so the allocator will hand it out again and two files share storage. If the bitmap write lands first and the crash happens, the block is marked used with no owner: a leak, which fsck can find by scanning for allocated-but-unreferenced blocks and free.

So the rule for allocation is: bitmap before pointer. The reverse for freeing: the pointer must be removed before the bitmap bit is cleared, because a crash between the two leaves a leak, while the opposite order leaves a pointer to a block that the allocator considers free.

Every metadata dependency in the filesystem has a preferred direction of this shape, and the direction is always chosen so that the intermediate state is a resource leak rather than a resource alias. Leaks are recoverable from local information, namely the block bitmap and the inode tree, without knowing what the interrupted operation intended. Aliases are not: once two inodes point at the same block, no scanning of structure can tell which one is the rightful owner.

The dependency graph for a single operation is small. Creating a file requires, in order: allocate the inode, initialize it, add the directory entry, and update the directory’s link count and the inode’s own count. Renaming a file over an existing name requires incrementing the new name’s target count, adding the new entry, removing the old entry, and decrementing the old target’s count. Each of those is a partial order, and independent operations can interleave freely, which is where soft updates gets its performance.

What the implementation must track

Enforcing an order requires knowing which writes are dependent, which means the buffer cache must carry dependency information per buffer. Each dirty buffer records the buffers that must be written before it, and the writeback path refuses to write a buffer whose dependencies are still dirty. The count is a small integer per buffer; when a dependency is satisfied the count is decremented, and a buffer with a zero count becomes eligible.

This is the mechanism’s cost: every buffer write must be preceded by a check, and every dependency edge must be created at the point where the operation is performed, which means every metadata operation must know its own dependency structure. The bookkeeping is not optional and not approximate — a missing edge is a correctness bug that shows up only after a crash at the wrong moment.

The writeback policy interacts with the dependency graph in a way that produces the design’s most distinctive feature. When a buffer is written, the buffers that were waiting on it become eligible, but the buffer itself is not marked clean: it stays dirty with a reduced count, because it will be written again once the buffers that depend on it have landed. This is rollback. A dependency that points from A to B means “A must be durable before B”; after A is written, B can go, and A is written a second time afterwards, at which point A’s content is the version that assumes B is present.

The reason for the second write is the crash window between A and B. Between them, A is on disk in a state that presumes B, and B is not. If the crash happens there, the disk is in a state the filesystem’s invariants reject: A points at something B was supposed to allocate. Rollback means the final content of A, once B is durable, is the version consistent with B, while the intermediate version that was written first is the one that keeps the intermediate state repairable.

/* Per-buffer dependency state, held in the buffer cache alongside the data. */
struct buf {
    uint64_t blkno;
    int      deps;        /* prerequisites not yet durable: blocks any write */
    int      succ;        /* dependents not yet durable: blocks the final write */
    bool     dirty;
    bool     safe_form;   /* the pre-dependency version is already on disk */
};

/* Writeback path: a buffer may be issued once its prerequisites are durable. */
static int can_write(struct buf *bp)
{
    return bp->deps > 0 ? -EAGAIN : 0;
}

/* Called after bp reaches disk. Propagate the edge in both directions. */
static void write_complete(struct buf *bp)
{
    bp->safe_form = (bp->succ > 0);        /* final form not yet safe to write */

    for (int i = 0; i < bp->ndependents; i++)
        dependent(bp, i)->deps--;          /* they may now go */

    for (int i = 0; i < bp->nprereqs; i++) {
        struct buf *p = prereq(bp, i);
        if (--p->succ == 0 && p->safe_form) {
            p->dirty     = true;           /* roll back: rewrite in the final form */
            p->safe_form = false;
        }
    }
}

The counters encode the order. deps is the number of prerequisites still outstanding, and a non-zero value keeps the buffer from being written at all. succ records how many buffers depend on this one; while it is non-zero, a write of this buffer goes out in the form that is safe in isolation, and when it reaches zero the buffer is dirtied again with the form that presumes its dependents. A buffer with succ == 0 is written once; the second write is the price of rollback, paid only by buffers at the head of a dependency edge.

Cycles, and why rollback is required

The partial order is not always acyclic. Two operations that each need the other’s resource produce a cycle: a directory entry that must be written before an inode’s link count can be decremented, where the link count’s buffer is also needed for the directory’s own allocation. When a cycle exists, no ordering satisfies all the constraints, so one of them must be broken.

The resolution is to write one member of the cycle early, in a form that is safe in isolation, then write the rest, then rewrite the first member with its final content. The early write is the rollback write. Its content must be chosen so that the intermediate state is repairable, which is the same criterion as everywhere else: over-allocated rather than aliased. In practice this means the early form of a directory block might contain a placeholder entry whose inode is already allocated but whose name is not yet linked, and the later form completes the link.

The cost of rollback is the extra write, which appears only for buffers on a cycle. In the common case the graph is acyclic and the write count is exactly the number of buffers, so the steady state is one write per modified block, the same as an in-place filesystem with no journal and about half of what a journal costs. The extra writes appear under the operations that create cycles, which in practice means directory operations that allocate and free simultaneously, and they are bounded by the number of buffers in the cycle rather than by the size of the operation.

What recovery must do, and how it is bounded

A crash leaves a state that satisfies some of the orderings and not others. Recovery does not replay a log; it runs a checker that reads the inode tree and the bitmaps and reconciles them. The difference from the pre-journaling full check is that the checker knows the state is of a restricted form: because every ordering was chosen to leak rather than alias, the inconsistencies it can encounter are limited to allocated-but-unreferenced blocks, link counts that are higher than the number of directory entries, and directory entries whose inode is unallocated.

Each of those is repairable with local information. Unreferenced blocks are freed. Link counts that exceed the entry count are decremented to match. Directory entries with unallocated inodes are either removed or have their inode reinitialized, depending on whether the entry’s presence is itself the result of a rollback write. The checker’s cost is proportional to the number of inconsistencies plus the cost of the scan needed to find them, and the scan can be restricted if the filesystem records which regions were being modified, which the cylinder-group or block-group structure of FFS provides locality for.

The remaining risk is the one case the ordering cannot eliminate: a crash between the two writes of a rollback pair. The intermediate state must be repairable, and the checker must be able to distinguish “this entry was being created” from “this entry was being destroyed”. FFS records the direction in the inode’s state. An inode whose link count is zero but which is still referenced is a file being created, while an inode whose link count is positive but which no entry references is a file being destroyed, and the checker resolves each accordingly.

Where soft updates loses to the other two

Soft updates has no log, so it has no way to make an operation atomic beyond the ordering discipline. A sequence of operations that a journal would commit as one unit is, under soft updates, a set of individually ordered writes with a repairable intermediate state. That is sufficient for structural consistency and insufficient for the stronger guarantee that a completed operation is present after a crash.

It also has no natural snapshot mechanism. Because it modifies blocks in place, a snapshot requires copying the blocks it wants to preserve, which is the thing copy-on-write avoids. The copy-on-write design is what makes O(1) snapshots possible, and the reference counting that supports them has no counterpart in a soft-updates filesystem.

The implementation burden is the other cost. Every metadata operation must be written with its dependency edges, and every new operation added to the filesystem must have its orderings derived and proved. A journal imposes no such requirement, since any set of blocks can go into a transaction. That asymmetry in implementation effort explains why soft updates stayed within the BSD family while journaling became the common default, and why copy-on-write became the basis for the newer designs. Soft updates remains the reference demonstration that ordering alone, with no log and no copying, is sufficient for crash consistency of metadata, and its dependency rules are the clearest statement of what “safe intermediate state” means.