Linux Kernel Architecture

Chapter 9: The Extended Filesystem Family

Classic Directory Allocation

Kernel versions up to and including 2.4 did not use Orlov allocation, but the technique described below,

calledclassicallocation. Ext2 filesystems can be mounted using theoldallocoption, which sets the

EXT2_MOUNT_OLDALLOCbit in thes_mount_optfield of the superblock. The kernel then no longer uses the

Orlov allocator but resorts to the classic scheme of allocation.^18

How does the classic scheme work? The block groups of the system are scanned in a forward search, and

particular attention is paid to two conditions:

1. Free space should still be available in the block group.


2. The number of directory inodes should be as small as possible compared to other inodes in
   the block group.

In this scheme, directory inodes are typically spread as uniformly as possible across the entire filesystem.

If none of the block groups satisfies requirements, the kernel restricts selection to groups with above

average amounts of free space and from these chooses those with the fewest directory inodes.

Inode Allocation for Other Files

A simpler scheme known asquadratic hashingis applied when searching for an inode for regular files,

links, and all file types other than directories. It is based on a forward search starting at the block group

of the directory inode of the directory in which the new file is to be created. The first block group found

with a free inode is reserved.

The block group in which the directory inode is located is searched first. Let’s assume its group ID is

start. If it does not have a free inode, the kernel scans the block group with the number start+ 20 ,then

start+ 20 + 21 , start+ 20 + 21 + 22 , and so on. A higher power of 2 is added to the group number in each

step, which results in the sequence 1, 1+2, 1+ 2 +4, 1+ 2 + 4 +8,··· =1, 3, 7, 15,....

Usually, this method quickly finds a free inode. However, if no free inode is returned on an (almost

hopelessly) overfilled filesystem, the kernel scansallblock groups in succession to ensure that every

effort is made to find a free inode. Again, the first block group with a free inode is selected. If absolutely

no inodes are free, the action is aborted with a corresponding error code.^19

Deleting Inodes

Both directory inodes and file inodes can be deleted, and, from the perspective of the filesystem, both

actions are much simpler than allocating inodes.

Let us first look at how directories are deleted. After the appropriate system call (rmdir) has been

invoked, the code meanders through the kernel and finally arrives at thermdirfunction pointer

of theinode_operationsstructure, which, for the Ext2 filesystem, containsext2_rmdirfrom

fs/ext2/namei.c.

(^18) In terms of compatibility with old kernel versions, it makes no difference whether directory inodes are reserved with the Orlov
allocator or not because the format of the filesystem remains unchanged.
(^19) In practice, this situation hardly ever occurs because the hard disk would have to contain a gigantic number of small files, and this
is very rarely the case on standard systems. A more realistic situation (often encountered in practice) is that all data blocks are full,
but a large number of inodes are still free.