自定义malloc实现

Question

最近有人问我一个问题，如何实现一个非常简单的malloc，具有以下限制和初始条件。

#define HEAP_SIZE 2048
int main()
{
    privateHeap = malloc(HEAP_SIZE + 256); //extra 256 bytes for heap metadata
    void* ptr = mymalloc( size_t(750) );
    myfree( ptr );
    return 0;
}

我需要在这里使用提供的确切空间实现mymalloc和myfree。256字节可以很好地映射到2048位，我可以用一个位数组来存储一个字节是分配的还是空闲的。但是当我用ptr调用myfree时，我不知道一开始分配了多少大小。我不能使用任何额外的位。

我似乎不认为有办法解决这个问题，但我已经反复强调这是可以做到的。有什么建议吗?

<标题>编辑1:

1. 对齐限制不存在。我假设我不会对齐任何东西。
2. 有一个演示程序，它做了一系列的malloc s和free来测试这一点，它没有任何很小的内存块。但这并不能保证任何事情。

<标题>编辑2:

文档中的指导方针:关于代码的某些准则:

1. 管理私有堆中的堆元数据;不要在提供的私有堆之外创建额外的链表;
2. 设计mymalloc, myrealloc, myFree为所有可能的输入工作。
3. myrealloc应该像c++库中的realloc一样执行以下操作:void* myrealloc( void* C, size_t newSize ):
   1. 如果newSize大于reallocThis中的chunk大小:
      1. 它应该首先尝试分配一个大小为newSize的块，以便新块的基指针也是reallocThis;
      2. 如果没有可用的可用空间来做就地分配，它应该在不同的区域分配请求大小的块;然后它应该复制前一个块的内容。
      3. 如果函数分配请求的内存块失败，则返回NULL指针，并指向该内存块by参数reallocThis保持不变
   2. 如果newSize更小，realloc应该缩小块的大小，并且应该总是成功。
   3. 如果newSize为0，它应该像免费一样工作。
   4. 如果reallocThis是NULL，它应该像malloc一样工作。
   5. 如果reallocThis是已经释放的指针，那么它应该通过返回NULL而优雅地失败
4. myFree不应该崩溃，当它被传递一个指针已经被释放。

Answer 1

malloc实现跟踪内存分配大小的一种常见方式，以便free知道它们有多大，以便在malloc返回指针之前以字节存储大小。因此，假设您只需要两个字节来存储长度，当malloc的调用者请求n字节的内存时，您实际上分配了n + 2字节。然后将长度存储在前两个字节中，并返回一个指针，指向存储长度的位置后面的字节。

一般来说，对于你的算法，一个简单而天真的实现是用一个空闲内存块的链表来跟踪未分配的内存，这些内存块按照它们在内存中的位置排序。要分配空间，您需要搜索一个足够大的空闲块。然后修改空闲列表以排除该分配。要释放一个块，您可以将它添加回空闲列表，合并相邻的空闲块。

按照现代标准，这不是一个好的malloc实现，但是很多旧的内存分配器都是这样工作的。

Answer 2

你似乎认为256字节的元数据是一个位图，以字节为单位跟踪空闲/使用中。

我认为以下是唯一可能的选择:

我首先将2048字节的堆视为1024个"块"，每个"块"2字节。这将为每个块提供2位信息。您可以将第一个块视为表示该块是否正在使用，第二个块表示下一个块是否与当前块属于同一逻辑块。

当调用free函数时，使用传递的地址在位图中找到正确的起始点。然后，您遍历将每个块标记为空闲的位，直到到达第二个位被设置为0的位，指示当前逻辑块的结束(即，下一个2字节块不是当前逻辑块的一部分)。