epoll原理

参考:https://my.oschina.net/editorial-story/blog/3052308

  1. 网卡DMA传来数据,存入内存
  2. 网卡向CPU发送中断信号,操作系统得知有新数据到来,通过网卡中断程序去处理数据
  3. 将数据写入对应的socket接收缓冲区
  4. 唤醒对应进程
  5. 将进程放入工作队列

内核接收网络数据全过程

如下图所示,进程在 recv 阻塞期间,计算机收到了对端传送的数据(步骤①)——>

数据经由网卡传送到内存(步骤②),——>

然后网卡通过中断信号通知 CPU 有数据到达,CPU 执行中断程序(步骤③)。——>

此处的中断程序主要有两项功能,先将网络数据写入到对应 socket 的接收缓冲区里面(步骤④),——>

再唤醒进程 A(步骤⑤),——>

重新将进程 A 放入工作队列中。

以上是内核接收数据全过程,这里我们可能会思考两个问题:

  • 其一,操作系统如何知道网络数据对应于哪个 socket?
  • 其二,如何同时监视多个 socket 的数据?

第一个问题:因为一个 socket 对应着一个端口号,而网络数据包中包含了 ip 和端口的信息,内核可以通过端口号找到对应的 socket。当然,为了提高处理速度,操作系统会维护端口号到 socket 的索引结构,以快速读取。

第二个问题是多路复用的重中之重,也正是本文后半部分的重点。

select 简单的方法往往有缺点,主要是:

其一,每次调用 select 都需要将进程加入到所有监视 socket 的等待队列,每次唤醒都需要从每个队列中移除。这里涉及了两次遍历,而且每次都要将整个 fds 列表传递给内核,有一定的开销。正是因为遍历操作开销大,出于效率的考量,才会规定 select 的最大监视数量,默认只能监视 1024 个 socket。

其二,进程被唤醒后,程序并不知道哪些 socket 收到数据,还需要遍历一次。

有没有减少遍历的方法?有没有保存就绪 socket 的方法?这两个问题便是 epoll 技术要解决的

epoll 通过以下一些措施来改进效率:

措施一:功能分离

select 低效的原因之一是将“维护等待队列”和“阻塞进程”两个步骤合二为一。

措施二:就绪列表

select 低效的另一个原因在于程序不知道哪些 socket 收到数据,只能一个个遍历。如果内核维护一个“就绪列表”,引用收到数据的 socket,就能避免遍历。如下图所示,计算机共有三个 socket,收到数据的 sock2 和 sock3 被就绪列表 rdlist 所引用。当进程被唤醒后,只要获取 rdlist 的内容,就能够知道哪些 socket 收到数据。

epoll 的原理与工作流程

创建 epoll 对象

维护监视列表

接收数据

阻塞和唤醒进程

epoll 的实现细节

相信读者对 epoll 的本质已经有一定的了解。但我们还需要知道 eventpoll 的数据结构是什么样子?

此外,就绪队列应该应使用什么数据结构?eventpoll 应使用什么数据结构来管理通过 epoll_ctl 添加或删除的 socket?

如下图所示,eventpoll 包含了 lock、mtx、wq(等待队列)与 rdlist 等成员,其中 rdlist 和 rbr 是我们所关心的。

就绪列表的数据结构

就绪列表引用着就绪的 socket,所以它应能够快速的插入数据。

程序可能随时调用 epoll_ctl 添加监视 socket,也可能随时删除。当删除时,若该 socket 已经存放在就绪列表中,它也应该被移除。所以就绪列表应是一种能够快速插入和删除的数据结构。

双向链表就是这样一种数据结构,epoll 使用双向链表来实现就绪队列(对应上图的 rdllist)。

索引结构

既然 epoll 将“维护监视队列”和“进程阻塞”分离,也意味着需要有个数据结构来保存监视的 socket,至少要方便地添加和移除,还要便于搜索,以避免重复添加。红黑树是一种自平衡二叉查找树,搜索、插入和删除时间复杂度都是O(log(N)),效率较好,epoll 使用了红黑树作为索引结构(对应上图的 rbr)。

注:因为操作系统要兼顾多种功能,以及由更多需要保存的数据,rdlist 并非直接引用 socket,而是通过 epitem 间接引用,红黑树的节点也是 epitem 对象。同样,文件系统也并非直接引用着 socket。为方便理解,本文中省略了一些间接结构。