伙伴分配器
内核初始化完毕后，使用页分配器管理物理页，当前使用的页分配器是伙伴分配器，伙伴分配器的特点是算法简单且效率高。
（接力棒由之前memblock交给了伙伴分配器）
1-基本的伙伴分配器
1、基本单位-阶和页
连续的物理页称为页块（page block）。
阶（order）是伙伴分配器的一个术语，是页的数量单位，2n个连续页称为n阶页块。
满足以下条件的两个n阶页块称为伙伴（buddy）。
- （1）两个页块是相邻的，即物理地址是连续的。
- （2）页块的第一页的物理页号必须是2n的整数倍。
- （3）如果合并成（n+1）阶页块，第一页的物理页号必须是2n+1的整数倍。
这是伙伴分配器（buddy allocator）这个名字的来源。以单页为例说明，0号页和1号页是伙伴，2号页和3号页是伙伴，1号页和2号页不是伙伴，因为1号页和2号页合并组成一阶页块，第一页的物理页号不是2的整数倍。
伙伴分配器分配和释放物理页的数量单位是阶。
2、分配n阶页块流程
分配n阶页块的过程如下。
- （1）查看是否有空闲的n阶页块，如果有，直接分配；如果没有，继续执行下一步。
- （2）查看是否存在空闲的（n+1）阶页块，如果有，把（n+1）阶页块分裂为两个n阶页块，一个插入空闲n阶页块链表，另一个分配出去；如果没有，继续执行下一步。
- （3）查看是否存在空闲的（n+2）阶页块，如果有，把（n+2）阶页块分裂为两个（n+1）阶页块，一个插入空闲（n+1）阶页块链表，另一个分裂为两个n阶页块，一个插入空闲n阶页块链表，另一个分配出去；如果没有，继续查看更高阶是否存在空闲页块。
3、内核拓展
内核在基本的伙伴分配器的基础上做了一些扩展。
- （1）支持内存节点和区域**，称为分区的伙伴分配器（zoned buddy allocator）**。
- （2）为了预防内存碎片，把物理页根据可移动性分组。
- （3）针对分配单页做了性能优化，为了减少处理器之间的锁竞争，在内存区域增加1个每处理器页集合。
2-分区的伙伴分配器（zoned buddy allocator）
1．数据结构
分区的伙伴分配器专注于某个内存节点的某个区域。
- 内存区域的结构体成员free_area用来维护空闲页块，数组下标对应页块的阶数。
- 结构体free_area的成员free_list是空闲页块的链表（暂且忽略它是一个数组，下面小节将介绍）,
- nr_free是空闲页块的数量。
- 内存区域的结构体成员managed_pages是伙伴分配器管理的物理页的数量，不包括引导内存分配器分配的物理页。
include/linux/mmzone.h struct zone { … /* 不同长度的空闲区域 */ struct free_area free_area[MAX_ORDER]; … unsigned long managed_pages; … } ____cacheline_internodealigned_in_smp; struct free_area { struct list_head free_list[MIGRATE_TYPES]; unsigned long nr_free; };
MAX_ORDER是最大阶数，实际上是可分配的最大阶数加1，默认值是11，意味着伙伴分配器一次最多可以分配210页。
可以使用配置宏CONFIG_FORCE_MAX_ZONEORDER指定最大阶数。
include/linux/mmzone.h /* 空闲内存管理-分区的伙伴分配器 */ #ifndef CONFIG_FORCE_MAX_ZONEORDER #define MAX_ORDER 11 #else #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER #endif
2．根据分配标志得到首选区域类型
申请页时，最低的4个标志位用来指定首选的内存区域类型：
include/linux/gfp.h #define ___GFP_DMA 0x01u #define ___GFP_HIGHMEM 0x02u #define ___GFP_DMA32 0x04u #define ___GFP_MOVABLE 0x08u
标志组合和首选的内存区域类型的对应关系如表所示。
图片
为什么要使用OPT_ZONE_DMA，而不使用ZONE_DMA？
因为DMA区域是可选的，如果不存在只能访问16MB以下物理内存的外围设备，那么不需要定义DMA区域，OPT_ZONE_DMA就是ZONE_NORMAL，从普通区域申请页。高端内存区域和DMA32区域也是可选的。
include/linux/gfp.h #ifdef CONFIG_HIGHMEM #define OPT_ZONE_HIGHMEM ZONE_HIGHMEM #else #define OPT_ZONE_HIGHMEM ZONE_NORMAL #endif #ifdef CONFIG_ZONE_DMA #define OPT_ZONE_DMA ZONE_DMA #else #define OPT_ZONE_DMA ZONE_NORMAL #endif #ifdef CONFIG_ZONE_DMA32 #define OPT_ZONE_DMA32 ZONE_DMA32 #else #define OPT_ZONE_DMA32 ZONE_NORMAL #endif
- 内核使用宏GFP_ZONE_TABLE定义了标志组合到区域类型的映射表，
- 其中GFP_ZONES_SHIFT是区域类型占用的位数，
- GFP_ZONE_TABLE把每种标志组合映射到32位整数的某个位置，偏移是（标志组合 * 区域类型位数），从这个偏移开始的GFP_ZONES_SHIFT个二进制位存放区域类型。
- 宏GFP_ZONE_TABLE是一个常量，编译器在编译时会进行优化，直接计算出结果，不会等到运行程序的时候才计算数值。
include/linux/gfp.h #define GFP_ZONE_TABLE ( \ (ZONE_NORMAL << 0 * GFP_ZONES_SHIFT) \ | (OPT_ZONE_DMA << ___GFP_DMA * GFP_ZONES_SHIFT) \ | (OPT_ZONE_HIGHMEM << ___GFP_HIGHMEM * GFP_ZONES_SHIFT) \ | (OPT_ZONE_DMA32 << ___GFP_DMA32 * GFP_ZONES_SHIFT) \ | (ZONE_NORMAL << ___GFP_MOVABLE * GFP_ZONES_SHIFT) \ | (OPT_ZONE_DMA << (___GFP_MOVABLE | ___GFP_DMA) * GFP_ZONES_SHIFT) \ | (ZONE_MOVABLE << (___GFP_MOVABLE | ___GFP_HIGHMEM) * GFP_ZONES_SHIFT)\ | (OPT_ZONE_DMA32 << (___GFP_MOVABLE | ___GFP_DMA32) * GFP_ZONES_SHIFT) \ )
gfp_zone()
内核使用函数gfp_zone()根据分配标志得到首选的区域类型：
- 先分离出区域标志位，
- 然后算出在映射表中的偏移（区域标志位 * 区域类型位数），
- 接着把映射表右移偏移值，
- 最后取出最低的区域类型位数。
include/linux/gfp.h static inline enum zone_type gfp_zone(gfp_t flags) { enum zone_type z; int bit = (__force int) (flags & GFP_ZONEMASK); z = (GFP_ZONE_TABLE >> (bit * GFP_ZONES_SHIFT)) & ((1 << GFP_ZONES_SHIFT) - 1); VM_BUG_ON((GFP_ZONE_BAD >> bit) & 1); return z; }
3．备用区域列表
如果首选的内存节点和区域不能满足页分配请求，可以从备用的内存区域借用物理页，借用必须遵守以下原则。
- （1）一个内存节点的某个区域类型可以从另一个内存节点的相同区域类型借用物理页，例如节点0的普通区域可以从节点1的普通区域借用物理页。
- （2）高区域类型可以从低区域类型借用物理页，例如普通区域可以从DMA区域借用物理页。
- （3）低区域类型不能从高区域类型借用物理页，例如DMA区域不能从普通区域借用物理页。
内存节点的pg_data_t实例定义了备用区域列表，其代码如下：
include/linux/mmzone.h typedef struct pglist_data { … struct zonelist node_zonelists[MAX_ZONELISTS]; /* 备用区域列表 */ … } pg_data_t; enum { ZONELIST_FALLBACK, /* 包含所有内存节点的备用区域列表 */ #ifdef CONFIG_NUMA ZONELIST_NOFALLBACK, /* 只包含当前内存节点的备用区域列表(__GFP_THISNODE) */ #endif MAX_ZONELISTS }; #define MAX_ZONES_PER_ZONELIST (MAX_NUMNODES * MAX_NR_ZONES) struct zonelist { struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1]; }; struct zoneref { struct zone *zone; /* 指向内存区域的数据结构 */ int zone_idx; /* 成员zone指向的内存区域的类型 */ };
- UMA系统只有一个备用区域列表，按区域类型从高到低排序。假设UMA系统包含普通区域和DMA区域，那么备用区域列表是：｛普通区域，DMA区域｝。
- NUMA系统的每个内存节点有两个备用区域列表：
- 一个包含所有内存节点的区域，
- 另一个只包含当前内存节点的区域。
如果申请页时指定标志__GFP_THISNODE，要求只能从指定内存节点分配物理页，就需要使用指定内存节点的第二个备用区域列表。
包含所有内存节点的备用区域列表有两种排序方法。
- （1）节点优先顺序：先根据节点距离从小到大排序，然后在每个节点里面根据区域类型从高到低排序
- （2）区域优先顺序：先根据区域类型从高到低排序，然后在每个区域类型里面根据节点距离从小到大排序。
节点优先顺序的
- 优点是优先选择距离近的内存，缺点是在高区域耗尽以前就使用低区域，例如DMA区域一般比较小，节点优先顺序会增大DMA区域耗尽的概率。
- 区域优先顺序的优点是减小低区域耗尽的概率，缺点是不能保证优先选择距离近的内存。
默认的排序方法是自动选择最优的排序方法：
- 如果是64位系统，因为需要DMA和DMA32区域的设备相对少，所以选择节点优先顺序；
- 如果是32位系统，选择区域优先顺序。
可以使用内核参数“numa_zonelist_order”指定排序方法：
- “d”表示默认排序方法，
- “n”表示节点优先顺序，
- “z”表示区域优先顺序，大小写字母都可以。
在运行中可以使用文件“/proc/sys/vm/numa_zonelist_order”修改排序方法。
假设NUMA系统包含节点0和1，节点0包含普通区域和DMA区域，节点1只包含普通区域。如果选择节点优先顺序，两个节点的备用区域列表如图所示。
图片
- 如果节点0的处理器申请普通区域的物理页，应该依次尝试节点0的普通区域、节点0的DMA区域和节点1的普通区域。
- 如果节点0的处理器申请DMA区域的物理页，首选区域是节点0的DMA区域，备用区域列表没有其他DMA区域可以选择。
4．区域水线
首选的内存区域在什么情况下从备用区域借用物理页？这个问题要从区域水线开始说起。每个内存区域有3个水线。
- （1）高水线（high）：如果内存区域的空闲页数大于高水线，说明该内存区域的内存充足。
- （2）低水线（low）：如果内存区域的空闲页数小于低水线，说明该内存区域的内存轻微不足。
- （3）最低水线（min）：如果内存区域的空闲页数小于最低水线，说明该内存区域的内存严重不足。
include/linux/mmzone.h enum zone_watermarks { WMARK_MIN, WMARK_LOW, WMARK_HIGH, NR_WMARK }; struct zone { … /* 区域水线，使用*_wmark_pages(zone) 宏访问 */ unsigned long watermark[NR_WMARK]; … } ____cacheline_internodealigned_in_smp;
最低水线以下的内存称为紧急保留内存，在内存严重不足的紧急情况下，给承诺“给我少量紧急保留内存使用，我可以释放更多的内存”的进程使用。
设置了进程标志位PF_MEMALLOC的进程可以使用紧急保留内存，标志位PF_MEMALLOC表示承诺“给我少量紧急保留内存使用，我可以释放更多的内存”。内存管理子系统以外的子系统不应该使用这个标志位，典型的例子是页回收内核线程kswapd，在回收页的过程中可能需要申请内存。
如果申请页时设置了标志位__GFP_MEMALLOC，即调用者承诺“给我少量紧急保留内存使用，我可以释放更多的内存”，那么可以使用紧急保留内存。申请页时，第一次尝试使用低水线，如果首选的内存区域的空闲页数小于低水线，就从备用的内存区域借用物理页。如果第一次分配失败，那么唤醒所有目标内存节点的页回收内核线程kswapd以异步回收页，然后尝试使用最低水线。如果首选的内存区域的空闲页数小于最低水线，就从备用的内存区域借用物理页。
申请页时，第一次尝试使用低水线，如果首选的内存区域的空闲页数小于低水线，就从备用的内存区域借用物理页。如果第一次分配失败，那么唤醒所有目标内存节点的页回收内核线程kswapd以异步回收页，然后尝试使用最低水线。如果首选的内存区域的空闲页数小于最低水线，就从备用的内存区域借用物理页。
1-计算水线时，有两个重要的参数。
- （1）min_free_kbytes是最小空闲字节数。默认值 = 4 * lowmen_kbytes，并且限制在范围[128,65536]以内。其中lowmem_kbytes是低端内存大小，单位是KB。参考文件“mm/page_alloc.c”中的函数init_per_zone_wmark_min。可以通过文件“/proc/sys/vm/min_free_kbytes”设置最小空闲字节数。
- （2）watermark_scale_factor是水线缩放因子。默认值是10，可以通过文件“/proc/sys/vm/watermark_scale_factor”修改水线缩放因子，取值范围是[1,1000]。
文件“mm/page_alloc.c”中的函数__setup_per_zone_wmarks()负责计算每个内存区域的最低水线、低水线和高水线。
计算最低水线的方法如下。
- （1）min_free_pages = min_free_kbytes对应的页数。
- （2）lowmem_pages = 所有低端内存区域中伙伴分配器管理的页数总和。
- （3）高端内存区域的最低水线 = zone->managed_pages/1024，并且限制在范围[32, 128]以内（zone->managed_pages是该内存区域中伙伴分配器管理的页数，在内核初始化的过程中引导内存分配器分配出去的物理页，不受伙伴分配器管理）。
- （4）低端内存区域的最低水线 = min_free_pages * zone->managed_pages /lowmem_pages，即把min_free_pages按比例分配到每个低端内存区域。
计算低水线和高水线的方法如下。
- （1）增量 = (最低水线 / 4, zone->managed_pages * watermark_scale_factor / 10000)取最大值。
- （2）低水线 = 最低水线 + 增量。
- （3）高水线 = 最低水线 + 增量 * 2。
如果（最低水线 / 4）比较大，那么计算公式简化如下。
- （1）低水线 = 最低水线 * 5/4。
- （2）高水线 = 最低水线 * 3/2。
5．防止过度借用
和高区域类型相比，低区域类型的内存相对少，是稀缺资源，而且有特殊用途，例如DMA区域用于外围设备和内存之间的数据传输。为了防止高区域类型过度借用低区域类型的物理页，低区域类型需要采取防卫措施，保留一定数量的物理页。
一个内存节点的某个区域类型从另一个内存节点的相同区域类型借用物理页，后者应该毫无保留地借用。
内存区域有一个数组用于存放保留页数：
include/linux/mmzone.h struct zone { … long lowmem_reserve[MAX_NR_ZONES]; … } ____cacheline_internodealigned_in_smp;
zone[i]->lowmem_reserve[j]表示区域类型i应该保留多少页不能借给区域类型j，仅当j大于i时有意义。
zone[i]->lowmem_reserve[j]的计算规则如下：
(i < j): zone[i]->lowmem_reserve[j] = (当前内存节点上从zone[i + 1] 到zone[j]伙伴分配器管理的页数总和) / sysctl_lowmem_reserve_ratio[i] (i = j): zone[i]->lowmem_reserve[j]= 0（相同的区域类型不应该保留） (i > j): zone[i]->lowmem_reserve[j]= 0（没意义，不会出现低区域类型从高区域类型借用物理页的情况）
数组sysctl_lowmem_reserve_ratio存放各种区域类型的保留比例，因为内核不允许使用浮点数，所以使用倒数值。DMA区域和DMA32区域的默认保留比例都是256，普通区域和高端内存区域的默认保留比例都是32。
mm/page_alloc.c int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = { #ifdef CONFIG_ZONE_DMA 256, #endif #ifdef CONFIG_ZONE_DMA32 256, #endif #ifdef CONFIG_HIGHMEM 32, #endif 32, };
可以通过文件“/proc/sys/vm/lowmem_reserve_ratio”修改各种区域类型的保留比例。
