This is a malloc/free/realloc replacement meant mainly for WebAssembly modules but adaptable to any situation. The goal is to have an allocator that stores information about all allocated buffers in a compact table that can easily be read and analysed, in my main case from the module’s host. This is achieved by having a table that is treated just like any other dynamically allocated buffer and each entry shows which entries come before and after it, where the buffer starts and ends, how much free space is available between the buffer’s end and the next buffer’s start, when a buffer was created or last modified as well as extra info such as the name of the function, file and line number that the call originates from. All this information is meant to provide clarity so that we can clearly see what’s going on in our code and use those insights to use dynamic allocation in more sensible ways.
CIT Alloc also reports helpful errors with a maximum level of detail, for instance attempting to free() or realloc() an address that is in the middle of an existing buffer will report not only the illegal call but also report inside which buffer that address is found, complete with information about the line of code that allocated that buffer in the first place.
CIT Alloc can also optionally erase all the unused bytes in the given memory space, so for instance when I use it in my WebAssembly modules all the unused bytes in the heap are always set to 0xC5. This helps keep a very clean heap that makes more sense when looking at it and also can help catch bugs.
Besides the compact information table a second information buffer called the map may also exist (it’s optional but used by default). This map contains cells that contain the index of the first buffer found in a 8 kB range (adjustable with the CITA_MAP_SCALE define). The first cell represents the first 8 kB of the heap, and the index is always zero (because the buffer of index 0 called "CITA base" has to be at the beginning of the heap). When we look for a buffer’s index by its address (or an address inside of it) we quickly (by a - and a >>) find the index of its cell in the map which gives us the index of a buffer in the table that serves as a starting point from which we can look for the buffer that encompasses the address we’re looking for, so in the worst case we only look through 8 kB worth of allocations instead of always starting from the beginning which would be many MB or even GB worth of allocations.
Information in the table is customisable: indices can be 8, 16 or 32-bit integers (16-bit indices will allow for about 65,532 allocations as index 0 is the base, 1 is the table, 2 may be the optional map and 0xFFFF is "not an index"), the creation and modification timestamps can be excluded, the link flag depends on whether link checking is done and the info string’s length can be adjusted, even down to zero. So with 16-bit indices and 32-bit addresses we can store as little as 16 bytes per allocation.
CIT Alloc is made so that the layout can be observed from outside of the module, so that the allocations of that module can be visualised in real time and understood clearly. This is a good way to see how memory is used inefficiently, how fragmented it might be, what buffers change over time and so you can easily verify if you have leaks or anything in memory that shouldn’t be there anymore. My current visualisation module looks like this:
This is the pure implementation of CIT Alloc, it doesn’t contain anything specific to a platform or application, anything specific to it must be provided through a series of defines. This makes it quite flexible, for instance you could use it to give it control of an entire heap, as I do with WebAssembly modules, or you could make it exist entirely inside a buffer inside a program that wouldn’t use CIT Alloc for its other allocations.
The top of the file contains a lot of information about how it works and how to use it.
This is what I use to use CIT Alloc in my WebAssembly modules. The first part shows how I suppress the linker’s inclusion of the default malloc implementation, then my function prototypes with extra arguments are defined and macros are defined that turn simple standard calls into calls to my functions with extra arguments. Then the necessary defines that CIT Alloc expects are defined and cit_alloc.h is directly included. The last part is the functions that take the place of the standard functions, put the extra info where CIT Alloc can use it and call the matching CIT Alloc functions.
In my module project, in the main header, cita_wasm.h is the first thing to be included, ahead of any other include, and in a C file I also include it like this:
#define CITA_WASM_IMPLEMENTATION_PART1
#include "cita_wasm.h"
#undef CITA_WASM_IMPLEMENTATION_PART1
#include "plugin_rl.h" // this includes cita_wasm.h
#define WAHE_INCLUDE_IMPL
#include <wahe_imports.h>
#include <wahe_utils.h>
#define CITA_WASM_IMPLEMENTATION_PART2
#include "cita_wasm.h"
...Part 1 is for having the functions that suppress the linking of the default allocator, part 2 is for the actual implementation which needs functions defined in the headers above it.
There’s no code related to threading in cit_alloc.h, and neither should there be because you’d want everything to be locked from beginning to end and yet not double-lock when a function calls another one like when cita_realloc() calls cita_malloc(). Any mutex would go inside the functions defined in the platform implementation file. It might look something like this:
void cita_myplatform_free(void *ptr, const char *filename, const char *func, int line)
{
mutex_lock(&cita_mutex);
cita_free(ptr);
mutex_unlock(&cita_mutex);
}