（七）Linux内存管理 - zoned page frame allocator - 2

背景

Read the fucking source code!
A picture is worth a thousand words.

说明：

1. Kernel版本：4.14
2. ARM64处理器，Contex-A53，双核
3. 使用工具：Source Insight 3.5， Visio

1. 概述

本文将分析 Buddy System 。

Buddy System 伙伴系统，是通过将物理内存划分为页面来进行管理的系统，支持连续的物理页面分配和释放。此外，使用与碎片相关的算法来确保最大的连续页面。

先通过一个例子大体介绍一下原理吧：

空闲的物理页框按大小分组成 0~MAX_ORDER 个链表，每个链表存放页框的大小为2的n次幂，其中n在 0 ~ MAX_ORDER-1 中取值。

假设请求分配 2^8 = 256 个页框块：

1. 检查 n = 8 的链表，检查是否有空闲块，找到了则直接返回；
2. 没有找到满足需求的，则查找 n = 9 的链表，找到 512大小 空闲块，拆分成两个 256大小 块，将其中一个 256大小 块返回，另一个 256大小 块添加到 n = 8 的链表中；
3. 在 n = 9 的链表中没有找到合适的块，则查找 n = 10 的链表，找到1024大小空闲块，将其拆分成 512 + 256 + 256 大小的块，返回需要获取的 256大小 的块，将剩下的 512大小 块插入 n = 9 链表中，剩下的 256大小 块插入 n = 8 的链表中；

合并过程是上述流程的逆过程，试图将大小相等的 Buddy块 进行合并成单独的块，并且会迭代合并下去，尝试合并成更大的块。合并需要满足要求：

1. 两个 Buddy块 大小一致；
2. 它们的物理地址连续；
3. 第一个 Buddy块 的起始地址为 (2 x N x 4K) 的整数倍，其中 4K 为页面大小， N 为 Buddy块 的大小；

struct page 结构中，与 Buddy System 相关的字段有：

• _mapcount ： 用于标记 page 是否处在 Buddy System 中，设置成 -1 或 PAGE_BUDDY_MAPCOUNT_VALUE(-128) ；
• private ： 一个 2^k 次幂的空闲块的第一个页描述符中， private 字段存放了块的 order 值，也就是 k 值；
• index ： 存放 MIGRATE 类型；
• _refcount ： 用户使用计数值，没有用户使用为0，有使用的话则增加；

2. Buddy页面分配

从上图中可以看出，在页面进行分配的时候，有以下四个步骤：

1. 如果申请的是 order = 0 的页面，直接选择从 pcp 中进行分配，并直接退出；
2. order > 0 时，如果分配标志中设置了 ALLOC_HARDER ，则从 free_list[MIGRATE_HIGHATOMIC] 的链表中进行页面分配，分配成功则返回；
3. 前两个条件都不满足，则在正常的 free_list[MIGRATE_*] 中进行分配，分配成功则直接则返回；
4. 如果3中分配失败了，则查找 后备类型fallbacks[MIGRATE_TYPES][4] ，并将查找到的页面移动到所需的 MIGRATE 类型中，移动成功后，重新尝试分配；

上述分配的过程，前3个步骤都会调用到 __rmqueue_smallest ，第4步调用 __rmqueue_fallback ，将从这两个函数来分析。

2.1 __rmqueue_smallest

__rmqueue_smallest 的源代码比较简单，贴上来看看吧：

static 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;
}

从代码中可以看出：

1. 从申请的 order 大小开始查找目标 MIGRATE 类型链表中页表，如果没有找到，则从更大的 order 中查找，直到 MAX_ORDER ；
2. 查找到页表之后，从对应的链表中删除掉，并调用 expand 函数进行处理；

2.2 __rmqueue_fallback

当上述过程没有分配到内存时，便会开始从后备迁移类型中进行分配。

其中，定义了一个全局的 二维fallbacks 的数组，并根据该数组进行查找，代码如下：

/*
 * This array describes the order lists are fallen back to when
 * the free lists for the desirable migrate type are depleted
 */
static int fallbacks[MIGRATE_TYPES][4] = {
    [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
    [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
    [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
#ifdef CONFIG_CMA
    [MIGRATE_CMA]         = { MIGRATE_TYPES }, /* Never used */
#endif
#ifdef CONFIG_MEMORY_ISOLATION
    [MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
#endif
};

3. Buddy页面释放

当 order = 0 时，会使用 Per-CPU Page Frame 来释放，其中：

• MIGRATE_UNMOVABLE, MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE 三个按原来的类型释放；
• MIGRATE_CMA, MIGRATE_HIGHATOMIC 类型释放到 MIGRATE_UNMOVABLE 类型中；
• MIGRATE_ISOLATE 类型释放到Buddy系统中；
  此外，在PCP释放的过程中，发生溢出时，会调用 free_pcppages_bulk() 来返回给Buddy系统。来一张图就清晰了：
  

在整个释放过程中，核心函数为 __free_one_page ，该函数的核心逻辑部分如下所示：

continue_merging:
    while (order < max_order - 1) {
        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++;
    }

• __find_buddy_pfn ： 根据释放页面的 pfn 计算对应的 buddy_pfn ，比如 pfn = 0x1000, order = 3 ，则 buddy_pfn = 0x1008 ， pfn = 0x1008, order = 3 ，则 buddy_pfn = 0x1000 ；
• page_is_buddy ：将 page 和 buddy 进行配对处理，判断是否能配对；
• 进行combine之后，再将pfn指向合并后的开始位置，继续往上一阶进行合并处理；

不得不说，还有很多细节没有去扣，一旦沉沦，将难以自拔，待续吧。