Needing advice for implementing malloc and free in C


For school, I need to write a program that uses my own implementation of malloc and free. I need to be able to report on all the chunks of memory in my 'heap', whether it's allocated or not. I feel like I've written good code to do so, but evidently not. The first few times I ran it, the report kept reporting on the same address forever. While trying to debug that, there came a point that the program wouldn't even let me start allocate space to use as my 'heap', it would just get a segmentation fault and quit. Any pointers on where I'm going wrong, or even to clean up my code at all, would be super helpful.

#include <unistd.h>
#include <assert.h>
#include <stdio.h>

#define WORDSIZE 8
#define ALLOCMAGIC 0xbaddecaf
#define FREEMAGIC 0xdeadbeef

typedef struct __header_t {
    size_t size;
    int magic;
} header_t;

typedef struct __node_t {
    size_t size;
    struct __node_t *next;
} node_t;

node_t *head = NULL;

// Find the free node that occurs just before the given node.
node_t *findLastFree(node_t * node) {

    // Initialize some pointers to traverse the free node linked list;
    node_t *lastFree = head;
    node_t *nextFree = lastFree->next;

    // Traverse linked list until the last node's pointer is pointed to NULL,
    // meaning the end of the list.
    while (nextFree != NULL) {

        // Check if target node is less than the next node, meaning the target node
        // is between last and next.  If so, then return last node.
        if (node < nextFree) {
            return lastFree;

        lastFree = nextFree;
        nextFree = lastFree->next;

    // If we have reached the end of the list and the target node is still greater
    // than the last node, return last node.
    return lastFree;

// If the given pointer is allocated, deallocate the space and coalesce the free
// node list.
void myFree(void *ptr) {

    // Initialize some free node pointers and assert that the given pointer is
    // the beginning of allocated space.
    node_t *lastFree;
    node_t *nextFree;
    node_t *newFree;
    header_t *block = ((header_t *) ptr) - 1;
    assert(block->magic == ALLOCMAGIC);

    // Set this block's signal to free space
    block->magic = FREEMAGIC;

    // Typecast the block into a free node and set it's size.
    size_t size = block->size + sizeof(header_t);
    newFree = (node_t *) block;
    newFree->size = size;

    // Check if node is before the first free node.  If so set the new node as
    // the new head.  If not, then handle node as it occurs after head.
    if (newFree < head) {

        nextFree = head;

        // Check if new node ends at the start of head.  If so, merge them
        // into a single free node.  Else point the new node at the previous head.
        // Either way, set new free as the new head.
        if ((newFree + newFree->size) == head) {
            newFree->next = head->next;
            newFree->size = newFree->size + head->size;
        } else {
            newFree->next = head;
        head = newFree;
    } else {

        // Set the free nodes for before and after the new free node.
        lastFree = findLastFree(newFree);
        nextFree = lastFree->next;

        // Check if new node is the last node.  If so, point the previous final
        // node at the new node and point the new node at NULL.
        if (nextFree == NULL) {

            lastFree->next = newFree;
            newFree->next = NULL;

        // Check if end of new node is touching next node.  If so, merge them
        // into a single free node.  Else point new free and next free.
        if ((newFree + newFree->size) == nextFree) {
            newFree->next = nextFree->next;
            newFree->size = newFree->size + nextFree->size;
        } else {
            newFree->next = nextFree;

        // Check if start of new node is touching last free node.  If so, merge
        // them into a single free node.  Else point last's next to new free.
        if ((lastFree + lastFree->size) == newFree) {
            lastFree->next = newFree->next;
            lastFree->size = lastFree->size + newFree->size;
        } else {
            lastFree->next = newFree;

// Split the given free node to fit the given size.  Create a new node at the 
// remainder and rearrange the free list to accomodate.
void splitBlock(node_t *node, size_t size) {

    // Create a new pointer at the end of the requested space.
    void *newBlock = node + size;

    // Set the bits of the new space as if it were allocated then freed.
    header_t *hptr = (header_t *) newBlock;
    hptr->size = (node->size - size - sizeof(header_t));
    hptr->magic = FREEMAGIC;

    // Typecast the new space into a node pointer.  Reinsert it into the free
    // node list.
    node_t *newFree = (node_t *) newBlock;
    newFree->size = node->size - size;
    newFree->next = node->next;
    node_t *lastFree = findLastFree(newFree);
    lastFree->next = newFree;

// Find a free node that can fit the given size.  Split the node so no space is 
// wasted.  If no node can fit requested size, increase the heap size to accomodate.
void *findFirstFit(size_t size) {

    // Create a node pointer to traverse the free node list.
    node_t *node = head;

    // Traverse the list until the end is reached.
    while(node != NULL) {

        // Check if the node can accomodate the requested size.
        if (node->size >= size) {

            // Split the current node at the requested size and return a pointer
            // to the start of the requested space.
            splitBlock(node, size);
            return (void *) node;
        node = node->next;

    // No free space could fit requested size, so request more space at the end
    // of the heap.
    void *newspace = sbrk(size);
    assert(newspace >= 0);

    return newspace;

// Allocate a block of space for the given size and return a pointer to the start
// of the freed space.

void *myMalloc(size_t need) {

    // Round the given size up to the next word size.  Add the size of a header to
    // the amount actually needed to allocate.
    need = (need + WORDSIZE - 1) & ~(WORDSIZE - 1);
    size_t actual = need + sizeof(header_t);

    // Find a free node that can accomodate the given size.  Check it is valid.
    void *firstfit = findFirstFit(actual);
    assert(firstfit >= 0);

    // Create a header for the newly allocated space.
    header_t *hptr = (header_t *) firstfit;
    hptr->magic = ALLOCMAGIC;
    hptr->size = need;

    return (void *) (hptr + 1);

// Print a report on the space starting at the given pointer.  Return a pointer to
// the start of the next block of space.
void *reportAndGetNext(void *ptr) {

    void *nextptr;
    header_t *hptr = (header_t *) ptr;

    // Check if the pointer is pointing to allocated space.
    if (hptr->magic == ALLOCMAGIC) {

        // Report the characteristics of the current block.
        printf("%p is ALLOCATED starting at %p and is %zd bytes long.\n", hptr, (hptr + 1), hptr->size);

        // Set the next pointer to be returned.
        nextptr = hptr + hptr->size + sizeof(header_t);
    } else {

        // Cast the pointer as a free node.  Set the next pointer to be returned.
        node_t *free = (node_t *) ptr;
        nextptr = free + free->size;

        // Report the characteristics of the current block.
        printf("%p is FREE for %zd bytes.\n", hptr, free->size);
    return nextptr;

// Report on all blocks of space contained within the heap space, starting at the 
// given pointer.
void report(void* startheap) {

    void *ptr = startheap;
    void *end = sbrk(0);
    int count = 50;

    printf("Current Status of Heap:\n");

    while (ptr != NULL && count > 0) {
        ptr = reportAndGetNext(ptr);
        count = count - 1;

    printf("Heap Length: %zd \n", (end - startheap));


int main(void) {

    void *start = sbrk(4096);
    assert(start >= 0);
    head = (node_t *) start;
    head->size = 4096;
    head->next = NULL;

    printf("Allocating block 1");
    void *ptr1 = myMalloc(26);
    void *ptr2 = myMalloc(126);

    return 0;
asked on Stack Overflow Oct 11, 2018 by ScottyD

1 Answer


The first obvious error I see is with pointer arithmentic. SplitBlock is trying to split size bytes from the front of a block, but when you do:

void splitBlock(node_t *node, size_t size) {
    // Create a new pointer at the end of the requested space.
    void *newBlock = node + size;

Your newBlock pointer is actually size * sizof(node_t) bytes into the block -- which may well be past the end of the block. You need to cast node to a char * before doing pointer arithmetic with it if you want byte offsets. However, you may then run into alignment issues...

answered on Stack Overflow Oct 12, 2018 by Chris Dodd

User contributions licensed under CC BY-SA 3.0