EPOLL内核源代码实现原理分析
转自http://www.blog.chinaunix.net/uid-26339466-id-3292595.html
epoll的实现主要依赖于一个迷你文件系统：eventpollfs。此文件系统通过eventpoll_init初始化。 在初始化的过程中，eventpollfs create两个slub分别是：epitem和eppoll_entry。
epoll使用过程中有几个基本的函数分别是｀epoll_create｀，｀epoll_ctl｀，｀epoll_wait｀。 涉及到四个重要的数据结构： struct eventpoll ， struct epitem， struct epoll_event ， struct eppoll_entry。
1、epoll_create和epoll_ctl
其中eventpoll是通过epoll_create生成，epoll_create传入一个size参数，size参数只要>0即可， 没有任何意义。epoll_create调用函数sys_epoll_create1实现eventpoll的初始化。 sys_epoll_create1通过ep_alloc生成一个eventpoll对象，并初始化eventpoll的三个等待队列， wait，poll_wait以及rdlist （ready的fd list）。同时还会初始化被监视fs的rbtree 根节点。
epollcreate在调用ep_alloc通过anon_inode_getfd创建一个名字为“[eventpoll]”的eventpollfs 文件描述符号并将file->private_data指定为指向前面生成的eventpoll。这样就将eventpoll和 文件id关联。最后返回文件描述符id。
通过epoll_create生成一个eventpoll后，可以通过epoll_ctl提供的相关操作对eventpoll进行ADD，
MOD，DEL操作。epoll_ctl有四个参数，分别是：int epfd（需要操作的eventpoll）, int op
（操作类型）, int fd（需要被监视的文件）, struct epoll_event *event（被监视文件的相关event）。
epoll_ctl首先通过epfd的private_data域获取需要操作的eventpoll，然后通过ep_find确认需要
操作的fd是否已经在被监视的红黑树中（eventpoll->rbr）。然后根据op的类型分别作ADD（ep_insert),
MOD（ep_modify），DEL（ep_remove）操作。
首先分析ep_insert，ep_insert有四个参数分别为： struct eventpoll *ep
（需要操作的eventpoll）, struct epoll_event *event（epoll_create传入的event参数，
当然得从user空间拷贝过来）, struct file *tfile（被监视的文件描述符）, int fd
（被监视的文件id）。ep_insert首先从slub中分配一个epitem的对象epi。并初始化epitem的三个list
头指针，rdllink（指向eventpoll的rdlist），fllist指向（struct file的f_ep_links），
pwqlist（指向包含此epitem的所有poll wait queue）。
并将epitem的ep指针，指向传入的eventpoll，并通过传入参数event对ep内部变量event赋值。
然后通过ep_set_ffd将目标文件和epitem关联。这样epitem本身就完成了和eventpoll以及被监视文件的关联。
下面还需要做两个动作：将epitem插入目标文件的polllist并注册回调函数；将epitem插入eventpoll的rbtree。
为了完成第一个动作，还需要一个数据结构ep_pqueue帮忙，ep_pqueue主要包含两个变量一个是epitem 还有一个是callback函数（ep_ptable_queue_proc）相关的一个数据结构poll_table，ep_pqueue 主要完成epitem和callback函数的关联。然后通过目标文件的poll函数调用callback函数ep_ptable_queue_proc。 Poll函数一般由设备驱动提供，以网络设备为例，他的poll函数为sock_poll然后根据sock类型调用不同的poll函数如：packet_poll。packet_poll在通过datagram_poll调用sock_poll_wait，最后在poll_wait实际调用callback函数（ep_ptable_queue_proc）。
ep_ptable_queue_proc函数完成epitem加入到特定文件的wait队列任务。ep_ptable_queue_proc有
三个参数：struct file *file（目标文件）,wait_queue_head_t *whead（目标文件的waitlist）,
poll_table *pt（前面生成的poll_table）。在函数中，引入了另外一个非常重要的数据结构eppoll_entry。eppoll_entry主要完成epitem和epitem事件发生时的callback（ep_poll_callback）函数之间的关联，并将上述两个数据结构包装成一个链表节点，挂载到目标文件file的waithead中。这两还得完成两个动作，首先将eppoll_entry的whead指向目标文件的waitlist（传入的参数2），然后初始化base变量指向epitem，最后通过add_wait_queue将epoll_entry挂载到目标文件的waitlist。完成这个动作后，epoll_entry已经被挂载到waitlist，然后还有一个动作必须完成，就是将eppoll_entry挂载到epitem的pwqlist上面。现在还剩下一个动作，就是将epitem的fllink链接到目标文件的f_ep_links上，这部分工作将在poll函数返回后在ep_insert中完成。当然ep_insert除了完成这个动作外，还会完成前面提到的第二步，epitem插入eventpoll的rbtree。完成以上动作后，将还会判断当前插入的event是否刚好发生，如果是，那么做一个ready动作，将epitem加入到rdlist中，并对epoll上的wait队列调用wakeup。
到此为止基本完成了epoll_create以及epoll_ctl最重要的ADD函数的工作介绍。下面进入epoll_wait函数介绍。
2、epoll_wait
epoll_wait有四个参数int epfd（被wait的epoll所关联的epollfs的fd）,
struct epoll_event __user * events（返回监视到的事件）, int maxevents
（每次return的events最大值）, int timeout（最大wait时间）。
epoll_wait首先会检测传入参数的合法性，包括maxevents有没有超过范围
（0<=maxevents（(INT_MAX / sizeof(struct epoll_event))））；
events指向的空间是否可写；epfd是否合法等。参数合法性检测都通过后，将通过epfd获取锁依赖的struct file，
然后通过file->private_data获取eventpoll。获取epoll后调用ep_poll函数完成真正的epoll_wait工作。ep_poll函数也是四个参数和epoll_wait唯一的差别就是第一参数是前面获取的eventpoll指针。ep_poll首先根据timeout的值判断是否是无限等待，如果不是将timeout（ms）转换为jiffs。然后判断eventpoll的rdlist是否为空，如果为空，那么将current进程通过一个waitquene entry加入eventpoll的waitlist（wq）。并将task的状态改为TASK_INTERRUPTIBLE；并通过schedule_timeout让出处理器。如果rdlist非空，那么通过ep_send_events将event转发到userspace。
ep_send_events通过ep_scan_ready_list对ready_list进行扫描，由于现在在对ready_list进行操作，这个时候必须保证rdlist数据的一致性，如果此时又有新的event ready，那么我们必须提供临时的存储空间，eventpoll提供了一个ovflist用来存储这种event。ep_send_events获取了rdlist后通过ep_send_events_proc完成真正的转发工作。完成转发后，ep_send_events还需要去判断ovflist，如果ovflist中有events，那么还需要将这些events转移到rdlist中。
ep_send_events_proc扫描rdlist从头上面拿出epitem，然后调用epollfs的poll函数（ep_eventpoll_poll），判断拿出来的那个events是否真的已经ready（这部分比较难理解，没怎么看懂）。如果ready，那么将数据封装到uevent里面，同事这里还需要判断epitem的类型是否是Level Triggered如果是，那么还需要把event再次插入队列尾部。
3、ep_poll_callback
以上描述中还缺少关键的一环，就是如何在被监视文件发生event的时候，如何将epitem加入rdlist并唤醒调用epoll_wait进程。这个工作由ep_poll_callback函数完成。前面提到eppoll_entry完成一个epitem和ep_poll_callback的关联，同时eppoll_entry会被插入目标文件file的（private_data）waithead中。以scoket为例，当socket数据ready，终端会调用相应的接口函数比如rawv6_rcv_skb，此函数会调用sock_def_readable然后，通过sk_has_sleeper判断sk_sleep上是否有等待的进程，如果有那么通过wake_up_interruptible_sync_poll函数调用ep_poll_callback。
ep_poll_callback函数首先会判断是否rdlist正在被使用（通过ovflist是否等于EP_UNACTIVE_PTR），如果是那么将epitem插入ovflist。如果不是那么将epitem插入rdlist。然后调用wake_up函数唤醒epitem上wq的进程。这样就可以返回到epoll_wait的调用者，将他唤醒。
