テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

(writeboost report) セグメントのチェックサム

セグメントは, 以下の構成

  1. (先頭512B) id, checksum, length
  2. (~ 4KB) 各データブロックのメタデータ (sector, dirty bitなど)
  3. (+ 4KB * length) データブロック

先頭512Bを除いた領域を元にしてチェックサムを生成し, セグメントの真正性を検証する. 1sectorのライトはアトミックとすると, セグメントの状態は,

  1. 先頭512Bが古い. idが古いまま (#1)
  2. 先頭は更新された(故にチェックサムは正しい)が, データがパーシャルライトされたため, チェックサムが合わない.
  3. 全部書き込まれてチェックサムOK

のいずれかである. #1については, すでにそのセグメントはcleanであったため, 無視して良い. ログのリプレイアルゴリズムについては別に書いた.


さて, どういうチェックサムを生成するか.

Linux Kernelには, crypto APIというものがあり, md5sha1などのハッシュ関数を実装している. どういうアルゴリズムが利用出来るかは, crpto_register_algo()を追っていけば分かる(SHAは, これをラップしたcrypto_regsiter_shash()を調べれば分かる). device-mapperと同じで, モジュールがinitされた時にアルゴリズムを登録するという設計になっている.


アルゴリズムは, CRC32Cというものを使うこととする. 私はこの領域はあまり詳しくないが, ストレージ領域では頻繁に使われるアルゴリズムのようである.

例えば, btrfs

u32 btrfs_csum_data(char *data, u32 seed, size_t len)
{
        return crc32c(seed, data, len);
}

例えば, xfs

tatic inline __uint32_t
xfs_start_cksum(char *buffer, size_t length, unsigned long cksum_offset)
{
        __uint32_t zero = 0;
        __uint32_t crc;

        /* Calculate CRC up to the checksum. */
        crc = crc32c(XFS_CRC_SEED, buffer, cksum_offset);

        /* Skip checksum field */
        crc = crc32c(crc, &zero, sizeof(__u32));

        /* Calculate the rest of the CRC. */
        return crc32c(crc, &buffer[cksum_offset + sizeof(__be32)],
                      length - (cksum_offset + sizeof(__be32)));
}

他には, drdb, iscsi, device-mapper領域でも使われている. 従って, これより厳しい検査をする必要はないだろうと分かる.


crc32, crc32cは頻繁に使われるからか, crypto APIのラッパーが用意されている. これを使うのが良いだろうと分かる. 第一引数のcrcは, 何でも良さそうである.

u32 crc32c(u32 crc, const void *address, unsigned int length)
{
        struct {
                struct shash_desc shash;
                char ctx[crypto_shash_descsize(tfm)];
        } desc;
        int err;

        desc.shash.tfm = tfm;
        desc.shash.flags = 0;
        *(u32 *)desc.ctx = crc;

        err = crypto_shash_update(&desc.shash, address, length);
        BUG_ON(err);

        return *(u32 *)desc.ctx;
}