|
作者:dustinzhou,腾讯 IEG 运营开发工程师2 I) u" [" B+ L* Z$ y" r
epoll 是 linux 特有的一个 I/O 事件通知机制。很久以来对 epoll 如何能够高效处理数以百万记的文件描述符很有兴趣。近期学习、研究了 epoll 源码,在这个过程中关于 epoll 数据结构和作者的实现思路产生出不少疑惑,在此总结为了 10 个问题并逐个加以解答和分析。 本文基于的内核源码版本是2.6.39 版本 。
$ @5 v9 A' P% g/ MQuestion 1: 是否所有的文件类型都可以被 epoll 监视?
* c1 x2 h8 K$ @; z/ L8 G) z0 [, @( ]
答案:不是。 看下面这个实验代码:3 z: `& b4 T: j' C" K
#include <stdio.h>#include <unistd.h>#include <sys/epoll.h>#include <stdlib.h>#include <sys/types.h>#include <sys/stat.h>#include <fcntl.h>#include <errno.h>#define MAX_EVENTS 1int main (void){ int epfd; epfd = epoll_create(100); /* 创建epoll实例,预计监听100个fd */ if (epfd < 0) { perror ("epoll_create"); } struct epoll_event *events; int nr_events, i; events = malloc (sizeof (struct epoll_event) * MAX_EVENTS); if (!events) { perror("malloc"); return 1; } /* 打开一个普通文本文件 */ int target_fd = open ("./11.txt", O_RDONLY); printf("target_fd %d\n", target_fd); int target_listen_type = EPOLLIN; for (i = 0; i < 1; i++) { int ret; events.data.fd = target_fd; /* epoll调用返回后,返回给应用进程的fd号 */ events.events = target_listen_type; /* 需要监听的事件类型 */ ret = epoll_ctl (epfd, EPOLL_CTL_ADD, target_fd, &events); /* 注册fd到epoll实例上 */ if (ret) { printf("ret %d, errno %d\n", ret, errno); perror ("epoll_ctl"); } } /* 应用进程阻塞在epoll上,超时时长置为-1表示一直等到有目标事件才会返回 */ nr_events = epoll_wait(epfd, events, MAX_EVENTS, -1); if (nr_events < 0) { perror ("epoll_wait"); free(events); return 1; } for (i = 0; i < nr_events; i++) { /* 打印出处于就绪状态的fd及其事件 */ printf("event=%d on fd=%d\n", events.events, events.data.fd); } free (events); close(epfd); return 0;}编译、运行上面的代码,会打印出下列信息:2 G0 `7 A9 ^$ K* y
gcc epoll_test.c -o epdemo./epdemotarget_fd 4ret -1, errno 1epoll_ctl: Operation not permitted正常打开了"txt"文件 fd=4, 但调用 epoll_ctl 监视这个 fd 时却 ret=-1 失败了, 并且错误码为 1,错误信息为"Operation not permitted"。错误码指明这个 fd 不能够被 epoll 监视。
1 |0 k; p. k/ S0 y5 V; e \1 c那什么样的 fd 才可以被 epoll 监视呢?( g1 r, X0 ^' Y b1 A. {
只有底层驱动实现了 file_operations 中 poll 函数的文件类型才可以被 epoll 监视!socket 类型的文件驱动是实现了 poll 函数的,因此才可以被 epoll 监视。struct file_operations 声明位置是在 include/linux/fs.h 中。
8 ^" G* x* s5 \, n! E- {5 v" G( E' ~$ lQuestion 2: ep->wq 的作用是什么?$ i7 G! e; \( P* t4 T: @2 A
, l. \. ?! m& n答案:wq 是一个等待队列,用来保存对某一个 epoll 实例调用 epoll_wait()的所有进程。8 S! W# D, b8 u/ n, w6 U
一个进程调用 epoll_wait()后,如果当前还没有任何事件发生,需要让当前进程挂起等待(放到 ep->wq 里);当 epoll 实例监视的文件上有事件发生后,需要唤醒 ep->wq 上的进程去继续执行用户态的业务逻辑。之所以要用一个等待队列来维护关注这个 epoll 的进程,是因为有时候调用 epoll_wait()的不只一个进程,当多个进程都在关注同一个 epoll 实例时,休眠的进程们通过这个等待队列就可以逐个被唤醒了。
% L" G& A* O5 i$ o) D# x4 ]' `# V多个进程关注同一个 epoll 实例,那么有事件发生后先唤醒谁?后唤醒谁?还是一起全唤醒?这涉及到一个称为“惊群效应”的问题。. \: P/ e7 L2 R' j& E( |* G0 ~
Question 3: 什么是 epoll 惊群?% j+ s1 Z7 v' j' u6 Q0 \
. i" H- m7 D" @& I9 C1 Y" T& u0 ~答案:多个进程等待在 ep->wq 上,事件触发后所有进程都被唤醒,但只有其中 1 个进程能够成功继续执行的现象。其他被白白唤起的进程等于做了无用功,可能会造成系统负载过高的问题。 下面这段代码能够直观感受什么是 epoll 惊群:5 }- Q/ V s; G1 D4 W
#include <sys/types.h>#include <sys/socket.h>#include <sys/epoll.h>#include <netdb.h>#include <string.h>#include <stdio.h>#include <unistd.h>#include <fcntl.h>#include <stdlib.h>#include <errno.h>#include <sys/wait.h>#define PROCESS_NUM 10static int create_and_bind (char *port){ int fd = socket(PF_INET, SOCK_STREAM, 0); struct sockaddr_in serveraddr; serveraddr.sin_family = AF_INET; serveraddr.sin_addr.s_addr = htonl(INADDR_ANY); serveraddr.sin_port = htons(atoi(port)); bind(fd, (struct sockaddr*)&serveraddr, sizeof(serveraddr)); return fd;}static int make_socket_non_blocking (int sfd){ int flags, s; flags = fcntl (sfd, F_GETFL, 0); if (flags == -1) { perror ("fcntl"); return -1; } flags |= O_NONBLOCK; s = fcntl (sfd, F_SETFL, flags); if (s == -1) { perror ("fcntl"); return -1; } return 0;}#define MAXEVENTS 64int main (int argc, char *argv[]){ int sfd, s; int efd; struct epoll_event event; struct epoll_event *events; sfd = create_and_bind("8001"); if (sfd == -1) abort (); s = make_socket_non_blocking (sfd); if (s == -1) abort (); s = listen(sfd, SOMAXCONN); if (s == -1) { perror ("listen"); abort (); } efd = epoll_create(MAXEVENTS); if (efd == -1) { perror("epoll_create"); abort(); } event.data.fd = sfd; //event.events = EPOLLIN | EPOLLET; event.events = EPOLLIN; s = epoll_ctl(efd, EPOLL_CTL_ADD, sfd, &event); if (s == -1) { perror("epoll_ctl"); abort(); } /* Buffer where events are returned */ events = calloc(MAXEVENTS, sizeof event); int k; for(k = 0; k < PROCESS_NUM; k++) { int pid = fork(); if(pid == 0) { /* The event loop */ while (1) { int n, i; n = epoll_wait(efd, events, MAXEVENTS, -1); printf("process %d return from epoll_wait!\n", getpid()); for (i = 0; i < n; i++) { if ((events.events & EPOLLERR) || (events.events & EPOLLHUP) || (!(events.events & EPOLLIN))) { /* An error has occured on this fd, or the socket is not ready for reading (why were we notified then?) */ fprintf (stderr, "epoll error\n"); close (events.data.fd); continue; } else if (sfd == events.data.fd) { /* We have a notification on the listening socket, which means one or more incoming connections. */ struct sockaddr in_addr; socklen_t in_len; int infd; char hbuf[NI_MAXHOST], sbuf[NI_MAXSERV]; in_len = sizeof in_addr; infd = accept(sfd, &in_addr, &in_len); if (infd == -1) { printf("process %d accept failed!\n", getpid()); break; } printf("process %d accept successed!\n", getpid()); /* Make the incoming socket non-blocking and add it to the list of fds to monitor. */ close(infd); } } } } } int status; wait(&status); free (events); close (sfd); return EXIT_SUCCESS;}将服务端的监听 socket fd 加入到 epoll_wait 的监视集合中,这样当有客户端想要建立连接,就会事件触发 epoll_wait 返回。此时如果 10 个进程同时在 epoll_wait 同一个 epoll 实例就出现了惊群效应。所有 10 个进程都被唤起,但只有一个能成功 accept。
3 A2 |9 c& r' a' o H7 {
B' X# D" ~! ~6 }
精华总结:10个问题理解 Linux epoll
2 {& L9 K8 b+ U9 l为了解决 epoll 惊群,内核后续的高版本又提供了 EPOLLEXCLUSIVE 选项和 SO_REUSEPORT 选项,我个人理解两种解决方案思路上的不同点在于:EPOLLEXCLUSIVE 是在唤起进程阶段起作用,只唤起排在队列最前面的 1 个进程;而 SO_REUSEPORT 是在分配连接时起作用,相当于每个进程自己都有一个独立的 epoll 实例,内核来决策把连接分配给哪个 epoll。: Y1 n4 h! t/ Y# v* ~! n
Question 4: ep->poll_wait 的作用是什么?
8 l( q8 ~, @& ?5 ]* x. h' g* ^9 [+ x2 p `* o
答案:ep->poll_wait 是 epoll 实例中另一个等待队列。当被监视的文件是一个 epoll 类型时,需要用这个等待队列来处理递归唤醒。
- A9 u8 G1 \% S# \/ e% m在阅读内核代码过程中,ep->wq 还算挺好理解,但我发现伴随着 ep->wq 唤醒, 还有一个 ep->poll_wait 的唤醒过程。比如下面这段代码,在 eventpoll.c 中出现了很多次:0 c/ D; C% ?5 v* I/ d0 a
/* If the file is already "ready" we drop it inside the ready list */ if ((revents & event->events) && !ep_is_linked(&epi->rdllink)) { list_add_tail(&epi->rdllink, &ep->rdllist); /* Notify waiting tasks that events are available */ if (waitqueue_active(&ep->wq)) wake_up_locked(&ep->wq); if (waitqueue_active(&ep->poll_wait)) pwake++; } spin_unlock_irqrestore(&ep->lock, flags); atomic_long_inc(&ep->user->epoll_watches); /* We have to call this outside the lock */ if (pwake) ep_poll_safewake(&ep->poll_wait);查阅很多资料后才搞明白其实 epoll 也是一种文件类型,其底层驱动也实现了 file_operations 中的 poll 函数,因此一个 epoll 类型的 fd 可以被其他 epoll 实例监视。而 epoll 类型的 fd 只会有“读就绪”的事件。当 epoll 所监视的非 epoll 类型文件有“读就绪”事件时,当前 epoll 也会进入“读就绪”状态。
6 | i* f2 p' N7 Y) h因此如果一个 epoll 实例监视了另一个 epoll 就会出现递归。举个例子,如图所示:" @' a: h i3 F3 q
5 ~$ _, c9 D5 E8 v
精华总结:10个问题理解 Linux epoll
( s# @7 W! S c5 h. c' _0 I
* p* N ]! x/ c9 @. g# |3 k
epollfd1 监视了 2 个“非 epoll”类型的 fd epollfd2 监视了 epollfd1 和 2 个“非 epoll”类型的 fd
' @1 D& Z$ l- B: s7 ^* d, A 如果 epollfd1 所监视的 2 个 fd 中有可读事件触发,fd 的 ep_poll_callback 回调函数会触发将 fd 放到 epollfd1 的 rdllist 中。此时 epollfd1 本身的可读事件也会触发,就需要从 epollfd1 的 poll_wait 等待队列中找到 epollfd2,调用 epollfd1 的 ep_poll_callback(将 epollfd1 放到 epollfd2 的 rdllist 中)。因此 ep->poll_wait 是用来处理 epoll 间嵌套监视的情况的。+ I1 i' y2 d" o+ K) w
Question 5: ep->rdllist 的作用是什么?0 _3 |# J- e* r
' T% g; O/ |2 H5 T
答案:epoll 实例中包含就绪事件的 fd 组成的链表。
) v7 |" x& Q2 `/ Y \* u通过扫描 ep->rdllist 链表,内核可以轻松获取当前有事件触发的 fd。而不是像 select()/poll() 那样全量扫描所有被监视的 fd,再从中找出有事件就绪的。因此可以说这一点决定了 epoll 的性能是远高于 select/poll 的。. H \ w9 O+ ~0 k# v/ ]
看到这里你可能又产生了一个小小的疑问:为什么 epoll 中事件就绪的 fd 会“主动”跑到 rdllist 中去,而不用全量扫描就能找到它们呢? 这是因为每当调用 epoll_ctl 新增一个被监视的 fd 时,都会注册一下这个 fd 的回调函数 ep_poll_callback, 当网卡收到数据包会触发一个中断,中断处理函数再回调 ep_poll_callback 将这个 fd 所属的“epitem”添加至 epoll 实例中的 rdllist 中。
8 c& e! S# r6 P6 Y5 I; E) \0 \Question 6: ep->ovflist 的作用是什么?! ]* k- `% `0 r. D
9 Z5 O0 F3 S. v4 g: ?答案:在 rdllist 被占用时,用来在不持有 ep->lock 的情况下收集有就绪事件的 fd。
: k. |8 G( P% t3 z/ p; \当 epoll 上已经有了一些就绪事件的时候,内核需要扫描 rdllist 将就绪的 fd 返回给用户态。这一步通过 ep_scan_ready_list 函数来实现。其中 sproc 是一个回调函数(也就是 ep_send_events_proc 函数),来处理数据从内核态到用户态的复制。4 e* z8 a u- n" H0 T: I5 @
/** * ep_scan_ready_list - Scans the ready list in a way that makes possible for the scan code, to call f_op->poll(). Also allows for O(NumReady) performance. * @ep: Pointer to the epoll private data structure. * @sproc: Pointer to the scan callback. * @priv: Private opaque data passed to the @sproc callback. * Returns: The same integer error code returned by the @sproc callback. */static int ep_scan_ready_list(struct eventpoll *ep, int (*sproc)(struct eventpoll *, struct list_head *, void *), void *priv)由于 rdllist 链表业务非常繁忙(epoll 增加监视文件、修改监视文件、有事件触发...等情况都需要操作 rdllist),所以在复制数据到用户空间时,加了一个 ep->mtx 互斥锁来保护 epoll 自身数据结构线程安全,此时其他执行流程里有争抢 ep->mtx 的操作都会因命中 ep->mtx 进入休眠。* \- x0 l) a+ a& a# D; k
但加锁期间很可能有新事件源源不断地产生,进而调用 ep_poll_callback(ep_poll_callback 不用争抢 ep->mtx 所以不会休眠),新触发的事件需要一个地方来收集,不然就丢事件了。这个用来临时收集新事件的链表就是 ovflist。我的理解是:引入 ovflist 后新产生的事件就不用因为想向 rdllist 里写而去和 ep_send_events_proc 争抢自旋锁(ep->lock), 同时 ep_send_events_proc 也可以放心大胆地在无锁(不持有 ep->lock)的情况下修改 rdllist。
& m/ }" r7 L3 P- v7 `7 Z, b- D看代码时会发现,还有一个 txlist 链表,这个链表用来最后向用户态复制数据,rdllist 要先把自己的数据全部转移到 txlist,然后 rdllist 自己被清空。ep_send_events_proc 遍历 txlist 处理向用户空间复制,复制成功后如果是水平触发(LT)还要把这个事件还回 rdllist,等待下一次 epoll_wait 来获取它。
: m# q7 _! ?& ~6 p( \. z1 Eovflist 上的 fd 会合入 rdllist 上等待下一次扫描;如果 txlist 上的 fd 没有处理完,最后也会合入 rdllist。这 3 个链表的关系是这样:
5 O: |4 j) ^, S4 `/ Y2 u v5 V- _: M* ?( T
精华总结:10个问题理解 Linux epoll
# u6 ?' B C7 J( n; _( N6 m, E
Question 7: epitem->pwqlist 队列的作用是什么?/ T/ _$ w% \1 h# J/ w+ z9 F
) e/ D% b1 G. K, H. g答案:用来保存这个 epitem 的 poll 等待队列。+ M7 T4 O& J* ]/ X3 D
首先介绍下什么是 epitem。epitem 是 epoll 中很重要的一种数据结构, 是红黑树和 rdllist 的基本组成元素。需要监听的文件和事件信息,都被包装在 epitem 结构里。" P# V' C7 Z# \' i. x& h8 G
struct epitem { struct rb_node rbn; // 用于加入红黑树 struct list_head rdllink; // 用于加入rdllist struct epoll_filefd ffd; // 包含被监视文件的文件指针和fd信息 struct list_head pwqlist; // poll等待队列 struct eventpoll *ep; // 所属的epoll实例 struct epoll_event event; // 关注的事件 /* 其他成员省略 */};回忆一下上文说到,每当用户调用 epoll_ctl()新增一个监视文件,都要给这个文件注册一个回调函数 ep_poll_callback, 当网卡收到数据后软中断会调用这个 ep_poll_callback 把这个 epitem 加入到 ep->rdllist 中。
# S* D4 B# j1 [" l' b' p1 npwdlist 就是跟 ep_poll_callback 注册相关的。
7 s2 U% F9 Y( x# O' |; G1 D( o* n当调用 epoll_ctl()新增一个监视文件后,内核会为这个 epitem 创建一个 eppoll_entry 对象,通过 eppoll_entry->wait_queue_t->wait_queue_func_t 来设置 ep_poll_callback。pwdlist 为什么要做成一个队列呢,直接设置成 eppoll_entry 对象不就行了吗?实际上不同文件类型实现 file_operations->poll 用到等待队列数量可能不同。虽然大多数都是 1 个,但也有例外。比如“scullpipe”类型的文件就用到了 2 个等待队列。& ]2 q2 r& l% g8 ^& O
pwqlist、epitem、fd、epoll_entry、ep_poll_callback 间的关系是这样:
% L. i* }7 d; r$ V a* T a" r' G, R% S( {! Y
精华总结:10个问题理解 Linux epoll
3 h/ m' ^, s2 L9 U: r
Question 8: epmutex、ep->mtx、ep->lock 3 把锁的区别是?
( d) y) h# M/ B6 `3 D: E0 K. [! w1 @+ y) k) u
答案:锁的粒度和使用目的不同。# c- @; y8 N5 {
- o' e# E& y* Y* e" m3 Fepmutex 是一个全局互斥锁,epoll 中一共只有 3 个地方用到这把锁。分别是 ep_free() 销毁一个 epoll 实例时、eventpoll_release_file() 清理从 epoll 中已经关闭的文件时、epoll_ctl() 时避免 epoll 间嵌套调用时形成死锁。我的理解是 epmutex 的锁粒度最大,用来处理跨 epoll 实例级别的同步操作。 ep->mtx 是一个 epoll 内部的互斥锁,在 ep_scan_ready_list() 扫描就绪列表、eventpoll_release_file() 中执行 ep_remove()删除一个被监视文件、ep_loop_check_proc()检查 epoll 是否有循环嵌套或过深嵌套、还有 epoll_ctl() 操作被监视文件增删改等处有使用。可以看出上述的函数里都会涉及对 epoll 实例中 rdllist 或红黑树的访问,因此我的理解是 ep->mtx 是一个 epoll 实例内的互斥锁,用来保护 epoll 实例内部的数据结构的线程安全。 ep->lock 是一个 epoll 实例内部的自旋锁,用来保护 ep->rdllist 的线程安全。自旋锁的特点是得不到锁时不会引起进程休眠,所以在 ep_poll_callback 中只能使用 ep->lock,否则就会丢事件。 ; n4 |) }+ P0 s E. p+ y5 d4 Y
Question 9: epoll 使用红黑树的目的是什么?/ f y4 X: L+ f# G
: d/ D6 s' A: x( K
答案:用来维护一个 epoll 实例中所有的 epitem。; f) i: t) Q9 ] W3 L" X
用户态调用 epoll_ctl()来操作 epoll 的监视文件时,需要增、删、改、查等动作有着比较高的效率。尤其是当 epoll 监视的文件数量达到百万级的时候,选用不同的数据结构带来的效率差异可能非常大。
2 H% _% P' [: E4 L- h& k+ ~) B9 L! n" ~# q9 Y( X* P
精华总结:10个问题理解 Linux epoll
) B R% e& [) ]/ e- }+ w# W" n
数据结构& p- v# W+ B( t7 c) |2 Y
| 特点$ g% T$ a. k1 w$ ~
| ( n1 k" b7 z+ B8 }9 F
从时间(增、删、改、查、按序遍历)、空间(存储空间大小、扩展性)等方面考量,红黑树都是非常优秀的数据结构(当然这以红黑树比较高的实现复杂度作为代价)。 epoll 红黑树中的 epitem 是按什么顺序组织的。阅读代码可以发现是先比较 2 个文件指针的地址大小,如果相同再比较文件 fd 的大小。
: b, N0 s% E/ Z/* Compare RB tree keys */static inline int ep_cmp_ffd(struct epoll_filefd *p1, struct epoll_filefd *p2){ return (p1->file > p2->file ? +1 : (p1->file < p2->file ? -1 : p1->fd - p2->fd));}epoll、epitem、和红黑树间的组织关系是这样:
: J6 v8 R5 o5 z- u* U' h$ M; E+ L9 g6 j
精华总结:10个问题理解 Linux epoll
! a6 b& s: _4 y- L
Question 10: 什么是水平触发、边缘触发?
3 f0 s. P8 s$ B$ N% N" |3 w% Y1 z7 }* w- D; p
答案:水平触发(LT)和边缘触发(ET)是 epoll_wait 的 2 种工作模式。 水平触发:关注点是数据(读操作缓冲区不为空,写操作缓冲区不为满),epoll_wait 总会返回就绪。LT 是 epoll 的默认工作模式。
4 x$ T( |9 ]) J) N- L% v边缘触发:关注点是变化,只有监视的文件上有数据变化发生(读操作关注有数据写进缓冲区,写操作关注数据从缓冲区取走),epoll_wait 才会返回。2 H+ [% X0 o. M5 g- j' D. M
看一个实验 ,直观感受下 2 种模式的区别, 客户端都是输入“abcdefgh” 8 个字符,服务端每次接收 2 个字符。6 h1 h$ R& U1 s
水平触发时,客户端输入 8 个字符触发了一次读就绪事件,由于被监视文件上还有数据可读故一直返回读就绪,服务端 4 次循环每次都能取到 2 个字符,直到 8 个字符全部读完。" d- Z5 u7 U/ K+ ]
) g; a& W# v. ~5 `! Q* \& D
精华总结:10个问题理解 Linux epoll
- |& o# w6 D% f+ L9 s. V9 n
; K( D% I$ c5 L& R, P m
精华总结:10个问题理解 Linux epoll
- l4 Q* _& Y2 L8 Y5 j) J- J边缘触发时,客户端同样输入 8 个字符但服务端一次循环读到 2 个字符后这个读就绪事件就没有了。等客户端再输入一个字符串后,服务端关注到了数据的“变化”继续从缓冲区读接下来的 2 个字符“c”和”d”。
9 }" Y( @/ F* ^8 N: g. V* d, ~
9 g. O% z' V6 u0 U
精华总结:10个问题理解 Linux epoll
* Z. e3 l/ ~5 M8 X6 H5 k7 k l
* b! F/ Z0 v& W, O) ?# m7 T
精华总结:10个问题理解 Linux epoll
2 E, d* `5 ~/ \1 x% [小结; v$ g& o# P, r$ E$ W' [) x6 W
( [$ |# p0 |9 j# `4 z
本文通过 10 个问题,其实也是从 10 个不同的视角去观察 epoll 这间宏伟的殿堂。至此也基本介绍完了 epoll 从监视事件,到内部数据结构组织、事件处理,最后到 epoll_wait 返回的整体工作过程。 最后附上一张 epoll 相关数据结构间的关系图,在学习 epoll 过程中它曾解答了我心中不少的疑惑,我愿称之为灯塔~) q" k+ G, j& c
/ J3 e+ m! e$ u7 k& C1 \2 ]
精华总结:10个问题理解 Linux epoll
1 [# k$ y1 K' g4 X8 i参考资料
1 q( P% k& }% O0 Q. E: u) S5 G5 Y! F: |# B" g! m+ }
Implementation of Epoll Red-black Trees (rbtree) in Linux What is the purpose of epoll's edge triggered option? epoll 源码分析(基于 linux-5.1.4) epoll 实现原理 epoll (2) source code analysis epoll 的内核实现 Linux Kernel Notes: epoll Implementation Principle accept 与 epoll 惊群 # x1 z7 }0 L! K1 ]/ d+ v% e1 y
6 v2 T6 s0 ^0 S- L( R }1 p8 B原文链接:腾讯技术工程|关注整站优化网 学习更多SEO相关方法... |
|