File Systems

A disk offers a flat array of numbered blocks, and a program wants a named, growable, randomly accessible stream of bytes.

The organising fact is that a file system's whole job is to turn a name into a sequence of block numbers, and every design decision is about where that mapping is stored and how many disk reads it takes to reach a given byte.

Contiguous allocation stores the mapping as two numbers and reaches any byte in one read. Linked allocation stores it inside the blocks themselves and reaches byte $N$ only by walking. Indexed allocation stores it in a separate block and reaches any byte in two.

The second organising fact is that the same question applies to the directory. A path is resolved one component at a time, and each component costs at least one read of a directory and one read of an inode.

The third is that a file system must survive a crash at any instant, which is why journaling exists and why the order of writes matters as much as their content.

1. Files, Attributes and Operations

A file is a named collection of related information stored on secondary storage, and it is the smallest unit of storage that has a name.

Attributes are kept separately from the data: name, identifier, type, location, size, protection bits, and timestamps for creation, last access and last modification.

Six basic operations exist: create, write, read, reposition, delete and truncate. Open and close are not file operations on the data but on a per-process table entry.

The open-file table has two levels. A system-wide table holds one entry per open file with the location and an open count; each process has a table of descriptors pointing into it.

This two-level structure is why two processes can share a file offset after fork but not after independently opening the same file. Fork duplicates the descriptor, which points at the same shared entry; a separate open creates a new entry with its own offset.

Access methods are sequential, which reads in order and supports rewind, and direct or relative, which addresses blocks by number and is what modern systems provide.

2. Directory Structure

A directory is a table mapping names to file control blocks, and its structure determines what naming is possible.

A single-level directory has one namespace for all users and cannot support duplicate names. A two-level directory gives each user their own, which prevents collisions but not grouping.

A tree-structured directory allows arbitrary nesting and is what almost everything uses. Each file has exactly one parent and one path.

An acyclic graph directory allows sharing, so a file can appear in several directories, which requires links.

A hard link is a second directory entry pointing at the same inode. The inode carries a reference count, and deletion removes the entry and decrements the count; the data is freed only at zero.

A symbolic link is a small file containing a path string. Removing the target leaves the link dangling, since nothing counts references to it.

The consequences differ sharply. Hard links cannot cross file system boundaries, because inode numbers are only meaningful within one file system, and are usually forbidden on directories to prevent cycles. Symbolic links can cross boundaries and can point at directories, at the cost of an extra resolution and the possibility of dangling.

3. Allocation Methods

Contiguous allocation stores a file in consecutive blocks, recorded as a start block and a length.

Access is excellent: byte $N$ is at start plus $N$ divided by block size, computed without any disk read. Both sequential and random access are optimal, and seek time is minimal.

Its defects are decisive. It suffers external fragmentation, and a file cannot grow beyond its neighbours without being moved, which requires knowing the final size at creation.

Linked allocation stores a pointer to the next block inside each block, with the directory holding only the first and last.

External fragmentation disappears entirely and files grow freely.

Random access becomes unusable. Reaching block $k$ requires reading all $k$ preceding blocks. A single bad pointer also loses the entire remainder of the file.

The file allocation table variant pulls all the pointers into one table at the start of the volume, indexed by block number. Random access improves greatly because the chain can be walked in the cached table rather than on disk.

Indexed allocation gives each file an index block holding all its block numbers.

Random access costs one extra read and there is no external fragmentation.

The index block itself bounds the file size, which is why real systems use multilevel schemes.

4. The inode

A UNIX inode holds the attributes plus a hybrid index structure, and its design deserves attention because it is the most examined object in this chapter.

It contains a fixed number of direct pointers, typically 12, each naming one data block.

Then a single indirect pointer names a block full of block numbers.

Then a double indirect pointer names a block of pointers to blocks of pointers.

Then a triple indirect pointer, adding one more level.

The design is deliberately asymmetric. Small files, which are the overwhelming majority, are reached entirely through the direct pointers with no extra read at all. Large files are still possible, at the cost of extra reads that are amortised over a large transfer.

The maximum file size is the sum of what each level addresses. With block size $B$ and pointer size $P$, one block holds $B/P$ pointers, so the total is

$12B+\frac{B}{P}\cdot B+{\left(\frac{B}{P}\right)}^{2}B+{\left(\frac{B}{P}\right)}^{3}B$

The number of reads to reach a byte depends on which region it falls in: zero extra reads for the first 12 blocks, one for the single indirect range, two for the double, three for the triple.

5. Free Space Management

A bit vector has one bit per block, set if free. Finding a run of free blocks is a scan for consecutive ones, which hardware can do quickly on whole words.

Its size is the block count divided by eight bytes, and it must be kept in memory to be useful, which for very large disks becomes significant.

A linked list of free blocks costs nothing in extra space, since the pointers live in the free blocks themselves, but finding contiguous space requires traversal.

Grouping stores $n$ free block addresses in the first free block, the last of which points at another such block, so many addresses are obtained in one read.

Counting stores an address plus a run length, exploiting the fact that free blocks tend to come in runs.

6. Path Resolution and Consistency

Resolving a path walks it one component at a time, and each component costs a directory read plus an inode read.

Resolving an absolute path starts at the root inode, whose number is fixed and known.

Directory implementations vary. A linear list is simple and requires a linear search per lookup. A hash table gives constant-time lookup at the cost of collisions and resizing. Large modern file systems use B-trees.

Caching matters more here than almost anywhere. The directory entry cache and the inode cache remove most of these reads, which is why repeated access to the same path is far cheaper than the analysis suggests.

Consistency is threatened because one logical operation touches several structures. Creating a file writes an inode, a directory entry and the free space map, and a crash between them leaves the disk inconsistent.

Journaling records the intended changes in a log before applying them. After a crash, the log is replayed, so incomplete operations are either completed or discarded atomically.

Write-ahead is the rule that makes it work: the log record must reach the disk before the change it describes.

Metadata-only journaling logs structural changes but not file contents, which is much faster and is the common default, at the cost of possibly recovering a valid file containing stale data.

7. Worked Examples

Example 1. An inode has 12 direct, one single indirect, one double indirect and one triple indirect pointer. Block size is 4 KB and each pointer is 4 bytes. Compute the maximum file size.

First find how many pointers fit in a block. A 4 KB block divided by a 4-byte pointer gives $4096/4=1024$ pointers.

Direct pointers address $12\times 4\text{ KB}=48$ KB.

The single indirect block addresses $1024$ blocks, which is $1024\times 4\text{ KB}=4$ MB.

The double indirect addresses $1024\times 1024=2^{20}$ blocks, which is $2^{20}\times 4\text{ KB}=4$ GB.

The triple indirect addresses $1024^3=2^{30}$ blocks, which is $2^{30}\times 4\text{ KB}=4$ TB.

The total is $48\text{ KB}+4\text{ MB}+4\text{ GB}+4\text{ TB}$, which is just over 4 TB.

Notice that each level dominates the sum of all previous ones by a factor of about 1024, so the answer is essentially the triple indirect contribution. Examiners often ask for the total and accept the approximation, but write the full sum to be safe.

Example 2. For that same inode, how many disk reads are needed to fetch the data block containing byte offset 5,000,000, assuming nothing is cached and the inode is already in memory?

Convert the offset to a block index. Dividing 5,000,000 by 4096 gives block index 1220, with a remainder that only affects the offset within the block.

Determine the region. Blocks 0 through 11 are direct. Blocks 12 through 1035 are covered by the single indirect, since it holds 1024 pointers.

Block 1220 exceeds 1035, so it falls in the double indirect range, which covers blocks 1036 through 1,049,611.

Reading it requires three disk accesses: one for the double indirect block, one for the second-level pointer block it names, and one for the data block itself.

Contrast with byte offset 40,000, which is block index 9, a direct pointer, needing a single access for the data block.

This asymmetry is the whole design argument for the inode: the common case pays nothing.

Example 3. A 1 TB disk uses 4 KB blocks. Compute the size of a free-space bit vector, and compare with a linked free list when the disk is 90 percent full.

The block count is $10^{12}$ divided by 4096, which is about $2.44\times 10^8$ blocks, roughly 244 million.

A bit vector needs one bit per block, so about $2.44\times 10^8$ bits, which is $3.05\times 10^7$ bytes, or roughly 30 MB.

That must be resident in memory to be useful, which is a real cost but acceptable on a machine with gigabytes of RAM.

With the disk 90 percent full there are about 24.4 million free blocks.

A linked free list stores its pointers inside the free blocks themselves, so it costs zero extra space.

But finding a run of, say, 100 contiguous free blocks requires traversing the list, and each traversal step is a disk read, because the next pointer lives in the block itself.

The bit vector finds the same run by scanning words in memory, which is orders of magnitude faster.

The trade-off inverts as the disk empties. With a nearly empty disk, the bit vector is mostly ones and still costs 30 MB, while the free list is long but rarely needs a contiguous search, since any block will do.

Example 4. File f has one hard link h and one symbolic link s, both created before anything is deleted. Describe the state after deleting f, and then after deleting h.

Initially the inode's link count is 2, counting the original directory entry f and the hard link h. The symbolic link is a separate file containing the string naming f, and does not affect the count.

Deleting f removes that directory entry and decrements the link count to 1.

The data survives, because the count is not zero, and h still reaches it perfectly.

But s is now dangling, since it holds the path to f, which no longer resolves. Opening s fails even though the data is still on disk under another name.

Now delete h. The link count drops to 0, so the inode and its data blocks are released to the free list.

The general rule to carry into the exam: hard links are counted and symbolic links are not. A file survives exactly as long as its link count is positive, and symbolic links have no vote.

One more consequence: creating a new file named f after the first deletion would make s resolve again, now pointing at completely different data, which is a real security consideration.

Example 5. A file has 100 blocks. Compare the number of disk accesses needed to append one block at the end and to insert one block in the middle, under contiguous, linked and indexed allocation, assuming the directory entry or index block is already in memory.

Under contiguous allocation, appending needs one write if the block after the file is free.

If it is not free, the entire file must be copied to a new region, costing 100 reads and 101 writes, which is the fragility of the scheme.

Inserting in the middle requires shifting all subsequent blocks, so about 50 reads and 51 writes even in the best case.

Under linked allocation, appending needs one read of the last block to update its pointer, plus one write of that block and one write of the new block, if the directory holds a pointer to the last block. Without that pointer it would need 100 reads to walk the chain.

Inserting in the middle needs 50 reads to reach the position, then two writes to splice the new block in. No other block moves, which is linked allocation's genuine advantage.

Under indexed allocation, appending needs one write of the new data block plus one write of the index block.

Inserting in the middle needs one write of the data block plus one write of the index block, after shifting entries within the index block in memory.

The comparison summarises the whole section. Contiguous is fastest to read and worst to modify. Linked modifies cheaply and reads terribly. Indexed is the compromise that real systems chose.

Example 6. Resolving the path /usr/local/bin/gcc from a cold cache requires how many disk accesses, assuming each directory fits in one block and the root inode number is known?

Start at the root. Read the root inode, then read its data block to find the entry for usr. That is 2 accesses.

For usr: read its inode, then its data block to find local. That is 2 more, running total 4.

For local: read its inode, then its data block to find bin. Total 6.

For bin: read its inode, then its data block to find gcc. Total 8.

Finally read the inode of gcc itself, giving 9 accesses before a single byte of the file has been read.

The general formula is $2d+1$ accesses, where $d$ is the number of directory components in the path, plus one for the final inode.

This is why the directory entry cache exists. Nine disk accesses per file open would make a compiler unusable, and in practice all but the last are served from memory after the first traversal.

If a directory spans several blocks, each additional block searched adds one access, so large flat directories are genuinely slower under a linear-list implementation, which is why B-trees replaced them.

Summary

A file system turns a name into a sequence of block numbers, and every design choice concerns where that mapping lives and how many reads reach a given byte.

Attributes live apart from data. The open-file table has a system-wide level and a per-process level, which is why fork shares a file offset while a separate open does not.

Tree directories give one path per file; acyclic graph directories need links. Hard links share an inode and are counted, cannot cross file systems, and are barred on directories. Symbolic links hold a path, can dangle, and can cross boundaries.

Contiguous allocation reaches any byte with no extra read but suffers external fragmentation and cannot grow. Linked allocation grows freely and destroys random access. The file allocation table pulls the pointers into one cacheable structure. Indexed allocation costs one extra read and bounds file size by the index block.

The inode combines 12 direct pointers with single, double and triple indirect blocks, so small files cost nothing extra and large files remain possible. Maximum size is $12B+(B/P)B+(B/P{)}^{2}B+(B/P{)}^{3}B$, and reads to reach a byte are zero, one, two or three extra depending on the region.

Free space is tracked by a bit vector, which is fast for contiguous searches and costs about 30 MB per terabyte at 4 KB blocks, or by a linked list, grouping or counting, which cost no extra space but make contiguous searches slow.

Path resolution costs about $2d+1$ accesses from a cold cache, which is why directory entry and inode caches dominate real performance.

Journaling records intended changes before applying them, with write-ahead ordering as the rule that makes recovery sound. Metadata-only journaling is the common default and trades content integrity for speed.