[博客翻译]用C编写一个简单的池分配器

由 发布于 池分配器C语言内存管理链表联合体
 收藏

原文地址：https://8dcc.github.io/programming/pool-allocator.html


用C语言编写一个简单的池分配器

目录

1. 介绍

我前段时间了解了池分配器，非常喜欢它的简单性和高性能，因此决定自己编写一个。本文最初受到Dmitry Soshnikov的文章的启发。
与malloc类似，池分配器允许用户在运行时分配内存。然而，池分配器比malloc快得多，代价是有一个固定的池大小。它允许用户在O(1)线性时间内分配和释放内存块（从现在起称为块）。此实现还使用很少的内存：在创建池时，会分配一个非常小的Pool结构以及池本身。空闲块用于存储信息，因此内存影响最小。
最后，我想提到的是，本文基于我的ANSI C库libpool，用于池分配。将来，我可能会对该仓库中的代码进行一些小改动，而这些改动不会反映在这里，所以请随时查看。

2. 编写初始实现

以下实现对应于我的libpool库的v1.0.0版本，有一些显著的“视觉”差异（例如没有ANSI限制）。一些改进，如能够调整/重新分配现有池的大小，将在下面进一步展开。

2.1. Chunk类型

在我们的简单实现中，我们将声明一个固定大小的Chunk类型。在更通用的实现中，我们会使用程序员在运行时指定的块大小，但该方法添加了许多类型转换，我认为这会使本文更加混乱。
首先，让我们看一下Chunk的定义。

#define CHUNK_SZ 64
typedef union Chunk Chunk;
union Chunk {
  Chunk* next;
  char arr[CHUNK_SZ];
};

注意我们是如何typedef一个union，而不是struct。
如果你不熟悉C语言中的union，它们在语法上类似于struct，但它们可以用于定义可能在不同时间保存不同类型和大小的对象的变量；与结构体不同，结构体允许程序员将不同的数据类型组合为单个记录。联合体本质上允许程序员访问单个存储区域中的数据，就好像它在给定时间存储了许多数据类型之一。当你访问联合体变量的成员时（例如my_chunk.next或my_chunk.arr），编译器负责访问union变量，就好像它是指定的成员类型（在该示例中，要么是指针，要么是CHUNK_SZ字符的数组，而不是两者）。
在这种情况下，使用union很方便，因为它允许我们根据上下文将Chunk解释为指向另一个Chunk的指针，同时还指定了Chunk的实际大小（即CHUNK_SZ）。还要注意，联合体的大小是最大可能成员的大小（在64位计算机中，sizeof(Chunk*)是8字节，由于arr成员是64字节，这将是Chunk联合体的大小）。
然而，仍然不清楚为什么我们需要根据上下文将Chunk解释为指针。首先，我们需要理解将有两种（隐式）类型的块：

  1. 空闲块：它们未被程序使用。它们将使用next指针。
  2. 非空闲块：它们已被分配，因此我们假设它们包含任意用户数据。具体来说，在此实现中，每个块最多可以包含CHUNK_SZ字节的数据。

如前所述，这些类型是“隐式的”。这意味着没有任何flags变量可以让我们知道指定的块是否空闲；相反，我们知道一个块是空闲的，因为它将位于空闲块链表中。当我们初始化池时，由于所有块都是空闲的，我们将使用Chunk.next指针将每个块链接到其相邻的块，如下所示：
pool-allocator1.svg
图1：初始化池后的四个空闲块。
灰色区域表示访问Chunk.next时未使用的联合体的其余部分，不完整的红色箭头表示NULL指针。此链表的创建及其优势将在下面创建池时解释。

2.2. Pool结构

我们还将声明一个Pool结构，它简单地包含：

  1. 指向空闲块链表的第一个元素的指针，当用户分配块时将使用它。
  2. 指向块数组的第一个元素的指针，当关闭整个池时将使用它。
typedef struct Pool Pool;
struct Pool {
  Chunk* free_chunk;
  Chunk* chunk_arr;
};

同样，根据实现的不同，可能需要其他成员，例如块大小；在这种情况下，它在编译时是已知的。

2.3. 创建池

我们将定义一个函数来创建一个具有任意数量块的Pool。

Pool* pool_new(size_t pool_sz) {
  Pool* pool = malloc(sizeof(Pool));
  if (pool == NULL)
    return NULL;
  pool->chunk_arr = pool->free_chunk = malloc(pool_sz * sizeof(Chunk));
  if (pool->chunk_arr == NULL) {
    free(pool);
    return NULL;
  }
  for (size_t i = 0; i < pool_sz - 1; i++)
    pool->chunk_arr[i].next = &pool->chunk_arr[i + 1];
  pool->chunk_arr[pool_sz - 1].next = NULL;
  return pool;
}

以下是每个步骤的简要说明：

  1. 我们使用malloc分配将返回的Pool结构。我们可以使用任何通用分配函数，不一定是malloc。
  2. 我们分配池本身，即Chunk联合体数组。我们将chunk_arr和free_chunk指针初始化为相同的地址，因为默认情况下所有块都是空闲的。
  3. 我们构建空闲块链表。我们将Chunk联合体的.next成员设置为相邻块的地址，除了最后一个空闲块，它将指向NULL。

这是从pool_new返回后池的样子：
pool-allocator2.svg
图2：初始化后的Pool结构布局。
这是用户在分配了两个块后池的样子。这个过程将在下面解释，但也许你已经开始意识到这种方法的优势：
pool-allocator3.svg
图3：分配两个块后的Pool结构布局。
由于此实现不支持池大小调整，唯一的O(n)算法发生在创建池本身时，因为我们需要遍历每个块以构建上述链表。另一方面，块分配过程具有O(1)复杂度，因为我们总是在Pool.free_chunk处有一个空闲块等待我们。释放块也是在线性时间内完成的，因为我们只需要将元素添加到这个链表的开头。

2.4. 分配块

现在池有一个指向空闲块链表的指针，当用户请求分配块时，我们只需要：

  1. 确保我们没有到达链表的末尾，即确保Pool.free_chunk指针不是NULL。
  2. 这个“空闲块”链表的第一个元素将被返回。在此之前，通过将链表的开头（即Pool.free_chunk）设置为原来的第二个元素（即Pool.free_chunk.next）来将其从链表中移除。
void* pool_alloc(Pool* pool) {
  if (pool == NULL || pool->free_chunk == NULL)
    return NULL;
  Chunk* result  = pool->free_chunk;
  pool->free_chunk = pool->free_chunk->next;
  return result;
}

现在用户可以安全地覆盖pool_alloc返回的指针的内容，这实际上是在设置Chunk联合体的arr成员。这是可以的，因为该块不再是我们“空闲块”链表的一部分。
再次强调，我们没有迭代任何东西，所以这个过程是线性的。在线性时间内分配任意大小的块显然有很大的优势，特别是当我们需要每秒多次分配和释放时（例如，模拟的每个滴答中的许多实体）。

2.5. 释放块

释放块非常简单，如果你理解了前面的部分，我建议你尝试编写自己的函数。
释放过程只是将块添加（前置）回空闲块链表中。正如你可能已经猜到的，这也是一个线性过程。

void pool_free(Pool* pool, void* ptr) {
  if (pool == NULL || ptr == NULL)
    return;
  Chunk* freed   = ptr;
  freed->next   = pool->free_chunk;
  pool->free_chunk = freed;
}

例如，按照前面的图，这将是用户释放第一个内存块后的布局。
pool-allocator4.svg
图4：释放一个块后的Pool结构布局。
请注意，与竞技场分配器不同，我们不必按照分配的顺序释放。

2.6. 关闭池

最后，一旦用户完成池的使用，应该能够将其释放回系统。在此实现中，这也是非常直观的，但在下面会变得有点棘手。

void pool_close(Pool* pool) {
  if (pool == NULL)
    return;
  free(pool->chunk_arr);
  free(pool);
}

3. 重新分配问题

使用池分配器时，有时你可能希望能够调整现有池的大小，例如当你用完块时。这可能看起来不太难，但有一些注意事项。
乍一看，我们可以通过几个简单的步骤重新分配池：

  1. 重新分配旧的块数组（即my_pool.chunk_arr）。
  2. 将新块链接在一起，就像我们在创建池时做的那样。
  3. 将新块前置到空闲块链表中，就像我们在释放先前分配的块时做的那样。

例如，按照前面的图，如果我们重新分配池以添加两个块，我们（乍一看）会得到以下布局。
pool-allocator5.svg
图5：调