c - malloc 实现？

Question

我正在尝试为 C 实现 malloc 和 free，但我不确定如何重用内存。我目前有一个看起来像这样的 struct:

typedef struct _mem_dictionary {
    void *addr;
    size_t size;
    int freed;
} mem_dictionary;

我的 malloc 看起来像这样:

void *malloc(size_t size) {
    void *return_ptr = sbrk(size);
    if (dictionary == NULL) 
        dictionary = sbrk(1024 * sizeof(mem_dictionary));

    dictionary[dictionary_ct].addr = return_ptr;
    dictionary[dictionary_ct].size = size;
    dictionary[dictionary_ct].freed = 1;
    dictionary_ct++;

    return return_ptr;
}

当我释放内存时，我会将地址标记为 0(这表明它是空闲的)。在我的 malloc 中，我会使用 for 循环来查找数组中等于 0 的任何值，然后将内存分配给该地址。我对如何实现这一点感到困惑。

Answer 1

最简单的方法是保留一个空闲 block 的链表。在 malloc ，如果列表不为空，则搜索一个足够大的 block 来满足请求并将其返回。如果列表为空或找不到这样的 block ，则调用 sbrk从操作系统分配一些内存。在 free ，您只需将内存块添加到空闲 block 列表中。作为奖励，您可以尝试合并连续的释放 block ，并且可以更改选择要返回的 block 的策略(最适合，最适合，...)。如果 block 大于请求，您也可以选择拆分块。

一些示例实现(未经测试，显然不是线程安全的，使用风险自负):

typedef struct free_block {
    size_t size;
    struct free_block* next;
} free_block;

static free_block free_block_list_head = { 0, 0 };
static const size_t overhead = sizeof(size_t);
static const size_t align_to = 16;

void* malloc(size_t size) {
    size = (size + sizeof(size_t) + (align_to - 1)) & ~ (align_to - 1);
    free_block* block = free_block_list_head.next;
    free_block** head = &(free_block_list_head.next);
    while (block != 0) {
        if (block->size >= size) {
            *head = block->next;
            return ((char*)block) + sizeof(size_t);
        }
        head = &(block->next);
        block = block->next;
    }

    block = (free_block*)sbrk(size);
    block->size = size;

    return ((char*)block) + sizeof(size_t);
}

void free(void* ptr) {
    free_block* block = (free_block*)(((char*)ptr) - sizeof(size_t));
    block->next = free_block_list_head.next;
    free_block_list_head.next = block;
}

备注:(n + align_to - 1) & ~ (align_to - 1)是四舍五入的技巧 n到最接近 align_to 的倍数大于 n .这仅在 align_to 时有效是二的幂并且取决于数字的二进制表示。

当 align_to是二的幂，它只设置了一位，因此 align_to - 1具有所有最低位集(即 align_to 的形式为 000...010...0，而 align_to - 1 的形式为 000...001...1 )。这意味着 ~ (align_to - 1)设置了所有高位，未设置低位(即它的形式为 111...110...0 )。所以x & ~ (align_to - 1)会将 x 的所有低位设置为零并将其向下舍入到最接近 align_to 的倍数.

最后，添加 align_to - 1至 size确保我们四舍五入到最接近 align_to 的倍数(除非 size 已经是 align_to 的倍数，在这种情况下我们希望得到 size )。