Solution

If we just compile and run the program, we obtain a lot of output, structured more or less as follows:

3.5
2.5
1.5
3.60739e-313
0
[...]
0
3.66616e-307
5.09279e-313
nan
nan
[...]
Segmentation fault

This is usually known as garbage output. The first three lines are the expected output, but we fail to understand why did the program not stop on the second loop when it was told. Furthermore, why the Segmentation fault?

We build the program with the debugging flag set and then debug it using valgrind: . We obtain the usual garbage interspersed with meaningful valgrind messages. We can run it again saving the standard error stream to the standard output and redirecting it through a pager: . valgrind's messages are:

==31179== Invalid write of size 8
==31179==    at 0x8048681: main (segmentationfault.cxx:6)
==31179==  Address 0x426A030 is 0 bytes after a block of size 8 alloc'd
==31179==    at 0x401A878: operator new(unsigned) (vg_replace_malloc.c:163)
==31179==    by 0x804864D: main (segmentationfault.cxx:4)
==31179== 
==31179== Invalid read of size 4
==31179==    at 0x804869E: main (segmentationfault.cxx:9)
==31179==  Address 0x426A03C is 12 bytes after a block of size 8 alloc'd
==31179==    at 0x401A878: operator new(unsigned) (vg_replace_malloc.c:163)
==31179==    by 0x804864D: main (segmentationfault.cxx:4)
==31179== 
==31179== Invalid read of size 4
==31179==    at 0x80486A1: main (segmentationfault.cxx:9)
==31179==  Address 0x426A038 is 8 bytes after a block of size 8 alloc'd
==31179==    at 0x401A878: operator new(unsigned) (vg_replace_malloc.c:163)
==31179==    by 0x804864D: main (segmentationfault.cxx:4)
==31179== 
==31179== Process terminating with default action of signal 11 (SIGSEGV)
==31179==  Bad permissions for mapped region at address 0x4262FFC
==31179==    at 0x804869E: main (segmentationfault.cxx:9)

The first error, Invalid write, is very serious. It means we are writing on heap memory we had not allocated. This usually results immediately in unpredictable behaviour and the fatal segmentation fault error. We can find out at which step of the loop the error arises by inserting a print statement before line 6, rebuilding, and running valgrind again. We see immediately that the Invalid write occurs when i has value 1. It is important to remove the temporary print statement in order to keep the line numbers valid. The fact that d[0] exists in memory but d[1] is invalid should immediately tell us that we failed to allocate enough memory. In particular, we issued the C++ statement , which reserves space on the heap for just one double floating point number. What we really wanted to do, in fact, was to have space for an array of size 3: .

We now rebuild and re-run the program. Again we get garbage output. valgrind reveals that the first error has been fixed:

==31348== Invalid read of size 4
==31348==    at 0x804869E: main (segmentationfault.cxx:9)
==31348==  Address 0x426A024 is 4 bytes before a block of size 24 alloc'd
==31348==    at 0x401ACE0: operator new[](unsigned) (vg_replace_malloc.c:195)
==31348==    by 0x804864D: main (segmentationfault.cxx:4)
==31348== 
==31348== Invalid read of size 4
==31348==    at 0x80486A1: main (segmentationfault.cxx:9)
==31348==  Address 0x426A020 is 8 bytes before a block of size 24 alloc'd
==31348==    at 0x401ACE0: operator new[](unsigned) (vg_replace_malloc.c:195)
==31348==    by 0x804864D: main (segmentationfault.cxx:4)
==31348== 
==31348== Process terminating with default action of signal 11 (SIGSEGV)
==31348==  Bad permissions for mapped region at address 0x4262FFC
==31348==    at 0x804869E: main (segmentationfault.cxx:9)

The Invalid read error is not as serious as the Invalid write, but almost as bad. It means that we are reading from unallocated memory.

To see what is happening we launch ddd and we set a breakpoint at line 9
. Then we start debugging run. Since the problem is that the loop does not seem to terminate as it should, we want to keep track of the counter i. With we can have i's value printed after each step . After a few steps, we find that i has value 0. Instead of terminating, the loop continues with i set at 4294967295. Naturally, the condition i >= 0 is still verified so that's the reason why the loop continues. The strange value in i is due to the fact that the counter was declared unsigned int, which means that it can never take negative values -- in other words, 0 is the minimum value that i can take. When an unsigned int is set at 0 (as i in our case) and then a decrement operator is applied to it (i- within the for statement), it is set to ``one less than the minimum value'', which by definition is taken to be the maximum value (i.e. a large, positive value). Thus the bug is explained. It can be fixed by taking away the unsigned qualifier.

We rebuild, re-run the program and find that it works without any trouble whatsoever:

3.5
2.5
1.5

The third bug is much harder to find, since the behaviour of the program is now correct. We can identify it by enclosing the whole program into an endless loop:

int main(int argc, char** argv) {
  using namespace std;
  while(true) {
    double* d = new double[3];
    for(int i = 0; i < 3; i++) {
      d[i] = 1.5 + i;
    }
    for(int i = 2; i >= 0; i--) {
      cout << d[i] << endl;
    }
  }
}

We now build and run the program, and in another shell we launch the shell command . In the last column of this window we find some program names which are running on the computer. We find the line relative to segmentationfault:

31467 liberti   25   0  9044 7404  764 R 18.9  1.2   0:04.85 segmentationfau

If we let our program run for a few seconds (minutes) we notice that on the column marked %MEM the percentage of memory dedicated to segmentationfault always increases. If we let this program run for a long time, it gobbles up the whole computer memory. On certain operating systems, this amounts to freezing the computer dead. On others, the process is automatically killed. In any case, we do not want any program of ours to follow this behaviour, called memory leak. It is easy to find that the cause of this bug is that we forgot to deallocate memory after the allocation. We insert the line right before the end of the program to fix this bug.