File Allocation Methods and Free-Space Management

A disk is an array of fixed-size blocks, and a file is a sequence of logical blocks 0, 1, 2 and so on. The allocation method decides which disk blocks hold a file and how the file system finds logical block $i$. The choice fixes three quantities: how many disk accesses a read of block $i$ costs, how large a file can be, and how much space is wasted.

There are three classical methods: contiguous, linked (with its table form, the FAT) and indexed (with the UNIX inode as its multilevel form). The file system must also remember which blocks are free, using a bit vector, a free list, grouping or counting. Each method is given with the arithmetic that goes with it.

Conventions. Logical blocks are numbered from 0. "Accesses" counts disk-block reads needed to fetch one data block, with the directory entry or inode already in memory unless stated otherwise. Block numbers (disk addresses) are 4 bytes.

The file occupies blocks start, start $+ 1$, ..., start $+$ length $- 1$. File a in Figure 1 has start 14 and length 6: blocks 14 to 19, and logical block 4 is disk block 18. Both sequential and direct access are fast, and sequential reads need almost no seeking. The costs are those of Contiguous Memory Allocation and Fragmentation: choosing a hole by first fit or best fit, external fragmentation, and the need to know the final size in advance. Some systems allocate a contiguous extent and link further extents when the file grows.

Each block stores the address of the next block of the file; the directory holds the first block (and often the last, for appending). File b has the chain 7, 21, 3, 12, 28, and the last block holds a null pointer. To read logical block 3, the system reads blocks 7, 21 and 3 for their pointers and then block 12: 4 accesses, and in general $i + 1$ for logical block $i$.

The FAT moves all the next-block pointers into one table with an entry per disk block, kept at the start of the volume and cached in memory. Entry $k$ holds the number of the block that follows block $k$ in its file, an end-of-file mark, or 0 for a free block. For file b:

The directory entry holds 7. Finding logical block $i$ means following $i$ entries in memory, then one disk access. The table is large, though: a 2 GB volume with 4 KB blocks has $2^{31}/2^{12} = 2^{19}$ blocks, and with 4-byte entries the FAT occupies 2 MB. The FAT width limits the volume: FAT-16 addresses at most $2^{16}$ blocks, so with 32 KB blocks the largest volume is 2 GB (Tanenbaum 4.5.1).

Each file has an index block: an array of disk-block addresses, entry $i$ giving logical block $i$. File c's index block is block 9 and holds 7, 21, 3, 12, 28 and then null entries. Reading any block takes 2 accesses (index block, then data); with the index block cached, 1. Direct access is fast and there is no external fragmentation, but every file, however small, costs a whole index block.

When one index block is not enough:

Let the block size be $B$ bytes and the address size $a$ bytes, so an index block holds $N = B/a$ addresses. With $d$ direct pointers and one each of single, double and triple indirect:

For $d = 12$, $B = 4$ KB and $a = 4$ bytes, $N = 1024$:

Check the address width too. A 4-byte block address can name $2^{32}$ blocks, so with 4 KB blocks the whole file system is limited to 16 TB. In this example the pointers, not the address width, limit the file size; with larger blocks or more indirection the address width can become the binding limit.

Second example. An inode with 10 direct pointers, one single and one double indirect pointer, 1 KB blocks and 4-byte addresses: $N = 256$, so the largest file is $(10 + 256 + 65{,}536) \times 1$ KB $= 65{,}802$ KB.

With $d = 12$ and $N = 1024$: logical blocks 0 to 11 are direct; 12 to 1,035 go through the single indirect block; 1,036 to 1,049,611 through the double indirect block; the rest through the triple indirect block.

The cost of reading block $i$, with the inode cached, is 1 access for a direct block, 2 for single indirect, 3 for double and 4 for triple. If the inode must be read first, add 1.

Address width binding. 8 KB blocks, 4-byte block addresses, 12 direct pointers and one each of single, double and triple indirect. An index block holds $N = 8192/4 = 2048$ addresses, so the pointers reach

But a 4-byte address names only $2^{32}$ blocks, $2^{32} \times 8$ KB $= 2^{45}$ bytes $= 32$ TB. A file cannot use more blocks than the volume can number, so the largest file is limited to 32 TB by the address width, not by the pointers.

Wider addresses. With 8-byte addresses and the same 8 KB blocks, $N = 1024$ and the pointers reach $12 + 2^{10} + 2^{20} + 2^{30}$ blocks, a little over $2^{30} \times 8$ KB $= 8$ TB. A 64-bit address no longer limits anything, so now the pointers bind. Doubling the address size halves $N$ and cuts the triple-indirect reach by a factor of 8.

Index blocks used by one file. With $d = 12$ and $N = 1024$ (4 KB blocks, 4-byte addresses), a file of 5,000 blocks uses the 12 direct pointers, the single indirect block for blocks 12 to 1,035, and the double indirect block for the remaining $5000 - 1036 = 3964$ blocks. Those need $\lceil 3964 / 1024 \rceil = 4$ second-level blocks. Index blocks in all: $1 + 1 + 4 = 6$, so the file occupies 5,006 blocks on disk.

One bit per block. Convention: as in Silberschatz 14.5, bit 1 means the block is free and 0 that it is allocated; some texts use the opposite, so check the question. To find the first free block, skip words that are all 0, then find the first 1 bit:

Example. With 8-bit words, bitmap 00000000 00000000 00101100 ... (bits numbered from the left within a word): two all-zero words, then the first 1 is at offset 2, so the first free block is $8 \times 2 + 2 = 18$. The free blocks in the third word are 18, 20 and 21.

Size. The bitmap for a 2 GB volume with 4 KB blocks has $2^{19}$ bits = 64 KB. For 1 TB with 4 KB blocks: $2^{28}$ bits = 32 MB. A bitmap is fast only if it is cached in memory, so its size matters.

Bitmap or free list? A disk of $2^{20}$ blocks of 1 KB needs a 128 KB bitmap (128 blocks) whatever its state. A free list stored as blocks of free addresses (255 four-byte addresses per 1 KB block, plus a pointer to the next such block) needs 40 blocks when 10,000 blocks are free, but 4,113 blocks when all $2^{20}$ are free. The list is smaller on a nearly full disk; the bitmap is smaller on an empty one (Tanenbaum 4.4.1).

Common misconceptions.