igraph bfs/dfs segmentation faults

[ludwikbukowski]

Hi, I am just playing with dfs/bfs functions and Im trying to access vertex attributes in callback function but everytime it crashes R vm:

library('igraph')
g <- make_tree(10)
g<- set_vertex_attr(g, "xx", value = 10:19)
f.in <- function(graph, data, extra) {
## print(V(graph)[data[1]]$xx) $## I tried something like this but doesnt work
print(graph) ## even this crashes R
FALSE
}
tmp <- bfs(g, root=1, "out",callback=f.in)

Even printing graph structure in callback function breaks everything...
The error I got:

 *** caught segfault ***
address 0x8, cause 'memory not mapped'

Traceback:
 1: .Call(C_R_igraph_bfs, graph, root, roots, neimode, unreachable,     restricted, as.logical(order), as.logical(rank), as.logical(father),     as.logical(pred), as.logical(succ), as.logical(dist), callback,     extra, rho)
 2: bfs(g, root = 1, "out", callback = f.in)

[zettsu-t]

I found a similar issue to call an igraph function in callbacks. The following code crashes in igraph 1.2.4.1.

library(igraph)
f <- function(h,v,e){
  igraph::neighbors(h,1)
  FALSE
}
g <- igraph::graph_from_data_frame(data.frame(from=1,to=2))
igraph::bfs(graph=g,root=1,neimode="all",callback=f)

Here is my environment to run the code shown above.

> sessionInfo()
R version 3.6.0 (2019-04-26)
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows >= 8 x64 (build 9200)

Matrix products: default

locale:
[1] LC_COLLATE=Japanese_Japan.932  LC_CTYPE=Japanese_Japan.932
[3] LC_MONETARY=Japanese_Japan.932 LC_NUMERIC=C
[5] LC_TIME=Japanese_Japan.932

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base

other attached packages:
[1] igraph_1.2.4.1

loaded via a namespace (and not attached):
[1] compiler_3.6.0  magrittr_1.5    tools_3.6.0     pkgconfig_2.0.2

[szhorvat]

@vtraag Still crashed in the dev version, we should investigate.

[szhorvat]

With 1.3 dev version:

> library(igraph)
> f <- function(h,v,e){
+     igraph::neighbors(h,1)
+     FALSE
+ }
> g <- igraph::graph_from_data_frame(data.frame(from=1,to=2))
> igraph::bfs(graph=g,root=1,neimode="all",callback=f)

Error in igraph::bfs(graph = g, root = 1, neimode = "all", callback = f) : 
  At core/core/dqueue.pmt:105 : Assertion failed: q->stor_begin != 0. This is an unexpected igraph error; please report this as a bug, along with the steps to reproduce it.

[ntamas]

The callbacks of the bfs / dfs functions seem to be fundamentally broken at the moment; in particular:

• returning anything that is a non-logical value crashes R (and this can happen easily if you forget to put FALSE at the end of the callback) (fixed in 380f381)
• any sort of error raised from the callback crashes R
• the vertex IDs in the named vector of the callback are 0-based, not 1-based (fixed in 380f381)
• furthermore, you are not allowed to call igraph functions from the callback because the R-to-C glue code will eventually hit on.exit( .Call(C_R_igraph_finalizer) ), which in turn calls R_igraph_finalizer(), which frees the contents of the "finally" stack

I'll have to look into how the callbacks are implemented to see if any of these is easy to fix.

[szhorvat]

Why do we need R_igraph_finalizer()? In what situation is this the only place where FINALLY_FREE() would be run?

[szhorvat]

BTW OP's example no longer seems to crash in dev version.

[ntamas]

R_igraph_finalizer() also takes care of hiding the progress bar in case it's still visible.

[szhorvat]

I'm just trying to understand the reason for IGRAPH_FINALLY_FREE() being run from that function. Are you aware of any case when this is necessary? It seems that freeing resources this way is dangerous and crash prone, so it'd be good to do it differently. But I don't understand very well how the R interface works, hence my question.

The progress bar seems to be an oerthogonal issue.

[ntamas]

I don't know; I'm not that familiar with the R internals either, but calling IGRAPH_FINALLY_FREE() multiple times should be safe. The calling-igraph-functions-from-callbacks problem should be solved with the introduction of the multi-level finally stack in the C core, so once we migrate to 0.10 in the R interface we can cross out the last remaining item from my comment.

[pchtsp]

BTW OP's example no longer seems to crash in dev version.

I just tried the current development version and the example still crashes for me. I hope the issue can be solved soon! And thanks for the library, it's great : )

> library('igraph')
> g <- make_tree(10)
> g<- set_vertex_attr(g, "xx", value = 10:19)
> f.in <- function(graph, data, extra) {
+     ## print(V(graph)[data[1]]$xx) $## I tried something like this but doesnt work
+     print(graph) ## even this crashes R
+     FALSE
+ }
> tmp <- bfs(g, root=1, "out",callback=f.in)
IGRAPH cb553c5 D--- 10 9 -- Tree
+ attr: name (g/c), children (g/n), mode (g/c), xx (v/n)
+ edges from cb553c5:
[1] 1-> 2 1-> 3 2-> 4 2-> 5 3-> 6 3-> 7 4-> 8 4-> 9 5->10
Error in bfs(g, root = 1, "out", callback = f.in) : 
  At core/core/dqueue.pmt:105 : Assertion failed: q->stor_begin != 0. This is an unexpected igraph error; please report this as a bug, along with the steps to reproduce it.

environment:

> sessionInfo()
R version 4.2.0 (2022-04-22)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu 20.04.4 LTS

Matrix products: default
BLAS:   /usr/lib/x86_64-linux-gnu/blas/libblas.so.3.9.0
LAPACK: /usr/lib/x86_64-linux-gnu/lapack/liblapack.so.3.9.0

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C               LC_TIME=en_US.UTF-8       
 [4] LC_COLLATE=en_US.UTF-8     LC_MONETARY=en_US.UTF-8    LC_MESSAGES=en_US.UTF-8   
 [7] LC_PAPER=en_US.UTF-8       LC_NAME=C                  LC_ADDRESS=C              
[10] LC_TELEPHONE=C             LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C       

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] igraph_1.3.1.9013

loaded via a namespace (and not attached):
[1] compiler_4.2.0  magrittr_2.0.3  tools_4.2.0     pkgconfig_2.0.3

[szhorvat]

Small copyable test case:

library('igraph')
g <- make_tree(10)
f.in <- function(graph, data, extra) { print(graph); FALSE }
bfs(g, root=1, "out",callback=f.in)

Stack trace:

    #0 0x1101c33e5 in __sanitizer_print_stack_trace+0x35 (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x543e5) (BuildId: e10aa413b3dc35e5b976a8a4fa9007742400000010000000000a0a00000e0a00)
    #1 0x115c1fca1 in R_igraph_fatal_handler+0x51 (igraph.so:x86_64+0x465ca1) (BuildId: 102c80ee74b13d378f5c7990a8ed881c320000002000000001000000000e0a00)
    #2 0x11589ead1 in igraph_fatal+0x11 (igraph.so:x86_64+0xe4ad1) (BuildId: 102c80ee74b13d378f5c7990a8ed881c320000002000000001000000000e0a00)
    #3 0x115899583 in igraph_dqueue_empty+0x83 (igraph.so:x86_64+0xdf583) (BuildId: 102c80ee74b13d378f5c7990a8ed881c320000002000000001000000000e0a00)
    #4 0x1159abead in igraph_bfs+0x95d (igraph.so:x86_64+0x1f1ead) (BuildId: 102c80ee74b13d378f5c7990a8ed881c320000002000000001000000000e0a00)
    #5 0x115c4ba63 in R_igraph_bfs+0x693 (igraph.so:x86_64+0x491a63) (BuildId: 102c80ee74b13d378f5c7990a8ed881c320000002000000001000000000e0a00)
    #6 0x10ee91407 in R_doDotCall dotcode.c
    #7 0x10ef3e738 in bcEval eval.c:7692
    #8 0x10ef24e4e in Rf_eval eval.c:748
    #9 0x10ef6af59 in R_execClosure eval.c
    #10 0x10ef56c2e in Rf_applyClosure eval.c:1844
    #11 0x10ef2598d in Rf_eval eval.c:871
    #12 0x10eff02e5 in Rf_ReplIteration main.c:264
    #13 0x10eff308e in run_Rmainloop main.c:316
    #14 0x10eff3182 in Rf_mainloop main.c:1201
    #15 0x10ed340b4 in main Rmain.c:29
    #16 0x7fff7e91f3d4 in start+0x0 (libdyld.dylib:x86_64+0x163d4) (BuildId: 002418ccad113d10865b015591d24e6c320000002000000001000000000e0a00)

It appears that print(graph) is necessary to produce this issue, and it might somehow cause the data structures of bfs be destroyed, probably with FINALLY_CLEAN (unverified).

Note that using igraph functions from callbacks is not currently supported. It is possible that print(graph) will internally call one of the affected functions.

[ntamas]

Addition: using print(unclass(g)) inside the callback works, which points further towards the direction of print() (or, more precisely, print.igraph). Adding another print after print(g) in the callback gets executed correctly, so print() within the callback is not returning an error, therefore I don't think that the error handler is involved; it must be something else.

[ntamas]

Okay, so it's simple and it will be solved in future versions when we switch the C core to 0.10, where we have the multi-level error stack available. The problem appears not only with print() but also with simpler igraph functions like is_directed(graph). The source code of the R part of is_directed(graph) looks like this:

function (graph)
{
    if (!is_igraph(graph)) {
        stop("Not a graph object")
    }
    on.exit(.Call(C_R_igraph_finalizer))
    .Call(C_R_igraph_is_directed, graph)
}

on.exit() is meant to schedule a call to C_R_igraph_finalizer when the execution returns to the top level. However, since the callbacks are now executed in a separate R context (so we can catch errors from the callback), C_R_igraph_finalizer gets called when we return from the R side of the callback to the C side of the callback inside the BFS, and indeed C_R_igraph_finalizer frees all the data structures required for the BFS at that point as it knows nothing about the callback.

Since igraph 0.10 on the C side is still far away in the pipeline, I'll try to think about alternative solutions.

[szhorvat]

@krlmlr Fixing this is unrealistic within the timeframe we have for 2.0.0. Removing from blocker list, re-add if you disagree.