# 2025q1 homework 6
contributed by <`Andrushika`>
## RCU 同步機制及用法
借用教材中的一張圖片，來說明 RCU 的機制：
圖片上方有一個 writer，下方有多個 reader。RCU 提供所謂的寬限期，每個 reader 要使用資源時，會進行 lock；當 writer 更新資料時，不會馬上把舊資料刪除，而是先將其保留，直到所有 reader lock 被釋放為止，這樣先前取用資料到一半的 reader 就不會受到影響。
而「寬限期」指的就是 writer update 到 reader 全部 unlock 的這段期間。這段期間內，不同的 reader 可能看到不同版本的資料；分界點取決於 reader 取用 lock 的時機點，如果 reader lock 在 writer update 之前，會取用到被保留下來的舊資料，反之則會取用到新資料。
### linux 核心中的 RCU 函式
`rcu_read_lock()`, `rcu_read_unlock()`：reader 使用，宣告 RCU 讀取的開始與結束。當還有 reader 持有 lock、writer 嘗試 update 時，進入寬限期。
`synchronize_rcu()` 是一個 blocking 的函式，會等待所有正在 read lock 的 reader 結束，之後才可以釋放舊資料。
`call_rcu(rcu_head, callback)` 則是 non-blocking 版本的，可以用來註冊一個 callback 函式，當所有 reader unlock 時執行 callback。
`rcu_dereference()`,`rcu_assign_pointer()`：分別用於 pointer 的安全讀寫，帶有 `READ_ONCE`, `WRITE_ONCE` 的相同功能，且帶有 memory barrier。舉 `rcu_assign_pointer()` 的例子來說：
```c
void foo_update(foo *new_fp) {
spin_lock(&foo_mutex);
foo *old_fp = global_foo;
new_fp->a = 1;
new_fp->b = 'b';
new_fp->c = 100;
// global_foo = new_fp; // wrong
rcu_assign_pointer(global_foo, new_fp); // right
spin_unlock(&foo_mutex);
synchronize_rcu();
kfree(old_fp);
}
```
如果沒有使用那個函式，因為不帶有 memory barrier，而可能會在 `new_fp` 更新到一半，就把 `new_fp` assign 給 `global_foo` 了。正確的方式是要使用 `rcu_assign_pointer()`，才能保證寫入順序的正確性。
:::info
[教材](https://hackmd.io/@sysprog/linux-rcu#%E9%A1%A7%E5%8F%8A-memory-ordering-%E7%9A%84%E5%BD%B1%E9%9F%BF)裡面有一句話：
> 我們可見其實作只是在數值指派之前，**加了 WRITE_ONCE 這樣的 memory barrier** 來確保程式碼的執行順序。
我對這裡的敘述有疑問，`WRITE_ONCE` 似乎並不能直接說是 memory barrier。我去找了 `rcu_assign_pointer()` 的定義：
```c
#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)
```
上方程式碼可見，當 `v` （要 assign 的新值）是 constant 且 `NULL` 的時候，會直接用 WRITE_ONCE；反之會呼叫 `smp_store_release()`，於是我又看了該函式的定義 [linux/tools/include/asm/barrier.h](https://github.com/torvalds/linux/blob/9f35e33144ae5377d6a8de86dd3bd4d995c6ac65/tools/include/asm/barrier.h#L49)：
```c
# define smp_store_release(p, v) \
do { \
smp_mb(); \
WRITE_ONCE(*p, v); \
} while (0)
```
這邊同時使用了 memory barrier 和 `WRITE_ONCE`，這也變相說明了兩者應該是不同的事情。`READ_ONCE`,`WRITE_ONCE` 的主要目的是阻止編譯器的優化行為，每次讀都一定從記憶體抓，每次寫都真的寫回記憶體，不能偷懶、不能延後。
:::
## 測試網頁伺服器的效能，並針對多核處理器場景調整
後續實驗我將同時使用 `hstress` 以及 [wrk](https://github.com/wg/wrk) 作為我的 benchmarking tool，不同工具的比較使實驗更精準。使用 `wrk` 而非 `ab` 的好處是，其可以指定 client 使用多少 threads 進行壓力測試（`hstress` 當中也有該功能），比如：
```shell
$ wrk -t8 -c200 -d10s http://localhost/
```
其中 `-t8` 代表同時使用 8 個 thread，使請求的發送可以平行化，當 concurrent 數量大的時候，能夠真正給予伺服器壓力，而不會因為只有一個 thread 在發送請求導致壓力推不上去；尤其在多核伺服器的測試中更可以看出差別。此外 `wrk` 可以輸出詳細的 metrics，其輸出格式如下（範例）：
```bash
Running 30s test @ http://127.0.0.1:8080/index.html
12 threads and 400 connections
Thread Stats Avg Stdev Max +/- Stdev
Latency 635.91us 0.89ms 12.92ms 93.69%
Req/Sec 56.20k 8.07k 62.00k 86.54%
22464657 requests in 30.00s, 17.76GB read
Requests/sec: 748868.53
Transfer/sec: 606.33MB
```
其額外包含 tail latency 和標準差可供參考。
## 使用 ftrace 追蹤 khttpd 效能瓶頸
首先，要啟用 `gcc` 的 code instrument 機制，需要在 `makefile` 中編譯時使用 `-pg` flag：
```
ccflags-y += -pg
```
之後檢查 ftrace 可追蹤到的函式：
```shell
sudo cat /sys/kernel/debug/tracing/available_filter_functions | grep khttpd
```
但我發現，有部份函式沒有出現在可 tracing 的列表中。詢問 ChatGPT 後，發現是編譯器會自動優化掉一些較小且只有單點呼叫的函式；此時需要在消失的函式前方加上 `noinline` 防止優化：
```c
static noinline struct work_struct *create_work(struct socket *socket)
static noinline void free_work(void)
```
之後就可以正確在 `available_filter_functions` 中看見想要 trace 的函式：
```shell
andrew@andrew-Alienware-m15-R6:~/linux2025/khttpd$ sudo cat /sys/kernel/debug/tracing/available_filter_functions | grep khttpd
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]
create_work [khttpd]
free_work [khttpd]
http_parser_callback_header_value [khttpd]
http_server_recv.constprop.0 [khttpd]
http_server_worker [khttpd]
http_server_send.isra.0 [khttpd]
http_parser_callback_message_complete [khttpd]
http_parser_callback_body [khttpd]
http_server_daemon [khttpd]
```
接下來需要設置 `ftrace_filter`，避免太多底層的呼叫混入 trace 紀錄中影響判讀。在 *Demystifying the Linux CPU Scheduler* 一書中，使用到了「僅保留特定 PID」的過濾方式，然而這在 khttpd 的測試中不管用：因為使用了 CMWQ 分配 kworker 執行任務，其 PID 會不斷生成，所以需要使用別的過濾方式。
我一開始把所有 khttpd 專案中的 function 全部寫入 `set_ftrace_filter`，於是就產生了下面這一長串：
```shell
echo http_server_worker >> $TRACE_DIR/set_ftrace_filter
echo create_work >> $TRACE_DIR/set_ftrace_filter
echo http_parser_callback_message_begin >> $TRACE_DIR/set_ftrace_filter
echo http_parser_callback_request_url >> $TRACE_DIR/set_ftrace_filter
echo http_parser_callback_header_field >> $TRACE_DIR/set_ftrace_filter
echo http_parser_callback_header_value >> $TRACE_DIR/set_ftrace_filter
echo http_parser_callback_headers_complete >> $TRACE_DIR/set_ftrace_filter
echo http_parser_callback_body >> $TRACE_DIR/set_ftrace_filter
echo http_parser_callback_message_complete >> $TRACE_DIR/set_ftrace_filter
echo http_parser_init >> $TRACE_DIR/set_ftrace_filter
echo http_parser_execute >> $TRACE_DIR/set_ftrace_filter
echo http_should_keep_alive >> $TRACE_DIR/set_ftrace_filter
```
後來再看老師寫的作業說明，裡面原來提供了更簡潔的寫法：
```shell
echo '*:mod:khttpd' >> $TRACE_DIR/set_ftrace_filter
```
這個故事告訴我們要好好閱讀作業說明，不要偷懶。
其實 ftrace 的官方文件也有說明更詳細的 [filter commands](https://docs.kernel.org/trace/ftrace.html#filter-commands) 用法。
以下 script 設定好要觀測的函式後，執行 `curl` 向 server 發出請求並印出 trace 結果；記得執行 shell 前需要先掛載 kernel module。
```shell
#!/bin/bash
TRACE_DIR=/sys/kernel/debug/tracing
# clean up
echo > $TRACE_DIR/trace
echo > $TRACE_DIR/set_graph_function
echo > $TRACE_DIR/set_ftrace_filter
echo function_graph > $TRACE_DIR/current_tracer
echo http_server_worker >> $TRACE_DIR/set_graph_function
echo create_work >> $TRACE_DIR/set_graph_function
echo '*:mod:khttpd' > $TRACE_DIR/set_ftrace_filter
echo funcgraph-tail > $TRACE_DIR/trace_options
echo 1 > $TRACE_DIR/tracing_on
curl -s http://localhost:8081/ > /dev/null
echo 0 > $TRACE_DIR/tracing_on
cat $TRACE_DIR/trace
```
執行後可以觀測到 ftrace 結果：
```
andrew@andrew-Alienware-m15-R6:~/linux2025/khttpd/scripts$ sudo ./trace_graph_func.sh
# tracer: function_graph
#
# CPU DURATION FUNCTION CALLS
# | | | | | | |
3) 3.413 us | create_work [khttpd]();
12) | http_server_worker [khttpd]() {
12) 1.543 us | http_parser_init [khttpd]();
12) 6.866 us | http_server_recv.constprop.0 [khttpd]();
12) | http_parser_execute [khttpd]() {
12) 0.500 us | http_parser_callback_message_begin [khttpd]();
12) 0.548 us | parse_url_char [khttpd]();
12) 0.397 us | http_parser_callback_request_url [khttpd]();
12) 0.276 us | http_parser_callback_header_field [khttpd]();
12) 0.372 us | http_parser_callback_header_value [khttpd]();
12) 0.277 us | http_parser_callback_header_field [khttpd]();
12) 0.233 us | http_parser_callback_header_value [khttpd]();
12) 0.262 us | http_parser_callback_header_field [khttpd]();
12) 0.262 us | http_parser_callback_header_value [khttpd]();
12) 0.372 us | http_parser_callback_headers_complete [khttpd]();
12) 0.345 us | http_message_needs_eof [khttpd]();
12) 0.327 us | http_should_keep_alive [khttpd]();
12) | http_parser_callback_message_complete [khttpd]() {
12) 0.268 us | http_should_keep_alive [khttpd]();
12) + 29.013 us | http_server_send.isra.0 [khttpd]();
12) + 38.932 us | } /* http_parser_callback_message_complete [khttpd] */
12) + 50.521 us | } /* http_parser_execute [khttpd] */
12) 0.286 us | http_should_keep_alive [khttpd]();
12) + 41.372 us | http_server_recv.constprop.0 [khttpd]();
12) ! 132.066 us | } /* http_server_worker [khttpd] */
```
其中發現 `http_server_send`, `http_server_recv` 等花費較多時間。
## 引入 CMWQ 至 khttpd
commit [ad0e8ad](https://github.com/Andrushika/khttpd/commit/ad0e8adf6c71684140795b26a2b1c9f63bd8ae93)
Sign in with Wallet
Connect another wallet