---
# System prepended metadata

title: 2022q1 seHTTPd 改進

---

# 2022q1 seHTTPd 改進
contributed by < `haoyu0970624763` >

> [作業說明](https://hackmd.io/@sysprog/linux2022-sehttpd)
> [GitHub](https://github.com/haoyu0970624763/sehttpd)

### 壓力測試

* [apache bench](https://httpd.apache.org/docs/current/programs/ab.html)
    * 用法: `ab -n 100000 -c 500 -k http://127.0.0.1:8081/`
    * 無法有效反映出多執行緒的特性
* [htstress](https://github.com/sysprog21/khttpd/blob/master/htstress.c)
    * 用法: 
        * 編譯: `gcc -std=gnu11 -Wall -Wextra -Werror -o htstress htstress.c -lpthread`
        * 使用: `./htstress -n 10000 -c 100 -t 8 localhost:8081`
    * 使用 epoll 觸發、可反映多執行緒的特性
* [wrk](https://github.com/wg/wrk)
    * 只支援 HTTP 通訊協定的連線請求（如 get, post 等），若要執行 get 之外的 HTTP 請求，需要使用者自行撰寫 lua 腳本
*  尚有 [httperf](https://github.com/httperf/httperf) , [weighttp](https://github.com/lighttpd/weighttp) 等壓力測試工具等

### 使用 computed goto 改寫 switch-case

在 [Computed goto for efficient dispatch tables](https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables) 一文中提及, goto 在執行效率上比 switch-case 要更好，主要可以從 2 個層面探討:
*    switch-case 會做 bounds checking  , 檢查是否有 default case 的狀況，即使程式中的 switch 沒有寫到 default case，編譯期間仍會產生強制檢查的程式，這是為了符合 C99 的標準
> If no converted case constant expression matches and there is no default label, no part of the switch body is executed.
*    另一部份則是 branch prediction 

branch prediction 的部份可參考老師之前撰寫的
[switch-背後的-goto-和實作考量](https://hackmd.io/@sysprog/c-control-flow?type=view#switch-%E8%83%8C%E5%BE%8C%E7%9A%84-goto-%E5%92%8C%E5%AF%A6%E4%BD%9C%E8%80%83%E9%87%8F)

我們透過 [Labels as Values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html)，在 http_parser.c 的兩個函式中加入 conditions 作為 label address table 讓 state 進行查表，並透過 goto 跳躍到對應的程式碼。

以 `http_parse_request_body` conditions 為範例

```
const void *conditions[] = {
    &&c_start,
    &&c_key,
    &&c_spaces_before_colon,
    &&c_spaces_after_colon,
    &&c_value,
    &&c_cr,
    &&c_crlf,
    &&c_crlfcr,
};
```

接著用 goto 取代 switch

```
goto *conditions[state];
```


我用 perf 觀察原本的程式碼 以及 使用 computed goto 改寫後的效率

switch 版本的觀測紀錄如下
```
$ sudo perf stat ./sehttpd -p 8081

$ ./htstress -n 100000 -c 1 -t 4 http:/127.0.0.1:8081/

requests:      100000
good requests: 100000 [100%]
bad requests:  0 [0%]
socket errors: 0 [0%]
seconds:       4.626
requests/sec:  21617.794


 Performance counter stats for './sehttpd -p 8081':

          4,551.69 msec task-clock                #    0.498 CPUs utilized          
               458      context-switches          #  100.622 /sec                   
                36      cpu-migrations            #    7.909 /sec                   
           100,070      page-faults               #   21.985 K/sec                  
    14,861,152,979      cycles                    #    3.265 GHz                    
    10,629,920,230      instructions              #    0.72  insn per cycle         
     2,043,158,393      branches                  #  448.879 M/sec                  
        25,004,139      branch-misses             #    1.22% of all branches
```

goto 版本的觀測紀錄如下
```
$ sudo perf stat ./sehttpd -p 8081

$ ./htstress -n 100000 -c 1 -t 4 http://127.0.0.1:8081/

requests:      100000
good requests: 100000 [100%]
bad requests:  0 [0%]
socket errors: 0 [0%]
seconds:       4.150
requests/sec:  24094.580


Performance counter stats for './sehttpd -p 8081':

          4,093.64 msec task-clock                #    0.207 CPUs utilized          
               359      context-switches          #   87.697 /sec                   
                34      cpu-migrations            #    8.306 /sec                   
           100,071      page-faults               #   24.445 K/sec                  
    13,730,441,736      cycles                    #    3.354 GHz                    
    10,613,940,571      instructions              #    0.77  insn per cycle         
     2,038,720,358      branches                  #  498.021 M/sec                  
        24,397,318      branch-misses             #    1.20% of all branches        
    
```

可以看出在 computed goto 版本中的執行的 cycles 少於 switch 版本的 且 branch miss rate 也略少於 switch 版本

在改寫的過程中有參照 [oscarshiang](https://hackmd.io/@oscarshiang/linux_sehttpd#2020q1-Homework6-sehttpd) 的共筆，不過在測量的過程中我沒辦法觀測出 branch miss rate 有明顯的改善，我更傾向在這個實驗中 goto 之所以效能更好的原因在於減少了`bounds checking`

#### 程式碼更動
更改 buffer size 從 8124 更改為 8192 , 變成 2 的冪 , 我們就可以透過跟 (MAX_BUF-1) 做 bitwise-AND , 可取得 0~8191的範圍來取代 % 的運算 , 因為 & 運算比 % 來的更有效率

原本
```c
p = (uint8_t *) &r->buf[pi % MAX_BUF];
```

更改成
```c
p = (uint8_t *) &r->buf[pi & (MAX_BUF - 1)];
```

:::warning
可將 `pi % MAX_BUF` 改為 `pi & (MAX_BUF - 1)`，當 `MAX_BUF` 為 2 的冪
詳見: [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
:notes: jserv
:::

###  epoll 工作模式
節錄自 [epoll](https://man7.org/linux/man-pages/man7/epoll.7.html) 中
>monitoring multiple file descriptors to see if I/O is possible on any of them

epoll 用來監聽 I/O 事件是否準備好了 , 而 epoll 又可分成
* Level-triggered
    * 當 file descriptors 準備就緒時 , kernel 透過 epoll 發送通知告知我們已就緒,接著就可以進行IO操作, 當我們長時間沒有進行操作時 , kernel 會繼續發送通知給我們
    * socket 在 readable/writable 狀態時，epoll_wait會返回該socket
* Edge-triggered
    * 當 file descriptors 從還沒準備好轉變成準備好時,kernel 通過 epoll 發送通知告知我們,並且不再發送第二次通知

以 [test_epoll_lt_and_et](https://github.com/Manistein/test_epoll_lt_and_et) 舉例說明可能會講的更清楚

在客户端输入aabbcc，客户端發送包含 aabbcc 内容的數據包到服務端，在服務端一次可讀取2個字元的情況下
* lt 模式下, 服務端先讀取 aa 並輸出 , epoll_wait 可返回 socket 繼續讀取資料 , 讀取 bb並輸出 , 依此類推
* et 模式下, 服務端先讀取 aa 並輸出 , epoll_wait 只有等到新的數據到達時才會被喚醒 , bbcc 會遺留在服務端的 buffer

我們可以看出
1. lt 模式下的操作更為直覺與簡單
2. et 模式下可能隱含較多的 bug

此外, et 模式的效能會比 lt 來的更好 , 原因在於當 kernel 發送通知後 , 會把該事件從 ready list 中刪除 , 而 lt 模式則不會從 ready list 中刪除該事件 , 當 list中有越來越多事件時 , epoll 下次要通知用戶時 , 搜尋 list 的時間會增長

兩種模式各有其優缺點 , 在高效的 web server 中 , 我認為採用 edge-triggered 的方式可能會更合適


### timer

web server 需要同時間處理多項請求 , 要優先處理哪個請求就變成一個重要的課題 , 而常見的作法之一是先處理最快到期的請求

在 [mainloop.c](https://github.com/haoyu0970624763/sehttpd/blob/master/src/mainloop.c)   中 server 接收請求後會先呼叫 [timer.c](https://github.com/haoyu0970624763/sehttpd/blob/master/src/timer.c) 中的`handle_expired_timers` 函式處理已經超出期限但還沒處理的請求 , 接著會呼叫 `add_timer` 函式將新的請求加入 queue 中 

而 `add_timer` 中根據 `node->key = current_msec + timeout` (`current_msec` 表示當前的時間 , `timeout` 代表處理請求的最大延遲時間),顯而易見的可以發現 node->key 值代表的是此請求處理的期限 

我們想取得最快到期的請求就可以透過 priority queue(MIN_HEAP)的方式獲取 , 也就是 `timer.c` 中的 `prio_queue_min` 函式
 

