Try   HackMD

2025q1 第 11 週測驗題

目的: 檢驗學員對 I/O 模型CPU 排程器並行程式設計的認知

作答表單: 測驗 1

測驗 1

以下嘗試改寫 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

載入時,kweb_init() 先決定執行緒數量:若未指定則取 max(2, num_online_cpus()),確保一條 listener 與至少一條 worker。listener 藉由

ctx0->listen_sock = create_listen(&err);
kthread_run(listener, ctx0, "kweb/accept");

獲得唯一的 TCP listening socket 並啟動 listener() 執行緒;其餘執行緒以

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) 休眠。偵測到連線後使用

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 每回合先清空接受佇列:

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

卸載時 kthread_stop() 先終止 listener,確定不再有新 socket 投遞,之後逐條停止 workers。每個 worker 清空剩餘客戶端、poll_freewait() 釋放 wait-queue,再由 stop_thread() 釋放 recv buffer 與 listener file。至此資源全部回收,模組方可安全卸載。

lock-free SPSC (single-producer/single-consumer) 建構在環形佇列 (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 機制。ring_enqueue() 只要發現下個位置會撞到 tail,就立即回傳 -ENOSPC;listener 採取 sock_release(cs) 直接丟連線,從而把壓力傳回 TCP 三向交握,避免大量排隊造成延遲尖峰。若要更平滑,可將失敗計數配合 msleep() 實作節流,也不影響佇列本身的 lock-free 特性。

在多個處理器核數和大量新連線場景下,上述手法通常能有接近線性擴充的吞吐,而不會被全域 lock 或 cache 失衡所拖慢。

kweb.c 是對應的實作,可在 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 操作
  • 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_ 開頭的巨集
  • 使用一致的程式碼風格,避免開頭和結尾的空白字元,以最精簡的形式書寫

延伸問題:

  1. 解釋上述程式碼運作原理並指出其效能瓶頸
  2. 探討 poll 效率和在多核處理器的效能議題
  3. 改進 lock-free SPSC 實作並針對 kweb 場景予以調整