# Linux 核心專題: 高效網頁伺服器開發
> 執行人: JoshuaLee0321
> [GitHub](https://github.com/JoshuaLee0321/cserv)
> [專題講解影片](https://youtu.be/PMLyoVDjCrs)
> [期末自我評量](https://wiki.csie.ncku.edu.tw/User/JoshuaLee0321)
:::success
:question: 提問清單
* ?
:::
## 任務簡述
在 [ktcp](https://hackmd.io/@sysprog/linux2023-ktcp) 提到，[cserv](https://github.com/sysprog21/cserv) 展現 event-driven, non-blocking I/O Multiplexing (主要是 epoll), shared memory, processor affinity, coroutine, context switch, UNIX signal, dynamic linking, circular buffer, hash table, red-black tree, atomic operations 等議題的實際應用。本任務預計參閱〈[Inside NGINX: How We Designed for Performance & Scale](https://www.nginx.com/blog/inside-nginx-how-we-designed-for-performance-scale/)〉，對比 [NGINX](https://nginx.org/en/) 和 [cserv](https://github.com/sysprog21/cserv)，歸納架構設計的異同，並著手改進後者。
參考資訊:
* [ktcp: cserv 高效網頁伺服器](https://hackmd.io/@sysprog/linux2023-ktcp-d)
* [The Architecture of Open Source Applications: nginx](https://aosabook.org/en/v2/nginx.html)
* [Inside NGINX: How We Designed for Performance & Scale](https://www.nginx.com/blog/inside-nginx-how-we-designed-for-performance-scale/)
### 實驗環境
> `$ lscpu`
:::spoiler
```bash
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 43 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 2600X Six-Core Processor
CPU family: 23
Model: 8
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 2
Frequency boost: enabled
CPU max MHz: 3600.0000
CPU min MHz: 2200.0000
BogoMIPS: 7199.09
...
Caches (sum of all):
L1d: 192 KiB (6 instances)
L1i: 384 KiB (6 instances)
L2: 3 MiB (6 instances)
L3: 16 MiB (2 instances)
NUMA:
NUMA node(s): 1
```
:::
## 架構設計描述和檢討
參閱〈[Inside NGINX: How We Designed for Performance & Scale](https://www.nginx.com/blog/inside-nginx-how-we-designed-for-performance-scale/)〉，對比 [NGINX](https://nginx.org/en/) 和 [cserv](https://github.com/sysprog21/cserv)，歸納架構設計的異同，逐一探討 cserv 相對於 NGINX 在高效能表現尚欠缺的關鍵設計，例如 [AIO](https://www.nginx.com/blog/thread-pools-boost-performance-9x/)。
### 主從式架構
#### NGINX
> NGINX leads the pack in web performance, and it’s all due to the way the software is designed. Whereas many web servers and application servers use a simple threaded or process‑based architecture, NGINX stands out with a sophisticated event‑driven architecture that enables it to scale to hundreds of thousands of concurrent connections on modern hardware.
NGINX 高效的原因歸於其架構，NGINX 使用 [master-slave](https://en.wikipedia.org/wiki/Master/slave_(technology)) 的架構，讓 不同的 workers 常駐在 cpu 上，同時讓另外一個 master 去處理其他 worker 需要的高權限操作 (e.g., Fetch file, transfer file, print, etc.)。
根據〈[Inside NGINX: How We Designed for Performance & Scale](https://www.nginx.com/blog/inside-nginx-how-we-designed-for-performance-scale/)〉，Nginx 的 master 專門執行一些特權操作如讀取設定檔案，bind 等等，worker 則負責把所有的工作完成，例如讀寫以及處理連線，而 worker 之所以會有效率的處理連線，也可以參照
[NGINX 開發日誌](https://www.nginx.com/blog/thread-pools-boost-performance-9x/)中以送貨員以及排隊等候的機制去看待這個問題
假設有一堆顧客，他們需要取貨，而有些貨物(1-3 號箱)盡在眼前，同時也很多貨物存在遙遠的倉庫中，此時注意這邊這位工作者(worker) 只會盲目的遵從目前顧客的要求，並且服務目前的顧客，假設有一個顧客要求比較遠的 4 號箱子，如此一來造成了護衛效應，擋住了後面也許有機會服務更快的顧客。
讓我們再想想另外一個情形，當這個 worker 學乖了，他利用一個送貨區，當每次有太遠的貨物需要取貨時，他並不會自己慢慢跑過去，而是一通電話叫送貨人員送來。如此一來就可以更快的服務到其他顧客，與此同時目前顧客也不會因服務其他人而導致他的任務沒有進展。
而 NGINX 的 worker 也一樣，當一個進程可能需要很長的操作時間時，他不會自己處理，而是將這個任務放進 TaskQueue 中，而任何空閒的 Thread 都可以將此 queue 中的任務取出來執行。
TasksQueue 以及 Thread Pool 在這邊扮演的腳色就是送貨員以及送貨車，Taskqueue 會接收由 worker process 來的工作，處理完之後再把結果送回 worker process 中。
為驗證這個事實，可以先使用以下命令
```bash
~$ sudo apt-get install nginx # 下載 NGINX
~$ ps -ef --forest |grep nginx # 查詢有關 nginx 的 process
# output:
# root 920 1 0 五 30 ? 00:00:00 nginx: master process /usr/sbin/nginx -g daemon on; master_process on;
# www-data 922 920 0 五 30 ? 00:00:00 \_ nginx: worker process
# www-data 923 920 0 五 30 ? 00:00:40 \_ nginx: worker process
# www-data 925 920 0 五 30 ? 00:00:07 \_ nginx: worker process
# www-data 926 920 0 五 30 ? 00:00:29 \_ nginx: worker process
# www-data 928 920 0 五 30 ? 00:00:00 \_ nginx: worker process
# www-data 929 920 0 五 30 ? 00:00:00 \_ nginx: worker process
# www-data 931 920 0 五 30 ? 00:00:00 \_ nginx: worker process
# www-data 932 920 0 五 30 ? 00:00:00 \_ nginx: worker process
# www-data 933 920 0 五 30 ? 00:00:00 \_ nginx: worker process
# www-data 934 920 0 五 30 ? 00:00:00 \_ nginx: worker process
# www-data 935 920 0 五 30 ? 00:00:00 \_ nginx: worker process
# www-data 936 920 0 五 30 ? 00:00:00 \_ nginx: worker process
```
數一下的確可以發現 `nginx: worker process` 存在於 `nginx: master process` 底下。
#### cserv
其實 cserv 也實作同樣的主從式架構，但與 NGINX 相異處在於，cserv 以 coroutine 做到 cooperative multitasking 以達到相對高效的結果。
:::warning
cserv 亦有 worker
> 根據
```c
// src/process.c
void process_init()
{
...
for (int i = 0; i < g_worker_process; i++) {
struct process *p = &worker[i];
p->pid = INVALID_PID;
p->cpuid = i % get_ncpu();
}
...
}
```
> 當中可以看到此 worker 一開始被分配到不同的 cpu 底下，由此可以得到 cserv 中也有 worker。
:::
對於 cserv 來說，當一個子程序要做 I/O 這類型長時間的阻斷式程序，coroutine 會暫停程序，而不會阻塞其他行程。
## 修正記憶體操作的錯誤
Goal: 以 [Cppcheck](https://cppcheck.sourceforge.io/), [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer), [Valgrind](https://valgrind.org/) 等工具找出現行 cserv 程式碼的記憶體操作缺失，著手改進並提交 pull request。
程式碼運用到 coroutine，但沒正確呼叫 `coro_stack_free` 函式。
### 使用 `Address Sanitizer` 尋找記憶體缺失
> 使用 Address Sanitizer 的方法非常簡單，只需要在編譯的時候增加 `-fsanitize=address -static-libasan` 的選項即可
```diff
- CFLAGS += -O2 -g
+ CFLAGS += -O2 -g -fsanitize=address -static-libasan
- LDFLAGS= -ldl
+ LDFLAGS = -ldl -fsanitize=address -static-libasan
```
接下來就可以觀察具體來說到底發生甚麼樣的缺失。
-----
根據以上改動執行 `./cserv start` 後可以看到非常多錯誤訊息
```bash=
==64560==ERROR: AddressSanitizer: SEGV on unknown address (pc 0x55ff33de0c2e bp 0x55ff346dd250 sp 0x7f63b642fee0 T0)
==64560==The signal is caused by a READ memory access.
==64560==Hint: this fault was caused by a dereference of a high value address (see register values below). Dissassemble the provided pc to learn which register was used.
#0 0x55ff33de0c2e in add_to_timer_node src/coro/sched.c:126
#1 0x55ff33de0c2e in move_to_inactive_tree src/coro/sched.c:161
#2 0x55ff33de0c2e in schedule_timeout src/coro/sched.c:347
#3 0x55ff33de37c4 in worker_accept_cycle src/process.c:170
#4 0x55ff33de0331 in coro_routine_proxy src/coro/sched.c:323
#5 0x55ff33de00f0 (/home/joshua/linux2023/cserv/cserv+0xef0f0)
AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV src/coro/sched.c:126 in add_to_timer_node
```
根據以上的輸出，在 3 行回報了這錯誤的原因，並在第 12 行告訴我們實際上出問題的位置即存在 `sched.c` 的 `add_to_timer_node` 中
### 觀察`add_to_timer_node`
```c=
static void add_to_timer_node(struct timer_node *tm_node,
struct coroutine *coro)
{
struct rb_node **newer = &tm_node->root.rb_node, *parent = NULL;
while (*newer) {
struct coroutine *each = container_of(*newer, struct coroutine, node); /* 整個 each 都有問題 */
int result = coro->coro_id - each->coro_id;
parent = *newer;
if (result < 0) {
newer = &(*newer)->rb_left;
} else {
newer = &(*newer)->rb_right;
}
}
rb_link_node(&coro->node, parent, newer);
rb_insert_color(&coro->node, &tm_node->root);
}
```
反覆試驗之後發現問題出現在讀取紅黑樹時讀取到錯誤的位置，以上程式碼在第 7 行使用 `container_of` 取出 coroutine 在第 8 行的地方要讀取出 `each` 時，ASan 就會報錯。原本認為與 race condition 有關連，於是在 coroutine 中加入了 spin_lock，但同樣的錯誤還是會出現
```diff
+ spin_lock(&coro->lock);
int result = coro->coro_id - each->coro_id;
+ spin_unlock(&coro->lock);
```
~~也許這個問題也許出在紅黑樹的存放區塊，`memcache.[c|h]` 中 (但目前不知道要怎麼驗證)~~
:::success
原本的猜想：
* 還記得以前學 MIPS 的時候，jump 指令為 [pseudo addressing mode](http://allyouneedtoknowaboutcomputer.blogspot.com/2012/12/mips-addressing-mode.html)，也就是會將 memory block 限縮到 memory 位址實際上最後 26 位，而無法跳脫出 memory block。
> 這個猜想在使用 gdb 之後發現是不可能的事情
```bash
0x000055555555aba7 in add_to_timer_node (coro=0x5555555f5e90, tm_node=0x5555555ebc40) at src/coro/sched.c:122
```
在這邊可以發現位址都存在同一個 memory block 中。
:::
### coroutine 記憶體缺失
為了驗證 coroutine 存在記憶體缺失，勢必需要撰寫程式來驗證 `switch.h / sched.h`這個檔案中存在記憶體缺失。
既然目標很明確，接下來只要實驗看看究竟是哪一個 function 沒有正確的釋放記憶體。
第一件事情就是必須把所有功能改為其他程式可以存取到，並且把 sched 搬到要測試的主程式中
改為所有編譯單元 (compilation unit) 都可存取到符號
```diff
// src/coro/sched.c
- static inline <type> SomeFunction();
+ <type> SomeFunction();
// src/coro/sched.h
+ all functions
```
自己撰寫了測試程式之後，基本上可以把錯誤限縮到 `move_to_inactive_tree` 當中
```c
int main()
{
schedule_init(10, 1024);
event_loop_init(1024);
int tmp = dispatch_coro(NULL_func, NULL);
printf("dispatch Done errno: %d\n", tmp);
struct coroutine *coro = create_coroutine();
// move_to_active_list_head(coro);
get_coroutine();
run_active_coroutine();
dispatch_coro(NULL_func, NULL);
check_timeout_coroutine();
// start treating tree
// coroutine_switch(sched.current, &sched.main_coro);
move_to_inactive_tree(coro);
return 0;
}
```
這個小程式跑出來的結果竟與先前的 `asan` 錯誤相同，錯誤碼如下：
```c
==10711==ERROR: AddressSanitizer: SEGV on unknown address (pc 0x55db0b0235e7 bp 0x7ffee8368fd0 sp 0x7ffee8368f90 T0)
==10711==The signal is caused by a READ memory access.
==10711==Hint: this fault was caused by a dereference of a high value address (see register values below). Dissassemble the provided pc to learn which register was used.
#0 0x55db0b0235e7 in add_to_timer_node coro/sched.c:84
#1 0x55db0b0238e4 in move_to_inactive_tree coro/sched.c:119
#2 0x55db0b02a6d0 in main /home/joshua/linux2023/cserv/testing/test.c:41
#3 0x7ff116629d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
#4 0x7ff116629e3f in __libc_start_main_impl ../csu/libc-start.c:392
#5 0x55db0af41504 in _start (/home/joshua/linux2023/cserv/testing/test+0xf504)
```
### 仔細觀察 `move_to_inactive_tree` 的實作
這個 function 如同其名，就是要把輸入的 coroutine 放到 sched.cache 中的 rb_tree
問題出現在第二個 `add_to_timer_node`
```c=
void move_to_inactive_tree(struct coroutine *coro)
{
struct rb_node **newer = &sched.inactive.rb_node, *parent = NULL;
while (*newer) {
...
}
struct timer_node *tmp = memcache_alloc(sched.cache);
if (unlikely(!tmp)) /* still in active list */
return;
tmp->timeout = coro->timeout;
add_to_timer_node(tmp, coro);
rb_link_node(&tmp->node, parent, newer);
rb_insert_color(&tmp->node, &sched.inactive);
}
```
:::info
### `gdb` v.s `udb`
對於這次專案來說，能夠有任何成果都必須要歸功於工具的使用，尤其是能夠紀錄程式狀態的 `udb`，即便操作都跟 `gdb` 相同，但後者卻無法做到跳回前一行的狀態，能否在狀態之間切換會是把問題找出來的關鍵點。
:::
第 8 行將 tmp取出之後，未顧及 `rb-node` 是否充分初始化，而該 timer_node 的 root 會指向不能存取的區域。以下為 [`udb`](https://docs.undo.io/UDB-quickref.pdf) 擷取的片段
* 若打開 `ASan` 時可以發現其中的記憶體並未被初始化
```bash
$43 = {node = {rb_parent_color = 137446328392345678700,
rb_left = 0xbebebebebebebebe,
rb_right = 0xbebebebebebebebe},
root = {rb_node = 0xbebebebebebebebe},
timeout = -4702111234474983746}
```
* 若沒有打開 `ASan`
```bash
$43 = {node = {rb_parent_color = 0,
rb_left = 0x0,
rb_right = 0x0},
root = {rb_node = 0x0},
timeout = 0}
```
從這邊可以看到，不管左邊還是右邊都並沒有進行初始化，而也因為如此，利用 `container_of` 沒有辦法找出對應的 coroutine，重點在於初始化，於是在 tmp 後面新增一行初始化即可解決這個問題
```diff
struct timer_node *tmp = memcache_alloc(sched.cache);
if (unlikely(!tmp)) /* still in active list */
return;
+ tmp->root = RB_ROOT;
```
新增此行之後，`Asan` 就不會再 runtime 的時候瘋狂報錯了。也因此而完成了 [cserv 的 issue 6](https://github.com/sysprog21/cserv/issues/6)
### `coro_stack_free` 並未被正常呼叫
消除了前一個 address sanitizer 的問題之後，縱使不會在執行時跳出警告訊息，當使用 `./cserv stop` 的時候以下警告訊息冒出了 12 次
```bash
==8832==WARNING: ASan is ignoring requested
__asan_handle_no_return: stack type:
default top: 0x7ffe6c4a2000;
bottom 0x7f909f82c000;
size: 0x006dccc76000 (471587053568)
```
十二次，第一個聯想到的就是因為這個電腦的環境總共有 12 個核心，也就是 12 個 worker (by default)，可以實驗看看如果更改 `conf` 檔會不會有所改變
```bash
==9179==WARNING: ASan is ignoring requested __asan_handle_no_return: stack type: default top: 0x7fffc1b1a000; bottom 0x7fab52252000; size: 0x00546f8c8000 (362648731648)
False positive error reports may follow
For details see https://github.com/google/sanitizers/issues/189
==9178==WARNING: ASan is ignoring requested __asan_handle_no_return: stack type: default top: 0x7fffc1b1a000; bottom 0x7fab52252000; size: 0x00546f8c8000 (362648731648)
False positive error reports may follow
For details see https://github.com/google/sanitizers/issues/189
==9177==WARNING: ASan is ignoring requested __asan_handle_no_return: stack type: default top: 0x7fffc1b1a000; bottom 0x7fab52252000; size: 0x00546f8c8000 (362648731648)
False positive error reports may follow
For details see https://github.com/google/sanitizers/issues/189
==9176==WARNING: ASan is ignoring requested __asan_handle_no_return: stack type: default top: 0x7fffc1b1a000; bottom 0x7fab52252000; size: 0x00546f8c8000 (362648731648)
False positive error reports may follow
For details see https://github.com/google/sanitizers/issues/189
```
跟預期的一樣，警告的次數完全跟 worker 的數量相同。
### 總是無法正確的釋放 coroutine
為了驗證 coroutine 在 runtime 以及結束時並沒有正常的收回 coroutine 的空間，這邊利用 [`htstress`](https://hackmd.io/@sysprog/linux2022-ktcp) 在 runtime 時檢查每一個 worker 的 sched
```c
/* src/coro/sched.c */
void schedule_cycle()
{
for (;;) {
check_timeout_coroutine();
run_active_coroutine();
printf("current sched: %ld\n", sched.curr_coro_size);
sched.policy(get_recent_timespan());
run_active_coroutine();
}
}
```
照理來說，當一個 connection 在 timeout 或是結束連線時，必須要在伺服器端主動釋放連線，但總會有幾個 worker 在結束連結許久後遲遲不把 coroutine 釋放。
```bash=
$ terminal1 :./htstress -n 1000000 -c 100 -t 10 http://172.27.229.224:8081/
$ terminal2 :./cserv start
current sched: 1001
current sched: 50
current sched: 1001
current sched: 1
current sched: 50
current sched: 1001
current sched: 1001
current sched: 50
current sched: 1
current sched: 1001
current sched: 50
```
另外，並沒有在 `sched.c` 中觀察到任何 `sched.curr_coro_size--`，也許新增一個 [garbage collection](https://zh.wikipedia.org/zh-tw/%E5%9E%83%E5%9C%BE%E5%9B%9E%E6%94%B6_(%E8%A8%88%E7%AE%97%E6%A9%9F%E7%A7%91%E5%AD%B8)) 系統會是一個可行的選擇
### 實作垃圾回收系統
首先在 coroutine 的 structure 中加入 `refcnt`，當這個 coroutine 被引用時(也就是呼叫 `coro_routine_proxy` 時)，就會增加，若這個 coroutine timeout，需要被 dereference 時(在 `timeout_coroutine_handler` 當中)，則減少。
```diff
static __attribute__((__regparm__(1))) void coro_routine_proxy(void *args)
{
struct coroutine *coro = args;
+ coro->refcnt++;
coro->func(coro->args);
move_to_idle_list_direct(coro);
coroutine_switch(sched.current, &sched.main_coro);
}
static inline void timeout_coroutine_handler(struct timer_node *node)
{
struct rb_node *recent;
while ((recent = node->root.rb_node)) {
struct coroutine *coro = container_of(recent, struct coroutine, node);
rb_erase(recent, &node->root);
coro->active_by_timeout = 1;
+ coro->refcnt--;
move_to_active_list_tail_direct(coro);
}
}
```
除此之外在 `schedule_cycle` 中新增 cleanup function，
```diff
void schedule_cycle()
{
for (;;) {
check_timeout_coroutine();
run_active_coroutine();
printf("current sched: %ld\n", sched.curr_coro_size);
+ /* check garbage */
+ if (sched.curr_coro_size > sched.max_coro_size / 2){
+ collect_cycle();
+ }
sched.policy(get_recent_timespan());
run_active_coroutine();
}
}
```
但目前還無法正確的實作出來，當重新啟動時，還是無法把相對應的 coroutine 刪除，也許 timeout_handler 沒有正確的把 sched.curr_coro_size 給往下調整
## 效能評比和分析
對 NGINX, [lwan](https://github.com/lpereira/lwan), cserv 三者進行效能分析，並從實驗數據解讀，探討現行 cserv 可改進之處。
## 導入 AIO
研讀〈[Thread Pools in NGINX Boost Performance 9x!](https://www.nginx.com/blog/thread-pools-boost-performance-9x/)〉，將 AIO 導入到 cserv，從而提高大檔案傳輸的效率。
### Synchronous I/O v.s Asynchronous I/O
在理解為何導入 AIO 可以提升大檔案傳輸效率的時候，我們可以先了解非同步 I／O 以及同步 I／O 的區別。
在恐龍書上其實只有講述這三種不同的 I／O，其中 Blocking 就是 Synchronous。
* Synchrous I/O - 當行程必須要呼叫 I/O 裝置時，整個行程都會停下來等他完成
以下例子來解釋 Synchronous (blocking) I/O
```c
int size = read(fd, buf, length); /* 在此行暫停等到 read 結束 */
if (size <= 0)
return;
/* 處理 read 完之後的結果 */
```
Synchronous I/O 有一些優點，那就是實作起來非常方便而且可讀性也很高。但缺點就非常多，當讀取的檔案過大，這個方法只會對系統造成非常大的衝擊
> 這邊想要請教老師，我一直想要把此種衝擊用 Convoy effect 來解釋，但怕定義不符合。究竟能不能使用護衛效應來解釋 blocking I/O
* Asynchronous I/O - 是一種非阻塞的 I/O 他允許應用程式在發起 I/O 之後繼續做不同的事情，而不需要等待這個操作完成。
Asynchronous I/O 跟前者的優缺點幾乎是對調的，他可以高效利用資源，提高性能。但缺點就是複雜性相對起來高很多，而且也需要較多額外處理才可以確保程式的正確執行。
以下例子簡易描述 aio_read 的流程
```c
/* I/O in background */
aio_read(aiocpb);
/* do sth else */
do_sth();
/* collect result */
collect();
```
-----
Sign in with Wallet
Connect another wallet