【謎】本当にあったfindコマンドの怖い話【検証編】
3/21 22時頃: 質問編へのリンクを撤去し、タイトルを変更しました。(元のタイトルは「【謎】本当にあったfindコマンドの怖い話【解決編】」)
昨日のエントリについて、実験にしてはケースが雑だったので再検証していきます。
ちなみにモチベーションは「問題を回避したい」ではなく「この現象の原因を知りたい」です1。 よろしくお願いします。
現象からして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
パイプを外しても二重読みは発生するようです。 パイプ関係なかったっすね。2
ケース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万ファイルで実行 → 発現する
さてここで、こんな有益な情報が……
一度に読み込む量が定数だからでは。
— kuwa1 (@kuwashima) 2018年3月20日
# define FTS_MAX_READDIR_ENTRIES 100000
# define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
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
これはファイルを読み込む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時間くらいかかる3ので、これ以上探すのはやめておきます。
findコマンドを改造して検証
ここまでの検証によって、どうやら FTS_MAX_READDIR_ENTRIES
の辺りが怪しいっぽいということがわかりました。
本当にそうなのでしょうか?
findコマンドを改造して確認してみましょう。
findコマンドのソースは findutils というプロジェクトからダウンロードできます。 以前、個人的にfindutilsからソースをコピーしてビルドするdockerコンテナを作成していたので、それを利用します。
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 すると、処理中に変更を加えた場合は影響が発生することがありそう。厳密な閾値は不定っぽい。
情報をご提供いただいいたり、いっしょに検証してくださったみなさまには感謝です。 ありがとうございました。
次でラスト
【謎】本当にあったfindコマンドの怖い話【おもしろ現象】
3/21 22時頃: 質問編へのリンクを撤去し、タイトルを変更しました。(元のタイトルは「【謎】本当にあったfindコマンドの怖い話【未解決→解決済み】」)
要約
100万個のファイルに対して、find
コマンドから始めて mv
コマンドでファイル名を変更するワンライナーを実行すると、 mv
コマンドが約158万回実行されました。
背景
これは、Software Design 2018年4月号
の「シェル芸人からの挑戦状」の記事執筆中に遭遇した不思議な現象です。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万個なのに、なぜか
mv
が 1584218回 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
- ftsfind.c\find - findutils.git - GNU findutils
- gnulib/fts.c at master · coreutils/gnulib · GitHub
- linux/readdir.c at 8e9a2dba8686187d8c8179e5b86640e653963889 · torvalds/linux · GitHub
- glibc/opendir.c at 20003c49884422da7ffbc459cdeee768a6fee07b · git-mirror/glibc · GitHub
3/21追記
原因分かりました。
DockerでXサーバを動かしてGUIを直接表示する
最近、LinuxのノートPC上でDockerのサーバを建てて生活しています。 そのノートPC上では、プログラミング・ブラウジング・ツイッター・Slack・VTuber動画を見たりといった、あらゆることをしています。これらのことをするためにはGUI環境が必要で、そのためにXサーバを"直接"動かしています。
アーキテクチャはこんな感じです:
ここではこの環境の構築手順について解説していきます。
0. ホスト環境
Ubuntu Server 16.04.3 LTS (64bit)
$ cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=16.04 DISTRIB_CODENAME=xenial DISTRIB_DESCRIPTION="Ubuntu 16.04.3 LTS"
1. XサーバとXクライアントの入ったコンテナの作成
Dockerfile:
FROM ubuntu:16.04 MAINTAINER kunst1080 kontrapunkt1080@gmail.com RUN apt-get update \ && DEBIAN_FRONTEND=noninteractive apt-get upgrade -y \ && DEBIAN_FRONTEND=noninteractive apt-get install -y \ dbus \ dbus-x11 \ xorg \ xserver-xorg-legacy \ xinit \ xterm \ && rm -rf /var/lib/apt/lists/* RUN sed -i "s/allowed_users=console/allowed_users=anybody/;$ a needs_root_rights=yes" /etc/X11/Xwrapper.config ARG user=user ARG uid=1000 RUN useradd ${user} -u $uid -m -G adm,dialout,cdrom,sudo,audio,dip,video,plugdev,netdev -s /bin/bash CMD [ "/usr/bin/startx", "--", "vt7" ]
- 「xserver-xorg-legacy」は一般ユーザで
startx
するために必要です - sed で「/etc/X11/Xwrapper.config」を編集していますが、これも一般ユーザで
startx
するために必要な設定です
2. コンテナの起動方法
$ docker run --rm --privileged \ --shm-size=8gb \ -v /run/udev:/run/udev \ -v /run/dbus:/run/dbus \ -v /run/systemd:/run/systemd \ $IMAGE
--privileged
オプションは、GUIを表示するために必要(特権コンテナ)/run/udev
はマウスとキーボードを使用するために必要/run/dbus
と/run/systemd
は Systemd を使うために必要。Systemd を使用しなければこれらのオプションは不要--shm-size
オプションは共有メモリのサイズを指定します。Google Chrome などのアプリケーションを使用するときはこのオプションは必須。(初期値はたったの64MB)
3. 実際の設定
上記の1と2は解説用に必要なエッセンスを取り出した内容です。 私が実際に使っている設定は以下のリポジトリにあります。
- docker-x11-base: Xサーバ、Xクライアント、よく使う各種ツール・ライブラリ
- docker-x11-wm: docker-x11-base + window manager
- docker-desktop: docker-x11-wm + アプリケーションいろいろ(Googl ChromeとかVSCodeとか)
必要に応じてアップデートしていますが、だいたいこんな感じでやって〼
補足 (2018/03/19 追記)
「なぜあえてこんな変なことをやっているのか?」という問いについては以下のスライドで触れているので、併せてご覧ください。
www.slideshare.net
参考URL
- https://docs.docker.com/engine/reference/run/
- How to start Xorg-server inside plain chroot? - Super User
- Ubuntu 16.04 (EE) xf86OpenConsole: Cannot open virtual console 2 (Permission denied) · GitHub
- [SOLVED] Unable to startx as user / Newbie Corner / Arch Linux Forums
- Xorg - ArchWiki Rootless Xorg
- Arch Linux - News: xorg-server 1.16 is now available
※この記事の英語版
Hugo+GitLab Pages+ZeroSSLでブログを作りました
英語でブログ書きたいなーっていうことで作ってみした。中身はまだ空っぽですが。
技術スタック
- フレームワーク: Hugo (静的サイトジェネレータ)
- ホスティング・CI: GitLab Pages
- SSL: ZeroSSL
GitLabの権限設定
GitLabの権限設定をうまくやることで、公開しつつリポジトリの直接閲覧は禁止する、ということができました。
↑こんな感じに、すべての権限を「Only Project Menbers」にしておけば、ビルドのログは見えますが、ソースコードやその他の情報は見れなくなります。
(なってる筈…)
まとめ
と、こんな感じでなんとかできたので、しばらくはあっちの方に書くようにしていきたいなぁという所存。
参考URL
Go言語でZaimのCLIクライアントを作成しました。
リポジトリはこちらです。
ざっくりとした使い方
zaim auth
で認証を行い、 zaim money
で明細の全履歴をJSONで吐き出します。
インストールや使い方はREADMEをご参照ください。
※デフォルトでは財布のデータだけが出力されます。全部の口座のデータをまとめてとるときのパラメータがわかりません…
開発小話
初めてGoでコードを書きました。
なぜGoで書いたのか?
- 普段よく使わせていただいている sachaos/todoist や peco がGo製で、参考にできそうだった。
- いままでこういう小物系はPythonで書く感じだったのですが、型が欲しかったので……
使用したライブラリ
先に挙げた sachaos/todoist
さんを参考にして、以下のライブラリを利用しました。
- CLIフレームワーク: urfave/cli
- 設定ファイルの読み込み: spf13/viper
- OAuth認証: garyburd/go-oauth
所感
- Goにはナウい言語機能が無いと聞いていて引っかかりはあったのですが、「コンパイルできるVBScript」だと思うとしっくりきて書きやすくなりました。
- 「オブジェクト指向ではない」という情報をよく目にしており、カプセル化ができるのかどうか不安だったのですが、構造体にメソッドを生やすことができたので満足です。
細かいことを気にせずさくっと書くにはよさそう。 今までPythonで書いてたような小物系はGoで書くようにしていきたい。
「第33回シェル芸勉強会 大阪サテライト」レポート
01/27(土)に東京で行われた「jus共催 第33回めでたいシェル芸勉強会」について、今回も大阪でサテライトしました!
※レポート、ちょっと省力化してます
イベント情報
東京(本家)
大阪サテライト
福岡サテライト
イベントのようす
まとめ
問題・解答例・東京LT・togetterなどは本家の方にまとまっています。
jus共催 第33回めでたいシェル芸勉強会の報告 | 上田ブログ
大阪サテライトレポート
参加者
今回はフェンリルさんに会場をお願いしました。
OSCと被ってしまったため来られない方もいらっしゃり、今回の参加者は8名で、初めましての方は1名でした。
LTのようす
今回もYoutubeで配信していただけました! 録画はコチラ↓
MSR(@msr386) さん 「Amazon Dash Hack」
so(@3socha) さん 「Contributions Graph芸」
くんすと(@kunst1080) 「Dockerを使ったクライアントハイパーバイザー」
※作成中のため、今回はスライドの公開は無しです
小原 一哉(@KoharaKazuya) さん 「macOS 濁点問題にシェル芸で挑んだ話」
まとめ
お疲れ様でした! 次回もよろしくお願いします!
Java でa == 1 && a == 2 && a == 3やってみた
==
じゃなくて、equals
ならできる……
public class Main { public static void main(String[] args) { MyInt a = new MyInt(1); if (a.equals(1) && a.equals(2) && a.equals(3)) { System.out.println("true"); } else { System.out.println("false"); } } } class MyInt { int i; public MyInt(int i) { this.i = i; } @Override public boolean equals(Object i) { return (int)i == this.i++; } }
$ javac Main.java $ java Main true