logo标签列表

malloc实现方式？

cmemory-managementmallocfree
34

我正在尝试为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的地址，然后为该地址分配内存。我有点困惑如何实现这一点。

2
这里有一篇关于dlmalloc的不错介绍：http://g.oswego.edu/dl/html/malloc.html - ninjalj
3个回答
29

最简单的方法是维护一个空闲块的链表。在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）。
malloc函数第一行中的魔数是干什么用的？ - Igbanam
它将 (size + sizeof(size_t)) 四舍五入到比 (size + sizeof(size_t)) 大的最近的 align_to 的倍数。这仅在 align_to 是2的幂时有效。 - Sylvain Defresne
在《编程珠玑》一书的第九章“代码调优”中，Jon Bentley举了一个类似的技巧作为例子，即使用链表缓存来保存已分配的内存（而不是再次分配），以加速图形程序（该程序在malloc上花费太多时间）。遗憾的是，该书的示例中没有包含代码，因此像这样看到代码对我特别有用。 - Drake Sobania
9

不要将字典条目的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)操作。考虑使用二项式堆，并以块大小作为索引。

抱歉，我对C语言还比较新，但是malloc()函数中的字典变量是什么？ - no92
@no92 -- 我本应该把它命名为“日志”，而不是“字典”。请记住，这只是我对malloc的一个示例和微不足道的实现。它至少有一个明显的缺陷：一次最多只能分配1024个块。给出这个示例的唯一目的是为读者提供一个实现自己的malloc的起点。这只是实现malloc/free库的概念基础，甚至没有实现realloc作为另一个明显的缺陷。它可能甚至不是最好的例子。 :) - Heath Hunnicutt
6

我正在借鉴Sylvain的回答中的代码。他似乎错过了计算free_block*大小时计算开销的步骤。

总体上，该代码通过将这个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;
}
1
谢谢，我认为这个回答比Sylvain的回答略微更正确，因为我只是在想这个问题。overhead变量是一个非常好的想法，只是没有正确计算或使用。 - bbill
有人能告诉我malloc函数中head的用途吗？(free_block** head = &(free_block_list_head.next);) 我没有看到它在任何地方被使用。此外，为什么我们在返回之前要添加sizeof(free_block)？ - user1719160
head是指向包含指针的地址的指针。它在while循环中用于取消链接返回给用户的内存块。添加和减去sizeof(free_block)是一种常见而巧妙的技巧，可以将元数据“隐藏”起来，不让调用者看到。 - Björn Lindqvist
在free()的实现中也存在一个小错误，因为free(NULL)会导致段错误。 - Björn Lindqvist
Sylvain使用sizeof(size_t)而不是sizeof(free_block)，因为“next pointer”仅用于已释放的块，否则它可能会被用户覆盖。 - bjoernz
1
你好，能否为这个实现添加适当的 realloc 函数？ - Phillip
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接