深入学习IO多路复用selectpollepoll实现原理

　　作者：mingguangtu，腾讯IEG后台开发工程师
　　selectpollepoll是Linux服务器提供的三种处理高并发网络请求的IO多路复用技术，是个老生常谈又不容易弄清楚其底层原理的知识点，本文打算深入学习下其实现机制。
　　Linux服务器处理网络请求有三种机制，select、poll、epoll，本文打算深入学习下其实现原理。
　　吃水不忘挖井人，最近两周花了些时间学习了张彦飞大佬的文章图解深入揭秘epoll是如何实现IO多路复用的和其他文章，及出版的书籍《深入理解Linux网络》，对阻塞IO、多路复用、epoll等的实现原理有了一定的了解；飞哥的文章描述底层源码逻辑比较清晰，就是有时候归纳总结事情本质的抽象程度不够，涉及内核源码细节的讲述较多，会让读者产生一定的学习成本，本文希望在这方面改进一下。0。结论
　　本文其他的内容主要是得出了下面几个结论：服务器要接收客户端的数据，要建立socket内核结构，主要包含两个重要的数据结构，（进程）等待队列，和（数据）接收队列，socket在进程中作为一个文件，可以用文件描述符fd来表示，为了方便理解，本文中，socket内核对象fd文件描述符TCP连接；阻塞IO的主要逻辑是：服务端和客户端建立了连接socket后，服务端的用户进程通过recv函数接收数据时，如果数据没有到达，则当前的用户进程的进程描述符和回调函数会封装到一个进程等待项中，加入到socket的进程等待队列中；如果连接上有数据到达网卡，由网卡将数据通过DMA控制器拷贝到内核内存的RingBuffer中，并向CPU发出硬中断，然后，CPU向内核中断进程ksoftirqd发出软中断信号，内核中断进程ksoftirqd将内核内存的RingBuffer中的数据根据数据报文的IP和端口号，将其拷贝到对应socket的数据接收队列中，然后通过socket的进程等待队列中的回调函数，唤醒要处理该数据的用户进程；阻塞IO的问题是：一次数据到达会进行两次进程切换，一次数据读取有两处阻塞，单进程对单连接；非阻塞IO模型解决了两次进程切换，两处阻塞，单进程对单连接中的两处阻塞问题，将两处阻塞变成了一处阻塞，但依然存在两次进程切换，一处阻塞，单进程对单连接的问题；用一个进程监听多个连接的IO多路复用技术解决了两次进程切换，一处阻塞，单进程对单连接中的两次进程切换，单进程对单连接，剩下了一处阻塞，这是Linux中同步IO都会有的问题，因为Linux没有提供异步IO实现；Linux的IO多路复用用三种实现：select、poll、epoll。select的问题是：
　　a）调用select时会陷入内核，这时需要将参数中的fdset从用户空间拷贝到内核空间，高并发场景下这样的拷贝会消耗极大资源；（epoll优化为不拷贝）
　　b）进程被唤醒后，不知道哪些连接已就绪即收到了数据，需要遍历传递进来的所有fdset的每一位，不管它们是否就绪；（epoll优化为异步事件通知）
　　c）select只返回就绪文件的个数，具体哪个文件可读还需要遍历；（epoll优化为只返回就绪的文件描述符，无需做无效的遍历）
　　d）同时能够监听的文件描述符数量太少，是1024或2048；（poll基于链表结构解决了长度限制）
　　7。poll只是基于链表的结构解决了最大文件描述符限制的问题，其他select性能差的问题依然没有解决；终极的解决方案是epoll，解决了select的前三个缺点；
　　8。epoll的实现原理看起来很复杂，其实很简单，注意两个回调函数的使用：数据到达socket的等待队列时，通过回调函数eppollcallback找到eventpoll对象中红黑树的epitem节点，并将其加入就绪列队rdllist，然后通过回调函数defaultwakefunction唤醒用户进程，并将rdllist传递给用户进程，让用户进程准确读取就绪的socket的数据。这种回调机制能够定向准确的通知程序要处理的事件，而不需要每次都循环遍历检查数据是否到达以及数据该由哪个进程处理，日常开发中可以学习借鉴下这种思想。1。Linux怎样处理网络请求1。1阻塞IO
　　要讲IO多路复用，最好先把传统的同步阻塞的网络IO的交互方式剖析清楚。
　　如果客户端想向Linux服务器发送一段数据，C语言的实现方式是：intmain（）｛intfdsocket（）；创建一个网络通信的socket结构体connect（fd，。。。）；通过三次握手跟服务器建立TCP连接send（fd，。。。）；写入数据到TCP连接close（fd）；关闭TCP连接｝
　　服务端通过如下C代码接收客户端的连接和发送的数据：intmain（）｛fdsocket（。。。）；创建一个网络通信的socket结构体bind（fd，。。。）；绑定通信端口listen（fd，128）；监听通信端口，判断TCP连接是否可以建立while（1）｛connfdaccept（fd，。。。）；阻塞建立连接intnrecv（connfd，buf，。。。）；阻塞读数据doSomeThing（buf）；利用读到的数据做些什么close（connfd）；关闭连接，循环等待下一个连接｝｝
　　把服务端处理请求的细节展开，得到如下图所示的同步阻塞网络IO的数据接收流程：
　　图1。1同步阻塞网络IO的数据接收流程
　　主要步骤是：
　　1）服务端通过socket（）函数陷入内核态进行socket系统调用，该内核函数会创建socket内核对象，主要有两个重要的结构体，（进程）等待队列，和（数据）接收队列，为了方便理解，等待队列前可以加上进程二字，其实不加更准确，接收队列同样；进程等待队列，存放了服务端的用户进程A的进程描述符和回调函数；socket的数据接收队列，存放网卡接收到的该socket要处理的数据；
　　2）进程A调用recv（）函数接收数据，会进入到recvfrom（）系统调用函数，发现socket的数据等待队列没有它要接收的数据到达时，进程A会让出CPU，进入阻塞状态，进程A的进程描述符和它被唤醒用到的回调函数callbackfunc会组成一个结构体叫等待队列项，放入socket的进程等待队列；
　　3）客户端的发送数据到达服务端的网卡；
　　4）网卡首先会将网络传输过来的数据通过DMA控制程序复制到内存环形缓冲区RingBuffer中；
　　5）网卡向CPU发出硬中断；
　　6）CPU收到了硬中断后，为了避免过度占用CPU处理网络设备请求导致其他设备如鼠标和键盘的消息无法被处理，会调用网络驱动注册的中断处理函数，进行简单快速处理后向内核中断进程ksoftirqd发出软中断，就释放CPU，由软中断进程处理复杂耗时的网络设备请求逻辑；
　　7）内核中断进程ksoftirqd收到软中断信号后，会将网卡复制到内存的数据，根据数据报文的IP和端口号，将其拷贝到对应socket的接收队列；
　　8）内核中断进程ksoftirqd根据socket的数据接收队列的数据，通过进程等待队列中的回调函数，唤醒要处理该数据的进程A，进程A会进入CPU的运行队列，等待获取CPU执行数据处理逻辑；
　　9）进程A获取CPU后，会回到之前调用recvfrom（）函数时阻塞的位置继续执行，这时发现socket内核空间的等待队列上有数据，会在内核态将内核空间的socket等待队列的数据拷贝到用户空间，然后才会回到用户态执行进程的用户程序，从而真的解除阻塞；
　　用户进程A在调用recvfrom（）系统函数时，有两个阶段都是等待的：在数据没有准备好的时候，进程A等待内核socket准备好数据；内核准备好数据后，进程A继续等待内核将socket等待队列的数据拷贝到自己的用户缓冲区；在内核完成数据拷贝到用户缓冲区后，进程A才会从recvfrom（）系统调用中返回，并解除阻塞状态。整体流程如下：
　　图1。2阻塞IO模型
　　在IO阻塞逻辑中，存在下面三个问题：进程在recv的时候大概率会被阻塞掉，导致一次进程切换；当TCP连接上的数据到达服务端的网卡、并从网卡复制到内核空间socket的数据等待队列时，进程会被唤醒，又是一次进程切换；并且，在用户进程继续执行完recvfrom（）函数系统调用，将内核空间的数据拷贝到了用户缓冲区后，用户进程才会真正拿到所需的数据进行处理；一个进程同时只能等待一条连接，如果有很多并发，则需要很多进程；
　　总结：一次数据到达会进行两次进程切换，一次数据读取有两处阻塞，单进程对单连接。1。2非阻塞IO
　　为了解决同步阻塞IO的问题，操作系统提供了非阻塞的recv（）函数，这个函数的效果是：如果没有数据从网卡到达内核socket的等待队列时，系统调用会直接返回，而不是阻塞的等待。
　　如果我们要产生一个非阻塞的socket，在C语言中如下代码所示：创建socketintsockfdsocket（AFINET，SOCKSTREAM，0）；。。。更改socket为nonblockfcntl（sockfd，FSETFL，fdflagsONONBLOCK）；connect。。。。while（1）｛intrecvlenrecv（sockfd，recvbuf，RECVBUFSIZE）；。。。。。。｝。。。
　　非阻塞IO模型如下图所示：
　　图1。3非阻塞IO模型
　　从上图中，我们知道，非阻塞IO，是将等待数据从网卡到达socket内核空间这一部分变成了非阻塞的，用户进程调用recvfrom（）会重复发送请求检查数据是否到达内核空间，如果没有到，则立即返回，不会阻塞。不过，当数据已经到达内核空间的socket的等待队列后，用户进程依然要等待recvfrom（）函数将数据从内核空间拷贝到用户空间，才会从recvfrom（）系统调用函数中返回。
　　非阻塞IO模型解决了两次进程切换，两处阻塞，单进程对单连接中的两处阻塞问题，将两处阻塞变成了一处阻塞，但依然存在两次进程切换，一处阻塞，单进程对单连接的问题。1。3IO多路复用
　　要解决两次进程切换，单进程对单连接的问题，服务器引入了IO多路复用技术，通过一个进程处理多个TCP连接，不仅降低了服务器处理网络请求的进程数，而且不用在每个连接的数据到达时就进行进程切换，进程可以一直运行并只处理有数据到达的连接，当然，如果要监听的所有连接都没有数据到达，进程还是会进入阻塞状态，直到某个连接有数据到达时被回调函数唤醒。
　　IO多路复用模型如下图所示：
　　图1。4IO多路复用模型
　　从上图可知，系统调用select函数阻塞执行并返回数据就绪的连接个数，然后调用recvfrom（）函数将到达内核空间的数据拷贝到用户空间，尽管这两个阶段都是阻塞的，但是由于只会处理有数据到达的连接，整体效率会有极大的提升。
　　到这里，阻塞IO模型的两次进程切换，两处阻塞，单进程对单连接问题，通过非阻塞IO和多路复用技术，就只剩下了一处阻塞这个问题，即Linux服务器上用户进程一定要等待数据从内核空间拷贝到用户空间，如果这个步骤也变成非阻塞的，也就是进程调用recvfrom后立刻返回，内核自行去准备好数据并将数据从内核空间拷贝到用户空间、再notify通知用户进程去读取数据，那就是IO异步调用，不过，Linux没有提供异步IO的实现，真正意义上的网络异步IO是Windows下的IOCP（IO完成端口）模型，这里就不探讨了。2。详解select、poll、epoll实现原理2。1select实现原理select函数定义
　　Linux提供的select函数的定义如下：intselect（intnfds，监控的文件描述符集里最大文件描述符加1fdsetreadfds，监控有读数据到达文件描述符集合，引用类型的参数fdsetwritefds，监控写数据到达文件描述符集合，引用类型的参数fdsetexceptfds，监控异常发生达文件描述符集合，引用类型的参数structtimevaltimeout）；定时阻塞监控时间
　　readfds、writefds、errorfds是三个文件描述符集合。select会遍历每个集合的前nfds个描述符，分别找到可以读取、可以写入、发生错误的描述符，统称为就绪的描述符。然后用找到的子集替换这三个引用参数中的对应集合，返回所有就绪描述符的数量。
　　timeout参数表示调用select时的阻塞时长。如果所有fd文件描述符都未就绪，就阻塞调用进程，直到某个描述符就绪，或者阻塞超过设置的timeout后，返回。如果timeout参数设为NULL，会无限阻塞直到某个描述符就绪；如果timeout参数设为0，会立即返回，不阻塞。
　　文件描述符fd
　　文件描述符（filedescriptor）是一个非负整数，从0开始。进程使用文件描述符来标识一个打开的文件。Linux中一切皆文件。
　　系统为每一个进程维护了一个文件描述符表，表示该进程打开文件的记录表，而文件描述符实际上就是这张表的索引。每个进程默认都有3个文件描述符：0（stdin）、1（stdout）、2（stderr）。
　　socket
　　socket可以用于同一台主机的不同进程间的通信，也可以用于不同主机间的通信。操作系统将socket映射到进程的一个文件描述符上，进程就可以通过读写这个文件描述符来和远程主机通信。
　　socket是进程间通信规则的高层抽象，而fd提供的是底层的具体实现。socket与fd是一一对应的。通过socket通信，实际上就是通过文件描述符fd读写文件。
　　本文中，为了方便理解，可以认为socket内核对象fd文件描述符TCP连接。
　　fdset文件描述符集合
　　select函数参数中的fdset类型表示文件描述符的集合。
　　由于文件描述符fd是一个从0开始的无符号整数，所以可以使用fdset的二进制每一位来表示一个文件描述符。某一位为1，表示对应的文件描述符已就绪。比如比如设fdset长度为1字节，则一个fdset变量最大可以表示8个文件描述符。当select返回fdset00010011时，表示文件描述符1、2、5已经就绪。
　　fdset的API
　　fdset的使用涉及以下几个API：includesysselect。hintFDZERO（intfd，fdsetfdset）；将fdset所有位置0intFDCLR（intfd，fdsetfdset）；将fdset某一位置0intFDSET（intfd，fdsetfdset）；将fdset某一位置1intFDISSET（intfd，fdsetfdset）；检测fdset某一位是否为1
　　select监听多个连接的用法
　　服务端使用select监控多个连接的C代码是：defineMAXCLINE5连接队列中的个数intfd〔MAXCLINE〕；连接的文件描述符队列intmain（void）｛sockfdsocket（AFINET，SOCKSTREAM，0）建立主机间通信的socket结构体。。。。。bind（sockfd，（structsockaddr）serveraddr，sizeof（serveraddr）；绑定socket到当前服务器listen（sockfd，5）；监听5个TCP连接fdsetfdsr；bitmap类型的文件描述符集合，01100表示第1、2位有数据到达intmax；for（i0；i5；i）｛。。。。。fd〔i〕accept（sockfd，（structsockaddr）clientaddr，sinsize）；跟5个客户端依次建立TCP连接，并将连接放入fd文件描述符队列｝while（1）循环监听连接上的数据是否到达｛FDZERO（fdsr）；对fdset即bitmap类型进行复位，即全部重置为0for（i0；i5；i）｛FDSET（fd〔i〕，fdsr）；将要监听的TCP连接对应的文件描述符所在的bitmap的位置置1，比如0110010110表示需要监听第1、2、5、7、8个文件描述符对应的TCP连接｝retselect（max1，fdsr，NULL，NULL，NULL）；调用select系统函数进入内核检查哪个连接的数据到达for（i0；i5；i）｛if（FDISSET（fd〔i〕，fdsr））fdset中为1的位置表示的连接，意味着有数据到达，可以让用户进程读取｛retrecv（fd〔i〕，buf，sizeof（buf），0）；。。。。。。｝｝｝
　　从注释中，我们可以看到，在一个进程中使用select监控多个连接的主要步骤是：
　　1）调用socket（）函数建立主机间通信的socket结构体，bind（）绑定socket到当前服务器，listen（）监听五个TCP连接；
　　2）调用accept（）函数建立和5个客户端的TCP连接，并把连接的文件描述符放入fd文件描述符队列；
　　3）定义一个fdset类型的变量fdsr；
　　4）调用FDZERO，将fdsr所有位置0；
　　5）调用FDSET，将fdsr要监听的几个文件描述符的位置1，表示要监听这几个文件描述符指向的连接；
　　6）调用select（）函数，并将fdsr参数传递给select；
　　7）select会将fdsr中就绪的位置1，未就绪的位置0，返回就绪的文件描述符的数量；
　　8）当select返回后，调用FDISSET检测哪些位为1，表示对应文件描述符对应的连接的数据已经就绪，可以调用recv函数读取该连接的数据了。
　　select的执行过程
　　在服务器进程A启动的时候，要监听的连接的socket文件描述符是3、4、5，如果这三个连接均没有数据到达网卡，则进程A会让出CPU，进入阻塞状态，同时会将进程A的进程描述符和被唤醒时用到的回调函数组成等待队列项加入到socket对象3、4、5的进程等待队列中，注意，这时select调用时，fdsr文件描述符集会从用户空间拷贝到内核空间，如下图所示：
　　图2。1select进程启动时，没有数据到达网卡
　　当网卡接收到数据，然后网卡通过中断信号通知CPU有数据到达，执行中断程序，中断程序主要做了两件事：
　　1）将网络数据写入到对应socket的数据接收队列里面；
　　2）唤醒队列中的等待进程A，重新将进程A放入CPU的运行队列中；
　　假设连接3、5有数据到达网卡，注意，这时select调用结束时，fdsr文件描述符集会从内核空间拷贝到用户空间：
　　图2。2select进程有数据到达时，会通过回调函数唤醒进程进行数据的读取
　　select的缺点
　　从上面两图描述的执行过程，可以发现select实现多路复用有以下缺点：
　　1。性能开销大
　　1）调用select时会陷入内核，这时需要将参数中的fdset从用户空间拷贝到内核空间，select执行完后，还需要将fdset从内核空间拷贝回用户空间，高并发场景下这样的拷贝会消耗极大资源；（epoll优化为不拷贝）
　　2）进程被唤醒后，不知道哪些连接已就绪即收到了数据，需要遍历传递进来的所有fdset的每一位，不管它们是否就绪；（epoll优化为异步事件通知）
　　3）select只返回就绪文件的个数，具体哪个文件可读还需要遍历；（epoll优化为只返回就绪的文件描述符，无需做无效的遍历）
　　2。同时能够监听的文件描述符数量太少。受限于sizeof（fdset）的大小，在编译内核时就确定了且无法更改。一般是32位操作系统是1024，64位是2048。（poll、epoll优化为适应链表方式）
　　第2个缺点被poll解决，第1个性能差的缺点被epoll解决。2。2poll实现原理
　　和select类似，只是描述fd集合的方式不同，poll使用pollfd结构而非select的fdset结构。structpollfd｛intfd；要监听的文件描述符shortevents；要监听的事件shortrevents；文件描述符fd上实际发生的事件｝；
　　管理多个描述符也是进行轮询，根据描述符的状态进行处理，但poll无最大文件描述符数量的限制，因其基于链表存储。
　　select和poll在内部机制方面并没有太大的差异。相比于select机制，poll只是取消了最大监控文件描述符数限制，并没有从根本上解决select存在的问题。2。3epoll实现原理
　　epoll是对select和poll的改进，解决了性能开销大和文件描述符数量少这两个缺点，是性能最高的多路复用实现方式，能支持的并发量也是最大。
　　epoll的特点是：
　　1）使用红黑树存储一份文件描述符集合，每个文件描述符只需在添加时传入一次，无需用户每次都重新传入；解决了select中fdset重复拷贝到内核的问题
　　2）通过异步IO事件找到就绪的文件描述符，而不是通过轮询的方式；
　　3）使用队列存储就绪的文件描述符，且会按需返回就绪的文件描述符，无须再次遍历；
　　epoll的基本用法是：intmain（void）｛structepolleventevents〔5〕；intepfdepollcreate（10）；创建一个epoll对象。。。。。。for（i0；i5；i）｛staticstructepolleventev；。。。。。ev。data。fdaccept（sockfd，（structsockaddr）clientaddr，sinsize）；ev。eventsEPOLLIN；epollctl（epfd，EPOLLCTLADD，ev。data。fd，ev）；向epoll对象中添加要管理的连接｝while（1）｛nfdsepollwait（epfd，events，5，10000）；等待其管理的连接上的IO事件for（i0；infds；i）｛。。。。。。read（events〔i〕。data。fd，buff，MAXBUF）｝｝
　　主要涉及到三个函数：intepollcreate（intsize）；创建一个eventpoll内核对象intepollctl（intepfd，intop，intfd，structepolleventevent）；将连接到socket对象添加到eventpoll对象上，epollevent是要监听的事件intepollwait（intepfd，structepolleventevents，intmaxevents，inttimeout）；等待连接socket的数据是否到达
　　epollcreate
　　epollcreate函数会创建一个structeventpoll的内核对象，类似socket，把它关联到当前进程的已打开文件列表中。
　　eventpoll主要包含三个字段：structeventpoll｛waitqueueheadtwq；等待队列链表，存放阻塞的进程structlistheadrdllist；数据就绪的文件描述符都会放到这里structrbrootrbr；红黑树，管理用户进程下添加进来的所有socket连接。。。。。。｝
　　wq：等待队列，如果当前进程没有数据需要处理，会把当前进程描述符和回调函数defaultwakefuncton构造一个等待队列项，放入当前wq对待队列，软中断数据就绪的时候会通过wq来找到阻塞在epoll对象上的用户进程。
　　rbr：一棵红黑树，管理用户进程下添加进来的所有socket连接。
　　rdllist：就绪的描述符的链表。当有的连接数据就绪的时候，内核会把就绪的连接放到rdllist链表里。这样应用进程只需要判断链表就能找出就绪进程，而不用去遍历整棵树。
　　eventpoll的结构如图2。3所示：
　　图2。3eventpoll对象的结构
　　epollctl
　　epollctl函数主要负责把服务端和客户端建立的socket连接注册到eventpoll对象里，会做三件事：
　　1）创建一个epitem对象，主要包含两个字段，分别存放socketfd即连接的文件描述符，和所属的eventpoll对象的指针；
　　2）将一个数据到达时用到的回调函数添加到socket的进程等待队列中，注意，跟第1。1节的阻塞IO模式不同的是，这里添加的socket的进程等待队列结构中，只有回调函数，没有设置进程描述符，因为在epoll中，进程是放在eventpoll的等待队列中，等待被epollwait函数唤醒，而不是放在socket的进程等待队列中；
　　3）将第1）步创建的epitem对象插入红黑树；
　　图2。4epollctl执行结果
　　epollwait
　　epollwait函数的动作比较简单，检查eventpoll对象的就绪的连接rdllist上是否有数据到达，如果没有就把当前的进程描述符添加到一个等待队列项里，加入到eventpoll的进程等待队列里，然后阻塞当前进程，等待数据到达时通过回调函数被唤醒。
　　当eventpoll监控的连接上有数据到达时，通过下面几个步骤唤醒对应的进程处理数据：
　　1）socket的数据接收队列有数据到达，会通过进程等待队列的回调函数eppollcallback唤醒红黑树中的节点epitem；
　　2）eppollcallback函数将有数据到达的epitem添加到eventpoll对象的就绪队列rdllist中；
　　3）eppollcallback函数检查eventpoll对象的进程等待队列上是否有等待项，通过回调函数defaultwakefunc唤醒这个进程，进行数据的处理；
　　4）当进程醒来后，继续从epollwait时暂停的代码继续执行，把rdlist中就绪的事件返回给用户进程，让用户进程调用recv把已经到达内核socket等待队列的数据拷贝到用户空间使用。
　　图2。5epollwait在有数据到达socket时、依次通过两个回调函数唤醒进程3。总结
　　从阻塞IO到epoll的实现中，我们可以看到wakeup回调函数机制被频繁的使用，至少有三处地方：一是阻塞IO中数据到达socket的等待队列时，通过回调函数唤醒进程，二是epoll中数据到达socket的等待队列时，通过回调函数eppollcallback找到eventpoll中红黑树的epitem节点，并将其加入就绪列队rdllist，三是通过回调函数defaultwakefunc唤醒用户进程，并将rdllist传递给用户进程，让用户进程准确读取数据。从中可知，这种回调机制能够定向准确的通知程序要处理的事件，而不需要每次都循环遍历检查数据是否到达以及数据该由哪个进程处理，提高了程序效率，在日常的业务开发中，我们也可以借鉴下这一机制。
　　References
　　图解深入揭秘epoll是如何实现IO多路复用的！
　　图解Linux网络包接收过程
　　图解深入理解高性能网络开发路上的绊脚石同步阻塞网络IO
　　从linux源码看socket的阻塞和非阻塞
　　Select、Poll、Epoll详解
　　你管这破玩意叫IO多路复用？
　　IO多路复用，selectpollepoll详解
　　大话Select、Poll、Epoll
　　IO多路复用底层原理全解，select，poll，epoll，socket，系统中断，进程调度，系统调用