512バイトに入らなくなる — メモリ管理とマルチタスク

メモリ管理とマルチタスク。メモリのブロックとチップ、二つの作業を切り替える時計。

512バイトに収まらなくなったら、カーネルを分けて読み込みます。メモリ管理とマルチタスクを実装します。

前回: 正規表現が固まる理由 — エンジンを100行で自作する

これは【番外編】です。 このサイトの本筋は roadmap.sh に沿った第0〜第8段階で、OS自作はそこに載っていません。 読まなくても順路は繋がります。飛ばして構いません。 それでも続きを書いているのは、malloc と「プロセス」の底が、この回で完全に見えるからです。前回は「Ctrl + C が無い」で終わりました。今回は「メモリを配る人」と「処理を切り替える人」を、自分で作ります。 前提: 自作OSでプロテクトモードへ移行する|BIOS出力が使えなくなる理由を先に読んでください。 ~/osdev/boot.asm が手元にあり、QEMU で 32bit protected mode. press keys: が出た状態から続けます。道具(NASM / QEMU / xxd)も、ビルドの仕方も、前回・前々回のまま変えません。新しい道具は1つも入れません。

前回、512バイトの中に、これだけ詰め込みました。

  • GDT(セグメントの表)
  • A20ラインを開ける処理
  • プロテクトモードへの移行
  • IDT(割り込みの表)を作る処理
  • PICのリマップ
  • キーボードの割り込みハンドラと、58バイトの変換表

そして、まだ余っていました。 NASM は何も文句を言いませんでした。

今回やりたいのは、この3つです。

やりたいこと必要なもの
メモリマップを取るBIOSを呼ぶ処理 + 結果を表示する処理
malloc を作る確保・解放・空きブロックを探す処理
マルチタスクタイマの設定 + レジスタ退避・復元 + タスクごとのスタック

書き始めて、すぐ止まります。

boot.asm:212: error: TIMES value -418 is negative

418バイト足りません。 これは削って何とかなる量ではありません。

512バイトの壁に、ここで本当にぶつかります。

そして、この壁の越え方は、40年前から1つに決まっています。

ブートセクタには「本体を読み込む処理」だけを書く。本体は別のファイルにして、ディスクの2セクタ目から置く。

これが「ブートローダ」と「カーネル」が別物である理由です。 GRUB も、Windows の起動も、全部この形です。512バイトに入らないから、2段階になっています。

この回でやるのは、その2段階への移行と、移行して初めて書けるようになる3つです。

対象レベル: 中級 / 区分: 必要に応じて読む

目次

この記事でわかること

  • ブートローダとカーネルが別ファイルなのは、設計思想ではなく「512バイトに入らないから」だということ
  • ディスクを読むBIOSの機能は、プロテクトモードに移ると使えなくなること。だから読み込みはリアルモードのうちに済ませる
  • ディスク読み込みは、失敗しても何も言わずに次へ進むこと。キャリーフラグを自分で見ないと気づけない
  • 「メモリが何GBあるか」は、CPUに聞いても分からないこと。BIOSに聞く(int 0x15, eax=0xE820)しかない
  • malloc の一番素朴な形は5行で書けること。そしてそれが使い物にならない理由(解放できない)
  • フリーリストにすると解放できるが、今度は断片化すること。空きが128バイトあるのに128バイト取れない、が実際に起きる
  • ページングが「なぜプロセスごとに同じアドレスを使えるのか」の答えだということ
  • 「マルチタスク」の正体は、タイマ割り込みで esp を差し替えているだけだということ

この記事でやること

  1. boot.asm を「読み込み係」に作り直し、kernel.asm を新しく書く(2段階ローダ)
  2. int 0x13 でカーネルをディスクから読み込み、キャリーフラグで成否を確認する
  3. int 0x15, eax=0xE820 でメモリマップを取り、画面に一覧を出す
  4. バンプアロケータ → フリーリスト の順に malloc を作り、断片化を画面で見る
  5. PIT(タイマ)を設定し、コンテキストスイッチを書いて、2つのカウンタが同時に増えるのを見る
  6. QEMU を終了し、後片づけをする

先に知る言葉

この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。

言葉意味
2段階ローダブートセクタが「本体を読み込むだけ」に徹し、本体(カーネル)を別ファイルにする構成。512バイト制限の回避策
セクタディスクの最小の読み書き単位。512バイト。ブートセクタは1セクタ目
CHSシリンダ・ヘッド・セクタ。円盤の物理的な位置でディスクの場所を指す、古い指定方法。int 0x13 の基本形はこれ
キャリーフラグCPUのフラグの1つ。BIOSの機能は、失敗するとこれを1にして戻ってくる。jc 命令で分岐できる
メモリマップ物理メモリのどこが使えて、どこが使えないかの一覧。連続した1本の領域ではない
E820int 0x15 に eax = 0xE820 を渡してメモリマップを1件ずつ取るBIOSの機能。名前は番号そのまま
ヒーププログラムが実行中に「ここから好きに使っていい」とされたメモリ領域。malloc が配るのはここ
アロケータヒープから「この分ください」に応えて番地を返す仕組み。malloc の中身
バンプアロケータ先頭から順に配るだけの、いちばん素朴なアロケータ。解放できない
フリーリスト空いているブロックを繋いで管理する方式。解放できるようになる。malloc の実装の基本形
断片化空きの合計は足りているのに、連続した空きが足りなくて確保できない状態
物理アドレスメモリチップ上の、本当の番地
仮想アドレスプログラムから見える番地。物理アドレスとは別物で、変換表を通して繋がる
ページング仮想アドレスを物理アドレスに変換する仕組み。4KBごとの「ページ」単位で対応表を持つ
PITProgrammable Interval Timer。一定間隔で割り込みを上げてくれるチップ。IRQ0
コンテキストスイッチいま動いている処理のレジスタを退避し、別の処理のレジスタを復元して、そちらに切り替えること
タスクここでは「切り替えの単位」。独立したスタックと、独立したレジスタの組を持つ処理の流れ

なぜ2段階なのか

ブートセクタが「読むだけ」になる理由

前々回のブートセクタの回で、BIOSがやることを1行で書きました。

ディスクの先頭512バイトを 0x7C00 に読み込んで、そこへジャンプする。以上。

BIOSはファイルシステムを読めません。 だから「512バイトの1セクタだけ」という、いちばん単純な取り方をします。この512バイトは、増やせません。

では、その512バイトが最初にやるべきことは何か。

「続きをディスクから読み込むこと」です。

BIOSはファイルシステムを知りませんが、ブートセクタは「ディスクの何セクタ目を読め」とBIOSに頼めます。 だから、

段中身サイズ
1段目ブートセクタ。カーネルを読み込んで、そこへ飛ぶだけ512バイト固定
2段目カーネル。やりたいこと全部制限なし(読み込む分だけ)

この形にすると、512バイト制限は1段目にしか掛かりません。

GRUB がやっているのも、これの発展形です。 GRUB は 1段目でさらに「1.5段目」を読み、そこでファイルシステムを読めるようにしてから、ファイル名で Linux カーネルを読み込みます。段が増えているだけで、考え方は同じです。

順番の絶対条件 — BIOSが生きているうちに読む

ここが、前回の回収です。

前回、いちばん重要な1行として、こう書きました。

プロテクトモードに入った瞬間、int 0x10 は使えなくなります。

これは int 0x10(画面)だけの話ではありません。 int 0x13(ディスク)も、int 0x15(システム情報)も、BIOSの機能は全部同じです。

つまり、順番が完全に決まります。

順やることどのモードで
1カーネルをディスクから読み込む(int 0x13)リアルモード(BIOSが要る)
2メモリマップを取る(int 0x15)リアルモード(BIOSが要る)
3A20を開けるどちらでも
4GDTを登録して、プロテクトモードへ移るここで切り替わる
5カーネルへ飛ぶプロテクトモード

「BIOSに聞きたいことは、全部リアルモードのうちに聞いておく。」 これが、この回でいちばん実務的な教訓です。移行したあとで「メモリが何MBか知りたい」と思っても、もう聞く相手がいません。

だから本物のOSも、起動の初期にBIOS(UEFIなら別の窓口)から情報を吸い上げて、メモリ上に置いてから移行します。 Linux カーネルが起動時に持っている「boot params」という構造体は、まさにこれです。

カーネルを別ファイルにして、読み込む

まず、置き場所を決める

読み込む前に、「どこへ読み込むか」を決めないといけません。 そしてここは好きに決められません。

リアルモードで最初の1MBは、こういう地図になっています。

番地何があるか使えるか
0x00000 – 0x004FFIVT(割り込みベクタ)とBIOSのデータ領域触ってはいけない
0x00500 – 0x07BFF空き使える(約30KB)
0x07C00 – 0x07DFFブートセクタ(自分自身)使えない
0x07E00 – 0x9FBFF空き使える(約610KB)
0x9FC00 – 0x9FFFFEBDA(BIOSが拡張データを置く)触ってはいけない
0xA0000 – 0xBFFFFビデオメモリ(0xB8000 はこの中)画面用
0xC0000 – 0xFFFFFBIOSやカードのROM使えない
0x100000 以降拡張メモリ(1MBより上)A20を開ければ使える

この地図は、ほぼ全部「歴史」でできています。 0x9FC00 から先が使えないのも、0xB8000 が画面なのも、1981年に決められたものがそのまま残っているだけです。

今回はこう割り当てます。

番地用途
0x00500メモリマップの件数(2バイト)
0x00504 〜メモリマップの中身(1件24バイト)
0x01000カーネルの読み込み先(今回8KBまで)
0x09000 〜IDT(前回と同じ場所)
0x8F000タスクB用のスタックの底
0x90000タスクA用のスタックの底
0x100000ヒープの先頭(malloc が配る領域)

ヒープを 0x100000(=ちょうど1MB)に置いているのは、偶然ではありません。 ここは、A20ラインを開けないと触れない領域です。 前回「A20を開けないと1MB以上が使えない」と書きました。その「1MB以上」を、今回初めて実際に使います。 開け忘れると、0x100000 への書き込みが 0x000000 に化けて、IVTを書き潰して静かに死にます。 エラーは出ません。

int 0x13 — ディスクから読む

BIOSにディスクを読ませる呼び出しは、こうです。

    mov bx, 0x1000          ; es:bx = 読み込み先
    mov ah, 0x02            ; 機能番号: セクタを読む
    mov al, 16              ; 読むセクタ数
    mov ch, 0x00            ; シリンダ 0
    mov cl, 0x02            ; セクタ 2 から(1 は自分自身)
    mov dh, 0x00            ; ヘッド 0
    mov dl, [boot_drive]    ; どのドライブか
    int 0x13

1つずつ意味を潰します。

レジスタ入れるもの注意
ah0x02 = 「セクタを読む」0x03 は書き込み。打ち間違えると本当に書きます
al読むセクタ数1セクタ = 512バイト。 16なら8KB
ch / dh / clシリンダ / ヘッド / セクタ円盤の物理的な位置。 今のSSDに円盤はありませんが、この指定方法だけ残っています
dlドライブ番号これが今回いちばんの罠(次で説明)
es:bx読み込み先の番地セグメント:オフセット。es = 0、bx = 0x1000 なら 0x1000

cl が 2 から始まるのに注意してください。 セクタ番号だけ、1から数えます。 シリンダもヘッドも0から数えるのに、セクタだけ1始まりです。ブートセクタ自身が1セクタ目なので、続きは2セクタ目からです。 ここを 1 にすると、ブートセクタ自身をカーネルとして読み込んで実行します。 何が起きるかは、実際にやると分かります(無限に再起動します)。

dl は、書き換える前に保存する

ブートセクタに制御が渡った瞬間、dl には「どのドライブから読み込まれたか」の番号が入っています。 BIOSが親切に置いていってくれる、唯一の引数です。

dl の値意味
0x001台目のフロッピー
0x801台目のハードディスク(QEMU の -drive はこれ)
0x812台目のハードディスク

そして前回のコードは、いきなりこれを壊していました。

start:
    cli
    xor ax, ax
    mov ds, ax

この時点ではまだ dl は無事です。 問題は、このあと自分で mov dl, 0 などと書いてしまうことです。決め打ちで 0x80 を入れても、たまたま動いてしまいます。 そしてUSBから起動した瞬間に動かなくなります。

だから、いちばん最初に保存します。

    mov [boot_drive], dl

「たまたま動く」がいちばん厄介です。 dl を 0x80 決め打ちにしても、QEMU では動きます。動くので、間違っていることに気づけません。 気づくのは、環境を変えたときです。 「繋がらない」を4段階で切り分けるの回で「動いている理由を説明できないものは、動いていないのと同じ」と書きました。同じ話がここにもあります。

失敗しても、何も言わない

ここが、この記事で必ず踏む罠です。

int 0x13 は、読み込みに失敗しても、そのまま次の命令へ進みます。

例外も出ません。画面にも何も出ません。読み込み先のメモリは、BIOSが置いていったゴミのままです。 そこへジャンプすると、でたらめなバイト列を命令として実行して、再起動します。

成否は、自分で確かめるしかありません。

    int 0x13
    jc disk_error           ; キャリーフラグが立っていたら失敗
    cmp al, 16              ; 実際に読めたセクタ数
    jne disk_error
確認意味
jc(jump if carry)BIOSは失敗するとキャリーフラグを1にして戻る。 これが唯一の合図
cmp al, 16al には「実際に読めたセクタ数」が返る。 頼んだ数より少ないことがある

ah には、さらにエラーコードが入って返ります。

ah意味
0x01指定が不正(セクタ番号が0など)
0x04セクタが見つからない(イメージが小さすぎるとき)
0x20コントローラの故障
0x80タイムアウト(ドライブがない)

「戻り値を見ていないコード」は、低レイヤでは即死につながります。 普段書いているコードでも、fetch の結果を確かめずに使えばエラーになります。でもエラーメッセージは出ます。 ここでは出ません。 出るのは「再起動を繰り返す真っ黒な画面」だけです。だから jc を書くのは、丁寧さではなく必須です。

そして、この時点ならまだBIOSが生きています。 つまり int 0x10 でエラーメッセージを出せます。

disk_error:
    mov si, err_msg
.print:
    lodsb
    test al, al
    je .hang
    mov ah, 0x0e
    int 0x10
    jmp .print
.hang:
    cli
    hlt
    jmp .hang

エラー表示をリアルモードのうちに書いておくのには、理由があります。 プロテクトモードに移ったあとは int 0x10 が使えず、0xb8000 に自分で書くしかありません。 そのコードを書く前に落ちたら、何も表示できません。 「まだ道具がある段階で、失敗の報告手段を作っておく」 ——これは低レイヤに限った話ではありません。

メモリマップを取る — 実際にいくら積んでいるかはBIOSに聞く

CPUは、メモリの量を知らない

ここは、知ると少し驚くところです。

CPU には「搭載メモリ量を返す命令」がありません。

CPU から見えるのは「アドレス空間」だけで、その番地に本当にメモリチップが刺さっているかどうかは分かりません。 刺さっていない番地に書き込んでも、エラーにならず、読み返すとゴミが返るだけのこともあります。

では、誰が知っているのか。

BIOS(UEFIならファームウェア)です。 起動時にハードを点検するので、どこにメモリがあり、どこが装置に使われているかを知っています。

だから聞きます。 それが int 0x15, eax = 0xE820 です。

メモリは1本の連続した領域ではない

「8GB積んでいる」を、0x00000000 から 0x200000000 までが全部使える、と思っていると外れます。

実際に返ってくるのは、こういう「区間の一覧」です。

開始長さ種別
0x00000000000000000x000000000009FC001 = 使える
0x000000000009FC000x00000000000004002 = 予約(EBDA)
0x00000000000F00000x00000000000100002 = 予約(BIOS ROM)
0x00000000001000000x0000000007EE00001 = 使える
0x00000000FFFC00000x00000000000400002 = 予約

種別(type)の意味は決まっています。

type意味
1自由に使える
2予約済み。触ってはいけない
3ACPI のテーブル。読んだあとなら再利用してよい
4ACPI が使うので保存が必要
5壊れているメモリ

穴が空いています。 0x9FC00 から 0x100000 までは、メモリチップは刺さっているのに使えません。 装置のために予約されているからです。 0xFFFC0000 あたりにも区間があります。 これはメモリではなく、PCI装置がアドレス空間の一部を借りているものです。 「メモリマップ」とは、メモリの地図ではなく、アドレス空間の地図です。

E820 の呼び方

1回の呼び出しで1件返ります。 続きがあるかどうかは ebx で分かります。

レジスタ役割
eax0xE820 を入れる。返ってくるときは 'SMAP'(0x534D4150)になる
ebx「次はどこから」を覚えている値。 最初は0。0が返ってきたら終わり
ecx1件のサイズ。 24を入れる(20の環境もある)
edx'SMAP'(0x534D4150)を入れる。 合言葉
es:di結果を書き込む先

edx に文字列 SMAP を入れるのが、いかにも古い仕様です。「本当にこの機能を呼びたいのか」を確かめるための合言葉で、間違っていると失敗します。

実際のコードはこうなります。 1回目と2回目以降で少し形が違うので、そこだけ注意して読んでください。

do_e820:
    mov di, 0x0504          ; 結果の置き場所
    xor ebx, ebx            ; 最初は 0
    xor bp, bp              ; 件数のカウンタ
    mov edx, 0x534d4150     ; 'SMAP'
    mov eax, 0xe820
    mov dword [di + 20], 1  ; 24バイト目を 1 にしておく(後述)
    mov ecx, 24
    int 0x15
    jc .failed              ; 1回目で失敗=この機能が無い
    mov edx, 0x534d4150
    cmp eax, edx
    jne .failed
    test ebx, ebx
    je .failed
    jmp .check

.next:
    mov eax, 0xe820
    mov dword [di + 20], 1
    mov ecx, 24
    int 0x15
    jc .done                ; 2回目以降の失敗は「もう無い」の意味
    mov edx, 0x534d4150

.check:
    jcxz .skip              ; 長さ0で返ってきたら捨てる
    mov ecx, [di + 8]
    or ecx, [di + 12]
    jz .skip                ; 区間の長さが0なら捨てる
    inc bp
    add di, 24

.skip:
    test ebx, ebx
    jne .next               ; ebx が 0 でなければ続きがある

.done:
    mov [0x0500], bp        ; 件数を保存
    clc
    ret

.failed:
    stc
    ret

引っかかりやすい点を3つだけ。

点中身
mov dword [di + 20], 124バイト目は「ACPI拡張属性」で、対応していないBIOSは書き換えません。 先に1を入れておくと、書き換えられなかった場合も「有効」として扱えます
1回目の jc と2回目以降の jc で意味が違う1回目の失敗 = この機能が存在しない(相当古い機種)。2回目以降の失敗 = もう続きが無い。同じフラグが別の意味を持ちます
ebx を消してはいけないebx が「次の位置」を覚えています。 途中で使い回すと、最初の1件を無限に返し続けます

jc の意味が呼び出し回数で変わる、というのは、まともなAPIではありません。 これが1980年代のインタフェースです。 返り値の型も、エラーの表現も統一されていません。今のライブラリが例外や Result で統一しているのは、この世界を経験した結果です。

実際に、2ファイルに分ける

ここまでを実際のファイルにします。 ~/osdev/ で作業します。

前回の boot.asm を残しておきます。

bash
$ cd ~/osdev
$ cp boot.asm boot32.asm

1段目 — boot.asm

bash
$ nano boot.asm

中身を全部これに置き換えてください。

[bits 16]
[org 0x7c00]

KERNEL_OFFSET   equ 0x1000
KERNEL_SECTORS  equ 16
MMAP_COUNT      equ 0x0500
MMAP_ENTRIES    equ 0x0504

start:
    cli
    xor ax, ax
    mov ds, ax
    mov es, ax
    mov ss, ax
    mov sp, 0x7c00
    cld
    mov [boot_drive], dl

    ; --- カーネルを読み込む(BIOSが生きているうちに) ---
    mov bx, KERNEL_OFFSET
    mov ah, 0x02
    mov al, KERNEL_SECTORS
    mov ch, 0x00
    mov cl, 0x02
    mov dh, 0x00
    mov dl, [boot_drive]
    int 0x13
    jc disk_error
    cmp al, KERNEL_SECTORS
    jne disk_error

    ; --- メモリマップを取る(これもBIOS) ---
    call do_e820

    ; --- A20 ---
    in al, 0x92
    or al, 2
    out 0x92, al

    lgdt [gdt_descriptor]

    mov eax, cr0
    or eax, 1
    mov cr0, eax

    jmp CODE_SEG:KERNEL_OFFSET

disk_error:
    mov si, err_msg
.print:
    lodsb
    test al, al
    je .hang
    mov ah, 0x0e
    int 0x10
    jmp .print
.hang:
    cli
    hlt
    jmp .hang

do_e820:
    mov di, MMAP_ENTRIES
    xor ebx, ebx
    xor bp, bp
    mov edx, 0x534d4150
    mov eax, 0xe820
    mov dword [di + 20], 1
    mov ecx, 24
    int 0x15
    jc .failed
    mov edx, 0x534d4150
    cmp eax, edx
    jne .failed
    test ebx, ebx
    je .failed
    jmp .check
.next:
    mov eax, 0xe820
    mov dword [di + 20], 1
    mov ecx, 24
    int 0x15
    jc .done
    mov edx, 0x534d4150
.check:
    jcxz .skip
    mov ecx, [di + 8]
    or ecx, [di + 12]
    jz .skip
    inc bp
    add di, 24
.skip:
    test ebx, ebx
    jne .next
.done:
    mov [MMAP_COUNT], bp
    clc
    ret
.failed:
    mov word [MMAP_COUNT], 0
    stc
    ret

boot_drive: db 0
err_msg:    db "disk read failed", 0

gdt_start:
    dq 0x0000000000000000
gdt_code:
    dw 0xffff
    dw 0x0000
    db 0x00
    db 10011010b
    db 11001111b
    db 0x00
gdt_data:
    dw 0xffff
    dw 0x0000
    db 0x00
    db 10010010b
    db 11001111b
    db 0x00
gdt_end:

gdt_descriptor:
    dw gdt_end - gdt_start - 1
    dd gdt_start

CODE_SEG equ gdt_code - gdt_start
DATA_SEG equ gdt_data - gdt_start

    times 510 - ($ - $$) db 0
    dw 0xaa55

Ctrl + O → Enter → Ctrl + X で保存します。

GDTは前回と1ビットも変えていません。 変わったのは「読み込みとメモリマップが増え、キーボードと表示が消えた」ところだけです。

1段目から、画面表示のコードがほぼ消えました。 残っているのはエラー表示だけです。 ブートローダの仕事は「読んで飛ぶ」であって、それ以外を持たせないのが正しい形です。

いちばん素朴なメモリ管理を作る

ここからは2段目(kernel.asm)の話です。 先に考え方を固めます。

まず、malloc が何を返しているのかを確認する

普段こう書きます。

char *p = malloc(64);

この1行で起きていることは、実はこれだけです。

「ヒープのどこかに64バイト分の場所を決めて、その先頭の番地を返す。」

メモリを「作って」いるわけではありません。 メモリは最初から全部そこにあります。やっているのは「区画の割り当て」です。 不動産の分譲に近く、土地は最初からあって、誰にどこを渡したかを台帳で管理しているだけです。

そして、その台帳を、いま自分で書きます。

バンプアロケータ — 5行で書ける malloc

いちばん素朴なやり方は、これです。

「次に配る番地」を1つだけ覚えておいて、聞かれたらそこを返し、その分だけ進める。

Cで書くと、こうなります。

static unsigned char *next = (unsigned char *)0x100000;

void *bump_alloc(unsigned int size) {
    void *p = next;
    next += size;
    return p;
}

アセンブラでも5行です。

heap_next: dd 0x100000

bump_alloc:                 ; eax = 欲しいバイト数 → eax = 番地
    mov edx, [heap_next]
    add eax, edx
    mov [heap_next], eax
    mov eax, edx
    ret

これは本当に動きます。 そしてとても速いです。足し算1回で終わります。

良い点中身
速い探索が無い。常に一定時間
単純壊れようがない
管理情報が要らないポインタ1個だけ

バンプアロケータは、おもちゃではありません。 実務でも使われています。 「この処理の間だけ使って、終わったらまとめて全部捨てる」という場面(アリーナ / リージョンと呼ばれます)では、これが最速で最適です。ゲームの1フレーム分の作業領域や、コンパイラの1関数の解析中の領域が典型です。

なぜ、それで足りないのか

理由は1つだけです。

解放できません。

free に相当するものが書けません。 「次に配る番地」しか覚えていないので、「途中のあの64バイトは、もう空いた」を記録する場所がないからです。

すると何が起きるか。

for (;;) {
    char *p = bump_alloc(64);
    use(p);
    /* 解放できない */
}

1秒に1000回呼べば、1秒で64KB。1時間で230MB。 メモリの終わりまで進んだら、その先の何かを書き潰して死にます。

「解放できない」は、「いつか必ず尽きる」と同じ意味です。 止まらないプログラムでは、必ず破綻します。 サーバーは止まりません。OSはもっと止まりません。だから解放できる仕組みが要ります。

フリーリスト — これが malloc の正体

解放できるようにするには、「どこが空いているか」を覚える必要があります。

いちばん素直な方法は、配ったメモリそのものに台帳を書き込むことです。

配る64バイトの、すぐ手前に「管理用の8バイト」をこっそり付ける。

ヒープの中は、こう並びます。

+--------+--------+------------------+--------+--------+---------------+
| size   | used   | 実際に配る64バイト | size   | used   | 実際に配る…   |
| 4byte  | 4byte  |                  | 4byte  | 4byte  |               |
+--------+--------+------------------+--------+--------+---------------+
^ ブロックの先頭   ^ malloc が返す番地

これで、次の2つができるようになります。

操作やること
確保先頭から順にブロックを見て、used == 0 かつ size が足りるものを探す。無ければ末尾に新しく作る
解放渡された番地の 4バイト手前の used を 0 にする。それだけ

Cで書くと、こうです。

struct block {
    unsigned int size;   /* 配ったバイト数 */
    unsigned int used;   /* 1 = 使用中, 0 = 空き */
};

void kfree(void *p) {
    ((struct block *)p - 1)->used = 0;   /* ヘッダ(8バイト手前から)の used、つまり4バイト手前を 0 に */
}

free(p) に「サイズ」を渡さないのを、不思議に思ったことはないでしょうか。

char *p = malloc(64);
free(p);          /* 64 を渡さなくていい */

答えは、サイズが p の手前に書いてあるからです。 free は p - 8 を見て、そこに書いてある 64 を読みます。 そして、これが「解放したポインタをもう一度 free すると壊れる」理由でもあります。 手前の8バイトを、既に別の用途で使われているかもしれない状態で書き換えるからです。

アセンブラでの実装が、これです。 30行ありません。

HEAP_START equ 0x100000

heap_end:  dd HEAP_START        ; まだ一度も使っていない領域の先頭

kmalloc:                        ; eax = バイト数 → eax = 番地
    push ebx
    push ecx
    mov ebx, HEAP_START
.scan:
    cmp ebx, [heap_end]
    jae .fresh                  ; 末尾まで来た=空きが無かった
    cmp dword [ebx + 4], 0
    jne .next                   ; 使用中
    cmp [ebx], eax
    jb .next                    ; 空いてるが小さい
    mov dword [ebx + 4], 1      ; 再利用する
    lea eax, [ebx + 8]
    pop ecx
    pop ebx
    ret
.next:
    mov ecx, [ebx]
    lea ebx, [ebx + ecx + 8]    ; 次のブロックへ
    jmp .scan
.fresh:
    mov ebx, [heap_end]
    mov [ebx], eax
    mov dword [ebx + 4], 1
    mov ecx, eax
    lea eax, [ebx + ecx + 8]
    mov [heap_end], eax
    lea eax, [ebx + 8]
    pop ecx
    pop ebx
    ret

kfree:                          ; eax = 番地
    mov dword [eax - 4], 0
    ret

kfree が2行なのは、手を抜いたからではありません。 本物の free も、本質はこの1行です。 残りは「隣り合った空きブロックを繋げる」「大きすぎるブロックを分割する」「OSにメモリを返す」といった最適化です。 今回はその最適化を全部外しています。 外すと、次の節のことが起きます。

断片化を、実際に起こして見る

この kmalloc には、はっきりした欠陥があります。 説明する前に、まず起こします。

やることは4手です。

手順操作
164バイトを3つ確保する(A、B、C)
2A を解放する
3C を解放する
4128バイトを要求する

3手目が終わった時点で、空きは合計128バイトあります。 A の64バイトと C の64バイトです。

それなのに、4手目は「新しい場所」を返します。

確保返る番地何が起きたか
A = 64バイト0x00100008新規
B = 64バイト0x00100050新規
C = 64バイト0x00100098新規
128バイト0x001000E0A も C も使われず、さらに先へ伸びた

空きは128バイトある。要求も128バイト。それでも使えません。 A と C の間に、使用中の B が挟まっているからです。 空きが連続していません。

これが断片化です。

合計の空き連続した最大の空き128バイト取れるか
A と C を解放後128バイト64バイト取れない

「メモリが足りない」と言われるのに、タスクマネージャでは空いている——この現象の一因が、これです。 合計では足りていても、連続した空きが無ければ確保できません。

本物の malloc は、この対策を何段も持っています。

対策中身
隣接ブロックの結合(coalescing)解放したとき、隣も空きなら繋げて1つの大きい空きにする
分割(splitting)大きい空きから必要な分だけ切り出し、余りを空きブロックとして残す
サイズ別の管理(binning)同じくらいの大きさの空きをまとめておき、探索を短くする
ページ単位で確保する大きい要求は、そもそもOSから4KB単位でまとめて取る

そして最後の対策が、次の節の話に繋がります。

[スクリーンショット: 03_断片化.png] QEMU の画面で、00100008 00100050 00100098 の3つと、その下の行に 001000e0 が出ている状態を撮ってください。「空きが128バイトあるのに、新しい番地が返っている」ことが分かる画面にしてください。

ページングの入口 — なぜプロセスごとに同じアドレスを使えるのか

ここは概念だけです。実装はしません。 ただし、この節を飛ばすと、この先の話が全部繋がらなくなります。

素朴な疑問

プロセスの回で、ps を見ると多数のプロセスが並んでいました。それぞれが独立していて、片方が壊れても他は無事でした。

ここで、素朴な疑問が出ます。

同じプログラムを2つ起動したら、両方が同じ番地を使おうとするのでは。

同じ実行ファイルなので、中に書かれている番地は同じです。 変数の場所も、関数の場所も、まったく同じ番地を指しています。

にもかかわらず、2つは干渉しません。 片方の変数を書き換えても、もう片方は変わりません。

答えが、ページングです。

プログラムが見ている番地は、本当の番地ではありません。

仮想アドレスと物理アドレス

誰が見るか中身
仮想アドレスプログラムそのプロセスのための、専用の番地空間
物理アドレスメモリチップ本当の番地

この2つを繋ぐのが「ページテーブル」という変換表で、変換するのはCPUの中の回路(MMU)です。

プロセスA の 0x00400000  →(Aのページテーブル)→ 物理 0x12345000
プロセスB の 0x00400000  →(Bのページテーブル)→ 物理 0x67890000

同じ仮想アドレスが、違う物理アドレスに繋がっています。 だから干渉しません。

「プロセスごとに独立したメモリ空間がある」の実体は、これです。 プロセスを切り替えるとき、OSはページテーブルの先頭番地(cr3 レジスタ)も差し替えます。 その瞬間、同じ番地が別の場所を指すようになります。

なぜ4KB単位なのか

1バイトごとに変換表を持ったら、表がメモリより大きくなります。 だからまとめて扱います。 その単位が 4KB = 1ページです。

数
4GBの空間を1バイト単位で管理43億エントリ — 不可能
4GBの空間を4KB単位で管理104万エントリ — 表を2段にすれば現実的

この「4KB」という数字は、この先いたるところで出てきます。 メモリの使用量が4KB単位で増えるのも、ファイルの読み込みが4KB単位なのも、全部ここが起点です。

ページングで、他に何が手に入るか

アドレス変換は、目的の半分でしかありません。

手に入るもの中身
メモリ保護ページごとに「読める / 書ける / 実行できる / ユーザーが触れる」を設定できる。破るとページフォルト
メモリより大きく見せる使っていないページをディスクへ追い出す(スワップ)
断片化の緩和物理的にバラバラなページを、仮想的には連続に見せられる
共有同じ物理ページを、2つのプロセスの別々の番地に見せられる(共有ライブラリはこれ)

前回、「Segmentation fault はOSが作っていたもの」と書きました。 正確には、CPUの「ページフォルト」という例外を、OSが SIGSEGV というシグナルに翻訳したものです。 手前で止めているのはCPU、メッセージを出しているのはOSです。 そして前回のGDTで「フラットモデル(全メモリを指す設定)」にしたのは、保護の仕事をこちらに渡すためでした。セグメントは無害化して、保護はページングでやる。 これが x86 の現代的な使い方です。

実装しない理由も、正直に書きます。

ページテーブルを作るコードは50行ほどで書けますが、間違えた瞬間に「再起動を繰り返す真っ黒な画面」になり、切り分けの手段がほぼありません。 今回は「マルチタスクが動いているのを目で見る」を優先します。 保護なしのマルチタスクでも、切り替えの本質は同じです。

タイマ割り込みで、2つの処理を切り替える

ここが今回の最終目標です。

PIT — 一定間隔で叩き起こしてもらう

前回、キーボードの割り込み(IRQ1)を使いました。IRQ0 は、タイマです。

PIT は、設定した間隔で、ひたすら割り込みを上げ続けるチップです。

元になるクロックが約 1,193,182 Hz で決まっています。 これを設定した数(divisor)で割ったものが、割り込みの頻度になります。

divisor割り込みの間隔
65535(最大)約 18.2 回 / 秒
11932約 100 回 / 秒
1193約 1000 回 / 秒

設定は4命令です。

init_pit:
    mov al, 0x36            ; チャンネル0、下位→上位の順、モード2
    out 0x43, al
    mov ax, 11932
    out 0x40, al            ; 下位バイト
    mov al, ah
    out 0x40, al            ; 上位バイト
    ret
ポート役割
0x43設定を書き込む口
0x40チャンネル0(IRQ0に繋がっている)の値を書き込む口

divisor は16bitですが、8bitずつ2回に分けて送ります。 ポートが8bit幅しかないためです。

1,193,182 Hz という半端な数字にも理由があります。 当時のテレビ放送用の水晶(約14.318 MHz)を12で割った値です。専用の部品を用意せず、安く手に入るものを流用した結果が、45年間そのまま残っています。

PICのマスクも変えます。 前回はキーボード(IRQ1)だけ通していましたが、今回はタイマ(IRQ0)だけ通します。

マスク値通すもの
前回0xfd(11111101)IRQ1 = キーボード
今回0xfe(11111110)IRQ0 = タイマ

キーボードを外したのは、コードを短くするためです。 両方通すと 0xfc になります。

コンテキストスイッチ — 何を保存して、何を戻すのか

「処理を切り替える」とは、具体的に何を入れ替えることなのか。 ここを正確にします。

いま動いている処理の「今の状態」は、次の2つに全部入っています。

保存すべきもの中身
レジスタeax 〜 edi、そして eip(次に実行する命令の番地) と eflags
スタック関数の呼び出し履歴、ローカル変数、戻り先

そして、素晴らしいことに、割り込みが起きた時点で半分は勝手に終わっています。

誰が何を保存するか
CPU(割り込み発生時に自動)eflags、cs、eip をスタックに積む
pusha 命令(1命令)汎用レジスタ8本をスタックに積む

つまり、割り込みハンドラの先頭で pusha を実行した時点で、状態は全部「そのタスクのスタックの上」に乗っています。

だとすると、切り替えに必要なのは、たった1つです。 esp(スタックポインタ)を、別のタスクのものに差し替えること。

これで全部です。

current:   dd 0                 ; いまどちらのタスクか(0 or 1)
esp_slots: dd 0, 0              ; 各タスクの esp の保存場所

timer_handler:
    pusha                       ; ① 汎用レジスタ8本を、いまのスタックへ
    mov eax, [current]
    mov [esp_slots + eax * 4], esp   ; ② いまの esp を保存
    xor eax, 1                  ; ③ 相手に切り替え
    mov [current], eax
    mov esp, [esp_slots + eax * 4]   ; ④ 相手の esp を復元
    mov al, 0x20
    out 0x20, al                ; ⑤ PIC に「終わった」と伝える
    popa                        ; ⑥ 相手のレジスタを復元
    iret                        ; ⑦ 相手が中断した場所へ戻る

11行です。 これがマルチタスクの心臓部の全部です。

行何をしているか
① pushaタスクAの状態を、タスクAのスタックに置く
②その置いた場所(esp)を覚えておく
③④esp をタスクBのものに差し替える
⑥ popaタスクBのスタックから、タスクBのレジスタを取り出す
⑦ iretタスクBが中断した命令の続きへ戻る

④と⑥の間で、世界が入れ替わっています。 同じ popa という1命令が、④の前ならAのレジスタを、④の後ならBのレジスタを復元します。 命令は同じで、指しているスタックだけが違います。 「今どのタスクを実行中か」は、CPUの中には存在しません。 esp が指している先が、それを決めています。

新しいタスクを「これから始める」には

切り替えのコードは、「中断されたタスクに戻る」形をしています。 つまり、まだ一度も動いたことのないタスクBを始めるには、「あたかも一度中断されたことがあるかのようなスタック」を、手で作ってやる必要があります。

iret が読む順番は、下から eip、cs、eflags です。 その下に popa が読む8本分(32バイト)を置きます。

init_task_b:
    mov edi, 0x8f000            ; タスクB用スタックの底
    sub edi, 4
    mov dword [edi], 0x202      ; eflags(IF=1 割り込み許可)
    sub edi, 4
    mov dword [edi], CODE_SEG   ; cs
    sub edi, 4
    mov dword [edi], task_b     ; eip = 開始位置
    mov ecx, 8                  ; popa が読む 8本分
.zero:
    sub edi, 4
    mov dword [edi], 0
    dec ecx
    jnz .zero
    mov [esp_slots + 4], edi
    ret

eflags に 0x202 を入れているのが重要です。 0x200 のビットが IF(割り込み許可)です。 ここを0にすると、タスクBに切り替わった瞬間に割り込みが止まり、二度とタスクAに戻れません。 画面はタスクBのカウンタだけが動き続けます。 「片方のタスクに移ったきり戻ってこない」の原因は、ほぼこれです。

そしてこれが、fork や pthread_create がやっていることの原型です。

「新しいプロセスを作る」の実体は、「新しいスタックを用意して、そこに偽の中断状態を書き込み、切り替え対象のリストに加える」ことです。

bashを自作した回で fork を呼びました。あの中で、カーネルはこれをやっています。(実際にはメモリ空間の複製も入るので、もっと大きな仕事です)

2つのカウンタが、同時に増える

タスクは、ただカウントアップして画面に書くだけにします。

task_a:
    xor esi, esi
.loop:
    inc esi
    mov eax, esi
    mov edi, 0xb8000 + 160 * 18 + 30 * 2
    mov dl, 0x0a                ; 緑
    call print_hex32
    mov ecx, 0x00400000
.wait:
    dec ecx
    jnz .wait
    jmp .loop

タスクBは、行と色が違うだけです。

.wait の空回りループは、単に「目で追える速さにする」ためです。 入れないと数字が高速で流れて読めません。

注意すべき点が1つあります。 print_hex32 を、タスクAとタスクBが同時に呼びます。 それでも壊れないのは、この関数がレジスタしか使わず、共有の変数を持たないからです。 もし途中経過をグローバル変数に置いていたら、切り替わった瞬間に壊れます。 これが「再入可能(リエントラント)」という言葉の意味です。 マルチスレッドのバグの大半が、ここから出ます。 「関数の中で static 変数を使うな」と言われる理由が、この11行のコードから直接来ています。

2段目 — kernel.asm を書く

全部つなげます。

bash
$ cd ~/osdev
$ nano kernel.asm

以下を全部貼り付けてください。

[bits 32]
[org 0x1000]

CODE_SEG     equ 0x08
DATA_SEG     equ 0x10
VGA          equ 0xb8000
IDT_BASE     equ 0x9000
HEAP_START   equ 0x100000
STACK_B_TOP  equ 0x8f000
MMAP_COUNT   equ 0x0500
MMAP_ENTRIES equ 0x0504

kernel_start:
    mov ax, DATA_SEG
    mov ds, ax
    mov es, ax
    mov fs, ax
    mov gs, ax
    mov ss, ax
    mov esp, 0x90000

    mov esi, msg_hello
    mov edi, VGA
    mov dl, 0x0f
    call print_str

    call show_mmap
    call demo_alloc

    mov esi, msg_task_a
    mov edi, VGA + 160 * 18
    mov dl, 0x0a
    call print_str
    mov esi, msg_task_b
    mov edi, VGA + 160 * 20
    mov dl, 0x0d
    call print_str

    call init_idt
    call init_pic
    call init_pit
    call init_task_b

    sti
    jmp task_a

; ---------------- 画面 ----------------
print_str:                      ; esi=文字列, edi=書き先, dl=色
    lodsb
    test al, al
    je .end
    mov [edi], al
    mov [edi + 1], dl
    add edi, 2
    jmp print_str
.end:
    ret

putc:                           ; al=文字, edi=書き先, dl=色
    mov [edi], al
    mov [edi + 1], dl
    add edi, 2
    ret

print_hex32:                    ; eax=値, edi=書き先, dl=色
    push ecx
    push ebx
    mov ecx, 8
.next:
    rol eax, 4
    mov bl, al
    and bl, 0x0f
    cmp bl, 10
    jb .num
    add bl, 'a' - 10
    jmp .put
.num:
    add bl, '0'
.put:
    mov [edi], bl
    mov [edi + 1], dl
    add edi, 2
    dec ecx
    jnz .next
    pop ebx
    pop ecx
    ret

; ---------------- メモリマップ ----------------
show_mmap:
    mov esi, msg_mmap
    mov edi, VGA + 160 * 2
    mov dl, 0x0e
    call print_str

    movzx ecx, word [MMAP_COUNT]
    test ecx, ecx
    je .none
    cmp ecx, 7
    jbe .ok
    mov ecx, 7
.ok:
    mov esi, MMAP_ENTRIES
    mov ebp, VGA + 160 * 3
.loop:
    mov edi, ebp
    mov dl, 0x0a
    mov eax, [esi + 4]
    call print_hex32
    mov eax, [esi]
    call print_hex32
    mov al, ' '
    call putc
    mov dl, 0x0b
    mov eax, [esi + 12]
    call print_hex32
    mov eax, [esi + 8]
    call print_hex32
    mov al, ' '
    call putc
    mov dl, 0x0f
    mov eax, [esi + 16]
    call print_hex32
    add esi, 24
    add ebp, 160
    dec ecx
    jnz .loop
    ret
.none:
    mov esi, msg_nommap
    mov edi, VGA + 160 * 3
    mov dl, 0x0c
    call print_str
    ret

; ---------------- アロケータ ----------------
kmalloc:                        ; eax = バイト数 → eax = 番地
    push ebx
    push ecx
    mov ebx, HEAP_START
.scan:
    cmp ebx, [heap_end]
    jae .fresh
    cmp dword [ebx + 4], 0
    jne .next
    cmp [ebx], eax
    jb .next
    mov dword [ebx + 4], 1
    lea eax, [ebx + 8]
    pop ecx
    pop ebx
    ret
.next:
    mov ecx, [ebx]
    lea ebx, [ebx + ecx + 8]
    jmp .scan
.fresh:
    mov ebx, [heap_end]
    mov [ebx], eax
    mov dword [ebx + 4], 1
    mov ecx, eax
    lea eax, [ebx + ecx + 8]
    mov [heap_end], eax
    lea eax, [ebx + 8]
    pop ecx
    pop ebx
    ret

kfree:                          ; eax = 番地
    mov dword [eax - 4], 0
    ret

demo_alloc:
    mov esi, msg_alloc
    mov edi, VGA + 160 * 11
    mov dl, 0x0e
    call print_str

    mov edi, VGA + 160 * 12
    mov dl, 0x0f
    mov eax, 64
    call kmalloc
    mov [ptr_a], eax
    call print_hex32
    mov al, ' '
    call putc

    mov eax, 64
    call kmalloc
    mov [ptr_b], eax
    call print_hex32
    mov al, ' '
    call putc

    mov eax, 64
    call kmalloc
    mov [ptr_c], eax
    call print_hex32

    mov eax, [ptr_a]
    call kfree
    mov eax, [ptr_c]
    call kfree

    mov esi, msg_frag
    mov edi, VGA + 160 * 13
    mov dl, 0x0e
    call print_str

    mov edi, VGA + 160 * 14
    mov dl, 0x0c
    mov eax, 128
    call kmalloc
    call print_hex32
    ret

; ---------------- 割り込み ----------------
init_idt:
    mov edi, IDT_BASE
    mov ecx, 0x21 * 2
    xor eax, eax
    rep stosd

    mov edi, IDT_BASE + 0x20 * 8
    mov eax, timer_handler
    mov [edi], ax
    mov word [edi + 2], CODE_SEG
    mov byte [edi + 4], 0
    mov byte [edi + 5], 10001110b
    shr eax, 16
    mov [edi + 6], ax
    lidt [idt_descriptor]
    ret

init_pic:
    mov al, 0x11
    out 0x20, al
    out 0xa0, al
    mov al, 0x20
    out 0x21, al
    mov al, 0x28
    out 0xa1, al
    mov al, 0x04
    out 0x21, al
    mov al, 0x02
    out 0xa1, al
    mov al, 0x01
    out 0x21, al
    out 0xa1, al
    mov al, 0xfe
    out 0x21, al
    mov al, 0xff
    out 0xa1, al
    ret

init_pit:
    mov al, 0x36
    out 0x43, al
    mov ax, 11932
    out 0x40, al
    mov al, ah
    out 0x40, al
    ret

init_task_b:
    mov edi, STACK_B_TOP
    sub edi, 4
    mov dword [edi], 0x202
    sub edi, 4
    mov dword [edi], CODE_SEG
    sub edi, 4
    mov dword [edi], task_b
    mov ecx, 8
.zero:
    sub edi, 4
    mov dword [edi], 0
    dec ecx
    jnz .zero
    mov [esp_slots + 4], edi
    ret

timer_handler:
    pusha
    mov eax, [current]
    mov [esp_slots + eax * 4], esp
    xor eax, 1
    mov [current], eax
    mov esp, [esp_slots + eax * 4]
    mov al, 0x20
    out 0x20, al
    popa
    iret

; ---------------- タスク ----------------
task_a:
    xor esi, esi
.loop:
    inc esi
    mov eax, esi
    mov edi, VGA + 160 * 18 + 30 * 2
    mov dl, 0x0a
    call print_hex32
    mov ecx, 0x00400000
.wait:
    dec ecx
    jnz .wait
    jmp .loop

task_b:
    xor esi, esi
.loop:
    inc esi
    mov eax, esi
    mov edi, VGA + 160 * 20 + 30 * 2
    mov dl, 0x0d
    call print_hex32
    mov ecx, 0x00400000
.wait:
    dec ecx
    jnz .wait
    jmp .loop

; ---------------- データ ----------------
idt_descriptor:
    dw 0x21 * 8 - 1
    dd IDT_BASE

current:   dd 0
esp_slots: dd 0, 0
heap_end:  dd HEAP_START
ptr_a:     dd 0
ptr_b:     dd 0
ptr_c:     dd 0

msg_hello:  db "stage2 kernel loaded from disk", 0
msg_mmap:   db "memory map (base / length / type):", 0
msg_nommap: db "e820 failed", 0
msg_alloc:  db "kmalloc 64 x 3, then free A and C:", 0
msg_frag:   db "kmalloc 128 (128 bytes free, but split):", 0
msg_task_a: db "task A counter:", 0
msg_task_b: db "task B counter:", 0

Ctrl + O → Enter → Ctrl + X で保存します。

[org 0x1000] に注目してください。 1段目は [org 0x7c00]、2段目は [org 0x1000]。 「このコードは何番地に置かれる前提か」を、NASM に教えています。 ここを間違えると、文字列やデータを参照する番地が全部ずれます。 コードは動くのに、画面に化けた文字が出るという形で現れます。

組み立てて、起動する

2つを別々にアセンブルして、1つのイメージにする

ここだけ、前回とコマンドが変わります。 増えるのは dd だけで、新しい道具は入れません。

bash
$ cd ~/osdev
$ nasm -f bin boot.asm -o boot.bin
$ nasm -f bin kernel.asm -o kernel.bin
$ ls -l boot.bin kernel.bin
-rw-rw-r-- 1 ubuntu ubuntu  512 Sep 15 10:22 boot.bin
-rw-rw-r-- 1 ubuntu ubuntu 1187 Sep 15 10:22 kernel.bin

boot.bin は512バイトちょうど。kernel.bin は制限がありません。

この2つを、ディスクイメージに並べます。

bash
$ dd if=/dev/zero of=os.img bs=512 count=32
$ dd if=boot.bin of=os.img conv=notrunc
$ dd if=kernel.bin of=os.img bs=512 seek=1 conv=notrunc
$ ls -l os.img

3行が何をしているか。

行意味
1行目512バイト × 32 = 16KB の、全部0のファイルを作る
2行目その先頭に boot.bin を上書き(conv=notrunc = ファイルを切り詰めない)
3行目512バイト単位で1つ飛ばした位置(=2セクタ目)に kernel.bin を上書き

seek=1 が「2セクタ目から」の指定です。 ブートセクタの cl = 2 と、ここが一致していないといけません。 1行目で先に全部0で埋めておくのが重要です。 イメージが小さいと、int 0x13 が「読むセクタが無い」で失敗します(ah = 0x04)。16セクタ読むと書いたので、イメージは最低17セクタ必要です。

[スクリーンショット: 01_2ファイル構成.png] ls -l boot.bin kernel.bin os.img の結果を撮ってください。boot.bin が512バイトちょうどで、os.img が16384バイトになっていることが分かる画面にしてください。

中身を目で確かめておきます。

bash
$ xxd -s 0x1f0 -l 32 os.img
000001f0: 0000 0000 0000 0000 0000 0000 0000 55aa  ..............U.
00000200: 66b8 1000 008e d88e c08e e08e e88e d0bc  f...............

0x1FE に 55 aa(ブートセクタの印)があり、その直後の 0x200 から2段目が始まっています。 ここが「2セクタ目」です。

QEMU で起動する

前回と同じコマンドで、ファイル名だけ変えます。

bash
$ qemu-system-i386 -drive format=raw,file=os.img -curses

画面はこうなります。

stage2 kernel loaded from disk

memory map (base / length / type):
0000000000000000 000000000009fc00 00000001
000000000009fc00 0000000000000400 00000002
00000000000f0000 0000000000010000 00000002
0000000000100000 0000000007ee0000 00000001
0000000007fe0000 0000000000020000 00000002
00000000fffc0000 0000000000040000 00000002

kmalloc 64 x 3, then free A and C:
00100008 00100050 00100098
kmalloc 128 (128 bytes free, but split):
001000e0

task A counter:               0000002b
task B counter:               0000002a

1行目が出た時点で、2段階ローダは成功しています。 この文字列は kernel.bin の中にしかありません。 ディスクから読み込めていなければ、絶対に出ません。

メモリマップの4行目に注目してください。

0000000000100000 0000000007ee0000 00000001

0x100000(1MB)から 0x7EE0000(約127MB)が「使える」と返っています。 QEMU の既定のメモリ量が128MBなので、その内訳です。ヒープをここに置いたのは、この行を見て決めたことになります。

[スクリーンショット: 02_メモリマップ表示.png] QEMU の画面上部に、stage2 kernel loaded from disk とメモリマップの一覧が出ている状態を撮ってください。

そして、下の2行を見る

画面のいちばん下、task A counter: と task B counter: の数字が、両方とも増え続けています。

プログラムは1つしか動いていません。CPUも1つです。

にもかかわらず、2つの数え上げが同時に進んでいます。 やっているのは、100分の1秒ごとに esp を差し替えているだけです。

[スクリーンショット: 04_2つのカウンタ.png] task A counter: と task B counter: の両方の数字が増えている状態を撮ってください。2行の数字が違う値になっている瞬間だと、別々に進んでいることが分かります。

これが「マルチタスク」の正体です。 プロセスの回で ps aux を打つと、数百のプロセスが並んでいました。あれが全部同時に動いているように見えるのも、これと同じことをしているからです。 違いは規模だけです。

今回作ったものLinux
切り替えの単位2つのタスク数百のプロセス・スレッド
切り替えの契機タイマ割り込みだけタイマ、システムコール、I/O待ち、yield
次に誰を動かすか交互(xor eax, 1)スケジューラが優先度・待ち時間・CPU割り当て量から決める
保存するもの汎用レジスタ + esp上記 + 浮動小数点/SIMD + cr3(ページテーブル)+ TLS
メモリの分離無い(同じ空間)ページングで完全に分離

「今どのタスクが動いているか」を決めているのが esp だけ、という事実は、しばらく残ります。 top の %CPU は、「一定時間のうち、そのタスクの esp が使われていた割合」です。 それ以上の意味はありません。

「同時に動く」は、同時ではない

もう1つ、ここで潰しておきたい誤解があります。

今回の2つのタスクは、1ミリ秒たりとも同時には動いていません。

CPUは1つで、命令は1つずつしか実行できません。 やっているのは高速な切り替えで、並行(concurrent)であって並列(parallel)ではありません。

言葉意味今回
並行(concurrency)複数の処理が、進行中の状態で共存しているこれ
並列(parallel)複数の処理が、物理的に同時に実行されているCPUコアが複数必要

「4コアだから4倍速い」が単純に成り立たないのは、ここが分かれているからです。 1つのコアの上でいくら切り替えても、合計の仕事量は増えません。

そして、切り替えにはコストがあります。 今回のハンドラは十数命令ですが、本物のOSではページテーブルの切り替え、TLB(アドレス変換のキャッシュ)の破棄、キャッシュの汚染が乗ります。 「スレッドを増やすほど速くなる」わけではない理由の1つが、これです。

ここから先に、何があるか

今回で「メモリを配る人」と「処理を切り替える人」ができました。 それでもまだOSではありません。 足りないものを、正直に書いておきます。

続き何をするか何が手に入るか
ページングページテーブルを作り、cr3 に設定して cr0 のPGビットを立てるプロセスごとに独立したメモリ空間。Segmentation fault が出せるようになる
ユーザーモード特権レベル3のセグメントを用意し、TSSを設定してそちらへ落ちるアプリがカーネルのメモリを触れなくなる。 暴走しても全体は死なない
システムコールint 0x80 や sysenter の入口を作り、ユーザーモードからカーネルを呼べるようにするwrite や open が呼べるようになる。ここで初めて printf が動く
ファイルシステムディスクドライバを書き、バイト列を「ファイル」として解釈する層を載せるopen / read / ファイル名
Cで書くgcc と ld を入れて、カーネルをCで書き直すアセンブラを移行部分だけに減らせる

順番には理由があります。 ユーザーモードは、ページングが無いと意味がありません。 特権レベルを下げても、メモリ空間が共通なら、番地を指定して他人のメモリを読めてしまうからです。 システムコールは、ユーザーモードが無いと意味がありません。 同じ特権レベルなら、普通の call で呼べてしまうからです。 「保護」は積み上げでしか作れません。 1つ飛ばすと、その上の全部が形だけになります。

そして、この続きを1つ1つ説明している教材があります。

教材何が書いてあるか
Writing a Simple Operating System from Scratch今回の内容とほぼ同じ道筋を、PDF1冊で。 2段階ローダとCへの移行が丁寧
cfenollosa/os-tutorial上を、動くコードで章ごとに追えるようにしたもの。 ここから先に進むなら、まずこれ
The little book about OS developmentページング・ユーザーモード・システムコールまで到達する。 今回の直接の続き
Writing an OS in RustRustで書く現代的な入門。 説明が図解込みで、概念の理解だけでも読む価値がある
MIT 6.828 / xv6教育用の小さなUnix。 ソースが数千行で読み切れる。「本物のOSの構造」を最短で見る方法
『30日でできる!OS自作入門』(川合秀実)日本語で最後まで到達できる本。 独自ツールを使う点は好みが分かれます

つまずいたところ

そのまま書きます。

症状原因
画面が真っ黒のまま、何も出ないos.img を作り直さずに QEMU を起動していました。 kernel.asm を直しても、nasm と dd を両方やり直さないと反映されません。1回のコマンドで済まなくなったので、これを頻繁にやります
disk read failed と出るos.img が小さすぎました。 dd if=/dev/zero ... count=32 を忘れ、boot.bin と kernel.bin を cat で繋いだだけだったので、16セクタ読もうとして届かなかった(ah = 0x04)
延々と再起動を繰り返すcl を 1 にしていました。 ブートセクタ自身を 0x1000 に読み込んで、そこへ飛んでいました。16bitのコードを32bitとして実行するので、即死します
jc を書かずに進めて、原因が分からなかったこれが今回いちばん時間を溶かしました。 読み込みに失敗しているのに、そのまま 0x1000 へ飛んでいました。jc disk_error を足した瞬間に、原因が1行で分かりました
メモリマップが1件しか出ないebx を途中で別用途に使っていました。 ebx が「次の位置」を保持しているので、毎回同じ1件目が返ってきていた
メモリマップが e820 failed になるedx に 'SMAP' を入れ直すのを、2回目以降で忘れていました。 BIOSによっては edx を壊して返してきます
0x100000 に書いたのに、読み返すと0A20ラインを開ける3命令を、コピーし忘れていました。 0x100000 が 0x000000 に化けて、IVTを書き潰していました。 エラーは一切出ません
確保した番地の中身が、いつの間にか壊れるヘッダの8バイトを数え忘れて、kmalloc が返す番地を ebx にしていました(正しくは ebx + 8)。返した番地に書き込むと、自分の管理情報を壊します
kfree したあと kmalloc が変な番地を返すmov dword [eax - 4], 0 を [eax - 8] と書いていました。 size の方を0にしてしまい、次の走査で「サイズ0のブロック」を無限に踏み続けました
タスクBに移ったきり、Aに戻らない初期スタックの eflags を 0 にしていました。 IF(0x200)が立っていないので、タスクBでは割り込みが止まったままでした
sti した瞬間に落ちるinit_pit を呼ぶ前に sti していました。 タイマは初期状態でも動いているので、IDTを整える前に割り込みが来ていました
カウンタが1つしか動かないinit_task_b で popa の分の32バイトを空けていませんでした。 iret が読む位置がずれて、でたらめな番地へ飛んでいました
数字が高速で流れて読めない空回りループを入れていませんでした。 これは正常な動作です
out 0x20, al を popa の後ろに書いて動かなくなったpopa でレジスタが復元されるので、al に入れた 0x20 が消えていました。 EOI が送られず、2回目の割り込みが来ません

今回、唯一まともに教えてくれたのが disk read failed の1行です。 そしてそれは、自分で jc を書いたから出ました。 書かなければ、やはり真っ黒な画面だけでした。 切り分け方は前回と同じです。 疑う場所の直前に 0xb8000 へ1文字書きます。2段階になったので、「1段目までは生きているか」「2段目に届いているか」を、この方法で分けて確かめられるようになりました。 これは前進です。

後片づけ

QEMU を終わらせます。 前回と同じです。

方法1: QEMUのモニタに切り替える

Esc を押してから 2 を押します(Alt + 2 でも切り替わります)。(qemu) というプロンプトに変わったら打ちます。

quit

方法2: 別のターミナルから止める

VS Code の Remote SSH でもう1つ端末を開いて打ちます。

bash
$ pkill qemu-system-i386

終了できたか確認します。

bash
$ pgrep qemu-system-i386 || echo "動いていません"
動いていません

入れた道具を消したい場合はこうします。

bash
$ sudo apt remove -y nasm qemu-system-x86
$ sudo apt autoremove -y

~/osdev/ は残して構いません。 boot16.asm(1回目)、boot32.asm(2回目)、boot.asm + kernel.asm(今回)が並びます。 3世代を見比べると、「512バイトに何を残し、何を追い出したか」がそのまま分かります。

そして、毎回と同じ注意です。

os.img を、本物のUSBメモリやディスクに書き込まないでください。 実物のディスクの先頭に書くと、パーティション情報が消えます。 QEMUの中だけで完結させてください。

まとめ

  • ブートローダとカーネルが別ファイルなのは、設計思想ではなく512バイト制限の回避策。 GRUB も同じ形の発展形
  • BIOSに聞きたいことは、全部リアルモードのうちに聞いておく。 ディスク(int 0x13)もメモリマップ(int 0x15)も、プロテクトモードに移ると使えない
  • int 0x13 は失敗しても何も言わない。 jc(キャリーフラグ)と al(実際に読めたセクタ数)を、自分で確かめる
  • セクタ番号だけ1から数える。 シリンダもヘッドも0始まりなのに、セクタは1始まり。cl = 2 が「続きから」
  • dl(起動ドライブ番号)は、BIOSが渡してくれる唯一の引数。 決め打ちするとたまたま動いて、環境を変えた瞬間に壊れる
  • CPUには「搭載メモリ量を返す命令」が無い。 知っているのはBIOSだけで、int 0x15, eax=0xE820 で1件ずつ聞く
  • メモリは1本の連続した領域ではない。 使える区間と、装置に予約された区間が交互に並んでいる
  • malloc はメモリを作らない。 「ここからここまでを、あなたに割り当てました」と台帳に書いて番地を返すだけ
  • バンプアロケータは5行で書けて、実務でも使われている。 ただし解放できない=いつか必ず尽きる
  • フリーリストは、配るメモリの手前8バイトに管理情報を埋め込む。 free にサイズを渡さなくていいのは、そこに書いてあるから
  • 断片化は、合計の空きが足りていても連続していないと確保できない現象。 実際に、空き128バイトあって128バイト取れない
  • ページングは、仮想アドレスを物理アドレスに変換する仕組み。 プロセスごとに同じ番地が使えるのは、変換表が違うから
  • cr3 の差し替えが「メモリ空間の切り替え」の実体。 ページ単位(4KB)で読み書き実行の権限も付けられる
  • コンテキストスイッチの本体は esp の差し替え1つ。 レジスタは pusha とCPUの自動退避で、既にスタックに乗っている
  • 新しいタスクを始めるとは、「一度中断されたかのような偽のスタック」を手で組み立てること。 fork の原型がこれ
  • 初期 eflags の IF ビットを忘れると、そのタスクに移ったきり戻らない
  • 同時に動いているように見えるのは、100分の1秒ごとに切り替えているから。 並行であって、並列ではない
  • 共有の変数を持たない関数だけが、切り替えられても壊れない。 「static を使うな」の理由が、この11行から出ている
  • 低レイヤはやはりエラーを出さない。 唯一の例外は、自分で書いた jc disk_error の1行だった

参考リンク


次に読む

この記事は 【番外編】roadmap.sh の外 の 31 / 35 本目です。

記事
← 前の記事インタプリタを自作する演習 — 字句解析と構文解析から実行まで
→ 次の記事自作OSにファイルシステムを付ける — 名前でファイルを読む仕組み

ここは番外編です。 本筋から外れているので、飛ばして構いません。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

【番外編】OS自作。roadmap.sh の範囲外。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次