Ractor.make_shareable(obj)

Introduce new method Ractor.make_shareable(obj) which tries to make
obj shareable object. Protocol is here.

(1) If obj is shareable, it is shareable.
(2) If obj is not a shareable object and if obj can be shareable
    object if it is frozen, then freeze obj. If obj has reachable
    objects (rs), do rs.each{|o| Ractor.make_shareable(o)}
    recursively (recursion is not Ruby-level, but C-level).
(3) Otherwise, raise Ractor::Error. Now T_DATA is not a shareable
    object even if the object is frozen.

If the method finished without error, given obj is marked as
a sharable object.

To allow makng a shareable frozen T_DATA object, then set
`RUBY_TYPED_FROZEN_SHAREABLE` as type->flags. On default,
this flag is not set. It means user defined T_DATA objects are
not allowed to become shareable objects when it is frozen.

You can make any object  shareable by setting FL_SHAREABLE flag,
so if you know that the T_DATA object is shareable (== thread-safe),
set this flag, at creation time for example. `Ractor` object is one
example, which is not a frozen, but a shareable object.

7 files changed, 384 insertions, 125 deletions

diff --git a/bootstraptest/test_ractor.rb b/bootstraptest/test_ractor.rb
index f951d4b938..6290b73c36 100644
--- a/bootstraptest/test_ractor.rb
+++ b/bootstraptest/test_ractor.rb
@@ -832,6 +832,80 @@ assert_equal '0', %q{
   }.take
 }
 
+# Ractor.make_shareable(obj)
+assert_equal 'true', %q{
+  class C
+    def initialize
+      @a = 'foo'
+      @b = 'bar'
+    end
+    attr_reader :a, :b
+  end
+  S = Struct.new(:s1, :s2)
+  str = "hello"
+  str.instance_variable_set("@iv", "hello")
+  /a/ =~ 'a'
+  m = $~
+  class N < Numeric
+    def /(other)
+      1
+    end
+  end
+  ary = []; ary << ary
+
+  a = [[1, ['2', '3']],
+       {Object.new => "hello"},
+       C.new,
+       S.new("x", "y"),
+       ("a".."b"),
+       str,
+       ary,             # cycle
+       /regexp/,
+       /#{'r'.upcase}/,
+       m,
+       Complex(N.new,0),
+       Rational(N.new,0),
+       true,
+       false,
+       nil,
+       1, 1.2, 1+3r, 1+4i, # Numeric
+  ]
+  Ractor.make_shareable(a)
+
+  # check all frozen
+  a.each{|o|
+    raise o.inspect unless o.frozen?
+
+    case o
+    when C
+      raise o.a.inspect unless o.a.frozen?
+      raise o.b.inspect unless o.b.frozen?
+    when Rational
+      raise o.numerator.inspect unless o.numerator.frozen?
+    when Complex
+      raise o.real.inspect unless o.real.frozen?
+    when Array
+      if o[0] == 1
+        raise o[1][1].inspect unless o[1][1].frozen?
+      end
+    when Hash
+      o.each{|k, v|
+        raise k.inspect unless k.frozen?
+        raise v.inspect unless v.frozen?
+      }
+    end
+  }
+
+  Ractor.shareable?(a)
+}
+
+# Ractor.make_shareable(obj) doesn't freeze shareable objects
+assert_equal 'true', %q{
+  r = Ractor.new{}
+  Ractor.make_shareable(a = [r])
+  [a.frozen?, a[0].frozen?] == [true, false]
+}
+
 ###
 ### Synchronization tests
 ###
diff --git a/common.mk b/common.mk
index a8719ca4e6..7b5ab6fbdd 100644
--- a/common.mk
+++ b/common.mk
@@ -10193,10 +10193,17 @@ ractor.$(OBJEXT): $(CCAN_DIR)/list/list.h
 ractor.$(OBJEXT): $(CCAN_DIR)/str/str.h
 ractor.$(OBJEXT): $(hdrdir)/ruby/ruby.h
 ractor.$(OBJEXT): $(top_srcdir)/internal/array.h
+ractor.$(OBJEXT): $(top_srcdir)/internal/bignum.h
+ractor.$(OBJEXT): $(top_srcdir)/internal/bits.h
 ractor.$(OBJEXT): $(top_srcdir)/internal/compilers.h
+ractor.$(OBJEXT): $(top_srcdir)/internal/complex.h
 ractor.$(OBJEXT): $(top_srcdir)/internal/error.h
+ractor.$(OBJEXT): $(top_srcdir)/internal/fixnum.h
 ractor.$(OBJEXT): $(top_srcdir)/internal/gc.h
+ractor.$(OBJEXT): $(top_srcdir)/internal/hash.h
 ractor.$(OBJEXT): $(top_srcdir)/internal/imemo.h
+ractor.$(OBJEXT): $(top_srcdir)/internal/numeric.h
+ractor.$(OBJEXT): $(top_srcdir)/internal/rational.h
 ractor.$(OBJEXT): $(top_srcdir)/internal/serial.h
 ractor.$(OBJEXT): $(top_srcdir)/internal/static_assert.h
 ractor.$(OBJEXT): $(top_srcdir)/internal/string.h
@@ -10220,6 +10227,7 @@ ractor.$(OBJEXT): {$(VPATH)}debug.h
 ractor.$(OBJEXT): {$(VPATH)}debug_counter.h
 ractor.$(OBJEXT): {$(VPATH)}defines.h
 ractor.$(OBJEXT): {$(VPATH)}encoding.h
+ractor.$(OBJEXT): {$(VPATH)}gc.h
 ractor.$(OBJEXT): {$(VPATH)}id.h
 ractor.$(OBJEXT): {$(VPATH)}id_table.h
 ractor.$(OBJEXT): {$(VPATH)}intern.h
@@ -10381,6 +10389,7 @@ ractor.$(OBJEXT): {$(VPATH)}subst.h
 ractor.$(OBJEXT): {$(VPATH)}thread.h
 ractor.$(OBJEXT): {$(VPATH)}thread_$(THREAD_MODEL).h
 ractor.$(OBJEXT): {$(VPATH)}thread_native.h
+ractor.$(OBJEXT): {$(VPATH)}variable.h
 ractor.$(OBJEXT): {$(VPATH)}vm_core.h
 ractor.$(OBJEXT): {$(VPATH)}vm_debug.h
 ractor.$(OBJEXT): {$(VPATH)}vm_opts.h
diff --git a/include/ruby/internal/core/rtypeddata.h b/include/ruby/internal/core/rtypeddata.h
index 3ffe07ec5e..c038e6f2b8 100644
--- a/include/ruby/internal/core/rtypeddata.h
+++ b/include/ruby/internal/core/rtypeddata.h
@@ -52,6 +52,7 @@
 #define RTYPEDDATA_P                 RTYPEDDATA_P
 #define RTYPEDDATA_TYPE              RTYPEDDATA_TYPE
 #define RUBY_TYPED_FREE_IMMEDIATELY  RUBY_TYPED_FREE_IMMEDIATELY
+#define RUBY_TYPED_FROZEN_SHAREABLE  RUBY_TYPED_FROZEN_SHAREABLE
 #define RUBY_TYPED_WB_PROTECTED      RUBY_TYPED_WB_PROTECTED
 #define RUBY_TYPED_PROMOTED1         RUBY_TYPED_PROMOTED1
 /** @endcond */
@@ -59,6 +60,7 @@
 /* bits for rb_data_type_struct::flags */
 enum rbimpl_typeddata_flags {
     RUBY_TYPED_FREE_IMMEDIATELY = 1,
+    RUBY_TYPED_FROZEN_SHAREABLE = RUBY_FL_SHAREABLE,
     RUBY_TYPED_WB_PROTECTED     = RUBY_FL_WB_PROTECTED, /* THIS FLAG DEPENDS ON Ruby version */
     RUBY_TYPED_PROMOTED1        = RUBY_FL_PROMOTED1     /* THIS FLAG DEPENDS ON Ruby version */
 };
diff --git a/internal/hash.h b/internal/hash.h
index 237ce58603..a4677c581b 100644
--- a/internal/hash.h
+++ b/internal/hash.h
@@ -83,6 +83,8 @@ VALUE rb_hash_set_pair(VALUE hash, VALUE pair);
 int rb_hash_stlike_delete(VALUE hash, st_data_t *pkey, st_data_t *pval);
 int rb_hash_stlike_foreach_with_replace(VALUE hash, st_foreach_check_callback_func *func, st_update_callback_func *replace, st_data_t arg);
 int rb_hash_stlike_update(VALUE hash, st_data_t key, st_update_callback_func *func, st_data_t arg);
+extern st_table *rb_hash_st_table(VALUE hash);
+
 static inline unsigned RHASH_AR_TABLE_SIZE_RAW(VALUE h);
 static inline VALUE RHASH_IFNONE(VALUE h);
 static inline size_t RHASH_SIZE(VALUE h);
@@ -135,7 +137,6 @@ RHASH_AR_TABLE(VALUE h)
 static inline st_table *
 RHASH_ST_TABLE(VALUE h)
 {
-    extern st_table *rb_hash_st_table(VALUE hash);
     return rb_hash_st_table(h)
 }
 
diff --git a/ractor.c b/ractor.c
index 68ac5a25fe..8c498a86b1 100644
--- a/ractor.c
+++ b/ractor.c
@@ -6,8 +6,13 @@
 #include "vm_core.h"
 #include "vm_sync.h"
 #include "ractor.h"
+#include "internal/complex.h"
 #include "internal/error.h"
+#include "internal/hash.h"
+#include "internal/rational.h"
 #include "internal/struct.h"
+#include "variable.h"
+#include "gc.h"
 
 static VALUE rb_cRactor;
 static VALUE rb_eRactorError;
@@ -1743,8 +1748,6 @@ rb_vm_main_ractor_ec(rb_vm_t *vm)
     return vm->ractor.main_ractor->threads.running_ec;
 }
 
-#include "ractor.rbinc"
-
 static VALUE
 ractor_moved_missing(int argc, VALUE *argv, VALUE self)
 {
@@ -1777,128 +1780,6 @@ Init_Ractor(void)
     rb_obj_freeze(rb_cRactorMovedObject);
 }
 
-static int
-rb_ractor_shareable_p_hash_i(VALUE key, VALUE value, VALUE arg)
-{
-    // TODO: should we need to avoid recursion to prevent stack overflow?
-    if (!rb_ractor_shareable_p(key) || !rb_ractor_shareable_p(value)) {
-        bool *shareable = (bool*)arg;
-        *shareable = false;
-        return ST_STOP;
-    }
-    return ST_CONTINUE;
-}
-
-static bool
-ractor_struct_shareable_members_p(VALUE obj)
-{
-    VM_ASSERT(RB_TYPE_P(obj, T_STRUCT));
-
-    long len = RSTRUCT_LEN(obj);
-    const VALUE *ptr = RSTRUCT_CONST_PTR(obj);
-
-    for (long i=0; i<len; i++) {
-        if (!rb_ractor_shareable_p(ptr[i])) {
-            return false;
-        }
-    }
-    return true;
-}
-
-static bool
-ractor_obj_ivars_shareable_p(VALUE obj)
-{
-    uint32_t len = ROBJECT_NUMIV(obj);
-    VALUE *ptr = ROBJECT_IVPTR(obj);
-
-    for (uint32_t i=0; i<len; i++) {
-        VALUE val = ptr[i];
-        if (val != Qundef && !rb_ractor_shareable_p(ptr[i])) {
-            return false;
-        }
-    }
-
-    return true;
-}
-
-MJIT_FUNC_EXPORTED bool
-rb_ractor_shareable_p_continue(VALUE obj)
-{
-    switch (BUILTIN_TYPE(obj)) {
-      case T_CLASS:
-      case T_MODULE:
-      case T_ICLASS:
-        goto shareable;
-
-      case T_FLOAT:
-      case T_COMPLEX:
-      case T_RATIONAL:
-      case T_BIGNUM:
-      case T_SYMBOL:
-        VM_ASSERT(RB_OBJ_FROZEN_RAW(obj));
-        goto shareable;
-
-      case T_STRING:
-      case T_REGEXP:
-        if (RB_OBJ_FROZEN_RAW(obj) &&
-            !FL_TEST_RAW(obj, RUBY_FL_EXIVAR)) {
-            goto shareable;
-        }
-        return false;
-      case T_ARRAY:
-        if (!RB_OBJ_FROZEN_RAW(obj) ||
-            FL_TEST_RAW(obj, RUBY_FL_EXIVAR)) {
-            return false;
-        }
-        else {
-            for (int i = 0; i < RARRAY_LEN(obj); i++) {
-                if (!rb_ractor_shareable_p(rb_ary_entry(obj, i))) return false;
-            }
-            goto shareable;
-        }
-      case T_HASH:
-        if (!RB_OBJ_FROZEN_RAW(obj) ||
-            FL_TEST_RAW(obj, RUBY_FL_EXIVAR)) {
-            return false;
-        }
-        else {
-            bool shareable = true;
-            rb_hash_foreach(obj, rb_ractor_shareable_p_hash_i, (VALUE)&shareable);
-            if (shareable) {
-                goto shareable;
-            }
-            else {
-                return false;
-            }
-        }
-      case T_STRUCT:
-        if (!RB_OBJ_FROZEN_RAW(obj) ||
-            FL_TEST_RAW(obj, RUBY_FL_EXIVAR)) {
-            return false;
-        }
-        else {
-            if (ractor_struct_shareable_members_p(obj)) {
-                goto shareable;
-            }
-            else {
-                return false;
-            }
-        }
-      case T_OBJECT:
-        if (RB_OBJ_FROZEN_RAW(obj) && ractor_obj_ivars_shareable_p(obj)) {
-            goto shareable;
-        }
-        else {
-            return false;
-        }
-      default:
-        return false;
-    }
-  shareable:
-    FL_SET_RAW(obj, RUBY_FL_SHAREABLE);
-    return true;
-}
-
 void
 rb_ractor_dump(void)
 {
@@ -1983,3 +1864,287 @@ rb_ractor_stderr_set(VALUE err)
         RB_OBJ_WRITE(cr->self, &cr->r_stderr, err);
     }
 }
+
+/// traverse function
+
+// 2: stop search
+// 1: skip child
+// 0: continue
+typedef int (*rb_obj_traverse_enter_func)(VALUE obj, void *data);
+typedef int (*rb_obj_traverse_leave_func)(VALUE obj, void *data);
+
+struct obj_traverse_data {
+    rb_obj_traverse_enter_func enter_func;
+    rb_obj_traverse_leave_func leave_func;
+    void *data;
+
+    st_table *rec;
+};
+
+
+struct obj_traverse_callback_data {
+    bool stop;
+    struct obj_traverse_data *data;
+};
+
+static int rb_obj_traverse_i(VALUE obj, struct obj_traverse_data *data);
+
+static int
+obj_hash_traverse_i(VALUE key, VALUE val, VALUE ptr)
+{
+    struct obj_traverse_callback_data *d = (struct obj_traverse_callback_data *)ptr;
+
+    if (rb_obj_traverse_i(key, d->data)) {
+        d->stop = true;
+        return ST_STOP;
+    }
+
+    if (rb_obj_traverse_i(val, d->data)) {
+        d->stop = true;
+        return ST_STOP;
+    }
+
+    return ST_CONTINUE;
+}
+
+static void
+obj_tdata_traverse_i(VALUE obj, void *ptr)
+{
+    struct obj_traverse_callback_data *d = (struct obj_traverse_callback_data *)ptr;
+
+    if (rb_obj_traverse_i(obj, d->data)) {
+        d->stop = true;
+    }
+}
+
+static int
+rb_obj_traverse_i(VALUE obj, struct obj_traverse_data *data)
+{
+    if (RB_SPECIAL_CONST_P(obj)) return 0;
+
+    switch (data->enter_func(obj, data->data)) {
+      case 0: break;
+      case 1: return 0; // skip children
+      case 2: return 1; // stop search
+      default: rb_bug("rb_obj_traverse_func should return 0 to 2");
+    }
+
+    if (st_insert(data->rec, obj, 1)) {
+        // already traversed
+        return 0;
+    }
+
+    if (FL_TEST(obj, FL_EXIVAR)) {
+        struct gen_ivtbl *ivtbl;
+        rb_ivar_generic_ivtbl_lookup(obj, &ivtbl);
+        for (uint32_t i = 0; i < ivtbl->numiv; i++) {
+            VALUE val = ivtbl->ivptr[i];
+            if (val != Qundef && rb_obj_traverse_i(val, data)) return 1;
+        }
+    }
+
+    switch (BUILTIN_TYPE(obj)) {
+      // no child node
+      case T_STRING:
+      case T_FLOAT:
+      case T_BIGNUM:
+      case T_REGEXP:
+      case T_FILE:
+      case T_SYMBOL:
+      case T_MATCH:
+        break;
+
+      case T_OBJECT:
+        {
+            uint32_t len = ROBJECT_NUMIV(obj);
+            VALUE *ptr = ROBJECT_IVPTR(obj);
+
+            for (uint32_t i=0; i<len; i++) {
+                VALUE val = ptr[i];
+                if (val != Qundef && rb_obj_traverse_i(val, data)) return 1;
+            }
+        }
+        break;
+
+      case T_ARRAY:
+        {
+            for (int i = 0; i < RARRAY_LENINT(obj); i++) {
+                VALUE e = rb_ary_entry(obj, i);
+                if (rb_obj_traverse_i(e, data)) return 1;
+            }
+        }
+        break;
+
+      case T_HASH:
+        {
+            if (rb_obj_traverse_i(RHASH_IFNONE(obj), data)) return 1;
+
+            struct obj_traverse_callback_data d = {
+                .stop = false,
+                .data = data,
+            };
+            rb_hash_foreach(obj, obj_hash_traverse_i, (VALUE)&d);
+            if (d.stop) return 1;
+        }
+        break;
+
+      case T_STRUCT:
+        {
+            long len = RSTRUCT_LEN(obj);
+            const VALUE *ptr = RSTRUCT_CONST_PTR(obj);
+
+            for (long i=0; i<len; i++) {
+                if (rb_obj_traverse_i(ptr[i], data)) return 1;
+            }
+        }
+        break;
+
+      case T_RATIONAL:
+        if (rb_obj_traverse_i(RRATIONAL(obj)->num, data)) return 1;
+        if (rb_obj_traverse_i(RRATIONAL(obj)->den, data)) return 1;
+        break;
+      case T_COMPLEX:
+        if (rb_obj_traverse_i(RCOMPLEX(obj)->real, data)) return 1;
+        if (rb_obj_traverse_i(RCOMPLEX(obj)->imag, data)) return 1;
+        break;
+
+      case T_DATA:
+        {
+            struct obj_traverse_callback_data d = {
+                .stop = false,
+                .data = data,
+            };
+            rb_objspace_reachable_objects_from(obj, obj_tdata_traverse_i, &d);
+            if (d.stop) return 1;
+        }
+        break;
+
+      // unreachable
+      case T_CLASS:
+      case T_MODULE:
+      case T_ICLASS:
+      default:
+        rp(obj);
+        rb_bug("unreachable");
+    }
+
+    switch (data->leave_func(obj, data->data)) {
+      case 0:
+      case 1: return 0; // terminate
+      case 2: return 1; // stop search
+      default: rb_bug("rb_obj_traverse_func should return 0 to 2");
+    }
+}
+
+// 0: traverse all
+// 1: stopped
+static int
+rb_obj_traverse(VALUE obj,
+                rb_obj_traverse_enter_func enter_func,
+                rb_obj_traverse_leave_func leave_func,
+                void *passed_data)
+{
+    VALUE h = rb_ident_hash_new();
+
+    struct obj_traverse_data data = {
+        .enter_func = enter_func,
+        .leave_func = leave_func,
+        .data = passed_data,
+        .rec = rb_hash_st_table(h),
+    };
+
+    int r = rb_obj_traverse_i(obj, &data);
+    RB_GC_GUARD(h);
+    return r;
+}
+
+static int
+frozen_shareable_p(VALUE obj)
+{
+    switch (BUILTIN_TYPE(obj)) {
+      case T_DATA:
+        if (RTYPEDDATA_P(obj)) {
+            const rb_data_type_t *type = RTYPEDDATA_TYPE(obj);
+            if (type->flags & RUBY_TYPED_FROZEN_SHAREABLE) {
+                return true;
+            }
+        }
+        return false;
+      default:
+        return true;
+    }
+}
+
+static int
+make_shareable_check_shareable(VALUE obj, void *data)
+{
+    VM_ASSERT(!SPECIAL_CONST_P(obj));
+
+    if (RB_OBJ_SHAREABLE_P(obj)) {
+        return 1;
+    }
+    else {
+        if (!frozen_shareable_p(obj)) {
+            rb_raise(rb_eRactorError, "can not make shareable object for %"PRIsVALUE, obj);
+        }
+    }
+
+    if (!OBJ_FROZEN(obj)) {
+        rb_funcall(obj, idFreeze, 0);
+    }
+    return 0;
+}
+
+static int
+mark_shareable(VALUE obj, void *data)
+{
+    FL_SET_RAW(obj, RUBY_FL_SHAREABLE);
+    return 0;
+}
+
+VALUE
+rb_ractor_make_shareable(VALUE obj)
+{
+    rb_obj_traverse(obj,
+                    make_shareable_check_shareable,
+                    mark_shareable,
+                    NULL);
+    return obj;
+}
+
+static int
+shareable_p_enter(VALUE obj, void *ptr)
+{
+    if (RB_OBJ_SHAREABLE_P(obj)) {
+        return 1;
+    }
+    else if (RB_TYPE_P(obj, T_CLASS)  ||
+             RB_TYPE_P(obj, T_MODULE) ||
+             RB_TYPE_P(obj, T_ICLASS)) {
+        // TODO: remove it
+        mark_shareable(obj, NULL);
+        return 1;
+    }
+    else if (RB_OBJ_FROZEN_RAW(obj) &&
+             frozen_shareable_p(obj)) {
+        return 0;
+    }
+
+    return 2; // fail
+}
+
+MJIT_FUNC_EXPORTED bool
+rb_ractor_shareable_p_continue(VALUE obj)
+{
+    if (rb_obj_traverse(obj,
+                        shareable_p_enter,
+                        mark_shareable,
+                        NULL)) {
+        return false;
+    }
+    else {
+        return true;
+    }
+}
+
+#include "ractor.rbinc"
diff --git a/ractor.rb b/ractor.rb
index c825fbe0da..936310d645 100644
--- a/ractor.rb
+++ b/ractor.rb
@@ -173,4 +173,10 @@ class Ractor
       rb_ractor_shareable_p(obj) ? Qtrue : Qfalse;
     }
   end
+
+  def self.make_shareable obj
+    __builtin_cexpr! %q{
+      rb_ractor_make_shareable(obj);
+    }
+  end
 end
diff --git a/ractor_pub.h b/ractor_pub.h
index 5347481429..f2869276f6 100644
--- a/ractor_pub.h
+++ b/ractor_pub.h
@@ -36,6 +36,8 @@ rb_ractor_shareable_p(VALUE obj)
     }
 }
 
+VALUE rb_ractor_make_shareable(VALUE obj);
+
 RUBY_SYMBOL_EXPORT_BEGIN
 
 VALUE rb_ractor_stdin(void);