View on GitHub


A memory allocator written in C.

Memory Allocator


This memory allocator is akin to ptmalloc2, jemalloc, tcmalloc and many others. These allocators are the underlying code of malloc.

Heap allocators request chunks of memory from the operating system and place several (small) object inside these. Using the free call these memory objects can be freed up again, allowing for reuse by future malloc calls. Important performance considerations of a heap allocator not only include being fast but also to reduce memory fragmentation.

malloc, free and realloc have been implemented without using the standard library versions of these functions. brk(2) and sbrk(2) has been used for asking the kernel for more heap space.

(Normal heap allocators may also use mmap to request memory from the kernel.)

Implementation Details

  1. malloc, free and realloc behave exactly as specified by their man-page description, whilst the Notes sections have been skipped as these are implementation-specific.
  2. This allocator does not place any restrictions on the maximum amount of memory supported or the maximum number of objects allocated. For example, it will scale regardless of whether the maximum brk size is 64KB or 1TB.
  3. A region of memory can be reused after freeing it with free.
  4. realloc behaves as described on its man-page and only allocates a new object when needed.
  5. The allocator batches brk calls, i.e., it does not need to request memory from the kernel for every allocation.
  6. The amortized overhead per allocation is on average 8 bytes or less.
  7. The allocator tries to optimize for locality (reuse recently freed memory).
  8. The allocator gives back memory to the kernel (using brk) when a large portion of the allocated memory has been freed up.
  9. The allocation functions work correctly without the my prefix.


The file test/tests.c contains a number of (automated) test cases that evaluate the different aspects of your allocator. It can be invoked manually via ./test <test name>. Running make check will run all test cases.