[Lemon-devel] Memory corruption when using IterableValueMap on Class derived from lemon Graph

[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.







On Fri, Apr 22, 2011 at 5:42 PM, Bernhard Kausler
<bernhard.kausler at iwr.uni-heidelberg.de> wrote:
> 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
>
>
> On 22.04.2011 09:57, Bernhard Kausler wrote:
>> Dear all,
>>
>> unfortunately, the user registration on the lemon website is broken and
>> I can't use the ticket system. Therefore, I report a bug here.
>>
>> 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
>>
>> ---------- code begin ---------
>> #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;
>> }
>> ---------- code end -----------
>>
>> 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
>>
>> Best,
>> Bernhard Kausler
>> _______________________________________________
>> Lemon-devel mailing list
>> Lemon-devel at lemon.cs.elte.hu
>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-devel
>
>
> _______________________________________________
> Lemon-devel mailing list
> Lemon-devel at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-devel
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0f5b2bb21e94.patch
Type: text/x-patch
Size: 1276 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-devel/attachments/20110424/bbafd1ac/attachment.patch>