# buddy memory allocation相关整理 Date: 2020-05-29 ### 概述 [wiki](https://en.wikipedia.org/wiki/Buddy_memory_allocation#cite_note-3)上的定义: 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的例子，申请的内存调整了下 | Step | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 1 | 24 | | | | | | | | | | | | | | | | | 2.1 | 23 | | | | | | | | 23 | | | | | | | | | 2.2 | 22 | | | | 22 | | | | 23 | | | | | | | | | 2.3 | 21 | | 21 | | 22 | | | | 23 | | | | | | | | | 2.4 | 20 | 20 | 21 | | 22 | | | | 23 | | | | | | | | | 2.5 | A:20 | 20 | 21 | | 22 | | | | 23 | | | | | | | | | 3 | A:20 | 20 | B: 21 | | 22 | | | | 23 | | | | | | | | | 4 | A:20 | C:20 | B: 21 | | 22 | | | | 23 | | | | | | | | | 5.1 | A:20 | C:20 | B: 21 | | 21 | | 21 | | 23 | | | | | | | | | 5.2 | A:20 | C:20 | B: 21 | | D: 21 | | 21 | | 23 | | | | | | | | | 6 | A:20 | C:20 | 21 | | D: 21 | | 21 | | 23 | | | | | | | | | 7.1 | A:20 | C:20 | 21 | | 21 | | 21 | | 23 | | | | | | | | | 7.2 | A:20 | C:20 | 21 | | 22 | | | | 23 | | | | | | | | | 8 | 20 | C:20 | 21 | | 22 | | | | 23 | | | | | | | | | 9.1 | 20 | 20 | 21 | | 22 | | | | 23 | | | | | | | | | 9.2 | 21 | | 21 | | 22 | | | | 23 | | | | | | | | | 9.3 | 22 | | | | 22 | | | | 23 | | | | | | | | | 9.4 | 23 | | | | | | | | 23 | | | | | | | | | 9.5 | 24 | | | | | | | | | | | | | | | | 1. 初始化状态，每块64K， 最大的块包含 24 个块, 一个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`内存模型的架构只有一个节点。 - 数据结构 : ```C 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` 输出结果： ```C [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](https://en.wikipedia.org/wiki/Buddy_memory_allocation) [How to add the mathematical symbol for 'power' (like X ^ 2) to a question?](https://meta.stackexchange.com/questions/226869/how-to-add-the-mathematical-symbol-for-power-like-x-2-to-a-question) [buddy-system-内核物理页管理的实现](https://ggaaooppeenngg.github.io/zh-CN/2016/08/31/buddy-system-%E5%86%85%E6%A0%B8%E7%89%A9%E7%90%86%E9%A1%B5%E5%88%86%E9%85%8D%E7%9A%84%E5%AE%9E%E7%8E%B0/) [godspeed1989/buddy\_allocator](https://github.com/godspeed1989/buddy_allocator/blob/master/buddy.h)