日々の破片

_ Binary 2.0 カンファレンス

Binary 2.0カンファレンス 2006 発表資料とレポート

一昨日になるが、Binary 2.0 カンファレンスに参加した（ご招待ありがとうございます）。

今回も滅法おもしろかった。僕にとっては、ネタ的/プレゼンインパクト的にはWiiリモコンでPS3をあやつった八重樫剛史さんの『tty hacks for PS3 Linux』と、あるある感が（あるのかよというツッコミはあるだろうけど）楽しかったakrさんの『getcontextの怪』と中村実さんの『マルチコア時代の並列プログラミング：ロックとメモリオーダリング』がベスト3かな。もちろん、「1か0かどちらかを選べと聞かれたら自由と答える」にはぐっと来たけどな。

で、上のはおいおいということで、残りからは本題に入る前に時間を食われてなにやら良くわからなかった竹迫良範さんの『Web2.0時代のAjax Binary Hacks 』が良く考えるとすごくおもしろかったのではないかとか、制約がすごいと会場からウケがとれる鴨志田良和さんの『携帯 Flash でバイナリ処理』とかのそれほどバイナリじゃないあたりから。

携帯FlashのActionScript（JavaScriptみたいなやつ）は、配列が無い（ここでおおっと会場がどよめく）、さらには忘れちゃったけど何かが無くて何とfunctonが無くて(追記：確かに無い)（もちろん会場がどよめく）、とにかく制約がきびしい。無ければ作れば良いじゃんといかないのは、メモリ制約も厳しいからとか。で、（数字は嘘かも）100Kのメモリに送り込むべきデータが圧縮しても95Kとか。でどう圧縮するかとか。そのあたりでIRCで一昔前のゲーム開発みたいじゃんというツッコミがあったりなかなか楽しい。そもそもデータを全部展開できないから取り出す位置だけをインデックスとして展開するということしたいけど、それをやるには辞書がランダムに配置されるgzipじゃだめだというような話もあったような気がするけど、ライトニングトークはメモしてないから間違ってるかも。で、データに文字列（ユニコード16ビットvalidなShift_JIS）を利用するんじゃなかったっけな（追記：利用する（と断言）。発表資料が公開されたので参照してください。おもしろいです）？ 配列がないから。ところが文字列はビット透過じゃないから、利用できる範囲が限定されていてそれを外れると？に変換されてしまうだかトランケートされるとかなのでうまくおさまるようにマッピングして……というようなPCを相手にしている限りはまったく実用的な意味はないけどパズル的におもしろい話（バイナリな話だな）。

戻って、竹迫さんのは、クロスドメイン通信をするのにGIFを利用するという話だったようなんだけど原理説明が光速だったので良くわからなかった（LLリングの時と同じで前振りで笑いを取りに行きすぎてるわけだが、それはそれでおもしろいからいいんだろうけど（追記：「けど」は余計でした。おもしろかったです））。GIFのサイズはブラウザー経由でJavaScriptで取り出せるから（追記：大きくは外してないけど、onloadの中では取り出せるということらしい。竹迫さんの解説）、そこにデータを仕込めばクロスドメイン通信ができるというのが技術的要旨だと思うのだが。img src=は確かにクロスドメイン（href=もそうだけど読まれたデータを見ることはできないけど、imgについてはサイズが取り出せるということなのだと理解したけど違うかも）。で、GIFのヘッダのサイズとして任意のデータを埋め込めばそれを参照できる（なんか例のA4の紙にでっかなデータを連想したけどそういう話ではたぶんなくて、サイズが0x414243ならABCというデータというようなことなのかな？）。

野首さんのASCIIは、首がふっとぶをテーマにしたASCIIアート（といっていいのかどうか良くわからないけど）MSX BASICで昔昔に作った動画（なのか？）の回顧展。トリをつとめるのにふさわしい時間制限を無視した演目でえらく刺激を受けた。このネタをなんだっけな？ 暗い洞窟症候群というのかな、つまりDirectXギンギンとかムービーですよ、ではできないだろう。抽象化とはすばらしいという温故知新。

鴨志田さんのは、PS3を使ったプレゼンで結構画像が粗い。で、諸般の事情からシートは6枚という。なぜ6枚なんだ？ と思わせておいてどこでそれに気付くかもポイントなんだろう。僕は3回転目くらいで気付いた。OS Xのユーザー切り替えみたいなプレゼンキューブなのだな。

Wiiリモコンを振ると立方体がカシャーンという音とともに回転してシートが出てくるという仕組み。音が重要。

以下、#はおれのコメント。というかコメントはコメント。

佐藤祐介さんの『Hello Binary World』は、gccの__attributeを使ってint mainを外す技の披露。main変数にretを書き込むあたりが山場かな。普通におもしろかった。
なんとなく、テレビのゴールデンタイムにやってるバラエティショウみたいなのでこういうのをやるような時代って絶対に来ないよなというのが不思議に思える空間があのカンファレンス会場なのだった。

金田憲二さんの『X日で作る仮想マシンモニタ（に向けて）』は、固いプレゼン。ネタは軽量VMモニタで、以下、僕が理解した範囲。ほとんど知識がゼロな分野なので間違って理解している可能性が高いので眉唾で読むこと。

昨今のVMは大規模で複雑化しているので利用するのが大変。実装が正しいのかも不明。バグがあればゲストOSが破壊されるので致命的。（と書いていて、ここで昨今のXXというのがVMなのかVMMなのかおれはわからなくなっている事実に気付く。ゲストOSが……ということからVMのことだと思うがVMMのことなのかも）で、軽量なVMモニタ（＝VMM）を作ることにして、現在3000行。

VMMは、プロセッサ/メモリを仮想化する。位置はプロセッサ/メモリの上、VMの下。モニタなんだからそれはそうだ。

仮想化とは：
 Sensitive命令の捕捉、割り込みの転送。メモリ割り当て（複数のVMの物理アドレスを個別に実機の物理アドレスに対応付ける）
#「メモリの仮想化：→Nested Paging」とメモしてあるけど、VMのページングをさらに割り当てするからnestedなのかな？
 AMD64には、VMRUN命令、VMEXIT例外というのがある。
VMRUN：
 コンテキストスイッチ命令（と理解した）
 jumpbufと実レジスタ群の交換みたいなことをする
 現在の実行コンテキストをVM_HSAVE_AREAに保存し、要求されたコンテキストを実行コンテキストに入れる（で、VMが実行されると理解したけど）
VMEXIT例外：
 エラーコードをメモリー上に格納（#IRCで、伏線キターと声が上がってたが別にその後はなかった）
 VM_HSAVE_AREAに保存していた状態を復帰
#sensitive命令の実行などでVMEXIT例外が上がるということらしい。sensitive命令ってなんだ？
苦労：
　SimNow（AMD64シミュレータ）、VMM、ゲストOS という並びなので（# VMがいないということは、VMモニタはVMのモニタではなくて、VMなのか？）
　バグがどこにあるかわからなくて大変。シミュレータの使い方を間違えていたというのもある。
　そのときは、アンドキュメンテッドなコマンドの実行が必要なのにそれをしていなかった。
質問：アンドキュメンテッドなコマンドの実行が必要だと、なぜわかったのか？
答え：あまりにおかしいので調べていたら研究室の先輩がバイナリを見て、怪しいシンボルを発見した（会場どよめき）。
　というのはおいておいて、サポートにメールして聞いた。
#サポート重要
質問：任意の命令をsensitive命令から外せるか？
答え：Yes
http://web.yl.is.s.u-tokyo.ac.jp/~kaneda/tvmm/

akrさんの「getcontextの怪」

#メモをそのまま掲載。

ruby getcontextを使うこともある
　IA-64ではうまく動かない。今は直したので動く
　setjmpは問題が起きない
　SPARC上のgccでも問題が起こる
　Sunコンパイラでは起きない
　Intelコンパイラ起きる
　HPコンパイラ起きない
  FreeBSD起きる（別件）
setjmp/longjmp
−メモリを復元しない
　longjmpからsetjmpへ値を伝えられる
#setcontext/getcontextを使う理由（必要になったらman見れば良いと思ったので適当）
IA64にはレジスタが多数あるので、関数呼び出しの前後の暇なときに保存/復元（レジスタスタック）。
SPARCにも同様な機構（レジスタウィンドウ）があるが、レジスタウィンドウはスタックに取られる。
レジスタスタックはヒープ上に確保（#ヒープという理解で良いかはわからない。スタックではない特定のプロセスメモリ空間のどこか）
setjmp　レジスタスタックのレジスタは保存復元しない
　　　（実はgccには細工が入っていた）
setcontext　記載がない：glibは保存復元しない
理由：関数呼び出しで本来レジスタは破壊されない：レジスタを多数保存するのは手間
setcontext　の前後で、r32が指すアドレスが変わる
結論：
大域脱出はコンパイラで対応する（コンパイラはレジスタスタックについて知らなければならない）
　→言語仕様に含めるべきだったのではないか
その他：
　最初IA64の問題としてgccのバグレポート。無視される。
　IA64を誰も使ってないから反応が無いと推測。
　同様な仕組みを持つSPARCで再現するだろうと考え、同様な問題が発生するパターンを作成しバグレポート。
　すぐに反応。パッチきたー。
　同様にIA64にも適用可能と指摘。IA64にも反映。
　バグレポートにはみんなが利用しているプラットフォーム重要。

中村実さんの「マルチコア時代の並列プログラミング：ロックとメモリオーダリング」

#メモをそのまま掲載。#は補足

　ターゲットモデル
　スレッドたくさん（Webアプリ）
　スレッドはコアにバインド（メモリスループットがボトルネック）
　並列GC（マルチコアでmutexがボトルネック）
：ターゲットは並列GC業界
　コアが増加で衝突が増加＝遅延発生
　衝突＝遅延
　MutexやSpin Lockに替わるスレッド同期？
　Lock-free synchronization
　　cas ll/sc
　　　Deque、FIFO、LIFO　などのデータ構造
　つまりOptimistic lock
シーケンスロック
　ロックをかけたいメモリーにカウンターを付ける（読み込みではロックしない）
　書き込み時にはカウンターが偶数＝解放、奇数＝占有
　書き込み時：1 カウンター読み取り　偶数＝CASで+1、書き換え、counter+1
　読み込み：Read Counter、Read Data、Read Counter 1が奇数または!=3で失敗
単方向リスト
　書き込み遅延を許可
　アトミック命令不要
Double-ended Queue（Deque)
　N.Arora et al、"Thread Scheduling for ……
　Sun HotSpot VMの並列GCで利用
どうやってプログラム？
　論文を読んで実装
　　　アプリケーションに合わせてデータ構造を調整して使う
　ライブラリ
　　Ross Bencina　
　　Lock-free library　GPL
問題点：
　衝突しなければ効率はmutexと変わらない
　アルゴリズムが複雑＝バグの源
　実装が難しい＝out-of-orderによってメモリアクセス順序の逆転が問題
　　→メモリフェンスを適切な位置に入れる必要がある
#衝突ゼロなら複雑な実装するより素直にmutex使うべきだし、衝突しすぎるなら楽観ロックの意味ないから素直にmutex使うべきだということだと思う。
Sequence lock
　読み込み側の3つのreadの順番が守られている必要がある（バリアが必要）
x86のメモリオーダリング
	RAR	WAR	WAW	RAW
i386：逆転なし
i486、p5	RAW（read after write）で逆転の可能性
P6以降 RAR、WAR、RAWで逆転の可能性
Opteron	RAR、RAWで逆転の可能性
C/C++では、基本はインラインアセンブラ（mb、rmb、wmb）を使ってmemory barrierを実装
#mbとか上で書いているのはそういうマクロが定義されているということだったかな？
C++　次期（C++0xには入るかも）
時代はマルチコア
　使えれば、Lock-free synchronizationを使おう
　Memory Ordering　コアが増えれば順序は起きやすくなる
メモリフェンスを入れた正しいプログラムを書こう
#なんか、Java並行スレッドプログラミングのような。
#でも、メモリバリアをバイナリアン以外のプログラマが意識するのはおそらく無理に近いように感じる。
#というわけで、akrさんのと同じくコンパイラが実装すべしというのがあるべき姿なのかな。

（参考のために追記：STM とロックフリーアルゴリズムの関係）

Binary Hacks ―ハッカー秘伝のテクニック100選(高林 哲)

#追記：YARVのグローバル変数ってハッシュだけど、読み込み多くて書き込み少ないとか、そもそもそんなにグローバル変数使うのか？ というのもあるわけでシーケンスロックを使って実装するとかが良いのかな、とか思った。