epoll底层实现

linux内核笔记

为什么使用红黑树？
-- 之前也使用过hash表，之后才改进成了红黑树，为了性能平均？最差的情况下，时间复杂度仍然是可容忍的。

http://www.hulkdev.com/posts/epoll-io
http://www.cnblogs.com/200911/p/7016843.html
https://blog.csdn.net/vividonly/article/details/7539342

epoll底层本身也是reactor模式的体现，于select/poll的最大区别在于其回调函数的实现。

static void ep_ptable_queue_proc(struct file *file, wait_queue_head_t *whead,
                 poll_table *pt)
……
init_waitqueue_func_entry(&pwq->wait, ep_poll_callback);
……
static int ep_poll_callback(wait_queue_t *wait, unsigned mode, int sync, void *key)
{
    list_add_tail(&epi->rdllink, &ep->rdllist);
}

对于epoll系统调用，当poll唤醒等待者时，epoll顺势记录了唤醒者的信息到红黑树。
对于select，它的唤醒函数为

__pollwait--->>>q->func = default_wake_function;
int default_wake_function(wait_queue_t *curr, unsigned mode, int sync,
              void *key)
{
    return try_to_wake_up(curr->private, mode, sync);
}

对于select调用来说，它只是简单的唤醒，很傻很天真，也就是头脑相对比较简单一些，这个简单的代价就是在do_select函数中有一个罕见的三重for循环。

当某一进程调用epoll_create方法时，Linux内核会创建一个eventpoll结构体，这个结构体中有两个成员与epoll的使用方式密切相关。eventpoll结构体如下所示：

struct eventpoll{  
    ....  
    /*红黑树的根节点，这颗树中存储着所有添加到epoll中的需要监控的事件*/  
    struct rb_root  rbr;
    /*双链表中则存放着将要通过epoll_wait返回给用户的满足条件的事件*/  
    struct list_head rdlist;
    ....  
};  

每一个epoll对象都有一个独立的eventpoll结构体，用于存放通过epoll_ctl方法向epoll对象中添加进来的事件。这些事件都会挂载在红黑树中，如此，重复添加的事件就可以通过红黑树而高效的识别出来(红黑树的插入时间效率是lgn，其中n为树的高度)。

而所有添加到epoll中的事件都会与设备(网卡)驱动程序建立回调关系，也就是说，当相应的事件发生时会调用这个回调方法。这个回调方法在内核中叫ep_poll_callback,它会将发生的事件添加到rdlist双链表中。

在epoll中，对于每一个事件，都会建立一个epitem结构体，如下所示：

struct epitem{
    struct rb_node  rbn;//红黑树节点  
    struct list_head    rdllink;//双向链表节点  
    struct epoll_filefd  ffd;  //事件句柄信息  
    struct eventpoll *ep;    //指向其所属的eventpoll对象  
    struct epoll_event event; //期待发生的事件类型  
}

当调用epoll_wait检查是否有事件发生时，只需要检查eventpoll对象中的rdlist双链表中是否有epitem元素即可。如果rdlist不为空，则把发生的事件复制到用户态，同时将事件数量返回给用户。

epoll数据结构示意图

epoll水平触发和边缘触发的实现： 当一个socket句柄上有事件时，内核会把该句柄插入上面所说的准备就绪list链表，这时我们调用epoll_wait，会把准备就绪的socket拷贝到用户态内存，然后清空准备就绪list链表， 最后，epoll_wait干了件事，就是检查这些socket，如果不是ET模式（就是LT模式的句柄了），并且这些socket上确实有未处理的事件时，又把该句柄放回到刚刚清空的准备就绪链表了，所以，非ET的句柄，只要它上面还有事件，epoll_wait每次都会返回。而ET模式的句柄，除非有新中断到，即使socket上的事件没有处理完，也是不会次次从epoll_wait返回的。

惊群问题解决

Epoll 新增 EPOLLEXCLUSIVE 选项解决了新建连接的’惊群‘问题，并没有完全解决，可能还是得依靠应用层

https://zhuanlan.zhihu.com/p/60966989

epoll最终和accept一样解决了新建连接的惊群问题 patch地址：
https://github.com/torvalds/linux/commit/df0108c5da561c66c333bb46bfe3c1fc65905898

在加入listen socket的sk_sleep队列 的唤醒队列里使用了 add_wait_queue_exculsive()函数，当tcp 收到三次握手最后一个 ack 报文时调用sock_def_readable时，只唤醒一个等待源，从而避免惊群。
调用栈如下：

//  tcp_v4_do_rcv()  
//  
//  -->tcp_child_process()  
//  
//  --->sock_def_readable()  
//  
//  ---->wake_up_interruptible_sync_poll()  
//  
//  ----->__wake_up_sync_key() 

https://lwn.net/Articles/667087/

但是在LT模式下如果使用不正确的话，仍然存在惊群的问题。