深入理解Linux虚拟内存管理（一）3：https://developer.aliyun.com/article/1597689
4.7 复制到用户空间/从用户空间复制
4.8 2.6中有哪些新特性
线性地址空间基本上保持了与 2.4 版本中相同的内容，几乎没有什么可以容易识别的变更。主要的变化是在用户空间增加一个新的页面以映射到固定的虚拟地址。在 x86 上，该页面位于 0xFFFFF000 处称为 vsyscall 页。该页中的代码提供了从用户空间进入内核空间最理想的方法。一个用户空间的程序现在可以通过调用 0xFFFFF000 来代替传统的 int 0x80 中断进入内核空间。
struct mm_struct 这个结构没有很重大的变化。首先的变化是结构中新增加了一个 free_area_cache 字段，该字段初始化为 TASK_UNMAPPED_BASE。这个字段用于标记第一个空洞在线性地址空间中的位置，以改善搜索的时间开销。在该结构的尾部新增加了少量的字段，这与内核转储有关，但已经超出本书的范围。
struct vm_area_struct 这个结构也没有很重大的变化。主要的区别是 vm_next_share 和 vm_pprev_share 两个字段中的特定链表被称为 shared 的新字段所替换。vm_raend 字段已被彻底地删除，因为文件预读在 2.6 内核中实现起来非常难。预读主要由储存在 struct file→f_ra 中的一个 struct file_ra_state 管理。如何实现预读的许多细节在 mm/readahead.c 文件中有描述。
struct address_space 第一种变化相比之下是较次要的。gfp_mask 字段被 flags 字段取代，该标志字段首部 __GFP_BITS_SHIFT 个位用作 gfp_mask，并且由 mapping_gfp_mask() 函数访问。余下的多个位用于存储异步 I/O 的状态。这两个标志位可能被设置为 AS_EIO，以表明是一个 I/O 错误，或者被设置为 AS_ENOSPC，以表示在异步写期间文件系统空间已耗尽。
该结构增加了较多的东西，它们主要与页面高速缓存和预读有关。由于这些字段十分独特，所以我们将会详细地介绍它们。
page_tree：这个字段是通过索引映射的页面高速缓存所有页面的基树，所有的数据都位于物理磁盘的块上。在 2.4 内核中，搜索页面高速缓存需要遍历整个链表。而在 2.6 内核中，它是一种基树查找，可以减少相当多的搜索时间。这个基树的实现在 lib/radix-tree.c 文件中。
page_lock：这个是保护页树的自旋锁。
io_pages：在写出脏页以及调用 do_writepages() 函数前，这些脏页被添加到这个链表中。正如前面注释所解释的一样，mpage_writepages() 函数在 fs/mpage.c 文件中，被写出的页放在这个链表中，以避免因为锁住一个已经被 I/O 锁住的页面而造成死锁。
dirtied_when：这个字段记录一个索引节点第一次变脏瞬间的时间点。这个字段决定索引节点在super_block→s_dirty 链表上的位置。这样就防止了经常变脏的索引节点仍然逗留在链表的首部而导致在其他一些索引节点上出现不能写出而饿死 (starving) 的情况。
backing_dev_info：这个字段记录预读相关的信息。该结构在 include/linux/backingdev.h 中有声明，而且还有注释来解释这些字段的作用。
private_list：这是一个可用的针对 address_space 的私有链表。如果已经使用了辅助函数 mark_buffer_dirty_inode() 和 sync_mapping_buffers()，则该链表就通过 buffer_head→b_assoc_buffers 字段链接到缓冲区的首部。
private_lock：这是一个可用的针对 address_space 的自旋锁。该锁的使用情况虽然是令人费解的，但是在针对 2.5.17( Iwn.net/2002/0523/a/2.5.17.php3 )版本的冗长变更日志中解释了它的一部分使用情况。它主要保护在这个映射中共享缓冲区的其他映射中的相关信息。该锁虽然不保护 private_list 这个字段，但是它保护该 映射中其他 address_space 共享缓冲区的 private_list 字段。
assoc_mapping：映射 private_list 链表包含的 address_space 中的后援缓冲区。
truncate_count：这是在一个区域由函数 invalidate_mmap_range() 收缩时的一个增量。当发生缺页中断时通过函数 do_no_page() 检查该计数器，以确保在一个页面没有错误时该计数器无效。
struct address_space_operations：大多数关于该结构的变更初看起来，似乎相当简单，但实际上非常練手。以下是作了变更的字段。
writepage; 函数 writepage() 的回调函数已经改变，另外增加了 一个参数 struct writeback_control。这个结构负责记录一些回写信息，如是否阻塞了或者页面分配器对于写操作是否是直接回收的或者 kupdated 的，并且它包含-个备份 backing_dev_info 的句柄以控制预读。
writepages：这个字段在把所有的页面写出之前，将所有的页从 dirty_pages 转移到 io_pages 中。
set_page_dirty：这是一个与 address_space 相关的设置某页为脏的方法。主要是供后援
存储器的 address_space_operations 使用，以及那些与脏页相关联却没有缓冲区的匿名共享页面所使用。
readpages：这个字段用于页面读取，使预读能够得到正确的控制。
bmap：这个字段已经变更为处理磁盘扇区而不是设备的大于 232 个字节的无符号长整型。
invalidatepage：这是一种更名的变化。函数 block_flushpage() 和回调函数 flushpage() 已经被重命名为 block_invalidatepage() 和 invalidatepage() 。
direct I/O：已经改变成用 2.6 版本中新的 I/O 机制。新的机制已经超出了本书的范围。
第5章 引导内存分配器
由于硬件配置多种多样，所以在编译时就静态初始化所有的内核存储结构是不现实的。下一章将讨论到物理页面的分配，即使是确定基本数据结构也需要分配一定的内存空间来完成其自身的初始化过程。但物理页面分配器如何分配内存去完成自身的初始化呢?
为了说明这一点，我们使用一种特殊的分配器 —— 引导内存分配器（boot memory allocator）。它基于大多数分配器的原理，以位图代替原来的空闲块链表结构来表示存储空间 [Tan01]。若位图中某一位为 1，表示该页面已经被分配；否则表示为被占有。该分配机制通过记录上一次分配的页面帧号（PFN）以及结束时的偏移量来实现分配大小小于一页的空间。连续的小的空闲空间将被合并存储在同一页上。
读者也许会问，当系统运行时为何不使用这种分配机制呢? 其中的一个关键原因在于：首次适应分配机制虽然不会受到碎片的严重影响[JW98]，但是它每次都需要通过对内存进行线性搜索来实现分配。若它检查的是位图，其成本将是相当高的。尤其是首次适应算法容易在内存的起始端留下许多小的空闲碎片，在需要分配较大的空间时，检查位图这一过程就显得代价很高 [WJNB95]。
在该分配机制中，存在着两种相似但又不同的 API。一种是如表 5.1 所列的 UMA 结构，另一种是如表 5.2 所列的 NUMA 结构。两者主要区别在于：NUMA API 必须附带对节点的操作，但由于 API 函数的调用者来自于与体系结构相关的层中，所以这不是一个很大的问题。
本章首先描述内存分配机制的结构，该结构用于记录每一个节点的可用物理内存。然后举例阐述如何设定物理内存的界定和每一个管理区的大小。接下来讨论如何使用这些信息初始化引导内存分配机制的结构。在解决了引导内存分配机制不再被使用后，我们开始研究其中的一些分配算法和函数。
5.1 描述引导内存映射
系统内存中的每一个节点都存在一个 bootmem_data 结构。它含有引导内存分配器给节点分配内存时所需的信息，如表示已分配页面的位图以及分配地点等信息。它在 <linux/bootmem.h> 文件中定义如下：
/* * node_bootmem_map is a map pointer - the bits represent all physical * memory pages (including holes) on the node. */ typedef struct bootmem_data { unsigned long node_boot_start; unsigned long node_low_pfn; void *node_bootmem_map; unsigned long last_offset; unsigned long last_pos; } bootmem_data_t;
该结构各个字段如下。
node_boot_start：表示块的起始物理地址。
node_low_pfn：表示块的结束地址，或就是该节点表示的 ZONE_NORMAL 的结束。
node_bootmem_map：以位表示的已分配和空闲页面的位图的地址。
last_offset：最后一次分配所在页面的偏移。如果为 0，则表示该页全部使用。
last_pos：最后一次分配时的页面帧数。使用 last_offset 字段，我们可以检测在内存分配时，是否可以合并上次分配所使用的页，而不用重新分配新页。
5.2 初始化引导内存分配器
每一种体系结构中都提供了一个 setup_arch() 函数，用于获取初始化引导内存分配器时所必须的参数信息。
各种体系结构都有其函数来获取这些信息。在 x86 体系结构中为 setup_memory() ，而在其他体系结构中，如在 MIPS 或 Sparc 中为 bootmem_init()，PPC 中为 do_init_bootmen()。除体系结构不同外各任务本质上是相同的。参数信息如下。
min_low_pfn：系统中可用的最小 PFN。
max_low_pfn：以低端内存区域表示的最大 PFN。
highstart_pfn：高端内存区域的起始 PFN。
highend_pfn：高端内存区域的最后一个 PFN。
max_pfn：表示系统中可用的最大 PFN。
5.3 初始化bootmem_data
一旦 setup_memory() 确定了可用物理页面的界限，系统将从两个引导内存的初始化函数中选择一个，并以待初始化的节点的起始和终止 PFN 作为调用参数。在 UMA 结构中，init_bootmem() 用于初始化 contig_page_data，而在 NUMA，init_bootmem_node() 则初始化一个具体的节点。这两个函数主要通过调用 init_bootmem_core() 来完成实际工作。
内核函数首先要把 pgdat_data_t 插入到 pgdat_list 链表中，因为这个节点在函数末尾很快就会用到。然后它记录下该节点的起始和结束地址（该节点与 bootmem_data_t 有关）并且分配一个位图来表示页面的分配情况。位图所需的大小以字节计算，计算公式如下：
该位图存放于由 bootmem_data_t→node_boot_start 指向的物理地址处，而其虚拟地址的映射由 bootmem_data_t→node_bootmem_map 指定。由于不存在与结构无关的方式来检测内存中的空洞，整个位图就被初始化为 1 来有效地标志所有已分配的页。将可用页面的位设置为 0 的工作则由与结构相关的代码完成，但在实际中只有 Spare 结构使用到这个位图。在 x86 结构中，register_bootmem_low_pages() 通过检测 e820 映射图，并在每一个可用页面上调用 free_bootmem() 函数，将其位设为 1，然后再调用 reserve_bootmem() 为保存实际位图所需的页面预留空间。
5.4 分配内存
// mm/bootmem.c void __init reserve_bootmem (unsigned long addr, unsigned long size) { reserve_bootmem_core(contig_page_data.bdata, addr, size); } static void __init reserve_bootmem_core(bootmem_data_t *bdata, unsigned long addr, unsigned long size) { unsigned long i; /* * round up, partially reserved pages are considered * fully reserved. */ unsigned long sidx = (addr - bdata->node_boot_start)/PAGE_SIZE; unsigned long eidx = (addr + size - bdata->node_boot_start + PAGE_SIZE-1)/PAGE_SIZE; unsigned long end = (addr + size + PAGE_SIZE-1)/PAGE_SIZE; for (i = sidx; i < eidx; i++) if (test_and_set_bit(i, bdata->node_bootmem_map)) printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE); }
reserve_bootmem() 函数用于保存调用者所需的页面，但对于一般的页面分配而言它是相当麻烦的。在 UMA 结构中，有四个简单的分配函数：alloc_bootmem()，alloc_bootmem_low() ，alloc_bootmem_pages() 和 alloc_bootmem_low_pages() 。 对它们的详细描述如表 5.1 所列。
这些函数都以不同的参数调用 __alloc_bootmem()，如图 5.1 所示：
在 NUMA 结构中，同样存在几个相似的函数，alloc_bootmem_node()，
alloc_bootmem_pages_node() 和 alloc_bootmem_low_pages_node() ，只不过它们多了一个节点作为参数。同样，它们也都调用 __alloc_bootmem_node()，只是参数不同。
无论是 __alloc_bootmem() 还是 __alloc_bootmem_node() ，本质上它们的参数相同。
// mm/bootmem.c void * __init __alloc_bootmem (unsigned long size, unsigned long align, unsigned long goal) { // ... for_each_pgdat(pgdat) if ((ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal))) return(ptr); // ... return NULL; } void * __init __alloc_bootmem_node (pg_data_t *pgdat, unsigned long size, unsigned long align, unsigned long goal) { void *ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal); // ... return NULL; } static void * __init __alloc_bootmem_core (bootmem_data_t *bdata, unsigned long size, unsigned long align, unsigned long goal) { // ... }
pdgat：要分配的节点。在 UMA 结构中，它被省掉了，其默认值是 contig_page_data。
size：所需要分配的空间大小；
align：要求对齐的字节数。如果分配空间比较小，就以 SMP_CACHE_BYTES 对齐，在 x86 结构中，它是硬件一级高速缓存的对齐方式。
goal：最佳分配的起始地址。底层函数一般从物理地址 0 开始，其他函数则开始于 MAX_DMA_ADDRESS，它是这种结构中 DMA 传输模式的最大地址。
__alloc_bootmem_core() 是所有 API 分配函数的核心。它是一个非常大的函数，因为它拥有许多可能出错的小步骤。该函数从 goal 地址开始，在线性范围内扫描一个足够大的内存空间以满足分配要求。对于 API 来说，这个地址或者是 0（适合 DMA 的分配方式），或者就是 MAX_DMA_ADDRESS。
该函数最巧妙、最主要的一部分在于判断新的分配空间是否能与上一个合并这一问题。
满足下列条件则可合并：
上次分配的页与此次分配（bootmem_date→pos）所找到的页相邻；
上一页有一定的空闲空间，即 bootmem_dataoffset != 0；
对齐小于 PAGE_SIZE。
不管分配是否能够合并，我们都必须更新 pos 和 offset 两个字段来表示分配的最后一页，以及该页使用了多少。如果该页完全使用，则 offset 为 0；
5.5 释放内存
与分配的函数不同，Linux 只提供了释放的函数，即用于 UMA 的 free_bootmem()，和用于 NUMA 的 free_bootmem_node() 。 两者都调用 free_bootmem_core()，只是 NUMA 中的不提供参数 pgdat。
相比分配器的其他函数而言，核心函数较为简单。对于受释放影响的每个完整页面的相应位被设为 0。如果原来就是 0，则调用 BUG() 提示发生重复释放错误。BUG() 用于由于内核故障而产生的不能消除的错误。它终止正在运行中的程序，使内核陷入循环，并打印出栈内信息和调试信息供开发者调试。
对释放函数的一个重要限制是只有完整的页面才可释放，它不会记录何时一个页面被部
分分配。所以当一个页面要部分释放时，整个页面都将保留。其实这并非是一个大问题，因为分配器在整个系统周期中都驻留内存，但启动时间内，它却是对开发者的一个重要限制。
// mm/bootmem.c static unsigned long __init free_all_bootmem_core(pg_data_t *pgdat) { struct page *page = pgdat->node_mem_map; bootmem_data_t *bdata = pgdat->bdata; unsigned long i, count, total = 0; unsigned long idx; if (!bdata->node_bootmem_map) BUG(); count = 0; idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT); for (i = 0; i < idx; i++, page++) { if (!test_bit(i, bdata->node_bootmem_map)) { count++; ClearPageReserved(page); set_page_count(page, 1); __free_page(page); } } total += count; /* * Now free the allocator bitmap itself, it's not * needed anymore: */ page = virt_to_page(bdata->node_bootmem_map); count = 0; for (i = 0; i < ((bdata->node_low_pfn-(bdata->node_boot_start >> PAGE_SHIFT))/8 + PAGE_SIZE-1)/PAGE_SIZE; i++,page++) { count++; ClearPageReserved(page); set_page_count(page, 1); __free_page(page); } total += count; bdata->node_bootmem_map = NULL; return total; }
5.6 销毁引导内存分配器
启动过程的末期，系统调用函数 start_kernel()，这个函数知道此时可以安全地移除启动分配器和与之相关的所有数据结构。 每种体系都要求提供 mem_init() 函数，该函数负责消除启动内存分配器和与之相关的结构。
这个函数的功能相当简单。它负责计算高、低端内存的维度并向用户显示出信息消息。若有需要，还将运行硬盘的最终初始化。在 x86 平台，有关 VM 的主要函数是 free_pages_init()。
这个函数首先使引导内存分配器调用函数回收自身，UMA 结构中是调用 free_all_bootmem() 函数，NUMA 中是调用 free_all_bootmem_node() 函数。这两个函数都调用内核函数 free_all_bootmem_core() ，但是使用的参数不同。free_all_bootmem_core() 函数原理很简单，它执行如下任务。
对于这个节点上分配器可以识别的所有未被分配的页面：
将它们结构页面上的 PG_reserved 标志位清 0；
将计数器设置为 1；
调用 __free_pages() 以使伙伴分配器（下章将讨论）能建立释放列表。
释放位图使用的所有页面，并将这些页面交给伙伴分配器。
在这个阶段，伙伴分配器控制了所有在低端内存下的页面。free_all_bootmem() 返回后首先清算保留页面的数量。高端内存页面由 free_pages_init() 负责处理。但此时需要理解的是如何分配和初始化整个 mem_map 序列，以及主分配器如何获取页面。图 5.3 显示了单节点系统中初始化低端内存页面的基本流程。free_all_bootmem() 返回后，ZONE-NORMAL 中的所有页面都为伙伴分配器所有。为了初始化高端内存页面，free_pages_init() 对 highstart_pfn 和 highend_pfn 之间的每一个页面都调用了函数 one_highpage_init() 。此函数简单将 PG_reserved 标志位清 0 ，设置 PG_highmem 标志位，设置计数器为 1 并调用 __free_pages() 将自已释放到伙伴分配器中。这与 free_all_bootmem_core() 操作一样。
此时不再需要引导内存分配器，伙伴分配器成为系统的主要物理页面分配器。值得注意的是，不仅启动分配器的数据被移除，它所有用于启动系统的代码也被移除了。所有用于启动系统的初始函数声明都被标明为 __init，如下所示：
unsigned long __init free_all_bootmem(void)
连接器将这些函数都放在 init 区。x86 平台上 free_initmem() 函数可以释放 __init_begin 到 __init_end 的所有页面给伙伴分配器。通过这种方法，Linux 能释放数量很大的启动代码所使用的内存，已不再需要启动代码。
5.7 2.6中有哪些新特性
引导内存分配器自 2.4 内核就没有什么重要的变化，主要是涉及一些优化和一些次要的有关 NUMA 体系结构的修改。第 1 个优化是在 bootmem_data_t 结构中增加了 last_success 字段。正如名字所表达的意思，该字段记录最近的一次成功分配的位置以减少搜索次数。 如果在 last_success 之前的一个地址释放，则该地址将会被改成空闲的区域。
第 2 个优化也和线性搜索有关。在搜索一个空闲页面时，2.4 内核将测试每个位，这样的开销是很大的。2.6 内核中使用测试一个长度为 BITS_PER_LONG 的块是否都是 1 来取代原来的操作。如果不是，就测试该块中单独的每个比特位。为加快线性搜索，通过函数 init_bootmem() 以节点的物理地址为序将它们排列起来。
最后的一个变更与 NUMA 体系结构及相似的体系结构相关。相似的体系结构现在定义了自己的 init_bootmem() 函数，并且任一个体系结构都可以有选择地定义它们自己的 reserve_bootmem() 函数。
第6章 物理页面分配
6.1 管理空闲块
如上所述，分配器维护空闲页面所组成的块，这里每一块都是 2 的方幂个页面。方幂的指数被称为阶。如图 6.1 所示，内核对于每一个阶都维护结构数组 free_area_t，用于指向一个空闲页面块的链表。
所以，数组的第 0 个元素将会指向具有 20 或 1 个页面大小的块的链表，第一个元素将会是一个具有 21(2) 个页面大小的块的链表，直到 2MAX_ORDER-1 个页面大小的块，MAX_ORDER 的值一般为 10。这消除了一个大页面被分开来满足一个小页面块即能满足的要求的可能性。页面块通过 page→list 这个线性链表来维护。
每一个管理区都有一个 free_area_t 结构数组，即 free_area[MAX_ORDER]，它在 <linux/mm.h> 中的定义如下所示：
// include/linux/mmzone.h typedef struct zone_struct { //... free_area_t free_area[MAX_ORDER]; //... } zone_t; typedef struct free_area_struct { struct list_head free_list; unsigned long *map; } free_area_t;
此结构的字段如下：
- free_list
空闲页面块的链表； - map
表示一对伙伴状态的位图。
6.2 分配页面
Linux 通过使用一位而非两位来表示每一对伙伴从而节省内存。每当一个伙伴被分配出去或者被释放，这对伙伴的位就会被切换。因此，如果这对页面块都是空闲的或者都在使用中，这个位就是 0；如果仅仅有一个在使用则这个位就是 1。为了切换到正确的位，我们使用文件 page_alloc.c 中的宏 MARK_USED() ，对它的解释如下：
#define MARK_USED(index, order, area) \ __change_bit((index) >> (1+(order)),(area)->map)
index 就是全局的 mem_map 数组中的页面下标。将它向右移动 1+order 位就可以得到代表伙伴对的映射中的位。
分配通常依据一个特定的幂次进行，0 代表需要一个单独的页面。如果空闲块不能满足所需的层，则一个高次的块会被分成两个伙伴，一个用于分配，另一个放入低次的空闲链表中。图 6.3 展示了一个块在何处被分开以及伙伴如何被加入到空闲链表直至找到一个适合进程的块。
当这个块被最终释放时，其伙伴将会被检查。如果两个都是空闲块，它们就会合并为一个次数较高的块并被放入高次链表。在此链表中伙伴被检测。如果伙伴并不空闲，则被释放的页面块就会加入当前次数的空闲链表。在这些链表的操作中，当一个进程处于不一致状态时，必须禁止中断，以防其他中断处理操作链表。这些措施通过使用中断安全的自旋锁来实现。
第二步决定使用哪个内存节点以及哪个 pg_data_t。Linux 使用了本地节点的分配策略，这是为了使用和运行与页面分配进程的 CPU 相关联的内存库。此处函数 __alloc_pages() 非常重要，因为它根据内核是建立在 UMA（mm/page_alloc.c 中提供的功能）上还是建立在 NUMA（mm/numa.c 提供的功能）上而有所不同。
无论使用哪一个 API，mm/page_alloc.c 中的函数 __alloc_pages() 都是分配器的核心。这个函数从不被直接调用，它会检查选定的管理区，看这个管理区可用的页面数量上是否适合分配。如果这个管理区不适合，分配器将会退回到其他管理区。退回的管理区的次在启动时由函数 build_zonelists() 决定。但通常是从 ZONE_HIGHMEM 退回到 ZONE_NORMAL，从 ZONE_NORMAL 再退回到 ZONE_DMA。如果空闲页面的数量达到 pages_low 的要求，系统激活 kswapd 开始从管理区中释放页面。如果内存空间极度紧张，调用者将自己完成 kswapd 的工作。
一旦最终选定了管理区，系统会调用函数 rmqueue() 分配页面块，或在没有合适大小的情况下切分高次的块。
6.3 释放页面
用于释放页面的主要函数是 __free_pages_ok()，它不能被直接调用，而是提供了函数 __free_pages()，它会首先进行一些简单的检查，如图 6.4 所示。
在释放伙伴时，Linux 会试着尽可能快地合并它们。但这并不是最优的做法，因为在最坏的情况下，分开块后即会有许多次的合并 [Vah96]。
为了探测伙伴们是不是可以合并，Linux 在 free_areamap 中检查与受影响的伙伴相对应的位。由于一个伙伴刚刚被此函数释放，很显然它知道至少有一个伙伴是空闲的。如果切换以后位图中的位是 0，那么另外一个伙伴也肯定是空闲的，因为如果这个位是 0，就意味着两个伙伴或者同为空闲或者同被分配。如果两个都是空闲的，系统可以合并它们。
计算这个伙伴地址有一个著名的方法 [Knu68]。由于分配是以 2k 个块进行的，块的地址，或者说至少它在 zone_mem_map 的起始地址将会是 2k 的整次幂。最终的结论是总会有至少 k 个数字的 0 在地址的右边。为了得到伙伴的地址，从右边数的第 k 位检测。如果为 0，伙伴将会翻转自己的位。为了得到这个位的值，Linux 引入了一个掩码，其计算如下：
mask=(~0<<k)
我们感兴趣的掩码是：
imask=1+~imask
Linux 在计算此掩码时采用了这个技巧：
imask=-mask=1+~imask
合并伙伴后，它便从空闲链表中被移除，并且这个新的合并对会被移到下一个高次链表中以确定是否可以再次合并。
6.4 获得空闲页面（GFP）标志位
获得空闲页面（GFP）标志位是贯穿整个虚拟内存的永恒概念。这个标志位决定分配器以及 kswapd 如何分配和释放页面。例如，一个中断处理程序也许不需要睡眠，所以它不需要设定 __GFP_WAIT 标志位，设置这个标志位表明调用者可以睡眠。存在 3 组 GFP 标志位，在 linux/mm.h 中有说明。
这 3 组中的第 1 组是列于表 6.3 中的管理区修饰符。这些标志位意味着调用者必须尽可能在一个特定管理区中进行分配。读者需要注意的是，这里没有一个适用于 ZONE_NORMAL 的管理区修饰符，因为管理区修饰符标志位在一个数组里是被用作开端的，0 则暗示在 ZONE_NORMAL 中进行分配。
下一个标志位是列于表 6.4 中的动作修饰符。它们改变了虚拟内存以及调用进程的运作。低级的标志位由于过于简单而不易使用。
要知道每一个实例的正确组合是非常困难的，所以 Linux 中给出了一些高级组合的定义，列于表 6.5 中。具体地，__GFP_ 从列表组合中被移除，所以 __GFP_HIGH 标志位在表中将被称作 HIGH。表 6.6 给出了形成高级标志位的组合。为了帮助理解，我们以 GFP_ATOMIC 为例子说明。它仅仅设置了 __GFP_HIGH 标志位，这意味着它具有高优先级，并使用紧急情况池（如果存在），但不会睡眠，也不会执行 I/O 或访问文件系统。比如这个标志位将会在中断处理程序中使用。
一个进程也许也会在 task_struct 中设置一些影响分配器动作的标志位。linux/shed.h 对所有进程标志位都有定义，表 6.7 只列举了影响虚拟内存的进程标志位。
6.5 进程标志位
一个必须提出的分配器普遍存在的重要问题是内外部的碎片问题。外部碎片是由于可用内存全部是小块而不能满足要求。内部碎片是由于一个大的块必须被分开来响应一些小的请求而浪费的空间。在 Linux 中，外部碎片不是一个非常严重的问题，因为对大块连续页面的请求是非常少见的，通常 vmalloc() 就可以满足这些请求。空闲块的链表确保大的块在不必要的情况下不被分开。
6.6 防止碎片
内部碎片是二进制伙伴系统所特有的一个非常严重的问题。尽管预计碎片只存在于 28% 的空间中 [WJNB95]，但与首先适应分配器的仅 1% 相比，碎片已达到了 60% 的面积。即使使用多种伙伴系统也无法显著改善这种状况 [PN77]。为了解决这个问题，Linux 使用了一个 slab 分配器 [Bon94] 将页面块切割为小的内存块进行分配 [Tan01]，这将在第 9 章中详细讨论。有了这种分配器的组合，内核可以使由内部分片导致的内存消耗量保持在最低限度。
6.7 2.6中有哪些新特性
（1）分配页面
尤其值得注意的不同之处似乎带有表面性。以前定义在 <linux/gfp.h> 中的函数 alloc_pages() 现在成了一个定义在 <linux/mm.h> 中的宏。新的布局仍然容易识别，主要的变化很微小，却很重要。2.4 内核通过编写特定的代码来完成基于运行中的 CPU 选择正确的节点进行分配，但在 2.6 内核中消除了 NUMA 和 UMA 这两种体系结构之间的差别。
在 2.6 内核中，函数 alloc_pages() 调用 numa_node_id() 返回一个当前正在运行的 CPU 相关节点的逻辑 ID。系统把该 NID 传递给 to_alloc_pages() 函数，作为该函数调用 NODE_DATA() 时的参数。在 UMA 结构中，将无条件地返回结果给 contig_page_data，在 NUMA 结构中取而代之的是建立了一个数组，其中存储了函数 NODE_DATA() 以 NID 作为的偏移量。或者说，体系结构负责为 NUMA 内存节点映射建立一个 CPU 的 ID 号。这在 2.4 内核中的节点局部分配策略下依然非常有效，而现在 2.6 中它的定义更加清晰。
（2）Per-CPU 的页面链表
前面在 2.8 节中已经讨论过，页面分配中最重要的改变便是为 Per-CPU 增加的链表。
在 2.4 内核中，分配页面时，需要加上一个中断 —— 安全的自旋锁。在 2.6 内核中，内存页面都由函数 buffered_rmqueue() 从 struct per_cpu_pageset 中分配。如果还没有达到内存下限（per_pu_pageset→low），则在不需要加自旋锁的情况下页面的分配从页面集中分配。在到达内存下限后，系统将会成批地分配大量的页面并加上中断 —— 安全自旋锁，然后添加到 Per-CPU 的链表中，最后返回一个链表给调用函数。
通常更高次的分配是比较少见的，当然它也需要加上中断-安全自旋锁，这样分离和合并伙伴时才没有时间延迟。在 0 次的分配，分离时会有延迟，直到在 Per-CPU 集中到达内存下限为止，而合并时的延迟则会一直持续到达内存上限。
然而，严格意义上，这不是一个延迟伙伴关系算法 [BL89]。尽管页面集中为 0 次分配引入了一个合并延迟，但它看起来更像是一个副作用而不是一个特意设计的特征，并且不存在什么有效的方法释放页面集以及合并伙伴。或者说，尽管 Per-CPU 的代码和新加入的代码占了 mm/page_alloc.c 文件中的大量代码，核心的伙伴关系算法却仍然和 2.4 内核中一样。
这个变化的意义是直截了当的；它减少了为保护伙伴链表的必须加锁的次数。在 Linux 中，高次的分配相对来说较少，因此优化适用于普通的情况。这个变化在有多个 CPU 的机器上更容易看出来，对于单个的 CPU 基本上没有什么差异。当然，页面集也有少量的问题，但它们都并不严重。
第 1 个问题是在页面集中如果有一些 0 次页以正常状态被合并到邻近的高次块中，则系统在进行高次分配时就有可能失败。第 2 个是如果内存很少，而当前 CPU 页面集为空并且其他 CPU 的页集都满时，由于不存在用作从远程页集中回收页面的机制，0 次页分配就有可能失败。最后一个潜在的问题是，伙伴关系中一些新的空闲页可能在其他的页面集中，这可能导致碎片问题。
（3）空闲页面
前面已经介绍过两个新的释放页面的 API 函数 free_hot_page() 和 free_cold_page()。就是这两个函数决定了是否把 Per-CPU 页面集中的页面放在活动或者非活动链表中。然而，尽管设计了 free_cold_page() 函数，但实际上它从没有被调用过。
函数 __free_pages() 所释放的 0 次页面和函数 __page_cache_release() 所释放的页面高速缓存中的空闲页面都存放在活动链表中；反之，高次分配的页面都立即由函数**__free_pages_ok()** 释放。0 次页面通常和用户空间相关，它的分配和释放是最普通的类型。由于大多数分配都是在 0 次上的，所以通过保持页面为 CPU 本地页面，将可以减少锁冲突。
最终，系统必须把页面链表传递给 free_pages_bulk() 函数，否则页面集链表将会占用所有的空闲页。 函数 free_pages_bulk() 将获得一个链表，其 中包括页面块分配、每一个块的次以及从该链表释放的块的计数。这里调用有两种情况：第 1 种情况是高次的页面被释放后传递给 __free_pages_ok() 函数。这时，页面块被放置在一个指定的次序链表中并被计数 1。第 2 种情况是，在运行的 CPU 中，页面集到达了内存上限。在这种情况下，页面集被赋予次 0 且计数为 pageset-batch。
在内核函数 __free_pages_bulk() 开始运行后，释放页面的机制与 2.4 中的伙伴链表非常类似。
（4）GFP 标志位
仍然只有 3 个管理区，因此管理区修饰符仍然相同。然而，增加了 3 个新的 GFP 标志位，它们将影响 VM 的响应请求时工作力度，或者不工作。这些标志位如下：
__GFP_NOFAIL
这个标志位被调用函数用于表明分配从不失败，以及分配器应该保持分配的不确定性。
__GFP_REPEAT
这个标志位被调用函数用于表明被一个请求在分配失败后应当尝试再次分配。在目前的实现中，它与 __GFP_NOFAIL 标志位的行为相同，以后它会被规定为在一小段时间后失败。
__GFP_NORETRY
这个标志位几乎与 __GFP_NOFAIL 标志位相反。它表明，如果分配失败，应该立即返回。在写本书的时候，这些标志位由于它们刚引入，还没有被大量地使用，随着时间的流逝，可能会被使用得越来越多。特别是 __GFP_REPEAT 标志位，将可能被广泛地使用，因为实现这个标志位行为的代码块贯穿于整个内核。
下面介绍的另外一个 GFP 标志位是一个称为 __GFP_COLD 的分配修改器，用于保证非活动页面从 Per-CPU 的链表中分配出来。以 VM 的观点来看，只有函数 page_cache_alloc_cold() 使用这个标志位，而该函数主要在 I/O 预读中使用。通常，页面分配基活动页面链表中取得页面。
最后一个新标志位是 __GFP_NO_GROW。这个标志位是 slab 分配器（在第 8 章中讨论）所使用的内部标志位，它的别名是 SLAB_NO_GROW。它用于表明新的 slab 任何时候都不应该从特定的高速缓存中分配。实际上，系统引入 GFP 标志位以补充旧的 SLAB_NO_GROW 标志位，后者目前在主流内核中并不被使用。
第7章 非连续内存分配
在处理高速缓存相关和内存存取所需大量内存的问题时，内存中使用连续的物理页应该是可取的，但由于伙伴系统的外部分页问题，这种做法又经常行不通。所以 Linux 使用一种叫 vmalloc() 的机制，在这种机制中，非连续的物理内存在虚存中是连续的。
Linux 中虚拟地址空间在 VMALLOC_START 和 VMALLOC_END 之间保留了一块区域，VMALLOC_START 的位置取决于可以访问的物理内存大小，该存储区域的大小至少是 VMALLOC_RESERVE，x86 上它的大小为 127 MB。5.1 节中已经讨论过该存储区域的精确的大小。
该存储区域的页表可以按照请求修改以指向物理页指示器分配的物理页，这就意味着分配的大小必须是硬件页面大小的整数倍。由于分配内存需要改变内核页表，而且仅可用在 VMALLOC_START 和 VMALLOC_RESERVE 之间的虚拟地址空间，所以在内存映射到 vmalloc() 时，内存的数量是有限制的。正是由于这个原因，页表仅保留在核心内核中使用。在 2.4.22 中，页表仅用于存储映射信息 (见第 11 章) 和把内核模块装载到内存。
本章首先描述内核如何跟踪使用 vmalloc 地址空间中区域，接着是如何分配和释放存储区域。
7.1 描述虚拟内存区
vmalloc 地址空间由一个资源映射分配器管理 [Vah06]，struct vm_struct 负责存储基地址/大小键对，在 linux/vmalloc.h 中 vm_struct 定义为：
// include/linux/vmalloc.h struct vm_struct { unsigned long flags; void * addr; unsigned long size; struct vm_struct * next; };
Linux 中的 VMA 的字段不止这么一些，它还包括其他的不属于 vmalloc 领域的信息，该结构体中的字段可以如下简要描述。
flags：使用 vmalloc() 时设为 VM_ALLOC，使用 ioremap 来完成高端内存地址到内核虚拟空间映射时设为 VM_IOREMAP。
addr：内存块的起始地址。
size：正如其名，它是以字节计的内存块大小。
next：是一个指向下一个 vm_struct 的指针，所有的 vm_struct 以地址为次序，且该链表由 vmlist_lock 锁保护。
很显然，内存区域由 next 字段链到一起，并且为了查找简单，它们以地址为次序。为了防止溢出，每个区域至少由一个页面隔离开。如图 7.1 中的空隙所示。
当内核要分配一块新的内存时，函数 get_vm_area() 线性查找 vm_struct 链表，然后由函数 kmalloc() 分配结构体所需的空间。为了重新映射一块内存以完成 I/O，需要使用虚拟区域 (习惯上称之为 ioremapping) ，系统将直接调用该函数完成请求区域的映射。
7.2 分配非连续区域
如表 7.1 所列，Linux 提供了函数 vmalloc() ，vmalloc_dma() 和 vmalloc_32() 以在连续的虚拟地址空间分配内存。它们都只有一个参数 size，它的值是下一页的边距向上取整。这几个函数都返回新分配区域的线性地址。
图 7.2 中的调用图很清楚地表明，在分配内存时有两个步骤。第 1 步使用 get_vm_area() 找到满足请求大小的区域，get_vm_area() 查找 vm_struct 的线性链表，然后返回一个描述该区域的新结构体。
第 2 步首先使用 vmalloc_area_pages() 分配所需的 PGD 记录，然后使用 alloc_area_pmd() 分配 PMD 记录，接着使用 alloc_area_pte() 分配 PTE 记录，最后使用 alloc_page() 分配页面。
vmalloc() 更新的页表并不属于当前进程，属于当前进程的是在 init_mm→pgd 中的引用页表。这意味着当进程访问 vmalloc 区域时将发生缺页中断异常，因为它的页表并没有指向正确的区域。在这个缺页中断处理代码中有个特殊的地方，那就是中断处理代码知道在 vmalloc 区域有个缺页中断，它利用主页表的信息更新当前进程的页表。使用 vmalloc() 处理伙伴分配器以及缺页中断的方法如图 7.3 所示。
7.3 释放非连续内存
函数 vfree() (如表 7.2 所列) 负责释放一块虚拟内存区域，它首先线性查找 vm_struct 链表，在找到需要释放的区域后，就在其 s 上调用 vmfree_area_pages()。如图 7.4 所示。
// 表 7.2 非连续内存释放 API void vfree(void addr) // 释放由 vmalloc()， vmalloc_dma() 或 vmalloc_32() 分配的内存
vmfree_area_pages() 与 vmalloc_area_pages() 正好相反，它遍历页表，并清除该区域的页表记录和相应的页面。
7.4 2.6 中有哪些新特性
2.6 中的非连续内存分配基本与 2.4 中的保持不变。主要的区别是分配页面的内部 API 有一些细微区别。在 2.4 中，vmalloc_area_pages() 负责遍历页表，调用 alloc_area_pte() 分配 PTE 以及页表。在 2.6 中，所有的页表都由 __vmalloc() 预先分配，然后存储在一个数组中并传递给函数 map_vm_area()，由它向内核页表中插入页面。
API 函数 get_vm_area() 也有细微的改变。在调用它时，它和以前一样遍历整个 vmalloc 虚拟地址空间，寻找一块空闲区域。但是，调用者也可以直接调用 __get_vm_area() 并指明范围，就可以只遍历 vmalloc 地址空间的一部分。这仅用于高级 RISC 机器 (ARM) 装载模块。
最后一个显著的改变是引入了一个新的接口 vmap()，它负责向 vmalloc 地址空间插入页面数组 。vmap() 仅用于声音子系统的内核。这个接口向后兼容到 2.4.22，但那时根本没有用到过它。它的引入仅仅是偶然性的向后兼容，或者是为了减轻那些需要 vmap() 的特定供应商补丁的应用负担。
