在本系列关于实现 malloc() 和 free() 的上一篇文章中，我们展示了如何通过释放新块来重用内存块并减少堆。然而，当前的函数引入了一个微妙的问题：它优先考虑重用较新的块，这可能会导致内存消耗随着时间的推移而增加。为什么会发生这种情况？让我们来分解一下。

通过重用最近的块来减少堆

考虑以下场景。首先，我们分配四个内存块：

void *ptr1 = abmalloc(8); 无效 *ptr2 = abmalloc(8); 无效 *ptr3 = abmalloc(8); 无效 *ptr4 = abmalloc(8);

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

内存结构可以这样可视化：

现在，我们发布第一块和第三块……

abfree(ptr1); abfree(ptr3);

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

...产生以下结构：

然后我们分配另一个相同大小的块：

void *ptr5 = abmalloc(8);

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

当函数 abmalloc() 开始搜索最近的空闲块时，它会重用顶部的块。如果我们现在释放最后一个块：

如果我们现在释放最后一个区块……

abfree(ptr4);

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

...我们可以将堆大小减少一个 8 字节块，因为前一个块不再空闲：

旧区块的再利用

现在，想象一下相同的场景，但进行了一项修改：我们的函数开始从最旧的块开始搜索空闲块。初始结构将是相同的......

...我们再次释放第一和第三个内存块：

这次，第一个块将被重用：

现在，当我们释放最后一个块时，顶部将有两个空闲块，使我们能够将堆减少两个 8 字节块：

这个例子说明了，通过优先选择较新的块，我们最终会积累旧的未使用的块，浪费内存并导致不必要的堆增长。解决方案是修改搜索策略，优先重用旧块。

实施对旧区块的偏好

为了解决这个问题，我们首先在标头中添加一个指向下一个块的指针。我们还将创建一个指向第一个块的全局指针，这样我们就可以从它开始搜索：

typedef 结构头 { 结构头*上一个，*下一个； size_t 尺寸； 可用布尔值； 标题； 标头*第一个= NULL； 标头*最后= NULL；

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

我们将在两种不同的情况下创建带有标头的内存块，所以让我们进行一个小的重构：我们将这个逻辑提取到一个分配和初始化标头的辅助函数（包括将字段 next 设置为 NULL）：

标题 *header_new(标题 *前一个, size_t 大小, bool 可用) { 标头 *header = sbrk(sizeof(标头) 大小); 标题->上一个=上一个； 标题->下一个= NULL； 标题->大小=大小； 标头->可用= false； 返回标头； }

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

通过这个新函数，我们可以简化 abmalloc() 中的逻辑：

void *abmalloc(size_t 大小) { 如果（大小== 0）{ 返回空值； } 标题*标题=最后； while (标题！= NULL) { if (标题->可用 && (标题->大小 >= 大小)) { 标头->可用= false； 返回标头1； } 标题=标题->上一页； } 最后 = header_new(最后, 大小, false); 返回最后1个； }

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

现在我们可以访问第一个和最后一个块，并且给定一个块，我们可以找出前一个和下一个块。我们还知道，当指向第一个块的指针为空时，还没有分配任何块。所以在这种情况下，我们将立即分配块，并初始化第一个和最后一个：

void *abmalloc(size_t 大小) { 如果（大小== 0）{ 返回空值； } 如果（第一个== NULL）{ 第一个 = 最后一个 = header_new(NULL, 大小, false); 返回第一个1； }

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

如果firstit不再为NULL，则已经分配了块，因此我们将开始搜索可重用的块。我们将继续使用变量 header 作为迭代器，但搜索将从最旧的块开始，而不是从最近的块开始：

标头 *标头 = 第一个；

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

在每次迭代时，我们将前进到序列中的下一个块，而不是向后到上一个块：

while (标题!= NULL) { if (标题->可用 && (标题->大小 >= 大小)) { 标头->可用= false； 返回标头1； } 标题=标题->下一个； }

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

逻辑保持不变：如果我们找到足够大小的可用块，则将其返回。否则，如果遍历列表后没有找到可重用的块，则分配一个新块：

最后 = header_new(最后, 大小, false);

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

现在，我们需要调整最后一个块（分配后，倒数第二个）。它指向 NULL，但现在它应该指向新块。为此，我们将前一个块的下一个字段设置为新的最后一个块：

最后一个->上一个->下一个 = 最后一个； 返回最后1个； }

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

abfree() 中的调整

函数 abfree() 基本上保持相同的结构，但现在我们必须处理一些边缘情况。当我们释放堆顶部的块时，一个新块将成为最后一个块，正如我们在此代码段中所做的那样：

最后 = 标题->上一个； brk（标头）

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

这里，指针头引用堆栈上最后一个可用的非空块。我们有两种可能的情况：

当前块有一个前一个块，它将成为新的最后一个块。在这种情况下，我们应该将该块的next指针设置为NULL。
当前块没有前一个块（即，它是第一个也是最旧的块）。当它被释放时，堆栈是空的。在这种情况下，我们不会尝试更新不存在的块的字段，而是先将其设置为 NULL，表示不再有分配的块。

我们的实现方式如下：

最后 = 标题->上一个； 如果（最后！= NULL）{ 上一个->下一个= NULL； } 别的 { 首先=空； } brk（标头）；

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

结论

我们的函数 abmalloc() 和 abfree() 现在看起来像这样：

typedef 结构头 { 结构头*上一个，*下一个； size_t 尺寸； 可用布尔值； 标题； 标头*第一个= NULL； 标头*最后= NULL； 标头 *header_new(标头 *前一个, size_t 大小, bool 可用) { 标头 *header = sbrk(sizeof(标头) 大小); 标题->上一个=上一个； 标题->下一个= NULL； 标题->大小=大小； 标头->可用= false； 返回标头； } 无效* abmalloc（size_t大小）{ 如果（大小== 0）{ 返回空值； } 如果（第一个== NULL）{ 第一个 = 最后一个 = header_new(NULL, 大小, false); 返回第一个1； } 标题*标题=第一个； while (标题！= NULL) { if (标题->可用 && (标题->大小 >= 大小)) { 标头->可用= false； 返回标头1； } 标题=标题->下一个； } 最后 = header_new(最后, 大小, false); 最后一个->上一个->下一个=最后一个； 返回最后1个； } 无效 abfree(无效 *ptr) { 如果（ptr == NULL）{ 返回; } 标头 *标头 = (标头*) ptr - 1; 如果（标题==最后）{ while ((标题->上一个！= NULL) && 标题->上一个->可用) { 标题=标题->上一页； } 最后=标题->上一个； 如果（最后！= NULL）{ 上一个->下一个= NULL； } 别的 { 首先=空； } brk（标头）； } 别的 { 标头->可用= true； } }

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

此更改使我们能够节省更多内存。然而，仍有一些问题需要解决。例如，考虑以下场景：我们请求分配 8 字节的内存块，而 abmalloc() 重用了一个 1024 字节的内存块。显然存在浪费。

我们将在下一篇文章中看到如何解决这个问题。