内存分配器 101 - 编写一个简单的内存分配器

本文介绍如何在 C 语言中编写一个简单的内存分配器。我们将实现 malloc()、calloc()、realloc() 和 free() 函数。

这是一篇入门级文章，因此我不会详细说明每个细节。这个内存分配器不会特别快速高效，我们也不会调整分配的内存以对齐页面边界，但我们会构建一个可以工作的内存分配器。仅此而已。

如果你想查看完整代码，请访问我的 GitHub 仓库 memalloc。

在开始构建内存分配器之前，你需要熟悉程序的内存布局。一个进程在其自己的虚拟地址空间中运行，该空间与其他进程的虚拟地址空间是独立的。这个虚拟地址空间通常由 5 个部分组成：

代码段 (Text section)：包含处理器要执行的二进制指令的部分。数据段 (Data section)：包含非零初始化的静态数据。BSS 段 (Block Started by Symbol)：包含零初始化的静态数据。程序中未初始化的静态数据会被初始化为 0 并存储在这里。堆 (Heap)：包含动态分配的数据。栈 (Stack)：包含自动变量、函数参数、基址指针副本等。

如图所示，栈和堆是向相反方向增长的。有时数据段、BSS 段和堆段被统称为“数据段”，其末尾由一个名为程序断点 (program break) 或 brk 的指针标记。也就是说，brk 指向堆的末尾。

如果我们要在堆中分配更多内存，需要请求系统增加 brk。同样，要释放内存，我们需要请求系统减少 brk。

假设我们运行的是 Linux（或类 Unix 系统），我们可以使用 sbrk() 系统调用来操作程序断点。

调用 sbrk(0) 会返回当前程序断点的地址。调用 sbrk(x) 并传入一个正值会将 brk 增加 x 字节，从而分配内存。调用 sbrk(-x) 并传入一个负值会将 brk 减少 x 字节，从而释放内存。如果失败，sbrk() 会返回 (void*) -1。

说实话，在 2015 年，sbrk() 并不是我们最好的选择。如今有更好的替代方案，比如 mmap()。sbrk() 并不是真正线程安全的。它只能以 LIFO（后进先出）的顺序增长或缩小。如果你在 macbook 上执行 man 2 sbrk，它会告诉你：

brk 和 sbrk 函数是虚拟内存管理出现之前遗留下来的历史产物。

然而，glibc 的 malloc 实现仍然使用 sbrk() 来分配不太大的内存块。[1]因此，我们将继续使用 sbrk() 来实现我们的简单内存分配器。

malloc()

malloc(size) 函数分配 size 字节的内存，并返回指向已分配内存的指针。我们的简单 malloc 实现如下：

void *malloc(size_t size){ void *block; block = sbrk(size); if (block == (void*) -1)  return NULL; return block;}

在上述代码中，我们使用给定的大小调用了 sbrk()。如果成功，size 字节的内存将在堆上分配。这很简单，不是吗？

棘手的部分是释放这些内存。free(ptr) 函数释放由 ptr 指向的内存块，该指针必须是由之前的 malloc()、calloc() 或 realloc() 调用返回的。但要释放一个内存块，首先需要知道要释放的内存块的大小。在当前方案中，这是不可能的，因为大小信息没有存储在任何地方。因此，我们必须找到一种方法来存储已分配块的大小信息。

此外，我们需要理解操作系统提供的堆内存是连续的。因此，我们只能释放位于堆末尾的内存。我们不能将中间的内存块释放回操作系统。可以将堆想象成一个长条面包，你只能在一端拉伸或收缩它，但必须保持它的完整性。为了解决无法释放非堆末尾内存的问题，我们将区分"释放内存"和"归还内存"。从现在开始，释放一个内存块并不一定意味着我们将内存归还给操作系统。它只是意味着我们将该块标记为空闲。这个被标记为空闲的块可能会在后续的 malloc() 调用中被重用。由于不在堆末尾的内存无法被释放，这是我们唯一可行的方式。

因此，现在我们需要为每个已分配的内存块存储两个信息：    1. 大小    2. 该块是空闲的还是非空闲的？

为了存储这些信息，我们将在每个新分配的内存块前添加一个头部。这个头部将如下所示：

struct header_t { size_t size; unsigned is_free;};

这个想法很简单。当程序请求_size_字节的内存时，我们计算total_size = header_size + size，然后调用sbrk(total_size)。我们使用 sbrk() 返回的内存空间来容纳头部和实际的内存块。头部由内部管理，对调用程序完全隐藏。

现在，我们的每个内存块将如下所示：

我们不能完全确定由我们的 malloc 分配的内存块是连续的。想象一下调用程序使用了外部的 sbrk()，或者在我们的内存块之间有一段通过_mmap()_映射的内存。我们还需要一种方法来遍历我们的内存块（为什么要遍历？我们将在查看_free()_的实现时了解原因）。因此，为了跟踪由我们的 malloc 分配的内存，我们将它们放入一个链表中。我们的头部现在将如下所示：

struct header_t { size_t size; unsigned is_free; struct header_t *next;};

内存块的链表如下图所示：

现在，让我们将整个头部结构体与一个 16 字节大小的 stub 变量一起封装在一个union中。这使得头部最终位于 16 字节对齐的内存地址上。回想一下，union 的大小是其成员中较大的那个。因此，这个 union 保证了头部的末尾是内存对齐的。头部的末尾是实际内存块开始的地方，因此分配器提供给调用者的内存将保持 16 字节对齐。

typedef char ALIGN[16];union header { struct {  size_t size;  unsigned is_free;  union header *next; } s; ALIGN stub;};typedef union header header_t;

我们将使用头指针和尾指针来跟踪链表。

header_t *head, *tail;

为了防止两个或多个线程并发访问内存，我们将实现一个基本的锁机制。

我们将使用一个全局锁，在对内存进行任何操作之前必须先获取该锁，操作完成后必须释放该锁。

pthread_mutex_t global_malloc_lock;

我们的 malloc 函数现在修改为：

void *malloc(size_t size){ size_t total_size; void *block; header_t *header; if (!size)  return NULL; pthread_mutex_lock(&global_malloc_lock); header = get_free_block(size); if (header) {  header->s.is_free = 0;  pthread_mutex_unlock(&global_malloc_lock);  return (void*)(header + 1); } total_size = sizeof(header_t) + size; block = sbrk(total_size); if (block == (void*) -1) {  pthread_mutex_unlock(&global_malloc_lock);  return NULL; } header = block; header->s.size = size; header->s.is_free = 0; header->s.next = NULL; if (!head)  head = header; if (tail)  tail->s.next = header; tail = header; pthread_mutex_unlock(&global_malloc_lock); return (void*)(header + 1);}header_t *get_free_block(size_t size){ header_t *curr = head; while(curr) {  if (curr->s.is_free && curr->s.size >= size)   return curr;  curr = curr->s.next; } return NULL;}

让我来解释一下代码：

我们首先检查请求的 size 是否为零。如果是，则返回 NULL。 对于有效的 size，我们首先获取锁。然后调用 get_free_block() - 它会遍历链表，查看是否存在标记为 free 且能够容纳给定大小的内存块。这里我们采用 first-fit 方法来搜索链表。

如果找到足够大的空闲块，我们只需将该块标记为 not-free，释放全局锁，然后返回指向该块的指针。在这种情况下，header 指针将指向我们通过遍历链表找到的内存块的头部。记住，我们需要向外部隐藏头部的存在。当我们执行 (header + 1) 时，它指向头部结束后的第一个字节。这恰好也是实际内存块的第一个字节，也就是调用者感兴趣的部分。这被强制转换为 (void*) 并返回。

如果没有找到足够大的空闲块，那么我们需要通过调用 sbrk() 来扩展堆。堆需要扩展的大小必须能够容纳请求的 size 以及头部。为此，我们首先计算总大小：total_size = sizeof(header_t) + size;。然后我们请求操作系统增加程序断点：sbrk(total_size)。

在从操作系统获得的内存中，我们首先为头部预留空间。在 C 语言中，不需要将 void* 强制转换为任何其他指针类型，它总是可以安全地提升。这就是为什么我们不需要显式地执行：header = (header_t *)block;我们用请求的 size（不是总大小）填充这个头部，并将其标记为 not-free。我们更新 next 指针、head 和 tail 以反映链表的新状态。如前所述，我们向调用者隐藏头部，因此返回 (void*)(header + 1)。我们确保也释放了全局锁。

free()

现在，我们来看看 free() 应该做什么。free() 必须首先确定要释放的块是否位于堆的末尾。如果是，我们可以将其释放给操作系统。否则，我们只需将其标记为 'free'，希望以后可以重用。

voidfree(void *block){ header_t *header, *tmp; void *programbreak; if (!block)  return; pthread_mutex_lock(&global_malloc_lock); header = (header_t*)block - 1; programbreak = sbrk(0); if ((char*)block + header->s.size == programbreak) {  if (head == tail) {   head = tail = NULL;  } else {   tmp = head;   while (tmp) {    if(tmp->s.next == tail) {     tmp->s.next = NULL;     tail = tmp;    }    tmp = tmp->s.next;   }  }  sbrk(0 - sizeof(header_t) - header->s.size);  pthread_mutex_unlock(&global_malloc_lock);  return; } header->s.is_free = 1; pthread_mutex_unlock(&global_malloc_lock);}

在这里，我们首先获取要释放的内存块的头部信息。我们只需要获取一个指针，该指针位于内存块后方，距离等于头部结构体的大小。因此，我们将 block 强制转换为 header 指针类型，并将其向后移动 1 个单位。header = (header_t*)block - 1;

sbrk(0) 返回当前程序断点（program break）的值。为了检查要释放的块是否位于堆的末尾，我们首先计算当前块的结束位置。结束位置可以通过 (char*)block + header->s.size 计算得出，然后将其与程序断点进行比较。

如果该块确实位于堆的末尾，那么我们可以缩小堆的大小并将内存释放给操作系统。我们首先重置 head 和 tail 指针以反映最后一个块的丢失。然后计算要释放的内存量，这是头部和实际块大小的总和：sizeof(header_t) + header->s.size。为了释放这么多内存，我们使用该值的负数调用 sbrk()。

如果该块不是链表中的最后一个块，我们只需设置其头部的 is_free 字段。这个字段会在 malloc() 实际调用 sbrk() 之前被 get_free_block() 检查。

calloc()

calloc(num, nsize) 函数为包含 num 个元素的数组分配内存，每个元素大小为 nsize 字节，并返回指向已分配内存的指针。此外，内存会被全部初始化为零。

void *calloc(size_t num, size_t nsize){ size_t size; void *block; if (!num || !nsize)  return NULL; size = num * nsize; /* check mul overflow */ if (nsize != size / num)  return NULL; block = malloc(size); if (!block)  return NULL; memset(block, 0, size); return block;}

在这里，我们首先进行乘法溢出的快速检查，然后调用我们的 malloc()， 并使用 memset() 将分配的内存全部清零。

realloc()

realloc() 将给定内存块的大小更改为指定大小。

void *malloc(size_t size){ void *block; block = sbrk(size); if (block == (void*) -1)  return NULL; return block;}0

在这里，我们首先获取内存块的头部信息，并检查该内存块是否已经具有满足请求大小的容量。如果满足，则无需进行任何操作。

如果当前内存块不具备请求的大小，则我们调用 malloc() 来获取一个符合请求大小的内存块，并使用 memcpy() 将内容重新定位到新的更大的内存块中。然后释放旧的内存块。

编译并使用我们的内存分配器

您可以从我的 GitHub 仓库获取代码 - memalloc。我们将编译我们的内存分配器，然后使用它来运行像 ls 这样的实用程序。

为此，我们首先将其编译为库文件。

void *malloc(size_t size){ void *block; block = sbrk(size); if (block == (void*) -1)  return NULL; return block;}1

-fPIC 和 -shared 选项确保编译输出具有位置无关代码（Position-Independent Code），并指示链接器生成适合动态链接的共享对象（shared object）。

在 Linux 系统中，如果将环境变量 LD_PRELOAD 设置为共享对象的路径，该文件将优先于其他库加载。我们可以利用这个技巧优先加载我们编译的库文件，这样后续在 shell 中运行的命令将使用我们实现的 malloc()、free()、calloc() 和 realloc() 函数。

void *malloc(size_t size){ void *block; block = sbrk(size); if (block == (void*) -1)  return NULL; return block;}2

现在，

void *malloc(size_t size){ void *block; block = sbrk(size); if (block == (void*) -1)  return NULL; return block;}3

瞧！这就是我们的内存分配器在为 ls 提供服务。如果您不相信，可以在 malloc() 中打印一些调试信息亲自查看。

感谢您的阅读。欢迎提出所有意见。如果您发现任何错误，请报告。

脚注与参考文献

查看一些内存分配器列表：liballocDoug Lea 的内存分配器.TCMallocptmalloc

[1] GNU C 库：Malloc 可调参数OSDev - 内存分配内存分配器 101 - James Golick