memory_allocator.c

1#include <stddef.h>2#include <stdio.h>3#include <stdlib.h>4#include <sys/mman.h>5 6#define ARENA_SIZE (1024 * 1024)7 8typedef struct {9  char *start;10  char *end;11  char *cursor;12} Arena;13 14typedef struct {15  size_t size;16  int is_free;17} Header;18 19static inline size_t block_span(size_t size) { return sizeof(Header) + size; }20 21Arena g_arena;22 23void arena_coalescing(Header *header) {24  char *next_addr = (char *)header + block_span(header->size);25  if (next_addr >= g_arena.cursor)26    return;27  Header *next_header = (Header *)next_addr;28  if (next_header->is_free) {29    header->size += block_span(next_header->size);30  }31}32 33// process_header split header if needed, then set is_free flag properly34void process_header(Header *header, size_t size, char *head_addr) {35  if (header->size > block_span(size)) {36    char *new_addr = head_addr + block_span(size);37    Header h = {header->size - size - sizeof(Header), 1};38    *(Header *)new_addr = h;39    header->size = size;40  }41  header->is_free = 0;42}43 44// find_free_block - iterate over headers, check for the one that can fit45// requested size46void *find_free_block(size_t size) {47  char *current = g_arena.start;48  while (current < g_arena.cursor) {49    Header *header = (Header *)current;50    if (header->is_free) {51      if (header->size >= size) {52        process_header(header, size, current);53        return current + sizeof(*header);54      } else {55      }56    }57    current += block_span(header->size);58  }59  return NULL;60}61 62void *arena_alloc(size_t size) {63  void *alloc = find_free_block(size);64  if (alloc != NULL) {65    return alloc;66  }67 68  if (g_arena.end - g_arena.cursor >= block_span(size)) {69    Header h = {size, 0};70    Header *h_addr = (Header *)g_arena.cursor;71    *h_addr = h;72    g_arena.cursor += sizeof(h);73    char *user_mem = g_arena.cursor;74    g_arena.cursor += size;75    return user_mem;76  }77  return NULL;78}79 80void arena_free(char *h_ptr) {81  Header *header = (Header *)(h_ptr - sizeof(Header));82  header->is_free = 1;83  arena_coalescing(header);84}85void check_arena_block() {86  char *current = g_arena.start;87  int block_num = 0;88  while (current < g_arena.cursor) {89    Header *header = (Header *)current;90    printf("Block %d: %zu bytes, %s\n", block_num, header->size,91           header->is_free ? "FREE" : "USED");92    current += block_span(header->size);93    block_num++;94  }95}96 97int main() {98  void *mem = mmap(NULL, ARENA_SIZE, PROT_READ | PROT_WRITE,99                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);100 101  if (mem == MAP_FAILED) {102    return -1;103  }104 105  g_arena.start = mem;106  g_arena.cursor = mem;107  g_arena.end = mem + ARENA_SIZE;108 109  char *a = arena_alloc(512);110  char *b = arena_alloc(512);111  char *c = arena_alloc(1024);112 113  printf("a: %p\n", a);114  printf("b: %p\n", b);115 116  unsigned long diff = b - a;117  printf("\nAddr difference: 0x%lx (%ld bytes)\n", diff, diff);118  printf("Expected: sizeof(Header) + user_size = %zu + 512 = %zu\n",119         sizeof(Header), block_span(512));120 121  arena_free(b);122  arena_free(a);123 124  printf("\nArena state after freeing:\n");125  check_arena_block();126 127  munmap(mem, ARENA_SIZE);128 129  return 0;130}