CS100-Lab 4 Solved

Memory management
The ability to dynamically allocate and deallocate memory is one of the strongest features of C++ programming, but the greatest strength can also be the greatest weakness. This is certainly true of C++ applications, where memory-handling problems are among the most common bugs.

One of the most subtle and hard-to-detect bugs is the memory leak - the failure to properly deallocate memory that was previously allocated. A small memory leak that occurs only once may not be noticed, but programs that leak large amounts of memory, or leak progressively, may display symptoms ranging from poor (and gradually decreasing) performance to running out of memory completely. Worse, a leaking program may use up so much memory that it causes another program to fail, leaving the user with no clue to where the problem truly lies. In addition, even harmless memory leaks may be symptomatic of other problems.
## Valgrind
[Valgrind](https://valgrind.org/) is an instrumentation framework for building dynamic analysis tools. We will be focusing on the Memcheck tool in their extensive tool suite. 

Note: Valgrind is designed for Linux, but it is also compatible with some versions of Mac OS (unless you are running a very new version of the OS).  If you are performing this lab on Windows, it is recommended that you use `hammer` to run valgrind.

### Memcheck
**Memcheck** detects memory-management problems, and is aimed primarily at C and C++ programs. When a program is run under Memcheck's supervision, all reads and writes of memory are checked, and calls to `malloc`/`new`/`free`/`delete` are *intercepted*. As a result, Memcheck can detect if your program:
 * Accesses memory it shouldn't (areas not yet allocated, areas that have been freed, areas past the end of heap blocks, inaccessible areas of the stack).
 * Uses uninitialized values in dangerous ways.
 * Leaks memory.
 * Does bad frees of heap blocks (double frees, mismatched frees).
 * Passes overlapping source and destination memory blocks to `memcpy()` and related functions.

Memcheck reports these errors as soon as they occur, giving the source line number at which it occurred, and also a stack trace of the functions called to reach that line. Memcheck tracks valid addresses and initialization of values. As a result, it can detect the use of uninitialized memory. Memcheck runs programs about 10-30x slower than normal.

### Perparing your program
Compile your program with the following flags:
 * `-g` - to include debugging information so that Memcheck's error messages include *exact* line numbers. 
 * `-O0` - to turn off all optimizations. Memcheck's error messages can be slightly inaccurate at `-O1` and can lead to spurious errors at `-O2` or above. 

For this lab the command: 
```
$ g++ -g -O0 *.cpp -o <exec_name
```
will be sufficient.

### Running your program under Memcheck
The examples/exercises in this lab don't use command line arguments, but if your program is called like this:
```
$ ./myprog arg1 arg2
```
Then run Valgrind like this:
```
$ valgrind --leak-check=full ./myprog arg1 arg2
```
Memcheck is the default tool so no tool flags are necessary. The `--leak-check` option turns on the detailed memory leak detector. 

Your program will run much slower (e.g. 20 - 30 times) than normal and use a lot more memory. Memcheck will issue messages about memory errors and leaks that it detects. 

## Examples
Let's go over some simple examples of the types of errors you can uncover using Valgrind and how to interpret the error messages. We're going to start with a simple c++ program (save the file as simple.cpp):
```
int main() {
    int *p = new int[10];
    p[10] = 1;

    return 0;
}
```
This is a pretty typical introduction to pointers example from CS012. It also contains a **very** common memory management mistake. On line 2 we allocated a contiguous location in memory large enough for 10 `int`s and assigned the starting address to an `int` pointer `p`. The next line then attempts to assign to the element with index 10. This may seem fine since it *seems* to be the last element in the array; however, due to 0-based addressing, the last element is actual `p[9]`.

Now, let's compile the program:
```
$ g++ -g -O0 -o example1 simple.cpp
```

And run it:
```
$ ./example1
```
You may get results similar to:
```
example1: malloc.c:2401: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsign
ed long) (old_size) = MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0
)' failed.
Aborted (core dumped)
```
Or it might even run, either way figuring out your error is cryptic and difficult. Let's run it through Valgrind (you don't need to recompile):
```
$ valgrind --leak-check=full ./example1
```
And you'll get a much more in detailed report of what is going on:
```
==13621== Memcheck, a memory error detector
==13621== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==13621== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==13621== Command: ./example1
==13621== 
==13621== Invalid write of size 4
==13621==    at 0x108698: main (simple.cpp:3)
==13621==  Address 0x5b7dca8 is 0 bytes after a block of size 40 alloc'd
==13621==    at 0x4C3089F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13621==    by 0x10868B: main (simple.cpp:2)
==13621== 
==13621== 
==13621== HEAP SUMMARY:
==13621==     in use at exit: 40 bytes in 1 blocks
==13621==   total heap usage: 2 allocs, 1 frees, 72,744 bytes allocated
==13621== 
==13621== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
==13621==    at 0x4C3089F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13621==    by 0x10868B: main (simple.cpp:2)
==13621== 
==13621== LEAK SUMMARY:
==13621==    definitely lost: 40 bytes in 1 blocks
==13621==    indirectly lost: 0 bytes in 0 blocks
==13621==      possibly lost: 0 bytes in 0 blocks
==13621==    still reachable: 0 bytes in 0 blocks
==13621==         suppressed: 0 bytes in 0 blocks
==13621== 
==13621== For counts of detected and suppressed errors, rerun with: -v
==13621== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
```
Let's look at this bit by bit. 
```
==13621== Memcheck, a memory error detector
==13621== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==13621== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==13621== Command: ./example1
``` 
 * 13621 is the process ID; typically it is not important.
 * The rest shows some copyright and version information as well as the command Valgrind is running (your executable).

Now we get into the errors:
```
==13621== Invalid write of size 4
==13621==    at 0x108698: main (simple.cpp:3)
==13621==  Address 0x5b7dca8 is 0 bytes after a block of size 40 alloc'd
==13621==    at 0x4C3089F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13621==    by 0x10868B: main (simple.cpp:2)
```
This shows us that the error was an `Invalid write of size 4` on line `(simple.cpp:3)` in function `main`. The address of the line (`0x108698`) as well as the address of the memory (`0x5b7dca8`) are shown here and they can be incredibly useful when debugging some really nasty memory bugs on the stack/heap, but they aren't helpful in this simple case. The rest of the error message will provide additional information that may help in identifying and fixing the error, in this case, a part of the root cause of the error comes from line (`simple.cpp:2`) with the `operator new[](unsigned long)`.

After this we get a `HEAP SUMMARY`:
```
==13621== HEAP SUMMARY:
==13621==     in use at exit: 40 bytes in 1 blocks
==13621==   total heap usage: 2 allocs, 1 frees, 72,744 bytes allocated
==13621== 
==13621== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
==13621==    at 0x4C3089F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13621==    by 0x10868B: main (simple.cpp:2)
```
This shows us the second error we have. We can see here that we have `40 bytes in 1 blocks` still *in use at exit*. Additionally, we had `2 allocs` but only `1 free`. There is memmory that was allocated but then did not have a corresponding deallocation. Looking at the records (second half of the message), we can see that `40 bytes in 1 block` are **definitely lost** in loss record 1 of 1. We are given some additional information to help track it down. `operator new[](unsigned long)` at `main (simple.cpp:2)` is at fault here. 

Finally, we are given a summary:
```
==13621== LEAK SUMMARY:
==13621==    definitely lost: 40 bytes in 1 blocks
==13621==    indirectly lost: 0 bytes in 0 blocks
==13621==      possibly lost: 0 bytes in 0 blocks
==13621==    still reachable: 0 bytes in 0 blocks
==13621==         suppressed: 0 bytes in 0 blocks
==13621== 
==13621== For counts of detected and suppressed errors, rerun with: -v
==13621== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
```
We have `40 bytes in 1 blocks` **definitely lost** and nothing *indirectly*, or *possibly* lost, no memory *still reachable* and no errors were suppressed. Don't worry, the next examples will cover these types of errors as well. You can add to verbosity by adding additional `-v` flags, but the default typically has enough information to cover most errors. 

Let's fix the errors one at a time. First, let's get rid of the `Invalid write` since that is causing our program to crash. The fix is quite simple, figure out the size of the array, the last index in the array, and make sure you are in bounds of the array. 
```
int main() {
    int *p = new int[10];
    p[9] = 1; // Correct this to size - 1 = 10 - 1 = 9

    return 0;
}
```
And compile and run again (I add a trick I frequently use, the `&&` means "execute the second command **only if** the first command **succeeds**):
```
$ g++ -g -O0 simple.cpp -o example1 && ./example1
```
Now your program should run to completion (you won't see any output). Woohoo! You fixed it...wait, there were two errors weren't there? Let's run it back through Valgrind and see:
```
$ valgrind ./example1
```
And you'll see the following (tool information excluded for brevity): 
```
==14490== HEAP SUMMARY:
==14490==     in use at exit: 40 bytes in 1 blocks
==14490==   total heap usage: 2 allocs, 1 frees, 72,744 bytes allocated
==14490== 
==14490== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
==14490==    at 0x4C3089F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==14490==    by 0x10868B: main (simple.cpp:2)
==14490== 
==14490== LEAK SUMMARY:
==14490==    definitely lost: 40 bytes in 1 blocks
==14490==    indirectly lost: 0 bytes in 0 blocks
==14490==      possibly lost: 0 bytes in 0 blocks
==14490==    still reachable: 0 bytes in 0 blocks
==14490==         suppressed: 0 bytes in 0 blocks
==14490== 
==14490== For counts of detected and suppressed errors, rerun with: -v
==14490== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
```
We can clearly see from our summaries that we are still *leaking* memory even though we don't have anymore write errors. We have the same error as above, but to remind us, we have `40 bytes in 1 blocks` **definitely lost** in record 1 due to the `operator new[](unsigned long)` on line (`simple.cpp:2`) in `main` function. Let's look at that code block (between `{` and `}`):
```
{
    int *p = new int[10];
    p[9] = 1;

    return 0;
}
```
The `new` operator allocates new memory, but we never deallocate that memory. Let's do that now:
```
{
    int *p = new int[10];
    p[9] = 1;

    delete p; // Deallocate the memory from the new above
    return 0;
}
```
*Yes I used the wrong delete but this was done on purpose, bear with me. If you didn't realize that was the wrong delete, that's exactly what this tool helps with so don't feel bad!*

### When a block is freed with an inappropriate deallocation function
 * If allocated with `malloc`, `calloc`, `realloc`, `valloc`, or `memalign`, you must deallocate with free\*.
 * If allocated with `new[]`, you must deallocate with `delete[]`.
 * If allocated with `new`, you must deallocate with `delete`.

\* These are common in `C` but less commonly seen in `C++`, so you likely haven't seen them much at this point.

Let's run this through Valgrind again:
```
==14593== Mismatched free() / delete / delete []
==14593==    at 0x4C3123B: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==14593==    by 0x10871E: main (simple.cpp:5)
==14593==  Address 0x5b7dc80 is 0 bytes inside a block of size 40 alloc'd
==14593==    at 0x4C3089F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==14593==    by 0x1086FB: main (simple.cpp:2)
==14593== 
==14593== 
==14593== HEAP SUMMARY:
==14593==     in use at exit: 0 bytes in 0 blocks
==14593==   total heap usage: 2 allocs, 2 frees, 72,744 bytes allocated
==14593== 
==14593== All heap blocks were freed -- no leaks are possible
==14593== 
==14593== For counts of detected and suppressed errors, rerun with: -v
==14593== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
```
If we look at the summary it appears we freed all of the memory, however, if we look at the error list we will see that we used a `Mismatched free() / delete / delete []` at `operator delete(void*)` on line (`simple.cpp:5`) in the `main` function. And if we look at the additional information we can see the root is from `operator new[](unsigned long)` at line (`simple.cpp:2`) in the `main` function. Looking at these two operators as shown by Valgrind, we can see that we allocated with a `[]` but didn't deallocate with the same. Let's fix that now. 
```
{
    int *p = new int[10];
    p[9] = 1;

    delete[] p; // Deallocate the memory from the new above
    return 0;
}
```
And run Valgrind again:
```
==14620== HEAP SUMMARY:
==14620==     in use at exit: 0 bytes in 0 blocks
==14620==   total heap usage: 2 allocs, 2 frees, 72,744 bytes allocated
==14620== 
==14620== All heap blocks were freed -- no leaks are possible
==14620== 
==14620== For counts of detected and suppressed errors, rerun with: -v
==14620== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
Now we're at what is called **Memcheck-clean**, we have `0 bytes in 0 blocks` in use at exit, `All heap blocks were freed -- no leaks are possible` and we have `0 errors from 0 contexts`. This is the goal of any program we write.

The final step, now that we're at **Memcheck-clean**, is to re-run with optimizations turned back on:
```
$ g++ -g -O2 *.cpp -o example1
```

Congratulations! You've successfully cleaned up a simple program from all memory leaks using the Memcheck tool in the Valgrind suite.
### Illegal read/illegal write errors
The first example showed an example of an *Illegal write* error. If we had tried to print out the value 
```
cout << p[10] << endl;
```
We would have had a reported `Invalid read of size 4` at that line. The rest of that error message looks very similar to the `Invalide write` error. 

### Use of uninitialized values
As a general rule, you should always initialize your values. Nonetheless there are times that it happens (unintentional or not). Memcheck will catch these errors with a caveat. Let's look at the following program (`uninitialized.cpp`):
```
#include <iostream
using namespace std;

int main() {
    int x;
    cout << x << endl;

    return 0;
}
```
Yes, it is again a silly examply, but it is used for illustrative purposes so bear with me. Let's compile and run this program:
```
$ g++ -g -O0 uninitialized.cpp -o example2 && ./example2
```
This should run and will print a number (often 0), **but** I want to emphasize that this should not be expected and is not because of the C++ standard. `x` is unintialized, and you may very well get a junk value. (I have graded a lot of assignments where students submitted programs that worked for them because their uninitialized variables happened to be zero.  When I graded them on my computer, they held junk values, and their programs failed.  The only way to be sure is to test your code under valgrind.) Now, let's run it through Valgrind and see what happens:
```
==14854== Conditional jump or move depends on uninitialised value(s)
==14854==    at 0x4F43B2A: std::ostreambuf_iterator<char, std::char_traits<char std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char ::_M_insert_int<long(std::ostreambuf_iterator<char, std::char_traits<char , std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x4F50074: std::ostream& std::ostream::_M_insert<long(long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x1088A2: main (uninitialized.cpp:6)
==14854== 
==14854== Use of uninitialised value of size 8
==14854==    at 0x4F4362E: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x4F43B53: std::ostreambuf_iterator<char, std::char_traits<char std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char ::_M_insert_int<long(std::ostreambuf_iterator<char, std::char_traits<char , std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x4F50074: std::ostream& std::ostream::_M_insert<long(long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x1088A2: main (uninitialized.cpp:6)
==14854== 
==14854== Conditional jump or move depends on uninitialised value(s)
==14854==    at 0x4F4363B: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x4F43B53: std::ostreambuf_iterator<char, std::char_traits<char std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char ::_M_insert_int<long(std::ostreambuf_iterator<char, std::char_traits<char , std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x4F50074: std::ostream& std::ostream::_M_insert<long(long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x1088A2: main (uninitialized.cpp:6)
==14854== 
==14854== Conditional jump or move depends on uninitialised value(s)
==14854==    at 0x4F43B86: std::ostreambuf_iterator<char, std::char_traits<char std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char ::_M_insert_int<long(std::ostreambuf_iterator<char, std::char_traits<char , std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x4F50074: std::ostream& std::ostream::_M_insert<long(long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x1088A2: main (uninitialized.cpp:6)
==14854== 
0
==14854== 
==14854== HEAP SUMMARY:
==14854==     in use at exit: 0 bytes in 0 blocks
==14854==   total heap usage: 2 allocs, 2 frees, 73,728 bytes allocated
==14854== 
==14854== All heap blocks were freed -- no leaks are possible
==14854== 
==14854== For counts of detected and suppressed errors, rerun with: -v
==14854== Use --track-origins=yes to see where uninitialised values come from
==14854== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 0 from 0)
```
Oh boy...that's a lot of errors, and they really don't seem friendly to look at. This is similar to compiler errors generated when using the Standard Template Library (STL), `cout` in this case. Let's take a look at the first error though:
```
==14854== Conditional jump or move depends on uninitialised value(s)
==14854==    at 0x4F43B2A: std::ostreambuf_iterator<char, std::char_traits<char std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char ::_M_insert_int<long(std::ostreambuf_iterator<char, std::char_traits<char , std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x4F50074: std::ostream& std::ostream::_M_insert<long(long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x1088A2: main (uninitialized.cpp:6)
```
Okay...so there is a *Conditional jump or move* somewhere that depends on an *unitialised value(s)*. You may have learned about *jumps* in CS061 if you've taken that course so far but the important part here is that it *depends on an unitialised value(s)*. In fact, if we look at the second error we can see:
```
==14854== Use of uninitialised value of size 8
==14854==    at 0x4F4362E: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x4F43B53: std::ostreambuf_iterator<char, std::char_traits<char std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char ::_M_insert_int<long(std::ostreambuf_iterator<char, std::char_traits<char , std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x4F50074: std::ostream& std::ostream::_M_insert<long(long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.25)
==14854==    by 0x1088A2: main (uninitialized.cpp:6)
```
There it is, right at the top: `Use of unintialised value of size 8`. However, if we inspect the error message we see that it is at `???` by `std::ostreambuf...` by `std::ostream&...` by `main (uninitialized.cpp:6)`. That last *by...by...by* sequence is the stack trace. It's frequently a good idea to skip past all the library files and see what is the last function **you wrote** that caused that. We can see that in the `main` function on line 6 we set off this error. But we still don't know what caused it. We can see by inspecting line 6 `cout << x << endl;` that it is likely caused by the variable `x`, but that's about all we get. It turns out, we can add additional flags into the Valgrind call to get more out of this, specifically the `--track-origins=yes` flag:
```
$ valgrind --leak-check=full --track-origins=yes ./example2
```
Now let's look at that same error again (the second one):
```
==14904== Use of uninitialised value of size 8
==14904==    ...
==14904==    ...
==14904==    ...
==14904==    by 0x1088A2: main (uninitialized.cpp:6)
==14904==  Uninitialised value was created by a stack allocation
==14904==    at 0x10888A: main (uninitialized.cpp:4)
```
I've truncated the errors from the STL for brevity. You shouldn't need to dig into those in most errors. If you do, grab a cup of tea, clear your schedule for the week and get busy. Now we can see that the new flag added some additional information:
```
==14904==  Uninitialised value was created by a stack allocation
==14904==    at 0x10888A: main (uninitialized.cpp:4)
```
The variable at fault here was created by stack allocation in the `main` function from (`unitialized.cpp:4`). After some inspection of that function we can see that the variable `x` is at fault and can fix it by simply initializing it to some value, let's say 10.
```
int x = 10;
```
Now, compiling and running Valgrind again we can see that we achieved **Memcheck-clean**.
```
==14973== HEAP SUMMARY:
==14973==     in use at exit: 0 bytes in 0 blocks
==14973==   total heap usage: 2 allocs, 2 frees, 73,728 bytes allocated
==14973== 
==14973== All heap blocks were freed -- no leaks are possible
==14973== 
==14973== For counts of detected and suppressed errors, rerun with: -v
==14973== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
It is important to note here that Valgrind will let your program copy around junk data as much as it likes. Memcheck will observe and keep track of the data, but doesn't complain. It doesn't complain until the use of uninitialized data might affect your program's externally-visible behaviour. Experiment with the following program to see how the generated reports look:
```
#include <iostream
using namespace std;

int main() {
    int x;
    bool z;
    int y = x + 5;
    if (x) {
        cout << "X is non-zero" << endl;
    }
    if (z) {
        cout << "Z is truthy" << endl;
    }
    cout << y << endl;
    return 0;
}
```

Another interesting example is this one:
```
#include <iostream

void foo(int x)
{
    std::cout<<x<<std::endl;
}

int main()
{
    int x;
    int r=4;
    int y=x+r;

    foo(y);
    
    return 0;
}
```
When I run this example, the valgrind report flags line 5 (the std::cout line), line 14 (the call to foo) in the stack trace.  It points to line 9 (the open brace on the main function) as the origin.  The origin is actually line 10, where the x is declared.  Note that the test for uninitialized values occurs when the value is used in a conditional, not on arithematic.  Thus, valgrind will not flag the computation of y.  A handy debugging trick is to insert "dummy" conditions to trigger the test, allowing you to test variables one by one to track down the problem.
```
#include <iostream

void foo(int x)
{
    std::cout<<x<<std::endl;
}

int zzzz=0; // dummy variable
int main()
{
    int x;
    int r=4;
    int y=x+r;
    if(x) zzzz++; // uninitialized error reported here
    if(r) zzzz++;
    if(y) zzzz++; // uninitialized error reported here

    foo(y);
    
    return 0;
}
```

### Illegal frees
Memcheck will also track the memory that has been deallocated so if you try to re-deallocate memory (as in a double free) it will catch that and report it to you. Consider the following program (doubleFree.cpp):
```
int main() {
    int *p = new int(10);

    delete p;
    delete p;

    return 0;
}
```
By inspection it is easy to see that `p` has been `delete`d twice, but let's run it through Valgrind anyways:
```
==15125== Invalid free() / delete / delete[] / realloc()
==15125==    at 0x4C3123B: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15125==    by 0x108727: main (doubleFree.cpp:5)
==15125==  Address 0x5b7dc80 is 0 bytes inside a block of size 4 free'd
==15125==    at 0x4C3123B: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15125==    by 0x108716: main (doubleFree.cpp:4)
==15125==  Block was alloc'd at
==15125==    at 0x4C3017F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15125==    by 0x1086FB: main (doubleFree.cpp:2)
==15125== 
==15125== 
==15125== HEAP SUMMARY:
==15125==     in use at exit: 0 bytes in 0 blocks
==15125==   total heap usage: 2 allocs, 3 frees, 72,708 bytes allocated
==15125== 
==15125== All heap blocks were freed -- no leaks are possible
==15125== 
==15125== For counts of detected and suppressed errors, rerun with: -v
==15125== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
```
The first (and only) error shows us that we have an `Invalid free() / delete / delete[] / realloc()` at `operator delete(void*)` on line (`doubleFree.cpp:5`) in the `main` function. This memory was `free'd` by `operator delete(void*)` on line (`doubleFree.cpp:4`) in the `main` function. The block was also originally `alloc'd` at `operator new(unsigned long)` on line `doubleFree.cpp:2` in the `main` function. We can get to **Memcheck-clean** by simply removing either of the `delete p;` statements.


### Memory leak detection
Memcheck has the following four leak kinds:
 * "Still reachable" - A start-pointer or chain of start-pointers to the block is found. The program could have *in theory* deallocated the memory.
 * "Definitely lost" - No pointer to the block can be found. There is no possible way to have deallocated this memory before the program exited. 
 * "Indirectly lost" - The block is lost, not because there are no pointers to it, but rather because all the blocks that point to it are themselves lost. For example, if you have a binary tree and the root node is lost, all it's children are indirectly lost. If you fixed the "definitely lost" block correctly these will be fixed as a side effect.
 * "Possibly lost" - A chain of one or more pointers to the block have been found, but at least one of them is an *interior* pointer. This is typically not good unless, through inspection, you identify the interior pointer and now how to access this memory. 

A **start-pointer** is a pointer at the beginning of a block whereas an **interior-pointer** points somewhere in the middle of the block (intentionally or unintentionally), for example:
```
int *p = new int[10]
int *ip = p + 2;
```
 * `p` points to the beginning of the array and is a start-pointer
 * `ip` points to the middle of the array and is an interior-pointer

There are many more kinds of interior pointers and you can read more about them on your own.

## Lab exercise
Now use what you have learned from this lab to get the `lineage` program to **Memheck-clean**. The program is a simplified family tree manager. It maintains a list of `Person`s in a `PersonList`. Each `Person` object maintains a set of pointers to his/her parents as well as to his/her children. The code contains several memory leaks. To compile:
```
$ g++ -g -O0 -fno-inline *.cpp -o lineage
```
\* The -fno-inline instructs the compiler to not inline any functions and makes it easier to see the function call chain.