Memory allocation/deallocation routines malloc() and free()

According to my declaration, allocate the 50000 block of array. If memory block is available on the array, the program allocates a block from the array according to specify size.  Here I used the array data structure to implement the heap. In this code taken large contiguous buffer which used to allocate all the spaces associate with the NewMalloc() function. There doesn't allocate the same region of memory to two different NewMalloc(). Initially all 50000 bytes are free in this array.

NewMalloc()

            It takes one integer argument which represents the size and return a pointer to a contiguous region of that many bytes.

            Now call to NewMalloc(60). There we expect to allocate the first 60 bytes and return a pointer to the caller. Actually in the array allocates 68-bytes for that region. Because I maintain a meta data that keeps track of what space is allocated and what space is free. In meta data I hold the size of the block and availability of the block.  Both these values are integer, that is the reason that allocated block from the NewMalloc(60) get extra 8-byte long.

            When we allocate the 60 bytes chunk from calling NewMalloc(60), it splits the one big free block in to two blocks. First block is that return to the user of size 60. There actually doesn't return a pointer to the meta data to the user, but a pointer to the first bytes that the user defined. The second block split is become the remaining free space. We must create a new meta data record at the very front of this free space that indicate it's size and the availability state.

Now call to NewMalloc(32). There we cannot use the first 60 bytes, because these bytes have been allocated. The 49924-byte free block at the head of the free list must be split in to a 32-byte allocated chunk and 49884-byte free chunk after allocating that end of the array.

NewFree()

            Suppose that user must want to free the first allocated 60-bytes. The routine NewFree() must free that block. After freed that first 60-bytes array should like this.

According to the above diagram the biggest block we can allocate is only 49884 byte long. If user allocate NewMalloc(49960) should fail and return NULL. Because there is not a free block on the array to allocate contiguously. Here the total free space is 60 + 49884 = 49944-bytes. But biggest block we can allocate is only 49884-bytes long.

Usage of First-Fit

            Now there have two free blocks 60 and 49884-bytes long. When call to NewMalloc(200) is made, split the second free block. Because 200 is too big for the first free block. Here is the diagram for that.

Here actually allocate 208-bytes. Because extra 8-bytes for data structure (meta data) of the node.And then call to NewMalloc(32) is called, then 32-byte small enough to allow us to split either the 60-byte block or ending free block (49676-bytes free block). Then here we must have to select which block assigns. The solution is using First-Fit algorithm. It means starting from the head of the freelist and going through the list until find the first block that big enough to hold the request.

According to whole above explanation, we can get little bit of knowledge inner working of malloc() and free() functions.

Implementation in C 

#include <stdio.h>
#include <stdlib.h>
//Maximum heap(array) size
#define SIZE 50000
//Basic Structure of the node
typedef struct node_type{
    int size;
    int nonAvailable;
}node;
//Array declaration
static char heap[SIZE];

void* NewMalloc(int size);
void NewFree(void *pointer);

void* NewMalloc(int size){
    //Full block size of the allocated memory area
    int blockSize = size + sizeof(node);
    node *head;
    //First node allocated from the beginning of the array
    head = (node *)&heap;
    //printf("head->size = %d\n", head->size);
    if(blockSize > SIZE){
        printf("\nError: Allocated memory is too long\n");
    }
    if(head->size == 0){
        head->size = SIZE;
        head->nonAvailable = 0;
    }

    //Find the corresponding empty locations
    while(head->nonAvailable || head->size < blockSize){

        void *heap_initial, *final, *next;
        heap_initial = &heap;
        //Keep the last array index
        final = heap_initial + SIZE;
        next = head;
        //Get the next block
        next += head->size;
        //Check the next available block is less than the final array index
        if(next < final)
            head = next;
        else
            head = NULL;
   
        if(head == NULL)
            break;
    }
 
    if(head == NULL){
        return NULL;
    }
    else{
        void* initial_heap = head;
        //Get the remaining size
        int remainder = head->size - blockSize;
        if(remainder > (sizeof(node) + 4)){
            //Create the new node to next available block
            node* newhead = (node*)(initial_heap + blockSize);
            newhead->size = remainder;
            newhead->nonAvailable = 0;
            head->size = blockSize;
        }
        //Now block is allocated
        head->nonAvailable = 1;
        //Return the initial address of the allocated block
        return (initial_heap + sizeof(node));
    }
}
void NewFree(void* pointer){

    void *initial, *end;
    //Keep initial location
    initial = &heap;
    //Keep last location
    end = initial + SIZE;
    //Check the validity of the pointer value
    if(pointer >= initial && pointer < end){
        //Get the initial address of the pointer node which need to remove
        node* head = (pointer - sizeof(node));
        node* nexthead;
        //Get the next block from the array
        void *heap_initial, *final, *next;
        heap_initial = &heap;
        final = heap_initial + SIZE;
        next = head;
        //Go through the blocks
        next += head->size;
        //Check next block initial value less than the ending value of the array
        if(next < final)
            nexthead = next;
        else
            nexthead = NULL;
        //Check next node is available
        if(!nexthead->nonAvailable){
            head->size += nexthead->size;
        }
        head->nonAvailable = 0;
    }
}