N07: ktcp

主講人: jserv / 課程討論區: 2025 年系統軟體課程

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

返回「Linux 核心設計」課程進度表

Concurrency Managed Workqueue (CMWQ)

參考自 Linux 核心文件 Workqueue

在 Linux 核心中，workqueue 是種達成非同步 (asynchronous) 執行的機制，可用於 deferred work 的處理。藉由 workqueue，開發者可將欲執行的「工作項目」(work item) 包裝為結構體，提交給核心排入佇列，核心則會由適當的 worker thread 進行處理。

傳統上，workqueue 會以 struct list_head 串接各個待執行的 work item。開發者使用 queue_work() 等介面提交工作後，核心便會指派一個適當的 worker thread 執行該任務。任務完成後將自佇列中移除。這樣的設計旨在簡化核心內部的執行緒使用與管理，並依據系統中可用的 CPU 數量進行並行處理，提升效率。

傳統 workqueue 架構與限制

在引入 CMWQ 之前，Linux 的 workqueue 實作存在一些重要限制，主要展現於資源耗用與並行能力的取捨上：

每個被建立的 workqueue 都會對應到一組獨立的 worker threads。
提供 2 種 workqueue 型態：
- Single-threaded (ST) workqueue：整個系統共用單一執行緒，所有 work item 須排隊依序執行，並行程度最低但資源消耗最小
- Multi-threaded (MT) workqueue：每個 CPU 配置一個 worker thread，允許工作在多核處理器上分散執行

然而，MT workqueue 的設計在較多處理器核數的系統上帶來嚴重的資源問題。例如，若建立 100 個 workqueue 且系統有 64 個 CPU，就會產生多達 6400 條 worker threads。由於 Linux PID 空間預設僅有 32K 個行程，一旦系統中啟動大量 MT workqueue，可能在開機過程中就將 PID 耗盡，造成重大問題。

此外，MT workqueue 雖然設計為多執行緒，但實際執行時，每個 worker thread 綁定單一 CPU，且各 CPU 間的 worker 無法共享工作項目，導致並行彈性有限。在某些負載情況下，甚至可能造成 worker threads 間等待資源、形成死結 (deadlock) 的狀況。

CMWQ 的出現與核心目標

為了解決上述限制，自 Linux v2.6.36 起導入 Concurrency Managed Workqueue (CMWQ) 機制。其關鍵理念是：

相容於過往的存取介面：保留原始 workqueue API 的使用方式，無須修改現有呼叫介面
統一資源管理：捨棄每個 workqueue 綁定一組 worker threads 的設計，改為所有 workqueue 共享一組 per-CPU worker pool
動態併發控制：CMWQ 內部根據工作負載與系統狀態，自動調整 worker threads 的並行程度與綁定，避免資源浪費。

架構說明

CMWQ 將工作項目的處理流程劃分為三個主要元素：

workqueue：供開發者提交 work item，表示邏輯上的工作佇列
worker pool：由核心維護的 worker thread 池，每個 CPU 有一組對應的 pool
worker：實際執行 work item 的執行緒，數量依負載動態調整

以下是架構圖，說明各元件間的關係：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

worker pool 管理多個 worker threads
workqueue 負責連接所有已提交的 work，形成佇列。

設計方式

在 CMWQ 架構中，每段要延後或非同步執行的處理流程會被歸類為一個工作項目 (work item)，其資料結構為 struct work_struct。該結構的定義如下：

typedef void (*work_func_t)(struct work_struct *work);

struct work_struct {
    atomic_long_t data;
    struct list_head entry;
    work_func_t func;
#ifdef CONFIG_LOCKDEP
    struct lockdep_map lockdep_map;
#endif
};

work_struct 中的 func 成員是一個函式指標，用來指定當此工作項目被執行時所要呼叫的函式。當 Linux 裝置驅動或子系統希望以非同步方式處理某項任務時，會建立一個 work_struct，設定其 func 為目標函式，並將此工作項目加入至 workqueue。

worker thread 的職責即為從佇列中取出 work item，並執行其 func。若佇列為空，worker thread 則會進入 idle 狀態。worker thread 由上層的 worker pool 所管理，worker pool 是 CMWQ 的主體資源管理的單位。

Worker Pool 架構

在 CMWQ 中，每個 CPU 會對應 2 個 worker pool：

負責處理一般優先權的 work item
處理高優先權的 work item

此外，系統中還會存在多個非綁定 (unbound) 的 worker pool，用來執行未限制於特定 CPU 的工作，這些 pool 的數量可依負載動態調整。

使用者透過 workqueue API 提交工作項目時，可指定其執行屬性，包括：

是否綁定 CPU (CPU locality)
是否需要高優先權執行
是否允許並行等級自動調整

這些屬性將決定該工作項目被分派至哪個 worker pool 中處理。

CPU 綁定與排程機制

對於綁定特定 CPU 的 worker pool，其與該 CPU 的排程器緊密整合。當任一 worker thread 被喚醒或進入休眠，系統會通知對應的 worker pool，使其能即時調整 worker 使用情況。

整體設計遵循「以最少資源維持最大效率」原則：
只要某 CPU 上有任何 runnable 的 worker thread，系統就暫不啟動新 worker；只有當該 CPU 上最後一個正在執行的 worker 進入睡眠，且仍有待處理的工作項目時，才會新啟一條 worker thread，以避免空轉與處理延遲。

此外，除了基本的記憶體配置與 kthread 結構，idle 狀態下的 worker thread 並不會額外耗用系統資源。因此，CMWQ 通常會保留一條 idle 的 worker thread，以利快速回應突如其來的工作項目。

Worker Pool 類型說明

Bound 類型 (綁定 CPU)
每個 CPU 擁有 2 組 worker pool：一組處理高優先權任務，另一組處理一般任務。此類 pool 僅允許工作在指定 CPU 上執行，適用於需要考慮 CPU 資源使用、cache locality 的情境
Unbound 類型 (不綁定 CPU)
適用於不需綁定 CPU 的一般性背景任務。其內部維護一組共享的 thread pool，根據實際負載動態建立與調整 worker thread 的數量。當使用者建立 unbound workqueue 並指定相關屬性時，系統會自動對應建立合適的 worker pool

當使用 unbound workqueue 時，開發者可透過 alloc_workqueue() 等 API 指定多項屬性 (例如最大並行數量、是否使用高優先權、是否支援 NUMA 等) ，CMWQ 將據此配置對應的 worker pool 並管理其排程策略。

若希望綁定 CPU 的 workqueue 也具備類似調整彈性，可設定特定旗標來略過核心對並行程度的內部控制，將資源管理的主導權交還給開發者。

CMWQ 的優勢

與 worker‑pool 脫鉤
workqueue 與底層 worker‑pool 已經脫鉤，使用者只需把 work item 加入佇列，無須關心如何配置 worker。核心會依 workqueue 旗標 (如 CPU 綁定、優先順序等) 自動安排 worker 並在適當時機切換與重用，降低 idle worker 數量並提升系統使用率。
阻塞偵測與動態增援
當某工作項目長時間佔用占用資源或發生阻塞時，CMWQ 會動態產生額外 worker thread，並分派至其他 CPU 處理，既避免過多執行緒，也防止整佇列卡住
彈性並行排程
所有 workqueue 共享同一組 worker‑pool，核心可根據任務優先級即時調整執行順序，讓不同任務在整體系統中維持最佳並行度

將 `create_workqueue` 改為 `alloc_workqueue`

2010 年的 commit d320c03 引入 alloc_workqueue() 以取代傳統 create_workqueue()：

Now that workqueue is more featureful, there should be a public workqueue creation function which takes parameters to control them. Rename __create_workqueue() to alloc_workqueue() and make 0 max_active mean WQ_DFL_ACTIVE. In the long run, all create_workqueue_*() will be converted over to alloc_workqueue().
(隨著 workqueue 功能增強，將 __create_workqueue() 更名為 alloc_workqueue()，並將 max_active = 0 視為 WQ_DFL_ACTIVE。最終將所有 create_workqueue_*() 轉移到 alloc_workqueue())

實際修改：

#define create_workqueue(name)                  \
-   __create_workqueue((name), WQ_RESCUER, 1)
+   alloc_workqueue((name), WQ_RESCUER, 1)

早期為了加入即時 (real‑time) 功能，另一則 commit 0d557dc 需修改 __create_workqueue 巨集並同步調整所有呼叫點，維護成本高昂：

-#define __create_workqueue(name, singlethread, freezeable)   \
+#define __create_workqueue(name, singlethread, freezeable, rt)   \

-#define create_workqueue(name) __create_workqueue((name), 0, 0)
+#define create_workqueue(name) __create_workqueue((name), 0, 0, 0)

改用 alloc_workqueue() 後，新增功能僅需透過旗標與參數即可，無需大量重寫巨集。例如 workqueue: remove WQ_SINGLE_CPU and use WQ_UNBOUND instead

-   WQ_SINGLE_CPU       = 1 << 1, /* only single cpu at a time */
+   WQ_UNBOUND          = 1 << 1, /* not bound to any cpu */
-   WQ_UNBOUND          = 1 << 6, /* not bound to any cpu */

透過旗標調整即可讓原本限於單一 CPU 的工作轉為不綁定 CPU，由核心自動管理並行度，完全符合 CMWQ「與資源管理脫鉤」的設計理念。

kthread 版與 CMWQ 版 kecho 執行差異

根據 kecho pull request #1 的說明，採用 CMWQ 的實作因具備較佳 locality 與預先建立的執行緒，使伺服器反應時間優於 kthread 為基礎的實作。我們基於 commit 7038c2 修正問題，重寫出 kthread‑based kecho，並與現行 CMWQ 版進行比較。

測試結果

kthread 為基礎的實作
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
CMWQ 為基礎的實作
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →

二者差距顯著，其中 kthread 為基礎的實作在接收 client 連線後才開始建立 kthread，因而額外耗時；CMWQ 為基礎的實作透過 thread pool 持續保留空閒 worker，work item 進入佇列後即可指派至可用執行緒，無須再建立 kthread。此差異在大量連線湧入時尤為明顯，顯示 CMWQ 方案於延遲與吞吐量方面更具優勢。

測量 kthread 建立成本

kecho pull request #1 提到 kthread-based 的 kecho 在回應時間上有很大的比例是受到 kthread 建立的成本影響，為瞭解其實際造成影響的比例，利用 eBPF 來測量建立 kthread_run 的時間成本。

載入 khttpd 核心模組後，利用以下命令觀察支援 kprobe 監聽的 event

$ sudo cat /sys/kernel/debug/tracing/available_filter_functions | grep khttpd

輸出應該可見 http_server_worker 和 http_server_daemon ，撰寫以下 python 程式，藉由 bcc 套件來使用 bpf 功能。

from bcc import BPF
code = """
#include <uapi/linux/ptrace.h>

BPF_HASH(start, u64);

int probe_handler(struct pt_regs *ctx)
{
	u64 ts = bpf_ktime_get_ns();
	bpf_trace_printk("in %llu\\n",ts);
	return 0;
}

int end_function(struct pt_regs *ctx)
{
	u64 ts = bpf_ktime_get_ns();
	bpf_trace_printk("out %llu\\n",ts);
	return 0;
}
"""

b = BPF(text = code)
b.attach_kprobe(event = 'http_server_worker', fn_name = 'probe_handler')
b.attach_kretprobe(event = 'http_server_worker', fn_name = 'end_function')

while True:
	try:
		res = b.trace_fields()
	except ValueError:
		continue
	print(res[5].decode("UTF-8"))

準備以下 wrapper function：

int my_thread_run(void *arg)
{
    struct task_struct *worker = kthread_run(http_server_worker, arg, KBUILD_MODNAME);
    if (IS_ERR(worker)) {
        pr_info("can't create more worker process\n");
    }

    char *buf;
    buf = kzalloc(1, GFP_KERNEL);
    if (!buf) {
        pr_err("can't allocate memory!\n");
        return -1;
    }

    kfree(buf);

    return 0;
}

測試的 BPF 程式與 python 程式如下:

from bcc import BPF
code = """
#include <uapi/linux/ptrace.h>

BPF_HASH(start, u64);

int kprobe__my_thread_run(struct pt_regs *ctx)
{
    u64 ts, key = 0;
	ts = bpf_ktime_get_ns();
	start.update(&key, &ts);
    return 0;
}

int kretprobe__my_thread_run(struct pt_regs *ctx)
{
    u64 key = 0;
    u64 *ts = start.lookup(&key);
	u64 end_ts = bpf_ktime_get_ns();
	if (ts != NULL) {
        u64 delta = end_ts - *ts;
		bpf_trace_printk("%llu\\n", delta);
		start.delete(&key);
    }
	
	start.update(&key, &end_ts);
    return 0;
}
"""

b = BPF(text = code)

with open('kthread_run_cost.txt', 'w') as f:
    i = 0
    while True:
        try:
            (task, pid, cpu, flags, ts, msg) = b.trace_fields()
            f.write(str(i))
            f.write(' ')
            f.write(msg.decode("UTF-8"))
            f.write('\n')
            i += 1
        except ValueError:
            continue

利用 ./htstress -n 100000 -c 1 -t 4 http://localhost:8081/ 對 khttpd 發送 100000 次 request 並利用上述測試程式監聽並將實驗結果製圖如下

可見多數時 kthread_run 的執行成本都分布在 500000 ns 以下，但當請求的數目接近 100000 時，就會出現部分 kthread_run 執行成本甚至超過 1500000 ns 的情況。

commit 7d95c8a

關於 kthread_run() 此巨集的定義可以在 include/linux/kthread.h 找到，主要作為 kthread_create() 的 wrapper。

引入 CMWQ 到 `khttpd`

在 kecho 的實作中，為統一管理 work，所有 work 皆加入鏈結串列。首先於 http_server.h 新增：

struct httpd_service {
    bool is_stopped;          /* 是否收到終止訊號 */
    struct list_head head;    /* 串列首節點 */
};
extern struct httpd_service daemon_list;

接著擴充 struct http_request，加入串列節點與 work 物件：

struct http_request {
    struct socket *socket;
    enum http_method method;
    char request_url[128];
    int complete;
+   struct list_head node;         /* 串列節點 */
+   struct work_struct khttpd_work;/* work 本體 */
};

整體流程：建立 CMWQ

\to

連線建立後產生 work

\to

workqueue 執行

\to

釋放資源。

在模組載入函式 khttpd_init 中呼叫 alloc_workqueue 建立 CMWQ：

khttpd_wq = alloc_workqueue(MODULE_NAME, 0, 0);

若預期長時間互動 (例如 telnet)，旗標可設 WQ_UNBOUND；短連線則維持 0 即可。實驗結果顯示 WQ_UNBOUND 在部分情況延遲較高，甚至曾導致測試機當機，推測與 work 延遲及排程負荷有關。

當 server 與 client 完成 TCP 的三方交握後，呼叫 create_work 產生工作項目：

static struct work_struct *create_work(struct socket *sk)
{
    struct http_request *work = kmalloc(sizeof(*work), GFP_KERNEL);
    if (!work)
        return NULL;

    work->socket = sk;
    INIT_WORK(&work->khttpd_work, http_server_worker); /* 指定執行函式 */
    list_add(&work->node, &daemon_list.head);          /* 加入鏈結串列 */

    return &work->khttpd_work;
}

模組卸載時走訪鏈結串列並依序釋放：

static void free_work(void)
{
    struct http_request *tar, *tmp;

    list_for_each_entry_safe(tar, tmp, &daemon_list.head, node) {
        kernel_sock_shutdown(tar->socket, SHUT_RDWR);
        flush_work(&tar->khttpd_work);
        sock_release(tar->socket);
        kfree(tar);
    }
}

整合 CMWQ 後，worker 執行緒預先存在且可重複使用，連線進來時只需提交 work；相比動態建立 kthread，能顯著降低建立成本並提升高並行負載下的效能。

使用命令 ./htstress http://localhost:8081 -t 3 -c 20 -n 200000 測試，以下為執行結果

requests:      200000
good requests: 200000 [100%]
bad requests:  0 [0%]
socker errors: 0 [0%]
seconds:       3.861
requests/sec:  51801.192

可見整個伺服器的吞吐量 (throughput) 大幅成長：

原本的實作	新增 CMWQ
30274.801	51801.192

實作 directory listing 功能

實作 directory listing 前，應當理解網頁伺服器在處理由目錄對應的 URL 時常見的幾個功能：

當請求目標為目錄而非檔案，伺服器通常嘗試：
1. 傳回預設首頁 (例如 index.html)。若無此檔，繼續以下
2. 動態產生一份目錄內容清單並以 HTML 格式回應，方便使用者瀏覽及下載
產生清單時，伺服器會列出檔案名稱、檔案大小、最後修改時間，並將名稱包成超連結，讓使用者點擊後可直接擷取檔案。
為避免安全風險，伺服器往往還需：
- 過濾.和 .. 等路徑穿越字串
- 隱藏系統保留或不想揭露的檔案
- 依瀏覽器語系加上適當的字元編碼宣告

在 khttpd 中實作此功能時，首先是取得給定目錄下的檔案名稱，並產生對應的 HTML。可新增 handle_directory 函式，並允許瀏覽器端顯示目錄清單，使用者點選檔名便可下載。若日後需加入排序、分頁或檔案圖示，只要在 handle_directory 內延伸對應邏輯即可。

commit 8614cb6







































static bool handle_directory(struct http_request *request)
{
    struct file *fp;
    char buf[SEND_BUFFER_SIZE] = {0};

    request->dir_context.actor = tracedir;
    if (request->method != HTTP_GET) {
        snprintf(buf, SEND_BUFFER_SIZE,
                 "HTTP/1.1 501 Not Implemented\r\n%s%s%s%s",
                 "Content-Type: text/plain\r\n", "Content-Length: 19\r\n",
                 "Connection: Close\r\n", "501 Not Implemented\r\n");
        http_server_send(request->socket, buf, strlen(buf));
        return false;
    }

    snprintf(buf, SEND_BUFFER_SIZE, "HTTP/1.1 200 OK\r\n%s%s%s",
             "Connection: Keep-Alive\r\n", "Content-Type: text/html\r\n",
             "Keep-Alive: timeout=5, max=1000\r\n\r\n");
    http_server_send(request->socket, buf, strlen(buf));


    snprintf(buf, SEND_BUFFER_SIZE, "%s%s%s%s", "<html><head><style>\r\n",
             "body{font-family: monospace; font-size: 15px;}\r\n",
             "td {padding: 1.5px 6px;}\r\n",
             "</style></head><body><table>\r\n");
    http_server_send(request->socket, buf, strlen(buf));

    fp = filp_open("/home/benson/khttpd/", O_RDONLY | O_DIRECTORY, 0);
    if (IS_ERR(fp)) {
        pr_info("Open file failed");
        return false;
    }

    iterate_dir(fp, &request->dir_context);
    snprintf(buf, SEND_BUFFER_SIZE, "</table></body></html>\r\n");
    http_server_send(request->socket, buf, strlen(buf));
    filp_close(fp, NULL);
    return true;
}

函式 handle_directory 執行流程如下：

檢查 client 是否送出 GET 請求，並回傳對應 HTTP 標頭 (第 7–19 行)
開啟目前目錄，透過 iterate_dir 走訪其中所有項目 (第 28–34 行)
完成後關閉連線並釋放資源

iterate_dir 於走訪過程中會呼叫 tracedir 處理各項目，亦即每列出一個檔案或子目錄都會觸發 tracedir。以下為 tracedir 實作：

// callback for 'iterate_dir', trace entry.
static int tracedir(struct dir_context *dir_context,
                    const char *name,
                    int namelen,
                    loff_t offset,
                    u64 ino,
                    unsigned int d_type)
{
    if (strcmp(name, ".") && strcmp(name, "..")) {
        struct http_request *request =
            container_of(dir_context, struct http_request, dir_context);
        char buf[SEND_BUFFER_SIZE] = {0};

        snprintf(buf, SEND_BUFFER_SIZE,
                 "<tr><td><a href=\"%s\">%s</a></td></tr>\r\n", name, name);
        http_server_send(request->socket, buf, strlen(buf));
    }
    return 0;
}

tracedir 逐項走訪目錄內容，每走訪一項便將對應資料立即傳送至 client。函式原型固定，卻仍需存取 socket 才能回傳資料，因此在設計上把 dir_context 嵌入 http_request。呼叫時透過巨集 container_of 先由 dir_context 推回外層 http_request，再取得內含的 socket。如此便無須額外傳遞 socket 指標，同時保持 tracedir 介面簡潔。

struct http_request {
    struct socket *socket;
    enum http_method method;
    char request_url[128];
    int complete;
+   struct dir_context dir_context;
    struct list_head node;
    struct work_struct khttpd_work;
};

最後展現目前的結果 (節錄部份)

取得現行目錄

以下示範取得目前工作目錄的方法，相關函式位於 fs/d_path.c 與 fs/namei.c。

struct path pwd;
char *cwd;
char current_path[100] = {0};

pwd = current->fs->pwd;
path_get(&pwd);
cwd = d_path(&pwd, current_path, sizeof(current_path));
pr_info("path = %s\n", cwd);

將模組載入後：

$ sudo insmod khttpd.ko

以瀏覽器存取時，pr_info 只印出 /，顯示目錄未解析為絕對路徑。欲改用 d_absolute_path，但該函式未以 EXPORT_SYMBOL 對外揭露，因此無法直接在外部模組呼叫。

改採模組參數方式：新增 WWWROOT，於載入時指定伺服器根目錄。

#define PATH_SIZE 100
static char WWWROOT[PATH_SIZE];
module_param_string(WWWROOT, WWWROOT, PATH_SIZE, 0);

為便於跨檔案使用，在 httpd_service 增添 dir_path 成員：

struct httpd_service {
    bool is_stopped;
+   char *dir_path;          /* 伺服器根目錄 */
    struct list_head head;
};

於 khttpd_init 判定 WWWROOT 是否為空字串，若空則設為預設 /，並存入 daemon_list.dir_path。

if (!*WWWROOT)
    WWWROOT[0] = '/';
daemon_list.dir_path = WWWROOT;

載入模組時便可選擇根目錄：

sudo insmod khttpd.ko # 使用預設 /
sudo insmod khttpd.ko WWWROOT="/home/user/khttpd" # 指定目錄

此作法避開無法呼叫 d_absolute_path 的限制，並讓伺服器根目錄在載入階段即可配置。

讀取檔案資料

讀取檔案前須先取得檔案屬性，例如檔案大小與類型。Linux 核心以 struct inode (定義於 include/linux/fs.h) 管理這些屬性，其中常用成員有：

i_mode 指出檔案類型與權限
i_size 紀錄檔案大小 (位元組)

掌握這二個欄位後，即可判定檔案是否為一般檔案、目錄或裝置節點，並依 i_size 配置適當緩衝區，再讀取實際內容。

/*
 * Keep mostly read-only and often accessed (especially for
 * the RCU path lookup and 'stat' data) fields at the beginning
 * of the 'struct inode'
 */
struct inode {
	umode_t			i_mode;
	...
	loff_t			i_size;
	...
}

檔案類型一樣位於 include/linux/fs.h ，可見不同類型的檔案有不同的數值:

/* these are defined by POSIX and also present in glibc's dirent.h */
#define DT_UNKNOWN  0
#define DT_FIFO     1
#define DT_CHR      2
#define DT_DIR      4
#define DT_BLK      6
#define DT_REG      8
#define DT_LNK      10
#define DT_SOCK     12
#define DT_WHT      14

判斷檔案類型時，可參考 include/uapi/linux/stat.h 中定義的巨集。常用者包括：

#define S_ISLNK(m)	(((m) & S_IFMT) == S_IFLNK)
#define S_ISREG(m)	(((m) & S_IFMT) == S_IFREG)
#define S_ISDIR(m)	(((m) & S_IFMT) == S_IFDIR)
#define S_ISCHR(m)	(((m) & S_IFMT) == S_IFCHR)
#define S_ISBLK(m)	(((m) & S_IFMT) == S_IFBLK)
#define S_ISFIFO(m)	(((m) & S_IFMT) == S_IFIFO)
#define S_ISSOCK(m)	(((m) & S_IFMT) == S_IFSOCK)

S_ISDIR 檢查 inode 的 i_mode 欄位是否對應目錄，S_ISREG 則確認是否為一般檔案。透過這兩個巨集即可快速分流後續處理邏輯。

接著開始修改程式，完整修改位於 Add the function of read file 及 Fix bug on reading file in deeper directory ，主要修改函式 handle_directory


















































static bool handle_directory(struct http_request *request)
{
    struct file *fp;
    char pwd[BUFFER_SIZE] = {0};

    ...

    catstr(pwd, daemon_list.dir_path, request->request_url);
    fp = filp_open(pwd, O_RDONLY, 0);

    if (IS_ERR(fp)) {
        send_http_header(request->socket, HTTP_STATUS_NOT_FOUND,
                         http_status_str(HTTP_STATUS_NOT_FOUND), "text/plain",
                         13, "Close");
        send_http_content(request->socket, "404 Not Found");
        return false;
    }

    if (S_ISDIR(fp->f_inode->i_mode)) {
        char buf[SEND_BUFFER_SIZE] = {0};
        snprintf(buf, SEND_BUFFER_SIZE, "HTTP/1.1 200 OK\r\n%s%s%s",
                 "Connection: Keep-Alive\r\n", "Content-Type: text/html\r\n",
                 "Keep-Alive: timeout=5, max=1000\r\n\r\n");
        http_server_send(request->socket, buf, strlen(buf));

        snprintf(buf, SEND_BUFFER_SIZE, "%s%s%s%s", "<html><head><style>\r\n",
                 "body{font-family: monospace; font-size: 15px;}\r\n",
                 "td {padding: 1.5px 6px;}\r\n",
                 "</style></head><body><table>\r\n");
        http_server_send(request->socket, buf, strlen(buf));

        iterate_dir(fp, &request->dir_context);

        snprintf(buf, SEND_BUFFER_SIZE, "</table></body></html>\r\n");
        http_server_send(request->socket, buf, strlen(buf));
        kernel_sock_shutdown(request->socket, SHUT_RDWR);

    } else if (S_ISREG(fp->f_inode->i_mode)) {
        char *read_data = kmalloc(fp->f_inode->i_size, GFP_KERNEL);
        int ret = read_file(fp, read_data);

        send_http_header(request->socket, HTTP_STATUS_OK,
                         http_status_str(HTTP_STATUS_OK), "text/plain", ret,
                         "Close");
        http_server_send(request->socket, read_data, ret);
        kfree(read_data);
    }
    filp_close(fp, NULL);
    return true;
}

修改後的函式 handle_directory 做了以下幾件事

第 8 行使用函式 catstr ，將 WWWROOT 的路徑及 client 的要求接在一起，並且輸出到 pwd，再由函式 filp_open 打開檔案
第 11 行表示如果開檔失敗，則回傳 NOT FOUND 訊息給 client
第 19 行表示如果為目錄，則將整個目錄擁有的檔案名稱傳送給 client
第 38 行表示如果為一般文件，則直接讀取檔案資料並且送給 client

接著稍微修改前面的實作，讓伺服器可以處理 ".." 的要求，完整修改參考 Consider request ".." to go back previous page ，以下節錄主要的修改

// callback for 'iterate_dir', trace entry.
static int tracedir(struct dir_context *dir_context,
                    const char *name,
                    int namelen,
                    loff_t offset,
                    u64 ino,
                    unsigned int d_type)
{
-   if (strcmp(name, ".") && strcmp(name, "..")) {
+   if (strcmp(name, ".")) {
        struct http_request *request =
            container_of(dir_context, struct http_request, dir_context);
        char buf[SEND_BUFFER_SIZE] = {0};
-       char *url =
-           !strcmp(request->request_url, "/") ? "" : request->request_url;

        SEND_HTTP_MSG(request->socket, buf,
                      "%lx\r\n<tr><td><a href=\"%s/%s\">%s</a></td></tr>\r\n",
-                     34 + strlen(url) + (namelen << 1), url, name, name);
+                     34 + strlen(request->request_url) + (namelen << 1),
+                     request->request_url, name, name);
    }
    return 0;
}

static int http_parser_callback_request_url(http_parser *parser,
                                            const char *p,
                                            size_t len)
{
    struct http_request *request = parser->data;
+   // if requst is "..", remove last character
+   if (p[len - 1] == '/')
+       len--;
    strncat(request->request_url, p, len);
    return 0;
}

函式 tracedir 主要只是移除多餘的程式碼，而函式 http_parser_callback_request_url 因進入到多層目錄後會回不去原本的目錄而有的改動。

考慮以下：假設現行目錄為 /ab/cd 並且送出 .. ，原來的時候會產生的結果為 /ab/ ，接著再送出一次 .. 會產生的結果仍然為 /ab/ ，表示進到二層以上的目錄後會回不到更早的目錄。

為了解決這樣的問題才會有以上的更動，如果路徑的最後一個字元為 '/' ，只要將其移除即可，用一樣的例結果會變成 /ab/cd

\to

/ab

\to

(空字串)

使用 Chunked transfer encoding 送出目錄資料

之前的實作由於每次傳送目錄資料時，不知總資料大小，因此都是送完資料後直接關閉連線，而在 HTTP 1.1 中提供了 Chunked encoding 的方法，可以將資料分成一個個的 chunk 並且分批發送，如此一來可以避免要在 HTTP header 中傳送 Content-Length: xx

參考 Transfer-Encoding: Chunked encoding 並由以下的範例可以得到幾個資訊

每次傳送資料前都要先送出資料的長度
資料的長度是 16 進位表示
資料長度和資料由 \r\n 隔開
要中斷資料傳送只要送出長度為 0 的資料即可

HTTP/1.1 200 OK
Content-Type: text/plain
Transfer-Encoding: chunked

7\r\n
Mozilla\r\n
9\r\n
Developer\r\n
7\r\n
Network\r\n
0\r\n
\r\n

在正式修改程式之前，之前撰寫的函式 send_http_header 和 send_http_content 實在是太冗長，因此將二者重新修改並且寫的更有彈性，新增巨集函式 SEND_HTTP_MSG 如下

#define SEND_HTTP_MSG(socket, buf, format, ...)           \
    snprintf(buf, SEND_BUFFER_SIZE, format, __VA_ARGS__); \
    http_server_send(socket, buf, strlen(buf))

如此一來，輸入的資料可以讓使用者任意送出，程式碼也變得更簡潔

以下主要列出使用 chunked encoding 的部份，分別是函式 handle_directory 及 tracedir

// callback for 'iterate_dir', trace entry.
static int tracedir(struct dir_context *dir_context,
                    const char *name,
                    int namelen,
                    loff_t offset,
                    u64 ino,
                    unsigned int d_type)
{
    if (strcmp(name, ".") && strcmp(name, "..")) {
        struct http_request *request =
            container_of(dir_context, struct http_request, dir_context);
        char buf[SEND_BUFFER_SIZE] = {0};
        char *url =
            !strcmp(request->request_url, "/") ? "" : request->request_url;

        SEND_HTTP_MSG(request->socket, buf,
                      "%lx\r\n<tr><td><a href=\"%s/%s\">%s</a></td></tr>\r\n",
                      34 + strlen(url) + (namelen << 1), url, name, name);
    }
    return 0;
}

static bool handle_directory(struct http_request *request)
{
	...
	if (S_ISDIR(fp->f_inode->i_mode)) {
		SEND_HTTP_MSG(request->socket, buf, "%s%s%s", "HTTP/1.1 200 OK\r\n",
		              "Content-Type: text/html\r\n",
		              "Transfer-Encoding: chunked\r\n\r\n");
		SEND_HTTP_MSG(
		    request->socket, buf, "7B\r\n%s%s%s%s", "<html><head><style>\r\n",
		    "body{font-family: monospace; font-size: 15px;}\r\n",
		    "td {padding: 1.5px 6px;}\r\n", "</style></head><body><table>\r\n");

		iterate_dir(fp, &request->dir_context);

		SEND_HTTP_MSG(request->socket, buf, "%s",
		              "16\r\n</table></body></html>\r\n");
		SEND_HTTP_MSG(request->socket, buf, "%s", "0\r\n\r\n");
	}
	...
}

主要修改的部份在於發送 HTTP header 時，需要新增 Transfer-Encoding: chunked ，另外每次傳送資料時後要先送出該資料的長度，最後要記得送出長度為 0 的資料

經過這樣的修改後，目前的伺服器可以送出不固定大小的資料

最後展示執行結果

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

使用 MIME 處理不同類型的檔案

參考 MIME 類別可以初步了解 MIME。MIME 是種表示檔案或各式位元組的標準，並定義於 RFC 6838 裡，如果要使用 MIME 的功能，則要在伺服器回應的 HTTP header 的項目 Content-Type 提供正確的類型

至於要回應什麼要的類型，可參考 Common MIME types ，裡頭提供了不同的副檔名應該要回應的型態

如此一來可以開始修改程式碼，完整修改參考 Add MIME to deal with different kind of files ，新增檔案 mime_type.h 裡面儲存常見的 MIME 類型

新增函式 get_mime_str ，功能為根據要求的檔案找到對應的回應訊息

// return mime type string
const char *get_mime_str(char *request_url)
{
    char *request_type = strchr(request_url, '.');
    int index = 0;
    if (!request_type)
        return "text/plain";

    while (mime_types[index].type) {
        if (!strcmp(mime_types[index].type, request_type))
            return mime_types[index].string;
        index++;
    }
    return "text/plain";
}

接著修改函式 handle_directory 裡處理一般檔案的部份，主要就是利用函式 get_mime_str 取得對應的回應訊息

static bool handle_directory(struct http_request *request)
{
	...
	else if (S_ISREG(fp->f_inode->i_mode)) {
		char *read_data = kmalloc(fp->f_inode->i_size, GFP_KERNEL);
		int ret = read_file(fp, read_data);

		SEND_HTTP_MSG(
			request->socket, buf, "%s%s%s%s%d%s", "HTTP/1.1 200 OK\r\n",
+			"Content-Type: ", get_mime_str(request->request_url),
			"\r\nContent-Length: ", ret, "\r\nConnection: Close\r\n\r\n");
		http_server_send(request->socket, read_data, ret);
		kfree(read_data);
	}
	...
}

卸載模組時產生錯誤

在前述實作發現問題：只要有對伺服器做請求後，在卸載模組時會產生以下的錯誤訊息

[ 3721.905941] ------------[ cut here ]------------
[ 3721.905958] kernel BUG at fs/inode.c:1676!
[ 3721.905974] invalid opcode: 0000 [#6] SMP PTI
[ 3721.905987] CPU: 0 PID: 10434 Comm: khttpd Tainted: G      D W  OE     5.13.0-41-generic #46~20.04.1-Ubuntu
[ 3721.905999] Hardware name: Acer Aspire F5-573G/Captain_SK  , BIOS V1.18 10/21/2016
[ 3721.906005] RIP: 0010:iput+0x1ac/0x200
[ 3721.906022] Code: 00 0f 1f 40 00 4c 89 e7 e8 01 fb ff ff
                     5b 41 5c 41 5d 5d c3 c3 85 d2 74 a4 49
                     83 bc 24 e0 00 00 00 00 0f 85 3a ff ff
                     ff eb 93 <0f> 0b 0f 0b e9 0e ff ff ff
                     a9 b7 08 00 00 75 17 41 8b 84 24 58 01
...

首先查閱 fs/inode.c 的第 1676 行，參考 fs/inode.c 可以找到對應的函式 iput

















void iput(struct inode *inode)
{
	if (!inode)
		return;
	BUG_ON(inode->i_state & I_CLEAR);
retry:
	if (atomic_dec_and_lock(&inode->i_count, &inode->i_lock)) {
		if (inode->i_nlink && (inode->i_state & I_DIRTY_TIME)) {
			atomic_inc(&inode->i_count);
			spin_unlock(&inode->i_lock);
			trace_writeback_lazytime_iput(inode);
			mark_inode_dirty_sync(inode);
			goto retry;
		}
		iput_final(inode);
	}
}

程式錯誤出現在上述函式第 5 行，初步研判與檔案系統操作相關。實測發現：伺服器收到請求後確實開啟並讀取檔案，但未立即關閉；執行緒停在 filp_close，需等到下一次請求才釋放檔案。相關程式片段如下：

static bool handle_directory(struct http_request *request, int keep_alive)
{
	...
	fp = filp_open(pwd, O_RDONLY, 0);
	...
	if (S_ISDIR(fp->f_inode->i_mode)) {
		...    
	} else if (S_ISREG(fp->f_inode->i_mode)) {
		...
		int ret = read_file(fp, read_data);
		...
	}
	filp_close(fp, NULL);
	return true;
}

當 client 在遠端關閉連線時，最後一次請求所開啟的檔案描述子仍未關閉；此時若直接卸載核心模組，便會觸發上述錯誤。

解法：為每個連線配置逾時 timer，伺服器可在時間到期主動關閉閒置連線並釋放相關資源。後續章節將說明具體實作步驟。

使用 Ftrace 觀察 kHTTPd

參考 Ftrace 及《Demystifying the Linux CPU Scheduler》第六章。

ftrace 是一個內建於 Linux 核心的動態追蹤工具，可用來追蹤函式、追蹤事件、計算 context switch 時間及中斷被關閉的時間點等等。

先確認目前的系統是否有 ftrace，輸入以下命令

cat /boot/config-`uname -r` | grep CONFIG_HAVE_FUNCTION_TRACER

期望輸出如下

CONFIG_HAVE_FUNCTION_TRACER=y

接著要怎麼使用 ftrace？可藉由寫入路徑 /sys/kernel/debug/tracing/ 內的檔案來設定 ftrace ，以下提供部份檔案，使用命令 sudo ls /sys/kernel/debug/tracing 查看

available_events            max_graph_depth   stack_max_size
available_filter_functions  options           stack_trace
available_tracers           per_cpu           stack_trace_filter
buffer_percent              printk_formats    synthetic_events
...

至於這些檔案負責什麼功能，以下列出實驗有使用到的設定，剩下可以從 Ftrace 找到說明

current_tracer: 設定或顯示目前使用的 tracers ，像是 function 、 function_graph 等等
tracing_on: 設定或顯示使用的 tracer 是否開啟寫入資料到 ring buffer 的功能，如果為 0 表示關閉，而 1 則表示開啟
trace: 儲存 tracer 所輸出的資料，換言之，就是紀錄整個追蹤所輸出的訊息
available_filter_functions: 列出 kernel 裡所有可以被追蹤的 kernel 函式
set_ftrace_filter: 指定要追蹤的函式，該函式一定要出現在 available_filter_functions 裡
set_graph_function: 指定要顯示呼叫關係的函數，顯示的資訊類似於程式碼的模樣，只是會將所有呼叫的函式都展開
max_graph_depth: function graph tracer 追蹤函式的最大深度

有了以上的知識，可開始追蹤 kHTTPd，這裡嘗試追蹤其中每個連線都會執行的函式 http_server_worker ，第一步是要掛載核心模組，且透過檔案 available_filter_functions 確定是否可以追蹤 khttpd 的函式，輸入命令 cat available_filter_functions | grep khttpd 查看，可見 kHTTPd 裡可被追蹤的所有函式:

parse_url_char [khttpd]
http_message_needs_eof.part.0 [khttpd]
http_message_needs_eof [khttpd]
http_should_keep_alive [khttpd]
http_parser_execute [khttpd]
http_method_str [khttpd]
http_status_str [khttpd]
http_parser_init [khttpd]
http_parser_settings_init [khttpd]
http_errno_name [khttpd]
http_errno_description [khttpd]
http_parser_url_init [khttpd]
...

接著建立 shell script 來追蹤函式 http_server_worker ，如下所示

#!/bin/bash
TRACE_DIR=/sys/kernel/debug/tracing

# clear
echo 0 > $TRACE_DIR/tracing_on
echo > $TRACE_DIR/set_graph_function
echo > $TRACE_DIR/set_ftrace_filter
echo nop > $TRACE_DIR/current_tracer

# setting
echo function_graph > $TRACE_DIR/current_tracer
echo 3 > $TRACE_DIR/max_graph_depth
echo http_server_worker > $TRACE_DIR/set_graph_function

# execute
echo 1 > $TRACE_DIR/tracing_on
./htstress localhost:8081 -n 2000
echo 0 > $TRACE_DIR/tracing_on

主要邏輯就是先清空 ftrace 的設定，接著設定函式 http_server_worker 為要追蹤的函式，最後在測試時開啟 tracer

執行 shell script 後，從 ftrace 的檔案 /sys/kernel/debug/tracing/trace 可以看到追蹤的輸出，以下節錄部份輸出

# tracer: function_graph
#
# CPU  DURATION                  FUNCTION CALLS
# |     |   |                     |   |   |   |
 0)               |  http_server_worker [khttpd]() {
 0)               |    kernel_sigaction() {
 0)   0.296 us    |      _raw_spin_lock_irq();
 0)   0.937 us    |    }
 0)   0.329 us    |    }
 0)               |    kmem_cache_alloc_trace() {
 0)   0.165 us    |      __cond_resched();
 0)   0.114 us    |      should_failslab();
 0)   0.913 us    |    }
 0)   0.111 us    |    http_parser_init [khttpd]();
 0)               |    http_add_timer [khttpd]() {
 0)   0.433 us    |      kmem_cache_alloc_trace();
 0)   0.174 us    |      ktime_get_ts64();
 0)   1.052 us    |    }
 0)               |    http_server_recv.constprop.0 [khttpd]() {
 0)   3.134 us    |      kernel_recvmsg();
 0)   3.367 us    |    }
 0)               |    kernel_sock_shutdown() {
 0) + 40.992 us   |      inet_shutdown();
 0) + 41.407 us   |    }
 0)   0.433 us    |    kfree();
 0) + 50.869 us   |  }

由上面的結果可以看到整個 http_server_worker 函式所花的時間以及內部函式所花的時間，有這樣的實驗可以開始分析造成 khttpd 效率低落的原因

找出 kHTTPd 的效能瓶頸

在尚未對原始程式碼進行任何修改前，可先透過以下指令設定核心的 ftrace 以啟用 function graph 模式：

$ echo function_graph | sudo tee /sys/kernel/tracing/current_tracer
$ echo display-graph | sudo tee -a /sys/kernel/tracing/trace_options
$ echo funcgraph-tail | sudo tee -a /sys/kernel/tracing/trace_options

接著，將 set_ftrace_filter 設定為只追蹤 khttpd 核心模組中的函式：

$ echo '*:mod:khttpd' | sudo tee /sys/kernel/tracing/set_ftrace_filter

透過 trace_pipe 觀察核心模組行為，並在另一個終端機輸入以下命令

$ curl -i http://localhost:8081/

觀察 trace_pipe 輸出

$ sudo cat /sys/kernel/tracing/trace_pipe 
 0)               |  http_server_worker [khttpd]() {
 0)   0.925 us    |    http_parser_init [khttpd]();
 0)   4.362 us    |    http_server_recv.constprop.0 [khttpd]();
 0)               |    http_parser_execute [khttpd]() {
 0)   0.361 us    |      http_parser_callback_message_begin [khttpd]();
 0)   1.129 us    |      parse_url_char [khttpd]();
 0)   0.453 us    |      http_parser_callback_request_url [khttpd]();
 0)   0.330 us    |      http_parser_callback_header_field [khttpd]();
 0)   0.275 us    |      http_parser_callback_header_value [khttpd]();
 0)   0.439 us    |      http_parser_callback_header_field [khttpd]();
 0)   0.261 us    |      http_parser_callback_header_value [khttpd]();
 0)   0.263 us    |      http_parser_callback_header_field [khttpd]();
 0)   0.274 us    |      http_parser_callback_header_value [khttpd]();
 0)   0.269 us    |      http_parser_callback_headers_complete [khttpd]();
 0)   0.368 us    |      http_message_needs_eof [khttpd]();
 0)   0.370 us    |      http_should_keep_alive [khttpd]();
 0)               |      http_parser_callback_message_complete [khttpd]() {
 0)   0.260 us    |        http_should_keep_alive [khttpd]();
 0) + 43.504 us   |        http_server_send.isra.0 [khttpd]();
 0) + 55.908 us   |      } /* http_parser_callback_message_complete [khttpd] */
 0) + 69.744 us   |    } /* http_parser_execute [khttpd] */
 0)   0.446 us    |    http_should_keep_alive [khttpd]();
 0)               |    http_server_recv.constprop.0 [khttpd]() {
 7) ! 116.629 us  |    } /* http_server_recv.constprop.0 [khttpd] */
 7) ! 259.895 us  |  } /* http_server_worker [khttpd] */

詳細欄位說明可參考 Function Graph Tracer，它能協助觀察各函式的呼叫順序與執行時間，進一步辨識瓶頸所在。

從追蹤結果可發現，幾個函式的執行時間明顯偏長，包括：

http_parser_execute()
http_parser_callback_message_complete()
http_server_send()
http_server_recv()

此外，函式結束時所執行的 CPU 和開始執行時的 CPU 不一致，顯示在執行期間可能發生過 context switch，表示該工作被中斷並重新排程。這類行為會對即時性造成影響，尤其在高並行環境下可能顯著降低整體吞吐量。若能降低這類 context switch 的發生頻率，將有助於提升 khttpd 處理請求的效率與穩定性。

為此，我們首先深入分析 http_parser_execute() 的內部實作。該函式採用狀態機模型，針對輸入資料 buf 進行逐字元處理，並依據目前的 parser->state (由 CURRENT_STATE() 巨集取出) 執行對應的解析邏輯。以一開始的 s_start_req 為例，parser 會先識別 HTTP 方法 (如 GET 或 POST) ，接著透過 UPDATE_STATE() 巨集進入下一個狀態，如 s_req_method，繼續處理 request-line 的其他部分。

這種逐字元的有限狀態機 (FSM) 雖然設計簡潔、具備良好可攜性，但在核心環境中處理封包時效率不彰。每個字元都會觸發一次狀態轉換與條件分支 (switch 或 if-else) ，導致頻繁跳躍與 cache miss，且難以批次處理。

改進方案：

以 token 爲單位進行解析
若以空白與 CRLF 分割封包後再處理，可大幅減少狀態轉換次數。例如 GET /index.html HTTP/1.1\r\n 可先以 strtok() 拆解為 method、path、version，再進行狀態變換。
使用預先比對的 method 對映表 (lookup table)
取代字元比對法 (如 strncmp(p, "GET", 3)) ，可用固定長度字串 hash 快速辨識常見 method (如 GET、POST、HEAD) 。
減少 memory barrier 或中斷禁止段的延遲貢獻
搭配 eBPF tracepoints 觀察 softirq 與 local_bh_disable() 的使用時間，有助了解是否為非同步通訊延遲來源。
排程行為分析
使用 perf sched latency 或 trace-cmd sched_switch 搭配 khttpd 專用 filter，觀察 worker thread 在 http_parser_execute() 或 http_server_send() 執行期間是否遭 preempt。必要時可透過 sched_setattr() 調高排程優先權或切換至 SCHED_FIFO/SCHED_RR 減少搶佔風險。

實作 content cache

以 Ftrace 分析函式執行時間，節錄部分 Ftrace 結果：










  0)               |      http_parser_callback_message_complete [khttpd]() {
  0)   0.310 us    |        http_should_keep_alive [khttpd]();
  0)               |        handle_directory [khttpd]() {
  0) + 28.890 us   |          filp_open();
  0) + 79.600 us   |          http_server_send.isra.0 [khttpd]();
  0) + 79.780 us   |          http_server_send.isra.0 [khttpd]();
  0) # 3295.400 us |          iterate_dir();                 ---> 時間異常的高
  0) + 47.380 us   |          http_server_send.isra.0 [khttpd]();
  0) + 53.270 us   |          http_server_send.isra.0 [khttpd]();
  0)   4.740 us    |          filp_close();

從左至右的每個資訊表示意思為：
0)：CPU 編號。
us：右方函式執行時間
xxx()：執行的函式
+, # 符號意思：+ 表示右方函式執行的時間，# 表示函式執行時間異常長。

觀察上方 ftrace 列出的每一個函式執行時間，可以發現到每一次客戶端要求某個目錄或檔案內容時都需要執行 iterate_dir 函式讀取目錄或檔案，這會導致吞吐量下降。上方 ftrace 結果中可以看到，第 473 行在走訪目錄需要花費大量的時間，如果短時間請求同一個 request_url 便需要花費大量的時間在相同的資訊上。為了能夠避免重複讀取相同的檔案資訊，這里可以實作一個 cache 儲存之前讀過的目錄或檔案把它們放在記憶體。一段時間內，若有相同的 request_url 請求就可以直接傳送已經儲存在記憶體的內容，減少走訪目錄讀取檔案資訊或是內容的時間、進而增加吞吐量。

為了將走訪目錄得到的資訊儲存起來，這裡的想法是建立一個 cache_content 的結構體在每次走放目錄下的檔案資訊時用鏈結串列串連需要的內容，每一個內容都是要傳送給客戶端的資訊。用鏈結串鏈串連內容的好處是既使目錄下的內容非常多也不需要擔心需要一次配置多大的記憶體空間，如果目錄下的內容非常少也不需要擔心浪費過多的記憶體空間。接著用一個 hash_table 儲存 request_url 和 cache_content 資訊，計算 request_url 對應到 hash_table 的位置將 cache_content 儲存起來。在每次客戶端傳送請求時會先檢查 hash_table 請求的網址有沒有暫存的資訊，如果有就從 hash_table 中取出資訊傳送給客戶端，如果沒有才重新走放指定的目錄得到所有資訊然後傳送給客戶端。

在這裡先定義我們需要的 content cache 結構體 cache_content，走訪目錄的每一個節點時都會將資訊儲存在結構體的 buf 中並且將 list_head 加入鏈結串列中。

struct cache_content {
    struct list_head cache;
    char buf[SEND_BUFFER_SIZE];
};

接著在 http_request 結構體中增加一個鏈結串列指標，儲存所有的目錄資訊。

struct http_request {
    struct list_head node;
    struct work_struct khttpd_work;
    void *timer_node;
+    struct list_head *cache_list;
};

接著便可以修改走訪目錄的程式，將 socket 要傳輸的內容、HTTP 標頭檔、HTML 標頭檔等資儲存在 cache_content 的 buf 裡接著加入至 http_request 的鏈結串列 cache_list。所有的要傳送給客戶端的資訊都加入至鏈結串列後，便可以將 cache_list 鏈結串列加入至雜湊表中提供下一次請求時查詢。

static bool tracedir(struct dir_context *dir_context, ...)
{
    ... 
    // create and add cache to cache_list
    struct cache_content *content =
        kmalloc(sizeof(struct cache_content), GFP_KERNEL);
    if (!content) {
        pr_err("can't allocate memory!\n");
        return false;
    }

    snprintf(content->buf, SEND_BUFFER_SIZE,
             "%lx\r\n<tr><td><a href=\"%s\">%s</a></td></tr>\r\n",
             34 + strlen(href_link) + strlen(name), href_link, name);
    add_to_list_tail(&content->cache, request->cache_list);
}

static bool handle_directory(struct http_request *request, int keep_alive)
{
    ...
    
    // url 判斷為目錄
    if (S_ISDIR(fp->f_inode->i_mode)) {
        
        ...
        
        // 初始化 cache_list 鏈結串列
        INIT_LIST_HEAD(head);
        request->cache_list = head;

        // add HTTP header to cache
        struct cache_content *content_header =
            kmalloc(sizeof(struct cache_content), GFP_KERNEL);
        snprintf(content_header->buf, SEND_BUFFER_SIZE, "%s%s%s%s",
                 "HTTP/1.1 200 OK\r\n", "Connection: Keep-Alive\r\n",
                 "Content-Type: text/html\r\n",
                 "Transfer-Encoding: chunked\r\n\r\n");
        add_to_list_tail(&content_header->cache, request->cache_list);
        
        // add HTML header to cache
        struct cache_content *content_html_head =
            kmalloc(sizeof(struct cache_content), GFP_KERNEL);
        snprintf(content_html_head->buf, SEND_BUFFER_SIZE, "7B\r\n%s%s%s%s",
                 "<html><head><style>\r\n",
                 "body{font-family: monospace; font-size: 15px;}\r\n",
                 "td {padding: 1.5px 6px;}\r\n",
                 "</style></head><body><table>\r\n");
        add_to_list_tail(&content_html_head->cache, request->cache_list);  
        ...
        // scan directory and add content to cache
        iterate_dir(fp, &request->dir_context);
        
        /// add linkedlist to hash table
        hash_insert(request->request_url, request->cache_list);    
        ...
    }
    ...
}

將 URL 與內容快取納入雜湊表管理

以下為加入雜湊表的實作：我們定義一個大小為

2^{8}

的雜湊表，並實作 hash_insert 函式，將指定的 URL 與對應的快取內容（以 cache_list 串列儲存）插入表中。

若該 URL 已存在於表內，則不重複插入，並釋放先前分配的記憶體。考量多執行緒情境可能同時有多個插入操作，插入過程中使用 spinlock 保護，確保資料一致性；若發現 URL 已存在於表中，則直接離開不做修改。

先定義一個 hash_content 結構，作為雜湊表的 entry：

head：指向該 URL 對應的快取內容（cache list)
request：對應的 URL 字串
node：用於鏈入 Linux 核心的 hash list
timer_node：配合 timeout 機制，用於後續釋放快取資源

該設計可加速 URL 查找與內容重複利用，亦方便搭配逾時機制自動清除過期資料。結構體定義如下：

struct hash_content {
    struct list_head *head;
    char *request;
    struct hlist_node node;
    void *timer_node;
};

以下程式實作將 URL 插入雜湊表的邏輯：

使用 jhash 函式計算 request_url 的雜湊值，結果儲存在 original_key 中
再透過取模運算，將 original_key 映射為 8 個位元 (即介於 0 到 255 間) 的索引 key，對應至雜湊表中的 bucket

DEFINE_HASHTABLE(ht, 8);
spinlock_t hash_lock;

void hash_insert(const char *request_url, struct list_head *head)
{
    // cal hash key
    u32 original_key = jhash(request_url, strlen(request_url), 0);
    u8 key = (u8) (original_key % 256);

    // init hash_content
    struct hash_content *content =
        kmalloc(sizeof(struct hash_content), GFP_KERNEL);
    content->head = head;
    content->request = kmalloc(strlen(request_url) + 1, GFP_KERNEL);
    memcpy(content->request, request_url, strlen(request_url) + 1);

    // add hash_content to the hash_table
    spin_lock(&hash_lock);
    struct hash_content *now = NULL;
    hash_for_each_possible_rcu(ht, now, node, key)
    {
        // 略過已經存在的 key
        char *now_request_url = now->request;
        if (strcmp(now_request_url, request_url) == 0) {
            pr_info("Key %s already exists in hash table\n", request_url);
            spin_unlock(&hash_lock);
            kfree(content->request);
            kfree(content);
            return;
        }
    }
    hash_add_rcu(ht, &content->node, key);
    spin_unlock(&hash_lock);
}

將 URL 插入雜湊表後，後續每次接收到相同 URL 的請求，只需查詢雜湊表是否已有對應快取。若存在，即可直接取出快取內容傳送給客戶端，無須重新走訪檔案系統，大幅降低存取延遲與系統負擔。

static bool handle_directory(struct http_request *request, int keep_alive)
{
    ...
        
    // check cache
    struct list_head *head = NULL;
    if (hash_check(request->request_url, &head)) {
        struct cache_content *now_content;
        list_for_each_entry (now_content, head, cache) {
            http_server_send(request->socket, now_content->buf,
                             strlen(now_content->buf));
        }
        filp_close(fp, NULL);
        return true;
    }
    
    ...
}

至此已完成將目錄內容與對應的 URL 儲存至雜湊表，目的是避免重複走訪目錄以查詢檔案資訊，藉此降低存取延遲。然而，實際效能評比後，發現成效不如預期，整體效能僅提升約 10%。

透過 ftrace 進一步分析後發現，瓶頸主要集中在 http_server_send 函式：該函式會逐一走訪 cache_list 鏈結串列中的所有節點，並將每個節點的 buf 內容個別傳送至 client。若串列有 n 個節點，就需執行 n 次 http_server_send，系統呼叫成本隨之累加，造成效能下降。

更佳作法是改用 scatter-gather I/O 技術，透過 iovec 結構將多個緩衝區整合成一個向量，再透過單一系統呼叫一次傳送所有內容至 client，不僅減少上下文切換次數，也可顯著提升吞吐效能。

測試結果：
之前:

$ ./htstress http://localhost:8081 -t 3 -c 20 -n 200000

requests/sec:  24318.492

之後:

$ ./htstress http://localhost:8081 -t 3 -c 20 -n 200000

requests/sec:  27590.404

以 ftace 觀察：

  4)               |        handle_directory [khttpd]() {
  4) + 28.440 us   |          filp_open();
  4) + 13.940 us   |          _printk();
  4)   1.200 us    |          hash_check [khttpd]();
  4) + 86.970 us   |          http_server_send.isra.0 [khttpd]();
 11) ! 128.340 us  |        }
 ...
  4) + 58.810 us   |          http_server_send.isra.0 [khttpd]();
  4) + 70.000 us   |          http_server_send.isra.0 [khttpd]();
  4) + 58.850 us   |          http_server_send.isra.0 [khttpd]();
  ...
  4) + 69.790 us   |          http_server_send.isra.0 [khttpd]();
  4) + 52.750 us   |          http_server_send.isra.0 [khttpd]();
  4) + 52.760 us   |          http_server_send.isra.0 [khttpd]();
  4)   4.560 us    |          filp_close();
  4) # 3542.000 us |        }
  4) # 3543.130 us |      }
  4) # 3551.010 us |    }

scatter-gather I/O 傳送資料

使用 scatter-gather I/O 一次讀取多個非連續記憶體區域傳送至客戶端，這樣的方式減少 socket 系統呼叫的開銷，增加效能和吞吐量，提高整體網頁伺服器的回應速度，增加約 85% 的吞吐量。

scatter-gather I/O 使用方式如下：

需要先建立 kvec 陣列儲存多個非連續記憶體空間
iov_base 指向非連續記憶體區域
iov_len 設定非連續記憶體內容的長度
接著使用 http_server_send2 裡的 kernel_sendmsg 一次性將收集到的非連續記憶體傳送到 socket。

commit 7d41618

void send_all_buffers(struct socket *sock, struct list_head *head)
{
    struct cache_content *now_content;
    struct kvec vec[MAX_KVEC];
    int vlen = 0;

    list_for_each_entry (now_content, head, cache) {
        if (vlen >= MAX_KVEC) {
            pr_err("Too many buffers to send in one go\n");
            break;
        }
        vec[vlen].iov_base = now_content->buf;
        vec[vlen].iov_len = strlen(now_content->buf);
        vlen++;
    }

    // 使用 http_server_send 一次性傳送所有緩衝區
    if (vlen > 0) {
        http_server_send2(sock, vec, vlen);
    }
}

結果比較

經改善後，可明顯觀察到使用內容快取前後的吞吐量變化：在並行數為 1 時，從每秒 2135 次提升至 10866 次；並行數為 20 時，則從 24318 次上升至 45093 次，效能提升符合預期。

這樣的結果是合理的，因為效能評比期間反覆存取同一個網址，且該內容已快取於記憶體中，無需再次走訪檔案系統，故能快速從快取中讀出並傳送給客戶端，大幅降低存取延遲。

引入 content cahce 前:

並行數量 = 1

$ ./htstress http://localhost:8081 -n 50000

requests:      50000
good requests: 50000 [100%]
bad requests:  0 [0%]
socket errors: 0 [0%]
seconds:       23.413
requests/sec:  2135.563

並行數量 = 20

$ ./htstress http://localhost:8081 -t 3 -c 20 -n 200000

good requests: 200000 [100%]
bad requests:  0 [0%]
socket errors: 0 [0%]
seconds:       8.224
requests/sec:  24318.492

引入 content cahce 後:

並行數量 = 1

$ ./htstress http://localhost:8081 -n 50000

requests:      50000
good requests: 50000 [100%]
bad requests:  0 [0%]
socket errors: 0 [0%]
seconds:       4.601
requests/sec:  10866.556

並行數量 = 20

$ ./htstress http://localhost:8081 -t 3 -c 20 -n 200000

requests:      200000
good requests: 200000 [100%]
bad requests:  0 [0%]
socket errors: 0 [0%]
seconds:       4.399
requests/sec:  45464.093

從下方 ftrace 輸出可以觀察到，一次就可將所有非連續記憶體內容傳給 client，減少傳輸開銷:

 10)               |      http_parser_callback_message_complete [khttpd]() {
 10)   0.310 us    |        http_should_keep_alive [khttpd]();
 10)               |        handle_directory [khttpd]() {
 10) + 27.350 us   |          filp_open();
 10)   0.780 us    |          hash_check [khttpd]();
 10) + 86.720 us   |          send_all_buffers [khttpd]();
 10)   1.940 us    |          filp_close();
 10) ! 118.410 us  |        }
 10) ! 119.550 us  |      }
 10) ! 125.590 us  |    }

支援 HTTP 壓縮

善用 Kernel Crypto API

支援 HTTP 壓縮的目的

目前已實作從指定目錄傳送檔案資訊、顯示檔案內容等功能，使用者點擊目錄中的超連結後，即可在網頁中瀏覽不同檔案的內容。然而，這些檔案多數為純文字格式，若能於伺服器端先行壓縮並再傳送至用戶端，便可有效降低資料傳輸量；當網頁需要顯示內容時，再由瀏覽器端進行解壓縮即可。

可善用 Linux 核心所提供的壓縮 API，將檔案內容經壓縮後透過 HTTP 回應傳送給客戶端，藉此達成減少網路傳輸負擔與提升效能的目的。

資料壓縮機制

預期支援常見的 HTTP 壓縮演算法，如 gzip 與 deflate。可透過查詢 /proc/crypto 來確認系統中目前支援的壓縮演算法；本例選用 deflate。

為了實作資料壓縮，可運用 Linux 核心所提供的壓縮 API，其中包含 crypto_alloc_comp 與 crypto_comp_compress 函式：

crypto_alloc_comp：用來建立壓縮操作的處理實體，並指定欲使用的壓縮演算法
crypto_comp_compress：根據指定的壓縮演算法，將輸入資料進行壓縮並輸出至緩衝區中
crypto_alloc_comp 函式參數

const char *alg_name：壓縮演算法名稱，此處使用 "deflate"
u32 type：設定為 0 即可
u32 mask：設定為 0 即可

crypto_comp_compress 函式參數

struct crypto_comp *tfm：由 crypto_alloc_comp() 建立的壓縮實體
const u8 *src：指向欲壓縮的輸入資料
unsigned int slen：輸入資料的長度 (以位元組為單位)
u8 *dst：指向輸出緩衝區的指標，用來儲存壓縮後的資料
unsigned int *dlen：指向一個整數的指標，壓縮完成後會被更新為實際壓縮資料的大小

完成壓縮邏輯後，我們即可將待回應的 HTTP 內容進行壓縮，並於回應標頭中加入 Content-Encoding 欄位，標明所使用的壓縮格式 (如 deflate) ，以便用戶端可正確解碼顯示。下面是建立的壓縮函式：

#define COMPRESS_ALGORITHM "deflate"

bool compress(const char *input,
              unsigned int input_len,
              char *output,
              unsigned int *output_len)
{
    struct crypto_comp *comp;

    comp = crypto_alloc_comp(COMPRESS_ALGORITHM, 0, 0);
    if (IS_ERR(comp)) {
        pr_err("Failed to allocate compression object\n");
        return false;
    }

    int ret = crypto_comp_compress(comp, input, input_len, output, output_len);

    if (ret) {
        pr_err("Compression failed with error code: %d\n", ret);
        crypto_free_comp(comp);
        return false;
    }

    crypto_free_comp(comp);
    return true;
}

static bool handle_directory(struct http_request *request, int keep_alive)
{
    ...
    else if (S_ISREG(fp->f_inode->i_mode)) {
        // Send HTTP header
        SEND_HTTP_MSG(request->socket, buf, "%s%s%s%s%u%s%s%s",
+                      "HTTP/1.1 200 OK\r\n", "Content-Encoding: deflate\r\n",
+                      "Content-Type: text/plain\r\n",
                      "Content-Length: ", tmp_buf_size,
                      "\r\nConnection: ", connection, "\r\n\r\n");
    }
    ...
}

結果比較

從網頁的開發者工具中觀察 benchmark 工具 htstress.c 可以看到壓縮前後數據從 16436 縮小至 5597，有明顯的下降。
Before:

After :

引入 timer 以主動關閉逾期的連線

根據高效 Web 伺服器開發 - 實作考量點提到以下考量點

當 Web 伺服器和客戶端網頁瀏覽器保持著一個長期連線的狀況下，遇到客戶端網路離線，伺服器該如何處理？

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

: 通訊協定無法立刻知悉，所以僅能透過伺服器引入 timer 逾時事件來克服

前述實作的 HTTP/1.1 keep-alive 機制可使伺服器在傳送完回應後持續保持與客戶端的 TCP 連線，允許於同一連線中處理多筆 HTTP 請求與回應，避免每次請求都需重新建立連線所帶來的延遲。

然而，為使伺服器能在資料傳輸完成後自動關閉不再使用的連線，應在請求結束後引入 timer 機制，於閒置一段時間後主動關閉未再活動的 TCP socket。

目前的 kHTTPd 尚未導入此機制，因此長時間閒置的連線會持續佔用 socket 資源。可參考 sehttpd 中的 timer 實作，其使用 min heap 建立 timer 的 priority queue，使查詢、插入、刪除與維護的時間複雜度均為

O (\log N)

，具良好擴展性。

要在 kHTTPd 中整合連線逾時管理，可分成以下子問題逐步解決：

將 socket 設定為 non-blocking 模式，以便在無資料可讀時不阻塞執行緒
讀取目前時間並為每個連線設定過期期限
實作 priority queue 管理所有連線的逾時事件，並定期檢查是否有到期的項目需關閉

socket 設 non-blocking

將 socket 設為 non-blocking 模式的主要原因在於：原本的實作中，socket 預設為 blocking，執行緒會在 kernel_accept 函式中阻塞等待新連線的到來。這種情況下無法持續檢查並處理逾時的連線，導致無法及時關閉閒置 socket，造成資源無法回收。

根據 kernel_accept 文件，可透過參數 flags 設定為 SOCK_NONBLOCK，使 kernel_accept 在無連線時立即返回並回傳 -EAGAIN。這樣我們便可在主迴圈中繼續執行 handle_expired_timers 函式，定期維護所有 socket 的 timer 並關閉逾期連線。

int http_server_daemon(void *arg)
{
    ...
    while (!kthread_should_stop()) {
        int err = kernel_accept(param->listen_socket, &socket, SOCK_NONBLOCK);

        // clean up expired timer
        handle_expired_timers();

        if (err < 0) {
            // 檢查此 thread 是否有 signal 發生
            if (signal_pending(current))
                break;

            // non-blocking socket, EAGAIN 表示沒有連線
            if (err == -EAGAIN) {
                continue;
            } else {
                pr_err("kernel_accept() error: %d\n", err);
                break;
            }
        }
        ...
    }
    ...
}

設定 socket 過期期限

我們需要建立一個 timer 優先佇列來管理每個連線的逾時狀態，為了讓查詢、插入與更新作業具備良好效能，這裡選用以 min heap 實作的優先佇列。

在 kHTTPd 的架構中，只有一個背景執行緒負責定期掃描並移除已過期的 timer，可視為唯一的 consumer；而每個處理 client 連線的工作執行緒皆可能動態新增或更新 timer，因此這是個典型的 MPSC (Multiple Producer, Single Consumer) 場景：

Multiple Producers：多個處理連線的執行緒會各自產生 timer 插入或更新佇列
Single Consumer：唯一的背景清理執行緒會定期從佇列中取出並處理最早過期的 timer

基於這樣的特性，設計時需特別考量 lock 的使用與資料一致性。以下定義結構體 socket timer 和維護 timer 的 priority queue:

typedef struct {
    size_t key;                   // expired time
    size_t pos;                   // timer list 中的位置
    timer_callback callback;      // 關閉 socket 的 function
    void *object;                 // http_request
} timer_node_t;

typedef struct {
    void **priv;
    atomic_t nalloc;              // number of items in queue
    atomic_t size;                // size of queue
    prio_queue_comparator comp;
    spinlock_t lock;              
} prio_queue_t;

整體的 priority queue 運作流程如下：

初始化 priority queue，等待處理連線
每當有新連線建立時，建立對應的 timer 並插入至 priority queue
定期透過 handle_expired_timers 檢查是否有 timer 已逾時，若有則關閉對應連線
若連線在逾時前再次送出請求，則更新對應的 timer_node_t 結構中的 key，延後其逾期期限

以下為新增連線 timer 的函式實作。由於處於多執行緒環境，可能同時有多個 work item 嘗試將 timer 插入至優先佇列，因此實作時特別注意並行控制：

使用 atomic 操作取得目前時間與有效計數，避免不一致的讀寫狀態
插入 timer 前後以 spin_lock 鎖住整個 priority queue，確保插入過程具一致性，避免發生 race condition

bool http_add_timer(void *object,
                    size_t timeout,
                    timer_callback cb,
                    bool is_socket)
{
    timer_node_t *node = kmalloc(sizeof(timer_node_t), GFP_KERNEL);

    if (!node)
        return false;

    current_time_update();
    node->key = atomic_read(&current_msec) + timeout;
    node->pos = atomic_read(&timer.nalloc) + 1;
    node->callback = cb;
    node->object = object;
    if (is_socket == false) {
        struct hash_content *content = (struct hash_content *) object;
        content->timer_node = node;
        pr_info("Added timer for key %s\n", content->request);
    } else {
        struct http_request *req = (struct http_request *) object;
        req->timer_node = node;
        pr_info("Added timer for socket\n");
    }

    // 加入 spinlock 保護
    spin_lock(&timer.lock);
    prio_queue_insert(&timer, node);
    spin_unlock(&timer.lock);
    return true;
}

維護、刪除過期 timer 和 socket

刪除過期 timer 的流程：由於 min heap 的特性是將最早的逾時項目維持在頂端，因此只需不斷檢查 heap 頂端的 timer。

每次從 heap 取出頂端 timer，檢查其逾時時間是否已達目前時間：

若已逾時，則關閉對應的 socket 並從 heap 中移除該 timer
若尚未逾時，表示後續所有 timer 的到期時間皆在未來，可停止檢查

void handle_expired_timers(void)
{
    while (!prio_queue_is_empty(&timer)) {
        timer_node_t *node;

        current_time_update();
        node = prio_queue_min(&timer);

        if (node->key > atomic_read(&current_msec))
            return;

        prio_queue_delmin(&timer);
    }
}

過期的 timer 需要執行一個 callback 函式關閉 socket，執行後會將 socket 通道關閉並且結束 work item 的生命週期。

int shutdown_socket(void *http_req)
{
    struct http_request *request = (struct http_request *) http_req;
    struct socket *socket = request->socket;
    kernel_sock_shutdown(socket, SHUT_RDWR);
    request->complete = 1;
    return 1;
}

結果比較

下面影片展示 socket 超過 expired time 後被關閉：

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

研究 Tickless Hierarchical Timing Wheel

若連線正常關閉 (即 read 回傳 0)，伺服器呼叫 close 即可；若網路中斷，在 TCP 層次無法立即得知，須靠應用層的逾時機制判斷失效連線。傳統作法在伺服器端加入 timer，常以 priority queue (例如 binary heap) 維護，從頭開始檢查是否逾時。

另一種高效方案是 tickless timer：動態調整下一次醒來的間隔，每回選出最接近到期的 timer，減少 CPU 空轉。常見實作為 timing wheel。William Ahern 提供的 Tickless Hierarchical Timing Wheel 便採此結構，理論依據出自論文〈Hashed and Hierarchical Timing Wheels〉。

bench 目錄收錄效能比較範例 (詳見 sysprog21/timeout) 。lwan 亦整合該 timer，並重新整理程式碼：

timing wheel 的插入、刪除均為 O(1)：

論文〈Hashed and Hierarchical Timing Wheels〉自最原始的 timeout model 出發，逐步改進並最終提出 Hashed 與 Hierarchical Timing Wheels。早期作業的 timeout 需要 O(n) 時間維護；論文目標在於將所有關鍵操作降至 O(1)。主要的函式：

STARTTIMER(interval, id, action) 新增 timer
STOPTIMER(id) 停止指定 timer
PERTICKBOOKKEEPING() 每 tick 檢查到期 timer
EXPIRYPROCESSING() 執行逾時動作

七種方案概述：

Straightforward: 插入、移除
$O (1)$ ，掃描
$O (n)$
Ordered List：保持鏈結串列排序，停止
$O (1)$ ，插入最壞
$O (n)$
Tree‑based：用平衡樹或 heap，插入
$O (\log n)$ ，停止
$O (\log n)$
Basic Timing Wheel：單層 wheel，掃描趨近
$O (1)$ ，遇長間隔易碰撞
Hashed Wheel + (Un)sorted List：以雜湊縮減搜索；排序與否取決於性能側重
Hierarchical Wheel：多層 wheel (秒、分、時、天) ，在高層存放遠期 timer，再逐層下移，所有操作
$O (1)$

lwan 採 4 層 wheel，每層 64 個 slot：

#define WHEEL_BIT 6   /* 2^6 = 64 */
#define WHEEL_NUM 4

struct timeouts {
    struct list_head wheel[WHEEL_NUM][1U << WHEEL_BIT];
    struct list_head expired;
    uint64_t pending[WHEEL_NUM]; /* 每層的位元圖 */
    timeout_t curtime;
};

實作技巧：

timeout_wheel() 透過 fls 計算應落在哪層
timeout_slot() 以位元運算取 slot 索引
pending 位元圖標記各層哪些 slot 仍有未處理 timer
每層操作僅用位元運算與鏈結串列，插入與刪除保持
$O (1)$

timeouts_update() 透過推進 curtime 並依 pending 位元圖搬運 timer，無需逐 tick 掃描，達到 tickless 目標。

此結構適用於高度並行伺服器：timer 數量可達數十萬且維護開銷仍穩定。若需進一步整合至 khttpd，可在接受連線時為每個 socket 設置逾時值，逾時事件由 timing wheel 統一管理，可大幅減少 idle 連線佔用資源。

藉由 RCU 在並行環境中釋放系統資源

RCU 是 Linux 核心的同步機制之一，允許多個 reader 在單一 writer 更新資料的同時，可以在不需要 lock 的前提，正確讀取資料。RCU 適用於頻繁的讀取 (即多個 reader)、但資料寫入 (即少量的 updater/writer) 卻不頻繁的情境，例如檔案系統，經常需要搜尋特定目錄，但對目錄的修改卻相對少，這就是 RCU 理想應用場景。

延伸閱讀: RCU 同步機制

RCU 藉由 lock-free 程式設計滿足以下場景的同步需求:

頻繁的讀取，不頻繁的寫入
對資料沒有 strong consistency 需求

Content Cache 與 RCU 的共通特性

由於 content cache 所使用的雜湊表在實務上「讀多寫少」，即讀取次數遠高於修改次數，因此適合搭配 RCU 這類 lock-free 同步機制。RCU 可讓多個執行緒在資料更新期間仍可進行讀取，避免典型 lock 造成的效能瓶頸，提升整體讀取效率。

除了用來儲存 content cache，雜湊表還需考慮資源釋放的機制。為此，我們將每筆 hash_content 加入前述實作的 timer_node，並設定逾時期限。當目前時間超過該期限時，handle_expired_timers 便會執行對應的 callback，將快取項目從雜湊表中移除。

由於雜湊表仍屬 MPSC 架構，這裡需要額外注意一點：若某筆快取項目在準備刪除時，仍有其他執行緒正在存取該項資料，則不應立即釋放。此時 RCU 可派上用場，確保在沒有任何讀取者存取該資料後才真正釋放資源，避免資料競爭與 use-after-free (UAF) 的風險。

RCU 程式

首先，在雜湊表存取時設定 rcu_read_lock 和 rcu_read_unlock，確保讀取操作在進行期間雜湊表不會被破壞。

bool hash_check(const char *request, struct list_head **head)
{
    u32 original_key = jhash(request, strlen(request), 0);
    u8 key = (u8) (original_key % 256);
    struct hash_content *now = NULL;
    rcu_read_lock();
    hash_for_each_possible_rcu(ht, now, node, key)
    {
        ...
    }
    rcu_read_unlock();
    return false;
}

接著在 timer callback 函式 remove_key_from_hashtable，將節點從雜湊表中移除後設定 synchronize_rcu 等待所有執行緒離開被刪除節點，最後才釋放被移除的節點。

// 刪除指定 key 的元素
int remove_key_from_hashtable(void *hash_cnt)
{
    rcu_read_lock();  // 開始 RCU 讀取區段
    ...
    hash_for_each_possible_rcu(ht, now, node, key)
    {
        char *now_request_url = now->request;
        if (strcmp(request_url, now_request_url) == 0) {
            pr_info("Removing key %s from hash table\n", request_url);

            // 刪除 hash_content from hash table
            spin_lock(&hash_lock);
            if (!hash_hashed(&now->node)) {  // 略過已經刪除的節點
                spin_unlock(&hash_lock);
                rcu_read_unlock();
                pr_info("Key already removed");
                return 0;
            }
            hash_del_rcu(&now->node);
            spin_unlock(&hash_lock);

            // 等待所有 RCU 讀取區段結束
            rcu_read_unlock();
            synchronize_rcu();

            // 釋放 cache list 的每一個 buffer
            list_for_each_entry_safe (cache_entry, tmp, now->head, cache) {
                list_del(&cache_entry->cache);
                kfree(cache_entry);
            }

            // release
            pr_info("Key removed");
            kfree(now->request);
            kfree(now);

            return 1;
        }
    }
    rcu_read_unlock();  // 結束 RCU 讀取區段
    return 0;
}

N07: ktcp

Concurrency Managed Workqueue (CMWQ)

傳統 workqueue 架構與限制

CMWQ 的出現與核心目標

架構說明

設計方式

Worker Pool 架構

CPU 綁定與排程機制

Worker Pool 類型說明

CMWQ 的優勢

將 create_workqueue 改為 alloc_workqueue

kthread 版與 CMWQ 版 kecho 執行差異

測量 kthread 建立成本

引入 CMWQ 到 khttpd

實作 directory listing 功能

取得現行目錄

讀取檔案資料

使用 Chunked transfer encoding 送出目錄資料

使用 MIME 處理不同類型的檔案

卸載模組時產生錯誤

使用 Ftrace 觀察 kHTTPd

找出 kHTTPd 的效能瓶頸

實作 content cache

將 URL 與內容快取納入雜湊表管理

scatter-gather I/O 傳送資料

結果比較

支援 HTTP 壓縮

支援 HTTP 壓縮的目的

資料壓縮機制

結果比較

引入 timer 以主動關閉逾期的連線

socket 設 non-blocking

設定 socket 過期期限

維護、刪除過期 timer 和 socket

結果比較

研究 Tickless Hierarchical Timing Wheel

藉由 RCU 在並行環境中釋放系統資源

Content Cache 與 RCU 的共通特性

RCU 程式

將 `create_workqueue` 改為 `alloc_workqueue`

引入 CMWQ 到 `khttpd`