How to rewrite "malloc" from scratch ? (with C)
This tutorial presents the way of recoding about-memory functions like "malloc", "free", "realloc", "memcpy", ... without the standard library
This post has the goal to help you making these functions, but the work remains for you (I give you pseudo-code or code parts to help) ! With these following explanations, you will get the principle and then you could make the functions by yourself. Right, let's start.
First malloc
This is a "dumb" memory allocation function, like I used to call it. We will not keep it, but you can start to introduce your code with this one.
void* my_malloc(size_t size) {
void* allocated = sbrk(0);
void* request = sbrk(size);
if (request == (void*) -1) {
return nullptr;
}
return allocated;
}
Let me explain it :
void*
: It's a pointer without assigned type, then you can have a pointer pointing on any object, no worries of its type.size_t
: You have to create it if you don't use the standard library. It's simply along unsigned int
nullptr
: You also have to create if you don't use the standard library. I defined it as#define nullptr 0
Now, we have sbrk()
. According to its documentation :
brk()
andsbrk()
change the location of the program break, which defines the end of the process's data segment (i.e., the program break is the first location after the end of the uninitialized data segment). Increasing the program break has the effect of allocating memory to the process; decreasing the break deallocates memory. Source : manpages.ubuntu.com
We are also checking if the request was accepted and then we return a pointer on the allocated block.
Do you see the problem here ? When we allocate an object, we want to free it after. But how can we know which memory block was allocated to free it ? Let's solve that problem.
Memory blocks
For each allocation, we will save the block's information to a structure called BlockMeta
: The meta-information of a memory block. It's true, the size in memory for each allocation will be increased but that's not so terrible, no worries.
Create your own from this scheme :
BlockMeta
- size // how much space you are using in memory for this block
- next // the following block
- is_free ? // maybe you already freed it
Help about types
I chose to set a type for this structure :typedef s_block_meta* BlockMeta
when s_block_meta
is the structure's name definition and BlockMeta
a type for the objects.
The next block is as the same type. But, the type is not already defined. Simply write struct s_block_meta* next;
Before updating the malloc
function, using BlockMeta
structure, we have to create two another functions to request memory space :
BlockMeta mem_find_free_block(BlockMeta* last, size_t size);
BlockMeta mem_request_space(BlockMeta last, size_t size);
And a global variable called BLOCK_BASE
set as nullptr
at begin. It's the base memory block of what we allocate. It could be used to get the last memory block or check if we are in the first malloc
call...
The find_free_block
function is very simple. The goal is to use the freed blocks again, for optimization.
var current_block = BLOCK_BASE
while
- current_block is ok
- current_block is not free // if the block is free, we could use it
- current_block's size is less than the requested size
loop :
last_block = current_block
current_block = current_block.next
// here, we found what we wanted : freed block with the good size
return current_block
The request_space
function is used when find_free_block
failed, it's a call to the operating system for more space. It looks more like our first "dumb malloc" because it uses sbrk
.
var created_block = null
var request = sbrk(requested_size + size of BlockMeta)
assert for request
if last exists
last.next = created_block
set created_block's attributes
return created_block
Create malloc using memory blocks
Well, now we can recreate malloc()
.
void* my_malloc(size_t size);
check requested_size // because it can be <= 0
var created_block = null
if BLOCK_BASE not ok // the first call
created_block = request_space(nullptr, requested_size) // here is not last when it's the first allocation
BLOCK_BASE = created_block
assert created_block
return created_block
var last = BLOCK_BASE
created_block = find_free_block(&last, size)
if created_block == nullptr // no block found, we have to request to the operating-system
created_block request_space(last, size)
assert created_block
return created_block
// here, a free block was found then we can use it
created_block.is_free = false
return created_block
Congratulations ! But, do you remember we have done all of these things to make the free
function ? Let's do it !
Free all that memory !
void mem_free(void* pointer);
From a pointer, we want to get the allocated block and set it as free
assert pointer
var retrieved_block = ????
retrieved_block.is_free = true
Mmhhh... We forgot the function that retrieves a memory block from its pointer. Don't be afraid, it's more simple that we can think.
BlockMeta mem_block_from_pointer(void* pointer) {
return (BlockMeta) pointer - 1;
}
Ok, simply change ????
by this function's call giving pointer
as argument and your free
function will work.
Allocate that again please !
I will not help you so much for the realloc
function. Keep in mind how it works without forgetting assertions :
void* my_realloc(void* pointer, size_t requested_size);
- Get the memory block from its pointer
- Return the same pointer if the block's size is enough or bigger than the requested size
- Else, you have to make a new allocation, to copy the pointed block to the new created block and to free the old block pointed by
pointer
- And return the new created block
Again, we haven't the memory copying function.
Copy copy copy copy copy copy ...
void mem_cpy(void* dest, const void* source, size_t size);
It's simply a function walking through both blocks. dest[i] = source[i]
Take note that because these are void
pointers, we have to cast dest
and source
to integer pointers.
Other memory utilities
bool mem_cmp(const void* first, const void* second, size_t size) {
The mem_cmp
looks like mem_cpy
but it doesn't set anything, when the first one's element is different than the second one's element, it returns "false". Else, when the loop has checked each elements, it returns "true"
void mem_set(void* dest, int fill_value, size_t size);
Same but it's setting each element as fill_value
Congratulations !
You did it ! Congratulations and thank you for reading me :)
I did my own memory library memlib, take a tour on it and compare with your work when you've done it. Don't hesitate to make a "pull request" on the repository if you did better stuff.
If you want some help, I'm still here to reply : Anto#3722 on Discord or below this post in the comments section.