読書メモ: xv6 book - Chapter 1: Operating System Organization


process は、プログラム間の time share, failure isolation, interaction を提供する. interaction は file descriptor 経由で行われる (pipe)
kernel は pipe の片側が落ちたらそいつの代わりに eof を送るとか、世話をしてる

x86 依存の実装もある:
user mode のプログラムが kernel mode priviledged instruction を実行しようとしたら、kernel mode の handler に処理をわたし、clean up してそのプロセスを終了
system call: プロセッサが、priviledge level を上げ、kernel によってセットされた entry point に処理を渡す

xv6 は monolithic kernel.

process の実装に使われるメカニズム:

- user/kernel mode flag
- address 空間
- time slicing (コンテキストスイッチ)

各プロセスがあたかもそれ専用のマシンで動いているかのような幻想(自分だけのCPU, アドレス空間)を提供する

アドレス空間は、プロセスごとの page table (or `maps`): virtual addr -> phys addr により実装. high address (>= 0x80000000 = KERNBASE = 2GB)には kernel 用のメモリが置かれる。

(high address を上に書いている)

```text
-------------------- <- 0xFFFFFFFF |
| kern memory      |               |
--------------------               |
| kern text & data |               |  kernel 用
-------------------- <- 0x80100000 |
| BIOS             |               |
-------------------- <- 0x80000000 |
| heap             |
--------------------
| stack            |
--------------------
| user text & data |
-------------------- <- 0x0
```

kernel を同じアドレス空間にマップしているのは、system call のときに 単に entry point に飛べ、また kernel が user のメモリを読めるように。

## Process

process の状態は、struct proc `p` により表される

- page table - `p->pgdir`
- kernel stack - `p->kstack` (kernel stack のlowest address)
- run state - `p->state`
    - allocated (EMBRYO)
    - ready to run
    - running
    - waiting I/O - kernel のデバイス待ち
    - exiting

kernel stack は実装的には、プロセスごとに kalloc で1ページ割り当てられる

## Initial process
 
順をおってみていく

- boot loader
- `entry` に飛ぶ. ここではページングをセットアップ
    - まだ仮想アドレスはないので、lower address (0x100000 = 1MB) にカーネルを置く
        - ちなみに 0x0 - 0x100000 は memory mapped I/O に使われている
    - page table を設定
        - 0:4M -> 0:4M
        - KERNBASE:KERNBASE+4M -> 0:4M
    - %cr3 <- page table の physical address
    - %cr0 <- CP0_PG (paging を有効化)
    - %esp を high address におき、high address version の main に飛ぶ (long jump)
- `main`. 最初のプロセスを作る
    - 色々なサブシステム（e.g. file system）をセットアップ
    - `userinit`
        - 最初のプロセス initproc が普通のプロセスのように動くよう下準備
            - 上の図っぽくなるようにセットアップ (Chapter 2,3)
            - initcode.S を 0 に貼り付け
            - trap frame (user 空間にもどるときに restore されるやつ) をセットアップ
            - %cs をセット -> レベル3 のユーザプロセスは PTE_U bit のないページや、%cr3 などの重要なレジスタにアクセスできなくなる。
        - `allocproc`
            - これは、fork() でも(ようするにすべてのプロセスに対して)呼ばれる
            - process table に struct proc を割り当てる
                1. 一番最初の UNUSED な slot を見つける
                1. state を EMBRYO にして pid を割り当て
                1. kernel stack を確保し割り当て (失敗したら手順を rollback)
            - その slot が実行可能なように状態をセットアップする ... (*)
            - state を RUNNABLE にする
            
(*) の詳細
kernel stack を以下のようにする (high address が上。stack は下に伸びる)

```text
--------------------
| trap frame       |  (割り込み時の process の context)
|                  |  eip は init process では 0 (forkedならforkの次)
-------------------- <- p->tf
| `&trapret`       |
-------------------- <- end of p->context
| eip = `&forkret` |
--------------------
| ...              |
--------------------
| edi              |
-------------------- <- p->context
| (empty)          |
-------------------- <- p->kstack
```

1. `swich` (コンテキストスイッチ) により、p->context が restore され、それにより forkret に飛ぶ
2. forkret からの ret で、trapret に飛ぶ
3. trapret は trap frame をもどし、user コンテキストにもどる

trap frame は、最初のプロセスだけ `userinit` でセットアップする。fork の場合は親からコピーされるのでよい。

- `main` の最後で、`mpmain` が呼ばれる
    - `schduler`
        - p->state が RUNNABLE なのを見つける (ただ一つ. initproc)
        - per cpu variable である `cpu->proc` に initproc をセット
        - `switchuvm` (switch to user virtual memory?)
            - hardware がこのプロセスの page table を使うようにする
            - TSS を設定 (chapter 3)
        - state <- RUNNING
    - `swtch` (chapter 5)
        - `cpu->scheduler` にレジスタを退避
        - load `p->context`
        - さっき store した eip = forkret が始まる
    - `forkret`
        - 最初の実行でのみ必要な初期化
    - `trapret`
        - trap frame の restore
    - `initcode.S`: 0 に map されていたコードが走り始める
        - `/init` を `exec` (chapter 2) する
    - `Init`
        - fd 0,1,2 をconsole device にひもづけ、shell を立ち上げる。

以上で、システムが立ち上がった。

## Misc

mpmain はすべての CPUで呼ばれるので、multi processor main の略っぽい