C语言 malloc 实现？

malloc implementation?

提问by user675257

I'm trying to implement mallocand freefor C, and I am not sure how to reuse memory. I currently have a structthat looks like this:

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

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

My malloclooks like this:

我的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;
}

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 0and then allocate memory to that address. I'm kind of confused how to implement this.

当我释放内存时，我只会将地址标记为0（表示它是空闲的）。在 my 中malloc，我将使用 for 循环查找数组中的任何值以使其相等0，然后为该地址分配内存。我有点困惑如何实现这一点。

回答by Sylvain Defresne

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

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

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;
}

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

注意：(n + align_to - 1) & ~ (align_to - 1)是一个技巧，可以四舍五入n到最接近的align_to大于 的倍数n。这仅适用align_to于 2 的幂并且取决于数字的二进制表示。

When align_tois a power of two, it only has one bit set, and thus align_to - 1has all the lowest bit sets (ie. align_tois of the form 000...010...0, and align_to - 1is 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 xand round it down to the nearest multiple of 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）。Sox & ~ (align_to - 1)将设置为零的所有低位x并将其向下舍入到最接近的倍数align_to。

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

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

回答by Heath Hunnicutt

You don't want to set the sizefield of the dictionary entry to zero -- you will need that information for re-use. Instead, set freed=1only when the block is freed.

您不想size将字典条目的字段设置为零——您将需要该信息以供重用。相反，freed=1仅在块被释放时设置。

You cannot coalesce adjacent blocks because there may have been intervening calls to sbrk(), so that makes this easier. You just need a forloop which searches for a large enough freed block:

你不能合并相邻的块，因为可能有对 的干预调用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;
        }
    }
}

This is not a great malloc()implementation. In fact, most malloc/freeimplementations will allocate a small header for each block returned by malloc. The header might start at the address eight (8) bytes lessthan the returned pointer, for example. In those bytes you can store a pointer to the mem_dictionaryentry owning the block. This avoids the O(N) operation in free. You can avoid the O(N) in malloc()by implementing a priority queue of freed blocks. Consider using a binomial heap, with block size as the index.

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

回答by Kingkong Jnr

I am borrowing code from Sylvain's response. He seems to have missed calculating the size of the free_block* ini calculating the overhead.

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

In overall the code works by prepending this free_block as a header to the allocated memory. 1. When user calls malloc, malloc returns the address of the payload, right after this header. 2. when free is called, the address of the starting of the header for the block is calculated (by subtracting the header size from the block address) and that is added to the free block pool.

总的来说，代码的工作原理是将此 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;
}