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

[Bernhard Kausler]

Dear Balazs,

so I just fixed the symptom not the cause ;) Thanks for your more detailed explanation.

As a suggestion: The Node class' default constructor in list_map.h doesn't initialize the "int id" (which caused the 
memory access errors). I think, id should be initialized to -1 (the same as the Invalid typed constructor) to make 
errors like this more unlikely in the future.

  class Node {
     protected:

       int id;
       explicit Node(int pid) { id = pid;}

     public:
       Node() {}
       Node (Invalid) { id = -1; }
       ...
     };

Best wishes,
Bernhard



On 04/24/2011 10:01 PM, Balázs Dezső wrote:
> 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: bernhard_kausler.vcf
Type: text/x-vcard
Size: 493 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-devel/attachments/20110426/f7941488/attachment.vcf>