一：引言
在Linux内核中,poll机制是一个非常重要的I/O多路复用机制。它允许进程监视多个文件描述符,等待其中任何一个进入就绪状态。poll的内部实现使用了poll_list链表结构而不是数组,这个设计选择背后有其深层的技术考量。本文将从内核源码层面深入分析这个设计决策的原因。
二：poll的基本工作原理
poll系统调用的基本接口如下：
int poll(struct pollfd *fds, nfds_t nfds, int timeout);
fds 是一个 struct pollfd 数组，每个元素包含一个文件描述符及其事件掩码。
nfds 是数组的大小。
timeout 是等待的时间（以毫秒为单位），如果为-1则无限期等待。
struct pollfd 结构体定义如下：
struct pollfd {int fd; // 文件描述符short events; // 请求的事件short revents; // 返回的事件};
在Linux内核中，poll 的实现主要位于 fs/select.c 文件中。我们可以通过以下步骤来追踪 poll 的执行流程：
1、用户空间到内核空间的转换：
用户空间的 poll 调用通过系统调用进入内核，内核调用 sys_poll 函数。
2、文件描述符集合的构建：
内核需要将用户传递的 pollfd 数组转换为内核可以处理的数据结构。
3、轮询文件描述符：
内核遍历文件描述符集合，检查每个文件描述符是否满足指定的事件条件。
4、结果返回：
将结果返回给用户空间。
其中第2点，应用层我们传递的是pollfd数组，要转换为内核的数据结构，内核对应的数据结构为：（V5.15版本）
// include/linux/poll.hstruct poll_list {struct poll_list *next; // 指向下一个poll_list节点int len; // 本节点包含的pollfd数量struct pollfd entries[]; // 弹性数组成员};// 文件系统层面的poll实现接口struct file_operations {...__poll_t (*poll) (struct file *file, struct poll_table_struct *wait);...};
拷贝的过程中
小规模操作使用栈空间，避免了内存分配。
len = min_t(unsigned int, nfds, N_STACK_PPS);if (copy_from_user(walk->entries, ufds + nfds-todo,sizeof(struct pollfd) * walk->len))
大规模操作通过链表分批处理，避免一次性分配大内存。
len = min(todo, POLLFD_PER_PAGE);size = sizeof(struct poll_list) + sizeof(struct pollfd) * len;walk = walk->next = kmalloc(size, GFP_KERNEL);
完整源码：
struct poll_wqueues table;int err = -EFAULT, fdcount, len, size;/* 使用栈空间来保存小规模的pollfd数组 */long stack_pps[POLL_STACK_ALLOC/sizeof(long)];struct poll_list *const head = (struct poll_list *)stack_pps;struct poll_list *walk = head;unsigned long todo = nfds;if (nfds > rlimit(RLIMIT_NOFILE))return -EINVAL;// 第一次拷贝：处理可以放入栈空间的部分len = min_t(unsigned int, nfds, N_STACK_PPS);for (;;) {walk->next = NULL;walk->len = len;if (!len)break;// 这里是关键的拷贝操作if (copy_from_user(walk->entries, ufds + nfds-todo,sizeof(struct pollfd) * walk->len))goto out_fds;todo -= walk->len;if (!todo)break;// 如果还有更多的fds需要处理，则分配新的poll_list节点len = min(todo, POLLFD_PER_PAGE);size = sizeof(struct poll_list) + sizeof(struct pollfd) * len;walk = walk->next = kmalloc(size, GFP_KERNEL);if (!walk) {err = -ENOMEM;goto out_fds;}}
三：为什么选择链表而不是数组
1、内存分配的灵活性
使用链表结构的第一个重要原因是内存分配的灵活性。让我们看看内核是如何为poll_list分配内存的:
//这个宏定义计算了在一个页面大小内可以容纳多少个 struct pollfd 结构体。PAGE_SIZE 是系统页面的大小，//sizeof(struct poll_list) 是 poll_list 结构体的大小，sizeof(struct pollfd) 是 pollfd 结构体的大小。//这个计算结果表示在一个页面内除了存储 poll_list 结构体本身外，还能存储多少个 pollfd 结构体。static struct poll_list *alloc_poll_list(int size){struct poll_list *p;int entries = POLLFD_PER_PAGE;if (size < entries) {entries = size;}p = kmalloc(struct_size(p, entries, sizeof(struct pollfd)), GFP_KERNEL);if (!p)return NULL;p->next = NULL;p->len = entries;return p;}
从上面的代码可以看出:
poll_list使用页对齐的内存分配,每个节点尽量利用一个完整的页面,通过链表结构,可以根据实际需要的pollfd数量动态分配多个节点,避免了一次性分配大块连续内存的问题.
如果使用数组结构,则存在以下问题:
// 假设使用数组方式struct poll_array {int len;struct pollfd entries[]; // 需要一次性分配足够大的连续内存};// 问题演示struct poll_array *alloc_poll_array(int size){// 1. 需要一次性分配大块连续内存// 2. 可能导致内存碎片// 3. 在内存压力大时更容易分配失败return kmalloc(sizeof(*p) + size * sizeof(struct pollfd), GFP_KERNEL);}
2、支持大量文件描述符
链表结构的第二个重要优势是能够支持大量文件描述符。内核中的实现:
// fs/select.cstatic int do_poll(struct poll_list *list, struct poll_wqueues *wait,struct timespec64 *end_time){poll_table* pt = &wait->pt;int error = 0;for (;;) {struct poll_list *walk;for (walk = list; walk != NULL; walk = walk->next) {struct pollfd * pfd = walk->entries;int len = walk->len;for (int i = 0; i < len; i++) {// 处理每个文件描述符error = do_pollfd(&pfd[i], pt, ...);}}if (!pt->qproc)break; // 所有fd都已就绪或出错if (signal_pending(current))break;if (end_time && time_after64(ktime_get(), *end_time))break; // 超时schedule(); // 让出CPU}return error;}
通过链表结构:
1、可以支持远超过单页内存大小的文件描述符数量
2、每个节点的大小限制在一个页面内,便于内存管理
3、遍历性能损失可以忽略不计,因为poll本身就是一个相对耗时的操作
如果使用数组:
// 使用数组的问题struct poll_array {int len;struct pollfd entries[MAX_POLL_FDS];};// 1. 需要预定义最大FD数量// 2. 过大的数组导致栈内存浪费// 3. 难以支持动态扩容
3、高效的插入和删除操作
链表的优势：
常数时间复杂度：链表在插入和删除节点时具有常数时间复杂度 O(1)，而数组需要移动大量元素，时间复杂度为 O(n)。
减少数据移动：链表不需要移动其他元素，只需要修改指针即可完成插入和删除操作。
数组的限制：
移动元素：数组在插入或删除元素时需要移动大量元素，特别是在数组中间位置进行操作时，性能下降明显。
复杂度高：数组的操作复杂度较高，不适合频繁的插入和删除操作
总结:
动态扩展性：链表可以根据实际需要动态分配和释放内存，避免了固定大小数组带来的内存浪费或不足问题。
高效的插入和删除操作：链表在插入和删除节点时具有常数时间复杂度，而数组需要移动大量元素，导致性能下降。
优化内存管理：页对齐的内存分配可以简化内存管理操作，提高内存管理的效率。
end
CppPlayer
关注，回复【电子书】珍藏CPP电子书资料赠送
精彩文章合集
专题推荐
