閱讀源碼時看到一個結構體的定義不知道在哪時，可以通過這個網站來查找，非常方便。

__user 是一個宏定義，表示用戶空間的，內核不能直接使用，需要使用函數 copy_from_user/copy_to_user 進行處理。

0. 進程打開的文件

進程的表示：

// 源碼位置：include/linux/sched.h

struct task_struct {

// ....省略其他屬性

/* 文件系統信息: */

struct fs_struct *fs;

/* 打開的文件信息: */

struct files_struct *files;

// ....省略其他屬性

}

進程維護打開的文件的數據結構：

// 源碼位置：include/linux/fdtable.h

struct files_struct {

/*

* read mostly part

*/

atomic_t count;

bool resize_in_progress;

wait_queue_head_t resize_wait;

struct fdtable __rcu *fdt;

struct fdtable fdtab;

/*

* written part on a separate cache line in SMP

*/

spinlock_t file_lock ____cacheline_aligned_in_smp;

unsigned int next_fd;

unsigned long close_on_exec_init[1];

unsigned long open_fds_init[1];

unsigned long full_fds_bits_init[1];

struct file __rcu * fd_array[NR_OPEN_DEFAULT];

};

struct fdtable {

// 進程能打開的最大文件數

unsigned int max_fds;

struct file __rcu **fd; /* current fd array */

unsigned long *close_on_exec;

// 當前打開的一組文件

unsigned long *open_fds;

unsigned long *full_fds_bits;

struct rcu_head rcu;

};

static inline bool fd_is_open(unsigned int fd, const struct fdtable *fdt)

{

return test_bit(fd, fdt->open_fds);

}

小結：進程打開的文件維護在位圖 fdtable.open_fds 裡，對應的比特位為 1 表示文件打開，為 0 是關閉。

select 裡傳遞事件也借鑑了這種思想，通過位圖來傳遞，FD 對應的比特位為 1 表示對事件感興趣或有事件發生。

1. 基本數據結構

// include/uapi/linux/posix_types.h

#define __FD_SETSIZE 1024

typedef struct {

unsigned long fds_bits[__FD_SETSIZE / (8 * sizeof(long))];

} __kernel_fd_set;

// 源碼位置： include/linux/types.h

typedef __kernel_fd_set fd_set;

// 源碼位置： fs/select.c

// 用於傳遞 select 的輸入事件、輸出結果，是 fd_set 的擴展版。

typedef struct {

unsigned long *in, *out, *ex;

unsigned long *res_in, *res_out, *res_ex;

} fd_set_bits;

小結：從上述定義可以看到，fd_set 就是一個位圖，限制了 select 操作就多可以 poll 1024 個文件，如果要支持 poll 更多的文件，需要修改源碼、重新編譯。

fd_set_bits 裡的6個變量是6個指針，指向不同的位圖起始地址，見下文裡的註釋說明。

2. select 主邏輯

select 調用利用 fd_set 這個位圖來傳遞輸入的要監聽的事件和輸出結果。

// 源碼位置： fs/select.c

// select 系統調用原型

SYSCALL_DEFINE5(select, int, n, fd_set __user *, inp, fd_set __user *, outp,

fd_set __user *, exp, struct timeval __user *, tvp)

{

struct timespec64 end_time, *to = NULL;

struct timeval tv;

int ret;

if (tvp) {

if (copy_from_user(&tv, tvp, sizeof(tv)))

return -EFAULT;

to = &end_time;

if (poll_select_set_timeout(to,

tv.tv_sec + (tv.tv_usec / USEC_PER_SEC),

(tv.tv_usec % USEC_PER_SEC) * NSEC_PER_USEC))

return -EINVAL;

}

ret = core_sys_select(n, inp, outp, exp, to);

ret = poll_select_copy_remaining(&end_time, tvp, 1, ret);

return ret;

}

int core_sys_select(int n, fd_set __user *inp, fd_set __user *outp,

fd_set __user *exp, struct timespec64 *end_time)

{

fd_set_bits fds;

void *bits;

int ret, max_fds;

size_t size, alloc_size;

struct fdtable *fdt;

/* Allocate small arguments on the stack to save memory and be faster */

// 在棧上分配的小段參數，用於節省內存和提升速度

// SELECT_STACK_ALLOC=256

long stack_fds[SELECT_STACK_ALLOC/sizeof(long)];

ret = -EINVAL;

if (n < 0)

goto out_nofds;

/* max_fds can increase, so grab it once to avoid race */

rcu_read_lock();

fdt = files_fdtable(current->files);

max_fds = fdt->max_fds;

rcu_read_unlock();

// poll 的最大 FD 不能超過 進程打開的最大FD

if (n > max_fds)

n = max_fds;

// 每個文件有3種輸入、3種輸出，因此每個文件需要6個位圖來表示事件

/*

* We need 6 bitmaps (in/out/ex for both incoming and outgoing),

* since we used fdset we need to allocate memory in units of

* long-words.

*/

// n 個文件需要的字節數，也是每份位圖的大小

size = FDS_BYTES(n);

bits = stack_fds;

// sizeof(stack_fds) / 6 是把棧上分配的內存塊劃分為 6 份做位圖

if (size > sizeof(stack_fds) / 6 ) {

/* Not enough space in on-stack array; must use kmalloc */

// 棧上分配的空間不夠，要使用 kmalloc

ret = -ENOMEM;

if (size > (SIZE_MAX / 6))

goto out_nofds;

alloc_size = 6 * size;

bits = kvmalloc(alloc_size, GFP_KERNEL);

if (!bits)

goto out_nofds;

}

// 把 fds 裡的指針指向不同位圖的起始地址

fds.in = bits;

fds.out = bits + size;

fds.ex = bits + 2*size;

fds.res_in = bits + 3*size;

fds.res_out = bits + 4*size;

fds.res_ex = bits + 5*size;

// 把用戶空間的事件拷貝到內核空間

if ((ret = get_fd_set(n, inp, fds.in)) ||

(ret = get_fd_set(n, outp, fds.out)) ||

(ret = get_fd_set(n, exp, fds.ex)))

goto out;

// 清零輸出結果

zero_fd_set(n, fds.res_in);

zero_fd_set(n, fds.res_out);

zero_fd_set(n, fds.res_ex);

ret = do_select(n, &fds, end_time);

if (ret < 0)

goto out;

if (!ret) {

ret = -ERESTARTNOHAND;

if (signal_pending(current))

goto out;

ret = 0;

}

// 通過 __copy_to_user 拷貝結果到用戶空間

if (set_fd_set(n, inp, fds.res_in) ||

set_fd_set(n, outp, fds.res_out) ||

set_fd_set(n, exp, fds.res_ex))

ret = -EFAULT;

out:

if (bits != stack_fds)

kvfree(bits);

out_nofds:

return ret;

}

static int do_select(int n, fd_set_bits *fds, struct timespec64 *end_time)

{

ktime_t expire, *to = NULL;

// 構建一個等待隊列，該隊列維護著對所有添加到文件的等待隊列的節點的指針

struct poll_wqueues table;

// 等待節點的數據原型，主要用於傳遞參數

poll_table *wait;

int retval, i, timed_out = 0;

u64 slack = 0;

unsigned int busy_flag = net_busy_loop_on() ? POLL_BUSY_LOOP : 0;

unsigned long busy_start = 0;

rcu_read_lock();

retval = max_select_fd(n, fds);

rcu_read_unlock();

if (retval < 0)

return retval;

n = retval;

// 設置 wait._qproc = __pollwait

poll_initwait(&table);

wait = &table.pt;

if (end_time && !end_time->tv_sec && !end_time->tv_nsec) {

wait->_qproc = NULL;

timed_out = 1;

}

if (end_time && !timed_out)

slack = select_estimate_accuracy(end_time);

retval = 0;

for (;;) {

unsigned long *rinp, *routp, *rexp, *inp, *outp, *exp;

bool can_busy_loop = false;

inp = fds->in; outp = fds->out; exp = fds->ex;

rinp = fds->res_in; routp = fds->res_out; rexp = fds->res_ex;

// 分批輪詢

for (i = 0; i < n; ++rinp, ++routp, ++rexp) {

unsigned long in, out, ex, all_bits, bit = 1, mask, j;

unsigned long res_in = 0, res_out = 0, res_ex = 0;

in = *inp++; out = *outp++; ex = *exp++;

all_bits = in | out | ex; //

if (all_bits == 0) {

// 沒有敢興趣的事件，跳過 BITS_PER_LONG 個文件

i += BITS_PER_LONG;

continue;

}

// 批次內逐個輪詢

for (j = 0; j < BITS_PER_LONG; ++j, ++i, bit <<= 1) { // bit 左移是為了給正確的文件設置事件結果

struct fd f;

if (i >= n)

break;

if (!(bit & all_bits))

continue;

f = fdget(i);

if (f.file) {

// 找到了文件

const struct file_operations *f_op;

f_op = f.file->f_op;

mask = DEFAULT_POLLMASK;

if (f_op->poll) {

wait_key_set(wait, in, out,

bit, busy_flag);

// 調用文件的 poll 函數，最終會調用到 __pollwait 函數

// __pollwait

mask = (*f_op->poll)(f.file, wait);

}

fdput(f);

// 下面的 if 語句塊內，是已經檢測到事件發生了，進程不需要進行等待和喚醒

// 把 _qproc 設置為 NULL 是為了避免往後續 poll 未就緒的文件時被加入等待隊列

// 這樣可以避免無效的喚醒

if ((mask & POLLIN_SET) && (in & bit)) {

res_in |= bit;

retval++;

wait->_qproc = NULL;

}

if ((mask & POLLOUT_SET) && (out & bit)) {

res_out |= bit;

retval++;

wait->_qproc = NULL;

}

if ((mask & POLLEX_SET) && (ex & bit)) {

res_ex |= bit;

retval++;

wait->_qproc = NULL;

}

//

/* got something, stop busy polling */

if (retval) {

can_busy_loop = false;

busy_flag = 0;

/*

* only remember a returned

* POLL_BUSY_LOOP if we asked for it

*/

} else if (busy_flag & mask)

can_busy_loop = true;

}

}

// 小批次輪詢完，把結果記錄下來

if (res_in)

*rinp = res_in;

if (res_out)

*routp = res_out;

if (res_ex)

*rexp = res_ex;

// 進入睡眠，等待超時或喚醒

cond_resched();

}

// 所有文件都輪詢了一遍，要加入文件等待隊列的都已經加了，避免下次輪詢重複添加

wait->_qproc = NULL;

// 有事件、或超時、或有信號要處理

if (retval || timed_out || signal_pending(current))

break;

if (table.error) {

retval = table.error;

break;

}

/* only if found POLL_BUSY_LOOP sockets && not out of time */

if (can_busy_loop && !need_resched()) {

if (!busy_start) {

busy_start = busy_loop_current_time();

continue;

}

if (!busy_loop_timeout(busy_start))

continue;

}

busy_flag = 0;

/*

* If this is the first loop and we have a timeout

* given, then we convert to ktime_t and set the to

* pointer to the expiry value.

*/

if (end_time && !to) {

expire = timespec64_to_ktime(*end_time);

to = &expire;

}

// 進程狀態設置為 TASK_INTERRUPTIBLE，進入睡眠直到超時

if (!poll_schedule_timeout(&table, TASK_INTERRUPTIBLE,

to, slack))

timed_out = 1;

}

// 釋放等待節點，重點是把等待節點從文件的等待隊列刪除掉

poll_freewait(&table);

return retval;

}

3. 等待與喚醒

3.0 相關數據結構

// 添加到文件等待隊列的節點類型

struct poll_table_entry {

// 要監聽的目標文件

struct file *filp;

// 要監聽的事件

unsigned long key;

wait_queue_entry_t wait;

// 等待隊列頭

wait_queue_head_t *wait_address;

};

// 每次執行 select 調用時維護的等待隊列

struct poll_wqueues {

// 調用 poll 操作時用於傳遞信息的對象

poll_table pt;

// inline_entries 空間不夠用申請的等待節點列表

struct poll_table_page *table;

// 執行 select 的進程信息

struct task_struct *polling_task;

// 是否已喚醒

int triggered;

int error;

// 指向 inline_entries 裡未使用的節點下標

int inline_index;

// 預申請的等待節點

struct poll_table_entry inline_entries[N_INLINE_POLL_ENTRIES];

};

// 如果 inline_entries 不夠用，則以 poll_table_page 鏈表的形式存起來

struct poll_table_page {

struct poll_table_page * next;

struct poll_table_entry * entry;

struct poll_table_entry entries[0];

};

3.1 等待

static inline void poll_wait(struct file * filp, wait_queue_head_t * wait_address, poll_table *p)

{

// p->_qproc 對應了上面 wait->_qproc = NULL; 的優化

if (p && p->_qproc && wait_address)

p->_qproc(filp, wait_address, p);

}

void poll_initwait(struct poll_wqueues *pwq)

{

// 設置 poll 等待隊列的處理函數為 __pollwait

init_poll_funcptr(&pwq->pt, __pollwait);

pwq->polling_task = current;

pwq->triggered = 0;

pwq->error = 0;

pwq->table = NULL;

pwq->inline_index = 0;

}

EXPORT_SYMBOL(poll_initwait);

static void __pollwait(struct file *filp, wait_queue_head_t *wait_address,

poll_table *p)

{

struct poll_wqueues *pwq = container_of(p, struct poll_wqueues, pt);

// 獲取一個等待節點

struct poll_table_entry *entry = poll_get_entry(pwq);

if (!entry)

return;

entry->filp = get_file(filp);

entry->wait_address = wait_address;

// 設置敢興趣的事件

entry->key = p->_key;

// 設置等待節點的回調函數為 pollwake，也即喚醒函數

init_waitqueue_func_entry(&entry->wait, pollwake);

// 指向本次 select 操作的 等待隊列

entry->wait.private = pwq;

// 把等待節點添加到文件的等待隊列上

add_wait_queue(wait_address, &entry->wait);

}

static inline void init_poll_funcptr(poll_table *pt, poll_queue_proc qproc)

{

pt->_qproc = qproc;

pt->_key = ~0UL; /* all events enabled */

}

3.2 喚醒

static int pollwake(wait_queue_entry_t *wait, unsigned mode, int sync, void *key)

{

struct poll_table_entry *entry;

// 找出等待節點 poll_table_entry

entry = container_of(wait, struct poll_table_entry, wait);

// 檢測是否發生了敢興趣的事件

if (key && !((unsigned long)key & entry->key))

return 0;

// 執行喚醒

return __pollwake(wait, mode, sync, key);

}

// 具體的喚醒邏輯就不展開了，涉及進程調度那些。

static int __pollwake(wait_queue_entry_t *wait, unsigned mode, int sync, void *key)

{

struct poll_wqueues *pwq = wait->private;

DECLARE_WAITQUEUE(dummy_wait, pwq->polling_task);

/*

* Although this function is called under waitqueue lock, LOCK

* doesn't imply write barrier and the users expect write

* barrier semantics on wakeup functions. The following

* smp_wmb() is equivalent to smp_wmb() in try_to_wake_up()

* and is paired with smp_store_mb() in poll_schedule_timeout.

*/

smp_wmb();

pwq->triggered = 1; // 設置為已觸發

/*

* Perform the default wake up operation using a dummy

* waitqueue.

*

* TODO: This is hacky but there currently is no interface to

* pass in @sync. @sync is scheduled to be removed and once

* that happens, wake_up_process() can be used directly.

*/

return default_wake_function(&dummy_wait, mode, sync, key);

}

4. 小結

4.0 概要說明

1. select 調用使用 fd_set 這個位圖數據結構來傳遞輸入事件、結果。
2. select執行時，由於內核不能直接訪問用戶空間，因此需要用 3 個位圖來存放輸入的事件，再用3個位圖來存放 poll 的結果。fd_set_bits 裡的6個指針分別指向這 6 個位圖的起始地址。
3. 從 do_select 的邏輯可以看到：

• select 實現首先嚐試在棧上分配一塊內存來存放上述6個位圖，如果存放不下則申請新的內存塊來存放。
• 每次 select 調用都嘗試對所有的文件分批次調用 poll，在每個批次之間會睡眠。
• 如果還沒有文件有感興趣的事件發生，則在被 poll 的文件的等待隊列上加入等待節點。一旦某個文件有事件發生，則後續的文件不管是否有事件發生，都不再加入等待節點。
• 如果前一輪 poll 沒有感興趣的事件發生，進程進入睡眠，等待喚醒或直至超時或有信號要處理；進程再次運行時，仍然需要 poll 所有的文件。
• select 調用結束前，把本次調用添加到文件等待隊列上的節點都刪除掉。

4.1 不足

1. 最多 poll 1024 個文件的限制。
2. 要 poll 的文件數量很大時，為傳遞輸入的感興趣的事件和輸出結果，在用戶空間與內核空間需要拷貝很大的內存。
3. 效率受限於要 poll 的文件數量，數量越多需要的時間就越多。