Self-recursive type definition with a Union segfaults

[Liozou]

Hi everyone! I just noticed that defining such a type segfaults:

struct Foo
   x::Union{Foo, Nothing}
end

yields

signal (11): Segmentation fault
in expression starting at REPL[1]:1
union_isbits at /home/liozou/julia/src/datatype.c:260
union_isbits at /home/liozou/julia/src/datatype.c:253
jl_islayout_inline at /home/liozou/julia/src/datatype.c:272
jl_compute_field_offsets at /home/liozou/julia/src/datatype.c:320
eval_structtype at /home/liozou/julia/src/interpreter.c:277
eval_body at /home/liozou/julia/src/interpreter.c:746
jl_interpret_toplevel_thunk_callback at /home/liozou/julia/src/interpreter.c:888
unknown function (ip: 0x7f617b33702b)
jl_interpret_toplevel_thunk at /home/liozou/julia/src/interpreter.c:897
jl_toplevel_eval_flex at /home/liozou/julia/src/toplevel.c:814
jl_toplevel_eval_flex at /home/liozou/julia/src/toplevel.c:764
jl_toplevel_eval at /home/liozou/julia/src/toplevel.c:823
jl_toplevel_eval_in at /home/liozou/julia/src/toplevel.c:843
eval at ./boot.jl:331
jl_fptr_args at /home/liozou/julia/src/gf.c:1910
_jl_invoke at /home/liozou/julia/src/gf.c:2130
jl_apply_generic at /home/liozou/julia/src/gf.c:2300
eval_user_input at /home/liozou/julia/usr/share/julia/stdlib/v1.4/REPL/src/REPL.jl:86
macro expansion at /home/liozou/julia/usr/share/julia/stdlib/v1.4/REPL/src/REPL.jl:118 [inlined]
#26 at ./task.jl:333
jl_fptr_args at /home/liozou/julia/src/gf.c:1910
_jl_invoke at /home/liozou/julia/src/gf.c:2130
jl_apply_generic at /home/liozou/julia/src/gf.c:2300
jl_apply at /home/liozou/julia/src/julia.h:1647
start_task at /home/liozou/julia/src/task.c:687
unknown function (ip: (nil))
Allocations: 934653 (Pool: 934420; Big: 233); GC: 1
Segmentation fault (core dumped)

I don't have a particular use case for this but I believe this should at most error instead of segfaulting. Git-bisection shows that #32448 introduced this behaviour. This code for instance used to work (and is now broken):

julia> struct Foo
          x::Union{Foo, Nothing}
       end

julia> function foo(x,n)
           for _ in 1:n
               x = Foo(x)
           end
           return x
       end
foo (generic function with 1 method)

julia> Base.length(f::Foo) = isnothing(f.x) ? 1 : 1 + length(f.x)

julia> length(foo(nothing, 1000))
1000

Version info:

julia> versioninfo()
Julia Version 1.4.0-DEV.379
Commit 88c34fc51d (2019-10-28 14:08 UTC)
DEBUG build
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

[quinnj]

Thanks for the detailed report; I'll take a look.

[quinnj]

@JeffBezanson, @vtjnash, @Keno (and whoever else may know/have an opinion),

The issue here is when constructing Foo, we check if its fields are jl_islayout_inline, which in turn calls union_isbits, which has no problem looking at Nothing, but when it checks Foo, it doesn't have a defined ty->layout yet, so the call to jl_datatype_align(ty) (ty->layout->alignment) segfaults.

Now, changing the union_isbits check to:

if (jl_is_datatype(ty) && jl_datatype_isinlinealloc(ty) && (((jl_datatype_t *)ty)->layout)) {
        size_t sz = jl_datatype_size(ty);
        size_t al = jl_datatype_align(ty);
        if (*nbytes < sz)
            *nbytes = sz;
        if (*align < al)
            *align = al;
        return 1;
    }

seems to do the trick, i.e. avoids allowing a recursive type to be marked inlinealloc, but I'm not sure if we'd prefer a more "principled" fix by somehow checking for the recursion directly in jl_compute_field_offsets or union_isbits.

I can put up a PR w/ the ty->layout check fix + test if we want to go that route, or I'm happy to discuss an alternative solution.

[vtjnash]

There’s already code there to prohibit inlining of recursive types. It’s currently run late, since the ordering didn’t use to matter. Apparently it should now run first.

[Keno]

Maybe check my branch for mutually recursive fielstypes. I had to address a bunch of these kinds of issues there.

[Liozou]

As @vtjnash suggested, I tried to put the code preventing inlining of recursive types at the top of the function, and it does solve the problem. The entire diff is

diff --git a/src/datatype.c b/src/datatype.c
index 9cf1ec58e0..fd0d8639aa 100644
--- a/src/datatype.c
+++ b/src/datatype.c
@@ -311,6 +311,18 @@ void jl_compute_field_offsets(jl_datatype_t *st)
         // based on whether its definition is self-referential
         if (w->types != NULL) {
             st->isbitstype = st->isinlinealloc = st->isconcretetype && !st->mutabl;
+            if (st->isinlinealloc) {
+                size_t i, nf = jl_svec_len(w->types);
+                for (i = 0; i < nf; i++) {
+                    jl_value_t *fld = jl_svecref(w->types, i);
+                    if (references_name(fld, w->name)) {
+                        st->isinlinealloc = 0;
+                        st->isbitstype = 0;
+                        st->zeroinit = 1;
+                        break;
+                    }
+                }
+            }
             size_t i, nf = jl_svec_len(st->types);
             for (i = 0; i < nf; i++) {
                 jl_value_t *fld = jl_svecref(st->types, i);
@@ -327,18 +339,6 @@ void jl_compute_field_offsets(jl_datatype_t *st)
                         st->has_concrete_subtype &= !jl_is_datatype(fld) || ((jl_datatype_t *)fld)->has_concrete_subtype;
                 }
             }
-            if (st->isinlinealloc) {
-                size_t i, nf = jl_svec_len(w->types);
-                for (i = 0; i < nf; i++) {
-                    jl_value_t *fld = jl_svecref(w->types, i);
-                    if (references_name(fld, w->name)) {
-                        st->isinlinealloc = 0;
-                        st->isbitstype = 0;
-                        st->zeroinit = 1;
-                        break;
-                    }
-                }
-            }
         }
         // If layout doesn't depend on type parameters, it's stored in st->name->wrapper
         // and reused by all subtypes.

I think this solution is the more specific option @quinnj was looking for, (but please correct me if I'm wrong!) so should I go ahead and make a PR?

[quinnj]

@Liozou, that’d be great! Thanks!