kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

Linux Cache 机制探究

http://www.penglixun.com/tech/system/linux_cache_discovery.html

相关源码主要在:
./fs/fscache/cache.c Cache实现的代码
./mm/slab.c SLAB管理器代码
./mm/swap.c 缓存替换算法代码
./mm/mmap.c 内存管理器代码
./mm/mempool.c 内存池实现代码

0. 预备:Linux内存管理基础

创建进程fork()、程序载入execve()、映射文件mmap()、动态内存分配malloc()/brk()等进程相关操作都需要分配内存给进程。不过这时进程申请和获得的还不是实际内存,而是虚拟内存,准确的说是“内存区域”。Linux除了内核以外,App都不能直接使用内存,因为Linux采用Memory Map的管理方式,App拿到的全部是内核映射自物理内存的一块虚拟内存。malloc分配很少会失败,因为malloc只是通知内存App需要内存,在没有正式使用之前,这段内存其实只在真正开始使用的时候才分配,所以malloc成功了并不代表使用的时候就真的可以拿到这么多内存。据说Google的tcmalloc改进了这一点。

进程对内存区域的分配最终多会归结到do_mmap()函数上来(brk调用被单独以系统调用实现,不用do_mmap())。内核使用do_mmap()函数创建一个新的线性地址区间,如果创建的地址区间和一个已经存在的地址区间相邻,并且它们具有相同的访问权限的话,那么两个区间将合并为一个。如果不能合并,那么就确实需要创建一个新的VMA了。但无论哪种情况, do_mmap()函数都会将一个地址区间加入到进程的地址空间中,无论是扩展已存在的内存区域还是创建一个新的区域。同样释放一个内存区域使用函数do_ummap(),它会销毁对应的内存区域。

另一个重要的部分是SLAB分配器。在Linux中以页为最小单位分配内存对于内核管理系统物理内存来说是比较方便的,但内核自身最常使用的内存却往往是很小(远远小于一页)的内存块,因为大都是一些描述符。一个整页中可以聚集多个这种这些小块内存,如果一样按页分配,那么会被频繁的创建/销毁,开始是非常大的。

为了满足内核对这种小内存块的需要,Linux系统采用了SLAB分配器。Slab分配器的实现相当复杂,但原理不难,其核心思想就是Memory Pool。内存片段(小块内存)被看作对象,当被使用完后,并不直接释放而是被缓存到Memory Pool里,留做下次使用,这就避免了频繁创建与销毁对象所带来的额外负载。

Slab技术不但避免了内存内部分片带来的不便,而且可以很好利用硬件缓存提高访问速度。但Slab仍然是建立在页面基础之上,Slab将页面分成众多小内存块以供分配,Slab中的对象分配和销毁使用kmem_cache_alloc与kmem_cache_free。

关于SALB分配器有一份资料:http://lsec.cc.ac.cn/~tengfei/doc/ldd3/ch08s02.html

关于内存管理的两份资料:http://lsec.cc.ac.cn/~tengfei/doc/ldd3/ch15.html

http://memorymyann.javaeye.com/blog/193061

1. Linux Cache的体系

在 Linux 中,当App需要读取Disk文件中的数据时,Linux先分配一些内存,将数据从Disk读入到这些内存中,然后再将数据传给App。当需要往文件中写数据时,Linux先分配内存接收用户数据,然后再将数据从内存写到Disk上。Linux Cache 管理指的就是对这些由Linux分配,并用来存储文件数据的内存的管理。

下图描述了 Linux 中文件 Cache 管理与内存管理以及文件系统的关系。从图中可以看到,在 Linux 中,具体的文件系统,如 ext2/ext3/ext4 等,负责在文件 Cache和存储设备之间交换数据,位于具体文件系统之上的虚拟文件系统VFS负责在应用程序和文件 Cache 之间通过 read/write 等接口交换数据,而内存管理系统负责文件 Cache 的分配和回收,同时虚拟内存管理系统(VMM)则允许应用程序和文件 Cache 之间通过 memory map的方式交换数据,FS Cache底层通过SLAB管理器来管理内存。

下图则非常清晰的描述了Cache所在的位置,磁盘与VFS之间的纽带。

2. Linux Cache的结构

在 Linux 中,文件 Cache 分为两层,一是 Page Cache,另一个 Buffer Cache,每一个 Page Cache 包含若干 Buffer Cache。内存管理系统和 VFS 只与 Page Cache 交互,内存管理系统负责维护每项 Page Cache 的分配和回收,同时在使用 memory map 方式访问时负责建立映射;VFS 负责 Page Cache 与用户空间的数据交换。而具体文件系统则一般只与 Buffer Cache 交互,它们负责在外围存储设备和 Buffer Cache 之间交换数据。读缓存以Page Cache为单位,每次读取若干个Page Cache,回写磁盘以Buffer Cache为单位,每次回写若干个Buffer Cache。 Page Cache、Buffer Cache、文件以及磁盘之间的关系如下图所示。

Page 结构和 buffer_head 数据结构的关系如下图所示。Page指向一组Buffer的头指针,Buffer的头指针指向磁盘块。在这两个图中,假定了 Page 的大小是 4K,磁盘块的大小是 1K。

在 Linux 内核中,文件的每个数据块最多只能对应一个 Page Cache 项,它通过两个数据结构来管理这些 Cache 项,一个是 Radix Tree,另一个是双向链表。Radix Tree 是一种搜索树,Linux 内核利用这个数据结构来通过文件内偏移快速定位 Cache 项,图 4 是 radix tree的一个示意图,该 radix tree 的分叉为4(22),树高为4,用来快速定位8位文件内偏移。Linux(2.6.7) 内核中的分叉为 64(26),树高为 6(64位系统)或者 11(32位系统),用来快速定位 32 位或者 64 位偏移,Radix tree 中的每一个到叶子节点的路径上的Key所拼接起来的字串都是一个地址,指向文件内相应偏移所对应的Cache项。

查看Page Cache的核心数据结构struct address_space就可以看到上述结构(略去了无关结构):

1
2
3
4
5
6
7
struct address_space  {
	struct inode             *host;              /* owner: inode, block_device */
	struct radix_tree_root      page_tree;         /* radix tree of all pages */
	unsigned long           nrpages;  /* number of total pages */
	struct address_space       *assoc_mapping;      /* ditto */
	......
} __attribute__((aligned(sizeof(long))));

下面是一个Radix Tree实例:

另一个数据结构是双向链表,Linux内核为每一片物理内存区域(zone) 维护active_list和inactive_list两个双向链表,这两个list主要用来实现物理内存的回收。这两个链表上除了文件Cache之 外,还包括其它匿名(Anonymous)内存,如进程堆栈等。

相关数据结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
truct page{
	struct list_head list;   //通过使用它进入下面的数据结构free_area_struct结构中的双向链队列
	struct address_space * mapping;   //用于内存交换的数据结构
	unsigned long index;//当页面进入交换文件后
	struct page *next_hash; //自身的指针,这样就可以链接成一个链表
	atomic t count; //用于页面交换的计数,若页面为空闲则为0,分配就赋值1,没建立或恢复一次映射就加1,断开映射就减一
	unsigned long flags;//反应页面各种状态,例如活跃,不活跃脏,不活跃干净,空闲
	struct list_head lru;
	unsigned long age; //表示页面寿命
	wait_queue_head_t wait;
	struct page ** pprev_hash;
	struct buffer_head * buffers;
	void * virtual
	struct zone_struct * zone; //指向所属的管理区
}
typedef struct free_area_struct {
	struct list_head free_list;   //linux 中通用的双向链队列
	unsigned int * map;
} free_area_t;
typedef struct zone_struct{
	spinlock_t        lock;
	unsigned long offset;  //表示该管理区在mem-map数组中,起始的页号
	unsigned long free pages;
	unsigned long inactive_clean_pages;
	unsigned long inactive_dirty_pages;
	unsigned pages_min, pages_low, pages_high;
	struct list_head inactive_clean_list;   //用于页面交换的队列,基于linux页面交换的机制。这里存贮的是不活动“干净”页面
	free_area_t free_area[MAX_ORDER]; //一组“空闲区间”队列,free_area_t定义在上面,其中空闲下标表示的是页面大小,例如:数组第一个元素0号,表示所有区间大小为2的 0次方的页面链接成的双向队列,1号表示所有2的1次方页面链接链接成的双向队列,2号表示所有2的2次方页面链接成的队列,其中要求是这些页面地址连续
	char * name;
	unsigned long size;
	struct pglist_data * zone_pgdat;   //用于指向它所属的存贮节点,及下面的数据结构
	unsigned  long  zone_start_paddr;
	unsigned  long    zone_start_mapnr;
	struct page * zone_mem_map;
} zone_t;

3. Cache预读与换出

Linux 内核中文件预读算法的具体过程是这样的: 对于每个文件的第一个读请求,系统读入所请求的页面并读入紧随其后的少数几个页面(不少于一个页面,通常是三个页 面),这时的预读称为同步预读。对于第二次读请求,如果所读页面不在Cache中,即不在前次预读的group中,则表明文件访问不是顺序访问,系统继续 采用同步预读;如果所读页面在Cache中,则表明前次预读命中,操作系统把预读group扩大一倍,并让底层文件系统读入group中剩下尚不在 Cache中的文件数据块,这时的预读称为异步预读。无论第二次读请求是否命中,系统都要更新当前预读group的大小。

此外,系统中定义了一个 window,它包括前一次预读的group和本次预读的group。任何接下来的读请求都会处于两种情况之一:

第一种情况是所请求的页面处于预读 window中,这时继续进行异步预读并更新相应的window和group;

第二种情况是所请求的页面处于预读window之外,这时系统就要进行同步 预读并重置相应的window和group。

下图是Linux内核预读机制的一个示意图,其中a是某次读操作之前的情况,b是读操作所请求页面不在 window中的情况,而c是读操作所请求页面在window中的情况。

Linux内核中文件Cache替换的具体过程是这样的:刚刚分配的Cache项链入到inactive_list头部,并将其状态设置为active,当内存不够需要回收Cache时,系统首先从尾部开始反向扫描 active_list并将状态不是referenced的项链入到inactive_list的头部,然后系统反向扫描inactive_list,如果所扫描的项的处于合适的状态就回收该项,直到回收了足够数目的Cache项。其中Active_list的含义是热访问数据,及多次被访问的,inactive_list是冷访问数据,表示尚未被访问的。如果数据被访问了,Page会被打上一个Refrence标记,如果Page没有被访问过,则打上Unrefrence标记。这些处理在swap.c中可以找到。 下图也描述了这个过程。

下面的代码描述了一个Page被访问它的标记为变化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * Mark a page as having seen activity.
 *
 * inactive,unreferenced        ->      inactive,referenced
 * inactive,referenced          ->      active,unreferenced
 * active,unreferenced          ->      active,referenced
 */
void mark_page_accessed(struct page *page)
{
	if (!PageActive(page) && !PageUnevictable(page) &&
			PageReferenced(page) && PageLRU(page)) {
		activate_page(page);
		ClearPageReferenced(page);
	} else if (!PageReferenced(page)) {
		SetPageReferenced(page);
	}
}

参考文章:

http://lsec.cc.ac.cn/~tengfei/doc/ldd3/

http://memorymyann.javaeye.com/blog/193061

http://www.cublog.cn/u/20047/showart.php?id=121850

http://blog.chinaunix.net/u2/74194/showart_1089736.html

关于内存管理,Linux有一个网页:http://linux-mm.org/

linux mmap 详解

http://blog.chinaunix.net/uid-20321537-id-3483405.html

一.前言

mmap的具体实现以前在学习内核时学习过,但是对于其中的很多函数是一知半解的,有些只能根据其函数名来猜测其具体的功能,在本文中,一起来重新深入理解其具体的实现。

二.mmap的用户层应用

1
void *mmap(void *start,size_t length,int prot,int flags,int fd,off_t offsize);

具体参数含义

start : 指向欲映射的内存起始地址,通常设为 NULL,代表让系统自动选定地址,映射成功后返回该地址。
length: 代表将文件中多大的部分映射到内存。
prot : 映射区域的保护方式。可以为以下几种方式的组合:
PROT_EXEC 映射区域可被执行
PROT_READ 映射区域可被读取
PROT_WRITE 映射区域可被写入
PROT_NONE 映射区域不能存取
flags : 影响映射区域的各种特性。在调用mmap()时必须要指定MAP_SHARED 或MAP_PRIVATE。
MAP_FIXED 如果参数start所指的地址无法成功建立映射时,则放弃映射,不对地址做修正。通常不鼓励用此旗标。
MAP_SHARED 对映射区域的写入数据会复制回文件内,而且允许其他映射该文件的进程共享。
MAP_PRIVATE 对映射区域的写入操作会产生一个映射文件的复制,即私人的“写入时复制”(copy on write)对此区域作的任何修改都不会写回原来的文件内容。
MAP_ANONYMOUS建立匿名映射。此时会忽略参数fd,不涉及文件,而且映射区域无法和其他进程共享。
MAP_DENYWRITE只允许对映射区域的写入操作,其他对文件直接写入的操作将会被拒绝。
MAP_LOCKED 将映射区域锁定住,这表示该区域不会被置换(swap)。
fd : 要映射到内存中的文件描述符。如果使用匿名内存映射时,即flags中设置了MAP_ANONYMOUS,fd设为-1。有些系统不支持匿名内存映射,则可以使用fopen打开/dev/zero文件,
然后对该文件进行映射,可以同样达到匿名内存映射的效果。
offset:文件映射的偏移量,通常设置为0,代表从文件最前方开始对应,offset必须是PAGE_SIZE的整数倍。

返回值:
若映射成功则返回映射区的内存起始地址,否则返回MAP_FAILED(-1),错误原因存于errno 中。

错误代码:
EBADF 参数fd 不是有效的文件描述词
EACCES 存取权限有误。如果是MAP_PRIVATE 情况下文件必须可读,使用MAP_SHARED则要有PROT_WRITE以及该文件要能写入。
EINVAL 参数start、length 或offset有一个不合法。
EAGAIN 文件被锁住,或是有太多内存被锁住。
ENOMEM 内存不足。

用户层的调用很简单,其具体功能就是直接将物理内存直接映射到用户虚拟内存,使用户空间可以直接对物理空间操作。但是对于内核层而言,其具体实现比较复杂。

三.mmap的内核实现

对于mmap的内核有了解的都会知道用户层的mmap到内核层的mmap其中多了一个参数vma_struct这个结构体,在开始时对于这个参数很疑惑就是这个参数的值是哪儿来的,在这里我们会一一来讲述。

mmap() —> sys_mmap_pgoff() 内核系统调用函数

munmap() —>sys_munmap() 内核系统调用函数,其最终调用unmap_region()来解除映射关系,不需要对应的file_operation有unmap操作项.

还是从do_mmap开始吧。

3.1 do_mmap

参数说明:
file :就是用户层想要映射的file
addr :欲映射的起始地址,即用户层的start
prot :用户层传入的port
flag :同上
offset:同上

从这里可以知道,这里面的参数几乎均是用户层传入的参数。

1
2
3
4
5
6
7
8
9
10
11
static inline unsigned long do_mmap(struct file *file, unsigned long addr,unsigned long len, unsigned long prot,
									unsigned long flag, unsigned long offset)
{
	unsigned long ret = -EINVAL;
	if ((offset + PAGE_ALIGN(len)) < offset)  --页对齐len,检测传入参数是否有误。
		goto out;
	if (!(offset & ~PAGE_MASK))           --检测offset是否页对齐。映射时只能映射页对齐的长度。
		ret = do_mmap_pgoff(file, addr, len, prot, flag, offset >> PAGE_SHIFT);
out:
	return ret;
}

3.2 do_mmap_pgoff

这个函数是巨大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
unsigned long do_mmap_pgoff(struct file * file, unsigned long addr,unsigned long len, unsigned long prot,unsigned long flags, unsigned long pgoff)
{
	struct mm_struct * mm = current->mm;      --当前用户进程的mm
	struct inode *inode;
	unsigned int vm_flags;
	int error;
	int accountable = 1;
	unsigned long reqprot = prot;

	if ((prot & PROT_READ) && (current->personality & READ_IMPLIES_EXEC))   --是否隐藏了可执行属性。
		if (!(file && (file->f_path.mnt->mnt_flags & MNT_NOEXEC)))
			prot |= PROT_EXEC;

	if (!len)
		return -EINVAL;

	if (!(flags & MAP_FIXED))              -
		addr = round_hint_to_min(addr);    --判断输入的欲映射的起始地址是否小于最小映射地址,如果小于,将addr修改为最小地址,不过前提是MAP_FIXED旗标没有设置。

	error = arch_mmap_check(addr, len, flags);   --不同平台对于mmap参数的不同检测。这里之间返回0
	if (error)
		return error;

	len = PAGE_ALIGN(len);        --检测len是否越界,len的范围在0~TASK_SIZE之间。
	if (!len || len > TASK_SIZE)
		return -ENOMEM;             --错误值为nomem

	if ((pgoff + (len >> PAGE_SHIFT)) < pgoff)  --再次检测是否越界。我们这里不得不小心哪个晕头了传入一个莫名其妙的值
	return -EOVERFLOW;

	if (mm->map_count > sysctl_max_map_count)   --在一个进程中对于mmap个数是有限制的。超出了还是nomem的错误。
		return -ENOMEM;

	addr = get_unmapped_area(file, addr, len, pgoff, flags);  --获取没有映射的地址,这个是查询mm中空闲的内存地址,这个在下面理解。
	if (addr & ~PAGE_MASK)
		return addr;

	vm_flags = calc_vm_prot_bits(prot) | calc_vm_flag_bits(flags) | mm->def_flags |
			   VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;      --设置vm_flags,根据传入的port和flags以及mm本身自有的旗标来设置。

	if (flags & MAP_LOCKED) {
		if (!can_do_mlock())
			return -EPERM;
		vm_flags |= VM_LOCKED;
	}

	if (vm_flags & VM_LOCKED) {
		unsigned long locked, lock_limit;
		locked = len >> PAGE_SHIFT;
		locked += mm->locked_vm;
		lock_limit = current->signal->rlim[RLIMIT_MEMLOCK].rlim_cur;
		lock_limit >>= PAGE_SHIFT;
		if (locked > lock_limit && !capable(CAP_IPC_LOCK))
			return -EAGAIN;
	}
	--关于锁定的内存区在以后学习中再看,这里就不细看。
	inode = file ? file->f_path.dentry->d_inode : NULL;  --判断是否匿名映射,如果不是则赋值inode

	if (file) {
		switch (flags & MAP_TYPE) {   --MAP_TYPE = 0x0F type的掩码
		case MAP_SHARED:
			if ((prot&PROT_WRITE) && !(file->f_mode&FMODE_WRITE))   --file应该被打开并允许写入。
				return -EACCES;
			if (IS_APPEND(inode) && (file->f_mode & FMODE_WRITE))  --不能写入一个只允许写追加的文件
				return -EACCES;
			if (locks_verify_locked(inode))      --确保文件没有被强制锁定。
				return -EAGAIN;

			vm_flags |= VM_SHARED | VM_MAYSHARE;  --尝试允许其他进程共享。
			if (!(file->f_mode & FMODE_WRITE))    --如果file不允许写就算了,共享也没有用啊,因为file就一直固定死了,共享也没有意义。
				vm_flags &= ~(VM_MAYWRITE | VM_SHARED);
		case MAP_PRIVATE:
			if (!(file->f_mode & FMODE_READ))
				return -EACCES;
			if (file->f_path.mnt->mnt_flags & MNT_NOEXEC) {
				if (vm_flags & VM_EXEC)
					return -EPERM;
				vm_flags &= ~VM_MAYEXEC;
			}
			if (is_file_hugepages(file))
				accountable = 0;

			if (!file->f_op || !file->f_op->mmap)
				return -ENODEV;
			break;

		default:
			return -EINVAL;
		}
	} else {
		switch (flags & MAP_TYPE) {
		case MAP_SHARED:
			pgoff = 0;
			vm_flags |= VM_SHARED | VM_MAYSHARE;
			break;
		case MAP_PRIVATE:
			pgoff = addr >> PAGE_SHIFT;
			break;
		default:
			return -EINVAL;
		}
	}
	--上面就是对一些旗标进行检测,防止出现旗标冲突,比如我欲映射的文件不允许写,而我映射的旗标却设定是可写并可以共享的,这个就冲突了。
	error = security_file_mmap(file, reqprot, prot, flags, addr, 0);   --这个函数就忽略了。
	if (error)
		return error;

	return mmap_region(file, addr, len, flags, vm_flags, pgoff,accountable);  --最后一个参数为是否为大页,如果是的就为0.其余的参数都好理解。
}

3.3 get_unmapped_area

这个是获取没有被映射的内存区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unsigned long get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,unsigned long pgoff, unsigned long flags)
{
	unsigned long (*get_area)(struct file *, unsigned long,unsigned long, unsigned long, unsigned long);
	get_area = current->mm->get_unmapped_area;
	if (file && file->f_op && file->f_op->get_unmapped_area)
		get_area = file->f_op->get_unmapped_area;
	addr = get_area(file, addr, len, pgoff, flags);
	if (IS_ERR_VALUE(addr))
		return addr;

	if (addr > TASK_SIZE - len)
		return -ENOMEM;
	if (addr & ~PAGE_MASK)
		return -EINVAL;

	return arch_rebalance_pgtables(addr, len);
}

对于get_area函数我们以arch_get_unmapped_area为例来看如何查找一个空闲的mmap area

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
unsigned long arch_get_unmapped_area(struct file *filp, unsigned long addr,unsigned long len, unsigned long pgoff, unsigned long flags)
{
	struct mm_struct *mm = current->mm;
	struct vm_area_struct *vma;
	unsigned long start_addr;

	if (len > TASK_SIZE)
		return -ENOMEM;

	if (flags & MAP_FIXED)    --还记否这个MAP_FIXED是什么含义不?
		return addr;

	if (addr) {
		addr = PAGE_ALIGN(addr);
		vma = find_vma(mm, addr); --vma为NULL即addr的地址不在任一个VMA(vma->vm_start~vma->vm_end) addr的地址没有被映射,
						而且空洞足够我们这次的映射,那么返回addr以准备这次的映射
		if (TASK_SIZE - len >= addr &&(!vma || addr + len <= vma->vm_start))
			return addr;
	}
	if (len > mm->cached_hole_size) { --如果所需的长度大于当前vma之间的空洞长度
			start_addr = addr = mm->free_area_cache;
	} else {
			start_addr = addr = TASK_UNMAPPED_BASE;  --需要的长度小于当前空洞,为了不至于时间浪费,那么从0开始搜寻,
					这里的搜寻基地址TASK_UNMAPPED_BASE很重要,用户mmap的地址的基地址必须在TASK_UNMAPPED_BASE之上,
					但是一定这样严格 吗?看上面的if (addr)判断,如果用户给了一个地址在TASK_UNMAPPED_BASE之下,
					映射实际上还是会发生的。
			mm->cached_hole_size = 0;
	}

full_search:
	for (vma = find_vma(mm, addr); ; vma = vma->vm_next) {
		if (TASK_SIZE - len < addr) {
			if (start_addr != TASK_UNMAPPED_BASE) {
				addr = TASK_UNMAPPED_BASE;
			  start_addr = addr;
				mm->cached_hole_size = 0;
				goto full_search;
			}
			return -ENOMEM;
		}
	
		if (!vma || addr + len <= vma->vm_start) {        --如果第一次find_vma返回值即为NULL ,vma没有被映射并且空洞足够映射
						!vma的条件只有可能在循环的第一次满足,在其后不可能满足,在其后的判断条件即为
						vma->vma_end~vma->vma_next->vma_start之间的空洞大小大于所需要映射的长度即可,
						下面判断条件中的addr为vma->vma_end,而vma->vm_start为 vma->vma_next->vma_start
			mm->free_area_cache = addr + len;
			return addr;
		}
		if (addr + mm->cached_hole_size < vma->vm_start)  --在循环的第一次如果vma不为NULL,不会满足下面的条件,在以后循环中mm->cached_hole_size
						则为该次vma->vm_start 与上一次的vma->vm_end之间的差值

				mm->cached_hole_size = vma->vm_start - addr;
		addr = vma->vm_end;
	}
}

还记否以前看的红黑树,这里就现实的用了红黑树的算法。关于这个我们就不看了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr)
{
	struct vm_area_struct *vma = NULL;

	if (mm) {
		vma = mm->mmap_cache;
		if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
			struct rb_node * rb_node;
			rb_node = mm->mm_rb.rb_node;
			vma = NULL;
			while (rb_node) {
				struct vm_area_struct * vma_tmp;

				vma_tmp = rb_entry(rb_node,struct vm_area_struct, vm_rb);
				if (vma_tmp->vm_end > addr) {
					vma = vma_tmp;
					if (vma_tmp->vm_start <= addr)
						break;
					rb_node = rb_node->rb_left;
				} else
					rb_node = rb_node->rb_right;
			}
			if (vma)
				mm->mmap_cache = vma;
		}
	}
	return vma;
}

3.4 mmap_region

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
unsigned long mmap_region(struct file *file, unsigned long addr,unsigned long len, unsigned long flags,
				unsigned int vm_flags, unsigned long pgoff,int accountable)
{
	struct mm_struct *mm = current->mm;
	struct vm_area_struct *vma, *prev;
	struct vm_area_struct *merged_vma;
	int correct_wcount = 0;
	int error;
	struct rb_node **rb_link, *rb_parent;
	unsigned long charged = 0;
	struct inode *inode =  file ? file->f_path.dentry->d_inode : NULL;

	/* Clear old maps */
	error = -ENOMEM;
munmap_back:
	vma = find_vma_prepare(mm, addr, &prev, &rb_link, &rb_parent); --函数find_vma_prepare()与find_vma()基本相同,它扫描当前进程地址空间的vm_area_struct
						结构所形成的红黑树,试图找到结束地址高于addr的第一个区间;如果找到了一个虚拟区,
						说明addr所在的虚拟区已经在使用,也就是已经有映射存在,因此要调用do_munmap()
						把这个老的虚拟区从进程地址空间中撤销,如果撤销不成功,就返回一个负数;
						如果撤销成功,就继续查找,直到在红黑树中找不到addr所在的虚拟区
	if (vma && vma->vm_start < addr + len) {
		if (do_munmap(mm, addr, len))
			return -ENOMEM;
		goto munmap_back;
	}
	if (!may_expand_vm(mm, len >> PAGE_SHIFT))                   -- 页数和超过限定值返回 0 ,不超过返回1
		return -ENOMEM;

	if (flags & MAP_NORESERVE)              -- 如果flags参数中没有设置MAP_NORESERVE标志,新的虚拟区含有私有的可写页,空闲页面数小于要映射的虚拟区
						的大小;则函数终止并返回一个负数;其中函数security_vm_enough_memory()用来检查一个
						进程的地址空间中是否有足够的内存来进行一个新的映射
		vm_flags |= VM_NORESERVE;

	if (accountable && (!(flags & MAP_NORESERVE) ||
				sysctl_overcommit_memory == OVERCOMMIT_NEVER)) {
		if (vm_flags & VM_SHARED) {
			/* Check memory availability in shmem_file_setup? */
			vm_flags |= VM_ACCOUNT;
		} else if (vm_flags & VM_WRITE) {
			charged = len >> PAGE_SHIFT;
			if (security_vm_enough_memory(charged))
				return -ENOMEM;
			vm_flags |= VM_ACCOUNT;
		}
	}
	if (!file && !(vm_flags & VM_SHARED)) { --如果是匿名映射(file为空),并且这个虚拟区是非共享的,则可以把这个虚拟区和与它紧挨的前一个虚拟区进行合并;
		虚拟区的合并是由vma_merge()函数实现的。如果合并成功,则转out处,请看后面out处的代码。
		vma = vma_merge(mm, prev, addr, addr + len, vm_flags,
					NULL, NULL, pgoff, NULL);
		if (vma)
			goto out;
	}
	vma = kmem_cache_zalloc(vm_area_cachep, GFP_KERNEL);
	if (!vma) {
		error = -ENOMEM;
		goto unacct_error;
	}

	vma->vm_mm = mm;
	vma->vm_start = addr;
	vma->vm_end = addr + len;
	vma->vm_flags = vm_flags;
	vma->vm_page_prot = vm_get_page_prot(vm_flags);
	vma->vm_pgoff = pgoff;

	if (file) {
		error = -EINVAL;
		if (vm_flags & (VM_GROWSDOWN|VM_GROWSUP))
			goto free_vma;
		if (vm_flags & VM_DENYWRITE) {
			error = deny_write_access(file);
			if (error)
				goto free_vma;
			correct_wcount = 1;
		}
		vma->vm_file = file;
		get_file(file);
		error = file->f_op->mmap(file, vma);    -- (⊙o⊙)哦 ,终于可以调用设备文件中真正的mmap
		if (error)
			goto unmap_and_free_vma;
		if (vm_flags & VM_EXECUTABLE)
			added_exe_file_vma(mm);
	} else if (vm_flags & VM_SHARED) {
		error = shmem_zero_setup(vma);// it will call shmem_file_setup(), the same way as called in ashmem.c
		if (error)
			goto free_vma;
	}

如果建立的是从文件到虚存区间的映射,则:

1.当参数flags中的VM_GROWSDOWN或VM_GROWSUP标志位为1时,说明这个区间可以向低地址或高地址扩展,但从文件映射的区间不能进行扩展,因此转到free_vma,释放给vm_area_struct分配的Slab,并返回一个错误;

2.当flags中的VM_DENYWRITE标志位为1时,就表示不允许通过常规的文件操作访问该文件,所以要调用deny_write_access()排斥常规的文件操作(参见第八章)。

3.get_file()函数的主要作用是递增file结构中的共享计数;

4.每个文件系统都有个fiel_operation数据结构,其中的函数指针mmap提供了用来建立从该类文件到虚存区间进行映射的操作,这是最具有实质意义的函数;对于大部分文件系统,这个函数为generic_file_mmap( )函数实现的,该函数执行以下操作:

(1)初始化vm_area_struct结构中的vm_ops域。如果VM_SHARED标志为1,就把该域设置成file_shared_mmap, 否则就把该域设置成file_private_mmap。从某种意义上说,这个步骤所做的事情类似于打开一个文件并初始化文件对象的方法。

(2)从索引节点的i_mode域(参见第八章)检查要映射的文件是否是一个常规文件。如果是其他类型的文件(例如目录或套接字),就返回一个错误代码。

(3)从索引节点的i_op域中检查是否定义了readpage( )的索引节点操作。如果没有定义,就返回一个错误代码。

(4)调用update_atime( )函数把当前时间存放在该文件索引节点的i_atime域中,并将这个索引节点标记成脏。

5.如果flags参数中的MAP_SHARED标志位为1,则调用shmem_zero_setup()进行共享内存的映射。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
	if ((vm_flags & (VM_SHARED|VM_ACCOUNT)) == (VM_SHARED|VM_ACCOUNT))
		vma->vm_flags &= ~VM_ACCOUNT;

	addr = vma->vm_start;
	pgoff = vma->vm_pgoff;
	vm_flags = vma->vm_flags;

	if (vma_wants_writenotify(vma))
		vma->vm_page_prot = vm_get_page_prot(vm_flags & ~VM_SHARED);

	merged_vma = NULL;
	if (file)
		merged_vma = vma_merge(mm, prev, addr, vma->vm_end,
			vma->vm_flags, NULL, file, pgoff, vma_policy(vma));
	if (merged_vma) {
		mpol_put(vma_policy(vma));
		kmem_cache_free(vm_area_cachep, vma);
		fput(file);
		if (vm_flags & VM_EXECUTABLE)
			removed_exe_file_vma(mm);
		vma = merged_vma;
	} else {
		vma_link(mm, vma, prev, rb_link, rb_parent);
		file = vma->vm_file;
	}

此时,把新建的虚拟区插入到进程的地址空间,这是由函数vma_link()完成的,该函数具有三方面的功能:
(1)把vma 插入到虚拟区链表中
(2)把vma插入到虚拟区形成的红黑树中
(3)把vam插入到索引节点(inode)共享链表中

函数atomic_inc(x)给*x加1,这是一个原子操作。在内核代码中,有很多地方调用了以atomic为前缀的函数。原子操作,在操作过程中不会被中断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
	if (correct_wcount)
		atomic_inc(&inode->i_writecount);
out:
	mm->total_vm += len >> PAGE_SHIFT;
	vm_stat_account(mm, vm_flags, file, len >> PAGE_SHIFT);
	if (vm_flags & VM_LOCKED) {
		long nr_pages = mlock_vma_pages_range(vma, addr, addr + len);
		if (nr_pages < 0)
			return nr_pages;    /* vma gone! */
		mm->locked_vm += (len >> PAGE_SHIFT) - nr_pages;
	} else if ((flags & MAP_POPULATE) && !(flags & MAP_NONBLOCK))
		make_pages_present(addr, addr + len);
	return addr;

unmap_and_free_vma:
	if (correct_wcount)
		atomic_inc(&inode->i_writecount);
	vma->vm_file = NULL;
	fput(file);

	unmap_region(mm, vma, prev, vma->vm_start, vma->vm_end);
	charged = 0;
free_vma:
	kmem_cache_free(vm_area_cachep, vma);
unacct_error:
	if (charged)
		vm_unacct_memory(charged);
	return error;
}

ok!到此mmap的内核核心就可以了,关于具体的mmap的实现,以后再看。

四.总结

mmap的实质是什么,其实就是从每一个进程中的用户空间分配一段空间用于映射。 这里面的机关重重,需要好好理解,不过谨记一点,进程的vma_struct是采用了红黑树来管理的。对于每一段的内存区都会有一个vma_struct 来描述,比如数据区,code区等等,以及mmap所需要的一段内存区。

五.其它

1、特点:

① 进程相关的
② 与XSI共享内存一样,需要与同步原语一起使用
③ 只能是有共同祖先的进程才能使用

2、使用

系统调用mmap()用于共享内存的两种方式:
(1)使用普通文件提供的内存映射:
适用于任何进程之间。此时,需要打开或创建一个文件,然后再调用mmap()

典型调用代码如下:

1
2
fd=open(name, flag, mode); if(fd<0) ...
ptr=mmap(NULL, len , PROT_READ|PROT_WRITE, MAP_SHARED , fd , 0);

通过mmap()实现共享内存的通信方式有许多特点和要注意的地方,可以参看UNIX网络编程第二卷。【3】

(2)使用特殊文件提供匿名内存映射:
适用于具有亲缘关系的进程之间。由于父子进程特殊的亲缘关系,在父进程中先调用mmap(),然后调用fork()。那么在调用fork()之后,子进程 继承父进程匿名映射后的地址空间,同样也继承mmap()返回的地址,这样,父子进程就可以通过映射区域进行通信了。一般来说,子进程单独维护从父进程继 承下来的一些变量。而mmap()返回的地址,却由父子进程共同维护。对于具有亲缘关系的进程实现共享内存最好的方式应该是采用匿名内存映射的方式。此时,不必指定具体的文件,只要设置相应的标志即可。

3、说明

(1)
1
void *mmap(void *addr, size_t len, int prot, int flag, int fd, off_t offset );

把文件或设备映射或解除映射到内存中

0)flag:必须有MAP_SHARED 标志
MAP_SHARED对映射区域的写入数据会复制回文件内,而且允许其他映射该文件的进程共享。
MAP_PRIVATE 对映射区域的写入操作会产生一个映射文件的复制,即私人的“写入时复制”(copy on write)对此区域作的任何修改都不会写回原来的文件内容。
MAP_ANONYMOUS建立匿名共享。此时会忽略参数fd(fd可以指定为-1),不涉及文件,而且映射区域无法和其他进程共享(只能用于具有亲缘关系的进程间通信)。
映射/dev/zero可为调用程序提供零填充的虚拟内存块。

1)start:指向欲映射的内存起始地址,通常设为 NULL,代表让系统自动选定地址,映射成功后返回该地址。

2)length:代表将文件中多大的部分映射到内存。

3)offset 必须是页面大小的整数倍。页面大小由 getpagesize(2)得到。

4)被映射的文件大小应是页面大小的整数倍。如一个文件大小不是页面大小的整数倍,映射时多出来的区域将被赋为0,对这些区域的写不会被写回到文件中。

5)munmap()系统调用将删除指定地址范围内的映射区域。随后对这个范围内区域的引用将产生非法的内存引用。当这个进程终止后,这个区域也会被删除。另一方面,关闭文件描述符并不会删除映射区域。

6)fd:要映射到内存中的文件描述符。如果使用匿名内存映射时,即flags中设置了MAP_ANONYMOUS,fd设为-1。有些系统不支持匿名内存映射,则可以使用fopen打开/dev/zero文件,然后对该文件进行映射,可以同样达到匿名内存映射的效果。

7)若映射成功则返回映射区的内存起始地址,否则返回MAP_FAILED(-1)。

(2) munmap
1
int munmap( void * addr, size_t len )

在进程地址空间中解除一个映射关系,当映射关系解除后,对原来映射地址的访问将导致段错误发生。

void * addr :调用mmap()时返回的地址
size_t len :映射区的大小

(3)
1
int msync ( void * addr , size_t len, int flags)

一般说来,进程在映射空间的对共享内容的改变并不直接写回到磁盘文件中,往往在调用munmap()后才执行该操作。可以调用msync()实现磁盘上文件与共享内存区的内容一致。

void * addr :调用mmap()时返回的地址
size_t len :映射区的大小
int flags :MS_ASYN: 异步写,MS_SYN : 同步写,MS_INVALIDAT : 无效的cache 数据。

5、其他

1)进程调用mmap()时,只是在进程空间内新增了一块相应大小的缓冲区,并设置了相应的访问标识,但并没有建立进程空间到物理页面的映射。因此,第一次访问该空间时,会引发一个缺页异常。

2)一个共享内存区域可以看作是特殊文件系统shm中的一个文件,shm的安装点在交换区上。

3)mmap()系统调用使得进程之间通过映射同一个普通文件实现共享内存。普通文件被映射到进程地址空间后,进程可以向访问普通内存一样对文件进行访问,不必再调用read(),write()等操作。

4)最终被映射文件的内容的长度不会超过文件本身的初始大小,即映射不能改变文件的大小。文件被映射部分而不是整个文件决定了进程能够访问的空间大小,另外,如果指定文件的偏移部分,一定要注意为页面大小的整数倍。

linux进程地址空间--vma的基本操作

http://blog.csdn.net/vanbreaker/article/details/7855007

在32位的系统上,线性地址空间可达到4GB,这4GB一般按照3:1的比例进行分配,也就是说用户进程享有前3GB线性地址空间,而内核独享最后1GB线性地址空间。由于虚拟内存的引入,每个进程都可拥有3GB的虚拟内存,并且用户进程之间的地址空间是互不可见、互不影响的,也就是说即使两个进程对同一个地址进行操作,也不会产生问题。在前面介绍的一些分配内存的途径中,无论是伙伴系统中分配页的函数,还是slab分配器中分配对象的函数,它们都会尽量快速地响应内核的分配请求,将相应的内存提交给内核使用,而内核对待用户空间显然不能如此。用户空间动态申请内存时往往只是获得一块线性地址的使用权,而并没有将这块线性地址区域与实际的物理内存对应上,只有当用户空间真正操作申请的内存时,才会触发一次缺页异常,这时内核才会分配实际的物理内存给用户空间。

用户进程的虚拟地址空间包含了若干区域,这些区域的分布方式是特定于体系结构的,不过所有的方式都包含下列成分:

可执行文件的二进制代码,也就是程序的代码段
存储全局变量的数据段
用于保存局部变量和实现函数调用的栈
环境变量和命令行参数
程序使用的动态库的代码
用于映射文件内容的区域

由此可以看到进程的虚拟内存空间会被分成不同的若干区域,每个区域都有其相关的属性和用途,一个合法的地址总是落在某个区域当中的,这些区域也不会重叠。在linux内核中,这样的区域被称之为虚拟内存区域(virtual memory areas),简称vma。一个vma就是一块连续的线性地址空间的抽象,它拥有自身的权限(可读,可写,可执行等等) ,每一个虚拟内存区域都由一个相关的struct vm_area_struct结构来描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct vm_area_struct {
	struct mm_struct * vm_mm;   /* 所属的内存描述符 */
	unsigned long vm_start;    /* vma的起始地址 */
	unsigned long vm_end;       /* vma的结束地址 */

	/* 该vma的在一个进程的vma链表中的前驱vma和后驱vma指针,链表中的vma都是按地址来排序的*/
	struct vm_area_struct *vm_next, *vm_prev;

	pgprot_t vm_page_prot;      /* vma的访问权限 */
	unsigned long vm_flags;    /* 标识集 */

	struct rb_node vm_rb;      /* 红黑树中对应的节点 */

	/*
	 * For areas with an address space and backing store,
	 * linkage into the address_space->i_mmap prio tree, or
	 * linkage to the list of like vmas hanging off its node, or
	 * linkage of vma in the address_space->i_mmap_nonlinear list.
	 */
	/* shared联合体用于和address space关联 */
	union {
		struct {
			struct list_head list;/* 用于链入非线性映射的链表 */
			void *parent;   /* aligns with prio_tree_node parent */
			struct vm_area_struct *head;
		} vm_set;

		struct raw_prio_tree_node prio_tree_node;/*线性映射则链入i_mmap优先树*/
	} shared;

	/*
	 * A file's MAP_PRIVATE vma can be in both i_mmap tree and anon_vma
	 * list, after a COW of one of the file pages.  A MAP_SHARED vma
	 * can only be in the i_mmap tree.  An anonymous MAP_PRIVATE, stack
	 * or brk vma (with NULL file) can only be in an anon_vma list.
	 */
	/*anno_vma_node和annon_vma用于管理源自匿名映射的共享页*/
	struct list_head anon_vma_node; /* Serialized by anon_vma->lock */
	struct anon_vma *anon_vma;  /* Serialized by page_table_lock */

	/* Function pointers to deal with this struct. */
	/*该vma上的各种标准操作函数指针集*/
	const struct vm_operations_struct *vm_ops;

	/* Information about our backing store: */
	unsigned long vm_pgoff;     /* 映射文件的偏移量,以PAGE_SIZE为单位 */
	struct file * vm_file;          /* 映射的文件,没有则为NULL */
	void * vm_private_data;     /* was vm_pte (shared mem) */
	unsigned long vm_truncate_count;/* truncate_count or restart_addr */

#ifndef CONFIG_MMU
	struct vm_region *vm_region;    /* NOMMU mapping region */
#endif
#ifdef CONFIG_NUMA
	struct mempolicy *vm_policy;    /* NUMA policy for the VMA */
#endif
};

进程的若干个vma区域都得按一定的形式组织在一起,这些vma都包含在进程的内存描述符中,也就是struct mm_struct中,这些vma在mm_struct以两种方式进行组织,一种是链表方式,对应于mm_struct中的mmap链表头,一种是红黑树方式,对应于mm_struct中的mm_rb根节点,和内核其他地方一样,链表用于遍历,红黑树用于查找。

下面以文件映射为例,来阐述文件的address_space和与其建立映射关系的vma是如何联系上的。首先来看看struct address_space中与vma相关的变量

1
2
3
4
5
6
7
struct address_space {
	struct inode        *host;      /* owner: inode, block_device */
	...
	struct prio_tree_root   i_mmap;     /* tree of private and shared mappings */
	struct list_head    i_mmap_nonlinear;          /*list VM_NONLINEAR mappings */
	...
} __attr

与此同时,struct file和struct inode中都包含有一个struct address_space的指针,分别为f_mapping和i_mapping。struct file是一个特定于进程的数据结构,而struct inode则是一个特定于文件的数据结构。每当进程打开一个文件时,都会将file->f_mapping设置到inode->i_mapping,下图则给出了文件和与其建立映射关系的vma的联系

下面来看几个vma的基本操作函数,这些函数都是后面实现具体功能的基础

find_vma()用来寻找一个针对于指定地址的vma,该vma要么包含了指定的地址,要么位于该地址之后并且离该地址最近,或者说寻找第一个满足addr<vma_end的vma

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
	struct vm_area_struct *vma = NULL;

	if (mm) {
		/* Check the cache first. */
		/* (Cache hit rate is typically around 35%.) */
		vma = mm->mmap_cache; //首先尝试mmap_cache中缓存的vma
		/*如果不满足下列条件中的任意一个则从红黑树中查找合适的vma
		  1.缓存vma不存在
		  2.缓存vma的结束地址小于给定的地址
		  3.缓存vma的起始地址大于给定的地址*/
		if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
			struct rb_node * rb_node;

			rb_node = mm->mm_rb.rb_node;//获取红黑树根节点
			vma = NULL;

			while (rb_node) {
				struct vm_area_struct * vma_tmp;

				vma_tmp = rb_entry(rb_node,   //获取节点对应的vma
						struct vm_area_struct, vm_rb);

				/*首先确定vma的结束地址是否大于给定地址,如果是的话,再确定
				  vma的起始地址是否小于给定地址,也就是优先保证给定的地址是
				  处于vma的范围之内的,如果无法保证这点,则只能找到一个距离
				  给定地址最近的vma并且该vma的结束地址要大于给定地址*/
				if (vma_tmp->vm_end > addr) {
					vma = vma_tmp;
					if (vma_tmp->vm_start <= addr)
						break;
					rb_node = rb_node->rb_left;
				} else
					rb_node = rb_node->rb_right;
			}
			if (vma)
				mm->mmap_cache = vma;//将结果保存在缓存中
		}
	}
	return vma;
}

当一个新区域被加到进程的地址空间时,内核会检查它是否可以与一个或多个现存区域合并,vma_merge()函数在可能的情况下,将一个新区域与周边区域进行合并。参数:

mm:新区域所属的进程地址空间
prev:在地址上紧接着新区域的前面一个vma
addr:新区域的起始地址
end:新区域的结束地址
vm_flags:新区域的标识集
anon_vma:新区域所属的匿名映射
file:新区域映射的文件
pgoff:新区域映射文件的偏移
policy:和NUMA相关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
struct vm_area_struct *vma_merge(struct mm_struct *mm,
			struct vm_area_struct *prev, unsigned long addr,
			unsigned long end, unsigned long vm_flags,
			struct anon_vma *anon_vma, struct file *file,
			pgoff_t pgoff, struct mempolicy *policy)
{
	pgoff_t pglen = (end - addr) >> PAGE_SHIFT;
	struct vm_area_struct *area, *next;

	/*
	 * We later require that vma->vm_flags == vm_flags,
	 * so this tests vma->vm_flags & VM_SPECIAL, too.
	 */
	if (vm_flags & VM_SPECIAL)
		return NULL;

	if (prev)//指定了先驱vma,则获取先驱vma的后驱vma
		next = prev->vm_next;
	else     //否则指定mm的vma链表中的第一个元素为后驱vma
		next = mm->mmap;
	area = next;

	/*后驱节点存在,并且后驱vma的结束地址和给定区域的结束地址相同,
	  也就是说两者有重叠,那么调整后驱vma*/
	if (next && next->vm_end == end)     /* cases 6, 7, 8 */
		next = next->vm_next;

	/*
	 * 先判断给定的区域能否和前驱vma进行合并,需要判断如下的几个方面:
	   1.前驱vma必须存在
	   2.前驱vma的结束地址正好等于给定区域的起始地址
	   3.两者的struct mempolicy中的相关属性要相同,这项检查只对NUMA架构有意义
	   4.其他相关项必须匹配,包括两者的vm_flags,是否映射同一个文件等等
	 */
	if (prev && prev->vm_end == addr &&
			mpol_equal(vma_policy(prev), policy) &&
			can_vma_merge_after(prev, vm_flags,
						anon_vma, file, pgoff)) {
		/*
		 *确定可以和前驱vma合并后再判断是否能和后驱vma合并,判断方式和前面一样,
		  不过这里多了一项检查,在给定区域能和前驱、后驱vma合并的情况下还要检查
		  前驱、后驱vma的匿名映射可以合并
		 */
		if (next && end == next->vm_start &&
				mpol_equal(policy, vma_policy(next)) &&
				can_vma_merge_before(next, vm_flags,
					anon_vma, file, pgoff+pglen) &&
				is_mergeable_anon_vma(prev->anon_vma,
							  next->anon_vma)) {
							/* cases 1, 6 */
			vma_adjust(prev, prev->vm_start,
				next->vm_end, prev->vm_pgoff, NULL);
		} else                  /* cases 2, 5, 7 */
			vma_adjust(prev, prev->vm_start,
				end, prev->vm_pgoff, NULL);
		return prev;
	}

	/*
	 * Can this new request be merged in front of next?
	 */
	 /*如果前面的步骤失败,那么则从后驱vma开始进行和上面类似的步骤*/
	if (next && end == next->vm_start &&
			mpol_equal(policy, vma_policy(next)) &&
			can_vma_merge_before(next, vm_flags,
					anon_vma, file, pgoff+pglen)) {
		if (prev && addr < prev->vm_end)  /* case 4 */
			vma_adjust(prev, prev->vm_start,
				addr, prev->vm_pgoff, NULL);
		else                    /* cases 3, 8 */
			vma_adjust(area, addr, next->vm_end,
				next->vm_pgoff - pglen, NULL);
		return area;
	}

	return NULL;
}

vma_adjust会执行具体的合并调整操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
void vma_adjust(struct vm_area_struct *vma, unsigned long start,
	unsigned long end, pgoff_t pgoff, struct vm_area_struct *insert)
{
	struct mm_struct *mm = vma->vm_mm;
	struct vm_area_struct *next = vma->vm_next;
	struct vm_area_struct *importer = NULL;
	struct address_space *mapping = NULL;
	struct prio_tree_root *root = NULL;
	struct file *file = vma->vm_file;
	struct anon_vma *anon_vma = NULL;
	long adjust_next = 0;
	int remove_next = 0;

	if (next && !insert) {
		/*指定的范围已经跨越了整个后驱vma,并且有可能超过后驱vma*/
		if (end >= next->vm_end) {
			/*
			 * vma expands, overlapping all the next, and
			 * perhaps the one after too (mprotect case 6).
			 */
again:          remove_next = 1 + (end > next->vm_end);//确定是否超过了后驱vma
			end = next->vm_end;
			anon_vma = next->anon_vma;
			importer = vma;
		} else if (end > next->vm_start) {/*指定的区域和后驱vma部分重合*/

			/*
			 * vma expands, overlapping part of the next:
			 * mprotect case 5 shifting the boundary up.
			 */
			adjust_next = (end - next->vm_start) >> PAGE_SHIFT;
			anon_vma = next->anon_vma;
			importer = vma;
		} else if (end < vma->vm_end) {/*指定的区域没到达后驱vma的结束处*/
			/*
			 * vma shrinks, and !insert tells it's not
			 * split_vma inserting another: so it must be
			 * mprotect case 4 shifting the boundary down.
			 */
			adjust_next = - ((vma->vm_end - end) >> PAGE_SHIFT);
			anon_vma = next->anon_vma;
			importer = next;
		}
	}

	if (file) {//如果有映射文件
		mapping = file->f_mapping;//获取文件对应的address_space
		if (!(vma->vm_flags & VM_NONLINEAR))
			root = &mapping->i_mmap;
		spin_lock(&mapping->i_mmap_lock);
		if (importer &&
			vma->vm_truncate_count != next->vm_truncate_count) {
			/*
			 * unmap_mapping_range might be in progress:
			 * ensure that the expanding vma is rescanned.
			 */
			importer->vm_truncate_count = 0;
		}
		/*如果指定了待插入的vma,则根据vma是否以非线性的方式映射文件来选择是将
		vma插入file对应的address_space的优先树(对应线性映射)还是双向链表(非线性映射)*/
		if (insert) {
			insert->vm_truncate_count = vma->vm_truncate_count;
			/*
			 * Put into prio_tree now, so instantiated pages
			 * are visible to arm/parisc __flush_dcache_page
			 * throughout; but we cannot insert into address
			 * space until vma start or end is updated.
			 */
			__vma_link_file(insert);
		}
	}

	/*
	 * When changing only vma->vm_end, we don't really need
	 * anon_vma lock.
	 */
	if (vma->anon_vma && (insert || importer || start != vma->vm_start))
		anon_vma = vma->anon_vma;
	if (anon_vma) {
		spin_lock(&anon_vma->lock);
		/*
		 * Easily overlooked: when mprotect shifts the boundary,
		 * make sure the expanding vma has anon_vma set if the
		 * shrinking vma had, to cover any anon pages imported.
		 */
		if (importer && !importer->anon_vma) {
			importer->anon_vma = anon_vma;
			__anon_vma_link(importer);//将importer插入importer的anon_vma匿名映射链表中
		}
	}

	if (root) {
		flush_dcache_mmap_lock(mapping);
		vma_prio_tree_remove(vma, root);
		if (adjust_next)
			vma_prio_tree_remove(next, root);
	}

	/*调整vma的相关量*/
	vma->vm_start = start;
	vma->vm_end = end;
	vma->vm_pgoff = pgoff;
	if (adjust_next) {//调整后驱vma的相关量
		next->vm_start += adjust_next << PAGE_SHIFT;
		next->vm_pgoff += adjust_next;
	}

	if (root) {
		if (adjust_next)//如果后驱vma被调整了,则重新插入到优先树中
			vma_prio_tree_insert(next, root);
		vma_prio_tree_insert(vma, root);//将vma插入到优先树中
		flush_dcache_mmap_unlock(mapping);
	}

	if (remove_next) {//给定区域与后驱vma有重合
		/*
		 * vma_merge has merged next into vma, and needs
		 * us to remove next before dropping the locks.
		 */
		__vma_unlink(mm, next, vma);//将后驱vma从红黑树中删除
		if (file)//将后驱vma从文件对应的address space中删除
			__remove_shared_vm_struct(next, file, mapping);
		if (next->anon_vma)//将后驱vma从匿名映射链表中删除
			__anon_vma_merge(vma, next);
	} else if (insert) {
		/*
		 * split_vma has split insert from vma, and needs
		 * us to insert it before dropping the locks
		 * (it may either follow vma or precede it).
		 */
		__insert_vm_struct(mm, insert);//将待插入的vma插入mm的红黑树,双向链表以及
						//匿名映射链表
	}

	if (anon_vma)
		spin_unlock(&anon_vma->lock);
	if (mapping)
		spin_unlock(&mapping->i_mmap_lock);

	if (remove_next) {
		if (file) {
			fput(file);
			if (next->vm_flags & VM_EXECUTABLE)
				removed_exe_file_vma(mm);
		}
		mm->map_count--;
		mpol_put(vma_policy(next));
		kmem_cache_free(vm_area_cachep, next);
		/*
		 * In mprotect's case 6 (see comments on vma_merge),
		 * we must remove another next too. It would clutter
		 * up the code too much to do both in one go.
		 */
		if (remove_next == 2) {//还有待删除的区域
			next = vma->vm_next;
			goto again;
		}
	}

	validate_mm(mm);
}

insert_vm_struct()函数用于插入一块新区域

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int insert_vm_struct(struct mm_struct * mm, struct vm_area_struct * vma)
{
	struct vm_area_struct * __vma, * prev;
	struct rb_node ** rb_link, * rb_parent;

	/*
	 * The vm_pgoff of a purely anonymous vma should be irrelevant
	 * until its first write fault, when page's anon_vma and index
	 * are set.  But now set the vm_pgoff it will almost certainly
	 * end up with (unless mremap moves it elsewhere before that
	 * first wfault), so /proc/pid/maps tells a consistent story.
	 *
	 * By setting it to reflect the virtual start address of the
	 * vma, merges and splits can happen in a seamless way, just
	 * using the existing file pgoff checks and manipulations.
	 * Similarly in do_mmap_pgoff and in do_brk.
	 */
	if (!vma->vm_file) {
		BUG_ON(vma->anon_vma);
		vma->vm_pgoff = vma->vm_start >> PAGE_SHIFT;
	}
	/*__vma用来保存和vma->start对应的vma(与find_vma()一样),同时获取以下信息:
	  1.prev用来保存对应的前驱vma
	  2.rb_link保存该vma区域插入对应的红黑树节点
	  3.rb_parent保存该vma区域对应的父节点*/
	__vma = find_vma_prepare(mm,vma->vm_start,&prev,&rb_link,&rb_parent);
	if (__vma && __vma->vm_start < vma->vm_end)
		return -ENOMEM;
	if ((vma->vm_flags & VM_ACCOUNT) &&
		 security_vm_enough_memory_mm(mm, vma_pages(vma)))
		return -ENOMEM;
	vma_link(mm, vma, prev, rb_link, rb_parent);//将vma关联到所有的数据结构中
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
			struct vm_area_struct *prev, struct rb_node **rb_link,
			struct rb_node *rb_parent)
{
	struct address_space *mapping = NULL;

	if (vma->vm_file)//如果存在文件映射则获取文件对应的地址空间
		mapping = vma->vm_file->f_mapping;

	if (mapping) {
		spin_lock(&mapping->i_mmap_lock);
		vma->vm_truncate_count = mapping->truncate_count;
	}
	anon_vma_lock(vma);

	/*将vma插入到相应的数据结构中--双向链表,红黑树和匿名映射链表*/
	__vma_link(mm, vma, prev, rb_link, rb_parent);
	__vma_link_file(vma);//将vma插入到文件地址空间的相应数据结构中

	anon_vma_unlock(vma);
	if (mapping)
		spin_unlock(&mapping->i_mmap_lock);

	mm->map_count++;
	validate_mm(mm);
}

在创建新的vma区域之前先要寻找一块足够大小的空闲区域,该项工作由get_unmapped_area()函数完成,而实际的工作将会由mm_struct中定义的辅助函数来完成。根据进程虚拟地址空间的布局,会选择使用不同的映射函数,在这里考虑大多数系统上采用的标准函数arch_get_unmapped_area();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
unsigned long
arch_get_unmapped_area(struct file *filp, unsigned long addr,
		unsigned long len, unsigned long pgoff, unsigned long flags)
{
	struct mm_struct *mm = current->mm;
	struct vm_area_struct *vma;
	unsigned long start_addr;

	if (len > TASK_SIZE)
		return -ENOMEM;

	if (flags & MAP_FIXED)
		return addr;

	if (addr) {
		addr = PAGE_ALIGN(addr);//将地址按页对齐
		vma = find_vma(mm, addr);//获取一个vma,该vma可能包含了addr也可能在addr后面并且离addr最近
		/*这里确定是否有一块适合的空闲区域,先要保证addr+len不会
		  超过进程地址空间的最大允许范围,然后如果前面vma获取成功的话则要保证
		  vma位于addr的后面并且addr+len不会延伸到该vma的区域*/
		if (TASK_SIZE - len >= addr &&
			(!vma || addr + len <= vma->vm_start))
			return addr;
	}
	/*前面获取不成功的话则要调整起始地址了,根据情况选择缓存的空闲区域地址
	  或者TASK_UNMAPPED_BASE=TASK_SIZE/3*/
	if (len > mm->cached_hole_size) {
			start_addr = addr = mm->free_area_cache;
	} else {
			start_addr = addr = TASK_UNMAPPED_BASE;
			mm->cached_hole_size = 0;
	}

full_search:
	/*从addr开始遍历用户地址空间*/
	for (vma = find_vma(mm, addr); ; vma = vma->vm_next) {
		/* At this point:  (!vma || addr < vma->vm_end). */
		if (TASK_SIZE - len < addr) {//这里判断是否已经遍历到了用户地址空间的末端
			/*
			 * Start a new search - just in case we missed
			 * some holes.
			 */
			 //如果上次不是从TAKS_UNMAPPED_BASE开始遍历的,则尝试从TASK_UNMAPPED_BASE开始遍历
			if (start_addr != TASK_UNMAPPED_BASE) {
				addr = TASK_UNMAPPED_BASE;
					start_addr = addr;
				mm->cached_hole_size = 0;
				goto full_search;
			}
			return -ENOMEM;
		}
		if (!vma || addr + len <= vma->vm_start) {//判断是否有空闲区域
			/*
			 *找到空闲区域的话则记住我们搜索的结束处,以便下次搜索
			 */
			mm->free_area_cache = addr + len;
			return addr;
		}
		/*该空闲区域不符合大小要求,但是如果这个空闲区域大于之前保存的最大值的话
		  则将这个空闲区域保存,这样便于前面确定从哪里开始搜索*/
		if (addr + mm->cached_hole_size < vma->vm_start)
				mm->cached_hole_size = vma->vm_start - addr;
		addr = vma->vm_end;
	}
}

查看某进程内存

test.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<sys/mman.h>
#include<sys/types.h>
#include<fcntl.h>
#include<stdio.h>
#include<unistd.h>

#include <time.h>
#include <string.h>

int main()
{   
	int i,j,k,l;
	char *mp;
	mp = (char*)mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); 
	strcpy(mp, "ABCDEFGHIJKL1234567890!@#$%^&*()KKKKKKKKKKKKKKKKKKK");
	strcpy(mp+4096, "AAAAAAAAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCC");
	sleep(10000000);
	munmap(mp, 8192);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# strace ./test
execve("./test", ["./test"], [/* 23 vars */]) = 0
brk(0)                                  = 0x1bdf000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f133f166000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f133f165000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
open("/etc/ld.so.cache", O_RDONLY)      = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=72203, ...}) = 0
mmap(NULL, 72203, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f133f153000
close(3)                                = 0
open("/lib64/libc.so.6", O_RDONLY)      = 3
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\360\332a\2217\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=1726296, ...}) = 0
mmap(0x3791600000, 3506520, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x3791600000
mprotect(0x379174f000, 2097152, PROT_NONE) = 0
mmap(0x379194f000, 20480, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x14f000) = 0x379194f000
mmap(0x3791954000, 16728, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x3791954000
close(3)                                = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f133f152000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f133f151000
arch_prctl(ARCH_SET_FS, 0x7f133f1516e0) = 0
mprotect(0x379194f000, 16384, PROT_READ) = 0
mprotect(0x379141c000, 4096, PROT_READ) = 0
munmap(0x7f133f153000, 72203)           = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f133f163000
rt_sigprocmask(SIG_BLOCK, [CHLD], [], 8) = 0
rt_sigaction(SIGCHLD, NULL, {SIG_DFL, [], 0}, 8) = 0
rt_sigprocmask(SIG_SETMASK, [], NULL, 8) = 0
nanosleep({10000000, 0},

基本确定最后一个mmap就是我们申请的,它的起始虚拟地址是0x7f133f163000,所以要在对应tast的mm中找到相应的vma。

1
2
3
4
crash> ps
...
  58674  58673   0  ffff88003d388ae0  IN   0.0    3672    316  test
...
1
2
3
4
5
crash_7.0.8> task_struct ffff88003d388ae0
struct task_struct {
...
mm = 0xffff88003d80ba00,
...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
crash_7.0.8> mm_struct 0xffff88003d80ba00
struct mm_struct {
  mmap = 0xffff88002a4d5ed0,
  mm_rb = {
	rb_node = 0xffff88003c2fad38
  },
  mmap_cache = 0xffff880029332788,
  get_unmapped_area = 0xffffffff81010410 <arch_get_unmapped_area_topdown>,
  get_unmapped_exec_area = 0x0,
  unmap_area = 0xffffffff8113aed0 <arch_unmap_area_topdown>,
  mmap_base = 139720639541248,
  task_size = 140737488351232,
  cached_hole_size = 0,   
  free_area_cache = 139720639524864,
  pgd = 0xffff88000c952000,
  ...

先看mmap,mmap_cache是不是,不是的话从mm_rb.rb_node开始找,这个是平衡二叉树的根。

1
2
3
#define rb_entry(ptr, type, member) container_of(ptr, type, member)

vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);

所以rb_node的地址减去vm_rb在struct vm_area_struct的偏移就是对应struct vm_area_struct的地址(2.6.32-358是0x38)

所以rb_node = 0xffff88003c2fad38 => struct vm_area_struct = 0xffff88003c2fad00

根据find_vma函数方法,直到找到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
	struct vm_area_struct *vma = NULL;

	if (mm) {
		/* Check the cache first. */
		/* (Cache hit rate is typically around 35%.) */
		vma = mm->mmap_cache;
		if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
			struct rb_node * rb_node;

			rb_node = mm->mm_rb.rb_node;
			vma = NULL;

			while (rb_node) {
				struct vm_area_struct * vma_tmp;

				vma_tmp = rb_entry(rb_node,
						struct vm_area_struct, vm_rb);

				if (vma_tmp->vm_end > addr) {
					vma = vma_tmp;
					if (vma_tmp->vm_start <= addr)
						break;
					rb_node = rb_node->rb_left;
				} else 
					rb_node = rb_node->rb_right;
			}
			if (vma)
				mm->mmap_cache = vma; 
		}
	}
	return vma; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
crash_7.0.8> vm_area_struct 0xffff88002d29c5f8
struct vm_area_struct {
  vm_mm = 0xffff88003d80ba00,
  vm_start = 139720639524864,
  vm_end = 139720639541248,
  vm_next = 0xffff880029332788,
  vm_prev = 0xffff88003c2fa918,
  vm_page_prot = {
	pgprot = 9223372036854775845
  },
  vm_flags = 1048691,
  vm_rb = {
	rb_parent_color = 18446612133323974193,
	rb_right = 0xffff8800293327c0,
	rb_left = 0xffff88003c2fa950
  },
  ...


crash_7.0.8> p/x 139720639524864
$4 = 0x7f133f163000

所以对应的vma就是0xffff88002d29c5f8,用内核函数follow_page找到对应page

follow_page.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/types.h>

#include <linux/sysctl.h>
#include <linux/timer.h>
#include <linux/hardirq.h>
#include <linux/bottom_half.h>
#include <linux/preempt.h>

#include <linux/types.h>
#include <linux/proc_fs.h>
#include <linux/file.h>

#include <linux/kprobes.h>

#include <linux/mm.h>
#include <linux/mm_types.h>

static int __init test_init(void)
{
	int i;
	struct page *(*follow_page_p)(struct vm_area_struct *vma, unsigned long address, unsigned int flags)
		= (struct page *(*)(struct vm_area_struct *vma, unsigned long address, unsigned int flags))0xffffffff81133ab0;
	struct vm_area_struct *vma = (struct vm_area_struct *)0xffff88002d29c5f8;
	unsigned long address = 139720639524864UL;
	struct page *pa;  
	char ch[4096+10]; 
	pa = follow_page_p(vma, address, 0);
	memcpy(ch, page_address(pa), 4096); 
	printk("page = %p\n", pa);
	printk("%s\n", ch);   
	return 0;
}

static void __exit test_exit(void)
{
	printk("test exit\n");
}

module_init(test_init);
module_exit(test_exit);

MODULE_LICENSE("GPL");
1
2
3
4
5
6
7
8
obj-m := follow_page.o
KDIR:=/lib/modules/$(shell uname -r)/build/
PWD=$(shell pwd)

all:
	make -C $(KDIR) M=$(PWD) modules
clean:
	make -C $(KDIR) M=$(PWD) clean
1
2
3
4
5
6
# insmod ./follow_page.ko
# rmmod follow_page
# dmesg
page = ffffea000077a1a8
ABCDEFGHIJKL1234567890!@#$%^&*()KKKKKKKKKKKKKKKKKKK
test exit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <linux/module.h> 
#include <linux/kernel.h> 
#include <linux/init.h>   
#include <linux/types.h>  

#include <linux/sysctl.h> 
#include <linux/timer.h>  
#include <linux/hardirq.h>
#include <linux/bottom_half.h>
#include <linux/preempt.h>

#include <linux/types.h>  
#include <linux/proc_fs.h>
#include <linux/file.h>   

#include <linux/kprobes.h>

#include <linux/mm.h>
#include <linux/mm_types.h>

static int __init test_init(void)
{
	struct page *(*follow_page_p)(struct vm_area_struct *vma, unsigned long address, unsigned int flags)
		= (struct page *(*)(struct vm_area_struct *vma, unsigned long address, unsigned int flags))0xffffffff81133ab0;
	struct vm_area_struct *vma = (struct vm_area_struct *)0xffff88002d29c5f8;
	unsigned long address = 139720639524864UL;
	struct page *pa;  
	char ch[4096+10]; 
	pa = follow_page_p(vma, address, 0);
	memcpy(ch, page_address(pa), 4096);
	{
		pgd_t *pgd;
		pud_t *pud;
		pmd_t *pmd;
		pte_t *pte;
		unsigned long pfn;

		pgd = pgd_offset(vma->vm_mm, address);
		pud = pud_offset(pgd, address);
		pmd = pmd_offset(pud, address);
		pte = pte_offset_map(pmd, address);
		pfn = pte_pfn(*pte);

		printk("follow_page=%p\n\n", pa);

		printk("PTE_PFN_MASK=0x%lx PAGE_OFFSET=%lx __va(x)=x+PAGE_OFFSET\n\n", PTE_PFN_MASK, PAGE_OFFSET);

		printk("mm->pgd=%p\n", vma->vm_mm->pgd);
		printk("PGDIR_SHIFT=%u PTRS_PER_PGD=%u pgd_index*8=0x%lx mm->pgd+index==pgd=%p\n\n", PGDIR_SHIFT, PTRS_PER_PGD, pgd_index(address)*8, pgd);

		printk("*pgd=0x%lx *pgd&MASK=0x%lx __va=%p\n", (*pgd).pgd, ((*pgd).pgd)&PTE_PFN_MASK, __va(((*pgd).pgd)&PTE_PFN_MASK));
		printk("PUD_SHIFT=%u PTRS_PER_PUD=%u pud_index*8=0x%lx __va+index==pud=%p\n\n", PUD_SHIFT, PTRS_PER_PUD, pud_index(address)*8, pud);

		printk("*pud=0x%lx *pud&MASK=0x%lx __va=%p\n", (*pud).pud, ((*pud).pud)&PTE_PFN_MASK, __va(((*pud).pud)&PTE_PFN_MASK));
		printk("PMD_SHIFT=%d PTRS_PER_PMD=%d pmd_index*8=0x%lx __va+index==pmd=%p\n\n", PMD_SHIFT, PTRS_PER_PMD, pmd_index(address)*8, pmd);

		printk("*pmd=0x%lx *pmd&MASK=0x%lx __va=%p\n", (*pmd).pmd, ((*pmd).pmd)&PTE_PFN_MASK, __va(((*pmd).pmd)&PTE_PFN_MASK));
		printk("PAGE_SHIFT=%d PTRS_PER_PTE=%d pte_index*8=0x%lx __va+index==pte=%p\n\n", PAGE_SHIFT, PTRS_PER_PTE, pte_index(address)*8, pte);

		printk("*pte=0x%lx *pte&MASK=0x%lx pte_pfn=%lx pfn=%lx\n", (*pte).pte, ((*pte).pte)&PTE_PFN_MASK, (((*pte).pte)&PTE_PFN_MASK)>>PAGE_SHIFT, pfn);
		printk("vmemmap=%p pfn*sizeof(page)=0x%lx cal_page=%p==follow_page\n\n", vmemmap, pfn*sizeof(struct page), vmemmap+pfn);
	}
	printk("%s\n", ch);
	return 0;
}

static void __exit test_exit(void)
{
	printk("test exit\n");
}

module_init(test_init);   
module_exit(test_exit);   

MODULE_LICENSE("GPL");
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# dmesg
follow_page=ffffea000077a1a8

PTE_PFN_MASK=0x3ffffffff000 PAGE_OFFSET=ffff880000000000 __va(x)=x+PAGE_OFFSET

mm->pgd=ffff88000c952000
PGDIR_SHIFT=39 PTRS_PER_PGD=512 pgd_index*8=0x7f0 mm->pgd+index==pgd=ffff88000c9527f0

*pgd=0x30bee067 *pgd&MASK=0x30bee000 __va=ffff880030bee000
PUD_SHIFT=30 PTRS_PER_PUD=512 pud_index*8=0x260 __va+index==pud=ffff880030bee260

*pud=0x323b1067 *pud&MASK=0x323b1000 __va=ffff8800323b1000
PMD_SHIFT=21 PTRS_PER_PMD=512 pmd_index*8=0xfc0 __va+index==pmd=ffff8800323b1fc0

*pmd=0xc934067 *pmd&MASK=0xc934000 __va=ffff88000c934000
PAGE_SHIFT=12 PTRS_PER_PTE=512 pte_index*8=0xb18 __va+index==pte=ffff88000c934b18

*pte=0x80000000222e3047 *pte&MASK=0x222e3000 pte_pfn=222e3 pfn=222e3
vmemmap=ffffea0000000000 pfn*sizeof(page)=0x77a1a8 cal_page=ffffea000077a1a8==follow_page

ABCDEFGHIJKL1234567890!@#$%^&*()KKKKKKKKKKKKKKKKKKK
test exit

dfs all vma, 虚拟地址连续,物理地址不连续

1
2
3
...
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f90fd1e3000
...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h> 
#include <linux/types.h>

#include <linux/sysctl.h>
#include <linux/timer.h>
#include <linux/hardirq.h>
#include <linux/bottom_half.h>
#include <linux/preempt.h>

#include <linux/types.h>
#include <linux/proc_fs.h>
#include <linux/file.h> 

#include <linux/kprobes.h>

#include <linux/mm.h>   
#include <linux/mm_types.h>

#define N 10000000
char ch[N];

void dfs(struct rb_node *rb)
{
	struct page *(*follow_page_p)(struct vm_area_struct *vma, unsigned long address, unsigned int flags)
		= (struct page *(*)(struct vm_area_struct *vma, unsigned long address, unsigned int flags))0xffffffff81133ab0;
	struct vm_area_struct *vma;
	unsigned long start, end, addr = 0x7f90fd1e3000;
	struct page *pa;
	if (!rb)
		return;
	vma = rb_entry(rb, struct vm_area_struct, vm_rb);
	start = vma->vm_start;
	end = vma->vm_end;
	if (addr >= start && addr < end && end-start <= N) {
		pa = follow_page_p(vma, addr, 0);
		if (pa) {
			memcpy(ch, page_address(pa), 4096);
			printk("page=%p ch=%s\n", pa, ch);
		}

		pa = follow_page_p(vma, addr+4096, 0);
		if (pa) {
			memcpy(ch, page_address(pa), 4096);
			printk("page=%p ch=%s\n", pa, ch);
		}
	}
	dfs(rb->rb_left);
	dfs(rb->rb_right);
}

static int __init test_init(void)
{
	struct mm_struct *mm = (struct mm_struct*)0xffff8800303a3880;
	printk("test start task->mm=%p\n", mm->mm_rb.rb_node);
	dfs(mm->mm_rb.rb_node);
	return 0;
}


static void __exit test_exit(void)
{
	printk("test exit\n");
}

module_init(test_init);
module_exit(test_exit);

MODULE_LICENSE("GPL");
1
2
3
4
test start task->mm=ffff88002cc05e40
page=ffffea000066e618 ch=ABCDEFGHIJKL1234567890!@#$%^&*()KKKKKKKKKKKKKKKKKKK
page=ffffea000062bec0 ch=AAAAAAAAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCC
test exit

vm_area_struct (VMA)

Linux内核中,关于虚存管理的最基本的管理单元应该是struct vm_area_struct了,它描述的是一段连续的、具有相同访问属性的虚存空间,该虚存空间的大小为物理内存页面的整数倍。

下面是struct vm_area_struct结构体的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
 * This struct defines a memory VMM memory area. There is one of these
 * per VM-area/task.  A VM area is any part of the process virtual memory
 * space that has a special rule for the page-fault handlers (ie a shared
 * library, the executable area etc).
 */
vm_area_struct { 
	struct mm_struct * vm_mm; /* VM area parameters */  
	unsigned long vm_start;  
	unsigned long vm_end;  
	  
	/* linked list of VM areas per task, sorted by address */  
	struct vm_area_struct *vm_next;  
	  
	pgprot_t vm_page_prot;  
	unsigned long vm_flags;  
	  
	/* AVL tree of VM areas per task, sorted by address */  
	short vm_avl_height;  
	struct vm_area_struct * vm_avl_left;  
	struct vm_area_struct * vm_avl_right;  
	  
	/* For areas with an address space and backing store, 
	* font-size: 10px;">vm_area_struct *vm_next_share; 
	struct vm_area_struct **vm_pprev_share; 
	 
	struct vm_operations_struct * vm_ops; 
	unsigned long vm_pgoff; /* offset in PAGE_SIZE units, *not* PAGE_CACHE_SIZE */  
	struct file * vm_file;  
	unsigned long vm_raend;  
	void * vm_private_data; /* was vm_pte (shared mem) */  
};

vm_area_struct结构所描述的虚存空间以vm_start、vm_end成员表示,它们分别保存了该虚存空间的首地址和末地址后第一个字节的地址,以字节为单位,所以虚存空间范围可以用[vm_start, vm_end)表示。

通常,进程所使用到的虚存空间不连续,且各部分虚存空间的访问属性也可能不同。所以一个进程的虚存空间需要多个vm_area_struct结构来描述。在vm_area_struct结构的数目较少的时候,各个vm_area_struct按照升序排序,以单链表的形式组织数据(通过vm_next指针指向下一个vm_area_struct结构)。但是当vm_area_struct结构的数据较多的时候,仍然采用链表组织的化,势必会影响到它的搜索速度。针对这个问题,vm_area_struct还添加了vm_avl_hight(树高)、vm_avl_left(左子节点)、vm_avl_right(右子节点)三个成员来实现AVL树,以提高vm_area_struct的搜索速度。

假如该vm_area_struct描述的是一个文件映射的虚存空间,成员vm_file便指向被映射的文件的file结构,vm_pgoff是该虚存空间起始地址在vm_file文件里面的文件偏移,单位为物理页面。

一个程序可以选择MAP_SHARED或MAP_PRIVATE共享模式将一个文件的某部分数据映射到自己的虚存空间里面。这两种映射方式的区别在于:MAP_SHARED映射后在内存中对该虚存空间的数据进行修改会影响到其他以同样方式映射该部分数据的进程,并且该修改还会被写回文件里面去,也就是这些进程实际上是在共用这些数据。而MAP_PRIVATE映射后对该虚存空间的数据进行修改不会影响到其他进程,也不会被写入文件中。

来自不同进程,所有映射同一个文件的vm_area_struct结构都会根据其共享模式分别组织成两个链表。链表的链头分别是:vm_file->f_dentry->d_inode->i_mapping->i_mmap_shared,vm_file->f_dentry->d_inode->i_mapping->i_mmap。而vm_area_struct结构中的vm_next_share指向链表中的下一个节点;vm_pprev_share是一个指针的指针,它的值是链表中上一个节点(头节点)结构的vm_next_share(i_mmap_shared或i_mmap)的地址。

进程建立vm_area_struct结构后,只是说明进程可以访问这个虚存空间,但有可能还没有分配相应的物理页面并建立好页面映射。在这种情况下,若是进程执行中有指令需要访问该虚存空间中的内存,便会产生一次缺页异常。这时候,就需要通过vm_area_struct结构里面的vm_ops->nopage所指向的函数来将产生缺页异常的地址对应的文件数据读取出来。

vm_flags主要保存了进程对该虚存空间的访问权限,然后还有一些其他的属性。vm_page_prot是新映射的物理页面的页表项pgprot的默认值。


原文:http://oss.org.cn/kernel-book/ch06/6.4.2.htm

6.4.2 进程的虚拟空间

如前所述,每个进程拥有3G字节的用户虚存空间。但是,这并不意味着用户进程在这3G的范围内可以任意使用,因为虚存空间最终得映射到某个物理存储空间(内存或磁盘空间),才真正可以使用。

那么,内核怎样管理每个进程3G的虚存空间呢?概括地说,用户进程经过编译、链接后形成的映象文件有一个代码段和数据段(包括data段和bss段),其中代码段在下,数据段在上。数据段中包括了所有静态分配的数据空间,即全局变量和所有申明为static的局部变量,这些空间是进程所必需的基本要求,这些空间是在建立一个进程的运行映像时就分配好的。除此之外,堆栈使用的空间也属于基本要求,所以也是在建立进程时就分配好的,如图6.16所示:

进程虚拟空间(3G)!

图6.16 进程虚拟空间的划分

由图可以看出,堆栈空间安排在虚存空间的顶部,运行时由顶向下延伸;代码段和数据段则在低部,运行时并不向上延伸。从数据段的顶部到堆栈段地址的下沿这个区间是一个巨大的空洞,这就是进程在运行时可以动态分配的空间(也叫动态内存)。

进程在运行过程中,可能会通过系统调用mmap动态申请虚拟内存或释放已分配的内存,新分配的虚拟内存必须和进程已有的虚拟地址链接起来才能使用;Linux 进程可以使用共享的程序库代码或数据,这样,共享库的代码和数据也需要链接到进程已有的虚拟地址中。在后面我们还会看到,系统利用了请页机制来避免对物理内存的过分使用。因为进程可能会访问当前不在物理内存中的虚拟内存,这时,操作系统通过请页机制把数据从磁盘装入到物理内存。为此,系统需要修改进程的页表,以便标志虚拟页已经装入到物理内存中,同时,Linux 还需要知道进程虚拟空间中任何一个虚拟地址区间的来源和当前所在位置,以便能够装入物理内存。

由于上面这些原因,Linux 采用了比较复杂的数据结构跟踪进程的虚拟地址。在进程的 task_struct结构中包含一个指向 mm_struct 结构的指针。进程的mm_struct 则包含装入的可执行映象信息以及进程的页目录指针pgd。该结构还包含有指向 vm_area_struct 结构的几个指针,每个 vm_area_struct 代表进程的一个虚拟地址区间。

图6.17 进程虚拟地址示意图

图 6.17是某个进程的虚拟内存简化布局以及相应的几个数据结构之间的关系。从图中可以看出,系统以虚拟内存地址的降序排列 vm_area_struct。在进程的运行过程中,Linux 要经常为进程分配虚拟地址区间,或者因为从交换文件中装入内存而修改虚拟地址信息,因此,vm_area_struct结构的访问时间就成了性能的关键因素。为此,除链表结构外,Linux 还利用 红黑(Red_black)树来组织 vm_area_struct。通过这种树结构,Linux 可以快速定位某个虚拟内存地址。

当进程利用系统调用动态分配内存时,Linux 首先分配一个 vm_area_struct 结构,并链接到进程的虚拟内存链表中,当后续的指令访问这一内存区间时,因为 Linux 尚未分配相应的物理内存,因此处理器在进行虚拟地址到物理地址的映射时会产生缺页异常(请看请页机制),当 Linux 处理这一缺页异常时,就可以为新的虚拟内存区分配实际的物理内存。

在内核中,经常会用到这样的操作:给定一个属于某个进程的虚拟地址,要求找到其所属的区间以及vma_area_struct结构,这是由find_vma()来实现的,其实现代码在mm/mmap.c中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
	struct vm_area_struct *vma = NULL;

	if (mm) {
		/* Check the cache first. */
		/* (Cache hit rate is typically around 35%.) */
		vma = mm->mmap_cache;
		if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
			struct rb_node * rb_node;

			rb_node = mm->mm_rb.rb_node;
			vma = NULL;

			while (rb_node) {
				struct vm_area_struct * vma_tmp;

				vma_tmp = rb_entry(rb_node,
						struct vm_area_struct, vm_rb);

				if (vma_tmp->vm_end > addr) {
					vma = vma_tmp;
					if (vma_tmp->vm_start <= addr)
						break;
					rb_node = rb_node->rb_left;
				} else 
					rb_node = rb_node->rb_right;
			}
			if (vma)
				mm->mmap_cache = vma; 
		}
	}
	return vma; 
}

这个函数比较简单,我们对其主要点给予解释:

·参数的含义:函数有两个参数,一个是指向mm_struct结构的指针,这表示一个进程的虚拟地址空间;一个是地址,表示该进程虚拟地址空间中的一个地址。

·条件检查:首先检查这个地址是否恰好落在上一次(最近一次)所访问的区间中。根据代码作者的注释,命中率一般达到35%,这也是mm_struct结构中设置mmap_cache指针的原因。如果没有命中,那就要在红黑树中进行搜索,红黑树与AVL树类似。

·查找节点:如果已经建立了红黑树结构(rb_rode不为空),就在红黑树中搜索。

·如果找到指定地址所在的区间,就把mmap_cache指针设置成指向所找到的vm_area_struct结构。

·如果没有找到,说明该地址所在的区间还没有建立,此时,就得建立一个新的虚拟区间,再调用insert_vm_struct()函数将新建立的区间插入到vm_struct中的线性队列或红黑树中。


原文:http://bbs.chinaunix.net/archiver/?tid-2058683.html

Linux sys_exec中可执行文件映射的建立及读取

  1. 创建一个vm_area_struct;
  2. 圈定一个虚用户空间,将其起始结束地址(elf段中已设置好)保存到vm_start和vm_end中;
  3. 将磁盘file句柄保存在vm_file中;
  4. 将对应段在磁盘file中的偏移值(elf段中已设置好)保存在vm_pgoff中;
  5. 将操作该磁盘file的磁盘操作函数保存在vm_ops中;
  6. 注意这里没有为对应的页目录表项创建页表,更不存在设置页表项了;