micro-engine.h/include/micro-engine/micro-arena.h at main · San7o/micro-engine.h

620 lines (525 loc) · 16.2 KB
///////////////////////////////////////////////////////////////////////
// SPDX-License-Identifier: MIT
// micro-arena.h
// =============
// Header only memory allocator in C99 (first fit). It implements
// the common memory functions from stdlib.h:
//       void *micro_arena_malloc(MicroArena *ma, size_t size);
//       void micro_arena_free(MicroArena *ma, void * ptr);
//       void *micro_arena_calloc(MicroArena *ma, size_t nmemb, size_t size);
//       void *micro_arena_realloc(MicroArena *ma, void * ptr, size_t size);
//       void *micro_arena_reallocarray(MicroArena *ma, void * ptr, size_t nmemb, size_t size);
// Author:  Giovanni Santini
// Mail:    giovanni.santini@proton.me
// Github:  @San7o
//     char buff[100];
//     MicroArena ma;
//     micro_arena_init(&ma, &buff[0], 100);
//     int array_len = 10;
//     int* mem = micro_arena_malloc(&ma, sizeof(int) * array_len);
//     assert(mem != NULL);  
//     micro_arena_free(&ma, mem);
// Do this:
//   #define MICRO_ARENA_IMPLEMENTATION
// before you include this file in *one* C or C++ file to create the
// implementation.
// i.e. it should look like this:
//   #include ...
//   #include ...
//   #include ...
//   #define MICRO_ARENA_IMPLEMENTATION
//   #include "micro-arena.h"
// You can tune the library by #defining certain values. See the
// "Config" comments under "Configuration" below.
// The official git repository of micro-arena.h is hosted at:
//     https://github.com/San7o/micro-arena.h
// This is part of a bigger collection of header-only C99 libraries
// called "micro-headers", contributions are welcome:
//     https://github.com/San7o/micro-headers
// Implementation info
// -------------------
// There are many ways to implement an allocator, with ceratin
// tradeoffs to choose from.
//   - linear allocator: The simplest allocator is probably a linear
//     allocator which is only able to allocate chunks from memory but
//     not free them. You can think of it as keeping a pointer to the
//     start of the free memory, and incrementing it by the amount of
//     memory to be allocated each time. This is often used in arena
//     allocators due to its simplicity, speed and the fact that you
//     often free the entire arena all at once when you don't need it
//     anymore.
//   - slab alloctor: this is useful when you need to allocate memory
//     of a known fixed amount. This allocator conceptually resembles
//     a stack of blocks of free memory: you pop the head to allocate
//     that block, and you push it back when you free it.
//   - free list: in this type of allocator, we keep a dynamic list of
//     free blocks. This allows us to allocate blocks of any size
//     by resizing or eliminating the free blocks when we allocate,
//     and expanding them when we free memory. The main disadvantage
//     is that we need to iterate over the block to find a range
//     bit enough for our allocation, which takes linear time and
//     is not ideal for realtime systems.
//   - buddy system: this is a fast algorythm for allocating memory of
//     any size. Essentially we divide the memory into blocks with
//     their size being a power of two. Then when we allocate, we
//     mark one of these blocks as used, and when we free we mark it
//     as unused. The problem here is that we may allocate a block
//     that is much bigger than what we need, creating a lot of
//     internal fragmentation.
// In the real world, more sophisticated allocators actually use more
// then one algorithm based on the size that needs to be allocated.  A
// good allocator may also support additional features such as
// per-thread memory and keeping the allocated memory aligned to some
// If you want to see more advanced memory allocaters, check out these
// projects:
//     https://google.github.io/tcmalloc/overview.html
//     https://nothings.org/stb/stb_malloc.h
#ifndef MICRO_ARENA
#define MICRO_ARENA
#define MICRO_ARENA_MAJOR 0
#define MICRO_ARENA_MINOR 1
#define MICRO_ARENA_VERSION \
  ((MICRO_ARENA_MAJOR << 8) | MICRO_ARENA_MINOR)
#ifdef __cplusplus
extern "C" {
// Configuration
// Config: Prefix for all functions
// For function inlining, set this to `static inline` and then define
// the implementation in all the files
#ifndef MICRO_ARENA_DEF
  #define MICRO_ARENA_DEF extern
// Config: Include an example program, see the end of the header
// #define MICRO_ARENA_EXAMPLE_MAIN
// Config: Maximum number of pointers. A limit is required since
//         we need to keep track of what pointers were allocated and
//         what parts of memory are free.
#ifndef MICRO_ARENA_MAX_NUM_CHUNKS
  #define MICRO_ARENA_MAX_NUM_CHUNKS 1024
// Config: Include debug functions
// #define MICRO_ARENA_DEBUG
// Config: Enable thread safety
// #define MICRO_ARENA_MULTITHREADED
#ifndef _SIZE_T_DEFINED
  #define _SIZE_T_DEFINED
  typedef __SIZE_TYPE__ size_t;
#ifdef MICRO_ARENA_MULTITHREADED
  #include <pthread.h>
typedef struct {
  char* start;
  size_t size;
} MicroArenaChunk;
typedef struct {
  MicroArenaChunk chunks[MICRO_ARENA_MAX_NUM_CHUNKS];
  size_t len;
} MicroArenaChunkList;
typedef struct {
  char *mem;
  MicroArenaChunkList free_chunks;
  // In this implementation we store the used chunks because we need
  // to know how bit was the allocated area. An alternative
  // implementation would be to store this information behind the
  // pointer.
  MicroArenaChunkList used_chunks;
  #ifdef MICRO_ARENA_MULTITHREADED
  pthread_mutex_t arena_mutex;
} MicroArena;
// Function declarations
MICRO_ARENA_DEF void micro_arena_init(MicroArena *ma, void* memory, size_t size);
// First fit. O(ma->free_chunks.len)
MICRO_ARENA_DEF void *micro_arena_malloc(MicroArena *ma, size_t size);
// O(max(ma->free_chunks.len, ma->used_chunks.len)
MICRO_ARENA_DEF void micro_arena_free(MicroArena *ma, void *ptr);
MICRO_ARENA_DEF void *micro_arena_calloc(MicroArena *ma, size_t nmemb, size_t size);
MICRO_ARENA_DEF void *micro_arena_realloc(MicroArena *ma, void *ptr, size_t size);
MICRO_ARENA_DEF void *micro_arena_reallocarray(MicroArena *ma, void *ptr,
                                               size_t nmemb, size_t size);
// Global allocator (same API as libc)
#ifdef MICRO_ARENA_GLOBAL
extern MicroArena _ma_global_arena;
#define micro_arena_ginit(memory, size) \
  micro_arena_init(&_ma_global_arena, memory, size)
#define micro_arena_gmalloc(size) \
  micro_arena_malloc(&_ma_global_arena, size)
#define micro_arena_gfree(ptr) \
  micro_arena_free(&_ma_global_arena, ptr)
#define micro_arena_gcalloc(nmemb, size) \
  micro_arena_calloc(&_ma_global_arena, nmemb, size)
#define micro_arena_grealloc(ptr, size) \
  micro_arena_realloc(&_ma_global_arena, ptr, size)
#define micro_arena_greallocarray(ptr, nmemb, size) \
  micro_arena_reallocarray(&_ma_global_arena, ptr, nmemb, size)
#endif // MICRO_ARENA_GLOBAL
MICRO_ARENA_DEF void
micro_arena_chunk_list_reset(MicroArenaChunkList *chunk_list);
MICRO_ARENA_DEF MicroArenaChunk*
micro_arena_chunk_list_add(MicroArenaChunkList *chunk_list,
                           void* start, size_t size);
// O(chunk_list->len) = O(MICRO_ARENA_MAX_NUM_CHUNKS)
// May invalidate previous pointers to its items
MICRO_ARENA_DEF void
micro_arena_chunk_list_remove(MicroArenaChunkList *chunk_list,
                              void* start);
MICRO_ARENA_DEF MicroArenaChunk*
micro_arena_chunk_list_get(MicroArenaChunkList *chunk_list,
                           void* start);
#ifdef MICRO_ARENA_DEBUG
MICRO_ARENA_DEF void
micro_arena_debug_print(MicroArena *ma);
MICRO_ARENA_DEF void
micro_arena_debug_print_chunk_list(MicroArenaChunkList *chunk_list);
#endif // MICRO_ARENA_DEBUG
MICRO_ARENA_DEF int micro_arena_major(void);
MICRO_ARENA_DEF int micro_arena_minor(void);
MICRO_ARENA_DEF int micro_arena_version(void);
// Implementation
#ifdef MICRO_ARENA_IMPLEMENTATION
#ifdef MICRO_ARENA_DEBUG
#include <stdio.h>
MICRO_ARENA_DEF void micro_arena_init(MicroArena *ma, void* memory, size_t size)
    return;
  micro_arena_chunk_list_reset(&ma->free_chunks);
  micro_arena_chunk_list_reset(&ma->used_chunks);
  micro_arena_chunk_list_add(&ma->free_chunks, memory, size);
  #ifdef MICRO_ARENA_MULTITHREADED
  pthread_mutex_init(&ma->arena_mutex, NULL);
MICRO_ARENA_DEF void *micro_arena_malloc(MicroArena *ma, size_t size)
  #ifdef MICRO_ARENA_MULTITHREADED
  pthread_mutex_lock(&ma->arena_mutex);
  #ifdef MICRO_ARENA_DEBUG
  printf("DEBUG: micro_arena_malloc: called with size %ld\n", size);
    goto exit;
  for (size_t i = 0; i < ma->free_chunks.len; ++i)
    if (ma->free_chunks.chunks[i].size < size)
      continue;
    MicroArenaChunk *used_chunk =
      micro_arena_chunk_list_add(&ma->used_chunks,
                                 ma->free_chunks.chunks[i].start,
    if (!used_chunk)
      goto exit;
    ma->free_chunks.chunks[i].start = ma->free_chunks.chunks[i].start + size;
    ma->free_chunks.chunks[i].size  = ma->free_chunks.chunks[i].size - size;
    #ifdef MICRO_ARENA_MULTITHREADED
    pthread_mutex_unlock(&ma->arena_mutex);
    #ifdef MICRO_ARENA_DEBUG
    printf("DEBUG: micro_arena_malloc: allocated %ld at chunk %p\n",
           size, used_chunk->start);
    return (void*)used_chunk->start;
  #ifdef MICRO_ARENA_MULTITHREADED
  pthread_mutex_unlock(&ma->arena_mutex);
  return NULL;
MICRO_ARENA_DEF void micro_arena_free(MicroArena *ma, void *ptr)
  #ifdef MICRO_ARENA_MULTITHREADED
  pthread_mutex_unlock(&ma->arena_mutex);
  #ifdef MICRO_ARENA_DEBUG
  printf("DEBUG: micro_arena_free: called with ptr %p\n", ptr);
    goto exit;
  MicroArenaChunk *used_chunk =
    micro_arena_chunk_list_get(&ma->used_chunks, ptr);
  if (!used_chunk)
    goto exit;
  #ifdef MICRO_ARENA_DEBUG
  printf("DEBUG: micro_arena_free: found used chunk start = %p, size = %ld\n",
         (void*)used_chunk->start,
         used_chunk->size);
  MicroArenaChunk *free_chunk_after = NULL;
  MicroArenaChunk *free_chunk_before = NULL;
  for (size_t i = 0; i < ma->free_chunks.len; ++i)
    if (ma->free_chunks.chunks[i].start ==
        used_chunk->start + used_chunk->size)
      free_chunk_after = &ma->free_chunks.chunks[i];
    if (used_chunk->start ==
        ma->free_chunks.chunks[i].start + ma->free_chunks.chunks[i].size)
      free_chunk_before = &ma->free_chunks.chunks[i];
  if (free_chunk_before && free_chunk_after)
    #ifdef MICRO_ARENA_DEBUG
    printf("DEBUG: micro_arena_free: free chunks were found before and after ptr\n");
    free_chunk_before->size += used_chunk->size + free_chunk_after->size;
    micro_arena_chunk_list_remove(&ma->used_chunks, used_chunk->start);
    micro_arena_chunk_list_remove(&ma->free_chunks, free_chunk_before->start);
    goto exit;
  if (free_chunk_before)
    #ifdef MICRO_ARENA_DEBUG
    printf("DEBUG: micro_arena_free: free chunks were found before ptr\n");
    free_chunk_before->size += used_chunk->size;
    micro_arena_chunk_list_remove(&ma->used_chunks, used_chunk->start);
    goto exit;
  if (free_chunk_after)
    #ifdef MICRO_ARENA_DEBUG
    printf("DEBUG: micro_arena_free: free chunks were found after ptr\n");
    free_chunk_after->start = used_chunk->start;
    free_chunk_after->size += used_chunk->size;
    micro_arena_chunk_list_remove(&ma->used_chunks, used_chunk->start);
    goto exit;
  #ifdef MICRO_ARENA_DEBUG
  printf("DEBUG: micro_arena_free: no free chunks found before or after prt\n");
  micro_arena_chunk_list_add(&ma->free_chunks,
                             used_chunk->start,
                             used_chunk->size);
  micro_arena_chunk_list_remove(&ma->used_chunks, used_chunk->start);
  #ifdef MICRO_ARENA_MULTITHREADED
  pthread_mutex_unlock(&ma->arena_mutex);
MICRO_ARENA_DEF void *micro_arena_calloc(MicroArena *ma, size_t nmemb, size_t size)
    return NULL;
  char* mem = micro_arena_malloc(ma, size * nmemb);
  if (!mem)
    return NULL;
  for (size_t i = 0; i < nmemb * size; ++i)
    mem[i] = 0;
  return mem;
MICRO_ARENA_DEF void *micro_arena_realloc(MicroArena *ma, void *ptr, size_t size)
    return NULL;
  if (ptr == NULL)
    return micro_arena_malloc(ma, size);
  MicroArenaChunk *used_chunk =
    micro_arena_chunk_list_get(&ma->used_chunks, ptr);
  if (!used_chunk)
    return NULL;
  char* mem = micro_arena_malloc(ma, size);
  if (!mem)
    return NULL;
  size_t min_size = (used_chunk->size < size) ? used_chunk->size : size;
  for (size_t i = 0; i < min_size; ++i)
    mem[i] = ((char*)ptr)[i];
  micro_arena_free(ma, ptr);
  return mem;
MICRO_ARENA_DEF void *micro_arena_reallocarray(MicroArena *ma, void *ptr,
                                               size_t nmemb, size_t size)
  return micro_arena_realloc(ma, ptr, nmemb * size);
MICRO_ARENA_DEF MicroArenaChunk*
micro_arena_chunk_list_add(MicroArenaChunkList *chunk_list,
                           void* start, size_t size)
  if (!chunk_list || chunk_list->len + 1 >= MICRO_ARENA_MAX_NUM_CHUNKS)
    return NULL;
  chunk_list->chunks[chunk_list->len] = (MicroArenaChunk){
    .start = start,
    .size = size,
  chunk_list->len++;
  return &chunk_list->chunks[chunk_list->len - 1];
MICRO_ARENA_DEF void
micro_arena_chunk_list_remove(MicroArenaChunkList *chunk_list,
                              void* start)
  if (!chunk_list)
    return;
  size_t i = 0;
  while (i < chunk_list->len)
    if (chunk_list->chunks[i].start == start)
      break;
  if (i >= chunk_list->len)
    return;
  for (i = i+1; i < chunk_list->len; ++i)
    chunk_list->chunks[i-1] = chunk_list->chunks[i];
  chunk_list->len--;
MICRO_ARENA_DEF MicroArenaChunk*
micro_arena_chunk_list_get(MicroArenaChunkList *chunk_list,
                           void* start)
  if (!chunk_list)
    return NULL;
  for (size_t i = 0; i < chunk_list->len; ++i)
    if (chunk_list->chunks[i].start == start)
      return &chunk_list->chunks[i];
  return NULL;
MICRO_ARENA_DEF void
micro_arena_chunk_list_reset(MicroArenaChunkList *chunk_list)
  if (!chunk_list)
    return;
  chunk_list->len = 0;
#ifdef MICRO_ARENA_GLOBAL
MicroArena _ma_global_arena;
#ifdef MICRO_ARENA_DEBUG
MICRO_ARENA_DEF void
micro_arena_debug_print(MicroArena *ma)
  printf("// MicroArena debug -----------------------------------------//\n");
    printf("MicroArena is NULL\n");
    return;
  printf("Free ");
  micro_arena_debug_print_chunk_list(&ma->free_chunks);
  printf("Used ");
  micro_arena_debug_print_chunk_list(&ma->used_chunks);
  printf("// ----------------------------------------------------------//\n");
MICRO_ARENA_DEF void
micro_arena_debug_print_chunk_list(MicroArenaChunkList* chunk_list)
  if (!chunk_list)
    printf("ChunkList is NULL\n");
    return;
  printf("Chunk list len: %ld\n", chunk_list->len);
  for (size_t i = 0; i < chunk_list->len; ++i)
    printf("- start = %p, size = %ld\n",
           (void*)chunk_list->chunks[i].start,
           chunk_list->chunks[i].size);
#define micro_arena_debug_print(...)
#define micro_arena_debug_print_chunk_list(...)
#endif // MICRO_ARENA_DEBUG
MICRO_ARENA_DEF int micro_arena_major(void)
  return MICRO_ARENA_MAJOR;
MICRO_ARENA_DEF int micro_arena_minor(void)
  return MICRO_ARENA_MINOR;
MICRO_ARENA_DEF int micro_arena_version(void)
  return MICRO_ARENA_VERSION;
#endif // MICRO_ARENA_IMPLEMENTATION
// Examples
#ifdef MICRO_ARENA_EXAMPLE_MAIN
// #define MICRO_ARENA_IMPLEMENTATION
// #include "micro-arena.h"
#include <assert.h>
#include <stdio.h>
int main(void)
  char buff[100];
  MicroArena ma;
  micro_arena_init(&ma, &buff[100], 100);
  int array_len = 10;
  int* mem = micro_arena_malloc(&ma, sizeof(int) * array_len);
  assert(mem != NULL);  
  micro_arena_free(&ma, mem);
  return 0;
#endif // MICRO_ARENA_EXAMPLE_MAIN
#ifdef __cplusplus
#endif // MICRO_ARENA
Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

micro-arena.h

Latest commit

History

micro-arena.h

File metadata and controls
