第六章 内核数据结构

发表于   |   分类于

内核数据结构

内核中实现了很多通用数据结构，包括Linked list、Queue、Map、Binary tree等

1. 链表

Linux内核中链表随处可见，它将链表节点塞入数据结构中。

链表在linux/types.h中声明，只有两个指针next、prev，是很简单的双向链表，linux/list.h中实现了很多链表操作的宏。

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

在使用的时候只需要在自己的结构中加上struct list_head list,如

1
2
3
4
5
6
struct person
{
    int age;
    char* name;
    struct list_head list;
};

内核常用的一个宏，获得包含member的结构体的指针：

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

利用这个宏，可以方便地得到包含链表的结构体：

1
2
3
4
5
6
7
8
/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

链表操作

函数 说明
list_add 添加节点
list_add_tail 添加到链表尾
list_del 删除一个节点，该节点的内存释放等工作需要自己完成
list_del_init deletes entry from list and reinitialize it
list_move、list_move_tail 把节点移动到另一个链表
list_empty 检查链表是否为空
list_splice、list_splice_tail 合并链表
list_splice_init、list_splice_tail_init 合并链表并初始化
list_for_each、list_for_each_entry 遍历链表
list_for_each_entry_reverse 反向遍历
list_for_each_entry_safe 遍历的同时删除
list_for_each_entry_safe_reverse 反向遍历的同时删除

2. 队列

队列常用来实现生产者消费者模型。Linux内核通用队列成为kfifo，申明:linux/kfifo.h，实现：lib/kfifo.c

Linux提供两个主要操作：enqueue和dequeue，维护了两个偏移量：入口偏移和出口偏移。

1
2
3
4
5
6
7
struct __kfifo {
	unsigned int	in;
	unsigned int	out;
	unsigned int	mask;
	unsigned int	esize;
	void		*data;
};

队列操作

函数 说明
kfifo_alloc 动态分配并初始化
kfifo_init 使用预先分配的buf
kfifo_put、kfifo_in put data into the fifo
kfifo_get、kfifo_out get data from the fifo
kfifo_size kfifo大小
kfifo_avail kfifo可用大小
kfifo_is_empty、kfifo_is_full 队列判断
kfifo_reset removes the entire fifo content
kfifo_free frees the fifo

3. 映射

idr数据结构用于映射用户空间的UID。

idr申明在linux/idr.h，相关函数实现：lib/idr.c

idr机制的介绍:idr机制(32叉树)

  • idr_pre_get调整后备树的大小
  • idr_get_new获取新的UID
  • idr_find
  • idr_remove
  • idr_destory
  • idr_remove_all

4. 二叉树

内核使用红黑树进行调度管理，红黑树
头文件:linux/rbtree.h
实现：lib/rbtree.c

5. 其他数据结构