epoll学习报告
kamuszhou 周霄 Jul/26/2013
这几天通读了内核中对epoll I/O模型的实现代码，结合网络上很多介绍epoll的文章，对epoll的实现原理已经很熟悉，下面谈谈我的几点体会。下文引用的内核代码来自3.9.6版本的内核，见URL：http://lxr.oss.org.cn/source/fs/eventpoll.c。
一. epoll的边沿触发(ET)的效率高于电平(LT)触发的效率
首先简单介绍一个背景：epoll实现中，把已经有事件发生的文件用一个双链表链接一起，这个双链表是在struct eventpoll结构中的rdllist域。用户空间调用epoll_wait()，陷入内核后就会立即检查这个双链表，如果链表中非空，就通过文件的poll()函数询问文件有无事件发生。如果有事件发生且是用户关心的，就会向用户空间报告，否则就睡眠。
epoll的实现代码中实际上只有两行代码与触发方式有关，如下图所示。
上图所示的代码运行的上下文情况是：用户加入到epoll中的某个文件，只要支持poll()，(可以是socket，FIFO，裸设备，whatever)有关心的事件到达(或可读，或可写，或报错)，内核空间已经把发生的事件复制到了用户空间，但还没有从内核态返回用户空间。在返回用户空间之前代码检查用被epoll监视的这个文件是否是ET触发，如果不是(那就是LT),就把监视的文件重新放回就绪队列，下次epoll_wait()调用的时候会立即重新检查这个文件有否有事件到达。如果这文件的确有事件发生，则epoll_wait()报告给调用者。如果没有，而且其它被监视的文件也没有事件发生，则调用epoll_wait()的task就让出处理器，开始睡觉(TASK_INTERRUPTIBLE)。这段逻辑在static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events, int maxevents, long timeout)中，第1494行。
如果监听的文件开启的是边沿触发(默认)，则不会执行上图中的list_add_tail()逻辑。这就是边沿触发只会向用户报告一次，直到下一个关心事件发生才向用户空间报告的原因。
那么为什么ET触发效率高于LT触发呢？看一个例子，假如客户端监视一个TCP的Socket，服务端这时发来1M数据，客户端的主机网卡驱动缓存足够大，一次性接收到了所有1M数据。下面看两段客户端的接收伪代码(没有写read调用返回时socket被关闭的情况；另socket描述符fd被设为非阻塞)。
上图的代码使用了LT触发，这段代码依赖epoll_wait()通知还有数据可供读取。所以共调用了1024次epoll_wait()，1024次read()，共2048次系统调用才读完1M数据。
上图使用ET触发，epoll_wait()只报告一次，然后代码循环调用1024次read()读完数据，直到第1025次read()返回-1，出错码为EAGAIN(EAGAIN等于EWOULDBLOCK)，于是代码知道已经接收完数据。一共只使用了1026次系统调用就读完了数据。
总结：即使使用电平触发也不要依赖epoll_wait()通知调用者到达事件，需要循环调用IO函数直到被通知EAGAIN，这样就把epoll_wait()的调用次数降到最低，仅管有可能在下次epoll_wait()时会有可能浪费一次文件的poll()调用，但这个很小的开销可以忽略。
二. 为什么epoll支持嵌套调用
读epoll的实现代码发现，一个epoll的文件描述符epfd可以嵌套的加入另一个epoll。这样有什么用呢？
epoll的实现中“平等的”对待每个被监视的文件，它们维护在一棵红黑树之中，假如有十万个文件被监视，那么查找某个文件时就要在这十万个文件中查找。即使红黑树的查找效率是log(n)，文件非常大时也是比较消耗时间的。
那么假如有这样一种情况，如果这十万个文件中只有1000个是活跃的，或者说这1000个文件优先级最高。那么则有一种优化方案是，创建两个epoll，第一个epoll（epfd0）监控100000 – 1000 个文件，第二个epoll (epfd1) 监控1000个高优先级文件以及epfd0。这样的好处是，大多数情况下epoll实现只在1001个元素的红黑树中查找，自然效率提高了。
总结：epoll的嵌套调用给开发者提供了一个在高并发环境下的优化方案。
三. epoll的效率一定比select/poll高吗。
答案是不一定。
Select的缺点大致有：
1. 内核中写死了最多只能监视1024个文件.
2. 每次调用select都要把关心的文件描述符和关心的文件件从一个用户空间的长长的数组拷贝到内核空间.
3. select若使得caller进程进入睡眠后，某个文件有事件到达此进程被唤醒，那么所有被监视的文件全部会被调用poll()询问“你有没有事件到达”，这是一个线性的时间复杂度。
epoll针对select的三个缺点的改进：
1. 监视的文件数由取决于系统中有多少低端内存(x86_64架构中的所有内存都是低端内存)。3.9.6版本的内核实现中，对于每个登录用户，最多使用系统中低端内存的4%用来创建监视用的数据结构。见第1951行代码。max_user_watches = (((si.totalram – si.totalhigh) / 25) << PAGE_SHIFT) / EP_ITEM_COST;
2. 用户只需要把关心的文件对应的数据结构在调用epoll_wait()前用epoll_ctl()一次性传入内存，以后调用epoll_wait()时不需要像select一样拷贝大量数据。
3. 当调用epoll_wait()的caller进程睡眠时，突然有事件到达，caller进程被唤醒，epoll_wait()返回用户空间，内核并不遍历没有监视的文件，而只报告在一个即短时间内发生的事件。下面更详细的描述这个场景，以监视tcp socket举例，大致是：某进程调用epoll_wait()，此时没有任何它关心的事件发生，于是caller进程进入睡眠。处理器调度了其它进程。数据到达时，当前进程被硬件中断，网卡驱动收到数据包，数据包在中断处理函数中被拷入内核，中断处理函数设置中断下半部(Half Bottom)。下半部被处理器调度，调用epoll实现代码注册的回调函数ep_poll_callback()。ep_poll_callback()函数唤醒之前的caller进程，caller进程重新获得CPU，从epoll实现的ep_poll()函数中恢复执行，在3.9.6内核中的第1564行： if (!schedule_hrtimeout_range(to, slack, HRTIMER_MODE_ABS))。然后，内核代码开始收集已经就绪的文件和发生的事件，发回用户空间。只有从第一次回调函数ep_poll_callback()被驱动的代码调用（caller进程还在睡眠时执行的ep_poll_callback()算第一次）到epoll实现代码走到第586行关闭中断关闭中断的代码 spin_lock_irqsave(&ep->lock, flags);之间发生的事件才会被收集。
对于第3点，这是epoll的优点，但在某种情况下却会是epoll的缺点。网上很多比较poll, select, epoll性能的文章，没来得及仔细看，我个人认为结论是可靠的。结论引入了一个概念active-to-total ratio，设所有被监控的文件数是n，活跃的文件数是m，active-to-total比则是m/n，如果这个比非常高，比如大于0.7，则poll或select的性能要高过epoll，反之则epoll胜出。
对比前文对select的第3个缺点和epoll的改进点3的叙述可以解释这个原因。因为select在返回用户空间前又轮循了所有关心的文件，而这些文件又大部分是有事件发生的，所以select所做的工作并没有浪费，但epoll只收集了一小段时间中发生的事件，于是select较之epoll减少了用户空间和内核空间的频繁切换，从而让select的性能反超epoll。
那么如何改进呢？明白了以上的原因，那么就可以对epoll做出改进，理论上对于active-to-total比较高的应用环境下，可以在epoll的实现中加入与select做法相同逻辑，即退出前询问所有的监控文件，反正active-to-total比很高。或者更好的方案，用一个链表链接活跃的文件，在epoll返回用户空间前遍历这个链表，争取每一个epoll_wait()调用返回尽可能多的事件。
附：epoll的主要数据结构简介.
epoll接口的主要数据结构有struct eventpoll，struct epitem，struct eppoll_entry。
在讲述这三个数据结构前先提一下struct file。Unix设计初期希望它的设计遵从“一切皆文件”的理念。在Linux内核中，每个抽象的文件对应一个内核struct file结构体。Struct file结构体中有一个void *private_data域。不同的文件类型会在private_data域中存放特定的信息。Struct file中另一个域f_op是函数指针的列表，它记录了对应该文件的操作。所有epoll文件的f_op都指向static const struct file_operations eventpoll_fops，因此可以代码判断一个文件是不是epoll如下：
static inline int is_file_epoll(struct file *f)
{
return f->f_op == &eventpoll_fops;
}
每次成功调用epoll_create时就会创建一个struct file的结构体，和一个struct eventpoll。Struct file中的private_data指向struct eventpoll。eventpoll维护了这个epoll的重要信息。其中比较重要的几个字段有：一个循环列表struct list_head rdllist链接了该epll中已经可以读写或者有出错的文件描述符。一个红黑树的根结点struct rb_root rbr，eventpoll维护了一棵红黑树，树中的结点是struct epitem。
每个被加入到epoll中被关注的文件描述符都对应一个struct epitem结构体。所有加入到同一个epoll中对应的所有epitem都挂在红黑树上。该红黑树的根结构保存在struct eventpoll中。epitem中记录了对应的文件的文件描述符和文件指针。
struct eppoll_entry是用来挂接到设备文件中的结构体。设备驱动在得知自己可读或可写或有错误时通过这个结构体通知有事件发生。每个eppoll_entry都指向一个epitem，一个epitem可能对应多个eppoll_entry。eppoll_entry中的域wait_queue_t wait就是被用来挂接到设备文件中的等待队列。设备文件通过wait可以拿到eppoll_entry，再通过eppoll_entry拿到epitem，再拿到eventpoll。