panda's tech note

Advent Calendar 2019: advfs

Day 9: ブロックデバイス対応(1)

昨日までで(何を持って最低限とするかは難しいですが)ファイルやディレクトリの作成・削除,ファイルの読み書きができるファイルシステムを作りました。シンボリックリンクやハードリンクなどは対応していませんが,それらや追加機能の実装をする前に,汚くなってきたコードをリファクタリングしようと思います。

ブロックデバイス上のファイルシステム

本来は ramfs でもメモリをページ管理をする必要があるのですが,昨日までは libc のメモリ管理が非常に便利でファイルの中身のバッファの割り当てに malloc()realloc() を使ってしまっていました。 libc が使える環境(ユーザランド)で ramfs を実装しているので,これでも良かったですが,通常はハードディスクやSSDなどのブロックデバイスをブロック単位で扱う必要があります。今日は,昨日までの実装を元にブロックデバイスにも対応できるようにリファクタリングしていきます。ここからは設計次第なので,私の場合はこう設計しましたが,別の設計でも良いと思います。

スーパーブロック

ファイルシステム全体の情報,例えばこのファイルシステムが使用できるブロックデバイスのサイズ, inode を管理するブロックへのポインタや最大 inode 数,最上位ディレクトリの inode 情報などのメタ情報を保存する領域をスーパーブロックと呼びます。

今回,スーパーブロックは,inode 領域へのポインタ,ブロック領域(データの実体)へのポインタ,inode の数および割り当て済みの数,データ用ブロック数および利用中の数,ブロックのフリーリスト(ブロック番号で指定),および最上位ディレクトリの inode 情報を保持します。inode 構造体については後述します。フリーリストは 0 番目のブロックがスーパーブロックであるため,この 0 を終端番号とします。

スーパーブロックの構造体は以下の通りです。今回はブロック番号は64ビットにしました。またエンディアンについては深く考えず,ホストのエンディアンのまま利用します。異なるマシンアーキテクチャをサポートする場合はエンディアンにも注意が必要です。

typedef struct {
    uint64_t ptr_inode;
    uint64_t ptr_block;
    /* # of inodes */
    uint64_t n_inodes;
    uint64_t n_inode_used;
    /* # of blocks */
    uint64_t n_blocks;
    uint64_t n_block_used;
    uint64_t freelist;
    /* Root inode */
    advfs_inode_t root;
} __attribute__ ((packed, aligned(ADVFS_BLOCK_SIZE))) advfs_superblock_t;

フリーリストは,ブロックの先頭64ビットに次のブロック番号を埋め込むことで実現します。初期化コードでもう一度説明しますが,以下の構造体として定義しています。

typedef struct {
    uint64_t next;
} advfs_free_list_t;

inode

inode 構造体は1エントリあたり512バイトの領域として定義します。つまり,1ブロックに8つの inode 情報を保存します。inode 構造体は以下の通り,inode の属性情報,エントリ名,16個分のブロック番号(配列)を持ちます。この16個のブロック番号のうち15個はファイルまたはディレクトリの実体(昨日までのコードの advfs_entry_file_tadvfs_entry_dir_t)を保存するための領域として利用します。16個目のブロックは,15個のブロックで不足した場合に16個目以降のブロックを参照するための配列(要素数は4096/8=512)を保存したブロックの番号が入ります。つまり,この配列の最後の番号は,リストの次のブロックへのポインタとして扱います。 

typedef struct {
    /* Attributes: 128 bytes */
    advfs_inode_attr_t attr;
    /* Name: 256 bytes */
    char name[ADVFS_NAME_MAX + 1];
    /* Blocks 128 bytes */
    uint64_t blocks[16];
} __attribute__ ((packed, aligned(512))) advfs_inode_t;

(予約領域を含め)128バイトの属性は以下の構造体で定義します。昨日の advfs_entry_t のファイルまたはディレクトリ固有の情報を除いたものが属性となります。

typedef struct {
    uint64_t type;
    uint64_t mode;
    uint64_t atime;
    uint64_t mtime;
    uint64_t ctime;
    uint64_t size;
    uint64_t n_blocks;
} __attribute__ ((packed, aligned(128))) advfs_inode_attr_t;

スーパーブロックの初期化

今日はスーパーブロックの初期化まで行います。

まず, ramfs 用のブロックデバイス領域として, 40 MiB (4096 * 10240: ADVFS_BLOCK_SIZE * ADVFS_BLOCK_NUM) の領域を確保します。今回は malloc() を使っていますが, mmap() を使った方が綺麗です。

    /* Initialize the block device */
    blkdev = malloc(ADVFS_BLOCK_SIZE * ADVFS_BLOCK_NUM);
    if ( NULL == blkdev ) {
        return -1;
    }
    sblk = blkdev;

次に,各種サイズチェックを行います。今回 inode 8個を1つのブロックに入れるため,予約 inode 数が8の倍数であること(正確には割り切れるサイズであること)を以下のコードで確認しています。これはコンパイル時に構造体のサイズをチェックしてもよいと思いますが,今回は実行時に確認しています。

    /* Ensure that each data structure size must be aligned. */
    assert( (ADVFS_BLOCK_SIZE % sizeof(advfs_inode_t)) == 0 );
    ratio = ADVFS_BLOCK_SIZE / sizeof(advfs_inode_t);
    assert( (ADVFS_INODE_NUM % ratio) == 0 );
    nblk = (ADVFS_INODE_NUM / ratio);

構造体のサイズ確認が済んだら,スーパーブロックの次に inode 配列を割り当てるため,inode 配列のブロック番号 ptr_inode1 にします。また,inode の数 n_inodes128 (ADVFS_INODE_NUM) にします。inode 配列には上の構造体サイズチェックの最後の行で取得できるブロック数分使用するため,この inode 配列の直後からブロック領域とするために,そのブロック番号 1 + nblkptr_block にセットします。また,これによりブロック領域で使えるブロック数は全体のブロック数から 1 + nblk を弾いた数になるので,この値を n_blocks にセットします。

    sblk->ptr_inode = 1;
    sblk->n_inodes = ADVFS_INODE_NUM;
    sblk->n_inode_used = 0;
    sblk->ptr_block = 1 + nblk;
    sblk->n_blocks = ADVFS_BLOCK_NUM - (1 + nblk);
    sblk->n_block_used = 0;

これで inode 配列とブロック領域の情報をスーパーブロックで定義できました。次に,inode 配列を初期化します。今回は全 inode を未使用状態 ADVFS_UNUSED としています。

    /* Initialize all inodes */
    inode = blkdev + ADVFS_BLOCK_SIZE * sblk->ptr_inode;
    for ( i = 0; i < (ssize_t)sblk->n_inodes; i++ ) {
        inode[i].attr.type = ADVFS_UNUSED;
    }

同様にブロック領域も初期化していきます。ブロック領域は,空きブロックをリンクドリスト形式で管理します。使用中のブロックは inode から参照されるため,スーパーブロックからは管理しません。空きブロックは未使用のブロックであるため,この未使用領域のうち先頭の8バイトをリンクドリストの次のブロックを指し示すポインタ(ブロック番号)として利用します。以下のコードでは,N番目のブロックの先頭に N+1 を書き込み,リストの最後のブロックからのポインタには 0 を代入することで終端しています。また,このフリーリストの先頭はブロック領域の先頭である sblk->ptr_block としています。

    /* Initialize all blocks */
    block = blkdev + ADVFS_BLOCK_SIZE * sblk->ptr_block;
    fl = block;
    for ( i = 0; i < (ssize_t)sblk->n_inodes - 1; i++ ) {
        fl->next = sblk->ptr_block + i + 1;
        fl = block + ADVFS_BLOCK_SIZE;
    }
    fl->next = 0;
    sblk->freelist = sblk->ptr_block;

最後に最上位ディレクトリの初期化を行います。

    /* Initialize the root inode */
    gettimeofday(&tv, NULL);
    sblk->root.attr.type = ADVFS_DIR;
    sblk->root.attr.mode = S_IFDIR | 0777;
    sblk->root.attr.atime = tv.tv_sec;
    sblk->root.attr.mtime = tv.tv_sec;
    sblk->root.attr.ctime = tv.tv_sec;
    sblk->root.attr.size = 0;
    sblk->root.attr.n_blocks = 0;
    sblk->root.name[0] = '\0';

今日のまとめと明日の予定

今日は,ブロックデバイスに対応できるようにリファクタリングを進めました。が,今日の時点では,初期化のみしか行って折らず,まだ実態は昨日のコードです。明日はリファクタリングを進めて,昨日までのコードを置き換えていこうと思います。