Back
+30 XP
Concept

Sparse File Hole Punching & Extent Mapping

Sparse files allow operating systems to represent multi-gigabyte files containing empty sectors without consuming physical disk storage. Storage systems track allocated extents in block tables; unallocated regions (holes) automatically read as zero bytes without taking disk space.

python
# Linux hole punching syscall via fallocate:
# os.fallocate(fd, mode=FALLOC_FL_PUNCH_HOLE|FALLOC_FL_KEEP_SIZE, offset, len)

# Sparse File Hole Punching & Extent Mapping When virtualization hypervisors create a 500 GB virtual disk image for a new guest operating system that only uses 4 GB of files, allocating 500 GB of real physical SSD sectors immediately wastes entire storage arrays. 💾⚡ **Sparse Files** solve this. Modern filesystems (ext4, XFS, APFS, NTFS) track files as a map of **Extents** (contiguous physical block ranges): - Allocated ranges point to physical disk blocks. - Unallocated ranges are **Holes**: ranges where no disk space exists. When an application reads a hole, the kernel immediately returns streams of `0x00` null bytes without performing disk reads. - **Hole Punching** (`FALLOC_FL_PUNCH_HOLE`) tells the filesystem to deallocate existing blocks back to the free disk pool while keeping file size identical. ```python # In-memory extent block simulation: blocks = {} # block_id -> 4096-byte array ``` ## Pop Quiz What occurs when an application attempts to read from an unallocated "hole" in a sparse file? - [ ] The filesystem automatically synthesizes and returns null bytes (0x00) without reading physical disk media. - [ ] The operating system raises an EOFError and truncates the file size to the hole offset. - [ ] The disk controller allocates new flash memory sectors filled with random entropy. - [ ] The file read call hangs until background daemons populate the hole. ## Real-World Challenge Implement `SparseExtentFile(size: int, block_size: int = 4096)`. - `write(offset: int, data: bytes)`: Allocates blocks on demand and writes bytes. - `punch_hole(offset: int, length: int)`: Deallocates any complete blocks fully spanned by the hole range. - `read(offset: int, length: int) -> bytes`: Returns bytes, returning `0x00` for unallocated holes. - `allocated_bytes() -> int`: Returns `len(allocated_blocks) * block_size`. <details> <summary>Solution</summary> ```python class SparseExtentFile: def __init__(self, size: int, block_size: int = 4096): self.size = size self.block_size = block_size self._blocks = {} # block_idx -> bytearray def write(self, offset: int, data: bytes): for idx, byte_val in enumerate(data): pos = offset + idx if pos >= self.size: break b_idx = pos // self.block_size b_offset = pos % self.block_size if b_idx not in self._blocks: self._blocks[b_idx] = bytearray(self.block_size) self._blocks[b_idx][b_offset] = byte_val def punch_hole(self, offset: int, length: int): # Calculate start and end block boundaries start_block = (offset + self.block_size - 1) // self.block_size end_block = (offset + length) // self.block_size for b_idx in range(start_block, end_block): if b_idx in self._blocks: del self._blocks[b_idx] def read(self, offset: int, length: int) -> bytes: result = bytearray(length) for idx in range(length): pos = offset + idx if pos >= self.size: break b_idx = pos // self.block_size b_offset = pos % self.block_size if b_idx in self._blocks: result[idx] = self._blocks[b_idx][b_offset] else: result[idx] = 0 # Hole synthesizes null bytes return bytes(result) def allocated_bytes(self) -> int: return len(self._blocks) * self.block_size # Verification sparse = SparseExtentFile(size=1024 * 1024, block_size=4096) # 1 MB logical size sparse.write(0, b"BOOT_SECTOR") sparse.write(8192, b"DATABASE_CHUNK") assert sparse.allocated_bytes() == 8192 # Only 2 blocks allocated assert sparse.read(0, 11) == b"BOOT_SECTOR" assert sparse.read(4096, 4) == b"\x00\x00\x00\x00" # Unallocated hole assert sparse.read(8192, 14) == b"DATABASE_CHUNK" # Punch hole on block 2 sparse.punch_hole(8192, 4096) assert sparse.allocated_bytes() == 4096 # Freed block 2 assert sparse.read(8192, 4) == b"\x00\x00\x00\x00" ``` </details>