malloc 实现? [英] malloc implementation?

问题描述

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

I'm trying to implement malloc and free for C, and I am not sure how to reuse memory. I currently have a struct that looks like this:

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

我的 malloc 看起来像这样:

My malloc looks like this:

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 相等的任何值，然后为该地址分配内存.我有点困惑如何实现这一点.

When I free memory, I would just mark the address as 0 (that would indicate that it is free). In my malloc, I would then use a for loop to look for any value in the array to equal 0 and then allocate memory to that address. I'm kind of confused how to implement this.

推荐答案

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

The easiest way to do it is to keep a linked list of free block. In malloc, if the list is not empty, you search for a block large enough to satisfy the request and return it. If the list is empty or if no such block can be found, you call sbrk to allocate some memory from the operating system. in free, you simply add the memory chunk to the list of free block. As bonus, you can try to merge contiguous freed block, and you can change the policy for choosing the block to return (first fit, best fit, ...). You can also choose to split the block if it is larger than the request.

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

Some sample implementation (it is not tested, and is obviously not thread-safe, use at your own risk):

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 是 2 的幂并且取决于数字的二进制表示.

Note: (n + align_to - 1) & ~ (align_to - 1) is a trick to round n to the nearest multiple of align_to that is larger than n. This only works when align_to is a power of two and depends on the binary representation of numbers.

当 align_to 是 2 的幂时，它只有一个比特集，因此 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 倍数.

When align_to is a power of two, it only has one bit set, and thus align_to - 1 has all the lowest bit sets (ie. align_to is of the form 000...010...0, and align_to - 1 is of the form 000...001...1). This means that ~ (align_to - 1) has all the high bit set, and the low bit unset (ie. it is of the form 111...110...0). So x & ~ (align_to - 1) will set to zero all the low bits of x and round it down to the nearest multiple of align_to.

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

Finally, adding align_to - 1 to size ensure that we round-up to the nearest multiple of align_to (unless size is already a multiple of align_to in which case we want to get size).

这篇关于malloc 实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！