一：引言

在Linux內核中,poll機制是一個非常重要的I/O多路復用機制。它允許進程監視多個文件描述符,等待其中任何一個進入就緒狀態。poll的內部實現使用了poll_list鏈表結構而不是數組,這個設計選擇背后有其深層的技術考量。本文將從內核源碼層面深入分析這個設計決策的原因。

二：poll的基本工作原理

poll系統調用的基本接口如下：

#include <poll.h>
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.h
struct 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);...
};

poll_list 是一個動態分配的鏈表節點，每個節點包含一個 poll_table_entry 數組，用于存儲文件描述符及其相關的等待隊列

三：為什么選擇鏈表而不是數組

1、內存分配的靈活性

使用鏈表結構的第一個重要原因是內存分配的靈活性。讓我們看看內核是如何為poll_list分配內存的:

#define POLLFD_PER_PAGE  ((PAGE_SIZE-sizeof(struct poll_list)) / sizeof(struct pollfd))
//這個宏定義計算了在一個頁面大小內可以容納多少個 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.c
static 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;
}

通過鏈表結構:

可以支持遠超過單頁內存大小的文件描述符數量

每個節點的大小限制在一個頁面內,便于內存管理

遍歷性能損失可以忽略不計,因為poll本身就是一個相對耗時的操作

如果使用數組:

// 使用數組的問題
struct poll_array {int len; struct pollfd entries[MAX_POLL_FDS];
};// 1. 需要預定義最大FD數量
// 2. 過大的數組導致棧內存浪費
// 3. 難以支持動態擴容

3、高效的插入和刪除操作

鏈表的優勢：

常數時間復雜度：鏈表在插入和刪除節點時具有常數時間復雜度 O(1)，而數組需要移動大量元素，時間復雜度為 O(n)。

減少數據移動：鏈表不需要移動其他元素，只需要修改指針即可完成插入和刪除操作。

數組的限制：

移動元素：數組在插入或刪除元素時需要移動大量元素，特別是在數組中間位置進行操作時，性能下降明顯。

復雜度高：數組的操作復雜度較高，不適合頻繁的插入和刪除操作

總結

1. 動態擴展性：鏈表可以根據實際需要動態分配和釋放內存，避免了固定大小數組帶來的內存浪費或不足問題。

2. 高效的插入和刪除操作：鏈表在插入和刪除節點時具有常數時間復雜度，而數組需要移動大量元素，導致性能下降。

3. 優化內存管理：頁對齊的內存分配可以簡化內存管理操作，提高內存管理的效率。