昨日はハッシュ関数による重複の検出について説明しました。今日からは重複ブロックの排除メカニズムを実装していきます。まずは，ブロックを管理するための構造体を定義し，ブロックに対するオペレーションを実装していきます。

ブロック管理をするための構造体を以下のように定義します。 hash はブロックのハッシュ値です。 ref は参照カウンタです。参照カウンタが1よりも大きい場合，複数のブロックが重複排除され，このブロックの内容で表されていることを意味します。つまり，このブロックへの書き込みを行う場合は別のブロックに書き込みます。 left および right はハッシュ値に対応するブロックを高速に検索するための二分木のポインタとして利用します。

typedef struct {
    /* Hash */
    unsigned char hash[SHA384_DIGEST_LENGTH];
    /* Reference counter */
    uint64_t ref;
    /* Left */
    uint64_t left;
    /* Right */
    uint64_t right;
} __attribute__ ((packed, aligned(128))) advfs_block_mgt_t;

この構造体は1ブロックにつき1つ用意し，inode 配列の後ろにブロック数分の配列として配置します。このため， main() 関数内の初期化を以下のように変更します。

    /* 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_inode = (ADVFS_INODE_NUM / ratio);

    assert( (ADVFS_BLOCK_SIZE % sizeof(advfs_block_mgt_t)) == 0 );
    ratio = ADVFS_BLOCK_SIZE / sizeof(advfs_block_mgt_t);
    nblk_mgt = (ADVFS_BLOCK_NUM / ratio);

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

    /* 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;
    }

    /* Initialize the block management array */
    mgt = blkdev + ADVFS_BLOCK_SIZE * sblk->ptr_block_mgt;
    for ( i = 0; i < (ssize_t)sblk->n_blocks; i++ ) {
        mgt[i].ref = 0;
    }

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

ブロック管理構造体で重複排除をする前に，ブロック書き込み時にハッシュ値をこの管理構造体に書き込む部分を先に実装します。実装は非常に単純で _write_block() 関数内で，ハッシュ値を計算し，このブロックに対応するブロック管理構造体のハッシュ値にコピーするだけです。

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

    /* Calculate the hash value */
    SHA384(buf, ADVFS_BLOCK_SIZE, hash);
    mgt = _get_block_mgt(advfs, pos);
    memcpy(mgt->hash, hash, SHA384_DIGEST_LENGTH);

    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];
        block = _get_block(advfs, b);
        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];
            block = _get_block(advfs, b);
            pos -= ADVFS_BLOCK_SIZE / sizeof(uint64_t) - 1;
        }
        b = block[pos];
    }
    block = _get_block(advfs, b);
    memcpy(block, buf, ADVFS_BLOCK_SIZE);

    return 0;
}

ブロック管理構造体へのアクセスは様々な場所から呼び出すため，以下のように _get_block_mgmt() 関数として実装しておきます。

static advfs_block_mgt_t *
_get_block_mgt(advfs_t *advfs, uint64_t b)
{
    uint64_t off;
    advfs_block_mgt_t *mgt;

    off = advfs->superblock->ptr_block_mgt;
    mgt = (void *)advfs->superblock + ADVFS_BLOCK_SIZE * off;

    return &mgt[b];
}

今日はブロックの書き込み時にハッシュ値を計算し，これをブロック管理構造体に保存するようにしました。明日はこのブロック管理構造体のハッシュ値での検索を高速に行うため，二分木を実装します。