Try   HackMD

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

執行人: Ackerman666
專題解說錄影

Reviewed by SuNsHiNe-75

關於「疑問：eBPF 壞掉應該是虛擬機器直接損毀，為什麼還會影響到 Kernel」問題，我認為有可能是該「有問題的 eBPF」程式使用一些手/寫法讓 Verifier 檢查不出問題而通過並注入核心，並在其中透過「設計不當」之程式損毀 Kernel（如消耗記憶體或 CPU 資源等）。

了解 感謝你提出這個看法 !

任務簡介

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

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

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

TODO: 自我檢查清單

https://hackmd.io/@sysprog/linux2024-ktcp-e

回答上述「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳。

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

RCU 原始碼

RCU 是 Linux 核心同步機制方法之一，可在不使用 lock 的情況下允許多個 Reader 在單一 Writer 更新資料的同時，也可正確的讀取資料。實做方式是透過維持多個版本資料，也就是同時有多個 Reader 可看到不同版本資料，但保證下一次讀取資料時，會讀取到最新的資料。

適用情境 : 頻繁讀取 (多個 Reader ) 但資料不頻繁寫入 (少量的 Updater/Writer) 的情境

RCU 設計方式

RCU 中 Updater 和 Reader 之間關係可用 Publisher 和 Subscriber 來描述。
Updater 進行內容更新後，會呼叫指定介面進行發布，Reader 呼叫特定介面來讀取最新發布內容。

Grace Period

Updater 更新資料後會發布新資料， 但此時不會立刻刪除舊資料，而是等待先前讀取舊資料的 Reader 讀取完畢後再執行銷毀操作，中間歷經的時間就稱為 Grace Period。

以下圖為例，t1 時間點發生寫入動作，t2 時間點完成寫入。但舊資料對 Reader3 而言在 t3 這個時間點才會完全讀取完畢，因此 Updater 必須等待 t2 至 t3 這段時間能銷毀舊資料。

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 →

RCU's grace-period guarantee allows updaters to wait for the completion of all pre-existing RCU read-side critical sections
A Tour Through RCU's Requirements

Updater

可透過 rcu_assign_pointer(p, v) 發布新資料 v 至受保護的指標 p

Assigns the specified value to the specified RCU-protected pointer, ensuring that any concurrent RCU readers will see any prior initialization.
可保證 reader 讀取的資料 v 是完成初始化的， 且之後 reader 讀取的值也是最新的

Updater 更新資料後會用 synchronize_rcu() 等待 Grace Period 結束，然後 Updater 再執行下一步操作 (kfree() 清空舊的資料等)。

Reader

可透過 rcu_dereference(p) 讀取到指標 p 的內容

Reader 可用 rcu_read_lock 和 rcu_read_unlock 標記出 read-side critical sections。Updaters 更新時會追蹤此 critical sections，等到沒有 Reader reference 時，就會啟動 Reclamation (如 Quiescent State-Based Reclamation )

經典 RCU 機制中，Reader 進到 read-side critical sections 時無法被 preemptive 也不能 sleep

疑問 : 為何經典 RCU 禁止搶佔

現在想到的解釋是搶佔會觸發 interrupt, 就會執行 context switch, 而這些都需要成本。如此當有頻繁發生搶佔時, 讀取端效能會不好。(但在一些即時系統, 高優先權任務還是需要先處理, 就可改採搶佔式的 RCU)

git log 有一系列討論，搭配 git blame 探討

顧及 memory ordering 的影響

以往用 lock 處理同步問題時，核心會處理 memory ordering 議題，但在 RCU 中，由於沒有 lock，因此需要自行處理。其中一個解決 memory ordering 解法為 memory barrier，而 RCU 機制已有對 memory barrier 進行包裝，提供了專門的 API 來解決該問題 (如 rcu_assign_pointer）

#define rcu_assign_pointer(p, v)					      \
do {									      \
    uintptr_t _r_a_p__v = (uintptr_t)(v);				      \
    rcu_check_sparse(p, __rcu);					      \
    								      \
    if (__builtin_constant_p(v) && (_r_a_p__v) == (uintptr_t)NULL)	      \
        WRITE_ONCE((p), (typeof(p))(_r_a_p__v));		      \
    else								      \
        smp_store_release(&p, RCU_INITIALIZER((typeof(p))_r_a_p__v)); \
} while (0)

觀察實做可看到加了 WRITE_ONCE memory barrier 機制來確保程式碼執行順序。

研讀 透過 eBPF 觀察作業系統行為

eBPF (Extended BPF) 為 Linux 核心內建內部行為分析工具，前身是 Berkeley Packet Filter (BPF) (最初拿來處理封包過濾機制)。

使用者層級 (user mode) 會準備好 BPF/eBPF 程式碼，並編譯對應 bytecode，最後會在核心內部專屬的虛擬機器上進行，達到從底層分析系統的效果。

相較古典的 classical BPF(cBPF)，eBPF 透過 map 機制來讓使用者層級與核心內部有塊共享的空間來互動。而 cBPF 使用者層級要取得分析資料時，則需仰賴系統呼叫將資料從核心複製到使用者層級，因此可知 eBPF 在效率上會來的較好。

eBPF 引入 verifier 機制，在注入程式前，會進行一系列檢查，避免注入危險的程式進而損壞 kernel

疑問 : eBPF壞掉應該是虛擬機器直接損毀，為什麼還會影響到 kernel ?

注意用語：

  • virtual machine 應翻譯為「虛擬機器」，而非簡略的「虛擬機」，用來區分 motor/engine (發動機) 在漢語常見的翻譯詞「機」。

已更正

Linux 基金會之中的專案 IO Visor，開發了 BPF Compiler Collection (BCC)。可使開發者專注於 C 語言注入於核心的邏輯、流程與編譯。載入 BPF 代碼及建立 map 等事項可交由 BCC 處理完成。在 BCC 中也可搭配 python 進行更彈性的處理 (如記錄的資料視覺化等)。

BCC 用法筆記可參考 0xff07 筆記

TIME-WAIT sockets

RFC 9293 (目前找到最新關於 TCP 標準的文件)

TCP 標準制定了多種狀態用來處理連線過程

A connection progresses through a series of states during its lifetime. The states are: LISTEN, SYN-SENT, SYN-RECEIVED, ESTABLISHED, FIN-WAIT-1, FIN-WAIT-2, CLOSE-WAIT, CLOSING, LAST-ACK, TIME-WAIT, and the fictional state CLOSED
State Machine Overview

TIME-WAIT 即是處理斷線的狀態之一。

TIME-WAIT -
represents waiting for enough time to pass to be sure the remote TCP peer received the acknowledgment of its connection termination request and to avoid new connections being impacted by delayed segments from previous connections.

斷線有分以下兩種

  1. Normal Close (斷線由兩方的其中一方先發起)
  2. Simultaneous Close (斷線由兩方同時發起)

這邊簡述 Normal Close 的流程 (假定現有 Pear A 與 Pear B 正進行連線)

​​​​TCP Peer A                                        TCP Peer B
​​​​1.  ESTABLISHED Connection                        ESTABLISHED Connection  (雙方正進行連線)
​​​​
​​​​2.  FIN-WAIT-1            -------> FIN ------->   CLOSE-WAIT
​​​​    (Peer A 發起斷線請求，進入 FIN-WAIT-1)           (Peer B 收到請求後進入 CLOSE-WAIT)
​​​​3.  FIN-WAIT-2            <------- ACK <-------   CLOSE-WAIT
​​​​    (收到 ACK，進入 FIN-WAIT-2)                     (進入 CLOSE-WAIT 後發送 ACK)
​​​​4.  TIME-WAIT             <------- FIN <-------   LAST-ACK
​​​​    (收到 FIN 進入 TIME-WAIT)                      (Peer B 完成斷線請求後發送 FIN，並進入 LAST-ACK)
​​​​5.  TIME-WAIT             -------> ACK ------->   CLOSED
​​​​    (進入 TIME-WAIT 後發送 ACK)                    (收到 ACK, Peer B 完成斷線)
​​​​    .
​​​​    .
​​​​    .
​​​​    CLOSED
​​​​    (TIME-WAIT 時間到，Peer A 完成斷線)

上述流程可以看到 Peer A 會在 TIME-WAIT 狀態等待一段時間後才進行 CLOSED。原因是透過一段時間的等待，來確保遠端有收到 ACK 並關閉連線。在 TIME-WAIT 期間內，如果 ACK 遺失了，發送端則可繼續重傳 ACK。

TIME-WAIT 等待時間為 2 倍 MSL (Maximum Segment Lifetime)，常見為 30 秒，1 分鐘和 2 分鐘。

Maximum segment lifetime is the time a TCP segment can exist in the internetwork system. MSL : TCP 分段可存在於網際網路系統中的最大時間
Maximum segment lifetime

為何使用 TIME-WAIT 確保連線關閉 :
如沒此機制，Pear A 斷線後可能立馬開啟新的連線請求至 Pear B，但如果 Pear B 尚未收到 ACK，那麼 Pear B 會認為舊的連線還是合法的，進而會發起 RST 終止發起的連線。TIME-WAIT 可以有效避免上述情況，使新連線可正常被接受。

RST (Reset) : control bit 的一種，用來立即終止不正常的TCP連接

ref:
TCP協定的TIME_WAIT狀態
TCP Connection Termination
TCP 連線狀態機制與流程

TIME_WAIT 相關議題 :
Server 能處理 TCP 連線的 Socket 有限，如果 Server 端有過多 TIME_WAIT 狀態連線存在。表示當前有許多連線尚未關閉，也就是對應 Socket 無法被重新使用，那麼就有可能影響 Server 的處理效能。此時可藉由調低 TIME_WAIT 來處理更多連線的情境。

drop-tcp-socket 原理 : eric88525 的筆記

TODO: 引入 CMWQ 改寫 kHTTPd

分析效能表現和提出改進方案
嘗試提交 pull request

用 eBPF 測量 kthread / CMWQ 關鍵操作的執行成本

安裝 ebpf

sudo apt-get install bpfcc-tools linux-headers-$(uname -r)

區分「函數」和「函式」，務必詳閱 https://hackmd.io/@sysprog/it-vocabulary

已更正

列出當前核心中可用的函式名稱， 來看有哪些函式可以被追蹤。

    cat /sys/kernel/debug/tracing/available_filter_functions

http_server_daemon 函式負責連線的處理，其中用到 kthread_run 建立執行緒執行 http_server_worker 處理連線後 client 送來的請求。這邊用 ebpf 追蹤 http_server_daemon 來測量 kthread 操作的執行成本。

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

event_function = "http_server_daemon"

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


filename = 'kthread_run_cost.txt'
with open(filename, 'a') as file:
    while True:
        try:
            res = b.trace_fields()
            file.write(res[5].decode("UTF-8") + '\n')
            file.flush()
        except ValueError:
            continue

程式碼參考自 2024 年 Linux 核心設計/實作課程作業 —— kecho + khttpd

執行以上程式碼進行測試，發現 http_server_daemon 無法被正常追蹤，原因尚未有想法。

發現 vax-r 同學是將 kthread_run 額外包在一個函式中，再讓 http_server_daemon 呼叫此函式，如此便可追蹤該函式，進而追蹤 kthread 操作執行成本。

參考該同學的寫法，將 http_server_daemon 會使用到的 kthread_run 執行在 handle_client_request 中。

使用指定的程式碼縮排風格，如同 lab0-c

// if success run, return 1, otherwise return 0
int handle_client_request(void *arg){

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

    kfree(buf);

    struct task_struct *worker = kthread_run(http_server_worker, arg, KBUILD_MODNAME);
    if (IS_ERR(worker))
        return 0;

    return 1;
}

event_function = "handle_client_request" 即可追蹤進入與退出 kthread_run 的時間點。

-event_function = "http_server_daemon"
+event_function = "handle_client_request"

執行 20 萬筆連線進行壓力測試

​​​​./htstress -n 200000 -c 1 -t 4 http://localhost:8081/

image

大部份執行 kthread_run 成本皆在 0.5us 以下，但可觀察到當連線次數大於 25000 次時，kthread_run 的執行時間會有明顯的增加。這部份是因 kthread_run 執行時會重新建立執行緒，導致同時連線次數過多時，反覆製造執行緒的時間開銷會變大。

commit : 52ba6f0

kthread 的一些用法

注意書寫規範：

  • 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","

kthread_run 是一個巨集，定義在 include/linux/kthread.h
巨集中由 kthread_create 建立執行緒，成功時會透過 wake_up_process 喚醒執行緒執行任務。

kthread_stop 是一個函式，定義在 linux/kernel/kthread.c
呼叫 kthread_stop 會去設定 KTHREAD_SHOULD_STOP，並等待執行緒結束。

Sets kthread_should_stop() for @k to return true, wakes it, and waits for it to exit.
This can also be called after kthread_create() instead of calling wake_up_process(): the thread will exit without calling threadfn().

kthread_should_stop 也是一個函式，回傳 KTHREAD_SHOULD_STOP 是否被設定。當執行緒呼叫 kthread_should_stop 時，就可知道是否應該要繼續執行亦或停止。

kthread_stop 在執行緒中呼叫時，可能發生 block 的窘境。因 kthread_stop 會等待執行緒結束， 所以在執行緒裡面呼叫，就會被 block 住，無法執行到下方結束執行緒的程式碼。
Is it neccessary to use kthread_stop if we return from kernel thread?

引入 Concurrency Managed Workqueue (cmwq)，改寫 kHTTPd

原版 http_server_daemon 會呼叫 handle_client_request， handle_client_request 又呼叫 kthread_run 建立新執行續執行 http_server_worker 處理 client 連線後所送的訊息。

這邊透過 CMWQ 機制取代 handle_client_request 中的 kthread_run

以下建立 CMWQ 方式參考 ksort
CMWQ筆記

目標是建立 work item 用來執行 http_server_worker，而原版的 http_server_worker 會使用傳入的 socket 來做接受訊息的處理。

因此我定義 request_handler 結構，w 為要執行的 work item，socket 為 client 所連的 socket。

哪來的「用戶」？

已更正

struct request_handler {
    struct work_struct w;
    void *socket;
};

將 handle_client_request 改寫如下

int handle_client_request(void *arg, struct workqueue_struct *workqueue)
{

    struct request_handler *handler = kmalloc(sizeof(struct request_handler), GFP_KERNEL);
    handler->socket = arg;
    INIT_WORK(&handler->w, http_server_worker);
    if (queue_work(workqueue, &handler->w) == 0){
        pr_err("work was already on a queue.");
        return 0;
    }
    return 1;
}

allocate 是「配置」，而非「分配」，以區隔 dispatch 的翻譯。

已更正

利用 kmalloc 配置 一塊空間給 handler。handler 進行 socket 指定並透過 INIT_WORK 設定 handler 要處理的 work item 為 http_server_worker。最後透過 queue_work 將 work item 加進 workqueue 中等待執行。

kmalloc 申請空間在實體記憶體上為連續，需設定 GFP flags，常見有下面兩種

  • GFP_KERNEL : 記憶體無空間可配置時，context 可進行 sleep，直到有空間可進行配置 (適用於大部份情境)
  • GFP_atomic : context 不會進行 sleep，如無可配置空間即會立刻回傳錯誤 (適用於需即時處理的情況, 如 interrupt)

在電腦科學中，任務（task）的上下文（英語：context）是一個任務所必不可少的一組資料（該任務可以是行程、執行緒）上下文 (電腦)

執行壓力測試 (20 萬請求)

​​​​CMWQ                                               Kthread

​​​​0 requests                                         0 requests
​​​​20000 requests                                     20000 requests
​​​​40000 requests                                     40000 requests
​​​​60000 requests                                     60000 requests
​​​​80000 requests                                     80000 requests
​​​​100000 requests                                    100000 requests
​​​​120000 requests                                    120000 requests
​​​​140000 requests                                    140000 requests
​​​​160000 requests                                    160000 requests
​​​​180000 requests                                    180000 requests

​​​​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:       1.965                               seconds:       3.077
​​​​requests/sec:  101779.254                          requests/sec:  64994.615

用 ebpf 觀察 CMWQ 執行成本，因是在 handle_client_request 初始化 work item 並加入 workqueue, 所以將偵測事件設定在該函式。

image

大部份執行時間皆在 0.25us 以下, 可看出 CMWQ 執行效率會較 kthread 來得佳，於壓力測試下也快了 1.5 倍左右。

主因是 CMWQ 使用 thread pool 概念，不用重新建立新的 kthread 來處理任務，只要在 client 連線時將 work 配置給空閒的執行緒來進行，如此可省去建立 kthread 所需的花費，能更有效率的處理大量連線的情況。

在現今網頁伺服器與資料庫管理系統，如 NGINX 和 MySQL 也皆使用到了 thread pool 概念來處理 client connection

在 The New MySQL Thread Pool 提到 MySQL 8.0 使用 thread pool 與 Max Transaction Limit 來處理大量連線。
Max Transaction Limit 意思是不會無限制的接受請求，而是限制能同時並行的 transaction 數量。限制此數量的好處在於可避免使用太多 concurrent data locks，進而拖累系統效率。

使用 kthread 處理連線作法是 TPC (Thread Per Connection) 雖然 TPC 實作簡單，但卻無法有效用於高併發場合 (反覆建立執行緒耗費資源)。 > TPC 觀念可參考 : [[架構設計] 單一 Server 高效能模式](https://godleon.github.io/blog/Architecture_Design/Architecture-Design-High-Performance-single-server/)

為何不參閱課程教材呢？
https://hackmd.io/@sysprog/linux-io-model

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

原本功能是 client 送出 HTTP_GET 請求後, http_server_response 函式會回傳 Hello World!, 這邊我將邏輯改成執行 directory_listing 來回傳目錄中所列出的檔案。

-    if (request->method != HTTP_GET)
-        response = keep_alive ? HTTP_RESPONSE_501_KEEPALIVE : HTTP_RESPONSE_501;
+    if (request->method != HTTP_GET) {
+        char *response =
+            keep_alive ? HTTP_RESPONSE_501_KEEPALIVE : HTTP_RESPONSE_501;
+        http_server_send(request->socket, response, strlen(response));
+    }
    
    else
-        response = keep_alive ? HTTP_RESPONSE_200_KEEPALIVE_DUMMY : HTTP_RESPONSE_200_DUMMY;
-    http_server_send(request->socket, response, strlen(response));
+        directory_listing(request);

Linux 核心提供 iterate_dir 函式，用來逐一走訪指定目錄中的每個項目。參數用到以下兩個結構。

  • struct file : 代表目前已開啟的檔案
  • struct dir_context : 透過 actor 設定處理目錄項目時會呼叫到的函式，pos 紀錄當前目錄讀寫的位置，定義如下。
struct dir_context {
    filldir_t actor; 
    loff_t pos;      
};

程式邏輯中檔案 file 會判斷是否有 iterate_shared 方法，並在通過一系列條件檢查後， 執行 file->f_op->iterate_shared(file, ctx)。

iterate_shared 是 VFS 提供的介面，以此來對 file 進行目錄的走訪。 iterate_shared 會呼叫 ctx 的 actor 對每個走訪到的項目執行指定的操作。

iterate_shared: called when the VFS needs to read the directory contents when filesystem supports concurrent dir iterators Overview of the Linux Virtual File System

int iterate_dir(struct file *file, struct dir_context *ctx)
{
	struct inode *inode = file_inode(file);
	int res = -ENOTDIR;

	if (!file->f_op->iterate_shared)
		goto out;

	res = security_file_permission(file, MAY_READ);
	if (res)
		goto out;

	res = fsnotify_file_perm(file, MAY_READ);
	if (res)
		goto out;

	res = down_read_killable(&inode->i_rwsem);
	if (res)
		goto out;

	res = -ENOENT;
	if (!IS_DEADDIR(inode)) {
		ctx->pos = file->f_pos;
		res = file->f_op->iterate_shared(file, ctx);
		file->f_pos = ctx->pos;
		fsnotify_access(file);
		file_accessed(file);
	}
	inode_unlock_shared(inode);
out:
	return res;
}

我定義 dir_tracer 結構用來存放 dir_context 與 socket

struct dir_tracer {
    struct dir_context dir_context;
    struct socket *socket;
};

在 directory_listing 中設定 d_tracer 的 actor 為 trace_directory (說明會在下面補充)，並將 request 的 socket 存放進 d_tracer.socket。
接著透過 filp_open 打開目錄 fp，並用 iterate_dir 走訪整個目錄。

static void directory_listing(struct http_request *request)
{
    struct dir_tracer d_tracer = {
        .dir_context =
            {
                .actor = trace_directory,
            },
        .socket = request->socket,
    };

    struct file *fp;
    char buf[SEND_BUFFER_SIZE] = {0};

    fp = filp_open("/home/xiang/Desktop/linux2024/khttpd", O_RDONLY, 0);

    if (IS_ERR(fp)) {
        pr_info("Open file failed");
        return;
    }

    snprintf(buf, SEND_BUFFER_SIZE, HTTP_RESPONSE_200_KEEPALIVE_HTML);
    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, &d_tracer.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;
}

走訪的過程會呼叫 d_tracer 成員 dir_context 的 actor。這邊的 actor 指向的是 trace_directory。而 actor 的宣告為 filldir_t, 因此 trace_directory 函式 格式要符合以下規範。

typedef int (*filldir_t)(struct dir_context *, const char *, int, loff_t, u64, unsigned);

在 trace_directory 中，name 代表的是目錄中的檔案名稱。在這邊只要是名稱不為 "." 與 ".."，就會透過 container_of 拿到擁有 dir_context 的 dir_tracer。並透過裡面所紀錄的 socket 去對 client 發送檔案名稱的訊息。

static bool trace_directory(struct dir_context *dir_context,
                            const char *name,
                            int name_size,
                            loff_t offset,
                            u64 ino,
                            unsigned int d_type)
{
    //"." represents the current directory, ".." represents the parent
    // directory, and neither of them will be displayed.
    if (strcmp(name, ".") && strcmp(name, "..")) {
        struct dir_tracer *tracer =
            container_of(dir_context, struct dir_tracer, 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(tracer->socket, buf, strlen(buf));
    }

    return true;
}

commit b66ddb4

結果如下

image

以 Ftrace (《Demystifying the Linux CPU Scheduler》第六章介紹過) 分析上述涉及 VFS 操作的執行成本。

涉及 VFS 操作函式於 directory_listing 中，在下文有透過 Ftrace 追蹤 http_server_worker，進而觀測執行 directory_listing 的成本。

改用分塊傳輸編碼(Chunked transfer encoding) 來傳送目錄列表

分塊傳輸編碼

分塊傳輸編碼只在 HTTP/1.1 提供。通常，回應 HTTP 訊息傳送的資料是整個傳送，而 Header 的 Content-Length 欄位代表資料的長度。但伺服器有時回傳的資料是動態決定的，並無法事先知道資料長度，此時可在 Header 加入 Transfer-Encoding : chunked 啟動分塊傳輸編碼。概念是將資料分解成多個資料塊來傳送。如此，伺服器可傳送資料且無需先知道傳送內容的大小。

分塊傳輸編碼格式 :

  • 非空資料塊 : 資料塊大小(16進位) + CRLF + 資料本身 + CRLF
  • 空資料塊 : 0 + CRLF + CRLF

定義 HTTP_RESPONSE_200_CHUNKED_KEEPALIVE 來代表使用分塊傳輸編碼的 Http Header

#define HTTP_RESPONSE_200_CHUNKED_KEEPALIVE                   \
    ""                                                        \
    "HTTP/1.1 200 OK" CRLF "Server: " KBUILD_MODNAME CRLF     \
    "Content-Type: %s" CRLF "Transfer-Encoding: chunked" CRLF \
    "Connection: Keep-Alive" CRLF CRLF

把 directory_listing 回傳的 Header 設定成 HTTP_RESPONSE_200_CHUNKED_KEEPALIVE。並透過 snprintf 將 "text/html" 根據格式整合到 Header 字串，使回傳資料的型別可被瀏覽器解讀成 html 格式。

// set http header
- snprintf(buf, SEND_BUFFER_SIZE, HTTP_RESPONSE_200_KEEPALIVE_HTML);
+ snprintf(buf, SEND_BUFFER_SIZE, HTTP_RESPONSE_200_CHUNKED_KEEPALIVE, "text/html");

分塊傳輸編碼規定傳輸時必須標示資料塊大小。因此對 trace_directory 做以下改動。使回傳目錄項目資料塊前，有確實計算資料塊大小並回傳。

 char buf[SEND_BUFFER_SIZE] = {0};
+char chunk_header[10] = {0};
+unsigned long chunk_size;

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

+// Calculate chunk size
+chunk_size = strlen(buf);
+// Prepare chunk header
+snprintf(chunk_header, sizeof(chunk_header), "%lx\r\n", chunk_size);
+// Send chunk header
+http_server_send(tracer->socket, chunk_header, strlen(chunk_header));
+// Send chunk data
+http_server_send(tracer->socket, buf, chunk_size);
+// Send CRLF
+http_server_send(tracer->socket, CRLF, strlen(CRLF));

使用 MIME 來傳輸不同類型的檔案

多用途網際網路郵件延伸（也稱為MIME）是一種識別不同類型資訊的標準。 MIME 原本作為電子郵件的延伸規格，但也可供 HTTP 用來定義伺服器分送的內容。MIME 類型

MIME 用來標示網路上送出內容的類型。對瀏覽器而言，接收正確 MIME 類型可正確辨別資料型態，並進一步做出正確的回應 (如顯示影像、網頁等)。

參考 Risheng1128 方法，建立 mime_type.h 紀錄常見的 MIME 類型。

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"},
    {".avi", "video/x-msvideo"},
    {".azw", "application/vnd.amazon.ebook"},
    {".bin", "application/octet-stream"},
    {".bmp", "image/bmp"},
    ...
}

並可透過 get_mime_str 根據給定的檔案回傳對應的 MIME 類型。

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

原版是透過逐一搜尋來找到對應的 MIME 類型，但當有大量請求要看檔案時，這種方式顯然不佳，而我認為可用二元搜尋或 Hash 方式改進。

顯示檔案內容

在核心中，檔案的屬性由結構 inode 所管理，這邊會使用到其成員 i_mode 及 i_size ，前者表示檔案類型，後者表示檔案大小。

indoe 定義在 include/linux/fs.h

在 http_server_response 中透過 S_ISDIR 與 S_ISREG 判斷檔案為目錄或是 Regular File，並分別執行對應函式。

Regular files are the most common files and are used to contain data. Regular files are in the form of text files or binary files: Types of files

// response directory list
else if (S_ISDIR(fp->f_inode->i_mode)) {
    directory_listing(request, fp);
}

// response file content
else if (S_ISREG(fp->f_inode->i_mode)) {
    file_content_response(request, fp);
}

file_content_response 用來傳送檔案內容。首先透過 fp->f_inode->i_size 取得檔案大小配置記憶體空間後，再透過 kernel_read 讀取檔案資訊。用snprintf 將 MIME 類型與檔案大小資訊一併寫入 Http Header 中，並回傳檔案給 client。

static int file_content_response(struct http_request *request, struct file *fp)
{
    char *read_data = kmalloc(fp->f_inode->i_size, GFP_KERNEL);
    int ret = kernel_read(fp, read_data, fp->f_inode->i_size, 0);
    char buf[SEND_BUFFER_SIZE] = {0};

    snprintf(buf, SEND_BUFFER_SIZE, HTTP_RESPONSE_200_KEEPALIVE,
             get_mime_str(request->request_url), ret);
    http_server_send(request->socket, buf, strlen(buf));
    http_server_send(request->socket, read_data, ret);

    kfree(read_data);
    return 0;
}

因有在 server 加入 MIME 類型判斷機制，瀏覽器可顯示文字檔與圖像。

image

image

commit b66ddb4

處理 kernel NULL pointer dereference

每次在瀏覽器測試伺服器時，khttp 常遇到 reference NULL pointer 的狀況，導致整個模組故障無法正常移除 (為此我重開機好多次…)。

​​​​[  181.444424] BUG: kernel NULL pointer dereference, address: 0000000000000016
​​​​[  181.444426] #PF: supervisor read access in kernel mode
​​​​[  181.444428] #PF: error_code(0x0000) - not-present page
​​​​[  181.444429] PGD 0 P4D 0 
​​​​[  181.444431] Oops: 0000 [#1] PREEMPT SMP NOPTI
​​​​[  181.444434] CPU: 15 PID: 635 Comm: kworker/15:2 Tainted: G        W  OE      6.5.0-41-generic #41~22.04.2-Ubuntu
​​​​[  181.444436] Hardware name: ASUSTeK COMPUTER INC. ASUS EXPERTCENTER D900TA_M900TA/D900TA, BIOS D900TA.305 06/03/2021
​​​​[  181.444437] Workqueue: khttp http_server_worker [khttpd]
​​​​[  181.444445] RIP: 0010:filp_close+0x11/0xa0

根據訊息，可觀察到錯誤是發生在 filp_close 上，而呼叫該函式是發生在 http_server_response 內。

int filp_close(struct file *filp, fl_owner_t id)

filp_close 定義在 linux/fs/open.c

看原始碼可發現 filp_close 會呼叫到 filp_flush ，filp_flush 又會有 cfilp->f_op->flush` 此類的操作。因此傳入的 flip 不能是空指標或無效指標。

指標分三種 : 合法指標, 空指標, 無效指標。其中無效指標是指向核心空間最後一個 page 上面
( 通常無效指針會指向錯誤代碼 可用 PTR_ERR 來返回錯誤代碼 )

程式碼中 filp_open 得到檔案的指標後，會做 IS_ERR(fp) 檢查，判斷是否為無效指標。

IS_ERR 與 PTR_ERR 定義在 linux/tools/include/linux/err.h

IS_ERR 會展開 IS_ERR_VALUE 巨集來判斷指標是否無效

#define IS_ERR_VALUE(x) unlikely((x) >= (unsigned long)-MAX_ERRNO)

MAX_ERRNO 巨集定義為 4095，代表錯誤碼的最高編號。 (unsigned long)-MAX_ERRNO 轉成 16 進位是 0xFFFF001，因此以 32 位元系統而言，0xFFFFF001 到 0xFFFFFFFF 範圍的地址被保留並用來儲存錯誤碼。所以指標指向位置大於等於 (unsigned long)-MAX_ERRNO 的話即代表指到了保留區，也就是說該指標為非法指標。

原版在判定為無效指標後，沒有立刻回傳終止函式，導致會呼叫到 filp_close 造成錯誤。改正方式為判定無效後立刻回傳。

struct file *fp = filp_open(filepath, O_RDONLY, 0);
if (IS_ERR(fp)) {
    pr_info("Open file failed");
    pr_err("request resouce not found ! \n");
    http_server_send(request->socket, HTTP_RESPONSE_404, strlen(HTTP_RESPONSE_404));
+   return 0;
}
...
filp_close(fp, NULL);

commit 8ee8983

Linux 核心可能貢獻點 :

  1. filp_close 可以增加防呆機制，為 NULL pointer 或是非法指標時，輸出錯誤並回傳 0
  2. IS_ERR() 在判斷時或許可用 bitwise 加速

TODO: 利用 Ftrace 找出 khttpd 核心模組的效能瓶頸

搭配閱讀《Demystifying the Linux CPU Scheduler》第 6 章

注意用語。

ftrace 是 Linux 核心內建的追蹤工具，可追蹤函式調用呼叫 、追蹤事件 (context switch、interrupt)等，進而可針對有興趣的部分做性能瓶頸分析。

ebpf 允許 user 在運行時可加載自定義程式碼到核心中，因此 ebpf 在靈活性上會比 ftrace 高

執行以下命令，檢查系統是否正確安裝 ftrace

​​​​cat /boot/config-`uname -r` | grep CONFIG_HAVE_FUNCTION_TRACER
​​​​CONFIG_HAVE_FUNCTION_TRACER=y

看 khttp 核心模組中有哪些函式可被追蹤

​​​​sudo cat /sys/kernel/debug/tracing/available_filter_functions | grep khttp
​​​​parse_url_char [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]
​​​​http_parser_parse_url [khttpd]
​​​​http_parser_pause [khttpd]
​​​​http_body_is_final [khttpd]
​​​​http_parser_version [khttpd]
​​​​http_parser_set_max_header_size [khttpd]
​​​​http_parser_callback_header_field [khttpd]
​​​​http_parser_callback_headers_complete [khttpd]
​​​​http_parser_callback_request_url [khttpd]
​​​​http_parser_callback_message_begin [khttpd]
​​​​http_parser_callback_header_value [khttpd]
​​​​http_server_recv.constprop.0 [khttpd]
​​​​http_server_send.isra.0 [khttpd]
​​​​http_parser_callback_message_complete [khttpd]
​​​​http_parser_callback_body [khttpd]
​​​​http_server_worker [khttpd]
​​​​handle_socket [khttpd]
​​​​http_server_daemon [khttpd]

對每個成功的連線，會透過 http_server_worker 接收處理 user 送來的請求。而連線只要沒斷掉 http_server_worker 就會持續運作接受 user 請求。因此追蹤 http_server_worker 來觀察在這過程中有無過於耗時的操作。

參考教材方式撰寫 shell script 追蹤函式 http_server_worker

​​​​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

​​​​# set
​​​​echo function_graph > $TRACE_DIR/current_tracer
​​​​echo 5 > $TRACE_DIR/max_graph_depth
​​​​echo http_server_worker > $TRACE_DIR/set_graph_function
​​​​echo '*:mod:khttpd' > set_ftrace_filter

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

echo function_graph > $TRACE_DIR/current_tracer 將追蹤機設置為 function_graph (紀錄函式呼叫和返回，並提供每個函式的執行時間和調用關係)
echo 5 > $TRACE_DIR/max_graph_depth 追蹤函式的深度最多為 5
echo '*:mod:khttpd' 只追蹤 khttp 模組中的函式

注意用語

追蹤的結果會紀錄於 trace_pipe 中， 透過以下指令命令觀察追蹤結果

​​​​sudo cat /sys/kernel/debug/tracing/trace_pipe
​​​​
​​​​  2)               |  http_server_worker [khttpd]() {
​​​​  2)   0.273 us    |    http_parser_init [khttpd]();
​​​​  2)   1.612 us    |    http_server_recv.constprop.0 [khttpd]();
​​​​  2)               |    http_parser_execute [khttpd]() {
​​​​  2)   0.191 us    |      http_parser_callback_message_begin [khttpd]();
​​​​  2)   0.316 us    |      parse_url_char [khttpd]();
​​​​  2)   0.236 us    |      http_parser_callback_request_url [khttpd]();
​​​​  2)   0.177 us    |      http_parser_callback_header_field [khttpd]();
​​​​  2)   0.168 us    |      http_parser_callback_header_value [khttpd]();
​​​​  2)   0.218 us    |      http_parser_callback_headers_complete [khttpd]();
​​​​  2)   0.111 us    |      http_message_needs_eof [khttpd]();
​​​​  2)   0.113 us    |      http_should_keep_alive [khttpd]();
​​​​  2)               |      http_parser_callback_message_complete [khttpd]() {
​​​​  2)   0.103 us    |        http_should_keep_alive [khttpd]();
​​​​  2)               |        http_server_response.isra.0 [khttpd]() {
​​​​  2) ! 476.211 us  |          directory_listing [khttpd]();
​​​​  2) ! 484.153 us  |        }
​​​​  2) ! 484.790 us  |      }
​​​​  2) ! 490.725 us  |    }
​​​​  2)   0.195 us    |    http_should_keep_alive [khttpd]();
​​​​  2) ! 499.699 us  |  }

2) 0.273 us | http_parser_init [khttpd](); 代表該函式運作在核心 2, 耗時 0.273 us

欄位詳細說明可參考 ftrace - Function Tracer

上述可觀察到 http_server_worker 在處理 http_parser_callback_message_complete 耗費 484.790us，裡頭執行到的 directory_listing 就佔了 476.211us。

將 ./htstress localhost:8081 -n 1 改成 ./htstress localhost:8081/iu.jpg -n 1 請求圖片內容。

​​​​ 11)               |      http_parser_callback_message_complete [khttpd]() {
​​​​ 11)   0.107 us    |        http_should_keep_alive [khttpd]();
​​​​ 11)               |        http_server_response.isra.0 [khttpd]() {
​​​​ 11) # 4039.789 us |          file_content_response.isra.0 [khttpd]();
​​​​ 11) # 4049.388 us |        }
​​​​ 11) # 4049.795 us |      }
​​​​ 11) # 4055.627 us |    }
​​​​ 11)   0.194 us    |    http_should_keep_alive [khttpd]();
​​​​ 11) # 4062.255 us |  }

file_content_response 來到了 4039.789us，由此可明顯看出 http_server_worker 執行主要耗時於回傳內容資訊給 client。這是因為每次 client 請求資料時，server 都需重新抓取內容資訊並回傳，但實際上可用快取機制加速處理過程。

TODO : 實作快取機制回傳目錄與內容

TODO: 提高 kHTTPd 的並行程度

嘗試提交 pull request

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

嘗試提交 pull request

當前連線採用 Keep-Alive 機制，且在 Header 中也沒設定 timeout。因此除非 client 請求關閉，否則連線會一直執行，此時閒置的連線就必須釋放將資源讓出。實作機制是可新增另個執行緒，專門追蹤各個連線上一次請求的時間點，當時間點大於設定門檻時，會將連線關閉，當連線有新請求時，則把時間點刷新。因有多個執行緒可能會同時對時間點有讀取或更新，因此可用 RCU 來解決同步問題。

TODO : 這部分實作尚待完成

Last changed by 
 
sysprog
System Software Programming
0
660
Published on HackMD