読者です 読者をやめる 読者になる 読者になる

ext2実装の道

linux

自作カーネルファイルシステムext2を使う予定で進めているのですが、ext2の構造自体よく知らないので、
まずはext2の勉強がてらLinux上のユーザランドで動くプログラムとして実装して、それを移植する方向で進めてます。
元々、自作カーネルBochskvmqemu)で動かしているので、ここで使用している仮想HDDはLinux上では単なるバイナリファイルです。
とは言っても、データ自体は歴としたext2ファイルシステムなので、これをmmapしてメモリに読み込んでしまえば、テスト・デバッグが楽だよね〜と思って、こういう形で進めることにしました。
今のところ、HDDイメージ直下のファイル・ディレクトリの一覧を取得できるようにはなってます。
#実験中のコードなので、綺麗ではありません><
ext2ファイルシステム自体の説明は、検索するとたくさんでますので、そちらをご参考。。。

実験中のソースはgithubに置いてあります。
ユーザランドで動くとはいえ、自作カーネルに移植することを前提にしていますので、ext2ファイルシステムで使う構造体などは、自作カーネルのヘッダを使ってます。

このような状態のHDDイメージがあって、

[masami@moonlight:~/experiment/ext2]% sudo mount ./hda.img /media/disk -o loop
[masami@moonlight:~/experiment/ext2]% ls /media/disk 
./  ../  dir_A/  dir_a/  lost+found/  test.txt

動かすとこんな感じです。

[masami@moonlight:~/experiment/ext2]% ./ext2test 
file size is 10321920
The file system was created by Linux
Inodes count 2528 : Block count 10080
Reserved block count 504
Free block count 9658
Rree inode count 2512
First block 1
Block size 1024
Block group nr is 0
Fragment size 1024
First data block is 0x1
First inode 11
Inode size 128
Block per group 0x2000
Inode per group 0x4f0
block group[0]: bg_block_bitmap is 0x2a(0xa800) : bg_inode_bitmap is 0x2b(0xac00) : bg_inode_table is0x2c(0xb000)
block group[0] has 4 directories
Block Data starts 0x32800
Free blocks 0x1f24
Free inodes 0x4e2
inode[2]= [.]
inode[2]= [..]
inode[11]= [lost+found]
inode[1265]= [dir_a]
inode[1266]= [dir_A]
inode[14]= [test.txt]
Next is 0x800800
block group[1]: bg_block_bitmap is 0x2a(0xa800) : bg_inode_bitmap is 0x2b(0xac00) : bg_inode_table is0x2c(0xb000)
block group[1] has 2 directories
Block Data starts 0x32800
Free blocks 0x1f29
Free inodes 0x4e5
inode[2]= [.]
inode[2]= [..]
inode[11]= [lost+found]
inode[1265]= [dir_a]
[masami@moonlight:~/experiment/ext2]% 

テストに使ってるHDDイメージをdumpe2fsしたときの結果はこちらです。

/sbin/dumpe2fs hda.img
dumpe2fs 1.41.11 (14-Mar-2010)
Filesystem volume name:   <none>
Last mounted on:          <not available>
Filesystem UUID:          6b2da9be-e3ce-4b84-aef5-ea86381f5d8b
Filesystem magic number:  0xEF53
Filesystem revision #:    1 (dynamic)
Filesystem features:      ext_attr resize_inode dir_index filetype sparse_super
Filesystem flags:         signed_directory_hash 
Default mount options:    (none)
Filesystem state:         clean
Errors behavior:          Continue
Filesystem OS type:       Linux
Inode count:              2528
Block count:              10080
Reserved block count:     504
Free blocks:              9658
Free inodes:              2512
First block:              1
Block size:               1024
Fragment size:            1024
Reserved GDT blocks:      39
Blocks per group:         8192
Fragments per group:      8192
Inodes per group:         1264
Inode blocks per group:   158
Filesystem created:       Sun Apr 25 11:51:59 2010
Last mount time:          Tue Apr 27 22:57:37 2010
Last write time:          Tue Apr 27 22:58:02 2010
Mount count:              4
Maximum mount count:      37
Last checked:             Sun Apr 25 11:51:59 2010
Check interval:           15552000 (6 months)
Next check after:         Fri Oct 22 11:51:59 2010
Reserved blocks uid:      0 (user root)
Reserved blocks gid:      0 (group root)
First inode:              11
Inode size:	          128
Default directory hash:   half_md4
Directory Hash Seed:      6e1cf179-37fa-4286-8ed6-fd6713b3b9b2


Group 0: (Blocks 1-8192)
  Primary superblock at 1, Group descriptors at 2-2
  Reserved GDT blocks at 3-41
  Block bitmap at 42 (+41), Inode bitmap at 43 (+42)
  Inode table at 44-201 (+43)
  7972 free blocks, 1250 free inodes, 4 directories
  Free blocks: 218-3584, 3587-4608, 4610-8192
  Free inodes: 15-1264
Group 1: (Blocks 8193-10079)
  Backup superblock at 8193, Group descriptors at 8194-8194
  Reserved GDT blocks at 8195-8233
  Block bitmap at 8234 (+41), Inode bitmap at 8235 (+42)
  Inode table at 8236-8393 (+43)
  1686 free blocks, 1262 free inodes, 2 directories
  Free blocks: 8394-10079
  Free inodes: 1267-2528

そして実際のコードですが、まずはヘッダのインクルードがあって、

#include "ext2fs.h"
#include "ext2_blockgroup.h"
#include "ext2_inode.h"
#include "ext2_dentry.h"

メイン関数はこんな感じになってます。

int main(int argc, char **argv)
{
	unsigned long size = 0;
	int block_cnt = 0;
	struct ext2_superblock sb;
	struct ext2_blockgroup *block_group;
	struct binary_tree *btree;
	int i;

	// Get HDD image file size and mmap the image.
	size = get_file_size();
	file_system = map2memory(size);

	printf("file size is %ld\n", size);

ここまでは単に、HDDイメージのファイルをmmapしてるだけです。変数「file_system」にHDDのイメージがコピーされてます。
そして、スーパーブロックの読み込みです。

	// Read super block which in block group zero.
	read_super_block(&sb);

ディスクの先頭1024バイトはブートブロックとかなので、飛ばして、1024バイト目からがスーパーブロックの開始になります。
なので、memcpyで一気に読み込みます。

static void read_super_block(struct ext2_superblock *sb)
{
	// Super block starts at address 1024. 
	memcpy(sb, file_system + SUPER_BLOCK_SIZE, sizeof(struct ext2_superblock));
}

メイン関数に戻って、しばらくはprintf()が続きます。

	// print some information.
	printf("The file system was created by %s\n", get_os_name(&sb));
	printf("Inodes count %u : Block count %u\n", sb.s_inodes_count, sb.s_blocks_count);
	printf("Reserved block count %u\n", sb.s_r_blocks_count);
	printf("Free block count %u\n", sb.s_free_blocks_count);
	printf("Rree inode count %u\n", sb.s_free_inodes_count);
	printf("First block %u\n", sb.s_first_data_block);
	printf("Block size %u\n", get_block_size(sb));
	printf("Block group nr is %d\n", sb.s_block_group_nr);
	printf("Fragment size %u\n", get_fragment_size(sb));
	printf("First data block is 0x%x\n", sb.s_first_data_block);
	printf("First inode %u\n", sb.s_first_ino);
	printf("Inode size %u\n", sb.s_inode_size);
	printf("Block per group 0x%x\n", sb.s_blocks_per_group);
	printf("Inode per group 0x%x\n", sb.s_inodes_per_group);

次に、ブロックグループが何個あるのかを調べるのですが、正直上手いやり方ではないと思います、、、

	// how many block groups do I have?
	block_cnt = sb.s_blocks_count / sb.s_blocks_per_group;

	// Allocate memory to store block group data.
	block_group = malloc(sizeof(*block_group) * (block_cnt + 1));
	assert(block_group != NULL);
	memset(block_group, 0x0, sizeof(*block_group));

	// Setup binary tree to store dentries.
	btree = malloc(sizeof(*btree) * (block_cnt + 1));
	assert(btree != NULL);
	memset(btree, 0x0, sizeof(*btree));
	btree->right = btree->left = NULL;
 
	// Read first block group descriptor.
	read_block_group(&sb, block_group, SUPER_BLOCK_SIZE * 2);

ブロックグループディスクリプタの読み込みはread_block_group()で行ってます。
引数は、スーパーブロック構造体、データの保存先のブロックグループを表す構造体、読み込む位置です。
ブロックグループ0に関しては、スーパーブロックの後ろにあるので、単純に2048バイト目から読んでます。
実装自体は単純にです。

static void read_block_group(struct ext2_superblock *sb,  struct ext2_blockgroup *bg, unsigned long offset)
{
	memcpy(bg, file_system + offset, sizeof(struct ext2_blockgroup));
}

そしたら、ブロックグループ単位でデータの読み込みをします。

	for (i = 0; i < block_cnt + 1; i++) {
		if (block_group[i].bg_block_bitmap != 0 &&
			block_group[i].bg_inode_bitmap != 0 &&
			block_group[i].bg_inode_table != 0) {
			printf("block group[%d]: bg_block_bitmap is 0x%x(0x%x) : bg_inode_bitmap is 0x%x(0x%x) : bg_inode_table is0x%x(0x%x)\n",
				i, 
				block_group[i].bg_block_bitmap, blockid2address(&sb, block_group[i].bg_block_bitmap),
				block_group[i].bg_inode_bitmap, blockid2address(&sb, block_group[i].bg_inode_bitmap),
				block_group[i].bg_inode_table, blockid2address(&sb, block_group[i].bg_inode_table));
				printf("block group[%d] has %d directories\n", i, block_group[i].bg_used_dirs_count);
				printf("Block Data starts 0x%lx\n", get_block_data_address(&sb, block_group, i));
				printf("Free blocks 0x%x\n",  block_group[i].bg_free_blocks_count);
				printf("Free inodes 0x%x\n",  block_group[i].bg_free_inodes_count);

まず、ここまでで使ってる関数ですが、blockid2address()は、以下のような関数です。

static u_int32_t blockid2address(struct ext2_superblock *sb, u_int32_t id)
{
	return get_block_size(*sb) * id;
}

さらに、get_block_size()はマクロです。

#define MIN_BLOCK_SIZE 1024
#define get_block_size(sb) (MIN_BLOCK_SIZE << (sb).s_log_block_size)

これで何をやってるかというと、データの位置がブロックIDという形で設定されているので、バイト単位のアドレスに直してるだけです。
LBAで読む分には必要ないはずですが、こまかいアドレス指定をするには変換が必要です。
次のget_block_data_address()ですが、こちらは実際のデータが始まるアドレスの取得をしてます。

static unsigned long get_block_data_address(struct ext2_superblock *sb, struct ext2_blockgroup *bg, int block_nr)
{
	return (unsigned long) sb->s_inodes_per_group * sizeof(struct ext2_inode) 
				+  blockid2address(sb, bg[block_nr].bg_inode_table);
}

ここの計算ですが、まず、下のバイナリダンプはHDDイメージのダンプで、アドレス00032800からがデータブロックの開始位置です。
この00032800を求めてるのが、 get_block_data_address()の処理内容です。

00032800  02 00 00 00 0c 00 01 02  2e 00 00 00 02 00 00 00  |................|
00032810  0c 00 02 02 2e 2e 00 00  0b 00 00 00 14 00 0a 02  |................|
00032820  6c 6f 73 74 2b 66 6f 75  6e 64 00 00 f1 04 00 00  |lost+found......|
00032830  10 00 05 02 64 69 72 5f  61 00 00 00 f2 04 00 00  |....dir_a.......|
00032840  10 00 05 02 64 69 72 5f  41 00 00 00 0e 00 00 00  |....dir_A.......|
00032850  b4 03 08 01 74 65 73 74  2e 74 78 74 00 00 00 00  |....test.txt....|

sb->s_inodes_per_groupですが、最初の実行時のログに出てた「Inode per group 0x4f0」の部分で、値は1264(0x4f0)です。
ext2_inode構造体は0x80(128)バイトです。次に、blockid2address()を使って、このブロックグループのinodeテーブルの大きさからアドレスを計算します。ログだと、「Block Data starts 0x32800」と出てる部分です。
そうすると、0x4f0 * 0x80 + 0xb000 = 0x32800となって、データブロックの開始アドレスが分かります。

その次はディレクトリエントリの読み出しです。

				// Get directory entries.
				if (get_all_directories(btree + i, get_block_data_address(&sb, block_group, i), block_group[i].bg_used_dirs_count + 2) < 0)
					exit(-1);

これの実装は以下のような形です。ディレクトリエントリは限度はありますが可変長なので、データ長を先に読んでから、
再度データを取得する感じになっています。構造体としては以下のような形で、nameの長さはname_lenで決まります。
ディレクトリエントリの大きさ自体は、rec_lenに書かれています。

struct ext2_dentry {
	u_int32_t inode;
	u_int16_t rec_len;
	u_int8_t name_len;
	u_int8_t file_type;
	char *name;
};

本題の、get_all_directories()ですが、rec_len、name_lenの大きさを取得してから、データの読み出しをしていくだけです。
データは連続しているので、処理ごとにoffsetを更新していって、読み出すアドレスを指定してます。

static int get_all_directories(struct binary_tree *btree, unsigned long address, u_int16_t count)
{
	int i;
	u_int16_t rec_len;
	u_int8_t name_len;
	unsigned long offset = 0;

	for (i = 0; i < count; i++) {
		struct ext2_dentry *dentry;
		
		dentry = malloc(sizeof(*dentry));
		assert(dentry != NULL);

		rec_len = read_dentry_rec_len(address, offset);
		name_len = read_dentry_name_len(address, offset);

		read_dentry(dentry, address, offset, rec_len, name_len);

		printf("inode[%u]= [%s]\n", dentry->inode, dentry->name);

		btree = add_binary_tree(btree, dentry);

		offset += rec_len;
	}

	return 0;
}

そしてmain()に戻ると、またread_block_group()がいるのですが、今は、ブロックグループが2個しかないことを前提にしてます。
ext2ファイルシステムの仕様でスーパーブロックは1個ではなくて、コピーがいくつか置かれるようになっています。
昔のバージョンではすべてのブロックグループにあったようですが、今は「The groups chosen are 0, 1 and powers of 3, 5 and 7.」となっているようです。
テスト用のHDDイメージは10MBしかなく、これでも問題がないので、、、

				// Copy of super block which exists block group zero, one and so on.
				if (i == 0) {
					printf("Next is 0x%x\n", (sb.s_blocks_per_group * 0x400) + (0x400 * ((i + 1) * 2)));
					read_block_group(&sb, &block_group[i + 1], (sb.s_blocks_per_group * 0x400) + 0x800);
				}
		}
	
	}

	munmap(file_system, size);
	free(block_group);

	return 0;
}

一応これで終わりで、ディレクトリを探索していくとかはまだ出来てないですが、/直下にあるものに関しては見えるようになってきました。