写点什么

对于 epoll 实现原理的理解

作者:C++后台开发
  • 2022 年 9 月 22 日
    湖南
  • 本文字数:2520 字

    阅读完需:约 8 分钟

Epoll 是 Linux IO 的多路复用的机制,是 select/poll 的增强版本,在 Linux 内核 fs/eventpoll.c 中可以查看 epoll 的具体的实现。

一、epoll 数据结构

  学习任何组件,首先得知道它有什么数据结构或者数据类型,epoll 主要有两个结构体:eventpoll 和 epitem。epitem 是每一个 IO 对应的事件,比如 EPOLL_CTL_ADD 操作时,就需要创建一个 epitem;eventpoll 是每一个 epoll 所对应的,比如 epoll_create 就是创建一个 eventpoll。

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;//sockfd
/* List containing poll wait queues */ struct eppoll_entry *pwqlist;
/* The "container" of this item */ struct eventpoll *ep;
/* List header used to link this item to the "struct file" items list */ struct hlist_node 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;};
struct eventpoll {
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; struct hlist_head refs;
#ifdef CONFIG_NET_RX_BUSY_POLL /* used to track busy poll napi_id */ unsigned int napi_id;#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC /* tracks wakeup nests for lockdep validation */ u8 nests;#endif};
复制代码

数据结构如下图所示。

  list 用来存储就绪的 IO,rbtree 用来存储所有 IO,方便快速查找 fd,这两种数据结构我们都从 inster 和 remove 来讨论。对于 list,当内核 IO 准备就绪时,则执行 epoll_event_callback 的回调函数,将 epitem 添加到 list 中;当 epoll_wait 激活重新运行时,将 list 的 epitem 逐一拷贝到 events 中,并删除 list 中被拷贝出来的 epitem。

对于 rbtree 又该何时添加何时删除呢?当 app 执行 epoll_ctl(EPOLL_CTL_ADD)操作,将 epitem 添加到 rbtree 中;当 app 执行 epoll_ctl(EPOLL_CTL_DEL)操作,将对应的 epitem 从 rbtree 中删除。那么 list 和 rbtree 又如何做到线程安全呢?

二、epoll 锁的机制

  list 使用最小粒度的锁 spinlock,便于在 SMP 下添加操作的时候,能够快速操作 list。避免 SMP 体系下,多核竞争,此处采用自旋锁,不适合采用睡眠锁;添加操作如下。

    (1)获取 spinlock

    (2)epitem 的 rdy 置为 1,代表 epitem 已在就绪队列中

    (3)添加到 list

    (4)将 eventpoll 的 rdnum 加 1

    (5)释放 spinlock

  删除则与添加类似。

  对于 rbtree 的操作使用互斥锁,过程如下:

    (1)获取互斥锁

    (2)查找 sockid 的 epitem 是否存在,不存在可以添加

    (3)分配 epitem

    (4)sockid 赋值

    (5)设置 event 添加到 epitem 的 event 域

    (6)将 epitem 添加到 rbtree

    (7)释放互斥锁

  这里的互斥锁,锁的是整颗树,而不是节点;删除则与之类似操作。

三、epoll 回调

  首先要知道回调函数何时执行,此部分需要与 tcp 的协议栈联系起来理解。

  (1)三次握手完成时,把 fd 加入到就绪队列,把 event 置为 EPOLLIN 可读,此时标识可以进入到 accept 读取 socket 数据;

  (2)recvbuffer 有数据的时候(可读数据),找到对应的 fd 加入到就绪队列,把 event 置 EPOLLIN 为可读;

  (3)sendbuffer 有空隙的时候(可发数据),找到对应的 fd 加入到就绪队列,把 event 置 EPOLLOUT 为可写;

  (4)接收到 fin 的时候(断开连接),找到对应的 fd 加入到就绪队列,把 event 置 EPOLLIN 为可读;

四、LT 与 ET

  (1)LT 是水平出发,有数据就一直触发,只要 recvBuffer 里面有数据就一直触发,直到数据读取完,适用于大块;

  (2)ET 是边沿触发,从没有数据到有数据,才触发,只触发一次,即使没读完数据,也不会再触发去读取剩余的数据,剩余的数据等待下一次触发再读,适用于小块;

思考:

  就绪集合为啥使用队列而不适用栈?

    首先就绪集合的数据本身就需要遍历所有,肯定使用链式的数据结构,如果使用栈,就会存在就绪节点一次那不完的情况,导致上一次没被取出的节点,在下一次 epoll_wait 再拿的时候也可能拿不到,导致出现一些就绪节点永远都不被处理。

  epoll 的误区:

  (1)epoll 性能高,里面有内存映射,mmap

  (2)epoll 比 select/poll 要高,在 fd 很少时 select/poll 比 epoll 更好

C/C++Linux服务器开发高级架构师/C++后台开发架构师​免费学习地址


另外还整理一些 C++后台开发架构师 相关学习资料,面试题,教学视频,以及学习路线图,免费分享加 qun:720209036,自取


用户头像

C/C++后台开发技术交流qun:720209036 2022.05.06 加入

还未添加个人简介

评论

发布
暂无评论
对于epoll实现原理的理解_后台开发_C++后台开发_InfoQ写作社区