Memory corruption when using IterableValueMap on Class derived from lemon Graph

[Alpar Juttner]

A post from Bernhard Kausler on lemon-devel@…:

The following code causes a memory access error.

• Tested for lemon 1.2.1 and the latest lemon-main sources
• Doesn't happen for other graph maps like IdMap

---

#include <lemon/list_graph.h>
#include <lemon/maps.h>

using namespace lemon;

class MyGraph : public ListDigraph {
};

int main() {
  MyGraph derived;
  IterableValueMap<MyGraph, MyGraph::Node, int> derived_m2(derived);

  derived.addNode();

  return 0;
}

---

gdb backtrace:
#0  0x00000000004059a3 in lemon::IterableValueMap<MyGraph,
lemon::ListDigraphBase::Node, int>::unlace (this=0x7fffffffdcf0,
key=...) at lemon-main/lemon/maps.h:3098
#1  0x0000000000405050 in lemon::IterableValueMap<MyGraph,
lemon::ListDigraphBase::Node, int>::add (this=0x7fffffffdcf0, key=...)
at lemon-main/lemon/maps.h:3255
#2  0x00000000004026ab in
lemon::AlterationNotifier<lemon::DigraphExtender<lemon::ListDigraphBase>, lemon::ListDigraphBase::Node>::add
(this=0x7fffffffdcc0, item=...) at
/home/bkausler/loca/include/lemon/bits/alteration_notifier.h:356
#3  0x00000000004018a7 in
lemon::DigraphExtender<lemon::ListDigraphBase>::addNode
(this=0x7fffffffdc80) at
/home/bkausler/local/include/lemon/bits/graph_extender.h:269
#4  0x00000000004012c8 in lemon::ListDigraph::addNode
(this=0x7fffffffdc80) at lemon-main/lemon/list_graph.h:352
#5  0x0000000000400f54 in main () at inheritance-bug.cpp:15

[Alpar Juttner]

From: Bernhard Kausler

Dear all,

the bug was caused by uninitialized "next" and "prev" fields in struct IterableValueMapNode (resp. struct IterableIntMapNode) in maps.h. Please find attached a patch​ for the lemon-main branch, that fixes the problem. (The patch is valid for lemon-1.2.1, too).

Best, Bernhard Kausler

[Alpar Juttner]

From: Balázs Dezső

Hi,

thanks for looking for this problem, but the patch is simpler. There is a typo in the code, the IterableValueMap::add() should call lace() instead of unlace().

Patch is attached.​

Balazs

For example, the following code would be wrong:

 MyGraph derived;
 IterableValueMap<MyGraph, MyGraph::Node, int> derived_m2(derived);

 MyGraph::Node n = derived.addNode();
 MyGraph::Node m = derived.addNode();

 derived_m2.set(n, 0);
 derived.erase(m);

The last call of function erase() would remove the node of n from the _first map of the iterable value map.

[Alpar Juttner]

The bugfix has been merged to branches 1.2 and default as [633956ca9421].