UNIX V6のディスクを読んでルートディレクトリのファイル一覧を出力してみる

前回、PDP-11の磁気ディスクRK11からブロック読み出しするをやったが、ディスクからデータを読み出せたら、あとはもうファイルシステムだ。（気が早いか）

でもまあ、とりあえず、UNIXのinodeファイルシステムの門を叩く。
ここでは、PDP-11(エミュ)からUNIX V6のディスクを読んで、ルートディレクトリのファイル一覧を出力するまでをやってみる。
要するにls /みたいなことを。Bare-metal programmingでやる。

いろいろ処理が増えてきたので、ソースコードはGitHubで管理するとして、ここではメモだけを残す。

inodeファイルシステム

UNIXのinodeファイルシステムは、Ken ThompsonさんとDenis Ritchieさんらの珠玉の作品で、
とてもシンプルな構造ながら柔軟なファイル管理ができる、UNIXのコアにしてエッセンスみたいなものだ

inodeファイルシステムのアイディアを簡単にまとめると：
1. ファイルそのものに管理情報は付けない(ファイルは単なるデータの固まり）
2. ファイルに付随する管理情報は別にもつ。これがinode。
3. inode情報はファイルの数分あるが、全ファイルのinode情報はディスク上にまとまって順番に格納される。このinodeの配列を指すインデックスがinode番号。
4. ディレクトリはファイルの一種で、ファイル名とinode番号がセットになった配列になっている。

ディスク上に格納されているinodeの情報（構造体）は下記の通り。

inod.h

struct  inode
{
    int  i_mode;
    char i_nlink;
    char i_uid;
    char i_gid;
    char i_size0;
    char *i_size1;
    int  i_addr[8];
    int  i_atime[2];
    int  i_mtime[2];
};

（上記はUNIX V6ソースコードからの抜粋。）

inode情報のサイズは32バイト。
OSの管理情報は置いといて、ローレベルで単純にファイルの読み書きができればいいだけなら、必要な情報って以下だけだ。

    char i_size0;     // ファイルサイズの上位８ビット
    char *i_size1;    // ファイルサイズの下位16ビット
    int  i_addr[8];   // ファイルの格納先ブロック番号の配列

なぜかi_size1がchar型のポインタだが、これはUNIX V6時代のC言語がunsignedがなかったため、ポインタ(16ビット長）で代用していたためらしい。
（個人的にはこういうのは好きで、ありものの道具でとりあえず間に合わせ、動くものをこしらえてから改善していく、という姿勢が見えていいなあ。と。）

ファイルサイズは24ビットまでということは、最大16MBまで扱えるように考慮したということか。
とはいえ、以前勉強メモでまとめたが、RKのディスクカードリッジ一枚で2.5MBまでしか入らないので、この時代としては十分すぎるほどだったのでしょう。

一方で、格納先のブロックのアドレス情報は8つ分しか配列が用意されていない。1ブロックは512バイトなので、これだけだと512*8で4KBまでの大きさのファイルしか扱えない。

実際は拡張モードが用意されてて、i_addr[]の差し先のブロック（512バイト）の中身が、さらに別のブロックのインデックスになっているという構造も使えるのだが、ここでは詳細は省く。
ここら辺は書籍「はじめてのOSコードリーディング」が詳しいのでおすすめです。

UNIX V6のディスク構成

さて、inodeはどこに格納されるのか？
UNIX V6のディスクフォーマットの構成は下記の通り。

ブロック番号	格納されているデータ
0	カーネルブートローダー
1	ディスク管理情報（スーパーブロック）
2	inode管理領域
..	....
n-1	inode管理領域
n	ファイルデータ保存領域
..	....

PDP-11が起動するとブロック０を読みにいって、そこに格納されているカーネルブードローダーがメモリ上に展開され実行される。
カーネルブートローダーはユーザからカーネル名('unix'など）の入力をうけつけ、カーネルを０番地にロードしてそこに飛ぶ。（ブートローダーは512バイト以内で収めないといけなので、アセンブラで書かれている。）

スーパーブロックと呼ばれるディスク管理情報にinode領域の大きさなどの情報が入っている。
あとは効率的なディスクアクセスを実現するために、空きブロックリストの管理も行っている。
inode領域はディスクの容量の大きさによって変わる。（まあ最大のinodeの数＝管理できるファイル数なので）

でまあ、今回はここは関係なくて、上記のinode情報の開始ブロックがブロック２、ということだけ分かれば十分。
inode情報は32バイトで、１ブロックには512/32で16個入る。いくつあるか分からないが、複数の連続ブロック領域にずらっと並んでいる。

任意のinodeの情報を取得する関数は下記のように書ける。

#define BLOCK_SIZE 512

typedef enum {
    IGET_OK,
    IGET_ERROR
} IgetResultT;

IgetResultT
iget(int ino, inode_t *dst_ibuf)
{
    void memcpy(void *dst, void *src, int n);
    static const int inode_start_block = 2;
    static const int inodes_per_block = BLOCK_SIZE / sizeof(inode_t);

    if (ino <= 0)
       return IGET_ERROR;

    static char _buf[BLOCK_SIZE];
    int blk_no = inode_start_block + (ino-1) / inodes_per_block;
    read_blk(0, blk_no, _buf);

    int i_offset = ((ino-1) % inodes_per_block) * sizeof(inode_t);
    memcpy(dst_ibuf, _buf+i_offset, sizeof(inode_t));

    return IGET_OK;
}

UNIX V6ではinodeは1番から始まっているので関数の仕様もそれに習う。
上記は、スーパーブロックの情報を見に行ってないので、とりうるinoの最大値は考慮していない。

read_blk()関数はこちら、memcpy()関数の説明は省く。詳細はGitHubのソース参照のこと。

inode_tは、UNIX V6のソースそのままではなく、とりあえず以下のように定義し直している。

typedef struct inode {
  uint16_t i_mode;
  char i_nlink;
  char i_uid;
  char i_gid;
  uint8_t i_size0;
  uint16_t i_size1;
  uint16_t i_addr[8];
  int16_t i_atime[2];
  int16_t i_mtime[2];
} inode_t;

さて、iget()でinode情報が取得できるようになったので、あとはルートディレクトリの情報をとりにいけばいい。
ルートディレクトリの情報はinode番号1番に格納されている。つまり、iget(1, &inode)するだけだ。

以下、ルートディレクトリ内のファイル一覧を出力する部分。

typedef struct {
  uint16_t ino;
  char name[14];
} dir_t;

int
cstart()
{
  // get root's inode info
  inode_t inode;
  iget(1, &inode);

  // print file name in root directory
  dir_t dir_info[BLOCK_SIZE/sizeof(dir_t)],
        *dirp = dir_info;
  read_blk(0, inode.i_addr[0], (void*)dir_info);
  do {
      if (dirp->name[0] == '\0') break;
      puts (dirp->name); puts("\n\r");
      dirp++;
  } while (dirp < (dir_info+BLOCK_SIZE));

  while(1);
}

実行

PDP-11エミュ(simh)で動かしてみる。

$pdp11 rc-pdp11

PDP-11 simulator V3.9-0
Disabling XQ
sim> g
..
.
unix
rkunix
dev
bin
etc
usr
usr2
tmp
lib
mnt
mnt2
test.c
rkunix.40
rkunix.70

ソースコード

GitHub: https://github.com/yenshan/p_uv6pdp11/tree/master/ls_root

参考文献

1.「はじめてのOSコードリーディング」（まだ全部読んでませんが・・・）
2.Denis Ritchieさんの論文「The UNIX Time-Sharing System」もおすすめ。(ネットで検索すれば出てきます）