buddy memory allocation相关整理

概述

wiki上的定义:

The buddy memory allocation technique is a memory allocation algorithm that divides memory into partitions to try to satisfy a memory request as suitably as possible. This system makes use of splitting memory into halves to try to give a best fit.

伙伴内存分配技术是一种内存分配算法，它将内存划分为多个分区，以尝试尽可能适当地满足内存请求。 该系统利用将内存分成两半来尝试提供最佳匹配。

算法

伙伴系统有多种形式； 将每个块细分为两个较小块的块是最简单，最常见的一种。
选定块的大小要根据实际情况选取，太小则需要更多的内存记录跟踪内存分配， 太大又容易产生空间浪费,另外，就是如果选择2的次幂单位的话， 最大的块有可能不会覆盖整个内存.

例子

同样是wiki的例子，申请的内存调整了下

1. 初始化状态，每块64K， 最大的块包含 2⁴ 个块, 一个4阶块.
2. 程序A请求内存34K，0阶块,过程如下:
   1. 没有可用的0阶块，因此拆分了4阶块，创建了两个3阶块。
   2. 仍然没有可用的0阶块，因此拆分了第一个3阶块，创建了两个2阶块。
   3. 仍然没有可用的0阶块，因此拆分了第一个2阶块，创建了两个1阶块。
   4. 仍然没有可用的0阶块，因此拆分了第一个1阶块，创建了两个0阶块。
3. 程序B请求内存66K，1阶块。1阶块可用，因此将其分配给B。
4. 程序C请求内存35K，0阶块。0阶块可用，因此将其分配给C。
5. 程序D请求内存67K，1阶块,过程如下:
   1. 没有可用的1阶块，因此拆分了2阶块，创建了两个1阶块。
   2. 有可用的1阶块，因此将其分配给D。
6. 程序B释放其内存，释放一个1阶​​块。
7. 程序D释放其内存。
   1. 释放一个1阶块。
   2. 由于新释放的块的伙伴块也是空闲的，因此将两者合并为一个2阶块。
8. 程序A释放其内存, 释放一个0阶块。
9. 程序C释放其内存, 释放一个0阶块。
   1. 释放一个0阶块。
   2. 由于新释放的0阶块的伙伴块也是空闲的，因此将两者合并为一个1阶块。
   3. 由于新形成的1阶块的伙伴块也是空闲的，因此将两者合并为一个2阶块。
   4. 由于新形成的2阶块的伙伴块也是空闲的，因此将两者合并为一个3阶块。
   5. 由于新形成的3阶块的伙伴块也是空闲的，因此将两者合并为一个4阶块。

过程整理为:

• 分配内存
  1. 寻找合适大小的内存块(最小2k块，该块大于或等于请求的内存)
     1. 如果找到，它将分配给程序
     2. 如果没有，它将尝试创建合适的内存块。 系统通过尝试以下操作来做到这一点：
        1. 将大于请求的内存大小的可用内存块拆分为一半
        2. 如果达到下限，则分配该内存量
        3. 返回步骤1（寻找合适大小的内存块）
        4. 重复此过程，直到找到合适的内存块
• 释放内存
  1. 释放内存块
  2. 看一下邻近的块-它是否释放
  3. 如果是这样，则将两者结合起来，然后返回到步骤2并重复此过程，直到达到上限（所有内存都已释放）或遇到非空闲邻居块为止

实现

Linux 物理内存管理

Linux物理内存管理:初始化时期，使用简单的内存分配方式bootmem,memblock来管理内存，完成初始化工作后，再转交给伙伴系统来管理物理页。

1. 是针对页进行分配的算法，也就是分配的最小单位是一个页;
2. 根据使用用途，以链表的形式存放在不同的ZONE类型的数组里。
3. ZONE又被分配到不同节点pglist_data上，主要是针对NUMA内存模型设计， SMP内存模型的架构只有一个节点。

• 数据结构 :

typedef struct pglist_data {
    struct zone node_zones[MAX_NR_ZONES];
    struct zonelist node_zonelists[MAX_ZONELISTS];
    int nr_zones;
  ...
};

struct zone {
    struct free_area    free_area[MAX_ORDER];
    unsigned long       flags;
    spinlock_t      lock;
    ...
}

struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long       nr_free;
};

再具体管理物理内存页的过程中，Linux内核设计上考虑到了实际的的应用场景: 对内存进行分类MIGRATE_* , 进行内存迁移,这个类型内存不够了可以从其他备选类型中再申请; 设置缓存分配页面per_cpu_pageset等等。

用linux的改一个

下面参考Linux 伙伴系统简化一个版本演示一下wiki上的伙伴系统的例子。

1. 使用alloc_pages分配

alloc_pages -> alloc_pages_current->__alloc_pages_nodemask ->rmqueue->__rmqueue_smallest->expand

1. 使用free_pages释放内存

free_pages-> __free_pages -> free_the_page -> __free_pages_ok -> free_one_page->__free_one_page

1. 伙伴系统初始化, 涉及到初始的内存从哪里来

mem_init -> memblock_free_all -> free_low_memory_core_early-> __free_memory_core -> memblock_free_pages -> __free_pages_core -> __free_pages

代码有些长, 放到github上了 https://github.com/weida/buddytest

输出结果：

[root@centosgpt buddylinux]# ./buddytest
     |2^4
 step| 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K |
 1   |2^4
 2   |2^4
     |2^3                                            |2^3
     |2^2                    |2^2                    |2^3
     |2^1        |2^1        |2^2                    |2^3
     |2^0  |2^0  |2^1        |2^2                    |2^3
 2   |A:2^0|2^0  |2^1        |2^2                    |2^3
 3   |A:2^0|2^0  |2^1        |2^2                    |2^3
 3   |A:2^0|2^0  |B:2^1      |2^2                    |2^3
 4   |A:2^0|2^0  |B:2^1      |2^2                    |2^3
 4   |A:2^0|C:2^0|B:2^1      |2^2                    |2^3
 5   |A:2^0|C:2^0|B:2^1      |2^2                    |2^3
     |A:2^0|C:2^0|B:2^1      |2^1        |2^1        |2^3
 5   |A:2^0|C:2^0|B:2^1      |D:2^1      |2^1        |2^3
 6   |A:2^0|C:2^0|B:2^1      |D:2^1      |2^1        |2^3
     |A:2^0|C:2^0|B:2^1      |D:2^1      |2^1        |2^3
 6   |A:2^0|C:2^0|2^1        |D:2^1      |2^1        |2^3
 7   |A:2^0|C:2^0|2^1        |D:2^1      |2^1        |2^3
     |A:2^0|C:2^0|2^1        |2^1        |2^1        |2^3
     |A:2^0|C:2^0|2^1        |2^2                    |2^3
 7   |A:2^0|C:2^0|2^1        |2^2                    |2^3
 8   |A:2^0|C:2^0|2^1        |2^2                    |2^3
     |2^0  |C:2^0|2^1        |2^2                    |2^3
 8   |2^0  |C:2^0|2^1        |2^2                    |2^3
 9   |2^0  |C:2^0|2^1        |2^2                    |2^3
     |2^0  |2^0  |2^1        |2^2                    |2^3
     |2^1        |2^1        |2^2                    |2^3
     |2^2                    |2^2                    |2^3
     |2^3                                            |2^3
     |2^4
 9   |2^4

参考及引用

Buddy memory allocation
How to add the mathematical symbol for ‘power’ (like X ^ 2) to a question?
buddy-system-内核物理页管理的实现
godspeed1989/buddy_allocator