文档章节

开篇之3:内核中list_head的理解

我叫半桶水
 我叫半桶水
发布于 07/14 10:16
字数 1959
阅读 38
收藏 0

date: 2014-08-30 19:09

1 需求分析

我们在《数据结构》课程上,学习过双向链表。现在假定有下列需求。

需求1:设计一个结构体,结构体本身支持双向链表,你的实现可能会是:

//方案1
struct myStruct
{
    int myValue;
    struct myStruct *prev;
    struct myStruct *next;
};

void OperateOnMyStruct(struct myStruct *);

没错,这可以很好的工作。这种链表,节点的“前驱”与“后继”是同一个类型,因此可以在节点的“前驱”与“后继”上执行结构体支持的操作,比如将前期和后继传给OperateOnMyStruct函数。

需求2:设计1000个不同的结构体,要求这些结构体支持双向链表。

呃,方案1的方法显得冗余,需要为每个结构体定义前驱和后继节点,多少重复代码呀,但还是忍了吧。

需求3:设计1000个不同的结构体,要求这些结构体支持双向链表,并且,结构体对象可以同时在多个队列中。比如结构体structA的对象objA,可以同时在链表A、B、C中,用图来描述,大概是这个样子:

同时在多个链表中的需求

此时,方案1的方法只怕是力不从心了。

2 内核的实现

抬头审视一下,方案1的缺陷在哪里?似乎没问题呀,用设计模式的思想来审视下呢?呃,违反了“开放封闭”原则。

该怎么优化这个方案呢?用面向对象的思维来思考下:呃,“链表”的需求,是所有结构体的共同需求,实现一个最基本的类,来处理链表的操作,然后其他的结构体继承自该类。 慢着,这样还是无法处理同一个对象在多个队列中的需求呀。设计模式不是告诉我们“多用组合,少用继承”吗?

对呀,我们可以实现一个处理链表的类,这个链表类再组合到其他的结构体中。相当于链表类“寄生”到其他的结构体中,其他的结构体就是“宿主”。链表类就像一个“粘钩”,一方面通过自身的prev和next指针,构成一个链表,这部分是粘钩的钩子,另一方,通过寄生在其他的结构体中,就像粘钩带粘性的那一端,将结构体粘住。这样作为宿主的结构体也在链表中了,示意图如下。有了“粘钩”,一个对象想粘在几个链表上都可以。

粘钩

内核就是这么干的,“链表类”的名字叫list_head,定义如下:

<include/linux/types.h>
185 struct list_head {
186         struct list_head *next, *prev;
187 };

结构体里面只是定义了双向链表的指针,因为内核是用C写的,所以“链表类”中的操作只能定义在结构体之外了,具体定义在中。关于链表的操作,没必要做过多的解释。但是到目前为止,我们还有一问题没解决:在方案1中,前驱或者后继节点本身就是目标结构体类型的指针,因此可以在它们身上执行结构体支持的操作;但在新的方案中,链表的节点类型为listhead指针,如何通过该listhead指针找到目标结构体即宿主结构体的指针呢?

这个问题可以等效为:已知一个结构体的定义,以及结构体中某个成员的地址,如何确定该成员所在的结构体对象的地址?比如如下结构体定义:

struct myStruct {
    int index;
    char names[NAME_LEN];
    int key;
};

struct myStruct structSample;

则在内存中的布局如下:

结构体成员偏移

已知成员变量key所在的地址,如何确定整个结构体的基址?更进一步,已知int*指针pkey指向结构体成员key,如何得到结构体的指针?从内存布局中我们可以看到,如果能够知道key相对结构体的偏移,那么拿key的地址减去偏移就可以了。所以问题转换为如何求得偏移。

key的偏移是个固定值,用成员的地址减去结构体的地址即可得到,假定结构体所在的地址为baseAddr则:

key的偏移 = &((struct myStruct *)baseAddr)->key - baseAddr

偏移量跟结构体所在的具体地址没有关系,那么如果假设结构体所在的地址为0呢?则有:

key的偏移 = &((struct myStruct *)0)->key – 0 = &((struct myStruct *)0)-> key

注意这里的技巧,这里将0强转成struct myStruct类型的指针,然后再通过操作符”->”引用结构体的成员。有人可能要担心0地址了,没关系,0地址虽然是非法地址,但我们又不去读写它,没有问题的。这里的地址强转以及结构体成员引用在编译期间的行为。

偏移确定以后,结构体所在的地址就可以得到了:

baseAddr = key的地址 - &((struct myStruct *)0)-> key

知道地址后,我们得到结构体指针:

myStruct  *pStru = (myStruct *) (pKey - &((struct myStruct *)0)-> key )

一切似乎很顺利,但我们忽略了一个问题。指针的加减操作跟指针的类型相关,比如,如果是指向int型的指针,指针每次加1,其实际的地址加4,而如果是指向char型的指针,指针每次加1,其实际地址加1。而我们这里的偏移是以字节为单位的,所以我们要保证这里的计算也是以字节为单位,很简单,将key强转成char *即可,于是:

myStruct  *pStru = (myStruct *) ((char*)pKey - &((struct myStruct *)0)-> key )

可见,我们只要知道结构体类型以及成员名,就可以根据成员的指针推导出结构体的指针。

内核中实现此功能的宏为list_entry,其定义仍然在中:

<include/linux/list.h >
/**
345  * list_entry - get the struct for this entry
346  * @ptr:        the &struct list_head pointer.
347  * @type:       the type of the struct this is embedded in.
348  * @member:     the name of the list_struct within the struct.
349  */
350 #define list_entry(ptr, type, member) \
351         container_of(ptr, type, member) 

<include/linux/kernel.h >
825 /**
826  * container_of - cast a member of a structure out to the containing structure
827  * @ptr:        the pointer to the member.
828  * @type:       the type of the container struct this is embedded in.
829  * @member:     the name of the member within the struct.
830  *
831  */
832 #define container_of(ptr, type, member) ({                      \
833         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
834         (type *)( (char *)__mptr - offsetof(type,member) );})  

<include/linux/stddef.h >
15 #undef offsetof
16 #ifdef __compiler_offsetof
17 #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
18 #else
19 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
20 #endif
21 #endif

listentry宏有三个参数:listhead的地址,寄主结构体的类型,寄主结构中list_head成员的名字。宏展开后如下:

list_entry(ptr, type, member)
/*
 *({ })返回块中最后一个表达式的值
 */
({
    /*
     *typeof为gcc的保留字,这里定义一个指针变量__mptr,指针指向member所属类型,
     *并将成员的地址赋给它。
     */
    const typeof( ((type *)0)->member ) *__mptr = (ptr); 
    /*
     *根据成员变量的地址以及成员变量相对结构体基址的偏移得到结构体所在的地址,
     *得到地址后,将地址强转成结构体类型的指针
     */
    (type *)( (char *)__mptr - ((size_t) &((type *)0)->member) );
})

内核中将list_head作为一个通用的“基础设施”,当需要用到链表的特性时,就用这个基础设施来“搭建”代码。类似的,红黑树也被实现为一个通用的基础设施,具体的实现在lib目录下的btree.c文件中, lib目录下还有队列fifo以及位图bitmap的实现。

© 著作权归作者所有

共有 人打赏支持
我叫半桶水
粉丝 0
博文 26
码字总数 71642
作品 0
西安
私信 提问
从著名的list_head看linux内核中OO

如果有人问我最欣赏linux的什么,我会毫不犹豫地回答:list_head。这个小小的结构向世人说明了用c语言写成的linux内核也在实现着OO,下面我就具体来说一下下。先看list_head struct list_hea...

晨曦之光
2012/04/10
448
0
深入分析 Linux 内核链表

一、 链表数据结构简介 链表是一种常用的组织有序数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,是线性表的一种重要实现方式。相对于数组,链 表具有更好的动态性,建立链表...

nothingfinal
2012/02/01
0
0
《Linux内核修炼之道》精华分享与讨论(14)——内核中的链表

推荐博文: Linux内核“问题门”——学习问题、经验集锦 推荐下载:《Linux内核修炼之道》精华版之方法论 早上上班坐地铁要排队,到了公司楼下等电梯要排队,中午吃饭要排队,下班了追求一个...

任桥伟
2010/04/20
0
0
多级指针和链表

如果看到一个声明:type **********************ptr;你会怎么想?估计一半人都疯了,如此声明一个变量的人本身要么是一个高手,要么是一个低能。这样的一排*事实上表示的是一个链表,链表上的...

晨曦之光
2012/04/10
214
0
从free到page cache

Free 我们经常用free查看服务器的内存使用情况,而free中的输出却有些让人困惑,如下: 图1-1 先看看各个数字的意义以及如何计算得到: free命令输出的第二行(Mem):这行分别显示了物理内存的...

长平狐
2012/09/03
769
0

没有更多内容

加载失败,请刷新页面

加载更多

VMware前路难测,多个厂家群雄逐鹿

在人们高谈Salesforce、亚马逊等新兴云计算厂商取得的成就时,以VMware、HPE和Cisco为代表的老牌厂商也在进行着自己的转型和变化,而且还取得一定的进展。以VMware为例,虚拟机巨头公布了第二...

linux-tao
9分钟前
0
0
Palindrome Linked List(leetcode234)

Given a singly linked list, determine if it is a palindrome. Example 1: Input: 1->2Output: false Example 2: Input: 1->2->2->1Output: true Follow up: Could you do it in O(n) ......

woshixin
11分钟前
0
0
【宇润日常疯测-003】PHP 序列化和 JSON 哪个更好?

有了 Swoole 以后,用我们熟悉的 PHP 就可以很方便地开发网络通信应用。有时候我们系统内部需要交换数据,那么,这时候问题来了,网络通讯的数据格式是选择 JSON 还是 serialize 呢? 一通分...

宇润
12分钟前
1
0
mybatis批量操作sql配置

在写批量sql操作时,遇到执行报错: <foreach collection="list" item="item" index="index" separator=";"> update t_xxx set column1=#{item.column1} where id= #{item.id} </foreach> 分......

lar555
24分钟前
2
0
L2TP VPN客户端配置

打开网络设置-->选择VPN-->添加VPN链接 配置完毕,打开更改适配器选项 右键-->属性 选中安全---允许使用安全协议,确定保存后连接vpn即可

阿伦哥-
28分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部