epoll 的数据结构：红黑树、就绪队列与回调机制

epoll 系列阅读分工

推荐阅读路径：OS 58 速览 → 本篇 57 → 网络 67 工程 → io_uring 对比文。

2003 年，Davide Libenzi 向 Linux 内核提交了 epoll 补丁（fs/eventpoll.c，Linux 2.5.44 合入）。在那之前，select/poll 每次调用都要把整个 fd 集合拷贝进内核并线性扫描——连接数到十万级时，CPU 耗在「问谁就绪了」上。epoll 把监控集合留在内核，用回调在事件到达时入队，复杂度从「每次 O(n) 扫描」变为「wait 时 O(k)，k=就绪数」。

一、select/poll 的性能灾难

1.1 select 的实现

select 的签名暴露了它的设计缺陷：

int select(int nfds, fd_set *readfds, fd_set *writefds,
           fd_set *exceptfds, struct timeval *timeout);

fd_set 本质上是一个位图，大小固定为 FD_SETSIZE（通常是 1024）。每次调用 select，内核做以下事情：

1. 把三个 fd_set 从用户态拷贝到内核态——O(n) 的 copy_from_user。
2. 遍历 0 到 nfds 的每一个位，对每个被设置的 fd 调用该 fd 对应的 poll 方法检查就绪状态——O(n) 的扫描。
3. 如果没有就绪事件，将当前进程挂到所有被监控 fd 的等待队列上，然后睡眠。
4. 被唤醒后，再次执行步骤 2。
5. 把修改后的 fd_set 拷贝回用户态——又一次 O(n)。

问题在于：每次调用都是全量操作。 即使 10 万个连接中只有 3 个就绪，你也要拷贝 10 万个 bit，扫描 10 万个 fd。

1.2 poll 的改进与不足

poll 用链表替代了位图，去掉了 1024 的上限：

int poll(struct pollfd *fds, nfds_t nfds, int timeout);

struct pollfd {
    int fd;
    short events;   // 关注的事件
    short revents;  // 返回的事件
};

但核心问题没变——每次调用仍然要拷贝整个数组、线性扫描所有 fd。poll 只是把 select 的 1024 限制去掉了，渐近复杂度仍是 O(n)。

1.3 复杂度对比（非 benchmark）

不在正文写 QPS 绝对值：echo server 的 req/s 随 payload、CPU 频率、是否 ET、是否 SO_REUSEPORT 而变；应在本机用 wrk/vegeta 复现。网络篇 67｜epoll 深度剖析 讨论 ET/LT 编程差异；与 io_uring 的 syscall 模型对比见 epoll vs io_uring。

select/poll 在今天的合理场景：监控 fd 少于约 100 且不想引入 epoll 生命周期管理。超过这个范围，Linux 服务器默认选 epoll。

二、epoll 的三个系统调用

epoll 把”注册兴趣”和”等待事件”拆成了独立的操作。这个设计决策是它高性能的根源。

2.1 epoll_create：创建实例

int epoll_create(int size);    // size 参数已被忽略（历史遗留）
int epoll_create1(int flags);  // 推荐使用，flags 可传 EPOLL_CLOEXEC

epoll_create 在内核中创建一个 struct eventpoll 对象，并返回一个文件描述符指向它。没错，epoll 实例本身就是一个 fd——这意味着你可以把一个 epoll fd 放到另一个 epoll 实例中监控，甚至可以 poll 一个 epoll fd。

内核中 eventpoll 的核心结构（简化自 fs/eventpoll.c）：

struct eventpoll {
    spinlock_t lock;              // 保护就绪链表的自旋锁
    struct mutex mtx;             // 保护红黑树操作的互斥锁
    wait_queue_head_t wq;         // epoll_wait 的等待队列
    wait_queue_head_t poll_wait;  // 当 epoll fd 本身被 poll 时使用

    struct rb_root_cached rbr;    // 红黑树：存储所有被监控的 fd
    struct list_head rdllist;     // 就绪链表：存储有事件的 fd

    struct epitem *ovflist;       // 溢出链表（传输期间暂存）
    struct wakeup_source *ws;     // 用于 EPOLLWAKEUP
    struct user_struct *user;     // 创建者的用户信息
};

三个最关键的字段：rbr（红黑树）、rdllist（就绪链表）和 wq（等待队列）。后面会详细展开。

2.2 epoll_ctl：增删改监控项

int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);

op 可以是：

• EPOLL_CTL_ADD：把 fd 添加到监控集合（插入红黑树）。
• EPOLL_CTL_MOD：修改已有 fd 的监控事件。
• EPOLL_CTL_DEL：从监控集合中移除 fd（从红黑树删除）。

每次 EPOLL_CTL_ADD 都会创建一个 struct epitem，这是 epoll 内部表示一个”被监控的 fd”的数据结构：

struct epitem {
    struct rb_node rbn;            // 红黑树节点（用于挂到 eventpoll->rbr）
    struct list_head rdllink;      // 就绪链表节点（用于挂到 eventpoll->rdllist）
    struct epitem *next;           // 溢出链表指针
    struct epoll_filefd ffd;       // 被监控的 fd + file 指针
    int nwait;                     // 等待队列计数
    struct list_head pwqlist;      // poll 等待队列链表
    struct eventpoll *ep;          // 所属的 eventpoll
    struct epoll_event event;      // 用户注册的事件和数据
};

注意 epitem 同时包含了红黑树节点（rbn）和链表节点（rdllink）。这意味着一个 epitem 可以同时存在于红黑树中（表示”被监控”）和就绪链表中（表示”有事件”）。这是一种典型的 Linux 内核设计模式：把链接节点嵌入到数据结构中，而不是在外部分配包装器。

三个系统调用如何串成生命周期：

sequenceDiagram
  participant App as Application
  participant API as epoll syscalls
  participant EP as eventpoll
  participant Sock as socket waitqueue
  App->>API: epoll_create1
  API->>EP: alloc rbr rdllist wq
  API-->>App: epfd
  App->>API: epoll_ctl ADD fd
  API->>EP: insert epitem into rbr
  API->>Sock: register ep_poll_callback
  Note over Sock: later data arrives
  Sock->>EP: callback appends rdllist
  EP->>EP: wake_up wq
  App->>API: epoll_wait
  API->>EP: splice ready events
  API-->>App: events array

2.3 epoll_wait：等待事件

int epoll_wait(int epfd, struct epoll_event *events,
               int maxevents, int timeout);

epoll_wait 的实现非常简洁：

1. 检查 rdllist 是否为空。
2. 如果为空，把当前进程放到 wq 等待队列上，睡眠。
3. 如果非空（或被唤醒后发现非空），把 rdllist 中的事件拷贝到用户态的 events 数组。
4. 对于 LT 模式的 fd，如果事件仍然存在，重新插入 rdllist。

关键点：epoll_wait 不做任何扫描。 它只是看就绪链表有没有东西，有就取出来，没有就睡觉。所有的”谁就绪了”判断已经在回调中完成了。

三、红黑树：监控集合的存储

3.1 为什么选择红黑树

epoll 需要一个数据结构来存储所有被监控的文件描述符。这个数据结构需要满足几个要求：

1. 快速查找：EPOLL_CTL_MOD 和 EPOLL_CTL_DEL 需要根据 fd 找到对应的 epitem。
2. 快速插入/删除：EPOLL_CTL_ADD 和 EPOLL_CTL_DEL 要快。
3. 不允许重复：同一个 fd 不能注册两次（除非用 dup 创建的不同 file 描述）。
4. 有序不是必需的：不需要范围查询或顺序遍历。

候选方案的对比：

红黑树看起来不是最快的——哈希表的均摊 O(1) 更好。但 Linux 内核选择红黑树的原因很实际：

1. 最坏情况有界。内核代码不能接受均摊分析——一个哈希表 rehash 可能导致一次系统调用耗时几百毫秒，这在实时系统中是不可接受的。红黑树的每次操作严格 O(log n)，最坏情况可预测。
2. 不需要预估大小。哈希表需要选择桶数量，太小会退化，太大浪费内存。红黑树按需增长，没有这个问题。
3. 内核中已有成熟实现。lib/rbtree.c 是 Linux 内核中使用最广泛的数据结构之一，经过了十几年的优化和测试。CFS 调度器、内存管理的 VMA、ext4 的 extent tree 都用它。
4. 删除操作更稳定。AVL 树在删除时可能需要 O(log n) 次旋转，红黑树最多只需要 3 次旋转。对于频繁增删 fd 的场景，这个差异很重要。

3.2 红黑树的键

红黑树的比较键不是简单的 fd 数值，而是 (file *, fd) 的组合。为什么不能只用 fd？

因为 Linux 中 fd 只是进程级别的索引号，同一个底层 file 对象可以对应多个 fd（通过 dup/dup2），而不同的 file 对象也可能指向同一个 fd（通过 close + open 重用了 fd 号）。用 (file *, fd) 组合作为键可以精确标识一个打开的文件描述。

// 内核中 epitem 的比较函数（简化）
static inline int ep_cmp_ffd(struct epoll_filefd *p1,
                              struct epoll_filefd *p2)
{
    // 先比较 file 指针
    if (p1->file > p2->file)
        return 1;
    if (p1->file < p2->file)
        return -1;
    // file 相同则比较 fd
    return p1->fd - p2->fd;
}

3.3 红黑树操作的锁保护

红黑树操作（插入、删除、查找）受 eventpoll->mtx（互斥锁）保护。这是一个睡眠锁，因为红黑树操作可能涉及内存分配（kmalloc），而内存分配可能会睡眠。

注意这里用的是互斥锁而不是自旋锁——这意味着 epoll_ctl 可能会阻塞，但不会忙等。在高并发场景下，如果大量线程同时对同一个 epoll 实例调用 epoll_ctl，这个锁会成为瓶颈。这也是为什么一些高性能框架（比如早期的 Nginx）选择每个 worker 使用独立的 epoll 实例，而不是共享一个。

我的经验是：如果你的 fd 增删频率超过每秒 10 万次，考虑分片——用多个 epoll 实例，每个管理一部分 fd。

红黑树键不是裸 fd 整数，而是 (file *, fd)：

flowchart LR
  dupPath["dup / dup2"]
  sameFile["same struct file"]
  twoFds["fd=3 and fd=7"]
  keyA["key A: fileX + 3"]
  keyB["key B: fileX + 7"]
  rbr["rbr allows both epitems"]
  dupPath --> sameFile --> twoFds
  twoFds --> keyA --> rbr
  twoFds --> keyB --> rbr

close 后再 open 可能复用同一个数字 fd，但 file * 已变——键随之不同，避免把新旧打开混成同一个 epitem。

四、就绪链表与回调机制

4.1 就绪链表（rdllist）

eventpoll->rdllist 是一个标准的 Linux 内核双向链表（struct list_head），存储所有当前有事件的 epitem。

为什么用链表而不是其他数据结构？因为就绪链表的操作模式极其简单：

• 添加：回调函数把 epitem 追加到尾部——O(1)。
• 取出：epoll_wait 把整个链表”摘走”一次性处理——O(1) 的 list_splice。
• 不需要查找：不需要根据 fd 在就绪链表中查找任何东西。
• 不需要排序：就绪事件没有优先级。

链表在这里是完美的选择。任何更复杂的数据结构都是浪费。

4.2 回调函数 ep_poll_callback

这是 epoll 的核心机制。当通过 epoll_ctl 添加一个 fd 时，内核做了以下事情：

1. 创建一个 epitem，插入红黑树。
2. 调用该 fd 的 poll 方法（注意，这不是系统调用 poll，而是 file_operations->poll），传入一个等待队列入口（wait_queue_entry）。
3. 这个等待队列入口的回调函数被设置为 ep_poll_callback。

当 fd 上发生事件时（比如 TCP socket 收到数据，或者连接建立完成），内核的协议栈代码会唤醒该 fd 的等待队列。此时 ep_poll_callback 被调用：

// 简化版 ep_poll_callback
static int ep_poll_callback(wait_queue_entry_t *wait,
                            unsigned mode, int sync, void *key)
{
    struct epitem *epi = container_of(wait, struct eppoll_entry, wait)->base;
    struct eventpoll *ep = epi->ep;
    unsigned long flags;

    // 检查事件是否匹配用户关注的事件
    if (key && !((unsigned long)key & epi->event.events))
        return 1;

    spin_lock_irqsave(&ep->lock, flags);

    // 如果 epitem 不在就绪链表中，加入就绪链表
    if (!ep_is_linked(epi))
        list_add_tail(&epi->rdllink, &ep->rdllist);

    // 唤醒 epoll_wait 中等待的进程
    if (waitqueue_active(&ep->wq))
        wake_up_locked(&ep->wq);

    spin_unlock_irqrestore(&ep->lock, flags);

    return 1;
}

这段代码做了三件关键的事：

1. 检查事件类型是否匹配（通过 key 参数与用户注册的事件做按位与）。
2. 把 epitem 加入就绪链表（通过 list_add_tail，O(1) 操作）。注意 ep_is_linked 检查防止重复添加。
3. 唤醒 epoll_wait（通过 wake_up_locked）。

就绪链表的自旋锁 ep->lock 用的是 spin_lock_irqsave，会关中断。这是因为回调可能在中断上下文中被调用（比如网卡收到数据触发的软中断），此时不能睡眠，也不能被同级中断打断。

回调路径（相对 epoll_wait 的集中扫描）是：

sequenceDiagram
  participant NIC as NIC softirq
  participant Stack as protocol stack
  participant WQ as socket waitqueue
  participant CB as ep_poll_callback
  participant RL as rdllist
  participant Wait as epoll_wait sleeper
  NIC->>Stack: packet / accept ready
  Stack->>WQ: wake waiters
  WQ->>CB: invoke callback
  CB->>CB: match event mask
  CB->>RL: list_add_tail if not linked
  CB->>Wait: wake_up_locked

4.3 整体流程图

把用户态三次调用与内核数据结构串起来（结构总览仍见文首 epoll-architecture.svg）：

flowchart TB
  subgraph user [User space]
    create["epoll_create"]
    ctl["epoll_ctl ADD"]
    wait["epoll_wait"]
  end
  subgraph kernel [Kernel]
    ep["alloc eventpoll\nrbr + rdllist + wq"]
    item["create epitem\ninsert rbr O(log n)"]
    reg["register ep_poll_callback\non fd waitqueue"]
    evt["I/O event arrives"]
    cb["callback → rdllist O(1)\nwake wq"]
    copy["splice rdllist\ncopy k events to user"]
  end
  create --> ep
  ctl --> item --> reg
  evt --> cb
  wait --> copy
  cb -.->|"wakes"| wait

这就是 epoll 的”O(1)“来源：epoll_wait 本身只做链表摘取和内存拷贝，不做任何 fd 扫描。扫描工作被分摊到了每个 fd 各自的回调中——但回调是事件驱动的，只有真正就绪的 fd 才会触发回调。

我一直觉得这是一个非常优雅的设计：把工作从”集中式轮询”变成了”分布式回调”。每个 fd 自己负责在就绪时报到，而不是让一个中央调度器挨个询问。

4.4 溢出链表 ovflist

eventpoll->ovflist 是一个容易被忽略但很重要的细节。当 epoll_wait 正在把就绪链表中的事件传输到用户态时，它需要持有 ep->lock。但在这段时间内，新的事件回调可能发生。为了避免锁竞争，epoll 使用了一个巧妙的手法：

1. epoll_wait 开始传输前，把 ovflist 设置为非 EP_UNACTIVE_PTR。
2. 此后 ep_poll_callback 发现 ovflist 是活跃的，就不往 rdllist 中添加，而是追加到 ovflist 中（用 epi->next 单链表）。
3. epoll_wait 传输完成后，把 ovflist 中的所有 epitem 移到 rdllist 中。

这相当于一个双缓冲机制：读写分离，避免了生产者（回调）和消费者（epoll_wait）的锁竞争。

4.5 ep_send_events 与 LT/ET 的分叉点

epoll_wait 从 rdllist 摘取 epitem 后，由 ep_send_events（及 helper）决定事件如何返回用户态、以及 是否重新挂回就绪链表——这是 LT/ET 语义的内核落点：

• ET（EPOLLET）：返回后不再检查 fd 是否仍就绪；若应用未读到 EAGAIN，剩余数据可能「饿死」直到新数据到达触发下一次边缘。
• LT（默认）：返回前/后会再次调用 file 的 poll 方法；若仍就绪则 list_add_tail 回 rdllist，下次 epoll_wait 继续报告。

因此 ET 的性能收益来自减少重复就绪报告，代价是把「读尽」责任完全推给应用层——与网络篇 67｜ET/LT 编程范式 的工程结论一致，但根因在本节的内核路径。

五、ET 与 LT：两种触发模式

5.1 LT（Level-Triggered）模式

LT 是 epoll 的默认模式，语义与 select/poll 一致：只要 fd 处于就绪状态，每次 epoll_wait 都会返回这个 fd。

实现上，LT 模式在 epoll_wait 取出事件后做了一个额外操作：

// ep_send_events_proc 中的简化逻辑
if (epi->event.events & EPOLLET) {
    // ET 模式：不重新插入就绪链表
} else {
    // LT 模式：如果事件仍然存在，重新插入就绪链表
    if (revents & epi->event.events)
        list_add_tail(&epi->rdllink, &ep->rdllist);
}

LT 模式的好处是编程简单：你不需要一次读完所有数据，下次 epoll_wait 还会通知你。但代价是：如果你注册了一个 fd 却不处理它的数据，epoll_wait 会反复返回这个 fd，浪费 CPU。

5.2 ET（Edge-Triggered）模式

ET 模式只在状态变化时通知一次。“状态变化”的定义是：

• 从”不可读”变为”可读”（比如 socket 收到了新数据）。
• 从”不可写”变为”可写”（比如发送缓冲区从满变为有空间）。

如果 socket 缓冲区里还有未读数据，但没有新数据到达，ET 模式不会通知你。因此在 ET 模式下，你必须在收到通知后循环读取直到 EAGAIN：

// ET 模式下正确的读取方式
while (1) {
    ssize_t n = read(fd, buf, sizeof(buf));
    if (n < 0) {
        if (errno == EAGAIN || errno == EWOULDBLOCK)
            break;  // 所有数据已读完
        perror("read");
        break;
    }
    if (n == 0) {
        // 对端关闭连接
        close(fd);
        break;
    }
    process_data(buf, n);
}

如果你在 ET 模式下只读了一部分数据就返回了 epoll_wait，剩余的数据会一直待在缓冲区里，直到有新数据到达触发下一次通知。这是 ET 模式下最常见的 bug——数据饥饿。

5.3 ET vs LT 的实际性能差异

ET 减少了 epoll_wait 返回的事件数量，理论上更高效。但实际项目中差距不大——Nginx 用 ET，Redis 用 LT，两者都能处理百万级连接。选择更多是编程模型的偏好。

5.4 惊群问题与 EPOLLEXCLUSIVE

当多个线程/进程同时 epoll_wait 在同一个 epoll 实例上时，一个新连接到达会唤醒所有等待的线程。但只有一个线程能成功 accept，其他线程白白被唤醒——这就是惊群效应（thundering herd）。

LT 模式下情况更糟：即使一个线程已经 accept 了连接，其他线程的 epoll_wait 仍然会返回这个监听 fd（因为 LT 会重复报告就绪状态）。

Linux 4.5 引入了 EPOLLEXCLUSIVE 标志：

struct epoll_event ev;
ev.events = EPOLLIN | EPOLLEXCLUSIVE;
ev.data.fd = listen_fd;
epoll_ctl(epfd, EPOLL_CTL_ADD, listen_fd, &ev);

设置了 EPOLLEXCLUSIVE 后，当事件到达时，内核只唤醒等待队列中的一个线程（而不是全部）。这大幅减少了不必要的上下文切换。

Nginx 从 1.11.3 开始支持 EPOLLEXCLUSIVE，在配置文件中使用 accept_mutex off（默认已经关闭）配合内核的 EPOLLEXCLUSIVE 来避免惊群。在此之前，Nginx 用一个进程间互斥锁（accept_mutex）来串行化 accept 操作，效率低得多。

我的建议：如果你的目标内核版本 >= 4.5，直接用 EPOLLEXCLUSIVE，忘掉应用层的 accept_mutex 方案。

stateDiagram-v2
  [*] --> Listening
  Listening --> HerdWake: accept event without exclusive
  HerdWake --> OneWins: all threads race accept
  OneWins --> Listening: losers burn CPU
  Listening --> ExclusiveWake: EPOLLEXCLUSIVE
  ExclusiveWake --> OneWins2: single waiter runs accept
  OneWins2 --> Listening

六、epoll 与 io_uring 的对比

就绪模型与完成模型的机制对比、最小 C 示例与适用场景，见专文《Linux 异步 I/O：epoll 与 io_uring 对比》；io_uring 系列索引见 io_uring/index.html。

此处只保留与本篇内核结构相关的结论：

6.1 该选哪个

我的观点是：

• 纯网络服务（反向代理、网关、RPC 框架）：epoll 仍然是最安全的选择。稳定、成熟、所有发行版都支持。
• 混合 I/O 服务（数据库、文件服务器、日志收集）：io_uring 的异步磁盘 I/O 是真正的差异化优势。
• 极致性能追求（低延迟交易、定制网络栈）：可评估 io_uring，但须关注内核 CVE 历史与 liburing 版本（见 io_uring 对比文）。

6.2 开放问题

1. io_uring 能否在纯 TCP 代理场景稳定替代 epoll：公开 benchmark 口径不一，nginx/haproxy 主线仍以 epoll/kqueue 为主；break-even 依赖 payload 与是否 batch read。
2. EPOLL_EXCLUSIVE / SO_REUSEPORT 与 EPOLLONESHOT 的组合语义 在多 worker 框架中仍易踩坑（见网络 67 篇）。
3. 单 epoll 实例锁争用：极高 epoll_ctl 频率下是否应 per-CPU epoll——缺少独立于框架的系统性测量。
4. epoll_pwait2（若启用）与 timerfd 集成的精确定时 vs 忙等 trade-off，在 2025+ 内核中的默认推荐仍未写入 man 7 epoll。

七、完整实现：epoll echo server

事件循环骨架（与下文完整代码对应）：

flowchart TD
  start["epoll_create1 + listen socket"]
  addL["epoll_ctl ADD listen_fd EPOLLIN|EPOLLET"]
  loop["epoll_wait"]
  branch{"fd == listen_fd?"}
  acceptLoop["accept until EAGAIN"]
  clientLoop["read/write until EAGAIN"]
  err["EPOLLERR|EPOLLHUP → DEL + close"]
  start --> addL --> loop
  loop --> branch
  branch -->|yes| acceptLoop --> loop
  branch -->|no EPOLLIN| clientLoop --> loop
  loop --> err
  err --> loop

下面是一个生产级的 epoll echo server 实现，使用 ET 模式 + 非阻塞 I/O：

/*
 * epoll_echo_server.c - ET 模式 epoll echo server
 *
 * 编译: gcc -O2 -Wall -o echo_server epoll_echo_server.c
 * 运行: ./echo_server 9527
 * 测试: echo "hello" | nc localhost 9527
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <sys/epoll.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#define MAX_EVENTS  1024
#define BUF_SIZE    4096

static int set_nonblocking(int fd)
{
    int flags = fcntl(fd, F_GETFL, 0);
    if (flags < 0) return -1;
    return fcntl(fd, F_SETFL, flags | O_NONBLOCK);
}

static int create_listen_socket(int port)
{
    int lfd = socket(AF_INET, SOCK_STREAM, 0);
    if (lfd < 0) {
        perror("socket");
        return -1;
    }

    int opt = 1;
    setsockopt(lfd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt));
    setsockopt(lfd, SOL_SOCKET, SO_REUSEPORT, &opt, sizeof(opt));

    struct sockaddr_in addr;
    memset(&addr, 0, sizeof(addr));
    addr.sin_family = AF_INET;
    addr.sin_addr.s_addr = htonl(INADDR_ANY);
    addr.sin_port = htons(port);

    if (bind(lfd, (struct sockaddr *)&addr, sizeof(addr)) < 0) {
        perror("bind");
        close(lfd);
        return -1;
    }

    if (listen(lfd, SOMAXCONN) < 0) {
        perror("listen");
        close(lfd);
        return -1;
    }

    if (set_nonblocking(lfd) < 0) {
        perror("set_nonblocking");
        close(lfd);
        return -1;
    }

    return lfd;
}

static int epoll_add(int epfd, int fd, uint32_t events)
{
    struct epoll_event ev;
    ev.events = events;
    ev.data.fd = fd;
    if (epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &ev) < 0) {
        perror("epoll_ctl ADD");
        return -1;
    }
    return 0;
}

static void handle_accept(int epfd, int listen_fd)
{
    /* ET 模式下必须循环 accept 直到 EAGAIN */
    while (1) {
        struct sockaddr_in client_addr;
        socklen_t addr_len = sizeof(client_addr);

        int cfd = accept(listen_fd,
                         (struct sockaddr *)&client_addr, &addr_len);
        if (cfd < 0) {
            if (errno == EAGAIN || errno == EWOULDBLOCK)
                break;  /* 所有待处理的连接都已接受 */
            perror("accept");
            break;
        }

        char ip[INET_ADDRSTRLEN];
        inet_ntop(AF_INET, &client_addr.sin_addr, ip, sizeof(ip));
        printf("[+] new connection: %s:%d (fd=%d)\n",
               ip, ntohs(client_addr.sin_port), cfd);

        if (set_nonblocking(cfd) < 0) {
            close(cfd);
            continue;
        }

        /* 用 EPOLLIN | EPOLLET 监控客户端 fd */
        if (epoll_add(epfd, cfd, EPOLLIN | EPOLLET) < 0) {
            close(cfd);
            continue;
        }
    }
}

static void handle_client(int epfd, int fd)
{
    char buf[BUF_SIZE];

    /* ET 模式下必须循环读取直到 EAGAIN */
    while (1) {
        ssize_t nread = read(fd, buf, sizeof(buf));
        if (nread < 0) {
            if (errno == EAGAIN || errno == EWOULDBLOCK)
                break;  /* 所有数据已读完 */
            perror("read");
            goto close_conn;
        }
        if (nread == 0) {
            /* 对端关闭连接 */
            printf("[-] client disconnected (fd=%d)\n", fd);
            goto close_conn;
        }

        /* echo 回写，处理短写 */
        ssize_t total = 0;
        while (total < nread) {
            ssize_t nwrite = write(fd, buf + total, nread - total);
            if (nwrite < 0) {
                if (errno == EAGAIN || errno == EWOULDBLOCK) {
                    /*
                     * 写缓冲区满了。生产环境中应该：
                     * 1. 把未写完的数据存到用户态缓冲区
                     * 2. 注册 EPOLLOUT 事件
                     * 3. EPOLLOUT 触发时继续写
                     * 这里简化处理，直接丢弃剩余数据。
                     */
                    fprintf(stderr, "write buffer full, data truncated\n");
                    break;
                }
                perror("write");
                goto close_conn;
            }
            total += nwrite;
        }
    }
    return;

close_conn:
    epoll_ctl(epfd, EPOLL_CTL_DEL, fd, NULL);
    close(fd);
}

int main(int argc, char *argv[])
{
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <port>\n", argv[0]);
        return 1;
    }

    int port = atoi(argv[1]);
    if (port <= 0 || port > 65535) {
        fprintf(stderr, "Invalid port: %s\n", argv[1]);
        return 1;
    }

    /* 1. 创建监听 socket */
    int listen_fd = create_listen_socket(port);
    if (listen_fd < 0)
        return 1;

    /* 2. 创建 epoll 实例 */
    int epfd = epoll_create1(EPOLL_CLOEXEC);
    if (epfd < 0) {
        perror("epoll_create1");
        close(listen_fd);
        return 1;
    }

    /* 3. 将监听 fd 加入 epoll，使用 ET 模式 */
    if (epoll_add(epfd, listen_fd, EPOLLIN | EPOLLET) < 0) {
        close(listen_fd);
        close(epfd);
        return 1;
    }

    printf("Echo server listening on port %d (ET mode)\n", port);

    /* 4. 事件循环 */
    struct epoll_event events[MAX_EVENTS];

    for (;;) {
        int nfds = epoll_wait(epfd, events, MAX_EVENTS, -1);
        if (nfds < 0) {
            if (errno == EINTR)
                continue;  /* 被信号中断，重试 */
            perror("epoll_wait");
            break;
        }

        for (int i = 0; i < nfds; i++) {
            int fd = events[i].data.fd;
            uint32_t ev = events[i].events;

            /* 错误处理 */
            if (ev & (EPOLLERR | EPOLLHUP)) {
                if (fd == listen_fd) {
                    fprintf(stderr, "listen socket error\n");
                    goto cleanup;
                }
                fprintf(stderr, "error on fd=%d\n", fd);
                epoll_ctl(epfd, EPOLL_CTL_DEL, fd, NULL);
                close(fd);
                continue;
            }

            if (fd == listen_fd) {
                handle_accept(epfd, listen_fd);
            } else if (ev & EPOLLIN) {
                handle_client(epfd, fd);
            }
        }
    }

cleanup:
    close(listen_fd);
    close(epfd);
    return 0;
}

编译和测试：

gcc -O2 -Wall -o echo_server epoll_echo_server.c
./echo_server 9527

# 另一个终端
echo "hello epoll" | nc localhost 9527

代码中的几个关键设计决策

1. 监听 socket 也用 ET 模式。这意味着 handle_accept 必须循环 accept 直到 EAGAIN。如果不这样做，多个连接同时到达时可能只 accept 了一个，其余的连接请求会丢失（直到下一个新连接触发 ET 通知）。

2. SO_REUSEPORT。允许多个进程绑定同一个端口，内核在 TCP 层做负载均衡。这比 EPOLLEXCLUSIVE 更彻底——每个进程有自己的监听 socket 和 accept 队列，完全没有争用。

3. EPOLL_CLOEXEC。确保 fork 后子进程不会继承 epoll fd。这是一个防御性编程的好习惯——忘记加这个标志导致的 fd 泄漏是非常难调试的。

4. 写操作的简化处理。生产环境中，当 write 返回 EAGAIN 时，应该把未写完的数据放入用户态写缓冲区，注册 EPOLLOUT 事件，等写缓冲区可用时再继续写。本示例为简洁省略了这部分逻辑。

八、性能特征与可伸缩性

8.1 各操作的时间复杂度

关键洞察：epoll_wait 的复杂度只与就绪事件数 k 有关，而不是监控的总 fd 数 n。 这就是为什么即使监控 10 万个 fd，只要活跃连接不多，epoll_wait 依然很快。

flowchart LR
  subgraph selectPath [select_poll]
    nAll["pay O(n) every wait"]
  end
  subgraph epollPath [epoll]
    ctlCost["ctl O(log n) on change"]
    waitCost["wait O(k) ready only"]
  end
  nAll -.->|"idle fds still scanned"| waste["wasted work"]
  ctlCost --> waitCost
  waitCost -->|"idle fds silent"| ok["stable under many idle conns"]

8.2 内存开销

每个被监控的 fd 在内核中占用一个 epitem 结构，大小约 128-160 字节（取决于内核版本和配置）。监控 10 万个 fd 大约需要 12-16 MB 的内核内存。

epoll 还有一个 per-user 限制 /proc/sys/fs/epoll/max_user_watches，默认约 40 万。监控更多 fd 需要调大此值。

8.3 可伸缩性瓶颈

epoll 的性能不是无限的。以下是我在实践中遇到的几个瓶颈：

1. 单个 epoll 实例的锁争用。epoll_ctl 需要获取互斥锁修改红黑树，ep_poll_callback 需要获取自旋锁修改就绪链表。当监控的 fd 非常多且事件频繁时，这些锁可能成为瓶颈。解决方案：分片，每个线程/CPU 核心一个 epoll 实例。

2. 用户态内存拷贝。epoll_wait 需要把就绪事件从内核拷贝到用户态。如果一次返回上千个事件，这个拷贝开销不可忽视。io_uring 的共享内存方案完全消除了这个开销。

3. 缓存污染。当活跃连接数很多时，epoll_wait 返回大量事件，处理这些事件时会访问大量不相关的内存地址（不同连接的缓冲区），导致 CPU 缓存频繁失效。

8.4 调优参数

# 系统级/进程级 fd 上限
cat /proc/sys/fs/file-max
ulimit -n

# epoll 监控上限
cat /proc/sys/fs/epoll/max_user_watches

# TCP 连接相关
cat /proc/sys/net/core/somaxconn
cat /proc/sys/net/ipv4/tcp_max_syn_backlog
cat /proc/sys/net/ipv4/ip_local_port_range

九、工程陷阱速查表

以下是我和同事在生产环境中踩过的坑，整理成表格供参考：

关于 close 与 EPOLL_CTL_DEL 的关系

一个常见误解是”close(fd) 就够了，不需要 EPOLL_CTL_DEL”。简单场景下确实如此。但如果 fd 通过 dup/fork 被复制过，close 一个副本不会触发 epoll 的自动清理——只有当所有指向同一 file 对象的 fd 都关闭后，epitem 才被移除。

我的建议：永远显式 EPOLL_CTL_DEL，不要依赖 close 的隐式清理。

十、从源码到直觉：个人思考

epoll 的设计哲学

回顾 epoll 的三个数据结构，我看到的是一个非常清晰的职责划分：

flowchart TB
  rbr["rbr red-black tree\nwho do I monitor"]
  rdllist["rdllist ready list\nwho has events now"]
  cb["ep_poll_callback\nbridge from fd wakeups"]
  cb -->|"append O(1)"| rdllist
  rbr -->|"epitem identity"| cb

• 红黑树负责”我监控了谁”——这是一个静态的注册表，变化频率低（连接建立和断开时才修改），但需要快速查找和去重。红黑树完美匹配。
• 就绪链表负责”谁有事件了”——这是一个动态的事件队列，变化频率高（每个数据包到达都可能触发），但只需要追加和批量摘取。双向链表完美匹配。
• 回调函数是连接两者的桥梁——它把”fd 就绪”这个内核事件翻译成”epitem 入队”这个 epoll 操作。

这种”注册一次，通知多次”的模式在系统设计中随处可见：数据库的触发器、消息队列的订阅、UI 框架的事件绑定，本质都是同一个思想。epoll 只是把它在操作系统层面实现得特别精致。

为什么理解内部实现很重要

有人说”用好 API 就够了，不需要知道内部实现”。我不同意。理解 epoll 的内部实现至少带来三个好处：

1. 调试能力。当你的服务 CPU 100% 而 QPS 没变时，如果你知道 LT 模式下 EPOLLHUP 会导致忙循环，你能在 5 分钟内定位问题。否则你可能花一整天在 perf 里大海捞针。

2. 设计决策。当你需要在 ET 和 LT 之间选择、在单 epoll 实例和多实例之间选择时，理解红黑树的锁和就绪链表的机制能帮你做出有根据的决定，而不是盲从 StackOverflow 上的建议。

3. 跨领域迁移。epoll 的红黑树+链表+回调模式在很多其他系统中出现：kqueue 的 knote、Windows 的 IOCP、甚至游戏引擎的事件系统。理解一个，触类旁通。

一个时代的终结？

epoll 已经 20 年了。io_uring 正在改变 Linux I/O 的格局。但我不认为 epoll 会很快消失。就像 TCP 没有被 QUIC 取代一样，成熟的技术有巨大的惯性。

更重要的是，epoll 的设计思想——“用合适的数据结构解决合适的问题”——永远不会过时。红黑树用于有序集合，链表用于 FIFO 队列，回调用于异步通知，这些基本模式会一直存在，只是穿着不同的外衣出现在不同的系统中。

理解 epoll，不是为了写出下一个 Nginx（虽然也不是不行），而是为了在面对任何”如何高效处理大量并发事件”的问题时，脑子里有一个经过 20 年实战验证的参考架构。

参考资料

规范 / 手册

• Linux man 7 epoll、man 2 epoll_create1、man 2 epoll_ctl、man 2 epoll_wait
• EPOLLEXCLUSIVE：man 7 epoll（Linux 4.5+）

源码

• Linux 内核 fs/eventpoll.c（struct eventpoll、struct epitem、ep_poll_callback）
• Linux 内核 lib/rbtree.c

论文 / 技术报告

• Davide Libenzi, epoll — scalable I/O event notification mechanism, 2002/2003（合入 Linux 2.5.44）

实验 / 工具 / 站内

• strace -e epoll_ctl,epoll_wait、bpftrace/ftrace 跟踪 ep_poll_callback
• 67｜epoll 深度剖析 · 58｜epoll 内部
• epoll 与 io_uring 对比 · io_uring 系列索引
• 红黑树与 AVL 树

上一篇: 文件系统的树 下一篇: 定时器算法