# 2025q1 Homework3
contributed by < [`EricccTaiwan`](https://github.com/EricccTaiwan?tab=repositories) >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 作業要求
- [ ] 縮減使用者和核心層級的通訊成本，並允許並行的對奕。
- [ ] 參照〈並行程式設計：排程器原理〉，引入若干 coroutine (注意：不得使用 POSIX Thread，採取教材提到的實作方式)，分別對應到 AI1, AI2 (具備玩井字遊戲的人工智慧程式，採取不同的演算法，可指定運作於使用者/核心層級) 和鍵盤事件處理，意味著使用者可連續觀看多場「電腦 vs. 電腦」的對弈，當按下 Ctrl-P 時暫停或回復棋盤畫面更新 (但運算仍持續)、當按下 Ctrl-Q 時離開「電腦 vs. 電腦」的對弈，注意不該使用 (n)curses 函式庫。當離開「電腦 vs. 電腦」的對弈時，ttt 應顯示多場對弈的過程，亦即類似 Moves: B2 -> C2 -> C3 -> D3 -> D4 的輸出，儘量重用現有的結構體和程式碼。
> 關於鍵盤事件和終端機畫面的處理機制，可參見 mazu-editor 原始程式碼和〈Build Your Own Text Editor〉。
- [ ] 在「電腦 vs. 電腦」的對弈模式，比照前述 load average 的計算方式，規範針對下棋 AI 的 load 機制，並運用定點數來統計不同 AI 實作機制對系統負載的使用率，整合到畫面輸出，開發過程中應有對應的數學分析和羅列實作考量因素。
- [ ] 對弈的過程中，要在螢幕顯示當下的時間 (含秒數)，並持續更新。
- [ ] 原本 kxo 棋盤繪製在核心模式，你應該修改程式碼，使畫面呈現的部分全部在使用者層級，且善用 bitops，降低核心和使用者層級之間的通訊成本，應給予相關量化
- [ ] 自 jserv/ttt 移植 reinforcement learning (RL) 到 kxo 核心模組，使其得以動態切換。
## Simrupt
為了理解 simrupt 的模擬 interrupt ， 因此查閱了 〈[Linux Kernel Development](https://www.doc-developpement-durable.org/file/Projets-informatiques/cours-&-manuels-informatiques/Linux/Linux%20Kernel%20Development,%203rd%20Edition.pdf)〉 一書，
> 這本書雖然於 2010 後沒就再進行更新， Linux kernel 停在 v2.6，但其中的概念說明得很清楚，如果要追 code 還是得看最新版本的 kernel
**Top Halves Versus Bottom Halves**
> These two goals—that an interrupt handler execute quickly and perform a large amount of work—clearly conflict with one another. Because of these competing goals, the pro-cessing of interrupts is split into two parts, or halves.The interrupt handler is the top half. The top half is run immediately upon receipt of the interrupt and performs only the work that is time-critical, such as acknowledging receipt of the interrupt or resetting the hardware.Work that can be performed later is deferred until the bottom half. The bottom half runs in the future, at a more convenient time, with all interrupts enabled
在 Linux 核心中，當系統處於正常執行狀態時，若接收到中斷（interrupt），核心會立即暫停當前的執行流程，轉而執行與該中斷相關的處理程式。這段立即執行的程式即為中斷的 Top Half ，其負責處理與硬體即時性相關的工作 (也是 Hard IRQ) ，例如確認中斷來源、清除中斷旗標，或快速收取資料等
[Linux 核心設計課程作業說明 - kxo \(C)](https://hackmd.io/@sysprog/linux2025-kxo/%2F%40sysprog%2Flinux2025-kxo-c#Interrupt-Handling)
>在 Linux 核心當中的中斷大致上有數種特性，例如以下兩種
>* interrupt handler must execute quickly
>* sometimes an interrupt handler must do a large amount of work
>
>有些情況是兩種特性都存在的，但它們看起來互相衝突，該如何解決呢？ Linux kernel 採用一種方式叫 deferred interrupts ，**將中斷處理延遲**，並且將上述兩種特性分別稱為 top half 和 bottom half ... 在 top half 只處理一點重要的事然後就將 bottom half 交由之後的 context 處理。
為了避免中斷 handler 耗時過長而影響系統即時性，Linux 將中斷處理流程區分為兩個階段。**Top Half** 處理緊急且時間敏感的部分 (e.g., 資料存取) ，而剩餘可延後處理的工作 (e.g.,資料處理) ，則交由 **Bottom Half** 來完成。
* Top Half : 執行於 hard interrupt (IRQ) context ，且不允許 blocking 或 sleeping 。 代代表一旦進入 Top Half，就必須快速完成關鍵處理並將控制權盡快交還給 kernel，避免系統被中斷長時間卡住，影響即時性與效能。
* Bottom half: 將中斷處理延遲，可執行在較低優先權、可延後的環境中。它可以透過 `softirq`、 `tasklet` 、 `workqueue` 、 `kernel thread` 等機制實作，並允許執行 blocking /可 sleeping 的操作，適合處理耗時、複雜或不可在 IRQ context 進行的邏輯。
因此在 simrupt 中主要也可以分成這兩個處理階層
#### Top Half
* 由 `timer_handler()` 模擬 interrupt 觸發。
* 呼叫 `process_data()` 處理 interrupt 邏輯：
* `update_simrupt_data()` 產生模擬資料。
* 呼叫 `fast_buf_put()` 將資料存入中斷專用的快速環形緩衝區 `fast_buf`。
* 透過 `tasklet_schedule()` 排程 Bottom Half 執行後續處理。
* 當 `timer_handler()` 結束前 ，會呼叫 `local_irq_enable()` 新啟用 local interrupt ，模擬 IRQ handler 結束後**交還控制權給 kernel** 。
#### Bottom Half
* Tasklet (`simrupt_tasklet_func`):
* 接收 Top Half 的排程請求 (`simrupt_tasklet`) 。
* 呼叫 queue_work()，把真正要執行的邏輯推進 workqueue。
* `queue_work(simrupt_workqueue, &work)`
* Workqueue (`simrupt_work_func`):
* 執行於 kernel thread context，可睡眠。
* 反覆使用 `fast_buf_get()` 取出 fast buffer 中的資料。
* 呼叫 `produce_data()` 把資料放進 kfifo（供 user-space read 使用）。
* 最後透過 `wake_up_interruptible()` 喚醒等待 read 的使用者。
`timer_init` 中 `timer_setup` : 初始化 `struct timer_list` 和指定 callback 函式 `timer_handler()` 。
當 user 輸入 `cat /dev/simrupt` 時，會觸發 `timer_open` 的 `mod_timer`
### interrupt context
起初，繼寬問我 interrupt 不也是一種 process 嗎? 因此針對這個問題，去搜尋了一下答案
首先，什麼是 interrupt ? 在 [Quora : How is context switch different than an interrupt?](https://qr.ae/pAy0zs) ，留言解釋，
> An interrupt is something that causes the CPU to start executing the interrupt service routine [ISR].
interrupt 是一種事件，它會讓 CPU 開始執行對應的 ISR
> This makes the synchronous portions of interrupt handling fall outside of the control of the scheduler and is therefore not really considered a process.
同時，interrupt 處理中與 synchronous 相關的部份**不受排程器的控制**，因此 interrupt 不被視為是一個 **process**。
這也解釋了在〈Linux Kernel Development〉中給出的以下結論
> Interrupt context, on the other hand, is not associated with a process.
也因為 interrupt 不受到排程器控制，因此在 top half 中的操作是 time curcial 的，若不盡快處理完，則 CPU 就會一直卡著，什麼事情也做不了，直到 top half 結束把資源還回來。
### softirqs
> Each processor has its own thread that is called ksoftirqd/n where the n is the number of the processor.
>
我的電腦是 8 核的CPU，透過下方的觀察，也能印證 1 個 CPU 只擁有 1 個特定的 kernel thread 去處理 SoftIRQ ，以及透過 `cat /proc/softirqs` 觀察每一種 SoftIRQ 類型，在每個 CPU 上被觸發的次數
```shell
$ systemd-cgls -k | grep ksoft
├─ 16 [ksoftirqd/0]
├─ 26 [ksoftirqd/1]
├─ 32 [ksoftirqd/2]
├─ 38 [ksoftirqd/3]
├─ 44 [ksoftirqd/4]
├─ 50 [ksoftirqd/5]
├─ 56 [ksoftirqd/6]
├─ 62 [ksoftirqd/7]
$ cat /proc/softirqs
CPU0 CPU1 CPU2 CPU3 CPU4 CPU5 CPU6 CPU7
HI: 151243 69531 65991 56232 63351 66739 63283 795674
TIMER: 239931 178717 153575 183527 134650 128697 165752 269527
NET_TX: 0 3 0 0 1 1 1 1
NET_RX: 838 793 652 672 592 583 420932 918
BLOCK: 167230 24 1 22 111 0 0 0
IRQ_POLL: 0 0 0 0 0 0 0 0
TASKLET: 10131 294 123 217 162 171 1790 155
SCHED: 1063906 650972 492111 448625 445299 417783 452196 510990
HRTIMER: 5 0 1 7 0 0 8469 2
RCU: 328984 304883 293418 298223 287283 284045 299032 306955
$
```
### workqueues
> Tasklets always run on the processor from which they were originally submitted. Workqueues work in the same way, but only by default.
Tasklets 是建立在 SoftIRQ 上，後者是 `per-CPU` 的機制，因此在 CPU0 上呼叫 `tasklet_schedule(&my_tasklet)` ，這個 tasklet 只會在 CPU0 上執行; 反之， workqueue 在「預設」的情況下野會在排程它的 CPU 上執行，但可以跨 CPU 、跨 thread 執行。
**[struct workqueue_struct \*alloc_workqueue(const char \*fmt, unsigned int flags, int max_active, ...)](https://docs.kernel.org/core-api/workqueue.html#c.alloc_workqueue)**
> For a per-cpu workqueue, max_active limits the number of in-flight work items for each CPU. e.g. max_active of 1 indicates that each CPU can be executing at most one work item for the workqueue.
> For unbound workqueues, `max_active` limits the number of in-flight work items for the whole system. e.g. `max_active` of 16 indicates that that there can be at most 16 work items executing for the workqueue in the whole system.
```c
// bound workqueue（預設 per-cpu）
alloc_workqueue("wq1", 0, 1);
// unbound workqueue
alloc_workqueue("wq2", WQ_UNBOUND, 16);
```
對於 unbound workqueues 來說，`max_active` 是限制整個系統的 work items 數量，而
`struct timer_list` 則是運用在 kernel space 當中的 dynamic timers
```c
/* Data produced by the simulated device */
static int simrupt_data;
```
## __stringify
```c
/* Indirect stringification. Doing two levels allows the parameter to be a
* macro itself. For example, compile with -DFOO=bar, __stringify(FOO)
* converts to "bar".
*/
#define __stringify_1(x...) #x
#define __stringify(x...) __stringify_1(x)
```
可以看到這邊的疑惑，為什麼 stringification 需要分兩層做，因此查詢 C99 規格書，
**6.10.3.1 Argument substitution**
> A parameter in the replacement list, unless preceded by a `#` or `##` preprocessing token or followed by a `##` preprocessing token (see below), is replaced by the corresponding argument after all macros contained therein have been expanded.
當參數與`#` 或 `##` 的[操作子 (operator) ](https://hackmd.io/@sysprog/it-vocabulary?stext=15389%3A8%3A0%3A1744571906%3Awkc8iX)搭配時，該參數不會被預先展開，所以才會有了上方兩層轉換的設計，如果只有單層轉換，
```c
#define FOO bar // FOO 會被展開成 bar
#define __stringify_1(x...) #x
__stringify_1(FOO) // 結果為"FOO"而非"bar"
```
此處 `FOO` 未被展開為 `bar`，因 `#` 操作子阻止了參數的巨集展開。因此透過雙層巨集強至分階段處理，
```c
#define __stringify_1(x...) #x // 實際字串化
#define __stringify(x...) __stringify_1(x) // 強制展開參數
__stringify(FOO) // 展開流程：
// 1. __stringify_1(FOO) => __stringify_1(bar) 展開巨集
// 2. 結果為"bar"
```
可以用一個表格來對照，
| 輸入 | 只用單層巨集 | 用雙層巨集 |
| ------------------------ | ------------ | ----------- |
| 一般參數 (`kxo_state`) | `"kxo_state"` | `"kxo_state"` |
| 巨集 (`#define FOO bar`) | `"FOO"` | `"bar" ` |
這樣的設計確保能統一處理所有參數類型，因此在 kxo 中，亦能正確的把 `kxo_state` 轉換成字串 `"kxo_state"`
```c
// _name 換被 kxo_state 所替換，且 kxo_state 不是巨集，只是一般參數
__stringify(kxo_state) => __stringify_1(kxo_state) => "kxo_state"
```
進而，最終可以得到，
```c
struct device_attribute dev_attr_kxo_state = { \
.attr = {.name = "kxo_state", \
.mode = 0644 }, \
.show = kxo_state_show, \
.store = kxo_state_store,
}
```
### Variadic Macros
同時，可以注意到 `__stringify(x...)` 所接受的參數 `x...` 形式比較特殊，這其實是 C 語言的一個擴展功能，稱為 [Variadic Macros (可變參數巨集)](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html#Variadic-Macros-1)，其詳細說明可參考 GCC 官方文件。
> The variable argument is completely macro-expanded before it is inserted into the macro expansion, just like an ordinary argument. You may use the ‘#’ and ‘##’ operators to stringize the variable argument or to paste its leading or trailing token with another token.
根據上述文件描述，可變參數如同一般參數一樣，在被插入到巨集擴展體之前會先被完全展開。這也表示我們可以對可變參數使用 `#` (字串化) 或 `##` (拼接) 操作子，下方舉例說明其運作方式 :
```c
#define FOO bar,bq
__stringify(FOO)
// 展開流程：
// 1. __stringify(FOO) 首先將 FOO 展開成 bar, bq
// => 呼叫 __stringify_1(bar, bq)
// 2. __stringify_1 接到參數 bar, bq，執行字串化
// => 結果為 "bar, bq"
```
透過這種設計，即使傳入的參數在展開後包含多個以逗號分隔的部分，`__stringify` 巨集也能將它們完整地轉換成單一字串，確保了處理的正確性與彈性。
---
softirqs
tasklets
workqueues
做 mod
(((head) - (tail)) & ((size)-1))
Consumer
`static int fast_buf_get(void)`
Producer
`static int fast_buf_put(unsigned char val)`
drive 一定要有這兩條，
```c
module_init(simrupt_init);
module_exit(simrupt_exit);
```
因此先去看 simrupt_init 做了什麼事情，
透過 `kfifo_alloc` 建立一個 circular buffer 給 Bottom-half 使用，
:::danger
善用 bpftrace 追蹤
:::
Sign in with Wallet
Connect another wallet