Buddy 内存管理机制（上）

发表于 2年以前 | 总阅读数：479 次

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() 初始化时主要初始化两部分信息：

1、初始化 struct page :

将 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() 在下一节中解析。

end