Chinaunix首页 | 论坛 | 博客

分类: LINUX

2009-11-07 10:04:01

链表
使用include/linux/list.h中提供的双链表数据结构,基本上只需嵌入struct list_head到你的数据结构中即可:
#include

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

struct mydatastructure {
        struct list_head mylist;
        /*...*/
};

链表编程接口:
INIT_LIST_HEAD() 初始化链表头
list_add() 在链表头后面添加一个元素
list_add_tail() 在链表尾添加一个元素
list_del() 从链表中删除一个元素
list_replace() 替换链表中一个元素
list_entry() 循环遍历所有结点
list_for_each_entry()/list_for_each_entry_safe() 更简单的遍历接口
list_empty() 检查链表是否为空
list_splice() 合并两个链表
为解释上述函数的使用方法,我们来实现一个例子吧。这个例子也是理解工作队列概念的基础。假设你的内核驱动需要在一个入口点执行一个责任重大的任务。例如强制调用线程进入睡眠等待任务。很自然的,你的驱动不喜欢阻塞至任务结束。所以无论驱动何时需要执行这个昂贵工作,通过添加对应的程序到工作功能链表中来延迟执行。实际工作由一个内核线程完成,它遍历整个链表并在后台执行工作函数。驱动提交工作函数到链表尾部,内核线程从链表头部取结点,因此保证了先进入工作队列的先处理。例子的关键数据结构:
 1 static struct_mydrv_wq {
 2     struct list_head mydrv_worklist; /*工作链表*/
 3     spinlock_t lock; /*保护链表*/
 4     wait_queue_head_t todo; /*同步提交者和工作者*/
 5 }mydrv_wq;
 6
 7 struct _mydrv_work {
 8     struct list_head mydrv_workitem; /*工作链*/
 9     void (*worker_func)(void *); /*要执行的工作*/
10     void *worker_data; /*worker_func的参数*/
11     /*...*/
12 }mydrv_work;
13

mydrv_wq对于所有工作提交任务是全局的。成员包括一个指向工作链表头的指针和在驱动提交工作函数和执行工作的内核线程之间通信的等待队列。链表助手不保护对链表成员的访问,所以需要你使用并发机制来串行化同时引用,这个是使用自旋锁做到的。驱动初始化程序mydrv_init()初始化自旋锁、链表头和等待队列并启动工作线程:
static int __init mydrv_init(void)
{
    spin_lock_init(&mydrv_wq.lock);
    init_waitqueue_head(&mydrv_wq.todo);
    INIT_LIST_HEAD(&mydrv_wq.mydrv_worklist);
    kernel_thread(mydrv_worker, NULL, CLONE_FS|CLONE_FILES|CLONE|SIGHAND|SIGCHILD);
    return 0;
}

提交稍后要执行的工作:
int submit_work(void (*func)(void *data), void *data)
{
    struct_mydrv_work *mydrv_work;
    mydrv_work = kmalloc(sizeof(struct_mydrv_work), GFP_ATOMIC);

    if (!mydrv_work) return -1;
    mydrv_work->worker_func = func;
    mydrv_work->worker_data = data;

    spin_lock(&mydrv_wq.lock);
    list_add_tail(&mydrv_work->mydrv_workitem, &mydrv_wq.mydrv_worklist);
    wake_up(&mydrv_wq.todo);
    spin_unlock(&mydrv_wq.lock);

    return 0;
}

在提交工作函数后唤醒工作线程。工作线程的通常结构如下,类似标准的内核线程。线程使用list_entry()返回嵌入在链表中的节点数据结构。mydrv_workitem嵌入在mydrv_work中,所以list_entry()返回对应的mydrv_work结构的指针。传递给list_entry()的参数分别是:嵌入结点的地址、包含结构的类型和嵌入链表的名字。
static int mydrv_worker(void *unused)
{
    DECLARE_WAITQUEUE(wait, current);
    void (*worker_func)(void *);
    void *worker_data;
    struct_mydrv_work *mydrv_work;

    set_current_state(TASK_INTERRUPTIBLE);

    while(!asked_to_die()) {
        add_wait_queue(&mydrv_wq.todo, &wait);

        if (list_empty(&mydrv_wq.mydrv_worklist)) {
            schedule();
        } else {
            set_current_state(TASK_RUNNING);
        }
        remove_wait_queue(&mydrv_wq.todo, &wait);

        spin_lock(&mydrv_wq.lock);

        while(!list_empty(&mydrv_wq.mydrv_worklist)) {
            mydrv_work = list_entry(mydrv_wq.mydrv_worklist.next, struct_mydrv_work, mydrv_workitem);
            worker_func = mydrv_work->worker_func;
            worker_data = mydrv_work->worker_data;

            list_del(mydrv_wq.mydrv_worklist.next);
            kfree(mydrv_work);

            spin_unlock(&mydrv_wq.lock);
            worker_func(worker_data);
            spin_lock(&mydrv_wq.lock);
        }
        spin_unlock(&mydrv_wq.lock);
        set_current_state(TASK_INTERRUPTIBLE);
    }

    set_current_state(TASK_RUNNING);
    return 0;
}
阅读(721) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~