Implementation of malloc, calloc, and realloc

[theifyppl]

I was going through old school projects and found something that might be interesting to some here: an implementation of the standard C library functions malloc, calloc, and realloc. Assuming what I found was the latest version of the code I wrote (a dicey assumption to make), the functionality should match the standard library methods exactly, and had gone through pretty extensive testing to confirm that's the case. As far as I can tell from a quick skim, the implementation is basically managing a linked-list of memory block pointers, using some OS calls to request more memory.

I don't like the styling I used to write this back then, but I'm too lazy to go back and change it.

Anyway, if anyone is interested in how those functions work under-the-hood, here ya go:

 

/*
 * The code below is a reimplementation of
 * the malloc library. It implements four
 * methods: malloc(3), calloc(3), realloc(3),
 * and free(3).
 */

#include <errno.h>
#include <stddef.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define HEAP_ALLOCATE_SIZE 64000
#define HEAP_MIN_BLOCK_SIZE 16

#define DEBUG_MAXLEN 256
#define STDERR_FD 2

/* Represents one node of the 
 * linked-list used to navigate the heap
 *
 * Designed so that sizeof(HeapHeader) is
 * a multiple of 16. uintptr_t is used for
 * integer data in order to ensure the size
 * is a multiple of 16 on both 32-bit and 
 * 64-bit machines.
 */
typedef struct HeapHeader {
   uintptr_t size; /* 4-byte ints */
   uintptr_t isFree;
   struct HeapHeader *next; /* 4-byte pointers */
   void *data;
} HeapHeader;

/* global static pointer to the head of the linked-list
 * maintaining the heap */
static HeapHeader *heapHead;

void *malloc(size_t size);
void *calloc(size_t nmemb, size_t size);
void free(void *ptr);
static size_t calcMinSizeForAllocation();
static void *reallocToPrev(HeapHeader *currHeapPtr, HeapHeader *prevHeapPtr,
  size_t newBlockSize);
static void *reallocToNext(HeapHeader *currHeapPtr, size_t newBlockSize);
static void *reallocToNew(HeapHeader *currHeapPtr, size_t newBlockSize);
static void searchListForBlock(void *ptr, HeapHeader **currHeapPtr, 
  HeapHeader **prevHeapPtr);
void *realloc(void *ptr, size_t size);

/*
 * This function attempts to allocate |size| bytes on the heap
 * and returns a pointer to the first byte. If needed, it will
 * request Heap memory from the OS via sbrk(2). It maintains
 * a linked-list structure to keep track of allocated memory.
 *
 * Returns a NULL pointer if the |size| input is 0, or if it
 * cannot allocate memory from the OS.
 */
void *malloc(size_t size) {
   
   HeapHeader *currHeapPtr = heapHead;
   HeapHeader *prevHeapPtr = NULL;
   HeapHeader *newBlock = NULL;
   HeapHeader *oldNext;
   
   size_t heapAllocateSize = HEAP_ALLOCATE_SIZE;
   size_t newBlockSize = HEAP_MIN_BLOCK_SIZE;
   size_t oldBlockSize, minSizeForAllocation;
   
   char *newHeapMemory;
   char mallocDebugOutput[DEBUG_MAXLEN];

   /* malloc(0) returns NULL */
   if (!size) {
      return NULL;
   }
   
   /* obtain new block size (must be multiple of 16) */
   while (newBlockSize < size) {
      newBlockSize += HEAP_MIN_BLOCK_SIZE;
   }
   
   /* search linked list until we reach large enough free block,
    * or until we reach the end */
   while (currHeapPtr &&
     (currHeapPtr->size < newBlockSize || !(currHeapPtr->isFree))) {
       
      /* maintain prev pointer to manipulate "next" pointers later */
      prevHeapPtr = currHeapPtr;
      currHeapPtr = currHeapPtr->next;
   }
   
   /* if we reached the end of the list without finding abort
    * suitable free block, request more memory from the OS */
   if (!currHeapPtr) {
      
      /* if requested size is greater than size we request
       * from OS, increase requested size until otherwise */
      while (heapAllocateSize < size) {
         heapAllocateSize += HEAP_ALLOCATE_SIZE;
      }
      
      /* ask for more memory from OS */
      if ((newHeapMemory = (void *)sbrk(heapAllocateSize)) == (void *)-1) {
         errno = ENOMEM;
         return NULL;
      }
      
      /* Fill header data for new block of data requested from OS */
      currHeapPtr = (HeapHeader *) newHeapMemory;
      currHeapPtr->size = heapAllocateSize - sizeof(HeapHeader);
      currHeapPtr->isFree = 1;
      currHeapPtr->next = NULL;
      currHeapPtr->data = currHeapPtr + 1;
      
      /* if this is not the first sbrk call, assign "next" ptr
       * of previous header; otherwise, assign head pointer */
      if (prevHeapPtr) {
         prevHeapPtr->next = currHeapPtr;
      }
      else {
         heapHead = currHeapPtr;
      }
   }
   
   /* save size and next of current block (before carving new
    * block of requested size) */
   oldBlockSize = currHeapPtr->size;
   oldNext = currHeapPtr->next;
   
   /* calculate the minimum number of bytes needed to
    * carve a new block out of the heap. */
   minSizeForAllocation = calcMinSizeForAllocation();
   
   /* adjust new block size if there isn't enough space
    * at the end of this block for an entire new block */
   if (oldBlockSize - newBlockSize < minSizeForAllocation) {
      newBlockSize = oldBlockSize;
   }
   else {
      /* addr of second block can be calculated from this pointer by moving
       * past this header and past the size of the new data block */
      currHeapPtr->next = (HeapHeader *)(((char*)currHeapPtr) + 
        sizeof(HeapHeader) + newBlockSize);
       
      /* move past new block to remaining space in old, larger block 
       * and fill in header data */
      newBlock = currHeapPtr->next;
      newBlock->next = oldNext;
      newBlock->size = oldBlockSize - newBlockSize - sizeof(HeapHeader);
      newBlock->isFree = 1;
      newBlock->data = newBlock + 1;
   }
   
   /* set size and free values of carved, requested block */
   currHeapPtr->size = newBlockSize;
   currHeapPtr->isFree = 0;
 
   /* IF DEBUG_MALLOC is set, print debug info */
   if (getenv("DEBUG_MALLOC")) {
      if ((snprintf(mallocDebugOutput, DEBUG_MAXLEN, 
        "MALLOC: malloc (%lu)\t=>\t(ptr=%p, size=%ld)\n", 
        (long unsigned)size, currHeapPtr->data, 
        (long)currHeapPtr->size)) >= 0) {
       
         if ((write(STDERR_FD, 
           mallocDebugOutput, strlen(mallocDebugOutput))) == -1) {
            perror("Could not output debug info.");
         }
      }
   }
 
   /* return pointer to data of new, carved block */
   return currHeapPtr->data;
}

/*
 * Performs the same function as malloc,
 * but initializes all bytes within the new
 * allocated block to 0.
 *
 * |nmemb| represents the number of items
 * to allocate memory for, and |size| is
 * the size of each item
 */
void *calloc(size_t nmemb, size_t size) {
   
   HeapHeader *newBlockPtr = NULL;
   int loopCounter;
   void *mallocData;
   char *currByte;
   char mallocDebugOutput[DEBUG_MAXLEN];
   
   /* calculate number of bytes to allocate */
   size_t numBytes = nmemb * size;
   
   /* let malloc allocate the memory block */
   mallocData = (void *)malloc(numBytes);
   
   /* if either input was 0, malloc(0) would
    * return NULL. Pass this NULL along */
   if (!mallocData) {
      return NULL;
   }
   
   /* malloc returned a pointer to the new block's data. 
    * save this position and move backward in memory to the 
    * Header data of the block */
   newBlockPtr = (HeapHeader *)((char *)mallocData - sizeof(HeapHeader));
   currByte = (char *)mallocData;
   
   /* set all allocated bytes to zero */
   for (loopCounter = 0; loopCounter < numBytes; loopCounter++) {
      *currByte++ = 0;
   }
   
   /* IF DEBUG_MALLOC is set, print debug info */
   if (getenv("DEBUG_MALLOC")) {
      if ((snprintf(mallocDebugOutput, DEBUG_MAXLEN, 
        "MALLOC: calloc (%lu, %lu)\t=>\t(ptr=%p, size=%ld)\n", 
        (long unsigned)nmemb, (long unsigned)size, newBlockPtr->data, 
        (long)newBlockPtr->size)) >= 0) {
       
         if ((write(STDERR_FD, 
           mallocDebugOutput, strlen(mallocDebugOutput))) == -1) {
            perror("Could not output debug info.");
         }
      }
   }
   
   return mallocData;
}


/* 
 * When passed a pointer to a block of data
 * previously allocated via malloc or calloc,
 * this function will mark that block as free 
 * and merge it with any adjacent free blocks.
 */
void free(void *ptr) {
   
   HeapHeader *currHeapPtr = heapHead;
   HeapHeader *prevHeapPtr = NULL;
   char mallocDebugOutput[DEBUG_MAXLEN];
   
   /* free(NULL) does nothing */
   if (!ptr) {
      return;
   }
   
   /* search linked-list for the block of memory that |ptr|
    * is pointing to */
   searchListForBlock(ptr, &currHeapPtr, &prevHeapPtr);
   
   /* if ptr not pointing to heap (search unsuccessful) */
   if (!currHeapPtr || (char *)ptr < (char *)currHeapPtr) {
      return;
   }
   
   /* set block as free */
   currHeapPtr->isFree = 1;
   
   if (currHeapPtr->next && currHeapPtr->next->isFree) {

      /* merge current block w/ next block, if both are free */
      currHeapPtr->size = currHeapPtr->size + sizeof(HeapHeader) + 
        currHeapPtr->next->size;  
      currHeapPtr->next = currHeapPtr->next->next;
   }
   
   if (prevHeapPtr && prevHeapPtr->isFree) {

      /* merge prev block w/ this block, if both are free */
      prevHeapPtr->size = prevHeapPtr->size + sizeof(HeapHeader) +
        currHeapPtr->size;
      prevHeapPtr->next = currHeapPtr->next;
   }
   
   /* IF DEBUG_MALLOC is set, print debug info */
   if (getenv("DEBUG_MALLOC")) {
      if ((snprintf(mallocDebugOutput, DEBUG_MAXLEN, 
        "MALLOC: free(%p)\n", ptr)) >= 0) {       
         if ((write(STDERR_FD, 
           mallocDebugOutput, strlen(mallocDebugOutput))) == -1) {
            perror("Could not output debug info.");
         }
      }
   }
}


/*
 * When passed a pointer to data previously allocated
 * via malloc or calloc and a new size, this function
 * reallocates the space to be the new specified size.
 * It will either shrink or expand (if possible) the
 * current block, or move the block entirely to a new,
 * suitable chunk of memory.
 */
void *realloc(void *ptr, size_t size) {
   
   HeapHeader *currHeapPtr = heapHead;
   HeapHeader *prevHeapPtr = NULL;
   HeapHeader *newBlock = NULL;
   
   void *returnPtr;
   int sizeDifference;
   size_t newBlockSize = HEAP_MIN_BLOCK_SIZE;
   size_t minSizeForAllocation;
   char mallocDebugOutput[DEBUG_MAXLEN];
   
   /* realloc(NULL, size) returns malloc(size) */
   if (!ptr) {
      return malloc(size);
   }
   
   /* realloc(ptr, 0) performs free(ptr) */
   if (ptr && !size) {
      free(ptr);
      return NULL;
   }
   
   /* search linked-list for the block of memory that |ptr|
    * is pointing to */
   searchListForBlock(ptr, &currHeapPtr, &prevHeapPtr);
   
   /* if ptr not pointing to heap (search unsuccessful) */
   if (!currHeapPtr || (char *)ptr < (char *)currHeapPtr) {
      return NULL;
   }
   
   /* calculate min number of bytes for a new block */
   minSizeForAllocation = calcMinSizeForAllocation();
   
   /* obtain new block size (multiple of 16) */
   while (newBlockSize < size) {
      newBlockSize += HEAP_MIN_BLOCK_SIZE;
   }
   
   /* same size, or not enough space for new block after carving; 
    * return the original pointer with no changes to actual block size */
   if (currHeapPtr->size >= newBlockSize && 
     currHeapPtr->size - newBlockSize < minSizeForAllocation) {
         
      return ptr;
   }
   

   /* if new size is smaller than old size, we shrink the block */
   if (currHeapPtr->size > newBlockSize) {
      
      /* calc size of new block */
      sizeDifference = currHeapPtr->size - newBlockSize - 
        sizeof(HeapHeader);
      
      /* shrink size of current block */
      currHeapPtr->size = newBlockSize;
      
      /* move to new block and fill data */
      newBlock = (HeapHeader *)(((char *)currHeapPtr) + sizeof(HeapHeader) +
        currHeapPtr->size);
      newBlock->size = sizeDifference;
      newBlock->isFree = 1;
      newBlock->data = newBlock + 1;
      
      /* update next ptrs for new block */
      newBlock->next = currHeapPtr->next;
      currHeapPtr->next = newBlock;
      returnPtr = currHeapPtr->data;
   }
   
   /* if we need to expand current block in memory */
   if (currHeapPtr->size < newBlockSize) {
      
      /* if we can merge with previous block,
       * else if we can merge with next block,
       * else move to entirely new block */
      if (prevHeapPtr && prevHeapPtr->isFree && 
        prevHeapPtr->size + currHeapPtr->size > newBlockSize) {
        
         returnPtr = reallocToPrev(currHeapPtr, prevHeapPtr, newBlockSize);
      }
      else if (currHeapPtr->next && currHeapPtr->next->isFree &&
        currHeapPtr->next->size + currHeapPtr->size > newBlockSize) {
         
         returnPtr = reallocToNext(currHeapPtr, newBlockSize);
      }
      else {
         returnPtr = reallocToNew(currHeapPtr, newBlockSize);
      }
   }
   
   /* IF DEBUG_MALLOC is set, print debug info */
   if (getenv("DEBUG_MALLOC")) {
      
      /* move back in memory to get to header data */
      currHeapPtr = (HeapHeader *)((char *)returnPtr - sizeof(HeapHeader));
      
      if ((snprintf(mallocDebugOutput, DEBUG_MAXLEN, 
        "MALLOC: realloc (%p, %lu)\t=>\t(ptr=%p, size=%ld)\n", 
        ptr, (long unsigned)size, returnPtr, 
        (long)currHeapPtr->size)) >= 0) {
       
         if ((write(STDERR_FD, 
           mallocDebugOutput, strlen(mallocDebugOutput))) == -1) {
            perror("Could not output debug info.");
         }
      }
   }
   
   return returnPtr;
}


/* calculate the minimum number of bytes needed to
 * carve a new block out of the heap. This depends
 * on sizeof(HeapHeader), which will be different
 * for 32-bit and 64-bit machines */
static size_t calcMinSizeForAllocation() {
   return sizeof(HeapHeader) + HEAP_MIN_BLOCK_SIZE;
}


/*
 * Expands the current block to merge with the previous
 * block, effectively reallocating more space for the block.
 */
static void *reallocToPrev(HeapHeader *currHeapPtr, HeapHeader *prevHeapPtr,
  size_t newBlockSize) {
   
   HeapHeader *oldNext = NULL;
   int sizeDifference, loopCounter;
   size_t oldBlockSize, minSizeForAllocation;
   char *newDataPointer, *oldDataPointer;
   
   /* check input validity. Ptrs cannot be NULL, prev must actually be
    * the block directly before |currHeapPtr|, and prev must be free */
   if (!currHeapPtr || !prevHeapPtr || prevHeapPtr->next != currHeapPtr ||
     !prevHeapPtr->isFree) {
      return NULL;
   }
   
   /* save original block size and calculate the size of the new,
    * carved block */
   sizeDifference = prevHeapPtr->size + currHeapPtr->size - newBlockSize;
   oldBlockSize = currHeapPtr->size;
   
   /* calculate min number of bytes for a new block */
   minSizeForAllocation = calcMinSizeForAllocation();
   
   /* if not enough room for new block, just point merged block to
    * the next block on the heap */
   if (sizeDifference + sizeof(HeapHeader) < minSizeForAllocation) {
      prevHeapPtr->size = prevHeapPtr->size + currHeapPtr->size
        + sizeof(HeapHeader);
      prevHeapPtr->next = currHeapPtr->next;
   }
   else {
      /* assign new block size to merged block, and save pointer
       * to block ahead of current one */
      prevHeapPtr->size = newBlockSize;
      oldNext = currHeapPtr->next;
   }
   
   prevHeapPtr->isFree = 0;
   
   /* copy data to new block */
   newDataPointer = (char *)prevHeapPtr->data;
   oldDataPointer = (char *)currHeapPtr->data;
   for (loopCounter = 0; loopCounter < oldBlockSize; 
     loopCounter++) {
      *newDataPointer++ = *oldDataPointer++;
   }
   
   /* if there was a block carved after merge, initialize it and
    * fill header data */
   if (sizeDifference + sizeof(HeapHeader) >=  minSizeForAllocation) {
      prevHeapPtr->next = (HeapHeader *)(((char *)prevHeapPtr->data) + 
        prevHeapPtr->size);
      currHeapPtr = prevHeapPtr->next;
      currHeapPtr->size = sizeDifference;
      currHeapPtr->isFree = 1;
      currHeapPtr->next = oldNext;
      currHeapPtr->data = currHeapPtr + 1;
   }
  
   return prevHeapPtr->data;
}


/*
 * Expands the current block to merge with the next
 * block, effectively reallocating more space for the block.
 */
static void *reallocToNext(HeapHeader *currHeapPtr, size_t newBlockSize) {
   
   HeapHeader *oldNext = NULL;
   int sizeDifference;
   size_t minSizeForAllocation;
   
   /* invalid inputs if current or next block don't exist, or if
    * the next block is not free, or if the requested size == 0 */
   if (!currHeapPtr || !currHeapPtr->next || !currHeapPtr->next->isFree ||
     !newBlockSize) {
      return NULL;
   }
   
   /* save original block size and calculate the size of the new,
    * carved block */
   sizeDifference = currHeapPtr->size + 
   currHeapPtr->next->size - newBlockSize;
  
   /* calculate min number of bytes for a new block */
   minSizeForAllocation = calcMinSizeForAllocation();
  
   /* if not enough space to carve new block after merge, use entire
    * space for merged block */
   if (sizeDifference + sizeof(HeapHeader) < minSizeForAllocation) {
      currHeapPtr->size = currHeapPtr->size + currHeapPtr->next->size +
        sizeof(HeapHeader);
      currHeapPtr->next = currHeapPtr->next->next;
   }
   else {
      /* set merged block size, initialize new carved block,
       * and fill header data */
      currHeapPtr->size = newBlockSize;
      oldNext = currHeapPtr->next->next;
      currHeapPtr->next = (HeapHeader *)(((char *)currHeapPtr->data) +
        currHeapPtr->size);
      currHeapPtr->next->size = sizeDifference;
      currHeapPtr->next->isFree = 1;
      currHeapPtr->next->next = oldNext;
      currHeapPtr->next->data = currHeapPtr->next + 1;
   }

   return currHeapPtr->data;
}

/*
 * Expands the current block by allocating an entirely new
 * block and copying the data to the new location.
 */
static void *reallocToNew(HeapHeader *currHeapPtr, size_t newBlockSize) {
   
   HeapHeader *newBlock = NULL;
   char *newDataPointer, *oldDataPointer;
   size_t oldBlockSize;
   int loopCounter;
   
   /* if current block doesn't exist or size == 0, invalid inputs */
   if (!currHeapPtr || !newBlockSize) {
      return NULL;
   }
   
   /* check if malloc for new space succeeds */
   if (!(newBlock = (HeapHeader *)malloc(newBlockSize))) {
      return NULL;
   }
   
   /* Copy over data to new block */
   newDataPointer = (char *)newBlock;
   oldDataPointer = (char *)currHeapPtr->data;
   oldBlockSize = currHeapPtr->size;
   for (loopCounter = 0; loopCounter < oldBlockSize; 
     loopCounter++) {
      *newDataPointer++ = *oldDataPointer++;
   }
   
   /* free old block */
   free(currHeapPtr->data);
   return newBlock;
}


/* Searches linked-list for the block of heap memory that |ptr|
 * is pointing to. Traverses linked-list while keeping track of
 * the current and previous nodes, which are returned via
 * pointers */
static void searchListForBlock(void *ptr, HeapHeader **currHeapPtr, 
  HeapHeader **prevHeapPtr) {
   
   /* keep traversing linked list while ptr is ahead of the current
    * block in memory but not within the size of the 
    * current block */
   while (*currHeapPtr && (char *)ptr >= (char *)(*currHeapPtr) && 
     (char *)ptr - (char *)(*currHeapPtr) > 
     sizeof(HeapHeader) + (*currHeapPtr)->size) {
      
      *prevHeapPtr = *currHeapPtr;
      *currHeapPtr = (*currHeapPtr)->next;
   }
}

 

Edited March 22, 2019 by theifyppl

[WarFox]

Just finished up doing a rough overview of C in one of the classes I am taking. Pointers to pointers still get me, especially when passing them to functions.

[theifyppl]

For sure! There was a ton of that in this class I was taking. It helps me to think about the actual memory layout (4 byte pointer pointing to another memory block, which may or may not be another 4 byte pointer). Drawing pictures of the memory blocks was an absolute necessity in the later projects we did.

[WarFox]

That makes sense, I should check out some diagrams that give a visual of pointers to pointers. I was able to do my assignment, but with a lot of help from stack exchange.