日志标签 ‘kernel’

Linux2.6进程调度分析(2)-调度算法

2011年4月4日

2.数据结构

O(1)调度算法通过几个数据结构可以巧妙的实现常数级的复杂度。

2.1可运行队列

调度程序每次在进程发生切换时,都要在就绪队列中选取一个最佳的进程来运行。Linux内核使用runqueue数据结构(在最新内核中该结构为rq)表示一个可运行队列(也就是就绪队列),每个CPU都有且只有一个这样的结构。该结构不仅描述了每个处理器中处于可运行状态(TASK_RUNNING)的进程链表,而且还描述了该处理器的调度信息。下面对该结构中的部分字段作详细描述。

spinlock_t lock:保护进程链表的自旋锁;
unsigned long nr_running:运行队列链表中进程数量;
unsigned long long nr_switches:CPU执行进程切换的次数;
unsigned long nr_uninterruptible:之前在运行队列链表中而现在处于重度睡眠状态的进程总数;
unsigned long expired_timestamp:过期队列中最老的进程被插入队列的时间;
unsigned long long timestamp_last_tick:最近一次定时器终端的时间;
task_t *curr:指向本地CPU当前正在运行的进程的进程描述符,即current;
task_t *idle:指向本地CPU上的idle进程描述符的指针;
struct mm_struct *prev_mm:在进程进行切换时用来存放被替换进程内存描述符的地址;
prio_array_t *active:指向可运行队列中活动链表;
prio_array_t *expired:指向可运行队列中过期链表;
prio_array_t arrays[2]:该数组的元素分别表示可运行队列中的活动进程集合和过期进程集合;
int best_expired_prio:过期进程中优先级最高的进程;

到目前为止,你可能对上述字段的理解还不是很深,最好的办法是学习完下面的内容后再回过头来重新看这些字段的用途。我们在上面说过,runqueue结构最主要的功能是描述处于可运行状态进程所组成的链表。不过,所谓的可运行队列并不是将一些列的runqueue结构连接在一些,而是由runqueue结构中的arrays数组来体现,该数组的元素为prio_array_t类型。

2.2优先级数组

O(1)算法的另一个核心数据结构即为prio_array结构体。该结构体中有一个用来表示进程动态优先级的数组queue,它包含了每一种优先级进程所形成的链表。

#define MAX_USER_RT_PRIO        100
#define MAX_RT_PRIO             MAX_USER_RT_PRIO
#define MAX_PRIO                (MAX_RT_PRIO + 40)
typedef struct prio_array prio_array_t;
struct prio_array {
        unsigned int nr_active;
        unsigned long bitmap[BITMAP_SIZE];
        struct list_head queue[MAX_PRIO];
};

由于进程优先级的最大值为139,因此MAX_PRIO的最大值取140(具体的是,普通进程使用100到139的优先级,实时进程使用0到99的优先级)。因此,queue数组中包含140个可运行状态的进程链表,每一条优先级链表上的进程都具有相同的优先级,而不同进程链表上的进程都拥有不同的优先级。

除此之外,prio_array结构中还包括一个优先级位图bitmap。该位图使用一个位(bit)来代表一个优先级,而140个优先级最少需要5个32位来表示,因此BITMAP_SIZE的值取5。起初,该位图中的所有位都被置0,当某个优先级的进程处于可运行状态时,该优先级所对应的位就被置1。

因此,O(1)算法中查找系统最高的优先级就转化成查找优先级位图中第一个被置1的位。与2.4内核中依次比较每个进程的优先级不同,由于进程优先级个数是定值,因此查找最佳优先级的时间恒定,它不会像以前的方法那样受可执行进程数量的影响。

如果确定了优先级,那么选取下一个进程就简单了,只需在queue数组中对应的链表上选取一个进程即可。

2.3活动进程和过期进程

在操作系统原理课上我们知道,当处于运行态的进程用完时间片后就会处于就绪态,此时调度程序再从就绪态的进程中选取一个作为即将要运行的进程。

而在具体Linux内核中,就绪态和运行态统一称为可运行态(TASK_RUNNING)。对于系统内处于可运行状态的进程,我们可以分为三类,首先是正处于执行状态的那个进程;其次,有一部分处于可运行状态的进程则还没有用完他们的时间片,他们等待被运行;剩下的进程已经用完了自己的时间片,在其他进程没有用完它们的时间片之前,他们不能再被运行。

据此,我们将进程分为两类,活动进程,那些还没有用完时间片的进程;过期进程,那些已经用完时间片的进程。因此,调度程序的工作就是在活动进程集合中选取一个最佳优先级的进程,如果该进程时间片恰好用完,就将该进程放入过期进程集合中。

在可运行队列结构中,arrays数组的两个元素分别用来表示刚才所述的活动进程集合和过期进程集合,active和expired两个指针分别直接指向这两个集合。

关于可运行队列和两个优先级数组的关系可参考下面的图:

正如上面分析的那样,可运行队列结构和优先级数组结构使得Q(1)调度算法在有限的时间内就可以完成,它不依赖系统内可运行进程的数量。

3. 调度算法

Linux2.4版本的内核调度算法理解起来简单:在每次进程切换时,内核依次扫描就绪队列上的每一个进程,计算每个进程的优先级,再选择出优先级最高的进程来运行;尽管这个算法理解简单,但是它花费在选择优先级最高进程上的时间却不容忽视。系统中可运行的进程越多,花费的时间就越大,时间复杂度为O(n)。伪代码如下:

for (系统中的每个进程) {
	重新计算时间片;
	重新计算优先级;
}

而2.6内核所采用的O(1)算法则很好的解决了这个问题,该算法可以在恒定的时间内为每个进程重新分配好时间片,而且在恒定的时间内可以选取一个最高优先级的进程,重要的是这两个过程都与系统中可运行的进程数无关,这也正是该算法取名为O(1)的缘故。

3.1 O(1)中时间片的计算

O(1)算法采用过期进程数组和活跃进程数组解决以往调度算法所带来的O(n)复杂度问题。过期数组中的进程都已经用完了时间片,而活跃数组的进程还拥有时间片。当一个进程用完自己的时间片后,它就被移动到过期进程数组中,同时这个过期进程在被移动之前就已经计算好了新的时间片。可以看到O(1)调度算法是采用分散计算时间片的方法,并不像以往算法中集中为所有可运行进程重新计算时间片。

当活跃进程数组中没有任何进程时,说明此时所有可运行的进程都用完了自己的时间片。那么此时只需要交换一下两个数组即可将过期进程切换为活跃进程,进而继续被调度程序所调度。两个数组之间的切换其实就是指针之间的交换,因此花费的时间是恒定的。下面的代码说明了两个数组之间的交换:

struct prop_array *array = rq->active;
if (array->nr_active != 0) {
	rq->active = rq->expired;
	rq->expired = array;
}

通过分散计算时间片、交换过期和活跃两个进程集合的方法可以使得O(1)算法在恒定的时间内为每个进程重新计算好时间片。

3.2 O(1)中进程的选择

进程调度的本质就是在当前可运行的进程集合中选择一个最佳的进程,这个最佳则是以进程的动态优先级为选取标准的。不管是过期进程集合还是活跃进程集合,都将每个优先级的进程组成一个链表,因此每个集合就有140个不同优先级的进程链表。同时,两个集合中还采用优先级位图来标记每个优先级链表中是否存在进程。

调度程序在选取最高优先级的进程时,首先利用优先级位图从高到低找到第一个被设置的位,该位对应着一条进程链表,这个链表中的进程是当前系统所有可运行进程中优先级最高的。在该优先级链表中选取头一个进程,它拥有最高的优先级,即为调度程序马上要执行的进程。上述进程的选取过程可用下述代码描述:

struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array *array;
int idx;

prev = current;
array = rq->active;
idx = sehed_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list);
if (prev != next)
	context_switch();

sehed_find_first_bit()用于在位图中快速查找第一个被设置的位。如果prev和next不是一个进程,那么此时进程切换就开始执行。

通过上述的内容可以发现,在恒定的时间重新分配时间片和选择一个最佳进程是Q(1)算法的核心。
参考:

1.深入理解LINUX内核(第三版) ;(美)博韦,西斯特 著; 陈莉君 张琼声 张宏伟译; 中国电力出版社;

2.Linux内核设计与实现;(美)拉芙(Love,R.)著,陈莉君 等译;机械工业出版社;

Linux2.6进程调度分析(1)-调度策略

2011年4月3日

对于分时操作系统而言,表面上看起来是多个进程同时在执行,而在系统内部则进行着从一个进程到另一个进程的切换动作。这样的进程并发执行涉及到进程切换(process switch)和进程调度(process scheduling)两大问题。本文主要说明Linux2.6中的普通进程调度策略(实时进程和普通进程在调度上稍有不同)问题,即系统何时进行进程切换以及选择哪一个进程进行切换。

1.调度策略

理想的进程调度目标应该是:进程响应时间尽可能的快,后台作业吞吐量高,避免某些进程出现饥饿现象,包括低优先级在内的所有进程都有被调度的可能。由此看来,进程调度的工作就是要处理好这几个方面的协调关系,使进程调度的综合性能达到最佳。

与进程调度最为密切的因素是进程的优先级,进程优先级通过一个数值来实现,每个进程都与一个值相关联。调度程序根据进程的优先级将CPU适当的分配给某一个进程。进程的优先级又跟进程的许多因素有关,接下来我们将依次分析这些因素与进程优先级的关系。

1.1进程的分类

进程可以被分为两种类型:I/O消耗型和CPU消耗型。前种类型的进程频繁使用I/O设备,并且大部分时间处于等待状态,以得到新的I/O请求,比如键盘活动等。后一种类型的进程则大部分时间都在占用CPU,对I/O设备并没有过多的需求。

为了使系统有较强的响应能力,I/O消耗型进程必须很快能被唤醒,以实现进程的切换。否则,用户会感到系统反应迟钝。对于CPU消耗型进程,由于它们常常位于后台运行,并且没有过多的I/O需求,因此系统并不需要对这类进程做出快速反应。

正如上面所说的,调度程序通常要处理好这两类进程之间的调度关系:系统既要有迅速的响应能力,又要有最大的CPU利用率(高吞吐量)。这种满足关系其实是矛盾的,如果系统要达到最大利用率,那么CPU就会被一直占用,这样就不能对I/O请求做出迅速响应。调度程序为了调和这种冲突,通常会倾向于I/O消耗型进程。也就是说,调度程序会优先调用这类进程以提高系统的响应能力,而尽量将CPU消耗型进程压后执行。但这并不意味着这类进程就被调度程序忽略。

1.2时间片

Linux的调度是基于分时技术的,多个进程以“时间多路复用”的形式运行,CPU的时间被划分成一小段,即所谓的时间片(slice)。每个进程都会得到一个时间片,在具体某个时间片内,一个进程会独享CPU时间。如果该进程在这个时间片内没有运行完毕,调度程序就会切换该进程使得其他拥有时间片的进程运行。

时间片的划分对系统来说也是一件难事,既不能过长又不能过短。过长的时间片会导致系统的响应能力下降;而过短的时间片会导致系统频繁发生进程切换,由此将带来不必要的处理器消耗。显然,I/O消耗型进程希望时间片越短越好,这样那些等待I/O的进程就能被迅速切换;而CPU消耗型进程则希望时间片越长越好,这样它们就可以一直占用CPU。因此,I/O消耗型进程和CPU消耗型进程的矛盾再一次显现出来。

Linux调度程序解决这种矛盾的方法是,提供一个较长的默认时间片,但是却提高交互进程的优先级,以使得这些进程运行的更频繁。在Linux的调度算法中,每个进程在诞生时总是继承父进程一半的时间片,而之后的时间片则是调度程序根据进程的静态优先级而分配。

1.3优先级

我们上面说过,调度程序在选取下一个执行的进程时依据的是进程的优先级。通过上面对进程的划分可以看出,不同类型的进程应该有不同的优先级。每个进程与生俱来(即从父进程那里继承而来)都有一个优先级,我们将其称为静态优先级。普通进程的静态优先级范围从100到139,100为最高优先级,139为最低优先级。

当进程用完了时间片后,系统就会为该进程分配新的时间片(即基本时间片),静态优先级本质上决定了时间片分配的大小。静态优先级和基本时间片的关系如下:

静态优先级<120,基本时间片=max((140-静态优先级)*20, MIN_TIMESLICE)
静态优先级>=120,基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)

其中MIN_TIMESLICE为系统规定的最小时间片。从该计算公式可以看出,静态优先级越高(值越低),进程得到的时间片越长。其结果是,优先级高的进程会获得更长的时间片,而优先级低的进程得到的时间片则较短。

进程除了拥有静态优先级外,还有动态优先级,其取值范围是100到139。当调度程序选择新进程运行时就会使用进程的动态优先级,动态优先级和静态优先级的关系可参考下面的公式:

动态优先级=max(100 , min(静态优先级 – bonus + 5) , 139)

从上面看出,动态优先级的生成是以静态优先级为基础,再加上相应的惩罚或奖励(bonus)。这个bonus并不是随机的产生,而是根据进程过去的平均睡眠时间做相应的惩罚或奖励。

所谓平均睡眠时间(sleep_avg,位于task_struct结构中)就是进程在睡眠状态所消耗的总时间数,这里的平均并不是直接对时间求平均数。平均睡眠时间随着进程的睡眠而增长,随着进程的运行而减少。因此,平均睡眠时间记录了进程睡眠和执行的时间,它是用来判断进程交互性强弱的关键数据。如果一个进程的平均睡眠时间很大,那么它很可能是一个交互性很强的进程。反之,如果一个进程的平均睡眠时间很小,那么它很可能一直在执行。另外,平均睡眠时间也记录着进程当前的交互状态,有很快的反应速度。比如一个进程在某一小段时间交互性很强,那么sleep_avg就有可能暴涨(当然它不能超过MAX_SLEEP_AVG),但如果之后都一直处于执行状态,那么sleep_avg就又可能一直递减。

理解了平均睡眠时间,那么bonus的含义也就显而易见了。交互性强的进程会得到调度程序的奖励(bonus为正),而那些一直霸占CPU的进程会得到相应的惩罚(bonus为负)。其实bonus相当于平均睡眠时间的缩影,此时只是将sleep_avg调整成bonus数值范围内的大小。

参考:

1.深入理解LINUX内核(第三版) ;(美)博韦,西斯特 著; 陈莉君 张琼声 张宏伟译; 中国电力出版社;

2.Linux内核设计与实现;(美)拉芙(Love,R.)著,陈莉君 等译;机械工业出版社;

虚拟映射和mmap()

2011年1月12日

虚存映射

我们知道,程序是存储在磁盘上到静态文件;进程是对程序到一次运行过程。在进程开始运行时,进程的代码和数据等内容必须装入到进程用户空间到适当区域。这些区域也就是所谓的代码段和数据段等,而被装入的数据和代码等内容被称为进程的可执行映像。从上面都描述中可以发现,进程在运行时并不是将程序一下子就装入到物理内存,而只是将程序装入到进程的用户空间,这个装入的过程称为虚存映射。

一个源程序在成为可执行文件的过程中会经历预处理、编译、汇编和链接四个阶段。因此,进程要成功运行不仅要在其用户空间装入进程映像,也要装入该进程所用到到函数库以及链接程序等。所以,一个进程到用户空间就被分为若干个内存区域。linux使用mm_struct结构来描述一个进程到用户地址空间,使用vm_area_struct结构来描述进程地址空间中的一个内存区域。因此,一个vm_area_struct结构可能代表进程到数据段,也可能代表链接程序到代码段等。

进程的虚存映射所做的只是将磁盘上到文件映射到该进程的用户地址空间,并没有建立虚拟内存到物理内存的映射。当某个可执行映像映射到进程用户空间并开始执行时,只有很少一部分虚拟页被装入了物理内存。在进程后续到执行过程中,如果需要访问到数据并不在物理内存中,则产生一个缺页中断(其实是异常),将所需页从交换区或磁盘中调入物理内存,这个过程即虚拟内存中到请页机制。

进程到虚存区

那么对于一个任意的进程,我们可以通过下面到方法查看其地址空间中到内存区域。

我们先看一个简单的测试程序:

#include < stdio.h >
#include < stdlib.h >

int main()
{
	int i=1;
	char *str=NULL;
	printf("hello,world!\n");
	str=(char *)malloc(sizeof(char)*1119);

	sleep(1000);

	return 0;
}

这个程序中使用到了malloc函数,因此str变量存储于堆中。我们通过打印/proc/3530/maps文件,即可看到该进程的内存空间划分。其中3530是该进程的id。

edsionte@edsionte-desktop:~$ cat /proc/3530/maps
0014a000-00165000 r-xp 00000000 08:07 398276     /lib/ld-2.11.1.so
00165000-00166000 r--p 0001a000 08:07 398276     /lib/ld-2.11.1.so
00166000-00167000 rw-p 0001b000 08:07 398276     /lib/ld-2.11.1.so
001d8000-0032b000 r-xp 00000000 08:07 421931     /lib/tls/i686/cmov/libc-2.11.1.so
0032b000-0032c000 ---p 00153000 08:07 421931     /lib/tls/i686/cmov/libc-2.11.1.so
0032c000-0032e000 r--p 00153000 08:07 421931     /lib/tls/i686/cmov/libc-2.11.1.so
0032e000-0032f000 rw-p 00155000 08:07 421931     /lib/tls/i686/cmov/libc-2.11.1.so
0032f000-00332000 rw-p 00000000 00:00 0
00441000-00442000 r-xp 00000000 00:00 0          [vdso]
08048000-08049000 r-xp 00000000 08:09 326401     /home/edsionte/test
08049000-0804a000 r--p 00000000 08:09 326401     /home/edsionte/test
0804a000-0804b000 rw-p 00001000 08:09 326401     /home/edsionte/test
08958000-08979000 rw-p 00000000 00:00 0          [heap]
b78ce000-b78cf000 rw-p 00000000 00:00 0
b78dd000-b78e0000 rw-p 00000000 00:00 0
bfa6a000-bfa7f000 rw-p 00000000 00:00 0          [stack]

每一行信息依次显示的内容为内存区域其实地址-终止地址,访问权限,偏移量,主设备号:次设备号,inode,文件。

上面的信息不但包含了test可执行对象的各内存区域,而且还分别显示了 /lib/ld-2.11.1.so(动态连接程序)文件和/lib/tls/i686/cmov/libc-2.11.1.so(C库)文件的内存区域信息。

我们从某个内存区域的访问权限上可以大致判断该区域的类型。各个属性符号的意义为:r-read,w-write,x-execute,s-shared,p-private。因此,r-x一般代表程序的代码段,即可读,可执行。rw-可能代表数据段,BSS段和堆栈段等,即可读,可写。堆栈段从行信息的文件名就可以区分;如果某行信息的文件名为空,那么可能是BSS段。另外,上述test进程共享了内核动态库,所以在00441000-00442000行处文件名显示为vdso(Virtual Dynamic Shared Object)。

mmap系统调用

通过mmap系统调用可以在进程到用户空间中创建一个新到虚存区。该系统调用到原型如下:

#include
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

该函数可以将以打开的文件映射到进程用户空间到一片内存区上,执行成功后,该函数返回这段映射区到首地址。用户得到这片虚存的首地址后,就可以像访问内存那样访问文件。

该系统调用的参数说明如下:

addr:映射到用户地址空间到起始地址;
length:映射区以字节为单位到长度;
prot:对映射区到访问模式。包括PROT_EXEC(可执行),PROT_READ (可读),PROT_WRITE(可写),PROT_NONE(文件不可访问)。这个访问模式不能超过所映射文件到打开模式。比如被映射的文件打开模式为只读,那么此处到访问模式不能是可读写的。
flags:这个字段比较灵活,不同到标志有不同的功能,具体如下:
MAP_SHARED:创建一个可被子进程共享的映射区;
MAP_PRIVATE:创建一个“写实复制”的映射区;
MAP_ANONYMOUS:创建一个匿名到映射区,该虚存区与进程无关;
fd:所要映射到进程用户空间的文件描述符,该文件必须为以打开的文件;
offset:文件的起始映射偏移量;

mmap()举例

在该程序中,首先以只读方式打开文件test.c,再通过该文件返回到文件描述符和mmap函数将test.c文件映射到当前进程到用户地址空间中。成功执行mmap函数后,buf被赋值为所映射的虚存区的首地址。注意,mmap函数返回的是void型指针,而buf是char型指针。将mmap返回值赋值给buf变量时,自动将void*转化为char*型。

最后,就像平常我们使用一个char型指针变量那样,依次打印出buf中到数据。

#include < stdio.h >
#include < sys/mman.h >
#include < fcntl.h >
int main()
{
	int i,fd;
	char *buf = NULL;

	fd = open("./test.c", O_RDONLY);
	if(fd < 0)
	{
		printf("open error\n");
		return -1;
	}

	buf = mmap(NULL, 12, PROT_READ, MAP_PRIVATE ,fd, 0);
	for(i = 0;i < 12;i++)
	{
		printf("%c",buf[i]);
	}
	printf("\n");

	return 0;
}

try一下!

边学边实践:打印VFS中的结构体

2010年11月27日

学习了VFS的基本原理,我们很有必要对这些理论知识进行验证和实践。本文所分析的几个小程序将更具体、直观的展现VFS中一些数据结构之间的逻辑关系。

1.打印超级块和索引结点

通过前面的分析我们知道,系统中所有的超级块都内嵌一个struct list_head类型的字段s_list。通过该字段将系统中所有的超级块链接成一个双联表。因此,如果我们知道这个双联表的头指针以及了解相关便利宏的使用方法,那么我们就可以遍历整个系统中的所有超级块了。
为了解释方便,我们将内嵌的list_head结构体称为内部结构体;将super_block结构体称为外部结构体;

具体的,我们可以通过 list_for_each宏来遍历一个list_head类型的双联表。该宏的定义如下:

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

使用该宏时,需要向head参数中传递要遍历双联表的头指针;而每次遍历得到的list_head类型的结点地址会保存在pos这个参数中。不过,这个宏只能遍历内嵌于超级块中的那个list_head结构的链表,并不能得到正在被遍历的那个超级块的地址(也就是指向当前正被遍历的超级块的指针)。也就是说,每次遍历时并不能得到超级块中的其他字段。因此,还应该使用 list_entry宏。该宏通过指向list_head结点的地址来得到外部超级块的首地址。

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

这个宏的第一个参数是指向内部结构体list_head的指针,第二个参数是外部结构体的类型,第三个参数是list_head类型的变量在外部结构体中的名称。这个宏最后会返回指向当前外部结构体的指针。比如,在super_block结构体中,list_head结构类型的字段名称为s_list,因此可以如下使用该宏:

sb = list_entry(pos, struct super_block, s_list);

对于超级块形成的双联表来说,它的头指针是super_blocks。但是很遗憾,super_blocks这个变量并没有被导出。所谓导出,就是通过EXPORT_SYMBOL将某个函数或者变量对全部内核代码公开。也就是说,使用 EXPORT_SYMBOL可以将一个函数以符号的方式导出给其他模块使用 。为了解决这个问题,我们可以在包含super_blocks的这个文件中将这个变量导出,并且重新编译内核。对于我们这里的这个小程序而言,这样做有些不值得。幸好,在/proc/kallsyms文件中,记录了内核中所有符号以及符号的地址。因此,在该文件中查找相应符号就可以得到其地址。

我们使用下述两条命令:

edsionte@edsionte-desktop:~/code/vfs/print_sb$ grep super_blocks /proc/kallsyms
c0772a30 D super_blocks
edsionte@edsionte-desktop:~/code/vfs/print_sb$ grep " sb_lock" /proc/kallsyms
c08c9d60 B sb_lock

就可以得到super_blocks变量的地址。另外,sb_lock超级块对应的自旋锁。

上述都准备好后,我们就可以进行遍历了。关键代码如下:

#define SUPER_BLOCKS_ADDRESS 0xc0772a30
#define SB_LOCK_ADDRESS 0xc08c9d60

static int __init my_init(void)
{
struct super_block *sb;
struct list_head *pos;
struct list_head *linode;
struct inode *pinode;
unsigned long long count = 0;

printk("print some fields of super blocks:\n");
spin_lock((spinlock_t *)SB_LOCK_ADDRESS);
list_for_each(pos, (struct list_head *)SUPER_BLOCKS_ADDRESS){

sb = list_entry(pos, struct super_block, s_list);
printk("dev_t:%d,%d ",MAJOR(sb->s_dev),MINOR(sb->s_dev));
printk("fs_name:%s\n",sb->s_type->name);
printk("\n");
}

spin_unlock((spinlock_t *)SB_LOCK_ADDRESS);
printk("the number of inodes:%llu\n",sizeof(struct inode)*count);

return 0;
}

另外,需要注意的是,每次重启电脑后,都要重新查找上述两个变量的地址。

对于一个超级块中所有的inode,有专门一个链表将所有的inode链接起来。这个链表的头结点是超级块中的s_inode字段。而inode之间是其内部的i_sb_list字段进行链接的。了解了这些,我们可以在上述程序的基础上,再打印每个超级块中的所有inode:

	list_for_each(pos, (struct list_head *)SUPER_BLOCKS_ADDRESS){

		sb = list_entry(pos, struct super_block, s_list);
		printk("dev_t:%d,%d ",MAJOR(sb->s_dev),MINOR(sb->s_dev));
		printk("fs_name:%s\n",sb->s_type->name);

		list_for_each(linode, &sb->s_inodes){

			pinode = list_entry(linode, struct inode, i_sb_list);
			count ++;
			printk("%lu\t",pinode->i_ino);
		}

		printk("\n");
	}

在上面代码的基础上,我们再加深一步。一个索引结点可能对应若干个dentry,这些dentry自身通过其内部的d_alias链接在一起;而整个链表的头结点是inode中的i_dentry字段。因此,根据上面的方法,我们可以在遍历每个inode的同时,继续遍历这个inode对应的所有dentry。部分代码如下:

	list_for_each(pos, (struct list_head *)SUPER_BLOCKS_ADDRESS){
		sb = list_entry(pos, struct super_block, s_list);
		printk("dev_t:%d,%d ",MAJOR(sb->s_dev),MINOR(sb->s_dev));
		printk("fs_name:%s\n",sb->s_type->name);

		list_for_each(linode, &sb->s_inodes){
			pinode = list_entry(linode, struct inode, i_sb_list);
			count ++;
			printk("%lu[",pinode->i_ino);

			list_for_each(ldentry, &pinode->i_dentry){
				pdentry = list_entry(ldentry, struct dentry, d_alias);
				printk("%s->",pdentry->d_name.name);
			}
			printk("]\t");
		}
		
		printk("\n");
	}

上出程序的完整的代码在这里

2.打印文件类型结构体

同样的道理,通过下述的代码可以打印file_system_type结构体。

#define FILE_SYSTEM_ADDRESS 0xc08ca3a4 /* grep file_systems /proc/kallsyms */
#define FILE_SYSTEM_LOCK_ADDRESS 0xc0772de0 /* grep file_systems_lock /proc/kallsyms */

static int __init printfs_init(void)
{
	struct file_system_type **pos;

	printk("\n\nprint file_system_type:\n");

	read_lock((rwlock_t *)FILE_SYSTEM_LOCK_ADDRESS);
	pos = (struct file_system_type **)FILE_SYSTEM_ADDRESS;

	while(*pos){
		printk("name: %s\n",(*pos)->name);
		pos = &((*pos)->next);
	}

	read_unlock((rwlock_t *)FILE_SYSTEM_LOCK_ADDRESS);

	return 0;
}

更多的打印信息可以按照上述方法继续添加。开始吧!

进程用户空间的代码描述

2010年11月9日

在前文中,我们对进程的虚拟地址空间进行了概述。本文将从内核代码的角度来分析进程的用户空间的的组织和结构。

上文中提到,每一个进程都拥有3GB大小的用户空间,而连续用户空间又按照存储内容的不同被划分成若干个区域。在内核中,主要通过mm_struct结构体和vm_area_struct结构体对进程用户空间进行描述。前者是对进程的用户空间进行整体的描述;而后者则是对用户空间中的某个区域进行描述。显然,每一个进程对应的有一个mm_struct结构和多个vm_area_struct结构。

1.mm_struct结构

最新版本中的mm_struct结构字段比较多,接下来只对部分字段做以说明。

mmap:vm_area_struct结构体类型的指针。指向进程用户空间中各区域所组成的双链表。链表方式可以高效的遍历所有元素;
mm_rb:rb_root结构体类型。同样描述内存区域块,只不过采用红黑树来表示。用红黑树可以快速索引到指定的元素;
mm_users:atomic_t类型。用来记录正在使用该地址空间的进程数目。比如,当前有3个进程正在共享该地址空间,那么其值为3;
mm_count:atomic_t类型。记录mm_struct结构体被引用的次数。如果当前该地址空间只被两个进程所共享,那么该值为1,mm_users为2;当这两个进程都退出时,该值为0,mm_users也为0。另外,内核线程并不需要访问用户的内存空间,也并不需要创建页表。内核线程一般会直接使用前一个进程的mm_struct结构。因此该字段的计数还包括内核线程对这个结构的引用。
map_count:int类型。内存区域的个数;
pgd:pgd_t类型,该结构体类型内部封装的是unsigned long类型的数据。pgd表示的是页目录基址。当调度程序调度一个进程运行时,就将这个线性地址转化为物理地址,并写入CR3控制寄存器中;
start_code, end_code, start_data, end_data:unsigned long类型。进程代码段和数据段的起始地址和终止地址;
start_brk, brk, start_stack:unsigned long类型。分别为堆的起始地址和终止地址,堆栈的起始地址。上文说过,进程的堆栈段是根据需求向下(朝低地址方向)延伸的,因此这里并没有堆栈段的终止地址;
arg_start, arg_end, env_start, env_end:unsigned long类型。命令行参数所在内存的起始地址和终止地址,环境变量所在内存的起始地址和终止地址;

2.vm_area_struct结构

上面我们已经知道,该结构体描述的是进程用户空间中的一个虚拟内存区间(Virtual Memory Area,VMA)。
vm_mm:mm_struct结构体类型指针。指向该区域所属的用户空间对应的mm_struct结构体。
vm_start,vm_end:unsigned long类型。该虚存区域的起始地址和终止地址。
vm_next,vm_prev:vm_area_struct结构体类型指针。构成VMA双联表。
vm_flags:unsigned long类型。该虚存区的标志。
vm_page_prot:pgprot_t结构体类型,内部封装了unsigned long类型。访问控制权限。
vm_ops:vm_operations_struct结构体类型。该虚存区域的操作函数接口,这些函数可以对虚存区中的页进行操作。

3.数据结构的关系

了解了上述结构体的关键字段,它们与进程之间的逻辑关系便是我们接下来要关心的重点。我们知道,一个进程在内核中使用task_struct结构对其进行描述。task_struct结构中有一个mm字段,它所指向的便是与该进程用户空间所对应的mm_struct结构体。通过上述分析,我们知道mm_struct结构中有mmap字段,它指向VMA双链表。因此,我们使用current->mm->mmap就可以获得VMA链表的头指针。那么current->mm->mmap->vm->next就可以获得指向该VMA双联表的下一个结点的指针。

4.动手查看内存区域

上述我们从代码角度分析了用户地址空间和内存区域。那么对于一个任意的进程,我们如何查看它的内存空间和所划分的内存区域?

我们先看一个简单的测试程序:

#include 
#include 

int main()
{
	int i=1;
	char *str=NULL;
	printf("hello,world!\n");
	str=(char *)malloc(sizeof(char)*1119);

	sleep(1000);

	return 0;
}

这个程序中使用到了malloc函数,因此str变量存储于堆中。我们通过打印/proc/3530/maps文件,即可看到该进程的内存空间划分。其中3530是该进程的id。

edsionte@edsionte-desktop:~$ cat /proc/3530/maps
0014a000-00165000 r-xp 00000000 08:07 398276     /lib/ld-2.11.1.so
00165000-00166000 r--p 0001a000 08:07 398276     /lib/ld-2.11.1.so
00166000-00167000 rw-p 0001b000 08:07 398276     /lib/ld-2.11.1.so
001d8000-0032b000 r-xp 00000000 08:07 421931     /lib/tls/i686/cmov/libc-2.11.1.so
0032b000-0032c000 ---p 00153000 08:07 421931     /lib/tls/i686/cmov/libc-2.11.1.so
0032c000-0032e000 r--p 00153000 08:07 421931     /lib/tls/i686/cmov/libc-2.11.1.so
0032e000-0032f000 rw-p 00155000 08:07 421931     /lib/tls/i686/cmov/libc-2.11.1.so
0032f000-00332000 rw-p 00000000 00:00 0
00441000-00442000 r-xp 00000000 00:00 0          [vdso]
08048000-08049000 r-xp 00000000 08:09 326401     /home/edsionte/test
08049000-0804a000 r--p 00000000 08:09 326401     /home/edsionte/test
0804a000-0804b000 rw-p 00001000 08:09 326401     /home/edsionte/test
08958000-08979000 rw-p 00000000 00:00 0          [heap]
b78ce000-b78cf000 rw-p 00000000 00:00 0
b78dd000-b78e0000 rw-p 00000000 00:00 0
bfa6a000-bfa7f000 rw-p 00000000 00:00 0          [stack]

每一行信息依次显示的内容为内存区域其实地址-终止地址,访问权限,偏移量,主设备号:次设备号,inode,文件。

上面的信息不但包含了test可执行对象的各内存区域,而且还分别显示了 /lib/ld-2.11.1.so(动态连接程序)文件和/lib/tls/i686/cmov/libc-2.11.1.so(C库)文件的内存区域信息。

我们从某个内存区域的访问权限上可以大致判断该区域的类型。各个属性符号的意义为:r-read,w-write,x-execute,s-shared,p-private。因此,r-x一般代表程序的代码段,即可读,可执行。rw-可能代表数据段,BSS段和堆栈段等,即可读,可写。堆栈段从行信息的文件名就可以区分;如果某行信息的文件名为空,那么可能是BSS段。另外,上述test进程共享了内核动态库,所以在00441000-00442000行处文件名显示为vdso(Virtual Dynamic Shared Object)。

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key