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

執行人: han1018
專題解說錄影

任務簡介

以第七次作業為基礎，熟悉 Linux 核心模組的開發、網路通訊機制、RCU 使用，和排除相關的技術議題。

應對下方修改，嘗試提交 pull request 到 khttpd。

參考資訊： (適度改寫下方程式碼並驗證)

• Jerejere0808
  $\to$ 開發紀錄
• Paintako
  $\to$ 開發紀錄
• cppcoffee/khttpd

TODO: 引入 CMWQ 改寫 kHTTPd

分析效能表現和提出改進方案

實驗環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         43 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 5 3600 6-Core Processor
    CPU family:          23
    Model:               113
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            0
    Frequency boost:     enabled
    CPU max MHz:         4208.2031
    CPU min MHz:         2200.0000
    BogoMIPS:            7200.03

測試原始專案運作正常

編譯 khttpd 專案

$ cd khttpd
$ make

掛載 khttpd 模組並且指定 port

$ sudo insmod khttpd.ko port=1999

掛載模組後查訪 index.html 會成功得到 Hello World!! 表示掛載成功

$ wget localhost:1999

Resolving localhost (localhost)... 127.0.0.1
Connecting to localhost (localhost)|127.0.0.1|:1999... connected.
HTTP request sent, awaiting response... 200 OK
Length: 12 [text/plain]
Saving to: ‘index.html’

index.html                      100%[======================================================>]      12  --.-KB/s    in 0s      

2024-06-03 21:57:36 (1.95 MB/s) - ‘index.html’ saved [12/12]

引入 CMWQ 改寫 kHTTPd

• 優勢：
  • CMWQ 利用的 thread pool 的機制，大幅減少了創建 thread 的 overhead。
  • 使用 unbounded thread 機制使得 thread 可以切換到 idle 的 CPU 上，增加系統資源的使用率。
  • 引入 scheduling 機制資源不會被需要長時間的 thread 佔用。
• 用法：
  • alloc_workqueue : 在初始化模組時用來建立一個 workqueue
  • destroy_workqueue : 用來釋放 workqueue
  • queue_work : 將任務放入 workqueue 中排程
  • INIT_WORK : 用以初始化任務

改動區域

khttpd 主要的運作是在 http_server_daemon 中以阻塞 (blocking) 方式偵測和等待新的 socket 連線。當接收到新的 socket 連線後，會立即建立一個 kthread 執行回覆客戶端內容的 http_server_worker 函式。這次的改動是使用 work 和 workpool 取代 kthread，以提高閒置 CPU 的使用率。

詳細改動可以參照 Implement CMWQ to improve throughput，

改動部分，新增了兩個結構體 khttpd_service、khttpd，用於存放 work item 和 workqueue。

struct khttpd_service {
    bool is_stopped;
    struct list_head worker;
};

struct khttpd {
    struct socket *sock;
    struct list_head list;
    struct work_struct khttpd_work;
};

接著，在等待 socket 連線的函式 http_server_daemon 中，用 create_work 取代建立 kthread，讓連線的 client 執行回覆函式 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");
+
+        // create work
+        work = create_work(socket);
+        if (!work) {
+            pr_err("can't create work\n");
+        }

在 http_server_worker 函式內，由於無法從 kthread 傳遞參數至函式，因此改用 CMWQ（Concurrent Managed Work Queue）。使用 container_of 來取得 work item 結構體，從而獲得 work item 的 socket。

static int http_server_worker(void *arg){
 ...

-    struct socket *socket = (struct socket *) arg;
+    struct khttpd *khttpd_work = container_of(work, struct khttpd, khttpd_work);
+    struct socket *socket = khttpd_work->sock;

 ...
}

建立 CMWQ 的 work item 和移除程式如下：

static struct work_struct *create_work(struct socket *sk)
{
    struct khttpd *work;

    // GFP_KERNEL: 正常配置記憶體
    if (!(work = kmalloc(sizeof(struct khttpd), GFP_KERNEL)))
        return NULL;

    work->sock = sk;

    // 建立 work - http_server_worker function
    INIT_WORK(&work->khttpd_work, http_server_worker);
    list_add(&work->list, &daemon.worker);  // Add work to worker list

    return &work->khttpd_work;
}

static void free_work(void)
{
    struct khttpd *tmp, *tgt;
    list_for_each_entry_safe (tgt, tmp, &daemon.worker, list) {
        kernel_sock_shutdown(tgt->sock, SHUT_RDWR);
        flush_work(&tgt->khttpd_work);
        sock_release(tgt->sock);
        kfree(tgt);
    }
}

結果比較

實際來測試使用 Before 的 kthread 方法執行 http_server_worker 與使用 CMWQ 方法執行的差異。可以看到從 kthread 改至 CMWQ 後效果提升不少，從 11218 上升至 14695 每秒！

加上 CMWQ 前：

• Benchmark：./htstress http://localhost:8081 -n 50000

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

requests:      50000
good requests: 50000 [100%]
bad requests:  0 [0%]
socket errors: 0 [0%]
seconds:       4.457
requests/sec:  11218.044

加上 CMWQ 後：

• Benchmark：./htstress http://localhost:8081 -n 50000

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

requests:      50000
good requests: 50000 [100%]
bad requests:  0 [0%]
socket errors: 0 [0%]
seconds:       3.402
requests/sec:  14695.790

TODO: 實作網頁伺服器目錄

• 提供目錄檔案存取功能，提供基本的 directory listing 功能
• 目前的 kHTTPd 初步實作 HTTP 1.1 keep-alive，不過效率不彰，以 ftrace 一類的工具指出問題所在並改進

實作 directory listing 功能

顯示目錄下的內容

• dir_context:
  dir_context 是 Linux 核心中用於檔案系統中的目錄讀取操作的一個結構體。可以在檔案系統中讀取目錄，並將它們傳遞給用戶空間的程序。這裡用做回傳走訪目錄下每一個節點的內容至 client 顯示。
• filp_open
  filp_open 與 user mode 的 open 相似，負責在 kernel mode 中打開指定的檔案並回傳一個 file pointer。

顯示指定目錄下所有的檔案

參考 Risheng1128 的方式，建立 handle_directory 函式實作回傳目錄的功能。在 client socket 連線後進入 handle_directory，打開指定目錄，將目錄中的每一個內容名稱用 HTML table 傳至 client，完整程式可以參考 Add the functions to return the directory list。

走訪每一個目錄節點的 callback 函式是 tracedir，tracedir 的功能就是會走訪整個目錄的資料，並且每執行一次就會將資料送到 client。將目錄中檔案名稱包成一個一個 HTML table 的 tr 再傳給 client。

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};
        
        // directory item
        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 true;
}

傳給 client 的 HTML 程式除了內容也需要負責傳送 HTTP 頭欄位、結尾等內容，如下：

static bool handle_directory(struct http_request *request)
{
    struct file *fp;
    char buf[SEND_BUFFER_SIZE] = {0};
    
    // 設定 directory callback function
    request->dir_context.actor = tracedir;
    
    // 只接受 GET method
    if (request->method != HTTP_GET) {
        ...
        return false;
    }
    
    // 傳 HTTP request header
    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));

    // HTML head
    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));
    
    ...
        
    // 走放目錄下的每一個節點，傳送內容至 client
    iterate_dir(fp, &request->dir_context);
    
    ...
        
    // 關閉目錄
    filp_close(fp, NULL);
    return true;
}

最後在 client 連線後的 callback 函式設定執行前面建立好的傳輸內容函式，取代掉原本單純的回傳 "hello world" 字樣：

static int http_server_response(struct http_request *request, int keep_alive)
{
    int ret = 0;
    ret = handle_directory(request);
    if (ret == 0) {
        pr_err("handle_directory failed\n");
        return -1;
    }
    return 0;
}

目前結果已經可以顯示指定路徑下的目錄了，如下圖：

• TODO :
  • 可以增加 index.html 搭配 css

增加返回前一目錄功能 ".."

參考 fatcatorange 方法，在目錄之間可以用點選方式返回前一目錄，好處是可以返回上一頁時可以不用點選瀏覽器的返回上一頁按鍵而看到之前目錄的快取。如果程式寫出 Bugs 時便可以第一時間知道。

返回連結的超連結用當前位置 + /../ ，便可以回至前一個目錄位置。

為了讓返回連結出現在第一個，這裡將返回連結順序放在 HTML head 傳送完之後回傳。在出現的返回連結的地方，避開首頁位置增加判斷 strcmp(request->request_url, "/")，網址位於子目錄位置時才顯示返回連結。

static bool handle_directory(struct http_request *request, int keep_alive)
{
    ...
    // 判斷為目錄
    if (S_ISDIR(fp->f_inode->i_mode)) {
        
    // Send HTTP header
    ...
    // Send HTML head
    ...

+    // Add .. link
+    if (strcmp(request->request_url, "/")) {
+        SEND_HTTP_MSG(
+            request->socket, buf,
+            "%lx\r\n<tr><td><a href=\"%s%s\">..</a></td></tr>\r\n",
+            36 + strlen(request->request_url) + 4, request->request_url,
+            "/../");
+    }

    ...
    }
}

成果如下圖：

掛載模組時指定目錄

參考 Risheng1128 的方式，新增掛載模組時的參數 root，掛載模組時可以設定目錄位置給模組參數 root 指定要開啟的路徑。完整的修改可以參考
Add the root parameter that can specify the directory path

設定模組的參數方式如下，參考 The Linux Kernel Module Programming Guide 使用 module_param_string 新增參數 root。

#define PATH_SIZE 100
static char ROOT[PATH_SIZE] = {0};
module_param_string(root, ROOT, PATH_SIZE, 0);

從掛載模組得到的參數需要傳給 http_server_daemon，這裡需要增加傳入 kthread 的參數，從 kthread 參數結構體 http_server_param 增加 root_path 指標變數。

struct http_server_param {
    struct socket *listen_socket;
+    char *root_path;
};

int http_server_daemon(void *arg){
    ...    
+    // Init root path
+    daemon.root_path = param->root_path;
}

現在便可以通過掛載模組時指定 root 變數一個目錄路徑，在連線網站時可以得到該目錄下的內容。

$ sudo insmod khttpd.ko port=8081 root="/home/deepcat/Documents/Course/linux2024/khttpd"

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

MIME 定義在 RFC 6838 標準裡，用於表示檔案、數據的性質和格式。如果想要在網頁中顯示不同類型的檔案（如 .pdf, .jpg, .mov 類型）需要在 HTTP header 中定義它的 Content-Type。

Content-Type 支援了 HTTP 可顯示的所有內容，可以參考 Common MIME types，裡面包含不同支援的檔案類型，以及對應的回應訊息。Content-Type 在使用時需要設定為 Content-Type : type/subtype ，type/subtype 可以參考 Common MIME types 內容進行設定。

這裡引用 Risheng1128 建立的常見 MIME 類型及回應內容，用一個 .h 建立 MIME 表格對應不同類型的檔案回應訊息。在傳送 HTTP header 標頭前會先確認這個檔案的類型，查找表格中對應的回應訊息，接著設定於 Content-Type。完整的修改可以參考 Support MIME type with common type of files

查找 MIME 回應訊息程式如下，會先建立一個表格存入常見的標頭格式，用走訪每一個節點方式找到對應的 MIME 類型，回傳給 HTTP Header。

typedef struct {
    const char *type;
    const char *string;
} mime_map;


mime_map mime_types[] = {
    {".aac", "audio/aac"},
    {".abw", "application/x-abiword"},
    {".arc", "application/x-freearc"},
    ....
}

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

結果

成果如下以可以顯示如 pdf, jpg 等常見檔案：

• PDF :
  

  

• JPG :
  

  

使用 Chunked transfer encoding 送出目錄資料

目前為止我們的 HTTP 傳輸實作是採用 keep-alive 的方式。這樣的用意是傳輸內容給 client 後不會立即關閉 socket 通道，會等待一段時間等待 client/server 傳輸新的內容。好處是避免每傳輸一筆資料就重新建立一個 socket，浪費許多資源和等待時間。

參考 Keep-Alive 如下圖，在 HTTP 1.1 的版本是預設使用 persistent connection ，允許在單一連線下處理多個請求。Persistent connection 模式下 client 會持續等待 server 傳來的資訊直到結束，而什麼時候結束便衍伸出了一個問題。Keep-alive 模式下使 client 難以確定一個回應結束和下一個回應開始的時間，為了解決這個問題需要使用 HTTP 1.1 引入的 Chunked transfer encoding 來給我們一個結束訊號，得到結束訊號後便可以將 socket 關閉。

參考 Transfer-Encoding: Chunked encoding，根據範例得到以下資訊：

• 每次傳送資料時都要在最前面加上資料的長度
• 資料需要由 \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

參考 fatcatorange 說明，和上述網站略微不同的是結束時需要設定為 0\r\n\r\n\r\n 才可以正確關閉 socket 連線。由此可以調整 Keep-alive 傳輸模式為 Chunked transfer encoding，完整修改可以參考 Fix: client directory page keep waiting data，

成果如下圖，修改為 Chunked transfer encoding 方法後可以觀察到每次 client 請求連線，Client 端不會因為一直等待 server 傳輸內容而轉圈圈了。

Before (Content-length mode):

After (Chunked-transfer-encoding mode):

TODO: 實作 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 請求就可以直接傳送已經儲存在記憶體的內容，減少走訪目錄讀取檔案資訊或是內容的時間、進而增加吞吐量。

---

實作 content cache

為了將走訪目錄得到的資訊儲存起來，這裡的想法是建立一個 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 鏈結串列加入至 hash table 中提供下一次請求時查詢。

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 和 content cahche 加入 Hash table

加入 hash table 的實現如下，這裡定義了一個 2^8 大小的 hashtable，hash_insert 這個函式會將傳入的 URL 和 cache 內容的鏈結串列 cache_list 插入到雜湊表中，如果該 URL 已經存在，則不做插入並釋放已分配的記憶體。考量到多執行緒下可能會有多個函式插入 URL 到 hash table，所以在插入時使用 spinlock 來保護資料正確性，如果 URL 已經存在至 hash table 則退出。

首先定義了一個結構體 hash_content 用於儲存 hash table entry 的資料結構

• head：指向 cache 鏈結串列
• request：客戶端請求的 URL
• node：指向 Linux 核心的 hash list
• timer_node：用於後續釋放資源

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

接著下面程式是實作插入 URL 至 hash table。

• jhash 函式是用來計算 request_url 的雜湊值，並存儲在 original_key 中
• 接著使用取模運算將 original_key 轉換成 8 位（即 256 之內）的 key

函式整段的流程如下：

• 使用旋轉鎖保護雜湊表的併發訪問，進行插入操作前加鎖（spin_lock(&hash_lock)）
• 使用 hash_for_each_possible_rcu 宏走訪雜湊表中所有可能的 key 位置
  • 如果找到與 request_url 相同的 key，則釋放新分配的 content，並返回以避免重複插入
• 使用 hash_add_rcu 宏將新的 hash_content 插入到雜湊表中
• 插入操作完成後解鎖（spin_unlock(&hash_lock)）

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 至 hash table 後每次訪問 URL 時只需要檢查 hash table 有無已存在的 cache，有的話則取出內容傳送至客戶端即可，不用再走訪 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 至 hash table，減少走訪目錄取得檔案資訊內容的時間。但使用 benchmark 測試時卻發現效果遠不如預期，改善後只有約 10 % 的進步。根據 ftrace 觀察原因，發現時間都卡在 socket 傳送資訊給 client 的 http_server_send 函式上。這裡的實作會走訪 cache_list 鏈結串列裡的內所有節點，將節點的 buf 內容依序傳給 client，所以假如有 n 個節點就需要執行 n 次的 http_server_send 函式，這樣的時間成本會太高。更好的方式是使用 scatter-gather I/O 方式用 iovec 結構體將多個 buffer 內容一次傳給客戶端，減少系統調用次數。

測試結果：
Before:

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

requests/sec:  24318.492

After :

$ ./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。

完整的修改可以參考：Optimize Content Cache Transmission with Scatter-Gather I/O

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

結果比較

改善後，可以看到使用 content cache 前後吞吐量的變化，並行數 = 1 時從 2135 上升至 10866，並行數 = 20 時從 24318 上升至 45093 次每秒，效果如預期。這是合理的原因是 benchmark 存取的是同一個網站且被存於快取記憶體，因此可以直接取出傳給客戶端。

Before 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

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

參考資料

• Fast Scatter-Gather I/O
• 參考 hash table 操作 include/linux/hash.h
• https://liujunming.top/2018/03/12/linux-kernel中HList和Hashtable/

TODO: 支援 HTTP 壓縮

善用 Kernel Crypto API，至少涵蓋 gzip 壓縮。

支援 HTTP 壓縮的目的

目前為止，已經實作了傳輸指定目錄下的檔案資訊、顯示檔案內容等功能，點擊目錄的超連結後便能在網頁中顯示不同的檔案內容，例如 PDF, JPG 圖片等功能。而這些檔案往往資料非常大，需要傳送資訊也要更久，如果可以傳輸壓縮後的檔案至客戶端，便可以大幅減少資料傳送量，要顯示時於網頁時再從客戶端解壓縮即可。這裡就是打算實作 Linux 核心支援的壓縮 API ，將壓縮後的檔案內容傳送給客戶端，希望降低傳輸的資料量。

壓縮的機制

這裡預期實作常見 HTTP 的壓縮演算法 - gzip / deflate。從 cat /proc/crypto 可以看到電腦中有支援的壓縮方式，這裡我使用的是 deflate 演算法，接下來再使用 Linux kernel API 來指定壓縮演算法來壓縮指定的記憶體空間。

Linux Kernel 提供的 API 為 crypto_alloc_comp、crypto_comp_compress 兩個函式來做資料壓縮，crypto_alloc_comp 用來指定使用的壓縮演算法名稱，crypto_comp_compress 用於實際壓縮數據，根據 crypto_alloc_comp 壓縮演算法來壓縮輸入的數據，並將結果存在指定的輸出記憶體空間中。

• 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 的內容壓縮，並設定 HTTP 標頭檔的 CONTENT-ENCODING，指定我們的壓縮演算法。

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

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

timer 的功能

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

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

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

前面實作的 HTTP 1.1 keep-alive ，每次客戶端與伺服器傳送完資料後會持續保持連線，允許在同一個 TCP 連接中傳送多個 HTTP 請求和回應，避免了每次請求都要重新建立連接的延遲。為了讓伺服器與客戶端在所有資料傳輸完成後可以自動關閉 TCP，這裡建立請求結束後可以引入 timer 逾時事件，關閉一段時間沒有傳輸的 TCP 連線。

目前的 kHTTPd 沒有使用 timer 來關閉閒置的連線，因此會導致 socket 資源被佔用。參考 sehttpd 裡 timer 的實作，使用 min heap 實做 timer 的優先佇列，讓查詢、新增、維護刪除的時間複查度維持在 O(log N)。

要在 kHTTPd 中的 socket 新增 timer 管理連線，可以將問題分成以下幾個小問題並且逐一解決：

• 將 socket 設定為 non-blocking
• 讀取目前的時間設定過期期限
• 實作 prority queue 並且管理每個連線

socket 設 non-blocking

將 socket 設定為 non-blocking 的原因在於，原本的實作中 socket 預設為 blocking，執行緒會停滯在函式 kernel_accept 等待新的 socket 請求，這樣沒有辦法不停的維護逾期連線的 timer、關閉逾期的 socket，因此將 socket 設定為 non-blocking。

根據 kernel_accept 文件，參數 flags 可以設定為 SOCK_NONBLOCK，如果沒有請求連線會立即返回並回傳 -EAGAIN，接著我們就使用 handle_expired_timers 函式維護 socket 的 timers，刪除逾期的 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 的優先佇列管理每個連線，為了讓查詢、維護、新增 timers 有效率這裡使用 min heap 實作的優先佇列。在 kHTTPd 中只會有一個 consumer 移除資料，亦即執行在背景的執行緒，而 producer 則是由多個處理連線的執行緒組成，因此歸納為 MPSC 的問題。

這裡先定義了兩個結構體 socket timer 和維護 timer 的優先佇列：

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 items 插入 timer 至優先佇列，這裡使用 atomic 方式讀取目前的時間和數量，並在插入優先佇列的前後使用 spin_lock 保護佇列的正確性，避免 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 特點是愈早的過期時間在愈上面，最上層的 timer 就是最早的過期時間。只要取出過期時間最早的 timer 查看是否過期，過期則刪除和關閉過期的 timer 和 socket，直到 min 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 後被關閉：

TODO: 藉由 RCU 在並行環境中得以釋放系統資源

RCU 同步機制

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

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

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

以上資訊參考：RCU 同步機制

Content cache 與 RCU 共同點

因為存放 content cache 的 hash table 通常讀取的次數是大於修改的次數，RCU (Read-Copy Update) lock free 同步機制可以提高讀取效率，使多個執行緒可以在有資料在更新時還能做讀取的動作，避免頻繁的 lock 導致效能下降。

Hash table 除了前面提到的可以新增 content cache，這裡也考量到釋放的問題。hash content 需要加入前面實作的 timer_node 並設定過期時間，當過期時間小於當前時間時就會被 handle_expired_timers 函式執行 callback 函式刪除 hash table 中的 cache。這裡 hash table 一樣是 MPSC 的問題，不一樣的地方是在刪除 hash content 的同時如果其還被執行緒存取著不會馬上被釋放，會等到沒有執行緒存取時才被釋放。

RCU 程式

首先，在 hash table 存取時設定 rcu_read_lock、rcu_read_unlock，確保讀取操作在進行期間 hash table 不會被破壞。

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，將節點從 hash table 中移除後設定 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;
}

參考：Linux 核心模式的 RCU example

實作結果

展示 hash table 釋放記憶體影片：

Tools

ftrace script 參考 Paintako :

#!/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 1
echo 0 > $TRACE_DIR/tracing_on

# result
sudo cat /sys/kernel/debug/tracing/trace > ./output.txt