Segment Liveness Accounting: How the Cleaner Knows What Is Already Dead

A cleaner cannot decide what to clean without knowing how much of each segment is still needed. The quantity that answers the question is the segment’s live byte count: the number of bytes in the segment that some current inode, indirect block, or map block still references. A segment with zero live bytes can be freed immediately at no cost. A segment that is entirely live cannot be freed at any cost short of moving all of it, which is pure overhead. The interesting segments lie between, and the whole efficiency of the collector depends on this number being accurate and current.

Keeping it accurate is harder than it sounds, because liveness is not a property of a block. It is a property of the relationship between a block and the rest of the filesystem, and that relationship changes when some unrelated write supersedes the block. The accounting must therefore be updated on every write that replaces an existing block, which is every write in the system.

Liveness is determined by the latest version

When a file’s block at offset n is rewritten, the filesystem appends a new block to the log and updates the inode (or indirect block) to point at the new address. The old block is now dead. Nothing marks it as dead; it simply stops being referenced. The segment that contains it has lost one live block, so its count must decrease by the block’s size.

The accounting problem is that the filesystem must know which segment the old block was in. It knows the old address, because the inode it is modifying held that address a moment ago, so the segment is computable by division. The decrement is therefore possible in constant time, provided the old address is still available at the moment of the update.

It usually is, and that is the whole trick: the liveness update piggybacks on the pointer update. When the inode is rewritten to point at the new block, the code that writes it also reads the pointer it is replacing and decrements that segment’s counter. There is no separate scan, no mark phase, and no need to consult the segment summary of the old block: the segment is recovered from the old address by a single division, segment = address / blocks_per_segment.

/* Replace the pointer at file offset off, accounting for both segments. */
static void install_block(struct lfs *fs, struct inode *ip, uint64_t off, uint64_t new_blk)
{
    uint64_t old_blk = inode_get_pointer(ip, off);
    if (old_blk) {
        struct segusage *os = &fs->usage[old_blk / fs->blocks_per_seg];
        os->live_bytes -= fs->blocksize;   /* the superseded copy dies here */
        os->dirty = 1;
    }
    inode_set_pointer(ip, off, new_blk);

    struct segusage *ns = &fs->usage[new_blk / fs->blocks_per_seg];
    ns->live_bytes += fs->blocksize;       /* the new copy is live on arrival */
    ns->dirty = 1;
}

Two properties of this code deserve attention. The counters are per segment, not per block, so the memory footprint is one small record per segment: a volume with a hundred thousand segments needs a hundred thousand records, which is well under a megabyte. And the record is dirty only while the change is in memory; it is written out as part of the checkpoint, not as part of every block write.

Why the counters must be exact

A tempting simplification is to estimate liveness from the segment’s age, on the theory that old segments contain mostly dead data. Some collectors do use such heuristics as a pre-filter, but the decision to clean a specific segment should rest on its actual count, because the cost of being wrong is asymmetric.

Cleaning a segment whose live fraction is higher than estimated copies more data than planned, and the copy consumes log space that the cleaner was trying to create. If the estimate is optimistic by enough, the cleaner can enter a state where each cleaning pass produces less free space than it consumed, and the volume slowly fills even though every individual decision looked reasonable. This is the failure mode analyzed in Garbage Collection Under Space Pressure, and it originates in accounting that was approximate.

Cleaning a segment whose live fraction is lower than estimated wastes an opportunity but does no harm: the segment is freed, and the collector simply did not pick the best candidate. Underestimating cost is the dangerous direction, which means the count should err toward including anything that might still be referenced.

The subtlety is that “still referenced” is not the same as “referenced by the current inode map”. A block may be referenced by an indirect block that is itself dead, in which case the block is dead too. Decrementing on the pointer replacement handles this correctly if the recursion is followed: when an indirect block is superseded, its own decrement happens, and the blocks it pointed to are decremented only if they are not referenced from the new indirect block. A naive implementation that decrements every child of a replaced indirect block will undercount liveness, because some children are shared between the old and new versions. A naive implementation that decrements none of them will overcount, leaving permanently unreclaimable space. The correct rule is to compare the old and new pointer arrays and decrement only the entries that differ.

Consistency with the segment summary

The live count in memory and the summary written into the segment describe the same facts from opposite directions. The summary says what was written into the segment when it was created. The live count says how much of it is still needed now. Both are needed: the summary to reconstruct state after a crash, the count to drive cleaning.

On recovery, the counts are rebuilt by scanning forward from the checkpoint and installing map entries, as described in Checkpoint Regions and Tail Recovery. The count for a segment is then derived by taking the summary’s total and subtracting the blocks whose entries were superseded by later summaries. Deriving it this way is exact, because the scan sees every superseding write in order.

For segments older than the checkpoint, the counts come from the checkpoint itself. This is why the segment usage table must be part of the checkpoint rather than being recomputed: recomputing it would require reading the entire log, including all the segments that have not changed since the last checkpoint.

There is a version hazard here that is easy to miss. The checkpoint records counts that were true when the checkpoint was taken. If a write between the checkpoint and the crash supersedes a block in an old segment, that segment’s true count is now lower than the checkpoint says. Recovery’s forward scan covers exactly those writes, so the counts converge to the truth. If the scan stops early because of a torn segment, the counts for old segments may be stale in the conservative direction, claiming live bytes that are dead, which delays reclamation of a small amount of space but never frees a live block. That is the correct direction to fail in.

Liveness across generations

A segment that is partially live is not a fixed object. Its count decreases over time as the blocks it contains are superseded, and it increases only if a block is copied into it, which happens only when it is being cleaned. So the natural history of a segment is a monotone decline from fully live at creation to fully dead at some later point.

This monotonicity is what makes the collector’s job tractable. A segment written recently is likely to be nearly fully live, because the blocks in it are fresh and their owners have not rewritten them yet. A segment written long ago is likely to be nearly dead, because its contents have been replaced many times over. Cleaning the oldest segments first is therefore a good heuristic, and it is the basis of the age-ordered policies discussed in Choosing What to Clean.

The monotonicity also has a limit. Some blocks are never superseded: a file that is written once and never modified keeps its blocks live for as long as the file exists. Those blocks migrate from segment to segment as their segments are cleaned, and each migration costs a copy. A volume dominated by such data has a floor on its live fraction that no policy can lower, and the collector’s throughput is bounded by how often it must move that immovable data.

The cost of tracking at block granularity

Per-segment counters are cheap. Per-block liveness would be more precise, allowing the collector to copy only the live blocks out of a segment and skip the dead ones without reading them. The cost is four to eight bytes of metadata per block, which for a 4 KiB block size is under 0.2 percent of the volume, and the benefit is avoiding reads of dead blocks during cleaning.

Whether that trade is worthwhile depends on the read cost relative to the write cost. On a device where reads are cheap and writes are the bottleneck, reading a whole segment to find the live blocks is fine, and the per-block map is wasted memory. On a device where reads cost as much as writes, or where the segment is large enough that reading it dominates, the map pays for itself. Implementations have gone both ways, and the choice is usually settled by whether the cleaner reads segments sequentially, in which case the dead blocks cost almost nothing, since the read is dominated by the transfer of the whole segment anyway, or in a scattered pattern, in which case skipping dead blocks avoids real seeks.

The accounting described here is the least glamorous part of a log-structured filesystem and the one most likely to be subtly wrong. A counter that drifts by a block per thousand writes is invisible in testing and accumulates into a volume that cannot reclaim space it should have. The defense is not cleverness but an invariant that can be checked: the sum of all segments’ live counts must equal the total number of blocks reachable from the inode map, and that equality can be verified by a full scan when the volume is idle.