Linux Kernel Architecture

Chapter 9: The Extended Filesystem Family

In this context, the termpathmeans the path through the descriptor tables to arrive at the desired data

block.

This information can be obtained without I/O interaction with the data block. All that is needed is the

position of the block in the file and the filesystem block size that is stored in the superblock data structure

and need not be read in explicitly.

ext2_block_to_pathperforms a step-by-step comparison. If the data block number is smaller than the

number of direct blocks (EXT2_NDIR_BLOCKS), it is returned without modification because the block can

be addressed directly.^16

If not, a calculation is made — with the help of the block size — to determine how many pointers to

blocks fit in a single block. The number of direct blocks is added to the result of the calculation to obtain

the maximum possible number of blocks in a file whose contents can be addressed by means of simple

indirection. If the number of the desired block is smaller than this value, an array withtwoblock numbers

is returned. The first entry contains the number of the simple indirection block, and the second specifies

the address of the pointer in the indirection block.

The same scheme is adopted to cater for double and triple indirection. An additional entry is added to

the returned array for each further level of indirection.

The number of array entries used to describe the position of a block in the indirection network is referred

to as thepath length. Logically, the path length increases as the number of indirection levels grows.

Up to now, use has been made only of the filesystem block size, and the filesystem has not had to perform

actual I/O operations on the hard disk. To find the absolute address of a data block, the path defined in

the path array must be followed, and this entails reading data from the hard disk.

ext2_get_branchinfs/ext2/inode.cfollows a known path to finally arrive at a data block. This task

is relatively straightforward.sb_breadreads the indirection blocks one after the other. The data in each

block and the offset value known from the path are used to find the pointer to the next indirection block.

This procedure is repeated until the code reaches a pointer to a data block that is returned as the result of

the function. This absolute address is used by higher-level functions such asblock_read_full_pageto

read the block contents.

Requesting New Blocks

The situation becomes more complicated when it is necessary to process a block that has not yet been

allocated. Before this situation can arise, a process must write to a file, thereby enlarging it; whether

classic system calls or memory mapping are used to do this is irrelevant. In all cases,ext2_get_blocksis

invoked to request new blocks for the file. Conceptually, adding new blocks to a file is composed of four

tasks:

❑ After detecting that new blocks are necessary, the kernel needs to decide if and how many levels

of indirection are required to associate the new blocks with the file.

❑ Free blocks must be found on the storage medium and reserved.

❑ The freshly allocated blocks must be added to the block list of the file.

(^16) Reminder: File blocks are numbered linearly starting at 0.