自作カーネル用にext2の実装をテストしてたんですが、inodeまわりでちょっとハマってたので、
ext2よりは簡単そうなminixのファイルシステムで実装の実験して、データを読めるようになりました。
ソースは例のごとくgithubにあります。
実装の方法は前回のext2と同じく、HDDのイメージをmmapしてデータを読むようにしてます。
Minixのファイルシステムもいくつかバージョンがあって、最近のMinix3ではV3みたいなのですが、
Linuxのmkfs.minixだとV1とV2しか作れないようだったので、mkfs.minixで作ったV2を読めるようにしました。
どうもMinix2.0.0のファイルシステムとも構造が微妙に違ったので、スーパーブロックとかinodeの構造体はmkfs.minixのソースをベースにしました。
本来、スーパーブロックとかは、ディスク上にあるデータだけでなくて、ディスクにはなくてメモリ上のみに存在するデータもあるのですが、
単に読むだけなので、その辺の実装はまだしてません。
Minixのファイルシステムのレイアウトはザクッと書くと、こんな感じになっていて、
ブートブロックとスーパーブロックは1kbです。inodeビットマップとゾーンビットマップはnブロック使用します。
#1ブロック＝＝1kbで作っています。
| ブートブロック | スーパーブロック | inodeビットマップ | ゾーンビットマップ | データブロック |
ゾーンとかブロックの説明はオペレーティングシステム第3版に書いてありますのでそちらをご参考ください。
ext2もminixのファイルシステムも基本は同じで、ディレクトリ・ファイルの検索は、このような形です。
ディレクトリエントリを読む→inode番号を取得→inodeを読む→ブロック番号を取得→ディレクトリエントリを読む→以下同様
それでは、スーパーブロックから。
struct minix_superblock {
u_int16_t s_ninodes;
u_int16_t s_nzones;
u_int16_t s_imap_blocks;
u_int16_t s_zmap_blocks;
u_int16_t s_firstdatazone;
u_int16_t s_log_zone_size;
u_int32_t s_max_size;
u_int16_t s_magic;
u_int16_t s_pad;
u_int32_t s_zones;
} __attribute__((packed));
ext2のスーパーブロックと比較しても結構小さいです。この中で主に使うフィールドは、s_firstdatazoneです。
これはデータブロックのゾーンが入ってます。このゾーンから実際のブロックを計算すれば、HDD上のデータブロックの先頭アドレスが取得できます。
最初にするのはスーパーブロックの読み込みで、これは1024バイト目からの1kbがデータの範囲です。
なので、単純にこのような形で読み込みます。
static void read_superblock(struct minix_superblock *sb) { // ignore boot block. memcpy(sb, file_system + 0x400, sizeof(*sb)); }
そうすると、テスト用HDDイメージのスーパーブロックはこのようなデータが入ってます。
Superblock info s_ninodes: 0xd20 s_nzones: 0x0 s_imap_blocks: 0x1 s_zmap_blocks: 0x2 s_firstdatazone: 0xd7 s_log_zone_size: 0x0 s_max_size: 0x7fffffff s_magic: 0x2478 s_pad: 0x1 s_zones: 0x2760
スーパーブロックの辺りをダンプするとこんな感じになってます。
00000400 20 0d 00 00 01 00 02 00 d7 00 00 00 ff ff ff 7f | ...............| 00000410 78 24 01 00 60 27 00 00 00 00 00 00 00 00 00 00 |x$..`'..........| 00000420 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| *
ext2の場合は、ブロックグループディスクリプターというものがあったりしたのですが、
MinixはこれだけでOKです。あとは、ディレクトリを辿ってファイルを検索したりできます。
ということで、ディレクトリを再帰的に辿って、どんなデータがあるか見ていくかという処理の場合、以下の用に書けます。
static void directory_walk(struct minix_superblock *sb, unsigned long address) { unsigned long offset = 0; struct minix_dentry dentry; struct minix_inode inode; unsigned long inode_tbl_bass = get_inode_table_address(*sb); int i; while (1) { // read first entry. read_dentry(&dentry, address, offset); if (dentry.inode == 0) break; read_inode(dentry.inode, &inode, inode_tbl_bass); printf("inode:0x%x name %s\n", dentry.inode, dentry.name); printf("i_mode: 0x%x(0x%x)\n", inode.i_mode, get_file_type(&inode)); printf("i_nlinks: 0x%x\n", inode.i_nlinks); printf("uid: 0x%x\n", inode.i_uid); printf("gid: 0x%x\n", inode.i_gid); printf("i_size: 0x%x\n", inode.i_size); printf("i_atime: 0x%x\n", inode.i_atime); printf("i_mtime: 0x%x\n", inode.i_mtime); printf("i_ctime: 0x%x\n", inode.i_ctime); for (i = 0; i < NR_I_ZONE; i++) { if (inode.i_zone[i]) printf("zone[%d]: 0x%x(0x%x)\n", i, inode.i_zone[i], get_data_zone(inode.i_zone[i])); } if ((get_file_type(&inode) == I_FT_DIR) && (strcmp(dentry.name, ".")) && (strcmp(dentry.name, ".."))) directory_walk(sb, get_data_zone(inode.i_zone[0])); offset += sizeof(dentry) - 1; } }
1番目の引数は、読み込んだスーパーブロックで、2番目の引数は、データブロックの先頭アドレスです。
これは以下のように取得してます。
#define get_first_data_zone(sb) (sb).s_firstdatazone * 0x400
1ブロック1kbなので、これにs_firstdatazoneの値（0xd7）を掛けて、0x35c0を得ます。
0x35c0辺りのデータはこのようになっていて、ディレクトリエントリがいくつか置かれています。
00035c00 01 00 2e 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00035c10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00035c20 01 00 2e 2e 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00035c30 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00035c40 02 00 64 69 72 5f 61 00 00 00 00 00 00 00 00 00 |..dir_a.........| 00035c50 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00035c60 04 00 64 69 72 5f 41 00 00 00 00 00 00 00 00 00 |..dir_A.........| 00035c70 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00035c80 06 00 74 65 73 74 2e 74 78 74 00 00 00 00 00 00 |..test.txt......| 00035c90 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| *
directory_walk()に戻りまして、最初にしているこれですが、inodeテーブルのアドレスを取得してます。
unsigned long inode_tbl_bass = get_inode_table_address(*sb);
これは単なるマクロで、ブートブロックとか、inodeビットマップ、ゾーンビットマップを読み飛ばして、inodeテーブルのアドレスを計算するだけです。ここに各ディレクトリ・ファイルのinodeがあるので必須です。
#define get_inode_table_address(sb) 0x800 + ((sb).s_imap_blocks * 0x400) + ((sb).s_zmap_blocks * 0x400)
その後は、ディレクトリエントリの読み込みと、inodeの読み込みになります。
// read first entry. read_dentry(&dentry, address, offset); if (dentry.inode == 0) break; read_inode(dentry.inode, &inode, inode_tbl_bass);
Minixのディレクトリエントリはext2と違って固定長です。
ext2は名前は0〜255バイトの可変長データなので、ディレクトリエントリ内に、データの長さと、名前の長さのフィールドを持っていましたが、Minixはinodeと名前しかもってません。
mkfs.minixのmanによると、名前の長さは14バイトまたは30バイトとだけど、デフォルトで30バイトにしてると書いてあったので、
名前は30バイトとしています。inodeは16bitで、合計32バイトのデータ構造です。大きさが中途半端なので、packed属性でパディングが入らないようにしてます。
上で貼り付けた、ディレクトリエントリのダンプもデータは32バイト単位になってます。
#define MAX_NAME_LEN 30 + 1 struct minix_dentry { u_int16_t inode; char name[MAX_NAME_LEN]; } __attribute__((packed));
ディレクトリエントリを読むと、ファイル/ディレクトリ名に該当するinode番号が取得できますので、次は、このinodeを読みます。
inodeはこんな感じの構造体です。i_modeはディレクトリとかレギュラーファイルの区別するのに使ってます。
あとは、i_sizeでファイルサイズを取得するのと、i_zoneからデータの位置を計算します。
i_zoneの役割はオペレーティングシステム第3版にあります。ようはデータが大きい場合に（1ブロックで収まらない）、例えば2ブロック必要なら、i_zone[0]とi_zone[1]にゾーンのアドレスが入るという感じです。
#define NR_I_ZONE 10 struct minix_inode { u_int16_t i_mode; u_int16_t i_nlinks; u_int16_t i_uid; u_int16_t i_gid; u_int32_t i_size; u_int32_t i_atime; u_int32_t i_mtime; u_int32_t i_ctime; u_int32_t i_zone[NR_I_ZONE]; } __attribute__((packed));
ここまで分かれば、ディレクトリエントリを読んだり、inodeを読んだりするのは簡単です。
static void read_dentry(struct minix_dentry *dentry, unsigned long address, unsigned long offset) { // dentry->name is 15 bytes which reserved for '\0'. memcpy(dentry, file_system + address + offset, sizeof(*dentry) - 1); } static void read_inode(u_int16_t inode_num, struct minix_inode *inode, unsigned long addr) { memcpy(inode, file_system + addr + ((inode_num - 1) * sizeof(*inode)), sizeof(*inode)); }
ディレクトリの探索は素直に再帰処理にしているので、今見ているinodeがディレクトリでかつ、"."や".."で無ければ、
そのディレクトリのi_zoneをアドレスとして、directory_walk()を呼び出します。
if ((get_file_type(&inode) == I_FT_DIR) && (strcmp(dentry.name, ".")) && (strcmp(dentry.name, ".."))) directory_walk(sb, get_data_zone(inode.i_zone[0])); offset += sizeof(dentry) - 1;
最後のoffsetに対する計算は単に、ディレクトリエントリを1個読み込んだら、次のエントリにオフセットを進めてるだけですね。
これで、ディレクトリの再帰検索が完了です。
これを応用して、こんな感じでファイルの読み出しも出来てます。実行結果から先に書くと、/dir_a/dir_b/foobar.txtと/test.txtの中身をダンプさせてます。
Linux上で見るときはどこかにマウントしているので、パスはルートからでは無いですが。
>>>>>>>>>>read_file() test <<<<<<<<<<<<<<<< file /dir_a/dir_b/foobar.txt: size is 0x7 0x66 0x6f 0x6f 0x62 0x61 0x72 0x0a >>>>>>>>>>read_file() test <<<<<<<<<<<<<<<< file /test.txt: size is 0x6 0x41 0x42 0x43 0x44 0x45 0x0a >>>>>>>>>>read_file() test <<<<<<<<<<<<<<<< [masami@moonlight:~/experiment/ext2/minix]% cat /media/test/dir_a/dir_b/foobar.txt foobar [masami@moonlight:~/experiment/ext2/minix]% cat /media/test/test.txt ABCDE [masami@moonlight:~/experiment/ext2/minix]%
コードはこんな感じです。
static void read_file(struct minix_superblock *sb, const char *fname) { u_int16_t ino; struct minix_inode inode; unsigned long inode_tbl_bass = get_inode_table_address(*sb); char *data; int i; ino = find_file(sb, get_first_data_zone(*sb), fname); if (!ino) { printf("file %s not found\n", fname); return ; } read_inode(ino, &inode, inode_tbl_bass); printf("file %s: size is 0x%x\n", fname, inode.i_size); data = malloc(inode.i_size); assert(data != NULL); memcpy(data, file_system + get_data_zone(inode.i_zone[0]),inode.i_size); for (i = 0; i < inode.i_size; i++) printf("0x%02x ", data[i]); printf("\n"); }
find_file()はあんまり綺麗じゃないんですが、fnameで指定された名前のファイル/ディレクトリを再帰的に探索して、見つかったらそのinodeを返してます。見つからなければ、0を返します。
static u_int16_t find_file(struct minix_superblock *sb, unsigned long address, const char *fname) { unsigned long offset = 0; struct minix_dentry dentry; struct minix_inode inode; unsigned long inode_tbl_bass = get_inode_table_address(*sb); const char *tmp; u_int16_t ret = 0; int len = 0; int ftype; while (1) { // read first entry. read_dentry(&dentry, address, offset); if (dentry.inode == 0) break; read_inode(dentry.inode, &inode, inode_tbl_bass); tmp = fname; if (tmp[0] == '/') tmp = tmp + 1; ftype = get_file_type(&inode); if (ftype == I_FT_DIR) { len = count_delimita_length(tmp, '/'); if (len == -1) { if (!strcmp(tmp, dentry.name)) return dentry.inode; } else if (!strncmp(tmp, dentry.name, len)) { ret = find_file(sb, get_data_zone(inode.i_zone[0]), tmp + len); } else { // if final character is '/', finish searching. if (!strcmp(tmp + len, "/")) return dentry.inode; } } else if (ftype == I_FT_REGULAR) { if (!strcmp(dentry.name, tmp)) return dentry.inode; } if (ret) return ret; offset += sizeof(dentry) - 1; } return 0; }
ということで、Minixのファイルシステムは一応読むことができるようになったので、これを自作カーネルに移植していこうと思ってます。
