Lesson 10.5: File Allocation

01 Introduction

Lesson 10.1 introduced the file as a named sequence of bytes and the directory as a mapping from names to inodes. Lesson 10.2 examined the metadata that the inode holds, and Lesson 10.3 presented the inode itself — its layout, its lifetime, and its role in path resolution. Lesson 10.4 turned to the directory's internal structure, showing how the name-to-inode mapping is stored and searched. This lesson addresses the other half of the file system's core: the mapping from a file's logical blocks to the physical blocks on the storage device.

The allocation problem is simple to state: a file is a sequence of logical blocks (block 0, block 1, block 2, …), and the storage device is a sequence of physical blocks (sector 0, sector 1, …). The file system must map each logical block of each file to a physical block, and it must be able to find the physical block for any logical block on demand. The mapping is recorded in the file's metadata — in the inode, or in a structure the inode points to — and it is read every time the file is accessed.

The choice of allocation method is one of the file system's most consequential design decisions. It determines the file's access characteristics (whether sequential reads are fast, whether random reads are fast), the file's growth characteristics (whether it can grow without moving, whether it can grow at all), the space overhead (how much space is wasted on pointers and on the last block), and the file system's resilience to fragmentation (whether the free space becomes too fragmented to use). The classical methods — contiguous, linked, and indexed allocation — each make a different trade-off, and the modern methods — extents, block groups, and delayed allocation — are refinements that address the classical methods' limitations.

This lesson presents the allocation problem and the three classical solutions. It presents extents, the modern method that ext4, XFS, and Btrfs use, and it presents the block group and allocation policies that decide which free blocks are chosen. It presents free-space management, the data structures that track which blocks are available, and it presents the fragmentation problem that allocation policies try to avoid. It closes with a survey of the allocation strategies of the major file systems.

Prerequisites

This lesson builds directly on Lessons 10.1, 10.2, and 10.3. The file as a sequence of logical blocks, the inode as the file's metadata record, and the inode's role in locating the file's data are all assumed. The directory structures of Lesson 10.4 are the context in which a file's name is resolved to an inode, but the directory's internal structure does not affect the allocation of the file's data blocks. The discussion of block groups and allocation policies assumes the general concept of a disk block from Lesson 11.1 (which is later in the module — read it as a preview if you have not yet covered it), but no new storage concepts are introduced. Familiarity with the Linux command line from Lesson 2.2 is helpful, since the interactive activity uses standard Unix tools.

02 Learning objectives

By the end of this lesson you will be able to

Define the allocation problem and explain why the choice of allocation method matters.
Describe contiguous allocation and explain its advantages and disadvantages.
Describe linked allocation and the File Allocation Table, and explain their trade-offs.
Describe indexed allocation, multi-level index blocks, and the inode's pointer scheme.
Describe extents and explain how modern file systems use them to reduce metadata overhead.
Explain block groups, allocation policies, and free-space management, and describe how they affect fragmentation.

This lesson contributes to U10.5 and U10.6, and to course learning outcomes CLO1, CLO4, CLO5, and CLO6.

03 Required reading

Operating System Concepts — Chapter 14, Section 14.4, Allocation Methods. The standard treatment of contiguous, linked, and indexed allocation, including the File Allocation Table and the multi-level index.
OSTEP — Chapter 40, File System Implementation. OSTEP's treatment of the file system's on-disk structures, including the inode's pointer scheme and the Fast File System's block groups, is the clearest available account, and it is the basis for the worked example in this lesson.
Tanenbaum & Bos — Modern Operating Systems, Chapter 4, Section 4.3.2, File System Implementation. A complementary treatment that develops the allocation methods from first principles and compares them systematically.
McKusick, M. K., Joy, W. N., Leffler, S. J., & Fabry, R. S. — A Fast File System for UNIX. ACM Transactions on Computer Systems, 1984. Sections 3 and 5 discuss the block layout, the cylinder groups, and the allocation policies.
Bach, M. J. — The Design of the UNIX Operating System. Prentice Hall, 1986. Chapter 4, Section 4.2. The classical System V inode's pointer scheme and the allocation of data blocks.
Kerrisk, M. — The Linux Programming Interface, Chapter 14, File Systems. The file-related interfaces: stat, statvfs, and the allocation-related system calls.
Love, R. — Linux Kernel Development, 3rd ed., Chapter 13, The Virtual File System. The VFS file operations and the address_space structure.
Linux man pages: man 2 stat, man 2 statvfs, man 2 fallocate, man 8 filefrag, man 1 debugfs, man 8 tune2fs, man 5 ext4, man 5 xfs, man 5 btrfs.

Reading strategy

Read the Silberschatz section first for the formal classification of allocation methods — contiguous, linked, indexed — and for the standard diagrams that show how each method maps a file's logical blocks to physical blocks. Then read OSTEP's treatment of the inode's pointer scheme and the Fast File System's block groups, which establishes the vocabulary and shows how the classical methods are refined in practice. The Fast File System paper is worth reading for the discussion of how allocation interacts with the disk's geometry and why the original Unix file system's performance degraded over time. Finally, the Linux kernel's allocation implementation — ext4's extents and block groups, XFS's allocation groups, Btrfs's extent tree — is the practical view, and it is what the interactive activity will let you observe. Pay particular attention to the difference between the logical view of a file (a sequence of bytes) and the physical view (a set of blocks on the device); the allocation method is the bridge between the two.

04 Core content

4.1 The allocation problem

A file is a sequence of bytes, and the file system presents it to programs as a sequence of logical blocks: block 0, block 1, block 2, and so on. A storage device is a sequence of physical blocks: sector 0, sector 1, and so on. The file system must map each logical block of each file to a physical block on the device, and it must be able to find the physical block for any logical block on demand.

The mapping is the file system's allocation method. It is recorded in the file's metadata — in the inode, or in a structure the inode points to — and it is read every time the file is accessed. The allocation method's properties determine:

Sequential access performance. How fast can the file system read the file from beginning to end? A method that places a file's blocks consecutively on the device gives the highest sequential throughput, because the device can read the blocks without seeking.
Random access performance. How fast can the file system read an arbitrary block of the file? A method that records the location of each block independently gives the fastest random access; a method that requires following a chain of pointers gives the slowest.
Growth characteristics. Can the file grow after it is created? A contiguous method requires the file's final size to be known in advance, or it must move the file when it grows; a linked or indexed method allows the file to grow without moving.
Space overhead. How much space is consumed by the metadata that records the mapping? A method that stores a pointer in every block (linked allocation) wastes space that could hold data; a method that stores the mapping in the inode (extents) uses much less.
Fragmentation. How much does the method suffer from external fragmentation — the inability to use free space because it is broken into pieces too small for the next file? A contiguous method suffers the most; a method that allocates block by block suffers the least.

No single method is best on all five dimensions. The classical methods each optimize a different subset, and the modern methods are refinements that combine their strengths. The following sections present each method in turn.

4.2 Contiguous allocation

Contiguous allocation stores a file's blocks in consecutive physical blocks on the device. The file's metadata records the starting block and the length in blocks, and the mapping is trivial: the i-th logical block is at physical block start + i.

The method's advantages follow directly from the contiguity:

Sequential access is optimal. The device reads the blocks without seeking, so the throughput is limited only by the device's sequential bandwidth. For a hard disk, this is the difference between a few hundred kilobytes per second (random access) and a few hundred megabytes per second (sequential access).
Random access is fast. The mapping is a single addition, so the file system can compute the physical block for any logical block without reading metadata. Only one seek is required.
Metadata is minimal. The mapping requires only two numbers — the start block and the length — regardless of the file's size. For a large file, the metadata is negligible.

The method's disadvantages are equally direct:

External fragmentation. As files are created and deleted, the free space becomes broken into pieces. A new file that requires a contiguous run of k blocks may not fit, even if the total free space is larger than k blocks. The free space is eventually so fragmented that the file system cannot satisfy large requests.
Growth is difficult. A file that grows must find additional contiguous blocks immediately after its current end. If the next block is in use, the file must be moved to a new, larger contiguous region — an expensive operation that requires copying the file's data. Alternatively, the file system can allocate more space than the file currently needs (a preallocation policy), but this wastes space if the file does not grow to fill it.
Compaction is expensive. The only way to recover from external fragmentation is to move files to consolidate the free space. Compaction requires reading and rewriting the files' data, and it is impractical for large file systems because it takes hours and cannot be done while the file system is in use.

Contiguous allocation is used by write-once media (CDs, DVDs) and by some specialized file systems, but it is not used by general-purpose file systems because of its fragmentation and growth problems. Its place in the modern world is as a conceptual baseline: the other methods are described by contrast with it.

Figure 10.5 — File allocation methods. Contiguous allocation stores a file's blocks consecutively and records only the start and length; sequential access is optimal but growth and fragmentation are problems. Linked allocation scatters the blocks and stores a pointer in each block; growth is easy but random access is slow. Indexed allocation stores the pointers in a separate index block; random access is fast and there is no external fragmentation, but the index block adds overhead. Modern file systems use extents, a refinement of indexed allocation that records ranges of contiguous blocks rather than individual blocks.

4.3 Linked allocation and the File Allocation Table

Linked allocation stores a file's blocks anywhere on the device and links them into a chain: each block contains a pointer to the next block in the file. The file's metadata records the first block (and, optionally, the last block), and the mapping for logical block i is found by following the chain from the first block i times.

The method's advantages address the contiguous method's weaknesses:

No external fragmentation. Any free block can be used for any file, so the free space is never broken into pieces too small to use. The file system can always satisfy a request as long as the total free space is sufficient.
Growth is easy. A file that grows simply allocates a new block and links the current last block to it. No moving, no preallocation, no contiguous run required.
Metadata is minimal. The file's metadata records only the first (and optionally the last) block, regardless of the file's size.

The method's disadvantages are significant:

Random access is slow. To read logical block i, the file system must read blocks 0 through i − 1 to follow the chain to block i. For a large file, this is a linear scan of the file's blocks, and each block read requires a disk access. Random access is therefore O(n) in the file's length, which is unacceptable for files that are accessed randomly (databases, executable images, virtual memory backing stores).
Pointer overhead. Each block must reserve space for the pointer to the next block. If the pointer is 4 bytes and the block is 4 KB, the overhead is 0.1%, which is small; but the pointer's presence complicates the block's layout, because the file's data cannot use the full block.
Reliability. A single corrupted or lost pointer breaks the chain, and the rest of the file becomes unreachable. The file system must therefore validate the chain (or use a redundant structure, such as the File Allocation Table) to detect corruption.

The classical refinement of linked allocation is the File Allocation Table (FAT), used by MS-DOS and its descendants. In FAT, the pointers are not stored in the data blocks; they are stored in a separate table, one entry per physical block. The table's entry for a block gives the next block in the chain (or a special value for "free" or "end of file"). The file's metadata records only the first block, and the chain is followed through the table.

The FAT has two advantages over the in-block pointer scheme. First, the data blocks are not reduced by the pointer's size, so the file's data can use the full block. Second, the table can be cached in memory, so following the chain is a memory operation rather than a disk operation. The table's disadvantage is its size: for a device with N blocks, the table has N entries, and each entry is a few bytes. For a 1 TB device with 4 KB blocks, the table has 256 million entries; at 4 bytes each, that is 1 GB of table — a significant fraction of the device's capacity. The FAT's size is the reason it is used only on small devices (USB flash drives, memory cards) and not on large file systems.

4.4 Indexed allocation

Indexed allocation stores the file's block pointers in a separate index block. The file's metadata records the index block's address, and the mapping for logical block i is found by reading the index block's i-th entry. The index block is a table of pointers: entry 0 points to the file's first block, entry 1 to the second, and so on.

The method's advantages are the best of both classical worlds:

Random access is fast. The mapping for logical block i is a single index-block read followed by a single data-block read — two disk accesses, regardless of the file's size. This is the method's principal advantage over linked allocation.
No external fragmentation. As with linked allocation, any free block can be used for any file, so the free space is never broken into unusable pieces.
Growth is easy. A file that grows allocates a new block and adds its pointer to the index block. If the index block is full, the file system allocates a new index block and links it to the first (this is the multi-level scheme described below).

The method's disadvantage is the index block's overhead. A file that is smaller than one block still requires an index block, which wastes space; a file that is exactly one block long requires an index block plus a data block, which doubles the file's space consumption. The classical Unix file system addresses this by using a hybrid scheme: the inode itself holds a small number of direct pointers (typically 12) that point directly to the file's first blocks, plus a single indirect pointer, a double indirect pointer, and a triple indirect pointer that point to index blocks of increasing depth.

The multi-level index scheme works as follows. The inode's direct pointers cover the file's first 12 blocks. The single indirect pointer points to an index block whose entries cover the next k blocks (where k is the number of pointers in a block, typically 1024 for a 4 KB block with 4-byte pointers). The double indirect pointer points to an index block whose entries point to index blocks, covering k² blocks. The triple indirect pointer covers k³ blocks. For a 4 KB block and 4-byte pointers, the maximum file size is 12 + 1024 + 1024² + 1024³ blocks, which is about 4 TB — large enough for most purposes, and the scheme's overhead is proportional to the file's size, not to the device's size.

The multi-level scheme is a classic example of a space-time trade-off. Small files use only the direct pointers, so their metadata overhead is minimal. Large files use the indirect pointers, so their metadata grows with their size, but the growth is logarithmic: a file of n blocks requires O(log n) index blocks, not O(n). The scheme's lookup cost is also logarithmic: a file of n blocks requires O(log n) index reads to find the block for a given logical address, which is fast even for very large files.

4.5 Extents: the modern approach

Indexed allocation records the location of every block individually, which is wasteful for large files that are stored contiguously or nearly contiguously. A file of 1 million blocks that is stored in a single contiguous run requires 1 million index entries, even though the run could be described by two numbers — the starting block and the length. Extents solve this problem by recording ranges of contiguous blocks rather than individual blocks.

An extent is a pair (or triple) of numbers: the logical block where the extent begins, the physical block where the extent begins, and the length of the extent in blocks. A file's metadata is a list of extents, and the mapping for a logical block is found by locating the extent whose logical range contains the block and computing the physical block as physical_start + (logical_block − logical_start).

The extent approach is a refinement of indexed allocation: it is an index, but the index's entries cover ranges rather than individual blocks. The advantage is a dramatic reduction in metadata size for large, contiguous files. A file of 1 million contiguous blocks requires one extent (three numbers) rather than 1 million index entries. A file of 1 million blocks stored in 1,000 extents requires 1,000 extents, which is still far less than 1 million entries.

The extent approach is used by modern file systems:

ext4 uses extents instead of the classical indirect-block scheme. A file's inode holds up to four extents directly, and a larger file uses an extent tree (a B-tree of extents) that is rooted in the inode.
XFS uses extents for all file data, with a B+tree of extents for large files. XFS was designed around extents from the beginning, and its allocation policies are extent-aware.
Btrfs uses extents as part of its extent tree, a B-tree that records the location of every extent in the file system. Btrfs's extent tree is one of the file system's central structures.
NTFS uses extents (called runs) in its Master File Table records. A file's metadata is a sequence of runs, each of which describes a contiguous range of blocks.

The extent's disadvantage is the same as the index block's: it adds metadata overhead for small files that would not benefit from the range compression. Modern file systems mitigate this by storing a few extents directly in the inode (ext4's four extents) or by storing small files entirely within the inode's metadata (ext4's inline data feature, NTFS's resident files). The result is a scheme that is efficient for both small and large files.

Extents and the "three easy pieces"

OSTEP describes the extent as a generalization of the index block: instead of one pointer per block, the index stores one entry per run of blocks. The idea is the same as the difference between a linked list and a run-length encoding of a sequence: the run-length encoding compresses a long sequence of identical values (here, "the next block is one greater than the current block") into a single entry. The extent is the file system's run-length encoding of its block map.

4.6 Block groups and allocation policies

The allocation method determines how a file's blocks are recorded, but it does not determine where the blocks are placed on the device. That decision is made by the allocation policy, and it is one of the file system's most important performance decisions.

The classical Unix file system (System V) placed a file's blocks wherever the free-space management structure indicated, with the result that a file's blocks were often scattered across the device. As the device filled, the scatter became worse, and the file system's performance degraded — a phenomenon that the Fast File System paper called the file system's aging. The Fast File System's solution was the block group (originally called a cylinder group): the device is divided into groups of consecutive blocks, each with its own inode table, block bitmap, and free-space information. The file system places a file's inode and data blocks in the same group when possible, so that the file's metadata and data are close together, and it places related files in the same group.

The block group's purpose is locality: by keeping a file's inode and data blocks near each other (in the same group, and ideally in the same region of the group), the file system reduces the number of seeks required to read the file. The improvement is significant on hard disks, where a seek costs several milliseconds, and it remains useful on SSDs, where locality reduces the number of flash-translation-layer lookups and the write amplification.

Modern file systems use variations of the block group:

ext2/ext3/ext4 use block groups with per-group inode tables, block bitmaps, and inode bitmaps. The default allocation policy places a new file's inode in the same group as its parent directory, and its data blocks in the same group as its inode.
XFS uses allocation groups, which are larger than ext4's block groups and are managed independently. XFS's allocation policy is extent-aware and tries to place a file's extents in the same allocation group.
Btrfs uses chunks and block groups that are allocated dynamically from a pool of free space. Btrfs's allocation policy is designed for copy-on-write and for the file system's snapshot and RAID features.

The allocation policy's details vary between file systems, but the general principles are the same: place related data close together, keep a file's metadata and data in the same region, and use the free-space information to choose blocks that minimize the file's fragmentation. The policy's effect is largest on hard disks, where the seek time dominates, and it is smallest on SSDs, where the access time is uniform. But even on SSDs, the policy matters for write amplification: a file that is stored contiguously can be written with fewer flash erase-block operations than a file that is scattered.

4.7 Free-space management

The allocation policy needs to know which blocks are free. The file system maintains a free-space management structure that records the state of every block, and it updates the structure when blocks are allocated or freed.

The classical free-space structures are:

Block bitmap: A bitmap with one bit per physical block. A bit is 1 if the block is free and 0 if it is allocated (or vice versa). The bitmap is simple, compact (one bit per block), and efficient for finding a free block (the file system scans the bitmap for a 1 bit). Its disadvantage is its size: for a device with N blocks, the bitmap is N bits, which is 1/32 of the device's capacity for a 4 KB block. For a 1 TB device, the bitmap is 32 MB, which is manageable. ext2/ext3/ext4 and NTFS use bitmaps.
Free list: A linked list of free blocks. The file system allocates a block by removing it from the list's head and frees a block by adding it to the head. The free list's advantage is that it uses no space for allocated blocks; its disadvantage is that finding a contiguous run of free blocks requires traversing the list, which is slow. The free list is used by some file systems for specific purposes (e.g., the free list of free inodes), but it is not used as the primary free-space structure by modern file systems.
Grouping: The free blocks are grouped into sets of k blocks, and the file system tracks the groups rather than the individual blocks. The first block of each group holds the addresses of the next k − 1 free blocks and a pointer to the next group. The grouping structure is a compromise between the bitmap and the free list: it is more compact than the free list and more efficient for finding contiguous runs than a simple list. It is used by some file systems for very large devices, where a full bitmap would be too large.

The free-space structure is updated transactionally on journaling file systems (Lesson 10.6), so a crash during an allocation does not leave the structure inconsistent with the file's metadata. On ext4, the block bitmap is part of the block group's metadata, and it is journaled along with the inode and the directory entry. On XFS and Btrfs, the free-space structure is part of the file system's metadata tree and is updated through the same mechanism as the file's extents.

4.8 Fragmentation

Fragmentation is the condition in which the free space is broken into pieces too small or too scattered to be used efficiently. It is the classical file system's principal long-term problem, and it is the reason the Fast File System's block groups and allocation policies were developed.

There are two kinds of fragmentation:

Internal fragmentation is the space wasted inside an allocated unit. A file that is 5 KB long and is allocated in 4 KB blocks occupies two blocks (8 KB), so 3 KB is wasted. The waste is internal to the file's allocation, and it is unavoidable when the allocation unit is larger than the file's last piece. Larger blocks reduce the metadata overhead but increase internal fragmentation; smaller blocks do the reverse. The choice of block size is therefore a trade-off, and modern file systems use 4 KB blocks as a compromise.
External fragmentation is the space wasted because the free blocks are scattered and cannot be combined into a large enough contiguous run. It is a problem for contiguous allocation, where a file needs a contiguous run; it is not a problem for linked or indexed allocation, where a file can use any free blocks. The extent-based methods are a middle ground: they prefer contiguous runs (for the extents' efficiency) but can fall back to scattered blocks when necessary.

The file system's allocation policy determines how quickly fragmentation develops. A policy that always allocates the first free block (first-fit) leaves the free space fragmented; a policy that allocates the best-fitting block (best-fit) leaves the free space in small pieces; a policy that allocates from a designated region (the block group) keeps the free space in each group reasonably large. Modern file systems use a combination of policies: they allocate from the block group that contains the file's parent directory, they use a free-space structure that records the largest free run, and they use delayed allocation to batch the allocation decisions and choose better blocks.

Delayed allocation is a technique used by ext4 and other modern file systems. Instead of allocating blocks when the data is written to the page cache, the file system delays the allocation until the data is flushed to disk. The delay allows the file system to see more of the file's data before deciding where to place it, so it can allocate larger contiguous extents and reduce fragmentation. The trade-off is that the file's block map is not known until the flush, which complicates some operations (e.g., mmap and fsync), and it can cause data loss if the system crashes before the flush (which is why fsync forces the allocation).

4.9 Allocation in practice

The major file systems' allocation strategies are summarized in the following table.

Allocation strategies of major file systems
File system	Allocation method	Free-space structure	Locality mechanism
ext2	Indexed (direct + indirect blocks)	Block bitmap per block group	Block groups
ext3	Indexed (direct + indirect blocks)	Block bitmap per block group	Block groups, journaling
ext4	Extents (extent tree in inode)	Block bitmap per block group	Block groups, delayed allocation, multiblock allocator
XFS	Extents (B+tree of extents)	Free-space B+tree per allocation group	Allocation groups, extent-aware policies
Btrfs	Extents (extent tree)	Free-space tree, space cache	Chunks, block groups, copy-on-write
NTFS	Extents (runs in MFT record)	Bitmap	MFT zones, allocation policies
FAT32	Linked (File Allocation Table)	FAT entries	None (FAT is global)

The table shows the clear trend: modern file systems use extents, free-space bitmaps or B+trees, and locality mechanisms (block groups, allocation groups, or chunks). The classical methods — contiguous, linked, and simple indexed — remain important as conceptual foundations, and they are still used in specialized contexts (FAT32 on removable media, the classical indirect blocks in ext2's legacy format), but the general-purpose file systems have moved to extents and locality-aware allocation.

4.10 Common misconceptions

"A file is stored in one contiguous region."

A file's blocks are usually not contiguous. The file system allocates blocks as they are needed, and the free space is rarely a single contiguous region. Extents reduce the number of separate regions, but a large file is still typically stored in several extents.

"Linked allocation is obsolete."

Linked allocation is still used by FAT32, which is the file system on most USB flash drives and memory cards. Its simplicity and its small metadata footprint make it suitable for small devices, even though it does not scale to large ones.

"Indexed allocation always uses an index block."

Indexed allocation uses an index block when the file is large enough to need one. The classical Unix inode holds direct pointers for the first 12 blocks, so a small file needs no index block at all. Modern file systems store a few extents directly in the inode, so a small file needs no separate extent tree.

"Extents are just large blocks."

An extent is a range of blocks, not a larger block. The file system still allocates and reads individual blocks; the extent is a description of a range, not a unit of allocation. The distinction matters because the extent's length is variable: a file can have extents of different lengths, and the file system can split an extent when part of it is freed.

"Block groups are about physical disk geometry."

Block groups were originally motivated by disk geometry (the cylinder group matched the disk's physical organization), but modern file systems use them for locality and for parallelism. On an SSD, the block group does not correspond to a physical region, but it still serves to keep related data together and to allow concurrent allocation in different groups.

"Fragmentation is only a problem for hard disks."

Fragmentation matters on SSDs too, although for different reasons. A fragmented file requires more flash-translation-layer lookups and can cause more write amplification, which reduces the SSD's lifetime. Modern SSDs' controllers hide much of the effect, but the file system's allocation policy still matters.

"Delayed allocation is just a performance optimization."

Delayed allocation improves performance by allowing the file system to allocate larger contiguous extents, but it also changes the file system's crash semantics. Data that is written but not yet flushed may not have a block map, so a crash can lose data that the application believes is committed. The application must call fsync to force the allocation and the flush.

"The file system's allocation policy is fixed."

Most file systems allow the allocation policy to be tuned — through mount options, through the file system's parameters, or through tools like tune2fs. The default policy is designed for general-purpose use, but a specialized workload (a database, a media server, a build farm) may benefit from a different policy.

05 Worked example

The following example traces a file's allocation under each of the classical methods, computes the cost of reading the file's blocks, and demonstrates the extent-based approach's metadata savings.

Allocating a 100-block file under three methods

Consider a file of 100 logical blocks (400 KB, with 4 KB blocks). Assume the device has 1,000 physical blocks, and the free space is fragmented: the free blocks are the ranges 100–199, 350–449, 600–699, 800–899, and 950–999. The file system must allocate 100 blocks for the file.

Contiguous allocation. The file needs a contiguous run of 100 blocks. The free ranges are each 100 blocks long, so the file can be placed in any of them — for example, blocks 100–199. The metadata records start=100 and length=100.

Linked allocation. The file's blocks can be scattered across the free ranges. The file system allocates blocks from the free ranges in order, and each block's pointer links to the next. The file's metadata records first=100 and (optionally) last=999. The chain runs through all five free ranges.

Indexed allocation. The file needs an index block plus 100 data blocks. The index block is allocated from a free range (say, block 350), and the data blocks are allocated from the remaining free blocks. The metadata records index=350.

Extent-based allocation. The file's blocks are grouped into extents that match the free ranges. The file has five extents:

Extent	Logical start	Physical start	Length
0	0	100	100
1	100	350	100
2	200	600	100
3	300	800	100
4	400	950	50

Wait — the file is 100 blocks long, but the free ranges total 500 blocks. The file uses the first 100 blocks of the free space: the range 100–199 (100 blocks). The remaining extents are not needed. This is the point: the file system can allocate the file in a single extent if the free space is sufficiently large, and it uses additional extents only when necessary.

If the free space is fragmented into ranges of 20 blocks each, the file needs five extents, one per range. The metadata is five extents (15 numbers) rather than 100 index entries or 100 pointers.

Cost of reading the file's blocks

Suppose a program reads the file's logical block 50, then its logical block 75, then its logical block 25. The cost of each read depends on the allocation method.

Method	Read block 50	Read block 75	Read block 25
Contiguous	1 seek + 1 read	1 seek + 1 read	1 seek + 1 read
Linked	51 reads (follow chain)	76 reads	26 reads
Indexed	1 index read + 1 data read	1 index read + 1 data read	1 index read + 1 data read
Extent	1 extent lookup + 1 data read	1 extent lookup + 1 data read	1 extent lookup + 1 data read

The table makes the methods' trade-offs concrete. Contiguous allocation gives the best access cost, but it cannot always satisfy a request (the free space may not have a large enough contiguous run). Linked allocation can always satisfy a request, but its access cost is O(n) in the file's length. Indexed allocation gives O(1) access cost regardless of the block's position, at the cost of an index block. Extent-based allocation gives O(1) access cost with less metadata overhead than indexed allocation, which is why modern file systems use it.

Metadata size for a large file

Consider a file of 1 million blocks (4 GB). The metadata size for each method is:

Method	Metadata size	Notes
Contiguous	2 numbers (8 bytes)	start + length
Linked (FAT)	4 MB (1 M entries × 4 bytes)	The FAT is global, so the file's metadata is the chain, but the FAT itself is 4 MB
Indexed (single-level)	4 MB (1 M entries × 4 bytes)	One index block per 1,024 data blocks, so about 977 index blocks
Indexed (multi-level)	~4 MB + tree overhead	The indirect blocks add a few thousand entries
Extents (1 extent)	12 bytes (3 numbers)	If the file is contiguous
Extents (1,000 extents)	12 KB (1,000 × 12 bytes)	If the file is fragmented into 1,000 extents

The extent-based method's metadata savings are dramatic. A contiguous 4 GB file requires 12 bytes of metadata with extents, versus 4 MB with a single-level index or a FAT. Even a fragmented file with 1,000 extents requires only 12 KB, which is still far less than 4 MB. The savings are the reason extents are used by all modern file systems.

Inspecting allocation on a live system

The Linux filefrag command shows a file's extents. The following example creates a fragmented file and examines its extents.

# Create a file and write to it
dd if=/dev/urandom of=/tmp/frag.bin bs=4k count=1000

# Show the file's extents
filefrag -v /tmp/frag.bin

# The output shows the extent number, the logical block,
# the physical block, and the length of each extent.
# A file with many extents is fragmented; a file with few
# extents is contiguous.

The filefrag output's "extents" count is the number of separate extents in the file. A file with one extent is perfectly contiguous; a file with many extents is fragmented. The command's -v option shows the mapping between logical and physical blocks, which is the file system's allocation map for the file.

On ext4, the debugfs command can show the inode's extent tree directly:

# Show the inode's extent tree
sudo debugfs -R 'stat /tmp/frag.bin' /dev/sda1 2>/dev/null

# The output includes the inode's direct extents and,
# for large files, the extent tree's blocks.

The debugfs output is the file system's internal view of the file's allocation. It shows the extents that the inode records and the extent tree that the file system uses for large files.

06 Interactive activity

Activity · explore file allocation on a live system

The goal of this activity is to use the Linux command line to observe a file's allocation, to measure the effect of fragmentation, and to demonstrate the extent-based approach's behaviour. Work through the steps in your course VM.

Observe a file's allocation. Create a file and use filefrag to see its extents.
```
# Create a file
dd if=/dev/zero of=/tmp/contig.bin bs=1M count=10

# Show the extents
filefrag /tmp/contig.bin
filefrag -v /tmp/contig.bin
```
The output shows the number of extents. A file that was created in one operation is usually stored in a single extent (or a few extents), which means it is contiguous. The -v option shows the logical and physical block numbers, which is the file's allocation map.
Create a fragmented file. Create a file by writing in small pieces, with other files created in between, and observe the fragmentation.
```
# Create a fragmented file
mkdir /tmp/frag-demo
cd /tmp/frag-demo
for i in $(seq 1 100); do
    dd if=/dev/zero of=file$i bs=4k count=10 2>/dev/null
    dd if=/dev/zero of=interloper$i bs=4k count=10 2>/dev/null
done

# Show the extents of one of the files
filefrag -v file50
```
The interleaved files cause the file system to scatter each file's blocks, so the files have many extents. Compare the extent count to the contiguous file's count.
Measure the effect of fragmentation. Read a contiguous file and a fragmented file, and compare the throughput.
```
# Read a contiguous file
time cat /tmp/contig.bin > /dev/null

# Read a fragmented file
time cat /tmp/frag-demo/file50 > /dev/null

# Drop the caches and repeat
sync
echo 3 | sudo tee /proc/sys/vm/drop_caches
time cat /tmp/contig.bin > /dev/null
time cat /tmp/frag-demo/file50 > /dev/null
```
The fragmented file's read is slower because the device must seek between the extents. On an SSD the difference is smaller, but it is still measurable for large files.
Inspect the inode's allocation. Use debugfs to examine the inode's extent tree.
```
# Find the file system device
df -T /tmp
# Use the device name from the output (e.g., /dev/sda1)

# Examine the inode
sudo debugfs -R 'stat /tmp/contig.bin' /dev/sda1 2>/dev/null

# The output shows the inode's fields, including the
# extent tree's root and the direct extents.
```
The debugfs output shows the file's inode, its size, its block count, and its extent tree. For a large file, the extent tree has multiple levels; for a small file, the inode's direct extents cover the entire file.
Compare file systems. If your VM has multiple file systems (ext4, XFS, Btrfs), create the same file on each and compare the extent counts.
```
# Check the file system types
df -T

# Create the same file on each file system
for fs in / /tmp /var; do
    echo "=== $fs ==="
    dd if=/dev/zero of=$fs/testfile bs=1M count=10 2>/dev/null
    filefrag $fs/testfile
    rm $fs/testfile
done
```
The extent counts differ because the file systems' allocation policies differ. ext4, XFS, and Btrfs all use extents, but their policies for choosing extents are different.
Observe delayed allocation. On ext4, the delalloc feature delays block allocation until the data is flushed. Observe the difference between writing a file and flushing it.
```
# Write a file without flushing
dd if=/dev/zero of=/tmp/delalloc.bin bs=1M count=100

# Immediately check the extents (the file may have
# no extents yet, because the allocation is delayed)
filefrag /tmp/delalloc.bin

# Flush the data
sync

# Check the extents again
filefrag /tmp/delalloc.bin
```
Before the flush, the file may have no extents or fewer extents; after the flush, the file has its final allocation. The difference is delayed allocation's effect: the file system waits until it has more data before deciding where to place it.
Examine the free-space structure. Use dumpe2fs to see the block groups and their free-space counts.
```
# Show the block group information
sudo dumpe2fs /dev/sda1 2>/dev/null | head -60

# The output shows each block group's number of free
# blocks, free inodes, and the location of the block
# bitmap and inode bitmap.
```
The block groups' free-space counts show how the free space is distributed. A file system with many groups and uneven free-space counts is one where the allocation policy has placed data unevenly.
Read the man pages. Read the man pages that document the allocation interface.
```
man 2 fallocate
man 2 statvfs
man 8 filefrag
man 1 debugfs
man 5 ext4
man 5 xfs
man 5 btrfs
```
For each, write a sentence describing its main contribution to your understanding of file allocation. The man 2 fallocate page documents the preallocation interface; the man 2 statvfs page documents the file system statistics; the man 8 filefrag page documents the extent-reporting tool.

Reflect: file allocation is one of those topics that is invisible when it works and painful when it does not. A well-allocated file reads at the device's full bandwidth; a poorly allocated file reads at a fraction of it. The file system's allocation policy is a compromise between the simplicity of the classical methods and the performance of the modern ones, and the compromise is shaped by the workloads the file system expects to see. Which workloads in your own experience are most sensitive to file allocation? What would you do to make those workloads more efficient — would you change the file system, change the allocation policy, or change the workload's access pattern? What is the right balance between the file system's automatic policies and the application's explicit control (through fallocate, for example)?

07 Knowledge check

Check your understanding

Question 1

Define the allocation problem. What are the properties that an allocation method must balance, and why is no single method best on all of them?

Show answer

The allocation problem is the problem of mapping a file's logical blocks (block 0, block 1, …) to physical blocks on the storage device, and of recording the mapping so that it can be found again. The file system must be able to find the physical block for any logical block on demand, and it must update the mapping when the file grows or shrinks. An allocation method must balance five properties. Sequential access performance is how fast the file can be read from beginning to end; a method that places a file's blocks consecutively gives the highest throughput. Random access performance is how fast an arbitrary block can be read; a method that records each block's location independently gives the fastest random access. Growth characteristics are whether the file can grow after it is created; a contiguous method requires the final size to be known in advance, while a linked or indexed method allows growth without moving. Space overhead is how much space the metadata consumes; a method that stores a pointer in every block wastes space, while a method that stores the mapping in the inode uses little. Fragmentation is how much the method suffers from external fragmentation; a contiguous method suffers the most, and a method that allocates block by block suffers the least. No single method is best on all five properties because they conflict. Contiguous allocation gives excellent sequential and random access but suffers from external fragmentation and cannot grow easily. Linked allocation has no external fragmentation and grows easily but has slow random access and pointer overhead. Indexed allocation gives fast random access and no external fragmentation but requires an index block for every file. Extents reduce the index block's overhead for large files but still require metadata. The choice of method is therefore a compromise, and the modern file systems' extent-based methods are the current best balance for general-purpose use.

Question 2

Describe contiguous allocation. What are its advantages and disadvantages, and why is it not used by general-purpose file systems?

Show answer

Contiguous allocation stores a file's blocks in consecutive physical blocks on the device. The file's metadata records the starting block and the length in blocks, and the mapping for logical block i is start + i. The advantages follow from the contiguity. Sequential access is optimal, because the device reads the blocks without seeking; on a hard disk this is the difference between a few hundred kilobytes per second and a few hundred megabytes per second. Random access is fast, because the mapping is a single addition and requires only one seek. Metadata is minimal, because the mapping requires only two numbers regardless of the file's size. The disadvantages are equally direct. External fragmentation develops as files are created and deleted: the free space becomes broken into pieces, and a new file that requires a contiguous run may not fit even when the total free space is sufficient. Growth is difficult, because a file that grows must find additional contiguous blocks immediately after its current end; if the next block is in use, the file must be moved to a new, larger contiguous region, which requires copying its data. Compaction — moving files to consolidate the free space — is the only way to recover from fragmentation, and it is impractical for large file systems because it takes hours and cannot be done while the file system is in use. Contiguous allocation is not used by general-purpose file systems because of these fragmentation and growth problems. It is used by write-once media (CDs, DVDs), where the data is written once and never modified, and it is a conceptual baseline for describing the other methods.

Question 3

Describe linked allocation and the File Allocation Table. What are the trade-offs between the in-block pointer scheme and the FAT?

Show answer

Linked allocation stores a file's blocks anywhere on the device and links them into a chain: each block contains a pointer to the next block in the file. The file's metadata records the first block (and optionally the last), and the mapping for logical block i is found by following the chain i times. The method has no external fragmentation (any free block can be used for any file), grows easily (a new block is simply linked to the current last block), and requires minimal metadata (only the first and last blocks). Its disadvantages are slow random access (reading block i requires reading all preceding blocks), pointer overhead (each block reserves space for the pointer), and reliability (a corrupted pointer breaks the chain and makes the rest of the file unreachable). The File Allocation Table (FAT) is a refinement in which the pointers are not stored in the data blocks but in a separate table, one entry per physical block. The table's entry for a block gives the next block in the chain, and the file's metadata records only the first block. The FAT has two advantages over the in-block pointer scheme. First, the data blocks are not reduced by the pointer's size, so the file's data can use the full block. Second, the table can be cached in memory, so following the chain is a memory operation rather than a disk operation. The FAT's disadvantage is its size: for a device with N blocks, the table has N entries, and each entry is a few bytes. For a 1 TB device with 4 KB blocks, the table has 256 million entries; at 4 bytes each, that is 1 GB — a significant fraction of the device's capacity. The FAT is therefore used only on small devices (USB flash drives, memory cards) and not on large file systems. The trade-off between the two schemes is thus: the in-block pointer scheme uses less memory but reduces the data blocks' capacity; the FAT preserves the data blocks' capacity but requires a large table in memory.

Question 4

Describe indexed allocation and the multi-level index scheme. How does the scheme balance the needs of small and large files?

Show answer

Indexed allocation stores the file's block pointers in a separate index block. The file's metadata records the index block's address, and the mapping for logical block i is found by reading the index block's i-th entry. The method gives fast random access (one index read plus one data read, regardless of the block's position), has no external fragmentation, and grows easily. Its disadvantage is the index block's overhead: a file that is smaller than one block still requires an index block, and a file that is exactly one block long requires an index block plus a data block. The multi-level index scheme addresses this by using a hybrid: the inode holds a small number of direct pointers (typically 12) that point directly to the file's first blocks, plus a single indirect pointer that points to an index block, a double indirect pointer that points to an index block whose entries point to index blocks, and a triple indirect pointer that covers even more blocks. The scheme balances the needs of small and large files. A small file uses only the direct pointers, so its metadata overhead is minimal — no index block is needed. A large file uses the indirect pointers, so its metadata grows with its size, but the growth is logarithmic: a file of n blocks requires O(log n) index blocks, not O(n). The lookup cost is also logarithmic: a file of n blocks requires O(log n) index reads to find the block for a given logical address. For a 4 KB block and 4-byte pointers, the maximum file size is 12 + 1024 + 1024² + 1024³ blocks, which is about 4 TB. The scheme is a classic space-time trade-off: it uses the minimum metadata for small files and scales logarithmically for large ones.

Question 5

What is an extent? How does it improve on single-block indexing, and why do modern file systems use extents rather than the classical indirect-block scheme?

Show answer

An extent is a range of contiguous blocks, described by a small number of values: the logical block where the extent begins, the physical block where the extent begins, and the length of the extent in blocks. A file's metadata is a list of extents, and the mapping for a logical block is found by locating the extent whose logical range contains the block and computing the physical block as physical_start + (logical_block − logical_start). An extent improves on single-block indexing by compressing a range of blocks into a single entry. A file of 1 million blocks that is stored contiguously requires 1 million index entries with single-block indexing, but only one extent (three numbers) with extents. A file that is fragmented into 1,000 extents requires 1,000 extent entries, which is still far less than 1 million index entries. The metadata savings are dramatic: for a 4 GB file, the classical indirect-block scheme requires about 4 MB of index blocks, while the extent scheme requires 12 bytes for a contiguous file or about 12 KB for a file with 1,000 extents. Modern file systems use extents rather than the classical indirect-block scheme for three reasons. First, the metadata savings: the extent scheme uses far less space, which is important for large files and for file systems with many files. Second, the lookup efficiency: finding the extent for a logical block is a search in a sorted list or a B-tree, which is fast even for files with many extents. Third, the allocation efficiency: the file system can allocate a large contiguous extent in one operation, which reduces fragmentation and improves sequential throughput. ext4 uses extents with an extent tree rooted in the inode; XFS uses a B+tree of extents; Btrfs uses an extent tree that is shared with the rest of the file system's metadata; and NTFS uses runs in its Master File Table records. The extent is the modern file system's standard allocation method.

08 Unit discussion

Discussion prompt

The allocation problem is one of the oldest problems in file system design, and its solutions have evolved through several distinct generations. The first file systems used contiguous allocation, because it was the simplest and the fastest. When fragmentation made it impractical, linked allocation replaced it, because it could use any free block. When random access became important, indexed allocation replaced linked allocation, because it could find any block in constant time. When the index blocks' overhead became significant, extents replaced single-block indexing, because they could describe a large file with a few entries. Each generation was a response to the limitations of the previous one, and each was shaped by the workloads of its time.

The trend is unmistakable: the file system's allocation metadata is becoming more compact and more structured. The classical indirect-block scheme stores one pointer per block; the extent scheme stores one entry per run of blocks; the modern file systems' B-trees store the runs in a sorted, balanced structure that supports both lookups and range queries. The allocation metadata is becoming a database — a small, specialized database that describes the file's layout on the device, with the same B-tree structures and the same transaction semantics that a general-purpose database uses.

If the allocation metadata is a database, should the application be able to query it? Some systems have proposed this: the extent-based interface allows an application to specify the extents it wants; the fallocate system call allows an application to preallocate a contiguous region; and the FIEMAP ioctl allows an application to retrieve a file's extent map. Each of these interfaces gives the application more control over the file's allocation, at the cost of more complexity. Most applications ignore them, because the file system's automatic policies are good enough for general-purpose use. But for specialized workloads — databases, media servers, virtual machine images — the explicit interfaces can make a significant difference.

Should applications have more control over file allocation, or should the file system's automatic policies be the only interface? What are the risks of giving applications control — what happens when an application makes a poor allocation decision? What are the risks of not giving them control — what happens when the file system's policy is wrong for the workload? Post your response to the Unit 10 discussion forum and reply to at least two classmates. Supports CLO1, CLO4, CLO5, and CLO6.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lesson 10.6. Aim to spend 60–90 minutes on it.

Trace the allocation methods. A device has 20 physical blocks. The free blocks are 0–4, 7–9, 12–15, and 18–19. A file of 8 blocks must be allocated. Show the file's allocation under each of the following methods:
- Contiguous allocation (which free range is used?)
- Linked allocation (which blocks are used, and what is the chain?)
- Indexed allocation (which block is the index block, and which blocks are the data blocks?)
- Extent-based allocation (what are the extents?)
For each method, compute the number of metadata entries required.
Compare the methods. Write a short paragraph (200–250 words) comparing contiguous, linked, indexed, and extent-based allocation. Your paragraph should address: (a) the mapping algorithm; (b) the access cost for sequential and random reads; (c) the growth characteristics; (d) the metadata overhead; (e) the fragmentation behaviour; (f) the workloads for which each method is best suited.
Measure the extent count. Create files of different sizes and observe how the extent count changes.
```
# Create files of different sizes
for size in 1 10 100 1000; do
    dd if=/dev/zero of=/tmp/file$size.bin bs=1M count=$size 2>/dev/null
    echo -n "size=${size}MB: "
    filefrag /tmp/file$size.bin | grep -o '[0-9]* extents*'
done
```
How does the extent count grow with the file's size? Does it grow linearly, logarithmically, or not at all? Explain your observation.
Create and measure a fragmented file. Write a program that creates a file by writing one block at a time, with fsync between the writes, and observe the extent count. Then create the same file with a single write and observe the difference.
```
# Write one block at a time, with fsync between writes
for i in $(seq 1 100); do
    dd if=/dev/zero of=/tmp/frag1.bin bs=4k count=1 seek=$i conv=notrunc 2>/dev/null
    sync
done

# Write the same data in one operation
dd if=/dev/zero of=/tmp/contig1.bin bs=4k count=100 2>/dev/null

filefrag /tmp/frag1.bin
filefrag /tmp/contig1.bin
```
Which file has more extents? Why? What does this tell you about the file system's allocation policy?
Examine the free-space structure. Use dumpe2fs to examine the block groups' free-space counts.
```
sudo dumpe2fs /dev/sda1 2>/dev/null | grep -A5 'Group'
```
How many block groups are there? How are the free blocks distributed across the groups? Is the distribution even or uneven? Explain what the distribution tells you about the file system's allocation policy.

Investigate a file's extent tree. Create a large file and use debugfs to examine its extent tree.

# Create a large file
dd if=/dev/zero of=/tmp/large.bin bs=1M count=500

# Examine the inode's extent tree
sudo debugfs -R 'stat /tmp/large.bin' /dev/sda1 2>/dev/null

# Use the extent tree's root block to examine the tree
# (the block number is shown in the stat output)
sudo debugfs -R 'extent_dump <block>' /dev/sda1 2>/dev/null

What does the extent tree look like? How many levels does it have? How does the tree's structure change with the file's fragmentation?

Design an allocation policy. A file system is being designed for a workload that consists of many small files (a few kilobytes each) and a few very large files (gigabytes each). Design an allocation policy for this workload. Consider:
- What block size would you use?
- How would you allocate small files?
- How would you allocate large files?
- How would you handle the large files' growth?
- How would you keep the small files' metadata overhead low?
Justify your design.
Reflect. In your own words, explain why the classical allocation methods (contiguous, linked, indexed) are not sufficient for modern file systems, and describe the two refinements (extents and locality-aware allocation) that modern file systems use. Then describe one situation in your own experience — a program you have written or a system you have used — where file allocation affected performance. What was the workload, and how would a different allocation method have helped?

10 Summary

The allocation problem is the mapping of a file's logical blocks to physical blocks on the storage device. The allocation method determines the file's sequential and random access performance, its growth characteristics, its metadata overhead, and its fragmentation behaviour.
Contiguous allocation stores a file's blocks in consecutive physical blocks. Its advantages are optimal sequential access, fast random access, and minimal metadata. Its disadvantages are external fragmentation, difficult growth, and expensive compaction. It is used by write-once media and is a conceptual baseline for the other methods.
Linked allocation stores a file's blocks anywhere and links them into a chain. It has no external fragmentation and grows easily, but its random access is O(n) in the file's length, and it has pointer overhead. The File Allocation Table (FAT) moves the pointers into a separate table, which can be cached in memory, but the table's size limits it to small devices.
Indexed allocation stores the pointers in a separate index block, giving O(1) random access and no external fragmentation at the cost of the index block's overhead. The multi-level index scheme uses direct pointers for small files and indirect pointers for large ones, balancing the needs of both.
Extents record ranges of contiguous blocks rather than individual blocks, dramatically reducing the metadata overhead for large files. ext4, XFS, Btrfs, and NTFS use extents, and the extent is the modern file system's standard allocation method.
Block groups (or allocation groups, or chunks) divide the device into regions, each with its own metadata and free-space information. Their purpose is locality: keeping a file's inode and data blocks close together, and keeping related files in the same region.
Free-space management uses a block bitmap, a free list, or a grouping structure to track which blocks are available. The structure is updated transactionally on journaling file systems.
Fragmentation is the condition in which the free space is broken into pieces too small or too scattered to be used efficiently. Internal fragmentation is the waste inside an allocated unit; external fragmentation is the waste caused by scattered free blocks. Allocation policies and delayed allocation are the modern file system's responses to fragmentation.
Delayed allocation postpones the allocation decision until the data is flushed, allowing the file system to see more of the file's data and choose larger contiguous extents. It improves allocation quality but changes the crash semantics, so applications must call fsync to force the allocation and the flush.
The modern file systems (ext4, XFS, Btrfs, NTFS) combine extents, free-space bitmaps or B+trees, locality mechanisms, and delayed allocation. The classical methods remain important as conceptual foundations and are still used in specialized contexts, but the general-purpose file systems have moved to extents and locality-aware allocation.

Looking ahead

This lesson presented the allocation of a file's data blocks: the classical methods, the extent-based method, the block groups and policies that decide where blocks are placed, and the free-space structures that track which blocks are available. It referred several times to the consistency of the allocation metadata and to the need for crash consistency. Lesson 10.6 presents journaling: the technique that file systems use to keep their metadata consistent across crashes. The lesson covers the journal's structure, the write-ahead logging protocol, the different journaling modes (writeback, ordered, data), and the trade-offs between performance and consistency. The journal is what makes the allocation metadata reliable, and it is the bridge between the file system's logical structures and the device's physical behaviour.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 14, Section 14.4.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 40. Available online at ostep.org.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 4, Section 4.3.2.
McKusick, M. K., Joy, W. N., Leffler, S. J., & Fabry, R. S. A Fast File System for UNIX. ACM Transactions on Computer Systems, 1984.
Bach, M. J. The Design of the UNIX Operating System. Prentice Hall, 1986. Chapter 4.
Kerrisk, M. The Linux Programming Interface. No Starch Press, 2010. Chapter 14.
Love, R. Linux Kernel Development, 3rd ed., Chapter 13, The Virtual File System.
Bovet, D. P., & Cesati, M. Understanding the Linux Kernel, 3rd ed. O'Reilly, 2005. Chapter 12.
Mathur, A., Cao, M., Bhattacharya, S., Dilger, A., Tomas, A., & Vivier, L. The New Ext3 Directory Index. Ottawa Linux Symposium, 2007.
Linux man-pages: man 2 stat, man 2 statvfs, man 2 fallocate, man 8 filefrag, man 1 debugfs, man 8 tune2fs, man 8 dumpe2fs, man 5 ext4, man 5 xfs, man 5 btrfs.