前言

本文以四個(gè)方面介紹epoll的實(shí)現(xiàn)原理，1.epoll的數(shù)據(jù)結(jié)構(gòu)；2.協(xié)議棧如何與epoll通信；3.epoll線程安全如何加鎖；4.ET與LT的實(shí)現(xiàn)。

epoll的數(shù)據(jù)結(jié)構(gòu)

多種數(shù)據(jù)結(jié)構(gòu)進(jìn)行決策

epoll至少需要兩個(gè)集合

1. 所有fd的總集

2. 就緒fd的集合

那么這個(gè)總集選用什么數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)呢？我們知道，一個(gè)fd，其底層對(duì)應(yīng)一個(gè)TCB。那么也就是說(shuō)key=fd,val=TCB,是一個(gè)典型的kv型數(shù)據(jù)結(jié)構(gòu)，對(duì)于kv型數(shù)據(jù)結(jié)構(gòu)我們可以使用以下三種進(jìn)行存儲(chǔ)。

1. hash2. 紅黑樹(shù)3. b/b+tree

如果使用hash進(jìn)行存儲(chǔ)，其優(yōu)點(diǎn)是查詢(xún)速度很快，O(1)。但是在我們調(diào)用epoll_create()的時(shí)候，hash底層的數(shù)組創(chuàng)建多大合適呢？如果我們有百萬(wàn)的fd，那么這個(gè)數(shù)組越大越好，如果我們僅僅十幾個(gè)fd需要管理，在創(chuàng)建數(shù)組的時(shí)候，太大的空間就很浪費(fèi)。而這個(gè)fd我們又不能預(yù)先知道有多少，所以hash是不合適的。

b/b+tree是多叉樹(shù)，一個(gè)結(jié)點(diǎn)可以存多個(gè)key，主要是用于降低層高，用于磁盤(pán)索引的，所以在我們這個(gè)內(nèi)存場(chǎng)景下也是不適合的。

在內(nèi)存索引的場(chǎng)景下我們一般使用紅黑樹(shù)來(lái)作為首選的數(shù)據(jù)結(jié)構(gòu)，首先紅黑樹(shù)的查找速度很快,O(log(N))。其次在調(diào)用epoll_create()的時(shí)候，只需要?jiǎng)?chuàng)建一個(gè)紅黑樹(shù)樹(shù)根即可，無(wú)需浪費(fèi)額外的空間。

那么就緒集合用什么數(shù)據(jù)結(jié)構(gòu)呢，首先就緒集合不是以查找為主的，就緒集合的作用是將里面的元素拷貝給用戶進(jìn)行處理，所以集合里的元素沒(méi)有優(yōu)先級(jí)，那么就可以采用線性的數(shù)據(jù)結(jié)構(gòu)，使用隊(duì)列來(lái)存儲(chǔ)，先進(jìn)先出，先就緒的先處理。

1. 所有fd的總集 -----> 紅黑樹(shù)

2. 就緒fd的集合 -----> 隊(duì)列

紅黑樹(shù)和就緒隊(duì)列的關(guān)系

紅黑樹(shù)的結(jié)點(diǎn)和就緒隊(duì)列的結(jié)點(diǎn)的同一個(gè)節(jié)點(diǎn)，所謂的加入就緒隊(duì)列，就是將結(jié)點(diǎn)的前后指針聯(lián)系到一起。所以就緒了不是將紅黑樹(shù)結(jié)點(diǎn)delete掉然后加入隊(duì)列。他們是同一個(gè)結(jié)點(diǎn)，不需要delete。

協(xié)議棧如何與epoll模塊通信

epoll的工作環(huán)境

應(yīng)用程序只能通過(guò)三個(gè)api接口來(lái)操作epoll。當(dāng)一個(gè)io準(zhǔn)備就緒的時(shí)候，epoll是怎么知道io準(zhǔn)備就緒了呢？是由協(xié)議棧將數(shù)據(jù)解析出來(lái)觸發(fā)回調(diào)通知epoll的。也就是說(shuō)可以把epoll的工作環(huán)境看出三部分，左邊應(yīng)用程序的api，中間的epoll，右邊是協(xié)議棧的回調(diào)(協(xié)議棧當(dāng)然不能直接操作epoll，中間的vfs在此不是重點(diǎn)，就直接省略vfs這一層了)。

協(xié)議棧觸發(fā)回調(diào)通知epoll的時(shí)機(jī)

socket有兩類(lèi)，一類(lèi)是監(jiān)聽(tīng)listenfd，一類(lèi)是客戶端clientfd。對(duì)于sockfd而言，我們一般比較關(guān)注EPOLLIN和EPOLLOUT這兩個(gè)事件，所以如果是listenfd，我們通常的做法就是accept。對(duì)于clientfd來(lái)說(shuō)，如果可讀我們就recv，如果可寫(xiě)我們就send。

協(xié)議棧將數(shù)據(jù)解析出來(lái)觸發(fā)回調(diào)通知epoll。epoll是怎么知道哪個(gè)io就緒了呢？我們從ip頭可以解析出源ip，目的ip和協(xié)議，從tcp頭可以解析出源端口和目的端口，此時(shí)五元組就湊齊了。socket fd --- < 源IP地址 , 源端口 , 目的IP地址 , 目的端口 , 協(xié)議 > 一個(gè)fd就是一個(gè)五元組，知道了fd，我們就能從紅黑樹(shù)中找到對(duì)應(yīng)的結(jié)點(diǎn)。

那么這個(gè)回調(diào)函數(shù)做什么事情呢？我們傳入fd和具體事件這兩個(gè)參數(shù)，然后做下面兩個(gè)操作

1. 通過(guò)fd找到對(duì)應(yīng)的結(jié)點(diǎn)

2. 把結(jié)點(diǎn)加入到就緒隊(duì)列

1、協(xié)議棧中，在三次握手完成之后，會(huì)往全連接隊(duì)列中添加一個(gè)TCB結(jié)點(diǎn)，然后觸發(fā)一個(gè)回調(diào)函數(shù)，通知到epoll里面有個(gè)EPOLLIN事件

2、客戶端發(fā)送一個(gè)數(shù)據(jù)包，協(xié)議棧接收后回復(fù)ACK，之后觸發(fā)一個(gè)回調(diào)函數(shù)，通知到epoll里面有個(gè)EPOLLIN事件

3、每個(gè)連接的TCB里面都有一個(gè)sendbuf，在對(duì)端接收到數(shù)據(jù)并返回ACK以后，sendbuf就可以將這部分確認(rèn)接收的數(shù)據(jù)清空，此時(shí)sendbuf里面就有剩余空間，此時(shí)觸發(fā)一個(gè)回調(diào)函數(shù)，通知到epoll里面有個(gè)EPOLLOUT事件

4、當(dāng)對(duì)端發(fā)送close，在接收到fin后回復(fù)ACK，此時(shí)會(huì)調(diào)用回調(diào)函數(shù)，通知到epoll有個(gè)EPOLLIN事件

5、當(dāng)接收到rst標(biāo)志位的時(shí)候，回復(fù)ack之后也會(huì)觸發(fā)回調(diào)函數(shù)，通知epoll有一個(gè)EPOLLERR事件

通知的時(shí)機(jī)總結(jié)

一個(gè)有5個(gè)通知的地方

1. 三次握手完成之后2. 接收數(shù)據(jù)回復(fù)ACK之后3. 發(fā)送數(shù)據(jù)收到ACK之后4. 接收FIN回復(fù)ACK之后 5. 接收RST回復(fù)ACK之后

從回調(diào)機(jī)制看epoll 與 select/poll的區(qū)別

由于select和poll沒(méi)有本質(zhì)的區(qū)別，所以下面統(tǒng)一稱(chēng)為poll。

//  poll跟select類(lèi)似, 其實(shí)poll就是把select三個(gè)文件描述符集合變成一個(gè)集合了。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);

我們看到每次調(diào)用poll，都需要把總集fds拷貝到內(nèi)核態(tài)，檢測(cè)完之后，再有內(nèi)核態(tài)拷貝的用戶態(tài)，這就是poll。而epoll不是這樣，epoll只要有新的io就調(diào)用epoll_ctl()加入到紅黑樹(shù)里面，一旦有觸發(fā)就用epoll_wait()將有事件的結(jié)點(diǎn)帶出來(lái)，可以看到他們的第一個(gè)區(qū)別：poll總是拷貝總集，如果有100w個(gè)fd，只有兩三個(gè)就緒呢？這會(huì)造成大量資源浪費(fèi)；而epoll總是將需要拷貝的東西進(jìn)行拷貝，沒(méi)有浪費(fèi)。

第二個(gè)區(qū)別：我們從上面知道了epoll的事件都是由協(xié)議棧進(jìn)行回調(diào)然后加入到就緒隊(duì)列的，而poll呢？?jī)?nèi)核如何檢測(cè)poll的io是否就緒？只能通過(guò)遍歷的方法判斷，所以poll檢測(cè)io通過(guò)遍歷的方法也是比較慢的。

所以?xún)烧叩膮^(qū)別：

1. select/poll需要把總集copy到內(nèi)核，而epoll不用

2. 實(shí)現(xiàn)原理上面，select/poll 需要循環(huán)遍歷總集是否有就緒，而epoll是那個(gè)結(jié)點(diǎn)就緒了就加入就緒隊(duì)列里面。

注意：poll不一定就比epoll慢，在io量小的情況下，poll是比epoll快的，而在大io量下，epoll絕對(duì)是有主導(dǎo)地位的。至于有多少個(gè)io才算多，其實(shí)也很難說(shuō)，一般認(rèn)為500或者1024為分界點(diǎn)（我亂說(shuō)的） 。

epoll線程安全如何加鎖

3個(gè)api做什么事情

1. epoll_create() ===》創(chuàng)建紅黑樹(shù)的根節(jié)點(diǎn)

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

3. epoll_wait() ===》把就緒隊(duì)列的結(jié)點(diǎn)copy到用戶態(tài)放到events里面，跟recv函數(shù)很像

分析加鎖

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

1. 如果同時(shí)調(diào)用 epoll_create() ，那就是創(chuàng)建三顆紅黑樹(shù)，沒(méi)有涉及到資源競(jìng)爭(zhēng)，沒(méi)有關(guān)系。

2. 如果同時(shí)調(diào)用 epoll_ctl() ，對(duì)同一顆紅黑樹(shù)進(jìn)行，增刪改，這就涉及到資源競(jìng)爭(zhēng)需要加鎖了，此時(shí)我們對(duì)整棵樹(shù)進(jìn)行加鎖。

3. 如果同時(shí)調(diào)用epoll_wait() ，其操作的是就緒隊(duì)列，所以需要對(duì)就緒隊(duì)列進(jìn)行加鎖。

我們要扣住epoll的工作環(huán)境，在應(yīng)用程序調(diào)用 epoll_ctl() ，協(xié)議棧會(huì)不會(huì)有回調(diào)操作紅黑樹(shù)結(jié)點(diǎn)？調(diào)用epoll_wait() copy出來(lái)的時(shí)候，協(xié)議棧會(huì)不會(huì)操作操作紅黑樹(shù)結(jié)點(diǎn)加入就緒隊(duì)列？綜上所述：

epoll_ctl() 對(duì)紅黑樹(shù)加鎖epoll_wait()對(duì)就緒隊(duì)列加鎖回調(diào)函數(shù)()   對(duì)紅黑樹(shù)加鎖,對(duì)就緒隊(duì)列加鎖

那么紅黑樹(shù)加什么鎖，就緒隊(duì)列加什么鎖呢？

對(duì)于紅黑樹(shù)這種節(jié)點(diǎn)比較多的時(shí)候，采用互斥鎖來(lái)加鎖。就緒隊(duì)列就跟生產(chǎn)者消費(fèi)者一樣，結(jié)點(diǎn)是從協(xié)議棧回調(diào)函數(shù)來(lái)生產(chǎn)的，消費(fèi)是epoll_wait()來(lái)消費(fèi)。那么對(duì)于隊(duì)列而言，用自旋鎖（對(duì)于隊(duì)列而言，插入刪除比較簡(jiǎn)單，cpu自旋等待比讓出的成本更低，所以用自旋鎖）。

ET與LT如何實(shí)現(xiàn)

• ET邊沿觸發(fā)，只觸發(fā)一次

• LT水平觸發(fā)，如果沒(méi)有讀完就一直觸發(fā)

代碼如何實(shí)現(xiàn)ET和LT的效果呢？水平觸發(fā)和邊沿觸發(fā)不是故意設(shè)計(jì)出來(lái)的，這是自然而然，水到渠成的功能。水平觸發(fā)和邊沿觸發(fā)代碼只需要改一點(diǎn)點(diǎn)就能實(shí)現(xiàn)。從協(xié)議棧檢測(cè)到接收數(shù)據(jù)，就調(diào)用一次回調(diào)，這就是ET，接收到數(shù)據(jù)，調(diào)用一次回調(diào)。而LT水平觸發(fā)，檢測(cè)到recvbuf里面有數(shù)據(jù)就調(diào)用回調(diào)。所以ET和LT就是在使用回調(diào)的次數(shù)上面的差異。

那么具體如何實(shí)現(xiàn)呢？協(xié)議棧流程里面觸發(fā)回調(diào)，是天然的符合ET只觸發(fā)一次的。那么如果是LT，在recv之后，如果緩沖區(qū)還有數(shù)據(jù)那么加入到就緒隊(duì)列。那么如果是LT，在send之后，如果緩沖區(qū)還有空間那么加入到就緒隊(duì)列。那么這樣就能實(shí)現(xiàn)LT了。

審核編輯：湯梓紅