【低レイヤ入門】C言語で作る自作VMを少しOSらしくする: メモリに1行を保持して置き換える | UNIX Cafe

自作VM開発記 22

この連載では、C言語で小さなVM（仮想マシン）を作っています。VMは、独自に決めた命令を読み取り、レジスタやメモリを動かします。その上で動くプログラムも自分で書き、入力したコマンドに反応するところまで進めてきました。

前回は、echo helloという1行をコマンド名と本文へ分けました。本文の先頭アドレスをレジスタに残しておけば、同じ行の文章を表示できます。ただし、表示後に次のコマンドを入力すると、入力用のメモリは新しい内容で上書きされます。

今回は、その入力とは別の場所に1行を保持します。set helloで内容を置き、あとからshowで取り出して表示します。別のコマンドを間に挟んでも残り、set worldで全体を置き換えられることが目標です。開発手順ではDay 42、第22回にあたります。

変更するのはVM上のプログラムです。programs/line-editor.asmを新しく用意し、既存の命令で入力バッファから編集バッファへコピーします。ファイルへ保存する仕組みはまだ持たず、まずメモリ上で1行の内容を管理するところから始めます。

まず、置いた1行をあとから表示する

プロジェクトのMakefileがあるディレクトリで、次のコマンドを実行します。Cコンパイラとmakeが必要です。後半の自動テストにはPython 3も使います。small-asmはアセンブリの命令名やラベルを、VMが読み取るバイト列へ変換する道具です。

make run-line-editor

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

VMとsmall-asmを用意し、programs/line-editor.asmを.binへ変換して起動します。Command>に、次の画面例のとおり入力してEnterを押してください。プロンプト自体を入力する必要はありません。

Command> set hello
Command> show
hello
Command> set world
Command> show
world
Command> quit
Goodbye from Handmade VM
CPU halted.

setの直後には完了メッセージを出さず、次のCommand>へ戻ります。showでは、その時点の内容と改行を表示します。画面例には端末が表示する入力文字も含めています。VMが入力文字を自動で出力しているわけではありません。

次は、set helloのあとでecho other、help、showを試してみてください。echoのotherやhelpの案内を表示したあとも、showの結果はhelloです。今回確かめたいのは、入力し直しても保持した内容が消えないことです。

引数なしの./handmade-vmを使う場合は、host側monitorの>へprograms/line-editor.binを入力します。Command>でquitすると実行中のVMが停止し、monitorへ戻ります。そこでもう一度起動すると、保持内容は空から始まります。

操作と空内容の扱いを先に決める

最初の行編集では、内容全体の置換と表示に操作を絞ります。文字の途中へ挿入したり、カーソルを動かしたりする機能はありません。操作名と入力の扱いは、次の仕様で揃えています。

set hello     本文helloで保持内容を置換する
set           Text>で次の1行を読み、その内容で置換する
set＋半角空白  空内容へ置換する（次の行は読まない）
show          保持内容とLFを表示する
quit          保存せず終了する

set単独の次に入力する1行は、そのまま編集内容として扱います。たとえばquitという文字をその行へ入力しても、終了コマンドにはなりません。あとからshowでquitと表示できます。コマンドとして読む段階と、本文として読む段階を分けているためです。

初期状態は空内容です。起動直後のshowは改行だけを表示します。空に戻したい場合は、setの後ろへ半角空白を付けてEnterを押すか、set単独の次のText>で何も入力せずEnterを押します。空であることも、保持できる内容の1つにします。

同じ行から指定する場合は、前回の分割規則を使います。先頭とコマンド直後の半角空白は読み飛ばし、本文中と末尾の空白は保持します。一方、Text>で読む行は分割しないので、先頭空白もそのまま残ります。

showは引数を必要としません。show xはUnknown commandとして扱い、保持内容を変えずに再入力へ戻します。末尾が半角空白だけのshow は受け付けます。helpとquitも同じ引数の規則を使い、echoの動作は前回から引き継ぎます。

入力バッファと編集バッファを分ける

バッファは、処理するデータを置いておくメモリ領域です。前回までの入力バッファは、コマンドを読むたびに使い直していました。今回の編集内容は、次のコマンドを入力しても必要になるので、別の領域へ移します。

0x000〜0x33B  命令と表示・比較用の文字列
0x500〜0x53F  入力バッファ（63 byte＋終端0）
0x600〜0x63F  編集バッファ（63 byte＋終端0）
高位メモリ     CALLIが使う戻り先スタック

アドレスはメモリ上の位置を表す番号です。0xで始まる数は16進数で、0x600は編集バッファの先頭です。今回は命令と文字列を0から連続配置し、その終わりが入力バッファの0x500より手前にあることを確認します。

起動時には、編集バッファの先頭へ0を書きます。0終端文字列は、先頭から最初の0までを文字として扱う形式です。先頭に0があれば、長さ0の空文字列になります。64 byte全部を消さなくても、文字列として空の状態を作れます。

    MOVI R5, 0x600
    MOVI R0, 0
    STB [R5], R0

MOVIはレジスタへ数値を入れる命令です。R5には書き込み先のアドレス、R0には書き込む値0が入ります。STBはR5が指すメモリへ、R0の下位8 bitを1 byteとして書き込みます。角括弧は、そのレジスタの中の数値をアドレスとして使うことを表します。

今回のVMは起動時にメモリを0で初期化していますが、プログラム側にも初期状態を作る命令を置きます。以後の処理が前提にする「編集内容は最初は空」という約束を、ソースの入口で読めるようにします。

本文のアドレスを覚えるだけでは残らない

前回のsplit_lineは、入力中の最初の区切りを0へ置き換え、本文の先頭をR6へ返しました。今回もこの処理を使います。set helloを分けた直後の入力バッファは、次のようになります。

アドレス  500 501 502 503 504 505 506 507 508 509
内容       s   e   t   0   h   e   l   l   o   0
                           ↑
                      R6 = 0x504
R7 = 1（区切りあり）

R6が覚えているのはhelloそのものではなく、hが置かれている位置です。このまま次のshowを入力すると、同じ0x500からs、h、o、w、0が書かれます。R6を保存しておくだけでは、元のhelloを後から読むことはできません。

そこで、次の入力へ戻る前に本文のbyteを0x600へ移します。元の場所を指すレジスタと、コピー先を指すレジスタを別々に持ち、1 byteずつ読み書きします。コピー後は、入力バッファの用途が変わっても編集バッファの文字列を読めます。

同じ行の本文か、次の行の本文かで違うのはコピー元の先頭です。区切りがある場合はsplit_lineのR6を使い、set単独ならread_lineの完了後にR6を0x500へ設定します。どちらも最後は同じcopy_lineへ渡します。

do_set:
    MOVI R3, 0
    CMP R7, R3
    JNZ store_line
    MOVI R0, text_prompt
    SYSCALL 1
    CALLI read_line
    MOVI R6, 0x500
store_line:
    CALLI copy_line
    JUMP command_loop

ここからのコードは実ソースの抜粋です。抜粋だけをファイルへ貼るのではなく、実行にはline-editor.asm全体を使ってください。R7は区切りがあれば1、なければ0です。CMPとJNZにより、区切りがあれば追加の入力を待たずstore_lineへ進みます。

区切りがない場合はText>を表示してread_lineを呼びます。read_lineがLFまで読み終わったあと、R6を入力バッファの先頭へ設定します。この経路では本文をコマンド名と分割しません。先頭の空白も含め、入力した1行がコピー対象です。

終端0もコピーしてから戻る

コピー処理では、R6を読み出し元、R5を書き込み先、R0を一時的な1 byteの置き場にします。R3には比較用の0を置きます。どの値がアドレスで、どの値が文字なのかを分けて見ると、短いループとして追えます。

copy_line:
    MOVI R5, 0x600
    MOVI R3, 0
copy_byte:
    LDB R0, [R6]
    STB [R5], R0
    CMP R0, R3
    JZ copy_done
    INC R6
    INC R5
    JUMP copy_byte
copy_done:
    RET

; end_copy_line

最初のLDBは、R6が指すメモリから1 byteを読み、R0へ入れます。続くSTBが、そのR0をR5の指すメモリへ書きます。そのあとでR0と0を比較し、0ならcopy_doneへ分岐します。文字が残っていれば両方のアドレスを1ずつ増やし、次のbyteへ進みます。

set helloなら、最初はR6=0x504、R5=0x600です。hを読み書きしたあと、両方が1増えます。helloの5文字をコピーすると、R6=0x509、R5=0x605になります。ここで入力側の0を編集側にも書き、両方のレジスタがその0を指した状態でRETします。

コピー後の編集バッファ
0x600  0x601  0x602  0x603  0x604  0x605
  h      e      l      l      o      0
                                    ↑
                               R5 = 0x605

大切なのは、終端判定より先にSTBしていることです。もし0を見つけた時点で書き込まずに戻ると、新しい文字列の終わりがコピー先にできません。特に、以前の内容より短く置換したときに、古い末尾が見えてしまいます。

たとえばabcdefを保持したあとxへ置換すると、メモリにはx、0、c、d、e、f、0が残ります。文字列として読む範囲は最初の0までなので、showはxだけを表示します。古いbyteをすべて消す処理は、今回の文字列の置換には必要ありません。

空内容のコピーでも同じループを使えます。最初に読むbyteが0なので、0x600へ0を書き、そのまま戻ります。文字が0個でも「終端0を1個書く」という仕事があることを、通常のコピーと同じ順番で確かめられます。

copy_lineはR0、R3、R5、R6とzero flagを書き換えます。R1、R2、R4、R7は保持します。呼び出す側は、63 byte以内に終端0がある入力を渡します。この部品自身に、任意の長さのデータを受け取って切り詰める機能は付けていません。

命令値、PC、SPからコピーを追う

LDBやSTBという名前は、small-asmによって32 bitの命令値へ変換されます。今回のLDB R0, [R6]は0x30060000、STB [R5], R0は0x31500000です。VMは命令値を分解し、どのレジスタを使うか決めます。

LDBではtype=3、op=0、rd=0、rs=6です。rdとrsは命令内のレジスタ番号の欄です。LDBの処理はrsで指定されたR6からアドレスを取り、そこのメモリを読み、rdで指定されたR0へ値を入れます。Cコードの代入部分だけを抜き出すと、次の形です。

vm->regs[inst.rd] = vm->memory[vm->regs[inst.rs]];

STBはtype=3、op=1、rd=5、rs=0です。こちらではrdが書き込み先のアドレスを持つレジスタ、rsが書き込む値を持つレジスタです。実際のVMはレジスタ番号とアドレスの範囲を検査してから、この代入を実行します。

vm->memory[vm->regs[inst.rd]] = vm->regs[inst.rs] & 0xFF;

アセンブリの角括弧の役割を、Cの配列アクセスまでつなげて見ることができます。0x600という数値をレジスタへ入れることと、memory[0x600]へ文字を書き込むことは別の操作です。前者で場所を指定し、後者でその場所の中身を変えます。

PCは次に読む命令の位置です。今回のstore_lineは0xB0にあり、そこにCALLIがあります。命令の読み取りでPCが4増えたあとの0xB4を戻り先として積み、copy_lineの0x12Cへ移ります。RETで0xB4へ戻ると、command_loopへのJUMPを実行します。

SPはスタックの位置です。初期値0x100000からCALLIで4減って0xFFFFCになり、RETで元へ戻ります。今回はcopy_lineの中から別のサブルーチンを呼ばないので、戻り先は1つだけです。文字列は低い位置のバッファ、戻り先は高い位置のスタックにあり、役割も場所も分かれています。

表示は編集バッファを指定する

showでは、入力バッファではなく編集バッファの先頭をSYSCALL 1へ渡します。このsyscallはR0を文字列のアドレスとして受け取り、最初の0までを表示します。0自体は表示しません。

do_show:
    MOVI R0, 0x600
    SYSCALL 1
    JUMP print_newline

文字列の末尾にはLFを保存していないので、表示後に改行を付けます。既存のprint_newlineへJUMPし、R0=10のSYSCALL 3でLFを1 byte出してからCommand>へ戻ります。空文字列なら文字の出力が0個で、LFだけが表示されます。

ここはCALLIではなくJUMPです。print_newlineはRETで戻る処理ではなく、最後にcommand_loopへ移る共通の経路です。戻り先が必要なcopy_lineと、次の入力へ進む表示経路を、PCの動きで区別して読めます。

63 byteは文字数ではなく入力全体の上限

入力バッファも編集バッファも64 byteですが、そのうち1 byteは終端0に使います。保存できるデータは最大63 byteです。同じ行にset と書くと4 byteを使うため、その後ろの本文は最大59 byteになります。先頭空白や余分な区切りも入力上限に含まれます。

63 byteの本文を保持したい場合は、set単独で次の1行を読みます。この経路ならコマンド名の分が不要です。最大長の内容をコピーしたとき、最後の文字は0x63E、終端0は0x63Fに入り、次の0x640には書き込みません。

上限を超えた入力は、前回までのread_lineと同じくLFまで消費します。切り詰めた残りが次のコマンドになることはありません。CRは行中でも無視し、LFで確定します。CRLFの入力に対応しますが、CRだけでは確定しません。

入力途中でEOFになると、既存のSYSCALL 2がinput EOFを表示してVMを停止します。read_lineから戻らないため、未完の本文をcopy_lineへ渡しません。quitでもEOFでもファイル保存は行わず、次の起動は空内容から始まります。

NULという値0のbyteが入力された場合、入力自体はLFまで消費しますが、コピーと表示は最初の0までです。UTF-8もbyte列として扱うため、日本語の1文字が複数byteなら上限で途中までになる場合があります。今回は文字単位の長さや文字境界の調整を追加していません。

コピー部品とコマンド全体を確認する

まず、実ソースからcopy_lineを取り出して、小さなVMプログラムに組み込んで動かします。テスト用の命令列は0x800から置き、入力と編集のバッファへ既知のbyteを書きます。呼び出し後にメモリとレジスタを期待値へ照合するPythonのテストです。

make test-line-copy
make test-line-editor

部品テストは8ケースです。通常の文字列、空、63 byte、長い内容から短い内容への置換、空への置換、途中のNUL、本文先頭の位置が違う場合を確認します。コピー元が変わらないこと、編集バッファ前後の目印byteが壊れないことも検査します。

次に、生成したline-editor.binをVMで実行し、入力に対する出力全体を比較します。終了コードが0で標準エラーが空であることも含め、75ケースが通過しました。通常操作のほか、echo後の保持、引数拒否、空白、上限、CRLF、EOF、NUL、UTF-8を含みます。

反復では、長い内容を置く、短く置換する、表示する、空にする、表示するという操作列を1000回繰り返します。monitorのテストでは同じプログラムを2回起動し、1回目の内容が次のVMに残らないことと、停止後にmonitorへ戻ることを確認します。

生成物は147命令588 byteと10個の文字列240 byteで、合計828 byteです。末尾の次は0x33Cなので、入力バッファの0x500には届きません。入出力テストでもサイズを検査し、今後ソースが大きくなって配置が重なった場合に気付けるようにしています。

Day 41の分割14ケースと入出力74ケースも通過しました。small-asmの既存テスト、旧echoの入出力も維持しています。今回追加したのはVM上のプログラムとそのテストであり、VM本体やassemblerへ命令を追加する必要はありませんでした。

今回分かったことと、次に進むこと

今回は、入力するための領域と、あとから使う内容を保持する領域を分けました。アドレスを覚えるだけでは入力の上書きを防げず、必要なbyteを別の場所へ移す必要があります。その小さなコピーも、読む、書く、終端を比較する、位置を進めるという既存命令の組み合わせで作れます。

置換の中心は終端0です。文字数を別に管理しなくても、新しい終端までを有効内容として読めば、短い内容や空へ変更できます。どの範囲を文字列として扱うのかを、メモリとポインタの両方から追えるようになりました。

次の候補は、保持した1行を保存し、読み戻すための仕様決めです。hostのファイルを使うか、仮想ディスクを用意するか、失敗をどう返すかを先に決めます。保存は今回のメモリ上の置換とは別の機能として進めます。