【低レイヤ入門】C言語で作る自作VMを少しOSらしくする: 入力バッファ処理をサブルーチンに分ける | UNIX Cafe

前回は、VM上で動く word-command.bin を追加しました。Enterまでの入力を memory[0x500] から保存し、help / quit と1 byteずつ比較するプログラムです。

help ならhelp用の文字列、quit なら終了メッセージ、それ以外なら Unknown command を表示します。

Command> Commands:
help: show help
quit: quit
CPU halted.

前回の命令列では、プロンプト表示の後に入力ループが続き、その後ろに文字列比較を並べていました。今回は、その入力部分を CALLI と RET で呼び出せる処理として分けます。

画面の表示は前回と同じです。今回確かめたいのは、入力ルーチンへ移動したあと、どのアドレスへ戻って help の比較を始めるかです。

Day 33: tools/write-word-command-subroutine-bin.c
        programs/word-command-subroutine.bin

今回の練習ノートとコードは、GitHubの handmade-vm-os に置いています。

今回の記事で扱う範囲

今回は、「1行入力の命令列を read_line というサブルーチンに分け、入力後に文字列比較へ戻るところ」までを扱います。

CALLI と RET はDay 20でVMに実装した命令です。今回は新しい命令やsyscallを追加せず、既存の命令をVM上のプログラムから使います。notes/vm.c も変更しません。

入力された文字列を help / quit と比較する部分も、前回と同じ形です。文字列比較処理そのものの整理は次回に回します。

main
  プロンプトを表示
  CALLI read_line
  help / quit と比較
  結果を表示して HALT

read_line
  1行を memory[0x500] から保存
  末尾に 0x00 を書く
  RET

まずmonitorから手で動かす

最初に、変更後も前回と同じ結果が表示されることを確認します。リポジトリのルートで make を実行し、VM本体と外部バイナリを用意します。

make

引数なしでVMを起動すると、host 側 monitorの > プロンプトが表示されます。

./handmade-vm

そこへ programs/word-command-subroutine.bin を入力して起動します。次に、VM上のプログラムが表示する Command> に help と入力します。

Welcome to Handmade VM
>programs/word-command-subroutine.bin
Command> help
Commands:
help: show help
quit: quit
CPU halted.
>quit
Goodbye from Handmade VM

ここには2種類のプロンプトがあります。> はhost 側 monitor、Command> はVM上の word-command-subroutine.bin が表示しています。Command> help の help はVM上の入力ルーチンが読み、最後の >quit はhost 側 monitorを終了します。

CPU halted. の後、外部プログラムの実行が終わってmonitorへ戻ります。この見た目は前回の word-command.bin と同じです。ここから、内部で進んだ命令の順番を見ていきます。

前回の入力ループをどこへ移すか

Day 32のプログラムでは、プロンプトを表示すると、そのまま入力ループへ進んでいました。Enterが来たら0終端を書き、その次に help の比較を始めます。

Day 32:
  プロンプト表示
  入力ループ
  0終端を書き込む
  help比較 → quit比較 → 結果表示

Day 33では、プロンプト表示の直後に CALLI read_line を置きます。入力ループを含む read_line は、結果表示用の命令列より後ろに置きます。

Day 33:
  プロンプト表示
  CALLI read_line ───────────────┐
  help比較 ←──── RET ────────────┘
  quit比較
  結果表示 → HALT

  read_line:
    入力ループ
    0終端を書き込む
    RET

この図の read_line は、生成された .bin の中でVMが実行する命令列です。一方、tools/write-word-command-subroutine-bin.c は、その命令列を生成するhost 側のCプログラムです。どちらの側で動く処理かを分けておきます。

仕様カードと呼び出しの約束

word-command-subroutine.bin は新しいVM命令ではなく、既存の命令を組み合わせたサンプルプログラムです。今回注目する仕様を短くまとめます。

名前: word-command-subroutine.bin
分類: sample program
目的: 1行入力をサブルーチンで読み、戻ってからコマンドを比較する
使う主な命令: CALLI, RET, SYSCALL 2, STB, LDB, CMP, JZ, JNZ
入力先: memory[0x500] から最大63 byte + 終端0 byte
使用レジスタ: R0, R1, R2 は入力ルーチン内で変更する
PCの変化: CALLIでread_lineへ移動し、RETでCALLIの次へ戻る
SPの変化: CALLIで4減り、RETで4戻る
成功条件: help / quit / その他の出力がDay 32と一致する

サブルーチンから返すものは、レジスタの値ではなく memory[0x500] に保存した0終端文字列です。R0、R1、R2 は入力中に変わるため、呼び出し側は戻った後でバッファを読み直します。

host標準入力が途中でEOFになった場合は、既存の SYSCALL 2 が input EOF を表示してVMを停止します。その場合は、入力ルーチンの RET まで進みません。

CALLIは「どこへ戻るか」も保存する

生成された word-command-subroutine.bin の先頭は、次の命令列です。1命令は4 byteです。

0x000: 40 00 03 00   MOVI R0, 0x300
0x004: 60 00 00 01   SYSCALL 1
0x008: 69 00 01 00   CALLI 0x100
0x00C: 40 10 05 00   MOVI R1, 0x500  ← help比較の開始

0x300 には Command> の0終端文字列があります。最初の2命令がそれを表示し、0x008 の CALLI 0x100 が入力ルーチンへ進みます。

69 00 01 00 を32bitの命令として読むと 0x69000100 です。decode すると type = 6、op = 9、imm = 0x100 になります。imm は、この命令が移動する先のアドレスです。

VMは命令を fetch した時点で PC を4増やします。したがって、0x008 にある CALLI を読んだ直後の PC は 0x00C です。この 0x00C が、入力が終わった後に戻る場所になります。

CALLIの場所:       0x008
fetch後のPC:       0x00C  ← 戻り先
CALLIの移動先:     0x100  ← read_line

戻り先はスタックの4 byteへ入る

戻り先の 0x00C を保存する場所がスタックです。SP は、その現在位置を指す値です。このVMでは初期状態の SP は 0x00100000 です。CALLI はまず SP を4減らし、そこへ戻り先の PC をbig-endianの4 byteで書き込みます。

CALLI前: SP = 0x00100000
CALLI後: SP = 0x000FFFFC

memory[0x000FFFFC] = 0x00
memory[0x000FFFFD] = 0x00
memory[0x000FFFFE] = 0x00
memory[0x000FFFFF] = 0x0C

PC = 0x00000100

ここでスタックに保存したのは文字の h ではありません。保存した値は、入力ルーチンから戻るための命令アドレス 0x00C です。入力文字は別の領域、memory[0x500] から保存します。

VM本体の CALLI 実行部分でも、この順番になっています。

vm->sp -= 4;
write_u32_be(vm->memory, vm->sp, vm->pc);
vm->pc = inst.imm;

vm->pc には、すでに fetch 後の 0x00C が入っています。それを保存した後、inst.imm の 0x100 へ移動します。入力文字の保存と戻り先の保存は、目的もメモリ上の場所も違います。

read_lineで1行を0終端文字列にする

PC = 0x100 になると、入力ルーチンの先頭から実行します。最初に R1 へ入力バッファの先頭アドレス 0x500 を入れます。SYSCALL 2 はhost標準入力から1 byte読み、その値を R0 へ入れます。

次は処理の形が分かるようにラベルを付けた説明用の表記です。現在の small-asm がこのまま組み立てるコードではありません。実際の .bin は後で見るwriterが生成します。

read_line:
    MOVI R1, 0x500
read_loop:
    SYSCALL 2
    MOVI R2, 10
    CMP R0, R2
    JZ finish_input
    MOVI R2, 13
    CMP R0, R2
    JZ finish_input
    STB [R1], R0
    INC R1
    MOVI R2, 0x53F
    CMP R1, R2
    JZ finish_input
    JUMP read_loop
finish_input:
    MOVI R0, 0
    STB [R1], R0
    RET

10 はLF、13 はCRです。どちらかを読んだ場合は、その文字を保存せず finish_input へ進みます。通常の文字なら STB [R1], R0 で現在のアドレスへ保存し、INC R1 で次の書き込み位置へ進みます。

例えば help とEnterを入力した場合、4文字を保存した後の R1 は 0x504 です。Enterを読んだときは finish_input へ進み、その 0x504 に 0x00 を書きます。

memory[0x500] = 'h'
memory[0x501] = 'e'
memory[0x502] = 'l'
memory[0x503] = 'p'
memory[0x504] = 0x00

入力は最大63 byteです。63 byteを保存すると R1 = 0x53F になり、そこへ終端の0を書いて戻ります。LFやCRで早く終わった場合、0を書き込む場所は入力した長さに応じて変わります。

RETでhelpの比較へ戻る

入力ルーチンの最後には RET があります。生成されたプログラムでは RET は 0x140 に置かれ、命令コードは 02 00 00 00 です。

RET は、現在の SP = 0x000FFFFC が指す4 byteから、先ほど保存した 0x0000000C を読みます。SP を4戻してから、読み出した値を PC に入れます。

RET直前:
  SP = 0x000FFFFC
  memory[SP..SP+3] = 00 00 00 0C

RET後:
  SP = 0x00100000
  PC = 0x0000000C

VM本体側の処理は、要点だけ抜き出すと次の形です。

uint32_t return_address = read_u32_be(vm->memory, vm->sp);
vm->sp += 4;
vm->pc = return_address;

実際のVMは、この代入前に戻り先の範囲も確認します。ここで見るポイントは、CALLI が保存した値を RET が取り出し、PC に戻していることです。

0x00C からは MOVI R1, 0x500 が始まります。これは help と比較するため、入力バッファの先頭を指す命令です。次に LDB で1 byte読み、h と比較します。

0x00C: MOVI R1, 0x500
0x010: LDB R0, [R1]
0x014: MOVI R2, 104  ('h')
0x018: CMP R0, R2
0x01C: JNZ compare_quit

help でなければ quit と比較し、どちらでもなければunknown用文字列を表示します。前回と同じく末尾の 0x00 まで比較するため、helpful は help に一致しません。

read_lineをHALTの後ろへ置く

writerは、help、quit、unknownの表示処理と HALT を並べ、その後に read_line を置きます。

main側:
  CALLI read_line
  help比較 → help表示 → HALT
  quit比較 → quit表示 → HALT
  その他 → unknown表示 → HALT

0x100から:
  read_line → RET

結果表示へ進んだときは、各 HALT でプログラムが停止します。そのまま下へ進んで read_line をもう一度実行することはありません。入力ルーチンへ入る経路は、先頭の CALLI です。

命令列より後ろの 0x300、0x340、0x3A0、0x3E0 には表示用の0終端文字列を配置しています。writerは命令列が最初の文字列の位置 0x300 へ重ならないかも確認します。

writerでCALLIの行き先を埋める

tools/write-word-command-subroutine-bin.c は、VMで実行する命令を配列へ積み、後からジャンプ先を埋めてバイナリを生成します。CALLI の行き先も、同じ方法で決めます。

先頭付近では、CALLI の命令を置く位置だけを確保します。この時点では read_line の開始アドレスがまだ決まっていません。

size_t call_read_line = emit_jump_placeholder(program, &count, 0x69000000);

help、quit、unknownの命令列を書いたあと、今の命令数から read_line の開始アドレスを求めます。

uint32_t read_line = address_of(count);

最後に、先ほど確保した CALLI の即値部分へ開始アドレスを入れます。

patch_jump(program, call_read_line, 0x69000000, read_line);

今回のバイナリでは read_line = 0x100 となるため、先頭の CALLI は 0x69000100 になります。先頭の 0x69 は type = 6 と op = 9、下位20 bitの 0x100 は移動先アドレスです。これはwriterが生成したVM命令の値であり、host 側のC関数呼び出しではありません。

自動確認と境界の確認

手で help の流れを確認した後は、Makefileのターゲットで3つの分岐をまとめて実行できます。

make test-word-command-subroutine

ターゲットは help、quit、hello を順に標準入力へ渡します。Makefileの中心部分は次の形です。

test-word-command-subroutine: $(VM) programs/word-command-subroutine.bin
	printf 'help\n' | ./$(VM) programs/word-command-subroutine.bin
	printf 'quit\n' | ./$(VM) programs/word-command-subroutine.bin
	printf 'hello\n' | ./$(VM) programs/word-command-subroutine.bin

pipeで入力した文字は端末側でechoされません。そのため、VMの出力部分では Command> help ではなく、Command> Commands: のようにプロンプトと結果が続きます。make が表示する実行コマンドは、次の例から省いています。

Command> Commands:
help: show help
quit: quit
CPU halted.
Command> Goodbye from Handmade VM
CPU halted.
Command> Unknown command
CPU halted.

完全一致と入力長の境界も見ておきます。例えば helpful は先頭が help でも、5文字目が0ではないためunknownになります。空行もunknownです。

printf 'helpful\n' | ./handmade-vm programs/word-command-subroutine.bin
printf '\n' | ./handmade-vm programs/word-command-subroutine.bin

これらは make test-word-command-subroutine には含まれません。63 byteの上限は、63文字を保存した時点で終端の0を書き、64文字目を読まない形です。Enterまで必ず読み切る行編集には、まだ進んでいません。

今回分かったこと

今回は、VM上の1行入力を read_line として分け、CALLI / RET で呼び出す形にしました。

• CALLI は戻り先 0x00C をスタックへ保存して 0x100 へ進みます
• RET は保存された値を PC へ戻し、help の比較を再開します
• 入力文字は memory[0x500] から保存し、戻り先アドレスはスタックへ保存します
• 戻った後はレジスタの値に頼らず、0終端の入力バッファを読み直します
• 新しいVM命令を追加せず、前回と同じ help / quit / unknown の結果を表示できます

入力部分はサブルーチンになりましたが、固定文字列の比較はまだ文字ごとの命令列を並べています。次回は、この比較処理を整理するところへ進みます。