实施 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的实现原理