Linux 使用 buddy system 来管理物理内存的初衷是什么？

[zyearn]

最近看了一下 xv6 的源码，它是用空闲链表来管理物理内存的，如果内核需要内存直接从这个链表上分。

然后去看了下 linux 的管理方式，是用 buddy system 来管理的，数组第 i 项存的是指向连续的 2^i 页(4K)的指针。然后在一个问题上卡住了：

buddy system 的设计和提出是为解决碎片问题的，可是什么情况下需要分配 i>=1（即连续2页或以上）的物理页呢？因为页表的存在，所以虚拟地址空间连续，物理地址完全可以是碎片啊，好像应用程序没有需要 n 个连续物理页的需求。

那为什么还需要 buddy system ？直接用链表管理好像没有额外的 overhead 吧？

现在想到的一个可能的应用场景是大页（ HugePage ），需要分配连续的物理内存。

[bengol]

1. DMA 是一种需求场景，不过不常见
2. 《 ULK 》中提到最主要的目的是避免 tlb 的频繁刷新，减少访问内存的次数
3. 你说的大页，也是为了减少 tlb 的刷新频率
欢迎讨论

[Andiry]

1. 如上所说， DMA 不支持非连续物理页面
2. 连续的虚拟地址可以减少页表 /页目录项数，提高 TLB 命中率
3. 链表管理的 overhead ：过多的分配 /释放会使链表长度增加，内存碎片化，从而增加分配的 overhead 。我没看过 xv6 的实现，假设它用的是简单的双向链表。

[zyearn]

@bengol 感谢回复，特地去看了下 ULK 的相关章节，作者总结了 3 个主要原因：

1. 有些时候连续物理页是必要的，比如 DMA

2. Even if contiguous page frame allocation is not strictly necessary, it offers the big advantage of leaving the kernel paging tables unchanged. What ’ s wrong with modifying the Page Tables? As we know from Chapter 2, frequent Page Table modifications lead to higher average memory access times, because they make the CPU flush the contents of the translation lookaside buffers.

3. 实现 hugepage ，减少了 TLB 表项从而降低 miss rate

其中第二点不是看得很懂，为什么会使 kernel paging tables unchanged ？和你说的 2 是一个意思吗？

@Andiry 感谢回复

请问你的说 2 指的是 hugepage 吗？只有 hugepage 才会减少页表 /页目录项数

另外， xv6 里面的链表里指针指向的 object 都是一个 4k 的页，并且这个指针存在空闲页的开头 8bytes ，所以没有额外的空间复杂度；分配的时间复杂度也是 O(1)，因为直接从链表头拿了。反而 buddy system 的 overhead 比链表高不少，因为它有频繁的合并和分裂内存的操作。所以链表的缺点就是没法分配连续的物理页面了，然后 buddy 就是对它的改进，是这样的吧

[adadada]

@zyearn 关于第二点： Linux kernel (以及其它很多操作系统内核的设计中) 会尽可能的将物理地址空间线性的映射到内核的虚拟地址空间 (例如 32 bit Linux kernel 会将物理内存的 896 MB 以下部分线性映射到内核虚拟地址空间 0xC000000 开始的部分)。当 kernel 给一个大于一页的内核对象分配内存时，如果它能够找到足够存放这个对象的连续物理页，它只需要将这些物理页的起始物理地址加上一个偏移就能够获得对应的虚拟地址，因为这部分已经在前面说的线性映射中映射好了。相对的， kernel 也可以选择将多个离散的物理页通过内核页表映射拼成连续的虚拟内存页，但是此时就需要修改和刷新内核页表。

另外， xv6 中的物理内存分配器页可以支持分配连续物理页，简单的说就是遍历链表去找满足要求的物理页，但是这个开销就太大了 (时间复杂度好像是 O(n)， n 是空闲内存页数)，而且会带来比较严重的 external fragements 。而对于 buddy allocator ，分配的开销应该是 O(1)，虽然 free 的开销会比较大但是可以比较好的避免 external fragements 。所以相对通过单一链表管理物理页分配的方法， buddy allocator 的改进应该是能够通过更好的连续物理页的分配。

[zyearn]

@adadada 写得很好，瞬间想清楚了很多，谢谢。有一个问题：“ leave kernel paging tables unchanged ” 这个动作是不是一个几乎必须的操作？否则的话需要修改所有进程的 kernel page table 了，开销太大了。

[Andiry]

@zyearn kernel paging table 不变，所有进程共享

此外，链表管理的缺点：
1. 没有 scalability ，操作链表需要加锁
2. 分配大量 page 是个 O(n)的过程，因为需要跟着链表走，一次只能分配一个 page
3. Cache 不友好，每次都要跳转到一个新的 page 去读首地址，如果这个 page 不在 cache 里还需要做 memory access

[zyearn]

@Andiry 谢谢提醒，稍微一想发现，因为多级页表的存在，所以只要复制第一级 table 中 kernel 范围内的指针，就可以实现 kernel page table 共享了。

[zealot0630]

@Andiry 连续内存也无法减少页表数量，除非用 4M 页
@zyearn x86 的 TLB 是很低效的 CR3/PDE/PTE 的任何变化都可能导致 TLB 失效

Linux 不仅仅是为 x86 设计的 要真正了解 TLB ，去看 ARM 和 MIPS ， ARM/MIPS 的一条 TLB 能处理 2^N 大小的页，不像 x86 是 4kb 钉死的

[adadada]

@zealot0630 按照 Intel SDM 上 “ Details of TLB Use ” 一节中的说法 "If the paging structures specify a translation using a page larger than 4 KBytes, some processors may cache multiple smaller-page TLB entries for that translation"，应该是部分 Intel x86 CPU 的 TLB 只能处理 4K 页。至少 Haswell 的 L1 DTLB 可以处理 4K ， 2M 和 1G 的页， L2 TLB 可以处理 4K 和 2M 的页。倒是更老的 SandyBridge 的 L2 TLB 只能处理 4K 的页。