Opened 3 years ago

Closed 18 months 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) Commit: 6612f1e7d8eba6309b9c9c694b3e0d18b9b404d5
Dependencies: Stopgaps:

Description (last modified by rws)

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 3 years ago by rws

  • Branch set to u/rws/crash_in_subgraphsearch_of_empty_graph

comment:2 Changed 3 years ago by rws

  • Authors set to Ralf Stephan
  • Commit set to 6b7403114f5541bd481b6e6a0aa606026cd0d5cf
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

6b7403121828: check for empty graph before de/allocating

comment:3 Changed 3 years ago by jdemeyer

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

Last edited 3 years ago by jdemeyer (previous) (diff)

comment:4 Changed 3 years ago by jdemeyer

  • Description modified (diff)
  • Status changed from needs_review to needs_work

comment:5 Changed 3 years ago by rws

  • Description modified (diff)

comment:6 follow-up: Changed 3 years ago by rws

Deallocation of tmp_array is also missing.

comment:7 Changed 3 years ago by rws

  • Branch changed from u/rws/crash_in_subgraphsearch_of_empty_graph to u/rws/21828

comment:8 Changed 3 years ago by rws

  • Commit changed from 6b7403114f5541bd481b6e6a0aa606026cd0d5cf to 5a14f4d446c6617e15cacb1e96a6ff92571df2c6
  • Status changed from needs_work to needs_review

Let's try again differently.


New commits:

5a14f4d21828: Crash in SubgraphSearch of empty graph

comment:9 follow-up: Changed 3 years ago by vdelecroix

doctest?

comment:10 Changed 3 years ago by jmantysalo

Good to fix this. For larger context see #21741.

comment:11 Changed 3 years ago by jdemeyer

  • 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 jdemeyer

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 rws

  • Authors Ralf Stephan deleted
  • 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 3 years ago by jdemeyer

What exactly is the problem here? What would be the minimal code to exhibit the problem?

comment:15 in reply to: ↑ 6 Changed 20 months ago by Konrad127123

Replying to rws:

Deallocation of tmp_array is also missing.

I've added a fix for this part in #24660 .

comment:16 Changed 20 months ago by jmantysalo

  • Milestone changed from sage-7.6 to sage-duplicate/invalid/wontfix
  • Status changed from needs_work to needs_review

comment:17 Changed 20 months ago by rws

You mean #24660? As said in comment:15 that is only part of it.

comment:18 Changed 19 months ago by rws

  • Branch set to u/rws/21828-1

comment:19 Changed 19 months ago by rws

  • Authors set to Ralf Stephan
  • 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:

5def5f421828: use MemoryAllocator in generic graphs; fixes crash

comment:20 Changed 19 months ago by dcoudert

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 19 months ago by jdemeyer

  • Status changed from needs_review to needs_work
  1. MemoryAllocator raises exceptions when out of memory, so the NULL checks are no longer needed.
  1. I'm surprised that for 0 < i < self.ng is legal Cython syntax. Cython understands for i in range(1, self.ng) though. To be safe, you may want to add cdef int i.
  1. My impression is that self.ng is constant. So I don't understand code of the form
    if self.ng == 0:
       raise StopIteration
    ....
    if self.ng > 0: ...
    

Isn't the latter trivially true?

Last edited 19 months ago by jdemeyer (previous) (diff)

comment:22 Changed 19 months ago by git

  • Commit changed from 5def5f425c477e15b3f74ab370340f7dd9a82205 to 8fa9ec74ac3055c534d95cb65d4aa4e3b4e07ec7

Branch pushed to git repo; I updated commit sha1. New commits:

8fa9ec721828: improvements, doctest

comment:23 Changed 19 months ago by rws

  • Status changed from needs_work to needs_review

comment:24 Changed 19 months ago by jdemeyer

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

Last edited 19 months ago by jdemeyer (previous) (diff)

comment:25 Changed 19 months ago by git

  • Commit changed from 8fa9ec74ac3055c534d95cb65d4aa4e3b4e07ec7 to 6612f1e7d8eba6309b9c9c694b3e0d18b9b404d5

Branch pushed to git repo; I updated commit sha1. New commits:

6612f1e21828: cosmetics

comment:26 Changed 19 months ago by rws

  • Status changed from needs_work to needs_review

comment:27 Changed 18 months ago by dcoudert

  • 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 18 months ago by rws

Thanks!

comment:29 Changed 18 months ago by vbraun

  • Branch changed from u/rws/21828-1 to 6612f1e7d8eba6309b9c9c694b3e0d18b9b404d5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.