Chinaunix首页 | 论坛 | 博客
  • 博客访问: 678358
  • 博文数量: 77
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1173
  • 用 户 组: 普通用户
  • 注册时间: 2014-05-16 11:20
个人简介

将技术做到极致...

文章分类

全部博文(77)

文章存档

2019年(3)

2015年(27)

2014年(47)

分类: LINUX

2014-09-04 13:43:13

内核数据结构贯穿于整个内核代码中,这里介绍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)

具体见下图:

list1

 

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

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

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

 

具体见下图:

list2

 

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地址的差,如下图所示:

step3

 

1.3 使用示例

构造了一个内核模块来实际使用一下内核中的链表,代码在CentOS6.3 x64上运行通过。

C代码:

点击(此处)折叠或打开

  1. #include<linux/init.h>
  2. #include<linux/slab.h>
  3. #include<linux/module.h>
  4. #include<linux/kernel.h>
  5. #include<linux/list.h>

  6. MODULE_LICENSE("Dual BSD/GPL");
  7. struct student
  8. {
  9.     int id;
  10.     char* name;
  11.     struct list_head list;
  12. };

  13. void print_student(struct student*);

  14. static int testlist_init(void)
  15. {
  16.     struct student *stu1, *stu2, *stu3, *stu4;
  17.     struct student *stu;
  18.     
  19.     // init a list head
  20.     LIST_HEAD(stu_head);

  21.     // init four list nodes
  22.     stu1 = kmalloc(sizeof(*stu1), GFP_KERNEL);
  23.     stu1->id = 1;
  24.     stu1->name = "wyb";
  25.     INIT_LIST_HEAD(&stu1->list);

  26.     stu2 = kmalloc(sizeof(*stu2), GFP_KERNEL);
  27.     stu2->id = 2;
  28.     stu2->name = "wyb2";
  29.     INIT_LIST_HEAD(&stu2->list);

  30.     stu3 = kmalloc(sizeof(*stu3), GFP_KERNEL);
  31.     stu3->id = 3;
  32.     stu3->name = "wyb3";
  33.     INIT_LIST_HEAD(&stu3->list);

  34.     stu4 = kmalloc(sizeof(*stu4), GFP_KERNEL);
  35.     stu4->id = 4;
  36.     stu4->name = "wyb4";
  37.     INIT_LIST_HEAD(&stu4->list);

  38.     // add the four nodes to head
  39.     list_add (&stu1->list, &stu_head);
  40.     list_add (&stu2->list, &stu_head);
  41.     list_add (&stu3->list, &stu_head);
  42.     list_add (&stu4->list, &stu_head);

  43.     // print each student from 4 to 1
  44.     list_for_each_entry(stu, &stu_head, list)
  45.     {
  46.         print_student(stu);
  47.     }
  48.     // print each student from 1 to 4
  49.     list_for_each_entry_reverse(stu, &stu_head, list)
  50.     {
  51.         print_student(stu);
  52.     }

  53.     // delete a entry stu2
  54.     list_del(&stu2->list);
  55.     list_for_each_entry(stu, &stu_head, list)
  56.     {
  57.         print_student(stu);
  58.     }

  59.     // replace stu3 with stu2
  60.     list_replace(&stu3->list, &stu2->list);
  61.     list_for_each_entry(stu, &stu_head, list)
  62.     {
  63.         print_student(stu);
  64.     }

  65.     return 0;
  66. }

  67. static void testlist_exit(void)
  68. {
  69.     printk(KERN_ALERT "*************************\n");
  70.     printk(KERN_ALERT "testlist is exited!\n");
  71.     printk(KERN_ALERT "*************************\n");
  72. }

  73. void print_student(struct student *stu)
  74. {
  75.     printk (KERN_ALERT "======================\n");
  76.     printk (KERN_ALERT "id =%d\n", stu->id);
  77.     printk (KERN_ALERT "name=%s\n", stu->name);
  78.     printk (KERN_ALERT "======================\n");
  79. }

  80. module_init(testlist_init);
  81. module_exit(testlist_exit)


Makefile:

点击(此处)折叠或打开

  1. obj-m += testlist.o

  2. #generate the path
  3. CURRENT_PATH:=$(shell pwd)
  4. #the current kernel version number
  5. LINUX_KERNEL:=$(shell uname -r)
  6. #the absolute path
  7. LINUX_KERNEL_PATH:=/usr/src/kernels/$(LINUX_KERNEL)
  8. #complie object
  9. all:
  10.     make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
  11.     rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c .tmp_versions *.unsigned
  12. #clean
  13. clean:
  14.     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代码:

点击(此处)折叠或打开

  1. #include "kn_common.h"

  2. MODULE_LICENSE("Dual BSD/GPL");
  3. struct student
  4. {
  5.     int id;
  6.     char* name;
  7. };

  8. static void print_student(struct student*);

  9. static int testkfifo_init(void)
  10. {
  11.     struct kfifo *fifo;
  12.     struct student *stu1, *stu2, *stu3, *stu4;
  13.     struct student *stu_tmp;
  14.     char* c_tmp;
  15.     int i;
  16.     // !!importent init a unlocked lock
  17.     spinlock_t sl = SPIN_LOCK_UNLOCKED;

  18.     // init kfifo
  19.     fifo = kfifo_alloc(4*sizeof(struct student), GFP_KERNEL, &sl);
  20.     
  21.     stu1 = kmalloc(sizeof(struct student), GFP_KERNEL);
  22.     stu1->id = 1;
  23.     stu1->name = "wyb1";
  24.     kfifo_put(fifo, (char *)stu1, sizeof(struct student));

  25.     stu2 = kmalloc(sizeof(struct student), GFP_KERNEL);
  26.     stu2->id = 1;
  27.     stu2->name = "wyb2";
  28.     kfifo_put(fifo, (char *)stu2, sizeof(struct student));

  29.     stu3 = kmalloc(sizeof(struct student), GFP_KERNEL);
  30.     stu3->id = 1;
  31.     stu3->name = "wyb3";
  32.     kfifo_put(fifo, (char *)stu3, sizeof(struct student));

  33.     stu4 = kmalloc(sizeof(struct student), GFP_KERNEL);
  34.     stu4->id = 1;
  35.     stu4->name = "wyb4";
  36.     kfifo_put(fifo, (char *)stu4, sizeof(struct student));

  37.     c_tmp = kmalloc(sizeof(struct student), GFP_KERNEL);
  38.     printk(KERN_ALERT "current fifo length is : %d\n", kfifo_len(fifo));
  39.     for (i=0; i < 4; i++) {

  40.         kfifo_get(fifo, c_tmp, sizeof(struct student));
  41.         stu_tmp = (struct student *)c_tmp;
  42.         print_student(stu_tmp);
  43.         printk(KERN_ALERT "current fifo length is : %d\n", kfifo_len(fifo));
  44.     }
  45.     
  46.     printk(KERN_ALERT "current fifo length is : %d\n", kfifo_len(fifo));
  47.     kfifo_free(fifo);
  48.     kfree(c_tmp);
  49.     return 0;
  50. }

  51. static void print_student(struct student *stu)
  52. {
  53.     printk(KERN_ALERT "=========================\n");
  54.     print_current_time(1);
  55.     printk(KERN_ALERT "id = %d\n", stu->id);
  56.     printk(KERN_ALERT "name = %s\n", stu->name);
  57.     printk(KERN_ALERT "=========================\n");
  58. }

  59. static void testkfifo_exit(void)
  60. {
  61.     printk(KERN_ALERT "*************************\n");
  62.     printk(KERN_ALERT "testkfifo is exited!\n");
  63.     printk(KERN_ALERT "*************************\n");
  64. }

  65. module_init(testkfifo_init);
  66. 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
阅读(5534) | 评论(1) | 转发(3) |
给主人留下些什么吧!~~

vv11332014-10-05 22:16:52

楼主的图是用什么工具画的?