内存分配之快速路径和慢速路径源码学习

文摘   2024-09-12 14:44   陕西  

作者简介: 高怡香,西安邮电大学计算机专业研二学生,导师陈莉君教授,热衷于探索linux内核。

页面分配

分配物理页面涉及到页面回收、内存规整、直接回收内存等,这里分析在内存充足下的快速路径分配以及内存不充足的情况下的慢速路径分配。

总体的函数调用框图如图所示:

预备知识

一、分配物理页面的接口函数

内核中分配物理页面的常用接口函数是alloc_pages(),它用于分配一个或多个连续的物理页面,并且分配的页面个数必须是2的整数次幂。

1.1 分配物理页面的核心接口函数

分配物理页面的核心接口函数有alloc_pages() 和 __get_free_pages(),下面详细介绍这两个函数。

1.1.1 alloc_pages()

include/linux/gfp.h中定义了alloc_pages 函数,内容如下:

/**
 * @brief 分配2的order次幂个连续的物理页面
 *
 * @param gfp_mask 分配掩码,描述页面分配方法的标志
 * @param order 分配页面的阶数,order必须小于MAX_ORDER
 * @return 返回第一个物理页面的 page 数据结构.
*/

#define alloc_pages(gfp_mask, order) \
  alloc_pages_node(numa_node_id(), gfp_mask, order)

alloc_pages() 函数的作用是分配2的order次幂个连续的物理页面,并返回第一个物理页面的 page 数据结构。

该函数的第一个参数为 gfp_mask ,是分配掩码,描述页面分配方法的标志;第二个参数是order,即阶数。

1.1.2 __get_free_pages()

/*
 * __get_free_pages 不会使用高端内存,因此不会与 __GFP_HIGHMEM 一起用。如果一定要使用高端内存,可通过alloc_pages()函数以及kmap()函数
 * 高端内存只实现在32位处理器中
 */


/**
 * @brief 分配2的order次幂个连续的物理页面
 *
 * @param gfp_mask 分配掩码,描述页面分配方法的标志
 * @param order 分配页面的阶数,order必须小于MAX_ORDER
 * @return 返回所分配内存的内核空间虚拟地址
*/

unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
{
 struct page *page;
 // __get_free_pages() 函数最终通过调用 alloc_pages() 来实现分配页面,但注意在这里,gfp_mask 是经过修正的
 page = alloc_pages(gfp_mask & ~__GFP_HIGHMEM, order);
 if (!page)
  return 0;
 //如果分配成功,则调用 page_address() 将第一个 page结构体对应的页面虚拟地址强转化为 unsigned long类型,并返回这个地址
 return (unsigned long) page_address(page);
}

1.1.3 分配一个物理页面

如果仅仅只需要分配一个物理页面的话,可以采用如下接口函数

alloc_page()

#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

alloc_page最终调用的是alloc_pages(),并且 order = 0。代表分配2的0次的页面,即一个页面

__get_free_page()

#define __get_free_page(gfp_mask) \
  __get_free_pages((gfp_mask), 0)

__get_free_page() 调用了 __get_free_pages()函数,而这个函数在修正 gfp_mask之后,也会调用alloc_pages() ,且 order=0

get_zeroed_page()

/**
 * @brief 分配一个全填充为0 的物理页面
 *
 * @param gfp_mask 分配掩码,描述页面分配方法的标志
 * @return 返回所分配内存的内核空间虚拟地址
*/
unsigned long get_zeroed_page(gfp_t gfp_mask)
{
 return __get_free_pages(gfp_mask | __GFP_ZERO, 0);
}

get_zeroed_page() 函数内部通过调用 __get_free_pages(), 设置阶数order = 0,且添加 __GFP_ZERO修饰符到 gfp_mask中,来确保返回一个填充为0的物理页面

1.2 页面释放函数

页面释放函数主要有__free_pages()__free_page()free_pages()free_page()在使用释放函数的时候要特别注意,要传递正确的 page指针以及order值,否则会引起系统崩溃。

__free_pages()

/**
 * @brief 释放连续的物理页面
 *
 * @param page 待释放页面的 page 指针。
 * @param order 待释放页面的数量
*/

void __free_pages(struct page *page, unsigned int order)
{
 //检查页面的引用计数是否为0,若为0,则表示页面没有被使用,则释放
 if (put_page_testzero(page))
  free_the_page(page, order);
}

__free_page()

//__free_page() 通过调用 __free_pages() 来释放 page 指向的 1个页面,
#define __free_page(page) __free_pages((page), 0)

free_pages()

/**
 * @brief 释放连续的物理页面
 *
 * @param addr 待释放页面的起始虚拟地址
 * @param order 待释放页面的数量
*/

void free_pages(unsigned long addr, unsigned int order)
{
 //确保该虚拟地址不为0 
 if (addr != 0) {
  //virt_addr_valid() 检查该地址有效,如果无效,则通过VM_BUG_ON() 触发一个错误。
  VM_BUG_ON(!virt_addr_valid((void *)addr));
  //最终通过调用virt_to_page()将虚拟地址转为对应的page结构,然后调用 __free_pages() 来释放
  __free_pages(virt_to_page((void *)addr), order);
 }
}

free_page()

//free_page() -> free_pages() -> __free_pages()
#define free_page(addr) free_pages((addr), 0)

二、分配掩码 gfp_mask

分配掩码是描述页面分配方法的标志,影响整个页面分配的流程,其定义在 include/linux/gfp.h中。其大概被分为几类:

  • 内存管理区修饰符:表示应当从哪些内存管理区中分配物理内存,使用gfp_mask的低4位表示

    标 志描 述
    __GFP_DMA从ZONE_DMA中分配内存
    __GFP_DMA32从ZONE_DMA32中分配内存
    __GFP_HIGHMEM优先从ZONE HIGHMEM中分配内存
    __GFP_MOVABLE页面可以被迁移或者回收,如用于内存规整机制
  • 移动修饰符:用于指示分配出来的页面的迁移属性

    标 志描 述
    __GFP_RECLAIMABLE在slab分配器中指定了SLABRECLAIMACCOUNT标志位,表示slab分配器中使 用的页面可以通过收割机来回收
    __GFP_HARDWALL使能cpuset 内存分配策略
    __GFP_THISNODE从指定的内存节点中分配内存,并且没有回退机制
    __GFP_ACCOUNT分配过程会被kmemcg记录
  • 水位修饰符:用于控制是否可以访问系统预留的内存(最低警戒线水位以下的内存)

    标 志描 述
    __GFP_HIGH表示分配内存具有高优先级,并且这个分配请求是很有必要的,分配器可以使用系统预留的内存(即最低警戒水位线下的预留内存)
    __GFP_ATOMIC表示分配内存的过程不能执行页面回收或者 睡眠动作,并且具有很高的优先级,可以访问系统预留的内存。常见的一个场景是在 中断上下文中分配内存
    __GFP_MEMALLOC分配过程中允许访问所有的内存,包括系统预留的内存。分配内存进程通常要保证在分配内存过程中很快会有内存被释放,如进程退出或者页面回收
    __GFP_NOMEMALLOC分配过程不允许访问系统预留的内存
  • 页面回收修饰符

    标 志描 述
    __GFP_IO允许开启I/O传输
    __GFP_FS允许调用底层的文件系统。这个标志清零通常是为了避免死锁的发生,如果相应的文件系统操作路径上已经持有了锁,分配内存过程又递归地调用这个文件系统的相应操 作路径,可能会产生死锁
    __GFP_DIRECT_RECLAIM分配内存的过程中允许使用页面直接回收机制
    __GFP_KSWAPD_RECLAIM表示当到达内存管理区的低水位时会唤醒kswapd内核线程,以异步地回收内存,直到内存管理区恢复到了高水位为止
    __GFP_RECLAIM用于允许或者禁止直接页面回收和kswapd内核线程
    __GFP_REPEAT当分配失败时会继续尝试
    __GFP_NOFAIL当分配失败时会无限地尝试下去,直到分配成功为止。当分配者希望分配内存不失败时, 应该使用这个标志位,而不是自己写一个while循环来不断地调用页面分配接口函数
  • 行为修饰符

    标志描述
    __GFP_COLD分配的内存不会马上被使用。通常会返回一个空的高速缓存页面
    __GFP_NOWARN关闭分配过程中的一些错误报告
    __GFP_ZERO返回一个全部填充为0的页面
    __GFP_NOTRACK不被kmemcheck机制跟踪
    __GFP_OTHER_NODE在远端的一个内存节点上分配。通 常在khugepaged内核线程中使用
  • 常用标志组合

标志描述
GFP_KERNEL内核分配内存常用的标志之一。它可能会被阻塞,即分配过程中可能会睡眠
GFP_ATOMIC调用者不能睡眠并且保证分配会成功。它可以访问系统预留的内存
GFP_NOWAIT分配中不允许睡眠等待
GFP_NOFS不会访问任何的文件系统的接口和操作
GFP_NOIO不需要启动任何的I/O操作。如使用直接回收机制丢弃干净的页面或者为slab分配的页面
GFP_USER通常用户空间的进程用来分配内存,这些内存可以被内核或者硬件使用。常用的一个场景是硬件使用的DMA缓冲器要映射到用户空间,如显卡的缓冲器
GFP_HIGHUSER用户空间进程用来分配内存,优先使用ZONE_HIGHMEM,这些内存可以映射到用户空间,内核空间不会直接访问这些内存。另外,这些内存不能迁移
GFP_HIGHUSER MOVABLE类似于GFP_HIGHUSER,但是页面可以迁移
GFP_DMA/GFP_DMA32使用ZONE DMA或者ZONE_DMA32来分配内存
GFP_TRANSHUGE/GFP_TRANSHUGE_LIGHT通常用于透明页面分配

快速路径分配

三、详解alloc_pages()

3.1 分析调用关系

//调用关系:alloc->pages()--> alloc_pages_node()
                              
#define alloc_pages(gfp_mask, order) \
  alloc_pages_node(numa_node_id(), gfp_mask, order)



 //调用关系:alloc_pages_node()--> __alloc_pages_node()                                                               
 static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
      unsigned int order)

{
 if (nid == NUMA_NO_NODE)
  nid = numa_mem_id();

 return __alloc_pages_node(nid, gfp_mask, order);
}
//调用关系:__alloc_pages_node()--> __alloc_pages()  
static inline struct page *  __alloc_pages_node(int nidgfp_t gfp_maskunsigned int order)
{

 VM_BUG_ON(nid < 0 || nid >= MAX_NUMNODES);
 VM_WARN_ON((gfp_mask & __GFP_THISNODE) && !node_online(nid));

 return __alloc_pages(gfp_mask, order, nid);
}    
//调用关系:__alloc_pages()--> __alloc_pages_nodemask()  
static inline struct page *
__alloc_pages(gfp_t gfp_maskunsigned int orderint preferred_nid)
{

 return __alloc_pages_nodemask(gfp_mask, order, preferred_nid, NULL);
}
//由此看出,alloc_pages()最终调用的是__alloc_pages_nodemask()函数

3.2 __alloc_pages_nodemask()

/*
 * __alloc_pages_nodemask() 函数是伙伴系统的核心函数
 */

struct page *
__alloc_pages_nodemask(gfp_t gfp_maskunsigned int orderint preferred_nid,
       nodemask_t *nodemask)
{

 struct page *page;

 //alloc_flags 用于表示页面分配的行为和属性,这里初始化值表示分配内存的判断条件为低水位
 unsigned int alloc_flags = ALLOC_WMARK_LOW;
 gfp_t alloc_mask; /* The gfp_t that was actually used for allocation */
 struct alloc_context ac = { };

  //这里表示order最多为10,因为MAX_ORDER=11,则分配最多不内存块为2^10 * 4KB = 4MB
 if (unlikely(order >= MAX_ORDER)) {
  WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
  return NULL;
 }

 gfp_mask &= gfp_allowed_mask;
 alloc_mask = gfp_mask;

 //prepare_alloc_pages()函数会计算相关信息保存到ac
    //ac类型为alloc_context,这个数据结构体是伙伴系统分配函数中用于保存相关的参数
 if (!prepare_alloc_pages(gfp_mask, order, preferred_nid, nodemask, &ac, &alloc_mask, &alloc_flags))
  return NULL;

 //finalise_ac()函数确定首选的zone
 finalise_ac(gfp_mask, &ac);

 //alloc_flags_nofragment() 是用于内存碎片化方面的一个优化
 alloc_flags |= alloc_flags_nofragment(ac.preferred_zoneref->zone, gfp_mask);

 /* 第一次尝试分配,从伙伴系统的空闲链表中分配内存 */
 page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);

 //若分配成功,则返回内存块的第一个页面的page数据结构
 if (likely(page))
  goto out;

 alloc_mask = current_gfp_context(gfp_mask);
 ac.spread_dirty_pages = false;

 if (unlikely(ac.nodemask != nodemask))
  ac.nodemask = nodemask;
 //若分配不成功,则最终调用__alloc_pages_slowpath()进入分配的慢速路径
 page = __alloc_pages_slowpath(alloc_mask, order, &ac);

out:
 if (memcg_kmem_enabled() && (gfp_mask & __GFP_ACCOUNT) && page &&
     unlikely(__memcg_kmem_charge(page, gfp_mask, order) != 0)) {
  __free_pages(page, order);
  page = NULL;
 }

 trace_mm_page_alloc(page, order, alloc_mask, ac.migratetype);

 return page;
}

3.3 相关数据结构

alloc_context 数据结构:

// alloc_context结构体是一个内部临时使用的结构体
struct alloc_context {
 struct zonelist *zonelist;    //指向每一个内存节点中对应的zonelist
 nodemask_t *nodemask;    //表示内存节点掩码
 struct zoneref *preferred_zoneref; //表示首选的zone的zoneref
 int migratetype;     //表示迁移类型
 enum zone_type high_zoneidx;  //分配掩码计算zone的zoneidx,即允许内存分配的最高的zone
 bool spread_dirty_pages;   //表示是否允许传播脏页
};

zonelist结构体是内核管理一个内存节点zone的数据结构,定义如下:

struct zonelist {
 struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
};

再看看 struct zoneref的定义:

//每个zoneref描述一个zone
struct zoneref {
 struct zone *zone; /* 指向真实的zone */
 int zone_idx;  /* 根据zone_idx函数获取的idx ,0表示最低*/
};

zonelist是所有可用的zone的链表,其中排在第一个的zone是首选zone,通常一个内存节点有两个zonelist,一个本地(包含备选zone),一个远端(用于NUMA系统,指向远端的内存节点zone)

zonelist在初始化的时候通过build_zonelists函数建立。遍历zonelist的宏有如下:

 first_zones_zonelist()
 for_each_zone_zonelist_nodemask ()
 for_next_zone_zonelist_nodemask ()

3.4 prepare_alloc_pages()

这个函数主要是用于初始化页面分配器中用到的参数,这些参数会临时保存到 alloc_context 数据结构

static inline bool prepare_alloc_pages(gfp_t gfp_mask, unsigned int order,
  int preferred_nid, nodemask_t *nodemask,
  struct alloc_context *ac, gfp_t *alloc_mask,
  unsigned int *alloc_flags)

{
 //gfp_zone() 根据分配掩码计算zone的zoneidx,存放在ac结构体的high_zoneidx
 ac->high_zoneidx = gfp_zone(gfp_mask);
 //node_zonelist() 函数返回首选内存节点preferred_nid对应的zonelist。通常一个内存节点有两个zonelist,一个本地,一个远端
 ac->zonelist = node_zonelist(preferred_nid, gfp_mask);
 ac->nodemask = nodemask;
 //gfpflags_to_migratetype()根据分配掩码来获取内存的迁移类型
 ac->migratetype = gfpflags_to_migratetype(gfp_mask);

 if (cpusets_enabled()) {
  *alloc_mask |= __GFP_HARDWALL;
  if (!ac->nodemask)
   ac->nodemask = &cpuset_current_mems_allowed;
  else
   *alloc_flags |= ALLOC_CPUSET;
 }

 fs_reclaim_acquire(gfp_mask);
 fs_reclaim_release(gfp_mask);

 might_sleep_if(gfp_mask & __GFP_DIRECT_RECLAIM);

 if (should_fail_alloc_page(gfp_mask, order))
  return false;

 if (IS_ENABLED(CONFIG_CMA) && ac->migratetype == MIGRATE_MOVABLE)
  *alloc_flags |= ALLOC_CMA;

 return true;
}

四、get_page_from_freelist()

get_page_from_freelist() 函数的主要作用是从伙伴系统的空闲页面链表中尝试分配物理页面。

4.1 代码分析

/*
 * get_page_from_freelist() 主要作用是从伙伴系统的空闲页面链表中尝试分配物理页面
 */

static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
      const struct alloc_context *ac)

{
 struct zoneref *z;
 struct zone *zone;
 struct pglist_data *last_pgdat_dirty_limit = NULL;
 bool no_fallback;

retry:
 
 //ALLOC_NOFRAGMENT 是新增的标志,表示需要避免内存碎片化
 no_fallback = alloc_flags & ALLOC_NOFRAGMENT;
 //preferred_zoneref 是表示首选推荐的zone,在finalise_ac() 中计算出的
 z = ac->preferred_zoneref;
 //从给定的首选推荐zone,开始遍历 zonelist 所有zone,遍历的时候是从高端zone到低端zone进行遍历的
 for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
        ac->nodemask) {
  struct page *page;
  unsigned long mark;

  if (cpusets_enabled() &&
   (alloc_flags & ALLOC_CPUSET) &&
   !__cpuset_zone_allowed(zone, gfp_mask))
    continue;

  if (ac->spread_dirty_pages) {
   if (last_pgdat_dirty_limit == zone->zone_pgdat)
    continue;

   if (!node_dirty_ok(zone->zone_pgdat)) {
    last_pgdat_dirty_limit = zone->zone_pgdat;
    continue;
   }
  }

  //当要分配的内存的zone不在本地内存节点,而是在远端内存节点,则要考虑内存的本地性
  if (no_fallback && nr_online_nodes > 1 &&
      zone != ac->preferred_zoneref->zone) {
   int local_nid;

   local_nid = zone_to_nid(ac->preferred_zoneref->zone);
   if (zone_to_nid(zone) != local_nid) {
    alloc_flags &= ~ALLOC_NOFRAGMENT;
    goto retry;
   }
  }
  // wmark_pages() 宏用来计算zone中某个水位的页面大小。
  mark = wmark_pages(zone, alloc_flags & ALLOC_WMARK_MASK);

  //zone_watermark_fast() 函数用于判断当前zone的空闲页面是否满足WMARK_LOW。另外还会根据order来判断是否有足够大的空闲内存块,若返回true,则代表zone的页面高于指定的水位或满足order分配需求
  if (!zone_watermark_fast(zone, order, mark,
           ac_classzone_idx(ac), alloc_flags)) {

   //处理当前zone不满足内存分配需求的情况
   int ret;

#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
  
   if (static_branch_unlikely(&deferred_pages)) {
    if (_deferred_grow_zone(zone, order))
     goto try_this_zone;
   }
#endif
   /* Checked here to keep the fast path fast */
   BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
   if (alloc_flags & ALLOC_NO_WATERMARKS)
    goto try_this_zone;

   //node_claim_mode = 0 ,表示可以从下一个zone或者内存节点中分配内存,否则表示可以在这个zone进行内存回收等
   if (node_reclaim_mode == 0 ||
       !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
    continue;
   //node_reclaim() 函数可以尝试回收一部分内存
   ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
   switch (ret) {
   case NODE_RECLAIM_NOSCAN:
    /* did not scan */
    continue;
   case NODE_RECLAIM_FULL:
    /* scanned but unreclaimable */
    continue;
   default:
    /* did we reclaim enough */
    if (zone_watermark_ok(zone, order, mark,
      ac_classzone_idx(ac), alloc_flags))
     goto try_this_zone;

    continue;
   }
  }
//表示马上要从这个zone中分配内存
try_this_zone:
  //rmqueue() 函数表示会从伙伴系统中分配内存,此函数是伙伴系统的核心分配函数
  page = rmqueue(ac->preferred_zoneref->zone, zone, order,
    gfp_mask, alloc_flags, ac->migratetype);

  //成功分配页面之后,进行设置相关属性以及做一些必要的检查,最终返回成功分配的页面page数据结构
  if (page) {
   prep_new_page(page, order, gfp_mask, alloc_flags);

   if (unlikely(order && (alloc_flags & ALLOC_HARDER)))
    reserve_highatomic_pageblock(page, zone, order);

   return page;
  } else {
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
   /* Try again if zone has deferred pages */
   if (static_branch_unlikely(&deferred_pages)) {
    if (_deferred_grow_zone(zone, order))
     goto try_this_zone;
   }
#endif
  }
 }

 //当遍历完zonelist中所有zone, 都没有分配所需要的内存,则判断有可能发生了外碎片化,此时可以重新尝试一次
 if (no_fallback) {
  alloc_flags &= ~ALLOC_NOFRAGMENT;
  goto retry;
 }

 return NULL;
}

4.2 zone_watermark_fast()

/**
 * @brief  zone_watermark_fast() 用于测试当前zone的水位情况以及判断是否满足多个页面的分配请求
 * @param z 表示检查是否满足请求的zone
 * @param order 表示分配2^order个物理页面
 * @param mark 表示要测试的水位标准
 * @param classzone_idx 表示首选的zone
 * @param alloc_flags 分配器内部使用的标志位属性
 */

static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
  unsigned long mark, int classzone_idx, unsigned int alloc_flags)

{
 //zone里面有一个关于物理页面统计数据的数组vm_stat[],这个数组存放了该zone中各种页面的统计数据,包含 NR_FREE_PAGES 等
 //zone_page_stat() 函数用于获取zone中空闲页面的数量
 long free_pages = zone_page_state(z, NR_FREE_PAGES);
 long cma_pages = 0;

#ifdef CONFIG_CMA
 /* If allocation can't use CMA areas don't use free CMA pages */
 if (!(alloc_flags & ALLOC_CMA))
  cma_pages = zone_page_state(z, NR_FREE_CMA_PAGES);
#endif

 //针对分配一个页面所作的快速处理。lowmem_reserve 是每个zone 预留的内存,为了防止高端zone在没有内存的情况下过度使用低端zone的内存资源
 if (!order && (free_pages - cma_pages) > mark + z->lowmem_reserve[classzone_idx])
  return true;
 //调用__zone_watermark_ok() 进一步检查空闲页面
 return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
     free_pages);
}

基于上面对alloc_pages以及get_page_freelist的分析,得知伙伴系统分配内存时,会先以low水线为基准调用get_page_from_freelist函数尝试进行内存分配,如果失败则会进入慢速内存分配流程,即__alloc_pages_slowpath函数,这个函数会尝试唤醒kswapd进行内存回收。这个过程就是内存规整的直接规整

五、rmqueue()

rmqueue() 函数会从伙伴系统中获取内存,若所需的内存块不够大,则会从更大的内存块中切内存。

5.1 预备知识

struct zone {
    struct per_cpu_pageset __percpu *pageset;
    ...
}
struct per_cpu_pages {
 int count;  /* 链表中页面的数量 */
 int high;  /* 缓存页面高于 high 水位,则回收页面到伙伴系统中 */
 int batch;  /* 每一次回收到伙伴系统的页面数量 */

 /* 页面链表,分成多个迁移类型 */
 struct list_head lists[MIGRATE_PCPTYPES];
};

struct per_cpu_pageset {
 struct per_cpu_pages pcp;
 ...
};

5.2 rmqueue()

/**
 * @brief 从指定的zone中分配内存
 * @param perferred_zone 首选的zone
 * @param zone 当前遍历的zone
 * @param order 分配2^order个连续的物理页面
 * @param gfp_flags 调用者传递过来的分配掩码
 * @param alloc_flags 页面分配器内部使用的标志位
 * @param migratetype 分配内存的迁移类型
 * @return 当分配成功时,返回内存块第一个物理页面的page数据结构
 * 
 * 
 */


static inline
struct page *rmqueue(struct zone *preferred_zone,
   struct zone *zone, unsigned int order,
   gfp_t gfp_flags, unsigned int alloc_flags,
   int migratetype)

{
 unsigned long flags;
 struct page *page;
 //处理分配一个物理页面的情况
 if (likely(order == 0)) {
  //调用rmqueue_pcplist()函数,从Per-CPU 变量 per_cpu_pages中分配物理页面。
  //Per-CPU 变量 per_cpu_pages 表示每个CPU 都有个本地的变量 per_cpu_pages。这个数据结构中有个单页面链表,里面存放了一小部分单个的物理页面。
  page = rmqueue_pcplist(preferred_zone, zone, gfp_flags,
     migratetype, alloc_flags);
  goto out;
 }

 //处理order>0的情况
 WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
 //申请自旋锁 zone->lock 来保护 zone 中的伙伴系统
 spin_lock_irqsave(&zone->lock, flags);
 //do-while 循环调用 __rmqueue() 分配内存
 do {
  page = NULL;
  if (alloc_flags & ALLOC_HARDER) {
   //调用 __rmqueue_smallest 来将大的内存块切
   page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
   if (page)
    trace_mm_page_alloc_zone_locked(page, order, migratetype);
  }
  // 如果分配不成功的话,则调用 __rmqueue() -> __rmqueue_fallback() 去伙伴系统的备份空闲链表(不同迁移类型的空闲链表)挪用内存
  if (!page)
   page = __rmqueue(zone, order, migratetype, alloc_flags);
 //分配成功之后,check_new_pages() 会去判断页面是否合格
 } while (page && check_new_pages(page, order));
 spin_unlock(&zone->lock);
 if (!page)
  goto failed;
 // 页面更新完成之后,需要去更新 zone的 NR_FREE_PAGES
 __mod_zone_freepage_state(zone, -(1 << order),
      get_pcppage_migratetype(page));

 __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
 zone_statistics(preferred_zone, zone);
 local_irq_restore(flags);

out:
 /* Separate test+clear to avoid unnecessary atomics */
 //当页面分配器触发向备份空闲链表借用内存时,说明系统有外碎片化倾向,所以设置该标志位。
 // 判断zone->flags是否设置了 ZONE_BOOSTED_WATERMARK 标志位,若该标志位置位,则将其清零
 if (test_bit(ZONE_BOOSTED_WATERMARK, &zone->flags)) {
  clear_bit(ZONE_BOOSTED_WATERMARK, &zone->flags);
  //并且唤醒 kswapd 内核线程回收内存
  wakeup_kswapd(zone, 00, zone_idx(zone));
 }
 //VM_BUG_ON_PAGE 宏需要打开CONFIG_DEBUG_VM 配置才会生效
 VM_BUG_ON_PAGE(page && bad_range(zone, page), page);
 //返回分配好的内存块中的第一个页面的page数据结构
 return page;

failed:
 local_irq_restore(flags);
 return NULL;
}

5.3 __rmqueue_smallest()

static __always_inline
struct page *__rmqueue_smallest(struct zone *zoneunsigned 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 */
 //从 order 开始查找 zone 中空闲的链表,如果zone对应的空闲链表中相应迁移类型的链表中没有空闲对象,通过Continue直接进入下一次循环,即 order+1 则查找上一级的order 对应的空闲链表
 for (current_order = order; current_order < MAX_ORDER; ++current_order) {
  area = &(zone->free_area[current_order]);
  //如果找到某个order的空闲链表中对应的类型有空闲块,则通过 expand() 来分配
  page = get_page_from_free_area(area, migratetype);
  if (!page)
   continue;
  del_page_from_free_area(page, area);
  //expand() 函数用于实现分配功能,current_order就是当前内存块对应的order,一般比order大
  expand(zone, page, order, current_order, area, migratetype);
  set_pcppage_migratetype(page, migratetype);
  return page;
 }

 return NULL;
}

慢速路径分配

六、__alloc_pages_slowpath()

/**
 * @brief 在低水位之下,alloc_pages() 进入慢速路径分配页面
 *
 * @param gfp_mask 调用页面分配器传递的分配掩码,描述页面分配方法的标志
 * @param order 分配页面的大小,order必须小于MAX_ORDER
 * @param ac 表示页面分配器内使用的控制分配参数的数据结构
*/

static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_maskunsigned int order,
      struct alloc_context *ac)
{

 //can_direct_reclaim 表示允许直接内存回收,分配掩码中隐含 __GFP_DIRECT_RECLAIM 标志的都可以进行直接内存回收
 bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;
 //costly_order表示形成的内存分配压力。PAGE_ALLOC_COSTLY_ORDER = 3,当要分配的阶数为4,即分配64KB的页面,会给页面分配器形成一定的内存压力
 const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
 struct page *page = NULL;
 unsigned int alloc_flags;
 unsigned long did_some_progress;
 enum compact_priority compact_priority;
 enum compact_result compact_result;
 int compaction_retries;
 int no_progress_loops;
 unsigned int cpuset_mems_cookie;
 int reserve_flags;

 /*
  * 检查是否在非中断上下文中滥用了__GFP_ATOMIC,使用__GFP_ATOMIC 会输出一次警告。如果是,则移除__GFP_ATOMIC标志
  * 这个标志表示调用页面分配器的进程不能直接回收页面或等待,调用者通常在中断上下文中。这个表示 优先级 较高,允许访问部分的系统预留内存
  */

 if (WARN_ON_ONCE((gfp_mask & (__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)) ==
    (__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)))
  gfp_mask &= ~__GFP_ATOMIC;

retry_cpuset:
 compaction_retries = 0;
 no_progress_loops = 0;
 compact_priority = DEF_COMPACT_PRIORITY;
 cpuset_mems_cookie = read_mems_allowed_begin();

 //gfp_to_alloc_flags() 重新设置分配掩码 alloc_flags
 alloc_flags = gfp_to_alloc_flags(gfp_mask);


 //重新设置首选zone,因为我们可能在快速路径中使用了不同的 nodemask,或者 cpuset 发生了修改,我们需要重试
 ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
     ac->high_zoneidx, ac->nodemask);
 if (!ac->preferred_zoneref->zone)
  goto nopage;

 //尝试唤醒kswapd进行内存回收
 if (alloc_flags & ALLOC_KSWAPD)
  wake_all_kswapds(order, gfp_mask, ac);

 /*
  *alloc_flags通过 gfp_to_alloc_flags() 被重新设置,后面唤醒内核线程kswapds进行内存回收,可能会出现合适的内存块,满足分配要求,因此再次尝试 get_page_from_freelist() 分配内存,注意 : 这次使用的是 min 水线
  */

 page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);

 //如果分配成功,直接返回内存块的第一个page
 if (page)
  goto got_pg;

 /* 如果上述在最低警戒水位条件下分配页面失败,在3种情况下可以考虑尝试先调用直接内存规整机制来解决页面分配失败的问题
  * 1.允许调用直接页面回收机制
  * 2.高成本的分配需求 costly_order,此时,系统可能有足够的空闲内存,但没有分配满足分配需求的连续页面,调用内存规整机制可能解决这个问题。或者对于请求,分配可迁移的多个连续物理页面
  * 3.不能访问系统预留内存 gfp_pfmemalloc_allowed() 表示是否允许访问系统预留内存。返回 0 则表示不允许访问预留内存,返回ALLOC_NO_WATERMARKS 表示不用考虑水位,访问全部的预留内存。
  *  当同时满足上面三条,就会调用 __alloc_pages_direct_compact() 进行内存规整。
  * 
  */

 if (can_direct_reclaim &&
   (costly_order ||
      (order > 0 && ac->migratetype != MIGRATE_MOVABLE))
   && !gfp_pfmemalloc_allowed(gfp_mask)) {

  //进行直接内存规整,优先级设置为INIT_COMPACT_PRIORITY,优先级越低,其规整强度越高
  page = __alloc_pages_direct_compact(gfp_mask, order,
      alloc_flags, ac,
      INIT_COMPACT_PRIORITY,
      &compact_result);
  if (page)
   goto got_pg;
  //如果分配依然失败,最终会进入 nopage ,在 nopage 执行中进入 retry,重新尝试唤醒kswapd、get_page_from_freelist、__alloc_pages_direct_reclaim 、__alloc_pages_direct_compact循环调用
   if (order >= pageblock_order && (gfp_mask & __GFP_IO) &&
       !(gfp_mask & __GFP_RETRY_MAYFAIL)) {
  
   if (compact_result == COMPACT_SKIPPED ||
       compact_result == COMPACT_DEFERRED)
    goto nopage;
  }

  if (costly_order && (gfp_mask & __GFP_NORETRY)) {
 
   if (compact_result == COMPACT_DEFERRED)
    goto nopage;

  
   compact_priority = INIT_COMPACT_PRIORITY;
  }
 }

retry:
 /* Ensure kswapd doesn't accidentally go to sleep as long as we loop */
 //1.唤醒 kswapd
 if (alloc_flags & ALLOC_KSWAPD)
  wake_all_kswapds(order, gfp_mask, ac);
 //__gfp_pfmemalloc_flags() 判断是否允许访问系统全部的预留内存。返回0,则不允许访问预留内存
 reserve_flags = __gfp_pfmemalloc_flags(gfp_mask);
 if (reserve_flags)
  alloc_flags = reserve_flags;

 if (!(alloc_flags & ALLOC_CPUSET) || reserve_flags) {
  ac->nodemask = NULL;
  ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
     ac->high_zoneidx, ac->nodemask);
 }

 /* Attempt with potentially adjusted zonelist and alloc_flags */
 //2.重新调用 get_page_from_freelist()分配页面,若成功,则返回 退出
 page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
 if (page)
  goto got_pg;

 /*若调用者不支持直接内存回收,则不能进行直接内存规整,跳转到 nopage*/
 if (!can_direct_reclaim)
  goto nopage;

 /* 若当前进程设置了PF_MEMALLOC,则表示可以访问全部的系统预留内存,则在进行get_page_from_freelist()分配页面的时候是不考虑水位的,既然这样都分配不成功,则跳转到 nopage */
 if (current->flags & PF_MEMALLOC)
  goto nopage;

 /* Try direct reclaim and then allocating */
 //3.调用 __alloc_pages_direct_reclaim() 进行直接内存回收,分配内存
 page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags, ac,
       &did_some_progress);
 if (page)
  goto got_pg;

 /* Try direct compaction and then allocating */
 //4. 如果直接内存回收之后没有分配到内存,则进行直接内存规整,即调用 __alloc_pages_direct_compact() 分配内存
 page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,
     compact_priority, &compact_result);
 if (page)
  goto got_pg;

 /*在进行一些列操作:内存回收、最低警戒线、内存规整都没分配成功。如果gfp_mask 设置了__GFP_NORETRY标志不允许重试,则跳转到 nopage */
 if (gfp_mask & __GFP_NORETRY)
  goto nopage;

 /*
  * 要分配大块的物理内存,并且 gfp_mask 没设置 __GFP_RETRY_MAYFAIL,说明不允许重试,则跳转到 nopage
  */

 if (costly_order && !(gfp_mask & __GFP_RETRY_MAYFAIL))
  goto nopage;
 //should_reclaim_retry() 判断是否需要重试直接页面回收机制,返回非0,则需要重试
 // did_some_progress 表示在直接内存规整中返回的已经成功回收的页面数量
 //no_progress_loops 表示没有进展的重试。对于大order的页面分配请求,虽然我们回收了一些页面,但由于碎片化严重等不足满足分配的需求,所以增加 no_progress_loops
 if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,
     did_some_progress > 0, &no_progress_loops))
  goto retry;


 //should_compact_retry() 判断是否需要重试内存规整
 if (did_some_progress > 0 &&
   should_compact_retry(ac, order, alloc_flags,
    compact_result, &compact_priority,
    &compaction_retries))
  goto retry;


 /* check_retry_cpuset() 判断是否需要尝试新的 cpuset ,这个需要使能 CONFIG_CPUSETS 功能 */
 if (check_retry_cpuset(cpuset_mems_cookie, ac))
  goto retry_cpuset;

 /* 如果所有的cpuset重新尝试之后,还没分配所需的内存,则使用OOM机制*/

 //__alloc_pages_may_oom() 终止占用内存较多的进程,从而释放内存
 page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);
 if (page)
  goto got_pg;

 /* 如果被终止的进程是当前进程且 alloc_flags 设置ALLOC_OOM或者gfp_mask设置 __GFP_NOMEMALLOC,跳转到 nopage*/
 if (tsk_is_oom_victim(current) &&
     (alloc_flags == ALLOC_OOM ||
      (gfp_mask & __GFP_NOMEMALLOC)))
  goto nopage;

 /* 在终止进程后释放了内存,因此跳转到retry重新分配内存 */
 if (did_some_progress) {
  no_progress_loops = 0;
  goto retry;
 }

nopage:
 /* Deal with possible cpuset update races before we fail */
 if (check_retry_cpuset(cpuset_mems_cookie, ac))
  goto retry_cpuset;


 // 若分配掩码设置 __GFP_NOFAIL,则分配不能失败,必须再尝试重新分配
 if (gfp_mask & __GFP_NOFAIL) {

  if (WARN_ON_ONCE(!can_direct_reclaim))
   goto fail;


  WARN_ON_ONCE(current->flags & PF_MEMALLOC);

  WARN_ON_ONCE(order > PAGE_ALLOC_COSTLY_ORDER);

  //首先调用__alloc_pages_cpuset_fallback () 尝试分配,若还没办法分配,则跳转到 retry
  page = __alloc_pages_cpuset_fallback(gfp_mask, order, ALLOC_HARDER, ac);
  if (page)
   goto got_pg;

  cond_resched();
  goto retry;
 }
 //若分配掩码没有设置 __GFP_NOFAIL,直接调用 warn_alloc 宣告失败
fail:
 warn_alloc(gfp_mask, ac->nodemask,
   "page allocation failure: order:%u", order);
got_pg:
 return page;
}

释放页面

七、释放页面

7.1 调用关系

释放页面的核心函数是free_page(),代码如下:

//__free_page() 通过调用 __free_pages() 来释放 page 指向的 1个页面,
#define __free_page(page) __free_pages((page), 0)
//free_page() -> free_pages() -> __free_pages()
#define free_page(addr) free_pages((addr), 0)


/**
 * @brief 释放连续的物理页面
 *
 * @param addr 待释放页面的起始虚拟地址
 * @param order 待释放页面的数量
*/

void free_pages(unsigned long addr, unsigned int order)
{
 //确保该虚拟地址不为0 
 if (addr != 0) {
  //virt_addr_valid() 检查该地址有效,如果无效,则通过VM_BUG_ON() 触发一个错误。
  VM_BUG_ON(!virt_addr_valid((void *)addr));
  //最终通过调用virt_to_page()将虚拟地址转为对应的page结构,然后调用 __free_pages() 来释放
  __free_pages(virt_to_page((void *)addr), order);
 }
}

可以看出来,free_page()、__free_page()函数最终调用的函数是__free_pages() -> free_the_page()

/**
 * @brief 释放连续的物理页面
 *
 * @param page 待释放页面的 page 指针。
 * @param order 待释放页面的数量
*/

void __free_pages(struct page *page, unsigned int order)
{
 //检查页面的引用计数是否为0,若为0,则表示页面没有被使用,则释放
 if (put_page_testzero(page))
  free_the_page(page, order);
}

static inline void free_the_page(struct page *page, unsigned int order)
{
 if (order == 0)  /* Via pcp? */
  free_unref_page(page);//释放单个页面
 else
  __free_pages_ok(page, order);//释放多个页面
}

7.2 释放单个页面

/*
 * 释放单个页面
 */

void free_unref_page(struct page *page)
{
 unsigned long flags;
 //使用 page_to_pfn() 宏将 page 数据结构转为页帧号
 unsigned long pfn = page_to_pfn(page);
 //free_unref_page_prepare() 对待释放页面做一些检查
 if (!free_unref_page_prepare(page, pfn))
  return;
 //关中断是因为不想在是释放页面的时候,有中断发生,因为中断可能会导致触发另外一个页面的分配,从而使得本地 pcp 链表结构可能会错乱
 local_irq_save(flags);
 //释放单个页面到 pcp 链表中
 free_unref_page_commit(page, pfn);
 local_irq_restore(flags);
}

7.3 释放多个页面

//释放多个页面
static void __free_pages_ok(struct page *page, unsigned int order)
{
 unsigned long flags;
 int migratetype;
 //将page数据结构通过宏转为页帧号
 unsigned long pfn = page_to_pfn(page);
 //对待释放页面做一些检查
 if (!free_pages_prepare(page, order, true))
  return;

 migratetype = get_pfnblock_migratetype(page, pfn);
 //关中断
 local_irq_save(flags);
 __count_vm_events(PGFREE, 1 << order);
 //最终调用的是 __free_one_page() 释放内存页面到伙伴系统,并且处理一些空闲页面的合并工作
 free_one_page(page_zone(page), page, pfn, order, migratetype);
 local_irq_restore(flags);
}

//调用关系:free_one_page() -> __free_one_page()
static void free_one_page(struct zone *zone,
    struct page *page, unsigned long pfn,
    unsigned int order,
    int migratetype)

{
 spin_lock(&zone->lock);
 if (unlikely(has_isolate_pageblock(zone) ||
  is_migrate_isolate(migratetype))) {
  migratetype = get_pfnblock_migratetype(page, pfn);
 }
 __free_one_page(page, pfn, zone, order, migratetype);
 spin_unlock(&zone->lock);
}

__free_one_page()

//合并相邻的伙伴块
static inline void __free_one_page(struct page *page,
  unsigned long pfn,
  struct zone *zone, unsigned int order,
  int migratetype)
{
 unsigned long combined_pfn;
 unsigned long uninitialized_var(buddy_pfn);
 struct page *buddy;
 unsigned int max_order;
 struct capture_control *capc = task_capc(zone);
 //计算 max_order 
 max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);

 VM_BUG_ON(!zone_is_initialized(zone));
 VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);

 VM_BUG_ON(migratetype == -1);
 if (likely(!is_migrate_isolate(migratetype)))
  __mod_zone_freepage_state(zone, 1 << order, migratetype);

 VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
 VM_BUG_ON_PAGE(bad_range(zone, page), page);

continue_merging:
 while (order < max_order - 1) {
  if (compaction_capture(capc, page, order, migratetype)) {
   __mod_zone_freepage_state(zone, -(1 << order),
        migratetype);
   return;
  }
  //计算buddy_pfn
  buddy_pfn = __find_buddy_pfn(pfn, order);
  //buddy 指向该内存块的临近内存块
  buddy = page + (buddy_pfn - pfn);

  if (!pfn_valid_within(buddy_pfn))
   goto done_merging;
   //page_is_buddy()检查内存块是不是空闲的内存块
  if (!page_is_buddy(page, buddy, order))
   goto done_merging;

  if (page_is_guard(buddy))
   clear_page_guard(zone, buddy, order, migratetype);
  else
  //取出与内存块向邻近的内存块
   del_page_from_free_area(buddy, &zone->free_area[order]);
  combined_pfn = buddy_pfn & pfn;
  page = page + (combined_pfn - pfn);
  pfn = combined_pfn;
  order++;
 }
 if (max_order < MAX_ORDER) {

  if (unlikely(has_isolate_pageblock(zone))) {
   int buddy_mt;

   buddy_pfn = __find_buddy_pfn(pfn, order);
   buddy = page + (buddy_pfn - pfn);
   buddy_mt = get_pageblock_migratetype(buddy);

   if (migratetype != buddy_mt
     && (is_migrate_isolate(migratetype) ||
      is_migrate_isolate(buddy_mt)))
    goto done_merging;
  }
  max_order++;
  goto continue_merging;
 }
//合并伙伴块
done_merging:
 set_page_order(page, order);

 if ((order < MAX_ORDER-2) && pfn_valid_within(buddy_pfn)
   && !is_shuffle_order(order)) {
  struct page *higher_page, *higher_buddy;
  combined_pfn = buddy_pfn & pfn;
  higher_page = page + (combined_pfn - pfn);
  buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
  higher_buddy = higher_page + (buddy_pfn - combined_pfn);
  if (pfn_valid_within(buddy_pfn) &&
      page_is_buddy(higher_page, higher_buddy, order + 1)) {
   add_to_free_area_tail(page, &zone->free_area[order],
           migratetype);
   return;
  }
 }

 if (is_shuffle_order(order))
  add_to_free_area_random(page, &zone->free_area[order],
    migratetype);
 else
  add_to_free_area(page, &zone->free_area[order], migratetype);

}

在本文中,我们对内存分配的快速路径和慢速路径进行了详细分析,分析了其源代码的关键部分。但由于笔者能力有限,如有纰漏,敬请指正,期待和大家共同进步!

Linux内核之旅
Linux内核之旅
 最新文章