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中，您只需将内存块添加到空闲块列表中即可。作为奖励，您可以尝试合并连续的释放块，并且可以更改选择要返回的块的策略（首先适合，最佳适合，...）。如果块大于请求，您还可以选择拆分块。

一些示例实现（它未经测试，显然不是线程安全的，使用风险自负）：

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 舍入到大于 n 的 align_to 的最接近倍数的技巧。仅当 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 的所有低位设置为零，并将其向下舍入到 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;
}