内核数据结构

更新时间：2019年5月25日17:40:39

内核数据结构

内核的数据结构主要有：链表、队列、映射和红黑树。

参考文献：

https://www.cnblogs.com/wang_yb/archive/2013/04/16/3023892.html

《内核设计与实现》

实验环境

Linux 4.14.120

链表

链表的结构体：

struct list_head{ struct list_head *next; };

内核的链表与常规链表不同，内核链表节点是数据链表的一个成员变量，结构如下图（图片参考自博客）。

将内核链表内嵌至用户数据的链表：

struct node{ int data_; struct list_head list_; }

链表API:

初始化链表头：INIT_HEAD(tmp_head),tmp_head不用事先定义，在宏中被定义，tmp_head本质上一个特殊的索引指针，充当链表的头节点，但是由于链表是双向循环链表，因此也可以选取任何一个环内节点作为头结点；初始化动态创建的用户数据节点（i.e.,链表节点）：INIT_LIST_HEAD(&tmp->list_),tmp为节点指针，节点动态创建，可参考下面实例程序；向链表增加节点，list_add(struct list_head *new, struct list_head *head)和list_add_tail(struct list_head *new, struct list_head *head)遍历，list_for_each_entry是宏，填入参数: list_for_each_entry(pos, head, member){ // struct node *, struct list_head *，struct list_head /* codes */ }

遍历同时删除：list_for_each_entry_safe(pos, next, head, member)，next类型与pos相同，因为链表在删除的时候需要两种指针，另一个指针指向删除的下一个节点（这是链表循环删除操作的常规范式）；反向遍历：XXX_reverse； 5. 删除链表节点：list_del(struct list_head *entry) 6. 移动链表节点：前面list_move(struct list_head *list, struct list_head *head)，后面list_move_tail(struct list_head *list, struct list_head *head) 7. 检查链表为空：list_empty(struct list_head *head) 8. 合并链表：list_splice(struct list_head *list, struct list_head *head)，并且初始化list，list_splice_init(struct list_head *list, struct list_head *head)

测试例程：

#include <linux/module.h> #include <linux/init.h> #include <linux/list.h> #include<linux/slab.h> struct node{ int data_; struct list_head list_; }; void Test(void) { int i; LIST_HEAD(head); struct node *p; struct node *tmp, *next; for(i = 0; i < 10; i++){ p = kmalloc(sizeof(*p), GFP_KERNEL); p->data_ = i + 1; INIT_LIST_HEAD(&p->list_); list_add_tail(&p->list_, &head); } list_for_each_entry(tmp, &head, list_){ printk("data_:%d\n", tmp->data_); } // free list_for_each_entry_safe(tmp, next, &head, list_){ BUG_ON(!tmp); list_del(&tmp->list_); kfree(tmp); } } int linked_list_init(void) { Test(); printk("%s(%d)\n", __func__, __LINE__); return 0; } void linked_list_exit(void) { printk("%s(%d)\n", __func__, __LINE__); } module_init(linked_list_init); module_exit(linked_list_exit); MODULE_AUTHOR("Arnold Lu"); MODULE_LICENSE("GPL"); MODULE_DESCRIPTION("Linked list test");

队列

创建队列，int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gft_mask)（内核自动分配缓冲区）或者void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size)（缓冲区由buffer指定），size是2的幂；入队，unsigned int kfifo_in(struct kfifo *fifo, const void *from, unsigned int len);返回值入队字节数；出队，unsigned int kfifo_out(struct kfifo *fifo, const void *to, unsigned int len);，出队会移除队头数据，若不移除队列元素，可以使用unsigned int kfifo_out_peek(struct kfifo *fifo, const void *to, unsigned int len,unsigned offset);，查看在偏移offset处的数据；存储kfifo队列的空间大小（以字节为单位）static inline unsigned int kfifo_size(struct kfifo *fifo)，kfifo队列以入队的数据大小static inline unsigned int kfifo_len(struct kfifo *fifo)，队列可用空间static inline unsigned int kfifo_avail(struct kfifo *fifo)，队列空/满static inline unsigned int kfifo_is_empty(struct kfifo *fifo);static inline unsigned int kfifo_is_full(struct kfifo *fifo);重置队列（i.e.,清空）static inline void kfifo_reset(struct kfifo *fifo)，释放kfifo_alloc分配的队列,kfifo_free(struct kfifo *)

测试例程：

#include <linux/module.h> #include <linux/init.h> #include <linux/kfifo.h> #include<linux/slab.h> struct node{ int data_; struct list_head list_; }; void Test(void) { struct kfifo* q; int ret = kfifo_alloc(q, 8, GFP_KERNEL); BUG_ON(ret); int *p; p = kmalloc(sizeof(int), GFP_KERNEL); kfifo_in(q, p, sizeof(p)); p = kmalloc(sizeof(int), GFP_KERNEL); kfifo_in(q, p, sizeof(p)); printk(KERN_EMERG "avail size : %d\n", kfifo_avail(q)); printk(KERN_EMERG "total size : %d\n", kfifo_size(q)); kfifo_out(q, p, sizeof(p)); printk(KERN_EMERG "out val : %d\n", *p); printk(KERN_EMERG "avail size : %d\n", kfifo_avail(q)); printk(KERN_EMERG "total size : %d\n", kfifo_size(q)); } int __kfifo_init(void) { Test(); printk("%s(%d)\n", __func__, __LINE__); return 0; } void __kfifo_exit(void) { printk("%s(%d)\n", __func__, __LINE__); } module_init(__kfifo_init); module_exit(__kfifo_exit); MODULE_AUTHOR("Arnold Lu"); MODULE_LICENSE("GPL"); MODULE_DESCRIPTION("Linked list test");

映射

目前网上和书上介绍是函数有int idr_pre_get(struct idr *idp, gfp_t gft_mask)（调整后备树大小，i.e.,增加映射表空间，因为idr底层是radix_tree实现的）和int idr_get_new(struct idr *idp, void *ptr, int *id)（获取新的UID存放于id，并且将ptr与id关联），但是不同版本的Linux定义不同，因此对映射类型不做详细阐述，用时再做探讨，下面提供一个例程：

#include <linux/module.h> #include <linux/init.h> #include <linux/idr.h> #include <linux/slab.h> #define dg_prt(fmt, args...) printk(KERN_EMERG fmt, ##args) void Test(void) { struct idr idr_hub; int val = 10, key1 , key2; idr_init(&idr_hub); if (idr_alloc(&idr_hub, &val, key1, key2, GFP_KERNEL)) BUG_ON(1); dg_prt("key1 = %d, key2 = %d, val = %d\n", key1, key2, val); } int my_idr_init(void) { Test(); printk("%s(%d)\n", __func__, __LINE__); return 0; } void my_idr_exit(void) { printk("%s(%d)\n", __func__, __LINE__); } module_init(my_idr_init); module_exit(my_idr_exit); MODULE_AUTHOR("Arnold Lu"); MODULE_LICENSE("GPL"); MODULE_DESCRIPTION("Linked list test");

红黑树

红黑树以后在介绍。