2025q1 Homework3

contributed by < EricccTaiwan >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

作業要求

• 縮減使用者和核心層級的通訊成本，並允許並行的對奕。
• 參照〈並行程式設計：排程器原理〉，引入若干 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〉 一書，

這本書雖然於 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)

在 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? ，留言解釋，

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 上被觸發的次數

$ 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, …)

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.

// 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

/* Data produced by the simulated device */
static int simrupt_data;

__stringify

/* 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) 搭配時，該參數不會被預先展開，所以才會有了上方兩層轉換的設計，如果只有單層轉換，

#define FOO bar //  FOO 會被展開成 bar
#define __stringify_1(x...)	#x

__stringify_1(FOO)  // 結果為"FOO"而非"bar"

此處 FOO 未被展開為 bar，因 # 操作子阻止了參數的巨集展開。因此透過雙層巨集強至分階段處理，

#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"

// _name 換被 kxo_state 所替換，且 kxo_state 不是巨集，只是一般參數
__stringify(kxo_state) => __stringify_1(kxo_state) => "kxo_state"

進而，最終可以得到，

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 (可變參數巨集)，其詳細說明可參考 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.

根據上述文件描述，可變參數如同一般參數一樣，在被插入到巨集擴展體之前會先被完全展開。這也表示我們可以對可變參數使用 # (字串化) 或 ## (拼接) 操作子，下方舉例說明其運作方式 :

#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 一定要有這兩條，

module_init(simrupt_init);
module_exit(simrupt_exit);

因此先去看 simrupt_init 做了什麼事情，
透過 kfifo_alloc 建立一個 circular buffer 給 Bottom-half 使用，

善用 bpftrace 追蹤