# Linux 核心設計: 針對事件驅動的 I/O 模型演化 研讀筆記
contributed by < `Jordymalone` >
> 參閱 [Linux 核心設計: 針對事件驅動的 I/O 模型演化](https://hackmd.io/@sysprog/linux-io-model/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fevent-driven-server)
## 事件驅動伺服器: 原理與實例
> [The Evolution of Linux I/O Models: A Path towards IO_uring](https://docs.google.com/presentation/d/1CJiDAO6GbWwpeaeG-TMN751H8Bpq_nKQnnZE_yclFB4/edit?slide=id.p#slide=id.p)
I/O models 大致上可以分成以下兩個面向:
* Synchronous I/O
* Blocking I/O
* Non-blocking I/O
* I/O multiplexing
* Asynchronous I/O - 實作上最麻煩
:::info
[signal](https://man7.org/linux/man-pages/man2/signal.2.html) 是同步還非同步? 兩者都有(?)
:::
透過 `read` 會切換到 kernel mode，這時候 kernel 要做對應的操作，依據給定的 fd 去判斷說這個 fd 來自哪裡，這邊的 fd 可以來自傳統意義上的檔案系統，也可以來自網路上的 socket，甚至可以來自 signal ([signalfd](https://man7.org/linux/man-pages/man2/signalfd.2.html)) 或是 timer ([timerfd](https://hackmd.io/@sysprog/linux-timerfd))。
```c
#include <unistd.h>
ssize_t read(int fd, void *buf, size_t count);
```
`buf` 這個參數很重要，他是個指標，其記憶體配置是由呼叫端去配置，為甚麼呢?
因為它實際的資料是從 kernel 複製到 user space，所以當你的緩衝區沒有正確配置記憶體或是保留記憶體的話，kernel 的資料複製就會錯誤。
:::info
所以核心原先並不知道你緩衝區需要多少資料，而是透過 `buf` 這個參數來得知可以給你多少
> `EFAULT` - `buf` is outside your accessible address space.
:::
User 與 Kernel 是 isolated 的，所以當資料準備好，還是得從 Kernel buffer 複製到 user space。
進入 kernel mode 可以分成兩階段 wait for data 和 copy data from kernel to user。
:::info
為什麼要分成這兩個階段?
:::
> Blocking 與 Nonblocking 並不是完全對立的，本質上是一種選擇，選擇在等待過程中我要不要收回一部份的權利
> * Blocking 把 I/O 的操作全程交給作業系統的核心處理
> * Nonblocking 則是呼叫端他可以收回一部分的控制權，但是真正的操作還是要靠 kernel
在資料沒就緒的情況下，可以去做別的事情。因為她總是會返回，所以我們一定要去檢查她返回的數值和對應的 error code。
Nonblocking 並不是說每一個時間都不會阻塞，總會有在某些地方被阻塞的，比如說 kernel 複製資料到 user space，這一定要等 kernel。
**Nonblocking 其關鍵在於等待資料就緒的時候可以做別的事。**
假設我可以等待很多種資料，我就可以搭配 multiplexor
:::info
本質上是 Blocking，為甚麼呢?
我們不會因為一個事件 block，可以看到事件怎麼來，並監聽多個事件。 (我還沒聽懂...)
:::
需要 Kernel 配合，user level thread 和 kernel level thread 可以在同個 CPU 也可以不同。
> 行程在提交 I/O 請求後，系統立即返回，I/O 的整個過程 (包括資料可用的等待與資料複製這兩個部分) 皆由核心背景處理 (kernel thread)，並在操作完成後透過訊號（signal）、callback 或完成佇列通知應用程式。整個過程中，行程從未因該 I/O 操作而被阻塞
`aio_read` 是 `read` 的非同步版本。
如果你的 aio 是跑在單核處理器上，那效果不會很顯著。
要好好思考你 aio 的應用場景。
> 引用自 [淺談I/O Model](https://medium.com/@clu1022/%E6%B7%BA%E8%AB%87i-o-model-32da09c619e6)
Synchronous I/O 在執行 I/O operation 的時候會將 process/thread 給 block 住，而asynchronous 則不同，其在 user process 觸發 I/O 操作後，就直接回傳去做別的事了，等到kernel 處理完 I/O 後，會發送一個信號給 user process，說 I/O 已經結束了，在這段過程中，user process 就沒有被block住 (就是叫別人去幫你等東西或是做事喇)。
再換個講法，區別這兩者的關鍵就是到底是誰在進行真正的I/O，如果是主執行緒，那就是synchronous，若是衍生出來的子執行緒，待子執行緒完成 I/O operation 後回報給主執行緒，這就是 asynchronous。
講到這邊可能有些地方還是會讓人搞混，譬如說 non-blocking 可能會被認為沒有 block 產生因而被歸類在 asynchronous 之下，但事實上是有的。前一段講到，synchronous I/O 在執行 I/O operation 的時候會將 process 給 block 住，這邊對 I/O operation 的定義 **指的是真實的 I/O 操作(物理意義上的)**。什麼是真實的 I/O 操作呢? 像是 recvfrom 這種 system call 就是。確實，在nonblocking 中，我們會一直問 kernel 東西好了沒，沒好就不管，但是若好了的話呢? 這時我們就必須透過 recvfrom 來將資料 copy 至 application buffer 中，**在 copy 的這個過程，user process 就是被 block 住的。**
其實對於 synchronous 這一詞，我想還可以這樣看: 所謂的同步 (synchronous)，就是 user space 跟 kernel space 要一起合作，由 user space trigger 一個 I/O operation，然後由 kernel space 來回應這個 request。至於在非同步 (asynchronous) 的概念裡，user space 就可以不用跟kernel space 合作了，我們可以從前面的例子中看到，在非同步的場景下，user space 就像是買家在家裡網購一般，一個訂單送出後，等商家 (kernel) 把東西送到府上後再直接拿就好了。講白了就是工具人喇。
- [ ] 待讀 [Synchronous and Asynchronous I/O](https://learn.microsoft.com/en-us/windows/win32/fileio/synchronous-and-asynchronous-i-o)
> 0512 閱讀計算機組織小考
原文書在講述 register file 做讀寫時，我可以在同個 clock cycle 中做讀寫，因為讀取是非同步的行為，而寫則是發生在**上升沿**，所以以順序來看是上升沿發生前，就已經做讀取了，所以上升沿發生的寫入，並不會影響到同個 clock cycle 中讀取出來的資料。
:::info
老師舉例的咖啡店要怎麼套用到 clock cycle 上?
:::
### I/O model
單一行程便可透過 select 高效處理多條連線，是達成高度並行伺服器的基礎。
什麼是雙工 duplex ?
~~班長和小兵，一個命令一個動作~~ 用電話這個例子來思考
為了解決能即時察覺哪條線路有可讀資料的問題，我們可以使用 [select](https://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫監聽來達到目的。
#### Blocking I/O
當行程在使用者空間呼叫 read() 系統呼叫後，系統會進行一次模式切換 (CPU mode transition)，切入核心空間並等待資料就緒。若所需資料尚未抵達核心緩衝區，行程將持續停留在核心空間，直到資料可用。
:::info
這樣算是 sleep 嗎? 那核心會維護一個資料結構來存放他嗎?
:::
那此時 CPU 在幹嘛?
CPU 不會一直待在那個核心函式裡「空轉」，而是回到排程器去做其他更重要的事情，我認為流程是:
行程資料尚未就緒 -> sleep -> 排程器接手安排下個 task -> CPU 做別的事情 -> 裝置準備好資料，發中斷 -> CPU 暫停當前做的事情跳進 Interrupt Handler 把資料搬到緩衝區 -> 喚醒行程 -> read() 做完，資料給你，回到 user space，等待排程器分配 CPU
#### Non-blocking I/O
透過 `fcntl()` 系統呼叫來啟用，將目標檔案描述子設定為 O_NONBLOCK 模式，告知核心後續所有操作應以非阻塞方式處理。
高效能伺服器框架 [lwan](https://github.com/lpereira/lwan) 即大量採用 non-blocking I/O 技術。
資料尚未準備完成時，會將控制權交還給 user space 去做其他事情，那資料準備好時，他要怎麼告知 user space 的應用程式？
#### I/O Multiplexing Model
**select**
- [ ] 待看 [select_tut(2)](https://man7.org/linux/man-pages/man2/select_tut.2.html)
select 正常情況下會回傳什麼?
> 回傳非負整數，代表的是**就緒**的檔案描述符數量，也就是在指定的 fd_set 中，處於就緒狀態 (可讀、可寫或有異常) 的檔案描述子
那何謂 **就緒**? (一直困擾著我)
在 `select` 中，一個 fd 就緒可以把他理解成，如果你現在馬上對這個 fd 做對應的操作 (`read` or `write`) ，他不會 block 阻塞，而且操作可以成功並返回合理的數值。
> select() 可能回報某個 socket fd 為「可讀」，但接下來的 read 卻仍可能阻塞。例如，資料雖到達，但因檢查碼錯誤被丟棄，導致後續無資料可讀。故建議對不應阻塞的 socket 加上 O_NONBLOCK 旗標
:::info
為什麼會有資料到達，但檢查碼錯誤被丟棄，導致後續無資料可讀的狀況?
:::
以我目前的認知，~~我認為 select 會以 linear seacrh 的形式去一個個監控 fd_set~~ `select` 透過線性掃描檢查 fd_set 中所有 fd，判斷它們是否「就緒」，並回傳就緒的 fd 數量。
* read - 有資料可以馬上讀 (不會 block)，或是對方關閉 (read() 回傳 0)
* write - 你可以立刻 write() 至 fd (buffer 有空間)
但 select 不是主動看到對方送資料進來，而是問 kernel 「嘿，我想對這幾個 fd 做某件事 (例如 read)，你告訴我誰現在可以馬上做而不會卡住？」，他是個**事件通知的機制**，他不在乎資料的內容或來源是誰，他只關心**是否可以對現在這個 fd 做某個 I/O 操作?**
select 其內部呼叫的是以下函式:
```c
static __attribute__((unused))
int select(int nfds, fd_set *rfds, fd_set *wfds, fd_set *efds, struct timeval *timeout)
{
return __sysret(sys_select(nfds, rfds, wfds, efds, timeout));
}
```
epoll
- [ ] 延伸閱讀: [poll vs select vs event-based](https://daniel.haxx.se/docs/poll-vs-select.html)
#### Asynchronous I/O
Linux 亦實作二種主要方案：
* glibc POSIX AIO：使用執行緒模擬非同步行為，實作上較為笨重
* Linux native AIO：直接由核心處理，但早期版本支援有限，對檔案類型與 I/O 模式有不少限制
具體上是遇到了什麼限制導致無法廣泛使用？
### I/O Multiplexing syscall
為什麼引入 epoll?
其實一開始我們會用 select() 來做 I/O 多工，是為了解決一個問題：
如果我一次只能 `read` 一個 socket，那我每個連線都要開一個執行緒來等資料，不但浪費資源，而且很難擴展。
`select()` 的好處是，我可以同時監控一堆連線，一次就知道哪個連線有動靜。這就像你當服務生，不用一桌桌問客人「要點餐了嗎」，**而是拿著一張清單問完所有桌，再回來處理那些真的有舉手的桌子。**
但這個方法還是有幾個明顯的缺點：
* 掃桌速度慢：每次你都要重新掃過整張清單，哪怕只有一兩桌真的有需要，你也得問完整圈（這就是 O(N) 的效能瓶頸）。
* 最多只能問 1024 桌：在 `select` 裡面，fd 的數量有限制（由 FD_SETSIZE 控制），你沒辦法監控成千上萬個連線。
* 誤報問題：有時候 `select` 會告訴你「這個連線可以讀了」，但你 read() 下去卻還是卡住，因為可能資料被丟棄了（像是 checksum 錯誤），這種「看起來可讀但其實沒有資料」會導致額外問題。
* 用法比較笨重：即使知道哪幾個 fd 就緒，你還是得自己一個個去掃查，找出是哪個有資料可以讀，再手動去呼叫 read()，整體流程比較複雜且浪費效率。
所以為了解決這些問題，Linux 才推出了 epoll。它與 select 最大的差別在於：
不用每次都去問所有人，只要一開始註冊好，之後有事的人會主動來通知你。
就像每桌都有個鈴鐺，客人要點餐就按鈴，這樣你只服務真正有需求的人，節省大量無謂的查詢成本。
再加上 epoll 幾乎沒有限制你監控幾個 fd，還能支援邊註冊邊監控（非同步註冊），所以當你的系統需要處理數千甚至上萬條連線時，epoll 幾乎是必選方案。
> 謝謝 GPT 的整理和比喻
節錄自 /tools/include/nolibc/sys.h
```c
static __attribute__((unused))
int select(int nfds, fd_set *rfds, fd_set *wfds, fd_set *efds, struct timeval *timeout)
{
return __sysret(sys_select(nfds, rfds, wfds, efds, timeout));
}
```
> 參閱 [5.34 Specifying Attributes of Variables](https://gcc.gnu.org/onlinedocs/gcc-4.4.5/gcc/Variable-Attributes.html#i386%20Variable%20Attributes)
GCC 提供 `__attribute__ ((...))` 語法，允許開發者在變數或函式宣告中加入特定屬性，用來控制編譯器的行為。
在上述程式碼中使用 `__attribute__ (( ))` 表示即使這個函式在後續程式碼中從未被使用，編譯器也不應產生 "defined but not used" 的警告。
### epoll 系列系統呼叫
EPOLL_CLOEXEC 為什麼需要這個？
確保執行 `exec` 的子行程不會意外繼承到 fd 資源
[epoll](https://man7.org/linux/man-pages/man7/epoll.7.html) - I/O event notification facility
```c
#include <sys/epoll.h>
int epoll_create(int size);
int epoll_create1(int flags);
```
[epoll_create](https://man7.org/linux/man-pages/man2/epoll_create.2.html)
> Returns a file descriptor referring to the new epoll instance. This file descriptor is used for all the subsequent calls to the epoll interface.
epoll_create1 - 建立一個 epoll 實例
> If flags is 0, then, other than the fact that the obsolete size argument is dropped, epoll_create1() is the same as epoll_create().
```c
int epfd = epoll_create1(0);
```
flags 種類:
* `0` - 行為與 epoll_create 一樣
* `EPOLL_CLOEXEC` - 若建立該 epoll fd 的行程透過 fork() 建立子行程，在子行程 exec() 之前，自動關閉該 epoll fd (避免子行程意外繼承不該存取的 epoll 實體)
```c
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *_Nullable event);
```
```c
struct epoll_event {
__poll_t events; // 你想監控什麼事件
__u64 data; // 任意資料，可存 fd、指標、結構體之類的
} EPOLL_PACKED;
```
[epoll_ctl](https://man7.org/linux/man-pages/man2/epoll_ctl.2.html) - 用來操作 epoll 實體，其功能是將特定 fd 加入、移除或更新於 epoll 的監控清單中 (這個監控清單又稱為 interest list)
`op` 又分以下三種操作
* `EPOLL_CTL_ADD` - 將 fd 加入 epoll 監控清單，設定所關注的事件
* `EPOLLIN`: 可讀（資料準備好了）
* `EPOLLOUT`: 可寫（可立即寫資料）
* `EPOLLERR`: 發生錯誤
* `EPOLLHUP`: 對方 hang up
* `EPOLLET`: Edge-triggered（邊緣觸發）
```c
struct epoll_event ev;
ev.events = EPOLLIN; // 當這個 fd 有資料可以讀時通知我
ev.data.f = STDIN_FILENO; // 看要放哪個 fd 你決定
epoll_ctl(epfd, EPOLL_CTL_ADD, STDIN_FILENO, &ev);
// 請把 fd=STDIN_FILENO 加到 epfd 代表的 epoll 監控清單裡，並監控它是否有 EPOLLIN 事件，發生時通知我
```
* `EPOLL_CTL_DEL` - 將 fd 自 epoll 清單移除，行程將不再收到該 fd 的事件通知。若該 fd 被加入至多個 epoll 實體，關閉該 fd 會自動從所有 epoll 清單中移除。
* `EPOLL_CTL_MOD` - 更新已在 epoll 中註冊的 fd 的事件關注設定
而這個 interest list 又有個子集合，專門暫存那些觸發的事件，叫做 ready list
- [ ] interest / ready list 是用什麼資料結構去維護的?
[epoll_wait](https://man7.org/linux/man-pages/man2/epoll_wait.2.html) - waits for events on the epoll instance referred to by the file descriptor epfd.
> The buffer pointed to by events is used to return information from the ready list about file descriptors in the interest list that have some events available. Up to maxevents are returned by epoll_wait(). The maxevents argument must be greater than zero.
> epoll event 與 epoll_create1 建立的 epoll instance 有什麼關係？
> 我用 epoll_create1 建立好之後會有什麼實體物件嗎？為什麼我還要自己用個 `struct epoll_event ev` 並 assign 值給他？
想像你是老闆（epoll instance），你有一個管理表格（kernel 的 red-black tree），你要記錄哪些員工 (fd):
* 要監控什麼狀況（例如 EPOLLIN = 有新任務來）
* 有事時要通知誰（ev.data = 員工 id、socket、callback 資訊）
* 這時你就要每次給 kernel 一份說明書（epoll_event）來記錄這個 fd。
何謂事件驅動式伺服器？
> 就像是披薩店
## 高效 web 伺服器開發
accept ?
accept a connection on a socket
```c
int accept(int sockfd, struct sockaddr *_Nullable restrict addr, socklen_t *_Nullable restrict addrlen);
```
TCP - Transmission Control Protocol
伺服器開了一扇門（`listen()`），等人來按門鈴（client 連線），一旦有人按門鈴（`accept()`），你開門給他，接著聊聊天（`read()`），然後回一句話（`write()`），聊完關門（`close()`），然後準備好迎接下一位訪客（再 `accept()`）。
```c
int sockfd = socket(...); // 1. 開門口
bind(sockfd, ...); // 2. 定門牌地址
listen(sockfd, BACKLOG); // 3. 開始聽門鈴
int connfd = accept(sockfd, ...); // 4. 有人按門鈴就開門
```
- [ ] [epoll demo](https://gist.github.com/MagnusTiberius/bf31eb8584452f8b12c637871ba517f0)
## Ref
* [带你彻底理解Linux五种I/O模型](https://wiyi.org/linux-io-model.html)
* [Chapter 6. I/O Multiplexing: The select and poll Functions](https://notes.shichao.io/unp/ch6/)
* [I/O Model](https://wirelessr.gitbooks.io/working-life/content/io_model.html)
Sign in with Wallet
Connect another wallet