This post has the goal to help you making these functions, but the work remains to you (I give you pseudo-codes or code parts to help) ! With these following explanations, you will get the principle and then you will be able to make the functions by yourself. Right, let's start.

First malloc

This is a "dumb" memory allocation function, like I use 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 a long unsigned int
• nullptr : You also have to create it if you don't use the standard library. I defined it as #define nullptr 0

Now, we have sbrk(). According to its documentation :

brk() and sbrk() 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 information of that block 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 it'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 has 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 for the beginning. It's the base memory block of what we allocate. It can 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 optimisation.

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 has 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 simpler that you might think.

BlockMeta mem_block_from_pointer(void* pointer) {
    return (BlockMeta) pointer - 1;
}

Ok, simply change ???? by a call on this function by 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);

• Gets the memory block from its pointer
• Returns the same pointer if the block's size is enough or bigger than the requested size
• Else, has 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 returns the new created block

Again, we don't have 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 all the 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.