10年ほど後のBinary Hacks
https://twitter.com/nalsh/status/869086098177146881
を見て、今ならどういうネタが書かれるかなぁとざっくり考えてみます。
perf
@nlashさんに指摘されていた通り、perfは重要だと思うんですが、書かれていたperf_event_openはptraceなんか目じゃないくらい使いこなしがムズいと思うので、素直にperfそのまま使えって感が強い気がします
ptrace
PTRACE_SYSCALL以外はあまり変わってないと思うんですが、PTRACE_SYSCALLはPTRACE_O_TRACESECCOMPでやるとずいぶん速くなるのでオトク
asan/tsan
valgrindのbinary translationでのinstrumentationてのはカッコいいけど、普通に考えるとコンパイラに手を入れる方が常識的ですよね……という
ELF
特に変わりが無い気がする
DWARF
よく知らないけど割と変わってて、-gsplit-dwarfとか-gzあたりは知っててもいい気がします
セキュリティまわり
mitigationは気休めなんで、ちゃんと2レイヤ以上セキュリティ機能使いましょう的な
angrとかqiraとか
CTF/セキュリティ系の人が作ったツールは色々面白そうだけどあまり知らない
glibcのrandomization
そういえば気がついたらプロセス内の関数ポインタ全部ランダマイズされるようになってたけど、たぶんここ10年な気がします
inotify
便利だと思う。特にinotifywaitコマンドが……fanotifyが何が違うかは忘れました
madvise
元々書いてなかった気がするとふと思い出しました
コンテナ
コンテナベースの仮想化とかは色々ありすぎて。cloneのオプションとかすごく増えた気がするけど、今見るとそうでもないか
ARMの命令
スマホの台頭を考えるとARMについてもなんか。thumbとか。
まとめ
なんか結構あるなということと、最近知識がアップデートされてないから知らないだけで面白いことが起きていることがまだまだありそうだなぁということを思いました
Very symmetric JavaScript code
だいぶ前に左右反転させてもだいたい同じに見えるコードを書いたのですが、もうちょっと進化させて、上下反転と、180度回転してもだいたい同じように見えるコードを書いてみました。
デモサイト: http://shinh.skr.jp/obf/very_symmetric_js.html
コード: https://github.com/shinh/hack/blob/master/very_symmetric_js/very_symmetric.js
普通のJS記号ゴルフと比べるとクォートが無いのが多少めんどくさく、あとは左右は一行コメントがあるから簡単なんですが、上下反転と180度回転のコードをコメントですっとばすのがパズルという感じでした。何も考えずに実行するコードの最後に /* と入れただけだと、180度回転した部分に */ が現れてしまってコメントが終わってしまうという。
drdr
オレオレワークフローエンジン作りたくなる病というのがあって、例えば make 系なんかだと Wikipediaに色々書いてあったりします。ワークフローエンジンと総称するのが正しいのか知りませんが、依存グラフを順ぐりに並列に実行していくようなもの、色々あるわけですけど、目的も粒度もバラバラですが以下のようなものは割と似たようなものに見えてます。
- thread pool
- Tensorflow
- make
- Digdag
閑話休題。なんか微妙に10秒程度待ち時間があるような処理があって(クラウドストレージに対する例えば ls とか)、その ls の結果全てに対してまた10秒程度時間がかかるコマンドをまとめて実行、終わったら結果を集計、みたいなことをしたりすることが最近多いです。1週間から1ヶ月ほど10回とか100回使うんだけど、でもそのうち捨てる系のコード。私の場合、よくやる解決と問題点は
- shell script で並列化したいところはバックグラウンド実行+waitで散らして、最後の部分は ruby かなんかで書く: shell script と ruby の2つを管理するのがうっとうしい。多少ややこしいパイプラインを作るの大変
- ruby かなんかでスレッドプール作ってやる: 分散部分のコードがめんどくさい。多少ややこしいパイプラインを作るのがかなりめんどくさい
- make を使う: 動作は理想的なことが多いけど、コードがめんどくさくて、あと宣言的な記述になって、シーケンシャルな記述じゃなくなるので、読みにくく編集しにくい
欲しいことを考えると
- CPU並列は無くても良い
- パフォーマンスは最適でなくて良い
- コマンドが手軽に実行できると良い
- コマンドが失敗したら即座に止まると良い
- shell はミスりやすいから嫌だ
- 処理の後半部分のやりなおしとかのためにチェックポイントを仕込めると良い
で、まあなんか作りはじめてみましたというのがこれ。
https://github.com/shinh/drdr/
あまり良い例が思いつかなかったのですが、自分のスライドのディレクトリにあるスライド全部に対して、それぞれページ数を集計するサンプルがこんな感じ。
URL = "http://shinh.skr.jp/slide/" drdr { # スライド一覧のところを読んできて、 list.ckpt に保存しておく # これ以降のスクリプトに書き損じがあっても、再度ネットワークアクセスは発生しない cmd("curl #{URL}", ckpt: 'list.ckpt') | task{|l| # ここから list.ckpt に依存した処理で、 Apache の directory index を適当にパース l.scan(/href="([a-z].*?)\/"/).map do |m| name = m[0] # スライドのページ数を適当に取ってくる。このコマンド実行は並列に走る cmd("curl #{URL}#{name}/ 2> /dev/null") | task{|l| last_page = 0 l.scan(/(\d+)\.html/) do last_page = [$1.to_i, last_page].max end [name, last_page] } end } | task{|a| # 全部終わったら CSV として出力 a.each do |name, max_page| puts [name, max_page] * "," end } }
などなど。妄想したほど使い勝手良くなってない気がするのですが、しかし自分が使える程度のものにはなってるような気がします。しかし一般的にこういうのはどういう感じで処理してるもんなんでしょうか。なんかいい方法あったら教えてください。。
あと Guild が実装されると計算も並列に走るようになっていい気がしますね
tanlog
最近、 tanlog というのを作って使っていて、割と便利なので紹介してみます。
https://github.com/shinh/test/blob/master/tanlog.rb
元々は同僚と、なんか端末に出たもの前もって lv とか tee に入れておくのって、忘れることあるし、 lv とか tee に流すと isatty が false になって色出ないのうざいよねえ…みたいな話をしてたように思います。 grep については fake_isatty とか作ったりしたんですが、この時 soda さんに仮想端末作ってやる方法があると教えてもらったのを思い出して、 script とかで記録しておいたら…とか話していました。
結果、その同僚は zenlog というのを作って便利になった、とか言ってたのですが、なんか Perl と bash 混じってるとか、コマンドの切れ目をプロンプトで教えるとか微妙…ということで自作したものです。 zenlog に対して tanlog なのはコマンド起動ごとになんかするからです。まあこういうのは人の作ったものを使うというよりはみんな勝手に作ればいい…
tanlog は screen/zsh と一緒に使うことが想定されていて、 preexec で tanlog start して precmd で tanlog end します。 tanlog start は screen のログファイルを指定して /tmp/tanlog/RAW の下に端末出力をダンプしはじめます。 tanlog end はその端末出力を綺麗にして /tmp/tanlog の下にコピーします。
このディレクトリの構造は適当に便利なようになっていて、
- /tmp/tanlog/2017-02-12: ログの実体がある場所
- /tmp/tanlog/TODAY: 今日のディレクトリへのシンボリックリンク
- /tmp/tanlog/TODAY/P: さっき実行したコマンドのログへのシンボリックリンク
- /tmp/tanlog/TODAY/PP: その前実行したコマンドのログへのシンボリックリンク
- /tmp/tanlog/make: makeコマンドのログへのシンボリックリンクがこの下にころがっている
- /tmp/tanlog/make/P: さっき実行した make のログへのシンボリックリンク
などと適当に便利そうなものが入っています。えーと llvm ビルドした時の cmake コマンドはどんな感じだったかな…とか思ったなら
wgrep llvm /tmp/tanlog/cmake/P*
なんてやってます。 wgrep てのは grep を w3m でラップした何かです。
あとは tanlog paths てすると最近実行したコマンドに含まれるパスとかURLぽいものがだーと出るので、それを w3m に喰わせる wl ていうのも使ったりしてます。コマンドが URL 出してくれたけど、それマウスとか screen とかでコピペするのめんどい、て時に使ってます。
https://github.com/shinh/test/blob/master/wl
そのまま他の人が使えるような形にはなってないと思いますが、 screen のログ機能なり script なり使って、とりあえずコマンドの実行結果を全部残しておく、てのはなかなか良いのではないかと思っています。 lv か tee 通すべきかな?とか一瞬逡巡するのが無くなります。実現がハッキーになりすぎるのが残念なところで、こういうことを色々便利にやってくれる screen つき shell みたいなの作りたいなぁとかいうことを割とずっと思っています。
ELVM Compiler Infrastructure について
はじめに
言語実装 Advent Calendar 2016 用です。
ELVMは、コンパイラをフロントエンドと中間言語とバックエンドにわけて、多言語多CPUに対応しよう……というようなLLVMの考え方を、パロディと言っていいレベルにまで単純化したものです。結果として実用性は全くないが、C言語から他言語へのトランスレータを極めて簡単に書け、 Brainfuck などのような難しい言語のコードもC言語を書くだけで生成できる、というようなことを主目的としています。
本当は ELVM のバックエンドを一つ足して、 Brainfuck とかのような難しいターゲットでなければ、こういう感じで手軽に足せますよーということを書こうかと思っていました。しかし、ありがたいことにそういう趣旨だったり、あるいはもっと難しいターゲットについても、既にあれこれと書いていただいたのでした。例えば
- Perl: http://qiita.com/mackee_w/items/5397d6b9215f41c41db1
- Tex: http://hak7a3.hatenablog.com/entry/2016/11/13/153418
- Tex: http://hak7a3.hatenablog.com/entry/2016/12/03/124632
- Vim: http://rhysd.hatenablog.com/entry/2016/12/02/030511
- C++ (constexpr): http://kw-udon.hatenablog.com/entry/2016/12/03/201722
- Unlambda: http://irori.hatenablog.com/entry/elvm-unlambda-part1
など。上のリストは、おおざっぱに、上の方に簡単な雰囲気をつかむのに向いてそうな記事、下の方に謎テクニックを楽しむのに向いてそうな記事を並べてみました。いずれにせよ、こういう記事は中身をよく把握してる私自身より、試行錯誤していただいた他の人達が書いた方がわかりやすいでしょう……ということでなんか違うことを書いてみます。
具体的にはどういうふうに作業を進めたりした…てことを雑に書いていこうかと。技術的な概要は一つ前のこのポストとそこからリンクされてるスライドに書いたので、そっちを参照してください。
sedlisp, beflisp, makelisp, bflisp
色々あって、Esolangですごく簡単なLisp処理系を書く、というのがマイブームになったことがありました。 GNU sed と GNU make は完全手書きでした。sedlisp を書いた時から、 @rui314 さんは「手書きじゃなくて中間層を介して変換した方が良いのではないか」と言っていたのですが、 sed や make だと、計算モデルが違いすぎるので直接書く方がラクかなということと、結果できたものが遅くなりすぎそうだったので、直接書きました。
ですが、 Befunge の時はなにか中間に入れないとキツいと感じたので、 LLVM bitcode から雑に変換する、という方法でやりました。といっても、 LLVM bitcode は任意のものを許すわけではなく、変換器がサポートしてる命令しか吐かないように注意深く書かれた lisp.c を LLVM bitcode にして、そこから Befunge に変換する、というようなやり方でした。
で、 Brainfuck もやってみるかなぁと思った時に、これは自明に Befunge 以上に大変なわけで、まあなんかから変換するしか無いわけです。でも LLVM bitcode て以外に命令セットでかいということは Befunge の時に感じてたので、あまりつきあいたくなかった。じゃあなんかオレオレ中間コードを作るのが良いかな、と考えました。
bfs
で、 bfs という中間形式をデッチ上げました。これは今の ELVM の EIR と同じなんですけど、最初は Brainfuck だけが想定ターゲットだったので、 Brainfuck Assembly 的な理由でこういう名前になっていました。ややこしいんで今後 EIR で統一します。中間形式をでっち上げるのは、まあ適当に決めるだけなので簡単です。
で形式が決まるとCコンパイラをいじることになります。 main しか無いような簡単なコードを書いてみて、x86-64のコードを出力してる部分を順に EIR を吐くように変換して、うまくいったらreturn 42;とか1+2;とか、命令を足しては出てきたx86-64のコードを等価な EIR のコードに変換していく感じでした。
すごく短いプログラムをコンパイルできるようになったら、 EIR のシミュレータを書いたかと思います。命令数が少ないので、 Brainfuck のインタプリタを書く程度プラスアルファくらいの手間でできます。途中、ああ命令だけじゃなくてデータも書けないといけないな、ということで.dataセクションを足したりもしました。
この段階で重要だったのは、C言語で書いたコードをx86-64に変換して実行した結果と、EIRにコンパイルしてシミュレータで動かした結果が同じ、ということをきちんとテストすることでした。なにかまだサポートできてないCの機能を見つけるたびに、C言語でテストを書いて、makeと叩けばx86-64で実行した結果とシミュレータの結果が同じであることをチェックできるようにしてたと思います。
bflisp
C言語→EIRが一通りうまくいってるぽくなってくると、次は EIR を Brainfuck に変換する部分です。これはまあ……大変です。定数ロードとかをかけ算でやるとかは大変だし遅いBF処理系では全く通用しないので、8bitセルのBFで複数セルを使って1byte (当時は1byte==16bit) の情報を扱います。つまり単なる加減命令とかでも、繰上がり下がりの計算がはさまることになって……めんどくさいです。がまあ加減くらいは序の口で。
一番キツかったのは比較命令だったかと思います。上位セルが大きかったら下位は無視してーとか、0と比較する時だけおかしいとか、下位が0の時だけおかしいとか、そういう謎の現象が起きまくりました。load/storeも結構大変だったのですが、比較の後だったから慣れていたというのと、あまりコーナーケースが多くなかったこともあって、どっちかというとどういうレイアウトにするか、っていうデザインが大変だったような気がします。
こういうわけわからない有象無象をデバッグするために、EIRのシミュレータと、EIRからBrainfuckを出力した時のコードに、トレース出力をつけました。具体的には1命令ごとにレジスタの状態を出力する感じです。これでできた巨大なトレース出力を diff していると、喰い違いが出てくる部分がでてきて、そこを見ればバグの原因がわかるので、小さいテストを書いて修正する……というのを繰り返しました。これはオモチャ CPU 作った時にも使ったアプローチで、CPUの時はエミュレータに実行トレースをつけたものと、iverilogでトレースを出してたものを比較してました。でまぁ、なんかうまくいきました。
あとは、C言語→EIRの時に使ったテストケースを、順にEIR→Brainfuckの変換でも正しく動くかをテストしていった感じでした。そんなこんなで lisp.c が Brainfuck の上で動きました。
8cc.bf
さて、lispが動くならCコンパイラ自体もBrainfuckで動かしたいな、ということで色々試しはじめます。まずわかったのは16bitのメモリ空間では、命令もデータも足りない、ということでした。命令の方は、「実際のCPUじゃないんだから、1命令ごとにPCひとつ使う必要ないよね」ってことで、 basic block ごとに PC が変わることになりました。 VLIW と考えても良いかもしれないです。いや良くないでしょうけど。
データの方はちょこざいなこともできなくて足りないので、素直に24bitに拡張しました。命令も拡張しても良かったんでしょうけど、前述の basic block ごとに命令をまとめる作戦は、単純に実行速度の向上にも貢献するのでいずれにせよやって良かったと思います。
あとは少しバグをつぶしたらEIR→Brainfuck側はだいたいできました。足りない libc 関数の用意と、 8cc 側の EIR としてサポートできない記述の修正です。 libc は ARC やオモチャ CPU のために書いたコードや、 Bionic から必要なものをひっこ抜いてきたり自分で書いたりして準備しました。 8cc 側の困った記述というのは、 signed が無いので value >= 0 とかが常に true とか、あとはビットシフトと浮動小数の撤去でした。
そんな感じで 8cc が Brainfuck 上で動きました。5時間ほどかかってセルフホストができて、おおーと思いました。
ELVM
このへんでだいたい満足してたのですが、2点ほど思っていることがありました。
- id:irori さんが Unlambda への変換を実現させて、 8cc.unl を作ってくれたのですが、こういう感じでもっとターゲットを増やすと面白いのではないか
- EIR→Brainfuckの変換はRubyで行なっていたので、完全なセルフホストではなかった。これでは人類からBrainfuckインタプリタ以外が失われた時に対応できない
でまあ、一番大変な 8cc.bf というのはすでに動いてたので、だるいなーと思ってたのです。がまあある日、2つとも一気に解決しよう、で ELVM とかいう景気のいい名前をつけよう、とか思い立ちました。名前とか決まるとやる気出ますね。
でまあ、まずはEIR→ターゲットの部分をCにしつつ、ちゃんとフレームワークぽい感じにしました。実装量はあったけどまあやるだけ。
他の部分は適当ですが、ターゲットを増やすのは割とやりやすくなってるのではないかと思います。なんか適当に周りの言語のコピペしてると、だいたいおかしいところが少しずつ見えてきて、インクリメンタルに作業できるんじゃないかと。特に Makefile がよく書けてると自負してまして、バックエンド書く人は少し Makefile に追記したら make hoge だけで hoge バックエンドに対するテストがたくさん走る感じになってます。
バックエンドを増殖させる
基本部分ができるとバックエンドを増殖させていきました。色々足していると、基盤部分にあった方がいい共通部品なんかが見えていったりしました。
Esoteric 方面の言語だと、 Befunge 、 sed 、 Piet 、 C-INTERCAL あたりはなかなか大変なバックエンドでした。特に経験が無かった C-INTERCAL と、あと Piet はなんか色々大変でした。
Piet はこう、 Befunge みたいな感じでできるかな…と思ってたのですが、コード変換と2次元レイアウトを同時にやるのが大変で、一旦 PietInst とかいう構造体の列にして、それからレイアウトを決めて色を配置する、みたいなことをやりました。つまりもう1つ中間言語を介してるわけです。
INTERCAL はこう、方言多すぎ、仕様多すぎですね。色々やってたのですが、結局 C-INTERCAL がまともに動きそう、ということでこれになりました。 add とか sub とか無いんで、このへんはパズルチックにプリミティブを作ってく感じでした。
反応など
当初は「ヘンなことやってるなあ」くらいに思われる程度だと思っていたのですが、予想以上に反応をいただいて、PRでバックエンドを足していただいたりして嬉しい誤算でした。現状28バックエンド中13バックエンドはPRでいただいた、というのはなかなかなもんだなと。最初の方に Unlambda, Vim, TeX バックエンドを書いてくだださった iroriさん rhysd さん hak7a3 さんには特に感謝する感じです。紹介記事書いていただいたのも後に続く人を増やしていただけたんでないかなと。
その後の展開としては、 C++ constexpr バックエンドのバズりっぷりがなかなか愉快でした。 @llvmweekly や Bjarne Stroustrup がコメントしたりと。あと、チューリングマシンバックエンドを書いていただいた、ND-CSE-30151というアカウントは、どうもこれノッテルダム大学の講義用のアカウントらしく、この講義のテーマにチューリング完全などがあるため、少なくとも授業で紹介くらいはしてくれるのでないかと思います。ジョークプロジェクトが大学の授業で紹介されるというのは、なかなか胸熱です。
あと、 id:irori さんの EsoLang vi のような方向性も面白いですね。改造 8cc が処理できる C 言語で書かれたソフトであれば、 Unlambda やら Brainfuck に変換できちゃうわけです。
まとめ
スライドにも書いたのですが、理論上できるに決まってることでも、実際動かしてみるのは大変だったりして、でも動いたりすると嬉しいもんだなと。どうも私は発見とかがしたいんじゃなくて、そんなのやってどうすんのってこととか、理屈はわかるけどそれ本当に現実的な話としてできるの、てことをやるのが好みなのかなぁと、最近思います。セクシーボイスアンドロボというマンガの主人公が、「私がしたいのは世界にちょっとしたドリームを与えるような、そういうこと」とか言ってたんですが、なんかたぶん、そういうことが目指すところな気がします
言語処理系、文法とかそういう表の部分に注目しがちですけど、バックエンドやそれ以降も面白いですよ、と。たとえば世の中の言語作者はもっとデバッガとかに興味持ってあげて欲しいと思ったりします。
あとはこう、なんか世の中にあるもののパロディーというか似たようなものを適当にでっちあげるというのは、なんかとりあえずやる、ってテーマとしては良いなと思ったりしました。なんか趣味コード書くかっていって、まぁいきなりデカいオープンソースに飛び込むとかすごい有用なもの作る、っていって手が動く人はいいんですけど…
PRは随時募集という感じなので、冬休みの暇潰しなどに、ぜひバックエンドを足してみてください
ELVM Compiler Infrastructure
最近作ってたオモチャがだいたいまとまってきました。
第12回 kernel/vm 勉強会で発表した時のスライド:
http://shinh.skr.jp/slide/elvm/000.html
これは何かというと、前作った bflisp を改良したり整理したりしたもので、 C 言語をシンプルな中間言語 (EIR) に変換する改造 8cc と、その中間言語を Brainfuck をはじめとした他言語に変換するバックエンドから成り立っています。 bflisp との差分は、 Brainfuck 以外のバックエンドを追加しやすくしたり、バックエンドを C で書いて、完全に Brainfuck だけで 8cc.bf を再現することができるようにしたり、という感じです。
特に興味深いであろうバックエンドとしては、 Brainfuck, Unlambda (id:irori さん作), Piet, C-INTERCAL, Befunge, Whitespace などがあります。例えば Lisp を Piet で動かしたりもできるようになりました。 lisp.png を gimp で開いてスクリーンショットを撮ったこの画像なんかは結構お気にいりです。
JavaScript に変換することもできるので、デモサイトは ELVM を使って作った JS で作られています。
http://shinh.skr.jp/elvm/8cc.js.html
スライドにも書きましたが、「チューリング完全な言語互いに等価だからうんぬん…」というような、理論ではそうなんだけど…というようなことが実際確認されるのを見るのはなかなか楽しかったです。コンパイラいじり、 esolangs での計算プリミティブ作成パズル、最小限の libc 作り、など好きなトピックがたくさんあるという意味でも楽しくて良かったです。
Brainfuck interpreter in Ruby's Regexp
Ruby の正規表現だけで Brainfuck インタプリタを作ることができました。正規表現の実行は =~ だけなので、ループなども正規表現の内部で実行してます。
https://github.com/shinh/hack/blob/master/bf_rb_reg/bf.rb
つまりどういうことができるかというと、 BF_REG という Regexp と BF_SUFFIX という文字列定数があって、 bf という文字列に格納された Brainfuck のコードを
BF_REG =~ bf + BF_SUFFIX
で実行することができます。出力は $~['o0'], $~['o1'], ... に入っているので、
output = '' 256.times do |i| o = $~["o#{i}"] break if !o output += o end
的なコードで取り出すことができます。入力は ! の後に続いてる文字列を入力とする形式。Ruby の正規表現は Turing 完全でないので、無限ループはできないようになっています。
仕様の一覧を並べると
- 8bit Brainfuck
- 入力の終端は -1
- メモリは255番地まで
- 出力文字数は256まで
- 入力文字数は256まで
- Brainfuck命令以外の文字があると正規表現がマッチに失敗する
- 無限ループがあると正規表現がマッチに失敗する(正確には1つのループが256回連続回ったら止まるという仕様なので、本当は止まるコードもマッチ失敗することがありえます)
など。256まで、という制限は実装をラクにするためなので、本質的な制限ではないです、が無限にはできないです(入力文字数は無限にできるかも?)。この程度の制限があっても十分に実用的(?)で、例えば cal.bf も動いています。
$ echo 2016 10 | time ruby bf.rb cal.bf 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ruby bf.rb cal.bf 1147.54s user 0.26s system 99% cpu 19:07.91 total
ただすごく遅くて、 cal.bf の実行に19分とかかかってました。1命令10msとかその程度だと思います。 + とか - が実に遅い。
こんなことできるとはつい最近まで思ってなかったのですが、 HITCON CTF で正規表現力の研鑽を積んだ結果、なんかできるような気がしてきて、やってみたらできました。
今思うに、一番重要なことは後方参照を更新できる、ということだったのかなと思います。 \g で呼び出された中にある後方参照は、呼び出されるたびに値が変わっていくという。