無料Wikiサービス | デモページ
Linux Kernel(2.6)の実装に関するメモ書き
リンク
最近更新したページ
検索

Buffer


概要

ディスクキャッシュのひとつ。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()でロックを取られている状態。
I/O中はロックが取られている。
BH_Mapped
Bufferがディスク上のどこかのブロックに対応している
(bh->b_bdev,bh->b_blocknrの値が有効)
BH_Async_Read
PageCacheにデータを読み込むためにRead I/O中であることを示す
(
関連関数:block_read_full_page())
BH_Boundary
Boundary Buffer(Boundary Buffer参照)
BH_New
各ファイルシステムのget_blockハンドラでディスクブロックのマッピングが新しく作成された場合にセットされる。

Bufferの管理方法

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

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

(2) address_space
BufferはPageCacheの一部として実装されているため、PageCacheと同じようにaddress_spaceで管理される(*1)。address_spaceのデータ構造についてはPageCache参照。

(*1) address_spaceはファイル/ディレクトリなどのinode単位に存在し、そのinodeが指すオブジェクト(ファイル/ディレクトリ等)のキャッシュ状況をページ単位に管理する。
PageCacheのデータは各ファイル/ディレクトリのaddress_spaceに登録されて管理されるが、Bufferはブロックデバイスのブロックをキャッシュするものなのでaddress_spaceにはブロックデバイス全体のaddress_space(bdev->bd_inode->i_mapping)が使用される(つまりBufferはデバイス毎にaddress_spaceが存在する)。


Bufferの検索

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

Bufferを検索する時は、デバイスとブロック番号で検索を行うが、address_spaceの方に検索に行く時は、ページキャッシュの実装に合わせてページ番号で検索する必要があるため、

  • デバイス→デバイスのaddress_space
  • ブロック番号→デバイス先頭からのページ番号
に変換して検索している。

__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/07/23 18:00:25 - kztomita
(2006/03/27 14:04:05 作成)
添付ファイル
buffer.png - kztomita