不使用Malloc/New或Free/Delete管理连续块内存

Question

不使用Malloc/New或Free/Delete管理连续块内存

6

如何在C++中创建一个自定义的MemoryManager来管理给定的连续内存块，而不依赖其他内存管理器（如Malloc / New）？

下面是更多背景信息：

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

我需要能够使用MemManager分配和释放这块连续内存的块。构造函数给出了块的总大小（以字节为单位）。

Allocate函数应该接受所需内存量（以字节为单位）并返回指向该内存块开头的指针。如果没有剩余内存，则返回空指针。

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

请注意以下限制：

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

-按照最初的规定，MemManager不能使用其他内存管理器来执行其功能，包括new/malloc和delete/free 我已经在几次工作面试中收到过这个问题，但是即使在网上进行了数小时的研究，也没有帮助我，而且我每次都失败了。我找到了类似的实现，但它们要么使用了malloc/new，要么是通用的，并从操作系统请求内存，这是我不允许做的。

请注意，我习惯于使用malloc/new和free/delete，使用它们时很少遇到麻烦。

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

如果有人有某种实现这样东西的想法，我将不胜感激。先谢谢了！

编辑：我忘记在原始帖子中直接指定这一点，但使用此MemManager分配的对象可以具有不同的大小。

编辑2：最终我使用了同质内存块，这实际上非常容易实现，得益于下面答案提供的信息。没有指定实现本身的确切规则，因此我将每个块分成8个字节。如果用户请求的字节数大于8，则无法给出，但是如果用户请求的字节数少于8（但> 0），则会给出额外的内存。如果传入的内存量不能被8整除，则末尾会有浪费的内存，我认为这比使用比所给的内存更多的内存要好得多。

- user4148144

诀窍是将元数据存储在分配的地址下方。现在太累了，无法写出完整的解释。 - Jason

2个回答

1

当你管理内存时，通常希望使用所管理的内存来存储所需的任何元数据。如果查看任何一个malloc实现（ptmalloc、phkmalloc、tcmalloc等），通常都会看到它们是如何实现的（当然忽略任何静态数据）。算法和结构是非常不同的，出于不同的原因，但我会尝试给出一些关于通用内存管理的见解。

管理同类内存块与管理非同类内存块不同，可以更加简单。例如...

MemoryManager::MemoryManager() {

  this->map = std::bitset<count>();
  this->mem = malloc(size * count);

  for (int i = 0; i < count; i++)
    this->map.set(i);
}

分配内存就是找到下一个std::bitset中的位（编译器可能会优化），将块标记为已分配并返回它。释放内存只需要计算索引，并将其标记为未分配。空闲列表是另一种方法（这里所描述的），但它的内存效率略低，并且可能无法很好地使用CPU缓存。

空闲列表可以成为管理非同质内存块的基础。为此，您需要存储块的大小，以及内存块中的下一个指针。大小让您将较大的块拆分为较小的块。然而，这通常会导致碎片化，因为合并块不是易事。这就是为什么大多数数据结构保持相同大小块的列表，并尽可能接近地映射请求的原因。

- Jason

谢谢您的回复！对于同质块，如果用户请求的内存超过单个块提供的内存会发生什么？ - user4148144

2

对于同质块，allocate方法可能不应该允许用户指定分配大小。对于非同质块，情况就有趣了 :). 如果您正在使用空闲列表，您可以尝试合并相邻的块，但这非常复杂。这是碎片化不好的原因之一。通常，内存管理器会直接使用mmap或等效的系统调用从系统中分配。但如果没有分配额外的内存，您需要返回null。 - Jason

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- masrtis · Accepted Answer

我尝试过使用类似链表的节点对象实现，指向分配的内存块并记录使用了多少字节。但是，使用这些实现时，我总是被迫在堆栈上创建新节点并将它们插入列表中，但一旦它们超出作用域，整个程序就会崩溃，因为地址和内存大小都丢失了。

你正在正确的道路上。你可以使用reinterpret_cast<>将LinkedList节点嵌入到给定的内存块中。由于允许将变量存储在内存管理器中，只要不动态分配内存，你就可以使用成员变量跟踪列表的头部。你可能需要特别注意对象大小（所有对象的大小是否相同？对象大小是否大于链表节点的大小？）

假设前面的问题的答案是真的，那么你可以处理内存块，并使用一个帮助链表将其拆分为更小的、对象大小的块，该链表跟踪空闲节点。你的空闲节点结构将是这样的：

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;
}

由于您提到Allocate函数需要输入对象大小，因此上述内容需要进行修改以存储元数据。您可以通过在空闲列表节点数据中包含空闲块的大小来实现此目的。这样可以避免拆分初始块，但会增加Allocate()和Deallocate()的复杂性。您还需要考虑内存碎片问题，因为如果没有足够内存来存储所请求的数量，除了分配失败之外，您无法做任何事情。一些Allocate()算法可能是：

1) 只需返回第一个可用的块，其大小足以容纳请求，并根据需要更新空闲块。这在搜索空闲列表方面是O(n)，但可能不需要搜索很多空闲块，并且可能导致日后出现碎片问题。

2) 搜索具有最小剩余量以容纳内存的块的空闲列表。这在搜索空闲列表方面仍然是O(n)，因为您必须查看每个节点以找到最少浪费的节点，但可以帮助延迟碎片问题。

无论如何，对于可变大小的内存分配，你都需要在某个地方存储分配的元数据。如果你完全不能动态分配，最好的位置是在用户请求块之前或之后；如果你想要添加填充并检查填充差异来检测缓冲区溢出/下溢，可以在Deallocate()期间添加特性。如果你想处理这个问题，你也可以像另一个答案中提到的那样添加一个紧凑步骤。

最后一点要注意的是，在FreeListNode帮助结构体中添加元数据时必须小心，因为允许的最小空闲块大小为sizeof(FreeListNode)。这是因为你正在将元数据存储在空闲内存块本身中。你需要存储越多的元数据以满足你的内部目的，你的内存管理器就会越浪费内存。