前言

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

epoll的數據結構

多種數據結構進行決策

epoll至少需要兩個集合

所有fd的總集
就緒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()的時候，只需要創建一個紅黑樹樹根即可，無需浪費額外的空間。

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

所有fd的總集 -----> 紅黑樹
就緒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通過遍歷的方法也是比較慢的。

所以兩者的區別：

select/poll需要把總集copy到內核，而epoll不用
實現原理上面，select/poll 需要循環遍歷總集是否有就緒，而epoll是那個結點就緒了就加入就緒隊列里面。

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

epoll線程安全如何加鎖

3個api做什么事情

epoll_create() ===》創建紅黑樹的根節點
epoll_ctl() ===》add,del,mod 增加、刪除、修改結點
epoll_wait() ===》把就緒隊列的結點copy到用戶態放到events里面，跟recv函數很像

分析加鎖

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

如果同時調用 epoll_create() ，那就是創建三顆紅黑樹，沒有涉及到資源競爭，沒有關系。
如果同時調用 epoll_ctl() ，對同一顆紅黑樹進行，增刪改，這就涉及到資源競爭需要加鎖了，此時我們對整棵樹進行加鎖。
如果同時調用epoll_wait() ，其操作的是就緒隊列，所以需要對就緒隊列進行加鎖。

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

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

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

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

ET與LT如何實現

ET邊沿觸發，只觸發一次
LT水平觸發，如果沒有讀完就一直觸發

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

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

審核編輯：湯梓紅