内存管理：内存分配

本文参考OSDev Wiki上关于“内存分配”的介绍，原文地址：https://wiki.osdev.org/Memory_Allocation

本文讨论的是从进程已可用的内存中进行分配（例如 malloc() 和 new()）。关于物理页框的分配，请参见 “Page Frame Allocation”。

内核最基本的功能之一是内存管理，即内存的分配与释放。

在最初阶段，内核是系统中唯一的进程。但它并非独占整个地址空间：BIOS 数据结构、内存映射的硬件寄存器等已经占据了部分地址空间。内核启动后首先需要做的事情之一，就是记录哪些物理内存区域可供使用，哪些应被视为“已占用”。

随后，可用的空闲空间将被用于内核数据结构、应用程序的二进制文件、它们的堆与栈等——内核需要一个函数来将某段内存标记为已保留，并将该内存提供给需要它的进程。在 C 标准库中，这由 malloc() 和 free() 负责；在 C++ 中则对应 new() 和 delete()。

概述

一个操作系统包含许多内存管理层。每一层都构建在前一层之上。从整体来看：

• RAM 由物理内存管理器（Physical Memory Manager，PMM）分配，PMM 通常是一个页框分配器（其他常见选择有 SLAB 和伙伴分配器）。
• 页（pages） 被虚拟内存管理器（Virtual Memory Manager，VMM）分配到地址空间中（通常通过 sbrk() 或 mmap() 系统调用）。
• 随后，可用的地址空间由用户态的分配器管理，通常称为 malloc()，这正是本节的主题。

内核堆管理非常类似，具有相同抽象，但使用不同函数：

• 最底层使用与用户态相同的 PMM。
• 内存通常通过一个特殊函数映射到内核地址空间，不需要系统调用来提升权限等级。
• 内核堆分配通过 kmalloc() 完成，其行为与 malloc() 类似，但定义在内核库中，而不是 libc。

可以看到，VMM 之间唯一的区别在于：由 PMM 分配的页应使用哪些页表进行映射（用户空间 vs. 内核空间）。一些保护位（如 supervisor page）也有所不同，但其他步骤完全一致。

顶层的内存管理也非常相似，唯一的不同在于：当管理器耗尽虚拟内存时，VMM 使用哪个回调函数。这意味着，只要替换其内部使用的该回调函数，你可以将任意已有的内存分配器用作 kmalloc()。

因此，内存分配过程经历如下步骤：

1. 是否有足够的空闲虚拟内存？
2. 若有，使用某种结构记录内存分配状态（取决于具体分配器）
3. 若无，则请求 VMM 扩大可用地址空间（sbrk/mmap/mapkernelheap 等）
4. VMM 进一步调用 PMM 分配 RAM
5. 新分配的 RAM 由 VMM 记录到相应的页表中
6. 回到步骤 2

步骤 3 到 5 速度较慢（主要因为涉及权限级别切换），因此内存分配器倾向于尽量减少这些调用，并尽可能重用其已经映射的地址空间中的内存。

一个非常非常简单的内存管理器

你能实现的最简单方法是 WaterMark 分配器。只需记录当前已分配到的位置，完全不考虑“释放”这一概念。

           before ...
                                                          <-N-->
   +----+-----+--+--------//--+             +----+-----+--+----+---//--+
   |##A#|##B##|C#|  free      |             |##A#|##B##|C#|##D#|free   |
   +----+-----+--+---------//-+             +----+-----+--+----+---//--+
                 ^freebase    ^freetop                    ^d   ^fbase  ^ftop

当为 D 分配 N 字节时，只需检查 freetop - freebase > N，然后将 freebase 增加 N。就是这么简单。

现在，如果你需要释放内存，最简单的方案之一是在被释放区域的起始位置放置一个描述符，使其可以被插入到“空闲区链表”中。保持该链表按地址排序，可以帮助你识别连续的空闲区域，并允许将它们合并为更大的空闲区。

      first free                        Structure of a   +--.--.--.--+    +---> +-- ...
        \/                              free zone        |F  R  E  E |    |     | FREE
   +----+-----+--+----+---+-----//--+                    |nextfreeptr|----+
   |##A#|free |C#|free|#E#|   free  |               <----|prevfreeptr|
   +----+-|---+--+-|--+---+-----//--+                    | zone size |
          +-next>--+                                     +///////////+

固定大小分配

对固定大小的内存块进行分配与释放极其简单。你可以将所有空闲内存视为一个链表的节点：

• 分配内存时，从链表头部取出一个节点；
• 释放内存时，将其放回链表头部。

这样分配与释放都具有常数时间，并且不存在碎片化。

在真实世界中，程序通常会分配不同大小的内存块，因此不太可能完全依赖此方法。

然而，从理论上讲，一个微内核可以被设计为所有内存结构大小完全一致（例如 Process 结构体、Thread 结构体、Message 结构体等）。这会非常快速且高效。

在这个背景下，大多数 Lisp 实现使用一种单一的 “box-and-pointer” 基本数据类型。该类型是包含两个值的结构，通常是 pointer/pointer 或 atom/pointer（atom 指数值）。在 32 位系统中，这类结构占用 8 字节。所有其他数据结构（列表、树、对象等）都构建在此基础类型之上。因此，Lisp 系统中的内存分配非常快速。

深入继续的提示

• 在某些情况下，尤其是处理对象时，你需要分配许多固定大小的对象。为此类对象创建预先划分的大块内存池是明智的做法。
• 在分配的对象前面隐藏一个头部存储块大小，会让设计更简单，这样调用 free 时不需要知道对象大小。通常，这个隐藏的头部就放在 malloc 返回块的正前方。
• 在宿主操作系统中设计内存分配器远比在内核中容易。如果你实现了完整的 malloc 接口（在 Linux 上，malloc、calloc、realloc 和 free 就够了），一个很好的健壮性测试是：将你的 malloc 编译成共享库，然后通过 LD_PRELOAD 强制让一个大型软件（例如整个宿主操作系统源码树的构建过程）使用你的 malloc。
• 调试时，“F R E E”“U S E D” 之类的魔法字样会让你的生活更轻松。TimRobinson 甚至使用 32 位来存储请求者的地址，因此你可以看到“这是一个 N 字节的块，由 MySillyFunction() 第 3405 行申请”。

内存与微内核

在微内核环境中，会出现这样的问题：内存管理到底应该放在哪里？如果指堆管理，应给内核一个专用的分配器和一块专用的内存区域——你可能需要两个：一个用于消息，一个用于其他所有内容。

内存管理的另一部分：进程地址空间管理，包括跟踪已使用的页（是的，让我们谈谈分页，它很棒、很优雅，让人脚底发暖的感觉）并按需向进程分配内存，你可以将这部分拆分开。更确切地说，你必须将此任务拆分——或者将内存管理的所有部分都放在内核中以简化设计。推荐的进程地址空间管理方法是：以每进程为单位处理。某个进程需要内存：就为它分配内存并返回给该进程。这样你的页分配例程可以保持简单直接。

在执行这些内存分配与释放任务时，你应考虑执行这些操作的任务需要能够在必要时切换到相应地址空间（即加载所需的页目录并执行操作——它就是这么一只滑不溜秋的小黄鼠狼）。认真考虑这些因素，并投入大量脑力设计它们。这是值得精心工程化的部分。

移植现有的内存分配器

编写自己的内存分配器并非总是可取或可行。编写一个高效的分配器可能本身就是一个完整项目。幸运的是，将现有内存分配器移植到你的操作系统（用于内核或用户态）非常容易。

使用现有分配器的优点包括：移植速度远比从零开始编写快，尤其当你希望专注于 OS 其他部分时；它们通常经过充分测试，因此你无需调试分配器；移植的工作量非常小；最后，别人已经完成了让它快速、可扩展、稳定等方面的艰苦工作。

移植内存分配器相当简单。大多数只包含一两个源文件或头文件。你必须实现的功能是：为分配器提供页面的分配与释放，以便内存分配器有内存可用。

某些分配器使用一组钩子，以便通过“页”为单位向内核请求内存。它们会在源码中存储一个常量，用于表示页面大小（例如 #define PAGE_SIZE 4096 表示 4KB 页），从而知道每次应请求多少页。对这类分配器，你必须实现：

• void *alloc_page(size_t pages) —— 分配连续的 pages 个虚拟内存页，并返回该组起始地址。
• void free_page(void *start, size_t pages) —— 从 start 开始释放连续的 pages 个虚拟内存页回内核。

此外，某些分配器要求你实现锁定功能，以确保分配器的关键区段不会被多个线程同时执行。典型函数如下：

• void wait_and_lock_mutex() —— 在进入关键区段前锁定互斥量。最简单的“锁”方法是禁用中断，适合作为起点；为了获得最佳性能，推荐实现自旋锁。
• void unlock_mutex() —— 离开关键区段后解锁互斥量。你要么重新启用中断，要么清除自旋锁，使等待的线程可进入关键区段。

选择内存分配器

可选择的内存分配器非常多。不存在“完美”的内存分配器，因为不同分配器试图实现的目标不同。而这些目标通常相互冲突，因此不同的分配器会做出不同的折中。

一些分配器具有以下特点：

• ……快速。 它们每秒能执行最多的分配和释放操作。“快速”是上下文相关的，在某些情形（如大量大块分配）中快速的分配器，在其他情形（大量小块频繁的分配与释放）中可能并不快。

• ……空间高效。 当其他分配器可能需要将内存对齐到页边界，或内部维护占用数兆字节的巨大结构时，这类分配器确保所有内存都被紧密利用，不浪费任何字节。这在可用 RAM 很少时尤其重要。

• ……稳定。 其他分配器可能更快，但这些分配器被设计用于长时间运行。它们重点关注最小化内存碎片化，这对运行数月不间断的服务器至关重要。

• ……可扩展。 有些分配器在单线程环境中分配速度很快，但其他线程必须锁等，结果整体效率下降。可扩展的分配器可以在最新的多核 CPU 上，同时处理数百个线程的分配请求，而不会有显著性能损失，并且只需最少的锁。

• ……实时。 某些快速分配器“平均”情况下 75 个周期即可完成一次分配，但偶尔最坏情况可能需要 350 个周期。实时分配器可能保证在不到 200 个周期内返回指针。这在媒体解码和实时系统中非常重要。

可选的分配器众多，因此以下列表远不全面：

• liballoc —— 出色的分配器，最初属于 Spoon OS，设计为能直接插入业余 OS 使用。
• dlmalloc —— Doug Lea 的内存分配器。广泛使用、易移植、通用性强。
• TCMalloc —— 线程缓存 malloc，一种实验性的可扩展分配器。
• nedmalloc —— 非常快速且高度可扩展的分配器，在多线程电子游戏中较为流行，用作默认分配器的替代品。
• ptmalloc —— glibc 中使用的广泛应用分配器，在空间效率与扩展性之间平衡良好。
• jemalloc —— 通用 malloc(3) 实现，强调碎片避免与可扩展并发支持，最早用于 FreeBSD。
• Hoard —— malloc 的可替换实现，可显著提升应用性能，特别是运行在多处理器与多核 CPU 上的多线程程序。
• Bucket —— 面向初学者的简单可替换 malloc，最大优点是文档详尽，不仅有源码注释，还解释其内部工作机制。

参见

教程

• Writing a memory manager

外部链接

• Memory Management 1 —— Tim Robinson 的内存管理系列第一部分
• Memory Management 2 —— Tim Robinson 的内存管理系列第二部分
• Publications about ‘Memory Management’ —— 一些优秀文章的列表
• TLSF: Memory Allocator for Real-Time —— 专为实时需求设计的通用动态内存分配器