理学部情報科学科の3S
なんとなくまとめてしまった。簡単な復習です。忘れないうちに。
全体としては、理情の授業は「コンピュータのシステムや"計算"という概念をあらゆるレイヤーで理解する」ことを目的に組まれているような感じで、「何かを作る」とか「何かを解く」というよりも「コンピュータ」とか「計算という概念」そのものが好きという人向けという感じがある（ので僕はとても好き）。まぁコンピュータ・サイエンスっていうのはそういうものなんだろうか。
課題そのもののネタバレは無いはず（多分）。
実験・演習
月：システムプログラミング実験
Operating SystemレイヤーやOperating Systemの一個上のレイヤーレベルの話を実践する実験。
第二回
Linuxのシステムコールを実際に呼び出してみる回。getpidのシステムコールを生で呼び出すと遅いが、libcを介すると速いという話や、簡単なcpを作ったりwcを作ったり、最後はls -lを作る。結構綺麗に作れたりする。
ls自体は、自分がパイプでどこかにつながれているか、出力がすぐにターミナルに吐き出されるかで、色付けをするかどうかを変えているみたいな小話があった（課題とは全く関係ないが）。
それをするには、isattyを使えば分かる ようである。まぁもっともぼくはlsに色をつけなかったが。
https://stackoverflow.com/questions/1061575/detect-in-c-if-outputting-to-a-terminal
第三回
マルチスレッド回。マルチスレッドで遊びます、終わり
第四回
ネットワーク回。tcp/udpで遊びます、終わり。実際ココらへんは際どい話が多くて実際もう一度やれと言われても綺麗にできる感じがしないので、正しい理解にはもう少し精進が必要そう。
正直四回まではあんま真面目にやってなかった気が（ほんまか）。ちょうどこのあたりで僕のPCが壊れた。
第五-六回
シェルを作る。とくにfg, bg, jobsなどのジョブ管理コマンドが正しく動くように実装する必要がある。
シェルは、お互いに壊しあうのが結構楽しいようで、その中で出てきた一つcatをn個パイプでつなげた
cat | cat | cat | .. | cat
その中の右端でも左端でもないようなcatのプロセスをkillしたときの挙動というのが比較的面白かった（かつ課題の大筋とは関係ない）のでメモをしておくと、殺されたcatの左側はwriteしようとしたタイミングでSIGKILLを受け取り、これはデフォルトで終了するので、たかだかn回のenterによってすべての左側のcatプロセスは終了する。一方右側のcatは単純にEOFを受け取ることになり、終了する。
なので、パイプでつながれたcatはどれか一つ死ぬと、連鎖的に死んでいくことになる。かなしい
第八-十回
ベアメタル回。OSに頼らずにコードを書くことが求められる。livaさんが用意してくれた部分が多いのでややまだ理解の至らない部分が多い（なぜ、hoge番地でMMIOできるようになっているか？とか、そもそも例外ハンドラ部分は、「ハンドラ」を書いただけであって、GDTいじったりIDTいじったりみたいなことはしなかったりなど）。
しかし、普通やらないであろう実験であることは確かで楽しいものではあった。個人的には、最初の方の四回半分にしてこっち長くしたほうが理解度的に幸せになれそうな感じがあった（ほんまか）
やることは、簡単なページング、DMAによる時間の計測および画面にデータを出力、TSCとの比較、割り込みとspin lockの実装をする。
spin lock、原理自体は結局CPU潰して待つというだけなんだが、結構奥が深い用で、複数コアで来た順にロックを獲得できるような仕組みというのはいろいろあるようである。
まず本当に愚直に実装する場合は、単に一つのbitでロックの状態を管理し、atomic命令によってTestAndSetをすればよいのだが、これだと順序が保たれない。すなわち「横入り」されてしまうかもしれない。
これを回避するためにticket lockというのがある。これは、銀行とか病院の「番号札」のような仕組みで、自分の番号札になるまで待つ、ロックを解放する際に値を1増やす、のようなアルゴリズムを考えることができる。
これでもう十分な気もするわけだが、複数のCPUが同時に特定のメモリ領域を書き込み・読み込みすることがticket lockでは要求される。これはキャッシュロックの頻発や、キャッシュラインのプロセッサ間での転送(cache line bouncing)が多発することになり、パフォーマンスに影響する。
これを防ぐために、単純に「待っている人の数」だけ待ち時間を増やすbackoffテクニックというのがある。またこのような単純なアプローチではなく、ロックの構造自体をCPU一つ一つに与えて、それぞれのCPUはその構造を監視する。この構造はリンクリスト的になっていて、自分が解放された際には、次にロックを獲得するものがいれば、隣の人のフラグを立てる、というようにする
このようにすることでcache line bouncingを極力抑えることができるようになる。
spin lockといっても非常に低レベルな問題によって工夫の仕様があるんだなあという気持ちになる
参考
https://lwn.net/Articles/531254/
https://lwn.net/Articles/590243/
なんか色々書いてしまった
火：関数論理型実験
名前の通り関数型言語OCamlと論理型言語Prologについて学ぶ実験。驚くべきことにこの実験でRustも勉強してしまった。
ところでこの実験のおかげでTeX力が1あがった（0から）
1-4回
OCaml自体で遊びます。Church数をOCamlで書くと、predに型がつかなくなってしまうので困りますね、という話や、副作用周りの話、Curry Howard isomorphism周りの話、モジュールを使ったGADT、リストモナドの"別実装"など。FLに一貫して言えるが、こういう発展的な"ネタ"は素直にOCamlを学んでいるときには見えにくい話なので、こういうの良いな〜っていう感じである。
5-9回
OCamlのインタプリターを作ります。lex/yaccから始まり、MLの基本機能を実装し、最後はlet多相を実装します。最後rank 2 多相を実装するというのがありましたが、残念ながらできていない。
let多相は、TAPLの22章Type Reconstructionあたりを実装する感じで、22.7のp334にある例
```ocaml
let x = fun x -> (x, x) in
let x = fun y -> x (x y) in
let x = fun y -> x (x y) in
let x = fun y -> x (x y) in
let x = fun y -> x (x y) in
let x = fun y -> x (x y) in
x (fun x -> x);;
```
という式は少なくともOCamlのバージョン4.06.1では、型がつかない。これは型がつかないのではなく、型推論が「終わらない」。これに型がつく（推論が生きている時間で終わる）ように拡張したりする。
unifyの回は、let多相が案外コーナーケースがあるらしく、意外と正しく実装するのは難しいらしい。
10-12回
最初にPrologで遊びます。tic tac toeを完全解析するような述語を作ったりする。
そして、Prologを作ります。なんとなく公開する（まぁprolog処理系はいくらでも書きようがありそうなので）。
https://github.com/moratorium08/pyoyog
基本的に後半はPrologが論理的におかしい挙動をするという話が行われる。Prologがどのように動作するかというのはWikipediaのSLD導出を見たほうが良いが、Prologの実装が必ずしもそれに沿ってないというのが問題となる。
これの最たる問題として
- Prologの探索アルゴリズムが深さ優先であること
- Prologがunifyアルゴリズムを走らせるときに、出現検査をしないこと
- Prologの否定を取る際に、変項を含む場合でもただちに否定をしてしまうこと
のような問題がある。これらを解決したProlog風処理系を作るのが課題になる。
13回
オセロの思考ルーチンを作る課題。これはOCamlでもHaskellでも P r o l o gでも良い。そしてなぜかRustでも良かった（許された）（なぜ？）。なので、Rustで書いたのだが、割とRustの勉強になってよかった。nomはlex/yaccになれた人間がいきなり使うと割としんどかったが。
書き始めるとわかるが、OCamlのint型は63bitで、64bit目はGCのために使われるらしい。しかしこの性質が今回の課題ではやや仇で、オセロのbitboardを実装する際できれば64bitの整数が欲しくなる。もちろんより処理の遅くなった64bit型整数というのがOCamlにも存在するが、bitboard上の演算は、速いほうがうれしそうという理由でRustで書いたほうが良いという話があった
ただ、Rustの場合、サーバーとの通信を行うクライアント側のコードなども自分で書く必要があり少ししんどかった。
あとあんまり強くならなかったので悲しい。評価関数学習はそんなに簡単ではなかった。
木：ハードウェア実験
詳細に書くのがしんどくなってきたので、以降適当にまとめる
ハードウェア実験はVerilogとVivadoに""あいさつ""するような内容。少なくとも理情で学ぶ言語たちに比べてクセが強いのでお気持ちを理解するような感じで、多分秋のCPU実験に備える、ないしコア係にはならんぞの気持ちを高める。
これしばしばVivadoの仕様（バグでは？！）みたいなのものに引っかかってしんどい気持ちになることがあり、よく引っかかったのが、
- 代入時の左右のビット数違い
- 勝手に最適化
の２つである。後者はとくにしんどく、ちゃんと回路がどのようにマッピングされたかを結局のところ見ましょうね〜という話らしい。ひえ〜
具体的な内容は前半4回ほどで、簡単な加算器とかフリップフロップをブレッドボードで作るやつをやった後に、残りでVerilogで回路を書いて、FPGAで動かす、というのをする。内容は、整数の割り算回路、浮動小数点数加算回路、UARTによる通信、AXI4バスのデータ転送回路である。最後のデータ転送あたりは、CPU実験が透けて見える内容になっていて、転送命令のFetch/Decode/Exec/Writeの工程をパイプライン化して速くするような課題をやった。
多分3Sでは一番の低レイヤーだった。
講義
講義は１限が無い、出席をほとんど取らないので期末試験でできれば（基本的に）良いという感じなのがとても良い。
実際演習は（真面目にやると）少し重めなので、授業出ずに課題やっていることもあった（良いことかは知らないが）
月：Operating System
OSの各種仕組みに関して概観する授業。マルチプロセス・マルチスレッドの周りのよくある話（Race Condition, Dead Lockとかそういう話）、CPUスケジューリングの話（FCFSからRate Monotonic, EDFおよびマルチプロセスの際のスケジューリング問題）、仮想記憶の話やPage Fault時のReplacementアルゴリズム周り(LRUやLRUの近似アルゴリズムについて）、IOとファイルシステム・権限周り、最後にバッチシステムや並列分散コンピュータ・メニーコアなどの話が非常にざっくりあった。なんか最後のメニーコア・GPGPUあたりの話が先生的には好きそう。
スライドが包括的で良いが、しかししばしばおかしなところがあったりしてfuga、まぁお気持ちで読めるが。授業にはあまり行かなかった。
火：離散数学
グラフ理論の話。グラフの基本的な話から、フロー、線形計画法・単体法、マトロイドの話が、双対性を軸に進む。
内容が半分競プロで、まぁフロー周りとかは完全に競プロでは。単体法の計算がしんどい。マトロイド周りはどちらかというと、"数学"という感じで、あまり深くやってないのでなんとも言えないが、触りをやった。あと、""予告問題""として、「polymatroidを用いて、Kruscalアルゴリズムの妥当性を証明する問題」を出そっかな〜って言っていたのでオッってなったが出なかった（何）。
あまり真面目に授業に出ていなかったのでなんとも言えない・・・。
水：情報論理
計算可能性、等式論理、命題論理、述語論理と最後にゲーデルの不完全性定理周りについて。教科書が英語。
内容が非常に広いので僕はどれほど理解できているかはわからない。ある意味初習論理 という感じで、多分反復深化が求められている。
計算可能性については、primitive recursive functionから始まり、recursive functionとwhile プログラムの等価性の話や、universal recursive functionとhalting problem周りの話、そしてRecursively Enumerable Predicateの話が続く。
各論理は、syntaxとsemanticsそれぞれについて議論した後に、健全性・完全性の話をする。特に、述語論理の完全性では、Herbrandの定理周りの話を（他の話題に比べて）深くやって、ある程度真面目に議論していた（と思う）。
まどかちゃんコンパクト性ss compact.pdf - Google ドライブ などが面白かった（ほんまか）。
木：言語処理系
コンパイラ周りの理論の授業。字句解析から始まり、LL・LR文法、型周り、中間コード生成と最適化、レジスタ割当などの話。二村射影も。
基本的に
[:タイガー本] は、https://www.amazon.co.jp/Modern-Compiler-Implementation-Andrew-Appel/dp/0521607647に沿った内容ではあるが、スライドが良いし、先生が良い（個人的な感想）。3S講義では一番好きだった。この授業は全部行ったと思う。
まとめ
最後のほう少し書くの疲れてしまった。
2017年の総括
毎年振り返っているので今年も振り返ろうかなと思います。そうはいっても2016年の総括を書いているのが本当に先週くらいかな？と思うほど1年が過ぎていくのが早かったので少々恐ろしい気持ちです。最近は分身を体得すべく努力しています。
以下ポエムです。
と思ったんですが、ポエムを書く気力がなかったのでやめます。気の赴くままに過ごしていました。来年も気の赴くまま好きなことをして嫌いなことはしないモラトリアム期間を過ごして行きたいなと思います（ほんまか？）
Brainf*ckを、直接実行可能バイナリにコンパイルした話
なんとなくカレンダーを埋めたいという衝動に駆られるので記事を書きます。
おととい書いたELFを書く話によって、僕らは事実上任意の機械語列をELFにすることができるようになりました。次は、当然任意のBrainf*ckで書かれたプログラムをコンパイルできるようになるべきです。
つまり今度の目標は、「与えられたBrainf*ckのプログラムを実行可能なELFに変換する」ということになります。
コンパイラというと、実際は、機械語を直接吐き出すのではなく、一度アセンブリ言語やなんらかの中間言語を生成して、そのあとでアセンブラ等によって機械語を吐き出すという形なものが書きやすく一般的（一般性を十分担保できるほど僕はコンパイラの実装を読んでいないが）な気がしますが、今回は、bfのコードを受け取って直接機械語に翻訳してみようと思います。
というのも課題の指定がそうなので。課題ではコンパイラそのものもアセンブリ言語で書く必要がありますが、とりあえず方針を立てる意味でもPythonで書いてみようと思います。またPowerPCではなくx86-64上のLinuxで動くプログラムについて考えます（なのでこの記事は課題そのものではないです）。
keystone engine
そうはいっても、吐き出す機械語をマニュアルを読んで生成するのはさすがに億劫なので、keystone engineという、CTFしているとたまに見かけるAssembly Frameworkの力を借ります。実際これで遊んでみたのを記録にしようと思っただけという話でもあります。
Keystoneを使うと次のように、アセンブリを対応する機械語に変換してくれます。
In [2]: from keystone import *
In [3]: ks = Ks(KS_ARCH_X86, KS_MODE_64)
In [4]: def asm(code):
...: c, _ = ks.asm(code)
...: return ''.join([chr(x) for x in c])
...:
In [5]: asm("mov rax, 1")
Out[5]: 'H\xc7\xc0\x01\x00\x00\x00'
In [6]: asm("nop")
Out[6]: '\x90'
In [7]: asm("jmp 0")
Out[7]: '\xeb\xfe'
書いたもの
現状はこんな感じで書いています。bfの仕様としては、とりあえず、めんどいのでメモリは100000バイトの領域を0x900000からmmapで確保するという適当なことをしてはいます。当然領域外へ出たら壊れます。 ここらへんちゃんとELF上に書いておけばいい話ではあるんですが、それをやるよりmmapした方が（書くのが）速いし、全体のサイズが小さいという話があるので、まぁ気が向いたらみたいなところが強い
あとはこれをアセンブリで書き出すだけではありますが、面倒なので気合いが出ればやろうという感じ
実行
せっかくなので、いくつかのbfのコードを実際にコンパイルしてみました。例えば、先日のesolangのCodeGolf大会で、@satosさんが書いた「与えられた2進数が三角数かどうか判定」するプログラムを実際に実行してみました（回答自体はTSGのGithubからみられます）。
ubuntu@ubuntu-xenial:~/ctf/experiment$ ./bf 00000011 00110111 10100101 00011111 01011001 10010100 00111100 01101000 11001000 01011011 10001000 10111110 01000010 01110011 10011001 10101100 00001010 01101001 00101101 11111101 11100111 00001000 00001111 10101011 00110010 11110111 00011100 11110110 00000000 10110001 01111000 00100011 01001110 10010000 00000110 00000001 00110011 00010101 10000101 11010010 00010101 01111101 00100001 01011010 00101110 11001010 11100000 00100100 10111110 00111110 11000000011110101111101100101010101101011000000110
一応正しく動いていそうです。
ちなみにコンパイルしたあとのバイナリをディスアセンブルすると、
こんな感じになります。Rev問だったら地獄ですね？
実際、同じ処理をペタペタ貼り付けているだけなので、ここらへんもう少し効率化とかすると楽しいかもしれません。
手で ELFを書く
学科の基礎実験でAssemblyでbrainfuckのコンパイラをかけという選択課題があります。この課題をやろうと思うと、ELFをある程度理解し、自分で生成できる必要があります。
今回、最低限の機械語を実行可能なELFフォーマットで出力できるようになるために手でELFを組み上げていき理解を深めてみようと思いました。
もちろんELFと言っても用途が様々ですが、ここでの目標は次の機械語の列を実行して、シェルが起動するということとします。
出展：http://shell-storm.org/shellcode/files/shellcode-806.php
お気持ちとしては、「たまにはシェルコードもエクスプロイトされずに実行されたいよね」です。
実際、Brainfuck -> 機械語のコンパイル結果はそれ自体に関数とか複数のオブジェクトファイルがリンクされているだとかそういう"構造"はなく、ただ単に機械語の列になると思うので、課題を達成するための理解として第一段階はそれでいいだろうという話でもあります。
方針
道具
ELFを手で書くと言っても、さすがに鉛筆で書くことはできません（メモリにマップすることができないため）。ここではpythonのアシストを借りつつ最終的にELFをダンプするようなスクリプトを書いていこうと思います。
その上で、ELFを書く上で、8~64bitのリトルエンディアンのpackが必要になることが多々あるため、次のようなショートカット関数を定義しておきます
import struct def p8(x): return struct.pack("<B", x) def p16(x): return struct.pack("<H", x) def p32(x): return struct.pack("<L", x) def p64(x): return struct.pack("<Q", x)
また、entrypointと、実際に実行する機械語として、
code = '\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05' entry_point = 0x400078
を定義しておきます。
全体像
ELFのヘッダについての詳細な情報は日本語や英語版Wikipediaなどに詳しく書いてあるので一つ一つ書くことはしてもしょうがないのですが、重要となる点についていくつか書きます。
まず、ELFは、ELF Header、Program Headerそして、Section Headerを持ちます。ELF Headerはただ一つ存在しELFファイル全体を管轄するメタデータです。 また、Program Headerはメモリにマップする、"され方"を定義するものです。つまり、メモリ上のどのアドレスにどのような領域（Read/Write? Executable?）をマップするかをとりしきります。 そして、Section Headerはオブジェクトファイルをリンクしたりする際のメタデータを持ちます。今回は外部のライブラリをロードしたりすることはないので、このHeaderは登場しません。
出展：Wikipedia
今回書くELFの構造的なイメージは次のような感じです。
このような形でマップされるようなELFを書いていきます。
環境
今回書くのは、64bit ELFバイナリ(x86-64)です。環境は
$ uname -a Linux ubuntu-xenial 4.4.0-97-generic #120-Ubuntu SMP Tue Sep 19 17:28:18 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux $ uname -a Linux ubuntu-xenial 4.4.0-97-generic #120-Ubuntu SMP Tue Sep 19 17:28:18 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 16.04.3 LTS Release: 16.04 Codename: xenial
です。
ELFヘッダを書く
まず必要となるのがELFヘッダです。これは書かないことには始まりません。次がELFヘッダです
# ELF Header elfh = '' elfh += '\x7fELF' # magic elfh += p8(2) # Class: 2 is 64bit elfh += p8(1) # Endinan: little endian elfh += p8(1) # ELF Version: EV Current elfh += p8(0) # EI_OSABI: It is often set to 0 regardless of the target platform.(Wikipedia) elfh += p8(0) # ABI version: (not used) elfh += p8(0) * 7 # Padding: currently unused elfh += p16(2) # e_type: 2 is exectable file elfh += p16(0x3e) # e_machine: 0x3e is x86-64 elfh += p32(1) # e_version: original version(maybe whatever) elfh += p64(entry_point) # e_entry: entry point elfh += p64(0x40) # e_phoff: program header table offset -> 64bit is 0x40 elfh += p64(0) # e_shoff: section header table offset -> notable elfh += p32(0) # e_flags: maybe whatever elfh += p16(0x40) # e_ehsize: ELF Header Size elfh += p16(0x38) # e_phentsize elfh += p16(1) # e_phnum: the number of program header entries elfh += p16(0) # e_shentsize: no section headers elfh += p16(0) # e_shnum: no section headers elfh += p16(0) # e_shstrndx: no section headers
一つ一つの内容については、Wikipediaを参照して欲しいですが、いくつか取り上げると、
elfh += p64(0x40) # e_phoff: program header table offset -> 64bit is 0x40
これは、上の図でいうと、Program Headerがすぐ下に続くことを意味しています。ELFで64bitのとき、ELF Headerの大きさは0x40なので、その大きさ分だけオフセットを書きます。
Program Header
今回必要になるのはただ一つのProgram Headerです。というのもマップする必要のある領域がただ一つであるためです。
prmh = '' prmh += p32(1) # p_type: type of segment prmh += p32(5) # p_flags: memory segment permission. 0b101 -> Exec + Read prmh += p64(0x40 + 0x38) # p_offset: offset of the segment prmh += p64(entry_point) # p_vaddr: virtual address to be mapped in memory prmh += p64(entry_point) # p_paddr: physical address to be mapped in memory (maybe not used in my machine) prmh += p64(len(code)) # p_filesz: file size of this segment prmh += p64(len(code)) # p_memsz: file size of this segment prmh += p64(0x1000) # p_align: alignment
これについては一行一行説明しようと思います
prmh += p32(1) # p_type: type of segment
これはセグメントのタイプを定義します。1がPT_LOADであり、ロード可能なデータに関するセグメントであることを意味しています。ロード可能であるとは、p_fileszやp_memszを持つということを意味しています。
prmh += p32(5) # p_flags: memory segment permission. 0b101 -> Exec + Read
これはマップする領域のpermissionを表します。1bit目がExec, 2bit目がWrite, 3bit目がReadに関するpermissionを意味しています。すなわち、5(0b101)はExecとReadができる領域であることを意味します
prmh += p64(0x40 + 0x38) # p_offset: offset of the segment
実際にこの領域が表すデータがファイルの先頭からのオフセットでどこにあるかを表します。最初に示した図を見てもられるとわかるとおり、Code自体はELF HeaderとProgram Header一つのすぐしたにあるので0x40 + 0x38であることがわかります。
prmh += p64(entry_point) # p_vaddr: virtual address to be mapped in memory prmh += p64(entry_point) # p_paddr: physical address to be mapped in memory (maybe not used in my machine)
これは、実行時にマップされるアドレスを表します。p_paddrは物理メモリを使う場合に使われる情報のようですが、僕の環境では関係ないと思われますし、基本的に普通のパソコンを使う限りは関係ない情報だと思われます。
prmh += p64(len(code)) # p_filesz: file size of this segment prmh += p64(len(code)) # p_memsz: file size of this segment
これは、それぞれfile上でのマップするデータの大きさと、メモリ上での大きさを表しています。今回は一致していますが、しばしばmemszはfileszより大きくてもよく、その場合0埋めがされます( Tips ELFフォーマットその１ ELFフォーマットについて)
prmh += p64(0x1000) # p_align: alignment
これはアラインメントを表します。
実際にダンプしてみる
この二つのHeaderに実行するコードをくっつけたファイルを吐き出すと実際に実行できます（完成したスクリプトは、ここにあります）。
ubuntu@ubuntu-xenial:~/ctf/experiment$ python snipet.py
(64, 56, 27)
147
ubuntu@ubuntu-xenial:~/ctf/experiment$ ./dump
$ echo hello
hello
$ readelf -e dump
ELF Header:
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: EXEC (Executable file)
Machine: Advanced Micro Devices X86-64
Version: 0x1
Entry point address: 0x400078
Start of program headers: 64 (bytes into file)
Start of section headers: 0 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 56 (bytes)
Number of program headers: 1
Size of section headers: 0 (bytes)
Number of section headers: 0
Section header string table index: 0
There are no sections in this file.
Program Headers:
Type Offset VirtAddr PhysAddr
FileSiz MemSiz Flags Align
LOAD 0x0000000000000078 0x0000000000400078 0x0000000000400078
0x000000000000001b 0x000000000000001b R E 1000
良さそうですね
終わりに
ELFファイルフォーマットについての知見が全くなかったので良い勉強になりました。brainfuck compiler on assembly書くぞの強い気持ち
参考にしたもの
Circle CI + Python3 + GAEについて
Circle CI + Python3 + GAEについて
別にどうというわけでもないが、メモ。３時間くらい悩まされたため。
背景
Googleが提供するPythonで実装されたスクリプト群がPython2で動くことはあまりにも有名ですね。そもそもAppEngineのStandard Environmentにデプロイしようと思うとPythonのバージョンは2でないと動かないです。
ところで、Flexible Engine(以下FE)では3も動かすことが可能です。先日、Python3 + Djangoで書いたコードをFEに投げてhogehogeしていました。ここにCIを導入しようと思い、ある程度無料でプライベートリポジトリでも利用可能なCircle CIを導入しました。
問題
問題は、アプリがPython3で動いている一方で、Python2のgcloudコマンド群を動かさないといけないという点です。
Circle CIが用意しているイメージを使ってgcloudコマンドを叩くことは可能（Python2のイメージを使ってインストールすることも可能）ですが、そうすると、App側で動かしたい一連のタスクが実行できなくなりました。
根底にあるのは、普通に提供されている機能だけを使うと、Python2/3の両立が必要なタスクが難しいのではないか？という点です。
解決
結論は簡単で自分でdockerイメージを作りました。gcloud-python3にあります（二つ入れただけですが）。
jobs:
deploy:
working_directory: ~/repo
docker:
- image: moratorium08/gcloud-python3
environment:
- GOOGLE_APPLICATION_CREDENTIALS: "gcp-key.json"
steps:
- checkout
- run:
name: create yamls
command: |
echo "$GOOGLE_AUTH" | base64 -i --decode > "gcp-key.json"
gcloud auth activate-service-account --key-file "gcp-key.json"
- run:
name: install dependencies
command: |
python3 -m venv venv
. venv/bin/activate
pip install -r requirements.txt
- run:
name: collect static
command: |
. venv/bin/activate
python manage.py collectstatic
- run:
name: upload static files
command:
gsutil rsync -R static $BUCKET_NAME
- run:
name: deploy production
command: |
gcloud --quiet config set project "$GOOGLE_PROJECT_ID"
gcloud --quiet app deploy app.yaml
workflows:
version: 2
build-deploy:
jobs:
- deploy:
filters:
branches:
only: master
こんな感じ
感想
Dockerで殴るのは速いし余計なことを考えなくて良いなぁという気持ちですが、そもそも普段使いでgcloudとPython3を両立させるのが少々めんどう（virtualenv下においてPython3の環境だけでなく2も動くようにしておかないといけない？）なので一元的に扱う良い方法はないものなのかなぁという感じです。
知ってたら教えてください
Unix V6コードリーディングの個人的なメモ
学科ゼミとしてV6を読む会というのをやっています。ここまでのところ4回ほど開いて、順次はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)を読んでいます。とりあえずオラオラと9章(加えて14章)まで読んで来たわけですが、面白いなぁと思ったいくつかのことについて自分でまとめておこうという気持ちになったのでまとめようと思います。
ぼくはLions本を前から読んでいるわけではなく、V6の基本的知識はOSコードリーディング本によるものです。
（書いたのは、好きな話や少し気になった話だけです（浅く網羅しても仕方ないため））
forkの仕組み
概念的に「forkはプロセスの内容がコピーされて分岐する」のような説明を聞くことがあるのですが、これを達成する部分は少し巧妙でした。これはほぼ各所で書かれている話ですが、理解したところをまとめておきたいと思います。
基本的にUnix V6で新しいプロセスを作るにはこのforkをします。forkとは、現状のプロセスのコピーを作って、プロセスを分岐させます。ここで、実行される命令の列は同じだが、二つのプロセスの実行の流れを分岐させるうまい仕組みがあります。
そもそもforkは細かく見ると、具体的には次のいくつかの部分に分かれます
【親プロセス】
- newprocを呼び出す
- procやデータセグメントの情報を子供のプロセスにコピーする(*)
- newprocをreturnし、このとき0が帰って来る
savu(u.u_rsav);
rpp = p;
u.u_procp = rpp;
rip = up;
n = rip->p_size;
a1 = rip->p_addr;
rpp->p_size = n;
a2 = malloc(coremap, n);
/*
* If there is not enough core for the
* new process, swap out the current process to generate the
* copy.
*/
if(a2 == NULL) {
rip->p_stat = SIDL;
rpp->p_addr = a1;
savu(u.u_ssav);
xswap(rpp, 0, 0);
rpp->p_flag =| SSWAP;
rip->p_stat = SRUN;
} else {
/*
* There is core, so just copy.
*/
rpp->p_addr = a2;
while(n--)
copyseg(a1++, a2++);
}
u.u_procp = rip;
return(0);
(ken/slp.c)
このとき、子供は起きていない状態で、親の実行が進みます。次に、swtchによって、プロセスのスイッチが起きて、子供が起こされた時どういう挙動になるかを考えます。まず実行が始まるのは、データセグメントやレジスタの情報を保存した部分になります。これは、すなわち、上記のnewprocの中の部分です。
swtch自体は、
if(rp->p_flag&SSWAP) { rp->p_flag =& ~SSWAP; aretu(u.u_ssav); } /* * The value returned here has many subtle implications. * See the newproc comments. */ return(1);
(ken/slp.c)
のような形で関数から戻ります。
ここで重要なのは、swtch内でaretuが実行されることにより、このnewprocを呼び出した関数に戻るように、swtchがreturnされるという点です（すなわち、スタックフレームが一個ずれる）。これにより、newprocからあたかも1が帰って来ている状態になり、結果として、
fork()
{
register struct proc *p1, *p2;
p1 = u.u_procp;
for(p2 = &proc[0]; p2 < &proc[NPROC]; p2++)
if(p2->p_stat == NULL)
goto found;
u.u_error = EAGAIN;
goto out;
found:
if(newproc()) {
u.u_ar0[R0] = p1->p_pid;
u.u_cstime[0] = 0;
u.u_cstime[1] = 0;
u.u_stime = 0;
u.u_cutime[0] = 0;
u.u_cutime[1] = 0;
u.u_utime = 0;
return;
}
u.u_ar0[R0] = p2->p_pid;
out:
u.u_ar0[R7] =+ 2;
}
(ken/sys1.c)
上のプログラムにおいて、newprocの返り値による分岐ができています（！）。この仕組みはなかなかうまいなぁと思います。
文章で書いてもわかりにくいので図にしました。
図にしてもあまりうまく書けなかったです。
MMU用のハードウェアAPRなどの管理
UISAやUDSAのようなアドレスは特定のアドレスにマップされていますが、なぜこれを更新するとちゃんとコンテキストスイッチができるのかについて本を読んでいて納得できなかったので一応メモです（今から考えるとそれはそう）。
というのは、UISAやUDSAというのはアドレス中の値であり、具体的には
#define UISA 0177640 /* first user I-space address register */ #define UDSA 0177660 /* first user D-space address register */
のように定まっています。しかし、このアドレスというのは仮想アドレスであることから、MMUがうまく参照できないのでは？という疑念がありました。
結論から言うと、カーネルAPRの7番目の値すなわち仮想アドレス0160000〜0177777が常に物理アドレス上の0760000〜0777777にマップされるため問題はないです。 つまり、UISAがマップされる場所やUDSAがマップされる場所は常に固定で、逆にこの固定の領域を使って周辺デバイスとのやりとりがなされています。 これらのアドレスが選ばれていることについては、Lions本を引用すれば"The method of assignment of addresses to registers in this page is a black art: the values are hallowed by tradition and are not to be questioned."らしいので、とりあえずこの場所に固定された領域があってMMUがここを読みに来ているのでうまくアドレス変換が可能となるのだということまでは言えると思います。
その他ネタ
へーって思った話。普通にPDP 11のWikipediaとかOSリーディングの本とか見れば書いてあることだが、へーって思ったのでメモ。
無名構造体
int型の値のMSBから8bitみたいな値を参照するのに、構造体のようにアクセスしているコードが随所にあります。
(*bdevsw[rootdev.d_major].d_open)(rootdev, 1);
こんな風な感じです。これ一見すると全然変ではないんですが、例えばrootdevというのは、
int rootdev; /* dev of root see conf.c */
のように定義されていることからわかるように、int型の値です。すなわち、int型の値に構造体にアクセスしているということで、なんやねんとなります。
実は、ここで使われているC言語はpre K&Rといわれるもので、現在ではありえないような構文がいくつか存在します。これもその一つで、裏には、無名構造体という概念があります。例えば、d_major、d_minorの定義は
struct
{
char d_minor;
char d_major;
};
のようになっています。このように無名な構造体を定義すると、任意の変数に対してこのような参照が可能になります。 デバイス番号というのは、MSB8bitにmajor番号、その下8bitにminor番号が入ったものになっています（int型自体は16bit）。したがって、見方によってはint型というのはchar型が二つ並んだという構造をしているものであると考えることができ、よって上のような書き方をすることができます。すなわち、MSB1byte分に対するアクセスであると言えます。
ところで面白いのは、デニスリッチーですら混乱したのか一部では
(*bdevsw[swapdev>>8].d_strategy)(&swbuf);
(dmr/bio.c のswap関数)
のように、デバイスのMSB1byteをある種より直接的に取り出しているコードがあったりして面白いです。
エンディアンの話
上に関連して、上のコードが動くならリトルエンディアンなんやろなーって思ったら、少し興味深い感じでした。というのは、確かに16bitの値に対してはリトルエンディアンになっているのですが、32bitの値を表現する、すなわち2ワードに関しては、ワードについてはビッグエンディアンになっているらしいということです。日本語で説明するのは難しいので図があります。
itruncで間接参照テーブルについてのoff by one errorっぽいやつ
if(*ip) {
if((rp->i_mode&ILARG) != 0) {
bp = bread(rp->i_dev, *ip);
for(cp = bp->b_addr+512; cp >= bp->b_addr; cp--)
if(*cp) {
if(ip == &rp->i_addr[7]) {
dp = bread(rp->i_dev, *cp);
for(ep = dp->b_addr+512; ep >= dp->b_addr; ep--)
if(*ep)
free(rp->i_dev, *ep);
brelse(dp);
}
free(rp->i_dev, *cp);
}
brelse(bp);
}
free(rp->i_dev, *ip);
*ip = 0;
}
(ken/iget.c itrunc関数）
ここですが、
for(cp = bp->b_addr+512; cp >= bp->b_addr; cp--)
はおそらく、512ではなく、510ですよね。
これに関してはLions本にも言及があり、"Since they will presumably contain zero, they will contribute nothing to the calculation."などと書いてある。確かに、*(b_addr+512)が0であれば、そのあとの条件分岐の中に入らないので良いっぽいのだが、いつゼロクリアしたかというと、これは難しくて、例えばバッファの初期化部分のコードを見ると
clrbuf(bp)
int *bp;
{
register *p;
register c;
p = bp->b_addr;
c = 256;
do
*p++ = 0;
while (--c);
}
(dmr/bio.c)
となっていて256回ループするが、ところで、bufferの定義は、
char buffers[NBUF][514];
であることから、最後の2byteについてはおそらく0クリアされない。すると、どこで、0クリアされているのかを考えると、おそらく起動時の物理メモリの0クリアまで遡るのではないか。この部分については完全に推測でしかないが、しかし、off by oneっぽいのが残っているのは少し面白いです。
ねむい。だいぶ雑になってしまったので渋い（また全部読んだ時に改めてまとめたい）
