※質問受付は終了しました。(3/22)

先にまとめ

  • リネームではinode番号は変わらないけどエントリの位置が変わることがある。
    • これが一番知りたかった情報。でも文章では理解したけど、検証コードはどう書けばいいかわからん…
  • readdirはアトミックじゃない。読み込み中にエントリ情報が変われば次の読み込みに影響する。
    • man にも「readdir()は非スレッドセーフです」って書いてある。
  • fts_readは実行時にreaddirの結果を10万件(ずつ？)キャッシュしていて、途中(たぶん10万件)まではエントリの変更の影響を受けないっぽい。途中からreaddirと同じことが起こる。
    • ソースコードの斜め読みと挙動を観察した限りそんな感じっぽい。厳密に裏取りしたいけど疲れた。
  • findコマンドは readdir ではなくそのラッパーの fts_read を使っているので、 fts_read と同じことが起こる。はず。

※3/25追記

リネームでエントリ位置が変わる現象について、ファイルシステムごとにどんな挙動を示すのか比較検証した記事をいただきました。ありがとうございます。

手元で簡単に検証できるような準備もされており、とてもわかりやすかったです。私も手を動かして追確認しました。

ディレクトリを getdents(2) しつつ rename(2) を繰り返す実験 - hibomaの日記

本編

昨日の記事 【謎】本当にあったfindコマンドの怖い話【おもしろ現象】 - くんすとの備忘録

と今日の記事 【謎】本当にあったfindコマンドの怖い話【検証編】 - くんすとの備忘録

のブコメを見て、詳しい人がたくさんいらっしゃるようだったので、せっかくなので質問コーナーやらせてください＞＜

全然詳しくないので教えてやってください＞＜

質問①

findはinode順に出力をする(予想)が、mvは同一ディスク内ではinode番号は変わらないと思っています。 なので、mvしたところでエントリには再度出てくるのは不思議…って思ってるんですが、どの辺の理解がおかしいですか？

もしかして: fts_readはinode順じゃなくてファイルシステム依存？ だとしたら何順？

A1-1: id:xbs2r さんからのブコメより

これを読めばわかる、っていうことなのでちゃんと読みます・・・(ｽﾐﾏｾﾝ

readdir() nonatomicity (Theodore Ts'o)

ざっくり読んだ感じ、記事中の質問は

readdir()が、別のプロセスからrename()されたファイルを拾ってくれない。リネーム前の名前もリネーム後の名前も降ってこない

で、こちらの例では find と -exec mv は別のプロセスなのでシチュエーションは同じ。

記事中の回答は

linked listで実装されているディレクトリでエントリが完全に密集しているとき(？)、その中のファイルをリネームするとディレクトリエントリの最後に追加される

readdir() がエントリをロックしてしまうと、readdir() を呼び出しまくるdos攻撃ができてしまうので、スレッドセーフにはあえてしていない。

ということなので、状態に寄っては readdir で同じファイルが複数回読まれるケースがある、ってことですね。。。

A1-2: あー (id:uva) さんからのコメント

ありがとうございます！

質問①について readdirが返すエントリの順序は不定のようですね

The order in which filenames are read by successive calls to readdir() depends on the filesystem implementation; it is unlikely that the names will be sorted in any fashion.

http://man7.org/linux/man-pages/man3/readdir.3.html

SOに似た質問ありました https://stackoverflow.com/questions/8977441/does-readdir-guarantee-an-order

inode順じゃなくて不定なんですね。(ファイルシステムに依存。SOにはディスクに格納されてる順、とかっていうのもありますね)

これならもし mv コマンドでinode番号が変われば、二重読み込みは発生しそうです。

inodeは関係ないですね。

A1-3: 自分: readdirの動きを検証

A1-1を確認するために、readdir(3) でファイルを読みつつ system(3) で mv コマンドを実行、mv前後の inode を確認するCのコードを雑に書きました。1

#include <stdio.h>
#include <stdlib.h>
#include <dirent.h>
#include <string.h>
#include <sys/stat.h>
unsigned long get_inode(char *name) {
unsigned long inode;
struct stat stat_buf;
char path[255];
snprintf(path, 255, "./%s", name);
if (stat(path, &stat_buf) == 0) {
inode = stat_buf.st_ino;
return inode;
} else {
perror("get_inode");
}
}
int do_move (char *src, unsigned long n) {
char cmd[255];
char dest[255];
unsigned long inode1;
unsigned long inode2;
inode1 = get_inode(src);
snprintf(dest, 255, "%sa", src);
snprintf(cmd, 255, "%s %s %s", "mv", src, dest);
system(cmd);
inode2 = get_inode(dest);
printf("%lu: %s (%lu) -> %s (%lu)\n", n, src, inode1, dest, inode2);
return 0;
}
int main(int argc, char**argv) {
char *path = "./";
char *s;
DIR *dir;
struct dirent *dent;
unsigned long n;
if (argc > 1) {
path = argv[1];
}
n = 1;
dir = opendir(path);
while ((dent = readdir(dir)) != NULL) {
s = dent->d_name;
if (strcmp(".", s) == 0 || strcmp("..", s) == 0) {
continue;
}
do_move (s, n);
n++;
}
closedir(dir);
return 0;
}
view raw mv-and-check-inode.c hosted with ❤ by GitHub
gist.github.com

ファイルを1500ファイル読み込んだところ、inode番号は変わらず、でも同じファイルが複数回読まれまたというのが見えました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

$ seq 1 1500 | xargs touch
$ ~/a.out | tee ~/a.txt
(略)
1635: 1 (393237) -> 1a (393237)
1636: 316 (393553) -> 316a (393553)
1637: 1163a (394400) -> 1163aa (394400)
1638: 1002 (394239) -> 1002a (394239)
$ wc -l ~/a.txt
1638 /home/hoge/a.txt

同じファイルが複数回読み込みされています。 inodeは関係ないですね。

A1-4: 自分: fts_read の動きを検証

readdirについては確認できましたが、findコマンドで実際に使われているのは readdir ではなく fts_read です。 なので、そちらについても確認していきます。

readdirの検証コードをftsで書き直します。

#include stdio.h
#include stdlib.h
#include fts.h
#include string.h
#include sys/stat.h
unsigned long get_inode(char *name) {
unsigned long inode;
struct stat stat_buf;
char path[255];
snprintf(path, 255, "./%s", name);
if (stat(path, &stat_buf) == 0) {
inode = stat_buf.st_ino;
return inode;
} else {
perror("get_inode");
}
}
int do_move (char *src, unsigned long n) {
char cmd[255];
char dest[255];
unsigned long inode1;
unsigned long inode2;
inode1 = get_inode(src);
snprintf(dest, 255, "%sa", src);
snprintf(cmd, 255, "%s %s %s", "mv", src, dest);
system(cmd);
inode2 = get_inode(dest);
printf("%lu: %s (%lu) -> %s (%lu)\n", n, src, inode1, dest, inode2);
return 0;
}
int main(int argc, char**argv) {
char* paths[] = { "./", NULL };
char *s;
FTS *fts;
FTSENT *ent;
unsigned long n;
if (argc > 1) {
paths[0] = argv[1];
}
n = 1;
fts = fts_open(paths, 0, NULL);
while ((ent = fts_read(fts)) != NULL) {
s = ent->fts_name;
if (strcmp("", s) == 0) {
continue;
}
do_move (s, n);
n++;
}
fts_close(fts);
return 0;
}
view raw mv-and-check-inode-fts.c hosted with ❤ by GitHub
gist.github.com

まずは10万ファイルの書き換えを実行してみます。

1
2
3
4
5
6
7
8
9

$ seq 1 100000 | xargs touch
$ ~/a.out.fts| tee ~/fts.100000.txt
(略)
99998: 98499 (491739) -> 98499a (491739)
99999: 56129 (449369) -> 56129a (449369)
100000: 52271 (445511) -> 52271a (445511)
$ wc -l ~/fts.100000.txt
100000 /root/fts.100000.txt

二重読みしてませんね。

次に20万ファイルで試してみます。

1
2
3
4
5
6
7
8
9

$ seq 1 200000 | xargs touch
$ ~/a.out.fts| tee ~/fts.200000.txt
(略)
199998: 56129 (449369) -> 56129a (449369)
199999: 52271 (445511) -> 52271a (445511)
200000: 171787 (565029) -> 171787a (565029)
$ wc -l  ~/fts.200000.txt
200000 /root/fts.200000.txt

これでも二重読みしませんね。(オイオイまじかよ……)

……fts.cの実装をソースからちゃんと理解してるわけでは全然なくって挙動を見てるだけなんだけど、やっぱり fts_read は途中までは保証されてるんじゃないかなぁ。

# 質問② 名前を変えただけでもう一度一覧に出てくるなら、対象となるファイル数を異常に増やしたり、処理中にsleepを噛ませたら無限にfindできると思うんですができるんでしょうか？

findの1件ずつsleepを挟むのは試してみたけど無理でした。(最初は無限にfindする企画でした) もしかして試してみたことのある方っています？

質問③

ファイル数が少ないときでもfindからmvしたときに二重読みしないのはたまたまなんでしょうか？

【解決編】で fts_read のタイミングで 最大100000件 までエントリをキャッシュしてるような風に見えたので、それ以下のエントリ数なら大丈夫だと思うんですが……

「不定だからやるな」って書いてあるのは理解したんですが、実際はどういう実装になっているんでしょうか。

A3-1: (id:siglite) さんからのブコメ

ありがとうございます。

“If a filename is renamed during a readdir() session of a directory, it is undefined where that neither, either, or both of the new and old filenames will be returned.” / 質問3: exec前に最大10万件先読みするから（最初の10万件は）execの影響がない…という感じ？

A1-1のリンクからの抜粋ですね。reddirのセッション中のディレクトリ内でリネームをすると、新しいファイル・古いファイル・両方のどれが読まれるか不定っていうことですね。 んで、findコマンド側で10万件キャッシュしてるから（最初の10万件は）execの影響がない…という。

前半は私がちゃんと理解できていなかったところで、後半は予想と同じですよね。 これで理解が合っていてほしいです。

その他いろいろ見ていて面白かったこと

FreeBSD の fts.c

freebsd/fts.c at 82974662ad9f9ece5f8374d2c898e83bd03aece9 · freebsd/freebsd · GitHub

FTS_MAX_READDIR_ENTRIES などというものはない。

gnulib の fts.c のコミットログ

fts: do not exhaust memory when processing million-entry directories · coreutils/gnulib@47cb657 · GitHub

FTS_MAX_READDIR_ENTRIES は7年前(2011/8/17)に追加されてる。

最後に

もういい加減飽きてきたのでここまで。濃い3日間だった。

無限 find 出来たよ！　って人がいればあとで教えて下さい。

  1. C言語を書いたのは人生で10回目くらいなのでひどいコードなのは見逃して頂きたく…↩