Setting attribute to vertex sequence leads to failed assertion

[krlmlr]

Describe the bug

A specific usage pattern leads to a failed assertion in the C core.

To reproduce

options(conflicts.policy = list(warn = FALSE))
library(igraph)

gg <- make_ring(3, directed = TRUE)
V(gg)$id <- V(gg)
subgraph(gg, 1)
#> Error in induced_subgraph(graph, vids): At core/core/vector.pmt:483 : Assertion failed: v->stor_begin != NULL. This is an unexpected igraph error; please report this as a bug, along with the steps to reproduce it.
#> Please restart your R session to avoid crashes or other surprising behavior.

^{Created on 2023-05-21 with reprex v2.0.2}

Version information

• R/igraph version: 342586e
• R version: 4.3.0
• Operating system: macOS

[krlmlr]

Introduced in efc8bec.

[krlmlr]

This particular commit has been added to trigger the creation of the native igraph object. Maybe we need to be more careful with what we allow as attributes. Do we really need to support vertex/edge sequences as attributes?

[krlmlr]

CRAN igraph

options(conflicts.policy = list(warn = FALSE))
library(igraph)

gg <- make_ring(2, directed = TRUE)
V(gg)$id <- V(gg)
dput(gg)
#> structure(list(2, TRUE, c(0, 1), c(1, 0), c(0, 1), c(1, 0), c(0, 
#> 1, 2), c(0, 1, 2), list(c(1, 0, 1), list(name = "Ring graph", 
#>     mutual = FALSE, circular = TRUE), list(id = structure(1:2, class = "igraph.vs", is_all = TRUE, env = <weak reference>, graph = "17d54ab3-1bea-4723-8d5f-2e86ada40fe5")), 
#>     list()), <environment>), class = "igraph")
dput(as.list(unclass(gg)[[10]]))
#> list(me = structure(list(2, TRUE, c(0, 1), c(1, 0), c(0, 1), 
#>     c(1, 0), c(0, 1, 2), c(0, 1, 2), list(c(1, 0, 1), list(name = "Ring graph", 
#>         mutual = FALSE, circular = TRUE), list(), list()), <environment>), class = "igraph"), 
#>     myid = "17d54ab3-1bea-4723-8d5f-2e86ada40fe5")

^{Created on 2023-05-21 with reprex v2.0.2}

dev igraph

options(conflicts.policy = list(warn = FALSE))
library(igraph)

gg <- make_ring(2, directed = TRUE)
V(gg)$id <- V(gg)
dput(gg)
#> structure(list(2, TRUE, c(0, 1), c(1, 0), NULL, NULL, NULL, NULL, 
#>     list(c(1, 0, 1), list(name = "Ring graph", mutual = FALSE, 
#>         circular = TRUE), list(id = structure(1:2, class = "igraph.vs", is_all = TRUE, env = <weak reference>, graph = "a59b2801-46a9-4a00-a77b-53c364c25ac5")), 
#>         list()), <environment>), class = "igraph")
dput(as.list(unclass(gg)[[10]]))
#> list(me = structure(list(2, TRUE, c(0, 1), c(1, 0), NULL, NULL, 
#>     NULL, NULL, list(c(1, 0, 1), list(name = "Ring graph", mutual = FALSE, 
#>         circular = TRUE), list(), list()), <environment>), class = "igraph"), 
#>     igraph = <pointer: 0x600000ac81e0>, myid = "a59b2801-46a9-4a00-a77b-53c364c25ac5")

^{Created on 2023-05-21 with reprex v2.0.2}

[krlmlr]

This is getting way too complicated. Do we even need to support sequences as vertex/edge attributes? Perhaps it's worth doing a revdepcheck with just that change on top of v1.4.2 .

[szhorvat]

Do you have a clear understanding of how that null pointer arises, and if yes, can you please share it? (BTW an ASan-enabled test would make this much clearer as fatal errors cause the printing of a stack trace.)

The fix you propose is for the symptom, but it's good to be aware of the underlying cause ...

[szhorvat]

Do we even need to support sequences as vertex/edge attributes?

Theoretically, there's some benefit, as one might want to maintain a mapping between the vertex (or edges) of two graphs, e.g. after vertex deletion or subsetting. This is a convenient way to do it. Of course, using plain vertex or edge IDs would also achieve the same.

[szhorvat]

ASan output:

subgraph(gg, 1)
    #0 0x109b3b475 in __sanitizer_print_stack_trace+0x35 (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x53475) (BuildId: 7b794d8c5f0d346faaffee92f0e796262400000010000000000a0a00000e0a00)
    #1 0x1182cf7c8 in R_igraph_fatal_handler rinterface_extra.c:2446
    #2 0x117f1c221 in igraph_fatal error.c:368
    #3 0x117f62652 in igraph_vector_size vector.pmt:483
    #4 0x1182c8781 in R_igraph_attribute_permute_edges_diff rinterface_extra.c:1215
    #5 0x1182c8a0d in R_igraph_attribute_permute_edges rinterface_extra.c:1257
    #6 0x1181de099 in igraph_i_induced_subgraph_map subgraph.c:250
    #7 0x1181dcc2f in igraph_induced_subgraph subgraph.c:364
    #8 0x1182a0702 in R_igraph_induced_subgraph rinterface.c:1506
    #9 0x1087c85a7 in R_doDotCall dotcode.c:874
    #10 0x1087d503a in do_dotcall dotcode.c:1551
    #11 0x1088629d3 in Rf_eval eval.c:1120
    #12 0x1088b1c69 in do_set eval.c:3250
    #13 0x1088625f9 in Rf_eval eval.c:1092
    #14 0x1088b09f7 in do_begin eval.c:2798
    #15 0x1088625f9 in Rf_eval eval.c:1092
    #16 0x1088a7b20 in R_execClosure eval.c
    #17 0x1088931ef in Rf_applyClosure eval.c:2113
    #18 0x108862af7 in Rf_eval eval.c:1140
    #19 0x1088b09f7 in do_begin eval.c:2798
    #20 0x1088625f9 in Rf_eval eval.c:1092
    #21 0x1088a7b20 in R_execClosure eval.c
    #22 0x1088931ef in Rf_applyClosure eval.c:2113
    #23 0x108862af7 in Rf_eval eval.c:1140
    #24 0x108937b88 in Rf_ReplIteration main.c:262
    #25 0x10893a99e in run_Rmainloop main.c:314
    #26 0x10893aa92 in Rf_mainloop main.c:1215
    #27 0x10865c805 in main Rmain.c:29
    #28 0x7fff5dd5d3d4 in start+0x0 (libdyld.dylib:x86_64+0x163d4) (BuildId: 002418ccad113d10865b015591d24e6c320000002000000001000000000e0a00)

Error in induced_subgraph(graph, vids) : 
  At core/core/vector.pmt:483 : Assertion failed: v->stor_begin != NULL. This is an unexpected igraph error; please report this as a bug, along with the steps to reproduce it.
Please restart your R session to avoid crashes or other surprising behavior.

To get line numbers, the package must be loaded from the dev directory instead of the installed location.

library(devtools)
load_all()

gg <- make_ring(3, directed = TRUE)
V(gg)$id <- V(gg)
subgraph(gg, 1)

[szhorvat]

As far as I can tell, the NULL pointer is present in the eids_new2old vector which is initialized in igraph_i_induced_subgraph_create_from_scratch(), i.e. not R/igraph code. How does this become NULL? This is very strange and should be fully understood before closing this issue, as there's a potential of a more serious underlying issue. Is the finally stack being prematurely unwound? Let's not close this with a purely symptomatic fix.

[szhorvat]

Some more investigation (adding extra IGRAPH_ASSERTs) shows that eids_new2old.stor_begin becomes NULL during this call:

https://github.com/igraph/igraph/blob/release/0.9/src/operators/subgraph.c#L246

Copying the code with context and annotating it:

    /* Copy the graph attributes */
    IGRAPH_CHECK(igraph_i_attribute_copy(res, graph,
                                         /* ga = */ 1, /* va = */ 0, /* ea = */ 0));

    // eids_new2old is valid here

    /* Copy the vertex attributes */
    IGRAPH_CHECK(igraph_i_attribute_permute_vertices(graph, res,
                 my_vids_new2old));

    // eids_new2old is no longer valid here, eids_new2old.stor_begin is now NULL

    /* Copy the edge attributes */
    IGRAPH_CHECK(igraph_i_attribute_permute_edges(graph, res, &eids_new2old));

This makes no sense to me, since igraph_i_attribute_permute_vertices() doesn't even have access to eids_new2old. The only explanation I can think of is that something unwinds the finally stack without properly escaping. In other words, the implementation of R_igraph_attribute_permute_vertices() may be lacking some important error checks. @Antonov548, is this possible?

CC @ntamas

[Antonov548]

@Antonov548, is this possible?

During the changes of igraph stucture, attributes was not changed and also as I see the vector which is lost pointer allocated just in C, so seems it's really some exception inside of igraph_i_attribute_permute_vertices. I will try to debug this.

[szhorvat]

Indeed something calls IGRAPH_FINALLY_FREE() during R_igraph_attribute_permute_vertices_diff(), but looking at that function I don't quite see how this is possible without actually aborting and returning to the top level. Perhaps one of the R API calls fails, but now things are set up so that error() doesn't immediately jump to the top level?

After adding some printfs to R_igraph_attribute_permute_vertices_diff() and uncommenting the debug line in IGRAPH_FINALLY_FREE(), I see:

Calling igraph_i_attribute_permute_vertices()
START R_igraph_attribute_permute_vertices_diff()
[X] Finally stack will be cleaned (contained 3 elements)
[X] Finally stack will be cleaned (contained 0 elements)
END R_igraph_attribute_permute_vertices_diff()
    #0 0x10efcc475 in __sanitizer_print_stack_trace+0x35 (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x53475) (BuildId: 7b794d8c5f0d346faaffee92f0e796262400000010000000000a0a00000e0a00)
    #1 0x11d77b588 in R_igraph_fatal_handler rinterface_extra.c:2456
    #2 0x11d3c7e61 in igraph_fatal error.c:368
    #3 0x11d40e292 in igraph_vector_size vector.pmt:483
    #4 0x11d774541 in R_igraph_attribute_permute_edges_diff rinterface_extra.c:1225
    #5 0x11d7747cd in R_igraph_attribute_permute_edges rinterface_extra.c:1267
    #6 0x11d689c14 in igraph_i_induced_subgraph_map subgraph.c:255
    #7 0x11d68886f in igraph_induced_subgraph subgraph.c:369
    #8 0x11d74c492 in R_igraph_induced_subgraph rinterface.c:1506

[Antonov548]

Indeed something calls IGRAPH_FINALLY_FREE() during R_igraph_attribute_permute_vertices_diff(), but looking at that function I don't quite see how this is possible without actually aborting and returning to the top level. Perhaps one of the R API calls fails, but now things are set up so that error() doesn't immediately jump to the top level?

After adding some printfs to R_igraph_attribute_permute_vertices_diff() and uncommenting the debug line in IGRAPH_FINALLY_FREE(), I see:

Calling permute_vertices()
START permute_vertices_diff()
[X] Finally stack will be cleaned (contained 3 elements)
[X] Finally stack will be cleaned (contained 0 elements)
END permute_vertices_diff()
    #0 0x10efcc475 in __sanitizer_print_stack_trace+0x35 (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x53475) (BuildId: 7b794d8c5f0d346faaffee92f0e796262400000010000000000a0a00000e0a00)
    #1 0x11d77b588 in R_igraph_fatal_handler rinterface_extra.c:2456
    #2 0x11d3c7e61 in igraph_fatal error.c:368
    #3 0x11d40e292 in igraph_vector_size vector.pmt:483
    #4 0x11d774541 in R_igraph_attribute_permute_edges_diff rinterface_extra.c:1225
    #5 0x11d7747cd in R_igraph_attribute_permute_edges rinterface_extra.c:1267
    #6 0x11d689c14 in igraph_i_induced_subgraph_map subgraph.c:255
    #7 0x11d68886f in igraph_induced_subgraph subgraph.c:369
    #8 0x11d74c492 in R_igraph_induced_subgraph rinterface.c:1506

Exception is coming from igraph_vector_size . I would suggest that idx argument is invalid in R_igraph_attribute_permute_edges_diff function.

Which also means that my_vids_new2old is invalid?

[szhorvat]

No, not quite. But I already debugged that far.

What is happening is that something triggers a call to IGRAPH_FINALLY_FREE() within the function R_igraph_attribute_permute_vertices_diff(). This should not happen unless jumping back to the top level, as it will free all of igraph's internal data structures which are still in use. The question is, how is this FINALLY_FREE() call triggered from R_igraph_attribute_permute_vertices_diff() given that this function doesn't even use the igraph API?

Hypothesis:

One of the R API calls fails, resulting in a call to error(). This is probably caught by one of the uses of tryCatch, such as the one in R_igraph_safe_eval_in_env(), preventing a return to the top level. But a "finalizer" still gets called.

Can you substantiate or refute this hypothesis @Antonov548 ?

[szhorvat]

To be more specific, this line fails in some way in R_igraph_attribute_permute_vertices_diff() and ends up calling R_igraph_finalizer():

SEXP newva = PROTECT(Rf_eval(l2, R_GlobalEnv));

What's to be resolved is not quite why it fails (has to do with copying a vertex selector, I guess), but why that failure doesn't result in a return to the top level, and whether anything can be done about that.

Or if this is not actually a failure, why does the above quoted line end up calling R_igraph_finalizer()??

[ntamas]

@szhorvat 's hypothesis is a plausible explanation. I don't really know whether the attribute handler implementation in R is rigorously prepared for handling errors, and even if so, how does it handle longjmps and stuff.

[krlmlr]

I believe `[.igraph.vs` <- function(x, ..., na_ok = FALSE) { is called in the process. Can we add logging (at the R level) to that function?

Ideally, the entire loop in R_igraph_attribute_permute_vertices_diff() would be implemented in R, with suitable exception handling, to ensure we don't leak errors here.

[szhorvat]

What kind of performance impact would that have? Note that this function will be invoked during any sort of graph modification or subsetting, so it is performance critical.

But what's missing here for me is an understanding of why the finalizer gets invoked here at all. This is a greater problem that can cause problems elsewhere too.

[szhorvat]

@Antonov548 @krlmlr If I understood you right, you are saying that this is basically an instance of the last bullet point of #253 (comment), i.e. calling an R/igraph function from C code? In other words, there is no failure, but some part of [.igraph.vs will end up using on.exit(.Call(R_igraph_finalizer))?

If so, then the ENTER/EXIT mechanism of igraph 0.10 should be helpful here. It allows inserting checkpoints in the "finally stack" (the stack of destructor calls) so that a single call to IGRAPH_FINALLY_FREE() would only run destructors up to the first checkpoint.

Also, if so, then it's entirely reasonable to fix this now by disallowing vertex/edge selectors as attributes (or rather converting to indices, as you did @krlmlr )

[Antonov548]

@szhorvat @krlmlr @ntamas

I have another one theory :)

Which seems the most possible for me as I think.

So, first of all I know how to fix example which is failing:

options(conflicts.policy = list(warn = FALSE))
library(igraph)

gg <- make_ring(3, directed = TRUE)
V(gg)$id <- V(gg)
subgraph(gg, 1)
#> Error in induced_subgraph(graph, vids): At core/core/vector.pmt:483 : Assertion failed: v->stor_begin != NULL. This is an unexpected igraph error; please report this as a bug, along with the steps to reproduce it.
#> Please restart your R session to avoid crashes or other surprising behavior.

Need to comment this line.

What is problem in this code:
attr(x, "env") - is weak reference to enviorement of igraph as I understand.
We create this weak reference when try to access vertices in V function (just like in the example). And when we create weak reference we .Call R_igraph_copy_env which copies enviorement from graph with Rf_duplicate.

And here is the thing: in the enviorement in dev version there is pointer to native stucture and the question is how Rf_duplicate copies this pointer and should we create deep copy of pointer.

[krlmlr]

Do we really need that complexity in `[.igraph.vs`() and friends?

[mbojan]

Chipping in as a person who incidentally bumped into that issue... From a user perspective I think the main (only?) concern is whether igraph will allow an arbitrary vector-like object (atomic vector or list with attr()ibutes) as vertex/edge attribute or not.

[krlmlr]

@Antonov548: Is this fixed with #813?

[szhorvat]

Is this fixed with #813?

No, those two fixes in #813 are completely unrelated.

[krlmlr]

Closed with #808.

[szhorvat]

@Antonov548

What is problem in this code:
attr(x, "env") - is weak reference to enviorement of igraph as I understand.
We create this weak reference when try to access vertices in V function (just like in the example). And when we create weak reference we .Call R_igraph_copy_env which copies enviorement from graph with Rf_duplicate.

Can you clarify how this leads to the invocation of the finalizer?

[github-actions]

This old thread has been automatically locked. If you think you have found something related to this, please open a new issue and link to this old issue if necessary.