[转帖]图解epoll

图解,epoll · 浏览次数 : 0

小编点评

## EP item creation and monitoring The code describes the creation of an EP item and how it's used for monitoring file system events. **Key points:** * An EP item is a data structure that represents an event source in epoll. * It holds information like the source file descriptor, event type, and user data. * The EP item is linked to the corresponding event source in the epoll table. * When an event occurs on the source, the epoll instance retrieves the EP item and processes the event. * The EP item can be added to a wait queue, allowing multiple instances to be notified when the event occurs. **Creating an EP item:** * `ep_item_from_wait()` function allocates memory for an EP item and fills it with information from the wait queue. * `list_add_tail()` adds the EP item to the end of a linked list for efficient access. **Monitoring file events:** * `ep_is_linked()` checks if an EP item is already linked to an event source. * `list_add_tail()` adds the EP item to the appropriate linked list for that source. * `__add_wait_queue_exclusive()` registers the EP item with a specific wait queue for exclusive waiting. * `ep_send_events()` sends the collected events to the registered event handlers. **Overall, this code demonstrates how to efficiently monitor file system events using EP items and event queues in epoll.**

正文

图解epoll

 

本文包含以下内容:

  • epoll是如何工作的

本文不包含以下内容:

  • epoll 的用法
  • epoll 的缺陷

select 和 poll 的缺点

epoll 对于动辄需要处理上万连接的网络服务应用的意义可以说是革命性的。对于普通的本地应用,select 和 poll可能就很好用了,但对于像C10K这类高并发的网络场景,select 和 poll就捉襟见肘了。

看看他们的API

int select(int nfds, fd_set *readfds, fd_set *writefds,
           fd_set *exceptfds, struct timeval *timeout);
           
int poll(struct pollfd *fds, nfds_t nfds, int timeout);

它们有一个共同点,用户需要将监控的文件描述符集合打包当做参数传入,每次调用时,这个集合都会从用户空间拷贝到内核空间,这么做的原因是内核对这个集合是无记忆的。对于绝大部分应用,这是一种十足的浪费,因为应用需要监控的描述符在大部分时间内基本都是不变的,也许会有变化,但都不大.

epoll 对此的改进

epoll对此的改进也正是它的实现方式,它需要完成以下两件事

  1. 描述符添加—内核可以记下用户关心哪些文件的哪些事件.
  2. 事件发生—内核可以记下哪些文件的哪些事件真正发生了,当用户前来获取时,能把结果提供给用户.

描述符添加

既然要有记忆,那么理所当然的内核需要需要一个数据结构来记, 这个数据结构简单点就像下面这个图中的epoll_instance, 它有一个链表头,链表上的元素epoll_item就是用户添加上去的, 每一项都记录了描述符fd和感兴趣的事件组合event 图片描述

事件发生

事件有多种类型, 其中POLLIN表示的可读事件是用户使用的最多的。比如:

  • 当一个TCP的socket收到报文,它会变得可读;
  • 当一个pipe受到对端发送的数据,它会变得可读;
  • 当一个timerfd对应的定时器超时,它会变得可读;

那么现在需要将这些可读事件和前面的epoll_instance关联起来。linux中,每一个文件描述符在内核都有一个struct file结构对应, 这个struct file有一个private_data指针,根据文件的实际类型,它们指向不同的数据结构。

图片描述

那么我能想到的最方便的做法就是epoll_item中增加一个指向struct file的指针,在struct file中增加一个指回epoll item的指针。 图片描述

为了能记录有事件发生的文件,我们还需要在epoll_instance中增加一个就绪链表readylist,在private_data指针指向的各种数据结构中增加一个指针回指到 struct file,在epoll item中增加一个挂接点字段,当一个文件可读时,就把它对应的epoll item挂接到epoll_instance 图片描述

在这之后,用户通过系统调用下来读取readylist就可以知道哪些文件就绪了。

好了,以上纯属我个人一拍脑袋想到的epoll大概的工作方式,其中一定包含不少缺陷。

不过真实的epoll的实现思想上与上面也差不多,下面来说一下

创建 epoll 实例

如同上面的epoll_instance,内核需要一个数据结构保存记录用户的注册项,这个结构在内核中就是struct eventpoll, 当用户使用epoll_create(2)或者epoll_create1(2)时,内核fs/eventpoll.c实际就会创建一个这样的结构.

/*
 * Create the internal data structure ("struct eventpoll").
 */
error = ep_alloc(&ep);

这个结构中比较重要的部分就是几个链表了,不过实例刚创建时它们都是空的,后续可以看到它们的作用

epoll_create()最终会向用户返回一个文件描述符,用来方便用户之后操作该 epoll实例,所以在创建epoll实例之后,内核就会分配一个文件描述符fd和对应的struct file结构

/*
* Creates all the items needed to setup an eventpoll file. That is,
* a file structure and a free file descriptor.
*/
fd = get_unused_fd_flags(O_RDWR | (flags & O_CLOEXEC));

file = anon_inode_getfile("[eventpoll]", &eventpoll_fops, ep,
                           O_RDWR | (flags & O_CLOEXEC));

最后就是把它们和刚才的epoll实例 关联起来,然后向用户返回fd

ep->file = file;

fd_install(fd, file);

return fd;

完成后,epoll实例 就成这样了。

图片描述

向 epoll 实例添加一个文件描述符

用户可以通过 epoll_ctl(2)向 epoll实例 添加要监控的描述符和感兴趣的事件。如同前面的epoll item,内核实际创建的是一个叫struct epitem的结构作为注册表项。如下图所示

图片描述 为了在描述符很多时的也能有较高的搜索效率, epoll实例 以红黑树的形式来组织每个struct epitem (取代上面例子中链表)。struct epitem结构中ffd是用来记录关联文件的字段, 同时它也作为该表项添加到红黑树上的Key;

rdllink的作用是当fd对应的文件准备好(关心的事件发生)时,内核会将它作为挂载点挂接到epoll实例中ep->rdllist链表上 fllink的作用是作为挂载点挂接到fd对应的文件的file->f_tfile_llink链表上,一般这个链表最多只有一个元素,除非发生了dup。 pwqlist是一个链表头,用来连接 poll wait queue。虽然它是链表,但其实链表上最多只会再挂接一个元素。

创建struct epitem的代码在fs/evnetpoll.cep_insert()

if (!(epi = kmem_cache_alloc(epi_cache, GFP_KERNEL)))
	return -ENOMEM;

之后会进行各个字段初始化

/* 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;

然后是设置局部变量epq

struct ep_pqueue epq;

epq.epi = epi;
init_poll_funcptr(&epq.pt, ep_ptable_queue_proc);

epq的数据结构是struct ep_pqueue,它是poll table的一层包装(加了一个struct epitem* 的指针)

struct  ep_pqueue{
    poll_table pt;
    struct epitem* epi;
}

poll table包含一个函数和一个事件掩码

typedef void (*poll_queue_proc)(struct file *, wait_queue_head_t *, struct poll_table_struct *);

typedef struct poll_table_struct {
    poll_queue_proc _qproc;
    unsigned long _key;   //  store the interested event masks
}poll_table;

这个poll table用在哪里呢 ? 答案是,用在了struct file_operationspoll操作 (这和本文开始说的selectpoll不是一个东西) 图片描述

struct file_operations { 
   // code omitted...
   unsigned int (*poll)(struct file*,  struct poll_table_struct*);
   // code omitted...
}

不同的文件有不同poll实现方式, 但一般它们的实现方式差不多是下面这种形式

static unsigned int XXXX_poll(struct file *file, poll_table *wait)
{
	私有数据 = file->private_data;
	unsigned int events = 0;
	
	poll_wait(file, &私有数据->wqh, wait);

	if (文件可读了)
		events |= POLLIN;
	
	return events;
} 

它们主要实现两个功能

  1. 将XXX放到文件私有数据的等待队列上 (一般file->private_data中都有一个等待队列头wait_queue_head_t wqh), 至于XXX是啥,各种类型文件实现各异,取决于poll_table参数
  2. 查询是否真的有事件了,若有则返回.

有兴趣的读者可以 timerfd_poll() 或者 pipe_poll() 它们的实现

poll_wait的实现很简单, 就是调用poll_table中设置的函数, 将文件私有的等待队列当作了参数.

static inline void poll_wait(struct file * filp, wait_queue_head_t * wait_address, poll_table *p)
{
	if (p && p->_qproc && wait_address)
		p->_qproc(filp, wait_address, p);
} 

回到 ep_insert()

所以这里设置的poll_table就是ep_ptable_queue_proc().

然后

revents = ep_item_poll(epi, &epq.pt);  

看其实现可以看到,其实就是主动去调用文件的poll函数. 这里以TCP socket文件为例好了(毕竟网络应用是最广泛的)

/*
 *   ep_item_poll  -> sock_poll -> tcp_poll
 */
unsigned int tcp_poll(struct file *file, struct socket *sock, poll_table *wait)  
{
    sock_poll_wait(file, sk_sleep(sk), wait);  // will call poll_wait()   
    // code omitted...
}

可以看到,最终还是调用到了poll_wait(),所以注册的ep_ptable_queue_proc()会执行

    struct epitem *epi = ep_item_from_epqueue(pt);
	struct eppoll_entry *pwq; 

    pwq = kmem_cache_alloc(pwq_cache, GFP_KERNEL)

这里面, 又分配了一个struct eppoll_entry结构. 其实它和struct epitem 结构是一一对应的.

随后就是一些初始化

    init_waitqueue_func_entry(&pwq->wait, ep_poll_callback); //  set func:ep_poll_callback
    pwq->whead = whead;  
    pwq->base = epi;

	add_wait_queue(whead, &pwq->wait) 
    list_add_tail(&pwq->llink, &epi->pwqlist);  
    epi->nwait++; 

这其中比较重要的是设置pwd->wait.func = ep_poll_callback

现在, struct epitem struct eppoll_entry的关系就像下面这样 图片描述

文件可读之后

对于TCP socket, 当收到对端报文后,最初设置的sk->sk_data_ready函数将被调用

void sock_init_data(struct socket *sock, struct sock *sk)
{
	// code omitted...
	 sk->sk_data_ready  =   sock_def_readable;
    // code omitted...
}

经过层层调用,最终会调用到 __wake_up_common 这里面会遍历挂在socket.wq上的等待队列上的函数

static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
			int nr_exclusive, int wake_flags, void *key)
{
	wait_queue_t *curr, *next;

	list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
		unsigned flags = curr->flags;

		if (curr->func(curr, mode, wake_flags, key) &&
				(flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
			break;
	}
} 

于是, 顺着图中的这条红色轨迹, 就会调用到我们设置的ep_poll_callback,那么接下来就是要让epoll实例能够知有文件已经可读了

图片描述

先从入参中取出当前表项epiep

    struct epitem *epi = ep_item_from_wait(wait);
	struct eventpoll *ep = epi->ep; 

再把epi挂到ep的就绪队列

if (!ep_is_linked(&epi->rdllink)) {
		list_add_tail(&epi->rdllink, &ep->rdllist)
	} 

接着唤醒阻塞在(如果有)该epoll实例的用户.

waitqueue_active(&ep->wq) 

用户获取事件

谁有可能阻塞在epoll实例的等待队列上呢? 当然就是使用epoll_wait来从epoll实例获取发生了感兴趣事件的的描述符的用户. epoll_wait会调用到ep_poll()函数.

if (!ep_events_available(ep)) {
		/*
		 * We don't have any available event to return to the caller.
		 * We need to sleep here, and we will be wake up by
		 * ep_poll_callback() when events will become available.
		 */
		init_waitqueue_entry(&wait, current);
		__add_wait_queue_exclusive(&ep->wq, &wait); 

如果没有事件,我们就将自己挂在epoll实例的等待队列上然后睡去….. 如果有事件,那么我们就要将事件返回给用户

ep_send_events(ep, events, maxevents) 

与[转帖]图解epoll相似的内容:

[转帖]图解epoll

图解epoll 本文包含以下内容: epoll是如何工作的 本文不包含以下内容: epoll 的用法 epoll 的缺陷 select 和 poll 的缺点 epoll 对于动辄需要处理上万连接的网络服务应用的意义可以说是革命性的。对于普通的本地应用,select 和 poll可能就很好用了,但对于

[转帖]图解LVS

https://www.jianshu.com/p/89c6f27771a4 LVS (linux virtual server)是 Linux标准内核的一部分。基于TCP/IP的负载均衡技术,转发效率极高,具有处理百万计并发连接请求的能力。由于工作在linux内核层,转发效率比工作在应用层的ngi

[转帖]图解架构 | SaaS、PaaS、IaaS

http://blog.itpub.net/70024420/viewspace-2925243/ 上次聊到了架构图如何画,其中涉及到了云服务的架构图,里面提到了很重要的三个概念 PaaS、IaaS、SaaS,很有必要在这里总结一波。 架构图,so easy? 本文内容如下: 随着互联网行业的飞速发

[转帖]图解一致性哈希算法,看这一篇就够了!

http://blog.itpub.net/70024420/viewspace-2925492/ 接下来介绍一个非常重要、也非常实用的算法:一致性哈希算法。通过介绍一致性哈希算法的原理并给出了一种实现和实际运用的案例,带大家真正理解一致性哈希算法。 一、背景 在具体介绍一致性哈希算法之前,先问一个

[转帖]图解第四代英特尔至强可扩展处理器家族

https://aijishu.com/a/1060000000379987 今天,代号Sapphire Rapids(SPR)的第四代英特尔至强(Intel Xeon)可扩展处理器,终于来了。 从三代Lake变到Rapids,有继承,有发展。这里的继承是指2D Mesh(网格)架构,发展是指Chi

[转帖]图解:什么是红黑树?

https://zhuanlan.zhihu.com/p/273829162 注:本文比较硬核但是很值得大家花心思看完,看完你一定会有所收获的 红黑树是面试中一个很经典也很有难度的知识点,网传字节跳动面试官最喜欢问这个问题。很多人会觉得这个知识点太难,不想花太多功夫去了解,也有人会认为这个数据结构在

[转帖]长篇图解 etcd 核心应用场景及编码实战

https://xie.infoq.cn/article/3329de088beb60f5803855895 一、白话 etcd 与 zookeeper 二、etcd 的 4 个核心机制 三、Leader 选举与客户端交互 四、etcd 的应用场景 4.1. kubernetes 大脑 4.2. 服

[转帖]⭐万字长篇超详细的图解Tomcat中间件方方面面储备知识⭐

https://developer.aliyun.com/article/885079?spm=a2c6h.24874632.expert-profile.321.7c46cfe9h5DxWK 2022-04-13 132举报 简介: LNMT 1.JAVA简介 常见的大型平台有LNMP、LNMP、

[转帖]网络包的内核漂流记 Part 1 - 图解网络包接收流程

https://blog.mygraphql.com/zh/notes/low-tec/network/kernel-net-stack/ 目录 目录 《网络包的内核漂流记》系列介绍 风格、样式、本文的交互阅读方式 📖 ISO 网络模型 网络包接收流程概述 网络包接收步骤 初始化与配置 IRQ 处

【转帖】71.常用的显示GC日志的参数、GC日志分析、日志分析工具的使用

目录 1.常用的显示GC日志的参数2.图解垃圾`GC`日志(重要)3.日志分析工具的使用 1.常用的显示GC日志的参数 解释: 日志中,GC和Full GC表示的是GC的类型。GC只在新生代进行,Full GC包括新生代和老年代、方法区。 Allocation Failure:GC发生的原因,一般新