ジャーナリング付き入出力クラス (その1)

アプリケーション組み込みのデータ・ストアを書くのに、 ジャーナリング付きの低レベルの入出力クラスがあると便利かもしれないと思いついて正月明けから作りだしたのですけど、 予想よりも複雑になってしまい、 これを使っていくかどうか自分に疑問を覚えつつも、 将来、 何かの参考にするかもしれないと思い直して備忘録にしておきます。 当初は、 mmap を使うつもりだったのですが、 そこまで行き着く前に力尽きました。 なので、 入出力システム・コールに pread/pwrite を使っています。

    snapshot-file ←──── journaling-file
          │                  │      ↑
          │  ┌───────┘      │
    (block_underflow)            (journaling)
          ↓  ↓                      │
     block buffer cache ───────┘
          ↓  ↑
 (data_read)  (data_write)
          ↓  ↑
       (application)

このクラスは、 バイト単位の読み書きをブロック単位でバッファリングします。 バッファ・キャッシュは単純に LRU リング・バッファと上書きブロック表の組み合わせを採用しました。 ファイルへの書き出しは、 ジャーナリング・ファイルへのログ先行書き込みになっています。 キャッシュからあふれたときに、 上書き済みブロックも、 ジャーナリング・ファイルへと追記していきます。 クローズするときに、 キャッシュ中に残っている上書き済みブロックをジャーナリング・ファイルへ吐きだしてから、 ジャーナリング・ファイルからスナップショット・ファイルへ内容を書き写して更新をします。 さらに、 ファイルをオープンするときに、 ジャーナリング・ファイルが残っていると、 キャッシュへはジャーナリング・ファイルから優先して読み込みます。

クラス名は ioblock_type です。 横着してバッファリング機能とジャーナリング機能を、 一つのクラスにまとめてしまっています。 注意点として、 アプリケーション組み込みデータ・ストア用なので大きなファイルを扱う必要はなかろうと、 off_t 型が 4 バイトであることを前提にしているため移植性に問題が生じる可能性があります。

struct block_image_type;
struct block_ring_type;

class ioblock_type {
public:
    ioblock_type ();
    ~ioblock_type ();

    bool data_open (std::string const& name, std::string const& mode);
    bool data_read (std::string& data, std::size_t count, off_t offset);
    bool data_write (std::string const& data, off_t offset);
    bool journaling (void);
    bool data_flush (void);
    bool undo (void);
    void data_close (void);

    bool is_open (void) const { return m_desc >= 0; }
    bool fail (void) const { return m_fail; }
    bool set_fail (void) { m_fail = true; return false; }
    void set_cache_limit (std::size_t bytes);
    void set_dirty_limit (std::size_t bytes);
    void set_block_size (std::size_t bytes);
    void set_file_size (off_t offset) { m_file_size = offset; }
    off_t get_file_size (void) const { return m_file_size; }

private:
    bool block_underflow (std::string& buf, off_t offset);
    bool block_overflow (off_t offset);
    bool reload_head (void);
    bool redo (void);

    void cache_init (std::size_t count);
    std::string& get_block (off_t offset);
    void paint_dirty (off_t offset);
    void paint_clean (off_t offset);
    void dirty_clear (void);
    void cache_clear (void);
    void dispose_ring (void);

    bool m_fail;                    // ファイル操作に失敗すると真になり、 クローズ時に undo します
    std::string m_file_name;        // スナップショット・ファイル名
    std::string m_log_name;         // ジャーリング・ファイル名
    std::string m_mode;             // ファイルのアクセス・モード
    int m_desc;                     // スナップショット・ファイル・ディスクリプタ
    int m_log;                      // ジャナーリング・ファイル・ディスクリプタ
    std::size_t m_block_size;       // ブロックのバイト数
    std::size_t m_cache_limit;      // LRU リングが扱う最大バイト数
    std::size_t m_dirty_limit;      // ダーティ・バッファが扱う最大バイト数
    off_t m_orig_size;              // スナップショット・ファイルのバイト数
    off_t m_file_size;              // data_flush 後のスナップショット・ファイルのバイト数
    off_t m_save_point;             // undo 時にジャーリングの巻き戻しオフセット
    std::map<off_t,off_t> m_head;   // ジャーナリング中のブロック・オフセット表
    std::map<off_t,block_ring_type*> m_block;   // LRU リング中のブロック・オフセット表
    std::map<off_t,block_image_type*> m_dirty;  // 上書き済みブロックの表
    block_ring_type* m_ring;        // LRU リングの番兵
    block_ring_type* m_free;        // LRU リングのフリー・リストの番兵
};

バッファ・キャッシュに 2 種類の構造体を使います。 ブロックのデータを保持する構造体と、 それをリングにする構造体になっています。 他は STL の map を利用しています。

struct block_image_type {
    int m_rfcnt;                    // 参照カウンタ
    bool m_dirty_flag;              // 上書き済み印
    off_t m_offset;                 // スナップショット・ファイル中の先頭オフセット
    std::string m_data;             // キャッシュしているブロック・データ

    block_image_type () : m_rfcnt (1), m_dirty_flag (false), m_offset (0), m_data () {}
};

struct block_ring_type {
    block_ring_type* m_next;
    block_ring_type* m_prev;
    block_image_type* m_image;
};

ブロック・バッファ・キャッシュ用のフリー・リストと使用中リストの両端を番兵の m_ring と m_free につなげて一つのリングにしています。

void
ioblock_type::cache_init (std::size_t count)
{
    m_head.clear ();
    m_block.clear ();
    dirty_clear ();
    dispose_ring ();
    m_ring = new block_ring_type[count + 2U];
    if (m_ring == nullptr)
        return;
    m_free = m_ring + 1;
    block_ring_type* cell = m_free;
    for (std::size_t j = 0; j < count; ++j) {
        ++cell;
        relink (cell - 1, cell, cell, cell + 1);
        cell->m_image = new block_image_type;
    }
    relink (cell, m_ring, cell, m_ring);
    relink (m_ring, m_free, m_ring, m_free);
    relink (m_free, m_free + 1, m_free, m_free + 1);
}

双方向リンクを書き直すのに便利な relink 手続きは、 40年前の名著 Kernighan & Plauger Software Tools から借用しました。

static inline void
relink (block_ring_type* p, block_ring_type* u, block_ring_type* v, block_ring_type* q)
{
    u->m_prev = p;
    v->m_next = q;
}

ブロックのデータを保持する構造体は、 読み込みされただけのものはリングだけにつながっていて、 キャッシュからあふれたブロックはデータを初期化して再利用します。 書き込みがあったブロックの構造体は、 リングと m_dirty の両方につながれて、 リングからあふれたときは、 リングから取り外されて、 m_dirty 表だけにつながります。

std::string&
ioblock_type::get_block (off_t offset)
{
    if (m_block.count (offset) == 0) {
        if (m_dirty.count (offset) > 0) {
            return m_dirty[offset]->m_data;
        }
        block_ring_type* earliest = m_free->m_next;
        if (earliest == m_ring) {
            earliest = m_free->m_prev;
            if (earliest->m_image->m_dirty_flag) {
                --(earliest->m_image->m_rfcnt);
                earliest->m_image = new block_image_type;
            }
        }
        m_block[offset] = earliest;
        earliest->m_image->m_offset = offset;
        earliest->m_image->m_data.clear ();
    }
    block_ring_type* cell = m_block[offset];
    if (m_ring != cell->m_prev) {
        relink (cell->m_prev, cell->m_next, cell->m_prev, cell->m_next);
        relink (cell, m_ring->m_next, cell, m_ring->m_next);
        relink (m_ring, cell, m_ring, cell);
    }
    return cell->m_image->m_data;
}

バッファリングされているブロックに書き込みしたときは、 paint_dirty メンバ関数で、 m_dirty にもブロックの構造体をつなぐようにします。

void
ioblock_type::paint_dirty (off_t offset)
{
    if (m_block.count (offset) > 0) {
        block_image_type* image = m_block[offset]->m_image;
        if (! image->m_dirty_flag) {
            image->m_dirty_flag = true;
            ++(image->m_rfcnt);
            m_dirty[offset] = image;
        }
    }
}

m_dirty 表につながったブロックの構造体を、 ジャーナリングしてメモリ中に残す必要がなくなったときは、 dirty_clear で適宜開放します。 不要になったかどうかは参照カウンタで調べています。

void
ioblock_type::dirty_clear (void)
{
    for (auto it = m_dirty.begin (); it != m_dirty.end (); ++it) {
        if (it->second != nullptr) {
            it->second->m_dirty_flag = false;
            if (--(it->second->m_rfcnt) <= 0) {
                delete it->second;
                it->second = nullptr;
            }
        }
    }
    m_dirty.clear ();
}

リングの廃棄時も同様にブロックの構造体の参照カウンタを減じて不要になったときに領域を開放します。

void
ioblock_type::dispose_ring (void)
{
    if (m_ring != nullptr) {
        block_ring_type* p = m_ring;
        do {
            if (p->m_image != nullptr && --(p->m_image->m_rfcnt) <= 0) {
                delete p->m_image;
                p->m_image = nullptr;
            }
            p = p->m_next;
        } while (p != m_ring);
        delete[] m_ring;
        m_ring = nullptr;
    }
}