Opened 8 years ago
Closed 8 years ago
#14501 closed defect (fixed)
Fix memory allocation problems in data_structures_pyx.pxi
Reported by: | dcoudert | Owned by: | joyner |
---|---|---|---|
Priority: | major | Milestone: | sage-5.10 |
Component: | group theory | Keywords: | |
Cc: | ncohen | Merged in: | sage-5.10.beta2 |
Authors: | David Coudert | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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:
Attachments (1)
Change History (18)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Cc ncohen added
- Status changed from new to needs_review
comment:3 Changed 8 years ago by
comment:4 follow-up: ↓ 5 Changed 8 years ago by
- Description modified (diff)
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
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 8 years ago by
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
comment:6 in reply to: ↑ 5 Changed 8 years ago by
- Description modified (diff)
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.
comment:7 Changed 8 years ago by
Apply: trac_14501.patch
comment:8 follow-up: ↓ 9 Changed 8 years ago by
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
comment:9 in reply to: ↑ 8 ; follow-up: ↓ 10 Changed 8 years ago by
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)
. InSC_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, forSC.gen
andSC.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.
comment:10 in reply to: ↑ 9 ; follow-up: ↓ 11 Changed 8 years ago by
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
Changed 8 years ago by
comment:11 in reply to: ↑ 10 Changed 8 years ago by
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 NULLI 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.
comment:12 follow-up: ↓ 13 Changed 8 years ago by
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
comment:13 in reply to: ↑ 12 ; follow-up: ↓ 14 Changed 8 years ago by
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.
comment:14 in reply to: ↑ 13 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
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
comment:15 Changed 8 years ago by
- Reviewers set to Nathann Cohen
comment:16 Changed 8 years ago by
Thanks!
comment:17 Changed 8 years ago by
- Merged in set to sage-5.10.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
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