Select函數實作原理分析

轉載至：http://blog.chinaunix.net/uid-20643761-id-1594860.html

select需要驅動程式的支援，驅動程式實作fops内的poll函數。select通過每個裝置檔案對應的poll函數提供的資訊判斷目前是否有資源可用(如可讀或寫)，如果有的話則傳回可用資源的檔案描述符個數，沒有的話則睡眠，等待有資源變為可用時再被喚醒繼續執行。

下面我們分兩個過程來分析select：

1. select的睡眠過程

支援阻塞操作的裝置驅動通常會實作一組自身的等待隊列如讀/寫等待隊列用于支援上層(使用者層)所需的BLOCK或NONBLOCK操作。當應用程式通過裝置驅動通路該裝置時(預設為BLOCK操作)，若該裝置目前沒有資料可讀或寫，則将該使用者程序插入到該裝置驅動對應的讀/寫等待隊列讓其睡眠一段時間，等到有資料可讀/寫時再将該程序喚醒。

select就是巧妙的利用等待隊列機制讓使用者程序适當在沒有資源可讀/寫時睡眠，有資源可讀/寫時喚醒。下面我們看看select睡眠的詳細過程。

select會循環周遊它所監測的fd_set内的所有檔案描述符對應的驅動程式的poll函數。驅動程式提供的poll函數首先會将調用select的使用者程序插入到該裝置驅動對應資源的等待隊列(如讀/寫等待隊列)，然後傳回一個bitmask告訴select目前資源哪些可用。當select循環周遊完所有fd_set内指定的檔案描述符對應的poll函數後，如果沒有一個資源可用(即沒有一個檔案可供操作)，則select讓該程序睡眠，一直等到有資源可用為止，程序被喚醒(或者timeout)繼續往下執行。

下面分析一下代碼是如何實作的。

select的調用path如下：sys_select -> core_sys_select -> do_select

其中最重要的函數是do_select, 最主要的工作是在這裡, 前面兩個函數主要做一些準備工作。do_select定義如下：

int do_select(int n, fd_set_bits *fds, s64 *timeout)
{
         struct poll_wqueues table;
         poll_table *wait;
         int retval, i;
 
         rcu_read_lock();
         retval = max_select_fd(n, fds);
         rcu_read_unlock();
 
         if (retval < 0)
                   return retval;
         n = retval;
 
         poll_initwait(&table);
         wait = &table.pt;
         if (!*timeout)
                   wait = NULL;
         retval = 0;        //retval用于儲存已經準備好的描述符數，初始為0
         for (;;) {
                   unsigned long *rinp, *routp, *rexp, *inp, *outp, *exp;
                   long __timeout;
 
                   set_current_state(TASK_INTERRUPTIBLE);    //将目前程序狀态改為TASK_INTERRUPTIBLE
 
                   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;
                            const struct file_operations *f_op = NULL;
                            struct file *file = NULL;
 
                            in = *inp++; out = *outp++; ex = *exp++;
                            all_bits = in | out | ex;
                            if (all_bits == 0) {
                                     i += __NFDBITS;       // //如果這個字沒有待查找的描述符, 跳過這個長字(32位)
                                     continue;
                            }
 
                            for (j = 0; j < __NFDBITS; ++j, ++i, bit <<= 1) {     //周遊每個長字裡的每個位
                                     int fput_needed;
                                     if (i >= n)
                                               break;
                                     if (!(bit & all_bits))
                                               continue;
                                     file = fget_light(i, &fput_needed);
                                     if (file) {
                                               f_op = file->f_op;
                                               MARK(fs_select, "%d %lld",
                                                                 i, (long long)*timeout);
                                               mask = DEFAULT_POLLMASK;
                                               if (f_op && f_op->poll)
/* 在這裡循環調用所監測的fd_set内的所有檔案描述符對應的驅動程式的poll函數 */
                                                        mask = (*f_op->poll)(file, retval ? NULL : wait);
                                               fput_light(file, fput_needed);
                                               if ((mask & POLLIN_SET) && (in & bit)) {
                                                        res_in |= bit; //如果是這個描述符可讀, 将這個位置位
                                                        retval++;  //傳回描述符個數加1
                                               }
                                               if ((mask & POLLOUT_SET) && (out & bit)) {
                                                        res_out |= bit;
                                                        retval++;
                                               }
                                               if ((mask & POLLEX_SET) && (ex & bit)) {
                                                        res_ex |= bit;
                                                        retval++;
                                               }
                                     }
                                     cond_resched();
                            }
//傳回結果
                            if (res_in)
                                     *rinp = res_in;
                            if (res_out)
                                     *routp = res_out;
                            if (res_ex)
                                     *rexp = res_ex;
                   }
                   wait = NULL;
/* 到這裡周遊結束。retval儲存了檢測到的可操作的檔案描述符的個數。如果有檔案可操作，則跳出for(;;)循環，直接傳回。若沒有檔案可操作且timeout時間未到同時沒有收到signal,則執行schedule_timeout睡眠。睡眠時間長短由__timeout決定，一直等到該程序被喚醒。
那該程序是如何被喚醒的？被誰喚醒的呢？
我們看下面的select喚醒過程*/
                   if (retval || !*timeout || signal_pending(current))
                            break;
                  if(table.error) {
                            retval = table.error;
                            break;
                   }
 
                   if (*timeout < 0) {
                            /* Wait indefinitely */
                            __timeout = MAX_SCHEDULE_TIMEOUT;
                   } else if (unlikely(*timeout >= (s64)MAX_SCHEDULE_TIMEOUT - 1)) {
                            /* Wait for longer than MAX_SCHEDULE_TIMEOUT. Do it in a loop */
                            __timeout = MAX_SCHEDULE_TIMEOUT - 1;
                            *timeout -= __timeout;
                   } else {
                            __timeout = *timeout;
                            *timeout = 0;
                   }
                   __timeout = schedule_timeout(__timeout);
                   if (*timeout >= 0)
                            *timeout += __timeout;
         }
         __set_current_state(TASK_RUNNING);
 
         poll_freewait(&table);
 
         return retval;
}

2. select的喚醒過程

前面介紹了select會循環周遊它所監測的fd_set内的所有檔案描述符對應的驅動程式的poll函數。驅動程式提供的poll函數首先會将調用select的使用者程序插入到該裝置驅動對應資源的等待隊列(如讀/寫等待隊列)，然後傳回一個bitmask告訴select目前資源哪些可用。

一個典型的驅動程式poll函數實作如下：

(摘自《Linux Device Drivers – ThirdEdition》Page 165)

static unsigned int scull_p_poll(struct file *filp, poll_table *wait)
{
    struct scull_pipe *dev = filp->private_data;
    unsigned int mask = 0;
    /*
     * The buffer is circular; it is considered full
     * if "wp" is right behind "rp" and empty if the
     * two are equal.
     */
    down(&dev->sem);
    poll_wait(filp, &dev->inq,  wait);
    poll_wait(filp, &dev->outq, wait);
    if (dev->rp != dev->wp)
        mask |= POLLIN | POLLRDNORM;    /* readable */
    if (spacefree(dev))
        mask |= POLLOUT | POLLWRNORM;   /* writable */
    up(&dev->sem);
    return mask;
}

将使用者程序插入驅動的等待隊列是通過poll_wait做的。

Poll_wait定義如下：

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

這裡的p->qproc在do_select内poll_initwait(&table)被初始化為__pollwait，如下：

void poll_initwait(struct poll_wqueues *pwq)
{
         init_poll_funcptr(&pwq->pt, __pollwait);
         pwq->error = 0;
         pwq->table = NULL;
         pwq->inline_index = 0;
}

__pollwait定義如下：

static void __pollwait(struct file *filp, wait_queue_head_t *wait_address,
                                     poll_table *p)
{
         struct poll_table_entry *entry = poll_get_entry(p);
         if (!entry)
                   return;
         get_file(filp);
         entry->filp = filp;
         entry->wait_address = wait_address;
         init_waitqueue_entry(&entry->wait, current);
         add_wait_queue(wait_address,&entry->wait);
}

通過init_waitqueue_entry初始化一個等待隊列項，這個等待隊列項關聯的程序即目前調用select的程序。然後将這個等待隊列項插入等待隊列wait_address。Wait_address即在驅動poll函數内調用poll_wait(filp, &dev->inq, wait);時傳入的該驅動的&dev->inq或者&dev->outq等待隊列。

注: 關于等待隊列的工作原理可以參考下面這篇文檔:

http://blog.chinaunix.net/u2/60011/showart_1334657.html

到這裡我們明白了select如何目前程序插入所有所監測的fd_set關聯的驅動内的等待隊列，那程序究竟是何時讓出CPU進入睡眠狀态的呢？

進入睡眠狀态是在do_select内調用schedule_timeout(__timeout)實作的。當select周遊完fd_set内的所有裝置檔案，發現沒有檔案可操作時(即retval=0),則調用schedule_timeout(__timeout)進入睡眠狀态。

喚醒該程序的過程通常是在所監測檔案的裝置驅動内實作的，驅動程式維護了針對自身資源讀寫的等待隊列。當裝置驅動發現自身資源變為可讀寫并且有程序睡眠在該資源的等待隊列上時，就會喚醒這個資源等待隊列上的程序。

舉個例子，比如核心的8250 uart driver:

Uart是使用的Tty層維護的兩個等待隊列, 分别對應于讀和寫: (uart是tty裝置的一種)

struct tty_struct {
         //……
         wait_queue_head_t write_wait;
         wait_queue_head_t read_wait;
         //……
}

當uart裝置接收到資料，會調用tty_flip_buffer_push(tty);将收到的資料push到tty層的buffer。

然後檢視是否有程序睡眠的讀等待隊列上，如果有則喚醒該等待會列。

過程如下：

serial8250_interrupt -> serial8250_handle_port -> receive_chars -> tty_flip_buffer_push ->

flush_to_ldisc -> disc->receive_buf

在disc->receive_buf函數内：

if (waitqueue_active(&tty->read_wait)) //若有程序阻塞在read_wait上則喚醒

wake_up_interruptible(&tty->read_wait);

到這裡明白了select程序被喚醒的過程。由于該程序是阻塞在所有監測的檔案對應的裝置等待隊列上的，是以在timeout時間内，隻要任意個裝置變為可操作，都會立即喚醒該程序，進而繼續往下執行。這就實作了select的當有一個檔案描述符可操作時就立即喚醒執行的基本原理。

Referece:

1. Linux Device Drivers – ThirdEdition

2. 核心等待隊列機制原理分析

http://blog.chinaunix.net/u2/60011/showart_1334657.html

3. Kernel code : Linux 2.6.18_pro500 - Montavista

Select函數實作原理分析Select函數實作原理分析

Select函數實作原理分析

1. select的睡眠過程

2. select的喚醒過程

繼續閱讀

antdesign和react的使用dropDown定位問題

ant-design的select元件加入value後placeholder不顯示

linux下socket程式設計基礎示例

以後面試官問你為啥不建議使用Select *，請你大聲回答他!

Windows網絡程式設計之（二）Socket通信非阻塞模式Select（TCP和UDP）

TCP Server處理多Client請求的方法—非阻塞accept與select

AngularJS Select(選擇框！)

MDUI中Select初始化問題

c# select資料庫資料

C#泛型清單List<T>基本用法總結

實驗樓sql進階之簡化資料操作提升性能(window)

mysql5.7官網直譯SQL語句優化--where條件查詢優化

五種IO模型：阻塞/非阻塞/複用/信号驅動/異步IO模型1. IO基本概念2. 五種IO模型3. 同步IO和異步IO4. 模式精細講解： MSG_DONTWAIT 、 MSG_WAITALL參考：

同步與異步以及阻塞與非阻塞的差別

老師布置的幾道SQL語句練習題