epoll 的实现原理

前言

本文以四个方面介绍 epoll 的实现原理，

1.epoll 的数据结构；

2.协议栈如何与 epoll 通信；

3.epoll 线程安全如何加锁；

4.ET 与 LT 的实现。

(epoll 实际上在 500 个以上效率就会比 select 还有 poll 高，书上说的是 1024.)

epoll 的数据结构

两个数据结构红黑树和队列

我们知道 epoll 是用来监听 fd 的，那么其底层的数据结构是怎么样的呢？我们要知道 epoll 在使用的时候 fd 主要就分为两个集合，一个是就绪状态 fd 的集合，一个是所有 fd 的集合，这两种集合有着不同的数据结构来操控

让我们想想我们经常使用的微信，平时是聊天的时候多还是不聊天的时候多。聊天的时候就相当于有信息发送给服务器了，这个用户的 fd 就处于就绪状态需要服务器来进行响应，不发消息手机放着的时候就是空闲状态 fd。根据微信我们就能知道，就绪集合的 fd 是少很多的。

对于有很多 fd 的所有 fd 的集合,我们需要快速的查找并且不造成过多的资源浪费，所以使用的数据结构是红黑树，不仅查找的速度快，而且内存的大小也是可以根据结点的多少来决定。

&emdp; 那这个就绪集合需要什么数据结构来操作呢？就绪集合的每个 fd 都需要处理不需要查找，没法确定具体 fd 的多少所以不能使用数组。那就是链式结构，链式结构分为两种一种是队列，一种是栈。使用的是队列，为什么不用栈呢？你可以想象一下，先是五个客户端有数据需要你处理，你用的是栈的数据结构，先处理了四个之后又来了五个，那就又从栈顶开始处理，栈底的就很晚才处理了。为了公平起见，采用先进先出的队列，先就绪的先处理。

两个数据结构之间的关系

epoll 有两个结构体，一个是 eventpoll 还有一个是 epitem。

• epoll_create 就是创建一个 eventpoll。

• epitem 是每一个 IO 所对应的的事件，epoll_ctl EPOLL_CTL_ADD 操作的时候，就需要创建一个 epitem。

  可以通过内核源码位置 fs/epollevent.c 查看源代码（内核代码在/usr/src/linux 目录下，自己电脑中的源代码应该是被编译成了库，自己的电脑上是找不到的）,可以通过这个网站查看源码点击这里。

eventpoll 的结构体中就有 rbr 指向红黑树的根节点，rdlist 指向链表的头节点。 &emdp; 红黑树的结点和就绪队列的结点的同一个节点，所谓的加入就绪队列，就是将结点的前后指针联系到一起。所以就绪了不是将红黑树结点 delete 掉然后加入队列。他们是同一个结点，不需要 delete。

​协议栈如何与 epoll 通信

当一个 io 准备就绪的时候，是由协议栈将数据解析出来触发回调通知 epoll 的。

epoll 是怎么知道哪个 io 就绪了呢？我们从 ip 头可以解析出源 ip，目的 ip 和协议，从 tcp 头可以解析出源端口和目的端口，此时五元组就凑齐了。socket fd --- < 源 IP 地址 , 源端口 , 目的 IP 地址 , 目的端口 , 协议 > 一个 fd 就是一个五元组，知道了 fd，我们就能从红黑树中找到对应的结点。

通知的时机一共有五个地方：

1. 三次握手完成之后2. 接收数据回复ACK之后3. 发送数据收到ACK之后4. 接收FIN回复ACK之后 5. 接收RST回复ACK之后

时机一

  协议栈中，在三次握手完成之后，会往全连接队列中添加一个 TCB 结点，然后触发一个回调函数，通知到 epoll 里面有个 EPOLLIN 事件。

时机二

  客户端发送一个数据包，协议栈接收后回复 ACK，之后触发一个回调函数，通知到 epoll 里面有个 EPOLLIN 事件。

时机三

每个连接的 TCB 里面都有一个 sendbuf，在对端接收到数据并返回 ACK 以后，sendbuf 就可以将这部分确认接收的数据清空，此时 sendbuf 里面就有剩余空间，此时触发一个回调函数，通知到 epoll 里面有个 EPOLLOUT 事件。

时机四

当对端发送 close，在接收到 fin 后回复 ACK，此时会调用回调函数，通知到 epoll 有个 EPOLLIN 事件。

时机五

当接收到 rst 标志位的时候，回复 ack 之后也会触发回调函数，通知 epoll 有一个 EPOLLERR 事件。

epoll 和 poll 与 select 的区别

  select 和 poll 没有本质的区别，poll 跟 select 类似, 其实 poll 就是把 select 三个文件描述符集合变成一个集合了。下面将 select 和 poll 统称为了 poll。

  每次调用 poll，都需要把总集 fds 拷贝到内核态，检测完之后，再有内核态拷贝到用户态，这就是 poll。epoll 是只要有新的 io 就调用 epoll_ctl()加入到红黑树里面，一旦有触发就用 epoll_wait()将有事件的结点带出来。

  区别一：poll 总是拷贝总集，如果 fd 很多，但是就绪的只有一点点，就会造成大量的资源浪费，而 epoll 只会将需要拷贝的拷贝。poll 全拷贝出来之后也需要循环判断每一个是否就绪，而 epoll 的队列所有都是就绪的，所以 epoll 拷贝需要拷贝的节省很多。

  区别二：我们从上面知道了 epoll 的事件都是由协议栈进行回调然后加入到就绪队列的，而 poll 呢？内核如何检测 poll 的 io 是否就绪？只能通过遍历的方法判断，所以 poll 检测 io 通过遍历的方法也是比较慢的。

  不要看 poll 内核态和用户态都是靠遍历的方式就觉得 poll 一定比 epoll 慢，在 io 量小的情况下，poll 是比 epoll 快的，在大量 io 的情况下，才是 epoll 的主场。至于有多少个 io 才算多，其实也很难说，一般认为 500 或者 1024 为分界点。

epoll 线程安全如何加锁

   如果有 3 个线程同时操作 epoll，有哪些地方需要加锁？我们用户层面一共就只有 3 个 api 可以使用。

  如果同时调用 epoll_ctl() ，对同一颗红黑树进行，增删改，这就涉及到资源竞争需要加锁了，此时我们对整棵树进行加锁。

  如果同时调用 epoll_wait() ，其操作的是就绪队列，所以需要对就绪队列进行加锁。

  在应用程序调用 epoll_ctl() ，协议栈有可能回调操作红黑树结点。调用 epoll_wait() copy 出来的时候，协议栈有可能操作红黑树结点加入就绪队列。 综上所述：

1.epoll_ctl() 对红黑树加锁2.epoll_wait()对就绪队列加锁3.回调函数()   对红黑树加锁,对就绪队列加锁

  对于红黑树这种节点比较多的时候，采用互斥锁来加锁。对于队列而言，插入删除比较简单，cpu 自旋等待比让出的成本更低，所以用自旋锁。

ET 与 LT 如何实现

ET边沿触发，只触发一次LT水平触发，如果没有读完就一直触发

水平触发和边沿触发不是故意设计出来的，这是自然而然，水到渠成的功能。水平触发和边沿触发代码只需要改一点点就能实现。从协议栈检测到接收数据，就调用一次回调加入到就绪队列，这就是 ET。而 LT 水平触发，检测到 recvbuf 里面有数据就调用回调加入就绪队列，如果还有数据就再调用回调加入到就绪队列。所以 ET 和 LT 就是在使用回调的次数上面的差异。（ET 是纯天然的只触发一次，而 LT 是经过一点点代码修改的）。

原文地址：epoll的实现原理 - 掘金