Linux 核心專題: 高效網頁伺服器開發

執行人: JoshuaLee0321
GitHub
專題講解影片
期末自我評量

提問清單

• ?

任務簡述

在 ktcp 提到，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〉，對比 NGINX 和 cserv，歸納架構設計的異同，並著手改進後者。

參考資訊:

• ktcp: cserv 高效網頁伺服器
• The Architecture of Open Source Applications: nginx
• Inside NGINX: How We Designed for Performance & Scale

實驗環境

$ lscpu

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〉，對比 NGINX 和 cserv，歸納架構設計的異同，逐一探討 cserv 相對於 NGINX 在高效能表現尚欠缺的關鍵設計，例如 AIO。

主從式架構

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 的架構，讓 不同的 workers 常駐在 cpu 上，同時讓另外一個 master 去處理其他 worker 需要的高權限操作 (e.g., Fetch file, transfer file, print, etc.)。

根據〈Inside NGINX: How We Designed for Performance & Scale〉，Nginx 的 master 專門執行一些特權操作如讀取設定檔案，bind 等等，worker 則負責把所有的工作完成，例如讀寫以及處理連線，而 worker 之所以會有效率的處理連線，也可以參照
NGINX 開發日誌中以送貨員以及排隊等候的機制去看待這個問題

假設有一堆顧客，他們需要取貨，而有些貨物(1-3 號箱)盡在眼前，同時也很多貨物存在遙遠的倉庫中，此時注意這邊這位工作者(worker) 只會盲目的遵從目前顧客的要求，並且服務目前的顧客，假設有一個顧客要求比較遠的 4 號箱子，如此一來造成了護衛效應，擋住了後面也許有機會服務更快的顧客。

讓我們再想想另外一個情形，當這個 worker 學乖了，他利用一個送貨區，當每次有太遠的貨物需要取貨時，他並不會自己慢慢跑過去，而是一通電話叫送貨人員送來。如此一來就可以更快的服務到其他顧客，與此同時目前顧客也不會因服務其他人而導致他的任務沒有進展。

而 NGINX 的 worker 也一樣，當一個進程可能需要很長的操作時間時，他不會自己處理，而是將這個任務放進 TaskQueue 中，而任何空閒的 Thread 都可以將此 queue 中的任務取出來執行。

TasksQueue 以及 Thread Pool 在這邊扮演的腳色就是送貨員以及送貨車，Taskqueue 會接收由 worker process 來的工作，處理完之後再把結果送回 worker process 中。

為驗證這個事實，可以先使用以下命令

~$ 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 以達到相對高效的結果。

cserv 亦有 worker

根據

// 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, Address Sanitizer, Valgrind 等工具找出現行 cserv 程式碼的記憶體操作缺失，著手改進並提交 pull request。

程式碼運用到 coroutine，但沒正確呼叫 coro_stack_free 函式。

使用 Address Sanitizer 尋找記憶體缺失

使用 Address Sanitizer 的方法非常簡單，只需要在編譯的時候增加 -fsanitize=address -static-libasan 的選項即可

- CFLAGS += -O2 -g 
+ CFLAGS += -O2 -g -fsanitize=address -static-libasan
- LDFLAGS= -ldl
+ LDFLAGS = -ldl -fsanitize=address -static-libasan

接下來就可以觀察具體來說到底發生甚麼樣的缺失。

---

根據以上改動執行 ./cserv start 後可以看到非常多錯誤訊息

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

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，但同樣的錯誤還是會出現

+   spin_lock(&coro->lock);
    int result = coro->coro_id - each->coro_id;
+   spin_unlock(&coro->lock);

也許這個問題也許出在紅黑樹的存放區塊，memcache.[c|h] 中 (但目前不知道要怎麼驗證)

原本的猜想：

• 還記得以前學 MIPS 的時候，jump 指令為 pseudo addressing mode，也就是會將 memory block 限縮到 memory 位址實際上最後 26 位，而無法跳脫出 memory block。

這個猜想在使用 gdb 之後發現是不可能的事情

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) 都可存取到符號

// src/coro/sched.c
- static inline <type> SomeFunction();
+ <type> SomeFunction();
// src/coro/sched.h
+ all functions

自己撰寫了測試程式之後，基本上可以把錯誤限縮到 move_to_inactive_tree 當中

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 錯誤相同，錯誤碼如下：

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

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

gdb v.s udb

對於這次專案來說，能夠有任何成果都必須要歸功於工具的使用，尤其是能夠紀錄程式狀態的 udb，即便操作都跟 gdb 相同，但後者卻無法做到跳回前一行的狀態，能否在狀態之間切換會是把問題找出來的關鍵點。

第 8 行將 tmp取出之後，未顧及 rb-node 是否充分初始化，而該 timer_node 的 root 會指向不能存取的區域。以下為 udb 擷取的片段

• 若打開 ASan 時可以發現其中的記憶體並未被初始化

$43 = {node = {rb_parent_color = 137446328392345678700, 
               rb_left = 0xbebebebebebebebe, 
               rb_right = 0xbebebebebebebebe},  
       root = {rb_node = 0xbebebebebebebebe},
       timeout = -4702111234474983746}

• 若沒有打開 ASan

$43 = {node = {rb_parent_color = 0, 
               rb_left = 0x0, 
               rb_right = 0x0},  
       root = {rb_node = 0x0},
       timeout = 0}

從這邊可以看到，不管左邊還是右邊都並沒有進行初始化，而也因為如此，利用 container_of 沒有辦法找出對應的　coroutine，重點在於初始化，於是在 tmp 後面新增一行初始化即可解決這個問題

    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

coro_stack_free 並未被正常呼叫

消除了前一個 address sanitizer 的問題之後，縱使不會在執行時跳出警告訊息，當使用 ./cserv stop 的時候以下警告訊息冒出了 12 次

==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 檔會不會有所改變

==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 在 runtime 時檢查每一個 worker 的 sched

/* 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 釋放。

$ 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 系統會是一個可行的選擇

實作垃圾回收系統

首先在 coroutine 的 structure 中加入 refcnt，當這個 coroutine 被引用時(也就是呼叫 coro_routine_proxy 時)，就會增加，若這個 coroutine timeout，需要被 dereference 時(在 timeout_coroutine_handler 當中)，則減少。

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，

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, cserv 三者進行效能分析，並從實驗數據解讀，探討現行 cserv 可改進之處。

導入 AIO

研讀〈Thread Pools in NGINX 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

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 的流程

/* I/O in background */
aio_read(aiocpb);

/* do sth else */
do_sth();
/* collect result */
collect();

---