前言

在操作系统实验中遇到了for_each_process这个宏,记录一下阅读源码时学到的新知识。

for_each_process介绍

操作系统在进行进程管理时,并不是直接对进程所有的内容(程序代码,数据段,进程控制块)进行管理,而是将进程的有效信息提取出来,通过管理这些信息来管理进程。一个进程的基本信息被存放在一个叫做进程控制块(PCB)的数据结构中。task_struct是Linux内核的一种进程控制块的数据结构,它会被装载到RAM中并且包含着进程的信息。每个进程都把它的信息放在 task_struct 这个结构体。每个进程的PCB都被视作一个结点,所有进程的连接都以链表的形式存在内核中。

下面介绍下Linux中的链表结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct list_head {
    struct list_head *next, *prev; //双向循环链表
};
/*附带的两种初始化方法LIST_HEAD_INIT 和 INIT_HEAD_LIST*/
/*利用内联函数实现,比较简单易懂*/
static inline void
INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list->prev = list;
}

/*
利用宏实现,初看LIST_HEAD_INIT不知道是什么意思,结合LIST_HEAD就可以知道
struct list_head name = LIST_HEAD_INIT(name) 等效于
struct list_head name = {&(name),&(name)}
即相当于name->next = name->prev = name
十分简洁!!!!
*/
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

在task_struct中有这样三种链表

1
2
3
4
5
6
struct task_struct{
    struct list_head tasks; //进程的PCB组成的链表
    struct list_head children; //进程的子进程组成的链表
    struct list_head sibling; ////进程的兄弟进程组成的链表
    ......
}

对于进程间直接的互联,通过任务描述符结构task_struct结构中的tasks成员来实现,它是list_head类型。这个链表是一个循环的双向链表,开始的时候只有init_task这一个进程,它是内核的第一个进程,它的初始化是通过静态分配内存,”手动”(其它的进程初始化都是通过动态分配内存初始化的)进行的,每新建一个进程,就通过SET_LINKS宏将该进程的task_struct结构加入到这条双向链表中,不过要注意的是如果一个进程新建一个线程(不包括主线程),也就是轻量级进程,它是不会加入该链表的。通过宏for_each_process可以从init_task开始遍历所有的进程

对于描述进程的亲属关系,Linux进程间的亲属关系有两种,一种是父进程与子进程间的父子关系,一种是进程同属一个父进程的兄弟关系。Linux中是通过进程描述符中的children和sibling来实现这种关系的,它们都是list_head类型的。

for_each_process源码追溯和进一步学习

首先看for_each_process的定义。

1
2
#define for_each_process(p) //从init_task开始遍历所有进程,p的类型是task_struct指针
    for (p = &init_task ; (p = next_task(p)) != &init_task ; )

发现两个未知生物init_task, next_task。

这是init_task的源码

1
2
3
4
5
6
/* Initial task structure */
struct task_struct init_task = INIT_TASK(init_task);

#define INIT_TASK(tsk){
	...
}

有关init_task的介绍:https://blog.csdn.net/gatieme/article/details/51484562

可以浅显认为init_task是系统的第1号进程,也有task_struct结构。

下面分析next_task。顾名思义next_task是取tasks链表中的下一个结点。让我们看下其源码。

1
2
3
4
#define next_task(p) \
	list_entry_rcu((p)->tasks.next, struct task_struct, tasks)
#define list_entry_rcu(ptr, type, member) \
	container_of(READ_ONCE(ptr), type, member)

可以看到,最终next_task追溯到了container_of。

顺便说一句:container_of的参数中出现了READ_ONCE, 这里简单介绍下。在某些情况下CPU对内存中变量读写并不是一次完成的,这可能会出现竞争。而READ_ONCE和WRITEONCE实现对变量一次性读取和一次性写入。这不是这篇文章的重点啦^ ^

下面我们重点分析container_of。

对container_of的分析

1
2
3
4
5
6
#define container_of(ptr, type, member) ({			\
	const typeof(((type *)0)->member) *__mptr = (ptr);	\
	(type *)((char *)__mptr - offsetof(type, member));	\
})

#define offsetof(type, member) ((size_t) &((type *)0)->member)

可以看到container_of中又使用了offsetof这个宏。我们首先分析这个宏的作用,即((size_t) &((type *)0)->member)

  • 0 : 常量0
  • (type *)0 : 对常量0的强制类型转换,转换为type * 类型指针。

先停一下。对一个常量0强制类型转换有什么意义呢,该指针的指向是什么呢?

ansi/iso-c99 标准规定: 值为0的常量可以被强制转换成任何一种类型的指针,
并且转换结果是一个NULL指针。并且NULL 指针的值为 0x00000000, 即内存中的“第 0 号地址”

  • (type *)0 ->member : 利用这个NULL指针来访问type的成员
  • &((type *)0 ->member) : 获得这个成员的地址

再停一下。既然他是一个NULL指针,为什么还可以访问其成员呢?其成员不是根本没有吗?

对于这个部分,聪明的编译器并不是在运行期执行的,而是在编译期根据type的内存布局和结构体实例首址计算得到的该成员的地址,并不会!!真的去访问这个不存在的成员!!

等等,什么叫根据type的内存布局和结构体实例首址计算得到的该成员的地址

举个例子,这里有一个结构体test,其成员为整型变量i,j,k。

1
2
3
4
5
struct test{
    int i;
    int j;
    int k;
}

很容易得到其内存布局如下,同时首地址为0x00H,因为一个int变量占4个字节,所以我们可以计算出变量k的地址:

1
2
3
4
5
6
7
+++++++  0x00H
+  i  +
+++++++  0x04H
+  j  +
+++++++  0x08H
+  k  +
+++++++

所以编译器在做什么事情呢?就是在做我刚才所展示的事情,计算结构体的某个成员的地址。同时,注意到这个地址并不是成员真实的逻辑地址,而是在结构体首地址为0x0000000时,成员的“地址”。我们很容易想到,其实这个所谓的“地址”就是成员相对结构体基址的偏移量。

那么&((type *)0)->member) 要做事情就是返回成员相对结构体基址的偏移量。(size_t)&((type *)0)->member) 就是将这个地址转换为无符号整数而已,其本质没有改变。

总结一下,现在我们的收获:得到了某个成员相对结构体基址的偏移量。

下面分析const typeof(((type *)0)->member) *__mptr = (ptr);

  • typeof : 返回变量的类型,这里就是返回(type *)0)->member 的类型,即type结构体的member成员的类型。
  • const typeof(((type *)0)->member) *__mptr 即为构造了一个常量指针,类型为type结构体的member成员的类型。
  • 然后将ptr的值赋给__mptr

等等,这两个是一个类型的指针么??是的!这里我们对宏的三个参数ptr,type,member的关系做下讲解

1
2
3
4
5
6
7
/*这里有一个名叫type的结构体,其成员为member,然后ptr是一个member类型的指针,指向member*/
struct type +++++++++++++++++++
            +  other members  +
            +   ......        +
            +++++++++++++++++++
ptr----->   +   member        +
            +++++++++++++++++++

下面分析(type *)((char *)__mptr - offsetof(type, member));

  • offsetof(type, member) :这个作用已经分析了,就是得到了某个成员相对结构体基址的偏移量。
  • __mptr : 其值为该成员的真实逻辑地址

等下,还需要强调一点。指针的减法! 假如 __mptr为整型指针 __mptr - offsetof 相当于减去 sizeof(int)*offsetof个字节! 但是我们并不希望它这么作减法,我们希望的是__mptr - offsetof就相当于offsetof个字节。所以使用了char*进行强制类型转换。

  • 也许你现在并不了解什么叫offsetof个字节,那么我们来考虑两者相减到底会发生什么?

还是以test结构体为例,此时结构体的首地址并不是0x00H了,而是真实的逻辑地址

1
2
3
4
5
6
7
+++++++  0xA000H 
+  i  +
+++++++  0xA004H
+  j  +
+++++++  0xA008H
+  k  +
+++++++

刚才我们通过offsetof 计算出了变量k的偏移量0x08H , k的真实逻辑地址为0xA008H ,两者相减0xA008H -0x08H = 0xA000H

惊喜地发现, 两者相减得到了该结构体的地址。

废话说了一大堆,终于说完了。这个container_of的作用是什么呢?就是通过结构体成员的地址得到结构体的地址!!!

回到for_each_process

1
2
3
4
5
6
#define for_each_process(p)
    for (p = &init_task ; (p = next_task(p)) != &init_task ; )
#define next_task(p) \
	list_entry_rcu((p)->tasks.next, struct task_struct, tasks)
#define list_entry_rcu(ptr, type, member) \
	container_of(READ_ONCE(ptr), type, member)

从上面可以看出

  • ptr = p->tasks.next : ptr指向tasks链表中的下一个结点(注意:下一个结点并非是整个task_struct结构,而是task_struct的tasks成员)
  • type = struct task_struct : 结构体类型是task_struct
  • member = tasks : 成员是tasks

所以next_task(p) 就是通过下一个进程的task_struct成员tasks返回了下一个进程的task_struct结构。

下面附录一张图,可能更方便大家理解,所谓的进程链表,其实并不是把整个PCB都链接起来,而是把PCB中的tasks结点链接起来

process

参考资料