PDP-11による機械語入門

PDP-11とはUNIX V6の動作対象となるアーキテクチャです。バイナリを通してUNIXを学習します。

この記事は以前開催していた池袋バイナリ勉強会の初回編で教えていた内容をまとめたものです。

この記事には姉妹編があります。

• 8086による機械語入門 2015.11.09
• VAXによる機械語入門 2016.02.14

環境設定

UNIX V6のバイナリを動かすためのインタプリタと、その上で動く当時のコンパイラをインストールします。

• インタプリタとコンパイラ一式をインストール

コンパイル

ハローワールドでテストします。

hello.c

main() {
    printf("hello\n");
    return 0;
}

※ UNIX V6にはlibcのヘッダがないため#includeはしません。

先ほどインストールしたコンパイラでPDP-11用のバイナリを生成します。

$ v6cc hello.c

※ v6ccはシェルスクリプトで、インタプリタ上で当時のコンパイラ（PDP-11バイナリ）を実行しています。

a.outというファイルが出力されます。PDP-11用のバイナリであることを確認します。

$ file a.out
a.out: PDP-11 executable not stripped

実行

出力されたバイナリをインタプリタで実行します。

$ 7run a.out
hello

オプション

7runを引数なしで実行するとオプションが確認できます。

$ 7run
usage: 7run [-p] [-d|-v/-s] cmd [args ...]
    -p: PDP-11 mode
    -8: 8086/V6 mode
    -d: disassemble mode (not run)
    -m: verbose mode with memory dump
    -v: verbose mode (output syscall and disassemble)
    -s: syscall mode (output syscall)

よく使う-dと-mを説明します。

逆アセンブル

バイナリの中にどのような命令が入っているかを分析します。この操作を逆アセンブルと呼びます。

$ 7run -d a.out

[crt0.o]
start:
0000: f009            setd
0002: 1180            mov sp, r0
0004: 1226            mov (r0), -(sp)
（略）

簡単なプログラムなのにすごく複雑だと感じられたと思います。入門にはあまりに複雑過ぎるため、今回の記事ではもっと簡単なものから始めます。基礎を固めてから、このバイナリに挑戦していただきます。

読み方

[crt0.o]やstartはシンボルと呼ばれ、見出しのようなものです。

その後は次のような構成になっています。

アドレス	機械語	アセンブリ言語
0000:	f009	setd
0002:	1180	mov sp, r0
0004:	1226	mov (r0), -(sp)

• アドレスは行番号のようなものです。そこにCPUに対する命令が入っています。
• 命令は数字で構成されており機械語と呼ばれます。ここでは16進数表記されています。
• 機械語は人間には読みにくいため、意味を英語の略語などで表記したものがアセンブリ言語です。

機械語やアセンブリ言語については後で詳しく見ていきます。

トレース

命令やレジスタなどのログを表示しながら実行できます。この操作をトレースと呼びます。

$ 7run -m a.out
 r0   r1   r2   r3   r4   r5   sp  flags pc
start:
0000 0000 0000 0000 0000 0000 fff6 ---- 0000:f009 setd
0000 0000 0000 0000 0000 0000 fff6 ---- 0002:1180 mov sp, r0
fff6 0000 0000 0000 0000 0000 fff6 -N-- 0004:1226 mov (r0), -(sp) ;[fff6]0001 ;[fff4]0000
（略）

逆アセンブルと異なるのは、命令が実行される順番に表示される点です。基本的には上から順番に実行されますが、分岐や関数呼び出しなどでアドレスが飛びます。

例

fff8 0000 0000 0000 0000 0000 fff4 -N-- 000c:09f7 0008      jsr pc, 0018 ;[0018]0977
_main:
fff8 0000 0000 0000 0000 0000 fff2 -N-- 0018:0977 023c      jsr r5, 0258 ;[0258]1140
csv:
fff8 0000 0000 0000 0000 001c fff0 -N-- 0258:1140           mov r5, r0

アドレスが飛んでいることを確認してください: 000c → 0018 → 0258

シンボル

逆アセンブルのときに出て来たシンボルを一覧表示します。

$ v6nm a.out
024e T _exit
020c T _flush
02be B _fout
（略）
027c d swtab
02b4 b width
0018 t ~main

構成は次の通りです。

アドレス	種類	シンボル名
024e	T	_exit
020c	T	_flush
02be	B	_fout

種類は初めから細かく理解していなくても、大雑把にTとtが関数、それ以外は変数だと考えておけば良いです。それらがどのアドレスに関連付けられているかを示しています。

※ 関数や変数以外にも種類はありますが、当面は必要ありません。

ファイルサイズの縮小

シンボルは付加的情報で実行には必要不可欠なものではありません。シンボルを削ってファイルサイズが縮小できます。

$ wc -c a.out
1186 a.out
$ v6strip a.out
$ wc -c a.out
706 a.out

シンボルがなくなっていることを確認します。

$ v6nm a.out
no name list

実行には支障ありません。

$ 7run a.out
hello

逆アセンブルでシンボルが出て来なくなります。

$ 7run -d a.out
0000: f009            setd
0002: 1180            mov sp, r0
0004: 1226            mov (r0), -(sp)
（略）

シンボルがないと関数の切れ目などが分からなくなるためデバッグや解析が困難になります。次のような運用方法が一般的です。

• 開発時にはデバッグのためシンボルを付けておきます。
• 完成品をバイナリ配布する際には、ファイルサイズを縮小するためシンボルを取り除きます。ソース非公開の商用製品の場合、内部構造を解析されにくくする意図もあります。

小さなバイナリ

小さなバイナリを作って分析します。

write.s

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6

/ exit(0);
mov $0, r0
sys exit

.data
hello: <hello\n>

実行結果

$ v6as write.s
$ v6strip a.out
$ 7run a.out
hello

• アセンブリ言語の文法はアセンブラによって方言があります。
  • このアセンブラでは/はコメントです。
• アセンブリ言語はCPUによって異なります。今回はPDP-11です。
  • r0 はレジスタと呼ばれます。変数のようなものです。
  • mov は前から後ろに代入します: mov $0, r0 ⇒ r0 = 0
  • sys は割り込みを発生させる命令です。

システムコール

割り込みでカーネルを呼び出してOSの機能を利用することをシステムコールと呼びます。

• sys の後にシステムコール名を書きます: write, exit など
• r0 は第一引数
  • write に渡す 1 は標準出力
• sys の次の行には追加の引数を書きます。

UNIX V6のシステムコール定義: /usr/sys/ken/sysent.c

int sysent[]
{
    追加の引数の数, &処理関数, /* システムコール番号 = システムコール名 */
    ...
};

• exit: システムコール番号 1, 追加の引数の数 0
• write: システムコール番号 4, 追加の引数の数 2
• sysent[] { の間にイコールがないのはC言語が古いため（pre K&R）

逆アセンブル

バイナリを分析します。

$ 7run -d a.out
0000: 15c0 0001       mov $1, r0
0004: 8904            sys 4 ; write
0006: 0010            ; arg
0008: 0006            ; arg
000a: 15c0 0000       mov $0, r0
000e: 8901            sys 1 ; exit

• write.s →（アセンブル）→ a.out →（逆アセンブル）→ 上記結果
  • アセンブル: アセンブリ言語 → バイナリ
  • 逆アセンブル: バイナリ → アセンブリ言語
• 逆とは言っても完全に元に戻るわけではありません。
  • 逆アセンブルでは対応するバイナリが確認できます。
• 逆アセンブラの出力はアセンブリ言語の文法とは異なります。
  • アセンブリ言語は8進数
  • 逆アセンブラは16進数

バイナリダンプ

バイナリを16進数で出力します。

$ hd a.out
00000000  07 01 10 00 06 00 00 00  00 00 00 00 00 00 01 00  |................|
00000010  c0 15 01 00 04 89 10 00  06 00 c0 15 00 00 01 89  |................|
00000020  68 65 6c 6c 6f 0a                                 |hello.|
00000026

※ hd がない環境では hexdump -C や od -tx1z -Ax を使用します。

メモリに読み込み

先頭の16バイトはヘッダです。ヘッダはメモリに配置しないため、ファイルのオフセットとメモリのアドレスは16バイトずれます。

メモリ配置

0000 c0 15 01 00 04 89 10 00 06 00 c0 15 00 00 01 89 ................
0010 68 65 6c 6c 6f 0a                               hello.

• text（命令）＋data

仕様

コード例は擬似言語で示します。

• ヘッダ＋text（命令）＋data
• ヘッダは最初の16バイト

aout = File.readAllBytes("a.out")
h = aout.slice(0, 16)

• ヘッダを2バイトずつ区切って、2番目がtextのサイズ、3番目がデータのサイズ。リトルエンディアン。
• 今回のサンプル: tsize = 0x0010, dsize = 0x0006

tsize = h.read16Unsigned(2)
dsize = h.read16Unsigned(4)

• ヘッダの後にtextがあり、その後にdataがある。連続した領域なので一気にメモリに読み込みます。
• 「メモリに読み込み」はmemをダンプしたものです。

mem = aout.slice(16, tsize + dsize)

練習

※ 制限時間内に作成できない場合、解答例に進んでください。

【問1-1:20分】ファイルをそのままバイナリダンプするプログラムを作ってください。（hd a.out 相当）

⇒ 解答例 (F#)

【問1-2:10分】メモリに読み込んだ状態をバイナリダンプするプログラムを作ってください。

⇒ 解答例 (F#)

【問2-1:1時間】逆アセンブラを作ってください。（7run -d a.out 相当）

⇒ 解答例 (F#)

【問2-2:1時間】バイナリを実行してください。（7run a.out 相当）

⇒ 解答例 (F#)

※ 以後、問2-2で作ったものをインタプリタと呼びます。

少しずつ拡張

先ほど作った小さなバイナリを少しずつ拡張していきます。

数値をメモリに書き込む

メモリを操作して出力する文字列を変更します。

write-1.s

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ r1 = hello;
/ *(uint16_t *)r1 = 0x4548;
mov $hello, r1
mov $42510, (r1)

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ exit(0);
mov $0, r0
sys exit


.data
hello: <hello\n>

実行結果

$ v6as write-1.s
$ mv a.out write-1.out
$ 7run write-1.out
hello
HEllo

練習

【問3-1:5分】逆アセンブラを対応させてください。

⇒ 解答例 (F#)

【問3-2:10分】インタプリタを対応させてください。

⇒ 解答例 (F#)

ディスプレースメント

相対アドレス指定によるメモリ操作を行います。

write-2.s

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ r1 = hello;
/ *(uint16_t *)(r1 + 2) = 0x4548;
mov $hello, r1
mov $42510, 2(r1)

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ exit(0);
mov $0, r0
sys exit


.data
hello: <hello\n>

実行結果

$ v6as write-2.s
$ mv a.out write-2.out
$ 7run write-2.out
hello
heHEo

2(r1) の 2 は r1 に対する差分を表します。この差分をディスプレースメントと呼びます。

意味的には (r1+2) です。（この構文はエラーになります）

練習

【問4-1:5分】逆アセンブラを対応させてください。

⇒ 解答例 (F#)

【問4-2:10分】インタプリタを対応させてください。

⇒ 解答例 (F#)

movb

1文字だけの書き替えを行います。

write-3.s

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ r1 = hello;
/ *(uint8_t *)r1 = 'H';
mov $hello, r1
movb $110, (r1)

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ r1 = hello;
/ *(uint8_t *)(r1 + 2) = 'L';
mov $hello, r1
movb $114, 2(r1)

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ exit(0);
mov $0, r0
sys exit


.data
hello: <hello\n>

実行結果

$ v6as write-3.s
$ mv a.out write-3.out
$ 7run write-3.out
hello
Hello
HeLlo

movb は mov の byte 版です。

練習

【問5-1:5分】逆アセンブラを対応させてください。

⇒ 解答例 (F#)

【問5-2:10分】インタプリタを対応させてください。

⇒ 解答例 (F#)

レジスタの値をメモリに書き込む

数値をいったんレジスタに入れてからメモリに書き込みます。

write-4.s

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ r1 = hello;
/ r0 = 0x4548;
/ *(uint16_t *)r1 = r0;
mov $hello, r1
mov $42510, r0
mov r0, (r1)

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ r1 = hello;
/ r2 = 0x4c4c;
/ *(uint16_t *)(r1 + 2) = r2;
mov $hello, r1
mov $46114, r2
mov r2, 2(r1)

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ exit(0);
mov $0, r0
sys exit


.data
hello: <hello\n>

実行結果

$ v6as write-4.s
$ mv a.out write-4.out
$ 7run write-4.out
hello
HEllo
HELLo

練習

【問6-1:5分】逆アセンブラを対応させてください。

⇒ 解答例 (F#)

【問6-2:15分】インタプリタを対応させてください。

⇒ 解答例 (F#)

バイト命令

レジスタを movb 命令のソースに使うと、下位の値だけが使われます。swab 命令で上位と下位を入れ替えることができます。

write-5.s

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ r1 = hello;
/ r0 = 0x4548;
/ *(uint8_t *)r1 = r0;
/ r0 = (r0 << 8) | (r0 >> 8);
/ *(uint8_t *)(r1 + 1) = r0;
mov $hello, r1
mov $42510, r0
movb r0, (r1)
swab r0
movb r0, 1(r1)

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ exit(0);
mov $0, r0
sys exit


.data
hello: <hello\n>

実行結果

$ v6as write-5.s
$ mv a.out write-5.out
$ 7run write-5.out
hello
HEllo

練習

【問7-1:10分】逆アセンブラを対応させてください。

⇒ 解答例 (F#)

【問7-2:20分】インタプリタを対応させてください。

⇒ 解答例 (F#)

アドレスを直接指定

今までメモリは r1 レジスタ経由でアクセスしていました（これを間接参照と呼びます）。アドレスを直接指定でアクセスすることも可能です（これを直接参照と呼びます）。

write-6.s

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ *(uint16_t *)hello = 0x4548;
mov $42510, hello

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ *(uint16_t *)(hello + 2) = 0x4c4c;
mov $46114, hello + 2

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ *(uint8_t *)(hello + 4) = 'O';
movb $117, hello + 4

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ exit(0);
mov $0, r0
sys exit


.data
hello: <hello\n>

実行結果

$ v6as write-6.s
$ mv a.out write-6.out
$ 7run write-6.out
hello
HEllo
HELLo
HELLO

相対アドレス

逆アセンブル結果を見ると、バイナリとアドレスに乖離があります。

000a: 15f7 4548 0030  mov $4548, 0040

バイナリを並べ直します。

000a: 15f7
000c: 4548
000e: 0030 → これが0040になる
0010: (次)

0030→0040となるのは、次のアドレスを基点とする相対アドレスだからです。

• 0010（基点） + 0030（相対アドレス） = 0040（絶対アドレス）

練習

【問8-1:5分】逆アセンブラを対応させてください。

⇒ 解答例 (F#)

【問8-2:10分】インタプリタを対応させてください。

⇒ 解答例 (F#)

引き算

引き算により小文字から大文字へ変換します。

write-7.s

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ *(uint16_t *)hello -= 0x2020;
sub $20040, hello

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ *(uint16_t *)(hello + 2) -= 0x2020;
sub $20040, hello + 2

/ write(1, hello, 6);
mov $1, r0
sys write
hello
6


/ exit(0);
mov $0, r0
sys exit


.data
hello: <hello\n>

実行結果

$ v6as write-7.s
$ mv a.out write-7.out
$ 7run write-7.out
hello
HEllo
HELLo

練習

【問9-1:5分】逆アセンブラを対応させてください。

⇒ 解答例 (F#)

【問9-2:15分】インタプリタを対応させてください。

⇒ 解答例 (F#)

仕様書

今まで推測していた仕様を仕様書で確認してください。

PDP-11/40 Processor Handbook (P.198～199)

• UNIXv6 ハードウェア資料

練習

仕様書を基に、今まで作った逆アセンブラとインタプリタをリファクタリングしてください。

テストコード集

自作インタプリタで順番に動作させてください。

1.c

main() {
    write(1, "hello\n", 6);
}

2.c

main() {
    putchar('a');
}

3.c

main() {
    printf("hello\n");
}

4.c

main() {
    int a;
    a = 1234;
    printf("a=%d\n", a);
}

5.c

main(argc, argv) char **argv; {
    int i;
    for(i = 0; i < argc; i++)
        printf("argv[%d]=%s\n", i, argv[i]);
}

6.c

main() {
    printo(012345);
}

printo(v) {
    int i;
    putchar(v < 0 ? '1' : '0');
    for (i = 0; i < 5; i++) {
        putchar(((v >> 12) & 7) + '0');
        v =<< 3;
    }
}

nm

既存のコマンドを自作インタプリタで動かしてみましょう。

# nm a.out

※ 2015年11月現在、達成者4名

cc

ccは内部で色々なものを呼んでいます。これらを自作インタプリタで順番に動かして、最終的にはccから一括で処理できることを目指してください。

• cc 1.c
  • /lib/c0 1.c /tmp/ctm1a /tmp/ctm2a
  • /lib/c1 /tmp/ctm1a /tmp/ctm2a /tmp/ctm3a
  • /bin/as - /tmp/ctm3a
    • /lib/as2 /tmp/atm1a /tmp/atm2a /tmp/atm3a -g
  • /bin/ld -X /lib/crt0.o test.o -lc –l

自作インタプリタでccを読んでハローワールドのビルドを目指してください。

カーネルビルドへの道

ハローワールドがビルドできたら、以下の順にカーネルビルドを目指してください。

1. 他のテストコード（2.c～6.c）をビルドする
2. V6カーネルをビルドする
3. アセンブラをビルドする
4. コンパイラをビルドする
5. 3と4のセルフホスティングを確認する
6. セルフホスティングしたツールでカーネルをコンパイルする

ここまで出来れば、バイナリのトレース練習は終了です。

※ 2015年11月現在、達成者3名

次はUNIX V6そのものを動かすことに挑戦しましょう！

※ 2015年12月6日現在、達成者1名

TM11のブートローダ→dist.tapのブートローダプログラム→dist.tapをrk0に展開→rk0を起動デバイスにしてUnixv6を起動→dist.tapのsrcをrk1に展開→rk1を/usr/souceにマウント→カーネルコンパイルまでエミュレートできたよ！

— kano (@kanorimon) 2015, 12月 6

まとめていただきました .@7shi さんの「PDP-11エミュレータ実装への道」をお気に入りにしました。 https://t.co/y0Xe7ebIr3

— kano (@kanorimon) 2015, 12月 7