ruby · casperisfine · Jun 12, 2025 · Jun 12, 2025 · Jun 12, 2025
diff --git a/gc.c b/gc.c
@@ -1781,14 +1781,6 @@ generate_next_object_id(void)
 #endif
 }
 
-void
-rb_gc_obj_id_moved(VALUE obj)
-{
-    if (UNLIKELY(id2ref_tbl)) {
-        st_insert(id2ref_tbl, (st_data_t)rb_obj_id(obj), (st_data_t)obj);
-    }
-}
-
 static int
 object_id_cmp(st_data_t x, st_data_t y)
 {
@@ -1853,6 +1845,109 @@ static const rb_data_type_t id2ref_tbl_type = {
 
 #define RUBY_ATOMIC_VALUE_LOAD(x) (VALUE)(RUBY_ATOMIC_PTR_LOAD(x))
 
+static VALUE obj_to_id_value = 0;
+static st_table *obj_to_id_tbl = NULL;
+
+static void mark_hash_values(st_table *tbl);
+
+static void
+obj_to_id_tbl_mark(void *data)
+{
+    st_table *table = (st_table *)data;
+    if (UNLIKELY(!RB_POSFIXABLE(LAST_OBJECT_ID()))) {
+        // It's very unlikely, but if enough object ids were generated, keys may be T_BIGNUM
+        mark_hash_values(table);
+    }
+    // We purposedly don't mark keys, as they are weak references.
+    // rb_gc_obj_free_vm_weak_references takes care of cleaning them up.
+}
+
+static size_t
+obj_to_id_tbl_memsize(const void *data)
+{
+    return rb_st_memsize(data);
+}
+
+static void
+obj_to_id_tbl_free(void *data)
+{
+    if (obj_to_id_tbl) {
+        st_free_table(obj_to_id_tbl);
+        obj_to_id_tbl = NULL; // clear global ref
+    }
+}
+
+struct obj_to_id_tbl_any_moved_p_args {
+    bool need_rebuild;
+};
+
+static int
+obj_to_id_tbl_any_moved_p_i(st_data_t key, st_data_t value, st_data_t data)
+{
+    struct obj_to_id_tbl_any_moved_p_args *args = (struct obj_to_id_tbl_any_moved_p_args *)data;
+
+    if (rb_gc_location(key) != key || (!FIXNUM_P(value) && rb_gc_location(value) != value)) {
+        args->need_rebuild = true;
+        return ST_STOP;
+    }
+    return ST_CONTINUE;
+}
+
+static int
+obj_to_id_rebuild_table_i(st_data_t key, st_data_t value, st_data_t data)
+{
+    st_table *new_table = (st_table *)data;
+    st_insert(new_table, rb_gc_location(key), rb_gc_location(value));
+    return ST_CONTINUE;
+}
+
+static void
+obj_to_id_tbl_compact(void *data)
+{
+    if (obj_to_id_tbl) {
+        struct obj_to_id_tbl_any_moved_p_args any_moved_args = { 0 };
+        st_foreach(obj_to_id_tbl, obj_to_id_tbl_any_moved_p_i, (st_data_t)&any_moved_args);
+
+        if (any_moved_args.need_rebuild) {
+            fprintf(stderr, "-- rebyild---\n");
+            st_table *new_table;
+            DURING_GC_COULD_MALLOC_REGION_START();
+            {
+                new_table = st_init_numtable_with_size(st_table_size(obj_to_id_tbl));
+            }
+            DURING_GC_COULD_MALLOC_REGION_END();
+            st_foreach(obj_to_id_tbl, obj_to_id_rebuild_table_i, (st_data_t)new_table);
+            st_free_table(obj_to_id_tbl);
+            obj_to_id_tbl = new_table;
+        }
+    }
+}
+
+void
+rb_gc_obj_id_moved(VALUE old_obj, VALUE obj)
+{
+    if (UNLIKELY(id2ref_tbl)) {
+        st_insert(id2ref_tbl, (st_data_t)rb_obj_id(obj), (st_data_t)obj);
+    }
+
+    if (rb_shape_obj_has_id(obj) == SHAPE_ID_FL_OBJ_ID_EXTERNAL) {
+        VALUE object_id;
+        st_delete(obj_to_id_tbl, &old_obj, &object_id);
+        st_insert(obj_to_id_tbl, obj, object_id);
+    }
+}
+
+static const rb_data_type_t obj_to_id_tbl_type = {
+    .wrap_struct_name = "VM/obj_to_id_table",
+    .function = {
+        .dmark = obj_to_id_tbl_mark,
+        .dfree = obj_to_id_tbl_free,
+        .dsize = obj_to_id_tbl_memsize,
+        .dcompact = obj_to_id_tbl_compact,
+    },
+    .flags = RUBY_TYPED_WB_PROTECTED | RUBY_TYPED_FREE_IMMEDIATELY
+};
+
 static VALUE
 class_object_id(VALUE klass)
 {
@@ -1875,13 +1970,19 @@ class_object_id(VALUE klass)
 static inline VALUE
 object_id_get(VALUE obj, shape_id_t shape_id)
 {
-    VALUE id;
-    if (rb_shape_too_complex_p(shape_id)) {
-        id = rb_obj_field_get(obj, ROOT_TOO_COMPLEX_WITH_OBJ_ID);
-    }
-    else {
-        id = rb_obj_field_get(obj, rb_shape_object_id(shape_id));
-    }
+    VALUE id = Qundef;
+
+    switch (rb_shape_has_object_id(shape_id)) {
+      case SHAPE_NO_OBJ_ID:
+        rb_bug("Unreacheable");
+        break;
+      case SHAPE_INLINE_OBJ_ID:
+        if (rb_shape_too_complex_p(shape_id)) {
+            id = rb_obj_field_get(obj, ROOT_TOO_COMPLEX_WITH_OBJ_ID);
+        }
+        else {
+            id = rb_obj_field_get(obj, rb_shape_object_id_inline(shape_id));
+        }
 
 #if RUBY_DEBUG
     if (!(FIXNUM_P(id) || RB_TYPE_P(id, T_BIGNUM))) {
@@ -1890,11 +1991,31 @@ object_id_get(VALUE obj, shape_id_t shape_id)
     }
 #endif
 
+        break;
+      case SHAPE_EXTERNAL_OBJ_ID:
+        {
+            RUBY_ASSERT(obj_to_id_tbl);
+            unsigned int lock_lev = RB_GC_VM_LOCK();
+            fprintf(stderr, "lookup %"PRIxVALUE"\n", obj);
+            st_lookup(obj_to_id_tbl, obj, &id);
+
+#if RUBY_DEBUG
+    if (!(FIXNUM_P(id) || RB_TYPE_P(id, T_BIGNUM))) {
+        rb_p(obj);
+        rb_bug("Object %s/%"PRIxVALUE" shape includes external object_id, but it's missing in obj_to_id_tbl", rb_obj_info(obj), obj);
+    }
+#endif
+
+            RB_GC_VM_UNLOCK(lock_lev);
+        }
+        break;
+    }
+
     return id;
 }
 
 static VALUE
-object_id0(VALUE obj)
+object_id0(VALUE obj, bool shareable)
 {
     VALUE id = Qfalse;
     shape_id_t shape_id = RBASIC_SHAPE_ID(obj);
@@ -1903,14 +2024,30 @@ object_id0(VALUE obj)
         return object_id_get(obj, shape_id);
     }
 
-    // rb_shape_object_id_shape may lock if the current shape has
-    // multiple children.
-    shape_id_t object_id_shape_id = rb_shape_transition_object_id(obj);
-
     id = generate_next_object_id();
-    rb_obj_field_set(obj, object_id_shape_id, id);
 
-    RUBY_ASSERT(RBASIC_SHAPE_ID(obj) == object_id_shape_id);
+    attr_index_t capacity = RSHAPE_CAPACITY(shape_id);
+    attr_index_t free_capacity = capacity - RSHAPE_LEN(shape_id);
+    if (shareable && RB_TYPE_P(obj, T_OBJECT) && capacity && !free_capacity) {
+        // If the object was shared and has no free capacity, we can't safely store the object_id inline, as it
+        // would require to move the object content into an external buffer.
+        // This is only a problem for T_OBJECT, given other types have external fields and can do RCU.
+        shape_id_t next_shape_id = rb_shape_transition_object_id_external(obj);
+        if (RB_UNLIKELY(!obj_to_id_tbl)) {
+            obj_to_id_tbl = st_init_numtable();
+            obj_to_id_value = TypedData_Wrap_Struct(0, &obj_to_id_tbl_type, obj_to_id_tbl);
+        }
+        fprintf(stderr, "insert %"PRIxVALUE"\n", obj);
+        // This can trigger compaction, which may rebuild the table and then crash....
+        st_insert(obj_to_id_tbl, obj, id);
+        fprintf(stderr, "inserted\n");
+        RBASIC_SET_SHAPE_ID(obj, next_shape_id);
+    }
+    else {
+        shape_id_t next_shape_id = rb_shape_transition_object_id_inline(obj);
+        rb_obj_field_set(obj, next_shape_id, id);
+    }
+
     RUBY_ASSERT(rb_shape_obj_has_id(obj));
 
     if (RB_UNLIKELY(id2ref_tbl)) {
@@ -1936,14 +2073,14 @@ object_id(VALUE obj)
         break;
     }
 
-    if (UNLIKELY(rb_gc_multi_ractor_p() && rb_ractor_shareable_p(obj))) {
+    if (UNLIKELY(rb_gc_multi_ractor_p() && RB_OBJ_SHAREABLE_P(obj))) {
         unsigned int lock_lev = RB_GC_VM_LOCK();
-        VALUE id = object_id0(obj);
+        VALUE id = object_id0(obj, true);
         RB_GC_VM_UNLOCK(lock_lev);
         return id;
     }
 
-    return object_id0(obj);
+    return object_id0(obj, false);
 }
 
 static void
@@ -2045,8 +2182,18 @@ obj_free_object_id(VALUE obj)
             break;
           default: {
             shape_id_t shape_id = RBASIC_SHAPE_ID(obj);
-            if (rb_shape_has_object_id(shape_id)) {
+            switch (rb_shape_has_object_id(shape_id)) {
+              case SHAPE_NO_OBJ_ID:
+                break;
+              case SHAPE_INLINE_OBJ_ID:
                 obj_id = object_id_get(obj, shape_id);
+                break;
+              case SHAPE_EXTERNAL_OBJ_ID:
+                // During shutdown the `obj_to_id_tbl` may be freed first.
+                if (obj_to_id_tbl) {
+                    st_delete(obj_to_id_tbl, &obj, &obj_id);
+                }
+                break;
             }
             break;
           }
@@ -2739,6 +2886,22 @@ rb_mark_set(st_table *tbl)
     st_foreach(tbl, mark_key, (st_data_t)rb_gc_get_objspace());
 }
 
+static int
+mark_value(st_data_t key, st_data_t value, st_data_t data)
+{
+    gc_mark_internal((VALUE)value);
+
+    return ST_CONTINUE;
+}
+
+static void
+mark_hash_values(st_table *tbl)
+{
+    if (!tbl) return;
+
+    st_foreach(tbl, mark_value, 0);
+}

 static int
 mark_keyvalue(st_data_t key, st_data_t value, st_data_t data)
 {
@@ -5543,6 +5706,7 @@ Init_GC(void)
 {
 #undef rb_intern
     rb_gc_register_address(&id2ref_value);
+    rb_gc_register_address(&obj_to_id_value);
 
     malloc_offset = gc_compute_malloc_offset();
 

diff --git a/internal/gc.h b/internal/gc.h
@@ -201,7 +201,7 @@ RUBY_ATTR_MALLOC void *rb_xcalloc_mul_add_mul(size_t, size_t, size_t, size_t);
 static inline void *ruby_sized_xrealloc_inlined(void *ptr, size_t new_size, size_t old_size) RUBY_ATTR_RETURNS_NONNULL RUBY_ATTR_ALLOC_SIZE((2));
 static inline void *ruby_sized_xrealloc2_inlined(void *ptr, size_t new_count, size_t elemsiz, size_t old_count) RUBY_ATTR_RETURNS_NONNULL RUBY_ATTR_ALLOC_SIZE((2, 3));
 static inline void ruby_sized_xfree_inlined(void *ptr, size_t size);
-void rb_gc_obj_id_moved(VALUE obj);
+void rb_gc_obj_id_moved(VALUE old_obj, VALUE obj);
 
 void *rb_gc_ractor_cache_alloc(rb_ractor_t *ractor);
 void rb_gc_ractor_cache_free(void *cache);

diff --git a/ractor.c b/ractor.c
@@ -1866,7 +1866,7 @@ move_leave(VALUE obj, struct obj_traverse_replace_data *data)
 
     void rb_replace_generic_ivar(VALUE clone, VALUE obj); // variable.c
 
-    rb_gc_obj_id_moved(data->replacement);
+    rb_gc_obj_id_moved(obj, data->replacement);
 
     if (UNLIKELY(FL_TEST_RAW(obj, FL_EXIVAR))) {
         rb_replace_generic_ivar(data->replacement, obj);

diff --git a/shape.c b/shape.c
@@ -709,7 +709,7 @@ remove_shape_recursive(rb_shape_t *shape, ID id, rb_shape_t **removed_shape)
 static inline shape_id_t transition_complex(shape_id_t shape_id);
 
 static shape_id_t
-shape_transition_object_id(shape_id_t original_shape_id)
+shape_transition_object_id_inline(shape_id_t original_shape_id)
 {
     RUBY_ASSERT(!rb_shape_has_object_id(original_shape_id));
 
@@ -720,17 +720,25 @@ shape_transition_object_id(shape_id_t original_shape_id)
     }
 
     RUBY_ASSERT(shape);
-    return shape_id(shape, original_shape_id) | SHAPE_ID_FL_HAS_OBJECT_ID;
+    return shape_id(shape, original_shape_id) | SHAPE_ID_FL_OBJ_ID_INLINE;
 }
 
 shape_id_t
-rb_shape_transition_object_id(VALUE obj)
+rb_shape_transition_object_id_inline(VALUE obj)
 {
-    return shape_transition_object_id(RBASIC_SHAPE_ID(obj));
+    return shape_transition_object_id_inline(RBASIC_SHAPE_ID(obj));
 }
 
 shape_id_t
-rb_shape_object_id(shape_id_t original_shape_id)
+rb_shape_transition_object_id_external(VALUE obj)
+{
+    shape_id_t original_shape_id = RBASIC_SHAPE_ID(obj);
+    RUBY_ASSERT(!rb_shape_has_object_id(original_shape_id));
+    return original_shape_id | SHAPE_ID_FL_OBJ_ID_EXTERNAL;
+}
+
+shape_id_t
+rb_shape_object_id_inline(shape_id_t original_shape_id)
 {
     RUBY_ASSERT(rb_shape_has_object_id(original_shape_id));
 
@@ -742,7 +750,7 @@ rb_shape_object_id(shape_id_t original_shape_id)
         shape = RSHAPE(shape->parent_id);
     }
 
-    return shape_id(shape, original_shape_id) | SHAPE_ID_FL_HAS_OBJECT_ID;
+    return shape_id(shape, original_shape_id) | SHAPE_ID_FL_OBJ_ID_INLINE;
 }
 
 static inline shape_id_t
@@ -754,7 +762,7 @@ transition_complex(shape_id_t shape_id)
     if (heap_index) {
         next_shape_id = rb_shape_root(heap_index - 1) | SHAPE_ID_FL_TOO_COMPLEX;
         if (rb_shape_has_object_id(shape_id)) {
-            next_shape_id = shape_transition_object_id(next_shape_id);
+            next_shape_id = shape_transition_object_id_inline(next_shape_id);
         }
     }
     else {
@@ -1104,7 +1112,7 @@ rb_shape_rebuild(shape_id_t initial_shape_id, shape_id_t dest_shape_id)
         return shape_id(next_shape, initial_shape_id);
     }
     else {
-        return transition_complex(initial_shape_id | (dest_shape_id & SHAPE_ID_FL_HAS_OBJECT_ID));
+        return transition_complex(initial_shape_id | (dest_shape_id & SHAPE_ID_FL_OBJ_ID_INLINE));
     }
 }
 
@@ -1223,7 +1231,7 @@ rb_shape_verify_consistency(VALUE obj, shape_id_t shape_id)
         shape = RSHAPE(shape->parent_id);
     }
 
-    if (rb_shape_has_object_id(shape_id)) {
+    if (rb_shape_has_object_id(shape_id) == SHAPE_INLINE_OBJ_ID) {
         if (!has_object_id) {
             rb_p(obj);
             rb_bug("shape_id claim having obj_id but doesn't shape_id=%u, obj=%s", shape_id, rb_obj_info(obj));