Chinaunix首页 | 论坛 | 博客

木驴的天空的ChinaUnix博客

首页　| 　博文目录　| 　关于我

木驴的天空

  • 博客访问： 18680
  • 博文数量： 6
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 0
  • 用 户 组： 普通用户
  • 注册时间： 2014-07-12 19:23
文章分类

全部博文（6）

文章存档

2014年（6）

我的朋友
最近访客
推荐博文
相关博文
《Linux内核设计与实现》读书笔记（六）- 内核数据结构之链表与队列

分类： LINUX

2014-09-07 16:41:17

原文地址：《Linux内核设计与实现》读书笔记（六）- 内核数据结构之链表与队列 作者：cfm5538

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

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

  15. void print_student(struct student*);

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

  25.     // init four list nodes
  26.     stu1 = kmalloc(sizeof(*stu1), GFP_KERNEL);
  27.     stu1->id = 1;
  28.     stu1->name = "wyb";
  29.     INIT_LIST_HEAD(&stu1->list);

  31.     stu2 = kmalloc(sizeof(*stu2), GFP_KERNEL);
  32.     stu2->id = 2;
  33.     stu2->name = "wyb2";
  34.     INIT_LIST_HEAD(&stu2->list);

  36.     stu3 = kmalloc(sizeof(*stu3), GFP_KERNEL);
  37.     stu3->id = 3;
  38.     stu3->name = "wyb3";
  39.     INIT_LIST_HEAD(&stu3->list);

  41.     stu4 = kmalloc(sizeof(*stu4), GFP_KERNEL);
  42.     stu4->id = 4;
  43.     stu4->name = "wyb4";
  44.     INIT_LIST_HEAD(&stu4->list);

  46.     // add the four nodes to head
  47.     list_add (&stu1->list, &stu_head);
  48.     list_add (&stu2->list, &stu_head);
  49.     list_add (&stu3->list, &stu_head);
  50.     list_add (&stu4->list, &stu_head);

  52.     // print each student from 4 to 1
  53.     list_for_each_entry(stu, &stu_head, list)
  54.     {
  55.         print_student(stu);
  56.     }
  57.     // print each student from 1 to 4
  58.     list_for_each_entry_reverse(stu, &stu_head, list)
  59.     {
  60.         print_student(stu);
  61.     }

  63.     // delete a entry stu2
  64.     list_del(&stu2->list);
  65.     list_for_each_entry(stu, &stu_head, list)
  66.     {
  67.         print_student(stu);
  68.     }

  70.     // replace stu3 with stu2
  71.     list_replace(&stu3->list, &stu2->list);
  72.     list_for_each_entry(stu, &stu_head, list)
  73.     {
  74.         print_student(stu);
  75.     }

  77.     return 0;
  78. }

  80. static void testlist_exit(void)
  81. {
  82.     printk(KERN_ALERT "*************************\n");
  83.     printk(KERN_ALERT "testlist is exited!\n");
  84.     printk(KERN_ALERT "*************************\n");
  85. }

  87. void print_student(struct student *stu)
  88. {
  89.     printk (KERN_ALERT "======================\n");
  90.     printk (KERN_ALERT "id =%d\n", stu->id);
  91.     printk (KERN_ALERT "name=%s\n", stu->name);
  92.     printk (KERN_ALERT "======================\n");
  93. }

  95. module_init(testlist_init);
  96. module_exit(testlist_exit)


Makefile：

点击(此处)折叠或打开

  1. obj-m += testlist.o

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

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

  10. static void print_student(struct student*);

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

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

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

  35.     stu3 = kmalloc(sizeof(struct student), GFP_KERNEL);
  36.     stu3->id = 1;
  37.     stu3->name = "wyb3";
  38.     kfifo_put(fifo, (char *)stu3, sizeof(struct student));

  40.     stu4 = kmalloc(sizeof(struct student), GFP_KERNEL);
  41.     stu4->id = 1;
  42.     stu4->name = "wyb4";
  43.     kfifo_put(fifo, (char *)stu4, sizeof(struct student));

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

  49.         kfifo_get(fifo, c_tmp, sizeof(struct student));
  50.         stu_tmp = (struct student *)c_tmp;
  51.         print_student(stu_tmp);
  52.         printk(KERN_ALERT "current fifo length is : %d\n", kfifo_len(fifo));
  53.     }
  54.     
  55.     printk(KERN_ALERT "current fifo length is : %d\n", kfifo_len(fifo));
  56.     kfifo_free(fifo);
  57.     kfree(c_tmp);
  58.     return 0;
  59. }

  61. static void print_student(struct student *stu)
  62. {
  63.     printk(KERN_ALERT "=========================\n");
  64.     print_current_time(1);
  65.     printk(KERN_ALERT "id = %d\n", stu->id);
  66.     printk(KERN_ALERT "name = %s\n", stu->name);
  67.     printk(KERN_ALERT "=========================\n");
  68. }

  70. static void testkfifo_exit(void)
  71. {
  72.     printk(KERN_ALERT "*************************\n");
  73.     printk(KERN_ALERT "testkfifo is exited!\n");
  74.     printk(KERN_ALERT "*************************\n");
  75. }

  77. module_init(testkfifo_init);
  78. 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
阅读(1495) | 评论(0) | 转发(0) |
0

上一篇：git版本仓库命令学习快速入门！

下一篇：Vim入门必知必会

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6