【Linux】【进程】epoll内核实现总结+ET和LT模式内核实现方式

【Linux】【网络】epoll内核实现总结+ET和LT模式内核实现方式

1.epoll的工作原理

eventpoll结构

当某一进程调用epoll_create方法时，Linux内核会创建一个eventpoll结构体，这个结构体中有两个成员与epoll的使用方式密切相关.

struct eventpoll{
	....
	/*红黑树的根节点，这颗树中存储着所有添加到epoll中的需要监控的事件*/
	struct rb_root rbr; // 监视列表（红黑树）
	/*双链表中则存放着将要通过epoll_wait返回给用户的满足条件的事件*/
	struct list_head rdlist; //就绪队列（双向链表）
	....
};

通过epoll_ctl方法向epoll对象添加事件。这些事件都会挂载在红黑树rbr中，红黑树的增删查改效率都是O(logn)，是一个高效的索引结构。并且可以利用红黑树键值的唯一性进行去重操作（重复添加无效）。
底层驱动程序允许操作系统注册一些回调函数，所有添加到epoll中的事件都会与设备(网卡)驱动程序建立回调关系，也就是说，当响应的事件发生时会调用这个回调方法。
这个回调方法在内核中叫ep_poll_callback,它会将发生的事件添加到rdlist双链表中.

epitem对象

rbr和rdlist中的元素都是这样的结构。在epoll中，对于每一个事件，都会建立一个epitem对象，该对象既挂接在rbr红黑树中也挂接在rdlist双链表中。

struct epitem{
	struct rb_node rbn;//红黑树节点
	struct list_head rdllink;//双向链表节点
	struct epoll_filefd ffd; //事件句柄信息
	struct eventpoll *ep; //指向其所属的eventpoll对象
	struct epoll_event event; //期待发生的事件类型
}

当中rbn和rdlist结构分别描述该节点在rbr红黑树和rdlist双链表中的链接关系。
当调用epoll_wait检查是否有事件发生时，只需要检查eventpoll对象中的rdlist双链表中是否有epitem元素即可.
如果rdlist不为空，则把发生的事件复制到用户态，同时将事件数量返回给用户. 这个操作的时间复杂度是O(1).

就绪队列：底层结构是rdlist双向链表，将监视且就绪的事件添加到队列。（核心结构，中间结构）
监视列表：底层结构是rbr红黑树，通过epoll_ctl添加就绪事件。（就像是一份名单）
中断回调：添加就绪事件的同时，系统向硬件驱动注册中断回调，事件发生时由他完成检查和就绪的任务。（完成实际的工作步骤）

2.整体网络操作

在这里插入图片描述

1.用户通过调用epoll_create(size)创建epoll模型（eventpoll结构）,当中就包括了rbr监视列表和rdlist就绪队列。

2.通过epoll_ctl(epfd, EPOLL_CTL_ADD, sockfd, event)

向rbr监视列表添加监视套接字的对应事件
同时在硬件驱动（网卡）中注册对应的中断回调。
做到以上两点，当数据到来时rdlist就绪队列就可以获取到对应事件的就绪节点了。

3.计算机收到了对端传送的数据。数据经由网卡传送到内存，然后网卡通过中断信号通知cpu有数据到达，cpu执行硬件驱动对应的中断回调程序。此处中断程序的主要功能有：

将数据不断解包，层层向上交付，一直交给对应套接字的接收队列（tcp传输层）。
在rbr监视列表（红黑树）中查找是否监视套接字的对应事件。
如果确认监视，则构建就绪节点，将节点插入到rdlist就绪队列当中
唤醒进程（如果进程被epoll_wait阻塞）

4.最后用户调用epoll_wait(epfd, events, maxevents, timeout)将epoll模型就绪队列中的就绪事件获取到events数组（用户空间），并返回就绪事件的数量。当然，如果此时就绪队列为空则进程阻塞或超时返回0。

5.接下来就是用户层的工作了，对照events数组当中的就绪事件，向指定的套接字句柄进行读写操作（当然还有期间的数据处理工作）。

内核角度

eventpoll对象相当于是socket和进程之间的中介，socket的数据接收并不直接影响进程，而是通过改变eventpoll的就绪列表来改变进程状态：

在select/poll中，在IO等待阶段进程是被挂起在每个监视socket的等待队列中，当数据到来时又需要将进程从每个socket的等待队列中移除再放入CPU运行队列才能唤醒进程，这就涉及到两次遍历，效率O(2n)；
而在epoll中，进程是被挂起在epoll模型（也是文件系统的一员）的等待队列中的，当有任意监视事件就绪（就绪队列中有节点），只需要将进程从epoll等待队列中移除再放入CPU运行队列即可，效率O(1)。

用户角度

epoll_wait获取上来的所有事件都是就绪事件，可以直接对照套接字和对应事件进行读写操作，不需要向select/poll那样把所有监视套接字都遍历判断一遍就绪了。

`select`/`poll` 的工作机制：

等待阶段：当进程调用 select 或 poll 时，内核会将该进程挂起，并将其添加到每个被监视的套接字的等待队列中。
事件发生：如果某个套接字上有事件（如可读或可写）发生，内核需要遍历该套接字的等待队列，将所有在此等待的进程从等待队列中移除，并将其放入 CPU 的运行队列中，以便唤醒这些进程。
性能影响：由于每个进程可能监视多个套接字，因此在事件发生时，内核需要对每个套接字的等待队列进行遍历和操作，导致时间复杂度为 O(n)，其中 n 是被监视的套接字数量。

从 select.c 源码来看，Linux 内核中 select 和 poll 机制的等待队列操作主要涉及 进程挂起、等待队列管理、进程唤醒 这几个关键步骤。以下是详细的解析：

1. 进程如何被挂起到等待队列

在 do_select() 函数中，进程在等待 I/O 事件时会进入睡眠状态：

set_current_state(TASK_INTERRUPTIBLE);

TASK_INTERRUPTIBLE 表示进程进入 可中断睡眠 状态，等待 I/O 事件发生。

然后，内核会遍历所有需要监视的 文件描述符（FD），并调用 poll_wait()：

if (f_op && f_op->poll)
    mask = (*f_op->poll)(file, retval ? NULL : wait);

file->f_op->poll 是文件的 poll() 函数，通常由设备驱动提供。
poll_wait()（内联定义在 linux/poll.h）会将当前进程添加到 该文件的等待队列。

2. `poll_wait()` 将进程加入等待队列

在 __pollwait() 中，进程会被添加到文件描述符的等待队列：

void __pollwait(struct file *filp, wait_queue_head_t *wait_address, poll_table *_p)
{
    struct poll_wqueues *p = container_of(_p, struct poll_wqueues, pt);
    struct poll_table_page *table = p->table;

    /* 创建新的等待队列条目 */
    struct poll_table_entry * entry = table->entry;
    table->entry = entry+1;
    get_file(filp);
    entry->filp = filp;
    entry->wait_address = wait_address;
    
    /* 初始化等待队列条目 */
    init_waitqueue_entry(&entry->wait, current);
    
    /* 将当前进程添加到该文件描述符的等待队列 */
    add_wait_queue(wait_address, &entry->wait);
}

wait_address 是 文件描述符（socket、管道等）的等待队列。
add_wait_queue() 将当前进程 (current) 挂起到 文件描述符的等待队列 中。

此时，进程已经进入 睡眠状态，等待事件发生。

3. 事件发生时，进程如何被唤醒

当套接字（或文件）上有 可读、可写 事件发生时，设备驱动会调用：

wake_up(&wait_queue);

该操作最终会调用：

static void wake_up_process(struct task_struct *p)
{
    if (task_is_running(p))
        return;
    p->state = TASK_RUNNING;
    enqueue_task(p); // 将进程放入 CPU 运行队列
}

从等待队列移除进程
修改进程状态为 TASK_RUNNING
将进程放入 CPU 的运行队列

此时，进程被唤醒，可以继续执行 select() 或 poll() 后续代码，处理 I/O 事件。

4. `select` 和 `poll` 的低效之处

4.1 `select/poll` 遍历每个文件的等待队列

进程会被 挂起到所有监视的套接字的等待队列。
事件发生时，内核需要遍历 所有文件的等待队列，找到需要唤醒的进程。

4.2 事件触发后需要两次遍历

遍历文件描述符的等待队列，将进程移除。
遍历所有等待的进程，将其放入 CPU 运行队列。

时间复杂度：O(2n)
如果有 成千上万个套接字，性能开销非常大。

5. `epoll` 如何优化这个过程

5.1 `epoll_wait` 进程只挂起在 `epoll` 的等待队列

add_wait_queue(&ep->wq, &wait);
schedule_timeout(timeout);

进程 不再被挂起到每个套接字的等待队列，而是挂起到 epoll 实例的等待队列。

5.2 事件发生时

static void ep_poll_callback(struct eppoll_entry *epi)
{
    list_add_tail(&epi->rdllink, &ep->rdlist);
    wake_up(&ep->wq);
}

只需要操作 epoll 的等待队列，即可唤醒 epoll_wait()，无需遍历所有套接字。
时间复杂度 O(1)，比 select / poll 更高效。

6. 总结

机制	等待队列	事件发生时的操作	时间复杂度
`select/poll`	进程挂起在所有套接字的等待队列	遍历所有套接字的等待队列，移除进程	O(2n)
`epoll`	进程挂起在 `epoll` 实例的等待队列	只需操作 `epoll` 等待队列	O(1)

epoll 通过 就绪队列 机制，避免了 select / poll 的 双重遍历等待队列，大幅提升高并发场景的 I/O 处理效率 🚀。

`epoll` 的工作机制：

等待阶段：epoll 引入了一个专用的事件监视对象（即 epoll 实例）。当进程调用 epoll_wait 时，内核将该进程挂起，并将其添加到 epoll 实例的等待队列中，epoll_wait 进程只挂起在 epoll 的等待队列

add_wait_queue(&ep->wq, &wait);
schedule_timeout(timeout);

2.进程不再被挂起到每个套接字的等待队列，而是挂起到 epoll 实例的等待队列。只需要操作 epoll 的等待队列，即可唤醒 epoll_wait()，无需遍历所有套接字。

事件发生：当任一被监视的套接字上有事件发生时，内核会将该事件添加到 epoll 实例的就绪队列中。如果这是第一个就绪事件，内核会将等待在 epoll 实例上的进程从等待队列中移除，并放入 CPU 的运行队列中，唤醒该进程。

2.LT/ET

水平触发（LT）模式：

默认模式：在 LT 模式下，当被监控的文件描述符上有事件发生时，epoll_wait 会通知应用程序。即使应用程序没有立即处理该事件，后续的 epoll_wait 调用仍会再次通知，直到事件被处理。
特点：LT 模式下，内核会持续通知应用程序某个文件描述符的事件，直到应用程序处理为止。

边沿触发（ET）模式：

高效模式：在 ET 模式下，当被监控的文件描述符上有事件发生时，epoll_wait 仅通知应用程序一次。如果应用程序没有及时处理，后续的 epoll_wait 调用将不会再次通知。因此，应用程序需要确保在收到通知后，非阻塞地读取或写入数据，直到返回 EAGAIN。
特点：ET 模式减少了重复通知的次数，提高了效率，但要求应用程序采用非阻塞 I/O，并在收到事件后立即处理。

内核实现上的区别：

总结一下epoll该函数： epoll_wait函数会使调用它的进程进入睡眠（timeout为0时除外），如果有监听的事件产生，该进程就被唤醒，同时将事件从内核里面拷贝到用户空间返回给该进程。
LT模式只不过比ET模式多执行了一个步骤，就是当epoll_wait获取完就绪队列epoll事件后，LT模式会再次将epoll事件添加到就绪队列。
LT模式多了这样一个步骤会让LT模式调用epoll_wait时会一直检测到epoll事件，直到socket缓冲区数据清空为止。