3/21 22時頃: 質問編へのリンクを撤去し、タイトルを変更しました。(元のタイトルは「【謎】本当にあったfindコマンドの怖い話【解決編】」)

昨日のエントリについて、実験にしてはケースが雑だったので再検証していきます。

ちなみにモチベーションは「問題を回避したい」ではなく「この現象の原因を知りたい」です¹。よろしくお願いします。

現象からしてfindコマンドが処理中に書き換えられたファイルを読み込んでいるのは明白です。

少しずつ仮設を立て見ていきましょう。まぁまぁお付き合いください。

検証ケース

ケース1: 10万ファイルで実行
ケース2: パイプを使わずfindコマンド一発にし、100万ファイルで実行
ケース3: ケース2を10万ファイルで実行
ケース4: ケース2を15万ファイルで実行

ケース1: 10万ファイルで実行 → 発現しない

昨日の記事は100万ファイルで検証していました。書いてはいなかったんですが、実は10万ファイル程度であれば謎現象が発現しないことは確認済みでした。とりあえずその様を御覧ください。

$  seq 100000 | xargs touch
$ find . | sed 's;./;;g' | fgrep -v . | awk '{print $1, "a"$1}' | xargs -n2 -I@ bash -c 'echo @;mv @' | nl

(中略)

99996    99996 a99996
99997    99997 a99997
99998    99998 a99998
99999    99999 a99999
100000    100000 a100000

パイプで繋いでいるからといって同じファイルを2回も読んだりしていません。直感的ですね。

ケース2: パイプを使わずfindコマンド一発にし、100万ファイルで実行 → 発現する

「間のパイプが怪しい」、オーケー、気持ちはわかります。それならfindコマンド一発にしてみましょう。

$ seq 1000000 | xargs touch
$ find . -type f -exec mv -v {} {}a \; | tee ~/case2.txt

(中略)

'./653325' -> './653325a'
'./653328a' -> './653328aa'
'./653345a' -> './653345aa'
'./653373aa' -> './653373aaa'
'./653392a' -> './653392aa'
'./653395aa' -> './653395aaa'
'./653416aa' -> './653416aaa'
'./653527aaa' -> './653527aaaa'

$ wc -l ~/case2.txt
1632595 /home/hoge/case2.txt

パイプを外しても二重読みは発生するようです。パイプ関係なかったっすね。²

ケース3: ケース2を10万ファイルで実行 → 発現しない

ケース1と同様に、パイプなし版でも10万ファイルでの挙動を確認してみます。

$ seq 100000 | xargs touch
$ find . -type f -exec mv -v {} {}a \; | tee ~/case3-100000.txt
(略)
$ wc -l ~/case3-100000.txt
100000 /home/hoge/case3-100000.txt

10万ファイルではこっちも大丈夫みたいです。

ケース4: ケース2を15万ファイルで実行 → 発現する

さてここで、こんな有益な情報が……

一度に読み込む量が定数だからでは。
# define FTS_MAX_READDIR_ENTRIES 100000
# define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
— kuwa1 (@kuwashima) 2018年3月20日

gnulib の fts.c のソースを確認したところ、確かに定数の宣言がありました。

/* If possible (see max_entries, below), read no more than this many directory
   entries at a time.  Without this limit (i.e., when using non-NULL
   fts_compar), processing a directory with 4,000,000 entries requires ~1GiB
   of memory, and handling 64M entries would require 16GiB of memory.  */
#ifndef FTS_MAX_READDIR_ENTRIES
# define FTS_MAX_READDIR_ENTRIES 100000
#endif


/* If there are more than this many entries in a directory,
   and the conditions mentioned below are satisfied, then sort
   the entries on inode number before any further processing.  */
#ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
# define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
#endif

https://github.com/coreutils/gnulib/blob/66ae2f356a594c83ad690d0dfadbc9c9a4cec5f4/lib/fts.c#L135-L148

これはファイルを読み込むpublicな関数 fts_read で使われている、ファイルを読み込む内部関数の fts_build の中で、一度に読み込むファイル数を決めいている定数(だと思います多分。私はマジでC言語ワカリマセン)です。 1回に 100000 エントリ読むっぽい感じでしょうか。大事を取って 150000 ファイルで処理して、二重読みが発生するかを検証してみます。

$ seq 150000 | xargs touch
$ find . -type f -exec mv -v {} {}a \; | tee ~/case4-150000.txt
(略)
$ wc -l ~/case4-150000.txt
182581 /home/hoge/case4-150000.txt

どうやら 100000 と 150000 の間くらいから二重読みが発生し出すみたいです。 1回試すのに1～2時間くらいかかる³ので、これ以上探すのはやめておきます。

findコマンドを改造して検証

ここまでの検証によって、どうやら FTS_MAX_READDIR_ENTRIES の辺りが怪しいっぽいということがわかりました。本当にそうなのでしょうか？ findコマンドを改造して確認してみましょう。

findコマンドのソースは findutils というプロジェクトからダウンロードできます。以前、個人的にfindutilsからソースをコピーしてビルドするdockerコンテナを作成していたので、それを利用します。

github.com

cloneし、FTS_MAX_READDIR_ENTRIES の値を10に書き換えてビルドします。

$ git clone --recursive https://github.com/kunst1080/docker-build-findutils
$ cd docker-build-findutils

# ソースの書き換え
$ sed -i".bak" 's/define FTS_MAX_READDIR_ENTRIES 100000/define FTS_MAX_READDIR_ENTRIES 10/g' findutils/gnulib/lib/fts.c

# ビルド
$ ./docker-build.sh
$ ./bootstrap.sh
$ ./configure.sh
$ ./make.sh
$ cp findutils/find/find ~/find10

はいできました。実行してみましょう。

1000ファイル → 発現しない

$ seq 1 1000 | xargs touch
$ ~/find10 . -type f -exec mv -v {} {}a \; | tee ~/new-find-1000.txt
$ wc -l ~/new-find-1000.txt 
1000 /home/hoge/new-find-1000.txt

1400ファイル → 発現する

$ seq 1 1400 | xargs touch
$ ~/find10 . -type f -exec mv -v {} {}a \; | tee ~/new-find-1400.txt
$ wc -l ~/new-find-1400.txt 
1432 /home/hoge/new-find-1400.txt

※1200、1300は発現するときとしないときがありました。

念の為、素の状態でビルドして1万ファイルで試してみる

$ git clone --recursive https://github.com/kunst1080/docker-build-findutils
$ cd docker-build-findutils

# ビルド
$ ./docker-build.sh
$ ./bootstrap.sh
$ ./configure.sh
$ ./make.sh
$ cp findutils/find/find ~/find-org

10万ファイルで実行

$ seq 1 100000 | xargs touch
$ ~/find-org . -type f -exec mv -v {} {}a \; | tee ~/new-find-org-100000.txt
$ wc -l ~/new-find-org-10000.txt
100000 /home/hoge/new-find-org-100000.txt

こっちは1万ファイルあっても大丈夫ですね。

まとめ

findコマンドについて、以下のことがわかりました。

find コマンドは、コンパイル時に使用した fts(3) に定義されている FTS_MAX_READDIR_ENTRIES の数だけエントリをキャッシュするっぽい。
FTS_MAX_READDIR_ENTRIES のデフォルト値は 100000 で、これ以下のファイル数であれば二重読み込みは発生しなさそう。
FTS_MAX_READDIR_ENTRIES 以上の数のファイルを対象に find すると、処理中に変更を加えた場合は影響が発生することがありそう。厳密な閾値は不定っぽい。

情報をご提供いただいいたり、いっしょに検証してくださったみなさまには感謝です。ありがとうございました。

次でラスト

www.kunst1080.net

回避策なんてくらでもあるので面白みはないでそ。↩
前回の記事のブコメでﾊﾟｲﾌﾟｶﾞｰって言っていた人たちはちゃんと検証してなかったんですね。まぁブコメ書くのにわざわざ検証なんてしないですよね。↩
実際は 500000、300000、200000 も試したのでもうおなかいっぱい。件数はいずれも概ね1.5倍前後になりました。↩

くんすとの備忘録

IT系技術メモ

【謎】本当にあったfindコマンドの怖い話【検証編】