Background
Just a re-post of a guide I wrote back in University to assist students in a programming course that focused on code efficiency and memory management. It has been sitting gathering dust, and I thought it should see the light of day again!
It is focused at a particular assigned where we had to build a 'snapshot' database in C. Some of the content may mention this assignment directly.
I found it initially very difficult to understand the difference between the different types of errors that are produced by C. This guide I wrote helped myself and others to understand the errors and then be able to quickly fix them.
Memory Leaks and Errors with Examples
Here is a quick guide on how to debug memory leaks and what each error means. This applies mainly to valgrind but can also apply to address sanitizer.
Running Valgrind
1) Compile your program (snapshot.c) using the following command:
gcc -Wall -Werror -std=c11 -g snapshot.c -o snapshot2) Run valgrind against your compiled program
valgrind --show-leak-kinds=all ./snapshotTypes of Errors
There a number of different errors that valgrind will output. Understanding what each one means will greatly assist you when attempting to fix your program.
This is sourced from: http://valgrind.org/docs/manual/quick-start.html
"probably lost": your program is leaking memory, you have not free()'d some allocated memory or you have changed the pointer to the object and hence, lost the original pointer. If you see this on OSX, it may be a false positive. Try testing on ucpu1 or ucpu2 to double check.
"definitely lost": your program is leaking memory, you have free()'d a struct and forgotten to free the list values inside the struct and therefore the list cannot be reached anymore.
"invalid write": the program wrote to some memory it should not have due to a heap block overrun. In other words, you have an: "ArrayIndexOutOfBoundsException" situation where in a loop you have not correctly calculated the number of items in the list... hitting an invalid index. In Address Sanitizer (the one Ed uses) this is likely to be the same as a heap-buffer-overflow.
The other common situation that throws this error is if malloc or realloc fails to return an address and you attempt to access something through the NULL value (similar to NullPointerException). In Address Sanitizer this will through a segmentaion fault :SIGSEGV.
Another thing you can do is free() an object and then try to access the free()'d object. In Address Sanitizer this will throw a heap-use-after-free.
AFAIK Address Santizer on Ed (and the sample tests provided) does not check for "definitely lost" or "probably lost" conditions and ONLY checks for "invalid writes". You will have to test for these conditions on your own machine.
Interpreting Address Sanitizer
Once you have read the above, you should be able to quickly identify the errors in your program. Note that the stack trace (list of functions that have been called) is also outputted when you have an error. This can be used to locate and fix the issue. In the below examples the most important bits of information are in bold.
Example 1: SIGSEV
ASAN:SIGSEGV
- =================================================================
- [1m[31m==6==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000020 (pc 0x0000004e6f60 bp 0x7fff13374010 sp 0x7fff13373e00 T0)
- [1m[0m #0 0x4e6f5f in entry_free /home/snapshot.c:269:3
- #1 0x4dc889 in command_purge /home/snapshot.c:569:17
- #2 0x4eab9b in main /home/snapshot.c:498:44
- #3 0x7fa83859aa3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x20a3f)
- #4 0x435898 in _start (/home/snapshot+0x435898)This is a SIGSEGV error (accessing a NULL pointer) on line 269 of snapshot.c. You could read the rest of the stack trace to workout what conditions caused the error but in this case it is obvious when looking at line 269...
269 n->prev->next = n->next;Obviously, previous was NULL and therefore a SEGV was caused.
Example 2: heap-use-after-free
=================================================================
- [1m[31m==6==ERROR: AddressSanitizer: heap-use-after-free on address 0x60300000efc0 at pc 0x0000004dfe30 bp 0x7fff804e0670 sp 0x7fff804e0668
- [1m[0m[1m[34mREAD of size 8 at 0x60300000efc0 thread T0[1m[0m
- #0 0x4dfe2f in command_rollback /home/snapshot.c:670:8
- #1 0x4e9e0b in main /home/snapshot.c:475:44
- #2 0x7f58b60eca3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x20a3f)
- #3 0x435898 in _start (/home/snapshot+0x435898)This is a heap-use-after-free error (accessing a free()'d pointer) on line 670 of snapshot.c. Again, taking a look at the line 670...
670 n = n->next;Obviously, n has been free()'d somewhere above this line, so the next logical step would be to go up line by line to find where the object was free()'d. In this case, that was the line above...
669 snapshot_remove(n);
670 n = n->next;So now that we know the problem we can work out a fix.
Example 3: heap-buffer-overflow
- =================================================================
- [1m[31m==6==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000efec at pc 0x0000004ddf58 bp 0x7ffd7b4060d0 sp 0x7ffd7b4060c8
- [1m[0m[1m[34mREAD of size 4 at 0x60200000efec thread T0[1m[0m
- #0 0x4ddf57 in command_pick /home/snapshot.c:401:19
- #1 0x4e60bb in main /home/snapshot.c:282:44
- #2 0x7f72f8cb1a3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x20a3f)
- #3 0x4356f8 in _start (/home/snapshot+0x4356f8)This is a heap-buffer-overflow error (over-run allocated memory) on line 401 of snapshot.c. Line 401:
401 printf("%d\n", n->values[index-1]);To debug this one, use the same process as above, keep going up until you find the problem.
Interpreting Valgrind
Valgrind should be your friend in this assignment as it tells you where actual memory leaks are.
It will tell you:
- how many mallocs you used
- how many of those mallocs you freed
- which were lost
- which were not freed on exit
Example 1: Your Goal!!
==3205==
==3205== HEAP SUMMARY:
==3205== in use at exit: 0 bytes in 0 blocks
==3205== total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==3205==
==3205== All heap blocks were freed -- no leaks are possible
==3205==
==3205== For counts of detected and suppressed errors, rerun with: -v
==3205== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)Key Points
- No heap in use at exit
- 0 allocs, 0 frees, 0 bytes
- All heap blocks were freed -- no leaks are possible
- 0 errors from 0 contexts
This is a really boring example where no mallocs were called, which is not really helpful.
Example 2: Difficult Example
==3215==
==3215== HEAP SUMMARY:
==3215== in use at exit: 0 bytes in 0 blocks
==3215== total heap usage: 41 allocs, 41 frees, 900 bytes allocated
==3215==
==3215== All heap blocks were freed -- no leaks are possible
==3215==
==3215== For counts of detected and suppressed errors, rerun with: -v
==3215== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)Key Points
- No heap in use at exit
- 41 allocs, 41 frees, 900 bytes
- All heap blocks were freed -- no leaks are possible
- 0 errors from 0 contexts
Here you can see I called malloc 41 times and free 41 times. That is what you should see if you do not have any memory leaks.
Example 3: Not freeing memory
==3286==
==3286== HEAP SUMMARY:
==3286== in use at exit: 32 bytes in 2 blocks
==3286== total heap usage: 86 allocs, 84 frees, 3,780 bytes allocated
==3286==
==3286== LEAK SUMMARY:
==3286== definitely lost: 32 bytes in 2 blocks
==3286== indirectly lost: 0 bytes in 0 blocks
==3286== possibly lost: 0 bytes in 0 blocks
==3286== still reachable: 0 bytes in 0 blocks
==3286== suppressed: 0 bytes in 0 blocks
==3286== Rerun with --leak-check=full to see details of leaked memory
==3286==
==3286== For counts of detected and suppressed errors, rerun with: -v
==3286== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)Key Points
- 2 blocks in use at exit
- 86 allocs, 84 frees, 3780 bytes
- 2 blocks were "definitely lost"
- 0 errors from 0 contexts
Ok. Let's have a look here. These ones are actually hard to debug because they do not give you a line number. You actually have to look through the whole code for what could be causing the problem. Making test cases that test specific functions can really help with this. In this case, I ran a test against my difference function.
Since I know which functions are called I can trace the issue back... (can take a while). let's say we have this stack-trace for the difference function...
create_object()
difference()
command_diff()
get_command()
main()I would start at the top and work backwards... (skipping a few steps here).
I had this in my code...
object = create_object (list, index);
free(list);
return object;
}So checking for memory leaks is all about understanding what your program is doing and knowing when and where you allocate memory.
Example 4: Invalid Writes
When you have an invalid write in valgrind it outputs a line number and error similar to Address Sanitizer AT THE POINT THE ERROR OCCURS!!
==3326== Invalid read of size 4
==3326== at 0x4024EA: difference (snapshot.c:898)
==3326== by 0x401C33: command_diff (snapshot.c:610)
==3326== by 0x400CC8: main (snapshot.c:87)
==3326== Address 0x51fe0fc is 0 bytes after a block of size 44 alloc'd
==3326== at 0x4C2CE8E: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3326== by 0x40264C: create_object (snapshot.c:931)
==3326== by 0x401C1C: command_diff (snapshot.c:608)
==3326== by 0x400CC8: main (snapshot.c:87)
==3326==
[21 144]
bye
==3326==
==3326== HEAP SUMMARY:
==3326== in use at exit: 0 bytes in 0 blocks
==3326== total heap usage: 84 allocs, 84 frees, 3,620 bytes allocated
==3326==
==3326== All heap blocks were freed -- no leaks are possible
==3326==
==3326== For counts of detected and suppressed errors, rerun with: -v
==3326== ERROR SUMMARY: 181 errors from 1 contexts (suppressed: 0 from 0)Key Points
- 2 blocks in use at exit
- 84 allocs, 84 frees, 3620 bytes
- All heap blocks were freed -- no leaks are possible
- 181 errors from 1 contexts
This is your typical ArrayIndexOutOfBounds error. Just go to the line that the error occurred on and fix it.
898 for(int j = 0; j < second->size+100; j++){I think that just about covers everything for memleaks and valgrind.
