内核中的函数以比较直接了当的方式获得动态内存：
- __get_free_pages() 或 alloc_pages() 从分区页框分配器获得页框。
- kmem_cache_alloc() 或 kmalloc() 使用 slab 分配器为专用或通用对象分配块。
- vmalloc() 或 vmalloc_32() 获得一块非连续的内存。
如果请求的内存区得以满足，会返回一个页描述符地址或线性地址。
RAM 的某些部分被永久地分配给内核，并用来存放内核代码及静态内核数据结构。
RAM 的其余部分称为动态内存。整个系统的性能取决于如果有效地管理动态内存。
后续部分：
页框管理和内存区管理会涉及对连续物理内存区处理的两种不同技术。
非连续内存区管理涉及处理非连续内存区的技术。
页框管理
Linux 采用 4KB 页框大小作为标准的内存分配单元，有如下两个原因：
- 分页单元引发的缺页异常很容易得到解释，或者是请求的页存在但不允许进程对其访问，或者是请求的页不存在。
- 主存和磁盘之间传输小块数据时更高效。
页描述符
页框的状态信息保存在一个类型为 page 的页描述符中，长度为 32 字节，所有的页描述存放在 mem_map 数组中。
virt_to_page(addr) 宏产生线性地址 addr 对应的页描述符。
pfn_to_page(pfn) 宏产生与页框号 pfn 对应的页描述符地址。
页描述符中的其中两个字段：
- _count，页的引用计数器。 -1：相应页框空闲，并可被分配给任一进程或内核本身；>= 0：页框被分配给了一个或多个进程，或用于存放一些内核数据结构。
page_count() 返回 _count 加 1 后的值，即该页的使用者数目。
- flags，包含多达 32 个用来描述页框状态的标志。
非一致内存访问（NUMA）
系统的物理内存被划分为几个节点。一个单独的节点内，任一给定 CPU 访问所有页面的时间是相同的，但对于不同 CPU，访问不同页面的时间可能不同。
每个节点都有一个类型为 pg_data_t 的描述符，存放于单向链表 pgdat_list。
区
每个节点内的物理内存可分为几个区。
80×86 体系结构的两种硬约束：
- ISA 总线的 DMA 处理器只能对 RAM 的前 16MB 寻址。
- 大容量 RAM 的现代 32 位计算机中，因为线性地址空间太小，CPU 无法直接访问所有物理内存。
为此，物理内存被划分为 3 个区
- ZONE_DMA，包含低于 16MB 的内存页框
- ZONE_NORMAL，包含高于 16MB 且低于 896MB 的内存页框。
- ZONE_HIGHMEM，包含从 896MB 开始高于 896MB 的内存页框。
ZONE_DMA 和 ZONE_NORMAL 区包含内存的“常规”页框，把它们线性映射到线性地址空间的第 4 个 GB后，内核就可以直接访问。
ZONE_HIGHMEM 区包含的内存页不能由内核直接访问，尽管它们页线性地映射到了线性地址空间的第 4 个 GB。64 位体系结构中，ZONE_HIGNMEM 为空。
每个区都有自己的描述符，其中许多字段用于回收页框。
每个页描述符都有到内存节点和到节点区的链接。为节省空间，链接方式被编码成索引存放在 flags 字段的高位。
page_zone() 参数为页描述符的地址，它读取页描述符中 flags 字段的最高位，然后通过查看 zone_table 数组来确定相应区描述符的地址。在启动时用所有内存节点的所有区描述符的地址初始化该数组。
内核调用一个内存分配函数时，必须指明请求页框所在的区。zonelist 为区描述符指针数组。
保留的页框池
当请求内存时，如果没有足够的空闲内存可用，发出请求的内核控制路径会被阻塞，直到有内存释放。
但是，一些内核控制路径不能被阻塞，如在处理中断或执行临界区内的代码时。此时，应当产生原子分配请求。
为尽量保证原子请求不失败，内核保留了一个页框池，只有在内存不足时才使用。
保留内存的数量（以 KB 为单位）存放在 min_free_kbytes 变量中，初始值在内核初始化时设置，与直接映射到内核线性地址空间第 4 个 GB 的物理内存数量—即包含在 ZONE_DMA 和 ZONE_NORMAL 内存区内的页框数目有关。
min_free_kbytes 的初始值不能小于 128 也不能大于 65536。
ZONE_DMA 和 ZONE_NORMAL 区将一定数量的页框作为保留内存。
内存区描述符的 pages_min 字段为区保留页框的数目。
分区页框分配器
区分配器接受动他内存分配与释放的请求。
每个区内，页框被伙伴系统处理。为达到更好的系统性能，一小部分页框保留在高速缓存中，以快速满足对单个页框的分配请求。
高端内存页框的内核映射
直接映射的物理内存末端、高度内存的始端所对应的线性地址存放在 high_memory 变量中，被设置为 896MB。
896MB 边界以上的页框不映射到内核线性地址空间的第 4 个 GB，因此，不能被内核直接访问。
所以，返回所分配页框线性地址的页分配器函数不适用于高端内存，即不适用于 ZONE_HIGHMEM 区内的页框。
32位平台上，Linux 需要通过某种方法运行内核使用所有可使用的 RAM，达到 PAE 所支持的 64GB，采用的方法如下：
- 高端内存页框只能通过 alloc_pages() 和 alloc_page() 分配，它们不返回第一个被分配也看看的线性地址，因为如果该页框属于高端内存，则其线性地址不存在。取而代之，它们返回第一个被分配页框的页描述符的线性地址，该地址是存在的，因为页描述符分配在低端内存后，在内核初始化阶段不会改变。
- 没有线性地址的高端内存中的页框不能被内核访问。内核线性地址空间的最后 128MB 中的一部分专门用于映射高端内存页框，这种映射是暂时的，否则只有 128MB 的高端内存可被访问。通过重复使用线性地址，可在不同时间访问整个高端内存。
内核采用三种不同的机制将页框映射到高端内存：
- 永久内核映射。建立永久内核映射可能会阻塞当前进程。
- 临时内核映射。建立临时内核映射时，内核控制路径不能被阻塞。
- 非连续内存分配。
以上技术没有一种可确保对整个 RAM 同时寻址，因为只有 128MB 的线性地址留给映射高端内存。
永久内核映射
永久内核映射可建立高端页框到内核地址空间的长期映射。主要使用内核页表中一个专门的页表，地址存放在 pkmap_page_table 变量中。
LAST_PKMAP 宏产生页表的表项数，512 或 1024，取决于 PAE 是否被激活。因此，内核一次最多访问 2MB 或 4MB 的高端内存。
页表映射的线性地址从 PKMAP_BASE 开始。pkmap_count 数组存放 LAST_PKMAP 个计数器，每个计数器对应 pkmap_page_table 中的一项。计数器有 3 中情况：
- 0，对应的页表项没有映射任何高端内存页框，并且是可用的。
- 1，对应的页表项没有映射任何高端内存页框，但不可用，因为上次使用后其相应的 TLB 表项还未被刷新。
- n，对应的页表项映射一个高端内存页框，有 n-1 个内核成分在使用该页框。
page_address_htable 散列表记录高端内存页框与永久映射的线性地址之间的联系。
该表中的 page_address_map 数据结构为高端内存中的每一个页框进行当前映射，它包含一个指向页描述符的指针和分配给该页框的线性地址。
page_address() 返回页框对应的线性地址，NULL 表示页框在高端内存中且没有被映射。参数为页描述符指针 page，有如下两种情况：
- 如果页框不在高端内存中（PG_highmem 标志为 0），线性地址存在，并且可通过以下方式获得：计算页框下标，将其转换为物理地址，根据该物理地址得到相应的线性地址。
__va((unsigned long)(page – mem_map) << 12)
- 如果页框在高端内存中（PG_highmem 标志为 1），如果在 page_address_htbale 散列表中找到页框，则返回其线性地址，否则返回 NULL。
kmap() 建立永久内核映射，相当于如下代码：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
2{
3 if(!PageHighMem(page)) // 如果页框不属于高端内存
4 return page_address(page); // 返回页框对应的线性地址
5 return kmap_high(page);
6}
7
8void *kmap_high(struct page *page)
9{
10 unsigned long vaddr;
11 spin_lock(&kmap_lock);
12 vaddr = (unsigned long)page->virtual;
13 if(!vaddr) // 如果页框没有被映射
14 vaddr = map_new_virtual(page); // 把页框的物理地址插入到 pkmap_page_table 某项中，并在 page_address_htbale 中加入一个元素
15 pkmap_count[(vaddr-PKMAP_BASE) >> PAGE_SHIFT]++; // 使得页框的线性地址对应的计数器加 1
16 spin_unlock(&kmap_lock);
17 return (void *)vaddr; // 返回对页框映射的线性地址
18}
19
20map_new_virtual() 执行两个嵌套循环：
21
22for(;;)
23{
24 int count;
25 DECLARE_WAITQUEUE(wait, current);
26 for(count = LAST_PKMAP; cout > 0; --count) // 扫描 pkmap_count 中所有计数器，直到找到一个空值
27 {
28 last_pkmap_nr = (last_pkmap_nr + 1) & (LAST_PKMAP - 1);
29 if(!last_pkmap_nr) // 搜索到最后一个计数器
30 {
31 // 开始另一趟计数器扫描，以搜寻值为 1 的计数器，并将它们的计数器重置为 0，
32 // 删除 page_address_htable 中对应的元素，并在 pkmap_page_table 的所有项上进行 TLB 刷新。
33 flush_all_zero_pkmaps();
34 count = LAST_PKMAP;
35 }
36
37 if(!pkmap_count[last_pkmap_nr]) // 找到一个未使用的项
38 {
39 unsigned long vaddr = PKMAP_BASE + (last_pkmap_nr << PAGE_SHIFT); // 确定该项对应的线性地址
40 set_pte(&(pkmap_page_table[last_pkmap_nr]), mk_pte(page, __pgprot(0x63)));
41 pkmap_count[last_pkmap_nr] = 1; // 表示该项已经被使用
42 set_page_address(page, (void *) vaddr); // 向 page_address_htbale 中插入一个新元素
43 return vaddr; // 返回线性地址
44 }
45 }
46
47 // 没有找到空的计数器，阻塞当前进程，
48 // 直到某个进程释放了 pkmap_page_table 页表中的一个表项
49 current->state = TASK_UNINTERRUPTIBLE;
50 add_wait_queue(&pkmap_map_wait, &wait); // 插入等待队列
51 spin_unlock(&kmap_lock);
52 schedule(); // 放弃 CPU
53 remove_wait_queue(&pkmap_map_wait, &wait);
54 spin_lock(&kmap_lock);
55
56 // 如果没有其他进程已经映射该页，返回线性地址
57 if(page_address(page))
58 return (unsigned long) page_address(page);
59}
60
61
kunmap() 撤销先前由 kmap() 建立的永久内核映射。如果页在高端内存中，则调用 kunmap_high()：
2
3
4
5
6
7
8
9
10
11
12
13
14
2{
3 spin_lock(&kmap_lock);
4
5 // 从页的线性地址计算出在 pkmap_count 数组的索引
6 // 计数器减 1 后与 1 比较，匹配成功表明没有进程在使用页
7 if((--pkmap_count[((unsigned long)page_address(page)-PKMAP_BASE)>>PAGE_SHIFT]) == 1)
8 if(waitqueue_active(&pkmap_map_wait)) // 唤醒由 map_new_virtual() 添加在等待队列中的进程
9 wake_up(&pkmap_map_wait);
10
11 spin_unlock(&kmap_lock);
12}
13
14
临时内核映射
因为临时内核映射从不阻塞当前进程，所以可用在中断处理程序和可延迟函数的内部。
高端内存的任一页框都可通过一个窗口映射到内核空间，留给临时内核映射的窗口树非常少。
每个 CPU 都有自己包含 13 个窗口的集合，用 enum km_type 数据结构表示，其中定义的每个符号标识了窗口的线性地址。
同一窗口不能被两个不同的控制路径同时使用。km_type 结构中的每个符号只能由一种内核成分使用，并以该成份命名。最后一个符号 KM_TYPE_NR 不表示线性地址，而是每个 CPU 可使用的窗口数。
km_type 中的每个符号（除最后一个）都是固定映射的线性地址的一个下标。
enum fixed_addresses 包含了符号 FIX_KMAP_BEGIN 和 FIX_KMAP_END，FIX_KMAP_END = FIX_KMAP_BEGIN + (KM_TYPE_NR * NR_CPUS) – 1。
内核用 fix_to_virt(FIX_KMAP_BEGIN) 线性地址对应的页表项地址初始化 kmap_pte 变量。
kmap_atomic() 建立临时内核映射，等价于如下代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2{
3 enum fixed_address idx;
4 unsigned long vaddr;
5
6 current_thread_info()->preempt_count++;
7 if(!PageHighMem(page))
8 return page_address(page);
9
10 // type 和 CPU 标识符（通过 smp_processor_id()）指定用哪个固定映射的线性地址来映射请求页
11 idx = type + KM_TYPE_NR * smp_precessor_id();
12
13 vaddr = fix_to_virt(FIX_KMAP_BEGIN + idx); // 得到线性地址
14 set_pte(kmap_pte-idx, mk_pte(page, 0x063)); // 初始化 kmap_pte 变量
15 __flush_tlb_single(vaddr); // 刷新 TLB 项
16 return (void *)vaddr; // 返回线性地址
17}
18
19
kunmap_atomic() 销毁临时内核映射。80×86 结构中，减少当前进程的 preempt_count，因此，在请求临时映射前，如果内核控制路径是可抢占的，那么它销毁同一映射后可再次被抢占。
该函数还会检查当前进程的 TIF_NEED_RESCHED 标志是否被置位，如果是，调用 schedule()。
伙伴系统算法
避免外碎片的方法之一：开发一种适当的技术记录现存的空闲连续页框块的情况，以尽量避免为满足对小块的请求而分割大的空闲块。
Linux 采用伙伴系统算法解决外碎片问题。所有的空闲页框被分组为 11 个块链表，每个块链表分别包含大小为 1，2，4，8，16，32，64，128，256，512，1024 个连续的页框。
每个块的第一个页框的物理地址是该块大小的整数倍。
工作原理：
如果要请求一个 256 个页框的块（1MB）
- 先在 256 个页框的链表中查找一个空闲块，如果没有找到，查找下一个更大的页块，即在 512 个页框的链表中查找，如果找到空闲块，将 512 的页框分成两等份，一般用于满足请求，另一半插入到 256 个页框的链表中。
- 如果 512 个页框的块链表中页没有找到空闲块，继续在 1024 个页框的链表中找，如果找到空闲块，其中的 256 用于满足请求，剩余的 768 个页框中，512 个插入到 512 个页框的链表中，256 个插入到 256 个页框的链表中。
- 如果 1024 个页框的链表中也没有找到空闲快，放弃并发出出错信号。
以上过程的逆过程为页框块的释放过程。内核试图把大小为 b 的一对空闲伙伴块合并为一个大小为 2b 的单独块。满足以下条件的两个块称为伙伴：
- 两个块具有相同的大小，记作 b。
- 它们的物理地址连续。
- 第一块的第一个页框的物理地址是 2 * b * $2^{12}$ 的倍数。
算法是迭代的，如果成功合并所释放的块，会试图合并 2b 的块，以再次试图形成更大的块。
数据结构
每个内存区采用不同的伙伴系统。80×86 中，有三种伙伴系统：
- 处理适合 ISA DMA 的页框
- 处理“常规”页框
- 处理高端内存页框
每个伙伴系统使用的主要数据结构如下：
- mem_map 数组。每个内存区都会用到 mem_map 的一个子集，内存区描述符的 zone_mem_map 和 size 字段分别描述 mem_map 中子集的第一个元素和元素个数。
- 包含 free_area 数组，11 个元素，每个元素对应一种块大小，该数组位于内存描述符的 free_area 字段中。
区描述符中 free_area 数组的第 k 个元素标识所有大小为 $2^k$ 的空闲块，该元素的
- free_list 字段是双向循环链表的头，该双向链循环链表中集中了大小为 $2^k$ 页的空闲块对应的页描述符。
- nr_free，指定了大小为 $2^k$ 的空闲块的个数。
一个 $2^k$ 的空闲页块的第一个页的描述符的 private 字段存放了块的 order，即数字 k，这样的话，当页块被释放时，内核可确定该块的伙伴是否页空闲，如果是的话，把两个块结合成大小为 $2^{k+1}$ 页的单一块。
分配块
__rmqueue() 在内存区中找到一个空闲块。需要两个参数：
- 区描述符的地址
- order，标识请求的空闲页块大小的对数值
如果页块被成功分配，__rmqueue() 返回第一个被分配页框的页描述符，否则，返回 NULL。
__rmqueue() 假设调用者已经禁止了本地中断并获得了包含伙伴系统数据结构的 zone->lock 自旋锁。从所请求的 order 的链表开始，扫描每个可用块链表：
2
3
4
5
6
7
8
9
10
11
12
2unsigned int current_order;
3
4for(current_order=order; current_order<11; ++current_order)
5{
6 area = zone->free_area + currernt_order;
7 if(!list_empty(&area->free_list))
8 goto block_found;
9}
10return NULL;
11
12
如果找到一个合适的空闲块，从链表中删除它的第一个页框描述符，并减少内存区描述符中的 free_pages 的值：
2
3
4
5
6
7
8
9
2 page = list_entry(area->free_list.next, strut page, lru);
3 list_del(&page->lru);
4 ClearPagePrivate(page);
5 page->private = 0;
6 area->nr_free--;
7 zone->free_pages -= 1UL << order;
8
9
如果从 curr_order 链表中找到的块大于请求的 order，就执行一个 while 循环：当为了满足 $2^h$ 个页框的请求而有必要使用 $2^k$ 个页框的块时（h < k），程序就分配前面的$2^h$个页框，而把后面 $2^k – 2^h$ 个页框循环再分配给 free_area 链表中下标为 h 到 k 之间的元素：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2while(curr_order > order)
3{
4 area--;
5 curr_order--;
6 size >>= 1;
7 buddy = page + size;
8 list_add(&buddy->lru, &area->free_list);
9 area->nr_free++;
10 buddy->private = curr_order;
11 SetPagePrivate(buddy);
12}
13return page;
14
15
找到合适的空闲块后，返回所分配的第一个页框对应的页描述符的地址 page。
释放块
__free_pages_bulk() 按照伙伴系统的策略释放页框，有 3 个基本输入参数：
-
page，被释放块中所包含的第一个页框描述符的地址。
-
zone，内存区描述符的地址。
-
order，块大小的对数。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2struct page *base = zone->zone_mem_map;
3unsigned long buddy_idx;
4unsigned long page_idx = page - base; // 第一个页框的下标
5struct page *buddy, *coalesced;
6int order_size = 1 << order;
7
8// 增加内存区中空闲页框的计数器
9zone->free_pages += order_size;
10
11while(order < 10)
12{
13 buddy_idx = page_idx ^ (1 << order); // 拥有 page_idx 页描述符下标的块的伙伴
14 buddy = base + buddy_idx; // 伙伴块的页描述符
15 if(!page_is_buddy(buddy, order)) // 检查 buddy 是否描述了大小为 order_size 的空闲页框块的第一个页
16 break; // 跳出循环，因为获得的空闲块不能和其他空闲块合并
17 list_del(&buddy->lru); // 伙伴块被释放，将它从 order 排序的空闲块链表上删除
18 zone->free_area[order].nr_free--;
19 ClearPagePrivate(buddy);
20 buddy->private = 0;
21 page_idx &= buddy_idx;
22 order++;
23}
24
25
page_is_buddy() 不满足后，说明获得的空闲块不能再和其他空闲块合并，将获得空闲块插入适当的链表，并以块大小 order 更新第一个页框的 private 字段：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2coalesced->private = order;
3SetPagePrivate(coalesced);
4list_add(&coalesced->lru, &zone->free_area[order].free_list);
5zone->free_area[order].nr_free++;
6
7int page_is_buddy(struct page *page, int order)
8{
9 // buddy 的第一个页必须为空闲（_count = -1）
10 // 必须属于动态内存（PG_reserved 位清零）
11 // private 字段必须存放将要被释放的块的 order
12 if(PagePrivate(buddy) && page->private == order && !PageReserved(buddy) && page_count(page) == 0)
13 return 1;
14 return 0;
15}
16
17
每 CPU 页框高速缓存
为提高系统性能，每个内存区定义了一个“每 CPU”页框高速缓存，包含一些预分配的页框，被用于满足本地 CPU 发出的单一内存请求。
为每个内存区和每个 CPU 提供了两个高速缓存：
- 热高速缓存，存放页框中所包含的内容很可能就在 CPU 硬件高速缓存中
- 冷高速缓存
如果内核或用户态进程再刚分配到页框后就立即向页框写，那么从热高速缓存中获得的页框对系统性能有利。
实际上，每次对页框存储单元的访问都会导致将另一个页框中的一行放入硬件高速缓存，除非硬件高速缓存已经包含了那行。
如果页框将要被 DMA 操作填充，那么从冷高速缓存中获得页框是方便的。这种情况下，不会涉及到 CPU，且硬件高速缓存的行不会被修改。
实现每 CPU 页框高速缓存的主要数据结构是存放再内存区描述符的 pageset 字段中的一个 per_cpu_pageset 数组数据结构。
per_cpu_pageset 数组中的每个元素对应一个 CPU，每个元素包含两个 per_cpu_pages 描述符，一个留给热高速缓存，另一个留给冷高速缓存。
内核使用两个位监视热高速缓存和冷高速缓存的大小：
- 如果页框个数低于下界 low，内核会从伙伴系统中分配 batch 个单一页框来补充对应的高速缓存。
- 如果页框个数高过上界 high，内核从高速缓存中释放 batch 个页框到伙伴系统中。
通过每 CPU 页框高速缓存分配页框
buffered_rmqueue() 在指定的区中分配页框。使用每 CPU 页框高速缓存来处理单一页框请求。
参数：
- 区描述符地址
- 请求分配的内存大小的对数 order
- 分配标志 gfp_flags。如果 gfp_flags 中的 __GFP_COLD 标志被置位，页框从冷高速缓存获取，否则从热高速缓存获取。
buffered_rmqueue() 本质上执行如下操作：
- if(order != 0) 每 CPU 页框高速缓存不能被使用，跳到第 4 步。
- if(per_cpu_pages 描述符的 count 字段 <= low 字段) __GFP_COLD 标志所标识的区本地每 CPU 高速缓存需要补充，执行如下子步骤：
a. 通过反复调用 __rmqueue() 从伙伴系统中分配 batch 个单一页框。
b. 将已分配页框的描述符插入高速缓存链表中。
c. count += 实际被分配页框的个数。
- if(count > 0) 函数从高速缓存链表中获得第一个页框，count -= 1，跳到第 5 步。
- 内存请求还没有被满足，或因为请求跨越了几个连续页框，或者是因为被选中的页框高速缓存为空。调用 __rmqueue() 从伙伴系统中分配所请求的页框。
- 如果内存请求得到满足，初始化第一个页框的页描述符：清除一些标志，private = 0，页框引用计数器 += 1。如果 gfp_flags 中的 __GPF_ZERO 标志被置位，则函数将被分配的内存区域填充 0。
- 返回第一个页框的页描述符地址，如果内存分配请求失败则返回 NULL。
释放页框到每 CPU 页框高速缓存
内核使用 free_hot_page() 和 free_cold_page() 释放单个页框到每 CPU 页框高速缓存，这两个函数都是 free_hot_cold_page() 的简易封装，接收的参数为：将要释放的页框的描述符地址 page 和 cold 标志。
free_hot_cold_page() 执行如下操作：
- 从 page->flags 字段获取包含该页框的内存区描述符地址。
- 获取由 cold 标志选择的内存区高速缓存的 per_cpu_pages 描述符的地址。
- 如果 count >= high，调用 free_pages_bulk() 清空高速缓存，将区描述符、将被释放的页框个数（batch 字段）、高速缓存链表的地址及数字 0（0 到 order 个页框）传递
给该函数。free_pages_bulk() 反复调用 __free_pages_bulk() 释放指定数量的（从高速缓存链表获得的）页框到内存区的伙伴系统中。
- 释放的页框添加到高速缓存链表上，count++。
Linux 2.6 内核，没有页框被释放到冷高速缓存。
区分配器
区分配器是内核页框分配器的前端，它必须分配一个包含足够多空闲页框的内存区来满足内存请求。区分配器必须满足如下目标：
- 保护保留的页框池。
- 当内存不足且允许阻塞当前进程时，触发页框回收算法；一旦某些页框被释放，区分配器将再次尝试分配。
- 尽可能保护小而珍贵的 ZONE_DMA 区。
对一组连续页框的请求实质上是通过执行 alloc_pages 宏来处理的。接着，该宏又调用 __alloc_pages()，该函数是区分配器的核心，接收如下 3 个参数：
- gfp_mask，在内存分配请求中指定的标志。
- order，将要分配的一组连续页框数量的对数。
- zonelist，指向 zonelist 数据结构的指针，按优先次序描述了适于内存分配的区。
__alloc_pages() 扫描包含在 zonelist 数据结构中的每个区：
2
3
4
5
6
7
8
9
10
11
2{
3 if(zone_watermark_ok(z, order, ...)) // 将当前区的空闲页框个数与一个阈值比较
4 {
5 page = buffered_rmqueue(z, order, gfp_mask); // 返回第一个被分配的页框的页描述符
6 if(page)
7 return page;
8 }
9}
10
11
zone_watermark_ok() 接收几个参数，它们觉得区中空闲页框个数的阈值 min。如果满足如下两个条件返回 1：
- 区中至少还有 min 个空闲页框，不包含为内存不足保留的页框（区描述符的 lowmem_reserve 字段）。
- 在 order 至少为 k 的块中起码还有 min/$2^k$ 个空闲页框。
阈值 min 由 zone_watermark_ok() 确定：
- 作为参数的 base 值可以是 pages_min、pages_low 和 pages_high 中的任意一个。
- 如果作为参数的 gfp_high 标志被置位，那么 base 值被 2 除。通常，当 gfp_mask 中的 __GFP_WAIT 标志被置位（能从高端内存中分配页框），则该标志为 1。
- 如果作为参数的 can_try_harder 标志被置位，则阈值将会再减少四分之一。当 gfp_mask 中的 __GFP_WAIT 标志被置位，或者如果当前进程是一个实时进程并在进程上下文中已经完成了内存分配，则 can_try_harder 标志等于 1。
__alloc_pages() 本质上执行如下步骤：
- 对区第一次扫描。第一次扫描中，将阈值 min 被设为 z->pages_low，z 指向正在被分析的区描述符（参数 can_try_harder 和 gfp_high 被设为 0）。
- 如果函数在上一步没有终止，那么没有剩下多少空闲内存：唤醒 kswapd 内核线程来异步地开始回收页框。
- 对区第二次扫描，将 z->pages_min 作为阈值 base 传递。实际阈值由 can_try_harder 和 gfp_high 标志决定。
- 如果函数在上一步没有终止，那么系统内存不足。如果产生内存分配请求的内核控制路径不是一个中断处理程序或一个可延迟函数，并且它试图回收页框，那么执行对区的第三次扫描，试图分配页框并忽略内存不足的阈值，即不调用 zone_watermark_ok()。只有这种情况下才允许内核控制路径耗用为内存不足预留的页。如果没有任何区包含足够的页，返回 NULL。
- 正在调用的内核控制路径并没有试图回收内存。如果 gfp_mask 的 __GFP_WAIT 标志没有被置位，返回 NULL，在这种情况下，需要阻塞当前进程。
- 当前进程可被阻塞，调用 cond_resched() 检查是否有其它的进程需要 CPU。
- 设置 current 的 PF_MEMALLOC 标志来表示进程已经准备好执行内存回收。
- 将一个指向 reclaim_state 数据结构的指针存入 current->reclaim_state，其字段 reclaimed_slab 被初始化为 0.
- try_to_free_pages() 试图回收一些页框，可能会阻塞当前进程。一旦函数返回，__alloc_pages() 就重设 current 的 PF_MEMALLOC 标志并再次调用 cond_resched()。
- 如果上一步已经释放了一些页框，在执行与第 3 步相同的区扫描。如果内存分配请求不能被满足，函数决定是否对区继续扫描：如果 __GFP_NORETRY 标志被清除，且内存分配请求跨越了多达 8 个页框或 __GFP_REPEAT 和 __GFP_NOFAIL 标志其中之一被置位，就调用 blk_congestion_wait() 使进程休眠一会，跳到第 6 步。否则，返回 NULL。
- 如果第 9 步没有释放任何页框，意味着空闲页框已经少到了危险的地步，并且不可能回收任何页框。如果允许内核控制路径执行依赖于文件系统的操作来杀死一个进程，且 __GFP_NORETRY 标志为 0，那么执行如下子步骤：
a. 使用等于 z->pages_high 的阈值再一次是扫描区。
b. out_of_memory() 杀死一个进程以释放一些内存。
c. 跳回第 1 步。
释放一组页框
释放页框的所有内核宏和函数都依赖于 __free_pages() 函数，它接收 2 个参数：
- 将要释放的第一个页框的页描述符的地址 page
- 将要释放的一组连续页框的数量的对数 order
执行如下步骤：
- 检查第一个页框是否真正属于动态内存（PG_reserved 标志被清 0）；如果不是，则终止。
- page->count–，if(page->count >= 0) 终止。
- if(order == 0) free_hot_page() 释放页框到适当区的每 CPU 热高速缓存。
- if(order > 0) 将页框加入到本地链表，free_pages_bulk() 释放页框到适当区的伙伴系统。
内存区管理
伙伴系统算法采用页框作为基本内存区，适用于对大块内存的请求，但不适用于处理对小内存区的请求。
一种典型的解决方法是提供按几何分布的内存区大小，即内存区大小取决于 2 的幂而不取决于所存放的数据大小。
为此，内核建立了 13 个按几何分布的空闲内存区链表，大小从 32 到 131072 字节。
用一个动态链表来记录每个页框所包含的空闲内存。
slab 分配器
算法基于下列前提：
- 所存放数据的类型可以影响内存区的分配方式。slab 分配器将内存区看作对象。为避免重复初始化，slab 分配器不丢弃已分配对象，而是释放后保存在内存中。
- 内核函数倾向于反复请求同一类型的内存区。slab 分配器将反复被请求的页框保存在高速缓存中并很快重新使用它们。
- 对内存区的请求可根据它们发生的频率分类。
- 引入的对象大小不是几何分布时，可借助处理器硬件高速缓存得到较好的性能。
- 硬件高速缓存的高性能是尽可能限制对伙伴系统分配器调用的另一个理由。
slab 分配器将对象分组放进高速缓存。每个高速缓存都是同种类型对象的一种“储备”。
包含高速缓存的主内存区被划分为多个 slab，每个 slab 由多个连续的页框组成，页框中包含已分配对象和空闲对象。
高速缓存描述符
每个高速缓存都由 kmem_cache_t 类型的数据结构描述。
slab 描述符
slab 描述符存放在两个可能的地方：
- 外部 slab 描述符，存放在 slab 外部，位于 cache_sizes 指向的一个不适合 ISA DMA 的普通高速缓存种。
- 内部 slab 描述符，存放在 slab 内部，位于分配给 slab 的第一个页框的起始位置。
当对象小于 512MB，或内存碎片在 slab 内部为 slab 描述符留下足够空间时，slab 分配器选用第二种方案。
如果 slab 描述符存放在 slab 外部，那么高速缓存描述符的 flags 字段中的 CFLAGS_OFF_SLAB 标志被置 1，否则被置 0。
普通和专用高速缓存
普通高速缓存只用于 slab 分配器。
专用高速缓存由内核的其余部分使用。
普通高速缓存是：
- 第一个高速缓存是 kmem_cache，包含由内核使用的其余高速缓存的高速缓存描述符，该高速缓存描述符包含于 cache_cache 变量。
- 另外一些高速缓存包含用作普通用途的用途区。
kmem_cache_init() 和 kmem_cache_sizes_init() 建立普通高速缓存。
kmem_cache_create() 创建专用高速缓存。
- 首先根据参数确定处理新高速缓存的最佳方法
- 然后从 cache_cache 普通高速缓存中为新高速缓存分配一个高速缓存描述符，并插入到 cache_chain 链表。
kmem_cache_destroy() 撤销一个高速缓存并将它从 cache_chain 链表上删除，主要用于模块中。
为避免浪费内存空间，内核必须在撤销高速缓存本身之前就撤销所有的 slab。
kmem_cache_shrink() 通过反复调用 slab_destroy() 撤销高速缓存种所有的 slab。
所有普通和专用高速缓存的名字都可以在运行期间通过读取 /proc/slabinfo 文件得到。
该文件也指明高速缓存中空闲对象的个数和已分配对象的个数。
slab 分配器与分区页框分配器的接口
slab 分配器创建新的 slab 时，它调用 kmem_getpages() 依靠分区页框分配器来获得一组连续的空闲页框。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2// flags：说明如何请求页框。与 cachep 的 gfpflags 字段的专用高速缓存分配标志相结合
3void *kem_getpages(kmem_cache_t *cachep, int flags)
4{
5 struct page *page;
6 int i;
7
8 flags |= cachep->gfpflags;
9 page = alloc_pages(flags, cachep->gfporder); // 内存分配请求的大小由 cachep->gfporder 指定
10 if(!page)
11 return NULL;
12 i = (1 << cache->gfporder);
13 if(cachep->flags & SLAB_RECLAIM_ACCOUNT) // 如果已经创建了 slab 高速缓存且 SLAB_RECLAIM_ACCOUNT 标志置位
14 atomic_add(i, &slab_reclaim_pages); // slab_reclaim_pages 被适当增加
15 while(i--)
16 SetPageSlab(page++); // 将所分配页框的页描述符中的 PG_slab 标志置位
17 return page_address(page);
18}
19
20
kmem_freepages() 释放分配给 slab 的页框
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2{
3 unsigned long i = (1 << cachep->gfporder);
4 strucct page *page = virt_to_page(addr); // 从线性地址 addr 开始释放页框
5
6 if(current->recalim_state) // 如果当前进程正在执行内存回收
7 current->reclaim_state->reclaimed_slab += i; // reclaimed_slab 被增加，于是刚被释放的页就能通过页框回收算法被记录下来
8 while(i--)
9 ClearPageSlab(page++);
10 free_pages((unsigned long) addr, cachep->gfporder);
11 if(cachep->flags & SLAB_RECLAIM_ACCOUNT) // 如果 SLAB_RECLAIM_ACCOUNT 标志置位
12 atomic_sub(1 << cachep->gfporder, &slab_reclaim_pages); // slab_reclaim_pages 被适当减少
13}
14
15
给高速缓存分配 slab
以下两个条件都为真时，才给高速缓存分配 slab：
- 已发出一个分配新对象的请求。
- 高速缓存中无空闲对象。
slab 分配器调用 cache_grow() 给高速缓存分配一个新的 slab。
cache_grow() 调用 kmem_getpages() 从分区页框分配器获得一组页框来存放一个单独的 slab，然后调用 alloc_slabmgmt() 获得一个新的 slab 描述符。
如果高速缓存描述符的 CFLAGS_OFF_SLAB 标志置位，则从其 slabp_cache 字段指向的普通高速缓存中分配该新的 slab 描述符，否则，从 slab 的第一个页框中分配该 slab 描述符。
给定一个页框，内核必须确定它是否被 slab 分配器使用，如果是，就迅速得到相应高速缓存和 slab 描述符的地址。
因此，cache_grow() 扫描分配给新 slab 的页框的所有页描述符，并将高速缓存描述符和 slab 描述符的地址分别赋给页描述符中 lru 字段的 next 字段和 prev 字段。
接着，cahce_grow() 调用 cache_init_objs()，将构造方式应用到新 slab 包含的所有对象上。
最后，cache_grow() 调用 list_add_tail() 将新的 slab 描述符 *slabp 添加到高速缓存描述符 *cachep 的全空 slab 链表的末端，并更新高速缓存中的空闲对象计数器：
2
3
4
2cachep->lists->free_objects += cachep->num;
3
4
从高度缓存中释放 slab
以下两种条件下会撤销 slab
- slab 高速缓存中有太多的空闲对象。
- 被周期性调用的定时器函数确定是否有完全未使用的 slab 能被释放。
slab_destroy() 撤销一个 slab，并释放相应的页框到分区页框分配器：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2{
3 if(cachep->dtor) // 如果高速缓存为它的对象提供了析构方法
4 {
5 int i;
6 for(i=0; i<cachep->num; i++)
7 {
8 void *objp = slabp->s_mem + cachep->objsize * i;
9 (cachep->dtor)(objp, cachep, 0); // 使用析构方法释放 slab 中的对象
10 }
11 }
12 kmem_freepages(cachep, slapb->s_mem - slabp->colouroff); // 把 slab 使用的所有连续页框返回给伙伴系统
13 if(cachep->flags & CFLAGS_OFF_SLAB) // 如果 slab 描述符存放在 slab 的外面
14 kmem_cache_free(cachep->slabp_cache, slabp); // 从 slab 描述符的高速缓存释放这个 slab 描述符
15}
16
17
对象描述符
每个对象都有类型为 kmem_bufctl_t 的一个描述符。
对象描述符存放在一个数组中，位于相应的 slab 描述符之后。
因此，与 slab 描述符本身类似，slab 的对象描述符页可以用两种可能的方式存放：
- 外部对象描述符，存放在 slab 的外面，位于高速缓存描述符的 slabp_cache 字段的一个普通高速缓存中。内存区的大小取决于 slab 中的对象数。
- 内部对象描述符，存放在 slab 内部，位于描述符所描述的对象前。
对象描述符是一个无符号整数，只有对象空闲时才有意义。
它包含下一个空闲对象在 slab 中的下标，因此实现了 slab 内部空闲对象的一个简单链表。
空闲对象链表中的最后一个元素的对象描述符用值 BUFCTL_END(0xffff) 标记。
对齐内存中的对象
slab 分配器所管理的对象可以在内存中对齐，即存放它们的内存单元的起始物理地址是一个对齐因子的倍数，通常为 2 的倍数。
slab 分配器所允许的最大对齐因子是 4096，即页框大小，意味着通过访问对象的物理地址或线性地址就可以访问对齐对象。
通常，如果内存单元的物理地址大小是字大小对齐的，则微机对内存单元的存器会非常快。
因此，缺省情况下，kmem_cache_create() 根据 BTES_PER_WORD 宏所指定的字大小来对齐对象。
当创建一个新的 slab 高速缓存时，可让其中的对象在第一级硬件高速缓存中对齐。
为此，需设置 SLAB_HWCACHE_ALIGN 高速缓存描述符标志。
kmem_cache_create() 按如下方式处理请求：
- 如果对象大小大于高速缓存行的一半，就在 RAM 中根据 L1_CACHE_BYTES 的倍数（行的开始）对齐对象。
- 否则，对象的大小为 L1_CACHE_BYTES 的因子取整，可避免小对象跨越两个高速缓存行。
slab 着色
同一硬件高速缓存行可以映射 RAM 中很多不同的块。
相同大小的对象倾向于存放在高速缓存内相同的偏移量处。
在不同的 slab 内具有相同偏移量的对象最终可能映射在同一高速缓存行中。
高速缓存的硬件可能因此花费内存周期，在同一高速缓存行于 RAM 内存单元间来回传输两个对象，而其他的高速缓存行却未被充分使用。
slab 着色可避免以上情况：将颜色（不同的随机数）分配给 slab。
slab 内放置对象的方式有多种，取决于以下变量：
- num，可在 slab 中存放对象的个数
- osize，对象的大小，包括对齐的字节。
- dsize，slab 描述符的大小加上所有对象描述符的大小，等于硬件高速缓存行大小的最小倍数。如果 slab 描述符和对象描述符都在 slab 外部，该值为 0.
- free，slab 内未用字节数。
一个 slab 中的总字节长度 = （num * osize) + dsize + free
slab 分配器利用空闲未用的字节 free 对 slab 着色。
“着色”是用来再细分 slab，并允许内存分配器把对象展开在不同的线性地址中，以便内核从微处理器的硬件高速缓存中获得更好性能。
具有不同颜色的 slab 把 slab 的第一个对象存放在不同的内存单元，同时满足对齐约束。
可用颜色的个数是 $free / aln$ ，存放在高速缓存描述符的 colour 字段。
如果用颜色 col 对一个 slab 着色，第一个对象的偏移量 = $col * aln + dsize$ 字节。
将当前颜色存放在高速缓存描述符的 colour_next 字段后，颜色就可以在给定对象类型的 slab 之间均匀分布。
cache_grow() 把 colour_next 表示的颜色赋给一个新的 slab，并递增该字段。
colour_next 值变为 colour 后，从 0 重新开始。
此外，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 字段。
本地高速缓存大小取决于存放再 slabg 高速缓存中对象的大小，范围从 1（相对于非常大的对象）到 120（相对于小对象）。
batchcount 字段的初始值，即从一个本地高速缓存的块中添加或删除对象的个数，被初始化为本地高速缓存大小的一半。
多处理器中，小对象使用的 slab 高速缓存同样包含一个附加的本地高速缓存，其地址存放在高速缓存描述符的 lists.shared 字段。
共享的本地高速缓存被所有 CPU 共享，它使得将空闲对象从一个本地高速缓存移动到另一个高速缓存更容易。
分配 slab 对象
kmem_cache_alloc() 可获得新对象。
参数：
-
cachep，指向高速缓存描述符，新空闲对象必须从该高速缓存描述符获得。
-
flag，传递给分区页框分配器函数的标志，该高速缓存的所有 slab 应当是满的。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2{
3 unsigned long save_flags;
4 void *objp;
5 struct array_cache *ac;
6
7 local_irq_save(save_flags);
8 ac = cache_p->array[smp_processor_id()]; // 试图从本地高速缓存获得一个空闲对象
9 if(ac->avail) // 如果有空闲对象，avail 包含指向最后释放的对象的项在本地高速缓存中的下标
10 {
11 ac->touched = 1;
12
13 // 获得空闲对象的地址并递减 ac->avail。本地高速缓存数组正好存放在 ac 描述符后面
14 objp = ((void **)(ac + 1))[--ac->avail];
15 }
16 else
17 objp = cache_alloc_refill(cachep, flags); // 重新填充本地高速缓存并获得一个空闲对象
18 local_irq_restore(save_flags);
19 return objp;
20}
21
22
cache_alloc_refill() 本质上执行如下步骤：
- 将本地高速缓存描述符地址存放在 ac 局部变量中：
ac = cachep->array[smp_processor_id()];
- 获得 cachep->spinlock。
- 如果 slab 高速缓存包含共享本地高速缓存，且该共享本地高速缓存包含一些空闲对象，就通过从共享本地高速缓存中上移 ac->batchcount 个指针来重新填充 CPU 的本地高速缓存，然后跳到第 6 步。
- 试图填充本地高速缓存，填充值为高速缓存的 slab 中包含的 ac->batchcount 个空闲对象的指针：
a. 查看高速缓存描述符的 slabs_partial 和 slabs_free 链表，并获得 slab 描述符的地址 slabp，相应的 slab 或者部分被填充，或者为空。如果不存在这样的描述符，转第 5 步。
b. 对于 slab 的每个空闲对象，增加 slab 描述符的 inuse 字段，将对象的地址插入本地高速缓存，并更新 free 字段使其存放 slab 中下一个空闲对象的下标：
slabp->inuse++;
((void**)(ac+1))[ac->avail++] = slabp->s_mem + slabp->free * cachep->obj_size;
slabp->free = ((kmem_bufctl_t*)(slabp+1))[slabp->free];
c. 如果必要，将 清空的 slab 插入到适当的链表上，slab_full 链表或 slab_parital 链表。
- 被加到本地高速缓存上的指针个数被存放在 ac->avail 字段：函数递减同样数量的 kmem_list3 结构的 free_objects 字段，以说明这些对象不再空闲。
- 释放 cachep->spinlock。
- if(ac->avail > 0) 说明填充完了高速缓存，ac->touched = 1，并返回最后插入到本地高速缓存的空闲对象指针：
return ((void **)(ac+1))[–ac->avail];
- 否则，没有发生任何高速缓存再填充情况：调用 cache_grow() 获得一个新 slab，从而获得了新的空闲对象。
- 如果 cache_grow() 失败，返回 NULL；否则，返回第 1 步重复该过程。
释放 slab 对象
kmem_cache_free() 释放一个曾经由 slab 分配器分配给某个内核函数的对象。
参数：
-
cachep，高速缓存描述符的地址。
-
objp，将要被释放对象的地址。
2
3
4
5
6
7
8
9
10
11
12
13
14
2{
3 unsigned long flags;
4 struct array_cache *ac;
5
6 local_irq_save(flags);
7 ac = cachep->array[smp_processor_id()];
8 if(ac->avail == ac->limit) // 如果本地高速缓存没有空间留给一个空闲对象的额外指针
9 cache_flusharray(cachep, ac)); // 清空本地高速缓存
10 ((void**)(ac+1)[ac->avail++] = objp; // 将指针加到本地高速缓存
11 local_irq_restore(flags);
12}
13
14
cache_flusharray() 执行如下操作：
- 获得 cachep->spinlock 自旋锁。
- 如果 slab 高速缓存包含一个共享本地高速缓存，并且如果该共享本地高速缓存还没有满，就通过从 CPU 本地高速缓存上移 ac->batchcount 个指针来重新填充共享本地高速缓存。
- free_block() 将包含在本地高速缓存中的 ac->batchcount 个对象归还给 slab 分配器。对于在地址 objp 处的每个对象，执行如下步骤：
a. 增加高速缓存描述符的 lists.freeobjects 字段。
b. 确定包含对象的 slab 描述符的地址：slabp = (struct slab *)(virt_to_page(objp)->lru.prev);
c. 从它的 slab 高速缓存链表上删除 slab 描述符。
d. 计算 slab 内对象的下标：objnr = （objp – slabp->s_mem) / cachep->objsize;
e. 将 slabp->free 的当前值存放在对象描述符中，并将对象的下标放入 slabp->free：
((kmem_bufctl_t *)(slabp_1))[objnr] = slabp->free;
slabp->free = objnr;
f. slabp->inuse–;
g. if(slabp->inuse == 0 && cachep->lists.free_objects > cachep->free->limit)，将 slab 的页框释放到分区页框分配器：
cachep->lists.free_objects -= cachep->num;
slab_destroy(cachep, slabp);
存放在 cachep->free_limit 的值通常等于 cachep->num + (1+N) * cachep->batchcount，N 代表系统中 CPU 的个数。
h. 否则，if(slab->inuse == 0) 但整个 slab 高速缓存中空闲对象的个数小于 cachep->free_limit，函数就将 slab 描述符插入到 cachep->lists.slabs_free 链表。
i. if(slab->inuse > 0) slab 被部分填充，则函数将 slab 描述符插入到 cachep->lists.slabs_parital 链表。
- 释放 cachep->spinlock 自旋锁。
- 本地高速缓存描述符的 avail 字段 -= 被移到共享本地高速缓存或被释放到 slab 分配器的对象的个数
- 将本地高速缓存的所有合法指针移动到本地高速缓存数组的起始处。这一步是必须的，因为第一个对象指针已从本地高速缓存删除，因此剩下的指针必须上移。
通用对象
如果对存储区的请求不频繁，就用一组普通高速缓存来处理，普通高速缓存中的对象具有几何分布大小，范围为 32~131072 字节。
kmalloc() 可得到通用对象。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2{
3 struct cache_sizes *csizep = malloc_sizes; // malloc_sizes 为 2 的幂次方
4 kmem_cache_t *cachep;
5 for(; csizep->cs_size; csizep++)
6 {
7 if(size > csizep->cs_size)
8 continue;
9 else
10 cachep = csizep->cs_cachep;
11
12 // 分配对象，参数或者为适用于 ISA DMA 页框的高速缓存描述符，
13 // 或者为适用于“常规”页框的高速缓存描述符
14 // 取决于调用者是否指定了 __GFP_DMA 标志
15 return kmem_cache_alloc(cachep, flags);
16 }
17 return NULL;
18}
19
20
kfree() 释放 kmalloc() 获得的对象
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2{
3 kmem_cache_t *c;
4 unsigned long flags;
5 if(!objp)
6 return;
7 local_irq_save(flags);
8
9 // 通过读取内存区所在的第一个页框描述符的 lru.next 字段，
10 // 就可确定出合适的高速缓存描述符
11 c = (kmem_cache_t *)(virt_to_page(objp)->lru.next);
12
13 kmem_cache_free(c, (void *)objp); // 释放相应的内存区
14
15 local_irq_restore(flags);
16}
17
18
内存池
一个内存池允许一个内核成分，如块设备子系统，仅在内存不足的紧急情况下分配一些动态内存。
内存池与“保留的页框池”不同，后者的页框只能满足中断处理程程序或内部临界区发出的原子内存分配请求，而前者动态内存的储备。
一个内存池常常叠加在 slab 分配器之上—它被用来保持 slab 对象的储备。
但一般而言，内存池能被用来分配任何一种类型的动态内存，从整个页框到使用 kmalloc() 分配的小内存区。
内存池由 mempool_t 对象描述。
- min_nr 存放内存池中元素的初始个数。
- curr_nr <= min_nr，存放了内存池中当前包含的内存元素个数。
- 内存池元素自身被一个指针数组引用，指针数组的地址存放在 elements 字段中。
- alloc、free 方法与基本的内存分配器交互，分别获得和释放一个内存元素。
- 内存元素是 slab 对象时，pool_data 存放 slab 高速缓存描述符的地址。
mempool_create() 创建一个新的内存池，接收的参数
- 内存元素的个数 min_nr
- 实现 alloc 和 free 方法的函数的地址
- 赋给 pool_data 的任意值
mempool_create() 分别为 mempool_t 对象和指向内存元素的指针数组分配内存，然后反复调用 alloc 方法得到 min_nr 个内存元素。
mempool_destroy() 释放池中所有内存元素，然后释放元素数组和 mempool_t 对象自己。
mempool_alloc() 从内存池分配一个元素，将 mempool_t 的地址和内存分配标志传递给它。
函数本质上依据参数所指定的内存分配标志，试图通过 alloc 方法从基本内存分配器分配一个内存元素。
如果分配成功，返回获得的内存元素而不涉及内存池。
否则，如果分配失败，就从内存池获得内存元素。
内存不足时，过多的分配会用尽内存池，如果 __GFP_WAIT 标志没有置位，则 mempool_alloc() 阻塞当前进程直到有一个内存元素被释放到内存池中。
mempool_free() 释放一个元素到内存池。如果内存池未满（curr_min < min_nur），函数将元素加到内存池中，否则，调用 free 方法释放到基本内存分配器。
非连续内存区管理
如果对内存区的请求不是很频繁，那么，通过连续的线性地址访问非连续的页框就有意义。
优点是避免了外碎片，缺点是必须打乱内核页表。
非连续内存区大小必须是 4096 的倍数。
Linux 使用非连续内存区：为或的交换区分配数据结构，为模块分配空间，为某些 I/O 驱动程序分配缓冲。
非连续内存区的线性地址
从 PAGE_OFFSET（通常为 0xc0000000，第 4 个 GB 的起始地址） 开始可查找线性地址的一个空闲区。
图 8-7 显示了如何使用第 4 个 GB 的线性地址。
- 内存的开始部分包含对前 896MB RAM 进行映射的线性地址；直接映射的物理内存末尾所对应的线性存储于 high_memory 变量。
- 内存区的结尾部分包含固定映射的线性地址。
- 从 PKMAP_BASE 开始，可查找用于高端内存页框的永久内核映射的线性地址。
- 其余的线性地址可用于非连续内存区。在物理内存映射的末尾与第一个内存区之间插入一个大小为 8MB（宏 VMALLOC_OFFSET）的安全区，可捕获对内存的越界访问。出于同样理由，插入其他 4KB 大小的安全区来隔离非连续的内存区。
非连续内存区区的描述符
每个非连续内存区都对应一个类型为 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
执行如下步骤：
- kmalloc() 为 vm_struct 类型的新描述符获得一个内存区。
- 为写得到 vmlist_lock 锁，扫描类型为 vm_struct 的描述符链表来查找线性地址一个空闲区域，至少覆盖 size + 4096 个地址（4096 是内存区之间的安全区间大小）。
- 如果存在这样一个区间，初始化描述符的字段，释放 vmlist_lock 锁，并返回该给连续内存区的起始地址。
- 否则，get_vm_area() 释放先前得到的描述符，释放 vmlist_lock，返回 NULL。
分配非连续内存区
vmalloc() 给内核分配一个非连续内存区，返回新内存区的起始地址。
参数 size 表示所请求内存区的大小。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
2{
3 struct vm_struct *area;
4 struct page **pages;
5 unsigned int array_size, i;
6 size = (size + PAGE_SIZE - 1) & PAGE_MASK; // 4096（页框大小）的整数倍
7
8 // 创建一个新的描述符，并返回该内存区的线性地址，flags 字段倍初始化为 VM_ALLOC
9 // 意味着，通过 vmalloc()，非连续页框将被映射到一个线性地址区间
10 area = get_vm_area(size, VM_ALLOC);
11 if(!area)
12 return NULL;
13
14 area->nr_pages = size >> PAGE_SHIFT;
15 area_size = (area->nr_pages * sizeof(struct page *));
16
17 // 请求一组连续的页框
18 // 这组连续页框足够包含一个页描述符指针数组
19 area->pages = pages = kmalloc(array_size, GFP_KERNEL);
20
21 if(!area_pages)
22 {
23 remove_vm_area(area->addr);
24 kfree(area);
25 return NULL;
26 }
27 memset(area->pages, 0, array_size); // 将所有指针设置为 NULL
28 for(i=0; i<area->nr_pages; i++)
29 {
30 // 为区间中的每个页分配一个页框
31 // 并把对应页描述符的地址存放在 area->pages 数组
32 // 必须使用 area->pages 数组，因为页框可能属于 ZONE_HIGHMEM 内存管理区，不必映射到一个线性地址上
33 area->pages[i] = alloc_page(GFP_KERNEL | __GFP_HIGHMEM);
34
35 if(!area->pages[i])
36 {
37 area->nr_pages = i;
38 fail: vfree(area->addr);
39 return NULL;
40 }
41 }
42
43 // 修改内核使用的页表项，以表明分配给非连续内存区的每个页框现在对应着一个线性地址
44 // 该线性递增被包含在 vmalloc() 产生的非连续线性地址区间中
45 if(map_vm_area(area, __pgprot(0x63), &pages))
46 goto fail;
47
48 return area->addr;
49}
50
51
map_vm_area() 使用以下 3 个参数：
- area，指向内存区的 vm_struct 描述符的指针。
- prot，已分配页框的保护位。总是被设置为 0x63，对应着 Present、Accessed、Read/Write 及 Dirty。
- pages，指向一个指针数组的变量的地址，该指针数组的指针指向页描述符。
首先把内存区的开始和末尾的线性地址分别分配给局部变量 address 和 end：
2
3
4
2end = address + (area->size - PAGE_SIZE); // area->size 存放内存区的实际地址加上 4KB 内存之间的安全区间
3
4
然后使用 pgd_offset_k 宏来得到在主内核页全局目录中的目录项，该项对应于内存区起始线性地址，然后获得内核页表自旋锁：
2
3
4
2spin_lock(&init_mm.page_table_lock);
3
4
然后，函数执行下列循环，建立所有指向非连续内存区的所有页表项
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
2for(i = pgd_index(address); i < pgd_index(end - 1); i++)
3{
4 // 为新内存区创建一个页上级目录
5 // 并将其物理地址写入内核页全局目录的合适表项
6 // 然后调用 alloc_area_pud() 为新的页上级目录分配所有相关的页表
7 pud_t *pud = pud_alloc(&init_mm, pgd, address);
8
9 ret = -ENOMEM;
10 if(!pud)
11 break;
12
13 // 将常量 2^30（PAE 未激活时，为 2^22） 与 address 的当前值相加
14 // 2^30 就是一个页上级目录所跨越的线性地址范围的大小
15 next = (address + PGDIR_SIZE) & PGDIR_MASK；
16
17 if(nex < address || next > end)
18 next = end;
19 if(map_area_pud(pud, address, next, prot, pages))
20 break;
21 address = next;
22 pgd++； // 增加执行页全局目录的指针 pgd
23 ret = 0;
24 spin_unlock(&init_mm.page_table_lock);
25 flush_cache_vmp((unsigned long)area->addr, end);
26 return ret;
27}
28
29
map_area_pud 为页上级目录所指向的所有页表执行一个类似的循环：
2
3
4
5
6
7
8
9
10
11
12
2{
3 pmd_t *pmd = pmd_alloc(&init_mm, pud, address);
4 if(!pmd)
5 return -ENOMEM;
6 if(map_area_pmd(pmd, address, end-address, prot, pages))
7 return -ENOMEM;
8 address = (address + PUD_SIZE) & PUD_MASK;
9 pud++;
10}while(address < end);
11
12
map_area_pmd() 为页中间目录所指向的所有页表执行一个类似的循环：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2{
3 // 分配一个新的页表，并跟新页中间目录中相应的目录项
4 pte_t *pte = pte_alloc_kernel(&init_mm, pmd, address);
5 if(!pte)
6 return -ENOMEM;
7
8 // 为页表中相应的表项分配所有的页框
9 if(map_area_pte(pte, address, end - address, prot, pages))
10 return -ENOMEM;
11
12 // 增加 2^22，2^22 是一个页表所跨越的线性地址区间的大小
13 address = (address + PMD_SIZE) & PMD_MASK;
14
15 pmd++;
16}while(address < end);
17
18
map_area_pte() 主循环：
2
3
4
5
6
7
8
9
10
11
12
13
14
2{
3 // 将被映射的页框的页描述符地址 page 是从地址 pages 处的变量指向的数组项读得
4 struct page *page = **pages;
5
6 // 将新页框的物理地址写进页表
7 set_pte(pte, mk_pte(page, prot));
8
9 address += PAGE_SIZE; // 将常量 4096（一个页框的长度）加到 address
10 pte++;
11 (*pages)++;
12}while(address < end);
13
14
map_vm_area() 不触及当前进程的页表。因此，当内核态的进程访问非连续内存区时，缺页发生，因为该内存区所对应的进程页表中的表项为空。
缺页处理程序会检查该缺页线性地址是否在主内核页表中，如果在，就把它的值拷贝到相应的进程页表项，并恢复进程的正常执行。
vmalloc_32() 与 vmalloc() 类似，分配非连续内存区，但只从 ZONE_NORMAL 和 ZONE_DMA 内存管理区中分配页框。
vmap() 映射非连续内存区中已分配的页框：
- 接收一组指向页描述符的指针作为参数
- 调用 get_vm_area() 得到一个新的 vm_struct 描述符
- 调用 map_vm_area() 映射页框
- 与 vmalloc() 相似，但不分配页框
释放非连续内存区
vfree() 释放 vmalloc() 或 vmalloc_32() 创建的非连续内存区。
vunmap() 释放 vmap() 创建的内存区。
两个函数的参数都为：将要释放的内存区的起始线性地址 address，均依赖于 __vunmap()。
__vunmap() 接收两个参数：
- 将要释放的内存区的起始地址 addr
- 标志 dealllocate_pages，如果被映射到内存区的页框应答被释放到分区页框分配中（调用 vfree()），该标志被置位，否则被清除（vunmap() 被调用）。
执行以下操作：
- remove_vm_area() 得到 vm_struct 描述符的地址 area，并清除非连续内存区中的线性地址对电影的内核的页表项。
- 如果 deallocate_pates() 被置位，扫描指向页描述符的 area->pages 指针数组，对每一个元素调用 __free_page() 释放页框到分区页框分配器。执行 kfree(area->pages) 释放数组本身。
- 调用 kfree(area) 释放 vm_struct 描述符。
remove_vm_area() 执行如下循环：
2
3
4
5
6
7
8
9
10
11
12
13
14
2for(p = &vmlist; tmp = *p; p = &tmp->next)
3{
4 if(tmp->addr == addr)
5 {
6 unmap_vm_area(tmp); // 释放内存区本身
7 *p = tmp->next;
8 break;
9 }
10}
11write_unlock(&vmlist_lock);
12return tmp;
13
14
unmap_vm_area() 参数为执行内存区的 vm_struct 描述符的指针 area，执行 map_vm_area() 的逆操作：
2
3
4
5
6
7
8
9
10
11
12
13
14
2end = address + area->size;
3pgd = pgd_offset_k(address);
4for(i = pgd_index(address); i <= pgd_index(end-1); i++)
5{
6 next = (address _ PGDIR_SIZE) & PGDIR_MASK;
7 if(next <= address || next > end)
8 next = end;
9 unmap_area_pud(pgd, address, next - address);
10 address = next;
11 pgd++;
12}
13
14
unmap_area_pud() 执行 map_area_pud 的逆操作：
2
3
4
5
6
7
8
2{
3 unmap_area_pmd(pud, address, end - address);
4 address = (address + PUD_SIZE) & PUD_MASK;
5 pud++;
6}while(address && address < end);
7
8
unmap_area_pmd() 执行 map_area_pmd 的逆操作：
2
3
4
5
6
7
8
2{
3 unmap_area_pte(pmd, address, end - address);
4 address = (address + PMD_SIZE) & PMD_MASK;
5 pmd++;
6}while(address < end);
7
8
unmap_area_pte() 执行 map_area_pte() 的逆操作：
2
3
4
5
6
7
8
9
10
2{
3 pte_t page = ptep_get_and_clear(pte); // 将指向的页表项设为 0
4 address += PAGE_SIZE;
5 pte++;
6 if(!pte_none(page) && !pte_present(page))
7 printk("whee... Swapped out page in kernel page table\n");
8}while(address < end);
9
10
与 vmalloc() 一样，内核修改主内核页全局目录和它的子页表中的相应项，但映射第 4 个 GB 的进程页表的项保持不变。
因为内核永远不会回收扎根于主内核页全局目录中的页上级目录、页中间目录和页表。
