内存 buddy 分配器

Linux 在拿到一大块内存后（譬如是64MB内存），先将其看作是好多个连续排列的 4MB 内存。
那么如果程序请求1MB的内存，那么内存分配操作逻辑如下：

• 选中一个 4MB 内存，将其切分为2个2MB的内存
• 2MB太大了，选取一个 2MB 内存切成2个1MB的内存
• 分配1MB内存给程序

这个算法就是所谓的 binary buddy 分配算法。
在 Linux 中，这个二分法最小分割到 4096 字节，也就是一个页的大小。
因此总共有 11 种大小，分别为 4KB，8KB，……4MB。
其中 4KB 为 order 0，4MB 为 order 10.
我们称其 max order 为 12，有些资料会提到这个概念。

以上这些信息可以在 /proc/buddyinfo 上查看，其格式大概是这样：

初始内存，空闲 64MB 内存：分为 16 个4MB。
4K(0) 8K(1) 16K(2) 32K(3) 64K(4) ...                           2M(9)   4M(10)
0     0     0      0      0      0       0       0       0       0       16
分配 1MB 后，空闲 63MB 内存：分为 15个4MB、1个2MB 和 1个1MB。
0     0     0      0      0      0       0       0       1       1       15

实际示例
$ cat /proc/buddyinfo
Node 0, zone      DMA      0      1      0      0      2      1      1      0      1      1      3
Node 0, zone    DMA32      6      2      2      6      3      4      2      3      2      3    432
Node 0, zone   Normal  22980   9813  54346  45837  20375   8005   4476   2776   1399    237  20226
$

buddy 内存的碎片问题

buddy 在上面这种情况下，有些被分为小块内存，那么就会存在内存碎片的问题。
/proc/pagetypeinfo

以上 buddy 管理的是不小于4K 的内存分配，slab 则是管理小于4KB 的内存对象。