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; }
tmpfs では ファイルシステムのデータ(inode情報など) はメモリ(ページ)上に保持されていて高速に探索できます。二次記憶装置が無いので、存在しないディレクトリエントリを速く探すための negative dentry は無くてもいいということなのですね。
ext3 や ext4 などでは .d_delete は特に実装されておらず、negative dentry がキャッシュされるということになるようです
まとめ
- negative dentry の役割
- negative dentry の検証
- tmpfs で negative dentry が保持されない理由
をまとめました。 dentry そのものの解説は大変なので省きました。解説の確実な書籍等をあたってください
参考にした重量型書籍
Wrox
売り上げランキング: 86,651