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

Question

我正在尝试使用一个隔离的自由列表来实现我自己的malloc（使用本教科书作为参考：http://csapp.cs.cmu.edu/)，但我不知道该怎么开始。

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

调用sbrk后如何设置此阵列？如何计算每个"bucket"中应该有多少字节，以及每个自由列表的类大小？在代码实现方面，如何设置自由列表指针数组？任何提示或提示都将不胜感激！我在网上查找了示例代码，但没有发现任何令人满意的内容。

Answer 1

内存分配理论需要整章或整本书，但这里有一些快速的想法可以让你开始。

你可以做一些类似的事情：

char *blobs[10];

其中blobs[0]指向16字节的块，blobs[1]指向32字节的块、blobs[2]指向64字节的块等等。。。高达指向8k块的斑点[9]。然后当你得到初始区块时，做一些类似的事情：

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

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

您可能会发现，需要使blobs数组超过10个条目，这样您才能处理更大的请求。

如果你想变得更复杂，你可以在处理请求时进行块划分。也就是说，如果有人从64KB的blob请求33.2K，也许你只想给出34KB，并将64K blob中的剩余空间划分为16K、8K、4K、2K块，以添加到这些空闲列表中。

Answer 2

不确定是否有"标准"的方法来做到这一点，但只是从逻辑上思考：你有一大块内存，你想把它分成不同大小的桶。因此，首先你需要弄清楚你要支持的水桶尺寸。我不是一个系统程序员，所以我不能说什么是"好"的bucket大小，但我想它们将是2的一些非连续幂（例如，16字节、64字节、512字节等）。

一旦你有了存储桶的大小，你就需要把内存块划分成几个存储桶。最好的方法是在每个块的开头使用一点blob空间作为标头。标头将包含块的大小和指示块是否空闲的标志。

struct header
{
    unsigned short blkSize;
    unsigned char  free;
};

在init函数中，您将划分blob:

void my_init()
{
    // "base" is a pointer to the start of the blob
    void *base = sbrk((intptr_t)MAX_HEAP_SIZE);
    if (!base)
    {
        // something went wrong
        exit(1);
    }
    // carve up the blob into buckets of varying size
    header *hdr = (header*)base;
    for (int i = 0; i < num16Bblocks; i++)
    {
        hdr->blkSize = 16;
        hdr->free    = 1;
        // increment the pointer to the start of the next block's header
        hdr += 16 + sizeof(header);
    }
    // repeat for other sizes
    for (int i = 0; i < num64Bblocks; i++)
    {
        hdr->blkSize = 64;
        hdr->free    = 1;
        // increment the pointer to the start of the next block's header
        hdr += 64 + sizeof(header);
    }
    // etc
}

当用户请求一些内存时，您将遍历blob，直到找到适合的最小bucket，将其标记为不再空闲，并返回一个指向bucket开头的指针：

void *my_malloc(size_t allocationSize)
{
    // walk the blocks until we find a free one of the appropriate size
    header *hdr = (header*)base;
    while (hdr <= base + MAX_HEAP_SIZE)
    {
        if (hdr->blkSize >= allocationSize &&
            hdr->free)
        {
            // we found a free block of an appropriate size, so we're going to mark it
            // as not free and return the memory just after the header
            hdr->free = 0;
            return (hdr + sizeof(header));
        }
        // didn't fit or isn't free, go to the next block
        hdr += hdr->blkSize + sizeof(header);
    }
    // did not find any available memory
    return NULL;
}

要释放（回收）一些内存，只需在标头中将其标记为空闲即可。

void my_free(void *mem)
{
    // back up to the header
    header *hdr = (header*)(mem - sizeof(header));
    // it's free again
    hdr->free = 1;
}

这是一个非常基本的实现，有几个缺点（例如，不能处理碎片，不是很动态），但它可能会给你一个很好的起点。