くんすとの備忘録

プログラミングや環境設定の覚え書き。

【謎】本当にあったfindコマンドの怖い話【おもしろ現象】

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


要約

100万個のファイルに対して、find コマンドから始めて mv コマンドでファイル名を変更するワンライナーを実行すると、 mv コマンドが約158万回実行されました。

背景

これは、Software Design 2018年4月号

gihyo.jp

の「シェル芸人からの挑戦状」の記事執筆中に遭遇した不思議な現象です。1 初めはコラムに書こうとしていたのですが、結局原因がわからず、解説が書けなかったために紙面からは外すことにしました。 流石に結論が「わかりませんでした」で雑誌には載せられないので……。

現象自体は面白かったため、代わりに個人のブログの方に書くことで共有します。 (掲載の許可は頂いています)

環境

連載と同様、OSは Ubuntu 16.04 LTS、ファイルシステムは ext4 です。

再現手順

適当なディレクトリで、ファイルを100万個作成します。2

$ mkdir ./tmp
$ cd ./tmp
$ seq 1000000 | xargs touch

そして、以下のワンライナーを実行します。3

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

……結果を見る前に、ワンライナーの簡単な解説をしておきます。

ワンライナーの簡単な解説

これは、カレントディレクトリにある全てのファイルに対して、ファイル名の先頭に「a」を付与してリネームするワンライナーです。 例えば、「100」→「a100」という風にリネームします。

最初の

$ find . | sed 's;./;;g' | fgrep -v .
19
41
46
56
(以下略)

で、find の結果から邪魔な ./../ を除去し、さらに出力の頭に付く ./ を外します。 次の

$ awk '{print $1, "a"$1}' 

で、頭に「a」が付いていないファイル名と付いているファイル名の並びを生成し、最後の

$  xargs -n2 -I@ bash -c 'echo @; mv @'

では xargs で出力を2つずつ(つまり、先のawk で作ったペアをそのまま)取り出し、mv コマンドの引数を echo しつつ mv でリネームします。

つまり、最後の xargs では

$ bash -c 'echo 100 a100; mv 100 a100'

のようなコマンドを生成し実行します。

上記までの処理を time コマンドで時間計測しつつ、最後の nl何回mvを行ったかを数えます

実行結果

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

(中略)

1584210    999922 a999922
1584211    a999928 aa999928
1584212    aaa999931 aaaa999931
1584213    999943 a999943
1584214    a999947 aa999947
1584215    999958 a999958
1584216    999975 a999975
1584217    999986 a999986
1584218    999991 a999991

real    215m29.449s
user    3m20.460s
sys    11m36.450s

予想に反する結果が出ていると思います。

  • 用意したファイルは100万個なのに、なぜか mv1584218回 4実行されている
  • なぜか頭に「aaaa」の付いているファイル(1584212番目)が作成されている、つまり同じファイルが4回 mv されている

なんやねんこれは

もう少し詳しく

落ち着いて、ファイル数を数えてみます。

# ファイル数は増えてない
$ ls -U | wc -l
1000000

# mvが実行された回数を確認
$ ls -U | egrep ^[0-9] | wc -l
0
$ ls -U | egrep ^a[0-9] | wc -l
555997
$ ls -U | egrep ^aa[0-9] | wc -l
327519
$ ls -U | egrep ^aaa[0-9] | wc -l
95794
$ ls -U | egrep ^aaaa[0-9] | wc -l
17967
$ ls -U | egrep ^aaaaa[0-9] | wc -l
2429
$ ls -U | egrep ^aaaaaa[0-9] | wc -l
270
$ ls -U | egrep ^aaaaaaa[0-9] | wc -l
24
$ ls -U | egrep ^aaaaaaaa[0-9] | wc -l
0
$ ls -U | egrep ^aaaaaaaaa[0-9] | wc -l
0

# mvが7回実行されたファイルの一覧を見てみる
$ ls -U | egrep ^aaaaaaa[0-9]
aaaaaaa341160
aaaaaaa151953
aaaaaaa113691
aaaaaaa218712
aaaaaaa383
aaaaaaa335324
aaaaaaa378631
aaaaaaa416996
aaaaaaa611043
aaaaaaa130523
aaaaaaa188204
aaaaaaa398190
aaaaaaa66948
aaaaaaa330277
aaaaaaa298033
aaaaaaa390206
aaaaaaa406303
aaaaaaa250092
aaaaaaa1242
aaaaaaa175660
aaaaaaa192394
aaaaaaa71772
aaaaaaa367675
aaaaaaa553388

……ちょっとよくわかりませんね。

まとめ

わからん

一応 findコマンドのソースは読んだんですが。。。 ファイルを読んでいるところは fts_read (3) で、その中の奥の方では readdir(3) を使ってて、この子がスレッドセーフじゃないとかなんかそんな感じなんでしょうか……?

冒頭にも書いたんですが、ほんとわからないので誰かわかる方がいらっしゃったら教えて下さい。。。 流石に何かのバグではないと思うんですけども……

参考URL

3/21追記

原因分かりました。

www.kunst1080.net


  1. 問2の解説を担当している「中村」というのが私です

  2. ここでは現象を単純化するために、あえて並列化はしません。並列化しなくても現象が発現します。

  3. ここでは現象を単純化するために、あえて並列化はしません。並列化しなくても現象が発現します。

  4. 何度か試したところ、同じ数字のときもあれば、違う数字のときもありました

広告