Using allocators to replace malloc()/free()?

Question

Is there any portable way to replace usage of malloc()/free() with wrappers around STL-like allocators?

The context: I have a C library that allows to specify custom malloc()/free()-like functions for memory management, and which is used in multi-threaded contexts. Looking around for a good multi-threaded allocator, I've found that GCC-libstdc++'s mt_alloc performs very well for my workloads. Now I would like to use it in said C library, but how to do it?

The major problem I see is in the deallocate() function, which, contrary to free(), takes the size of the allocated memory block in addition to its address. So I need somehow to keep track of the size associated to every memory allocation, so that it can be fed back to deallocate() when freeing the memory. The simplest solution I've thought about to solve this is to store the size of the allocated memory at the beginning of the memory block, but then I'm not sure how to solve alignment issues that could arise.

Is there any simple solution that I'm overlooking?

Answer 1

On my platform, malloc ensures that allocated memory is aligned at an 8-byte boundary. To mimic this behavior, use an allocator<uint64_t>:

#include <stdint.h>
#include <ext/mt_allocator.h>

static __gnu_cxx::__mt_alloc<uint64_t> theAllocator;

void* mtmalloc(size_t size)
{
    // Divide size by sizeof(uint64_t) and round up
    size_t payloadElementCount = (size + sizeof(uint64_t) - 1) /
                                 sizeof(uint64_t);

    // Add an extra uint64_t to store the chunk size
    size_t chunkElementCount = 1 + payloadElementCount;

    // Allocate the chunk
    uint64_t* chunk = theAllocator.allocate(chunkElementCount);

    // Store the chunk size in the first word
    chunk[0] = chunkElementCount;

    // Return a pointer past where the chunk size is stored
    return static_cast<void*>(chunk + 1);
}

void mtfree(void* pointer)
{
    // The chunk begins one word before the passed in pointer
    uint64_t* chunk = static_cast<uint64_t*>(pointer) - 1;

    // Retrieve the chunk size
    size_t chunkElementCount = chunk[0];

    // Deallocate the chunk
    theAllocator.deallocate(chunk, chunkElementCount);
}

int main()
{
    int* array = (int*)mtmalloc(sizeof(int) * 4);
    array[0] = 0;
    array[1] = 1;
    array[2] = 2;
    array[3] = 3;
    mtfree(array);
}

For your platform, substitute uint64_t with the appropriate type.

You should test this with something like Valgrind to insure there are no memory leaks!

---

Instead of uint64_t, you can use GCC's __BIGGEST_ALIGNMENT__ and Boost's aligned_storage type trait for a solution portable to GCC compilers:

typedef boost::aligned_storage<__BIGGEST_ALIGNMENT__, __BIGGEST_ALIGNMENT__> AlignedType;

Answer 2

There's a great series about this written on altdevblogaday by Paul Laska. Here's the link to the first article: http://altdevblogaday.org/2011/04/11/ready-set-allocate-part-1/

In the article he takes care about block-size allocations and alignment issues. It should provide a well-thought and well-written solution for taking care of your deallocate-issues.

Answer 3

See my answer here regarding storing a value in the beginning of the block. You can slightly modify it for your needs.

Answer 4

The two main methods of object size tracking that I'm aware of are implicitly in a size-segregated allocator with metadata off to the side (e.g. Kingsley-style allocator), or tacking the size in front of the object as an object header (e.g. dlmalloc). A pretty awful third solution would be maintaining a map of every allocated object and its size. That map, of course, would be managed by another allocator.

I think you're on the correct track, and it's good that you're aware of alignment considerations. I tried to look up some information on mt_alloc to see if there are alternatives or surprises, but such information does not seem to be easily forthcoming. Some allocators have a method to query an object size (which may or may not be cheap to do). If the deallocate function requires passing the size explicitly, then I would guess no such function exists, but you never know.

If alignment is important, your calculation will need to be tweaked a bit, since the allocator probably will not return memory aligned appropriately for you. If you know nothing about the alignment of returned pointers, you need something like:

struct object_header {
    size_t size;
};

void * buf = xxmalloc (2 * alignment + size + sizeof(object_header));
void * alignedPtr = (void *) (((size_t) buf + sizeof(object_header) + alignment - 1) & ~(alignment - 1));

If mt_alloc cannot tolerate freeing objects on interior pointers, then this scheme raises a problem for you because by padding out extra space for alignment, you no longer know the original address returned to you. In that case you may need to store an extra field in your header.

Depending on how mt_alloc manages memory internally, tacking on an extra header can also give you substantial overhead. In a size-segregated allocator, tacking on this header can give you up to 2x space overhead on objects up to page-size, at which point you can pay up to the cost of an extra page per object. In other allocators, this may not be an issue, but it's something to look out for.