Sparse Files and the Gap Between Length and Allocation

Creating a file, seeking to offset 2^40, and writing one byte produces a file whose reported size is one tebibyte plus one byte and whose allocated space is one block. No zeros were written for the intervening bytes, and none exist on disk. The read that follows returns zeros because the interface requires it, not because the data is stored. The mechanism that makes this possible, and the places where it breaks, hinge on the separation between the length the interface reports and the blocks the filesystem actually maps.

Two numbers, one file

The interface has always carried both. st_size from stat is the length, and st_blocks is the space allocated, counted in 512-byte units. A file created by the seek-then-write sequence above reports a st_size of 1,099,511,627,777 bytes and a st_blocks of 8 on a filesystem with 4096-byte blocks. Both numbers are correct and neither is derivable from the other.

The filesystem stores the mapping, not the contents, for the parts of the file that have been written. On ext4 an inode’s block map is a tree rooted in a small array of extents; each extent records a logical block range and the physical block where it starts, so a contiguous run of a file costs one extent rather than one pointer per block. A logical block not covered by any extent is a hole, and the read path translates a lookup miss into a zero-filled buffer without consulting the disk.

The extent tree has a fixed depth for small files and grows when the file fragments. Ext4’s default inode holds four extents inline; a file that needs more allocates a block for the extent tree, and the tree can deepen further. The consequence for sparse files is that holes cost nothing at all: a hole is the absence of an extent, and a file that is almost entirely holes has a block map that is almost empty.

Reads and writes inside a hole

Reading a hole returns zeros. The kernel does not allocate on read, so a program that seeks across a hole and reads a page receives a zero-filled page and the file’s allocation is unchanged. This is a requirement of the interface, not an optimisation: a read must return the same bytes whether or not the region is allocated, and the only way to satisfy that is to synthesise zeros.

Writing into a hole is where allocation happens. The first write to a logical block inside a hole triggers an allocation, and the filesystem must decide how much to allocate around the write. Ext4’s delayed allocation holds dirty pages in memory and assigns blocks at writeback time, which lets it see the final shape of the write and allocate a contiguous extent rather than one block per page. The delay is bounded by the dirty-page limits and by the periodic writeback interval, so a program that writes a byte and immediately crashes has no allocation at all, while a program that writes and calls sync gets a block.

A write that extends the file past its current end sets the length. A write strictly inside the current length does not: the size is the maximum offset ever written plus the write’s length, and punching a hole later does not reduce it. This asymmetry is why truncating a file to a smaller size and then extending it back leaves holes where the data used to be, rather than restoring it.

The limits on how long, and how scattered, a sparse file can be

The length of a sparse file is bounded by the file offset type, not by the device. A 64-bit offset allows a length near $2^{63}-1$ bytes, and the filesystem’s own format narrows that further: ext4 caps a file at roughly 16 TiB with 4 KiB blocks because of the extent format, while XFS allows lengths in the exabyte range on paper. A program that seeks to a large offset and writes one byte therefore succeeds or fails on the size limit, and the failure is EFBIG rather than ENOSPC, because nothing was to be allocated.

The block map itself is not free. Each distinct region of data needs an extent record, so a file built by writing one byte every megabyte is sparse in data blocks but not in metadata: it needs one extent per byte written, and those records consume blocks of their own. The pathological form of this is a file whose extent descriptors outnumber its data blocks, which is why filesystems merge adjacent extents on every write and why a scattered write pattern into a hole costs more than writing the same number of bytes contiguously. Sparseness is a property of the map, and the map has a cost of its own.

Seeking over a hole without reading it

A program that copies a sparse file by reading and writing every byte destroys the sparseness: the reads return zeros, the writes allocate blocks for them, and the copy occupies the full length. The interface provides a way to ask where the data actually is.

lseek with SEEK_HOLE returns the offset of the next hole at or after the given position, and SEEK_DATA returns the offset of the next region with data. A copy that alternates the two calls can skip the holes entirely and reproduce the sparse structure:

/* Copy only the data regions, leaving holes as holes. */
off_t pos = 0, end = src_size;
while (pos < end) {
    off_t data = lseek(src, pos, SEEK_DATA);
    if (data < 0) {                 /* ENXIO: no data at or after pos */
        if (errno == ENXIO) break;
        return -1;
    }
    off_t hole = lseek(src, data, SEEK_HOLE);
    copy_range(src, dst, data, hole - data);
    pos = hole;
}

copy_range copies len bytes at off from the source to the same offset in the destination, looping over read and write until the count is consumed; it is the only part of the loop that depends on the application’s own buffering, and the rest is the two lseek calls.

Both calls are advisory in the sense that a filesystem may report a data region as extending over a hole, but they must never report a hole where data exists. The weaker direction is safe: a copy that trusts the answers loses sparseness at worst, and never loses content. Some filesystems implement SEEK_HOLE by consulting the extent map, which is exact; others fall back to scanning for zero-filled pages, which is approximate and can be slow.

SEEK_DATA on a filesystem that does not support the operation fails with EINVAL, so a copy tool must be prepared to fall back to reading everything.

Punching holes in existing files

The reverse operation removes allocated blocks from a range while keeping the file’s length. fallocate with FALLOC_FL_PUNCH_HOLE combined with FALLOC_FL_KEEP_SIZE does this: the range becomes a hole, reads return zeros, and st_size is unchanged. The blocks return to the allocator immediately, and the inode’s extent map loses the corresponding entries.

The flag combination is required because fallocate by default extends the file’s length. The two flags together say “deallocate this range and do not change the size”, which is precisely hole punching. Calling it without FALLOC_FL_KEEP_SIZE on a range beyond the end grows the file instead.

Punching has a granularity floor. On ext4 and XFS the smallest unit is the filesystem block, typically 4096 bytes; a punch that covers part of a block zeroes the rest of the block rather than freeing it, and the block remains allocated. A program that punches many small ranges below the block size therefore frees nothing. Alignment to the block size matters more than the range’s length.

The operation also interacts with page cache. Blocks that were mapped into a process through mmap and are resident in the page cache must be invalidated, because the mapping no longer has storage behind it. Linux handles this by unmapping the affected pages, so a process with a live mapping over the punched range receives SIGBUS on the next access. That is the correct behaviour and it is also a hazard: a program cannot punch holes in a file it has mapped and continue to use the mapping.

Preallocation as the opposite trade

fallocate without flags reserves blocks for a range without writing them, so the blocks are allocated but their contents are undefined until written. The file’s st_size grows to cover the range and st_blocks rises, but no data is transferred. This is the mechanism a database uses to avoid ENOSPC in the middle of a large write: reserve the space up front, then fill it, and the write cannot fail for lack of space.

The three states a block range can be in are worth keeping distinct:

State	st_size	st_blocks	Read returns
hole	covers range	unchanged	zeros
unwritten extent	covers range	counted	zeros until written
written extent	covers range	counted	stored bytes

An unwritten extent reads as zeros, like a hole, but occupies space. The distinction exists so that a filesystem can allocate contiguously without zeroing, which would cost a full pass over the range. Ext4 records unwritten extents in the extent tree with a flag, and converts them to written when the range is first written.

The trade is explicit: preallocation converts a possible mid-write failure into an up-front failure, at the cost of holding space that may never be used. A file with a large unwritten extent looks full to du and empty to cat.

Where sparse files surprise their owners

Four consequences recur.

Backup and archive tools that read every byte inflate the file to its full length, and a restore produces a file that occupies what it reports. Tar has a sparse-file extension that records holes, and its absence from a format means the copy is dense. Copying with a tool that does not understand SEEK_HOLE is the most common way to turn a terabyte of holes into a terabyte of zeros.

cp and similar utilities decide whether to preserve sparseness from the source’s st_blocks; a source with st_blocks far below its st_size is sparse, and the copy is done with hole detection. A file whose blocks are only slightly fewer than its length gets a dense copy, which is the right call for small gaps.

Filesystem-level deduplication and compression change what st_blocks means. On a filesystem that compresses, the block count reflects compressed storage, so st_size and st_blocks can differ by a large factor for a file with no holes at all. Tools that infer sparseness from the ratio misclassify compressed files.

Quotas and space accounting count allocated blocks, not lengths, which is the reason a sparse file is nearly free against a quota until it is written. The other side of the same rule is that a program can create a file whose logical size exceeds the free space on the device many times over, and only discover the limit when it writes.

Sparse files and the block map

The property that makes all of this work is that the inode’s block map is a map from logical offsets to physical blocks, not a contiguous description of the file. A file whose map covers a few regions can be enormous. A filesystem that allocated the file’s blocks at creation, as some simple designs do, cannot represent a hole at all, and on those filesystems a sparse file is impossible rather than merely expensive.

The same map structure is what truncate uses to extend a file: extending the length adds no extents, so the new region is a hole. Truncating to a smaller size removes the extents covering the removed range and frees their blocks, which is why truncate to zero on a large file is fast: it is proportional to the number of extents, not to the file’s length. The inode itself, and the fields that report these two numbers, are described in What an Inode Stores, and Why It Stores No Name, while the cost of reading that map and the properties of the device underneath it belong to the storage layers below the interface.

One more interaction belongs here. A sparse file that is mmaped has pages mapped for the whole length, and a read fault on a hole page maps the shared zero page rather than allocating. A write fault allocates, exactly as a write would. The mapping therefore preserves sparseness on read and breaks it on write, one page at a time. The mapping is established through a descriptor, whose offset and flags belong to the description described in Open File Descriptions and the Offsets They Share. The allocation happens during a fault rather than during a syscall, so a process that maps a hole and writes through the mapping has no return value to check; the first indication that the device is full is a SIGBUS on the faulting access, delivered by the kernel rather than reported by the write. Programs that need an error they can handle must reserve space with fallocate before mapping it, which is the same up-front trade described above.