基于版本:Linux 5.4
1. epoll 简介
epoll
是Linux内核中的一种可扩展IO事件处理机制,最早在 Linux 2.5.44内核中引入,可被用于代替POSIX select 和 poll 系统调用,并且在具有大量应用程序请求时能够获得较好的性能( 此时被监视的文件描述符数目非常大,与旧的 select 和 poll 系统调用完成操作所需 O(n) 不同, epoll能在O(1)时间内完成操作,所以性能相当高),epoll 与 FreeBSD的kqueue类似,都向用户空间提供了自己的文件描述符来进行操作。
2. select 和 poll
在linux 没有实现epoll事件驱动机制之前,我们一般选择用select或者poll等IO多路复用的方法来实现并发服务程序。在大数据、高并发、集群等一些名词唱得火热之年代,select和poll的用武之地越来越有限,风头已经被epoll占尽。
select的缺点:
(1)单个进程能够监视的文件描述符的数量存在最大限制,通常是1024,当然可以更改数量,但由于select采用轮询的方式扫描文件描述符,文件描述符数量越多,性能越差;(在linux内核头文件中,有这样的定义:#define __FD_SETSIZE 1024)
(2)内核 / 用户空间内存拷贝问题,select需要复制大量的句柄数据结构,产生巨大的开销;
(3)select返回的是含有整个句柄的数组,应用程序需要遍历整个数组才能发现哪些句柄发生了事件;
(4)select的触发方式是水平触发,应用程序如果没有完成对一个已经就绪的文件描述符进行IO操作,那么之后每次select调用还是会将这些文件描述符通知进程。
相比select模型,poll使用链表保存文件描述符,因此没有了监视文件数量的限制,但其他三个缺点依然存在。拿select模型为例,假设我们的服务器需要支持100万的并发连接,则在__FD_SETSIZE 为1024的情况下,则我们至少需要开辟1k个进程才能实现100万的并发连接。除了进程间上下文切换的时间消耗外,从内核/用户空间大量的无脑内存拷贝、数组轮询等,是系统难以承受的。因此,基于select模型的服务器程序,要达到10万级别的并发访问,是一个很难完成的任务。因此,该epoll上场了。
3. epoll 重要实现
3.1 epoll_create 函数
int epoll_create(int size);
创建一个epoll的句柄,size用来告诉内核需要监听的数目一共有多大。当创建好epoll句柄后,它就是会占用一个fd值,在linux下如果查看/proc/进程id/fd/,是能够看到这个fd的,所以在使用完epoll后,必须调用close() 关闭,否则可能导致fd被耗尽。
在内核中,每个epoll 实例会有一个struct eventpoll 类型的对象一一对应,该对象时epoll 的核心,声明在 fs/eventpoll.c 文件中:
struct eventpoll {
...
/* Wait queue used by sys_epoll_wait() */
wait_queue_head_t wq;
/* Wait queue used by file->poll() */
wait_queue_head_t poll_wait;
/* List of ready file descriptors */
struct list_head rdllist;
/* Lock which protects rdllist and ovflist */
rwlock_t lock;
/* RB tree root used to store monitored fd structs */
struct rb_root_cached rbr;
/*
* This is a single linked list that chains all the "struct epitem" that
* happened while transferring ready events to userspace w/out
* holding ->lock.
*/
struct epitem *ovflist;
/* wakeup_source used when ep_scan_ready_list is running */
struct wakeup_source *ws;
/* The user that created the eventpoll descriptor */
struct user_struct *user;
struct file *file;
...
};
epoll_create 在内核中实现的代码见 do_epoll_create():
- step1,首先是创建一个struct eventpoll对象:
struct eventpoll *ep = NULL;
...
error = ep_alloc(&ep);
if (error < 0)
return error;
- step2,然后分配一个未使用的fd:
fd = get_unused_fd_flags(O_RDWR | (flags & O_CLOEXEC));
if (fd < 0) {
error = fd;
goto out_free_ep;
}
- step3,再创建一个struct file,用以与fd 对应:
file = anon_inode_getfile("[eventpoll]", &eventpoll_fops, ep,
O_RDWR | (flags & O_CLOEXEC));
- step4,将上面创建好的file,存放到eventpoll 中的file 指针中,同时将file->private_data 指向eventpoll 对象ep:
ep->file = file;
- step5,最后将未使用的fd 和创建好的file 进行绑定:
fd_install(fd, file);
总结大致如下:
- 对于每个进程都会拥有一个struct task_struct 管理所有的files、memory等;
- task_struct 对象中有个成员为struct file_struct 对象,用以管理进程所有文件描述符;
- 新创建的struct file 会与未使用的fd进行绑定,并存放在fdtable 中的struct file数组中;
- 新创建的struct file就是epoll 文件,其中的private_data 指向eventpoll 这个epoll 的核心结构体;
3.2 epoll_ctl 函数
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
epoll的事件注册函数,第一个参数是 epoll_create() 的epoll 文件的描述符,即epoll fd,第二个参数表示动作,使用如下三个宏来表示
- EPOLL_CTL_ADD //注册新的fd到epfd中;
- EPOLL_CTL_MOD //修改已经注册的fd的监听事件
- EPOLL_CTL_DEL //从epfd中删除一个fd;
第三个参数是需要监听的fd,第四个参数是告诉内核需要监听什么事,struct epoll_event 结构如下:
typedef union epoll_data
{
void *ptr;
int fd;
__uint32_t u32;
__uint64_t u64;
} epoll_data_t;
struct epoll_event {
__uint32_t events; /* Epoll events */
epoll_data_t data; /* User data variable */
};
其中成员events 可以是以下几个宏的集合:
- EPOLLIN //表示对应的文件描述符可以读(包括对端SOCKET正常关闭)
- EPOLLOUT //表示对应的文件描述符可以写
- EPOLLPRI //表示对应的文件描述符有紧急的数据可读(这里应该表示有带外数据到来)
- EPOLLERR //表示对应的文件描述符发生错误
- EPOLLHUP //表示对应的文件描述符被挂断
- EPOLLET //将EPOLL设为边缘触发(Edge Triggered)模式,这是相对于水平触发(Level Triggered)来说的。
- EPOLLONESHOT//只监听一次事件,当监听完这次事件之后,如果还需要继续监听这个socket的话,需要再次把这个socket加入到EPOLL队列里。
当对方关闭连接(FIN), EPOLLERR,都可以认为是一种EPOLLIN事件,在read的时候分别有0,-1两个返回值。
在内核中epoll_ctl 同样实现在fs/eventpoll.c 文件中:
SYSCALL_DEFINE4(epoll_ctl, int, epfd, int, op, int, fd,
struct epoll_event __user *, event)
{
int error;
int full_check = 0;
struct fd f, tf;
struct eventpoll *ep;
struct epitem *epi;
struct epoll_event epds;
struct eventpoll *tep = NULL;
...
}
- step1,如果不是del 命令,则需要进行一个用户空间的copy:
if (ep_op_has_event(op) &&
copy_from_user(&epds, event, sizeof(struct epoll_event)))
goto error_return;
- step2,传入参数的过滤,确认参数是否有效
f = fdget(epfd); //1. 确认传入的epoll fd是否有效
if (!f.file)
goto error_return;
/* Get the "struct file *" for the target file */
tf = fdget(fd); //2. 确认传入需要监听的fd 是否有效
if (!tf.file)
goto error_fput;
/* The target file descriptor must support poll */
error = -EPERM;
if (!file_can_poll(tf.file)) //3. 确认需要监听的fd是否可以poll
goto error_tgt_fput;
/* Check if EPOLLWAKEUP is allowed */
if (ep_op_has_event(op)) //4. 确认event 是否可以唤醒
ep_take_care_of_epollwakeup(&epds);
/*
* We have to check that the file structure underneath the file descriptor
* the user passed to us _is_ an eventpoll file. And also we do not permit
* adding an epoll file descriptor inside itself.
*/
error = -EINVAL;
if (f.file == tf.file || !is_file_epoll(f.file)) //5. 需要监听的fd,不能是epoll 本身
goto error_tgt_fput;
大致情况可见代码中的注释,一共5次确认。
其中第 3 次确认,即确认需要监听的fd 是否可以poll,主要依赖file_operations 中poll 成员的设定。也就是说file 的poll 成员没有设定时,该文件是不允许epoll的。
至于哪些fd 可以使用epoll 进行监听,详细看第 4 节。
- step3,接下来判断用户是否设置了EPOLLEXCLUSIVE标志,这个标志是4.5版本内核才有的,主要是为了解决同一个文件描述符同时被添加到多个epoll实例中造成的“惊群”问题。这个标志的设置有一些限制条件,比如只能是在EPOLL_CTL_ADD操作中设置,而且对应的文件描述符本身不能是一个epoll实例,下面代码就是对这些限制的检查:
/*
* epoll adds to the wakeup queue at EPOLL_CTL_ADD time only,
* so EPOLLEXCLUSIVE is not allowed for a EPOLL_CTL_MOD operation.
* Also, we do not currently supported nested exclusive wakeups.
*/
if (ep_op_has_event(op) && (epds.events & EPOLLEXCLUSIVE)) {
if (op == EPOLL_CTL_MOD)
goto error_tgt_fput;
if (op == EPOLL_CTL_ADD && (is_file_epoll(tf.file) ||
(epds.events & ~EPOLLEXCLUSIVE_OK_BITS)))
goto error_tgt_fput;
}
- step4,获取struct eventpoll 对象:
ep = f.file->private_data;
- step5,如果要添加的文件描述符本身也代表一个epoll实例,那么有可能会造成死循环,内核对此情况做了检查,如果存在死循环则返回错误。
if (op == EPOLL_CTL_ADD) {
if (!list_empty(&f.file->f_ep_links) ||
ep->gen == loop_check_gen ||
is_file_epoll(tf.file)) {
full_check = 1;
mutex_unlock(&ep->mtx);
mutex_lock(&epmutex);
if (is_file_epoll(tf.file)) {
error = -ELOOP;
if (ep_loop_check(ep, tf.file) != 0)
goto error_tgt_fput;
} else {
get_file(tf.file);
list_add(&tf.file->f_tfile_llink,
&tfile_check_list);
}
mutex_lock_nested(&ep->mtx, 0);
if (is_file_epoll(tf.file)) {
tep = tf.file->private_data;
mutex_lock_nested(&tep->mtx, 1);
}
}
}
- step6,接下来会从epoll实例的红黑树里寻找和被监控文件对应的epollitem对象,如果不存在,也就是之前没有添加过该文件,返回的会是NULL。
epi = ep_find(ep, tf.file, fd);
ep_find()函数本质是一个红黑树查找过程,红黑树查找和插入使用的比较函数是ep_cmp_ffd(),先比较struct file对象的地址大小,相同的话再比较文件描述符大小。struct file对象地址相同的一种情况是通过dup()系统调用将不同的文件描述符指向同一个struct file对象。
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));
}
- step7,接下来会根据操作符op的不同做不同的处理,这里我们只看op等于EPOLL_CTL_ADD时的添加操作。首先会判断上一步操作中返回的epollitem对象地址是否为NULL,不是NULL说明该文件已经添加过了,返回错误,否则调用ep_insert()函数进行真正的添加操作。在添加文件之前内核会自动为该文件增加POLLERR和POLLHUP事件。
case EPOLL_CTL_ADD:
if (!epi) {
epds.events |= EPOLLERR | EPOLLHUP;
error = ep_insert(ep, &epds, tf.file, fd, full_check);
} else
error = -EEXIST;
break;
ep_insert()返回之后会判断full_check标志,该标志和上文提到的死循环检测相关,这里也略去。
3.2.1 ep_insert
本节接上面EPOLL_CTL_ADD,最终会调用到ep_insert 进行实际的添加。
- step1,首先判断epoll 实例中监视的文件数量是否超过限制,如果没有则创建epitem:
user_watches = atomic_long_read(&ep->user->epoll_watches);
if (unlikely(user_watches >= max_user_watches))
return -ENOSPC;
if (!(epi = kmem_cache_alloc(epi_cache, GFP_KERNEL)))
return -ENOMEM;
- step2,对epitem 进行初始化:
/* Item initialization follow here ... */
INIT_LIST_HEAD(&epi->rdllink);
INIT_LIST_HEAD(&epi->fllink);
INIT_LIST_HEAD(&epi->pwqlist);
epi->ep = ep;
ep_set_ffd(&epi->ffd, tfile, fd);
epi->event = *event;
epi->nwait = 0;
epi->next = EP_UNACTIVE_PTR;
if (epi->event.events & EPOLLWAKEUP) {
error = ep_create_wakeup_source(epi);
if (error)
goto error_create_wakeup_source;
} else {
RCU_INIT_POINTER(epi->ws, NULL);
- step3,将epitem中的fllink字段添加到struct file中的f_ep_links链表中,这样就可以通过struct file找到所有对应的struct epitem对象,进而通过struct epitem找到所有的epoll实例对应的struct eventpoll:
/* Add the current item to the list of active epoll hook for this file */
spin_lock(&tfile->f_lock);
list_add_tail_rcu(&epi->fllink, &tfile->f_ep_links);
spin_unlock(&tfile->f_lock);
- step4,将epitem 插入到红黑树中:
/*
* Add the current item to the RB tree. All RB tree operations are
* protected by "mtx", and ep_insert() is called with "mtx" held.
*/
ep_rbtree_insert(ep, epi);
- step5,接下来是比较重要的操作:将epollitem对象添加到被监视文件的等待队列上去。等待队列实际上就是一个回调函数链表,定义在include/linux/wait.h文件中。因为不同文件系统的实现不同,无法直接通过struct file对象获取等待队列,因此这里通过struct file的poll操作,以回调的方式返回对象的等待队列,这里设置的回调函数是ep_ptable_queue_proc:
struct ep_pqueue epq;
...
/* Initialize the poll table using the queue callback */
epq.epi = epi;
init_poll_funcptr(&epq.pt, ep_ptable_queue_proc);
/*
* Attach the item to the poll hooks and get current event bits.
* We can safely use the file* here because its usage count has
* been increased by the caller of this function. Note that after
* this operation completes, the poll callback can start hitting
* the new item.
*/
revents = ep_item_poll(epi, &epq.pt, 1);
上面代码中结构体ep_queue的作用是能够在poll的回调函数中取得对应的epollitem对象,这种做法在Linux内核里非常常见。
在回调函数ep_ptable_queue_proc中,内核会创建一个struct eppoll_entry对象,然后将等待队列中的回调函数设置为ep_poll_callback()。也就是说,当被监控文件有事件到来时,比如socker收到数据时,ep_poll_callback()会被回调。ep_ptable_queue_proc()代码如下:
static void ep_ptable_queue_proc(struct file *file, wait_queue_head_t *whead,
poll_table *pt)
{
struct epitem *epi = ep_item_from_epqueue(pt);
struct eppoll_entry *pwq;
if (epi->nwait >= 0 && (pwq = kmem_cache_alloc(pwq_cache, GFP_KERNEL))) {
init_waitqueue_func_entry(&pwq->wait, ep_poll_callback);
pwq->whead = whead;
pwq->base = epi;
if (epi->event.events & EPOLLEXCLUSIVE)
add_wait_queue_exclusive(whead, &pwq->wait);
else
add_wait_queue(whead, &pwq->wait);
list_add_tail(&pwq->llink, &epi->pwqlist);
epi->nwait++;
} else {
/* We have to signal that an error occurred */
epi->nwait = -1;
}
}
eppoll_entry和epitem等结构关系如下图:
根据上面情况总结一个结构图:
3.3 epoll_wait 函数
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);
参数events用来从内核得到事件的集合,maxevents 告之内核这个events有多大,这个 maxevents 的值不能大于创建 epoll_create() 时的size,参数 timeout 是超时时间(毫秒,0会立即返回,-1将不确定,也有说法说是永久阻塞)。该函数返回需要处理的事件数目,如返回0表示已超时。
4. 可以使用epoll 的fd
首先说,类似 ext2,ext4,xfs 这种常规的文件系统是没有实现的,换句话说,这些你最常见的、真的是文件的文件系统反倒是用不了 epoll 机制的。
那谁支持呢?
最常见的就是网络套接字:socket 。网络也是 epoll 池最常见的应用地点。
net/socket.c
static const struct file_operations socket_file_ops = {
.owner = THIS_MODULE,
.llseek = no_llseek,
.read_iter = sock_read_iter,
.write_iter = sock_write_iter,
.poll = sock_poll,
socket 实现了 poll 调用,所以 socket fd 是天然可以放到 epoll 池管理的。
Linux 下还有两个很典型的 fd (当然linux 中不止这两个fd,例如PSI fd),常常也会放到 epoll 池里:
- eventfd:eventfd 实现非常简单,故名思义就是专门用来做事件通知用的。使用系统调用 eventfd 创建,这种文件 fd 无法传输数据,只用来传输事件,常常用于生产消费者模式的事件实现;
- timeFd:这是一种定时器 fd,使用 timerfd_create 创建,到时间点触发可读事件;
小结一下:
- ext2,ext4,xfs 等这种真正的文件系统的 fd ,无法使用 epoll 管理;
- socket fd,eventfd,timerfd 这些实现了 poll 调用的可以放到 epoll 池进行管理;
5. 触发方式
在函数epoll_ctl 中会选择epoll 的触发方式,使用水平触发(LT)还是边沿触发(ET)。
- LT(level triggered)是缺省的工作方式,并且同时支持block和no-block socket.在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作,内核还是会继续通知你的,所以,这种模式编程出错误可能性要小一点。传统的select/poll都是这种模型的代表。
- ET (edge-triggered)是高速工作方式,只支持non-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如,你在发送,接收或者接收请求,或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误)。但是请注意,如果一直不对这个fd作IO操作(从而导致它再次变成未就绪),内核不会发送更多的通知(only once),不过在TCP协议中,ET模式的加速效用仍需要更多的benchmark确认。
ET和LT的区别就在这里体现,LT事件不会丢弃,而是只要读buffer里面有数据可以让用户读,则不断的通知你。而ET则只在事件发生之时通知。可以简单理解为LT是水平触发,而ET则为边缘触发。LT模式只要有事件未处理就会触发,而ET则只在高低电平变换时(即状态从1到0或者0到1)触发。
6. epoll高效原理
Epoll在linux内核中源码主要为 eventpoll.c 和 eventpoll.h 主要位于fs/eventpoll.c 和 include/linux/eventpool.h, 具体可以参考Linux 5.4源码,下述为部分关键数据结构摘要, 主要介绍epitem 红黑树节点 和eventpoll 关键入口数据结构,维护着链表头节点ready list header和红黑树根节点RB-Tree root。
struct epitem {
union {
/* RB tree node links this structure to the eventpoll RB tree */
struct rb_node rbn;
/* Used to free the struct epitem */
struct rcu_head rcu;
};
/* List header used to link this structure to the eventpoll ready list */
struct list_head rdllink;
/*
* Works together "struct eventpoll"->ovflist in keeping the
* single linked chain of items.
*/
struct epitem *next;
/* The file descriptor information this item refers to */
struct epoll_filefd ffd;
/* Number of active wait queue attached to poll operations */
int nwait;
/* List containing poll wait queues */
struct list_head pwqlist;
/* The "container" of this item */
struct eventpoll *ep;
/* List header used to link this item to the "struct file" items list */
struct list_head fllink;
/* wakeup_source used when EPOLLWAKEUP is set */
struct wakeup_source __rcu *ws;
/* The structure that describe the interested events and the source fd */
struct epoll_event event;
};
/*
* This structure is stored inside the "private_data" member of the file
* structure and represents the main data structure for the eventpoll
* interface.
*/
struct eventpoll {
/*
* This mutex is used to ensure that files are not removed
* while epoll is using them. This is held during the event
* collection loop, the file cleanup path, the epoll file exit
* code and the ctl operations.
*/
struct mutex mtx;
/* Wait queue used by sys_epoll_wait() */
wait_queue_head_t wq;
/* Wait queue used by file->poll() */
wait_queue_head_t poll_wait;
/* List of ready file descriptors */
struct list_head rdllist;
/* Lock which protects rdllist and ovflist */
rwlock_t lock;
/* RB tree root used to store monitored fd structs */
struct rb_root_cached rbr;
/*
* This is a single linked list that chains all the "struct epitem" that
* happened while transferring ready events to userspace w/out
* holding ->lock.
*/
struct epitem *ovflist;
/* wakeup_source used when ep_scan_ready_list is running */
struct wakeup_source *ws;
/* The user that created the eventpoll descriptor */
struct user_struct *user;
struct file *file;
/* used to optimize loop detection check */
u64 gen;
#ifdef CONFIG_NET_RX_BUSY_POLL
/* used to track busy poll napi_id */
unsigned int napi_id;
#endif
};
epoll使用RB-Tree红黑树去监听并维护所有文件描述符,RB-Tree的根节点
调用epoll_create时,内核除了帮我们在epoll文件系统里建了个file结点,在内核cache里建了个红黑树用于存储以后 epoll_ctl 传来的socket 外,还会再建立一个list链表,用于存储准备就绪的事件。
当epoll_wait调用时,仅仅观察这个list链表里有没有数据即可。有数据就返回,没有数据就sleep,等到timeout时间到后即使链表没数据也返回。所以,epoll_wait非常高效。而且,通常情况下即使我们要监控百万计的句柄,大多一次也只返回很少量的准备就绪句柄而已,所以,epoll_wait仅需要从内核态copy少量的句柄到用户态而已。
那么,这个准备就绪list链表是怎么维护的呢?
当我们执行epoll_ctl时,除了把socket放到epoll文件系统里file对象对应的红黑树上之外,还会给内核中断处理程序注册一个回调函数,告诉内核,如果这个句柄的中断到了,就把它放到准备就绪list链表里。所以,当一个socket上有数据到了,内核在把网卡上的数据copy到内核中后就来把socket插入到准备就绪链表里了。
epoll相比于select并不是在所有情况下都要高效,例如在如果有少于1024个文件描述符监听,且大多数socket都是出于活跃繁忙的状态,这种情况下,select要比epoll更为高效,因为epoll会有更多次的系统调用,用户态和内核态会有更加频繁的切换。
epoll高效的本质在于:
- 内部管理 fd 使用了高效的红黑树结构管理,做到了增删改之后性能的优化和平衡;
- epoll 池添加 fd 的时候,调用 file_operations->poll ,把这个 fd 就绪之后的回调路径安排好。通过事件通知的形式,做到最高效的运行;
- epoll 池核心的两个数据结构:红黑树和就绪列表。红黑树是为了应对用户的增删改需求,就绪列表是 fd 事件就绪之后放置的特殊地点,epoll 池只需要遍历这个就绪链表,就能给用户返回所有已经就绪的 fd 数组;
参考:
https://zhuanlan.zhihu.com/p/93609693
https://www.cnblogs.com/xiaobingqianrui/p/9234290.html
https://blog.csdn.net/dog250/article/details/50528373
https://www.cnblogs.com/sduzh/p/6714281.html
今天的文章Linux 中的 epoll 原理及使用分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/7382.html