About valgrind (memory checker)
-------------------------------

If you need to track down a bug where memory is being corrupted or leaked, there
is a useful tool called valgrind on the linux machines (link to its home page
from the Computing Resources page). 

A memory leak shows itself to you as where the memory was allocated and never
deleted. Valgrind points you to the function to investigate further.  Besides
checking for memory leaks, valgrind tells you when you read (access memory),
write outside the bounds of an array (in general, memory that is not yours),
or use uninitialized memory (garbage).

For example, if you write outside the bounds of an array, it is possible that
you overwrite the memory of another array or object, or memory needed for the
delete operation.  Typically the size of the array is stored in memory just
before the array contents.  Suppose you have array A. Now suppose array B is
stored in memory just after A.  If you write outside of A, you may overwrite
where the size is stored for B. Then, when you try to delete array B, you crash.

To get valgrind to give line numbers where the errors occur, use the -g option.
For example:  g++ -g leak.cpp
To use valgrind, after you compile, enter:  valgrind ./a.out
This will execute your program, give output, as well as run it through valgrind.
Here is a simple program that reads and writes outside the bounds of the array,
attempts to use garbage memory, and has a memory leak:

PROGRAM (file leak.cpp):

line  1   #include <iostream>
line  2   using namespace std;
line  3   
line  4   void messAroundMore(int p[]) {
line  5      p[8] = 100;       // invalid write
line  6      p[2] = p[8];      // invalid read
line  7      cout << p[3];     // attempt to use garbage (uninitialized memory)
line  8   }
line  9   
line 10   void messAround(int p[]) {
line 11      messAroundMore(p);
line 12   }
line 13   
line 14   int main() {
line 15      int* p = new int[5];    // memory leak, never deleted
line 16      messAround(p);
line 17      return 0;
line 18   }

VALGRIND OUTPUT 

. . . with commentary by me. Note that there is a lot of output and it is best
to ignore all the extra output and just focus on where the problem occurs.
Since most of your functions are short, that is usually enough to guide you
to where the problem happens. If the -g option is used when compiling, you
will be given the line number of the error code.

To make it easier to read, I have removed the numbers that it puts at the start
of each line. Commentary by me starts with ***** .

-----------------------------------------------------------------------------

Memcheck, a memory error detector
Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
Using Valgrind-3.21.0 and LibVEX; rerun with -h for copyright info
Command: ./a.out

Invalid write of size 4
   at 0x40078A: messAroundMore(int*) (leak.cpp:5)
   by 0x4007D1: messAround(int*) (leak.cpp:11)
   by 0x4007F6: main (leak.cpp:16)
 Address 0x5b4eca0 is 12 bytes after a block of size 20 alloc'd
   at 0x4C39C63: operator new[](unsigned long) (vg_replace_malloc.c:714)
   by 0x4007E6: main (leak.cpp:15)

***** Commentary -- What is useful here is knowing that the invalid write is in
***** messAroundMore() on line 5. The call stack is shown, but you only care 
***** about the top of the stack, i.e., the function listed first. Ignore the 
***** detailed information. This tells you that it is in this function that you 
***** are writing outside of your array. That's where the error is.

Invalid read of size 4
   at 0x40079C: messAroundMore(int*) (leak.cpp:6)
   by 0x4007D1: messAround(int*) (leak.cpp:11)
   by 0x4007F6: main (leak.cpp:16)
 Address 0x5b4eca0 is 12 bytes after a block of size 20 alloc'd
   at 0x4C39C63: operator new[](unsigned long) (vg_replace_malloc.c:714)
   by 0x4007E6: main (leak.cpp:15)

***** Commentary -- Same as before, what is useful here is knowing that the
***** invalid read is in messAroundMore(), line 6. Ignore the detailed 
***** information. Accessing p[8] is not a valid access.

Conditional jump or move depends on uninitialised value(s)
   at 0x4F57292: 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/lib64/libstdc++.so.6.0.25)
   by 0x4F651D8: std::ostream& std::ostream::_M_insert<long>(long) (in /usr/lib64/libstdc++.so.6.0.25)
   by 0x4007B6: messAroundMore(int*) (leak.cpp:7)
   by 0x4007D1: messAround(int*) (leak.cpp:11)
   by 0x4007F6: main (leak.cpp:16)

***** Commentary -- What is useful here is knowing that the uninitialized value
***** (garbage) is in messAroundMore(), line 7. Skip all the I/O stuff until you
***** get to the function you wrote. When the bug uses library functions like 
***** cout, there is a lot of ostream output. I train my eyes to skip over it.

Use of uninitialised value of size 8
   at 0x4F56D3E: ??? (in /usr/lib64/libstdc++.so.6.0.25)
   by 0x4F572BC: 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/lib64/libstdc++.so.6.0.25)
   by 0x4F651D8: std::ostream& std::ostream::_M_insert<long>(long) (in /usr/lib64/libstdc++.so.6.0.25)
   by 0x4007B6: messAroundMore(int*) (leak.cpp:7)
   by 0x4007D1: messAround(int*) (leak.cpp:11)
   by 0x4007F6: main (leak.cpp:16)

***** Commentary -- Just in case the last error didn't alert you to the problem,
***** another error is given saying that you are using uninitialized memory in
***** messAroundMore(), line 7. Again, a lot of ostream output.

***** After this, it gave two more "Conditional jump or move depends on 
***** uninitialised value(s)" errors.  I would have already fixed the problem
***** from seeing the first error, which would have gotten rid of four errors
***** when I used valgrind again. It is common to have multiple errors.

0

***** This was my actual output. The garbage printed was interpreted as zero.

HEAP SUMMARY:
    in use at exit: 20 bytes in 1 blocks
  total heap usage: 3 allocs, 2 frees, 73,748 bytes allocated

LEAK SUMMARY:
   definitely lost: 20 bytes in 1 blocks
   indirectly lost: 0 bytes in 0 blocks
     possibly lost: 0 bytes in 0 blocks
   still reachable: 0 bytes in 0 blocks
        suppressed: 0 bytes in 0 blocks
Rerun with --leak-check=full to see details of leaked memory

Use --track-origins=yes to see where uninitialised values come from
For lists of detected and suppressed errors, rerun with: -s
ERROR SUMMARY: 6 errors from 6 contexts (suppressed: 0 from 0)

***** Commentary -- You can see there is a memory leak because 20 bytes are
***** definitely lost. For details, enter:  valgrind --leak-check=full ./a.out

***** There are 3 allocations (new) and only 2 frees (delete) which means that
***** one of the "new" in the program does not have a matching "delete".
***** Debugging for the leak(s) can be challenging which is why it is important 
***** to continually valgrind as you go and not at the end of a large program.

***** Don't worry about any suppressed errors. They usually aren't real errors,
***** more like warnings for things that could be a problem, but are not. 
***** For example, you don't initialize a variable because you know you'll
***** be initializing it later. Valgrind doesn't know that.