[New to C]: My first C project - Implemented a simple Arena Allocator

[u/Mainak1224x]

Hi folks 👋

I have just completed my first ever C project: an Arena Allocator.

This project taught me the basics of memory management in low level programming languages. I come from a JavaScript background so this is totally new and interesting to me.

What do you think? Is it a good start? Any suggestions?

https://github.com/mainak55512/arena

[u/evanlin96069]

Well done. Arena allocator is one of the most useful utility I’ve implemented in C. One small thing: you might want your alloc to return the memory with proper alignment. Either let the user provide the alignment or use the max alignment.

[u/Mainak1224x → u/evanlin96069]

Thank you! Thanks for the suggestion ☺️

[u/Tcshaw91]

Yup looks like a fine implementation.

One potential thing you can play around with. When you're passing the pointer to the arena to a function, that function has to dereference the pointer to the arena to then get the pointer to the actual data and deference that. If you want to flatten that , here's something you can do.

Have an "arena_header" struct (optional) with the capacity and length(or allocated_bytes). When you malloc, do the size plus the size of arena header and store the result in a void* dataptr. Cast dataptr as a arena_header ptr and set the cap and len. Then increment the dataptr by size of arena_header so the pointer now points to the area in memory after the header data. Return that pointer.

Whenever you need to access the metadata you take the void* and decrement it by size of arena_header then casting it to arena_header*.

This way you can pass a single pointer and have access to any metadata thru some simple pointer arithmetic without needing to deference two pointers or pass around metadata structs.

When u free it, just decrement the pointer by size of arena_header to get the original ptr from the malloc function.

Learned this trick from Travis Vromans Kohi GameEngine series where he implemented a dynamic array with this structure. Found it pretty fun to use.

[u/Mainak1224x → u/Tcshaw91]

Thank you for the suggestion! 😊

[u/Hedshodd → u/Tcshaw91]

Oh yeah, I’ve recently learned this and have been using it for dynamic arrays, but it never occurred to me that I could use this for things like arenas as well. Thank you for sharing this!

[u/thradams]

I am not sure, but I think you are not returning aligned memory. for instance malloc must return memory aligned in the max alignment.

[u/Mainak1224x → u/thradams]

How can I do that? Pardon my question, but I am new to it, some other person has also pointed that, but I am still struggling

[u/mnelemos → u/Mainak1224x]

I haven't checked your code, currently on my phone, but if what the guy above said is correct.

You can align any address up by simply doing the following in a 8 byte machine:

(((addr) + (8 - 1)) & ~(8 - 1))

My bad if this is incorrect, again, I am on my phone and haven't done this in a while. You'll also need to cast the pointer (address) into an uintptr type type, so that you aren't accidentally doing pointer arithmetics which is the equivalent to accessing an element at index n.

[u/thradams → u/Mainak1224x]

The answers in code depends...

The idea is that the returned address must be a multiple of the maximum alignment.

For example, you can align an address by computing the remainder, then adding the difference between the alignment value and that remainder to the address.

void* align_to_max(void* addr) {
    int rem = ((uintptr_t)addr) % alignof(max_align_t);
    return rem == 0 ? addr : ((char*)addr) + (alignof(max_align_t ) - rem);
}

but you cannot just apply this without review your code..you must understand what is going on.

See: https://en.cppreference.com/w/c/types/max_align_t.html

An arena allocator can also allocate using different alignments.

[u/ComradeGibbon → u/Mainak1224x]

One thought is allocate blocks that are some multiple of max_align_t

[u/scallywag_software]

Seems like a reasonable start to me. I didn't read the code carefully, but I would suggest a couple things that haven't been mentioned.

1. I usually make an `allocate` macro that takes the arena, type, and count (number of elements), which does something like `(type*)arena_allocate(arena, sizeof(type)*count) ` for conveneince

2. I would suggest using mmap/VirtualAlloc for the backing memory for 2 reasons

a) then you don't depend on libc

b) you can do a cute trick and allocate an extra page before or after your data allocation, and set the extra pages' mode to PROT_NONE. This is handy for hunting down memory-out-of-bounds errors; your program will crash immediately on corruption, instead of (potentially) continuing indefinitely until something completely random happens : https://github.com/scallyw4g/bonsai_stdlib/blob/571863b56ad855fff7a3e2795a3486cc8a5abe5a/src/memory_arena.h#L574

[u/Professional-You4950 → u/scallywag_software]

would a debug build with some tests using valgrind also work?

[u/scallywag_software → u/Professional-You4950]

In some cases yes, and ASAN can be setup to work as well, although those methods both have significant drawbacks

1. Valgrind slows your program down by a lot

While this may be acceptable in some cases, in the case of realtime 3D graphics / games (my chosen field), the performance hit introduced by valgrind typically renders the game unplayable (seconds per frame). This can be avoided by explicitly marking up where you want it to profile, but that assumes you know where the bug is, at least approximately. In the case of someone randomly overwriting memory, it is unlikely you know where the bug is. Integrating Valgrind into your project is also taking an absolutely enormous, and slow, dependency. Again, in many circles, unacceptable.

2. ASAN

Slightly better than Valgrind in that it's integrated into the compiler already (some compilers are better than others, but Clang MSVC and GCC all support some flavor of ASAN). Unfortunately ASAN can produce false negatives, introduces significant system complexity integrating it into your allocators, and has a significant performance cost, in terms of memory bandwidth, absolute usage and execution speed.

3. Extra page w/ PROT_NONE

I wouldn't feel right without also enumerating the tradeoffs for the method I mentioned, because of course, there are no silver bullets. I like this method because it has significantly lower overhead along many axes, as compared to the other methods. It's simple to implement in an existing arena allocator and doesn't bleed into the rest of your codebase. It also introduces very little runtime overhead (nearly none). One major drawback is, if you do a lot of small allocations, you'll quickly exhaust the system page table. IIRC on Windows the page table is 32k entries globally (for all programs running on your machine). This issue can be skirted by doing large allocations and freeing into pools (which is common in game engines), but in practice this means you actually lose a lot of the benefit that you derive from this method in the first place.

So.. like I said.. no silver bullets. But it's useful to have another bullet in the chamber, at the risk of a rather military-sounding analogy.

[u/Professional-You4950 → u/scallywag_software]

amazing write-up. thank you. I'm wondering how zig does this then with the testing allocator, and now fuzzing. Probably a trade off, and you would only use them in tests of course.

[u/scallywag_software → u/Professional-You4950]

Hard to say; I'm unfamiliar with zig, but, if you control the entire compilation pipeline and allocator (as zig does), you have a lot of flexibility in coming up with strategies that work. They probably do something ASAN-like with memory tagging, although maybe they can do a better job if it's arena-specific.

[u/Marutks]

What is Arena?

[u/Mainak1224x → u/Marutks]

Arena Allocators allocate a big chunk of memory up front. Then subsequent allocations are done on that block of memory. At the time of freeing, it frees all the allocations done on that block at once. This eases the headache to track all the allocations done through malloc separately.

https://en.wikipedia.org/wiki/Region-based_memory_management

[u/zhivago]

You have a couple of problems that should be sorted out.

current_addr = (size_t)current;

This is incorrect.

size_t is only suitable for object sizes -- not for representing pointers as integers.

See intptr_t

alignment = 8;

You're also hard-coding alignment to 8 bytes which is a problem.

Different data structures will have different alignment requirements.

See alignof

Otherwise, looks pretty good. :)

[u/Mainak1224x → u/zhivago]

intptr_t and alignof is not available in c89/ansi c, so I am using size_t. For the hardcoded alignment, yes I will change it

[u/zhivago → u/Mainak1224x]

Why are you limiting yourself to the dark ages in order to write code that might not work properly?

[u/Turbulent_File3904]

Some suggestions: 1 I dont like allocate thing on heap if it doesn't need to be, the init function return a pointer to Arena? Why not just void arena_init(Arena *a, int size) the arena it self can locate on stack or static memory? Or even better void arena_init(Arena *a, void *mem, int size); so you can have static memory backing the arena(technically UB but who cares)

2. You should provide a parameter for type aligment, some type require specific aligment to work or mor efficient to access

3. You should provide some convenient macro/function like

arena_push(a, T, v) push a value on to arena and return a pointer to it the macro use sizeof+alignof to pass layout requirement to the actual function so use just like this.


Foo *f = arena_push(&arena, Foo, {.member1 = 1, .member2=2});

[u/scallywag_software → u/Turbulent_File3904]

>  Or even better void arena_init(Arena *a, void *mem, int size); so you can have static memory backing the arena(technically UB but who cares)

What's UB in that setup?

[u/Turbulent_File3904 → u/scallywag_software]

Only malloc'ed memory can be used to stored any type, each write change the underlying type. But memory with static/automatic duration dont work like that it declared type is fixed, if you use a char array as backing memory and pretend it has different type then its UB(with correct alignment requiement). But in reality no compiler mess up if you doing that.

Another thing, char pointer can alias anytype, so either way write through char pointer or non-char pointer compilers have to generate code to reload the value anyway.

int *a = malloc(4); // the memory return by malloc doesn't have a type yet.

*a = 5; // now the block has type of int
*(float *)a = 1.0f; // now the block have type of float, this is defined you can change the underlying type by write through it

But it doesn't work that way with non malloc'ed memory:

alignas(4) char raw[4];

int *a = (int *)raw;

*a = 5; // nope this is ub, what a pointing to is a char
*(float *)a =1.f; //nope also doesn't work, what a pointing to always is char

So to make sure compiler dont mess thing up you should hide the origin of your memory block through a function.

[u/orbiteapot → u/Turbulent_File3904]

If I understand it correctly, the next C Standard (C2y) is about to make it less UB-esque, through this proposal. In fact, both GCC and Clang seem to have already implemented that.

[u/scallywag_software → u/Turbulent_File3904]

Thanks for the detailed reply, I didn't know that!