xv6-riscv 第5 ~ 6章のまとめ

xv6の課題の続きで、今回は5章と6章をまとめます

第5章 xv6 lazy page allocation

github.com

課題

  • Eliminate allocation from sbrk() (easy)
  • Lazy allocation (moderate)
  • Lazytests and Usertests (moderate)

課題は3つに分かれていますが、全てLazy allocationを実装しようというものになっています。
課題前の実装ではsbrkを呼び出すと、即座にプロセスに割り当てられるメモリを増やします。 ただ、sbrkを呼び出したからと言って、プロセスはすぐに割り当てられたメモリを使うとは限りません。 そこで、この課題ではsbrkを呼び出したときにはメモリの割当を行わず、実際に使用するときにメモリを割り当てる実装を行います。

考え方は至ってシンプルですが、影響箇所が割と多い課題でした。

  • 考慮が必要なケース

    • モリーのコピー
      • まだ割当がされていない領域はコピーせずスキップする
    • モリーの削除
      • まだ割当がされていない領域は削除せずスキップする
    • モリーの読み込み/書き込み
      • まだ割当がされていない領域に読み込み/書き込みを行う場合には、そのタイミングでメモリ割り当ても一緒に行う
  • バリデーション

    • sbrkで確保した以上のメモリーを要求された時
    • kallocが失敗した時
    • user stackを侵食しようとした時

第6章 Copy-on-Write Fork for xv6

github.com (cowtestは通るようになったが、usertestsはまだうまく行っておらず成功してない)

課題

Implement copy-on write(hard)

COW forkを実装しようという課題です。

通常のforkでは、forkが行われた時に親から子へメモリの内容をコピーします。 ただ、内容に変更があるまでは親子共に同じものであるため、 forkの時ではなく書き込みがあったときにメモリの内容をコピーするように遅延しようというものになっています。

第一感は複雑そうな課題がでたなぁという印象でしたが、仕組みは意外とシンプルでした。

1 . fork時にページエントリを作成するが、親子共に同じ物理アドレスを参照するようにする
2. 1で作成したページエントリは、読み込み専用かつCOWで対象というフラグも立てておく
3. もし書き込みがあった場合にはページフォルトのトラップが発生する
4. トラップハンドラでページフォルトをキャッチして、もしCOWの対象であればコピーする

これに加えて、メモリ解放時のロジックも変更する必要がありました。
今までは一つの物理アドレスは一つのページエントリから参照されていたので、何も考えずにメモリ開放するだけでOKでした。
しかし、今回から複数のページエントリから一つの物理アドレスを参照される可能性がでるようになりました。
そのため、物理アドレスがいくつのページエントリから参照をされているかを管理しておき、メモリ解放が要求された時に参照が0だった場合のみ、実際にメモリ解放を行うというロジックに変更しました。

「reference count」と名前がついてましたが、GCの仕組みでもこんな感じを見たことがあったので理解はすんなりできました。


長い道と思いましたが、残り課題が5個になりました。 この調子で続けていきたいですね!