Nobody's hiring jr. dev so I made my own memory allocator in C
Dhadve Yash12 min read
In this blog, we will be learning how to make a malloc function and free function. Ofcourse it's not gonna be how a really malloc works in c but you will get an idea. our malloc will be able to allocate dynamic size of memory also it can deallocate that memory once freed and can be reused. But once a memory is used it gets fragmented and we should be able to merge fragmented memory and be able to reuse it, we will implement that as well.
// First we need some memory to work with
// Here we are making heap of type char as 1 char takes 1 bytes of space
// so we are creating heap of size 640k Bytes.
#define HEAP_CAPACITY 640000
char heap[HEAP_CAP] = {0};
Now we have memory to work with, so lets make malloc function that will allocate the memory for it in this above heap array.
#include "stdio.h"
#define HEAP_CAPACITY 640000
#define CHUNK_LIST_CAP 1024
// This defines every chunk we allocate
// it stores the starting point of our chunk and the total size of the chunk
typedef struct {
char *start;
size_t size;
} Chunk;
// chunk list stores the list of chunks
// we will be using it to store how many chunks we have allocated
// also how many chunks we have free
typedef struct {
size_t count;
Chunk chunks[CHUNK_LIST_CAP];
} Chunk_List;
char heap[HEAP_CAPACITY] = {0};
// We are initilizing it with 0 as we have not allocated any chunks yet
Chunk_List allocated_chunks = {0};
// In freed_chunks we are initializing it with the whole heap as all the memory is free
// so we have one chunk which is the whole heap
// in output it will look like this:
// Chunks (1): start: 0x7f8b3c000000, size: 640000
Chunk_List freed_chunks = {
.count = 1,
.chunks = {
[0] = {.start = heap, .size = sizeof(heap)},
},
};
void *heap_alloc(size_t size)
{
// size should be greater than 0 as we cannot allocate 0 bytes or less that would be dumb
if (size > 0){
// We are looping through the freed_chunks to find a chunk that is big enough to allocate
// eg. we want to allocate 10 bytes
// And in our freed_chunks we have
// (1): start: 0x7f8b3c000000, size: 639995
// (2): start: 0x7f8b3d000000, size: 5
// then we will take memory from first chunk and allocate 10 bytes
// and we will then have ->
// freed_chunks will look like this:
// (1): start: 0x7f8b3c000000, size: 639985 // we reduced 10 bytes from this
// (2): start: 0x7f8b3d000000, size: 5
// allocated_chunks will look like this:
// (1): start: 0x7f8b3c000000, size: 10
for (size_t i = 0; i < freed_chunks.count; ++i)
{
// we selet the chunk from freed_chunks
const Chunk chunk = freed_chunks.chunks[i];
// if we find the chunk that is big enough to allocate
// we will remove it from freed_chunks and insert it into allocated_chunks
if (chunk.size >= size)
{
// remove the chunk from freed_chunks
freed_chunks.chunks[i] = freed_chunks.chunks[freed_chunks.count - 1];
freed_chunks.count--;
// insert the chunk into alloced_chunks
allocated_chunks.chunks[allocated_chunks.count++] = (Chunk){chunk.start, size};
// if there is any tail left, insert it into freed_chunks
const size_t tail_size = chunk.size - size;
if (tail_size > 0)
{
freed_chunks.chunks[freed_chunks.count++] = (Chunk){(char *)chunk.start + size, tail_size};
}
return chunk.start;
}
}
}
return NULL;
}
cool now we have our allocator function ready. But we need some way to visualize it so lets make a function for that.
void chunk_list_dump(const Chunk_List *list){
printf("Chunks (%zu):\n", list->count); // print number of chunks we have
// loop over all chunks and print their start address and size
for (size_t i = 0; i < list->count; ++i){
printf("start: %p, size: %zu\n",
(void *) list->chunks[i].start,
list->chunks[i].size);
}
}
Now lets test it -
int main(void){
void *ptr1 = heap_alloc(10);
void *ptr2 = heap_alloc(50);
(void) ptr1;
(void) ptr2;
// we are doing this to tell compiler that
// we aren't gonna use that variable, so it won't throw warning
chunk_list_dump(&allocated_chunks);
printf("Free");
chunk_list_dump(&freed_chunks);
return 0;
}
output -
Chunks (2):
start: 0x102f6c008, size: 10
start: 0x102f6c012, size: 50
FreeChunks (1):
start: 0x102f6c044, size: 639940
Now lets work on free function -
void heap_free(void *ptr){
// we check if the pointer is not NULL because if it is NULL we cannot theres nothing to free
if (ptr != NULL){
// We need to find the index of the chunk in allocated_chunks
int index = -1;
for (size_t i = 0; i < allocated_chunks.count; ++i){
if (allocated_chunks.chunks[i].start == ptr) {
index = i;
break;
}
}
assert(index >= 0);
assert(ptr == allocated_chunks.chunks[index].start);
// Insert the chunk into freed_chunks
assert(freed_chunks.count < CHUNK_LIST_CAP);
freed_chunks.chunks[freed_chunks.count++] = allocated_chunks.chunks[index];
// Remove the chunk from allocated_chunks
for (size_t i = index; i < allocated_chunks.count - 1; ++i){
allocated_chunks.chunks[i] = allocated_chunks.chunks[i + 1];
}
allocated_chunks.count -= 1;
}
}
And there we have our free function -
int main(void){
void *ptr1 = heap_alloc(10);
void *ptr2 = heap_alloc(50);
heap_free(ptr1);
chunk_list_dump(&allocated_chunks);
printf("Free");
chunk_list_dump(&freed_chunks);
return 0;
}
output - as we can see it removed the a chunk from our memory and added it to our free memory
Chunks (1):
start: 0x1007f8012, size: 50
FreeChunks (2):
start: 0x1007f8044, size: 639940
start: 0x1007f8008, size: 10
But wait … there are lot of issues with this
When reallocating new memory it should pick up smallest memory eg
heap_alloc(5)should get memory fromfreed_chunksof size 10 but it doesn’twhen the memory is fragmented it should be able to merge itself for future use
Doing that is gonna be messy so we will break our code in smaller helper functions chunk_list_find chunk_list_insert chunk_list_merge chunk_list_remove
Lets break down these functions one by one.
// the returns the index of the chunk based on input pointer
int chunk_list_find(const Chunk_List *list, void *ptr)
{
for (size_t i = 0; i < list->count; ++i){
if (list->chunks[i].start == ptr) {
return (int) i;
}
}
return -1;
}
void chunk_list_insert(Chunk_List *list, void *ptr, size_t size)
{
// we check if our list if full or not
// if it is full we cannot insert any more chunks
// so we will error out
assert(list->count < CHUNK_LIST_CAP);
// we insert the chunk at the end of the list
// we are using the last index of the list to insert the chunk
list->chunks[list->count].start = ptr;
list->chunks[list->count].size = size;
// we are doing mini bubble sort here
// we are sorting the chunks based on their starting address
// we always assume that our list is sorted
// and now we have added new element at the end of the list
// that element might be smaller from the previous elements
// so we check from backwards and swap the elements until we find the right position
// e.g. if we have chunks like this:
// index: 0 1 2
// start: 0x100 0x200 0x400
// and now we add new element at index 3
// index: 0 1 2 3
// start: 0x100 0x200 0x400 0x250 (unsorted)
// ^- this is the new element and added at the end of the list
// and teh address is smaller than the previous elements
// so we need to swap it
// SWAP 1:
// index: 0 1 2 3
// start: 0x100 0x200 0x250 0x400 (unsorted)
// now that we have swapped and the element, our inserted chunk is greater than the previous element and thus list is in sorted order
for (size_t i = list->count; i > 0 && list->chunks[i].start < list->chunks[i - 1].start; --i)
{
Chunk t = list->chunks[i];
list->chunks[i] = list->chunks[i - 1];
list->chunks[i - 1] = t;
}
list->count += 1; // incrementing the count as we have added a new chunk
}
// Made a house becase i got bored
// __________
// ///////////\
// /////////// \
// | _ | |
// |[] | | []|[]|
// | | | | |
// --------------
// Now back to the business
// merge function merges the 'adjecent' fragemented memory chunks
void chunk_list_merge(Chunk_List *dst, Chunk_List *src){
// Given src:
// index: 0 1 2
// start: 0x1000 0x1100 0x2000
// size: 0x100 0x100 0x080
dst->count = 0;
for (size_t i = 0; i < src->count; ++i)
{
const Chunk chunk = src->chunks[i];
if (dst->count > 0)
{
Chunk *top_chunk = &dst->chunks[dst->count - 1];
// we will get last chunk form dst list
// and check if the start of the current chunk is adjacent to the last chunk
// if it is adjacent, we will merge the two chunks
// and add it to the last chunk
// by adding the start and size of top chunk,
// we check if our next chunk is adjacent
if (top_chunk->start + top_chunk->size == chunk.start)
{
top_chunk->size += chunk.size;
}
else
{
// but if it is not adjacent, we will just insert the chunk into dst
chunk_list_insert(dst, chunk.start, chunk.size);
}
}
else
{
// since dst count is goint to be 0 at start
// we will just insert the first chunk into dst
chunk_list_insert(dst, chunk.start, chunk.size);
}
}
}
void chunk_list_remove(Chunk_List *list, size_t index)
{
assert(index < list->count);
for (size_t i = index; i < list->count; ++i) {
list->chunks[i] = list->chunks[i+1];
}
list->count -= 1;
}
And there we have it. All of our helper functions ready and lets just quickly refactor our heap_alloc and heap_free -
void *heap_alloc(size_t size){
if (size > 0){
chunk_list_merge(&tmp_chunks, &freed_chunks);
freed_chunks = tmp_chunks;
for (size_t i = 0; i < freed_chunks.count; ++i){
const Chunk chunk = freed_chunks.chunks[i];
if (chunk.size >= size){
chunk_list_remove(&freed_chunks, i);
const size_t tail_size = chunk.size - size;
chunk_list_insert(&alloced_chunks, chunk.start, size);
if (tail_size > 0){
chunk_list_insert(&freed_chunks, (char *)chunk.start + size, tail_size);
}
return chunk.start;
}
}
}
return NULL;
}
void heap_free(void *ptr){
if (ptr != NULL){
const int index = chunk_list_find(&alloced_chunks, ptr);
assert(index >= 0);
assert(ptr == alloced_chunks.chunks[index].start);
chunk_list_insert(&freed_chunks,
alloced_chunks.chunks[index].start,
alloced_chunks.chunks[index].size);
chunk_list_remove(&alloced_chunks, (size_t)index);
}
}
And our project is complete…
lets test it out
int main(void){
heap_alloc(20);
for (int i = 0; i < 10; ++i){
void *ptr = heap_alloc(10);
heap_free(ptr);
}
heap_alloc(20);
chunk_list_dump(&alloced_chunks);
printf("Free");
chunk_list_dump(&freed_chunks);
return 0;
}
Output -
Chunks (2):
start: 0x9c3f6, size: 20
start: 0x100114008, size: 20
FreeChunks (1):
start: 0x9c400, size: 639960
Hope you were able to learn and make your own malloc.
complete code -
#include "stdio.h"
#include "assert.h"
#define HEAP_CAPACITY 640000
#define CHUNK_LIST_CAP 1024
// This defines every chunk we allocate
// it stores the starting point of our chunk and the total size of the chunk
typedef struct {
char *start;
size_t size;
} Chunk;
// chunk list stores the list of chunks
// we will be using it to store how many chunks we have allocated
// also how many chunks we have free
typedef struct {
size_t count;
Chunk chunks[CHUNK_LIST_CAP];
} Chunk_List;
char heap[HEAP_CAPACITY] = {0};
// We are initilizing it with 0 as we have not allocated any chunks yet
Chunk_List allocated_chunks = {0};
// In freed_chunks we are initializing it with the whole heap as all the memory is free
// so we have one chunk which is the whole heap
// in output it will look like this:
// Chunks (1): start: 0x7f8b3c000000, size: 640000
Chunk_List freed_chunks = {
.count = 1,
.chunks = {
[0] = {.start = heap, .size = sizeof(heap)},
},
};
// the returns the index of the chunk based on input pointer
int chunk_list_find(const Chunk_List *list, void *ptr)
{
for (size_t i = 0; i < list->count; ++i){
if (list->chunks[i].start == ptr) {
return (int) i;
}
}
return -1;
}
void chunk_list_insert(Chunk_List *list, void *ptr, size_t size)
{
// we check if our list if full or not
// if it is full we cannot insert any more chunks
// so we will error out
assert(list->count < CHUNK_LIST_CAP);
// we insert the chunk at the end of the list
// we are using the last index of the list to insert the chunk
list->chunks[list->count].start = ptr;
list->chunks[list->count].size = size;
// we are doing mini bubble sort here
// we are sorting the chunks based on their starting address
// we always assume that our list is sorted
// and now we have added new element at the end of the list
// that element might be smaller from the previous elements
// so we check from backwards and swap the elements until we find the right position
// e.g. if we have chunks like this:
// index: 0 1 2
// start: 0x100 0x200 0x400
// and now we add new element at index 3
// index: 0 1 2 3
// start: 0x100 0x200 0x400 0x250 (unsorted)
// ^- this is the new element and added at the end of the list
// and teh address is smaller than the previous elements
// so we need to swap it
// SWAP 1:
// index: 0 1 2 3
// start: 0x100 0x200 0x250 0x400 (unsorted)
// now that we have swapped and the element, our inserted chunk is greater than the previous element and thus list is in sorted order
for (size_t i = list->count; i > 0 && list->chunks[i].start < list->chunks[i - 1].start; --i)
{
Chunk t = list->chunks[i];
list->chunks[i] = list->chunks[i - 1];
list->chunks[i - 1] = t;
}
list->count += 1; // incrementing the count as we have added a new chunk
}
// merge function merges the 'adjecent' fragemented memory chunks
void chunk_list_merge(Chunk_List *dst, Chunk_List *src){
// Given src:
// index: 0 1 2
// start: 0x1000 0x1100 0x2000
// size: 0x100 0x100 0x080
dst->count = 0;
for (size_t i = 0; i < src->count; ++i)
{
const Chunk chunk = src->chunks[i];
if (dst->count > 0)
{
Chunk *top_chunk = &dst->chunks[dst->count - 1];
// we will get last chunk form dst list
// and check if the start of the current chunk is adjacent to the last chunk
// if it is adjacent, we will merge the two chunks
// and add it to the last chunk
// by adding the start and size of top chunk
if (top_chunk->start + top_chunk->size == chunk.start) // this part is kinda sketchy and should be checked
{
top_chunk->size += chunk.size;
}
else
{
// but if it is not adjacent, we will just insert the chunk into dst
chunk_list_insert(dst, chunk.start, chunk.size);
}
}
else
{
// since dst count is goint to be 0 at start
// we will just insert the first chunk into dst
chunk_list_insert(dst, chunk.start, chunk.size);
}
}
}
void chunk_list_remove(Chunk_List *list, size_t index)
{
assert(index < list->count);
for (size_t i = index; i < list->count-1; ++i) {
list->chunks[i] = list->chunks[i+1];
}
list->count -= 1;
}
void *heap_alloc(size_t size)
{
if (size > 0)
{
Chunk_List tmp_chunks = {0};
chunk_list_merge(&tmp_chunks, &freed_chunks);
freed_chunks = tmp_chunks;
for (size_t i = 0; i < freed_chunks.count; ++i)
{
const Chunk chunk = freed_chunks.chunks[i];
if (chunk.size >= size)
{
chunk_list_remove(&freed_chunks, i);
const size_t tail_size = chunk.size - size;
chunk_list_insert(&allocated_chunks, chunk.start, size);
if (tail_size > 0)
{
chunk_list_insert(&freed_chunks, (char *)chunk.start + size, tail_size);
}
return chunk.start;
}
}
}
return NULL;
}
// O(N)
void heap_free(void *ptr)
{
if (ptr != NULL){
const int index = chunk_list_find(&allocated_chunks, ptr);
assert(index >= 0);
assert(ptr == allocated_chunks.chunks[index].start);
chunk_list_insert(&freed_chunks,
allocated_chunks.chunks[index].start,
allocated_chunks.chunks[index].size);
chunk_list_remove(&allocated_chunks, (size_t)index);
}
}
void chunk_list_dump(const Chunk_List *list){
printf("Chunks (%zu):\n", list->count);
for (size_t i = 0; i < list->count; ++i){
printf("start: %p, size: %zu\n",
(void *) list->chunks[i].start,
list->chunks[i].size);
}
}
int main(void){
void *ptr1 = heap_alloc(10);
void *ptr2 = heap_alloc(50);
(void) ptr1;
(void) ptr2;
heap_free(ptr1);
heap_free(ptr2);
heap_alloc(10);
// void *ptr3 = heap_alloc(10);
// (void) ptr3;
chunk_list_dump(&allocated_chunks);
printf("Free");
chunk_list_dump(&freed_chunks);
return 0;
}
0
Subscribe to my newsletter
Read articles from Dhadve Yash directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by