ext2/3/4はファイルシステムをグループで管理し、各ファイルをHD全領域に散りばめることで、ブロックの断片化を起こりにくくしています。

・ファイルシステムイメージ

ブートブロック

ブロックグループ0

ブロックグループ1

・・・・

ブロックグループn

・ブロックグループイメージ

スーパブロック

ブロックグループdes

データブロックbmp

iノードbmp

iノードtbl

データブblk

データブロックbmpおよびiノードbmpは１ブロックです。従って１グループ内で管理するブロック数はブロックサイズを4096バイトとすると、4096×8個となり、サイズは4K×8×4K=128Mです。inodeおよびブロックを管理するのはグループ単位で行いますが、ファイルシステムとしてinode番号は一意となります。もしグループm内のn番目と言う場合、inode番号はm×グループ内inode数+nです。

inodeをアロケート（inode番号を割り当てる）するのはext2_new_inodeで行います。まずグループ番号を取得します。inodeはディレクトリまたはファイルによって、グループアロケートロジックがことなります。またディレクトリはマウントオプションにより、簡易なfind_group_dirと高度なfind_group_orlovに処理がゆだねられます。

 if (S_ISDIR(mode)) {
     if (test_opt(sb, OLDALLOC))
           group = find_group_dir(sb, dir);
     else
           group = find_group_orlov(sb, dir);
 } else 
     group = find_group_other(sb, dir);

find_group_dirはスーパブロック情報の全未使用のinode数をブロックグループ数で割ることで、各グループに割り当てられている平均的な未使用inode数とし、全グループからこの平均的未使用inode数より少ないなかで、未使用データブロックが一番多くあるグループが選ばれます。

find_group_orlovは、アロケートするディレクトリがルートの場合とそうでない場合で処理が分かれます。ルートの場合は平均的inode数と平均的ブロック数より小さいグループ内で、アロケートされているディレクトリが一番少ないものを選択します。ルート配下のディレクトリは全グループに散りばめるということです。

 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);

ルートでない場合は、最小未使用inode数、最小未使用ブロック数で、それより大きいものが選択されるようです（しきいちが異なる）。なお、rootと大きく違うのは、負債数というものが判断基準に入っています。これはグループ内のディレクトリと通常ファイルの割合をしめすもので、この値が大きければと対ファイル数と比べて、ディレクトリが多く入っていることになりますが、この値より小さい債数のグループが選択されます。

 blocks_per_dir = (le32_to_cpu(es->s_blocks_count)-free_blocks) / ndirs;
 max_debt = EXT2_BLOCKS_PER_GROUP(sb) / max(blocks_per_dir, BLOCK_COST);
 min_inodes = avefreei - inodes_per_group / 4;
 min_blocks = avefreeb - EXT2_BLOCKS_PER_GROUP(sb) / 4;

全グループ内で、未使用のinode数がmin_inodes多く、未使用のブロック数がmin_blocks多く、そしてmax_debtよりディレクトリ数が小さいものが選択されます。要は一定数の空きinode、空きブロックがあって、対ファイル数、ディレクトリ数割合が一定より小さいものが選択ということです。

プログラムを追っているいるだけで、今ひとつ具体的な違いはみえてきませんが、まあ、ディレクトリはちりばめて、できるだけ空いているグループを探していると言う感じです。

通常ファイルのfind_group_otherは単純です。まず、この親ディレクトリのグループに空きinode、空きブロックがあれば、それで選択されます。そうでなければ、適当なところから空いているinode、空いているブロックのあるグループをみつけます。


ブロックグループがわかればそのグループからinodeを取得します。 そのグループのinodeビットマップを読み込みます。ext2_find_next_zero_bit関数で先頭から0ビットのところを検索しています。この値ををno += group * EXT2_INODES_PER_GROUP(sb) + 1でinode番号としています。（inode番号の最初は0でなく１のようです。）

inodeにはs_first_inoというメンバーがあります。通常(?)は11のようで、11からユーザプロセスで作成したファイルに割り当てられるようになっています。1から10までは予約となっていて、ext2では下記のようになっています。

#define EXT2_BAD_INO             1      /* Bad blocks inode */
#define EXT2_ROOT_INO            2      /* Root inode */
#define EXT2_BOOT_LOADER_INO     5      /* Boot loader inode */
#define EXT2_UNDEL_DIR_INO       6      /* Undelete directory inode */
#define EXT2_GOOD_OLD_FIRST_INO 11

なお、実装でのs_first_inoの取り扱いでは、inodeビットマップの検索スタートということでないようです。ext2_find_next_zero_bitはグループに関係なく先頭から0のビットを検索しているようです。そして取得したinodeが1〜10の場合はIOエラーとしています。たぶんファイルシステム作成において、先頭の0〜10ビットは1としているものと思われます。

inode番号が決定すると、次回のfind_group_orlovdeでのグループ割り当ての指針となる負債（スーパブロック内のs_debts[group]）を、ディレクトリなら+1、ファイルなら-1としています。

p/s
ｖｆｓ内においてinode番号はinodeを特定するもので、一意でなければならない。と思っていました。しかしinode番号はvfsとは関係ないものだというのを理解しました。ext2_new_inodeでnew_inodeを呼び出すことで、inodeメモリーキャッシュを確保し、イニシャライズしています。その時inode番号として静的変数last_inoをインクリメントすることでinode番号としています。しかし、ext2/3/4でinodeベースのローカルファイルシステムでinode番号が取得されると、そのinode番号で上書きしています。

inode番号はローカルファイルシステム上でinodeがどこにあるかを示すインデックスでvfsとは関係ないものなのです。