Logo Questions Linux Laravel Mysql Ubuntu Git Menu
HTML CSS JAVASCRIPT SQL PYTHON PHP BOOTSTRAP JAVA JQUERY R React Kotlin
 

Is there way to verify my program has no memory leaks?

Tags:

c

memory-management

memory

memory-leaks

debugging

I wish to determine if the following program (an implementation of finding the maximum sub-array) leaks memory. Is there a general way to determine this? Such as using some feature of a debugger? What are general strategies?

struct Interval {
   int max_left;
   int max_right;
   int sum;
};

struct Interval * max_crossing_subarray(int A[], int low, int mid, int high) {
    struct Interval * crossing = malloc(sizeof(struct Interval));

    int left_sum = INT_MIN;
    int sum = 0;

    for(int i = mid; i >= low; --i) {
        sum = sum + A[i];
        if(sum > left_sum) {
            left_sum = sum;
            crossing->max_left = i;
        }
    }

    int right_sum = INT_MIN;
    sum = 0;

    for(int j = mid+1; j <= high; ++j) {
        sum = sum + A[j];
        if(sum > right_sum) {
            right_sum = sum;
            crossing->max_right = j;
        }
    }

    crossing->sum = left_sum + right_sum;

    return crossing;
}

struct Interval * max_subarray(int A[], int low, int high) {
    if(high == low) {
        struct Interval * base = malloc(sizeof(struct Interval));
        *base = (struct Interval) { low, high, A[low] };
        return base;
    } else {
        int mid = floor((low+high)/2);
        struct Interval * left = malloc(sizeof(struct Interval));
        struct Interval * right = malloc(sizeof(struct Interval));
        left = max_subarray(A, low, mid);
        right = max_subarray(A, mid+1, high);
        struct Interval * cross = max_crossing_subarray(A, low, mid, high);
        if(left->sum >= right->sum & right->sum >= cross->sum) {
            free(right);
            free(cross);
            return left;
        } else if(right->sum >= left->sum & right->sum >= cross-> sum) {
            free(left);
            free(cross);
            return right;
        } else {
            free(left);
            free(right);
            return cross;
        }
    }
}

int main()
{
    int A[] = {-10, 7, -5, -3, 40, 4, -1, 8, -3, -1, -5, 20, 7};
    struct Interval * result = max_subarray(A, 0, 12);

    printf("left: %i, right: %i, sum: %i\n", result->max_left, result->max_right, result->sum);

    return 0;
}

Due to the recursive nature of the program it's quite difficult to follow (at least for me). I think I've plugged everything but I'd like to find a methodology for being sure.

Edit: The software suggested in the selected answer allowed me to find all my leaks and as pointed out in the comment there was no reason to allocate left and right, below is the memory leak free code.

struct Interval {
   int max_left;
   int max_right;
   int sum;
};

struct Interval * max_crossing_subarray(int A[], int low, int mid, int high) {
    struct Interval * crossing = malloc(sizeof(struct Interval));

    int left_sum = INT_MIN;
    int sum = 0;

    for(int i = mid; i >= low; --i) {
        sum = sum + A[i];
        if(sum > left_sum) {
            left_sum = sum;
            crossing->max_left = i;
        }
    }

    int right_sum = INT_MIN;
    sum = 0;

    for(int j = mid+1; j <= high; ++j) {
        sum = sum + A[j];
        if(sum > right_sum) {
            right_sum = sum;
            crossing->max_right = j;
        }
    }

    crossing->sum = left_sum + right_sum;

    return crossing;
}

struct Interval * max_subarray(int A[], int low, int high) {
    if(high == low) {
        struct Interval * base = malloc(sizeof(struct Interval));
        *base = (struct Interval) { low, high, A[low] };
        return base;
    } else {
        int mid = floor((low+high)/2);
        struct Interval * left = max_subarray(A, low, mid);
        struct Interval * right = max_subarray(A, mid+1, high);
        struct Interval * cross = max_crossing_subarray(A, low, mid, high);
        if(left->sum >= right->sum & right->sum >= cross->sum) {
            free(right);
            free(cross);
            return left;
        } else if(right->sum >= left->sum & right->sum >= cross-> sum) {
            free(left);
            free(cross);
            return right;
        } else {
            free(left);
            free(right);
            return cross;
        }
    }
}

int main()
{
    int A[] = {-10, 7, -5, -3, 40, 4, -1, 8, -3, -1, -5, 20, 7};
    struct Interval * result = max_subarray(A, 0, 13-1);

    printf("left: %i, right: %i, sum: %i\n", result->max_left, result->max_right, result->sum);

    return 0;
}
like image 606
Ivor Denham-Dyson Avatar asked Jun 10 '20 12:06

Ivor Denham-Dyson

2 Answers

You can use valgrind. It's a memory debugging tool for Linux and other UNIX-like systems that finds memory leaks as well as invalid memory accesses.

When I run this code through valgrind, it outputs the following:

[dbush@db-centos7 ~]$ valgrind ./x1
==3406== Memcheck, a memory error detector
==3406== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3406== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==3406== Command: ./x1
==3406== 
left: 4, right: 12, sum: 69
==3406== 
==3406== HEAP SUMMARY:
==3406==     in use at exit: 300 bytes in 25 blocks
==3406==   total heap usage: 49 allocs, 24 frees, 588 bytes allocated
==3406== 
==3406== LEAK SUMMARY:
==3406==    definitely lost: 300 bytes in 25 blocks
==3406==    indirectly lost: 0 bytes in 0 blocks
==3406==      possibly lost: 0 bytes in 0 blocks
==3406==    still reachable: 0 bytes in 0 blocks
==3406==         suppressed: 0 bytes in 0 blocks
==3406== Rerun with --leak-check=full to see details of leaked memory
==3406== 
==3406== For counts of detected and suppressed errors, rerun with: -v
==3406== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

So you have some leaks. Now let's pass the --leak-check=full option to see where exactly those leaks are:

==11531== Memcheck, a memory error detector
==11531== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==11531== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==11531== Command: ./x1
==11531== 
left: 4, right: 12, sum: 69
==11531== 
==11531== HEAP SUMMARY:
==11531==     in use at exit: 300 bytes in 25 blocks
==11531==   total heap usage: 49 allocs, 24 frees, 588 bytes allocated
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 1 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 2 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 3 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 4 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 5 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 6 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 7 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 8 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 9 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 10 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 11 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 12 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 13 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 14 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 15 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 16 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 17 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 18 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 19 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 20 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 21 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 22 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 23 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007A8: max_subarray (x1.c:49)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 24 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x4007B6: max_subarray (x1.c:50)
==11531==    by 0x4007CE: max_subarray (x1.c:51)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x4007E9: max_subarray (x1.c:52)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== 12 bytes in 1 blocks are definitely lost in loss record 25 of 25
==11531==    at 0x4C29EA3: malloc (vg_replace_malloc.c:309)
==11531==    by 0x40065B: max_crossing_subarray (x1.c:13)
==11531==    by 0x400802: max_subarray (x1.c:53)
==11531==    by 0x400931: main (x1.c:73)
==11531== 
==11531== LEAK SUMMARY:
==11531==    definitely lost: 300 bytes in 25 blocks
==11531==    indirectly lost: 0 bytes in 0 blocks
==11531==      possibly lost: 0 bytes in 0 blocks
==11531==    still reachable: 0 bytes in 0 blocks
==11531==         suppressed: 0 bytes in 0 blocks
==11531== 
==11531== For counts of detected and suppressed errors, rerun with: -v
==11531== ERROR SUMMARY: 25 errors from 25 contexts (suppressed: 0 from 0)

Most of these leaks are coming from these two lines:

    struct Interval * left = malloc(sizeof(struct Interval));
    struct Interval * right = malloc(sizeof(struct Interval));

And if we look at the next two lines it's apparent why:

    left = max_subarray(A, low, mid);
    right = max_subarray(A, mid+1, high);

So right after you assign the address of allocated memory to these pointers you overwrite those addresses with other values, causing a leak. This can be fixed by getting rid of the malloc calls and initializing with the result of the function calls:

    struct Interval * left = max_subarray(A, low, mid);
    struct Interval * right = max_subarray(A, mid+1, high);

The last one is in max_crossing_subarray

struct Interval * crossing = malloc(sizeof(struct Interval));

This pointer is returned from the function, so we need to see where the missing free is. After some looking around, we see that it is called from max_subarray, which eventually returns it to main as result:

struct Interval * result = max_subarray(A, 0, 13-1);

printf("left: %i, right: %i, sum: %i\n", result->max_left, result->max_right, result->sum);

return 0;

But as you can see, there's no call to free here, so let's add it:

struct Interval * result = max_subarray(A, 0, 13-1);

printf("left: %i, right: %i, sum: %i\n", result->max_left, result->max_right, result->sum);

free(result);
return 0;

Now after making those fixes we'll run through valgrind again:

==11736== Memcheck, a memory error detector
==11736== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==11736== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==11736== Command: ./x1
==11736== 
left: 4, right: 12, sum: 69
==11736== 
==11736== HEAP SUMMARY:
==11736==     in use at exit: 0 bytes in 0 blocks
==11736==   total heap usage: 25 allocs, 25 frees, 300 bytes allocated
==11736== 
==11736== All heap blocks were freed -- no leaks are possible
==11736== 
==11736== For counts of detected and suppressed errors, rerun with: -v
==11736== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

And the leaks are gone.

like image 182
dbush Avatar answered Nov 14 '22 23:11

dbush

In general you cannot prove your program correctness unless you restrict the language to a sublanguage (like misra) with less features. In general the problem is undecidable.

But you can use software like lint for static check of math patterns, or valgrind for dynamic check, or languages like Coq in which the programs are proofs and they use the Hoare logic to make statements about your code. For example, using Hoare logic, it is proved that the kernel of Windows never segment faults.

like image 42
alinsoar Avatar answered Nov 14 '22 23:11

alinsoar
Sign in to Comment

Related questions

Preprocessor: Concatenate string to each argument in __VA_ARGS__
Create C timer in macOS
Does it make sense to exit(0) after a call to execl()?
Array of Linked Lists in C: initializing and inserting?
pthread_mutex_timedlock() exiting prematurely without waiting for timeout
Is variable assignment a statement or expression?
How exactly does the wait function work (in regards to condition variables)
Can I overflow uint32_t in a temporary result?
What's the default value of int fields of a local struct variable?
Is 1[&array] a proper replacement for &array[sizeof(array)/sizeof(array[0])] or way too obfuscated?
Convert the Linux open, read, write, close functions to work on Windows
Does pointer equality imply integer equality?
Is it legal to access struct members via offset pointers from other struct members?
Why is this non-null terminated string printed correctly
Why do I get different output on linux and OS/X
What's the difference between (size_t)-1 and ~0?
Why is MAP_GROWSDOWN mapping does not grow?
Size of int, short, long, long long?
CMake cannot create MakeFile on Windows
C multiple assignments to same variable in short-circuited expression

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!