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個になりました。 この調子で続けていきたいですね!

xv6-riscv 第2, 4章のまとめ

xv6の課題の続きで、今回は2章と4章をまとめます (3章の課題難しくてスキップしている)  

第2章 system calls

github.com

課題

System call tracing (moderate)

システムコールを呼ばれるたびにログに吐き出すシステムコールを作る課題

課題の意図は、システムコールの追加方法を学ぼうというものっぽいので、誘導にそってやれば特に難しいことはなかったです。

解くのにかかった時間: 1時間

Sysinfo (moderate)

残メモリと使用中のプロセス数を取得するシステムコールを作る課題

こちらも誘導が丁寧なので上からやっていけば簡単に終わりました。 強いて言えばkernelからuserにsysinfoの情報を渡すときに、copyoutを使わなければ行けないのが少々トリッキーなくらいでした。

解くのにかかった時間: 1時間

第4章 Traps and system calls

この3章、4章あたりから課題が急に難しくなってきた感じです。

github.com

課題

RISC-V assembly (easy)

RISC-Vのアセンブラを学ぼうという課題で、読めば終わるものでした

解くのにかかった時間: 20分

Backtrace (moderate)

backtrace関数を作ろうという課題。

stack frameとtrap frameを混同しておりめっちゃ時間がかかりました。 この課題で必要なのはstack frameでそれっぽいことは別紙に書いてあります。 https://pdos.csail.mit.edu/6.828/2020/lec/l-riscv-slides.pdf

stack frameの構造さえわかってしまえば、空になるまでframeを戻っていく簡単な課題でした。

上記の誤解を気づけたのは、gdbのbacktraceコマンドで今回の正解が表示させてみたり、 frame infoコマンドと私が書いたコードの差分をとってみたり、結構泥臭いことやってました。

解くのにかかった時間: 6時間

Alarm (hard)

この課題では、テストコードで割り込み上限回数とコールバック関数が与えられます。
そして、テストコードが断続的にタイマー割り込みを発生させるので、割り込みの回数を記憶しておき割り込み上限回数まで達したらコールバックを呼び出すという課題です。

割り込み時、どうやってコールバック関数を呼び出すかが難問でした。
正直わからなかったので先人たちの知恵を借りたところ、epcを直接書き換えれば良いということがわかり、目からウロコでした。
同時に、このままwebエンジニアとして生きていたら、一生仕事でこのコード書くことないんだろうなと思いました。

解くのにかかった時間: 3時間

xv6-riscv 第1章のまとめ

MITで行われているxv6について授業の資料が公開されていたので、先々週くらいからチャンレンジしています。 4章くらいまで終わったので、まずは1章を軽くまとめてみます。

はじめに

xv6とは

近代UNIX系OSの元となったUnix v6を移植したものです。

Unix v6とは

  • エッセンスは現在のOSにも通づるものがある
  • 約1万行程度とOSにしては少ない分量で書かれているのでOSの全体像を学習するのにとても役立つ
  • ただし、古いC言語PDP-11という古いマシン(CPU? プロセッサ?)用に記述されているので読みづらい部分がある

という特徴があります

xv6は

  • C言語はC99以降のものなり、またriscvで動作するようになっているので、2020年度の我々にも読みやすいものとなっている
  • 教育用なのでコードや注釈もわかりやすいものになっている
  • 講義の資料や課題とかまでついている

となっており、OSの全体像を把握したい人にはうってつけのものになっています。

ドキュメントなど

このページの上にあるxv6というタブからソースコードと資料(pdf)をダウンロードできます。 また、各授業ごとに課題もついております。 https://pdos.csail.mit.edu/6.S081/2020/schedule.html

私は英語が得意ではないので、この日本語にしてくれた方の資料を読みつつ、気になるところがあれば英語の資料にあたる方法をとっています。 https://www.sugawara-lab.jp/lecture.html

進め方としては

  1. その章の資料を読む
  2. 課題を読んで、実際のソースコードを改良して機能追加をする
  3. 付属してあるテストコードを実行してテストが通るまで改良を続ける
  4. 次の章を読む

といったサイクルを繰り返します

課題は半日以上かかる歯ごたえがあり、点数とかも表示されるのでゲーム感覚で楽しめてます。 脱線になりますが、私は勉強するときは手を動かしたいタイプで、また独学だと課題に正解しているかわからないことが多いので、今回のようなテストコードが付属してある形式はとても好みです。

本章

本文のまとめとかはよくあると思うので、課題のほうを中心にまとめてみます。 githubのコードもあげています。ただ、C言語が詳しくなくテストに通っているだけで模範解答では全く無いと思います。

各課題の難易度は、Easyだと1時間未満、Moderateは1 ~ 2時間、Hardはそれ以上かかる見込みだそうです

https://pdos.csail.mit.edu/6.S081/2020/labs/guidance.html

第1章 Xv6 and Unix utilities

github.com

Boot xv6 (easy)

xv6を起動する課題。

OSごとに手順がまとまっており、特につまるところはありませんでした。 https://pdos.csail.mit.edu/6.S081/2020/tools.html

sleep (easy)

実装済みのシステムコール sleep をコマンドラインから呼び出してみようという課題。

おそらく課題の意図としては、ディレクトリ構造やシステムコールの呼び出し方を把握するだけのもので特に難しいことはなかったです。 誘導もとても丁寧でした。

解くのにかかった時間: 20分

pingpong (easy)

forkとpipeを駆使して、子プロセスでping、親プロセスでpongと出力しようという課題。

割とよくある課題で本文中にもforkやpipeの解説があったため、割と簡単でした。

解くのにかかった時間: 30分

primes (moderate)/(hard)

ハードなのでスキップしてます。

find (moderate)

簡易版findコマンドを作ろうという課題。

これは仕様の勘違いで時間がかかりました。
find a b は、aディレクトリとbディレクトリから再帰的にファイルを検索するものかと思ってました。
実際には./a/b/*以下を再帰的に検索するもので、カレントディレクトリを起点に、bディレクトリから再帰的にファイルを検索するものだったそうです。

その他には、文字列にstrcmpを使わなければいけないなど、C言語っぽいところで詰まったことが多かったです。

解くのにかかった時間: 2時間

xargs (moderate)

簡易版xargsコマンドを作ろうという課題。

実装してみて、なるほどこんな簡単な仕組みで動いていたのかという印象を受けました。 xargsは結構すんなり作ることができましたが、前課題のfindに依存しておりそっちが壊れていたのに気づかず、時間がかかってしまいました。

解くのにかかった時間: 2時間

elf形式の解析をrustでやってみてる

5年くらい前からxv6のコードを読みたいなーと、何度かチャレンジして失敗している。新人教育してくれた先輩がカーネル屋さんだったり組み込みの方が多かったので、なんとなく低レイヤーに憧れがあるのだと思う。

チャレンジ失敗している理由としては、普段業務でやってないブートローダー・メモリ配置・アセンブラあたりで躓くことが多いので、今回はまずリンカ・ローダの本を読み進めている。

www.amazon.co.jp

限られた環境のみだが、elf形式の解析(readelfの再実装)がなんとなく動く状態になってきた。今回は勉強兼ねてrustに挑戦してみている。

github.com

つまづいたところ

手を動かしたので、ELFの構造と中に何が入っているのかはなんとなく理解できるようになった。 あと、rustのセットアップ、以前はvscodeの設定を色々弄る必要があった覚えがあったが、すんなり終わったので敷居だいぶ下がったなぁと思った。

今週末4連休なので、簡易ローダづくりを終わらせたい  

参考にしたページ

https://msyksphinz.hatenablog.com/entry/2020/08/08/040000
https://tomo-wait-for-it-yuki.hatenablog.com/entry/2019/01/05/161331
https://uclibc.org/docs/elf-64-gen.pdf