c - 实现池内存 API - 处理 union

Question

我想为数据结构实现一个 API，该数据结构预先将内存分配给一定大小的多个对象，而不是每次根据需要为每个对象使用“malloc”和“free” .

API 应包含以下三个功能:

pool* API_init(size_t sizeOfObj, int numOfObj)

接受两个参数，对象大小和我们希望存储的此类对象的数量，并返回指向池的指针 - 管理内存的数据结构。

void* API_malloc(Pool* pool)

接受池并返回单个对象的新分配指针。

void API_free(Pool* pool, void* obj)

接受两个参数，池和需要标记为未使用的地址。

方法“API_malloc”和“API_free”的复杂度时间要求是恒定的，池的内存复杂度应该是“sizeOfObj”*“numOfObj”+恒定。

为了处理碎片，我想将池定义为大小为“sizeOfObj”字节的 block 的链接列表，其中还包含指向下一个未使用的 block 的指针。 为了节省内存空间，我决定用UNION来定义chunk。

这是我的实现:

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

typedef struct Pool Pool;
typedef union Chunk Chunk;


union Chunk{

    char* padding;
    Chunk* next;
};

struct Pool{

    Chunk* nextFreeChunk;
};

Pool* API_init(int sizeOfObj, int numOfObj){

    Pool* res = (Pool*) malloc(sizeof(Pool));
    Chunk* next;
    Chunk* curr;

    for(int i = numOfObj -1; i >= 0; i--){

        curr = (Chunk*) malloc (sizeof(Chunk));
        curr->padding = (char*) malloc(sizeOfObj);

        if(i < numOfObj -1)
            curr->next = next;

        next = curr;
    }

    res->nextFreeChunk = curr;
    return res;
}

void* API_malloc(Pool* pool){

    void* res = pool->nextFreeChunk;
    pool->nextFreeChunk = (pool->nextFreeChunk)->next;
    return res;
}

void API_free(Pool* pool, void* obj){

    Chunk* ch = (Chunk*) obj;
    ch->next = pool->nextFreeChunk;
    pool->nextFreeChunk = ch;
}

我的问题是，正如我所定义的， block 不一定具有给定的“sizeOfObj”大小，并且 char 指针正在浪费内存(超过常量)。

我知道 union 不能将灵活的 char 数组作为成员，因此我无法在“API_init”内定义成员“char padding[sizeOfObj]”。

任何解决我的问题或新的实现方法的建议将不胜感激。

Answer 1

您遇到的问题是，由于 padding 和 next 共享相同的内存(属于 union )，当您分配给 next 时， padding 指向的任何数据都将丢失。

您的解决方案是让您的 block 成为您的数据，或者成为指向下一个空闲 block 的指针。因此，对于每个malloc()，我们需要分配max(sizeof(union Chunk), sizeOfObj)

union Chunk{
    char data[1]; /* `1` is a dummy value, the compiler doesn't actually really care 
                     if we allocate and use more than 1 char */ 
    union Chunk* next;
};


/* We return `struct Pool` by value to save a `malloc()`  (c is not java)*/ 
struct Pool API_init(size_t sizeOfObj, size_t numOfObj){

    union Chunk* prev = NULL;
    size_t chunksize = max(sizeof (union Chunk), sizeOfObj);

    /* counting upwards is easier than downwards */
    for(size_t i = 0; i < numOfObj; i++){

        /* We don't cast the return value from `malloc()`. This is c, not c++ */
        curr = malloc(chunksize);

        curr->next = prev;

        prev = curr;
    }

    struct Pool res;   
    res.nextFreeChunk = curr;
    return res;
}

您的 API_malloc() 和 API_free() 看起来不错，只不过它们是用 c++ 而不是 c 编写的。用 c 编写时不要使用 c++ 语法。并使用 c 编译器，而不是 c++ 编译器。

您可以通过一次性分配整个池来改进这一点，而不是使用多个 malloc():

struct Pool{
    char *buffer;
    Chunk* nextFreeChunk;
};

struct Pool API_init(size_t sizeOfObj, size_t numOfObj){

    size_t chunksize = max(sizeof (union Chunk), sizeOfObj);

    /* Checking for overflow is left as an exercise for the reader */
    size_t buffersize = numOfObj * chunksize;

    char *buffer = malloc(buffersize);


    for(size_t i = 0; i < numOfObj - 1; i++){

        union Chunk *curr = (union Chunk *)(buffer + i * chunksize);
        curr->next = (union Chunk *)(buffer + (i+1) * chunksize);

    }

    if (numOfObj)
    {
        union Chunk *last = (union Chunk *)(buffer + (numOfObj - 1) * chunksize);
        last->next = NULL;
    }


    struct Pool res;
    res.buffer = buffer;    
    res.nextFreeChunk = (union Chunk *)buffer;
    return res;
}

当然，为了简洁起见，任何错误检查和小错误修复都会被省略