自己動手實現Epoll

Epoll是Linux IO多路復用的管理機制。作為現在Linux平臺高性能網絡IO必要的組件。內核的實現可以參照：fs/eventpoll.c .

為什么需要自己實現epoll呢？現在自己打算做一個用戶態的協議棧。采用單線程的模式。https://github.com/wangbojing/NtyTcp，至于為什么要實現用戶態協議棧？可以自行百度C10M的問題。

由于協議棧做到了用戶態故需要自己實現高性能網絡IO的管理。所以epoll就自己實現一下。代碼：https://github.com/wangbojing/NtyTcp/blob/master/src/nty_epoll_rb.c

?

在實現epoll之前，先得好好理解內核epoll的運行原理。內核的epoll可以從四方面來理解。

1.????? Epoll的數據結構，rbtree對<fd, event>的存儲，ready隊列存儲就緒io。

2.????? Epoll的線程安全，SMP的運行，以及防止死鎖。

3.????? Epoll內核回調。

4.????? Epoll的LT（水平觸發）與ET（邊沿觸發）

下面從這四個方面來實現epoll。

一、Epoll數據結構

Epoll主要由兩個結構體：eventpoll與epitem。Epitem是每一個IO所對應的的事件。比如 epoll_ctl EPOLL_CTL_ADD操作的時候，就需要創建一個epitem。Eventpoll是每一個epoll所對應的的。比如epoll_create 就是創建一個eventpoll。

Epitem的定義

Eventpoll的定義

數據結構如下圖所示。

List 用來存儲準備就緒的IO。對于數據結構主要討論兩方面：insert與remove。同樣如此，對于list我們也討論insert與remove。何時將數據插入到list中呢？當內核IO準備就緒的時候，則會執行epoll_event_callback的回調函數，將epitem添加到list中。

那何時刪除list中的數據呢？當epoll_wait激活重新運行的時候，將list的epitem逐一copy到events參數中。

Rbtree用來存儲所有io的數據，方便快速通io_fd查找。也從insert與remove來討論。

對于rbtree何時添加：當App執行epoll_ctl EPOLL_CTL_ADD操作，將epitem添加到rbtree中。何時刪除呢？當App執行epoll_ctl EPOLL_CTL_DEL操作，將epitem添加到rbtree中。

List與rbtree的操作又如何做到線程安全，SMP，防止死鎖呢？

?

?

二、Epoll鎖機制

Epoll 從以下幾個方面是需要加鎖保護的。List的操作，rbtree的操作，epoll_wait的等待。

List使用最小粒度的鎖spinlock，便于在SMP下添加操作的時候，能夠快速操作list。

List添加

346行：獲取spinlock。

347行：epitem 的rdy置為1，代表epitem已經在就緒隊列中，后續再觸發相同事件就只需更改event。

348行：添加到list中。

349行：將eventpoll的rdnum域 加1。

350行：釋放spinlock

?

List刪除

301行：獲取spinlock

304行：判讀rdnum與maxevents的大小，避免event溢出。

307行：循環遍歷list，判斷添加list不能為空

309行：獲取list首個結點

310行：移除list首個結點。

311行：將epitem的rdy域置為0，標識epitem不再就緒隊列中。

313行：copy epitem的event到用戶空間的events。

316行：copy數量加1

317行：eventpoll中rdnum減一。

避免SMP體系下，多核競爭。此處采用自旋鎖，不適合采用睡眠鎖。

?

Rbtree的添加

149行：獲取互斥鎖。

153行：查找sockid的epitem是否存在。存在則不能添加，不存在則可以添加。

160行：分配epitem。

167行：sockid賦值

168行：將設置的event添加到epitem的event域。

170行：將epitem添加到rbrtree中。

173行：釋放互斥鎖。

?

Rbtree刪除：

177行：獲取互斥鎖。

181行：刪除sockid的結點，如果不存在，則rbtree返回-1。

188行：釋放epitem

190行：釋放互斥鎖。

?

Epoll_wait的掛起。

采用pthread_cond_wait，具體實現可以參照。

https://github.com/wangbojing/NtyTcp/blob/master/src/nty_epoll_rb.c

?

?

三、Epoll回調

Epoll 的回調函數何時執行，此部分需要與Tcp的協議棧一起來闡述。Tcp協議棧的時序圖如下圖所示，epoll從協議棧回調的部分從下圖的編號1,2,3,4。具體Tcp協議棧的實現，后續從另外的文章中表述出來。下面分別對四個步驟詳細描述

編號1：是tcp三次握手，對端反饋ack后，socket進入rcvd狀態。需要將監聽socket的event置為EPOLLIN，此時標識可以進入到accept讀取socket數據。

編號2：在established狀態，收到數據以后，需要將socket的event置為EPOLLIN狀態。

編號3：在established狀態，收到fin時，此時socket進入到close_wait。需要socket的event置為EPOLLIN。讀取斷開信息。

編號4：檢測socket的send狀態，如果對端cwnd>0是可以，發送的數據。故需要將socket置為EPOLLOUT。

所以在此四處添加EPOLL的回調函數，即可使得epoll正常接收到io事件。

四、LT與ET

LT（水平觸發）與ET（邊沿觸發）是電子信號里面的概念。不清楚可以man epoll查看的。如下圖所示：

比如：event = EPOLLIN | EPOLLLT，將event設置為EPOLLIN與水平觸發。只要event為EPOLLIN時就能不斷調用epoll回調函數。

比如: event = EPOLLIN | EPOLLET，event如果從EPOLLOUT變化為EPOLLIN的時候，就會觸發。在此情形下，變化只發生一次，故只調用一次epoll回調函數。關于水平觸發與邊沿觸發放在epoll回調函數執行的時候，如果為EPOLLET（邊沿觸發），與之前的event對比，如果發生改變則調用epoll回調函數，如果為EPOLLLT（水平觸發），則查看event是否為EPOLLIN，即可調用epoll回調函數。

BAT， 滴滴，今日頭條，美圖，美團等一線內推 技術崗位內推?

QQ群：935760465