正文

buddy(伙伴)系统分配器之分配page(代码片段)

Loopers  Loopers  2022-12-12  728

关键词：

Buddy分配器是按照页为单位分配和释放物理内存的，在Zone那一节文章中freearea就是通过buddy分配器来管理的。

buddy分配器将空闲页面按照order的大小分配挂到不同的order链表中。比如order为0的链表下就挂载着大小为1个page的空闲页，order=4的链表下就挂载着大小为16个page的空闲页面。

buddy分配器的算法是：

当分配order=n的页面的时候，首先order=n的freelist链表中去寻找对应的页，如果order=n的freelist中有空闲的页面，则直接分配
当order=n的freelist链表中没有可用的页面时，则去order=n+1的freelist中查找是否有对应的空闲页面
如果order=n+1的freelist链表中存在空闲页面，则从order=n+1的freelist中取出一个空闲页面，将其分为两个order=n的页面。
其中一个分配出去，另外一个挂载到order=n的空闲链表中。
其中刚分开的那两个空闲页面称为buddy

举个例子：比如申请order=2的，迁移类型为MIGRATE_MOVABLE为可移动的页面

当比如分配order=2的页面时，先去freearea[2].free_list[MIGRATE_MOVABLE]中查找是否有空闲的页面，如果有则返回此页面，同时freearea[2].nr_free减1
如果freearea[2].freelist[MIGRATE_MOVABLE]中没有可用的空闲页面，则去freearea[3].freelist[MIGRATE_MOVABLE]去寻找是否有可用的空闲页面
如果freearea[3].freelist[MIGRATE_MOVABLE]中存在空闲的页面，则将其一分为二，其中一份直接返回，另外一份挂载到freearea[2].freelist[MIGRATE_MOVABLE]的链表中
同时将freearea[3].nr_free减去1，freearea[2].nr_free加上1
刚才从freearea[3].freelist[MIGRATE_MOVABLE]拆分的两个空闲页面，这两个空闲页面物理地址是连续的，我们称之为buddy

在真正分析分配代码之前，我们需要看一下ALLOC_开头的一些flag

/* The ALLOC_WMARK bits are used as an index to zone->watermark */
#define ALLOC_WMARK_MIN     WMARK_MIN
#define ALLOC_WMARK_LOW     WMARK_LOW
#define ALLOC_WMARK_HIGH    WMARK_HIGH
#define ALLOC_NO_WATERMARKS 0x04 /* don't check watermarks at all */
 
/* Mask to get the watermark bits */
#define ALLOC_WMARK_MASK    (ALLOC_NO_WATERMARKS-1)

ALLOC_WMARK_MIN: 从最低水位分配或者以上
ALLOC_WMARK_LOW：从低水位分配或者以上
ALLOC_WMARK_HIGH：从高水位分配或者以上
ALLOC_NO_WATERMARKS：分配不检查水位

#ifdef CONFIG_MMU
#define ALLOC_OOM       0x08
#else
#define ALLOC_OOM       ALLOC_NO_WATERMARKS
#endif
 
#define ALLOC_HARDER         0x10 /* try to alloc harder */
#define ALLOC_HIGH       0x20 /* __GFP_HIGH set */
#define ALLOC_CPUSET         0x40 /* check for correct cpuset */
#define ALLOC_CMA        0x80 /* allow allocations from CMA areas */
#ifdef CONFIG_ZONE_DMA32
#define ALLOC_NOFRAGMENT    0x100 /* avoid mixing pageblock types */
#else
#define ALLOC_NOFRAGMENT      0x0
#endif
#define ALLOC_KSWAPD        0x200 /* allow waking of kswapd */

ALLOC_HARDER: 努力去分配，尽力的去分配
ALLOC_HIGH：高优先级的分配
ALLOC_CPUSET：检查是否正确CPUSET配置
ALLOC_CMA：允许从CMA区域分配
ALLOC_KSWAPD：允许唤醒kswapd

接着再来看下__GFP_开头的一起请求flag, gfp_flag有点太多，先列举点

#define __GFP_DMA   ((__force gfp_t)___GFP_DMA)
#define __GFP_HIGHMEM   ((__force gfp_t)___GFP_HIGHMEM)
#define __GFP_DMA32 ((__force gfp_t)___GFP_DMA32)
#define __GFP_MOVABLE   ((__force gfp_t)___GFP_MOVABLE)  /* ZONE_MOVABLE allowed */
#define __GFP_CMA   ((__force gfp_t)___GFP_CMA)
#define GFP_ZONEMASK    (__GFP_DMA|__GFP_HIGHMEM|__GFP_DMA32|__GFP_MOVABLE)
#define __GFP_NOFAIL    ((__force gfp_t)___GFP_NOFAIL)
#define __GFP_NORETRY   ((__force gfp_t)___GFP_NORETRY)

__GFP_DMA: 允许从DMA区域分配
__GFP_HIGHMEM: 允许从highmem区域分配
__GFP_DMA32: 允许从DMA32区域分配
__GFP_MOVEABLE: 允许从可移动区域分配
__GFP_CMA: 允许从CMA区域分配
__GFP_NOFAIL：分配不允许失败，会一直重试
__GFP_NORETRY：分配失败后不允许retry

我们接下来看下buddy分配的核心代码：

/*
 * Allocate a page from the given zone. Use pcplists for order-0 allocations.
 */
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)) 
        page = rmqueue_pcplist(preferred_zone, zone, order,
                gfp_flags, migratetype, alloc_flags);
        goto out;
    
 
    /*
     * We most definitely don't want callers attempting to
     * allocate greater than order-1 page units with __GFP_NOFAIL.
     */
    WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
    spin_lock_irqsave(&zone->lock, flags);
 
    do 
        page = NULL;
 
        if (alloc_flags & ALLOC_HARDER) 
            page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
            if (page)
                trace_mm_page_alloc_zone_locked(page, order, migratetype);
        
 
        if (!page && migratetype == MIGRATE_MOVABLE &&
                gfp_flags & __GFP_CMA)
            page = __rmqueue_cma(zone, order);
 
        if (!page)
            page = __rmqueue(zone, order, migratetype, alloc_flags);
     while (page && check_new_pages(page, order));
 
    spin_unlock(&zone->lock);
    if (!page)
        goto failed;
    __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 */
    if (test_bit(ZONE_BOOSTED_WATERMARK, &zone->flags)) 
        clear_bit(ZONE_BOOSTED_WATERMARK, &zone->flags);
        wakeup_kswapd(zone, 0, 0, zone_idx(zone));
    
 
    VM_BUG_ON_PAGE(page && bad_range(zone, page), page);
    return page;
 
failed:
    local_irq_restore(flags);
    return NULL;

当order等于0时，会直接从per-cpu的列表中获取page
当分配的order大于1时，而且设置的flag是__GFP_NOFAIL，则会发生警告
当分配的flag是需要ALLOC_HARDER分配时，则优先从MIGRATE_HIGHATOMIC（高阶原子分配）
如果分配失败，当迁移类型是MIGRATE_MOVABLE的，而且分配标志是从CMA分配，则优先从CMA区域分配
如果CMA区域分配失败，则直接调用__rmqueue根据参数从freelist中分配一个空闲页

申请一页的时候会经历上述的4个步骤，最终这4个步骤会全部调用到第五步__rmqueue_smallest函数中。

/*
 * Go through the free lists for the given migratetype and remove
 * the smallest available page from the freelists
 */
static __always_inline
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 = list_first_entry_or_null(&area->free_list[migratetype],
                            struct page, lru);
        if (!page)
            continue;
        list_del(&page->lru);
        rmv_page_order(page);
        area->nr_free--;
        expand(zone, page, order, current_order, area, migratetype);
        set_pcppage_migratetype(page, migratetype);
        return page;
    
 
    return NULL;

这个函数有三个参数zone代表从哪个zone分配，order代表分配的大小，migratetype：代表分配时的迁移类型
获取一个空闲页的算法是：
1. 获取当前order的free_area, free_area[current_order]
2. 根据参数迁移类型，从当前的freelist中获取一个page， freelist[migratetype]
3. 如果当前freelist中存在可用的page
  1. 将此page从page的lru链表中删除
  2. 设置此page的private为0， ((page)->private = (0))
  3. 将此order去的可用page页数减1， area->nr_free–;
  4. 设置此page的迁移类型： page->index = migratetype;
4. 如果当前freelist中无可用的page
  1. 则从下一个order继续找是否有可用的page，比如current_order=5，则第一次没找到可用的page时，current_order=6
  2. 假设从current_order=6的freelist链表中找到可用的page。
  3. 将此page从page链表中删除
  4. 设置此page的private为0， ((page)->private = (0))
  5. 将此order去的可用page页数减1， area->nr_free–;
  6. 调用expand函数，会将order=6的页拆分为两个order=5的页，一个页返回，另外一个order=5的页加入到order=5的freelist链表中

继续看下expand的函数实现

static inline void expand(struct zone *zone, struct page *page, int low, int high, struct free_area *area, int migratetype)

    unsigned long size = 1 << high;
 
    while (high > low) 
        area--;
        high--;
        size >>= 1;
        VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);
 
        /*
         * Mark as guard pages (or page), that will allow to
         * merge back to allocator when buddy will be freed.
         * Corresponding page table entries will not be touched,
         * pages will stay not present in virtual address space
         */
        if (set_page_guard(zone, &page[size], high, migratetype))
            continue;
 
        list_add(&page[size].lru, &area->free_list[migratetype]);
        area->nr_free++;
        set_page_order(&page[size], high);

当从希望获得order获取到可用的page时，不会进入此函数，举例：希望从order=5获取，order=5有可用的页，直接返回，则不进此函数
当最终获得页的order大于希望获得页的order，则会进入到此函数，举例：希望从order=5获取，order=5无可用的页，从order=6获取到了也，则会进入到此函数
此函数实现的算法是：假如high=6 low=5
1. 将area减去1，则当前area会指向order=5的area_free[5]的链表上
2. 将area→freelist[migratetype]的添加到page的lru链表上，此page就是Order=6的页分裂开的
3. 将area的nr_free加一
4. 设置此page的page->private=order数

linux内存从0到1学习笔记(6.8，物理内存初始化之buddy伙伴系统)

...内存管理slaballocator在系统初始化阶段会先启用一个bootmem分配器和memblock分配器，bootmem分配器管理着一个node结点的所有内存，包括nu 查看详情

buddy分配器之释放一页(代码片段)

在上面一节我们讲述了buddy分配器是如何分配一页的，本节我们在学习buddy分配器是如何释放一页的分配一页的算法：比如当前释放order=n的页获得当前释放order=n的页，对应的buddy，也就是兄弟页，俗话说... 查看详情

12linux的伙伴系统和slab分配器

...：查询本机的内存区；zone数据结构表示一个区； SLAB分配器：为了分配更小的内存大小，192原因：查看详情

内存管理算法--buddy伙伴算法

...n.net/orange_os/article/details/7392986Buddy算法的优缺点：1）尽管伙伴内存算法在内存碎片问题上已经做的相当出色，但是该算法中，一个很小的块往往会阻碍一个大块的合并，一个系统中，对内存块的分配，大小是随机的，一片内存中... 查看详情

内核解读之内存管理页分配器伙伴系统介绍(代码片段)

文章目录1分配器的需求２伙伴系统的内存组织２.1zonelist列表结构２.2zone的空闲内存结构2.3内存迁移类型２.4pcp页框1分配器的需求伙伴系统是linux的页框分配器，负责系统物理内存的分配工作。由于几乎所有模... 查看详情

内核解读之内存管理页分配器伙伴系统介绍(代码片段)

物理内存管理之zone详解(代码片段)

...就可以看到ZONE中是如何管理我们page的，就会看到buddy分配器。structzo 查看详情

内核源码解读之内存管理（10）percpu_page_set分析(代码片段)

...f0c;而且经常存在频繁分配释放的行为，如果每次都去伙伴系统中申请，会经常需要获取zone->lock锁住整个zone区域。随着CPU核心数的增加，伙伴系统锁竞争激烈程度也会越来越大。为了改善这个问题，linux内核中... 查看详情

slub的引入及举例说明(代码片段)

我们都知道Buddy分配器是按照页的单位分配的（Buddy系统分配器实现），如果我们需要分配几十个字节，几百个字节的时候，就需要用到SLAB分配器。SLAB分配器专门是针对小内存分配而设计的，比如我们驱动... 查看详情

slub的引入及举例说明(代码片段)

深入理解伙伴算法及其改进

... 今天遇到很好的一个腾讯面试官，进一步探讨了伙伴算法，面试官非常nice，对伙伴算法的优缺点详细给我讲了一下，发现这个算法值得深入研究一波~看了很多资料，下面整理资料，然后谈谈自己的理解。体会　　L... 查看详情

伙伴系统(代码片段)

...一组连续的页而建立的高效分配策略，结合2的幂次方个分配器和空闲缓冲区合并的技术。内存被分成含有若干个（2^0,2^1,2^2...2^11）页面的块。　　伙伴系统的分配器维护空闲页面所组成的块,这里每一块都是2的方幂个页面,方幂... 查看详情

内存管理-slab[原理](代码片段)

...,一次分配内存的大小是随机的。第一种分配方案通过buddy系统实现，第二种分配方案就是通过slab子系统实现。slab子系统随内核的发展衍生出slub和slob,最新应用于服务器的内核一般默认使用slub来实现第二种内存分配方案。slob 查看详情

linux内核源码分析之伙伴系统(代码片段)

目录伙伴关系基础避免碎片1，依据可移动性组织页2、虚拟可移动内存域内核中不连续页的分配用vmalloc分配内存释放内存伙伴关系基础 free_area[]数组中各个元素的索引也解释为阶，用于指定对应链表... 查看详情

内核源码解读（10）percpu_page_set分析(代码片段)

好友分配算法 - 起始堆地址

...Allocator，它利用了给定数据块及其对应地址的重要不变量伙伴。计算如下……BUDDY(X):X+2^iifxmod2^i+1=0X-2^iifxmod2^i-1=0WhereXisth 查看详情

linux采用啥方法实现内存的分配和释放

...............Linux采用Buddy算法有效分配和释放物理页块。linux系统内存管理的特点linux的进程结束后，它占用的资源全部释放，但是内存仅仅是设置了标志，标志了这部分内存已经不再使用，可以被重新分配的。当进程需要内存时，l... 查看详情