Why am I getting this double free or corrupted backtrack error in C?

Question

I am trying to print a tree I build to a file in preorder, and I keep getting this error. I am pretty new to C so I am lost. I tried printing statements and implementing if-else statements returning from the function if the node is NULL, but it still is not working. The code works perfectly for upto 19 nodes in the tree, but it does not work for 199, 1999, and 19999 nodes. I also tried using valgrind but I am having issues understanding the messages valgrind puts out. The code I use is:

The code is :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "stack.h"
#include <errno.h>

extern int errno;

void preprint(treenode *node, FILE *fpw)
{
    if (node == NULL)
    {
        return;
    }
    int i = 0;
    int flagsink = node->flagsink;
    if (node != NULL)
    {
        switch (flagsink)
        {
        case 1:
            fprintf(fpw, "%d(%le)\n", node->label, node->sinkCap);
            //  printf("here1\n");
            //printf("Leaf printed: %d(%le)\n", node->label, node->sinkCap);
            break;
        case 0:
            fprintf(fpw, "(%le %le)\n", node->leftl, node->rightl);
            //  printf("here\n");
            //printf("non leaf printed: (%le %le)\n", node->leftl, node->rightl);
            break;
        }
        //printf("line printed\n");
        //if (node->left == NULL){
        //  printf("\nError is HERE\n");
        //  return;
        //}
        preprint(node->left, fpw);
        //if (node->right == NULL){
        //  printf("\nError is HERE\n");
        //  return;
        //}
        //else{
        preprint(node->right, fpw);
        //}
    }
}

void preprint2(treenode *node, FILE *fpw2)
{
    if (node == NULL)
    {
        return;
    }
    int flagsink = node->flagsink;
    if (node != NULL)
    {
        int i1, i2;
        double res1, cap1, res2, cap2;
        switch (flagsink)
        {
        case 1:
            //int i;
            i1 = node->label;
            //double res, cap;
            res1 = node->nres;
            cap1 = node->capacitance;
            fwrite(&i1, 2, sizeof(int), fpw2);
            fwrite(&res1, 2, sizeof(double), fpw2);
            fwrite(&cap1, 2, sizeof(double), fpw2);
            printf("here3\n");
            //printf("Leaf res printed: %d%le%le\n", node->label, node->nres, node->capacitance);
            break;
        case 0:
            //int i;
            //double res, cap;
            i2 = -1;
            res2 = node->nres;
            cap2 = node->capacitance;
            fwrite(&i2, 2, sizeof(int), fpw2);
            fwrite(&res2, 2, sizeof(double), fpw2);
            fwrite(&cap2, 2, sizeof(double), fpw2);
            printf("here4\n");
            //fwrite(fpw, "(%d%le%le)\n", -1, node->nres, node->capacitance);
            //printf("non leaf res printed: (%d %le %le)\n", -1, node->nres, node->capacitance);
            break;
        }
        preprint2(node->left, fpw2);
        preprint2(node->right, fpw2);
    }
    return;
}

void calc_cap(treenode *root, double sourceres, double unitres, double unitcap)
{
    if (root == NULL)
    {
        return;
    }
    if (root != NULL)
    {
        int flagsink = root->flagsink;
        if (root->rflag == 1)
        {
            root->nres = sourceres;
            root->capacitance = (((root->leftl) * unitcap) / 2) + (((root->rightl) * unitcap) / 2);
        }
        else
        {
            switch (flagsink)
            {
            case 1:
                root->nres = root->parent * unitres;
                root->capacitance = (((root->parent) * unitcap) / 2) + root->sinkCap;
                break;
            case 0:
                root->nres = root->parent * unitres;
                root->capacitance = (((root->leftl) * unitcap) / 2) + (((root->rightl) * unitcap) / 2) + (((root->parent) * unitcap) / 2);
            }
        }
    }
}

void bt_build(FILE *fp, FILE *fpw, FILE *fpw2)
{
    double sourceres;
    double unitres;
    double unitcap;
    //char ch;
    int errnum;
    int stack_size = 1000;
    rewind(fp);
    printf("here is okay\n");
    stnode *stack = NULL;

    stack = cr_stack(stack_size);
    printf("Stack is allocated\n");
    if (stack == NULL)
    {
        errnum = errno;
        fprintf(stderr, "Stack build function failed: %s\n", strerror(errnum));
        return;
    }
    //stnode *stack = NULL;
    //stack = malloc(sizeof(stnode));
    //if(stack == NULL){
    //  printf("Mallocing error\n");
    //}
    printf("Try this\n");
    treenode *right;
    treenode *left;
    double leftl;
    double rightl;
    double sinkCap;
    int label;

    if (fscanf(fp, "%le %le %le\n", &sourceres, &unitres, &unitcap) == 3)
    {
        printf("here\n");
        while (!feof(fp))
        {
            //ch = fgetc(fp);
            //if(ch != '('){
            if (fscanf(fp, "(%le %le)\n", &leftl, &rightl) == 2)
            {
                //int value = fscanf(fp, "%le %le)\n", &leftl, rightl);
                int flagsink = 0;
                //printf("(%le %le)\n", leftl, rightl);
                treenode *placeholder = NULL;
                //int value = fscanf(fp, "%le %le)\n", &leftl, rightl);
                right = pop(stack);
                left = pop(stack);
                placeholder = newNode(0, 0, leftl, rightl, left, right, flagsink);
                right->parent = placeholder->rightl;
                left->parent = placeholder->leftl;
                push(stack, placeholder);
            }
            else if (fscanf(fp, "%d(%le)\n", &label, &sinkCap) == 2)
            {
                //printf("%d(%le)\n", label, sinkCap);
                //fseek(fp, -1L, SEEK_CUR);
                int flagsink = 1;
                treenode *placeholder = NULL;
                //int value = fscanf(fp, "%d(%le)\n", &label, &sinkCap);
                placeholder = newNode(label, sinkCap, 0, 0, NULL, NULL, flagsink);

                push(stack, placeholder);
            }
            else
            {
                break;
            }
        }
    }

    treenode *root = NULL;
    root = pop(stack);
    preprint(root, fpw);
    root->parent = sourceres;
    root->rflag = 1;
    //calc_cap(root, sourceres, unitres, unitcap);
    printf("\nBACKTRACK\n");
    //preprint2(root, fpw2);

    destroy(root);

    printf("\nTree destroyed\n");
    return;
}

void destroy(treenode *root)
{
    if (root == NULL)
    {
        return;
    }
    free(root);
    destroy(root->left);
    destroy(root->right);
}

Valgrind gives me the following message:

 ==157624== Invalid read of size 8
==157624==    at 0x40111D: destroy (solution.c:192)
==157624==    by 0x401128: destroy (solution.c:192)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x4010EC: bt_build (solution.c:181)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==  Address 0x520ce40 is 16 bytes inside a block of size 88 free'd
==157624==    at 0x4C2B06D: free (vg_replace_malloc.c:540)
==157624==    by 0x401118: destroy (solution.c:191)
==157624==    by 0x401128: destroy (solution.c:192)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x4010EC: bt_build (solution.c:181)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==  Block was alloc'd at
==157624==    at 0x4C29F73: malloc (vg_replace_malloc.c:309)
==157624==    by 0x4009F3: newNode (stack.c:28)
==157624==    by 0x400FC7: bt_build (solution.c:153)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==
==157624== Invalid read of size 8
==157624==    at 0x40112D: destroy (solution.c:193)
==157624==    by 0x401128: destroy (solution.c:192)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x4010EC: bt_build (solution.c:181)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==  Address 0x520ce38 is 8 bytes inside a block of size 88 free'd
==157624==    at 0x4C2B06D: free (vg_replace_malloc.c:540)
==157624==    by 0x401118: destroy (solution.c:191)
==157624==    by 0x401128: destroy (solution.c:192)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x4010EC: bt_build (solution.c:181)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==  Block was alloc'd at
==157624==    at 0x4C29F73: malloc (vg_replace_malloc.c:309)
==157624==    by 0x4009F3: newNode (stack.c:28)
==157624==    by 0x400FC7: bt_build (solution.c:153)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==
==157624== Invalid read of size 8
==157624==    at 0x40112D: destroy (solution.c:193)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x4010EC: bt_build (solution.c:181)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==  Address 0x520d338 is 8 bytes inside a block of size 88 free'd
==157624==    at 0x4C2B06D: free (vg_replace_malloc.c:540)
==157624==    by 0x401118: destroy (solution.c:191)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x4010EC: bt_build (solution.c:181)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==  Block was alloc'd at
==157624==    at 0x4C29F73: malloc (vg_replace_malloc.c:309)
==157624==    by 0x4009F3: newNode (stack.c:28)
==157624==    by 0x400FC7: bt_build (solution.c:153)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==
==157624== Invalid read of size 8
==157624==    at 0x40111D: destroy (solution.c:192)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x4010EC: bt_build (solution.c:181)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==  Address 0x520d2a0 is 16 bytes inside a block of size 88 free'd
==157624==    at 0x4C2B06D: free (vg_replace_malloc.c:540)
==157624==    by 0x401118: destroy (solution.c:191)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x4010EC: bt_build (solution.c:181)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==  Block was alloc'd at
==157624==    at 0x4C29F73: malloc (vg_replace_malloc.c:309)
==157624==    by 0x4009F3: newNode (stack.c:28)
==157624==    by 0x400FC7: bt_build (solution.c:153)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==
==157624== Invalid read of size 8
==157624==    at 0x40112D: destroy (solution.c:193)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x4010EC: bt_build (solution.c:181)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==  Address 0x520d298 is 8 bytes inside a block of size 88 free'd
==157624==    at 0x4C2B06D: free (vg_replace_malloc.c:540)
==157624==    by 0x401118: destroy (solution.c:191)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x401138: destroy (solution.c:193)
==157624==    by 0x4010EC: bt_build (solution.c:181)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==  Block was alloc'd at
==157624==    at 0x4C29F73: malloc (vg_replace_malloc.c:309)
==157624==    by 0x4009F3: newNode (stack.c:28)
==157624==    by 0x400FC7: bt_build (solution.c:153)
==157624==    by 0x4011EA: main (pa3.c:25)
==157624==

Tree destroyed
==157624==
==157624== HEAP SUMMARY:
==157624==     in use at exit: 8 bytes in 1 blocks
==157624==   total heap usage: 203 allocs, 202 frees, 19,224 bytes allocated
==157624==
==157624== LEAK SUMMARY:
==157624==    definitely lost: 8 bytes in 1 blocks
==157624==    indirectly lost: 0 bytes in 0 blocks
==157624==      possibly lost: 0 bytes in 0 blocks
==157624==    still reachable: 0 bytes in 0 blocks
==157624==         suppressed: 0 bytes in 0 blocks
==157624== Rerun with --leak-check=full to see details of leaked memory
==157624==
==157624== For lists of detected and suppressed errors, rerun with: -s
==157624== ERROR SUMMARY: 796 errors from 35 contexts (suppressed: 0 from 0)

The error is:

*** Error in `a.out': double free or corruption (out): 0x0000000000f746f0 ***
======= Backtrace: =========
/lib64/libc.so.6(+0x81299)[0x7f0b8ae97299]
a.out[0x401119]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x401129]
a.out[0x4010ed]
a.out[0x4011eb]
/lib64/libc.so.6(__libc_start_main+0xf5)[0x7f0b8ae38555]
a.out[0x400819]
======= Memory map: ========
00400000-00402000 r-xp 00000000 fd:03 2082285                            /home/shay/a/navani/ece368/pao3/pa3/a.out
00601000-00602000 r--p 00001000 fd:03 2082285                            /home/shay/a/navani/ece368/pao3/pa3/a.out
00602000-00603000 rw-p 00002000 fd:03 2082285                            /home/shay/a/navani/ece368/pao3/pa3/a.out
00f74000-00f95000 rw-p 00000000 00:00 0                                  [heap]
7f0b84000000-7f0b84021000 rw-p 00000000 00:00 0
7f0b84021000-7f0b88000000 ---p 00000000 00:00 0
7f0b8ac00000-7f0b8ac15000 r-xp 00000000 fd:00 15049718                   /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f0b8ac15000-7f0b8ae14000 ---p 00015000 fd:00 15049718                   /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f0b8ae14000-7f0b8ae15000 r--p 00014000 fd:00 15049718                   /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f0b8ae15000-7f0b8ae16000 rw-p 00015000 fd:00 15049718                   /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f0b8ae16000-7f0b8afda000 r-xp 00000000 fd:00 12593713                   /usr/lib64/libc-2.17.so
7f0b8afda000-7f0b8b1d9000 ---p 001c4000 fd:00 12593713                   /usr/lib64/libc-2.17.so
7f0b8b1d9000-7f0b8b1dd000 r--p 001c3000 fd:00 12593713                   /usr/lib64/libc-2.17.so
7f0b8b1dd000-7f0b8b1df000 rw-p 001c7000 fd:00 12593713                   /usr/lib64/libc-2.17.so
7f0b8b1df000-7f0b8b1e4000 rw-p 00000000 00:00 0
7f0b8b1e4000-7f0b8b206000 r-xp 00000000 fd:00 13185028                   /usr/lib64/ld-2.17.so
7f0b8b3ca000-7f0b8b3cd000 rw-p 00000000 00:00 0
7f0b8b400000-7f0b8b405000 rw-p 00000000 00:00 0
7f0b8b405000-7f0b8b406000 r--p 00021000 fd:00 13185028                   /usr/lib64/ld-2.17.so
7f0b8b406000-7f0b8b407000 rw-p 00022000 fd:00 13185028                   /usr/lib64/ld-2.17.so
7f0b8b407000-7f0b8b408000 rw-p 00000000 00:00 0
7ffd41444000-7ffd41465000 rw-p 00000000 00:00 0                          [stack]
7ffd414af000-7ffd414b1000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Aborted (core dumped)

Begin by building with the `-g` flag. That will add debug information so you can learn when and where it happens. Then begin by scaling back your code, essentially creating a [mcve]. Then use a debugger to step through the code statement by statement, while drawing out all objects and pointers on a piece of paper to keep track of everything. If you still can't solve it yourself then [edit] your question to include what you found out during your debugging, as well as showing the [mcve] instead. — Some programmer dude, Dec 30 '20 at 04:13
By the way, how large is your tree? Have you made sure you won't get too deep recursion? — Some programmer dude, Dec 30 '20 at 04:16
My tree has 199 nodes to be exact. I ran the compiler with valgrind and the -g flag. I edited my question to include the error message — Saumya navani, Dec 30 '20 at 04:24
this is not minimal reproducible, so cannot guess what can go wrong, you can print addresses in order of memory allocation and free order may find some clue — IrAM, Dec 30 '20 at 04:35
On problem is [`while (!feof(fp))`](https://stackoverflow.com/q/5431941/440558). Another *possible* problem could be an empty stack. Or invalid (but non-null) `left` or `right` pointers in the tree (which would make sense reading that "invalid read" message from Valgrind). — Some programmer dude, Dec 30 '20 at 07:47
the posted code does not compile! Amongst several other problems, the contents of the 'home grown' header file: `stack..h` needs to be part of the question — user3629249, Dec 31 '20 at 07:24
running the posted code through a C compiler results in over 30 warnings and errors. Your compiler should have told you about those problems. If it did not tell you then either enable the warnings for your compiler (or get a better compiler) — user3629249, Dec 31 '20 at 07:30
regarding: `int flagsink = node->flagsink; if (node != NULL)` if `node` is NULL, then this first statement will cause a `seg fault event` — user3629249, Dec 31 '20 at 07:40
regarding statements like: `fwrite(&i1, 2, sizeof(int), fpw2);` the function: `fwrite()` can fail. so should always check the returned value (which these statements are failing to save) to assure the operation was successful — user3629249, Dec 31 '20 at 07:45
regarding: `stack = cr_stack(stack_size);` the function: `cr_stack()` is not defined anywhere in the posted code — user3629249, Dec 31 '20 at 07:51

score 2 · Answer 1 · answered Dec 30 '20 at 05:19

free(root);
destroy(root->left);
destroy(root->right);

In the function, void destroy(treenode *root) , you are freeing the pointer root. Accessing a free'd pointer invokes undefined behaviour.

From man page of errno:

On some ancient systems, <errno.h> was not present or did not declare errno, so that it was necessary to declare errno manually (i.e., extern int errno). Do not do this. It long ago ceased to be necessary, and it will cause problems with modern versions of the C library.

There is no need to explicitly declare errno again in the code. You declared errno in the beginning of the code.

These are the issues, I found.

Why am I getting this double free or corrupted backtrack error in C?

1 Answers1