Linux 核心專題: 高效網頁伺服器

執行人: yqt2000
解說影片

任務說明

依據 ktcp 作業規範，開發高效網頁伺服器 (針對靜態)。

TODO: 回答「自我檢查清單」的所有問題

需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳

研讀〈Linux 核心設計: RCU 同步機制〉並測試相關 Linux 核心模組以理解其用法
如何測試網頁伺服器的效能，針對多核處理器場景調整
如何利用 Ftrace 找出 khttpd 核心模組的效能瓶頸，該如何設計相關實驗學習。搭配閱讀《Demystifying the Linux CPU Scheduler》第 6 章
解釋 drop-tcp-socket 核心模組運作原理。TIME-WAIT sockets 又是什麼？

待整理 eric88525, zoanana990 筆記內容

研讀透過 eBPF 觀察作業系統行為，如何用 eBPF 測量 kthread / CMWQ 關鍵操作的執行成本？

參照 eBPF 教程

參照〈測試 Linux 核心的虛擬化環境〉和〈建構 User-Mode Linux 的實驗環境〉，在原生的 Linux 系統中，利用 UML 或 virtme 建構虛擬化執行環境，搭配 GDB 追蹤 khttpd 核心模組

研讀〈Linux 核心設計: RCU 同步機制〉並測試相關 Linux 核心模組以理解其用法

簡記 Linux 核心設計: 淺談同步機制

隨著電腦硬體逐漸提供 atomic 指令後，mutex 或稱為 lock 的機制被列入作業系統的實作考量:

需要進入 CS 時，用 mutex/lock —— 上鎖/解鎖永遠是同一個 thread/process;
要處理 signalling 時，用 semaphore —— 等待/通知通常是不同的 threads/processes;

~~簡言之，要搶資源時用 mutex，要互相通知時用 semaphore。~~

上方說法過於武斷，避免這樣的「簡言之」。
工程人員說話要精準。

mutex 與 semaphore 的差別在於：

process 使用 mutex 時，process 的運作是持有 mutex，執行 CS 來存取資源，然後釋放 mutex
- Mutex 就像是資源的一把鎖：解鈴還須繫鈴人
process 使用 semaphore 時，process 總是發出信號 (signal)，或者總是接收信號 (wait)，同一個 process 不會先後進行 signal 與 wait
- 換言之，process 要不擔任 producer，要不充當 consumer 的角色，不能兩者都是。semaphore 是為了保護 process 的執行同步正確;

簡記〈Linux 核心設計: RCU 同步機制〉

RCU 適用於頻繁的讀取 (即多個 reader)、但資料寫入 (即少量的 updater/writer) 卻不頻繁的情境，例如檔案系統，經常需要搜尋特定目錄，但對目錄的修改卻相對少，這就是 RCU 理想應用場景。

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

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

即使存取舊的資料，不會影響最終行為的正確，這樣的情境就適合 RCU，對其他網路操作也有相似的考量。

實驗環境

$ gcc --version
gcc (Ubuntu 13.2.0-23ubuntu4) 13.2.0

$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   8
  On-line CPU(s) list:    0-7
Vendor ID:                GenuineIntel
  Model name:             11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
    CPU family:           6
    Model:                140
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             1
    CPU(s) scaling MHz:   39%
    CPU max MHz:          4200.0000
    CPU min MHz:          400.0000
    BogoMIPS:             4838.40

TODO: 引入 Concurrency Managed Workqueue (cmwq)

改寫 kHTTPd，分析效能表現和提出改進方案，可參考 kecho

參考 YiChianLin, oscarshiang

CMWQ 簡介

CMWQ 是對 Linux 傳統 Workqueue 機制的改進和重新實現。它保持了原有 API 的兼容性，同時引入了更智能的並行管理和資源利用策略。

注意用語！

一般 workqueue:

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 →

CMWQ 與一般 Workqueue 的差別：

	CMWQ	一般workqueue
執行緒管理	使用統一的 Worker pools，由所有 workqueue 共享，更有效利用資源	Multi Thread 模式下每個 CPU 有一個 worker，Single Thread 模式下整個系統只有一個 worker
並行處理	可以動態調整並行級別，更靈活的進行管理	Multi Thread 可能因 I/O blocking 導致其他 worker 等待；Single Thread 可能造成死鎖
資源利用	通過共享 worker pools 和動態調整，大幅減少資源浪費	容易造成系統資源浪費，特別是在 Multi Thread 模式下

CMWQ 設計方式：

引入了 work item 的概念，為一個簡單的結構包含函式指標指向非同步任務運作的函式，執行時建立一個 work item 和(放入) workqueue。而處理這些任務的執行緒為 worker threads 用於一個接一個處理這些任務，而在任務結束後 thread 會變為 idle 狀態，而 worker-pools 就是用來管理這些 threads

兩種 worker-pools 類型:

Bound 類型:綁定特定的 CPU，使管理的 worker 執行在指定的 CPU 上執行，而每個 CPU 中會有兩個 worker-pools 一個為高優先級的，另一個給普通優先級的，透過不同的 flags 影響 workqueue 的執行優先度
Unbound 類型:thread pool 用於處理不綁定特定 CPU，其 thread pool 是動態變化，透過設定 workqueue 的屬性建立對應的 worker-pools

分離 Workqueue 和 Worker-pools：使用者只需關注將任務放入 queue，不需考慮執行細節。

CMWQ 的優勢及為什麼適用於該專案：

注意用語！

concurrency 是「並行」
file 是「檔案」，不是「文件」
不要參照品質低劣的簡體中文網頁，避免用 ChatGPT，後者已嚴重受簡體中文扭曲

務必詳閱 https://hackmd.io/@sysprog/it-vocabulary 和 https://hackmd.io/@l10n-tw/glossaries

網頁伺服器需要同時處理大量請求。CMWQ 通過共享 worker pools 和根據負載動態調整執行緒數量，可以滿足高並行的需求和大幅減少一般 workqueue 資源浪費的問題。
另外網頁伺服器可能需要處理不同優先級的請求。CMWQ 提供了高優先級和普通優先級的 worker pools，可以更好地處理不同類型的 HTTP 請求。
長時間任務處理：對於可能耗時較長的 HTTP 請求（如大檔案傳輸），CMWQ 可以動態建立新執行緒並分配給其他 CPU 執行，避免阻塞其他請求的處理。
跨 CPU 執行能力：CMWQ 的 Unbound 類型 worker pools 允許任務在不同 CPU 間切換，這可以提高多核系統上網頁伺服器的整體性能。

使用方式

為了在核心模組中引入 CMWQ，我們會需要使用到 <linux/workqueue.h> 中的這些函式：

alloc_workqueue : 在初始化模組時用來建立一個 CMWQ
destroy_workqueue : 用來釋放 workqueue
queue_work : 將 work 放入 workqueue 中排程
INIT_WORK : 用以初始化 work

引入 CMWQ 至 khttpd

參考了 kecho 的作法，以及 fatcatorange,YiChianLin 的筆記
這部份我的 commit: fde4de, e593125

程式碼註解不該出現中文！總是用美式英語書寫。
改進 git commit message，參照第一次作業的規範。

`main.c`

宣告 workqueue ，並在使用 workqueue 相關 API 時 include workqueue.h

workqueue_struct 定義於 workqueue.c 中，裡面有 CMWQ 文件中所提及的 unbound_attrs 可以設定 workqueue 在 unbound 條件下的屬性;
alloc_workqueue 定義於 workqueue.c 中，初始化一個 CMWQ 並在 flag 的設定為 WQ_UNBOUND 表示不會被特定的 CPU 所限制，使資源不會被閒置，可以透過切換的方式執行未完成的任務

...
+ #include <linux/workqueue.h>
...
+ struct workqueue_struct *khttpd_wq;
...
static int __init khttpd_init(void)
{
    ...
    param.listen_socket = listen_socket;
+   khttpd_wq = alloc_workqueue("khttp_wq", WQ_UNBOUND, 0);
    ...
}

`http_server.h`

khttpd_service 採用雙向鏈結串列作為 workqueue 管理 work

struct khttpd_service {
    bool is_stopped;
    struct list_head head; //workqueue
};
extern struct khttpd_service daemon_list;

`http_server.c`

請求 - 以 http_request 作為其結構體，嵌入 list_head 進行管理，而
work_struct 為真正要作的任務，可被 INIT_WORK 函式初始化，去運行客製化的函式（ e.g. 此專案中處理請求的函式 http_server_worker）

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;
};

http_server_daemon()

第 37 行(work = create_work(socket);) 為每一個連線的請求建立一個 work 進行處理
queue_work() 將 work 放入 CMWQ 中進行排程

注意書寫規範：

使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致





















































+ #include <linux/workqueue.h>
+ struct khttpd_service daemon_list = {.is_stopped = false};
+ extern struct workqueue_struct *khttpd_wq;  // set up workqueue
...
int http_server_daemon(void *arg)
{
-    struct task_struct *worker;
    ...
+    // CMWQ
+    struct work_struct *work;
+    if (!khttpd_wq)
+        return -ENOMEM;
+    // initial workqueue head
+    INIT_LIST_HEAD(&daemon_list.head);
    ...

    // 判斷執行緒是否該被中止
    while (!kthread_should_stop()) {
        int err = kernel_accept(param->listen_socket, &socket,
                                0);  // 接受 client 連線要求
        if (err < 0) {
            // 檢查目前執行緒是否有 signal 發生
            if (signal_pending(current))
                break;
            pr_err("kernel_accept() error: %d\n", err);
            continue;
        }
-        // 建立新的執行緒並且執行函式 http_server_worker
-        worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);
-        if (IS_ERR(worker)) {
-           pr_err("can't create more worker process\n");
-            continue;
-        }

+        // CMWQ 為每一個連線的請求建立一個 work 進行處理
+       if (unlikely(!(work = create_work(socket)))) {
+            pr_err("can't create work\n");
+            continue;
+        }
+        // 而建立出來的 work 會由 os 配置 worker 執行，
+        // 配置後由 khttpd_wq 將每一個 work 用 list_head 的 linked list
+        // 進行管理， 使用到 queue_work() 將 work 放入 workqueue 中
+        queue_work(khttpd_wq, work);
+    }

+    daemon_list.is_stopped = true;

+    // free work and workqueue
+    free_work();
+    destroy_workqueue(khttp_wq);

    return 0;
}

注意書寫規範：

程式碼註解不該出現中文，總是用美式英語書寫

`create_work()` & `free_work()`

在 create_work 中，根據傳入的 socket 建立一個 work，為每一個連線請求進行 kernel space (kmalloc) 的動態記憶體配置，並進行初始化，再透過 list_add 加入到 workqueue 當中

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

    work->socket = sk;

    // 初始化已經建立的 work ，並運行函式 http_server_worker
    INIT_WORK(&work->khttpd_work, http_server_worker);
    list_add(&work->node, &daemon_list.head); 
    return &work->khttpd_work;
}

注意書寫規範：

程式碼註解不該出現中文，總是用美式英語書寫

free_work():用於釋放掉所建立連線的所配置的記憶體空間，使用 list_for_each_entry_safe 巨集走訪每一個在 list 中所管理的 work
kernel_sock_shutdown(): 斷開 socket 的連線(包含傳送與接收的功能)，對應的巨集 SHUT_RDWR 關閉方式
flush_work():等待目前的的 work 執行完畢
sock_release(): 根據文件的註解，將 socket 釋放在 stack，也會斷開對應連接的 fd
kfree():釋放掉從 kmalloc 所配置出的記憶體空間

static void free_work(void)
{
    struct http_request *tmp, *target; /* cppcheck-suppress uninitvar */

    // list : member
    list_for_each_entry_safe (target, tmp, &daemon_list.head, node) {
        kernel_sock_shutdown(target->socket, SHUT_RDWR);
        flush_work(&target->khttpd_work);
        sock_release(target->socket);
        kfree(target);
    }
}

http_server_worker()

使用 workqueue 時，程式執行時就是傳入一個 struct work_struct ，因此可透過 container_of 取得請求的 socket









- static int http_server_worker(void *arg)
+ static void http_server_worker(struct work_struct *work){
    ...
-    struct socket *socket = (struct socket *) arg;
+    // http_request->socket, 透過 container_of 找到 http_request 中的 socket
+    struct socket *socket = 
+        container_of(work, struct http_request, khttpd_work)->socket;
    ...
}

注意書寫規範：

程式碼註解不該出現中文，總是用美式英語書寫

引入 CMWQ 之前，khttpd 與其他網路伺服器相比，ab 測試的結果

100000 requests with 500 requests at a time(concurrency)
ab -n 100000 -c 500 -k http://127.0.0.1:8081/

	Requests per second	Time per request (mean, across all concurrent requests)
khttpd	185278.85 #/sec	0.005 ms
kecho	136125.17 #/sec	0.007 ms
cserv	42542.40 #/sec	0.024 ms

比較 khttpd 在引入 CMWQ 之後的結果

make check 運行腳本進行測試，htstress 作為客戶端發送請求給伺服器，比較單純使用 kthread_run 和引入 CMWQ 後伺服器處理 200000 筆的請求的表現。

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

-n : 表示對 server 請求連線的數量
-c : 表示總體對 server 的連線數量
-t : 表示使用多少執行緒

	引入 CMWQ 之前	引入 CMWQ 之後
requests:	200000	200000
good requests:	200000 [100%]	200000 [100%]
bad requests:	0 [0%]	0 [0%]
socket errors:	0 [0%]	0 [0%]
seconds:	3.354	2.003
requests/sec:	59624.124	99860.744

可以看到處理 200000 筆請求的整體時間降低了不少，另外每秒可處理的請求個數也提昇了約 1.6倍。

TODO: 提供目錄檔案存取功能，提供基本的 directory listing 功能

按照作業 kecho + khttpd 實作 directory listening 的步驟以及比照 fatcatorange同學筆記內容修正缺失的方法去實作該功能，以下為整理兩者筆記並融合我在實作遇上的問題和解決方法。

修改 `http_server_response`

要加入這個功能，要修改 http_server_response ，原本的 http_server_response 只會檢查是不是用 get ，是的話回傳一個 HTTP_RESPONSE_200 (代表成功) ，內容是 hello world。

而這個函式被使用在 http_server.c/http_parser_callback_message_complete():

static int http_parser_callback_message_complete(http_parser *parser)
{
    struct http_request *request = parser->data;
    http_server_response(request, http_should_keep_alive(parser));
    request->complete = 1;
    return 0;
}

上述函式被綁定在 http_server.c/http_server_worker()：

struct http_parser_settings setting = {
        .on_message_begin = http_parser_callback_message_begin,
        .on_url = http_parser_callback_request_url,
        .on_header_field = http_parser_callback_header_field,
        .on_header_value = http_parser_callback_header_value,
        .on_headers_complete = http_parser_callback_headers_complete,
        .on_body = http_parser_callback_body,
        .on_message_complete = http_parser_callback_message_complete};

當 http_server_worker() 執行 http_parser_execute() 時，就會根據解析執行對應的函式，以這個例子來說，解析完整個 http 請求時執行 http_parser_callback_message_complete()

正式修改 http_server.c/http_server_response():

static int http_server_response(struct http_request *request, int keep_alive)
{
-    char const *response;

-    pr_info("requested_url = %s\n", request->request_url);
-    if (request->method != HTTP_GET)
-        response = keep_alive ? HTTP_RESPONSE_501_KEEPALIVE : HTTP_RESPONSE_501;
-    else
-        response = keep_alive ? HTTP_RESPONSE_200_KEEPALIVE_DUMMY
-                              : HTTP_RESPONSE_200_DUMMY;
-    http_server_send(request->socket, response, strlen(response));

+    pr_info("khttpd: requested_url = %s\n", request->request_url);

+   if (handle_directory(request) == 0)
+        kernel_sock_shutdown(request->socket, SHUT_RDWR);
    return 0;
}

實作目錄檔案存取功能 `http_server.c/handle_directory()`

handle_directory() 對於不同的 case 做出回應，主要執行以下步驟：

檢查請求屬性是否為 GET ，以及開啟請求的 url 檔案
case: IS_ERR - url 檔案無法開啟 => 404 Not Found
case: S_ISDIR - url 屬於目錄 => 繼續對迭代目錄
case: S_ISREG - url 屬於檔案 => 讀取檔案，印出內容

其中迭代目錄(tracedir, iterate_dir)為該方法的精隨，於下面內容繼續介紹


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

    request->dir_context.actor = tracedir;
    
    // request is not GET => 501 Not Implemented
    if (request->method != HTTP_GET) {
        send_http_header(request->socket, HTTP_STATUS_NOT_IMPLEMENTED,
                         http_status_str(HTTP_STATUS_NOT_IMPLEMENTED),
                         "text/plain", 19, "close");
        send_http_content(request->socket, "501 Not Implemented");
        return false;
    }

    catstr(pwd, daemon_list.path, request->request_url);
    printk("%s\n", pwd);
    fp = filp_open(pwd, O_RDONLY, 0);
    
    // case : link is not found
    if (IS_ERR(fp)) {    
        send_http_header(request->socket, HTTP_STATUS_NOT_FOUND,
                         http_status_str(HTTP_STATUS_NOT_FOUND), "text/plain",
                         14, "close");
        send_http_content(request->socket, "404 Not Found");
        kernel_sock_shutdown(request->socket, SHUT_RDWR);
        return false;
    }
    //case: link is directory => iterate_dir
    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));

    // case: link is file => readfile 
    } 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);
    }
    kernel_sock_shutdown(request->socket, SHUT_RDWR);
    filp_close(fp, NULL);
    return true;
}

iterate_dir(struct file *, struct dir_context *); 定義於 <linux/fs.h> 可對目錄struct file* 進行迭代並運行 struct dir_context * 設置的 callback function。

因此首先須在 struct http_request 中加入 struct dir_context
















+ #include <linux/fs.h>
...
+ #define SEND_BUFFER_SIZE 256
+ #define BUFFER_SIZE 256
...
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;
+   // struct dir_context, defines in fs.h
+   struct dir_context dir_context;  
};

而 http_server.c/trace_dir() 可以回傳給客戶端當前目錄下的資料夾連結或檔案連結，並將其印出顯示在 localhost 的頁面上，使得使用者可以藉由點擊目錄進入更深層的目錄或存取檔案

static _Bool 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 *des = kmalloc(strlen(request->request_url) + strlen(name) + 2,
                            GFP_KERNEL);
        if (strcmp(request->request_url, "/") != 0) {
            strncpy(des, request->request_url, strlen(request->request_url));
            strcat(des, "/");
            strcat(des, name);
        } else {
            strncpy(des, name, strlen(name));
        }

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

指定開啟目錄的路徑

main.c

...
+ static char WWWROOT[PATH_LENGTH] = {0};
+ module_param_string(WWWROOT, WWWROOT, PATH_LENGTH, 0);
...
static int __init khttpd_init(void)
{
...
+ if (!*WWWROOT)  // prevent empty input from user
+        WWWROOT[0] = '/';
+    daemon_list.path = WWWROOT;
...
}

http_server.h

struct khttpd_service {
    bool is_stopped;
+    char *path;
    struct list_head head;  // workqueue
};

即可透過 module_param ，在載入模組時指定路徑，e.g.

$ sudo insmod khttpd.ko WWWROOT='"/home/oldwustd1/linux2024"'

其餘實作細節

http_server.c 中的 send_http_header() & send_http_content() & catstr() & read_file()

static void send_http_header(struct socket *socket,
                             int status,
                             const char *status_msg,
                             char const *type,
                             int length,
                             char const *conn_msg)
{
    char buf[SEND_BUFFER_SIZE] = {0};
    snprintf(buf, SEND_BUFFER_SIZE,
             "HTTP/1.1 %d %s\r\n     \
                Content-Type: %s\r\n    \
                Content-Length: %d\r\n  \
                Connection: %s\r\n\r\n",
             status, status_msg, type, length, conn_msg);
    http_server_send(socket, buf, strlen(buf));
}

static void send_http_content(struct socket *socket, char const *content)
{
    char buf[SEND_BUFFER_SIZE] = {0};
    snprintf(buf, SEND_BUFFER_SIZE, "%s\r\n", content);
    http_server_send(socket, buf, strlen(buf));
}

// concatenate string
static void catstr(char *res, char const *first, char const *second)
{
    int first_size = strlen(first);
    int second_size = strlen(second);
    memset(res, 0, BUFFER_SIZE);
    memcpy(res, first, first_size);
    memcpy(res + first_size, second, second_size);
}
static inline int read_file(struct file *fp, char *buf)
{
    return kernel_read(fp, buf, fp->f_inode->i_size, 0);
}

成果展示

TODO: 引入 timer，讓 kHTTPd 主動關閉逾期的連線

TODO: 以 RCU 搭配自行設計的 lock-free 資料結構，在並行環境中得以釋放系統資源

學習 cserv 的 memcache 並在 kHTTPd 重新實作

過程中應一併完成以下:
- 修正 kHTTPd 的執行時期缺失
- 指出 kHTTPd 實作的缺失 (特別是安全疑慮) 並予以改正

TODO: 用你改進的 kHTTPd 和 cserv 進行效能評比

解釋行為落差