Heap Memory Allocator in C

Hi System Devs, Hope you are doing well!

In this third and final instalment of article, we cover the implementation of the C library functions free(), calloc(), and realloc().

Please Read the following two Parts before proceeding further:

PART 1 : Introduction and sbrk() system call

PART 2 : Our way of malloc() implementation

free()

Managing freed memory is an incredibly interesting and hard problem with two main concerns: performance and reducing heap fragmentation / waste:

How do we organize free blocks of memory such that we can quickly locate a sufficiently large block (or determine that we lack one) when someone calls malloc without making calls to free prohibitively expensive?
What can we do to reduce fragmentation and waste in the face of sometimes drastically changing allocation patterns over the lifetime of a (potentially long-running) program? It's worth noting that heap fragmentation can have a substantial impact on CPU cache efficiency.

Hope you read the first two parts of this article in order to at what our free() should do. free() has to first deterimine if the block-to-be-freed is at the end of the heap. If it is, we can release it to the OS. Otherwise, all we do is mark it ‘free’, hoping to reuse it later.

void free(void* block) {
    header_t *header, *temp;
    void *program_break;
    if(!block) {
        return;
    }
    pthread_mutex_lock(&global_malloc_lock);
    header = (header_t*)block - 1;

    program_break = sbrk(0); // Current value of program break

   // Check if the block is the last one. If yes, release it to OS
   // after adjusting head and tail pointers to reflect the loss.
    if((char*)block + header->s.size == program_break) {
        if(head == tail)
            head = tail = NULL;
        else {
            temp = head;
            while(temp) {
                if(temp->s.next == tail) {
                       temp->s.next = NULL;
                       tail = temp;
                }
                temp = temp->s.next;
            }
        }
        sbrk(0 - sizeof(header_t) - header->s.size);
        pthread_mutex_unlock(&global_malloc_lock);
        return;
    }
    header->s.is_free = 1;
    pthread_mutex_unlock(&global_malloc_lock);
}

Here, first we get the header of the block we want to free. All we need to do is get a pointer that is behind the block by a distance equalling the size of the header. So, we cast block to a header pointer type and move it behind by 1 unit. header = (header_t*)block - 1;

sbrk(0) gives the current value of program break. To check if the block to be freed is at the end of the heap, we first find the end of the current block. The end can be computed as (char*)block + header->s.size. This is then compared with the program break.

If it is in fact at the end, then we could shrink the size of the heap and release memory to OS. We first reset our head and tail pointers to reflect the loss of the last block. Then the amount of memory to be released is calculated. This the sum of sizes of the header and the acutal block: sizeof(header_t) + header->s.size. To release this much amount of memory, we call sbrk() with the negative of this value.

In the case the block is not the last one in the linked list, we simply set the is_free field of its header. This is the field checked by get_free_block() before actually calling sbrk() on a malloc() (Please check PART2).

calloc()

The calloc library function is almost same as malloc function in the functionality except calloc() zero-initilizes the buffer. Zeroing out the memory may take a little time, so you probably want to use malloc() if that performance is an issue. If initializing the memory is more important, use calloc().

Calloc is useful when the program requires multiple blocks of memory, especially when handling arrays or structures that need to be initialised to zero.

So, The calloc(num, nsize) function allocates memory for an array of num elements of nsize bytes each and returns a pointer to the allocated memory. Additionally, the memory is all set to zeroes.

Syntax: ***void *****calloc(*size_t*numberOfBlocks,size_tsizeOfEachBlock)*

void* calloc(size_t num, size_t nsize) {
    size_t size;
    void *block;
    if(!num || !nsize)
        return NULL;
    size = num * nsize;
    // Check for multiplication overflow
    if(nsize != (size/num))
        return NULL;
    block = malloc(size);
    if(!block)
        return NULL;
    memset(block, 0, size);

    return block;
}

Here, we do a quick check for multiplicative overflow, then call our malloc(),
and clears the allocated memory to all zeroes using memset()

realloc()

realloc() changes the size of the given memory block to the given size.

void *realloc(void *block, size_t size) {
    header_t *header;
    void *ptrToReallocatedBlock;
    if(!block || !size)
        return malloc(size);
    header = (header_t*)block - 1;
    if(header->s.size >= size)
        return block;
    ptrToReallocatedBlock = malloc(size);
    if(ptrToReallocatedBlock) {
        memcpy(ptrToReallocatedBlock, block, header->s.size);
        free(block);
    }
    return ptrToReallocatedBlock;
}

Here, we first get the block’s header and see if the block already has the size to accomodate the requested size. If it does, there’s nothing to be done.

If the current block does not have the requested size, then we call malloc() to get a block of the request size, and relocate contents to the new bigger block using memcpy(). The old memory block is then freed.

We can also implement our own memset(), memcpy(), memmove() functions. However, I prefer to use the existing library functions as they are much more reliable.

That's it for now. You can check the complete code in my GitHub Repo: Heap Memory allocator

I strongly recommend to go through some allocator resources in internet, below few are quite interesting and informative.

Short Lecture notes

Google's memory allocator : tcmalloc docs

Thanks for reading...

Keep Learning!

Heap Memory Allocator in C Programming

PART 3

free()

calloc()

realloc()