内存管理

RAM中的某些部分永久的分配给内核，并用来存放内核代码以及静态的内核数据结构。其余的部分我们称为动态内存，这不仅是进程所需要的宝贵资源，也是内核本身所需要的宝贵资源。

页框管理

Linux采用4KB页框大小作为标准的内存分配单元。基于以下两个原因，这会使事情变得简单：

• 由分页单元引发的缺页异常很容易得到解释，或者是由于请求的页存在但不允许进程对其访问，或者是由于请求的页不存在。在第二种情况下，内存分配器必须找到一个4KB的空闲页框，并将其分配给进程。
• 虽然4KB和4MB都是磁盘块大小的倍数，但是在绝大多数情况下，当主存和磁盘之间传输小块数据时更高效。

页描述符

内核必须记录每个页框当前的状态。在以下情况下页框是不空闲的：

• 包含用户态进程的数据；
• 某个软件高速缓存的数据；
• 动态分配的内核数据结构；
• 设备驱动程序缓冲的数据；
• 内核模块的代码等等。

页框的状态信息保存在一个类型为page的页描述符中，其中的字段如表8.1所示。所有的页描述符存放在mem_map数组中。因为每个描述符长度为32字节，所以mem_map所需要的空间略小于整个RAM的1%。virt_to_page(addr)宏产生线性地址addr对应的页描述符地址。pfn_to_page(pfn)宏产生与页框号pfn对应的页描述符地址。

_count字段：为页的引用计数器。如果为-1，那么说明该页框空闲，可以被分配给任何一个进程或者内核本身；如果大于0或者等于0，则说明页框被分配给了一个或者多个进程，或者用于存放一些内核数据结构。page_count()函数就是返回这个count的值加1，也即是该页使用者的数目。

flags字段包含多达32个用于描述页框状态的标志。

非一致性内存访问（NUMA）

内核2.6支持这种内存访问模型，这种模型中，给定CPU对不同内存单元的访问时间可能不一样。系统的物理内存被划分为几个节点（node）.在一个单独的节点内，任何一个给定CPU访问页面所需的时间都是相同的。然而，对不同的CPU，这个时间可能就不同，对于每个CPU而言，内核都试图把耗时节点的访问次数减到最小，这就要小心地选择CPU最常引用的内核数据结构的存放位置。

每个节点中的物理内存又可以分为几个管理区。每个节点都有一个pg_data_t的描述符，所有节点的描述符存放在一个单向链表中，第一个元素由pgdata_list变量指向。

IBM兼容PC使用一致访问内存（UMA）模型，因此并不真正需要NUMA的支持。但是即使对NUMA的支持没有被编译进内核，Linux还是使用一个节点，只是这个节点包含了系统中所有的物理内存。因此pgdata_list指向一个只包含一个节点的链表，这个节点也就是节点0的描述符，存放于contig_page_data变量中。这样做的好处是有助于内存代码的处理更具可移植性。

内存管理区

由于计算机体系结构有硬件的制约，所以内核必须处理80x86体系结构的两种硬件约束：

• ISA总线的直接内存存取（DMA）处理器有一个严格的限制：只能对主存的前16M寻址。
• 在具有大容量的内存的现代32位计算机中，CPU不能直接访问所有的物理内存，因为线性地址空间太小，只有4G。超过4G的部分就不能直接进行寻址了。

为了应对上述的两种限制，内核2.6把每个内存节点的物理内存划分为3个管理区（zone），在x86 UMA体系结构下的管理区为：

• ZONE_DMA包含低于16M的内存页框
• ZONE_NORMAL包含高于16M低于896M的内存页框
• ZONE_HIGHMEN包含从896M开始到高于896M的内存页框

前两个包含内存的常规页框，通过把它们映射到虚拟地址空间中的第4个G，内核就可以直接进行访问。第三个区包含的内存页不能由内核直接访问。

同样，每个管理区也都有自己的描述符。

每个页描述符都有到内存节点node以及到节点内管理区(即这个页所在的管理区)的指针。为了节省空间，这下指针和典型的指针不一样，而是被编码成索引放到了flags字段的高位。

page_zone()函数接收一个页描述符的物理地址作为参数，读取页描述符中flags字段的最高位，然后通过查看zone_table数组来确定相应管理区描述符的地址。在启动时用所内存节点的所有管理区描述符的地址初始化这个数组。

当内核调用一个内存分配函数的时候，必须指明请求的页框所在的管理区。为了在内存分配中请求中指定首选管理区，内核使用zonelist数据结构，也就是管理区描述符指针数组。

保留的页框池

用两种不同的方法来满足内存分配请求，如果有足够的空闲内存则满足请求；否则必须回收一些内存，并且将发出请求的内核控制路径阻塞，直到有内存被释放。

保留内存的数量（以KB为单位）存放在min_free_kbytes变量中，初始值在内核初始化时设置，并取决于直接映射到内核线性地址空间第4个GB的物理内存的数量，即取决于包含在ZONE_DMA和ZONE_NORMAL内存管理区内的页框数目。保留的原因是因为在原子请求从不被阻塞，如果没有足够的空闲页，那么就是分配失败，为了尽量减少这种情况发生，当内存不足的时候，就会使用保留的页框池。

ZONE_DMA和ZONE_NORMAL内存管理区将一定量的页框贡献给保留内存，这个数目与两个管理区的相对大小成比例。管理区描述符中的pages_min字段存储了管理区内保留的页框的数据。这个字段和pages_low、pages_high字段一起还在页框回收算法中起作用。page_low字段总是被设为pages_min的值的5/4，而pages_high总是被设置为pages_min的值的3/2。

分区页框分配器

叫做分区页框分配器（zoned page frame allocator）的内核子系统，处理对连续页框组的内存分配请求。

管理区分配器部分接受动态分配和释放的请求，在请求分配的情况下，搜索一个能满足请求的一组连续页框内存的管理区。在每个管理区内，页框被伙伴系统来处理，为了达到更好的系统性能，一小部分页框保留在高速缓存中用于快速地满足对单个页框的分配请求。

请求和释放页框

6个函数被用来请求页框，一般都返回第一个所分配页框描述符的地址，分配失败则返回NULL。

• alloc_pages(gfp_mask, order)：请求2的order次方个连续的页框，
• alloc_page(gfp_mask)：用于获得单独页框的宏
• __get_free_pages(gfp_mask,order)：返回第一个所分配页的线性地址
• __get_free_page(gfp_mask)：用于获得单独页框的宏
• __get_zeroed_page(gfp_mask)：获取归零的页框，它调用alloc_pages(gfp_mask | __GFP_ZERO, 0)
• __get_dma_pages(gfp_mask,order)：获取适用于DMA的页框，它扩展为__get_free_pages(gfp_mask | __GFP_DMA, order)

gfp_mask是一组标志，它指明了如何寻找空闲的页框，能在gfp_mask中使用的标志如图

实际上Linux使用预定义标志值的集合，如下表。

__GFP_DMA和__GFP_HIGHMEM被称作管理区修饰符，他们标示寻找空闲页框时内核所搜索的管理区。contig_page_data节点描述符的node_zonelists字段是一个管理区描述符链表的数组，它代表后备管理区，对管理区修饰符的每一个设置，相应的链表包含的内存管理区能在原来的管理区缺少页框的情况下，被用于满足内存分配需求，在80x86下，后备管理区如下：

• 如果__GFP_DMA标志被置位，则只能从内存管理区获取页框。
• 否则，如果__GFP_HIGHMEM标志没有被置位，则只能接优先次序从ZONE_NORMAL和ZONE_DMA内存管理区获取页框。
• 否则(__GFP_HIGHMEM标志被置位），则可以按优先次序从ZONE_HIGHMEM、ZONE_NORMAL和ZONE_DMA内存管理区获得页框。

下面4个函数和宏中的任一个都可以释放页框：

• __free_pages(page,order)：该函数先检查page指向的页描述符；如果该页框未被保留（PG_reserved标志为0），就把描述符的字段减1。如果count值变为0，就假定从与page对应的页框开始的2的order次方个连续页框不再被使用。在这种情况下，该函数释放页框
• free_pages(addr, order)：这个函数类似于__free_pges(page,order)，但是它接收的参数为要释放的第一个页框的线性地址addr。
• __free_page(page)：这个宏释放page所指描述符对应的页框；它扩展为：__free_pages(page, 0)
• free_page(addr)：该宏释放线性地址为addr的页框，它扩展为free_pages(addr, 0)

高端内存页框的内核映射

与直接映射的物理内存末端、高端内存的始端所对应的线性地址存放在high_memory变量中，它被设置为896MB。896MB边界以上的页框并不映射在内核线性地址空间的第四个GB，因此内核不能直接访问。这意味着返回所分配页框线性地址的页分配器函数并不适用于高端内存。

Linux设计者不得不找到某种方法来允许内核使用所有可使用的RAM，达到PAE所支持的64GB0采用的方法如下：

• 高端内存页框的分配只能通过alloc_pages()函数和它的快捷函数alloc_page()。这些函数不返回第一个被分配页框的线性地址，因为如果该页框属于高端内存，那么这样的线性地址根本不存在。取而代之，这些函数返回第一个被分配页框的页描述符的线性地址。这些线性地址总是存在的，因为所有页描述符一旦被分配在低端内存中，它们在内核初始化阶段就不会改变。
• 没有线性地址的高端内存中的页框不能被内核访问。因此，内核线性地址空间的最后128MB中的一部分专门用于映射高端内存页框。当然，这种映射是暂时的，否则只有128MB的高端内存可以被访问。取而代之，通过重复使用线性地址，使得整个高端内存能够在不同的时间被访问。

内核可以采用三种不同的机制将页框映射到高端内存；分别叫做永久内核映射、临时内核映射及非连续内存分配。

建立永久内核映射可能阻塞当前进程；这发生在空闲页表项不存在时，也就是在高端内存上没有页表项可以用作页框的“窗口”时。因此，永久内核映射不能用于中断处理程序和可延迟函数。相反建立临时内核映射绝不会要求阻塞当前进程。

永久内核映射

永久内核映射允许内核建立高端页框到内核地址空间的长期映射。他们使用主内核页表中一个专门的页表，其地址存放在变量pkmap_page_table中，这在前面的页表机制管理区初始化中已经介绍过了。页表中的表项数由LAST_PKMAP宏产生，内核一次最多访问2MB或4MB的高端内存。

1
2
3

/*这里由定义可以看出永久内存映射为固定映射下面的4M空间*/
#define PKMAP_BASE ((FIXADDR_BOOT_START - PAGE_SIZE * (LAST_PKMAP + 1))	\
		    & PMD_MASK)

• 计数器为0：对应页表项没有映射任何高端内存页框，并且是可用的。
• 计数器为1：对应页表项没有映射任何高端内存页框，但是不能使用，因为其相应的TLB还未刷新。
• 计数器为n，远大于1：对应页表项映射一个高端内存页框，正好有n-1个内核成分在使用这个页框。

为了记录高端内存页框与永久内核映射包含的线性地址之间的联系，内核使用了page_address_htable散列表。该表包含一个page_address_map结构，用于为高端内存中的每一个页框进行当前映射。而该数据结构还包含一个指向页描述符的指针和分配给该页框的线性地址。

page_address()函数返回页框对应的线性地址，如果页框在高端内存中并且没有被映射，则返回NULL。这个函数接受一个页描述符指针page作为其参数，并区分以下两种情况：

1. 如果页框不在高端内存中（PG_highmen标志为0），则线性地址总是存在并且是通过计算页框下标，然后将其转换成物理地址，最后根据相应的物理地址得到线性地址。这是由下面的代码完成的：

   1	__va((unsigned long)(page - mem_map) << 12)

2. 如果页框在高端内存（PG_highmen标志为1）中，该函数就到page_address_htable散列表中查找。如果在散列表中找到页框，page_address()就返回它的线性地址，否则返回NULL。

kmap()函数建立永久内核映射。

1
2
3
4
5
6
7
8

/* 高端内存映射，运用数组进行操作分配情况 */
/* 分配好后需要加入哈希表中；*/
void *kmap(struct page *page)
{
	if (!PageHighMem(page)) /*如果页框不属于高端内存*/
		return page_address(page);
	return kmap_high(page);/*页框确实属于高端内存*/
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * kmap_high - map a highmem page into memory
 * @page: &struct page to map
 *
 * Returns the page's virtual memory address.
 *
 * We cannot call this from interrupts, as it may block.
 */
void *kmap_high(struct page *page)
{
	unsigned long vaddr;
	lock_kmap();

	vaddr = (unsigned long)page_address(page);
	if (!vaddr)
		vaddr = map_new_virtual(page);
	pkmap_count[PKMAP_NR(vaddr)]++;
	BUG_ON(pkmap_count[PKMAP_NR(vaddr)] < 2);
	unlock_kmap();
	return (void*) vaddr;/*返回地址*/
}

map_new_virtual()实际上执行两个嵌套循环：

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

static inline unsigned long map_new_virtual(struct page *page)
{
	count = LAST_PKMAP;
	for (;;) {
		int count;
		DECLARE_WAITQUEUE(wait, current);
		for(count = LAST_PKMAP; count > 0; count --) {
			last_pkmap_nr = (last_pkmap_nr + 1) & LAST_PKMAP_MASK;
			if (!last_pkmap_nr) {
				flush_all_zero_pkmaps();
				count = LAST_PKMAP;
			}
			if (!pkmap_count[last_pkmap_nr]) {
				unsigned long vaddr = PKMAP_BASE + (last_pkmap_nr << PAGE_SHIFT);
				set_pte(&(pkmap_page_table[last_pkmap_nr]), mk_pte(page, __pgprot(0x63)));
				pkmap_count[last_pkmap_nr] = 1;
				set_page_address(page, (void*)vaddr);
				return vaddr;
			}
		}

		current->state = TASK_UNITERRUPTIBLE;
		add_wait_queue(&pkmap_map_wait, &wait);
		unlock_kmap();
		schedule();
		remove_wait_queue(&pkmap_map_wait, &wait);
		lock_kmap();
		
		if (page_address(page))
			return (unsigned long)page_address(page);
 
	}
}

在内循环中，该函数扫描pkmap_count中的所有计数器直到找到一个空值。当在pkmap_count中找到了一个未使用的项时，大的if代码块运行。这段代码确定该项对应的线性地址，为它在pkmap_page_table页表中创建一个项，将count置1，因为该项现在已经被使用了，调用set_page_address()函数插入一个新元素到page_address_htable散列表中，并返回线性地址。

函数从上次停止的地方开始，穿越pkmap_count数组执行循环。这是函数通过将pkmap_page_table页表中上次使用过页表项的索引保存在一个名为last_pkmap_nr的变量中做到的。 因此，搜索从上次因调用map_new_virtual()函数而跳出的地方重新开始。

当在pkmap_count中搜索到最后一个计数器时，就又从下标为0的计数器重新开始搜索。不过，在继续之前，map_new_virtual()调用flush_all_zero_pkmaps()函数来开始寻找计数器 为1 的另一趟扫描。每个值为1的计数器都表示在pkmap_page_table页表中表项是空闲的，但不能使用，因为相应的TLB表项还没有被刷新。flush_all_zero_pkmaps()把它们的计数器重置为0，删除page_address_htable散列表中对应的元素，并在pkmap_page_table的所有项上进行TLB刷新。

如果内循环在pkmap_count中没有找到空的计数器，map_new_virtual()函数就阻塞当前进程，直到某个进程释放了pkmap_page_table页表中的一个表项。通过把current插入到pkmap_map_wait等待队列，把current状态设置为TASK_UNINTERRUPTIBLE并调用schedule()放弃CPU来达到此目的。一旦进程被唤醒，该函数就通过调用page_address()检查是否存在另一个进程已经映射了该页；如果还没有其他进程映射该页，则内循环重新开始。

kunmap()函数撤销先前由kmap()建立的永久内核映射。如果页确实在高端内存中，则调用kunmap_high()函数，它本质上等价于下列代码：

1
2
3
4
5
6
7
8

void kunmap_high(struct page * page)
{
    spin_lock(&kmap_lock);
    if ((--pkmap_count[((unsigned long)page_address(page) - PKMAP_BASE) >> PAGE_SHIFT]) == 1)
        if (waitqueue_active(&pkmap_map_wait))
            wake_up(&pkmap_map_wait);
    spin_unlock(&kmap_lock);
}

中括号内的表达式从页的线性地址计算出pkmap_count数组的索引。计数器被减1并与1相比。匹配成功表明没有进程在使用页。该函数最终能唤醒由map_new_virtual()添加在等待队列中的进程（如果有的话）。

总结一下，如果是通过alloc_page()获得了高端内存对应的page，内核专门为此留出一块线性空间，从PKMAP_BASE到FIXADDR_START，用于映射高端内存。在2.6内核上，如果不指定PAE，这个地址范围是4G-8M到4G-4M之间。这个空间叫内核永久映射空间或者永久内核映射空间。

这个空间和其它空间使用同样的页全局目录表，对于内核来说，就是swapper_pg_dir，对普通进程来说，通过 CR3寄存器指向。通常情况下，这个空间是 4M 大小，因此仅仅需要一个页表即可，内核通过来pkmap_page_table寻找这个页表。

通过kmap()， 可以把一个page映射到这个空间来。通过kunmap()，可以把一个page对应的线性地址从这个空间释放出来。

临时内核映射

临时内核映射比永久内核映射的实现要简单。在高端内存的任一页框都可以通过一个窗口（为此而保留的一个页表项）映射到内核地址空间。留给临时内核映射的窗口数是非常少的。

每个CPU都有它自己的包含13个窗口的集合，它们用enum km_type数据结构表示。该数据结构中定义的每个符号，如KM_BOUNCE_READ、KM_USER0或KM_PTE0，标识了窗口的线性地址。

内核必须确保同一窗口永不会被两个不同的控制路径同时使用。因此，km_type结构中的每个符号只能由一种内核成分使用，并以该成分命名。最后一个符号KM_TYPE_NR本身并不表示一个线性地址，但由每个CPU 用来产生不同的可用窗口数。

在km_type中的每个符号（除了最后一个）都是固定映射的线性地址的一个下标。enum_fixed_addresses数据结构包含符号FIX_KMAP_BEGIN和FIX_KMAP_END；把后者赋给下标FIX_KMAP_BEGIN+(KM_TYPE_NR*NR_CPUS)-1。在这种方式下，系统中的每个CPU都有KM_TYPE_NR个固定映射的线性地址。此外，内核用fix_to_virt(FIX_KMAP_BEGIN)线性地址对应的页表项的地址初始化kmap_pte变量。

为了建立临时内核映射，内核调用kmap_atomic()函数，它本质上等价于下列代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void * kmap_atomic(struct page * page, enum km_type type)
{
    enum fixed_addresses idx;
    unsigned long vaddr;

    current_thread_info( )->preempt_count++;
    if (!PageHighMem(page))
        return page_address(page);
    idx = type + KM_TYPE_NR * smp_processor_id( );
    vaddr = fix_to_virt(FIX_KMAP_BEGIN + idx);
    set_pte(kmap_pte-idx, mk_pte(page, 0x063));
    __flush_tlb_single(vaddr);
    return (void *) vaddr;
}

type参数和CPU标识符（通过smp_processor_id()）指定必须用哪个固定映射的线性地址映射请求页。如果页框不属于高端内存，则该函数返回页框的线性地址；否则，用页的物理地址及Present、Accessed、Read/Write 和Dirty 位建立该固定映射的线性地址对应的页表项。最后，该函数刷新适当的TLB 项并返回线性地址。

为了撤销临时内核映射，内核使用kunmap_atomic()函数。在80x86结构中，这个函数减少当前进程的preempt_count；因此，如果在请求临时内核映像之前能抢占内核控制路径，那么在同一个映射被撤销后可以再次抢占。此外，kunmap_atomic()检查当前进程的TIF_NEED_RESCHED标志是否被置位，如果是，就调用schedule()。

总结一下临时内核映射。前边提到从线性地址4G向前倒数若干的页面有一个空间称为固定映射空间，在这个空间中，有一部分用于高端内存的临时映射。这块空间具有如下特点：

1. 每个 CPU 占用一块空间
2. 在每个 CPU 占用的那块空间中，又分为多个小空间，每个小空间大小是 1 个 page，每个小空间用于一个目的，这些目的定义在kmap_types.h 中的 km_type 中。

当要进行一次临时映射的时候，需要指定映射的目的，根据映射目的，可以找到对应的小空间，然后把这个空间的地址作为映射地址。这意味着一次临时映射会导致以前的映射被覆盖。通过 kmap_atomic() 可实现临时映射。

伙伴系统算法

频繁的请求和释放不同大小的一组连续页框，必然导致在已分配页框的块内分散了许多小块的空闲页框。从本质上来说，避免外碎片的方法有两种：

• 利用分页单元把一组非连续的空闲页框映射到连续的线性地址区间。
• 开发一种适当的技术来记录现存的空闲连续页框块的情况，以尽量避免为满足对小块的请求而分割大的空闲块。

内核首选第二种方法，由于以下的原因：

• 在某些情况下，连续的页框确实是必要的，因为连续的线性地址不足以满足请求。比如DMA分配缓冲区的时候，会忽略分页单元而直接访问地址总线，因此，所请求的缓冲区就必须位于连续的页框中。
• 频繁的修改页表势必导致平均访问内存次数的增加，因为会频繁的刷新TLB。
• 内核通过4MB的页可以访问大块连续的物理内存，减少了转换后缓冲器失效率，提高访问内存的平均速度。

伙伴系统算法就是用来解决外碎片问题。

把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512，1024个连续的页框。对1024个页框的最大请求对应着4M大小的连续内存块。每个块的第一个页框的物理地址是该块大小的整数倍。

假设要请求一个256个页框的块（即1MB）：

• 算法先在256个页框的链表中检查是否有一个空闲块。
• 如果没有这样的块，算法会查找下一个更大的页块，也就是，在512个页框的链表中找一个空闲块。
• 如果存在这样的块，内核就把512的页框分成两等份，一半用作满足请求，另一半插入到256个页框的链表中。
• 如果在512个页框的块链表中也没找到空闲块，就继续找更大的块 —— 1024个页框的块。
• 如果这样的块存在，内核把1024个页框块的256个页框用作请求，然后从剩余的768个页框中拿512个插入到512个页框的链表中，再把最后的256个插入到256个页框的链表中。
• 如果1024个页框的链表还是空的，算法就放弃并发出错信号。

内核试图把大小为b的一对空闲伙伴块合并为一个大小为2b的单独块，满足一下条件的两个块为伙伴：

• 两个块具有相同的大小，记作b；
• 物理地址连续
• 第一个块的第一个页框的物理地址是2*b*2^12的倍数

数据结构

有三种伙伴系统：第一种处理适合ISA DMA的页框，第二种处理“常规”页框，第三种处理高端内存页框。每个伙伴系统使用的主要数据结构如下：

1. 前面介绍过的mem_map数组。实际上，每个管理区都关系到mem_map元素的子集。子集中的第一个元素和元素的个数分别由管理区描述符的zone_mem_map和size字段指定。
2. 包含有11个元素、元素类型为free_area的一个数组，每个元素对应一种块大小。该数组存放在管理区描述符zone_t的free_area字段中。

我们考虑管理区描述符中free_area数组的第k个元素，它标识所有大小为2^k的空闲块。这个元素的free_list字段是双向循环链表的头，这个双向循环链表集中了大小为2^k页的空闲块对应的页描述符。更精确地说，该链表包含每个空闲页框块（大小为2^k）的起始页框的页描述符；指向链表中相邻元素的指针存放在页描述符page的lru字段中。

除了链表头外，free_area数组的第k个元素同样包含字段nr_free，它指定了大小为2^k页的空闲块的个数。当然，如果没有大小为2^k的空闲页框块，则nr_free等于0且free_list为空（free_list的两个指针next和prev都指向它自己的free_list字段）。

最后，一个2^k的空闲页块的第一个页的描述符的private字段存放了块的order，也就是数字k。正是由于这个字段，当页块被释放时，内核可以确定这个块的伙伴是否也空闲。如果是的话，它可以把两个块结合成大小为2^(k+1)页的单一块。

块分配

内核使用__rmqueue()函数来在管理区中找到一个空闲块。该函数需要两个参数：管理区描述符的地址zone和order，order表示请求的空闲页块大小的对数值（0 表示一个单页块，1 表示一个两页块，2表示四个页块）。如果页框被成功分配，__rmqueue()函数就返回第一个被分配页框的页描述符。否则，函数返回NULL。

在__rmqueue()函数中，从所请求order的链表开始，它扫描每个可用块链表进行循环搜索，如果需要搜索更大的order，就继续搜索：

1
2
3
4
5
6
7
8
9

struct free_area *area;
unsigned int current_order;

for (current_order=order; current_order<11; ++current_order) {
    area = zone->free_area + current_order;
    if (!list_empty(&area->free_list))
        goto block_found;
}
return NULL;

1
2
3
4
5
6
7

block_found:
    page = list_entry(area->free_list.next, struct page, lru);
    list_del(&page->lru);
    ClearPagePrivate(page);
    page->private = 0;
    area->nr_free--;
    zone->free_pages -= 1UL << order;

1
2
3
4
5
6
7
8
9
10
11
12

size = 1 << curr_order;
while (curr_order > order) {
    area--;
    curr_order--;
    size >>= 1;
    buddy = page + size;
    list_add(&buddy->lru, &area->free_list);
    area->nr_free++;
    buddy->private = curr_order;
    SetPagePrivate(buddy);
}
return page;

块释放

__free_pages_bulk()函数按照伙伴系统的策略释放页框。它使用3个基本输入参数：

• page：被释放块中所包含的第一个页框描述符的地址。
• zone：管理区描述符的地址。
• order：块大小的对数。

__free_pages_bulk()首先声明和初始化一些局部变量：

1
2
3
4

struct page * base = zone->zone_mem_map;
unsigned long buddy_idx, page_idx = page - base;
struct page * buddy, * coalesced;
int order_size = 1 << order;

1

zone->free_pages += order_size;

1
2
3
4
5
6
7
8
9
10
11
12

while (order < 10) {
    buddy_idx = page_idx ^ (1 << order);
    buddy = base + buddy_idx;
    if (!page_is_buddy(buddy, order))
        break;
    list_del(&buddy->lru);
    zone->free_area[order].nr_free--;
    ClearPagePrivate(buddy);
    buddy->private = 0;
    page_idx &= buddy_idx;   /* 合并 */
    order++;
}

尤其要注意：buddy_idx = page_idx ^ (1 << order)这行代码。这行代码很巧妙，短小精干。因为order一来就等于4，所以循环从4开始的，即第一个循环为buddy_idx = page_idx ^ (1<<4)，即buddy_idx = page_idx ^ 10000。如果page_idx第5位为1，比如是20号页框（10100），那么在异或以后，buddy_idx为4号页框（00100）。如果page_idx第5位为0，比如是第40号页框（101000），那么在异或以后，buddy_idx为56号页框（111000）。

为什么要做这么一个运算呢？想想我们的目的是什么。__free_pages_bulk是将以其参数page为首的2^order个页面找到一个伙伴，并与其合并。在mem_map数组中，这个伙伴的老大要么是在这个page的前2^order，要么就是后2^order。如果单单是加或者减，那么就会忽略前面的或者后面的伙伴。

找到伙伴以后，把该伙伴的老大page的地址赋给buddy：

1

buddy = base + buddy_idx;

1
2
3
4
5
6
7

int page_is_buddy(struct page *page, int order)
{
    if (PagePrivate(buddy) && page->private == order &&
          !PageReserved(buddy) && page_count(page) ==0)
        return 1;
    return 0;
}

1. buddy的第一个页必须为空闲（_count字段等于-1）；
2. 它必须属于动态内存（PG_reserved 位清零）；
3. 它的private字段必须有意义（PG_private 位置位）；
4. 它的private字段必须存放将要被释放的块的order。

如果所有这些条件都符合，就说明有新的伙伴存在啦，那么伙伴块就要跟page结合，先必须得脱离原来的free_list，执行page_idx &= buddy_idx合并，并再执行一次循环以寻找两倍大小的伙伴块。

如果page_is_buddy()中至少有一个条件没有被满足，则该函数跳出循环，因为获得的空闲块不能再和其他空闲块合并。函数将它插入适当的链表并以块大小的order 更新第一个页框的private 字段。

1
2
3
4
5

coalesced = base + page_idx;
coalesced->private = order;
SetPagePrivate(coalesced);
list_add(&coalesced->lru, &zone->free_area[order].free_list);
zone->free_area[order].nr_free++;

每CPU页框高速缓存

内核经常请求和释放单个页框。为了提升系统性能，如果请求单个或释放单个页框时，内核在使用伙伴算法之前多添了一个步骤，即每CPU页框高速缓存。每个内存管理区定义了一个每CPU页框高速缓存，所有每CPU高速缓存包含一些预先分配的页框，它们被用于满足本地CPU 发出的单个页内存请求。

更进一步，内核为每个内存管理区和每个CPU提供了两个高速缓存：一个热高速缓存，它存放的页框中所包含的内容很可能就在CPU 硬件高速缓存中；还有一个冷高速缓存。

如果内核或用户态进程在刚分配到页框后就立即向页框写，那么从热高速缓存中获得页框就对系统性能有利。我们知道，CPU中的硬件高速缓存存在有最近使用过的页框。而我们每次对页框存储单元的访问将都会导致原来一个存在于硬件高速缓存的一页被替换掉。当然，除非硬件高速缓存包含有一行：它映射刚被访问的 “热”页框单元，那么我们称为“命中”。

反过来，如果页框将要被DMA操作填充，那么从冷高速缓存中获得页框是方便的。在这种情况下，不会涉及到CPU，并且硬件高速缓存的行不会被修改。从冷高速缓存获得页框为其他类型的内存分配保存了热页框储备。

如果实在理解不了上面对热缓存和冷缓存的定义，那我们就干脆这样理解：热缓存跟CPU有关，要使用到对应CPU的高速缓存，当我们读写一个页面时，如果没有命中硬件高速缓存就替换一个页；冷缓存跟CPU无关，当我们读写一个页面时根本不去管有没有命中CPU的硬件缓存。

数据结构

实现每CPU页框高速缓存的主要数据结构是存放在内存管理区描述符zone_t的pageset字段中的一个per_cpu_pageset数组数据结构。该数组包含为每个CPU 提供的一个元素；这个元素依次由两个per_cpu_pages描述符组成，一个留给热高速缓存而另一个留给冷高速缓存。

内核使用两个位标来监视热高速缓存或冷高速缓存的大小：如果页框个数低于下界low，内核通过从伙伴系统中分配batch个单一页框来补充对应的高速缓存；否则，如果页框个数高过上界high，内核从高速缓存中释放batch个页框到伙伴系统中。值batch、low和high本质上取决于内存管理区中包含的页框个数。

通过每CPU 页框高速缓存分配页框

buffered_rmqueue()函数在指定的内存管理区中分配页框。它使用每CPU页框高速缓存来处理单一页框请求。

参数为内存管理区描述符的地址，请求分配的内存大小的对数order，以及分配标志gfp_flags。如果gfp_flags中的__GFP_COLD标志被置位，那么页框应当从冷高速缓存中获取，否则它应从热高速缓存中获取（此标志只对单一页框请求有意义）。该函数本质上执行如下操作：

1. 如果order不等于0，每CPU页框高速缓存就不能被使用：函数跳到第4步。
2. 检查由__GFP_COLD标志所标识的内存管理区本地每CPU高速缓存是否需要补充（per_cpu_pages描述符的count字段小于或等于low字段）。在这种情况下，它执行如下子步骤：
   1. 通过反复调用__rmqueue()函数从伙伴系统中分配batch 个单一页框。
   2. 将已分配页框的描述符插入高速缓存链表中。
   3. 通过给count 增加实际被分配页框的个数来更新它。
3. 如果count值为正，则函数从高速缓存链表获得一个页框，count减1并跳到第5步。（注意，每CPU 页框高速缓存有可能为空，当在第2a 步调用__rmqueue()函数而分配页框失败时就会发生这种情况。）
4. 到这里，内存请求还没有被满足，或者是因为请求跨越了几个连续页框，或者是因为被选中的页框高速缓存为空。调用__rmqueue()函数从伙伴系统中分配所请求的页框。
5. 如果内存请求得到满足，函数就初始化（第一个）页框的页描述符：清除一些标志，将private字段置0，并将页框引用计数器置1。此外，如果gfp_flags中的__GPF_ZERO标志被置位，则函数将被分配的内存区域填充0。
6. 返回（第一个）页框的页描述符地址，如果内存分配请求失败则返回NULL。

释放页框到每CPU 页框高速缓存

为了释放单个页框到每CPU 页框高速缓存，内核使用free_hot_page()和free_cold_page()函数。它们都是free_hot_cold_page()函数的简单封装，接收的参数为将要释放的页框的描述符地址page和cold标志（指定是热高速缓存还是冷高速缓存）。

free_hot_cold_page()函数执行如下操作：

1. 从page->flags字段获取包含该页框的内存管理区描述符地址。
2. 获取由cold标志选择的管理区高速缓存的per_cpu_pages 描述符的地址。
3. 检查高速缓存是否应该被清空：如果count值高于或等于high，则调用free_pages_bulk()函数，将管理区描述符、将被释放的页框个数（batch字段）、高速缓存链表的地址以及数字0（为0 到order 个页框）传递给该函数。free_pages_bulkl()函数依次反复调用__free_pages_bulk()函数来释放指定数量的（从高速缓存链表获得的）页框到内存管理区的伙伴系统中。
4. 把释放的页框添加到高速缓存链表上，并增加count 字段。

应该注意的是，在当前的Linux 2.6内核版本中，从没有页框被释放到冷高速缓存中：至于硬件高速缓存，内核总是假设被释放的页框是热的。当然，这并不意味着冷高速缓存是空的：当达到下界时通过buffered_rmqueue()补充冷高速缓存。

管理区分配器

管理区分配器是内核页框分配器的前端。该成分必须分配一个包含足够多空闲页框的内存管理区，使他能满足内存请求。管理区分配器必须满足几个目标：

• 它应当保护保留的页框池。
• 当内存不足且允许阻塞当前进程时，它应当触发页框回收算法；一旦某些页框被释放，管理区分配器将再次尝试分配。
• 如果可能，它应当保存小而珍贵的ZONE_DMA内存管理区。例如，如果是对ZONE_NORMAL或ZONE_HIGHMEM页框的请求，那么管理区分配器会不太愿意分配ZONE_DMA内存管理区中的页框。

对一组连续页框的每次请求实质上是通过执行alloc_pages宏实现的，接着这个宏又调用__alloc_pages()函数，它接收以下三个参数：

• gfp_mask：在内存分配请求中指定的标志
• order：将要分配的一组连续页框数量的对数
• zonelist：指向zonelist的指针，该数据结构按优先次序描述了适于内存分配的内存管理区

__alloc_pages()扫描包含在zonelist中的每个内存管理区：

1
2
3
4
5
6
7

for (i = 0; (z = zonelinst->zones[i]) != NULL; i ++) {
    if (zone_watermark_of(z, order, ...)) {
        page = buffered_rmqueue(z, order, gfp_mask);
        if (page)
            return page;
    }
}

对于每个内存管理区，该函数将空闲页框的个数与一个阈值作比较，该阈值取决于内存分配标志、当前进程的类型以及管理区被函数检查过的次数。实际上，如果空闲内存不足，那么每个内存管理区一般会被检查n遍，每一遍在所请求的空闲内存最低量的基础上使用更低的阈值扫描。因此前面一段代码在__alloc_pages()函数体内被复制了几次，每次变化很小。__alloc_pages()函数调用buffered_rmqueue()函数：它返回第一个被分配的页框的页描述符；如果内存管理区没有所请求大小的一组连续页框，则返回NULL。

zone_watermark_ok()辅助函数，他的目的就是来探测对应的内存管理区中有没有足够的空闲页框，该函数接收几个参数，它们决定对应内存管理区中空闲页框个数的阈值min。同时满足下列两个条件则返回1的情况：

1. 除了被分配的页框外，在内存管理区中至少还有min个空闲页框，不包括为内存不足保留的页框（管理区描述符的lowmem_reserve 字段）。
2. 除了被分配的页框外，这里在order至少为k的块中起码还有min/2^k 个空闲页框，其中，对于每个k，取值在1 和分配的order 之间。因此，如果order大于0，那么在大小至少为2的块中至少还有min/2个空闲页框；如果order大于1，那么在大小至少为4的块中起码还有min/4个空闲页框。

__alloc_pages()本质上执行如下步骤：

1. 执行对内存管理区的第一次扫描。在第一次扫描中，阈值min被设为z->pages_low，其中的z指向正在被分析的管理区描述符（参数can_try_harder 和gfp_high 被设为0）。
2. 如果函数在上一步没有终止，那么没有剩下多少空闲内存：函数唤醒kswapd内核线程来异步地开始回收页框。
3. 执行对内存管理区的第二次扫描，将值z->pages_min作为阈值base传递。正如前面解释的，实际阈值由the_can_try_harder和gfp_high标志决定。这一步与第1步相似，但该函数使用了较低的阈值。
4. 如果函数在上一步没有终止，那么系统内存肯定不足。如果产生内存分配请求的内核控制路径不是一个中断处理程序或一个可延迟函数，并且它试图回收页框（或者是current的PF_MEMALLOC标志被置位，或者是它的PF_MEMDIE标志被置位），那么函数随即执行对内存管理区的第三次扫描，试图分配页框并忽略内存不足的阈值, 也就是说，不调用zone_watermark_ok()。唯有在这种情况下才允许内核控制路径耗用为内存不足预留的页（由管理区描述符的lowmem_reserve字段指定）。其实，在这种情况下产生内存请求的内核控制路径最终将试图释放页框，因此只要有可能它就应当得到它所请求的。如果没有任何内存管理区包含足够的页框，函数就返回NULL 来提示调用者发生了错误。
5. 在这里，正在调用的内核控制路径并没有试图回收内存。如果gfp_mask的__GFP_WAIT标志没有被置位，函数就返回NULL 来提示该内核控制路径内存分配失败：在这种情况下，如果不阻塞当前进程就没有办法满足请求。
6. 在这里当前进程能够被阻塞：调用cond_resched()检查是否有其它的进程需要CPU。
7. 设置current的PF_MEMALLOC标志来表示进程已经准备好执行内存回收。
8. 将一个指向reclaim_state数据结构的指针存入current->reclaim_state。这个数据结构只包含一个字段reclaimed_slab，被初始化为0。
9. 调用try_to_free_pages()寻找一些页框来回收。后一个函数可能阻塞当前进程。一旦函数返回，__alloc_pages()就重设current的PF_MEMALLOC标志并再次调用cond_resched()。
10. 如果上一步已经释放了一些页框，那么该函数还要执行一次与第3步相同的内存管理区扫描。如果内存分配请求不能被满足，那么函数决定是否应当继续扫描内存管理区：如果__GFP_NORETRY标志被清除, 并且内存分配请求跨越了多达8个页框或__GFP_REPEAT和__GFP_NOFAIL标志其中之一被置位，那么函数就调用blk_congestion_wait()使进程休眠一会儿，并且跳回到第6步。否则，函数返回NULL来提示调用者内存分配失败了。
11. 如果在第9步中没有释放任何页框，就意味着内核遇到很大的麻烦，因为空闲页框已经少到了危险的地步，并且不可能回收任何页框。也许到了该作出重要决定的时候了。如果允许内核控制路径执行依赖于文件系统的操作来杀死一个进程（gfp_mask中的__GFP_FS标志被置位）并且__GFP_NORETRY标志为0，那么执行如下子步骤：
    1. 使用等于z->pages_high的阈值再一次扫描内存管理区。
    2. 调用out_of_memory()通过杀死一个进程开始释放一些内存。
    3. 跳回第1 步。

因为第11a 步使用的界值远比前面扫描时使用的界值要高，所以这个步骤很容易失败。实际上，只有当另一个内核控制路径已经杀死一个进程来回收它的内存后，第11a 步才会成功执行。因此，第11a步避免了两个无辜的进程（而不是一个）被杀死。

释放一组页框

管理区分配器同样负责释放页框。

释放页框的所有内核宏和函数都依赖于__free_pages()函数。它接收的参数为将要释放的第一个页框的页描述符的地址(page)和将要释放的一组连续页框的数量的对数（order）。该函数执行如下步骤：

1. 检查第一个页框是否真正属于动态内存（它的PG_reserved标志被清0）；如果不是，则终止。
2. 减少page->_count使用计数器的值；如果它仍然大于或等于0，则终止。
3. 如果order 等于0，那么该函数调用free_hot_page()来释放页框给适当内存管理区的每CPU 热高速缓存。
4. 如果order大于0，那么它将页框加入到本地链表中，并调用free_pages_bulk()函数把它们释放到适当内存管理区的伙伴系统中。

内存区管理

内部碎片的产生主要是由于请求内存的大小与分配给它的大小不匹配而造成的，即使多个此数据结构通过一定规则挤进一个页面，那么也还有若干字节的空间被浪费。使用slab分配器解决，它有以下特性：

• 所存放数据的类型可以影响内存区的分配方式。
  • 例如，当给用户态进程分配一个页框时，内核调用get_zeroed_page()函数用0填充这个页。
  • slab分配器概念扩充了这种思想，并把内存区看作对象（object），这些对象由一组数据结构和几个叫做构造或析构函数组成。前者初始化内存区，而后者回收内存区。
  • 为了避免重复初始化对象，slab分配器并不丢弃已分配的对象，而是释放但把它们保存在内存中。当以后又要请求新的对象时，就可以从内存获取而不用重新初始化。
• 内核函数倾向于反复请求同一类型的内存区。例如，只要内核创建一个新进程，它就要为一些固定大小的数据结构分配内存区。当进程结束时，包含这些数据结构的内存区还可以被重新使用。slab分配器把那些页框保存在高速缓存中并很快地重新使用它们。
• 对内存区的请求可以根据它们发生的频率来分类。对于预期频繁请求一个特定大小的内存区而言，可以通过创建一组具有适当大小的专用对象来高效地处理，由此以避免内碎片的产生。另一种情况，对于很少遇到的内存区大小，可以通过基于一系列几何分布大小的对象的分配模式来处理，即使这种方法会导致内碎片的产生。
• 在引入的对象大小不是几何分布的情况下，也就是说，数据结构的起始地址不是物理地址值的2的幂次方，事情反倒好办。这可以借助处理器硬件高速缓存而导致较好的性能。
• 硬件高速缓存的高性能又是尽可能地限制对伙伴系统分配器调用的另一个理由，因为对伙伴系统函数的每次调用都“弄脏”硬件高速缓存，所以增加了对内存的平均访问时间。内核函数对硬件高速缓存的影响就是所谓的函数足迹（footprint），其定义为函数结束时重写高速缓存的百分比。显而易见，大的“足迹”导致内核函数刚执行之后较慢的代码执行，因为硬件高速缓存此时填满了无用的信息。

slab分配器把对象分组放进高速缓存。每个高速缓存都是同种类型对象的一种“储备”。例如，当一个文件被打开时，存放相应“打开文件”对象所需的内存区是从一个叫做filp（“文件指针”）的slab 分配器的高速缓存中得到的。

包含高速缓存的主内存区被划分为多个slab，每个slab 由一个或多个连续的页框组成，这些页框中既包含已分配的对象，也包含空闲的对象。

高速缓存描述符

每个高速缓存都是由kmem_cache_t（等价于struct kmem_cache_s类型）类型的数据结构来描述的；

kmem_cache_t描述符的lists字段又是一个kmem_lists结构体，

slab描述符

高速缓存中的每个slab都有自己的类型为slab的描述符

slab描述符可能存放在两个地方：

• 外部slab描述符，存放在slab外部，位于cache_sizes指向的一个不适合ISA DMA的普通高速缓存中。
• 内部slab描述符，存放在slab内部，位于分配给slab的第一个页框的起始位置。

普通和专用高速缓存

高速缓存被分为两种类型：普通和专用。普通高速缓存只由slab分配器用于自己的目的，而专用高速缓存由内核的其余部分使用。

普通高速缓存：

• 第一种：第一个高速缓存叫做kmem_cache，包含有内核使用的其余高速缓存描述符。cache_cache变量包含第一个高速缓存的描述符；
• 第二种：用作普通用途的内存区。内存区大小一般分为13个内存区。malloc_sizes的表（其元素类型为cache_sizes）分别指向26个高速缓存描述符，与其相关的内存区大小为：32,64,128,256,…,131072字节。每种大小，都有两个高速缓存：一个适用于ISA DMA分配，另一个使用与常规分配。

在系统初始化调用kmem_cache_init()和kmem_cache_sizes_init()来建立普通高速缓存。

专用高速缓存是由kmem_cache_create()函数创建的。从普通高速缓存中的cache_cache中取出来的一个描述符，并把描述符插入到高速缓存描述符的cache_chain链表中；还可以调用kmem_cache_destory()撤销一个高速缓存并将它从cache_chain链表上删除。为避免浪费空间，将分配的slab撤销，kmem_cache_shrink()函数通过反复调用slab_destroy()撤销所有的slab

slab分配器与分区页框分配器的接口

当slab分配器创建新的slab时，需要依靠分区页框分配器来获得一组连续的空闲页框。为了达到此目的，需要调用kmem_getpages()函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void * kmem_getpages(kmem_cache_t *cachep, int flags)
{
    struct page *page;
    int i;

    flags |= cachep->gfpflags;
    page = alloc_pages(flags, cachep->gfporder);
    if (!page)
        return NULL;
    i = (1 << cachep->gfporder);

    while (i--)
            SetPageSlab(page++);
    return page_address(page);
}

cachep指向需要外页框的高速缓存的高速缓存描述符，flags说明如何请求页框，与存放在高速缓存描述符的gfpflags中的专用高速缓存分配标志相结合。

内存分配请求的大小由高速缓存描述符的gfporder字段指定，该字段将高速缓存中slab的大小编码，注意不可能从ZONE_HIGHMEM内存管理区分配页框，因为kmem_getpages()函数返回由page_address()函数产生的线性地址。

在相反的操作中，通过调用kmem_freepages()函数可以释放分配给slab的页框。这个函数从线性地址addr开始释放页框，这些页框曾分配给由cachep标识的高速缓存中的slab。

给高速缓存分配slab

一个新创建的高速缓存没有包含任何slab，因此也没有空闲的对象。只有当以下两个条件都为真时，才给高速缓存分配slab：

• 已发出一个分配新对象的请求。
• 高速缓存不包含任何空闲对象。

当这些情况发生时，slab 分配器通过调用cache_grow()函数给高速缓存分配一个新的slab：

1

static int cache_grow (kmem_cache_t * cachep, int flags, int nodeid)

给定一个页框，内核必须确定它是否被slab分配器使用，如果是，就迅速得到相应高速缓存和slab描述符的地址。因此，cache_grow()扫描分配给新slab的页框的所有页描述符，并将高速缓存描述符和slab描述符的地址分别赋给页描述符中lru字段的next和prev子字段。这项工作不会出错，因为只有当页框空闲时伙伴系统的函数才会使用lru字段，而只要涉及伙伴系统，slab 分配器函数所处理的页框就不空闲并将PG_slab标志置位。

接着，cache_grow()调用cache_init_objs()，它将构造方法（如果定义了的话）在新slab 上添加对象。

最后，cache_grow()调用list_add_tail()来将新得到的slab 描述符*slabp，添加到高速缓存描述符*cachep的全空slab 链表的末端，并更新高速缓存中的空闲对象计数器：

1
2

list_add_tail(&slabp->list, &cachep->lists->slabs_free);
cachep->lists->free_objects += cachep->num;

从高速缓存中释放slab

在两种条件下才能撤销slab：

• slab 高速缓存中有太多的空闲对象。
• 被周期性调用的定时器函数确定是否有完全未使用的slab 能被释放。

在两种情况下，调用slab_destroy()函数撤销一个slab，并释放相应的页框到分区页框分配器：

1
2
3
4
5
6
7
8
9
10
11

void slab_destroy(kmem_cache_t *cachep, slab_t *slabp) {
    if(cachep_dtor) {
        for(int i = 0; i < cachep->num; i ++) {
            void *objp = slabp->s_mem + cachep->objsize * i;
            (cachep->dtor)(objp, cachep, 0);
        }
    }
    kmem_freepages(cachep, slabp->s_mem - slabp->colouroff);
    if(cachep->flags && CFLAGS_OFF_SLAB)
        kmem_cache_free(cachep->slabp_cache, slabp);
}

这个函数检查高速缓存是否为它的对象提供了析构方法，如果是，就使用析构方法释放slab 中的所有对象。objp 局部变量记录当前已检查的对象。接下来，又调用kmem_freepages()，该函数把slab 使用的所有连续页框返回给伙伴系统。最后，如果slab 描述符存放在slab 的外面，那么，就从slab 描述符的高速缓存释放这个slab 描述符。

对象描述符

每个对象都有类型为kmem_bufctl_t的一个描述符，对象描述符放在数组中，位于相应的slab描述符之后，两种可能的存放：

• 外部对象描述符：在slab外面，位于高速缓存描述符的slabp_cache字段指向的一个普通高速缓存中。
• 内部对象描述符：在slab内部，正好位于描述符所描述的对象之前。

数组中的第一个对象描述符描述slab中的第一个对象，依次类推。它包含的是下一个空闲对象在slab中的下标，因此实现了slab内部空闲对象的一个简单链表。空闲对象链表中的最后一个元素的对象描述符用常规值BUFCTL_END（0xffff）标记。例如，某个slab中有16个对象，其中只有1、3、5号对象空闲。那么1号对象描述符的值为3，3号对象描述符的值为5，5号对象描述符的值为BUFCTL_END。

对齐内存中的对象

slab 分配器所管理的对象可以在内存中进行对齐，也就是说，存放它们的内存单元的起始物理地址是一个给定常量的倍数，通常是2的倍数。这个常量就叫对齐因子（alignment factor）。

slab分配器所允许的最大对齐因子是4096，即页框大小。这就意味着通过访问对象的物理地址或线性地址就可以对齐对象。在这两种情况下，只有最低的12 位才可以通过对齐来改变。

通常情况下，如果内存单元的物理地址是字大小（即计算机的内部内存总线的宽度）对齐的， 那么， 微机对内存单元的存取会非常快。因此，缺省情况下，kmem_cache_create()函数根据BYTES_PER_WORD宏所指定的字大小来对齐对象。对于80x86 处理器，这个宏产生的值为4，因为字长是32 位。

当创建一个新的slab高速缓存时，就可以让它所包含的对象在第一级硬件高速缓存中对齐。为了做到这点，设置SLAB_HWCACHE_ALIGN高速缓存描述符标志。kmem_cache_create()函数按如下方式处理请求：

• 如果对象的大小大于高速缓存行（cache line）的一半，就在RAM中根据L1_CACHE_BYTES的倍数（也就是行的开始）对齐对象。
• 否则，对象的大小就是L1_CACHE_BYTES的因子取整。这可以保证一个小对象不会横跨两个高速缓存行。

显然，slab 分配器在这里所做的事情就是以内存空间换取访问时间，即通过人为地增加对象的大小来获得较好的高速缓存性能，由此也引起额外的内碎片。

slab着色

在CPU中，同一硬件高速缓存行可以映射RAM中不同的块。高速缓存的硬件可能因此而花费内存周期在同一高速缓存行与RAM内存单元之间来来往往传送两个对象，而其他的高速缓存行并未充分使用。slab 分配器通过一种叫做slab 着色的策略，尽量降低高速缓存的这种不愉快行为：把叫做颜色的不同随机数分配给slab。

在讨论slab着色之前，我们再回顾一下高速缓存内对象的布局。让我们考虑某个高速缓存，它的对象在RAM中被对齐。这就意味着对象的地址肯定是某个给定正数值（比如说aln，我们设aln=0x100）的倍数。连对齐的约束也考虑在内，在slab 内放置对象就有很多种可能的方式。方式的选择取决于对下列变量所做的决定：

• num：可以在slab 中存放的对象个数（其值在高速缓存描述符的num 字段中）。
• osize：对象的大小，包括对齐的字节。
• dsize：slap描述符的大小加上所有对象描述符的大小，就等于硬件高速缓存行大小的最小倍数。如果slab 描述符和对象描述符都存放在slap 的外部，那么这个值等于0。
• free：在slab 内未用字节（没有分配给任一对象的字节）的个数。

一个slab 中的总字节长度可以表示为如下表达式：

1

slab 的长度 = (num × osize) + dsize + free

free 总是小于osize，因为否则的话，就有可能把另外的对象放在slab 内。不过，free 可以大于aln。

slab 分配器利用空闲未用的字节free 来对slab着色。术语着色只是用来再细分slab，并允许内存分配器把对象展开在不同的线性地址之中。这样的话，内核从微处理器的硬件高速缓存中可能获得最好性能。

具有不同颜色的slab把slab的第一个对象存放在不同的内存单元，同时满足对齐约束。可用颜色的个数是free/aln（这个值存放在高速缓存描述符的colour 字段）。因此，第一个颜色表示为0，最后一个颜色表示为(free/aln)-1。（一种特殊情况是，如果free 比aln 小，那么colour 被设为0，不过所有slab 都使用颜色0，因此颜色真正的个数为1。）

如果用颜色col 对一个slab 着色，那么，第一个对象的偏移量（相对于slab 的起始地址）就等于col × aln + dsize字节。图8-6 显示了slab 内对象的布局对slab 颜色的依赖情况。着色本质上导致把slab 中的一些空闲区域从末尾移到开始。

只有当free 足够大时，着色才起作用。显然，如果对象没有请求对齐，或者如果slab 内的未用字节数小于所请求的对齐（free ≤ aln），那么，唯一可能着色的slab 就是具有颜色0 的slab，也就是说，把这个slab 的第一个对象的偏移量赋为0。

通过把当前颜色存放在高速缓存描述符的colour_next字段，就可以在一个给定对象类型的slab 之间平等地发布各种颜色。cache_grow()函数把colour_next所表示的颜色赋给一个新的slab，并递增这个字段的值。当colour_next的值变为colour后，又从0 开始。这样，每个新创建的slab 都与前一个slab 具有不同的颜色，直到最大可用颜色。此外，cache_grow()函数从高速缓存描述符的colour_off字段获得值aln，根据slab内对象的个数计算dsize，最后把col×aln+dsize的值存放到slab描述符的colouroff字段中。

空闲slab对象的本地高速缓存

为了减少处理器之间对自旋锁的竞争并更好的利用硬件高速缓存，slab分配器的每个高速缓存包含一个被称作slab本地高速缓存的每CPU数据结构，该结构由一个指向被释放对象的小指针数组组成。slab对象的大多数分配和释放只影响本地数组，只有在本地数组下溢或上溢时才涉及slab数据结构。

高速缓存描述符的array字段是一组指向array_cache数据结构的指针，系统中每个CPU对应于一个元素。每个array_cache数据结构是空闲对象的本地高速缓存的一个描述符。

本地高速缓存描述符并不包含本地高速缓存本身的地址；事实本地高速缓存本身的地址在本地高速缓存描述符之后。本地高速缓存存放的是指向已经释放的对象的指针，而不是对象本身，对象本身总是位于高速缓存的slab中。

当创建一个新的slab高速缓存时，kmem_cache_create()函数决定本地高速缓存大小、分配本地高速缓存，并将它们的指针存放在高速缓存描述符的array字段。

多处理器系统中，小对象使用的slab高速缓存同样包含一个附加的本地高速缓存，他的地址被存放在高速缓存描述符的lists.shared中，被所有的CPU共享，它使得将空闲对象从一个本地高速缓存移动到另一个高速缓存的任务更加容易。

分配slab对象

通过调用kmem_cache_alloc()函数获得新对象。参数cachep指向高速缓存描述符，新空闲对象必须从该高速缓存描述符获得，而参数flag表示传递给分区页框分配器函数的标志，该高速缓存的所有slab应当是满的。该函数本质上等价于下列代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void * kmem_cache_alloc(kmem_cache_t *cachep, int flags)
{
    unsigned long save_flags;
    void *objp;
    struct array_cache *ac;

    local_irq_save(save_flags);
    ac = cache_p->array[smp_processor_id()];
    if (ac->avail) {
        ac->touched = 1;
        objp = ((void **)(ac+1))[--ac->avail];
    } else
        objp = cache_alloc_refill(cachep, flags);
    local_irq_restore(save_flags);
    return objp;
}

cache_alloc_refill()函数本质上执行如下步骤：

1. 将本地高速缓存描述符的地址存放在ac 局部变量中：ac = cachep->array[smp_processor_id()];
2. 获得cachep->spinlock。
3. 如果slab高速缓存包含共享本地高速缓存，并且该共享本地高速缓存包含一些空闲对象，函数就通过从共享本地高速缓存中上移ac->batchcount个指针来重新填充CPU 的本地高速缓存。然后，函数跳到第6 步。
4. 函数试图填充本地高速缓存， 填充值为高速缓存的slab中包含的多达ac->batchcount个空闲对象的指针：
   1. 查看高速缓存描述符的slabs_partial和slabs_free链表，并获得slab 描述符的地址slabp，该slab描述符的相应slab或者部分被填充，或者为空。如果不存在这样的描述符，则函数转到第5 步。
   2. 对于slab 中的每个空闲对象，函数增加slab描述符的inuse字段，将对象的地址插入本地高速缓存，并更新free字段使得它存放了slab 中下一个空闲对象的下标：
   3. slabp->inuse++;，((void**)(ac+1))[ac->avail++] = slabp->s_mem + slabp->free * cachep->obj_size;，slabp->free = ((kmem_bufctl_t*)(slabp+1))[slabp->free];
   4. 如果必要，将清空的slab 插入到适当的链表上，可以是slab_full链表，也可以是slab_partial链表。
5. 在这一步，被加到本地高速缓存上的指针个数被存放在ac->avail字段：函数递减同样数量的kmem_list3结构的free_objects字段来说明这些对象不再空闲。
6. 释放cachep->spinlock。
7. 如果现在ac->avail字段大于0（一些高速缓存再填充的情况发生了），函数将ac->touched字段设为1，并返回最后插入到本地高速缓存的空闲对象指针：return ((void**)(ac+1))[--ac->avail];
8. 否则，没有发生任何高速缓存再填充情况：调用cache_grow()获得一个新slab，从而获得了新的空闲对象。
9. 如果cache_grow()失败了，则函数返回NULL；否则它返回到第1 步重复该过程。

释放Slab对象

kmem_cache_free()函数释放一个曾经由slab分配器分配给某个内核函数的对象。它的参数为cachep和objp，前者是高速缓存描述符的地址，而后者是将被释放对象的地址：

1
2
3
4
5
6
7
8
9
10
11
12

void kmem_cache_free(kmem_cache_t *cachep, void *objp)
{
    unsigned long flags;
    struct array_cache *ac;

    local_irq_save(flags);
    ac = cachep->array[smp_processor_id()];
    if (ac->avail == ac->limit)
        cache_flusharray(cachep, ac);
    ((void**)(ac+1))[ac->avail++] = objp;
    local_irq_restore(flags);
}

cache_flusharray()函数执行如下操作：

1. 获得cachep->spinlock自旋锁。
2. 如果slab高速缓存包含一个共享本地高速缓存，并且如果该共享本地高速缓存还没有满，函数就通过从CPU的本地高速缓存中上移ac->batchcount个指针来重新填充共享本地高速缓存。
3. 调用free_block()函数将当前包含在本地高速缓存中的ac->batchcount个对象归还给slab 分配器。对于在地址objp处的每个对象，函数执行如下步骤：
   1. 增加高速缓存描述符的lists.free_objects字段。
   2. 确定包含对象的slab 描述符的地址：slabp = (struct slab *)(virt_to_page(objp)->lru.prev);，请记住，slab 页的描述符的lru.prev 字段指向相应的slab 描述符。
   3. 从它的slab 高速缓存链表（cachep->lists.slabs_partial或是cachep->lists.slabs_full）上删除slab 描述符。
   4. 计算slab 内对象的下标：objnr = (objp - slabp->s_mem) / cachep->objsize;
   5. 将slabp->free的当前值存放在对象描述符中，并将对象的下标放入slabp->free（最后被释放的对象将再次成为首先被分配的对象）：((kmem_bufctl_t *)(slabp+1))[objnr] = slabp->free;，slabp->free = objnr;
   6. 递减slabp->inuse字段。
   7. 如果slabp->inuse等于0（也就是slab 中所有对象空闲），并且整个slab 高速缓存中空闲对象的个数(cachep->lists.free_objects)大于cachep->free_limit字段中存放的限制，那么函数将slab 的页框释放到分区页框分配器：cachep->lists.free_objects -= cachep->num;，lab_destroy(cachep, slabp);。放在cachep->free_limit字段中的值通常等于cachep->num+(1+N)×cachep->batchcount，其中N 代表系统中CPU 的个数。
   8. 否则，如果slab->inuse等于0，但整个slab 高速缓存中空闲对象的个数小于cachep->free_limit，函数就将slab描述符插入到cachep->lists.slabs_free链表中。
   9. 最后，如果slab->inuse大于0，slab 被部分填充，则函数将slab 描述符插入到cachep->lists.slabs_partial链表中。
4. 释放cachep->spinlock自旋锁。
5. 通过减去被移到共享本地高速缓存或被释放到slab分配器的对象的个数来更新本地高速缓存描述符的avail 字段。
6. 移动本地高速缓存数组起始处的那个本地高速缓存中的所有指针。这一步是必需的，因为已经把第一个对象指针从本地高速缓存上删除，因此剩下的指针必须上移。

通用对象

初始化阶段建立了一些高速缓存包含用作通用用途的类型的slab对象。如果对存储区的请求不频繁，就用一组普通高速缓存来处理，普通高速缓存中的对象具有几何分布的大小，范围为32～131072 字节。

调用kmalloc()函数就可以得到这种类型的对象，函数等价于下列代码片段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void * kmalloc(size_t size, int flags)
{
    struct cache_sizes *csizep = malloc_sizes;
    kmem_cache_t * cachep;
    for (; csizep->cs_size; csizep++) {
        if (size > csizep->cs_size)
            continue;
        if (flags & _ _GFP_DMA)
            cachep = csizep->cs_dmacachep;
        else
            cachep = csizep->cs_cachep;
        return kmem_cache_alloc(cachep, flags);
    }
    return NULL;
}

调用kmalloc()所获得的对象可以通过调用kfree()来释放：

1
2
3
4
5
6
7
8
9
10
11

void kfree(const void *objp)
{
    kmem_cache_t * c;
    unsigned long flags;
    if (!objp)
        return;
    local_irq_save(flags);
    c = (kmem_cache_t *)(virt_to_page(objp)->lru.next);
     kmem_cache_free(c, (void *)objp);
    local_irq_restore(flags);
}

内存池

内存池（memory pool）是Linux 2.6 的一个新特性，主要供一些驱动程序使用。基本上讲，一个内存池允许一个内核成分，如块设备子系统，仅在内存不足的紧急情况下分配一些动态内存来使用。

一个内存池常常叠加在slab 分配器之上 —— 也就是说，它被用来保存slab 对象的储备。但是一般而言，内存池能被用来分配任何一种类型的动态内存，从整个页框到使用kmalloc()分配的小内存区。因此，我们一般将内存池处理的内存单元看作内存元素。

内存池由mempool_t对象描述，它的字段如下所示。

min_nr字段存放了内存池中元素的初始个数。换句话说，存放在该字段中的值代表了内存元素的个数，内存池的拥有者确信能从内存分配器得到这个数目。curr_nr字段总是低于或等于min_nr，它存放了内存池中当前包含的内存元素个数。内存元素自身被一个指针数组引用，指针数组的地址存放在elements字段中。

alloc和free方法与基本的内存分配器进行交互，分别用于获得和释放一个内存元素。两个方法可以是拥有内存池的内核成分提供的定制函数。
当内存元素是slab对象时，alloc和free方法一般由mempool_alloc_slab()和mempool_free_slab()函数实现，它们只是分别调用kmem_cache_alloc()和kmem_cache_free()函数。在这种情况下，mempool_t对象的pool_data字段存放了slab高速缓存描述符的地址。

mempool_create()函数创建一个新的内存池；它接收的参数为内存元素的个数min_nr、实现alloc和free方法的函数的地址和赋给pool_data字段的任意值。该函数分别为mempool_t对象和指向内存元素的指针数组分配内存，然后反复调用alloc方法来得到min_nr个内存元素。相反地，mempool_destroy()函数释放池中所有内存元素，然后释放元素数组和mempool_t对象自己。

为了从内存池分配一个元素，内核调用mempool_alloc()函数，将mempool_t对象的地址和内存分配标志传递给它。函数本质上依据参数所指定的内存分配标志，试图通过调用alloc方法从基本内存分配器分配一个内存元素。如果分配成功，函数返回获得的内存元素而不触及内存池。否则，如果分配失败，就从内存池获得内存元素。当然，在内存不足的情况下过多的分配会用尽内存池：在这种情况下，如果__GFP_WAIT标志没有置位，则mempool_alloc()阻塞当前进程直到有一个内存元素被释放到内存池中。

相反地，为了释放一个元素到内存池，内核调用mempool_free()函数。如果内存池未满（curr_min小于min_nr），则函数将元素加到内存池中。否则，mempool_free()调用free方法来释放元素到基本内存分配器。

非连续内存区管理

把内存区映射到一组连续的页框是最好的选择，这样可以充分利用高速缓存就并获得较低的平均访问时间。不过，如果对内存区的请求不是很频繁，那通过连续的线性地址来访问非连续的页框这样一种分配方式将会很有意义，因为这样可以避免外部碎片，而缺点是必须打乱内核页表。显然，非连续内存区的大小必须是4096的倍数。

非连续内存的线性地址

查找线性地址的空闲区，可以从PAGE_OFFSET开始查找（通常为0xc0000000，即第四个GB的起始地址）：

• 内存区的开始部分包含的是对前896MB RAM进行映射的线性地址。直接映射的物理内存末尾所对应的线性地址保存在high_memory全局变量中。当物理内存小于896MB，则线性地址0xc0000000以后的896MB与其一一对应；当物理内存大于896MB而小于4GB时，只直接映射前896MB的地址到0xc0000000以后的线性空间，然后把线性空间的其他部分与896MB和4GB物理空间映射起来，称为动态重映射；当物理内存大于4GB，则需要考虑PAE的情况。
• 从PKMAP_BASE开始，我们查找用于高端内存页框的永久内核映射的线性地址。
• 其余的线性地址可以用于非连续内存区。在物理内存映射的末尾与第一个内存区之间插入一个大小为8MB（宏VMALLOC_OFFSET）的安全区，目的是为了“捕获”对内存的越界访问。出于同样的理由，插入其他4KB 大小的安全区来隔离非连续的内存区。

为非连续内存区保留的线性地址空间的起始地址由VMALLOC_START宏定义，而末尾地址由VMALLOC_END宏定义。

非连续内存区的描述符

每个非连续内存区都对应着一个类型为vm_struct的描述符：

通过next字段，这些描述符被插入到一个简单的链表中，链表第一个元素的地址存放在vmlist变量中。对这个链表的访问依靠vmlist_lock读/ 写自旋锁来保护。flags字段标识了非连续区映射的内存的类型：

• VM_ALLOC表示使用vmalloc()得到的页；
• VM_MAP表示使用vmap()映射的已经被分配的页；
• VM_IOREMAP表示使用ioremap()映射的硬件设备的板上内存。

get_vm_area()函数在线性地址VMALLOC_START和VMALLOC_END之间查找一个空闲区域。该函数使用两个参数：将被创建的内存区的字节大小（size）和指定空闲区类型的标志（flag）。步骤执行如下：

1. 调用kmalloc()为vm_struct类型的新描述符获得一个内存区。
2. 为写得到vmlist_lock锁，并扫描类型为vm_struct的描述符链表来查找线性地址一个空闲区域，至少覆盖size + 4096个地址（4096 是内存区之间的安全区间大小）。
3. 如果存在这样一个区间，函数就初始化描述符的字段，释放vmlist_lock锁，并以返回这个非连续内存区的起始地址而结束。
4. 否则，get_vm_area()释放先前得到的描述符，释放vmlist_lock，然后返回NULL。

分配非连续内存区

vmalloc()函数给内核分配一个非连续内存区。参数size表示所请求内存区的大小。如果这个函数能够满足请求，就返回新内存区的起始地址；否则，返回一个NULL指针（mm/vmalloc.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

void * vmalloc(unsigned long size)
{
    struct vm_struct *area;
    struct page **pages;
    unsigned int array_size, i;
    size = (size + PAGE_SIZE - 1) & PAGE_MASK;
    area = get_vm_area(size, VM_ALLOC);
    if (!area)
        return NULL;
    area->nr_pages = size >> PAGE_SHIFT;
    array_size = (area->nr_pages * sizeof(struct page *));
    area->pages = pages = kmalloc(array_size, GFP_KERNEL);
    if (!area->pages) {
        remove_vm_area(area->addr);
        kfree(area);
        return NULL;
    }
    memset(area->pages, 0, array_size);
    for (i=0; i<area->nr_pages; i++) {
        area->pages[i] = alloc_page(GFP_KERNEL|_ _GFP_HIGHMEM);
        if (!area->pages[i]) {
            area->nr_pages = i;
    fail:   vfree(area->addr);
            return NULL;
       }
    }
    if (map_vm_area(area, _ _pgprot(0x63), &pages) )
        goto fail;
    return area->addr;
}

简要介绍一下memset(area->pages, 0, array_size)的实现函数：

1
2
3
4
5
6
7
8
9
10
11

static inline void * __memset_generic(void * s, char c,size_t count)
{
int d0, d1;
__asm__ __volatile__(
    "rep/n/t"
    "stosb"
    : "=&c" (d0), "=&D" (d1)
    :"a" (c),"1" (s),"0" (count)
    :"memory");
return s;
}

到这里，已经得到了一个新的连续线性地址区间，并且已经分配了一组非连续页框来映射这些线性地址。最后至关重要的步骤是修改内核使用的页表项 ，以此表明分配给非连续内存区的每个页框现在对应着一个线性地址，这个线性地址被包含在vmalloc()产生的非连续线性地址区间中。这就是map_vm_area()所要做的，下面来详细说说:

map_vm_area()函数使用以下3 个参数：

• area：指向内存区的vm_struct描述符的指针。
• prot：已分配页框的保护位。它总是被置为0x63，对应着Present、Accessed、Read/Write 及Dirty。
• pages：指向一个指针数组的变量的地址，该指针数组的指针指向页描述符（因此，struct page ***被当作数据类型使用！）。

函数首先把内存区的开始和末尾的线性地址分别分配给局部变量address和end：

1
2

address = area->addr;
end = address + (area->size - PAGE_SIZE);

1
2

pgd = pgd_offset_k(address);
spin_lock(&init_mm.page_table_lock);

然后，函数执行下列循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int ret = 0;
for (i = pgd_index(address); i < pgd_index(end-1); i++) {
    pud_t *pud = pud_alloc(&init_mm, pgd, address);
    ret = -ENOMEM;
    if (!pud)
        break;
    next = (address + PGDIR_SIZE) & PGDIR_MASK;
    if (next < address || next > end)
        next = end;
    if (map_area_pud(pud, address, next, prot, pages))
        break;
    address = next;
    pgd++;
    ret = 0;
}
spin_unlock(&init_mm.page_table_lock);
flush_cache_vmap((unsigned long)area->addr, end);
return ret;

循环结束的条件是：指向非连续内存区的所有页表项全被建立。

map_area_pud()函数为页上级目录所指向的所有页表执行一个类似的循环：

1
2
3
4
5
6
7
8
9

do {
    pmd_t * pmd = pmd_alloc(&init_mm, pud, address);
    if (!pmd)
        return -ENOMEM;
    if (map_area_pmd(pmd, address, end-address, prot, pages))
        return -ENOMEM;
    address = (address + PUD_SIZE) & PUD_MASK;
    pud++;
} while (address < end);

1
2
3
4
5
6
7
8
9

do {
    pte_t * pte = pte_alloc_kernel(&init_mm, pmd, address);
    if (!pte)
        return -ENOMEM;
    if (map_area_pte(pte, address, end-address, prot, pages))
        return -ENOMEM;
    address = (address + PMD_SIZE) & PMD_MASK;
    pmd++;
} while (address < end);

map_area_pte()的主循环为：

1
2
3
4
5
6
7

do {
    struct page * page = **pages;
    set_pte(pte, mk_pte(page, prot));
    address += PAGE_SIZE;
    pte++;
    (*pages)++;
} while (address < end);

注意，map_vm_area()并不触及当前进程的页表。因此，当内核态的进程访问非连续内存区时，缺页发生，因为该内存区所对应的进程页表中的表项为空。然而，缺页处理程序要检查这个缺页线性地址是否在主内核页表中（也就是init_mm.pgd页全局目录和它的子页表）。一旦处理程序发现一个主内核页表含有这个线性地址的非空项，就把它的值拷贝到相应的进程页表项中，并恢复进程的正常执行。

除了vmalloc()函数之外，非连续内存区还能由vmalloc_32()函数分配，该函数与vmalloc()很相似，但是它只从ZONE_NORMAL和ZONE_DMA内存管理区中分配页框。

Linux 2.6 还特别提供了一个vmap()函数，它将映射非连续内存区中已经分配的页框：本质上，该函数接收一组指向页描述符的指针作为参数，调用get_vm_area()得到一个新vm_struct描述符，然后调用map_vm_area()来映射页框。因此该函数与vmalloc()相似，但是它不分配页框。

释放非连续内存区

vfree()函数释放vmalloc()或vmalloc_32()创建的非连续内存区，而vunmap()函数释放vmap()创建的内存区。两个函数都使用同一个参数 —— 将要释放的内存区的起始线性地址address；它们都依赖于__vunmap()函数来做实质性的工作。

__vunmap()函数接收两个参数：将要释放的内存区的起始地址的地址addr，以及标志deallocate_pages，如果被映射到内存区内的页框应当被释放到分区页框分配器（调用vfree()）中，那么这个标志被置位，否则被清除（vunmap()被调用）。该函数执行以下操作：

1. 调用remove_vm_area()函数得到vm_struct描述符的地址area，并清除非连续内存区中的线性地址对应的内核的页表项。
2. 如果deallocate_pages被置位，函数扫描指向页描述符的area->pages指针数组；对于数组的每一个元素，调用__free_page()函数释放页框到分区页框分配器。此外，执行kfree(area->pages)来释放数组本身。
3. 调用kfree(area)来释放vm_struct描述符。

remove_vm_area()函数执行如下循环：

1
2
3
4
5
6
7
8
9
10

write_lock(&vmlist_lock);
for (p = &vmlist ; (tmp = *p) ; p = &tmp->next) {
    if (tmp->addr == addr) {
        unmap_vm_area(tmp);
        *p = tmp->next;
        break;
    }
}
write_unlock(&vmlist_lock);
return tmp;

1
2
3
4
5
6
7
8
9
10
11

address = area->addr;
end = address + area->size;
pgd = pgd_offset_k(address);
for (i = pgd_index(address); i <= pgd_index(end-1); i++) {
    next = (address + PGDIR_SIZE) & PGDIR_MASK;
    if (next <= address || next > end)
        next = end;
    unmap_area_pud(pgd, address, next - address);
    address = next;
    pgd++;
}

1
2
3
4
5

do {
    unmap_area_pmd(pud, address, end-address);
    address = (address + PUD_SIZE) & PUD_MASK;
    pud++;
} while (address && (address < end));

1
2
3
4
5

do {
    unmap_area_pte(pmd, address, end-address);
    address = (address + PMD_SIZE) & PMD_MASK;
    pmd++;
} while (address < end);

1
2
3
4
5
6
7

do {
    pte_t page = ptep_get_and_clear(pte);
    address += PAGE_SIZE;
    pte++;
    if (!pte_none(page) && !pte_present(page))
        printk("Whee... Swapped out page in kernel page table/n");
} while (address < end);

与vmalloc()一样，内核修改主内核页全局目录和它的子页表中的相应项，但是映射第4个GB的进程页表的项保持不变。这是在情理之中的，因为内核永远也不会收回扎根于主内核页全局目录中的页上级目录、页中间目录和页表。

例如，假定内核态的进程访问一个随后要释放的非连续内存区。进程的页全局目录项等于主内核页全局目录中的相应项，由于“缺页异常处理程序”博文中所描述的机制，这些目录项指向相同的页上级目录、页中间目录和页表。unmap_area_pte()函数只清除页表中的项（不回收页表本身）。进程对已释放非连续内存区的进一步访问必将由于空的页表项而触发缺页异常。但是，缺页处理程序会认为这样的访问是一个错误，因为主内核页表不包含有效的表项。

进程地址空间

内核中的函数以相当直接了当的方式获得动态内存。当给用户态进程分配内存时，情况完全不同了：

• 进程对动态内存的请求被认为是不紧迫的，一般来说，内核总是尽量推迟给用户态进程分配内存。
• 由于用户进程时不可信任的，因此，内核必须能随时准备捕获用户态进程引起的所有寻址错误。

当用户态进程请求动态内存时，并没有获得请求的页框，而仅仅获得对一个新的线性地址区间的使用权，而这一线性地址区间就成为进程地址空间的一部分。

进程地址空间

进程地址空间由允许进程使用的全部线性地址组成。内核可以通过增加或删除某些线程地址区间来动态地修改进程的地址空间。内核通过所谓线性去得资源来标示线性地址区间，线性区是由起始线性地址、长度和一些访问权限来描述的。进程获得新线性区的一些典型情况：

1. 用户在控制台输入一条命令时，shell进程创建一个新的进程去执行这个命令。结果是，一个全新的地址空间（也就是一组线性区）分配给新进程。
2. 正在运行的进程有可能决定装入一个完全不同的程序。这时，进程描述符不变，可是在装入这个程序以前所有的线性区却被释放，并有一组新的线性区被分配给这个进程。
3. 正在运行的进程可能对一个文件执行内存映像。
4. 进程可能持续向他的用户态堆栈增加数据，知道映像这个堆栈的线性区用完为止，此时，内核也许会决定扩展这个线性区的大小。
5. 进程可能创建一个IPC共享线性区来与其他合作进程共享数据。此时，内核给这个进程分配一个新的线性区以实现这个方案。
6. 进程可能通过调用类似malloc这样的函数扩展自己的动态堆。结果是，内核可能决定扩展给这个堆所分配的线性区。

内存描述符

数据结构描述

进程描述符task_struct中的mm字段描述了进程地址空间：

所有内存描述符存放在一个双向链表中，每个描述符在mmlist字段存放相邻元素的地址。链表的每一个元素是init_mm的mmlist字段，init_mm是初始化阶段进程0所使用的内存描述符。mmlist_lock自旋锁保护多处理器系统对链表的同时访问。

mm_user字段存放共享mm_struct数据结构的轻量级进程的个数。mm_count字段是内存描述符的主使用计数器，在mm_users次使用计数器中的所有用户在mm_count中只作为一个单位。每当mm_count递减时，内核都要检查它是否变为0，如果是，就要解除这个内存描述符，因为不再有用户使用它。

以下例子解释mm_users和mm_count之间的不同。考虑一个内存描述符由两个轻量级进程共享。它的mm_users字段通常存放的值为2，而mm_count字段存放的值为1(两个所有者进程算作一个)。

如果把内存描述符暂时借给一个内核线程，那么，内核就增加mm_count。这样即两个轻量级进程都死亡，且mm_users字段变为0，这个内存描述符也不被释放，直到内核线程使用完为止，因为mm_count字段仍然大于0。

如果内核想确保内存描述符在一个长操作的中间不被释放，那么就应该增加mm_users字段，而不是mm_count字段的值. 最终的结果是相同的，因为mm_users的增加确保了mm_count来变为0，即使拥有这个内存描述符的所有轻量级进程全部死亡。

mm_alloc()函数用来从slab分配器高速缓存中获取一个新的内存描述符。mm_alloc()调用kmem_cache_alloc()来初始化新的内存描述符，并把mm_count和mm_users字段都置为1。mmput()函数递减内存描述符的mm_users字段。如果该字段变为0，这个函数就释放局部描述符表/线性区描述符及由内存描述符所引用的页表，并调用mmdrop()后一个函数把mm_count字段减1，如果该字段变为0，就释放mm_struct数据结构。

内核线程的内存描述符

内核线程仅运行在内核态，它们永远不会访问TASK_SIZE(等于PAGE_OFFSET，x86下通常为0xC0000000)以下的地址。内核线程不用线性区，因而内存描述符的很多字段对内核线程没有意义。大于TASK_SIZE线性地址的相应页表项都是相同的，因此一个内核线程到底使用什么样的页表集根本没关系。为了避免无用的TLB和高速缓存刷新，内核线程使用一组最近运行的普通进程的页表。进程描述符用mm和active_mm处理此情况。

mm字段指向进程所拥有的内存描述符，active_mm字段指向进程运行时所使用的内存描述符。对普通进程而言，这两个字段存放相同的指针。但是，内核线程不拥有内存描述符，因此它们的mm字段总是NULL。内核线程运行时，它的active_mm字段被初始化为前一个运行进程的active_mm值。

内核态的进程为高于TASK_SIZE的线性地址修改页表项，那么它也就应当更新系统中所有进程页表集合中的相应表项。事实上，一旦内核态的一个进程进行了设置。映射应该对内核态的其他所有进程都有效.触及所有进程的页表集合是相当费时的操作，因此，linux采用延迟方式。每当一个高端地址必须被重新映射时，内核就更新根目录在swapper_pg_dir主内存页全局目录中的常规页表集合。这个页全局目录由主内存描述符的pgd字段指向，而主内存描述符存放于init_mm变量。

线性区

Linux通过vm_area_struct的对象实现线性区：

每个线性区描述符表示一个线性地址区间。vm_start字段指向线性区的第一个线性地址，而vm_end字段指向线性区之后的第一个线性地址。vm_end - vm_start表示线性区的长度。vm_mm字段指向拥有这个区间的进程的mm_struct内存描述符。

进程所拥有的线性区从来不重叠，并且内核尽力把新分配的线性区与紧邻的现有线性区进行合并。如果两个线性区的访问权限相匹配，则合并。

vm_ops指向vm_operations_struct结构，存放的是线性区的方法，以下四种方法可应用于UMA系统：

mmap_cache字段保存进程最后一次引用线性区的描述符地址，引用此字段可减少查找一个给定线性地址所在线性区花费的时间。

线性区数据结构

进程所拥有的所有线性区是通过一个简单的链表链接在一起的。每个vm_area_struct元素的vm_next字段指向链表的下一个元素。内核通过进程的内存描述符的nmap字段来查找线性区，其中nmap字段指向链表中的第一个线性区描述符。内存描述符中的map_count字段存放进程所拥有的线性区数目。默认情况下，一个进程可以最多拥有65536个不同的线性区。

进程地址空间、内存描述符和线性区链表之间的关系：

内核频繁执行的一个操作是查找包含指定线性地址的线性区。只要在指定线性地址之后找到一个线性区，搜索就可以结束。多数Linux的线性区非常少，但是如果线性区过于庞大，线性区链表的管理会变得非常低效。

Linux2.6把内存描述符存放在叫做红黑树（read-black-tree）的数据结构中。每个元素（或说节点）通常有两个孩子：左孩子和右孩子。树中的元素被排序。对关键字为N的节点，它的左子树上的所有元素的关键字都比N小；相反，它的右子树上的所有元素的关键字都比N大；节点的关键字被写入节点内部。而除了具有基本的二叉排序树的特点以外，红-黑树必须满足下列5条规则：

1. 每个节点必须或为黑或为红。
2. 树的根必须为黑。
3. 红节点的孩子必须为黑。
4. 从一个节点到后代叶子节点的每个路径都包含相同数量的黑节点。当统计黑节点个数时，空指针也算作黑节点。

这4条规则确保具有n个内部节点的任何红一黑树其高度最多为2 × log(n+1)。在红-黑树中搜索一个元素因此而变得非常高效，因为其操作的执行时间与树大小的对数成线性比例。换句话说，双倍的线性区个数只多增加一次循环。

为了存放进程的线性区，Linux既使用了链表，又使用了红黑树。这两种结构包含指向同一线性区描述符的指针，当插入或删除一个线性区描述符的时候，内核通过红黑树搜索前后元素，并用搜索结果快速更新链表而不用扫描链表。链表的头由内存描述符的mmap字段所指向，任何线性区对象都在vm_next字段存放指向链表下一个元素的指针。红黑树的首部由mm_rb字段所指向，任何线性区对象都在类型为rb_node的vm_rb字段存放节点颜色以及指向双亲、左孩子和右孩子的指针。

一般的，红黑树用来确定含有指定地址的线性区，而链表通常在扫描整个线性区集合时使用。

线性区访问权限

每个线性区都由一组号码连续的页组成。线性区的大小是4KB的倍数（必须包含完整的页），而栈的大小却是任意的。与页相关的几种标志：

• 在每个页表项中存放的几个标志，如Read/Write、Present或User/Supervisor
• 存放在每个页描述符flags字段的一组

第一种标志由80x86硬件用来检查能否执行所请求的寻址类型，第二种则由Linux用于许多不同目的，第三种则被存放在vm_area_struct描述符的vm_flags字段中。一些标志给内核提供关于这个线性区的全部页信息。

线性区描述符所包含的页访问权限可以任意组合。例如，存在这样一种可能性，允许一个线性区中的页可以执行但是不可以读取。为了有效地实现这种保护方案，与线性区的页相关的访问权限（读、写及执行）必须被复制到相应的所有表项中，以便由分页单元直接执行检查。换句话说，页访问权限表示何种类型的访问应该产生一个缺页异常。Linux委派缺页处理程序查找导致缺页的原因，因为缺页处理程序实现了许多页处理策略。

页表标志的初值存放在vm_area_struct描述符的vm_page_prot字段中。当增加一个页时，内核根据vm_page_prot字段的值设置相应页表项中的标志。

然而，并不能把线性区的访问权限直接转换为页保护位：

• 在某些情况下，即使由相应线性区描述符的vm_flags字段所指定的某个页的访问权限允许对该页进行访问，但是，对该页的访问还是应当产生一个缺页异常。例如“写时复制”的情况，内核可能决定把属于两个不同进程的两个完全一样的可写私有页（它的VM_SHARE标志被清0）存入同一个页框中；在这种情况下，无论哪一个进程试图改动这个页都应当产生一个异常。
• 80x86处理器的页表仅有两个保护位，即Read/Write和User/Supervisor标志。此外，一个线性区所包含的任何一个页的User/Supervisor标志必须总置为1，因为用户态进程必须总能够访问其中的页。
• 启用PAE的新近Intel Pentium 4微处理器，在所有64位页表项中支持NX（No eXecute）标志。

如果内核没有被编译成支持PAE，那么Linux采取以下规则以克服80x86微处理器的硬件限制：

• 读访问权限总是隐含着执行访问权限，反之亦然。
• 写访问权限总是隐含着读访问权限。

反之，如果内核被编译成支持PAE，而且CPU有NX标志，Linux就采取不同的规则：

• 行访问权限总是隐含着读访问权限。
• 访问权限总是隐含着读访问权限。

此外，为了能做到“写时复制”中适当推迟页框的分配，只要相应的页不是由多个进程共享，那么这种页框都是写保护的。因此，要根据以下规则精简由读、写、执行和共享访问权限的16种可能组合：

• 如果页具有写和共享两种访问权限，那么，Read/Write位被设置为1。
• 如果页具有读或执行访问权限，但是既没有写也没有共享访问权限，那么，Read/Write位被清0。
• 如果支持NX位，而且页没有执行访问权限，那么，把NX位设置为1。
• 如果页没有任何访问权限，那么，Present位被清0，以便每次访问都产生一个缺页异常。然而，为了把这种情况与真正的页框不存在的情况相区分，Linux还把Page size位置为1

访问权限的每种组合所对应的精简后的保护位存放在protection_map数组的16个元素中（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

pgprot_t protection_map[16] = {
 __P000, __P001, __P010, __P011, __P100, __P101, __P110, __P111,
 __S000, __S001, __S010, __S011, __S100, __S101, __S110, __S111
};

//include/asm-i386/Pgtable.h
#define __P000 PAGE_NONE
#define __P001 PAGE_READONLY
#define __P010 PAGE_COPY
#define __P011 PAGE_COPY
#define __P100 PAGE_READONLY_EXEC
#define __P101 PAGE_READONLY_EXEC
#define __P110 PAGE_COPY_EXEC
#define __P111 PAGE_COPY_EXEC

#define __S000 PAGE_NONE
#define __S001 PAGE_READONLY
#define __S010 PAGE_SHARED
#define __S011 PAGE_SHARED
#define __S100 PAGE_READONLY_EXEC
#define __S101 PAGE_READONLY_EXEC
#define __S110 PAGE_SHARED_EXEC
#define __S111 PAGE_SHARED_EXEC

1
2

#define COPY_EXEC /
 __pgprot(_PAGE_PRESENT | _PAGE_USER | _PAGE_ACCESSED)

线性区的处理

对线性区描述符进行操作的低层函数应当被看作简化了do_map()和do_unmap()实现的辅助函数。这两个函数分别扩大或者缩小进程的地址空间。这两个函数所处的层次比我们这里所考虑函数的层次要高一些，它们并不接受线性区描述符作为参数，而是使用一个线性地址区间的起始地址、长度和访问限权作为参数。

查找给定地址的最邻近区

find_vma()函数有两个参数：进程内存描述符的地址mm和线性地址addr，查找线性区的vm_end字段大于addr的第一个线性区的位置，并返回这个线性区描述符的地址。

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

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

由find_vma()函数所选择的线性区并不一定要包含addr，也就是说vm_end可能会小于addr，因为addr可能位于任何线性区之外，这时候我们就要新建一个线性区对象，但不是在find_vma函数中创建，find_vma函数仅返回mm->mmap_cache，也就是当前的那个vma结构。

每个内存描述符包含一个mmap_cache字段，这个字段保存进程最后一次引用线性区的描述符地址。引进这个附加的字段是为了减少查找一个给定线性地址所在线性区而花费的时间。程序中引用地址的局部性使下面这种情况出现的可能性很大：如果检查的最后一个线性地址属于某一给定的线性区，那么，下一个要检查的线性地址也属于这一个线性区。

因此，该函数一开始就检查由mmap_cache所指定的线性区是否包含addr（vma && vma->vm_end > addr && vma->vm_start <= addr）。如果是，就返回这个线性区描述符的指针：

1
2
3

vma = mm->mmap_cache;
if (vma && vma->vm_end > addr && vma->vm_start <= addr)
    return vma;

否则，必须扫描进程的线性区，红-黑树算法就用到了：

1
2
3
4
5
6
7
8
9
10
11
12

rb_node = mm->mm_rb.rb_node;
vma = NULL;
while (rb_node) {
    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;
}

函数使用的宏rb_entry，从指向红-黑树中一个节点的指针导出相应线性区描述符的地址：

1
2
3
4
5

#define rb_entry(ptr, type, member) container_of(ptr, type, member)
#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)

那么，根据上面的代码，翻译过来就是：

1
2

vma_tmp = ({ typeof( ((vm_area_struct *)0)->vm_rb ) *__mptr = (rb_node); /
        (type *)( (char *)__mptr - ((size_t) &((vm_area_struct *)0)->vm_rb) );})

第一行typeof( ((vm_area_struct *)0)->vm_rb )得到vm_rb的类型，即指向顶地址0的那个vm_area_struct结构vm_rb字段的那个类型，即rb_node类型，把他用一个临时变量__mptr表示，其值为函数类的临时变量rb_node，所以*__mptr就是临时变量rb_node的真实地址值。那么第二行用这个*__mptr减去vm_rb成员相对于vm_area_struct顶部的偏移值，就得到了其宿主的vm_area_struct的地址的真实值，即最后得出对应的线性区vm_area_struct的地址。

函数find_vma_prev()与find_vma()类似，不同的是它把函数选中的前一个线性区描述符的指针赋给附加参数的结果参数pprev。最后，函数find_vma_prepare()确定新叶子节点在与给定线性地址对应的红-黑树中的位置，并返回前一个线性区的地址和要插入的叶子节点的父节点的地址。

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

static struct vm_area_struct *
find_vma_prepare(struct mm_struct *mm, unsigned long addr,
    struct vm_area_struct **pprev, struct rb_node ***rb_link,
    struct rb_node ** rb_parent)
{
    struct vm_area_struct * vma;
    struct rb_node ** __rb_link, * __rb_parent, * rb_prev;

    __rb_link = &mm->mm_rb.rb_node;
    rb_prev = __rb_parent = NULL;
    vma = NULL;

    while (*__rb_link) {
        struct vm_area_struct *vma_tmp;

        __rb_parent = *__rb_link;
        vma_tmp = rb_entry(__rb_parent, struct vm_area_struct, vm_rb);

        if (vma_tmp->vm_end > addr) {
            vma = vma_tmp;
            if (vma_tmp->vm_start <= addr)
                return vma;
            __rb_link = &__rb_parent->rb_left;
        } else {
            rb_prev = __rb_parent;
            __rb_link = &__rb_parent->rb_right;
        }
    }

    *pprev = NULL;
    if (rb_prev)
        *pprev = rb_entry(rb_prev, struct vm_area_struct, vm_rb);
    *rb_link = __rb_link;
    *rb_parent = __rb_parent;
    return vma;
}

查找一个与给定的地址区间相重叠的线性区

find_vma_intersection()函数查找与给定的线性地址区间相重叠的第一个线性区。mm参数指向进程的内存描述符，而线性地址start_addr和end_addr指定这个区间。

1
2
3
4
5
6
7
8

static inline struct vm_area_struct * find_vma_intersection(struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr)
{
    struct vm_area_struct * vma = find_vma(mm,start_addr);

    if (vma && end_addr <= vma->vm_start)
        vma = NULL;
    return vma;
}

如果没有这样的线性区存在，函数就返回一个NULL指针。准确地说，如果find_vma()函数回一个有效的地址，但是所找到的线性区是从这个线性地址区间的末尾开始的，vma就被置为NULL。

查找一个空闲的地址区间

get_unmapped_area()查找进程的地址空间以找到一个可以使用的线性地址区间。len参数指定区间的长度，addr指定必须从哪个地址开始查找。查找成功则返回这个新区间的地址；否则返回错误码-ENOMEM。

1
2

static inline unsigned long get_unmapped_area(struct file * file, unsigned long addr,
  unsigned long len, unsigned long pgoff, unsigned long flags)

如果参数addr不等于NULL，函数就检查所指定的地址是否在用户态空间（if (addr > TASK_SIZE - len)）并与页边界对齐（if (addr & ~PAGE_MASK)）。接下来，函数根据线性地址区间是否应该用于文件内存映射或匿名内存映射，调用两个方法（get_unmapped_area文件操作file->f_op->get_unmapped_area和内存描述符的get_unmapped_area方法current->mm->get_unmapped_area(file, addr, len, pgoff, flags)）中的一个。在前一种情况下，函数执行get_unmapped_area文件操作。

第二种情况下，函数执行内存描述符的get_unmapped_area方法。根据进程的线性区类型，由函数arch_get_unmapped_area()或arch_get_unmapped_area_topdown()实现get_unmapped_area方法。通过系统调用mmap()，每个进程都可能获得两种不同形式的线性区：一种从线性地址0x40000000（1G）开始并向高端地址增长，即所谓的“堆”；另一种正好从用户态堆栈开始并向低端地址增长，即所谓的“栈”。前者就调用arch_get_unmapped_area函数，后者就会调用arch_get_unmapped_area_topdown函数，后面博文会详细讨论。

现在我们讨论函数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

if (len > TASK_SIZE)
    return -ENOMEM;
addr = (addr + 0xfff) & 0xfffff000;
if (addr && addr + len <= TASK_SIZE) {
    vma = find_vma(current->mm, addr);
    if (!vma || addr + len <= vma->vm_start)
        return addr;
}
start_addr = addr = mm->free_area_cache;
for (vma = find_vma(current->mm, addr); ; vma = vma->vm_next) {
    if (addr + len > TASK_SIZE) {
        if (start_addr == (TASK_SIZE/3+0xfff)&0xfffff000)
            return -ENOMEM;
        start_addr = addr = (TASK_SIZE/3+0xfff)&0xfffff000;
        vma = find_vma(current->mm, addr);
    }
    if (!vma || addr + len <= vma->vm_start) {
        mm->free_area_cache = addr + len;
        return addr;
    }
    addr = vma->vm_end;
}

函数首先检查区间的长度是否在用户态下线性地址区间的限长TASK_SIZE（通常为3GB）之内。如果addr不为0，函数就试图从addr开始分配区间。为了安全起见，函数把addr的值调整为4KB的倍数（addr = (addr + 0xfff) & 0xfffff000）。

如果addr等于0或前面的搜索失败，函数arch_get_unmapped_area()就扫描用户态线性地址空间以查找一个可以包含新区的足够大的线性地址范围，但任何已有的线性区都不包括这个地址范围。为了提高搜索的速度，让搜索从最近被分配的线性区后面的线性地址开始（vma = find_vma(current->mm, addr)）。

把内存描述符的字段mm->free_area_cache初始化为用户态线性地址空间的三分之一（通常是1GB，start_addr = addr = (TASK_SIZE/3+0xfff)&0xfffff000），并在以后创建新线性区时对它进行更新。如果函数找不到一个合适的线性地址范围，就从用户态线性地址空间的三分之一的开始处重新开始搜索：其实，用户态线性地址空间的三分之一是为有预定义起始线性地址的线性区（典型的是可执行文件的正文段、数据段和bss段）而保留的。

函数调用find_vma()以确定搜索起点之后第一个线性区终点的位置。可能出现三种情况：

• 如果所请求的区间大于正待扫描的线性地址空间部分（addr + len > TASK-SIZE），函数就从用户态地址空间的三分之一处重新开始搜索，如果已经完成第二次搜索，就返回-ENOMEM（没有足够的线性地址空间来满足这个请求）。
• 刚刚扫描过的线性区后面的空闲区没有足够的大小（vma !＝ NULL && vma->vm_start < addr + len）。此时，继续考虑下一个线性区。
• 如果以上两种情况都没有发生，则找到一个足够大的空闲区，此时，函数返回addr。

向内存描述符链表中插入一个线性区

insert_vm_struct()函数在线性区对象链表和内存描述符的红-黑树中插入一个vm_area_struct结构。这个函数使用两个参数：mm指定进程内存描述符的地址，vmp指定要插入的vm_area_struct对象的地址。线性区对象的vm_start和vm_end字段必定已经初始化过。

该函数调用find_vma_prepare()在红-黑树mm->mm_rb中查找vma应该位于何处：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;

    if (!vma->vm_file) {
        BUG_ON(vma->anon_vma);
        vma->vm_pgoff = vma->vm_start >> PAGE_SHIFT;
    }
    __vma = find_vma_prepare(mm,vma->vm_start,&prev,&rb_link,&rb_parent);
    if (__vma && __vma->vm_start < vma->vm_end)
        return -ENOMEM;
    vma_link(mm, vma, prev, rb_link, rb_parent);
    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
30
31
32
33
34
35
36

static struct vm_area_struct *
find_vma_prepare(struct mm_struct *mm, unsigned long addr,
  struct vm_area_struct **pprev, struct rb_node ***rb_link,
  struct rb_node ** rb_parent)
{
    struct vm_area_struct * vma;
    struct rb_node ** __rb_link, * __rb_parent, * rb_prev;

     __rb_link = &mm->mm_rb.rb_node;
    rb_prev = __rb_parent = NULL;    /* rb_prev内部变量表示vma的前一个vm_area_struct结构在树中的位置 */
    vma = NULL;

    while (*__rb_link) {
        struct vm_area_struct *vma_tmp;

        __rb_parent = *__rb_link;
        vma_tmp = rb_entry(__rb_parent, struct vm_area_struct, vm_rb);

        if (vma_tmp->vm_end > addr) {
            vma = vma_tmp;
            if (vma_tmp->vm_start <= addr)
                return vma;
            __rb_link = &__rb_parent->rb_left;
        } else {
            rb_prev = __rb_parent;
            __rb_link = &__rb_parent->rb_right;
        }
    }

    *pprev = NULL;
    if (rb_prev)
        *pprev = rb_entry(rb_prev, struct vm_area_struct, vm_rb);
    *rb_link = __rb_link;
    *rb_parent = __rb_parent;
    return vma;
}

然后，insert_vm_struct()又调用vma_link()函数：

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

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_link(mm, vma, prev, rb_link, rb_parent);
    __vma_link_file(vma);

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

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

1
2
3
4
5
6
7
8
9

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)
{
    __vma_link_list(mm, vma, prev, rb_parent);
    __vma_link_rb(mm, vma, rb_link, rb_parent);
    __anon_vma_link(vma);
}

vma_link依次执行以下操作：

1. 在mm->mmap所指向的链表中插入线性区
2. 在红-黑树mm->mm_rb中插入线性区
3. 如果线性区是匿名的，就把它插入以相应的anon_vma数据结构作为头节点的链表中（__anon_vma_link(vma)）。
4. 递增mm->map_count计数器（mm->map_count++;）。

如果线性区包含一个内存映射文件，则vma_link()函数执行在回收页框相关博文描述的其他任务。

__vma_unlink()函数接收的参数为一个内存描述符地址mm和两个线性区对象地址vma和prev。两个线性区都应当属于mm，prev应当在线性区的排序中位于vma之前。该函数从内存描述符链表和红-黑树中删除vma，如果mm->mmap_cache（存放刚被引用的线性区）字段指向刚被删除的线性区，则还要对mm->mmap_cache进行更新。

分配线性地址空间

do_mmap()函数为当前进程创建并初始化一个新的线性区。不过分配成功之后，可以把这个新的线性区与进程已有的其他线性区合并。函数相关参数：

• file和offset：如果新的线性区将把一个文件映射到内存，则使用文件描述符指针和文件偏移量offset。
• addr：这个线性地址指定从何时开始查找一个空闲的区间。
• len：线性地址区间的长度。
• prot：这个参数指定这个线性区所包含页的访问权限。

• flag：这个参数指定线性区的其他标志。

  • MAP_GROWSDOWN、MAP_LOCKED、MAP_DENYWRITE和MAP_EXECUTABLE
    • 它们的含义与“线性区数据结构”博文中所列出标志的含义相同。
  • MAP_SHARED和MAP_PRIVATE
    • 前一个标志指定线性区中的页可以被几个进程共享；后一个标志作用和两个标志都指向vm_area_struct描述符中的VM_SHARED标志。
  • MAX_FIXED
    • 区间的起始地址必须是由参数addr所指定的。
  • MAX_ANONYMOUS
    • 没有文件与这个线性区相关联。
  • MAP_NORESERVE
    • 函数不必预先检查空闲页框的数目。
  • MAP_POPULATE
    • 函数应该为线性区建立的映射提前分配需要的页框。该标志仅对映射文件的线性区和IPC共享的线性区有意义。
  • MAX_NONBLOCK
    • 只有在MAP_POPULATE标志置位时才有意义：提前分配页框时，函数肯定不阻塞。

  我们看到do_mmap()函数对offset的值进行一些初步检查，然后执行do_mmap_pgoff()函数。这里假设新的线性地址区间映射的不是磁盘文件，仅对实现匿名线性区的do_mmap_pgoff()函数进行说明（mm/Mmap.c）：

• 首先检查参数的值是否正确，所提的请求是否能被满足。尤其是要检查以下不能满足请求的条件：
  • 线性地址区间的长度为0或者包含的地址大于TASK_SIZE
  • 进程已经映射了过多的线性区，mm内存描述符的map_count字段的值超过了允许的最大值
  • flag指定新线性地址区间的页必须被锁在RAM中，但不允许创建上锁的线性区，或者进程加锁页的总数超过了保存在进程描述符signal->rlim[RLIMIT_MEMLOCK].rlim_cur字段中的阈值
  • 以上任意一个成立则do_mmap_pgoff()终止并返回一个负值
• 执行内存描述符的get_unmapped_area()方法
• 通过把存放在prot和flags参数中的值进行组合来计算新线性区描述符的标志
  • 只有在prot中设置了相应的PROT_READ、PROT_WRITE和PROT_EXEC标志，calc_vm_prot_bits()函数才在vm_flags中设置VM_READ，VM_WRITE和VM_EXEC标志；只有在flags设置了相应的MAP_GROWSDOWN，MAP_DENYWRITE，MAP_EXECUTABLE和MAP_LOCKED标志，calc_vm_flag_bits()也才在VM_flags中设置VM_GROWSDOWN、VM_DENYWRITE、VM_EXECUTABLE和VM_LOCKED标志。在vm_flags中还有几个标志被置为1：VM_MAYREAD、VM_MAYWRITE、VM_MAYEXEC，在mm->def_flags中所有线性区的默认标志，以及如果线性区的页与其他进程共享时的VM_SHARED和VM_MAYSHARE。

1
2
3
4
5
6

vm_flags = calc_vm_prot_bits(prot) | calc_vm_flag_bits(flags) |
  mm->def_flags | VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;
if (flags & MAP_LOCKED) {
 if (!can_do_mlock())
  return -EPERM;
 vm_flags |= VM_LOCKED;

• 调用find_vma_prepare()确定处于新区间之前的线性区对象的位置，以及在红-黑树中新线性区的位置

1
2
3
4
5
6

vma = find_vma_prepare(mm, addr, &prev, &rb_link, &rb_parent);
if (!vma || vma->vm_start >= addr + len) {
    break;
if (do_munmap(mm, addr, len))
    return -ENOMEM;
}

• 检查插是否还存在与新区间重叠的线性区，这种情况发生在函数返回一个非空的地址，这个地址指向一个线性区，而该区的起始位置位于新区间结束地址之前的时候。这时do_mmap_pgoff()调用do_munmap()删除新的区间。
• 检查新的线性区是否引起进程地址空间的大小(mm->total_vm<<PAGE_SHIFT) + len超过存放在进程描述符signal->rlim[RLIMIT_AS].rlim_cur字段中的阈值。
  • 如果是，就返回出错码-ENOMEM。注意，这个检查只在这里进行，而不在前面与其他检查一起进行，
  • 因为一些线性区可能在刚才调用do_munmap()时候被删除。
• 如果在flags参数中没有设置MAP_NORESERVE标志，新的线性区包含私有可写页，并且没有足够的空闲页框，则返回出错码-ENOMEM；这最后一个检查是由security_vm_enough_memory()函数实现的。
• 如果新区间是私有的（没有设置VM_SHARED），且映射的不是磁盘上的一个文件，那么，调用vma_merge()检查前一个线性区是否可以以这样的方式进行扩展来包含新的区间。
  • 当然，前一个线性区必须与在vm_flags局部变量中存放标志的那些线性区具有完全相同的标志。
  • 如果前一个线性区可以扩展，那么，vma_merge()也试图把它与随后的线性区进行合并（这发生在新区间填充两个线性区之间的空洞，且三个线性区全部具有相同的标志的时候）。
  • 万一在扩展前一个线性区时获得成功，则跳到12步。
• 调用slab分配函数kmem_cache_alloc()为新的线性区分配一个vm_area_struct数据结构
• 初始化新的线性区对象（由vma指向）：

1
2
3
4
5
6

vma->vm_mm = mm;
vma->vm_start = addr;
vma->vm_end = addr + len;
vma->vm_flags = vm_flags;
vma->vm_page_prot = protection_map[vm_flags & (VM_READ|VM_WRITE|VM_EXEC|VM_SHARED)];
vma->vm_pgoff = pgoff;

• 如果MAP_SHARED标志被设置（以及新的线性区不映射磁盘上的文件），则该线性区是一个共享匿名区：
  • 调用shmem_zero_setup()对它进行初始化。共享匿名区主要用于进程间通信。
• 调用vma_link()把新线性区插人到线性区链表和红-黑树中
• 增加存放在内存描述符total_vm字段中的进程地址空间的大小
• 如果设置了VM_LOCKED标志，就调用make_pages_present()连续分配线性区的所有页，并把它们锁在RAM中

1
2

mm->locked_vm += len >> PAGE_SHIFT;
make_pages_present(addr, addr + len);

• make_pages_present()函数按如下方式调用get_user_pages()：

  1 2	write = (vma->vm_flags & VM_WRITE) != 0; get_user_pages(current, current->mm, addr, len, write, 0, NULL, NULL);

• get_user_pages()函数在addr和addr+len之间页的所有起始线性地址上循环；

  • 对于其中的每个页，该函数调用follow_page()检查在当前页表中是否有到物理页的映射。
  • 如果没有这样的物理页存在，则get_user_pages()调用handle_mm_fault()。
  • 以后我们会看到，后一个函数分配一个页框并根据内存描述符的vm_flags字段设置它的页表项。
• 最后，函数通过返回新线性区的线性地址而终止。

释放线性地址区间

内核使用do_munmap()函数从当前进程的地址空间中删除一个线性地址区间。参数mm为进程内存描述符的地址，start地址区间的起始地址，len长度。

1

do_munmap(struct mm_struct *mm, unsigned long addr, size_t len)    //

该函数主要两个阶段：

• 第一阶段，扫描进程所拥有的线性区链表，并把包含在进程地址空间的线性地址区间中的所有线性区从链表中解除链接。
• 第二阶段，更新进程的页表，并把第一阶段找到并标识出的线性区删除。函数利用后面要说明的spilt_vma()和unmap_region()函数。

do_munmap()执行下边的步骤：

• 参数值进行一些初步检查：如果线性地址区间所含的地址大于TASK_SIZE，如start不是4096的倍数，或者如果线性地址区间的长度为0，则函数返回一个错误代码-EINVAL。
• 确定要删除的线性地址区间之后第一个线性区结构vma的位置（mpnt->end > start)，如果有这样的线性区：mpnt = find_vma_prev(mm, start, &prev);
• 如果没有这样的线性区，也没有与线性地址区间重叠的线性区，就什么都不做，因为该线性地址区间上没有线性区：
• 如果线性区的起始地址在线性区vma内，就调用split_vma()把线性区vma划分成两个较小的区：一个区在线性地址区间外部，而另一个在区间内部。

1
2
3
4
5
6

if (start > vma->vm_start) {
 int error = split_vma(mm, vma, start, 0);
 if (error)
  return error;
 prev = vma;
}

• 更新局部变量prev，以前它存储的是指向线性区vma前面一个线性区的指针，现在要让它指向vma，即指向线性地址区间外部的那个新线性区。这样，prev仍然指向要删除的第一个线性区前面的那个线性区。
• 如果线性地址区间的结束地址在一个线性区内部，就再次调用split_vma()把最后重叠的那个线性区划分成两个较小的区：一个区在线性地址区间内部，而另一个在区间外部。

1
2
3
4
5
6

last = find_vma(mm, end);
if (last && end > last->vm_start) {
 int error = split_vma(mm, last, end, 1);
 if (error)
  return error;
}

• 如果线性地址区间正好包含在某个线性区内部，就必须用用个较小的新线性区取代该线性区。当发生这种情况时，在第4步和第5步把该线性区分成三个较小的线性区：删除中间的那个线性区，而保留第一个和最后一个线性区。
• 更新mpnt的值，使它指向线性地址区间的第一个线性区。如果prev为NULL，即没有上述线性区，就从mm->mmap获得第一个线性区的地址：mpnt = prev? prev->vm_next: mm->mmap;
• 调用detach_vmas_to_be_unmapped()从进程的线性地址空间中删除位于线性地址区间中的线性区。
  • 要删除的线性区的描述符放在一个排好序的链表中，
  • 局部变量mpnt指向该链表的头（实际上，这个链表只是进程初始线性区链表的一部分）。
• 获得mm->page_table_lock自旋锁
• 调用unmap_region()清除与线性地址区间对应的页表项并释放相应的页框：unmap_region(mm, vma, prev, start, end);
• 释放mm->page_table_lock自旋锁
• 释放建立链表时收集的线性区描述符
  • 对在链表中的所有线性区调用unmap_vma()函数，本质上：
    • 更新mm->total_vm和mm->locked_vm字段
    • 执行内存描述符的mm->unmap_area方法，根据进程线性区的不同类型选择arch_unmap_area()或arch_unmap_area_topdown()中的一个来实现mm->unmap_area方法
    • 调用线性区的close方法
    • 如果线性区是匿名的，则函数把它从mm->anon_vma所指向的匿名线性区链表中删除
    • 调用kmem_cache_free()释放线性区描述符
• 返回成功

split_vma()函数

split_vma()函数把与线性地址区间交叉的线性区划分成两个较小的区，一个在线性地址区间外部，另一个在区间的内部。该函数接收4个参数：内存描述符指针mm，线性区描述符指针vma（标识要被划分的线性区），表示区间与线性区之间交叉点的地址addr，以及表示区间与线性区之间交叉点在区间起始处还是结束处的标志new_below。我们来看看该函数的代码：

• 调用kmem_cache_alloc()获得一个新的线性区描述符vm_area_struct，并把它的地址存放在新的局部变量中new，如果没有可用的空闲空间，就返回-ENOMEM。
• 用vma描述符的字段值初始化新描述符的字段。
• 如果new_below标志等于1，说明线性地址区间的结束地址在vma线性区的内部，因此必须把新线性区放在vma线性区的前面，所以函数把字段new->vm_end和vma->vm_start都赋值为addr。
• 相反，new_below为0，说明线性地址区间的起始地址在vma线性区的内部，因此必须把新线性区放在vma线性区之后，所以函数把new->vm_start和vma->vm_end字段都赋值为addr。
• 如果定义了新线性区的open方法，函数就执行它。
• 根据new_below的值调用vma_adjust函数把新线性区描述符链接到线性区链表mm->mmap和红-黑树mm->mm_rb。此外，vma_adjust函数还要根据线性区vma的最新大小对红-黑树进行调整。

unmap_region()函数

unmap_region()函数遍历线性区链表并释放它们的页框，该函数有五个参数：

• 内存描述符指针mm
• 指向第一个被删除线性区描述符的指针vma
• 指向进程链表中vma前面的线性区的指针prev

• 界定被删除线性地址区间的范围的两个地址start和end

• 调用lru_add_drain()

• 调用tlb_gather_mmu()函数初始化每CPU变量mmu_gathers。mmu_gathers的值依赖于CPU体系结构：通常该变量应该存放成功更新进程页表项所需要的所有信息。在80x86体系结构中，tlb_gather_mmu()函数只是简单地把内存描述符指针mm的值赋给本地CPU的mmu_gathers变量。
• 把mmu_gathers变量的地址保存在局部变量tlb中。
• 调用unmap_vmas()扫描线性地址空间的所有页表项：如果只有一个有效CPU，函数就调用free_swap_and_cache()反复释放相应的页（页面回收中会提到）；否则，函数就把相应页描述符的指针保存在局部变量mmu_gathers中。
• 调用free_pgtables(tlb, prev, start, end)回收在上一步已经清空的进程页表。
• 调用tlb_finish_mmu(tlb, start, end)结束unmap_region()函数的工作，tlb_finish_mmu(tlb, start, end)依次执行下面的操作：
  • 调用flush_tlb_mm()刷新TLB。
  • 在多处理器系统中，调用freepages_and_swap_cache()释放页框，这些页框的指针已经集中存放在mmu_gather数据结构中了。

缺页异常处理程序

Linux的缺页（Page Fault）异常处理程序必须区分一下两种情况：

• 由编程错误引起的异常
• 由引用属于进程地址空间还尚未分配物理页框的页所引起的异常。

线性描述符可以让缺页异常处理程序非常有效的完成它的工作。do_page_fault()函数是80x86上的缺页中断服务程序，它把引起缺页的线性地址和当前进程的线性区相比较，从而能够选择适当的方法处理异常。

详细流程如图所示，图中标识good_area、bad_area和no_context等是出现在do_page_fault()中的标记，它们有助于你理清流程图中的块与代码中特定行之间的关系：

do_page_fault()函数接收以下输入参数：

• pt_regs结构的地址regs，该结构包含当异常发生时的微处理器寄存器的值。
• 3位的error_code，当异常发生时由控制单元压入栈中。这些位有以下含义：
  • 如果第0位被清0，则异常由访问一个不存在的页所引起（页表项中的Present标志被清0）；否则，如果第0位被设置，则异常由无效的访问权限所引起。
  • 如果第1位被清0，则异常由读访问或者执行访问所引起；如果该位被设置，则异常由写访问所引起。
  • 如果第2位被清0，则异常发生在处理器处于内核态时；否则，异常发生在处理器处于用户态时。

do_page_fault()的第一步操作是读取引起缺页的b线性地址b（address = read_cr2();）。当异常发生时，CPU控制单元把这个值存放在cr2控制寄存器中：

1
2
3
4
5
6
7

#define read_cr2() ({ /
 unsigned int __dummy; /
 __asm__ __volatile__( /
  "movl %%cr2,%0/n/t" /
  :"=r" (__dummy)); /
 __dummy; /
})

函数首先检查引起缺页的线性地址是否属于内核空间，即是否是第3GB~4GB之间：

1
2
3
4
5
6
7
8
9

si_code = SEGV_MAPERR;
if (unlikely(address >= TASK_SIZE)) { /* 0xd = 1101 */
    if (!(error_code & 0x0000000d) && vmalloc_fault(address) >= 0)  
        return;
    if (notify_page_fault(DIE_PAGE_FAULT, "page fault", regs, error_code, 14,
        SIGSEGV) == NOTIFY_STOP)
        return;
    goto bad_area_nosemaphore;
}

如果发生了由于内核试图访问不存在的页框引起的异常，就去执行vmalloc_fault(address)函数，该部分代码处理可能由于在内核态访问非连续内存区而引起的缺页，否则就跳转去执行bad_area_nosemaphore标记处的代码。接下来缺页处理程序检查异常发生时内核是否正在执行一些关键例程或运行内核线程。如果缺页发生在下面任何一种情况，则in_atomic()产生等于1的值。

• 内核正在执行中断处理程序或可延迟函数。
• 内核正在禁用内核抢占的情况下执行临界区代码。

如果缺页的确发生在中断处理程序、可延迟函数、临界区或内核线程中，do_page_fault()就不会试图把这个线性地址与current的线性区做比较。再一个，内核线程从来不使用小于TASK_SIZE的地址。同样，中断处理程序、可延迟函数和临界区代码也不应该使用小于TASK_SIZE的地址，因为这可能导致当前进程的阻塞。

现在，让我们假定缺页没有发生在中断处理程序、可延迟函数、临界区或者内核线程中。于是函数必须检查进程所拥有的线性区以决定引起缺页的线性地址是否包含在进程的地址空间中，为此必须获得进程的mmap_sem读/写信号量：

1
2
3
4
5
6

if (!down_read_trylock(&mm->mmap_sem)) {
 if ((error_code & 4) == 0 &&
     !search_exception_tables(regs->eip))
  goto bad_area_nosemaphore;
 down_read(&mm->mmap_sem);
}

如果内核bug和硬件故障有可能被排除，那么当缺页发生时，当前进程就不会有为写而获得信号量mmap_sem。尽管如此，do_page_fault()还是想确定的确没有获得这个信号量，因为如果不是这样就会发生死锁。所以，函数使用down_read_trylock()而不是down_read()。

如果这个信号量被关闭而且缺页发生在内核态(error_code & 4)，do_page_fault()就要确定异常发生的时候，是否正在使用作为系统调用参数被传递给内核的线性地址。此时，因为每个系统调用服务例程都小心地避免在访问用户态地址空间以前为写而获得mmap_sem信号量，所以do_page_fault()确信mmap_sem信号量由另外一个进程占有了（!search_exception_tables(regs->eip)），从而do_page_fault()一直等待直到该信号量被释放（down_read(&mm->mmap_sem)）。否则，如果缺页是由于内核bug或严重的硬件故障引起的，函数就跳转到bad_area_nosemaphore标记处。

我们假设已经为读而获得了mmap_sem信号量。现在，do_page_fault()开始搜索错误线性地址所在的线性区：

1
2
3
4
5
6
7

vma = find_vma(mm, address);
if (!vma)
    goto bad_area;
if (vma->vm_start <= address)
    goto good_area;
if (!(vma->vm_flags & VM_GROWSDOWN))
    goto bad_area;

如果vma为NULL，说明address之后没有线性区，因此这个错误的地址肯定是无效的。另一方面，如果在address之后结束处的第一个线性区包含address，则函数跳到标记为good_area的代码处。

如果两个“if”条件都不满足，则函数就确定address没有包含在任何线性区中，但内部变量vma指向当前进程的mm_struct的mmap_cache指向的那个vm_area_struct。函数就执行进一步的检查，由于这个错误地址可能是由push或pusha指令在进程的用户态堆栈上的操作所引起的。

我们稍微离题一点，解释一下栈是如何映射到线性区上的。每个向低地址扩展的栈所在的区，它的VM_GROWSDOWN标志被设置，这样，当vm_start字段的值可能被减小的时候，而vm_end字段的值保持不变。这种线性区的边界包括、但不严格限定用户态堆栈当前的大小。这种细微的差别主要基于以下原因：

• 线性区的大小是4KB的倍数（必须包含完整的页），而栈的大小却是任意的。
• 分配给一个线性区的页框在这个线性区被删除前永远不被释放。尤其是，一个栈所在线性区的vm_start字段的值只能减小，永远也不能增加。甚至进程执行一系列的pop指令时，这个线性区的大小仍然保持不变。

现在这一点就很清楚了，当进程填满分配给它的堆栈的最后一个页框后，进程如何引起一个“缺页”异常——push引用了这个线性区以外的一个地址（即引用一个不存在的页框）。注意，这种异常不是由程序错误引起的，因此它必须由缺页处理程序单独处理。

do_page_fault()它检查上面所描述的情况：

1
2
3
4
5
6
7

if (!(vma->vm_flags & VM_GROWSDOWN))
    goto bad_area;
if (error_code & 4 && address + 32 < regs->esp)
   goto bad_area;
if (expand_stack(vma, address))
  goto bad_area;
}

如果线性区的VM_GROWSDOWN标志被设置，并且异常发生在用户态，函数就要检查address是否小于regs->esp栈指针的值（它应该只小于一点点）。因为几个与栈相关的汇编语言指令只有在访问内存之后才执行减esp寄存器的操作，所以允许进程有32字节的后备区间。如果这个地址足够高，则代码调用espand_stack()函数检查是否允许进程既扩展它的栈也扩展它的地址空间。如果一切都可以，expand_stack就把vma的vm_start字段设为address，并返回0；否则，expand_stack返回-ENOMEM。

注意：只要线性区的VM_GROWSDOWN标志被设置，但异常不是发生在用户态，上述代码就跳过容错检查。这些条件意味着内核正在访问用户态的栈，也意味着这段代码总是应当运行expand_stack()。

处理地址空间以外的错误地址

如果address不属于进程的地址空间，那么do_page_fault()函数执行bad_area标记处的语句，如果错误在用户态，则发送一个SIGSEGV信号给current进程并结束函数；

1
2
3
4
5
6
7
8
9
10
11
12
13
14

bad_area:
    up_read(&mm->mmap_sem);

bad_area_nosemaphore:
if (error_code & 4) {
    tsk->thread.cr2 = address;
    tsk->thread.error_code = error_code | (address >= TASK_SIZE);
    tsk->thread.trap_no = 14;
    info.si_signo = SIGSEGV;
    info.si_errno = 0;
    info.si_addr = (void*)address;
    force_sig_info_fault(SIGSEGV, si_code, address, tsk);
    return;
}

force_sig_info_fault()函数确信进程不忽略或阻塞SIGSEGV信号，并通过info局部变量传递附加信息的同时把该信号发送给用户态进程。info.si_code变量已被置为SEGV_MAPERR（如果异常是由于一个不存在的页框引起），或置为SEGV_ACCERR（如果异常是由于对现有页框的无效访问引起）。

如果异常发生在内核态，仍然有两种可选的情况：

• 异常的引起是由于把某个线性地址作为系统调用的参数传递给内核。
• 异常是因一个真正的内核缺陷所引起的。

函数这样区分这两种可选的情况：

1
2
3
4
5

no_context:
if ((fixup = search_exception_table(regs->eip)) != 0)
    regs->eip = fixup;
    return;
}

在第一种情况中，代码跳到一段“修正代码”处，这段代码的典型操作就是向当前进程发送SIGSEGV信号，或用一个适当的出错码终止系统调用处理程序。

在第二种情况中，函数把CPU寄存器和内核态堆栈的全部转储打印到控制台，并输出到一个系统消息缓冲区，然后调用函数do_exit()杀死当前进程。这就是所谓按所显示的消息命名的内核漏洞（Kernel oops）错误。

处理地址空间内的错误地址

如果addr地址属于进程的地址空间，则do_page_fault()转到good_area标记处执行

1
2
3
4
5
6
7
8
9
10

good_area:
    info.si_code = SEGV_ACCERR;
    write = 0;
    if(error_code & 2) {
        if (!(vma->vm_flags & VM_WRITE))
            goto bad_area;
        write++;
    } else 
        if ((error_code & 1) || !(vma->vm_flags & (VM_READ | VM_EXEC)))
    goto bad_area;

如果异常由写访问引起，函数检查这个线性区是否可写（!(vma->vm_flags & VM_WRITE)）。如果不可写，跳到bad_area代码处；如果可写，把write局部变量置为1。

如果异常由读或执行访问引起，函数检查这一页是否已经存在于RAM中。在存在的情况下，异常发生是由于进程试图访问用户态下的一个有特权的页框（页框的User/Supervisor标志被清除），因此函数跳到bad_area代码处（然而，这种情况从不会发生，因为内核不会把具有特权的页框贼给进程。）。在不存在的情况下（error_code & 3 = 0），函数还将检查这个线性区是否可读或可执行。

如果这个线性区的访问权限与引起异常的访问类型相匹配，则调用handle_mm_fault()函数分配一个新的页框：

1
2
3
4
5
6
7
8
9
10

survive:
ret = handle_mm_fault(tsk->mm, vma, address, write);
if (ret == VM_FAULT_MINOR || ret == VM_FAULT_MAJOR) {
    if(ret == VM_FAULT_MINOR)
        tsk->min_flt ++;
    else
        tsk->maj_flt++;
    up_read(&tsk->mm->mmap_sem);
    return;
}

如果handle_mm_fault()函数成功地给进程分配一个页框，则返回VM_FAULT_MINOR或VM_FAULT_MAJOR。值VM_FAULT_MINOR表示在没有阻塞当前进程的情况下处理了缺页；这种缺页叫做次缺页（minor fault）。值VM_FAULT_MAJOR表示缺页迫使当前进程睡眠（很可能是由于当用磁盘上的数据填充所分配的页框时花费时间）；阻塞当前进程的缺页就叫做主缺页（major fault）。函数也返回VM_FAULT_OOM（没有足够的内存）或VM_FAULT_STGBOS（其他任何错误）。

如果handle_mm_fault()返回值VM_FAULT_SIGBUS，则向进程发送SIGBUS信号：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

if(ret == VM_FAULT_SIGBUS) {

do_sigbus:
    up_read(&tsk->mm->mmap_sem);
    if (!(error_code & 4))
        goto no_context;
    tsk->thread.cr2 = address;
    tsk->thread.error_code = error_code;
    tsk->thread.trap_no = 14;
    info.si_signo = SIGBUS;
    info.si_errno = 0;
    info.si_code = BUS_ADRESS;
    info.si_addr = (void*)address;
    force_sig_info_fault(SIGBUS, &info, tsk);
}

如果handle_mm_fault()不分配新的页框，就返回值VM_FAULT_OOM，此时内核通常杀死当前进程，不过，如果当前进程是init进程（tsk->pid == 1），则只是把它放在运行队列的末尾并调用调度程序；一旦init恢复执行，则又去执行handle_mm_fault()：

1
2
3
4
5
6
7
8
9
10
11
12
13

if(ret == VM_FAULT_OOM) {

out_of_memory:
    up_read(&tsk->mm->mmap_sem);
    if (tsk->pid == 1) {
        if(error_code & 4)
            do_exit(SIGKILL);
        goto no_context;
    }
    yield();
    down_read(&tsk->mm->mmap_sem);
    goto survive;
}

handle_mm_fault()函数作用于4个参数：

• mm：指向异常发生时正在CPU上运行的进程的内存描述符。
• vma：指向引起异常的线性地址所在线性区的描述符。
• address：引起异常的线性地址。
• write_access：如果tsk试图向address写，则置为1；如果tsk试图在address读或执行，则置为0。

这个函数会检查用来映射address的页中间目录和页表是否存在：

1
2
3

if (!pud)
if (!pmd)
if (!pte)

即使address属于进程的地址空间，相应的页表也可能还没有被分配，因此，在做别的事情之前首先执行分配页目录和页表的任务：

1
2
3

pud = pud_alloc(mm, pgd, address);
pmd = pmd_alloc(mm, pud, address);
pte = pte_alloc_map(mm, pmd, address);

pgd局部变量包含引用address的页全局目录项。如果需要的话，调用pud_alloc()和pmd_alloc()函数分别分配一个新的页上级目录和页中间目录（在80x86微处理器中，这种分配永远不会发生，因为页上级目录总是包含在页全局目录中，并且页中间目录或者包含在页上级目录中（PAE未激活），或者与页上级目录一块被分配（PAE被激活））。然后，如果需要的话调用的pte_alloc_map()函数会分配一个新的页表。

如果以上两步都成功，pte局部变量所指向的页表项就是引用address的表项。然后调用handle_pte_fault()函数检查address地址所对应的页表项，并决定如何为进程分配一个新页框：

1. 如果被访问的页不存在，也就是说，这个页还没有被存放在任何一个页框中，那么，内核分配一个新的页框并适当地初始化。这种技术称为请求调页（demand paging）。
2. 如果被访问的页存在但是标记为只读，也就是说，它已经被存放在一个页框中，那么，内核分配一个新的页框，并把旧页框的数据拷贝到新页框来初始化它的内容。这种技术称为写时复制（Copy On Write，COW）。

请求调页

术语请求调页指的是一种动态内存分配技术，它把页框的分配推迟到不能再推迟位置，也就是说，一直推迟到进程要访问的页不在RAM中时位置，由此引起一个缺页异常。

请求调页技术背后的动机是：进程开始运行的时候并不访问其地址空间中的全部地址；事实上，有一部分地址也许永远不被进程使用。对于全局分配来说，请求调页是首选的，因为它增加了系统中空闲页框的平均数，从而更好地利用空闲内存。从另一个观点来看，在RAM总体保持不变的情况下，请求调页从总体上能使系统有更大的吞吐量。

被访问的页可能不在主存中，其原因或者是进程从没访问过该页，或者是内核已经回收了相应的页框。在这两种情况下，缺页处理程序必须为进程分配新的页框。不过，如何初始化这个页框取决于是哪一种页以及页以前是否被进程访问过。特殊情况下：

1. 这个页从未被进程访问到且没有映射磁盘文件，或者页映射了磁盘文件。内核能够识别这些情况，它根据页表相应的表项被填充为0，也就是说，pte_none宏返回1。
2. 页属于非线性磁盘文件的映射。内核能够识别这种情况，因为Present标志被清0而且Dirty标志被置1，也就是说，pte_file宏返回1。
3. 进程已经访问过这个页，但是其内容被临时保存在磁盘上。内核能够识别这种情况，这是因为相应表项没被填充为0，但是Present和Dirty标志被清0。

因此，handle_pte_fault()函数通过检查address对应的页表项能够区分三种情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static inline int handle_pte_fault(struct mm_struct *mm,
        struct vm_area_struct * vma, unsigned long address,
        int write_access, pte_t *pte, pmd_t *pmd)
{
    pte_t entry;

    entry = *pte;
    if (!pte_present(entry)) {
        if (pte_none(entry))
            return do_no_page(mm, vma, address, write_access, pte, pmd);
        if (pte_file(entry))
            return do_file_page(mm, vma, address, write_access, pte, pmd);
        return do_swap_page(mm, vma, address, pte, pmd, entry, write_access);
    }

在第一种情况下，当页从未被访问或页线性地映射磁盘文件时则调用do_no_page()函数。通过检查vma线性区描述符的nopage确定这个页是否被映射到一个磁盘文件：

• vma->vm_ops->nopage不为NULL，线性区映射了一个磁盘文件，nopage字段指向装入页的函数。
• vma->vm_ops为NULL，或者vma->vm_ops->nopage为NULL，线性区没有映射文件，它是一个匿名映射。因此do_no_page()调用do_anonymous_page()获得一个新的页框。

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

static int do_anonymous_page(struct mm_struct *mm, struct vm_area_struct *vma,
  unsigned long address, pte_t *page_table, pmd_t *pmd,
  int write_access)
{
    struct page *page;
    spinlock_t *ptl;
    pte_t entry;

    if (write_access) {
        pte_unmap(page_table);
        spin_unlock(&mm->page_table_lock);
        page = alloc_page(GFP_HIGHUSER | __GFP_ZERO);
        spin_lock(&mm->page_table_lock);
        page_table = pte_offset_map(pmd, addr);
        mm->rss ++;

        entry = maybe_mkwrite(pte_mkdirty(mk_pte(page, vma->vm_page_prot)), vma);
        lru_cache_add_active(page);
        SetPageReference(page);
        set_pte(page_table, entry);
        pte_unmap(page_table);
        spin_unlock(&mm->page_table_lock);
        return VM_FAULT_MINOR;
    }
}

pte_unmap宏的第一次执行释放一种临时内核映射，这种映射了在调用handle_pte_fault()函数之前由pte_offset_map宏所建立页表项的高端内存物理地址。pte_offset_map和pte_unmap这对宏获取和释放同一个临时内核映射。临时内核映射必须在调用alloc_zeroed_user_highpage，本质上也就是alloc_page()之前释放，因为这个函数可能会阻塞当前进程。

函数递增内存描述符的rss字段以记录分配给进程的页框总数。相应的页表项设置为页框的物理地址，页表框被标记为既脏又可写的。lru_cache_add_active()函数把新页框插入与交换相关的数据结构中。

相反，当处理读访问时，即write_access为0，页的内容是无关紧要的，因为进程第一次对它访问。给进程一个填充为0的页要比给它一个由其他进程填充了信息的旧页更为安全。Linux在请求调页方面做得更深入一些。没有必要立即给进程分配一个填充为0的新页框，由于我们也可以给它一个现有的称为零页（zero page）的页，这样可以进一步推迟页框的分配。零页在内核初始化期间被静态分配，并存放在empty_zero_page变量中（长为4096字节的数组，并用0填充）。

写时复制

第一代Unix系统实现了一种傻瓜式的进程创建：当发出fork()系统调用时，内核原样复制父进程的整个地址空间并把复制的那一份分配给子进程。这种行为非常耗时，因为它需要：

• 为子进程的页表分配页框
• 为子进程的页分配页框
• 初始化子进程的页表
• 把父进程的页复制到子进程相应的页中

写时复制（Copy On Write，COW）的思想相当简单：父进程和子进程共享页框而不是复制页框。然后只要页框被共享，它们就不能被修改。无论父进程还是子进程何时试图写一个共享的页框，就产生一个异常，这是内核就把这个页复制到一个新的页框中并标记可写。原来的页框仍然是写保护的：当其他进程试图写入时，内核检查写进程是否是这个页框的唯一属主，如果是，就把这个页框标记为对这个进程可写。

页描述符的_count字段用于跟踪共享相应页框的进程数目。只要进程释放一个页框或者在它上面执行写时复制，它的_count字段就减小；只有当_count变为-1时，这个页框才被释放。

handle_pte_fault()函数确定缺页异常是由访问内存中现有的一个页而引起时：

1
2
3
4
5
6
7
8
9
10
11
12
13

if(pte_present(entry)) {
    if (write_access) {
        if (!pte_write(entry))
            return do_wp_page(mm, vma, address, pte, pmd, ptl, entry);
            entry = pte_mkdirty(entry);
    }
    entry = pte_mkyoung(entry);
    set_pte(pte,entry);
    flush_tlb_page(vma, address);
    pte_unmap(pte);
    spin_unlock(&mm->page_table_lock);
    return VM_FAULT_MINOR;
}

handle_pte_fault()函数是与体系结构无关的：它考虑任何违背页访问权限的可能。然而，在80x86体系结构上，如果页是存在的，那么，访问权限是写允许的(write_access=1)而页框是写保护的（参见前面“处理地址空间内的错误地址”一博）。因此，总是要调用do_wp_page()函数。

do_wp_page()函数首先获取与缺页异常相关的页框描述符：

1

old_page = vm_normal_page(vma, address, orig_pte);

接下来，函数确定页的复制是否真正必要。如果仅有一个进程拥有这个页，那么，写时复制就不必应用，且该进程应当自由地写该页。具体来说，函数读取页描述符的_count字段：如果它等于0（只有一个所有者），写时复制就不必进行。

实际上，检查要稍微复杂些，因为当页插入到交换高速缓存（并且当设置了页描述符的PG_private标志时，_count字段也增加。不过，当写时复制不进行时，就把该页框标记为可写的，以免试图写时引起进一步的缺页异常：

1
2
3
4
5

set_pte(page_table, maybe_mkwrite(pte_mkyoung(pte_mkdirty(pte)),vma));
flush_tlb_page(vma, address);
pte_unmap(page_table);
spin_unlock(&mm->page_table_lock);
return VM_FAULT_MINOR;

如果两个或多个进程通过写时复制共享页框，那么函数就把旧页框（old page）的内容复制到新分配的页框(new page)中。为了避免竞争条件，在开始复制操作前调用get_page()把old_page的使用计数加1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

old_page = pte_page(pte);
pte_unmap(page_table);
get_page(old_page);
spin_unlock(&mm->page_table_lock);
if (old_page == virt_to_page(empty_zero_page))
    new_page = alloc_page(GFP_HIGHUSER | _ _GFP_ZERO);
} else {
    new_page = alloc_page(GFP_HIGHUSER);
    vfrom = kmap_atomic(old_page, KM_USER0)
    vto = kmap_atomic(new_page, KM_USER1);
    copy_page(vto, vfrom);
    kunmap_atomic(vfrom, KM_USER0);
    kunmap_atomic(vto, KM_USER0);
}

如果旧页框是零页，就在分配新的页框时（__GFP_ZERO标志）把它填充为0。否则，使用copy_page()宏复制页框的内容。不要求一定要对零页做特殊的处理，但是特殊处理确实能够提高系统的性能，因为它减少地址引用而保护了微处理器的硬件高速缓存。

因为页框的分配可能阻塞进程，因此，函数检查自从函数开始执行以来是否已经修改了页表项（pte和*page_table具有不同的值）。如果是，新的页框被释放，old_page的使用计数器被减少（取消以前的增加），函数结束。

如果所有的事情看起来进展顺利，那么，新页框的物理地址最终被写进页表项，且使用相应的TLB寄存器无效：

1
2
3
4
5
6
7
8

spin_lock(&mm->page_table_lock);
entry = maybe_mkwrite(pte_mkdirty(mk_pte(new_page,
                                         vma->vm_page_prot)),vma);
set_pte(page_table, entry);
flush_tlb_page(vma, address);
lru_cache_add_active(new_page);
pte_unmap(page_table);
spin_unlock(&mm->page_table_lock);

lru_cache_add_active()函数把新页框插入到与交换相关的数据结构中。

最后，do_wp_page()把old_page的使用计数器减少两次。第一次的减少是取消复制页框内容之前进行的安全性增加；第二次的减少是反映当前进程不再拥有该页框这一事实。

处理非连续内存区访问

内核在更新非连续内存区对应的页表项时是非常懒惰的。事实上，vmalloc()和vfree()函数只把自己现在在更新主内核页表。

然而一旦内核初始化结束，任何进程或内核线程便都不直接使用主内核页表。因此，我们来考虑内核态进程对非连续内存区的第一次访问。当把线性地址转换为物理地址时，CPU的内存管理单元遇到空的页表项并产生一个缺页。但是缺页异常处理程序认识这种特殊的情况，因为异常发生在内核态且产生缺页的线性地址大于TASK_SIZE。

因此do_page_fault()检查相应的主内核页表项。把存放在cr3寄存器中的当前进程页全局目录的物理地址赋给局部变量pgd_paddr（内核不使用current->mm_pgd导出当前进程的页全局目录地址，因为这种缺页可能在任何时刻都发生，甚至在进程切换期间发生。），把与pgd_paddr相应的线性地址赋给局部变量pgd，并且把主内核页全局目录的线性地址赋给pgd_k局部变量。

如果产生缺页的线性地址所对应的主内核页全局目录项为空，即if(!pud_present(*pud_k))，则函数跳到标号为no_context处。否则，函数检查与错误线性地址相对应的主内核页上级目录项和主内核页中间目录项。如果它们中有一个为空，再次跳到标号为no_context处。

创建和删除进程的地址空间

重点关注fork()系统调用为子进程创建一个完整的新地址空间。相反，当进程结束时，内核撤消它的地址空间。

创建进程的地址空间

当创建一个新的进程时内核调用copy_mm()函数。这个函数通过建立新进程的所有页表和内存描述符来创建进程的地址空间。

1

static int copy_mm(unsigned long clone_flags, struct task_struct * tsk)

通常，每个进程都有自己的地址空间，但是轻量级进程可以通过调用clone()函数来创建。这些轻量级进程共享同一地址空间，也就是说，允许它们对同一组页进行寻址。

按照前面讲述的写时复制方法，传统的进程继承父进程的地址空间，只要页是只读的，就依然共享它们。当其中的一个进程试图对某个页进行写时，此时，这个页才被复制一份。一段时间之后，所创建的子进程通常会因为缺页异常而获得与父进程不一样的完全属于自己的地址空间。

另一方面，轻量级的进程使用父进程的地址空间。Linux实现轻量级进程很简单，即不复制父进程地址空间。创建轻量级的进程（clone）比创建普通进程相应要快得多，而且只要父进程和子进程谨慎地协调它们的访问，就可以认为页的共享是有益的。

如果通过clone()系统调用已经创建了新进程，并且flag参数的CLONE_VM标志被设置，则copy_mm()函数把父进程（current）地址空间给子进程（tsk）：

1
2
3
4
5
6
7

if (clone_flags & CLONE_VM) {
    atomic_inc(&current->mm->mm_users);
    spin_unlock_wait(&current->mm->page_table_lock);
    tsk->mm = current->mm;
    tsk->active_mm = current->mm;
    return 0;
}

如果没有设置CLONE_VM标志，copy_mm()函数就必须创建一个新的地址空间（在进程请求一个地址之前，即使在地址空间内没有分配内存）。函数分配一个新的内存描述符，把它的地址存放在新进程描述符tsk的mm字段中，并把current->mm的内容复制到tsk->mm中。然后改变新进程描述符的一些字段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

static struct mm_struct *dup_mm(struct task_struct *tsk)
{
    tsk->mm = kmem_cache_alloc(mm_cachep, SLAB_KERNEL);
    memcpy(tsk->mm, current->mm, sizeof(*tsk->mm));
    atomic_set(&mm->mm_users, 1);
    atomic_set(&mm->mm_count, 1);
    init_rwsem(&mm->mmap_sem);
    tsk->mm->core_waiters = 0;
    tsk->mm->page_table_lock = SPIN_LOCK_UNLOCKED;
    tsk->mm->ioctx_list_lock = RW_LOCK_UNLOCKED;
    tsk->mm->ioctx_list = NULL;
    tsk->default_kioctx = INIT_KIOCTX(tsk->mm->default_kioctx, *tsk->mm);
    tsk->mm->free_area_cache = (TASK_SIZE/3+0xfff)&0xfffff000;
    tsk->mm->pgd = pgd_alloc(tsk->mm);
    tsk->mm->def_flags = 0;

mm_alloc_pgd()调用pgd_alloc()宏为新进程分配一个全新的页全局目录，随后调用依赖于体系结构的init_new_context()函数：对于80x86处理器，该函数检查当前进程是否拥有定制的局部描述符表，如果是，init_new_context()复制一份current的局部描述符表并把它插入tsk的地址空间。最后调用dup_mmap()函数既复制父进程的线性区，也复制父进程的页表，把新内存描述符tsk->mm插入到内存描述符的全局链表中。然后从current->mm->mmap所指向的线性区开始扫描父进程的线性区链表。它复制遇到的每个vm_area_struct线性区描述符，并把复制品插入到子进程的线性区链表和红-黑树中。

在插入一个新的线性区描述符之后，如果需要的话，dup_mmap()立即调用copy_page_range()创建必要的页表来映射这个线性区所包含的一组页，并且初始化新页表的表项。尤其是，与私有的、可写的页（VM_SHARED标志关闭，VM_MAYWRITE标志打开）所对应的任一页框都标记为对父子进程是只读的，以便这种页框能用写时复制机制进行处理：

删除进程的地址空间

当进程结束时，内核调用exit_mm()函数释放进程的地址空间。

1
2
3
4

mm_release(tsk, tsk->mm);
if (!(mm = tsk->mm)) /* kernel thread ? */
    return;
down_read(&mm->mmap_sem);

mm_release()函数唤醒在tsk->vfork_done补充信号量上睡眠的任一进程。典型地，只有当现有进程通过vfork()系统调用被创建时，相应的等待队列才会为非空。如果正在被终止的进程不是内核线程，exit_mm()函数就必须释放内存描述符和所有相关的数据结构。首先，它检查mm->core_waiters标志是否被置位：如果是，进程就把内存的所有内容卸载到一个转储文件中。为了避免转储文件的混乱，函数利用mm->core_done和mm->core_startup_done补充原语使共享同一个内存描述符mm的轻量级进程的执行串行化。

接下来，函数递增内存描述符的主使用计数器，重新设置进程描述符的mm字段，并使处理器处于懒惰TLB模式：

1
2
3
4
5
6
7

atomic_inc(&mm->mm_count);
spin_lock(tsk->alloc_lock);
tsk->mm = NULL;
up_read(&mm->map_sem);
enter_lazy_tlb(mm, current);
spin_unlock(tsk->alloc_lock);
mmput(mm);

最后，调用mmput()函数释放局部描述符表、线性区描述符和页表。不过，因为exit_mm()已经递增了主使用计数器，所以并不释放内存描述符本身。当要把正在被终止的进程从本地CPU撤消时，将由finish_task_switch()函数释放内存描述符。

堆的管理

每个Unix进程都拥有一个特殊的线性区，这个线性区就是所谓的堆（heap），堆用于满足进程的动态内存请求。内存描述符的start_brk与brk字段分别限定了这个区的开始地址和结束地址。进程可以使用下面的API来请求和释放动态内存：

• malloc(size):请求size个字节的动态内存
• calloc(n,size):请求含n个大小为size的元素的一个数组。
• realloc(ptr,size):该表由前面的malloc()或calloc()分配内存区字段的大小。
• free(addr):释放由malloc()和calloc()分配的其实地址为addr的线性区。
• brk(addr):直接修改堆的大小。addr参数指定current->mm->brk的新值，返回值是线性区新的结束地址。
• sbrk(incr):类似于brk()，其中的incr参数指定是增加还是减小以字节为单位的堆大小

brk()函数和以上列出的函数有所不同，因为它是唯一以系统调用的方式实现的函数，而其他所有的函数都是使用brk()和mmap()系统调用实现的C语言库函数。

当用户态的进程调用brk()系统调用时，内核执行sys_brk(addr)函数。该函数首先验证addr参数是否位干进程代码所在的线性区。如果是，则立即返回，因为堆不能与进程代码所在的线性区重叠：

1
2
3
4
5
6
7

mm = current->mm;
down_write(&mm->mmap_sem);
if (addr < mm->end_code) {
out:
    up_write(&mm->mmap_sem);
    return mm->brk;
}

由于brk()系统调用作用于某一个非代码的线性区，它分配和释放完整的页。因此，该函数把addr的值调整为PAGE_SIZE的倍数，然后把调整的结果与内存描述符的brk字段的值进行比较：

1
2
3
4
5
6

newbrk = (addr + 0xfff) & 0xfffff000;
oldbrk = (mm->brk + 0xfff) & 0xfffff000;
if (oldbrk == newbrk) {
    mm->brk = addr;
    goto out;
}

如果进程请求缩小堆，则sys_brk()调用do_munmap()函数完成这项任务，然后返回：

1
2
3
4
5

if (addr <= mm->brk) {
    if (!do_munmap(mm, newbrk, oldbrk-newbrk))
        mm->brk = addr;
    goto out;
}

如果进程请求扩大堆，则sys_brk()首先检查是否允许进程这样做。如果进程企图分配在其跟制范围之外的内存，函数并不多分配内存，只简单地返回mm->brk的原有值：

1
2
3

rlim = current->signal->rlim[RLIMIT_DATA].rlim_cur;
if (rlim < RLIM_INFINITY && addr - mm->start_data > rlim)
    goto out;

然后，函数检查扩大后的堆是否和进程的其他线性区相重叠，如果是，不做任何事情就返回：

1
2

if (find_vma_intersection(mm, oldbrk, newbrk+PAGE_SIZE))
    goto out;

如果一切都顺利，则调用do_brk()函数。如果它返回oldbrk，则分配成功且sys_brt()函数返回addr的值；否则，返回旧的mm->brk值：

1
2
3

if (do_brk(oldbrk, newbrk-oldbrk) == oldbrk)
    mm->brk = addr;
goto out;

do_brk()函数实际上是仅处理匿名线性区的do_mmap()的简化版。可以认为它的调用等价于：

1
2

do_mmap(NULL, oldbrk, newbrk-oldbrk, PROT_READ|PROT_WRITE|PROT_EXEC,
        MAP_FIXED|MAP_PRIVATE, 0)

当然，do_brk()比do_mmap()稍快，因为前者假定线性区不映射磁盘上的文件，从而避免了检查线性区对象的几个字段。

用C/C++开发的程序执行效率很高，但却经常受到内存泄漏的困扰。本文提供一种通过wrap malloc查找memory leak的思路，依靠这个方法，笔者紧急解决了内存泄漏问题，避免项目流血上大促，该方法在日后工作中大放光彩，发现了项目中大量沉疴已久的内存泄漏问题。

什么是内存泄漏？

动态申请的内存丢失引用，造成没有办法回收它（我知道杠jing要说进程退出前系统会统一回收），这便是内存泄漏。

Java等编程语言会自动管理内存回收，而C/C++需要显式的释放，有很多手段可以避免内存泄漏，比如RAII，比如智能指针（大多基于引用计数计数），比如内存池。

理论上，只要我们足够小心，在每次申请的时候，都牢记释放，那这个世界就清净了，但现实往往没有那么美好，比如抛异常了，释放内存的语句执行不到，又或者某菜鸟程序员不小心埋了一个雷，所以，我们必须直面真实的世界，那就是我们会遭遇内存泄漏。

怎么查内存泄漏？

我们可以review代码，但从海量代码里找到隐藏的问题，这如同大海捞针，往往两手空空。

所以，我们需要借助工具，比如valgrind，但这些找内存泄漏的工具，往往对你使用动态内存的方式有某种期待，或者说约束，比如常驻内存的对象会被误报出来，然后真正有用的信息会掩盖在误报的汪洋大海里。很多时候，甚至valgrind根本解决不了日常项目中的问题。

所以很多著名的开源项目，为了能用valgrind跑，都费大力气，大幅修改源代码，从而使得项目符合valgrind的要求，满足这些要求，用valgrind跑完没有任何报警的项目叫valgrind干净。

既然这些玩意儿都中看不中用，所以，求人不如求己，还是得自力更生。

什么是动态内存分配器？

动态内存分配器是介于kernel跟应用程序之间的一个函数库，glibc提供的动态内存分配器叫ptmalloc，它也是应用最广泛的动态内存分配器实现。

从kernel角度看，动态内存分配器属于应用程序层；而从应用程序的角度看，动态内存分配器属于系统层。

应用程序可以通过mmap系统直接向kernel申请动态内存，也可以通过动态内存分配器的malloc接口分配内存，而动态内存分配器会通过sbrk、mmap向kernel分配内存，所以应用程序通过free释放的内存，并不一定会真正返还给系统，它也有可能被动态内存分配器缓存起来。

google有自己的动态内存分配器tcmalloc，另外jemalloc也是著名的动态内存分配器，他们有不同的性能表现，也有不同的缓存和分配策略。你可以用它们替换linux系统glibc自带的ptmalloc。

new/delete跟malloc/free的关系

new是c++的用法，比如Foo *f = new Foo，其实它分为3步。

1. 通过operator new()分配sizeof(Foo)的内存，最终通过malloc分配。
2. 在新分配的内存上构建Foo对象。
3. 返回新构建的对象地址。

new=分配内存+构造+返回，而delete则是等于析构+free。所以搞定malloc、free就是从根本上搞定动态内存分配。

chunk

每次通过malloc返回的一块内存叫一个chunk，动态内存分配器是这样定义的，后面我们都这样称呼。

wrap malloc

gcc支持wrap，即通过传递-Wl,--wrap,malloc的方式，可以改变调用malloc的行为，把对malloc的调用链接到自定义的__wrap_malloc(size_t)函数，而我们可以在__wrap_malloc(size_t)函数的实现中通过__real_malloc(size_t)真正分配内存，而后我们可以做搞点小动作。

同样，我们可以wrap free。malloc跟free是配对的，当然也有其他相关API，比如calloc、realloc、valloc，但这根本上还是malloc+free，比如realloc就是malloc + free。

怎么去定位内存泄漏呢？

我们会malloc各种不同size的chunk，也就是每种不同size的chunk会有不同数量，如果我们能够跟踪每种size的chunk数量，那就可以知道哪种size的chunk在泄漏。很简单，如果该size的chunk数量一直在增长，那它很可能泄漏。

光知道某种size的chunk泄漏了还不够，我们得知道是哪个调用路径上导致该size的chunk被分配，从而去检查是不是正确释放了。

怎么跟踪到每种size的chunk数量？

我们可以维护一个全局 unsigned int malloc_map[1024 * 1024]数组，该数组的下标就是chunk的size，malloc_map[size]的值就对应到该size的chunk分配量。

这等于维护了一个chunk size到chunk count的映射表，它足够快，而且它可以覆盖到0 ~ 1M大小的chunk的范围，它已经足够大了，试想一次分配一兆的块已经很恐怖了，可以覆盖到大部分场景。

那大于1M的块怎么办呢？我们可以通过log记录下来。

• 在__wrap_malloc里，++malloc_map[size]
• 在__wrap_free里，--malloc_map[size]

很简单，我们通过malloc_map记录了各size的chunk的分配量。

如何知道释放的chunk的size？

不对，free(void *p)只有一个参数，我如何知道释放的chunk的size呢？怎么办？

我们通过在__wrap_malloc(size_t)的时候，分配8+size的chunk，也就是多分配8字节，开始的8字节存储该chunk的size，然后返回的是(char*)chunk + 8，也就是偏移8个字节返回给调用malloc的应用程序。

这样在free的时候，传入参数void* p，我们把p往前移动8个字节，解引用就能得到该chunk的大小，而该大小值就是前一步，在__wrap_malloc的时候设置的size。

好了，我们真正做到记录各size的chunk数量了，它就存在于malloc_map[1M]的数组中，假设64个字节的chunk一直在被分配，数量一直在增长，我们觉得该size的chunk很有可能泄漏，那怎么定位到是哪里调用过来的呢？

如何记录调用链？

我们可以维护一个toplist数组，该数组假设有10个元素，它保存的是chunk数最大的10种size，这个很容易做到，通过对malloc_map取top 10就行。

然后我们在__wrap_malloc(size_t)里，测试该size是不是toplist之一，如果是的话，那我们通过glibc的backtrace把调用堆栈dump到log文件里去。

注意：这里不能再分配内存，所以你只能使用backtrace，而不能使用backtrace_symbols，这样你只能得到调用堆栈的符号地址，而不是符号名。

如何把符号地址转换成符号名，也就是对应到代码行呢？

addr2line

addr2line工具可以做到，你可以追查到调用链，进而定位到内存泄漏的问题。

至此，你已经get到了整个核心思想。

当然，实际项目中，我们做的更多，我们不仅仅记录了toplist size，还记录了各size chunk的增量toplist，会记录大块的malloc/free，会wrap更多的API。

总结一下：通过wrap malloc/free + backtrace + addr2line，你就可以定位到内存泄漏了，恭喜大家。

使用valgrind

valgrind是什么？

Valgrind是一套Linux下，开放源代码（GPL V2）的仿真调试工具的集合。Valgrind由内核（core）以及基于内核的其他调试工具组成。内核类似于一个框架（framework），它模拟了一个CPU环境，并提供服务给其他工具；而其他工具则类似于插件 (plug-in)，利用内核提供的服务完成各种特定的内存调试任务。Valgrind的体系结构如下图所示：

Valgrind包括如下一些工具：

Memcheck

最常用的工具，用来检测程序中出现的内存问题，所有对内存的读写都会被检测到，一切对malloc()/free()/new/delete的调用都会被捕获。所以，它能检测以下问题：

• 对未初始化内存的使用；
• 读/写释放后的内存块；
• 读/写超出malloc分配的内存块；
• 读/写不适当的栈中内存块；
• 内存泄漏，指向一块内存的指针永远丢失；
• 不正确的malloc/free或new/delete匹配；
• memcpy()相关函数中的dst和src指针重叠。

Callgrind

和gprof类似的分析工具，但它对程序的运行观察更是入微，能给我们提供更多的信息。和gprof不同，它不需要在编译源代码时附加特殊选项，但加上调试选项是推荐的。Callgrind收集程序运行时的一些数据，建立函数调用关系图，还可以有选择地进行cache模拟。在运行结束时，它会把分析数据写入一个文件。callgrind_annotate可以把这个文件的内容转化成可读的形式。

Cachegrind

Cache分析器，它模拟CPU中的一级缓存I1，Dl和二级缓存，能够精确地指出程序中cache的丢失和命中。如果需要，它还能够为我们提供cache丢失次数，内存引用次数，以及每行代码，每个函数，每个模块，整个程序产生的指令数。这对优化程序有很大的帮助。

Helgrind

它主要用来检查多线程程序中出现的竞争问题。Helgrind寻找内存中被多个线程访问，而又没有一贯加锁的区域，这些区域往往是线程之间失去同步的地方，而且会导致难以发掘的错误。Helgrind实现了名为“Eraser”的竞争检测算法，并做了进一步改进，减少了报告错误的次数。不过，Helgrind仍然处于实验阶段。

Massif

堆栈分析器，它能测量程序在堆栈中使用了多少内存，告诉我们堆块，堆管理块和栈的大小。Massif能帮助我们减少内存的使用，在带有虚拟内存的现代系统中，它还能够加速我们程序的运行，减少程序停留在交换区中的几率。

此外，lackey和nulgrind也会提供。Lackey是小型工具，很少用到；Nulgrind只是为开发者展示如何创建一个工具。

原理

一个典型的Linux C程序内存空间由如下几部分组成：

• 代码段（.text）。这里存放的是CPU要执行的指令。代码段是可共享的，相同的代码在内存中只会有一个拷贝，同时这个段是只读的，防止程序由于错误而修改自身的指令。
• 初始化数据段（.data）。这里存放的是程序中需要明确赋初始值的变量，例如位于所有函数之外的全局变量：int val=”100”。需要强调的是，以上两段都是位于程序的可执行文件中，内核在调用exec函数启动该程序时从源程序文件中读入。
• 未初始化数据段（.bss）。位于这一段中的数据，内核在执行该程序前，将其初始化为0或者null。例如出现在任何函数之外的全局变量：int sum;
• 堆（Heap）。这个段用于在程序中进行动态内存申请，例如经常用到的malloc，new系列函数就是从这个段中申请内存。
• 栈（Stack）。函数中的局部变量以及在函数调用过程中产生的临时变量都保存在此段中。

Memcheck 能够检测出内存问题，关键在于其建立了两个全局表。

• Valid-Value 表：
  • 对于进程的整个地址空间中的每一个字节(byte)，都有与之对应的 8 个 bits；对于 CPU 的每个寄存器，也有一个与之对应的 bit 向量。这些 bits 负责记录该字节或者寄存器值是否具有有效的、已初始化的值。
• Valid-Address 表
• 对于进程整个地址空间中的每一个字节(byte)，还有与之对应的 1 个 bit，负责记录该地址是否能够被读写。

检测原理

当要读写内存中某个字节时，首先检查这个字节对应的 A bit。如果该A bit显示该位置是无效位置，memcheck 则报告读写错误。

内核（core）类似于一个虚拟的 CPU 环境，这样当内存中的某个字节被加载到真实的 CPU 中时，该字节对应的 V bit 也被加载到虚拟的 CPU 环境中。一旦寄存器中的值，被用来产生内存地址，或者该值能够影响程序输出，则 memcheck 会检查对应的V bits，如果该值尚未初始化，则会报告使用未初始化内存错误。

Valgrind 使用

用法: valgrind [options] prog-and-args

• [options]：常用选项，适用于所有Valgrind工具
• -tool=<name>：最常用的选项。运行 valgrind中名为toolname的工具。默认memcheck。
• h –help：显示帮助信息。
• -version：显示valgrind内核的版本，每个工具都有各自的版本。
• q –quiet：安静地运行，只打印错误信息。
• v –verbose：更详细的信息, 增加错误数统计。
• -trace-children=no|yes：跟踪子线程? [no]
• -track-fds=no|yes：跟踪打开的文件描述？[no]
• -time-stamp=no|yes：增加时间戳到LOG信息? [no]
• -log-fd=<number>：输出LOG到描述符文件 [2=stderr]
• -log-file=<file>：将输出的信息写入到filename.PID的文件里，PID是运行程序的进行ID
• -log-file-exactly=<file>：输出LOG信息到 file
• -log-file-qualifier=<VAR>：取得环境变量的值来做为输出信息的文件名。 [none]
• -log-socket=ipaddr:port：输出LOG到socket ，ipaddr:port

LOG信息输出

• -xml=yes：将信息以xml格式输出，只有memcheck可用
• -num-callers=<number> show <number>：callers in stack traces [12]
• -error-limit=no|yes：如果太多错误，则停止显示新错误? [yes]
• -error-exitcode=<number>：如果发现错误则返回错误代码 [0=disable]
• -db-attach=no|：当出现错误，valgrind会自动启动调试器gdb。[no]
• -db-command=<command>：启动调试器的命令行选项 [gdb -nw %f %p]

适用于Memcheck工具的相关选项：

• -leak-check=no|summary|full：要求对leak给出详细信息? [summary]
• -leak-resolution=low|med|high：how much bt merging in leak check [low]
• -show-reachable=no|yes：show reachable blocks in leak check? [no]

Valgrind 使用举例（一）

1

mpirun -n 12 valgrind run/cpl/c_coupler/exe/c_coupler : -n 10 valgrind run/atm/gamil/exe/gamil : -n 4 valgrind run/ocn/licom/exe/licom : -n 4 valgrind run/sice/cice/exe/cice : -n 4 valgrind run/lnd/clm/exe/clm

下面是一段有问题的C程序代码test.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# include <stdlib.h>
void f(void)
{
   int* x = malloc(10 * sizeof(int));
   x[10] = 0;  //问题1: 数组下标越界
}                  //问题2: 内存没有释放

int main(void)
{
   f();
   return 0;
 }

valgrind --tool=memcheck --leak-check=full ./test

问题分析：

• 对于位于程序中不同段的变量，其初始值是不同的，全局变量和静态变量初始值为0，而局部变量和动态申请的变量，其初始值为随机值。如果程序使用了为随机值的变量，那么程序的行为就变得不可预期。

数组越界/内存未释放

1
2
3
4
5
6
7
8
9
10
11
12

#include<stdlib.h>
void k(void)
{
    int *x = malloc(8 * sizeof(int));
    x[9] = 0; //数组下标越界
} //内存未释放

int main(void)
{
    k();
    return 0;
}

1）编译程序test.c

1

gcc -Wall test.c -g -o test #Wall提示所有告警，-g 调试信息，-o输出

2）使用Valgrind检查程序BUG

1
2

valgrind --tool=memcheck --leak-check=full ./test
#--leak-check=full 所有泄露检查

3) 运行结果如下：

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