自作OSにページングを実装した
いやー、今年の夏は暑いっすねー。どうもお初にお目にかかります。空き地です。ハードのことはめっきりわからないソフトクリーム屋さんです。
なんかよくわからないままに開発を続けていた自作OSにページングを実装してみました。今回はその流れを書いていきたいと思います。
なんで実装したかというと、ただ単にかっこよかったからです。
データ構造を実装する
ページングを実現するには、PDT、PDE、PT、PTEなどのデータ構造を実装する必要があります。では、簡単にこのデータ構造体を説明します。
まず、ページそのものの説明です。
ページの説明
このように、4KiBのメモリを一つの領域として考え、それをページと呼びます。
次にPTE（ページテーブルエントリ）です。PTEはページそのものを指しています。C言語のポインタのポインタのようなものです。
先頭20bitはこのPTEが指しているページの先頭の物理アドレスを指しています。その次にいる3bitはOS側が自由に使用できるビットです。
このビットに関してはCPUは関知しません。
それ以降のビットはフラグですが、ここでは軽く説明するだけにします。
まあ、全部重要なので、各自ググりましょう。
| フラグ | 意味 |
| G | Global Pageに設定する |
| D | このページに書き込みが行われたか |
| A | このページが今までにアクセスされたことがあるかのフラグ |
| C | このPTEが指すページのキャッシュを有効化するフラグ |
| W | このビットが立っていると、このページはwrite throughされることになる |
| U | このビットでそのページがカーネル用なのかユーザ用なのかを判別できる |
| R | このビットが立っているとそのページは書き込み可能ということになる。プログラムの実行コードはこのビットが下りている。 |
| P | このページが現在RAM上に存在しているかのフラグ。HDD等にスワップされたときこのフラグは下りる。 |
次にページテーブルです。ページテーブルは単にPTEを1024個集めただけです。
次にページディレクトリエントリです。
| フラグ | 意味 |
| G | このページテーブルのページはグローバルとして扱われる。 |
| S | ページサイズ。ここで、4KB or 4MBを指定できる。 |
| A | このページテーブルが今までにアクセスされたことがあるかのフラグ |
| D | このビットが立っていると、このページテーブルはキャッシュされない |
| W | このビットが立っていると、このページテーブルはwrite throughされることになる |
| U | このビットでそのページテーブルがカーネル用なのかユーザ用なのかを判別できる |
| R | このビットが立っているとそのページテーブルは書き込み可能ということになる。プログラムの実行コードはこのビットが下りている。 |
| P | このページテーブルが現在RAM上に存在しているかのフラグ。HDD等にスワップされたときこのフラグは下りる。 |
次にページディレクトリテーブルです。ページディレクトリテーブルはページディレクトリが1024個集まったものです。簡単ですね。PDTはいわばページを遠隔的にまとめ上げているような存在です。
これまでのデータ構造が理解できればページングの理解は8割できたといっても過言ではないですね。
ここで、やっとく実装というかコードを見せようと思ったんですが、仮想アドレスの説明がまだでした。仮想アドレスの説明の後でここまでの実装を見せます。
仮想アドレス
次に、仮想アドレスについて説明していきます。今回はx86アーキテクチャがターゲットなので32bitの仮想アドレスになります。仮想アドレスは物理アドレスのように線形的なものではなく、そのアドレス自体に意味を持っています。ざっと次のような感じです。
このようにうまく出来てるわけですよ。ページングを考え出した人に感謝しましょう。 では次に仮想アドレスから物理アドレスを計算してみます。 
まあこんなところでしょう。これで、仮想アドレスがわかれば、PDT=>PDE=>PT=>PTE=>ページの物理アドレスというように理解できるようになっています。つまり、仮想アドレスとPDTがわかれば仮想アドレスでアドレッシングができるわけです。では実際の実装面を見ていきます。
データ構造の実装
データ構造の実装。
typedef unsigned long page_table_entry_t; typedef unsigned long page_directory_entry_t; typedef unsigned long virtual_address32; typedef unsigned long virtual_address64; typedef page_table_entry_t *page_table; typedef page_directory_entry_t *page_directory;
まあそうだろうなっていう感じですね。データ構造とか言いながら構造体はいないです。次に定数です。
#define MM_PAGE_SIZE 4096 #define KERNEL_PHYSICAL_ADDR 0x00010000 #define VIRTADDR_PTE_MASK 0x000003FF #define VIRTADDR_PTE_SHIFT 12 #define VIRTADDR_PDE_MASK 0x000003FF #define VIRTADDR_PDE_SHIFT 22 #define MM_NUM_PTE 1024 #define MM_NUM_PDE 1024 #define MM_PAGE_DIRECTORY_SIZE (sizeof(page_directory_entry) * MM_NUM_PDE) #define MM_OK 0 #define MM_ERROR (-1) #define MM_4KIB_ALIGN (0xfffff000) #define MM_KERNEL_LAND_MEMORY 0x00000000 #define MM_KERNEL_LAND_SIZE 0x40000000 #define MM_USER_LAND_MEMORY 0x40000000 #define MM_USER_LAND_SIZE 0xc0000000 #define VIRT_KERNEL_HEAP 0x30000000 #define MM_1MIB 0x00100000 #define MM_4MIB 0x00400000 #define MM_USER_PT (MM_USER_LAND_MEMORY - (3 * MM_1MIB)) #define MM_KERNEL_PT (MM_USER_PT - (MM_1MIB)) #define MM_PDT (MM_KERNEL_PT - MM_4MIB) #define MM_KERNEL_HEAP_ADDR (MM_PDT - MM_4MIB) #define MM_KERNEL_STACK_BASE_ADDR MM_KERNEL_HELP_ADDR
ほーん。という感じです。
で、補助用の関数がこんな感じです。上の定数が登場する感じです。（”感じ”が多い感じですね。結論:フィーリングは重要）
inline u8_t pte32_is_present(page_table_entry_t pte)
{
return (u32_t)pte & (u32_t)PTE32_PRESENT;
}
inline u8_t pte32_is_writable(page_table_entry_t pte)
{
return (u32_t)pte & (u32_t)PTE32_WRITABLE;
}
inline void pte32_set_flags(page_table_entry_t *entry, unsigned long flags)
{
*entry |= flags;
}
inline void pte32_clear_flags(page_table_entry_t *entry, unsigned long flags)
{
*entry &= ~flags;
}
inline void pte32_set_addr(page_table_entry_t *entry, u32_t addr)
{
addr &= PTE32_PHYSICAL_ADDR;
*entry |= addr;
}
inline void *pte32_get_addr(page_table_entry_t entry)
{
return (void *)((u32_t)entry & (u32_t)PTE32_PHYSICAL_ADDR);
}
inline u8_t pde32_is_present(page_directory_entry_t pde)
{
return (u32_t)pde & (u32_t)PDE32_PRESENT;
}
inline u8_t pde32_is_writable(page_directory_entry_t pde)
{
return (u32_t)pde & (u32_t)PDE32_WRITABLE;
}
inline void pde32_set_flags(page_directory_entry_t *pde, u32_t flags)
{
*pde |= flags;
}
inline u8_t pde32_clear_flags(page_directory_entry_t *pde, u32_t flags)
{
*pde &= ~flags;
}
inline void pde32_set_pt_addr(page_directory_entry_t *pde, u32_t addr)
{
addr &= PDE32_PT_ADDR;
*pde |= addr;
}
inline void *pde32_get_pt_addr(page_directory_entry_t pde)
{
return (void *)((u32_t)pde & (u32_t)PDE32_PT_ADDR);
}
まあ、なんとなく予想できるんですが、初歩的なビット演算のオンパレードです。面白みがないですよねぇ。OS開発で一機能を作るときはつまらん初歩的なAPIの開発から始まるもんです。しょうがないっすね。まあ、悩まなくていいので楽といえば楽です。
ページングへの移行
普通の人ならページング？は？そんなん知らんわって感じだと思うんですが、ここまで読んでいただけてありがたいです。皆さんシステムプログラミングの沼に落ちましょう。まあ、ここまで読んでくれた変人なら以上のデータ構造の実装は余裕だと思うので、ページングへの移行を説明したいと思います。
なんか、ページングへの移行とか言うと、くそむずい気がしますが、そんなことはありません。超簡単です。移行するだけならcr0レジスタのPGフラグを立ててやればいいだけです。PGは最上位ビットなので、0x80000000をorしてやればOKなわけです。しかしながら、コンフィグレーションレジスタは直接値をいじれないので、eaxなどの汎用レジスタを介して行います。 あとですね、仮想アドレスのセクション？で言ったとおり、仮想アドレスがあってもPDTがわからないとアドレッシングはできないので、PDTのアドレスを教えてやる必要があります。これも超簡単で、cr3レジスタにPDTのアドレスを渡してやるだけでOKです。この２つの処理をstore_cr3関数とgo_paging関数で実装します。
;; void *store_cr3(void *p); store_cr3: mov eax, [esp+4] mov cr3, eax ret ;; void go_paging(void); go_paging: cli push eax mov eax, cr0 or eax, 0x80000000 mov cr0, eax pop eax sti ret
まあこんなところなんですが、読みやすくするためにCのラッパ関数を作ります。
static void go_paging32(void *pdt)
{
store_cr3(pdt);
go_paging();
}
引数にはPDTのアドレスを取ります。ひとまずこれでページングには移行できそうです。ここらへんはCPU扱ってる感が出てシステムプログラミングでしか味わえない興奮が溢れてきます。ここまでは難易度:易ですが、こっから難易度:普通-くらいになっていきます。
仮想アドレスでカーネルを動かす
ページングが有効化されているときに、ページテーブルとかに定義されていないアドレスにアクセスしようとするとページフォルト例外が発生します。これはカーネルのバイナリの実行でも起きます。つまり、ページング移行前に、カーネルのバイナリがマップされている領域をPTEとして設定しておく必要があります。これからページングを実装しようとする自作OS開発者さん、カーネルがマップされている物理アドレス覚えてます？少なくとも、僕は忘れてました。ローダ部分を読んで思い出しましょう。このロードしたアドレスと仮想アドレスを一致させてマップすることで、カーネルに大きな変更を加えることなくカーネルを動作させることができます。
余談ですが、Linuxなどの強いOSたちは、ロードしたアドレスとマップする仮想アドレスを一致させるような甘いことはせず、ページング移行まで実行バイナリとの差分を計算して動作させているようですよ。詳しくはググってください。
以上のようなことを実装するわけですが、こんな感じで実装しました。詳しくは僕のGitHubを見てください。あ、そうそう。この僕のOSはMITライセンスが適用されているんで、これを守った上で私的目的で利用していいですよ。
u8_t init_virtual_memory_management()
{
//0x00000000~用
page_table kernel_table;
//0xc0000000~用
page_table user_table;
page_table paging_info_table;
page_table pdt_region;
page_directory directory;
current_page_directory = directory = MM_PDT;
memset(MM_PDT, 0x00, MM_4MIB);
/*
* 0x00000000~
*/
kernel_table = MM_KERNEL_PT;
/*
* 0xc0000000~
*/
user_table = MM_USER_PT;
paging_info_table = ((page_table)kernel_table + (MM_NUM_PTE * (MM_KERNEL_PT / MM_4MIB)));
pdt_region = ((page_table)kernel_table + (MM_NUM_PTE * (MM_PDT / MM_4MIB)));
map_page(directory, kernel_table, MM_KERNEL_LAND_MEMORY, 0x00000000, PDE32_PRESENT | PDE32_WRITABLE);
map_page(directory, user_table, MM_USER_LAND_MEMORY, 0xc0000000, PDE32_PRESENT | PDE32_WRITABLE);
map_page(directory, paging_info_table, MM_KERNEL_PT, MM_KERNEL_PT, PDE32_PRESENT | PDE32_WRITABLE);
map_page(directory, pdt_region, MM_PDT, MM_PDT, PDE32_PRESENT | PDE32_WRITABLE);
go_paging32(directory);
printk("MM_USER_PT:0x%x\n", MM_USER_PT);
printk("MM_KERNEL_PT:0x%x\n", MM_KERNEL_PT);
printk("MM_PDT:0x%x\n", MM_PDT);
printk("paging_info_table:0x%x\n", paging_info_table);
return MM_OK;
}
そうですね、まあココらへんは実装が重要ではなく、カーネルを動作させることが重要なので、流れさえ掴んでくれればって感じです。なので、こんなコードより仮想アドレスを物理アドレスにマップするところが重要だったりするんでしょうか。ということで、そこら辺もコード載せておきます。
inline void create_pt32(page_table table, u32_t physical_addr, u32_t virtual_addr)
{
int i;
page_table_entry_t *pte;
for(i = 0;
i < MM_NUM_PTE;
i++, physical_addr += MM_PAGE_SIZE, virtual_addr += MM_PAGE_SIZE){
pte = pt32_get_pte(table, virtual_addr);
pte32_set_flags(pte, PTE32_PRESENT | PTE32_WRITABLE);
pte32_set_addr(pte, physical_addr);
}
}
u8_t map_page(page_directory directory, page_table ptable, void *physical_address, virtual_address32 virtual_address, u32_t flags)
{
page_directory_entry_t pde;
memset((void *)ptable, 0x00, MM_PAGE_SIZE);
create_pt32(ptable, physical_address, virtual_address);
pde = pd32_get_pde(directory, virtual_address);
pde32_set_flags(pde, flags);
pde32_set_pt_addr(pde, (u32_t)ptable);
return MM_OK;
}
ちなみに、ここらへんで気づいた方はいると思うんですが（この汚いコードでは無理っぽい）、PDTやらPTのメモリアドレスは決め打ちです。そっちのほうが簡単で管理しやすいですからね。まあこんな感じで、init_virtual_memory_management関数を呼び出すといろいろ設定を行い、結果的にページングが有効化されます。
本当に実装できたのか確認する
有効化した後に次の様な処理を書いてみてください。
char *p = (対応付済みの仮想アドレス) *p = 0;
これで例外が発生しなければページングに移行できています。いえーい。
デマンドページング
実を言うとデマンドページングについて書くつもりはなかったのですが、時間があるので書くことにしました。
デマンドページングとはPTEの設定を動的に行うことです。最小限のPTEだけ設定しておき、要求が発生したときにPTEを設定してあげるという方式です。Linuxはこれで動いているらしいです。適当にこんな感じじゃねって実装してみたんですが、大したことはないです。デマンドページングについて次の知識があれば余裕で実装できます。（一応図も入れておきます。）
・ページフォルト例外が発生したときにページをPTEに設定してあげる。
・ページフォルト例外が発生したとき、アクセスしようとしたアドレスはcr2レジスタに格納されている。
・エラーコードはちゃんとpopする。
では実装を見ていきます。
ページフォルトハンドラ
ページフォルトハンドラはその名のとおり、ページフォルト例外が発生したときに呼び出されます。実装はこんな感じです。
;; ページフォルト例外のハンドラ asm_inthandler0e: pop eax push es push ds pushad mov eax, esp push eax mov ax, ss mov ds, ax mov es, ax call page_fault_handler pop eax popad pop ds pop es iretd
ここで重要なのは、先頭の”pop eax”です。エラーコードをpopしています。これをpopしないと、正しいアドレスに戻れなくなるので注意してください。僕はこれで半日潰しました。
次に、このハンドラから呼び出されているpage_fault_handler関数です。これはみんな大好きCで書かれてます。
int *page_fault_handler(int *esp)
{
virtual_address32 virt_addr = load_cr2();
char addr_msg[32];
memset(addr_msg, 0, 32);
puts("Page Fault!");
sprintf(addr_msg, "address:0x%x", virt_addr);
puts(addr_msg);
if(virt_addr < (MM_KERNEL_LAND_MEMORY + MM_KERNEL_LAND_SIZE)){
resolve_kpage_fault(virt_addr);
}else{
puts("Kernel Panic: page mapping error.");
}
return 0;
}
load_cr2関数を呼び出しているのはcr2に例外が発生したときにアクセスしようとしたアドレスが書き込まれているからです。ちなみに、load_cr2関数はアセンブリ関数です。定義はあとで書きます。（書かなくてもわかると思いますが）
途中のifですが、これはページフォルトが発生した領域がユーザ空間なのかカーネル空間なのかで分岐しています。ユーザ空間の実装はまだなのでカーネルパニックを起こします。（無限にページフォルトしまくる）カーネル空間で発生している場合、resolve_kpage_faultを呼び出し、デマンドページングを施します。
load_cr2関数
load_cr2:
mov eax, cr2
ret
ほらね、簡単だったでしょ。数バイトの関数ですよ全く。
resolve_kpage_fault関数
void resolve_kpage_fault(virtual_address32 virt_addr)
{
page_table_entry_t *pte;
page_table pt;
virtual_address32 masked_virtaddr = virt_addr & MM_4KIB_ALIGN;
// カーネルPTの羅列の中から今回の仮想アドレスに適したPT（アドレス）を計算する
pt = MM_KERNEL_PT + (MM_NUM_PTE * (virt_addr / MM_4MIB));
puts("-------\npage resolver start");
pte = pt32_get_pte(pt, masked_virtaddr);
map_page(current_page_directory, pt, masked_virtaddr, masked_virtaddr, PDE32_PRESENT | PDE32_WRITABLE);
puts("-------\npage resolver result");
printk("required virtual address:0x%x\n", virt_addr);
printk("new page_table addr:0x%x\n", pt);
printk("masked addr:0x%x\n", masked_virtaddr);
printk("head pte addr:0x%x\n", pte);
}
この関数がデマンドページングの本体って感じですね。やってることは単純で仮想アドレスをカーネルのPTのPTEに設定しているだけです。楽勝ですね。Linuxが使っているからといって怯えちゃだめってことですね。これをやると、ページングの設定がされていないページにアクセスしても、カーネルが勝手に設定をしてくれます。
とまあ、ここまでダラダラやってきましたが、ページングについてはこんなもんでしょうか。まだまだ初歩的なページング実装ですので、今後の成長に期待しましょう。
ちなみに、無限にページフォルト例外を吐きまくるとはこういうことです。
実際成功すると、何も出ないので面白くありません。（達成感とコンピュータアーキテクチャの素晴らしさは実感する）
ですが、成功したときの写真を載せておかないと、本当に実装できたのか疑われそうなので、デバッグメッセージ付きの写真貼っときます。次のようなコードをページングが有効化された後に埋め込みます。
char *p = (char *)(0x10000000);
*p = 0;
puts("I'm back!");
memcpy(p, "unko", 3);
p[4] = 0;
puts(p);
char *buf = (char *)kmalloc(10);
printk("returned addr: 0x%x\n", (u32_t)buf);
memcpy(buf, "unko", 3);
buf[4] = 0;
puts(buf);
kfree(buf);
puts("fin");
結果はこんな感じです。*p = 0でページフォルトが発生しているところがpaging_info_table:0x3fc00000の後です。無事動いてますね。
まとめ（というか雑談）
まあそんなこんなでページングの実装してまいりました。初投稿だったのでかなり読みにくい記事になっていると思いますが、ここまで読み進めてくださってありがとう御座います。きっと皆さん自作OSを開発してページングを実装したくなったことでしょう。システムプログラミングはVRやらWebやら機械学習やらに比べ、地味ですが、ハマるとやばいので皆さんこぞってシステムプログラミング沼にダイブしましょう。以上空き地がお届けしました。
参考にした文献
Daniel P. Bovet, Marco Cesati(2007)『詳解Linuxカーネル第３版』（杉田由美子ほか訳）オーム社
参考にしたWebページ
OSDev Paging: https://wiki.osdev.org/Paging
０から作るOS開発ページングその１ページとPTEとPDE: http://softwaretechnique.jp/OS_Development/kernel_development07.html
こにゃにゃちわー。
LinuxとEmacsをこよなく愛する高専生です。
今日もレポートに負けずプログラム書くぞー！
