Linux Kernel Architecture

Chapter 9: The Extended Filesystem Family

While entries for subdirectories should be as close to the parent directory as possible, subdirectories of
the filesystem root should be diverted as well as possible. Otherwise, directories would again accumulate
in a distinguished block group.

Parent inode is root inode?

Test suitability of group

Group found?

Return group number

Fallback selection

Yes

Yes

No

find_group_orlov

get_random_bytes

No

Search starts in

Search starts in random group

present group

Iterate over

all groups

Figure 9-20: Code flow diagram forfind_group_orlov.

Let’s first take a look at the standard situation in which a new subdirectory is to be created at some
point in the directory tree (and not in the root directory). This corresponds to the right-hand branch in
Figure 9-20. The kernel computes several variables used as criteria to establish the suitability of a block
group to accommodate the desired directory node (I took the liberty of rearranging the code a little to
make it easier to understand):

fs/ext2/ialloc.c

int ngroups = sbi->s_groups_count;

int inodes_per_group = EXT2_INODES_PER_GROUP(sb);

freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);

avefreei = freei / ngroups;

free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);

avefreeb = free_blocks / ngroups;

ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);

blocks_per_dir = (le32_to_cpu(es->s_blocks_count)-free_blocks) / ndirs;

max_dirs = ndirs / ngroups + inodes_per_group / 16;

min_inodes = avefreei - inodes_per_group / 4;

min_blocks = avefreeb - EXT2_BLOCKS_PER_GROUP(sb) / 4;

max_debt = EXT2_BLOCKS_PER_GROUP(sb) / max(blocks_per_dir, BLOCK_COST);

if (max_debt * INODE_COST > inodes_per_group)

max_debt = inodes_per_group / INODE_COST;

if (max_debt > 255)

max_debt = 255;

if (max_debt == 0)

max_debt = 1;