epoll 可以说是和 poll 非常相似的一种 I/O 多路复用技术，epoll 通过监控注册的多个描述字，来进行 I/O 事件的分发处理。不同于 poll 的是，epoll 不仅提供了默认的 level-triggered（条件触发）机制，还提供了性能更为强劲的 edge-triggered（边缘触发）机制。

工作流程

用户进程调用epoll_create;
内核创建readyList，红黑树;
用户进程调用epoll_ctrl，传递监控的句柄(如Socket)，以及在上面关注的事件;
内核将句柄插入红黑树;
内核的中断处理程序注册一个回调，如果红黑树中某个句柄的中断到了，把它对应的事件放到ReadyList。

— 另一个流程 —

用户进程调用epoll_wait
内核从ReadyList返回可回调的事件。

epoll用法

使用 epoll 进行网络程序的编写，需要三个步骤，分别是 epoll_create，epoll_ctl 和 epoll_wait。

epoll_create

1
2
3


int epoll_create(int size);
int epoll_create1(int flags);
//  返回值: 若成功返回一个大于0的值，表示epoll实例；若返回-1表示出错

epoll_create() 方法创建了一个 epoll 实例，从 Linux 2.6.8 开始，参数 size 被自动忽略，但是该值仍需要一个大于 0 的整数。这个 epoll 实例被用来调用 epoll_ctl 和 epoll_wait，如果这个 epoll 实例不再需要，比如服务器正常关机，需要调用 close() 方法释放 epoll 实例，这样系统内核可以回收 epoll 实例所分配使用的内核资源。

参数 size，在一开始的 epoll_create 实现中，是用来告知内核期望监控的文件描述字大小，然后内核使用这部分的信息来初始化内核数据结构。在新的实现中，这个参数不再被需要，因为内核可以动态分配需要的内核数据结构。我们只需要注意，每次将 size 设置成一个大于 0 的整数就可以了。

epoll_create1() 的用法和 epoll_create() 基本一致，如果 epoll_create1() 的输入 flags 为 0，则和 epoll_create() 一样，内核自动忽略。可以增加如 EPOLL_CLOEXEC 的额外选项。

epoll_ctl

1
2


int epoll_ctl(int epfd， int op， int fd， struct epoll_event *event);
//  返回值: 若成功返回0；若返回-1表示出错

在创建完 epoll 实例之后，可以通过调用 epoll_ctl 往这个 epoll 实例增加或删除监控的事件。

第一个参数 epfd 是刚刚调用 epoll_create 创建的 epoll 实例描述字，可以简单理解成是 epoll 句柄。
第二个参数表示增加还是删除一个监控事件，它有三个选项可供选择：
- EPOLL_CTL_ADD：向 epoll 实例注册文件描述符对应的事件。
- EPOLL_CTL_DEL：向 epoll 实例删除文件描述符对应的事件。
- EPOLL_CTL_MOD：修改文件描述符对应的事件。
第三个参数是注册的事件的文件描述符，比如一个监听套接字。
第四个参数表示的是注册的事件类型，并且可以在这个结构体里设置用户需要的数据，其中最为常见的是使用联合结构里的 fd 字段，表示事件所对应的文件描述符。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


typedef union epoll_data {
     void        *ptr;
     int          fd;
     uint32_t     u32;
     uint64_t     u64;
 } epoll_data_t;
 
 struct epoll_event {
     uint32_t     events;      /* Epoll events */
     epoll_data_t data;        /* User data variable */
 };

这里 epoll 使用了和 poll 同样的 mask 数据类型机制，重要的几种事件类型有：

EPOLLIN：表示对应的文件描述字可以读；
EPOLLOUT：表示对应的文件描述字可以写；
EPOLLRDHUP：表示套接字的一端已经关闭，或者半关闭；
EPOLLHUP：表示对应的文件描述字被挂起；
EPOLLET：设置为 edge-triggered，默认为 level-triggered。

epoll_wait

1
2


int epoll_wait(int epfd， struct epoll_event *events， int maxevents， int timeout);
//  返回值: 成功返回的是一个大于0的数，表示事件的个数；返回0表示的是超时时间到；若出错返回-1。

epoll_wait() 函数类似之前的 poll 和 select 函数，调用者进程被挂起，在等待内核 I/O 事件的分发。

第一个参数是 epoll 实例描述字，也就是 epoll 句柄。

第二个参数返回给用户空间需要处理的 I/O 事件，这是一个数组，数组的大小由 epoll_wait 的返回值决定，这个数组的每个元素都是一个需要待处理的 I/O 事件，其中 events 表示具体的事件类型，事件类型取值和 epoll_ctl 可设置的值一样，这个 epoll_event 结构体里的 data 值就是在 epoll_ctl 那里设置的 data，也就是用户空间和内核空间调用时需要的数据。

第三个参数是一个大于 0 的整数，表示 epoll_wait 可以返回的最大事件值。

edge-triggered VS level-triggered

两者的区别，条件触发（level-triggered）的意思是只要满足事件的条件，比如有数据需要读，就一直不断地把这个事件传递给用户；而边缘触发（edge-triggered）的意思是只有第一次满足条件的时候才触发，之后就不会再传递同样的事件了。一般我们认为，边缘触发的效率比条件触发的效率要高，这一点也是 epoll 的杀手锏之一。

epoll 的性能优于 select 和 poll 的原因

第一个方面是事件集合。每次使用 poll 或 select 之前，都需要准备一个感兴趣的事件集合，系统内核拿到事件集合，进行分析并在内核空间构建相应的数据结构来完成对事件集合的注册。而 epoll 则不是这样，epoll 维护了一个全局的事件集合，通过 epoll 句柄，可以操纵这个事件集合，增加、删除或修改这个事件集合里的某个元素。要知道在绝大多数情况下，事件集合的变化没有那么的大，这样操纵系统内核就不需要每次重新扫描事件集合，构建内核空间数据结构。

第二个方面是就绪列表。每次在使用 poll 或者 select 之后，应用程序都需要扫描整个感兴趣的事件集合，从中找出真正活动的事件，这个列表如果增长到 10K 以上，每次扫描的时间损耗也是惊人的。事实上，很多情况下扫描完一圈，可能发现只有几个真正活动的事件。而 epoll 则不是这样，epoll 返回的直接就是活动的事件列表，应用程序减少了大量的扫描时间。

此外， epoll 还提供了更高级的能力——边缘触发。举一个例子说明一下。如果某个套接字有 100 个字节可以读，边缘触发（edge-triggered）和条件触发（level-triggered）都会产生 read ready notification 事件，如果应用程序只读取了 50 个字节，边缘触发就会陷入等待；而条件触发则会因为还有 50 个字节没有读取完，不断地产生 read ready notification 事件。在条件触发下（level-triggered），如果某个套接字缓冲区可以写，会无限次返回 write ready notification 事件，在这种情况下，如果应用程序没有准备好，不需要发送数据，仍需要解除套接字上的 ready notification 事件，否则 CPU 就直接跪了。

为什么用红黑树？

关于为什么要红黑树，考虑到中间观察者最核心的诉求有两个。

第一个核心诉求，是让线程可以注册自己关心的消息类型。

比如线程对文件描述符 =123 的 Socket 文件读写都感兴趣，会去中间观察者处注册。当 FD=123 的 Socket 发生读写时，中间观察者负责通知线程，这是一个响应式的模型。

第二个核心诉求，是当 FD=123 的 Socket 发生变化（读写等）时，能够快速地判断是哪个线程需要知道这个消息

所以，中间观察者需要一个快速能插入（注册过程）、查询（通知过程）一个整数的数据结构，这个整数就是 Socket 的文件描述符。综合来看，能够解决这个问题的数据结构中属于是一个Map接口，候选实现:

哈希表 O(1)
红黑树 O(lgn)
跳表近似O(lgn)

据说老版本的内核和FreeBSD的Kqueue使用的是哈希表。

个人理解现在内核使用红黑树的原因:

哈希表：空间因素，可伸缩性。

频繁增删，哈希表需要预估空间大小，这个场景下无法做到。间接影响响应时间，假如要resize，原来的数据还得移动。即使用了一致性哈希算法，也难以满足非阻塞的timeout时间限制。(时间不稳定)
百万级连接，哈希表有镂空的空间，太浪费内存。

跳表：慢于红黑树，空间也高。

红黑树：经验判断，内核的其他地方如防火墙也使用红黑树，实践上看性能最优。

Epoll 简介

Contents