2002 年 linux 2.5.44 发布了 epoll, epoll 是 linux 实现高并发网络 I/O 处理的基础, 但凡存在网络 I/O 的系统或框架 (比如 nginx、netty、kafka、redis 等) 都离不开 epoll;
因此学习 epoll 的原理对于应用开发者理解网络框架的运行原理有着巨大的帮助;

前置基础知识

DMA 与中断

当 NIC 网卡收到网络数据时的处理流程:

  • 网卡通过 Direct Memory Access 将数据写到内核内存 (Ring Buffer 和 sk_buff);
  • 网卡向 CPU 发出中断请求 (Interrupt Request, IRQ);
  • 为解决频繁 IRQ 导致大量上下文切换的开销, 内核采用了请求预聚合技术 (N-API, 即 New API):
    • 内核的 napi_schedule 函数专门快速响应 IRQ, 只记录必要信息, 并在合适的时机发出软中断 softirq;
    • 内核的 net_rx_action 函数响应软中断, 从 Ring Buffer 中批量拉取收到的数据并处理协议栈, 填充 socket 再交付上层;
      net data transfer
      net data transfer

linux: 一切皆文件

在 linux 系统中 “一切皆文件 (Everything is a file)” 是一个核心的设计理念,
linux 将所有资源 (无论是普通文件、目录、设备、网络套接字还是进程信息) 都抽象为文件的形式, 并以一个抽象层 (Virtual File System) 统一管理, 使得用户可以用统一的文件描述符处理各种资源:

  • 普通文件：如文本文件、图片文件等;
  • 目录：目录本身也被视为一种特殊的文件;
  • 设备：硬件设备（如硬盘、键盘、显示器）被抽象为设备文件;
  • 管道和套接字：用于进程间通信的管道和网络通信的套接字也可以像文件一样操作;
  • 系统信息：例如 /proc 和 /sys 文件系统中的内容，提供对系统状态和内核参数的访问;

当我们使用 epoll 时, 内核会创建一个 struct eventpoll, eventpoll 也是文件系统中的一种资源类型;

文件系统的 wait queue

在 Linux 文件系统中，等待队列是一种内核同步机制，用于管理因某些条件未满足而需要等待的进程; 它广泛应用于文件 I/O 操作、设备驱动程序和网络通信中，尤其是在处理阻塞操作时:

  • 当读取文件时，如果文件的数据尚未准备好 (如管道或设备文件), 进程会被加入到等待队列中;
  • 当写入文件时，如果缓冲区已满，进程也会被加入到等待队列中;

当条件满足时 (如数据到达或缓冲区有空间可用) 内核会唤醒等待队列中的进程;

当我们使用 epoll 时, 我们主要与两种文件类型打交道: eventpoll 和 socket, 他们分别有自己的等待队列 (wq), 存放不同类型的资源:

  • eventpoll 队列: 存放的是等待 IO 事件到来的进程;
  • socket 队列: 存放的是 struct eventpoll;

linux 内核中通常用 wait_queue_head_t 双向链表类型来定义等待队列;

epoll 的数据结构

eventpoll

eventpoll 是 epoll 核心数据结构, 用于管理一个 epoll 实例的所有相关信息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct eventpoll {
    struct rb_root rbr;             // 红黑树，存储所有注册的 epitem
    struct list_head rdllist;       // 就绪链表，存储当前就绪的 epitem
    wait_queue_head_t wq;           // 等待队列，用于阻塞调用 epoll_wait() 的进程
    
    spinlock_t lock;                // 保护 eventpoll 对象的自旋锁
    struct mutex mtx;               // 互斥锁，用于保护某些关键操作
    wait_queue_head_t poll_wait;    // 用于支持嵌套 epoll (epoll over epoll)
    struct epitem *ovflist;         // 溢出链表，用于处理边缘触发模式下的特殊情况
    struct user_struct *user;       // 用户信息，用于资源限制跟踪
    struct file *file;              // 指向与该 epoll 实例关联的文件对象
    int visited;                    // 用于标记是否访问过，避免循环嵌套
    ...
};

eventpoll 结构体主要成员如下:

  • rbr: 用于记录用户注册的其所感兴趣的 socket 事件, 使用红黑树结构, 方便后续查找;
  • rdllist: 当向 epoll 注册的 socket 事件发生后, 就绪队列会记录相关 socket 的读/写事件并返回给用户进程;
  • wq: 当用户进程调用 epoll_wait 进入休眠后, 被挂在该等待队列, 用于注册事件发生时回调唤醒该进程;

epitem

epitem 是 epoll 另一个核心数据结构, 承载了相关文件描述符 (通常为 socket 描述符) 及其事件订阅信息:

  • ffd: 通过 ffd.fd 可以获取目标文件描述符;
  • event: 事件类型, 常用如下: EPOLLIN (socket 可读), EPOLLOUT (socket 可写)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct epitem {
        struct epoll_filefd ffd;  // 文件描述符及其相关信息
        struct epoll_event event; // 用户注册的事件信息
        
        struct rb_node rbn;       // 红黑树节点, 用于插入到红黑树 (rbr) 中
        struct list_head rdllink; // 就绪链表节点, 用于插入到就绪链表 (rdllist) 中
        
        struct eventpoll *ep;     // 指向所属的 eventpoll 对象
        ...
    };

除此之外, epitem 还有两个关键的字段:

  • rbn: 作为一个 rb_node 类型 (linux 内核中通用的红黑树节点结构体), 它是 epitem 的字段, 同时也是 eventpoll rbr 红黑树的节点, eventpoll 通过内核中的一个通用宏定义 container_of, 可依据局部字段的地址计算出整个结构体的地址, 从而定位到 epitem;
  • rdllink: 作为一个 list_head 类型 (linux 内核中通用的双向链表节点结构体), 与 rbn 类似, 它是 epitem 的字段, 同时也是 eventpoll rdllist 双向链表的节点, eventpoll 同样可以基于 container_of 根据 rdllink 字段定位到 epitem;

可以看到, epoll 的数据结构非常紧凑, eventpoll 的 rbr 和 rdllist 都是基于对 epitem 的引用构建的, 以最大限度地提升性能和节约内存:

struct eventpoll
struct eventpoll

epoll 数据结构的选型

有很多文章说, eventpoll 使用红黑树管理 socket 事件订阅只是一种实现方式, 也可以换成哈希表等其他高效的内存结构, 个人认为这是一个值得讨论的问题;
首先我们先梳理一下 epoll 面临的业务场景:

  • 大量、高并发的 socket 请求: epoll 通常被服务端用于处理高并发的海量用户请求, 对低延迟要求很高;
  • 低活跃的单个 socket 对象: 虽然有海量的请求连接到服务器, 但是对每一个具体的 socket 对象, 却活跃度很低, 在其生命周期的大部分时间内都不会产生 IO 事件;
  • 朝生夕死的 socket 对象: socket 对象通常不会存活很久, 用户请求结束后会关闭连接;

总结一下业务特点就是:

  • 存在 socket 的大量新增;
  • 存在 socket 的大量删除;
  • 对 socket 事件的响应处理必须要快;
  • 虽然 socket 总量很大, 但是同一时刻发生 IO 事件的 socket 占总量比例不高;

再来看下不同数据结构对以上业务特点的支持能力:

  • 红黑树:
    • 优点:
      1. 依托于链式结构无需大块的连续内存, 不管当前树结构有多么庞大, 创建新节点的成本都极低, 只要能找到一块可用内存就行;
      2. 删除节点的成本也相对可控, 通过有限的旋转和重新着色即可维护树的平衡;
    • 缺点:
      1. 查询时间复杂度是 O(logn), 当节点数量巨大, 查询性能会受一定影响;
  • 哈希表:
    • 优点:
      1. 当内存足够大时, 查询 socket 的时间复杂度为 O(1);
    • 缺点:
      1. 需要申请一大片连续的内存用作文件描述符到 socket 的映射, 不够灵活;
      2. 当 socket 数量不断增长, hash 冲突的概率越大, 查询复杂度会劣化 (最差可劣化到 O(n));
      3. 如果需要扩容哈希表以减少 key 冲突, 需要申请一片新的连续内存, 并将旧的数据复制过去, 开销很大;
      4. 当请求流量进入低谷期时, 已扩容的哈希表如果不缩容, 会造成内存浪费; 如果缩容, 则又涉及数据复制, 增大开销;

 
综合考虑: 我们需要的理想数据结构是:

  • 增删 socket 订阅事件、维护索引的成本要足够低;
  • socket 事件订阅查询效率要尽可能高, 且要保持查询性能稳定, 不能因 socket 数量规模的急剧变化而产生明显劣化;

因此 linux 内核选择了查询性能十分稳定、对内存使用效率更高、使用方式更灵活的红黑树作为 eventpoll 索引 socket 订阅事件的数据结构;

补充: 内核常用结构和宏定义

  • rb_node: 内核通用红黑树节点

    1
    2
    3
    4
    5
    struct rb_node {
        unsigned long __rb_parent_color;  // 父节点指针和颜色标志
        struct rb_node *rb_right;         // 右子节点指针
        struct rb_node *rb_left;          // 左子节点指针
    };

  • rb_root: 内核通用红黑树根

    1
    2
    3
    struct rb_root {
        struct rb_node *rb_node;  // 指向红黑树的根节点
    };

  • list_head: 内核通用双向链表节点

    1
    2
    3
    4
    struct list_head {
        struct list_head *next;  // 指向下一个节点
        struct list_head *prev;  // 指向前一个节点
    };

container_of 宏定义:

1
2
3
4
5
6
7
8
/**
 * @param ptr：指向结构体中某个字段的指针 (如 rb_node 的地址)
 * @param type：结构体的类型 (如 struct epitem)
 * @param member：字段的名称 (如 rbn)
 */
#define container_of(ptr, type, member) ({                      \
    const typeof(((type *)0)->member) *__mptr = (ptr);          \
    (type *)((char *)__mptr - offsetof(type, member)); })

epoll 的执行逻辑

一般来说, 用户使用 epoll 的逻辑是:

  • 调用 epoll_create, 创建对象;
  • 调用 epoll_ctl, 订阅感兴趣的 socket 事件;
  • 调用 epoll_wait, 等待订阅事件的发生;

epoll_create

1
2
#include <sys/epoll.h>
int epoll_create(int size);

进程调用 epoll_create 方法, 内核会创建出一个 struct eventpoll, 注册到文件列表中, 并将其文件描述符 epfd 返回给进程;

epoll_create
epoll_create

epoll_ctl

1
2
3
4
5
6
7
8
9
#include <sys/epoll.h>

/**
 * @param epfd  eventpoll 的文件描述符
 * @param op    EPOLL_CTL_ADD / EPOLL_CTL_MOD / EPOLL_CTL_DEL
 * @param fd    需要操作的文件 (比如 socket)
 * @param event 感兴趣的 socket 事件类型
 */
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);

进程调用 epoll_ctl, 内核主要做了三件事:

  1. 在内存中创建一个 struct epitem;
  2. 插入目标 epitem 的 rbn 节点至 eventpoll 的 rbr 红黑树, 从而建立对 socket 事件订阅的高效查询;
  3. 将 struct eventpoll 插入到目标 socket 等待队列, 用于 socket 接收到数据时回调以唤醒调用 epoll 线程;

epoll_ctl_process

insert_into_socket_wq
insert_into_socket_wq

epoll_wait

1
2
3
4
5
6
7
8
9
#include <sys/epoll.h>

/**
 * @param epfd      eventpoll 的文件描述符
 * @param events    epoll 事件数组
 * @param maxevents 指定events 数组的大小, 即可以处理的最大事件数
 * @param timeout   若无目标事件发生, timeout 时间后返回 0
 */
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);

关于 timeout 的设置:

  • timeout > 0: 如果在指定的时间内没有事件发生, epoll_wait 将阻塞最多 timeout 毫秒;
    如果在此期间有事件发生则立即返回, 且返回值为触发事件的数量;
  • timeout == 0: 不阻塞而是立即返回, 这种模式通常用于非阻塞检查, 适合需要快速轮询的场景;
  • timeout == -1: 无限期阻塞, 直到至少有一个事件发生, 这是最常用的模式, 适合不需要定时功能的场景;
    绝大多数 I/O 多路复用场景, 尤其是长时间运行的服务端程序都应该是这个模式;

 
进程调用 epoll_wait 的过程:

  • 如果没有注册的 socket 事件触发, 则进程被挂到 struct eventpoll 的等待队列, 然后休眠:
    epoll_wait_sleep
    epoll_wait_sleep
  • 如果有注册的 socket 事件触发, 中断程序会唤醒 eventpoll 等待队列中的进程, 同时将目标 socket 挂到 eventpoll 的 rdllist 上并返回给目标进程:

整体事件/数据流

  • 事件流图:
    • 红色数字: 调用 epoll_wait 并被挂起的执行顺序;
    • 蓝色字母: socket 事件触发唤醒进程并返回结果的执行顺序;
      epoll_wait events flow
      epoll_wait events flow
       
  • 数据流图:
    • 有 socket 事件触发, 从 rbr 中查找是否有注册的 socket 事件与之匹配;
    • 匹配到了 socket 事件, 则将 rbr 上对应的 epitem 选出, 组装到 rdlist 链中返回给应用进程;
      epoll_wait data flow
      epoll_wait data flow

epoll 的触发模式

水平触发 (LT)

Level Trigger, 适合需要确保所有数据都被读取的场景:
当调用 epoll_wait 没有全部读完 socket 缓冲区, 下一次调用 epoll_wait 依然能够检测到 socket 就绪事件, 直到 socket 缓冲区数据被全部读完为止;

边缘触发 (ET)

Edge Trigger, 适合高效快速响应的场景:
当 socket 接收数据后, epoll rdlist 只会插入一次 socket 就绪事件, epoll_wait 检测到 socket 读事件后, 必须一次性把 socket 缓冲区数据全部读完, 否则数据可能丢失;

参考资料