Hi guys, blogging after a long time… 🙂

First of all, this post is about some code I developed in C for an assignment in my degree program, which I think would be very helpful to those who are in need, specially my juniors. 😉 But please use this just to get an idea and copy pasting will guarantee a big 0!

Follow is the question we got.

What does malloc and free do?

So according to the problem, we were to implement MyMalloc() and MyFree() functions that are similar to malloc() and free() functions given in the C standard library, but they should only allocate and free memory from a given array of 20000 bytes. First thing to do was study what actually do by malloc() and free(). After some readings, I gathered that simply malloc() would return a void pointer that points to a memory block of the size we gave as the parameter to the function, from the free space available in the memory, i.e. RAM. Accordingly free() would release such allocated memory blocks by using the pointer we supply as it’s parameter.

Think of the RAM as a set of slots as follows and each slot is 1 byte. If we call malloc(4); it’ll return the void pointer p1, that points to 4 free slots, i.e a block.

As you can see, there are other places in memory that also can give 4 free blocks. The place of the allocation depends on three strategies as,

1. First Fit – Allocates the first available block. (Method used in above example)
2. Best Fit – Allocates the block in which after the allocation the left over free space is minimum.
3. Worst Fit – Allocates the block in which after the allocation the left over free space is maximum.

Each method have it’s pros and cons and you can read more about these three hear.

Then we can call free(p1); that would free up the allocated memory block which will result in follow diagram.

There are more to it, but this is the very basic procedure of malloc() and free(). In our case, the RAM is 20000 bytes array.

Getting started

First of all we need to identify each set of memory blocks individually. I used a simple header of 5 bytes for that which contains 1 byte to specify whether the block is allocated or free (a/f) and 4 bytes to specify the block size in bytes. (In C char is 1 byte and int is 4 bytes in size)

I used a char array of 20000 bytes as my memory and assign ‘null’ to each memory block by follow code segment.

char mem[SIZE] = {'\0'};

At the beginning, I considered the whole array is a one free block with one header. But that header data should be included (initialize memory) before we do any process, and also there should be a way to know whether the array is initialized or not. I used the first byte of the array to indicate that, and called it “init bit”. After the initialization my array looked like this.

After that each MyMalloc(int x); call would behave as follows.

1. Search through the array until it finds a free block that has the size greater than or equal to the size given as the parameter, x.
2. Change the first byte of it’s header to ‘a’.
3. If the block size is greater than x + 5, then divide the block into two and insert a new header for the left over space.
4. Cast and return a void pointer that points to the block.

That’s about it! Simple right? 😉 Let’s see the code.

Code explanation

#include <stdio.h>

#define SIZE 20000 //size of the memory
#define INIT 0 //'i' if array is initialized, '\0' otherwise
#define I 1 //i to use in for loops, 4 bytes
#define START 5 //actual position that can use to allocate

char mem[SIZE] = {'\0'}; //Null all values in the array

void * MyMalloc(size_t size){
	printf("Start of mymalloc\n");

	if (mem[INIT] == '\0') {
		int i;
		for (i = 0; i < SIZE; ++i) 		{ 			mem[i] = '\0'; 		} 		mem[INIT] = 'i'; 		mem[START] = 'f'; 		*(int*)(&mem[START + 1]) = 19994; 		printf("Initialized\n"); 	} 	int i = START; //*(int*)(&mem[I]) 	while (1) { 		printf("i:%d\n", i); 		 		if (i > 20000) {
			printf("End of MyMalloc\n");
			return NULL;
		}
		if ((mem[i] == 'f') && (*(int*)(&mem[i + 1]) >= (size))){
			mem[i] = 'a'; // to indicate that this is an allocated block

			int curSize = *(int*)(&mem[i+1]);
			int leftSize = curSize - (size + 5);
			//if the left size is < 6B, thw whole block is allocated 			if (leftSize > 5) {
				*(int*)(&mem[i+1]) = size; //update the new size

				int next = i + 5 + size; //4 bytes to store the size of the block
				printf("next:%d\n", next);

				mem[next] = 'f';
				*(int*)(&mem[next + 1]) = leftSize;
			}
			printf("End of MyMalloc\n");
			return (void*)(&mem[i+5]);
		} else {
			i += *(int*)(&mem[i + 1]) + 5;
		}
	}
}

void MyFree(void* ptr){
	printf("Start of MyFree\n");
	int i = START;
	int before = 0;
	while (1) {
		printf("i:%d\n", i);

		if (i > 20000) {
			printf("End of MyFree\n");
			break;
		}
		if ((void*)(&mem[i+5]) == ptr){
			printf("found\n");
			mem[i] = 'f';
			//check if the slot after is a free one
			int next = i + 5 + *(int*)(&mem[i + 1]);
			if (mem[next] == 'f') {
				//combining two free slots
				*(int*)(&mem[i + 1]) = *(int*)(&mem[i + 1]) + 5 + *(int*)(&mem[next + 1]);
			}

			//check if the slot before is a free one
			if (mem[before] == 'f') {
				//combining two free slots
				*(int*)(&mem[before + 1]) = *(int*)(&mem[before + 1]) + 5 + *(int*)(&mem[i + 1]);
			}
			printf("size:%d\n", *(int*)(&mem[before + 1]));
			printf("End of MyFree\n");
			break;
		} else {
			before = i;
			i += *(int*)(&mem[i + 1]) + 5;
		}
	}
}

void printer(int size){
	printf("Start of printer\n");
	int i;
	for (i = 0; i < size; ++i)
	{
		//printf("%d\t%s\t%c\n", i, &mem[i], mem[i]);
		printf("%d\t%c\n", i, mem[i]);
	}
	printf("End of printer\n");
}

As you can see my array is mem, and mem[0] is used as init bit. Next 5 bytes are for the first header and mem[5] is the actual position that we can start giving away as memory blocks. There’s a very important code segment I want to share.

*(int*)(&mem[5]) = 19994;

This will take an address of a memory location, cast that into integer pointer and sets its value to 19994. Basically this line will let us store integers in a char array. This is really important to overcome our problem, specially if you saw this line in the question.

4. All the data structures that are required to manage the memory must also reside within the same array.

What’s that mean? It means you cannot use any out side variables in your code! Did you notice the line 14 of my code? Well according to this, it’s illegal! We cannot use such variables. But you can see I’ve used few of them hear and there right? I wrote my code using them and after I’m done, I replaced all of them with mem array locations. All this was possible because of the above line of code.

Line 13 to 24 is the initialization code, only executes once. Then come the while loop that searches through the array to find a suitable block using the pointing variable ‘i’. Each time if the block is not free or the size doesn’t match, I added the size of the block and size of the header (5) to the pointing variable ‘i’ to pass the block. I’ve seen some approaches that used linked lists to do this, but in my opinion they needed a bigger header which leads to memory wastage.

MyFree function is also operate similarly.

1. Goes through the array block by block and matches the memory address of each block with the given pointer as the function parameter to find the correct block.
2. Free the block by changing header.
3. Check if the next block is also a free block. If it is, then combine them.
4. Check if the previous block is also a free block. If it is, then combine them.

That’s about it! Yaai! 😀

Running the example

Let’s try to run this in your own machine. First copy paste above code in to a new file name “mymalloc.c”. Then create another file named “mymalloc.h”. This one doesn’t have to contain any code, it’s only used to import our mymalloc into some other main program. Then create your main file, “main.c”. Follow is my sample main code.

#include <stdio.h>
#include "mymalloc.h"
#include <string.h>

int main(int argc, char const *argv[])
{
	printf("Start of main\n");

	char* p1 = (char*)MyMalloc(10);
	//strcpy(p, "Helloaaaa");
	printer(50);

	char* p2 = (char*)MyMalloc(10);
	printer(50);

	char* p3 = (char*)MyMalloc(10);
	printer(50);

	MyFree((void*)p2);
	printer(100);

	MyFree((void*)p3);
	printer(100);
	temp(33);

	char* p4 = (char*)MyMalloc(11);
	printer(100);

	temp(49);
	printf("End of main\n");
	//printer(50);
	return 0;
}

Then compile and run. If you’re using gcc compiler in a linux OS, just type

gcc mymalloc.c main.c -o a

to compile the files and

./a.out

to run in your terminal. If you see some lines printing starting with “Start of main” on the console then you’re good. 😀
If you’re on windows hear is a great tutorial to help you install gcc on windows.

You can download all files from hear. It contains the “mymalloc.c” file with replaced variables as well. “mymalloc-original.c” is the one I posted hear.

OK then.! I hope you got something out of this. Please like and share. Thank you.