实现 malloc() 和 free() — 分割大块

在本系列的上一篇文章中，我们看到了选择要重用的内存块的顺序如何导致更大或更少的内存消耗，并且我们更改了函数来避免这种情况浪费。但我们需要解决另一个甚至更严重的问题：有时，一个非常大的内存块可能会占用几个较小块可以使用的空间。考虑下面的情况，我们分配一大块内存，释放它，然后分配两个小得多的块：

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

这里，我们有一个空闲的 128 字节内存块，当我们分配一个只有 8 字节的块时，所有 128 字节都变得不可用。当我们分配另一个 8 字节块时，堆需要再次增长。这不是对内存的有效利用。

对于这种情况至少有两种流行的解决方案。一种更有效的方法是使用 bins：列出按大小分组的块。这是一种更复杂、更有效的方法，但也更复杂。另一种更简单的选择是找到一个大块并将其分成更小的块。我们将遵循这种方法。

但请记住：更简单并不意味着简单;-)

初始重构

在开始之前，让我们进行一个小的重构。目前， header_new() 函数做了两件事：为新块分配更多内存并初始化其标头，设置元数据和指向前一个块的指针。初始化标头的部分可能有用，所以让我们将其提取出来。我们将创建两个新函数来提高可读性：

• header_plug() 函数，它将初始化的块“插入”到前一个和下一个块。
• header_init() 函数，用于设置块元数据的初始值（大小和可用性）。

它们的外观如下：

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

现在，我们只需要修改 header_new() 即可使用这些新函数：

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

（此外，我们可以从 abmalloc() 函数中删除最后一行 ->previous->next = last; 行，因为 header_plug() 现在可以处理该问题。）

分裂方块

有了这些工具，让我们创建 header_split() 函数。给定标头和所需的最小大小，如果原始块足够大以包含

，则此函数会将内存块分成两部分

• 所需尺寸，
• 新区块的新标头，以及
• 一点额外的内存。

首先，我们检查块是否足够大：

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

如果满足这个条件，我们就分割区块。首先，我们通过减去标头的大小和 abmalloc 请求的空间来减小当前块的大小：

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

这会在当前块之后留下一个内存空间，我们将用它来创建新块。我们计算这个新块的指针：

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

现在我们有了指向新块的指针，我们用 header_init() 初始化它的头：

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

我们使用 header_plug() 将新块连接到前一个和下一个块：

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

如果原始块是最后一个，那么新块现在将是最后一个，因此我们更新最后一个指针：

header->size = original_size - size - sizeof(Header);

最后，我们返回新块：

Header *new_header = header + sizeof(Header) + header->size;

如果原始块不够大，我们只需返回原始块：

header_init(new_header, size, true);

更新 abmalloc()

现在，我们只需要回到 abmalloc() 函数，在找到可用块的地方，我们调用 header_split() 来尝试拆分它：

header_plug(new_header, header, header->next);

如果区块可以分裂，则返回新区块。否则，原始块将像以前一样保留并返回。

关于块分裂的注意事项

请注意，我们在原始块的末尾创建了新块。我们可以在一开始就创建它，但是通过在最后创建新的已用块，新的空闲块会更接近旧块。这样，下次调用 abmalloc() 时就会首先找到它。

分割大内存块是向前迈出的一步，但存在相反的问题：小内存块可能会导致碎片，发出更大的请求会导致堆增长。我们将在下一篇文章中看到如何解决这个问题。

以上是实现 malloc() 和 free() — 分割大块的详细内容。更多信息请关注PHP中文网其他相关文章！