# Tenok即時作業系統
###### tags: `articles`
**作者: [鄭聖文](http://wiki.csie.ncku.edu.tw/User/shengwen)**
**E-mail:** `shengwen1997.tw[at]gmail.com`
**本文章以 `創用CC 姓名標示─非商業性─相同方式分享` 授權**
如您願意參與協作或指證錯誤請聯繫我
**COSCUP 2023 演說: [Tenok: 打造用於機器人控制的微型即時作業系統](https://drive.google.com/file/d/1p8YJVPVwFAEknMXPbXzjj0y0p5qcqT2T/view?fbclid=IwAR2Xr0a5hKDGxEpMMvM0tQfdcMziAqR1vR7N-7Le-tUmbpUlYJcxVxQ0mcY)**
## I. 概要
`Tenok` 一詞在阿美族語中表示核心 (Kernel)，其啟發自成大資工系師生於2013年所創作的 [rtenv](https://github.com/embedded2014/rtenv) / [rtenv+](https://github.com/embedded2014/rtenv-plus)，後者被用於[嵌入式系統系列課程](http://wiki.csie.ncku.edu.tw/embedded/schedule)中作為教材。原先 Tenok 只是用於學習及重現 rtenv，但目前已強化了部分 rtenv 設計，可視為另一個作業系統開發的參考案例。
Tenok 亦參考了 [mini-arm-os](https://github.com/jserv/mini-arm-os) 以及 FreeRTOS，相較於 rtenv 有更完整的資源管理功能，且檔案系統基於 inode 邏輯，更加貼近於真實作業系統的設計。另外也包含了一個支援自動補齊、歷史檢索以及數個快捷鍵功能的 Shell 文字互動界面。
以下為 Tenok 的主要特徵以及功能:
* POSIX 風格的 API
* 同步機制: Spinlock, Mutex, Semaphore
* 行程間通訊: FIFO (Named pipe), Message Queue
* 支援浮點數運算單元 (Floating-point Unit, FPU)
* 內建 Shell 的文字互動介面
* 簡單的 rootfs 及 romfs 的檔案系統實做
Tenok 的原始碼以及展示影片可參見以下連結:
* [展示影片](https://www.youtube.com/watch?v=byWihWcMP00)
* [GitHub連結](https://github.com/shengwen-tw/tenok)
## II. 開發環境準備
Tenok 目前支援了 ARM Cortex-M4F 的硬體架構，建議使用的硬體開發板如下:
* [STM32F4DISCOVERY](https://www.st.com/en/evaluation-tools/stm32f4discovery.html)
* [32F429IDISCOVERY](https://www.st.com/en/evaluation-tools/32f429idiscovery.html)
除了實體硬體，您也可以使用 QEMU 進行實驗。
---
**參考實驗環境:** Ubuntu 20.04 (GNU/Linux 5.8.0)
1. 安裝所需套件:
```
sudo apt install build-essential git zlib1g-dev libsdl1.2-dev automake* autoconf* \
libtool libpixman-1-dev lib32gcc1 lib32ncurses5 libc6:i386 libncurses5:i386 \
libstdc++6:i386 libusb-1.0.0-dev ninja-build
```
2. 安裝 OpenOCD:
```
git clone git://git.code.sf.net/p/openocd/code openocd
cd openocd
./bootstrap
./configure --prefix=/usr/local --enable-jlink --enable-amtjtagaccel --enable-buspirate \
--enable-stlink --disable-libftdi
echo -e "all:\ninstall:" > doc/Makefile
make -j4
sudo make install
```
3. 安裝 GCC toolchain 9 (arm-none-eabi):
```
wget https://developer.arm.com/-/media/Files/downloads/gnu-rm/9-2019q4/gcc-arm-none-eabi-9-2019-q4-major-x86_64-linux.tar.bz2
tar jxf ./gcc-arm-none-eabi-9-2019-q4-major-x86_64-linux.tar.bz2
rm gcc-arm-none-eabi-9-2019-q4-major-x86_64-linux.tar.bz2
```
4. 安裝 QEMU:
```
git clone git://git.qemu.org/qemu.git
cd qemu
git submodule init
git submodule update --recursive
mkdir build
cd build
../configure
make -j $(nproc)
```
5. 編輯 `~/.bashrc` 並增加以下指令:
```
PATH=$PATH:${YOUR_PATH}/qemu/build
PATH=$PATH:${YOUR_PATH}/gcc-arm-none-eabi-9-2019-q4-major/bin
```
註: `${YOUR_PATH}` 須換成操作者的安裝路徑
6. 重啟終端機即可完成安裝
## III. 實驗步驟
### 3.1 下載原始碼
```
git clone https://github.com/shengwen-tw/tenok.git
cd tenok
```
### 3.2 使用 QEMU 模擬器
1. 打開 `Makefile` 並啟用以下設定:
```
include platform/qemu.mk
```
2. 編譯:
```
make
```
3. 啟動 QEMU 進行模擬:
```
make qemu
```
4. 若要使用 gdb 進行除錯，則再打開新的終端機並輸入:
```
make gdbauto
```
### 3.3 使用實體硬體
1. 將開發板的 PC10 (TX) 連接至 USB-TTL 模組的 RX, 開發板的 PC11 (RX) 連接至 USB-TTL 模組的 TX:
[圖] 32F429IDISCOVERY開發板
2. 打開 `Makefile` 並啟用以下其中一種設定:
```
include platform/stm32f4disc.mk #STM32F4DISCOVERY board
```
```
include platform/stm32f429disc.mk #32D4IDISCOVERY board
```
3. 編譯:
```
make
```
4. 將開發板透過 USB 連接至電腦並輸入以下指令進行燒錄:
```
make flash
```
5. 若要使用 gdb 進行除錯，則在終端機1輸入:
```
make openocd
```
6. 並在終端機2輸入:
```
make gdbauto
```
## IV. ARM Cortex-M4F 硬體機制
本章節將對 ARM Cortex-M4F 官方資料進行導讀。了解硬體機制對於設計作業系統至關重要。官方手冊的 PDF 檔可見**參考資料**一章。
---
幾個術語的釐清:
[圖] 來源: Cortex-M4 Devices Generic User Guide 1-4
| 名稱 | 說明 |
| -------- | -------- |
| Nested Vectored Interrupt Controller (NVIC) | ARM Cortex-M 處理器中的[中斷](https://zh.wikipedia.org/zh-tw/%E4%B8%AD%E6%96%B7) (Interrupt) 控制器，支援分組 (Grouping) 以及優先權分級 (Priority)，具有低延遲響應特性 |
| System Control Block (SCB)| 用於提供 CPU 資訊、CPU 控制、進行組態設定以及回報系統異常事件 (Exception) 的模組 |
| System timer | 系統時鐘，又稱 SysTick, 是一個24位元的下數定時器。用於實作即時作業系統 (RTOS) 中的時間 Tick 功能 |
| Floating-point Unit (FPU) | 浮點數運算單元 |
---
### 4.1 核心暫存器 (Core registers)
首先來了解 ARM Cortex-M4(F) 的核心暫存器的功能，請見下圖:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-3
以下進行摘錄說明:
| 暫存器 | 用途 |
| -------- | -------- |
| R0-R12 | 32位元的通用暫存器 |
| R13 (SP) | 即 Stack Pointer，包含 PSP (Process Stack Pointer) 及 MSP (Main Stack Pointer)。當前 SP 是 MSP 或是 PSP 須依情況而定 |
| R14 (LR)| 即 Link Register，用於保存函式呼返回 (Function return) 位址或是異常返回 (Exception return) 的設定值 |
| R15 (PC)| 即 Program Counter，其指向目前執行中的指令的位址|
| PRIMASK、FAULTMASK 及 BASEPRI | 用於控制中斷的啟動/關閉 |
| PSR | 即 Program Status Register，其包含了 APSR，IPSR 以及 EPSR 三個部分，詳細定義請見下圖 |
| CONTROL | 控制 Stack、CPU 特權/非特權模式行為以及顯示 FPU 狀態的暫存器 |
接著來看 PSR (Program Status Register) 的定義:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-4
由上圖可知，PSR 由 APSR、IPSR 以及 EPSR 所構成。以下列出 PSR 的幾個較重要位元之功能:
| PSR位元 | 位置 | 功能 |
| -------- | -------- | -------- |
| N | [31] | Negative flag |
| Z | [30] | Zero flag |
| C | [29] | Carry or borrow flag |
| V | [28] | Overflow flag |
| Q | [27] | DSP overflow and saturation flag |
| ISR_NUMBER | [8:0] | 中斷服務常式 (Interrupt Service Routine, ISR) 之編號 |
其中 ISR_NUMBER (即 EPSR[8:0]) 可用於判斷目前是處於哪個中斷函式之中，若其值為0表示目前沒有中斷發生 (即 Thread mode)。ISR_NUMBER 的詳細定義由下圖給出:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-6
可以發現 ISR_NUMBER 的0至15已由 ARM 所制定，而16以後至最大值240則由廠商 (Vendor) 規劃用於諸如 USART、I2C、SPI 等周邊 ([Peripheral](https://zh.wikipedia.org/wiki/%E5%A4%96%E9%83%A8%E8%AE%BE%E5%A4%87))。
---
### 4.2 異常事件 (Exception)
上述的中斷 (Interrupt) 實際上只是 ARM Cortex-M 處理器中所定義的 Exception (異常事件) 中的一部分。異常事件的完整的定義則由下圖給出:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-22
由圖可知 Interrupt request (IRQ) 的編號被安排在零及正整數之後，而編號為負數的異常事件具有特殊地位。值得特別注意的是:
- **SVCall (Supervisor Call):** 一般用來實做系統呼叫 (Syscall), 具有即時響應 (Synchronous) 之特性
- **PendSV (Pendable Service):** 一般用來實做 Context switch，非即時響應 (Asynchronous)，會待其他異常事件都結束之後才處理
- 除了 Reset, NMI, HardFault 的優先權固定為-3, -2, -1之外 (數值越小優先權越高)，其餘異常事件優先權皆可以由開發者設定
- Vector address 是處理異常事件所定義的函式進入點位址, 即當異常事件被觸發後會跳轉到該函式
---
### 4.3 NVIC 優先權分組 (Priority grouping)
在 ARM Cortex-M4 的手冊中，Interrupt priority grouping 的描述如下:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-25
NVIC 的優先權分組提供了更細緻的優先權分組，分為分組優先權 (Group priority) 和子優先權 (Subpriority)，基本規則為分組優先權先比較，相同時再比較子優先權。
而由 STM32F4 手冊中可以找到支援的優先權分組選項:
[圖] 來源: STM32 Cortex®-M4 MCUs and MPUs programming manual 229/262
實際上 STM32 的 Driver library 採用 Group 0-4 的名稱來進行區分，將表格重新整理如下:
| 優先權分組 | 分組優先權範圍 | 子優先權範圍 | PRI_N[7:4]分配 |
| -------- | -------- | -------- | - |
| Group 0 | None | 0-15 | [7:4]用於子優先權 |
| Group 1 | 0-1| 0-7 | [7]用於分組優先權、[6:4]用於子優先權 |
| Group 2 | 0-3| 0-3 | [7:6]用於分組優先權、[5:4]用於子優先權 |
| Group 3 | 0-7| 0-1| [7:5]用於分組優先權、[4]用於子優先權 |
| Group 4 | 0-15| None | [7:4]用於分組優先權 |
為了簡化設計，Tenok 採用了 Group 4。
---
### 4.4 Stack Pointer: MSP 和 PSP
一般的電腦程式包含了靜態記憶體及動態記憶體管理，分別使用 Stack 以及 Heap 的記憶體區間。前者由編譯器規劃並會隨著呼叫函式、使用變數的行為而擴大範圍，後者則由使用者透過 `malloc()`、`free()` 等行為的顯式呼叫而產生變化。
[圖] 常見的 Stack 與 Heap 的記憶體分配模式 (ARM 的 Stack 採高位址遞減模式)
ARM Cortex-M 有兩個 Stack Pointer，分別為
* **MSP (Main Stack Pointer):** CPU 在 Reset 後即預設使用 MSP，一般會在 OS 啟動後提供給 Kernel space 程式使用
* **PSP (Process Stack Pointer):** 提供給 User space 的的程式使用，一般 OS 會根據Task數量分配多個區塊的記憶體，而透過改變 PSP 的指向搭配 Context switch 則可以實現多工
MSP 或是 PSP 的使用可以透過修改 CONTROL 暫存器來指定，詳細內容將於後續介紹。
---
### 4.5 Exception entry
Exception entry 意指當 CPU 進入 Exception 後所會自動發生的行為，官方手冊定義了 Exception entry 的發生時機:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-26
意即，當有待發生中的 (Pending) 異常事件時，以下幾種情況會產生 Exception entry:
* 處理器在 Thread mode 狀態
* 新的異常事件的權限比現在處理中的異常事件還要高，那麼將發生搶占，且會形成巢狀關係
下圖給出了一個異常事件的巢狀發生範例:
[圖] 來源:A Beginner’s Guide on Interrupt Latency and Interrupt Latency of the Arm Cortex-M processors
當 Exception entry 發生時:
* CPU 會記錄發生中斷的當下正在執行的指令位址 (如此一來中斷結束後才能回到原來的地方)，而 LR 會被寫入特殊的 EXC_RETURN 數值
* CPU 會自動進行 Stack push 將部分暫存器資料保存至 SP 指向的記憶體位址。同時根據程式是否使用到 FPU 進行浮點數運算， Stack push 行為將產生差異。詳細的內容請見下圖:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-27
上圖之左側和右側分別展示了使用和沒有使用 FPU 的 Stack push 行為。其中，S0 至 S15 為浮點數資料暫存器、FPSCR 為 Floating-point Status and Control Register。另外可以注意到 SP 的位址在 Stack push 後會遞減，這是因為 ARM 的 Stack 設計屬於高位址遞減。
至於為甚麼要將 Stack push 分成兩種情況的原因是是效能考量。因為並非所有的程式都需要計算浮點數，如果省略沒有用到的情況將有助於提升效能，而 ARM 稱此機制為 Lazy Stacking。
---
### 4.6 Exception return
Exception return 發生在完成處理 Exception 之後，與 Exception entry 成對發生。以下行為都可以產生 Exception return:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-28
即: Exception return 發生在 Handler mode，當以下任何一種組合語言指令將 EXC_RETURN 值載入 PC 暫存器後便會發生:
* 使用 `LDM` 或是 `POP` 指令將資料載入到PC暫存器中
* 使用 `LDR` 指令且儲存的對象是 PC 暫存器
* 呼叫 `BX` 指令和任意暫存器產生 Branching
上面所提到的 EXC_RETURN 值是 CPU 在 Exception entry 發生時自動寫入 LR 暫存器的內容，由下圖給出:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-28
翻譯成中文意即:
| EXC_RETURN[31:0] | FPU使用 | 功能 |
| ---------- | -- | ------------------- |
| 0xFFFFFFF1 | 無 | 返回 Handler mode 且切換至 MSP |
| 0xFFFFFFF9 | 無 | 返回 Thread mode 且切換至 MSP |
| 0xFFFFFFFD | 無 | 返回 Thread mode 且切換至 PSP |
| 0xFFFFFFE1 | 有 | 返回 Handler mode 且切換至 MSP |
| 0xFFFFFFE9 | 有 | 返回 Thread mode 且切換至 MSP |
| 0xFFFFFFED | 有 | 返回 Thread mode 且切換至 PSP |
值得注意的是，在異常事件處理函式中可以透過檢測 LR[4] 來判斷 Task 是否使用到 FPU，此細節將在 Context switch 實作中提到。
關於 Handler mode 以及 Thread mode的介紹會在後續給出。
---
### 4.7 Tail chaining 機制
Tail chaining 指的是當一個 ISR 完成以後，如果還有其他等待中的 ISR，處理器會直接切換至此 ISR 並省略 Stack push 和 Stack pop 的動作。此機制避免了不必要的記憶體存取和節省了處理器的能耗，且只需要6個 Clock cycles (ARM Cortex-M3 和 Cortex-M4 的情況)。 下圖為 Tail chaining 的一個範例:
[圖] 來源: A Beginner’s Guide on Interrupt Latency and Interrupt Latency of the Arm Cortex-M processors
---
### 4.8 Late arrival 機制
Late arrival 指的是如果一個高優先權的異常事件比低優先權的還要晚出現，處理器仍會優先服務高優先權異常事件的機制 (如下圖，IRQ1 比 IRQ2 晚觸發仍可以先被服務)。此機制確保高優先權異常可以更快的被處理，且避免了複雜的巢狀結構發生。除此之外，Late arrival 也可以幫助減少能耗。
[圖] 來源: A Beginner’s Guide on Interrupt Latency and Interrupt Latency of the Arm Cortex-M processors
---
### 4.9 特權等級 (Privilege levels) 以及處理器模式 (Processor modes)
ARM Cortex 處理器使用了特權等級 (Privilege levels) 來規範程式執行時可被允許的操作，同時特權等級與處理器模式 (Processor modes) 息息相關。請見下圖:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-2
**特權等級 (Privilege levels)**
特權等級包含了特權模式 (Privileged mode) 以及非特權模式 (Unprivileged mode)，前者可以存取所有硬體資源，而後者則受限。此設計用於保護作業系統核心，避免 User task 碰觸敏感資源。
* **特權模式 (Privileged mode):** 可操作所有硬體資源
* **非特權模式 (Unprivileged mode):**
- `MSR` 和 `MRS` 指令的功能受限，且不允許使用 `CPS` 指令
- 不允許操作 System timer, NVIC, 或是 System Control Block
- 某些記憶體區塊或是硬體周邊可能被禁止存取
**處理器模式 (Processor modes)**
[圖] 來源: Cortex-M3 Devices Generic User Guide 2-2
上圖給出了處理器模式 (Processor modes) 的兩種狀態: 當沒有異常事件產生時，程式碼執行於 Thread mode，反之則執行於 Handler mode。
根據ARM的設計，Handler mode 固定為 Privileged mode (即異常處理函式的必執行於特權模式下)，而 Thread mode 則根據 CONTROL 暫存器設定可以是 Privileged mode 或是 Unprivileged mode。
CPU 在 Reset 後會預先運作在 Privileged mode 以及 Thread mode 下。一種可行的設計是在作業系統啟動後再切換 User space 至 Unprivileged mode 來切割 User space 和 Kernel space。在此設計模式下，Privileged mode 使用 MSP 而 Unprivileged mode 則為 PSP。
然而上述的設計並非唯一可行的作法，像是 FreeRTOS 便不使用 PSP。FreeRTOS 的 Scheduler 是屬於 run-to-completion 設計，而不論是 Task 或是 Scheduler 皆使用 Privileged mode 以及 MSP。另外，由於許多 Baremetal 的應用不需要太複雜的資源管理，因此使用 Privileged mode 以及 MSP 即可足夠。
綜合以上描述，ARM Cortex-M 的模式切換可以表示為下圖:
[圖] 特權等級以及處理器模式之間的關係
---
### 4.10 特權等級以及 Stack Pointer 切換
特權等級以及 Stack Pointer 的切換 (MSP 或 PSP) 可由修改 CONTROL 暫存器達成。CONTROL 暫存器的定義由下圖給出:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-9
其中:
* **FPCA[2]:** 用於顯示目前的程式的 Context 是否有使用到浮點數運算
* **SPSEL[1]:** 用於設定 Stack Pointer 是使用 MSP 或是 PSP
* **nPRIV[0]:** 用於設定特權等級
特權等級以及 Stack Pointer 通常在 Context switch 中切換。由於 CONTROL 暫存器屬於特殊暫存器，其操作必須使用 `MSR` 或是 `MRS` 指令進行:
* `MSR`: 將即時值 (Immediate value) 或是通用暫存器的內容寫入特殊暫存器中
* `MRS`: 將特殊暫存器的內容寫入通用暫存器中
需要注意的是，修改 CONTROL 暫存器需要特權模式的等級。下圖給出了 CPU 切換至非特權模式的組合語言程式範例:
[圖] 來源: 不詳，擷自成大資工Wiki
另外手冊中明確指出了當使用 `MSR` 指令更改了 Stack Pointer 後，必須呼叫 `ISB` 指令來重置 CPU 的 Pipeline 以確保 CPU 正確執行新的 Stack 記憶體中的指令：
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-10
### 4.11 中斷的開啟以及關閉
ARM Cortex-M 提供了四道專門用於開啟/關閉中斷的指令:
[圖] 來源: Cortex-M4 Devices Generic User Guide 3-159
| 指令 | 行為 | 說明 |
| --------- | -------------------- | -------- |
| `CPSID i` | Set PRIMASK暫存器 | 關閉 Interrupts 以及可設定的 Fault handlers |
| `CPSID f` | Set FAULTMASK暫存器 | 關閉 Interrupts 以及所有 Fault handlers |
| `CPSIE i` | Clear PRIMASK暫存器 | 開啟 Interrupts 以及可設定的 Fault handlers |
| `CPSIE f` | Clear FAULTMASK暫存器 | 開啟 Interrupts 以及所有 Fault handlers |
下圖給出了 PRIMASK 暫存器的定義:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-8
以及 Fault Mask 暫存器的定義:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-8
除了硬開啟/關閉中斷外，ARM Cortex-M 亦提供了 Base Priority Mask 暫存器。透過寫入此暫存器的[7:0]位，可以設定大於等於此數值的中斷都會被屏蔽 (注意: 數值越大代表優先權越小)。Base Priority Mask 暫存器的定義由下圖給出:
[圖] 來源: Cortex-M4 Devices Generic User Guide 2-9
使用 Base Priority Mask 暫存器的好處是不必關閉不影響作業系統運作的特定中斷函式。 在 Tenok 原始碼中對應的實作如下:
```
//tenok/kernel/kernel.c
//允許所有中斷
void reset_basepri(void)
{
asm volatile ("mov r0, #0\n"
"msr basepri, r0\n");
}
//關閉大於KERNEL_INT_PRI值的中斷
void set_basepri(void)
{
asm volatile ("mov r0, %0\n"
"msr basepri, r0\n"
:: "i"(KERNEL_INT_PRI << 4)); //由於Tenok採用NVIC Group 4,
//即高4位的PRI_N[7:4]有效，
//使用時須左移4位
}
```
語法部分可以參見已故 **Liao Wen Satoshi** 朋友所撰寫的文章: [關於GNU Inline Assembly](http://wen00072.github.io/blog/2015/12/10/about-inline-asm/)。
## V. Context switch 實作
### 5.1 ARM Architecture Procedure Call Standard (AAPCS)
在說明 Context switch 的實做前，先介紹 AAPCS (ARM Architecture Procedure Call Standard) 以利於撰寫組合語言程式。
節錄幾個會用到的重點 [(AAPCS的官方說明)](https://developer.arm.com/documentation/den0013/d/Application-Binary-Interfaces/Procedure-Call-Standard):
* R0-R3 可以用來傳入前四個函式的輸入參數，又稱為 Caller-saved 暫存器，須由呼叫者保存
* R4-R11 一般用於區域變數使用，又稱 Callee-saved 暫存器，須由函式本身保存
* R0, R1 可以用來保存回傳值
* 當參數為64位元時可以合併兩個暫存器使用(如 R0+R1, R2+R3)
* R0-R3 不夠用時須用 Stack 協助傳遞
### 5.2 Context switch 的基本流程
ARM Cortex-M4F 的 Context switch 須考慮有無使用 FPU 的兩種情況。
**Task 沒有使用到 FPU 的情況:**
[圖] 來源: Cortex-M4(F) Lazy Stacking and Context Switching 15
上圖的內容為: 當前一個 Task 沒有使用到 FPU 資源，且異常事件被觸發 (如 SysTick 發生)， CONTROL 暫存器的 FPCA 位元將變為低電位，而 EXC_RETURN[4] 將變為高電位。再進入 Exception entry 時，CPU 會自動地將 R0-R3, R12, PC 和PSR推入 Stack。而此張圖並沒有說明的部分為，開發者再設計作業系統時，無論是保存舊的 Context 或是載入新的 Context，都需要自行 Pop / Push 核心暫存器的 R4-R11 部分。
此情況的 Context switch 基本流程為:
1. 舊的 Task 正在執行
2. Exception 被觸發，Context switch 開始
3. CPU 在 Exception entry 自動地將 R0-R3, R12, LR, PC 放入舊的 Stack Pointer 的位址中
4. OS 手動將 R4-R11 放入舊的 Stack pointer 的位址中
5. OS 手動從新的Stack pointer指向的內容中取出 R4-R11
6. CPU 在 Exception return 時自動地從新的 Stack Pointer 的位址中取出 R0-R3, R12, LR, PC
7. CPU 切換到新的 Task 執行
**Task 有使用到 FPU 的情況:**
[圖] 來源: Cortex-M4(F) Lazy Stacking and Context Switching 17
如上圖所示，若前一個 Task 使用了 FPU 資源，CONTROL 暫存器的 FPCA 位元將成為高電位。此時若觸發異常事件 (如用 SysTick 發生)，FPCA 將被反轉並拉低 EXC_RETURN[4] 的電位。當 Exception entry 被觸發後，R0-R3, R12, PC, PSR 將會被自動推入 Stack，同時也會為 FPU 的 S0-S15 和 FPSCR 在 Stack 內保留空間。此情況需要 OS 手動呼叫 `VSTM` 指令將舊的 FPU 暫存器的 S16-S31 部分保存至 Stack 內，並在要載入新的 Task 時用 `VLDM` 指令取出新的 S16-S31。而通用暫存器的部分則與先前所描述的相同。
此情況的 Context switch 基本流程為:
1. 舊的 Task 正在執行
2. Exception 被觸發，Context switch 開始
3. CPU 在 Exception entry 時自動地將 R0-R3, R12, LR, PC 放入舊的 Stack Pointer 的位址內，且會為 S0-S15 和 FPSCR 自動保存空間
4. OS 手動將 S16-S31 放入舊的 Stack Pointer 的位址內
5. OS 手動將 R4-R11 放入舊的 Stack Pointer 的位址內
6. OS 手動從新的 Stack Pointer 指向的位址中取出 R4-R11
7. Exception return 時自動地從新的 Stack pointer 指向的 Stack 中先取出 S0-S15, FPSCR，後取出 R0-R3, R12, LR, PC
8. CPU切換到新的 Task 執行
最後，以下先進行預告，Tenok 的 Context switch 的關係圖為如下:
[圖] Tenok的Context switch原理
### 5.3 第一個 Task 的初始化
第一個 Task 肩負著啟動 OS 的責任，我們首先介紹 `task_create()` 函式來了解其過程:
```
//tenok/kernel/kernel.c
...
#define THREAD_PSP 0xFFFFFFFD
#define INITIAL_XPSR 0x01000000
...
void task_create(task_func_t task_func, uint8_t priority)
{
...
tasks[task_cnt].pid = task_cnt; //根據目前有的Task數量分配PID
tasks[task_cnt].status = TASK_WAIT; //設定此Task為等待狀態
tasks[task_cnt].priority = priority; //設定優先權
tasks[task_cnt].stack_size = TASK_STACK_SIZE; //設定Stack大小
/* Stack初始化，使Context switch可以工作的關鍵程式碼 */
uint32_t *stack_top = tasks[task_cnt].stack + tasks[task_cnt].stack_size - 18;
stack_top[17] = INITIAL_XPSR;
stack_top[16] = (uint32_t)task_func; // PC = Task程式進入點
...
stack_top[8] = THREAD_PSP; //_LR = 0xfffffffd
tasks[task_cnt].stack_top = (struct task_stack *)stack_top;
...
}
```
上述的程式碼的行為可以繪製為下圖:
[圖] 使用 `task_create()` 後 **User stack** 的變化
`task_create()` 函數的機制可以分成三部分解說:
**Exception return 的行為設定 (藍色):**
* 設定了 PC 暫存器 (要執行的 User task 的函式位址) 以及 PSR 暫存器 (將 CPU 設定為 Thumb mode)
* 關於 Thumb mode 請參閱: [嵌入式系統建構：開發運作於STM32的韌體程式](http://wiki.csie.ncku.edu.tw/embedded/Lab19/stm32-prog.pdf)
(結論而言， ARM 指令集包含 ARM 模式和 Thumb-2 模式，ARM Cortex-M4 只支援後者)
* 模擬了 Exception entry 的行爲，將 R0-R3, R12, LR, PC 以及 PSR 推入了 User stack 中。待此 User task 被載入後會被 Exception return 自動取出。
**保留傳遞 Syscall 編號使用的 Stack 空間 (綠色):**
* Syscall 編號決定了 Kernel 要處理哪一個 Syscall。稍後可以發現第一個 Task 啟動時會傳遞0為數值但實際會被Kernel忽略，待後續 User task 真正呼叫 Syscall (傳遞大於0的Syscall編號) 時才會有效。
* 命名 _R7 是因為剛好使用 R7 做傳遞 ([ABI](https://zh.wikipedia.org/zh-tw/%E5%BA%94%E7%94%A8%E4%BA%8C%E8%BF%9B%E5%88%B6%E6%8E%A5%E5%8F%A3))，不過 R7 使用前後有做 Stacking / Unstacking，因此不會影響 User context
**處理需要開發者保存 Task 的 Context (黃色):**
* 設定了 LR 暫存器 (_LR, 用於將 User space 設定為 PSP 和 Unprivileged mode)
* 處理 R4-R11 需要開發者手動保存/載入的部分
除了上面所述，這裡有兩點需要特別指出:
* R0-R12 的值都是設定為0，因為程式尚未開始執行
* 載入新的 Task 不需要考慮 FPU，因為 Task 執行前從未使用過 FPU 資源
當第一個 Task 的 Stack 設定好後，便可呼叫 `os_env_init()` 函數來切割 Kernel space 和 User space:
```
//tenok/kernel/context_switch.s
//此函數在sched_start()中被呼叫，此時CPU為Thread mode和Privilege mode並使用MSP
.type os_env_init, %function
.global os_env_init
os_env_init:
//函式輸入:
//第一個參數(由R0傳入): Stack top的位址
/* 先保存此時的Kernel context */
mrs ip, psr //將PSR複製到IP內
push {r4, r5, r6, r7, r8, r9, r10, r11, ip, lr} //Stacking: 保存R4-R11, IP和_LR到MSP
/* 切換至PSP (註: CONTROL暫存器的寫入需要特權模式) */
msr psp, r0 //複製R0到PSP
mov r0, #3 //R0設定成3 (0b0000'0011), 即Unprivilege mode和使用PSP
msr control, r0 //複製R0到CONTROL使設定生效
isb //重置Pipeline
//觸發SVC異常事件 (或是當作呼叫編號為0的Syscall)，
//由於先前對Task stack的初始化，雖然os_env_init()是在Kernel中被呼叫的，
//但是會對CPU產生一個錯覺是Syscall是在Task中呼叫的
push {r7} //Stacking: 儲存舊的R7內容
mov r7, #0 //R7寫入0的數值
svc 0 //觸發SVC異常事件(此時程式會跳躍到SVC異常事件服務函式中)
/* 如果下面的程式開始執行代表SVC異常事件已經完成了 */
nop
pop {r7} //Unstacking: 還原舊的R7內容
/* Kernel space正式完成切割，從此之後進入Kernel都要先關閉中斷 */
cpsid i
cpsid f
bx lr //函式返回
```
從上述的程式碼我們知道 `os_env_init()` 執行過程中會被中斷一次並跳躍到 SVC 的函式內，SVC 的異常事件服務函式實作為:
```
//tenok/kernel/context_switch.s
.type SVC_Handler, %function
.global SVC_Handler
SVC_Handler:
/* 注意: 進入異常事件後CPU會自動切換至Handler mode和使用MSP */
/* 關閉所有中斷，只要涉及Context switch的程式都不應該被打斷 */
cpsid i
cpsid f
/* 取得User stack的Stack top位址 */
mrs r0, psp //複製PSP到R0
/* FPU的Context switch */
tst r14, #0x10 //檢測_LR[4]是否為1 (是否有使用到FPU?)
it eq //如果成立則下面一行指令會被略過
vstmdbeq r0!, {s16-s31} //Stacking: 保存User stack的FPU暫存器S16-S31
stmdb r0!, {r7} //Stacking: 保存User task的R7 (Syscall編號)內容
stmdb r0!, {r4, r5, r6, r7, r8, r9, r10, r11, lr} //Stacking: 保存User task的R4-R11和_LR
/* 載入Kernel context */
pop {r4, r5, r6, r7, r8, r9, r10, r11, ip, lr} //Unstacking: 從MSP取回R14-R11, IP和_LR
msr psr_nzcvq, ip //將IP保存的內容寫回PSR
/* 異常返回 */
bx lr //回到Kernel space
```
**讀者可能會有如下的疑惑:** 為什麼在切換至非特權模式後要再呼叫 Syscall 0 才回到 Kernel space 中呢? 這是為了依靠 SVC 異常進入 Handler mode 來取得特權。如果不這樣做，即使 `os_env_init()` 結束後直接返回 Kernel space 也無法回復至特權模式。
下圖為上述內容的視覺化描述:
[圖] `os_env_init()` 函式的流程
### 5.4 從 Kernel space 切換至 User Space
完成初始化後，接著就可以考慮如何切換至 User task。假設已有一個可被執行的 Task 存在，透過 `jump_to_user_space()` 可以達成切換。
`jump_to_user_space()` 的函數原型 (Function prototype) 的定義如下:
```
//tenok/kernel/kernel.h
...
uint32_t *jump_to_user_space(uint32_t stack);
...
```
而 `jump_to_user_space()` 的函數實作為:
```
//tenok/kernel/context_switch.s
.type jump_to_user_space, %function
.global jump_to_user_space
jump_to_user_space:
//輸入參數1 (R0): User task的Stack top位址
//回傳值 (R0): 載入User task的新的Stack top位址
//由於呼叫此函數時是Thread mode和Privilege mode，
//CPU在Exception entry時會自動將Kernel的LR設定為 0xFFFFFFF9 或 0xFFFFFFE9，
//因此當Task返回至Kernel時便會正確地還原這些設定
/* 保存Kernel狀態 */
mrs ip, psr //將PSR複製到IP中
push {r4, r5, r6, r7, r8, r9, r10, r11, ip, lr} //Stacking: 保存Kernel stack的
//R4-R11，IP和_LR
/* 載入User context */
ldmia r0!, {r4, r5, r6, r7, r8, r9, r10, r11, lr} //Unstacking: 從R0指向的Stack top
//位址取回R14-R11和_LR
ldmia r0!, {r7} //Unstacking: 載入Syscall編號
/* FPU的Context switch */
tst r14, #0x10 //檢測_LR[4]是否為1 (是否有使用到FPU?)
it eq //如果成立則下面一行指令會被略過
vldmiaeq r0!, {s16-s31} //Stacking: 保存User stack的FPU暫存器S16-S31
msr psp, r0 //將R0寫入到PSP (將要執行的Task stack寫入PSP)
/* 解除中斷關閉 */
cpsie i
cpsie f
//跳躍到User task，由於先前Stack初始化時異常返回的_LR值已被設為
//THREAD_PSP (0xFFFFFFFD)，因此跳躍後會自動切換為PSP
bx lr
```
### 5.5 從 User Space 切換至 Kernel Space
有兩個原因會導致 User task 重新回到 Kernel space 中:
* SysTick 的中斷被觸發 (時間到，必須重新進行排程)
* User task 呼叫 Syscall (觸發 SVC 異常事件回到 Kernel 處理 Syscall)
**由 SysTick 返回 Kernel 的情況:**
SysTick 的中斷觸發頻率為1000次/每秒，這在 `tenok/kconfig.h` 中可以見到:
```
#define OS_TICK_FREQ 1000 /* Hz */
```
而 SysTick 的異常事件處理函式的實作如下:
```
//tenok/kernel/context_switch.s
.type SysTick_Handler, %function
.global SysTick_Handler
SysTick_Handler:
/* 注意: 進入異常事件後CPU會自動切換至Handler mode和使用MSP */
/* 關閉所有中斷，只要涉及Context switch的程式都不應該被打斷 */
cpsid i
cpsid f
neg r7, r7 //將_R7變成負數，如此一來返回Kernel space時就可以和Syscall的
//request做出區別
/* 取得User stack的Stack top位址 */
mrs r0, psp //複製PSP到R0
/* FPU的Context switch */
tst r14, #0x10 //檢測_LR[4]是否為1 (是否有使用到FPU?)
it eq //如果成立則下面一行指令會被略過
vstmdbeq r0!, {s16-s31} //Stacking: 保存User stack的FPU暫存器S16-S31
stmdb r0!, {r7} //Stacking: 保存User task的R7 (Syscall編號)內容
stmdb r0!, {r4, r5, r6, r7, r8, r9, r10, r11, lr} //Stacking: 保存User task的R4-R11和_LR
/* 載入Kernel context */
pop {r4, r5, r6, r7, r8, r9, r10, r11, ip, lr} //Unstacking: 從MSP取回R14-R11, IP和_LR
msr psr_nzcvq, ip //將IP保存的內容寫回PSR
/* 異常返回 */
bx lr //回到Kernel space
```
**由 SVC 返回 Kernel 的情況:**
由於 SVC 的異常函式已在上文給出，此處就進行省略。取而代之說明 Syscall 是怎麼產生的:
我們可以以 `sleep()` 這個 Syscall 進行說明，其函式原型為:
```
//tenok/kernel/syscall.h
...
uint32_t sleep(uint32_t ticks);
...
```
而 `sleep()` 的實作如下:
```
//tenok/kernel/syscall.s
...
//定義一個GNU AS的巨集(Macro)方便使用
.macro syscall syscall_num
push {r7} //Stacking: 儲存舊的R7內容
mov r7, \syscall_num //_R7寫入Syscall編號
svc 0 //觸發SVC異常事件
nop
pop {r7} //Unstacking: 還原舊的R7內容
bx lr //函數返回
.endm
...
.type sleep, %function
.global sleep
sleep:
syscall #5 //呼叫前面定義的巨集並帶入數值為5的Syscall編號
...
```
當 CPU 回到 Kernel space 後，OS 可以透過 `syscall_handler()` 函式比對以下的 Syscall table 找到對應的 Syscall 處理函數:
```
//tenok/kernel/kernel.c
/* syscall table */
syscall_info_t syscall_table[] = {
...
DEF_SYSCALL(sleep, 5),
...
};
```
上述的的程式碼中包含了巨集函式 `DEF_SYSCALL()` 將 `sleep()` 的請求連結到服務函數 `sys_sleep()` 並標註其編號為5。此巨集的實作如下:
```
#define DEF_SYSCALL(func, _num) \
{.syscall_handler = sys_ ## func, .num = _num}
|___ 巨集黏合運算子 (Token-pasting operator)
```
而且 `syscall_handler()` 函式的實作為
```
//tenok/kernel/kernel.c
...
void syscall_handler(void)
{
/* 比較Syscall編號後呼叫對應的處理函數 */
int i;
for(i = 0; i < syscall_table_size; i++) {
if(running_task->stack_top->r7 == syscall_table[i].num) {
/* 執行Syscall */
syscall_table[i].syscall_handler();
break;
}
}
}
```
最後給出 `sys_sleep()` 的程式碼:
```
//tenok/kernel/kernel.c
void sys_sleep(void)
{
/* 設定睡眠時間 */
running_task->remained_ticks = *running_task->reg.r0;
/* 將執行中的Task改為等待狀態並放到Sleep list中 */
running_task->status = TASK_WAIT;
list_push(&sleep_list, &(running_task->list));
/* 設定甦醒後Syscall的回傳值為0 */
*(uint32_t *)running_task->reg.r0 = 0;
}
```
## VI. Linux 風格的 Linked list 實作
Tenok 實作了一個 Linux 風格的 Linked list 資料結構。相較於常見做法將要串連的結構體類型 (Structure data type) 作為指標紀錄下一個元素，Linux 將 Linked list 獨立成了一個結構體:
```
tenok/kernel/list.h
...
struct list {
struct list *prev;
struct list *next;
};
...
```
由定義可以知道此 Linked list 的設計為雙向連結，且實際上還會形成環型結構。使用時，須把 `struct list` 嵌入要使用的資料結構中，如:
```
struct object {
uint8_t data1;
...
struct list list;
};
```
同時，使用者需要再建立一列表頭變數 (List head) 用於追蹤 Linked list 中的所有元素。舉例來說，下圖為一個型態為 `struct object` 的 Linked list:
[圖] Linked list範例
我們接著對所有用於操作 Linked list 的函式進行說明:
```
//tenok/kernel/list.c
...
void list_init(struct list *list)
{
//功能: 初始化，Linked list使用前須進行的動作
//輸入: 列表頭(List head)
//如果傳入的列表頭為空則將其首尾連至自己
if(list != NULL) {
list->prev = list;
list->next = list;
}
}
int list_is_empty(struct list *list)
{
//功能: 查看Linked list是否為空
//輸入: 列表頭(List head)
/* 列表頭首尾連自自己代表Linked list為空 */
return list->next == list;
}
void list_remove(struct list *list)
{
//功能: 給定一個元素並將其從Linked list中移除
//輸入: 要從Linked list中移除的元素
/* 確認Linked list為非空 */
if(list != NULL) {
/* 取出中間元素並將前後元素相連 */
list->next->prev = list->prev;
list->prev->next = list->next;
}
}
void list_push(struct list *list, struct list *new)
{
//功能: 將一個新的元素推入Linked list的末端
//輸入: 列表頭 (list)、 新元素 (new)
if(list != NULL && new != NULL) {
/* 將新元素連至原末元素後端再與列表頭相連 */
new->prev = list->prev;
new->next = list;
list->prev->next = new;
list->prev = new;
}
}
struct list *list_pop(struct list *list)
{
//功能: 從Linked list的前端取出一個元素
//輸入: 回傳取出元素的位址
//第一個元素位於列表頭之後
struct list *first = list->next;
//若第一個元素等於列表頭則表示Linked list為空
if(list == first) {
return NULL;
}
//取出第一個元素並將後一個元素與列表頭相連
list->next = first->next;
list->next->prev = list;
return first;
}
```
接著會產生的問題是要如何透過 `struct list` 獲取結構體 `struct object` 本身呢? Tenok 仿照了 Linux 的設計並提供了以下的程式實作:
```
#define container_of(ptr, type, member) \
((type *)((void *)ptr - offsetof(type, member)))
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
```
其中 `offsetof()` 是一個用於計算結構成員位移 (offset of a structure member) 的內建巨集 (Macro)。接著我們以下面的程式碼作為範例說明 `container_of()` / `list_entry()` 巨集的使用:
```
/* 建立一個object的Linked list並初始化 */
struct list obj_list; //列表頭
list_init(&obj_list);
/* Push一個新元素 */
struct object new_obj = {.data1 = 10};
list_push(&obj_list, new_obj);
/* 取出第一個元素的list */
struct list *first = obj_list->next;
/* 取出第一個元素的data1數值 */
struct object *obj = container_of(first, struct object, list);
uint8_t val = obj->data1;
```
另外一個常見的應用場景是尋訪 (Traversal) 所有 Linked list 元素。這可以使用:
```
#define list_for_each(curr, list) \
for ((curr) = (list)->next; (curr) != (list); (curr) = (curr)->next)
```
並再以一個範例進行使用說明:
```
/* 建立一個object的Linked list並初始化 */
struct list obj_list; //列表頭
list_init(&obj_list);
/* Push一個新元素 */
struct object new_obj1 = {.data1 = 10};
list_push(&obj_list, new_obj1);
/* 再Push一個新元素 */
struct object new_obj2 = {.data1 = 20};
list_push(&obj_list, new_obj2);
/* 尋訪所有元素 */
struct list *curr;
list_for_each(curr, &obj_list) {
/* 取出元素N的data1數值 */
struct object *obj = container_of(curr, struct object, list);
uint8_t val = obj->data1;
}
```
由此可以知C語言是一個強大的程式語言，允許使用者透過巨集 (Macro) 自行擴充語言。
**延伸閱讀:**
* [offsetof(3) - Linux manual page](https://man7.org/linux/man-pages/man3/offsetof.3.html)
* [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list)
## VII. 任務排程 (Task scheduling)
在 Tenok 中，Task 有三種狀態:
```
enum {
TASK_WAIT, //等待中
TASK_READY, //可被執行
TASK_RUNNING //執行中
} TASK_STATUS;
```
每一個 Task 都有一個對應的 Task Control Block 用於保存資訊:
```
//tenok/kernel/kernel.h
...
struct task_ctrl_blk {
struct task_stack *stack_top; //Task目前的Stack頂端
uint32_t stack[TASK_STACK_SIZE]; //Task stack
uint32_t stack_size; //Stack的大小, 目前的設計只允許固定值
uint8_t status; //Task的狀態
uint32_t pid; //Task的PID編號
int priority; //Task的優先權
char name[TASK_NAME_LEN_MAX]; //Task的名稱
uint32_t sleep_ticks; //睡眠計數器，下數到0時Task會被喚醒
bool syscall_pending; //用來表示Task的Syscall尚未完成
struct {
size_t size; //Task請求了某個檔案操作但是目前無法被滿足，並將
//大小保存於此
} file_request;
struct list list; //用來串連Task list
};
...
```
Tenok 採用了 Priority-based Round-Robin Algorithm 進行排程，有 TASK_MAX_PRIORITY + 1 個 Ready list 及一個 Sleep list 如下圖所示:
[圖] Ready lists 與 Sleep list
Priority-based Round-Robin Algorithm 的基本原則為:
* 優先從具有較高優先權的 Ready list 中選取任務
* 當 Ready list 的優先權與執行中 Task 的相等，則須等待執行中 Task 所分配的 Time quantum (時間量) 被耗盡後才可切換到下一個任務
對應的程式碼為:
```
/* task lists */
//tenok/kernel/kernel.c
...
struct list ready_list[TASK_MAX_PRIORITY + 1];
struct list sleep_list;
/* tasks */
struct task_ctrl_blk tasks[TASK_CNT_MAX];
struct task_ctrl_blk *running_task = NULL; //用來儲存當前執行的Task
...
```
結合先前在 Linked list 中所介紹的內容，每一個 Task list 的結構如下:
[圖] Task list 的結構
以下給出排程演算法的實作:
```
//tenok/kernel/kernel.c
void schedule(void)
{
/*
* 由於特定OS API會透過Syscall關閉IRQ, 此情況下OS不應該進行排程直到呼叫的
* Task將IRQ重新啟動
*/
if(irq_off == true)
return;
/* 檢查是否有可以被喚醒的Task */
struct list *list_itr = sleep_list.next;
while(list_itr != &sleep_list) {
/* 由於Task可能從Sleep list移除，先紀錄下一個對象 */
struct list *next = list_itr->next;
/* 取得Task Control Block */
struct task_ctrl_blk *task = list_entry(list_itr, struct task_ctrl_blk, list);
/* 睡眠所需等待的Tick已經耗盡，將Task根據優先權放入Ready list中 */
if(task->sleep_ticks == 0) {
task->status = TASK_READY;
list_remove(list_itr); //remove the task from the sleep list
list_push(&ready_list[task->priority], list_itr);
}
/* 準備下一個要檢查的對象 */
list_itr = next;
}
/* 由優先權大的往小的開始找到一個包含可以執行的Task的Ready list */
int pri;
for(pri = TASK_MAX_PRIORITY; pri >= 0; pri--) {
if(list_is_empty(&ready_list[pri]) == false)
break;
}
/* Task在Time quantum (即SysTick的週期) 被耗盡前便返回了Kernel (即Syscall) */
if(running_task->status == TASK_RUNNING) {
/* 確認是否有更高優先權的任務在Ready list中等待 */
if(pri > running_task->priority) {
/* 有，進入睡眠狀態 */
prepare_to_wait(&sleep_list, &running_task->list, TASK_WAIT);
} else {
/* 沒有，直接返回不切換到別的Task */
return;
}
}
/* 從Ready list中Pop出一個Task來執行 */
struct list *next = list_pop(&ready_list[pri]);
running_task = list_entry(next, struct task_ctrl_blk, list);
running_task->status = TASK_RUNNING;
}
```
同時，如果 User task 是透過 SysTick 中斷回到 Kernel 的話會觸發 `tasks_tick_update()` 函數:
```
//tenok/kernel/kernel.c
static void tasks_tick_update(void)
{
/* 現在執行中的Task的Time quantum已經耗盡，將其設定為睡眠狀態並待新的Task被選出 */
if(running_task->status == TASK_RUNNING) {
prepare_to_wait(&sleep_list, &running_task->list, TASK_WAIT);
}
/* 更新所有睡眠中的Task還須等待的Tick量 */
struct list *curr;
list_for_each(curr, &sleep_list) {
/* 取得第N個睡眠中的Task的Task Control Block */
struct task_ctrl_blk *task = list_entry(curr, struct task_ctrl_blk, list);
/* 計數器遞減直到為0 */
if(task->sleep_ticks > 0) {
task->sleep_ticks--;
}
}
}
```
## VIII. 同步機制 (Synchronization)
Tenok 實作了 Spinlock, Mutex 以及 Semaphore, 以下簡述了三種機制的差異:
**Spinlock:**
* 基於 Busy waiting 的一種鎖
* 需要使用到原子操作 (Automic operation) 如: [Test-and-set](https://en.wikipedia.org/wiki/Test-and-set) 或 [Compare-and-swap
](https://en.wikipedia.org/wiki/Compare-and-swap) 實作
* 沒有 Context switch的開銷 (Overhead)，可用於需要快速反應的短程式
**Mutex:**
* 需要使用到 Spinlock 實作
* 是 Process 層次的物件，當無法獲取資源時進行睡眠
* 有持有者 (Owner) 概念，只有上鎖者可以進行解鎖
* 產生 Critical Section 的目的是保護共享資源
* 如遇到優先權反轉 (Priority inversion) 問題，則需要如 Priority Inheritance Protocol (PIP) 等機制
**Semaphore:**
* 需要使用到 Spinlock 實作
* 是 Process 層次的物件，當無法獲取資源時進行睡眠
* 沒有限制一定要由上鎖者解鎖
* 產生 Critical Section 的目的為:
1. 使用計數器處理生產者-消費者問題 (在一個 Thread 中，`signal()` 與 `wait()` 不會同時發生)
2. 執行緒同步: 如一執行緒A通知執行緒B繼續執行
**參考閱讀:**
* [Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync?type=view) (在 <*既生瑜，何生亮？*> 中說明了 Mutex 與 Semaphore 存在差異)
* [Priority Inversion on Mars](https://www.slideshare.net/jserv/priority-inversion-30367388?fbclid=IwAR0GdoqVaKk41XrMoyWtO-lHasoJ4fZVhDw7X50o1GEFdgRoJAq-aNvolss) (火星拓荒者號的優先權反轉案例)
---
### 8.1 Spinlock 實作
ARM Cortex-M 提供了 Load-Exclusive 和 Store-Exclusive 的機制用於實作如 Spinlock 的 Synchronization primitives (同步原語)，如下圖所示:
[圖] 來源: Cortex-M3 Devices Generic User Guide 2-19
**Load-Exclusive 指令:**
* 讀取某個記憶體位址的內容，同時請求標記此位址為獨佔 (前者一定會成功，後者不一定)
**Store-Exclusive 指令:**
* 嘗試寫入某個記憶體位址，回傳的位元顯示了寫入的成功與否 (0: 成功; 1: 失敗，沒有取得記憶體的獨佔權)
ARM Cortex-M 提供了三組指令，分別為:
* `LDREX` 和 `STREX` 用於 Word (32 bits) 大小的資料
* `LDREXH` 和 `STREXH` 用於 Halfword (16 bits) 大小的資料
* `LDREXB` 和 `STREXB` 用於 Byte (8 bits) 大小的資料
了解了基本原理以後，以下給出 Spinlock 的實作:
**函式原型:**
```
//tenok/kernel/spinlock.h
...
#define spin_lock_irq(lock) \
do { \
preempt_disable(); \
spin_lock(lock); \
} while(0)
#define spin_unlock_irq(lock) \
do { \
spin_unlock(lock); \
preempt_enable(); \
} while(0)
typedef uint32_t spinlock_t;
void spin_lock(spinlock_t *lock);
void spin_unlock(spinlock_t *lock);
...
```
**實作:**
```
.syntax unified
/* Spinlock上鎖 */
.type spin_lock, %function
.global spin_lock
spin_lock:
//函式參數:
//第一個參數(由R0傳入): 鎖變數的記憶體位址
loop: ldrex r2, [r0] //將鎖變數的位址載入R2並請求獨佔此記憶體位址
cmp r2, #1 //如果鎖變數 == 1 (變數已鎖上)
beq loop //返回loop標籤重試
mov r1, #1 //將數值1複製到R1
strex r2, r1, [r0] //嘗試將1 (R1) 寫入鎖變數 ([R0])，是否寫入成功會記錄在R2內
cmp r2, #1 //如果R2 == 1 (寫入失敗)
beq loop //返回loop標籤重試
bx lr //函式返回
/* Spinlock解鎖 (比上鎖簡單，直接將鎖變數歸零即可) */
.type spin_unlock, %function
.global spin_unlock
//函式參數:
//第一個參數(由R0傳入): 鎖變數的記憶體位址
spin_unlock:
mov r1, #0 //將數值0複製到R1
str r1, [r0] //將0 (R1) 寫入鎖變數 ([R0])
bx lr //函式返回
```
---
### 8.2 Mutex 實作
有了 Spinlock 之後便可實作 Mutex，以下給出 Mutex 的實作 (注意，目前的的實作做不包含任何 Protocol 設計):
```
int pthread_mutex_init(_pthread_mutex_t *mutex, const pthread_mutex_attr_t *attr)
{
mutex->owner = NULL; //初始化擁有者為空，這個指標會指向Task Control Block的位址
mutex->lock = 0; //初始化Mutex的Spinlock
list_init(&mutex->wait_list); //初始化當Mutex需要睡眠時使用的wait_list
return 0;
}
int pthread_mutex_unlock(_pthread_mutex_t *mutex)
{
/* 進入Critical Section */
spin_lock_irq(&mutex->lock);
int retval = 0;
/* 檢查呼叫函數的Task是否為持有者 */
if(mutex->owner == running_task) {
/* 是，清空持有者 (解鎖) */
mutex->owner = NULL;
/* 檢查是否有其他Task因為嘗試存取該Mutex而正在睡眠 */
if(!list_is_empty(&mutex->wait_list)) {
/* 透過wake_up()喚醒一個Task */
wake_up(&mutex->wait_list);
}
} else {
/* 否，返回異常值 */
retval = EPERM;
}
/* 離開Critical Section */
spin_unlock_irq(&mutex->lock);
/* 回傳0 */
return retval;
}
int pthread_mutex_lock(_pthread_mutex_t *mutex)
{
/* 重複嘗試直到取得Mutex */
while(1) {
/* 進入Critical Section */
spin_lock_irq(&mutex->lock);
/* 檢查該Mutex是否早已被其他Task占用 (上鎖) */
if(mutex->owner != NULL) {
/* 是，呼叫prepare_to_wait()把自己放進wait_list中睡眠等待 */
prepare_to_wait(&mutex->wait_list, &running_task->list, TASK_WAIT);
/* 離開Critical Section */
spin_unlock_irq(&mutex->lock);
/* 讓Task進入睡眠 */
sched_yield();
} else {
/* 否，Mutex沒有被占用，可以上鎖 */
/* 將Mutex的持有者設定為自己 */
mutex->owner = running_task;
/* 離開Critical Section */
spin_unlock_irq(&mutex->lock);
/* 離開迴圈 */
break;
}
}
/* 回傳0 */
return 0;
}
```
---
### 8.3 Semaphore 實作
同樣的，Sempaphore 的實作也需要 Spinlock。以下為一 Semaphore 的虛擬碼 (Pseudo-code) 範例:
[圖] 來源: Synchronization: Spinlocks - Semaphores (CS 4410 Operating Systems, Cornell University)
以下給出 Semaphore 的實作:
```
int sem_init(sem_t *sem, int pshared, unsigned int value)
{
sem->count = value; //初始化Semaphore的數量
sem->lock = 0; //初始化Semaphore的Spinlock
list_init(&sem->wait_list); //初始化Semaphore無法取得時，Task的等待清單
return 0;
}
/* sem_post()可以在User task或是Interrupt中被呼叫 */
int sem_post(sem_t *sem)
{
/* 進入Critical Section */
spin_lock_irq(&sem->lock);
int retval;
/* 預防整數溢位 */
if(sem->count >= (INT32_MAX - 1)) {
retval = -EAGAIN; //稍後用來回傳提示使用者重新嘗試
} else {
/* 增加Semaphore的數量 */
sem->count++;
/* 如有Task在等待且Semaphore數量> 0則喚醒一個Task */
if(sem->count > 0 && !list_is_empty(&sem->wait_list)) {
wake_up(&sem->wait_list);
}
retval = 0; //稍後回傳0表示成功
}
/* 離開Critical Section */
spin_unlock_irq(&sem->lock);
return 0; //回傳，程式結束
}
//sem_trywait() 可以被User task或是Kernel program呼叫。
//因為不會產生阻塞所可以用於如: chardev driver的file operation中使用
int sem_trywait(sem_t *sem)
{
/* 進入Critical Section */
spin_lock_irq(&sem->lock);
int retval;
/* 檢查Semaphore的數量 */
if(sem->count <= 0) {
/* 無法獲得Semaphore, 將Task放到等待清單中 */
prepare_to_wait(&sem->wait_list, &running_task->list, TASK_WAIT);
retval = -EAGAIN; //稍後用來回傳提示使用者重新嘗試
} else {
/* Semaphore獲取成功 */
sem->count--;
retval = 0; //成功，稍後回傳0
}
/* 離開Critical Section */
spin_unlock_irq(&sem->lock);
return retval; //回傳，程式結束
}
/* sem_wait()只能在User task中呼叫 */
int sem_wait(sem_t *sem)
{
/* 進入Critical Section */
spin_lock_irq(&sem->lock);
while(1) {
if(sem->count <= 0) {
/* 無法獲得Semaphore, 將Task放到等待清單中 */
prepare_to_wait(&sem->wait_list, &running_task->list, TASK_WAIT);
/* 離開Critical Section */
spin_unlock_irq(&sem->lock);
/* 讓Task進入睡眠 */
sched_yield();
} else {
/* 成功獲取Semaphore */
sem->count--;
/* 離開Critical Section */
spin_unlock_irq(&sem->lock);
return 0;
}
}
}
```
## IX: 檔案系統 (File System)
### 9.1 檔案以及檔案抽象層 (File Abstraction Layer)
Tenok 目前支援了五種檔案類型，分別為:
| 檔案類型 | 巨集名稱 | 數值 |
| -------- | -------- | -------- |
| FIFO (named pipe) | S_IFIFO | 0 |
| Character device | S_IFCHR | 1 |
| Block device | S_IFBLK | 2 |
| Regular file | S_IFREG | 3 |
| Directory | S_IFDIR | 4 |
為了追蹤所有存在的檔案，Tenok 建立了以下的 File table:
```
//tenok/kernel/kernel.c
...
/* file table */
struct file *files[TASK_CNT_MAX + FILE_CNT_MAX];
int file_cnt = 0;
...
```
由於各個檔案的實作不同，檔案的結構體定義使用到了先前介紹過的技巧讓 File table 指向各個檔案共通的 `struct file` 成員，待需要取出結構體本身時再呼叫 `container_of()` 巨集。另外所有檔案都使用了一份統一的軟體介面 (Software interface) 稱之為 File operations，確保了不同種類的檔案實作之間仍能有一個相同的規範遵循。下圖給出了 File table, File 以及 File operations 之間的關係:
[圖] File table, File 以及 File operations
以下給出了 `struct file` 和 File operations 的程式定義:
```
//tenok/kernel/fs.h
...
struct file {
struct inode *file_inode; //指向該檔案inode的指標
struct file_operations *f_op; //檔案支援的操作
};
/* 檔案支援的操作 (目前只有實作三個，可逕行擴充) */
struct file_operations {
/* 讀寫頭移動操作函式 */
long (*llseek)(struct file *filp, long offset, int whence);
/* 讀操作函式 */
ssize_t (*read)(struct file *filp, char *buf, size_t size, loff_t offset);
/* 寫操作函式 */
ssize_t (*write)(struct file *filp, const char *buf, size_t size, loff_t offset);
};
...
```
實際設計上，File table 保留了前 TASK_CNT_MAX 個空間給所有的 Task 存放 FIFO 用於行程間通訊 (Inter-Process Communication, IPC)，而剩下的 FILE_CNT_MAX 數量才是真正可以使用的空間。下圖給出了上述的的空間分配規則:
[圖] File table 的空間分配
### 9.2 Super block, inode, dentry 以及 Block
File table 雖然記錄了所有檔案的位址，但是使用上並不夠方便。一個常見的作業系統功能是透過給定的路徑找到所要的檔案，要達到這樣的功能需要更完整的檔案系統設計，因此首先介紹 Super block、inode、dentry 以及 Block 的概念。
所謂的 Super block 一般位於磁碟分割區 (Partition) 的最前端並存有此檔案系統的基本資訊，其在 Tenok 中的程式定義如下：
```
//tenok/kernel/fs.h
struct super_block {
uint32_t s_blk_cnt; //Block的使用數量
uint32_t s_inode_cnt; //inode的使用數量
bool s_rd_only; //是否只能已讀
uint32_t s_sb_addr; //Super block的起始位址
uint32_t s_ino_addr; //inode的起始位址
uint32_t s_blk_addr; //Block的起始位址
};
```
inode 是檔案系統中拓樸結構節點的基本元素，其在程式定義為:
```
//tenok/kernel/fs.h
struct inode {
uint8_t i_mode; //檔案類型
uint8_t i_rdev; //裝置的掛載號碼 (0保留給rootfs)
bool i_sync; //掛載的檔案是否已經同步
uint32_t i_ino; //inode號碼
uint32_t i_parent; //父節點目錄的inode號碼
uint32_t i_fd; //File descriptor號碼
uint32_t i_size; //檔案大小 (Bytes)
uint32_t i_blocks; //Block的使用數量
uint32_t i_data; //資料的虛擬記憶體位址
struct list i_dentry; //dentry list的列表頭 (List head)
};
```
dentry 描述了一個目錄所包含的檔案名稱以及對應的 inode 編號。一般而言檔案名稱不會被保存在 inode 而是在 dentry 中。以下為 dentry 的程式定義:
```
//tenok/kernel/fs.h
struct dentry {
char d_name[FILE_NAME_LEN_MAX]; //檔案名稱
uint32_t d_inode; //檔案的inode號碼
uint32_t d_parent; //父目錄的inode號碼
struct list d_list; //連結多個dentry用的List
};
```
而最後 Block 就是一塊用於儲存資訊的空間。下圖給出了一個檔案系統的拓樸結構範例:
[圖] 檔案系統的拓樸結構範例，romfs 掛載在 root之下
在 Tenok 中檔案系統由 Super block, inodes 和 Blocks 組成，其在被儲存到 ROM 後會有以下的排列關係:
[圖] Tenok 的檔案系統在 ROM 中的儲存結構
為了解釋檔案系統的實作，我們現在考慮一個只存有 `/poem.txt` 檔案和 `/document/` 目錄的情況，並將其繪製為:
[圖] 一個 Tenok 的檔案系統範例
如果 inode 的類型為目錄 (S_IFDIR)，則其指向的 Block 空間將儲存 dentry 所組成的列表 (dentry list)。這個列表會給出該目錄下所有檔案的名稱、inode 編號以及指向下一個 dentry 的 `struct list`。由於檔案系統單一 Block 大小有限，不能無限地儲存 dentry。當一個 Block 無法容納新的 dentry 時，檔案系統會分配新的 Block 並透過 dentry 的 `struct list` 成員進行串連。
然而，如果 inode 的類型為標準檔案 (S_IFREG)，則其指向的 Block 空間將儲存檔案的內容。同樣地，由於檔案可能需要用到多個 Block 儲存，因此在所有 Block 的頂端 (Header) 有一個用於指向下一個 Block 位址的指標，而最後一個 Block 的指標將指向 NULL。
因此，只要順著第一個 inode (即根目錄) 往下尋訪 (Traversal) 便可找到所有的檔案。舉例來說，inodes[0] 的 dentry list 便包含了 `document/` 及 `poem.txt` 的 inode 資訊。透過上圖我們可以知道 `poem.txt` 的 inode 編號為1，因此只要透過存取 inodes[1].i_data 便可得到儲存檔案內容第一個區塊的位址。
實際上，許多 Unix 作業系統採用的作法是一個 inode 可以記錄多個 Block 的位址，具有較優的效能表現，如:
[圖] inode/block 資料存取示意圖 (來源: 鳥哥私房菜網站 - 蔡德明博士)
而 Tenok 採用了類似於 FAT (File Allocation Table) 檔案系統的串連設計，若要存取第 N 個 Block 則必須先尋訪 (Traverse) 完前 N-1 個 Blocks:
[圖] FAT檔案系統資料存取示意圖 (來源: 鳥哥私房菜網站 - 蔡德明博士)
同時，許多成熟的檔案系統通常還包含了 inode map 以及 Block map 用來標記 inode 和 Block 的使用情況 (用於達成 inode 和 Block 的動態管理)。但是由於 Tenok 目前沒有實作此功能，因此不支援檔案的刪除。
### 9.3 檔案系統伺服器 (File System Server)
Tenok 參考了 rtenv 將檔案系統實做為 User task。傳統上作業系統可以大致被分為 Monolithic kernel 與 Microkernel 兩派。前者將作業系統的許多模組如 File system, driver 等整合於 Kernel 中以試圖提升作業系統的效能，而後者則儘可能的使 Kernel 保持精簡，並將非關鍵模組放置於 User space 中。此兩者的優缺點可見: [淺談 Microkernel 設計和真實世界中的應用
](https://hackmd.io/@sysprog/microkernel-design)。
回到 Tenok 的部分，`mknod()`, `open()`, `opendir` 以及 `mount()` 等 Syscall 會需要檔案系統從給定的檔案路徑中尋找到對應的 inode, dentry 以及 File descriptor 等。User task 在呼叫這些 Syscall 時，實際上會透過 FIFO 的 IPC 機制向 File system task 發送請求指令，而當任務完成後則會向 Task 寫回請求結果。在任務完成前，User task將會進入睡眠狀態。以下的兩張圖片描述了這個過程:
[圖] 步驟一: User task 向 File system task 發送檔案操作請求
[圖] 步驟二: File system task 回傳結果給 User task
可以注意到，圖中指定了 File system task 的 PID 為1。這是因為根據設計，第一個 Task在 載入後必須馬上呼叫 `os_service_init()` 函式載入 File system task，而在 `tenok/kconfig.h` 中也可以見到以下的設定:
```
...
#define FILE_SYSTEM_FD 1 /* file system program is assumed to be the *
* second task to be launched */
...
```
另外我們也可以在 File system task 中見到以下用於處理 User task 請求的程式結構:
```
//tenok/kernel/fs.c
...
void file_system_task(void)
{
...
switch(file_cmd) {
case FS_CREATE_FILE: {
...
break;
}
case FS_OPEN_FILE: {
...
break;
}
case FS_OPEN_DIR: {
...
break;
}
case FS_MOUNT: {
...
break;
}
}
}
}
```
最後需要補充的是，由於 Tenok 假設了上述這些 Syscall (新建檔案、開啟檔案、開啟目錄等) 不會被頻繁的呼叫，因此 File system task 的優先權被設定為最低。
## X. 行程間通訊 (Inter-Process Communication, IPC)
### 10.1 Ring Buffer 資料結構
Tenok 支援了兩種 IPC 功能: FIFO (Named pipe) 及 Message Queue 皆用到了 Ring buffer 的資料結構。Ring buffer 在概念上是一個首尾相連、先進先出 (First In, First Out, FIFO) 的資料結構，如同下圖所示:
[圖] Ring buffer 的概念圖
但實際上電腦的記憶體為線性關係，因此 Ring buffer 的實作上必須使用一塊連續記憶體並記錄頭尾位置:
[圖] Ring buffer 在記憶體中實際的狀況
以下為 Ring buffer 結構體的程式定義:
```
//tenok/kernel/ringbuf.h
struct ringbuf {
int start; //開始位置
int end; //結束位置
int count; //目前Ring buffer中擁有的元素數量
void *data; //指向分配給Ring buffer的空間
size_t ring_size; //Ring buffer中可容納的元素數量
size_t type_size; //Ring buffer中單一元素的大小 (幾個Byte)
struct file file; //Ring buffer可被實作為FIFO
struct list task_wait_list; //Ring buffer無法服務Task時的等待清單
};
```
以及各個函式的實作:
```
//tenok/kernel/ringbuf.c
/* 用於更新Ring buffer開始/結束位置的子程式 */
static int ringbuf_increase(struct ringbuf *rb, int ptr)
{
/* 位置加一 */
ptr++;
/* 是否已來到Ring buffer的最末端 */
if(ptr >= rb->ring_size) {
ptr = 0; //是，位置回到最前端
}
/* 回傳新的位置 */
return ptr;
}
/* 將一個資料放入Ring buffer中 */
void ringbuf_put(struct ringbuf *rb, const void *data)
{
size_t type_size = rb->type_size;
/* 檢查Ring buffer是否已滿 */
if(ringbuf_is_full(rb) == true) {
/* 是，覆寫最舊一筆資料以及遞增Ring buffer的開始位置 */
memcpy((char *)(rb->data + (rb->start * type_size)), (char *)data, type_size);
rb->start = ringbuf_increase(rb, rb->start);
} else {
/* 否，從尾端添加一筆新資料 */
memcpy((char *)(rb->data + (rb->end * type_size)), (char *)data, type_size);
rb->count++;
}
/* 更新結束位置因為新資料已被加入Ring buffer */
rb->end = ringbuf_increase(rb, rb->end);
}
/* 從Ring buffer中取出一個資料 */
void ringbuf_get(struct ringbuf *rb, void *data)
{
size_t type_size = rb->type_size;
/* 檢查Ring buffer中是否有資料可以取用 */
if(rb->count > 0) {
/* 資料複製、更新開始位置以及資料數量減一 */
memcpy((char *)data, (char *)(rb->data + (rb->start * type_size)), type_size);
rb->start = ringbuf_increase(rb, rb->start);
rb->count--;
}
}
/* 檢查Ring buffer是否為空 */
bool ringbuf_is_empty(struct ringbuf *rb)
{
return rb->count == 0; //大小為零即空
}
/* Ring buffer是否為滿 */
bool ringbuf_is_full(struct ringbuf *rb)
{
return rb->count == rb->ring_size; //數量等於最大容量即滿
}
```
---
### 10.2 FIFO (Named Pipe)
[FIFO](https://en.wikipedia.org/wiki/Named_pipe) (一般又稱為 Named Pipe) 提供了 [Byte stream](https://zh.wikipedia.org/wiki/%E4%BD%8D%E5%85%83%E7%B5%84%E6%B5%81) (位元組流) 等級的 IPC 功能，在 Tenok 中被設計為 Syscall。
以下摘錄了 FIFO 的原始碼實作:
```
//tenok/kernel/fifo.c
...
ssize_t fifo_read(struct file *filp, char *buf, size_t size, loff_t offset);
ssize_t fifo_write(struct file *filp, const char *buf, size_t size, loff_t offset);
/* 因為FIFO使用了File abstraction layer，所以必須定義支援的File operations */
static struct file_operations fifo_ops = {
.read = fifo_read,
.write = fifo_write
};
int fifo_init(int fd, struct file **files, struct inode *file_inode, struct memory_pool *mem_pool)
{
/* Pipe (Ring buffer) 的記憶體分配和初始化 (註: 大小為Byte級) */
struct ringbuf *pipe = memory_pool_alloc(mem_pool, sizeof(struct ringbuf));
uint8_t *pipe_mem = memory_pool_alloc(mem_pool, sizeof(uint8_t) * PIPE_DEPTH);
ringbuf_init(pipe, pipe_mem, sizeof(uint8_t), PIPE_DEPTH);
/* 將FIFO掛載到File table上 */
pipe->file.f_op = &fifo_ops; //連結所支援的File operations
pipe->file.file_inode = file_inode; //紀錄由檔案系統分配的inode
files[fd] = &pipe->file; //Pipe的file成員掛載到File table上
return 0;
}
ssize_t fifo_read(struct file *filp, char *buf, size_t size, loff_t offset)
{
/* 由Pipe的file成員取得其容器，即Pipe自身 */
struct ringbuf *pipe = container_of(filp, struct ringbuf, file);
/* 如果Task要求的讀取量比實際可行的多，則將其排入等待清單中 */
if(size > pipe->count) {
/* put the current task into the waiting list */
prepare_to_wait(&pipe->task_wait_list, &running_task->list, TASK_WAIT);
/* 打開Syscall pending flag提示Kernel稍後還要回來處理 */
running_task->syscall_pending = true;
return 0; //由於請求暫時無法被滿足，先返回讓Kernel繼續工作
} else {
/* 讀取請求已經被滿足，關閉syscall pending flag */
running_task->syscall_pending = false;
}
/* 從Pipe (Ring buffer) 中取出資料 */
int i;
for(i = 0; i < size; i++) {
ringbuf_get(pipe, &buf[i]);
}
return size; //回傳接讀取到的數量
}
ssize_t fifo_write(struct file *filp, const char *buf, size_t size, loff_t offset)
{
/* 由Pipe的file成員取得其容器，即Pipe自身 */
struct ringbuf *pipe = container_of(filp, struct ringbuf, file);
/* 取出Pipe的Task等待清單 */
struct list *wait_list = &pipe->task_wait_list;
/* 將資料放入Pipe (Ring buffer) 中 */
int i;
for(i = 0; i < size; i++) {
ringbuf_put(pipe, &buf[i]);
}
/* 檢查是否有Task正在等待中 */
if(!list_is_empty(wait_list)) {
/* 從清單中取出一個Task */
struct task_ctrl_blk *task = list_entry(wait_list->next, struct task_ctrl_blk, list);
/* 檢查此Task先前請求的讀取量是否可以被滿足 */
if(task->file_request.size <= pipe->count) {
/* 是，將其喚醒重新嘗試讀取 */
wake_up(wait_list);
}
}
return size; //回傳寫入的數量
}
```
---
### 10.3 訊息佇列 (Message Queue)
Message Queue 與 FIFO 相似都提供了 IPC 功能，但主要差異在於前者支援自定義封包類型而後者僅支援 Byte 型態。同時，Tenok 為了要使 Message Queue 能在 Interrupt 中被呼叫 (參考了 FreeRTOS 中 Queue 的設計)，因此沒有將其實作為 Syscall。在 Tenok 提供的 Serial0 驅動程式中便利用了這個特性實作了 RX 的資料接收。
以下摘錄了 Message Queue 的實作原始碼:
```
//tenok/kernel/mqueue.c
...
struct msg_queue mq_table[MQUEUE_CNT_MAX]; //Message Queue Table
int mq_cnt = 0; //目前OS中有的Message Queue的數量
mqd_t mq_open(const char *name, int oflag, struct mq_attr *attr)
{
/* 目前的Message Queue只被允許設定為非阻塞模式 */
if(!(attr->mq_flags & O_NONBLOCK))
return -1;
/* 分配和初始化 Pipe (Ring buffer) 的資料結構 (註: 大小為封包級) */
struct ringbuf *pipe = memory_pool_alloc(&mem_pool, sizeof(struct ringbuf));
uint8_t *pipe_mem = memory_pool_alloc(&mem_pool, attr->mq_msgsize * attr->mq_maxmsg);
ringbuf_init(pipe, pipe_mem, attr->mq_msgsize, attr->mq_maxmsg);
/* 掛載到Message Queue的Table上 (注意: Message Queue與File system屬於不同子系統) */
int mqdes = mq_cnt;
mq_table[mqdes].pipe = pipe; //將分配到的Pipe記憶統空間記錄到Message Queue Table上
mq_table[mqdes].lock = 0; //初始化Message Queue的Spinlock
strncpy(mq_table[mqdes].name, name, FILE_NAME_LEN_MAX); //紀錄Message Queue的名稱 (目前僅用做除錯使用)
mq_cnt++;
/* 回傳Message Queue的描述子 (Descriptor) */
return mqdes;
}
/* mq_receive()只能被User Task呼叫 */
ssize_t mq_receive(mqd_t mqdes, char *msg_ptr, size_t msg_len, unsigned int *msg_prio)
{
/* 從Table中取出Message Queue */
struct msg_queue *mq = &mq_table[mqdes];
/* 取出Message Queue的Task等待清單 */
struct list *task_wait_list = &mq->pipe->task_wait_list;
ssize_t retval;
/* 進入Critical Section */
spin_lock_irq(&mq->lock);
/* 檢查Pipe (Ring buffer) 中是否有足夠的資料可以提供 */
if(msg_len > mq->pipe->count) {
/* 否，將Task放入等待清單中 */
prepare_to_wait(task_wait_list, &running_task->list, TASK_WAIT);
/* 將Task想讀取的數量紀錄到Task Control Block中 */
running_task->file_request.size = msg_len;
retval = -EAGAIN; //失敗，稍後用來回傳提示使用者重新嘗試
} else {
/* 從Pipe (Ring buffer) 中取出資料 */
int i;
for(i = 0; i < msg_len; i++) {
ringbuf_get(mq->pipe, &msg_ptr[i]);
}
retval = msg_len; //成功，稍後回傳接收到的大小
}
/* 離開Critical Section */
spin_unlock_irq(&mq->lock);
return retval; 回傳，程式結束
}
/* mq_send()可以被User task或是Interrupt呼叫 */
int mq_send(mqd_t mqdes, const char *msg_ptr, size_t msg_len, unsigned int msg_prio)
{
/* 從Table中取出Message Queue */
struct msg_queue *mq = &mq_table[mqdes];
/* 取出Message Queue的Task等待清單 */
struct list *task_wait_list = &mq->pipe->task_wait_list;
/* 進入Critical Section */
spin_lock_irq(&mq->lock);
/* 將資料放入Pipe (Ring buffer) 中 */
int i;
for(i = 0; i < msg_len; i++) {
ringbuf_put(mq->pipe, &msg_ptr[i]);
}
/* 檢查是否有Task正在等待中 */
if(!list_is_empty(task_wait_list)) {
/* 從清單中取出一個Task */
struct task_ctrl_blk *task = list_entry(task_wait_list->next, struct task_ctrl_blk, list);
/* 檢查此Task先前請求的接收量是否可以被滿足 */
if(task->file_request.size <= mq->pipe->count) {
/* 是，將其喚醒重新嘗試接收 */
wake_up(task_wait_list);
}
}
/* 離開Critical section */
spin_unlock_irq(&mq->lock);
return msg_len; //回傳接收到的數量
}
```
## XI: 未來方向
**High-priority goal:**
特化 Tenok 於 Real-time Robotics Control 的應用，否則作為 General-purpose 的作業系統此專案會不具足夠的特色/競爭性 (大抵是 jserv 的意見)
1. Real-time Performance 的驗證/分析
2. 透過 Meta-language 產生通訊專用的程式碼，並提供視覺化工具用於繪製重要訊號 (參考自 [ROS](http://wiki.ros.org/msg))
* 直接支援 ROS 聽起來也很好但大概率會無法達成
3. 支援 [Gazebo](https://gazebosim.org/home) 做 Software-in-the-loop (SIL) simulation
4. 提供 [MAVLink](https://mavlink.io/en/) 通訊的 System Module
5. Online variable tunning? (自動控制演算法調整參數時不用修改程式6重新編譯)
7. 完善檔案系統的設計
8. Unit-test
9. 支援 `malloc()` / `free()`
10. Task scheduling 的視覺化
11. 做完以上幾個重要功能的話就來 Port 一個簡易版的四軸飛控作為應用範例
**Low-priority goal:**
以下功能也想做，但除了作為練習，目前想不到實用的價值
1. 支援 RPi2040 並支援多核心、Load balancing 等
2. 支援 RISC-V (RV32)
## 附錄: Tenok API
### Syscall:
```
//tenok/kernel/syscall.h
void sched_yield(void);
void set_irq(uint32_t state);
void set_program_name(char *name);
int fork(void);
uint32_t sleep(uint32_t ticks);
int mount(const char *source, const char *target);
int open(const char *pathname, int flags, mode_t);
ssize_t read(int fd, void *buf, size_t count);
ssize_t write(int fd, const void *buf, size_t count);
long lseek(int fd, long offset, int whence);
int fstat(int fd, struct stat *statbuf);
int opendir(const char *name, DIR *dir);
int readdir(DIR *dirp, struct dirent *dirent);
uint32_t getpriority(void);
int setpriority(int which, int who, int prio);
int getpid(void);
int mknod(const char *pathname, mode_t mode, dev_t dev);
```
### Function call:
```
//tenok/kernel/semaphore.h
int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_post(sem_t *sem);
int sem_trywait(sem_t *sem);
int sem_wait(sem_t *sem);
int sem_getvalue(sem_t *sem, int *sval);
//tenok/kernel/mutex.h
int pthread_mutex_init(_pthread_mutex_t *mutex, const pthread_mutex_attr_t *attr);
int pthread_mutex_unlock(_pthread_mutex_t *mutex);
int pthread_mutex_lock(_pthread_mutex_t *mutex);
//tenok/kernel/mqueue.h
mqd_t mq_open(const char *name, int oflag, struct mq_attr *attr);
ssize_t mq_receive(mqd_t mqdes, char *msg_ptr, size_t msg_len, unsigned int *msg_prio);
int mq_send(mqd_t mqdes, const char *msg_ptr, size_t msg_len, unsigned int msg_prio);
//tenok/kernel/file.h
int fopen(const char *pathname, const char *mode, FILE *file);
size_t fread(void *ptr, size_t size, size_t nmemb, FILE *fstream);
size_t fwrite(const void *ptr, size_t size, size_t nmemb, FILE *fstream);
int fseek(FILE *stream, long offset, int whence);
int fileno(FILE *stream);
```
## 參考資料
1. [rtenv+: 成大資工Wiki](http://wiki.csie.ncku.edu.tw/embedded/rtenv)
2. [Build a Minimal Operating System in ARM Cortex-M3](http://wiki.csie.ncku.edu.tw/embedded/summer2015/mini-arm-os.pdf)
3. [從無到有打造 IoT 作業系統核心：以 Piko/RT 為例](https://hackmd.io/@owlfox/SyaTF2VgL/https%3A%2F%2Fhackmd.io%2Fs%2FSJHIn4b_W)
4. [FreeRTOS 內核實現與應用開發實戰指南 — 基於 STM32](https://www.tenlong.com.tw/products/9787111618256)
5. [嵌入式系統建構：開發運作於STM32的韌體程式](http://wiki.csie.ncku.edu.tw/embedded/Lab19/stm32-prog.pdf)
6. [Cortex-M4 Devices Generic User Guide - Arm](https://documentation-service.arm.com/static/5f2ac76d60a93e65927bbdc5?token=)
7. [Cortex-M4(F) Lazy Stacking and Context Switching - Application Note 298](https://developer.arm.com/documentation/dai0298/a/)
8. [STM32 Cortex®-M4 MCUs and MPUs programming manual](https://www.st.com/resource/en/programming_manual/pm0214-stm32-cortexm4-mcus-and-mpus-programming-manual-stmicroelectronics.pdf)
9. [ARM Cortex-A Series Programmer's Guide for ARMv7-A: Procedure Call Standard
](https://developer.arm.com/documentation/den0013/d/Application-Binary-Interfaces/Procedure-Call-Standard)
9. [A Beginner’s Guide on Interrupt Latency and Interrupt Latency of the Arm Cortex-M processors](https://community.arm.com/arm-community-blogs/b/architectures-and-processors-blog/posts/beginner-guide-on-interrupt-latency-and-interrupt-latency-of-the-arm-cortex-m-processors)
10. [Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync?type=view)
11. [Priority Inversion on Mars](https://www.slideshare.net/jserv/priority-inversion-30367388?fbclid=IwAR0GdoqVaKk41XrMoyWtO-lHasoJ4fZVhDw7X50o1GEFdgRoJAq-aNvolss)
12. [Synchronization: Spinlocks - Semaphores (CS 4410 Operating Systems, Cornell University)](http://www.cs.cornell.edu/courses/cs4410/2013su/slides/lecture06.pdf)
13. [關於GNU Inline Assembly](http://wen00072.github.io/blog/2015/12/10/about-inline-asm/)
14. [offsetof(3) - Linux manual page](https://man7.org/linux/man-pages/man3/offsetof.3.html)
15. [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list)
16. [Linux 磁碟與檔案系統管理 - 鳥哥的私房菜網站](https://linux.vbird.org/linux_basic/centos7/0230filesystem.php)
17. [淺談 Microkernel 設計和真實世界中的應用
](https://hackmd.io/@sysprog/microkernel-design)
Sign in with Wallet
Connect another wallet