自定义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位,如果分配了一个字节或者它是空闲的,我可以存储一个位数组.但是当我myfree打电话时ptr,我不知道开始时分配了多少大小.我不能使用任何额外的位.

我似乎认为没有办法解决这个问题,但我一直在重申可以做到这一点.有什么建议 ？

编辑1:

1. 对齐限制不存在.我以为我不会调整任何东西.
2. 有一个演示程序执行了一系列的mallocs和释放来测试它,它没有任何小的内存块.但这并不保证任何事情.

编辑2:

文档中的指南:关于代码的某些指南:

1. 管理私有堆中的堆元数据; 不要在提供的私有堆之外创建额外的链接列表;
2. 设计mymalloc,myrealloc,myFree为所有可能的输入工作.
3. myrealloc应该像realloc在C++库中 一样执行以下操作void* myrealloc( void* C, size_t newSize ):
   1. 如果newSize大于块中的大小reallocThis:
      1. 它应该首先尝试分配一个大小的块,newSize以便新的块的基指针也是reallocThis;
      2. 如果没有可用的空间来进行就地分配,它应该在不同的区域分配一块请求的大小; 然后它应该复制上一个块的内容.
      3. 如果函数未能分配所请求的内存块,NULL则返回指针,并且参数指向的内存块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 字节块不是当前逻辑块的一部分）。

[哎呀：刚刚注意到罗斯里奇已经在评论中提出了几乎相同的基本想法。]