3137
作者简介：伟林，中年码农，从事过电信、手机、安全、芯片等行业，目前依旧从事Linux方向开发工作，个人爱好Linux相关知识分享。
Buddy 简介
内存是计算机系统中最重要的核心资源之一，Buddy 系统是 Linux 最底层的内存管理机制，它使用 Page 粒度来管理内存。通常情况下一个 Page 的大小为 4K，在 Buddy 系统中分配、释放、回收的最小单位都是 Page。
上图是 Buddy 系统的内部组织结构，本篇文章只关心未分配区域Free区域的管理，下篇文章再来分析可回收区域的管理。
统的内存总大小动辄几G几十G，不同的内存区域也有不同的特性。Buddy 使用层次化的结构把这些特性给组织起来：
1、Node。在 NUMA 架构下存在多个 Memory 和 CPU 节点，不同 CPU 访问不同 Memory 节点的速度是不一样的，使用 Node 的形式把各个 Memory 节点的内存管理起来。
2、Zone。某些外设只能访问低 16M 的物理地址，某些外设只能访问低 4G 的物理地址，32bit 的内核空间只能直接映射低 896M 物理地址。根据这些地址空间的限制，把同一个 node 内的内存再划分成多个 zone 。
3、Order Freelist。按照空闲内存块的长度，把内存挂载到不同长度的 freelist 链表中。freelist 的长度是以 (2^order x Page) 来递增的，即 1 page、2 page、4 page … 2^n，通常情况下最大 order 为10 对应的空闲内存大小为 4M bytes。在分配时，如果一个空闲块的大小不能被任一长度整除，它就从大到小逐个分解成多个 (2^order x Page) 块来挂载；在释放时，首先把内存释放到对应长度的链表中，随后看看和该内存大小相同、地址相邻的兄弟块(Buddy)是不是free的，如果可以和 buddy 块合并成一个大块挂载到更高一阶的链表，在挂载的时候继续尝试合并。这就是 Buddy 的核心思想，已2的幂个 page 的长度来管理内存方便分配和释放，最核心的目的就是减少内存的碎片化。
4、Migrate Type。为了进一步减少碎片化，系统对内存按照迁移类型进行了分类，最基本的迁移类型有：不可移动(unmovable)、可移动(movable)、可回收(reclaimable)。初始的最大块空闲内存都是 unmovable 的，如果其中一小块分配给了 reclaimable ，那么剩下的内存都变成了 reclaimable。这样坏的类型和坏的类型集中到了一起，避免坏情况的扩散从而造成多个 Free 区域无法合并的情况。
5、PerCPU 1 Page Cache。大于 1 Page 的内存分配大多发生在内核态，而用户态的内存分配使用的是缺页机制所以分配的大小一般是 1 Page。针对大小为 1 Page 的内存分配，系统设计了一个免锁的 PerCPU cache 来支撑。1 Page (Order = 0) 的空闲内存优先释放到 PCP 中，超过了一定 batch 才会释放到 Order Freelist当中；同样 1 Page 的内存也优先在 PCP 中分配。
Buddy 初始化
Struct Page 初始化
以 Page 大小的粒度来管理内存，一个 Page 对应的物理内存称为页框 (Page Frame)。另外为了应对复杂的管理，系统给每个 Page 还分配了一个管理结构 struct page，系统在初始化时会预留这部分的物理内存并且映射到 vmemmap 区域 (参考：内核地址空间布局)，内核根据物理页帧的编号 pfn 就能在 vmemmap 区域中找到对应的 struct page 结构。
struct page 结构存储了很多信息 (参考：Page 页帧管理详解)。在 sparse_init() 时已经把所有的struct page 结构清零，zone_sizes_init() 初始化时主要初始化两部分信息：
将 page->flags 中保存的 setcion、node、zone 设置成对应的 index，这样后续操作 struct page 结构时就能快速的找到对应的 setcion、node、zone 而不需要重新根据 pfn 来进行计算。page->flags 中的 flag 部分初始化为 0。
另外给 page->_refcount、_mapcount、_last_cpupid、lru 等成员都进行了初始化。
start_kernel() → setup_arch() → x86_init.paging.pagetable_init() → native_pagetable_init() → paging_init() → zone_sizes_init() → free_area_init_nodes() → free_area_init_node() → free_area_init_core():
|→ memmap_init() → memmap_init_zone()
void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
unsigned long start_pfn, enum memmap_context context)
{
for (pfn = start_pfn; pfn < end_pfn; pfn++) {
/* (2) 当前是一个pageblock的第一个page */
if (!(pfn & (pageblock_nr_pages - 1))) {
struct page *page = pfn_to_page(pfn);
/* (2.1) 初始化对应的 struct page 结构 */
__init_single_page(page, pfn, zone, nid,
context != MEMMAP_HOTPLUG);
/* (2.2) 初始化时把所有pageblock的migratetype设置成MIGRATE_MOVABLE */
set_pageblock_migratetype(page, MIGRATE_MOVABLE);
cond_resched();
/* (3) pageblock中的其他page */
} else {
/* (3.1) 初始化对应的 struct page 结构 */
__init_single_pfn(pfn, zone, nid,
context != MEMMAP_HOTPLUG);
}
}
}
↓
__init_single_pfn()
↓
static void __meminit __init_single_page(struct page *page, unsigned long pfn,
unsigned long zone, int nid, bool zero)
{
/* (2.1.1) 如果需要，对struct page结构清零 */
if (zero)
mm_zero_struct_page(page);
/* (2.1.2) 设置page->flags中的setcion index、node index、zone index */
set_page_links(page, zone, nid, pfn);
/* (2.1.3) 设置page->_refcount = 1 */
init_page_count(page);
/* (2.1.4) 设置page->_mapcount = -1 */
page_mapcount_reset(page);
/* (2.1.5) 设置page->_last_cpupid = -1 */
page_cpupid_reset_last(page);
/* (2.1.6) 初始化page->lru */
INIT_LIST_HEAD(&page->lru);
#ifdef WANT_PAGE_VIRTUAL
/* The shift won't overflow because ZONE_NORMAL is below 4G. */
if (!is_highmem_idx(zone))
set_page_address(page, __va(pfn << PAGE_SHIFT));
#endif
}
2、分配并初始化 zone->pageblock_flags：文章开始时说了 migrate type 的概念。系统把内存划分成多个 pageblock，一个 pageblock 即对应 (2^max_order x Page)，每个 pageblock 拥有自己的 migrate type。
系统以 zone 为单位分配空间来保存所有 pageblock 的 migrate type：
start_kernel() → setup_arch() → x86_init.paging.pagetable_init() → native_pagetable_init() → paging_init() → zone_sizes_init() → free_area_init_nodes() → free_area_init_node() → free_area_init_core():
|→ setup_usemap()
static void __init setup_usemap(struct pglist_data *pgdat,
struct zone *zone,
unsigned long zone_start_pfn,
unsigned long zonesize)
{
unsigned long usemapsize = usemap_size(zone_start_pfn, zonesize);
zone->pageblock_flags = NULL;
if (usemapsize)
/* (1) 分配存储当前zone里所有pageblock的migrate标志 */
zone->pageblock_flags =
memblock_virt_alloc_node_nopanic(usemapsize,
pgdat->node_id);
}
pageblock 的初始 migrate type 为 MIGRATE_MOVABLE：
void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
unsigned long start_pfn, enum memmap_context context)
{
for (pfn = start_pfn; pfn < end_pfn; pfn++) {
/* (2) 当前是一个pageblock的第一个page */
if (!(pfn & (pageblock_nr_pages - 1))) {
struct page *page = pfn_to_page(pfn);
/* (2.1) 初始化对应的 struct page 结构 */
__init_single_page(page, pfn, zone, nid,
context != MEMMAP_HOTPLUG);
/* (2.2) 初始化时把所有pageblock的migratetype设置成MIGRATE_MOVABLE */
set_pageblock_migratetype(page, MIGRATE_MOVABLE);
cond_resched();
/* (3) pageblock中的其他page */
} else {
/* (3.1) 初始化对应的 struct page 结构 */
__init_single_pfn(pfn, zone, nid,
context != MEMMAP_HOTPLUG);
}
}
}
pageblock 中第一个分配的内存的 migrate type 决定了整个 pageblock 的 migrate type。
Buddy 初始化
在内核启动过程中在 Buddy 初始化以前，系统使用一个简便的 Memblock 机制来管理内存。在 Buddy 数据结构准备好后，需要把 Memblock 中的内存释放到 Buddy 当中。
这就是 Buddy 系统初始的状态，除了保留的内存，其他的内存都处于 Free 状态：
start_kernel() → mm_init() → mem_init() → free_all_bootmem():
unsigned long __init free_all_bootmem(void)
{
unsigned long pages;
/* (1) 将每个node每个zone管理的page清零：z->managed_pages = 0 */
reset_all_zones_managed_pages();
/* (2) 将memblock中的内存转移到buddy系统中 */
pages = free_low_memory_core_early();
totalram_pages += pages;
return pages;
}
↓
static unsigned long __init free_low_memory_core_early(void)
{
unsigned long count = 0;
phys_addr_t start, end;
u64 i;
memblock_clear_hotplug(0, -1);
/* (2.1) 遍历memblock中的保留内存，将其对应的`struct page`结构page->flags设置PG_reserved标志 */
for_each_reserved_mem_region(i, &start, &end)
reserve_bootmem_region(start, end);
/*
* We need to use NUMA_NO_NODE instead of NODE_DATA(0)->node_id
* because in some case like Node0 doesn't have RAM installed
* low ram will be on Node1
*/
/* (2.2) 遍历memblock中尚未分配的内存，将其释放到buddy系统中 */
for_each_free_mem_range(i, NUMA_NO_NODE, MEMBLOCK_NONE, &start, &end,
NULL)
count += __free_memory_core(start, end);
return count;
}
↓
__free_memory_core()
↓
static void __init __free_pages_memory(unsigned long start, unsigned long end)
{
int order;
/* (2.2.1) 对需要释放的区域，拆分成尽可能大的 2^order 内存块去释放 */
while (start < end) {
order = min(MAX_ORDER - 1UL, __ffs(start));
/* (2.2.1.1) 计算最大的释放长度(2^order)page */
while (start + (1UL << order) > end)
order--;
/* (2.2.1.2) 继续释放 */
__free_pages_bootmem(pfn_to_page(start), start, order);
start += (1UL << order);
}
}
↓
__free_pages_bootmem() → __free_pages_boot_core() → __free_pages()
具体的释放细节 __free_pages() 在下一节中解析。
