Linux 核心設計：事件驅動伺服器之原理和實例

--- tags: LINUX KERNEL --- # Linux 核心設計：事件驅動伺服器之原理和實例 > [The Evolution of Linux I/O Models: A Path towards IO_uring](https://docs.google.com/presentation/d/1CJiDAO6GbWwpeaeG-TMN751H8Bpq_nKQnnZE_yclFB4/edit?usp=sharing) / [錄影](https://youtu.be/Y0npaFZVKYo) ==[直播錄影](https://youtu.be/4ahU3xN5dMY)== 筆記：zoanana990 ## I/O Model 在討論伺服器前，應先理解 I/O Model，後者不僅會影響著應用程式的行為，更直接影響其 I/O 存取速度。本文介紹常見的 I/O Model，如 * Synchronous I/O * Blocking I/O * Non blocking I/o * I/O multiplexing * Asynchronous I/O > 不要被名詞迷惑，不一定 I/O 都是屬於這四類的其一，可以把它當一個指標，就是 I/O 可能偏向其中一個。 ### Blocking I/O (阻塞式 I/O) ![](https://i.imgur.com/cA7mJRl.png) - 當 User space 呼叫指令 read 的時候，會因為系統呼叫而進入kernel mode，此時作業系統會根據讀取的資料，可能是檔案系統、網路封包等等 ```c ssize_t read(int fildes, void *buf, size_t nbyte); /* [EAGAIN] The file was marked for non-blocking I/O, and no data were ready to be read. */ ``` - 進入 kernel space 後，會先讀取資料，再將資料傳回 buf 中。這裡有個細節，buf 的記憶體是儲存在 user space 的 - 當 kernel 在做事的時候 user 這邊在納涼，因此這種讀取方式稱為阻斷式，因為 user 沒有在動了 - 要記得注意返回值，有可能 Data 還沒準備好 ![](https://i.imgur.com/1RdeGBg.png) > [圖片來源](https://programmersought.com/article/56383199720/) 當行程在使用者層級呼叫 `read` 系統呼叫後，經過 mode transition，進入核心等待資料準備，當需要資料還沒抵達緩衝區 (buffer)，行程會持續待在核心空間。==從使用者層級的角度來說，就是 blocking 在一個系統呼叫，自然無法繼續執行程式==: ```cpp read(fd, buf, size); /* reach here until get "size" bytes data */ do_something(); ... ``` 由於 blocking (阻塞) 的特性，高效的網頁伺服器實作中，會避免只用此 I/O Model。 ### Non blocking I/O ![](https://i.imgur.com/2oTCzQ4.png) > [圖片來源](https://programmersought.com/article/56383199720/) 當行程呼叫 `read` 後，經過 mode transition，進入核心等待資料準備，若核心的資料尚未準備好，會馬上返回使用者模式的行程，避開阻塞。所以從使用者層級的角度來看，不再因資料尚未準備好，而阻塞於系統呼叫。可藉由 `fcntl` 系統改變 file descriptor 的屬性 (即 `O_NONBLOCK`)，通知核心 fd 應看作 non-blocking 來處理。實際案例可見高效伺服器的實作 [lwan](https://github.com/lpereira/lwan)，在 [lwan-readahead.c](https://github.com/lpereira/lwan/blob/f51cd6cc6f929107c283ec3dfda9bab431a14d87/src/lib/lwan-readahead.c#L120) 中前見運用 non-blocking IO 的實例: ```cpp while (true) { struct lwan_readahead_cmd cmd[16]; ssize_t n_bytes = read(readahead_pipe_fd[0], cmd, sizeof(cmd)); ssize_t cmds; if (UNLIKELY(n_bytes < 0)) { if (errno == EAGAIN || errno == EINTR) continue; lwan_status_perror("Ignoring error while reading from pipe (%d)", readahead_pipe_fd[0]); continue; #if PIPE_DIRECT_FLAG } else if (UNLIKELY(n_bytes % (ssize_t)sizeof(cmd[0]))) { lwan_status_warning("Ignoring readahead packet read of %zd bytes", n_bytes); continue; #endif } ``` 此時的 `read` 已設定為 non-blocking，因此即使資料尚未準備好，都會馬上返回。接著要判斷自核心返回使用者層級的原因，若只是單純資料沒準備好，收到的回傳值就是 `EAGAIN`，剩下的工作就是找機會再次呼叫 `read`。 ### I/O multiplexing ![](https://i.imgur.com/tCC9xqZ.png) > [圖片來源](https://programmersought.com/article/56383199720/) 簡單來說，I/O multiplexing 就是 [select](https://man7.org/linux/man-pages/man2/select.2.html) / [epoll](https://man7.org/linux/man-pages/man7/epoll.7.html) 的行為，雖說二者仍有差別 (`epoll` 有別於 `select`，沒有監聽數量的限制，且在找尋是透過紅黑樹，找尋的複雜度是 $O(logN)$，而 `select` 是 $O(N)$ )，但行為可歸納為一類。以 `epoll` 的例子來說，當行程呼叫 `epoll_wait` 後，經過 mode transition，開始核心監聽 (監聽的時間根據傳入的 `timeout` 決定)，時間到後切回使用者層級，回傳的數值代表剛監聽到的事件數量，根據數量來做對應的處理 (利用 callback)。 epoll 操作的架構很固定，大致如下: ```cpp nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1); ... for (n = 0; n < nfds; ++n) { if (events[n].data.fd == listen_sock) { /* do connection */ } else { /* do request */ do_use_fd(events[n].data.fd); } } ``` I/O multiplexing 的好處是，只用單一執行緒即可「同時處理」多個網路連接的 I/O，這裡的「同時處理」是巨觀，而非微觀表現。但只有單一執行緒的話，用 event-driven 來描述較恰當，也就是所謂的事件觸發，當有事件 (無論是 connection, reading requests 或 write requests) 來臨/完成，才做對應的處理，而不是一直卡在那裡等結果，浪費 CPU 資源。注意: `epoll_wait` 本質上還是 blocking 操作。 ### Asynchronous I/O ![](https://i.imgur.com/migkRtb.png) > [圖片來源](https://programmersought.com/article/56383199720/) 倘若 I/O multiplexing 已讓人拍案叫絕，==Asynchronous I/O 就更玄妙，可想像為 non-blocking I/O 的加強版：呼叫 `read` 後切換至核心空間時，此時**即使資料已就緒**，仍會馬上返回使用者層級，讓原本的程式碼得以繼續執行，而方才的工作留在核心，轉交其他核心執行緒 (kernel thread) 來完成。當完成後，核心會藉由 signal 等方式通知使用者模式的行程。== ```cpp aio_read(fd, buf, size); ----- // do read in background (kernel) /* return immediately */ | do_something_else(); | | wait_complete(); <----- ``` 這種模式乍聽之下的確無懈可擊，[POSIX asynchronous I/O (AIO)](https://man7.org/linux/man-pages/man7/aio.7.html) 也很早就納入 `POSIX.1` 規範，但 AIO 實作和應用上卻都有很大的挑戰，不論是 glibc POSIX AIO 甚至是 Linux native AIO。所以目前主流的高效伺服器通常都以 I/O multiplexing 為主。 > [非同步 I/O -- POSIX AIO 從入門到放棄](http://blog.litexavier.me/aio/posix_aio/2020/03/09/aio-01.html) ## Event-driven Server Event-driven 是種概念，沒有明確的科學定義，但要了解 event-driven 的行為不難，參考〈[如何向你阿嬤解釋 "Event-Driven" Web Servers](https://daverecycles.tumblr.com/post/3104767110/explain-event-driven-web-servers-to-your-grandma)〉: ### 傳統網頁伺服器想像有個 pizza 店，只雇用一個店員，當有客戶打電話進來訂餐時，店員收到訂單後不會掛斷電話，直到 pizza 做好後，店員通知客戶可以來拿後，再掛斷電話。這種模式很明顯的缺點是，在服務某客戶期間，無法接洽其他客戶，直接影響著用戶體驗 (latency) 與單位時間的服務量 (throughput)。 ### 事件驅動的網頁伺服器這個 pizza 店同樣只雇用一個店員，當有客戶打電話進來訂餐時，店員收到訂單後會馬上掛斷電話，然後等到 pizza 製作完畢，再打電話通知客戶可以來拿取。期間因為電話已掛斷，所以仍可持續收到更多的訂單。當然可請更多員工 (worker thread in thread pool) 在廚房烤 pizza 來增加單位時間的服務量 (throughput)。不過一旦員工數量持續增長，pizza 店的容量反而是限制 (capacity)。 ## 案例探討: [NGINX](https://nginx.org/) ### Design ![](https://i.imgur.com/bmoxV2k.png) > [圖片出處](https://www.nginx.com/blog/inside-nginx-how-we-designed-for-performance-scale/) NGINX 的組成為一個 Master 行程，負責做初始化相關的工作，例如組態設定, 建立 worker, 管理 worker (接收來自外界的 signal，向各 worker 發送 signal，監控 worker 的運行狀態)。至於 Worker 就是專門來處理客戶端的請求 (一般是網頁瀏覽器)，NGINX 的 worker 會對 CPU 設定 [affinity](https://linux.die.net/man/2/sched_getaffinity)，因此可降低 thread (worker) 間的 context switch 數量，抑制其引起效能低落的可能性。為了確保 worker 各自處理獨立的連線，worker 間會嘗試獲取 accept lock 來決定連線。每個 worker 使用 asynchronous & non-blocking 的方式，達到高並行程度的監聽事件(非處理事件，因為一個 worker 在一個時間最多只能處理一個事件)。 ### Event loop 每個採用事件驅動模型開發的網頁伺服器，大多會有一個主要的迴圈 (main loop，若有多個 worker 則有多個迴圈)，後者負責的工作，以核心空間 (涉及系統呼叫的內部行為) 來說，包含接收新的連線、接收請求、回應請求等等。以使用者層級來說，則包含封包過濾、內容壓縮等操作。 NGINX 針對 Linux 的實作中，worker 的 main loop 可參考 [ngx_epoll_module.c](https://github.com/nginx/nginx/blob/a64190933e06758d50eea926e6a55974645096fd/src/event/modules/ngx_epoll_module.c) 中的 `ngx_epoll_process_events`: ```cpp static ngx_int_t ngx_epoll_process_events(ngx_cycle_t *cycle, ngx_msec_t timer, ngx_uint_t flags) { ... events = epoll_wait(ep, event_list, (int) nevents, timer); ... for (i = 0; i < events; i++) { c = event_list[i].data.ptr; ... revents = event_list[i].events; ... if ((revents & EPOLLIN) && rev->active) { ... } wev = c->write; if ((revents & EPOLLOUT) && wev->active) { ... } } return NGX_OK; } ``` 可見到，雖然 NGINX 的 main loop 超過 200 行，但其骨架還是照著 `epoll` 常見的應用案例。先用 `epoll_wait` 監聽準備好的 events，再逐一處理。 ### 單一連線請求的流程 NGINX 完成一次連線請求的流程非常複雜，包含大量的使用者層級封包處理邏輯，本文不會細究。以下提供上至 main loop 內呼叫 `rev->handler` (連線請求)，下至底層系統呼叫 `sendfile` 的流程: * `ngx_http_wait_request_handler` $\to$ `ngx_http_process_request_line` * `ngx_http_process_request_line` $\to$ `ngx_http_process_request_headers` ... * `ngx_http_write_filter` $\to$ `c->send_chain` * `c->send_chain` === `ngx_send_chain` * `ngx_send_chain` === `ngx_io.send_chain` (`event/ngx_event.h`) * `ngx_io` === `ngx_os_io` (`event/modules/ngx_epoll_module.c`) * `ngx_os_io` === `ngx_linux_io` (`os/unix/ngx_linux_init.c`) * `static ngx_os_io_t ngx_linux_io = {..ngx_linux_sendfile_chain}` (`os/unix/ngx_linux_init.c`) * `sendfile64` [註1] filter module 由眾多 filters 組成，主要是負責對輸出的內容進行處理，可對輸出進行修改。所有的 filter 模組都被組織成一條 list，輸出會依次穿越所有的 filter。`ngx_http_write_filter` 為最後一個 filter，將最後過濾好的資訊傳送出去。 [註2] filter 的順序很重要，在編譯的時候就決定好，可見 [auto/modules](https://github.com/nginx/nginx/blob/a64190933e06758d50eea926e6a55974645096fd/auto/modules)。 [註3] 可透過 GDB 的命令 `catch syscall SYSCALL_NUMBER`, `set follow-fork-mode child`, `r`, 再 `where`，用以觀察 NGINX 處理請求的流程。 ### Thread pool #### 為何要有 thread pool? 依據《[NGINX Development guide](http://nginx.org/en/docs/dev/development_guide.html#threads)》 > Keep in mind that the threads interface is a helper for the existing asynchronous approach to processing client connections, and by no means intended as a replacement. 因為 Linux 本身沒有提供完整 AIO 介面 (但 FreeBSD 有)，因此沒辦法完整的使用 NGINX 的高度並行設計 (thread pool 支援)。但在 Linux 上的某些特殊情境仍有使用 thread pool 的好處，可參考 [Thread Pools in NGINX Boost Performance 9x!](https://www.nginx.com/blog/thread-pools-boost-performance-9x/)。說明在傳輸極大檔案時，可藉由透過 thread pool 來增加 throughput。 #### 機制 NGINX 實作 thread pool 的原理/流程: worker process 拿到任務後會把 task 丟到 thread pool，然後 worker process **就假設成功，接續處理下一個 task**。 #### 程式碼以下追蹤程式碼，應證上述總結: ```cpp ngx_linux_sendfile(ngx_connection_t *c, ngx_buf_t *file, size_t size) { ... #if (NGX_THREADS) if (file->file->thread_handler) { return ngx_linux_sendfile_thread(c, file, size); } #endif ``` 回到無 thread pool 的 NGINX 處理連線請求時，`sendfile` 的所在處 `ngx_linux_sendfile`，當設定 thread 版本 (by `--with-thread`) 即啟用 `NGX_THREADS`，所以真正負責任務的函式為 `ngx_linux_sendfile_thread`。 ```cpp static ssize_t ngx_linux_sendfile_thread(ngx_connection_t *c, ngx_buf_t *file, size_t size) { ... task = c->sendfile_task; if (task == NULL) { task = ngx_thread_task_alloc(c->pool, sizeof(ngx_linux_sendfile_ctx_t)); if (task == NULL) { return NGX_ERROR; } task->handler = ngx_linux_sendfile_thread_handler; c->sendfile_task = task; } ... if (file->file->thread_handler(task, file->file) != NGX_OK) { return NGX_ERROR; } return NGX_DONE; } ``` 這裡有三件事需要注意: 1. `task->handler` 是用來記錄稍後 thread 需要做的工作內容，因此這裡很明顯，給 thread 做的事為 `ngx_linux_sendfile_thread_handler` 2. `file->thread_handler` 負責把至此設定好的 task meta data (如 handler 等...) 置入 thread pool (藉由 `ngx_thread_task_post`) 3. 最後直接回傳 `NGX_DONE`，事實上任務可能尚未執行完畢。延續 (1): ```cpp static void ngx_linux_sendfile_thread_handler(void *data, ngx_log_t *log) { ... file = ctx->file; offset = file->file_pos; again: n = sendfile(ctx->socket, file->file->fd, &offset, ctx->size); if (n == -1) { ctx->err = ngx_errno; } else { ctx->sent = n; ctx->err = 0; } ... if (ctx->err == NGX_EINTR) { goto again; } } ``` thread 真正做的任務為 `ngx_linux_sendfile_thread_handler`，此 handler 就是負責 `sendfile` 並試到其成功為止。而此 handler 真正被呼叫的地方在 thread 的 loop 中: ```cpp static void * ngx_thread_pool_cycle(void *data) { ... for ( ;; ) { ... task->handler(task->ctx, tp->log); ... } ``` `ngx_thread_pool_cycle` 基本上就是 consumer，負責: 1. 上鎖後搶任務 2. 執行任務 3. 把任務置入 finish list 4. notify。舉 `epoll` 系列來說，notify 的實作存於 `ngx_epoll_module_ctx` 中的成員 `ngx_epoll_notify`。 ```cpp static void ngx_epoll_notify_handler(ngx_event_t *ev) { ... n = read(notify_fd, &count, sizeof(uint64_t)); ``` notify_handler 的 `read` 會觸發 `EPOLLIN` 信號。因為已將 `notify_fd` 透過 `epoll_ctl` (於 `ngx_epoll_notify_init`) 加入 `ep` 作為感興趣的執行案例 (instance)，所以可由 `ep` (`epoll` file descriptor) 感知 (透過 `ngx_epoll_process_events` 中的 `epoll_wait`)。延續 (2): `thread_handler` 可能指向 `ngx_http_cache_thread_handler`, `ngx_http_upstream_thread_handler` 等等，但函式內都含 `ngx_thread_task_post`，負責把任務移到丟到 queue 上。 #### Thread pool 與 epoll loop 的關係統整上述討論和程式碼行為，展示如下圖: ![](https://i.imgur.com/sc1t6aS.png) 補充一些細節: 1. 在 epoll_module 內會初始化與 notify 的資料，包含: * 建立 `notify_fd` 供 epoll loop 與 thread 間溝通 * 設定 `notify_event` 並加入 `epoll` interested list (藉由 `epoll_ctl`) 2. 當有 notify 事件產生 (`ngx_epoll_notify` 產生的 `EPOLLIN` 訊號)，`epoll_wait` 收到後，擷取 event 內的處理函式 (`rev->handler`)。此 handler 即 `ngx_epoll_notify_handler`，於 `epoll_notify_init` 內設定的。 3. `ngx_epoll_notify_handler` 是會在 epoll main loop 中呼叫，其內容包含: * `read`: 銜接 thread 中 `ngx_notify` 產生的 `write` * 呼叫 handler，此 handler 為呼叫 `ngx_notify` 的參數，舉例來說: `ngx_thread_poll_handler` # 高效 Web 伺服器開發 :::info 本文探討 ==[seHTTPd](https://github.com/sysprog21/sehttpd)== 的設計和實作議題，涵蓋並行處理、I/O 模型、epoll、React pattern，和 Web 伺服器在事件驅動架構的考量。 ::: > 資料整理: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) ## TCP 伺服器的實作挑戰一般來說，TCP 伺服器的流程是先 [listen](http://man7.org/linux/man-pages/man2/listen.2.html) 於某個 port，呼叫 [accept](http://man7.org/linux/man-pages/man2/accept.2.html) 等待客戶端的連線，等客戶端連線後會返回一個 fd (file descriptor)，自指定 fd 進行 [read](http://man7.org/linux/man-pages/man2/read.2.html)，以 TCP echo 來說，對應的處置方式即 [write](http://man7.org/linux/man-pages/man2/read.2.html) 同樣的資料到該 fd，然後重新 [accept](http://man7.org/linux/man-pages/man2/accept.2.html)，關鍵程式碼如下: ```cpp /* Enter an infinite loop to respond to client requests */ while (1) { /* Wait for a connection, then accept() it */ if ((conn_s = accept(list_s, NULL, NULL)) < 0) exit(EXIT_FAILURE); /* Retrieve an input line from the connected socket */ for (size_t n = 1; n < MAX_LINE - 1; n++) { ssize_t rc; char c; if ((rc = read(conn_s, &c, 1)) == 1) { *buffer++ = c; if (c == '\n') break; } else if (rc == 0) break; else { if (errno == EINTR) continue; break; } } *buffer = 0; /* simply write it back to the same socket */ size_t nleft = strlen(buffer); while (nleft > 0) { ssize_t nwritten; if ((nwritten = write(conn_s, buffer, nleft)) <= 0) { if (errno == EINTR) nwritten = 0; break; } nleft -= nwritten; buffer += nwritten; } /* Close the connected socket */ if (close(conn_s) < 0) exit(EXIT_FAILURE); } ``` > 完整程式碼可見 [echoserv](http://www.paulgriffiths.net/program/c/srcs/echoservsrc.html) 理解這個 echo 伺服器後，即可在其上擴展為 web 伺服器 —— HTTP 建構於 TCP 之上，會有通訊協定的解析和處理。[CS:APP](https://hackmd.io/@sysprog/CSAPP) 提供 [tiny.c](http://csapp.cs.cmu.edu/public/ics2/code/netp/tiny/tiny.c) 來服務靜態和動態內容，儘管效益不彰，但已達到教學的目的。雖然這個程式能正常工作，但它無法勝任廣泛的應用，原因是伺服器在處理一個客戶端請求時，無法受理別的客戶端請求，也就是說，這個程式無法同時滿足兩個想獲得 echo 服務的使用者，這自然是極大的限制。其中一項改進的解決方案：[accept](http://man7.org/linux/man-pages/man2/accept.2.html) 之後再進行 [fork](http://man7.org/linux/man-pages/man2/fork.2.html)，父行程 (parent process) 繼續 [accept](http://man7.org/linux/man-pages/man2/accept.2.html)，子行程 (child process) 則處理該 fd，對應的程式碼如下: ```cpp int guard(int n, char *err) { if (n == -1) { perror(err); exit(1); } return n; } int main(void) { int listen_fd = guard(socket(PF_INET, SOCK_STREAM, 0), "Could not create TCP socket"); guard(listen(listen_fd, 100), "Could not listen on TCP socket"); struct sockaddr_in listen_addr; socklen_t addr_len = sizeof(listen_addr); guard(getsockname(listen_fd, (struct sockaddr *) &listen_addr, &addr_len), "Could not get socket name"); for (;;) { int conn_fd = accept(listen_fd, NULL, NULL); if (guard(fork(), "Could not fork") == 0) { char buf[100]; for (;;) { ssize_t nreceived = guard(recv(conn_fd, buf, sizeof(buf), 0), "Could not recv on TCP connection"); if (nreceived == 0) { guard(shutdown(conn_fd, SHUT_WR), "Could not shutdown TCP connection"); guard(close(conn_fd), "Could not close TCP connection"); exit(0); } guard(send(conn_fd, buf, nreceived, 0), "Could not send to TCP connection"); } } else { /* Child takes over connection; close it in parent */ close(conn_fd); } } return 0; } ``` > [完整程式碼](https://jameshfisher.com/2017/02/25/tcp-server-fork/) 乍看這個程式解決上述只能服務單一客戶端請求的問題，但基於以下幾個因素，仍無法滿足效能需求: * 每個網路連線都涉及 [fork](http://man7.org/linux/man-pages/man2/fork.2.html)，開銷大：定址空間是 copy-on-write (CoW)，因此初期開銷不大，但仍有複製父行程 page table 的操作，而執行緒卻可分享同一個 page table。 * 行程間的排程器承受的壓力大：考慮到系統因大量連線而有成千上萬個行程，排程器勢必要耗費時間於挑選出下一個欲執行的行程，及進行 context switch，整體開銷可觀，可參見《[A Design Framework for Highly Concurrent Systems](https://people.eecs.berkeley.edu/~culler/papers/events.pdf)》的分析。 * 在負載沈重的狀況下，行程易於消耗大量的記憶體資源：每個網路連線對應一個獨立的定址空間，即使在執行緒的狀況下，每個連線也會佔用資源。此外，[fork](http://man7.org/linux/man-pages/man2/fork.2.html) 後 parent-child 行程之間需要 IPC，這也是成本。改用執行緒雖可克服 [fork](http://man7.org/linux/man-pages/man2/fork.2.html) 開銷的問題，但排程器和記憶體開銷仍無法解決。單純行程和執行緒的模型在本質相似，被歸類於 process-per-connection model，無法滿足高並行 (concurrency) 需求。可引入 [thread pool](https://en.wikipedia.org/wiki/Thread_pool)：事先建立數量固定的執行緒，依據需求分配任務到這些執行緒，免去 TCP 伺服器在服務客戶端請求時，需要重新建立執行緒的疑慮。引入 [thread pool](https://en.wikipedia.org/wiki/Thread_pool) 後，TCP 伺服器的基本架構是，主要的循環 (main loop) 用 [accept](http://man7.org/linux/man-pages/man2/accept.2.html) 網路連線，之後將該連線分配給 [thread pool](https://en.wikipedia.org/wiki/Thread_pool) 的某個執行緒，處理後這個執行緒又可處理別的網路連線。 > 延伸閱讀: [圖解 Go 執行時期排程器](https://tonybai.com/2020/03/21/illustrated-tales-of-go-runtime-scheduler/) ![](https://i.imgur.com/bhsp5jC.png) 乍看 [thread pool](https://en.wikipedia.org/wiki/Thread_pool) 是個理想的方案，但在真實情況中，很多連線都要長時間處理 (longer keep alive time，即在一個 TCP 連線中進行多次通訊)，一個執行緒收到任務後，處理完第一批來的資料，此時會再次呼叫 [read](http://man7.org/linux/man-pages/man2/read.2.html)，但卻無法確認對方何時發送新資料，於是該執行緒就被這個 [read](http://man7.org/linux/man-pages/man2/read.2.html) 給阻塞 (blocked) 住了，這也是預設 I/O 操作的模式 —— 即便該 fd 沒有任何資料，呼叫 [read](http://man7.org/linux/man-pages/man2/read.2.html) 仍會致使行程的 blocking。於是，在 [thread pool](https://en.wikipedia.org/wiki/Thread_pool) 上若有 $n$ 個執行緒，只要遇上第 $n + 1$ 個長時間的連線，系統仍無法滿足並行需求。不難發現問題的根源是 [read](http://man7.org/linux/man-pages/man2/read.2.html) 預設行為致使的 blocking，解法是將後者該換為 non-blocking I/O。[read](http://man7.org/linux/man-pages/man2/read.2.html) 的做法是若有資料則返回資料，如果沒有可讀資料就返回 `-1` 並設定 errno 為 `EAGAIN`，後者表明下次有資料再繼續處理。 > `EAGAIN` The file descriptor fd refers to a file other than a socket and has been marked nonblocking (`O_NONBLOCK`), and the read would block. See [open(2)](http://man7.org/linux/man-pages/man2/open.2.html) for further details on the `O_NONBLOCK` flag. 很快我們發現新問題：行程如何得知這個 fd 在何時有資料可讀取呢？這就要透過事件驅動 (event-driven) 模型來克服。 ## I/O 事件模型探討 I/O 事件模型前，我們應當理解雙工 ([duplex](https://en.wikipedia.org/wiki/Duplex_(telecommunications))) 的概念，亦即二台通訊裝置之間如何進行雙向的資料傳輸，可區分為: * 半雙工 (half-duplex): 允許二台裝置之間的雙向資料傳輸，但不能同時進行 * 因此同一時間只允許一裝置傳送資料，若另一裝置要傳送資料，需等原來傳送資料的裝置傳送完成後再處理 ![](https://i.imgur.com/wINA9fs.png) * 無線對講機就是使用半雙工系統。由於對講機傳送及接收使用相同的頻率，不允許同時進行。因此一方講完後，需設法告知另一方講話結束（例如講完後加上 "OVER"），另一方才知道可開始講話 * 全雙工 (full-duplex): 允許二台裝置間==同時==進行雙向資料傳輸 ![](https://i.imgur.com/zwwAUWs.png) * 一般的電話和手機屬於全雙工的系統，講話時同時也可聽到對方的聲音 ![](https://i.imgur.com/JQJg9iq.png) 1969 年 UNIX 剛被創造時，其 shell/tty 是不折不扣的半雙工 I/O: 對終端機進行寫入和讀取，不可同時進行，這並非不合理的限制，畢竟當時的作業系統的使用者 (且為專業人士) 主要對電腦下命令: * 使用者發出命令: 寫入資料到 file descriptor * 機器回傳執行結果: 自 file descriptor 讀取資料換句話說，機器不能在使用者輸入命令前，提前輸出結果，這樣只要半雙工即可。但考慮另一個情境，由接線生負責操作多電話線的插線接通，依據發話端的要求將電話線接到其他線路，從而達成電話中繼 (relay): * 接線生監聽 N 個終端機：監聽終端機 * 接線生聽某個終端：自終端機讀取 * 接線生把聽到的話傳給另一個終端機：寫入資料到終端機依據 UNIX 檔案操作的特性，若一個 file descriptor (以下簡稱 `fd`) 表示的檔案沒有資料可讀取，那麼讀取檔案的操作將會 blocked (阻塞)，傳話中繼接線生就不知道 N 個終端機裡頭到底有哪個終端機可讀取，於是乎，任意讀取一個終端機就會造成行程的阻塞。假設終端機編號 `1` 的資料在 2 分鐘後才會到來，中繼接線生不巧讓行程去讀終端機編號 `1`，這會造成終端機編號 `1` 阻塞 2 分鐘。10 秒後，終端機編號 2 的資料到來，，然而此時行程已阻塞在終端機編號 `1`，只能興嘆！若要克服這窘境，中繼接線生需要一個指示： > 「告訴我哪個終端機有資料可讀！」 [4.2BSD](https://en.wikipedia.org/wiki/Berkeley_Software_Distribution) 提供 [select](https://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫，恰到好處地解決問題：檢查所有 N 個終端機，回傳有資料可讀的終端機列表。若無任何終端機有資料可讀，[select](https://man7.org/linux/man-pages/man2/select.2.html) 將會阻塞，反之，只要有任何終端機有資料可讀，[select](https://man7.org/linux/man-pages/man2/select.2.html) 就會返回原本的程式。於是，[select](https://man7.org/linux/man-pages/man2/select.2.html) 成為全雙工的 fd 操作，並鞏固 UNIX 設計哲學 "Everything is a file"，這也是為何單一行程可服務多個網連線，因為透過 [select](https://man7.org/linux/man-pages/man2/select.2.html) 可得知哪一組資料可處理。 ![](https://i.imgur.com/uXPFiNs.png) > blocking I/O ![](https://i.imgur.com/c77Sx0q.png) > I/O Multiplexing > source: [I/O Multiplexing](http://www.cs.toronto.edu/~krueger/csc209h/f05/lectures/Week11-Select.pdf) - Blocking / Non-blocking I/O：在等待 I/O 資料**準備就緒** (e.g. **有資料可以讀取**) 的過程，使用者層級的行程是否會被 **blocked**。 - Blocking I/O：在等待 I/O 資料準備就緒的過程，使用者層級的行程會被 blocked。 - e.g. 未設定 **O_NONBLOCK** 的 [read](http://man7.org/linux/man-pages/man2/read.2.html), [select](http://man7.org/linux/man-pages/man2/select.2.html), [epoll](http://man7.org/linux/man-pages/man7/epoll.7.html) - Non-blocking I/O：在向核心詢問是否可進行 I/O 操作的過程，不論 I/O 資料是否準備就緒，使用者層級的行程都不會被 blocked。若 I/O 資料尚未準備就緒 (e.g. 尚無資料可讀取)，則會直接返回，並設定 `errno` 指明錯誤 (e.g. `EAGAIN`、`EWOULDBLOCK`)。使用者層級的行程必須重複詢問 (e.g. 在 `while` 迴圈中重複呼叫 [read](http://man7.org/linux/man-pages/man2/read.2.html)) 直到 I/O 資料準備就緒才可進行 I/O operation。 - e.g. 設定 **O_NONBLOCK** 的 [read](http://man7.org/linux/man-pages/man2/read.2.html), `aio_read()`, `aio_write()` - Synchronous / Asynchronous I/O：在從/向核心空間讀取/寫入資料 (i.e. **實際進行 I/O 操作**) 的過程，使用者層級的行程是否會被 **blocked**。 - Synchronous I/O：從/向核心空間讀取/寫入資料的過程，使用者層級的行程會被 blocked - e.g. [read](http://man7.org/linux/man-pages/man2/read.2.html), [recvfrom](http://man7.org/linux/man-pages/man2/recv.2.html) - Asynchronous I/O：從/向核心空間讀取/寫入的過程交由核心內部處理。核心複製完資料後，再通知使用者層級的行程。這中間使用者層級的行程不會被 blocked。 - e.g. `aio_read()`, `aio_write()` 延伸閱讀: [I/O Models 中文解說](https://rickhw.github.io/2019/02/27/ComputerScience/IO-Models/) ### I/O Multiplexing ```cpp int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); ``` [select](http://man7.org/linux/man-pages/man2/select.2.html) 搭配 [read](http://man7.org/linux/man-pages/man2/read.2.html) 可實作出 I/O multiplexing 機制，而 I/O multiplexing 其實是 Blocking I/O 的延伸，但 `select()` + `read()` 相較單一 [read](http://man7.org/linux/man-pages/man2/read.2.html) 的優勢是 `select()` 可同時等待多個 `file descriptors` (`fd`)。若 I/O multiplexing 要處理的連線數量過少，可能會因內部處理較複雜，致使更高的延遲。在 4.2BSD 提出 select 系統呼叫時，I/O multiplexing 並非著眼於提高單一連線的速度，而是可在只使用單一行程或執行緒狀況下，監視或處理更多的連線。呼叫 `select()` 時所傳入的是多個 `fd set`，而非只是一個 `fd`。只要 `fd set` 中任一個以上的 `fd` 的 I/O 資料準備就緒，`select()` 就會返回。呼叫 `select()` 的行程必須走訪 `fd set` 來檢查是哪幾個 `fd` 可以進行 I/O 操作，爾後再呼叫 `read()`、`recvfrom()` 讀取資料。此時 I/O 資料應準備就緒，可直接讀取。但也有例外，e.g. `select()` man page 所述： > Under Linux, select() may report a socket file descriptor as "ready for reading", while nevertheless a subsequent read blocks. This could for example happen when data has arrived but upon examination has wrong checksum and is discarded. There may be other circumstances in which a file descriptor is spuriously reported as ready. Thus it may be safer to use O_NONBLOCK on sockets that should not block. `select()` 後的 `read()`、`recvfrom()` 是 Blocking I/O 或是 Non-blocking I/O，取決於設定 **O_NONBLOCK** 與否。將 **read()** 或 **recvfrom()** 設為 **NON_BLOCKING** 才可避免使用者層級的行程再次被 blocked。由於 `select()` 最多只可同時監控 (watch) `1024` 個 `fd`，且當返回時，使用者層級仍要走訪整個 `fd set`，才可知道是哪些 `fd` 的資料已準備好，存在性能疑慮，因此才有後續的 `epoll()`。 ### epoll 系列系統呼叫關於 `epoll` 系列 API (注意: epoll 不是單一 Linux 系統呼叫)，可參見 [The method to epoll’s madness](https://medium.com/@copyconstruct/the-method-to-epolls-madness-d9d2d6378642) 一文說明。 > select/poll 的時間複雜度是 $O(n)$，而 epoll 的時間複雜度是 $O(1)$ ```cpp int epoll_create(int size); ``` [epoll_create](http://man7.org/linux/man-pages/man2/epoll_create.2.html) 系統呼叫回傳指向在 Linux 核心新建的 epoll 資料結構對應的 fd，使用該系統呼叫的行程可透過該 fd，進行新增、刪除，和變更其他的想要監視的 fd。自 Linux `v2.6.8` 起，該系統呼叫的參數已被忽視，但考量到相容性，該參數仍要大於 `0`。 ![](https://i.imgur.com/sHHIdRk.png) 摘自 man page: > In the initial epoll_create() implementation, the size argument informed the kernel of the number of file descriptors that the caller expected to add to the epoll instance. The kernel used this information as a hint for the amount of space to initially allocate in internal data structures describing events. (If necessary, the kernel would allocate more space if the caller's usage exceeded the hint given in size.) Nowadays, this hint is no longer required (the kernel dynamically sizes the required data structures without needing the hint), but size must still be greater than zero, in order to ensure backward compatibility when new epoll applications are run on older kernels. ```cpp int epoll_create1(int flags); ``` [epoll_create1](http://man7.org/linux/man-pages/man2/epoll_create.2.html) 系統呼叫的參數: * `0`: 表現如同 [epoll_create](http://man7.org/linux/man-pages/man2/epoll_create.2.html) * `EPOLL_CLOEXEC`: 透過 fork 自現有行程分出的子行程，將在行程執行前，關閉 epoll fd，換言之，子行程無法存取父行程設定的 epoll 資源。 ```cpp int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); ``` [epoll_ctl](http://man7.org/linux/man-pages/man2/epoll_ctl.2.html) ![](https://i.imgur.com/wnI4Gsp.png) > All the file descriptors registered with an epoll instance are collectively called an epoll set or the interest list. ready list 是 interest list 的子集合: ![](https://i.imgur.com/AY4LioQ.png) 下述三種操作: * Add/Register fd with the epoll instance (EPOLL_CTL_ADD) and get notified about events that occur on fd * Delete/deregister fd from the epoll instance. This would mean that the process would no longer get any notifications about events on that file descriptor (EPOLL_CTL_DEL). If a file descriptor has been added to multiple epoll instances, then closing it will remove it from all of the epoll interest lists to which it was added. * Modify the events fd is monitoring (EPOLL_CTL_MOD) ![](https://i.imgur.com/E8EWgJ4.png) ## Reactor Pattern 同步的事件循環搭配 non-blocking I/O 又稱為 [Reactor pattern](http://en.wikipedia.org/wiki/Reactor_pattern)。 ![](https://i.imgur.com/tmGVoO1.jpg) 事件循環用來通知特定事件，若 listenfd 可讀取，則呼叫 [accept](http://man7.org/linux/man-pages/man2/accept.2.html)，把新建立的 fd 加入 epoll 中；若是普通的連線 fd，將其加入到一個生產者與消費者佇列中，讓 worker thread 取用。thread pool 用來做計算，從一個生產者與消費者佇列裡領取一個 fd 作為計算輸入，直到讀到 `EAGAIN` 為止，保存現在的處理狀態（狀態機），等待事件循環，直到這個 fd 讀寫事件的下一次通知。 [Reactor pattern](http://en.wikipedia.org/wiki/Reactor_pattern) 是個設計模式 (design pattern)，針對同時處理多個或單個服務需求。服務處理任務 (service handler) 將傳入的需求拆解，然後分派給相關的請求端處理任務 (request handler)。再來思考為何需要 [Reactor pattern](http://en.wikipedia.org/wiki/Reactor_pattern)。考慮這樣的情境：web 應用程式收到請求，處理過後接著要讀取資料或是將資料寫入到資料庫，中間勢必要等待其他功能模組或程式進行，延遲的時間可能數十毫秒或更長，但原本的 web 應用程式就處於等待的狀態，也就是不做事情，但 CPU 佔用率仍居高不下，因為行程處理資料庫的存取、檔案的 I/O 或者是跟其他服務的**溝通之間的等待**都存在可觀成本。在 Reactor Pattern 中有個單執行緒的事件循環 (event loop)，不停地循環等待新事件的發生，事件處理的過程中如有Blocking I/O 的產生，會使用 **defer** 手段，將動作轉包到事件循環以外的其他執行緒，從而讓等待資料庫讀取的狀況發生在另外一個執行緒，這樣的好處很明顯 —— 主要的事件循環不會發生 blocking，並可繼續服務下一個事件，等待資料庫讀取完畢、資料回傳後，再透過預先設定的 callback，將資料傳回主要事件循環中，自此繼續受理各項請求。 ## Edge vs. Level Triggering select 和 poll 屬於 level-triggered Asynchronous I/O 則傾向 edge-triggered. `epoll` 的兩種工作模式談起: 1. Edge Triggered (ET, 邊緣觸發) 2. Level Triggered (LT, 條件觸發) ![](https://i.imgur.com/U5MvTC2.png) ET 表示在狀態改變時才通知（例如: 在邊緣上從低電位到高電位），LT 表示在這個狀態才通知（例如: 只要處於低電位就通知)。對應到 epoll，ET 指一旦有新資料就通知（狀態的改變），而 LT 是「只要有新資料」就會持續通知，直到緩衝區的資料全數取出。 ## 實作考量點 :question: 若將 fd 放入生產者與消費者佇列後，拿到這個任務的 worker thread 尚未讀完這個 fd，因為沒讀取完資料，所以這個 fd 可讀，那麼下一次事件循環又返回這個 fd，還分配給其他的執行緒，該如何處理？ :thinking_face: 若某 fd 對應到 2 KiB 的資料，程式只讀取 1 KiB，ET 就不會在下次 `epoll_wait` 時返回，而是會在讀取結束後又有新資料之際才回傳。而 LT 每次都會回傳該 fd，只要該 fd 有資料可讀。所以我們要用 epoll 的 ET，把 fd 設為 `O_NONBLOCK`，如果返回某 fd 可讀，循環 read 直到 `EAGAIN`（若 read 回傳 `0`，則遠端關閉連線）。 > 實驗程式碼: [test_epoll_lt_and_et](https://github.com/Manistein/test_epoll_lt_and_et) :question: 如果某個執行緒在處理 fd 的同時，又有新的一批資料進來，該 fd 可讀（注意和上一題的區別：一個是處理同一批資料，另一個是處理新一批資料），那麼該 fd 會被分配另一個執行緒，這樣兩個執行緒處理同一個 fd 就會導致錯亂。 :thinking_face: 設定 `EPOLLONESHOT` 可解決這個問題。在 fd 回傳可讀後，需要另行設定，才能讓 epoll 重新回傳這個 fd。 :question: 當 Web 伺服器和客戶端網頁瀏覽器保持著一個長期連線的狀況下，遇到 (1) 網頁瀏覽器突然關閉; (2) 客戶端網路離線; 這兩種狀況，伺服器該如何處理？ :thinking_face: 分兩種狀況處理: 1. 此時該 fd 在事件循環裡會回傳一個可讀事件，然後分配給某個執行緒，該執行緒 read 會回傳 `0`，代表對方已關閉這個 fd，於是伺服器端呼叫 close 即可; 2. 通訊協定無法立刻知悉，所以僅能透過伺服器引入 timer 逾時事件來克服 timer 可透過 priority queue 實作，後者又常用 binary heap 實作，可參見以下: * [Priority Queue 簡介](https://alrightchiu.github.io/SecondRound/priority-queueintrojian-jie.html) * [Priority Queue：Binary Heap](https://alrightchiu.github.io/SecondRound/priority-queuebinary-heap.html) :question: 將 fd 設定為 non-blocking 後，需要不斷地 read 直到回傳 `-1`，errno 為 EAGAIN，然後等待下次 epoll_wait 回傳這個 fd 再繼續處理。這時就遇到了 blocking read 不曾遇到的問題：資料可能分批送達，於是在通訊協定解析到一半時，read 就回傳 `-1`，所以我們必須將已讀到的資料保存下來，並維護其狀態，以表示是否仍需要資料。例如解析 HTTP Request Header 時，讀到 `GET /index.html HTT` (注意：少一個 `P`) 就結束，在 blocking I/O 裡只要繼續 read 就可處理，但在 nonblocking I/O，我們必須維護這個狀態，下一次必須讀到欠缺的 `P` 字元，否則 HTTP 通訊協定會遇上解析錯誤。 :thinking_face: 解法是維護一個狀態機，在解析 Request Header 時候對應一個狀態機，解析 Header Body 的時候也維護一個狀態機。 ## 參考資訊 * [Concurrent HTTP Server with Epoll](https://kaleid-liner.github.io/blog/2019/06/02/epoll-web-server.html) * [fancy: A high performance web server](https://github.com/guangqianpeng/fancy) * [poll vs select vs event-based](https://daniel.haxx.se/docs/poll-vs-select.html) * [Async IO on Linux: select, poll, and epoll](https://jvns.ca/blog/2017/06/03/async-io-on-linux--select--poll--and-epoll/) * [Fast UNIX Servers](https://nick-black.com/dankwiki/index.php/Fast_UNIX_Servers) * [Concurrent Servers](https://eli.thegreenplace.net/2017/concurrent-servers-part-1-introduction/) # 以 sendfile 和 splice 系統呼叫達到 Zero-Copy ## 特殊系統呼叫的定位在 [in-kernel HTTP server](https://hackmd.io/@sysprog/kernel-web-server) 中，提到: 1. Linux 核心差一點就走進 Microsoft Windows 的「為需求而升級」的發展道路，從而偏離原先 Linux 核心「只提供機制不提供策略」的道路 * Linus Torvalds 在 2001 年 10 月說過： > "From a technical standpoint,I believe the kernel will be"more of the same" and that all the _really_interesting stuff will be going out in user space." 2. Linux 2.4 時代，核心提供一個名為 khttpd 的核心內部的 web 伺服器 (in-kernel httpd)。當時 Linux 的效能不夠好，且無法有效利用 SMP 的優勢、thread 的實現還是很拙劣 (不是 NPTL)，很多方面沒有達到 POSIX 的性能期待，因此當時的開發者就鑽進瞭解決性能瓶頸的牛角尖上 3. 有鑑於 Apache 伺服器多半在 Linux 上運作，且 web 伺服器是如此普遍也重要，因此效能瓶頸往往是 Apache 本身，因此面對這個如此「特化」又不得不理會的需求，開發者們只好就事論事地將 web 伺服器單獨加速，也就是在核心內部中實做一個 web 加速器 * 如果按照這條路走下去，Linux 或許還會把圖形處理搬到核心內部，一如 Windows NT 所為 * 自 Windows NT 以來，為了效率考量，字型處理 (font engine) 是實作於核心內部 (!)，因此也招來 [CVE-2015-3052](https://vulners.com/cve/CVE-2015-3052) (BLEND vulnerability) 的安全漏洞，從而影響到[核心模式](https://googleprojectzero.blogspot.com/2015/08/one-font-vulnerability-to-rule-them-all.html) 4. 不過 Linux 2.6 以來，核心發展重新找到自己的方向，沒必要透過特化需求去克服局部的效能瓶頸 5. Linux-2.6 核心的發展策略是基於整體思維，像是新的排程演算法 (O(1) scheduler 和後續的 CFS)，又像是 linux-2.6.17 中的 [splice](http://man7.org/linux/man-pages/man2/splice.2.html) 和 [tee](http://man7.org/linux/man-pages/man2/tee.2.html) 系統呼叫，都讓 khttpd 沒有存在的必要 ## sendfile 系統呼叫 khttpd 這樣的實作可讓 Linux 核心成為提供讀取靜態網站頁面的服務，減少核心和使用者層級之間的 context switch 和資料複製。 Linux 應用程式在讀取和傳送網路資料的流程，簡化為以下 (K 表示核心， U 表示使用者層級): * U: open() * K: do_sys_open() * K: do_filp_open() - 找到檔案，並從所在的檔案系統取得 struct file * K: 回傳檔案物件 * U: malloc() - 準備記憶體空間作為 buffer * U: read(file, buffer) * K: vfs_read(file) - 標準 VFS 的檔案讀取操作 * K: `file->f_op->read()` - 透過資料所在的檔案系統，使用提供的低階 read 操作 * K: copy_to_user(buffer) - 將檔案資料從實體儲存裝置讀出來後，複製一份到使用者層級的 buffer 接著是將讀到的資料透過網路傳送出去： * U: write(Socket, buffer) - 將 buffer 內資料傳送出去 * K: copy_from_user(buffer) - 將使用者層級的 buffer 複製回去核心空間 * K: Send data - 傳送資料 Linux 核心提供 [sendfile](http://man7.org/linux/man-pages/man2/sendfile.2.html) 系統呼叫 (註: BSD 家族也有作業系統提供 `sendfile`，但是語意有出入)，於是我們只要指定 socket file description 和將要送出去的檔案給 sendfile，後者即可在核心模式中，將檔案自儲存裝置讀取複製出來，不再經過任何多餘核心和使用者層級的資料複製，直接從指定的裝置輸出。以下逐步探討個別系統呼叫的行為。舉例來說，伺服器讀取一個檔案，然後把檔案資料經由 socket 將資料傳送給客戶端。程式碼包含以下: ```cpp read(file, tmp_buf, len); write(socket, tmp_buf, len); ``` 流程示意: ![](https://i.imgur.com/1RoFRKx.png) * 步驟 `1` 到 `2`: 當執行 read 函式 (由 glibc 或相似的 libc 提供) 後，read 系統呼叫被觸發，檔案資料會經由 DMA 傳遞於核心模式內的 buffer，然後再由 CPU 將檔案資料搬到使用者層級的 buffer (tmp_buf) 中。 * 步驟 `3` 到 `4`: 執行 write 函式後，write 系統呼叫被觸發，藉由 CPU 將使用者層級的 buffer 的資料搬到 socket buffer 裡頭，資料傳遞到 socket buffer 後，會再經由 DMA，將資料送出去給客戶端。 * 合計 4 次資料複製討論: * 整個流程中不難發現資料是重覆複製，在資料量增大時，會對效能產生衝擊。若能把這些部份改掉，那就可減少記憶體的消耗並增加效能。 * 以硬體的角度來看，透過記憶體進行資料暫存的操作其實可省去，直接將檔案資料傳遞到網路裝置 —— 但並非所有的硬體都支援。是否可減少使用者層級 buffer 的操作呢？可以，例如透過 [mmap](http://man7.org/linux/man-pages/man2/mmap.2.html) 來取代 read: ```cpp tmp_buf = mmap(file, len); write(socket, tmp_buf, len); ``` 流程示意: ![](https://i.imgur.com/9madsOS.png) * 步驟 `1` 到 `2`: mmap 執行後，一如上述 read 系統呼叫，將檔案資料經由 DMA 複製一份到核心模式的 buffer，但不同的是，read 需要將核心 buffer 複製到使用者層級的 buffer，mmap 卻不會，因為 mmap 的使用者 buffer 和核心模式的 buffer 共享同一塊硬體分頁 (page)，因此 mmap 可減少一次 CPU copy。 * 步驟 `3` 到 `4`: write 執行後，把核心模式的 buffer 經由 CPU 複製到 socket buffer，再經由 DMA 傳輸到客戶端。 * 合計 3 次資料複製討論: * 使用 mmap 會付出可觀的成本，一是來自虛擬記憶體管理 (VMM) 的代價，另一是同步議題 * 存取小檔案時，直接用 read() 或 write() 更有效率 * 單個行程對檔案進行循序存取 (sequential access) 時，用 mmap()幾乎不會有任何效能提升 (甚至有反效果)。反過來說，用 read 循序讀取檔案時，檔案系統會使用 read-ahead 的方式，提前將檔案內容快取到檔案系統的緩衝區，因此使用 read() 可提升 cache hit。 * 當使用 mmap + write 時，系統同時又有另外一個程式對同一個檔案執行 write 時，將會觸發 SIGBUS 訊號 —— 因為產生非預期的記憶體存取操作，這個訊號對應的處理行為是，系統砍掉你的程式，並產生 core dump * 所以你不得不因此對 SIGBUS 訊號做事後補救或者提出資料存取的規範。 sendfile 系統呼叫的提出，就是克服上述問題，取代 read/write 兩個操作，並減少 context switch 和資料複製的次數: ```cpp sendfile(socket, file, len); ``` 流程示意: ![](https://i.imgur.com/Xco4OR0.png) * 步驟 `1`: sendfile 執行後，檔案資料會經由 DMA 傳遞給核心 buffer，再由 CPU 複製到socket buffer * 步驟 `2`: 將 socket buffer 的資料經由 DMA 傳遞到客戶端，所以執行 2 次 DMA Copy 及 1 次的 CPU Copy * 合計 3 次的資料複製討論: * 儘管改善資料複製和 context switch 成本，但仍有一份重複的資料，也就是 socket buffer，後者是否也能略去呢？只要硬體提供必要機制，即可做到，即 scatter-gather (聚合) 的功能，該功能主要的目的是，即將傳遞資料的一端不必要求存放的資料位址是連續的記憶體空間，換言之，可分散在記憶體的各個位置，隨後由硬體介入處理。 * 上述的組合就構成 Zero-Copy —— 不僅減少 context switch 且也減少 buffer 的使用，上層的應用程不需要做任何的變動，依舊使用 sendfile 系統呼叫。可用以下命令查詢網路卡是否支持 scatter-gather 特性： ```shell $ ethtool -k enp5s0 | grep scatter-gather ``` 參考輸出: ``` scatter-gather: on tx-scatter-gather: on tx-scatter-gather-fraglist: off [fixed] ``` Zero-Copy 流程示意: ![](https://i.imgur.com/hLvVzAG.png) * 步驟 `1`: sendfile 執行後，檔案資料經由 DMA 傳給核心模式的 buffer，但已不會再把資料複製到 socket buffer，後者只需理會有哪些核心模式的 buffer 的地址及資料長度，因此用 apend 模式。 * 步驟 `2`: 資料傳給客戶端也用 DMA，但來源變成核心模式 buffer。因此，不需要 CPU 去搬動資料，而是純粹 DMA 搬資料來實現 Zero-Copy。 ## splice 系統呼叫 sendfile 只適用於將資料從檔案拷貝到 socket，同時需要硬體的支援，Linux 核心自 `v2.6.17` 引入 splice 系統呼叫，不僅不需要硬體支援，還提供兩個 file descriptor (fd) 之間的資料 Zero-Copy。在 Linux 核心 2.6.33 後的版本，sendfile 已不再受限於複製資料到 socket 的操作，可用於任意的檔案。 ```cpp splice(fd_in, off_in, fd_out, off_out, len, flags); ``` ![](https://hackmd.io/_uploads/BJRfideQc.jpg) 以 splice 系統呼叫達到的 Zero-Copy，過程中的表現: * 2 次 context switch * 0 次 CPU 複製 * 2 次 DMA 複製使用者程式讀寫資料的流程如下： 1. 使用者程式經由 splice() 函式向核心發起系統呼叫 $\to$ 從使用者模式切換為核心模式 2. CPU 利用 DMA 控制器將資料從主記憶體或儲存裝置複製到核心空間的 read buffer 3. CPU 在核心空間的 read buffer 和 socket buffer 之間建立管線（pipe)。 4. CPU 利用 DMA 控制器將資料從 socket buffer 複製到網路裝置進行資料傳輸 5. context 從核心模式切換回使用者模式，splice 系統呼叫執行返回 6. splice 複製方式也同樣存在使用者程式不能對資料進行修改的問題。此外，它用 Linux 的管線緩衝機制，可用於任意兩個 fd 中傳輸資料，但它的兩個 fd 參數中有一個必為管線裝置。 ## 運用 sendfile 和 splice 來實作快速的 `cat` UNIX 工具的 [cat](http://man7.org/linux/man-pages/man1/cat.1.html) 是 "concatenate" 的意思，該命令具體作用為 > concatenate files and print on the standard output 透過上述 sendfile 和 splice 系統呼叫，我們可實作一個更快的 cat，專案: [fastcat](https://github.com/sysprog21/fastcat) ![](https://i.imgur.com/PzAjpy6.png) 用 [bench](https://hackage.haskell.org/package/bench) 工具測量: - [ ] simple ``` bench './simple 100-0.txt' benchmarking ./simple 100-0.txt time 176.2 ms (169.3 ms .. 189.5 ms) 0.995 R² (0.985 R² .. 1.000 R²) mean 175.6 ms (173.4 ms .. 179.7 ms) std dev 4.361 ms (1.680 ms .. 6.660 ms) variance introduced by outliers: 12% (moderately inflated) ``` - [ ] GNU coreutils 內附的 `cat` ``` bench 'cat 100-0.txt' benchmarking cat 100-0.txt time 2.691 ms (2.658 ms .. 2.719 ms) 0.999 R² (0.999 R² .. 1.000 R²) mean 2.662 ms (2.650 ms .. 2.675 ms) std dev 41.02 μs (32.51 μs .. 50.45 μs) ``` - [ ] fastcat ``` bench './fastcat 100-0.txt' benchmarking ./fastcat 100-0.txt time 1.520 ms (1.479 ms .. 1.566 ms) 0.995 R² (0.991 R² .. 0.999 R²) mean 1.514 ms (1.497 ms .. 1.532 ms) std dev 63.00 μs (46.37 μs .. 84.38 μs) variance introduced by outliers: 29% (moderately inflated) ``` --- shell 特殊變數: * `$?` : 上個執行過的命令所返回的狀態值 * `$$` : 目前 shell 的 process ID ```shell $ ls -l /proc/$$/fd ``` 參考輸出: ``` lrwx------ 1 0 -> /dev/pts/0 lrwx------ 1 1 -> /dev/pts/0 lrwx------ 1 2 -> /dev/pts/0 lrwx------ 1 255 -> /dev/pts/0 l-wx------ 1 3 -> /dev/null ``` # 透過 timerfd 處理週期性任務 ## timerfd [timerfd](http://man7.org/linux/man-pages/man2/timerfd_settime.2.html) 是 Linux 系統呼叫，允許用 file descriptor 的方式來操作 timer，並可搭配原本的 I/O Multiplexor 機制。一旦 timerfd_create() 將時間轉為 fd，後者在 timeout 時即可 read，這樣我們透過 epoll 一類的系統呼叫，就能處理週期性任務。 > [Linux 核心設計: 檔案系統概念及實作手法](https://hackmd.io/@sysprog/linux-file-system) [timerfd](http://man7.org/linux/man-pages/man2/timerfd_settime.2.html) 和 [select](https://man7.org/linux/man-pages/man2/select.2.html) 的timeout 區別: - `timerfd_create` 將計時器轉換為檔案，一遇到超時，該特別的檔案即可讀取，於是就可搭配 I/O multiplexor，用一致的方式來處理 I/O 事件和超時事件，參見[高效 Web 伺服器開發](https://hackmd.io/@sysprog/fast-web-server) - [select](https://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫的 `timeout` 的精度較低範例程式碼: ```cpp #include <stdint.h> /* Definition of uint64_t */ #include <stdio.h> #include <stdlib.h> #include <sys/timerfd.h> #include <time.h> #include <unistd.h> #define handle_error(msg) \ do { \ perror(msg); \ exit(EXIT_FAILURE); \ } while (0) static void print_elapsed_time(void) { static struct timespec start; struct timespec curr; static int first_call = 1; int secs, nsecs; if (first_call) { first_call = 0; if (clock_gettime(CLOCK_MONOTONIC, &start) == -1) handle_error("clock_gettime"); } if (clock_gettime(CLOCK_MONOTONIC, &curr) == -1) handle_error("clock_gettime"); secs = curr.tv_sec - start.tv_sec; nsecs = curr.tv_nsec - start.tv_nsec; if (nsecs < 0) { secs--; nsecs += 1000000000; } printf("%d.%03d: ", secs, (nsecs + 500000) / 1000000); } int main(int argc, char *argv[]) { struct itimerspec new_value; int max_exp, fd; struct timespec now; uint64_t exp, tot_exp; ssize_t s; if ((argc != 2) && (argc != 4)) { fprintf(stderr, "%s init-secs [interval-secs max-exp]\n", argv[0]); exit(EXIT_FAILURE); } if (clock_gettime(CLOCK_REALTIME, &now) == -1) handle_error("clock_gettime"); /* Create a CLOCK_REALTIME absolute timer with initial expiration and interval as specified in command line */ new_value.it_value.tv_sec = now.tv_sec + atoi(argv[1]); new_value.it_value.tv_nsec = now.tv_nsec; if (argc == 2) { new_value.it_interval.tv_sec = 0; max_exp = 1; } else { new_value.it_interval.tv_sec = atoi(argv[2]); max_exp = atoi(argv[3]); } new_value.it_interval.tv_nsec = 0; fd = timerfd_create(CLOCK_REALTIME, 0); if (fd == -1) handle_error("timerfd_create"); if (timerfd_settime(fd, TFD_TIMER_ABSTIME, &new_value, NULL) == -1) handle_error("timerfd_settime"); print_elapsed_time(); printf("timer started\n"); for (tot_exp = 0; tot_exp < max_exp;) { s = read(fd, &exp, sizeof(uint64_t)); if (s != sizeof(uint64_t)) handle_error("read"); tot_exp += exp; print_elapsed_time(); printf("read: %llu; total=%llu\n", (unsigned long long) exp, (unsigned long long) tot_exp); } exit(EXIT_SUCCESS); } ``` 預期輸出: (參數: `1 1 10`) ``` 0.000: timer started 1.000: read: 1; total=1 2.000: read: 1; total=2 3.000: read: 1; total=3 4.000: read: 1; total=4 5.000: read: 1; total=5 6.000: read: 1; total=6 7.000: read: 1; total=7 8.000: read: 1; total=8 9.000: read: 1; total=9 10.000: read: 1; total=10 ``` 搭配 epoll 的示範: ```cpp #include <pthread.h> #include <stdio.h> #include <sys/epoll.h> #include <sys/timerfd.h> #include <time.h> #include <unistd.h> static void add_event(int epoll_fd, int fd, int state) { struct epoll_event ev = { .events = state, .data.fd = fd, }; epoll_ctl(epoll_fd, EPOLL_CTL_ADD, fd, &ev); return; } static int calc_proc_time(int *start) { struct timespec end; clock_gettime(CLOCK_REALTIME, &end); if (start) return end.tv_sec * 1000 + end.tv_nsec / 1000000 - *start; return end.tv_sec * 1000 + end.tv_nsec / 1000000; } static void *worker(void *user) { int epoll_fd = *(int *) user; struct epoll_event events[1] = {0}; while (1) { int ms = calc_proc_time(NULL); int fire_events = epoll_wait(epoll_fd, events, 1, -1); ms = calc_proc_time(&ms); if (fire_events > 0) { printf("time out: %d ms\n", ms); uint64_t exp; ssize_t size = read(events[0].data.fd, &exp, sizeof(uint64_t)); if (size != sizeof(uint64_t)) perror("read error"); } } return NULL; } int timer_update(int timer_fd, int ms) { struct itimerspec its = { .it_interval = {.tv_sec = 2, .tv_nsec = 0}, .it_value.tv_sec = ms / 1000, .it_value.tv_nsec = (ms % 1000) * 1000 * 1000, }; if (timerfd_settime(timer_fd, 0, &its, NULL) < 0) return -1; printf("timer update: %d\n", ms); return 0; } int main() { /* create epoll */ int epoll_fd = epoll_create(1); /* create timer */ int timer_fd = timerfd_create(CLOCK_MONOTONIC, TFD_CLOEXEC | TFD_NONBLOCK); /* add timer fd to epoll monitor event */ add_event(epoll_fd, timer_fd, EPOLLIN); /* create thread to monitor */ pthread_t tid; pthread_create(&tid, NULL, &worker, (void *) &epoll_fd); timer_update(timer_fd, 1000); while (1) usleep(1000000); return 0; } ``` 練習題: * [2020q1 第 15 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz15) # io_uring ## 點題 > 前情提要: [事件驅動伺服器：原理和實例](https://hackmd.io/@sysprog/event-driven-server) * [The Evolution of File Descriptor Monitoring in Linux: From select to io_uring](https://vmsplice.net/~stefan/stefanha-fosdem-2021.pdf) * [IO-uring speed the RocksDB & TiKV](https://openinx.github.io/ppt/io-uring.pdf) ## What is io_uring? 在 Linux 底下操作 IO 有以下方式: * `read` 系列 * `pread` * `preadv` 但他們都是 synchronous 的，所以 POSIX 有實做 `aio_read`，但其乏善可陳且效能欠佳。事實上 Linux 也有自己的 native async IO interface，但是包含以下缺點: 1. async IO 只支援 `O_DIRECT` (or un-buffered) accesses -> file descriptor 的設定 2. IO submission 伴隨 104 bytes 的 data copy (for IO that's supposedly zero copy)，此外一次 IO 必須呼叫兩個 system call (submit + wait-for-completion) 3. 有很多可能會導致 async 最後變成 blocking (如: submission 會 block 等待 meta data; request slots 如果都被佔滿， submission 亦會 block 住) Jens Axboe 一開始先嘗試改寫原有的 native aio，但是失敗收場，因此他決定提出一個新的 interface，包含以下目標 (越後面越重要): 1. Easy to understand and intuitive to use 2. Extendable，除了 block oriented IO，networking 和 non-block storage 也要能用 3. Efficiency 4. Scalability 在設計 io_uring 時，為了避免過多 data copy，Jens Axboe 選擇透過 shared memory 來完成 application 和 kernel 間的溝通。其中不可避免的是同步問題，使用 single producer and single consumer ring buffer 來替代 shared lock 解決 shared data 的同步問題。而這溝通的管道又可分為 submission queue (SQ) 和 completion queue (CQ)。以 CQ 來說，kernel 就是 producer，user application 就是 consumer。SQ 則是相反。 ## Linking request CQEs can arrive in any order as they become available。(舉例: 先讀在 HDD 上的 A.txt，再讀 SSD 上的 B.txt，若限制完成順序的話，將會影響到效能)。事實上，也可以強制 ordering (see [example](https://kernel.dk/io_uring.pdf)) liburing 預設會非循序的執行 submit queue 上的 operation，但是有些特別的情況，我們需要這些 operation 被循序的執行，如：`write` + `close`。所以我們可以透過添加 `IOSQE_IO_LINK` 來達到效果。詳細用法可參考 [linking request](https://unixism.net/loti/tutorial/link_liburing.html) ## Submission Queue Polling liburing 可以透過設定 flag: `IORING_SETUP_SQPOLL` 切換成 poll 模式，這個模式可以避免使用者一直呼叫 `io_uring_enter` (system call)。此模式下，kernel thread 會一直去檢查 submission queue 上是否有工作要做。詳細用法可參考 [Submission Queue Polling](https://unixism.net/loti/tutorial/sq_poll.html#sq-poll) 值得注意的是 kernel thread 的數量需要被控制，否則大量的 CPU cycle 會被 k-thread 佔據。為了避免這個機制，liburing 的 kthread 在一定的時間內沒有收到工作要做，kthread 就會 sleep，所以下一次要做 submission queue 上的工作就需要走原本的方式: `io_uring_enter()` :::info When using liburing, you never directly call the io_uring_enter() system call. That is usually taken care of by liburing’s io_uring_submit() function. It automatically determines if you are using polling mode or not and deals with when your program needs to call io_uring_enter() without you having to bother about it. ::: ## Memory ordering 如果要直接使用 liburing 就不用管這個議題，但是如果是要操作 raw interface，那這個就很重要。提供兩種操作: 1. `read_barrier()`: Ensure previous writes are visible before doing subsequent memory reads 2. `write_barrier()`: Order this write after previous writes > The kernel will include a read_barrier() before reading the SQ ring tail, to ensure that the tail write from the application is visible. From the CQ ring side, since the consumer/producer roles are reversed, the application merely needs to issue a read_barrier() before reading the CQ ring tail to ensure it sees any writes made by the kernel. ## liburing library * Remove the need for boiler plate code for setup of an io_uring instance * Provide a simplified API for basic use cases. ### Advanced use cases and features #### FIXED FILES AND BUFFERS #### POLLED IO I/O relying on hardware interrupts to signal a completion event. When IO is polled, the application will repeatedly ask the hardware driver for status on a submitted IO request. [註] [Real polling example](https://unixism.net/loti/tutorial/sq_poll.html) [註] Submission queue polling only works in combination with fixed files (not fixed buffer) #### KERNEL SIDE POLLING 會有 kernel thread 主動偵測 SQ 上是否有東西，這樣可以避免呼叫 syscall: `io_uring_enter` ## 原始程式碼 ### `io_uring_setup` 基本的設定。我們關注的是 setup 時需要設定哪些關於 `IORING_SETUP_SQPOLL` 的操作，預期找到 kthread 的建立，kthread 的工作內容等等。從 `io_sq_offload_create` 可知 offload 和 kthread 有關。往裡面看可以找到 [create_io_thread](https://github.com/torvalds/linux/blob/65090f30ab791810a3dc840317e57df05018559c/kernel/fork.c#L2444)，透過 `copy_process` 達到 fork，搭配 `wake_up_new_task` 啟動 process。該 process 要做的事為 [io_sq_thread](https://github.com/torvalds/linux/blob/master/fs/io_uring.c#L6882)， ### `io_uring_enter` [io_uring_enter](https://github.com/torvalds/linux/blob/master/fs/io_uring.c#L9332) 在 prepare 完 write/read 之類的 operation 後會被呼叫，這裡我們只關注在 poll 模式下的行為: ```cpp if (ctx->flags & IORING_SETUP_SQPOLL) { io_cqring_overflow_flush(ctx, false); ret = -EOWNERDEAD; if (unlikely(ctx->sq_data->thread == NULL)) goto out; if (flags & IORING_ENTER_SQ_WAKEUP) wake_up(&ctx->sq_data->wait); if (flags & IORING_ENTER_SQ_WAIT) { ret = io_sqpoll_wait_sq(ctx); if (ret) goto out; } submitted = to_submit; } else if ... ``` 1. 若 `kthread` 閒置太久，為了避免霸佔 CPU，所以會主動 sleep，所以若看到 flag: `IORING_ENTER_SQ_WAKEUP` 設起，就必須要喚醒 kthread。 2. [PATCH: provide IORING_ENTER_SQ_WAIT for SQPOLL SQ ring waits](https://www.spinics.net/lists/io-uring/msg04097.html) ## Install liburing 1. 下載 source [code](https://github.com/axboe/liburing/releases) 2. ./configure 3. sudo make install 4. compile example: gcc -Wall -O2 -D_GNU_SOURCE -o io_uring-test io_uring-test.c -luring ## liburing flow io_uring_queue_init -> alloc iov -> io_uring_get_sqe -> io_uring_prep_readv -> io_uring_sqe_set_data -> io_uring_submit io_uring_wait_cqe -> io_uring_cqe_get_data -> io_uring_cqe_seen -> io_uring_queue_exit ## liburing/io_uring API ### io_uring 1. io_uring_setup(u32 entries, struct io_uring_params *p) * Description: Set up a submission queue (SQ) and completion queue (CQ) with at least entries entries, and returns a file descriptor which can be used to perform subsequent operations on the io_uring instance. * Relationship: wrap by liburing function: `io_uring_queue_init` * Flags: member of `struct io_uring_params` * IORING_SETUP_IOPOLL: * busy-waiting for an I/O completion * provides lower latency, but may consume more CPU resources than interrupt driven I/O * usable only on a file descriptor opened using the O_DIRECT flag * It is illegal to mix and match polled and non-polled I/O on an io_uring instance * IORING_SETUP_SQPOLL: * after setting, a kernel thread is created to perform submission queue polling * flag will be set with `IORING_SQ_NEED_WAKEUP` if kernel thread is idle more than `sq_thread_idle` milliseconds * before linux 5.11, application must register a set of files to be used for IO through `io_uring_register` using the `IORING_REGISTER_FILES` opcode * IORING_SETUP_SQ_AFF: * poll thread will be bound to the cpu set in the `sq_thread_cpu` field of the `struct io_uring_params` * If no flags are specified, the io_uring instance is setup for interrupt driven I/O 2. io_uring_register(unsigned int fd, unsigned int opcode, void *arg, unsigned int nr_args) * opcode: * IORING_REGISTER_BUFFERS: * uffers are mapped into the kernel and eligible for I/O * make use of them, the application must specify the `IORING_OP_READ_FIXED` or `IORING_OP_WRITE_FIXED` opcodes in the submission queue entry and set the `buf_index` field to the desired buffer index * IORING_REGISTER_FILES: * Description: register files for I/O. `arg` contains a pointer to an array of `nr_args` file descriptors * make use of them, the `IOSQE_FIXED_FILE` flag must be set in the flags member of the `struct io_uring_sqe`, and the `fd` member is set to the index of the file in the file descriptor array * IORING_REGISTER_EVENTFD: * It's possible to use `eventfd()` to get notified of completion events on an io_uring instance. 3. io_uring_enter(unsigned int fd, unsigned int to_submit, unsigned int min_complete, unsigned int flags, sigset_t *sig) * Description: single call can both submit new I/O and wait for completions of I/O initiated by this call or previous calls to `io_uring_enter()` * Flags: * IORING_ENTER_GETEVENTS: * wait for the specificied number of events in `min_complete` before returning * can be set along with to_submit to both submit and complete events in a single system call * IORING_ENTER_SQ_WAKEUP * IORING_ENTER_SQ_WAIT * opcode: * IORING_OP_READV * IORING_OP_WRITEV * some details: * If the io_uring instance was configured for polling, by specifying `IORING_SETUP_IOPOLL` in the call to `io_uring_setup()`, then `min_complete` has a slightly different meaning. Passing a value of 0 instructs the kernel to return any events which are already complete, without blocking. If `min_complete` is a non-zero value, the kernel will still return immediately if any completion events are available. If no event completions are available, then the call will poll either until one or more completions become available, or until the process has exceeded its scheduler time slice. ### liburing ## io_uring v.s. epoll ### io_uring is slower than epoll? - [liburing #189](https://github.com/axboe/liburing/issues/189) - [liburing #215](https://github.com/axboe/liburing/issues/215) - [netty #10622](https://github.com/netty/netty/issues/10622) ## Reference * [Lord of the io_uring](https://unixism.net/loti/what_is_io_uring.html) * [Efficient IO with io_uring - official pdf](https://kernel.dk/io_uring.pdf) * [io_uring](https://unixism.net/2020/04/io-uring-by-example-part-1-introduction/) * [liburing example](https://unixism.net/loti/tutorial/index.html) * [liburing web server](https://github.com/shuveb/loti-examples/blob/master/webserver_liburing.c)