+-
Linux 内核 常用数据结构

相关教程

Linux内核,让你不知如何下手的地方

Linux内核网卡技术分享

工程师的圣地—Linux内核, 谈谈内核的架构

Linux内核,进程间通信组件的实现


...

linux 内核 常用数据结构

Linux 内核代码中广泛使用了数据结构和算法,其中最常用的两个是链表和红黑树。

链表

Linux 内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而

产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。链表的每个元素都是

离散存放的,因此不需要占用连续的内存。链表通常由若干节点组成,每个节点的结构都是

一样的,由有效数据区和指针区两部分组成。有效数据区用来存储有效数据信息,而指针区

用来指向链表的前继节点或者后继节点。因此,链表就是利用指针将各个节点串联起来的一

种存储结构。

(1)单向链表

单向链表的指针区只包含一个指向下一个节点的指针,因此会形成一个单一方向的链表,如

下代码所示。

struct list { int data; /*有效数据*/ struct list *next; /*指向下一个元素的指针*/ };

如图所示,单向链表具有单向移动性,也就是只能访问当前的节点的后继节点,而无法访问

当前节点的前继节点,因此在实际项目中运用得比较少。

(2)双向链表

如图所示,双向链表和单向链表的区别是指针区包含了两个指针,一个指向前继节点,另一

个指向后继节点,如下代码所示。

struct list { int data; /*有效数据*/ struct list *next; /*指向下一个元素的指针*/ struct list *prev; /*指向上一个元素的指针*/ };

(3)Linux 内核链表实现

单向链表和双向链表在实际使用中有一些局限性,如数据区必须是固定数据,而实际需求是

多种多样的。这种方法无法构建一套通用的链表,因为每个不同的数据区需要一套链表。为

此,Linux 内核把所有链表操作方法的共同部分提取出来,把不同的部分留给代码编程者自

己去处理。Linux 内核实现了一套纯链表的封装,链表节点数据结构只有指针区而没有数据

区,另外还封装了各种操作函数,如创建节点函数、插入节点函数、删除节点函数、遍历节

点函数等。

Linux 内核链表使用 struct list_head 数据结构来描述。

<include/linux/types.h> struct list_head { struct list_head *next, *prev; };

struct list_head 数据结构不包含链表节点的数据区,通常是嵌入其他数据结构,如 struct page

数据结构中嵌入了一个 lru 链表节点,通常是把 page 数据结构挂入 LRU 链表。

<include/linux/mm_types.h> struct page { ... struct list_head lru; ... }

链表头的初始化有两种方法,一种是静态初始化,另一种动态初始化。把 next 和 prev 指针

都初始化并指向自己,这样便初始化了一个带头节点的空链表。

<include/linux/list.h> /*静态初始化*/ #define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) /*动态初始化*/ static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; }

添加节点到一个链表中,内核提供了几个接口函数,如 list_add()是把一个节点添加到表头,

list_add_tail()是插入表尾。

<include/linux/list.h> void list_add(struct list_head *new, struct list_head *head) list_add_tail(struct list_head *new, struct list_head *head)

遍历节点的接口函数。

#define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)

这个宏只是遍历一个一个节点的当前位置,那么如何获取节点本身的数据结构呢?这里还需

要使用 list_entry()宏。

#define list_entry(ptr, type, member) \ container_of(ptr, type, member) container_of()宏的定义在 kernel.h 头文件中。 #define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

其中 offsetof()宏是通过把 0 地址转换为 type 类型的指针,然后去获取该结构体中 member

成员的指针,也就是获取了 member 在 type 结构体中的偏移量。最后用指针 ptr 减去 offset,

就得到 type 结构体的真实地址了。

下面是遍历链表的一个例子。

<drivers/block/osdblk.c> static ssize_t class_osdblk_list(struct class *c, struct class_attribute *attr, char *data) { int n = 0; struct list_head *tmp; list_for_each(tmp, &osdblkdev_list) { struct osdblk_device *osdev; osdev = list_entry(tmp, struct osdblk_device, node); n += sprintf(data+n, "%d %d %llu %llu %s\n", osdev->id, osdev->major, osdev->obj.partition, osdev->obj.id, osdev->osd_path); } return n; }

红黑树

红黑树(Red Black Tree)被广泛应用在内核的内存管理和进程调度中,用于将排序的元素组

织到树中。红黑树被广泛应用在计算机科学的各个领域中,它在速度和实现复杂度之间提供

一个很好的平衡。

红黑树是具有以下特征的二叉树。

 每个节点或红或黑。

 每个叶节点是黑色的。

 如果结点都是红色,那么两个子结点都是黑色。

 从一个内部结点到叶结点的简单路径上,对所有叶节点来说,黑色结点的数目都是相同

的。

红黑树的一个优点是,所有重要的操作(例如插入、删除、搜索)都可以在 O(log n)时间内

完成,n 为树中元素的数目。经典的算法教科书都会讲解红黑树的实现,这里只是列出一个

内核中使用红黑树的例子,供读者在实际的驱动和内核编程中参考。这个例子可以在内核代

码的 documentation/Rbtree.txt 文件中找到。

#include <linux/init.h> #include <linux/list.h> #include <linux/module.h> #include <linux/kernel.h> #include <linux/slab.h> #include <linux/mm.h> #include <linux/rbtree.h> MODULE_AUTHOR("figo.zhang"); MODULE_DESCRIPTION(" "); MODULE_LICENSE("GPL"); struct mytype { struct rb_node node; int key; }; /*红黑树根节点*/ struct rb_root mytree = RB_ROOT; /*根据 key 来查找节点*/ struct mytype *my_search(struct rb_root *root, int new) { struct rb_node *node = root->rb_node; while (node) { struct mytype *data = container_of(node, struct mytype, node); if (data->key > new) node = node->rb_left; else if (data->key < new) node = node->rb_right; else return data; } return NULL; } /*插入一个元素到红黑树中*/ int my_insert(struct rb_root *root, struct mytype *data) { struct rb_node **new = &(root->rb_node), *parent=NULL; /* 寻找可以添加新节点的地方 */ while (*new) { struct mytype *this = container_of(*new, struct mytype, node); parent = *new; if (this->key > data->key) new = &((*new)->rb_left); else if (this->key < data->key) { new = &((*new)->rb_right); } else return -1; } /* 添加一个新节点 */ rb_link_node(&data->node, parent, new); rb_insert_color(&data->node, root); return 0; } static int __init my_init(void) { int i; struct mytype *data; struct rb_node *node; /*插入元素*/ for (i =0; i < 20; i+=2) { data = kmalloc(sizeof(struct mytype), GFP_KERNEL); data->key = i; my_insert(&mytree, data); } /*遍历红黑树,打印所有节点的 key 值*/ for (node = rb_first(&mytree); node; node = rb_next(node)) printk("key=%d\n", rb_entry(node, struct mytype, node)->key); return 0; } static void __exit my_exit(void) { struct mytype *data; struct rb_node *node; for (node = rb_first(&mytree); node; node = rb_next(node)) { data = rb_entry(node, struct mytype, node); if (data) { rb_erase(&data->node, &mytree); kfree(data); } } } module_init(my_init); module_exit(my_exit);

mytree 是红黑树的根节点,my_insert()实现插入一个元素到红黑树中,my_search()根据 key

来查找节点。内核大量使用红黑树。