Linux Kernel Architecture

Chapter 9: The Extended Filesystem Family

are divided into blocks that are occupied by files. How many blocks a particular file occupies depends on
the size of the file contents (and, of course, on the size of the block itself).

Like system memory, which, in the view of the kernel, is divided into pages of equal size and is addressed
by unique numbers or pointers, all hard disk blocks are uniquely identified by a number. This enables
the file metadata stored in the inode structure to be associated with the file contents located in the
data block sections on hard disk. The link between the two is established by storing the addresses of
the data blocks in the inode.

Files do not necessarily occupy successive data blocks (although this would be

desirable for performance reasons) but are spread over the entire hard disk.

A closer examination of this concept quickly reveals a problem. Maximum file size is limited by the
number of block numbers that can be held in the inode structure. If this number is too small, less space is
needed to manage the inode structures, but, at the same time, only small-sized files can be represented.

Increasing the number of blocks in the inode structure does not solve the problem, as the following quick
calculation proves. The size of a data block is 4 KiB. To hold a file comprising 700 MiB, the filesystem
would need approximately 175,000 data blocks. If a data block can be uniquely identified by a 4-byte
number, the inode would need 175,000×4 bytes to store the information on all data blocks — this is
impracticable because a large portion of disk space would be given over to storing inode information.
What’s more, most of this space would not be needed by most files, whose average size would be less
than 700 MiB.

This is, of course, an age-old problem and is not Linux-specific. Fortunately, allUnixfilesystems includ-
ing Ext2 feature a proven solution known asindirection.^5

With indirection, only a few bytes of the inode hold pointers to blocks — just enough to ensure that an
average small-size file can be represented. With larger files, pointers to the individual data blocks are
stored indirectly, as illustrated graphically in Figure 9-4.

12 direct

Data Structures

Indirection Data blocks

blocks

Inode

Figure 9-4: Simple and double indirection.

(^5) Even the relatively primitive Minix filesystem supports indirection.