c - 在 C 中实现隔离内存存储 (malloc)

Question

我正在尝试使用隔离的空闲列表实现我自己的 malloc(使用这本教科书作为引用:http://csapp.cs.cmu.edu/)，但我不确定如何开始。

我有一个方法，malloc_init()，它使用 sbrk 返回一 block 内存。在我的任务上下文中，我不允许在初始调用后请求更多内存，并且允许我请求的内存量受限于 MAX_HEAP_SIZE(由其他人设置) .我在想我会保留一个指针数组，每个指针都指向一个预定大小的空闲列表。

如何在调用 sbrk 后设置这个数组？我如何确定每个“桶”中应该有多少字节以及每个空闲列表的类大小？在代码实现上，如何设置freelist指针数组？任何提示或提示将不胜感激!我在网上查找示例代码，但没有发现任何令人满意的东西。

Answer 1

内存分配理论需要整章或书籍，但这里有一些快速的想法可以帮助您入门。

你可以这样做:

char *blobs[10];

其中 blobs[0] 指向 16 字节的 block ，blobs[1] 指向 32 字节的 block ，blob[2] 指向 64 字节的 block ，...最多 blobs[9] 指向 8k 的 block 。然后，当您获得初始 block 时，请执行以下操作:

bsize = 8192;
idx = 9;
memsize = MAX_HEAP_SIZE;
while (idx >= 0) {
    while (memsize > bsize) {
        /* carve a bsize chunk from your initial block */
        /* and insert it onto a singly-linked headed by listblobs[idx]; */
        /* use the first (sizeof(char *)) bytes of each chunk as a next pointer */
    }
    bsize /= 2;
    idx--;
}

然后，当您需要分配时，找到正确的列表并从中获取一 block 。你需要使用比请求稍大的 block ，这样你就有了记录 block 来自哪个列表的地方，以便您可以释放它。

您可能会发现需要使 blob 数组包含 10 个以上的条目才能处理更大的请求。

如果你想更复杂，你可以在服务请求时做分块。也就是说，如果有人从一个 64KB 的 blob 中请求 33.2K，也许你只想给 34KB 并将 64K blob 中的剩余空间分成 16K、8K、4K、2K block 以添加到那些空闲列表中。