[c] malloc and free implementation on the static memory pool

CMakeLists.txt

# How to build and to run
#   mkdir build ; cd build/ ; cmake .. ; make ; ./test
#   (cleanup: rm -r build/)
set(CMAKE_C_STANDARD 11)
list(APPEND CMAKE_C_FLAGS "-Wall -Wextra -pedantic")
add_library(mymalloc SHARED mymalloc.c)
add_executable(test test.c)
link_directories(.)
target_link_libraries(test mymalloc)

mymalloc.c

// malloc and free implementaion on the static memory pool
// see https://en.wikipedia.org/wiki/C_dynamic_memory_allocation
#include "mymalloc.h"

union chunk;
struct info {
  union chunk* prev;
  union chunk* next;
  size_t size;
};
struct node {
  struct info info;
  size_t used;
};
union chunk {
  unsigned char data[sizeof (struct node)];
  struct node node;
};

// static memory
enum {CHUNK_MAX = 1024};
static size_t initialized = 0;
static const size_t chunk_max = CHUNK_MAX;
static union chunk pool[CHUNK_MAX];
static union chunk head = {.node = {{NULL, NULL, 0}, 0}};
static union chunk tail = {.node = {{NULL, NULL, 0}, 0}};

static void init() {
  head.node.info.next = pool;
  union chunk* prev = &head;
  union chunk* curr = pool;
  for (size_t i = 0; i < chunk_max; i++) {
    curr->node.info.prev = prev;
    curr->node.info.next = curr + 1;
    curr->node.info.size = 0;
    curr->node.used = 0;
    prev = curr++;
  }
  prev->node.info.next = &tail;
  tail.node.info.prev = prev;
  initialized = 1;
}

static size_t chunk_count(size_t size) {
  size_t chunks = 0;
  size_t chunks_size = 0;
  while (chunks_size < size + sizeof (struct info)) {
    chunks_size += sizeof (union chunk);
    chunks++;
  }
  return chunks;
}

static void* unlink(union chunk* top, size_t count) {
  union chunk* prev = top->node.info.prev;
  union chunk* next = top[count - 1].node.info.next;
  prev->node.info.next = next;
  next->node.info.prev = prev;
  top->node.info.size = count;
  return top->data + sizeof (struct info);
}

static void relink(union chunk* top) {
  if (top < pool || pool + chunk_max - 1 < top) return;
  union chunk* prev = &head;
  while (prev->node.info.next != &tail && prev->node.info.next < top) {
    prev = prev->node.info.next;
  }
  if (prev == top) return; //dual free
  union chunk* next = prev->node.info.next;
  union chunk* curr = top;
  prev->node.info.next = curr;
  size_t count = top->node.info.size;
  for (size_t i = 0; i < count; i++) {
    curr->node.info.prev = prev;
    curr->node.info.next = curr + 1;
    curr->node.info.size = 0;
    curr->node.used = 0;
    prev = curr++;
  }
  prev->node.info.next = next;
  next->node.info.prev = prev;
}

extern void* mymalloc(size_t size) {
  if (!initialized) init();
  size_t chunks = chunk_count(size);
  size_t keep = 0;
  union chunk* top = head.node.info.next;
  for (union chunk* curr = top; curr != &tail; curr = curr->node.info.next) {
    keep++;
    if (keep == chunks) return unlink(top, chunks);
    if (curr->node.info.next == curr + 1) continue;
    keep = 0;
    top = curr->node.info.next;
  }
  return NULL;
}

extern void myfree(void* ptr) {
  if (ptr == NULL) return;
  char* bptr = ptr;
  ptr = bptr - sizeof (struct info);
  relink(ptr);
}

mymalloc.h

#ifndef __MYMALLOC_H_
#define __MYMALLOC_H_

#include <stddef.h>

extern void* mymalloc(size_t size);
extern void myfree(void* ptr);

#endif

test.c

// mymalloc example
// clang -Wall -Wextra -std=c11 mymalloc.c test.c -o mymalloc_test
#include <stdio.h>
#include "mymalloc.h"

int main() {
  size_t* buf1 = mymalloc(sizeof (size_t) * 4);
  for (int i = 0; i < 4; i++) buf1[i] = i + 1;
  size_t* buf2 = mymalloc(sizeof (size_t) * 4);
  for (int i = 0; i < 4; i++) buf2[i] = (i + 1) * 16;
  printf("buf1(%p): %zx, %zx, %zx, %zx\n",
         buf1, buf1[0], buf1[1], buf1[2], buf1[3]);
  printf("buf2(%p): %zx, %zx, %zx, %zx\n",
         buf2, buf2[0], buf2[1], buf2[2], buf2[3]);
  myfree(buf1);

  // area resued by same size of freed buf1
  size_t* buf3 = mymalloc(sizeof (size_t) * 4);
  printf("buf3(%p) == buf1\n", buf3); // same as buf1
  myfree(buf3);

  // buf1 area not reused because not enough size from buf1
  size_t* buf4 = mymalloc(sizeof (size_t) * 8);
  printf("buf4(%p) > buf2\n", buf4); // diffrent from buf1
  myfree(buf4);
  myfree(buf2);

  // 1 chunk x 3
  size_t* buf5 = mymalloc(sizeof (size_t));
  printf("buf5(%p) == buf1\n", buf5);
  size_t* buf6 = mymalloc(sizeof (size_t));
  printf("buf6(%p) == buf1 + 0x20\n", buf6);
  size_t* buf7 = mymalloc(sizeof (size_t));
  printf("buf7(%p) == buf1 + 0x40\n", buf7);
  myfree(buf5);
  myfree(buf6);
  myfree(buf7);
  
  return 0;
}

Design of the mymalloc:

• union chunk is a node of a special double lineked list(node.info.prev andnode.info.next) or mid of allocated memory.

• node.used is a start of the allocated memory (so mymalloc returns the addres of node.used), not allocation flag.

• node.info.size is a count of chunks as a continuing allocated chunk area (the count includes itself).

• pool is a array of chunks.

• NOTE: a free node is just a single independent node, not a bunch of chunks (info.size is always 0).

• union chunk is 4x pointer size(32bytes in 64bit target) block unit.

• init makes a double list to the whole pool as every chunk as unused node

• mymalloc searches a continuing chunk area to enough to allocate from the pool.

• unlink removes the chunks to the pool

• relink (called in myfree) adds as the released chunks as free double linked list nodes.

• avoid to use specific sized ints and their literals , instead of use size_t.

Hi,
Can I ask what is the motivation of declaring chunk as a union?