Linux内核中网络数据包的接收-第二部分 select/poll/epoll

Linux 2.6+内核的wakeup callback机制

Linux内核通过睡眠队列来组织所有等待某个事件的task，而wakeup机制则可以异步唤醒整个睡眠队列上的task，每一个睡眠队列上的节点都拥有一个callback，wakeup逻辑在唤醒睡眠队列时，会遍历该队列链表上的每一个节点，调用每一个节点的callback，如果遍历过程中遇到某个节点是排他节点，则终止遍历，不再继续遍历后面的节点。总体上的逻辑可以用下面的伪代码表示：

睡眠等待

define sleep_list;
define wait_entry;
wait_entry.task= current_task;
wait_entry.callback = func1;
if (something_not_ready); then
    # 进入阻塞路径
    add_entry_to_list(wait_entry, sleep_list);
go on:  
    schedule();
    if (something_not_ready); then
        goto go_on;
    endif
    del_entry_from_list(wait_entry, sleep_list);
endif
...

唤醒机制

something_ready;
for_each(sleep_list) as wait_entry; do
    wait_entry.callback(...);
    if(wait_entry.exclusion); then
        break;
    endif
done

我们只需要狠狠地关注这个callback机制，它能做的事真的不止select/poll/epoll，Linux的AIO也是它来做的，注册了callback，你几乎可以让一个阻塞路径在被唤醒的时候做任何事情。一般而言，一个callback里面都是以下的逻辑：

common_callback_func(...)
{
    do_something_private;
    wakeup_common;
}

其中，do_something_private是wait_entry自己的自定义逻辑，而wakeup_common则是公共逻辑，旨在将该wait_entry的task加入到CPU的就绪task队列，然后让CPU去调度它。

       现在留个思考，如果实现select/poll，应该在wait_entry的callback上做什么文章呢？

       .....

select/poll的逻辑

要知道，在大多数情况下，要高效处理网络数据，一个task一般会批量处理多个socket，哪个来了数据就去读那个，这就意味着要公平对待所有这些socket，你不可能阻塞在任何socket的“数据读”上，也就是说你不能在阻塞模式下针对任何socket调用recv/recvfrom，这就是多路复用socket的实质性需求。

       假设有N个socket被同一个task处理，怎么完成多路复用逻辑呢？很显然，我们要等待“数据可读”这个事件，而不是去等待“实际的数据”！！我们要阻塞在事件上，该事件就是“N个socket中有一个或多个socket上有数据可读”，也就是说，只要这个阻塞解除，就意味着一定有数据可读，意味着接下来调用recv/recvform一定不会阻塞！另一方面，这个task要同时排入所有这些socket的sleep_list上，期待任意一个socket只要有数据可读，都可以唤醒该task。

       那么，select/poll这类多路复用模型的设计就显而易见了。

       select/poll的设计非常简单，为每一个socket引入一个poll例程，该历程对于“数据可读”的判断如下：

poll()
{
    ...
    if (接收队列不为空) {
        ev |= POLL_IN;
    }
    ...
}

当task调用select/poll的时候，如果没有数据可读，task会阻塞，此时它已经排入了所有N个socket的sleep_list，只要有一个socket来了数据，这个task就会被唤醒，接下来的事情就是

for_each_N_socket as sk; do
    event.evt = sk.poll(...);
    event.sk = sk;
    put_event_to_user;
done;

可见，只要有一个socket有数据可读，整个N个socket就会被遍历一遍调用一遍poll函数，看看有没有数据可读，事实上，当阻塞在select/poll的task被唤醒的时候，它根本不知道具体socket有数据可读，它只知道这些socket中至少有一个socket有数据可读，因此它需要遍历一遍，以示求证，遍历完成后，用户态task可以根据返回的结果集来对有事件发生的socket进行读操作。

       可见，select/poll非常原始，如果有100000个socket(夸张吗？)，有一个socket可读，那么系统不得不遍历一遍...因此select只限制了最多可以复用1024个socket，并且在Linux上这是宏控制的。select/poll只是朴素地实现了socket的多路复用，根本不适合大容量网络服务器的处理场景。其瓶颈在于，不能随着socket的增多而战时扩展性。

epoll对wait_entry callback的利用

既然一个wait_entry的callback可以做任意事，那么能否让其做的比select/poll场景下的wakeup_common更多呢？

       为此，epoll准备了一个链表，叫做ready_list，所有处于ready_list中的socket，都是有事件的，对于数据读而言，都是确实有数据可读的。epoll的wait_entry的callback要做的就是，将自己自行加入到这个ready_list中去，等待epoll_wait返回的时候，只需要遍历ready_list即可。epoll_wait睡眠在一个单独的队列(single_epoll_waitlist)上，而不是socket的睡眠队列上。

       和select/poll不同的是，使用epoll的task不需要同时排入所有多路复用socket的睡眠队列，这些socket都拥有自己的队列，task只需要睡眠在自己的单独队列中等待事件即可，每一个socket的wait_entry的callback逻辑为：

epoll_wakecallback(...)
{
    add_this_socket_to_ready_list;
    wakeup_single_epoll_waitlist;
}

为此，epoll需要一个额外的调用，那就是epoll_ctrl ADD，将一个socket加入到epoll table中，它主要提供一个wakeup callback，将这个socket指定给一个epoll entry，同时会初始化该wait_entry的callback为epoll_wakecallback。整个epoll_wait以及协议栈的wakeup逻辑如下所示：

协议栈唤醒socket的睡眠队列

1.数据包排入了socket的接收队列;；
2.唤醒socket的睡眠队列，即调用各个wait_entry的callback；
3.callback将自己这个socket加入ready_list；
4.唤醒epoll_wait睡眠在的单独队列。
自此，epoll_wait继续前行，遍历调用ready_list里面每一个socket的poll历程，搜集事件。这个过程是例行的，因为这是必不可少的，ready_list里面每一个socket都有数据可读，做不了无用功，这是和select/poll的本质区别(select/poll中，即便没有数据可读，也要全部遍历一遍)。

       总结一下，epoll逻辑要做以下的例程：

epoll add逻辑

define wait_entry
wait_entry.socket = this_socket;
wait_entry.callback = epoll_wakecallback;
add_entry_to_list(wait_entry, this_socket.sleep_list);

epoll wait逻辑

define single_wait_list
define single_wait_entry
single_wait_entry.callback = wakeup_common;
single_wait_entry.task = current_task;
if (ready_list_is_empty); then
    # 进入阻塞路径
    add_entry_to_list(single_wait_entry, single_wait_list);
go on:  
    schedule();
    if (sready_list_is_empty); then
        goto go_on;
    endif
    del_entry_from_list(single_wait_entry, single_wait_list);
endif
for_each_ready_list as sk; do
    event.evt = sk.poll(...);
    event.sk = sk;
    put_event_to_user;
done;

epoll唤醒的逻辑

add_this_socket_to_ready_list;
wakeup_single_wait_list;

综合以上，可以给出下面的关于epoll的流程图，可以对比本文第一部分的流程图做比较

可以看出，epoll和select/poll的本质区别就是，在发生事件的时候，每一个epoll item(也就是socket)都拥有自己单独的一个wakeup callback，而对于select/poll而言，只有一个！这就意味着epoll中，一个socket发生事件，可以调用其独立的callback来处理它自身。从宏观上看，epoll的高效在于分离出了两类睡眠等待，一个是epoll本身的睡眠等待，它等待的是“任意一个socket发生事件”，即epoll_wait调用返回的条件，它并不适合直接睡眠在socket的睡眠队列上，如果真要这样，到底睡谁呢？毕竟那么多socket...因此它只睡自己。一个socket的睡眠队列一定要仅仅和它自己相关，因此另一类睡眠等待是每一个socket自身的，它睡眠在自己的队列上即可。

epoll的ET和LT

是时候提到ET和LT了，最大的争议在于哪个性能高，而不是到底怎么用。各种文档上都说ET高效，但事实上，根本不是这样，对于实际而言，LT高效的同时，更安全。两者到底什么区别呢？

概念上的区别

ET：只有状态发生变化的时候，才会通知，比如数据缓冲去从无到有的时候(不可读-可读)，如果缓冲区里面有数据，便不会一直通知；
LT：只要缓冲区里面有数据，就会一直通知。
查了很多资料，得到的答案无非就是类似上述的，然而如果看Linux的实现，反而让人对ET更加迷惑。什么叫状态发生变化呢？比如数据接收缓冲区里面一次性来了10个数据包，对比上述流程图，很显然会调用10次的wakeup操作，是不是意味着这个socket要被加入ready_list 10次呢？肯定不是这样的，第二个数据包到来调用wakeup callback时，发现该socket已经在ready_list了，肯定不会再加了，此时epoll_wait返回，用户读取了1个数据包之后，假设程序有bug，便不再读取了，此时缓冲区里面还有9个数据包，问题来了，此时如果协议栈再排入一个包，到底是通知还是不通知呢？？按照概念理解，不会通知了，因为这不是“状态的变化”，但是事实上在Linux上你试一下的话，发现是会通知的，因为只要有包排入socket队列，就会触发wakeup callback，就会将socket放入ready_list中，对于ET而言，在epoll_wait返回前，socket就已经从ready_list中摘除了。因此，如果在ET模式下，你发现程序阻塞在epoll_wait了，并不能下结论说一定是数据包没有收完一个原因导致的，也可能是数据包确实没有收完，但如果此时来一个新的数据包，epoll_wait还是会返回的，虽然这并没有带来缓冲去状态的边沿变化。

       因此，对于缓冲区状态的变化，不能简单理解为有和无这么简单，而是数据包的到来和不到来。

       ET和LT是中断的概念，如果你把数据包的到来，即插入到socket接收队列这件事理解成一个中断事件，所谓的边沿触发不就是这个概念吗？

实现上的区别

在代码实现的逻辑上，ET和LT实现的区别在于LT一旦有事件则会一直加进ready_list，直到下一次的poll将其移出，然后在探测到感兴趣事件后再将其加进ready_list。由poll例程来判断是否有事件，而不是完全依赖wakeup callback，这是真正意义的poll，即不断轮询！也就是说，LT模式是完全轮询的，每次都会去poll一次，直到poll不到感兴趣的事件，才会歇息，此时就只有数据包的到来可以重新依赖wakeup callback将其加入ready_list了。在实现上，从下面的代码可以看出二者的差异。

epoll_wait
for_each_ready_list_item as entry; do
    remove_from_ready_list(entry);
    event = entry.poll(...);
    if (event) then
        put_user;
        if (LT) then
            # 以下一次poll的结论为结果
            add_entry_to_ready_list(entry);
        endif
    endif
done

性能上的区别

性能的区别主要体现在数据结构的组织以及算法上，对于epoll而言，主要就是链表操作和wakeup callback操作，对于ET而言，是wakeup callback将socket加入到ready_list，而对于LT而言，则除了wakeup callback可以将socket加入到ready_list之外，epoll_wait也可以将其为了下一次的poll加入到ready_list，wakeup callback中反而有更少工作量，但这并不是性能差异的根本，性能差异的根本在于链表的遍历，如果有海量的socket采用LT模式，由于每次发生事件后都会再次将其加入ready_list，那么即便是该socket已经没有事件了，还是会用一次poll来确认，这额外的一次对于无事件socket没有意义的遍历在ET上是没有的。但是注意，遍历链表的性能消耗只有在链表超长时才会体现，你觉得千儿八百的socket就会体现LT的劣势吗？诚然，ET确实会减少数据可读的通知次数，但这事实上并没有带来压倒性的优势。

       LT确实比ET更容易使用，也不容易死锁，还是建议用LT来正常编程，而不是用ET来偶尔炫技。

编程上的区别

epoll的ET在阻塞模式下，无法识别到队列空事件，从而只是阻塞在单独一个socket的Recv而不是所有被监控socket的epoll_wait调用上，虽然不会影响代码的运行，只要该socket有数据到来便好，但是会影响编程逻辑，这意味着解除了多路复用的武装，造成大量socket的饥饿，即便有数据了，也没法读。当然，对于LT而言，也有类似的问题，但是LT会激进地反馈数据可读，因此事件不会轻易因为你的编程错误而被丢弃。

       对于LT而言，由于它会不断反馈，只要有数据，你想什么时候读就可以什么时候读，它永远有“下一次poll”的机会主动探知是否有数据可以继续读，即便使用阻塞模式，只要不要跨越阻塞边界造成其他socket饥饿，读多少数据均可以，但是对于ET而言，它在通知你的应用程序数据可读后，虽然新的数据到来还是会通知，但是你并不能控制新的数据一定会来以及什么时候来，所以你必须读完所有的数据才能离开，读完所有的时候意味着你必须可以探知数据为空，因此也就是说，你必须采用非阻塞模式，直到返回EAGIN错误。

给出几个ET模式下的tips

1.队列缓冲区的大小包括skb结构体本身的长度，230左右
2.ET模式下，wakeup callback中将socket加入ready_list的次数 >= 收到数据包的个数，因此
多个数据报足够快到达可能只会触发一次epoll wakeup callback的成功回调，此时只会将socket添加进ready_list一次
        =>造成队列满
                =>后续的大报文加不进去
        =>瓶塞效应
        =>可以填补缓冲区剩余hole的小报文可以触发ET模式的epoll_wait返回，如果最小长度就是1，那么可以发送0长度的包引诱epoll_wait返回
            =>但是由于skb结构体的大小是固有大小，以上的引诱不能保证会成功。
3.epoll惊群，可以参考ngx的经验
4.epoll也可借鉴NAPI关中断的方案，直到Recv例程返回EAGIN或者发生错误，epoll的wakeup callback不再被调用，这意味着只要缓冲区不为空，就算来了新的数据包也不会通知了。
a.只要socket的epoll wakeup callback被调用，禁掉后续的通知；
b.Recv例程在返回EAGIN或者错误的时候，开始后续的通知。