【C/C】用户态协议栈如何实现 epoll红黑树、就绪队列和回调通知1. 为什么用户态协议栈也需要 epoll如果协议栈完全运行在用户态那么内核的socket、recv、send、epoll_wait都不能直接代表这套协议栈里的连接。原因很简单连接状态、接收队列、发送队列都在用户态自己的数据结构里。内核不知道你的ng_tcp_stream什么时候收到了数据也不知道你的rcvbuf什么时候变成非空。所以用户态协议栈要么提供一套自己的 API例如nsocket();nbind();nlisten();naccept();nsend();nrecv();nepoll_create();nepoll_ctl();nepoll_wait();要么做更复杂的兼容层把应用无感迁移过去。这个示例选择了前者用n*前缀实现教学版 socket/epoll。2. eventpoll关注集合 就绪队列 条件变量Linux 内核 epoll 的核心概念可以简化成两部分关注集合应用通过epoll_ctl(ADD/MOD/DEL)注册自己关心哪些 fd。就绪队列当某个 fd 真的可读/可写时把它放到 ready listepoll_wait返回它。示例代码也是这个思路。代码片段来自ustack-main/tcp_concurrency.cstructepitem{RB_ENTRY(epitem)rbn;LIST_ENTRY(epitem)rdlink;intrdy;intsockfd;structepoll_eventevent;};RB_HEAD(_epoll_rb_socket,epitem);RB_GENERATE_STATIC(_epoll_rb_socket,epitem,rbn,sockfd_cmp);typedefstruct_epoll_rb_socketep_rb_tree;structeventpoll{intfd;ep_rb_tree rbr;intrbcnt;LIST_HEAD(,epitem)rdlist;intrdnum;intwaiting;pthread_mutex_tmtx;pthread_spinlock_tlock;pthread_cond_tcond;pthread_mutex_tcdmtx;};这里有三个关键字段rbr红黑树保存“我关注了哪些 sockfd”。rdlist就绪链表保存“哪些 sockfd 已经有事件”。cond条件变量nepoll_wait()没事件时阻塞有事件时被唤醒。为什么关注集合用红黑树因为epoll_ctl和协议栈回调都需要按 sockfd 快速查找epitem。链表也能做但连接数一多线性查找会拖慢路径。3. nepoll_create创建用户态 eventpollnepoll_create()的职责是分配一个用户态 epoll 对象并给它分配一个 fd。intnepoll_create(intsize){if(size0)return-1;intepfdget_fd_frombitmap();structeventpoll*ep(structeventpoll*)rte_malloc(eventpoll,sizeof(structeventpoll),0);if(!ep){set_fd_frombitmap(epfd);return-1;}structng_tcp_table*tabletcpInstance();table-epep;ep-fdepfd;ep-rbcnt0;RB_INIT(ep-rbr);LIST_INIT(ep-rdlist);pthread_mutex_init(ep-mtx,NULL);pthread_mutex_init(ep-cdmtx,NULL);pthread_cond_init(ep-cond,NULL);pthread_spin_init(ep-lock,PTHREAD_PROCESS_SHARED);returnepfd;}这个实现里有一个教学上很直观的设计table-ep ep。也就是说TCP 协议栈表能直接找到当前 epoll 对象。后面 TCP 收到新连接或数据时就可以调用epoll_event_callback()通知等待者。真实工程中可能会有多个 epoll 实例、多线程归属、fd 到 epoll 的反向索引等更复杂的问题。这个示例先把最小闭环跑通了。4. nepoll_ctl把 sockfd 加入关注集合nepoll_ctl()的 ADD 操作本质是创建epitem然后插入红黑树。intnepoll_ctl(intepfd,intop,intsockid,structepoll_event*event){structeventpoll*ep(structeventpoll*)get_hostinfo_fromfd(epfd);if(!ep||(!eventop!EPOLL_CTL_DEL)){errno-EINVAL;return-1;}if(opEPOLL_CTL_ADD){pthread_mutex_lock(ep-mtx);structepitemtmp;tmp.sockfdsockid;structepitem*epiRB_FIND(_epoll_rb_socket,ep-rbr,tmp);if(epi){pthread_mutex_unlock(ep-mtx);return-1;}epi(structepitem*)rte_malloc(epitem,sizeof(structepitem),0);epi-sockfdsockid;memcpy(epi-event,event,sizeof(structepoll_event));RB_INSERT(_epoll_rb_socket,ep-rbr,epi);ep-rbcnt;pthread_mutex_unlock(ep-mtx);}return0;}这一段对应内核 epoll 里的“兴趣列表”。注意它只是表示“我关心这个 sockfd 的事件”并不代表事件已经发生。5. 协议栈回调把关注项移动到就绪队列真正让 epoll 动起来的是回调函数。intepoll_event_callback(structeventpoll*ep,intsockid,uint32_tevent){structepitemtmp;tmp.sockfdsockid;structepitem*epiRB_FIND(_epoll_rb_socket,ep-rbr,tmp);if(!epi){printf(rbtree not exist\n);return-1;}if(epi-rdy){epi-event.events|event;return1;}pthread_spin_lock(ep-lock);epi-rdy1;LIST_INSERT_HEAD(ep-rdlist,epi,rdlink);ep-rdnum;pthread_spin_unlock(ep-lock);pthread_mutex_lock(ep-cdmtx);pthread_cond_signal(ep-cond);pthread_mutex_unlock(ep-cdmtx);}这段逻辑对应四步sockid - 红黑树查 epitem - 如果已在 ready list只合并事件 - 如果不在 ready list插入 rdlist - signal 条件变量唤醒 nepoll_wait也就是说nepoll_wait()不负责轮询每个 socket 是否有数据。它只等rdlist。协议栈在“状态真的变化”时主动把事件送进去。这就是 epoll 相比普通轮询更高效的关键。6. nepoll_wait没事件就睡有事件就拷贝返回nepoll_wait()的阻塞逻辑用条件变量完成。intnepoll_wait(intepfd,structepoll_event*events,intmaxevents,inttimeout){structeventpoll*ep(structeventpoll*)get_hostinfo_fromfd(epfd);if(!ep||!events||maxevents0){rte_errno-EINVAL;return-1;}pthread_mutex_lock(ep-cdmtx);while(ep-rdnum0timeout!0){ep-waiting1;if(timeout0){structtimespecdeadline;clock_gettime(CLOCK_REALTIME,deadline);deadline.tv_nsectimeout*1000000;pthread_cond_timedwait(ep-cond,ep-cdmtx,deadline);timeout0;}elseif(timeout0){pthread_cond_wait(ep-cond,ep-cdmtx);}ep-waiting0;}pthread_mutex_unlock(ep-cdmtx);pthread_spin_lock(ep-lock);intcnt0;intnum(ep-rdnummaxevents?maxevents:ep-rdnum);while(num!0!LIST_EMPTY(ep-rdlist)){structepitem*epiLIST_FIRST(ep-rdlist);LIST_REMOVE(epi,rdlink);epi-rdy0;memcpy(events[cnt],epi-event,sizeof(structepoll_event));num--;ep-rdnum--;}pthread_spin_unlock(ep-lock);returncnt;}这里可以对应标准 epoll 的三个 timeout 语义timeout 0一直等。timeout 0不等马上返回。timeout 0最多等指定毫秒数。这个示例实现的是最小模型已经能说明 epoll 的主干机制关注集合不等于就绪队列就绪队列由协议栈事件驱动。7. TCP 在哪里触发 EPOLLIN用户态 epoll 的事件来源不是内核而是 TCP 状态机。当三次握手完成后监听 socket 应该变成可读因为accept()可以拿到新连接。示例代码在SYN_RCVD收到 ACK 后触发staticintng_tcp_handle_syn_rcvd(structng_tcp_stream*stream,structrte_tcp_hdr*tcphdr){if(tcphdr-tcp_flagsRTE_TCP_ACK_FLAG){if(stream-statusNG_TCP_STATUS_SYN_RCVD){stream-statusNG_TCP_STATUS_ESTABLISHED;structng_tcp_stream*listenerng_tcp_stream_search(0,0,0,stream-dport);pthread_mutex_lock(listener-mutex);pthread_cond_signal(listener-cond);pthread_mutex_unlock(listener-mutex);structng_tcp_table*tabletcpInstance();epoll_event_callback(table-ep,listener-fd,EPOLLIN);}}return0;}当连接已经建立收到PSH数据时连接 socket 应该变成可读staticintng_tcp_handle_established(structng_tcp_stream*stream,structrte_tcp_hdr*tcphdr,inttcplen){if(tcphdr-tcp_flagsRTE_TCP_PSH_FLAG){ng_tcp_enqueue_recvbuffer(stream,tcphdr,tcplen);structng_tcp_table*tabletcpInstance();epoll_event_callback(table-ep,stream-fd,EPOLLIN);}return0;}这两处就是 epoll 和 TCP 状态机的连接点三次握手完成 - listener fd 可读 - accept 不再阻塞 收到 PSH 数据 - stream fd 可读 - recv 不再阻塞8. 应用侧怎么用单 epoll 版本的 TCP server 入口大致是这样intlistenfdnsocket(AF_INET,SOCK_STREAM,0);structsockaddr_inservaddr;servaddr.sin_familyAF_INET;servaddr.sin_addr.s_addrhtonl(INADDR_ANY);servaddr.sin_porthtons(9999);nbind(listenfd,(structsockaddr*)servaddr,sizeof(servaddr));nlisten(listenfd,10);intepfdnepoll_create(1);structepoll_eventev,events[128];ev.eventsEPOLLIN;ev.data.fdlistenfd;nepoll_ctl(epfd,EPOLL_CTL_ADD,listenfd,ev);while(1){intnreadynepoll_wait(epfd,events,128,-1);for(inti0;inready;i){if(events[i].data.fdlistenfd){intconnfdnaccept(listenfd,NULL,NULL);ev.eventsEPOLLIN;ev.data.fdconnfd;nepoll_ctl(epfd,EPOLL_CTL_ADD,connfd,ev);}else{charbuffer[1024]{0};nrecv(events[i].data.fd,buffer,sizeof(buffer),0);nsend(events[i].data.fd,buffer,strlen(buffer),0);}}}这段 API 形式和普通 Linux epoll 很像但底层已经完全变了普通epoll_wait等内核 fd。这里的nepoll_wait等用户态协议栈自己的 fd。普通recv从内核 socket buffer 取数据。这里的nrecv从ng_tcp_stream-rcvbuf取数据。9. 这个教学实现还缺什么这份代码适合学习 epoll 骨架但离工程级实现还有距离只展示了单 epoll 思路多 epoll 实例和多线程归属还需要设计。EPOLLET、EPOLLONESHOT等语义没有完整展开。事件合并、错误事件、关闭事件的边界还可以继续补齐。TCP 本身也缺少完整重传、拥塞控制、乱序重排、滑动窗口等机制。内存释放和异常路径要更严格否则长时间运行容易泄漏。但作为学习材料它已经把最关键的主线讲清楚了epoll_ctl 注册 sockfd - 红黑树保存关注集合 - TCP/UDP 收到数据后触发 callback - callback 插入就绪队列并 signal - epoll_wait 拷贝就绪事件返回应用10. 总结用户态协议栈里的 epoll本质上不是“调用一下内核 epoll”而是自己维护事件系统。核心数据结构是eventpoll ├── rbr: 关注集合红黑树 ├── rdlist: 就绪队列链表 ├── cond: 阻塞和唤醒 epoll_wait └── lock/mtx: 保护并发访问核心事件流是协议栈收到报文 - 更新 TCP/UDP 接收缓冲 - 调用 epoll_event_callback - epitem 进入 rdlist - nepoll_wait 被唤醒 - 应用处理 accept/recv/send看懂这一层之后再去读内核 epoll、mTCP、F-Stack、Seastar 这类框架会更容易抓住主线高性能网络框架的核心不是“多线程 非阻塞”这几个词而是数据到达时事件如何从协议栈准确、高效地传递到应用。学习链接: https://github.com/0voice