--- tags: linux2025 --- # [2025q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 11 週測驗題 :::info 目的: 檢驗學員對 [I/O 模型](https://hackmd.io/@sysprog/linux-io-model)、[CPU 排程器](https://hackmd.io/@sysprog/linux-scheduler)和[並行程式設計](https://hackmd.io/@sysprog/concurrency)的認知 ::: ==[作答表單: 測驗 `1`](https://docs.google.com/forms/d/e/1FAIpQLSfFg3GrvDPpSviuCwCL-YoWXnzTr-p9oFSD5Z-u6roT0UdDGg/viewform?usp=dialog)== ### 測驗 `1` 以下嘗試改寫 [ktcp](https://hackmd.io/@sysprog/linux2025-ktcp) 作業，`kweb` 是個運作於 Linux 核心中的迷你 HTTP 伺服器，直接在核心空間接受 TCP 連線、解析 HTTP/1.1 請求，回送固定的 `Hello, world!` 字串，並嘗試在多核處理器系統上降低 lock contention。 kweb 載入時建立一條 listener 執行緒與多條 worker 執行緒，藉由 lock-free SPSC ringbuffer 把 listener 接收到的 socket 指標交給對應 worker，整個過程只依賴 release/acquire memory barrier，不依賴 spinlock 或 atomic 操作。 > 延伸閱讀: [並行程式設計: Lock-Free Programming](https://hackmd.io/@sysprog/concurrency-lockfree) 載入時，`kweb_init()` 先決定執行緒數量：若未指定則取 `max(2, num_online_cpus())`，確保一條 listener 與至少一條 worker。listener 藉由 ```c ctx0->listen_sock = create_listen(&err); kthread_run(listener, ctx0, "kweb/accept"); ``` 獲得唯一的 TCP listening socket 並啟動 `listener()` 執行緒；其餘執行緒以 ```c ctx->rbuf = kmalloc(RBUF_SIZE, GFP_KERNEL); kthread_run(worker, ctx, "kweb/%d", idx); ``` 各自投入 `worker()` 迴圈並擁有獨立的 4 KiB recv buffer 及 `accept_ring`。 listener 採非阻塞策略：先用 `vfs_poll()` 檢查 `POLLIN`，若 backlog 為空就 `schedule_timeout_interruptible(10 ms)` 休眠。偵測到連線後使用 ```c while (kernel_accept(ctx0->listen_sock, &cs, O_NONBLOCK) == 0) { struct thread_ctx *dst = &ctx0[(rr++ % (num_threads-1)) + 1]; if (ring_enqueue(&dst->ring, cs)) sock_release(cs); } ``` 以 round-robin 策略，將 socket 指標寫入目標 worker 的 SPSC ring。`ring_enqueue()` 只是把指標寫進 slot 再 `smp_store_release(&r->head, next)`，整個過程不觸及 spinlock 或 atomic。 worker 每回合先清空接受佇列： ```c while (ctx->nr_cli < MAX_CLIENTS) { struct socket *cs = ring_dequeue(&ctx->ring); if (!cs) break; struct file *cf = sock_alloc_file(cs, 0, NULL); ctx->cli[ctx->nr_cli++] = (struct client_ctx){ .sock = cs, .file = cf }; } ``` 接著逐一走訪 `cli[]`。若 `vfs_poll()` 回傳 `POLLIN`，就呼叫 `handle_cli()`。若整個迴圈偵測不到任何活動，worker 會進入可被訊號喚醒的睡眠；忙碌狀態則在迴圈尾呼叫 `cond_resched()`，自願釋放 CPU，避免 soft-lockup。listener 在空檔同樣使用 10 ms sleep，二者都不會無止盡等待。 > 延伸閱讀: [Softlockup detector and hardlockup detector](https://docs.kernel.org/admin-guide/lockup-watchdogs.html) 卸載時 `kthread_stop()` 先終止 listener，確定不再有新 socket 投遞，之後逐條停止 workers。每個 worker 清空剩餘客戶端、`poll_freewait()` 釋放 wait-queue，再由 `stop_thread()` 釋放 recv buffer 與 listener file。至此資源全部回收，模組方可安全卸載。 lock-free SPSC (single-producer/single-consumer) 建構在[環形佇列](https://en.wikipedia.org/wiki/Circular_buffer) (circular buffer; ring buffer) 之上，其目標是讓資料在二個固定角色之間移動時，佇列大小取 2 的冪，這樣可用位元遮罩取代昂貴的除法。producer 只遞增 head，consumer 只遞增 tail，彼此永遠不會同時寫入同一個欄位，所以不需要互斥。唯一要保證的是「socket 指標寫進 slot 後，consumer 必須先看到資料，再看到 head 前進」，於是 producer 在更新 head 時使用 `smp_store_release()`；consumer 在讀 head 前使用 `smp_load_acquire()`。release / acquire barrier 確保記憶體次序 (memory order)，同時比 full barrier 成本低。 在 kweb 中，listener thread 是佇列的唯一 producer，它將 `kernel_accept()` 取得的 `struct socket *` 寫入 worker 的 ring。worker thread 是唯一 consumer，從環形佇列讀出指標後把它轉成 `struct file` 並加入自己的 client 陣列。該設計有以下好處： 1. 避免多 listener 方案裡對 `inet_csk_accept()` 的競爭。無論有多少 CPU，真正呼叫 accept 的只有 listener，一次持有 short-lived 鎖就結束，再透過無鎖佇列把結果發給其他核心，省去了 N 個執行緒同時搶 accept 鎖的 cache-line ping-pong 2. 資料路徑 cache-local。每個 worker 只處理自己 ring 與 client 陣列，這些結構和 recv buffer 都分配在本 CPU 上，後續應用層 parse 與 send 都在同一處理器核完成，減少跨處理器核遷移 3. 可預測的 [back pressure](https://en.wikipedia.org/wiki/Back_pressure) 機制。`ring_enqueue()` 只要發現下個位置會撞到 tail，就立即回傳 `-ENOSPC`；listener 採取 `sock_release(cs)` 直接丟連線，從而把壓力傳回 TCP 三向交握，避免大量排隊造成延遲尖峰。若要更平滑，可將失敗計數配合 `msleep()` 實作節流，也不影響佇列本身的 lock-free 特性。 在多個處理器核數和大量新連線場景下，上述手法通常能有接近線性擴充的吞吐，而不會被全域 lock 或 cache 失衡所拖慢。 [kweb.c](https://gist.github.com/jserv/de379f067bcb567c4781c3b45e6609aa) 是對應的實作，可在 Linux v6.8 編譯和執行，參考的執行訊息: ``` + sudo insmod kweb.ko + curl http://localhost:8848 Hello, world!+ echo '--- Baseline (c=50) ---' --- Baseline (c=50) --- + wrk -t4 -c50 -d30s http://localhost:8848 Running 30s test @ http://localhost:8848 4 threads and 50 connections Thread Stats Avg Stdev Max +/- Stdev Latency 11.78ms 11.27ms 106.44ms 78.16% Req/Sec 612.32 829.90 12.24k 95.63% 66790 requests in 30.06s, 4.84MB read Socket errors: connect 0, read 0, write 0, timeout 48 Requests/sec: 2222.22 Transfer/sec: 164.93KB + sudo rmmod kweb ``` 補完程式碼，使其運作符合預期，作答規範： * `AAAA` (Line 54) 包含 `_ONCE` 結尾的巨集，作為 compiler barrier，參見[並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics) * `BBBB` (Line 70) 不該出現 `/` 或 `%` 一類的除法運算子 * `CCCC` (Line 97) 和 `DDDD` (Line 98) 是十進位數值 * `EEEE` (Line 313), `IGNORE1` (Line 231), `IGNORE2` (Line 350), `HHHH` (Line 285) 包含 `kthread_` 開頭的函式或巨集 * `GGGG` (Line 264) 以 `TASK_` 開頭的巨集 * 使用一致的程式碼風格，避免開頭和結尾的空白字元，以最精簡的形式書寫 :::success 延伸問題: 1. 解釋上述程式碼運作原理並指出其效能瓶頸 2. 探討 poll 效率和在多核處理器的效能議題 3. 改進 lock-free SPSC 實作並針對 kweb 場景予以調整 :::