mrclng mrclng - 3 years ago 33
C++ Question

Why do these visit methods cause memory leaks?

I am working on a medium sized C++ framework for expression parsing that is being used for storing and manipulating optimization problems.
The framework consists of three parts:


  1. A DSL and corresponding parser structures (not of interest here)

  2. The datastructure, consisting of a hierarchy of different node types

  3. A number of operations that are implemented as visitors



A valgrind test of a program implementing this framework reported a number of memory leaks that could be tracked down to one of the visitors, namely the
copyCreator
, more specifically to a visit method for a
forallNode
.

The relevant code segments are listed here, while a complete MWE (due to the complexity of the code still 445 loc) can be found here.

template<typename copyNodeType>
struct copyCreator : public baseVisitor {
copyCreator(scope * globalScope) : baseVisitor(globalScope) {}
copyCreator(scope * globalScope, node * firstVisit) :
baseVisitor(globalScope) {
firstVisit->accept(*this);
}

~copyCreator() {
copy.reset();
for(auto ptr : openList) {
delete ptr;
}
}

std::unique_ptr<copyNodeType> copy = 0;
vector<nonterminalNode *> openList;
bool error = true;

// push to tree
template<typename nodeType>
void push(nodeType * ptr) {
if (copy) {
openList.back()->add_child(ptr); // if root is set, append to tree
}
else {
auto temp = dynamic_cast<copyNodeType *>(ptr);
if(temp) {
copy = std::unique_ptr<copyNodeType>(temp);
error = false;
}
}
}

// ...

void visit(struct forallNode & nod) {
auto scopeCopy = new scope;
nodeFinder<realVariableSymbol> varFinder(nod.localScope);
varFinder.maxDepth = 0;
for(auto member : nod.localScope->members) {
varFinder.elems.clear();
member.second->accept(varFinder);
if(varFinder.elems.empty()) {
delete scopeCopy;
return;
}
else {
//FIXME: MEMLEAK
copyCreator<setNode> mySet(globalScope, varFinder.elems[0]->hostSet.get());
if(mySet.copy.get()) {
scopeCopy->define(member.first, new realVariableSymbol(mySet.copy.release()));
continue;
}
nodeFinder<realIdentifierNode> uDefSet(globalScope, varFinder.elems[0]->hostSet.get(), 0);
if(!uDefSet.elems.empty()) {
scopeCopy->define(member.first, new realVariableSymbol(new realSetIdentifierNode(uDefSet.elems[0]->id)));
continue;
}
}
}
auto next = new forallNode(scopeCopy); //FIXME: MEMLEAK
push(next);
openList.push_back(next);
nod.child->accept(*this); //FIXME: MEMLEAK
openList.pop_back();
};


After constructing the used elements, calling

// These three versions of calling the copyCreator cause memleaks!
copyCreator<programNode> cpy0(&globalScope);
p.accept(cpy0);

copyCreator<programNode> cpy1(&globalScope);
cpy1.visit(p);

copyCreator<programNode> cpy2(&globalScope, a);
return 0;


in main causes the following valgrind report for the MWE:

HEAP SUMMARY:
in use at exit: 496 bytes in 13 blocks
total heap usage: 68 allocs, 55 frees, 74,840 bytes allocated

24 bytes in 1 blocks are definitely lost in loss record 4 of 13
at 0x4C2E1FC: operator new(unsigned long) (vg_replace_malloc.c:334)
by 0x407BE4: copyCreator<programNode>::visit(realConstantNode&) (in /home/mala01/test/a.out)
by 0x4025F9: realConstantNode::accept(visitor&) (in /home/mala01/test/a.out)
by 0x408119: copyCreator<programNode>::visit(forallNode&) (in /home/mala01/test/a.out)
by 0x40290B: forallNode::accept(visitor&) (in /home/mala01/test/a.out)
by 0x403CE6: copyCreator<programNode>::copyCreator(scope*, node*) (in /home/mala01/test/a.out)
by 0x4014A7: main (in /home/mala01/test/a.out)

40 bytes in 1 blocks are definitely lost in loss record 6 of 13
at 0x4C2E1FC: operator new(unsigned long) (vg_replace_malloc.c:334)
by 0x40938D: copyCreator<setNode>::visit(realIdentifierNode&) (in /home/mala01/test/a.out)
by 0x401CC5: realIdentifierNode::accept(visitor&) (in /home/mala01/test/a.out)
by 0x40869E: copyCreator<setNode>::copyCreator(scope*, node*) (in /home/mala01/test/a.out)
by 0x407E24: copyCreator<programNode>::visit(forallNode&) (in /home/mala01/test/a.out)
by 0x40290B: forallNode::accept(visitor&) (in /home/mala01/test/a.out)
by 0x403BF8: copyCreator<programNode>::visit(programNode&) (in /home/mala01/test/a.out)
by 0x402B79: programNode::accept(visitor&) (in /home/mala01/test/a.out)
by 0x401436: main (in /home/mala01/test/a.out)

40 bytes in 1 blocks are definitely lost in loss record 7 of 13
at 0x4C2E1FC: operator new(unsigned long) (vg_replace_malloc.c:334)
by 0x40938D: copyCreator<setNode>::visit(realIdentifierNode&) (in /home/mala01/test/a.out)
by 0x401CC5: realIdentifierNode::accept(visitor&) (in /home/mala01/test/a.out)
by 0x40869E: copyCreator<setNode>::copyCreator(scope*, node*) (in /home/mala01/test/a.out)
by 0x407E24: copyCreator<programNode>::visit(forallNode&) (in /home/mala01/test/a.out)
by 0x40290B: forallNode::accept(visitor&) (in /home/mala01/test/a.out)
by 0x403BF8: copyCreator<programNode>::visit(programNode&) (in /home/mala01/test/a.out)
by 0x401468: main (in /home/mala01/test/a.out)

40 bytes in 1 blocks are definitely lost in loss record 8 of 13
at 0x4C2E1FC: operator new(unsigned long) (vg_replace_malloc.c:334)
by 0x40938D: copyCreator<setNode>::visit(realIdentifierNode&) (in /home/mala01/test/a.out)
by 0x401CC5: realIdentifierNode::accept(visitor&) (in /home/mala01/test/a.out)
by 0x40869E: copyCreator<setNode>::copyCreator(scope*, node*) (in /home/mala01/test/a.out)
by 0x407E24: copyCreator<programNode>::visit(forallNode&) (in /home/mala01/test/a.out)
by 0x40290B: forallNode::accept(visitor&) (in /home/mala01/test/a.out)
by 0x403CE6: copyCreator<programNode>::copyCreator(scope*, node*) (in /home/mala01/test/a.out)
by 0x4014A7: main (in /home/mala01/test/a.out)

352 (32 direct, 320 indirect) bytes in 1 blocks are definitely lost in loss record 13 of 13
at 0x4C2E1FC: operator new(unsigned long) (vg_replace_malloc.c:334)
by 0x408071: copyCreator<programNode>::visit(forallNode&) (in /home/mala01/test/a.out)
by 0x40290B: forallNode::accept(visitor&) (in /home/mala01/test/a.out)
by 0x403CE6: copyCreator<programNode>::copyCreator(scope*, node*) (in /home/mala01/test/a.out)
by 0x4014A7: main (in /home/mala01/test/a.out)

LEAK SUMMARY:
definitely lost: 176 bytes in 5 blocks
indirectly lost: 320 bytes in 8 blocks
possibly lost: 0 bytes in 0 blocks
still reachable: 0 bytes in 0 blocks
suppressed: 0 bytes in 0 blocks


There are a two main reasons why I am confused about this:


  • The two different constructors cause a different number of leaks

  • The leaks are reported to occur during visits



The
accept
methods of all nodes simply triggers a standard double dispatch to the
visit
method of the correct visitor.
nonterminalNode
s are implemented to store their children in
std::vectors
of
std::unique_ptr
.
scopes
(that can be thought of as symbol tables and hold definitions) store their members in
std::unordered_map<string, symbol *>
, where
symbol
is a descendant of the standard
node
, but on destruction they manage deletion of all their elements.
forallNode
s have a local
scope
that can store local definitions but they also take care of deleting this scope.

I am fairly new to C++ programming and might have overlooked some really fundamental issue, but after two days of fruitless searching I am putting my hopes in the community.

Also if something is unclear let me know and I can try to elaborate further.
Thanks in advance if someone has the patience to look through this ;)

Answer Source

copyCreator<nodeType>::push(ptr) is supposed to take ownership of ptr. But it fails to do so if (a) ptr is not of type nodeType* (as determined by dynamic_cast), and (b) no node of type nodeType has been visited yet.

In other words, copyCreator<nodeType> creates, and promptly leaks, copies of all nodes until it encounters one of type nodeType.

This is precisely what happens in copyCreator<programNode> cpy2(&globalScope, a);, where a is forallNode*. cpy2 expects to encounter programNode (which it never does), and meanwhile, it copies and leaks all other nodes.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download