Memory leak in recursive function

Question

This is a snippet of my implementation of the Cooley-Tukey algorithm in C. And yes, this is college homework. But in any case ... The algorithm works fine, but I have to free ar1 and ar2 to get rid of huge memory leaks on huge input data, but every time I try, I get invalid reads. Theoretically, ar1 and ar2 should be used only by the current instance of the function, and they should be unique, since each instance of mallocs outputs its own result.

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) 

Thus, it seems that calling dft on line 83 frees up memory, which is then accessed by calling dft on the next line. Any idea what really happens and how can I get rid of leaks?

Answer 1

You say "each instance of mallocs has its own output", however this is not true in this statement:

 if(N == 1) return from; 

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

How could I get rid of leaks?

I expect you to free ar1 and ar2 before returning.

Answer 2

The best way to fix these problems is to clearly define your premises and postconditions. Do you think the returned result was malloc'ed? If so, you seem to be breaking this by returning "from" and also not freeing "ar2". If you assume that the returned result is not malloc'ed, you need to make sure that this memory was provided by the caller and also does not return malloc 'memory.