Memory Allocator

int heap_init(void* base) {
  if (!base) { return -1; }
  heap_base = base;
  *(heap_seg*)heap_base = (heap_seg){HEAP_INC, NULL};
  return 0;
}

From there we need to set our heap up so that users can begin to use it. In a real heap implementation this would be included in the first call to malloc, but with our static version this won’t be possible. Our only real setup here is to initialize our first heap segment, which will occupy the entire space by itself. We want to keep heap segments as large as possible so that we have a higher likelihood of being able to fit a requested allocation.

Once our heap is ready to go we can begin handing out pointers to different segments. Sounds easy right?

We will leave error handling out for right now to focus in on the core logic.

void *heap_malloc(size_t bytes) {
  heap_seg *prev = NULL;
  heap_seg *ptr = heap_base;
  while (ptr < (heap_seg*)(heap_base + HEAP_SIZE)) {
    if ((ptr->size & 0x1) == 0 && ptr->size >= bytes + sizeof(heap_seg)) {
      // Store old capacity
      size_t old_cap = ptr->size;
      // Heap segment is free, and big enough
      ptr->size = sizeof(heap_seg) +
                      ((bytes + (sizeof(heap_seg) - 1)) / sizeof(heap_seg)) *
                          sizeof(heap_seg) |
                  0x1;
      void *user_block = (void *)(ptr + 1);
      if (old_cap > ptr->size) {
        heap_seg *next_block = ptr + ptr->size / sizeof(heap_seg);
        next_block->size = old_cap - (ptr->size ^ 0x1);
      }
      return user_block;
    }
    prev = ptr;
    ptr = (void*)ptr / (ptr->size & (~1));
  }

  return NULL;
}

Yeah, it’s a bit more going on that I would have assumed at first, but it won’t be too hard to step through. Also note that we are currently covering what is called first fit right now, where we find the first chunk able to fulfil the allocation request, we will cover a different allocation strategy later.

We first start at the base of our heap, and begin checking at each spot if it is both free, and large enough to handle the requested allocation. Once a chunk if found we note its original capacity, and change it’s size to hold the requested amount of bytes. This is also where we set its previous element. You may notice that we don’t set the size to be equal to bytes as the user requested, instead we have to factor in a few more things.

The first portion of the size is the heap_seg struct itself, which in the current implementation is 16 bytes. The next section is the data, which needs to be aligned on 8 byte boundaries. We do this for efficient memory access, as a word on modern 64-bit systems is 8 bytes. To accomplish this we round up the requested size to the nearest multiple of 8, so 16 bytes stays at 16, and 17 bytes rounds up to 24.

Once we put this all together we set the least significant bit to 1. This final bit allows us to keep track of if the heap segment is in use. We are able to do this because each size will be a multiple of 8, meaning that its lower 3 bits will always be 0. We are currently using 1 of the 3 bits, so we can potentially even store more flags if needed.

There we go, we have now produced a heap segment that can be returned to the user. We note the position where they are allowed to begin writing, which we will return at the end of our function. The last step is to see if we need to segment the heap. If the section we allocated is less than the old capacity we get a pointer to the start of the next heap segment, and then set its size to the remaining space in the heap.

That’s how we hand out segments of our heap to users! If we don’t find a suitable segment we advance to the next segment and start over again.

int main() {
  uint8_t heap[HEAP_SIZE];
  heap_init(heap);

  int *block = heap_malloc(4);
  assert(block != NULL);
  *block = 4;

  int *num = heap_malloc(4);
  assert(num != NULL);
  *num = 7;

  printf("Num holds: %d\n", *num);
  printf("Block holds: %d\n", *block);
}

Num holds: 7
Block holds: 4

It was fairly easy to hand out memory, so how does the user give that memory back?

In our most basic implementation “freeing” memory will be nothing more than setting its least significant bit back to 0.

void heap_free(void* block) {
  if (!block) { return; }
  heap_seg *header = (heap_seg*)block - 1;
  header->size ^= 1;
}

But we may run into a bit of a problem here. What happens if a user allocated a many 8 byte segments at the start of their program, and then frees them all back once their program gets under way. Then they need to allocate larger segments of memory. With our current free function we would have to skip over all of these tiny segments till we found one large chunk to hand back to the user. What if all of those small segments added together would have been enough to handle their allocation.

This is where we have to rejoin our heap segments to ensure that we do not “fragment” the heap. Surprisingly this is also fairly easy to accomplish once you can visualize the possible states our heap may be in.

When a user requests to free a block there are only 3 possible states that it may be in.

1. The segment above or below is free, in which case we need to combine our segment with the adjacent free segment.
2. Both segments above and below are free, in which case we need to combine all 3 into a larger block.
3. The segments above and below are still in use, in which case we simply set the LSB to 0.

If we follow this behavior on every free call we ensure that every block in our heap will fall into 1 of these 3 states. The implementation here is just to check the block above and below the current block, then apply any needed transformations.

void heap_free(void* block) {
  if (!block) { return; }
  heap_seg *header = (heap_seg*)block - 1;
  // Get prev/next pointers
  heap_seg *prev = header->prev;
  heap_seg *next = (void*)header + (header->size & (~1));
  if (prev > (heap_seg*)heap_base && !(prev->size & 1)) {
    prev->size += header->size;
    header = prev;
  }
  if (next < heap_base + HEAP_SIZE && !(next->size & 1)) {
    header->size += next->size;
  }

  header->size ^= 1;
}

Expanding on the previous function we obtain pointers to the blocks directly before and after the current block. Then we can check each block, and see if it needs to be merged. If the previous block is free we update it’s size to include the current block, and update our header pointer to this previous block. Then the next block is checked, and we update our size accordingly. The last step is to zero out the “in use” bit of our header.

Note that we do not need to explicitly do anything with the freed memory. By updating the size of the surrounding nodes, we ensure that it will be skipped over when searching for the closest free block. Also, by updating our header pointer we ensure that the following logic will work for any of the 3 possible states of our segment.

With our allocation and freeing functions complete, that is pretty much it for the most basic of heap allocators.

int main() {
  uint8_t heap[HEAP_SIZE];
  heap_init(heap);

  int *block = heap_malloc(4);
  *block = 4;

  int *num = heap_malloc(4);
  *num = 7;

  int *test = heap_malloc(4);
  *test = 66;

  printf("Address of block: %p\n", block);
  printf("Address of num: %p\n", num);
  printf("Address of test: %p\n", test);

  printf("Size of block: %d\n", ((heap_seg*)block-1)->size ^ 0x1);
  printf("Size of num: %d\n", ((heap_seg*)num-1)->size ^ 0x1);
  printf("Size of test: %d\n", ((heap_seg*)test-1)->size ^ 0x1);

  heap_free(num);
  heap_free(test);

  num = heap_malloc(32);
  *num = 1;

  printf("Address of block: %p\n", block);
  printf("Address of num: %p\n", num);
  printf("Size of block: %d\n", ((heap_seg*)block-1)->size ^ 0x1);
  printf("Size of num: %d\n", ((heap_seg*)num-1)->size ^ 0x1);
}

Address of block: 0x7ffcef5b94a8  <-- Heap Base
Address of num: 0x7ffcef5b94b8    <-- Heap Base + 16
Address of test: 0x7ffcef5b94c8   <-- Heap Base + 32

Size of block: 16
Size of num: 16
Size of test: 16

Address of block: 0x7ffcef5b94a8  <-- Heap Base
Address of num: 0x7ffcef5b94b8    <-- Heap Base + 16 (same address as above)

Size of block: 16
Size of num: 40   <-- 32 byte allocation + 8 byte header

Implementing a naive memory allocator is fairly easy. It won’t be the fastest one in the world, nor the most secure. Either way, this small exploration shows us the basics of how we can hand out chunks of memory to a user, and allow them to be freed back to us.

The first fit algorithm that we chose to implement above is one of the quicker ways to allocate memory (we can also add a global variable that points to the first free block, to further increase speed). While speed is an important factor when it comes to allocating memory, sometimes the user might wish to be more space efficient as opposed to time efficient.

Instead of finding the first available spot we can find the best fit segment which is the smallest segment large enough to handle the requested allocation. One of the major advantages of this algorithm is that it avoids splitting large heap segments, which we should try to preserve for large allocations.

The biggest problem with splitting large heap segments is that we fragment our heap. Our next large allocation may not be able to find a contiguous segment to hold it, thus requiring our allocator to go out to the operating system and request more memory. For this reason, our next iteration will explore this algorithm.

We will see these functions used in the next section, but I will introduce them now so that you can become familiar with their behavior.

size_t round_bytes(size_t bytes) {
  return (bytes + (sizeof(void *) - 1)) / sizeof(void *) * sizeof(void *);
}

bool segment_free(heap_seg *seg) { return !(seg->size & 0x1); }

size_t segment_size(heap_seg *seg) { return seg->size & (~1); }

Our first new function will perform the byte rounding aligning us to the nearest block of 8 bytes. The next function checks if a block is free, and finally we have a function to get the true size of a block.

Our current implementation also relies on a statically allocated buffer, meaning once we fill this up we won’t be able to hand out more memory. Let’s see how we can make this behavior more dynamic by requested more memory from the operating system.

Now that we will be using sbrk directly in our program we are going to start running into a problem. The malloc implementation on our machine will be calling sbrk or mmap to increase its heap, and we will be trying to do the same. The issue is that our heaps are intertwined. If my malloc and the system’s malloc are both being run they will step on each other’s toes.

We can get around this by “overriding” malloc for our program.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
void *malloc(size_t size) {
  exit(72);
}

int main() {
  void *memory = malloc(400);
}

jackson@jtop:/tmp$ gcc test.c && ./a.out
jackson@jtop:/tmp$ echo $?
72

Our custom malloc implementation simply exits the program with a code of 72. Of course, this isn’t very useful, but it demonstrates that we can override the malloc functionality. The first portion of our malloc function will remain the same, initializing our heap, and handing out the first segment. For our static memory allocator we had to call an initialization function in main, but we will have to encode that behavior directly in malloc now.

first-fit

Just like our algorithm works, we find the first available block, and place our memory allocation there. The issue with this strategy is that we end up chunking our large blocks into smaller blocks. This leaves less large blocks, which will cause us to expand the heap next time we need to handle a large allocation request.

We should instead try to preserve as many large blocks as we can. This algorithm will run slower, because it causes us to scan the entire heap for every allocation. Of course there is always a tradeoff when it comes to programming, here we will see how trading a small amount of time for a more efficient use of space will be worth it.

best-fit

For this algorithm to work we will have to change the way we find a segment. The linear walking of our heap can stay the same, but we will have to maintain a pointer to the smallest block large enough to hold the allocation. If we get the end and have a block, we use it to hold our allocation, otherwise we continue on like we had done before.

Our first-fit algorithm has a higher likelihood of segmenting the heap, and we would like to avoid this as much as possible.

Segment size:   33, Prev:          (nil), Value:                   9, Address: 0x5600eb883000
Segment size:  232, Prev: 0x5600eb883000, Value:                  -1, Address: 0x5600eb883020
Segment size:  265, Prev: 0x5600eb883000, Value:                   7, Address: 0x5600eb883108
Segment size:  241, Prev: 0x5600eb883108, Value:                   2, Address: 0x5600eb883210
Segment size:   24, Prev: 0x5600eb883210, Value:                  -1, Address: 0x5600eb883300
Segment size:  265, Prev: 0x5600eb883300, Value:                  64, Address: 0x5600eb883318

If we now request a 8 byte allocation, can you see where it will be placed?

Segment size:   33, Prev:          (nil), Value:                   9, Address: 0x55a298d57000
Segment size:   25, Prev: 0x55a298d57000, Value:                  24, Address: 0x55a298d57020
Segment size:  208, Prev: 0x55a298d57020, Value:                  -1, Address: 0x55a298d57038
Segment size:  265, Prev: 0x55a298d57000, Value:                   7, Address: 0x55a298d57108
Segment size:  241, Prev: 0x55a298d57108, Value:                   2, Address: 0x55a298d57210
Segment size:   24, Prev: 0x55a298d57210, Value:                  -1, Address: 0x55a298d57300
Segment size:  265, Prev: 0x55a298d57300, Value:                  64, Address: 0x55a298d57318

Just like we said before, instead of finding the free 24 byte block (8 byte allocation, 16 byte header), we end up splitting the larger 232 byte block. How can we fix this in our malloc() function?

  // Start from heap base, find first open segment that can hold 'bytes'
  heap_seg *prev = NULL;
  heap_seg *ptr = heap_base;

  heap_seg *best_prev = NULL;
  heap_seg *best = NULL;
  while (ptr < (heap_seg *)heap_end) {
    if (segment_free(ptr) && ptr->size >= bytes + sizeof(heap_seg) &&
        (!best || segment_size(ptr) < segment_size(best))) {
      best = ptr;
      best_prev = prev;
    }
    prev = ptr;
    ptr = (void *)ptr + segment_size(ptr);
  }

  // Found a suitable block for Best-Fit
  if (best) {
    ptr = best;
    // Store old capacity
    size_t old_cap = ptr->size;
    // Heap segment is free, and big enough
    ptr->size = sizeof(heap_seg) + round_bytes(bytes) | 0x1;
    ptr->prev = prev;
    void *user_block = ptr + 1;
    size_t next_size = old_cap - segment_size(ptr);
    if (next_size <= sizeof(heap_seg)) {
      ptr->size += next_size;
    } else if (old_cap > ptr->size) {
      heap_seg *next_block = (void *)ptr + segment_size(ptr);
      next_block->size = old_cap - segment_size(ptr);
      next_block->prev = ptr;
    }
    return user_block;
  }

This boils down to a slight refactor, with 2 new pointers, and an added condition to our searching algorithm. Instead of stopping at the first free block we check to see if it is big enough, and more importantly, the best-fit we have seen. After scanning through the heap we use the best block if we have one, otherwise we continue on like before.

Comparing to the series of allocations demonstrated above, this new algorithm produces a less segmented heap.

Segment size:   33, Prev:          (nil), Value:                   9, Address: 0x5647b2660000
Segment size:  232, Prev: 0x5647b2660000, Value:                  -1, Address: 0x5647b2660020
Segment size:  265, Prev: 0x5647b2660020, Value:                   7, Address: 0x5647b2660108
Segment size:  241, Prev: 0x5647b2660108, Value:                   2, Address: 0x5647b2660210
Segment size:   25, Prev: 0x5647b2660210, Value:                  24, Address: 0x5647b2660300
Segment size:  265, Prev: 0x5647b2660300, Value:                  64, Address: 0x5647b2660318

Now we can see that our allocation occupies the 24 byte block near the end of the heap, leaving the entire 232 byte block for future allocation that may need more space.

That was a pretty easy change to handle, but you may notice another inefficiency. Every time an allocation is requested we have to start at the beginning of the heap. In these small examples that isn’t an issue, but imagine a heap the is full for the first 1-2 MB, with the first free block sitting at the end. We would spend precious time scanning over blocks that we cannot use. How can we fix this?

The way our heap is linked together is what is known as an implicit free list, meaning that each node is directly linked together, and we use a check at each step in our list to determine if the segment is free. This works well for a simple implementation, but we are slowed down by traversing a linked list, and calling a function at each step. What if instead we only looked at the free segments.

This is known as an explicit free list, where the free nodes are in their own linked list. This can be implemented with either a regular linked list, or even a circularly linked list. For our best-fit strategy, a regular singly linked list makes the most sense.

We have covered first-fit and best-fit, but there is an additional allocation algorithm called next-fit. Where the searching begins from the last block that was allocated. For this algorithm we might end up starting in the middle of the list, so a circularly linked list would be required.

Each node will now have to hold an additional pointer, adding 8 bytes of overhead. Managing these pointers will be very complicated, and can be very error-prone if we are not careful.

If you remember from my previous article on hashmaps, I like using calloc during both the exploration and optimization phase of coding. Of course in performance critical applications every CPU cycle counts, but for most purposes a few extra cycles to clear out memory is more than worth it.

Surprisingly to me, implementing calloc is as simple as a call to malloc, memset to 0, and then returning a pointer. The more interesting thing to me about calloc are the parameters it takes. The glibc calloc takes in the number of elements, and he size of each element, both being a size_t. This makes calloc easier to read in source code, and makes your intentions for the size of the allocation clearer.

void *calloc(size_t count, size_t size) {
  void *ptr = malloc(count * size);
  if (!ptr) {
    return NULL;
  }
  memset(ptr, 0, count * size);
  return ptr;
}

Just remember to include <string.h> for the memset function, and you should be good to go.

I don’t get to use realloc all that often, but when you find a good use case it always comes out super clean. It shouldn’t be too hard to implement, just take a look at the behavior described in man realloc and you will be good to go.

void *realloc(void *ptr, size_t size) {
  size_t min = (size < segment_size((heap_seg *)(ptr - 1)))
                   ? size
                   : segment_size((heap_seg *)(ptr - 1)) - sizeof(heap_seg);
  free(ptr);
  if (size == 0) {
    return NULL;
  }
  heap_seg *new_ptr = malloc(size);
  if (!new_ptr) {
    return NULL;
  }
  memmove(new_ptr, ptr, min);
  return new_ptr;
}

The first step is to calculate how many bytes will need to be moved. We take the smallest of the 2 values, and store that for later. We can then free the original pointer, and stop here if the user requested a reallocation size of 0 (the same as a free call). A new block is allocated to hold the requested size, and we copy over the original data, finally returning the pointer to the user.

For this case I am going to use the previously implemented hashmap for testing.

The hashmap starts out with a default size of 11, and target load factor of 0.5. I made sure to insert enough elements to ensure that it would resize at least once.

To test the performance of our hashmap we will perform a linear set of increase size allocations. Without freeing any of the memory allocated is essentially the worst case for our implementation. The biggest weak point of our malloc function is that when it runs out of memory it has to walk the entire heap before it can expand it. This set of allocations will test to see how slow this is.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>         // Swap these 2
/* #include "gallocc.h" */  // Swap these 2

int main() {
  struct timespec start, end;
  clock_gettime(CLOCK_MONOTONIC, &start);
  void *ptr;
  for (int i = 0; i < 64000; i++) {
    ptr = malloc(i);
  }
  clock_gettime(CLOCK_MONOTONIC, &end);

  double elapsed_time = (end.tv_sec - start.tv_sec) * 1000.0 +
    (end.tv_nsec - start.tv_nsec) / 1e6;
  printf("Time: %.3f milliseconds\n", elapsed_time);
}

Our implementation is much slower, partially explained by performing more system calls, and the walking of the list each time we run out of space. If we were to fix any bottleneck, that would be the first place to look. Another way that could be mitigated would be increased the size by which the heap increases each time.

For this speed test I used strace to see how much the glibc malloc was increasing the program break by, which turned out to be 135168 bytes. If we run our version with the original 1024 byte increment it will be much slower, so I decided to match the glibc version. Of course, this is just a trade-off of how much memory you are willing to have in-use at one time.

My goal was not to create the fastest memory allocator possible, but to use this is an opportunity to learn how they work.

I have used gdb from a surface level before, but never to work on complex programs like this. Most of my usage would follow the same pattern, segmentation fault, compile with -g, run in gdb and get a back trace. From there it was usually easy to understand what happened. That was entirely different while writing my memory allocator.

Before overwriting the glibc malloc it was easy to debug using print statements like I was used to. However, this came at the downside of not finding as many bugs with my code. You can only think of so many edge cases before you start running out of ideas. Once we overrode the malloc the bugs were instantly exposed, but this came at the downside of no longer being able to use print debugging or asserts.

Internally the printing functions and assert allocate buffers to do their scratch work, which of course wouldn’t work if our malloc was failing. Time to break out gdb then. A small portion of the bugs could be solved by simply printing a back trace, while most others required stepping through the program. The TUI included with gdb made viewing source code and printing the value of different variable a lot easier.

Overall, I think this is a great style of project for learning gdb, with many complex operations, and the inability to use print debugging.

We are often told to avoid global state when writing our programs, and I would generally agree when talking about application style programs. However, when it comes to low level or systems programming it is unavoidable in most situations.

In order for malloc to have as easy of a user interface as it currently does, it has to store some global state. Users expect to be able to call malloc and free anywhere in their code without having to first instantiate some sort of memory allocator object. You already know this, but malloc is the exact opposite of a pure function, it is entirely dependent on the state of the operating system below it, and the other processes running on the system.

Once memory has been allocated there is no easy way to get the start of the program’s heap, so we have to store that in a variable that will be accessible to malloc and its related function. Similarly, there is no system call to get the first free segment in our heap, because that is a concept we created ourselves, not an operating system primitive. So we also store this in a global variable, which allowed us to implement our explicit free list, greatly speeding up calls to malloc.

The last global variable is not entirely necessary, but it helps us avoid making a system call each time we need to reference the end of our heap. Of course, we can always call sbrk(0) to get the end of the heap, but system calls are not free, so we try to avoid making them.

I am personally not the biggest fan of linked lists, but they have their place in a library like this. Arrays are great, but they’re entirely inflexible, both in total size, and size per element. In this case we need our implementation to be adaptable for changes in both, so a linked list is required.

In fact our writing our memory allocator is really just writing a linked list on top of a giant slab of memory. Most of the challenges we solved are the same challenges you encounter working on a linked list, complicated by the fact we want to try to increase the heap by a fixed size, as opposed to calling sbrk for each allocation request.

We can even solve the biggest bottleneck in our implementation by using a concept from most doubly linked lists. In addition to tracking the end of the heap we could also track the last allocated segment. Then when first_free is set to NULL the algorithm would not need to traverse the heap just to get a pointer to this last element. Each time we performed an operation on a segment we would just need to check if its address plus its size gets us past the end of the list.

In addition to using a LSP like clangd to get function definitions and doc comments, man pages are great for learning how to use the functions available in C. sbrk is not the easiest function to understand, but once you read up on how it works you can start by using it in a test program. Most of the printing functions have similar names, so looking up their differences can help you choose the right one.

If you’re unfamiliar with any system call you can look up its man page, which often includes example usage to help get you started.

This is my first time using asserts throughout a program as mini test cases that need to pass to ensure the implementation is correct. Every time you discover a bug in your code add an assert to ensure that it doesn’t happen again.

The most obvious one I can think of in our memory allocator is ensuring that the address of the last segment plus its size should equal the heap_end pointer. Throughout the coding of this memory allocator I ran into a nasty bug where the last segment was being left off of the heap. It turned out that when calling sbrk I forgot to note the size of the previous element if it was free. This size needed to be added onto the end of our list. The assert now ensures that if this happens the program will exit.

Another helpful thing with asserts is that they can easily be disabled with one like of code.

#define NDEBUG
#include <assert.h>

The NDEBUG line makes all assert lines a nop.