鲁达 每天十五分钟，熟读一个技术点，水滴石穿，一切只为渴望更优秀的你！
————零声学院
6.3 内存的分配和回收
在内存初始化完成以后，内存中就常驻有内核映像（内核代码和数据）。以后，随着用
户程序的执行和结束，就需要不断地分配和释放物理页面。内核应该为分配一组连续的页面
而建立一种稳定、高效的分配策略。为此，必须解决一个比较重要的内存管理问题，即外碎
片问题。频繁地请求和释放不同大小的一组连续页面，必然导致在已分配的内存块中分散许
多小块的空闲页面。由此带来的问题是，即使这些小块的空闲页面加起来足以满足所请求的
页面，但是要分配一个大块的连续页面可能就根本无法满足。Linux 采用著名的伙伴（Buddy）
系统算法来解决外碎片问题。
但是请注意，在 Linux 中，CPU 不能按物理地址来访问存储空间，而必须使用虚拟地址；
因此，对于内存页面的管理，通常是先在虚存空间中分配一个虚存区间，然后才根据需要为
此区间分配相应的物理页面并建立起映射，也就是说，虚存区间的分配在前，而物理页面的
分配在后，但是为了承接上一节的内容，我们先介绍内存的分配和回收，然后再介绍用户进
程虚存区间的建立。
6.3.1 伙伴算法
1．原理
Linux 的伙伴算法把所有的空闲页面分为 10 个块组，每组中块的大小是 2 的幂次方个页
面，例如，第 0 组中块的大小都为 20 （1 个页面），第 1 组中块的大小都为 21 （2 个页面），
第 9 组中块的大小都为 29 （512 个页面）。也就是说，每一组中块的大小是相同的，且这同样
大小的块形成一个链表。
我们通过一个简单的例子来说明该算法的工作原理。
假设要求分配的块的大小为 128 个页面（由多个页面组成的块我们就叫做页面块）。该
算法先在块大小为 128 个页面的链表中查找，看是否有这样一个空闲块。如果有，就直接分
配；如果没有，该算法会查找下一个更大的块，具体地说，就是在块大小 256 个页面的链表
中查找一个空闲块。如果存在这样的空闲块，内核就把这 256 个页面分为两等份，一份分配
出去，另一份插入到块大小为 128 个页面的链表中。如果在块大小为 256 个页面的链表中也
没有找到空闲页块，就继续找更大的块，即 512 个页面的块。如果存在这样的块，内核就从
512 个页面的块中分出 128 个页面满足请求，然后从 384 个页面中取出 256 个页面插入到块
大小为 256 个页面的链表中。然后把剩余的 128 个页面插入到块大小为 128 个页面的链表中。
如果 512 个页面的链表中还没有空闲块，该算法就放弃分配，并发出出错信号。
以上过程的逆过程就是块的释放过程，这也是该算法名字的来由。满足以下条件的两个
块称为伙伴：
（1）两个块的大小相同；
（2）两个块的物理地址连续。
伙伴算法把满足以上条件的两个块合并为一个块，该算法是迭代算法，如果合并后的块
还可以跟相邻的块进行合并，那么该算法就继续合并。
2．数据结构
在 6.2.6 节中所介绍的管理区数据结构 struct zone_struct 中，涉及到空闲区数据结
构：
free_area_t free_area[MAX_ORDER];
我们再次对 free_area_t 给予较详细的描述。
#difine MAX_ORDER 10 type struct free_area_struct { struct list_head free_list unsigned int *map } free_area_t其中 list_head 域是一个通用的双向链表结构，链表中元素的类型将为 mem_map_t（即
struct page 结构）。Map 域指向一个位图，其大小取决于现有的页面数。free_area 第 k 项
位图的每一位，描述的就是大小为 2k 个页面的两个伙伴块的状态。如果位图的某位为 0，表
示一对兄弟块中或者两个都空闲，或者两个都被分配，如果为 1，肯定有一块已被分配。当
兄弟块都空闲时，内核把它们当作一个大小为 2k+1的单独快来处理。如图 6.9 给出该数据结
构的示意图。
图 6.9 中，free_aea 数组的元素 0 包含了一个空闲页（页面编号为 0）；而元素 2 则包
含了两个以 4 个页面为大小的空闲页面块，第一个页面块的起始编号为 4，而第二个页面块
的起始编号为 56。
我们曾提到，当需要分配若干个内存页面时，用于 DMA 的内存页面必须是连续的。其实
为了便于管理，从伙伴算法可以看出，只要请求分配的块大小不超过 512 个页面（2KB），内
核就尽量分配连续的页面。
6.3.2 物理页面的分配和释放
当一个进程请求分配连续的物理页面时，可以通过调用 alloc_pages()来完成。Linux 2.4
版本中有两个 alloc_pages()，一个在 mm 中，另一个在 mm/page_alloc,c 中，编译
时根据所定义的条件选项 CONFIG_DISCONTIGMEM 来进行取舍。
1．非一致存储结构（NUMA）中页面的分配
CONFIG_DISCONTIGMEM 条件编译的含义是“不连续的存储空间”，Linux 把不连续的存储
空间也归类为非一致存储结构（NUMA）。这是因为，不连续的存储空间本质上是一种广义的
NUMA，因为那说明在最低物理地址和最高物理地址之间存在着空洞，而有空洞的空间当然是
“不一致”的。所以，在地址不连续的物理空间也要像结构不一样的物理空间那样划分出若干
连续且均匀的“节点”。因此，在存储结构不连续的系统中，每个模块都有若干个节点，因而
都有个 pg_data_t 数据结构队列。我们先来看 mm 中的 alloc_page()函数：
/* * This can be refined. Currently, tries to do round robin, instead * should do concentratic circle search, starting from current node. */ struct page * _alloc_pages（unsigned int gfp_mask, unsigned int order） { struct page *ret = 0; pg_data_t *start, *temp; #ifndef CONFIG_NUMA unsigned long flags; static pg_data_t *next = 0; #endif if （order >= MAX_ORDER） return NULL; #ifdef CONFIG_NUMA temp = NODE_DATA（numa_node_id（））; #else spin_lock_irqsave（&node_lock, flags）; if （!next） next = pgdat_list; temp = next; next = next->node_next; spin_unlock_irqrestore（&node_lock, flags）; #endif start = temp; while （temp） { if （（ret = alloc_pages_pgdat（temp, gfp_mask, order））） return（ret）; temp = temp->node_next; } temp = pgdat_list; while （temp != start） { if （（ret = alloc_pages_pgdat（temp, gfp_mask, order））） return（ret）; temp = temp->node_next; } return（0）; }对该函数的说明如下。
该函数有两个参数。gfp_mask 表示采用哪种分配策略。参数 order 表示所需物理块的大
小，可以是 1、2、3 直到 2MAX_ORDER-1。
如果定义了 CONFIG_NUMA，也就是在 NUMA 结构的系统中，可以通过 NUMA_DATA（）宏找
到 CPU 所在节点的 pg_data_t 数据结构队列，并存放在临时变量 temp 中。
如果在不连续的 UMA 结构中，则有个 pg_data_t 数据结构的队列 pgdat_list，pgdat_list
就是该队列的首部。因为队列一般都是临界资源，因此，在对该队列进行两个以上的操作时
要加锁。
分配时轮流从各个节点开始，以求各节点负荷的平衡。函数中有两个循环，其形式基本
相同，也就是，对节点队列基本进行两遍扫描，直至在某个节点内分配成功，则跳出循环，
否则，则彻底失败，从而返回 0。对于每个节点，调用 alloc_pages_pgdat（）函数试图分配
所需的页面。
2．一致存储结构(UMA)中页面的分配
连续空间 UMA 结构的 alloc_page()是在 include/linux 中定义的：
#ifndef CONFIG_DISCONTIGMEM static inline struct page * alloc_pages（unsigned int gfp_mask, unsigned int order） { /* * Gets optimized away by the compiler. */ if （order >= MAX_ORDER） return NULL; return __alloc_pages（gfp_mask, order, con（gfp_mask & GFP_ZONEMASK））; } #endif从这个函数的定义可以看出， alloc_page()是 _alloc_pages（）的封装函数，而
_alloc_pages（）才是伙伴算法的核心。这个函数定义于 mm 中，我们先对此
函数给予概要描述。
_alloc_pages（）在管理区链表 zonelist 中依次查找每个区，从中找到满足要求的区，
然后用伙伴算法从这个区中分配给定大小（2 order个）的页面块。如果所有的区都没有足够的
空闲页面，则调用 swapper 或 bdflush 内核线程，把脏页写到磁盘以释放一些页面。
在__alloc_pages()和虚拟内存（简称 VM）的代码之间有一些复杂的接口（后面会详细
描述）。每个区都要对刚刚被映射到某个进程 VM 的页面进行跟踪，被映射的页面也许仅仅做
了标记，而并没有真正地分配出去。因为根据虚拟存储的分配原理，对物理页面的分配要尽
量推迟到不能再推迟为止，也就是说，当进程的代码或数据必须装入到内存时，才给它真正
分配物理页面。
搞清楚页面分配的基本原则后，我们对其代码具体分析如下：
/* * This is the 'heart' of the zoned buddy allocator: */ struct page * __alloc_pages（unsigned int gfp_mask, unsigned int order, zonelist_t *zonelist） { unsigned long min; zone_t **zone, * classzone; struct page * page; int freed; zone = zonelist->zones; classzone = *zone; min = 1UL << order; for （;;） { zone_t *z = *（zone++）; if （!z） break; min += z->pages_low; if （z->free_pages > min） { page = rmqueue（z, order）; if （page） return page; } }这是对一个分配策略中所规定的所有页面管理区的循环。循环中依次考察各个区中空闲
页面的总量，如果总量尚大于“最低水位线”与所请求页面数之和，就调用 rmqueue（）试
图从该区中进行分配。如果分配成功，则返回一个 page 结构指针，指向页面块中第一个页面
的起始地址。
classzone->need_balance = 1; mb（）; if （waitqueue_active（&kswapd_wait）） wake_up_interruptible（&kswapd_wait）;如果发现管理区中的空闲页面总量已经降到最低点，则把 zone_t 结构中需要重新平衡
的标志（need_balance）置 1，而且如果内核线程 kswapd 在一个等待队列中睡眠，就唤醒它，
让它收回一些页面以备使用（可以看出，need_balance 是和 kswapd 配合使用的）。
zone = zonelist->zones; min = 1UL << order; for （;;） { unsigned long local_min; zone_t *z = *（zone++）; if （!z） break; local_min = z->pages_min; if （!（gfp_mask & __GFP_WAIT）） local_min >>= 2; min += local_min; if （z->free_pages > min） { page = rmqueue（z, order）; if （page） return page; } }如果给定分配策略中所有的页面管理区都分配失败，那只好把原来的“最低水位”再向
下调（除以 4），然后看是否满足要求（z->free_pages > min），如果能满足要求，则调用 rmqueue
（）进行分配。
/* here we're in the low on memory slow path */ rebalance: if （current->flags & （PF_MEMALLOC | PF_MEMDIE）） { zone = zonelist->zones; for （;;） { zone_t *z = *（zone++）; if （!z） break; page = rmqueue（z, order）; if （page） return page; } return NULL; }如果分配还不成功，这时候就要看是哪类进程在请求分配内存页面。其中 PF_MEMALLOC
和 PF_MEMDIE 是进程的 task_struct 结构中 flags 域的值，对于正在分配页面的进程（如
kswapd 内核线程），则其 PF_MEMALLOC 的值为 1（一般进程的这个标志为 0），而对于使内存
溢出而被杀死的进程，则其 PF_MEMDIE 为 1。不管哪种情况，都说明必须给该进程分配页面
（想想为什么）。因此，继续进行分配。
/* Atomic allocations - we can't balance anything */ if （!（gfp_mask & __GFP_WAIT）） return NULL;如果请求分配页面的进程不能等待，也不能被重新调度，只好在没有分配到页面的情况
下“空手”返回。
page = balance_classzone（classzone, gfp_mask, order, &freed）; if （page） return page;如果经过几番努力，必须得到页面的进程（如 kswapd）还没有分配到页面，就要调用
balance_classzone（）函数把当前进程所占有的局部页面释放出来。如果释放成功，则返回
一个 page 结构指针，指向页面块中第一个页面的起始地址。
zone = zonelist->zones; min = 1UL << order; for （;;） { zone_t *z = *（zone++）; if （!z） break; min += z->pages_min; if （z->free_pages > min） { page = rmqueue（z, order）; if （page） return page; } }继续进行分配。
/* Don't let big-order allocations loop * if （order > 3） return NULL; /* Yield for kswapd, and try again */ current->policy |= SCHED_YIELD; __set_current_state（TASK_RUNNING）; schedule（）; goto rebalance; }在这个函数中，频繁调用了 rmqueue（）函数，下面我们具体来看一下这个函数内容。
（1）rmqueue（）函数
该函数试图从一个页面管理区分配若干连续的内存页面。这是最基本的分配操作，其具
体代码如下：
static struct page * rmqueue（zone_t *zone, unsigned int order） { free_area_t * area = zone->free_area + order; unsigned int curr_order = order; struct list_head *head, *curr; unsigned long flags; struct page *page; spin_lock_irqsave（&zone->lock, flags）; do { head = &area->free_list; curr = memlist_next（head）; if （curr != head） { unsigned int index; page = memlist_entry（curr, struct page, list）; if （BAD_RANGE（zone,page）） BUG（）; memlist_del（curr）; index = page - zone->zone_mem_map; if （curr_order != MAX_ORDER-1） MARK_USED（index, curr_order, area）; zone->free_pages -= 1UL << order; page = expand（zone, page, index, order, curr_order, area）; spin_unlock_irqrestore（&zone->lock, flags）; set_page_count（page, 1）; if （BAD_RANGE（zone,page）） BUG（）; if （PageLRU（page）） BUG（）; if （PageActive（page）） BUG（）; return page; } curr_order++; area++; } while （curr_order < MAX_ORDER）; spin_unlock_irqrestore（&zone->lock, flags）; return NULL; }对该函数的解释如下。
参数 zone 指向要分配页面的管理区，order 表示要求分配的页面数为 2 order 。
do 循环从 free_area 数组的第 order 个元素开始，扫描每个元素中由 page 结构组成的
双向循环空闲队列。如果找到合适的页块，就把它从队列中删除，删除的过程是不允许其他
进程、其他处理器来打扰的。所以要用 spin_lock_irqsave（）将这个循环加上锁。
首先在恰好满足大小要求的队列里进行分配。其中 memlist_entry(curr, struct page,
list)获得空闲块的第 1 个页面的地址，如果这个地址是个无效的地址，就陷入 BUG()。如果
有效，memlist_del(curr)从队列中摘除分配出去的页面块。如果某个页面块被分配出去，就
要在 frea_area 的位图中进行标记，这是通过调用 MARK_USED（）宏来完成的。
如果分配出去后还有剩余块，就通过 expand（）获得所分配的页块，而把剩余块链入适
当的空闲队列中。
如果当前空闲队列没有空闲块，就从更大的空闲块队列中找。
（2）expand（）函数
该函数源代码如下。
static inline struct page * expand （zone_t *zone, struct page *page, unsigned long index, int low, int high, free_area_t * area） { unsigned long size = 1 << high; while （high > low） { if （BAD_RANGE（zone,page）） BUG（）; area--; high--; size >>= 1; memlist_add_head（&（page）->list, &（area）->free_list）; MARK_USED（index, high, area）; index += size; page += size; } if （BAD_RANGE（zone,page）） BUG（）; return page; }对该函数解释如下。
参数 zone 指向已分配页块所在的管理区；page 指向已分配的页块；index 是已分配的
页面在 mem_map 中的下标； low 表示所需页面块大小为 2 low，而 high 表示从空闲队列中实
际进行分配的页面块大小为 2 high；area 是 free_area_struct 结构，指向实际要分配的页块。
通过上面介绍可以知道，返回给请求者的块大小为 2low 个页面，并把剩余的页面放入合
适的空闲队列，且对伙伴系统的位图进行相应的修改。例如，假定我们需要一个 2 页面的块，
但是，我们不得不从 order 为 3（8 个页面）的空闲队列中进行分配，又假定我们碰巧选择物
理页面 800 作为该页面块的底部。在我们这个例子中，这几个参数值为：
page == mem_map+800
index == 800
low == 1
high == 3
area == zone->free_area+high （ 也就是 frea_area 数组中下标为 3 的元素）
首先把 size 初始化为分配块的页面数(例如，size = 1<<3 == 8)
while 循环进行循环查找。每次循环都把 size 减半。如果我们从空闲队列中分配的一个
块与所要求的大小匹配，那么 low = high，就彻底从循环中跳出，返回所分配的页块。
如果分配到的物理块所在的空闲块大于所需块的大小（即 2 high>2low），那就将该空闲块
分为两半（即 area--;high--; size >>= 1）,然后调用 memlist_add_head（）把刚分配出去
的页面块又加入到低一档（物理块减半）的空闲队列中，准备从剩下的一半空闲块中重新进
行分配，并调用 MARK_USED（）设置位图。
在上面的例子中，第 1 次循环，我们从页面 800 开始，把页面大小为 4（即 2high--）的块
其首地址插入到 frea_area[2]中的空闲队列；因为 low<high，又开始第 2 次循环，这次从页
面 804 开始，把页面大小为 2 的块插入到 frea_area[1]中的空闲队列，此时，page＝806，
high=low＝1，退出循环，我们给调用者返回从 806 页面开始的一个 2 页面块。
从这个例子可以看出，这是一种巧妙的分配算法。
3．释放页面
从上面的介绍可以看出，页面块的分配必然导致内存的碎片化，而页面块的释放则可以
将页面块重新组合成大的页面块。页面的释放函数为__free_pages(page struct *page,
unsigned long order) ，该函数从给定的页面开始，释放的页面块大小为 2order。原函数为:
void __free_pages（page struct *page, unsigned long order） { if （!PageReserved（page） && put_page_testzero（page）） __free_pages_ok（page, order）; }其中比较巧妙的部分就是调用 put_page_testzero()宏，该函数把页面的引用计数减 1，
如果减 1 后引用计数为 0，则该函数返回 1。因此，如果调用者不是该页面的最后一个用户，
那么，这个页面实际上就不会被释放。另外要说明的是不可释放保留页 PageReserved，这是
通过 PageReserved（）宏进行检查的。
如果调用者是该页面的最后一个用户，则__free_pages() 再调用 __free_pages_ok()。
__free_pages_ok（）才是对页面块进行释放的实际函数，该函数把释放的页面块链入空闲链
表，并对伙伴系统的位图进行管理，必要时合并伙伴块。这实际上是 expand()函数的反操作，
我们对此不再进行详细的讨论。
6.3.3 Slab 分配机制
采用伙伴算法分配内存时，每次至少分配一个页面。但当请求分配的内存大小为几十个
字节或几百个字节时应该如何处理？如何在一个页面中分配小的内存区，小内存区的分配所
产生的内碎片又如何解决？
Linux 2.0 采用的解决办法是建立了 13 个空闲区链表，它们的大小从 32 字节到 132056
字节。从 Linux 2.2 开始，MM 的开发者采用了一种叫做 Slab 的分配模式，该模式早在 1994
年就被开发出来，用于 Sun Microsystem Solaris 2.4 操作系统中。Slab 的提出主要是基于
以下考虑。
内核对内存区的分配取决于所存放数据的类型。例如，当给用户态进程分配页面时，内
核调用 get_free_page()函数，并用 0 填充这个页面。而给内核的数据结构分配页面时，事
情没有这么简单，例如，要对数据结构所在的内存进行初始化、在不用时要收回它们所占用
的内存。因此，Slab 中引入了对象这个概念，所谓对象就是存放一组数据结构的内存区，其
方法就是构造或析构函数，构造函数用于初始化数据结构所在的内存区，而析构函数收回相
应的内存区。但为了便于理解，你也可以把对象直接看作内核的数据结构。为了避免重复初
始化对象，Slab 分配模式并不丢弃已分配的对象，而是释放但把它们依然保留在内存中。当
以后又要请求分配同一对象时，就可以从内存获取而不用进行初始化，这是在 Solaris 中引
入 Slab 的基本思想。
实际上，Linux 中对 Slab 分配模式有所改进，它对内存区的处理并不需要进行初始化或
回收。出于效率的考虑，Linux 并不调用对象的构造或析构函数，而是把指向这两个函数的
指针都置为空。Linux 中引入 Slab 的主要目的是为了减少对伙伴算法的调用次数。
实际上，内核经常反复使用某一内存区。例如，只要内核创建一个新的进程，就要为该
进程相关的数据结构（task_struct、打开文件对象等）分配内存区。当进程结束时，收回这
些内存区。因为进程的创建和撤销非常频繁，因此，Linux 的早期版本把大量的时间花费在
反复分配或回收这些内存区上。从 Linux 2.2 开始，把那些频繁使用的页面保存在高速缓存
中并重新使用。
可以根据对内存区的使用频率来对它分类。对于预期频繁使用的内存区，可以创建一组
特定大小的专用缓冲区进行处理，以避免内碎片的产生。对于较少使用的内存区，可以创建
一组通用缓冲区（如 Linux 2.0 中所使用的 2 的幂次方）来处理，即使这种处理模式产生碎
片，也对整个系统的性能影响不大。
硬件高速缓存的使用，又为尽量减少对伙伴算法的调用提供了另一个理由，因为对伙伴
算法的每次调用都会“弄脏”硬件高速缓存，因此，这就增加了对内存的平均访问次数。
Slab 分配模式把对象分组放进缓冲区（尽管英文中使用了 Cache 这个词，但实际上指的
是内存中的区域，而不是指硬件高速缓存）。因为缓冲区的组织和管理与硬件高速缓存的命中
率密切相关，因此，Slab 缓冲区并非由各个对象直接构成，而是由一连串的“大块（Slab）”
构成，而每个大块中则包含了若干个同种类型的对象，这些对象或已被分配，或空闲，如图
6.10 所示。一般而言，对象分两种，一种是大对象，一种是小对象。所谓小对象，是指在一
个页面中可以容纳下好几个对象的那种。例如，一个 inode 结构大约占 300 多个字节，因此，
一个页面中可以容纳 8 个以上的 inode 结构，因此，inode 结构就为小对象。Linux 内核中把
小于 512 字节的对象叫做小对象。
实际上，缓冲区就是主存中的一片区域，把这片区域划分为多个块，每块就是一个 Slab，
每个 Slab 由一个或多个页面组成，每个 Slab 中存放的就是对象。
因为 Slab 分配模式的实现比较复杂，我们不准备对其进行详细的分析，只对主要内容
给予描述。
1．Slab 的数据结构
Slab 分配模式有两个主要的数据结构，一个是描述缓冲区的结构 kmem_cache_t，一个
是描述 Slab 的结构 kmem_slab_t，下面对这两个结构给予简要讨论。
（1）Slab
Slab 是 Slab 管理模式中最基本的结构。它由一组连续的物理页面组成，对象就被顺序
放在这些页面中。其数据结构在 mm 中定义如下：
/* * slab_t * * Manages the objs in a slab. Placed either at the beginning of mem allocated * for a slab, or allocated from an general cache. * Slabs are chained into three list: fully used, partial, fully free slabs. */ typedef struct slab_s { struct list_head list; unsigned long colouroff; void *s_mem; /* including colour offset */ unsigned int inuse; /* num of objs active in slab */ kmem_bufctl_t free; } slab_t;这里的链表用来将前一个 Slab 和后一个 Slab 链接起来形成一个双向链表，colouroff
为该 Slab 上着色区的大小，指针 s_mem 指向对象区的起点，inuse 是 Slab 中所分配对象的
个数。最后，free 的值指明了空闲对象链中的第一个对象，kmem_bufctl_t 其实是一个整数。
Slab 结构的示意图如图 6.11 所示。
对于小对象，就把 Slab 的描述结构 slab_t 放在该 Slab 中；对于大对象，则把 Slab 结
构游离出来，集中存放。关于 Slab 中的着色区再给予具体描述。
每个 Slab 的首部都有一个小小的区域是不用的，称为“着色区（Coloring Area）”。
着色区的大小使 Slab 中的每个对象的起始地址都按高速缓存中的“缓存行（Cache Line）”
大小进行对齐（80386 的一级高速缓存行大小为 16 字节，Pentium 为 32 字节）。因为 Slab
是由 1 个页面或多个页面（最多为 32）组成，因此，每个 Slab 都是从一个页面边界开始的，
它自然按高速缓存的缓冲行对齐。但是，Slab 中的对象大小不确定，设置着色区的目的就是
将 Slab 中第一个对象的起始地址往后推到与缓冲行对齐的位置。因为一个缓冲区中有多个
Slab，因此，应该把每个缓冲区中的各个 Slab 着色区的大小尽量安排成不同的大小，这样可
以使得在不同的 Slab 中，处于同一相对位置的对象，让它们在高速缓存中的起始地址相互错
开，这样就可以改善高速缓存的存取效率。
每个 Slab 上最后一个对象以后也有个小小的废料区是不用的，这是对着色区大小的补
偿，其大小取决于着色区的大小，以及 Slab 与其每个对象的相对大小。但该区域与着色区的
总和对于同一种对象的各个 Slab 是个常数。
每个对象的大小基本上是所需数据结构的大小。只有当数据结构的大小不与高速缓存中
的缓冲行对齐时，才增加若干字节使其对齐。所以，一个 Slab 上的所有对象的起始地址都必
然是按高速缓存中的缓冲行对齐的。
（2）缓冲区
每个缓冲区管理着一个 Slab 链表，Slab 按序分为 3 组。第 1 组是全满的 Slab（没有空
闲的对象），第 2 组 Slab 中只有部分对象被分配，部分对象还空闲，最后一组 Slab 中的对象
全部空闲。只所以这样分组，是为了对 Slab 进行有效的管理。每个缓冲区还有一个轮转锁
（Spinlock），在对链表进行修改时用这个轮转锁进行同步。类型 kmem_cache_s 在 mm
中定义如下：
struct kmem_cache_s { /* 1） each alloc & free */ /* full, partial first, then free */ struct list_head slabs_full; struct list_head slabs_partial; struct list_head slabs_free; unsigned int objsize; unsigned int flags; /* constant flags */ unsigned int num; /* # of objs per slab */ spinlock_t spinlock; #ifdef CONFIG_SMP unsigned int batchcount; #endif /* 2） slab additions /removals */ /* order of pgs per slab （2^n） */ unsigned int gfporder; /* force GFP flags, e.g. GFP_DMA */ unsigned int gfpflags; size_t colour; /* cache colouring range */ unsigned int colour_off; /* colour offset */ unsigned int colour_next; /* cache colouring */ kmem_cache_t *slabp_cache; unsigned int growing; unsigned int dflags; /* dynamic flags */ /* constructor func */ void （*ctor）（void *, kmem_cache_t *, unsigned long）; /* de-constructor func */ void （*dtor）（void *, kmem_cache_t *, unsigned long）; unsigned long failures; /* 3） cache creation/removal */ char name[CACHE_NAMELEN]; struct list_head next; #ifdef CONFIG_SMP /* 4） per-cpu data */ cpucache_t *cpudata[NR_CPUS]; #endif ….. };然后定义了 kmem_cache_t，并给部分域赋予了初值：
static kmem_cache_t cache_cache = { slabs_full: LIST_HEAD_INIT（cac）, slabs_partial: LIST_HEAD_INIT（cac）, slabs_free: LIST_HEAD_INIT（cac）, objsize: sizeof（kmem_cache_t）, flags: SLAB_NO_REAP, spinlock: SPIN_LOCK_UNLOCKED, colour_off: L1_CACHE_BYTES, name: "kmem_cache", };对该结构说明如下。
该结构中有 3 个队列 slabs_full、slabs_partial 以及 slabs_free，分别指向满 Slab、
半满 Slab 和空闲 Slab，另一个队列 next 则把所有的专用缓冲区链成一个链表。
除了这些队列和指针外，该结构中还有一些重要的域：objsize 是原始的数据结构的大
小，这里初始化为 kmem_cache_t 的大小；num 表示每个 Slab 上有几个缓冲区；gfporder 则
表示每个 Slab 大小的对数，即每个 Slab 由 2 gfporder个页面构成。
如前所述，着色区的使用是为了使同一缓冲区中不同 Slab 上的对象区的起始地址相互
错开，这样有利于改善高速缓存的效率。colour_off 表示颜色的偏移量，colour 表示颜色的
数量；一个缓冲区中颜色的数量取决于 Slab 中对象的个数、剩余空间以及高速缓存行的大小。
所以，对每个缓冲区都要计算它的颜色数量，这个数量就保存在 colour 中，而下一个 Slab
将要使用的颜色则保存在 colour_next 中。当 colour_next 达到最大值时，就又从 0 开始。
着色区的大小可以根据（colour_off×colour）算得。例如，如果 colour 为 5，colour_off
为 8，则第一个 Slab 的颜色将为 0，Slab 中第一个对象区的起始地址（相对）为 0，下一个
Slab 中第一个对象区的起始地址为 8，再下一个为 16，24，32，0……等。
cache_cache 变量实际上就是缓冲区结构的头指针。
由此可以看出，缓冲区结构 kmem_cache_t 相当于 Slab 的总控结构，缓冲区结构与 Slab
结构之间的关系如图 6.12 所示。
在图 6.12 中，深灰色表示全满的 Slab，浅灰色表示含有空闲对象的 Slab，而无色表示
空的 Slab。缓冲区结构之间形成一个单向链表，Slab 结构之间形成一个双向链表。另外，缓
冲区结构还有分别指向满、半满、空闲 Slab 结构的指针。
2．专用缓冲区的建立和撤销
专用缓冲区是通过 kmem_cache_create（）函数建立的，函数原型为：
kmem_cache_t *kmem_cache_create（const char *name, size_t size, size_t offset,
unsigned long c_flags,
void （*ctor） （void *objp, kmem_cache_t *cachep, unsigned long flags）,
void （*dtor） （void *objp, kmem_cache_t *cachep, unsigned long flags））
对其参数说明如下。
（1）name： 缓冲区名 ( 19 个字符)。
（2）size： 对象大小。
（3）offset ：所请求的着色偏移量。
（4）c_flags ：对缓冲区的设置标志。
• SLAB_HWCACHE_ALIGN：表示与第一个高速缓存中的缓冲行边界（16 或 32 字节）对齐。
• SLAB_NO_REAP：不允许系统回收内存。
• SLAB_CACHE_DMA：表示 Slab 使用的是 DMA 内存。
（5）ctor ：构造函数（一般都为 NULL）。
（6）dtor ：析构函数（一般都为 NULL）。
（7）objp ：指向对象的指针。
（8）cachep ：指向缓冲区。
对专用缓冲区的创建过程简述如下。
kmem_cache_create（）函数要进行一系列的计算，以确定最佳的 Slab 构成。包括：每
个 Slab 由几个页面组成，划分为多少个对象；Slab 的描述结构 slab_t 应该放在 Slab 的外
面还是放在 Slab 的尾部；还有“颜色”的数量等等。并根据调用参数和计算结果设置
kmem_cache_t 结构中的各个域，包括两个函数指针 ctor 和 dtor。最后，将 kmem_cache_t
结构插入到 cache_cache 的 next 队列中。
但请注意，函数 kmem_cache_create（）所创建的缓冲区中还没有包含任何 Slab，因此，
也没有空闲的对象。只有以下两个条件都为真时，才给缓冲区分配 Slab：
（1）已发出一个分配新对象的请求；
（2）缓冲区不包含任何空闲对象。
当这两个条件都成立时，Slab 分配模式就调用 kmem_cache_grow（）函数给缓冲区分配
一个新的 Slab。其中，该函数调用 kmem_gatepages()从伙伴系统获得一组页面；然后又调用
kmem_cache_slabgmt()获得一个新的 Slab结构；还要调用 kmem_cache_init_objs()为新 Slab
中的所有对象申请构造方法（如果定义的话）；最后，调用 kmem_slab_link_end()把这个 Slab
结构插入到缓冲区中 Slab 链表的末尾。
Slab 分配模式的最大好处就是给频繁使用的数据结构建立专用缓冲区。但到目前的版本
为止，Linux 内核中多数专用缓冲区的建立都用 NULL 作为构造函数的指针，例如，为虚存区
间结构 vm_area_struct 建立的专用缓冲区 vm_area_cachep：
vm_area_cachep = kmem_cache_create（"vm_area_struct",
sizeof（struct vm_area_struct）, 0,
SLAB_HWCACHE_ALIGN, NULL, NULL）;
就把构造和析构函数的指针置为 NULL，也就是说，内核并没有充分利用 Slab 管理机制
所提供的好处。为了说明如何利用专用缓冲区，我们从内核代码中选取一个构造函数不为空
的简单例子，这个例子与网络子系统有关，在 net/core 中定义：
void __init skb_init（void） { int i; skbuff_head_cache = kmem_cache_create（"skbuff_head_cache", sizeof（struct sk_buff）, 0, SLAB_HWCACHE_ALIGN, skb_headerinit, NULL）; if （!skbuff_head_cache） panic（"cannot create skbuff cache"）; for （i=0; i<NR_CPUS; i++） skb_queue_head_init（&skb_head_pool[i].list）; }从代码中可以看出，skb_init（）调用 kmem_cache_create（）为网络子系统建立一个
sk_buff 数据结构的专用缓冲区，其名称为“skbuff_head_cache”（ 你可以通过读取／
proc/slabinfo/文件得到所有缓冲区的名字）。调用参数 offset 为 0，表示第一个对象在 Slab
中的位移并无特殊要求。但是参数 flags 为 SLAB_HWCACHE_ALIGN，表示 Slab 中的对象要与
高速缓存中的缓冲行边界对齐。对象的构造函数为 skb_headerinit（），而析构函数为空，
也就是说，在释放一个 Slab 时无需对各个缓冲区进行特殊的处理。
当从内核卸载一个模块时，同时应当撤销为这个模块中的数据结构所建立的缓冲区，这
是通过调用 kmem_cache_destroy()函数来完成的。从 Linux 2.4.16 内核代码中进行查找可
知，对这个函数的调用非常少。
3．通用缓冲区
在内核中初始化开销不大的数据结构可以合用一个通用的缓冲区。通用缓冲区非常类似
于物理页面分配中的大小分区，最小的为 32，然后依次为 64、128、……直至 128KB（即 32
个页面），但是，对通用缓冲区的管理又采用的是 Slab 方式。从通用缓冲区中分配和释放缓
冲区的函数为：
void *kmalloc（size_t size, int flags）;
Void kree（const void *objp）;
因此，当一个数据结构的使用根本不频繁时，或其大小不足一个页面时，就没有必要给
其分配专用缓冲区，而应该调用 kmallo()进行分配。如果数据结构的大小接近一个页面，则
干脆通过 alloc_page()为之分配一个页面。
事实上，在内核中，尤其是驱动程序中，有大量的数据结构仅仅是一次性使用，而且所
占内存只有几十个字节，因此，一般情况下调用 kmallo()给内核数据结构分配内存就足够了。
另外，因为，在 Linux 2.0 以前的版本一般都调用 kmallo()给内核数据结构分配内存，因此，
调用该函数的一个优点是（让你开发的驱动程序）能保持向后兼容。
6.3.4 内核空间非连续内存区的管理
我们说，任何时候，CPU 访问的都是虚拟内存，那么，在你编写驱动程序，或者编写模
块时，Linux 给你分配什么样的内存？它处于 4GB 空间的什么位置？这就是我们要讨论的非
连续内存。
首先，非连续内存处于 3GB 到 4GB 之间，也就是处于内核空间，如图 6.13 所示。
图 6.13 中，PAGE_OFFSET 为 3GB，high_memory 为保存物理地址最高值的变量，
VMALLOC_START 为非连续区的的起始地址，定义于 include／i386 中：
#define VMALLOC_OFFSET （8*1024*1024）
#define VMALLOC_START （（（unsigned long） high_memory + 2*VMALLOC_OFFSET-1） & \~
（VMALLOC_OFFSET-1））
在物理地址的末尾与第一个内存区之间插入了一个 8MB（VMALLOC_OFFSET）的区间，这
是一个安全区，目的是为了“捕获”对非连续区的非法访问。出于同样的理由，在其他非连
续的内存区之间也插入了 4KB 大小的安全区。每个非连续内存区的大小都是 4096 的倍数。
1．非连续区的数据结构
描述非连续区的数据结构为 struct vm_struct，定义于 include/linux 中：
struct vm_struct { unsigned long flags; void * addr; unsigned long size; struct vm_struct * next; };struct vm_struct * vmlist;
非连续区组成一个单链表，链表第一个元素的地址存放在变量 vmlist 中。Addr 域是内
存区的起始地址；size 是内存区的大小加 4096(安全区的大小)。
2．创建一个非连续区的结构
函数 get_vm_area（）创建一个新的非连续区结构，其代码在 mm 中：
struct vm_struct * get_vm_area（unsigned long size, unsigned long flags） { unsigned long addr; struct vm_struct **p, *tmp, *area; area = （struct vm_struct *） kmalloc（sizeof（*area）, GFP_KERNEL）; if （!area） return NULL; size += PAGE_SIZE; addr = VMALLOC_START; write_lock（&vmlist_lock）; for （p = &vmlist; （tmp = *p） ; p = &tmp->next） { if （（size + addr） < addr） goto out; if （size + addr <= （unsigned long） tmp->addr） break; addr = tmp->size + （unsigned long） tmp->addr; if （addr > VMALLOC_END-size） goto out; } area->flags = flags; area->addr = （void *）addr; area->size = size; area->next = *p; *p = area; write_unlock（&vmlist_lock）; return area; out: write_unlock（&vmlist_lock）; kfree（area）; return NULL; }这个函数比较简单，就是在单链表中插入一个元素。其中调用了 kmalloc()和 kfree()
函数,分别用来为 vm_struct 结构分配内存和释放所分配的内存。
3．分配非连续内存区
vmalloc（）函数给内核分配一个非连续的内存区，在/include/linux 中定
义如下：
static inline void * vmalloc （unsigned long size） { return __vmalloc（size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL）; } vmalloc（）最终调用的是__vmalloc（）函数，该函数的代码在 mm 中： void * __vmalloc （unsigned long size, int gfp_mask, pgprot_t prot） { void * addr; struct vm_struct *area; size = PAGE_ALIGN（size）; if （!size || （size >> PAGE_SHIFT） > num_physpages） { BUG（）; return NULL; } area = get_vm_area（size, VM_ALLOC）; if （!area） return NULL; addr = area->addr; if （vmalloc_area_pages（VMALLOC_VMADDR（addr）, size, gfp_mask, prot）） { vfree（addr）; return NULL; } return addr; }函数首先把 size 参数取整为页面大小（4096）的一个倍数，也就是按页的大小进行对
齐，然后进行有效性检查，如果有大小合适的可用内存，就调用 get_vm_area（）获得一个
内存区的结构。但真正的内存区还没有获得，函数 vmalloc_area_pages（）真正进行非连续
内存区的分配：
inline int vmalloc_area_pages （unsigned long address, unsigned long size, int gfp_mask, pgprot_t prot） { pgd_t * dir; unsigned long end = address + size; int ret; dir = pgd_offset_k（address）; spin_lock（&ini）; do { pmd_t *pmd; pmd = pmd_alloc（&init_mm, dir, address）; ret = -ENOMEM; if （!pmd） break; ret = -ENOMEM; if （alloc_area_pmd（pmd, address, end - address, gfp_mask, prot）） break; address = （address + PGDIR_SIZE） & PGDIR_MASK; dir++; ret = 0; } while （address && （address < end））; spin_unlock（&ini）; return ret; }该函数有两个主要的参数，address 表示内存区的起始地址，size 表示内存区的大小。
内存区的末尾地址赋给了局部变量 end。其中还调用了几个主要的函数或宏。
（1）pgd_offset_k（）宏导出这个内存区起始地址在页目录中的目录项。
（2）pmd_alloc（）为新的内存区创建一个中间页目录。
（3）alloc_area_pmd（）为新的中间页目录分配所有相关的页表，并更新页的总目录；
该函数调用 pte_alloc_kernel()函数来分配一个新的页表，之后再调用 alloc_area_pte（）
为页表项分配具体的物理页面。
（4）从 vmalloc_area_pages（）函数可以看出，该函数实际建立起了非连续内存区到物
理页面的映射。
4．kmalloc()与 vmalloc()的区别
kmalloc()与 vmalloc() 都是在内核代码中提供给其他子系统用来分配内存的函数，但
二者有何区别？
从前面的介绍已经看出，这两个函数所分配的内存都处于内核空间，即从 3GB～4GB；但位
置不同，kmalloc()分配的内存处于 3GB～high_memory 之间，而 vmalloc()分配的内存在
VMALLOC_START～4GB 之间，也就是非连续内存区。一般情况下在驱动程序中都是调用 kmalloc()
来给数据结构分配内存，而 vmalloc()用在为活动的交换区分配数据结构，为某些 I/O 驱动程
序分配缓冲区，或为模块分配空间，例如在 include/asm-i386 中定义了如下语句：
#define module_map（x） vmalloc（x）
其含义就是把模块映射到非连续的内存区。
与 kmalloc()和 vmalloc()相对应，两个释放内存的函数为 kfree()和 vfree()。