伙伴分配器

分区的伙伴分配器

当系统内核初始化完毕后，使用页分配器管理物理页，当使用的页分配器是伙伴分配器，伙伴分配器的特点是算法简单且高效

连续的物理页成为页块（page block）。阶（order）是伙伴分配器的一个专业术语，是页的数量单位，2^n个连续页成为n阶页块。

满足以下条件的两个n阶页块成为伙伴（buddy）：

两个页块是相邻，即物理地址是连续的；
页块的第一页的物理页号必须是2^n的整数倍；
如果合并成（n+1）阶页块，第一页的物理页号必须是2^(n+1)的整数倍

伙伴分配器分配和释放物理页的数量单位为阶，分配n阶页块的过程如下：

查看是否有空闲的n阶页块，如果有直接分配；否则，继续执行下一步；
查看是否存在空闲的（n+1）阶页块，如果有，把（n+1）阶块分裂成两个n阶页块，一个插入空闲n阶页块链表，另一个分配出去；否则继续执行下一步。
查看是否存在空闲的（n+2）阶页块，如果有把（n+2）阶段分裂成两个（n+1）阶页块，一个插入空闲（n+1）阶页块链表，另一个分裂为两个n阶页块，一个插入空间n阶页块链表,另一个分配出去；如果没有，继续查看更高阶是否存在空闲页块。

数据结构

分页的伙伴分配器专注于某个内存节点的某个区域，内存区域的结构成员free_area用来维护空闲页块，数组下标对应页块的除数。内核源码结构：

//mmzone.h
#ifndef __GENERATING_BOUNDS_H
struct {
/* read-mostly fields*/
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif
/*free areas of different sizes */
struct free_area free_area[MAX_ORDER];//不同长度的空闲区域
unsigned long managed_pages;//伙伴分配器管理的物理页的数量

内核在基本的伙伴分配器基础改进扩展：

支持内存节点和区域，成为分区的伙伴分配器（zond buddy allocator）；
为了预防内存碎片，把物理根据可移动性分组；
针对分配单页做了性能优化，为了减少处理器的锁竞争，在内存区域增加1个每处理器页集合。

分区的伙伴分配器源码分析：

1. 数据结构

//mmzone.h
struct zone{
/* read-mostly fields*/

/*free areas of different sizes */
struct free_area free_area[MAX_ORDER];//不同长度的空闲区域

/* Free memory management - zoned buddy allocator. */

     #ifndef CONFIG_FORCE_MAX_ZONEORDER
    #define MAX_ORDER 11
    #else
    #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
    #endif
    #define MAX_ORDER_NR_PAGES(1 << (MAX_ORDER-1))

/*MAX_ORDER 是最大除数，实际上是可以分配的最大除数加1，默认值是11，意味着伙伴分配器一次
最多可以分配2^10页。

CONFIG_FORCE_MAX_ZONEORDER 指定最大除数

free_area 结构体内核源码*/
struct free_area {
    struct list_head free_list[MIGRATE_TYPES];
    unsigned long nr_free;
};

enum(migratetype)migrate_types = 4

2.根据分配标志获取首选区域类型

申请页的时候，最低的4个标志位用来指定首选的内存区域类型，内核源码如下：

    #ifndef __LINUX_GFP_H
    #define __LINUX_GFP_H

//标志组合
    #define __GFP_DMA 0x01u
    #define __GFP_HIGHTMEM 0x02u
    #define __GFP_DMA32 0x04u
    #define __GFP_MOVABLE 0x08u

//区域类型
    #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个二进制存放区域类型

# 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)\

3. 备用区域列表

如果首选的内存节点或区域不能满足分配请求，可以从备用的内存区域借用物理页，借用必须遵守相应的规则。

借用必须遵守规则：
    一个内存节点的某个区域类型可以从另一个内存节点的相同区域类型借用物理页，比如节点0的普通区域可以从节点1的普通区域借用物流；
    高区域可以从地区域类型借用物理页，比如普通区域可以从DMA区域借用物理页
    地区域类型不能从高区域类型借用物理页，比如DMA区域不能从普通区域借用物理页。

内存节点的pg_data_t 实例已定义备用区域列表，内核源码如下：

    //memzone.h
    struct bootmem_data;
    typedef struct pglist_data {
    struct zone node_zones[MAX_NR_ZONES];//内存区域数组
    struct zonelist node_zonelists[MAX_ZONELISTS];//备用区域列表
    int nr_zones;//该节点包含的内存区域数量
    #ifdef CONFIG_FLAT_NODE_MEM_MAP//除了稀疏内存模型以外
    struct page*node_mem_map;//页描述符数组
    #ifdef CONFIG_PAGE_EXTENSION
    struct page_ext *node_page_ext;//页的扩展属性
    #endif
    #endif
    #ifndef CONFIG_BO_BOOTMEM
        struct bootmem_data *bdata;//阴道bootmem分配器
    #endif

enum {
    ZONELIST_FALLBACK,//包含所有内存点的备用区域列表
    #ifdef CONFIG_NUMA

        ZONELIST_NOFALLBACK,//只包含当前内存节点的备用区域列表
    #endif
        MAXZONELISTS
}


struct  zoneref {
    struct zone *zone; //指向内存区域的数据结构
    int zone_idx;//成员zone 指向的内存区域的类型
}

UMA系统只有一个备用区域列表，按区域类型从高到低排序，假设UMA系统包含普通区域和DMA区域，那么备用区域列表：{普通区域，MDA区域}。 UMA系统每个内存节点有两个备用区域列表：一个包含所有内存节点的区域，另一个只包含当前内存节点的区域。

包含所有内存节点的备用区域列表的两种排序方法：

节点优先顺序先根据节点距离从小到大排序，然后在每个节点里面根据区域类型从高到低排序优点：优先选择距离近的内存，缺点是在高区域耗尽以前使用低区域。
区域优先顺序先根据区域类型从高到低排序，然后再每个区域类型里面根据节点距离从小到大排序。优点：是减少低区域耗尽的几率，缺点是不能保证优先选择距离近的内存。

默认的排序方法就是自动选择最优的排序方法：

如果是64位系统，因为需要DMA和DMA32区域的备用相对较少，选择节点优先书序。
如果是32位系统，选择区域优先顺序。

4. 区域水线

首选的内存区域什么情况下从备用区域借用物理页呢？每个内存区域有3个水线。
a.高水线（high）：如果内存区域的空闲页数大于高水线，说明内存区域的内存充足；
b.低水线（low）:如果内存区域的空闲页数小于低水线，说明内存区域的内存轻微不足；
c.最低水线 (min)：如果内存区域的空闲也睡小于最低水线，说明内存区域的内存严重不足。

enum zone_watermarks {
    WMARK_MIN,
    WMARK_LOW,
    WMARK_HIGH,
    NR_WMARK
};

最低水线以下的内存成为紧急保留内存，在内存严重不足的紧急情况下，给承诺“分给我们少量的紧急保留内存使用，我们可以释放更多的内存”的进程使用

watermark 水位控制内核源码重要数据参数

struct zone {
        unsigned long watermark[NR_WMARK];//页分配器使用的水线
    }



enum zone_watermarks {
    WMARK_MIN,
    WMARK_LOW,
    WMARK_HIGH,
    NR_WMARK
};
#define min_wmark_pages(z) (z->watermark[WMARK_MIN])
#define low_wmark_pages(z)(z->watermark[WMARK_LOW])
#define high_wmark_pages(z)(z->watermark[WMARK_HIGH])

比如HIGH/LOW/MIN三个水位都可以计算出来？

 unsigned long managed_pages;//伙伴分配器管理的物理页的数量 包括空洞 计算方式 zone_end_pfn-zone_start_pfn
 unsigned long spanned_pages;//当前区域跨越的总页数，包括空洞//代表zone 中可用的所有物理页，计算公式spanned_pages - hole_pages
 unsigned long present_pages;//当前区域存在的物理页的数量，不包括空洞 //代表通过buddy 管理所有可用的页，计算公式present_pages - reserved_+pages

三者之间的关系： spanned_pages > present_pages > managed_pages.
在ubuntu 中可以用  cat /proc/zoneinfo 可以看到
min_free_kbytes代表的是系统保留空闲内存的最低限额：
watermark[VMARK_MIN]的值是通过min_free_kbytes 计算出来

unsigned long nr_free_buffer_pages(void)
{
    return nr_free_zone_pages(gfp_zone(GFP_USER));
}

static unsigned long nr_free_zone_pages(int offset)
{
    struct zoneref *z;
    struct zone *zone;
    unsigned long sum = 0;
    struct zonelist *zonelist = node_zonelist(numa_node_id(),GFP_KERNEL);
    for_each_zone_zonelist(zone,z ,zonelist ,offset) {
        unsigned long size = zone->managed_pages;
        unsigned long high = high_wmark_pages(zone);
        if(size > high) {
            sum += size - high;
        }
    }
    return sum;
}

int  __meminit init_per_zone_wmark_min(void)
{
    unsigned long lowmem_kbytes;
    int new_min_free_kbytes;
    //lowmem 中超过高水位的页的总和，单位kbytes,就是lowmem中超过high水位的页乘以4得到lowmem_kbytes
    lowmem_kbytes = nr_free_buffer_pages()*(PAGE_SIZE >> 10);
    //
    new_min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
    //min_free_kbytes最小不能小于128k,最大不超过65535k
    if(new_min_free_kbytes > user_min_free_kbytes) {
        min_free_kbytes = new_min_free_kbytes;
        if(min_free_kbytes < 128) 
             min_free_kbytes = 128;
        if(min_free_kbytes > 655365)
            min_free_kbytes = 65536;
    } else {
        pr_warn("min_free_kbytes is not updated to %d because user defined value %d is prederred",new_min_free_kbytes,user_min_free_kbytes);
    }
    setup_per_zone_wmarks();
    refresh_zone_stat_thresholds();
    setup_per_zone_lowmem_reserve();
#ifdef CONFIG_NUMA
    setup_min_unmapped_ratio();
    setup_min_slab_ratio();
#endif
    return 0;
}

分配页

在Linux内核中，所有分配页的函数最终都会调用到

__alloc_apges_nodemask

此函数被称为分区的伙伴分配器的心脏。核心函数原型如下：

//page_alloc.c
struct page __alloc_pages_nodemask(gfp_t gfp_mask,unsigned int order,struct zonelist *zonelist,nodemask_t *nodemask)

算法流程如下：

根据分配标志位得到首选区域类型和迁移类型
执行快速路径，使用低水线尝试第一次分配
如果快速路径分配失败，才执行慢速路径

gfp_mask:分配标志位 order：阶数 zonelist:首选内存节点的备用区域列表 nodemask:允许从哪里内存节点分配页，如果调用者没有要求,可以传入空指针

页分配器定义内部分配标志位

#define ALLOC_WMARK_MIN WMARK_MIN //使用最低水线
#define ALLOC_WMARK_LOW WMARK_LOW //使用低水线
#define ALLOC_WMARk_HIGH WMARK_HIGH //使用最高水线
#define ALLCO_NO_WATERMARKS //完全不检查水线

#define ALLOC_WMARK_MASK (ALLOC_NO_WATERMARKS-1) //得到水线的掩码
#define ALLOC_HARDER 0x10 //试图更努力分配
#define ALLOC_HIGH 0x20 //调用者是高优先级
#define ALLOC_CPUSET 0x40 //检查CPUSET是否允许进城从某个内存节点分配页
#define ALLOC_CMA 0x80 //允许从CMA(连续内存分配器)迁移类型分配

快速路径调用函数如下：

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 = ac->preferred_zoneref;
    struct zone *zone;
    struct pglist_data *last_pgdat_dirty_limit = NULL;
    /*扫描备用区域列表中每个满足条件的区域：区域类型小于或等待首选区域类型，并且内存节点在节点掩码中的相应被设置处理*/
    for_next_zone_zonelist_nodemask(zone,z,ac->zonelist,ac->high_zoneidx,ac->nodemask){
        struct page *page;
        unsigned long mark;
    /*
    如果编程cpuset功能，调用者设置ALLOC_CPUSET 要求使用cpuset检查，并且cpuset不允许当前进程从这个内存节点分配，那么不能从这个区域分配页
    */
    if(cpusets_enabled()&& (alloc_flags & ALLOC_CPUSET) && !__cpuset_zone_allowed(zone,gfp_mask))
        continue;
     /*
    如果调用者设置标志位__GFP_WRITE,表示文件系统申请分配一个页页缓存页用来写文件，那么检查内存节点的脏页数量是否超过限制，如果超过就不能从这个区域分配页
        */
        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;
            }
        }
        //检查流水线，如果（区域的空闲页数-申请的页数）小于水线
        mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK]
        if(!zone_watermark_fast(zone,order,mark,ac_classzone_idx(ac),alloc_flags)) {
            int ret;
            BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
            if(alloc_flags & ALLOC_NO_WATERMARKS)
                goto try_this_zone;
            /*如果没有开启节点回收功能，或者当前节点和首选节点之间的距离大于回收距离，不能从这个区域分配页*/
             if(node_reclaim_mode == 0 || !zone_allows_reclaim(ac->preferred_zoneref->zone,zone))
                continue;
            /* 从节点回收没有映射到里程虚拟地址空间的文件页的块分配器申请的页，然后重新检查水线，如果（区域的空闲页数-申请的页数）小于水线，不能从这个区域分配页
            */
            ret = node_reclaim(zone->zone_pgdat,gfp_mask,order);
            switch(ret) {
                case NODE_RECLAIM_NOSCAN:
                    continue;
                case NODE_RECLAIM_FULL:
                    continue;
                default:
                    if(zone_watermark_ok(zone,order,mark,ac_classzone_idx(ac),alloc_flags))
                        goto try_this_zone;
                    continue;
            }
        }
        try_this_zone:
            //直接从当前区域分配页，调用rmqueue来分配
            page = rmqueue(ac->preferred_zoneref->zone,zone,order,gfp_mask,alloc_flags,ac->migratetype);
            // 如果分配成功,调用函数prep_new_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;
            }
        }
        return NULL;
    }
}

慢速路径调用函数内核源码分析（如果低水线分配失败，则执行慢速路径）

static inline struct page * __alloc_pages_slowpath(gfp_t gfp_mask,unsigned int order,struct alloc_context *ac)
{
    bool can_direct_reclaim = gfp_mask & __GFP_DIRRECT_RECLAIM;
    const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
}

释放页

void __free_pages(struct page *page ,unsigned int order) 第一个参数是第一个物理页的page实例地址，第二个参数是阶数。

void __free_pages(struct page *page,unsigned int order)
{
    if(put_page_testzero(page)){
        if(order == 0)
            free_hot_cold_page(page,false);
        else
            __free_pages_ok(page,order);
    }
}

HrQing

基于Django的网站，记录IT 开发，包括c++,java,python, 接受半导体测试服务，包括力学测试，表面分析测试，热学测试，联系方式：[email protected]。

伙伴分配器

伙伴分配器

分区的伙伴分配器

数据结构

内核在基本的伙伴分配器基础改进扩展：

分区的伙伴分配器源码分析：

1. 数据结构

2.根据分配标志获取首选区域类型

3. 备用区域列表

包含所有内存节点的备用区域列表的两种排序方法：

4. 区域水线

watermark 水位控制内核源码重要数据参数

分配页

页分配器定义内部分配标志位

快速路径调用函数如下：

慢速路径调用函数内核源码分析（如果低水线分配失败，则执行慢速路径）

释放页

您还没有登录，请您登录后发表评论。

伙伴分配器

分区的伙伴分配器

数据结构

内核在基本的伙伴分配器基础改进扩展：

分区的伙伴分配器源码分析：

1. 数据结构

2.根据分配标志获取首选区域类型

3. 备用区域列表

包含所有内存节点的备用区域列表的两种排序方法：

4. 区域水线

watermark 水位控制 内核源码重要数据参数

分配页

页分配器定义内部分配标志位

快速路径调用函数如下：

慢速路径调用函数内核源码分析（如果低水线分配失败，则执行慢速路径）

释放页

您还没有登录，请您登录后发表评论。

watermark 水位控制内核源码重要数据参数