Based on my session search, the following CS topics have already been pushed:
- RCU (covered twice)
- False Sharing
- Branch Prediction
- Register Renaming
- eBPF Verifier
- Redis Skip List (covered twice)
- Thompson NFA Construction
- ABA Problem
- Git internals

I need a fresh topic. Let me write about epoll's internal data structures — it bridges data structures, OS, and source code reading, and hasn't been covered.

epoll 里那棵红黑树是干嘛的

用 epoll_wait 监听十万个连接的时候，你大概不会去想那些 fd 被存在了哪里。但翻开 Linux 内核 fs/eventpoll.c，会发现每个 epoll 实例的核心是两个数据结构：一棵红黑树和一个双向链表。红黑树存所有被注册的 fd，链表存已经有事件就绪的 fd。epoll_ctl(EPOLL_CTL_ADD) 把新 fd 插入红黑树，O(log n)；epoll_wait 直接从就绪链表上摘节点，O(1)。这个分工是整个设计的关键——红黑树负责"找得到"，就绪链表负责"直接拿"。

为什么不用哈希表？因为 fd 的取值范围可以从 0 到几百万，哈希表要么留大量空桶浪费内存，要么频繁扩容引发内核里的内存分配麻烦。红黑树只用每个节点一小块 epitem 结构体，插入删除都是确定性 O(log n)，不需要额外调 kmalloc 做桶扩展。为什么不用数组线性扫描？那就是 select 和 poll 的老路了——每次都要把整个 fd 集合从用户空间拷进内核再扫一遍，十万个 fd 的时候这个开销是灾难级的。

就绪链表的填充过程才是真正精巧的地方。内核收到网卡中断后，在软中断处理函数里判断 socket 是否有数据可读。如果有，就把这个 socket 对应的 epitem 挂上就绪链表（用的是 list_add_tail，一行代码），同时唤醒在 epoll 实例等待队列上睡眠的进程。epoll_wait 醒来后直接遍历就绪链表，把事件拷贝到用户空间，不需要扫描整棵红黑树。这就是事件驱动和轮询的本质差距——你不用去找事件，事件来找你。

还有个容易搞混的细节：水平触发（LT）和边沿触发（ET）的行为差异就体现在就绪链表上。LT 模式下，如果一个 fd 的缓冲区还有数据没读完，每次 epoll_wait 都会把它重新挂回就绪链表；ET 模式下，只有状态变化的那一瞬间入队一次，之后不管你读没读完都不再通知。所以 ET 必须配合非阻塞 I/O 循环读到 EAGAIN 为止，漏读就是丢事件。两种模式各有场景：LT 是安全默认，ET 配合事件循环框架是高并发标配。

epoll_waitmax_events

下次用 strace -e trace=epoll_wait,epoll_ctl 看 nginx worker，你会发现 epoll_ctl 的调用远少于 epoll_wait——因为树只需要建一次，而链表在每次事件到来时自动维护自身。

#CS