shimada-kの日記

ソフトウェア・エンジニアのブログです

ページキャッシュのミスはどこで起きているのか

あけましておめでとうございます。これは「カーネル/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など気になるワードが満載で、もっと読みこんでいきたいところです。

*1:Linuxのページキャッシュ」 http://d.hatena.ne.jp/naoya/20070521/1179754203

*2:fuseの場合はfuse_file_aio_read()でラップされていました