Buddy System

Buddy System 伙伴系统

Buddy System，即伙伴系统，被广泛应用于分配连续的物理内存页。本节内容将：

  • 回顾伙伴系统的基础知识与设计理念
  • 分析 Chcore 源码对伙伴系统的代码实现与架构
  • 解析 Chcore 源码对伙伴系统操作相关函数的具体实现

回顾：为什么需要伙伴系统

面对进程多种多样的内存分配请求，自然需要一个精良的分配器设计来承担这样宏伟的责任。许多分配器无不在内存碎片（无法被利用的内存）的困扰下捉襟见肘，而伙伴系统则在一定程度上解决了普通简易分配器会带来的内存碎片问题，尤其是在分配连续内存的情况下。

外部碎片与内部碎片

  • 外部碎片：单个空闲内存部分小于分配请求的内存大小
  • 内部碎片：分配内存大于实际内存导致的内存碎片

Buddy System 将通过合并与级联的设计来避免这些困扰

伙伴系统的设计理念

伙伴系统设计理念即基于伙伴块进行分裂与合并，主要可概括为以下几点：

  • 物理内存划为块为单位分配内存，每个块由连续物理页组成，大小为 2^n 个物理页（便于分裂与合并）
  • 大块可根据分配需求分裂为小块，两个相同的小块可合并为大块，大块分裂出的两个小块即称作伙伴
  • 分配时根据需求选择块，若这样的空闲块不存在，则找大块分裂；释放内存时查看其伙伴，若伙伴也空闲则直接合并

如下图所示，相同颜色的块即表示伙伴块


graph TD
A[内存空间
16KB] -->|分割| B[块 1
8KB]
A -->|分割| C[块 2
8KB]
B -->|分割| D[块 3
4KB]
B -->|分割| E[块 4
4KB]
C -->|分割| F[块 5
4KB]
C -->|分割| G[块 6
4KB]

    style A fill:#f9f,stroke:#333,stroke-width:2px
    style B fill:#ccf,stroke:#333,stroke-width:2px
    style C fill:#ccf,stroke:#333,stroke-width:2px
    style D fill:#cfc,stroke:#333,stroke-width:2px
    style E fill:#cfc,stroke:#333,stroke-width:2px
    style F fill:#290,stroke:#333,stroke-width:2px
    style G fill:#290,stroke:#333,stroke-width:2px

由此一来，基于 Buddy System 的分配模式便可确保每时每刻的空闲块都是最大的，这样可以避免外部碎片；同时基于分配请求来寻找空闲块分配的操作又尽可能减小了内部碎片的大小。尽量避免了较大内存碎片的产生

Chcore 伙伴系统的设计

核心数据结构

核心数据结构，即 page 和 phys_mem_pool ，如下所示为源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#define N_PHYS_MEM_POOLS 3

/* The following two are defined in mm.c and filled by mmparse.c. */
extern paddr_t physmem_map[N_PHYS_MEM_POOLS][2];
extern int physmem_map_num;

/* All the following symbols are only used locally in the mm module. */

/* `struct page` is the metadata of one physical 4k page. */
struct page {
        /* Free list */
        struct list_head node;
        /* Whether the correspond physical page is free now. */
        int allocated;
        /* The order of the memory chunck that this page belongs to. */
        int order;
        /* Used for ChCore slab allocator. */
        void *slab;
        /* The physical memory pool this page belongs to */
        struct phys_mem_pool *pool;
};

struct free_list {
        struct list_head free_list;
        unsigned long nr_free;
};

/*
 * Supported Order: [0, BUDDY_MAX_ORDER).
 * The max allocated size (continous physical memory size) is
 * 2^(BUDDY_MAX_ORDER - 1) * 4K.
 * Given BUDDY_MAX_ORDER is 14, the max allocated chunk is 32M.
 */
#define BUDDY_PAGE_SIZE     (0x1000)
#define BUDDY_MAX_ORDER     (14)

/* One page size is 4K, so the order is 12. */
#define BUDDY_PAGE_SIZE_ORDER (12)

/* Each physical memory chunk can be represented by one physical memory pool. */
struct phys_mem_pool {
        /*
         * The start virtual address (for used in kernel) of
         * this physical memory pool.
         */
        vaddr_t pool_start_addr;
        unsigned long pool_mem_size;

        /*
         * The start virtual address (for used in kernel) of
         * the metadata area of this pool.
         */
        struct page *page_metadata;

        /* One lock for one pool. */
        struct lock buddy_lock;

        /* The free list of different free-memory-chunk orders. */
        struct free_list free_lists[BUDDY_MAX_ORDER];

        /*
         * This field is only used in ChCore unit test.
         * The number of (4k) physical pages in this physical memory pool.
         */
        unsigned long pool_phys_page_num;
};

/* Disjoint physical memory can be represented by several phys_mem_pools. */
extern struct phys_mem_pool global_mem[N_PHYS_MEM_POOLS];

page

在 chcore 中，一个 page 结构体即表示一个实际的 4KB 大小的物理内存页，我们来看它的具体成员组成：

  • struct list_head node ：是用于维护空闲链表的节点，当我们需要把这个页移入/移出空闲链表时，就会使用到这个节点
  • int allocated ：表示该页是否被分配
  • int order ：表示该页所属的块的阶数（即 2^n 的 n）
  • struct phys_mem_pool *pool ：表示该页所隶属的内存池

另外还有 slab，这个会在下文讲解 slab 分配器的时候具体解析

phys_mem_pool

chcore 里的内存池即表示一整块连续的物理内存，也就是伙伴系统概念中所提到的整个空闲链表背后所属于的大的连续内存块。所以相应的，它就需要维护链表数组以及其所包含的所有页表元数据。我们还是来看看它的具体成员组成：

  • vaddr_t pool_start_addr ：内存池表示内存的起始地址
  • unsigned long pool_mem_size ：内存池表示的内存大小
  • struct page *page_metadata ：一个页表数组，包含了这个内存块里的所有页表
  • struct lock buddy_lock ：内存池的锁，用于并行化
  • struct free_list free_lists[BUDDY_MAX_ORDER] ：空闲链表数组，这里的 order 最大为 14，故有 14 个这样的链表，可以依次表示 4KB 到 32MB 的内存

核心函数接口

即伙伴系统用于实际操作这些数据结构的函数，这里先大概介绍一下接口，下文再深入研究其实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void init_buddy(struct phys_mem_pool *, struct page *start_page,
                vaddr_t start_addr, unsigned long page_num);

static struct page *get_buddy_chunk(struct phys_mem_pool *pool,
                                    struct page *chunk)

static struct page *split_chunk(struct phys_mem_pool *pool, int order,
                                struct page *chunk)

static struct page *merge_chunk(struct phys_mem_pool *pool, struct page *chunk)

struct page *buddy_get_pages(struct phys_mem_pool *, int order);

void buddy_free_pages(struct phys_mem_pool *, struct page *page);

void *page_to_virt(struct page *page);

struct page *virt_to_page(void* ptr);

unsigned long get_free_mem_size_from_buddy(struct phys_mem_pool *);

unsigned long get_total_mem_size_from_buddy(struct phys_mem_pool *);

从上到下的函数接口依次的功能为：

  • init_buddy ：初始化伙伴系统，包括其链表数组，页表元数据数组等
  • get_buddy_chunk ：根据指定内存池和内存块（的起始页表项）找到其伙伴块
  • split_chunk ：分裂内存块
  • merge_chunk ：合并伙伴内存块
  • buddy_get_pages ：查询并获取指定内存池和阶数的内存块
  • buddy_free_pages ：释放指定内存池的内存块
  • page_to_virt ：获取给定内存块（page_metadata）的虚拟地址，这是因为 page 类的指针指向的是 page_metadata 而非实际地址
  • virt_to_page ：根据给定虚拟地址找到相应的内存块（page_metadata），和上面的函数互为逆操作
  • get_free_mem_size_from_buddy ：获取给定内存池中当前可用的内存总量
  • get_total_mem_size_from_buddy ：获取给定内存池的总大小

Chcore 源码对伙伴系统的具体实现

上一部分我们从上层的视角讲解了伙伴系统的原理以及 Chcore 中伙伴系统的架构，这一部分我们则从下层的视角，来分析上文提到的函数接口以及 Buddy System 核心功能的具体实现

本节主要着重分析对伙伴系统的初始化以及对伙伴块的操作函数的讲解，而受限于篇幅，辅助函数本处不做解析，感兴趣者可自行阅读

init_buddy

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
 * The layout of a phys_mem_pool:
 * | page_metadata are (an array of struct page) | alignment pad | usable memory
 * |
 *
 * The usable memory: [pool_start_addr, pool_start_addr + pool_mem_size).
 */
void init_buddy(struct phys_mem_pool *pool, struct page *start_page,
                vaddr_t start_addr, unsigned long page_num)
{
        int order;
        int page_idx;
        struct page *page;

        BUG_ON(lock_init(&pool->buddy_lock) != 0);

        /* Init the physical memory pool. */
        pool->pool_start_addr = start_addr;
        pool->page_metadata = start_page;
        pool->pool_mem_size = page_num * BUDDY_PAGE_SIZE;
        /* This field is for unit test only. */
        pool->pool_phys_page_num = page_num;

        /* Init the free lists */
        for (order = 0; order < BUDDY_MAX_ORDER; ++order) {
                pool->free_lists[order].nr_free = 0;
                init_list_head(&(pool->free_lists[order].free_list));
        }

        /* Clear the page_metadata area. */
        memset((char *)start_page, 0, page_num * sizeof(struct page));

        /* Init the page_metadata area. */
        for (page_idx = 0; page_idx < page_num; ++page_idx) {
                page = start_page + page_idx;
                page->allocated = 1;
                page->order = 0;
                page->pool = pool;
        }

        /* Put each physical memory page into the free lists. */
        for (page_idx = 0; page_idx < page_num; ++page_idx) {
                page = start_page + page_idx;
                buddy_free_pages(pool, page);
        }
}

解析

这个函数主要负责初始化我们的伙伴系统，它将接受的参数用于初始化一个特定的内存池，并为之设置相应页表数组和空闲链表数组等。你可能会好奇，这些参数本身又是怎么来的？这便涉及到对整个物理内存系统的初始化，可以移步 mm.c 文件的 mm_init 函数及相关辅助函数作进一步的学习

根据抽象屏障原则，我们这里只需要关心它是如何初始化一个内存池即可

我们根据注释分析得到实际上的内存池内存布局：

1
2
3
4
5
内存池的布局：
+--------------------------------------------------------------------
|     页面元数据区域        |    对齐填充     |      实际可用内存区域      |
| (struct page 数组)      |    (未使用)     |    (用于分配的物理内存)    |
+------------------------+-------------------------------------------

源码的工作可以分成三个阶段：

  • 初始化物理内存池：根据传入的参数设置物理内存池的相应数据成员，这里的 BUDDY_PAGE_SIZE 是 0x1000，也即 4KB
  • 初始化空闲链表：用一个 for 循环将每个阶的空闲链表均初始化，这里首先将每个链表的空闲数设为 0，同时用初始化函数 init_list_head 将这个链表节点的首尾都连到自己身上
  • 初始化页表元数据：先用 memset 将这块内存全部清零；再用 for 循环溜一遍，利用指针运算初始化每个页表相应数据；最后再依次 free 每个物理页表，这里自然会涉及到后面的 merge 操作，并最终得到一个全部空闲的内存池

可以看见，chcore 中实际的设计和书上提到的基本一致，不过书上的介绍做了一定的简化

get_buddy_chunk

找呀找呀找朋友，找到一个伙伴块

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static struct page *get_buddy_chunk(struct phys_mem_pool *pool,
                                    struct page *chunk)
{
        vaddr_t chunk_addr;
        vaddr_t buddy_chunk_addr;
        int order;

        /* Get the address of the chunk. */
        chunk_addr = (vaddr_t)page_to_virt(chunk);
        order = chunk->order;
        /*
         * Calculate the address of the buddy chunk according to the address
         * relationship between buddies.
         */
        buddy_chunk_addr = chunk_addr
                           ^ (1UL << (order + BUDDY_PAGE_SIZE_ORDER));

        /* Check whether the buddy_chunk_addr belongs to pool. */
        if ((buddy_chunk_addr < pool->pool_start_addr)
            || ((buddy_chunk_addr + (1 << order) * BUDDY_PAGE_SIZE)
                > (pool->pool_start_addr + pool->pool_mem_size))) {
                return NULL;
        }

        return virt_to_page((void *)buddy_chunk_addr);
}

解析

由伙伴块的定义可知，互为伙伴的两个块，它们的内存地址仅有一位不同，且该位由 order 决定

于是这块代码的核心便在于如何由位运算得到伙伴块的地址，首先，我们有：

1
2
块A的伙伴是块B = 块A的地址 ^ size
块B的伙伴是块A = 块B的地址 ^ size

于是我们可以由 order 和 BUDDY_PAGE_SIZE_ORDER（这里是 12，因为一个页的大小是 4KB）得到 size 的大小：

1
(1UL << (order + BUDDY_PAGE_SIZE_ORDER))

再做一个异或，就得到了相应的伙伴块地址。接下来的事情，就交给辅助函数！

buddy_get_pages

现在让我们看看一次完整的向伙伴系统申请内存的流程是怎样的！

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
struct page *buddy_get_pages(struct phys_mem_pool *pool, int order)
{
        int cur_order;
        struct list_head *free_list;
        struct page *page = NULL;

        if (unlikely(order >= BUDDY_MAX_ORDER)) {
                kwarn("ChCore does not support allocating such too large "
                      "contious physical memory\n");
                return NULL;
        }

        lock(&pool->buddy_lock);

        /* Search a chunk (with just enough size) in the free lists. */
        for (cur_order = order; cur_order < BUDDY_MAX_ORDER; ++cur_order) {
                free_list = &(pool->free_lists[cur_order].free_list);
                if (!list_empty(free_list)) {
                        /* Get a free memory chunck from the free list */
                        page = list_entry(free_list->next, struct page, node);
                        list_del(&page->node);
                        pool->free_lists[cur_order].nr_free -= 1;
                        page->allocated = 1;
                        break;
                }
        }

        if (unlikely(page == NULL)) {
                kdebug("[OOM] No enough memory in memory pool %p\n", pool);
                goto out;
        }

        /*
         * Split the chunk found and return the start part of the chunck
         * which can meet the required size.
         */
        page = split_chunk(pool, order, page);

out:
        unlock(&pool->buddy_lock);
        return page;
}

解析

重点可以看看伙伴系统是如何查找满足要求的空闲块的：

1
2
3
4
5
6
7
8
9
10
11
12
/* Search a chunk (with just enough size) in the free lists. */
for (cur_order = order; cur_order < BUDDY_MAX_ORDER; ++cur_order) {
        free_list = &(pool->free_lists[cur_order].free_list);
        if (!list_empty(free_list)) {
                /* Get a free memory chunck from the free list */
                page = list_entry(free_list->next, struct page, node);
                list_del(&page->node);
                pool->free_lists[cur_order].nr_free -= 1;
                page->allocated = 1;
                break;
        }
}

从查询要求提供的 order 开始，一级一级向上查找，如果没有则向上加一级，如果有则操作链表，取出这块空闲块，并同时设置空闲链表的相应参数，退出循环

一个可能的例子如下：

1
2
3
4
5
6
假设要申请 order=2 (16KB) 的内存：

1. 先查找 order=2 的空闲链表
2. 如果没有，查找 order=3 的空闲链表
3. 如果没有，继续查找更大的空闲链表
4. 直到找到可用的内存块或达到最大阶数

至于裂开的操作，我们马上就会讲到

buddy_free_pages

和 get 操作类似，我们现在来看看 free 操作是如何进行的

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void buddy_free_pages(struct phys_mem_pool *pool, struct page *page)
{
        int order;
        struct list_head *free_list;

        lock(&pool->buddy_lock);

        BUG_ON(page->allocated == 0);
        /* Mark the chunk @page as free. */
        page->allocated = 0;
        /* Merge the freed chunk. */
        page = merge_chunk(pool, page);

        /* Put the merged chunk into the its corresponding free list. */
        order = page->order;
        free_list = &(pool->free_lists[order].free_list);
        list_add(&page->node, free_list);
        pool->free_lists[order].nr_free += 1;

        unlock(&pool->buddy_lock);
}

解析

get 还需要查询是否有空闲块，而 free 则简单多了——直接设置参数后 merge 即可！最后不要使用链表操作将这个块放进内存池的空闲链表里

同样的，加锁和去锁在这里也少不了，它们是并发安全性的保证

下面我们就讲解裂开和合并的具体实现，也是伙伴系统最关键的地方

spilt_chunk

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
static struct page *split_chunk(struct phys_mem_pool *pool, int order,
                                struct page *chunk)
{
        struct page *buddy_chunk;
        struct list_head *free_list;

        /*
         * If the @chunk's order equals to the required order,
         * return this chunk.
         */
        if (chunk->order == order)
                return chunk;

        /*
         * If the current order is larger than the required order,
         * split the memory chunck into two halves.
         */
        chunk->order -= 1;

        buddy_chunk = get_buddy_chunk(pool, chunk);
        /* The buddy_chunk must exist since we are spliting a large chunk. */
        if (buddy_chunk == NULL) {
                BUG("buddy_chunk must exist");
                return NULL;
        }

        /* Set the metadata of the remaining buddy_chunk. */
        buddy_chunk->order = chunk->order;
        buddy_chunk->allocated = 0;

        /* Put the remaining buddy_chunk into its correspondint free list. */
        free_list = &(pool->free_lists[buddy_chunk->order].free_list);
        list_add(&buddy_chunk->node, free_list);
        pool->free_lists[buddy_chunk->order].nr_free += 1;

        /* Continue to split current chunk (@chunk). */
        return split_chunk(pool, order, chunk);
}

解析

注意该函数接受的参数： order 指的是最后要得到的内存块的 order，这一点也可以在上面申请内存的函数中对该函数的调用发现

函数整体上采用尾递归的设计，每次执行时先判断边界条件，随后再进行具体的单次分裂的操作

下面是对于其逻辑的具体分析：


flowchart TD
A[开始分裂] --> B{chunk->order == order?}
B -->|是| C[返回当前块]
B -->|否| D[chunk->order -= 1]
D --> E[获取伙伴块]
E --> F{伙伴块存在?}
F -->|否| G[报错返回 NULL]
F -->|是| H[设置伙伴块元数据]
H --> I[将伙伴块加入空闲链表]
I --> J[递归分裂当前块]
J --> B

以将 16KB 分裂为 4KB 为例，我们可以用一个示意图来描述这个过程。此处粉色块表示被加入空闲链表的伙伴块，白色块表示继续递归分裂的块，直到拿到我们想要的块


graph TD
subgraph "初始状态 order=2 16KB"
A[16KB 块]
end

    subgraph "第一次分裂 order=1"
        B[8KB块] --- C[8KB伙伴块]
    end

    subgraph "第二次分裂 order=0"
        D[4KB块] --- E[4KB伙伴块]
        F[8KB块]
    end

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F

    style F fill:#f9f,stroke:#333
    style E fill:#f9f,stroke:#333

最后我们再来看合并块的实现

merge_chunk

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/* The most recursion level of merge_chunk is decided by the macro of
 * BUDDY_MAX_ORDER. */
static struct page *merge_chunk(struct phys_mem_pool *pool, struct page *chunk)
{
        struct page *buddy_chunk;

        /* The @chunk has already been the largest one. */
        if (chunk->order == (BUDDY_MAX_ORDER - 1)) {
                return chunk;
        }

        /* Locate the buddy_chunk of @chunk. */
        buddy_chunk = get_buddy_chunk(pool, chunk);

        /* If the buddy_chunk does not exist, no further merge is required. */
        if (buddy_chunk == NULL)
                return chunk;

        /* The buddy_chunk is not free, no further merge is required. */
        if (buddy_chunk->allocated == 1)
                return chunk;

        /* The buddy_chunk is not free as a whole, no further merge is required.
         */
        if (buddy_chunk->order != chunk->order)
                return chunk;

        /* Remove the buddy_chunk from its current free list. */
        list_del(&(buddy_chunk->node));
        pool->free_lists[buddy_chunk->order].nr_free -= 1;

        /* Merge the two buddies and get a larger chunk @chunk (order+1). */
        buddy_chunk->order += 1;
        chunk->order += 1;
        if (chunk > buddy_chunk)
                chunk = buddy_chunk;

        /* Keeping merging. */
        return merge_chunk(pool, chunk);
}

解析

有了对分裂块过程的了解，那么合并块理解起来就更简单了：同样是基于尾递归的实现，每次执行时先判断当前块是否已经达到最大的阶数 or 它的伙伴已经不在了，然后再执行相应操作，最后递归处理

我们以一张示例图结束伙伴块之间的羁绊


flowchart TD
A[开始合并] --> B{是否最大 order?}
B -->|是| C[返回当前块]
B -->|否| D[获取伙伴块]
D --> E{伙伴块存在?}
E -->|否| C
E -->|是| F{伙伴块已分配?}
F -->|是| C
F -->|否| G{伙伴块 order 相同?}
G -->|否| C
G -->|是| H[从空闲链表移除伙伴块]
H --> I[增加两个块的 order]
I --> J[选择较小地址块]
J --> K[递归继续合并]
K --> A

注意这里判断伙伴块阶数相同的操作，实际上是看伙伴块是否依然作为一个整体空闲着存在，而不是已经裂开了

同样以 4KB——16KB 为例，介绍一次典型的合并过程


graph TD
subgraph "初始状态 order=0"
A[4KB 块] --- B[4KB 伙伴块]
C[4KB 块] --- D[4KB 伙伴块]
end

    subgraph "第一次合并 order=1"
        E[8KB块] --- F[8KB块]
    end

    subgraph "第二次合并 order=2"
        G[16KB块]
    end

    A --> E
    B --> E
    C --> F
    D --> F
    E --> G
    F --> G

    style A fill:#f9f,stroke:#333
    style B fill:#f9f,stroke:#333
    style C fill:#f9f,stroke:#333
    style D fill:#f9f,stroke:#333

这样便完成了对 merge 操作的实现的介绍与解析

ChCore > 内存管理 > 物理内存管理
#OS #ChCore #Buddy System
Buddy System
http://example.com/2025/02/11/BuddySys/
作者
思源南路世一劈
发布于
2025年2月11日
许可协议