首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Buddy分配器之释放一页

Buddy分配器之释放一页

作者头像
DragonKingZhu
发布2020-04-24 10:38:35
7410
发布2020-04-24 10:38:35
举报

在上面一节我们讲述了buddy分配器是如何分配一页的,本节我们在学习buddy分配器是如何释放一页的

分配一页的算法:比如当前释放order=n的页

  • 获得当前释放order=n的页,对应的buddy,也就是兄弟页,俗话说先找到兄弟
    • 找到兄弟buddy了之后,接下来就是看buddy和此页是否可以合并
      • 检查buddy是否是空闲的页(通过检查page→private是否为0)
      • 检查buddy是否和此页是相同的order
      • 检查buddy和此page是否属于同一个zone
      • 检查buddy的引用计数_refcount是否为0
    • 如果上述的条件都符合,则认为此buddy和此page可以合并
    • 将此buddy从lru链表中删除,页的个数减去1
    • 再将order++,从更高的order去寻找buddy,检查是否可以合并
  • 当找不到buddy的时候,则将此order的页加到lru链表中
  • 将order此页的nr_free加1

举例:当释放order=2的页

  • 找到order=2的buddy页,也就是兄弟页
  • 检查此buddy页是否可以和当前释放的页合并
  • 如果可以合并,则order+1=3
  • 则找到order=3的buddy页
  • 检查此buddy页是否可以和需要分配页是否可以合并
  • 如果合并则将order+1=4。 继续检查是否可以合并到最大order
  • 如果当order=4时无法合并,则将此page添加到order=4的freelist中即可。

那怎么获取一个将要释放页的buddy呢,内核提供了一个函数,可以获取buddy的pfn

static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{
    return page_pfn ^ (1 << order);
}

我们在zone那一节讲解了page和pfn的关系,这里在复习一下。物理页如果按照4K的大小来描述的话,一个4K大小的物理页的区域我们称之为page frame页帧,而如果给page frame编号的话,就出现了page frame num。

而内核提供的page_to_pfn和pfn_to_page可以轻松的相互转化pfn和page的关系,在内存模型为稀疏模型的情况下,page=vmemmap+pfn

假设当前的order=0, page_pfn=0的话,则对应的buddy_pfn=0^(1<<0)=1,则物理页0和物理页1是buddy,就是好兄弟

假设当前的order=3, page_pfn=0的话,则对应的buddy_pfn=0^(1<<3)=8,则物理页0和物理页8是buddy,中间刚好是order个页。

说以说可以通过上述的函数来计算出buddy所在的位置

我们接下来看看buddy释放页的核心函数:

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 = 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 = __find_buddy_pfn(pfn, order);
        buddy = page + (buddy_pfn - pfn);
 
        if (!pfn_valid_within(buddy_pfn))
            goto done_merging;
        if (!page_is_buddy(page, buddy, order))
            goto done_merging;
        /*
         * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
         * merge with it and move up one order.
         */
        if (page_is_guard(buddy)) {
            clear_page_guard(zone, buddy, order, migratetype);
        } else {
            list_del(&buddy->lru);
            zone->free_area[order].nr_free--;
            rmv_page_order(buddy);
        }
        combined_pfn = buddy_pfn & pfn;
        page = page + (combined_pfn - pfn);
        pfn = combined_pfn;
        order++;
    }
    if (max_order < MAX_ORDER) {
        /* If we are here, it means order is >= pageblock_order.
         * We want to prevent merge between freepages on isolate
         * pageblock and normal pageblock. Without this, pageblock
         * isolation could cause incorrect freepage or CMA accounting.
         *
         * We don't want to hit this code for the more frequent
         * low-order merging.
         */
        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 this is not the largest possible page, check if the buddy
     * of the next-highest order is free. If it is, it's possible
     * that pages are being freed that will coalesce soon. In case,
     * that is happening, add the free page to the tail of the list
     * so it's less likely to be used soon and more likely to be merged
     * as a higher order page
     */
    if ((order < MAX_ORDER-2) && pfn_valid_within(buddy_pfn)) {
        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)) {
            list_add_tail(&page->lru,
                &zone->free_area[order].free_list[migratetype]);
            goto out;
        }
    }
 
    list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
out:
    zone->free_area[order].nr_free++;
}
  • 首先会进行一系列合法性检查,zone是否初始化? 迁移类型是否等于-1? 等等
  • 接着就会进入一个while循环,当前order到最大order减去1之间 寻找合适的buddy,然后合并
    1. 根据当前page和pfn,获取buddy的buddy_pfn,根据buddy_pfn在获取buddy页
    2. 通过调用pfn_valid_within来检查buddy_pfn是否是有效的,通过物理地址>>PAGE_SHIFT来判断
    3. 调用page_is_buddy函数来检查此buffy页是否可以合并
      1. page_order(buddy) == order //buddy的所在order和释放的页的order是否相同
      2. page_zone_id(page) != page_zone_id(buddy) //检查是都都在一个相同的zone中
      3. page_count(buddy) != 0 //检查buddy页的索引技术是否等于0
    4. 检查到此buddy可以和此page可以完美合并则进行下一步操作
    5. 将buddy页从page的lru链表中删除,同时将此order可用的page数目减去1,设置此buddy页不在buddy系统中
    6. 计算buddy页和释放页合并后的pdn和page,同时将order数目加1
    7. 继续进入到while循环中再次判断,是否有空闲的页可以合并,
    8. 当出现无法找到合适的buddy页时,则调到done_merging进行做最后的收尾
  • set_page_order(page, order); //设置最终page的order数目
  • 如果当前的order不是最大的order,系统还可以再尝试一波,还是上面相同的操作
  • 将最终合并后的页假如到属于他们order的lru链表中
  • 将此order的可用的页的个数加1
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档