2024q1 Homework7 (kHTTPd)

contributed by < vax-r >

自我檢查清單

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

• 如何測試網頁伺服器的效能，針對多核處理器場景調整

• 如何利用 Ftrace 找出 khttpd 核心模組的效能瓶頸，該如何設計相關實驗學習。搭配閱讀《Demystifying the Linux CPU Scheduler》第 6 章
  Answer : ftrace 顧名思義是 function tracer ，追蹤函式又是怎麼達成的呢？首先搞清楚 tracing 代表的是在執行時期紀錄事件的數據，也稱為 software profiling ，在 ftrace 當中是透過 code instrumentation 。 Instrumentation 又可以分為兩種

  • Function tracing, 利用 gcc 等編譯器在編譯時期做 code instrumentation
  • Event tracing, 在 source code 當中利用 tracepoints 來達成

  Function tracing 利用 dynamic profiling 達成，也就是編譯器在編譯時在每個函式開頭都加上一個 NOP ，這些 NOP 的位置又被記錄下來，如果我們需要對某個函式進行 tracing 時，就將對應的 NOP 換成 JMP ，這樣的技術又稱為 runtime injection 。
  Event tracing 則是利用在 source code 當中加入 tracepoints 來達成， tracepoints 會直接呼叫 tracing function ，因此是 static 的，每次我們要新增 tracepoints 都要重新編譯整個 kernel 。
  Tracing functions 實際上利用一個 ring buffer 來記錄所有執行時期的事件，舊的事件會被新的事件給覆寫過去。
  利用以下命令觀察系統是否有啟用 ftrace
  $ cat /boot/config-$(uname -r) | grep CONFIG_HAVE_FUNCTION_TRACER
  預期輸出為 CONFIG_HAVE_FUNCTION_TRACER=y

• 解釋 drop-tcp-socket 核心模組運作原理。TIME-WAIT sockets 又是什麼？

• 研讀 透過 eBPF 觀察作業系統行為，如何用 eBPF 測量 kthread / CMWQ 關鍵操作的執行成本？
  Ans : 參照 下方筆記

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

閱讀《高效 Web 伺服器開發》

參考 The Tenouk's Linux Socket (network) programming tutorial ，以下是 TCP 連線流程圖

我們在意 Server 端的場景，首先我們建立一個 socket file descriptor 後將它 bind 到對應的 socket ，之後開始監聽特定 port ，接下來關鍵的步驟在於 server 呼叫 accept() 等待連線，若有 client 嘗試進行連線並成功， accept() 會返回一個 file descriptor 並利用該 file descriptor 進行 read() ，同樣等到有資料才會跳到下一步驟。

此時若有兩個同時想嘗試連線並獲得服務的 client ，則這種 server 設計一次只能服務一個，服務結束後才能服務下一個 client ，若前一個 client 在連線或寫入時速度很慢， server 只能持續等待，同時也延後了服務下一個 client 的時間，造成效能不彰。

process-per-connection model
本文作者提出一個方法，每次 accept() 之後進行 fork() ，讓子行程處理對應 client ，而父行程繼續 accept() ，如此一來看似解決一次只能處理一個連線的問題，但效能上仍有很大改進空間

• fork() 開銷大，要複製父行程的資料空間與 page table 的等等。
• 排程器在大量連線產生大量行程後會承受巨大壓力，耗費大量時間挑選下一個執行的行程，並且進行 context switch 。

若改用執行緒，雖然解決 fork() 開銷問題，以及可以共享記憶體空間， IPC 成本降低，但由於行程和執行緒本質類似，對於排程器來說依舊會承受很大壓力，同樣是 process-per-connection model 仍然不滿足 high concurrency 需求。

thread pool
既然每次收到請求要建立對應的執行緒或行程，導致建立執行緒產生大量成本以及排程器的壓力，為何不直接先建立許多執行緒呢？如此一來可以省去收到連線請求才建立執行緒的成本。但這依舊存在一個問題，如何面對 long keep-alive time ？也就是真實情況中許多連線都會進行多次寫入，只要該執行緒和客戶端連線後，若客戶端沒有主動斷開連線，該執行緒會持續被該客戶佔用，假設本來有 $n$ 個執行緒，結果都被佔用了，如果真的有大量資料持續發送就算了，若只是在 read() 處等待，客戶根本沒有送資料只是佔用著執行緒，會造成系統很大的問題。

當然我們可以透過 non-blocking I/O 解決這個情況，但如此一來執行緒會在 main loop 當中瘋狂切換 accept()->read()->accept()->read() ，能否在對應的 file descriptor 有資料可讀取的時候再進行 read() 呢？這時我們就需要 event-driven model 。

I/O Multiplexing
作為 blocking I/O 的延伸，將較於持續透過同一個 main loop 一口氣完成 read() 一直到 process data 並 reply ， I/O multiplexing 將一個執行緒用來監聽哪個 fd 可以讀取 (透過 select() ) 若有可讀取的 fd 則交給另一個執行緒處理，自己則回到 userspace 繼續監聽

此處和 Linux kernel 當中處理中斷的概念類似，都利用到 deferable work 的概念將接收任務和處理任務拆分開，但由於 select() 有其限制，因此後來衍伸出了 epoll() 。

epoll()
根據 epoll(7) 解說， epoll() API 提供一系列的系統呼叫來達成和 poll(), select() 相似的行為，也就是同時監控多個 file descriptor ，而最主要的元件就是 epoll instance ，一個存在 kernel space 的資料結構，從 user space 角度來看 ， epoll instance 可以被拆分為兩個部分

• The interest list (epoll set): 當前被監控的 file descriptor 集合
• The ready list: 被標記為 ready 的 file descriptor 集合，是 interest list 的子集合，由 kernel 動態產生。

以下幾個系統呼叫是用來創建並管理 epoll instance 的

• epoll_create() : 建立一個新的 epoll instance 並回傳對應的 file descriptor 。
• epoll_ctl() : 將指定的 file descriptor 加入 interest list 當中。
• epoll_wait() : 等待 I/O 事件發生，若沒有則會阻塞該執行緒。

React Pattern
main loop 只負責監聽 file descriptor ，並把新建立的 file descriptor 加入 epoll instance 當中，若有連線產生則交由 (defer) request handler 處理，如此一來 main loop 不會因會事件處理而 blocking ，所有任務都交由 request handler 幫忙處理。

eBPF

過往我們想更改作業系統行為不外乎兩種方式，提交 patch 到 LKML 並試圖獲得採納、撰寫 kernel module 並載入原本的作業系統核心，前者太耗時、後者缺乏 portability 。 eBPF 提供我們不更動原本作業系統核心程式碼的情況下改變作業系統行為的能力，它在作業系統核心度中運行沙盒程式來擴充作業系統行為，並且保證安全性與效率。
eBPF program 本質上是 event-driven ，當作業系統核心或者應用程式通過它指定的 hook points 時會觸發特定行為， hook points 可以是 system calls 、 function entry\exit 、 kernel tracepoints 、 network events 或更多。

如果我們想建立的 predefined hook point 不存在，則我們也可以自行創建 kprobe 或 uprobe 並將 eBPF 程式掛在上面。

撰寫 eBPF program

多數來說我們不會直接撰寫 eBPF bytecode ，而是透過 Cilium, bcc 或 bpftrace 等工具提供一個 eBPF 的 high-level 封裝並使用這些工具撰寫 eBPF program ，透過編譯後才得到 eBPF bytecode 。在 Linux kernel 來說可以先透過 C 語言撰寫再透過 LLVM 將 C code 編譯為 eBPF bytecode 。
在 eBPF program 載入 Linux kernel 前會先需要兩個步驟來確保它可以被掛載到 hook point 上。

1. Verification
   確保 eBPF 的運行是安全的，它會驗證程式的幾個特性例如：
   • 確保要載入 eBPF program 的行程是具有特權的 (priviledge) 。除非特別註明非特權行程也能載入 eBPF program ，否則只有具特權的程式可以。
   • 確保程式不會 crash
   • 確保程式總是會執行完畢 (不存在無窮迴圈等等)
2. JIT Compilation
   將 generic bytecode 轉譯為 machine specific instruction ，最佳化執行速度，使得 eBPF 程式的運行跟原始的 kernel code 一樣有效率。

Maps

eBPF Maps 作為一個非常重要的元件，提供了整個系統共享資源的能力，不管是 kernel 或 user space 當中的 eBPF program 都可以透過系統呼叫存取 eBPF Maps ，而 Maps 由很多不同的資料結構組成，包括 hash table, LRU, Ring Buffer 等等。

Helper call

eBPF 不能直接呼叫隨意的 kernel function ，否則會使 eBPF program 和特定版本的核心過度關聯而喪失相容性， kernel 因此特別提供了一組 API 稱為 helper functions 給 eBPF program ，例如有以下幾種功能

• Generate random numbers
• Get current time & date
• eBPF map access
• Get process/cgroup context
• Manipulate network packets and forwarding logic

Tail & Function Calls

eBPF program 由 tail calls 和 functions calls 組成。 function calls 使 eBPF program 可以定義並呼叫函式， Tail calls 則是可以呼叫並執行另外一個 eBPF program ，被呼叫的 program 會取代目前的 context 繼續執行，和 execve() 系統呼叫的概念類似。

bcc python tutorial

bcc Python Developer Tutorial
由於我們不會直接撰寫 eBPF bytecode ，我們可以透過 bcc 這個高階封裝的框架來幫忙，首先撰寫一個簡單的程式來監控 sync 系統呼叫，若系統呼叫了 sync 則印出訊息

from bcc import BPF

BPF(text='int kprobe__sys_sync(void *ctx) { bpf_trace_printk("Tracing sys_sync()... Ctrl-C to end\\n"); return 0; }').trace_print()

有幾點可以注意

• text='...' : 定義了 BPF program ，是用 C 語言寫的
• kprobe__sys_sync() : kernel 利用 kprobes 達成動態追蹤的捷徑， kprobe__ 後面的部分代表要追蹤的 kernel function ，在這個例子當中是 sys_sync() 。
• void *ctx : context 的參數。
• .trace_print() : 一個可以讀取 trace_pipe 並印出 output 的 bcc routine 。

再換一個測試程式，如下

from __future__ import print_function
from bcc import BPF
from bcc.utils import printb

# load BPF program
b = BPF(text="""
#include <uapi/linux/ptrace.h>

BPF_HASH(last);

int do_trace(struct pt_regs *ctx) {
    u64 ts, *tsp, delta, key = 0;

    // attempt to read stored timestamp
    tsp = last.lookup(&key);
    if (tsp != NULL) {
        delta = bpf_ktime_get_ns() - *tsp;
        if (delta < 1000000000) {
            // output if time is less than 1 second
            bpf_trace_printk("%d\\n", delta / 1000000);
        }
        last.delete(&key);
    }

    // update stored timestamp
    ts = bpf_ktime_get_ns();
    last.update(&key, &ts);
    return 0;
}
""")

b.attach_kprobe(event=b.get_syscall_fnname("sync"), fn_name="do_trace")
print("Tracing for quick sync's... Ctrl-C to end")

# format output
start = 0
while 1:
    try:
        (task, pid, cpu, flags, ts, ms) = b.trace_fields()
        if start == 0:
            start = ts
        ts = ts - start
        printb(b"At time %.2f s: multiple syncs detected, last %s ms ago" % (ts, ms))
    except KeyboardInterrupt:
        exit()

• bpf_ktime_get_ns() : 回傳以 nanoseconds 為單位的時間。
• BPF_HAS(last) : 建立一個 BPF map object ，本質上是一個 associative array ，名稱為 last ，預設的 key, value 型態是 u64
• key = 0 : 只會儲存一組 key/value pair ，而 key 被寫死為 0
• if (tsp != NULL) : verifier 規定指標型態的變數都需要經過檢查才能使用
• last.delete(&key) : 把 key 從 hash 當中刪除。
• last.update(&key, &ts) : 更新 key 對應的 value

可用的 event 可在 /sys/kernel/debug/tracing/available_filter_functions 檔案當中找到。

kecho

kecho_mod.c 合併 echo_server.[ch] 實作一個在核心空間的網路伺服器，透過一個 kernel thread 運作伺服器並且透過 CMWQ 搭配 worker 來處理網路封包請求。另外此專案還設置一個 user space 的網路伺服器 user-echo-server.c ，如果編譯後並利用 benchmark 程式 bench.c 所編譯得到的 bench 進行測試，該程式預設對目標伺服器發送 1000 個封包請求，注意會先利用 pthread 建立 1000 個 worker ，並等待該 1000 個 worker thread 都準備好才會開始對伺服器發送請求。

對 kecho 和 user-echo-server 分別進行 benchmark 測試所得結果如下，注意 kecho 測試時有將 CMWQ 設為 bounded ，以提供更好的 CPU affinity 。

• kecho
  
• user-echo-server
  

整體分佈可以發現 kecho 平均 response time 比較低，但是同樣數量的 threads 對 kecho 發送請求得到的 response time 差異很大。
相反的在 user-echo-server 則是平均 response time 高，但是相同 thread 數量，每個 thread 的 response time 是很穩定的，而且 response time 上漲的變化像是階梯形式，過了某個 threshold 會突然飆升。

khttpd

eBPF 量測建立 kthread 成本

首先載入 khttpd 核心模組，之後利用以下命令觀察可利用 kprobe 監聽的 event

$ cat /sys/kernel/debug/tracing/available_filter_functions | grep khttpd

輸出應該可見 http_server_worker 和 http_server_daemon ，撰寫以下 python 程式利用 bcc 套件來使用 bpf 功能。

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

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

while True:
	try:
		res = b.trace_fields()
	except ValueError:
		continue
	print(res[5].decode("UTF-8"))

以上做法無法捕捉到我額外寫的 wrapper function ，就算利用 frace 也無法捕捉到，於是我另外撰寫一個測試用的函式如下

int my_test_func(void *arg) {
    char *buf;
    buf = kzalloc(RECV_BUFFER_SIZE, GFP_KERNEL);
    if (!buf) {
        pr_err("can't allocate memory!\n");
        return -1;
    }
    memset(buf, 0, RECV_BUFFER_SIZE);
    kfree(buf);

    return 0;
}

同樣在 http_server_daemon 當中呼叫此函式，這麼做的時候 kprobe 和 ftrace 皆能夠捕捉到此函式的執行，我推測是原本的 wrapper function 功能過於簡單，被編譯器簡化後執行流程不會呼叫到該 wrapper function 的函式地址，而是直接執行裡面的內容，所以才沒有捕捉到。於是我將 wrapper function 改寫為以下形式就捕捉到了。

int my_thread_run(void *arg)
{
    struct task_struct *worker = kthread_run(http_server_worker, arg, KBUILD_MODNAME);
    if (IS_ERR(worker)) {
        pr_info("can't create more worker process\n");
    }

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

    kfree(buf);

    return 0;
}

測試的 BPF 程式與 python 程式如下

from bcc import BPF
code = """
#include <uapi/linux/ptrace.h>

BPF_HASH(start, u64);

int kprobe__my_thread_run(struct pt_regs *ctx)
{
    u64 ts, key = 0;
	ts = bpf_ktime_get_ns();
	start.update(&key, &ts);
    return 0;
}

int kretprobe__my_thread_run(struct pt_regs *ctx)
{
    u64 key = 0;
    u64 *ts = start.lookup(&key);
	u64 end_ts = bpf_ktime_get_ns();
	if (ts != NULL) {
        u64 delta = end_ts - *ts;
		bpf_trace_printk("%llu\\n", delta);
		start.delete(&key);
    }
	
	start.update(&key, &end_ts);
    return 0;
}
"""

b = BPF(text = code)

with open('kthread_run_cost.txt', 'w') as f:
    i = 0
    while True:
        try:
            (task, pid, cpu, flags, ts, msg) = b.trace_fields()
            f.write(str(i))
            f.write(' ')
            f.write(msg.decode("UTF-8"))
            f.write('\n')
            i += 1
        except ValueError:
            continue

利用 ./htstress -n 100000 -c 1 -t 4 http://localhost:8081/ 對 khttpd 發送 100000 次 request 並利用上述測試程式監聽並將數據作圖如下

可以發現多數時候 kthread_run 的執行成本都分布在 500000 ns 以下，但當請求的數目接近 100000 時，就會出現部分 kthread_run 執行成本甚至超過 1500000 ns 的情況。

commit 7d95c8a

關於 kthread_run() 此巨集的定義可以在 /include/linux/kthread.h 找到，主要作為 kthread_create() 的 wrapper 。

ftrace 量測 khttpd 效能瓶頸

在尚未對原本程式進行任何改動的情況下，先將 kernel 的 ftrace 開啟以下選項

/sys/kernel/tracing# echo function_graph > current_tracer
/sys/kernel/tracing# echo display-graph > trace_options
/sys/kernel/tracing# echo funcgraph-tail > trace_options

接著把 set_ftrace_filter 指定為只追蹤 khttpd 核心模組的相關函式

/sys/kernel/tracing# echo '*:mod:khttpd' > set_ftrace_filter

透過 trace_pipe 觀察核心模組行為，並在另一個終端機輸入以下命令

$ curl -i http://localhost:8081/

觀察 trace_pipe 輸出

/sys/kernel/tracing# cat trace_pipe
 0)               |  http_server_worker [khttpd]() {
 0)   0.925 us    |    http_parser_init [khttpd]();
 0)   4.362 us    |    http_server_recv.constprop.0 [khttpd]();
 0)               |    http_parser_execute [khttpd]() {
 0)   0.361 us    |      http_parser_callback_message_begin [khttpd]();
 0)   1.129 us    |      parse_url_char [khttpd]();
 0)   0.453 us    |      http_parser_callback_request_url [khttpd]();
 0)   0.330 us    |      http_parser_callback_header_field [khttpd]();
 0)   0.275 us    |      http_parser_callback_header_value [khttpd]();
 0)   0.439 us    |      http_parser_callback_header_field [khttpd]();
 0)   0.261 us    |      http_parser_callback_header_value [khttpd]();
 0)   0.263 us    |      http_parser_callback_header_field [khttpd]();
 0)   0.274 us    |      http_parser_callback_header_value [khttpd]();
 0)   0.269 us    |      http_parser_callback_headers_complete [khttpd]();
 0)   0.368 us    |      http_message_needs_eof [khttpd]();
 0)   0.370 us    |      http_should_keep_alive [khttpd]();
 0)               |      http_parser_callback_message_complete [khttpd]() {
 0)   0.260 us    |        http_should_keep_alive [khttpd]();
 0) + 43.504 us   |        http_server_send.isra.0 [khttpd]();
 0) + 55.908 us   |      } /* http_parser_callback_message_complete [khttpd] */
 0) + 69.744 us   |    } /* http_parser_execute [khttpd] */
 0)   0.446 us    |    http_should_keep_alive [khttpd]();
 0)               |    http_server_recv.constprop.0 [khttpd]() {
 7) ! 116.629 us  |    } /* http_server_recv.constprop.0 [khttpd] */
 7) ! 259.895 us  |  } /* http_server_worker [khttpd] */

詳細欄位說明可以參照 function graph tracer 。
此處可以發現幾個函式耗費了比較長的時間，包括 http_parser_execute(), http_parser_callback_message_complete(), http_server_send(), http_server_recv() 。而且函式結束時的 CPU 和運作時期的 CPU 不同，代表中間可能經過 context-switch 並重新 schedule ，能否避免此行為來增加 khttpd 處理請求的速度。

首先分析 http_parser_execute() 做了什麼，是否有能夠優化的空間。在該函式當中會將送入的 data 逐字元處理並且每次都判斷當前的 CURRENT_STATE() 也就是 p_state 的值才做處理，一開始 p_state 是 s_start_req 先分析該請求使用哪種 http method ，例如 GET 或 POST ，接著透過 UPDATE_STATE() 巨集將 p_state 轉為 s_req_method ，這種一個一個字元處理的方法導致很大的延遲，可以透過將 buf 當中的資料拆解分析來進行優化。

參考資料

https://www.brendangregg.com/blog/2019-01-01/learn-ebpf-tracing.html

https://github.com/iovisor/bcc/blob/master/docs/tutorial_bcc_python_developer.md