内核数据结构贯穿于整个内核代码中,这里介绍4个基本的内核数据结构。
利用这4个基本的数据结构,可以在编写内核代码时节约大量时间。
主要内容:
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)
具体见下图:
传统的链表有个最大的缺点就是不好共通化,因为每个node中的data1,data2等等都是不确定的(无论是个数还是类型)。
linux中的链表巧妙的解决了这个问题,linux的链表不是将用户数据保存在链表节点中,而是将链表节点保存在用户数据中。
linux的链表节点只有2个指针(pre和next),这样的话,链表的节点将独立于用户数据之外,便于实现链表的共同操作。
具体见下图:
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地址的差,如下图所示:
1.3 使用示例
构造了一个内核模块来实际使用一下内核中的链表,代码在CentOS6.3 x64上运行通过。
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*);
-
-
static int testlist_init(void)
-
{
-
struct student *stu1, *stu2, *stu3, *stu4;
-
struct student *stu;
-
-
// init a list head
-
LIST_HEAD(stu_head);
-
-
// init four list nodes
-
stu1 = kmalloc(sizeof(*stu1), GFP_KERNEL);
-
stu1->id = 1;
-
stu1->name = "wyb";
-
INIT_LIST_HEAD(&stu1->list);
-
-
stu2 = kmalloc(sizeof(*stu2), GFP_KERNEL);
-
stu2->id = 2;
-
stu2->name = "wyb2";
-
INIT_LIST_HEAD(&stu2->list);
-
-
stu3 = kmalloc(sizeof(*stu3), GFP_KERNEL);
-
stu3->id = 3;
-
stu3->name = "wyb3";
-
INIT_LIST_HEAD(&stu3->list);
-
-
stu4 = kmalloc(sizeof(*stu4), GFP_KERNEL);
-
stu4->id = 4;
-
stu4->name = "wyb4";
-
INIT_LIST_HEAD(&stu4->list);
-
-
// add the four nodes to head
-
list_add (&stu1->list, &stu_head);
-
list_add (&stu2->list, &stu_head);
-
list_add (&stu3->list, &stu_head);
-
list_add (&stu4->list, &stu_head);
-
-
// print each student from 4 to 1
-
list_for_each_entry(stu, &stu_head, list)
-
{
-
print_student(stu);
-
}
-
// print each student from 1 to 4
-
list_for_each_entry_reverse(stu, &stu_head, list)
-
{
-
print_student(stu);
-
}
-
-
// delete a entry stu2
-
list_del(&stu2->list);
-
list_for_each_entry(stu, &stu_head, list)
-
{
-
print_student(stu);
-
}
-
-
// replace stu3 with stu2
-
list_replace(&stu3->list, &stu2->list);
-
list_for_each_entry(stu, &stu_head, list)
-
{
-
print_student(stu);
-
}
-
-
return 0;
-
}
-
-
static void testlist_exit(void)
-
{
-
printk(KERN_ALERT "*************************\n");
-
printk(KERN_ALERT "testlist is exited!\n");
-
printk(KERN_ALERT "*************************\n");
-
}
-
-
void print_student(struct student *stu)
-
{
-
printk (KERN_ALERT "======================\n");
-
printk (KERN_ALERT "id =%d\n", stu->id);
-
printk (KERN_ALERT "name=%s\n", stu->name);
-
printk (KERN_ALERT "======================\n");
-
}
-
-
module_init(testlist_init);
-
module_exit(testlist_exit)
Makefile:
-
obj-m += testlist.o
-
-
#generate the path
-
CURRENT_PATH:=$(shell pwd)
-
#the current kernel version number
-
LINUX_KERNEL:=$(shell uname -r)
-
#the absolute path
-
LINUX_KERNEL_PATH:=/usr/src/kernels/$(LINUX_KERNEL)
-
#complie object
-
all:
-
make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
-
rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c .tmp_versions *.unsigned
-
#clean
-
clean:
-
rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c *.ko .tmp_versions *.unsigned
安装,卸载内核模块以及查看内核模块的运行结果:
insmod testlist.ko
rmmod testlist
dmesg | tail -100
2. 队列
内核中的队列是以字节形式保存数据的,所以获取数据的时候,需要知道数据的大小。
如果从队列中取得数据时指定的大小不对的话,取得数据会不完整或过大。
2.1 头文件简介
内核中关于队列定义的头文件位于: include/linux/kfifo.h
头文件中定义的函数的实现位于:kernel/kfifo.c
2.2 队列代码的注意点
内核队列编程需要注意的是:
-
队列的size在初始化时,始终设定为2的n次方
-
使用队列之前将队列结构体中的锁(spinlock)释放
2.3 使用示例
构造了一个内核模块来实际使用一下内核中的队列,代码在CentOS6.3 x64上运行通过。
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;
-
// !!importent init a unlocked lock
-
spinlock_t sl = SPIN_LOCK_UNLOCKED;
-
-
// init kfifo
-
fifo = kfifo_alloc(4*sizeof(struct student), GFP_KERNEL, &sl);
-
-
stu1 = kmalloc(sizeof(struct student), GFP_KERNEL);
-
stu1->id = 1;
-
stu1->name = "wyb1";
-
kfifo_put(fifo, (char *)stu1, sizeof(struct student));
-
-
stu2 = kmalloc(sizeof(struct student), GFP_KERNEL);
-
stu2->id = 1;
-
stu2->name = "wyb2";
-
kfifo_put(fifo, (char *)stu2, sizeof(struct student));
-
-
stu3 = kmalloc(sizeof(struct student), GFP_KERNEL);
-
stu3->id = 1;
-
stu3->name = "wyb3";
-
kfifo_put(fifo, (char *)stu3, sizeof(struct student));
-
-
stu4 = kmalloc(sizeof(struct student), GFP_KERNEL);
-
stu4->id = 1;
-
stu4->name = "wyb4";
-
kfifo_put(fifo, (char *)stu4, sizeof(struct student));
-
-
c_tmp = kmalloc(sizeof(struct student), GFP_KERNEL);
-
printk(KERN_ALERT "current fifo length is : %d\n", kfifo_len(fifo));
-
for (i=0; i < 4; i++) {
-
-
kfifo_get(fifo, c_tmp, sizeof(struct student));
-
stu_tmp = (struct student *)c_tmp;
-
print_student(stu_tmp);
-
printk(KERN_ALERT "current fifo length is : %d\n", kfifo_len(fifo));
-
}
-
-
printk(KERN_ALERT "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(KERN_ALERT "=========================\n");
-
print_current_time(1);
-
printk(KERN_ALERT "id = %d\n", stu->id);
-
printk(KERN_ALERT "name = %s\n", stu->name);
-
printk(KERN_ALERT "=========================\n");
-
}
-
-
static void testkfifo_exit(void)
-
{
-
printk(KERN_ALERT "*************************\n");
-
printk(KERN_ALERT "testkfifo is exited!\n");
-
printk(KERN_ALERT "*************************\n");
-
}
-
-
module_init(testkfifo_init);
-
module_exit(testkfifo_exit);
其中引用的kn_common.h文件:
#include
#include
#include
#include
#include
#include
void print_current_time(int);
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(KERN_ALERT "%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(KERN_ALERT "\n");
kfree(tv);
kfree(t);
}
Makefile:
obj-m += fifo.o
fifo-objs := testkfifo.o kn_common.o
#generate the path
CURRENT_PATH:=$(shell pwd)
#the current kernel version number
LINUX_KERNEL:=$(shell uname -r)
#the absolute path
LINUX_KERNEL_PATH:=/usr/src/kernels/$(LINUX_KERNEL)
#complie object all: make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c .tmp_versions *.unsigned
#clean
clean: rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c *.ko .tmp_versions *.unsigned
安装,卸载内核模块以及查看内核模块的运行结果:
insmod fifo.ko
rmmod fifo
dmesg | tail -40
from:
http://www.cnblogs.com/wang_yb/archive/2013/04/16/3023892.html
阅读(1214) | 评论(0) | 转发(0) |