# NachOS Trace code 筆記
- [概略](#概略)
- [Debug](#Debug)
- [吃 CLI 參數](#吃-CLI-參數)
- [Trace](#Trace)
- [Trace1](#Trace1)
- [Trace2](#Trace2)
- [Trace3](#Trace3)
- [Trace4](#Trace4)
- [Trace4_Init_ThreadedKernel](#Trace4_Init_ThreadedKernel)
- [Trace4_Timer](#Trace4_Timer)
- [Trace4_OneTick()](#Trace4_OneTick())
- [Trace4_Init_Machine](#Trace4_Init_Machine)
- [Trace4_Init_FileSystem](#Trace4_Init_FileSystem)
- [Trace5](#Trace5)
- [Trace6](#Trace6)
- [Trace6_StackAllocate](#Trace6_StackAllocate)
- [Trace7](#Trace7)
- [Trace7_SWITCH](#Trace7_SWITCH)
- [Trace8](#Trace8)
- [Trace8_Machine::Run](#Trace8_MachineRun)
- [Trace8_OneInstruction](#Trace8_OneInstruction)
- [Trace8_OneTick](#Trace8_OneTick)
- [Trace9](#Trace9)
- [Trace9_yieldOnReturn](#Trace9_yieldOnReturn)
- [Trace10_Halt](#Trace10_Halt)
## 概略
- [github repos 在此](https://github.com/LJP-TW/NachOS)
repos 已經更新過了，這份筆記提到的 code 是在 commit `Add TraceCode Note`
code 全放在 code 資料夾
Makefile 也推薦高速掃過看一下
[最後的章節](#Trace)會以執行流程的方式紀錄整個執行過程，追蹤 `userprog/nachos`
並會統整一些架構出來，放在中間的章節
## Debug
**初始化在 [threads/main.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/main.cc)**
用參數 `-d` 設定的字串創造一個 Debug Obj
Debug Class 定義於 [lib/debug.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/lib/debug.h)
假設 `-d` 設定為 `ti`(e.g. `./userprog/nachos -e test/test2 -d ti`)
那 Debug Class 的 enableFlags 會是字串 `ti`
接著在整個專案的任意處寫類似以下的語句:
- ```DEBUG(dbgThread, "My debug message")```
DEBUG 是一個 macro，也定義在 [lib/debug.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/lib/debug.h)，會去看 dbgThread 代表的字元 `t` (同樣也寫在 lib/debug.h) 是否有在剛剛 `-d` 設定的字串中，有就輸出 `My debug message`
## 吃 CLI 參數
看 [Trace3](#Trace3)
## Trace
以下 Trace 在 code 底下執行 ```./userprog/nachos -e test/test1``` 的過程
### Trace1
進入點為 [threads/main.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/main.cc)
這裡也設定了 Debug 物件，詳細請看[Debug](#Debug)
接著 call ```kernel = new KernelType(argc, argv);```，KernelType 是一個 Macro，定義在 [threads/main.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/main.h)，會根據 define 了以下 symbol 做不一樣的行為
- NETWORK
- USER_PROGRAM
- 兩者都沒設
現在來追看看到底什麼 symbol 有被 define
### Trace2
因為我們追蹤的是 `userprog/nachos`，看一下 [userprog/Makefile](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/userprog/Makefile)，以下 focus 在 跟 define 有關的部分
userprog/Makefile 中有一行
```
DEFINES = -DTHREADS -DUSER_PROGRAM -DFILESYS_NEEDED -DFILESYS_STUB
```
再往下一點有兩行
```
include ../Makefile.common
include ../Makefile.dep
```
[Makefile.common](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/Makefile.common) 裡有一行
```
CFLAGS = -g -Wall $(INCPATH) $(DEFINES) $(HOST) -DCHANGED
```
[Makefile.dep](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/Makefile.dep) 只有這樣
```
# CPU = x86, OS = linux
HOST = -Dx86 -DLINUX -DBSD
DISASM = disasm
```
對於 Makefile 的 `=` 跟 `:=` 兩個指派運算子的觀念可以看看[這篇文](http://dannysun-unknown.blogspot.com/2015/03/makefile.html)，簡單來說，`=` 是會到要用到的時候才會展開
而 CFLAGS 是 compile 時，會餵給 compiler 吃的參數
最後整個 CFLAGS 是 `-g -Wall $(INCPATH這個我們先不考慮) -DTHREADS -DUSER_PROGRAM -DFILESYS_NEEDED -DFILESYS_STUB -Dx86 -DLINUX -DBSD -DCHANGED`
這些參數會使 compiler 在 compile 時預先 define
- THREADS
- USER_PROGRAM
- FILESYS_NEEDED
- FILESYS_STUB
- x86
- LINUX
- BSD
- CHANGED
因為 define 了 USER_PROGRAM，所以前面 [Trace1](#Trace1) 的 main.h 會 define KernelType 為 UserProgKernel
### Trace3
在 [threads/main.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/main.cc) 中執行 ```kernel = new KernelType(argc, argv);```，實際上是創造 UserProgKernel 物件
UserProgKernel 實作於 [userprog/userkernel.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/userprog/userkernel.cc)，會先執行父類別 ThreadedKernel 的 Constructor
ThreadedKernel 實作於 [threads/kernel.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/kernel.cc)，設定 ```randomSlice = FALSE;```會在後續創造 Alarm obj 時用到
回到 UserProgKernel，吃到參數 `-e`，將 `execfile[0]` 設為 `test/test1`，`execfileNum` 為 1
可以看到 UserProgKernel 的 Constructor 只是吃吃參數而已，真正有做些初始化是在後面
### Trace4
在 [threads/main.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/main.cc) 中執行 ``` kernel->Initialize();```
執行 [userprog/userkernel.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/userprog/userkernel.cc) 中的`UserProgKernel::Initialize()`
`UserProgKernel::Initialize()` 會執行
- `ThreadedKernel::Initialize()`
- 請看 [Trace4_Init_ThreadedKernel](#Trace4_Init_ThreadedKernel)
- `machine = new Machine(debugUserProg);`
- 請看 [Trace4_Init_Machine](#Trace4_Init_Machine)
- `fileSystem = new FileSystem();`
- 請看 [Trace4_Init_FileSystem](#Trace4_Init_FileSystem)
### Trace4_Init_ThreadedKernel
執行 [threads/kernel.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/kernel.cc) 中的`ThreadedKernel::Initialize()`
`ThreadedKernel::Initialize()` 會執行
- `stats = new Statistics();`
- `Statistics::Statistics()` 實作於 [machine/stats.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/stats.cc) 中
- 此元件掌管 Tick Counters 跟其他數據統計
- `interrupt = new Interrupt;`
- `Interrupt::Interrupt()` 實作於 [machine/interrupt.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/interrupt.cc) 中
- 主要模擬硬體中斷的元件
- 初始化一些 member
- `level = IntOff;`
- disable 中斷
- `pending = new SortedList<PendingInterrupt *>(PendingCompare);`
- 初始化 Pending list
- 裡面會存放著中斷，後續會再追到
- `inHandler = FALSE;`
- 還未在處裡中斷
- `yieldOnReturn = FALSE;`
- 還沒要進行 context switch
- `status = SystemMode;`
- 正在 kernel mode
- `scheduler = new Scheduler(type);`
- `Scheduler::Scheduler(SchedulerType type)` 實作於 [threads/scheduler.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/scheduler.cc) 中
- CPU Scheduler
- 初始化 blockedList、readyList
- `alarm = new Alarm(randomSlice);`
- `Alarm::Alarm(bool doRandom)` 實作於 [threads/alarm.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/alarm.cc) 中
- 設定 Timer 物件，randomSlice 為 False
- 請看 [Trace4_Timer](#Trace4_Timer)
- `currentThread = new Thread("main");`
- `Thread::Thread(char* threadName)` 實作於 `threads/threads.cc` 中
- 初始化大部分參數為 NULL，還需要 call `Thread::Fork()`
- `currentThread->setStatus(RUNNING);`
- 直接設 main thread 的 status 為 RUNNING
- `interrupt->Enable();`
- 實作於 [machine/interrupt.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/interrupt.h)，直接 call `Interrupt::SetLevel(IntOn);`
- 中斷元件從不接受中斷改變狀態為接受中斷，會 call 一次 `Interrupt::OneTick()`
- 請看 [Trace4_OneTick()](#Trace4_OneTick())
#### Trace4_Timer
`Timer::Timer(bool doRandom, CallBackObj *toCall)` 實作於 [machine/timer.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/timer.cc) 中
將 `callPeriodically` 設定為 `toCall`
並呼叫 `Timer::SetInterrupt()`
`Timer::SetInterrupt()` 中，若 Timer 為 Enable，則呼叫 `Interrupt::Schedule`
創造一個 PendingInterrupt 物件，紀錄著
- 什麼要被 call: this Timer
- 何時要被 call: delay，也就是 TimerTicks
- 中斷類型: TimerInt
並插入到 Pending list
#### Trace4_OneTick()
`Interrupt::OneTick()` 實作於 [machine/interrupt.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/interrupt.cc)
Trace 到此時，還在 kernel mode，totalTicks 會加上 SystemTick
(各種 Ticks 定義在 [machine/stats.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/stats.h) 中)
先禁止接受中斷後執行
- `CheckIfDue(FALSE);`
`Interrupt::CheckIfDue(bool advanceClock)` 簡單來說是檢查 Pending list 有無已經到達預定執行時間的中斷要做，有就呼叫此中斷的 Callback，再呼叫中斷的 Callback 的期間，將 inHandler 設為 True，表示正在處理中斷，回傳值的狀況分為以下狀況
- Pending List 為空，沒有任何中斷要做
- Return false
- 下一個中斷要處理的時間還沒到，且 advanceClock 為 False
- Return false
- 此 function 原本行為是下一個中斷要處理的時間還沒到的話，會快轉到下一個要中斷要處理的時間，但若 advanceClock 為 false，表示告訴這個 function 先不要快轉
- 其餘狀況皆 return true
由於 Pending List 中已經有一個 TimerInt 的中斷，時間還沒到，應該要快轉，但 advanceClock 設 false，所以回傳 false
處理完中斷後，重新開啟接受中斷
看看有無要進行 content switch，有則執行 ```kernel->currentThread->Yield();```不過 Trace 到目前為止是還不會需要 content switch 的。
### Trace4_Init_Machine
`Machine::Machine(bool debug)` 實作於 [machine/machine.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/machine.cc)，debug 參數為 false，簡單來說，就是初始化機器的暫存器為 0，清空 mainMemory
### Trace4_Init_FileSystem
`FileSystem::FileSystem(bool format)` 實作於 `filesys/filesys.cc`，format 預設為 true，這個就先不深追
### Trace5
在 [threads/main.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/main.cc) 中執行
```
CallOnUserAbort(Cleanup); //設定按下 ctrl+c 就 call `Cleanup`
kernel->SelfTest(); // 不是很重要，For debugging
kernel->Run(); // 繼續追蹤這個 function call
```
main 到此告一段落，Control flow 移轉到 kernel->Run()
### Trace6
`UserProgKernel::Run()` 首先一個 for 迴圈，為每支 userprogram 建立 Thread、分配 AddrSpace，並且執行 Fork
本例子是執行
```
t[n] = new Thread("test/test1");
t[n]->space = new AddrSpace();
t[n]->Fork((VoidFunctionPtr) &ForkExecute, (void *)t[n]);
```
最後執行 `ThreadedKernel::Run();`
- `t[n] = new Thread("test/test1");`
- 初始化大部分參數為 NULL，thread status 為 JUST_CREATED
- `t[n]->space = new AddrSpace();`
- `AddrSpace::AddrSpace()` 實作於 [userprog/addrspace.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/userprog/addrspace.cc)
- 目前 pageTable 直接將 virtual address 映射為 physical address
- `t[n]->Fork((VoidFunctionPtr) &ForkExecute, (void *)t[n]);`
- 首先呼叫 `StackAllocate(func, arg);` 分配一塊 stack
- 請看 [Trace6_StackAllocate](#Trace6_StackAllocate)
- 將 thread 放到 ready list
- thread status 變成 READY
### Trace6_StackAllocate
`Thread::StackAllocate (VoidFunctionPtr func, void *arg)`首先執行
- `stack = (int *) AllocBoundedArray(StackSize * sizeof(int));`
`AllocBoundedArray(StackSize * sizeof(int))` 實作於 [lib/sysdep.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/lib/sysdep.cc)
- 首先 call `getpagesize()` 取得一個 page 多大
- 創造 `pgSize * 2 + size` 的空間
- 將頭尾 2 頁設為不可 rwx
- 這 2 個 page 是為了偵測有無發生 stack overflow
- 最後 return 實際可用的第 2 頁位址
回到 `Thread::StackAllocate`，接下來會根據不同架構做不一樣的事情，在 [Trace2](#Trace2) 我們知道有 define x86，所以會執行
```
stackTop = stack + StackSize - 4;
*(--stackTop) = (int) ThreadRoot;
*stack = STACK_FENCEPOST;
machineState[PCState] =(void *)ThreadRoot;
machineState[StartupPCState] = (void *)ThreadBegin;
machineState[InitialPCState] = (void *)func;
machineState[InitialArgState] = (void *)arg;
machineState[WhenDonePCState] = (void *)ThreadFinish;
```
:::info
- PCState、StartupPCState 那些 define 在 [threads/switch.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/switch.h)
```
#define PCState (_PC/4-1)
#define FPState (_EBP/4-1)
#define InitialPCState (_ESI/4-1)
#define InitialArgState (_EDX/4-1)
#define WhenDonePCState (_EDI/4-1)
#define StartupPCState (_ECX/4-1)
```
詳細機制後面會再提
:::
- stack 位址是 from high to low，所以將 stackTop 移動到這塊記憶體的最高記憶體位址
- 將 ThreadRoot push 上去
- 將 stack 最底設為 STACK_FENCEPOST，用來偵測有無 overflow
- STACK_FENCEPOST 只是一個 const int 0xdedbeef
- 定義於 threads/thread.cc
- ThreadRoot 先定義於 [threads/thread.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/thread.h)
- 實作於 [threads/switch.s](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/switch.s)
- 設定一些初始的 Register
- 例如將 `machineState[PC]` 設定為 ThreadRoot
- 後續會詳談，這邊留個印象就好
目前為止 thread `test/test1` 的 stack 上的資料大概像
### Trace7
回到 `UserProgKernel::Run()`，for 迴圈跑完後執行 `ThreadedKernel::Run();`
`ThreadedKernel::Run()` 裡頭執行 `currentThread->Finish();`
`currentThread` 為在 [Trace4_Init_ThreadedKernel](#Trace4_Init_ThreadedKernel) 設定的 `main`
Thread `main` 的 `Thread::Finish` 執行了
- 首先關閉接收中斷
- 呼叫 `Sleep(TRUE)`
Thread `main` 的 `Thread::Sleep (bool finishing)` 執行了
- 將 thread `main` status 設為 BLOCKED
- 尋找下一個在 ready list 的 thread
- 找到 `test/test1`
- 執行 nextthread
- 執行 `kernel->scheduler->Run(Thread test/test1, TRUE);`
`Scheduler::Run (Thread test/test1, TRUE)` 執行了
- 將 toBeDestroyed 設為 `main`
- 呼叫 thread `main` 的 `CheckOverflow`
- 檢查 stack 上是否為 STACK_FENCEPOST
- 將 kernel->currentThread 設為 thread `test/test1`
- 將 thread `test/test1` status 設為 RUNNING
- 執行 SWITCH(`main`, `test/test1`)
- 請看 [Trace7_SWITCH](#Trace7_SWITCH)
- 執行 `CheckToBeDestroyed()`
- Delete thread `main`
- thread main 的 stack 應該於 SWITCH 中被清除
### Trace7_SWITCH
`void SWITCH(Thread *oldThread, Thread *newThread);`
- 定義於 [threads/thread.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/thread.h)
- 實作於 [threads/switch.s](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/switch.s)
在 [Trace2](#Trace2) 我們知道 define 了 x86，所以 switch.s 中的 SWITCH code 為
```
.comm _eax_save,4
.globl SWITCH
SWITCH:
movl %eax,_eax_save # save the value of eax
movl 4(%esp),%eax # move pointer to t1 into eax
movl %ebx,_EBX(%eax) # save registers
movl %ecx,_ECX(%eax)
movl %edx,_EDX(%eax)
movl %esi,_ESI(%eax)
movl %edi,_EDI(%eax)
movl %ebp,_EBP(%eax)
movl %esp,_ESP(%eax) # save stack pointer
movl _eax_save,%ebx # get the saved value of eax
movl %ebx,_EAX(%eax) # store it
movl 0(%esp),%ebx # get return address from stack into ebx
movl %ebx,_PC(%eax) # save it into the pc storage
movl 8(%esp),%eax # move pointer to t2 into eax
movl _EAX(%eax),%ebx # get new value for eax into ebx
movl %ebx,_eax_save # save it
movl _EBX(%eax),%ebx # retore old registers
movl _ECX(%eax),%ecx
movl _EDX(%eax),%edx
movl _ESI(%eax),%esi
movl _EDI(%eax),%edi
movl _EBP(%eax),%ebp
movl _ESP(%eax),%esp # restore stack pointer
movl _PC(%eax),%eax # restore return address into eax
movl %eax,4(%esp) # copy over the ret address on the stack
movl _eax_save,%eax
ret
```
(AT&T 語法的組語, src在左, dst在右)
對應 `SWITCH(main, test/test1)` 的組合語言是
```
push Thread * test/test1
push Thread * main
call SWITCH
```
所以執行 nachos 的主機的 stack 上會長這樣
解釋 SWITCH 做的事情
```
movl %eax,_eax_save
```
- 先將 `eax` 的值存到 `_eax_save`
```
movl 4(%esp),%eax # move pointer to t1 into eax
movl %ebx,_EBX(%eax) # save registers
movl %ecx,_ECX(%eax)
movl %edx,_EDX(%eax)
movl %esi,_ESI(%eax)
movl %edi,_EDI(%eax)
movl %ebp,_EBP(%eax)
movl %esp,_ESP(%eax) # save stack pointer
```
:::info
- 這邊要配合 [switch.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/switch.h) 看，switch.h 有一段 code 如下
```
#define _ESP 0
#define _EAX 4
#define _EBX 8
#define _ECX 12
#define _EDX 16
#define _EBP 20
#define _ESI 24
#define _EDI 28
#define _PC 32
```
- 還要配合 Thread Class 前半段的定義
```
class Thread {
private:
// NOTE: DO NOT CHANGE the order of these first two members.
// THEY MUST be in this position for SWITCH to work.
int *stackTop; // the current stack pointer
void *machineState[MachineStateSize]; // all registers except for stackTop
```
- Thread * `test/test1` + 0 就會存取到 stackTop
- Thread * `test/test1` + 4 就會存取到 machineState[0]
- Thread * `test/test1` + 8 就會存取到 machineState[1]
- 以此類推
:::
- 將 `eax` 的值改為 `esp + 4`，也就是 Thread * `main`
- 將 `ebx` 存到 `[eax + _EBX]`，也就是 `[eax + 8]`，也就是 Thread * `main` 的 `machineState[1]`，之後以 `machineState[EBX]` 形式表示
- 以此類推
- **其中**，`_ESP` 為 0，所以改 `machineState[ESP]` 實際上是改 Thread class 裡的 stackTop
```
movl _eax_save,%ebx
movl %ebx,_EAX(%eax)
```
- 將剛剛存的 `eax` 放到 `ebx`
- 存放到 Thread * `main` 的 `machineState[EAX]`
```
movl 0(%esp),%ebx
movl %ebx,_PC(%eax)
```
- 將 call 完 SWITCH 後要回去的 return address 放到 Thread * `main` 的 `machineState[PC]`
:::success
到目前為止存好了 Thread * `main` (oldThread) 各個暫存器的值
- esp 為:
- PC 為 Return address
- 為 call 完 SWITCH 後的下一個指令位址
:::
```
movl 8(%esp),%eax
```
- 存取 Thread * `test/test1`
```
movl _EAX(%eax),%ebx # get new value for eax into ebx
movl %ebx,_eax_save # save it
movl _EBX(%eax),%ebx # retore old registers
movl _ECX(%eax),%ecx
movl _EDX(%eax),%edx
movl _ESI(%eax),%esi
movl _EDI(%eax),%edi
movl _EBP(%eax),%ebp
movl _ESP(%eax),%esp # restore stack pointer
```
- 將 Thread * `test/test1` 紀錄的各個暫存器的值恢復
- 將 `eax` 先存到 `_eax_save`
- 以此類推
- **其中**，取出 `_ESP(%eax)` 實際上是取出 Thread * `test/test1` 的 stackTop
- 複習這張圖
- 所以現在機器上的 esp 會指向這一塊記憶體
```
movl _PC(%eax),%eax # restore return address into eax
movl %eax,4(%esp) # copy over the ret address on the stack
movl _eax_save,%eax
ret
```
- 將 Thread * `test/test1` 的 Program Counter 放到 return address
- 恢復 `eax`
- return，從 esp pop return address 到 PC，也就是跳轉到 ThreadRoot 上，所以現在 stack 長這樣
(pop 只會取值出來放到暫存器，並將 `esp` + 4，並不會改動值)
### Trace8
現在要跳轉到 Thread `test/test1` 的 Program counter 上
可以回顧 [Trace6_StackAllocate](#Trace6_StackAllocate)，Thread `test/test1` `machineState[PC]` 是 `ThreadRoot` 的位址
所以 Control flow 現在會跑到 `ThreadRoot` 上執行
`void ThreadRoot()`
- 定義於 [threads/thread.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/thread.h)
- 實作於 [threads/switch.s](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/switch.s)
code 如下
```
.globl ThreadRoot
/* void ThreadRoot( void )
**
** expects the following registers to be initialized:
** eax points to startup function (interrupt enable)
** edx contains inital argument to thread function
** esi points to thread function
** edi point to Thread::Finish()
*/
ThreadRoot:
pushl %ebp
movl %esp,%ebp
pushl InitialArg
call StartupPC
call InitialPC
call WhenDonePC
# NOT REACHED
movl %ebp,%esp
popl %ebp
ret
```
- `ebp` 值初始為 0，push 上去後將 `esp` 的值放到 `ebp`
- `pushl InitialArg`
- `call StartupPC`，會 push 下一個指令位址
`StartupPC` 定義在 [threads/switch.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/switch.h)，就是 `%ecx`
在剛剛的 SWITCH 中，`%ecx` 的值設定為 Thread * `test/test1` 的 `machineState[ECX]`
而 Thread * `test/test1` 的 `machineState[ECX]` 的值在 [Trace6_StackAllocate](#Trace6_StackAllocate) 中有設定
```
machineState[StartupPCState] = (void *)ThreadBegin;
```
所以現在會呼叫 `ThreadBegin`
`static void ThreadBegin()` 實作於 [threads/thread.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/thread.cc)
```
static void ThreadBegin() { kernel->currentThread->Begin(); }
```
`kernel->currentThread` 現在為 Thread `test/test1`
所以會呼叫到 Thread `test/test1` 的 `Begin()`
`Thread::Begin()` 執行
- `kernel->scheduler->CheckToBeDestroyed();`
- Thread * `main` 在此被砍掉
- `kernel->interrupt->Enable();`
- `void Enable() { (void) SetLevel(IntOn); }`
- `Interrupt::SetLevel(IntStatus now)` 中斷從關閉到打開，會 call 一次 `OneTick()`
`Interrupt::OneTick()` 執行
- 還在 SystemMode，計數 sysmtemTicks
- 關閉中斷
- 執行 `CheckIfDue(FALSE);`
- pending list 有元件，但時間未到，又 advanceClock 為 False，故回傳 false
- 開啟中斷
- yieldOnReturn 為 false，不會做事
執行完了 return，從 stack pop 出 return address 到 PC，執行`call InitialPC`，會 push 下一個要執行的指令
`InitialPC` 定義在 [threads/switch.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/threads/switch.h)，就是 `%esi`
在剛剛的 SWITCH 中，`%esi` 的值設定為 Thread * `test/test1` 的 `machineState[ESI]`
而 Thread * `test/test1` 的 `machineState[ESI]` 的值在 [Trace6_StackAllocate](#Trace6_StackAllocate) 中有設定
```
machineState[InitialPCState] = (void *)func;
```
`func` 為 `ForkExecute`，所以現在會呼叫 `ForkExecute(Thread *t)`
- 實作於 [userprog/userkernel.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/userprog/userkernel.cc)
- Thread * `t` 這第一個參數為 `esp` + 4 的 InitialArg，此時回頭追一下 InitialArg 是什麼
- 在 [Trace6](#Trace6) 可以看到 Fork 的 arg 是 `t[n]`
- 進一步在 [Trace6_StackAllocate](#Trace6_StackAllocate) 可以看到
```
machineState[InitialArgState] = (void *)arg;
```
- 所以 InitialArg ，也就是`t`，是 Thread `test/test1`
- `ForkExecute(Thread *t)` 執行 `t->space->Execute(t->getName());`
執行 Thread `test/test1` 的 `space->Execute("test/test1")`
`AddrSpace::Execute(char *fileName)` 實作於 [userprog/addrspace.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/userprog/addrspace.cc)，執行了
- `Load(fileName)`
- 將主機(Linux)上的檔案讀進 `kernel->machine->mainMemory`
- `this->InitRegisters()`
- 裡頭用到的 `NumTotalRegs` 是定義於 [machine/machine.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/machine.h)，為 user program 能用的 CPU registers
- 將 `kernel->machine` 的所有 registers 先填為 0
- 包含將 `kernel->machine` 的 PC register 寫為 0 (user program 的 start，也就是 entry point，要放在 memory address 0)
- 將 `kernel->machine` 的 NextPC register 寫為 4
- 將 `kernel->machine` 的 StackReg 寫為最高位址
- `this->RestoreState()`
- 將 `kernel->machine` 的 pageTable 改為此 Thread 的 AddrSpace 的 pageTable
- `kernel->machine->Run()`
- 定義於 [machine/machine.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/machine.h)
- 實作於 [machine/mipssim.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/mipssim.cc)
- **實際上 NachOS 以 MIPS 架構模擬執行 user program 的 function**
- 請看下一章節
### Trace8_Machine::Run
執行以下事情
```c=
nstruction *instr = new Instruction;
kernel->interrupt->setStatus(UserMode);
for (;;) {
OneInstruction(instr);
kernel->interrupt->OneTick();
if (singleStep && (runUntilTime <= kernel->stats->totalTicks))
Debugger();
}
```
- 首先，class `Instruction` 只是一個用來存放指令的結構
- 將 `kernel->interrupt` 設為 `UserMode`
- 接下來是無限迴圈
- 執行 OneInstruction
- 請看 [Trace8_OneInstruction](#Trace8_OneInstruction)
- 執行 `kernel->interrupt->OneTick()`
- 請看 [Trace8_OneTick](#Trace8_OneTick)
- 下面的 if 是如果有開啟 debug 選項，要求逐行動態 debug
- 本例沒有啟用
### Trace8_OneInstruction
- 定義於 [machine/machine.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/machine.h)
- 實作於 [machine/mipssim.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/mipssim.cc)
這邊沒有認真追完，但看個大概還是能看得出來執行了什麼
```
ReadMem(registers[PCReg], 4, &raw)
```
- 實作於 [machine/translate.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/translate.cc)
- 從 PCReg 讀一條指令(MIPS 指令皆為 4 bytes)
```
instr->value = raw;
instr->Decode();
```
- 翻譯指令
```
int pcAfter = registers[NextPCReg] + 4;
```
- 先記著 NextPC
```
switch (instr->opCode)
{
case OP_xxx:
...
...
}
```
- 依照是什麼指令，選擇要做什麼事情
- 就是一個典型 Virtual Machine
- **其中 OP_SYSCALL 會執行 `RaiseException(SyscallException, 0);`**
- 請看 [Trace8_RaiseException](#Trace8_RaiseException)
- 有一些指令會更改 `nextLoadReg`、`nextLoadValue`，在待會的`DelayedLoad(nextLoadReg, nextLoadValue);` 會用到
```
DelayedLoad(nextLoadReg, nextLoadValue);
```
- 執行 `registers[registers[LoadReg]] = registers[LoadValueReg];`
- 設定 `registers[LoadReg] = nextReg`
- 設定 `registers[LoadValueReg] = nextValue;`
統整來說，call 了 `DelayedLoad(MyReg1, MyValue1);`，並不會馬上將 `MyValue1` 存到 Register `MyReg1` 上，而是要等下次再 call 到這個 function 才會存過去 (所以叫做 `DelayedLoad`)
- 大概猜想創造這個 function 是為了完成 MIPS 的指令，這裡我的猜想極可能有誤
```
registers[PrevPCReg] = registers[PCReg];
registers[PCReg] = registers[NextPCReg];
registers[NextPCReg] = pcAfter;
```
- 更新跟 PC 有關的 Register
#### Trace8_RaiseException
`Machine::RaiseException(ExceptionType which, int badVAddr)`
- 定義於 [machine/machine.h](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/machine.h)
- 實作於 [machine/machine.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/machine.cc)
當執行 user 的 MIPS 程式時，若有 call syscall 或有其他狀況，都會觸發這個 function (寫在 [Trace8_OneInstruction](#Trace8_OneInstruction) 中)
執行了以下事情
- `registers[BadVAddrReg] = badVAddr;`
- 透過 virtual machine 暫存器傳遞參數
- `DelayedLoad(0, 0);`
- 將還沒 Load 的東西 Load 好
- `kernel->interrupt->setStatus(SystemMode);`
- 陷入 `SystemMode` (`KernelMode`)
- `ExceptionHandler(which);`
- 執行對應要做的事情
- `kernel->interrupt->setStatus(UserMode);`
- 回到 `UserMode`
`ExceptionHandler(ExceptionType which)`
- 實作於 [userprog/exception.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/userprog/exception.cc)
- 這邊就是可以自訂 exception、syscall 的地方了
- 因為之前完成過自訂 syscall 的作業，對這邊算熟悉，就不細講這邊，這邊不懂的人請另找跟寫 syscall 相關的文章，應該有所幫助
### Trace8_OneTick
`Interrupt::OneTick()`
- 實作於 [machine/interrupt.cc](https://github.com/LJP-TW/NachOS/blob/540e13362406a95923271c6e653de03dfc3bb9a9/code/machine/interrupt.cc)
此時的 OneTick 為 `UserMode`
:::info
在此整理一下 OneTick 被 call 的狀況
第一次 `UserMode` OneTick 之前會歷經三次 `SystemMode` OneTick
- 第一次 `SystemMode` OneTick
- 在 `ThreadedKernel->Initialize()` 開啟接受中斷，進而呼叫到
- 第二次 `SystemMode` OneTick
- 在 `UserProgKernel->Run()` 初始化 user program，呼叫到 Fork 時，將 thread 放進 readylist 時有關開一次中斷，進而呼叫到
- 第三次 `SystemMode` OneTick
- `SWITCH` 過後，執行每個 user thread 都會先執行的 `Thread::Begin()`，裡頭有將中斷開啟，進而呼叫到
在此例中，若後面加上 debug flag `-d i`，可以看到前三個 Ticks 是一次跳 10，後面則一次跳 1，是因為設定在 machine/stats.h 中的 SystemTick 為 10，UserTick 為 1，而前三次 Ticks 是在 SystemMode 運行，後面的 Ticks 是在 UserMode
:::
### Trace9
這邊高速 Trace 一下，以 debug 資訊為輔助
在執行 nachos 的指令後面加上 `-d i`，可以看到跟 interrupt 有關的 debug 資訊
這邊小小複習一下 [Trace8_Machine::Run](#Trace8_MachineRun)
裡頭的無限迴圈做的事情就是
- 執行一行 user program (MIPS) 的指令
- 其中指令有可能會 `RaiseException` 進而陷入 SystemMode 執行 syscall
- call 一次 `kernel->interrupt->OneTick()`
- 每次 OneTick 就會
- 增加 Ticks 數
- 檢查 pending list 有無到期的中斷要執行
- 若 yieldOnReturn 為 True，則要多做一些事
- 請看 [Trace9_yieldOnReturn](#Trace9_yieldOnReturn)
還有整個程式執行完後的部分也還未追到
- 請看 [Trace10_Halt](#Trace10_Halt)
### Trace9_yieldOnReturn
在初始化時，有創造 `Timer`，並且有註冊在未來 TimerTicks 過後要執行 `Timer` 的 callback
- 可以回顧 [Trace4_Timer](#Trace4_Timer)
- TimerTicks 定義在 machine/stats.h，為 100
- 初始化時 totalTicks 為 0，所以這次註冊是註冊在 totalTicks 為 100 時會執行 `Timer` 的 callback
在剛剛的 [Trace9](#Trace9)，在無限迴圈時會一直 call `OneTick`
因為是 UserMode，所以 totalTicks 一次加 UserTick
- UserTick 定義在 machine/stats.h，為 1
當 totalTicks 來到 100 時，`Interrupt::OneTick()` 的執行流程是
- 執行 `CheckIfDue(FALSE);`，裡頭執行了
- `next = pending->Front();`
- 抓取到 Timer 中斷，且現在為要處理這個中斷的時間點
- `kernel->machine->DelayedLoad(0, 0);`
- 將先前有設定要 DelayedLoad 的值正式 load 進去
- `inHandler = TRUE;` 設定正在處理中斷
- 進入 while 迴圈，處理每個到期的中斷
- `next = pending->RemoveFront();`
- 從 pending list 抓取第一個出來處理
- `next->callOnInterrupt->CallBack();`
- 呼叫 `Timer->CallBack()`
- 進一步呼叫 `Alarm->CallBack()`
- 若在 IdleMode、Pending list 中沒有其他未來要處理的中段，且符合一些其他條件，則關閉 `Timer`
- 若符合某些條件，則呼叫 `interrupt->YieldOnReturn();`
- 呼叫 `SetInterrupt();`，若 Timer 沒被 disable，則設定在未來 100 個 Tick 後要再一次執行 Timer 中斷
- `inHandler = FALSE;` 設定沒在處理中斷
- 若 yieldOnReturn 為 True
- 先將 yieldOnReturn 設為 False
- status 進入 SystemMode
- 執行 `kernel->currentThread->Yield();` 準備讓出 CPU
- 請看 [Trace9_yield](#Trace9_yield)
- status 回到原本的 Mode
:::info
所以整個流程可以理解為
- 下一個 Timer 時間點到了之後，就要執行 Content switch
:::
#### Trace9_yield
`Thread::Yield()` 執行的事情是
- 先關閉中斷
- 從 readylist 中找下一個要跑的 thread
- 如果 readylist 沒有 thread，就不做 content switch
- 如果有
- 則執行 `ReadyToRun()` 把 oldThread 丟進 ready list
- 再執行 `kernel->scheduler->Run(nextThread, FALSE);`
- `kernel->scheduler->Run` 主要就是做 Content switch
- 將中斷設為原本的狀態
此例子只有一個 user program，所以這裡不會做 Content switch
### Trace10_Halt
這邊在執行 nachos 的指令後面多加一個 flag `-d ita`，可以多看到跟 Interrupt、Thread、AddrSpace 有關的 debug 資訊
User program 最後會 call syscall `SC_Exit`
Function call stack:
- `Machine::Run` -> `OneInstruction` -> `RaiseException` -> `ExceptionHandler`
- switch case `SC_Exit` 執行了
- `kernel->currentThread->Finish();`
`kernel->currentThread->Finish();` 執行了
- 關閉中斷
- `Sleep(TRUE)` 永久睡去(其實就是死了)
- 設定此 thread status 為 BLOCKED
- While Ready list 沒有 thread
- 呼叫 `kernel->interrupt->Idle();`
- 設定系統進入 IdleMode
- 檢查未來是否還有中斷沒處理
- 有的，有一個 Timer 預計在 totalTicks 為 200 時執行
- 將 Ticks 快轉
- 呼叫 Timer 的 callback
- 呼叫 Alarm 的 callback
- 系統在 IdleMode，未來也沒有中斷了，將 Timer disable
- 呼叫 `Timer::SetInterrupt()`
- Timer 已被 disable，什麼事都不會做
- 設定系統進入 SystemMode
- Ready list 還是沒有 thread
- 呼叫 `kernel->interrupt->Idle();`
- 設定系統進入 IdleMode
- 檢查未來是否還有中斷沒處理
- 沒有
- 呼叫 `Halt()` 進行關機
###### tags: `OS`, `NachOS`
Sign in with Wallet
Connect another wallet