Linux内核数据结构

分类： Linux内核学习 Linux设备驱动2011-01-05 11:55 107人阅读评论(0) 收藏举报

链表，队列，映射，二叉树等数据结构是程序设计中常用的数据结构。为了统一这些数据结构的操作接口，Linux内核开发者实现了一些标准的操作接口及实现（使用了大量的GNU扩展特性），以达到代码重用，开发者应该尽量使用这些标准接口，避免实现自己的再创造，虽然那样看起来很酷，很有劲。

有关链表

传统的双向链表实现方法是在链表元素中加入两个指针，然后用这些指针来构造双向链表。如下所示

[cpp] view plain copy

struct node{
value_type value;
struct element *prev;
struct element *next;
}node, *list_head;

其示意图如下：NULL为空指针。

如果将双向链表中的首尾两个元素进行链接，则会形成循环双向链表。示意图如下：

由上可以看出，如果想得到链表中某个指定节点，必须要遍历链表。所以，对于那些需要随机存取的数据，尽量使用数组，而不是链表，当然也可以配合一个哈希表来使用链表，有兴趣的同志可以看看。

上面的实现方法没有问题，但是对于内核来说，如果每个内核对象都采用这种方法，那么要为每个结构体添加相应代码，还要实现其链表操作函数。这样很麻烦，而且也不能达到代码复用以及提供统一的接口。所以内核开发者采用了另外一种巧妙的方法：声明list_head这么一个结构，然后只要嵌入这么一个数据结构就可以实现双向链表了。

[c-sharp] view plain copy

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

假设你想以链表形式存储自己的课程与成绩，则可以采用下面的形式

[c-sharp] view plain copy

struct cource_score{
int num;
int score;
struct list_head list;
};

这样，就利用成员变量list将所有的链表节点连接起来，当然，一般还要设置一个头结点。

除此之外，开发者还提供了一些函数和宏用于链表操作。如使用container_of()可以通过list成员获得course_score结构体的地址。

[c-sharp] view plain copy

#define container_of(ptr, type, member) ({ /
const typeof( ((type *)0)->member ) *_mptr = (ptr); /
(type *)( (char *)_mptr - offsetof(type, member) ) ;})
#define offsetof(type, member) ((ssize_t)&(type *)0)->member)
#define list_entry(ptr, type, member) /
constainer_of(ptr, type, member)

宏container_of使用了GNU扩展。分析一下这个宏定义，首先注意ptr为指向容器结构体的指针，type为容器结构体的类型，而member则是其内嵌的list_head成员变量的名称，如上例，type为course_score，而member则为list。

(type *)0将地址0转换为结构type的地址

(type *)0->member获取type机构体中member成员变量的偏移地址。由于容器结构体的地址为0，这就是member成员的偏移地址，所以宏offsetof也就是这个作用。

typeof( ((type *)0->member)返回member成员的类型，然后将指针_mptr声明为该类型的指针，并赋值为ptr。

(type *)((char *)_mptr - offsetof(type, member));})则根据member成员的实际_mptr以及偏移量offsetof()则可以得到容器结构体的地址。

当有两种方法可以初始化链表，静态初始化和动态初始化。

[c-sharp] view plain copy

#define LIST_HEAD_INIT(name) {&(name),&name)}
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do{/
(ptr)->next = (ptr);(ptr)->next = (ptr);/
}while (0)
static inline void INIT_LIST_HEAD(struct list_head * list)
{
list->next = list;
list->prev = list;
}

如果在编码时初始化链表，则可以使用宏LIST_HEAD_INIT，如上例中，则可以

[c-sharp] view plain copy

struct course_score math = {
num = 1;
score = 60;
list = LIST_HEAD_INIT(math.list);
};

如果是运行时初始化链表,则可以使用宏INIT_LIST_HEAD或者内联函数INIT_LIST_HEAD来初始化，两者功能一样，只是内联函数提供了类型检测。如下所示

[c-sharp] view plain copy

struct course_score *math;
math = kmalloc(sizeof(struct course_score));
math->num = 1;
math->score = 60;
INIT_HEAD_LIST(&math->list);

链表的其他操作包括添加、删除、合并、遍历等。

插入节点

[c-sharp] view plain copy

static inline void list_add(struct list_head * new , struct list_head * head)
{
__list_add(new , head, head->next);
}
static inline void list_add_tail(struct list_head * new ,struct list_head * head)
{
__list_add(new , head->prev, head);
}
struct 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 ;
}

插入操作有两种：表头插入和表尾插入。实际上，两种插入的方法是一样的，只是内部函数调用时，参数不同而已。

删除节点

[c-sharp] view plain copy

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
static inline void list_del(struct list_head * entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POSITION;
entry->prev = LIST_POSITION;
}

对 LIST_POISON1,LIST_POISON2 的解释：

These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized list entries.

[c-sharp] view plain copy

#define LIST_POISON1 ((void *) 0x00100100)
#define LIST_POISON2 ((void *) 0x00200200)

移动节点

[c-sharp] view plain copy

static inline void list_move(struct list_head * list, struct list_head * head)
{
__list_del(list->prev, list->next);
list_add(list, head);
}
static inline void list_move_tail(struct list_head * list, struct list_head * head)
{
__list_del(list->prev, list->next);
list_add_tail(list, head);
}

链表合并

[c-sharp] view plain copy

static inline void _list_splice(struct list_head * list, struct list_head * head)
{
struct list_head * first = list->next;
struct list_head * last = list->prev;
struct list_head * at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
static inline void list_splice(struct list_head * list, struct list_head * head)
{
if(!list_empty(list))
__list_splice(list, head);
}

将一个非空链表插入到另外一个链表中。先做链表是否为空的检查，因为每个链表只有一个头节点，将空链表插入到另外一个链表中是没有意义的。但被插入的链表可以是空的。两个链表有两个头结点，在函数中要去掉一个头结点。

链表遍历

[c-sharp] view plain copy

#define list_for_each(pos, head)/
for(pos = (head)->next; prefetch(pos->next), pos != (head);
static inline void prefetch(void *x)
{
asm volatile("prefetch0 %0":
:
"m"(* unsigned long *)x));
}
#define list_for_each_entry(pos, head, member) /
for(pos = list_entry((head)->next, typeof(*pos),member); /
prefetch(pos->member.next), &pos->member != (head); /
pos = list_entry(pos->member.next, typeof(*pos),member))

prefetch为预取函数，提前预取下一指令，能提高程序执行速度。

队列

队列也是一种链表，只是针对队列的操作只能是从队尾插入，从队首删除。在操作系统中有很多这种数据结构的用武之地，一般是一个进程产生数据，另外一个进程处理数据，如Linux中网络数据包的处理，进程之间使用管道通信等，都是这种情况。Linux内核中队列称作kfifo，其对应的源文件时kernel/kfifo.c，<linux/kfifo.h>中包含了其声明。

 
    [c-sharp]  
    view plain 
    copy 
     
   
struct __kfifo {  
    unsigned int    in;  
    unsigned int    out;  
    unsigned int    mask;  
    unsigned int    esize;  
    void        *data;  
};  
 
 
#define __STRUCT_KFIFO_COMMON(datatype, recsize, ptrtype) /  
    union { /  
        struct __kfifo    kfifo; /  
        datatype    *type; /  
        char        (*rectype)[recsize]; /  
        ptrtype        *ptr; /  
        const ptrtype    *ptr_const; /  
    }  
 
 
#define __STRUCT_KFIFO_PTR(type, recsize, ptrtype) /  
{ /  
    __STRUCT_KFIFO_COMMON(type, recsize, ptrtype); /  
    type        buf[0]; /  
}  
  
  
struct kfifo __STRUCT_KFIFO_PTR(unsigned char, 0, void);  

kfifo提供了两种操作，入队(in)和出队(out)，为了记录下一次出队或者入队的位置，kfifo维护了两个变量in和out。入队操作会将数据拷贝至队列中，具体位置由in确定，然后根据数据大小更新in，标识下一入队发生的位置。出队的操作与之类似。当in和out相等时，队列为空，此时不能执行出队操作。当in等于队列长度时，不能执行入队操作。

和其他内核对象一样，定义并初始化队列也有静态和动态两种方式。

动态方法

 
    [c-sharp]  
    view plain 
    copy 
     
   
static inline int __must_check  
__kfifo_int_must_check_helper(int val)  
{  
    return val;  
}  
 
 
#define kfifo_alloc(fifo, size, gfp_mask) /  
__kfifo_int_must_check_helper( /  
({ /  
    typeof((fifo) + 1) __tmp = (fifo); /  
    struct __kfifo *__kfifo = &__tmp->kfifo; /  
    __is_kfifo_ptr(__tmp) ? /  
    __kfifo_alloc(__kfifo, size, sizeof(*__tmp->type), gfp_mask) : /  
    -EINVAL; /  
}) /  
)  

这个函数创建并初始化一个大小为size的队列。gfp_mask指定内存分配方式，可以取值GFP_KERNEL，GFP_ATOMIC，当在进程上下文分配内存，使用GFP_KERNEL，此时，允许kmalloc函数因为等待内存页释放而睡眠。如果，在中断上下文中分配内存，使用GFP_ATOMIC，此时kmalloc不能睡眠，此时可能由于内存不足导致分配失败。

如果，你想自己分配队列空间，可以使用下面这个函数。

 
    [c-sharp]  
    view plain 
    copy 
     
   
#define kfifo_init(fifo, buffer, size) /  
({ /  
    typeof((fifo) + 1) __tmp = (fifo); /  
    struct __kfifo *__kfifo = &__tmp->kfifo; /  
    __is_kfifo_ptr(__tmp) ? /  
    __kfifo_init(__kfifo, buffer, size, sizeof(*__tmp->type)) : /  
    -EINVAL; /  
})  

这个函数创建并初始化kfifo，这个kfifo使用buffer指向的大小为size的区域作为队列节点存储区域。注意，size必须为2的n次方，即size = 2 ⁿ。

静态方法

DECLARE_KFIFO(name, size);

INIT_KFIFO(name);

入队

但kfifo成功创建后，就可以想队列尾部放入数据

 
    [c-sharp]  
    view plain 
    copy 
     
   
#define    kfifo_in(fifo, buf, n) /  
({ /  
    typeof((fifo) + 1) __tmp = (fifo); /  
    typeof((buf) + 1) __buf = (buf); /  
    unsigned long __n = (n); /  
    const size_t __recsize = sizeof(*__tmp->rectype); /  
    struct __kfifo *__kfifo = &__tmp->kfifo; /  
    if (0) { /  
        typeof(__tmp->ptr_const) __dummy __attribute__ ((unused)); /  
        __dummy = (typeof(__buf))NULL; /  
    } /  
    (__recsize) ?/  
    __kfifo_in_r(__kfifo, __buf, __n, __recsize) : /  
    __kfifo_in(__kfifo, __buf, __n); /  
})  

这个函数将buf开始的n个字符插入队列。这里是尽最大努力的拷贝，也就是说如果空间不足，拷贝的大小就是可用空间可容纳的大小。

出队

 
    [c-sharp]  
    view plain 
    copy 
     
   
#define    kfifo_out(fifo, buf, n) /  
__kfifo_uint_must_check_helper( /  
({ /  
    typeof((fifo) + 1) __tmp = (fifo); /  
    typeof((buf) + 1) __buf = (buf); /  
    unsigned long __n = (n); /  
    const size_t __recsize = sizeof(*__tmp->rectype); /  
    struct __kfifo *__kfifo = &__tmp->kfifo; /  
    if (0) { /  
        typeof(__tmp->ptr) __dummy = NULL; /  
        __buf = __dummy; /  
    } /  
    (__recsize) ?/  
    __kfifo_out_r(__kfifo, __buf, __n, __recsize) : /  
    __kfifo_out(__kfifo, __buf, __n); /  
}) /  
)  

这个函数从队列中读出长度为n的数据，然后放入以buf表示的缓冲区中。出队意味着以后数据已不在队列中，你也可以调用函数kfifo_out_peek来读取数据而不从队列中删除这些数据。对于队列的操作需要注意的就是同步的问题，因为这等效于读者和写者问题。有兴趣可以看看内核中的实现。

其他队列的操作还有很多，代码文件位于linux/kfifo.c以及include/linux/kfifo.h中。

秒客网

Linux内核数据结构

相关文章