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

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

一些示例实现(它没有经过测试，而且显然不是线程安全的，使用风险自负)：

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的幂并且依赖于数字的二进制表示时，这才有效。

当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的所有低位设置为0，并将其向下舍入到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条目的指针。这避免了free中的O(N)操作。您可以通过实现释放块的优先级队列来避免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;
}