深入理解SELECT、POLL和EPOLL

前言 + 吹牛

既然已经说了是深入理解，那么我们这篇文章涉及到的肯定不止简单的概念介绍，会进入到操作系统和内核的层面去理解这三种处理方式。我们之前会介绍一些概念帮助我们更好的理解整个NIO。

用户空间与内核空间

现在操作系统都是采用虚拟存储器，那么对32位操作系统而言，它的寻址空间（虚拟存储空间）为4G（2的32次方）。操作系统的核心是内核，独立于普通的应用程序，可以访问受保护的内存空间，也有访问底层硬件设备的所有权限。

为了保证用户进程不能直接操作内核，保证内核的安全，操心系统将虚拟空间划分为两部分，一部分为内核空间，一部分为用户空间。针对Linux操作系统而言，将最高的1G字节（从虚拟地址0xC0000000到0xFFFFFFFF），供内核使用，称为内核空间，而将较低的3G字节（从虚拟地址0x00000000到0xBFFFFFFF），供各个进程使用，称为用户空间。我们可以简单理解为，一张纸，四分之一给一个叫内核的人用，四分之三给一个叫用户的人用。

文件描述符fd

文件描述符是计算机科学中的一个术语，是一个用于表述指向文件的引用的抽象化概念。

文件描述符在形式上是一个非负整数。实际上，它是一个索引值，指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。在程序设计中，一些涉及底层的程序编写往往会围绕着文件描述符展开。但是文件描述符这一概念往往只适用于Unix和Linux这样的操作系统。

Linux的socket事件wakeup callback机制

在介绍select、poll和epoll前，有必要说说Linux（2.6+）内核的事件wakeup callback机制，这是IO多路复用机制存在的本质。Linux通过socket睡眠队列来管理所有等待socket的某个事件的进程（Process），同时通过wakeup机制来异步唤醒整个睡眠队列上等待事件的Process，通知Process相关事件发生。

我们可以理解为，每个socket维护了一个队列，比如socket可读的时候，内核就会唤醒队列里的各个Process，并且执行每个Process的callback函数。总体上会涉及两大逻辑：

睡眠逻辑：

select、poll、epoll_wait陷入内核，判断监控的socket是否有关心的事件发生了，如果没，则为当前Process构建一个wait_entry节点，然后插入到监控socket的sleep_list里取。
Linux调用schedule函数进行Process的状态转换，shcedule函数是Linux的调度Process的函数，这里指的是Process进入sleep直到超时或者事件发生。
关心的事件发生后，将当前Process的wait_entry节点从socket的sleep_list中删除。

唤醒逻辑：

socket的事件发生了，然后socket顺序遍历其睡眠队列sleep_list，依次调用每个wait_entry节点（对应各个Process）的callback函数。
直到完成队列的遍历或遇到某个wait_entry节点是排他的才停止。
一般情况下callback包含两个逻辑：wait_entry自定义的私有逻辑和唤醒的公共逻辑，主要用于将该wait_entry的Process放入CPU的就绪队列，让CPU随后可以调度其执行。

SELECT

上面是一些基本概念，下面才是重头戏，我们先从最开始也是各方面问题最多的SELECT开始。

SELECT和POLL以及EPOLL一样，都可以管理多个socket。我们以read事件为例展开说一下SELECT的过程，对于read而言，哪个socket有数据可读，Process就去读取该socket的数据来处理。我们关心的，无非就是，我们管理的socket里，哪个可以读，也就是我们期待可读事件的通知，而不是盲目地对每个socket调用recv/recvfrom来尝试接收数据。我们应该block在等待事件的发生上，这个事件简单点就是关心的N个socket中一个或多个socket有数据可读了，当block解除的时候，就意味着，我们一定可以找到一个或多个socket上有可读的数据（至少一个可读）。

另一方面，根据上面的socket wakeup callback机制，我们不知道什么时候，哪个socket会有读事件发生。所以，Process需要同时插入到我们管理的这好多个socket的sleep_list上等待任意一个socket可读事件发生而被唤醒，当Process被唤醒的时候，其callback里面应该有个逻辑去检查具体哪些socket可读了。然后把这些事件反馈给用户程序，用户程序就知道，哦，我该处理这些socket了，我可以从这些socket里读取数据了。

select的多路复用逻辑就清晰了，select为每个socket引入一个poll逻辑，该逻辑用于收集socket发生的事件。对于可读事件来说，简单伪码如下：

private int sk_event;

void poll() {
    //其他逻辑...
    when (receive queue is not empty) {
        sk_event |= POLL_IN；
    }
   //其他逻辑...
}

解释一下，当receive queue不为空的时候，我们就给这个socket的sk_event添加一个POLL_IN事件，用来表示当前这个socket可读。将来Process遍历到这个socket，发现其sk_event包含POLL_IN的时候，就可以对这个socket进行读取数据操作了。

接下来，当用户Process调用select的时候，select会将需要监控的readfds集合拷贝到内核空间（因为内核才能通知说某个socket可读），然后遍历自己监控的socket，挨个调用socket的poll逻辑以便检查该socket是否有可读事件。

遍历完所有的socket后，如果没有任何一个sk可读，那么select会调用schedule，使得Process进入睡眠（或者睡眠timeout这么长时间）。如果在timeout时间内某个socket上有数据可读了，或者等待timeout了，则调用select的Process会被唤醒。

接下来select就是遍历监控的socket集合，挨个收集可读事件并返回给用户了，相应的伪码如下：

for (socket in readfds) {
    sk_event.evt = socket.poll();
    sk_event.sk = socket;
    return_event_for_process;
}

总结一下我们发现select有两个问题：

被监控的readfds需要从用户空间拷贝到内核空间。为了减少数据拷贝带来的性能损坏，内核对被监控的fds集合大小做了限制，并且这个是通过宏控制的，大小不可改变，只能通过重新编译内核等复杂方式改变。
被监控的readfds集合中，只要有一个有数据可读，整个socket集合就会被遍历一次并且调用socket的poll函数收集可读事件。

说到这，我们有几个问题要解决：

被监控的fds集合限制为1024，1024太小了，我们希望能够有个比较大的可监控fds集合。
fds集合需要从用户空间拷贝到内核空间的问题，我们希望不需要拷贝。
当被监控的fds中某些有数据可读的时候，我们希望通知更加精细一点，就是我们希望能够从通知中得到有可读事件的fds列表，而不是需要遍历整个fds来收集。

POLL

poll非常鸡肋，只解决了第一个问题——1024的问题。poll改变了fds集合的描述方式，使用了pollfd结构而不是select的fd_set结构，使得poll支持的fds集合限制远大于select的1024。这里我们就不细说了。

EPOLL

问题1被poll解决了，2和3就被epoll解决了。

这里抄一段话，计算机世界里，有两大解决问题的方式：

计算机科学领域的任何问题, 都可以通过添加一个中间层来解决。
变集中处理为分散处理。

我们看看怎么解决上述的问题的。

fds集合拷贝问题的解决
对于IO多路复用，有两件事是必须要做的(对于监控可读事件而言)：

准备好需要监控的fds集合。
探测并返回fds集合中哪些fd可读了。

细看select和poll的函数原型，我们会发现，每次调用select或poll都在重复地准备整个需要监控的fds集合。我们需要监控三个socket，就要准备一个readfds，然后新增监控一个socket，就要再准备一个readfds（包含旧的和新的socket的readfds）。然而对于频繁调用的select或poll而言，fds集合的变化频率要低得多，我们没必要每次都重新准备整个fds集合。

于是，epoll引入了epoll_ctl系统调用，将高频调用的epoll_wait和低频的epoll_ctl隔离开。epoll_ctl是epoll的事件注册函数，它不同与select()是在监听事件时，告诉内核要监听什么类型的事件，而是在这里先注册要监听的事件类型。到了有变化才变更，将select或poll高频、大块内存拷贝变成epoll_ctl的低频、小块内存的拷贝，避免了大量的内存拷贝。这就是我们说的，分散处理方式。

同时，对于高频epoll_wait的可读就绪的fd集合返回的拷贝问题，epoll通过内核与用户空间mmap同一块内存来解决。mmap将用户空间的一块地址和内核空间的一块地址同时映射到相同的一块物理内存地址（不管是用户空间还是内核空间都是虚拟地址，最终要通过地址映射映射到物理地址），使得这块物理内存对内核和对用户均可见，减少用户态和内核态之间的数据交换。

另外，epoll通过epoll_ctl来对监控的fds集合来进行增、删、改，那么必须涉及到fd的快速查找问题。于是，一个低时间复杂度的增、删、改、查的数据结构来组织被监控的fds集合是必不可少的了。

在linux 2.6.8之前的内核，epoll使用hash来组织fds集合，于是在创建epoll fd的时候，epoll需要初始化hash的大小。于是epoll_create(int size)有一个参数size，以便内核根据size的大小来分配hash的大小。在linux 2.6.8以后的内核中，epoll使用红黑树来组织监控的fds集合，所以参数size实际上已经没有意义了。

按需遍历就绪的fds集合
通过上面的socket的睡眠队列唤醒逻辑我们知道，socket唤醒睡眠在其睡眠队列的wait_entry的时候会调用wait_entry的回调函数callback，并且，我们可以在callback中做任何事情。为了做到只遍历就绪的fd，我们需要有个地方来组织那些已经就绪的fd。

为此，epoll引入了一个中间层，一个双向链表ready_list，一个单独的睡眠队列single_epoll_wait_list，并且，与select或poll不同的是，epoll的Process不需要同时插入到多路复用的socket集合的所有睡眠队列中，相反Process只是插入到中间层的epoll的单独睡眠队列中（即single_epoll_wait_list），Process睡眠在epoll的单独队列上，等待事件的发生。同时，引入一个中间的wait_entry_sk，它与某个socket密切相关，wait_entry_sk睡眠在socket的睡眠队列上，其callback函数逻辑是将当前socket排入到epoll的ready_list中，并唤醒epoll的single_epoll_wait_list。而single_epoll_wait_list上睡眠的Process的回调函数就明朗了：遍历ready_list上的所有socket，挨个调用socket的poll函数收集事件，然后唤醒Process从epoll_wait返回。

语言很苍白，我们看下图：

EPOLL各阶段图

四张图代表四种状态：

调用epoll之前，我们希望我们的MyProcess可以管理四个socket。
四个socket都没有事件，这时候MyProcess进入single_epoll_wait_list并且sleep。
有一个socket（大红色）收到了数据，触发其wait_entry_sk，把这个socket加入到ready_list里。
MyProcess被唤醒（从single_epoll_wait_list出来了表示被唤醒），来处理ready_list中的所有socket：遍历epoll的ready_list，挨个调用每个socket的poll逻辑收集发生的事件，对于监控可读事件而已，ready_list上的每个socket都是有数据可读的，这里的遍历必要的。

至此，我们就可以理解说为什么epoll才是真正高性能的方式。

关于边缘触发和水平触发

epoll都说了，不说说这两种模式实在说不过去。

我们说两种模式前，要先说一下epoll的唤醒逻辑：

协议数据包到达网卡并被排入socket的接收队列。
睡眠在socket的睡眠队列wait_entry被唤醒，wait_entry_sk的回调函数epoll_callback_sk被执行。
epoll_callback_sk将当前socket插入epoll的ready_list中。
唤醒睡眠在epoll的单独睡眠队列single_epoll_wait_list的wait_entry，wait_entry_proc被唤醒执行回调函数epoll_callback_proc。
遍历epoll的ready_list，挨个调用每个socket的poll逻辑收集发生的事件。
将每个socket收集到的事件，通过epoll_wait传入的events数组回传并唤醒相应的Process。

大的逻辑其实没有变化，我们之前没有提过wait_entry_proc和epoll_callback_proc，这里简单说一下：

wait_entry_proc：睡眠实体，将当前Process关联给wait_entry_proc，并设置回调函数为epoll_callback_proc。我们之前说睡眠在single_epoll_wait_list中的是Process，其实是包了一层的wait_entry_proc。

epoll_callback_proc：回调函数，主要逻辑是遍历epoll的ready_list，挨个调用每个socket的poll逻辑收集发生的事件，然后将每个socket收集到的事件，通过epoll_wait传入的events数组回传并唤醒相应的Process。

那么两种触发模式的本质，就在唤醒逻辑里我们说的第5步。其实真是的情况应该是这样的：

对于边沿触发（ET）：
遍历epoll的ready_list，将socket从ready_list中移除，然后调用该socket的poll逻辑收集发生的事件。

对于水平触发（LT）：

遍历epoll的ready_list，将socket从ready_list中移除，然后调用该socket的poll逻辑收集发生的事件。
如果该socket的poll函数返回了关心的事件（对于可读事件来说，就是POLL_IN事件），那么该socket被重新加入到epoll的ready_list中！

对于可读事件而言，在ET模式下，如果某个socket有新的数据到达，那么该socket就会被排入epoll的ready_list，从而epoll_wait就一定能收到可读事件的通知（调用socket的poll逻辑一定能收集到可读事件）。于是，我们通常理解的缓冲区状态变化时触发的理解是不准确的，准确的理解应该是是否有新的数据达到缓冲区。

而在LT模式下，某个socket被探测到有数据可读，那么该socket会被重新加入到ready_list，那么在该socket的数据被全部取走前，下次调用epoll_wait就一定能够收到该socket的可读事件，从而epoll_wait就能返回。

这才是我们说两种触发模式本质上的区别。之前我跟dubbo的committer聊起这个触发模式的时候，也是知其然的级别，今天了解到以后，赶紧去给人家澄清一下~希望大家都可以看得懂~