Linux 核心專題：kHTTPd 改進

執行人: w96086123
專題解說錄影

Reviewed by `SimonLee0316`

利用 hashtable 建立cache 的方式儲存每個連線的時間，請問在這個實作中每個連線的重新發送一個請求就會在更新一次 cache 值嗎？

任務簡介

改進 kHTTPd 的並行處理能力，予以量化並有效管理連線。

TODO: 閱讀 CS:APP 第 11 章

紀錄對電腦網路的認知
TCP 3-way handshake 為何要？
L2 -> L4 的分工和作用
Ethernet frame 大小？
ICMP 封包大小？

TCP 3-way handshake 為何要？

注意用語

data 是「資料」，而非「數據」
是電腦「網路」，而非「網絡」

務必使用本課程教材規範的術語！

TCP 使用 3-way handshake 的主要原因有以下幾點：

初始化序列號：
3-way handshake 中的一個關鍵步驟是交換初始序列號。這些序列號對於後續的資料傳輸非常重要：

1-1. 序列號的作用：
初始序列號在交握過程中被交換，並用於標記後續資料包的順序。這樣可以確保資料包能夠按照正確的順序被接收和處理。TCP 使用這些序列號來進行資料包的排序和重傳，以確保資料傳輸的可靠性和完整性。

1-2. 資料包重傳和排序：
如果資料包在傳輸過程中丟失或順序錯亂，TCP 可以根據序列號進行重傳和排序。這確保了即使在不可靠的網路環境中，資料也能夠正確無誤地被傳輸和處理。

1-3. 資料傳輸一致性：
通過使用序列號，TCP 能夠保證資料在網路中傳輸的一致性，避免資料丟失或重複接收。
確保雙方處於可以同步的狀態
2-1. 同步狀態確認：
三次交握過程中，客戶端和服務器互相交換初始序列號，這確保了雙方的資料傳輸是在同一個基準點上開始的。這樣可以避免資料包因網路延遲、丟失或重傳等問題導致的不同步狀況。

2-2. 資料傳輸可靠性：
確保雙方都已經準備好接收和發送資料，這樣可以避免資料包的錯誤傳輸或重傳，從而保證資料傳輸的可靠性。例如，如果雙方未同步，可能會出現資料包無法正確識別的情況，導致資料丟失或重複接收。

2-3. 避免資料包錯誤：
當前客戶端和服務器都處於同步狀態時，可以避免由於網路不同步或其他技術問題（如路由延遲）而導致的資料包錯誤，從而確保資料傳輸的完整性和正確性。
避免舊資料干擾
3-way handshake 也有助於防止舊資料包對新連接的干擾：

3-1. 避免重複和舊資料包：
當前的連接使用了新的序列號，每次建立連接時，TCP 會分配一個新的初始序列號。這確保了即使之前的連接已經關閉並建立了新連接，舊的資料包（帶有舊序列號）也不會干擾新連接。舊資料包會因為序列號不匹配而被丟棄。

3-2. 網路延遲和資料包識別：
在一些情況下，資料包可能因為網路延遲等原因滯留在網路中。通過每次連接使用不同的序列號，TCP 可以識別並丟棄這些過期或重複的資料包，防止其影響新連接。

3-3. 序列號的唯一性：
TCP 序列號具有唯一性，每個連接的序列號範圍是不同的，因此即使同一個 IP 和通訊埠組合重新建立連接，因為序列號的不同，也不會接收到舊資料包的影響。

L2 -> L4 的分工和作用

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 →

每層加入不同的標頭並解析這些標頭，是為了確保數據能夠在複雜的網路環境中正確且高效地傳輸。

L4 (傳輸層) (Transport Layer)
主要動作：加入傳輸標頭（TH）與解析傳輸層標頭

功能：
- 傳輸層負責提供端到端的通信服務，確保資料能夠可靠且有序地從一個設備傳送到另一個設備。
- 增加傳輸標頭（TH），包含以下關鍵資訊：
  - 源通訊埠號：標識資料來源的通訊埠。
  - 目的通訊埠號：標識資料目標的通訊埠。
  - 序列號：用於封包排序，確保資料按正確順序重組。
  - 確認號：確認接收到的封包，確保資料傳輸的可靠性。
  - 協定類型：如 TCP 或 UDP 。
解析傳輸標頭：
- 接收方在解析封包時，會查看傳輸標頭以了解資料的源通訊埠、目的通訊埠及其他控制信息，然後將資料傳遞給相應的程式。
L3 (網路層) (Network Layer)
主要動作：加入網路標頭（NH）與解析網路層標頭

功能：
- 網路層負責封包的路徑選擇和轉發，並加上網路標頭（NH），形成完整的封包。
- 網路標頭包含邏輯位址（IP 位址），標識網路中的設備，確保封包可以在不同的網路節點之間正確轉發。
作用：
- 路由選擇 (Routing)
  - 根據網路拓撲和當前網路狀況選擇最佳路徑。
  - 使用路由協定（如 OSPF）來更新和維護路由表。
- 邏輯位址分配
  - 提供全球唯一的邏輯位址系統（如IP位址），保證資料能夠在不同網路之間正確傳送。
解析網路標頭：
- 接收方會檢查網路標頭中的IP位址，確定封包是否到達最終目的地或需要繼續轉發。
L2 (資料鏈路層) (Data link Layer)
主要動作：加入資料鏈結串列頭（DLH）和資料鏈結串列尾（DLT）與解析資料鏈路層標頭

功能描述：
- 資料鏈路層負責物理尋址、錯誤檢測和校正，確保資料能夠在同一網段內可靠傳輸。
- 資料鏈路層會將封包加上資料鏈結串列頭（DLH）和資料鏈結串列尾（DLT），形成資訊框（Frame）。
  作用：
- 資料鏈結串列頭（DLH）
  - 包含實體位址（如MAC位址）和錯誤檢測信息。
  - 實體位址用於識別網路中的設備。
- 資料鏈結串列尾（DLT）
  - 包含錯誤檢測碼（如FCS），用於檢測和校正數據傳輸過程中的錯誤。
解析資料路層標頭：
- 接收方會檢查資料鏈結串列頭中的實體位址，確認是否是目標設備，並通過資料鏈結串列尾的錯誤檢測碼檢查封包完整性
資料鏈路層可進一步分成兩個子層：
- 邏輯鏈路控制 (LLC) 子層
  - 負責流量控制、錯誤檢測和封包的分段和組合。
  - 提供統一的接口給上層網路層，隱藏不同物理媒介的差異。
- 媒介存取控制 (MAC) 子層
  - 管理對共享媒介的存取控制，確保各設備在網路中不會發生資料碰撞。
  - 定義物理位址（MAC 位址）以唯一標識網路中的設備。

注意用語：access 是「存取」，而非「訪問」(visit)
參見資訊科技詞彙翻譯和詞彙對照表

Ethernet frame 大小？

在乙太網路 ( Ethernet ) 中，資料的傳輸單位是 Ethernet frame。
每個 Ethernet frame 以 Header 、 Data 、 Trailer 三個部分組成，每個 frame 長度有一定的規範，以下為各部分的規範：

Header
- 目的位址： 6 Bytes
- 源位址： 6 Bytes
- EtherType： 2 Bytes
Data
- 最小長度： 46 Bytes
- 最大長度： 1500 Bytes
Trailer
- FCS ( Frame Check Sequence )： 4 Bytes

由上述可以每個 Ethernet frame 最小為 64 Bytes ，最大為 1518 Bytes 。
另外在 Ethernet frame 有以下的動作：

若資料不足 46 Bytes 時，則會填充至 46 Bytes。
當資料過大，大於 1500 Bytes 時，會進行拆分傳輸，並且在接收端進行重組。
另外 FCS 則用於錯誤檢測，確保傳輸過程 frame 沒有遺失資料。

ICMP 封包大小？

參考於維基百科

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 →

圖片參考至 IT邦幫忙

注意術語，查閱國家教育研究院的雙語詞彙。

ICMP 封包由兩個主要部分組成： ICMP 頭和 ICMP 資料。這個 ICMP 封包通常嵌入在一個 IP 封包中，由 IP 頭封裝。

ICMP 頭
- 大小： 8 Bytes
- 內容：
  - Type ( 1 Byte ) ：表示 ICMP 類型，譬如：請求、回應等等
  - Code ( 1 Byte )：輔助定義 Type 的子類別
  - Checksum ( 2 Bytes )：檢測 ICMP 封包是否有錯誤
  - Rest of header ( 4 Bytes)：根據上述三種類別進行變化
ICMP 資料
- 大小：可變化，最低可以為 0 ，之後根據 RFC 791 ， IP 封包大小不能超過 576 Bytes 。且 IP 頭標準大小為 20 Bytes ， ICMP 頭為 8 Bytes ，因此資料最大為 548 Bytes
- 內容：回應主要內容為錯誤訊息

因此 ICMP 封包最小為 8 Bytes 。

TODO: 改進 kHTTPd

以 ktcp 的 kHTTPd 為基礎，提升其並行處理能力，予以量化並有效管理連線

引入 CMWQ ，並且分析效能

參考 ktcp 作業流程，將 CMWQ 引入至 khttp 中
整理過後的整體程式流程為：

建立 CMWQ
連線建立後建立 work，並將此 work 加入至 workqueue 進行管理
work 開始執行
work 結束時，釋放所有記憶體

減少非必要的縮排。

main.c
建立 CMWQ
在 khttp_init 中建立 workqueue 。

// create CMWQ
khttpd_wq = alloc_workqueue(MODULE_NAME, 0, 0);

http_server.h

使用 http_service 管理 workqueue ，http_request 管理 request ，workqueue 、 work 都使用 list_head 方式進行連接。

// manage  workqueue
struct httpd_service {
    bool is_stopped;
    struct list_head head;
};

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

http_server.c

建立 work : create_work
為每個連線請求進行 kernel space 的動態記憶體配置，並透過 INIT_WORK 為此請求進行初始化，再透過 list_add 加入至 workqueue 中

注意書寫規範：

程式碼註解不該出現中文，總是用美式英語書寫
使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致

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

    // alloc size of http_request 
    if (!(work = kmalloc(sizeof(struct http_request), GFP_KERNEL)))
        return NULL;

    work->socket = sk;

    // initialization work ，and 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 巨集走訪每個在 workqueue 中所管理的 work 。

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

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

在 http_server_daemon 中將上述兩個函式加入
主要為修改執行方式與釋放方式，原有的方法是使用 kthread_run 建立並執行，因此需要改成使用 create_work 建立 work 且使用 queue_work 來執行此請求，最終結束時將此 workqueue 設定為停止狀態，並且利用 free_work 進行記憶體釋放。

注意書寫規範：

程式碼註解不該出現中文，總是用美式英語書寫
使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致

     while (!kthread_should_stop()) {
         int err = kernel_accept(param->listen_socket, &socket, 0);
         if (err < 0) {
            nt http_server_daemon(void *arg)
             pr_err("kernel_accept() error: %d\n", err);
             continue;
         }
-        worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);
+        // Create worker by CMWQ
+        worker = create_work(socket);
         if (IS_ERR(worker)) {
             pr_err("can't create more worker process\n");
             continue;
         }
+        // start server workqueue
+        queue_work(khttpd_wq, worker);
     }
+    daemon_list.is_stopped = true;
+    free_work();

引入 CMWQ 之後，在處理 200000 的請求明顯可以在處理速度上加快了約 1.3 倍。

量化解釋改進的幅度，理論依據在哪？

origin:                                CMWQ:
requests:      200000                  requests:      200000
good requests: 200000 [100%]           good requests: 200000 [100%]
bad requests:  0 [0%]                  bad requests:  0 [0%]
socket errors: 0 [0%]                  socket errors: 0 [0%]
seconds:       3.597                   seconds:       2.741
requests/sec:  55594.719               requests/sec:  72953.615

提供目錄檔案存取功能

Directory list

主要流程：

進行 method 判斷。由於此功能設定為 GET，因此對於非 GET 方法，回傳 501 狀態。
判斷設定的路徑是否存在，若不存在則回傳 404 狀態。
判斷此路徑是否為資料夾，若是則走訪此資料夾；若是檔案，則讀取檔案內容。
3.1 由於在走訪過程中無法得知整體長度，因此需要在走訪過程中直接發送資料，而非等待全部走訪完成後再統一處理並傳送資料。

http_server.c
在 http_server 中新增兩個函式 handle_directory 與 tracedir 。
在 handle_directory 主要處理流程中的判斷與讀取檔案內容。

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


    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.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};
        request->dir_context.actor = tracedir;

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

directory 是「目錄」，而非「檔案夾」

在 tracedir 中，主要處理的為走訪~~資料夾~~ 中內容，並且在走訪的過程中就會進行傳送。

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, ".")) {
        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 true;
}

Initital Path

流程：

先在 main.c 裡面設定初始位置
在 handle_directory 中將 request url 與初始位置組合

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

在 http_server 中，新增處理路徑合併的函式 catstr ，並且在 handle_dirctory 中使用此函式

// http_server.c
static void catstr(char *res, char *first, char *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);
}

Use Chunk to send data

在不使用 chunk 作為傳輸的時候可能會出現以下問題：

高延遲
如果需要等待整個資料處理完畢後再進行傳輸，會產生較高的延遲，尤其是在資料量較大時，更容易發生此問題
記憶體壓力
由於需要等待資料處理完畢之後才進行送出，因此會占用需多記憶體空間，導致空間不足
錯誤處理困難
當在傳輸的過程中出現錯誤，此時就需要重新處理與傳輸，因此增加了處理的複查度與時間
使用體驗不佳
因為上述所提到的高延遲問題，會產生 client 需要等待全部的資料傳輸完成後，瀏覽器才能開始呈現，因此在使用體驗上會是不佳的狀態

那如何使用 chunk 進行傳輸？
只需要在 HTTP header 發送時，新增 Transfer-Encoding: chunked ，即可使用 chunk 傳輸，並且在最後傳送資料長度為 0 的資料，表示傳出完成。
之後在傳送資料的時候，需要先標示這次的資料長度為多少，並且以 16 進位表示。

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");
// When you use chunk to send Data, you need apply data length at start 
SEND_HTTP_MSG(request->socket, buf, "%s",
              "16\r\n</table></body></html>\r\n");

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

這次實作的 timer 是使用 Priority Queue 與 Min Heap 進行管理。
選擇使用 Min Heap 的主要原因為尋找最小值的時間複雜度為常數時間。因為在這種需要頻繁地去尋找最小值的特定狀況下，直接使用 Min Heap 進行管控，是一種最常使用的方法。

timer node 的結構如下：

key 儲存逾期的時間點，作為 Priority 使用
pos 儲存此 node 在 queue 中的位置

typedef struct {
    size_t key;
    size_t pos;  // the position of timer in queue
    timer_callback callback;
    struct socket *socket;
} timer_node_t;

timer 中主要的操作有以下：

handle_expired_timers
取得目前 timer 中 key 為最小值的 node，並且判斷是否已經逾期，若是則刪除，直到 queue 為空

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

http_timer_update
更新此 node 在 timer 中的 key 值，主要做於此 request 有新的請求時更新 timeout 的時間點

void http_timer_update(timer_node_t *node, size_t timeout)
{
    current_time_update();
    node->key = atomic_read(&current_msec) + timeout;
    // update new position
    node->pos = prio_queue_sink(&timer, node->pos);
}

http_add_timer
將新的 request 加入至 timer

bool http_add_timer(struct http_request *req, size_t timeout, timer_callback cb)
{
    timer_node_t *node = kmalloc(sizeof(timer_node_t), GFP_KERNEL);

    if (!node)
        return false;

    current_time_update();
    req->timer_item = node;
    node->key = atomic_read(&current_msec) + timeout;
    node->pos = atomic_read(&timer.nalloc) + 1;
    node->callback = cb;
    node->socket = req->socket;

    prio_queue_insert(&timer, node);
    return true;
}

整體的實作流程為：

初始化 timer
當初始化成功建立之後，程式會一直執行 handle_expired_timers
當建立 work 時，會執行 http_add_timer ，建立新的 timer node 並且放入 queue 中

如何驗證上述流程的效益？

目前的 kHTTPd 初步實作 HTTP 1.1 keep-alive，不過效率不彰，以 ftrace 一類的工具指出問題所在並改進

找出問題
以下是請求一次且從 ftrace 輸出中擷取的一部分：

  9)               |    http_parser_execute [khttpd]() {
  9)   0.464 us    |      http_parser_callback_headers_complete [khttpd]();
  9)   0.250 us    |      http_message_needs_eof [khttpd]();
  9)   0.272 us    |      http_should_keep_alive [khttpd]();
  9)               |      http_parser_callback_message_complete [khttpd]() {
  9)   0.289 us    |        http_should_keep_alive [khttpd]();
  9)               |        handle_directory [khttpd]() {
  9) + 15.485 us   |          filp_open();
  9) + 74.317 us   |          http_server_send.isra.0 [khttpd]();
  9) + 55.432 us   |          http_server_send.isra.0 [khttpd]();
  9) # 1270.662 us |          iterate_dir();
  9) + 30.469 us   |          http_server_send.isra.0 [khttpd]();
  9) + 40.951 us   |          http_server_send.isra.0 [khttpd]();
  9)   5.280 us    |          filp_close();
  9) # 1498.453 us |        }
  9)               |        _printk() {
  9) + 13.177 us   |          vprintk();
  9) + 13.739 us   |        }
  9) # 1513.489 us |      }
  9) # 1517.121 us |    }

由此可知，在每次的請求中所主要耗費在走訪目錄的過程，其次為傳送資料。

解決問題
由於走訪本身無法進行有效的改善，其時間複雜度為 O(n)，因此我使用 cache 的方式進行改善。
我的 cache 是利用 hashtable 的方式建立
結構為:
我主要 url 作為 index 進行尋找，且紀錄原本 response 的資料。

struct cache_item {
    char request_url[128];   
    char response_data[4096]; 
    size_t response_size;    
    size_t max_size;         
    struct hlist_node node;  
};

主要操作如下：

cahce_lookup

struct cache_item *cache_lookup(const char *url)
{
    struct cache_item *item;
    u32 key = hash_fn(url);

    hash_for_each_possible(cache_table, item, node, key) {
        if (strcmp(item->request_url, url) == 0) {
            return item;
        }
    }
    return NULL;
}

cache_create_item

struct cache_item *cache_create_item(const char *url)
{
    struct cache_item *item = kmalloc(sizeof(struct cache_item), GFP_KERNEL);
    if (!item) {
        pr_err("Failed to allocate memory for cache_item\n");
        return NULL;
    }

    strncpy(item->request_url, url, sizeof(item->request_url));
    memset(item->response_data, 0, sizeof(item->response_data));
    item->response_size = 0;
    item->max_size = sizeof(item->response_data); 

    return item;
}

cache_insert

int cache_insert(const char *url, const char *response_data)
{
    struct cache_item *item;
    u32 key = hash_fn(url);

    item = cache_lookup(url);
    if (item) {
        memset(item->response_data, 0, sizeof(item->response_data));
        strncat(item->response_data, response_data, sizeof(item->response_data) - 1);
        item->response_size = strlen(item->response_data);
        return 0;
    }

    item = cache_create_item(url);
    if (!item) {
        return -ENOMEM;
    }

    strncat(item->response_data, response_data, sizeof(item->response_data) - 1);
    item->response_size = strlen(item->response_data);
    hash_add(cache_table, &item->node, key);
    return 0;
}

主要流程為：

先進行初始化
在進入 handle_directory 之前，先尋找在 hashtable 中是否有 request url
2_1. 若有則回傳以記錄的 response data
2_2. 否則進行下一步
執行 handle_directory
在執行傳送資料之前先將資料儲存至 cache 中

實作結果
可以看到在重複請求同樣網址時，可以有效提升處理速度

原本實做                         實作 cache
requests:      20000            requests:      20000
good requests: 20000 [100%]     good requests: 20000 [100%]
bad requests:  0 [0%]           bad requests:  0 [0%]
socket errors: 0 [0%]           socket errors: 0 [0%]
seconds:       5.787            seconds:       0.977
requests/sec:  3455.947         requests/sec:  20471.835

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

在原有的設計上，會因為有大量的記憶體配置請求，每次 kernel 處理記憶體配置時，會需要保證其餘程式的安全，所以需要一定的時間處理該請求，因此會耗費大量的時間，並且當長時間的配置與釋放記憶體空間，會造成記憶體空間破碎化。
因為以上的原因，才使用 memcache 進行統一的記憶體空間管理。由於 memcache 只作為提供空間與數量管理的機制，因此需要將 LRU 加入至 hashtable 。

為何引入 LRU 會有幫助？你的理論依據是什麼？建立統計模型來探討。

主要操作如下：

減少非必要的縮排。

memcache_create
此函式為 memcache 初始化，主要是配置整體大小並且將此空間切分為數份 obj_size 的 element 後將 element 加入至 memcache

struct memcache *memcache_create(size_t obj_size, int max_cache_size)
{
    struct memcache *cache;
    size_t size;
    void *element;

    size = sizeof(struct memcache) + max_cache_size * sizeof(void *);
    cache = kmalloc(size, GFP_KERNEL);
    if (!cache)
        return NULL;

    cache->elements = (void **)((char *)cache + sizeof(struct memcache));
    cache->obj_size = obj_size;
    cache->cache_size = max_cache_size;
    cache->curr = 0;
    INIT_LIST_HEAD(&cache->lru_list);

    max_cache_size >>= 2;
    while (cache->curr < max_cache_size) {
        element = kmalloc(cache->obj_size, GFP_KERNEL);
        if (!element) {
            free_pool(cache);
            return NULL;
        }
        add_element(cache, element);
    }

    return cache;
}

memcache_alloc
主要為若 memcache 還有空間數量可以分配時則回傳開空間大小，否則再次配置

void *memcache_alloc(struct memcache *cache)
{
    return (cache->curr) ? remove_element(cache) : kmalloc(cache->obj_size, GFP_KERNEL);
}

整體流程為：

在 hashtable 初始化時，建立 memcache
在建立新的 hashtable 節點時，從 memcache 進行配置，並且將此節點放入置 LRU ，若進行配置時存在數量已超過最大值時則刪除最舊的節點
在尋找或插入 hashtable 節點時，會將此節點放入至 LRU 的最前方

TODO: 探討 eBPF 對於網頁伺服器開發的作用

量化 Linux 核心網路的行為

參考 fatcatorange 與使用 matplotlib 實施可視化分析，撰寫以下程式：

from bcc import BPF
import matplotlib.pyplot as plt

# eBPF 程序
code = """
#include <uapi/linux/ptrace.h>

BPF_HASH(start, u32, u64); 

int probe_handler(struct pt_regs *ctx)
{
    u64 ts = bpf_ktime_get_ns();
    u32 tgid = bpf_get_current_pid_tgid();
    start.update(&tgid, &ts);  
    return 0;
}

int end_function(struct pt_regs *ctx)
{
    u64 ts = bpf_ktime_get_ns();
    u32 tgid = bpf_get_current_pid_tgid();
    u64 *start_ts = start.lookup(&tgid); 
    if (start_ts) {
        bpf_trace_printk("duration: %llu\\n", ts - *start_ts); 
        start.delete(&tgid);  
    }
    return 0;
}
"""

# 初始化 eBPF
b = BPF(text=code)
b.attach_kprobe(event='handle_directory', fn_name='probe_handler')
b.attach_kretprobe(event='handle_directory', fn_name='end_function')

durations = []

# 捕获数据并保存到 durations 列表中
print("Capturing durations... Press Ctrl+C to stop.")
try:
    while True:
        (task, pid, cpu, flags, ts, msg) = b.trace_fields()
        duration = int(msg.split()[1])
        durations.append(duration)
        print(f"Captured duration: {duration}")
except KeyboardInterrupt:
    print("Stopping capture...")

# 生成折线图
plt.figure(figsize=(10, 5))
plt.plot(durations, marker='*', color='purple', markersize=3)
plt.title('Duration over time')
plt.xlabel('Sample number')
plt.ylabel('Duration (ns)')
plt.grid(True)
plt.savefig('durations_plot.png')
plt.show()

注意書寫規範：

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

我選擇 handle_directory 作為量化目標，選擇此函式的原因是因為每次的請求都會進入此函式，並且根據上方 ftrace 的結果，得知此處是整個系統中最耗時的區域。

完成上方的改進 kHTTPd 之後，進行了 1000 、 10000 與 100000 次的連續請求，並完成以下的折線圖，以便後須觀察。

1000
10000
100000

從折線圖中可以看出， handle_directory 函式的執行時間在不同的請求次數下表現出相對穩定的趨勢。具體分析如下：

1000 次請求：在 1000 次請求下，handle_directory 函數的執行時間較為穩定，只有少數幾個數據點出現較大的波動。
10000 次請求：在 10000 次請求下，執行時間的波動稍有增加，但整體趨勢仍然較為穩定，顯示出系統在較大負載下的穩定性。
100000 次請求：在 100000 次請求下，執行時間的波動性進一步增加，但總體上系統仍然保持穩定，沒有出現隨著時間推移或其他因素導致的處理成本顯著上升的情況。

「執行時間的波動」的成因是什麼？

整體來看，函式在不同請求次數下的表現相對穩定，並未因為時間的推移或其他因素導致處理成本顯著上升。