自作カーネルはファイルシステムにext2を使う予定で進めているのですが、ext2の構造自体よく知らないので、
まずはext2の勉強がてらLinux上のユーザランドで動くプログラムとして実装して、それを移植する方向で進めてます。
元々、自作カーネルはBochs・kvm（qemu)で動かしているので、ここで使用している仮想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; }
一応これで終わりで、ディレクトリを探索していくとかはまだ出来てないですが、/直下にあるものに関しては見えるようになってきました。
