3

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

PS：这是为了学习。我试图了解结构、链表、内存分配。提前致谢。

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

1 回答 1

2

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

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

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

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

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

我认为这是能够在没有碎片和丢失内存的情况下进行 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;

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

// 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

希望这可以帮助。

于 2012-12-05T00:15:49.857 回答