# 學習實作小型作業系統 (筆記)
contributed by <`tina0405`>
github: [tina0405/raspberry-pi3-mini-os
](https://github.com/tina0405/raspberry-pi3-mini-os)
### 硬體選擇： [Raspberry Pi 3 model B](https://www.raspberrypi.com.tw/tag/bcm2837/)

| item |specfication|
| :--------: | :--------: |
| SoC | Broadcom BCM2837 |
| CPU | 1.2 GHz 64-bit quad-core ARM Cortex-A53 |
| GPU | Dual Core VideoCore IV® Multimedia Co-Processor; Open GL ES 2.0; hardware-accelerated OpenVG; 1080p60 H.264 high-profie decode |
|記憶體| 1GB LPDDR2（和 GPU 共享）|
|視訊輸出| Composite RCA; HDMI|
|音訊輸出| 3.5 mm jack; HDMI(1.3 & 1.4)|
|儲存| microSD|
|USB| USB 2.0 x 4|
|Ethernet| 10/100 RJ45|
|Wireless| 802.11n|
|Bluetooth| Bluetooth 4.1; Bluetooth Low Energy(BLE)|
|GPIO| 40-pin 2.54 mm (100 mil)| |expansion header| 2×20 strip|

### 環境
~~~
tina@tina-X550VB:~/Hw$ lsb_release -da
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 16.04.3 LTS
Release: 16.04
Codename: xenial
~~~
### raspbian
##### 選擇原因
Raspbian 是基本官方提供的作業系統我會選擇這個是因為想利用它內部提供的 bootcode.bin 和 start.elf 幫助我完成 bootloader 階段，好讓心力放在 kernel 實作部份。

* 參考 [Ahmed El-Arabawy 的 Embedded Systems: Lecture 7 （page 46-47）](https://www.slideshare.net/a_elarabawy/cu-cmp445-lec07lab01preparingthepi-48396907)


* 首先當我們將板子 power on 後， ARM 的處理器目前是 off 的狀態，而 SDRAM 是 disable 的狀態， 而是利用 GPU 來進行 start booting
* GPU 是去 ROM 裡執行`第 1 階段 bootloader`
* 接著 GPU 又會去 SD 卡中讀 FAT32 第 1 分區的 bootcode.bin
* bootcode.bin 是`第 2 階段 bootloader` 他做兩件事
1. enable SDRAM
2. 載入且執行 start.elf
* `第 3 階段 bootloader` 是 start.elf， 讀 kernel image(kernel.img)， configuration 檔 （config.txt）， 和 kernel command line 參數 (cmdline.txt)， 把這些都載入記憶體然後再喚醒 ARM 核心

##### [安裝 raspbian 步驟](https://www.raspberrypi.org/documentation/installation/installing-images/linux.md?fbclid=IwAR2bu_t8vauCXo1JtHy441EK14rgn6sYiVrnRL-_TvdSR02mlUt3ph8cCn4)
* [下載官方網址](https://www.raspberrypi.org/downloads/raspbian/)
* 我下載的是 Raspbian Stretch Lite （Minimal image based on Debian Stretch）
* Version: November 2018
* Release date: 2018-11-13
* Kernel version: 4.14
* 將 img 檔燒入 Raspberry Pi
* 載完後先進行解壓縮，會得到`img` 檔
~~~
unzip 2018-11-13-raspbian-stretch-lite.zip
~~~
* 由上面 boot 的資料，先格式化成 FAT32
~~~
tina@tina-X550VB:~/Hw$ sudo umount /dev/sdf1
tina@tina-X550VB:~/Hw$ sudo mkdosfs -F 32 -v /dev/sdf1
mkfs.fat 3.0.28 (2015-05-16)
/dev/sdf1 has 64 heads and 32 sectors per track,
hidden sectors 0x2000;
logical sector size is 512,
using 0xf8 media descriptor, with 89854 sectors;
drive number 0x80;
filesystem has 2 32-bit FATs and 1 sector per cluster.
FAT size is 691 sectors, and provides 88440 clusters.
There are 32 reserved sectors.
Volume ID is e6c75d1f, no volume label.
~~~
* 先查看 SD 卡掛在 dev 下的名字
* `df` 顯示可使用之檔案儲存空間及檔案數目
* 發現插上 SD card 後，多了一個 `/dev/sdf1`
~~~
tina@tina-X550VB:~/Hw$ df -h
Filesystem Size Used Avail Use% Mounted on
udev 3.9G 3.9G 0 100% /dev
tmpfs 787M 26M 761M 4% /run
/dev/sda5 16G 12G 3.5G 77% /
tmpfs 3.9G 37M 3.9G 1% /dev/shm
tmpfs 5.0M 4.0K 5.0M 1% /run/lock
tmpfs 3.9G 0 3.9G 0% /sys/fs/cgroup
/dev/sda6 47G 41G 4.3G 91% /home
none 3.9G 2.0M 3.9G 1% /tmp/guest-zvfiym
tmpfs 787M 84K 787M 1% /run/user/991
tmpfs 787M 124K 787M 1% /run/user/1000
/dev/sdf1 44M 23M 22M 51% /media/tina/boot
~~~
* 反掛載 `/dev/sdf`，避免再運行過程中有其他的寫入
~~~
umount /dev/sdf
~~~
* 利用`dd`: 意為 data description， 能夠將輸入寫到標準輸出中
* `if`= input file ;`of`= output file
* 所以`of` 應該要填入 SD 卡的位置 of=/dev/sdf
~~~
dd bs=4M if=2018-11-13-raspbian-stretch-lite.img of=/dev/sdx conv=fsync
~~~

### [測試 serial port](https://cdn-learn.adafruit.com/downloads/pdf/adafruits-raspberry-pi-lesson-5-using-a-console-cable.pdf)
在 SD 安裝完後 raspbian 後先別急著把其他除了 bootloader 的檔案刪掉，我們可以先用原本的 kernel 測試 serial port 是否正常能使用。
* 因為使用實驗室的 raspberry pi， 在一年前廠商所附的 USB 轉 Serial port 線被學長燒掉，目前是用同類型的 PL2303HX 晶片代替， 雖然從 ６ pin 變 4 pin， 但如果只是要連接 Serial port 其實很夠用。
* 晶片上和板子上的 TX 接 RX， RX 接 TX

* 在 boot/[config.txt](https://my.oschina.net/funnky/blog/132885) 文件中打開 `enable_uart=1` （如下）

~~~
# Uncomment this to enable the lirc-rpi module
#dtoverlay=lirc-rpi

# Additional overlays and parameters are documented /boot/overlays/README

# Enable audio (loads snd_bcm2835)
dtparam=audio=on
enable_uart=1
~~~
* 改好後，拿出 SD 卡插到板子上，接上 serial port， hdmi， 開啟電源
* 電腦端下指令和 ttyUSB0 做傳輸，就成功了！
~~~
sudo screen /dev/ttyUSB0 115200
~~~
---
接下來的內容我會參考兩份 github 的開放資源做學習， 瞭解其操作後，接著再去針對我的 kernel 做進一步的設計
* [Learning operating system development using Linux kernel and Raspberry Pi](https://github.com/s-matyukevich/raspberry-pi-os)
* 這份對初步了解作業系統，及內部暫存器操作非常有幫助，當然還是要對照著 ARMv8 手冊來看
* [Bare Metal Programming on Raspberry Pi 3](https://github.com/bztsrc/raspi3-tutorial)
* 這份是將周邊硬體的 memory 都整理好， 使用起來相當方便， 不用像之前在冷門開發板上，還要去 u-boot 去 kernel 裡抓週邊
---
### 第一支程式 hello world！
程式碼放在 [我的github](https://github.com/tina0405/raspberry-pi3-mini-os/tree/master/1.hello_world) 上，首先我們需要一個 linker script 去幫我們放置以下的程式，我們先定一個 `.text.boot` 段， 之後有關開機的 initial 內容就放置在這。
* boot.S
* 搭配 [Cortex-A series processors](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0500g/BABHBJCI.html): 從 MPIDR_EL1 的末端撈出 processor id， `and x0, x0,#0xFF`， 如果是 Core0 就抓出來做初始化，因為初始化只會做一次， 其他的處理器就去 `proc_hold` 裡等待。
* 初始化的內容，也就是跳轉到 `master label` 後是清空 bbs 段
~~~C=
#include "mm.h"

.section ".text.boot"

.globl _start
_start:
mrs x0, mpidr_el1
and x0, x0,#0xFF // Check processor id
cbz x0, master // Hang for all non-primary CPU
b proc_hold

proc_hold:
b proc_hold

master:
adr x0, bss_begin
adr x1, bss_end
sub x1, x1, x0
bl memzero

mov sp, #LOW_MEMORY
bl kernel
b proc_hold // should never come here
~~~
* kernel.c
~~~C=
#include "uart.h"
void kernel(void)

uart_init();
uart_send_string("Hello, world!\r\n");

while (1) {
char word = uart_recv();
uart_send(word);
}
}
~~~
* config.txt
* `kernel_old=1` 規定 kernel image 被載入 address 0.
* `disable_commandline_tags=1` GPU 不會傳遞任何command line 的參數給 booted image。

* `-Map` 參數能讓我們了解其配置，指令放至 Makefile 裡了。

~~~
.text.boot 0x0000000000000000 0x30
*(.text.boot)
.text.boot 0x0000000000000000 0x30 objects/boot_s.o
0x0000000000000000 _start

.text 0x0000000000000030 0x228
*(.text)
.text 0x0000000000000030 0x1d0 objects/uart_c.o
0x0000000000000030 uart_send
0x0000000000000078 uart_recv
0x00000000000000b4 uart_send_string
0x000000000000010c uart_init
.text 0x0000000000000200 0x2c objects/kernel_c.o
0x0000000000000200 kernel
.text 0x000000000000022c 0x1c objects/utils_s.o
0x000000000000022c put32
0x0000000000000234 get32
0x000000000000023c delay
.text 0x0000000000000248 0x10 objects/mm_s.o
0x0000000000000248 memzero
.text 0x0000000000000258 0x0 objects/boot_s.o

~~~
* 寫一個 [Makefile](https://github.com/tina0405/raspberry-pi3-mini-os/blob/master/1.hello_world/Makefile) 能夠加速開發流程， 裡面的 `$(wildcard *.c)` 是取出當前目錄的 .c 檔，`$(wildcard *.s)` 是取出當前目錄的 .s 檔，好將他們都編成 .o 檔，再將全部的 .o 檔 link 起來。

* 搬進 SD 卡的 FAT32 的第1分區 /boot， 此時可以留下前面提到的開機流程需要的幾個檔案即可。

---
### 讓四核操控 serial port

* [程式碼](https://github.com/tina0405/raspberry-pi3-mini-os/tree/master/3.four_core_uart)，延續上一篇 `hello world！` 這次來控制 4 顆核心，首先我們不再把其他三顆核心放到 `proc_hold` ，而是讓他們進入 `setup_stack`， 在這至少要確保不會 override 核心的 image 檔，用 `#LOW_MEMORY` 先給 4MB ， 而 stack pointer 的配置如下：
~~~
+----------------+ physical address 0x0
| |
| image | ---> size 4MB
| |
|----------------| Core 0 stack pointer
| Core 0 stack | ---> size 2KB
|----------------| Core 1 stack pointer
| Core 1 stack | ---> size 2KB
|----------------| Core 2 stack pointer
| Core 2 stack | ---> size 2KB
|----------------| Core 3 stack pointer
| Core 3 stack | ---> size 2KB
+----------------+

~~~
* boot.S 的 `memzero` 只需收兩個參數，一是開始地址，二是所需空間。
~~~ c=
.globl _start
_start:
mrs x0, mpidr_el1
and x0, x0,#0xFF // Check processor id
cbz x0, master // initial master CPU
b setup_stack

proc_hold:
b proc_hold

master:
adr x0, bss_begin
adr x1, bss_end
sub x1, x1, x0
bl memzero

// each processor have to set up stack

setup_stack:
mrs x0, mpidr_el1
and x0, x0,#0xFF // Check processor id
mov x1, 0x4000 // 2Kb for stack
mul x1, x1, x0
mov x2, #LOW_MEMORY // image adresses in 0x0; Start of stack pointer do not override image
add x1, x1, x2 // base + offset
mov sp, x1
bl kernel
b proc_hold // should never come here
~~~
* `memzero`
* `subs` : set flag， 通常下一步會去比較 Z flag
* `b.gt`: 1100 = GT - Z clear, and either N set and V set, or N clear and V set (>)
* `xzr`: 是設計來取出零常數量的暫存器，通常用 wzr/xzr 來表示
* 參考 [subs](http://users.ece.utexas.edu/~valvano/EE345M/Arm_EE382N_4.pdf)，[arm assembler](http://www.keil.com/support/man/docs/armasm/armasm_dom1361289908769.htm)
~~~
memzero:
str xzr, [x0], #8
subs x1, x1, #8
b.gt memzero
ret
~~~
* Condition Code Flags

~~~
N = Negative result from ALU flag.
Z = Zero result from ALU flag.
C = ALU operation Carried out.
V = ALU operation oVerflowed.
~~~

* kernel.c
* 在跳到 kernel 前把 processor id 存到 x0， 傳近來後要印出來必須是 char 的型態，並加上結尾符 `'\0'`，不然會停止不了，只有 core 0 會做 uart_init（），因為硬體只有一個，其他核心則是先以 delay 的方式做等待，避免互相搶佔 uart 硬體資源，之後如果能實作 mutex 就可以先把資源鎖住，等用完再釋放。
~~~c=
void kernel(int procid)
{
char procstr[2];
procstr[0] = procid + '0';
procstr[1] = '\0';

if(procid == 0) {
uart_init();
}
else {
delay(100000 * procid);
}

uart_send_string("Hello from processor ");
uart_send_string(procstr);
uart_send_string("\r\n");

if(procid ==0) {
while (1) {
uart_send(uart_recv());
}
}
else {
while(1) {}
}
}
~~~
* 以下是結果

---
### Exception Level
[程式碼](https://github.com/tina0405/raspberry-pi3-mini-os/tree/master/2.exception_level/el_3)首先在暫存器沒有任何設定之下先單純測試 exception level，但在 kernel 內至少要有簡易的 print 可以將結果印再螢幕上 ， 拿了 gnu 的 [printf](http://www.sparetimelabs.com/tinyprintf/tinyprintf.php) 來做輸出，文中提到只要將 `putc` 放入函式中 `init_printf(NULL,putc)` 即可利用， 如果照以上程式碼做的話，會得到 `exception level`： 3


* 每個支持 ARM.v8 architecture 的 ARM 處理器，都有 4 exception levels（EL）.
* `EL0` 通常 user process 應該要不能拿到別的 process 的資料，為了達到這些行為， 作業系統會將 user process 設定在 EL0， 但在這個 exception level， process 可以擁有自己的虛擬記憶體， 不能用指令去改變虛擬記憶體的設定， 所以為了確保 process 獨立，作業系統要準備分開的虛擬記憶體空間給每個 process ，而且在處理 user process 前，處理器應該要設定成 EL0
* `EL1` 作業系統層級，可以拿到控制虛擬記憶體設定的那些暫存器， 也可以拿到系統暫存器
* `EL2` 給 host OS 使用 ，guest OS 只能使用 `EL1`.
* `EL3` hardware level.
* 利用 `CurrentEL` 暫存器，來瞭解目前的 exception level， 但因為有 2 個保留 bit 在右邊，所以右移2個
~~~c=
.globl get_el
get_el:
mrs x0, CurrentEL
lsr x0, x0, #2
ret
~~~
* 然後再在 C 中使用， 這時候已經可以把 printf 拿來用了。
~~~c=
int el = get_el();
printf("Exception level: %d \r\n", el);
~~~
* 在 ARM 的架構裡， 在沒有更高 level 的軟體支援的前提下，不能增加程式自己的 exception level ，其實這個設定是有原因的，如果每個程式都可以任意改變 EL 設定的話，這樣他就有可能拿到別支程式的 data。 很重要的一點是，Current EL 只有在例外產生的時候才能改變，但這種情況只有在執行違法指令（例如在嘗試拿取不存在的記憶體位置，或除以 0） 也是有 application 可以故意執行 `svc` 指令來產生例外。 硬體產生的中斷也可被認為是一種特別形式的例外。 然而例外被產生跟著以下步驟發生（這邊所定義的例外，是處理 EL n 的情形）

1. 當前指令的地址是存在 ELR_ELn 暫存器 (全名 Exception link register)
2. 當前處理器狀態 CPSR (Current Processor Status Register) 是被存在 SPSR_ELn 暫存器 (全名Saved Program Status Register)
3. 一個 Exception handler 被執行時，不論有沒有工作需要被做，都會去執行。
5. Exception handler 呼叫 `eret` 指令. 這個指令重新儲存處理器狀態（從 `SPSR_ELn` 暫存器裡取得新狀態），然後再從 `ELR_ELn` 裡拿到地址恢復執行。

#### 切換到 EL1
[程式碼](https://github.com/tina0405/raspberry-pi3-mini-os/tree/master/2.exception_level/el_1)，一般而言作業系統並沒有義務切換到 EL1，但是在 EL1 讓我們有特權執行一些 OS 的任務
* 先關掉 MMU， MMU 會在 page table 設定好後，再次打開，現階段先關掉， 而 `sctlr_el1` 是可以被大於等於 EL1 層級的 exception 拿到， 而暫存器 0 的位置是控制 MMU 參考 [ARMv8 手冊 p.2654](https://static.docs.arm.com/ddi0487/ca/DDI0487C_a_armv8_arm.pdf?_ga=2.109811589.1077926107.1543714027-1596023854.1506794914)，所以才會用 `#define SCTLR_MMU_DISABLED (0 << 0)` 和`#define SCTLR_MMU_ENABLED (1 << 0)` 來定義開關 
~~~
ldr x0, =SCTLR_VALUE_MMU_DISABLED
msr sctlr_el1, x0
~~~
* 我們其實不會用到 hypervisor. `hcr_el2`（Hypervisor Configuration Register EL2） 雖然沒有用到但還是要給予基本的設定， 因為他牽動到 EL1 的例外狀態，執行的狀態應該要是 `AArch64` 而非`AArch32`，而這邊就是在做 configure 的設定.
~~~
ldr x0, =HCR_VALUE
msr hcr_el2, x0
~~~
* `scr_el3` 是負責控制安全設定。例如：他控制更低階層執行安全或不安全狀態。 他也可以控制 EL2 執行狀態， 他讓 EL2 可以執行 AArch64 的狀態，而且所有比 EL2 低的 exception levels 將會不安全，可參考 [ARMv8 手冊 p.2648](https://static.docs.arm.com/ddi0487/ca/DDI0487C_a_armv8_arm.pdf?_ga=2.109811589.1077926107.1543714027-1596023854.1506794914)， NS-bit(non-security) 值給 0 的話，有些 TLB 指令是不能用的。
~~~
ldr x0, =SCR_VALUE
msr scr_el3, x0
~~~
* `spsr_el3` 暫存器的設定就如同前面所說，能設定處理器的狀態，然後再利用 `eret` 指令重新儲存處理器的狀態。
~~~
ldr x0, =SPSR_VALUE
msr spsr_el3, x0
~~~
* 我們利用 `#define SPSR_MASK_ALL (7 << 6)` 來關閉中斷，再利用 `#define SPSR_EL1h (5 << 0)` 來決定後面 3-bits 的 exception level， 哪個例外的 stack pointer， 如下：


* `elr_el3` 裏面放置的地址是在 eret 指令執行後要跳轉回去的地址， 這邊我們先把 `el1_entry` lebal 的地址載回去， 告訴他重新設完處理器後要回到 `el1_entry`，也就是原本程式初始化的那段。

~~~
adr x0, el1_entry
msr elr_el3, x0
eret
~~~
* 現在在回頭將 `CurrentEL` 暫存器的值印出來，結果為`exception level`： 1

---
http://jasonyychiu.blogspot.com/2017/11/interrupt.html
### interrupt and exception
[程式碼](https://github.com/tina0405/raspberry-pi3-mini-os/tree/master/4.interrupt)中用任意鍵切換兩個 timer 1 和 timer 3 的中斷， 在 [ARMv8](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.den0024a/CHDEEDDC.html) 架構中，中斷被視為是例外的一種，以下介紹 4 種類型的例外:
* `Synchronous exception Exceptions`： 這種例外通常是被當前執行的指令造成。例如： 你可以使用 str 指令去儲存一些 data 在不存在的記憶體空間。 在這個 case 裡，一個同步的例外會被產生，同步例外會被用來產生軟體中斷，是藉由 svc 指令來產生的軟體中斷（也稱作 synchronous exception），將在後面提及。

* `IRQ (Interrupt Request)`： 這個是正常中斷，他們是非同步的，意思是他們與當前指令無關，和 synchronous exceptions 比起來，他們並不是被處理器產生的，而是透過外部硬體去控制。
p109
* `FIQ (Fast Interrupt Request)`： 這個類型的中斷叫作快速中斷， 是為了例外優先順序而存在的。如此一來他可以分辨這個例外是正常還是快速。 快速中斷再發出第一個訊號後，將由一個 separate exception handler 來處理。Linux 裡沒有使用 Fast Interrupt 這個結構。

* `SError (System Error)`： 系統錯誤也像 IRQ 和 FIQ，是由外部硬體發出非同步中斷。但又不同於 IRQ 和 FIQ，SError 會指出一些錯誤條件。 [例子](https://community.arm.com/processors/f/discussions/3205/re-what-is-serror-detailed-explanation-is-required)

#### Exception vectors
每個例外類型都需要有自己的 handler。 個別的 handlers 應該要被定義再不同的執行狀態，這裡有4個執行狀態，如果執行在 EL1 就必須了解它們：
1. `EL1t Exception` 是 EL1 的 stack pointer 是和 EL0 一起共享時。這個會發生在 SPSel 暫存器值是 0 時。
2. `EL1h Exception` 是發生在 EL1 貢獻 stack pointer 是分配給 EL1，這個會發生在 SPSel 暫存器值是 1 時，也就是我們要使用的狀態。
3. `EL0_64 Exception` EL0 執行在 64-bit 模式
4. `EL0_32 Exception` EL0 執行在 32-bit 模式

一般而言， 我們應該會有 16 種狀態，因為一種例外有 4 種執行狀態（4*4）。有一種特別的結構，他會掌握所有 handler，我們稱之為 exception vector table 或是 vector table。 這個表可以被想像成例外向量的矩陣，每個 exception vector (or handler) 都有一組連續的指令負責處理特定的例外， 因此在手冊裡提到每個例外最多都會佔據 0x80 bytes （[手冊 p.1876](https://static.docs.arm.com/ddi0487/ca/DDI0487C_a_armv8_arm.pdf?_ga=2.109811589.1077926107.1543714027-1596023854.1506794914)）。 這些記憶體空間雖然不多，但開發者還是可以讓程式從例外向量跳轉去其他記憶體空間。
* [align 錯誤的例子](https://blog.csdn.net/lemon_fantasy/article/details/3597138)，有些程式如果沒 align ，會造成錯誤。

* 首先先寫一個可以進入 exception vector 的 macro，至於這裡 `.align 7` 的原因， 是因為每個例外長度都為 0x80 bytes， 換算成 10 進位就是 128，而 2^7 也恰好等於 128

~~~
.macro ventry label
.align 7
b \label
.endm
~~~
* 即使我們不會全部 exception 都用到，我們還是必須設置，因為我們必須從其他例外的錯誤訊息中去觀察作業系統行為。
#### vector table 的設定
處理器並不知道例外向量表在哪，所以我們必須把 vector table 的地址存入暫存器 `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
~~~
* 並且照著[手冊 p.1876](https://static.docs.arm.com/ddi0487/ca/DDI0487C_a_armv8_arm.pdf?_ga=2.109811589.1077926107.1543714027-1596023854.1506794914) 將每個 exception level 的順序放好，如 `vectors` 的 label 那樣：
* 我們當前的 `exception level = 1`， 所以 `lower exception level = 0`，因此順序如下：
~~~ c =
vectors:
ventry sync_invalid_el1t // Synchronous EL1t
ventry irq_invalid_el1t // IRQ EL1t
ventry fiq_invalid_el1t // FIQ EL1t
ventry error_invalid_el1t // Error EL1t

ventry sync_invalid_el1h // Synchronous EL1h
ventry el1_irq // IRQ EL1h
ventry fiq_invalid_el1h // FIQ EL1h
ventry error_invalid_el1h // Error EL1h

ventry sync_invalid_el0_64 // Synchronous 64-bit EL0
ventry irq_invalid_el0_64 // IRQ 64-bit EL0
ventry fiq_invalid_el0_64 // FIQ 64-bit EL0
ventry error_invalid_el0_64 // Error 64-bit EL0

ventry sync_invalid_el0_32 // Synchronous 32-bit EL0
ventry irq_invalid_el0_32 // IRQ 32-bit EL0
ventry fiq_invalid_el0_32 // FIQ 32-bit EL0
ventry error_invalid_el0_32 // Error 32-bit EL0
~~~
* 再來是中斷記憶體空間的配置， 參考 [BCM2837 ARM Peripherals 手冊 p112](https://github.com/raspberrypi/documentation/files/1888662/BCM2837-ARM-Peripherals.-.Revised.-.V2-1.pdf)
* 記憶體空間的配置是， `PBASE` 為 `0x3F000000`，一開始覺得很奇怪手冊上明明提到 base address 為 `0X7E00B000`， 為什麼會變成 `0X3F00B000`，後來在規格書的前面找到一段話：
~~~
Peripherals (at physical address 0x3F000000 on) are mapped
into the kernel virtual address space starting at address
0xF2000000. Thus a peripheral advertised here at bus address
0x7Ennnnnn is available in the ARM kenel at virtual address
0xF2nnnnnn.
~~~
~~~ c=
#define IRQ_BASIC_PENDING (PBASE+0x0000B200)
#define IRQ_PENDING_1 (PBASE+0x0000B204)
#define IRQ_PENDING_2 (PBASE+0x0000B208)
#define FIQ_CONTROL (PBASE+0x0000B20C)
#define ENABLE_IRQS_1 (PBASE+0x0000B210)
#define ENABLE_IRQS_2 (PBASE+0x0000B214)
#define ENABLE_BASIC_IRQS (PBASE+0x0000B218)
#define DISABLE_IRQS_1 (PBASE+0x0000B21C)
#define DISABLE_IRQS_2 (PBASE+0x0000B220)
#define DISABLE_BASIC_IRQS (PBASE+0x0000B224)
~~~
#### timer 的設定
在[文件](https://embedded-xinu.readthedocs.io/en/latest/arm/rpi/BCM2835-System-Timer.html)中提到，BCM2835 系統中的 timer 0 和 timer 2 是留給 GPU 使用的，而我們真的可以用到的是 timer 1 和 timer 3，所以就用[程式碼](https://github.com/tina0405/raspberry-pi3-mini-os/tree/master/4.interrupt)練習操控 timer 1 和 timer 3 的切換。
* irq.c 裡的 `extern char choose` 是在 kernel 裡給使用者使用的參數，而 `ENABLE_IRQS_1` 放置各個 `timer` 應該要設置的 bit

~~~c=
extern char choose;
void enable_interrupt_controller()
{
switch (choose) {
case '1':
put32(ENABLE_IRQS_1, SYSTEM_TIMER_IRQ_1);
break;
case '3':
put32(ENABLE_IRQS_1, SYSTEM_TIMER_IRQ_3);
break;
default:
printf("Undefine choose: %d\r\n", choose);
}

}
~~~
* 還記得前面 `vector table` 會進入 `el1_irq` 的中斷嗎？這時候 jump 到 `el1_irq` 的 label 時就會執行 `handle_irq`
~~~c=
　el1_irq :
kernel_entry
bl handle_irq
kernel_exit
~~~
* `IRQ_PENDING_1`（0-31 bit）這個暫存器是掌握了中斷的狀態，我們可以利用這個暫存器去檢查 interrupt 是由哪個 timer 產生的。注意多個中斷是可以同時被等待的。這邊我讓各個中斷印出自己所屬的 timer。
~~~c=
void handle_irq(void)
{
unsigned int irq = get32(IRQ_PENDING_1);
switch (irq) {
case (SYSTEM_TIMER_IRQ_1):
handle_timer_irq();
break;
case (SYSTEM_TIMER_IRQ_3):
handle_timer_irq_3();
break;
default:
printf("Unknown pending irq: %x\r\n", irq);
}
}
~~~
* 以下是切換結果， 但在 disable 後會做完最後一個 pending interrupt，所以在下個 timer 開始前，會再做一次前個 timer：
---
### 行程管理者 (Process Manager)
參考：[洪文彬學長的論文---嵌入式微核心系統之設計與實作](http://etds.lib.ncku.edu.tw/etdservice/view_metadata?etdun=U0026-0812200911394652&query_field1=&query_word1=%E6%B4%AA%E6%96%87%E5%BD%AC)
行程管理者是用來管理系統中的行程。 目前暫定此系統會處理 Process 及 Thread。
* 行程管理區塊(PCB)在系統中是很龐大的資料結構，也包括以下機制：
* 伺服行程管理
* 使用者行程管理
* 執行緒管理

* 論文中的排程的， 行程就緒佇列(Ready Queue)共有 64 個,且系統中行程的優先權共有 64 種。一個行程的優先權以無號整數(Unsigned Integer)(0 ~ 63)來表示,且較小的值表示高優先權,較大的值表示低優先權。

### Ｍinix　行程排程
Minix　使用多重佇列演算法，先說明 Ｍinix 將任務分為四個層，而在佇列中要考慮的就是，第二層的Ｉ/O 任務行程，伺服器(服務者)行程在第三層，使用者行程在第四層
而排程程式為這個層次準備了三個可執行行程的佇列，Rdy_head 指向佇列第一個元素 Rdy_tail 指向佇列最後一個元素，每當行程從暫停被喚醒時，便將其置於末端(Rdy_tail 有助於此項操作)，每當行程被暫停時，就將其從佇列中移除，此排程演算法簡單來說就是會選取最高優先權且非空的第一個行程，如果所有佇列皆空，則 idle


pick_proc 檢查每個佇列，先對 TASK_Q 做測試，如果準備好了，就設定 proc_ptr 並回傳，但如果 TASK_Q 和 SERVER_Q 都為空， USER_Q要做時不只需要將 proc_ptr 並回傳，還需回傳 bill_ptr，意思是向使用者索取 CPU 的費用，若無佇列準備則回到 idle，因為佇列在任何變動下皆會影響下一步，因此需要呼叫 pick_proc 來重新設定 proc_ptr

使用者任務在受限的時間中進行，因此為循環式排程，而其他如檔案系統或 I/O 任務則不用受時間限制，因為他相信作業系統是安全的，做完會停止下來

#### Q1： 論文的硬體上沒有 MMU 無法實作 fork， raspberry 上有， 用 multi-thread 來補足 fork？
* Copy-on-write 需要 MMU 幫忙（有人要寫入時，會回傳副本給呼叫此 function 的人，如果沒有人改，就共用一份）

#### Q3: 就實作面來說，有父行程和子行程做切換，有什麼好處？
* 父行程和子行程可以有自己的 data，開發者再寫程式時不需顧慮子行程會改到父行程的資料

#### 資料來源: [fork](https://blog.albert-chen.com/swoole-basic-concepts/)
* process 中還另外包含了 parent 與 child 的概念， 而 threads 是被包含在 process 中，如果拿例子來說， process 就像是工廠， thread 則是員工，工廠只有一個，員工卻有可能有很多。

#### [Unix fork](https://slideplayer.com/slide/10091132/)
* 子行程複製父行程的資料，由 ret 值去判斷父行程或子行程
* process tree（行程樹），他的 root 是一種特別的結構，由 OS 創建。

---
### 實現簡易排程
這是[原作者程式碼](https://github.com/tina0405/raspberry-pi-os/tree/master/src/lesson04)，但我想將排程改成上述 Minix 之結構， 一開始的程式碼保留 4MB 放置 kernel image，將 stack pointer 放置 kernel image 所佔空間的最低處 0x00400000。
~~~
0 +------------------+
| kernel image |
|------------------|
| |
|------------------|
| init task stack |
0x00400000 +------------------+
| |
| |
0x3F000000 +------------------+
| device registers |
0x40000000 +------------------+
~~~
* 將暫存器狀態儲存下來
~~~C=
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;
};
~~~
* 大家一起使用 process 這個 function
~~~ c=
void process(char *array)
{
while (1){
for (int i = 0; i < 5; i++){
uart_send(array[i]);
delay(100000);
}
}
}
~~~

* 排程演算法
task 矩陣裡有 64 個任務， 會先檢查任務是否是 TASK_RUNNING 及他的 counter 是否大於 c

~~~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();
}
~~~
* The X30 general-purpose register is used as the procedure call link register. <ARM Architecture Reference Manual ARMv8, for ARMv8-A architecture profile>

* 中斷處理，每次重新 _schedule()，以下是 ARM v8的中斷處理

* 其 pState 暫存器 bit 所代表意義：

* 回到實作層面將資料結構從靜態矩陣改成動態的linked list 排程演算法選用多重佇列（Multiple Queue）。
* 過度時期使用排程(只能容納 64 任務)
~~~
+-------------------------------+
| | | | | | | |
|PCB|PCB|PCB| ... |PCB|PCB|PCB|
| | | | | | | |
+-------------------------------+
~~~
* 目前的排程演算法結構

---
### 使用者行程及系統呼叫
我們將會將使用者的行程定為 EL0，這限制了他們獲得特權處理器的操作，沒有這個步驟，其他技術將沒辦法使用，因為使用者的程式將有可能將安全設定重寫， 但當我們限制使用者程序禁止使用 kernel 的程式，他要怎麼樣使用一些像 print 的簡單程式來使用 UART 呢？ 我們會實作一些簡單的 API 來執行，而這些API 被執行時必須將 exception level 提升到 EL1 ，呼叫這些 API 就叫作系統呼叫
#### 系統呼叫的執行
系統呼叫，最簡單的定義，就是希望每個系統呼叫都是一個同步例外，如果一個使用者決定要去執行一個系統呼叫，那第一步將是準備所需參數，然後再切換到 svc 指令。 這個指令產生同步的，這種例外是在 EL1 處理的，也就是作業系統處理的程式。 而 OS 會驗證參數，會應要求和執行正常例外 return，並確保在 svc 指令執行完時，恢復 EL0。
~~~
.globl call_sys_write
call_sys_write:
mov w8, #SYS_WRITE_NUMBER
svc #0
ret
~~~

只要使用 svc 指令，就可以產生同步例外， 並觸發 vector table 裡的 el0_sync， 因為 system call 是由 user mode 去執行所以是 el_0，`#ESR_ELx_EC_SHIFT` 被定為 26(右移26)， 是因為要去找 exception class，參考 [ARMv8 手冊 p.2436](https://static.docs.arm.com/ddi0487/ca/DDI0487C_a_armv8_arm.pdf?_ga=2.109811589.1077926107.1543714027-1596023854.1506794914)

~~~
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
~~~
* 而比較的話則是看 [ARMv8 手冊 p.2438](https://static.docs.arm.com/ddi0487/ca/DDI0487C_a_armv8_arm.pdf?_ga=2.109811589.1077926107.1543714027-1596023854.1506794914) ，而定`ESR_ELx_EC_SVC64` 為 0x15
`kernel_entry` 和 `kernel_exit` 是相對的兩個函式，在 interrupt 發生後，擔心中間產生對暫存器產生不可預期的結果，因此先將一班常用的暫存器結果存下來，做完中斷離開時再還原。
* 在 entry.S 中的 `kernel_entry` 其中比較特別的是如果是 EL0 的話，要將 `sp_el0` 先存起來，後來再還回去，因為在樹莓派裡的 `sp` 是重複使用的，先將 stack point 向地址低的地方移，再將暫存器移入。
~~~
.macro kernel_entry, el
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]

.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

stp
, x21, [sp, #16 * 15]
stp x22, x23, [sp, #16 * 16]
.endm
~~~

* 跳到 `el0_svc` 執行系統呼叫前，會先打開 interrupt
* `uxtw`
* `b.hs`

~~~
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
blr x16 // call sys_* routine
b ret_from_syscall
ni_sys:
handle_invalid_entry 0, SYSCALL_ERROR
~~~
* `ret_from_syscall`
~~~
ret_from_syscall:
bl disable_irq
str x0, [sp, #S_X0] // returned x0
kernel_exit 0

~~~

* `kernel_exit`
~~~
.macro kernel_exit, el
ldp x22, x23, [sp, #16 * 16]
ldp x30, x21, [sp, #16 * 15]

.if \el == 0
msr sp_el0, x21
.endif /* \el == 0 */

msr elr_el1, x22
msr spsr_el1, x23

ldp x0, x1, [sp, #16 * 0]
ldp x2, x3, [sp, #16 * 1]
ldp x4, x5, [sp, #16 * 2]
ldp x6, x7, [sp, #16 * 3]
ldp x8, x9, [sp, #16 * 4]
ldp x10, x11, [sp, #16 * 5]
ldp x12, x13, [sp, #16 * 6]
ldp x14, x15, [sp, #16 * 7]
ldp x16, x17, [sp, #16 * 8]
ldp x18, x19, [sp, #16 * 9]
ldp x20, x21, [sp, #16 * 10]
ldp x22, x23, [sp, #16 * 11]
ldp x24, x25, [sp, #16 * 12]
ldp x26, x27, [sp, #16 * 13]
ldp x28, x29, [sp, #16 * 14]
add sp, sp, #S_FRAME_SIZE
eret
.endm

~~~
* 這邊的 `kernel_exit` 是搭配原作者所使用的 pt_regs 的結構。

---
### Virtual memory management
雖然 lesson5 原本的程式已經達到管理記憶體的，但是 user mode 和 kernel mode 用同一塊記憶體還是有危險性存在，這代表 user 可以任意改寫 kernel 的資料。 除此之外，就算我們能夠確保沒有惡意程式的存在，不停的確認空間是否被佔據，也增加了程式的 overhead，這也就是為什麼我們需要 Virtual memory management。

* 這個部份將會著重在虛擬記憶體，當進程 （process） 要求一塊新的記憶體空間， MMU 將會啟動，並且利用虛擬記憶體映射一塊實體記憶體給進程。
* 這裡 page 的大小定為 4kb （作者對這個數字的解釋是，每個 page 有 9 bits， 所以有 2^9 = 512 個項目，再來因為是 64 bit 處理器，一個地址佔 8 bytes， 512*8 = 4096 剛好是4kb），但 ARMv8 有支援更大 size 的 page
* 有四級階層，對照圖如下：
* PGD (Page Global Directory)
* PUD (Page Upper Directory)
* PMD (Page Middle Directory)
* PTE (Page Table Entry)
* PTE 是最後一級，指向最後的物理記憶體。
* 記憶體轉換的處理是始於 PGD Table， 而 PGD Table 的地址被存入 ttbr0_el1 暫存器。 每個進程都有一份 page table 的副本，包含 PGD 地址，當 context switch 發生時， 下一個進程的 PGD 地址將會被載入 ttbr0_el1 暫存器。

* 原作者 [s-matyukevich github](https://github.com/s-matyukevich/raspberry-pi-os/blob/master/docs/lesson06/rpi-os.md) 上的精美圖示
~~~
Virtual address Physical Memory
+-----------------------------------------------------------------------+ +-----------------_+
| | PGD Index | PUD Index | PMD Index | PTE Index | Page offset | | |
+-----------------------------------------------------------------------+ | |
63 47 | 38 | 29 | 20 | 11 | 0 | Page N |
| | | | +--------------------+ +---->+------------------+
| | | +---------------------+ | | | |
+------+ | | | | | | |
| | +----------+ | | | |------------------|
+------+ | PGD | | | +---------------->| Physical address |
| ttbr |---->+-------------+ | PUD | | | |------------------|
+------+ | | | | +->+-------------+ | PMD | | | |
| +-------------+ | | | | | +->+-------------+ | PTE | +------------------+
+->| PUD address |----+ +-------------+ | | | | | +->+--------------+ | | |
+-------------+ +--->| PMD address |----+ +-------------+ | | | | | | |
| | +-------------+ +--->| PTE address |----+ +-------------_+ | | |
+-------------+ | | +-------------+ +--->| Page address |----+ | |
+-------------+ | | +--------------+ | |
+-------------+ | | | |
+--------------+ +------------------+

~~~
* 接下來，MMU 會使用 PGD 指標和虛擬記憶體去計算相對應的實體記憶體，所有的虛擬記憶體地址都只使用 48 bits，在做轉換時， MMU 被分為4個部份。
* Bits [39 - 47] 包含索引在 PGD table 上， MMU 可以利用這個索引找到 PUD。
* Bits [30 - 38] 包含索引在 PUD table 上， MMU 可以利用這個索引找到 PMD.
* Bits [21 - 29] 包含索引在 PMD table 上， MMU 可以利用這個索引找到 PTE.
* Bits [12 - 20] 包含索引在 PTE table 上. MMU 可以利用這個索引找到實際位置.
* Bits [0 - 11] 包含 offset 在 physical page. MMU 使用 offset 去決定確切的位置，在前面找到的 page 裡（相對於原本的）

* 可是如果當要映射的記憶體空間不是 4KB， 而是 2MB 的話， 會少一個 level， 且把原本給 PTE 的空間給 offset， 讓 offset 從 12 bits 變成 21 bits， 用 21 bits 解碼 2MB的空間。
* 但我們可能都很好奇， MMU 是如何預先知道最後是要指向 PTE 還是還是 PMD？ 其實是這是 page table 裡的一個重要東西，叫作描述檔（descriptor）
~~~
descriptor format
+------------------------------------------------------------------------------------------+
| Upper attributes | Address (bits 47:12) | Lower attributes | Block/table bit | Valid bit |
+------------------------------------------------------------------------------------------+
63 47 11 2 1 0
~~~
* 這裡的關鍵是，描述檔裡的地址，會指向下一個對齊的 page， 也就是說前面 12 bits 都可以留給 MMU 做使用，先定為 0。
* bit-0: 是 valid bit， 簡單來說就是 MMU 會去看這份描述檔的 valid bit，來判斷這份 descriptor 是否有效， 因此必須填入1， 但如果是 0 就會發出同步例外，當作例外錯誤來處理（後面會講到如何分配新的 page 和新的描述檔來應對）

* bit-1: 這個 bit 指出是否現在這個 descriptor 指出下一個在這個層級中的 page table （也被稱作 "table descriptor"）或是實體 page（這種 descriptors 稱作 "block descriptors"）。

* bits[11:2]: 這些 bits 是被 table descriptors 忽略的。 因為 block descriptors 包含一些特徵，例如 mapped page 是否可被可被快取或可被執行。

* bits[47:12]: 這是存地址用的，只有[47:12]需要被儲存，其他則是先為 0。

* bits[63:48]: 其他特性.

* 每個 block descriptor 都包含了一些特性去控制虛擬記憶體， 然而這些特性有重要的一部份不是在 descriptor 中配置的。取而代之， ARM 處理器允許他們儲存一些重要的資訊在一個特殊的暫存器 `mair_el1`，這個暫存器包含 8 個部份，每個部份 8-bit 長，而 descriptor 也不會全部都拿，只拿對自己有幫助的部份，只提供 2 bits 當作 mair 部份的參考，詳細的 `mair_el1` 暫存器資訊在 [ARMv8 手冊 p.2609](https://static.docs.arm.com/ddi0487/ca/DDI0487C_a_armv8_arm.pdf?_ga=2.109811589.1077926107.1543714027-1596023854.1506794914)

~~~ c=
/*
* Memory region attributes:
*
* n = AttrIndx[2:0]
* n MAIR
* DEVICE_nGnRnE 000 00000000
* NORMAL_NC 001 01000100
*/
#define MT_DEVICE_nGnRnE 0x0
#define MT_NORMAL_NC 0x1
#define MT_DEVICE_nGnRnE_FLAGS 0x00
#define MT_NORMAL_NC_FLAGS 0x44
~~~
* 這個代表

* 所以 `AttrIndex[2:0]` 決定了選擇哪一區段的 Attr，像程式碼 n = 001，就是選擇 Attr1
* 而 8-bit 代表的意思，則由上下兩表組成如果是01000100就是 normal memory，inner non-cacheable 和 normal memory，outer non-cacheable

* 在 mmu 打開後，每個程式都只能拿到虛擬記憶體空間，而不能拿到實體記憶體， kernel 和 user 如果不要拿到同一塊記憶體空間的話，有一種方法是每次載入 kernel 都重新載入 pgd 暫存器，但這個方法的成本很高， 會讓 cache 失效， 另一個方法是把地址分為兩部份， 3G 給 user，1G 給 kernel，另外 Armv8 有一個特殊設計， 讓 user/kernel 可以達到 address split。

* 有兩個暫存器可以儲存 pgd 的地址： `ttbr0_el1` 和 `ttbr1_el1`，前面提到，我們其實只用到 64 bits 裡的 48 bits,所以前面 16 bits 可以用來區分 ttbr0 及 ttbr1 轉換的進程，如果高位 16 bits 都為 0 則 pdg 的地址就存入 ttbr0_el1， 但如果地址起始是 0xffff 就把 pdg 的地址就存入 ttbr1_el1， 這個架構還能確保進程在 el0 上執行，決對不會動到虛擬記憶體 0xffff 開頭的內容。
* http://kib.kiev.ua/x86docs/ARMARM/DDI0487A_e_armv8_arm.pdf
* https://community.arm.com/developer/tools-software/oss-platforms/f/dev-platforms-forum/5316/issue-with-stxr-in-armv8
* https://developer.arm.com/docs/100941/latest/memory-attributes
---
### File System
* 目前能讀 FAT16 和 FAT32，因此如果將讀檔類型看作 component，進行抽換，驗證時將 sd 卡切為
* partition 1 --- FAT32
* partition 2 --- FAT16
~~~
0 +------------------+
| kernel image |
k= kernel_size |------------------|
| sd partition 1 | <- boot record
k + 0x200 |------------------|
| sd partition 2 |
k + 0x400 |------------------|
| sd partition 3 |
k + 0x600 |------------------|
| sd partition 4 |
k + 0x800 |------------------|
| |
| |
| |
| init task stack |
0x00400000 +------------------+
| |
| |
0x3F000000 +------------------+
| device registers |
0x40000000 +------------------+
~~~
https://cpl.li/2019/mbrfat/

---
### Thread
* mutex、 spinlock、 semaphore
* 藉由 pthread 瞭解執行緒
* POSIX Thread 函式庫的支援
* 函式原型及意義, 參考 [wiki](https://zh.wikipedia.org/wiki/POSIX%E7%BA%BF%E7%A8%8B)， [thispoint.com](https://thispointer.com/posix-detached-vs-joinable-threads-pthread_join-pthread_detach-examples/)
* pthread_create
~~~=c
int pthread_create ( pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void),void *arg ) ;
~~~
* 產生新的執行緒, routine 是執行緒的函式, arg 是傳給執行緒的參數, attr 用來設定執行緒一些屬性。
* 步驟：
1. Allocate a new thread structure.
2. Use the default attributes if ATTR is NULL.
3. Initialize the thread state.
* attr 如果沒設定的話，使用預設
* 指定排程優先權大小
* stack 大小
* stack 位置
* `__detachstate`: 此參數有兩個選擇，一為`PTHREAD_CREATE_DETACHED` 分離線程（結束後，線程資源直接回收，且不能同步），二為 `PTHREAD_CREATE_JOINABLE` 非分離線程（可同步，資源的回收，由線程來做）， 一旦設為分離線程，則不可改為非分離線程

* `__schedpolicy`： 標示新線程的排程方法，表示新线程的调度策略，SCHED_OTHER（正常、非即時）、SCHED_RR（即時，輪詢）和SCHED_FIFO（即時）三种，預設為SCHED_OTHER，即時的調度只有在 Kernel mode 有效
* `__schedparam`： 目前只有一個參數，`sched_priority` 預設為 0，為排程時的優先權，有定義 sched_get_priority_max 和 sched_get_priority_min 能得到系統最大和最小優先權。
* __contentionscope： 目前有兩個選項PTHREAD_SCOPE_SYSTEM （所有線程一起競爭 CPU 時間）和 PTHREAD_SCOPE_PROCESS（只與同個進程競爭裡的 CPU 時間）。
~~~c=
const struct __pthread_attr __pthread_default_attr = {
__schedparam: { sched_priority: 0 },
__stacksize: 0,
__stackaddr: NULL,
#ifdef PAGESIZE
__guardsize: PAGESIZE,
#else
__guardsize: 1,
#endif /* PAGESIZE */
__detachstate: PTHREAD_CREATE_JOINABLE,
__inheritsched: PTHREAD_EXPLICIT_SCHED,
__contentionscope: PTHREAD_SCOPE_SYSTEM,
__schedpolicy: SCHED_OTHER
};
~~~
* pthread_exit
~~~=c
void pthread_exit (void *value_ptr);
~~~
* 呼叫此函式的執執行緒停止執行,並回傳結果 value_ptr 給主執行緒 (main) 。若是主執行緒呼叫此函式,則主執行緒會等到所有的執行緒都執行結束之後才停止執行。

> value_ptr 會回傳值給 pthread_join 的第二個參數， 但大部份例子是 NULL，用途為？
>A： 其實應該先解析以下 join 的參數二

* pthread_join
~~~=c
int pthread_join ( pthread_t thread, void **value_ptr ) ;
~~~
* 第一個參數是target thread 的 ID， 第二個參數是回傳值，會 block 呼叫的執行緒直到其他執行緒結束。
* pthread_join 參數二，其實是傳入 thread_id 的狀態
~~~C=
pthread_join (pthread_t thread, void **status){
struct __pthread *pthread;
...
...
switch (pthread->state)
{
case PTHREAD_EXITED:
/* THREAD has already exited. Salvage its exit status. */
if (status != NULL)
*status = pthread->status;

__pthread_mutex_unlock (&pthread->state_lock);

__pthread_dealloc (pthread);
break;
...
...
}

return err;
}
~~~
* 而 status 分為以下四種
~~~ =C
enum pthread_state
{
/* The thread is running and joinable. */
PTHREAD_JOINABLE = 0,
/* The thread is running and detached. */
PTHREAD_DETACHED,
/* A joinable thread exited and its return code is available. */
PTHREAD_EXITED,
/* The thread structure is unallocated and available for reuse. */
PTHREAD_TERMINATED
};
~~~
* pthread_self
~~~=c
pthread_t pthread_self ( void );
~~~
* 此函式回傳執行緒的 ID 。

* pthread_equal： 不需用到 system call
~~~=c
int pthread_equal ( pthread_t t1, pthread_t t2 );
~~~
* 比較 t1 與 t2 這兩個執行緒的 Handler 是否相同。
* thread_yield ( void );
呼叫此函式的執行緒暫時放棄 CPU 執行權。
* int pthread_detach ( pthread_t thread , **value_ptr );
此函式將執行緒狀態設為無法被等待執行結束 (Non-joinable) 。之後若此執行緒
執行結束, value_ptr 可用來存放執行緒的回傳值。
* int pthread_attr_init ( pthread_attr_t *attr );
初始化執行緒屬性資料為預設值。
int pthread_attr_destroy ( pthread_attr_t *attr );
刪除執行緒屬性資料。

* int pthread_attr_setdetachstate ( pthread_attr_t *attr, int detachstate );
依照 detachstate 的值來設定執行緒屬性 attr 是否被設定為可被等待執行結束
(Joinable) 或不可被等待執行結束 (Non-Joinable) 。
* int pthread_attr_getdetachstate ( const pthread_attr_t *attr, int *detachstate );
得到執行緒屬性資料中是否可被等待執行結束 (Joinable) 的值。
int pthread_attr_getstackaddr ( const pthread_attr_t *attr, void **stackaddr );
得到執行緒堆疊的位址。
int pthread_attr_getstacksize ( const pthread_attr_t *attr, size_t *stacksize );
得到執行緒堆疊大小。

---
#### 為了達到 lock 的目的，本文在 Armv8 系統上使用 [exclusive instruction](https://hackmd.io/s/Hkevs5bh4),為求版面乾淨，相關介紹放置連結中
* int pthread_mutex_init ( pthread_mutex_t *mutex, pthread_mutexattr_t *attr );
使用屬性 attr 來初始化 mutex 。
* int pthread_mutex_destroy ( pthread_mutex_t *mutex );
刪除 mutex 。

- [x] thread_mutex_trylock
~~~=c
int pthread_mutex_trylock ( pthread_mutex_t *mutex );
~~~
* 測試 mutex 是否能夠上鎖,若不能則回傳錯誤值,可以用在執行緒不能被停頓(Block) 的情形。
* 這裡使用 ARMv8 的 exclusive 操作，且參考[讀寫 lock](http://www.lujun.org.cn/?p=4097)，而重寫了一份， w4 放置回傳值，0 為成功，1 為失敗
~~~ c=
.globl try_lock
1:
mov w4, #1
mov w0, w4
ret
try_lock: /*w3 w4 tmp*/
ldaxr w3, [x0] /*x0:lock*/
cbnz w3, 1b
add w3, w3, #1
stxr w4, w3, [x0]
cbnz w4, 1b
mov w0, w4
ret
~~~

* thread_mutex_lock
~~~c=
int pthread_mutex_lock ( pthread_mutex_t *mutex );
~~~
* 將 mutex 上鎖,若上鎖不成功則該執行緒會停頓 (Block) 。

~~~
enum __pthread_mutex_type
{
__PTHREAD_MUTEX_NORMAL,
__PTHREAD_MUTEX_ERRORCHECK,
__PTHREAD_MUTEX_RECURSIVE
};

~~~
* 註： [mutex](htts://www.itread01.com/content/1549861589.html) 屬性差別

- [x] int pthread_mutex_unlock ( pthread_mutex_t *mutex );
解除 mutex 的上鎖狀態。
* 這邊的設計，雖然說是參考 pthread，但因為目前只有單核心，所以不會真的在 loop 裡，等到解鎖完成，而是直接進排程來表示此次失敗（假設一種情況是目前 exclusive 暫存器狀態無法 stlxr），等下次再輪回來時，再試。
~~~C=

.globl unlock
loop: bl schedule
unlock: /*w3 w4 tmp*/
ldxr w3, [x0]
cbz w3, error_unlock
sub w3, w3, #1
stlxr w4, w3, [x0]
cbnz w4, loop
mov w0, w4
ret

.globl error_unlock
error_unlock:
mov w0, #1
ret
~~~

* int pthread_mutexattr_init ( pthread_mutexattr_t *attr );
初始化關連到 mutex 的屬性 attr 。
* int pthread_mutexattr_destroy ( pthread_mutexattr_t *attr );
刪除關連到 mutex 的屬性 attr 。
---
* int pthread_cond_init ( pthread_cond_t *condition, pthread_condattr_t *attr );
使用條件變數屬性 attr 來初始化條件變數 (condition variable) 。
int pthread_cond_destroy ( pthread_cond_t *condition );
刪除修件變數。

* int pthread_cond_signal ( pthread_cond_t *condition );
叫醒停頓 (Block) 在該條件變數的執行緒中的一個。
* int pthread_cond_broadcast ( pthread_cond_t *condition );
叫醒所有停頓 (Block) 在該條件變數的執行緒。
* int pthread_cond_wait ( pthread_cond_t *cond, pthread_mutex_t * mutex);
呼叫此函式的執行緒會停頓 (Block) 在該條件變數中,如果 mutex 已經被該執行緒上鎖,則 mutex 會自動解除。
* int pthread_cond_timewait ( pthread_cond_t *cond, pthread_mutex_t *mutex, const
struct timespec *abstime );
呼叫此函式的執行緒會停頓 (Block) 在該條件變數中,且己經上鎖的 mutex 會被解除。但此執行緒停頓 (Block) 有時間限制,當經過了由 abstime 所設定的時間之後,該執行緒會繼續執行,並且會重新上鎖 mutex 。
* int pthread_condattr_init ( pthread_condattr_t *attr );
初始化關連到條件變數的屬性 attr 。
* int pthread_condattr_destroy ( pthread_condattr_t *attr );
刪除關連到條件變數的屬性 attr 。
---
~~~c =
int _pthread_spin_lock (__pthread_spinlock_t *lock)
{
int i;

while (1)
{
for (i = 0; i < __pthread_spin_count; i++)
{
if (__pthread_spin_trylock (lock) == 0)
return 0;
}

__sched_yield ();
}
}
~~~

---
### process manager deamon
* 傳遞信息
* 結束行程
---

### IPC
* kernel mode 間傳遞訊息
* user mode 要和 kernel 溝通， 叫 request
* thread 和 thread 之間傳遞訊息
* user process 要求 service
（先作Rendezvous，TCB新增STATE和）

[mailbox](http://cs.lmu.edu/~ray/note/messagepassing/)

---
### ELF 解析
* [ELF 解析](https://hackmd.io/s/H1G5-o83N)裡是額外寫的一篇，由於本系統在運作後,能支援以下兩件事，因此也必須了解裡頭的配置:
* 載入新的應用程式（user application）時， 此使用的格式為 excutable ELF 檔。
* 動態的載入新的 components（新的服務），使用的是 relocatable ELF，測試機器碼(object code)這部份放置[載入,連結與重配置](https://hackmd.io/s/SkwnZNp2N)中。
* 目標是學習 [Implementing Loadable Kernel Modules for Linux](http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/DDJ/1995/9505/9505a/9505a.htm) 這份 Journal， 並實做出能動態載入的 component
* components 能使用之系統內函式,須將這些函式存入 symbol table
~~~
.text 0xffff000000006590 0x3c8 build/kernel/sys_c.o
0xffff000000006590 kernel_sevice_write
0xffff0000000065b0 kernel_sevice_fork
0xffff0000000065d4 kernel_sevice_exit
0xffff0000000065ec kernel_sevice_led_blink
0xffff000000006604 kernel_sevice_read
0xffff00000000661c kernel_sevice_create_thread
0xffff000000006650 kernel_sevice_thread_self
0xffff000000006664 kernel_sevice_thread_join
0xffff00000000668c kernel_sevice_thread_exit
0xffff0000000066a0 kernel_sevice_thread_signal
0xffff0000000066c0 kernel_sevice_list_file
0xffff0000000066d8 kernel_sevice_cd_folder
0xffff0000000066f8 kernel_sevice_dump_file
0xffff000000006718 kernel_sevice_root_file
0xffff000000006734 kernel_sevice_com_file
0xffff000000006754 kernel_sevice_run_file
0xffff000000006774 kernel_sevice_mutex_trylock
0xffff000000006794 kernel_sevice_mutex_lock
0xffff0000000067b4 kernel_sevice_mutex_unlock
0xffff0000000067d4 kernel_sevice_allocate_page
0xffff0000000067e8 kernel_sevice_free_page
0xffff000000006808 kernel_sevice_send_msg
0xffff000000006920 kernel_sevice_recieve_msg
~~~
* 對照 symbol table 及 page 去往回填入機器碼，步驟就跟 [載入,連結與重配置](https://hackmd.io/s/SkwnZNp2N)一樣。只是將他變成一個 relocation 的函式,有固定流程。
~~~c=
int get_ndx(Elf64_Sym* sym){
return sym->st_shndx;

}

int get_strname(Elf64_Sym* sym){
return sym->st_name;

}

void relocate(char* comp_start,unsigned long section_table_start,unsigned long section_size,char* base,Elf64_Rela* rela,unsigned long size){
for(int init=0; init < size/24 ;init++){

if((unsigned int)(rela+init)->r_info==0x113){}
else if((unsigned int)(rela+init)->r_info == 0x115){

int ndx = get_ndx(base + move_sec[5].addr + 24*((rela+init)->r_info >> 32));
int rel_num = find_sec_addr(base + section_table_start + ndx*(section_size));
unsigned int* ch_test = (comp_start + (rela+init)->r_offset);

if(rel_num == 1){ /*rodata*/
*ch_test = (((move_sec[0].size + (rela+init)->r_addend)*4)<<8) + (0x91000000);

}else if(rel_num==2){ /*data*/
*ch_test = (((move_sec[0].size + move_sec[1].size + (rela+init)->r_addend)*4)<<8)+(0x91000000);
}else if(rel_num==3){ /*bss*/
*ch_test = (((move_sec[0].size + move_sec[1].size + move_sec[2].size + (rela+init)->r_addend)*4)<<8)+(0x91000000);
}else{
printf("Not data section!");
}
}else if((unsigned int)(rela+init)->r_info==0x11b){
int ndx = get_ndx(base + move_sec[5].addr + 24*((rela+init)->r_info >> 32));
if(ndx==0){
int strname = get_strname(base + move_sec[5].addr + 24*((rela+init)->r_info >> 32));
char str_name[30]={'\0'};
int i = 0,ksym_i = 0,flag =0;

char* chara =base + move_sec[6].addr+ (int)strname;
while(*(chara+i)!='\0'){
str_name[i] = *(chara+i);
i++;
}

while(ksym[ksym_i].sym_name[0]!='\0')
if(!memcmp(&ksym[ksym_i++] , &str_name[0] ,i-1)){flag = 1; break;}

if(flag==1){
unsigned int value = 0x3ffffff -((((int)comp_start + (rela+init)->r_offset) - ksym[ksym_i-1].sym_addr)/4)+1;
unsigned int* bl_test = (comp_start + (rela+init)->r_offset);
*bl_test = value + 0x94000000;
}else{
printf("Not componets support this function: %s",str_name);
}

}else{

printf("To do list\n\r");
}
}

}

}
~~~
* `ksym.o` 如果掛載已存在 symbol 會拒絕此註冊。
~~~c=
void init_compt(void){ /*initial*/
kservice_uart_write("Initial component!\n\r");
kservice_reg_compt("recieve_msg");
}

void oper_compt(unsigned long gpio,int on_off){ /*operation*/
kservice_uart_write("Operation!\n\r");
/*
put32(GPPUD,on_off);
delay(150);
put32(GPPUDCLK0,(1<<gpio));
delay(150);
put32(GPPUDCLK0,0);
*/
}

void exit_compt(void){ /*exit*/
kservice_unreg_compt("recieve_msg");
kservice_uart_write("Clean up GPIO component!\n\r");
}
~~~

* 掛載 `incom` / 卸載 `rmcom`

---

### ASM 指令
* `msr`： Load value from a system register to one of the general purpose registers (x0–x30)
* `and`： Perform the logical AND operation. We use this command to strip the last byte from the value we obtain from the `mpidr_el1` register.
* `cbz`: Compare the result of the previously executed operation to 0 and jump (or branch in ARM terminology) to the provided label if the comparison yields true.
* `b`: Perform an unconditional branch to some label.
* `adr`: Load a label's relative address into the target register. In this case, we want pointers to the start and end of the .bss region.
* `sub`: Subtract values from two registers.
* `bl`: (Branch with a link) perform an unconditional branch and store the return address in x30 (the link register). When the subroutine is finished, use the ret instruction to jump back to the return address.
* `mov`: Move a value between registers or from a constant to a register.
* `blr`: Branch with link to register, calls a subroutine at an address in a register, setting register 30 to pc + 4
* `lsl`: Logical shift left (register).
* 尋址格式， 參考[刘坤的技术博客](https://blog.cnbluebox.com/blog/2017/07/24/arm64-start/)
* `[x10, #0x10]`: signed offset 從 x10 + 0x10的地址取值
* `[sp, #-16]!`: pre-index 從 sp-16 地址取值，取值完後在把 sp-16 寫回 sp
* `[sp], #16`: post-index 從 sp 地址取值，取值完後在把 sp+16 寫回 sp

---
### 未解決問題
* 多少 resource（額外檔案），config file
(https://www.raspberrypi.org/forums/viewtopic.php?t=202861)
* CPU 和 GPU 溝通用 mailbox

affinity

MPIDR
image 大小
CACHE LINE

PAGE size 4096 的根據？

* linux 的 module 能使用其他 module 嗎

### 參考文件
* [Learning operating system development using Linux kernel and Raspberry Pi](https://github.com/s-matyukevich/raspberry-pi-os)
* [Bare Metal Programming on Raspberry Pi 3](https://github.com/bztsrc/raspi3-tutorial)
* [processor](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0500g/BABHBJCI.html)

* [function CALL](https://community.arm.com/processors/b/blog/posts/how-to-call-a-function-from-arm-assembler)
* [interrupt](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.den0024a/ch10s05.html)

* http://dec.0123456789.tw/

* https://www.datadoctor.biz/data_recovery_programming_book_chapter3-page19.html

* http://lexra.pixnet.net/blog/post/303910876-%EF%BF%AD-master-boot-record-(mbr)-%E4%BB%A5%E5%8F%8A-fat32-%E8%A7%A3%E6%9E%90
* [interrupt](
http://coopermaa2nd.blogspot.com/2011/04/3-interrupts.html)

* libary

## 筆記
* active UML
* swap 流程
* HONOI stack TEST
* CRT0
* 初始化狀態圖
* [UML](https://studentcodebank.wordpress.com/2017/11/21/uml-%E6%B4%BB%E5%8B%95%E5%9C%96%E8%A1%A8-activity-diagram/)
* [Microsoft](https://support.office.com/zh-tw/article/%E5%BB%BA%E7%AB%8B%E5%9F%BA%E6%9C%AC%E6%B5%81%E7%A8%8B%E5%9C%96-e207d975-4a51-4bfa-a356-eeec314bd276)
* [2個結束點](https://www.uml-diagrams.org/google-sign-on-uml-activity-diagram-example.html)
* [時序圖](http://www.woshipm.com/ucd/607593.html)