等待队列中的双向链表建立分析

beyes

等待队列是一个双向链表。主要构成由是一个等待队列头和多个等待队列结构组成。


在内核中，add_wait_queue() 函数用于将一个等待进程添加到等待队列中，该函数定义为：

void fastcall add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
    unsigned long flags;

    wait->flags &= ~WQ_FLAG_EXCLUSIVE;
    spin_lock_irqsave(&q->lock, flags);
    __add_wait_queue(q, wait);
    spin_unlock_irqrestore(&q->lock, flags);
}

该函数在获得必要的自旋锁后，调用 __add_wait_queue() 函数来完成这道工作，__add_wait_queue() 函数定义为：

static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
{
    list_add(&new->task_list, &head->task_list);
}

list_add 是标准链表操作函数，它定义为：

/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

从上面的注释注意到，链表的添加是一种堆栈式添加的，按照添加的规则是先进后出，后进先出。那么可以想象，后来的节点是添加到链表头的。


__list_add() 定义为：

static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

从上面的代码可以看到，新添加的节点会插入到链表头和第一个节点中间。


为了更直观的体现出链表的建立过程，我将相关的宏定义都挪倒用户态程序中，然后打印出链表中指针的指向地址，最后得出链表的结构。客户端代码如下：

#include <stdio.h>

struct list_head {
        struct list_head *next, *prev;
};

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

typedef struct __wait_queue {
        int a;
        int b;
        struct list_head task_list;
}wait_queue_t;

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define DEFINE_WAIT(name)                       \
        wait_queue_t name = {                   \
                .a = 7,                         \
                .b = 8,                         \
                .task_list = LIST_HEAD_INIT((name).task_list),  \
        }

#define __WAIT_QUEUE_HEAD_INITIALIZER(name) {   \
        .lock = 10,                             \
        .task_list = { &(name).task_list, &(name).task_list } }

#define DECLARE_WAIT_QUEUE_HEAD(name) \
        wait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name)

static inline int list_empty(const struct list_head *head)
{
        return head->next == head;
}


static inline void __list_add(struct list_head *new,
                struct list_head *prev,
                struct list_head *next)
{
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
        __list_add(new, head, head->next);
}

static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
{
        list_add(&new->task_list, &head->task_list);
}

void prepare_to_wait (wait_queue_head_t *q, wait_queue_t *wait)
{
        if (list_empty(&wait->task_list))
                __add_wait_queue(q, wait);
}
int main(void)
{
        DECLARE_WAIT_QUEUE_HEAD(wq);
        printf ("header task_list address: 0x%x\n", &wq.task_list);
        printf ("header prev: 0x%x\n", wq.task_list.prev);
        printf ("header next: 0x%x\n", wq.task_list.next);

        printf ("------------list_add a new-------------\n\n");

        DEFINE_WAIT(__wait);
        prepare_to_wait (&wq, &__wait);
        printf ("header prev: 0x%x\n", wq.task_list.prev);
        printf ("header next: 0x%x\n", wq.task_list.next);
        printf ("first node task_list address: 0x%x\n", &__wait.task_list);
        printf ("first node prev: 0x%x\n", __wait.task_list.prev);
        printf ("first node next: 0x%x\n", __wait.task_list.next);

        printf ("------------list_add a new-------------\n");

        DEFINE_WAIT(second);
        prepare_to_wait (&wq, &second);
        printf ("header prev: 0x%x\n", wq.task_list.prev);
        printf ("header next: 0x%x\n", wq.task_list.next);
        printf ("first node prev: 0x%x\n", __wait.task_list.prev);
        printf ("first node next: 0x%x\n", __wait.task_list.next);
        printf ("second node task_list address: 0x%x\n", &second.task_list);
        printf ("second node prev: 0x%x\n", second.task_list.prev);
        printf ("second node next: 0x%x\n", second.task_list.next);

        printf ("------------list_add a new-------------\n");

        DEFINE_WAIT(third);
        prepare_to_wait (&wq, &third);
        printf ("header prev: 0x%x\n", wq.task_list.prev);
        printf ("header next: 0x%x\n", wq.task_list.next);
        printf ("first node prev: 0x%x\n", __wait.task_list.prev);
        printf ("first node next: 0x%x\n", __wait.task_list.next);
        printf ("second node prev: 0x%x\n", second.task_list.prev);
        printf ("second node next: 0x%x\n", second.task_list.next);
        printf ("third node task_list address: 0x%x\n", &third.task_list);
        printf ("third node prev: 0x%x\n", third.task_list.prev);
        printf ("third node next: 0x%x\n", third.task_list.next);

        return (0);
}

运行输出：

linux-kd1q:/home/beyes/C/micro # ./micro
header task_list address: 0xbfc6b3b8
header prev: 0xbfc6b3b8
header next: 0xbfc6b3b8
------------list_add a new-------------


header prev: 0xbfc6b3ac
header next: 0xbfc6b3ac
first node task_list address: 0xbfc6b3ac
first node prev: 0xbfc6b3b8
first node next: 0xbfc6b3b8
------------list_add a new-------------
header prev: 0xbfc6b3ac
header next: 0xbfc6b39c
first node prev: 0xbfc6b39c
first node next: 0xbfc6b3b8
second node task_list address: 0xbfc6b39c
second node prev: 0xbfc6b3b8
second node next: 0xbfc6b3ac
------------list_add a new-------------
header prev: 0xbfc6b3ac
header next: 0xbfc6b38c
first node prev: 0xbfc6b39c
first node next: 0xbfc6b3b8
second node prev: 0xbfc6b38c
second node next: 0xbfc6b3ac
third node task_list address: 0xbfc6b38c
third node prev: 0xbfc6b3b8
third node next: 0xbfc6b39c

首先，使用 DECLARE_WAIT_QUEUE_HEAD 宏静态的建立一个链表头，链表头的名字为 wq 。从第一次的输出：

header task_list address: 0xbfc6b3b8
header prev: 0xbfc6b3b8
header next: 0xbfc6b3b8

此时链表头的结构是：

list_head 结构体里面的指针都指向链表头自身。


下面添加第一个等待节点，从输出代码：

header prev: 0xbfc6b3ac
header next: 0xbfc6b3ac
first node task_list address: 0xbfc6b3ac
first node prev: 0xbfc6b3b8
first node next: 0xbfc6b3b8

我们可以得到如下的结构：

再添加第 2 个节点，从代码片段：

        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;

可以知道，第 2 个节点是插入到链表头和第 1 个节点之间的。比较输出结果中的：

header prev: 0xbfc6b3ac
header next: 0xbfc6b39c
first node prev: 0xbfc6b39c
first node next: 0xbfc6b3b8
second node task_list address: 0xbfc6b39c
second node prev: 0xbfc6b3b8
second node next: 0xbfc6b3ac

也能看出这一点。这时结构如下图所示：

从上图可知，这种节点的添加，犹如堆栈一样，最后进来的就成为了栈顶，先进去的节点则一层一层的往后推去。依次类推后面的节点。注意的是，链表头的 prev 永远指向最后一个节点；最后一个节点的 next 永远指向链表头。下面是一个更美观的图：

0x521

描述的真清晰。我想请教一下你使用什么工具画的图啊？我也想学习学习。

beyes

0x521:描述的真清晰。我想请教一下你使用什么工具画的图啊？我也想学习学习。 (2012-07-03 23:10) 

也有 Windows 里的画图，还有 Linux 里的 GIMP 。

0x521

非常想知道倒数第二张图是用什么工具画的，麻烦分享一下啊，谢啦！

0x521

beyes:也有 Windows 里的画图，还有 Linux 里的 GIMP 。 (2012-07-04 11:48) 

大侠，你的倒数第二张图是用什么工具画的啊？求解