Malloc-Simulation

Dilan Perera — Mon, 14 Dec 2020 16:54:25 +0000

Malloc() and Free()

In C language array is a collection of a fixed number of values. Once the size of an array is declared, you cannot change it. sometimes the size of the array you declared may be insufficient. To solve this issue, you can allocate memory manually during run-time. This is known as dynamic memory allocation in C programming. To allocate memory dynamically, library functions are malloc(), calloc(), realloc() and free() are used. These functions are defined in the header file.

malloc()

The name “malloc” stands for memory allocation. The malloc() function reserves a block of memory of the specified number of bytes. And, it returns a pointer of void which can be cast into a pointer of any form.

Syntax of malloc()

ptr = (castType*) malloc(size);

Example:- ptr = (float*) malloc(100 * sizeof(float));

The above statement allocates 400 bytes of memory. It’s because the size of float is 4 bytes. And, the pointer ptr holds the address of the first byte in the allocated memory.

The expression results in a NULL pointer if the memory cannot be allocated.

free()

Like other languages in C dynamically allocated memory created with malloc() doesn’t get freed on its own. the developer must explicitly use free() to release the space he allocated previously.

Syntax of free()

free(ptr);

In this “Malloc and Free” Simulation,

25000 Bytes long array considered as memory and all allocation are done using that memory. The simulated version of malloc() is called MyMalloc() and the simulated version of free() is called MyFree().

Like in real malloc(), First MyMalloc() function requires size as a parameter, and then the function will allocate that much of memory from that 25000 bytes pool (it search best-fit memory location for that given size of memory and allocate it ). Finally, the function returns its pointer.

When an allocation is happening, 25000 Bytes of the memory pool divide into the various size of memory blocks. To connect those memory blocks, all memory blocks are put into the linked-list. Every memory block is connected to two other blocks except head and tail blocks. To track the information about those memory blocks, meta-data is used. Every memory block has its meta-data section. meta-data will track whether that block is allocated or not, the size of the block, and the pointer of the next block.

MyFree() is also requires a pointer of allocated memory as a parameter and working exactly like real free()
function set the allocated block as free by changing the metadata of that allocated memory block. Then check whether's next or/and previous blocks are free, if those are free, those blocks are merged with newly freed block and create a new block.

Files

mymalloc.c - implementation of MyMalloc()/MyFree()

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

struct metaData *metaList = NULL;

/* This is for malloc first use, just initialize the first node of metaData linked list*/
struct metaData *initializeMemory(void *startPtr, size_t sizeMem)
{
    struct metaData *tmp = (struct metaData *)startPtr;
    tmp->STATUS = FREE;
    tmp->NEXT   = NULL;
    tmp->SIZE   = sizeMem - sizeof(struct metaData);
    return tmp;
}
/* Create a new node and add it before node which point "nextptr" */
struct metaData *newMeta(struct metaData *startPtr, size_t sizeMem, struct metaData *nextPtr)
{
    struct metaData *tmp = startPtr;
    tmp->STATUS = FREE;
    tmp->NEXT   = nextPtr;
    tmp->SIZE   = sizeMem - sizeof(struct metaData);
    return tmp;
}
/*Find the best fited node in the linkedlist and returns it's pointer*/
struct metaData *searchBestFit(size_t targetSize)
{
    struct metaData *tmp = metaList;
    struct metaData *min = NULL;
    while (tmp)
    {
        if (min == NULL && (tmp->SIZE) >= targetSize && (tmp->STATUS) == FREE)
            min = tmp;
        else if (min && (tmp->SIZE) >= targetSize && (tmp->SIZE) < (min->SIZE) && (tmp->STATUS) == FREE)
        {
            min = tmp;
        }

        tmp = tmp->NEXT;
    }
    return min;
}
/* Just for testing purposes, print all nodes in the linked list*/
void printMemory(struct metaData *ptr)
{
    //if metaList is empty,create a new node and init all memory to it
    if (!metaList) 
    {
        metaList = initializeMemory((void *)MEMORY, MEMSIZE);
        ptr=metaList;
    }
    while (ptr)
    {
        printf("[PTR=%p]\t[STARTPTR=%p]\t[SIZE=%ld]\t[STATUS=%s]\t[NEXTPTR=%p]\t\n", ptr, ptr + 1, ptr->SIZE, (ptr->STATUS == 0) ? "ALLOC" : "FREE", ptr->NEXT);
        ptr = ptr->NEXT;
    }
    printf("\n\n");
    return;
}

void *MyMalloc(size_t givenSize)
{
    //if metaList is empty,create a new node and init all memory to it
    if (!metaList) 
    {
        metaList = initializeMemory((void *)MEMORY, MEMSIZE);
    }
    struct metaData *ptr;
    ptr = searchBestFit(givenSize + sizeof(struct metaData));
    //if there is a fitted slot for the given node setup it for use otherwise return NULL
    if (ptr)
    {
        char *tmp;
        tmp = (char *)ptr;
        tmp = tmp + (int)sizeof(struct metaData) + (int)givenSize;
        ptr->NEXT   = newMeta((struct metaData *)tmp, ptr->SIZE - givenSize, ptr->NEXT);
        ptr->SIZE   = givenSize;
        ptr->STATUS = ALLOCATED;
        return ptr + 1;
    }
    else
    {
        fprintf(stderr, "Error ! Out Of Memory \n\n");
        return NULL;
    }
}
/* Sreach for a node,which it's nextnode has "locAddress" and return it*/
struct metaData *preMeta(void *locAddress)
{
    struct metaData *tmp    = metaList;
    struct metaData *preTmp = metaList;
    while (tmp)
    {
        if (tmp + 1 == locAddress)
        {
            return preTmp;
        }
        preTmp = tmp;
        tmp = tmp->NEXT;
    }
    return NULL;
}

void MyFree(void *givenAddress)
{
    //if the first node has that "givenAddress" just free it 
    if (givenAddress == metaList + 1)
    {
        metaList->STATUS = FREE;
        if (metaList->NEXT != NULL)
        {
            //if second node is also a free node mearge them together
            if (metaList->NEXT->STATUS == FREE)
            {
                struct metaData *tmp;
                tmp = metaList;
                size_t newSize = tmp->SIZE + tmp->NEXT->SIZE + sizeof(struct metaData);
                tmp->SIZE = newSize;
                tmp->NEXT = tmp->NEXT->NEXT;
            }
        }
    }
    else
    {
        struct metaData *preMetaAddress = preMeta(givenAddress);
        //if there is a pointer called "givenAddress" make it free and mareage with near free slots
        if (preMetaAddress)
        {
            preMetaAddress->NEXT->STATUS = FREE;
            //if node is last one 
            if (preMetaAddress->NEXT->NEXT == NULL)
            {
                if (preMetaAddress->STATUS == FREE)
                {
                    preMetaAddress->SIZE = preMetaAddress->SIZE + preMetaAddress->NEXT->SIZE + sizeof(struct metaData);
                    preMetaAddress->NEXT = preMetaAddress->NEXT->NEXT;
                }
            }
            else
            {
                // prevNode and nextNode both are empty
                if (preMetaAddress->STATUS == FREE && preMetaAddress->NEXT->NEXT->STATUS == FREE)
                {
                    preMetaAddress->SIZE = preMetaAddress->SIZE + preMetaAddress->NEXT->SIZE + preMetaAddress->NEXT->NEXT->SIZE + sizeof(struct metaData) * 2;
                    preMetaAddress->NEXT = preMetaAddress->NEXT->NEXT->NEXT;
                }
                //only prevNode is  empty
                else if (preMetaAddress->STATUS == FREE)
                {
                    preMetaAddress->SIZE = preMetaAddress->SIZE + preMetaAddress->NEXT->SIZE + sizeof(struct metaData);
                    preMetaAddress->NEXT = preMetaAddress->NEXT->NEXT;
                }
                //only nextNode is empty
                else if (preMetaAddress->NEXT->NEXT->STATUS == FREE)
                {
                    preMetaAddress->NEXT->SIZE = preMetaAddress->NEXT->SIZE + preMetaAddress->NEXT->NEXT->SIZE + sizeof(struct metaData);
                    preMetaAddress->NEXT->NEXT = preMetaAddress->NEXT->NEXT->NEXT;
                }
            }
        }
        else
        {
            fprintf(stderr, "Error ! Enter a Valid Pointer");
        }
    }
    return;
}

mymalloc.h - Declarations related to MyMalloc()/MyFree()

/***** MYMALLOC FUNCTION USING BEST FIT ******/
#include<stddef.h>
#include<stdio.h>
#define FREE 1
#define ALLOCATED 0
#define MEMSIZE 25000

char MEMORY[MEMSIZE];//create byte addressed array

struct metaData{
    int STATUS;
    size_t SIZE;
    struct metaData * NEXT;
};

struct metaData * initializeMemory(void *startPtr, size_t sizeMem);
struct metaData * newMeta(struct metaData *startPtr, size_t sizeMem, struct metaData *nextPtr);
struct metaData * searchBestFit(size_t targetSize);
void printMemory(struct metaData *ptr);
void * MyMalloc(size_t givenSize);
struct metaData * preMeta(void *locAddress);
void MyFree(void *givenAddress);

testCases.c - Sample Test Cases
`

#include<stdio.h>
#include "mymalloc.c"
int main()
{
printMemory(metaList);

char * x=MyMalloc(10000);
printMemory(metaList);

char * y=MyMalloc(1000);
printMemory(metaList);

MyFree(y);
printMemory(metaList);

char * z=MyMalloc(27000);
printMemory(metaList);

return 0;
}

Note : Defragment procedure for memory is not implemented.

View on GitHub