Opened 3 years ago
Closed 20 months ago
#21828 closed defect (fixed)
Use MemoryAllocator in generic graphs; fixes crash
Reported by:  rws  Owned by:  

Priority:  critical  Milestone:  sage8.2 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  Ralf Stephan  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  6612f1e (Commits)  Commit:  6612f1e7d8eba6309b9c9c694b3e0d18b9b404d5 
Dependencies:  Stopgaps: 
Description (last modified by )
Sage on OpenSuSE 42.2 (built from scratch with internal gcc4.9 and 5.4) crashes on the command Poset().is_incomparable_chain_free(1,1)
. Reason is there is no check in the SubgraphSearch
member functions for an empty graph, so happily unallocated memory is changed in _initialization()
.
This was discovered because of several failing doctests on OpenSuSE, presumably because of the system's more stringent memory model.
Change History (29)
comment:1 Changed 3 years ago by
 Branch set to u/rws/crash_in_subgraphsearch_of_empty_graph
comment:2 Changed 3 years ago by
 Commit set to 6b7403114f5541bd481b6e6a0aa606026cd0d5cf
 Description modified (diff)
 Status changed from new to needs_review
comment:3 Changed 3 years ago by
It's not really clear to me if adding if self.ng == 0: return
in those places is the right thing to do. Why in __cinit__
and __dealloc__
for example? I don't see the problem there. And in _initialize
, why should self.stack
and self.active
not be initialized? If you do the initialization correctly, it should also be possible to remove the if self.ng == 0: return
from __next__
.
comment:4 Changed 3 years ago by
 Description modified (diff)
 Status changed from needs_review to needs_work
comment:5 Changed 3 years ago by
 Description modified (diff)
comment:6 followup: ↓ 15 Changed 3 years ago by
Deallocation of tmp_array
is also missing.
comment:7 Changed 3 years ago by
 Branch changed from u/rws/crash_in_subgraphsearch_of_empty_graph to u/rws/21828
comment:8 Changed 3 years ago by
 Commit changed from 6b7403114f5541bd481b6e6a0aa606026cd0d5cf to 5a14f4d446c6617e15cacb1e96a6ff92571df2c6
 Status changed from needs_work to needs_review
comment:9 followup: ↓ 13 Changed 3 years ago by
doctest?
comment:10 Changed 3 years ago by
Good to fix this. For larger context see #21741.
comment:11 Changed 3 years ago by
 Status changed from needs_review to needs_work
This seems overly complicated to me...
This looks like the only place where you really need to do something:
self.busy[0] = 1
comment:12 Changed 3 years ago by
You may also want to look at src/sage/ext/memory_allocator.pyx
to simplify the memory allocations.
comment:13 in reply to: ↑ 9 Changed 3 years ago by
 Branch u/rws/21828 deleted
 Commit 5a14f4d446c6617e15cacb1e96a6ff92571df2c6 deleted
 Description modified (diff)
 Milestone changed from sage7.5 to sage7.6
My Python understanding does not suffice for this. Please someone take over.
comment:14 Changed 3 years ago by
What exactly is the problem here? What would be the minimal code to exhibit the problem?
comment:15 in reply to: ↑ 6 Changed 22 months ago by
comment:16 Changed 21 months ago by
 Milestone changed from sage7.6 to sageduplicate/invalid/wontfix
 Status changed from needs_work to needs_review
comment:17 Changed 21 months ago by
You mean #24660? As said in comment:15 that is only part of it.
comment:18 Changed 21 months ago by
 Branch set to u/rws/218281
comment:19 Changed 21 months ago by
 Commit set to 5def5f425c477e15b3f74ab370340f7dd9a82205
 Milestone changed from sageduplicate/invalid/wontfix to sage8.2
 Summary changed from Crash in SubgraphSearch of empty graph to Use MemoryAllocator in generic graphs; fixes crash
Finally I got the handle on this. I'm inserting/leaving some checks for efficiency reasons. Please review, as this makes patchbot fail on OpenSuSE.
New commits:
5def5f4  21828: use MemoryAllocator in generic graphs; fixes crash

comment:20 Changed 21 months ago by
I don't have OpenSuSE, so I cannot fully test the patch (working for me on OSX).
Could you add a doctest for Poset().is_incomparable_chain_free(1,1)
?
comment:21 Changed 21 months ago by
 Status changed from needs_review to needs_work
MemoryAllocator
raises exceptions when out of memory, so theNULL
checks are no longer needed.
 I'm surprised that
for 0 < i < self.ng
is legal Cython syntax. Cython understandsfor i in range(1, self.ng)
though. To be safe, you may want to addcdef int i
.
 My impression is that
self.ng
is constant. So I don't understand code of the formif self.ng == 0: raise StopIteration .... if self.ng > 0: ...
Isn't the latter trivially true?
comment:22 Changed 21 months ago by
 Commit changed from 5def5f425c477e15b3f74ab370340f7dd9a82205 to 8fa9ec74ac3055c534d95cb65d4aa4e3b4e07ec7
Branch pushed to git repo; I updated commit sha1. New commits:
8fa9ec7  21828: improvements, doctest

comment:23 Changed 21 months ago by
 Status changed from needs_work to needs_review
comment:24 Changed 21 months ago by
 Status changed from needs_review to needs_work
I think that you should still fix the for 0 < i < self.ng:
syntax (sorry if my previous comment was not clear on this).
comment:25 Changed 21 months ago by
 Commit changed from 8fa9ec74ac3055c534d95cb65d4aa4e3b4e07ec7 to 6612f1e7d8eba6309b9c9c694b3e0d18b9b404d5
Branch pushed to git repo; I updated commit sha1. New commits:
6612f1e  21828: cosmetics

comment:26 Changed 21 months ago by
 Status changed from needs_work to needs_review
comment:27 Changed 20 months ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
For me this patch is perfectly working, so I give it positive review.
comment:28 Changed 20 months ago by
Thanks!
comment:29 Changed 20 months ago by
 Branch changed from u/rws/218281 to 6612f1e7d8eba6309b9c9c694b3e0d18b9b404d5
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
21828: check for empty graph before de/allocating