Free-Up-The-Space (Part-3)

This is Part 3 of my series on memory allocation. I kept having this recurring feeling that I did not add a function to free up the memory after use, which has led me to this article. Additionally, an excellent lunch on Monday afternoon acted as a catalyst that brought this article into being. I was not planning on writing this, but Sir Casper accused me of using AI for writing my articles (Yes, I use it, but only for proofreading and grammar). Therefore, I have undertaken this assignment not to prove him wrong, but as a fun escapade of life.

There will be no breakthroughs or eureka moments here, just an accumulation of mechanics with fundamental ideas of how to work with memory inside RAM. I am working with virtual memory, so please keep that in mind.

Pointer Arithmetic

void * user_space = (void *)(metadata2 + 1);
struct metadata *metadata3 = (struct metadata *)((char *)user_space + request_size);

The lovely code above is a wonderful way to understand pointer arithmetic. I will be pasting my whole code below, so please look at it if you get confused.

void * user_space
Here, I have created a pointer of type void, which literally means the data type has not been defined yet. If you are wondering how the OS deals with it, just know it is read as a marker that says the type will be defined later, and the OS moves on.

(void *)(metadata2 + 1);
As we can see in our code, we have a data type struct named metadata, and we created a variable named metadata2 of type struct metadata. So, if the data type is struct metadata, how is it possible that we can do + 1? Isn't 1 an integer? Also, we cannot add integers to a struct, pointer, boolean, or array. So, what are we doing here?

First, we need to understand what metadata2 is: it is a struct of 24 bytes. How? Look at this code:

struct metadata {
    size_t memory_size;
    bool is_free;
    struct metadata * ptr;
};

size_t is for an unsigned integer whose data size changes according to the architecture; for x86 64-bit, it is 8 bytes. bool here is 1 byte. We only need 1 bit to store 0 or 1, but because computer memory is mapped out in 8-bit blocks (byte-addressable), the smallest piece of memory we can ask for is 1 byte.

Finally, we have a pointer inside the struct, which is always 8 bytes. Because all these programs are running on a 64-bit architecture, the CPU processes data in 64-bit (8-byte) chunks, and memory addresses themselves are 64 bits wide. This creates a theoretical maximum memory size range of 0 bytes to 16 exabytes (EB) (specifically 2^64 bytes, which equals 18,446,744,073,709,551,616 bytes). These spaces are divided into 2 ranges: User-Space and Kernel-Space. In typical systems, the Virtual Memory is addressed using a 2^48 bit range.

What all this means is that in our 8-byte addressable system, the CPU finds it easier to deal with 8 bytes at a time. Hence, padding is used to make each field of the memory stack exactly 8 bytes, so 8 x 3 = 24 bytes for our struct.

In turn, when we see metadata2 + 1, we need to understand that metadata2 is actually 24 bytes. It is a struct located inside the raw_memory
void * raw_memory = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
where each block is sized by our 24-byte struct. Hence, when we do + 1 arithmetic, we get a jump of 24 bytes instead of just 1. If we had converted it to (char *), then we could have gotten a 1-byte jump, but we are looking at it pretending it's a struct metadata of 24 bytes located inside the raw_memory.
The math is the same, but the step values are different. That's how I look at it.

Free-Up Space

void my_free(void *user_space){

    struct metadata *cleaning_crew = ((struct metadata *)user_space) - 1;
    cleaning_crew->is_free = true;
}

Here too, pointer arithmetic dominates. What we literally did was point at the user_space and subtract 1. user_space here is a pointer to the space right after metadata2, so by subtracting 1 (which steps back by exactly one 24-byte struct), we just ended up right back at the start of metadata2.
We then changed is_free to true to represent that indeed, the memory is free.

Finally

Never forget to take the memory address and anchor it to a variable, or else it will be lost (like Casper's love for women), leading to a memory leak.

    //here, i got the free space to use later, after i am done using i need to destroy it
    void * my_data = my_malloc(36);
    // here after i am done using teh memory i destroy it
    my_free(my_data);

As I keep exploring computers, I explore life as a whole. It has been a lovely journey and a learning experience. Soon I will be exploring more complex topics and ideas I have in mind. Thank you, and have a lovely life ahead.

Final Code

#include <stdio.h>
#include <stdbool.h>
#include <sys/mman.h>

struct metadata {
    size_t memory_size;
    bool is_free;
    struct metadata * ptr;
};

void * my_malloc(size_t request_size);
struct metadata *global_metadata;
void my_free(void * user_space);



int main(){

    void * raw_memory = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

    struct metadata *metadata1 = (struct metadata *)raw_memory;
    metadata1->memory_size = 4096 - sizeof(struct metadata);
    metadata1->is_free = true;
    metadata1->ptr = NULL;

    global_metadata = metadata1;

    //here, i got the free space to use later after done using i need to destroy it
    void * my_data = my_malloc(36);
    // here after i am done using teh memory i destroy it
    my_free(my_data);
    return 0;
}


void * my_malloc(size_t request_size){

    struct metadata *metadata2 = global_metadata ;


    while (metadata2 !=  NULL){
        if (metadata2->is_free == true && metadata2->memory_size >= request_size){
            void * user_space = (void *)(metadata2 + 1);
            struct metadata *metadata3 = (struct metadata *)((char *)user_space + request_size);

            size_t old_size = metadata2->memory_size;

            metadata2->is_free = false;
            metadata2->memory_size = request_size;
            metadata3->ptr = metadata2->ptr;
            metadata2->ptr = metadata3;

            metadata3->is_free = true;
            metadata3->memory_size = old_size - request_size - sizeof(struct metadata);
            metadata3->ptr = NULL;

            return user_space;

        }

        metadata2 = metadata2->ptr;

    }
return NULL;    
}

void my_free(void *user_space){

    struct metadata *cleaning_crew = ((struct metadata *)user_space) - 1;
    cleaning_crew->is_free = true;
}