Is there a memory leak in this C code?

Question

In

https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

the C implementation calls malloc inside the recursive function. Isn't that a memory leak?

#include <stdio.h>
#include <stdlib.h>

int mod (int a, int b){
    return a %b; 
}   

int *extendedEuclid (int a, int b){
   int *dxy = (int *)malloc(sizeof(int) *3);

   if (b ==0){
      dxy[0] =a; dxy[1] =1; dxy[2] =0;

       return dxy;
   }
   else{
       int t, t2;
       dxy = extendedEuclid(b, mod(a, b));
       t =dxy[1];
       t2 =dxy[2];
       dxy[1] =dxy[2];
       dxy[2] = t - a/b *t2;

       return dxy;
    }
}

int main(void)
{
   int a =99, b =78;
   int *ptr;

   ptr =extendedEuclid (a, b);
   printf("%d = %d * %d + %d * %d \n",ptr[0], a, ptr[1], b, ptr[2] );

   return 0;        
}

How do you free memory allocated in recursive functions?

Strictly speaking, if there is no `free` for each `malloc`, there is always a memory leak. — Lundin, Aug 23 '18 at 11:51
Yes, it's a leak. Especially in the `else` part (where the recursive call is made) and the allocated memory is completely disregarded. If the rest of the book contains code as bad as this, then I suggest you try to find another book. — Some programmer dude, Aug 23 '18 at 11:51
The problem is not allocating memory, the problem is when the bunch of allocated memory is not deallocated once it is not needed. Anyway, you can check it by yourself with some tools such as valgrind. — Jose, Aug 23 '18 at 11:51
This implementation seems to be about demonstrating the algorithm, and not about being production quality. Even without the erroneous allocation in each step of the recursion, it never make an attempt to free memory. It seems to rely on being executed in a hosted environment, where all the memory will be reclaimed by the hosting platform upon program termination. — StoryTeller - Unslander Monica, Aug 23 '18 at 11:53
@StoryTeller While true, sloppy code is still sloppy and could lead beginners to programming to learn bad habits. — Some programmer dude, Aug 23 '18 at 11:56
@Someprogrammerdude - It's not an endorsement of such code. Just a possible explanation for the OP to consider beyond "whomever wrote this doesn't know a thing about programming in C". — StoryTeller - Unslander Monica, Aug 23 '18 at 11:57
BTW, `mod()` is often considered different than `%`. Re:[What's the difference between “mod” and “remainder”?](https://stackoverflow.com/q/13683563/2410359). — chux - Reinstate Monica, Aug 23 '18 at 13:16

Support Ukraine · Answer 1 · 2018-08-23T12:06:14.677

3

Isn't that a memory leak?

Yes, it is. Every time a recursive call is made, i.e. here:

dxy = extendedEuclid(b, mod(a, b));

the just malloc'ed memory is leaked as dxy is overwritten with a new value (aka the return value)

The code should be more like:

int *extendedEuclid (int a, int b){
    int *dxy;
    if (b ==0){
        dxy = (int *)malloc(sizeof(int) *3);  // Move malloc to here
        dxy[0] =a; dxy[1] =1; dxy[2] =0;

        return dxy;
    }
    else { ....

So that the malloc is only done once, i.e. when there is no recursive call

edited Aug 23 '18 at 12:06

answered Aug 23 '18 at 11:52

Support Ukraine

42,271
4
38
63

While the leaking would be less, there's still a leak since there's no matching call to `free`. – Some programmer dude Aug 23 '18 at 11:53
1

@Someprogrammerdude Well, the **function** doesn't leak anymore. That's the important part. If the caller doesn't handle the returned pointer correct, it's another problem. – Support Ukraine Aug 23 '18 at 11:55

klutt · Answer 2 · 2018-08-23T12:31:04.353

Isn't that a memory leak?

Yes it is. An easy method to see this is the program valgrind

$ valgrind ./a.out 
==8528== Memcheck, a memory error detector
==8528== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==8528== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==8528== Command: ./a.out
==8528== 
3 = 99 * -11 + 78 * 14 
==8528== 
==8528== HEAP SUMMARY:
==8528==     in use at exit: 72 bytes in 6 blocks
==8528==   total heap usage: 7 allocs, 1 frees, 1,096 bytes allocated
==8528== 
==8528== LEAK SUMMARY:
==8528==    definitely lost: 72 bytes in 6 blocks
==8528==    indirectly lost: 0 bytes in 0 blocks
==8528==      possibly lost: 0 bytes in 0 blocks
==8528==    still reachable: 0 bytes in 0 blocks
==8528==         suppressed: 0 bytes in 0 blocks
==8528== Rerun with --leak-check=full to see details of leaked memory
==8528== 
==8528== For counts of detected and suppressed errors, rerun with: -v
==8528== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

How do you free memory allocated in recursive functions?

Hard to give a general answer to that question. It depends on the specific function. In this specific case you could change it so that you write the result to an output parameter instead of returning a pointer. Then the prototype of your method could look like this:

void extendedEuclid (int a, int b, int *dxy)

Remove the line declaring dxy and the malloc call, change extendedEuclid(b, mod(a, b)) to extendedEuclid(b, mod(a, b), dxy) and remove the return statements. Then, in main you do this:

int *ptr = malloc(sizeof(int) *3);
extendedEuclid (a, b, ptr);
printf("%d = %d * %d + %d * %d \n",ptr[0], a, ptr[1], b, ptr[2] );
free(ptr);

Oh, and don't cast malloc

Is there a memory leak in this C code?

2 Answers2