malloc实现？

Question

我正在尝试实现malloc和freeC,我不知道如何重用内存.我目前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

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

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

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.这仅在2 align_to的幂时有效并且取决于数字的二进制表示.

当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.

最后,添加align_to - 1以size确保我们向上舍入到最接近的倍数align_to(除非size已经是align_to我们想要获得的多个size).

Answer 2

您不希望size将字典条目的字段设置为零 - 您将需要该信息以便重复使用.而是freed=1仅在块被释放时设置.

你不能合并相邻的块,因为可能有干预调用sbrk(),这样可以更容易.你只需要一个for循环来搜索一个足够大的释放块:

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


void *malloc(size_t size)
{
     void *return_ptr = NULL;
     int i;

     if (dictionary == NULL) {
         dictionary = sbrk(1024 * sizeof(mem_dictionary));
         memset(dictionary, 0, 1024 * sizeof(mem_dictionary));
     }

     for (i = 0; i < dictionary_ct; i++)
         if (dictionary[i].size >= size
          && dictionary[i].freed)
     {
         dictionary[i].freed = 0;
         return dictionary[i].addr;
     }

     return_ptr = sbrk(size);

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

     return return_ptr;
}

void free(void *ptr)
{
    int i;

    if (!dictionary)
        return;

    for (i = 0; i < dictionary_ct; i++ )
    {
        if (dictionary[i].addr == ptr)
        {
            dictionary[i].freed = 1;
            return;
        }
    }
}

这不是一个很好的malloc()实现.实际上,大多数malloc/ free实现将为malloc返回的每个块分配一个小头.例如,标题可能从比返回指针少八(8)个字节的地址开始.在这些字节中,您可以存储指向mem_dictionary拥有该块的条目的指针.这避免了O(N)操作free.您可以malloc()通过实现释放块的优先级队列来避免O(N).考虑使用二进制堆,块大小作为索引.

Answer 3

我从Sylvain的回复中借用代码.他似乎错过了计算free_block*ini计算开销的大小.

总体而言,代码的工作原理是将此free_block作为标头添加到已分配的内存中.1.当用户调用malloc时,malloc会在此标头之后返回有效负载的地址.2.当调用free时,计算块头的起始地址(通过从块地址中减去头大小)并将其添加到空闲块池中.

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(free_block) + (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(free_block);
        }
        head = &(block->next);
        block = block->next;
    }

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

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

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