天道酬勤

上一篇介绍了信号量可以使用waitqueue实现，这一篇主要讲waitqueue的实现，waitqueue故名思义就是等待队列。waitqueue在linux中的实现主要在下面文件中：

include/linux/wait.h
kernel/sched/wait.c

一、先看数据结构

struct __wait_queue_head {
         spinlock_t                lock;
         struct list_head        task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;

从数据结构上看，这个实现比较简单，就是一个自旋锁和一个任务列表。这个自旋锁用于保护列表的读取修改。

二、init_waitqueue_head(&_wait); //变量初始化

#define init_waitqueue_head(wq_head)                        \
    do {                                    \
        static struct lock_class_key __key;             \
                                        \
        __init_waitqueue_head((wq_head), #wq_head, &__key);     \
    } while (0)

这个函数由宏定义实现，这个宏定义中包含两个语句，定义了一个struct lock_class_key结构体以及调用了

 __init_waitqueue_head函数初始化这个结构体。下面是这个函数的实现：

void __init_waitqueue_head(wait_queue_head_t *q, const char *name, struct lock_class_key *key)
{
         spin_lock_init(&q->lock);
         lockdep_set_class_and_name(&q->lock, key, name);
         INIT_LIST_HEAD(&q->task_list);
}

这个函数先初始化了结构体中的自旋锁，然后设置了lock_class_key结构体，这个结构体用于死锁检测的，最后初始化了waitqueue结构体的列表。

三、挂起等待的实现

DEFINE_WAIT(wait);      //定义临时变量
prepare_to_wait(&pgdat->kswapd_wait, &wait, TASK_INTERRUPTIBLE);   //设置线程的状态
schedule();         //让出CPU
//在获取到信号后从这里运行
finish_wait(&pgdat->kswapd_wait, &wait); //唤醒后清理上次的信号

介绍到这里需要看下另外一个结构体

struct __wait_queue {
         unsigned int                flags;
         void                        *private;
         wait_queue_func_t        func;        //回调函数
         struct list_head        task_list;                //双向列表的实现，为了挂在wait_queue_head后
};
typedef struct __wait_queue wait_queue_t;

这个结构体是表示的是等待队列的一个节点，对应的task会挂在这个结构体上，一般private所指的就是挂起的任务的结构体。在流程的开头出首先定义了临时的变量，这个定义的方式也是我们熟悉的宏方式，我们可以看到，这里的定义就是初始化了一个wait_queue的节点。这里需要注意的一点是这个回调函数，这个回调函数在唤醒的时候会调用，其作用就是将task任务重新挂在到调度器中，使得等待的任务可以继续运行。

 typedef int (*wait_queue_func_t)(wait_queue_t *wait, unsigned mode, int flags, void *key);
 int default_wake_function(wait_queue_t *wait, unsigned mode, int flags, void *key);
 
 int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
                           void *key)
 {
         return try_to_wake_up(curr->private, mode, wake_flags);
 }
 
 int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key)
 {
         int ret = default_wake_function(wait, mode, sync, key);
 
         if (ret)
                 list_del_init(&wait->task_list);
         return ret;
 }
 
 int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key);
 
 #define DEFINE_WAIT_FUNC(name, function)                                \
         wait_queue_t name = {                                                \
                 .private        = current,                                \
                 .func                = function,                                \
                 .task_list        = LIST_HEAD_INIT((name).task_list),        \
         }
 
 #define DEFINE_WAIT(name) DEFINE_WAIT_FUNC(name, autoremove_wake_function)

下面我们看下prepare_to_wait的实现

prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)
{
         unsigned long flags;
 
         wait->flags &= ~WQ_FLAG_EXCLUSIVE;
         spin_lock_irqsave(&q->lock, flags);
         if (list_empty(&wait->task_list))
                 __add_wait_queue(q, wait);
         set_current_state(state);
         spin_unlock_irqrestore(&q->lock, flags);
}
EXPORT_SYMBOL(prepare_to_wait);

这个函数就是简单的将临时定义的wait_queue挂在原来定义好的（非临时的，其他线程可以获得）wait_queue_head上。下面就是使用schedule方法将当前的线程的CPU让出去，进入等待的时间，等待其他线程的唤醒。

void finish_wait(wait_queue_head_t *q, wait_queue_t *wait)
{
         unsigned long flags;
 
         __set_current_state(TASK_RUNNING);
         /*
          * We can check for list emptiness outside the lock
          * IFF:
          *  - we use the "careful" check that verifies both
          *    the next and prev pointers, so that there cannot
          *    be any half-pending updates in progress on other
          *    CPU's that we haven't seen yet (and that might
          *    still change the stack area.
          * and
          *  - all other users take the lock (ie we can only
          *    have _one_ other CPU that looks at or modifies
          *    the list).
          */
         if (!list_empty_careful(&wait->task_list)) {
                 spin_lock_irqsave(&q->lock, flags);
                 list_del_init(&wait->task_list);
                 spin_unlock_irqrestore(&q->lock, flags);
         }
}

这个函数执行的时候表示当前线程已经被唤醒了，这个函数做的动作就是清理，这里的动作与回调函数基本一致，至于为什么这么做，就是为了防止多核的影响。

四、触发原理实现

上一篇中使用了wake_up_interruptible函数唤醒kswad，这个函数也是由宏实现：

#define wake_up_interruptible(x)        __wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)
//这里1表示唤醒队列中的第一个任务。从实现代码中就可以看出来。
void __wake_up(wait_queue_head_t *q, unsigned int mode,
                         int nr_exclusive, void *key)
{
         unsigned long flags; 
         spin_lock_irqsave(&q->lock, flags);
         __wake_up_common(q, mode, nr_exclusive, 0, key);
         spin_unlock_irqrestore(&q->lock, flags);
}
 
static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
                         int nr_exclusive, int wake_flags, void *key)
{
         wait_queue_t *curr, *next;
         list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
                 unsigned flags = curr->flags;
                 if (curr->func(curr, mode, wake_flags, key) &&
                                 (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
                         break;
         }
}

前面已经说了，在函数指针中，最终调用了sched核心中的try_to_wake_up，唤醒挂在队列上的任务。

最后我们总结一下，用一幅图示意出来，应该比较好理解的