Memory leak in recursive function

Question

This is a snippet of my implementation of the Cooley-Tukey algorithm in C. And yes, it's college homework. But anyway... The algorithm works fine but I have to free ar1 and ar2 to get rid of immense memory leaks on huge input data but every time I try, I get invalid reads. In theory, ar1 and ar2 should only be used by the current instance of the function and they should be unique, since every instance mallocs its own output.

complex_exp * dft(complex_exp * from, int N, int s, int inverse) {

if(N == 1)
    return from;

int i;
complex_exp * transformed = (complex_exp *) malloc(N * sizeof(complex_exp));
complex_exp * ar1 = dft(from, N / 2, 2*s, inverse); //LINE 83
complex_exp * ar2 = dft(from + s, N / 2, 2*s, inverse); // LINE 84

for(i = 0; i < N/2; i++) {

    transformed[i] = ar1[i]; //LINE 88
}

for(i = N/2; i < N; i++) {
    transformed[i] = ar2[i - N/2];
}

//Do stuff with the transformed array - NO reference to ar1 or ar2.

free(ar1); //LINE 113
return transformed;
}

Valgrind says:

==69597== Invalid read of size 8
==69597==    at 0x100000EE6: dft (progtest05.c:88)
==69597==    by 0x100000EA2: dft (progtest05.c:84)
==69597==    by 0x100000E67: dft (progtest05.c:83)
==69597==    by 0x100000E67: dft (progtest05.c:83)
==69597==    by 0x100001A0E: main (progtest05.c:233)
==69597==  Address 0x100007250 is 64 bytes inside a block of size 256 free'd
==69597==    at 0xDCB8: free (vg_replace_malloc.c:450)
==69597==    by 0x1000011E5: dft (progtest05.c:113)
==69597==    by 0x100000E67: dft (progtest05.c:83)
==69597==    by 0x100000E67: dft (progtest05.c:83)
==69597==    by 0x100000E67: dft (progtest05.c:83)
==69597==    by 0x100001A0E: main (progtest05.c:233)

So it seems that a call to dft on line 83 frees the memory which then the call to dft on the next line tries to access. Any idea what's actually going on and how I could get rid of the leaks?

Answer 1

You say "every instance mallocs its own output", however that's not true in this statement:

if(N == 1)
    return from;

Perhaps when N==1 you should return a copy of from (i.e. malloc new memory, copy the contents of from into the new memory, and return the copy).

how I could get rid of the leaks?

I expect you must free ar1 and ar2 before returning transformed.

Answer 2

The best way to fix these issues is to clearly define your preconditions and postconditions. Do you assume that the returned result has been malloc'ed? If so, you appear to violate this by returning "from" and also by failing to free "ar2". If you assume that the returned result is not malloc'ed, then you need to ensure that this memory has been provided by the caller and furthermore not return malloc'ed memory.