Fix memory allocation problems in data_structures_pyx.pxi

[dcoudert]

The following test causes a segfault on my computer (Intel(R) Xeon(R) CPU W3520 @ 2.67GHz / 4GB ram / linux)

sage: G = graphs.CompleteGraph(10)
sage: GG = G.line_graph().line_graph().line_graph()
sage: H = GG.relabel(inplace=False)
sage: GG.is_isomorphic(H)
...
sage: line 135:  3438 Segmentation fault      (core dumped) "$SAGE_ROOT/spkg/bin/sage" "$@"

Tracking the segfault, I ended up in the SC_new of sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi and also in the (de)allocate_dc_work_space methods of double_coset.pyx file.

This patch fix some assignments performed before testing memory allocations and other similar stuff. Finally, I end up with a proper MemoryError? and so the problem is solved

Apply:

• trac_14501.patch​

[ncohen]

Yoooooooooooo !

Well, what you do seems mostly harmless (though sage_free(SC.generators[i]) is not indented correctly) but if it changes nothing ?...

Moving the two assignment can avoid a segfault alright, replacing a malloc by a calloc is unnecessary unless proven otherwise, and splitting a loop into two may also be unnecessary if the two vectors are only allocated together (and checked at that time).

Nathann

[dcoudert]

Moving the two assignment can avoid a segfault alright,

Yes

replacing a malloc by a calloc is unnecessary unless proven otherwise,

Proof: With malloc, C allocates a contiguous segment of memory. However, this block is not initialized! type "man malloc" in your terminal of go to ​http://man7.org/linux/man-pages/man3/malloc.3.html. With calloc, the memory is initialized to 0 or NULL. \qed

In any case, it is always safer to ensure that variables are initialized.

and splitting a loop into two may also be unnecessary if the two vectors are only allocated together (and checked at that time).

Ok.

---

I forgot to tick "replace" while uploading update patch.

Apply: trac_14501.2.patch

[ncohen]

Proof: With malloc, C allocates a contiguous segment of memory. However, this block is not initialized! type "man malloc" in your terminal of go to ​http://man7.org/linux/man-pages/man3/malloc.3.html. With calloc, the memory is initialized to 0 or NULL. \qed

I know. That's what I meant when I said that it is useless unless proven otherwise.

In the case at hand, 10 lines after the malloc that you relaced with a calloc the whole vector is overwritten with data that makes sense, contrary to 0s.

Nathann

[dcoudert]

In the case at hand, 10 lines after the malloc that you relaced with a calloc the whole vector is overwritten with data that makes sense, contrary to 0s.

The point is that if the SC_dealloc function is called before assigning something that make sense to SC.generators[i], then sage_free is called with unknown argument.

I did further corrections in this file plus in the double_coset.pyx file. In both files we had calls to free methods on unassigned pointers.

Overall these modification solve the problem and now the method raises a MemoryError?!

Further cleaning should certainly be done in these files to prevent similar errors.

[dcoudert]

Apply: trac_14501.patch

[ncohen]

Your patch adds

sage_free(int_array)
sage_free(int_ptrs)

three lines before SC_dealloc(SC). In SC_dealloc :

	sage_free(SC.generators) # frees int_ptrs                                                                                                                                              
	sage_free(SC.orbit_sizes) # frees int_array  

You also set to NULL the members of a structure that is deallocated two lines afterwards.

The and SC.gen_inverses is not NULL also seems to be unnecessary, for SC.gen and SC.gen_inverses are always allocated (and checked) simultaneously, so that both are not NULL or both are NULL. And "formally", that is if you believe that one can be NULL while the other is not (which does not happen) you introduce a memory leak with this additional test, for you will only deallocate both vectors if BOTH are NULL, and do nothing when only one of them is NULL (which again, does not happen).

Nathann

[dcoudert]

Nathann,

again, pointers are not set to NULL by default, and a sage_free call on an non initialized pointer gives a segfault (or should give a segfault).

Replying to ncohen:

Your patch adds

sage_free(int_array)
sage_free(int_ptrs)

three lines before SC_dealloc(SC). In SC_dealloc :

	sage_free(SC.generators) # frees int_ptrs                                                                                                                                              
	sage_free(SC.orbit_sizes) # frees int_array  

Yes and I'm right to do it since at that point of the program the int_array variable has not been assigned to SC.generators. Therefore SC.generators points to something we don't know (neither int_array, nor NULL) and a call to sage_free could results in a segfault (at least it is the case on my computer). The same for int_ptrs.

You also set to NULL the members of a structure that is deallocated two lines afterwards.

Yes, since the SC_dealloc methods tests if some members of the structure are not NULL. If they have never been initialized, they could be different from NULL and so we can have a segfault!

The and SC.gen_inverses is not NULL also seems to be unnecessary, for SC.gen and SC.gen_inverses are always allocated (and checked) simultaneously, so that both are not NULL or both are NULL.

No, they are allocated using 2 distinct malloc. So the first one could succeed while the second one fails. In case the second fails, then it is set to NULL.

And "formally", that is if you believe that one can be NULL while the other is not (which does not happen) you introduce a memory leak with this additional test, for you will only deallocate both vectors if BOTH are NULL, and do nothing when only one of them is NULL (which again, does not happen).

Yes, that's right. So I'm splitting these instruction again.

I'm not adding these instructions for fun. I'm adding them because if you follow properly the sequence of instructions, you realize that some tests are unsafe and could result in segfault. More precisely, removing any of these instructions results in a segfault on my computer.

David.

[ncohen]

Yo !

Why don't you just put a "calloc" where StabilizerChain? is allocated then ?

No, they are allocated using 2 distinct malloc. So the first one could succeed while the second one fails. In case the second fails, then it is set to NULL.

That's the block of code you will see each time they are allocated

	SC.generators[i]   = <int *> sage_malloc( SC.array_size[i]*n * sizeof(int) )
	SC.gen_inverses[i] = <int *> sage_malloc( SC.array_size[i]*n * sizeof(int) )
	if SC.generators[i] is NULL or SC.gen_inverses[i] is NULL:
            SC_dealloc(SC)
            return NULL

I swear that one cannot be NULL while the other is :-P

Nathann

[dcoudert]

Why don't you just put a "calloc" where StabilizerChain? is allocated then ?

That's correct, and it allows for removing series of NULL assignments. Done.

No, they are allocated using 2 distinct malloc. So the first one could succeed while the second one fails. In case the second fails, then it is set to NULL.

That's the block of code you will see each time they are allocated

	SC.generators[i]   = <int *> sage_malloc( SC.array_size[i]*n * sizeof(int) )
	SC.gen_inverses[i] = <int *> sage_malloc( SC.array_size[i]*n * sizeof(int) )
	if SC.generators[i] is NULL or SC.gen_inverses[i] is NULL:
            SC_dealloc(SC)
            return NULL

I swear that one cannot be NULL while the other is :-P

Well, if SC.generators[i] is NULL then SC.gen_inverses[i] should also be NULL (unless something strange happens). However, the converse is false.

For the SC.generators is not NULL test, you are right: if it is NULL, then it means it has never been assigned int_ptrs and so SC.gen_inverses is also NULL. In this case, the converse is also true. I have re-merged the tests.

See updated patch.

[ncohen]

Yoooooooooooo !

Do you still needs those lines ?

sage_free(int_array)
sage_free(int_ptrs)

Short of this, I think the patch is good to go. I wish there was a nice way to avoid this O(n) calloc, but everything I see would make the code trickier, and it really doesn't need it :-P

Nathann

[dcoudert]

Do you still needs those lines ?

sage_free(int_array)
sage_free(int_ptrs)

Yes. They have not yet been assigned to SC.stuff pointers and so must be deallocated. The other option is to assign these pointers to SC.stuff and let SC_dealloc do the job, but then it will enter a for loop. We don't need that.

Short of this, I think the patch is good to go. I wish there was a nice way to avoid this O(n) calloc, but everything I see would make the code trickier, and it really doesn't need it :-P

At least calloc is low level implementation and so we may expect it is way faster than assignments.

Thanks,

D.

[ncohen]

Yes. They have not yet been assigned to SC.stuff pointers and so must be deallocated.

Oops. Of course :-P

At least calloc is low level implementation and so we may expect it is way faster than assignments.

Well, I don't think it makes much of a difference... It's more an aesthetic thing I guess :-P

Well, then... good to go !

Nathann

[dcoudert]

Thanks!