《Linux原理与结构》课件第6章

第六章物理内存管理6.1内存管理系统组成结构 6.2伙伴内存管理6.3逻辑内存管理6.4对象内存管理在操作系统营造的虚拟社会中，除了被时钟管理部分管理的时间之外，另一个重要的基石就是空间。对空间的管理是操作系统的另一项核心工作。

操作系统所管理的空间可大致分为内存空间和外存空间，其中内存空间可被处理器直接访问的，是最基础的空间。内存空间是计算机系统中的重要资源，操作系统中的进程运行在内存空间中，操作系统本身也运行在内存空间中，离开了内存空间，计算机系统将无法运行。另一方面，内存空间又是计算机系统中的紧缺资源，操作系统及其管理的所有进程共享同一块物理内存空间，其容量似乎永远都无法满足进程对它的需求。因而有必要对内存空间实施严格的、精细的管理。

内存管理的工作艰巨而繁琐，可大致分成两大部分：物理内存管理部分管理系统中的物理内存空间，负责物理内存的分配、释放、回收等；虚拟内存管理部分管理进程的虚拟内存空间，负责虚拟内存的创建、撤销、换入、换出及虚拟地址到物理地址的转换等。物理内存管理的主要任务是快速、合理、高效地分配与回收物理内存资源以尽力提高其利用率；虚拟内存管理的主要任务是为进程模拟出尽可能大的内存空间并实现它们间的隔离与保护。在操作系统长期的发展过程中，内存管理部分由简到繁，不断演变，正逐步走向成熟。

为解决复杂的内存管理问题，Linux采用了分而治之的设计方法，将内存管理工作交给几个既相互独立又相互关联的管理器分别负责。这些内存管理器各司其职，互相配合，共同管理系统中的内存空间，如图6.1所示。6.1内存管理系统组成结构图6.1内存管理系统的组成结构

Linux的物理内存管理子系统运行在内核空间，仅为内核提供服务。内核需要的物理内存通常是连续的，而且应该有内核线性地址(内核用线性地址访问物理内存)。如果按申请的规模划分，内核对物理内存的需求大致可分为中规模(几个物理上连续的页)、小规模(若干字节)和大规模(多个逻辑上连续的页)等几类。为了满足内核对物理内存的不同需求，Linux将物理内存管理子系统进一步划分成三个管理器，即伙伴内存管理器、对象内存管理器和逻辑内存管理器。伙伴内存管理器是物理内存的真正管理者，是物理内存管理的基础。伙伴内存管理器以页块(若干个连续的物理页)为单位分配、释放、回收物理内存，虽比较粗放，但极为快速、高效，且不会产生外部碎片。

对象内存管理器建立在伙伴内存管理器之上，是一种细粒度的物理内存管理器。对象内存管理器将来自伙伴内存管理器的内存页块划分成小内存对象，以满足内核对小内存的需求，并负责将回收到的小内存对象组合成内存页块后还给伙伴内存管理器。由于伙伴内存管理器只能提供物理上连续的内存，常常无法满足内核对大内存的需求，因而Linux实现了逻辑内存管理器，专门为内核提供逻辑上连续、物理上可不连续的大内存服务。

在系统初始化期间，Linux还提供了一个初始内存管理器Bootmem，用于向内核提供物理内存服务。但在伙伴内存管理器启动之后，Bootmem已让出管理权，被停止了工作。除内核之外，内存管理的主要服务对象是进程。与内核不同，每个进程都需要一块容量足够大的独立的虚拟内存，用于暂存它的程序、数据、堆栈等。因而内存管理的另一个核心工作是利用有限的物理内存和外存设备为系统中的每个进程都模拟出一块连续的虚拟内存，并实现各虚拟内存之间的隔离与保护。Linux中负责进程内存管理工作的是虚拟内存管理器和用户内存管理器。用户内存管理器运行在用户空间中，负责进程虚拟内存(在堆中)的动态分配、释放与回收(如库函数malloc()、free()等)。用户内存管理器一般在函数库(如Libc)中实现，不属于内核的组成部分，但需要内核中的虚拟内存管理器为其提供帮助。

本章主要分析Linux的物理内存管理部分，虚拟内存管理部分将在第8章中讨论。

伙伴内存管理器管理系统中的物理内存，因采用伙伴算法而得名。所谓物理内存就是计算机系统中实际配置的内存。根据处理器与物理内存的组织关系可将计算机系统分成两大类。在UMA(UniformMemoryAccess)系统中，每个处理器都可以访问到所有的物理内存，且访问速度都相同。在NUMA(Non-UniformMemoryAccess)系统中，处理器虽可访问到所有的物理内存，但访问速度略有差异。6.2伙伴内存管理事实上，一个NUMA系统由多个节点组成，每个节点都有自己的处理器和物理内存，处理器对节点内部内存的访问速度较快，对其它节点的内存访问速度较慢。UMA是NUMA的特例，只有一个节点的NUMA就是UMA。

计算机系统中的物理内存被统一编址，其中的每个字节都有一个物理地址，只有通过物理地址才能访问到物理内存单元。在一个计算机系统中，可以使用的所有物理地址的集合称为物理地址空间。物理地址空间的大小取决于地址线的位数。物理地址空间中的地址除可用于访问物理内存之外，还可用于访问固件中的ROM(如BIOS)及设备中的寄存器(如APIC中的寄存器等)。不能访问任何实体的物理地址区间称为空洞，空洞中的物理地址是无效的。在初始化时，系统已经通过BIOSint15h的e820服务获得了物理地址空间的布局信息，并已利用该信息完成了伙伴内存管理器的初始化。6.2.1伙伴内存管理结构

物理内存的管理方法很多，如静态分区法、动态分区法、伙伴算法等，衡量算法好坏的标准主要是效率和利用率，影响的因素主要是管理粒度。细粒度的管理具有较高的利用率，但算法比较复杂；粗粒度的管理具有较高的效率，但利用率不高。伙伴内存管理器采用伙伴算法管理它的物理内存，管理的最小粒度是1页(4KB)。

为了实现页粒度的内存管理，需要一种数据结构来描述每一个物理页的使用情况。伙伴内存管理器为每个物理页准备了一个32字节的page结构，其格式如图6.2所示。图6.2page结构在Linux的发展过程中，page结构在不断演变，最重要的是其中的三项：

(1)标志flags是一个4字节的位图，用于描述物理页的属性或状态。常用的属性如表6.1所示。flags的前端还记录着页所属的节点和管理区的编号。

(2)引用计数_count用于记录物理页的当前用户数，_count为0的页是空闲的。

(3)通用链表节点lru用于将page结构链入到需要的队列中。

另外，page结构中还包含几个复用域，如index、freelist和free共用同一个域，它们的意义随应用场合的不同而变化。复用域的使用使page结构既可满足不同的应用需求，又不至于变得太大。

表6.1物理页的属性续表毫无疑问，系统中存在很多page结构，必须另外建立一种结构来组织、管理它们。最简单的管理方法是定义一个page结构数组。由于计算机系统中的物理内存页数不是固定的，因而只能在检测到物理内存大小之后动态地建立该数组。page结构数组可能很大，为节约物理内存，应尽量压缩page结构的大小。早期的Linux仅在系统初始化时建立了一个page结构数组，称为mem_map[]。由于需要支持NUMA系统，新版本的Linux将物理内存划分成多个节点，并为每个节点建立了一个page结构数组。Linux的节点由一个名字古怪的结构描述，其主要内容如下：

typedefstructpglist_data{

structzone node_zones[MAX_NR_ZONES]; //所有管理区

structzonelist node_zonelists[MAX_ZONELISTS]; //尝试序列

int nr_zones; //节点中的管理区数

structpage *node_mem_map; //page结构数组

unsignedlong node_start_pfn; //开始页号

unsignedlong node_present_pages; //总页数，不含空洞

unsignedlong node_spanned_pages; //总页数，含空洞

wait_queue_head_t kswapd_wait; //回收进程等待队列

structtask_struct *kswapd; //物理内存回收进程

int kswapd_max_order; //上次回收的尺寸

}pg_data_t;

一个pglist_data结构描述一个节点内部的物理内存，对应物理地址空间中的一块连续的地址区间，其开始页号是node_start_pfn，大小是node_spanned_pages页。由于空洞的存在，节点中的实际物理页数node_present_pages可能小于node_spanned_pages。节点内部的page结构数组是node_mem_map，其中的每个page结构描述节点内的一个物理页，包括空洞页。系统中所有的节点结构被组织在数组node_data中。

structpglist_data*node_data[MAX_NUMNODES]_read_mostly;

在基于X86的个人计算机或服务器上，尽管可能配置有多个处理器，但其内存访问模型通常是UMA，因而系统中仅有一个节点，称为contig_page_data。

即使属于同一个节点，物理页的特性也可能不同，如有些物理页有永久性的内核线性地址而另一些物理页没有，有些物理页可用作ISADMA而另一些物理页不能等。不同特性的物理页有着不同的用处，应采用不同的管理方法，或者说应区别对待一个节点内部的物理内存。伙伴内存管理器将一个节点内部的物理内存进一步划分成管理区。每个节点都可以定义2到4个管理区，其中ZONE_DMA区管理的是16MB以下的物理内存，可供老式DMA使用；ZONE_DMA32区管理的是可供32位设备做DMA使用的物理内存(4GB以下)，仅用于64位系统；ZONE_NORMAL区管理的是除ZONE_DMA之外的低端物理内存，可供常规使用；ZONE_HIGHMEM区管理的是没有内核线性地址的高端物理内存，可供特殊使用；ZONE_MOVABLE区是虚拟的，它管理的内存来自其它几个区，都是可动态迁移的物理页，用于内存的热插拔(MemoryHotplug)和紧缩，其大小由命令行参数指定，缺省情况下为空。32位系统中没有ZONE_DMA32区，64位系统中没有ZONE_HIGHMEM区。内存管理区由结构zone描述，其主要内容包括如下几个：

(1)开始页号zone_start_pfn表示管理区的开始位置。

(2)总页数spanned_pages表示管理区的大小，含空洞。

(3)可分配页数present_pages表示管理区中的可用物理内存总页数，不含空洞。

(4)基准线watermark[]描述管理区中空闲内存的三个基准指标。

(5)空闲页块队列free_area[]用于组织不同大小的空闲页块。

(6)

LRU队列lru[]用于描述区内各类物理页的最近使用情况。

(7)热页队列pageset用于暂存刚被释放的单个物理页。

(8)迁移类型位图pageblock_flags用于描述各页组的迁移类型。

(9)预留空间总量lowmem_reserve[]用于记录应为其它管理区预留的内存页数。

一个管理区管理一块连续的物理地址空间，其中可能包含空洞。图6.3是物理内存的一种划分方式。

图6.3物理内存空间的划分图6.3中的物理内存空间由2个节点构成，其中节点1被划分成3个管理区，节点2被划分成2个管理区。两个节点间有一块空洞，节点1的第3个管理区中也有一块空洞。由于page结构数组所占空间无法再做它用，因而也被算做空洞。

伙伴内存管理器以管理区为单位管理物理内存，包括单个物理页及多个连续物理页的分配、释放、回收等。虽然利用page结构数组能够实现单个物理页的管理，但却难以进行多个连续物理页的分配。为解决连续物理页的管理问题，Linux引入了页块的概念。一个页块(pageblock)就是一组连续的物理页。为规范起见，Linux规定页块的大小必须是2i(i=0,1,…,10)页，页块中起始页的编号必须是页块大小的倍数。页块是一个动态管理单元，相邻的小页块可以组合成大页块，大页块也可拆分成小页块。页块以起始页为代表，起始页的编号就是整个页块的编号，起始页的page结构中记录着整个页块的管理信息。

伙伴内存管理器以页块为单位管理各区中的物理内存，因而需要为每一种大小的空闲页块准备一个队列。Linux为每个管理区都定义了一个free_area[]数组，用于组织区内的空闲页块。大小为2i页的空闲页块被组织在free_area的第i队列中。第i队列中的1个大小为2i页的页块可以被划分成2个大小为2i-1页的小页块(伙伴)并挂在第i-1队列中；第i-1队列中的2个小伙伴可以被合并成大小为2i页的页块并挂在第i队列中。

在早期的版本中，伙伴内存管理器为每一种大小的空闲页块准备了一个队列。然而，新版本的伙伴内存管理器需要面对内存迁移问题，为每一种大小的空闲页块准备一个队列已无法满足需要。所谓内存迁移就是将页块从一个物理位置移动到另一个物理位置，也就是将一个页块的内容拷贝到另一个页块中，并保持移动前后的虚拟或线性地址不变。内存迁移的需求主要来自两个方面：为了加快NUMA内存的访问速度，需要将处理器经常访问的内存迁移到离它最近的节点中；为了解决内存碎化问题，需要进行物理内存紧缩，将分散的小空闲页块合并成大页块。

为了实现内存迁移，需要进一步区分页块的迁移属性。事实上，可将物理内存页块大致分成五种类型，不可迁移型(MIGRATE_UNMOVABLE)页块只能驻留在物理内存的固定位置(如内核页)，不能移动；可回收型(MIGRATE_RECLAIMABLE)页块中的内容可先被释放而后再在新的位置上重新生成(如来自映像文件的页)；可迁移型(MIGRATE_MOVABLE)页块中的内容可被拷贝到新的位置而不改变其虚拟或线性地址(如用户进程中的虚拟页)；预留型(MIGRATE_RESERVE)页块是留给内存不足时应急使用的；孤立型(MIGRATE_ISOLATE)页块用于在NUMA的节点间迁移，不可分配。显然，同一类型的页块应集中在一起，不同类型的页块不应相互交叉。不加限制的页块分配会影响页块的合并，如图6.4所示，由于第13页不可迁移，前16个空闲页就不能合并成大页块。

图6.4不可迁移页影响页块合并的情况如果可迁移型页块内部不存在不可迁移的页，那么将其中的非空闲页迁移出去之后即可合并成大的空闲页块。为了聚合同一类型的页块，伙伴内存管理器预先将区中的物理内存划分成了大小为1024页的页组，并为每个页组指定了一个迁移类型。页块的分配按照迁移类型进行。如此以来，在可迁移型页组中就不太可能再出现其它类型的页块。管理区中的位图pageblock_flags(3位一组)用于标识各页组的迁移类型，如图6.5所示。

图6.5页块的迁移类型每个物理页都属于一个页组，都有一个确定的迁移类型，不管它是空闲的还是正在被使用的。当然，页组的迁移类型是可以改变的。

区分页组的迁移类型与定义ZONE_MOVABLE区的作用一样，但更加精细。

划分了迁移类型之后，就应为每一种类型的空闲页块准备一个队列。新版本的伙伴内存管理器为每一种大小的空闲页块准备了5个队列，分别用于组织5种不同迁移类型的空闲页块。结构free_area的定义如下：

structfree_area{

tructlist_head free_list[MIGRATE_TYPES]; //

5个空闲页块队列

unsignedlong nr_free; //空闲页块数

};

图6.6是一个管理区中的空闲页块队列示意图。左边是早期的free_area[]，每种大小的空闲页块1个队列。右边是新的free_area[]，每种大小的空闲页块5个队列。

图6.6free_area数组与空闲页块队列6.2.2伙伴内存初始化

在系统初始化期间，已经进行了大量的内存初始化工作，如检测出了物理内存的布局结构，确定了系统中的节点数及各节点的管理区数，设置了伙伴内存管理器所需的节点结构、管理区结构及所有的page结构，并已将所有的空闲页块都转移到了free_area数组的MOVABLE队列中。下面几件是伙伴内存管理器专有的初始化工作。

1.确定管理区尝试序列

伙伴内存管理器管理着一到多个节点，每个节点中又包含着多个管理区。通常情况下，物理内存的申请者应告诉管理器自己想从哪个节点的哪个管理区中申请内存。伙伴内存管理器应尽量按照申请者的要求为其分配内存。当指定的管理区无法满足请求时，伙伴内存管理器可以返回失败信息，也可以尝试其它的管理区。如果允许尝试其它管理区，则应预先确定一个管理区的尝试顺序，或者说管理区的分配优先级。管理区排序的基本原则是先“便宜”后“贵重”。DMA区容量有限且有特定用途，其它区中的内存无法替代，因而最为贵重。NORMAL区的容量有限，而且内核仅能使用NORMAL和DMA区中的内存(只有这两个区中的内存有内核线性地址)，因而比较贵重。内核不直接访问HIGHMEM区中的内存，该区对内核的影响不大，最为便宜。一般情况下，节点间管理区的尝试顺序应该是先本地后外地，节点内管理区的尝试顺序应该是MOVABLE>HIGHMEM>

NORMAL>DMA32>DMA。当然，由于节点性质的不同，其管理区的尝试顺序也可能会有所变化。结构pglist_data的域node_zonelists中包含一个数组_zonerefs，其中记录着管理区的尝试序列。单节点上的管理区尝试序列如图6.7所示。

如申请者申请DMA内存，那么仅能从DMA区中为其分配，但如果申请者申请高端内存，那么可以从HIGHMEM、NORMAL或DMA区中为其分配。

图6.7管理区尝试序列

2.预留空闲内存

物理内存，尤其是低端物理内存，是十分紧缺的资源，如果不加控制的话，很容易全部耗尽。一旦物理内存被耗尽，很多紧急工作将无法正常开展。当物理内存回收程序也无法正常运行时，物理内存资源将无法被回收，系统有可能不稳定甚至崩溃。因而，在任何情况下，都应该预留一部分空闲的物理内存以备急需。

需要预留的空闲物理内存量记录在变量min_free_kbytes中，其大小取决于低端物理内存的总量，但不得小于128KB，也不应大于64MB。Linux用以下公式计算预留的最小物理内存量：

min_free_kbytes=sqrt(lowmem_kbytes*16)

其中lowmem_kbytes是低端物理内存(包括DMA和NORMAL区)总量。预留的物理内存应按比例分布在各个低端管理区内。为安全起见，高端管理区中也应适当预留一部分内存。为各管理区设定的预留物理内存量会影响到伙伴内存管理器的分配行为。一旦管理区中的空闲内存出现紧张(接近预留量)迹象，就应设法为其回收物理内存。紧张的标志是根据min_free_kbytes算出的基准线，记录在zone的watermark数组中。基准线包括三条，MIN<LOW<HIGH，其中的MIN就是为管理区设定的预留物理内存页数。三条基准线的大致设定如下：

(1)低端管理区的MIN=((min_free_kbytes/4)

×

present_pages)/lowmem_pages。

(2)高端管理区的MIN=present_pages/1024，需在32和128之间。

(3)

LOW=MIN+MIN/4。

(4)

HIGH=MIN+MIN/2。

其中的present_pages是管理区中的可用物理内存页数，lowmen_pages是可用低端物理内存总页数。当管理区中的空闲内存量小于LOW时，表示该区的内存已比较紧张，应立刻开始为其回收物理内存。在确定预留页数之后，应将预留的空闲页块从free_area的MOVABLE队列迁移到RESERVE队列，并将它们的迁移类型改为MIGRATE_RESERVE。由于迁移类型是按页组标记的，因而应以页组为单位(1024页)迁移预留页，迁移的页组数为(MIN+1023)/1024，迁移的内存量可能会超过应预留的物理页数(MIN页)。

即使为每个管理区都预留了物理内存空间，仍然有可能耗尽低端物理内存，原因是管理区的尝试序列。当高端内存紧缺时，伙伴内存管理器会自动用低端内存代替高端内存，其结果会导致低端内存消耗过快。解决这一问题的方法是让低优先级的管理区为高优先级的管理区也预留一些内存空间，或者说将高优先级管理区的预留内存拿出一部分放在低优先级管理区中。在zone结构的lowmem_reserve数组中记录着一个管理区应为其它管理区预留的内存页数。数组lowmem_reserve的值是可调的。

3.确定迁移类型尝试序列

定义了迁移类型之后，物理内存的申请者还需指定所需页块的迁移类型。当特定类型的空闲页无法满足请求时，Linux允许尝试其它的迁移类型，当然需要预先确定迁移类型的尝试序列。数组fallbacks[]中记录着迁移类型的尝试序列，如下：

不可迁移型：UNMOVABLE>RECLAIMABLE>MOVABLE>RESERVE。

可回收型：RECLAIMABLE>UNMOVABLE>MOVABLE>RESERVE。

可迁移型：MOVABLE>RECLAIMABLE>UNMOVABLE>RESERVE。

预留型：RESERVE>RESERVE>RESERVE>RESERVE，即只许分配预留页。

4.建立热页管理队列

伙伴内存管理器采用伙伴算法管理内存页块的分配和释放。分配时可能拆分页块，释放时会尽力合并页块。经典伙伴算法的问题是过于频繁的拆分与合并降低了管理器的性能。在新版本的管理区结构中，为每个处理器都增加了一个热页队列(或者说热页缓存)，用于暂存各处理器新释放的单个物理页，试图通过延迟热页的合并时机来提高伙伴内存管理器的性能。热页(hotpage)是位于处理器Cache中的页，冷页(coldpage)是不在处理器Cache中的页。处理器对热页的访问速度要快于冷页。管理区结构zone中的pageset是热页队列，每个处理器一个。一个热页队列由一个per_cpu_pageset结构描述，其定义如下：

structper_cpu_pageset{

structper_cpu_pages pcp;

s8 stat_threshold;

s8 vm_stat_diff[NR_VM_ZONE_STAT_ITEMS];

}_cacheline_aligned_in_smp;

真正的队列在结构per_cpu_pages中，其定义如下：

structper_cpu_pages{

int count; //队列中的页数

int high; //基准线

int batch; //批的大小

structlist_head lists[3]; //前三种迁移类型各有一个热页队列

};如果新释放的单个空闲页(散页)不是MIGRATE_ISOLATE类型，伙伴内存管理器会先将其加入到热页队列(预留页与可迁移页共用一个队列)而不是free_area数组中，因而暂时不会被合并。当热页数量(count)超过基准线high时，再一次性地将其中batch个空闲页转给free_area(可能被合并)。batch大致是区中内存页数的1/4096，但必须在1到32之间，high的初值是6倍的batch。热页队列的平均长度是4*batch，大约是管理区大小的千分之一，基本与处理器的L2cache的大小相当。伙伴内存管理器总是试图从热页队列中分配单个物理页。当热页队列为空或缺少指定类型的页时，伙伴内存管理器会从free_area中一次性批发过来batch个指定类型的页。6.2.3物理页块分配

伙伴内存管理器采用伙伴算法，以页块(2order页)为单位从free_area中分配物理内存。满足下列条件的两个页块互称为伙伴：

(1)大小相等，都是2order页；

(2)位置相邻，起始页编号分别是B1、B2，且|B1-B2|=2order；

(3)编号的第order位相反，B2=B1^(1<<order)，B1=B2^(1<<order)。如图6.8所示，大小为2页(order=1)、起始页号为4的页块(由4、5两页组成)有两个相邻页块，分别是2、3页块和6、7页块，但只有6、7页块是它的伙伴。同样地，大小为4页(order=2)起始页号为12的页块的伙伴是8、9、10、11页块，而不是16、17、18、19页块，也不是16、17页块。

图6.8伙伴页块一个大的页块可以被平分成两个小伙伴，如4、5、6、7页块可以被平分成两个大小为2页的伙伴，即4、5和6、7页块。两个小伙伴可以被合并成一个大页块，如伙伴4、5与6、7可合并成页块4、5、6、7，当然，4、5、6、7与其伙伴0、1、2、3可进一步合并成大小为8页的页块。

伙伴算法的分配思路是：根据请求的大小(2order页)和迁移类型查free_area[order]中的空闲页块队列，找满足要求的空闲页块。如找到，则将其直接分配给请求者；如找不到，则向上搜索free_area数组。如在free_area[order+i]中找到满足要求的空闲页块，则将其平分成伙伴，将其中的一个挂在free_area[order+i-1]的队列中，将另一个再平分成伙伴。平分过程一直持续，直到得到大小为2order页的两个小伙伴。而后将其中的一个小伙伴挂在free_area[order]的队列中，将另一个分配给请求者。

伙伴内存管理器的请求者至少需要提供三类参数：管理区编号、页块大小和对页块的特殊需求。管理区编号给出了一个请求者建议的管理区，伙伴管理器将优先从该管理区中分配内存。如建议的管理区无法满足请求，伙伴管理器将按管理区尝试序列搜索优先级更低的管理区。对页块的特殊需求很多，如建议的页块迁移类型、是否特别紧急(可动用预留内存)、是否允许暂停(在内存紧缺时先回收内存)、是否允许I/O操作、是否允许文件操作、是否需要对页块进行特殊处理(如清0)等。

伙伴内存管理器按如下流程从管理区中分配物理内存页块：

(1)根据请求参数，确定请求者建议的管理区号zone_idx和迁移类型号，进而确定一个管理区尝试序列和一个迁移类型尝试序列。

(2)按尝试序列顺序搜索各管理区，找一个能满足请求者要求的管理区。符合下列条件的管理区能满足要求：

①系统允许在该管理区中为请求者分配内存。

②在做完此次内存分配之后，该管理区中还有足够的空闲内存。管理区中的空闲物理内存页数减去为其余管理区预留的物理内存页数(即lowmem_reserve[zone_idx])不应少于它的LOW基准线。

③在做完此次内存分配之后，该管理区中的空闲内存块仍然具有合理的分布，意思是管理区中尺寸大于或等于2order页的空闲内存页数不小于LOW/2order页。

(3)从找到的管理区中选择大小为2order页的页块。

①如果order为0(申请1页)，则从当前处理器的热页队列中选择物理页。如果热页队列中有要求类型的页，则选择其一并将其从队列中摘下；如果热页队列中没有要求类型的页，则从free_area中一次性申请batch个该种类型的页，将它们插入热页队列，并从其中选择一个页。

②如果order大于0，则直接从free_area[i](i>=order)中选择页块。如果i>order，需要将所选的大页块拆分成小伙伴。在大页块拆分出来的两个小伙伴中，大序号的伙伴被插入到free_area的队列中，被选中的总是序号最小的伙伴。

③如果整个管理区中都没有与请求者要求类型一致的页块，则从其它类型中迁移1个尽可能大的页块到要求类型的队列中，而后再次选择页块。这里的“其它类型”由迁移类型尝试序列决定，但不含RESERVE类型。如果迁移过来的页块足够大(超过半个页组)，则将整个页组改成要求类型，相当于从其它类型中迁移过来一个页组；否则保持页组的类型不变，相当于在一种类型的页组中强行分配一个其它类型的小页块。

④如果无法从其它类型中迁移页块，则尝试从RESERVE类型中选择页块。

(4)设置页块的管理结构，将其分配给请求者。

①找到所选页块中起始页的page结构，将它的private清0，_count置1。

②如果需要，将页块的内容全部清0。

③如果所选页块超过1页且请求者提出了要求，则将其组织成复合页。复合页(compound)的起始页称为头页，其余页称为尾页。在复合页中，所有页的first_page都指向起始页的page结构，第一个尾页的lru.prev中记录页块的大小、lru.next中记录页块的解构函数。

(5)如果分配过程失败，说明系统中的物理内存出现了紧缺现象。

①唤醒在节点上等待的守护进程kswapd，让它去回收物理内存。这些守护进程在后台运行。

②放松检查条件，如仅检查MIN基准线或根本不再检查基准线，而后再次尝试分配内存。

③如果仍然失败，则直接回收物理内存，并回收当前处理器的热页，而后再次尝试分配内存。④如果仍然失败，说明内存真的耗尽了(OutofMemory)，则启动进程杀手(killer)尝试停止一些进程来回收物理内存，而后再次尝试分配内存。

⑤如果仍然失败，则显示信息，通报内存分配失败。

Linux的伙伴内存管理器提供了多个物理内存分配函数，其中alloc_pages()类的函数得到的是起始页的page结构，而_

_get_free_pages()类的函数得到的是起始页的内核线性地址。6.2.4内核线性地址分配

页块分配操作所分配的物理内存页块可能属于低端内存，也可能属于高端内存。内核可能需要访问这些内存页块，也可能不需要访问它们(仅给用户进程使用)。由于系统未为高端内存预分配内核线性地址，因而当内核需要访问来自高端的内存页块时，伙伴内存管理器必须临时为它们分配内核线性地址。

Linux在内核线性地址空间(3GB～4GB)中为高端内存预留了1024页的kmap区间(起始线性地址是PKMAP_BASE)，专门用于为高端内存临时指派内核线性地址。在系统初始化时，Linux已为kmap区间建立了1个页表pkmap_page_table。所谓为一个内存页分配临时的内核线性地址实际就是在页表pkmap_page_table中找一个空的页表项，将其中的页基地址(PageBaseAddress)改为内存页的物理地址。内核线性地址的分配以页为单位，一次一页。由多个页组成的页块可能会分配到不连续的内核线性地址。为了管理临时线性地址的分配，Linux定义了数组pkmap_count来记录kmap区间中各页的使用情况，如下：

intpkmap_count[LAST_PKMAP]; //LAST_PKMAP=1024

数组pkmap_count的某元素为0表示与之对应的内核线性地址当前是空闲的，可以将其分配给新的内存页。为内存页分配内核线性地址之后，通过页表pkmap_page_table可以方便地将线性地址转换成物理地址，但却难以将物理地址转换成线性地址。为了方便查找物理页的内核线性地址，Linux又定义了结构page_address_map来记录物理页与内核线性地址的对应关系，并定义了Hash表page_address_htable，如图6.9所示。

structpage_address_map{

structpage *page; //内存页的管理结构

void *virtual; //内核线性地址

structlist_head list;

};

structpage_address_map page_address_maps[LAST_PKMAP];

staticstructpage_address_slot{

structlist_head lh; //page_address_map结构队列

spinlock_t lock; //队列保护锁

}_cacheline_aligned_in_smp page_address_htable[1<<PA_HASH_ORDER];

图6.9高端内存页的内核线性地址当需要为某高端内存页分配内核线性地址时，Linux首先从数组pkmap_count中找一个空闲的页表项，得到一个空闲的内核线性地址，而后修改页表pkmap_page_table，将其映射到指定的内存页，同时填写一个page_address_map结构，并将该结构插入到Hash表page_address_htable中。此后，用页的物理地址查Hash表page_address_htable即可得到它的内核线性地址。在图6.9中，为内存页j分配的内核线性地址是：PKMAP_BASE+i*PAGE_SIZE。

当内核不再使用高端页时，应该释放它占用的线性地址，包括清除它的页表项、删除它在Hash表page_address_htable中的page_address_map结构等。

如果在分配过程中发现已没有空闲的页表项，则请求者必须等待。为了满足无法等待的请求者的需要，Linux在“FixedVirtualAddress”区间为每个处理器预留了8页的内核线性地址，用于应急。

Linux提供了一组函数，用于管理高端内存页的线性地址，其中kmap()为高端内存页分配内核线性地址，kunmap()释放高端内存页的内核线性地址，kmap_atomic()将一个高端内存页映射到“FixedVirtualAddress”区间的一个固定位置，kunmap_atomic()清除高端内存页到“FixedVirtualAddress”的映射。6.2.5物理页块释放

如果正在使用的物理页块又变成空闲的，那么应该将其还给伙伴内存管理器，这一过程称为物理页块的释放。释放是分配的逆过程。

一般情况下，被释放的页块应该插入到free_area数组的某个空闲页块队列中，队列位置由页块的大小和迁移类型决定。与分配过程相反，在释放过程中应该尽可能地将小页块合并成大页块。如果被释放页块的伙伴也是空闲的，就应该将它们合并，而后插入到free_area的更高阶队列中。合并的过程可能是递归的，一个小页块的释放可能会引起一连串的合并。页块释放过程中需要解决的问题主要有两个，一是确定伙伴的编号，二是确定伙伴是否在指定的队列中。根据页块的大小和编号，可以比较容易地算出其伙伴的编号。确定伙伴是否在指定队列的方法要稍微麻烦一点。在早期的版本中，Linux为free_area的每个队列准备了一个位图，两个伙伴合用其中的一位，0表示伙伴不在队列中，1表示伙伴在队列中。随着内存的增大、队列的增多，位图的开销变得难以承受，因而在新版本中，Linux取消了队列位图，改用page结构来判断伙伴的位置。为此Linux做了如下约定：当将空闲页块插入free_area时，要在其起始页的flags上设置PG_buddy标志，并在private中记录页块的大小(即order)。除起始页之外，空闲页块的其余页上均不能设置PG_buddy标志，其private也应被清0。确定伙伴是否在指定队列的方法如下：

(1)根据页块的编号B1和大小2order，算出其伙伴的编号B2=B1^(1<<order)。

(2)如果B2在空洞中，那么B1的伙伴不在指定队列中。

(3)如果B2和B1不在一个管理区中，那么B1的伙伴不在指定队列中。

(4)如果B2的flags上有PG_buddy标志且其private等于order，则B1的伙伴在指定队列中。

假如要释放页块属于zone管理区，其大小是2order页，迁移类型是migratetype，那么页块应被插入到zone的free_area[order].free_list[migratetype]队列中。如果页块的伙伴不在该队列中，则应先设置起始页上的标志，而后再将其直接插入队列。如果页块的伙伴在该队列中，则应将它的伙伴从队列中摘下，清除伙伴起始页上的标志，将它们合并成大小为2order+1页的页块，而后再将其插入到free_area[order+1].free_list[migratetype]中。当然，此次插入仍需要判断其伙伴是否在队列中，并在可能的情况下进行页块合并。如果页块的大小达到了最大(如210页)，则不需要再合并。

上述释放算法的好处是总能得到大的空闲页块，大页块可以满足未来更多的需要，问题是合并过于积极。过于积极的合并会导致未来不必要的拆分，带来额外的系统开销。新版本的Linux增加了热页队列，试图将合并工作向后推迟。如果要释放的是单个物理页，直接将其加入到当前处理器的热页队列的队头即可，不需要将其与伙伴合并。当然，合并推迟不是无限制的，如果热页队列的长度超过了预设的基准(high)线，则要一次性地将其中batch个空闲页归还给free_area。归还的物理页全部位于热页队列的队尾，基本已属于冷页。缓存而后批量处理是Linux经常采用的Lazy策略，基于Lazy策略的分配与释放算法可有效地减少拆分与合并的次数，提高伙伴内存管理的性能。

Linux的伙伴内存管理器提供了多个物理内存释放函数，其中free_pages()类函数的参数是起始页的page结构，而_

_free_pages()类函数的参数是起始页的内核线性地址。

伙伴内存管理器十分有效，但它只能分配物理上连续的内存页块。虽然伙伴内存管理器会尽力合并小页块，但随着系统的运行，内存页块仍然有碎化的趋势。当碎化严重时，伙伴内存管理器虽能回收到足够的空闲内存，却无法将它们合并成大的页块，无法满足请求者的需求。为解决这一问题，Linux在伙伴内存管理器的基础上又提供了逻辑内存管理器，试图向它的用户提供仅在逻辑上连续的大块内存。6.3逻辑内存管理事实上，在启动分页机制之后，不管是操作系统内核还是应用程序，在访问内存时使用的都是逻辑或线性地址，因而只要逻辑上连续就已足够，并不需要真正的物理连续。逻辑内存管理器就建立在这一事实之上，它利用内核中一块连续的线性地址空间为其用户模拟出逻辑上连续的大内存块。由多个逻辑上连续的内存页构成的页块称为逻辑页块，逻辑页块的大小不用遵循2的指数次方的约定，可以由任意多个页构成。为实现逻辑内存管理，Linux已在初始化时专门预留了128MB的内核线性地址空间，其开始地址为VMALLOC_START，终止地址为VMALLOC_END(见图3.4)。利用这块内核线性地址空间可实现逻辑页块的分配，其步骤大致如下：

(1)在VMALLOC_START和VMALLOC_END之间找一块足够大的线性地址区间。

(2)向伙伴内存管理器申请一组物理页，每次1页，不要求物理上连续。

(3)修改第0号进程的页目录、页表，建立内核线性地址到物理地址的映射。

步骤的后两步比较容易实现，困难的是线性地址区间的分配。虽然可以用伙伴算法管理这块线性地址空间，但逻辑内存管理器选用了更为简单的动态分区法，即根据请求者的需要动态地从预留的内核线性地址空间中划出小区间。为了实现区间的动态划分，避免交叉重叠，逻辑内存管理器需要知道预留空间的使用情况，如哪些部分是空闲的、哪些部分已分配出去等。Linux用结构vm_struct描述已分配的线性地址区间，如下：

structvm_struct{

structvm_struct *next;

void *addr; //区间开始线性地址

unsignedlong size; //区间大小

unsignedlong flags; //标志

structpage **pages; //组成逻辑内存页块的物理内存页

unsignedint nr_pages; //区间的页数

unsignedlong phys_addr; //映射的I/O物理地址

};一个vm_struct结构描述预留线性地址空间中的一段连续的区间，它由若干个逻辑页组成，其中的每个逻辑页又被映射到一个物理页，形成了一个逻辑上连续的内存页块，即逻辑页块，如图6.10所示。

系统中所有的vm_struct结构组成一个单向的有序队列，vmlist是队头，如图6.11所示。队列中的vm_struct结构按addr排列，从小到大，逻辑页块间至少有1页的隔离带。

图6.10结构vm_struct描述的逻辑内存块

图6.11vmlist队列与逻辑页块两个相邻逻辑页块之间的空隙是隔离带。在早期的实现中，逻辑内存管理器采用最先适应算法分配逻辑页块，即顺序搜索vmlist队列(或者说顺序搜索空闲页块队列)，从第一个满足要求的空闲页块中划出需要的页数，组成新的逻辑页块并将其分配给请求者。在新版本中，为了加快查找和分配的速度，Linux另外定义了一个vmap_area结构。与vm_struct一样，vmap_area描述的也是已分配的线性地址区间，但与vm_struct不同，系统中的vmap_area结构被组织成一棵红黑树。结构vm_struct与vmap_area关联在一起，通过搜索红黑树可以快速找到vm_struct结构。从左到右顺序搜索红黑树，可以找到所有的空闲区间，从而实现空闲区间的分配。

如果找不到足够大的空闲区间，则分配失败。

由于逻辑内存管理器要为物理页重新指派内核线性地址，因而应尽可能从高端内存中为逻辑页块分配物理页。当然可以从低端内存中分配物理页，但从低端内存中分配的物理页会有两个内核线性地址，显然是一种浪费。逻辑内存管理器所管理的线性地址空间(VMALLOC_START到VMALLOC_END)还有另外一个用处，即为板卡上的I/O内存分配临时的内核线性地址，以便在内核中能直接访问它们。

逻辑内存管理器所管理的内核线性地址空间是有限的、紧缺的，因而在用完之后，应该尽快释放。释放操作与分配操作相反，它将一个逻辑页块中的所有物理页逐个还给伙伴内存管理器并清除各逻辑页在第0号进程中的页表项，而后将vm_struct结构从队列中摘下并释放掉。由于逻辑内存管理器仅修改第0号进程的页表，因而其它进程(包括申请者)访问逻辑页块时可能会引起页故障异常。页故障异常处理程序会修正这一错误，见8.4.4。

函数vmalloc()用于分配逻辑页块，vfree()用于释放逻辑页块。函数vmap()用于将一组物理页映射到一块内核线性地址区间，从而将它们组织成一个逻辑页块；函数vunmap()用于释放一个逻辑页块所占用的内核线性地址区间。函数ioremap()用于为I/O内存分配内核线性地址，函数iounmap()用于释放I/O内存所占用的内核线性地址。

伙伴内存管理器与逻辑内存管理器合作，可以为内核提供大内存服务。然而，内核在运行过程中最经常使用的还是小内存(小于1页)，如建立数据结构、缓冲区等。内核对小内存的使用极为频繁且种类繁多，使用它们的时机和数量难以预估，无法预先分配，只能动态地创建和撤销。由于伙伴内存管理器与逻辑内存管理器的分配粒度都较大，由它们直接提供小内存服务会造成较大的浪费。6.4对象内存管理为了满足内核对小内存的需求，提高物理内存的利用率，Linux引入了对象内存管理器。早期的Linux中仅有一种对象内存管理器，称为Slab。新版本的Linux又引入了其它两种对象内存管理器，分别称为Slub和Slob。三种对象管理器具有相同的接口。

对象内存管理器建立在伙伴内存管理器之上，它将来自伙伴内存管理器的大块内存划分成小对象分配给请求者，并将回收到的小对象组合成大块内存后还给伙伴内存管理器。如果将伙伴内存管理器看成批发商的话，那么对象内存管理器就是零售商，或者说是内存对象的缓存。6.4.1Slab管理器

一个Slab就是从伙伴内存管理器申请到的一个物理内存页块，该页块被划分成了一组大小相等的小块，称为内存对象。每个对象都可满足内核的一种特殊需求。具有相同属性的一到多个Slab构成一个Cache(缓存)，一个Cache管理一种类型的内存对象。当需要小内存时，内核从预建的Cache中申请内存对象，用完之后再将其还给Cache。当一个Cache中的内存对象被用完后，Slab管理器会为其追加新的Slab。当物理内存紧缺时，伙伴内存管理器会从Cache中回收完全空闲的Slab。由此可见，Slab管理器定义了一个层次型的管理结构，Slab管理器管理一组Cache，每个Cache管理一组Slab，每个Slab管理一组内存对象，如图6.12所示。

图6.12Slab管理器的层次结构

Slab管理器对内存对象的大小基本没有限制，对一个Cache中的Slab数也基本未作限制。一个Cache中可以没有Slab，也可以有多个Slab。一个Slab中可能没有空闲内存对象(已用满)，可能有空闲内存对象，也可能全是空闲内存对象(空闲)。

1.管理结构

虽然可以让Cache直接管理内存对象，但以页块(Slab)为单位的内存对象管理更便于空闲页块的回收，因而至少应该为Slab管理器定义两种管理结构，一个是Cache管理结构，另一个是Slab管理结构。

Slab结构管理由同一块物理内存划分出来的内存对象，其定义如下：

structslab{

structlist_head list;

unsignedlong colouroff; //首部着色区的大小

void *s_mem; //第一个内存对象的开始地址

unsignedint inuse; //已分配出去的对象数

kmem_bufctl_t free; //空闲对象队列的队头

unsignedshort nodeid; //所属节点的编号

};

为了对内存对象实施管理，Slab的首要任务是描述各个内存对象的使用情况。可以用位图标识空闲的内存对象，但比较方便的方法是将一个Slab中的空闲内存对象组织成一个队列，并在slab结构中记录队列的队头。早期的Linux在每个内存对象的尾部都加入一个指针用于将空闲的内存对象串联成一个真正的队列，如图6.13所示。然而这一额外的指针不仅增加了对象的长度，而且容易使本来规整的对象尺寸变得不规整，会造成较大的空间浪费。新版本的Linux去掉了内存对象尾部的指针，将它们集中在一个数组中，用数组中的指针模拟内存对象，用数组内部的链表模拟内存对象队列。进一步地，Linux将数组中的指针换成了对象序号，利用序号将空闲的内存对象串成队列。由于不同Slab中的对象数有较大的差别，不宜将序号数组直接定义在slab结构中。事实上，序号数组是与slab结构一起动态建立的，其大小取决于Slab中的对象数，其位置紧接在slab结构之后，如图6.13所示。域free中记录的是空闲内存对象队列的队头，也就是第一个空闲内存对象的序号。

图6.13Slab管理结构

Slab管理器不限制内存对象的尺寸，但为了提高内存访问的性能，应该对对象尺寸进行适当地规范，如将对象尺寸规约成处理器一级缓存(L1cache)中缓存行(CacheLine)大小(64或32字节)的倍数，即让对象的开始位置都位于缓存行的边界处。即使经过了规约，在将页块划分成内存对象的过程中，通常还是会剩余一小部分空间(在所有内存对象之外，称为外部碎片，有别于对象尾部的内部碎片)。剩余的小空间可以集中在页块的首部或尾部，但也可以分散在首尾两处。通过调整剩余空间在页块首尾的分布，可以调整各内存对象的起始位置(偏移量)，从而调整对象在高速缓存中的位置，减少一级缓存冲突，提高内存访问速度。Slab管理器将剩余的小空间称为着色区，如图6.13所示。着色区被分成色块，色块大小是缓存行的长度。Slab首部的色块数记录在colouroff域中。同一Cache中的不同Slab应有不同的colouroff。

结构slab与序号数组捆绑在一起，可以位于Slab内部(如在页块的首部或尾部)，也可以位于Slab外部(单独建立)。Slab管理器会选用碎片最小的实现方案。

Cache的管理信息记录在结构kmem_cache中，其内容可大致可分成如下几部分：

(1)

Cache描述信息。Cache的名称为name、属性为flags、活跃状况为free_touched，所有的Cache结构被其中的next链接成双向循环链表，表头是cache_chain。

(2)

Slab描述信息，用于新Slab的创建。当需要创建新的Slab时，Slab管理器向伙伴内存管理器申请大小为2gfporder页、满足gfpflags要求的页块，该页块被划分成num个内存对象，对象大小(规约后)为buffer_size字节，剩余的着色区由colour个色块组成，色块大小为colour_off字节，下一个Slab的首部色块数为colour_next。在一个Slab中，管理结构(包括slab结构和序号数组)占用slab_size字节。如果需将slab结构建立在页块之外，可从专用的Cache中申请管理结构，指针slabp_cache指向该Cache。在分配内存对象之前，可以使用构造函数ctor对其初始化。

(3)

Slab队列nodelists，用于组织同一Cache中的所有slab结构。Slab队列由结构kmem_list3定义，每个内存节点一个，其中还包含一些统计信息，如Cache中属于各内存节点的空闲对象数free_objects、在各节点中最多允许拥有的空闲对象数free_limit、下次回收各节点内存对象的时间next_reap等。

(4)热对象(hotobject)栈管理信息。每个Cache中都包含一个热对象栈array，用于缓存Cache中的热对象。

在早期的版本中，Linux为每个Cache仅准备了一个slab结构队列，但做了简单的排序，前部是已用满的Slab，尾部是完全空闲的Slab。为了维护队列的顺序，每次对象分配、释放后都需要调整Slab的位置，额外的开销较大。新版本的Linux在每个Cache中为每个内存节点都准备了三个slab结构队列，分别用于组织部分满的、完全满的和完全空闲的slab结构。与“热页队列”相似，Slab管理器为每个处理器建立了一个“热对象”栈，用于记录该处理器新释放的、可能还在L1Cache中的内存对象。热对象栈由结构array_cache定义，每个处理器一个，如下：

structarray_cache{

unsignedint avail; //当前可用的热对象数

unsignedint limit; //上限

unsignedint batchcount; //对象批的大小

unsignedint touched; //最近是否被用过

spinlock_t lock; //保护锁，基本可以不用

void *entry[]; //热对象栈

};新释放的内存对象被压入堆栈entry中缓存，avail是栈顶位置。当缓存中的热对象数超过limit时，再将其中batchcount个热对象还给Slab。Slab管理器总是试图从热对象栈中分配内存对象。当热对象栈为空时，Slab管理器会一次性向其中转移batchcount个内存对象。可以认为，热对象栈是Cache中内存对象的一个缓存。图6.14是一个Cache的管理结构。图6.14Cache管理结构

2. Cache创建

Linux允许为经常使用的每种数据结构创建一个独立的Cache。从这类Cache中申请到的内存不仅大小恰能满足建立一个数据结构的需要，而且可认为其内容已经过了适当的初始化。Slab管理器的这一特性可简化数据结构的管理。

创建一个Cache其实就是创建一个kmem_cache结构，当然，创建者需要提供一些参数，如名称、对象尺寸、对齐方式、构造函数、特殊要求等。Cache的创建过程如下：

(1)从cache_cache中申请一个对象，用于建立kmem_cache结构。

(2)根据创建者的特殊要求和对齐方式，调整对象尺寸。如果对象尺寸大于512字节，应将管理结构建立在Slab之外，否则应将管理结构建立在Slab内部。当然创建者可以不管对象的尺寸，强行要求将管理结构建立在Slab之外。

(3)根据对象尺寸、对齐方式、Slab管理结构位置等信息，确定Slab页块的大小，并据此算出Slab管理结构的大小、一个页块可划分出的对象数及剩余空间(碎片)的大小等。早期的Linux会选择较大的页块以使碎片最小化，新版本的Linux选择能满足要求的最小页块，以减少大页块的消耗。

PAGE_SIZE<<gfporder=head+num

×

buffer_size+colour

×

colour_off

其中head是管理结构大小。如果管理结构在Slab外，head=0。

碎片大小不应超过页块的1/8。如果碎片大小可容下Slab的管理结构，则应将管理结构建在Slab内。

(4)如果需要将管理结构建立在Slab之外，还要为其找一个合适的通用Cache。

(5)根据对象大小算出可在Cache中缓存的热对象数(如表6.2所示)，为每个在线处理器创建一个热对象管理结构，包括结构array_cache和其后的entry数组。

(6)如果对象尺寸不超过1页，则为Cache建立一个共享的热对象管理结构，用于管理在处理器间共享的热对象。共享热对象栈的大小是8

×

batchcount。

(7)为每一个在线的节点(Node)创建一个kmem_list3结构，用于组织其上的Slab，其中的域free_limit=(1+节点中的处理器数)

×

batchcount+num。

(8)将填写号的kmem_cache结构插入到链表cache_chain中。

表6.2内存对象大小与热对象数的关系3. Slab创建

新建的Cache仅有一个管理结构，其中没有任何Slab。Cache的Slab是在使用过程中动态创建的。当Slab管理器发现Cache中已没有空闲的内存对象时，即为其创建一个新的Slab。Slab的创建过程如下：

(1)找到当前节点的kmem_list3结构，根据其中的colour_next折算出新Slab的首部着色区大小offset，并将colour_next加1(循环加)。

(2)向伙伴内存管理器申请2gfporder页连续的物理内存，用于建立Slab。

(3)建立Slab管理结构。

①如果管理结构位于Slab之外，则从slabp_cache中再申请一块内存，用于建立slab结构和序号数组。

②如果管理结构位于Slab内部，则从所申请页块的首部(加上着色区offset)划出slab_size字节的内存，用于建立slab结构和序号数组。

(4)在页块的page结构上增加管理信息。Slab页块由2gfporder页组成，其中每一页都有一个page结构，对所有这些page结构做如下设置，以备后用：

①在flags域中加入PG_Slab标志，表示它们正被用做Slab。②让lru.prev指向slab结构。

③让lru.next指向kmem_cache结构。

(5)初始化Slab中的内存对象及管理结构，包括：

①如果Cache有构造函数ctor，则用该构造函数初始化每个内存对象。

②将序号数组中的所有元素串成一个队列，表示所有对象都处于空闲状态。序号数组的最后一个元素设为BUFCTL_END(0xFFFFFFFF)，表示队尾。

③设置slab结构，将free设为序号队列的队头，将inuse清0，将s_mem设为第一个对象的开始地址，将colouroff设为第一个对象的偏移量。

(6)将结构kmem_list3的free_objects加num，将新建的slab结构插入到它的free队列中，表示新增加了num个空闲内存对象。4.对象分配

从对象内存管理器申请对象时需要指出对象所属的Cache和对对象的特殊要求，不需要指出对象的大小，因为Cache中的对象尺寸已经预先确定。

从Cache中分配对象的工作按从易到难的顺序进行，大致如下：

(1)如果当前处理器的热对象栈不空，则栈顶的热对象最有可能驻留在L1Cache中，应该将该对象分配出去。

(2)如果当前处理器的热对象栈为空，但Cache的共享热对象栈不空，则先从共享热对象栈中转移一批对象到热对象栈中，而后再将栈顶的对象分配出去。

(3)如果Cache的共享对象栈也为空，则先从Cache的Slab中转移一批对象到热对象栈中，而后再将栈顶的对象分配出去。

(4)如果Cache中已没有空闲对象，则先为其创建一个新的Slab，并将其中的一批对象转移到热对象栈中，而后再将栈顶的对象分配出去。

批的大小不超过batchcount。从Slab中转移对象的工作实际就是从Slab中逐个分配对象的工作。分配的顺序是先部分空闲的Slab(在partial队列中)再完全空闲的Slab(在free队列中)。从Slab中分配一个对象的过程如下：

(1)确定要分配的对象。要分配对象的序号是free，它的开始地址是：

s_mem+buffer_size

×

free

(2)调整空闲对象队列。在Slab的序号数组中，序号为free的元素的内容是下一个空闲对象的序号，将该序号存入slab结构的free域中(删除原队头)。

(3)将slab结构中的inuse加1，表示又分配出去1个对象。