lundi 24 juillet 2017

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. nonterminalNodes 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. forallNodes 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 ;)

Aucun commentaire:

Enregistrer un commentaire