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::AddSensation(), MaxNode::AddSensations(),
MaxNode::ClearSequence() and MaxNode::SensationSequence().

If someone could explain why the deletes in MaxNode::ClearSequence() 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_SensationSequence.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 (((TaxiSensation*)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::const_iterator i = sensations.begin();
i != sensations.end();
++i)
cerr << " " << (*i)->ToString() << "\n";
}

// MaxNode::AddSensation
void AddSensation( const Sensation* const p_sensation )
{ m_SensationSequence.push_front( p_sensation->Clone() ); }

// MaxNode::AddSensations
void AddSensations( seq_type sensations )
{
m_SensationSequence.insert( m_SensationSequence.begin(),
sensations.begin(),
sensations.end() );
}

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

m_SensationSequence.clear();
}

// MaxNode::SensationSequence
const seq_type SensationSequence() const
{ return m_SensationSequence; }

vector<MaxNode*> m_Children;

protected:
std::string m_Name;
seq_type m_SensationSequence;
};


//////////////////////////////////////////////////////////////////////
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:air< 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.push_back( pair<MaxNode*,float>( node_A, 0 ) );

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

cerr << "Filling stack";
while (active_nodes.back().first->IsInternal())
{
cerr << ".";
pair<MaxNode*,float> p =
pair<MaxNode*,float>( active_nodes.back().first->m_Children[0], n );
active_nodes.push_back( p );
}
(active_nodes.back().first)->AddSensation( sens );

cerr << "\nCheck for termination\n";
for (stack_type::reverse_iterator i = active_nodes.rbegin();
i != active_nodes.rend();
/*noop*/)
{

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

// 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.front().first)
exit(0);
else
{
MaxNode* child = i->first;
++i;
i->first->Update( i->second, child->SensationSequence() );

// 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->AddSensations( (child->SensationSequence()) );
child->ClearSequence();
active_nodes.erase( i.base(), active_nodes.end() );
}
}
else
{
++i;
}
}
}
return 0;
}

 

[Gianni Mariani]

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::AddSensation(), MaxNode::AddSensations(),
MaxNode::ClearSequence() and MaxNode::SensationSequence().

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

..... 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<Sensation
const*, std::allocator<Sensation const*> >) (segf.cpp:84)
==8090== by 0x80497A7: main (segf.cpp:195)
==8090== by 0x42017498: __libc_start_main (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_malloc.c:233)
==8090== by 0x804B392: TaxiSensation::~TaxiSensation() (in
/home/gianni/limbo/asmx/asprin/src/austria/examples/segf)
==8090== by 0x804A38E: MaxNode::ClearSequence() (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::const_iterator i = sensations.begin();
i != sensations.end();
++i)
cerr << " " << (*i)->ToString() << "\n"; // <<<<<<<<< line 84
}

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

 

[Martin Magnusson]

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

That program looks interesting. Too bad it's only for Linux.

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

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]

That program looks interesting. Too bad it's only for Linux.


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

#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]

That program looks interesting. Too bad it's only for Linux.

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.

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.

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