6.828: Operating System Engineering (56)

ちょっと試験の文脈 (?) を先に確認しといた方が良いな、ということで確認を。
最初から確認してみます。

    // should be able to allocate three pages

pp0、pp1、pp2 を page_alloc してそれぞれが NULL ではなく異なる値であることを確認してます。その後、

    // temporarily steal the rest of the free pages

で、page_free_list を退避して LIST_INIT することで空きを無くしてます。その上で

    // should be no free memory

pp 渡して page_alloc して -E_NO_MEM が戻ってくることを確認。また、0x0 番地にページが割り当てられていないことを確認。

    // there is no page allocated at address 0

で、ここからが本番で free な page が無いので

    // there is no free memory, so we can't allocate a page table

page_insert は失敗することを確認した後に pp0 を page_free して

    // free pp0 and try again: pp0 should be used for page table

0x0 番地にページは割り当てられてないことを確認
0x0 な va を pp1 に page_insert して成功することを確認
pp0 に割り当てられてたページは page table になっていることを確認
0x0 な va に pp1 なページが割り当てられていることを確認
pp1 の参照カウントが 1
pp0 の参照カウントが 1

次は

    // should be able to map pp2 at PGSIZE because pp0 is already allocated for page table

pp2 を PGSIZE (4096 というか 0x1000) 番地に page insert できるはずだけど、それって pp0 が PGSIZE な va の page table になってるから、というナニ。

PGSIZE な va を pp2 に page_insert して成功することを確認
PGSIZE な va に pp2 なページが割り当てられていることを確認
pp2 の参照カウントが 1

この時点で free memory はたしかに無いですね。

    // should be no free memory

で、次に pp2 を再度 PGSIZE 番地に page_insert します。

    // should be able to map pp2 at PGSIZE because it's already there

PGSIZE な va を pp2 に page_insert して成功することを確認
PGSIZE な va に pp2 なページが割り当てられていることを確認
pp2 の参照カウントが 1

で、pp2 が free list に無いことを確認とあるな。

    // pp2 should NOT be on the free list
    // could happen in ref counts are handled sloppily in page_insert

ここでは page_alloc して -E_NO_MEM が戻ることを確認しとりますが、コメントによると page_insert での参照カウントのハンドルが微妙とかってどーゆー意味だろ。
スルーして次ですが、

    // check that pgdir_walk returns a pointer to the pte

PGSIZE の page table の先頭アドレスを取得して PGSIZE を渡された pgdir_walk の戻り値と page table の先頭アドレス + PTX(PGSIZE) の値を比較してます。
あら、pgdir_walk の戻りは pte ってことで良かったんですね。
で、次は権限云々とのこと。

    // should be able to change permissions too.

PTE_U を渡して PGSIZE な va を pp2 に page_insert して成功することを確認
PGSIZE な va に pp2 なページが割り当てられていることを確認
pp2 の参照カウントが 1
PGSIZE の pte の値について PTE_U なビットが立っていることを確認
boot_pgdir[0] も PTE_U なビットが立っていることを確認
- あ、ここは page table 側のみ PTE_U だと親のパーミッションが優先されるので page directory も PTE_U を立ててるんでした。忘れてた。

次に空きはないことを確認して

    // should not be able to map at PTSIZE because need free page for page table

PTSIZE なので pp0 な page table が指せる範疇をギリ超えてるのか。ええと、pp0 を使って PTSIZE な va について page_insert して失敗することを確認してます。
そろそろ試験に失敗してるあたりになるのかな。次は PGSIZE な va を pp1 に page_insert するようです。

    // insert pp1 at PGSIZE (replacing pp2)

PGSIZE な va を pp1 に page_insert して成功することを確認
- 権限は 0 を渡している
PTE_U な権限が pte に付いてないことを確認

このあたりから文脈の確認が必要というか理解できてないあたりに突入。

    // should have pp1 at both 0 and PGSIZE, pp2 nowhere, ...

これ pp1 が、というよりは 0x0 番地と PGSIZE 番地が pp1 を、という方が実際に近い気はしますがスルー。

0x0 な va が指してる物理アドレスと pp1 を物理アドレスに変換した値が同値であることを確認
PGSIZE な va が指してる物理アドレスと pp1 を物理アドレスに変換した値が同値であることを確認
pp1 の参照カウントが 2
pp2 の参照カウントが 0

なるほど。で、次が

    // pp2 should be returned by page_alloc

page_alloc したら pp2 の値が割り当てられることを確認してます。どーゆーことかというと異なるページが割り当てられたら今まで割り当てられてたページは解放される、ということなのか。確かにソレを昨日盛り込んだ記憶があります。
次が失敗してる断点になるのかな。

    // unmapping pp1 at 0 should keep pp1 at PGSIZE

0x0 に割り当てられた pp1 をアンマップするが PGSIZE は pp1 を指しとけよ、ってことなのかな。

0x0 番地を page_remove
0x0 な pte は ~0 になっていること
- page_remove 時に ~0 で pte を初期化するのかな
PGSIZE な va が指してる物理アドレスと pp1 を物理アドレスに変換した値が同値であることを確認
pp1 の参照カウントが 1
pp2 の参照カウントが 0

む、page_remove 時に参照カウントが減るのか、減るな。あと、削除時に 0 を memset してますが、同時に pte の値を ~0 にすれば良いのかな。
次は

    // unmapping pp1 at PGSIZE should free it

とのこと。

PGSIZE 番地を page_remove
0x0 な pte は ~0 になっていること
PGSIZE な pte は ~0 になっていること
pp1 の参照カウントが 0
pp2 の参照カウントが 0

で、

    // so it should be returned by page_alloc

page_alloc で戻ってくるのは pp1 の値。先の試験で pp2 も確保済みなので

    // should be no free memory

空きは無い、と。~0 がパスすればこのあたりまでは大丈夫そうかな。残りはもうちょいです。

    // forcibly take pp0 back

boot_pgdir の 0 番目の要素は pp0 なページの物理アドレスを指していることを確認
boot_pgdir の 0 番目の要素を 0 初期化
pp0 の参照カウントが 1 であることを確認
pp0 の参照カウントを 0 で初期化

無理矢理元に戻しちゃうのか。

    // check pointer arithmetic in pgdir_walk

pp0 を page_free する
va に PGSIZE * NPDENTRIES + PGSIZE を代入
- 4096 * 1024 + 4096 って何でしょ
- 確保可能な page table の領域サイズ + 1 ページ?
ptep に va な pte を確保して代入
ptep1 に va な page table のアドレスを取得して格納
ptep と ptep1 + PTX(va) の値が正しいかを確認
boot_pgdir[PDX(va)] に 0 代入 (後始末)
pp0->pp_ref に 0 代入 (後始末)

    // check that new page tables get cleared

pp0 な番地を 0xff で埋める
pp0 を page_free する
0x0 番地な pte を確保
ptep に pp0 な番地 (リニアアドレス) を代入
確保したページテーブルの要素は PTE_P が立っていないことを確認
- ページテーブルの全ての要素について確認
boot_pgdir[0] に 0 代入 (後始末)
pp0->pp_ref に 0 代入 (後始末)

あとは後始末だけですね。

    // give free list back

退避してた page_free_list を復帰して

    // free the pages we took

pp0、pp1、pp2 を page_free しておしまい。

修正する前に

確認しとく。今パスしない assert は以下。

    // unmapping pp1 at 0 should keep pp1 at PGSIZE
    page_remove(boot_pgdir, 0x0);
    assert(check_va2pa(boot_pgdir, 0x0) == ~0);

page_remove したら何がどうなっていないといけないか、というと

boot_pgdir[0x0] & PTE_P が真
*1[PTX(va)] & PTE_P が真
PTE_ADDR(((pte_p *)KADDR(PTE_ADDR(boot_pgdir[0x0]))[PTX(va)]) が ~0

う、check_va2pa の末端 return までいったら PTE_ADDR なフィルタがかかっているので ~0 が戻るってありえねー、って思ったら存在フラグを落とせば良いことにようやく気づきました。とほほ杉。
とゆーことはどーすりゃ良いんでしょ。

続き

存在フラグを落とす処理を盛り込んでも上手く処理できぬ。なんでかねー、と言いつつ色々見回してみたところ、直前で以下な状態になってて

    // should have pp1 at both 0 and PGSIZE, pp2 nowhere, ...
    assert(check_va2pa(boot_pgdir, 0) == page2pa(pp1));
    assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
    // ... and ref counts should reflect this
    assert(pp1->pp_ref == 2);
    assert(pp2->pp_ref == 0);

その後、page_remove でこうならないと駄目とのこと。

    // unmapping pp1 at 0 should keep pp1 at PGSIZE
    page_remove(boot_pgdir, 0x0);
    assert(check_va2pa(boot_pgdir, 0x0) == ~0);
    assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
    assert(pp1->pp_ref == 1);
    assert(pp2->pp_ref == 0);

これは page_remove の実装が駄目ってことですね。というか基本的に remove されたら *pte をアレすりゃ良いだけなのか。
ということで page_check 手続きの assert 全てパスしました。長かった。実は boot_map_segment 手続き未実装なので、そちら対応ができたら Page Table Management なソースを晒す方向で。

*1:pte_p *)KADDR(PTE_ADDR(boot_pgdir[0x0]