malloc causing segmentation fault by _int_malloc

Question

I have a tree structure which I am adding a large amount of nodes too. The number of times this is done (tree cleaned between runs) and the number of nodes is given as a command line argument. For numbers of nodes roughly < 6000 and any number of runs the program performs as expected. However when the number of nodes exceeds this and the number of runs exceeds a low number around 50 the program causes a segmentation fault.

    Program received signal SIGSEGV, Segmentation fault.
    _int_malloc (av=0x7ffff7201740 <main_arena>, bytes=112) at malloc.c:3570
    3570    malloc.c: No such file or directory.

Using backtrace this tracks too

#0  _int_malloc (av=0x7ffff7201740 <main_arena>, bytes=112) at malloc.c:3570
#1  0x00007ffff6ecbfb5 in __GI___libc_malloc (bytes=112) at malloc.c:2924
#2  0x0000000000401a99 in createTreeForQuad (quad=...) at cs257.c:217
#3  0x0000000000401b3a in addQuadsToTree (tree=tree@entry=0x2f965c8) at cs257.c:230
#4  0x0000000000401dec in addBody (tree=tree@entry=0x2f965c8, body=...) at cs257.c:292
#5  0x0000000000402146 in addBodyToCorrectQuad (body=..., tree=tree@entry=0x2f961c8) at cs257.c:245
#6  0x0000000000401eaf in addBody (tree=tree@entry=0x2f961c8, body=...) at cs257.c:296
#7  0x0000000000402146 in addBodyToCorrectQuad (body=..., tree=tree@entry=0x2f95dc8) at cs257.c:245

Note that the addBody -> addBodyToCorrectQuad -> addBody recursion happens a large number of times at high number of nodes. The code with the malloc which fails is below.

Tree *createTreeForQuad(Quad quad) {
Tree *tree;
tree = (Tree *)malloc(sizeof*tree);
if (tree != NULL){
    tree->quad = quad;
    tree->internal = 0;
    tree->bodyEmpty = 1;
    return tree;
}else{
   printf("\n ------------------------------------ MALLOC FAILED----------------------------------------");
    }
}

The code I use to free the tree is as follows, with it being called on the root node and the internal flag being set to 0 when the tree is a leaf.

void cleanTree(Tree **tree) {
    if((*tree)->internal == 0) {
        free(*tree);
    }
    else{
        cleanTree(&((*tree)->NE));
        cleanTree(&((*tree)->SE));
        cleanTree(&((*tree)->SW));
        cleanTree(&((*tree)->NW));
        cleanTree(&((*tree)->NE1));
        cleanTree(&((*tree)->NW1));
        cleanTree(&((*tree)->SE1));
        cleanTree(&((*tree)->SW1));
        free(*tree);
    }
}

The tree struct looks like this

typedef struct Tree Tree;
struct Tree {
    Body body;
    Quad quad;
    Tree *NE;
    Tree *NW;
    Tree *SE;
    Tree *SW;
    Tree *NE1;
    Tree *NW1;
    Tree *SE1;
    Tree *SW1;
    int internal;
    int bodyEmpty;
};

The code for adding Bodys to the tree is as follows with addBodyToCorrectQuad calling addBody on the quad that the body exists within.

void addBody(Tree **tree, Body body) {
   if( (*tree)->bodyEmpty == 1) { 
        (*tree)->body = body;
        (*tree)->bodyEmpty = 0;
    }
    else {
        if((*tree)->internal) {
            (*tree)->body = combineBody((*tree)->body, body);
            addBodyToCorrectQuad(body, tree);
            //printf("B\n");
        }
        else{
            (*tree)->internal = 1;   /
            addQuadsToTree(tree);
            //printf("%f",((*tree)->NW)->quad.x);
            addBodyToCorrectQuad((*tree)->body, tree);
            (*tree)->body = combineBody((*tree)->body, body);
            addBodyToCorrectQuad(body, tree);
            //printf("C\n");
        }
    }
}

Solution

You have heap corruption somewhere -- someone is running off the end of an array or dereferencing an invalid pointer or using some object after it has been freed.

Try using valgrind or some other memory debugging tool to narrow down where the problem is.