xv6ノート
これはxv6を読んだ際のノート。
参考資料は「9. 参考リンク」と「10. 参考書籍」に列挙した。
また、ノートの節々でどの参考資料を参照したのかを記した。
環境
使用したソースコードやツールのバージョン。
- xv6 commit eeb7b415dbcb12cc362d0783e41c3d1f44066b17
- Linux 4.19.128-microsoft-standard #1 SMP Tue Jun 23 12:58:10 UTC 2020 x86_64 GNU/Linux
- Debian 9.11
- gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1)
- GNU ld (GNU Binutils for Debian) 2.28
- GNU Make 4.1
- GNU objcopy (GNU Binutils for Debian) 2.28
- GNU objdump (GNU Binutils for Debian) 2.28
- GNU readelf (GNU Binutils for Debian) 2.28
- QEMU emulator version 2.8.1(Debian 1:2.8+dfsg-6+deb9u8)
- GNU gdb (Debian 7.12-6) 7.12.0.20161007-git
1. ビルドと実行
ビルドと実行は、makeとmake qemuで行えるとREADMEに記載がある。
また以下の記事からmake qemu-noxでXなしで実行でき、make qemu-nox-gdbでXなしでgdbでデバッグできることが分かる。
「xv6のデバッグ環境をつくる」（リンク2）
コンパイル時にレベル2の最適化オプションが付与されているので、デバッグの際に変数の中身が見れないことがある。 そのときは、MakefileのCFLAGSからオプションO2を削ると変数の中身が見える。
Makefile
#CFLAGS = -fno-pic -static -fno-builtin -fno-strict-aliasing -O2 -Wall -MD -ggdb -m32 -Werror -fno-omit-frame-pointer
CFLAGS = -fno-pic -static -fno-builtin -fno-strict-aliasing -Wall -MD -ggdb -m32 -fno-omit-frame-pointer
シングルスレッドでの動作を確認したいときは、MakefileのCPUS変数の値を1にする。
Makefile
#CPUS := 2
CPUS := 1
また、wsl上でqemuやgdbを動かしていて、キーボード入力などのためにXを使いたいとき（qemu-noxで実行するとシリアルポートを使うことになる）は、windows側でXサーバを起動し、wsl側の環境変数DISPLAYを<win側のvethのアドレス>:0として、make qemu-gdbを実行する。
XサーバにVcXsrvを使う場合は以下の記事が参考になる。
「AsTechLog WSL2＋Ubuntu 20.04でGUIアプリを動かす」（リンク26）
2. xv6.imgのビルド
makeの実行
2.1. ターゲットxv6.img
Makefileの最初のターゲットがxv6.imgなので、makeを実行するとxv6.imgが作られる。
xv6.imgはbootblockとkernelから次のように作られる。
- ddコマンドで0埋めされた512*10000=5.12MBのxv6.imgファイルを作る
- ddコマンドでxv6.imgファイルの頭（0セクタ目）にbootblockを差し込む
- ddコマンドでxv6.imgファイルの先頭から512バイトの位置（1セクタ目）にkernelを差し込む
Makefile
xv6.img: bootblock kernel
dd if=/dev/zero of=xv6.img count=10000
dd if=bootblock of=xv6.img conv=notrunc
dd if=kernel of=xv6.img seek=1 conv=notrunc
2.2. Makefile内の変数
ターゲットbootblockとkernelを見る前に、Makefile内の変数を確認する。
変数CCがgccなのでコンパイラにはgccを使う。
変数CFLAGSは後ろの方が環境によって変わるようなので、makeを実行して中身を確認すると以下のようになっていることが分かる。
CFLAGS = -fno-pic -static -fno-builtin -fno-strict-aliasing -O2 -Wall -MD -ggdb -m32 -Werror -fno-omit-frame-pointer -fno-stack-protector
各オプションの意味はマニュアル「Using the GNU Compiler Collection (GCC)」（リンク3）を見るとだいたいわかる。
知りたいオプションをOption Summaryページでページ内検索して、各ページに飛ぶのと楽。
| Option | 意味 |
|---|---|
| fno-pic | マニュアルにこのオプションの記載はないが、fpicオプションはあるのでその否定だとわかる。出力を位置独立コード（Position Independent Code）にしない。位置独立コードに関しては「リンカ・ローダ 実践開発テクニック」（書籍1）に詳しく載っている。 |
| static | 動的ライブラリを静的リンクする。 |
| fno-builtin | 組み込み関数を使わないようにする。 |
| O2 | レベル2の最適化オプションを有効にする。 |
| Wall | 警告オプションを有効にする。 |
| MD | 拡張子「*.d」ファイルを作成し、依存関係にあるファイル名を書き込んでくれる。 |
| ggdb | gdbで使用するデバッグ情報を作る。 |
| m32 | int, long, ポインタを32bitにする。 |
| Werror | 全ての警告をエラーにする。 |
| fno-omit-frame-pointer | fomit-frame-pointerオプションの否定。関数呼び出しにて必ずベースポインタを使う。 |
| fno-stack-protector | fstack-protectorオプションの否定。バッファオーバーフローやスタックスマッシング攻撃をチェックするコードを追加しない。 |
変数LDがldなのでリンカはldを使うことが分かる。
変数LDFLAGSもCFLAGS同様にmakeを実行して出力を確認すると以下のようになっていることが分かる。
LDFLAGS = -m elf_i386
オプションの意味はマニュアル「Using ld The GNU linker ld version 2 January 1994」（リンク4）で確認できる。このマニュアルはIndexからオプションが簡単に探せる。
| Option | 意味 |
|---|---|
| m | 指定したリンカをエミュレートする。ここではelf_i386をエミュレート。elfについては「リンカ・ローダ 実践開発テクニック」（書籍1）に詳しく記載されている。 |
変数OBJDUMPはobjdump。
変数OBJCOPYはobjcopy。マニュアル「3 objcopy」（リンク5）によると、Oオプションで出力ファイルのフォーマットを指定できる。また、出力フォーマットにバイナリを指定した場合、オブジェクトには以下の3つのシンボルが作成され、プログラムからデータにアクセスすることができる。
- _binary_<ファイル名>_start
- _binary_<ファイル名>_end
- _binary_<ファイル名>_size
例えば画像ファイルをオブジェクトファイルに変換し、プログラム内で上記シンボルからアクセスすることができる。
これらのシンボルはリンカldのbオプションでバイナリを指定した際にも作成される。
2.3. ターゲットbootblock
bootblockは次のように作られる。
- bootmain.cをコンパイルする。nostdincオプションはシステムからヘッダーファイルを探さないようにするオプションで、Iオプションで指定されたディレクトリからヘッダーファイルを探す。つまりここではカレントディレクトリから探す。
- bootasm.Sをコンパイルする。
- bootblock.oとしてbootasm.oとbootmain.oをリンクする。Nオプションはtextセクションとdataセクションを読み書き可能にする。また、dataに関するセグメントをページに揃えないようにする。eオプションはエントリポイントを指定する。ここではstartをエントリポイントとしている。Ttextオプションはtextセグメントの開始アドレスを設定する。ここでは0x7C00にしている。0x7C00はBIOSがMBRをロードするアドレス。
- objdumpを使ってbootblock.oをディスアセンブリしてbootblock.asmを作成する。このファイルは使用しないが、アセンブリを見たいときに少し便利。
- objcopyを使ってbootblock.oからbootblockを作る。Sオプションは再配置情報とシンボル情報を削除する。Oオプションで出力をbinaryとする。jオプションは出力するセクションを指定する。つまりtextセクションだけをコピーする。
- sign.plを実行してbootblockをMBRにする。bootblockが510バイトより大きいときはエラーにする。そうでない場合は509バイト目までを0埋めして、510～511バイトにブートシグニチャ0x55AAを追加する。
Makefile
bootblock: bootasm.S bootmain.c
$(CC) $(CFLAGS) -fno-pic -O -nostdinc -I. -c bootmain.c
$(CC) $(CFLAGS) -fno-pic -nostdinc -I. -c bootasm.S
$(LD) $(LDFLAGS) -N -e start -Ttext 0x7C00 -o bootblock.o bootasm.o bootmain.o
$(OBJDUMP) -S bootblock.o > bootblock.asm
$(OBJCOPY) -S -O binary -j .text bootblock.o bootblock
./sign.pl bootblock
2.4. ターゲットkernel
kernelの依存先としてentryotherとinitcodeがあるが、それらについては後ほど読むことにする。
kernelは次のように作られる。
- ターゲットkernelに依存している他のターゲットを作成する。 ひとつめが$(OBJS)になっていて、GNU makeの暗黙のルールにより、変数OJBSに記載されているオブジェクトが*.cや*.Sから作成される。 この時、vectors.oの作成のところでvectors.cもvectors.Sもないので、Makefile内のターゲットvectors.Sが実行され、vectors.plが実行される。 vectors.plはvector0からvector255までの割り込みハンドラが定義されたvectors.Sを作成する。 makeの暗黙のルールについてはマニュアル「GNU make」（リンク6）の「10 Using Implicit Rules」に記載されている。
- 各オブジェクトをリンクし、バイナリファイルとしてkernelを作る。
Tオプションはリンカスクリプトを指定する。ここではkernel.ldを使う。kernel.ldを読むと、以下の設定をしている。
このリンカスクリプトにより、作成されるkernelは仮想アドレス0x80100000で実行され、物理アドレス0x100000にロードされることが分かる。
- 出力フォーマットをelf32-i386、出力アーキテクチャをi386、エントリポイントを_startに設定。
- textセクションの開始アドレスを0x80100000、ロード先アドレスを0x100000に設定し、オブジェクトファイルのtextセクション等を配置。
- オブジェクト内でetextシンボルが定義されていない場合は、textセクションの後ろにetextシンボルを定義する。
- textセクションの後ろに、オブジェクトファイルのrodataセクション等を含むrodataセクションを配置。
- rodataセクションの後ろに、stabセクションを配置。オブジェクトファイルのstabセクションをシンボル__STAB_BEGIN__と__STAB_END__で挟む。
- stabセクションの後ろに、stabstrセクションを配置。オブジェクトファイルのstabstrセクションをシンボル__STABSTR_BEGIN__と__STABSTR_END__で挟む。
- stabセクションの後ろの次のページ境界に合うように（0x1000にアラインメント）し、シンボルdataを定義。
- シンボルdataの後ろに、各オブジェクトファイルのdataセクションを含むdataセクションを配置。
- dataセクションの後ろにシンボルedataを定義。
- シンボルedataの後ろに、各オブジェクトファイルのbssセクションを含むbssセクションを配置。
- シンボルendを定義。
- 各オブジェクトファイルのeh_frameセクションとnote.GNU-stackセクションをDISCARDで破棄。
- objdumpでディスアセンブリしてkernel.asmを作成。
- objdumpでkernelのシンボルテーブルを出力し、sedで加工してkernel.symを作成。
Makefile
kernel: $(OBJS) entry.o entryother initcode kernel.ld
$(LD) $(LDFLAGS) -T kernel.ld -o kernel entry.o $(OBJS) -b binary initcode entryother
$(OBJDUMP) -S kernel > kernel.asm
$(OBJDUMP) -t kernel | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > kernel.sym
3. カーネルのロード
make qemuからentryの実行まで。
3.1. bootasm.S
bootasm.SではGDTを作り、プロテクトモードへ切り替え、bootmain関数を呼び出す。
A20ラインの有効化
最初にBIOSが立ち上がり、xv6.imgの最初の510～511バイト目の0x55AAを見てブートセクタだと判断して物理アドレス0x7C00にディスクから1セクタ（512バイト）分読み込む。
つまりxv6.imgのbootblockの部分が0x7C00に読み込まれる。
bootblockの頭の方はbootasm.Sなので、startから実行が開始される。
cli命令で割り込みを無効化する。
axレジスタを使い、各セグメントレジスタ（ds, es, ss）の値を0に初期化する。
次に、キーボードコントローラを使ってアドレスバスのA20ライン以上を使えるように設定を行う。
このA20ラインや、セグメント機構、ページング、割り込み等については「はじめて読む486」（書籍2）に詳しく記載されている。
まだアドレスバスが0～19までしか無く、20bitで1MBのアドレスを使用していた時代、0xFFFFFの次0x100000へのアクセスで0x0にアクセスすることができたらしく、その性質を利用したプログラムも書かれていたらしい。その互換性を維持するために起動時はアドレスバスがA19までしか使用できないようになっているらしいので、この上限を開放する必要がある。
A20ラインの有効化にはいくつかの方法があり、その内のひとつとしてキーボードコントローラを使用した方法がある。
キーボードコントローラの仕様については「Keyboard scancodes」（リンク7）の「The AT keyboard controller」に載っている。
上記リンクによると、ポート0x64からの読み込みはステータスレジスタの内容となり、書き込みはコマンドとして解釈される。
また、ポート0x60への書き込みはコマンドのデータとして解釈される。
ラベルsata20.1では、ポート0x64からステータス0x2以外が読み出せるまでループしている。 ステータスは0bitがアウトプットバッファを示し、1bitがインプットバッファを示していて、0が空で1がフル。 バッファが空だった場合、ポート0x64にコマンド0xd1を書き込む。0xd1はアウトプットポートにデータを書き込むコマンド。 ラベルsata20.2のループでバッファが空であることを確認できるまで待ち、ポート0x60にデータ0xdfを書き込む。データ0xdfをアウトプットポートに書き込むと、A20ラインが有効になる。
bootasm.S
.code16 # Assemble for 16-bit mode
.globl start
start:
cli # BIOS enabled interrupts; disable
# Zero data segment registers DS, ES, and SS.
xorw %ax,%ax # Set %ax to zero
movw %ax,%ds # -> Data Segment
movw %ax,%es # -> Extra Segment
movw %ax,%ss # -> Stack Segment
# Physical address line A20 is tied to zero so that the first PCs
# with 2 MB would run software that assumed 1 MB. Undo that.
seta20.1:
inb $0x64,%al # Wait for not busy
testb $0x2,%al
jnz seta20.1
movb $0xd1,%al # 0xd1 -> port 0x64
outb %al,$0x64
seta20.2:
inb $0x64,%al # Wait for not busy
testb $0x2,%al
jnz seta20.2
movb $0xdf,%al # 0xdf -> port 0x60
outb %al,$0x60
GDTの作成とロード
プロテクトモードに切り替える準備をする。
プロテクトモードのセグメント機構ではセグメントディスクリプタを使うので、事前にGDTを作ってlgdt命令で設定する必要がある。GDTに関しても「はじめて読む486」（書籍2）に詳しく記載されている。
lgdt命令ではgdtrにGDTのサイズとアドレスをセットする。
サイズは2バイトで、ラベル間の差を取って（gtddesc - gdt - 1）求める。
アドレスにはgdtラベルのアドレスをセットする。
gdtラベルからGDTのエントリが書かれてる。全部で3エントリ。セグメントディスクリプタを作成するSEG_ASMマクロはasm.hに定義されている。
p2align 2で2 * 2 = 4バイトでアラインメントする。
セグメントディスクリプタの構造はプロセッサのマニュアル「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）の「vol.3A 3.4.5 Segment Descriptors」に記載されてる。
作成されるセグメントディスクリプタの内容は、ビルドで作成されたbootblockバイナリを見て、マニュアルの図と照らし合わせるとわかりやすい。
SEG_ASMマクロと引数の一部を電卓で計算すると、コードセグメントディスクリプタの方に値0x9Aが入っているのが分かるので、bootblockをxxdで開いてlessにパイプして9aでサーチすると位置0x60にGDTを見つけることができる。
GDTに作成される3つのエントリは以下のようになっている。
エントリ1: NULL。8バイト全て0。
エントリ2: コードセグメントディスクリプタ。値は16進数で FF FF 00 00 00 9A CF 00。
エントリ3: データセグメントディスクリプタ。値は16進数で FF FF 00 00 00 92 CF 00。
コードセグメントディスクリプタの値はリミット値が0xFFFFF、セグメントベースが0x00000000、属性が0x9AC。属性は以下のようになってる。
type 1100
S 0
DPL 01
P 1
AVL 1
O 0
D 0
G 1
リミット値は0xFFFFFだけど、Gフラグが1だからページ単位になって4K倍されるので0xFFFFF * 4096 = 4GB。
データセグメントディスクリプタの値もコードセグメントディスクリプタとだいたい同じになっている。属性は0x92C。
bootasm.S
# Bootstrap GDT
.p2align 2 # force 4 byte alignment
gdt:
SEG_NULLASM # null seg
SEG_ASM(STA_X|STA_R, 0x0, 0xffffffff) # code seg
SEG_ASM(STA_W, 0x0, 0xffffffff) # data seg
gdtdesc:
.word (gdtdesc - gdt - 1) # sizeof(gdt) - 1
.long gdt # address gdt
asm.h
#define SEG_NULLASM \
.word 0, 0; \
.byte 0, 0, 0, 0
// The 0xC0 means the limit is in 4096-byte units
// and (for executable segments) 32-bit mode.
#define SEG_ASM(type,base,lim) \
.word (((lim) >> 12) & 0xffff), ((base) & 0xffff); \
.byte (((base) >> 16) & 0xff), (0x90 | (type)), \
(0xC0 | (((lim) >> 28) & 0xf)), (((base) >> 24) & 0xff)
#define STA_X 0x8 // Executable segment
#define STA_W 0x2 // Writeable (non-executable segments)
#define STA_R 0x2 // Readable (executable segments)
プロテクトモードへの切り替え
cr0のプロテクトモード有効フラグ（0bit）を立ててプロテクトモードに切り替える。
GDTのコードセグメントディスクリプタを使ってプロテクトモードでの実行を開始するために、ファージャンプをする。csレジスタの値はファージャンプでなければ変更できないため。
セグメントディスクリプタは1エントリ8バイトなのでljmp $8, $start32で、NULLの次のコードセグメントディスクリプタを指定する。
bootasm.S
# Switch from real to protected mode. Use a bootstrap GDT that makes
# virtual addresses map directly to physical addresses so that the
# effective memory map doesn't change during the transition.
lgdt gdtdesc
movl %cr0, %eax
orl $CR0_PE, %eax
movl %eax, %cr0
//PAGEBREAK!
# Complete the transition to 32-bit protected mode by using a long jmp
# to reload %cs and %eip. The segment descriptors are set up with no
# translation, so that the mapping is still the identity mapping.
ljmp $(SEG_KCODE<<3), $start32
mmu.h
#define SEG_KCODE 1 // kernel code
#define SEG_KDATA 2 // kernel data+stack
start32ラベルから32bit命令で実行が始まる。
ds, es, ssにデータセグメントディスクリプタを設定する。
fs, gsに0を設定する。
espにstartのアドレスを設定する。startは0x7C00なのでそこから下に向かってスタックが伸びていくことになる。
bootmain関数を呼び出す。bootmain関数はbootmain.cに定義されいる。
bootasm.S
.code32 # Tell assembler to generate 32-bit code now.
start32:
# Set up the protected-mode data segment registers
movw $(SEG_KDATA<<3), %ax # Our data segment selector
movw %ax, %ds # -> DS: Data Segment
movw %ax, %es # -> ES: Extra Segment
movw %ax, %ss # -> SS: Stack Segment
movw $0, %ax # Zero segments not ready for use
movw %ax, %fs # -> FS
movw %ax, %gs # -> GS
# Set up the stack pointer and call into C.
movl $start, %esp
call bootmain
もしもbootmainがリターンした場合、ポート0x8a00にデータ0x8ae0を送る。
Bochsのマニュアル「Bochs Developers Guide」（リンク9）の「Chapter 3. Advanced debugger usage」から、ポート0x8A00はコマンドレジスタのサーバになっていて、コマンド0x8ae0はデバッガプロンプトに戻ることが分かる。そしてデバッガプロンプトに戻るということはCtrl-Cと同義であると書いてある。
デバッガプロンプトに戻った後、無限ループする。
bootasm.S
# If bootmain returns (it shouldn't), trigger a Bochs
# breakpoint if running under Bochs, then loop.
movw $0x8a00, %ax # 0x8a00 -> port 0x8a00
movw %ax, %dx
outw %ax, %dx
movw $0x8ae0, %ax # 0x8ae0 -> port 0x8a00
outw %ax, %dx
spin:
jmp spin
3.2. bootmain関数
この関数はディスクからカーネル（elfバイナリ）を物理アドレス0x100000にロードし、entry関数を実行する。
「2.1. ターゲットxv6.img」で見たように、kernelは1セクタ目から存在している。
readseg関数で1セクタ目から4096バイト分をelfhdrポインタに読み込む。
ここでは読み込みを開始するオフセットに0を渡しているが、readseg関数は読み込みを1セクタ目から開始するので問題ない。
マジックナンバーを確認し、読み込んだデータが少なくともelfヘッダを持っていることを確認する。
elfの構造に関しては「リンカ・ローダ 実践開発テクニック」（書籍1）に詳しく記載されている。
読み込んだデータ（カーネル）から、プログラムヘッダを取得する。elfヘッダのアドレス（0x10000）にelfhdr構造体のphoffフィールド（プログラムヘッダのオフセット）を加算することでプログラムヘッダが始まるアドレスが求められる。
プログラムヘッダの個数はelfhdr構造体のphnumフィールドから得られる。
プログラムヘッダの開始アドレスと個数が分かったので、for文で各プログラムヘッダをproghdr構造体に取り出し、以下のようにセグメントをディスクから読み込む。
- プログラムヘッダからロード先物理アドレス（paddrフィールド）を取得する。
- readseg関数でロード先物理アドレスに、ディスク上のセグメント開始位置（offフィールド）からセグメントサイズ（fileszフィールド）の分だけ読み込む。
- もしも、セグメントがメモリ上に展開されるサイズ（memszフィールド）が、セグメントサイズ（fileszフィールド）よりも大きい場合、stosb関数でセグメントの後ろをメモリ上に展開されるサイズまで0埋めする。
これでカーネルの全てのセグメントがメモリ上の適切な位置にロードされた。
elfバイナリ（カーネル）のエントリーポイントをelfヘッダのentryフィールドから取得する。関数として呼び出すため、関数ポインタにキャストして取得している。ここではエントリーポイントはentry.Sの_startラベル。
最後にエントリーポイントを関数として呼び出し、カーネルの実行を開始する。
elf.h
#define ELF_MAGIC 0x464C457FU // "\x7FELF" in little endian
// File header
struct elfhdr {
uint magic; // must equal ELF_MAGIC
uchar elf[12];
ushort type;
ushort machine;
uint version;
uint entry;
uint phoff;
uint shoff;
uint flags;
ushort ehsize;
ushort phentsize;
ushort phnum;
ushort shentsize;
ushort shnum;
ushort shstrndx;
};
// Program section header
struct proghdr {
uint type;
uint off;
uint vaddr;
uint paddr;
uint filesz;
uint memsz;
uint flags;
uint align;
};
bootmain.c
void
bootmain(void)
{
struct elfhdr *elf;
struct proghdr *ph, *eph;
void (*entry)(void);
uchar* pa;
elf = (struct elfhdr*)0x10000; // scratch space
// Read 1st page off disk
readseg((uchar*)elf, 4096, 0);
// Is this an ELF executable?
if(elf->magic != ELF_MAGIC)
return; // let bootasm.S handle error
// Load each program segment (ignores ph flags).
ph = (struct proghdr*)((uchar*)elf + elf->phoff);
eph = ph + elf->phnum;
for(; ph < eph; ph++){
pa = (uchar*)ph->paddr;
readseg(pa, ph->filesz, ph->off);
if(ph->memsz > ph->filesz)
stosb(pa + ph->filesz, 0, ph->memsz - ph->filesz);
}
// Call the entry point from the ELF header.
// Does not return!
entry = (void(*)(void))(elf->entry);
entry();
}
プログラムヘッダとセクションヘッダの情報はobjdumpで確認できるので、以下のようにここで処理されているプログラムヘッダの値を確認できる。
プログラムヘッダは次の3エントリ。仮想アドレスと物理アドレスは「2.4. ターゲットkernel」で見たリンカスクリプトkernel.ldにより設定されている。
- textセクション。物理アドレス0x100000にロードする。
- dataセクション。物理アドレス0x108000にロードする。
- スタック。サイズが0。
objdump -ph kernel | lessの出力結果
kernel: file format elf32-i386
Program Header:
LOAD off 0x00001000 vaddr 0x80100000 paddr 0x00100000 align 2**12
filesz 0x0000788c memsz 0x0000788c flags r-x
LOAD off 0x00009000 vaddr 0x80108000 paddr 0x00108000 align 2**12
filesz 0x00002516 memsz 0x0000d4a8 flags rw-
STACK off 0x00000000 vaddr 0x00000000 paddr 0x00000000 align 2**4
filesz 0x00000000 memsz 0x00000000 flags rwx
Sections:
Idx Name Size VMA LMA File off Algn
0 .text 00006e92 80100000 00100000 00001000 2**4
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 .rodata 000009ec 80106ea0 00106ea0 00007ea0 2**5
CONTENTS, ALLOC, LOAD, READONLY, DATA
2 .data 00002516 80108000 00108000 00009000 2**12
CONTENTS, ALLOC, LOAD, DATA
3 .bss 0000af88 8010a520 0010a520 0000b516 2**5
ALLOC
4 .debug_line 00002694 00000000 00000000 0000b516 2**0
CONTENTS, READONLY, DEBUGGING
5 .debug_info 000104e2 00000000 00000000 0000dbaa 2**0
CONTENTS, READONLY, DEBUGGING
6 .debug_abbrev 0000390e 00000000 00000000 0001e08c 2**0
CONTENTS, READONLY, DEBUGGING
7 .debug_aranges 000003a8 00000000 00000000 000219a0 2**3
CONTENTS, READONLY, DEBUGGING
8 .debug_loc 00005239 00000000 00000000 00021d48 2**0
CONTENTS, READONLY, DEBUGGING
9 .debug_ranges 00000748 00000000 00000000 00026f81 2**0
CONTENTS, READONLY, DEBUGGING
10 .debug_str 00000e48 00000000 00000000 000276c9 2**0
CONTENTS, READONLY, DEBUGGING
11 .comment 0000002d 00000000 00000000 00028511 2**0
CONTENTS, READONLY
また、elfヘッダのentryフィールドが示すエントリーポイントのアドレスはreadelfで確認できる。 textセクション開始位置の少し後ろ0x10000cにエントリーポイントがある。
readelf -h kernel
ELF Header:
Magic: 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00
Class: ELF32
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: EXEC (Executable file)
Machine: Intel 80386
Version: 0x1
Entry point address: 0x10000c
Start of program headers: 52 (bytes into file)
Start of section headers: 149308 (bytes into file)
Flags: 0x0
Size of this header: 52 (bytes)
Size of program headers: 32 (bytes)
Number of program headers: 4
Size of section headers: 40 (bytes)
Number of section headers: 16
Section header string table index: 15
readseg関数
この関数はサイズを指定してディスクからデータを読み込む。
データの読み込み先物理アドレス（pa）と、読み込むバイト数（count）、読み込みを開始するディスクのオフセットバイト数（offset）を引数として受けとる。
ディスクからの読み込みは1セクタ（512バイト）ずつだが、読み込みたいデータがセクタの途中から開始される場合がある。offsetが512で割り切れない場合がそう。
その場合のために、読み込み先アドレスをセクタ内の読み込み開始位置までの分だけ（offset % 512）下げておく。これで引数で与えられた読み込み先アドレスに丁度offsetバイト目のデータが入る。
また、読み込みはセクタ番号を指定して行い、offsetをその番号の指定に使用するため、セクタサイズで割っておく。このとき、1加算することでブートセクタを含まないようにしている。
つまりoffsetの値が0でも、データの読み込みは1セクタ目から開始される。
データの読み込みにはreadsect関数を用いる。
bootmain.c
#define SECTSIZE 512
/* 略 */
void
readseg(uchar* pa, uint count, uint offset)
{
uchar* epa;
epa = pa + count;
// Round down to sector boundary.
pa -= offset % SECTSIZE;
// Translate from bytes to sectors; kernel starts at sector 1.
offset = (offset / SECTSIZE) + 1;
// If this is too slow, we could read lots of sectors at a time.
// We'd write more to memory than asked, but it doesn't matter --
// we load in increasing order.
for(; pa < epa; pa += SECTSIZE, offset++)
readsect(pa, offset);
}
readsect関数
この関数はセクタを指定してディスクからデータを読み込む。
IOポートの読み書きにはinb関数やoutb関数を使用する。
ポート番号の意味は「OSDev I/O Ports」（リンク10）にリストされている。
また、個々のポートの働きに関しては「XT, AT and PS/2 I/O port addresses」（リンク11）に詳しく載っている。
ディスクコントローラの読み書きを行う前に、waitdisk関数を使用してディスクの準備ができるまで待機する。
waitdisk関数はwhileループを使い、ディスクコントローラのステータスレジスタ（0x1F7）の6, 7bitが1, 0でなくなるまで待つ。6bitはディスクのreadyを示し、7bitはコントローラがコマンドを実行中かどうかを示している。つまり状態がreadyかつ、コマンド実行中でなくなるまで待機する。
ポート0x1F7は読み込み時にはステータスレジスタ、書き込み時にはコマンドレジスタへのアクセスとなる。
readsect関数は読み込み先アドレス（dst）とセクタ番号（offset）を引数として受け取る。
ポート0x1F2から0x1F7に書き込みを行い、以下の内容のコマンドを発行する。
0x1F2: 1セクタ分
0x1F3: offset番目のセクタ
0x1F4, 0x1F5: offsetの3バイト目 + offsetの2バイト目で表されるシリンダー
0x1F6: offsetの4バイト目のビットで示されるヘッド
0x1F7: セクタをリードする（再試行ありで）
コマンド実行終了までwaitdisk関数で待機し、insl関数でデータレジスタ（0x1f0）からdstに512 / 4 = 128 * 4バイト = 512バイト読み込む。
bootmain.c
void
waitdisk(void)
{
// Wait for disk ready.
while((inb(0x1F7) & 0xC0) != 0x40)
;
}
// Read a single sector at offset into dst.
void
readsect(void *dst, uint offset)
{
// Issue command.
waitdisk();
outb(0x1F2, 1); // count = 1
outb(0x1F3, offset);
outb(0x1F4, offset >> 8);
outb(0x1F5, offset >> 16);
outb(0x1F6, (offset >> 24) | 0xE0);
outb(0x1F7, 0x20); // cmd 0x20 - read sectors
// Read data.
waitdisk();
insl(0x1F0, dst, SECTSIZE/4);
}
inb関数、outb関数、insl関数
inb関数はポートから1バイト読み込む。
outb関数はポートに1バイト書き込む。
insl関数はポートから指定回数分だけ4バイトずつ読み込む。
これらの関数ではインラインアセンブリを使用する。GCCのインラインアセンブリについては「Using the GNU Compiler Collection (GCC)」（リンク3）の「6.44 How to Use Inline Assembly Language in C Code」で説明されている。
また、x86の命令については「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）の「Vol.2 Instruction Set Reference, A-Z」で確認できる。
x86.h
static inline uchar
inb(ushort port)
{
uchar data;
asm volatile("in %1,%0" : "=a" (data) : "d" (port));
return data;
}
static inline void
insl(int port, void *addr, int cnt)
{
asm volatile("cld; rep insl" :
"=D" (addr), "=c" (cnt) :
"d" (port), "0" (addr), "1" (cnt) :
"memory", "cc");
}
static inline void
outb(ushort port, uchar data)
{
asm volatile("out %0,%1" : : "a" (data), "d" (port));
}
insl関数の動きを見ると、以下のようになっている。
cld命令でEFLAGSのDFフラグを0にすることで、文字列操作が行われるとesiとediがインクリメントされるようになる。このため出力先edi(addr)が毎回4バイトずつずれてくれる。
拡張インラインアセンブリの入力にある数字（ここでは0と1）は、番号と一致するオペランドを使うことを示している。
つまりここでは出力が「”=D(addr), “=c”(cnt)」なので、入力は「”d”(port), “D”(addr), “c”(cnt)」と書き直せる。ediとecx
が入力としても出力としても使用される。
insl命令はedxの示すポートから4バイトをediに読み込む。
また、命令にrepがつくと、文字列操作の実行毎にカウントレジスタ（ecx）がデクリメントされ、指定された回数だけ命令をリピートするようになる。
ここで、一度出力と入力を整理する。
出力: edi(addr), ecx(cnt)
入力: edx(port), edi(addr), ecx(cnt)
insl命令では出力: edi(addr)と入力: edx(port)を使う。rep命令はecxを使う。
一見入力のedi(addr)とecx(cnt)が不要に見える。ディスアセンブリされたbootblock.asmを見ると、この部分は次のようになっていて、入力としてのediとecxはますます不要に思える。
bootblock.asm
asm volatile("cld; rep insl" :
7ce4: 8b 7d 08 mov 0x8(%ebp),%edi
7ce7: b9 80 00 00 00 mov $0x80,%ecx
7cec: ba f0 01 00 00 mov $0x1f0,%edx
7cf1: fc cld
7cf2: f3 6d rep insl (%dx),%es:(%edi)
insl(0x1F0, dst, SECTSIZE/4);
しかし、「ProgrammerSought Gnu embedded assembly, inline assembly detailed introduction」（リンク12）によると、repでループする過程において、ループ毎のedi(addr)とecx(cnt)が同一のものであるということをコンパイラに伝えるために必要らしい。
このrepを使用したパターンは今後も出てくる。
stosb関数
この関数は値（data）を指定バイト分（cnt）だけアドレス（addr）に書き込む。
repを使用したパターンなので、insl関数と同様の動きになる。
x86.h
> 42 static inline void
> 43 stosb(void *addr, int data, int cnt)
> 44 {
> 45 asm volatile("cld; rep stosb" :
> 46 "=D" (addr), "=c" (cnt) :
> 47 "0" (addr), "1" (cnt), "a" (data) :
> 48 "memory", "cc");
> 49 }
これで物理アドレス0x100000にカーネルをロードすることができた。
4. ページング機構の有効化
entry.Sからmain関数の実行まで。
4.1. entry.S
entry.Sではページングを有効化し、ページディレクトリを作成して、main関数を呼び出す。
エントリーポイントは「2.4. ターゲットkernel」で見たリンカスクリプトkernel.ldにより_startに設定されている。_startのアドレスは0x10000cだったことを3.2. bootmain関数で確認した。
今、カーネルを実行していくためにentry.Sのentryラベルから実行を開始したい。
しかし、リンカスクリプトによりカーネルは仮想アドレス0x80100000で実行されるようにリンクされている。
これは「xv6 a simple, Unix-like teaching operating system」の「Figure 1-3. Layout of a Virtual address space」のように、仮想アドレスの上の方にカーネルを置きたいからである。
このためシンボルのアドレスを見ると、entryは0x8010000cで実行されるようになっている。
しかし、kernelのtextのロード先は物理アドレス0x100000なので、実際にはentryは0x100000の近くに配置されている。
なので、V2P_WO(entry)でentryの実際のアドレスを求め、_startのアドレス0x10000cに代入することでentryを実行する。
以降同様の目的でV2P_WOマクロを度々使用する。
readelf -s kernel | grep -e start -e entry
46: 801026e6 402 FUNC LOCAL DEFAULT 1 idestart
75: 8010393f 196 FUNC LOCAL DEFAULT 1 startothers
131: 8010000c 0 NOTYPE GLOBAL DEFAULT 1 entry
348: 8010a000 4096 OBJECT GLOBAL DEFAULT 4 entrypgdir
349: 0010000c 0 NOTYPE GLOBAL DEFAULT 1 _start
391: 0000008a 0 NOTYPE GLOBAL DEFAULT ABS _binary_entryother_size
429: 8010b4ec 0 NOTYPE GLOBAL DEFAULT 4 _binary_entryother_start
492: 8010b4c0 0 NOTYPE GLOBAL DEFAULT 4 _binary_initcode_start
504: 8010b576 0 NOTYPE GLOBAL DEFAULT 4 _binary_entryother_end
560: 80103022 227 FUNC GLOBAL DEFAULT 1 lapicstartap
memlayout.h
#define KERNBASE 0x80000000 // First kernel virtual address
/* 略 */
#define V2P_WO(x) ((x) - KERNBASE) // same as V2P, but without casts
entry.S
.globl _start
_start = V2P_WO(entry)
# Entering xv6 on boot processor, with paging off.
.globl entry
entry:
ページング機構を有効にする。
なお、ページング機構を有効にしてもセグメント機構は無効にならない。
セグメント機構は無効にできないので常に有効になっている。
ページサイズは通常4kBだが、cr4の4bitを1にすると4MBにできる。ここでは4MBページングを有効にする。
「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」の「Vol.3A 4.3 32-BIT PAGING」にページングに関して記載されているが、cr4.PSEが何bitなのかが分からなかった。
しかし、「Wikipedia Control register」（リンク13）によると4bitがPSEらしく、実際コードもそうなっている。
ページディレクトリには、main.cに定義されているentrypgdirを使う。
ページング機構ではページディレクトリのアドレスをcr3に設定することになっているため、entrypgdirの物理アドレスを設定する。
ページディレクトリentrypgdirは、0番と512番の2つのエントリを持つ。
各エントリがページを指しており、ここでは0番目も512番目も同じ0ページ目（物理アドレス0から4MB分）を指している。
また、ページがメモリ上に存在し（PTE_P）、書き込み可能で（PTE_W）、グローバルなページである（PTE_PS）ことを示している。
これらページディレクトリエントリの各部位の意味や、仮想アドレスの変換方法についてはSDMの「Vol.3A 4.3 32-Bit Paging」に図付きで記述されている。
4MBページでの仮想アドレスの変換方法はSMDの「Figure 4-3. Linear-Address Translation to a 4-MByte Page using 32-bit Paging」の通り。
仮想アドレスの上位10bitがページディレクトリのエントリ番号を示しており、今回はページディレクトリエントリのフラグ部分以外が0なので、ページフレーム0の物理アドレス0x0からページが開始される。
512エントリ目はこの後main関数以降の実行アドレスが高い（0x8000000等）ため必要であり。 0エントリ目はページングを有効にした瞬間からページング機構を用いたアドレス変換が始まるので、低い位置で動いている今（0x100000等）必要となる。
cr0の31bitを1にしてページング機構を有効にし、16bitも1にして書き込み可能ページへの書き込みを特権レベル0でも禁止する。
main関数を実行する前に、今後使用するスタックを準備する。
.commでスタック分の領域が作られ、KSTACKSIZEが4096なのでスタックサイズは4kB。
スタックは上から下に伸びるので、espにはstack + 4096したアドレスを設定する。
.commなのでbssセクションに作成される。リンカスクリプトではbssセクションは後ろの方に作ったので、カーネルの後ろ、データのさらに後ろをスタックとして使用することになる。
memlayout.h
#define KERNBASE 0x80000000 // First kernel virtual address
/* 略 */
#define V2P_WO(x) ((x) - KERNBASE) // same as V2P, but without casts
param.h
#define KSTACKSIZE 4096 // size of per-process kernel stack
entry.S
.globl _start
_start = V2P_WO(entry)
# Entering xv6 on boot processor, with paging off.
.globl entry
entry:
# Turn on page size extension for 4Mbyte pages
movl %cr4, %eax
orl $(CR4_PSE), %eax
movl %eax, %cr4
# Set page directory
movl $(V2P_WO(entrypgdir)), %eax
movl %eax, %cr3
# Turn on paging.
movl %cr0, %eax
orl $(CR0_PG|CR0_WP), %eax
movl %eax, %cr0
# Set up the stack pointer.
movl $(stack + KSTACKSIZE), %esp
# Jump to main(), and switch to executing at
# high addresses. The indirect call is needed because
# the assembler produces a PC-relative instruction
# for a direct jump.
mov $main, %eax
jmp *%eax
.comm stack, KSTACKSIZE
main.c
__attribute__((__aligned__(PGSIZE)))
pde_t entrypgdir[NPDENTRIES] = {4MB
// Map VA's [0, 4MB) to PA's [0, 4MB)
[0] = (0) | PTE_P | PTE_W | PTE_PS,
// Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
[KERNBASE>>PDXSHIFT] = (0) | PTE_P | PTE_W | PTE_PS,
};
mmu.h
#define NPDENTRIES 1024 // # directory entries per page directory
#define PGSIZE 4096 // bytes mapped by a page
#define PDXSHIFT 22 // offset of PDX in a linear address
// Page table/directory entry flags.
#define PTE_P 0x001 // Present
#define PTE_W 0x002 // Writeable
#define PTE_U 0x004 // User
#define PTE_PS 0x080 // Page Size
entry.Sの最後、main関数にジャンプする。
main関数が実際にロードされているアドレスはELFのテキストセグメントを0x100000に読み込んだので、おそらくそのちょっと先くらいだろう。
仮想アドレスはreadelfで確認すると0x80103853になっている。
readelf -s kernel | grep main
73: 00000000 0 FILE LOCAL DEFAULT ABS main.c
76: 801038f8 71 FUNC LOCAL DEFAULT 1 mpmain
415: 80103853 139 FUNC GLOBAL DEFAULT 1 main
ページングが有効になっているので、先ほどのページディレクトリを使って以下のようにmainのアドレスが変換される。
- 仮想アドレス0x80103853(main)から上位10bitを取り出す。0b1000 0000 00になる。 10進数で512なので、ページディレクトリの512番目のエントリを使用する。
- 512番目のエントリはフラグ以外0なので、ページフレームを示すbitも全て0となり、0番目のページフレームを使うことが分かる。
- 仮想アドレス0x80103853(main)の下位22bitを取り出す。0b01 0000 0011 1000 0101 0011になる。 これは0x103853なので、0ページ目の0x103853に変換される。つまりmainの物理アドレスは0x103853となる。
この変換はSDMの「Figure 4-3. Linear-Address Translation to a 4-MByte Page using 32-bit Paging」を見ながら行った。
これでページングを有効にし、main関数にジャンプすることができた。
5. カーネルの実行
main関数からスケジューラの実行まで。
5.1. main関数
ここからは各関数でAPICの設定やAPの起動等を行い、最終的にスケジューラを起動する。
main.c
extern char end[]; // first address after kernel loaded from ELF file
/* 略 */
int
main(void)
{
kinit1(end, P2V(4*1024*1024)); // phys page allocator
kvmalloc(); // kernel page table
mpinit(); // detect other processors
lapicinit(); // interrupt controller
seginit(); // segment descriptors
picinit(); // disable pic
ioapicinit(); // another interrupt controller
consoleinit(); // console hardware
uartinit(); // serial port
pinit(); // process table
tvinit(); // trap vectors
binit(); // buffer cache
fileinit(); // file table
ideinit(); // disk
startothers(); // start other processors
kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after startothers()
userinit(); // first user process
mpmain(); // finish this processor's setup
}
先に各関数の概要をまとめておく。
| 関数名 | 概要 |
|---|---|
| kinit1 | 大域変数kmemのfreelistに、kernelの終わりから物理アドレス4MBまでを追加する。 |
| kvmalloc | カーネル用のページディレクトリとPDE、PTEを作成して切り替える。 |
| mpinit | 大域変数lapicにLAPICへのアクセスアドレスを設定、各cpu構造体にLAPIC IDを設定、大域変数ioapicidにIOAPIC IDを設定する。 |
| lapicinit | LAPICを有効にし、スプリアス割り込みを無効化。APICタイマが10000000からバスクロックが進むごとにカウントダウンされ、0になるとIRQ32で割り込みをかけ、再度カウントダウンを始めるよう設定。LINT0とLINT1ピン、パフォーマンスモニタリングカウンタを無効化。割り込みエラーの際にIRQ51で割り込みかけるように設定。ESR、EOIレジスタをリセット。ICRでAPにINIT IPIを送信し、Arb IDをLAPIC IDと同じ値に設定。TPRをリセット。 |
| seginit | GDTを作成し、ロードする。 |
| picinit | MPに対応していない古いPICでの割り込みを無効化する。 |
| ioapicinit | 大域変数ioapicにIOAPICへのアクセスアドレスを設定し、IOリダイレクションテーブルの設定を行う。IRQ0～23番がBSPにIRQ32～55番でリダイレクトされるよう設定を行い、それら全てを無効化する。 |
| consoleinit | devsw配列の1番にコンソール読み書き用の関数を設定し、IOAPICのキーボードコントローラからの割込みのリダイレクトを有効化する（IRQ1からIRQ33へのリダイレクト）。 |
| uartinit | UARTのFIFOを無効化し、ボーレートを9600、ワードサイズを8bitに初期化。シリアルポートが使用できるか否かを確認し、使用できる場合は「xv6...」という文字列を送信する。 |
| pinit | ロセステーブルのロックを初期化する。 |
| tvinit | 大域変数idtに256個のゲートディスクリプタを作成する。 |
| binit | 大域変数bcache（バッファキャッシュ）を初期化する。 |
| fileinit | 大域変数ftable（ファイルテーブル）のロックを初期化する。 |
| ideinit | ディスク1の存在確認をする。ide.cの静的変数havedisk1に値を設定（0ならディスク1は無し、1なら有り）。 |
| startothers | 各APを起動し、GDT、ページング、IDT等の設定を行い、スケジューラを実行する。mpmain関数もここで見る。 |
| kinit2 | 大域変数kmemのfreelistに物理アドレス4MB（0x400000）から終わり（0xe000000）までを加え、use_lockフィールドの値を1にする。 |
| userinit | initcode.Sのプロセスを作成し、プロセステーブルに追加する。 |
| mpmain | APのときと同様にBSPでも「cpu0: starting 0」をコンソールに出力し、IDTを読み込み、スケジューラを実行する。 |
5.2. kinit1関数
この関数は、大域変数kmemのfreelistに、kernelの終わりから物理アドレス4MBまでを追加する。
main関数からはkernelのendシンボルのアドレス（vstart）と、物理アドレス4MBの仮想アドレス（vend）を受け取る。
main.c
extern char end[]; // first address after kernel loaded from ELF file
/* 略 */
int
main(void)
{
kinit1(end, P2V(4*1024*1024)); // phys page allocator
endは「2.4. ターゲットkernel」で見たリンカスクリプトkernel.ldによりbssセグメントの後ろ、elfの最後に作成されている。
アドレスはreadelfで確認でき、ここでは0x80116528になっている。
物理アドレスにすると0x116528。
readelf -s kernel | grep end
257: 801035ae 196 FUNC GLOBAL DEFAULT 1 end_op
331: 80116528 0 NOTYPE GLOBAL DEFAULT 4 end
352: 8010b4ec 0 NOTYPE GLOBAL DEFAULT 3 _binary_initcode_end
503: 8010b576 0 NOTYPE GLOBAL DEFAULT 3 _binary_entryother_end
物理アドレスから仮想アドレスへの変換はP2Vマクロを使う。V2Pマクロと同様にカーネルベースアドレスを使って変換する。
memlayout.h
#define KERNBASE 0x80000000 // First kernel virtual address
/* 略 */
#define P2V(a) ((void *)(((char *) (a)) + KERNBASE))
main関数から与えられたアドレスの範囲は、物理アドレスだと0x116528（vstart）から0x400000（vend）。
freelistに加えるためにPGROUNDUPマクロで4kBにアラインメントするので、開始アドレスは0x117000となり0x400000と差を取ると0x2E9AD8 = 0x2E9000で約3MB。
ページは大域変数kmemのfreelistフィールドに持っておく。
freelistフィールドはrun構造体の線形リストになっており、ページが必要な時はこのリストから取得し、解放するときはこのリストに戻すことになる。
kmem構造体はその他に2つのフィールドを持っており、lockフィールドは排他制御に使用し、use_lockフィールドは排他制御の必要性を示す。
use_lockが0のときは排他制御が不要なので、freelistへアクセスする際にkmemのロックを取らない。use_lockはkinit2関数で初めて1に初期化される。
spinlock構造体等を用いた排他制御に関しては、consoleinit関数で見る。
kalloc.c
struct run {
struct run *next;
};
struct {
struct spinlock lock;
int use_lock;
struct run *freelist;
} kmem;
kinit1関数は、大域変数kmemのロックを初期化し、freelistにアドレスend（vstart）の次のページから物理アドレス0x400000までを追加する。追加されるページは全て1埋めされる。
kalloc.c
void
kinit1(void *vstart, void *vend)
{
initlock(&kmem.lock, "kmem");
kmem.use_lock = 0;
freerange(vstart, vend);
}
freerange関数
この関数は、指定された仮想アドレスの範囲をkmemのfreelistに加える。
freelistに加えられる範囲は、vstartの次の4kB境界から、vendの次の4kB境界までである。
PGROUNDUPマクロは引数として与えられたアドレスの次のページ境界のアドレスを計算する。
mmu.h
#define PGROUNDUP(sz) (((sz)+PGSIZE-1) & ~(PGSIZE-1))
kalloc.c
void
freerange(void *vstart, void *vend)
{
char *p;
p = (char*)PGROUNDUP((uint)vstart);
for(; p + PGSIZE <= (char*)vend; p += PGSIZE)
kfree(p);
}
kfree関数
この関数は、指定された仮想アドレスのページをkmemのfreelistに加える。ページサイズは4kBで内容は全て1で初期化される。
ページの開始アドレス（v）はページサイズで割り切れ、end以上PHYSTOP未満でなければならない。PHYSTOP（0xE000000）はxv6での物理アドレスの上限。この条件を満たさない場合、panic関数を呼び出す。
panic関数はコンソールのロックを取り、パニックした理由とコールスタックをコンソールに出力し、panickedフラグを1にして無限ループに入る。
コンソール出力にはcgaputc関数を使用する。
ページの初期化はmemset関数で1で埋めすることで行う。
kmemのuse_lockフィールドが1のとき、APが起動しており排他制御が必要となるため、freelistにページを加える間、acquire関数とrelease関数でロックの取得と解放を行う。
kinit1関数の呼び出しではuse_lockは0なので、排他制御は行わない。
初期化したページはfreelistの先頭に追加していく。
kalloc.c
void
kfree(char *v)
{
struct run *r;
if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP)
panic("kfree");
// Fill with junk to catch dangling refs.
memset(v, 1, PGSIZE);
if(kmem.use_lock)
acquire(&kmem.lock);
r = (struct run*)v;
r->next = kmem.freelist;
kmem.freelist = r;
if(kmem.use_lock)
release(&kmem.lock);
}
memlayout.h
#define PHYSTOP 0xE000000 // Top physical memory
memset関数
この関数は指定したアドレスに値をnバイト分書き込む。
書き込み先アドレス（dst）と書き込みサイズ（n）が4で割り切れる場合、stosl関数を使用して4バイトずつ書き込みを行う。
割り切れない場合はstosb関数を使って1バイトずつ書き込む。
4バイトずつ書き込む場合は、書き込む値（c）から1バイト分取り出し、それをシフトして4バイト並べた値を書き込む。
stosb関数とstosl関数は「3.2. bootmain関数」で見たinsl関数と同様にrepを使用したパターンになっている。
string.c
void*
memset(void *dst, int c, uint n)
{
if ((int)dst%4 == 0 && n%4 == 0){
c &= 0xFF;
stosl(dst, (c<<24)|(c<<16)|(c<<8)|c, n/4);
} else
stosb(dst, c, n);
return dst;
}
x86.h
static inline void
stosb(void *addr, int data, int cnt)
{
asm volatile("cld; rep stosb" :
"=D" (addr), "=c" (cnt) :
"0" (addr), "1" (cnt), "a" (data) :
"memory", "cc");
}
static inline void
stosl(void *addr, int data, int cnt)
{
asm volatile("cld; rep stosl" :
"=D" (addr), "=c" (cnt) :
"0" (addr), "1" (cnt), "a" (data) :
"memory", "cc");
}
これで大域変数kmemのfreelistに約3MB分のページを追加できた。
5.3. kvmalloc関数
この関数はカーネル用のページディレクトリとPDE、PTEを作成してそれに切り替える。
4kBページングへの切り替えもここで行われる。
大域変数kpgdirに1ページ分のメモリを確保し、カーネル用のページディレクトリとする。
ページディレクトリには次の4つのアドレス変換ができるようにPDEとPTEを作成する。
- 仮想アドレス0x80000000～0x800FF000 → 物理アドレス0x0～0xff000
- 仮想アドレス0x80100000～0x80108000 → 物理アドレス0x100000～0x108000
- 仮想アドレス0x80109000～0x8DFFF000 → 物理アドレス0x109000～0xEDFFF000
- 仮想アドレス0xFE000000～ → 物理アドレス0xFE000000～
別な書き方をすると、それぞれ以下の領域のアドレスを変換する。
- I/Oスペース
- カーネルのテキストと読み込み専用データ
- カーネルのデータとメモリ
- メモリマップドI/Oを使用するデバイスのためのスペース
この変換は「xv6 a simple, Unix-like teaching operating system」の図2-2のマッピングを実現する。
ページディレクトリの作成はsetupkvm関数で行い、PDEのbitの設定によりここで4MBページから4kBページに切り替わる。
作成したページディレクトリをswitchkvm関数でcr3にロードする。
vm.c
pde_t *kpgdir; // for use in scheduler()
/* 略 */
void
kvmalloc(void)
{
kpgdir = setupkvm();
switchkvm();
}
setupkvm関数
この関数はカーネル用のページディレクトリとPDE、PTEを作成する。
PDEとPTEはkmap構造体の配列（kmap）を基に作成する。
kmap構造体は、仮想アドレス（virt）を物理アドレス（phys_start）にサイズ（phys_end - phys_start）分だけマップすることを示している。
また、その際にPTEの属性（perm）を設定する。
変数dataはリンカスクリプトで作成されたシンボルで、text、rodata、stab、stabstrの後ろのページ境界に定義されている。今回は0x80109000に存在している。
readelf -s kernel | grep data
411: 80109000 0 NOTYPE GLOBAL DEFAULT 3 data
memlayout.h
#define EXTMEM 0x100000 // Start of extended memory
#define PHYSTOP 0xE000000 // Top physical memory
#define DEVSPACE 0xFE000000 // Other devices are at high addresses
// Key addresses for address space layout (see kmap in vm.c for layout)
#define KERNBASE 0x80000000 // First kernel virtual address
#define KERNLINK (KERNBASE+EXTMEM) // Address where kernel is linked
vm.c
static struct kmap {
void *virt;
uint phys_start;
uint phys_end;
int perm;
} kmap[] = {
{ (void*)KERNBASE, 0, EXTMEM, PTE_W}, // I/O space
{ (void*)KERNLINK, V2P(KERNLINK), V2P(data), 0}, // kern text+rodata
{ (void*)data, V2P(data), PHYSTOP, PTE_W}, // kern data+memory
{ (void*)DEVSPACE, DEVSPACE, 0, PTE_W}, // more devices
};
setupkvm関数では、はじめにページディレクトリとしてkalloc関数で1ページ割り当て、0埋めする。
デバイスのメモリマップドI/Oに使用されるアドレス（DEVSPACE）よりも、使用できる物理アドレスの上限（PHYSTOP）が大きかった場合、panicする。
for文でkmap配列を走査し、kmap構造体で示された通りにPDEとPTEを作成する。PDEとPTEの作成にはmappages関数を使う。
もしもPDEやPTEの作成に失敗した場合は、freevm関数でページディレクトリに含まれる全てのPDEとPTE、ページを解放する。
defs.h
// number of elements in fixed-size array
#define NELEM(x) (sizeof(x)/sizeof((x)[0]))
vm.c
pde_t*
setupkvm(void)
{
pde_t *pgdir;
struct kmap *k;
if((pgdir = (pde_t*)kalloc()) == 0)
return 0;
memset(pgdir, 0, PGSIZE);
if (P2V(PHYSTOP) > (void*)DEVSPACE)
panic("PHYSTOP too high");
for(k = kmap; k < &kmap[NELEM(kmap)]; k++)
if(mappages(pgdir, k->virt, k->phys_end - k->phys_start,
(uint)k->phys_start, k->perm) < 0) {
freevm(pgdir);
return 0;
}
return pgdir;
}
kalloc関数
この関数はkmemのfreelistから1ページ割り当てる。
メモリが必要な時はこの先ずっとこの関数を使用して割り当てを行うので、AP起動後は排他制御が行われる。 kmemのfreelistの先頭を取ってきて返す。 freelistが空の場合、中身のないポインタを返す。
kalloc.c
char*
kalloc(void)
{
struct run *r;
if(kmem.use_lock)
acquire(&kmem.lock);
r = kmem.freelist;
if(r)
kmem.freelist = r->next;
if(kmem.use_lock)
release(&kmem.lock);
return (char*)r;
}
mappages関数
この関数はページディレクトリに、仮想アドレスから物理アドレスへの変換が行えるPDEとPTEを作成する。
関数を呼び出す際にページやPTEの範囲を気にする必要はなく、指定した物理アドレスの範囲を指定した仮想アドレスからアクセスできるようにマッピングしてくれる。
ページディレクトリ（pgdir）に、仮想アドレス（va）から物理アドレスの範囲（paからsizeバイト分）へ変換できるPDEとPTEを作成する。 PTEには属性（perm）を設定する。
まず変換範囲の開始仮想アドレス（a）と終了仮想アドレス（last）を求める。 どちらもページサイズにアラインメントされている必要があるので、PGROUNDDOWNマクロを使用する。 PGROUNDDOWNマクロは、「5.2. kinit1関数」で使用したPGROUNDUPマクロと同様の方法で、アドレスから前のページ境界のアドレスを計算する。 0x1000（PGSIZE）から1引いた0xFFFの否定0x000を論理積して4kBにアラインメントする。
mmu.h
> 90 #define PGROUNDUP(sz) (((sz)+PGSIZE-1) & ~(PGSIZE-1))
> 91 #define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))
次にfor文で開始仮想アドレス（a）から、変換する最後の仮想アドレス（last）までを走査する。ループ毎の処理の流れは以下のよう。
- 仮想アドレスのPTEを取得する。既にページディレクトリにPTEが存在する場合はそれを取得し、存在しない場合は作成する。これはwalkpgdir関数を用いて行う。
- PTEが未使用であることを確認する。PTE_Pフラグが0の場合は未使用、1の場合は使用されている。
- PTEに物理アドレスの上位20bitと属性bitをセットし、PTE_Pフラグを立てる。
これで求めているアドレス変換が完成する。
vm.c
static int
mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
{
char *a, *last;
pte_t *pte;
a = (char*)PGROUNDDOWN((uint)va);
last = (char*)PGROUNDDOWN(((uint)va) + size - 1);
for(;;){
if((pte = walkpgdir(pgdir, a, 1)) == 0)
return -1;
if(*pte & PTE_P)
panic("remap");
*pte = pa | perm | PTE_P;
if(a == last)
break;
a += PGSIZE;
pa += PGSIZE;
}
return 0;
}
walkpgdir関数
この関数はページディレクトリから、指定された仮想アドレスに対応するPTEを返す。
PTEがすでに存在している場合はそれを返すが、無い場合は引数allocが1の場合に限り新たに作成する。
また、PTEをPDEにセットする際に、読み書きフラグ（1bit）とユーザフラグ（2bit）を立てる。ページサイズフラグ（7bit）は立てないので、ページサイズは4kBとなる。
PDEの構造と各bitの意味は「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）の「Vol.3 4.3 32-BIT PAGING」に書いてある。
ある仮想アドレスが示すPDEのインデックスはPDXマクロで求めることができる。
コメントに仮想アドレスの構造が示されているので分かりやすい。
PDEを指すインデックスは仮想アドレスの22～31bitなので、22bit右シフトし、0b001111111111（0x3FF）で論理積を取ると求められる。
同様にPTEのインデックスはPTXマクロで求めることができる。
mmu.h
// A virtual address 'la' has a three-part structure as follows:
//
// +--------10------+-------10-------+---------12----------+
// | Page Directory | Page Table | Offset within Page |
// | Index | Index | |
// +----------------+----------------+---------------------+
// \--- PDX(va) --/ \--- PTX(va) --/
// page directory index
#define PDX(va) (((uint)(va) >> PDXSHIFT) & 0x3FF)
// page table index
#define PTX(va) (((uint)(va) >> PTXSHIFT) & 0x3FF)
/* 略 */
#define PTXSHIFT 12 // offset of PTX in a linear address
#define PDXSHIFT 22 // offset of PDX in a linear address
ページディレクトリから仮想アドレスの示すPDEを取得し、それが使用済みの場合（PTE_P==1）はページテーブルを取得する。 ページテーブルの取得にはPTE_ADDRマクロを使う。PDEの12～31bitがページテーブルのアドレスを示しており、ページテーブルは4kBでアラインメントされているため、下位12bitを0にするとアドレスが求まる。 このアドレスは物理アドレスなのでPTEへのアクセスはP2Vマクロで仮想アドレスに変換して行う。
mmu.h
#define PTE_ADDR(pte) ((uint)(pte) & ~0xFFF)
仮想アドレスが示すPDEが未使用（PTE_P==0）かつ、引数allocが真の場合、新たにページテーブルを作成する。
ページテーブルとしてkalloc関数で1ページ分割り当て、内容を0埋めして初期化する。つまり全てのPTEの内容が0の状態。
PDEにページテーブルのアドレス上位20bitと、読み書きフラグとユーザフラグをセットし、PTE_Pフラグを立てる。繰り返しになるが、ページサイズフラグ（7bit）は立てないので、ページサイズは4kBとなる。
最後に、仮想アドレスが示すPTEをPTXマクロを使用してページテーブルから取得し、呼び出し元に返す。
vm.c
static pte_t *
walkpgdir(pde_t *pgdir, const void *va, int alloc)
{
pde_t *pde;
pte_t *pgtab;
pde = &pgdir[PDX(va)];
if(*pde & PTE_P){
pgtab = (pte_t*)P2V(PTE_ADDR(*pde));
} else {
if(!alloc || (pgtab = (pte_t*)kalloc()) == 0)
return 0;
// Make sure all those PTE_P bits are zero.
memset(pgtab, 0, PGSIZE);
// The permissions here are overly generous, but they can
// be further restricted by the permissions in the page table
// entries, if necessary.
*pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U;
}
return &pgtab[PTX(va)];
}
switchkvm関数
この関数はカーネル用のページディレクトリをcr3にロードする。
呼び出し後からはアドレス変換がkpgdirを使用して行われる。
lcr3関数は引数valを汎用レジスタのどれかに入れてcr3にセットする。
vm.c
void
switchkvm(void)
{
lcr3(V2P(kpgdir)); // switch to the kernel page table
}
x86.h
static inline void
lcr3(uint val)
{
asm volatile("movl %0,%%cr3" : : "r" (val));
}
5.4. mpinit関数
この関数は大域変数lapicにLAPICへのアクセスアドレスを設定、各cpu構造体にLAPICのIDを設定、大域変数ioapicidにIOAPICのIDを設定する。
この関数ではマルチプロセッサに関する情報を取得する。
xv6では使用できる最大CPU数をNCPUとして8に定義している。システムで実際に使用可能なCPU数は、大域変数ncpuに保持する。
また、CPUに関する情報を持つ構造体としてcpu構造体が定義されており、配列cpusとして保持している。
param.h
#define NCPU 8 // maximum number of CPUs
proc.h
struct cpu {
uchar apicid; // Local APIC ID
struct context *scheduler; // swtch() here to enter scheduler
struct taskstate ts; // Used by x86 to find stack for interrupt
struct segdesc gdt[NSEGS]; // x86 global descriptor table
volatile uint started; // Has the CPU started?
int ncli; // Depth of pushcli nesting.
int intena; // Were interrupts enabled before pushcli?
struct proc *proc; // The process running on this cpu or null
};
mp.c
struct cpu cpus[NCPU];
int ncpu;
マルチプロセッサに関する構造体が定義されているmp.hの1行目に「MultiProcessor Specification Version 1.4」（リンク14）を見るように書いてある。
このMP仕様書によると、プロセッサは1つのBSP（ブートストラッププロセッサ）とその他のAP（アプリケーションプロセッサ）とに分けられ、起動時はBSPが動いている。
各プロセッサはLAPICを有しており、ICC（割り込みコントローラバス）を通してIOAPICと接続されている。
LAPICに振られているIDでプロセッサを区別することが可能。
起動時には全てのAPのLAPICと、全てのIOAPICが無効化されているため、それらを初期化しなければならない。
また、割り込みモードとして、PICモード、仮想配線モード、Symmetric I/Oモードの3つがある。
システムはPICモードか仮想配線モードで開始され、マルチプロセッサでの割り込みを行うためにSymmetric I/Oモードに移行する必要がある。
MP仕様書の「Table 4-1. MP Floating Pointer Structure Fields」にIMCRがない場合は仮想配線モードが実装されていると書いてある。
IMCR（Interrupt Mode Configuration Register）はPICモードの時に使用されるレジスタ。
Symmetric I/Oモードへの移行方法はMP仕様書の「3.6.2.3 Symmetric I/O Mode」によると、IMCRがある場合はそこに0x1を書き込み、IOAPICのリダイレクションテーブルのエントリを有効化することで行える。
メモリ上には、マルチプロセッサに関する情報を取得するために、MPフローティングポインタ構造体と、MP設定テーブルが用意されている（後者はオプション）。
MPフローティングポインタ構造体はシステムのMPに関する基本的な情報を持っており、以下のいずれかの場所にある。
- EBDA（拡張BIOSデータ領域）の最初の1キロバイト
- システムベースメモリの最後の1キロバイト以内のどこか
- 0xF0000から0xFFFFFまでのBIOS ROMアドレスのどこか
MP設定テーブルの開始アドレスは、MPフローティングポインタ構造体のPHYSICAL ADDRESS POINTERフィールド（4バイト目）が持っている。このフィールドの値が0の場合は、MP設定テーブルは存在しない。
MP設定テーブルはひとつのヘッダ部分と、複数のエントリ部分に分かれている。ヘッダにはMP設定テーブルの基本的な情報を持っている。
基本的なエントリとその構造はMP仕様書の「Table 4-3. Base MP Configuration Table Entry types」に定義されており、以下の5つのエントリがある。各エントリはタイプコード（0バイト目）で識別することが可能。
- Processor: 0（タイプコード）
- Bus: 1
- I/O APIC: 2
- I/O Interrupt Assignment: 3
- Local Interrupt Assignment: 4
このエントリとタイプコードに合わせるようにmp.hに定義がある。
mp.h
#define MPPROC 0x00 // One per processor
#define MPBUS 0x01 // One per bus
#define MPIOAPIC 0x02 // One per I/O APIC
#define MPIOINTR 0x03 // One per bus interrupt source
#define MPLINTR 0x04 // One per system interrupt source
mpinit関数は、まずMPフローティングポインタ構造体と、MP設定テーブルを取得する。取得にはmpconfig関数を使う。
MP設定テーブルからLAPICへのアクセスアドレスを取得し、大域変数lapicに設定する。
アドレスはADDRESS OF LOCAL APICフィールド（36バイト目）から取得可能。
LAPICはプロセッサに内臓されているため、各プロセッサが個別に持っているが、MP仕様書によると、各プロセッサは自分のLAPICにアクセスするために同じアドレスにアクセスする。アドレスは同じでもアクセスは自分のLAPICへのものになる。
for文でMP設定テーブルのエントリをポインタpで走査する。
エントリのタイプコード（1バイト目）により処理内容が分かれる。未知のエントリが検出された場合はpanic。
Processerの場合:
大域変数cpus[ncpu]のapicidフィールドにLAPIC IDを設定する。LAPIC IDは、エントリのLOCAL APIC IDフィールド（1バイト目）にある。
次のプロセッサエントリのためにncpuをインクリメントする。
pにエントリのサイズを加えて、ループを継続する。
I/O APICの場合:
大域変数ioapicidにIOAPIC IDを設定する。IOAPIC IDは、エントリのI/O APIC IDフィールド（1バイト目）にある。
pにエントリのサイズを加えて、ループを継続する。
Bus, I/O Interrupt Assignment, Local Interrupt Assignmentの場合:
何もしない。
pにエントリのサイズを加えて、ループを継続する。
全てのエントリの処理が終わった時点で、以下の大域変数が設定されている。
lapic: LAPICへのアクセスアドレスが設定されている。
ncpu: システムで使用できるCPU数が設定されている。
cpus配列: ncpu分のapicidフィールドに各LAPIC IDが設定されている。
ioapicid: IOAPIC IDが設定されている。
mpinit関数の最後の処理、IMCR（Interrupt Mode Configuration Register）がシステムに実装されている場合、Symmetric I/Oモードへの移行準備として、そこに0x1を書き込む。
IMCRの有無は、MPフローティングポインタ構造体のMP FEATURE INFORMATION BYTE 2フィールド（12バイト目）の7bit目が1であればIMCR有り、0なら無しと判断できる。
0から6bit目まではMP仕様で予約されている。
MP仕様書の「3.6.2.1 PIC Mode」によると、IMCRへはポート0x22に0x70を書き込む事でアクセスできる。データの読み書きはポート0x23に行う。
IMCRの内容をそのまま0bitを1にする。
mp.c
void
mpinit(void)
{
uchar *p, *e;
int ismp;
struct mp *mp;
struct mpconf *conf;
struct mpproc *proc;
struct mpioapic *ioapic;
if((conf = mpconfig(&mp)) == 0)
panic("Expect to run on an SMP");
ismp = 1;
lapic = (uint*)conf->lapicaddr;
for(p=(uchar*)(conf+1), e=(uchar*)conf+conf->length; p<e; ){
switch(*p){
case MPPROC:
proc = (struct mpproc*)p;
if(ncpu < NCPU) {
cpus[ncpu].apicid = proc->apicid; // apicid may differ from ncpu
ncpu++;
}
p += sizeof(struct mpproc);
continue;
case MPIOAPIC:
ioapic = (struct mpioapic*)p;
ioapicid = ioapic->apicno;
p += sizeof(struct mpioapic);
continue;
case MPBUS:
case MPIOINTR:
case MPLINTR:
p += 8;
continue;
default:
ismp = 0;
break;
}
}
if(!ismp)
panic("Didn't find a suitable machine");
if(mp->imcrp){
// Bochs doesn't support IMCR, so this doesn't run on Bochs.
// But it would on real hardware.
outb(0x22, 0x70); // Select IMCR
outb(0x23, inb(0x23) | 1); // Mask external interrupts.
}
}
mpconfig関数
この関数はメモリからMP設定テーブルを取得する。
MPフローティングポインタ構造体をmpconfig関数で取得し、そのPHYSICAL ADDRESS POINTERフィールド（4バイト目）からMP設定テーブルのアドレスを取得する。
MP設定テーブルのSIGNATUREフィールド（0バイト目）が “PCMP” であることを確認し、M確かにMP設定テーブルであることを確認する。
準拠しているMP仕様のバージョンを確認する。これはMP設定テーブルのSPEC_REVフィールド（9バイト目）から確認でき、「MultiProcessor Specification Version 1.4」（リンク14）の「Table 4-1. MP Floating Pointer Structure Fields」によると0x1がバージョン1.1、0x4がバージョン1.4を示す。
チェックサムの計算を行う。MP設定テーブル全体の値を1バイト単位で合計し、結果が0となることでMP設定テーブルに誤りがないことを確認する。CHECKSUMフィールド（10バイト目）の値は結果が0になるような値が設定されている。
引数pmpにMPフローティングポインタ構造体を代入し、MP設定テーブルを呼び出し元に返す。
mp.c
static uchar
sum(uchar *addr, int len)
{
int i, sum;
sum = 0;
for(i=0; i<len; i++)
sum += addr[i];
return sum;
}
/* 略 */
static struct mpconf*
mpconfig(struct mp **pmp)
{
struct mpconf *conf;
struct mp *mp;
if((mp = mpsearch()) == 0 || mp->physaddr == 0)
return 0;
conf = (struct mpconf*) P2V((uint) mp->physaddr);
if(memcmp(conf, "PCMP", 4) != 0)
return 0;
if(conf->version != 1 && conf->version != 4)
return 0;
if(sum((uchar*)conf, conf->length) != 0)
return 0;
*pmp = mp;
return conf;
}
mpsearch関数
この関数はメモリからMPフローティングポインタ構造体を取得する。
「MultiProcessor Specification Version 1.4」（リンク14）の「3.9 Support for Fault-resilient Booting」に記載されているaからcの方法を順に試し、MPフローティングポインタ構造体を探す。
- EBDA（拡張BIOSデータ領域）の最初の1キロバイト
- システムベースメモリの最後の1キロバイト以内のどこか
- 0xF0000から0xFFFFFまでのBIOS ROMアドレスのどこか
各範囲の走査にはmpsearch1関数を使用する。
まず最初のif文で方法aを試す。
BIOSからブートローダに移る際のx86のメモリマップは「OSDev Memory Map (x86)」（リンク15）に記載されている。
それによると、BDAは0x0400から始まり、0x040Eから2バイト分には、4bit右シフトされたEBDAの物理アドレスが入っている。
なので、0x40Fの内容を上位8bit、0x40Eの内容を下位8bitとして、4bit左シフトすると、EBDAの物理アドレスが求められる。
次にelse文で方法bを試す。
システムベースメモリというのはmpsearch関数を読む限りではEBDAの開始アドレスまでを指す。
BDA内、0x0413から2バイト分には、EBDAまでのキロバイト数が記してある。
なので、0x414の内容を上位8bit、0x413の内容を下位8bitとして、1024掛けるとEBDAまでのバイト数になる。
EBDAの手前1キロバイト以内を探す。
最後にreturn文で方法cを試す。
mp.c
static struct mp*
mpsearch(void)
{
uchar *bda;
uint p;
struct mp *mp;
bda = (uchar *) P2V(0x400);
if((p = ((bda[0x0F]<<8)| bda[0x0E]) << 4)){
if((mp = mpsearch1(p, 1024)))
return mp;
} else {
p = ((bda[0x14]<<8)|bda[0x13])*1024;
if((mp = mpsearch1(p-1024, 1024)))
return mp;
}
return mpsearch1(0xF0000, 0x10000);
}
mpsearch1関数では与えられた物理アドレスと長さ分の範囲を走査し、MPフローティングポインタ構造体を探す。
MP仕様書の「Table 4-1. MP Floating Pointer Structure Fields」によると、SIGNATUREフィールド（0バイト目）に ”_MP_” が入っているため、それを頼りに同構造体を探すことができる。
また、CHECKSUMフィールド（10バイト目）により、見つけた領域がMPフローティングポインタ構造体であるか否かを断定できる。
チェックサムの計算方法は「mpconfig関数」のときと同様。
mp.c
// Look for an MP structure in the len bytes at addr.
static struct mp*
mpsearch1(uint a, int len)
{
uchar *e, *p, *addr;
addr = P2V(a);
e = addr+len;
for(p = addr; p < e; p += sizeof(struct mp))
if(memcmp(p, "_MP_", 4) == 0 && sum(p, sizeof(struct mp)) == 0)
return (struct mp*)p;
return 0;
}
memcmp関数
引数v1と引数v2の値をnバイトまで比較し、等しい場合は0を、等しくない場合は一致しなかった値のv1 - v2の値を返す。
string.c
int
memcmp(const void *v1, const void *v2, uint n)
{
const uchar *s1, *s2;
s1 = v1;
s2 = v2;
while(n-- > 0){
if(*s1 != *s2)
return *s1 - *s2;
s1++, s2++;
}
return 0;
}
5.5. lapicinit関数
この関数はLAPICを有効にし、スプリアス割り込みを無効化。APICタイマが10000000からバスクロックが進むごとにカウントダウンされ、0になるとIRQ32で割り込みをかけ、再度カウントダウンを始めるよう設定。LINT0とLINT1ピン、パフォーマンスモニタリングカウンタも無効化。割り込みエラーの際にIRQ51で割り込みを発生するように設定。ESR、EOIレジスタをリセット。ICRでAPにINIT IPIを送信し、Arb IDをLAPIC IDと同じ値に設定。TPRに0を設定する。
LAPICの設定を行うので、「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）の「Vol.3 CHAPTER 10 ADVANCED PROGRAMMABLE INTERRUPT CONTROLLER (APIC)」を参照する。
MPの場合、外部からの割り込みをIOAPICが各LAPICに送信する。
xv6ではIOAPICのIOリダイレクションテーブルのエントリに割り込み先プロセッサのIDを設定し、IRQに応じて特定のプロセッサにリダイレクトする。
内部からの割り込みは、LAPICがLVT（ローカルベクタテーブル）を使用してプロセッサに割り込みを送信する。
ローカル割り込みのソースとしては、プロセッサの割り込みピン（LINT0とLINT1ピン）、APICタイマ、温度センサ、パフォーマンスモニタリングカウンタ、他のプロセッサがある。
ローカルAPICは多くのレジスタを備えており、そのアドレスと名前はIntel-SDMの「Table 10-1 Local APIC Register Address Map」にリストされている。
各レジスタへのアクセスは「5.4. mpinit関数」にてLAPICへのアクセスアドレスを設定した大域変数lapicを通して行う。
レジスタのアドレスをオフセットとして使うことにより、lapic変数から任意のレジスタにアクセスできる。
lapic変数はuint*型なので、バイト単位でオフセットを使用するために4で割る。
例えばLocal APIC ID Register（0xFEE00020）にアクセスする際は、lapic[0x0020 / 4]とする。
LAPICのレジスタへの書き込みにはlapicw関数を使用する。
オフセット（index）で示されるレジスタに値（value）を書き込む。
書き込み完了を待機するために、Local APIC ID Registerの読み込みを行う。
lapic.c
// Local APIC registers, divided by 4 for use as uint[] indices.
#define ID (0x0020/4) // ID
/* 略 */
static void
lapicw(int index, int value)
{
lapic[index] = value;
lapic[ID]; // wait for write to finish, by reading
}
lapicinit関数は設定項目が多いので、設定項目毎に見ていくことにする。
lapic.c
void
lapicinit(void)
{
if(!lapic)
return;
// Enable local APIC; set spurious interrupt vector.
lapicw(SVR, ENABLE | (T_IRQ0 + IRQ_SPURIOUS));
// The timer repeatedly counts down at bus frequency
// from lapic[TICR] and then issues an interrupt.
// If xv6 cared more about precise timekeeping,
// TICR would be calibrated using an external time source.
lapicw(TDCR, X1);
lapicw(TIMER, PERIODIC | (T_IRQ0 + IRQ_TIMER));
lapicw(TICR, 10000000);
// Disable logical interrupt lines.
lapicw(LINT0, MASKED);
lapicw(LINT1, MASKED);
// Disable performance counter overflow interrupts
// on machines that provide that interrupt entry.
if(((lapic[VER]>>16) & 0xFF) >= 4)
lapicw(PCINT, MASKED);
// Map error interrupt to IRQ_ERROR.
lapicw(ERROR, T_IRQ0 + IRQ_ERROR);
// Clear error status register (requires back-to-back writes).
lapicw(ESR, 0);
lapicw(ESR, 0);
// Ack any outstanding interrupts.
lapicw(EOI, 0);
// Send an Init Level De-Assert to synchronise arbitration ID's.
lapicw(ICRHI, 0);
lapicw(ICRLO, BCAST | INIT | LEVEL);
while(lapic[ICRLO] & DELIVS)
;
// Enable interrupts on the APIC (but not on the processor).
lapicw(TPR, 0);
}
LAPICの有効化と、スプリアス割り込みベクタの設定
LAPICは電源投入時やリセット時に無効化されているため、ここで有効化する。
方法は2通りあり、Intel-SDMの「Vol.3 10.4.3 Enabling or Disabling the Local APIC」に記されている。
ここでは2番目のスプリアス割り込みベクタレジスタのフラグを使用する方法をとっている。
レジスタにはアドレス0xFEE000F0（オフセット0xF0）でアクセスでき、各bitの意味はIntel-SDMの「Vol.3 10.9 SPURIOUS INTERRUPT」に記載されている。
APIC Software Enable/Disableビット（8bit）をセットするとLAPICが有効になる。
LAPICの有効化と同時に、スプリアス割り込みに何番のIRQを使用するかを設定する。
スプリアス割り込みは、電気的な干渉やデバイスの誤動作等により期せずして発生した割り込みのことで、スプリアス割り込みベクタレジスタの0～7bitでその際のIRQを設定できる。
ここでは63番をスプリアス割り込みに割り当てている。
教科書「xv6 a simple, Unix-like teaching operating system」（リンク1）の「Code: Assembly trap handlers」によると、x86には256個の割り込みベクタ番号があり、0～31番は除算エラーや無効なアドレスのアクセスによるエラー等に割り当てられていて、32～255番はユーザが定義できるようになっている。
xv6は32～63番をハードウェア割り込みに使用する。システムコールは64番を使用する。
0～31番までの割り込みはIntel-SDMの「Vol.3 Table 6-1. Protected-Mode Exceptions and Interrupts」にリストしてある。
また、traps.hには割り込み番号の一覧が定義されている。
traps.h
#define T_IRQ0 32 // IRQ 0 corresponds to int T_IRQ
/* 略 */
#define IRQ_SPURIOUS 31
lapic.c
#define SVR (0x00F0/4) // Spurious Interrupt Vector
#define ENABLE 0x00000100 // Unit Enable
/* 略 */
lapicw(SVR, ENABLE | (T_IRQ0 + IRQ_SPURIOUS));
LAPICタイマの設定
Intel-SDMの「Vol.3 10.5.4 APIC Timer」によると、LAPICには32bitプログラマブルタイマが含まれていて、Divide Configurationレジスタ、Initial Countレジスタ、Current Countレジスタ、LVT Timerレジスタの4つで設定を行う。
動作としては、Initial Countレジスタから値がCurrent Countレジスタにコピーされて、後者がカウントダウンする。
カウントが0になると、タイマ割り込みが発生する。
ここでは以下の4つの設定を行う。
- タイマの周波数
- タイマの動作モードと割り込み番号
- タイマの初期値
タイマの周波数:
Divide Configurationレジスタ（0x3E0）に0xBを設定する。
このレジスタはその値によって、LAPICタイマの周波数が、プロセッサのバスクロックを何分の一したものにするかを設定する。
Intel-SDMに各bitパターンで設定されるの値が記されている。0b1011（0xB）の場合は1分の1が設定されるので、バスクロックと等しい周波数で動作する。
タイマの動作モードと割り込み番号:
LVT Timerレジスタ（0x320）に0x20020を設定する。
LAPICタイマの動作モードは、このレジスタの18bitと17bitによって決定される。ここではPeriodicモードが設定される。
動作モードは以下の3種類。0b11は予約済み。
| bit | モード | 動作 |
|---|---|---|
| 0b00 | One-shot | Current Countレジスタの値が0になり、割り込み発生後も0のまま変化しない。 |
| 0b01 | Periodic | Current Countレジスタの値が0になり、割り込み発生後、Initial Countレジスタの値を再びコピーし、継続的にカウントダウンを行う。 |
| 0b10 | TSC-Deadline | Initial Countレジスタが無視され、Current Countレジスタは常に0になり、タイマの動作はIA32_TSC_DEADLINE MSRによって制御される。 |
割り込み番号は32番をタイマ割り込みに割り当てている。
タイマの初期値:
Initial Countレジスタ（0x380）に10000000を設定する。
まとめると、LAPICタイマは、10000000からバスクロックが進むごとにカウントダウンされ、0になるとIRQ32番で割り込みをかける。その後再び10000000からカウントダウンが始まる。
traps.h
#define T_IRQ0 32 // IRQ 0 corresponds to int T_IRQ
#define IRQ_TIMER 0
lapic.c
#define TIMER (0x0320/4) // Local Vector Table 0 (TIMER)
#define X1 0x0000000B // divide counts by 1
#define PERIODIC 0x00020000 // Periodic
/* 略 */
#define TICR (0x0380/4) // Timer Initial Count
#define TDCR (0x03E0/4) // Timer Divide Configuration
/* 略 */
lapicw(TDCR, X1);
lapicw(TIMER, PERIODIC | (T_IRQ0 + IRQ_TIMER));
lapicw(TICR, 10000000);
LINT0ピンとLINT1ピンの無効化
Intel-SDMの「Vol.3 6.3.1 External Interrupts」によると、LINT0ピンとLINT1ピンはLAPICが有効な場合、割り込みに関与するようプログラムすることができる。 xv6では使用しないので無効にするのだと思う。 LINT0ピン（0x350）と、LINT1ピン（0x360）に0x00010000を設定している。 Intel-SDMの「Vol.3 Figure 10-8. Local Vector Table (LVT)」を見ると、16bitはマスクビットで1がMaskedとなっている。
lapic.c
#define LINT0 (0x0350/4) // Local Vector Table 1 (LINT0)
#define LINT1 (0x0360/4) // Local Vector Table 2 (LINT1)
/* 略 */
#define MASKED 0x00010000 // Interrupt masked
/* 略 */
lapicw(LINT0, MASKED);
lapicw(LINT1, MASKED);
パフォーマンスモニタリングカウンタの無効化
パフォーマンスモニタリングカウンタが実装されている場合に、それを無効化する。
Local APIC Versionレジスタ（0x30）のMax LVT Entry（16～23bit）の値が4以上であれば、実装されている。
この値の意味は、Intel-SDMの「Vol.3 10.4.8 Local APIC Version Register」に記載してあり、LVTエントリの数-1の値が設定されている。
LVTのエントリは同マニュアルの「Vol.3 Figure 10-8 Local Vector Table (LVT)」で確認でき、5番目がパフォーマンスモニタリングカウンタになっている。
なので、4（5-1=4）以上であればパフォーマンスモニタリングカウンタが実装されている。
実装されている場合は、パフォーマンスモニタリングカウンタ（0x340）のマスクビットを立てて無効化する。
lapic.c
#define VER (0x0030/4) // Version
/* 略 */
#define PCINT (0x0340/4) // Performance Counter LVT
/* 略 */
#define MASKED 0x00010000 // Interrupt masked
/* 略 */
if(((lapic[VER]>>16) & 0xFF) >= 4)
lapicw(PCINT, MASKED);
##LAPICでエラーが生じた際のIRQ番号の設定
LVT Errorレジスタ（0x370）に51を設定する。
このレジスタはIntel-SDMの「Vol.3 10.5.3 Error Handling」によると、LAPICでエラーが生じた際に割り込みを行うIRQ番号を設定することができる。
ここでは51番を設定している。
traps.h
#define T_IRQ0 32 // IRQ 0 corresponds to int T_IRQ
/* 略 */
#define IRQ_ERROR 19
lapic.c
#define ERROR (0x0370/4) // Local Vector Table 3 (ERROR)
/* 略 */
lapicw(ERROR, T_IRQ0 + IRQ_ERROR);
ESRをリセット
ESR（Error Status Register）（0x280）に0を設定する。 Intel-SDMの「Vol.3 10.5.3 Error Handling」によると、ESRはLAPICの割り込みでエラーが生じた際に検出されたエラーが書き込まれる。 ソースコード内のコメントによるとESRを初期化するためには0を2回書き込む必要があるらしいが、理由は見つけられなかった。
lapic.c
#define ESR (0x0280/4) // Error Status
/* 略 */
// Clear error status register (requires back-to-back writes).
lapicw(ESR, 0);
lapicw(ESR, 0);
EOIレジスタをリセット
EOI（End Of Interrupt）レジスタ（0xB0）に0を設定する。
Intel-SDMの「Vol.3 10.8.5 Signaling Interrupt Servicing Completion」でこのレジスタについて記載されている。
割り込みハンドラは、割り込み処理の終了時、iret命令の前にEOIレジスタに書き込みを行う必要がある。
lapic.c
#define EOI (0x00B0/4) // EOI
/* 略 */
lapicw(EOI, 0);
ICRの設定
ICR（Interrupt Command Register）は64bitなので、LAPICアクセスアドレスのインデックスが32bitずつ0x300と0x310に分かれている。
ICRについては、Intel-SDMの「Vol.3 10.6.1 Interrupt Command Register (ICR)」に記載があり、プロセッサ間割り込みIPI（Inter Processor Interrupts）の送信と設定を行う。各bitの意味は同マニュアルに記載されている。
ここではDestination Shorthand（18, 19bit）とDelivery Mode（8～10bit）、Trigger Mode（15bit）を以下のように設定する。
Destination Shorthand: All Including Self（0b01）。IPIの送信先を自分を含む全てのプロセッサにする。
Delivery Mode: INITモード（0b101）。全てのプロセッサにINIT IPIを送信する。
Trigger Mode: レベルモード（0b1）。INIT level de-assert delivery modeのトリガをレベルに設定する。
上記IPIの送信が終了するまでwhileループする。
ICRのDelivery Status（12bit）が1の時は送信が未完了、0になると送信完了となる。
Intel-SDMの「Vol.3 8.4.4.2 Typical AP Initialization Sequence」によると、起動後、各APはCLI命令とHLT命令が実行された状態になっており、BSPからのINIT IPIを待っている。
同マニュアル「Vol.3 10.6.1 Interrupt Command Register（ICR）」によると、ここではINIT IPIをlevel de-assertで送信することにより、IPIの処理順序を決定するために使われるArb ID（Arbitration ID）をLAPIC IDと同じ値にしている。
また、「MultiProcessor Specification Version 1.4」（リンク14）の「5.2 Integrated APIC Configurations」によると、APはRESETやINITシグナルを受けると、HALT状態になり、OSがSTARTUP IPIを送信するまで停止したままとなる。
lapic.c
#define ICRLO (0x0300/4) // Interrupt Command
#define INIT 0x00000500 // INIT/RESET
#define STARTUP 0x00000600 // Startup IPI
#define DELIVS 0x00001000 // Delivery status
#define ASSERT 0x00004000 // Assert interrupt (vs deassert)
#define DEASSERT 0x00000000
#define LEVEL 0x00008000 // Level triggered
#define BCAST 0x00080000 // Send to all APICs, including self.
#define BUSY 0x00001000
#define FIXED 0x00000000
#define ICRHI (0x0310/4) // Interrupt Command [63:32]
/* 略 */
lapicw(ICRHI, 0);
lapicw(ICRLO, BCAST | INIT | LEVEL);
while(lapic[ICRLO] & DELIVS)
;
TPRの設定
lapicinit関数の最後に、TPR（Task Priority Register）に0を設定する。
TPRについてはIntel-SDMの「Vol.3 10.8.3.1 Task and Processor Priorities」に記載されており、名前の通りタスク優先度の設定を行うことができる。
lapic.c
#define TPR (0x0080/4) // Task Priority
/* 略 */
lapicw(TPR, 0);
5.6. seginit関数
この関数はGDTを作成し、ロードする。
ここまでは「3.1. bootasm.S」で作成した3つのエントリを持つGDTを使用してきた。
ここではユーザ空間用のセグメントディスクリプタを持った新しいGDTを作成する。
セグメントディスクリプタの構造は「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）の「Vol.3 3.4.5 Segment Descriptors」に書いてある。
関数を実行しているcpu構造体のgdtフィールドに以下の4つのセグメントディスクリプタを作成する。0番目はNULLディスクリプタなので初期化は不要。
1番目: カーネル用のコードセグメントディスクリプタ
2番目: カーネル用のデータセグメントディスクリプタ
3番目: ユーザ用のコードセグメントディスクリプタ
4番目: ユーザ用のデータセグメントディスクリプタ
4つともベースアドレスは0x0、セグメントリミットは0xFFFFF。
Gフラグが1なので、セグメントリミットはページサイズ倍（4kB)され0xFFFFF000（4GB）となる。
タイプは4つとも読み書き可能、コードセグメントディスクリプタのみ実行可能にもなっている。
DPL（Descriptor Privilege Level）はカーネル用は0、ユーザ用は3。
全てのセグメントの範囲が0から4GBまでで重なっている。
メモリ管理にはページング機構を使用するが、セグメント機構は無効化できないため、こうして4GBまでをセグメント機構的になんにでも使えるようにしている。
cpu構造体のgdtフィールドは要素数が6（定数NSEGS）に定義されているため、GDTにはエントリが6つあることになる。
0から4番目まではここで作成するが、5番目はプロセスのコンテキストスイッチを行う際にTSS（タスク状態セグメント）ディスクリプタとして作成することになる。
作成したGDTをlgdt関数でgdtレジスタにロードする。
このとき、ecsレジスタの値は更新不要。
「3.1. bootasm.S」ではファージャンプを行うことでecsの設定を行っているが、コードセグメントディスクリプタのインデックスがここで作成したGDTでも変わらず1番目（8バイト目）であるため、再設定が不要。
mmu.h
#define SEG_KCODE 1 // kernel code
#define SEG_KDATA 2 // kernel data+stack
#define SEG_UCODE 3 // user code
#define SEG_UDATA 4 // user data+stack
#define SEG_TSS 5 // this process's task state
/* 略 */
#define SEG(type, base, lim, dpl) (struct segdesc) \
{ ((lim) >> 12) & 0xffff, (uint)(base) & 0xffff, \
((uint)(base) >> 16) & 0xff, type, 1, dpl, 1, \
(uint)(lim) >> 28, 0, 0, 1, 1, (uint)(base) >> 24 }
/* 略 */
#define STA_X 0x8 // Executable segment
#define STA_W 0x2 // Writeable (non-executable segments)
#define STA_R 0x2 // Readable (executable segments)
vm.c
void
seginit(void)
{
struct cpu *c;
// Map "logical" addresses to virtual addresses using identity map.
// Cannot share a CODE descriptor for both kernel and user
// because it would have to have DPL_USR, but the CPU forbids
// an interrupt from CPL=0 to DPL=3.
c = &cpus[cpuid()];
c->gdt[SEG_KCODE] = SEG(STA_X|STA_R, 0, 0xffffffff, 0);
c->gdt[SEG_KDATA] = SEG(STA_W, 0, 0xffffffff, 0);
c->gdt[SEG_UCODE] = SEG(STA_X|STA_R, 0, 0xffffffff, DPL_USER);
c->gdt[SEG_UDATA] = SEG(STA_W, 0, 0xffffffff, DPL_USER);
lgdt(c->gdt, sizeof(c->gdt));
}
作成されたセグメントディスクリプタをgdbで確認すると以下のようになっている。
$1 = {lim_15_0 = 0x0, base_15_0 = 0x0, base_23_16 = 0x0, type = 0x0, s = 0x0, dpl = 0x0, p = 0x0, lim_19_16 = 0x0, avl = 0x0, rsv1 = 0x0, db = 0x0, g = 0x0, base_31_24 = 0x0}
$2 = {lim_15_0 = 0xffff, base_15_0 = 0x0, base_23_16 = 0x0, type = 0xa, s = 0x1, dpl = 0x0, p = 0x1, lim_19_16 = 0xf, avl = 0x0, rsv1 = 0x0, db = 0x1, g = 0x1, base_31_24 = 0x0}
$3 = {lim_15_0 = 0xffff, base_15_0 = 0x0, base_23_16 = 0x0, type = 0x2, s = 0x1, dpl = 0x0, p = 0x1, lim_19_16 = 0xf, avl = 0x0, rsv1 = 0x0, db = 0x1, g = 0x1, base_31_24 = 0x0}
$4 = {lim_15_0 = 0xffff, base_15_0 = 0x0, base_23_16 = 0x0, type = 0xa, s = 0x1, dpl = 0x3, p = 0x1, lim_19_16 = 0xf, avl = 0x0, rsv1 = 0x0, db = 0x1, g = 0x1, base_31_24 = 0x0}
$5 = {lim_15_0 = 0xffff, base_15_0 = 0x0, base_23_16 = 0x0, type = 0x2, s = 0x1, dpl = 0x3, p = 0x1, lim_19_16 = 0xf, avl = 0x0, rsv1 = 0x0, db = 0x1, g = 0x1, base_31_24 = 0x0}
cpuid関数
この関数は、この関数を実行しているプロセッサのcpuidを返す。
ここで言うcpuidとは、cpus配列のインデックスのこと。
各プロセッサのcpu構造体はcpus配列のエントリとして保持しており、mycpu関数はそれを実行しているプロセッサのエントリを返してくれる。
そのエントリのアドレスからcpus配列の先頭アドレスを引けば、cpus配列内でのインデックスになる。
proc.c
> 30 int
> 31 cpuid() {
> 32 return mycpu()-cpus;
> 33 }
mycpu関数
この関数は、この関数を実行しているプロセッサのcpu構造体をcpus配列から探して返す。
eflagsレジスタの値を取得し、Interrupt enableビット（9bit）を確認して、割り込みが無効になっていることを確認する。 0が無効で1が有効。 eflagsレジスタの各bitの役割は「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）の「Vol.3 2.3 SYSTEM FLAGS AND FIELDS IN THE EFLAGS REGISTER」に書いてある。
cpus配列をfor文で走査し、apicidフィールドの値が関数を実行しているプロセッサのLAPIC IDと等しいエントリを探す。 各cpu構造体のapicidフィールドは「5.4. mpinit関数」で設定済み。
mmu.h
#define FL_IF 0x00000200 // Interrupt Enable
proc.c
struct cpu*
mycpu(void)
{
int apicid, i;
if(readeflags()&FL_IF)
panic("mycpu called with interrupts enabled\n");
apicid = lapicid();
// APIC IDs are not guaranteed to be contiguous. Maybe we should have
// a reverse map, or reserve a register to store &cpus[i].
for (i = 0; i < ncpu; ++i) {
if (cpus[i].apicid == apicid)
return &cpus[i];
}
panic("unknown apicid\n");
}
readeflags関数
この関数はeflagsレジスタの値を取得する。
pushfl命令はeflagsレジスタの内容をスタックに積む命令。
x86.h
static inline uint
readeflags(void)
{
uint eflags;
asm volatile("pushfl; popl %0" : "=r" (eflags));
return eflags;
}
lapic関数
この関数は、この関数を実行しているプロセッサのLAPIC IDを取得する。
LAPIC IDは 「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）の「Vol.3 10.4.6 Local APIC ID」によると、Local APIC ID Register（0x20）の24～31bitから得られる。
LAPICへのアクセスについては「5.4. mpinit関数」に書いた。
lapic.c
int
lapicid(void)
{
if (!lapic)
return 0;
return lapic[ID] >> 24;
}
5.7. picinit関数
この関数はMPに対応していない古いPICでの割り込みを無効化する。
outb関数でポート0x20と0xA1に0xFFを書き込んでいる。 「OSDev I/O Ports」（リンク10）によると、ポート0x21はThe first Programmable Interrupt Controllerで、ポート0xA1はThe second PIC。 「OSDev 8259 PIC」（リンク16）の「Disabling」によると、LAPICとIOAPICを使用する場合はPICを無効化しなければいならず、その方法として0xFFを設定する。
picirq.c
#define IO_PIC1 0x20 // Master (IRQs 0-7)
#define IO_PIC2 0xA0 // Slave (IRQs 8-15)
// Don't use the 8259A interrupt controllers. Xv6 assumes SMP hardware.
void
picinit(void)
{
// mask all interrupts
outb(IO_PIC1+1, 0xFF);
outb(IO_PIC2+1, 0xFF);
}
5.8. ioapicinit関数
この関数は、大域変数ioapicにIOAPICへのアクセスアドレスを設定し、IOリダイレクションテーブルの設定を行う。
IRQ0～23番が、BSPにIRQ32～55番でリダイレクトされるよう設定を行い、それら全てを無効化する。
「OSDev IOAPIC」（リンク17）のexternal linksからIOAPICの仕様書「82093AA I/O ADVANCED PROGRAMMABLE INTERRUPT CONTROLLER (IOAPIC)」（リンク18）が確認できる。
仕様書の「3.0. REGISTER DESCRIPTION」によると、IOAPICの操作はI/O Register Selectレジスタにアクセスしたいレジスタのオフセットを書き込み、I/O Windowレジスタを通してデータの読み書きを行う。
I/O Register Selectレジスタのアドレスはデフォルトで0xFEC00000だが、制限された範囲内で変更が可能。xv6ではデフォルトのまま使用する。
I/O Windowsレジスタのアドレスもデフォルトの0xFEC00010になる。
xv6ではこの2つのレジスタにアクセスするため、ioapic構造体を定義している。
2つのアドレスは16バイト離れているため、padフィールドを設けている。
レジスタへの読み書きはioapicread関数とioapicwrite関数で行う。
ioapic.c
#define IOAPIC 0xFEC00000 // Default physical address of IO APIC
/* 略 */
volatile struct ioapic *ioapic;
// IO APIC MMIO structure: write reg, then read or write data.
struct ioapic {
uint reg;
uint pad[3];
uint data;
};
static uint
ioapicread(int reg)
{
ioapic->reg = reg;
return ioapic->data;
}
static void
ioapicwrite(int reg, uint data)
{
ioapic->reg = reg;
ioapic->data = data;
}
仕様書の「Table 2. IOAPIC Registers」より、アクセスできるIOAPICのレジスタとオフセットは以下の通り。
- IOAPIC ID（オフセット0x00）
- IOAPIC Version（0x01）
- IOAPIC Arbitration ID（0x02）
- Redirection Table（0x10～0x3F）
IOリダイレクションテーブルを使用することで、外部割込みソースからの割込みをそのIRQ番号に応じてLAPICにリダイレクトすることができる。
テーブルのインデックスが入力されるIRQ番号に対応しており、各エントリにリダイレクト先LAPICやIRQ番号等を設定する。
IOAPICへ入力されるIRQ番号がそれぞれどの割込みソースに割り当てられているのかは、そのデバイスが接続されているIOAPICのピンに依存する。
しかし、一般的に使用されるIRQ番号は決まっており、仕様書の「2.4. Interrupt Signals」の記載のほか、「OSDev Interrupt」（リンク29）の「General IBM-PC Compativle Interrupt Information」にもリストされている。
これらによると、例えばIRQ0はProgrammable Interrupt Timer Interruptに、IRQ1はKeyboard Interruptに使用されることがわかる。
エントリのサイズは64bitで、上下32bitずつオフセットを変えてアクセスすることになる。
仕様書の表2によるとテーブルのオフセット範囲は0x10～0x3Fであるため、エントリ数は24だが、IOAPIC VersionレジスタのMaximum Redirection Entryフィールド（16～23bit）から最大エントリ番号を得ることができる。
記載によると、最大で240エントリ持つことができる。
ioapicinit関数では、まず大域変数ioapicにIOAPICへのアクセスアドレス0xFEC00000を設定する。
次にIOリダイレクションテーブルの最大エントリ番号と、IOAPIC IDを取得する。
デバッガで最大エントリ番号を見ると、今回は仕様書の値と同じ24（値は23）だった。
IOAPIC IDが「5.4. mpinit関数」にてMP設定テーブルから取得したIOAPIC IDと異なる場合、コンソールにメッセージを出力する。
出力に使用するcprintf関数は「5.17 startothers関数」で見る。
for文でIOリダイレクションテーブルのエントリを走査し、以下の設定を行う。 エントリの構造は仕様書の「3.2.4. IOREDTBL[23:0]—I/O REDIRECTION TABLE REGISTERS」に記載されている。
- Interrupt Mask（16bit）に1をセットしエントリを無効化
- Interrupt Vector（0～7bit）にリダイレクト先IRQ番号としてタイマー割込み32番（T_IRQ0）から順にセット
- Destination Mode（11bit）を0にしてPhysical Modeをセット
- Destination Field（56～63bit）に0をセット。このフィールドはDestination Modeによって意味が異なり、Physical Modeではリダイレクト先のLAPIC IDを意味する。0なのでBSPにリダイレクトする。
ioapic.c
#define REG_ID 0x00 // Register index: ID
#define REG_VER 0x01 // Register index: version
#define REG_TABLE 0x10 // Redirection table base
/* 略 */
#define INT_DISABLED 0x00010000 // Interrupt disabled
/* 略 */
void
ioapicinit(void)
{
int i, id, maxintr;
ioapic = (volatile struct ioapic*)IOAPIC;
maxintr = (ioapicread(REG_VER) >> 16) & 0xFF;
id = ioapicread(REG_ID) >> 24;
if(id != ioapicid)
cprintf("ioapicinit: id isn't equal to ioapicid; not a MP\n");
// Mark all interrupts edge-triggered, active high, disabled,
// and not routed to any CPUs.
for(i = 0; i <= maxintr; i++){
ioapicwrite(REG_TABLE+2*i, INT_DISABLED | (T_IRQ0 + i));
ioapicwrite(REG_TABLE+2*i+1, 0);
}
}
このIOリダイレクションテーブルの設定により、IRQ0～23番がBSPのLAPICにIRQ32～55番でリダイレクトされるが、この時点では全てのリダイレクトが無効化された状態になっている。
エントリの有効化は、後ほどioapicenable関数を呼び出して個別に行う。その際に割込み先LAPIC IDも再設定する。
5.9. consoleinit関数
この関数はdevsw配列の1番にコンソール読み書き用の関数を設定し、IOAPICのキーボードコントローラからの割込みのリダイレクト（IRQ1からIRQ33へのリダイレクト）を有効化する。
デバイスの読み書きにはdevsw構造体を使用する。
この構造体は関数ポインタreadとwriteを持っており、そこにデバイス毎の読み書き用の関数を持っておく。
file.cでdevsw構造体の配列devswが定義されており、デバイス10個分の構造体を持つことができる。
この配列の1番目をコンソールのために使用する。残りの9個は使用しない。
ディスクの読み書きにはdevsw構造体を使用せず、ide.cに定義されているiderw関数を使用する。
file.h
struct devsw {
int (*read)(struct inode*, char*, int);
int (*write)(struct inode*, char*, int);
};
file.c
struct devsw devsw[NDEV];
param.h
#define NDEV 10 // maximum major device number
コンソールの排他制御にはconsole.cの静的変数consを使用する。 consはspinlock構造体のlockフィールドと、int型のlockingフィールドを持っている。 lockフィールドはコンソールを使用する際のロックに使われる。 ロックについては「5.10. ロック（spinlock, sleeplock）」に書く。 lockingフィールドの値は通常1で、panic関数が呼ばれると0になり、その後1に戻ることはない。 このフィールドはcprintf関数内で使用されており、値が1の場合はコンソールのロックを取り、0の場合は取らない。 おそらくpanic関数が呼ばれた際に、既にコンソールのロックが取られている可能性があるため、panic関数でlockingを0にするのだと思う。
console.c
static struct {
struct spinlock lock;
int locking;
} cons;
consoleinit関数ではまずconsのlockフィールドを初期化する。
devsw配列のコンソール（1番）のwriteフィールドにconsolewrite関数を設定し、readフィールドにconsoleread関数を設定する。
次にconsのlockingフィールドを1で初期化する。
この値は上述したように、panicが呼ばれるまで0にならない。
最後に、ioapicenable関数でキーボードコントローラからの割込みを有効化する。
file.h
#define CONSOLE 1
traps.h
#define IRQ_KBD 1
console.c
void
consoleinit(void)
{
initlock(&cons.lock, "console");
devsw[CONSOLE].write = consolewrite;
devsw[CONSOLE].read = consoleread;
cons.locking = 1;
ioapicenable(IRQ_KBD, 0);
}
consolewrite関数
この関数はコンソールに文字を出力する。
inodeのロックを解放し、コンソールのロックを取ってbufからn文字分出力する。
出力が終わったらコンソールのロックを解放し、inodeのロックを再び取得する。
コンソール出力中はinodeのロックが不要なのでロックを解放する。
inodeについては「5.11. iノードのロック」に書く。
出力はconsputc関数で行う。
consputc関数の引数はint型だが、アスキーコードの範囲で渡したいので、0xffで論理積を取って1バイトだけ渡す。
console.c
int
consolewrite(struct inode *ip, char *buf, int n)
{
int i;
iunlock(ip);
acquire(&cons.lock);
for(i = 0; i < n; i++)
consputc(buf[i] & 0xff);
release(&cons.lock);
ilock(ip);
return n;
}
consputc関数はシリアルポートが有ればそちらに書き込みを行い、無ければメモリにマップされているビデオメモリに書き込む。
シリアルポートへの書き込みはuartputc関数で行い、ビデオメモリへの書き込みはcgaputc関数で行う。
シリアルポートの有無はmain関数から呼ばれるuartinit関数で確認する。
また、シリアルポートにバックスペースを書き込む際には、'\b'でカーソル位置を1文字戻し、空白を印字し、再びカーソル位置を1文字戻す。
console.cにはint型の静的変数panickedが定義されており、この値はpanic関数が呼ばれると1になる。
consputc関数は、panic関数が呼ばれている場合は、割り込みを無効化し、無限ループする。
console.c
static int panicked = 0;
/* 略 */
void
consputc(int c)
{
if(panicked){
cli();
for(;;)
;
}
if(c == BACKSPACE){
uartputc('\b'); uartputc(' '); uartputc('\b');
} else
uartputc(c);
cgaputc(c);
}
uartputc関数は「5.13. uartinit」に書くとして、cgaputc関数を見る。 cgaputc関数はメモリ上のビデオメモリ領域に書き込むことで画面出力を行う。
カーソル位置はCRTコントローラを使用して読み書きする。 「Hardware Level VGA and SVGA Video Programming Information Page CRT Controller Registers」（リンク19） によると、CRTCレジスタにはアドレスレジスタとデータレジスタがあり、それぞれポート0x3d4とポート0x3d5からアクセスできる。 リンク先の「Cursor Location High Register (Index 0Eh)」と「Cursor Location Low Register (Index 0Fh)」に、アドレスレジスタに14（0xE）と15（0xF）を書き込むことで、データレジスタからカーソル位置を取得することができると記載がある。 カーソル位置は画面左上を0として、1行80文字、25行までで連続して増加していく。
プロテクトモード時のビデオモードに関しては「OSDev Drawing In Protected Mode」（リンク20）に記載されており、ここではCGAモードなので物理アドレス0xb8000からビデオメモリ領域になっている。
ビデオメモリへは2バイトずつ書き込みを行い、書き込む値は「OSDev Text UI」（リンク21）によると、上位1バイトで色を指定し、下位1バイトでASCIIコードを指定する。
色の指定方法はリンク先の「Colours」で図解されており、上位4bitで背景色、下位4bitで文字色を指定する。
また、3, 7bit目がそれぞれbright bitとなっており、立てると明るい色になる。
cgaputc関数では0x0700で論理和を取り文字色をライトグレイにしているが、例えば0xb200で論理和を取ると背景色がライトシアンとなり、文字色が緑色となる。
cgaputc関数ではint型の変数posでカーソル位置を操作する。
引数が改行コードの場合、posが次の行の先頭になるように、80 - 現在位置%80だけ加算する。
引数がバックスペースかつposが0より大きい場合、posをデクリメントする。
それ以外の場合は現在位置の次の位置に引数の文字（1バイト）を文字色ライトグレイ、背景色黒で描画する。
変数crtはメモリ上のビデオメモリ領域の開始アドレス（0xb8000）を持っている。
カーソル位置が0未満或いは25行80列より大きいところを指している場合、panicする。
25行目を指している場合、memmove関数を使用して全体を1行分前方に動かし、カーソル位置も1行分減らす。
全体を1行分前にコピーするので、最終行に値が残っている。それをmemset関数で0にリセットする。
最後に画面上の現在の位置にスペースを書き込む。
console.c
#define BACKSPACE 0x100
#define CRTPORT 0x3d4
static ushort *crt = (ushort*)P2V(0xb8000); // CGA memory
static void
cgaputc(int c)
{
int pos;
// Cursor position: col + 80*row.
outb(CRTPORT, 14);
pos = inb(CRTPORT+1) << 8;
outb(CRTPORT, 15);
pos |= inb(CRTPORT+1);
if(c == '\n')
pos += 80 - pos%80;
else if(c == BACKSPACE){
if(pos > 0) --pos;
} else
crt[pos++] = (c&0xff) | 0x0700; // black on white
if(pos < 0 || pos > 25*80)
panic("pos under/overflow");
if((pos/80) >= 24){ // Scroll up.
memmove(crt, crt+80, sizeof(crt[0])*23*80);
pos -= 80;
memset(crt+pos, 0, sizeof(crt[0])*(24*80 - pos));
}
outb(CRTPORT, 14);
outb(CRTPORT+1, pos>>8);
outb(CRTPORT, 15);
outb(CRTPORT+1, pos);
crt[pos] = ' ' | 0x0700;
}
memmove関数
この関数は第二引数のアドレス（ソース）から第三引数のサイズ分、第一引数のアドレス（移動先）にコピーする。 このとき、ソースが移動先より手前で開始し、移動先がコピーサイズ分に被るとき、頭からコピーしていくとソースの一部が上書きされ失われるので、末尾からコピーしていく。
string.c
void*
memmove(void *dst, const void *src, uint n)
{
const char *s;
char *d;
s = src;
d = dst;
if(s < d && s + n > d){
s += n;
d += n;
while(n-- > 0)
*--d = *--s;
} else
while(n-- > 0)
*d++ = *s++;
return dst;
}
consoleread関数
この関数はコンソールからnバイト読み込む。
コンソールへの入力に起因する割り込みから順に書くことにする。
なお、割り込み時の動作については「」に書く。
キーボードあるいはシリアルポートから入力が行われると、割込みが生じ最終的にkbdintr関数かuartintr関数が呼ばれる。
それらはいずれもconsoleintr関数を呼び出しており、引数としてkbdgetc関数あるいはuartgetc関数を渡す。
uartgetc関数については「5.13. uartinit関数」に書く。
kbd.c
void
kbdintr(void)
{
consoleintr(kbdgetc);
}
uart.c
void
uartintr(void)
{
consoleintr(uartgetc);
}
kbdgetc関数
この関数はキーボードコントローラからの入力信号（スキャンコード）を解析し、キーボードに入力された文字コードを返す。
「Bochs Developers Guide」（リンク9）によると、ポート0x60（アウトプットバッファ）から、スキャンコードを取得できる。
スキャンコードに関しては「Keyboard scancodes Andries Brouwer」（リンク7）で解説されており、キーが押されるときmakeコードが入力され、離されるときにbreakコードが入力される。
breakコードはmakeコードに0x80が加算された値になっている。
例えば、aキーが押されると0x1eが入力され、キーが離されて0x9eが入力される。
また、コード0xe0と0xe1はエスケープシーケンスになっており、プリフィクスとして使用される。
あるキーを押すと、0xe0が入力され、続けて入力される特定のスキャンコードと共に解釈することになる。
例えば、方向キー上が押されると0xe0が入力され、続けて0x48が入力され、離された後に0xc8が入力される。
なので、gdbで確認する際はキーが押されたときと、離されたときを別々に観測するとよい。
xv6では、スキャンコードから文字コードへの変換にkbd.hに定義されている3つの配列normalmap、shiftmap、ctlmapを使用する。
各配列は名前の通り、普通の入力、シフトキーを使用した入力、コントロールキーを使用した入力で使用される。
参照する配列の切り替えには、shiftcodeとtogglecodeの2つの配列を使用する。
そこにはCTRLキーやALTキー、CAPSLOCKキー等が定義されている。
kbdget関数では配列charcodeに変換に使用する3つの配列を持っておく。
4番目のctlmapはシフトキーとコントロールキーが同時に入力された場合に使用される。
ctlmap配列ではCマクロが使用されており、このマクロは与えられた文字コードを制御コードに変換する。
各制御コードは「ASCII Code - The extended ASCII table」（リンク27）で確認できる。
例えばC('C')の場合、
'C' - '@' = 0x43 - 0x40 = 0x03
なので、End of Text（0x03）となる。
kbd.h
// C('A') == Control-A
#define C(x) (x - '@')
エスケープシーケンス（0xe0）や、シフトキー、コントロールキー、CAPSLOCKのオンオフは変数shiftの各bitで表現する。 各bitの役割は以下。
kbd.h
> 9 #define SHIFT (1<<0)
> 10 #define CTL (1<<1)
> 11 #define ALT (1<<2)
> 12
> 13 #define CAPSLOCK (1<<3)
> 14 #define NUMLOCK (1<<4)
> 15 #define SCROLLLOCK (1<<5)
> 16
> 17 #define E0ESC (1<<6)
変数shiftのSHIFTビットもCTLビットも設定されていれば4エントリ目のctlmapテーブルが使用される。
kbdgetc関数ははじめに、キーボードコントローラのステータス（0x64）を取得する。
ステータスの0bitからインプットバッファの状態を確認でき、1のときフル、0のとき空を示す。
アウトプットバッファ（0x60）から1つ分のスキャンコードを取得し、次のように分岐する。
- エスケープシーケンス（0xE0）の場合、変数shiftのE0ESCビットを立てる。
- breakコードの場合、つまりキーが離された場合、変数shiftのE0ESCビット、SHIFTビット、CTLビット、ALTビットを0にする。 CAPSLOCKビットやNUMLOCKビット、SCROLLLOCKビットは入力を跨いで有効となるため変更しない。 エスケープシーケンス以外の場合、0x7fとの論理積によりmakeコードを取得している。
- 変数shiftのE0ESCビットが1の場合、変数dataにbreakコード（0x80を論理和）を代入し、E0ESCビットを0にする。エスケープシーケンス（0xE0）が使用される場合breakコードが入力されないので、続くスキャンコードをbreakコードに変換する必要がある。
次に、スキャンコードの変換に用いる配列を決定するため、変数shiftを設定する。
shiftcode配列はそのままビットを設定するが、togglecode配列はCAPSLOCKやNUMLOCK等を扱うため排他的論理和でビットを更新する。
最後に配列から文字コードを取得するが、変数shiftのCAPSLOCKビットが1の場合、アルファベットの大文字と小文字を変換する。
kbd.c
int
kbdgetc(void)
{
static uint shift;
static uchar *charcode[4] = {
normalmap, shiftmap, ctlmap, ctlmap
};
uint st, data, c;
st = inb(KBSTATP);
if((st & KBS_DIB) == 0)
return -1;
data = inb(KBDATAP);
if(data == 0xE0){
shift |= E0ESC;
return 0;
} else if(data & 0x80){
// Key released
data = (shift & E0ESC ? data : data & 0x7F);
shift &= ~(shiftcode[data] | E0ESC);
return 0;
} else if(shift & E0ESC){
// Last character was an E0 escape; or with 0x80
data |= 0x80;
shift &= ~E0ESC;
}
shift |= shiftcode[data];
shift ^= togglecode[data];
c = charcode[shift & (CTL | SHIFT)][data];
if(shift & CAPSLOCK){
if('a' <= c && c <= 'z')
c += 'A' - 'a';
else if('A' <= c && c <= 'Z')
c += 'a' - 'A';
}
return c;
}
consoleintr関数
この関数はキーボードやシリアルポートから入力された値を読み取り、それをコンソールに出力する。 また、入力を待っているプロセスを起床させ、値を渡す。
入力を待っているプロセスはconsoleread関数でスリープしており、input構造体を通して値を渡す。
input構造体は次の4つのフィールドで構成される。
- buf: 入力された直近128文字を持つ
- r: bufフィールドからプロセスが読み出した位置を示すとともに、コンソールへの出力を待っているプロセスを起床させるチャネルとしても使用される。
- w: bufフィールドからコンソールに出力した位置を示す
- e: bufフィールドの現在位置を表す
bufは要素127まで来たら要素0から上書きするため、読み書きする際は要素数で割った余りをインデックスとして使用する。 r、w、eの各フィールドは0から開始する。 文字が入力される度にeがインクリメントされbufに文字が入る。 それをコンソールに出力するとwがeで更新され、追いつく。 コンソールへの文字出力後、consoleread関数でスリープしているプロセスが起床され、そこでrからwの位置までbufの中身を読み取る。 r、w、eは明示的に初期化されることはなく、uintの最大値2の32乗-1まで増加し続ける。
console.c
#define INPUT_BUF 128
struct {
char buf[INPUT_BUF];
uint r; // Read index
uint w; // Write index
uint e; // Edit index
} input;
while文で1文字ずつ読み、switch文で次のように分岐する。
- Ctrl + Pの場合、procdump関数を実行する。この関数はプロセスの一覧を出力し、スリープ状態のプロセスの場合はコールスタックも出力する。
- Ctrl + Uの場合、コンソールの現在の行の文字を全て消す。 現在位置eを行頭まで戻しつつ、文字を1文字ずつ消していく。
- Ctrl + H、あるいはバックスペース（0x7f）の場合、1文字消す。 バックスペースが入力されると、キーボードの場合はkbdgetc関数からバックスペース（0x08）が返ってきてCtrl + Hのケースに一致し、シリアルポートの場合はuartgetc関数からデリート（0x7f）が返ってきてこのケースに一致する。 コンソールの現在位置eと前回の最終出力位置wが等しくない場合、つまり消せる入力がある場合はeをデクリメントし、consputc関数を使ってバックスペースを出力する。
- 上記以外の場合、文字をコンソールに出力する。 キャリッジリターン（0x0d）は改行（0x0a）に変換する。
次の場合、出力済み位置wに現在位置eを代入し、rのアドレスをチャネルとしてスリープしているプロセスを起床させる。
- 入力が終了する（Enter）
- Ctrl + Dが入力される（EOT）
- 読み込む必要がある文字列がbufの容量と等しくなった場合
スリープしているプロセスはコンソールへ入力された文字列（bufの中身）を読み取り、解釈する。
console.c
void
consoleintr(int (*getc)(void))
{
int c, doprocdump = 0;
acquire(&cons.lock);
while((c = getc()) >= 0){
switch(c){
case C('P'): // Process listing.
// procdump() locks cons.lock indirectly; invoke later
doprocdump = 1;
break;
case C('U'): // Kill line.
while(input.e != input.w &&
input.buf[(input.e-1) % INPUT_BUF] != '\n'){
input.e--;
consputc(BACKSPACE);
}
break;
case C('H'): case '\x7f': // Backspace
if(input.e != input.w){
input.e--;
consputc(BACKSPACE);
}
break;
default:
if(c != 0 && input.e-input.r < INPUT_BUF){
c = (c == '\r') ? '\n' : c;
input.buf[input.e++ % INPUT_BUF] = c;
consputc(c);
if(c == '\n' || c == C('D') || input.e == input.r+INPUT_BUF){
input.w = input.e;
wakeup(&input.r);
}
}
break;
}
}
release(&cons.lock);
if(doprocdump) {
procdump(); // now call procdump() wo. cons.lock held
}
}
consoleread関数はinput構造体のbufフィールドを読み込む。
コンソールの読み込み位置（r）が出力済み位置（w）に追いついている場合、入力待ちのために現在のプロセスをスリープ状態にする。
このため第一引数で与えられたiノードのロックを開放する。
スリープについては「5.10. ロック（spinlock, sleeplock）」に書く。
プロセスが起床し、出力済み位置（w）が読み込み位置（r）よりも先に進んだ場合、rをインクリメントしbufから文字コードを取り出す。
文字コードがCtrl + D（EOT）の場合、読み込みのwhileループから抜ける。
このとき、既に何文字か読み込んでいた場合はrをデクリメントする。
これにより、次回実行時にはwhileループに入らず、そのまま同じEOTを読み込むことになり、直ぐにbreakでループを抜けることになる。
呼び出し元にreturnで返される読み込んだ文字数は0になり、第二引数dstには何も書き込まれず、呼び出し元は読み込みたい文字列がEOTで終了されたことを知ることができる。
console.c
int
consoleread(struct inode *ip, char *dst, int n)
{
uint target;
int c;
iunlock(ip);
target = n;
acquire(&cons.lock);
while(n > 0){
while(input.r == input.w){
if(myproc()->killed){
release(&cons.lock);
ilock(ip);
return -1;
}
sleep(&input.r, &cons.lock);
}
c = input.buf[input.r++ % INPUT_BUF];
if(c == C('D')){ // EOF
if(n < target){
// Save ^D for next time, to make sure
// caller gets a 0-byte result.
input.r--;
}
break;
}
*dst++ = c;
--n;
if(c == '\n')
break;
}
release(&cons.lock);
ilock(ip);
return target - n;
}
ioapicenable関数
この関数は指定されたIRQのリダイレクトを有効化し、リダイレクト先LAPICを設定する。
IOリダイレクションテーブルの設定は「5.8. ioapicinit関数」で行った。 ここではそこでも使用したioapicwrite関数にて、エントリのDestination Field（56bit（32+24））にLAPIC IDを設定する。 また、同時にInterrupt Mask（16bit）が0に設定されることにより割り込みのリダイレクトを有効化している。
ioapic.c
void
ioapicenable(int irq, int cpunum)
{
// Mark interrupt edge-triggered, active high,
// enabled, and routed to the given cpunum,
// which happens to be that cpu's APIC ID.
ioapicwrite(REG_TABLE+2*irq, T_IRQ0 + irq);
ioapicwrite(REG_TABLE+2*irq+1, cpunum << 24);
}
5.10. ロック（spinlock, sleeplock）
「xv6 a simple, Unix-like teaching operating system」（リンク1）の4章「Locking」と5章「Scheduling」を読むとよい。
xv6にはスピンロックとスリープロックの2種類のロックがあり、それぞれacquire関数とacquiresleep関数で取ることができる。
前者はロックが取れるまでプロセッサを占有するので短時間のロックに使用し、後者はロックが取れるまでプロセッサを明け渡すので長時間のロックに使用する。
ロックの解放にはrelease関数とreleasesleep関数をそれぞれ使用する。
スピンロック
このロックはロックが取れるまでプロセッサを明け渡さない。
spinlock構造体を使用する。
主に使用するのはlockedフィールドで、1のときロック済みであることを示す。
cpuフィールドやpcsフィールドはデバッグに使用する。
spinlock.h
struct spinlock {
uint locked; // Is the lock held?
// For debugging:
char *name; // Name of lock.
struct cpu *cpu; // The cpu holding the lock.
uint pcs[10]; // The call stack (an array of program counters)
// that locked the lock.
};
acquire関数
この関数は、割り込みを無効にし、他のプロセッサがロックを解放するまで待ってからロックを取得する。 ロック取得後にspinlock構造体に自分のcpu構造体と、最大10個分のコールスタックを記録する。
まず現在のプロセッサで割り込みを禁止する。
もしもここで割り込みを禁止しなかった場合、あるロックを取得し、直後に割り込みが生じて同じロックを取得しようとした場合に割り込み側がロックが解放されるまで待つことになるが、ロックを持っている処理は進まないのでデッドロックとなる。
現在のプロセッサが既にそのロックを取得している場合はpanicする。
spinlock構造体のlockedフィールドを1にできるまで（ロックを取得できるまで）ループする。
ここがスピンロックの肝であり、xchg関数でlockedフィールドの独立性を保つ。
ロック取得前後の命令の実行順序が入れ替わらないように__sync_synchronize関数を呼び出す。
この関数はGCCのビルトイン関数で、「Using the GNU Compiler Collection (GCC)」 （リンク3）の「6.51 Legacy __sync Built-in Functions for Atomic Memory Access」によると、フルメモリバリアを行う関数である。
手元でコードを書きアセンブリ出力してみると、mfence命令にコンパイルされる。
mfence命令は、「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）によると、この命令の前にあるメモリを読み書きする命令は必ずこの命令よりも前に実行され、この命令の後にあるメモリを読み書きする命令は必ずこの命令よりも後に実行されることを保証する。
これはプロセッサのOut-Of-Order実行を抑止するという点で、コンパイラレベルの最適化を抑止するvolatile修飾子とは異なる。
Out-Of-Order実行やプロセッサの仕組みについては「プロセッサを支える技術」（書籍4）がとても詳しくて分かりやすい。
acquire関数は最後に、デバッグのための情報をspinlock構造体の中に残す。
spinlock.c
void
acquire(struct spinlock *lk)
{
pushcli(); // disable interrupts to avoid deadlock.
if(holding(lk))
panic("acquire");
// The xchg is atomic.
while(xchg(&lk->locked, 1) != 0)
;
// Tell the C compiler and the processor to not move loads or stores
// past this point, to ensure that the critical section's memory
// references happen after the lock is acquired.
__sync_synchronize();
// Record info about lock acquisition for debugging.
lk->cpu = mycpu();
getcallerpcs(&lk, lk->pcs);
}
pushcli関数とpopcli関数
割り込みの禁止は呼び出される関数によりネストされるので、これらの関数で管理する。
pushcli関数は現在のcpuの割り込みを禁止する。 この関数が実行される度にcpu構造体のncliフィールドがインクリメントされる。 関数呼び出し前に既に割り込み禁止としている場合があるため、ncliが0のときだけeflagsレジスタのInterrupt enableビット（9bit）を、cpu構造体のintenaフィールドに保存する。
popcli数はpushcli関数とは反対に、ncliフィールドをデクリメントする。 ncliフィールドとintenaフィールドに従って割り込みを有効化する。
spinlock.c
void
pushcli(void)
{
int eflags;
eflags = readeflags();
cli();
if(mycpu()->ncli == 0)
mycpu()->intena = eflags & FL_IF;
mycpu()->ncli += 1;
}
void
popcli(void)
{
if(readeflags()&FL_IF)
panic("popcli - interruptible");
if(--mycpu()->ncli < 0)
panic("popcli");
if(mycpu()->ncli == 0 && mycpu()->intena)
sti();
}
holding関数
この関数は引数のspinlock構造体のロックを現在のプロセッサが取っている場合に1を返す。
spinlock.c
int
holding(struct spinlock *lock)
{
int r;
pushcli();
r = lock->locked && lock->cpu == mycpu();
popcli();
return r;
}
xchg関数
この関数はaddrにnewvalを代入し、元々入っていた値を呼び出し元に返す。 このとき、必ず単一のプロセッサのみが値の代入に成功する。
lock接頭辞とxchgl命令により、単一のプロセッサのみが値を変更できることを保証している。 命令的には値を代入するというより、交換する。 「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）によると、lock接頭辞は特定の命令あるいは出力がメモリである命令の場合に使用することができ、プロセッサのロッキングプロトコルを働かせることができる。 xchgl命令はlock接頭辞と組み合わせることが可能で、第一オペランドと第二オペランドの内容を交換する。
この関数の拡張インラインアセンブリの、入出力と破壊対象は次のようになっている。
出力:
"+m" (*addr)
と
"=a"(result)
入力:
"1"(newval)
破壊対象:
"cc"
使用されている各制約は「Using the GNU Compiler Collection (GCC)」（リンク3）に記載されている。
"cc" は「6.44.2 Extended Asm - Assembler Instructions with C Expression Operands」に記載されており、他の制約は「6.44.3 Constraints for asm Operands」の各項に記載されている。
出力について、
"+"
は読み書きに使用されることを示し、
"m"
はメモリのアドレスであることを示す。
また、
"="
は書き込みのみに使用されることを示し、
"a"
は
x86ではeaxレジスタを示す。
入力について、
"1"
は %1 と同じものを指すので、eaxとなる。
破壊対象について、
"cc"
はフラグレジスタを示す。
しかし、Intel SDM（リンク8）のlock接頭辞とxchg命令のFlags AffectedにはどちらもNoneが記載されているため、なぜこれが必要なのかはわからない。
xchg関数の動きをまとめると、入力としてnewvalをeaxに入れ、xchgl addr, %eaxとなり、addrとeaxの中身が交換され、eaxにはaddrに元々入っていた値が入る。
出力としてeaxをresultと紐づけているので、resultにはaddrに元々入っていた値が入る。
acquire関数では、この関数からの戻り値をwhileループの条件に使用している。 戻り値が1の場合は他のプロセッサがロックを取っていることになり、0の場合は誰もロックを取っていないということになる。
x86.h
static inline uint
xchg(volatile uint *addr, uint newval)
{
uint result;
// The + in "+m" denotes a read-modify-write operand.
asm volatile("lock; xchgl %0, %1" :
"+m" (*addr), "=a" (result) :
"1" (newval) :
"cc");
return result;
}
getcallerpcs関数
この関数は引数pcs配列にコールスタックを作成する。
動作は関数の呼び出し規約が分かると分かりやすい。
呼び出し規約については「コンピュータの構成と設計 第4版」（書籍5）に説明があり、GCCにおける呼び出し規約は「Guide: Function Calling Conventions」（リンク22）にまとめられている。
この関数はまず変数ebpに現在のスタックフレームのベースアドレスを取得する。
スタックには引数pcs、引数v、リターンアドレス、ベースアドレスの順で積まれており、ひとつ16バイトで低いアドレスへ伸びていくので、引数vの積まれているアドレスから、-32バイトするとベースアドレスを得ることができる。
次にspinlock構造体の配列pcsは要素数が10なので、10個分までのスタックフレームのベースアドレスを入れるため、for文で10回ループする。
ベースアドレスをpcs配列に加え、リターンアドレスを変数ebpに代入し、次のループでebp[1]から前のスタックフレームのベースアドレスを取得し、pcs配列に加え、再びリターンアドレスをebpに代入していく。
ベースアドレスが0か、カーネル空間外を指している場合にループを抜ける。
スタックフレームが10個に満たなかった場合、2つめのfor文でpcs配列の残りのエントリに0を代入する。
spinlock.c
void
getcallerpcs(void *v, uint pcs[])
{
uint *ebp;
int i;
ebp = (uint*)v - 2;
for(i = 0; i < 10; i++){
if(ebp == 0 || ebp < (uint*)KERNBASE || ebp == (uint*)0xffffffff)
break;
pcs[i] = ebp[1]; // saved %eip
ebp = (uint*)ebp[0]; // saved %ebp
}
for(; i < 10; i++)
pcs[i] = 0;
}
release関数
この関数はspinlock構造体のロックを解放する。
基本的にacquire関数の動作を反対から行う。 movl命令を用いたロック解放部分以外は上で確認した通り。
spinlock構造体のコールスタックとcpu構造体を0でリセットした後、__sync_synchronize関数でロック解放前と解放後の命令順序を保証する。
ロックの解放は、既に現在のプロセッサが当該ロックを取得していることがholding関数により保証されているため、xchg命令ではなく、move命令でlockedフィールドに0を代入する。
c言語で lk-\>locked = 0 とぜず、拡張インラインアセンブリを使用する理由は、「xv6 a simple, Unix-like teaching operating system」（リンク1）の4章「Code: Locks」で説明されており、c言語の仕様では特段単一の代入命令がatomicに行われることを明記していないため。
ロック解放後、popcli関数で必要に応じて割り込みを可能にする。
spinlock.c
void
release(struct spinlock *lk)
{
if(!holding(lk))
panic("release");
lk->pcs[0] = 0;
lk->cpu = 0;
// Tell the C compiler and the processor to not move loads or stores
// past this point, to ensure that all the stores in the critical
// section are visible to other cores before the lock is released.
// Both the C compiler and the hardware may re-order loads and
// stores; __sync_synchronize() tells them both not to.
__sync_synchronize();
// Release the lock, equivalent to lk->locked = 0.
// This code can't use a C assignment, since it might
// not be atomic. A real OS would use C atomics here.
asm volatile("movl $0, %0" : "+m" (lk->locked) : );
popcli();
}
スリープロック
このロックはロックが取れるまでプロセスをスリープ状態にしてプロセッサを明け渡す。 ディスクにアクセスする可能性がある場合等、長時間ロックを取得する可能性がある場合に使用する。
sleeplock構造体を使用する。 lockedフィールドでロックの状態を管理するが、独立性はspinlock構造体を使用して確保する。 また、後者はプロセスを起床させる際のチャネルとしても使用する。
スリープロックの流れは次の通り。
まだ誰も取得していないスリープロックを取得するとき:
lockedフィールドを1にし、pidフィールドに自分のpidを代入する。
ロック使用後は、lockedとpidを0にリセットし、同ロックを必要としている他のプロセスの状態を実行可能状態にする。
既に誰かが取得しているスリープロックを取得するとき:
自分（プロセス）のチャネルに取得したいスリープロックをセットし、スリープ状態になる。
スリープすると、コンテキストスイッチを行いスケジューラスレッドにプロセッサを明け渡す。
スリープロックが解放されると、それを取っていたプロセスがチャネルを通してスリープ状態のプロセス（自分）を実行可能状態にする。
あとはスケジューラスレッドが自分を実行してくれるまで待つ。
もしも他のプロセスも同じロックを取るためにスリープしている場合、スケジューラがそちらを先に実行してしまうと自分は再びスリープ状態となり、ロック解放まで再度待つことになる。
sleeplock.h
struct sleeplock {
uint locked; // Is the lock held?
struct spinlock lk; // spinlock protecting this sleep lock
// For debugging:
char *name; // Name of lock.
int pid; // Process holding lock
};
acquiresleep関数
この関数はスリープロックを取る。 ロックが取れるまで自身をスリープ状態とする。
同じスリープロックの取得が同時に行われないように、まずsleeplock構造体のlkフィールド（spinlock構造体）のロックを取る。
スリープする場合にはsleeplock構造体のアドレスを起床する際のチャネルとして用いる。
スリープロックが取られていない場合はスリープしない。
sleeplock.c
void
acquiresleep(struct sleeplock *lk)
{
acquire(&lk->lk);
while (lk->locked) {
sleep(lk, &lk->lk);
}
lk->locked = 1;
lk->pid = myproc()->pid;
release(&lk->lk);
}
sleep関数
名前の通りスリープする。
もしも引数のspinlock構造体がプロセステーブルのロックではなかった場合、プロセステーブルのロックを取り、spinlock構造体のロックを解放する。 つまりプロセステーブルのロックを取りたい。 sched関数では、scheduler関数のプロセステーブルを走査するループの中、swtch関数の後のところに復帰する。 そこではプロセステーブルのロックが取得済みの前提で動作しており、ループ終了後にそのロックを解放する。 このためsleep関数内でsched関数を呼ぶ前にプロセステーブルのロックを取得しておく必要がある。
スリープする際には第一引数chanのアドレスをチャネルに設定する。 チャネルはproc構造体のchanフィールドで、他のプロセスがプロセステーブルから特定のプロセスを見つけるために使う。
ここではスリープとはsched関数内でスケジューラスレッドにコンテキストスイッチすることであるため、sched関数呼び出し以降は起床後に実行されることとなる。
proc.c
void
sleep(void *chan, struct spinlock *lk)
{
struct proc *p = myproc();
if(p == 0)
panic("sleep");
if(lk == 0)
panic("sleep without lk");
// Must acquire ptable.lock in order to
// change p->state and then call sched.
// Once we hold ptable.lock, we can be
// guaranteed that we won't miss any wakeup
// (wakeup runs with ptable.lock locked),
// so it's okay to release lk.
if(lk != &ptable.lock){ //DOC: sleeplock0
acquire(&ptable.lock); //DOC: sleeplock1
release(lk);
}
// Go to sleep.
p->chan = chan;
p->state = SLEEPING;
sched();
// Tidy up.
p->chan = 0;
// Reacquire original lock.
if(lk != &ptable.lock){ //DOC: sleeplock2
release(&ptable.lock);
acquire(lk);
}
}
sched関数
sched関数はスケジューラスレッドにコンテキストスイッチする。
各if文でscheduler関数のプロセステーブルのループに戻るための準備ができているかを確認している。 準備ができていないとpanicしてしまう。 必要な準備は次の通り。
- ページテーブルのロックを取得していること
- pushcli関数が1回以上呼ばれていること
- 自分のステータスが実行状態でないこと
- 割り込みが無効になっていること（eflagsレジスタのInterrupt enableビット）
準備ができていることを確認後、自分のcpu構造体からintenaフィールドの値を退避する。
これは再びコンテキストスイッチされ今のプロセスに戻ってきた際に、intenaフィールドの値が変わっているかもしれないため。
そしてswtch関数でスケジューラスレッドにコンテキストスイッチする。
swtch関数については5.22. scheduler関数とmpmain関数に書く。
関数呼び出しのような要領でコンテキストスイッチを行う。
再び今のプロセスにコンテキストスイッチして戻ってきた際に、退避しておいたintenaフィールドの値を復元する。
proc.c
void
sched(void)
{
int intena;
struct proc *p = myproc();
if(!holding(&ptable.lock))
panic("sched ptable.lock");
if(mycpu()->ncli != 1)
panic("sched locks");
if(p->state == RUNNING)
panic("sched running");
if(readeflags()&FL_IF)
panic("sched interruptible");
intena = mycpu()->intena;
swtch(&p->context, mycpu()->scheduler);
mycpu()->intena = intena;
}
releasesleep関数
この関数はスリープロックを解放し、同ロックを必要としているプロセスを起床させる。
同じsleeplock構造体のロックの取得が同時に行われないよう、lkフィールド（spinlock構造体）のロックを取る。
sleeplock構造体のアドレスをチャネルとして、wakeup関数でロックを必要としているプロセスを起床させる。
sleeplock.c
void
releasesleep(struct sleeplock *lk)
{
acquire(&lk->lk);
lk->locked = 0;
lk->pid = 0;
wakeup(lk);
release(&lk->lk);
}
wakeup関数
wakeup関数は引数で渡されたチャネル（アドレス）を元に、スリープ状態のプロセスを実行可能状態にする。 実際のところはwakeup1関数を呼び出す。
プロセステーブルを走査し、同じチャネルを持っているスリープ状態のプロセスを探すため、プロセステーブルのロックを取る。
wakeup1関数にチャネルを渡し、起床処理を行う。
wakeup関数とwakeup1関数に分かれている理由は、呼び出し元が既にプロセステーブルのロックを取得している場合に対応するため。
プロセステーブルのロックを取っていない場合はwakeup関数を呼び出し、既にロックを取っている場合はwakeup1関数を呼び出す。
プロセステーブルを走査し、スリープ状態かつ同じチャネルを持っているプロセスがいる場合、そのプロセスの状態を実行可能状態にする。
proc.c
static void
wakeup1(void *chan)
{
struct proc *p;
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
if(p->state == SLEEPING && p->chan == chan)
p->state = RUNNABLE;
}
// Wake up all processes sleeping on chan.
void
wakeup(void *chan)
{
acquire(&ptable.lock);
wakeup1(chan);
release(&ptable.lock);
}
5.11. iノード
スケジューラの実行までに使用するiノード周りの操作について書く。
- inode構造体
- inode構造体の作成（iget関数）
- ロック（ilock/iunlock関数）
- 参照カウンタのインクリメント（idup数）
- 参照カウンタのデクリメント（iput関数）
- ファイルデータの取得（readi関数）
- ブロックの割り当て（bmap関数）
- 削除（itrunc関数）
- 更新（iupdate関数）
inode構造体
inodeについては、「xv6 a simple, Unix-like teaching operating system」（リンク1）の6章「File system」を読むとよい。
dinode構造体とinode構造体の2つがある。
dinode構造体
ディスク上のiノードブロックにその情報が格納されてる。
typeフィールドは次の4つの状態を表す。
- 0: 未使用
- 1: ファイル
- 2: ディレクトリ
- 3: デバイスファイル
addrs配列はファイルの存在しているディスク上のブロック番号を持ち、「xv6 a simple, Unix-like teaching operating system」（リンク1）の図6-3「The representation of a file on disk」で分かりやすく図解されている。 要素数は13で、12番目（NDIRECT）までは直接ブロック番号が入っており、13番目はindirect blockのブロック番号が入っている。 ブロックサイズは512バイトで、ブロック番号は4バイトなので、indirect blockは128個のブロックを指すことができる。 つまりinode構造体は全部で140個（128+12）のブロックを指すことができる。 逆に言えば71680バイト（140*512）がファイルの最大サイズとなる。
にあるように、前12エントリがそのままデータブロックを指しており、13エントリ目は128エントリまで保持できる別のテーブルを参照している。
ブロックサイズが512バイトなので、dinode構造体から直接参照できるのは12 * 512 = 6kBまで。
fs.h
#define NDIRECT 12
/* 略 */
struct dinode {
short type; // File type
short major; // Major device number (T_DEV only)
short minor; // Minor device number (T_DEV only)
short nlink; // Number of links to inode in file system
uint size; // Size of file (bytes)
uint addrs[NDIRECT+1]; // Data block addresses
};
inode構造体
後半はdinode構造体のコピーになっている。
validフィールドは既にディスクからdinodeの情報を読み出したか否かを示すフラグ。
file.h
struct inode {
uint dev; // Device number
uint inum; // Inode number
int ref; // Reference count
struct sleeplock lock; // protects everything below here
int valid; // inode has been read from disk?
short type; // copy of disk inode
short major;
short minor;
short nlink;
uint size;
uint addrs[NDIRECT+1];
};
inode構造体はicache構造体に持っておく。
全部で50個持てる。逆に言えば50個以上開けない。
param.h
#define NINODE 50 // maximum number of active i-nodes
fs.c
struct {
struct spinlock lock;
struct inode inode[NINODE];
} icache;
inode構造体の作成（iget関数）
iノードキャッシュからinode構造体を返す。
探しているiノードがキャッシュにある場合は参照カウンタをインクリメントしてそれを返し、無い場合はキャッシュ内の未使用エントリを初期化して返す。
ディスクからのデータ読み出しは行わないので、dinode構造体の持つ内容のコピーは行わない。
キャッシュからはデバイス番号とiノード番号を頼りにエントリを検索する。
fs.c
static struct inode*
iget(uint dev, uint inum)
{
struct inode *ip, *empty;
acquire(&icache.lock);
// Is the inode already cached?
empty = 0;
for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){
if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){
ip->ref++;
release(&icache.lock);
return ip;
}
if(empty == 0 && ip->ref == 0) // Remember empty slot.
empty = ip;
}
// Recycle an inode cache entry.
if(empty == 0)
panic("iget: no inodes");
ip = empty;
ip->dev = dev;
ip->inum = inum;
ip->ref = 1;
ip->valid = 0;
release(&icache.lock);
return ip;
}
ロック（ilock/iunlock関数）
iノードを使用する処理はファイルシステムを扱う処理なのでディスクにアクセスする可能性があり、長時間ロックを取得する可能性が高いためスリープロックを使用する。
ilock関数はinode構造体のロックを取り、dinode構造体のデータをまだ持っていない場合にバッファキャッシュやディスクからそれを読み込む。
dinode構造体のデータはbread関数で取得する。 bread関数はデータをデバイス番号とブロック番号を基にバッファキャッシュから探し、そこに無ければディスクからデータを読み込んでバッファキャッシュに加える。 ブロック番号はIBLOCKマクロを使用して、iノード番号とsuperblock構造体から求める。 superblock構造体は、大域変数sbがiinit関数で定義される。 スーパーブロックは「xv6 a simple, Unix-like teaching operating system」（リンク1）の図6-2における1番目のブロックで、ファイルシステムのサイズやデータブロック数等の情報を持っている。 IBLOCKマクロはinode番号をブロック当たりのiノード数で割り、それにiノード領域の開始ブロック番号を加算することで目的のiノードが含まれるブロック番号を求める。 ブロック当たりのiノード数はIPBとして定義されており、ブロックサイズをdinode構造体のサイズで割ったもの。
buf構造体のdataフィールドにはdinode構造体のデータがiノード番号順に並んでいるため、iノード番号をIPBで割った余り番目からデータを取り出す。
その後dinode構造体の全フィールドをinode構造体にコピーし、最後にバッファキャッシュを始末する。
fs.h
#define IPB (BSIZE / sizeof(struct dinode))
// Block containing inode i
#define IBLOCK(i, sb) ((i) / IPB + sb.inodestart)
fs.c
struct superblock sb;
/* 略 */
void
ilock(struct inode *ip)
{
struct buf *bp;
struct dinode *dip;
if(ip == 0 || ip->ref < 1)
panic("ilock");
acquiresleep(&ip->lock);
if(ip->valid == 0){
bp = bread(ip->dev, IBLOCK(ip->inum, sb));
dip = (struct dinode*)bp->data + ip->inum%IPB;
ip->type = dip->type;
ip->major = dip->major;
ip->minor = dip->minor;
ip->nlink = dip->nlink;
ip->size = dip->size;
memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
brelse(bp);
ip->valid = 1;
if(ip->type == 0)
panic("ilock: no type");
}
}
ロックはiunlock関数で解放する。
fs.c
void
iunlock(struct inode *ip)
{
if(ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1)
panic("iunlock");
releasesleep(&ip->lock);
}
参照カウンタのインクリメント（idup関数）
inode構造体の参照カウンタをインクリメントする。
fs.c
struct inode*
idup(struct inode *ip)
{
acquire(&icache.lock);
ip->ref++;
release(&icache.lock);
return ip;
}
参照カウンタのデクリメント（iput関数）
この関数は引数のinode構造体ipの参照カウンタをデクリメントする。 また、ファイルデータをディスクから取得済みかつ他のファイル（ディレクトリエントリ）がリンクされておらず、誰からも参照されていない場合にiノードを解放する。 ここで言う解放は、addrsをバッファキャッシュごと全て解放しディスクに書き出すことでファイルを削除することを指す。 参照カウンタの値は誰からも参照されていない場合は1。
iunlockput関数はinode構造体のロックを解放し、iput関数を呼び出す。
fs.c
void
iput(struct inode *ip)
{
acquiresleep(&ip->lock);
if(ip->valid && ip->nlink == 0){
acquire(&icache.lock);
int r = ip->ref;
release(&icache.lock);
if(r == 1){
// inode has no links and no other references: truncate and free.
itrunc(ip);
ip->type = 0;
iupdate(ip);
ip->valid = 0;
}
}
releasesleep(&ip->lock);
acquire(&icache.lock);
ip->ref--;
release(&icache.lock);
}
/* 略 */
void
iunlockput(struct inode *ip)
{
iunlock(ip);
iput(ip);
}
ファイルデータの取得（readi関数）
この関数はファイルからデータを最大nバイト分dstに読み込む。
iノードがデバイスファイルの場合とそれ以外（ファイルあるいはディレクトリ）とで処理が分かれる。
デバイスファイルの場合:
読み込みにはデバイス番号を頼りにdevsw配列の該当するread関数を使う。
例えばコンソールならdevsw[1].readなので、consoleinit関数で設定したconsoleread関数が実行される。
ファイルあるいはディレクトリの場合:
ファイルのデータをoffバイト目から読み込み始める。
ファイルサイズよりも読み込みサイズ（off+n）大きい場合は調整する。
読み込むデータ（nバイト）がブロックを跨いでいる可能性があるため、ループで読み込む。
mがループ毎にdstにコピーするバイト数を示し、totにはコピーした総バイト数を持つ。
読み込みにはbread関数を使う。
この関数にはデバイス番号とブロック番号を渡す必要がある。
bmap関数では第一引数のinode構造体のaddrsフィールドから、第二引数で指定されたバイト目があるブロック番号を得ることができる。
基本的にはoffからそのブロックの終わりまでずつコピーしていく。
例えばoffが600の場合、1ブロック512バイトなので、offは2ブロック目の88バイト目から始まる。
なので 512-88=424 バイトずつコピーしていく。
そして読み込みバイト数nがコピーしていく単位で割り切れない場合は、最後のループでnからコピー済みバイト数totの差だけコピーする。
他の例として、nが1000の場合、3回目のループで残りコピーバイト数が 1000-424*2=152 なので、152バイトだけコピーする。
変数mにはこの動きをするために、minマクロを使用して残りコピーバイト数（n-tot）と基本的なコピー単位のどちらか小さい方を代入する。
コピーバイト数mが決まると、memmove関数でdstにブロックのデータ（bs->data）のオフセットの位置からその分だけコピーする。
バッファキャッシュbpは読み込み後不要となるのでループ毎に解放する。
1ブロック分ずつコピーするわけではないので、次のループでも同じブロックをバッファキャッシュに読み込む可能性がある。
しかしここで解放しなければ、バッファキャッシュのサイズが30なのでコピー対象のデータが30ブロック以上の時にキャッシュが足りなくなりpanicしてしまう。
fs.c
#define min(a, b) ((a) < (b) ? (a) : (b))
/* 略 */
int
readi(struct inode *ip, char *dst, uint off, uint n)
{
uint tot, m;
struct buf *bp;
if(ip->type == T_DEV){
if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read)
return -1;
return devsw[ip->major].read(ip, dst, n);
}
if(off > ip->size || off + n < off)
return -1;
if(off + n > ip->size)
n = ip->size - off;
for(tot=0; tot<n; tot+=m, off+=m, dst+=m){
bp = bread(ip->dev, bmap(ip, off/BSIZE));
m = min(n - tot, BSIZE - off%BSIZE);
memmove(dst, bp->data + off%BSIZE, m);
brelse(bp);
}
return n;
}
ブロックの割り当て（bmap関数）
この関数はaddrsフィールドのbn番目のブロック番号を返す。 もしもbn番目が0でブロックが割り当てられていない場合、ディスクのdata領域から1ブロック割り当てる。
2つのif文に分かれており、前半はbnがaddrsの12番目までの処理を行い、後半はindirect block（13番目）の処理を行う。
12番目まで:
addrsフィールドのbn番目からブロック番号を取り出す。
もしもbn番目が0でブロックが割り当てられていない場合、balloc関数でファイルシステムのdata領域から1ブロック割り当て、そのブロック番号をbn番目に入れる。
indirect block:
bnをそのままindirect block内でのインデックスとするため、12減算する。
NINDIRECTはindirect blockのエントリ数。
indirect blockのブロック番号を取り出し、0の場合はballoc関数で1ブロック割り当てる。
変数bpにbread関数でindirect blockを読み出し、そこからさらにbn番目のブロック番号を取り出す。
bn番目が0の場合も同様にブロックを割り当てる。
このとき、新たにブロックの割り当てを行うとindirect blockの内容を更新することになるため、log_write関数で変更をディスクに反映する。
log_write関数ではバッファキャッシュのB_DIRTYを立て、後々呼び出されるwrite_log関数でディスクに書き込みを行う。
bpをbrelse関数で解放し、呼び出し元にブロック番号addrを返して終了。
fs.h
#define NDIRECT 12
#define NINDIRECT (BSIZE / sizeof(uint))
fs.c
static uint
bmap(struct inode *ip, uint bn)
{
uint addr, *a;
struct buf *bp;
if(bn < NDIRECT){
if((addr = ip->addrs[bn]) == 0)
ip->addrs[bn] = addr = balloc(ip->dev);
return addr;
}
bn -= NDIRECT;
if(bn < NINDIRECT){
// Load indirect block, allocating if necessary.
if((addr = ip->addrs[NDIRECT]) == 0)
ip->addrs[NDIRECT] = addr = balloc(ip->dev);
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
if((addr = a[bn]) == 0){
a[bn] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
return addr;
}
panic("bmap: out of range");
}
削除（itrunc関数）
この関数はiノードのデータを解放する。 ここで言う解放は、addrsをバッファキャッシュごと全て解放しディスクに書き出すことでファイルを削除することを指す。
ファイルシステム上のブロックを未使用にマークする。
動作はbmap関数とほぼ同様で、addrsフィールドを走査してbfree関数でブロックを解放しつつ0を代入していく。
その後ファイルサイズも0とし、iupdate関数を呼び出してdinode構造体に変更を反映する。
fs.c
static void
itrunc(struct inode *ip)
{
int i, j;
struct buf *bp;
uint *a;
for(i = 0; i < NDIRECT; i++){
if(ip->addrs[i]){
bfree(ip->dev, ip->addrs[i]);
ip->addrs[i] = 0;
}
}
if(ip->addrs[NDIRECT]){
bp = bread(ip->dev, ip->addrs[NDIRECT]);
a = (uint*)bp->data;
for(j = 0; j < NINDIRECT; j++){
if(a[j])
bfree(ip->dev, a[j]);
}
brelse(bp);
bfree(ip->dev, ip->addrs[NDIRECT]);
ip->addrs[NDIRECT] = 0;
}
ip->size = 0;
iupdate(ip);
}
更新（iupdate関数）
この関数はinode構造体の内容をdinode構造体にコピーし、その変更をディスクに反映する。
ディスク上にあるdinode構造体はbread関数で取得する。
その際のブロック番号はIBLOCKマクロで算出する。
log_write関数で変更をディスクに反映する。
この関数ではバッファキャッシュのB_DIRTYを立て、後々呼び出されるwrite_log関数でディスクに書き込みを行う。
fs.c
void
iupdate(struct inode *ip)
{
struct buf *bp;
struct dinode *dip;
bp = bread(ip->dev, IBLOCK(ip->inum, sb));
dip = (struct dinode*)bp->data + ip->inum%IPB;
dip->type = ip->type;
dip->major = ip->major;
dip->minor = ip->minor;
dip->nlink = ip->nlink;
dip->size = ip->size;
memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
log_write(bp);
brelse(bp);
}
5.12. バッファキャッシュとディスクの読み書き
スケジューラの実行までに使用するバッファキャッシュ周りの操作について書く。
- buf構造体
- buf構造体の取得（bread関数）
- buf構造体の書き込み（bwrite関数）
- ディスクの読み書き（iderw関数）
- データブロックの割り当て（balloc関数）
- データブロックの解放（bfree関数）
buf構造体
バッファキャッシュについては、「xv6 a simple, Unix-like teaching operating system」（リンク1）の6章「File system」を読むとよい。
buf構造体はディスクから読み込んだ1ブロック分のデータをキャッシュしておくための構造体。
30個分を大域変数bcacheのbufフィールドに持つ。
bcache構造体はbinit関数で初期化される。
バッファキャッシュは循環リストになっており、各buf構造体のnextフィールドとprevフィールドでリンクする。
アクセスする際にはbcache構造体のheadフィールドを基点として、nextかprevでどちらかに回って走査する。
直近使用されたバッファはnext側の先頭に移動されるため、欲しいデータが既にバッファされているか確認するときはnext側に回る。
逆にデータをバッファする際は、未使用のバッファを探すためにprev側から回る。
buf構造体のflagsフィールドは0x0が未使用、B_VALID（0x2）が使用中、B_DIRTY（0x4）が変更済みを示す。
dataフィールドに1ブロック分のデータを持つ。
bio.c
struct {
struct spinlock lock;
struct buf buf[NBUF];
// Linked list of all buffers, through prev/next.
// head.next is most recently used.
struct buf head;
} bcache;
buf.h
struct buf {
int flags;
uint dev;
uint blockno;
struct sleeplock lock;
uint refcnt;
struct buf *prev; // LRU cache list
struct buf *next;
struct buf *qnext; // disk queue
uchar data[BSIZE];
};
#define B_VALID 0x2 // buffer has been read from disk
#define B_DIRTY 0x4 // buffer needs to be written to disk
buf構造体の取得（bread関数）
bread関数を使用して、欲しいブロックのbuf構造体を取得する。
ブロックがバッファキャッシュに存在しない場合は、空のエントリにディスクからブロックを読み込む。
バッファキャッシュからの取得はbget関数で行い、ディスクからの読み込みはiderw関数で行う。
bio.c
struct buf*
bread(uint dev, uint blockno)
{
struct buf *b;
b = bget(dev, blockno);
if((b->flags & B_VALID) == 0) {
iderw(b);
}
return b;
}
bget関数はデバイス番号とブロック番号を用いてバッファキャッシュからbuf構造体を探し、無ければ未使用のバッファを返す。
最近キャッシュされた順に探すため、headからnext方向に走査する。
キャッシュを見つけた場合はbuf構造体の参照カウンタをインクリメントし、スリープロックを取る。
見つからなかった場合は未使用のbuf構造体を探すため、headからprev方向に走査する。
もしもキャッシュが30個全て使用されていた場合はpanicする。
bio.c
static struct buf*
bget(uint dev, uint blockno)
{
struct buf *b;
acquire(&bcache.lock);
// Is the block already cached?
for(b = bcache.head.next; b != &bcache.head; b = b->next){
if(b->dev == dev && b->blockno == blockno){
b->refcnt++;
release(&bcache.lock);
acquiresleep(&b->lock);
return b;
}
}
// Not cached; recycle an unused buffer.
// Even if refcnt==0, B_DIRTY indicates a buffer is in use
// because log.c has modified it but not yet committed it.
for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
if(b->refcnt == 0 && (b->flags & B_DIRTY) == 0) {
b->dev = dev;
b->blockno = blockno;
b->flags = 0;
b->refcnt = 1;
release(&bcache.lock);
acquiresleep(&b->lock);
return b;
}
}
panic("bget: no buffers");
}
buf構造体の書き込み（bwrite関数）
iderw関数でディスクへbuf構造体を書き出す。
void
bwrite(struct buf *b)
{
if(!holdingsleep(&b->lock))
panic("bwrite");
b->flags |= B_DIRTY;
iderw(b);
}
ディスクの読み書き（iderw関数）
buf構造体をidequeueにエンキューし、それがキューの先頭である場合にディスクの読み込み或いは書き込み処理を行う。
buf構造体のデバイス番号が0でなかった場合、かつhavedisk1フラグが0だった場合はpanicする。 ディスクはカーネルイメージのディスク0と、ファイルシステムイメージのディスク1の2つのみであるため、デバイス番号は0か1になる。 また、デバイス番号が1ならば、ファイルシステムイメージの存在が確認されている必要があり、havedisk1フラグでそれを確認できる。 このフラグはideinit関数でディスクをチェックする際に設定される。
ideへの要求となるbuf構造体はide.cで定義されているidequeueにエンキューされ、idestart関数でそれをひとつずつideに処理してもらう。 iderw関数では、もしも引数のbuf構造体がidequeueの先頭だった場合、idestart関数でideに処理要求を出す。 ideの読み書きが終わるまではスリープ状態となり、割り込みを待つ。 ideの処理が終わると、割り込みによりideintr関数が実行され、その中でidequeueからデキューされ、順次idestart関数が呼ばれる。
ide.c
static struct buf *idequeue;
/* 略 */
void
iderw(struct buf *b)
{
struct buf **pp;
if(!holdingsleep(&b->lock))
panic("iderw: buf not locked");
if((b->flags & (B_VALID|B_DIRTY)) == B_VALID)
panic("iderw: nothing to do");
if(b->dev != 0 && !havedisk1)
panic("iderw: ide disk 1 not present");
acquire(&idelock); //DOC:acquire-lock
// Append b to idequeue.
b->qnext = 0;
for(pp=&idequeue; *pp; pp=&(*pp)->qnext) //DOC:insert-queue
;
*pp = b;
// Start disk if necessary.
if(idequeue == b)
idestart(b);
// Wait for request to finish.
while((b->flags & (B_VALID|B_DIRTY)) != B_VALID){
sleep(b, &idelock);
}
release(&idelock);
}
idestart関数はideにbuf構造体に応じたリクエストを出す。
ideコントローラのレジスタに書き込みを行うことでそれを行う。
ide.cの1行目に、これはPIOベースのシンプルなIDEドライバコードであるとのコメントがある。
アクセスしているレジスタとデータの意味は「OSDev ATA PIO Mode」（リンク23）に記載されている。 関数内に出てくる0x1f7はリンクの「Addressing Modes」の「Registers」によると、読み込み時はステータスレジスタ、書き込み時はコマンドレジスタとなり、コマンドは「OSDev ATA Command Matrix」（リンク24）に一覧としてまとまっている。
読み書きを行うブロックの指定にはLBA方式を使用する。 LBAについては「OSDev LBA」（リンク25）に記載されている。 フロッピーディスクなどの場合はCHSという方法でセクタにアクセスする。
変数sector_per_blockからwrite_cmdまでの値は以下。
- sector_per_block: いずれも512バイトなので1
- sector: ブロックがある（はじまる）セクタ番号（LBA）。 ブロックサイズとセクタサイズが等しいので、ブロックサイズがそのまま求める番号となる。
- read_cmd: 読み込みに使用するコマンド。 コマンドは「OSDev ATA Command Matrix」（リンク24）に載っている。 セクタサイズとブロックサイズが異なる場合、複数のセクタを読む0xc4（IDE_CMD_RDMUL）とし、等しい場合はそのセクタだけを読む0x20（IDE_CMD_READ）とする。
- write_cmd: 書き込みに使用するコマンド。 複数セクタを書く場合は0xc5（IDE_CMD_WRMUL）、ひとつの場合は0x30（IDE_CMD_WRITE）とする。
ideにコマンドをリクエストする前に、ブロックサイズがセクタサイズの7倍より大きくないことを確認するが、なぜこのチェックが必要なのかはわからない。
idewait関数でドライブがビジーでもエラーでもなくなるまで待つ。
読み書きの設定は以下。
デバイスコントロールレジスタ（0x3f6）に0を書き込み、1bit目（nIEN）を0にすることでドライブの割り込みを有効化する。
セクタカウントレジスタ（0x1f2）に、sector_per_blockを設定する。ここでは1。
LBAloレジスタ（0x1f3）に、LBAの1バイト目を設定する。
レジスタが8bitなので、LBAは4つに分けて設定する。
LBAmidレジスタ（0x1f4）に、LBAの2バイト目を設定する。
LBAhiレジスタ（0x1f5）に、LBAの3バイト目を設定する。
ドライブ/ヘッドレジスタ（0x1f6）の各bitを設定する。
「OSDev ATA PIO Mode」（リンク23）の「Addressing Modes」の「Drive / Head Register (I/O base + 6)」を見ると各bitの役割が分かる。
5bitと7bitは常に1、6bitはLBAを使用する場合1とするため、ここでは0xe0をセット。
4bitはドライブ番号なのでbuf構造体のdevフィールドの1bitをセット。
0～3bitにはLBAの24～27bitをセットする。
ideにコマンドを発行する。 buf構造体のflagsフィールドの変更済みフラグ（B_DIRTY）が立っている場合は書き込み、そうでなければ読み込みを行う。
書き込みの場合:
コマンドレジスタ（0x1f7）に書き込みコマンド（write_cmd）を書き込み、データレジスタ（0x1f0）にoutsl関数でbuf構造体のdataフィールドの内容を128回に分けて4バイトずつ書き込む。
読み込みの場合:
コマンドレジスタ（0x1f0）に読み込みコマンド（read_cmd）を書き込む。
書き込み終了あるいは、読み込み準備の完了により、ideコントローラから割り込みが入り、最終的にはideintr関数が呼び出される。
ide.c
static void
idestart(struct buf *b)
{
if(b == 0)
panic("idestart");
if(b->blockno >= FSSIZE)
panic("incorrect blockno");
int sector_per_block = BSIZE/SECTOR_SIZE;
int sector = b->blockno * sector_per_block;
int read_cmd = (sector_per_block == 1) ? IDE_CMD_READ : IDE_CMD_RDMUL;
int write_cmd = (sector_per_block == 1) ? IDE_CMD_WRITE : IDE_CMD_WRMUL;
if (sector_per_block > 7) panic("idestart");
idewait(0);
outb(0x3f6, 0); // generate interrupt
outb(0x1f2, sector_per_block); // number of sectors
outb(0x1f3, sector & 0xff);
outb(0x1f4, (sector >> 8) & 0xff);
outb(0x1f5, (sector >> 16) & 0xff);
outb(0x1f6, 0xe0 | ((b->dev&1)<<4) | ((sector>>24)&0x0f));
if(b->flags & B_DIRTY){
outb(0x1f7, write_cmd);
outsl(0x1f0, b->data, BSIZE/4);
} else {
outb(0x1f7, read_cmd);
}
}
idewait関数はドライブがビジーでもエラーでもなくなるまでwhileループで待つ。
引数checkerrに0を渡すとエラーチェックはせず、1を渡すとドライブのエラーをチェックし、エラーの場合に-1を返してくれる。
ループの終了条件はステータスレジスタ（0x1f7）を読み取り、7bitのビジービット（IDE_BSY）が0、かつ6bitのレディビット（IDE_DRDY）が1になること。
エラーチェックではステータスレジスタの5bitドライブ障害エラービット（IDE_DF）あるいは0bitエラービット（IDE_ERR）を確認し、いずれかが1の場合に-1を返す。
ide.c
#define IDE_BSY 0x80
#define IDE_DRDY 0x40
#define IDE_DF 0x20
#define IDE_ERR 0x01
/* 略 */
static int
idewait(int checkerr)
{
int r;
while(((r = inb(0x1f7)) & (IDE_BSY|IDE_DRDY)) != IDE_DRDY)
;
if(checkerr && (r & (IDE_DF|IDE_ERR)) != 0)
return -1;
return 0;
}
まだ割り込みベクタの初期化を読むのは先になるが、動きとしては、このあとディスクの準備ができるとideコントローラからirq14番で割り込みが入り、IOAPICのリダイレクトテーブルによって割り込みベクタ 46(32 + 14)番がtrap関数にわたされ、ideintr関数により読み込みが行われる。
ideintr関数はidequeueの先頭のbuf構造体のflagsフィールドに応じてディスクから読み込みを行う。
もしもbuf構造体のflagsフィールドの変更済みフラグ（B_DIRTY）が0で、かつidewait関数でドライブの準備ができている場合、ディスクから読み出しを行う。 読み出しはinsl関数でコントロールレジスタ（0x1f0）からbuf構造体のdataフィールドにブロックサイズ分読み込む。 次に、buf構造体のflagsフィールドの読み込み済みフラグ（B_VALID）を1にし、変更済みフラグ（B_DIRTY）をビット反転して論理積を取って0にする。
読み込みを待っているプロセスを起床し、idequeueにエントリがまだ残っている場合は次のエントリを引数としてidestart関数を呼び出す。
ide.c
void
ideintr(void)
{
struct buf *b;
// First queued buffer is the active request.
acquire(&idelock);
if((b = idequeue) == 0){
release(&idelock);
return;
}
idequeue = b->qnext;
// Read data if needed.
if(!(b->flags & B_DIRTY) && idewait(1) >= 0)
insl(0x1f0, b->data, BSIZE/4);
// Wake process waiting for this buf.
b->flags |= B_VALID;
b->flags &= ~B_DIRTY;
wakeup(b);
// Start disk on next buf in queue.
if(idequeue != 0)
idestart(idequeue);
release(&idelock);
}
データブロックの割り当て（balloc関数）
balloc関数はファイルシステムのdata領域で空いているブロックを探してそのブロック番号を返す。 ファイルシステムのbitmap領域に当該ブロックを使用済みとしてマークする。
bitmap領域に関しては、教科書「xv6 a simple, Unix-like teaching operating system」（リンク1）の6章「File system」の「Code: Block allocator」で説明されている。
bitmap領域の1bitがファイルシステム上の1ブロックを表しており、使用済みか否かを管理している。
bitmap領域が何番目のブロックから始まるのかといったファイルシステムの情報は、superblockにある。
これは後々initプロセス実行時に呼び出されるforkret関数の中でiinit関数を呼び出し、superblock構造体の大域変数sbに読み込む。
この関数は二重のforループになっており、外側でbitmap領域のブロックを、内側でそのブロックのbitを走査する。
外側ループ:
変数bはbitmap領域のbitの番号を表すと同時に、ファイルシステムのブロック番号でもある。
BPBマクロはブロックあたりのbitmapのbit数を表す（512*8）ので、bはブロックに含まれるbit数（4096）ずつ増加することになる。
終了条件はbがファイルシステムの総ブロックサイズsb.size（1000ブロック）を越えるときなので、fs.imgの場合はこのループは1度しか回らない。
次にbitmap領域のブロックをbuf構造体のポインタbpに取り出す。
ブロックの取り出しにはbread関数を使用し、ブロック番号の指定はBBLOCKマクロで行う。
BBLOCKマクロはbitmap領域のbビット目が含まれるブロック番号を返してくれる。
これはbをBPBで割ってブロック番号を割り出し、bitmap領域の開始ブロックsb.bmapstartに加算して求めている。
内側ループ:
bitmap領域の現在のブロックのbitを1つずつ走査し、0になっているbit（未使用のブロック番号）を探す。
変数biをブロックの総bit数（512*8）までインクリメントしていく。
ブロックの全てのbitを走査すると言ってもbuf構造体bpのdataフィールドからアクセスできるのは1バイトずつなので、変数mを8bit分のフラグとして、0bitから順に7bitまで1を立てていってその論理積でbitを調べる。
なので、mにはbiを8で割った余りだけ左シフトした1を代入していく。
bpのdataフィールドの各bitをmで論理積してブロックの使用状況を調べる。
もしもbitが0で、ブロックb+biが使用されていないとき、今度はmの論理和でbpのdataフィールドのbitを立てて使用済みにマークする。
bpが更新されたので、log_write関数で変更をディスクに反映し、brelse関数でbpを解放する。
bzero関数で使用済みにマークしたブロック（b+bi番目）を0埋めし、呼び出し元にブロック番号を返す。
bzero関数は引数devのデバイスの引数bnoのブロック番号で示されるブロックを0埋めして、log_write関数でディスクに書き出す。
もしもbitmap領域のbitが全て1で、未使用のブロックが存在しないときは、panicする。
fs.h
#define BPB (BSIZE*8)
/* 略 */
#define BBLOCK(b, sb) (b/BPB + sb.bmapstart)
fs.c
static void
bzero(int dev, int bno)
{
struct buf *bp;
bp = bread(dev, bno);
memset(bp->data, 0, BSIZE);
log_write(bp);
brelse(bp);
}
/* 略 */
static uint
balloc(uint dev)
{
int b, bi, m;
struct buf *bp;
bp = 0;
for(b = 0; b < sb.size; b += BPB){
bp = bread(dev, BBLOCK(b, sb));
for(bi = 0; bi < BPB && b + bi < sb.size; bi++){
m = 1 << (bi % 8);
if((bp->data[bi/8] & m) == 0){ // Is block free?
bp->data[bi/8] |= m; // Mark block in use.
log_write(bp);
brelse(bp);
bzero(dev, b + bi);
return b + bi;
}
}
brelse(bp);
}
panic("balloc: out of blocks");
}
データブロックの解放（bfree関数）
この関数はデバイスdevのb番目のブロックを解放する。
balloc関数と同じ要領でファイルシステムのbitmap領域のb番目のbitを0にする。
log_write関数でディスクに変更を反映し、brelse関数でバッファキャッシュを解放する。
fs.c
static void
bfree(int dev, uint b)
{
struct buf *bp;
int bi, m;
bp = bread(dev, BBLOCK(b, sb));
bi = b % BPB;
m = 1 << (bi % 8);
if((bp->data[bi/8] & m) == 0)
panic("freeing free block");
bp->data[bi/8] &= ~m;
log_write(bp);
brelse(bp);
}
5.13. uartinit関数
この関数はシリアルポートがある場合はそれを初期化し、シリアルポートを通して画面に「xv6...」と表示する。
シリアルポートへのアクセスは「XT, AT and PS/2 I/O port addresses」（リンク11）によると、0x3f8～0x3ffで行える。
個々のレジスタの役割や設定値に関しては「Serial Programming/8250 UART Programming」（リンク28）に詳しく記載がある。
UARTは12のレジスタに8つのポートからアクセスする。
各レジスタへのアクセス方法はリンク28の表「UART Registers」にまとまっている。
ポートへの読み書きとDivisor Latch Access Bit（DLAB）の状態によって切り替わる。
uart.cではシリアルポートの有無を示すフラグとして、int型の静的変数uartが定義されている。 この値が1のときシリアルポートが有る。 また、uart.cでは定数COM1が値0x3f8で定義されている。
まずUARTの設定は次の通り。
- FIFO: FIFOコントロールレジスタ（+2）に0を設定し、FIFOを無効化する。 リンク28の「FIFO Control Register」を読むと、uartの入出力はFIFOの形でバッファできると書いてあるが、xv6では使用しない。
- DLAB: ラインコントロールレジスタ（+3）に0x80を設定し、DLABを1にする。
- ボーレート: Divisor Latch Low Byteレジスタ（+0, DLABは1）に12を設定し、ボーレートを9600に設定する。 UARTチップは一般的に115.2kHzで動作するクロックを持っており、ここではボーレート9600で送信したいので12を設定する。 各ボーレートと設定すべき値に関してはリンク28の表「Divisor Latch Byte Values (common baud rates)」にまとまっている。 表によるとDivisor Latch Hight Byteレジスタ（+1）には0を設定しなければならないため、そのようにする。
- ワードサイズ: ラインコントロールレジスタ（+3）に0x03を設定し、DLABを0にするとともに、ワードサイズを8bitに設定する。 ワードサイズの設定はラインコントロールレジスタの0bitと1bitの組み合わせにより、5bitから8bitまで設定できる。
- フロー制御: モデムコントロールレジスタ（+4）に0を設定する。 このレジスタにより、ソフトウェアでハードウェアのフロー制御を行えるが、使用しないので0で初期化する。
シリアルポートの有無を確認する。
有無というより、UARTを使用してシリアルデータ通信が可能か否かを確認している。
ラインステータスレジスタ（+5）の値が0xffと等しくない場合、シリアルポートが使用可能であることを示す。
スレジスタの各bitの役割についてはリンク28の「Line Status Register」に詳しく載っている。
特段0xffの場合に使用できないというようなことはないようだが、全てのbitが立っている状況が普通ではないことは分かる。
特にbit2（Parity Error）やbit3（Framing Error）が1になっていては通信はできない。
シリアルポートが使用できる場合、割り込みの設定を行う。
割り込み識別レジスタ（+2）を読み、以前の割り込みに関する情報をクリアする。
レシーバーバッファレジスタ（+0, DLABは0）を読み、バッファ内のデータをクリアする。
ioapicenable関数でシリアルポート（COM1）からの割り込みの設定と有効化をする。
IOAPICのリダイレクトテーブルにIRQ4番からの割り込みをIRQ36番としてBSP（cpu0）のLAPICにリダイレクトするよう設定する。
最後に「xv6...」という文字列をuartputc関数を使用して1文字ずつ画面に表示する。
uart.c
#define COM1 0x3f8
static int uart; // is there a uart?
void
uartinit(void)
{
char *p;
// Turn off the FIFO
outb(COM1+2, 0);
// 9600 baud, 8 data bits, 1 stop bit, parity off.
outb(COM1+3, 0x80); // Unlock divisor
outb(COM1+0, 115200/9600);
outb(COM1+1, 0);
outb(COM1+3, 0x03); // Lock divisor, 8 data bits.
outb(COM1+4, 0);
outb(COM1+1, 0x01); // Enable receive interrupts.
// If status is 0xFF, no serial port.
if(inb(COM1+5) == 0xFF)
return;
uart = 1;
// Acknowledge pre-existing interrupt conditions;
// enable interrupts.
inb(COM1+2);
inb(COM1+0);
ioapicenable(IRQ_COM1, 0);
// Announce that we're here.
for(p="xv6...\n"; *p; p++)
uartputc(*p);
}
traps.h
#define IRQ_COM1 4
uartgetc関数
UARTのラインステータスレジスタ（+5）のData Ready（0bit）を見て、データの準備ができていることを確認する。
レシーババッファレジスタ（+0, DLABは0）から入力されたデータを呼び出し元に返す。
シリアルポートではasciiコードがやり取りされるので、特に変換処理等はない。
uart.c
#define COM1 0x3f8
/* 略 */
static int
uartgetc(void)
{
if(!uart)
return -1;
if(!(inb(COM1+5) & 0x01))
return -1;
return inb(COM1+0);
}
uartputc関数
uartputc関数は、シリアルポートに文字を書き込む。
forループでUARTのラインステータスレジスタ（+5）のEmpty Transmitter Holding Register（5bit）が0になるまで、最大128回ループする。
5bitは1の場合は送信中、0の場合は送信可能。
microdelay関数はlapic.cに定義されているが実体は何もしない。
コメントに、実際のハードウェアではマイクロ秒単位のスピンロックを動的に行うと書いてある。
Transmitter Holding Buffer（+0, DLABは0）に引数の文字を書き込む。
uart.c
void
uartputc(int c)
{
int i;
if(!uart)
return;
for(i = 0; i < 128 && !(inb(COM1+5) & 0x20); i++)
microdelay(10);
outb(COM1+0, c);
}
lapic.c
// Spin for a given number of microseconds.
// On real hardware would want to tune this dynamically.
void
microdelay(int us)
{
}
5.14. pinit関数
この関数はプロセステーブルのロックを初期化する。
コメントの通り。
param.h
#define NPROC 64 // maximum number of processes
proc.c
struct {
struct spinlock lock;
struct proc proc[NPROC];
} ptable;
/* 略 */
void
pinit(void)
{
initlock(&ptable.lock, "ptable");
}
proc構造体
プロセスを表す構造体。 コメントの通り。
types.h
typedef uint pde_t;
param.h
#define NOFILE 16 // open files per process
proc.h
enum procstate { UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };
// Per-process state
struct proc {
uint sz; // Size of process memory (bytes)
pde_t* pgdir; // Page table
char *kstack; // Bottom of kernel stack for this process
enum procstate state; // Process state
int pid; // Process ID
struct proc *parent; // Parent process
struct trapframe *tf; // Trap frame for current syscall
struct context *context; // swtch() here to run process
void *chan; // If non-zero, sleeping on chan
int killed; // If non-zero, have been killed
struct file *ofile[NOFILE]; // Open files
struct inode *cwd; // Current directory
char name[16]; // Process name (debugging)
};
5.15. tvinit関数
大域変数idtに256個のゲートディスクリプタを作成する。
IDT（Interrupt Descriptor Table）を作成する。
IDTについては「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）のVol.3 Chapter6.10「Interrupt Descriptor Table (IDT)」で説明されている。
ここでは、IDTはgatedesc構造体の配列になっており、大域変数idtで宣言されている。
Intel SDMによると256個の割り込みベクタを持てるため、idtの要素数も256。
IDTに格納される各ゲートディスクリプタの構造はIntel SDMの図6-2「IDT Gate Descriptors」に記載されており、ここで使用するのはInterrupt GateとTrap Gate。 割り込みにはInterrupt Gateを使用し、システムコールにはTrap Gateを使用する。
gatedesc構造体はmmu.hで定義されている。
- off_15_0: 割り込みベクタのアドレスの下半分を設定する。
- cs: GDT上のエントリのインデックスを設定する。 セグメントディスクリプタは8バイトなので8の倍数。
- args: 予約済みなので0埋め。
- rsv1: 全て0。
- type: Interrupt Gateの場合は0b1110（0xE）、Trap Gateの場合は0b1111（0xF）を設定する。 Intel SDMの図で確認すると3bitがDになり、ゲートディスクリプタのサイズが32bitの場合1、16bitの場合0になる。 なのでここでは1で固定。
- s: 12bitに当たるので0固定。
- dpl: ディスクリプタ特権レベル（Descriptor Privilege Level）なので、Interrupt Gateの場合0、Trap Gateの場合3を設定する。 特権レベルについてはVol.3 Chapter5.5「PRIVILEGE LEVELS」で説明されており、カーネルが0、ユーザが3。
- p: セグメント存在フラグ。今回はセグメントがメモリ上に存在するので1を設定する。
- off_31_16: 割り込みベクタのアドレスの上半分を設定する。
SETGATEマクロで各ゲートディスクリプタを作成する。
trap.c
struct gatedesc idt[256];
mmu.h
struct gatedesc {
uint off_15_0 : 16; // low 16 bits of offset in segment
uint cs : 16; // code segment selector
uint args : 5; // # args, 0 for interrupt/trap gates
uint rsv1 : 3; // reserved(should be zero I guess)
uint type : 4; // type(STS_{IG32,TG32})
uint s : 1; // must be 0 (system)
uint dpl : 2; // descriptor(meaning new) privilege level
uint p : 1; // Present
uint off_31_16 : 16; // high bits of offset in segment
};
/* 略 */
#define SETGATE(gate, istrap, sel, off, d) \
{ \
(gate).off_15_0 = (uint)(off) & 0xffff; \
(gate).cs = (sel); \
(gate).args = 0; \
(gate).rsv1 = 0; \
(gate).type = (istrap) ? STS_TG32 : STS_IG32; \
(gate).s = 0; \
(gate).dpl = (d); \
(gate).p = 1; \
(gate).off_31_16 = (uint)(off) >> 16; \
}
割り込みベクタテーブルはvectors.Sに定義されている256個の関数のアドレスが、同ファイル内のvectorsラベル以下に列挙されている。
関数はvector0からvector255まであり、スタックに0とIRQ番号をプッシュし、alltraps関数に跳んでいる。
alltraps関数はtrapasm.Sで定義されている。
vectors.Sはmake時にvectors.plを実行することで作られる。
trap.cで、extern宣言として符号なし整数型の配列vectorsで割り込みベクタテーブルを参照している。
vectors.S
.globl alltraps
.globl vector0
vector0:
pushl $0
pushl $0
jmp alltraps
.globl vector1
# 略
.globl vector255
vector255:
pushl $0
pushl $255
jmp alltraps
# vector table
.data
.globl vectors
vectors:
.long vector0
# 略
.long vector255
trap.c
extern uint vectors[]; // in vectors.S: array of 256 entry pointers
tvinit関数では、まずforループで配列idtに割り込みベクタテーブルの全エントリ分（256個）の割り込みゲートディスクリプタを作成する。
DPLは0。
次に、システムコールにはIRQ64番を使うので、idtの64番目を上書きする形でトラップゲートディスクリプタをDPL3で作成する。
最後にtickslockのロックを初期化する。
trap.c
void
tvinit(void)
{
int i;
for(i = 0; i < 256; i++)
SETGATE(idt[i], 0, SEG_KCODE<<3, vectors[i], 0);
SETGATE(idt[T_SYSCALL], 1, SEG_KCODE<<3, vectors[T_SYSCALL], DPL_USER);
initlock(&tickslock, "time");
}
tick
tickは一般的に一定周期で時間を刻むことを言い、ここでも同様に使われる。
符号なしint型の大域変数ticksと、そのロックに使用するtickslockが定義されている。
使用箇所をgrepすると、タイマー割り込みに関する部分とシステムコールsys_sleep内でのみ使用されており、インクリメントだけで代入は行われない。
sysproc.cに定義されているsys_sleep関数でその使われ方を見ることができる。
この関数はticksが引数n分だけインクリメントされるまで、現在のプロセスをスリープ状態にする。
はじめに、argint関数を使用して自身に与えられたint型の引数を変数nに取り出す。
そして現在のticksの値をローカル変数ticks0に保存しておく。
whileループで ticks - ticks0 < n が偽になるまでプロセスをスリープする。
起床するためのチャネルにはticksのアドレスを用いる。
ticksはcpu0からのタイマー割り込みによりインクリメントされるので、その度に起床されることになる。
trap.c
struct spinlock tickslock;
uint ticks;
sysproc.c
int
sys_sleep(void)
{
int n;
uint ticks0;
if(argint(0, &n) < 0)
return -1;
acquire(&tickslock);
ticks0 = ticks;
while(ticks - ticks0 < n){
if(myproc()->killed){
release(&tickslock);
return -1;
}
sleep(&ticks, &tickslock);
}
release(&tickslock);
return 0;
}
ticksがインクリメントされる部分だけ合わせて見ることにする。
割り込みやトラップが生じるとIDTや割り込みベクタテーブル等を経由してtrapasm.Sのalltraps関数からtrap.cのtrap関数が呼び出されれる。
trap関数はIRQ番号によって分岐する。
ticksはタイマー割り込みかつcpu0からの割り込みである場合にのみインクリメントされる。
その後ticksのアドレスをチャネルとしてスリープ状態のプロセスを起床させる。
LAPICタイマの設定はlapicinitで見た。
trap.c
switch(tf->trapno){
case T_IRQ0 + IRQ_TIMER:
if(cpuid() == 0){
acquire(&tickslock);
ticks++;
wakeup(&ticks);
release(&tickslock);
}
lapiceoi();
break;
5.16. binit関数
この関数でバッファキャッシュを初期化を行う。
バッファキャッシュについては5.12. バッファキャッシュとディスクの読み書きで見た。
キャッシュを走査するためのbcache内のheadフィールドの前（prev）と後（next）のアドレスをheadフィールドの値で初期化する。
そしてforループでバッファキャッシュの全エントリ（30個）を初期化し、buf配列が循環するようにリンクさせる。
ループが終わると、headのnextはbuf配列の29番目を指すようになり、prevは0番目を指すようになる。
29番目のprevと0番目のnextはheadを指す。
headからnextを辿ると、buf配列の29, 28, 27 ... 0, headとなる。
headからprevを辿ると、buf配列の0, 1, 2 ... 29, headとなる。
bio.c
void
binit(void)
{
struct buf *b;
initlock(&bcache.lock, "bcache");
//PAGEBREAK!
// Create linked list of buffers
bcache.head.prev = &bcache.head;
bcache.head.next = &bcache.head;
for(b = bcache.buf; b < bcache.buf+NBUF; b++){
b->next = bcache.head.next;
b->prev = &bcache.head;
initsleeplock(&b->lock, "buffer");
bcache.head.next->prev = b;
bcache.head.next = b;
}
}
5.17. fileinit関数
この関数はファイルテーブル構造体のロックを初期化する。
ファイルテーブル構造体は大域変数ftableとして定義されており、fileフィールドにはオープンしているファイルを持つ。 要素数100なのでオープンできるのは最大100ファイル。
param.h
#define NFILE 100 // open files per system
file.c
struct {
struct spinlock lock;
struct file file[NFILE];
} ftable;
void
fileinit(void)
{
initlock(&ftable.lock, "ftable");
}
file構造体
各フィールドは名前の通り。
タイプに合わせてpipeフィールドかinodeフィールドに各構造体を持つ。
iノードの場合はoffフィールドにファイル内でのオフセットを持つ。
file.h
struct file {
enum { FD_NONE, FD_PIPE, FD_INODE } type;
int ref; // reference count
char readable;
char writable;
struct pipe *pipe;
struct inode *ip;
uint off;
};
pipe構造体
dataフィールドはパイプで流すデータを保持する。
他のフィールドはコメントの通り。
data, nread, nwriteフィールドは、consoleintr関数とconsoleread関数で使用されるinput構造体のbuf, r, wフィールドと同様の使い方をする。 つまりnreadとnwriteは増加し続け、dataにはnreadとnwriteをPIPESIZEで割った余りをインデックスとしてアクセスする。
pipe.c
#define PIPESIZE 512
struct pipe {
struct spinlock lock;
char data[PIPESIZE];
uint nread; // number of bytes read
uint nwrite; // number of bytes written
int readopen; // read fd is still open
int writeopen; // write fd is still open
};
5.18. ideinit関数
この関数ではIDEの割り込みの有効化と、ディスク1の存在確認を行う。
ide.cに宣言されている静的なint型の変数havedisk1が、ディスク1の有無を示すフラグとなっており、値が1場合にディスク1があることを示す。
IDEからの割り込みをioapicenable関数で有効化する。 IRQ番号は「OSDev Interrupt」（リンク29）の表「Standard ISA IRQs」をによると、14番がPrimary ATA Hard Disk、と15番がSecondary ATA Hard Diskとなっている。 ここでは14番（IRQ_IDE）からの割り込みを有効化する。 割り込み先はcpuid（LAPIC ID）が最も大きいcpuに設定する。 cpu数を示す大域変数ncpuはmpinit関数で設定した。
idewait関数でディスク0がビジーでもエラーでもなくなるまで待つ。
ディスク1の有無を確認するために、読み書きを行うディスクをディスク1に切り替える。
「OSDev ATA PIO Mode」（リンク23）によると、IDEコントローラのdrive/headレジスタ（0x1f6）の4bitを1にすることでディスク1に切り替えられる。
また、5～7bitは101で固定のようだが、ここでは0xe0で全て1に設定している。
ディスク1のステータスレジスタ（0x1f7）から0以外の値が読み取れるまで、for文で1000回ループする。
エラーになっていようがレディになっていようがとりあえず0以外が返ってくればディスク1が存在することは確認できる。
ディスク1の存在確認完了後、読み書きするディスクをディスク0に戻す。
traps.h
#define IRQ_IDE 14
ide.c
static int havedisk1;
/* 略 */
void
ideinit(void)
{
int i;
initlock(&idelock, "ide");
ioapicenable(IRQ_IDE, ncpu - 1);
idewait(0);
// Check if disk 1 is present
outb(0x1f6, 0xe0 | (1<<4));
for(i=0; i<1000; i++){
if(inb(0x1f7) != 0){
havedisk1 = 1;
break;
}
}
// Switch back to disk 0.
outb(0x1f6, 0xe0 | (0<<4));
}
5.19. startothers関数
各APを起動し、GDT、ページング、IDT等の設定を行い、スケジューラを実行する。
APをスタートさせ、設定を済ませて一気にスケジューラの起動まで行う。 なのでmain関数の最後に呼ばれるmpmain関数もここで先に呼ばれる。 APで行う設定はほとんどBSPと同じように行う。
startothers関数を見る前に、APのエントリポイントとなるentryother.Sを見る。
Makefileのターゲットentryotherを見ると、まずgccでentryother.Sからentryother.oを作成する。
各コマンドのオプションについては「2. xv6.imgのビルド」で見た。
ldのTtextオプションでTEXTセグメントの開始アドレスを0x7000とし、entryother.oからbootblockother.oを作成する。
objcopyでbootblockother.oからTEXTセクションのみをentryotherとしてコピーする。
出力にバイナリを指定しているため、entryotherに次の3つのシンボルが作成される。
- _binary_entryother_start
- _binary_entryother_end
- _binary_entryother_size
最後にobjdumpでbootblockother.oを逆アセンブルし、entryother.asmを作成している。 カーネルには作成したバイナリのentryotherがリンクされる。
Makefile
entryother: entryother.S
$(CC) $(CFLAGS) -fno-pic -nostdinc -I. -c entryother.S
$(LD) $(LDFLAGS) -N -e start -Ttext 0x7000 -o bootblockother.o entryother.o
$(OBJCOPY) -S -O binary -j .text bootblockother.o entryother
$(OBJDUMP) -S bootblockother.o > entryother.asm
memmove関数を使用してentryother.Sのコードを物理アドレス0x7000にコピーする。 APではページングがまだ有効化されていないので、P2Vマクロを使用して仮想アドレスを求める必要がある。
forループで大域変数cpusを走査し、APをひとつずつ起動する。 BSPの場合はcontinue。 このループはBSPで実行されているため、mycpu関数はBSPのcpu構造体を返す。
APの起動時に使用するカーネルスタックとして変数stackに1ページ分のメモリを割り当てる。 割り当てにはkalloc関数を用いる。 大域変数kmemのuse_lockフィールドは依然として0なので排他制御は行わない（kinit2関数で初めて1になる）。
entryotherを実行する際に渡す引数をスタックにセットする。
- 第一引数: スタックの底のアドレス。 スタックのアドレスにカーネルスタックサイズ（4kB）を加算して求める。
- 第二引数: main.cに定義されているmpenter関数のアドレス。関数ポインタとしてキャストして代入する。
- 第三引数: main.cに定義されている変数entrypgdirのアドレス。 ラージページのページディレクトリで、0番と512番の2つのエントリが0ページ目（物理アドレス0から4MB分）を指している。
BSPはAPのcpu構造体のstartedフィールドが0でなくなるまでwhileループする。 startedフィールドが1になるまでの大まかな流れは次の通り。
- lapicstartap関数でAPを起動
- codeとして渡したentryother.Sの実行
- entryother.Sに第二引数として渡したmpenter関数の実行
- mpmain関数でAPのcpu構造体のstartedフィールドに1を設定
main.c
static void
startothers(void)
{
extern uchar _binary_entryother_start[], _binary_entryother_size[];
uchar *code;
struct cpu *c;
char *stack;
// Write entry code to unused memory at 0x7000.
// The linker has placed the image of entryother.S in
// _binary_entryother_start.
code = P2V(0x7000);
memmove(code, _binary_entryother_start, (uint)_binary_entryother_size);
for(c = cpus; c < cpus+ncpu; c++){
if(c == mycpu()) // We've started already.
continue;
// Tell entryother.S what stack to use, where to enter, and what
// pgdir to use. We cannot use kpgdir yet, because the AP processor
// is running in low memory, so we use entrypgdir for the APs too.
stack = kalloc();
*(void**)(code-4) = stack + KSTACKSIZE;
*(void(**)(void))(code-8) = mpenter;
*(int**)(code-12) = (void *) V2P(entrypgdir);
lapicstartap(c->apicid, V2P(code));
// wait for cpu to finish mpmain()
while(c->started == 0)
;
}
}
/* 略 */
__attribute__((__aligned__(PGSIZE)))
pde_t entrypgdir[NPDENTRIES] = {
// Map VA's [0, 4MB) to PA's [0, 4MB)
[0] = (0) | PTE_P | PTE_W | PTE_PS,
// Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
[KERNBASE>>PDXSHIFT] = (0) | PTE_P | PTE_W | PTE_PS,
};
lapicstartap関数
この関数ではAPを起動し、entryother.Sを実行する。
APの起動方法は「MultiProcessor Specification Version 1.4」（リンク14）のB.4「Application Processor Startup」に記載されている。
起動の流れは次のようになる。
- BSPのBIOSシャットダウンコードを0x0Aに初期化し、warm reset vectorにAPリセット時に実行させるコードのアドレスを設定する。 BIOSシャットダウンコード（0x0A）は、リセット時にBIOSの初期化処理を行わず、EOI（End Of Interrupt割り込み終了の信号）なしで40:67（CS:IP）に格納されている4バイトのアドレスにジャンプする。
- BSPから起動したいAPにINIT IPIを送る。
- IPIの処理が終わるまで10ms待つ。
- BSPから起動したいAPにSTARTUP IPIを送る。このとき、Vectorフィールドに実行開始アドレスを入れる。
- IPIの処理が終わるまで200μs待つ。
- 手順4と5をもう一度行う。INIT IPIとSTARTUP IPIは自動で再試行せず、OSはそれを正常に行う必要があるため2回呼び出す。 lapicstartap関数のコメントによると、2回目のSTARTUP IPIでのみAPを起動させるアーキテクチャも存在するらしい。
INIT IPIの使用方法はlapicinit関数で見た。
STARTUP IPIの使用方法は「MultiProcessor Specification Version 1.4」（リンク14）のB.4.2「USING STARTUP IPI」に記載されている。
このIPIは送信先のプロセッサをリアルモードで物理アドレス0x000VV000から実行する。
VVの部分は、ICRのVectorフィールドに設定された値が入る。
起動手順をlapicstartap関数に沿って読んでいく。 完全に上記手順に従っているわけではないため、行っていることがやや異なる。
手順1:
BIOSのシャットダウンコードを0x0Aに初期化する。
BIOSの設定を行うCMOSのポートは「Bochs Developers Guide」（リンク9）によると、0x70～0x7Fであり0x70がCMOSのインデックスレジスタとなっている。
シャットダウンコードの設定はシャットダウンステータスバイト（0x0F）から行うことができ、0x0Aの場合は、リセット時に40:67（CS:IP）に格納されている4バイトのアドレスにジャンプする設定となる。
リセット時にentryother.Sが実行されるよう、物理アドレス0x467にcode（引数addr）のアドレスを代入する。
リアルモードのセグメント機構ではセグメントレジスタが16bit、アドレスバスが20bitであるため、セグメントのアクセスではアドレスの下位4bitを0とする。
そのため0x7000（entryotherの開始アドレス）を4bit右シフトしている。
この辺りのことは「初めて読む486」（書籍2）に書いてある。
手順2:
APにINIT IPIを2回送る。
INIT IPIはlapicinit関数で使用したが、ここではLevelがAssertになっているため、もう一度見る。
IPIについては「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）のVol.3A「10.6.1 Interrupt Command Register (ICR)」に記載されている。
1回目:
LAPICのICR（Interrupt Command Register）（LAPICのインデックス0x310）に書き込みを行うことでIPIを送信する。
上半分（56bit目）にLAPIC IDを設定し、下半分にはINIT（0x500）、LEVEL（0x8000）、ASSERT（0x4000）を設定する（0b1100 0101 0000 0000）。
8～10bitが0b101なので、Delivery ModeはINIT。
11bitが0なのでDestination ModeはPhysical。
14bitが1なのでLevelはAssert。
15bitが1なのでTrigger ModeはLevel。
Levelフラグが1（Assert）かつ、Delivery ModeのINITがLevel De-assertでないことから、INITリクエストを特定のプロセッサに送信することがわかる。
送信先はDestination ModeがPhysicalであることから、ICRの56～59bitで指定されたLAPICIDのプロセッサとなる。
INIT IPIの処理が終わるまで200μ秒待つ （microdelay関数）。
2回目:
Levelフラグを0（De-assert）でINIT IPIを送信する。
Delivery ModeがDe-assertなので送信先は全てのプロセッサとなる。
手順3:
100μs待つ。
「MultiProcessor Specification Version 1.4」（リンク14）には10msとあるが、lapicstartap関数のコメントにBochsでは遅すぎると記載がある。
手順4:
STARTUP IPIを2回送る。
ICRの56～59bitに送信先APのLAPIC IDを設定し、8～10bit目に0b110（Start-Up）を設定して、Vectorにentryother.Sのアドレス（0x7）を設定（実行を開始するアドレスVVの部分）する。
手順5:
200μs待つ。
関数内のAP起動手順は以上。 第一引数apicidで指定されたAPはSTARTUP IPIで起動され、entryother.Sが実行される。
lapic.c
#define ICRLO (0x0300/4) // Interrupt Command
#define INIT 0x00000500 // INIT/RESET
#define STARTUP 0x00000600 // Startup IPI
#define DELIVS 0x00001000 // Delivery status
#define ASSERT 0x00004000 // Assert interrupt (vs deassert)
#define DEASSERT 0x00000000
#define LEVEL 0x00008000 // Level triggered
#define BCAST 0x00080000 // Send to all APICs, including self.
#define BUSY 0x00001000
#define FIXED 0x00000000
#define ICRHI (0x0310/4) // Interrupt Command [63:32]
/* 略 */
#define CMOS_PORT 0x70
#define CMOS_RETURN 0x71
/* 略 */
void
lapicstartap(uchar apicid, uint addr)
{
int i;
ushort *wrv;
// "The BSP must initialize CMOS shutdown code to 0AH
// and the warm reset vector (DWORD based at 40:67) to point at
// the AP startup code prior to the [universal startup algorithm]."
outb(CMOS_PORT, 0xF); // offset 0xF is shutdown code
outb(CMOS_PORT+1, 0x0A);
wrv = (ushort*)P2V((0x40<<4 | 0x67)); // Warm reset vector
wrv[0] = 0;
wrv[1] = addr >> 4;
// "Universal startup algorithm."
// Send INIT (level-triggered) interrupt to reset other CPU.
lapicw(ICRHI, apicid<<24);
lapicw(ICRLO, INIT | LEVEL | ASSERT);
microdelay(200);
lapicw(ICRLO, INIT | LEVEL);
microdelay(100); // should be 10ms, but too slow in Bochs!
// Send startup IPI (twice!) to enter code.
// Regular hardware is supposed to only accept a STARTUP
// when it is in the halted state due to an INIT. So the second
// should be ignored, but it is part of the official Intel algorithm.
// Bochs complains about the second one. Too bad for Bochs.
for(i = 0; i < 2; i++){
lapicw(ICRHI, apicid<<24);
lapicw(ICRLO, STARTUP | (addr>>12));
microdelay(200);
}
}
entryother.S
この関数はSTARTUP IPIによりAPで実行される。
概ねbootasm.S、entry.Sと同様。
GDTをロードし、プロテクトモードへ移行、ページングを有効化する。
最後にスタックポインタをセットし、mpenter関数を呼び出す。
ラージページの設定まではbootasm.Sとentry.Sのコードと同じ。
ページディレクトリの設定から見る。
entryother.Sはobjcopyコマンドで作成されたバイナリとしてリンクされているため、main.cで定義されているentrypgdir変数が見えない。
そのため、startothers関数内であらかじめ第3引数の位置（start-12）にセットしておいたentrypgdirのアドレスを使用する。
同様に、スタックポインタに設定するスタックのアドレスはstartothers関数にてkalloc関数で割り当てた1ページ分の領域を設定する。
これは第一引数の位置にセットしたので、 start-4 になる。
最後にmpenter関数のアドレスは、startothers関数で第二引数の位置にセットしたので、start-8 になる。
entryother.S
.code16
.globl start
start:
cli
# Zero data segment registers DS, ES, and SS.
xorw %ax,%ax
movw %ax,%ds
movw %ax,%es
movw %ax,%ss
# Switch from real to protected mode. Use a bootstrap GDT that makes
# virtual addresses map directly to physical addresses so that the
# effective memory map doesn't change during the transition.
lgdt gdtdesc
movl %cr0, %eax
orl $CR0_PE, %eax
movl %eax, %cr0
# Complete the transition to 32-bit protected mode by using a long jmp
# to reload %cs and %eip. The segment descriptors are set up with no
# translation, so that the mapping is still the identity mapping.
ljmpl $(SEG_KCODE<<3), $(start32)
//PAGEBREAK!
.code32 # Tell assembler to generate 32-bit code now.
start32:
# Set up the protected-mode data segment registers
movw $(SEG_KDATA<<3), %ax # Our data segment selector
movw %ax, %ds # -> DS: Data Segment
movw %ax, %es # -> ES: Extra Segment
movw %ax, %ss # -> SS: Stack Segment
movw $0, %ax # Zero segments not ready for use
movw %ax, %fs # -> FS
movw %ax, %gs # -> GS
# Turn on page size extension for 4Mbyte pages
movl %cr4, %eax
orl $(CR4_PSE), %eax
movl %eax, %cr4
# Use entrypgdir as our initial page table
movl (start-12), %eax
movl %eax, %cr3
# Turn on paging.
movl %cr0, %eax
orl $(CR0_PE|CR0_PG|CR0_WP), %eax
movl %eax, %cr0
# Switch to the stack allocated by startothers()
movl (start-4), %esp
# Call mpenter()
call *(start-8)
movw $0x8a00, %ax
movw %ax, %dx
outw %ax, %dx
movw $0x8ae0, %ax
outw %ax, %dx
spin:
jmp spin
.p2align 2
gdt:
SEG_NULLASM
SEG_ASM(STA_X|STA_R, 0, 0xffffffff)
SEG_ASM(STA_W, 0, 0xffffffff)
gdtdesc:
.word (gdtdesc - gdt - 1)
.long gdt
mpenter関数
BSPで行った設定を同様にAPにも行う。
switchkvm関数でcr3にカーネル用のページディレクトリkpgdirのアドレスをセットする。
kpgdirはBSPと同じものが使用される。
4kBページングとなるのも同様。
seginit関数でGDTの作成とロード、lapicinit関数でLAPICの設定を行う。
main.c
static void
mpenter(void)
{
switchkvm();
seginit();
lapicinit();
mpmain();
}
mpmain関数
この関数はコンソールに「cpu1: starting 1」と表示し、IDTをロードしてcpu構造体のstartedフィールドの値を1にした後、スケジューラを呼び出す。
コンソールの文字列はLAPIC IDによって変わる。
cpu構造体のstartedフィールドをxchg関数で1にする。
ここでxchg命令を使ってアトミックにstartedフィールドの値を更新する理由はわからない。
この関数はBSPからmain関数の最後でも呼び出される。
scheduler関数はその時に見ることにする。
main.c
static void
mpmain(void)
{
cprintf("cpu%d: starting %d\n", cpuid(), cpuid());
idtinit(); // load idt register
xchg(&(mycpu()->started), 1); // tell startothers() we're up
scheduler(); // start running processes
}
cprintf関数
この関数は与えられたフォーマットでコンソールに文字を出力する。 フォーマットにはエスケープシーケンスを使用することが可能であり、第二引数以降の可変個の文字をフォーマットして挿入できる。
変数argpに可変長引数の先頭アドレスを代入する。
第一引数fmtのアドレスをuint分加算し、スタックの低い位置（高いアドレス）に有る第二引数を得る。
fmtを1バイトずつ操作し、場合分けしながらコンソールに出力する。
- %以外: consputc関数でコンソールに出力する。
- 0: ループをbreak。
- d: printint関数で可変長引数から10進数符号ありでコンソールに出力する。
- x, p: printint関数で可変長引数から16進数符号なしでコンソールに出力する。
- s: 可変長引数から文字列を出力する。 1文字ずつ取り出し、値が0になるまでconsputc関数で1バイトずつコンソールに出力する。 1文字目が0の場合のみ文字列 "(null)" を出力する。
- %: consputc関数でコンソールに '%' を出力する。
console.c
void
cprintf(char *fmt, ...)
{
int i, c, locking;
uint *argp;
char *s;
locking = cons.locking;
if(locking)
acquire(&cons.lock);
if (fmt == 0)
panic("null fmt");
argp = (uint*)(void*)(&fmt + 1);
for(i = 0; (c = fmt[i] & 0xff) != 0; i++){
if(c != '%'){
consputc(c);
continue;
}
c = fmt[++i] & 0xff;
if(c == 0)
break;
switch(c){
case 'd':
printint(*argp++, 10, 1);
break;
case 'x':
case 'p':
printint(*argp++, 16, 0);
break;
case 's':
if((s = (char*)*argp++) == 0)
s = "(null)";
for(; *s; s++)
consputc(*s);
break;
case '%':
consputc('%');
break;
default:
// Print unknown % sequence to draw attention.
consputc('%');
consputc(c);
break;
}
}
if(locking)
release(&cons.lock);
}
printint関数
この関数は整数xxを、基数baseとしてコンソールに出力する。 また、第三引数signが0以外の場合符号ありで出力する。
配列digitsを使用して整数xxを文字コードに変換し、配列bufに持つ。 bufは頭から詰めていき、お尻から出力する。
console.c
static void
printint(int xx, int base, int sign)
{
static char digits[] = "0123456789abcdef";
char buf[16];
int i;
uint x;
if(sign && (sign = xx < 0))
x = -xx;
else
x = xx;
i = 0;
do{
buf[i++] = digits[x % base];
}while((x /= base) != 0);
if(sign)
buf[i++] = '-';
while(--i >= 0)
consputc(buf[i]);
}
idtinit関数
この関数はtvinit関数で作成したIDTをlidt関数を通してlidt命令でロードする。
trap.c
void
idtinit(void)
{
lidt(idt, sizeof(idt));
}
x86.h
struct gatedesc;
static inline void
lidt(struct gatedesc *p, int size)
{
volatile ushort pd[3];
pd[0] = size-1;
pd[1] = (uint)p;
pd[2] = (uint)p >> 16;
asm volatile("lidt (%0)" : : "r" (pd));
}
5.20. kinit2関数
freerange関数でkmem構造体のfreelistに0x400000～0xe000000までの領域をページとして加える。 差を取ると0xdc00000で4096で割ると56320ページ分ある。
main.c
int
main(void)
{
/* 略 */
kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after startothers()
/* 略 */
}
kalloc.c
void
kinit2(void *vstart, void *vend)
{
freerange(vstart, vend);
kmem.use_lock = 1;
}
5.21. userinit関数
initcode.Sのプロセスを作成し、プロセステーブルに追加する。
userinit関数を見る前に、initプロセスを実行するinitcode.Sと、プロセステーブルのエントリをプロセスとして割り当てるallocproc関数を見る。
initcode.S
entryother.Sと同様。 TEXTセグメントの開始アドレスは0x0。 以下のシンボルが作成され、バイナリがカーネルにリンクされる。
- _binary_initcode_start
- _binary_initcode_end
- _binary_initcode_size
Makefile
initcode: initcode.S
$(CC) $(CFLAGS) -nostdinc -I. -c initcode.S
$(LD) $(LDFLAGS) -N -e start -Ttext 0 -o initcode.out initcode.o
$(OBJCOPY) -S -O binary initcode.out initcode
$(OBJDUMP) -S initcode.o > initcode.asm
allocproc関数
この関数はプロセステーブルから未使用のエントリを取得し、初期化して返す。
プロセステーブルを走査し、stateフィールドがUNUSEDのエントリを取得してfoundラベルにジャンプする。
foundラベル以降ではproc構造体の各フィールドと、カーネルスタックを初期化する。
kalloc関数で1ページ分のをカーネルスタックとして割り当てる。
カーネルスタックの底（p->state + KSTACKSIZE）から順に以下3つを設定する。
- プロセスの状態を保存するために使用するトラップフレームの領域を確保する。
- 4バイト分の領域を確保し、trapret関数のアドレスを代入する。 カーネル空間での処理終了後、trapret関数を呼び出してトラップフレームに保存した状態を復元し、最終的にiret命令でユーザ空間に戻る。
- contextフィール分の領域を確保し、0埋めする。 context構造体のeipフィールドにforkret関数のアドレスを代入する。
プロセスは最初のコンテキストスイッチ時にforkret関数の実行から始まり、次にtrapret関数が実行され、トラップフレームに保存した状態を復元してユーザ空間でプログラムを実行することになる。
forkret関数とtrapret関数についてはinitプロセスで見る。
proc.h
enum procstate { UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };
proc.c
static struct proc*
allocproc(void)
{
struct proc *p;
char *sp;
acquire(&ptable.lock);
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
if(p->state == UNUSED)
goto found;
release(&ptable.lock);
return 0;
found:
p->state = EMBRYO;
p->pid = nextpid++;
release(&ptable.lock);
// Allocate kernel stack.
if((p->kstack = kalloc()) == 0){
p->state = UNUSED;
return 0;
}
sp = p->kstack + KSTACKSIZE;
// Leave room for trap frame.
sp -= sizeof *p->tf;
p->tf = (struct trapframe*)sp;
// Set up new context to start executing at forkret,
// which returns to trapret.
sp -= 4;
*(uint*)sp = (uint)trapret;
sp -= sizeof *p->context;
p->context = (struct context*)sp;
memset(p->context, 0, sizeof *p->context);
p->context->eip = (uint)forkret;
return p;
}
userinit関数
変数pに、allocproc関数を使用してプロセステーブルからエントリを割り当てる。
このプロセスは最初initcode.Sを実行するために使用されるが、後からexecシステムコールによりinit.cを実行するプロセスに変わる。
そのため、initプロセスを持つためのproc.cの変数initprocに代入しておく。
プロセスのpgdirフィールドにカーネル空間のページディレクトリエントリを持ったページディレクトリを作成する。
作成はsetupkvm関数でvm.cのkmap配列を基に行われる。
inituvm関数で、initcode.Sを配置するためのページを割り当て、ページディレクトリにPDEとPTEを作成する。
initcode.SのTEXTセクションは仮想アドレス0から始まるので、0番目のPDEから変換するように作る。
initプロセスのトラップフレームの設定を行う。
スケジューラによりinitプロセスにコンテキストスイッチされたとき、initプロセスのcontextフィールドのeipの値により、forkret関数が実行される。
さらにforkret関数からiret命令によりtrapret関数が実行され、トラップフレームの内容にしたがってプログラムが実行される。
ここではその準備をする。
- cs: ユーザコードセグメントディスクリプタのエントリ番号（3）と、DPL3を設定する。
- ds: 同様にユーザデータセグメントディスクリプタのエントリ番号（4）と、DPL3を設定する。
- es, ss: データセグメントディスクリプタを設定する。 特に使用しないので、とりあえずデータセグメントディスクリプタを設定しているんだと思う。
- eflags: 9bit（Interrupt Enable Flag）のみを1に設定する（0x00000200）。 つまりユーザ空間に戻った後は割り込みが有効化される。 eflagsレジスタの各bitの役割については「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）のVol.1「3.4.3 EFLAGS Register」の図3-8 「EFLAGS Register」に記載されている。
- esp: ページサイズ（4096）を設定する。 initcode.Sには1ページ分の領域しか割り当てないので、その中で最も高いアドレスにスタックポインタを設定する。
- eip: initcode.Sは仮想アドレス0から開始するようにリンクされているため0を設定する。
プロセスの名前に「initcode」を設定する。
safestrcpy関数で即値 "initcode" をコピーしている。
cwdフィールドにルートディレクトリのinode構造体を設定する。
namei関数はinode構造体を取得する。
プロセスを実行する準備が整ったので、状態を実行可能状態とする。
ここで、コメントにもあるように、他のAPでは既にスケジューラが動いているため、initプロセスが必ずしもBSPで実行されるとは限らない。
MakefileのCPUSを8とかにしてGDBでscheduler関数の途中で止めてinitcodeプロセスが実行されるときのapicidを確認すると、APで実行されるパターンを観測できる。
proc.c
void
userinit(void)
{
struct proc *p;
extern char _binary_initcode_start[], _binary_initcode_size[];
p = allocproc();
initproc = p;
if((p->pgdir = setupkvm()) == 0)
panic("userinit: out of memory?");
inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size);
p->sz = PGSIZE;
memset(p->tf, 0, sizeof(*p->tf));
p->tf->cs = (SEG_UCODE << 3) | DPL_USER;
p->tf->ds = (SEG_UDATA << 3) | DPL_USER;
p->tf->es = p->tf->ds;
p->tf->ss = p->tf->ds;
p->tf->eflags = FL_IF;
p->tf->esp = PGSIZE;
p->tf->eip = 0; // beginning of initcode.S
safestrcpy(p->name, "initcode", sizeof(p->name));
p->cwd = namei("/");
// this assignment to p->state lets other cores
// run this process. the acquire forces the above
// writes to be visible, and the lock is also needed
// because the assignment might not be atomic.
acquire(&ptable.lock);
p->state = RUNNABLE;
release(&ptable.lock);
}
inituvm関数
この関数はinitcode.Sをinitプロセスの0番目のPDEに配置するためだけに存在している。
pgdirにinitプロセスのページディレクトリのアドレスを受け、initにinitcode.Sの開始アドレス、szにinitcode.Sのサイズを受ける。
まずszがページサイズ以上だった場合にpanicする。
理由は定かではないけど、恐らく、ページングが有効になっている都合上、initcode.Sが複数ページにわたるとkallocでも複数ページ確保しなければならず、initcode.Sを適切に分割して各ページに配置することが手間になるからだと思う。
pgdirに仮想アドレス0から1ページ分の領域を、memの物理アドレスを参照するようにPDEとPTEを作成する。
作成にはmappages関数を使用し、PTEの属性は書き込みフラグとユーザフラグを立てる。
最後にinitcode.Sをmemmove関数でmemにコピーする。
memはkalloc関数で割り当てる1ページ分の領域しか持っていないため、initプロセスは4kBに収まる必要がある。
vm.c
void
inituvm(pde_t *pgdir, char *init, uint sz)
{
char *mem;
if(sz >= PGSIZE)
panic("inituvm: more than a page");
mem = kalloc();
memset(mem, 0, PGSIZE);
mappages(pgdir, 0, PGSIZE, V2P(mem), PTE_W|PTE_U);
memmove(mem, init, sz);
}
safestrcpy関数
この関数はsにtからn-1バイト分だけコピーする。 コピー先sはヌル終端される。
string.c
char*
safestrcpy(char *s, const char *t, int n)
{
char *os;
os = s;
if(n <= 0)
return os;
while(--n > 0 && (*s++ = *t++) != 0)
;
*s = 0;
return os;
}
namei関数
この関数はpathとして受け取ったパスのinode構造体を呼び出し元に返す。 中身としてはnamex関数を呼び出してその戻り値を返すだけ。 namex関数を呼び出す際にはnameiparentフラグ（第二引数）を0にしている。
fs.c
struct inode*
namei(char *path)
{
char name[DIRSIZ];
return namex(path, 0, name);
}
namex関数は引数pathで指定されたファイルのinode構造体を返す。
また、引数nameにファイル名を代入してくれる。
引数nameiparentが0以外の場合は、pathの親ファイルのinode構造体を返す。
変数ipに、ルートディレクトリのinode構造体か、現在のプロセスのカレントディレクトリのinode構造体を代入する。 igetとidupはiノードのところで見た。
whileループでpathのiノードを順に辿り、目的のiノードを探す。 条件式でskipelem関数を実行し、pathのファイル名をひとつずつ消化して、nameにその時のファイル名を代入し、pathを残りのパスで更新する。 つまり、namex関数の引数pathが単一のファイル名だった場合、whileループは行われない。
ループ内の処理を見る。
ipがディレクトリ以外の場合、呼び出し元に0を返す。
このループに入る時点でipがディレクトリであることが確定しているため、この分岐は実質的なエラー処理にあたる。
引数nameiparentが真かつpathの最後のループの場合、呼び出し元にnameのディレクトリを返す。
ここではip更新前なのでipはnameのひとつ上のディレクトリのinode構造体になっている。
ipを更新するため、変数nextにipのディレクトリエントリでファイル名がnameと等しいエントリのinode構造体を取得する。
取得にはdirlookup関数を使用する。
この関数は第一引数のinode構造体のデータをバッファキャッシュから取得し、ディレクトリエントリから第二引数のnameとファイル名が等しいエントリのinodeを返してくれる。
第三引数は目的のディレクトリエントリが何番目だったかを返してくれるが、使用しないのでここでは0。
whileループが終わったとき、nameには引数pathの最後のファイル名が入っており、そのinode構造体がipに入っている。 引数nameiparentが真のときにwhileループ終了後まで来る場合は不正なので、iput関数でipの参照カウンタをデクリメントし、必要であれば解放する。 pathが単一のファイル名だけだった場合がこれにあたる。
fs.c
static struct inode*
namex(char *path, int nameiparent, char *name)
{
struct inode *ip, *next;
if(*path == '/')
ip = iget(ROOTDEV, ROOTINO);
else
ip = idup(myproc()->cwd);
while((path = skipelem(path, name)) != 0){
ilock(ip);
if(ip->type != T_DIR){
iunlockput(ip);
return 0;
}
if(nameiparent && *path == '\0'){
// Stop one level early.
iunlock(ip);
return ip;
}
if((next = dirlookup(ip, name, 0)) == 0){
iunlockput(ip);
return 0;
}
iunlockput(ip);
ip = next;
}
if(nameiparent){
iput(ip);
return 0;
}
return ip;
}
skipelem関数
この関数は引数pathの最初のファイル名を引数nameにコピーし、残りを戻り値として返す。
コメントにExampleとして具体的な入出力が記載されている。
ファイル名は最大14（DIRSIZ）バイト。
fs.c
// Examples:
// skipelem("a/bb/c", name) = "bb/c", setting name = "a"
// skipelem("///a//bb", name) = "bb", setting name = "a"
// skipelem("a", name) = "", setting name = "a"
// skipelem("", name) = skipelem("////", name) = 0
//
static char*
skipelem(char *path, char *name)
{
char *s;
int len;
while(*path == '/')
path++;
if(*path == 0)
return 0;
s = path;
while(*path != '/' && *path != 0)
path++;
len = path - s;
if(len >= DIRSIZ)
memmove(name, s, DIRSIZ);
else {
memmove(name, s, len);
name[len] = 0;
}
while(*path == '/')
path++;
return path;
}
dirlookup関数
この関数はディレクトリdpから引数nameと同名のディレクトリエントリを返す。 また、引数poffにディレクトリエントリが何番目だったかを返してくれる。
forループでディレクトリエントリを走査する。 dirent構造体の取得はreadiで行う。
fs.h
#define DIRSIZ 14
struct dirent {
ushort inum;
char name[DIRSIZ];
};
fs.c
struct inode*
dirlookup(struct inode *dp, char *name, uint *poff)
{
uint off, inum;
struct dirent de;
if(dp->type != T_DIR)
panic("dirlookup not DIR");
for(off = 0; off < dp->size; off += sizeof(de)){
if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
panic("dirlookup read");
if(de.inum == 0)
continue;
if(namecmp(name, de.name) == 0){
// entry matches path element
if(poff)
*poff = off;
inum = de.inum;
return iget(dp->dev, inum);
}
}
return 0;
}
namecmp関数はstrncmp関数で14文字比較する。
strncmp関数はpとqを最大nバイト比較し、等しければ0、等しくなければ等しくなくなった文字の差を返す。
fs.c
int
namecmp(const char *s, const char *t)
{
return strncmp(s, t, DIRSIZ);
}
string.c
int
strncmp(const char *p, const char *q, uint n)
{
while(n > 0 && *p && *p == *q)
n--, p++, q++;
if(n == 0)
return 0;
return (uchar)*p - (uchar)*q;
}
5.22. スケジューラとコンテキストスイッチ
scheduler関数は無限ループで次の2つを繰り返す。
- sti関数で割り込みを有効化する
- プロセステーブルを走査して実行可能状態（RUNNABLE）のプロセスにコンテキストスイッチする
最初にschedulerが実行されるとき、プロセステーブルの64個のプロセスの内、状態がRUNNABLEになっているのはuserinit関数で作成されたinitcode.Sのプロセスのみなので、それが実行されることになる。
全てのプロセッサでschedulerが実行されており、プロセステーブルを触る可能性があるため、forループの前後でプロセステーブルのロックの取得と解放を行う。
実行可能状態のプロセスを見つけた場合、switchuvm関数でコンテキストスイッチの準備を行う。
準備ができたらプロセスを実行状態とし、swtch関数でコンテキストスイッチする。
コンテキストスイッチはTSSを用いたx86の機能を使うのではなく、スタックフレームの切り替えによって行う。
その後再びプロセスからスケジューラにコンテキストスイッチされたとき、switchkvm関数でページディレクトリをカーネルのものに切り替え、cpu構造体のprocフィールドに0を代入する。
proc.c
void
scheduler(void)
{
struct proc *p;
struct cpu *c = mycpu();
c->proc = 0;
for(;;){
// Enable interrupts on this processor.
sti();
// Loop over process table looking for process to run.
acquire(&ptable.lock);
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if(p->state != RUNNABLE)
continue;
// Switch to chosen process. It is the process's job
// to release ptable.lock and then reacquire it
// before jumping back to us.
c->proc = p;
switchuvm(p);
p->state = RUNNING;
swtch(&(c->scheduler), p->context);
switchkvm();
// Process is done running for now.
// It should have changed its p->state before coming back.
c->proc = 0;
}
release(&ptable.lock);
}
}
コンテキストスイッチ
x86にはTSSディスクリプタを使用してコンテキストスイッチを行う機能があり、「初めて読む486」（書籍2）の8章「タスク」や、「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」（リンク8）のVol.3 CHAPTER7「TASK MANAGEMENT」に記載があるが、xv6ではそれをフルに使わない。 TSSディスクリプタ自体はカーネルモードのスタックの情報とプロセスのIOMAPのために使用する。 これはLinuxカーネルも同様で、「詳解LINUXカーネル 第3版」（書籍3）の3.3.2「タスク状態セグメント」に記載がある。 xv6はタスク切り替えをスタックとret命令を使用して行う。
switchuvm関数
この関数はコンテキストスイッチするプロセスのTSS構造体とそのディスクリプタを作成し、ltr命令でそれをロードする。
また、lcr3関数でプロセスのページディレクトリをcr3にロードする。
TSSディスクリプタはcpuのGDTの5番目にセットする。
x86のコンテキストスイッチ機能を使用する場合はプロセス切り替え時に、切り替え前のプロセスと切り替え後のプロセスの2つのTSSディスクリプタがGDTに必要だが、その機能を使用しないので毎回GDTの5番目にTSSディスクリプタを格納する。
TSSとTSSディスクリプタの構造はIntel-SDM（リンク8）のVol.3 Figure 7-2「32-Bit Task-State Segment (TSS)」とVol.3 Figure 7-3「TSS Descriptor」に書いてある。
TSSディスクリプタはmmu.hに定義されているSEG16マクロを使用して作成する。
Intel-SDMのFigure 7-3によるとtypeフィールドの次のbit（segdesc構造体のsフィールド）は常に0。
segdesc構造体のコメントを見ると、このbitは0がシステム、1がアプリケーションを表すことがわかる。
SEG16マクロの第二引数baseには、cpu構造体のtsフィールドのアドレスを渡す。
tsフィールドはtaskstate構造体で、Intel-SDMのFigure 7-2と同じ構造をしている。
TSSではカーネルモードで使用するスタックセグメント（ss）とスタックポインタ（esp）、IOMAP（iomb）のみを使用する。
iombフィールドにはプロセスからin命令やout命令でアクセスを許可するポートを設定する。
bitが0のときにアクセスの許可を示し、ここでは0xFFFFで全てのbitを1に設定しているため、プロセスはどのポートへもアクセスできない。
ltr命令でTSSディスクリプタをtrレジスタにロードする。
GDTは1エントリ8バイトなので、5を3bit左シフト（5*2^3）することでTSSディスクリプタを指定する。
プロセスのページディレクトリをcr3にロードし、仮想アドレス空間を切り替える。
これでswitchuvm関数は終わりだが、まだeipやespの値は切り替わっていないため、scheduler関数に処理が戻る。
mmu.h
#define SEG_TSS 5 // this process's task state
/* 略 */
#define SEG16(type, base, lim, dpl) (struct segdesc) \
{ (lim) & 0xffff, (uint)(base) & 0xffff, \
((uint)(base) >> 16) & 0xff, type, 1, dpl, 1, \
(uint)(lim) >> 16, 0, 0, 1, 0, (uint)(base) >> 24 }
vm.c
void
switchuvm(struct proc *p)
{
if(p == 0)
panic("switchuvm: no process");
if(p->kstack == 0)
panic("switchuvm: no kstack");
if(p->pgdir == 0)
panic("switchuvm: no pgdir");
pushcli();
mycpu()->gdt[SEG_TSS] = SEG16(STS_T32A, &mycpu()->ts,
sizeof(mycpu()->ts)-1, 0);
mycpu()->gdt[SEG_TSS].s = 0;
mycpu()->ts.ss0 = SEG_KDATA << 3;
mycpu()->ts.esp0 = (uint)p->kstack + KSTACKSIZE;
// setting IOPL=0 in eflags *and* iomb beyond the tss segment limit
// forbids I/O instructions (e.g., inb and outb) from user space
mycpu()->ts.iomb = (ushort) 0xFFFF;
ltr(SEG_TSS << 3);
lcr3(V2P(p->pgdir)); // switch to process's address space
popcli();
}
swtch関数
この関数はスタックフレームの切り替えを行い、ret命令を使用してeipを切り替え先プロセスのリターンアドレスに移動させる。
この関数の動作を知るためにはGCCの関数呼び出し規約を知っている必要がある。 呼び出し規約は「Guide: Function Calling Conventions」（リンク22）でいくつかの具体例とともに解説されている。 関数呼び出し時にはスタックに引数が右から左に順にpushされ、次にリターンアドレスがpushされる。 つまり引数が2つある場合は、第二引数がスタックにpushされ、次に第一引数がpushされ、最後にリターンアドレスがpushされる。 また、関数に入るときと出るときとでebx、esi、edi、ebpの値が変更されてはいけない。
swtch関数の動きとしては、espを切り替え先プロセスのスタックに切り替え、そこに積まれているリターンアドレスにret命令でeipを移動する。
初めてのschedulerが呼ばれてから、プロセスへの切り替えの流れは以下のようになる。
- swtch関数の第一引数にはスケジューラのコンテキスト（まだ0x0）、第二引数にはuserinit関数で作成されたproc構造体のcontextフィールドが渡される。
この時点でスタックには次のように値が積まれている。
添え字は積まれている順番で、括弧内は入っている値。
popすると2番目（リターンアドレス）が取り出されることになる。
0: 第二引数（proc構造体のcontextフィールド）
1: 第一引数（スケジューラのコンテキスト0x0）
2: リターンアドレス（scheduler関数のswitchkvm関数を呼び出すアドレス）
このとき、contextフィールドはcontext構造体だが、スタックと捉えることができる。 contextフィールドには次のように値が積まれている。
0: eip（forkret関数のアドレス）
1: ebp（0）
2: ebx（0）
3: esi（0）
4: edi（0） - スタックにebx、esi、edi、ebpの値を保存する。
スタックは次のようになる。
0: 第二引数（proc構造体のcontextフィールド）
1: 第一引数（スケジューラのコンテキスト0x0）
2: リターンアドレス（scheduler関数のswitchkvm関数を呼び出すアドレス）
3: ebp
4: ebx
5: esi
6: edi - スケジューラのcontext構造体がスタックを指すようにする（context構造体が完成する）。
- espにproc構造体のcontextフィールドのアドレスを代入し、プロセスのスタックに切り替える。
- プロセスのスタックからebx、esi、edi、ebpの値を復帰する。 スタックはeip（forkret関数のアドレス）のみが積まれた状態となる。
- ret命令でforkret関数に移動し、プロセスの切り替えが終了する。
proc.h
struct context {
uint edi;
uint esi;
uint ebx;
uint ebp;
uint eip;
};
swtch.S
.globl swtch
swtch:
movl 4(%esp), %eax
movl 8(%esp), %edx
# Save old callee-saved registers
pushl %ebp
pushl %ebx
pushl %esi
pushl %edi
# Switch stacks
movl %esp, (%eax)
movl %edx, %esp
# Load new callee-saved registers
popl %edi
popl %esi
popl %ebx
popl %ebp
ret
6. fs.imgの作成
initプロセスの実行を見る前にここで一度ファイルシステムの作成について見ることにする。 xv6で使用するファイルシステムはfs.imgとして作成される。
7. initの実行
8. shの実行
参考リンク
- 「xv6 a simple, Unix-like teaching operating system」
https://pdos.csail.mit.edu/6.828/2018/xv6/book-rev11.pdf - 「xv6のデバッグ環境をつくる」
https://qiita.com/ksky/items/974ad1249cfb2dcf5437 - 「Using the GNU Compiler Collection (GCC)」
https://gcc.gnu.org/onlinedocs/gcc-6.5.0/gcc/ - 「Using ld The GNU linker ld version 2 January 1994」
https://ftp.gnu.org/old-gnu/Manuals/ld-2.9.1/html_mono/ld.html - 「3 objcopy」
https://sourceware.org/binutils/docs-2.35/binutils/objcopy.html#objcopy - 「GNU make」
https://www.gnu.org/software/make/manual/make.html - 「Keyboard scancodes Andries Brouwer」
https://www.win.tue.nl/~aeb/linux/kbd/scancodes.html - 「Intel 64 and IA-32 architectures software developer's manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4」
https://software.intel.com/content/www/us/en/develop/download/intel-64-and-ia-32-architectures-sdm-combined-volumes-1-2a-2b-2c-2d-3a-3b-3c-3d-and-4.html - 「Bochs Developers Guide」. Kevin Lawton. Bryce Denney. Christophe Bothamy. Edited by Michael Calabrese
http://bochs.sourceforge.net/doc/docbook/development/index.html - 「OSDev I/O Ports」
https://wiki.osdev.org/I/O_Ports - 「XT, AT and PS/2 I/O port addresses」
http://bochs.sourceforge.net/techspec/PORTS.LST - 「ProgrammerSought Gnu embedded assembly, inline assembly detailed introduction」
https://programmersought.com/article/74671233226/ - 「Wikipedia Control register」
https://en.wikipedia.org/wiki/Control_register - 「MultiProcessor Specification Version 1.4」
https://pdos.csail.mit.edu/6.828/2008/readings/ia32/MPspec.pdf - 「OSDev Memory Map (x86)」
https://wiki.osdev.org/Memory_Map_(x86) - 「OSDev 8259 PIC」
https://wiki.osdev.org/PIC - 「OSDev IOAPIC」
https://wiki.osdev.org/IOAPIC - 「82093AA I/O ADVANCED PROGRAMMABLE INTERRUPT CONTROLLER (IOAPIC)」
http://web.archive.org/web/20161130153145/http://download.intel.com/design/chipsets/datashts/29056601.pdf - 「Hardware Level VGA and SVGA Video Programming Information Page CRT Controller Registers」
http://web.stanford.edu/class/cs140/projects/pintos/specs/freevga/vga/crtcreg.htm - 「OSDev Drawing In Protected Mode」
https://wiki.osdev.org/Drawing_In_Protected_Mode - 「OSDev Text UI」
https://wiki.osdev.org/Text_UI - 「Guide: Function Calling Conventions」
http://www.delorie.com/djgpp/doc/ug/asm/calling.html - 「OSDev ATA PIO Mode」
https://wiki.osdev.org/ATA_PIO_Mode - 「OSDev ATA Command Matrix」
https://wiki.osdev.org/ATA_Command_Matrix - 「OSDev LBA」
https://wiki.osdev.org/LBA - 「AsTechLog WSL2＋Ubuntu 20.04でGUIアプリを動かす」
https://astherier.com/blog/2020/08/run-gui-apps-on-wsl2/#toc_id_2 - 「ASCII Code - The extended ASCII table」
https://www.ascii-code.com/ - 「Serial Programming/8250 UART Programming」
https://en.wikibooks.org/wiki/Serial_Programming/8250_UART_Programming - 「OSDev Interrupt」
https://wiki.osdev.org/Interrupts
参考書籍
- 坂井 弘亮. リンカ・ローダ 実践開発テクニック. CQ出版社. 978-4-7898-3807-8
- 蒲地 輝尚. 初めて読む486. アスキー出版局. 4-7561-0213-1
- DANIEL P. BOVET, MARCO CASTATI. 詳解LINUXカーネル 第3版. オライリー・ジャパン. 978-4-87311-313-5
- Hisa Ando. プロセッサを支える技術. 技術評論社. 978-4-7741-4521-1
- David A.Patterson, John L.Hennessy. コンピュータの構成と設計 第4版. 日経BP社. 978-4-8222-8479-4