Delayed Allocation and the Reservation Window

Allocating a block at the moment a program writes to it is the obvious design, and it is wrong for sequential writes. The program writes eight kilobytes, the filesystem picks a free block, the program writes another eight kilobytes a moment later, the filesystem picks another free block, and the two choices are made independently with no knowledge that the file will eventually be a gigabyte long. Delayed allocation defers the choice until a large run of writes has accumulated, so the allocator can see the whole run and place it as one extent.

The decision moves from write to writeback

With delayed allocation, a write into a page that is not yet backed by a block does not allocate anything. The page is added to the page cache and marked dirty, and the inode records that this range is pending allocation. The block map for that range stays empty, and a read of the range is served from the cache rather than from the device.

Allocation happens when writeback selects the page, the mechanism described in The Page Cache and the Writeback Path. By then the page cache may hold megabytes of contiguous dirty data for the file, so the writeback path can ask for a single allocation covering the whole run, and the extent tree gets one record instead of hundreds. The layout improvement is the primary motivation: sequential write throughput on a fragmented volume depends on how large a contiguous run the allocator can find, and the allocator’s chances improve with the size of the request it is given.

/* Schematic: a write into an unmapped page reserves space, allocates nothing.
 * Not kernel source. */
int da_write_begin(struct file *f, loff_t pos, unsigned len)
{
        if (reserve_blocks(f->inode, len) < 0)
                return -ENOSPC;                /* fail here, not at writeback */
        /* The page joins the cache with no block number attached. */
        return pagecache_begin(f->mapping, pos, len);
}

The reservation step is what makes the deferral safe. Between the write and the writeback, the filesystem has promised space it has not yet taken from the free pool. If it did not reserve, another file could consume the free blocks and the writeback would fail with ENOSPC long after the writing program was told the write succeeded. The reservation converts a late failure into an early one, which is the only way the interface’s contract can be kept.

What a reservation actually holds

A reservation is per-inode, not per-write. The inode carries a window: a starting block and a length, plus a count of blocks reserved. When a write needs space, the filesystem checks whether the write falls inside the current window; if it does, the reservation is already sufficient. If it does not, the window is closed and a new one is opened, sized from a heuristic that grows with the file’s size so that a large file gets a large window and a small file does not hoard space.

The window is a claim against the filesystem’s free space, counted separately from blocks actually assigned. While a window is open, its unused portion is space the filesystem has promised and cannot hand to another inode, so it is subtracted from what allocation sees as available. Closing the window returns whatever was not used. That accounting is why a volume with delayed allocation can report less free space than the sum of its files’ sizes would suggest: part of the free space is reserved rather than allocated.

Two windows cannot overlap for the same inode, and the filesystem serialises window changes with the inode’s lock. Without that, two concurrent writers appending to the same file could each open a window and reserve the same blocks twice, and the accounting would drift below the true free count. The counters involved are maintained per filesystem and reconciled lazily; the group descriptor’s free count is updated when blocks are actually allocated, not when they are reserved.

The reservation is also what bounds the damage of a crash. A window is an in-memory claim; the on-disk inode has no field for it. On recovery the claim simply does not exist, so any space that was reserved and never converted into an extent is free again, and any extent that was committed has its blocks marked used in the bitmap by the journal replay. The two cases cannot disagree, because the only durable record of an allocation is the committed extent, and the only durable record of a reservation is nothing at all.

The ordering problem the deferral creates

Deferring allocation moves the moment at which the block map changes. In the ordinary path, a write allocates a block and dirties the block map, and both the data and the map are written back later. With delayed allocation, the block map does not exist until writeback, so the writeback path must decide the order in which the data and the map reach the device.

The safe order is: allocate the blocks and record the new extents in a transaction, write the data into those blocks, and only then commit the transaction. A crash before the commit discards the transaction, so the bitmap still marks the blocks free and the inode still has its old map: the write is lost, and the volume is consistent. The dangerous order is the reverse. If the transaction commits before the data reaches its home blocks, a crash leaves an inode whose map names blocks holding whatever was there before, so the file reads stale content through a map the filesystem considers valid.

/* Schematic writeback for a file with pending allocations. Not kernel source. */
int da_writepages(struct inode *in)
{
        reserve_blocks_for_pending(in);   /* 1. enough free blocks for the range */
        begin_transaction();
        record_extents(in);               /* 2. the new map entries, journalled */
        write_pages(in);                  /* 3. data reaches its home blocks */
        commit_transaction();             /* 4. only now is the map authoritative */
        return 0;
}

The journaling mode decides how strictly that ordering is enforced. In the mode that journals data as well as metadata, the data goes into the journal as part of the same transaction, so the commit covers both and a crash yields either the whole write or none of it, at the cost of writing every byte twice. In the metadata-only mode with ordering, the filesystem issues the data writes and waits for them to complete before committing the transaction that records the extents, so the map never becomes authoritative ahead of the data; the guarantee is the weaker one above, since a torn data write can still leave a block that is partially old and partially new. The mode that journals metadata with no ordering at all gives that up, and a crash can leave a committed map naming blocks that hold stale bytes or zeroes.

Interaction with fsync and with holes

fsync on a file with pending delayed allocations forces the allocation and the writeback before it returns, because otherwise the call would not have made the data durable. That means the first fsync after a burst of writes pays for the allocation of the whole burst, and a program that writes and syncs in small increments gets none of the layout benefit and all of the cost. The pattern that benefits is a large write followed by one sync.

Reads of a pending range are served from the cache, so a program that writes a region and reads it back sees its own data without the filesystem having allocated anything. That is the same guarantee the cache gives for ordinary writes; the difference is only that the block map is absent, and a reader that bypasses the cache with direct I/O cannot be served, because there is no block to read from. Direct I/O against a file with pending allocations forces them, which is one reason mixing buffered and direct access to the same file is discouraged.

Holes are affected in a subtler way. A write that leaves a gap creates a sparse region; with delayed allocation, the gap is not materialised as absent extents until writeback decides what to do with the ranges around it. If the surrounding writes are far apart, the allocator may allocate them as separate extents with a hole between, or it may decide the file is sparse and leave the gap unallocated. The inode’s size field is updated at write time regardless, so stat reports the full length while the allocated block count stays at zero for the gap.

When the deferral is not worth it

Three situations argue against it. A workload that writes a small amount and immediately syncs gains nothing and pays the reservation cost. A filesystem that is nearly full cannot defer safely, because a reservation may fail and the write must then be refused at write time, which is the behaviour delayed allocation was meant to avoid; implementations fall back to immediate allocation when free space drops below a threshold.

The third is the one that matters for correctness: a program that relies on write failing when the device is full will not see the failure with delayed allocation, unless the reservation is checked at write time. The reservation is what makes the check possible, and a filesystem that implements delayed allocation without it has a real bug, not a performance trade-off. The reservation window and the extent tree described in Extent Trees and the Replacement of Indirect Block Maps are two halves of the same mechanism: the window decides how much can be promised, and the tree records what was delivered.