时间戳

首页 > 解决方案 > 空闲列表分配器标头元数据

c++ - 空闲列表分配器标头元数据

问题描述

我正在尝试实现一个空闲列表内存分配器，并且我正在为标题元数据应该包含的内容而苦苦挣扎。
我看到大多数示例和实现只保留分配的有效负载的大小，但我发现这还不够。

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

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，所以我们实际上需要做的是分配新的块@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 ...]

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

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

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

void* Deallocate(void* ptr);

如果我们像这样释放之前分配的块：

Deallocate((void*)0x08);

然后我们不能将一个开头有这 4 个字节的空闲块作为填充返回给我们的空闲列表。

我的实现对空闲列表使用 LIFO 策略插入顺序，因此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我们将获得一个以 @ 开头的空闲块，0x04这意味着我们跳过了 4 个字节，我们永远无法再次获得它们，导致非常糟糕的碎片问题不会消失。

所以我想我错过了一些我不明白的东西。我认为这个问题可以解决，如果它Header也能保存padding信息，然后一切都可以正确地解除分配，但这是额外的内存浪费，除此之外，我看不到在Header存储填充的地方分配空闲列表的实现。

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

我想我在这里不理解某些东西，如果有人可以帮助我理解我不理解的东西，我会很高兴..

更新： 这是具有上述问题
的当前实现：Allocate

void* FreeListAllocator::Allocate(const std::size_t size, const std::size_t alignment)
{
    Chunk* chunk = m_Head;
    void* currentAddress = reinterpret_cast<char*>(chunk) + sizeof(Header);
    std::size_t space = chunk->m_Size;
    std::align(alignment, size, currentAddress, space);
    std::size_t padding = reinterpret_cast<char*>(currentAddress) - reinterpret_cast<char*>(chunk) - sizeof(Header);
    while (size + padding > chunk->m_Size)
    {
        chunk = chunk->m_Next;
        if (chunk == nullptr)
            break;
        currentAddress = reinterpret_cast<char*>(chunk) + sizeof(Header);
        space = chunk->m_Size;
        std::align(alignment, size, currentAddress, space);
        padding = reinterpret_cast<char*>(currentAddress) - reinterpret_cast<char*>(chunk) - sizeof(Header);
    }

    if (chunk == nullptr)
        return nullptr;

    m_Head = reinterpret_cast<Chunk*>(reinterpret_cast<char*>(chunk) + sizeof(Header) + size + padding);
    m_Head->m_Size = chunk->m_Size - (size + padding + sizeof(Header));
    m_Head->m_Next = nullptr;

    Header* header = reinterpret_cast<Header*>(reinterpret_cast<char*>(chunk) + padding);
    header->m_Size = size;

    return reinterpret_cast<char*>(chunk) + sizeof(Header);
}

请注意，我的空闲列表分配器X在构造时分配一个大小的内存区域，并且分配的整个内存区域malloc被视为单个块。稍后，当完成一些分配和取消分配时，空闲列表开始变得不止一个元素：

FreeListAllocator(const std::size_t size, bool resizeable)
    : m_Size(size), m_Head(nullptr)
{
    m_StartAddress = ::operator new(size);
    m_Head = reinterpret_cast<Chunk*>(m_StartAddress);
    m_Head->m_Size = size - sizeof(Header);
    m_Head->m_Next = nullptr;
}

标签： c++memorymemory-management

解决方案

哦，嘿，这是我在工作中必须解决的问题。

让我们从一些假设开始并做出选择。

首先，我们假设我们在一个不支持非对齐访问的平台上，比如 MIPS 或 ARM。其次，我们将假设任何分配器给我们的真正的 RAM 块都没有任何对齐（或 1 个字节的对齐）。第三，我们假设周围没有操作系统来仔细检查我们的对齐、分配或内存边界（即我们在这里独自飞行）。

接下来，我们将选择我们的自然对齐方式，即默认情况下我们将对齐我们分配的任何新块的数量。这通常是我们的标头结构的大小，因为我们不需要处理用户块的对齐小于我们的结构大小但大于我们的自然对齐的边缘情况。出于本示例的目的，我将标头定义如下：

struct AllocationHeader
{
    struct ListEntry* pNext;
    struct ListEntry* pPrev;
    uint32 Size;
    uint8 Alignment;
    uint8 Adjustment;
    uint16 Flags;
};

这个结构的大小是 16 字节，所以我们从这个分配器分配的任何块都将保证至少 16 字节的对齐。值得注意的是，无论您的标头大小是多少，所涉及的算法都是相同的。

现在，开始分配。

第一步实际上是从释放开始，因为这将告知我们如何构建我们的标题以及我们实际上需要如何分配我们的内存。

要释放我们系统分配的一块内存，我们需要恢复原始块地址和块头。标头相当简单 - 只需从用户块地址中减去标头的大小：

AllocationHeader* pHeader = (AllocationHeader*)(((uint8*)UserPtr) - sizeof(AllocationHeader));

这为我们提供了标题信息，然后我们可以根据需要使用这些信息。

第二步是从头中恢复原始块地址。这是我们的Adjustment会员给的。

正如您正确指出的那样，要获得与用户想要的等效的块对齐，我们需要将分配标头地址最多调整max(UserAlignment, NaturalAlignment) - 1字节。在分配时，我们需要将该值存储在块的头部，否则我们无法恢复下层分配器提供的原始分配地址。

一旦我们有了调整值，我们就可以继续恢复原始块地址：

uint8 Adjustment = pHeader->Adjustment;
uint8* BlockPointer = ((uint8*)pHeader) - Adjustment;

所以现在的诀窍是计算调整值。

为此，我们在分配函数中执行以下步骤：

  1. 分配一块与我们的用户块大小相同的内存块，加上我们的标题大小和用户对齐，如果它比我们的标题大。
uint8 ActualAlignment = max(NaturalAlignment, UserAlignment);
uint32 BlockSize = UserSize + sizeof(AllocationHeader) + ActualAlignment;
uint8* pRawBlock = ::operator new(BlockSize);
  1. 根据实际对齐检查地址，以产生与我们理想对齐的偏移量。
uint8 Offset = ((uintptr)pRawBlock) & (ActualAlignment - 1);
  1. 根据偏移和实际对齐计算调整值。
uint8 Adjustment = (((ActualAlignment - Offset) - NaturalAlignment) & (ActualAlignment - 1));

这个表情似乎……很奇怪。毕竟，如果我们分配一个对齐到 32 字节的块，而我们的偏移量是 26 字节，当我们减去 16 的自然对齐时，我们最终会得到 -10，这作为对齐没有意义。AND 通过ActualAlignment - 1屏蔽最高位来解决这个问题，导致 22，我们需要添加到原始地址的字节数，以确保我们的标题不仅正确对齐，而且我们分配的结构将具有正确的对齐也是如此。

让我们看一下前面的示例，并检查结果地址。

我们的地址与理想对齐有 26 个字节的偏移量。将该值插入我们的表达式会产生：

Adjustment = ((32 - 26) - 16) & 31

Adjustment = ((6) - 16) & 31
Adjustment = (-10) & 31
Adjustment = 0xF6 & 0x1F
Adjustment = 0x16
Adjustment = 22

如果我们然后将该调整值添加到我们的原始偏移量，我们得到：

pAllocationHeader = (26 + 22) = 48
pUserBlock = pAllocationHeader + 16 = 48 + 16 = 64

分配头和用户块现在都正确对齐了，我们可以继续。

  1. 填写分配头并返回用户块。
pAllocationHeader = (AllocationHeader*)(pRawBlock + Adjustment);
pAllocationHeader->Size = BlockSize;
pAllocationHeader->Alignment = ActualAlignment;
pAllocationHeader->Adjustment = Adjustment;
AddToAllocatedList(pAllocationHeader);
return (uint8*)(((uint8*)pAllocationHeader) + sizeof(AllocationHeader));

这里最重要的部分是跟踪调整值。我的示例结构中的所有其他内容都用于记账（即假设我们是唯一的分配者），但Adjustment成员需要存储在块元数据中的某个位置，否则您将永远无法释放块。

推荐阅读