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;