Acknowledgements
Valgrind
include < stdio .h>
include <stdlib .h>
define SIZE 100
- 4. Complex errors where valgrind is misleading
- 5. Mismatched free-delete.

Acknowledgements

This assignment has been modified by your CMPT 295 instructor.

Valgrind

Valgrind is a free utility for memory debugging, memory leak detection, and profiling. It runs only on Linux systems. In order to test your linked list program with Valgrind you should use the following command:

To instruct valgrind to also check for memory leaks, run:

valgrind --leak-check=full -s ./executable

If your program has no memory leaks, you will see something similar to the following output:

HEAP SUMMARY:
     in use at exit: 0 bytes in 0 blocks
   total heap usage: 140 allocs, 140 frees, 75,164 bytes allocated

All heap blocks were freed -- no leaks are possible

If your program does have memory leaks, you will see a report about all found mistakes or inconsistencies. Each row of the report starts with the process ID (the process ID is a number assigned by the operating system to a running program). Each error has a description, a stack trace (showing where the error occurred), and other data about the error. It is important to eliminate errors in the order that they occur during execution, since a single error early could cause others later on.

Here is a list of some of the errors that Valgrind can detect and report.

1. Detecting uninitialized values

line 5 j is uninitialized (garbage), copied into *p
line 11: Using i which now contains garbage

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

void foo(int *p) {
int j;
*p = j;
}

int main() {
int i = 10;
foo(&i);
printf("i = %d\n", i);
return 0;
}

Lets detect this using valgrind.

# WARNING: You need valgrind installed. Your 295 VM comes with valgrind preinstalled
# Build the executable. Note the inclusion of -g flag to help valgrind report exact linux number.
$ gcc -g uninitialized.c -o uninit
$ valgrind --tool=memcheck ./uninit

==20== Memcheck, a memory error detector
==20== Copyright (C) 2002-2017, and GNU GPLd, by Julian Seward et al.
==20== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==20== Command: ./uninit
==20==
==20== Conditional jump or move depends on uninitialised value(s)
==20==    at 0x48CBAD8: __vfprintf_internal (vfprintf-internal.c:1687)
==20==    by 0x48B5EBE: printf (printf.c:33)
==20==    by 0x1091C4: main (uninitialized.c:14)
==20==
==20== Use of uninitialised value of size 8
==20==    at 0x48AF81B: _itoa_word (_itoa.c:179)
==20==    by 0x48CB6F4: __vfprintf_internal (vfprintf-internal.c:1687)
==20==    by 0x48B5EBE: printf (printf.c:33)
==20==    by 0x1091C4: main (uninitialized.c:14)
==20==
==20== Conditional jump or move depends on uninitialised value(s)
==20==    at 0x48AF82D: _itoa_word (_itoa.c:179)
==20==    by 0x48CB6F4: __vfprintf_internal (vfprintf-internal.c:1687)
==20==    by 0x48B5EBE: printf (printf.c:33)
==20==    by 0x1091C4: main (uninitialized.c:14)
==20==
==20== Conditional jump or move depends on uninitialised value(s)
==20==    at 0x48CC3A8: __vfprintf_internal (vfprintf-internal.c:1687)
==20==    by 0x48B5EBE: printf (printf.c:33)
==20==    by 0x1091C4: main (uninitialized.c:14)
==20==
==20== Conditional jump or move depends on uninitialised value(s)
==20==    at 0x48CB86E: __vfprintf_internal (vfprintf-internal.c:1687)
==20==    by 0x48B5EBE: printf (printf.c:33)
==20==    by 0x1091C4: main (uninitialized.c:14)
==20==
i = 0
==20==
==20== HEAP SUMMARY:
==20==     in use at exit: 0 bytes in 0 blocks
==20==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated

You see a number of errors related to printf on line 33. The relevant error reported by valgrind's output indicates use of an uninitialized value. The variable used in line 33 is i, and hence we know that following the call to fooxsto have an uninitialized value

2. Invalid read/write errors.

This error will happen when your code reads or writes to a memory address which you did not allocate. Sometimes this error occurs when an array is indexed beyond its boundary, which is referred to as an "overrun" error. Unfortunately, Valgrind is unable to check for locally-allocated arrays (i.e., those that are on the stack.) Overrun checking is only performed for dynamic memory.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct entry_t {
char *value;
char *next;
};

struct header_as_type {
struct entry_t variable;
};

struct header_as_pointer {
struct entry_t\* variable;
};

void main() {
struct header_as_type head_t;
struct header_as_pointer head_p;
char string[] = "Hello World";
head_t.variable.value = string;
printf("%p",head_t.variable.value);

// INCORRECT EXECUTION.
// UNCOMMENT Line below if you want correct execution
// head_p.variable = (struct entry_t\*)malloc(sizeof(struct entry_t));
head_p.variable->value = string;
printf("%p",head_p.variable->value);
}

$ gcc -g invalid.c -o invalid
$ ./invalid
segfault
# We now use valgrind to identify why the segfault is happening.
$ valgrind --leak-check=full -s ./invalid
==61== Memcheck, a memory error detector
==61== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==61== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==61== Command: ./invalid
==61==
==61== Use of uninitialised value of size 8
==61==    at 0x1091C1: main (invalid.c:24)
==61==
==61==
==61== Process terminating with default action of signal 11 (SIGSEGV)
==61==  Bad permissions for mapped region at address 0x10924D
==61==    at 0x1091C1: main (invalid.c:24)
0x1fff00054c==61==
==61== HEAP SUMMARY:
==61==     in use at exit: 0 bytes in 0 blocks
==61==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated
==61==
==61== All heap blocks were freed -- no leaks are possible
==61==
==61== Use --track-origins=yes to see where uninitialised values come from
==61== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
==61==
==61== 1 errors in context 1 of 1:
==61== Use of uninitialised value of size 8
==61==    at 0x1091C1: main (invalid.c:24)
==61==
==61== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Valgrind notes the uninitialized value in line 24. It complains that head_p.variable->value is uninitialized. To understand why we now use pythontutor to visualize the problem. When you are on line 24, you can see head_p is pointing to ? i.e., its uninitialized. head_t on the other hand has been allocated on the stack and the two pointers within it value and next. heat_t.value pointer is initialized in line 18. To fix the problem uncomment line 23 to allocate entry_t and head_p and rerun pythontutor fixed example. Now, in line 23 you can see heat_p is initialized. heat_p->value is then initialized on line 24.

3. Invalid Read 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# include < stdio .h>

# include <stdlib .h>

# define SIZE 100

int main () {
int i , sum = 0;
int \*a = malloc ( SIZE );
for ( i = 0; i < SIZE ; ++ i )
sum += a [ i ];
a [26] = 1;
a = NULL ;
if ( sum > 0) printf ("Hi !\n") ;
return 0;
}

We read past the end of the allocated array.

Trying to read from area which we are not allowed to access
Could result in a SEGFAULT and surely doesn’t do what we want
Valgrind provides enough details to find the problem

$ gcc -g invalid2.c -o invalid2
$ valgrind --leak-check=full -s ./invalid2

==77== Memcheck, a memory error detector
==77== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==77== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==77== Command: ./invalid2
==77==
==77== Invalid read of size 4
==77==    at 0x1091A7: main (invalid2.c:8)
==77==  Address 0x4a460a4 is 0 bytes after a block of size 100 alloc'd
==77==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==77==    by 0x109185: main (invalid2.c:6)
==77==
==77== Invalid write of size 4
==77==    at 0x1091BE: main (invalid2.c:9)
==77==  Address 0x4a460a8 is 4 bytes after a block of size 100 alloc'd
==77==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==77==    by 0x109185: main (invalid2.c:6)
==77==
==77== Conditional jump or move depends on uninitialised value(s)
==77==    at 0x1091D0: main (invalid2.c:11)
==77==
Hi !
==77==
==77== HEAP SUMMARY:
==77==     in use at exit: 100 bytes in 1 blocks
==77==   total heap usage: 2 allocs, 1 frees, 1,124 bytes allocated
==77==
==77== 100 bytes in 1 blocks are definitely lost in loss record 1 of 1
==77==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==77==    by 0x109185: main (invalid2.c:6)
==77==
==77== LEAK SUMMARY:
==77==    definitely lost: 100 bytes in 1 blocks
==77==    indirectly lost: 0 bytes in 0 blocks
==77==      possibly lost: 0 bytes in 0 blocks
==77==    still reachable: 0 bytes in 0 blocks
==77==         suppressed: 0 bytes in 0 blocks
==77==
==77== Use --track-origins=yes to see where uninitialised values come from
==77== ERROR SUMMARY: 78 errors from 4 contexts (suppressed: 0 from 0)
==77==
==77== 1 errors in context 1 of 4:
==77== Conditional jump or move depends on uninitialised value(s)
==77==    at 0x1091D0: main (invalid2.c:11)
==77==
==77==
==77== 1 errors in context 2 of 4:
==77== Invalid write of size 4
==77==    at 0x1091BE: main (invalid2.c:9)
==77==  Address 0x4a460a8 is 4 bytes after a block of size 100 alloc'd
==77==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==77==    by 0x109185: main (invalid2.c:6)
==77==
==77==
==77== 75 errors in context 3 of 4:
==77== Invalid read of size 4
==77==    at 0x1091A7: main (invalid2.c:8)
==77==  Address 0x4a460a4 is 0 bytes after a block of size 100 alloc'd
==77==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==77==    by 0x109185: main (invalid2.c:6)
==77==
==77== ERROR SUMMARY: 78 errors from 4 contexts (suppressed: 0 from 0)

4. Complex errors where valgrind is misleading

Valgrind is useful but may misreport logical errors in your data structure. For instance, in this example valgrind reports a memory leak. However, the actual error is caused by a logical error in the data structure.

$ gcc -g driver1.c linkedlist.c -o linkedlist
$ valgrind --leak-check=full -s ./linkedlist
==85== Memcheck, a memory error detector
==85== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==85== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==85== Command: ./linkedlist
==85==
Test failed.
==85==
==85== HEAP SUMMARY:
==85==     in use at exit: 64 bytes in 3 blocks
==85==   total heap usage: 4 allocs, 1 frees, 1,088 bytes allocated
==85==
==85== 64 (16 direct, 48 indirect) bytes in 1 blocks are definitely lost in loss record 3 of 3
==85==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==85==    by 0x1092AA: create_list (linkedlist.c:10)
==85==    by 0x1091DD: test_linked_list (driver1.c:18)
==85==    by 0x10919A: main (driver1.c:9)
==85==
==85== LEAK SUMMARY:
==85==    definitely lost: 16 bytes in 1 blocks
==85==    indirectly lost: 48 bytes in 2 blocks
==85==      possibly lost: 0 bytes in 0 blocks
==85==    still reachable: 0 bytes in 0 blocks
==85==         suppressed: 0 bytes in 0 blocks
==85==
==85== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

However, if we visualize. We can see that the error

Python Tutor Visualization

the linked list node logic is broken.
the first node val=10 next pointer is not set. This leads to the
second node being lost. The error is due to insert_end in which the next pointer is not set.
However, valgrind does not observe error until, check_val fails and it detects a memory leak. This is because delete_list iterates in a forward direction and stops at the first node. It never gets to the val=20 to free it.
The error is observed as a memory leak. However, the primary cause is due to next pointer not being set correctly.

5. Mismatched free-delete.

This occurs when your code attempts to delete allocated memory twice, or delete memory that was not allocated with new.

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

int main()
{
 char *x = malloc(100);
 free(x);
 free(x);
 return 0;
}

$ gcc -g doublefree.c -o doublefree
$ valgrind --leak-check=full -s ./doublefree
==92== Memcheck, a memory error detector
==92== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==92== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==92== Command: ./doublefree
==92==
==92== Invalid free() / delete / delete[] / realloc()
==92==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==92==    by 0x10919A: main (doublefree.c:8)
==92==  Address 0x4a46040 is 0 bytes inside a block of size 100 free'd
==92==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==92==    by 0x10918E: main (doublefree.c:7)
==92==  Block was alloc'd at
==92==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==92==    by 0x10917E: main (doublefree.c:6)
==92==
==92==
==92== HEAP SUMMARY:
==92==     in use at exit: 0 bytes in 0 blocks
==92==   total heap usage: 1 allocs, 2 frees, 100 bytes allocated
==92==
==92== All heap blocks were freed -- no leaks are possible
==92==
==92== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
==92==
==92== 1 errors in context 1 of 1:
==92== Invalid free() / delete / delete[] / realloc()
==92==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==92==    by 0x10919A: main (doublefree.c:8)
==92==  Address 0x4a46040 is 0 bytes inside a block of size 100 free'd
==92==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==92==    by 0x10918E: main (doublefree.c:7)
==92==  Block was alloc'd at
==92==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==92==    by 0x10917E: main (doublefree.c:6)
==92==
==92== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)