Illegal free in graph_generators

[nbruin]

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.

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

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

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

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

[jpflori]

Handle correctly empty trees ; doctest in trees.pyx

[jpflori]

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