## Linux 核心專題: 高性能網頁伺服器
> 執行人: [Ackerman666](https://github.com/Ackerman666/khttpd)
> [專題解說錄影](https://youtu.be/gZzO1-6JJrE)

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

## 任務簡介
以[第七次作業](https://hackmd.io/@sysprog/linux2024-ktcp)為基礎，熟悉 Linux 核心模組的開發、網路通訊機制、RCU 使用，和排除相關的技術議題。

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

參考資訊： (適度改寫下方程式碼並驗證)
* Jerejere0808 $\to$ [開發紀錄](https://hackmd.io/@sysprog/HkzcnhOHn)
* Paintako $\to$ [開發紀錄](https://hackmd.io/@sysprog/BkSW8Z2Bn)
* [cppcoffee/khttpd](https://github.com/cppcoffee/khttpd)

## TODO: 自我檢查清單
> https://hackmd.io/@sysprog/linux2024-ktcp-e

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

### 研讀〈[RCU 同步機制](https://hackmd.io/@sysprog/linux-rcu)〉並測試相關 Linux 核心模組以理解其用法

> [RCU 原始碼](https://github.com/torvalds/linux/blob/master/include/linux/rcupdate.h)

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 這段時間能銷毀舊資料。


> 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](https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html)

#### 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](https://hackmd.io/@sysprog/linux-rcu#QSBR-%E6%BC%94%E7%AE%97%E6%B3%95) )

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

:::warning
疑問 : 為何經典 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 觀察作業系統行為](https://hackmd.io/@sysprog/linux-ebpf)

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

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

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

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

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

:::danger
注意用語：
* virtual machine 應翻譯為「虛擬機器」，而非簡略的「虛擬機」，用來區分 motor/engine (發動機) 在漢語常見的翻譯詞「機」。
> 已更正
:::

Linux 基金會之中的專案 IO Visor，開發了 BPF Compiler Collection (BCC)。可使開發者專注於 C 語言注入於核心的邏輯、流程與編譯。載入 BPF 代碼及建立 map 等事項可交由 BCC 處理完成。在 BCC 中也可搭配 python 進行更彈性的處理 (如記錄的資料視覺化等)。
> BCC 用法筆記可參考 [0xff07 筆記](https://hackmd.io/@0xff07/HyrLVSZ78/https%3A%2F%2Fhackmd.io%2F%400xff07%2Fr1f4B8aGI)

### TIME-WAIT sockets

> [RFC 9293](https://www.rfc-editor.org/rfc/rfc9293) (目前找到最新關於 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](https://www.rfc-editor.org/rfc/rfc9293#section-3.3.2)

`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](https://zh.wikipedia.org/zh-tw/TCP%E9%87%8D%E7%BD%AE%E6%94%BB%E5%87%BB)

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

ref:
[TCP協定的TIME_WAIT狀態](https://blog.csdn.net/weixin_43207025/article/details/115024066)
[TCP Connection Termination](https://www.geeksforgeeks.org/tcp-connection-termination/)
[TCP 連線狀態機制與流程](https://dev.twsiyuan.com/2017/09/tcp-states.html)

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

drop-tcp-socket 原理 : [eric88525 的筆記](https://hackmd.io/@eric88525/linux2022-ktcp#drop-tcp-socket-%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84%E9%81%8B%E4%BD%9C%E5%8E%9F%E7%90%86)

## TODO: 引入 CMWQ 改寫 kHTTPd
> 分析效能表現和提出改進方案
> 嘗試提交 pull request

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

安裝 ebpf

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

:::danger
區分「函數」和「函式」，務必詳閱 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](https://hackmd.io/@sysprog/linux2024-ktcp-c#%E6%B8%AC%E9%87%8F-kthread-%E5%BB%BA%E7%AB%8B%E6%88%90%E6%9C%AC)

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

發現 [vax-r](https://hackmd.io/@vax-r/linux2024-homework7#khttpd) 同學是將 `kthread_run` 額外包在一個函式中，再讓 `http_server_daemon` 呼叫此函式，如此便可追蹤該函式，進而追蹤 kthread 操作執行成本。

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

:::danger
使用指定的程式碼縮排風格，如同 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/

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

> commit : [52ba6f0](https://github.com/Ackerman666/khttpd/commit/52ba6f063b2bfc91a9dc5c0ad5a8a51bc5dc9ff3)

**kthread 的一些用法**

:::danger
注意書寫規範：
* 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
:::

`kthread_run` 是一個巨集，定義在 [include/linux/kthread.h](https://github.com/torvalds/linux/blob/master/include/linux/kthread.h)
巨集中由 `kthread_create` 建立執行緒，成功時會透過 `wake_up_process` 喚醒執行緒執行任務。

`kthread_stop` 是一個函式，定義在 [linux/kernel/kthread.c](https://github.com/torvalds/linux/blob/55027e689933ba2e64f3d245fb1ff185b3e7fc81/kernel/kthread.c#L38)
呼叫 `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?](https://stackoverflow.com/questions/36336874/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](https://github.com/sysprog21/ksort/blob/master/sort_impl.c)
> [CMWQ筆記](https://hackmd.io/kXFroi_hQRqAqzPtoi8ylg?view#CMWQ-%E7%AD%86%E8%A8%98)

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

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

:::danger
哪來的「用戶」？
> 已更正
:::

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

:::danger
allocate 是「配置」，而非「分配」，以區隔 dispatch 的翻譯。
> 已更正
:::

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

`kmalloc` 申請空間在實體記憶體上為連續，需設定 [GFP flags](https://www.kernel.org/doc/html/next/core-api/memory-allocation.html#get-free-page-flags)，常見有下面兩種
* GFP_KERNEL : 記憶體無空間可配置時，context 可進行 sleep，直到有空間可進行配置 (適用於大部份情境)
* GFP_atomic : context 不會進行 sleep，如無可配置空間即會立刻回傳錯誤 (適用於需即時處理的情況, 如 interrupt)
> 在電腦科學中，任務（task）的上下文（英語：context）是一個任務所必不可少的一組資料（該任務可以是行程、執行緒）[上下文 (電腦)](https://zh.wikipedia.org/zh-tw/%E4%B8%8A%E4%B8%8B%E6%96%87_(%E8%AE%A1%E7%AE%97%E6%9C%BA))

執行壓力測試 (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, 所以將偵測事件設定在該函式。


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

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

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

:::info
在 [The New MySQL Thread Pool](https://dev.mysql.com/blog-archive/the-new-mysql-thread-pool/) 提到 MySQL 8.0 使用 thread pool 與 Max Transaction Limit 來處理大量連線。
Max Transaction Limit 意思是不會無限制的接受請求，而是限制能同時並行的 transaction 數量。限制此數量的好處在於可避免使用太多 concurrent data locks，進而拖累系統效率。
:::

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

:::danger
為何不參閱課程教材呢？
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`](https://github.com/torvalds/linux/blob/e5b3efbe1ab1793bb49ae07d56d0973267e65112/fs/readdir.c#L87) 函式，用來逐一走訪指定目錄中的每個項目。參數用到以下兩個結構。
* `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](https://www.kernel.org/doc/Documentation/filesystems/vfs.txt)

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` <s>函式</s> 格式要符合以下規範。

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](https://github.com/Ackerman666/khttpd/commit/b66ddb405bb7528ec9f6f5cab5f9d9abd460f02e)

結果如下


:::danger
以 Ftrace (《Demystifying the Linux CPU Scheduler》第六章介紹過) 分析上述涉及 VFS 操作的執行成本。
> 涉及 VFS 操作函式於 `directory_listing` 中，在下文有透過 Ftrace 追蹤 `http_server_worker`，進而觀測執行 `directory_listing` 的成本。
:::

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

> [分塊傳輸編碼](https://zh.wikipedia.org/zh-tw/%E5%88%86%E5%9D%97%E4%BC%A0%E8%BE%93%E7%BC%96%E7%A0%81)

分塊傳輸編碼只在 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 類型](https://www.ibm.com/docs/zh-tw/sc-and-ds/8.4.0?topic=guide-mime-types)

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

參考 [Risheng1128](https://github.com/Risheng1128/khttpd/commit/c6fd206226d3c6ee8f6ef1334bd43b5790f774fd) 方法，建立 `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](https://github.com/torvalds/linux/blob/master/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](https://www.ibm.com/docs/en/aix/7.1?topic=files-types)

// 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 類型判斷機制，瀏覽器可顯示文字檔與圖像。



> commit [b66ddb4](https://github.com/Ackerman666/khttpd/commit/e1ceeb763b38df5b8df1306720d63d15fb8dfeef)

### 處理 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](https://github.com/torvalds/linux/blob/626737a5791b59df5c4d1365c4dcfc9b0d70affe/fs/open.c#L1524)

看原始碼可發現 `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](https://github.com/torvalds/linux/blob/master/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](https://github.com/Ackerman666/khttpd/commit/8ee8983863569409bcac8b273ef492b1c5058cd4)

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

:::

## TODO: 利用 Ftrace 找出 khttpd 核心模組的效能瓶頸
> 搭配閱讀《Demystifying the Linux CPU Scheduler》第 6 章

:::danger
注意用語。
:::

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

:::info
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` 來觀察在這過程中有無過於耗時的操作。

參考[教材](https://hackmd.io/@sysprog/linux2024-ktcp-c#%E4%BD%BF%E7%94%A8-Ftrace-%E8%A7%80%E5%AF%9F-kHTTPd)方式撰寫 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` 模組中的函式

:::danger
注意用語
:::

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

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](https://docs.kernel.org/trace/ftrace.html#function-graph-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 都需重新抓取內容資訊並回傳，但實際上可用快取機制加速處理過程。

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

## TODO: 提高 kHTTPd 的並行程度
> 嘗試提交 pull request

## TODO: 藉由 RCU 在並行環境中得以釋放系統資源
> 嘗試提交 pull request

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

::: info
TODO : 這部分實作尚待完成
:::