C Program sometimes giving segfault

Question

For some reason, my program sometimes works correctly, and sometimes just ends in a segfault. I am trying to create an implementation of malloc. If I start off with a size of 5000, and I do malloc(1000), I expect the remaining memory size to be 3984 (due to the size of the memory entry as well).

When I output the memory remaining with printf, it sometimes prints 3984 and sometimes just ends in a Segmentation Fault. Any help would be appreciated.

#include "malloc-free-impl.h"

static char memArr[5000];
static char* memArrPtr = &memArr;
static MemEntryPtr head = NULL;

void* custom_malloc(int size) {
    if (head == NULL) {
        head = (MemEntryPtr) memArrPtr;
        head->prev = NULL;
        head->next = NULL;
        head->isFree = 1;
        head->size = sizeof(memArr) - sizeof(head);
    }

    MemEntryPtr curr = head;
    while (curr->isFree != 1 && curr->size > size + sizeof(struct MemEntry)) {
        curr = curr->next;
    }

    if ((curr->size - (size)) > sizeof(struct MemEntry)) {
        MemEntryPtr newMemEntry = (MemEntryPtr) (&curr + sizeof(struct MemEntry) + size);
        newMemEntry->prev = curr;
        newMemEntry->next = NULL;
        newMemEntry->isFree = 1;
        newMemEntry->size = curr->size - (size + sizeof(newMemEntry));

        printf("%d\n", newMemEntry->size);

        curr->isFree = 0;
        curr->next = newMemEntry;

        return newMemEntry;
    }

    return NULL;
}

void* custom_free(MemEntryPtr memBlock) {
    memBlock->isFree = 1;
    return NULL;
}

int main(int argc, char** argv) {
    MemEntryPtr node = (MemEntryPtr) custom_malloc(1000);
    return 1;
}

Answer 1

malloc-free-impl.h ( minimal stub to replicate issue )

#ifndef _malloc_free_impl_
#define _malloc_free_impl_

struct MemEntry
{
    struct MemEntry *prev, *next;
      int isFree, size;
};

typedef struct MemEntry * MemEntryPtr;

#endif

what does valgrind say

$ gcc -g test.c -o test
test.c:8:26: warning: initialization from incompatible pointer type [enabled by default]
 static char* memArrPtr = &memArr;
                          ^
$ valgrind ./test
==30474== Memcheck, a memory error detector
==30474== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==30474== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==30474== Command: ./test
==30474== 
==30474== Invalid write of size 8
==30474==    at 0x4005FF: custom_malloc (test.c:27)
==30474==    by 0x4006A3: main (test.c:49)
==30474==  Address 0xfff001f90 is not stack'd, malloc'd or (recently) free'd
==30474== 
==30474== 
==30474== Process terminating with default action of signal 11 (SIGSEGV)
==30474==  Access not within mapped region at address 0xFFF001F90
==30474==    at 0x4005FF: custom_malloc (test.c:27)
==30474==    by 0x4006A3: main (test.c:49)
==30474==  If you believe this happened as a result of a stack
==30474==  overflow in your program's main thread (unlikely but
==30474==  possible), you can try to increase the size of the
==30474==  main thread stack using the --main-stacksize= flag.
==30474==  The main thread stack size used in this run was 8388608.
==30474== 
==30474== HEAP SUMMARY:
==30474==     in use at exit: 0 bytes in 0 blocks
==30474==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==30474== 
==30474== All heap blocks were freed -- no leaks are possible
==30474== 
==30474== For counts of detected and suppressed errors, rerun with: -v
==30474== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)

valgrind is objecting to an invalid write at line 27 :

25   if ((curr->size - (size)) > sizeof(struct MemEntry)) {
26     MemEntryPtr newMemEntry = (MemEntryPtr) (&curr + sizeof(struct MemEntry) + size);
27     newMemEntry->prev = curr;

in particular, its saying the memory address newMemEntry->prev is invalid.

tracing back, this memory address should be valid as long as newMemEntry is a valid MemEntryPtr address.

But the assignment of newMemEntry is

• adding sizes aligned to sizeof char
• applying this pointer arithmetic on base pointer of type ( MemEntryPtr * ) instead of char * to match char-aligned sizes

Changing the code to perform pointer arithmetic on base char * as all the sizeofs are written with that in mind, we get :

25   if ((curr->size - (size)) > sizeof(struct MemEntry)) {
26     MemEntryPtr newMemEntry = (MemEntryPtr) ((char *)curr + sizeof(struct MemEntry) + size);
27     newMemEntry->prev = curr;

and checking this change with valgrind :

valgrind recheck

$ gcc -g test.c -o test
test.c:8:26: warning: initialization from incompatible pointer type [enabled by default]
 static char* memArrPtr = &memArr;
                          ^
$ valgrind ./test
==1212== Memcheck, a memory error detector
==1212== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==1212== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==1212== Command: ./test
==1212== 
3984
==1212== 
==1212== HEAP SUMMARY:
==1212==     in use at exit: 0 bytes in 0 blocks
==1212==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==1212== 
==1212== All heap blocks were freed -- no leaks are possible
==1212== 
==1212== For counts of detected and suppressed errors, rerun with: -v
==1212== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

memory usage now ok - and no segfault