Linux内核学习——数据结构

发表于

内核数据结构

链表

1
2
3
4
struct list_head {
    struct list_head *next;
    struct list_head *prev;
};

在linux中，链表的实现是非常特别的——它不是把数据结构塞进链表里，而是将链表塞进数据结构里。这样就可以重用定义好的struct结构了。比如：

1
2
3
4
5
6
struct fox{
    unsigned long tail_length;
    unsigned long weight;
    bool is_fantastic;
    struct list_head list;
};

但这样怎么找到结构体foo的其它变量呢，方法很简单，由于结构体的偏移量在编译时已经确定下来了，使用宏定义container_of()我们就可以找到父结构的任何变量。

1
2
3
4
#define container_of(ptr, type, member) ({				\
	const typeof(((type *)0)->member) * __mptr = (ptr);	\
	(type *) ( (char*)__mptr - offsetof(type,member));	\
})

队列

在linux中的通用队列为kfifo，在文件kernel/kfifo.c中实现。提供了两个主要的操作：入列和出队。另外，kfifo对象还维护了两个偏移量：入口偏移和出口偏移。

enqueue操作会拷贝数据到队列中的入口偏移位置，然后入口偏移位置会增加元素数目的值。dequeue操作则是相反的操作。

映射

linux的映射不是一个通用的映射，它将一个唯一的标识树(UID)映射到一个指针