--- title: 2022 年春季 Linux 核心設計課程作業 —— seHTTPd image: https://repository-images.githubusercontent.com/253265147/e39b3700-77a9-11ea-9676-267ecffaedd4 description: 檢驗學員對 Linux 核心 I/O multiplexor, non-blocking I/O、事件驅動,和多執行緒程式設計的認知 tags: linux2022 --- # K09: sehttpd ###### tags: `linux2022` > 主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2022 年系統軟體課程](https://www.facebook.com/groups/system.software2022/) :mega: 返回「[Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程進度表 ==[解說錄影](https://youtu.be/XMKNPiIYVCE?t=5361)== ## :memo: 預期目標 * 學習 [Linux 核心設計: 針對事件驅動的 I/O 模型演化](https://hackmd.io/@sysprog/linux-io-model) 和對應的 Linux 系統呼叫; * 建構高效事件驅動的 web 伺服器,過程中深度體會 Linux 系統呼叫、行程和執行緒的運作機制; * 學習透過 eBPF 進行作業系統層級的動態分析,並針對 web 伺服器發展特定的分析工具; ## :shark: seHTTPd [seHTTPd](https://github.com/sysprog21/sehttpd) 是個高效的 web 伺服器,涵蓋並行處理、I/O 事件模型、epoll、[React pattern](http://en.wikipedia.org/wiki/Reactor_pattern),和 Web 伺服器在事件驅動架構的考量,可參見 [高效 Web 伺服器開發](https://hackmd.io/@sysprog/fast-web-server)。 預先準備的套件: (eBPF 作為後續分析使用) ```shell $ sudo apt install wget $ sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 4052245BD4284CDD $ echo "deb https://repo.iovisor.org/apt/$(lsb_release -cs) $(lsb_release -cs) main" | sudo tee /etc/apt/sources.list.d/iovisor.list $ sudo apt-get update $ sudo apt-get install bcc-tools linux-headers-$(uname -r) $ sudo apt install apache2-utils ``` 取得程式碼和編譯: ```shell $ git clone https://github.com/sysprog21/sehttpd $ cd sehttpd $ make ``` 預期可見 `sehttpd` 這個執行檔。接著透過內建的 test suite 來測試: ```shell $ make check ``` ### 對 seHTTPd 進行壓力測試 首先,我們可用「古典」的方法,透過 [Apache Benching tool](https://httpd.apache.org/docs/current/programs/ab.html) 對 seHTTPd 進行壓力測試。在一個終端機視窗執行以下命令: ```shell $ ./sehttpd ``` 切換到網頁瀏覽器,開啟網址 `http://127.0.0.1:8081/` 應在網頁瀏覽器畫面中見到以下輸出: :::info Welcome! If you see this page, the seHTTPd web server is successfully working. ::: 然後在另一個終端機視窗執行以下命令: ```shell $ ab -n 10000 -c 500 -k http://127.0.0.1:8081/ ``` 參考程式輸出: (數值若跟你的測試結果有顯著出入,實屬正常) ```shell Server Software: seHTTPd Server Hostname: 127.0.0.1 Server Port: 8081 Document Path: / Document Length: 241 bytes Concurrency Level: 500 Time taken for tests: 0.927 seconds Complete requests: 10000 Failed requests: 0 Keep-Alive requests: 10000 Total transferred: 4180000 bytes HTML transferred: 2410000 bytes Requests per second: 10784.81 [#/sec] (mean) Time per request: 46.361 [ms] (mean) Time per request: 0.093 [ms] (mean, across all concurrent requests) Transfer rate: 4402.39 [Kbytes/sec] received ``` 留意到上述幾項: * `-k` 參數: 表示 "Enable the HTTP KeepAlive feature",也就是在一個 HTTP session 中執行多筆請求 * `-c` 參數: 表示 concurrency,即同時要下達請求的數量 * `-n` 參數: 表示壓力測試過程中,期望下達的請求總量 關於輸出結果,請詳閱 [ab - Apache HTTP server benchmarking tool](https://httpd.apache.org/docs/current/programs/ab.html) 說明。 :notebook: 需要注意的是,`ab` 無法有效反映出多執行緒的特性 (`ab` 自身就消耗單核 100% 的運算量),因此我們才會在 [khttpd](https://github.com/sysprog21/khttpd) 提供 [htstress.c](https://github.com/sysprog21/khttpd/blob/master/htstress.c),後者提供 `-t` 選項,能夠依據測試環境的有效 CPU 個數進行分配。 [ab - Apache HTTP server benchmarking tool](https://httpd.apache.org/docs/current/programs/ab.html) 的實作從今日的 GNU/Linux 或 FreeBSD 來說,算是過時且未能反映系統特性,除了 `htstress`,尚可使用 [wrk](https://github.com/wg/wrk),該專案的訴求是 > wrk is a modern HTTP benchmarking tool capable of generating significant load when run on a single multi-core CPU. It combines a multithreaded design with scalable event notification systems such as epoll and kqueue. 另一個可測試 HTTP 伺服器負載的工具是 [httperf](https://github.com/httperf/httperf)。 ### 例外處理 倘若你將 seHTTPd 執行後,不立刻關閉,隨即較長時間的等待和重新用上述 `ab` 多次測試 (變更 `-n` 和 `-c` 參數的指定數值) 後,可能會遇到以下錯誤狀況 (部分) 1. Segmentation fault; 2. 顯示訊息 `[ERROR] (src/http.c:253: errno: Resource temporarily unavailable) rc != 0` 可用 `$ grep -r log_err` 搜尋原始程式碼,以得知現有的例外處理機制 (注意: 裡頭存在若干缺失,切勿「舉燭」)。 ## :microscope: 以 [eBPF](https://en.wikipedia.org/wiki/Berkeley_Packet_Filter) 追蹤 HTTP 封包 首先,研讀 [Linux 核心設計: 透過 eBPF 觀察作業系統行為](https://hackmd.io/@sysprog/linux-ebpf) 以理解核心動態追蹤機制,後者允許我們使用非侵入式的方式,不用去修改我們的作業系統核心內部,不用去修改我們的應用程式,也不用去修改我們的業務程式碼或者任何系統配置,就可快速高效地精確獲取我們想要的資訊。 在 [seHTTPd](https://github.com/sysprog21/sehttpd) 原始程式碼的 [ebpf 目錄](https://github.com/sysprog21/sehttpd/tree/master/ebpf)提供簡易的 HTTP 封包分析工具,就是建構在 eBPF 的基礎之上,並透過 [IO Visor](https://github.com/iovisor) 提供的工具來運作。 概念示意圖: ![](https://i.imgur.com/3cgRcmI.png) 使用方式: (預先在另一個終端機視窗執行 `$ ./sehttpd`) ```shell $ cd ebpf $ sudo python http-parse-sample.py ``` 注意: 這個工具預設監控 `eth0` 這個網路介面 (network interface)。倘若你的預設網路介面不是 `eth0`,你需要依據 `ip` 工具的輸出,決定監控哪個網路介面。舉例來說,在某台 GNU/Linux 機器上執行以下命令: ```shell $ ip link ``` 你會見到若干輸出,如果你的環境裡頭已執行 [Docker](https://www.docker.com/),輸出數量會很可觀,但不用擔心,排除 `lo`, `tun`, `virbr`, `docker`, `br-`, `veth` 開頭的輸出,然後就剩下 `enp5s0` 這樣的網路介面 (端視你的網路硬體而有不同),於是可將上述命令改為: ```shell $ sudo python http-parse-sample.py -i enp5s0 ``` 然後打開網頁瀏覽器,多次存取和刷新 `http://127.0.0.1:8081/` 網址,然後你應可在上述執行 Python 程式的終端機見到類似以下的輸出: ``` TCP src port '51670' TCP dst port '8081' ¢GET / HTTP/1.1 IP hdr length '20' IP src '192.168.50.97' IP dst '61.70.212.51' TCP src port '8081' TCP dst port '51670' ÌHTTP/1.1 304 Not Modified ``` 關於上述程式運作的概況,可參考 [Appendix C](https://hackmd.io/@0xff07/r1f4B8aGI)。 透過 eBPF 追蹤 [fibdrv](https://github.com/sysprog21/fibdrv) 核心模組的運作機制,可參見 [0xff07 的共筆](https://hackmd.io/@0xff07/S1vfNHWB8) * [對應的程式碼](https://github.com/0xff07/fibdrv/) ## :runner: [Thread Pool](https://en.wikipedia.org/wiki/Thread_pool) 和並行議題 現行 [seHTTPd](https://github.com/sysprog21/sehttpd) 運用 non-blocking I/O 和 I/O multiplexor 機制,在單執行緒仍可有效能表現,但若我們想更充分運用硬體特性,勢必要透過多執行緒和克服相關並行議題。請事先研讀 [並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency) 引入 [thread pool](https://en.wikipedia.org/wiki/Thread_pool) 的設計,需要非常小心,否則容易致使反效果 —— 分配更多的執行緒,但最終的伺服器效能還不如單執行緒為基礎的實作。應充分研讀 [An Introduction to Lock-Free Programming](https://preshing.com/20120612/an-introduction-to-lock-free-programming/),以掌握 lockless/lock-free 程式設計背景知識。 多執行緒的程式不容易除錯,可善用 [ThreadSanitizer](https://github.com/google/sanitizers/wiki/ThreadSanitizerCppManual) 這項已整合到 gcc/clang。修改 `Makefile`,在 `LDFLAGS =` 後方新增下列: ```shell # ThreadSanitizer CFLAGS += -fsanitize=thread LDFLAGS += -fsanitize=thread ``` 之後 `$ make clean all` 即可編譯出支援 [ThreadSanitizer](https://github.com/google/sanitizers/wiki/ThreadSanitizerCppManual) 的 seHTTPd 執行檔。 ## 使用 computed goto 改寫 switch-case 在 [Computed goto for efficient dispatch tables](https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables) 一文提到:因為 switch 還是會有判斷數值的處理,所以在執行效率上 `goto` 還是會比使用 `switch-case` 來得好,而且使用 `goto` 也可以避免使用 `switch-case` 帶來 branch miss 的損失。 搭配 GNU extension 中提供的 [Labels as Values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html),在 `http_parser.c:http_parse_request_line` 中的加入 `conditions` 作為 label address table 讓其可用 `state` 來查表,並直接利用 `goto` 跳躍到對應的程式碼。 ```cpp const void *conditions[] = {&&c_start, &&c_method, &&c_spaces_before_uri, &&c_after_slash_in_uri, &&c_http, &&c_http_H, &&c_http_HT, &&c_http_HTT, &&c_http_HTTP, &&c_first_major_digit, &&c_major_digit, &&c_first_minor_digit, &&c_minor_digit, &&c_spaces_after_digit, &&c_almost_done}; ``` 接著將 `switch` 的部分取代為 `goto` ```cpp goto *conditions[state]; ``` 接著利用 perf 觀察使用 computed goto 改寫後關於 branch prediction 的表現: ```shell $ sudo record -e branch-misses:u,branch-instructions:u ./sehttpd $ ./htstress -n 100000 -c 1 -t 4 http://localhost:8081/ requests: 100000 good requests: 100000 [100%] bad requests: 0 [0%] socker errors: 0 [0%] seconds: 3.839 requests/sec: 26047.527 $ sudo perf report Available samples 12K branch-misses:u 14K branch-instructions:u ``` 使用 switch-case 的版本: ```shell $ sudo record -e branch-misses:u,branch-instructions:u ./sehttpd $ ./htstress -n 100000 -c 1 -t 4 http://localhost:8081/ requests: 100000 good requests: 100000 [100%] bad requests: 0 [0%] socker errors: 0 [0%] seconds: 4.000 requests/sec: 24997.963 $ sudo perf report Available samples 13K branch-misses:u 14K branch-instructions:u ``` 可見 computed goto 版本的伺服器因為在 branch miss 的數量較使用 switch-case 版本少,所以執行的時間得到改善。 接著因為在宣告 `state` 與 `conditions` 時裡面的名稱有高度的重疊,所以改以 [X macro 的方式](https://en.wikipedia.org/wiki/X_Macro)簡化宣告的程式碼 ```cpp #define state_code(X) \ X(_start), X(_method), X(_spaces_before_uri), X(_after_slash_in_uri), \ X(_http), X(_http_H), X(_http_HT), X(_http_HTT), X(_http_HTTP), \ X(_first_major_digit), X(_major_digit), X(_first_minor_digit), \ X(_minor_digit), X(_spaces_after_digit), X(_almost_done) #define define_enum(name, code) enum { code(enum_entry) } name #define enum_entry(entry) s##entry #define define_label_array(name, code) void *name[] = {code(label_entry)} #define label_entry(entry) &&c##entry ``` 利用巨集組合 enumerate 的變數與 label 並將 macro 作為變數傳到 `state_code` 這個 macro 中,展開後就會得到與上方宣告一樣的結果 設計 `dispatch()` 的 macro 來進行各種情況的程式碼跳躍。 ```cpp #define dispatch(i) \ do { \ if (i >= r->last) \ interrupt_parse(); \ p = (uint8_t *) &r->buf[pi % MAX_BUF]; \ ch = *p; \ goto *conditions[state]; \ } while (0) ``` 因為將 for 迴圈的功能也實作在 `dispatch` 中,所以使用 computed goto 進行 `dispatch` 之前,也要處理字串迭代的更新。 但考慮到在進入 for 迴圈的時候並不會將 `pi` 遞增,所以為了讓進入迴圈前與進入迴圈後 `dispatch` 的行爲與原先 for 迴圈的實作一致,此處將 `pi` 作為巨集參數的參數帶入,讓其可在二種不同的情況做不同的處理。 ## :checkered_flag: 自我檢查清單 - [ ] 在 [高效 Web 伺服器開發](https://hackmd.io/@sysprog/fast-web-server) 提到 epoll 的兩種工作模式 (level trigger vs. edge trigger),對照 [seHTTPd](https://github.com/sysprog21/sehttpd) 原始程式碼,解釋 epoll 工作模式的設定和在 web 伺服器實作的考量點 $\to$ 搭配程式碼實驗並說明 > 提示: 參考實驗程式碼: [test_epoll_lt_and_et](https://github.com/Manistein/test_epoll_lt_and_et) - [ ] [seHTTPd](https://github.com/sysprog21/sehttpd) 內部為何有 timer,考量點和具體作用為何?timer 為何用到 priority queue 呢?能否在 Linux 核心原始程式碼找到類似的用法? - [ ] lock-free/lockless 的 thread pool 的效益為何?在高並行的應用場域 (如 web 伺服器),可以如何發揮 thread pool 的效益呢? - [ ] 解釋前述 `http-parse-sample.py` 運作機制,以及 eBPF 程式在 Linux 核心內部分析封包的優勢為何? ## :penguin: 作業要求 * 回答上述「自我檢查清單」的所有問題,需要附上對應的參考資料和必要的程式碼,以第一手材料 (包含自己設計的實驗) 為佳 :::warning :warning: 如果你在 2022 年 4 月 19 日前,已從 GitHub [sysprog21/sehttpd](https://github.com/sysprog21/sehttpd) 進行 fork,請依據 [Alternatives to forking into the same account](https://github.community/t5/Support-Protips/Alternatives-to-forking-into-the-same-account/ba-p/7428) 一文,對舊的 repository 做對應處置,然後重新 fork ::: * 在 GitHub 上 fork [sehttpd](https://github.com/sysprog21/sehttpd),目標是修正 seHTTPd 的執行時期的缺失,提升效能和穩健度 (robustness),需要充分落實以下: * 修改 [htstress.c](https://github.com/sysprog21/khttpd/blob/master/htstress.c) 並放入 git repository,學習 [wrk](https://github.com/wg/wrk) 和 [httperf](https://github.com/httperf/httperf) 的部分特徵,強化對 seHTTPd 伺服器的測試 (除了效能,也該涵蓋正確性測試,包含檔案存取),特別是 concurrency 和 multi-threading 等議題; * 強化 seHTTPd 實作的例外處理,得以長時間持續運作,應修正各式程式邏輯、記憶體管理,和 I/O 事件模型處理相關的缺失; * 參考上述 eBPF 範例程式,實作專門動態分析 seHTTPd 執行過程中 Linux 核心內部事件、系統呼叫,關鍵操作耗費的時間等等的工具; * 引入 [thread pool](https://en.wikipedia.org/wiki/Thread_pool) 到 seHTTPd 探討對 web 伺服器的效能的影響,過程中應該充分量化各因素,尤其是在多執行緒的環境中 non-blocking I/O 搭配事件驅動程式設計的實作; * 提供基本的 [directory listing](https://cwiki.apache.org/confluence/display/httpd/DirectoryListings) 功能: 可指定 `WWWROOT`,例如 [httpd](https://github.com/sysprog21/concurrent-programs/tree/master/httpd) * 以 [sendfile](http://man7.org/linux/man-pages/man2/sendfile.2.html) 系統呼叫改寫 `src/http.c` 裡頭傳遞檔案內容的實作 (對應到 `serve_static` 函式),思考在高並行的環境中,檔案系統 I/O 的開銷及改進空間; * 嘗試以 `io_uring` 改寫 seHTTPd,並比較原本使用 `epoll` 的處理效率 * 用 `$ grep -r TODO *` 找出 seHTTPd 的待做事項,予以列出並充分闡述具體執行方法,例如涉及動態記憶體管理、長期閒置連線的處理機制等等。 > ==[mimalloc](https://github.com/microsoft/mimalloc)== 的運用是個值得留意的改進方向,可參考共筆 [mimalloc 實作機制和改善](https://hackmd.io/@jserv/BynrpV0eB) 和 [mimalloc 實驗](https://hackmd.io/@hankluo6/mimalloc) * 複習 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 裡頭針對 [Valgrind](https://valgrind.org/) 和建構其上的 [Massif](https://valgrind.org/docs/manual/ms-manual.html) 工具,用以分析 seHTTPd 的記憶體開銷,設計實驗讓 seHTTPd 得以長時間運作,並搭配各式工作負載 (work load)。 * 在你的開發環境中安裝 [Nginx](https://nginx.org/en/) 伺服器並比較由你強化後的 seHTTPd 和 [Nginx](https://nginx.org/en/) 的效能差異,試圖解釋針對 Linux 的改進空間 ## 繳交方式 編輯 [Homework6 作業區共筆](https://hackmd.io/@sysprog/linux2022-homework6),將你的觀察、上述要求的解說、應用場合探討,以及各式效能改善過程,善用 gnuplot 製圖,紀錄於新建立的共筆 ## 截止日期 * May 10, 2022 (含) 之前 > 越早在 GitHub 上有動態、越早接受 code review,評分越高 ## 作業觀摩 * [jwang0306](https://hackmd.io/@jwang0306/final-project) * [XDEv11](https://hackmd.io/@XDEv11/sehttpd-project) * [eecheng87](https://hackmd.io/@eecheng/BJpGSJWq8) * [OscarShiang](https://hackmd.io/@oscarshiang/linux_sehttpd)