[博客翻译]用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：调整大小后的Pool结构布局，添加了两个新块。
然而，有一个重要的细节容易被忽略。当我们重新分配池（即块数组）时，数组的基地址可能会改变，因此每个块的地址也会改变。这是一个问题，因为：

  1. 用于构建空闲块链表的旧指针仍然指向旧数组，因此它们变得无效。有几种可能的修复方法，例如从旧的基地址重新计算偏移量1，存储偏移量而不是指针等。
  2. 当用户分配块时我们返回的指针也指向旧数组，因此它们也无效。如果用户尝试访问或释放这些指针，可能会发生分段错误。

这是重新分配后布局可能的样子。用单线划掉的不完整连接表示指向旧数组的无效（但非空）指针，现在已无效。
pool-allocator6.svg
图6：调整大小的问题：旧指针可能变得无效。

4. 第二次实现：扩展池

与其修改现有的块数组，我们可以分配一个新数组，其中包含我们想要添加的块数，并将它们前置到现有池的空闲块链表中。虽然这只能让池增长（而不能缩小），但我认为这是大多数实现所需要的。下面将解释这种方法的一些重要细节。
下图显示了如何分别分配两个不同的Chunk数组。绿色区域表示在pool_new中分配的初始块数组，而蓝色区域表示在扩展池时分配的不同块数组。这两个数组在内存中不一定是相邻的，这就是为什么不需要重新分配。
pool-allocator7.svg
图7：扩展池后的不同块数组。
请注意，我们必须跟踪每个数组的起始位置，因为我们需要分别释放它们。在前面的图中，我们使用两个chunk_arr0和chunk_arr1成员来表示这一点，但由于我们希望允许用户任意次数地扩展池，我们应该能够在运行时跟踪不定数量的指针（指向块数组的起始位置）。

4.1. 跟踪数组起始位置

为了跟踪这些指针，我们将创建另一个“数组起始位置”链表。我们声明一个LinkedPtr结构，它将包含链表中下一个元素的地址（或NULL），以及每个数组起始位置的指针。

typedef struct LinkedPtr LinkedPtr;
struct LinkedPtr {
  Chunk* ptr;
  LinkedPtr* next;
};

现在，我们不在Pool结构中存储单个Chunk*，而是存储指向数组起始位置链表的指针。

struct Pool {
  Chunk* free_chunk;
  LinkedPtr* array_starts; /* 更新 */
};

这在内存中占用更多空间，但这是值得的。即使我们不调整池的大小，也只需要多两个指针的大小：一个指向LinkedPtr结构本身，另一个是（未使用的）.next成员。

4.2. 对pool_new和pool_close的修改

pool_new和pool_free函数需要根据我们的新LinkedPtr结构进行修改。
在创建池时，我们不再将块数组的基地址存储在pool->chunk_arr中，而是必须分配一个LinkedPtr结构并将其写入其中。

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

在关闭池时，我们还需要遍历这个array_starts链表，释放链表中的每个块数组和每个LinkedPtr结构。

void pool_close(Pool* pool) {
  if (pool == NULL)
    return;
  LinkedPtr* linkedptr = pool->array_starts;
  while (linkedptr != NULL) {
    LinkedPtr* next = linkedptr->next;
    free(linkedptr->ptr);
    free(linkedptr);
    linkedptr = next;
  }
  free(pool);
}

4.3. 不修改数组的情况下调整大小

现在我们有一种方法来存储不定数量的块数组的起始地址，我们可以实现前面的图中显示的调整大小方法。调整大小的过程如下：

  1. 分配我们试图添加到池中的额外块数组。
  2. 将新块链接在一起，就像我们在创建池时做的那样。
  3. 将额外块数组前置到“空闲块”链表中，就像我们在释放块时做的那样。
  4. 分配一个新的LinkedPtr结构，并将新块数组的起始位置存储在其中。
  5. 将这个新的LinkedPtr结构前置到存储在Pool结构中的“数组起始位置”链表中。

这是对应于前面步骤的代码。

bool pool_resize(Pool* pool, size_t extra_chunk_num) {
  if (pool == NULL || extra_chunk_num == 0)
    return false;
  /* 步骤1 */
  Chunk* extra_chunk_arr = malloc(extra_chunk_num * sizeof(Chunk));
  if (extra_chunk_arr == NULL)
    return false;
  /* 步骤2 */
  for (size_t i = 0; i < extra_chunk_num - 1; i++)
    extra_chunk_arr[i].next = &extra_chunk_arr[i + 1];
  /* 步骤3 */
  extra_chunk_arr[extra_chunk_num - 1].next = pool->free_chunk;
  pool->free_chunk             = extra_chunk_arr;
  /* 步骤4 */
  LinkedPtr* array_start = malloc(sizeof(LinkedPtr));
  if (array_start == NULL) {
    free(extra_chunk_arr);
    return false;
  }
  /* 步骤5 */
  array_start->ptr  = extra_chunk_arr;
  array_start->next = pool->array_starts;
  pool->array_starts = array_start;
  return true;
}

就像在前面的图中一样，绿色和蓝色区域表示独立分配的数组，但它们的LinkedPtr结构也包含在图中。
pool-allocator8.svg
图8：调整大小后的池布局，显示数组起始位置的链表。
自然，这第二个实现能够以相同的O(1)效率分配和释放块。内存影响稍微大一些，但如果你曾经想调整池的大小，这可能是值得的。

脚注：

1
这种方法的示例，我在注意到第二个问题之前写的，可以在我的libpool仓库的提交bb0c8a2中看到。该代码不使用Chunk联合体，因此类型转换使其可读性较差。

阅读全文（20积分）