Why is it not OK to delete here?

[Martin Magnusson]

I'm getting segmentation faults when trying to fix a memory leak in my
program. The problem is related to lists of pointers which get passed
around between objects.

Here is a description of how the code works:
I have a stack consisting of nodes and arguments, much like a function
execution stack. In this example there are only three nodes on the
stack. For each run through the loop, a copy of the current sensation is
written to the top-most node, node_C (which is a MaxLeaf). This
sensation object is then copied to the second node from the top, node_B,
and is prepended to a list which node_B keeps. After the copy, node_C's
copy of the sensation is deleted to prevent memory leaking. When node_B
terminates, it passes its sensation list up to node_A. Here, the list as
the correct number of elements, but they all seem to be invalid. When
trying to call the ToString() method on the sensations in the list, I
get a segmentation fault. If I never call delete this doesn't happen.

I'm sorry for the lengthy code, but I have tried to delete all that
isn't necessary.

The problem has to do with the functions TaxiSensation:: Clone(),
MaxNode::AddSen sation(), MaxNode::AddSen sations(),
MaxNode::ClearS equence() and MaxNode::Sensat ionSequence().

If someone could explain why the deletes in MaxNode::ClearS equence() are
bad, I'd be very grateful! The code should compile with no problems,
just "g++ test.cpp" works in any case.

/ martin

// Code begins here: /////////////////////////////////////////////////

#include <sstream>
#include <iostream>
#include <vector>
#include <list>
using namespace std;

//////////////////////////////////////////////////////////////////////
class Sensation {
public:
Sensation() {}
virtual ~Sensation() {}

virtual std::string ToString() const = 0;

virtual Sensation* Clone() const = 0;
};


//////////////////////////////////////////////////////////////////////
class TaxiSensation : public Sensation
{
public:
TaxiSensation()
{ m_Walls = vector<int>( 25, 0 ); }

TaxiSensation* Clone() const
{ return new TaxiSensation(* this); }

std::string TaxiSensation:: ToString() const
{ return "(this is a sensation)"; }

int X;

private:
vector<int> m_Walls; // Positions of walls.

};


//////////////////////////////////////////////////////////////////////
typedef list<const Sensation*> seq_type;


//////////////////////////////////////////////////////////////////////
class MaxNode
{
public:
MaxNode( std::string name = "NN" )
{
m_Name = name;
m_SensationSequ ence.clear();
}

virtual ~MaxNode()
{}

void AddChild( MaxNode* p_child )
{ m_Children.push _back( p_child ); }

virtual bool IsTerminated( const float argument,
const Sensation* p_sensation ) const
{
if (((TaxiSensatio n*)p_sensation)->X >= 2)
{
cerr << m_Name << " terminated.\n";
return true;
}
else
return false;
}

virtual bool IsInternal() const
{ return true; }

virtual void Update( const float argument,
const seq_type sensations)
{
cerr << "Updating " << m_Name << "\n";
for (seq_type::cons t_iterator i = sensations.begi n();
i != sensations.end( );
++i)
cerr << " " << (*i)->ToString() << "\n";
}

// MaxNode::AddSen sation
void AddSensation( const Sensation* const p_sensation )
{ m_SensationSequ ence.push_front ( p_sensation->Clone() ); }

// MaxNode::AddSen sations
void AddSensations( seq_type sensations )
{
m_SensationSequ ence.insert( m_SensationSequ ence.begin(),
sensations.begi n(),
sensations.end( ) );
}

// Is there a problem here? Is it not OK to delete the list elements?
void ClearSequence()
{
for (seq_type::cons t_iterator i = m_SensationSequ ence.begin();
i != m_SensationSequ ence.end();
++i)
delete *i;

m_SensationSequ ence.clear();
}

// MaxNode::Sensat ionSequence
const seq_type SensationSequen ce() const
{ return m_SensationSequ ence; }

vector<MaxNode* > m_Children;

protected:
std::string m_Name;
seq_type m_SensationSequ ence;
};


//////////////////////////////////////////////////////////////////////
class MaxLeaf : public MaxNode
{
public:
MaxLeaf( std::string name = "NN" )
{ m_Name = name; }

virtual ~MaxLeaf() {}

bool IsInternal() const
{ return false; }

bool IsTerminated( const float argument, const Sensation* p_sens) const
{ return true; }

};


/*============== =============== =============== =============== =============*/
int main()
{
typedef std::list< std::pair< MaxNode*, float > > stack_type;
stack_type active_nodes;

MaxNode* node_A = new MaxNode( "Node A" );
MaxNode* node_B = new MaxNode( "Node B" );
MaxLeaf* node_C = new MaxLeaf( "Node C" );

node_A->AddChild( node_B );
node_B->AddChild( node_C );

TaxiSensation* sens = new TaxiSensation;

active_nodes.pu sh_back( pair<MaxNode*,f loat>( node_A, 0 ) );

for (int n = 0; n < 5; ++n)
{
((TaxiSensation *)sens)->X = n;

cerr << "Filling stack";
while (active_nodes.b ack().first->IsInternal() )
{
cerr << ".";
pair<MaxNode*,f loat> p =
pair<MaxNode*,f loat>( active_nodes.ba ck().first->m_Children[0], n );
active_nodes.pu sh_back( p );
}
(active_nodes.b ack().first)->AddSensation ( sens );

cerr << "\nCheck for termination\n";
for (stack_type::re verse_iterator i = active_nodes.rb egin();
i != active_nodes.re nd();
/*noop*/)
{

// First update the leaf node, node_C
if (!(i->first->IsInternal() ))
{
i->first->Update( i->second,
i->first->SensationSeque nce() );
}

// Also update the parent node of any node that is terminated
// (node_C is always terminated, node_B and node_A terminates
// the third time through this loop.
if (i->first->IsTerminated ( i->second, sens ))
{
if (i->first == active_nodes.fr ont().first)
exit(0);
else
{
MaxNode* child = i->first;
++i;
i->first->Update( i->second, child->SensationSeque nce() );

// Prepend a Sensation to (*i)'s list.
// node_B gets one Sensation at a time here, while node_A
// should get a list of 3 elements when node_B terminates.
i->first->AddSensation s( (child->SensationSeque nce()) );
child->ClearSequence( );
active_nodes.er ase( i.base(), active_nodes.en d() );
}
}
else
{
++i;
}
}
}
return 0;
}

[Gianni Mariani]

Re: Why is it not OK to delete here?

Martin Magnusson wrote:[color=blue]
> I'm getting segmentation faults when trying to fix a memory leak in my
> program. The problem is related to lists of pointers which get passed
> around between objects.
>
> Here is a description of how the code works:
> I have a stack consisting of nodes and arguments, much like a function
> execution stack. In this example there are only three nodes on the
> stack. For each run through the loop, a copy of the current sensation is
> written to the top-most node, node_C (which is a MaxLeaf). This
> sensation object is then copied to the second node from the top, node_B,
> and is prepended to a list which node_B keeps. After the copy, node_C's
> copy of the sensation is deleted to prevent memory leaking. When node_B
> terminates, it passes its sensation list up to node_A. Here, the list as
> the correct number of elements, but they all seem to be invalid. When
> trying to call the ToString() method on the sensations in the list, I
> get a segmentation fault. If I never call delete this doesn't happen.
>
> I'm sorry for the lengthy code, but I have tried to delete all that
> isn't necessary.
>
> The problem has to do with the functions TaxiSensation:: Clone(),
> MaxNode::AddSen sation(), MaxNode::AddSen sations(),
> MaxNode::ClearS equence() and MaxNode::Sensat ionSequence().
>
> If someone could explain why the deletes in MaxNode::ClearS equence() are
> bad, I'd be very grateful! The code should compile with no problems,
> just "g++ test.cpp" works in any case.
>[/color]

..... snip ...

Valgrind is your friend. (Julian Seward is my hero)

OK - here is the valgrind output.

==8090== Memcheck, a.k.a. Valgrind, a memory error detector for x86-linux.
==8090== Copyright (C) 2002-2003, and GNU GPL'd, by Julian Seward.
==8090== Using valgrind-20030725, a program supervision framework for
x86-linux.
==8090== Copyright (C) 2000-2003, and GNU GPL'd, by Julian Seward.
==8090== Estimated CPU clock rate is 798 MHz
==8090== For more details, rerun with: -v
==8090==
Filling stack..
Check for termination
Updating Node C
(this is a sensation)
Updating Node B
(this is a sensation)
Filling stack.
Check for termination
Updating Node C
(this is a sensation)
Updating Node B
(this is a sensation)
Filling stack.
Check for termination
Updating Node C
(this is a sensation)
Updating Node B
(this is a sensation)
Node B terminated.
Updating Node A
==8090== Invalid read of size 4
==8090== at 0x804BCEB: MaxNode::Update (float, std::list<Sensa tion
const*, std::allocator< Sensation const*> >) (segf.cpp:84)
==8090== by 0x80497A7: main (segf.cpp:195)
==8090== by 0x42017498: __libc_start_ma in (in /lib/i686/libc-2.2.5.so)
==8090== by 0x8048C8C: (within
/home/gianni/limbo/asmx/asprin/src/austria/examples/segf)
==8090== Address 0x4191F73C is 0 bytes inside a block of size 20 free'd
==8090== at 0x40026C23: operator delete(void*) (vg_replace_mal loc.c:233)
==8090== by 0x804B392: TaxiSensation:: ~TaxiSensation( ) (in
/home/gianni/limbo/asmx/asprin/src/austria/examples/segf)
==8090== by 0x804A38E: MaxNode::ClearS equence() (segf.cpp:105)
==8090== by 0x8049873: main (segf.cpp:201)
pure virtual method called
Abort (core dumped)

... Invalid read of size 4 (segf.cpp:84)

For some reason, the object being pointed to by the iterator is dead -
this is mot likely when the vtable was being accessed:

virtual void Update( const float argument,
const seq_type sensations)
{
cerr << "Updating " << m_Name << "\n";
for (seq_type::cons t_iterator i = sensations.begi n();
i != sensations.end( );
++i)
cerr << " " << (*i)->ToString() << "\n"; // <<<<<<<<< line 84
}

It seems like you simply delete them before you call "Update".

[Martin Magnusson]

Re: Why is it not OK to delete here?

Gianni Mariani wrote:[color=blue]
> Valgrind is your friend. (Julian Seward is my hero)[/color]
That program looks interesting. Too bad it's only for Linux.
[color=blue]
> It seems like you simply delete them before you call "Update".[/color]
I do call delete on some pointers, but I would have thought that there
were copies of them, which were not deleted, which are passed to the
Update function. I realize now though, that although I pass a copy of
the list to the other node, no deep copy of the pointers are made, so
they are still invalidated when I call delete. Traversing the list and
calling Clone again on each of the pointers seems to fix this.

I still get weird crashes at other points in the program now though...
and gdb isn't helping me much there either, but I guess I should go to
another group to discuss that.

Thanks for the input.

/ martin

[lilburne]

Re: Why is it not OK to delete here?

Martin Magnusson wrote:
[color=blue]
> Gianni Mariani wrote:
>[color=green]
>> Valgrind is your friend. (Julian Seward is my hero)[/color]
>
> That program looks interesting. Too bad it's only for Linux.
>[color=green]
>> It seems like you simply delete them before you call "Update".[/color]
>
> I do call delete on some pointers, but I would have thought that there
> were copies of them, which were not deleted, which are passed to the
> Update function. I realize now though, that although I pass a copy of
> the list to the other node, no deep copy of the pointers are made, so
> they are still invalidated when I call delete. Traversing the list and
> calling Clone again on each of the pointers seems to fix this.
>
> I still get weird crashes at other points in the program now though...
> and gdb isn't helping me much there either, but I guess I should go to
> another group to discuss that.
>
> Thanks for the input.
>
> / martin
>
>
>[/color]
#include <cassert>

const int VALID = 98765;
const int DEAD = 0xdeaddead;

class validity {
int alive;
public:
validity() { alive = VALID; }
~validity() { alive = DEAD;}
bool valid(void * p);
};

bool validity::valid (void* p)
{
assert(p != 0);
return alive == VALID;
}

Stick something like the above (which is cheap n cheerful)
in your classes:

class A {
validity vc;
public:
};

and add:

assert(vc.valid (this));

as the first statement of all methods. It will provide some
simple checks that objects accessed via pointers have been
created, that they haven't been deleted, that you haven't
been returned a reference to a local, and it might provide
some check on memory getting trampled.

[Gianni Mariani]

Re: Why is it not OK to delete here?

Martin Magnusson wrote:[color=blue]
> Gianni Mariani wrote:
>[color=green]
>> Valgrind is your friend. (Julian Seward is my hero)[/color]
>
> That program looks interesting. Too bad it's only for Linux.[/color]

But it's easy to have a linux box and if the code is portable (like
yours - good work btw) then you can allways pop it onto a linux box.
[color=blue]
>[color=green]
>> It seems like you simply delete them before you call "Update".[/color]
>
> I do call delete on some pointers, but I would have thought that there
> were copies of them, which were not deleted, which are passed to the
> Update function. I realize now though, that although I pass a copy of
> the list to the other node, no deep copy of the pointers are made, so
> they are still invalidated when I call delete. Traversing the list and
> calling Clone again on each of the pointers seems to fix this.
>
> I still get weird crashes at other points in the program now though...
> and gdb isn't helping me much there either, but I guess I should go to
> another group to discuss that.
>
> Thanks for the input.[/color]

You might want to consider using reference counting and smart pointers.