C 自由函数(不使用 malloc)

Question

我正在编写自己的内存分配程序(不使用 malloc)，现在我只能使用 free 函数(在我的代码中为 free)。我相信分配的功能就在那里，唯一的问题在于免费功能。因此，通过运行下面的代码，我可以分配 32 个 block :每个 block 的大小为 48 + 16( header 大小)。 那么如何在分配它们之后立即释放/释放它们呢？你能看看我的免费功能并指出正确的方向吗？

P.S.:这是为了学习目的。我试图了解结构、链表、内存分配。 提前致谢。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BUFFER_SIZE 2048

typedef struct blk_struct
{
    size_t  size_blk;
    struct  blk_struct *next;
    char    data[0];
}blk_struct;

struct blk_struct *first = NULL;
static char buffer[BUFFER_SIZE];

void *asalloc(size_t size)
{
    int nunits = (size + sizeof(blk_struct));
    static int val = 1;

    blk_struct *block, *current;

    //locate position for block
    if(first == NULL)
    {
        block = (blk_struct *)&buffer[0];

        // Sanity check size.
        if(nunits > BUFFER_SIZE)
            return NULL;

        // Initialise structure contents.
        block->size_blk = size;
        block->next     = NULL;

        // Add to linked list.
        first = block;

        // Give user their pointer.
        return block->data;
    }
    //create a free list and search for a free block
    for(current = first; current != NULL; current = current->next)
    {
        // If this element is the last element.
        if(current->next == NULL)
        {
            block = (blk_struct *) (current->data + current->size_blk);

            // Check we have space left to do this allocation
             if((blk_struct *) &block->data[size] >
                     (blk_struct *) &buffer[BUFFER_SIZE])
             {
                 printf("No more space\n");
                 return NULL;
             }

            // Initialise structure contents.
            block->size_blk = size;
            block->next     = NULL;

            // Add to linked list.
            current->next   = block;
            // Give user their pointer.
            return block->data;
        }
    }
    printf("List Error\n");
    return NULL;
}

// 'Free' function. blk_ptr = pointer to the block of memory to be released
void asfree(void *blk_ptr)
{
    struct blk_struct *ptr = first;
    struct blk_struct *tmp = NULL;

    while(ptr != NULL)
    {
        if(ptr == blk_ptr)
        {
            printf("Found your block\n");
            free(blk_ptr);
            break;
        }
        tmp = ptr;
        ptr = ptr->next;
    }
}

// Requests fixed size pointers
int test_asalloc(void)
{
    void *ptr = NULL;
    int size = 48;
    int i = 1;
    int total = 0;

    do
    {
        ptr = asalloc(size);

        if(ptr != NULL)
        {
            memset(ptr, 0xff, size);
            printf("Pointer %d = %p%s", i, ptr, (i % 4 != 0) ? ", " : "\n");
            // each header needs 16 bytes: (sizeof(blk_struct))
            total += (size + sizeof(blk_struct));
            i++;
        }
        asfree(ptr); // *** <--- Calls the 'free' function ***
    }
    while(ptr != NULL);
    printf("%d expected %zu\nTotal size: %d\n", i - 1,
            BUFFER_SIZE / (size + sizeof(blk_struct)), total);
}

int main(void)
{
    test_asalloc();
    return 0;
}

Answer 1

我可以看出您的 asfree 存在一些问题。

寻找区 block 头时需要减去sizeof(blk_struct)。由于用户想要释放的已分配数据就在 header 后面，您有指向该数据的指针，而不是 header 。

第二个问题是拿到header之后怎么办。您不能只调用免费数据。您需要在标题中有一些标志并将该 block 标记为空闲。下次你尝试分配一个 block 时，你需要能够重用空闲 block ，而不仅仅是在最后创建新 block 。能够将一个大的空闲 block 分成两个较小的 block 也很好。为避免碎片，需要将相邻的空闲 block 合并为一个更大的 block 。

目前我正在编写一个操作系统作为一个学校项目。我建议您使用像这样工作的简单分配器:

• 内存块的标题包含指向相邻 block 的链接和空闲标志。
• 一开始有一个大块，上面有空闲标志，覆盖了整个内存。
• 当调用 malloc 时，从头到尾搜索 block 。当找到足够大的 block 时，它会被分成两部分(分配一个和免费提醒)。返回指向已分配 block 数据的指针。
• 当调用 free 时，匹配 block 被标记为空闲。如果相邻 block 也空闲，则将它们合并。

我认为这是能够在不产生碎片和丢失内存的情况下执行 malloc 和 free 的基础。

页眉和页脚的结构如下所示:

// Header of a heap block
typedef struct {
    // Size of the block including header and footer
    size_t size;

    // Indication of a free block
    bool free;

    // A magic value to detect overwrite of heap header.
    uint32_t magic;

} heap_block_head_t;


// Footer of a heap block
typedef struct {
    // A magic value to detect overwrite of heap footer.
    uint32_t magic;

    // Size of the block
    size_t size;

} heap_block_foot_t;

像上面这样的堆满了带有页眉和页脚的 block 的堆很像一个链表。 block 不会明确地描述它们的邻居，但只要你现在它们在那里，你就可以很容易地找到它们。如果您有一个标题的位置，那么您可以将 block 大小添加到该位置，并且您有下一个 block 的标题位置。

// Get next block
heap_block_head_t *current = ....
heap_block_head_t *next = (heap_block_head_t*)(((void*) current) + current->size);

// Get previous block
heap_block_head_t *current = ....
heap_block_foot_t *prev_foot = (heap_block_foot_t*)(((void*) current) - sizeof(heap_block_foot_t));
heap_block_head_t *prev = (heap_block_head_t*)(((void*) prev_foot) + sizeof(heap_block_foot_t) - prev_foot->size);

// Not sure if this is correct. I just wanted to illustrate the idea behind.
// Some extra check for heap start and end are needed

希望这对您有所帮助。