negative dentry と tmpfs で negative dentry がキャッシュされない理由について調べた

kazeburo さんの一時ファイルとdentry cacheとメモリを読んでからしばらくファイルシステム周りを調べていたのでした。

先のエントリで /tmp のファイル作成/削除を繰り返して dentry キャッシュがもりもり溜まっていくのは negative dentry であることが理解できました。

negative dentry とは

negative dentry とは存在しない inode に対応する dentry です。 dentry キャッシュの役割は RAM より低速な HDD や SSD などの二次記憶装置からのディレクトリエントリの読み取りをメモリにキャッシュしておき高速化するためですが、negative dentry をキャッシュすることで存在しないディレクトリエントリの読み取りもキャッシュされます。

「存在しないのにキャッシュ？」がしばらくイミフだったのですが、DNS のネガティブキャッシュの動作に似ているなと思いました (存在しないレコード情報をキャッシュして問い合わせを減らし高速化)

negative dentry は存在しないパスを open(2) や stat(2) すると作成されます (追記: 存在しないパスを lookup すれば作成されると思うので、これら以外のシステムコールでも作られそうです) unlink(2)や rmdir(2) してリンクカウントが 0 になった inode の dentry も negative dentry に変わります。

negative dentry をひたすら増やす検証

negative dentry が溜まる様子は下記のワンライナーで検証できます

# 適当に存在しないパスを stat しまくる。 open にしてもいいです
 perl -e 'stat "/not-exists-$_" for 1..10000000'

存在しないパスへの stat(2) が ENOENT を返し、dentry キャッシュのサイズが増えていきます

ワンライナーを走らせながら slabtop を実行すると dentry のサイズが増えるのを観測できます

 Active / Total Objects (% used)    : 2472409 / 2477139 (99.8%)
 Active / Total Slabs (% used)      : 123870 / 123871 (100.0%)
 Active / Total Caches (% used)     : 88 / 181 (48.6%)
 Active / Total Size (% used)       : 469136.95K / 470052.57K (99.8%)
 Minimum / Average / Maximum Object : 0.02K / 0.19K / 4096.00K

  OBJS ACTIVE  USE OBJ SIZE  SLABS OBJ/SLAB CACHE SIZE NAME                   
2421040 2419219  99%    0.19K 121052       20    484208K dentry # めっちゃ増えてる

ところが slabtop では通常の dentry なのか negative dentry なのか判別できません ...

sar -w でも確認できます ( negative entry は dentunusd にカウントされます )

[vagrant@vagrant-centos65 ~]$ sar -v 1 10000
Linux 2.6.32-431.el6.x86_64 (vagrant-centos65.vagrantup.com)    02/07/14        _x86_64_        (1 CPU)

03:39:21    dentunusd   file-nr  inode-nr    pty-nr
03:39:22          498       640      5634        14
03:39:23          498       640      5634        14
03:39:24          498       640      5634        14
03:39:25       312053       640      5644        14  # ワンライナーを走らせたら盛り盛り増える
03:39:26       753031       640      5644        14
03:39:27      1124943       640      5644        14
03:39:28      1261772       640      5204        14
03:39:29      1283973       640      5204        14
03:39:30      1292790       640      5204        14
03:39:31      1317779       640      5204        14

negative dentry は何の役に立つのか?

/tmp に同じパス名でファイル作成や削除を繰り返すようなケースや、PerlやRubyのような言語のライブラリ/モジュールの探索 (例: Perl がモジュールを探すために @INC配列のディレクトリ群を走査する際、存在しないパスにも open(2) しまくって探している ) では、存在しないディレクトリエントリを毎回 HDD に問い合わせていると遅そうなので negative dentry のキャッシュが有効に作用していそうです。

一方で File::Temp の tmpfile() のようにランダムなパスを生成し同一パスの再利用を避けるケースと相性が悪いことは kazeburo さんのブログでも実証されています。

tmpfs で negative dentry がキャッシュされない理由

tmpfs では negative dentry はキャッシュされません。 unlink/rmdir すると dentry はすぐに破棄されます。ちょっと長いですが、実装を追って説明します ( ソースは 2.6.32 のバニラカーネルから )

tmpfs でのディレクトリエントリの探索は simple_lookup を実装としています。

static const struct inode_operations shmem_dir_inode_operations = {
#ifdef CONFIG_TMPFS
	.create		= shmem_create,
	.lookup		= simple_lookup,  // ディレクトリエントリの探索に用いるメソッド

simple_lookup で .d_delete( d_put で呼び出される) に simple_delete_entry を使うよう dentry_operations をセットしています

/*
 * Lookup the data. This is trivial - if the dentry didn't already
 * exist, we know it is negative.  Set d_op to delete negative dentries.
 */
struct dentry *simple_lookup(struct inode *dir, struct dentry *dentry, struct nameidata *nd)
{
        static const struct dentry_operations simple_dentry_operations = { 
                .d_delete = simple_delete_dentry,  // これ
        };  

        if (dentry->d_name.len > NAME_MAX)
                return ERR_PTR(-ENAMETOOLONG);
        dentry->d_op = &simple_dentry_operations;
        d_add(dentry, NULL);
        return NULL;
}

simple_delete_dentry は下記のように return 1 を返すだけです。コメントにお役立ち情報が書いています

/*
 * Retaining negative dentries for an in-memory filesystem just wastes
 * memory and lookup time: arrange for them to be deleted immediately.
 */
static int simple_delete_dentry(struct dentry *dentry)
{
	return 1;
}

コメントの中身は「インメモリなファイルシステムで negative dentry を保持してもメモリの無駄になるしハッシュ検索の時間も無駄になる。のですぐ消す」とのことです。なるほどー

dentry_operations の .d_delete は dput 内で呼び出されます。.d_delete が 1 を返すことで dentry は探索ハッシュテーブルからの削除 + LRUから削除され、dput された時点で破棄されるロジックになっています。

void dput(struct dentry *dentry)
{
	if (!dentry)
		return;

repeat:
	if (atomic_read(&dentry->d_count) == 1)
		might_sleep();
	if (!atomic_dec_and_lock(&dentry->d_count, &dcache_lock))
		return;

	spin_lock(&dentry->d_lock);
	if (atomic_read(&dentry->d_count)) {
		spin_unlock(&dentry->d_lock);
		spin_unlock(&dcache_lock);
		return;
	}

	/*
	 * AV: ->d_delete() is _NOT_ allowed to block now.
	 */
	if (dentry->d_op && dentry->d_op->d_delete) {
		if (dentry->d_op->d_delete(sentry))  // ここで 1を返す
			goto unhash_it;
	}
	/* Unreachable? Get rid of it */
 	if (d_unhashed(dentry))
		goto kill_it;
  	if (list_empty(&dentry->d_lru)) {
  		dentry->d_flags |= DCACHE_REFERENCED;
                // dentry キャッシュの追加
		dentry_lru_add(dentry);
  	}
 	spin_unlock(&dentry->d_lock);
	spin_unlock(&dcache_lock);
	return;

unhash_it:
        // dentryキャッシュのハッシュテーブルから削除
	__d_drop(dentry);
kill_it:
	/* if dentry was on the d_lru list delete it from there */
        // LRUからも削除
	dentry_lru_del(dentry);
	dentry = d_kill(dentry);
	if (dentry)
		goto repeat;
}