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

minixのファイルシステムからデータを読む。

自作OS

自作カーネル用に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版に書いてありますのでそちらをご参考ください。

ext2minixファイルシステムも基本は同じで、ディレクトリ・ファイルの検索は、このような形です。
ディレクトリエントリを読む→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ファイルシステムは一応読むことができるようになったので、これを自作カーネルに移植していこうと思ってます。