Simple Memory Arena

Question

A memory arena implementation targeting standard C - this is draft code for Slider 3 (https://mrsename.blogspot.com/), a new programming language implementation being developed. Other memory arena implementations (as far as I know) are large, complex, slow, proprietary or non-portable.

In the following code: An arena's memory block starts with metadata consisting of an array of "free lists" - linked lists of released spaces. Each index in the array is one less than a number of units - the unit size (specified, along with the arena's total number of units, when creating the arena) is the minimum size of a space. A space is allocated by calling "a_malloc", expanded-if-possible by calling "a_realloc" which expands it into a large-enough free space immediately after it (if no such space exists, the space's content is relocated instead), and released by calling "a_free" which coalesces it with any free space immediately before/after it - those 3 functions are analogous to the C standard functions "malloc", "realloc", and "free". Each space has a pointer-sized header (storing its size) and footer (pointing to the header if the space is deallocated) used when coalescing. The arena provides bump-pointer alllocation within the current free space; once it runs out, the largest free space becomes the new current one. The whole arena can be released at once by calling "a_del". Arenas can be nested (by repeated use of "#include") and can't be shared between threads.

//arena.h
//If this code is written correctly, it makes no assumptions of the target platform, 
//other than C standard compatibility and that pointers and integers are interchangeable.

//The a_init function below initializes an arena. Its parameters are: a pointer to the 
//arena struct, the unit size, and the total number of units.

//The program that includes this file specifies what action to take if an error happens.
#ifndef err
#define err                                         \
    {                                               \
        printf("\nerror at line %d in ", __LINE__); \
        printf("%s", __FILE__);                     \
        exit(1);                                    \
    }
#endif

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

//By default, the C standard allocator is the underlying allocator
#ifndef u_alloc
#define u_alloc malloc
#define u_free free
#endif

#ifndef ArenaSupport
//Needing to be overflow-safe, this code uses overflow blocking code 
//at https://mega.nz/file/zgJRmRIC#HBHnY9uQGOEKkfl468U6lhg2ce9Rj9J8JZjOsokYyrE 
#include "overflow.h"
//The header included above provides functions uadd, usub, umul, and udivL for safe 
//unsigned addition, subtraction, multiplication, and division.

//On systems with virtual memory, memset as used below is perhaps implemented 
//efficiently, e.g. by bringing in page(s) of zeroes.
#define bzero(b, len) memset((b), '\0', (len))

typedef void *ptr;
#define null NULL
#define itmAt(T, a, n) (T *)uadd((adr)a, umul(n, sizeof(T)))
#define adrAt(a, n) *(itmAt(adr, a, n))
#define dec1(f) usub(f, 1)
#define ptrsize sizeof(ptr)
#define Ptrs(n) umul(n, ptrsize)
#define uprint(l) printf("%" PRIu64 "\n", (unum)(l));

typedef struct
{
    ptr data; // the arena's memory block
    adr unitSize,
        start, //start of the arena's content area (which is after the metadata)
        fpos,  //current free space's position
        fsize, //current free space's size
        units, //total number of units
        size;  //the arena's total content size
} ArenaSt;
typedef ArenaSt *Arena;
//size of header plus footer:
#define hfsize Ptrs(2)
adr b_space(ptr p)
{ //obtain header pointer from pointer to space's content:
    return usub((adr)p, ptrsize);
}
ptr a_space(adr p)
{ //from header pointer, obtain pointer to space's content:
    return (ptr)uadd(p, ptrsize);
}
adr roundUp(adr l, adr f)
{
    adr rem = l % f;
    if (rem > 0)
        l = uadd(l, usub(f, rem));
    return l;
}
adr r_space(Arena a, adr l)
{
    l = uadd(l, hfsize);
    //round up to multiple of unit size:
    adr us = a->unitSize;
    return roundUp(l, us);
}
//The free lists are doubly-linked. In a deallocated space, first comes the header, then 
//the Next pointer, then the Previous pointer. For an allocated space, the footer is zero.
#define Size(p) adrAt(p, 0)
#define Next(o) adrAt(o, 1)
#define Prev(o) adrAt(o, 2)
#define Footer(p, osize) adrAt(uadd(p, usub(osize, ptrsize)), 0)
#define Index(bsize) dec1(udivL(bsize, a->unitSize))
#define MetaAt(pos) adrAt(a->data, pos)
#define Meta(bsize) MetaAt(Index(bsize))
#define incb(p, v) p = uadd((p), (adr)(v))
#define decb(p, v) p = usub((p), (adr)(v))
//end of arena's memory block:
#define End uadd(a->size, a->start)
//footer of space right before space S:
#define Before(S) adrAt(usub(S, ptrsize), 0)
void a_prepare(adr o, adr nsize)
{ //Prepares an allocated space
    //store size in header:
    Size(o) = nsize;
    //set footer to zero:
    Footer(o, nsize) = 0;
}
ptr use_space(Arena a, adr osize)
{
    adr p = a->fpos;
    a_prepare(p, osize);
    decb(a->fsize, osize);
    incb(a->fpos, osize);
    return a_space(p);
}
void fl_remove(Arena a, adr o, adr bsize)
{
    //remove a space from its free list:
    adr prev = Prev(o);
    adr sp = Next(o);
    if (prev == 0)
    {
        Meta(bsize) = sp;
        if (sp != 0)
            Prev(sp) = 0;
    }
    else
    {
        //In a linked list, if A.next is B and B.next is C, then after removing B, A.next 
//will be C and C.prev will be A.
        Next(prev) = sp;
        if (sp != 0)
            Prev(sp) = prev;
    }
}
void fl_add(Arena a, adr o, adr osize)
{
    adr prev = Meta(osize);
    Meta(osize) = o;
    Next(o) = prev;
    Prev(o) = 0;
    if (prev != 0)
        Prev(prev) = o;

    Size(o) = osize;
    Footer(o, osize) = o;
}
void join_after(Arena a, adr o, adr osize)
{
    adr end = uadd(o, osize); //end of this space
    if (end < End)
    {
        //is the current space right after this one?
        if ((a->fsize != 0) && (end == a->fpos))
        {
            a->fpos = o;
            incb(a->fsize, osize);
            return;
        }
        else
        {
            adr asize = Size(end);
            adr footer = Footer(end, asize);
            //is the space right after this one free?
            if (footer != 0)
            {
                incb(osize, asize);
                //remove that space from its free list:
                fl_remove(a, end, asize);
            }
        }
    }
    if ((a->fsize == 0) || (a->fpos == o))
    {
        a->fpos = o;
        a->fsize = osize;
    }
    else
    {
        //add this space to its free list
        fl_add(a, o, osize);
    }
}
void a_free(Arena a, ptr op)
{
    if (op == null)
        return;
    adr o = b_space(op);
    adr osize = Size(o);
    if (o > a->start)
    {
        //is the current space right before this one?
        if ((a->fsize != 0) && (uadd(a->fpos, a->fsize) == o))
        {
            o = a->fpos;
            incb(osize, a->fsize);
            a->fsize = osize;
        }
        else
        {
            adr before = Before(o);
            //is the space right before this one free?
            if (before != 0)
            {
                adr bsize = Size(before);
                o = before;
                incb(osize, bsize);
                //remove that space from its free list:
                fl_remove(a, o, bsize);
            }
        }
    }
    join_after(a, o, osize);
}
void a_replace(Arena a)
{
    if (a->fsize != 0)
    { //save current space into the free list matching its size
        fl_add(a, a->fpos, a->fsize);
    }
    //replace current free space with largest one
    for (adr f = dec1(a->units); f > 0; f = dec1(f))
    {
        adr p = MetaAt(dec1(f));
        if (p != 0)
        {
            a->fpos = p;
            a->fsize = umul(a->unitSize, f);
            adr fs = Next(p);
            MetaAt(dec1(f)) = fs;
            if (fs != 0)
                Prev(fs) = 0;
            return;
        }
    }
    a->fpos = 0;
    a->fsize = 0;
}
ptr a_malloc(Arena a, adr osize)
{
    if (osize == 0)
        return null;

    //check if arena is full
    if (a->fsize == 0)
        return null;

    adr otsize = r_space(a, osize);

    if (otsize > a->fsize)
    {
        a_replace(a);
        if (otsize > a->fsize)
        {
            return null;
        }
    }
    if (otsize == a->fsize)
    {
        ptr p = use_space(a, otsize);
        a_replace(a);
        return p;
    }
    return use_space(a, otsize);
}
ptr a_realloc(Arena a, ptr op, adr rnsize)
{
    if (op == null)
        return op;
    if (rnsize == 0)
    {
        a_free(a, op);
        return null;
    }
    adr nsize = r_space(a, rnsize);
    adr o = b_space(op);
    adr osize = Size(o);
    if (nsize <= osize)
        return op;                 //shrinking a space is not supported
    adr end = uadd(o, osize);      //end of this space
    adr diff = usub(nsize, osize); //difference between new size and old size
    if (end < End)
    {
        //is the current space right after this one, and if so, does it have sufficient size?
        if ((end == a->fpos) && (a->fsize >= diff))
        {
            a_prepare(o, nsize);
            decb(a->fsize, diff);
            incb(a->fpos, diff);
            if (a->fsize == 0)
            {
                a_replace(a);
            }
            return op;
        }
        else if ((end != a->fpos) || (a->fsize == 0))
        {
            adr asize = Size(end);
            adr footer = Footer(end, asize);
            //is the space right after this one free, and if so, does it have sufficient size?
            if ((footer != 0) && (asize >= diff))
            {
                //remove that space from its free list:
                fl_remove(a, end, asize);

                if (asize > diff)
                {
                    fl_add(a, uadd(end, diff), usub(asize, diff));
                }
                a_prepare(o, nsize);
                return op;
            }
        }
    }
    ptr n = a_malloc(a, rnsize);
    if (n == null)
    {
        a_free(a, op);
        return null;
    }
    memcpy(n, op, usub(osize, hfsize));
    a_free(a, op);
    return n;
}
#define ArenaSupport
#endif
void a_del(Arena a)
{
    u_free(a->data);
}
void a_init(Arena a, adr us, adr units)
{
    //minimum unit size is 4 times pointer size
    adr min = Ptrs(4);
    if (us < min)
        us = min;
    //unit size must be multiple of pointer size
    us = roundUp(us, ptrsize);

    if (units < 2)
        units = 2;

    a->unitSize = us;
    adr csize = umul(us, units);
    a->size = csize;
    a->fsize = csize;
    adr msize = Ptrs(dec1(units)); //size of metadata
    ptr d = u_alloc(uadd(msize, csize));
    if (d == null)
        err;
    a->data = d;
    bzero(d, msize);
    a->fpos = uadd(msize, (adr)d);
    a->start = a->fpos;
    a->units = units;
}
#ifdef Test
int main(int argc, char **argvp)
{
    ArenaSt z;
    Arena a = &z;
    a_init(a, 0, 12);
    uprint(Ptrs(8));
    uprint(a->fsize);
    ptr q = a_malloc(a, Ptrs(8));
    printf("q:");
    uprint(q);
    uprint(a->fsize);
    ptr w = a_malloc(a, Ptrs(8));
    printf("w:");
    uprint(w);
    uprint(a->fsize);
    ptr e = a_malloc(a, Ptrs(8));
    uprint(e);
    uprint(a->fsize);
    ptr r = a_malloc(a, Ptrs(8));
    uprint(r);
    uprint(a->fsize);

    ptr n = a_malloc(a, 1);
    printf("n:");
    uprint(n); //null

    a_free(a, w);
    a_free(a, e);
    uprint(a->fsize);
    uprint(a->fpos);

    r = a_realloc(a, r, Ptrs(16));
    printf("r:");
    uprint(r); //r is now where w was
    uprint(a->fsize);
    uprint(a->fpos);

    a_free(a, r);
    q = a_realloc(a, q, Ptrs(16));
    printf("q:");
    uprint(q); //q stays in same place
    uprint(a->fsize);
    uprint(a->fpos);
    a_free(a, q);

    ptr x[12];
    for (adr i = 0; i < 12; incb(i, 2))
    {
        x[i] = a_malloc(a, 1);
        ptr p = a_malloc(a, 1);
        printf("p:");
        uprint(p);
        x[uadd(i, 1)] = p;
    }
    uprint(a->fsize);
    uprint(a->fpos);
    for (adr i = 0; i < 12; incb(i, 2))
    {
        a_free(a, x[uadd(i, 1)]);
    }
    uprint(a->fsize);
    uprint(a->fpos);
    for (adr i = 0; i < 12; incb(i, 2))
    {
        printf("x i:");
        uprint(x[i]);

        ptr p = a_malloc(a, 1);
        printf("+ 1:");
        uprint(p);
        x[uadd(i, 1)] = p;
    }

    a_free(a, x[0]);
    uprint(a->fsize);
    uprint(a->fpos);
    printf("x 8:");
    uprint(x[8]);
    a_free(a, x[8]);
    uprint(a->fsize);
    uprint(a->fpos);

    printf("x 7:");
    uprint(x[7]);

    ptr p = a_realloc(a, x[7], Ptrs(6));
    x[7] = p;
    printf("x 7:");
    uprint(p); //x[7] stays in same place

    printf("x 6:");
    uprint(x[6]);
    a_free(a, x[7]);
    uprint(a->fsize);
    uprint(a->fpos);
    p = a_realloc(a, x[6], Ptrs(10));
    x[6] = p;
    printf("x 6:");
    uprint(p); //x[6] stays in same place

    a_del(a);
    return 0;
}
#endif

/*The code above is available for distribution and use, under the following terms:

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHOR(S) OR
COPYRIGHT HOLDER(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

Note: the "overflow.h" header which the above code uses and contains the location of (https://mega.nz/file/zgJRmRIC#HBHnY9uQGOEKkfl468U6lhg2ce9Rj9J8JZjOsokYyrE) defines the "adr" type. In the above code's next version, the size (in pointers) of the metadata array may be reduced to half the number of units. To test the above code, compile and run the following program:

#define Test
#include "arena.h"

Also, can anyone provide insight regarding the implications of licensing code under the terms above?

Answer 1

Avoid macros

Your code relies way too much on macros, to the point it doesn't even look like C anymore and is becoming unreadable. Take for example the first one: err. If I see code using it:

if (some_condition)
    err;

Then unless I know the exact definition of err, it just looks like a variable to me, that is being used in a statement that has no effect. At the very least, make it look like it is a function:

#define err() do {\
    fprintf(stderr, "Error at line %d in %s\n", __LINE__, __FILE__);\
    exit(EXIT_FAILURE);\
} while(0)

This way you have to write:

if (some_condition)
    err();

Now it looks like a function is being called. And forgetting the parentheses or the semicolon will result in an error. Also see this post for why do...while(0) is needed.

Another problem with your err is that you #define this before you #include standard header files. What if those headers use the name err anywhere? It would get replaced by the contents of your macro, at best causing a compilation error, at worst the standard headers would cause subtly different and unexpected behavior.

There are lots of issues with macros, so even better would be to avoid those completely and make err() a regular function, but then of course __LINE__ and __FILE__ don't work the way you want them to anymore. You can also consider just not printing the line number and filename, and instead call abort() on error; this will make it easier to use a proper debugger like gdb, which will give you much more information than just which line and file the error occurred in.

The next set of macros are u_alloc and u_free. Consider not defining them, and use the regular malloc() and free() in the code. Some malloc replacements will just replace those symbols so you don't need to call something else, and for those libraries that have allocation functions that have their own names, you can write #define malloc that_other_alloc.

Some macros look completely pointless:

#define null NULL

Why do that? Why not just write NULL in your code? A lot of the other macros look like it's just to save a bit of typing. But by giving everything short names that are not clear for someone who doesn't know exactly what the definition of all those macros are, the code just becomes unreadable. Saving a few keystrokes should not be a reason to create a macro.

Most of your macros are not safe; the arguments are used without enclosing parentheses. You did it correctly in incb() and decb() though, so that tells me you do know about this issue.

Avoid typedefing standard types

While using typedef for a custom struct is normal practice, avoid creating typedefs for standard types. Consider ptr: it's just two more characters to write void*, and now it's clear to everyone that knows C what it is, without having to wonder: "ptr? I guess it is a pointer? But a pointer to what type?" And adr is even worse; is it a pointer type or an integer holding an address? If you just write uintptr_t, it's immediately clear what it is to someone who knows about <stdint.h>.

Don't abbreviate unnecessarily

To reiterate, a lot of your code is unreadable because you abbreviate things too much. Instead of a, just write arena. I can understand it if you don't like to type a lot, but in that case, consider configuring your editor so it does code completion, and/or use the macro functionality of your editor.

Overly long names are not recommended either, instead they should be concise and meaningful.

Use static for non-public functions and variables

A user of your arena should use a_init(), a_malloc() and so on. Those are part of the public API of your library. They should never call any of the other functions directly. To prevent the user from being able to use those, and to avoid naming conflicts with other libraries or other parts of the user code, make sure the functions and variables that should not be public are made static.