實作 malloc() 和 free() — 首先重複使用舊記憶體

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

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

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

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

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

现在，我们发布第一和第三个区块......

abfree(ptr1);
abfree(ptr3);

…产生以下结构：

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

void *ptr5 = abmalloc(8);

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

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

abfree(ptr4);

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

旧区块的再利用

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

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

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

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

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

实施对旧区块的偏好

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

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;
Header *first = NULL;
Header *last = NULL;

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

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header) + size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

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

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  Header *header = last; 
  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header + 1; 
    } 
    header = header->previous; 
  } 
  last = header_new(last, size, false); 
  return last + 1; 
}

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

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  if (first == NULL) { 
    first = last = header_new(NULL, size, false); 
    return first + 1; 
  }

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

  Header *header = first;

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

  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header + 1; 
    } 
    header = header->next; 
  }

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

  last = header_new(last, size, false);

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

  last->previous->next = last; 
  return last + 1; 
}

Adjustments in abfree()

The function abfree() basically maintains the same structure, but now we must handle some edge cases. When we free blocks at the top of the heap, a new block becomes the last one, as we already do in this snippet:

    last = header->previous;
    brk(header)

Here, the pointer header references the last non-null block available on the stack. We have two possible scenarios:

1. the current block has a previous block, which will become the new last block. In this case, we should set the pointer nextof this block to NULL.
2. the current block does not have a previous block (i.e., it is the first and oldest block). When it is freed, the stack is empty. In this case, instead of trying to update a field of a non-existent block, we simply set it first to NULL, indicating that there are no more allocated blocks.

Here is how we implement it:

  last = header->previous; 
  if (last != NULL) { 
    last->next = NULL; 
  } else { 
    first = NULL; 
  } 
  brk(header);

Conclusion

Our functions abmalloc() and abfree() now look like this:

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;

Header *first = NULL;
Header *last = NULL;

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header) + size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  if (first == NULL) {
    first = last = header_new(NULL, size, false);
    return first + 1;
  }
  Header *header = first;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header + 1;
    }
    header = header->next;
  }
  last = header_new(last, size, false);
  last->previous->next = last;
  return last + 1;
}

void abfree(void *ptr) {
  if (ptr == NULL) {
   return;
  }
  Header *header = (Header*) ptr - 1;
  if (header == last) {
    while ((header->previous != NULL) && header->previous->available) {
      header = header->previous;
    }
    last = header->previous;
    if (last != NULL) {
      last->next = NULL;
    } else {
      first = NULL;
    }
    brk(header);
  } else {
   header->available = true;
  }
 }

This change allows us to save considerably more memory. There are, however, still problems to solve. For example, consider the following scenario: we request the allocation of a memory block of 8 bytes, and abmalloc() reuse a block of, say, 1024 bytes. There is clearly a waste.

We will see how to solve this in the next post.

以上是實作 malloc() 和 free() — 首先重複使用舊記憶體的詳細內容。更多資訊請關注PHP中文網其他相關文章！