Opened 6 years ago
Closed 6 years 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 )
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)
Change History (9)
comment:1 follow-up: ↓ 2 Changed 6 years ago by
comment:2 in reply to: ↑ 1 Changed 6 years ago by
Replying to nbruin:
I think the problem is in
sage/graphs/trees.pyx
:78, the__dealloc__
method ofTreeIterator
. 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 6 years ago by
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 6 years ago by
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.
comment:5 Changed 6 years ago by
- 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 6 years ago by
- 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 6 years ago by
- Reviewers set to Nathann Cohen
comment:8 Changed 6 years ago by
- Merged in set to sage-5.6.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
I think the problem is in
sage/graphs/trees.pyx
:78, the__dealloc__
method ofTreeIterator
. It does: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.