# 2025q1 Homework3 (kxo)
contributed by < `tsaiiuo` >
:::danger
標題不符合作業規範，注意細節！
:::
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## Linux 核心的並行處理
### kfifo
```c
int kfifo_to_user(struct kfifo *fifo, void __user *dest, unsigned int len, unsigned int *copied);
```
若運行正常會回傳 0 ，反之則運行失敗，同時將讀取資料從 FIFO 移除
```c
do {
ret = kfifo_to_user(&rx_fifo, buf, count, &read);
if (unlikely(ret < 0))
break;
if (read)
break;
if (file->f_flags & O_NONBLOCK) {
ret = -EAGAIN;
break;
}
ret = wait_event_interruptible(rx_wait, kfifo_len(&rx_fifo));
} while (ret == 0);
```
因此若 `read` 大於 0 時則直接中斷迴圈，反之先呼叫 `wait_event_interruptible()` 等待資料
### `bpftrace`
詳細去探討 softirq 的幾種處理模式，主要探討 workqueue，tasklet
#### 使用 `bpftrace` 追蹤 /dev/simrupt 開啟的狀態
```c
tasklet_func: comm=ksoftirqd/7, pid=62, tid=62
work_func: comm=kworker/u32:5, pid=120363, tid=120363
tasklet_func: comm=swapper/0, pid=0, tid=0
work_func: comm=kworker/u32:5, pid=120363, tid=120363
tasklet_func: comm=swapper/7, pid=0, tid=0
work_func: comm=kworker/u32:2, pid=120699, tid=120699
tasklet_func: comm=gnome-shell, pid=2272, tid=2272
work_func: comm=kworker/u32:2, pid=120699, tid=120699
tasklet_func: comm=ksoftirqd/0, pid=16, tid=16
work_func: comm=kworker/u32:0, pid=118325, tid=118325
```
<s>我查到的資訊如下
| 名稱 | 類型 | 何時執行 | 可否睡眠 | 用途 |
|------------------|--------------|----------------------------------------------|---------|-------------------------------------|
| swapper/0 | idle task | CPU 沒有 runnable thread 時 | 是 | 進入 CPU idle / 省電 |
| gnome‑shell | userspace | 在桌面環境下執行 shell 時 | 是 | 桌面 UI 與視窗管理 |
| Isolated Web Co | userspace | 瀏覽器隔離的 web 內容 process | 是 | 沙箱化的網頁內容執行 |
| kworker/u32:3 | kernel thread| 呼叫 `queue_work()` 之後執行 workqueue | 是 | 做可睡眠、可阻塞的 deferred work |
| ksoftirqd/0 | kernel thread| softirq 在硬中斷上下文無法完成時由此清理 | 閒置時是，一旦開始處理 softirq 則不行 | 在 process context 延後執行 softirq |
Linux 在「軟中斷（softirq）」的上下文裡，是這樣排程它們執行的：
硬中斷結束時 立刻跑一輪 softirq（若未超過預定數量）。
若上面那輪沒跑完（或達到 quota）就排到 ksoftirqd/<cpu> 這支 kernel thread 來處理 backlog。
並且每次進入或離開系統呼叫（syscall、iret、return_from_exception）前後，kernel 都會檢查是否有 pending softirq，並在當前執行緒上下文（current->comm）裡跑一輪。
</s>
>[2025-04-15 問答簡記](https://hackmd.io/V7bD2XjnQuCZqDMt4ZizGA?view#%E5%9B%9E%E9%A1%A7-simrupt) 上課有詳細地在 **與其在字面意義「推敲」，不如運用 eBPF 分析** 討論
```text
? (PID=0)
│
├── init (systemd) (PID=1)
│
└── kthreadd (PID=2)
kthreadd (PID=2)
│
├── kworker (running workqueue, per CPU)
│
│
└── ksoftirqd (CPU-wise)
```
透過上圖解釋 kworker 與 ksoftirqd 與 kthreadd 的關係，並且也確實是 kernel thread 可被處理器排程，除此之外閱讀 **Demystifying the Linux CPU Scheduler** 的第二章節 46 頁
> idle is used to schedule the per-cpu idle task (also called swapper
task) which is run if no other task is runnable
得知 swapper 行程負責執行所謂的 idle task ，並且 idle task 是順位最低的任務，表格表示順位由高到低排序的結果，來自 **Demystifying the Linux CPU Scheduler** 的第二章節 45 頁
| Scheduling classes | Scheduling policies |
| --------------------- | ------------------- |
| stop_sched_class | SCHED_DEADLINE |
| dl_sched_class | SCHED_FIFO |
| rt_sched_class | SCHED_RR |
| fair_sched_class | SCHED_NORMAL |
| idle_sched_class | SCHED_BATCH |
| | SCHED_IDLE |
:::danger
彙整課程教材和對應討論！
:::
> 了解，以新增彙整教材來源和看法
這裡觀察到 `swapper/0` 我推測試表示 CPU 在 idle 時候（idle task）檢查並跑 softirq。
`gnome‑shell`、`Isolated Web Co` 則表示我在測試的當下是在桌面環境下執行 shell 並且也有跑網頁瀏覽器，那它們就成了當下在呼叫者脈絡中直接執行(direct softirq)。
#### 追蹤 `simrupt_tasklet_func`
```shell
$ sudo bpftrace -e '
kprobe:simrupt_tasklet_func {
printf("Tasklet started: CPU %d, Time %llu ns, PID %d, Comm %s\n", cpu, nsecs, pid, comm);
}
kretprobe:simrupt_tasklet_func {
printf("Tasklet ended: CPU %d, Time %llu ns, PID %d, Comm %s\n", cpu, nsecs, pid, comm);
}
'
```
在 softirq context 中，pid 通常為 0 ，因其執行於 interrupt context，不屬於一般行程。也就是前面觀察到的 `swapper/0` ，而也可以觀測出每個 tasklet 確實都在同一個 cpu 下完成動作。
```c
Tasklet started: CPU 6, Time 109690157318108 ns, PID 0, Comm swapper/6
Tasklet ended: CPU 6, Time 109690157333077 ns, PID 0, Comm swapper/6
Tasklet started: CPU 7, Time 109690261332207 ns, PID 0, Comm swapper/7
Tasklet ended: CPU 7, Time 109690261367869 ns, PID 0, Comm swapper/7
Tasklet started: CPU 3, Time 109690365106477 ns, PID 38, Comm ksoftirqd/3
Tasklet ended: CPU 3, Time 109690365137567 ns, PID 38, Comm ksoftirqd/3
Tasklet started: CPU 3, Time 109690469109373 ns, PID 0, Comm swapper/3
Tasklet ended: CPU 3, Time 109690469141214 ns, PID 0, Comm swapper/3
Tasklet started: CPU 4, Time 109690573115972 ns, PID 0, Comm swapper/4
Tasklet ended: CPU 4, Time 109690573157736 ns, PID 0, Comm swapper/4
Tasklet started: CPU 4, Time 109690677322947 ns, PID 0, Comm swapper/4
Tasklet ended: CPU 4, Time 109690677346556 ns, PID 0, Comm swapper/4
Tasklet started: CPU 4, Time 109690781032125 ns, PID 0, Comm swapper/4
Tasklet ended: CPU 4, Time 109690781066765 ns, PID 0, Comm swapper/4
Tasklet started: CPU 2, Time 109690885328658 ns, PID 0, Comm swapper/2
Tasklet ended: CPU 2, Time 109690885352016 ns, PID 0, Comm swapper/2
Tasklet started: CPU 2, Time 109690989289717 ns, PID 0, Comm swapper/2
Tasklet ended: CPU 2, Time 109690989301835 ns, PID 0, Comm swapper/2
```
## 對奕的核心模組
### 接收 Ctrl+Q 的輸入
這邊在測試 sample code 時發現 Ctrl + Q 的功能是無法使用的，因此去了解以下程式碼
```clike
static struct termios orig_termios;
static void raw_mode_disable(void)
{
tcsetattr(STDIN_FILENO, TCSAFLUSH, &orig_termios);
}
static void raw_mode_enable(void)
{
tcgetattr(STDIN_FILENO, &orig_termios);
atexit(raw_mode_disable);
struct termios raw = orig_termios;
raw.c_lflag &= ~(ECHO | ICANON);
tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw);
}
```
**c_iflag** 在 Linux 終端機設定中，c_iflag 代表輸入模式標誌，其中 `ECHO` 代表平常對終端機輸入時都會即時的在終端機呈現出來，`ICANON` 是將鍵盤輸入被視為一行一行處理，內核會等待直到遇到換行或 EOF（例如 Ctrl+D）才將輸入交給應用程式，並啟用內建的行編輯功能，例如：Ctrl+H（通常作為退格鍵），Ctrl+U（通常用來刪除整個行），Ctrl+W（通常用來刪除一個單詞））。
而其中 IXON 是用來啟用 XON/XOFF 軟體流控制的旗標，對應到的是Ctrl+S（通常代表停止傳輸）和 Ctrl+Q（代表繼續傳輸）。
**tcgetattr() :** 用來獲取 `STDIN_FILENO` 也就是標準終端機的輸入屬性並賦予給 `orig_termios`。
**atexit() :** 註冊一個函式使在程式關閉時能呼叫，這邊呼叫了 `raw_mode_disable` 去回覆原先的標準終端機輸入。
**tcsetattr()：** 用來設定指定終端機的屬性，第二個參數：`TCSAFLUSH` ，表示在應用新設定之前，丟棄輸入緩衝區中尚未處理的資料，同時等待輸出完成後再改變屬性。
**raw_mode_disable()：** 用來將原先的終端機標準輸入法復原。
> commit [db8c9ed](https://github.com/tsaiiuo/kxo/commit/db8c9edc78534b661c8ee75208459f3fd5f40096)
因此若需要接收 Ctrl + Q 的輸入則必須也把 `IXON` 也給去除。
> commit [27c41e9](https://github.com/tsaiiuo/kxo/commit/27c41e96cc75928815c29266fedd4d313dbdaf3c)
Linux kernel module 也須一併更改才可中止遊戲並重啟。
### 使畫面呈現的部分全部在使用者層級
> commit [0ccdfe6](https://github.com/tsaiiuo/kxo/commit/0ccdfe66fabfaf5cdea67aa4dd9ab460520ac818)
將 `draw_board` 的運算移動到使用者層級，並且把 `kxo` 內的邏輯移除只須傳送 `table` 本身
原先是透過傳送 66 位元的資料
```c
| | |
-------
| |O|
-------
| |X|
-------
| | |
-------
```
而改進之後只須傳遞 `table` 本身（16位元），因此，每次能減少 50 個字元的通訊成本。
### 顯示多場對弈的過程
>參考 [@rota1001](https://hackmd.io/@rota1001/linux2025-homework3#%E5%B0%8D%E5%A5%95%E7%9A%84%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84) 大大的程式碼
先創立紀錄程式碼本身
> commit [6acfa42](https://github.com/tsaiiuo/kxo/commit/6acfa4259e9705c98583f5af57f28c2740d91ff2)
每一步的可能性只有 16 種，因此用 4 個位元即可成功表示所有可能，而一場對局中最多就是 總共 16 步，因此可以用一個無號 64 位元整數去紀錄一場對局，更進一步說使用無號 64 位元整數的循環陣列去紀錄最近 `N_BOARDS` + 1 個對局。而 0 ~ 15 分別代表那一個區塊如以下設定：
```c
0|4|8|12
-------
1|5|9|13
-------
2|6|10|14
-------
3|7|11|15
-------
```
使用 bitwise 操作去動態更新 `head` 與 `tail` 的值，只須 O(1) 的時間複雜度
```c
if (((head - tail) & N_BOARDS) == 1)
head = (head + 1) & N_BOARDS;
```
這邊以 `N_BOARDS` 為 15 為例子，第一次串列大小來到 15 時會將 `head` 更新為 1 （ -15 & 15 = 1 ），因為下次的插入會插入 0 的位置去覆蓋以往的資料，並且在這之後在每次更新 `tail` 時 `head` 也都會動態更新。
>延伸閱讀 [演算法與資料結構 隊列(Queue)與循環對列(Circular Queue)](https://hackmd.io/@hank20010209/B1TkvWYO_#%E6%BC%94%E7%AE%97%E6%B3%95%E8%88%87%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E9%9A%8A%E5%88%97Queue%E8%88%87%E5%BE%AA%E7%92%B0%E5%B0%8D%E5%88%97Circular-Queue)
再來需要將紀錄在核心程式結束時傳遞給使用者，並進行適當的輸出
> commit [98433dd](https://github.com/tsaiiuo/kxo/commit/98433dd3258667051cb79417fa25de592a1d7842)
我的輸出期望目標一開始是期望像專案 `ttt` 那樣，但後來覺得要加入哪個對戰者的資訊比較有可閱讀性，因此先在一場遊戲判斷結束時內建初始的回合都給 `O` ，這樣的話就不需要額外記憶體空間也能判斷是誰的回合
```diff
//timer_handler(struct timer_list *__timer)
if (attr_obj.end == '0') {
...
+ turn = 'O';
...
}
```
使用 `ioctl（input/output control）`是一種用來做「非標準 I/O 操作」的機制，它允許使用者空間透過一支系統呼叫，把自訂的命令和參數傳給驅動程式，驅動程式再根據命令做出硬體或內核層面的特殊處理。它的調用個數如下：
```c
int ioctl(int fd, ind cmd, …)；
```
這裡設置兩個 `cmd` 分別對應取得棋盤局數大小與取得單一棋盤結果，因此只須 1 個位元即可表示所有狀態，這邊定義 `IOCTL_READ_SIZE` = 0 ，`IOCTL_READ_LIST` = 1 ，並透過判斷最後一個位元去執行相對應的操作
```c
static long kxo_ioctl(struct file *flip, unsigned int cmd, unsigned long arg)
{
int ret;
switch (cmd & 1) {
...
return ret;
}
```
在使用者端透過一連串的 bitwise 操作輸出內容
>延伸閱讀 [Linux Ioctl internel](https://hackmd.io/@happy-kernel-learning/ByVFh6BEw#linux%E7%B3%BB%E7%B5%B1ioctl%E4%BD%BF%E7%94%A8%E7%A4%BA%E4%BE%8B)
```c
void print_record(uint64_t record)
{
...
for (int i = 0; record_size; i += 1, record_size = record_size >> 4) {
unsigned int move = record_size & 15;
char turn = i & 1 ? 'X' : 'O';
printf("[%c] ", turn);
printf("%c%u", 'A' + (move >> 2), move & 3);
if (record_size >> 4)
printf(" -> ");
}
...
}
```
每次讀取 4 個位元，並將 4 個位元的值右移 2 位元之後即可獲取他由左到右的絕對順序（因為每個 column 儲存 4 筆資料），在將,同理在將 `move` 與 3 做 AND 的操作即可獲取由上到下的絕對位置，此外判斷 `i` 的奇偶也可知道是誰的操作。
:::danger
文字訊息不要用圖片展現
:::
目前紀錄結果如下
### 顯示當下的時間，並持續更新
> commit [2ee4092](https://github.com/tsaiiuo/kxo/commit/2ee4092d16c8caab3b8a1c63200c4e30ebc22960)
>
使用 `C` 函式庫內的 `<time.h>`
```c
time_t time(time_t *tloc);
```
回傳一個 time_t（通常是 long 或 long long）代表當前 UNIX epoch 以來的秒數。在呼叫以下函式轉成本地時間 struct `tm`
```c
struct tm *localtime_r(const time_t *timep, struct tm *result);
```
`tm` 結構如下
```c
struct tm {
int tm_sec; /* 秒，範圍 0–60 (因為可能有 leap second) */
int tm_min; /* 分，範圍 0–59 */
int tm_hour; /* 時，範圍 0–23 */
int tm_mday; /* 月中第幾天，範圍 1–31 */
int tm_mon; /* 月份 (0 = January, …, 11 = December) */
int tm_year; /* 1900 年以後的年分( 2025 → tm_year=125) */
int tm_wday; /* 星期 (0 = Sunday, …, 6 = Saturday) */
int tm_yday; /* 年中第幾天 (0 = Jan 1) */
int tm_isdst; /* 夏令時間標記 (>0 = DST in effect, 0 = no, <0 = unknown) */
};
```
轉換完成後配合原先的畫面輸出即可！
Sign in with Wallet
Connect another wallet