### Introduction
This is going to be my first post and to start things off i'll write a simple dynamic memory allocator such as _malloc_. The idea of this writing was to make this concept as clear as possible to me, but after brainstorming it, i decided to post it since i think memory allocation is a really important topic and every programmer should know about it.
I'm going to assume that: you know what C pointers are and how to work with them, a basic idea of what malloc() does and that you're familiar with the concept of a linked list.
_==Disclaimer==: This document was inspired by Marwan Burelle's malloc() implementation + this article was not made to show off the ideal dynamic allocator but instead a simple version of it that works + i'm going to present better options and flaws of this malloc at the end of the document + i'm consolidating this as i'm writing it so bear with me._
### Where we're at
First of all, let's talk about where our program is located in memory and how does a typical process memory layout looks like:
[MISSING IMAGE]
We have a couple of separate "chunks" here:
- the kernel space is everything on the computer besides our running process
- the stack: grows downwards and it's used to "save" return addresses, padding (we will see what this is), function parameters and overall temporary storage.
- the most important for us today, the heap: it grows upwards and is much more difficult to handle than the stack. It's used to "save" data that needs to persist during the execution of the program, dynamically allocated objects (using our `malloc()`) and much more.
- bss: has unitialized data. If we declare `ìnt i;` as a global variable, it's stored here.
- data: has initialized data. If we declare `ìnt i = 0` as a global variable, it's stored here.
- text: stores the program code as read-only.
### The heap's layout
[MISSING IMAGE]
Here we have a visual representation of the heap and the most important component: the _break_. The break is the limit of the mapped region and trying to access memory above it should trigger a bus error (the region where virtual memory has been "linked" to physical memory by the MMU is the mapped region). This is important for our malloc because to make the heap "grow" (aka allocate more memory) the break needs to move. To access this break we can use unistd.h's functions sbrk()/brk().
> We're assuming that the heap is a big chunk of contiguous space but nothing guarantees this.
> In fact, there are a lot more limits in the heap but the closest we can get to this one is using `getrlimit(RLIMIT_DATA, struct rlimit *rlim)` from sys/resource.h.
### sbrk()
```c
void *sbrk(intptr_t increment);
```
**sbrk()** moves the break by the given increment (in bytes).
- On success, if the break was increased, sbrk() returns a pointer to the start of the newly allocated memory.
- On error, it returns (void*)-1.
Calling sbrk(0) can be used to find the current location of the _break_ (this is going to be important to find the start of the heap and error handling).
### Memory Pages and No-Man’s Land
[MISSING IMAGE]
You might be wondering what are those dotted lines dividing the memory. These "parts" are called pages, they organize physical and virtual memory, and each of them contain around 4096 bytes each, on most systems. Because of this, the break might not be on a page boundary as you can see in the preceding figure. So, the break is in the middle of a page, but can you access that memory between the break and the next page boundary? Yes! The problem is you ==can't be certain of the position of the next boundary== (technically you can find it but it's system dependent and not advised). This area is called _no-man's land_ and it's the root of a lot of bugs related to pointer manipulation.
> I'm removing the pages to make things visually clearer.
## Our first malloc()
```c
#include <unistd.h>
void *malloc(size_t size) {
void *break = sbrk(0);
if (sbrk(size) == (void*)-1) {
return NULL;
}
return break;
}
```
This is the simplest malloc implementation we can have but the mechanism is the same further on: we store the current break to return it in case something fails and we try to increase it by the amount of bytes the user wants.
### Organizing the heap
We know that we need to increase the _break_ to allocate more memory. If we do this multiple times the heap is going to start looking like it fell on the floor.
[MISSING IMAGE]
How do we organize this to make our lives easier?
#### How to structure the heap for our benefit
To make this easier to access and manage, we'll make a "sign" that precedes each block that contains its meta-data:
- The size of the block
- If the block is free
- Where the next block is
This way we don't need to parse the whole block to know it's size or whether it's size is totally occupied, everything will be noted each time the break moves and a new block is created.
[MISSING IMAGE]
## Actually (almost) implementing it
Let's declare the meta-data block structure because that's going to be used all around the code.
```c
#include <stdbool.h>
#include <unistd.h>
#define BMETADATA 24
struct b_meta {
size_t size;
int free;
struct b_meta *next;
};
```
A question you may have is: how are we going to allocate memory of each of these things without malloc? Let me explain.
A struct, in memory, is natively aligned with the help of something called padding. Padding is added to align the structure members so that memory access is optimized. For example, in a 64-bit architecture, accessing a 64-bit (8 byte) value is optimized when the memory address is aligned to an 8-byte boundary. With that information, we can assume that there's going to be padding between `ìnt` and the pointer.
```
0x00: size_t size; /* 8 bytes (aligned at 0) */
0x08: int free; /* 4 bytes (aligned at 8) */
0x0c: (padding) /* 4 bytes */
0x10: struct b_meta *next; /* 8 bytes (aligned at 16) */
```
So, when we call `b_meta->next` what we're really doing is getting the base address of the struct and adding the length, in bytes, of the previous fields + padding: `_((char_ )b_meta + 16).
`BMETADATA`is what's going to keep track of the total metadata block size.
> It's not the most memory-efficient way to declare `free` as an integer but it's just to demonstrate padding.
## Implementing it
We're going to implement the classic _first fit_ malloc: we traverse all the blocks and stop when we find a free one with enough space for the requested allocation.
### find_block()
Let's make the function that goes through the heap and finds a free block:
```c
struct b_meta *find_block(struct b_meta **last, size_t size) {
struct b_meta *b = base;
while (b && !(b->free && b->size >= size)) {
*last = b;
b = b->next;
}
return b;
}
```
This function traverses the heap from the start using the global variable `base` (which we will define later on) while the current block we're analyzing exists, is not free and doesn't have enough memory to store the requested size. The function stores the last visited block in `last`.
> We need a double pointer on the first argument because we need to access and modify that pointer globally, not only inside the find_block() function.
### extend_heap()
Now we can traverse through the heap, but what if there's no heap available to traverse? We need to extend it but there's another problem: what if we expand the heap but there's space between the break and the end of the previous block? We need to make a macro definition such as `BMETADATA` to align the size requested by the user.
##### Align requested size by the architecture boundaries
```c
#define align(x) (((((x)-1)>>3)<<3)+8)
```
In a 64-bit system, we need to align things by 8 bytes boundaries as we saw earlier.
This macro is the same as saying: if we choose any positive integer, divide it by 8, multiply it by 8 and adding 8 to the result is the nearest positive multiple of 8. But if we choose a multiple of 8 it allocates more 8 bytes then it should, so we subtract 1 before all the other operations.
> `>>3`is the same as dividing by four and `<<3`is the same as multiplying by four in bit shifting.
> The macro is not used directly here, but on the malloc() function when the user asks for more bytes.
This is how we expand the heap, in code:
```c
struct b_meta *extend_heap(struct b_meta *last, size_t size) {
struct b_meta *b;
b = sbrk(0); /* the break is at the end of the previous block */
if (sbrk(BMETADATA + size) == (void *)-1) {
return NULL;
}
b->size = size;
b->next = NULL;
if (last) {
last->next = b;
}
b->free = 0;
return b;
}
```
### split_block()
Now, let's think about what happens in this situation: the user asked for 200 bytes and he got a 500 byte block back. Those 300 bytes are going to be completely wasted.
[MISSING IMAGE]
We can fix that _splitting the blocks_. The idea is simple: we go through the chunks as usual but if we find a block that suits the user's needs, we check if it has space for a new block's metadata + the user requested bytes. If it does, we split it in two.
We're going to add a new variable `char data[1]` to our struct so that we can do accurate pointer arithmetic since this points to 1 byte (if we access block->data + 7 we get to the start of the block). `BMETADATA` was set to 24 bytes but since `data` needs 1 byte in memory, there's also 7 bytes of padding. The total `BMETADATA` is now 32, don't forget to change it.
Let's write that in code:
```c
void split_block(struct b_meta *block, size_t size) {
struct b_meta *new;
new = block->data + 7 + size;
new->size = block->size - size - BMETADATA; /* Figure x */
new->next = block->next; /* Figure x+1 */
block->next = new; /* Figure x+2 */
block->size = size;
new->free = 1;
block->free = 0;
}
```
> Keep in mind the distinction between block and the block's metadata, it can get confusing from now on. In the code, block is always referring to the metadata rather than the actual block.
I'm not going to explain the code in this part, the visual representation is much more understandable. Check the code's comments and follow the images below :)
[MISSING IMAGE]
### malloc()
We need a way to know if we already did something to the heap and for that we need to initialize a global variable called `base` (base of our heap) as `NULL`.
```c
void *base = NULL;
```
The malloc() implementation:
```c
void *malloc(size_t size) {
struct b_meta *b, *last;
size_t s = align(size);
if (base) {
last = base;
b = find_block(&last, size);
if (b) {
if ((b->size - s) >= (BMETADATA + 8)) {
split_block(b, size);
} else {
b = extend_heap(last, size);
if (!b) {
fprintf(stderr, "ERROR: Couldn't extend heap: %s\n", strerror(errno));
return NULL;
}
}
}
} else {
b = extend_heap(NULL, size);
if (!b) {
fprintf(stderr, "ERROR: Couldn't extend heap: %s\n", strerror(errno));
return NULL;
}
base = b;
}
return (b->data + 7);
}
```
I'm going to explain this function segment for segment but first, take a look at it to see if you can understand it.
1-
```c
void *malloc(size_t size) {
struct b_meta *b, *last;
size_t s = align(size);
```
In here, we have 2 uninitialized variables `*b`and `*last`. They assume multiple functions during the execution but i'll specify once i get there.
2-
```c
if (base) {
last = base;
b = find_block(&last, size);
```
We're saying: if base exists, we already extended the heap and assigned it. So, we put the `last` pointer back at the base to re-traverse the whole heap to find a free block using find_block().
3-
```c
if (b) {
if ((b->size - s) >= (BMETADATA + 8)) {
split_block(b, size);
b->free = 0;
} else {
b = extend_heap(last, size);
if (!b)
fprintf(stderr, "ERROR: Couldn't extend heap\n");
return NULL;
}
}
```
If we find a block suitable for the user's needs, and this block has enough space for another block's metadata + 8 bytes, we split it. Else, if we don't find a suitable block, we extend the heap.
> These 8 bytes are needed to keep the alignment after splitting the block.
>
> Having a block with less than 8 bytes could increase memory fragmentation later on. It's better to allocate a bit more to keep the memory aligned than having a lot of 1/2/3 bytes unused spaces scattered around the heap.
4 -
```c
} else {
b = extend_heap(NULL, size);
if (!b) {
fprintf(stderr, "ERROR: Couldn't extend heap: %s\n", strerror(errno));
return NULL;
}
base = b;
}
return (b->data + 7);
}
```
We only reach this part of the code on the first iteration, when `base` hasn't been initialized. In this case, we extend the heap and assign `base` to the block we receive (`b`) from calling extend_heap().
At the end of the function we return `b->data + 7` (end of the struct + 7 bytes to get to the start of the block where the free bytes are).
### Fragmentation
We're now freeing blocks. One of the biggest problems in memory management is the memory fragmentation, we need to keep this in mind in every step of this implementation. With that said, we have something to do here to minimize our problem. Imagine freeing a couple of blocks right now. The heap would look something like this:
[MISSING IMAGE]
Wouldn't it be a good idea to merge those two together at the end so it's not fragmented? All we have to do is test the next and previous chunks. But how do we keep track of the previous ones? We have several options:
- search from the beginning, which is really slow and not the best idea
- we could keep a pointer like we do on find_block for the last chunk visited
- or just add another link to our list (double linked list).
The last one is the better option, let's modify our struct again.
```c
struct b_meta {
size_t size; /* 8 bytes */
int free; /* 4 bytes */
struct b_meta *next; /* 8 bytes */
struct b_meta *prev; /* 8 bytes */
char data[1]; /* 1 byte */
};
```
We added the parameter `prev`and this will be used to keep track of the previous block.
Let's try to write a merge() function.
> You'll need to change extend_heap() and split_block() prior to adding that extra parameter.
> `BMETADATA`is now 40 bytes. Don't forget about it.
### merge()
```c
struct b_meta *merge(struct b_meta *b) {
if (b->next && b->next->free) {
b->size += BMETADATA + b->next->size;
b->next = b->next->next;
if (b->next) {
b->next->prev = b;
}
}
return b;
}
```
This needs to be demonstrated visually otherwise it's too confusing. Here's our demo!
[MISSING IMAGE]
### Before implementing free()
To free a dynamically allocated block, the user needs to provide a pointer returned by malloc().
Let's see an example:
```
(...)
int *p = malloc(sizeof(int));
free(p);
```
We need to check if the pointer the user gave us is a "malloc'ed" pointer. We're going to have 2 functions to handle the pointer verification: one is going to retrieve the block of metadata using only the pointer, and the other one is going to verify if the pointer is inside the heap.
But this is still not enough to be completely certain that this was a malloc'ed block. We should plant some information inside the struct that can identify that "this was malloc'ed". For this, we can use a _magic_ number or even better a pointer. This pointer will be pointing to `data` so if we verify that `block->ptr == block->data` we can make sure it was malloc'ed.
```c
struct b_meta {
size_t size; /* 8 bytes */
int free; /* 4 bytes */
struct b_meta *next; /* 8 bytes */
struct b_meta *prev; /* 8 bytes */
void *ptr; /* 8 bytes */
char data[1]; /* 1 byte */
};
```
> `BMETADATA` = 48 bytes.
> Yes, we could have defined our macro as `sizeof(struct b_meta)` but I wanted you to understand how the padding works. There's no more changes now.
### get_block()
This is the first function:
```c
struct b_meta *get_block(void *ptr) {
char *byte;
byte = ptr;
return ((void *)(byte -= BMETADATA));
}
```
[MISSING IMAGE]
Once again we use the `char*` declaration so we can do pointer arithmetic more precisely. The argument passed into the function is a pointer to the start of the block. We need to go back `BMETADATA`bytes to get to the start of metadata block and that's exactly what the function is returning.
### validate_block()
The second function is pretty straight forward too:
```c
int validate_block(void *ptr) {
if (base) {
if (ptr > base && ptr < sbrk(0)) {
return (ptr - 7 == get_block(ptr)->ptr);
}
}
return (0);
}
```
We first check if `base` is initialized:
- If it is, we check if the pointer passed by the user is between this base and the end of the heap on sbrk(0).
We then return the value that results of comparing the location of this pointer with the pointer that's pointing to the `data` variable inside.
If one of the conditions isn't true, we return 0.
[MISSING IMAGE]
### Finally implementing free()
```c
void free(void *ptr) {
struct b_meta *b;
if (validate_block(ptr)) {
b = get_block(ptr);
if (b->free) {
fprintf(stderr, "ERROR: Can't free a block that's already freed\n");
return;
b->free = 1;
if (b->prev && b->prev->free)
b = merge(b->prev);
if (b->next)
merge(b->next);
else {
if (b->prev)
b->prev->next = NULL;
else
base = NULL;
brk(b);
}
}
}
}
```
We first check if the provided pointer is valid using the validate_block() function and if this pointer is valid, it retrieves the metadata block associated with the pointer. It checks if the block is already freed to prevent double-free errors.
```c
void free(void *ptr) {
struct b_meta *b;
if (validate_block(ptr)) {
b = get_block(ptr);
if (b->free) {
fprintf(stderr, "ERROR: Can't free a block that's already freed\n");
return;
```
It checks if there exists a free previous block and if it does, it merges the current block with the previous one.
```c
if (b->prev && b->prev->free)
b = merge(b->prev);
```
If there's a next block, it attempts to merge with it. If there's no next block (i.e., this is the last block):
- If there's a previous block, it updates the previous block's next pointer to NULL.
- If there's no previous block, it sets the base to NULL.
- It then calls brk() to set the break at b since it's the last block.
```c
if (b->next)
merge(b->next);
else {
if (b->prev)
b->prev->next = NULL;
else
base = NULL;
brk(b);
```
# Conclusion
There are multiple alternatives to implement a dynamic allocator. Such as: best-fit and worst-fit. They all have trade-offs just like our first-fit malloc. This implementation is not perfect, it implements a linear search which works for small amounts of data but something like a binary tree would be much better for larger amounts of information. This implementation is also not thread-safe we would need to add some synchronization mechanisms such as a mutex. It could lead to a race condition because of the global variable `base` if multiple threads try to access it at the same time.
This took awhile to make. I learned a lot while doing this article, let's keep practicing and talking to the CPU :)