9
\$\begingroup\$

I'm learning C and I am currently implementing a memory pool.

I'm writing it in steps, first I implemented a fixed-sized memory pool then I will try to implement a memory pool with a known size of elements but an unknown number of elements and ultimately try to write a generic one that is just a block of memory that can allocate any size.

The pool is actually a block of memory that is initialized with values that are pointers to the next memory like so:

 ______________
|0x8 |0x10|NULL|
|____|____|____|
 ^    ^    ^
 0x0  0x8  0x10

I want to know if I'm heading in the right direction. There is the code

allocator.h:

#include <stdlib.h>

typedef struct FixedPoolAllocator FixedPoolAllocator;

FixedPoolAllocator* FixedPoolAllocator_new(size_t nmemb, size_t size);

void* FixedPoolAllocator_alloc(FixedPoolAllocator *allocator);

void FixedPoolAllocator_free(FixedPoolAllocator *allocator, void *ptr);

void FixedPoolAllocator_destroy(FixedPoolAllocator *allocator);

allocator.c:

#include "allocator.h"

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

typedef struct FixedPoolAllocator {

    // The currently free space in which a value can be stored
    size_t *currentFree;
    size_t numOfMembers;
    size_t memberSize;
    // The actual memory block, It is of type char* so that pointer arithmetic will be easier
    char *mem;

} FixedPoolAllocator;

FixedPoolAllocator* FixedPoolAllocator_new(size_t nmemb, size_t size)
{
    if (0 == size || 0 == nmemb) return NULL;

    FixedPoolAllocator *ret = malloc(sizeof *ret);
    if (NULL == ret) return NULL;

    // Make sure that the size of each member is atleast size_t so that the members can store a memory address
    size_t member_size = MAX(sizeof(size_t), size);

    ret->mem = malloc(nmemb * member_size);
    if (NULL == ret->mem) return NULL;
    // The initial free member
    ret->currentFree = (size_t*)ret->mem;

    ret->numOfMembers = nmemb;
    ret->memberSize = size;

    size_t *temp = ret->currentFree;

    // Assign each member with the address of the next member
    size_t i;
    for (i = 0; i < nmemb - 1; i++) {
        *temp = (size_t) (ret->mem + (i+1) * member_size);
        temp = (size_t*) ((char*)temp + member_size);
    }

    // The last member points to NULL
    *temp = (size_t)NULL;

    return ret;
}

void* FixedPoolAllocator_alloc(FixedPoolAllocator *allocator)
{
    if (NULL == allocator || NULL == allocator->currentFree) return NULL;

    // Return the currently free member and update currentFree to the next member in the list
    void *ret = allocator->currentFree;
    allocator->currentFree = (size_t*)*allocator->currentFree;

    return ret;
}

void FixedPoolAllocator_free(FixedPoolAllocator *allocator, void *ptr)
{
    size_t ptr_as_value = (size_t)ptr;

    // Assign the pointed value with the current free member
    *(size_t*)ptr = (size_t)allocator->currentFree;
    // Update the currenty free member to be the one that was just freed
    allocator->currentFree = ptr;
}

void FixedPoolAllocator_destroy(FixedPoolAllocator *allocator)
{
    free(allocator->mem);

    free(allocator);
}
\$\endgroup\$
3
  • 3
    \$\begingroup\$ Thanks for fixing the post, and I hope you get some good answers! \$\endgroup\$ Commented Sep 26, 2018 at 14:32
  • \$\begingroup\$ Curious, why prohibit size == 0 with if (0 == size || 0 == nmemb) return NULL; versus if (0 == nmemb) return NULL;. I see nothing in code that that prevents use of size == 0. \$\endgroup\$ Commented Sep 27, 2018 at 9:54
  • \$\begingroup\$ Because calling malloc(member_size*nmemb) when size == 0 would allocate memory that isn't really needed \$\endgroup\$ Commented Sep 27, 2018 at 10:21

2 Answers 2

Reset to default
4
\$\begingroup\$

Only a small review

Alignment not guaranteed

temp = (size_t*) ((char*)temp + member_size); attempts to convert a char* to size_t *, yet (char*)temp + member_size is not known to be properly aligned for a size_t*. Insufficient alignment is undefined behavior.

Detect overflow

As the true product of nmemb * member_size may exceed SIZE_MAX:

if (SIZE_MAX/nmemb > member_size) {
  Handle_Overflow();  // clean-up, return NULL;
}
... =  malloc(nmemb * member_size);

Strange uses of size_t as pointer

// The last member points to NULL *temp = (size_t)NULL; implies something wrong. If codes needs a pointer, use a pointer, not size_t. If code needs a size, doesn't use a pointer. Note that size_t and pointers do not necessarily covert well back and forth. They might not be the same memory width either.

This use of size_t as a place to encode a pointer is simply broken. Code needs a new approach.

\$\endgroup\$
3
  • \$\begingroup\$ I actually just read about the notion of 'memory alignment' and I will definitely be fixing that. When I wrote (size_t)NULL it was so that the compiler won't give me a warning about assining (void*) to size_t. \$\endgroup\$ Commented Sep 27, 2018 at 10:24
  • \$\begingroup\$ Also, is there some way to know what is the memory alignement of the CPU in C? \$\endgroup\$ Commented Sep 27, 2018 at 11:02
  • 1
    \$\begingroup\$ @JimMorrison "to know what is the memory alignement": Research max_align_t for C99 or later, else align to a union of wide types double, long, void* and int (*)() (a function pointer). Detail: it is not the alignment requirement of the CPU needed, but the alignment requirement the compiler imposes (which may be more stringent than the CPU). \$\endgroup\$ Commented Sep 27, 2018 at 16:37
3
\$\begingroup\$

If you want enough size to fit a void* then actually use sizeof(void*). If you really want to use an integer type instead of a pointer type then use intptr_t instead of size_t.

size_t member_size = MAX(sizeof(void*), size);

You leak if you fail to allocate the actual pool:

if (NULL == ret->mem) {
    free(ret);
    return NULL;
}

Initializing the pool can be done simpler:

// Assign each member with the address of the next member
size_t i;
for (i = 0; i < nmemb - 1; i++) {
    *temp = (void*) ((char*)temp + member_size);
    temp = (void*) ((char*)temp + member_size);
}

You can also avoid that entire initialization loop by using an extra member that marks the high water mark (the furthest element that was ever allocated) and is used when allocator->currentFree == NULL:

void* FixedPoolAllocator_alloc(FixedPoolAllocator *allocator)
{
    if (NULL == allocator) return NULL;

    if (NULL == allocator->currentFree)
    {
        // nothing in freelist, increment highWater
        if (allocator->highWater == ret->numOfMembers) return NULL;

        void *ret = (void*) (allocator->mem + allocator->highWater);
        allocator->highWater += allocator->memberSize;
        return ret;
    }

    // Return the currently free member and update currentFree to the next member in the list
    void *ret = allocator->currentFree;
    allocator->currentFree = (void*)*allocator->currentFree;

    return ret;
}
\$\endgroup\$
1
  • \$\begingroup\$ 1) Why the unnecessary cast in void *ret = (void*) ((char*)temp + allocator->highWater);? 2) void *ret = ...; ... ret->memberSize; is certainly wrong. \$\endgroup\$ Commented Sep 27, 2018 at 9:46

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.