# 2025q1 Homework3 (kxo)
contributed by < `BrotherHong` >
## 小修正
### 核心模式棋盤繪製
> commit [12c45a3](https://github.com/BrotherHong/kxo/commit/12c45a3a272350f5bc1e1da223b7083987a2fd91)
在原本於核心繪製棋盤的函式 `draw_board` 中，未將字串的結尾放上 `\0` 導致使用者在讀取字串並直接輸出時會出現一些亂碼，因此修正將最後一個換行符號改成 `\0`。
```diff
{
...
while (i < DRAWBUFFER_SIZE) {
...
}
+ draw_buffer[i - 1] = '\0';
+ smp_wmb();
return 0;
}
```
### Ctrl+Q 無法使用
在一開始將專案 fork 並 clone 到本機執行測試時，README 提到的 Ctrl+Q 可以中止執行，但實際上卻沒有任何作用。雖然在作業教材的[對奕核心模組](https://hackmd.io/@sysprog/linux2025-kxo/%2F%40sysprog%2Flinux2025-kxo-d)中有提到可以使用下方的指令來讓其正常執行，不過每次重開終端機都必須輸入一次有點太麻煩了。
```b
$ stty start '^-' stop '^-'
```
閱讀參考教材 〈[Build Your Own Text Editor](https://viewsourcecode.org/snaptoken/kilo/)〉關於如何從零寫出一個文字編輯器，裡面在建構最初的文字編輯器環境時就有針對終端機的各種鍵盤按鍵做初始化，讓一些特殊鍵的功能失效，使終端機的環境回到最原始的狀態，其中就有提到 Ctrl+Q 的功能是用來 software flow control，當 Ctrl+S 被按下後就會使終端機停止接收資料傳輸，而在 Ctrl+Q 按下後就會重新啟動接收資料傳輸。
如果要停止使用 Ctrl+S 和 Ctrl+Q 的原始功能的話就需要在程式執行一開始時透過 termios 將特定的 flag 清除掉：
```c
struct termios raw = orig_termios;
raw.c_iflag &= ~(IXON);
```
不過已經看到<s>有人</s> 先修正了
:::danger
明確指出 GitHub 活動
:::
## <s>優化</s> 核心通訊成本
:::danger
注意用語
:::
**目標：** 將棋盤繪製的工作從核心改到使用者層級進行
**量化成本：** 傳輸 bytes 數量、在 `xo-user` 測量 `read()` 所耗費的時間 (us)
### 在使用者層級繪製棋盤
> commit [f17242e](https://github.com/BrotherHong/kxo/commit/f17242ef4a786f1b3382028e88897ceda40520c2)
#### 想法
要繪製棋盤，我們只需要知道每個位置的棋子狀態 ( ` ` `X` `O` ) 就能繪製了，因此我們只需要從 kernel space 讀取各格棋子的資訊。
最直覺的想法就是使用一個字元陣列 (`char grid[N_GRIDS]`) 來儲存，這樣傳輸的成本就從 66 bytes 降到 16 bytes (以 `BOARD_SIZE = 4` 為例)
但是考慮陣列裡面的數值只會有三種 ( ` ` `X` `O` ) ，用 8 bits 存太浪費了，3 種狀態最少只需要 $\left\lceil\log_2{3}\right\rceil=2$ bits 就能表達了，這樣一個 byte 就能存 4 個位置的棋子資訊，如此一來傳輸成本就變成 `N_GRIDS >> 2` 個 bytes (16 bytes -> 4 bytes)
:::danger
提供數學分析
:::
#### 實作
建立 `draw.h` 來定義傳輸資訊用的定義及操作
* 定義每種狀態對應的 bit
```c
#define DRAW_SPACE 0b00
#define DRAW_X 0b01
#define DRAW_O 0b10
```
* 依照 byte 中由 MSB 到 LSB 的順序，每 2 bits 存一個棋子狀態
```
O| |X| -> 0b10000100
-------
|X|O| -> 0b00011000
-------
| |X| -> 0b00000100
-------
O| |O| -> 0b10001000
-------
```
* 取得字元對應的 bits
```c
#define DRAW_GET_BIT(symb) \
((symb) == ' ' ? DRAW_SPACE : ((symb == 'X') ? DRAW_X : DRAW_O))
```
* 繪製、讀取字元
```c
#define DRAW_XO(chr, symb, i) ((chr) |= (DRAW_GET_BIT(symb) << ((i) << 1)))
#define DRAW_XO_GET_BIT(chr, i) (((chr) & ((0b11 << ((i) << 1)))) >> ((i) << 1))
#define DRAW_XO_GET_SYMB(chr, i) \
((DRAW_XO_GET_BIT(chr, i) == DRAW_SPACE) \
? ' ' \
: ((DRAW_XO_GET_BIT(chr, i) == DRAW_X) ? 'X' : 'O'))
```
* `xo-user` 讀到資料後繪製應用 (部份)
```c
for (int j = 0; j < (BOARD_SIZE << 1) - 1 && k < N_GRIDS; j++) {
display_buf[i++] =
j & 1 ? '|' : DRAW_XO_GET_SYMB(board_info[k >> 2], (k & 0x3));
if (j & 1)
k++;
}
```
#### 結論
從 kernel space 到 user space 的資料傳輸量從 66 bytes 優化成 4 bytes。 不過有點好奇這樣的差別會不會對傳輸時間有影響？
### 加入時間測量模式
> commit [122c9ca](https://github.com/BrotherHong/kxo/commit/122c9ca9d49fd1927fcc6aaf4e32a8ae32127331)
定義 `MEASURE_MODE` 來開關測量模式
```c
#define MEASURE_MODE 1
#if MEASURE_MODE
#define MEASURE_COUNT 1000
#define MEASURED_FILE "/tmp/measured_kernel.txt"
#endif
```
針對 `read()` 部份測量時間
* 當測量次數到會自動中止
* 設定 `len > 0` 去忽略錯誤或未讀到任何東西的情況
* 設定一個閾值 `elapsed_time >= 100` 去過濾掉時間小於 0.1 ms 的情況
* 在測量的時候，有時後會遇到時間不滿 1000 ns 的情況，與其他常見的測量時間差距過大，因此將其過濾掉
> 每次遇到此情況，當次棋盤會和前一次長的一樣，目前還不知道為什麼會這樣。
```c
int len;
long elapsed_time = 0;
clock_gettime(CLOCK_MONOTONIC, &start);
len = read(device_fd, display_buf, DRAWBUFFER_SIZE);
clock_gettime(CLOCK_MONOTONIC, &end);
if (len > 0) {
elapsed_time = (end.tv_sec - start.tv_sec) * 1000000 +
(end.tv_nsec - start.tv_nsec) / 1000;
// only record the time that is greater than 0.1 ms
if (elapsed_time >= 100)
measured_time[measure_idx++] = elapsed_time;
if (measure_idx >= MEASURE_COUNT)
end_attr = true;
}
```
### 測量結果比較
**測量方式：** 每個情況測量 1000 次，依照上方測量模式的方式測量，並在統計時去除頭尾 5% 的資料來過濾一些異常值。
:::danger
搭配 Ftrace 來分析。
:::
分別在 read 為 blocking 和 non-blocking 的情況下測量耗時的差異。
* blocking
當 read 為 blocking (預設) 時傳輸資料**平均時間**分在 kernel space 以及在 user space 繪製分別大約為 198 ms 和 205 ms，從圖表看也可以發現幾乎一模一樣。
```
📊 統計數據 (Kernel Drawing): 📊 統計數據 (User Drawing):
Mean: 197586.69 μs Mean: 204950.87 μs
Median: 104048.00 μs Median: 104011.00 μs
Standard Deviation: 181033.25 μs Standard Deviation: 189495.13 μs
Min: 9298.00 μs Min: 5096.00 μs
Max: 649861.00 μs Max: 673559.00 μs
Q1 (25%): 57768.00 μs Q1 (25%): 56817.50 μs
Q3 (75%): 296912.00 μs Q3 (75%): 299257.50 μs
```
:::danger
使用精準用語
:::
* non-blocking
**平均時間**大約落在 364 ns 和 382 ns ，與 blocking 的結果<s>差不多</s> ，不管在哪裡繪製，傳輸資料所花的時間都非常接近。
```
📊 統計數據 (Kernel Drawing): 📊 統計數據 (User Drawing):
Mean: 364.24 ns Mean: 382.07 ns
Median: 314.00 ns Median: 317.00 ns
Standard Deviation: 120.78 ns Standard Deviation: 138.26 ns
Min: 237.00 ns Min: 239.00 ns
Max: 801.00 ns Max: 816.00 ns
Q1 (25%): 300.00 ns Q1 (25%): 301.00 ns
Q3 (75%): 369.00 ns Q3 (75%): 390.25 ns
```
### 結論
透過將棋盤繪製的邏輯從 kernel space 搬移到 user space 並優化其傳輸成本，我們可以發現如果從**傳輸資料量**(bytes)的角度來看算是優化了許多；但如果從**傳輸時間**角度來看的話兩者的差異並不大，如此傳輸資料量的差距可能還不足以影響傳輸的時間。
## 筆記
### kmalloc vs. vmalloc
> [What is the difference between vmalloc and kmalloc?](https://stackoverflow.com/questions/116343/what-is-the-difference-between-vmalloc-and-kmalloc)
> [Memory Allocation Guide -- The Linux Kernel documentation](https://www.kernel.org/doc/html/v5.0/core-api/memory-allocation.html)
**主要差異：physical 記憶體位址是否連續**
* kmalloc
* 保證 physical 記憶體位址為連續的 (virtual 也是)
* 適用較小的記憶體需求
* vmalloc
* 不保證 physical 記憶體位址連續，但 virtual 是連續的
* 適用較大的記憶體需求
>[!Note] Get Free Page (GFP) flag
>`GFP_KERNEL` : 一般用途使用，分配成功率高 (可睡眠，嘗試等待記憶體回收)
>`GFP_NOWAIT` : 用於不能阻塞的情境 (不可睡眠，但可能會嘗試記憶體回收)
>`GFP_ATOMIC` : 用於不能阻塞的情境 (不可睡眠，也不會等待記憶體回收)
Sign in with Wallet
Connect another wallet