Simplify subclasses list, remove from Box

Currently we maintain the subclasses list for two separate purposes (we essentially have to different relationships we're putting into the same list):

1. On a T_MODULE, we track the T_ICLASSes created to include it into
   other classes. Used for method invalidation and propagating includes
   on the module that happen after it's been used
2. On a T_CLASS/T_ICLASS, we track the T_CLASS/T_ICLASS which are the
   immediate children of the class. We use this for method invalidation,
   some cvar things, and to iterate through subclasses.

Purpose 1 does not have any issues with box, the T_ICLASS always belongs
to one specific module and that's immutable. This list can be box-global
(always use the prime classext or hoist it out) and only needs to be
pruned during free. If we care about behaviour under a particular box
(ie. the propagating includes), we should look up the current box being
modified on the ICLASS itself.

Purpose 2 is more complicated. It currently tracks the immediate
children, the T_CLASS or T_ICLASS whose super points back. Because super
is per-box and is mutable (include/prepend insert ICLASSes into the
chain) we need to update the list on include/prepend, entries must be
per-box, and we can have multiple entries per-box. *I propose we
simplify this by no longer tracking the immediate subclass*, but instead
tracking the T_CLASS -> ... -> T_CLASS relationship, ie. the inverse of
rb_class_superclass. That relationship is the same across all boxes and
immutable after Class creation.

As a special case the ICLASS for refinements are also added to the
purpose 2 list (on T_CLASS). As those ICLASS do not chain to an eventual
leaf T_CLASS.

When we need to find the classes which have included a module, we can
use the module subclasses list to find the ICLASS and then use
RCLASS_INCLUDER. If we needed to iterate all T_ICLASS, we could then
walk up the CLASS_SUPER chain, but I didn't find anywhere we needed to
do that.

7 files changed, 178 insertions, 292 deletions

diff --git a/class.c b/class.c
index 9c1bd86dc3..9b29f000b4 100644
--- a/class.c
+++ b/class.c
@@ -80,6 +80,10 @@
 #define METACLASS_OF(k) RBASIC(k)->klass
 #define SET_METACLASS_OF(k, cls) RBASIC_SET_CLASS(k, cls)
 
+static void rb_class_remove_from_super_subclasses(VALUE klass);
+static void rb_class_remove_from_module_subclasses(VALUE klass);
+static void rb_class_classext_free_subclasses(rb_classext_t *ext);
+
 static enum rb_id_table_iterator_result
 cvar_table_free_i(VALUE value, void *ctx)
 {
@@ -114,7 +118,10 @@ rb_class_classext_free(VALUE klass, rb_classext_t *ext, bool is_prime)
         rb_id_table_free(tbl);
     }
 
-    rb_class_classext_free_subclasses(ext, klass, false);
+    if (is_prime) {
+        rb_class_remove_from_super_subclasses(klass);
+        rb_class_classext_free_subclasses(ext);
+    }
 
     if (RCLASSEXT_SUPERCLASSES_WITH_SELF(ext)) {
         RUBY_ASSERT(is_prime); // superclasses should only be used on prime
@@ -138,7 +145,10 @@ rb_iclass_classext_free(VALUE klass, rb_classext_t *ext, bool is_prime)
         rb_id_table_free(RCLASSEXT_CALLABLE_M_TBL(ext));
     }
 
-    rb_class_classext_free_subclasses(ext, klass, false);
+    if (is_prime) {
+        rb_class_remove_from_super_subclasses(klass);
+        rb_class_remove_from_module_subclasses(klass);
+    }
 
     if (!is_prime) { // the prime classext will be freed with RClass
         xfree(ext);
@@ -157,8 +167,6 @@ iclass_free_orphan_classext(VALUE klass, rb_classext_t *ext)
         rb_id_table_free(RCLASSEXT_CALLABLE_M_TBL(ext));
     }
 
-    rb_class_classext_free_subclasses(ext, klass, true); // replacing this classext with a newer one
-
     xfree(ext);
 }
 
@@ -309,66 +317,6 @@ duplicate_classext_const_tbl(struct rb_id_table *src, VALUE klass)
     return dst;
 }
 
-static VALUE
-box_subclasses_tbl_key(const rb_box_t *box)
-{
-    if (!box){
-        return 0;
-    }
-    return (VALUE)box->box_id;
-}
-
-static void
-duplicate_classext_subclasses(rb_classext_t *orig, rb_classext_t *copy)
-{
-    rb_subclass_anchor_t *anchor, *orig_anchor;
-    rb_subclass_entry_t *head, *cur, *cdr, *entry, *first = NULL;
-    rb_box_subclasses_t *box_subclasses;
-    struct st_table *tbl;
-
-    if (RCLASSEXT_SUBCLASSES(orig)) {
-        orig_anchor = RCLASSEXT_SUBCLASSES(orig);
-        box_subclasses = orig_anchor->box_subclasses;
-        tbl = ((rb_box_subclasses_t *)box_subclasses)->tbl;
-
-        anchor = ZALLOC(rb_subclass_anchor_t);
-        anchor->box_subclasses = rb_box_subclasses_ref_inc(box_subclasses);
-
-        head = ZALLOC(rb_subclass_entry_t);
-        anchor->head = head;
-
-        RCLASSEXT_SUBCLASSES(copy) = anchor;
-
-        cur = head;
-        entry = orig_anchor->head;
-        RUBY_ASSERT(!entry->klass);
-        // The head entry has NULL klass always. See rb_class_foreach_subclass().
-        entry = entry->next;
-        while (entry) {
-            if (rb_objspace_garbage_object_p(entry->klass)) {
-                entry = entry->next;
-                continue;
-            }
-            cdr = ZALLOC(rb_subclass_entry_t);
-            cdr->klass = entry->klass;
-            cdr->prev = cur;
-            cur->next = cdr;
-            if (!first) {
-                VALUE box_id = box_subclasses_tbl_key(RCLASSEXT_BOX(copy));
-                first = cdr;
-                st_insert(tbl, box_id, (st_data_t)first);
-            }
-            cur = cdr;
-            entry = entry->next;
-        }
-    }
-
-    if (RCLASSEXT_BOX_SUPER_SUBCLASSES(orig))
-        RCLASSEXT_BOX_SUPER_SUBCLASSES(copy) = rb_box_subclasses_ref_inc(RCLASSEXT_BOX_SUPER_SUBCLASSES(orig));
-    if (RCLASSEXT_BOX_MODULE_SUBCLASSES(orig))
-        RCLASSEXT_BOX_MODULE_SUBCLASSES(copy) = rb_box_subclasses_ref_inc(RCLASSEXT_BOX_MODULE_SUBCLASSES(orig));
-}
-
 static void
 class_duplicate_iclass_classext(VALUE iclass, rb_classext_t *mod_ext, const rb_box_t *box)
 {
@@ -404,8 +352,7 @@ class_duplicate_iclass_classext(VALUE iclass, rb_classext_t *mod_ext, const rb_b
     // RCLASSEXT_CALLABLE_M_TBL(ext) = NULL;
     // RCLASSEXT_CC_TBL(ext) = NULL;
 
-    // subclasses, box_super_subclasses_tbl, box_module_subclasses_tbl
-    duplicate_classext_subclasses(src, ext);
+    // Subclasses/back-pointers are only in the prime classext.
 
     RCLASSEXT_SET_ORIGIN(ext, iclass, RCLASSEXT_ORIGIN(src));
     RCLASSEXT_ICLASS_IS_ORIGIN(ext) = RCLASSEXT_ICLASS_IS_ORIGIN(src);
@@ -461,8 +408,7 @@ rb_class_duplicate_classext(rb_classext_t *orig, VALUE klass, const rb_box_t *bo
 
     RCLASSEXT_CVC_TBL(ext) = duplicate_classext_id_table(RCLASSEXT_CVC_TBL(orig), dup_iclass);
 
-    // subclasses, subclasses_index
-    duplicate_classext_subclasses(orig, ext);
+    // Subclasses/back-pointers are only in the prime classext.
 
     RCLASSEXT_SET_ORIGIN(ext, klass, RCLASSEXT_ORIGIN(orig));
     /*
@@ -480,24 +426,28 @@ rb_class_duplicate_classext(rb_classext_t *orig, VALUE klass, const rb_box_t *bo
     /* For the usual T_CLASS/T_MODULE, iclass flags are always false */
 
     if (dup_iclass) {
-        VALUE iclass;
         /*
          * ICLASS has the same m_tbl/const_tbl/cvc_tbl with the included module.
          * So the module's classext is copied, its tables should be also referred
          * by the ICLASS's classext for the box.
+         *
+         * Subclasses are only in the prime classext, so read from orig.
          */
-        rb_subclass_anchor_t *anchor = RCLASSEXT_SUBCLASSES(ext);
-        rb_subclass_entry_t *subclass_entry = anchor->head;
+        rb_subclass_entry_t *subclass_entry = RCLASSEXT_SUBCLASSES(orig);
+        if (subclass_entry) subclass_entry = subclass_entry->next; // skip dummy head
         while (subclass_entry) {
-            if (subclass_entry->klass && RB_TYPE_P(subclass_entry->klass, T_ICLASS)) {
-                iclass = subclass_entry->klass;
-                VM_ASSERT(RB_TYPE_P(iclass, T_ICLASS));
-                if (RBASIC_CLASS(iclass) == klass) {
-                    // Is the subclass an ICLASS including this module into another class
-                    // If so we need to re-associate it under our box with the new ext
-                    VM_ASSERT(FL_TEST_RAW(iclass, RCLASS_BOXABLE));
-                    class_duplicate_iclass_classext(iclass, ext, box);
-                }
+            VALUE iclass = subclass_entry->klass;
+
+            /* every node in the subclass list should be an ICLASS built from this module */
+            VM_ASSERT(iclass);
+            VM_ASSERT(RB_TYPE_P(iclass, T_ICLASS));
+            VM_ASSERT(RBASIC_CLASS(iclass) == klass);
+
+            if (FL_TEST_RAW(iclass, RCLASS_BOXABLE)) {
+                // Non-boxable ICLASSes (included by classes in main/user boxes) can't
+                // hold per-box classexts, and their includer classes also can't, so
+                // method lookup through them always uses the prime classext.
+                class_duplicate_iclass_classext(iclass, ext, box);
             }
             subclass_entry = subclass_entry->next;
         }
@@ -558,49 +508,46 @@ rb_class_variation_count(VALUE klass)
     return RCLASS_VARIATION_COUNT(klass);
 }
 
-static void
-push_subclass_entry_to_list(VALUE super, VALUE klass, bool is_module)
+static rb_subclass_entry_t *
+push_subclass_entry_to_list(VALUE super, VALUE klass)
 {
     rb_subclass_entry_t *entry, *head;
-    rb_subclass_anchor_t *anchor;
-    rb_box_subclasses_t *box_subclasses;
-    struct st_table *tbl;
-    const rb_box_t *box = rb_current_box();
+
+    RUBY_ASSERT(
+            (RB_TYPE_P(super, T_MODULE) && RB_TYPE_P(klass, T_ICLASS)) ||
+            (RB_TYPE_P(super, T_CLASS) && RB_TYPE_P(klass, T_CLASS)) ||
+            (RB_TYPE_P(klass, T_ICLASS) && !NIL_P(RCLASS_REFINED_CLASS(klass)))
+            );
 
     entry = ZALLOC(rb_subclass_entry_t);
     entry->klass = klass;
 
     RB_VM_LOCKING() {
-        anchor = RCLASS_WRITABLE_SUBCLASSES(super);
-        VM_ASSERT(anchor);
-        box_subclasses = (rb_box_subclasses_t *)anchor->box_subclasses;
-        VM_ASSERT(box_subclasses);
-        tbl = box_subclasses->tbl;
-        VM_ASSERT(tbl);
-
-        head = anchor->head;
+        head = RCLASS_WRITABLE_SUBCLASSES(super);
+        if (!head) {
+            head = ZALLOC(rb_subclass_entry_t);
+            RCLASS_SET_SUBCLASSES(super, head);
+        }
+        entry->next = head->next;
+        entry->prev = head;
+
         if (head->next) {
             head->next->prev = entry;
-            entry->next = head->next;
         }
         head->next = entry;
-        entry->prev = head;
-        st_insert(tbl, box_subclasses_tbl_key(box), (st_data_t)entry);
     }
 
-    if (is_module) {
-        RCLASS_WRITE_BOX_MODULE_SUBCLASSES(klass, anchor->box_subclasses);
-    }
-    else {
-        RCLASS_WRITE_BOX_SUPER_SUBCLASSES(klass, anchor->box_subclasses);
-    }
+    return entry;
 }
 
 void
 rb_class_subclass_add(VALUE super, VALUE klass)
 {
     if (super && !UNDEF_P(super)) {
-        push_subclass_entry_to_list(super, klass, false);
+        RUBY_ASSERT(RB_TYPE_P(super, T_CLASS) || RB_TYPE_P(super, T_MODULE));
+        RUBY_ASSERT(RB_TYPE_P(klass, T_CLASS) || RB_TYPE_P(klass, T_ICLASS));
+        rb_subclass_entry_t *entry = push_subclass_entry_to_list(super, klass);
+        RCLASS_EXT_PRIME(klass)->subclass_entry = entry;
     }
 }
 
@@ -608,105 +555,81 @@ static void
 rb_module_add_to_subclasses_list(VALUE module, VALUE iclass)
 {
     if (module && !UNDEF_P(module)) {
-        push_subclass_entry_to_list(module, iclass, true);
+        RUBY_ASSERT(RB_TYPE_P(module, T_MODULE));
+        RUBY_ASSERT(RB_TYPE_P(iclass, T_ICLASS));
+        rb_subclass_entry_t *entry = push_subclass_entry_to_list(module, iclass);
+        RCLASS_EXT_PRIME(iclass)->module_subclass_entry = entry;
     }
 }
 
-static struct rb_subclass_entry *
-class_get_subclasses_for_ns(struct st_table *tbl, VALUE box_id)
+static void
+rb_subclass_entry_remove(rb_subclass_entry_t *entry)
 {
-    st_data_t value;
-    if (st_lookup(tbl, (st_data_t)box_id, &value)) {
-        return (struct rb_subclass_entry *)value;
+    if (entry) {
+        rb_subclass_entry_t *prev = entry->prev, *next = entry->next;
+
+        if (prev) {
+            prev->next = next;
+        }
+        if (next) {
+            next->prev = prev;
+        }
+
+        xfree(entry);
     }
-    return NULL;
 }
 
-static int
-remove_class_from_subclasses_replace_first_entry(st_data_t *key, st_data_t *value, st_data_t arg, int existing)
+static void
+rb_class_remove_from_super_subclasses(VALUE klass)
 {
-    *value = arg;
-    return ST_CONTINUE;
+    rb_classext_t *ext = RCLASS_EXT_PRIME(klass);
+    rb_subclass_entry_t *entry = RCLASSEXT_SUBCLASS_ENTRY(ext);
+
+    if (!entry) return;
+    rb_subclass_entry_remove(entry);
+    RCLASSEXT_SUBCLASS_ENTRY(ext) = NULL;
 }
 
 static void
-remove_class_from_subclasses(struct st_table *tbl, VALUE box_id, VALUE klass)
+rb_class_remove_from_module_subclasses(VALUE klass)
 {
-    rb_subclass_entry_t *entry = class_get_subclasses_for_ns(tbl, box_id);
-    bool first_entry = true;
-    while (entry) {
-        if (entry->klass == klass) {
-            rb_subclass_entry_t *prev = entry->prev, *next = entry->next;
+    rb_classext_t *ext = RCLASS_EXT_PRIME(klass);
+    rb_subclass_entry_t *entry = RCLASSEXT_MODULE_SUBCLASS_ENTRY(ext);
 
-            if (prev) {
-                prev->next = next;
-            }
-            if (next) {
-                next->prev = prev;
-            }
+    if (!entry) return;
+    rb_subclass_entry_remove(entry);
+    RCLASSEXT_MODULE_SUBCLASS_ENTRY(ext) = NULL;
+}
+
+static void
+rb_class_classext_free_subclasses(rb_classext_t *ext)
+{
+    rb_subclass_entry_t *head = RCLASSEXT_SUBCLASSES(ext);
 
-            if (first_entry) {
-                if (next) {
-                    st_update(tbl, box_id, remove_class_from_subclasses_replace_first_entry, (st_data_t)next);
+    if (head) {
+        // Detach all children's back-pointers before freeing the list,
+        // so they don't try to unlink from a freed entry later.
+        rb_subclass_entry_t *entry = head->next; // skip dummy head
+        while (entry) {
+            if (entry->klass) {
+                rb_classext_t *child_ext = RCLASS_EXT_PRIME(entry->klass);
+                if (RCLASSEXT_SUBCLASS_ENTRY(child_ext) == entry) {
+                    RCLASSEXT_SUBCLASS_ENTRY(child_ext) = NULL;
                 }
-                else {
-                    // no subclass entries in this ns after the deletion
-                    st_delete(tbl, &box_id, NULL);
+                if (RCLASSEXT_MODULE_SUBCLASS_ENTRY(child_ext) == entry) {
+                    RCLASSEXT_MODULE_SUBCLASS_ENTRY(child_ext) = NULL;
                 }
             }
+            entry = entry->next;
+        }
 
+        entry = head;
+        while (entry) {
+            rb_subclass_entry_t *next = entry->next;
             xfree(entry);
-
-            break;
+            entry = next;
         }
-        else if (first_entry) {
-            first_entry = false;
-        }
-        entry = entry->next;
-    }
-}
-
-void
-rb_class_remove_from_super_subclasses(VALUE klass)
-{
-    rb_classext_t *ext = RCLASS_EXT_WRITABLE(klass);
-    rb_box_subclasses_t *box_subclasses = RCLASSEXT_BOX_SUPER_SUBCLASSES(ext);
-
-    if (!box_subclasses) return;
-    remove_class_from_subclasses(box_subclasses->tbl, box_subclasses_tbl_key(RCLASSEXT_BOX(ext)), klass);
-    rb_box_subclasses_ref_dec(box_subclasses);
-    RCLASSEXT_BOX_SUPER_SUBCLASSES(ext) = 0;
-}
-
-void
-rb_class_classext_free_subclasses(rb_classext_t *ext, VALUE klass, bool replacing)
-{
-    rb_subclass_anchor_t *anchor = RCLASSEXT_SUBCLASSES(ext);
-    struct st_table *tbl = anchor->box_subclasses->tbl;
-    VALUE box_id = box_subclasses_tbl_key(RCLASSEXT_BOX(ext));
-    rb_subclass_entry_t *next, *entry = anchor->head;
-
-    while (entry) {
-        next = entry->next;
-        xfree(entry);
-        entry = next;
-    }
-    VM_ASSERT(
-        rb_box_subclasses_ref_count(anchor->box_subclasses) > 0,
-        "box_subclasses refcount (%p) %ld", anchor->box_subclasses, rb_box_subclasses_ref_count(anchor->box_subclasses));
-    st_delete(tbl, &box_id, NULL);
-    rb_box_subclasses_ref_dec(anchor->box_subclasses);
-    xfree(anchor);
-
-    if (RCLASSEXT_BOX_SUPER_SUBCLASSES(ext)) {
-        rb_box_subclasses_t *box_sub = RCLASSEXT_BOX_SUPER_SUBCLASSES(ext);
-        if (!replacing) remove_class_from_subclasses(box_sub->tbl, box_id, klass);
-        rb_box_subclasses_ref_dec(box_sub);
-    }
-    if (RCLASSEXT_BOX_MODULE_SUBCLASSES(ext)) {
-        rb_box_subclasses_t *box_sub = RCLASSEXT_BOX_MODULE_SUBCLASSES(ext);
-        if (!replacing) remove_class_from_subclasses(box_sub->tbl, box_id, klass);
-        rb_box_subclasses_ref_dec(box_sub);
+        RCLASSEXT_SUBCLASSES(ext) = NULL;
     }
 }
 
@@ -755,8 +678,6 @@ class_switch_superclass(VALUE super, VALUE klass)
 static VALUE
 class_alloc0(enum ruby_value_type type, VALUE klass, bool boxable)
 {
-    rb_box_subclasses_t *box_subclasses;
-    rb_subclass_anchor_t *anchor;
     const rb_box_t *box = rb_current_box();
 
     if (!ruby_box_init_done) {
@@ -768,19 +689,6 @@ class_alloc0(enum ruby_value_type type, VALUE klass, bool boxable)
         alloc_size = sizeof(struct RClass_boxable);
     }
 
-    // class_alloc is supposed to return a new object that is not promoted yet.
-    // So, we need to avoid GC after NEWOBJ_OF.
-    // To achieve that, we allocate subclass lists before NEWOBJ_OF.
-    //
-    // TODO: Note that this could cause memory leak.
-    // If NEWOBJ_OF fails with out of memory, these buffers will leak.
-    box_subclasses = ZALLOC(rb_box_subclasses_t);
-    box_subclasses->refcount = 1;
-    box_subclasses->tbl = st_init_numtable();
-    anchor = ZALLOC(rb_subclass_anchor_t);
-    anchor->box_subclasses = box_subclasses;
-    anchor->head = ZALLOC(rb_subclass_entry_t);
-
     RUBY_ASSERT(type == T_CLASS || type == T_ICLASS || type == T_MODULE);
 
     VALUE flags = type | FL_SHAREABLE;
@@ -812,8 +720,6 @@ class_alloc0(enum ruby_value_type type, VALUE klass, bool boxable)
     RCLASS_SET_ORIGIN((VALUE)obj, (VALUE)obj);
     RCLASS_SET_REFINED_CLASS((VALUE)obj, Qnil);
 
-    RCLASS_SET_SUBCLASSES((VALUE)obj, anchor);
-
     return (VALUE)obj;
 }
 
@@ -828,7 +734,12 @@ static VALUE
 class_associate_super(VALUE klass, VALUE super, bool init)
 {
     if (super && !UNDEF_P(super)) {
-        class_switch_superclass(super, klass);
+        // Only maintain subclass lists for T_CLASS→T_CLASS relationships.
+        // Include/prepend inserts ICLASSes into the super chain, but T_CLASS
+        // subclass lists should track only the immutable T_CLASS→T_CLASS link.
+        if (RB_TYPE_P(klass, T_CLASS) && RB_TYPE_P(super, T_CLASS)) {
+            class_switch_superclass(super, klass);
+        }
     }
     if (init) {
         RCLASS_SET_SUPER(klass, super);
@@ -2215,19 +2126,17 @@ class_descendants_recursive(VALUE klass, VALUE v)
 {
     struct subclass_traverse_data *data = (struct subclass_traverse_data *) v;
 
-    if (BUILTIN_TYPE(klass) == T_CLASS && !RCLASS_SINGLETON_P(klass)) {
+    if (RB_TYPE_P(klass, T_ICLASS)) return; // skip refinement ICLASSes
+
+    if (!RCLASS_SINGLETON_P(klass)) {
         if (data->buffer && data->count < data->maxcount && !rb_objspace_garbage_object_p(klass)) {
             // assumes that this does not cause GC as long as the length does not exceed the capacity
             rb_ary_push(data->buffer, klass);
         }
         data->count++;
-        if (!data->immediate_only) {
-            rb_class_foreach_subclass(klass, class_descendants_recursive, v);
-        }
-    }
-    else {
-        rb_class_foreach_subclass(klass, class_descendants_recursive, v);
+        if (data->immediate_only) return;
     }
+    rb_class_foreach_subclass(klass, class_descendants_recursive, v);
 }
 
 static VALUE
diff --git a/eval.c b/eval.c
index deadd5dd64..6d83033e1e 100644
--- a/eval.c
+++ b/eval.c
@@ -1429,6 +1429,8 @@ rb_using_refinement(rb_cref_t *cref, VALUE klass, VALUE module)
 
     RCLASS_WRITE_M_TBL(c, RCLASS_M_TBL(module));
 
+    rb_class_subclass_add(klass, iclass);
+
     rb_hash_aset(CREF_REFINEMENTS(cref), klass, iclass);
 }
 
@@ -1529,10 +1531,12 @@ add_activated_refinement(VALUE activated_refinements,
     superclass = refinement_superclass(superclass);
     c = iclass = rb_include_class_new(refinement, superclass);
     RCLASS_SET_REFINED_CLASS(c, klass);
+    rb_class_subclass_add(klass, iclass);
     refinement = RCLASS_SUPER(refinement);
     while (refinement && refinement != klass) {
         c = rb_class_set_super(c, rb_include_class_new(refinement, RCLASS_SUPER(c)));
         RCLASS_SET_REFINED_CLASS(c, klass);
+        rb_class_subclass_add(klass, c);
         refinement = RCLASS_SUPER(refinement);
     }
     rb_hash_aset(activated_refinements, klass, iclass);
diff --git a/gc.c b/gc.c
index 8e239011e6..0afba4f22c 100644
--- a/gc.c
+++ b/gc.c
@@ -3764,10 +3764,8 @@ update_const_tbl(void *objspace, struct rb_id_table *tbl)
 static void
 update_subclasses(void *objspace, rb_classext_t *ext)
 {
-    rb_subclass_entry_t *entry;
-    rb_subclass_anchor_t *anchor = RCLASSEXT_SUBCLASSES(ext);
-    if (!anchor) return;
-    entry = anchor->head;
+    rb_subclass_entry_t *entry = RCLASSEXT_SUBCLASSES(ext);
+    if (!entry) return;
     while (entry) {
         if (entry->klass)
             UPDATE_IF_MOVED(objspace, entry->klass);
diff --git a/internal/class.h b/internal/class.h
index ea68b07fc2..164081b569 100644
--- a/internal/class.h
+++ b/internal/class.h
@@ -27,41 +27,6 @@
 # undef RCLASS_SUPER
 #endif
 
-struct rb_box_subclasses {
-    long refcount;
-    struct st_table *tbl;
-};
-typedef struct rb_box_subclasses rb_box_subclasses_t;
-
-static inline long
-rb_box_subclasses_ref_count(rb_box_subclasses_t *box_sub)
-{
-    return box_sub->refcount;
-}
-
-static inline rb_box_subclasses_t *
-rb_box_subclasses_ref_inc(rb_box_subclasses_t *box_sub)
-{
-    box_sub->refcount++;
-    return box_sub;
-}
-
-static inline void
-rb_box_subclasses_ref_dec(rb_box_subclasses_t *box_sub)
-{
-    box_sub->refcount--;
-    if (box_sub->refcount == 0) {
-        st_free_table(box_sub->tbl);
-        xfree(box_sub);
-    }
-}
-
-struct rb_subclass_anchor {
-    rb_box_subclasses_t *box_subclasses;
-    struct rb_subclass_entry *head;
-};
-typedef struct rb_subclass_anchor rb_subclass_anchor_t;
-
 struct rb_subclass_entry {
     VALUE klass;
     struct rb_subclass_entry *next;
@@ -87,24 +52,21 @@ struct rb_classext_struct {
     struct rb_id_table *cvc_tbl;
     VALUE *superclasses;
     /**
-     * The head of subclasses is a blank (w/o klass) entry to be referred from anchor (and be never deleted).
-     * (anchor -> head -> 1st-entry)
+     * The head of the subclasses linked list. This is a dummy entry (klass == 0)
+     * whose `next` points to the first real entry. Only used in prime classext.
      */
-    struct rb_subclass_anchor *subclasses;
+    struct rb_subclass_entry *subclasses;
     /**
-     * The `box_super_subclasses` points the `box_subclasses` struct to retreive the subclasses
-     * of the super class in a specific box.
-     * In compaction GCs, collecting a classext should trigger the deletion of a rb_subclass_entry
-     * from the super's subclasses. But it may be prevented by the read barrier.
-     * Fetching the super's subclasses for a ns is to avoid the read barrier in that process.
+     * Back-pointer to this class's entry in its superclass's subclasses list.
+     * Used for O(1) removal when the class is freed.
      */
-    rb_box_subclasses_t *box_super_subclasses;
+    struct rb_subclass_entry *subclass_entry;
     /**
-     * In the case that this is an `ICLASS`, `box_module_subclasses` points to the link
-     * in the module's `subclasses` list that indicates that the klass has been
-     * included. Hopefully that makes sense.
+     * In the case that this is an `ICLASS`, `module_subclass_entry` points to the
+     * entry in the module's `subclasses` list that indicates that the klass has been
+     * included. Used for O(1) removal.
      */
-    rb_box_subclasses_t *box_module_subclasses;
+    struct rb_subclass_entry *module_subclass_entry;
 
     const VALUE origin_;
     const VALUE refined_class;
@@ -188,8 +150,8 @@ static inline rb_classext_t * RCLASS_EXT_WRITABLE(VALUE obj);
 #define RCLASSEXT_SUPERCLASS_DEPTH(ext) (ext->superclass_depth)
 #define RCLASSEXT_SUPERCLASSES(ext) (ext->superclasses)
 #define RCLASSEXT_SUBCLASSES(ext) (ext->subclasses)
-#define RCLASSEXT_BOX_SUPER_SUBCLASSES(ext) (ext->box_super_subclasses)
-#define RCLASSEXT_BOX_MODULE_SUBCLASSES(ext) (ext->box_module_subclasses)
+#define RCLASSEXT_SUBCLASS_ENTRY(ext) (ext->subclass_entry)
+#define RCLASSEXT_MODULE_SUBCLASS_ENTRY(ext) (ext->module_subclass_entry)
 #define RCLASSEXT_ORIGIN(ext) (ext->origin_)
 #define RCLASSEXT_REFINED_CLASS(ext) (ext->refined_class)
 // class.allocator/singleton_class.attached_object are not accessed directly via RCLASSEXT_*
@@ -227,8 +189,8 @@ static inline void RCLASSEXT_SET_INCLUDER(rb_classext_t *ext, VALUE klass, VALUE
  * so always those should be writable.
  */
 #define RCLASS_CVC_TBL(c) (RCLASS_EXT_READABLE(c)->cvc_tbl)
-#define RCLASS_SUBCLASSES_X(c) (RCLASS_EXT_READABLE(c)->subclasses)
-#define RCLASS_SUBCLASSES_FIRST(c) (RCLASS_EXT_READABLE(c)->subclasses->head->next)
+#define RCLASS_SUBCLASSES(c) (RCLASS_EXT_PRIME(c)->subclasses)
+#define RCLASS_SUBCLASSES_FIRST(c) (RCLASS_EXT_PRIME(c)->subclasses ? RCLASS_EXT_PRIME(c)->subclasses->next : NULL)
 #define RCLASS_ORIGIN(c) (RCLASS_EXT_READABLE(c)->origin_)
 #define RICLASS_IS_ORIGIN_P(c) (RCLASS_EXT_READABLE(c)->iclass_is_origin)
 #define RCLASS_PERMANENT_CLASSPATH_P(c) (RCLASS_EXT_READABLE(c)->permanent_classpath)
@@ -255,7 +217,8 @@ static inline void RCLASSEXT_SET_INCLUDER(rb_classext_t *ext, VALUE klass, VALUE
 #define RCLASS_WRITABLE_CALLABLE_M_TBL(c) (RCLASS_EXT_WRITABLE(c)->callable_m_tbl)
 #define RCLASS_WRITABLE_CC_TBL(c) (RCLASS_EXT_WRITABLE(c)->cc_tbl)
 #define RCLASS_WRITABLE_CVC_TBL(c) (RCLASS_EXT_WRITABLE(c)->cvc_tbl)
-#define RCLASS_WRITABLE_SUBCLASSES(c) (RCLASS_EXT_WRITABLE(c)->subclasses)
+// Subclasses are only in the prime classext (box-invariant)
+#define RCLASS_WRITABLE_SUBCLASSES(c) (RCLASS_EXT_PRIME(c)->subclasses)
 
 static inline void RCLASS_SET_SUPER(VALUE klass, VALUE super);
 static inline void RCLASS_WRITE_SUPER(VALUE klass, VALUE super);
@@ -267,9 +230,7 @@ static inline void RCLASS_SET_CVC_TBL(VALUE klass, struct rb_id_table *table);
 static inline void RCLASS_WRITE_CVC_TBL(VALUE klass, struct rb_id_table *table);
 
 static inline void RCLASS_WRITE_SUPERCLASSES(VALUE klass, size_t depth, VALUE *superclasses, bool with_self);
-static inline void RCLASS_SET_SUBCLASSES(VALUE klass, rb_subclass_anchor_t *anchor);
-static inline void RCLASS_WRITE_BOX_SUPER_SUBCLASSES(VALUE klass, rb_box_subclasses_t *box_subclasses);
-static inline void RCLASS_WRITE_BOX_MODULE_SUBCLASSES(VALUE klass, rb_box_subclasses_t *box_subclasses);
+static inline void RCLASS_SET_SUBCLASSES(VALUE klass, rb_subclass_entry_t *head);
 
 static inline void RCLASS_SET_ORIGIN(VALUE klass, VALUE origin);
 static inline void RCLASS_WRITE_ORIGIN(VALUE klass, VALUE origin);
@@ -488,7 +449,6 @@ RCLASSEXT_SET_INCLUDER(rb_classext_t *ext, VALUE klass, VALUE includer)
 typedef void rb_class_classext_foreach_callback_func(rb_classext_t *classext, bool is_prime, VALUE box_value, void *arg);
 void rb_class_classext_foreach(VALUE klass, rb_class_classext_foreach_callback_func *func, void *arg);
 void rb_class_subclass_add(VALUE super, VALUE klass);
-void rb_class_classext_free_subclasses(rb_classext_t *, VALUE, bool);
 void rb_class_foreach_subclass(VALUE klass, void (*f)(VALUE, VALUE), VALUE);
 void rb_class_update_superclasses(VALUE);
 int rb_singleton_class_internal_p(VALUE sklass);
@@ -727,28 +687,10 @@ RCLASS_WRITE_SUPERCLASSES(VALUE klass, size_t depth, VALUE *superclasses, bool w
 }
 
 static inline void
-RCLASS_SET_SUBCLASSES(VALUE klass, struct rb_subclass_anchor *anchor)
+RCLASS_SET_SUBCLASSES(VALUE klass, rb_subclass_entry_t *head)
 {
     rb_classext_t *ext = RCLASS_EXT_PRIME(klass);
-    RCLASSEXT_SUBCLASSES(ext) = anchor;
-}
-
-static inline void
-RCLASS_WRITE_BOX_SUPER_SUBCLASSES(VALUE klass, rb_box_subclasses_t *box_subclasses)
-{
-    rb_classext_t *ext = RCLASS_EXT_WRITABLE(klass);
-    if (RCLASSEXT_BOX_SUPER_SUBCLASSES(ext))
-        rb_box_subclasses_ref_dec(RCLASSEXT_BOX_SUPER_SUBCLASSES(ext));
-    RCLASSEXT_BOX_SUPER_SUBCLASSES(ext) = rb_box_subclasses_ref_inc(box_subclasses);
-}
-
-static inline void
-RCLASS_WRITE_BOX_MODULE_SUBCLASSES(VALUE klass, rb_box_subclasses_t *box_subclasses)
-{
-    rb_classext_t *ext = RCLASS_EXT_WRITABLE(klass);
-    if (RCLASSEXT_BOX_MODULE_SUBCLASSES(ext))
-        rb_box_subclasses_ref_dec(RCLASSEXT_BOX_MODULE_SUBCLASSES(ext));
-    RCLASSEXT_BOX_MODULE_SUBCLASSES(ext) = rb_box_subclasses_ref_inc(box_subclasses);
+    RCLASSEXT_SUBCLASSES(ext) = head;
 }
 
 static inline void
diff --git a/test/ruby/test_box.rb b/test/ruby/test_box.rb
index cfd21ac0aa..43a753b311 100644
--- a/test/ruby/test_box.rb
+++ b/test/ruby/test_box.rb
@@ -870,4 +870,22 @@ class TestBox < Test::Unit::TestCase
       end
     end;
   end
+
+  def test_user_box_iclass_with_module_modified_in_another_box
+    assert_separately([ENV_ENABLE_BOX], __FILE__, __LINE__, "#{<<~"begin;"}\n#{<<~'end;'}", ignore_stderr: true)
+    begin;
+      # A user box creates a class that includes a core module.
+      # The ICLASS is allocated in the user box context (non-boxable).
+      box1 = Ruby::Box.new
+      box1.eval("class IMath; include Math; end")
+
+      # A second user box adds an instance method on that module,
+      # triggering classext duplication which iterates the module's
+      # subclass list and encounters box1's non-boxable ICLASS.
+      box2 = Ruby::Box.new
+      box2.eval("module Math; def box2_test = :box2; end")
+
+      assert_equal :box2, box2.eval("Class.new { include Math }.new.box2_test")
+    end;
+  end
 end
diff --git a/variable.c b/variable.c
index ff8d24d78a..11b186063e 100644
--- a/variable.c
+++ b/variable.c
@@ -4233,8 +4233,9 @@ find_cvar(VALUE klass, VALUE * front, VALUE * target, ID id)
 static void
 check_for_cvar_table(VALUE subclass, VALUE key)
 {
-    // Must not check ivar on ICLASS
-    if (!RB_TYPE_P(subclass, T_ICLASS) && RTEST(rb_ivar_defined(subclass, key))) {
+    if (RB_TYPE_P(subclass, T_ICLASS)) return; // skip refinement ICLASSes
+
+    if (RTEST(rb_ivar_defined(subclass, key))) {
         RB_DEBUG_COUNTER_INC(cvar_class_invalidate);
         ruby_vm_global_cvar_state++;
         return;
diff --git a/vm_method.c b/vm_method.c
index 2b3ac74d57..fcb2f28f8d 100644
--- a/vm_method.c
+++ b/vm_method.c
@@ -442,7 +442,11 @@ clear_method_cache_by_id_in_class(VALUE klass, ID mid)
     RB_VM_LOCKING() {
         rb_vm_barrier();
 
-        if (LIKELY(RCLASS_SUBCLASSES_FIRST(klass) == NULL)) {
+        if (LIKELY(RCLASS_SUBCLASSES_FIRST(klass) == NULL) &&
+            // Non-refinement ICLASSes (from module inclusion) previously had
+            // subclasses reparented onto them, so they need the tree path for
+            // broader cme-based invalidation even though they now have no subclasses.
+            !(RB_TYPE_P(klass, T_ICLASS) && NIL_P(RCLASS_REFINED_CLASS(klass)))) {
             // no subclasses
             // check only current class
 
@@ -1280,6 +1284,16 @@ rb_add_refined_method_entry(VALUE refined_class, ID mid)
 static void
 check_override_opt_method_i(VALUE klass, VALUE arg)
 {
+    if (RB_TYPE_P(klass, T_ICLASS)) {
+        // ICLASS from a module's subclass list: check the includer and
+        // recurse into the includer's T_CLASS subclasses.
+        VALUE includer = RCLASS_INCLUDER(klass);
+        if (!UNDEF_P(includer) && includer) {
+            check_override_opt_method_i(includer, arg);
+        }
+        return;
+    }
+
     ID mid = (ID)arg;
     const rb_method_entry_t *me, *newme;