Opened 4 years ago
Closed 3 years ago
#21828 closed defect (fixed)
Use MemoryAllocator in generic graphs; fixes crash
Reported by: | rws | Owned by: | |
---|---|---|---|
Priority: | critical | Milestone: | sage-8.2 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | ||
Authors: | Ralf Stephan | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | 6612f1e (Commits, GitHub, GitLab) | Commit: | 6612f1e7d8eba6309b9c9c694b3e0d18b9b404d5 |
Dependencies: | Stopgaps: |
Description (last modified by )
Sage on OpenSuSE 42.2 (built from scratch with internal gcc-4.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 4 years ago by
- Branch set to u/rws/crash_in_subgraphsearch_of_empty_graph
comment:2 Changed 4 years ago by
- Commit set to 6b7403114f5541bd481b6e6a0aa606026cd0d5cf
- Description modified (diff)
- Status changed from new to needs_review
comment:3 Changed 4 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 4 years ago by
- Description modified (diff)
- Status changed from needs_review to needs_work
comment:5 Changed 4 years ago by
- Description modified (diff)
comment:6 follow-up: ↓ 15 Changed 4 years ago by
Deallocation of tmp_array
is also missing.
comment:7 Changed 4 years ago by
- Branch changed from u/rws/crash_in_subgraphsearch_of_empty_graph to u/rws/21828
comment:8 Changed 4 years ago by
- Commit changed from 6b7403114f5541bd481b6e6a0aa606026cd0d5cf to 5a14f4d446c6617e15cacb1e96a6ff92571df2c6
- Status changed from needs_work to needs_review
comment:9 follow-up: ↓ 13 Changed 4 years ago by
doctest?
comment:10 Changed 4 years ago by
Good to fix this. For larger context see #21741.
comment:11 Changed 4 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 4 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 4 years ago by
- Branch u/rws/21828 deleted
- Commit 5a14f4d446c6617e15cacb1e96a6ff92571df2c6 deleted
- Description modified (diff)
- Milestone changed from sage-7.5 to sage-7.6
My Python understanding does not suffice for this. Please someone take over.
comment:14 Changed 4 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 3 years ago by
comment:16 Changed 3 years ago by
- Milestone changed from sage-7.6 to sage-duplicate/invalid/wontfix
- Status changed from needs_work to needs_review
comment:17 Changed 3 years ago by
You mean #24660? As said in comment:15 that is only part of it.
comment:18 Changed 3 years ago by
- Branch set to u/rws/21828-1
comment:19 Changed 3 years ago by
- Commit set to 5def5f425c477e15b3f74ab370340f7dd9a82205
- Milestone changed from sage-duplicate/invalid/wontfix to sage-8.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 3 years 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 3 years 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 3 years 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 3 years ago by
- Status changed from needs_work to needs_review
comment:24 Changed 3 years 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 3 years 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 3 years ago by
- Status changed from needs_work to needs_review
comment:27 Changed 3 years 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 3 years ago by
Thanks!
comment:29 Changed 3 years ago by
- Branch changed from u/rws/21828-1 to 6612f1e7d8eba6309b9c9c694b3e0d18b9b404d5
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
21828: check for empty graph before de/allocating