Linux内核链表
内核链表的设计思路
内核链表中自己实现了一个纯链表(纯链表就是没有数据区域,只有前后向指针)的封装,以及纯链表的各种操作函数(节点创建、插入、删除、遍历······)。这个纯链表本身自己没有任何用处,它的用法是给我们具体链表作为核心来调用。
list.h文件简介
(1)内核中核心纯链表的实现在include/linux/list.h文件中
(2)list.h中就是一个纯链表的完整封装,包含节点定义和各种链表操作方法。
源代码解析
/*
* Simple doubly linked list implementation.
*
* Some of the internal functions ("__xxx") are useful when
* manipulating whole lists rather than single entries, as
* sometimes we already know the next/prev entries and we can
* generate better code by using them directly rather than
* using the generic single-entry routines.
*/ struct list_head {
struct list_head *next, *prev;
}; #define LIST_HEAD_INIT(name) { &(name), &(name) }//初始化链表节点name,将前指针和后指针都指向自己 #define LIST_HEAD(name) \ //定义的同时初始化
struct list_head name = LIST_HEAD_INIT(name) static inline void INIT_LIST_HEAD(struct list_head *list) //链表头节点初始化函数
{
list->next = list;
list->prev = list;
}
struct list_head {
struct list_head *next, *prev;
};
此结构体所构成的链表为双向循环链表
此结构体在linux内核中被大量的引用,几乎所有内核当中需要构成链表结构的地方都用到了这个结构体。例如内核的总线设备就用到了这个结构体
#define LIST_HEAD_INIT(name) { &(name), &(name) }//初始化链表节点name,将前指针和后指针都指向自己
#define LIST_HEAD(name) \ //定义的同时初始化
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list) //链表头节点初始化函数
{
list->next = list;
list->prev = list;
}
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
#ifndef CONFIG_DEBUG_LIST
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
#else
extern void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next);
#endif /**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
} /**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
示例
#include <linux/list.h> struct driver_info
{
int data;
}; // driver结构体用来管理内核中的驱动
struct driver
{
char name[]; // 驱动名称
int id; // 驱动id编号
struct driver_info info; // 驱动信息
struct list_head head; // 内嵌的内核链表成员
}; struct driver2
{
char name[]; // 驱动名称
int id; // 驱动id编号
struct driver_info info; // 驱动信息
//struct list_head head; // 内嵌的内核链表成员
struct driver *prev;
struct driver *next;
}; // 分析driver结构体,可知:前三个成员都是数据区域成员(就是我们之前简化为int data的东西),第4个成员是一个struct list_head类型的变量,这就是一个纯链表。
// 本来driver结构体是没有链表的,也无法用链表来管理。但是我们driver内嵌的head成员本身就是一个纯链表,所以driver通过head成员给自己扩展了链表的功能。
// driver通过内嵌的方式扩展链表成员,本身不只是有了一个链表成员,关键是可以通过利用list_head本身事先实现的链表的各种操作方法来操作head。 // 最终效果:我们可以通过遍历head来实现driver的遍历;遍历head的函数在list.h中已经事先写好了,所以我们内核中去遍历driver时就不用重复去写了。
// 通过操作head来操作driver,实质上就是通过操作结构体的某个成员变量来操作整个结构体变量。这里面要借助container_of宏
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
关于container_of
#ifndef offsetof
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif #ifndef container_of
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof(((type *))->member) * __mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
#endif
1、#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE*)0)->MEMBER)
1.1 功能:
返回结构体TYPE中MEMBER成员相对于结构体首地址的偏移量,以字节为单位。
1.2 解析:
此类复杂表达式的解析应该采用从内向外、逐层理解的方式。
首先,(TYPE *)0表示将数字0强制类型转换为TYPE类型(TYPE为结构体类型)的指针。因此这里的0代表内存地址0,即我们认为内存地址0开始的sizeof(TYPE)个字节内存储的是一个TYPE类型的变量。
然后,((TYPE *)0)->MEMBER 得到该结构体变量中的MEMBER成员变量,
而 &(((TYPE*)0)->MEMBER) 使用取地址符&取得了MEMBER成员变量的地址,(size_t)加在前面表示将MEMBER成员变量的地址强制类型转换为size_t(即unsigned int),并将结果作为宏的返回值。
可见,offsetof宏返回的是MEMBER成员在内存中的实际地址。又因为整个结构体的起始地址是0,因此MEMBER成员的实际地址在数值上就等于MEMBER成员相对于结构体首地址的偏移量。
1.3 扩展思考:
1.3.1 使用offsetof宏会影响内存0地址处的值吗?
答案是不会,从1.3.2可知offsetof宏的运算是在C编译器编译时完成的,因此内存的0地址在机器指令中根本未被操作,当然不会影响其值了。
1.3.2offsetof宏返回的MEMBER相对于结构体首地址的偏移量是如何得到的?->符号如何能正确寻址到结构体中某个成员变量?
container_of宏分为两部分,
第一部分:const typeof( ((type *)0)->member ) *__mptr = (ptr);
通过typeof定义一个member指针类型的指针变量__mptr,(即__mptr是指向member类型的指针),并将__mptr赋值为ptr。
第二部分: (type *)( (char *)__mptr - offsetof(type,member) ),通过offsetof宏计算出member在type中的偏移,然后用member的实际地址__mptr减去偏移,得到type的起始地址,即指向type类型的指针。
1. 将地址0强转成type *指针,取到成员member指针,然后再使用typeof来获取到member的类型,将结构体中变量ptr的指针保存到__mptr.
2. 使用offsetof宏获取到member变量相对于结构体type的偏移量,这样将__mptr的值减去偏移量即是结构体的地址,然后再强转即得到结构体指针。
从上面我们可以看到,不使用__mptr来保存ptr指针,直接用ptr指针来减偏移量不也可以达到目的么?
答案是使用_mptr的目的是在编译期间进行类型检测(第一句,赋值时如果类型不匹配会报告警),保证传入的成员地址与成员类型是匹配的,而在运行期间则和忽略中间变量__mptr是一样的。
话说有个结构体a, 地址表示为 &a, 这个结构体里面有个成员叫b
地址表示为 &b, 现在请问 “ &b - &a ” 表示什么含义?
答案:偏移量,成员变量的首地址相对于结构体首地址的偏移量。如果 &a 碰巧又等于0 ,那么 &b - &a = &b - 0 = &b 这样话,上面的答案就变成了:成员变量的首地址,就是偏移量这个说的就是 offsetof的作用
现在我们有了偏移量,再拿到成员变量的实际地址,减去上面说的偏移量,不就是当前结构体的首地址了吗!
(char *)__mptr中的char *不可瞎改,这里将__mptr强制类型转换为char *指针,意在指针加减时保证地址偏移量为1
未完待续......
最新文章
- [LeetCode] Kth Largest Element in an Array 数组中第k大的数字
- [ES] 安装
- jvm的垃圾回收原理
- repeater重复器、地址栏传值、response
- linux(ubuntu)安装时遇到的问题
- 【原创】Silverlight客户端发起WebRequest请求分析
- Python入门笔记(8):列表
- Akka.NET
- MyBatis框架
- NSMutableString
- Hadoop上路-02_Hadoop FS Shell
- python手记(50)
- 解决 IntelliJ 乱码问题
- C语言结构体(struct)使用方法
- How Many Equations Can You Find(dfs)
- HA机制下的Hadoop配置
- C. 新年的繁荣
- Make Eudict for reviewing example sentences
- GsonUtil工具类
- 让一个继承unittest.TestCase的类下的setUp和tearDown只执行一次