xv6実装の詳解(マルチタスク処理 switching編)

# はじめに

xv6とはUnix V6のx86(32bit)実装の教育用OSです。[第一回目の記事](https://qiita.com/knknkn1162/items/9bd54e165c6c9edca49b)でxv6のソースコードリーディングをお勧めしたのですが、[前回のboot処理](https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1)に引き続きソースコードの解説をしたいと思います！ 本記事はswitchingがどう実装されているかの解説記事です。

# 目次

+ 何がOS実装の理解を難しくしているのか
  + [xv6ソースコードリーディングの勧めとGNU assemblyのポイント](https://qiita.com/knknkn1162/items/9bd54e165c6c9edca49b)
+ xv6実装の詳解
  + [boot処理編: segmentationとpagingを中心に](https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1)
  + マルチタスク処理編 
      + switching <= 本記事はココ
      + [interrupt](http://cstmize.hatenablog.jp/entry/2019/03/20/xv6%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AEException%E3%81%A8Interrupt%E3%81%AE%E6%8C%99%E5%8B%95)

Note) switchingの記事、2018/11時点ではあんまり需要なさそうので、この次のinterruptについての記事はcontribution数が相当増えない限り、多分公開しない予定です。 -> (2019/3) 簡単にまとめました http://cstmize.hatenablog.jp/entry/2019/03/20/xv6%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AEException%E3%81%A8Interrupt%E3%81%AE%E6%8C%99%E5%8B%95

# 準備

https://github.com/mit-pdos/xv6-public の準備をしておきます。

```.rb:Vagrantfile
# -*- mode: ruby -*-
# vi: set ft=ruby :
Vagrant.configure("2") do |config|
  config.vm.box = "ubuntu/trusty32"
  config.vm.synced_folder ".", "/home/vagrant/shared"
end
```

のち、`vagrant up && vagrant ssh`でubuntuに入ったのち、

```bash
# バージョン固定せずにかなりラフにinstallしても動くようだ。本記事ではqemuは使用しないので、インストールしていない
$ sudo apt-get install build-essential gdb libgmp3-dev libmpfr-dev libmpfr4 libmpfr4-dbg mpc
$ git clone https://github.com/mit-pdos/xv6-public
$ cd shared/xv6-public
# もし、動作確認したければ、以下のようにする
$ sudo apt-get install qemu
# Makefile参考に
$ make qemu
```

あと、kernel実行バイナリを得るために以下のコマンドでファイルを生成します：

```bash
# Makefile使用する
make kernel
# objdump -S kernel > xv6_kernel.asm
readelf -s kernel > kernel_readelf_s.log
```

`make kernel`の出力結果と、`kernel_readelf_s.log`は kernel_readelf_s.logは https://gist.github.com/knknkn1162/09e9a8c12e0a4ea0db07deb1d7bb4c19 に置いときました。

## 参考リンク

+ [Intel® 64 and IA-32 Architectures Software Developer’s Manual(SDM) vol.3 (Order Number: 325384-067US May 2018)](https://www.intel.co.jp/content/www/jp/ja/architecture-and-technology/64-ia-32-architectures-software-developer-system-programming-manual-325384.html) (公式) 本記事では `Intel SDM vol.3`と略します

+ `%eip`と`%esp` レジスタの挙動について(第一回目の記事)

+ The Linux Programming Interface(TLPI) .. ch.14 file system関連での参考文献としてあげました

# マルチタスク処理とswitchingとinterruptの関係

マルチタスク処理とは複数のprocessをあたかも同時並行に動かす処理です。実際には、1~10ms単位でCPUが複数のprocessを切り替えることで、OS使用者にとって同時に動いているように見せます。

この切り替わるタイミングですが大きく分けて二つあります：

+ RUNNINGの状態のprocessが`wait`や`exit`することにより、状態が切り替わるとき

+ timerによるinterruptで強制的に別のprocessに切り替えるとき

前者は、別のRUNNBALEの状態のprocessを動かしたいので、スループット向上のため、現行のprocessを左記のprocessに切り替えます。
後者は、もし同じprocessのままで、いつまでも切り替わらなかった場合、そのprocessが終了するまで、OS使用者は他のアクションができずに待たされることになります(カーソルが:hourglass_flowing_sand:マークになる) これでは不便なので、ある一定の時間が経過したら強制的に(といっても今までの設定を保存して)別のprocessの作業に切り替えます。

雑に言うと、この切り替わりの動作のことをswitchingと言い、別の要因(この例だとtimer)による中断をinterruptと言います。

switchingする際には、ざっくり

1. 古い方のprocessの設定を保存し、
2. 新しい方のprocessの設定を復元する(中断したものが再開するので)

必要があります。なので、init processが動作するまでをゴールに

1. switchingする前はなにがどうなっているのか
2. switchingする直前と直後はどうなっているのか(registerの内容の保存、復元を行うわけですが..)
3. switchingした後はどうなるのか

と言う感じで、その時歴史が動いた的なストーリーでお話ししたいです:earth_asia:

interruptについては、APIC(Advanced Programmable Interrupt Controller)の話からする必要がありそうで、かなり長くなりそうなので、別の記事にまとめたいと思います！

# 全体の流れ

この記事では、特に`swtch`関数から、`%eip`と`%esp`が活躍しまくります。
この2つのregisterの意味合いについて把握していないと、ほとんど意味不明になってしまいますので、あまりよくわかっていない方は[第一回目の%espと%eipの記事](https://qiita.com/knknkn1162/items/9bd54e165c6c9edca49b#esp%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF%E3%81%A8eip%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF)に目を通しておいてください。(完全に理解していても多分初見では混乱すると思います...)

```
entry.S:
  - (scheduler processの)stack領域と%espを設定
main.c:
  kinit2():
    - 2GB+4MB~のkernel spaceを使用可能(free)にしておく
  seginit():
    - kernel spaceとuser spaceを権限的に分けたいのでGDTを再設定し、その先頭アドレスをレジスタ(GDTR)にロード
  userinit():
    allocproc():
      - process tableから使用されていないprocessを選択(これがinitcode.Sを実行するためのprocessとなる)
      - 上のprocessをprocAと呼ぶことにする。
      - procAのstack領域(4096byte)を確保
      上で確保したstack領域のconfiguration:
        - swtch()からforkret()に飛べるような細工をする
        - forkret()からtrapret()に飛べるような細工をする
    setupkvm():
      - procAのkernel領域のpagingの設定
    inituvm():
      - procAのためにinitcodeのバイナリを展開させておく
    procAのconfiguration:
      - ここで、trapret()からinitcode()に飛べるような細工をしている
    - procAの状態をRUNNABLEにしておく
  mpmain():
    scheduler():
      - realmodeの最初からOFFにし続けていたinterruptを有効にしておく
      - process tableのうちRUNNABLEの状態のprocessを選択
      - procAが選択されたとする
      switchuvm():
        interrupt(主に`int $T_SYSCALL`)が生じた場合のkernel modeへのrestore設定:
          - TSS(Task State Segment) DescriptorをGDTのentry内に設定
          - TSSの設定
          - TSSをTR(Task Register)にロード
        - procAのpaging設定を`%cr3`にロード
      - procAの状態をRUNNINGにしておく
      - (*ZZ) swtchが呼ばれる(call)直前、swtch関数の直後のaddressがstackに積まれることに注意)
      swtch():
        - registerの保存(scheduler processのstack領域にpush)
        - %espをscheduler processのstack領域からprocAのstack領域内に移動させる
        - procAのstack領域で保存されていた値をregisterに復元(pop)させる
        - `ret` instruction実行でforkretに飛ぶ
      forkret():
        - (inodeのinitialization)
        - returnの直前の%espはtrapretのaddressが入っているので、関数のreturnでtrapretにjump
      trapret():
        - 保存されていたregister(%es, %fs, %gs, %ds)を復元しておく
        - `iret`intruction実行で%eip(initcode関数のaddress), %cs, %eflags, %esp, %ssが復元され、initcodeにjump
      initcode():
        - sys_execを実行するために、(`exec("init", ["init", 0]`となるように)引数を設定
        - `int $T_SYSCALL(=60)`の実行  
        => (ここからはinterruptの記事で解説しますが、init processの実行までを[`initcode.S`の`int $T_SYSCALL`が実行された後]の節にて見届けてます      
```

「細工」と言っているのはstack領域に関数へのpointerを積むことで、数ステップ後のreturn時にその積まれた関数が発動するので、そう呼んでいます(専門用語ではない) 
ソースコードを追っていくと実感するのですが、ぷよぷよの不定形連鎖っぽく繋がっていく感じです:curry:

## `initcode.S`の`int $T_SYSCALL`が実行された後

　`initcode.S`の`int $T_SYSCALL`が実行された後はinterruptの記事で詳しくするつもりですが、ざっくり追っておくと、

```
1. int呼び出しによるhardware処理 (https://pdos.csail.mit.edu/6.828/2018/xv6/book-rev11.pdf のCh.3 X86 protectionを参照のこと)
2. alltraps
3. trap
4. syscall
5. sys_exec
6. exec
7. execがreturn
8. sys_execがreturn
9. syscallがreturn
10. trapがreturn
11. 3が終了したので、alltrapsの最後(`iret`)までを実行
12. init program codeのentry pointにジャンプ
```

で、init processが動き出します。後は、initがforkして、

+ 親プロセスがZOMBIE状態のprocessを処理

+ 子プロセスがexecを介してshell実行

すると言う流れです。この部分はinterrupt の回の時にお話したいです！

## scheduler関数の再開

その後、`wait()`や`exit()`やTimerによるinterruptなどで`sched`関数が呼ばれ、(*ZZ)の影響で、schedulerを実行している関数に飛びます：

```
- (schedが呼び出される前にprocessの状態がRUNNING以外の状態となっている)
sched():
  - swtchを呼び出し
swtch():
  - registerの保存
  - %espをscheduler processのstack領域からprocAのstack領域内に移動させる
  - (*ZZ) のため、`ret` instruction実行でschedulerのswtch実行直後に飛ぶ
schedulerのswtichkvm():
  - schedulerのprocessのpage directoryを`%cr3`(page directoryの場所を格納しておくためのregister)にロード
  - schedulerのforが終わる
  - schedulerがprocess tableからprocessがRUNNABLEのprocessを選択する(これをprocBとしよう)
  - swtch実行
swtch():
  - registerの保存
  - %espをscheduler processのstack領域からprocAのstack領域内に移動させる
  - `ret` instruction実行でprocBに飛ぶ
```


となります。(ここは本記事で(interruptを避けつつ)紹介します!)

ということでみたらわかるのですが、今回の記事も死ぬほど詳しく書きましたので、めっちゃ長いです:innocent:


# switchingする前はなにがどうなっているのか

この章では`entry.S`から`main > mpmain > scheduler > swtch`関数の直前まで追っていきたいと思います。

## entry.S

```.as:entry.S
# # Entering xv6 on boot processor, with paging off.
# .globl entry
# entry:
  # Set up the stack pointer.
  # mov    $0x801020c0,%esp
  movl $(stack + KSTACKSIZE), %esp

  mov $main, %eax
  jmp *%eax

// declares a common symbol named symbol. (static allocation which size is KSTACKSIZE=0x1000=4096byte)
.comm stack, KSTACKSIZE
```

どこからスタート? なんですが、stack領域が用意されて、stackの一番上のaddressの値`%esp` registerに格納されるところから、スタートです。このstackが後のschedulerを実行させるときのstack領域となります。

<img width="258" alt="スクリーンショット 2018-09-23 14.58.17.png" src="https://qiita-image-store.s3.amazonaws.com/0/133922/8c1689ea-7968-2cca-7eb4-8dbd0044b0ec.png">

## main()

### kinit2()

この関数では、2GB+4MB~のkernel spaceを使用可能状態にします。
kinit1()では、page directoryやpage tableの領域確保のために必要と思われる領域だけを使用可能状態にしていたのですが、各種初期設定が完了しているので、使用可能な領域を広げます。(page directoryなどに関しては[前の記事](https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#4k-byte-paging%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)にて詳しく説明しているので、参照してください)

### seginit()

seginitに関しては、 https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#seginit で説明しているので、そちらをご覧ください(独立して読める話になっています)

図としてはこんな感じ：

![スクリーンショット 2018-09-26 12.38.56.png](https://qiita-image-store.s3.amazonaws.com/0/133922/d9061d5a-5f39-d21c-d3a1-7713f58f12be.png)

(`%esp`の位置については、entry.Sで用意されたstack領域内にあること以外は、どの位置にあるかの関心は現状あまりないので、適当につけています。`cpus[k]`の`k`は適当な添字)

図には示しませんが、`%cs`や`%ds` registerは`1<<3`, `2<<3`となります。(`%cs`, `%ds` registerについては、　https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#cscode-segment-register-dsdata-segment-register%E3%82%92%E8%A8%AD%E5%AE%9A を参照してください)

`cpus`は`struct cpu cpus[NCPU];`と定義されていて、global変数です。

以下、模式図と言うことで、相対的な長さ、縮尺に関しては気にしないでください:eyes:

### userinit()

userinitは

```proc.c
userinit(void)
{
  struct proc *p;
  extern char _binary_initcode_start[], _binary_initcode_size[];

  p = allocproc();
  
  // static struct proc *initproc;
  initproc = p;
  // ASet up kernel part of a page table.
  if((p->pgdir = setupkvm()) == 0)
    panic("userinit: out of memory?");
  // B. Load the initcode into address 0 of pgdir.
  inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size);
  // configure procA
  // 省略
  acquire(&ptable.lock);
  p->state = RUNNABLE;
  release(&ptable.lock);

}
```

なので、以下の小節では、

+ `_binary_objfile_start`と`_binary_objfile_size`について

+ `allocproc`
+ `setupkvm`
+ `// configure procA`以下のコード
+ procAの状態を`RUNNABLE`に切り替える


部分についての説明をしたいと思います！

#### `_binary_objfile_start`と`_binary_objfile_size`について

`userinit`にある`_binary_initcode_start`や`_binary_initcode_size`という謎の変数が急に登場しています。externなので、どこか外部から引っ張ってきているみたいです。

[準備の節]()で作成した、[kernel_readelf_s.log](https://gist.github.com/knknkn1162/09e9a8c12e0a4ea0db07deb1d7bb4c19)を見ると、

+ `_binary_initcode_start` は https://gist.github.com/knknkn1162/09e9a8c12e0a4ea0db07deb1d7bb4c19#file-kernel_readelf_s-log-L451 に
+ `_binary_initcode_size`　は https://gist.github.com/knknkn1162/09e9a8c12e0a4ea0db07deb1d7bb4c19#file-kernel_readelf_s-log-L472 に

あるようです。

さらに、`make kernel`の出力を見て見ると、 

```.bash:
gcc -fno-pic -static -fno-builtin -fno-strict-aliasing -O2 -Wall -MD -ggdb -m32 -Werror -fno-omit-frame-pointer -fno-stack-protector -nostdinc -I. -c initcode.S
ld -m    elf_i386 -N -e start -Ttext 0 -o initcode.out initcode.o
# -S: Do not copy relocation and symbol information from the source file.(strip-all)
# -O: Write the output file using the object format bfdname. objcopy can be used to generate a raw binary file by using an output target of binary (e.g., use -O binary).
objcopy -S -O binary initcode.out initcode
ld -m    elf_i386 -T kernel.ld -o kernel entry.o bio.o console.o exec.o file.o fs.o ide.o ioapic.o kalloc.o kbd.o lapic.o log.o main.o mp.o picirq.o pipe.o proc.o sleeplock.o spinlock.o string.o swtch.o syscall.o sysfile.o sysproc.o trapasm.o trap.o uart.o vectors.o vm.o  -b binary initcode entryother
```

とあり、`objcopy -S -O binary initcode.out initcode`からinitcode raw binaryを抜き出しています。と言うことで、最後の行の`ld -o kernel -b binary initcode`で、`_binary_initcode_start`や`_binary_initcode_size` を生成していることがわかります。

`_binary_objfile_start`や`_binary_objfile_size`の記述は`man ld`にはなく、`objcopy -B`にあるようで、`man objcopy`によれば、

```
-B bfdarch
--binary-architecture=bfdarch
  Useful when transforming a architecture-less input file into an object file.
In this case the output architecture can be set to bfdarch.  
This option will be ignored if the input file has a known bfdarch.  
You can access this binary data inside a program by referencing the special symbols that are created by the conversion process.  
These symbols are called _binary_objfile_start, _binary_objfile_end and _binary_objfile_size.  
e.g. you can transform a picture file into an object file and then access it in your code using these symbols.
```

とのことです[^objcopy]。

[^objcopy]: https://stackoverflow.com/a/29035523 あたりを参考にしました

#### allocproc()

##### process tableから使用されていないprocessを選択

```proc.c
struct {
  struct spinlock lock;
  // #define NPROC        64  // maximum number of processes
  struct proc proc[NPROC];
} ptable;

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:
  // in the early stages of growth
  p->state = EMBRYO;
  p->pid = nextpid++;
```

ここの部分は、`UNUSED`の状態のprocessを選択する部分です。ptableはglobal変数なので、静的に領域が確保されています。
ここで、選択されたprocess(変数`p`)を以下`procA`と呼ぶことにします。(`struct proc`の内容は、https://github.com/mit-pdos/xv6-public/blob/b818915f793cd20c5d1e24f668534a9d690f3cc8/proc.h#L37-L52 のような感じ。)

ちなみに`EMBRYO`というのは`胎芽、胚`という意味みたいです(very early stage of the process)。

##### procAのstack領域の構成

ここから、procAのstack領域の構成です。図とコードの対応関係は以下のような感じ(図の番号がコード内の番号に対応しています)：

```
1: kallocでprocAのstack領域を確保する
2: procAのstack領域の最上部にstruct trapframeを配置する
3: 2の下にtrapret(コレはtrapasm.Sで定義された関数のaddress)を設定する。(ここで、forkret()からtrapret()に飛べるような細工をしている。)
4: 3の下にstruct contextを配置する。
5: ここで、swtch()からforkret()に飛べるような細工をする
```

![スクリーンショット 2018-10-01 12.31.27.png](https://qiita-image-store.s3.amazonaws.com/0/133922/6ae1ab49-4989-04fa-f850-48464391ea6d.png)


`ptable`はglobal変数で、以下のような構造をしています(変数`i`は適当な添字です)：

```proc.c
struct {
  struct spinlock lock;
  // #define NPROC        64  // maximum number of processes
  struct proc proc[NPROC];
} ptable;
```

2~4は変数`sp`の移動により[`struct trapframe`](https://github.com/mit-pdos/xv6-public/blob/b818915f793cd20c5d1e24f668534a9d690f3cc8/x86.h#L150-L183)や[`struct context`](https://github.com/mit-pdos/xv6-public/blob/b818915f793cd20c5d1e24f668534a9d690f3cc8/proc.h#L27-L33)の配置を実現していることがポイントです。

```proc.c
// allocproc()の続き
  // Allocate kernel stack.
  // 1. kallocでprocAのstack領域を確保する
  if((p->kstack = kalloc()) == 0){
    p->state = UNUSED;
    return 0;
  }
  sp = p->kstack + KSTACKSIZE;

  // Leave room for trap frame.
  sp -= sizeof *p->tf;
  // 2. procAのstack領域の最上部にstruct trapframeを配置する
  p->tf = (struct trapframe*)sp;

  // Set up new context to start executing at forkret,
  // which returns to trapret.
  sp -= 4;
  // 3. 2の下にtrapret(コレはtrapasm.Sで定義された関数のaddress)を設定する。
  // ここで、forkret()からtrapret()に飛べるような細工をしている。
  *(uint*)sp = (uint)trapret;

  sp -= sizeof *p->context;
  // 4. 3の下にstruct contextを配置する。
  p->context = (struct context*)sp;
  memset(p->context, 0, sizeof *p->context);
  // 5. ここで、swtch()からforkret()に飛べるような細工をする
  p->context->eip = (uint)forkret;

  return p;
}
```

細工の部分については、その段になったら説明しますが、2週目にこの記事を読むときはちょっと気を払う感じで。

#### setupkvm()

この関数は実は、[boot処理の `kvmalloc()`で登場](https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#kvmalloc%E3%81%AE%E5%8B%95%E4%BD%9C)しているのですが、再度説明します。
page tableやpage directoryなどの用語に関しては、説明なく使っていきますので、よくわからない方は、前の記事の https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#4mbyte%E3%81%AEpaging%E3%82%92%E8%A8%B1%E5%8F%AF から読み始めるか、適宜ほかのサイトを確認してください。

今の所、`kvmalloc`で反映した4K-Byte pagingが反映されています：

> <img width="744" alt="68747470733a2f2f71696974612d696d6167652d73746f72652e73332e616d617a6f6e6177732e636f6d2f302f3133333932322f62653231333634372d393464312d643930392d363530342d6130396234653339623763662e706e67.png" src="https://qiita-image-store.s3.amazonaws.com/0/133922/0b2e4869-0261-69d9-0bf6-693950496aa7.png">
> Intel SDM vol.3 ch.4 Pagingより引用

`userinit`の`setupkvm`でやることは、procAに関するkernel spaceのpagingを設定することです。そのために、page directoryを作成します。
(その後、CPUがこのプロセスを`RUNNING`させる直前[(`main > scheduler > switchuvm`関数内にある)](https://github.com/mit-pdos/xv6-public/blob/1d19081efbb9517d07c7e6c1a8393c6343ba7817/vm.c#L176)に`%cr3` register(`Page Directory Base Register(PDBR)`)を再設定します。

注意) 現在のpagingは、`main > kvmalloc > setupkvm`が`switchkvm();`(`%cr3`にロード)によって、設定されている点に注意してください。

```vm.c
pde_t*
setupkvm(void)
{
  pde_t *pgdir;
  struct kmap *k;

  // // Allocate one 4096-byte page of physical memory.
  // At that time,
  if((pgdir = (pde_t*)kalloc()) == 0)
    return 0;
```

この部分で、page directoryの領域(4*1024byte)を確保します。

```vm.c
// setupkvm(void)の続き:
  memset(pgdir, 0, PGSIZE);
  // #define DEVSPACE 0xFE000000         // Other devices are at high addresses
  // #define PHYSTOP 0xE000000           // Top physical memory
  if (P2V(PHYSTOP) > (void*)DEVSPACE)
    panic("PHYSTOP too high");
  for(k = kmap; k < &kmap[NELEM(kmap)]; k++)
    // mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
    if(mappages(pgdir, k->virt, k->phys_end - k->phys_start,
                (uint)k->phys_start, k->perm) < 0) {
      freevm(pgdir);
      return 0;
    }
  return pgdir;
}
```


後半の`mappages`(`walkpgdir`が本質的な仕事をしている)で、paging設定の作成を行います。`kmap`は

```vm.c
static struct kmap {
  void *virt;
  uint phys_start;
  uint phys_end;
  int perm;
  /*
    0x80101000                . = ALIGN (0x1000)
    [!provide]                PROVIDE (data = .)
   */
} kmap[] = {
 // #define EXTMEM=0x00100000
 // ##define KERNBASE 0x80000000         // First kernel virtual address
 { (void*)KERNBASE, 0,             EXTMEM,    PTE_W}, // I/O space (0x80000000 ~ 0x80100000)
 // #define KERNLINK (KERNBASE+EXTMEM)=0x80100000  // Address where kernel is linked
 { (void*)KERNLINK, V2P(KERNLINK), V2P(data), 0},     // kern text+rodata (0x80100000 ~ 0x80102000)
 { (void*)data,     V2P(data),     PHYSTOP,   PTE_W}, // kern data+memory (0x80102000 ~ 0x8E000000)
 // #define DEVSPACE 0xFE000000         // Other devices are at high addresses
 { (void*)DEVSPACE, DEVSPACE,      0,         PTE_W}, // more devices (0xFE000000 ~ 0xFFFFFFFF)
};
```

以下のような変数です。kernel spaceでのpaging設定は`kmap`という変換式に基づいており、全てのprocessで共通なのですが、user spaceではprocessごとにpagingの設定が異なります。この点については、 https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#kernel-space%E3%81%A8user-space%E3%81%AEpaging を参照してください。

結局、`p->pgdir = setupkvm()`のように格納された状態の図は以下のようになります(といっても、前回との差分はprocAに上記で設定したpagingの設定を結びつけているだけです)：

![スクリーンショット 2018-10-01 12.34.43.png](https://qiita-image-store.s3.amazonaws.com/0/133922/b099c774-3bc8-ba97-2a01-ea654b99353f.png)



#### inituvm()

主にやることは2つあり、

1. `mappages(pgdir, 0, PGSIZE, V2P(mem), PTE_W|PTE_U);`でvirtual addressの**user space**`[0~4096byte)`をphysical addressの`[V2P(mem), V2P(mem)+4096)`にmappingさせるようにpagingを設定する

2. `memmove(mem, init, sz);`でvirtual addressの**kernel space**`[mem, mem+4096)`に `_binary_initcode_start` ~ `_binary_initcode_start + _binary_initcode_size`までのbinaryをmoveしておく。

です。

1.のmemは`mem = kalloc()`で動的に確保した領域で4096byteです。

2で、virtual address: `[mem, mem+4096)`はkernel領域なので、physical addressでは、`[V2P(mem), V2P(mem)+4096)`に対応しており、1番のmappingの設定と一貫性があります。また、initcode.Sを見てもらえればわかるのですが、100行以内のassemblyで明らかに4096byteに収まる(実際には44byteでした[^binary])ので、1page分の使用で十分です。

[^binary]: これは、で作成されたraw binaryファイル`initcode`のサイズです。詳しくは、[`_binary_objfile_start`と`_binary_objfile_size`について](https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c#_binary_objfile_start%E3%81%A8_binary_objfile_size%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)の節を参照にしてください。

#### procAのconfiguration

これは図とコードを対応させた方が良いかなと思います。こんな感じ:


![スクリーンショット 2018-10-01 12.37.29.png](https://qiita-image-store.s3.amazonaws.com/0/133922/9cc55d70-b6a8-f99b-688d-dd8c069581ad.png)



```proc.c
// userinit(void)の続き
  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;
  // #define FL_IF           0x00000200      // Interrupt Enable
  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("/");
```

general registerとは、`%eax`とか`%ebx`とかのことでこの領域はまだ0で初期化されたままです。

cpusについては、`seginit()`で登場しました。
`initcode`の`0~4096`と言うのは、virtual adddressなので、物理memoryの`0~4096`でないことに注意してください。([inituvm()の小節](...)の参照のこと)

#### procAの状態を`RUNNABLE`に

```proc.c
  acquire(&ptable.lock);
  p->state = RUNNABLE;
  release(&ptable.lock);
```

最後にprocAの状態を`RUNNABLE`にすることで、`main > mpmain > scheduler`関数の

```proc.c
void
scheduler(void)
{
  struct proc *p;
  // 中略
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      if(p->state != RUNNABLE)
        continue;
      // このあとswitching処理

```

で拾ってもらえるようにしてます。

##### 排他処理を行う理由

:satellite_orbital: ここのトピックはやや難しいです。

`p->state = RUNNABLE;`の前後で`acquire`と`lock`で包んでいるのは、排他処理する必要があるからですが、

https://github.com/mit-pdos/xv6-public/blob/b818915f793cd20c5d1e24f668534a9d690f3cc8/proc.c#L145-L151 で書いている通り、

```.c:
  // 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);
```

と言うのが理由です。ですが、ちょっと自明ではないので、次の2点について深掘りして見ます。

+ 他のCPUは何をしていて、どう競合が起こる可能性があるのか?

+ なぜ、`p->state = RUNNABLE;`は`might not be atomic.`なのか? 

##### 他のCPUは何していて、どう競合が起こる可能性があるのか?

xv6は https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#%E5%85%A8%E4%BD%93%E3%81%AE%E6%B5%81%E3%82%8C のNote　の部分でも触れたように、MultiProcessorに対応しています。
他のCPUのboot処理からの挙動については、 https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#%E5%85%A8%E4%BD%93%E3%81%AE%E6%B5%81%E3%82%8C のNote)に書いておきましたがざっくり言うと、

1: (BIOSのbootstrap処理前に)BIOSやOSのbootstrap処理が走るCPU(BootStrap Processor: BSPという)が選択される。選択されなかったCPU(Application Processor: APという)は待機。

2-1: `main > startothers > lapicstartap`の[`lapicw(ICRLO, STARTUP | (addr>>12));`](https://github.com/mit-pdos/xv6-public/blob/1d19081efbb9517d07c7e6c1a8393c6343ba7817/lapic.c#L158)にて、APが`entryother.S`を実行してOSのbootstrap処理を行う

2-2: BSPはhttps://github.com/mit-pdos/xv6-public/blob/1d19081efbb9517d07c7e6c1a8393c6343ba7817/main.c#L92-L93 にて待機する

3: APは2-1の続きで[`mpmain > xchg(&(mycpu()->started), 1);`](https://github.com/mit-pdos/xv6-public/blob/1d19081efbb9517d07c7e6c1a8393c6343ba7817/main.c#L56)を実行し、2-2で待機していたBSPを起こす。APはそのまま、止まることなく、`mpmain > scheduler`に突入する

上記の3から、AP(Application Processor)は`mpenter > mpmain > scheduler`の

```proc.c
// scheduler(void)
    // 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;
```

まで突入している可能性があります。この場合、以下の競合が起こる可能性があります。とりあえず、`p->state = RUNNABLE;`はatomicでないのを前提とします。(atomicでない確認は次節で)

[^bsp_ap]: BSPはBootStrap Processor、APはApplication Processorの略です。詳しくは、Intel SDM vol.3 ch.8.4.1 BSP and AP Processors をご覧ください。

```
1. BSPがuserinitの`p->state = RUNNABLE;`を処理し始める
2. APが`p->state != RUNNABLE`でfalseを返し、continueする
3. APが`p->state = RUNNING`を実行する
4. BSPがuserinitの`p->state = RUNNABLE;`を処理し終わり、p->stateにRUNNABLEが代入される
```

もし、こういうことが起こると、`p`の状態がRUNNABLEにも関わらず、CPUによってprocessが実行するため、予期せぬ動作をするでしょう。
実際には、2と3の間に`switchuvm(p)`が挟まれているため、上記のようなことが起こる可能性は限りなく低いのですが、可能性のある限りlockは必要です。

##### なぜ、`p->state = RUNNABLE;`は`might not be atomic.`なのか?

もし、atomicならば、1と4の2つの部分に処理がまたがることはありませんので、lockは不要ですが、実際にはatomicです。

Intel SDM vol.3 ch.8.1.1 Guaranteed Atomic Operations によれば、atomicであるためには32-bit 境界でのメモリの書き込み、読み込みが必要[^xchg]ということで、今回の場合はその保証がないため、アトミックであることが保証できません。なので、`might not be atomic.`というわけでした。

[^xchg]: 例外的に、`xchg` instructionでオペランドの一つがmemory addressだった場合はlockがかかるため、atomicとなります。詳細は、Intel SDM vol.3 ch. 8.1.2.1 Automatic Lockingを参照のこと。

以上2つのことから、`p->state != RUNNABLE`の前後では`acquire`, `lock`が必要となります。よく考えてみれば意外とむずい部分でした:scream:

Note) 「単一のinstructionである」 -> 「その命令はatomicである」、という命題は必ずしも **成り立たない** ことに注意。上記の例だと、`p->state != RUNNABLE`は`c7 43 0c 03 00 00 00 	movl   $0x3,0xc(%ebx)`( https://gist.github.com/knknkn1162/9149a610070a8bd14486c5533def1876#file-kernel-asm-L9917-L9918 )で表現できますが、上の考察で見たようにこのinstruction自体は、atomicではありません。

----

`userinit()`部分がやっと終わったので、続いては少し飛んで`main > mpmain > scheduler`関数を見ていきます！

## mpmain()のscheduler()

部分部分確認していきます：

```proc.c
void
scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();
  c->proc = 0;
  
  for(;;){
    // Enable interrupts on this processor.
    sti();
```

`sti`はinterruptをONにする関数で`sti` instructionと同等です。あとは、Multiprocessor対応なので、`struct cpu *c = mycpu();`で、自身のCPUに対応したstruct cpuをとってきてます。

```proc.c
// scheduler(void)
    // 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;
```

ここは何回か説明した通りですが、`p`の状態が`RUNNABLE`のprocessを探し出しています。このprocessを動作させるわけですね。今回は上記でみたinitcodeを動かすprocessを探してこれたとします[^not_found_runnable]。

[^not_found_runnable]: 実際には、他のCPUが`mpenter > mpmain > scheduler`ときて、このprocessを獲得している場合があるので、`bootasm`から続いてきているCPUでこのprocessが見つからずに,他のRUNNBALEのprocessが訪れるまで`for(;;){`の中身を繰り返す可能性があります。


### switchuvm()

また図とソースコードを対応づけておきます(さらに複雑ですが、ほとんどこれで仕掛けは終わりです:muscle:)：

```
1. cpuのproc構造体と先ほどまで構成していたprocAを結びつける
2. TSS(Task State Segment) DescriptorをGDTのentry内に設定
3. TSSの設定
4. TSSをTR(Task Register)にロード
5. procAのpaging設定を`%cr3`にロード
6. procAの状態をRUNNABLEからRUNNINGに切り替える
```

![スクリーンショット 2018-10-01 12.47.14.png](https://qiita-image-store.s3.amazonaws.com/0/133922/213c0c40-9a07-cfae-28b9-9266777a89e4.png)


```proc.c
// schedulerの中身のつづき
      // 1.cpuのproc構造体と先ほどまで構成していたprocAを結びつける
      c->proc = p;
      // 2~5: 下記を参照
      switchuvm(p);
      // 6. procAの状態をRUNNABLEからRUNNINGに切り替える
      p->state = RUNNING;
```

```vm.c
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();
  // 2. TSS(Task State Segment) DescriptorをGDTのentry内に設定
  // #define SEG_TSS   5  // this process's task state
  // #define SEG16(type, base, lim, dpl) (struct segdesc)
  // #define STS_T32A    0x9     // Available 32-bit TSS
  mycpu()->gdt[SEG_TSS] = SEG16(STS_T32A, &mycpu()->ts,
                                sizeof(mycpu()->ts)-1, 0);
  //   uint s : 1;          // 0 = system, 1 = application
  mycpu()->gdt[SEG_TSS].s = 0;
  
  // 3. TSSの設定
  //   struct taskstate ts;         // Used by x86 to find stack for interrupt
  mycpu()->ts.ss0 = SEG_KDATA << 3;
  // uint esp0;         // Stack pointers and segment selectors
  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;
  //0x101 << 3
  //  asm volatile("ltr %0" : : "r" (sel)); // Load Task Register
  // The contents of Task register is segment selector. See Intel SDM vol.3 Fig2.6 and Ch2.4.4
  // 4. TSSをTR(Task Register)にロード
  ltr(SEG_TSS << 3);

  // 5. procAのpaging設定を`%cr3`にロード
  // asm volatile("movl %0,%%cr3" : : "r" (val));
  lcr3(V2P(p->pgdir));  // switch to process's address space
  popcli();
}
```

冒頭と最後のpushcli/popcliは`cli, sti` instructionの拡張です。 https://github.com/mit-pdos/xv6-public/blob/b818915f793cd20c5d1e24f668534a9d690f3cc8/spinlock.c#L100-L102 を参照すればまぁ良いんじゃないかと。

`5. procAのpaging設定を%cr3にロード`の部分はprocAのpagingの設定を`%cr3`(Page Directory Base Register(PDBR))に反映させている部分です。このregisterに関しては、前回の記事の　https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#page-directory%E3%81%AEaddress%E3%82%92%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF%E3%81%AB%E3%83%AD%E3%83%BC%E3%83%89 に書いています。

その他の、`2. TSS(Task State Segment) DescriptorをGDTのentry内に設定`と、`3. TSSの設定`ですが、ここは、`initcode`が`int $SYS_CALL`を呼び出したときに効いてくる部分なので、ここの部分はinterruptの記事に回します！(大事な箇所ではありますが...)

準備が終わっていよいよ`swtch`関数ですが、switchingの本質的な関数となります。

# switchingする直前と直後はどうなっているのか

ここでは、`%esp`(stack pointer)がダイナミックに移動する部分ですので、特に`%esp`に注目してください:eye:

## swtch

いよいよswtchです:sunglasses: とは言ってもここまで丁寧に追ってきたので、switching自体はむずくありません。ここから`entry.S`で用意されたstackの挙動を追っていきます。

```proc.c
// scheduler関数の中身の続き
      // void swtch(struct context **old, struct context *new);
      swtch(&(c->scheduler), p->context);
```

### switching前夜

swtch関数は引数ありなので、引数がstackに積まれます。詳しくは、このシリーズの最初の記事の https://qiita.com/knknkn1162/items/9bd54e165c6c9edca49b#%E5%BC%95%E6%95%B0%E3%82%92%E6%8C%81%E3%81%A4%E5%A0%B4%E5%90%88 に書いています。
重要なのが、```switchkvm(); // switch page table```へのaddressをstackに積んでいることです。

これがあるため、[scheduler関数の再開](https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c#scheduler%E9%96%A2%E6%95%B0%E3%81%AE%E5%86%8D%E9%96%8B)でもちらっとみたように、scheduler関数に戻れるのでした。詳しくは[sched関数の呼び出し ~ swtch呼び出し ~ scheduler関数の再開までの章](https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c#sched%E9%96%A2%E6%95%B0%E3%81%AE%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97--swtch%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97--scheduler%E9%96%A2%E6%95%B0%E3%81%AE%E5%86%8D%E9%96%8B%E3%81%BE%E3%81%A7)で解説します。

図とコードを対応させると、こんな感じ：

```
0. `swtch(&(c->scheduler), p->context);`で呼ばれるので、引数とreturn先のaddressがstackに積まれる
1. 第一引数を取り出す
2. 第二引数を取り出す
3. 現在のregisterを保存する
```

![スクリーンショット 2018-10-01 12.40.00.png](https://qiita-image-store.s3.amazonaws.com/0/133922/709f3970-10b3-15e7-1629-a6b3cf1699ad.png)




```.as:swtch.S
// 0. `swtch(&(c->scheduler), p->context);`で呼ばれるので、引数とreturn先のaddressがstackに積まれる
// #   void swtch(struct context **old, struct context *new);
.globl swtch
swtch:
  // 1. 第一引数を取り出す
  movl 4(%esp), %eax
  // 2. 第二引数を取り出す
  movl 8(%esp), %edx

  // 3. 現在のregisterを保存する
  pushl %ebp
  pushl %ebx
  pushl %esi
  pushl %edi
```

+ 第一引数は`struct context**`、第二引数は`struct context*`なので、橙色で指し示した部分になります。
(第二引数の矢印の先に注意。もし、`&procA->context`だと、型が`struct context**`になってしまう)

+ `swtchuvmへのpointer`を`eip`メンバと解釈すれば、上図の`%esp`は`struct context*`のアドレスにちょうど対応しています。というより、そうなるように、汎用registerをstackにpushしたのでした。

+ swtchを呼んだ(`call` instructionに対応)ので、以下のようにその次のinstructionへのpointer(下記でいうと、`call swtichkvm`を指し示すアドレス(`0x801039e0`))がstackに積まれています([sched関数の呼び出し ~ swtch呼び出し ~ scheduler関数の再開まで](https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c#sched%E9%96%A2%E6%95%B0%E3%81%AE%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97--swtch%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97--scheduler%E9%96%A2%E6%95%B0%E3%81%AE%E5%86%8D%E9%96%8B%E3%81%BE%E3%81%A7)の章でこの部分が重要になります)：

```.as:
// https://gist.github.com/knknkn1162/9149a610070a8bd14486c5533def1876#file-kernel-asm-L10302-L10306 より
// 中略
      swtch(&(c->scheduler), p->context);
801039d4:	89 3c 24             	mov    %edi,(%esp)
801039d7:	89 44 24 04          	mov    %eax,0x4(%esp)
801039db:	e8 0b 0b 00 00       	call   801044eb <swtch>
      switchkvm();
801039e0:	e8 6b 2b 00 00       	call   80106550 <switchkvm>
// 省略
```

### switching

たった2行ですが、これも図とコードを番号で対応させましょう：

![スクリーンショット 2018-10-01 12.41.32.png](https://qiita-image-store.s3.amazonaws.com/0/133922/1b2635e4-677a-ff88-076d-fcf7d3cc04ca.png)



```.as:swtch.S
// swtch: の続き
  # Switch stacks
  // 1. entry.Sのstack pointerを自身のcpu構造体の`struct context *scheduler`に保存する
  movl %esp, (%eax)
  // 2. %esp registerをprocAのstack領域内のaddressに書き換える。
  movl %edx, %esp
```

`%esp`が`userinit > allocproc`で用意されたstack領域内に移動しましたね? switchingがこれで完了しました！
自身のcpu構造体の`struct context *scheduler`に古い方のstack pointerの値を保存しています。[sched関数の呼び出し ~ swtch呼び出し ~ scheduler関数の再開まで](https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c#sched%E9%96%A2%E6%95%B0%E3%81%AE%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97--swtch%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97--scheduler%E9%96%A2%E6%95%B0%E3%81%AE%E5%86%8D%E9%96%8B%E3%81%BE%E3%81%A7)の章にて`%esp`がこの保存されたstack pointerのaddressにrestoreします。



### switching完了後

switchingは理解できたでしょうか。あとは、新しいprocessの`%esp`上のstack領域で、registerを復元しつつ、`%esp`を *引き上げる*だけです：

![スクリーンショット 2018-10-01 12.52.01.png](https://qiita-image-store.s3.amazonaws.com/0/133922/5b740f40-1fd6-4e30-5f0a-d2cff10d1e60.png)



```.as:swtch.S
// swtch: の続き
  // 1. registerを復元する(結果的に`%edi=%esi=%ebx=%ebp=0`となり、`0`に初期化される。
  popl %edi
  popl %esi
  popl %ebx
  popl %ebp
  // 2. `%eip`に`forkret`関数へのaddressをpopして、`%eip`のaddress先(つまりforkret関数)にjump!!
  ret
```

[sched関数の呼び出し ~ swtch呼び出し ~ scheduler関数の再開まで](https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c#sched%E9%96%A2%E6%95%B0%E3%81%AE%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97--swtch%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97--scheduler%E9%96%A2%E6%95%B0%E3%81%AE%E5%86%8D%E9%96%8B%E3%81%BE%E3%81%A7)の章まで、`entry.S`で用意されたstackは使用しないので、ご退場いただきました。`ret`については、[一番目の記事のhelloの関数化の節](https://qiita.com/knknkn1162/items/9bd54e165c6c9edca49b#hello%E3%81%AE%E9%96%A2%E6%95%B0%E5%8C%96)の`関数が呼ばれる仕組み`を参照してください:ok_hand_tone1:


https://qiita.com/knknkn1162/items/9bd54e165c6c9edca49b#hello%E3%81%AE%E9%96%A2%E6%95%B0%E5%8C%96 の終わりの部分に書いたように、
%espが指し示している部分(`forkret`へのaddress)が%eipにpopされ、`%eip`がそのaddressにjumpするのでした。

これでswitching自体の挙動は説明したのですが、ここからの関数へのジャンプの仕方が、ぷよぷよでいう連鎖の本番なので、この後の挙動もみていきましょう:curry:

ということで、`forkret`へと続きます...

# switchingした後はどうなるのか

switchingし終わったので、procAのstack領域で作業していくことになります。`forkret`にjumpした直後はこんな感じの模式図になっています：

![スクリーンショット 2018-09-27 16.02.41.png](https://qiita-image-store.s3.amazonaws.com/0/133922/90ebed24-574e-88ea-acd8-ac829acd752d.png)


## forkret()

`forkret`はあんまり大したことやっていなくて、inodeの初期化くらいです。inodeについては、The Linux Programming Interfaceのch.14 File Systemを読めば良いかと思います(こちらは、ext2 file systemの文脈ですが)

また、`%eip`にpopして、スタックポインタの`%esp`が引き上がります。`%eip`はtrapret関数へのaddressなので、そこにjumpします！


## `trapret()`

今回は、`%esp`の移り変わりが重要なので、`%esp`の移動と番号を図で対応させておきます：

![スクリーンショット 2018-10-01 12.44.57.png](https://qiita-image-store.s3.amazonaws.com/0/133922/2ce5cee4-cb62-d0e5-8dac-827faac0876b.png)




```.as:trapasm.S
.globl trapret
// 0. (現在の状態)
trapret:
  // 1. general registerを復元(pop)する
  popal
  // 2. %es, %ds, %fs, %gs(segment register達)を復元(pop)する
  popl %gs
  popl %fs
  popl %es
  popl %ds
  // 3. trapnoとerrは無視して、%espを引き上げる
  addl $0x8, %esp  # trapno and errcode
  // 4. %eip, %cs, %eflags, %esp, %ssを復元する。
  // 5. `%eip`はinitcodeへのprogram codeのentrypointであるので、jump!
  iret
  // 6. user 領域でprogram が実行されることになる。(今まで全てkernel領域で作業していた!!)
```

ここでのポイントおよび難所は`iret`です。
`iret`について理解するためには、2つの問いに答える必要があります：

+ `iret`と`ret`はどう違うの?

+ なぜ`trapretでは`ret`を呼び出さないの?

### `iret`と`ret`はどう違う?

`ret`が`call`と対応関係にあるように、`iret`は、interrupt(or exception)呼び出しと対応関係にあります[^iret] interruptの本格的な説明は次の記事あたりでお話ししたいのですが、`iret`と関係ある部分だけ説明します：

[^iret]: Intel SDM vol.3 ch.6.12.1 Exception- or Interrupt-Handler Procedures に　`To return from an exception- or interrupt-handler procedure, the handler must use the IRET (or IRETD) instruction.`とある

`cli`でinterruptがOFFでない限り、いつでもinterruptが呼び出されます[^interrupt_cond]。interrupt呼び出しの直後はhardwareが自動的に以下のことを行います[^interrupt](つまり以下の仕様に関しては**software上でprogramを書く必要はありません**)：

1-1: 現状の`%ss`, `%esp` registerを一時的に退避させておく

1-2: TSS(Task State Segment)に保存されている`%ss`および`%esp`を復元する(`%esp`の変更により、user spaceからkernel spaceに移動している)

2: 1で退避させていた`%ss`と`%esp`をstackに積む(`%esp`は移動)

3: 現状の`EFLAGS`, `%cs`, `%eip` registerをstackに積む

4: (exceptionの場合)error codeがあればそれもstackに積む(今回はinterruptなので積まれない)

[^interrupt_cond]: もちろん、APIC(Advanced Programmable Interrupt Controller)が適切に設定されているのを前提としてる

TSS(Task State Segment)に関しては本記事では説明していませんが、TSS領域内に`%ss`や`%esp`が保存されています[^tss]。
上記の前後ではこんな感じになります：

> <img width="681" alt="スクリーンショット 2018-09-27 22.03.26.png" src="https://qiita-image-store.s3.amazonaws.com/0/133922/c23c810f-8248-50c4-d526-a4bd92362a51.png">
> Intel SDM vol.3 ch.6.12.1 Exception- or Interrupt-Handler Procedures の図より引用

`iret`は`interrupt`でやったことの逆を**hardware**側で自動的に行います。
つまり、interrupt前の状態に戻すため、積まれたstack内のregister(`%eip`, `%cs`, `%eflags`, `%esp`, `%ss`)の値を復元(pop)します。

[^tss]: TSS(Task State Segment)については、Intel SDM vol.3 Figure 7-2. 32-Bit Task-State Segment (TSS) に図があります

[^interrupt]: Intel SDM vol.3 ch. 6.12.1 Exception- or Interrupt-Handler Procedures を参照のこと。本記事では簡単のため、user landからのinterruptを想定している。

### なぜ`trapret`では`ret`を呼び出さないの?

`iret`のセマンティクスについては理解したところで、なぜ`ret`を用いないの?という疑問が起こります。そもそも、`interrupt`は起こっていないので、`iret`を使うのは一見すると変です。

まず、そもそものところから、解決すると、`ret`が`call`と対応関係にある と言いましたが、 https://qiita.com/knknkn1162/items/9bd54e165c6c9edca49b#ret-instruction%E3%81%AE%E5%BF%9C%E7%94%A8 でも書いたように、必ずしも対になって呼ばれる必要はありません。 
これと同様に、`interrupt`呼び出しと`iret` instructionは**必ずしも対になって呼ばれる必要はありません**。かなり不思議な感じがしますが、こういう風に解釈できます。
`call`を呼ばずに`ret`のみを呼び出したときのことは　　https://qiita.com/knknkn1162/items/9bd54e165c6c9edca49b#ret-instruction%E3%81%AE%E5%BF%9C%E7%94%A8 にて書いてありますが、コード部分を再掲します：

```.as:hello.s
// https://qiita.com/knknkn1162/items/9bd54e165c6c9edca49b#ret-instruction%E3%81%AE%E5%BF%9C%E7%94%A8 の例を復元した
.text
  .globl main

main:
  movl $exit, %eax
  pushl %eax
  jmp hello

hello:
  movl $0x04, %eax
  movl $0x01, %ebx
  movl $message, %ecx
  movl $12, %edx # length
  int $0x80
  ret

exit:
  # exit
  movl $0x01, %eax
  xorl %ebx, %ebx
  int $0x80

message:
  .ascii "Hello world\n"
```

`jmp hello`する前に`pushl %eax`でstackに積む動作を行なっています。これは`call hello`相当の必要な準備をhello関数の最後の`ret`のためにする必要がある、という解釈ができます。

これを`interrupt`呼び出しと`iret` instructionの場合に適用すると、`iret`呼び出しの前に`interrupt`相当の必要な準備をtrapret関数の最後の`iret`のためにする必要がある、という解釈ができます。
まぁ、ちょっとまだ気持ち悪い感じはあると思いますが、ニュアンスは伝わったと思います(思いたい..)

そうなると、次の論点は、「`interrupt`相当の必要な準備」って何ですか？ということです。種明かしをすると、ここに仕込んでありました：

```proc.c
// userinit(void) の続き
  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;
  // #define FL_IF           0x00000200      // Interrupt Enable
  p->tf->eflags = FL_IF;
  p->tf->esp = PGSIZE;
  p->tf->eip = 0;  // beginning of initcode.S
  // (省略)
```

```proc.h
struct trapframe {
  // registers as pushed by pusha
  uint edi;
  uint esi;
  uint ebp;
  uint oesp;      // useless & ignored
  uint ebx;
  uint edx;
  uint ecx;
  uint eax;

  // rest of trap frame
  ushort gs;
  ushort padding1;
  ushort fs;
  ushort padding2;
  ushort es;
  ushort padding3;
  ushort ds;
  ushort padding4;
  uint trapno;

  // below here defined by x86 hardware
  uint err;
  uint eip;
  ushort cs;
  ushort padding5;
  uint eflags;

  // below here only when crossing rings, such as from user to kernel
  uint esp;
  ushort ss;
  ushort padding6;
};
```

上のコードにて、復元先の`%eip`, `%cs`, `eflags`, `%esp`, `%ss` registerを設定します。

最後の論点は、なぜ、`ret`でなく`iret`なの? というところですが、これはkernel landからuser landへ移行できるinstructionが`iret` instructionしか存在しないから[^iret_userland]です。`trapret`の直前まで、kernel landで動作していましたが、`initcode`はuser landで動作するコードなので`%cs`やEFLAGS registerの再設定が必要ということで、`ret`でなく`iret`を使用します。

[^iret_userland]: http://jamesmolloy.co.uk/tutorial_html/10.-User%20Mode.html を参考にしました。`The x86 is strange in that there is no direct way to switch to user mode. The only way one can reach user mode is to return from an exception that began in user mode. The only method of getting there in the first place is to set up the stack as if an exception in user mode had occurred, then executing an exception return instruction (IRET).`と書かれています。

-------

かなりむずいと思われますので、わからんかったら、とりあえず、initcodeまで飛べるんやな、と思っていただいて大丈夫です:kissing_smiling_eyes:

#### initcode

initcodeに突入した直後は図のようになります：

![スクリーンショット 2018-09-27 16.57.19.png](https://qiita-image-store.s3.amazonaws.com/0/133922/2d71be3b-9d48-800d-2573-650146dcb2d5.png)

大きなポイントとしては、前節まではkernel landからuser landへ移動したことです！ (とは言っても、すぐに`int $T_SYSCALL`にて、kernel landに引き戻されるのですが:airplane:)


```.as:initcode.S
.globl start
start:
  pushl $argv
  pushl $init
  pushl $0  // where caller pc would be
  movl $SYS_exec, %eax
  int $T_SYSCALL

# for(;;) exit();
exit:
  movl $SYS_exit, %eax
  int $T_SYSCALL
  jmp exit

# char init[] = "/init\0";
init:
  .string "/init\0"

# char *argv[] = { init, 0 };
.p2align 2
argv:
  .long init
  .long 0
```

本記事でやるのはswitchingなので、`int $T_SYSCALL`の直前で一旦終わりです。pathが`"/init"`であるバイナリ(これは、`init.c`をコンパイル、リンクしたあとのELF形式のbinaryです)で、引数をunixのexitとおんなじように設定し、あとは、x86の`int 0x80`呼び出しと似たような感じで`int $T_SYSCALL`を呼び出します。

このあと、``` `initcode.S`の`int $T_SYSCALL`が実行された後```の節にもある通りになりますが、直後の動きとしては、`struct cpu`構造体の`struct taskstate`に設定しておいた値がregisterに復元され... という流れになります。
詳細は、interruptが深く関わってくるので、別の記事でお話ししたいと思います:upside_down: お楽しみに!!

-----------

## sched関数の呼び出し ~ swtch呼び出し ~ scheduler関数の再開まで

前章で scheduler関数 -> initのprocessが動作するまでを説明しました。ここでは、CPUがprocessからscheduler関数へと戻るまでの流れを説明します。ここでいうprocessはinit processでも良いし、他の動作しているprocessでも同じですが、以下のタイミングでswtch呼び出し ~ scheduler関数の再開されます：

+ RUNNINGの状態のprocessが`wait`や`sleep`, `exit`などにより、状態が切り替わるとき

+ timerによるinterruptで強制的に別のprocessに切り替えるとき

本章では、前者の挙動をみます。後者はinterruptの記事で取り上げます。
wait, sleep, exitは関数を辿って行くと[^wait_sleep_exit]、`sched`に落ち着きます：

[^wait_sleep_exit]: wait, sleep, exitの他にも状態が変化する関数はあります。


```
wait -> sleep(状態がSLEEPINGに) -> sched
sleep -> sleep(状態がSLEEPINGに) -> sched
exit(状態がZOMBIEに) -> sched
```

3つの関数をみればわかるとおり、いままで　RUNNINGだったprocessの状態が変化した後、`sched`関数に突入します：

```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");
  // Were interrupts enabled before pushcli?
  intena = mycpu()->intena;
  // save the current context in proc->context and switch to the sched context previously in cpu->scheduler
  // both args are the type of `(struct context**, struct context*)`, which saves registers for kernel context switches.
  swtch(&p->context, mycpu()->scheduler);
  mycpu()->intena = intena;
}
```

大事なのが、`swtch`なので、その確認です。`swtch`は`main > scheduler > swtch`で一度でてきたswitchingの部分の一番本質的なコードのあった関数でした。

## swtch

```.as:swtch.S
.globl swtch
swtch:
  # former context
  movl 4(%esp), %eax
  # latter context
  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
  // now eip=forkret
  ret
```

またこのコードに行き着きました。



### switching前夜

また、図とコードを番号とともに対応させておきます：

![スクリーンショット 2018-09-28 11.29.32.png](https://qiita-image-store.s3.amazonaws.com/0/133922/97f8fb60-01bc-9b09-930a-57ee21ce6120.png)


```.as:swtch.S
// 0. `swtch(&p->context, mycpu()->scheduler);`で呼ばれるので、引数とreturn先のaddressがstackに積まれる
// #   void swtch(struct context **old, struct context *new);
.globl swtch
swtch:
  // 1. 第一引数を取り出す
  movl 4(%esp), %eax
  // 2. 第二引数を取り出す
  movl 8(%esp), %edx

  // 3. 現在のregisterを保存する
  pushl %ebp
  pushl %ebx
  pushl %esi
  pushl %edi
```

第二引数と図との対応に注意しましょう。また、3の時点では前に述べたswitchingと同じように`%esp`を`struct context*`のaddressと解釈できます。


### switching

同様に、図とコードを番号とともに対応させておきます：

![スクリーンショット 2018-09-28 11.33.21.png](https://qiita-image-store.s3.amazonaws.com/0/133922/edca32ab-e9b7-6cd1-b92a-b5abe9937db1.png)


```.as:swtch.S
// .globl swtch
// swtch:
  # Switch stacks
  // 1. procAのcontextを自身のcpu構造体の`struct context *scheduler`に保存する
  movl %esp, (%eax)
  // 2. %esp registerをscheduler processのstack領域内のaddressに書き換える。
  movl %edx, %esp
```

### switching完了後

後は同様に新しいprocess(scheduler process)の%esp上で、registerを復元しつつ、`%esp`を *引き上げる*だけです：

`ret`の後は、[switchingする前はなにがどうなっているのかの章]()の部分でもお話ししたように、`switchkvm(); // switch page table`へのaddressにjumpします。

## scheduler()からRUNNABLEのprocessにjump

```proc.c
scheduler関数の続き
  for(;;) {
      // 中略
      // switch current context to next context
      // void swtch(struct context **old, struct context *new);
      swtch(&(c->scheduler), p->context);
      switchkvm(); // switch page table

      // Process is done running for now.
      // It should have changed its p->state before coming back.
      c->proc = 0;
    }
    release(&ptable.lock);

  }
}
```

swtch関数の長旅(!!)が終わりました。ここからはpagingがscheduler processのものに変わりますので、`switchkvm();`にて`%cr3`にpage directoryを再ロードします。
いままで`c->proc = p`だったものが`c->proc = 0;`で終わり、for文が終わります。

```proc.c
// scheduler関数の続き
  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;
      // switch current context to next context
      // void swtch(struct context **old, struct context *new);
      swtch(&(c->scheduler), p->context);
```

ここの内容は、`mpmain()のscheduler()`の節でみた通り、

1: RUNNABLEのprocessを見つけ、
2: `c->proc = p`にて、CPU実行するprocessを結びつけて、
3: switchuvmにて
  3-1: taskの作成、task registerへのdescriptorのロード
  3-2: procAのpagingを`%cr3`(page directory base register (PDBR))に再ロード

を行い、swtchに突入した後は、[switchingする直前と直後はどうなっているのか](https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c#switching%E3%81%99%E3%82%8B%E7%9B%B4%E5%89%8D%E3%81%A8%E7%9B%B4%E5%BE%8C%E3%81%AF%E3%81%A9%E3%81%86%E3%81%AA%E3%81%A3%E3%81%A6%E3%81%84%E3%82%8B%E3%81%AE%E3%81%8B)の章でみた通りです。`swtch`でswitching完了後は`p`を上記のprocessとしたときの`p->tf->context`にある`forkret`を実行します[^forkret] ただし、 https://github.com/mit-pdos/xv6-public/blob/b818915f793cd20c5d1e24f668534a9d690f3cc8/proc.c#L403 のとおり、firstはもはや0[^static]なので、早々と`trapret`を実行し、`p->tf->eip` で格納された関数にジャンプし、関数を実行することになります。

長期出張から帰ってきて、また出張に出かけて行く船乗りのようなやつでした:ferry:

# まとめ

xv6(OS)にて、

1. switchingする前はなにがどうなっているのか
2. switchingする直前と直後はどうなっているのか(設定内容の保存、復元を行うわけですが..)
3. switchingした後はどうなるのか

を説明しました。随所随所でinterruptの部分を最低限拾いながら、死ぬほど詳しく解説したつもりです:innocent: 
根本的に間違っているとか、ちょっと間違っているとかでもご指摘くだされば嬉しいです！


[^forkret]: fork関数と`userinit`(これはboot時のみ)関数だけがprocessを作成(`fork`の場合は複製)する。両者、`allocproc`関数が`p->tf->context = forkret`と定めているので。いかなる場合でも`forkret`から実行されることになる。

[^static]: ここまで理解しているなら補足不要だと思いますが、`static int first = 1;`は`first`変数が一度のみ初期化されるという意味です。`static`キーワードで調べてみるとわかると思います。