memory debugging -- lost blocks

[jaapkroe]

Hi,

I've written a small program which finds saddle points on an energy surface and I am trying to get the memory management correct. I'm always messing this up.
The code works, and I've use valgrind to debug.
I get the strange result that for 100 iterations there seems to be no problem:

==15583== Memcheck, a memory error detector
==15583== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==15583== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==15583== Command: ./test -wn 100
==15583== 
==15583== Invalid read of size 8
==15583==    at 0x403AB1: void grow2d<gauss>(gauss**&, unsigned long&, int) (test.cpp:142)
==15583==    by 0x4029A9: main (test.cpp:236)
==15583==  Address 0x5937050 is 0 bytes after a block of size 16 alloc'd
==15583==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15583==    by 0x40254E: main (test.cpp:153)
==15583== 
==15583== Invalid read of size 8
==15583==    at 0x403B78: void grow2d<double>(double**&, unsigned long&, int) (test.cpp:142)
==15583==    by 0x402C4B: main (test.cpp:255)
==15583==  Address 0x59370a0 is 0 bytes after a block of size 16 alloc'd
==15583==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15583==    by 0x40256C: main (test.cpp:154)
==15583== 
==15583== 
==15583== HEAP SUMMARY:
==15583==     in use at exit: 0 bytes in 0 blocks
==15583==   total heap usage: 9,775 allocs, 9,775 frees, 179,838 bytes allocated
==15583== 
==15583== All heap blocks were freed -- no leaks are possible
==15583== 
==15583== For counts of detected and suppressed errors, rerun with: -v
==15583== ERROR SUMMARY: 28 errors from 2 contexts (suppressed: 4 from 4)

While for 1000 iterations, I get the following messages

==15596== Memcheck, a memory error detector
==15596== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==15596== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==15596== Command: ./test -wn 1000
==15596== 
==15596== Invalid read of size 8
==15596==    at 0x403AB1: void grow2d<gauss>(gauss**&, unsigned long&, int) (test.cpp:142)
==15596==    by 0x4029A9: main (test.cpp:236)
==15596==  Address 0x5937050 is 0 bytes after a block of size 16 alloc'd
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x40254E: main (test.cpp:153)
==15596== 
==15596== Invalid read of size 8
==15596==    at 0x403B78: void grow2d<double>(double**&, unsigned long&, int) (test.cpp:142)
==15596==    by 0x402C4B: main (test.cpp:255)
==15596==  Address 0x59370a0 is 0 bytes after a block of size 16 alloc'd
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x40256C: main (test.cpp:154)
==15596== 
==15596== 
==15596== HEAP SUMMARY:
==15596==     in use at exit: 2,120 bytes in 79 blocks
==15596==   total heap usage: 83,875 allocs, 83,796 frees, 1,365,438 bytes allocated
==15596== 
==15596== 76 bytes in 1 blocks are definitely lost in loss record 1 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x402D88: main (test.cpp:265)
==15596== 
==15596== 76 bytes in 1 blocks are definitely lost in loss record 2 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x402DA0: main (test.cpp:266)
==15596== 
==15596== 80 bytes in 5 blocks are indirectly lost in loss record 3 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x4029F7: main (test.cpp:239)
==15596== 
==15596== 80 bytes in 5 blocks are indirectly lost in loss record 4 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x402A13: main (test.cpp:240)
==15596== 
==15596== 120 bytes in 5 blocks are indirectly lost in loss record 5 of 13
==15596==    at 0x4C24DFA: operator new(unsigned long) (vg_replace_malloc.c:261)
==15596==    by 0x4029C8: main (test.cpp:237)
==15596== 
==15596== 152 bytes in 1 blocks are definitely lost in loss record 6 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x402DB8: main (test.cpp:267)
==15596== 
==15596== 304 bytes in 19 blocks are indirectly lost in loss record 7 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x402C71: main (test.cpp:256)
==15596== 
==15596== 304 bytes in 19 blocks are indirectly lost in loss record 8 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x402E81: main (test.cpp:274)
==15596== 
==15596== 304 bytes in 19 blocks are indirectly lost in loss record 9 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x402EAD: main (test.cpp:275)
==15596== 
==15596== 344 (64 direct, 280 indirect) bytes in 1 blocks are definitely lost in loss record 10 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x403A82: void grow2d<gauss>(gauss**&, unsigned long&, int) (test.cpp:141)
==15596==    by 0x4029A9: main (test.cpp:236)
==15596== 
==15596== 456 (152 direct, 304 indirect) bytes in 1 blocks are definitely lost in loss record 11 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x402DD0: main (test.cpp:268)
==15596== 
==15596== 456 (152 direct, 304 indirect) bytes in 1 blocks are definitely lost in loss record 12 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x402DE8: main (test.cpp:269)
==15596== 
==15596== 560 (256 direct, 304 indirect) bytes in 1 blocks are definitely lost in loss record 13 of 13
==15596==    at 0x4C24A72: operator new[](unsigned long) (vg_replace_malloc.c:305)
==15596==    by 0x403B49: void grow2d<double>(double**&, unsigned long&, int) (test.cpp:141)
==15596==    by 0x402C4B: main (test.cpp:255)
==15596== 
==15596== LEAK SUMMARY:
==15596==    definitely lost: 928 bytes in 7 blocks
==15596==    indirectly lost: 1,192 bytes in 72 blocks
==15596==      possibly lost: 0 bytes in 0 blocks
==15596==    still reachable: 0 bytes in 0 blocks
==15596==         suppressed: 0 bytes in 0 blocks
==15596== 
==15596== For counts of detected and suppressed errors, rerun with: -v
==15596== ERROR SUMMARY: 35 errors from 9 contexts (suppressed: 4 from 4)

Since the source is too large to post here (~300 lines) I've put it here:
http://petveturas.com/tmp/neb.cpp
From the valgrind output there seem to be at least two problems, (1) I'm apparently reading/writing to something of size 0 and (2) at some point memory is allocated which is not freed.

The problematic part seems to be the compute function (line 62) because if comment it out the 'leak' errors disappear but I don't allocate anything dynamically there so I don't understand why it's not destroyed outside the scope, the references are also not resized.
Another part where I'm really uncertain is the function grow2d (line 138), perhaps the real problem is there.
I initially wrote it as:

  size_t size = 2*n+1;
  type** newlist = new type*[size];

  size_t size = 2*n+1;
  type** newlist = new type*[size+1];

But the +1 seems necessary..
Sorry for the long code, but I'm not sure how to reduce it to a minimal example.
I hope somebody can give some hints/advice on what I'm doing wrong here.

Thanks in advance!

Jaap

[ne555]

I suggest you to use std::vector instead.

gauss **gaus_list ¿why a pointer to a pointer?
A little encapsulation would be good too (let the class to manage its state)

[jaapkroe]

Thanks. That was a remnant of old code, because gauss_list was initially a 2d-array of doubles.
It should be

gauss *gauss_list

of course.
I am trying to convert the code to std::vector, but again I have more issue I don't understand.
Could you tell me why the following example fails (

double free or corruption

)

#include <stdlib.h>
#include <vector>

using namespace std;

struct gauss {
  double *mu;
  double h;
  ~gauss() {
    delete[] mu;
  }
  gauss(size_t s) {
    _size = s;
    mu = new double[_size];
  }
  private: 
    int _size;
};

int main (int argc, char* argv[]) {
  vector<gauss> gauss_list; 
  size_t s;
  s = 2;
  
  for(int i=0;i<10;i++) {
    gauss_list.push_back(gauss(s));
  }
}

[Moschops]

http://stackoverflow.com/questions/2814013/double-free-inside-of-a-destructor-upon-adding-to-a-vector

[jaapkroe]

Ah ok.. I was missing some class functionality, it works like this.

#include <stdlib.h>
#include <vector>

using namespace std;

struct gauss {
  double *mu;
  double h;
  ~gauss() {
    delete[] mu;
  }
  gauss(size_t s) {
    _size = s;
    mu = new double[_size];
  }
  gauss(const gauss& other) {
    _size = other._size;
    mu = new double[_size];
    for(int i=0;i<_size;i++) mu[i] = other.mu[i];
    h = other.h;
  }
  gauss& operator=(const gauss& other) {
    if (&other==this) return *this ;
    if(_size != other._size) {
      delete[] mu;
      _size = other._size;
      mu = new double[_size];
    }
    for(int i=0;i<_size;i++) mu[i] = other.mu[i];
    h = other.h;
    return *this;
  }
  private:
    int _size;
};

int main (int argc, char* argv[]) {
  vector<gauss> gauss_list;
  size_t s;
  s = 2;

  for(int i=0;i<10;i++) {
    gauss_list.push_back(gauss(s));
  }
}

[jaapkroe]

Ok solved! Thanks for the suggestions.
In the end I rewrote most of it with vectors, but the main problem was that I had a return statement inside a loop in main before I freed the memory so there the memory was lost..

Program can be found here:
http://petveturas.com/prog/neb-cpp/neb.cpp

[ne555]

You could still replace mu and sigma by vectors.

[jaapkroe]

Hmm I'm not sure. This is the main part of the program which should be fast and low memory. I think the vector class is about the same for speed but has some memory overhead compared to dynamics arrays to be able to iterate back and forth. Is this correct or are am I biased against vectors?

[ne555]

You are thinking in linked list.
To iterate in a vector you just increment a pointer. Basically, it's just a wrapper for a dynamic array,