前回は、カーネルの呼出し、キー割り込みと VRAM の予約領域の設定の話をした。
今回の主な話は次の 3 つ

○　拡張メモリ領域へのデータ転送
○　ページング機能の有効化
○　ページフォルトの実装

又、ソースはこちら

（言葉の定義）
以後、各処理の実行タイミングについて議論する際、対象となる処理がどのタイミングで実行されるのかを明確にするために、各プログラム(ルーチン)を起動してから呼ばれる順に再定義する。

・ファーストステージ
ブートセクタ(HDD の場合は MBR) に書かれたプログラム。主な処理は、FDD の初期設定と、以降のデータを適当なサイズ (onix では 10 セクタ) だけセカンドステージのメモリ領域に読み出す事。そして、セカンドステージへのジャンプ。

・セカンドステージ
ブートローダーのメインの処理。各種ハードウェア(HDD, キーボード, PIC)のチェックと初期設定。物理メモリサイズのチェックとブートパラメータの作成。A20 アドレスラインの初期化、そして GDT の初期化と登録。加えて、今回話をする拡張メモリ領域へのデータ転送処理を行っている。

・スタートアップルーチン(NEW)
新しくカーネルの前にセカンドステージから呼び出されるプログラム、今回話をする(仮)ページング機能の初期化と、ページング機能の有効化。そして、カーネルの呼出しを行っている。

・カーネル
onix のメインコンポーネント。

○　拡張メモリ領域へのデータ転送

先にも言ってしまったが、この処理はこれはセカンドステージにおける処理になる。これまで、FD からのデータの読み出しは、ファーストステージで行っている int $0x13 (ah = 0x20) によってのみおこなわれていた。32bit プロテクトモードに以降した後で、フロッピーからデータを持ってこようとすると、データ読み出しにおける FDD コントローラの制御処理を自前で用意しなければならず面倒なので、できれば bios コールを使いたい。けれども、リアルモードにおいて扱えるアドレス幅は 1MB なので、FDD の全ての内容をそのままメモリ上には置けない。
リアルモードにおいて、1MB 以降のメモリ領域に対してデータの転送を行う為に int $0x15 (ah = 0x87) bios コールを利用した。これによって 16MB までの領域に対してデータの転送が可能になる。
しかし、この処理はメモリの転送処理になるので、FDD から直接拡張メモリ領域に対して、データを転送する事はできない。なので、一端メモリの通常領域に対して FDD からデータを読み込んで、読み込んだデータを拡張メモリ領域に転送するという処理を繰り返す。
ソースでは、second.S の _block_copy が拡張メモリ領域に対してデータ転送処理を行う。

_block_copy:
	pusha
	movw $0x9000, %ax
	movw %ax, %es

	xor %eax, %eax
	movl $_ext_copy_gdt, %eax
	movl %eax, %esi
	addl $0x10, %eax

	movw $0xffff, (%eax)
	movl 0x24(%esp), %edx
	movl %edx, 0x02(%eax)
	movw $0x93, 0x05(%eax)

	addl $0x08, %eax
	movw $0xffff, (%eax)
	movl 0x28(%esp), %edx
	movl %edx, 0x02(%eax)
	movw $0x93, 0x05(%eax)

	xorl %ecx, %ecx
	movl 0x2c(%esp), %ecx
	movl $0x00008700, %eax

	int $0x15
	popa

	ret

bios は gdt を利用して拡張メモリ領域に対してデータの転送処理を行っている。利用するディスクリプタは 2 個目と 3 個目で、各ディスクリプタのフォーマットは次ページに書かれている。

http://www.delorie.com/djgpp/doc/rbinter/id/35/15.html

各セグメントのアクセス権限は、上記のサイトで意味ありげに書かれている 0x93 という値を利用してみる(恐らく推奨値)。
尚、gdt は、後に lgdt で登録している領域と分けている理由は特に無いが、メモリ領域を多目的に使いまわさなければならない程、メモリに貧しい時代には生きておらず、それよりも多目的に使うことによって生じるバグを恐れた為である。

_block_copy の呼出し側の関数 load_images() [calc.c] では、セカンドステージ以降のフロッピーデータを物理アドレス 0x93000 番地から始まるバッファ領域に置いて、0x100000 番地以降の領域へ転送している。
メモリの通常領域のバッファ領域の直後にデータを置かない理由は、通常領域の後方には bios の予約領域が存在するので、それらの地雷を避けるために 0x100000 番地以降に転送している。

　
○　ページング機能の有効化

アーキテクチャのアドレス変換のうち、一般に論理アドレスと呼ばれるものからリニアアドレスへの変換処理については、前回の gdt の初期化及び登録によって行われるようになった。今回は、リニアアドレスを物理アドレスに変換する仕組みについて、実装したものをみてゆく。
ページング機能の有効化は、cr0 レジスタの最上位ビットをアサートする事によって行われる。ブート時には、これはネゲートされている。単にこれをアサートしただけではシステムは止まる。これを有効にする為に、ページディレクトリテーブル及びページテーブル (以下、特に断らない限り、これらを区別なく "ページテーブル" と呼ぶ) の初期化を行う。この処理を行っているのが、startup.S である。

詳しい実装を見る前に、仕組みをおさらいする。
ハードウェアのページング機能が有効な場合におけるリニアアドレスから物理アドレスへの変換は、2階層のページテーブルを参照する。
具体的なアドレス変換の方法は、指定されたリニアアドレスの上位 10 bit が cr3 レジスタが参照するページディレクトリのオフセットになり、リニアアドレスの 12-21 bit が先に解決したページディレクトリのエントリが参照するページテーブルのオフセットになり、下位 12 bit が先に解決したページディレクトリが参照するページのオフセットになる。
ページテーブルの各エントリのビットフィールドは、次のページに詳しく書かれている。

http://caspar.hazymoon.jp/OpenBSD/annex/intel_paging.html

ページテーブルを実装する上での注意 (はまりやすいポイント) として次の 2 つが存在する。

・ページテーブルの場所
・ページングを有効にする場所

まずは "ページテーブルの場所" について話をする。
ページテーブルのエントリ数は各 1K 個で、各エントリのアドレスフィールドは先のリンクのサイトに書かれているようになっている。アドレスフィールドが 20bit になっているのは、ページテーブルのサイズが固定であり、各エントリが 4byte と決められている為、20bit で 32bit アドレス空間内でページテーブルを識別できる為である。つまりページテーブルは、 4K のアライメントで存在しなければならず、適当な場所にページテーブルが存在すると、ページディレクトリからページテーブルを見付けられなくなってしまう。
startup.S では、.org によって、下位 12bit が 0 になる適当な領域にページテーブルを置き、以後しばらくの間この領域をカーネルの予約領域として不可侵に扱わなければならない。
次に、"ページングを有効にする場所" について話をする。
ページテーブルを先に話したようなきちんとした場所に置き、cr3 レジスタにその物理アドレスを登録した場合、あとはページング機能を有効にするだけなのだが。これまた適当な場所 (設定したページテーブルにおいて、現在のアドレスポインタを解決した時に現在の命令が格納されている物理メモリにマッピングされない場所) に立っている場合、ページング機能を有効化した瞬間、迷子になる。
onix では (linux同様に) 、リニアアドレスの 0x00000000 番地から始まる 8MB と、0xC0000000 番地から始まる 8MB を物理アドレスの 0x00000000 番地から始まる 8MB にマッピングさせる。これは、この後に呼び出すカーネルをリニアアドレスの 0xC0000000 番地に置く為である。なので、ページディレクトリは、0番 と 1番、そして 768番 と 769番を設定し、各 2 つのエントリが同じページテーブルを参照し、そのページテーブルが物理アドレス 0x00000000 番地から 0x00800000 までの 8MB をマッピングするように設定する。
では、実際にページング機能を有効化させる処理 (startup.S) を見ていく。
Makefile でのプログラムの配置によって、スタートアップルーチンが置かれる物理アドレスは 0x90C00 番地になる。そして、second.S によってジャンプするアドレスも 0x90C00 番地になる。しかし startup.S では、リンカスクリプトでプログラムの .text セクションのアドレスを 0xC0000000 番地に指定している。これは、ページング機能を有効にしても、解決される物理アドレスは startup.S のプログラムが存在する場所になる為のものであるが、ページング機能が有効になるまで、このプログラムが参照する場所は嘘のアドレスになる。なので startup.S では、ページテーブルを参照する際、0xC0000000 を引いた値を求めるアドレスとしている (これによって、実際の物理アドレスを参照できる)。
又、ページテーブルの作成処理において登場する stosl という命令により、%edi が指す場所に %eax の値を格納する処理を行っている。そして、cr3 レジスタにページディレクトリを格納し、cr0 の最上位ビットをアサートする。
 
 
○　ページフォルトの実装

割り込みベクタ 0x0e のハードウェア割り込み処理を stage3.S で実装。

movl $0xb0000000, %eax
movl $0x10, (%eax)

という処理を実行した時、ページフォルトに登録した割り込みサービスルーチンが実行され、続きの処理が実行される事を確認できた。
又、割り込みサービスルーチンにおいて処理を停止させた時、cr2 レジスタにページフォルトが発生した時に読み書きされたリニアアドレスが入っている事を確認。まともなカーネルでは、ページテーブルを更新し、ここに物理アドレスをマッピングさせ、Present フラグを立てる。
現段階では、テストメッセージを吐いて処理を呼出元に返している。

今回話す内容は次の２つ。

○　物理アドレス全体のマッピング
○　プロセススイッチの仕組み

尚、最新のソースは、
http://sourceforge.jp/projects/onix/
の subversion リポジトリに置いてあり、不定期に更新する。
  
      　
○　物理アドレス全体のマッピング

前回、startup ルーチンにおける仮のページングの話をした。今回は、物理アドレス全体のページを対象としたページテーブルの初期化及び有効化の話をする。
前回話した仮のページングでは、物理メモリの下位 8 MB をリニアアドレス 0x00000000 - 0x00800000 と 0xC0000000 - 0xC0800000 にマッピングさせ、この領域に対するアクセスのアドレス変換を行わせるものであった。
今回話すページングは、マシンに搭載されている物理アドレス全体を 0xC0000000 から始まるリニアアドレスにマッピングさせる。何故、0xC0000000 (以下、ベースアドレス) なのかというと、ベースアドレスより上位のメモリ空間をユーザープロセスが使用する領域とす為である。別に 0xC0000000 という場所に特別な意味は無い。単純に、ユーザー空間とカーネル空間という概念的な区切り場所として分かりやすい場所である為である。実際に、0x80000000 で区切る OS の一つが Windows ある。
さて、物理アドレス全体をマッピングさせるわけなので、その実メモリの容量を知らなければならない。これを調べる為の方法が、int 0x15 (0xE801) の bios コールである。当然これはリアルモード中に調べなければならない。ブートローダで調べた実メモリの容量を、カーネルが知る為に、ブートローダがカーネルパラメータを作成し、カーネルに渡さなければならない。
onix では、物理アドレス 0x00080000 番地をカーネルパラメータの予約領域として、カーネル側でこれを参照する事でこれを実現する。
startup ルーチンにおける仮のページングでは、ポピュラーな 2 段のページング機構を利用していたが、onix のカーネルでは拡張ページを扱う。この為、cr3 が指すページディレクトリが直接ページを参照する。
拡張ページを扱う場合、CPU に対して次の 2 つの手続きが必要になる。

・CR4 レジスタの 5 bit目のページサイズ拡張ビットを立てる
・各ページディレクトリの下位 8 bit目の PS フラグを立て、直接ページを参照させる。

実際に試してはいないが、手続きが二つあるという事は部分的に通常ページを利用できるのだろう。
しかし、上述した処理を実行し、ページディレクトリのアドレスを cr3 レジスタに登録しても、それを実行した直後に処理が停止する。これは、cr4 レジスタ以外のレジスタがアドレスをリニアアドレスとして解釈する為である。
つまり、ブートシーケンスで初期化・登録した gdtr はリニアアドレスを参照する為、リニアアドレスの先頭付近を参照し、アドレス解決が出来きなくなる為に引き起こる。通常、この設定はカーネルが呼び出されてから、再度設定処理を行うのだが、リニアアドレスの最初の 1 ページ分を物理アドレスの先頭 1 ページにマッピングさせれば話が済むので、リニアアドレスの先頭ページをカーネルの予約領域として扱う事にする。
これで、物理メモリを支配的に扱えるようになった。
 
 
○　プロセススイッチの仕組み

プロセスの概念自体、まだ onix には存在しないのだが、マルチプログラミングを実現するカーネルの仕組みについて考えてみる。
これを実現する最も低レベル(*)な処理は、やはりプロセススイッチであろう。

(*) レイヤが低いという意味

プロセススイッチによって、実行中のプロセスが中断され、別のプロセスのプロセスが CPU を使う。そして一定時間経過してから、またプロセスに処理が切り替わる。
これをまともに動かす為には、以下の 2 つの仕組みが必要になる。

・各プロセスの状態を保存するデータ構造
・プロセス・スイッチ

ここでは、2 つ目に挙げたプロセス・スイッチの実現方法について考えてみる。
実行中のユーザープロセスの処理を切替えるという事は、次の 2 つを切替える事を意味する。

・ページテーブルの切替え
・プログラムカウンタの切替え

ページテーブルは、プロセスの付属情報としてページテーブルを持たせ、切替え時に cr3 レジスタをそれに書き換えればよい。
intel ではプログラムカウンタを切替える cpu 命令として、jmp 命令と ret 命令が存在する。
ここで、linux におけるプロセススイッチの実装を覗いてみる。linux におけるプロセススイッチの処理は、include/asm-i386/system.h でマクロ定義される switch_to で行われる。

14    #define switch_to(prev,next,last) do {                    \
15        unsigned long esi,edi;                        \
16        asm volatile("pushfl\n\t"        /* Save flags */    \
17                 "pushl %%ebp\n\t"                    \
18                 "movl %%esp,%0\n\t"    /* save ESP */        \
19                 "movl %5,%%esp\n\t"    /* restore ESP */    \
20                 "movl $1f,%1\n\t"        /* save EIP */        \
21                 "pushl %6\n\t"        /* restore EIP */    \
22                 "jmp __switch_to\n"                \
23                 "1:\t"                        \
24                 "popl %%ebp\n\t"                    \
25                 "popfl"                        \
26                 :"=m" (prev->thread.esp),"=m" (prev->thread.eip),    \
27                  "=a" (last),"=S" (esi),"=D" (edi)            \
28                 :"m" (next->thread.esp),"m" (next->thread.eip),    \
29                  "2" (prev), "d" (next));                \
30    } while (0)

ミソは、21 行目と 22 行目である。
通常、"call foo" のように関数を呼び出した場合、呼び出し側の次の命令アドレスをスタックに積み、リンカが解決した関数シンボルのアドレスにジャンプする。
関数側では ret 命令によって、スタックにつまれた戻りアドレスに対してジャンプする。
switch_to ではこれを利用し、スタックにスイッチするプロセスの命令アドレスを積み、__switch_to 関数 [arch/i386/process.c] にジャンプする。
__switch_to 関数内で cpu レジスタの退避等を行い、ret 命令を実行する。ret 命令によって切替えたプロセスの処理が行われる。

実に秀逸なこの動作を実現させる為には、プロセスのデータ構造がきちんと設計されていなければ当然できない上、fork や exec といった処理を実装しなければまともなプロセス管理はできない。
なので、これを実装するのはまだ先の話になりそうだ。

ATA デバイスとシステムとのデータ通信における、最もプリミティブな I/O 処理を行うデバイスドライバを書いたので、その話をしようと思ったが、ファイルシステムの話をするまでとっておく事にする。

前回プロセススイッチの仕組みの話をしたが、その前に、メモリ管理システムを実装しないと、まともなプロセス設計ができない。
今回は、メモリ管理の話を主にする。

ソースは、
http://sourceforge.jp/projects/onix/
でリポジトリが公開されている。

まず、一般的なプロセスの概論とメモリ管理との関連について述べる。
前回話したように、仮想メモリによって実メモリ空間を仮想メモリ空間にマッピングし、仮想的に実メモリを分割されたページの集合と考える。
なので、カーネルは物理メモリをページ毎に処理をするのが具合がいい。ただし、1 ページのサイズは 2^22(=8MB) なので、これをそのまま利用するには、使い勝手が悪いので、各ページに対して加工処理を行い、プロセスに提供する。

広義におけるオペレーティングシステムは、プロセスを単位とする集合である。カーネルも、システムの旗振り役のプロセスと考る。プロセスがメモリを所望した際カーネルがその要求に応えるのだが、先述したようにカーネルの一部の機能がページに対して加工処理を行って、要求に適合したサイズのメモリ領域をプロセスに渡し、カーネル側でどのプロセスにどれだけのメモリをわたしたのかという帳簿をつける。
ここでは、最終的にプロセスに渡されたメモリ領域を slab (木板) と呼び、これを管理するカーネルの機構をスラブアロケータと呼ぶ。
以降で、onix におけるスラブアロケータの概要について話をする。
 
システムには、複数の種類のスラブが存在し、それぞれの種類のスラブをまとめた集合を "スラブディレクトリ" と呼ぶ。
各ページはスラブディレクトリを持ち、スラブアロケータはページのスラブディレクトリに応じて、ページからスラブが取り出される。スラブサイズは先述した用にスラブディレクトリ毎に異なり、同サイズのスラブを大量に抱えこんだスラブディレクトリもあれば、小さいサイズから大きいサイズまでいろいろな種類のスラブを持ったスラブディレクトリもある。
又、物理アドレス空間において、物理メモリ全体を複数の領域に分割し、分割されたそれぞれの領域ごとに異なる種類のスラブディレクトリを持ったページ配置する。

スラブと連呼しているが、linux におけるそれとは違い、スラブキャッシュにない要求に対して動的にスラブを作成する事はせず、onix では固定長の複数種類のスラブを事前に用意しておき、その中から精査してプロセスに渡す処理を実装した。
多少のフラグメンテーションが起こる事が予想されるが、ハードリソースが豊かな時代では、その程度の事でプロセスが餓死する事は無い。

スラブディレクトリにある各スラブは、スラブディレクトリの管理オブジェクト(以下、スラブディスクリプタ)が持つビットマップによって行われる。各スラブは、ページのオフセットとスラブディスクリプタのビットマップ(*1)のオフセットで、スラブアロケータによって識別される。

*1:実際には、ビットではなく各スラブに対して 1 byte の情報を持たせる。
このようなデータ構造にした場合、ビット演算を行う事を考えれば、各スラブに対して高々数種類の情報しか持たせられない。このときスラブアロケータがあるスラブを見たとき、隣接するスラブがプロセスによって連続的に確保されたものなのかどうかわからない。
先にも述べたように、スラブに対してメモリ要求を行うのはプロセスだけなので、プロセスがメモリ確保を行う度に、どのスラブから何バイト確保したかのリストを作成する事で、プロセス管理機構側からどのスラブが連続的に利用されているのか把握できる。又、linux における逆マッピングの仕組みによって、スラブアロケータ側からも把握できる。