xv6 ソースコード読み会

2015/06/05 - 2015/06/07 にxv6のソース読み会があったので参加してきました。

読んだソースコードは swetland/xv6 で 64bit 版の xv6 です。

gdb で追えるようにした話はこちら。

History of CPU Architectures

OS を読む/書くにあたって CPU の仕様を見ることは避けられないので Intel CPU の歴史から。ソースを辿ったわけでは無いので間違いがあるかもしれません。

• 4004 (4bit cpu)
• 8080/8080a/Z80 (8bit cpu)
• Z80 が AH/AL, BH/BL, CH/CL, DH/DL, SP, IP で register は16bit だったとか
• 8086 (16bit cpu)
• 16bit に拡張するためにセグメントレジスタを使った
• i386(32/64bit cpu)
• eax register ができた
• セグメントレジスタの参照先を変えることでプロセス空間を変えたりできる
• segment register を変えることで virtual memory へもアクセスできる
• セグメントの対応表は GDT とかに入ってる

16 から 32 への拡張は命令セットはそんなに変わらなかったそうです。

8 から 16 、 32 から 64 がだいぶ変わったとか。

Intel 64 and IA-32 Architectures Software Developer Manuals

xv6 の boot は 16 bit から始まって 32bit へ拡張、最後に64bitになります。
何故16bitからスタートしているかは CPU の仕様だったりします。
ということでマニュアルを確認することに。
読んだ当時の2015年の Intel 64bit CPU の Manual はこちら。
Section 2.2 Modes of Operation によると、CPU は3つのモードがあるみたいです。

• protected mode
• native state of processor
• 32/64bit mode
• real-address mode
• 8086 processor
• 16bit mode
• 起動時はこのモード
• system management mode
• Power Management とかの System 周りをやるモード

なので xv6 の boot process は real-address mode から protected mode への移行ももちろん入っているわけです。

モードの変更方法もマニュアルに書かれていて、Section 9.9 Mode Switching の 9.9.1 Switching to Protected Mode にあります。

Interupput を disable にして、 CR0 register の PE (Protection Enable) flag をセットするとか具体的な手順が書かれています。

あと、Register の構成や GDT については Figure 2-2. System-Level Registers and Data Structures in IA-32e Mode に載っています。

仮想記憶のアドレスの切り替えやメモリ空間の拡張はセグメントレジスタの値を切り替えることによって行なっていて、その Segment Descripter の対応は GDT(Global Descripter Table)に入ってるみたいです。

なので GDT を切り替えることでアドレス空間を切り替えるような構成になってるみたいです。

Boot phase on xv6(16bit)

さてブートから読んでいきましょう、ということで kernel/bootasm.S を読みます。

.code16 から始まっているので 16bit mode で始まっていることが分かります。

cli で clear interrupt して ds,es,ss を zero fill 。

seta20.1 でinb/outb で 0xd1 と 0xdf を書き込み。

inb/outb は CPU が持ってる IO らしいです。

0xd1 は今から命令を書くよ、ってもので 0xdf は A20 を有効化する命令みたいです。

そして gdtdesc から lgdt (load gdt) して gdt をセット。

%cr0 に PE をセットして protected modeへ。

最後にljmpして 32bit mode になります。

この手順はマニュアルにそのまま書いてあったりします(Section 9-9)。

Boot phase on xv6(32bit)

protected mode になっても基本的には初期化。
32bit なので .code32 で始まっています。
register を初期化して bootmain って関数を call。

bootmain は C で書かれていて、 kernel/bootmain.c にあります。

mbheader にいろいろとベタで書かれていて、こいつは後から main に移る時に参照します。

bootmain は readseg してその値をメモリの 0x10000 に書き込みます。

readseg する場所は entry64.S が書きこまれているところです。

entry64.S を見ると分かるのですが、マジックナンバー 0x1BADB002 が書かれていて、read segした後にこいつがあるかチェックしています。

マジックナンバーが書かれてる = multi boot の entry が入ってる、ってことで entry の中身を展開して、 entry() を呼びます。

kernel/entry64.S に entry の中身が書かれていて、 page table の初期化とかをしています。

64bit mode (IA32e) にするために CR4.PAE を立てたり、 EFER.LME を立ててから

 ljmp します。

CR4.PAE は Physical Address Extension でメモリを 4GB 以上扱えるようにするもので、 64bit mode になる時に必須です。

EFER.LME の EFER は Extended Feature Enable Register でフラグを設定するレジスタです。

  LME は IE-32e Mode Enable で命令セットを64bit mode に切り替えるフラグです。(たぶん LongModeEnable)

これを有効にして ljmp すると 64bit mode になります。

Boot phase on xv6(64bit)

64bit になったらあとは main へ。

main は kernel/main.c にあります。

main では初期化を行ないます。

• uartearlyinit: uart (console)の初期化
• kinit1: カーネル用にメモリ確保。 freelist を作るだけ。
• kvmalloc: カーネルのページテーブルにメモリ割り当て。
• acpiinit: acpi を確認してCPU数をチェック。
• pinit: プロセステーブルの初期化。 lock を作るだけ。

とかを読みました。

main は最後に mpmain を呼びます。

mpmain は CPU ごとに呼ばれます。

mpmain は最終的に scheduler に落ちます。

syscall

次に syscall を読もう、ということに。
syscall の table は kernel/syscall.h に定義されています。
syscall は trap された後に kernel/syscall.c の syscall(void) で実行されます。
trap は alltraps から呼ばれるようになっていて、 alltraps は kernel/trapasm64.S に定義されています。
trap vector は kernel/vectors.S に定義されていて、 tools/vectors64.pl で生成されるみたいです。

sys_wait

具体的なシステムコールを読もうということで wait を読むことに。

sys_wait から wait() を呼んでます。

wait は kernel/proc.c にあります。

process table を lock して、子供を ptable から探してそれが終わるまで sleep してます。

sleep は 2つの spinlock を使って status を SLEEPING にして内部で sched() しています。

sched

sched は process の切り替えみたいです。kernel/proc.c にあります。

ちゃんとロックしてるか、interrupt が enable じゃないかなどをチェックしてから swtch() します。

proc.h に定義されている proc という名前の変数には __thread が付いていて、 thread local storage みたいです。

コメントによれば Per CPU Variable とのこと。

gcc の実装はこうなっていて、 fs や gs に CPU ごとに違う値が入ってるっぽいです。

thread local な値があるので並列にプロセスを実行できるってわけですね。

swtch

kernel/swtch64.S にあります。

レジスタの中身を退避してから stack pointer を切り替えることで process を切り替えてます。

実際 sp を切り替えたあとに gdb で bt すると別の back trace が得られました。

stack pointer が変わるのでこのCPUでこの先に実行される命令が変わるわけです。

scheduler

sched を読んだのて scheduler もきちんと読もう、ということに。

scheduler() は kernel/proc.c にあります。

mpmain から呼ばれています。

sti() を使ってinterrupt を enableに。

ptable を lock して、 RUNNABLE なものを拾ってきて switchuvm。

switchuvm はたぶん switch user virtual memory で gdt を切り替え。

これでプロセスの virutal memory を切り替えているみたいですね。

その後にまた swtch する感じです。

プロセスが終わったら switchkvm で kernel virtual memory に戻ってきます。

scheduler は ptable を無限ループで見続けてます。

sys_fork

あと1つくらい syscall を読もうよ、ということで fork。

fork の本体は kernel/proc.c にあります。

allocproc で新しいプロセスを作ってます。

copyuvm() で親の virtual memory をコピってますね。

子供側の return value は0なので eax を0にして state を RUNNING に。

親側に pid を返して終わり。

感想とか

当然といえば当然なのだけれど、OSはCPUの仕様に依存していて、特にbootとかはCPU側の手順に合わせる必要があって。

Page Table とかも IA32e では CPU 側が専用命令を持っているようで、OSが handle できない部分もあるんだなー、とか。

xv6 のコードはかなり短かくて、読みやすいとか玩具みたいとかのコメントがちらほら。

個人的にはマクロとかが無いので ctags とか gdb だけで追えて割と素直だなー、と。

PC とか SP とか register とか、CPUの機構知ってないと読むの大変な気もしますが、コンピュータアーキテクチャの講義でやってるのでハードウェアとソフトウェアの繋がりが見えて良いですね。

あと gdb が stack pointer の切り替えとか thread local な値も dump できるのがだいぶ便利で助かりました。

迷ったら x/20 とかするの便利。 x/20i とか x/20s とか x/20x とか。

これだけハードウェアに近い機構もサポートしている gdb の内部も気になるかもです。

CPU Architecture に詳しくなった気がする xv6 読み会でした。