panda's tech note

Advent Calendar 2019: advfs

Day 18: 重複排除機能(7)

inode からのブロック管理(論理ブロック)

昨日,ブロック領域は重複排除を行うと書きましたが,例外として,inode のブロック管理配列から連鎖するブロックは重複排除を行わないようにします。なお,論理ブロックの構成をおさらいすると以下の図のようになります。論理ブロック 0 から 6 までは inode 構造体,論理ブロック 7 は inode 構造体のブロック配列の最後の要素から参照される物理ブロック内の配列の先頭,と言うように,配列を連鎖させることで論理ブロックと物理ブロックのマッピングを行っています。巨大なファイルになると,このリストの走査の計算量が無視できなくなると思いますが,今回の実装ではこのようにしています。

   +- inode -----+   
   | ...         |       +-------------------+
   | blocks[0]   |------>| Block 0           |
   | ...         |       +-------------------+  +-------------------+
   | blocks[6]   |----------------------------->| Block 6           |
   | blocks[7]   |--+                           +-------------------+
   +-------------+  |
                    |
   +----------------+
   |
   v
   +-------------+       +-------------------+
   | block[0]    |------>| Block 7           |
   | ...         |       +-------------------+  +-------------------+
   | block[510]  |----------------------------->| Block 517         |
   | block[511]  |--+                           +-------------------+
   +-------------+  |
                    |
   +----------------+
   |
   v
   +-------------+       +-------------------+
   | block[0]    |------>| Block 518         |
   | ...         |       +-------------------+
   | block[510]  |
   | block[511]  |
   +-------------+

この連鎖をするブロックは重複排除の対象からは外します。このようにブロックを直接読み書きするために, advfs_read_raw_block() 関数および advfs_write_raw_block() 関数を定義します。

int
advfs_read_raw_block(advfs_t *advfs, void *buf, uint64_t pos)
{
    uint64_t *block;

    block = _get_block(advfs, pos);
    memcpy(buf, block, ADVFS_BLOCK_SIZE);

    return 0;
}
int
advfs_write_raw_block(advfs_t *advfs, void *buf, uint64_t pos)
{
    uint64_t *block;

    block = _get_block(advfs, pos);
    memcpy(block, buf, ADVFS_BLOCK_SIZE);

    return 0;
}

これらの関数を使って,論理ブロックから物理ブロックの解決およびそのマッピング情報の更新関数を実装します。

まず,論理ブロックから物理ブロックの解決は _resolve_block() 関数とほぼ同じですが,inode 構造体のメモリを破壊的に操作しないように inode 番号 inr と論理ブロック番号 pos を引数に取る _resolve_block_map() 関数を以下の通り実装します。上記の図のリストをたどる処理を必要なブロックを読みながら行っているだけです。

static uint64_t
_resolve_block_map(advfs_t *advfs, uint64_t inr, uint64_t pos)
{
    uint64_t b;
    uint64_t *block;
    advfs_inode_t inode;
    uint8_t buf[ADVFS_BLOCK_SIZE];

    /* Read the inode */
    advfs_read_inode(advfs, &inode, inr);

    if ( pos < ADVFS_INODE_BLOCKPTR - 1 ) {
        /* The block number is included in the inode structure */
        b = inode.blocks[pos];
    } else {
        /* Resolve from the chain */
        b = inode.blocks[ADVFS_INODE_BLOCKPTR - 1];
        advfs_read_raw_block(advfs, buf, b);
        block = (uint64_t *)buf;
        pos -= ADVFS_INODE_BLOCKPTR - 1;
        while ( pos >= (ADVFS_BLOCK_SIZE / sizeof(uint64_t) - 1) ) {
            /* Get the next chain */
            b = block[ADVFS_BLOCK_SIZE / sizeof(uint64_t) - 1];
            advfs_read_raw_block(advfs, buf, b);
            block = (uint64_t *)buf;
            pos -= ADVFS_BLOCK_SIZE / sizeof(uint64_t) - 1;
        }
        b = block[pos];
    }

    return b;
}

次に,論理ブロックから物理ブロックへのマッピング情報を更新する関数を実装します。第2引数に inode 番号,第3引数に論理ブロック番号,第4引数に物理ブロック番号を渡します。基本的には _resolve_block_map() 関数と同様のロジックですが,最後に書き戻しを行っています。

static int
_update_block_map(advfs_t *advfs, uint64_t inr, uint64_t pos, uint64_t pb)
{
    uint64_t b;
    uint64_t *block;
    advfs_inode_t inode;
    uint8_t buf[ADVFS_BLOCK_SIZE];

    /* Read the inode */
    advfs_read_inode(advfs, &inode, inr);

    if ( pos < ADVFS_INODE_BLOCKPTR - 1 ) {
        /* The block number is included in the inode structure */
        inode.blocks[pos] = pb;

        /* Write back */
        advfs_write_inode(advfs, &inode, inr);
    } else {
        /* Resolve from the chain */
        b = inode.blocks[ADVFS_INODE_BLOCKPTR - 1];
        advfs_read_raw_block(advfs, buf, b);
        block = (uint64_t *)buf;
        pos -= ADVFS_INODE_BLOCKPTR - 1;
        while ( pos >= (ADVFS_BLOCK_SIZE / sizeof(uint64_t) - 1) ) {
            /* Get the next chain */
            b = block[ADVFS_BLOCK_SIZE / sizeof(uint64_t) - 1];
            advfs_read_raw_block(advfs, buf, b);
            block = (uint64_t *)buf;
            pos -= ADVFS_BLOCK_SIZE / sizeof(uint64_t) - 1;
        }
        block[pos] = pb;

        /* Write back */
        advfs_write_raw_block(advfs, buf, b);
    }

    return 0;
}

ブロックの読み書き

上記の関数を使って重複排除機能付きブロックの読み書きを実装します。15日目で実装した各関数とロジックは同じですが,inode 構造体を引数で渡さずに inode 番号を引数に取るようにします。これにより,inode の更新をブロック単位で行えるようになります。

ブロックの読み込みは以下の通りです。inode 番号 inr に対するディレクトリまたはファイルの論理ブロック posbuf に読み込みます。上記の _resolve_block_map() 関数により inode 番号 inr に対応する論理ブロック pos の物理ブロック番号を解決し,その値が 0 であれば内容がすべて 0x00 のブロック,それ以外であれば物理ブロック番号に対応するブロックを buf に読み込みます。

int
advfs_read_block(advfs_t *advfs, uint64_t inr, void *buf, uint64_t pos)
{
    uint64_t b;

    b = _resolve_block_map(advfs, inr, pos);
    if ( b == 0 ) {
        memset(buf, 0, ADVFS_BLOCK_SIZE);
    } else {
        advfs_read_raw_block(advfs, buf, b);
    }

    return 0;
}

書き込みは15日目に実装したのと同様に,重複排除を含むため,多少複雑になっています。以下のように inode 番号 inr の論理ブロック posbuf を書き込む関数 advfs_write_block() 関数を実装します。この関数ではまず,書き込むブロックのハッシュ値を取り,このハッシュ値に対応するブロックを取得します。そして,現在の論理ブロック pos に対応する物理ブロック番号を解決します。

書き込むブロックのハッシュ値に対応するブロックが存在する場合,当該ブロックの参照カウンタを1増加させ,現在のブロックが存在すれば参照カウンタを1減少させます。もし,参照カウンタが0になった場合はこのブロックを解放します。

書き込むブロックのハッシュ値に対応するブロックが存在しない場合は,単純に新しいブロックを確保・追加します。現在のブロックが存在すれば,そのブロックの参照カウンタを1減少させ,参照カウンタが0になった場合は解放します。

int
advfs_write_block(advfs_t *advfs, uint64_t inr, void *buf, uint64_t pos)
{
    uint64_t b;
    uint64_t cur;
    unsigned char hash[SHA384_DIGEST_LENGTH];
    advfs_block_mgt_t mgt;
    advfs_inode_t inode;

    /* Read the inode corresponding to inr */
    advfs_read_inode(advfs, &inode, inr);

    /* Calculate the hash value */
    SHA384(buf, ADVFS_BLOCK_SIZE, hash);

    /* Resolve the physical block corresponding to the logical block */
    cur = _resolve_block_map(advfs, inr, pos);

    /* Check the duplication */
    b = _block_search(advfs, hash);
    if ( b != 0 ) {
        /* Found */
        if ( cur != b ) {
            if ( cur != 0 ) {
                /* Unreference the old block */
                advfs_read_block_mgt(advfs, &mgt, cur);
                mgt.ref--;
                advfs_write_block_mgt(advfs, &mgt, cur);
                if ( mgt.ref == 0 ) {
                    /* Release this block */
                    _block_delete(advfs, cur);
                    advfs_free_block(advfs, cur);
                }
            }
            /* Referencde the new block */
            advfs_read_block_mgt(advfs, &mgt, b);
            mgt.ref++;
            advfs_write_block_mgt(advfs, &mgt, b);
        }
    } else {
        /* Not found, then allocate a new block, then write the content */
        b = advfs_alloc_block(advfs);
        advfs_write_raw_block(advfs, buf, b);
        memcpy(mgt.hash, hash, sizeof(mgt.hash));
        mgt.ref = 1;
        mgt.left = 0;
        mgt.right = 0;
        /* Add to the tree */
        _block_add(advfs, b);

        if ( cur != 0 ) {
            /* Unreference and free if needed */
            advfs_read_block_mgt(advfs, &mgt, cur);
            mgt.ref--;
            advfs_write_block_mgt(advfs, &mgt, cur);
            if ( mgt.ref == 0 ) {
                /* Release this block */
                _block_delete(advfs, cur);
                advfs_free_block(advfs, cur);
            }
        }

        /* Update the block map */
        _update_block_map(advfs, inr, pos, b);
    }

    return 0;
}

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

ブロック単位での読み書きに対応できてきました。明日はパス名から inode の検索やファイルの追加をブロック単位で行うために大規模な改造をします。