Linux Kernel Architecture

Chapter 9: The Extended Filesystem Family

are usually two versions of a data structure — one for persistent storage on disk, the other for working

with memory.

In the sections below, the frequently used wordblockhas two different meanings:

❑ On the one hand, some filesystems reside on block-oriented devices that — as explained in

Chapter 6 — do not transfer individual characters but entire data blocks.

❑ On the other, the Second Extended Filesystem is ablock-basedfilesystem that divides the hard

disk into several blocks, all of the same size, to manage metadata and the actual file contents.

This means that the structure of the underlying storage medium is imposed on the structure

of the filesystem and this naturally influences the design of the algorithms and data structures

used. This chapter takes a closer look at this influence.

One aspect is of particular importance when dividing the hard disk into fixed-sized blocks — files may

occupy only integer multiples of the block size. Let us look at the impact of this situation by reference to

Figure 9-1, in which, for simplicity’s sake, we assume a block size of 5 units. We want to store three files

whosesizesare2,4,and11units.

File A

File B

File C

Figure 9-1: File distribution in block-based filesystems.

The clearly more effective method of dividing existing storage space is applied in the upper part, where

the contents of the individual files are spread as compactly as possible across the available blocks. How-

ever, this method is not used in practice because it has a major disadvantage.^3 The information needed

to manage the file boundaries within the individual blocks would be so voluminous that it would imme-

diately cancel out any advantage gained as compared to the wasteful assignment of blocks in the right

part of the figure. As a result, each file occupies not only the space needed for its data but also the space

left over when the block size is rounded up to the next integer multiple.

StructureOverview

Let’s first take a bird’s eye view of the C structures used to manage data to get a clear picture of the

functions of the individual components and the interplay among them. Figure 9-2 shows the contents of

a block group, a central element of the Ext2 filesystem.

A block group is the basic element that accommodates the further structures of the filesystem. Each

filesystem consists of a very large number of block groups arranged one after the other on the hard disk

as shown in Figure 9-3.

(^3) ‘‘Not used‘‘ is not strictly accurate because a diluted form of this scheme that, to a certain extent, allows the use of a single block to
hold several small files is under development and may be included as standard in future versions of the Ext2/3 filesystem. Although
the basic infrastructure for suchfragmentsis included in the code, it is not yet implemented.