ページキャッシュのミスはどこで起きているのか
あけましておめでとうございます。これは「カーネル/VM Advent Calendar2011」35日目の記事です。そして2012年一発目の記事になります。
この記事ではページキャッシュミスについて書きます。ページキャッシュとDB(主にtmpfsと絡めたお話)についてはid:naoyaさんの記事*1が有名かと思います。
ディスクIOは遅いので、メモリ上にデータをキャッシュしている。それがページキャッシュである。読みたいファイルのデータがページキャッシュ上にあればディスクまで読みにいかずページキャッシュから読んで返す、これで高速化できる。
ページキャッシュは基数ツリー(radix tree)というデータ構造で管理されていて、エントリはページ単位(4096バイト)である。
だと言うことは知識として得ています。ただ「ページキャッシュ機構が透過的に働く」という表現が抽象的で書籍やWebの説明ではよく分からないわけです。なんとなくモヤッとした理解でとどまってしまいます。
ということで、ユーザアプリでread(2)が発行された際にページキャッシュミスが発生するロジックがLinuxカーネルのソースでどうなっているか、若干深めに追ってみたいと思います。
システムコールを担当する関数達は以下のようになっています。ファイルシステムはext4でカーネルソースのバージョンは3.0です。read(2)が発行されるとdo_sync_read()が呼ばれることを示しています。
const struct file_operations ext4_file_operations = { .llseek = ext4_llseek, .read = do_sync_read, .write = do_sync_write, .aio_read = generic_file_aio_read, .aio_write = ext4_file_write, .unlocked_ioctl = ext4_ioctl, (以下省略)
do_sync_read()はfs/read_write.cにあります。
ssize_t do_sync_read(struct file *filp, char __user *buf, size_t len, loff_t *ppos) { struct iovec iov = { .iov_base = buf, .iov_len = len }; struct kiocb kiocb; ssize_t ret; init_sync_kiocb(&kiocb, filp); kiocb.ki_pos = *ppos; kiocb.ki_left = len; kiocb.ki_nbytes = len; for (;;) { ret = filp->f_op->aio_read(&kiocb, &iov, 1, kiocb.ki_pos); if (ret != -EIOCBRETRY) break; wait_on_retry_sync_kiocb(&kiocb); } if (-EIOCBQUEUED == ret) ret = wait_on_sync_kiocb(&kiocb); *ppos = kiocb.ki_pos; return ret; }
for文の中でaio_read()を呼んでいます。これはまさしく、上のfile_operations構造体でいう所のgeneric_file_aio_read()のことです。ということでread(2)が発行されるとdo_read_sync()経由でgeneric_file_aio_read()が呼ばれることになります。
generic_file_aio_read()はmm/filemap.cにあります。
ssize_t generic_file_aio_read(struct kiocb *iocb, const struct iovec *iov, unsigned long nr_segs, loff_t pos) { struct file *filp = iocb->ki_filp; ssize_t retval; unsigned long seg = 0; size_t count; loff_t *ppos = &iocb->ki_pos; struct blk_plug plug; count = 0; retval = generic_segment_checks(iov, &nr_segs, &count, VERIFY_WRITE); if (retval) return retval; blk_start_plug(&plug); /* coalesce the iovecs and go direct-to-BIO for O_DIRECT */ if (filp->f_flags & O_DIRECT) { (省略) } count = retval; for (seg = 0; seg < nr_segs; seg++) { read_descriptor_t desc; loff_t offset = 0; /* * If we did a short DIO read we need to skip the section of the * iov that we've already read data into. */ if (count) { if (count > iov[seg].iov_len) { count -= iov[seg].iov_len; continue; } offset = count; count = 0; } desc.written = 0; desc.arg.buf = iov[seg].iov_base + offset; desc.count = iov[seg].iov_len - offset; if (desc.count == 0) continue; desc.error = 0; do_generic_file_read(filp, ppos, &desc, file_read_actor); retval += desc.written; if (desc.error) { retval = retval ?: desc.error; break; } if (desc.count > 0) break; } out: blk_finish_plug(&plug); return retval; }
2番目にでてくるif文ですが、O_DIRECTとはOSのページキャッシュに頼らず自前でキャッシュを持つ構造をしているRDBなどのシステムが使うopen(2)のオプションなので、今回は無視します。これはカーネル2.4以降で実装されたものらしいです。
generic_file_aio_read()はext4だけではなくext3やbtrfs、fuseでもfile_operations構造体*2に含まれています。
ブロックデバイス上のファイルに対してread(2)を発行する時はファイルシステムの種類に関わらずページキャッシュにファイルデータが存在するか確認しにいっていて、その部分のコードは統一されているということですね。
続いてfor文に移りますが、この中でdo_generic_file_read()が呼ばれています。これは同じくmm/filemap.cにある関数です。
static void do_generic_file_read(struct file *filp, loff_t *ppos, read_descriptor_t *desc, read_actor_t actor) { struct address_space *mapping = filp->f_mapping; struct inode *inode = mapping->host; struct file_ra_state *ra = &filp->f_ra; pgoff_t index; pgoff_t last_index; pgoff_t prev_index; unsigned long offset; /* offset into pagecache page */ unsigned int prev_offset; int error; index = *ppos >> PAGE_CACHE_SHIFT; prev_index = ra->prev_pos >> PAGE_CACHE_SHIFT; prev_offset = ra->prev_pos & (PAGE_CACHE_SIZE-1); last_index = (*ppos + desc->count + PAGE_CACHE_SIZE-1) >> PAGE_CACHE_SHIFT; offset = *ppos & ~PAGE_CACHE_MASK; for (;;) { struct page *page; pgoff_t end_index; loff_t isize; unsigned long nr, ret; cond_resched(); find_page: page = find_get_page(mapping, index); if (!page) { page_cache_sync_readahead(mapping, ra, filp, index, last_index - index); page = find_get_page(mapping, index); if (unlikely(page == NULL)) goto no_cached_page; } (以下省略)
ありました。for文の中でfind_get_page()を呼び出していて、pageがNULLならページキャッシュにミスヒットしたというロジックになっています。
find_get_page()もやはりmm/filemap.cにあります。
struct page *find_get_page(struct address_space *mapping, pgoff_t offset) { void **pagep; struct page *page; rcu_read_lock(); repeat: page = NULL; pagep = radix_tree_lookup_slot(&mapping->page_tree, offset); if (pagep) { page = radix_tree_deref_slot(pagep); if (unlikely(!page)) goto out; if (radix_tree_deref_retry(page)) goto repeat; if (!page_cache_get_speculative(page)) goto repeat; /* * Has the page moved? * This is part of the lockless pagecache protocol. See * include/linux/pagemap.h for details. */ if (unlikely(page != *pagep)) { page_cache_release(page); goto repeat; } } out: rcu_read_unlock(); return page; }
基数ツリーのライブラリ関数を呼び出して該当のファイルのデータがキャッシュにあるか検索しています。ちなみに基数ツリーを扱うライブラリはlib/radix-tree.cにありました。
address_space構造体のpage_treeに基数ツリーの構造が格納されているようです。address_space構造体の定義を見てみます。
include/linux/fs.h
struct address_space { struct inode *host; /* owner: inode, block_device */ struct radix_tree_root page_tree; /* radix tree of all pages */ spinlock_t tree_lock; /* and lock protecting it */ unsigned int i_mmap_writable;/* count VM_SHARED mappings */ struct prio_tree_root i_mmap; /* tree of private and shared mappings */ struct list_head i_mmap_nonlinear;/*list VM_NONLINEAR mappings */ struct mutex i_mmap_mutex; /* protect tree, count, list */ /* Protected by tree_lock together with the radix tree */ unsigned long nrpages; /* number of total pages */ pgoff_t writeback_index;/* writeback starts here */ const struct address_space_operations *a_ops; /* methods */ unsigned long flags; /* error bits/gfp mask */ struct backing_dev_info *backing_dev_info; /* device readahead, etc */ spinlock_t private_lock; /* for use by the address_space */ struct list_head private_list; /* ditto */ struct address_space *assoc_mapping; /* ditto */ } __attribute__((aligned(sizeof(long))));
inode構造体のポインタが格納されています。ページキャッシュはブロックデバイスにおけるinodeごとに存在するということですね。
※まとめ
- ページキャッシュはページ単位でファイルの内容が基数ツリーで管理されている
- ブロックデバイスのinode1つに対して基数ツリーが1つ存在する
- ページキャッシュミスはdo_generic_file_read()で起きている
- ブロックデバイスを扱うファイルシステムは多くの場合(少なくともread(2)時に)ページキャッシュを走査する実装になっている(これが「透過的に働く」の意味)
しかし、このdo_generic_file_read()はPageReadAheadやPageUptoDateなど気になるワードが満載で、もっと読みこんでいきたいところです。