自由列表分配器头元数据

Question

我正在尝试实现一个空闲列表内存分配器，并且正在为标头元数据保留什么而苦苦挣扎。我看到大多数示例和实现都只是保持分配的有效负载的大小，但我觉得不够。

例如，说我们的分配接口是：

void* Allocate(const std::size_t size, const std::size_t alignment);

简单来说，我们假设池的起始地址为@ 0x0。如果我们的Header仅保留尺寸信息，则其定义如下：

struct Header {
  std::size_t size;
};

因此，我们可以说sizeof(Header) = 4和alignof(Header) = 4（假设我们在x32上）。现在，假设我们按如下方式分配一个double：

Allocate(sizeof(double), alignof(double));

这等于说我们要分配大小为8和对齐方式为8的块。现在，如果将Header放在池@ 0x0的开头，则分配的块将不会与8对齐，因此，我们实际要做的是分配新的块@ [C0 ]，并按如下所示输入0x08 @ Header：

0x04

其中

[_ _ _ _ X X X X Y Y Y Y Y Y Y Y _ _ _ ...]
[0 1 2 3 4 5 6 7 8 9 A B C D E F G H I ...]

表示X，Header表示为我们的Y分配的块。这样，不仅分配的块对齐，而且double也对齐。

现在您可以看到，我们在开始处跳过了4个字节，因此我们可以将Header和分配的块都对齐到正确的对齐位置。

我的问题是，当我们希望取消分配tis块时，我们无法取回这4个字节，而我们将永远丢失它们。例如，说我们的取消分配接口是：

Header

如果我们以前像这样取消分配已分配的块：

void* Deallocate(void* ptr);

然后，我们无法将空闲的块以开头的这4个字节作为填充物退还给我们的空闲列表。

我的实现将LIFO策略插入顺序用于空闲列表，因此，Deallocate((void*)0x08); 的实现如下：

Deallocate

因此，最后分配的块是空闲列表头中的第一个块。现在您可以注意到空闲块的起始地址为

void* Deallocate(void* ptr) {
    Chunk* chunk = reinterpret_cast<Chunk*>(reinterpret_cast<char*>(ptr) - sizeof(Header));
    chunk->m_Size = reinterpret_cast<Header*>(chunk)->m_Size;
    chunk->m_Next = m_Head;
    m_Head = chunk;
}

这意味着上述调用取消分配Chunk* chunk = reinterpret_cast<Chunk*>(reinterpret_cast<char*>(ptr) - sizeof(Header)); ，我们将获得一个以@ (void*)0x8开头的空闲块，这意味着我们跳过了4个字节，并且再也无法获取它们，从而导致非常严重的碎片化问题，这些问题不会消失。

所以我想我缺少了一些我不理解的东西。我认为，如果0x04可以同时保存Header信息，然后可以正确地重新分配所有信息，则可以解决此问题，但这是额外的内存浪费，此外，我看不到将空闲列表分配到哪里padding存储填充。

您可能会争辩说Header的大小是分配的块+填充的大小，但这无助于我解决从Header起始地址开始的字节数，我需要向后检索这些字节填充字节，以便可以将该块完全释放回空闲列表。在我们的示例中，如果我们要在Header中存储此信息，则Header将不存储Header字节，而是8字节（8 + 4），当我12时，我将无法存储找出要从Deallocate((void*)0x08);地址减多少字节以取回这4个填充字节。

我想我在这里不了解某些内容，如果有人可以帮助我了解我所不了解的内容，我会感到很高兴。

Answer 1

这是因为大多数分配器将指针返回到针对任何标量类型适当对齐的内存块。因此，无需将对齐方式传递给分配器接口，例如

Header

通常，块按8字节（x32）和16字节（x64）对齐。向C ++ 11添加了一种特殊类型来获取该值：

void* malloc(size_t size)

因此，通过该值对齐标头和有效负载就足够了。