Opened 2 years ago

Closed 22 months ago

#13719 closed defect (fixed)

Illegal free in graph_generators

Reported by: nbruin Owned by: rlm
Priority: critical Milestone: sage-5.6
Component: graph theory Keywords: graphs segfault
Cc: Merged in: sage-5.6.beta0
Authors: Jean-Pierre Flori Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jpflori)

On linux:

$ export MALLOC_CHECK_=3
$ sage -t -gdb -force_lib "devel/sage/sage/graphs/graph_generators.py"

produces a SIGABRT. gdb traceback (first bit):

#0  0x00000031cfe36285 in raise () from /lib64/libc.so.6
#1  0x00000031cfe37b9b in abort () from /lib64/libc.so.6
#2  0x00000031cfe7774e in __libc_message () from /lib64/libc.so.6
#3  0x00000031cfe7da76 in malloc_printerr () from /lib64/libc.so.6
#4  0x00007fffbe7eeead in sage_free (ptr=<optimized out>) at /usr/local/sage/5.0/local/include/csage/memory.h:46
#5  __pyx_pf_4sage_6graphs_5trees_12TreeIterator_1__dealloc__ (__pyx_v_self=0x7fffbf10c930) at sage/graphs/trees.c:807
#6  __pyx_tp_dealloc_4sage_6graphs_5trees_TreeIterator (o=0x7fffbf10c930) at sage/graphs/trees.c:2486
#7  0x00007ffff7cc6bf3 in tupledealloc (op=0x7fffc3890450) at Objects/tupleobject.c:220
#8  0x00007ffff7d12c49 in do_call (nk=<optimized out>, na=<optimized out>, pp_stack=0x7fffffffb990, func=0x7ffff7fc33e0) at Python/ceval.c:4233
...

For tree with no vertices, no memory was allocated (more or less as intended, with a malloc with size 0), but the next routine of the iterator tries to write something at the "allocated" address.

This is fixed by handling separately the 0 sized trees and not allocating nor writing anything in this case.

Attachments (1)

trac_13719.patch (2.2 KB) - added by jpflori 2 years ago.
Handle correctly empty trees ; doctest in trees.pyx

Download all attachments as: .zip

Change History (9)

comment:1 follow-up: Changed 2 years ago by nbruin

I think the problem is in sage/graphs/trees.pyx:78, the __dealloc__ method of TreeIterator. It does:

    def __dealloc__(self):
        if self.l != NULL:
            sage_free(self.l)
        if self.current_level_sequence != NULL:
            sage_free(self.current_level_sequence)

however, self.l and self.current_level_sequence are python attributes, not cdeffed pointers! So I don't think one can expect that self.l hold a valid value by the time __dealloc__ gets called. Storing pointers in python attributes is highly suspect to begin with.

comment:2 in reply to: ↑ 1 Changed 2 years ago by jpflori

Replying to nbruin:

I think the problem is in sage/graphs/trees.pyx:78, the __dealloc__ method of TreeIterator. It does:

    def __dealloc__(self):
        if self.l != NULL:
            sage_free(self.l)
        if self.current_level_sequence != NULL:
            sage_free(self.current_level_sequence)

however, self.l and self.current_level_sequence are python attributes, not cdeffed pointers! So I don't think one can expect that self.l hold a valid value by the time __dealloc__ gets called. Storing pointers in python attributes is highly suspect to begin with.

It seems that l and current_level_sequence are properly defined in trees.pxd as cdefed pointers, so the problem might be elsewhere or just a little bit more involved.
Maybe l and current_level_sequence can point to the same memory address, whence a double free.

comment:3 Changed 2 years ago by jpflori

Ok, the problem is that the functions in tree.pyx do not properly handle the case where self.vertices == 0 which is tested by graph_generator.py.
A patch will follow shortly.

comment:4 Changed 2 years ago by nbruin

doctest on TreeIterator to explicitly test proper handling of the edge case? Even though the test would only test the presence of the patch with MALLOC_CHECK_, I think it's a good habit to test edge cases directly on top of the indirect tests from elsewhere.

(tree.pxd: Shoot! cython cannot be read locally. The headers are important too. I'm happy to see the attributes were properly defined. I was worried that cython would even allow such unsafe implicit pointer-to-object casts.)

Last edited 2 years ago by nbruin (previous) (diff)

Changed 2 years ago by jpflori

Handle correctly empty trees ; doctest in trees.pyx

comment:5 Changed 2 years ago by jpflori

  • Authors set to Jean-Pierre Flori
  • Component changed from memleak to graph theory
  • Description modified (diff)
  • Keywords graphs segfault added
  • Status changed from new to needs_review

Updated patch with local doctest, feel free to devise a better one.

I just realized that I did not mention that this should go quite undetectable unless one uses MALLOC_CHECK.
Nonetheless, as ones write something in memory which was not allocated for this purpose, the fixed bug should potentially lead to segfaults (although this obviously never happened since this code is in Sage, or not frequently enough to be reported).

comment:6 Changed 23 months ago by ncohen

  • Status changed from needs_review to positive_review

Helloooooooooooo !!

Well, I was not able to reproduce the bug even from the instructions on this ticket, but the changes make sense anyway (not allocating 0bytes of memory, or setting pointers to NULL after freeing the memory. Well :-)

Nathann

comment:7 Changed 22 months ago by jdemeyer

  • Reviewers set to Nathann Cohen

comment:8 Changed 22 months ago by jdemeyer

  • Merged in set to sage-5.6.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.