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を差し替えているだけだということ
この記事でやること
boot.asmを「読み込み係」に作り直し、kernel.asmを新しく書く(2段階ローダ)int 0x13でカーネルをディスクから読み込み、キャリーフラグで成否を確認するint 0x15, eax=0xE820でメモリマップを取り、画面に一覧を出す- バンプアロケータ → フリーリスト の順に
mallocを作り、断片化を画面で見る - PIT(タイマ)を設定し、コンテキストスイッチを書いて、2つのカウンタが同時に増えるのを見る
- QEMU を終了し、後片づけをする
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| 2段階ローダ | ブートセクタが「本体を読み込むだけ」に徹し、本体(カーネル)を別ファイルにする構成。512バイト制限の回避策 |
| セクタ | ディスクの最小の読み書き単位。512バイト。ブートセクタは1セクタ目 |
| CHS | シリンダ・ヘッド・セクタ。円盤の物理的な位置でディスクの場所を指す、古い指定方法。int 0x13 の基本形はこれ |
| キャリーフラグ | CPUのフラグの1つ。BIOSの機能は、失敗するとこれを1にして戻ってくる。jc 命令で分岐できる |
| メモリマップ | 物理メモリのどこが使えて、どこが使えないかの一覧。連続した1本の領域ではない |
| E820 | int 0x15 に eax = 0xE820 を渡してメモリマップを1件ずつ取るBIOSの機能。名前は番号そのまま |
| ヒープ | プログラムが実行中に「ここから好きに使っていい」とされたメモリ領域。malloc が配るのはここ |
| アロケータ | ヒープから「この分ください」に応えて番地を返す仕組み。malloc の中身 |
| バンプアロケータ | 先頭から順に配るだけの、いちばん素朴なアロケータ。解放できない |
| フリーリスト | 空いているブロックを繋いで管理する方式。解放できるようになる。malloc の実装の基本形 |
| 断片化 | 空きの合計は足りているのに、連続した空きが足りなくて確保できない状態 |
| 物理アドレス | メモリチップ上の、本当の番地 |
| 仮想アドレス | プログラムから見える番地。物理アドレスとは別物で、変換表を通して繋がる |
| ページング | 仮想アドレスを物理アドレスに変換する仕組み。4KBごとの「ページ」単位で対応表を持つ |
| PIT | Programmable 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が要る) |
| 3 | A20を開ける | どちらでも |
| 4 | GDTを登録して、プロテクトモードへ移る | ここで切り替わる |
| 5 | カーネルへ飛ぶ | プロテクトモード |
「BIOSに聞きたいことは、全部リアルモードのうちに聞いておく。」 これが、この回でいちばん実務的な教訓です。移行したあとで「メモリが何MBか知りたい」と思っても、もう聞く相手がいません。
だから本物のOSも、起動の初期にBIOS(UEFIなら別の窓口)から情報を吸い上げて、メモリ上に置いてから移行します。 Linux カーネルが起動時に持っている「boot params」という構造体は、まさにこれです。
カーネルを別ファイルにして、読み込む
まず、置き場所を決める
読み込む前に、「どこへ読み込むか」を決めないといけません。 そしてここは好きに決められません。
リアルモードで最初の1MBは、こういう地図になっています。
| 番地 | 何があるか | 使えるか |
|---|---|---|
0x00000 – 0x004FF | IVT(割り込みベクタ)とBIOSのデータ領域 | 触ってはいけない |
0x00500 – 0x07BFF | 空き | 使える(約30KB) |
0x07C00 – 0x07DFF | ブートセクタ(自分自身) | 使えない |
0x07E00 – 0x9FBFF | 空き | 使える(約610KB) |
0x9FC00 – 0x9FFFF | EBDA(BIOSが拡張データを置く) | 触ってはいけない |
0xA0000 – 0xBFFFF | ビデオメモリ(0xB8000 はこの中) | 画面用 |
0xC0000 – 0xFFFFF | BIOSやカードの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つずつ意味を潰します。
| レジスタ | 入れるもの | 注意 |
|---|---|---|
ah | 0x02 = 「セクタを読む」 | 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 の値 | 意味 |
|---|---|
0x00 | 1台目のフロッピー |
0x80 | 1台目のハードディスク(QEMU の -drive はこれ) |
0x81 | 2台目のハードディスク |
そして前回のコードは、いきなりこれを壊していました。
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, 16 | al には「実際に読めたセクタ数」が返る。 頼んだ数より少ないことがある |
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 までが全部使える、と思っていると外れます。
実際に返ってくるのは、こういう「区間の一覧」です。
| 開始 | 長さ | 種別 |
|---|---|---|
0x0000000000000000 | 0x000000000009FC00 | 1 = 使える |
0x000000000009FC00 | 0x0000000000000400 | 2 = 予約(EBDA) |
0x00000000000F0000 | 0x0000000000010000 | 2 = 予約(BIOS ROM) |
0x0000000000100000 | 0x0000000007EE0000 | 1 = 使える |
0x00000000FFFC0000 | 0x0000000000040000 | 2 = 予約 |
種別(type)の意味は決まっています。
| type | 意味 |
|---|---|
1 | 自由に使える |
2 | 予約済み。触ってはいけない |
3 | ACPI のテーブル。読んだあとなら再利用してよい |
4 | ACPI が使うので保存が必要 |
5 | 壊れているメモリ |
穴が空いています。
0x9FC00から0x100000までは、メモリチップは刺さっているのに使えません。 装置のために予約されているからです。0xFFFC0000あたりにも区間があります。 これはメモリではなく、PCI装置がアドレス空間の一部を借りているものです。 「メモリマップ」とは、メモリの地図ではなく、アドレス空間の地図です。
E820 の呼び方
1回の呼び出しで1件返ります。 続きがあるかどうかは ebx で分かります。
| レジスタ | 役割 |
|---|---|
eax | 0xE820 を入れる。返ってくるときは 'SMAP'(0x534D4150)になる |
ebx | 「次はどこから」を覚えている値。 最初は0。0が返ってきたら終わり |
ecx | 1件のサイズ。 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], 1 | 24バイト目は「ACPI拡張属性」で、対応していないBIOSは書き換えません。 先に1を入れておくと、書き換えられなかった場合も「有効」として扱えます |
1回目の jc と2回目以降の jc で意味が違う | 1回目の失敗 = この機能が存在しない(相当古い機種)。2回目以降の失敗 = もう続きが無い。同じフラグが別の意味を持ちます |
ebx を消してはいけない | ebx が「次の位置」を覚えています。 途中で使い回すと、最初の1件を無限に返し続けます |
jcの意味が呼び出し回数で変わる、というのは、まともなAPIではありません。 これが1980年代のインタフェースです。 返り値の型も、エラーの表現も統一されていません。今のライブラリが例外やResultで統一しているのは、この世界を経験した結果です。
実際に、2ファイルに分ける
ここまでを実際のファイルにします。 ~/osdev/ で作業します。
前回の boot.asm を残しておきます。
1段目 — 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手です。
| 手順 | 操作 |
|---|---|
| 1 | 64バイトを3つ確保する(A、B、C) |
| 2 | A を解放する |
| 3 | C を解放する |
| 4 | 128バイトを要求する |
3手目が終わった時点で、空きは合計128バイトあります。 A の64バイトと C の64バイトです。
それなのに、4手目は「新しい場所」を返します。
| 確保 | 返る番地 | 何が起きたか |
|---|---|---|
| A = 64バイト | 0x00100008 | 新規 |
| B = 64バイト | 0x00100050 | 新規 |
| C = 64バイト | 0x00100098 | 新規 |
| 128バイト | 0x001000E0 | A も 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 を書く
全部つなげます。
以下を全部貼り付けてください。
[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 だけで、新しい道具は入れません。
-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つを、ディスクイメージに並べます。
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バイトになっていることが分かる画面にしてください。
中身を目で確かめておきます。
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 で起動する
前回と同じコマンドで、ファイル名だけ変えます。
画面はこうなります。
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 Rust | Rustで書く現代的な入門。 説明が図解込みで、概念の理解だけでも読む価値がある |
| 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 に書いたのに、読み返すと0 | A20ラインを開ける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つ端末を開いて打ちます。
終了できたか確認します。
動いていません
入れた道具を消したい場合はこうします。
~/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 — Computer Science
- OSDev Wiki — Bootloader
- OSDev Wiki — Memory Allocation
- OSDev Wiki — Paging
- OSDev Wiki — Programmable Interval Timer
- OSDev Wiki — Context Switching
- OSDev Wiki — Multitasking Systems
- Wikipedia — Ralf Brown’s Interrupt List(BIOS呼び出し一覧の解説)
- Writing a Simple Operating System from Scratch
- cfenollosa/os-tutorial
- The little book about OS development
- Writing an OS in Rust
- MIT 6.828 / xv6
- Intel Software Developer Manuals
- NASM 公式ドキュメント
- QEMU 公式ドキュメント — x86 システムエミュレーション
次に読む
この記事は 【番外編】roadmap.sh の外 の 31 / 35 本目です。
ここは番外編です。 本筋から外れているので、飛ばして構いません。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
【番外編】OS自作。roadmap.sh の範囲外。

コメント