linux内核设计与实现（第六章）----内核数据结构

ゞ浴缸里的玫瑰 2022-10-02 01:48 259阅读 0赞

作为一个合格的linux驱动工程师，在查看linux内核代码中，发现内核数据结构贯穿于整个内核代码。

在这里介绍4种最基本的数据结构，可以在内核代码编写中节约大量的时间。

## 主要内容： ##

1.  链表
2.  队列
3.  映射

# 1 链表 #

链表是linux内核中最简单的，同时也是使用最广泛的数据结构，内核中使用的是一种双向链表。

## 1.1头文件简介 ##

内核中关于链表定义的代码位于： include/linux/list.h

list.h文件中对每个函数都有注释，这里就不详细说了。

其实刚开始只要先了解一个常用的链表操作（追加，删除，遍历）的实现方法，

其他方法基本都是基于这些常用操作的。

## 1.2 链表代码的注意点 ##

在阅读list.h文件之前，有一点必须注意：linux内核中的链表使用方法和一般数据结构中定义的链表是有所不同的。

一般的双向链表一般是如下的结构，

*  有个单独的头结点(head)
 *  每个节点(node)除了包含必要的数据之外，还有2个指针(pre,next)
 *  pre指针指向前一个节点(node)，next指针指向后一个节点(node)
 *  头结点(head)的pre指针指向链表的最后一个节点
 *  最后一个节点的next指针指向头结点(head)

具体见下图：

![1372245483_5101.png][]

传统的链表有个最大的缺点就是不好共通化，因为每个node中的data1，data2等等都是不确定的(无论是个数还是类型)。

linux中的链表巧妙的解决了这个问题，linux的链表不是将用户数据保存在链表节点中，而是将链表节点保存在用户数据中。

linux的链表节点只有2个指针(pre和next)，这样的话，链表的节点将独立于用户数据之外，便于实现链表的共同操作。

具体见下图：

![1372245484_4910.png][]

linux链表中的最大问题是怎样通过链表的节点来取得用户数据？

和传统的链表不同，linux的链表节点(node)中没有包含用户的用户data1，data2等。

整个list.h文件中，我觉得最复杂的代码就是获取用户数据的宏定义

#define list_entry(ptr, type, member) \
        container_of(ptr, type, member)

这个宏没什么特别的，主要是container\_of这个宏

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

这里面的type一般是个结构体，也就是包含用户数据和链表节点的结构体。

ptr是指向type中链表节点的指针

member则是type中定义链表节点是用的名字

比如

struct student
    {
        int id;
        char* name;
        struct list_head list;
    };

*  type是struct student
 *  ptr是指向stuct list的指针，也就是指向member类型的指针
 *  member就是 list

下面分析一下container\_of宏:

复制代码
    
    // 步骤1：将数字0强制转型为type*，然后取得其中的member元素
    ((type *)0)->member  // 相当于((struct student *)0)->list
    
    // 步骤2：定义一个临时变量__mptr，并将其也指向ptr所指向的链表节点
    const typeof(((type *)0)->member)*__mptr = (ptr);
    
    // 步骤3：计算member字段距离type中第一个字段的距离，也就是type地址和member地址之间的差
    // offset(type, member)也是一个宏，定义如下：
    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    
    // 步骤4：将__mptr的地址 - type地址和member地址之间的差
    // 其实也就是获取type的地址

步骤1，2，4比较容易理解，下面的图以sturct student为例进行说明步骤3：

首先需要知道 ((TYPE \*)0) 表示将地址0转换为 TYPE 类型的地址

由于TYPE的地址是0，所以((TYPE \*)0)->MEMBER 也就是 MEMBER的地址和TYPE地址的差，如下图所示：

![16132055-c76dbaa451034effa0a132a2bda35c23.png][]

## 1.3 使用示例 ##

构造一个内核模块使用内核链表，代码在ubuntu中运行。

c代码：

#include <linux/init.h>
    #include <linux/slab.h>
    #include <linux/module.h>
    #include <linux/kernel.h>
    #include <linux/list.h>
    
    MODULE_LICENSE("Dual BSD/GPL");
    
    struct student
    {
    	int id;
    	char *name;
    	struct list_head list;
    };
    
    void print_student(struct student *stu)
    {
    	printk("=================\n");
    	printk("id = %d\n",stu->id);
    	printk("name = %s\n",stu->name);
    	printk("=================\n");
    }
    
    static int testlist_init(void)
    {
    	struct student *stu1,*stu2,*stu3,*stu4;
    	struct student *stu;
    	
    	LIST_HEAD(stu_head);
    	stu1 = kmalloc(sizeof(*stu1),GFP_KERNEL);
    	stu1->id = 1;
    	stu1->name = "laoyl";
    	INIT_LIST_HEAD(&stu1->list);
    
    	stu2 = kmalloc(sizeof(*stu2),GFP_KERNEL);
    	stu2->id = 2;
    	stu2->name = "laoyl2";
    	INIT_LIST_HEAD(&stu2->list);
    
    	stu3 = kmalloc(sizeof(*stu3),GFP_KERNEL);
    	stu3->id = 3;
    	stu3->name = "laoyl3";
    	INIT_LIST_HEAD(&stu3->list);
    
    	stu4 = kmalloc(sizeof(*stu4),GFP_KERNEL);
    	stu4->id = 4;
    	stu4->name = "laoyl4";
    	INIT_LIST_HEAD(&stu4->list);
    
    	list_add(&stu1->list,&stu_head);
    	list_add(&stu2->list,&stu_head);
    	list_add(&stu3->list,&stu_head);
    	list_add(&stu4->list,&stu_head);
    
    	list_for_each_entry(stu,&stu_head,list)
    	{
    		print_student(stu);
    	}
    
    	list_for_each_entry_reverse(stu,&stu_head,list)
    	{
    		print_student(stu);
    	}
    
    	list_del(&stu2->list);
    	list_for_each_entry(stu,&stu_head,list)
    	{
    		print_student(stu);
    	}
    
    //	list_replace(&stu3->list,&stu2->list);
    	list_add_tail(&stu2->list,&stu_head);
    	list_for_each_entry(stu,&stu_head,list)
    	{
    		print_student(stu);
    	}
    
    	return 0;
    }
    
    static void testlist_exit(void)
    {
    	printk("******************\n");
    	printk("testlist is exited\n");
    	printk("******************\n");
    }
    
    module_init(testlist_init);
    module_exit(testlist_exit);

Makefile：

ifneq ($(KERNELRELEASE),)
    
    obj-m := list.o
    
    else
    LINUX_KERNEL:=$(shell uname -r)
    KDIR := /lib/modules/$(LINUX_KERNEL)/build
    all:
    	make -C $(KDIR) M=$(PWD) modules 
    clean:
    	rm -f *.ko *.o *.mod.o *.mod.c *.symvers
    
    endif

# 2 队列 #

内核中的队列是以字节形式保存数据的，所以获取数据的时候，需要知道数据的大小。

如果从队列中取得数据时指定的大小不对的话，取得数据会不完整或过大。

## 2.1 头文件简介 ##

内核中关于队列定义的头文件位于：<linux/kfifo.h> include/linux/kfifo.h

头文件中定义的函数的实现位于：kernel/kfifo.c

## 2.2 队列代码的注意点 ##

内核队列编程需要注意的是：

*  队列的size在初始化时，始终设定为2的n次方
 *  使用队列之前将队列结构体中的锁(spinlock)释放

## 2.3 使用示例 ##

构造一个内核模块使用内核队列，代码在ubuntu中运行。

c代码：

#include "kn_common.h"
    
    MODULE_LICENSE("Dual BSD/GPL");
    
    struct student
    {
    	int id;
    	char *name;
    };
    
    static void print_student(struct student*);
    
    static int testkfifo_init(void)
    {
    	struct kfifo fifo;
    	struct student *stu1,*stu2,*stu3,*stu4;
    	struct student *stu_tmp;
    	char *c_tmp;
    	int i,ret;
    	
    	ret = kfifo_alloc(&fifo,4*sizeof(struct student),GFP_KERNEL);
    	if(ret)
    	{
    		printk("kfifo_alloc error\n");
    		return ret;
    	}
    
    	stu1 = kmalloc(sizeof(struct student),GFP_KERNEL);
    	stu1->id = 1;
    	stu1->name = "laoyl1";
    	kfifo_in(&fifo,(char*)stu1,sizeof(struct student));
    
    	stu2 = kmalloc(sizeof(struct student),GFP_KERNEL);
    	stu2->id = 2;
    	stu2->name = "laoyl2";
    	kfifo_in(&fifo,(char*)stu2,sizeof(struct student));
    
    	stu3 = kmalloc(sizeof(struct student),GFP_KERNEL);
    	stu3->id = 3;
    	stu3->name = "laoyl3";
    	kfifo_in(&fifo,(char*)stu3,sizeof(struct student));
    
    	stu4 = kmalloc(sizeof(struct student),GFP_KERNEL);
    	stu4->id = 4;
    	stu4->name = "laoyl4";
    	kfifo_in(&fifo,(char*)stu4,sizeof(struct student));
    
    	c_tmp = kmalloc(sizeof(struct student),GFP_KERNEL);
    	printk("current fifo size is:%d\n",kfifo_size(&fifo));
    	printk("current fifo length is:%d\n",kfifo_len(&fifo));
    	for(i=0;i<4;i++)
    	{
    		kfifo_out(&fifo,c_tmp,sizeof(struct student));
    		stu_tmp = (struct student *)c_tmp;
    		print_student(stu_tmp);
    		printk("current fifo length is:%d\n",kfifo_len(&fifo));
    		printk("current fifo avail is:%d\n",kfifo_avail(&fifo));
    	}
    	printk("current fifo length is:%d\n",kfifo_len(&fifo));
    	kfifo_free(&fifo);
    	kfree(c_tmp);
    	return 0;
    }
    
    static void print_student(struct student *stu)
    {
    	printk("=====================\n");
    	print_current_time(1);
    	printk("id = %d\n",stu->id);
    	printk("name = %s\n",stu->name);
    	printk("=====================\n");
    }
    
    
    static void testkfifo_exit(void)
    {
    	printk("*********************\n");
    	printk("testkfifo is exited!\n");
    	printk("*********************\n");
    }
    
    module_init(testkfifo_init);
    module_exit(testkfifo_exit);

其中引用的kn\_common.h文件：

#include <linux/init.h>
    #include <linux/module.h>
    #include <linux/slab.h>
    #include <linux/kernel.h>
    #include <linux/kfifo.h>
    #include <linux/time.h>
    
    void print_current_time(int is_new_line);

kn\_common.h对应的kn\_common.c：

#include "kn_common.h"
    
    void print_current_time(int is_new_line)
    {
    	struct timeval *tv;
    	struct tm *t;
    	tv = kmalloc(sizeof(struct timeval),GFP_KERNEL);
    	t = kmalloc(sizeof(struct tm),GFP_KERNEL);
    	do_gettimeofday(tv);
    	time_to_tm(tv->tv_sec,0,t);
    	printk("%ld-%d-%d %d:%d:%d",
    			t->tm_year+1900,
    			t->tm_mon+1,
    			t->tm_mday,
    			(t->tm_hour+8)%24,
    			t->tm_min,
    			t->tm_sec);
    	if(is_new_line ==1)
    	{
    		printk("\n");
    	}
    	kfree(tv);
    	kfree(t);
    }

Makefile：

ifneq ($(KERNELRELEASE),)
    
    obj-m +=fifo.o
    fifo-objs := testkfifo.o kn_common.o
    
    else
    KDIR := /ftpdown/linux-source/linux-3.0.8
    all:
    	make -C $(KDIR) M=$(PWD) modules ARCH=arm CROSS_COMPILE=arm-linux-
    	rm -rf *.order *.symvers *.o *.mod.o *.mod.c 	
    clean:
    	rm -f *.ko *.o *.mod.o *.mod.c *.symvers *.order
    
    endif

# 3 映射 #

映射的有点想其他语言(C\#或者python)中的字典类型，每个唯一的id对应一个自定义的数据结构。

## 3.1 头文件简介 ##

内核中关于映射定义的头文件位于：<linux/idr.h> include/linux/idr.h

头文件中定义的函数的实现位于：lib/idr.c

## 3.2 映射代码的注意点 ##

映射的使用需要注意的是，给自定义的数据结构申请一个id的时候，不能直接申请id，先要分配id(函数idr\_pre\_get)，分配成功后，在获取一个id(函数idr\_get\_new)。

idr的结构比较复杂。

## 3.3 使用示例 ##

构造了一个内核模块来实际使用一下内核中的映射，代码在ubuntu运行通过。

C代码:

#include <linux/idr.h>
    #include "kn_common.h"
    
    MODULE_LICENSE("Dual BSD/GPL");
    struct student 
    {
    	int id;
    	char *name;
    };
    
    static int print_student(int,void*,void*);
    
    static int testidr_init(void)
    {
    	DEFINE_IDR(idp);
    	struct student *stu[4];
    
    	int id,ret,i;
    	
    	for(i=0;i<4;i++)
    	{
    		stu[i] = kmalloc(sizeof(struct student),GFP_KERNEL);
    		stu[i]->id = i;
    		stu[i]->name = "laoyl";
    	}
    	
    	print_current_time(1);
    	for(i=0;i<4;i++)
    	{
    		do{
    			if(!idr_pre_get(&idp,GFP_KERNEL))
    				return -ENOSPC;
    			ret = idr_get_new(&idp,stu[i],&id);
    			printk("id=%d\n",id);
    		}while(ret == -EAGAIN);
    	}
    	/* delete */
    	idr_remove(&idp,1);
    	/* find */
    	print_student(0,idr_find(&idp,2),NULL);
    	
    	/* each */
    	idr_for_each(&idp,print_student,(void *)"hello");
    	
    	idr_remove_all(&idp);
    	idr_destroy(&idp);
    	for(i=0;i<4;i++)
    	{
    		kfree(stu[i]);
    	}
    	return 0;
    }
    
    static int print_student(int id,void *p,void *data)
    {
    	struct student *stu = p;
    
    	printk("====================\n");
    	printk("idr-id = %d\n",id);
    	printk("idr-data = %s\n",(char*)data);
    	print_current_time(1);
    	printk("id = %d\n",stu->id);
    	printk("name = %s\n",stu->name);
    	printk("====================\n");
    	return 0;
    }
    
    static void testidr_exit(void)
    {
    	printk("***************************\n");
    	print_current_time(1);
    	printk("testidr is exited!\n");
    	printk("***************************\n");
    }
    
    module_init(testidr_init);
    module_exit(testidr_exit);

**注：**其中用到的kn\_common.h和kn\_common.c文件与队列的示例中一样。

Makefile:

ifneq ($(KERNELRELEASE),)
    
    obj-m +=idr.o
    idr-objs := testidr.o kn_common.o
    
    else
    KDIR := /ftpdown/linux-source/linux-3.0.8
    all:
    	make -C $(KDIR) M=$(PWD) modules ARCH=arm CROSS_COMPILE=arm-linux-
    	rm -rf *.order *.symvers *.o *.mod.o *.mod.c 	
    clean:
    	rm -f *.ko *.o *.mod.o *.mod.c *.symvers *.order
    
    endif

[1372245483_5101.png]: https://img-my.csdn.net/uploads/201306/26/1372245483_5101.png
[1372245484_4910.png]: https://img-my.csdn.net/uploads/201306/26/1372245484_4910.png
[16132055-c76dbaa451034effa0a132a2bda35c23.png]: /images/20220113/05d1aa58cad24d6bb3cd779a65a5c734.png