0

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);
    report(start);
    myFree(ptr1);
    myFree(ptr2);

    return 0;
}
ScottyD
  • 25
  • 3
  • 2
    Note that you should not create function, variable, tag or macro names that start with an underscore, in general. [C11 §7.1.3 Reserved identifiers](https://port70.net/~nsz/c/c11/n1570.html#7.1.3) says (in part): — _All identifiers that begin with an underscore and either an uppercase letter or another underscore are always reserved for any use. — All identifiers that begin with an underscore are always reserved for use as identifiers with file scope in both the ordinary and tag name spaces._ See also [What does double underscore (`__const`) mean in C?](https://stackoverflow.com/a/1449301) – Jonathan Leffler Oct 11 '18 at 23:39
  • @JonathanLeffler: If the goal is to write a library to allow a freestanding implementation to be used as a hosting implementation for purposes of running other programs, then the library itself would essentially become *part* of the implementation used by those other programs. Library private declarations that need to be included within library headers (e.g. to make macros work) that don't start with underscores will risk collisions with names used in client code. – supercat Oct 11 '18 at 23:44
  • question #1 : did you try to debug it with your debugger? – pm100 Oct 11 '18 at 23:45
  • @supercat: The 'in general' comment is in there to allow for such exceptions. If you know enough to quibble, you can make your own mind up about whether to use names reserved for the implementation. If you don't know, then avoiding names starting with underscore is simple and effective advice (or avoiding names starting double underscore or underscore and a capital letter). – Jonathan Leffler Oct 11 '18 at 23:45
  • @JonathanLeffler: Fair enough. I thought it worth mentioning that creation of library code is an exception to that principle, since *that's what the OP is doing*. – supercat Oct 11 '18 at 23:47
  • @ScottyD using `-fsanitize=address` and `-g` it shows me your segfault is at line 154 so I guess in the `node->size` access. – nullp0tr Oct 11 '18 at 23:54
  • Look sgood (too lazy to debug) Hint: use `for()`loops. Just for sanity. Plus: your `void myFree(void *ptr) {}` function could be too large to manage. – wildplasser Oct 11 '18 at 23:56
  • @nullp0tr You're right, it's at that line that the seg fault happens. Curiously, however, I inserted print statements to help me see what I'm dealing with. I'm able to use myMalloc once and on the second use is when I get segmentation fault. But I have a print statement right before the `if (node->size >= size)` where I print `node->size`. No problem. So I have no clue where the error is coming from. – ScottyD Oct 12 '18 at 01:25
  • You may benefit from the awkwardly written, but good basic introduction [Malloc Tutorial](https://github.com/zyfjeff/C-HOW-TO/blob/master/c-malloc/Malloc_tutorial.pdf) Pay careful attention if you are implementing on a 64-bit box, as the tutorial was written for a 32-bit implementation (you can adapt for 64-bit relatively easily) – David C. Rankin Oct 12 '18 at 06:41

1 Answers1

0

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...

Chris Dodd
  • 119,907
  • 13
  • 134
  • 226