Linux Kernel(2.6)の実装に関するメモ書き

Buffer


Rev.29を表示中。最新版はこちら

概要

ディスクキャッシュのひとつ。Bufferはディスクのブロック単位のキャッシュを行なう。ブロック Read/WriteはBufferを経由して行なわれる。このため、ディスク上のi-nodeなどのメタデータはBufferにキャッシュされる。

ファイルのキャッシュにはPageCacheが使用される。

2.6からBufferはPageCacheの一部として実装されるようになった。

Bufferの構造

Bufferはディスクブロックをキャッシュするものなので、1つのBufferのサイズはブロックサイズに等しくなる。Bufferは物理ページ1ページ内に収容されるように作成される。このためPageSize 4KBに対しBlockサイズが1KBの場合、1Page内に4Block分のBufferが作られる(図1)。各Bufferには管理用のbuffer_headがある。Bufferを格納しているページのpage構造体はPG_privateフラグを持ち、privateがBuffer#0のbuffer_headへのアドレスを保持している。



図1 Bufferの構造


表1 buffer_headのフィールド(一部)
フィールド
意味
b_state
Bufferの状態を示すフラグ群(表2)
b_this_page
次のBufferのBufferHeadへのポインタ。循環リストになっている。
b_page
Bufferを格納しているページのpage構造体のアドレス。
b_blocknr
キャッシュしているブロックのブロック番号
b_data
Bufferのアドレス。
b_bdev
キャッシュしているブロックの属しているブロックデバイス

表2 bufferの状態フラグ(一部)
フラグ
説明
BH_Uptodate
Bufferのデータが最新の状態
BH_Lock
lock_buffer()でロックを取られている
BH_Mapped
Bufferがディスク上のどこかのブロックに対応している
(bh->b_bdev,bh->b_blocknrの値が有効)
BH_Boundary
Boundary Buffer(Boundary Buffer参照)

Bufferの管理方法

BufferはLRUリストとaddress_spaceのRadixTreeで管理される。

(1) LRUリスト
LRUリストはbh_lrus[]でCPU毎にリストを持つ。

(2) address_spaceのRadixTree
BufferはPageCacheの一部として実装されているため、PageCacheと同じようにaddress_spaceのRadixTree(mapping->page_tree)で管理される。これにより、ページ番号で高速に検索できる。address_spaceのデータ構造についてはPageCache参照。

mappingはキャッシュしているファイル(inode)単位に存在するものだが、Bufferはデバイスのブロックをキャッシュするものなのでmappingにはデバイスのmapping(bdev->bd_inode->i_mapping)が使用される(つまりBufferのRadixTreeはデバイス毎に存在する)。

Bufferを検索する時は、デバイスとブロック番号で検索を行うが、RadixTreeに検索に行く時は、
  • デバイス→デバイスのmapping
  • ブロック番号→デバイス先頭からのページ番号
に変換して検索している。

データ構造はPageCache参照。

Bufferの検索は__find_get_block()で行う。__find_get_block()はまずLRUリストから指定ブロックのBufferを探し、なければPageCacheから検索を行う。


__find_get_block()の処理概要
__find_get_block(bdev, block) - ブロックデバイスとブロック番号を指定
{
    bh = lookup_bh_lru() - LRUリストからBufferを検索

    if (bh == NULL) {
        /* LRUになかったのでRadixTreeを検索 */
        bh = __find_get_block_slow()
        ===== __find_get_block_slow()内 ====
            find_get_page() - PageCacheを検索(*1)

            見つけたPageのBufferHeadから
            該当Block#を持つBufferHeadを探して
            見つかったら返す
        ===== __find_get_block_slow()ここまで ====
        if (bh)
            bh_lru_install() - LRUリストに入れる
    }
    /* Bufferに対応するページにアクセスした事を
     * 示すフラグを設定。
     * 空きメモリが減ってきて不要なPageCacheが
     * 削除される時の順番に影響する。
     * Ref. to mark_page_accessed() */
    if (bh)
        touch_buffer(bh);
}
(*1) BufferはPageCacheの一部として実装されているため、PageCacheから検索をしている。PageCacheから検索をする際、address_spaceにはデバイスのinodeに対応するmapping(bdev->bd_inode->i_mapping)を指定し、offsetにはブロック番号をデバイス先頭からのページ番号に変換した値(block >> (PAGE_CACHE_SHIFT - bd_inode->i_blkbits))を指定している。

Block Read

デバイスの指定ブロックをReadするのには__bread()がある。__bread()はBufferに指定ブロックのデータがあるかチェックをして、あればBufferからデータを返す。Bufferが存在しなかった場合には、新たにBufferを作成して、ディスクに対してReadを行い取得したBlockデータをBufferに格納して返す。

bread()の処理概要
__bread(bdev, block, size)
{
    /* Bufferを検索
     * なかった場合は新しいBufferが作成されて返される
     */
    struct buffer_head *bh = __getblk(bdev, block, size);

    /* Bufferのデータが最新(Uptodate)状態でなければ、
     * デバイスからRead。
     */
    if (likely(bh) && !buffer_uptodate(bh))
        bh = __bread_slow(bh);
    return bh;
}
__getblk()は指定BlockのBufferを取得する。まずBufferを検索してBufferにデータがあれば、それを返す。なかった場合は新規にBufferを作成して返す。

__getblk()の処理概要
__getblk(bdev, block, size)
{
    /* Bufferを検索 */
    bh = __find_get_block();
    if (bh == NULL)
        /* Bufferになければ新規に作成 */
        bh = __getblk_slow(bdev, block, size);
            ==== __getblk_slow()内 ====
            for (;;) {
                bh = __find_get_block(bdev, block, size);
                if (bh)
                        return bh;
                /* Bufferを作成
                 * できなければメモリ解放を試みる */
                if (!grow_buffers(bdev, block, size))
                        free_more_memory();
            }
            ==== __getblk_slow()ここまで ====
}

__getblk()で指定Blockのデータがなかった場合、新しいBufferが作成されるので__bread()でbuffer_update()が偽になり__bread_slow()が呼び出される。__bread_slow()はRead I/O Requestを発行(submit_bh())して、I/Oが完了するまで現在のコンテキストをブロックする(wait_on_buffer())。ここでBlockしたプロセスはI/O完了時に呼び出されるハンドラend_buffer_read_sync()でunlock_buffer()が呼び出されるとWakeUpする。

__bread_slow()の処理概要
__bread_slow(bh)
{
    if (buffer_uptodate(bh)) {
        /* Bufferのデータが最新状態だった */
        return bh;
    } else {
        /* Read I/O完了時のハンドラ設定 */
        bh->b_end_io = end_buffer_read_sync;
        /* デバイスへのI/O Request発行 */
        submit_bh(READ, bh);
        /* I/O 完了待ち */
        wait_on_buffer(bh);
        if (buffer_uptodate(bh))
            return bh;
    }
    return NULL;
}

I/O完了時にはbh->b_end_ioに登録した関数が呼び出される。bread()の場合はend_buffer_read_sync()が呼び出される。end_buffer_read_sync()はBufferをUptodate状態にして、unlock_buffer()でRead待ちのプロセスをWakeupする。

end_buffer_read_sync()の処理概要
if (uptodate) {
    /* Uptodate状態にする */
    set_buffer_uptodate(bh);
} else {
    /* This happens, due to failed READA attempts. */
    clear_buffer_uptodate(bh);
}
/* __bread_slow()のwait_on_buffer()で
 * I/O完了待ち状態になっているプロセスをWakeup
 */
unlock_buffer(bh);

関連関数

alloc_page_buffers(page, size, retry)
指定ページに対してBufferHeadのリストを作成する

最後のBufferHeadのb_this_pageはまだNULL
struct pageのprivateも未設定

link_dev_buffer(page, head)
最後のBufferHeadのb_this_pageを設定して循環リストにする
page->privateの設定

submit_bh(rw, bh)
指定したbhに関してbio(Block I/OのRequest構造体)を作成しsubmit_bio()を呼び出しI/O Requestを発行する。

lock_buffer(bh)
Bufferのロック(BH_locked)を取得する。
既に取られていた場合は、取れるまでブロックする(*1)。

(*1) wait_on_bit_lock()でbh->b_stateのBH_Lockを取得できるまでブロックする。

unlock_buffer(bh)
ロック(BH_locked)を解放する。
lock_buffer()やwait_on_buffer()でロック解放待ちのプロセスがいた場合、プロセスをWakeupする(*2)。

(*2) wake_up_bit(&bh->b_state, BH_Lock)でbh->b_stateのBH_Lockビットがクリアされるのを待っているプロセスを起こす。

wait_on_buffer(bh)
Bufferのロック(BH_locked)が解除されるのを待つ(*3)。
unlock_buffer()でロックが解除されるとWakeupされる。

(*3) wait_on_bit()でbh->b_stateのBH_Lockビットがクリアされるまでブロックする。


関連ページ

PageCache


最終更新 2007/03/03 16:27:28 - kztomita
(2006/03/27 14:04:05 作成)
添付ファイル
buffer.png - kztomita


リンク
最近更新したページ
検索