Sherlock's blog

有容乃大，无欲则刚

0%

Linux内存管理-伙伴系统分析

发表于
文本分析Linux内核内存管理中伙伴系统的基本逻辑。代码分析基于v6.5-rc3。

基本逻辑

伙伴系统的目的就是为了缓解内存分配中的内存碎片。写过内存分配的人对此有直接的认识，
系统里有一大块内存，不同的用户不断请求和释放不同大小的内存，一个直观的管理办法是，
把这一大块内存按照相同的单位分成大小相等的块，根据请求内存的大小依次从这些块中分配
内存，当大小内存混合分配时，随着内存块的不断分配和释放，小块内存很容易分配的很分散，
导致大块内存分配困难。

1
2
3
4
5
6
7
+---+---+---+---+---+---+---+---+           +---+---+---+---+---+---+---+---+
| a | b | b | b | c | d | d | d |           | a |   |   |   | c |   |   |   |
+---+---+---+---+---+---+---+---+           +---+---+---+---+---+---+---+---+
| d | e | f | f | f | f | g | h |   ---->   |   | e |   |   |   |   | g |   |
+---+---+---+---+---+---+---+---+           +---+---+---+---+---+---+---+---+
| h | h | h | h | h | i | j | j |           |   |   |   |   |   | i |   |   |
+---+---+---+---+---+---+---+---+           +---+---+---+---+---+---+---+---+

如上即使大的内存块释放了，由于小内存块分散分布，我们无法跨越小内存块而分配出大的
内存块来。

我们可以想到的一个朴素逻辑: 小块内存在一个内存块里分，大块内存在另一个内存块里
分，这里所谓的大小内存块可以有很多级。

1
2
3
4
5
6
7
     +---+---+---+---+---+---+---+---+
L0   | a | b | c | d |   |   |   |   |
     +---+---+---+---+---+---+---+---+
L1   | e | e | f | f | g | g |   |   |
     +---+---+---+---+---+---+---+---+
L2   | h | h | h | h | i | i | i | i |
     +---+---+---+---+---+---+---+---+

如上，一个小块内存(可以叫一个page)的分配只在L0的内存块里分，只在L1分配连续两个page，
只在L2分配连续四个page。这样小的内存块天然就被局限在特定的内存区域里了，它们不会
出来捣乱。

但是，这里有个问题，比如L0内存分完了，L1/L2又有内存，如何把L1/L2的内存让出来给L0
用，L0用完后再换给L1/L2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
     +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+
L0   | a |-->| b |-->| c |-->| d |-->| j |-->| k |-->| l |-->| m |
     +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+

     +---+---+   +---+---+   +-------+   +---+---+
L1   | e | e |-->| f | f |-->| g | g |-->|   |   |
     +---+---+   +---+---+   +---+---+   +---+---+   -------------\
                                                                   \
     +---+---+---+---+   +---+---+---+---+                          \
L2   | h | h | h | h |-->| i | i | i | i |                           \      allocated
     +---+---+---+---+   +---+---+---+---+                            \       |
                                                                       v      v

     +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+  +---+
L0   | a |-->| b |-->| c |-->| d |-->| j |-->| k |-->| l |-->| m |-->|   |  |   |
     +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+  +---+

     +---+---+   +---+---+   +-------+
L1   | e | e |-->| f | f |-->| g | g |
     +---+---+   +---+---+   +---+---+

     +---+---+---+---+   +---+---+---+---+
L2   | h | h | h | h |-->| i | i | i | i |
     +---+---+---+---+   +---+---+---+---+

如上，在各个内存区域里，使用链表管理各个内存块，当L0的内存不够用的时候，就从更高
一级的内存域里(如上是L1)把一个大内存块分开，一部分分给用户使用，一部分挂入L0的空闲
内存链表。当L0 allocated内存使用完，返回空闲链表时，如果它的“伙伴”也是空闲的，那么
就可以把他们合并成一个L1的大块，挂回L1的空闲链表，这样分配大内存块时，就可以使用。
注意，伙伴系统里的空闲链表上的是空闲的内存，如上图里为了表示方便，在内存块里写了
字母表示连续分配的内存。

实际上，伙伴系统里一开始并没有给小块内存链表上固定的分内存，就是伙伴系统不是专门
划分出L0/L1/L2的固定内存区域的，伙伴系统在初始化的时候把内存挂在大内存块的链表上，
当需要小内存的时候，再从大内存块一级一级拆出来分到小内存链表上。注意这样的分配方
式并不是小内存块都在连续区域里的，分配的时候还是可能有碎片出现，逻辑上看，伙伴系统
需要尽量先把一个大内存块分完，再拆另外的大内存块。

1
2
3
4
5
6
7
8
9
10

                                           +---+   +---+          +---+   +---+    
L0                                         | 2 |   | 1'|          | 2'|   | 1'|    
                                           +---+   +---+          +---+   +---+    
                                        => +---+---+         => +---+---+        
L1                                         | 3 | 4 |            | 3 | 4 |        
                                           +---+---+            +---+---+        
   +---+---+---+---+  +---+---+---+---+    +---+---+---+---+    +---+---+---+---+
L2 | 1 | 2 | 3 | 4 |->| 5 | 6 | 7 | 8 |    | 5 | 6 | 7 | 8 |    | 5 | 6 | 7 | 8 |
   +---+---+---+---+  +---+---+---+---+    +---+---+---+---+    +---+---+---+---+

如上，分配完块1内存(分配出的内存块用n’表示)，再需要分L0内存时，我们应该把块1的伙伴
块2分配出去使用，而不是去拆L1中更大的块，拆大块内存必要引起碎片化加重。进一步看L0
中有更多的小块可选的时候，应该怎么选择分配出去的小块，看起来可以从链表里任意找，
因为凡是加到链表里的块，它的伙伴一定已经被分配出去了(最大的块除外)。

内存迁移和伙伴系统的关系

内存迁移的基本逻辑。在有虚拟内存的系统里，比如Linux系统，内核给用户呈现的内存语意
在虚拟地址上，也就是说用户针对一个虚拟地址读写数据就可以了，这给内核内部扩展了腾挪
空间，也就是说一个虚拟地址上的数据可能一会保存在一个物理内存上，一会保存在另一个
物理地址上。这里物理页面上数据迁移的动作就叫内存迁移。

内存迁移的一个目的就是提高访问性能，进程可能会在不同核上迁移，如果不同核跨越了NUMA
节点，内存访问的效率会降低，内核通过内存迁移把数据搬移到CPU所在NUMA的内存上，这样
相同NUMA内内存访问效率高。

内存迁移也可以缓解内存上的碎片，比如对于如上从L1拆借到L0的内存(如上中间的图)，我们
可以把块1‘上的数据迁移到其他page上，这样块1就可以释放回伙伴系统，块1可以和块2合并，
块12可以和块34合并，从而拼回L2的块1234。

可以看到，虚拟内存支持的地址空间重映射是内存迁移可以使用的基础，不然都是物理内存，
PA已经给到用户，你再把数据迁移到新的PA上就乱了。可以看到内存迁移包含：1. 数据在
物理内存上的搬移；2. 虚拟地址到物理地址的重映射。我们这里考虑和伙伴系统的关系，
所以，只考虑第一点。一般第一点这样的内存迁移又叫内存规整(memory compaction)。

内存迁移是有成本的，对于有些页可以直接定义为unmovable页，内存迁移不能作用于这些页。

大页和伙伴系统的关系

大页有传统大页和透明大页(THP)，传统大页和伙伴系统没有关系，THP的大页一般是2MB页，
也就是伙伴系统里order是9的页(一个基础页是4KB)，当order为9的内存域里没有内存可分配
时就要通过内存迁移调整出2MB大页。(需要结合代码确定这个逻辑)

代码分析

实际上，如果你用/proc/buddyinfo查看系统一开始buddy系统的信息，会发现内存基本上都
挂在order上最大的空闲链表上，特定order的内存区域不断的从大order内存区域上拆下来。

Linux内核内存管理整体脉络可以参考这里，内存管理的基本数据结构(pglist_data/zone/free_area)，
也在这里有所介绍。

我们分别找下伙伴系统代码的几个关键位置：1. 系统一开始怎么被给到伙伴系统；2. 内存
怎么从伙伴系统分配出去；3. 内存释放到伙伴系统后，怎么合并成大内存。

上面的参考文章里已经指出伙伴系统初始化的代码路径，最后是调用__free_memory_core进行
初始化。没有搞清的逻辑是，free_area里的movable/unmovable等不同迁移属性的内存区域
是否是一开始初始化好一整块的？

alloc_pages是伙伴系统的核心分配函数，顺着往下走可以到get_page_from_freelist，这个
是伙伴系统的核心分配函数，再往下走是慢速路径了，我们这这里不看。

1
2
3
4
5
6
7
8
9
10
11
get_page_from_freelist
  +-> rmqueue
    +-> rmqueue_buddy
      +-> __rmqueue
            /*
             * 这里从伙伴系统的freelist上取节点下来，然后使用__ClearPageBuddy，
             * 标记对应的struct page脱离伙伴系统的管理。
             *
             * 注意__ClearPageBuddy函数是用宏定义在include/linux/page-flags.h里的。
             */
        +-> __rmqueue_smallest

伙伴系统释放内存的核心函数是：free_pages，一路调用到__free_one_page，这个函数实际
执行内存释放和伙伴合并的逻辑。

1
2
3
4
5
6
7
8
9
10
__free_one_page
  +-> while (order < MAX_ORDER) {
            /*
             * 可以看见伙伴系统找buddy的逻辑是很简单的: page_pfn ^ (1 << order)，
             * 其实就是把pfn的最低有效bit反转下。
             */
        +-> find_buddy_page_pfn
      }
  +-> done_merging
    ...

注意, 这里可以看到，伙伴系统并没有固定的数据结构记录谁是谁的buddy，只是每次都用
如上的简单算法直接计算得到buddy，计算只是得到可能的buddy，随后还要用page_is_buddy
再做下最终确认。