ファイルやディレクトリの探し方まとめ

完成

gist.github.com

実践

  • /usr/で実践
  • リンクファイルがあると末尾に@がつくためFile not foundになったり、空白をファイル名に含む場合にうまくソートできなかったり、ファイルが無いディレクトリだとディレクトリを表示してしまったり、等を修正。
user:[~]$ for dir in $(find /usr/ -type d | grep -vxF .); do echo "$(ls -1 $dir | wc -l) $dir"; done | sort -rn | head -n 10
3295 /usr/share/app-install/desktop
2103 /usr/share/app-install/icons
1973 /usr/share/man/man3
1910 /usr/lib/x86_64-linux-gnu
1890 /usr/share/doc
1723 /usr/bin
1682 /usr/share/man/man1
1568 /usr/src/linux-headers-4.8.0-52-generic/include/config
1568 /usr/src/linux-headers-4.8.0-36-generic/include/config
1180 /usr/src/linux-headers-4.8.0-52/include/linux
user:[~]$ for dir in $(find /usr/ -type d | grep -vxF .); do stat "$dir/$(ls -S --file-type $dir | egrep -v "[/@]$" | head -n1)" --format="%s %n"; done | grep -v "/$" | sort -rn | head -n 10
103581280 /usr/lib/x86_64-linux-gnu/libOxideQtCore.so.0
75839136 /usr/lib/thunderbird/libxul.so
72949536 /usr/lib/firefox/libxul.so
58131384 /usr/lib/libreoffice/program/libmergedlo.so
39688256 /usr/lib/x86_64-linux-gnu/webkit2gtk-4.0/WebKitPluginProcess2
26068668 /usr/share/tegaki/models/zinnia/handwriting-ja.model
23701384 /usr/lib/mozc/mozc_server
22427896 /usr/lib/gcc/x86_64-linux-gnu/5/cc1plus
19319840 /usr/share/fonts/opentype/noto/NotoSansCJK-Bold.ttc
18597793 /usr/share/mythes/th_en_US_v2.dat
user:[~]$ for dir in $(find /usr/ -type d | grep -vxF .); do stat "$dir/$(ls -t --file-type $dir | egrep -v "[/@]$" | head -n1)" --format="%Y %n"; done | grep -v "/$" | sort -rn | head -n 10
1495553004 /usr/lib/python3.5/xml/dom/__pycache__/NodeFilter.cpython-35.pyc
1495553004 /usr/lib/python3.5/json/__pycache__/encoder.cpython-35.pyc
1495553004 /usr/lib/python3.5/email/mime/__pycache__/nonmultipart.cpython-35.pyc
1495542287 /usr/lib/python2.7/dist-packages/pygtkcompat/pygtkcompat.pyc
1495542287 /usr/lib/python2.7/dist-packages/gtweak/tweaks/tweak_group_interface.pyc
1495542287 /usr/lib/python2.7/dist-packages/gtweak/__init__.pyc
1495542287 /usr/lib/python2.7/dist-packages/gi/repository/__init__.pyc
1495542287 /usr/lib/python2.7/dist-packages/gi/overrides/GIMarshallingTests.pyc
1495542287 /usr/lib/python2.7/dist-packages/gi/_gobject/__init__.pyc
1495542287 /usr/lib/python2.7/dist-packages/gi/_error.pyc
user:[~]$ du -sh /usr/
3.4G    /usr/
user:[~]$ du -s --inode /usr/
200085 /usr/
user:[~]$ find /usr/ -type f | wc -l
116407
user:[~]$ find /usr/ -type d | wc -l
20743
user:[~]$ find /usr/ -type l | wc -l
62938
user:[~]$ find /usr/ -mmin -1440 | wc -l
18

練習

[~/Work]$ for dir in $(seq 1 100);do mkdir dir_$dir; cd dir_$dir; for file in $(seq 1 100);do touch file_$file; done; for sub in $(seq 1 10); do mkdir sub_$sub; cd sub_$sub; for file in $(seq 1 100); do touch sub_file_$file; done; cd ..; done; cd ..; done
[~/Work]$ touch dir_100/file_101
[~/Work]$ cat dir_100/file_101 
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
[~/Work]$ for dir in $(find . -type d | grep -vxF .); do echo "$dir $(ls -1 $dir | wc -l)"; done | sort -r -k 2 | head -n 10
./dir_100 111
./dir_99 110
./dir_98 110
./dir_97 110
./dir_96 110
./dir_95 110
./dir_94 110
./dir_93 110
./dir_92 110
./dir_91 110
  • 修正した時間が直近のファイルTop10
[~/Work]$ for dir in $(find . -type d | grep -vxF .); do echo "$(stat $dir/$(ls -Ft $dir | grep -v "/$" | head -n1) --format='%n %Y')"; done | sort -r -k 2 | head -n 10
./dir_100/file_101 1495551073
./dir_100/sub_10/sub_file_100 1495551019
./dir_100/sub_9/sub_file_100 1495551018
./dir_100/sub_8/sub_file_100 1495551018
./dir_100/sub_7/sub_file_100 1495551017
./dir_100/sub_6/sub_file_100 1495551016
./dir_100/sub_5/sub_file_100 1495551016
./dir_100/sub_4/sub_file_100 1495551015
./dir_100/sub_3/sub_file_100 1495551014
./dir_100/sub_2/sub_file_100 1495551014
  • inodeの数
[~/Work]$ du -s --inode .
111102  .
  • ファイルサイズの合計
[~/Work]$ du -sh .
4.4M    .
  • サイズが大きいファイルTop10
[~/Work]$ for dir in $(find . -type d | grep -vxF .); do echo "$(stat $dir/$(ls -Ft $dir | grep -v "/$" | head -n1) --format='%n %s')"; done | sort -r -k 2 | head -n 10
./dir_100/file_101 121
./dir_99/sub_9/sub_file_100 0
./dir_99/sub_8/sub_file_100 0
./dir_99/sub_7/sub_file_100 0
./dir_99/sub_6/sub_file_100 0
./dir_99/sub_5/sub_file_100 0
./dir_99/sub_4/sub_file_100 0
./dir_99/sub_3/sub_file_100 0
./dir_99/sub_2/sub_file_100 0
./dir_99/sub_10/sub_file_100 0
  • ファイル数
[~/Work]$ find . -type f | wc -l
110001
[~/Work]$ find . -type d | wc -l
1101
[~/Work]$ find . -mmin -10
./dir_100
./dir_100/file_101

Binary Searchと分割統治によるコード最適化

Binary Searchは強力でソート済みでない配列に対して適用することも可能である。それどころか、対象が離散的な値である必要すら無い。 分割統治(Divide-and-conquer)はそれに良く似た手法で、対象を再帰的に半分にしてく手法である。

今回はランダムに数値が並んだ配列の中で、それらの数値の取りうる範囲が指定されており、その範囲の中で一つだけ数値が欠けていて、その欠けている数値を探し出す問題を考える。例えば範囲が1〜10で配列の長さは9であり、配列の中の数値に重複は無い場合である。

直感的に考えると配列をソートして一つずつ順に数値を見ていけば良い。数値が欠けていればインデックスとの対応が合わないはずだ。 しかしこれは最速でもO(Nlog(N))かかることになる。もう少し詳しく言えば、ソートしてから一つずつ配列を見ていくので、最悪の場合はO(Nlog(N)+N)になるだろう。

このような問題は分割統治を使ってもっと速くできる。Binary Searchのようにインデックスをlow,highとして扱うような使い方では解けないため、ここは配列のサイズを1/2ずつに分割していく方法を組み合わせる。上記の例で言うと、low=1, high=10, mid=5として初期設定し、midより大きい配列、小さい配列、に分ける。欠けている場合は、配列が期待するサイズよりも小さいはずなので、lowかhighにmidを設定し、そちらの配列を再帰的に検査していく。

ここまで考えることができればO(Nlog(N))よりも速くできることが分かるだろう。しかし、ここに辿り着く前にこれがO(Nlog(N))よりも速くなる、ということに気付くのが難しい。実際には、midを元にサイズNの配列を作成するための走査が必要になるためO(N)になる。Binary Searchを用いていることを実感したいならばもう少し詳しく考えて、N+N/2+N/4+...となるので初項=N、公比=1/2、の等比数列の和を求めると、N*(1-(1/2)^N)/1-(1/2)、となり、Nが十分大きければ(1/2)^N≒0となるため、O(N)が導ける。

この問題の解法は、例えば、k個の欠けている数値のうちの一つを探し出す、とか、k個の重複している数値のうちの一つを探し出すなどにも適用できる。 コードは以下。配列をスクランブルした後、最後の要素を削除(配列のサイズをマイナス1)することによって、欠けている配列を作り出している。

Find a lost number in O(N) better than O(NlogN) by sort. · GitHub

MBPでの実行結果。

$ for i in `seq 1 5`; do echo $i; ./find_a_lost_number 100000000; done
1
78221769==78221769:OK
func_O_N : 1.27 sec.
78221769==78221769:OK
func_O_NlogN : 20.13 sec.
2
12264665==12264665:OK
func_O_N : 1.21 sec.
12264665==12264665:OK
func_O_NlogN : 20.09 sec.
3
78228998==78228998:OK
func_O_N : 1.23 sec.
78228998==78228998:OK
func_O_NlogN : 20.05 sec.
4
44908476==44908476:OK
func_O_N : 1.32 sec.
44908476==44908476:OK
func_O_NlogN : 20.35 sec.
5
85940350==85940350:OK
func_O_N : 1.24 sec.
85940350==85940350:OK
func_O_NlogN : 20.17 sec.
$

二つ目の問題は、配列の中で合計値が最大となる部分配列を発見する。配列の要素は整数なので、負の値も存在する。

これには、計算量がO(N3), O(N2), O(NlogN), O(N), となる解法が存在するが、分割統治を利用した解法はO(NlogN)となる。1/2に分割しながら中央の値から左と右の部分配列の合計を計算し、最大となる部分配列を見つける。O(N)の解法の基礎となるアイデアは、配列の最初の要素から合計していくが、合計が負の値になったときはその次の要素を部分配列の最初の要素とする。そうやって部分配列を細切れにしながら合計の最大値を更新していくと、O(N)で、つまり一つのループで計算できる。

Find maximum sum of sub array in O(N^3), O(N^2), O(NlogN), O(N). · GitHub

出力としては、部分配列の最初のインデックス-[合計値]-部分配列の最後のインデックスとしている。

$ ./max_sub_array 3000
1653-[62030]-1900
func_O_N3 : 12.63 sec.
1653-[62030]-1900
func_O_N2 : 0.01 sec.
1653-[62030]-1900
func_O_NlogN : 0.00 sec.
1653-[62030]-1900
func_O_N : 0.00 sec.

$ ./max_sub_array 30000
2795-[4884646]-29986
func_O_N2 : 1.34 sec.
2795-[4884646]-29986
func_O_NlogN : 0.00 sec.
2795-[4884646]-29986
func_O_N : 0.00 sec.

$ ./max_sub_array 30000000
25697428-[46557400133]-28003047
func_O_NlogN : 4.39 sec.
25697428-[46557400133]-28003047
func_O_N : 0.20 sec.

tracerouteのベストプラクティス

ファイヤウォールの設定が厳しいネットワークや、ロードバランサーが動作するネットワーク、使用するパケットのプロトコルによる違い、等を考えて最も経路発見しやすい方法を考える。

ファイヤウォールの設定が厳しいネットワーク

ファイヤウォールの設定が厳しい場合、pingすらインターネット上のサーバに通らないことがある。tracerouteも同様で、デフォルトの設定では通らないことが多いが、ファイヤウォールが必ずといっていいほど通しているポートを使えば良い。TCPではHTTPの80番ポート、UDPではDNSの53番ポート、が最も良く知られたポートの内の一つだろう。実際、tracerouteのデフォルト設定ではデフォルトゲートウェイまでしか経路発見できないが、UDPの53番ポートを使うとかなり先まで経路発見できることがある。

ロードバランサーが動作するネットワーク

ECMPによってロードバランスしているネットワーク(インターネット)では、パケットを投げる度に経路が変わってしまう。ただし、ロードバランスには大きく二つの方式があって、インターフェースをフローで振り分けるか、パケットで振り分けるか、の違いがある。フローは5 tuples (IP/Port Dest/Src Protocol) によってインターフェースを振り分ける方式で、IP/UDP/TCPのヘッダで決まる5 tuplesを固定すれば、ロードバランスによる経路の違いは出ないので安定した経路発見が行えるはずだ。

ただし5 tuplesを固定するために、tracerouteがどのように経路発見を行っているのかを確認しておく必要がある。Linux版のtracerouteコマンドはデフォルトはUDPパケットによる経路発見を行う。つまり、UDPパケットのIPヘッダのTTLを一つずつ増やしていくやり方だ。また、受け取ったTime ExceededのICMPパケットが、どのUDPパケットに対応するのかを判断できる必要がある。大きく遅延したパケットを受信したり、他のアプリケーションが送信したパケットに対するTime Exceededパケットと区別する必要があるし、Linuxのtracerouteのデフォルト動作は以下の通り同時に複数のパケットを投げる。

       -N squeries, --sim-queries=squeries
              Specifies the number of probe packets sent out simultaneously.
              Sending several probes concurrently can  speed  up  traceroute
              considerably. The default value is 16.
              Note that some routers and hosts can use ICMP rate throttling.
              In such a situation specifying too large number  can  lead  to
              loss of some responses.

Time ExceededのICMPパケットはそのデータ部に、元のパケットのIPヘッダとペイロードの最初の8バイトを含めるので、元のUDPパケットのヘッダに存在するポート番号を識別できるため、tracerouteはこれを生かしてUDPの宛先ポート番号を一つずつ増やしながらUDPパケットを生成する。

http://pages.cs.wisc.edu/~agember/cs640/s15/assign3/images/image00.png

Internet Control Message Protocol - Wikipedia

ここで、フローベースのロードバランスに対応しようとすると問題があることが分かる。5 tuplesが変わってしまうとロードバランスの影響を受けるからだ。これに対応したのが Paris Traceroute で、UDPパケットヘッダの宛先ポート番号ではなくチェックサムを使って対応を取る。まるでビットコインのように、UDPパケットのペイロードを用いて任意のチェックサムの値を作り出す。UDPパケットヘッダのチェックサムは最初の8バイトに含まれるので、これもTime ExceededのICMPパケットに含まれる。単純にUDPパケットのペイロードにシーケンス番号を書けないのもこれが理由だ。

http://paris-traceroute.net/images/traceroute_load_balancers.gif

Paris Traceroute

ただ、tracerouteにもこれと同等と思われるオプションが実装されているため、UDPパケットを使いつつ宛先や送信元のポート番号を任意の値に固定できる。例えば、-Uオプションで宛先ポート番号を53に固定する。これは、DNSで使われるポート番号であり、最も通りやすい(経路途中でファイヤウォールにフィルタで破棄される可能性が少ない)ポートの一つだ。また--sport=オプションで、送信元ポートを固定することもできる。

両者の違いはChecksumの使い方にあるようだ。tracerouteのパケットをtcpdump -vvで見てみると[bad udp cksum]と表示されるのが分かる。宛先ポートや送信元ポートを変更してもChecksumの値を変えておらず固定値にしているようだ。一方、paris-tracerouteの方は[udp sum ok]と表示されるため、ヘッダに併せてChecksumを正確に作り直していることが分かる。これが、tracerouteの動作の結果としてどう影響するかは分からないが、全く同じ挙動ではないという点は気をつけておいた方がいいだろう。また、paris-tracerouteは完全に全ての経路を把握してから標準出力に出力するので、複数経路を何らかのアルゴリズムで適当な経路を選択しているのかもしれない*1

なお、Windows版のtracertはICMPパケットを使った経路発見を行う。LinuxのtracerouteでもICMPやTCPを扱えるが、これも細かい仕様は両者で異なると思われるので、同じICMPパケットでも発見できる経路に違いが出るかもしれない。

また、-Aで各ホップの所属するAS番号を取得することができるので活用した方が良い。これは内部でwhoisを使っており*2whoisはポート45番*3を用いてwhoisサーバとやり取りするので、イントラネットがポート45番をフィルタしていると使うことができず、AS番号の部分が[!!]という表示になってしまう。

使用するパケットのプロトコルによる違い

上記でほとんど説明したが、総括するとtracerouteにはICMP/UDP/TCPの違いがあって、ネットワークによってはそれぞれで結果が異なることが予想できるのでいくつか試してみるべきだろう。あと、最後にpingで宛先とのRTTを確認して、どの程度まで経路発見が出来たのかを把握しておくのが良い。

実際にやってみた結果を考慮する*4と以下のようになった。ネットワークによって結果は変わってくるので、これが唯一の解答にはならないとは思う。

  • ファイヤウォールが厳しい場合はWell-Knownなポートを使ってみる
  • ロードバランスによる影響を抑えたい場合は宛先と送信元のポートを固定する
  • ウェブサーバに対してTCP80番を使うとCDNの影響により2〜3ホップで届いてしまうことがある(実際に知りたい経路ではない可能性がある)
  • 宛先ポートと送信元ポートを固定すると結果が悪くなる場合もあったため、デフォルト設定も含めていくつかのオプションを試すべき

*1:そのあたりは論文参照のこと https://paris-traceroute.net/images/e2emon2007.pdf

*2:実際にwhoisコマンドをインストールする必要は無かった

*3:straceで見た限りUDP/TCP両方を使っているようだ

*4:実際に発見した経路は出さないことにする

Git for WindowsにおけるRubyのputsの挙動

Git for Windows (Git bash)でrubyのプログラムを走らせているときプログラムが停止しているような挙動に遭遇した。デバッグしてみると、停止している箇所はユーザからの入力を受け付ける部分であったが、入力待ちで停止しているのではなく、putsでユーザに入力を促すメッセージを表示している部分であった。putsデバッグメッセージを入れると表示せずにそこで停止してしまうことに気づいて、pprintを代用してみたところ、pだと正常にメッセージ表示される。putsの後にpを持ってくると、putsも表示される。これはどうもputsの場合は非同期にバッファに蓄えられており、pの場合はバッファを含めて同期的に全て標準出力に出力される(flushされる)、という挙動になっているらしい。そのため、$stdout.sync = trueをプログラムの先頭に書いておくことで、putsでも正常にメッセージ表示されるようになった。

なお、Cygwinコマンドプロンプトから実行するとこのようなputsの問題は起こらなかった。

MinGWでどうなるかは試していませんが、こういった症状がある記事が見当たらなかったし、なかなかおもしろい挙動だったのでメモ。まあ、Git bashではgitコマンドだけを使うことにしておいた方が良い、ということなのかも。

環境は、Windows 7 32bit / Ruby 2.2 / Git for windows

git-for-windows.github.io

仮想マシンのスタックとネットワークI/Oについて

仮想化コンセプト

  • 仮想マシンモニタ=VMM(Virtual Machine Monitor)は、自身の子プロセスとして仮想マシンを実行し、ユーザモードでは実行できない命令を仮想マシンが発行したときは、CPUで例外が発生するため、それをVMMが補足(trap)*1して、仮想マシンが実行すべき命令をVMMが実行すれば良い(trap-and-emulate)。
  • そのためには、VMMは特権モードで実行し、仮想マシンを特権モードより低いモード(かつ、ユーザモードより高いモード)で実行すれば良い。

x86における仮想化

  • リングのコンセプトには0〜3の4段階があり、リング0はハードウェアにアクセスする特権命令を実行する。つまり、カーネルモードはリング0で実行し、ユーザモードはリング3で実行する。なお、1,2は使用しない。
  • x86では、「非特権命令であるためリング0以外で実行してもトラップは発生しないが、リングの状態やハードウェアリソースの状態に依存する命令」=センシティブ命令、が存在するため、仮想化コンセプト通りにVMMを実装してもうまくいかない。

http://image.gihyo.co.jp/assets/images/dev/serial/01/vm_work/0004/004.jpg

  • そこで、バイナリトランスレーションという技術により、VMMが仮想マシンの実行するプログラムを解析して、センシティブ命令を別の命令に置き換えるという手法が確立されたが、実装の難易度が高く、VMMの選択肢が限られていた。

Intel VT-x/AMD-Vの登場

  • Intel VT-xはハードウェア(CPU)による仮想化の実現支援機構で、全ての特権命令やセンシティブ命令をトラップできるようになった

  • リング0の状態にVM root modeとVM non-root modeの区別を提供したことで、ゲストOSをリング0(non-root mode)で動かしてもVMMがそれより上位(root mode)から制御できる

  • ゲストOSが特権命令を発行するとnon-root modeからroot modeへの移行(VMExit)により、制御がVMMに移されハードウェアへのアクセスなどが実行される

  • Intel VT-x

http://image.gihyo.co.jp/assets/images/dev/serial/01/vm_work/0005/002.jpg

http://image.gihyo.co.jp/assets/images/dev/serial/01/vm_work/0005/003.jpg

  • 性能については、バイナリトランスレーションを採用しているVMwareの方が、CPUの仮想化支援機構を利用したKVMよりも、当初は速かった。VMEntryやVMExitによるモードの移行処理のオーバーヘッドが大きかったためである。CPUの技術向上によりこれらの処理に必要なクロック数が下がり、この差は解消されていった。

VMCS(Intel)/VMCB(AMD)

  • 仮想マシンが扱う各種レジスタなどの情報を保存しておくための物理メモリ上の領域。CPUによって、VMEntryの際にはVMCSから情報を復帰し、VMExitの際にはVMCSへ情報を退避する。VMCSに保存されない情報については、VMMによって復帰・退避が行われる。

http://image.slidesharecdn.com/2nd-intelvt-091006192819-phpapp01/95/bitvisor-intelvt-53-728.jpg?cb=1254857383

EPT (Extended Page Table)

  • ゲストOSは各プロセス毎にページテーブルを持つが、VMMはゲストに物理メモリにアクセスさせるために、ゲストの仮想アドレスからホストの物理アドレスへの変換表をSPT (Shadow Page Table)として管理する。
  • このソフトウェア的な管理をなくすために、仮想マシンごとのゲストの物理アドレスからホストの物理アドレスへの変換の部分は別途VMMが管理する。これがEPT。
  • VMMによるSPTを用いたソフトウェア的な管理をなくし、ゲストOSのページテーブル変更=SPTの更新時のVMExit/VMEntryのオーバーヘッドをなくすことができる。

VPID (Virtual Processor Identifier)

  • TLB(Translation Lookahead Buffer)は、直前に利用したプロセスのページテーブルをCPUキャッシュに載せて再利用することで、メモリアクセスを減らして高速化する。
  • 仮想マシンのTLBと、VMMのTLBは異なるため、VMEntry-VMExitの際に(つまり仮想マシンのプロセスがシステムコールを呼んで特権命令を実行する度に)、TLBがフラッシュされてしまい、TLBの本来の意義が果たせなくなってしまう。
  • そこで、TLBをそれぞれの仮想マシンとVMMで使い分けてCPUキャッシュに保持するために、VPIDを導入しそれぞれのTLBを識別して管理できるようにした。

完全仮想化

  • ゲストOSを変更しない完全仮想化であらゆるOSをゲストとして実現する。KVMではQemuによるエミュレーションを利用するが、CPUのエミュレーションは非常に遅いので、Intel-VT/AMD-Vの仮想化支援機構が無いと実用性が無い。
  • KVMではHypervisorはLinuxホスト上でqemu-kvmと呼ばれる一つのプロセスとして動作し、kvm.koというカーネルモジュールを介して特権命令を実行する。

準仮想化

  • ゲストOSを変更する準仮想化で仮想化を実現するが、オープンソースのOSしかゲストとして採用できない。仮想マシンをリング1で実行することで、CPUの仮想化支援機構を必要としない方式。
  • Xen/VMware ESXではHypervisorは物理ハードウェア上で直接動作する。

Nested VMM

  • CPUの仮想化支援機構を、ゲスト上のVMMにも提供する機能。KVM on KVM などが可能になる。仮想マシン/proc/cpuinfovmxsmxといった単語が見える場合は、Nested VMMが有効。

I/Oの仮想化

Intel VT-d

SR-IOV

  • PCI Expressバイスが排他的な仮想デバイスの機能(VF)を提供することで、IOMMUを有効にしながらも仮想マシン間で物理デバイスの共有が可能になった。
  • NICバイスの場合、仮想スイッチによるCPUを用いたホスト-ゲスト間のトラヒック転送を担う必要がなくなり、単一の物理デバイスを共有しながらも物理NICのネイティブな処理能力を発揮することができる。

仮想デバイスによるNICエミュレーション

VMMが、エミュレートした仮想デバイス仮想マシンに対して提供し、仮想マシンにはその仮想デバイスに対するデバイスドライバがインストールされる。それぞれ、バックエンド、フロントエンド、と呼ばれる。

仮想化環境におけるパケットフォワーディング

  • e1000

https://image.slidesharecdn.com/e4-bb-ae-e6-83-b3-e5-8c-96-e7-92-b0-e5-a2-83-e3-81-ab-e3-81-8a-e3-81-91-e3-82-8b-20-e3-83-91-e3-82-b1-e3-83-83-e3-83-88-e3-83-95-e3-82-a9-e3-83-af-e3-83-bc-e3-83-87-e3-82-a3-e3-83-b3-e3-82-b0-130603141515-phpapp01/95/-12-638.jpg?cb=1370268967

  • virtio

https://image.slidesharecdn.com/e4-bb-ae-e6-83-b3-e5-8c-96-e7-92-b0-e5-a2-83-e3-81-ab-e3-81-8a-e3-81-91-e3-82-8b-20-e3-83-91-e3-82-b1-e3-83-83-e3-83-88-e3-83-95-e3-82-a9-e3-83-af-e3-83-bc-e3-83-87-e3-82-a3-e3-83-b3-e3-82-b0-130603141515-phpapp01/95/-26-638.jpg?cb=1370268967

  • vhost-net

https://image.slidesharecdn.com/e4-bb-ae-e6-83-b3-e5-8c-96-e7-92-b0-e5-a2-83-e3-81-ab-e3-81-8a-e3-81-91-e3-82-8b-20-e3-83-91-e3-82-b1-e3-83-83-e3-83-88-e3-83-95-e3-82-a9-e3-83-af-e3-83-bc-e3-83-87-e3-82-a3-e3-83-b3-e3-82-b0-130603141515-phpapp01/95/-27-638.jpg?cb=1370268967

Thanks to

www.slideshare.net

ネットワークI/O

  • パケット受信処理

http://i0.wp.com/opensourceforu.com/wp-content/uploads/2016/08/Figure-1-Data-receiving-process.jpg

  • NAPI - ハードウェア割り込みが多くて性能が上がらない状況を改善するため、ハードウェア割り込みが発生した際にいったん割り込みを禁止して、カーネルが物理デバイスのメモリをポーリングする、という仕組みを提供するLinux Kernel API。ポーリングはプロセススケジューリングによって実行されるため、割り込み禁止からポーリングの間にNICに到着したパケットをまとめてソフトウェア処理できるため効率が良い。

http://www.coderplay.org/images/2015-12-05-1/nic-device-driver-process.png

  • 受信パケットを別のCPUで処理すると、プロセススケジューリングに依存してパケット処理の順序が変わってしまうことでreorderingが発生する頻度が多くなることを避けるため、受信パケットのソフトウェア上の処理は特定のCPUに集中してしまう。

  • RSS (Receive Side Scaling) - NICに複数の受信パケットキューを持たせ、パケットの5 tuplesをハッシュとしてキューに振り分け、それぞれのキューを別のCPUに割り当てて処理する制御を実現したもの。5 tuplesで一意にCPUを振り分けることで、上記のようなreorderingの頻発が起こるのを防ぐ。

  • RFS (Receive Flow Steering) - RSSの仕組みをソフトウェアとして実現し、さらにアプリケーションプロセスがユーザ空間で最後に処理したCPUを記憶して、動的にそのCPUをキューに割り当てる。それによってCPUのキャッシュヒットを高める。NICからのDMAでパケット(フレーム)をリングバッファに取り込んだ後にプロトコルスタックの処理をCPUで行う際のキャッシュを活用することによる性能向上が見込める。

  • netmap

    • ユーザアプリケーションが直接参照可能なメモリ領域とNICバイスmmapによりマッピング
    • 上記のメモリ領域は再利用するためにリングメモリとして事前に確保
    • systemcallあたりの処理パケット数を増やすことによりコストを下げる(amortize)
    • 共有メモリ領域にメモリを確保することによりプロセス間(インターフェース間)のフォワーディングはzero-copyを実現

blog.yuuk.io

www.slideshare.net

http://www.coderplay.org/networkingdev/Linux-Kernel-Networking-Packet-Receiving.htmlwww.coderplay.org

Linuxデバイスドライバ 第3版

Linuxデバイスドライバ 第3版

Intel DPDK

  • パケット処理におけるLinuxカーネルの処理がオーバーヘッドとなりつつあり、さらにSR-IOVなどNICと(ユーザスペースで動作する)仮想マシンを直接繋げる技術も登場している。
  • Intel DPDKは、Linuxカーネルをバイパスし、ユーザスペースでデバイスドライバを動かして、直接パケットをアプリケーションに届けるようなプログラムを実装するためのSDKを提供する。
  • PMD(Poll Mode Driver)と呼ばれる特別なデバイスドライバを特定のCPUで動かしてNICを監視し、パケットをユーザスペースのアプリケーションに届ける。また、UIO/VFIOといったユーザスペースでデバイスドライバを動かすためのカーネルモジュールを使用する。
  • Hugepageによって1ページあたりのサイズを大きくすることで1ページにバッファを収めることができるため、仮想メモリ空間で連続的なメモリを実現する必要なく、ユーザ空間へのDMAが実現できる。
  • マルチコアを活用しており、フロー単位でCPUを割り当てるrun-to-completionモードと、処理単位でCPUを割り当てるpipelineモードが選択できる。

http://www.bosco-tech.com/file/160311_icm2015-muramatsu.pdf

f:id:nishidy:20161112001534p:plain:w500

blog.slankdev.net

*1:例外発生時に呼ばれるコールバック関数をオーバーライトしてる?

Sortアルゴリズムの消費メモリについて(続 〜In-place merge sort & Multithread merge sort〜)

Quick Sortは理論上は対象データの並び順によって最速のソートになる可能性があるが、最悪の場合(降順にソートされている場合かつPivotを先頭あるいは最後の要素に選択する場合)はO(n^2)かかってしまう、という問題点があり、Merge Sortは安定してO(nlog(n))を達成できるため、Merge Sortが好んで利用されるケースもある。しかし、計算量だけでなくメモリの使用量についても考慮すると、Merge SortはO(n)使用してしまうことになる。このメモリ使用量O(n)を減らすことはできないだろうか、と考えてみる。

Bubble SortのようにIn-placeで要素を変更していくと、余分なメモリを使用する必要がないので、メモリ量はO(1)、つまり2要素の間で入れ替える分だけ用意すれば済むが、計算量はO(n^2)で非常に遅いので使えない。そこで、Merge Sortの改良版として、In-placeでMerge Sortを実施するアルゴリズムを考える。

d.hatena.ne.jp

上記を参考に、実装を読みながらCで実装した。実装したというより読む部分が多かったので、実装上にコメントを多めに入れている。特に不思議だったのは、最小公倍数を求めている(gcd関数がある)ところだ。これは、左のリストのkey以上と右のリストのkey以下を入れ替えるために必要らしい。最小公倍数を求めずに、左のリストのkey以上と右のリストのkey以下を一つのリストとみなして回転するやり方でも問題無いように思えるが、そこは良くわからないので、参考通りに実装した。

void rot_left( int * p, int size, int rot )

    //
    // * Example to explain rotation * //
    //
    // original p = { 0,2,4,6,8, 1,2,3,4,5 }
    // key  = 5
    // rot_left p = { 6,8, 1,2,3,4, (5) }
    //
    // size = 6 ( p = { < 6,8, 1,2,3,4 > ,5 }
    // rot  = 2 ( p = { < 6,8 >, 1,2,3,4,5 }
    //
    // then, gcd is 2 and rotate as follows
    // { < 6,8, 1,2,3,4 > ,5 } <= rot_left p
    // { < 1,8, 3,2,6,4 > ,5 }
    // { < 1,2, 3,4,6,8 > ,5 }
    //

f:id:nishidy:20161104224809p:plain:w400

  • Cの実装はこちら

In-place merge sort · GitHub

In-place merge sortは、メモリ使用量はO(1)で済むが、計算量はO(n(log(n)^2))となる。実測してみたところ通常のMerge SortのO(nlog(n))に比べるとかなり遅い。ソート処理中に動的にメモリを割り当てる必要がないため、速度的にも期待は持てたのだが実際にはそれほど速くなかった。実際のメモリ使用量については/usr/bin/timeRSSを測定してみた。ソート対象データとしてはどちらも10,000,000のint型のリストを二つ(一つはソート結果を照合するため)使用しているが、in_place_merge_sortの方がおよそRSSが半分になっていることが分かる。

$ /usr/bin/time -l ./merge_sort 10000000
Merge sort : 4.06 sec.
Sorted check OK.
mem_size = 889MB, malloc_cnt = 9999999
        4.99 real         4.86 user         0.09 sys
 161189888  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
     39360  page reclaims
         2  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         0  signals received
         0  voluntary context switches
      2533  involuntary context switches

$ /usr/bin/time -l ./in_place_merge_sort 10000000
In place merge sort : 24.49 sec.
Sorted check OK.
       25.39 real        24.92 user         0.12 sys
  80576512  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
     19678  page reclaims
         3  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         0  signals received
         1  voluntary context switches
     11428  involuntary context switches

mallocしたメモリ量をカウントした結果がRSSよりも非常に大きいのはなぜだろうか。 念のため、10のリストで実行した結果はこちら。

$ /usr/bin/time -l ./merge_sort 10
Merge sort : 0.00 sec.
Sorted check OK.
mem_size = 0MB, malloc_cnt = 9
        0.01 real         0.00 user         0.00 sys
    548864  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
       141  page reclaims
         2  page faults
         0  swaps
         0  block input operations
         1  block output operations
         0  messages sent
         0  messages received
         0  signals received
         1  voluntary context switches
         3  involuntary context switches

$ /usr/bin/time -l ./in_place_merge_sort 10
In place merge sort : 0.00 sec.
Sorted check OK.
        0.00 real         0.00 user         0.00 sys
    561152  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
       146  page reclaims
         0  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         0  signals received
         0  voluntary context switches
         1  involuntary context switches

また、Multithreadを使ってMerge sortを高速化できないか実装してみた。ソート対象の範囲は共有しなくて良いので、ロックなしでthreadが実行できる。GCPのvCPUx16のインスタンスを使って、thread数を変えながら実行時間を測定してみた。なお、thread数もmalloc回数もロック無しで雑にカウントしているので信頼はできない。また、こちらでは消費メモリについてはそれほど気にしていない。ソート対象はsrand(100)で固定、3回ずつ測定を実施した。

thread数を大きくした場合に、thread無しの実装よりも速くなった。ただ、GCPの環境では実行するたびに測定結果に数秒の揺らぎがあったので、単純にスレッド数の違いが測定時間に影響しているのかどうかはまだ疑わしい。なお、GCPIntel VT-xは使っていないらしい。仮想化環境はKVMだが、CPUはVMに排他的に割り当てられていないのだろうか?(それともこれはnested virtualization = KVM on KVM が可能でないことを確認をしただけなのだろうか?) Nested VMMは無効だということですね。

Merge sort with multi-threaded (without lock) · GitHub

$ cat /proc/cpuinfo | egrep "model name" | uniq
model name      : Intel(R) Xeon(R) CPU @ 2.50GHz
$ cat /proc/cpuinfo | egrep "processor" | wc -l
16
$ grep -i vmx /proc/cpuinfo 
$ dmesg | grep -i vmx

$ for i in 2 4 8 16 18 20; do for j in {1..3};do ./sort 10000000 $i; done; echo ""; done
Merge sort with multi-thread: 3.58 sec.
Sorted check OK.
mem_size = 1088MB, malloc_cnt = 26107177
# of threads = 2
Merge sort with multi-thread: 3.54 sec.
Sorted check OK.
mem_size = 1094MB, malloc_cnt = 26378016
# of threads = 2
Merge sort with multi-thread: 2.86 sec.
Sorted check OK.
mem_size = 1078MB, malloc_cnt = 25520760
# of threads = 2

Merge sort with multi-thread: 3.54 sec.
Sorted check OK.
mem_size = 951MB, malloc_cnt = 21693873
# of threads = 4
Merge sort with multi-thread: 3.62 sec.
Sorted check OK.
mem_size = 953MB, malloc_cnt = 21775278
# of threads = 4
Merge sort with multi-thread: 3.56 sec.
Sorted check OK.
mem_size = 942MB, malloc_cnt = 21880252
# of threads = 4

Merge sort with multi-thread: 3.95 sec.
Sorted check OK.
mem_size = 665MB, malloc_cnt = 13939773
# of threads = 9
Merge sort with multi-thread: 4.06 sec.
Sorted check OK.
mem_size = 492MB, malloc_cnt = 9169216
# of threads = 10
Merge sort with multi-thread: 3.76 sec.
Sorted check OK.
mem_size = 648MB, malloc_cnt = 13171368
# of threads = 9

Merge sort with multi-thread: 3.69 sec.
Sorted check OK.
mem_size = 484MB, malloc_cnt = 8216468
# of threads = 16
Merge sort with multi-thread: 2.25 sec.
Sorted check OK.
mem_size = 436MB, malloc_cnt = 7040719
# of threads = 17
Merge sort with multi-thread: 1.83 sec.
Sorted check OK.
mem_size = 485MB, malloc_cnt = 8194432
# of threads = 18

Merge sort with multi-thread: 1.85 sec.
Sorted check OK.
mem_size = 480MB, malloc_cnt = 8200301
# of threads = 19
Merge sort with multi-thread: 2.40 sec.
Sorted check OK.
mem_size = 436MB, malloc_cnt = 6874139
# of threads = 18
Merge sort with multi-thread: 2.25 sec.
Sorted check OK.
mem_size = 451MB, malloc_cnt = 6861356
# of threads = 19

Merge sort with multi-thread: 1.79 sec.
Sorted check OK.
mem_size = 511MB, malloc_cnt = 8695299
# of threads = 21
Merge sort with multi-thread: 2.15 sec.
Sorted check OK.
mem_size = 455MB, malloc_cnt = 7680709
# of threads = 21
Merge sort with multi-thread: 2.03 sec.
Sorted check OK.
mem_size = 464MB, malloc_cnt = 7855797
# of threads = 21
$ for i in {1..3};do ./sorts_low_mem 10000000; echo ""; done
Quick sort : 5.45 sec.
Sorted check OK.
mem_size = 1419MB, malloc_cnt = 6832420
Merge sort : 2.93 sec.
Sorted check OK.
mem_size = 889MB, malloc_cnt = 9999999

Quick sort : 5.43 sec.
Sorted check OK.
mem_size = 1419MB, malloc_cnt = 6832420
Merge sort : 2.97 sec.
Sorted check OK.
mem_size = 889MB, malloc_cnt = 9999999

Quick sort : 5.49 sec.
Sorted check OK.
mem_size = 1419MB, malloc_cnt = 6832420
Merge sort : 2.96 sec.
Sorted check OK.
mem_size = 889MB, malloc_cnt = 9999999

Binary Searchの集合への適用について

Binary Search – topcoder

Binary Searchは、例えばソートされている整数のリストにある値が含まれているかどうかを確認するときに使うと、単純なループでチェックするよりもかなり計算量を抑えることができる。単純にループで確認するやり方は計算量がO(n)になるが、Binary SearchではO(log(n))になる。どのくらい違うかというとO(1)≒O(log(n))≪O(n)くらいに考えれば良い。

このようにBinary Searchでリストから値を検索するためのライブラリは多くの言語で提供されている。ただ、Binary Searchはもっと強力で、ある実数の集合に対する適用が可能だ。対象が一見してシーケンシャルなものである必要はない。これは競プロでは良く使われる手法であり、慣れてくれば問題文を理解した時点ですぐにBinary Searchによる解法が適当だと判断できるようになるらしい。

対象が集合になってもBinary Searchとして考えるのはリストである。ただし、noyesがそれぞれ連続して現れるように述語(Predicate)を考える必要がある。noyesの境目は一つであり、その境目に向かってBinary Searchが進んで行くことになる。実装における勘所は以下になる。

  • 解答すべき値をLower boundとUpper boundの間で上下に振り、与えられた条件が答えになるような述語を考える
  • 与えられた条件の中で、最小値(Lower bound)と最大値(Upper bound)を考える

述語はyesnoを返却する関数を考えれば良い。ただし、リストに適用した場合の述語は、medianと比較した結果を返すだけ、であるのに比べると、もっと複雑になる。また、与えられた条件の中でboundを導き出すことも非常に重要である。例えば、以下の問題では実際にboundを取り違えて正しい値に収束しない実装を書いてしまった。

Problem Statement for FairWorkload

    int getMostWork(int[] folders, int workers){
        int low = 0;
        int high= 0;

        for(int f: folders){ high+=f; }

        int mid=0, c=0, t=0, m=0;
        while(low<high){
            mid = low + (high-low)/2;
            c=t=0;
            for(int f: folders){
                if(mid<f){ break; }
                if(t+f<=mid){ t+=f; }
                else{ 
                    t=f; c++;
                }
            }

            if(c<workers){ high = mid; }
            else{ low = mid+1; }
        }

        return low;
    }

この場合、Upper boundは全ての数を足し合わせたもので問題無いが、Lower boundは0以上でかつ十分小さな値、であればなんでも良いわけではない。ここは条件として与えられたリストの中の最大の値を使わなければいけない。

        for(int f: folders){
            if(low<f){ low=f; } // XXX
            high+=f;
        }

ソートされた整数のリストに対するBinary Searchのboundは、そのリストのインデックスの最大値と最小値であることは明白だが、集合に適用する場合はここを考えるのが一つの勘所になる。

このようにしてTopCoderのModerateレベルのBinary Searchで解ける問題を解いてみた。実装は以下。TopCoderは実際に解いた解答者の実装を公開しているので、そちらを参考にする方が良い。

FairWorkload - SRM 169 · GitHub

Mortgage – SRM 189 · GitHub

HairCuts – SRM 261 · GitHub

UnionOfIntervals – SRM 277 · GitHub