COIN-OR::LEMON - Graph Library

Opened 8 years ago

Closed 8 years ago

#420 closed defect (fixed)

Memory corruption when using IterableValueMap on Class derived from lemon Graph

Reported by: Alpar Juttner Owned by: Balazs Dezso
Priority: critical Milestone: LEMON 1.3 release
Component: core Version: hg main
Keywords: Cc: ernhard.kausler@…
Revision id:

Description (last modified by 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

Attachments (2)

uninitialized-iterable-maps-nodes_lemon-main.patch (980 bytes) - added by Alpar Juttner 8 years ago.
0f5b2bb21e94.patch (1.2 KB) - added by Alpar Juttner 8 years ago.

Download all attachments as: .zip

Change History (5)

Changed 8 years ago by Alpar Juttner

comment:1 Changed 8 years ago by Alpar Juttner

Cc: ernhard.kausler@… added
Description: modified (diff)

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

Changed 8 years ago by Alpar Juttner

Attachment: 0f5b2bb21e94.patch added

comment:2 Changed 8 years ago by 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.

comment:3 Changed 8 years ago by Alpar Juttner

Description: modified (diff)
Resolution: fixed
Status: newclosed

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

Note: See TracTickets for help on using tickets.