Opened 5 years ago

Closed 5 years ago

#17376 closed defect (fixed)

Cleanup subgraphsearch to avoid crashes

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.5
Component: graph theory Keywords:
Cc: dcoudert, dimpase, jmantysalo, vdelecroix, Simon, tscrim Merged in:
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: de40d01 (Commits) Commit: de40d01a7a79dc7c30700e48bd9545eb0d528ebd
Dependencies: Stopgaps:

Description (last modified by ncohen)

The SubgraphSearch code crashes from time to time when you Ctrl+C it during its memory allocation instructions.

This patch cleans the code a bit so that all allocations happen in one place, before the actual code is run. And so __dealloc__ only frees the memory that has been allocated, even if the code was interrupted.

Basically, we avoid crashed only with simple code cleaning.

1) In order to produce the crash, run this and CTRL+C it immediately: 

graphs.CompleteMultipartiteGraph([20,20,20,20]).subgraph_search(graphs.CompleteGraph(5))

Do it several times in a row if necessary.

2) The code could use a rewrite with bitsets. It would be faster and lighter in memory, but there is already a pretty similar code in needs_review at #17309 and I fear that it may take time before it is reviewed. So I will wait for this before reimplementing SubgraphSearch.

Change History (8)

comment:1 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/17376
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 357ab7e45b828c0900e320c8a933aee91df69ffc

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

​357ab7etrac #17376: Cleanup subgraphsearch to avoid crashes

comment:3 Changed 5 years ago by git

  • Commit changed from 357ab7e45b828c0900e320c8a933aee91df69ffc to de40d01a7a79dc7c30700e48bd9545eb0d528ebd

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​de40d01trac #17376: Cleanup subgraphsearch to avoid crashes

comment:4 Changed 5 years ago by ncohen

  • Description modified (diff)

comment:5 follow-up: Changed 5 years ago by dcoudert

  • Component changed from graphics to graph theory
  • Reviewers set to David Coudert

I tried the patch multiple times and got no crash, while without the patch I can get a segfault.

Install OK, long tests OK => positive review.

David. PS: I'm changing the patch from "graphics" to "graph theory". It seems more appropriate.

comment:6 Changed 5 years ago by dcoudert

  • Status changed from needs_review to positive_review

comment:7 in reply to: ↑ 5 Changed 5 years ago by ncohen

YOooooooooo !

PS: I'm changing the patch from "graphics" to "graph theory". It seems more appropriate.

Oh, right.

And thanks for the review !

Nathann

comment:8 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/17376 to de40d01a7a79dc7c30700e48bd9545eb0d528ebd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.