c++ - 在没有 Malloc/New 或 Free/Delete 的情况下管理连续的内存块

Question

如果没有 C++ 中其他内存管理器(例如 Malloc/New)的帮助，如何创建自定义 MemoryManager 来管理给定的连续内存块？

这里有更多的上下文:

   MemManager::MemManager(void* memory, unsigned char totalsize)
   {
       Memory = memory;
       MemSize = totalsize;
   }

我需要能够使用 MemManager 分配和释放此连续内存块。构造函数被赋予 block 的总大小(以字节为单位)。

分配函数应以字节为单位获取所需的内存量，并返回指向该内存块开头的指针。如果没有内存剩余，则返回 NULL 指针。

Deallocate 函数应接收指向必须释放的内存块的指针，并将其返回给 MemManager 以供将来使用。

注意以下限制:

-除了分配给它的内存块，MemManager 不能使用任何动态内存

-正如最初指定的那样，MemManager 不能使用其他内存管理器来执行其功能，包括 new/malloc 和 delete/free

我已经在好几次工作面试中收到过这个问题，但即使在线研究了几个小时也无济于事，我每次都失败了。我发现了类似的实现，但它们要么都使用了 malloc/new，要么是通用的，并从操作系统请求内存，我不允许这样做。

请注意，我对使用 malloc/new 和 free/delete 感到很舒服，使用它们时几乎没有问题。

我已经尝试过以 LinkedList 方式利用节点对象的实现，这些节点对象指向分配的内存块并说明使用了多少字节。然而，对于这些实现，我总是被迫在堆栈上创建新节点并将它们插入到列表中，但是一旦它们超出范围，整个程序就会崩溃，因为地址和内存大小都丢失了。

如果有人对如何实现这样的东西有某种想法，我将不胜感激。提前致谢!

编辑:我忘记在我的原始帖子中直接指定它，但是用这个 MemManager 分配的对象可以有不同的大小。

编辑 2:我最终使用了同质内存块，由于下面的答案提供的信息，这实际上很容易实现。关于实现本身的确切规则没有指定，所以我将每个 block 分成 8 个字节。如果用户要求超过8个字节，我就给不了，但是如果用户要求少于8个字节(但>0)那么我就给额外的内存。如果传入的内存量不能被 8 整除，那么最后会浪费内存，我认为这比使用比你给定的更多的内存要好得多。

Answer 1

I have tried implementations that utilize node objects in a LinkedList fashion that point to the block of memory allocated and state how many bytes were used. However, with those implementations I was always forced to create new nodes onto the stack and insert them into the list, but as soon as they went out of scope the entire program broke since the addresses and memory sizes were lost.

您走在正确的轨道上。您可以将 LinkedList 节点嵌入到您通过 reinterpret_cast<> 获得的内存块中。由于只要不动态分配内存就可以在内存管理器中存储变量，因此可以使用成员变量跟踪列表的头部。您可能需要特别注意对象的大小(所有对象的大小都一样吗？对象的大小是否大于链表节点的大小？)

假设前面问题的答案是正确的，然后您可以处理内存块并使用跟踪空闲节点的辅助链表将其拆分为更小的对象大小的 block 。您的免费节点结构将类似于

struct FreeListNode
{
    FreeListNode* Next;
};

分配时，您所做的就是从空闲列表中删除头节点并将其返回。解除分配只是将释放的内存块插入空闲列表。拆分内存块只是一个循环:

// static_cast only needed if constructor takes a void pointer; can't perform pointer arithmetic on void*
char* memoryEnd = static_cast<char*>(memory) + totalSize; 
for (char* blockStart = block; blockStart < memoryEnd; blockStart += objectSize)
{
    FreeListNode* freeNode = reinterpret_cast<FreeListNode*>(blockStart);
    freeNode->Next = freeListHead;
    freeListHead = freeNode;
}

正如您提到的分配函数接受对象大小，需要修改以上内容以存储元数据。您可以通过在空闲列表节点数据中包含空闲 block 的大小来实现这一点。这消除了拆分初始 block 的需要，但在 Allocate() 和 Deallocate() 中引入了复杂性。您还需要担心内存碎片，因为如果您没有足够内存的空闲 block 来存储请求的数量，那么除了分配失败之外，您无能为力。几个 Allocate() 算法可能是:

1) 只返回第一个足够大的可用 block 来容纳请求，必要时更新空闲 block 。就搜索空闲列表而言，这是 O(n)，但可能不需要搜索大量空闲 block ，并可能导致碎片化问题。

2) 在空闲列表中搜索空闲量最少的 block 以容纳内存。就搜索空闲列表而言，这仍然是 O(n)，因为您必须查看每个节点以找到浪费最少的节点，但这有助于延迟碎片问题。

无论哪种方式，对于可变大小，您还必须在某处存储用于分配的元数据。如果你根本不能动态分配，最好的地方是在用户请求 block 之前或之后；如果要添加初始化为已知值的填充并检查填充是否存在差异，则可以在 Deallocate() 期间添加检测缓冲区溢出/下溢的功能。如果您想处理该问题，您还可以添加另一个答案中提到的紧凑步骤。

最后一点:将元数据添加到 FreeListNode 帮助器结构时必须小心，因为允许的最小空闲 block 大小是 sizeof(FreeListNode)。这是因为您将元数据存储在空闲内存块本身中。您发现自己需要为内部用途存储的元数据越多，您的内存管理器就会越浪费。