從 4 個方面分析 epoll 的實現原理

前言

本文以四個方面介紹 epoll 的實現原理，1.epoll 的數據結構；2. 協議棧如何與 epoll 通信；3.epoll 線程安全如何加鎖；4.ET 與 LT 的實現。

epoll 的數據結構

多種數據結構進行決策

epoll 至少需要兩個集合

  1. 所有 fd 的總集

  2. 就緒 fd 的集合

那麼這個總集選用什麼數據結構存儲呢？我們知道，一個 fd，其底層對應一個 TCB。那麼也就是說 key=fd,val=TCB, 是一個典型的 kv 型數據結構，對於 kv 型數據結構我們可以使用以下三種進行存儲。

1. hash2. 紅黑樹3. b/b+tree

如果使用 hash 進行存儲，其優點是查詢速度很快，O(1)。但是在我們調用 epoll_create() 的時候，hash 底層的數組創建多大合適呢？如果我們有百萬的 fd，那麼這個數組越大越好，如果我們僅僅十幾個 fd 需要管理，在創建數組的時候，太大的空間就很浪費。而這個 fd 我們又不能預先知道有多少，所以 hash 是不合適的。

b/b+tree 是多叉樹，一個結點可以存多個 key，主要是用於降低層高，用於磁盤索引的，所以在我們這個內存場景下也是不適合的。

在內存索引的場景下我們一般使用紅黑樹來作爲首選的數據結構，首先紅黑樹的查找速度很快, O(log(N))。其次在調用 epoll_create() 的時候，只需要創建一個紅黑樹樹根即可，無需浪費額外的空間。

那麼就緒集合用什麼數據結構呢，首先就緒集合不是以查找爲主的，就緒集合的作用是將裏面的元素拷貝給用戶進行處理，所以集合裏的元素沒有優先級，那麼就可以採用線性的數據結構，使用隊列來存儲，先進先出，先就緒的先處理。

  1. 所有 fd 的總集 -----> 紅黑樹

  2. 就緒 fd 的集合 -----> 隊列

紅黑樹和就緒隊列的關係

紅黑樹的結點和就緒隊列的結點的同一個節點，所謂的加入就緒隊列，就是將結點的前後指針聯繫到一起。所以就緒了不是將紅黑樹結點 delete 掉然後加入隊列。他們是同一個結點，不需要 delete。

協議棧如何與 epoll 模塊通信

epoll 的工作環境

應用程序只能通過三個 api 接口來操作 epoll。當一個 io 準備就緒的時候，epoll 是怎麼知道 io 準備就緒了呢？是由協議棧將數據解析出來觸發回調通知 epoll 的。也就是說可以把 epoll 的工作環境看出三部分，左邊應用程序的 api，中間的 epoll，右邊是協議棧的回調 (協議棧當然不能直接操作 epoll，中間的 vfs 在此不是重點，就直接省略 vfs 這一層了)。

協議棧觸發回調通知 epoll 的時機

socket 有兩類，一類是監聽 listenfd，一類是客戶端 clientfd。對於 sockfd 而言，我們一般比較關注 EPOLLIN 和 EPOLLOUT 這兩個事件，所以如果是 listenfd，我們通常的做法就是 accept。對於 clientfd 來說，如果可讀我們就 recv，如果可寫我們就 send。

協議棧將數據解析出來觸發回調通知 epoll。epoll 是怎麼知道哪個 io 就緒了呢？我們從 ip 頭可以解析出源 ip，目的 ip 和協議，從 tcp 頭可以解析出源端口和目的端口，此時五元組就湊齊了。socket fd --- <源 IP 地址 , 源端口 , 目的 IP 地址 , 目的端口 , 協議> 一個 fd 就是一個五元組，知道了 fd，我們就能從紅黑樹中找到對應的結點。

那麼這個回調函數做什麼事情呢？我們傳入 fd 和具體事件這兩個參數，然後做下面兩個操作

  1. 通過 fd 找到對應的結點

  2. 把結點加入到就緒隊列

1、協議棧中，在三次握手完成之後，會往全連接隊列中添加一個 TCB 結點，然後觸發一個回調函數，通知到 epoll 裏面有個 EPOLLIN 事件

2、客戶端發送一個數據包，協議棧接收後回覆 ACK，之後觸發一個回調函數，通知到 epoll 裏面有個 EPOLLIN 事件

3、每個連接的 TCB 裏面都有一個 sendbuf，在對端接收到數據並返回 ACK 以後，sendbuf 就可以將這部分確認接收的數據清空，此時 sendbuf 裏面就有剩餘空間，此時觸發一個回調函數，通知到 epoll 裏面有個 EPOLLOUT 事件

4、當對端發送 close，在接收到 fin 後回覆 ACK，此時會調用回調函數，通知到 epoll 有個 EPOLLIN 事件

5、當接收到 rst 標誌位的時候，回覆 ack 之後也會觸發回調函數，通知 epoll 有一個 EPOLLERR 事件

通知的時機總結

一個有 5 個通知的地方

1. 三次握手完成之後2. 接收數據回覆ACK之後3. 發送數據收到ACK之後4. 接收FIN回覆ACK之後 5. 接收RST回覆ACK之後

從回調機制看 epoll 與 select/poll 的區別

由於 select 和 poll 沒有本質的區別，所以下面統一稱爲 poll。

//  poll跟select類似, 其實poll就是把select三個文件描述符集合變成一個集合了。int select(int nfds, fd_set * readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);int poll(struct pollfd *fds, nfds_t nfds, int timeout);

我們看到每次調用 poll，都需要把總集 fds 拷貝到內核態，檢測完之後，再有內核態拷貝的用戶態，這就是 poll。而 epoll 不是這樣，epoll 只要有新的 io 就調用 epoll_ctl() 加入到紅黑樹裏面，一旦有觸發就用 epoll_wait() 將有事件的結點帶出來，可以看到他們的第一個區別：poll 總是拷貝總集，如果有 100w 個 fd，只有兩三個就緒呢？這會造成大量資源浪費；而 epoll 總是將需要拷貝的東西進行拷貝，沒有浪費。

第二個區別：我們從上面知道了 epoll 的事件都是由協議棧進行回調然後加入到就緒隊列的，而 poll 呢？內核如何檢測 poll 的 io 是否就緒？只能通過遍歷的方法判斷，所以 poll 檢測 io 通過遍歷的方法也是比較慢的。

所以兩者的區別：

  1. select/poll 需要把總集 copy 到內核，而 epoll 不用

  2. 實現原理上面，select/poll 需要循環遍歷總集是否有就緒，而 epoll 是那個結點就緒了就加入就緒隊列裏面。

注意：poll 不一定就比 epoll 慢，在 io 量小的情況下，poll 是比 epoll 快的，而在大 io 量下，epoll 絕對是有主導地位的。至於有多少個 io 纔算多，其實也很難說，一般認爲 500 或者 1024 爲分界點（我亂說的） 。

epoll 線程安全如何加鎖

3 個 api 做什麼事情

  1. epoll_create() ===》創建紅黑樹的根節點

  2. epoll_ctl() ===》add,del,mod 增加、刪除、修改結點

  3. epoll_wait() ===》把就緒隊列的結點 copy 到用戶態放到 events 裏面，跟 recv 函數很像

分析加鎖

如果有 3 個線程同時操作 epoll，有哪些地方需要加鎖？我們用戶層面一共就只有 3 個 api 可以使用：

  1. 如果同時調用 epoll_create() ，那就是創建三顆紅黑樹，沒有涉及到資源競爭，沒有關係。

  2. 如果同時調用 epoll_ctl() ，對同一顆紅黑樹進行，增刪改，這就涉及到資源競爭需要加鎖了，此時我們對整棵樹進行加鎖。

  3. 如果同時調用 epoll_wait() ，其操作的是就緒隊列，所以需要對就緒隊列進行加鎖。

我們要扣住 epoll 的工作環境，在應用程序調用 epoll_ctl() ，協議棧會不會有回調操作紅黑樹結點？調用 epoll_wait() copy 出來的時候，協議棧會不會操作操作紅黑樹結點加入就緒隊列？綜上所述：

epoll_ctl() 對紅黑樹加鎖epoll_wait()對就緒隊列加鎖回調函數()   對紅黑樹加鎖,對就緒隊列加鎖

那麼紅黑樹加什麼鎖，就緒隊列加什麼鎖呢？

對於紅黑樹這種節點比較多的時候，採用互斥鎖來加鎖。就緒隊列就跟生產者消費者一樣，結點是從協議棧回調函數來生產的，消費是 epoll_wait() 來消費。那麼對於隊列而言，用自旋鎖（對於隊列而言，插入刪除比較簡單，cpu 自旋等待比讓出的成本更低，所以用自旋鎖）。

ET 與 LT 如何實現

代碼如何實現 ET 和 LT 的效果呢？水平觸發和邊沿觸發不是故意設計出來的，這是自然而然，水到渠成的功能。水平觸發和邊沿觸發代碼只需要改一點點就能實現。從協議棧檢測到接收數據，就調用一次回調，這就是 ET，接收到數據，調用一次回調。而 LT 水平觸發，檢測到 recvbuf 裏面有數據就調用回調。所以 ET 和 LT 就是在使用回調的次數上面的差異。

那麼具體如何實現呢？協議棧流程裏面觸發回調，是天然的符合 ET 只觸發一次的。那麼如果是 LT，在 recv 之後，如果緩衝區還有數據那麼加入到就緒隊列。那麼如果是 LT，在 send 之後，如果緩衝區還有空間那麼加入到就緒隊列。那麼這樣就能實現 LT 了。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ZuqW-SCPZpydjYTl6EvL8g

猜你喜歡