###### tags: `OS`
Raspberry-pi-os
===
reference:
https://github.com/s-matyukevich/raspberry-pi-os
## Bootloader before the kernel image
為了避免頻繁的插、拔 SD card 進行 image 的更新，在 image 最一開始設置一個 bootloader，監聽 UART 一定的秒數，秒數內能夠進行新的 kernel image upload
樹莓派開始接收數據，並將數據保存到 sd 卡上第一個 fat32 分區的 root，覆蓋掉原有的kernel.img
### rpi bootloader
FSBL（第一階段bootloader）位於ROM，由各個hardware vendor來實現。
它會加載一個image到內存（這個image可以是第二階段bootloader，例如grub、lilo等，也可以是kernel），並將 CPU 的控制權移交
### UART
* SoC and Host communication
* recive/put data 都是透過 register `AUX_MU_IO` [read/write]
* register `AUX_MU_LSR[1]` 表示有無數據可讀
* register `AUX_MU_LSR[6]` 表示數據是否已滿，能否繼續寫入
### sd和fat32文件系统
[RPI SD card spec.](https://gist.github.com/eggman/40612fdeb6d081a9a7d1a63ddef647f1)
```text
sdhci 0x20300000
sdhost 0x20202000
```
[FatFs](http://elm-chan.org/fsw/ff/00index_e.html)
### timer
使用 system timer
```clike
#define MMIO_BASE 0x3F000000U
#define SYSTIMER_BASE (MMIO_BASE + 0x3000)
#define SYSTIMER_CS (SYSTIMER_BASE+0x0)
#define SYSTIMER_CNT (SYSTIMER_BASE+0x4)
#define SYSTIMER_CMP (SYSTIMER_BASE+0xC)
uint64_t systimer_counter()
{
return get32(SYSTIMER_CNT);
}
void systimer_sleep_one_second()
{
uint64_t current = systimer_counter();
while(1) if(systimer_counter() - current > 1000000) break;
}
void systimer_sleep_quarter_second()
{
uint64_t current = systimer_counter();
while(1) if(systimer_counter() - current > 250000) break;
}
```
### power
```clike
#define PM_WDOG_MAGIC 0x5a000000
#define PM_RSTC_FULLRST 0x00000020
void reset()
{
unsigned int r;
// trigger a restart by instructing the GPU to boot from partition 0
r = (*PM_RSTS) & ~0xfffffaaa;
*PM_RSTS = PM_WDOG_MAGIC | r; // boot from partition 0
*PM_WDOG = PM_WDOG_MAGIC | 10;
*PM_RSTC = PM_WDOG_MAGIC | PM_RSTC_FULLRST;
}
```
### get image then save to SD card
```clike
// Waiting
for (int i = 0; i < 24; i++) {
char c;
systimer_sleep(1);
if(uart_dataready()) {
// get image size
uint32_t size = 0;
for(int i=0; i<4; ++i)
{
c = uart_getc();
uart_send(c);
size = size << 8;
size = size + c;
}
// save the image data
char* data = (char *)0x90000;
char* bp = data;
for(int s=0; s<size; ++s) {
*bp = uart_getc();
uart_send(*bp);
bp += 1;
}
systimer_sleep(1);
uart_send('#');
// Overwrite the original image file
FIL fdst;
FRESULT res = f_open(&fdst, "0:/kernel8.img", FA_CREATE_ALWAYS | FA_WRITE);
if (res != FR_OK)
{
systimer_sleep(4);
reset();
return;
}
uint32_t sizewrite = 0;
res = f_write(&fdst, (void *)data, size, (unsigned int*)&sizewrite);
f_close(&fdst);
}
}
```
## Kernel Initialization (mini uart & GPIO)
## Processor Initialization
### Exception Level
`ARMv8` 定義了四個例外層級。EL0-EL3，數字越大權限(privilege)越高。
* `EL0` 用於應用程式。無特權模式(unprivileged)
作業系統為了 process 的隔離，所以要負責例外層級的處理。
user process 不應該能夠 access 到其他 process data。 為了達到上述行為，作業系統始终在` EL0` 上執行每個 user porcess。
* `EL1` 用於作業系統本身。作業系統核心模式(OS kernel mode)
* `EL2` 用於使用虛擬機監控程式的場景。虛擬機器監視器模式(Hypervisor mode)
* `EL3` TrustZone® monitor mode
### 查詢當前的 Exception Level
確認 `CurrentEL` system register ([utils.S](https://github.com/tingggggg/OSDIg/blob/main/l2_Processor_Initialization/src/utils.S))
```assembly
.globl get_el
get_el:
mrs x0, CurrentEL
lsr x0, x0, #2
ret
```
在尚未進行任何切換動作，當前的 Exception Level 應該為 `3`
```c
int el = get_el();
printf("Exception level: %d \r\n", el);
```
```shell
Exception level：3
```
### 切換當前的 Exception Level
在 `ARM architecture` 下只有當發生異常時，才能夠更改當前的 `EL`。執行某些非法指令(例如: access 不存在的 address)則可以觸發。另外還有 `interrupts` 也被視為特殊類型的異常。
每當有異常時就會觸發下列的動作
1. 當前指令的 address 保存在 `ELR_ELn` register (`Exception link register`)
2. 當前處理器狀態保存在 `SPSR_ELn` register (`Saved Program Status Register`)
3. `exception handler` 執行所需的任何工作
4. `exception handler` 呼叫 `eret` 指令。該指令從 `SPSR_ELn` 恢復處理器狀態，並且從保存在 `ELR_ELn` register 中的 address 開始恢復執行
**需要注意的點是 `exception handler` 並沒有一定要返回到異常所源自的相同位置。若有必要，`exception handler` 能夠對 `ELR_ELn` & `SPSR_ELn` 的內容進行修改。**
### 切換到 `EL1`
`EL1` 層具有執行所有常見 `OS` 任務的正確特權(privilege)集合，所以將作業系統切換到 `EL1` 是很直觀的
檢視 [boot.S](https://github.com/tingggggg/OSDIg/blob/main/l2_Processor_Initialization/src/boot.S)
```assembly
master:
ldr x0, =SCTLR_VALUE_MMU_DISABLED
msr sctlr_el1, x0
ldr x0, =HCR_VALUE
msr hcr_el2, x0
ldr x0, =SCR_VALUE
msr scr_el3, x0
ldr x0, =SPSR_VALUE
msr spsr_el3, x0
adr x0, el1_entry
msr elr_el3, x0
eret
```
如上 `master` function 主要進行一些 system register 的設置
* SCTLR_EL1, System Control Register (EL1), Page 2654 of [AArch64-Reference-Manual](https://developer.arm.com/docs/ddi0487/ca/arm-architecture-reference-manual-armv8-for-armv8-a-architecture-profile).
* `SCTLR_I_CACHE_DISABLED (0 << 12)` 與 `SCTLR_D_CACHE_DISABLED (0 << 2)` 禁用指令與數據 cache
* `SCTLR_MMU_DISABLED (0 << 0)` 禁用 MMU
```c
#define SCTLR_RESERVED (3 << 28) | (3 << 22) | (1 << 20) | (1 << 11)
#define SCTLR_EE_LITTLE_ENDIAN (0 << 25)
#define SCTLR_EOE_LITTLE_ENDIAN (0 << 24)
#define SCTLR_I_CACHE_DISABLED (0 << 12)
#define SCTLR_D_CACHE_DISABLED (0 << 2)
#define SCTLR_MMU_DISABLED (0 << 0)
#define SCTLR_MMU_ENABLED (1 << 0)
#define SCTLR_VALUE_MMU_DISABLED (SCTLR_RESERVED | SCTLR_EE_LITTLE_ENDIAN | SCTLR_I_CACHE_DISABLED | SCTLR_D_CACHE_DISABLED | SCTLR_MMU_DISABLED)
```
* HCR_EL2, Hypervisor Configuration Register (EL2), Page 2487 of [AArch64-Reference-Manual](https://developer.arm.com/docs/ddi0487/ca/arm-architecture-reference-manual-armv8-for-armv8-a-architecture-profile).
* 該 register 31 bit 控制 `EL1` 的執行狀態。`0` 為 `AArch32`，`1` 為 `AArch64`
```c
#define HCR_RW (1 << 31)
#define HCR_VALUE HCR_RW
```
* SCR_EL3, Secure Configuration Register (EL3), Page 2648 of [Arch64-Reference-Manual](https://developer.arm.com/docs/ddi0487/ca/arm-architecture-reference-manual-armv8-for-armv8-a-architecture-profile).
* 該 register 負責 security 的設置
```c
#define SCR_RESERVED (3 << 4)
#define SCR_RW (1 << 10)
#define SCR_NS (1 << 0)
#define SCR_VALUE (SCR_RESERVED | SCR_RW | SCR_NS)
```
* SPSR_EL3, Saved Program Status Register (EL3), Page 389 of [Arch64-Reference-Manual](https://developer.arm.com/docs/ddi0487/ca/arm-architecture-reference-manual-armv8-for-armv8-a-architecture-profile).
* 該 register 保存了處理器狀態，執行 `eret` 後會恢復該狀態。當 `EL3` 發生異常會自動保存 `spsr_el3`。**而其為 writeable，所以可以透過重寫它來達成切換 `EL` 的目的**
* `SPSR_MASK_ALL (7 << 6)` 切換成 `EL1` 後，所有類型的中斷都將被禁用(masked)
* 6 ~ 8 bit 分別為 `FIQ mask bit`, `IRQ mask bit`, `SError interrupt mask bit`
* `SPSR_EL1h (5 << 0)` 設置為 `EL1h` 模式
* `0` bit 用來選擇 `SP`。 "0 means the SP is always SP0" & "1 means the exception SP is determined by the EL"
```c
#define SPSR_MASK_ALL (7 << 6) // change EL to EL1
#define SPSR_EL1h (5 << 0) // EL1h mode means that we are using EL1 dedicated stack pointer
#define SPSR_VALUE (SPSR_MASK_ALL | SPSR_EL1h)
```
* ELR_EL3, Exception Link Register (EL3), Page 351 of [AArch64-Reference-Manual](https://developer.arm.com/docs/ddi0487/ca/arm-architecture-reference-manual-armv8-for-armv8-a-architecture-profile).
* `elr_el3` 保存了 address，在執行 `eret` 後則會返回到該 address
* 將 `el1_entry (即執行任務的 function)` 寫入上述 address
```
adr x0, el1_entry
msr elr_el3, x0
eret
```
```
el1_entry:
adr x0, bss_begin
adr x1, bss_end
sub x1, x1, x0
bl memzero
mov sp, #LOW_MEMORY
bl kernel_main
```
### Exercises
1. [Instead of jumping directly from EL3 to EL1, try to get to EL2 first and only then switch to EL1](https://github.com/tingggggg/OSDIg/tree/ex2.1).
2. [Remove 'general-regs-only' flag](https://github.com/tingggggg/OSDIg/tree/ex2.2).
***
## Interrupt Handing
### Interrupt & Exception
`ARM.v8 architecture` 有四種類型的異常
* Synchronous exception
由目前執行的指令引起(例如 `str` 將數據寫入不存在的記憶體位置)
* IRQ (Interrupt Request)
永遠是 asynchronous，意味著它與當前執行的指令無關。與 `Synchronous exception` 相反，它始終是由 external hardware 產生，而不是處理器本身生成的
* FIQ (Fast Interrupt Request)
為優先處理異常的目的而存在。能夠將部分中斷配置成 `normal`，其他中斷配置成 `fast`。Linux 中不使用 `FIQ`。
* SError (System Error)
與 `IRQ`, `FIQ` 一樣為 asynchronous，由 external hardware 產生。與 `IRQ`, `FIQ` 不同的是它永遠表示某種錯誤情況
### Exception vectors
每個異常類型都需要有自己的 handler。以異常 handler 的角度來看有四種執行狀態(execution states)，以在 `EL1` 工作，執行狀態可以定義如下
* **EL1t Exception is taken from EL1**(`EL1` 與 `EL0` 共享 stack pointer)
* 當 `SPSel` register 值為 0 時會發生
* **EL1h Exception is taken from EL1**
* 當 `SPSel` register 值為 1 時會發生(==也是我們當前使用的 mode==)
* **EL0_64 Exception is taken from EL0 executing in 64-bit mode**
* **EL0_32 Exception is taken from EL0 executing in 32-bit mode**
總共需要定義 16 個 `exception handler`(4 exception levels X 4 execution states)，而一個保存所有 `exception handler` address 的特殊結構稱為 `exception vector table` (`exception table`)
參考 page 1876 of the [AArch64-Reference-Manual](https://developer.arm.com/docs/ddi0487/ca/arm-architecture-reference-manual-armv8-for-armv8-a-architecture-profile)，每個異常佔用 `0x80` bytes
透過以下 macro `ventry` 建立異常 `exception table` 中的 entries
* 不直接在異常向量內部處理異常，而是跳轉到 macro 所提供的標籤
* 使用 `.align 7` 的目的是將所有的異常向量 offset 對齊 `0x80` bytes(如上圖所示)
```
.macro ventry label
.align 7
b \label
.endm
```
[entry.S](https://github.com/tingggggg/OSDIg/blob/main/l3_Interrupt_Handling/src/entry.S) 定義了 16 個異常向量。目前雖然只處理 `EL1h` 的 `IRQ`，仍舊需要定義總共 16 個的 handler，目的是希望看到有意義的錯誤訊息，避免出現問題。針對目前不關注的錯誤型態透過 macro `handle_invalid_entry` 來處理
* 會準備三個參數(x0 ~ x2)，然後呼叫 `show_invalid_entry_message`
* `x0`: 主用使用 [entry.h](https://github.com/tingggggg/OSDIg/blob/main/l3_Interrupt_Handling/include/entry.h)中所定義的 0 ~ 15 的編號(index)，使得能夠準確的知道執行了哪個異常 process
* `x1`: ==最重要==的參數，`ESR`(Exception Syndrome Register)實際來自 `esr_el1` register，它包含了有關導致異常的原因與詳細訊息
* `x2`: 為在同步異常的情況下很重要的關鍵，它來自前面有提過的 `elr_el1` register，其中包含生成異常時已執行的指令 address。在同步異常中，該指令也就是導致異常的指令
* 最後透過 `show_invalid_entry_message` 能夠在畫面中顯示當前的異常
```
.macro handle_invalid_entry type
kernel_entry
mov x0, #\type
mrs x1, esr_el1
mrs x2, elr_el1
bl show_invalid_entry_message
b err_hang
.endm
```
### Saving register state
當 `exception handler` 處理完成後會希望所有 `general register` 保持與生成異常前相同的值，若不實現此功能可能會產生不可預測的錯誤。於是透過 macro `kernel_entry` 來實現
* 將 register `x0 - x30` 保存到 stack
* 有對應的 `kernel_exit` 從 stack 恢復先前保存的 processor 狀態
```
.macro kernel_entry
sub sp, sp, #S_FRAME_SIZE
stp x0, x1, [sp, #16 * 0]
stp x2, x3, [sp, #16 * 1]
stp x4, x5, [sp, #16 * 2]
stp x6, x7, [sp, #16 * 3]
stp x8, x9, [sp, #16 * 4]
stp x10, x11, [sp, #16 * 5]
stp x12, x13, [sp, #16 * 6]
stp x14, x15, [sp, #16 * 7]
stp x16, x17, [sp, #16 * 8]
stp x18, x19, [sp, #16 * 9]
stp x20, x21, [sp, #16 * 10]
stp x22, x23, [sp, #16 * 11]
stp x24, x25, [sp, #16 * 12]
stp x26, x27, [sp, #16 * 13]
stp x28, x29, [sp, #16 * 14]
str x30, [sp, #16 * 15]
.endm
```
### Setting the vector table
準備完 `exception table` 後需將其 address 設置於 `vbar_el1` (Vector Base Address Register)
```
.globl irq_vector_init
irq_vector_init:
adr x0, vectors // load VBAR_EL1 with virtual
msr vbar_el1, x0 // vector table address
ret
```
### Masking / Unmasking interrupts
在特定的程式碼段==絕對不能被異步中斷攔截==。例如 `kernel_entry` 中進行 general register 的狀態保存，若執行到一半被攔截中斷，processor 的狀態將會被覆蓋、遺失。因此，每當執行 exception handler 時 processor 會自動禁用所有類型的 interrupts
[irq.S](https://github.com/tingggggg/OSDIg/blob/main/l3_Interrupt_Handling/src/irq.S) 中的兩個函式負則 masking & unmasking
```
.globl enable_irq
enable_irq:
msr daifclr, #2
ret
.globl disable_irq
disable_irq:
msr daifset, #2
ret
```
ARM processor state 有 4 位，負責控制不同類型中斷的 mask 狀態
* D: Masks debug exceptions. 為特殊類型的 `synchronous exceptions`
* A: Masks `SErrors`。之所以命名為 `A` 是因為 `SError` 也被稱為 `asynchronous aborts`
* I: Masks `IRQs`
* F: Masks `FIQs`
`daifclr` & `daifset` 都設置 `#2` 的原因是目前只設置 `I` 位
### Configuring interrupt controller
`interrupt controller` 能夠啟用/禁用 hardware 發送的 interrupt。
* 通過 `ENABLE_IRQS_1` register 控制啟用/禁用 interrupts
```
...
#define ENABLE_IRQS_1 (PBASE+0x0000B210)
#define ENABLE_IRQS_2 (PBASE+0x0000B214)
...
#define SYSTEM_TIMER_IRQ_0 (1 << 0)
#define SYSTEM_TIMER_IRQ_1 (1 << 1)
...
```
```
void enable_interrupt_controller()
{
put32(ENABLE_IRQS_1, SYSTEM_TIMER_IRQ_1);
}
```
### Generic IRQ handler
在 handler 中透過 `IRQ_PENDING_1` register 來獲取 `0-31` 的中斷狀態。透過該 register 能夠檢查當前的中斷是由 timer 產生或者其他 devices，進一步呼叫特定的中斷 handler。
多個中斷可能同時產生，因此每個中斷的 handler 必須確認是否已經完成對於中斷的處理。
```
void handle_irq(void)
{
unsigned int irq = get32(IRQ_PENDING_1);
switch (irq) {
case (SYSTEM_TIMER_IRQ_1):
handle_timer_irq();
break;
default:
printf("Unknown pending irq: %x\r\n", irq);
}
}
```
### Timer(System Timer) initialization
Raspberry Pi 的 system timer 具有連接到中斷控制器的 4 條中斷線和 4 個相應的 compare register。當計數器的值等於儲存在 compare register 之一中的值時，就會觸發相對應的中斷。因此需要對 compare register 之一進行非零值的初始化。
```
void timer_init(void)
{
curVal = get32(TIMER_CLO);
curVal += interval;
put32(TIMER_C1, curVal); // set first time of interrupt
}
```
### Handling timer interruputs
第一步更新下一次觸發中斷的時間。
再來將 `1` 寫入 `TIMER_CS` register(稱為 "Timer Control/Status" register)，用於確認來自 4 條中斷線中第 `1` 條的中斷
```
void handle_timer_irq( void )
{
curVal += interval;
put32(TIMER_C1, curVal);
put32(TIMER_CS, TIMER_CS_M1);
printf("Timer interrupt received\n\r");
}
```
### Exercises
1. [Use local timer instead of the system timer to generate processor interrupts](https://github.com/tingggggg/OSDIg/tree/ex3.1).
2. [Handle MiniUART interrupts](https://github.com/tingggggg/OSDIg/tree/ex3.2).
***
## Processor Scheduler
Process scheduling 是核心任務之一。Scheduling 指的是一個 OS 應該要能夠實現不同 processes 共享 CPU time。其中最困難的事一個 process 不知道 scheduling 的發生，也就是説它將自己視為唯一佔用 CPU 的 process
### task_struct
如果要管理 processes，首先要做的就是建立一個描述 process 的 struct，而在 [Linux](https://elixir.free-electrons.com/linux/v2.6.38.8/source/include/linux/sched.h#L1193) 中就具有這樣的 struct，它稱為 `task_struct`。參考與模仿 Linux 中的實現方式如下
這個 struct 具有以下內容：
* `cpu_context`
* 其為另一個獨立的 struct，其中包含正在切換的任務之間可能不同的所有 register 之值。
* 不保存所有的 register，只保存了 `x19-x30`(fp: `x29`, pc: `x30`) 和 `sp` 的原因是根據 ARM 的調用約定，`x0-x18` registers ==可以被調用的函式覆蓋==，所以不得假定這些 registers value 在調用結束後仍然存在
* `state`
* 當前運行任務的狀態(執行、等待...)
* `counter`
* 用於確認當前任務運行的時間，timer tick 時會減 1，到 0 時會切換其他任務
* `priority`
* 安排新任務時將 `priority` 複製到 `counter`
* 通過優先級的設定，能夠調整、安排任務相對其他任務獲得的 `processor time`
* `preempt_count`
* 若該值設置為非零值，表示當前任務正在值行不可中斷的功能。或忽略該任務期間發生的 timer tick，而且不會 rescheduling
```
struct cpu_context {
unsigned long x19;
unsigned long x20;
unsigned long x21;
unsigned long x22;
unsigned long x23;
unsigned long x24;
unsigned long x25;
unsigned long x26;
unsigned long x27;
unsigned long x28;
unsigned long fp;
unsigned long sp;
unsigned long pc;
};
struct task_struct {
struct cpu_context cpu_context;
long state;
long counter;
long priority;
long preempt_count;
};
```
kernel 啟動後只有一個任務是執行中的狀態，也就是 `kernel_main` function。稱其為 "init task" ，在開啟 scheduling 之前，首先必須填充 "init task" 相對應的 `task_struct`
```c
#define INIT_TASK \
/*cpu_context*/ { {0,0,0,0,0,0,0,0,0,0,0,0,0}, \
/* state etc */ 0,0,1, 0 \
}
static struct task_struct init_task = INIT_TASK;
```
所有任務存放在 `task`。另外透過一個 struct pointer `current` 指向 `init task`
```c
#define NR_TASKS 64
struct task_struct *task[NR_TASKS] = {&(init_task), };
struct task_struct *current = &(init_task);
```
### `kernel_main` function
需要關注的重點
* `copy_process()` 使用兩個參數，新 thread 中要執行的函式以及傳遞給該函式的參數。`copy_process` 會建立新的 `task_struct` 使其能夠被 scheduler 調度
* `schedule()` 是主要的調度 process 功能。它檢查是否有新任務需要搶佔當前的任務。timer interrupt handler 也會呼叫 `schedule`
```c
void kernel_main(void)
{
uart_init();
init_printf(0, putc);
irq_vector_init();
timer_init();
enable_interrupt_controller();
enable_irq();
int res = copy_process((unsigned long)&process, (unsigned long)"12345");
if (res != 0) {
printf("error while starting process 1");
return;
}
res = copy_process((unsigned long)&process, (unsigned long)"abcde");
if (res != 0) {
printf("error while starting process 2");
return;
}
while (1){
schedule();
}
}
```
呼叫了兩次 `copy_process()` 都使用 `process` 函式傳入。`process` 會不斷 print 出傳入的參數
```c
void process(char *array)
{
while (1){
for (int i = 0; i < 5; i++){
uart_send(array[i]);
delay(100000);
}
}
}
```
### Memory allocation
每個任務都應該具有屬於自己的獨立 stack，因此在建立新任務需要進行正確的記憶體分配。透過以下的方法進行記憶體分配
* 分配器與記憶體頁面搭配使用
* `mem_map` array 保存了每一個記憶體頁面的使用狀態。每當要分配新的頁面時 loop through 這個 array 獲取第一個空閒頁面
* `HIGH_MEMORY`: 系統中的記憶體總量為 `1 GB` 減去最後的 device registers 保留位
* `LOW_MEMORY`: 前 `4 MB` 的記憶體保留給 kernel image 和 init task。所有的 memory allocation 由此開始
* `PAGE_SIZE` 定義為 `4 KB`
```c
#define PAGE_SHIFT 12
#define TABLE_SHIFT 9
#define SECTION_SHIFT (PAGE_SHIFT + TABLE_SHIFT)
#define PAGE_SIZE (1 << PAGE_SHIFT) // 4 KB
#define SECTION_SIZE (1 << SECTION_SHIFT)
#define LOW_MEMORY (2 * SECTION_SIZE)
#define HIGH_MEMORY PBASE
#define PAGING_MEMORY (HIGH_MEMORY - LOW_MEMORY)
#define PAGING_PAGES (PAGING_MEMORY / PAGE_SIZE)
```
```c
static unsigned short mem_map [ PAGING_PAGES ] = {0,};
unsigned long get_free_page()
{
for (int i = 0; i < PAGING_PAGES; i++){
if (mem_map[i] == 0){
mem_map[i] = 1;
return LOW_MEMORY + i*PAGE_SIZE;
}
}
return 0;
}
void free_page(unsigned long p){
mem_map[p / PAGE_SIZE] = 0;
}
```
### Creating a new task
透過 `copy_process` 來建立新任務
* `preempt_diable()` 禁用"搶佔"，避免在執行過程被切換到其他任務
* 透過 `get_free_page()` 分配一個尚未被使用的 page。在此 page 底部放置新任務的 `task_struct`
* 分配好 `task_struct` 後，初始化其屬性
* `priority` 和 `counter` 根據當前任務的 `priority` 來設置
* `state` 設置為 `TASK_RUNNING`，表示新任務已經準備好開始
* `preempt_count` 設置為 `1`，表示在執行任務之後，在完成特定初始化工作之前，不進行任務的切換
* 初始化 `cpu_context`
* 將 stack 設置在新 page 的頂端 (`THEAD_SIZE` = `PAGE_SIZE` = `4 KB`)
* `pc` 設置為 `ret_from_fork` function
* 將新創的任務加入到 task array
* 創建完成後，將==當前==任務的搶佔開啟
```c
int copy_process(unsigned long fn, unsigned long arg)
{
preempt_disable();
struct task_struct *p;
p = (struct task_struct *) get_free_page();
if (!p)
return 1;
p->priority = current->priority;
p->state = TASK_RUNNING;
p->counter = p->priority;
p->preempt_count = 1; //disable preemtion until schedule_tail
p->cpu_context.x19 = fn;
p->cpu_context.x20 = arg;
p->cpu_context.pc = (unsigned long)ret_from_fork;
p->cpu_context.sp = (unsigned long)p + THREAD_SIZE;
int pid = nr_tasks++;
task[pid] = p;
preempt_enable();
return 0;
}
```
* `ret_from_fork` function
* 呼叫 `schedule_tail` function 來啟用搶佔
* 然後使用保存在 `x20` register 中的參數來執行 `x19` register 的函式
* ==??? ???== 在呼叫 `ret_from_fork` 之前，從 `cpu_context` 恢復 `x19`, `x20`
```assembly
.globl ret_from_fork
ret_from_fork:
bl schedule_tail
mov x0, x20
blr x19 //should never return
```
```c
void schedule_tail(void) {
preempt_enable();
}
```
以上過程僅僅是建立新任務到 task array，完成創建後並不會發生切換任務，待後續 `schedule` 才會執行新任務
### Scene of calling `schedule` function
1. 當前任務沒有任何事情要做(事情做完)，但仍舊不能終止時。
2. `schedule` 呼叫被加入 timer interrupt handler 中，來定時執行
`timer_tick` 被 interrupt handler 呼叫
* 首先將當前任務 `counter` 減一，若 `counter` 大於 `0` 或者當前當前任務禁用搶佔，則返回(不做任何事)，否則呼叫 `schedule` 並啟用中斷。
```c
void handle_timer_irq(void)
{
curVal += interval;
put32(TIMER_C1, curVal); // update for next interrupt
put32(TIMER_CS, TIMER_CS_M1);
timer_tick();
}
```
```c
void timer_tick()
{
--current->counter;
if (current->counter > 0 || current->preempt_count > 0) {
return;
}
current->counter = 0;
enable_irq();
_schedule();
disable_irq();
}
```
### Scheduling algorithm
`schedule` 演算法參考 [Linux kernel 第一個發行版的作法](https://github.com/zavg/linux-0.01/blob/master/kernel/sched.c#L68)
工作原理如下
1. 第一個內部 `for` loop through 所有任務，目的是找到 ==`counter` 最大處於 `TASK_RUNNING` 狀態的任務==。若找到該條件任務則會跳出外部 `while`，然後切換到該任務。
2. 若經過第一個內部 `for` 沒找到符合條件任務，有兩種可能
* (1)沒有 `TASK_RUNNING` 狀態任務
* e.g 所有任務都在等待中斷
* (2)任務的 `counter` 皆為 `0`
3. 若發生步驟 2 得情況，將會執行第二個內部 `for` ，對每個任務增加其 `counter`
* 任務通過第二個 `for` 迭代次數越多，其 `counter` 越高
* 任務 `counter` 限制不會大於 `2 * priority`
4. 隨著 `while` 執行，
* 若==至少有一個任務==處於 `TASK_RUNNING` 狀態，則 `while` 迭代的二次就會結束，因為第一次的迭代讓所有任務 `counter` 不為 `0`
* 若==沒有任務==處於 `TASK_RUNNING`，則 `while` 將會不斷運行直到某個任務轉換成 `TASK_RUNNING` 狀態。
:::info
==需要思考的部分==是若在單個 CPU 上運行，在執行這個 `while` 時該如何更改任務狀態？
這就能夠理解為什麼執行 `schedule` 時必須==啟用中斷(`enable_irq`)==，中斷會發生執行 `schedule` 期間，interrupt handler 可以更改任務的狀態，更改==某些在等待中斷的任務狀態==
:::
```c
void _schedule(void)
{
preempt_disable();
int next,c;
struct task_struct * p;
while (1) {
c = -1;
next = 0;
for (int i = 0; i < NR_TASKS; i++){
p = task[i];
if (p && p->state == TASK_RUNNING && p->counter > c) {
c = p->counter;
next = i;
}
}
if (c) {
break;
}
for (int i = 0; i < NR_TASKS; i++) {
p = task[i];
if (p) {
p->counter = (p->counter >> 1) + p->priority;
}
}
}
switch_to(task[next]);
preempt_enable();
}
```
### Switching tasks
找到 `counter` 非零且處於 `TASK_RUNNING` 狀態的任務後，呼叫 `switch_to` 來切換任務
* 首先檢查要切換的任務與當前任務是否不為同一個，不同才進行切換動作
```c
void switch_to(struct task_struct * next)
{
if (current == next)
return;
struct task_struct * prev = current;
current = next;
cpu_switch_to(prev, next);
}
```
實際的切換工作呼叫了 `cpu_switch_to`
* `THREAD_CPU_CONTEXT` 為 `task_struct` 中 `cpu_context` 結構的偏移量，其為 constant `0`
* `add x8, x0, x10`
* `x0` 指向第一個參數的 pointer，也就是當前任務的 `task_sturct`
* `x8` 指向當前任務的 `cpu_context`
* `mov x9, sp` 將 `x9` register 指向當前 stack pointer
```assembly
.globl cpu_switch_to
cpu_switch_to:
mov x10, #THREAD_CPU_CONTEXT
add x8, x0, x10
mov x9, sp
stp x19, x20, [x8], #16 // store callee-saved registers
stp x21, x22, [x8], #16
stp x23, x24, [x8], #16
stp x25, x26, [x8], #16
stp x27, x28, [x8], #16
stp x29, x9, [x8], #16
str x30, [x8]
add x8, x1, x10
ldp x19, x20, [x8], #16 // restore callee-saved registers
ldp x21, x22, [x8], #16
ldp x23, x24, [x8], #16
ldp x25, x26, [x8], #16
ldp x27, x28, [x8], #16
ldp x29, x9, [x8], #16
ldr x30, [x8]
mov sp, x9
ret
```
* 透過 [stp](https://https://developer.arm.com/documentation/dui0801/h/A64-Data-Transfer-Instructions/STP) 指令將 `callee-saved` registers 按照 `cpu_context` 的順序==保存==
* `stp x19, x20, [x8], #16` 從 `x19` 開始寫回 `cpu_context`，依照 `cpu_context` 順序
* `stp x29, x9, [x8], #16` 將 `x9` 寫回 `cpu_context` 的 `sp` (`x29` 為 frame pointer)
* `str x30, [x8]` 從 `x30` 寫回 `cpu_context` 的 `pc` (保存了函式返回的 address)
```assembly
mov x9, sp
stp x19, x20, [x8], #16 // store callee-saved registers
stp x21, x22, [x8], #16
stp x23, x24, [x8], #16
stp x25, x26, [x8], #16
stp x27, x28, [x8], #16
stp x29, x9, [x8], #16
str x30, [x8]
```
* 透過 [ldp](https://developer.arm.com/documentation/ddi0596/2020-12/Base-Instructions/LDP--Load-Pair-of-Registers-) 指令將 `callee-saved` registers 按照 `cpu_context` 的順序==恢復==
* 首先從 `x1` 下一個任務 address 加上 `THREAD_CPU_CONTEXT` 保存到 `x8`
* `ldp x19, x20, [x8], #16` 從 `x19` 開始讀回 `cpu_context`
* 並把 `sp` 指向下一個任務 `cpu_context` 中的 `sp`
```assembly
add x8, x1, x10
ldp x19, x20, [x8], #16 // restore callee-saved registers
ldp x21, x22, [x8], #16
ldp x23, x24, [x8], #16
ldp x25, x26, [x8], #16
ldp x27, x28, [x8], #16
ldp x29, x9, [x8], #16
ldr x30, [x8]
mov sp, x9
```
* `ret` 後返回到 link register (`x30`) 所指向的 address
* 若某個任務==第一次被切換到==，其實就是執行 `ret_from_fork`。
因為在 `copy_process` 創建新任務時，執行了 `pc` 的初始化
`p->cpu_context.pc = (unsigned long)ret_from_fork`
* 第二次以後的執行(==再次被切換到==)，就會恢復到上次停止的 address(`pc`)
### How scheduling works with exception entry/exit?
原本的 [kernel_entry](https://github.com/tingggggg/OSDIg/blob/73d18fbe3920c4a2c94b6936fd80679c12285fab/l3_Interrupt_Handling/src/entry.S#L17) & [kernel_exit](https://github.com/tingggggg/OSDIg/blob/73d18fbe3920c4a2c94b6936fd80679c12285fab/l3_Interrupt_Handling/src/entry.S#L37) 進行 registers 的保存和恢復。加入 `scheduler` 後能夠將 interrupt handler 視為一個 task，能夠在處理 interrupt 時切換任務，而 interrupt 的返回 `eret` 依賴以下兩個 registers
* `elr_el1` : 返回的 address
* `spsr_el1` : 處理器狀態
因此要在處理 interrupt 中切換任務，需要進行以上==兩個 registers== 和 gerneral registers 的保存與恢復
* `elr_el1` address 寫入對應 `cpu_context` 結構的 `pc`
* `spsr_el1` 狀態寫入對應 `task_struct` 結構的 `state`
```assembly
.macro kernel_entry
...
stp x28, x29, [sp, #16 * 14]
mrs x22, elr_el1
mrs x23, spsr_el1
stp x30, x22, [sp, #16 * 15]
str x23, [sp, #16 * 16]
.endm
```
```assembly
.macro kernel_exit
ldr x23, [sp, #16 * 16]
ldp x30, x22, [sp, #16 * 15]
msr elr_el1, x22
msr spsr_el1, x23
ldp x0, x1, [sp, #16 * 0]
...
add sp, sp, #S_FRAME_SIZE
eret
.endm
```
### Exercises
1. [Add printf to all main kernel functions to output information about the curent memory and processor state](https://github.com/tingggggg/OSDIg/tree/ex4.1).
2. [Introduce a way to assign priority to the tasks](https://github.com/tingggggg/OSDIg/tree/ex4.2).
3. [Allow user processes to use FP/SIMD registers](https://github.com/tingggggg/OSDIg/tree/ex4.3).
4. [Allow the kernel to have an unlimited number of tasks through linked list](https://github.com/tingggggg/OSDIg/tree/ex4.4).
***
## User Processes System call
為了 processes 的隔離，需要將所有 user processes 移至 EL0，這能夠限制它們對 `privileged processor operations` 的訪問
另外提供 API(`system call`) 給 user processes 來 print 出相關訊息
### System calls implementation
每個 `system call` 都是 `synchronous exception`。如果 user process 需要執行 `system call` 必須準備必要的參數，然後呼叫 `svc` command。
`svc` 會生成 `synchronous exception`，並由 OS 在 EL1 處理。目前實作的 OS 定義 4 個 `system call`:
1. `write`: 使用 UART device 在畫面上顯示出訊息
2. `clone`: 創建一個新的 user thread
3. `malloc`: 為 user process 分配新的 memory page
4. `exit`: 每個 process 執行完後必須呼叫此 `system call`，進行必要的清理
* 所有在 `system calls` 在 [sys.c](https://github.com/tingggggg/OSDIg/blob/main/l5_UserProcesses_SystemCalls/src/sys.c)
* [sys_call_table](https://github.com/tingggggg/OSDIg/blob/85f1906839722cd6c03c062b70bc337e690d0fb8/l5_UserProcesses_SystemCalls/src/sys.c#L31) 指向所有 `system calls` handlers
* 以 `write` 為例
* 將 `system call` 的 index 存放在 `w8` register
* 透過 `svc` 生成 `synchronous exception`
* ==使用的慣例== `x0 ~ x7` 用於呼叫 `system call` 的參數， `x8` or `w8` 用於呼叫 `system call` 的 index
```assembly
.globl call_sys_write
call_sys_write:
mov w8, #SYS_WRITE_NUMBER
svc #0
ret
```
### Handling synchronous exceptions
產生 `synchronous exception` 後，會呼叫已註冊的對應 handler
* 首先呼叫 `kernel_entry`
* 檢查 `esr_el1` (Exception Syndrome Register)。該 register 包含 "exception class"，如果 `"exception class" == ESR_ELx_EC_SVC64` 表示當前的異常由 `svc` 產生
* 若符合 `ESR_ELx_EC_SVC64` 會進一步執行 `el0_svc`，否則顯示錯誤
```assembly
el0_sync:
kernel_entry 0
mrs x25, esr_el1 // read the syndrome register
lsr x24, x25, #ESR_ELx_EC_SHIFT // exception class
cmp x24, #ESR_ELx_EC_SVC64 // SVC in 64-bit state
b.eq el0_svc
handle_invalid_entry 0, SYNC_ERROR
```
`el0_svc` 執行的工作
* 將 `system call` table 加載到 `stbl`
* 將呼叫的 `system call` index 加載到 `scno`
* 起用中斷 `enable_irq`
* 檢查呼叫的 index 是否合法 (< `sc_nr`)，若不合法則報錯
* `system call` handler 存入 `x16` ==(stbl + (scno * 8))==
* 最後執行 handler，並在完成後呼叫 `ret_from_syscall`
```assembly
sc_nr .req x25 // number of system calls
scno .req x26 // syscall number
stbl .req x27 // syscall table pointer
el0_svc:
adr stbl, sys_call_table // load syscall table pointer
uxtw scno, w8 // syscall number in w8
mov sc_nr, #__NR_syscalls
bl enable_irq
cmp scno, sc_nr // check upper syscall limit
b.hs ni_sys
ldr x16, [stbl, scno, lsl #3] // address in the syscall table
// [stbl, scno, lsl #3] = stbl + (scno * 8)
// size of void pointer is 8
blr x16 // call sys_* routine
b ret_from_syscall
ni_sys:
handle_invalid_entry 0, SYSCALL_ERROR
```
`ret_from_syscall` 首先禁用中斷，然後將 `x0` register value 存入 stack
(==???== 因為接下來要執行的 `kernel_exit` 將從 stack 恢復 general register value，而希望將原 `x0` value 回傳到 user code)
```assembly
ret_from_syscall:
bl disable_irq
str x0, [sp, #S_X0] // returned x0
kernel_exit 0
```
### Switching between EL0 and EL1
兩個 macro `kernel_entry` & `kernel_exit` 更新為能夠接受==一個傳入參數==
* `EL0` 與 `EL1` 使用不同的 stack，此處 `EL0` 使用了原始 stack `sp_el0`，因此在發生異常後 stack pointe 會被覆蓋，所以需要在發生異常的前/後，保存/恢復該 register 的值
* `EL1` 中獲取異常不恢復 stack pointer，原因是在異常處理過程中發生 context switch，在 `kernel_exit` 時， sp 已經被 `cpu_switch_to` 切換
* 不需要在執行 `eret` 前指定需要返回的 exception level，因為相個資訊儲存在 `spsr_el1` 中，==永遠都會返回到發生異常的 level==
```assembly
//kernel_entry
.if \el == 0
mrs x21, sp_el0
.else
add x21, sp, #S_FRAME_SIZE
.endif /* \el == 0 */
mrs x22, elr_el1
mrs x23, spsr_el1
########
//kernel_exit
.if \el == 0
msr sp_el0, x21
.endif /* \el == 0 */
msr elr_el1, x22
msr spsr_el1, x23
```
### Moving a task to user mode
使用任何 `system call` 之前，首先需要有在 `user mode` 下執行的任務。能夠將 kernel task 移動至 `user mode` 來達成
`kenel_main` 函式中，創建一個新的 kernel thread，將在 scheduler 開始後，在 kernel model 執行 `kernel_process` 函式
```c
int res = copy_process(PF_KTHREAD, (unsigned long)&kernel_process, 0, 0);
if (res < 0) {
printf("error while starting kernel process");
return;
}
```
```c
void kernel_process(){
printf("Kernel process started. EL %d\r\n", get_el());
int err = move_to_user_mode((unsigned long)&user_process);
if (err < 0){
printf("Error while moving process to user mode\n\r");
}
}
```
先前創建新任務在 stack 頂部保留一個區域 (`pt_regs 區域`)，將會在這裡被使用到
`pt_regs` struct 的初始化 (這個區域與 `kernel_exit` 期望的格式相符合)
* `pc` 指向需要在 user mode 下執行的工作。`kernel_exit` 將把 `pc` 複製到 `elr_el1` register 確保從異常返回後回到 `pc` address
* `pstate` 由 `kernel_exit` 複製到 `spsr_el1`，異常返回後成為處理器狀態。 `PSR_MODEL_EL0t` constant 將異常返回到 `EL0`
* `stack` 為 user stack 分配一個 page，並將 `sp` 指到 page 頂部
* `task_pt_regs` 用於計算 `pt_regs` 區域位置
```c
int move_to_user_mode(unsigned long pc)
{
struct pt_regs *regs = task_pt_regs(current);
memzero((unsigned long)regs, sizeof(*regs));
regs->pc = pc;
regs->pstate = PSR_MODE_EL0t;
unsigned long stack = get_free_page(); //allocate new user stack
if (!stack) {
return -1;
}
regs->sp = stack + PAGE_SIZE;
current->stack = stack;
return 0;
}
```
```c
struct pt_regs * task_pt_regs(struct task_struct *tsk)
{
unsigned long p = (unsigned long)tsk + THREAD_SIZE - sizeof(struct pt_regs);
return (struct pt_regs *)p;
}
```
### Forking user processes
`user_process` 透過 `move_to_user_mode` 後在 user mode 下執行
使用 `clone` system call 來啟用兩個任務。其中 `clone` 需要搭配 `malloc` 獲取的 stack address
* 保存 registers value `x0-x2`
* 呼叫 `sys_clone`
* 檢查 `sys_clone` 的返回值，
* 返回值 `0`，表示當前正在新創建的 kernel thread 中
* 返回值不為 `0`，表示其為任務 `PID`，在這裡即會直接返回
```assembly
.globl call_sys_clone
call_sys_clone:
/* Save args for the child. */
mov x10, x0 /*fn*/
mov x11, x1 /*arg*/
mov x12, x2 /*stack*/
/* Do the system call. */
mov x0, x2 /* stack */
mov x8, #SYS_CLONE_NUMBER
svc 0x0
cmp x0, #0
beq thread_start
ret
thread_start:
mov x29, 0
/* Pick the function arg and execute. */
mov x0, x11
blr x10
/* We are done, pass the return value through x0. */
mov x8, #SYS_EXIT_NUMBER
svc 0x0
```
`copy_process` 現在能夠處理 `kernel` or `user` thread，clone user thread 時會有新的處理
* `struct pt_regs * cur_regs = task_pt_regs(current)` 第一件事是訪問處理器狀態，該狀態由 `kernel_entry` 保存
* `*childregs = *cur_regs` 將當前處理器狀態複製到新任務的狀態。新狀態下 `x0` 設置為 0，因為調用者會將 `x0` 解釋為 system call 的返回值(使用此值來確定是否仍在執行原始的 thread 一部分 or 新 thread)
* 新任務的下一個 `sp` 指向新 user stack 的頂部
```diff
int copy_process(unsigned long clone_flags, unsigned long fn, unsigned long arg, unsigned long stack)
{
preempt_disable();
struct task_struct *p;
p = (struct task_struct *) get_free_page();
if (!p) {
return -1;
}
struct pt_regs *childregs = task_pt_regs(p);
memzero((unsigned long)childregs, sizeof(struct pt_regs));
memzero((unsigned long)&p->cpu_context, sizeof(struct cpu_context));
if (clone_flags & PF_KTHREAD) {
p->cpu_context.x19 = fn;
p->cpu_context.x20 = arg;
+ } else {
+ struct pt_regs * cur_regs = task_pt_regs(current);
+ *childregs = *cur_regs;
+ childregs->regs[0] = 0;
+ childregs->sp = stack + PAGE_SIZE;
+ p->stack = stack;
+ }
p->flags = clone_flags;
p->priority = current->priority;
p->state = TASK_RUNNING;
p->counter = p->priority;
p->preempt_count = 1; //disable preemtion until schedule_tail
p->cpu_context.pc = (unsigned long)ret_from_fork;
p->cpu_context.sp = (unsigned long)childregs;
int pid = nr_tasks++;
task[pid] = p;
preempt_enable();
return pid;
}
```
### Exiting a task
每個任務完成後，透過 `exit` system call，其呼叫了 `exit_process`，負責停止任務
* 依照 linux 傳統，並不會直接刪除任務，而是修改其狀態為 `TASK_ZOMBIE`。如此 schedule 不會在執行該任務。(==這種作法使得 `parent process` 即使在 `child process` 完成後也能夠查詢相關訊息==)
* 刪除不必要的 user stack 後執行 schedule 選擇下一個待執行任務
```c
void exit_process(){
preempt_disable();
for (int i = 0; i < NR_TASKS; i++){
if (task[i] == current) {
task[i]->state = TASK_ZOMBIE;
break;
}
}
if (current->stack) {
free_page(current->stack);
}
preempt_enable();
schedule();
}
```
### Exercises
1. [When a task is executed in user mode, try to access some of the system registers. Make sure that a synchronous exception is generated in this case](https://github.com/tingggggg/OSDIg/tree/ex5.1).
2. [Implement a new system call that can be used to set current task priority](https://github.com/tingggggg/OSDIg/tree/ex5.2).
***
Sign in with Wallet
Connect another wallet