Linux系统中,进程之间有一个强烈的持续关系,所有进度都是 PID 为1的
init 进度的遗族。内核在系统启动的尾声阶段启动 init
进度。该进程读取系统的初叶化脚本(initscript)并履行别的的有关程序,最终成就系统启动的全方位进程。

Linux 内核list_head 学习(一)

【澳门金沙国际】Linux内核学习笔记,Linux内核之数据双链表。关于container_of的用法,可参考
http://www.linuxidc.com/Linux/2012-02/53700.htm 。其实就是不留余地了”怎么着通过结构中的某个变量的地点获取结构本身的指针“那样的题材。container_of完毕了根据一个结构体变量中的一个分子变量的指针来收获指向任何结构体变量的指针的功能。

导读 Linux 内核中自己实现了双向链表,可以在 include/linux/list.h 找到定义。我们将会首先从双向链表数据结构开始介绍内核里的数据结构。为什么?因为它在内核里使用的很广泛,你只需要在 free-electrons.com 检索一下就知道了。

  系统中每个进度必有一个父进度,相应的,每个进程也可以由零个或者多个子进度。拥有同一个父进度的富有进程被称为兄弟。进度之间的关系存放在进度描述符
task_struct 中。每个 task_struct 都饱含一个针对其父进度 task_struct
的指针 parent,还有一个被叫做 children 的子进度链表。

首先container_of出现在linux/kernel.h中。定义如下:

澳门金沙国际 1

 

在Linux内核中,提供了一个用来创制双向循环链表的构造 list_head。即便linux内核是用C语言写的,但是list_head的引入,使得内核数据结构也得以有所面向对象的风味,通过利用操作list_head 的通用接口很简单已毕代码的录用,有点类似于C++的后续机制(希望有空子写篇小说商讨一下C语言的面向对象机制)。上边就是kernel中的list_head结构定义:

[cpp]

首先让大家看一下在 include/linux/types.h 里的主结构体:

一、父进程的拜会方法

struct list_head {

  1. /** 
  2.  * container_of – cast a member of a structure out to the containing structure 
  3.  * @ptr:    the pointer to the member. 
  4.  * @type:   the type of the container struct this is embedded in. 
  5.  * @member: the name of the member within the struct. 
  6.  * 
  7.  */  
  8. #define container_of(ptr, type, member) ({          \
      
  9.     const typeof( ((type *)0)->member ) *__mptr = (ptr); \  
  10.     (type *)( (char *)__mptr – offsetof(type,member) );}) 
struct list_head { 
       struct list_head *next, *prev;
};

  对于眼前经过,可以利用上边代码访问其父进度,得到其经过描述符:

  struct list_head *next, *prev;

typeof( ((type *)0)->member )
*__mptr 就是声称了一个针对其
大家在看一下offset的概念,在linux/stddef.h中。定义如下:

您也许注意到那和你在此以前见过的双向链表的兑现形式是见仁见智的。

struct task_struct *my_parent = current -> parent;

};

[cpp]

举个例证来说,在 glib 库里是那样完成的:

   其中,current 是一个宏,在
linux/asm-generic/current.h中有定义:

#define
LIST_HEAD_INIT(name) { &(name), &(name) }

  1. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
struct GList {
gpointer data;
GList *next;
GList *prev;
};
/* SPDX-License-Identifier: GPL-2.0 */
#ifndef __ASM_GENERIC_CURRENT_H
#define __ASM_GENERIC_CURRENT_H

#include <linux/thread_info.h>

#define get_current() (current_thread_info()->task)
#define current get_current()

#endif /* __ASM_GENERIC_CURRENT_H */

内需小心的一些是,头结点head是不行使的,这一点要求专注。

offset顾名思义就是得到该成员变量基于其包涵体地址的偏移量。先分析一下以此宏:

平日来说一个链表结构会包罗一个针对某个项目标指针。

  而 current_thread_info() 函数在
arch/arm/include/asm/thread_info.h 中有定义:

使用list_head社团的链表的协会如下图所示:

  1. ( (TYPE *)0 ) 将零转型为TYPE类型指针; 
  2. ((TYPE *)0)->MEMBER 访问结构中的数据成员; 
  3. &( ( (TYPE *)0 )->MEMBER )取出数据成员的地址; 
    4.(size_t)(&(((TYPE*)0)->MEMBER))结果转换类型。

而是 Linux
内核中的链表已毕并没有这么做。所以难点来了:链表在哪个地方保存数据吧?实际上,内核里心想事成的链表是侵入式链表(Intrusive
list)。侵入式链表并不在节点内保留数据-它的节点仅仅包括指向前后节点的指针,以及指向链表节点数据部分的指针——数据就是这么附加在链表上的。那就使得那个数据结构是通用的,使用起来就不须要考虑节点数据的类型了。

/*
 * how to get the thread information struct from C
 */
static inline struct thread_info *current_thread_info(void) __attribute_const__;

static inline struct thread_info *current_thread_info(void)
{
    return (struct thread_info *)
        (current_stack_pointer & ~(THREAD_SIZE - 1));        // 让SP堆栈指针与栈底对齐    
}    

   

有人也许感觉很不适于(TYPE
*)0那种用法,把一个0转换成一个结构体指针是怎么着意思啊?其实就是声称了一个针对无物的指针,并告诉编译器那些指针式指向TYPE类型的,然后成员地址自然为偏移地址,因为成员地址-0依旧成员地址。

比如:

   可以见到,current 实际上是指向当前履行进度的 task_struct 指针的。

澳门金沙国际 2

最后把__mptr
强制类型转换为char*品类,有限协理指针相减时是以一个字节为单位展开相减的,保险了程序的不错。

struct nmi_desc {
spinlock_t lock;
struct list_head head;
};

 

list_head这些布局看起来怪怪的,它竟没有数据域!所以见到那些协会的人率先感应就是大家怎么访问数据?

诸如此类大家就能够使用container_of来根据一个成员变量的指针来博取指向任何结构体变量的指针,对于应用层程序而言,那种体制完全没有要求,不过对于设备驱动程序而言,运用container_of就很有要求了。

让我们看多少个例子来驾驭一下在基础里是什么样选用 list_head 的。

二、子进度的拜访方法

其实list_head不是拿来单独用的,它一般被嵌到任何协会中,如:

澳门金沙国际 3

看来,在根本里有许多广大不等的地方都用到了链表。大家来看一个在杂项字符驱动里面的应用的事例。在
drivers/char/misc.c 的杂项字符驱动 API
被用来编排处理小型硬件或编造设备的小驱动。那些使得共享相同的主设备号:

  可以选择以下方式访问子进度:

struct file_node{

#define MISC_MAJOR 10
struct task_struct *task;
struct list_head *list;

list_for_each(list,&current->children){
    task = list_entry(list,struct task_struct,sibling);      
}

  char c;

而是都有各自分裂的次设备号。

  可以看出,那里运用的是链表相关的操作来访问子进度。大家清楚,
task_struct 是存放在在一个双向循环链表 task_list(职责队列)中的,而一个
task_struct 包罗了一个实际经过的保有新闻,因而,大家只需求找到子进程的
task_struct
即可以访问子进度了,上边代码就是如此做的。那么,具体是怎么着找到子进度的经过描述符
task_struct的吧?上面对上边的代码进行详细分析:

  struct list_head node;

比如:

  list_head: 在 linux/types.h
中定义

};

ls -l /dev | grep 10
crw------- 1 root root 10, 235 Mar 21 12:01 autofs
drwxr-xr-x 10 root root 200 Mar 21 12:01 cpu
crw------- 1 root root 10, 62 Mar 21 12:01 cpu_dma_latency
crw------- 1 root root 10, 203 Mar 21 12:01 cuse
drwxr-xr-x 2 root root 100 Mar 21 12:01 dri
crw-rw-rw- 1 root root 10, 229 Mar 21 12:01 fuse
crw------- 1 root root 10, 228 Mar 21 12:01 hpet
crw------- 1 root root 10, 183 Mar 21 12:01 hwrng
crw-rw----+ 1 root kvm 10, 232 Mar 21 12:01 kvm
crw-rw---- 1 root disk 10, 237 Mar 21 12:01 loop-control
crw------- 1 root root 10, 227 Mar 21 12:01 mcelog
crw------- 1 root root 10, 59 Mar 21 12:01 memory_bandwidth
crw------- 1 root root 10, 61 Mar 21 12:01 network_latency
crw------- 1 root root 10, 60 Mar 21 12:01 network_throughput
crw-r----- 1 root kmem 10, 144 Mar 21 12:01 nvram
brw-rw---- 1 root disk 1, 10 Mar 21 12:01 ram10
crw--w---- 1 root tty 4, 10 Mar 21 12:01 tty10
crw-rw---- 1 root dialout 4, 74 Mar 21 12:01 ttyS10
crw------- 1 root root 10, 63 Mar 21 12:01 vga_arbiter
crw------- 1 root root 10, 137 Mar 21 12:01 vhci
struct list_head{
    struct list_head *next,*prev;  
};

此时list_head就当作它的父结构中的一个成员了,当大家了然list_head的地方(指针)时,我们可以透过list.c提供的宏 list_entry 来赢得它的父结构的地方。上面大家来探视list_entry的实现:

现在让大家看看它是怎么使用链表的。首先看一下协会体 miscdevice:

  显然,list_head
其实就是一个双向链表,而且一般的话,都是双向循环链表。

#define
list_entry(ptr,type,member)\

struct miscdevice
{
int minor;
const char *name;
const struct file_operations *fops;
struct list_head list;
struct device *parent;
struct device *this_device;
const char *nodename;
mode_t mode;
};

 

  container_of(ptr,type,member)

可以见见结构体miscdevice的第几个变量list 是有着注册过的配备的链表。

  list_for_each:
在linux/list.h 中定义

   

在源代码文件的早先可以看到那些链表的定义:

#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

#define
offsetof(TYPE,MEMBER) ((size_t)&((TYPE *)0)->MEMBER)

static LIST_HEAD(misc_list);

  那是一个宏定义。其中,pos 是指向 list_head 的指针,而 head 是双链表
list_head
中的指针,定义了从哪个地方初始遍历那个链表。这一个宏的出力就是对一个双向循环链表进行遍历。

#define
container_of(ptr,type,member) ( {\

它实质上是对用list_head 类型定义的变量的扩展。

 

  const typeof( ((type*)0)->member )
*__mptr=(ptr);\

#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)

  list_entry: 在 linux/list.h
中定义,也是一个宏定义

  (type*)( (char*)__mptr –
offsetof(type,member) );} )

下一场利用宏 LIST_HEAD_INIT 举办开头化,

/**
 * 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_head within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

   

那会使用变量name 的地址来填充prev和next 结构体的多少个变量。

  list_entry 实际上就是 container_of。

那里涉及到多个宏,依旧有点复杂的,我们一个一个来看:

#define LIST_HEAD_INIT(name) { &(name), &(name) }

 

#define offsetof(TYPE,MEMBER) (
(size_t)& ((TYPE *)0)-> MEMBER )

现今来看看注册杂项设备的函数misc_register。

  container_of : 在 linux/kernel.h
中定义

俺们清楚 0 地址内容是无法访问的,但 0地址的地方大家还能访问的,这里用到一个取址运算符

它在一起来就用函数 INIT_LIST_HEAD 初叶化了miscdevice->list。

/**
 * 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) ({                \
    void *__mptr = (void *)(ptr);                    \
    BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&    \
             !__same_type(*(ptr), void),            \
             "pointer type mismatch in container_of()");    \
    ((type *)(__mptr - offsetof(type, member))); })

(TYPE
*)0 它代表将 0地址强制转换为TYPE类型,((TYPE *)0)-> MEMBER 也就是从0址址找到TYPE 的成员MEMBER 。

INIT_LIST_HEAD(&misc->list);

  container_of
实现了根据一个结构中的一个分子变量的指针来取得指向任何结构的指针的成效。其中,offsetof
也是一个宏,它的作用是获得成员变量基于其所在结构的地方的偏移量,定义如下:

咱们构成地点的构造来看

成效和宏LIST_HEAD_INIT一样。

#define offsetof(TYPE,MEMBER)  ((size_t) &((TYPE *)0) -> MEMBER)        // 获得成员变量member基于其所在结构的地址的偏移量,该宏在 linux/stddef.h 中有定义

struct file_node{

static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}

  分析一下 offsetof 宏:

  char c;

接下来,在函数device_create 创造了装备后,

1)、((TYPE *) 0) : 将 0 转换成 TYPE 类型的指针。那注脚了一个针对性 0
的指针,且那么些指针是 TYPE 类型的;

  struct list_head node;

我们就用上面的口舌将装备增加到设备链表:

2)、((TYPE *) 0) -> MEMBER: 访问结构中的成员MEMBER,一个针对 0 的
TYPE 类型的组织;明显,MEMBER 的地址就是偏移地址;

};

list_add(&misc->list, &misc_list);

3)、&((TYPE *) 0) -> MEMBER
:取多少成员MEMBER的地点(不是按位与,不要看错了);

将实参代入 offset( struct file_node, node
);最后将成为那样:

根本文件list.h 提供了向链表添加新项的 API 接口。

4)、((size_t) &((TYPE *) 0) -> MEMBER): 强制类型转换成 size_t
类型。 

(
(size_t) & ((struct file_node*)0)-> node );那样看的仍旧不很了解,大家再变变:

咱们来看望它的兑现:

 

struct file_node
*p = NULL;

static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}

& p->node;

实际就是运用3个指定的参数来调用了其中函数__澳门金沙国际 ,list_add:

诸如此类应有相比较清楚了,即求 p 的积极分子 node的地点,只不过p 为0地址,从0地址早先算成员node的地址,也就是成员 node 在构造体 struct file_node中的偏移量。offset宏就是算MEMBER在TYPE中的偏移量的。

new – 新项。
head – 新项将会插在head的末尾
head->next – 插入前,head 前边的项。
__list_add的落到实处分外不难:

大家再看首个宏

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;
}

#define
container_of(ptr,type,member) ( {\

那边,我们在prev和next 之间添加了一个新项。

  const typeof( ((type*)0)->member )
*__mptr=(ptr);\

从而我们初始时用宏LIST_HEAD_INIT定义的misc
链表会包括指向miscdevice->list 的前进指针和向后指针。
那会儿还有一个题材:怎样取得列表的内容呢?那里有一个很是的宏:

  (type*)( (char*)__mptr –
offsetof(type,member) );} )

#define list_entry(ptr, type, member) \
container_of(ptr, type, member)

本条宏是由多少个语句组成,最终container_of再次回到的结果就是首个表明式的值。那里__mptr为中等变量,那就是list_head指针类型,它被起初化为ptr的值,而ptr就是眼下所求的结构体中list_head节点的地址。为何要用中间变量,这是考虑到安全性因素,即使传进来一个ptr++,所有ptr++放在一个表明式中会有副效用,像 (p++)+(p++)之类。

行使了多个参数:

(char*)__mptr 之所以要强制类型转化为char是因为地点是以字节为单位的,而char的长短就是一个字节。

ptr – 指向结构 list_head 的指针;
type – 结构体类型;
member – 在布局体内类型为list_head 的变量的名字;

container_of的值是八个地点相减,

比如:

刚说了__mptr是结构体中list_head节点的地方,offset宏求的是list_head节点MEMBER在结构体TYPE中的偏移量,那么__mptr减去它所在结构体中的偏移量,就是结构体的地址。

const struct miscdevice *p = list_entry(v, struct miscdevice, list)

所以list_entry(ptr,type,member)宏的成效就是,由结构体成员地址求结构体地址。其中ptr 是所求结构体中list_head成员指针,type是所求结构体类型,member是协会体list_head成员名。通过下图来总计一下:

接下来大家就足以接纳p->minor 或者
p->name来访问miscdevice。让大家来看望list_entry 的实现:

   

#define list_entry(ptr, type, member) \
container_of(ptr, type, member)

澳门金沙国际 4

如我辈所见,它但是使用相同的参数调用了宏container_of。初看那么些宏挺奇怪的:

   

#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})

继续列举部分双链表的常用操作:

先是你可以小心到花括号内包涵多少个表明式。

双向链表的遍历——list_for_each

编译器会举办花括号内的一体言辞,然后回来最终的表明式的值。

//注:那里prefetch 是gcc的一个优化增选,也足以绝不

比如:

#define
list_for_each(pos, head) \

#include <stdio.h>
int main() {
int i = 0;
printf("i = %d\n", ({++i; ++i;}));
return 0;
}

         for (pos =
(head)->next; prefetch(pos->next), pos != (head); \

末段会打印出2。

                 pos
= pos->next)

下一些就是typeof,它也很简单。

   

如同你从名字所精通的,它不过重临了给定变量的序列。当自身先是次看到宏container_of的完毕时,让自家以为最奇怪的就是表明式((type
*)0)中的0。实际上这么些指针巧妙的总计了从结构体特定变量的舞狮,那里的0刚好就是位宽里的零偏移。

变化双向链表的头结点——LIST_HEAD()

比如:

LIST_HEAD() — 生成一个名为name的双向链表头节点

#include <stdio.h>
struct s {
int field1;
char field2;
char field3;
};
int main() {
printf("%p\n", &((struct s*)0)->field3);
return 0;
}

#define
LIST_HEAD(name) \

结果突显0x5。

struct list_head
name = LIST_HEAD_INIT(name)

下一个宏offsetof会计算从结构体起首地址到某个给定结构字段的偏移。

static inline void
INIT_LIST_HEAD(struct list_head *list)

它的兑现和方面类似:
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
今日我们来总计一下宏container_of。只需给定结构体中list_head类型
字段的地点、名字和布局体容器的类型,它就可以回去结构体的发端地址。在宏定义的率先行,申明了一个针对性结构体成员变量ptr的指针__mptr,并且把ptr
的地点赋给它。现在ptr 和__mptr
指向了同一个地址。从技术上讲大家并不需求这一行,可是它可以一本万利地展开项目检查。第一行保障了一定的结构体(参数type)包蕴成员变量member。第二行代码会用宏offsetof总结成员变量绝对于结构体开端地址的晃动,然后从结构体的地址减去这些偏移,最终就赢得了结构体。

{

当然了list_add 和 list_entry不是<linux/list.h>

  list->next = list;

提供的唯一成效。双向链表的落实还提供了如下API:

  list->prev = list;

list_add
list_add_tail
list_del
list_replace
list_move
list_is_last
list_empty
list_cut_position
list_splice
list_for_each
list_for_each_entry

}

等等很多别样API。

双向链表的插入操作 — list_add()

将new所代表的结构体插入head所管理的双向链表的头节点head之后: (即插入表头)

static inline void
list_add(struct list_head *new, struct list_head *head)

{

  __list_add(new, head, head->next);

}

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;

}

从list中去除结点——list_del()

static inline void
list_del(struct list_head *entry)

{

  __list_del(entry->prev,
entry->next);

  entry->next = LIST_POISON1;

  entry->prev = LIST_POISON2;

}

static inline void
__list_del(struct list_head * prev, struct list_head * next)

{

  next->prev = prev;

  prev->next = next;

}

   

判断链表是不是为空(如果双向链表head为空则重返真,否则为假)——list_empty()

static inline int
list_empty(const struct list_head *head)

{

  return head->next == head;

}

   

make it simple, make
it happen

 

相关文章