内存管理之页分配器

Linux操作系统内存管理是操作系统的核心功能，目的是为了实现对物理内存的有效利用，包括：内存分配、内存回收、基于物理内存在内核空间中的映射原理，物理内存的管理方式也不完全相同。内核中的物理内存管理主要分为如下几种：

• 连续性大块内存管理
• per-CPU页框高速缓存管理
• slab缓存管理

下面主要讲述大块连续物理内存的管理，其使用伙伴算法逻辑、页表实现管理，以页框为基本单位，使用页管理器（Page Allocator）实现。

连续性大块内存管理策略详解

操作系统内存寻址

• 逻辑地址（Logical Address）
  以应用程序的视角记录内存地址关系的一种方式，一般由段（Segment）+段内偏移（Offset）构成
• 线性地址（Linear/Flat Address）
  也称为虚拟地址，是一种将内存地址空间视作一个单一连续性地址空间的方式。以x86_64为例，使用其中的48位用来寻址，一共可表征256TB的空间。

• 物理地址（Physical Address）
  是内存设备的电气特性表示，用于内存设备物理内存单元寻址。
  在80x86 CPU中，采用分段和分页进行寻址管理，从而实现把逻辑地址经过分段单元处理，转换为线性地址，再由分页单元处理，转换为物理地址。需要说明的是，上述过程均有硬件完成，而无需操作系统负责转换。
  例如，在Linux Kernel中使用如下方法进行物理地址到虚拟地址的转换：

  _va = x - PHYS_OFFSET +PAGE_OFFSET

  我们将用于将线性地址转换为物理地址的部分，称为分页单元（Paging Unit），下面来详细讲述关于分页单元处理过程：
  线性地址被划分为以固定长度为单位的组，称为页（Page），它是一个逻辑上的概念。同时，分页单元会将物理内存分割成和页一样大小的组，称为页框（Page Frame）。二者大小一致，目的是为了更好地对应映射，便于将页装入不同的页框中。
  在硬件设计中，为了解决虚拟地址空间到物理地址空间的映射，并尽可能提高在映射查找的同时加速内存页面的查找速度，遂建立了多级页表机制，实现快速索引访问。以x86_64位为例，使用四级页表项，每一级占9位，一共寻址64T个页。
  

  四级页表
  
  来源：https://www.imooc.com/article/285600

  连续性内存管理的原理

  连续性能存管理，可以理解为对页框的管理，由于现代CPU都支持了多核特性，从而出现了非一致性内存访问（NUMA），故而出现了基于分区分页的管理。我们这里讨论在某个管理区内的页框的分配与释放管理。

  连续性内存分配

  物理页面的分配会分配出一段连续的物理内存空间，使用来自伙伴系统的内存。分配方法如下：基于GFP掩码+分配阶数order。GFP掩码确定了要分配内存空间所属的zone（zone 在不同的架构下有不同的类型，比如在ARM下就仅有Normal和High两种），order确定了需要的内存空间大小，即order的2次幂数量个页框的内存空间。之所以具有不同大小类型的空间，也是为了提高内存空间的分配效率和回收效率，便于在接近于需求空间大小上进行分配和回收。在找到足够空闲大小的zone后，按照order大小，分配不同2^order的空间。分配剩余部分，则加入到同一zone的order-1级的空闲列表中去。

  连续性内存释放

  基于当前所属的阶（order），计算其相邻的兄弟页框，并判断是否可回收，如果可回收，则将待释放的页合并到一起并继续循环，进入下一阶的循环，如果不可回收。则退出，并加入空闲队列。

  Linux Kernel页管理实现

  在内核中，页面管理初始化经过如下调用流程：start_kernel->setup_arch->paging_init->prepare_page_table
  物理内存管理：物理内存寻址、清零、验证。
  GFP的类型：

• GFP_KERNEL
• GFP_ATOMIC
• __GFP_HIGHMEM

• __GFP_HIGH
  

  页分配数据结构描述
  
  下面简要的将kernel中实现上述页分配管理的逻辑予以说明，整体逻辑并不复杂，但本文中略去了不必要的如：参数检验、不相关代码逻辑、部分逻辑分支等，以更清楚地呈现整个逻辑。
  arch/ia64/kernel/setup.c 中，进行页初始化准备，关键在于从内存驱动中读取分区、页框数等信息，并初始化数据结构。

   // arch/ia64/kernel/setup.c
   setup_arch () {
    ...
     efi_init ();
     io_port_init ();
    ...
     cpu_init ();
    ...
     paging_init ();
  }

  include/linux/mmzone.h 头文件中，详细定义了内存分区情况，以及在kernel中针对于内存页管理的数据结构描述：

 // include/linux/mmzone.h
 struct zone {
     unsigned  long  _watermark [NR_WMARK];
# ifdef CONFIG_NUMA
     int node;
#endif
     unsigned  long zone_start_pfn;
     const  char *name;
    ...
     struct free_area free_area [MAX_ORDER];
     spinlock_t lock;
    ...
}

 struct free_area {
     struct list_head free_list [MIGRATE_TYPES];
     unsigned  long nr_free;
}

内核页分配实现

具体的也分配逻辑如下：

 // mm/page_alloc.c
 /*
 * This is the 'heart' of the zoned buddy allocator.
 */
__alloc_pages () {
    ...
    gfp = current_gfp_context ();
    ...
    page = get_page_from_freelist (alloc_gfp, order, alloc_flags, &ac);
     if ( likely (page))
         goto out;
    ...
    page = __alloc_pages_slowpath (alloc_gfp, order, &ac);
out:
     if ( memcg_kmem_enabled () && (gfp & __GFP_ACCOUNT) && page &&
     unlikely ( __memcg_kmem_charge_page (page, gfp, order) != 0 )) {
         __free_pages (page, order);
        page = NULL ;
    }
     trace_mm_page_alloc (page, order, alloc_gfp, ac . migratetype );
     return page;
}

get_page_from_freelist ()
    -> rmqueue () // 从Node缓冲的页队列中取出可用的页，页选择在Node的空闲页和脏页的阈值范围内
        -> __rmqueue () 
            -> __rmqueue_smallest () // 从0开始，循环每个order，并从满足的中间取出page
                -> prep_new_page ()

 struct page * __rmqueue_smallest ( struct zone * zone , unsigned  int  order , int  migratetype )
{
     unsigned  int current_order;
     struct free_area *area;
     struct page *page;
     /* Find a page of the appropriate size in the preferred list */
     for (current_order = order; current_order < MAX_ORDER; ++current_order) {
        area = &( zone -> free_area [current_order]);
        page = get_page_from_free_area (area, migratetype);
         if (!page)
             continue ;
         del_page_from_free_list (page, zone, current_order);
         expand (zone, page, order, current_order, migratetype);
         set_pcppage_migratetype (page, migratetype);
         return page;
    }
    return  NULL ;
}

内核页释放实现

释放一个页面的流程：
基于当前所属的阶（order），计算其相邻的兄弟页框，并判断是否可回收，如果可回收，则将待释放的页合并到一起并继续循环，进入下一阶的循环，如果不可回收。则退出，并加入空闲队列。

// mm/page_alloc.c
__free_one_page() {
    // 合并PageBuddy，并加入到空闲链表
    continue_merging:
    while (order < max_order) {
        buddy_pfn = __find_buddy_pfn(pfn, order);
        buddy = page + (buddy_pfn - pfn);
        if (!page_is_buddy(page, buddy, order))
        goto done_merging;
        del_page_from_free_list(buddy, zone, order);
        combined_pfn = buddy_pfn & pfn;
        page = page + (combined_pfn - pfn);
        pfn = combined_pfn;
        order++;
    }
done_merging:
    set_buddy_order(page, order);
    to_tail = buddy_merge_likely(pfn, buddy_pfn, page, order);
    add_to_free_list(page, zone, order, migratetype);
}

__find_buddy_pfn(pfn, order) {
    return pfn ^ (1 << order);
}

参考资料

• 《深入理解Linux内核（第三版）》
• Linux Kernel源码分析