Allocators Are Monkeys with Typewriters

Summary

Table of Contents Introduction Memory allocators Buddy system Allocation Deallocation Introduction Recently I was looking at an issue on mimalloc, a "state-of-the-art" memory allocator developed by Microsoft. The issue was quite simple, developers wanted a way to preallocate a piece of memory and use it as mimalloc's heap. Seeing that mimalloc does not offer this feature, I thought: "how hard can it be to write a memory allocator to manage a preallocated region?". The answer to this question is: "given enough time, even a monkey with a typewriter can write a memory allocator". The implementation is around 163 LoC and very straightforward. Memory allocators To write a memory allocator, we first need to understand what an allocator does. An allocator is "a component of a programming language or runtime system that is responsible for managing the allocation and deallocation of memory during program execution". Roughly speaking, a custom allocator needs to provide a way for the developer to allocate, deallocate and reallocate memory from the operating system. The C standard library provides malloc/free/resize (C11 introduced aligned_alloc and C23 introduced free_sized and free_aligned_sized), then a custom allocator will need to provide the same (or nearly) the same interface for easy integration with already existing code. Memory Fragmentation One of the problems an allocator tries to solve is memory fragmentation. Memory fragmentation happens when the memory is split into small unused blocks throughout a memory chunk, making larger allocations harder because there is fewer contiguous memory available to allocate. Since memory is allocated in chunks, sometimes the real size allocated by the allocator is bigger than the requested size, and the unused memory left is wasted. This is called internal fragmentation. External fragmentation "arises when free memory is separated into small blocks and is interspersed by allocated memory". There are a lot of methods an allocator ...