# 從硬體切入的嵌入式系統開發
Contributed by <[`rota1001`](https://github.com/rota1001)>
> [Github](https://github.com/rota1001/arm-os-101)

為了了解一個作業系統是如何在開發板上運行的，我決定去復現 Linux 核心專題 [Running Linux 6.14 on stm32f429](https://hackmd.io/@yawu/HkZ2pm22yx)。原訂計畫是這樣的，但是做了一陣子發現他的 flash 只有 128KB，sram 只有 20KB，這很明顯就沒辦法跑一個 linux 在上面。於是，後面直接鬼轉嵌入式系統開發。

## STM32f103c8t6

參考 STM32f103xx 的 [Reference Manual](https://www.st.com/resource/en/reference_manual/rm0008-stm32f101xx-stm32f102xx-stm32f103xx-stm32f105xx-and-stm32f107xx-advanced-armbased-32bit-mcus-stmicroelectronics.pdf)

### STM32 的引導模式設定
在第 60 頁可以看到，設定 BOOT1 與 BOOT0 可以決定啟動的模式，如果 BOOT0 被設為 0 的話，那麼系統會從 flash 啟動

### 記憶體配置
在第 54 頁可以看到，flash 的起始位置是 0x08000000

在第 53 頁可以看到，SRAM 的開頭是 0x20000000：
> The STM32F10xxx features up to 96 Kbytes of static SRAM. It can be accessed as bytes,
half-words (16 bits) or full words (32 bits). The SRAM start address is 0x2000 0000.

根據第 61 頁可以看到，如果使用 flash 啟動的話，那麼它會從 0x08000000 獲得初始的 stack 位置，從 0x08000004 獲得要從哪裡開始執行程式：
> The BOOT pins are also re-sampled when exiting from Standby mode. Consequently they must be kept in the required Boot mode configuration in Standby mode. After this startup delay has elapsed, the CPU fetches the top-of-stack value from address 0x0000 0000, then starts code execution from the boot memory starting from 0x0000 0004

## 撰寫第一個程式

首先是安裝 stlink 工具：

$ cd ~
$ git clone https://github.com/stlink-org/stlink
$ cd stlink
$ sudo apt-get install -y cmake libusb-1.0-0-dev
$ sudo apt-get -y install cmake
$ sudo apt-get install libstlink1
$ make
$ cd build/Release
$ sudo make install

這個時候把 stlink 的對應腳位接上開發板，將它插入電腦，並且執行下列命令確定它有被讀取到：

$ st-info --probe
Found 1 stlink programmers
  version:    V2J46S7
  serial:     37FF71064E573436899E1043
  flash:      131072 (pagesize: 1024)
  sram:       20480
  chipid:     0x410
  dev-type:   STM32F1xx_MD

接下來參考 [嵌入式系統建構：開發運作於STM32的韌體程式](https://docs.google.com/document/d/1Ygl6cEGPXUffhTJE0K6B8zEtGmIuIdCjlZBkFlijUaE/edit?tab=t.0) 去開發一個小程式，只是要針對 stm32f103 去做一些小修改。

首先我們先去控制一下在開發板上的 LED，發現它可以藉由 GPIOC13（PC13） 去控制。

在 [Reference Manual](https://www.st.com/resource/en/reference_manual/rm0008-stm32f101xx-stm32f102xx-stm32f103xx-stm32f105xx-and-stm32f107xx-advanced-armbased-32bit-mcus-stmicroelectronics.pdf) 的第 51 頁可以看到控制 GPIO Port C 的暫存器是放在 0x40011000 為開頭的地方：

在 [Reference Manual](https://www.st.com/resource/en/reference_manual/rm0008-stm32f101xx-stm32f102xx-stm32f103xx-stm32f105xx-and-stm32f107xx-advanced-armbased-32bit-mcus-stmicroelectronics.pdf) 的第 173 頁可以看到 output register 是在偏移量 0x0C 的位置，也就是說以 GPIOC 來說就是 0x4001100C：

在 [Reference Manual](https://www.st.com/resource/en/reference_manual/rm0008-stm32f101xx-stm32f102xx-stm32f103xx-stm32f105xx-and-stm32f107xx-advanced-armbased-32bit-mcus-stmicroelectronics.pdf) 的第 172 頁可以看到 GPIOC 的 CRH 設定，也就是比較高位的 16 個針腳的設定。MODE 可以設定一個針腳是 input mode 還是 output mode，00 代表 input mode，其他的代表不同速度的 output mode。CNF 代表的是 data register 會如何影響 pin 腳的電位，這裡去翻閱了一下 [General Purpose Input/Output (GPIO) 教材](https://wiki.csie.ncku.edu.tw/embedded/GPIO)。以 input 來說，Analog mod（00）代表的是不經過 Schmitt trigger，也就是輸出的是類比的訊號。Floating input（11）代表是高阻抗狀態，也就是在沒有外部訊號的情況下他的電位是無法確定的。pull-up / push-down（10）代表的是在沒有外部訊號的情況下，他有特定電位（pull-up 是 1、push-down 是 0）。以 output 來說，push-pull（00）代表的是由 output register 決定電位。Open-drain（01）代表如果 output register 是 0 意味著低電位，而 output register 是 1 意味著高阻抗。應用場景像是如果很多個輸出針腳被接在同一個 bus 上面的時候，希望由其中一個 pin 腳來決定一整個 bus 的電位，那麼可以把其他針腳都調到 Open-drain 模式下，並且 output register 設為 1，那一個針腳調為 push-pull 模式，這樣他的 output register 的值就會直接的影響到 bus　的電位。另外兩個模式是 Alternate function，表示要使用這個腳位除了 GPIO 以外的特定功能，像是 USART。那以我們這裡的使用情境來說，要調成 General purpose output push-pull 的狀態，所以設為 00，至於 MODE 就跟著教材設為速度 10 MHz 的輸出狀態。

另外要開啟 GPIOC 的時鐘，也就是 RCC_APB2ENR_IOPCEN。

這裡照著教材寫了一段簡單的[程式碼](https://gist.github.com/rota1001/35a07e015028897434152465d72aff20)，使用 `make` 進行編譯，並且使用 `make flash` 進行燒錄（這裡使用 stlink 進行燒錄），然後就會看到藍色的 LED 燈在閃爍（要把 BOOT0 調成 0）。

### isr_vector
在 [The Definitive Guide To ARM Cortex M3](https://tinymicros.com/mediawiki/images/7/75/Definitive_Guide_To_The_ARM_Cortex_M3.pdf) 的第 123 頁中可以看到，flash 的開頭是一個 isr_vector，裡面偏移量是 0 的地方放的是 MSP，偏移量是 4 的地方放的是一開始會跳到的地址。

### 記憶體配置
前面的程式碼中用了相對簡單的記憶體配置，只有將 .text 區段映射進來。接下來會寫一個 linker script 來將其他各種區段映射進來。
首先是用 MEMORY 可以依照記憶體的基址與大小來宣告記憶體（flash 寫成 0x08000000 也可以）：

MEMORY {
    FLASH (rx) : ORIGIN = 0x00000000, LENGTH = 32k
    SRAM (rwx) : ORIGIN = 0x20000000, LENGTH = 20k
}

接下來是將 `.text`、`.data`、`.bss` 映射進來，如果是在 flash 裡的話，會被寫在 flash 裡面，如果是在 sram 裡的話，在跑的時候會在 sram 裡有對應的區段，但是他的內容沒有做設定的話不會初始化。如果像是 .data 區段需要初始化的話，會使用 AT 設定 LMA（Load Memory Address），讓他在 flash 中被儲存，在跑起來的時候手動去將它複製到 sram 裡面。

    . = 0x0;
    .text : {
        KEEP(*(.isr_vector))
        *(.text)
        *(.rodata)
        . = ALIGN(4);
        _etext = .;
    } > FLASH

    .data : AT (_etext) {
        _data = .;
        *(.data)
        . = ALIGN(4);
        _edata = .;
    } > SRAM
    
    .bss (NOLOAD) : {
        _bss = .;
        *(.bss)
        . = ALIGN(4);
        _ebss = .;
    } > SRAM

    _end = .;
}

這裡驗證一下如果沒有手動複製 .data 段的資料的話在 sram 中的資料不會初始化，首先將程式改成這樣，在 `reset_isr` 裡面呼叫 `main`，並且宣告全域變數 `int x = 0xdeadbeef`，在 `main` 裡判斷它是否為 `0xdeadbeef`：

int x = 0xdeadbeef;

int main()
{
    unsigned c = 0;
    RCC_APB2ENR = (1 << 4); /* IOPCEN = 1 */
    GPIOC_CRH = 0x44144444;

    if (x != 0xdeadbeef)
        while (1);

    while (1) {
        GPIOC_ODR |= (1UL << 13);
        for (c = 0; c < 500000; c++);
        GPIOC_ODR &= ~(1UL << 13);
        for (c = 0; c < 500000; c++);
    }
}

void reset_isr()
{
    main();
    while(1);
}

去執行後，發現 LED 燈變成恆亮的狀態，代表它陷入無窮迴圈了。接下來將 `x` 宣告成區域變數，就是在 stack 上的狀態：

- int x = 0xdeadbeef;
...
+   int x = 0xdeadbeef;
    if (x != 0xdeadbeef)
        while (1);

會發現它開始閃爍了。

接下來同樣是宣告全域變數 `int x = 0xdeadbeef`，只是手動從 flash 中複製 .data 區段到 sram 中的對應空間：

void reset_isr()
{
+    unsigned long *src = &_etext, *dst = &_data;
+    while (dst != &_edata)
+        *dst++ = *src++;
    main();
    while(1);
}

會發現 LED 燈右開始閃了，代表全域變數有順利的被初始化。接下來補上一下 .bss 區段的初始化，這裡就告一段落了。

### 在 sram 中執行 main 函式
先將指令移動到 sram 的好處第一個是比較快，第二個是執行程式碼的時候比較有靈活性，因為 flash 是唯讀的，記憶體分配需要在程式設計時進行設定。相對的，sram 可以在運行時間進行記憶體分配。
對 linker script 做一些修改，將 .text 區段搬到 SRAM 裡面，並且新增一個 .isr_vector 區段，放的是 `isr_vector` 與 `reset_isr`，這兩個東西是會放在 flash 裡面的：

    .isr_vector : {
        KEEP(*(.isr_vector))
        KEEP(*(.reset))
    } > FLASH
    . = ALIGN(4);
    _text_lma = .;
    .text : AT (_text_lma) {
        _text = .;
        *(.text)
        *(.rodata)
        . = ALIGN(4);
        _etext = .;
    } > SRAM

在 `reset_isr` 與 `isr_vector` 上面要加上 `attribute` 來描述他在哪個區段中。並且，在 `reset_isr` 裡面要把 .text 區段從 flash 複製到 sram 裡面，最後再呼叫 `main`。

__attribute__((section(".reset")))
void reset_isr()
{
    unsigned long *src = &_text_lma, *dst = &_text;
    while (dst != &_etext)
        *dst++ = *src++;

    dst = &_data;
    while (dst != &_edata)
        *dst++ = *src++;

    dst = &_bss;
    while (dst != &_ebss)
        *dst++ = 0;

    main();
    while(1);
}

### 使用 gdb 進行除錯
stlink 有提供 gdb server，使用 `st-util` 可以開啟它：

$ st-util
st-util 1.8.0-117-gdb953ea
2025-07-20T07:09:22 INFO common_legacy.c: NRST is not connected --> using software reset via AIRCR
2025-07-20T07:09:22 INFO common_legacy.c: STM32F1xx_MD: 20 KiB SRAM, 128 KiB flash in at least 1 KiB pages.
2025-07-20T07:09:22 INFO gdb-server.c: Listening at *:4242...

這個時候，他在 `localhost:4242` 啟動了一個 gdb server，這個時候使用 gdb-multiarch 去連上它（使用 `target remote :4242` 命令）：

LEGEND: STACK | HEAP | CODE | DATA | WX | RODATA
──────────────────────[ REGISTERS / show-flags off / show-compact-regs off ]──────────────────────
 R0   0x6c
 R1   0x20000114
...
─────────────────────────[ DISASM / armcm / thumb mode / set emulate on ]─────────────────────────
 ► 0x200000ac    ldr    r3, [pc, #0x18]     R3, [0x200000c8]
   0x200000ae    ldr    r3, [r3]            R3,
  ...
────────────────────────────────────────────[ STACK ]─────────────────────────────────────────────
00:0000│ r7 sp 0x20000fc0
01:0004│       0x20000fc4
...
──────────────────────────────────────────[ BACKTRACE ]───────────────────────────────────────────
 ► 0 0x200000ac None
   1 0x200000f6 None
──────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg> 

成功連上了，我有使用 pwndbg 這個插件，看起來的形狀會和原生 gdb 不太一樣。如果編譯時有加 `-g` 參數保留 symbol 的話，可以使用 `file` 命令去獲得 symbol，甚至可以看到原始碼：

─────────────────────────────────[ SOURCE (CODE) ]─────────────────────────────────
In file: /home/rota1001/linux2025/stm32/test/main.c:21
   16     if (x != 0xdeadbeef)
   17         while (1);
   18 
   19     while (1) {
   20         GPIOC_ODR |= (1UL << 13);
 ► 21         for (c = 0; c < 500000; c++);
   22         GPIOC_ODR &= ~(1UL << 13);
   23         for (c = 0; c < 500000; c++);
   24     }
   25 }
   26

### USART 序列通訊
#### 輸出訊息
這裡要使用 USART1 去進行序列通訊，可以看到 TX 與 RX 分別對應到的是 PA9 與 PA10，TX 是發送端，RX 是接收端。
如果要連接電腦，必須準備一個 USB to serial 的模組，重要的針腳有 GND、TXD、RXD 三個。GND 接地，TXD 是它的發送端，要接到 stm32 的 RX，RXD 是它的接收端，要接到 stm32 的 TX。

TX 是輸出端，所以 MODE 要調成輸出的模式，這裡是用 `11`，而 CNF 要調成 Alternate push-pull（`10`）。RX 是接收端，MODE 要調成 `00`，CNF 調成 `01`。

因為他是 PAx，我們用到了他的 GPIO 與 Alternate function，還有用到 USART1，他們的時鐘都要被開啟，分別在 `RCC_APB2ENR` 的 `AFIOEN`、`IOPAEN`、`USART1EN` 這三個地方可以設定。

接下來是設定 baud rate，要設定成 9600 bps。而我們能做的事情是利用 `USART_BRR` 去設定 USARTDIV，以下看看怎麼換算的。其中用到了一個參數 $f_{CK}$，在 USART1 他是 PCLK2，在 USART2 到 USART5 是 PCLK1。PCLK2 可以由 HCLK 經過 APB2 分頻器獲得，HCLK 可以由系統時鐘經過 AHB 分頻器獲得，而 AHB 與 APB2 這兩個分頻器預設的情況下分頻的倍率是 1，所以一開始的 $f_{CK}$ 是和系統時鐘一樣的。（至於如何控制時鐘，在後面會做討論）

接下來看一下它的系統時鐘頻率是多少。在 Reference Manual 的 7.2 可以看到，stm32f103 的系統時鐘可以基於三種東西，HSI、HSE 與 PLL。在 7.2.6 可以看到，HSI 被選為預設的時鐘：
> After a system reset, the HSI oscillator is selected as system clock.

在 7.2.2 可以看到，HSI 的頻率是 8 MHz，所以可以知道預設的 $f_{CK}$ 是 8 MHz：
> The HSI clock signal is generated from an internal 8 MHz RC Oscillator and can be used
directly as a system clock or divided by 2 to be used as PLL input.

在 Reference Manual 的 27.3.4 有敘述 baud rate 的換算公式：
$$\text{baud}=\frac{f_{CK}}{16\times\text{USARTDIV}}$$

所以可以計算一下：
$$\text{USARTDIV}=\frac{8\times 10^6}{16\times9600}=52.083$$
而它會以 `USART_BRR` 會以二進位制保留 8 位數字與 4 位小數點。52 是 0x34，而 0.083 約等於 0b0.00010，所以小數點是 0x1，所以 `USART_BRR` 要設定為 0x341。

接下來要設定 `USART_CR1`，有以下幾個東西要設定：
- UE：USART enable，表示啟用 USART
- TE：Transmitter enable

接下來可以由 `USART_SR` 的 TXE 去判斷傳過去的字元是否被讀取了，如果已經被讀取的話那個位元會變成 1，這個時候就能送下一個字元了：

void USART1_sendchar(char c) {
    while (!(USART1_SR & USART_SR_TXE));
    USART1_DR = c;
}

完整程式碼在[這裡](https://gist.github.com/rota1001/9df87342272d3c59dc52626019967207)。

接下來試試看輸出 hello 到電腦上，這裡先使用 minicom 去進行操作。首先把 usb to serial 模組插入，這個時候用 dmesg 去看應該要看到以下類似的訊息：

[163244.941558] usb 3-3.1: new full-speed USB device number 103 using xhci_hcd
[163245.081810] usb 3-3.1: New USB device found, idVendor=1a86, idProduct=7523, bcdDevice= 2.64
[163245.081835] usb 3-3.1: New USB device strings: Mfr=0, Product=2, SerialNumber=0
[163245.081843] usb 3-3.1: Product: USB Serial
[163245.090706] ch341 3-3.1:1.0: ch341-uart converter detected
[163245.091941] usb 3-3.1: ch341-uart converter now attached to ttyUSB0

然後可以在 `/dev` 目錄下看到對應的檔案：

$ file /dev/ttyUSB0
/dev/ttyUSB0: character special (188/0)

接下來用 cat 命令，會發現訊息被印出來了：

sudo cat /dev/ttyUSB0
Hello
Hello
Hello
Hello
Hello
Hello

#### 輸入訊息
多設定 `USART_CR1_RE` 這個位元，然後透過 `USART_SR_RXNE` 去判斷是否有字元傳過來，這樣可以做到一個阻塞式的輸入：

char USART1_getchar() {
    while (!(USART1_SR & USART_SR_RXNE));
    char c = USART1_DR;;
    return c;
}

接下來在 `main` 裡面實作一個用 `getchar` 輸入，並用 `sendchar` 輸出的程式，然後使用 minicom 之類的東西就可以和它互動：

while(1) {
    char c = USART1_getchar();
    USART1_sendchar(c);
}

接下來用 C 語言寫一個程式來和開發板做互動，完整程式碼在 [gist](https://gist.github.com/rota1001/3bdf3f46a87f9b5e0675df8ece7d9f94) 上，以下摘錄重點。
通過 termios 將 stdin 變成 raw mode。具體來說將 `ICANON` 關閉可以讓透過 stdin 輸入的東西不會以一行一行為單位，關閉 `ECHO` 可以讓透過 stdin 輸入的東西不會同時輸出到 stdout。

new_tty.c_lflag &= ~(ICANON | ECHO);
if (tcsetattr(STDIN_FILENO, TCSANOW, &new_tty)) {
    perror("tcsetattr");
    close(fd);
    return 1;
}

然後我讓它一直接收字元，直到接收到 `q`。對 `/dev/ttyUSB1` 去進行讀寫，並將讀取的內容印出來：

char c;
while ((c = getchar()) != 'q') {
    write(fd, &c, 1);
    int n = read(fd, &c, 1);
    if (n > 0)
        putchar(c);
}

另外這裡同樣能對 `/dev/ttyUSB1` 透過 termios 進行設定，譬如設定 baud rate 之類的，但是這裡因為我沒有設定一樣能運作，就沒有特別設定了。

### SPI
這是一種主從式的串行通訊，有 4 根腳（不一定全部會用到）：
- SS：選擇線
- MISO：從 slave 傳給 master 的針腳
- MOSI：從 master 傳給 slave 的針腳
- SCK：通訊用的時鐘

如果只要從 master 傳訊息給 slave 的話，那只要接 MOSI 就好了，因為前鎮子獲得了使用邏輯分析儀的技能，讓我們來看看它傳訊息時這些針腳的電位：
這是在傳送 0xde 這個位元組過去，在 SCK 的每個週期中，MOSI 會表示一個位元，從高位開始傳送，結果是 110011110，剛好是 0xde 的二進位制表示。
## arm-os-101
到這裡，終於可以開始寫作業系統了。目前對於這個作業系統要達成什麼目標還沒什麼想法，不過我想，在這個過程中應該會出現挑戰，那麼目標自然就會出現了。然後在系統開發初期所有的輸入輸出都是阻塞式的。在未來實作出排程器之後，會新增中斷處理來進行改善。
### boot
和前面做的事情的基本上差不多，定義好 stack 頂端、`reset_isr` 作為進入點，並且將 .text 與 .data 區段初始化，然後進入 `kernel_main`，就可以開始做其他事情了。
> commit [a386e9f](https://github.com/rota1001/arm-os-101/commit/a386e9f530da11195a5786bc0836157dedfae7f3)

### 輸入輸出
同樣使用 USART1 做輸出，實作出 `putchar` 與 `getchar` 之後，可以在這個基礎上實作出其他函式。`printf` 我目前只有實作出部份的 format 處理。另外，我去實作了 `PANIC` 巨集，然後讓它輸出除錯訊息，並且會讓 LED 燈不斷閃爍：

#define PANIC(fmt, ...)            \
    do {                   \
        printf("\n=== KERNEL PANIC ===\n"); \
        printf(fmt "\nLocation: %s:%d\n", ##__VA_ARGS__, __FILE__, __LINE__); \
        debug_shine_led(); \
    } while (0)

其他部份沒什麼好講的就跳過：
> commit [a55e046](https://github.com/rota1001/arm-os-101/commit/a55e046961753c09c4d3bac5bbe72ac7cd617b06)
### 偵測 usb-to-serial 模組是否有插進電腦
現階段我沒有螢幕，是透過 USART 去與我的筆電做通訊，如果我有個使用者程式，我要有一個方式去偵測我的筆電是否已經把 `/dev/USBtty0` 打開了。首先想到的方式是利用 usb-to-serial 的 5V 針腳來判斷 usb-to-serial 模組是否有插進電腦裡，然而這樣沒辦法判斷我是否已經把 `/dev/USBtty0` 打開了，經過一些研究後，我發現這件事情只靠我目前手上有的這個 usb-to-serial 模組做不到。於是，我想這件事也不是那麼迫切需要解決。首先，未來這個裝置會有一個螢幕，不會有插進去後實際上還沒有啟動客戶端的問題，另外，如果真的需要用這樣的方式去與筆電做互動的話，那我可以設計一個在筆電上運行的客戶端，並且與這個作業系統約定一種傳遞狀態的方式，這是一個純軟體的解決方案。所以，目前先預設如果有把 USB 插進電腦，就可以開使用 USART 進行通訊了。

前面說到，我透過 5V 去判斷 USB 是否有成功的被插進去，然而 5V 對於某些針腳來說太高了，所以使用了一些電阻去進行降壓：

5V -- 1kΩ -- + -- 2kΩ -- GND
             |
            GPIO

這樣能把電位降到大約 3.3V，並且把 GPIO 調成 input with pull-down 模式，就可以這樣判斷是否有插入了。接下來設計一個測試程式，讓它成功偵測 USB 插入的時候就亮 LED 燈，沒有插入就關燈（當然之前是都用 3 用電錶測過了）：

/* PB12 input with pull-down*/
RCC_APB2ENR |= RCC_APB2ENR_IOPBEN;
GPIOB_CRH &= ~(0xF << 16);
GPIOB_CRH |=  GPIO_CONF(GPIO_CNF_INPUT_PUSH_PULL, GPIO_MODE_INPUT) << 16;
GPIOB_ODR &= ~(1 << 12);

RCC_APB2ENR |= RCC_APB2ENR_IOPCEN;
GPIOC_CRH = 0x44144444;
USART1_init();
while (1) {
    if ((GPIOB_IDR >> 12) & 1) {
        GPIOC_ODR &= ~(1ULL << 13);
    } else {
        GPIOC_ODR |= (1ULL << 13);
    }
}

會發現它如預期的運作了。

後來我發現 push up 的設計更合理，因為當我有把線接到 GPIO 且還沒插入 USB 時，GPIO 其實是低電位的（是有外部電壓的），所以使用 push-up、pull-down 或 floating 是沒什麼差別的。而考慮到有些使用者沒有在硬體上加入這些設計，使用 push up 讓檢查通過可以兼容這些硬體，並且讓他們一定程度上能運作。譬如說他們的 USART 有接上，但沒有把 5V 的訊號經過一些處理後接到 GPIO，那它序列通訊的功能還是可以正常運作。反過來說，如果它有接上的話，那麼在 USB 未插入的狀況下就會是低電位，所以會做是否有插入的檢查。
> commit [09a81d3](https://github.com/rota1001/arm-os-101/commit/09a81d3a23648574623efb97d479d64dcdc6a47b)
### 記憶體管理
這裡先暫時使用 first fit 策略，之後在思考有沒有必要換成其他策略。我想之後大機率會換成線性搜尋的 best fit 策略，因為 stm32f103 的 sram 只有 20KB，樹狀結構的優勢只有在節點多的時候才會顯現出來，而缺點就是每個節點要多花兩個 word 的空間來存左右節點的指標，這在空間受限的情況下是蠻大的花費。

實作上與我之前寫的 [custom-memory-allocator](https://github.com/rota1001/custom-memory-allocator) 大同小異，吸取了一點 glibc 的結構體設計。
用紀錄 `size` 與 `prev_size` 就能分別計算出下一個和上一個記憶體區塊的地址，並且讓記憶體區塊做對齊，在 LSB 紀錄那個區塊有沒有被使用。然後，使用長度為 0 的字元陣列來宣告分配的記憶體區塊，會由分配給結構體的記憶體大小決定陣列的大小。

typedef struct block {
    size_t size;
    size_t prev_size;
    char mem[0];
} block_t;

剩下就是把它實作出來：
> commit [bb8f39e](https://github.com/rota1001/arm-os-101/commit/bb8f39e103442dbdd072459c80e573182ab7e8b7)

### qemu 模擬環境建立
qemu 沒有對 stm32 的原生支援，這裡使用的是 fork 出來的版本 [qemu_stm32](https://github.com/beckus/qemu_stm32)，要注意的一件事是它只支援 python2，我自己是使用 conda 去建立虛擬環境。

$ sudo apt install device-tree-compiler libfdt-dev
$ git clone git://github.com/beckus/qemu_stm32.git
$ cd qemu-stm32
$ ./configure --enable-debug --disable-werror --target-list="arm-softmmu"
$ make -j`nproc`

### 系統時鐘頻率調整
參考 [嵌入式系統建構：開發運作於STM32的韌體程式](https://docs.google.com/document/d/1Ygl6cEGPXUffhTJE0K6B8zEtGmIuIdCjlZBkFlijUaE/edit?tab=t.0) 的敘述，將 system clock 的頻率提昇至 64MHz，之所以不是 72MHz 是因為我懶得去調整 bauding rate 所對應到的 BRR，所以希望 PCLK2 的頻率不會變，這樣的話如果提昇的頻率倍數是二的冪的話，就能直接使用 `RCC_CFGR_PPRE2` 去進行降頻。
前面有講過，stm32 的系統時鐘可以來自三種時鐘源，HSI、HSE 與 PLL，預設是使用 HSI。這裡要去升頻，所以要用 PLL。PLL 的來源可以是從 HSI 或是 HSE，這裡用 HSE。從下圖可以發現，如果從 HSE 來的話，可以依照 PLLXTPRE 去選擇要使用 HSE 的頻率或是 HSE 降頻至 $\frac{1}{2}$ 倍的頻率。reset 之後的預設是沒有降頻的，所以我就沿用原始設定。

接下來一步步來講解我的程式碼：
- 打開 HSE，並等待它穩定

    SET_REG_FIELD(RCC->CR, RCC_CR_HSEON, 1); /* Turn on HSE */
    while (!GET_REG_FIELD(RCC->CR, RCC_CR_HSERDY)); /* Wait for ready */

- 將 PLL 的來源設為 HSE

    SET_REG_FIELD(RCC->CFGR, RCC_CFGR_PLLSRC, 1); /* Set PLL source to HSE *

- 將倍率設為 8

    SET_REG_FIELD(RCC->CFGR, RCC_CFGR_PLLMUL,0b0110); /* set PLL multiplication factor to 8 */

- 將 PLL 開啟並等待它穩定

    SET_REG_FIELD(RCC->CR, RCC_CR_PLLON, 1);
    while (!GET_REG_FIELD(RCC->CR, RCC_CR_PLLRDY));

- 將 APB2 降頻倍率設為 8，讓 PCLK2 的頻率不變

    SET_REG_FIELD(RCC->CFGR, RCC_CFGR_PPRE2, 0b110); /* HCLK divided by 8 */

- 選擇 PLL 為系統時鐘源，並等待它穩定

    SET_REG_FIELD(RCC->CFGR, RCC_CFGR_SW, 2); /* PLL selected as system clock */
    while (GET_REG_FIELD(RCC->CFGR, RCC_CFGR_SWS) != 2);

### 排程器
排程器會從協同式排程開始，但之後會引入搶佔式排程。context switch 部份參考 [linmo](https://github.com/sysprog21/linmo/tree/main) 使用 `setjmp` 與 `longjmp` 進行實作。排程器作為一個特殊的任務，對於一個 CPU 都會儲存一個專屬於排程器的 context（雖然目前還沒有多核支援），對於 `yield` 或 timer interrupt 觸發的排程都會在儲存對應行程的 context 之後直接切換到排程器的 context。

我先前對於 kernel process 與 user process 的關係有點誤解，這裡做一下澄清。context switch 是從一個 kernel process 轉換到另一個 kernel process，如果要從一個 user process 轉換到另一個行程的話，那必須通過中斷進入 kernel process，再進行 context switch。之所以要強調這件事情是因為這會影響到我們需要儲存哪些 context，譬如說在 user process 中的 stack pointer 是 `psp`，而在 kernel process 中的 stack pointer 是 `sp`（當然這都是指在特權模式下看到的暫存器）。

這裡會需要儲存的暫存器有 `r4` 到 `r11`、`lr`（return address）、`sp`（stack pointer）。在 `setjmp` 中會去將暫存器的內容放到 `context_t` 結構體中：

__attribute__((naked)) int setjmp(context_t *ctx)
{
    asm volatile(
        "STR r4, [r0]\n"
        "STR r5, [r0, #4]\n"
        ...
        "STR lr, [r0, #32]\n"
        "STR sp, [r0, #36]\n"
        "mov r0, 0\n"
        "bx lr\n"
        :
        :
        : "memory");
}

正常呼叫下，`setjmp` 是回傳 0 的，然而，因為在 `setjmp` 中獲取的 context 是當下的 context，他的回傳地址（`lr`）會是結束 `setjmp` 呼叫後會回傳回去的地方，所以只能用回傳值來分辨是呼叫完 `setjmp` 的回傳還是使用 `longjmp` 去恢復 context 的。基於這樣的考量，`longjmp` 會在跳到回傳地址之前，先把 `r0` 設為 1：

__attribute__((naked)) void longjmp(context_t *ctx)
{
    asm volatile(
        "LDR r4, [r0]\n"
        "LDR r5, [r0, #4]\n"
        ...
        "LDR lr, [r0, #32]\n"
        "LDR sp, [r0, #36]\n"
        "mov r0, 1\n"
        "bx lr\n"
        :
        :
        : "memory");
}

以下寫一個測試的程式，它會先使用 `setjmp` 儲存 context，這個時候會回傳 0，接下來使用 `longjmp` 恢復 context，這個時候會恢復當時的狀態，並且回傳 1：

context_t ctx;
if (!setjmp(&ctx)) {
    printf("setjmp == 0\n");
    longjmp(&ctx);
} else {
    printf("setjmp == 1\n");
}

最後結果如同預期：

setjmp == 0
setjmp == 1

#### 協同式排程
首先是 `sched`，也就是排程的函式，它會不斷找下一個要被執行的行程，儲存當下排程器的 context，並恢復要被執行的行程的 context：

void sched(void)
{
    while (1) {
        list_node_t *now = task_list.next;
        if (now == &task_list)
            return;
        list_remove(now);
        list_push_back(&task_list, now);
        current = container_of(now, task_t, list);
        if (!setjmp(&sched_context))
            longjmp(&current->context);
    }
}

`yield` 是拿來讓一個行程主動放棄 CPU 的函式，它會儲存現在在執行的行程的 context，並恢復排程器的 context，等同於跳回那個無窮迴圈並且讓 `setjmp` 回傳 1：

void yield(void)
{
    if (!setjmp(&current->context))
        longjmp(&sched_context);
}

如果一直找得到下一個可以執行的任務，`sched` 是不會停止的。而實際上，在一個作業系統上沒有任務運行是非預期的行為，之後會設計個 idle 任務來執行。

接下來是用 `proc_create` 創建行程。給定一個初始函式與 `stack`，它會設定初始的 context，與初始化任務結構體：

task_t *proc_create(void (*func)(void), void *stack)
{
    task_t *task = (task_t *) malloc(sizeof(task_t));
    if (!task)
        return 0;
    memset(&task->context, 0, sizeof(task->context));
    task->context.lr = (unsigned long) func;
    task->context.psp = (unsigned long) stack;
    list_push_back(&task_list, &task->list);
    return task;
}

目前還沒有對任務的狀態做設計，這件事之後會處理。

接下來試驗一下：

void proc1(void)
{
    while (1) {
        printf("proc1\n");
        for (int c = 0; c < 50000; c++)
            ;
        yield();
    }
}

void proc2(void)
{
    while (1) {
        printf("proc2\n");
        for (int c = 0; c < 50000; c++)
            ;
        yield();
    }
}

void kernel_main()
{
    ...
    char *stack1, *stack2;
    stack1 = malloc(512);
    ...
    stack2 = malloc(512);
    ...
    if (!proc_create(proc1, stack1 + 512))
        goto FAIL3;
    if (!proc_create(proc2, stack2 + 512))
        goto FAIL3;
    sched();
}

會發現如預期的兩個行程交戶執行：

proc1
proc2
proc1
proc2
proc1
proc2
proc1
proc2

> commit [8b43155](https://github.com/rota1001/arm-os-101/commit/8b4315570d3ef606b7d9671d539d6e3fbaf70be3)
#### 搶佔式排程
TBD...
#### 使用者行程
TBD...
### 系統呼叫
TBD...
## Reference
- [Running Linux 6.14 on stm32f429](https://hackmd.io/@yawu/HkZ2pm22yx)
- [sysprog21/linmo](https://github.com/sysprog21/linmo)
- [jserv/mini-arm-os](https://github.com/jserv/mini-arm-os)