File allocation methods and inodes

Why it exists

A disk offers numbered blocks. A file system must decide which blocks hold which file, and keep enough information to find block number $k$ of a file quickly. The choice is a trade between three things: fast access (sequential and direct), efficient use of space (no waste, files that can grow), and small bookkeeping. Four classical methods, contiguous, linked (with its table version, the FAT), indexed and the combined Unix inode scheme, embody different trades. GATE asks, over and over, for the maximum file size of an inode scheme and for the number of disk accesses to read a given block, and for the size of a FAT.

Prerequisites

You need files, directories and inodes from file systems.

Precise definitions

Block. The unit of transfer between disk and memory (512 bytes to a few kilobytes). A file occupies a whole number of blocks; its last block is partly empty (internal fragmentation, on average half a block per file).

Contiguous allocation. Each file occupies a set of consecutive blocks. The directory entry holds the start block and the length.

• Direct access to block $k$: start $+ k$, one disk access; sequential access is fastest (the head moves little).
• Problems: external fragmentation (free space split into runs too small for a new file), the final size must be known when the file is created (or space is over-reserved), and a file that grows may have to be moved. Compaction is expensive.

Linked allocation. Each file is a linked list of blocks that may be anywhere on the disk; each block holds a pointer to the next. The directory entry holds the first (and often the last) block.

• No external fragmentation, files grow freely.
• Block $k$ can be reached only by following $k$ pointers: $k + 1$ disk accesses for logical block $k$ (counting from 0), so direct access is slow.
• The pointer takes space (a block of $B$ bytes holds $B - p$ bytes of data); a damaged pointer loses the rest of the file.

File allocation table (FAT). Linked allocation with the pointers stored in a table, with one entry per disk block: the entry of block $b$ holds the number of the block that follows it in its file (or a special end-of-file value; unused blocks have entry 0). The directory entry holds the first block. The FAT is cached in memory, so following the chain costs no disk accesses: reading logical block $k$ is one disk access (to the data block), and direct access is fast. Disadvantages: the table (all its entries) must be in memory and is big for a big disk.

$\text{FAT size} = (\text{number of blocks}) \times (\text{entry size}), \qquad \text{entry size} \ge \lceil \log_2 (\text{number of blocks}) \rceil \text{ bits}.$

Indexed allocation. Each file has an index block that holds the block numbers of all its data blocks; entry $i$ is the block of logical block $i$. The directory entry points to the index block.

• No external fragmentation; direct access is easy: 2 disk accesses for a block (the index block, then the data block), or 1 if the index block is cached.
• The index block is overhead even for a tiny file. A file with more blocks than an index block can hold needs more than one index block: linked index blocks (the last entry points to the next index block), a multilevel index (an index of index blocks), or the combined scheme.

Combined scheme: the Unix inode. The inode, kept in memory when the file is open, holds the attributes and:

• $D$ direct pointers (usually 12) to data blocks,
• one single indirect pointer to a block of pointers to data blocks,
• one double indirect pointer to a block of pointers to blocks of pointers to data blocks,
• one triple indirect pointer, one level deeper again.

With block size $B$ and pointer size $p$ one indirect block holds $n = B/p$ pointers. The number of data blocks an inode can address is

$D + n + n^2 + n^3, \qquad \text{maximum file size} = (D + n + n^2 + n^3) \cdot B$

(drop the terms of the levels that the inode does not have). Small files use only direct pointers (no extra blocks at all); large files pay for indirect blocks. Disk accesses to read logical block $k$ (inode in memory, indirect blocks not cached): $1$ if $k < D$; $2$ if in the single range ($D \le k < D + n$); $3$ in the double range; $4$ in the triple range. (Each level of indirection adds one access.)

Comparison.

How it works

All the animations use a disk of 32 blocks (the inode one uses 64), drawn as a grid; each block shows the file and logical position it holds (A3 is the fourth block of file A), and the blocks read in a step are numbered in reading order. The panel at the right shows the directory entry, FAT, index block or inode.

Contiguous. File C starts at block 12; reading logical block 3 is one access (block 15). The animation also shows the problem: file B cannot grow because C follows it, and the free space (19 blocks) is split into runs of 2, 3 and 14 so a 15-block file does not fit.

Linked. File A is the chain 3, 7, 4, 12, 9; reading logical block 4 means reading all five blocks in order: 5 accesses.

FAT. The same chain with the pointers in a table in memory: the walk 3, 7, 4, 12, 9 costs nothing, and the single disk read is block 9.

Indexed. File A's index block (20) lists its data blocks; reading logical block 3 reads the index block, then block 11: 2 accesses; the next read, with the index in memory, costs 1.

Unix inode (toy sizes). Blocks of 32 bytes and 4-byte pointers give 8 pointers per indirect block; the inode has 4 direct pointers, a single and a double indirect pointer. Reading logical block 2 costs 1 access, block 7 costs 2, and block 25 costs 3.

Worked examples

#include <stdio.h>
 
/* blocks addressable by an inode with `direct` direct pointers and one single, double and triple indirect pointer */
static unsigned long long max_blocks(unsigned direct, unsigned per_block) {
    unsigned long long n = direct, p = 1;
    for (int level = 1; level <= 3; level++) { p *= per_block; n += p; }
    return n;
}
 
/* disk blocks read to fetch logical block k, with the inode in memory */
static int accesses(unsigned long long k, unsigned direct, unsigned per_block) {
    if (k < direct) return 1;
    k -= direct;
    unsigned long long p = 1;
    for (int level = 1; level <= 3; level++) {
        p *= per_block;
        if (k < p) return 1 + level;
        k -= p;
    }
    return -1;
}
 
int main(void) {
    unsigned block = 1024, ptr = 4, per = block / ptr;
    unsigned long long n = max_blocks(12, per);
    printf("block %u bytes, pointer %u bytes: %u pointers per block\n", block, ptr, per);
    printf("12 direct + single + double + triple: %llu blocks, %.2f GB\n", n, (double)n * block / (1024.0 * 1024 * 1024));
    printf("direct only: %u KB; with the single indirect block: %u KB\n", 12 * block / 1024, (12 + per) * block / 1024);
    unsigned long long ks[7] = {0, 11, 12, 267, 268, 65803, 65804};
    printf("disk accesses for logical blocks:");
    for (int i = 0; i < 7; i++) printf(" %llu->%d", ks[i], accesses(ks[i], 12, per));
    printf("\n");
    /* 512-byte blocks, 4-byte pointers, 10 direct, single and double indirect only */
    unsigned long long m = 10 + 128 + 128ull * 128;
    printf("10 direct + single + double with 512-byte blocks: %llu blocks, %llu KB\n", m, m * 512 / 1024);
    /* FAT: a 16 GB disk with 4 KB blocks */
    unsigned long long blocks = (16ull << 30) / 4096;
    int bits = 0;
    while ((1ull << bits) < blocks) bits++;
    printf("FAT for a 16 GB disk with 4 KB blocks: %llu entries of %d bits (stored in 4 bytes): %llu MB\n", blocks, bits, blocks * 4 / (1024 * 1024));
    printf("linked allocation: %d data bytes in a 512-byte block, %d in a 4096-byte block\n", 512 - 4, 4096 - 4);
    return 0;
}

block 1024 bytes, pointer 4 bytes: 256 pointers per block
12 direct + single + double + triple: 16843020 blocks, 16.06 GB
direct only: 12 KB; with the single indirect block: 268 KB
disk accesses for logical blocks: 0->1 11->1 12->2 267->2 268->3 65803->3 65804->4
10 direct + single + double with 512-byte blocks: 16522 blocks, 8261 KB
FAT for a 16 GB disk with 4 KB blocks: 4194304 entries of 22 bits (stored in 4 bytes): 16 MB
linked allocation: 508 data bytes in a 512-byte block, 4092 in a 4096-byte block

Cheat box

Traps and GATE patterns

Connections

Each method rests on the files and inodes of file systems. Contiguous allocation has the external fragmentation of contiguous memory allocation, and the inode's levels of pointers are the same idea as a multilevel page table: the number of levels adds one access each. Where the blocks lie decides how far the head must move, which is the subject of disk scheduling.

PYQs

A disk of size 512M bytes is divided into blocks of
64K bytes. A file is stored in the disk using linked
allocation. In linked allocation, each data block
reserves 4 bytes to store the pointer to the next data
block. The link part of the last data block contains
a NULL pointer (also of 4 bytes). Suppose a file of
1M bytes needs to be stored in the disk. Assume,
1K = 210 and 1M = 220. The amount of space in
bytes that will be wasted due to internal
fragmentation is ______. (Answer in integer)

A disk of size 512 M bytes is divided into blocks of
64 K bytes. A file is stored in the disk using linked
allocation. In linked allocation, each data block
reserves 4 bytes to store the pointer to the next data
block. The link part of the last data block contains a
NULL pointer (also of 4 bytes). Suppose a file of 1 M
bytes needs to be stored in the disk. Assume, 1 K =
210and 1 M = 220. The amount of space in bytes that
will be wasted due to internal fragmentation is
______

Consider two files systems A and B, that use
contiguous allocation and linked allocation,
respectively. A file of size 100 blocks is already
stored in A and also in B. Now, consider inserting
a new block in the middle of the file
(between 50th and 51st block), whose data is
already available in the memory. Assume that there
are enough free blocks at the end of the file and that
the file control blocks are already in memory. Let
the number of disk accesses required to insert a
block
in
the
middle
of
the
file
in A and B are  nA and nB, respectively, then the
value of nA+nB is__________________.

The index node (inode) of a Unix-like file system has
12 direct, one single-indirect and one double-indirect
pointers. The disk block size is 4 kB, and the disk
block address is 32-bits long. The maximum possible
file size is (rounded off to 1 decimal place) ______
GB.

In a file allocation system, which of the following
allocation scheme(s) can be used if no external
fragmentation is allowed?
1. Contiguous
2. Linked
3. Indexed

A FAT (file allocation table) based file system is
being used and the total overhead of each entry in the
FAT is 4 bytes in size. Given a 100 × 106 bytes disk
on which the file system is stored and data block size
is 103 bytes, the maximum size of a file that can be
stored on this disk in units of 106 bytes is
____________.

OPERATING SYSTEMS

A file system with 300 Gbyte disk uses a file
descriptor with 8 direct block addresses, 1 indirect
block address and 1 doubly indirect block address.
The size of each disk block is 128 Bytes and the
size of each disk block address is 8 Bytes. The
maximum possible file size in this file system is

The data blocks of a very large file in the Unix file
system are allocated using

Self-check

Revision card

References