ruby-changes:69866
From: Matt <ko1@a...>
Date: Mon, 22 Nov 2021 23:11:28 +0900 (JST)
Subject: [ruby-changes:69866] b680b632e5 (master): Make RCLASS_EXT(c)->subclasses a doubly linked list
https://git.ruby-lang.org/ruby.git/commit/?id=b680b632e5 From b680b632e5b88e4ea550de3f15cf6ef782efeb48 Mon Sep 17 00:00:00 2001 From: Matt Valentine-House <matt@e...> Date: Mon, 15 Nov 2021 21:09:10 +0000 Subject: Make RCLASS_EXT(c)->subclasses a doubly linked list Updating RCLASS_PARENT_SUBCLASSES and RCLASS_MODULE_SUBCLASSES while compacting can trigger the read barrier. This commit makes RCLASS_SUBCLASSES a doubly linked list with a dedicated head object so that we can add and remove entries from the list without having to touch an object in the Ruby heap --- class.c | 114 ++++++++++++++++++++++++++++++++++++------------------- gc.c | 15 +------- internal/class.h | 10 +++-- 3 files changed, 84 insertions(+), 55 deletions(-) diff --git a/class.c b/class.c index 01939f50088..52750aad79d 100644 --- a/class.c +++ b/class.c @@ -37,87 +37,113 @@ https://github.com/ruby/ruby/blob/trunk/class.c#L37 RUBY_EXTERN rb_serial_t ruby_vm_global_cvar_state; -void -rb_class_subclass_add(VALUE super, VALUE klass) +static rb_subclass_entry_t * +push_subclass_entry_to_list(VALUE super, VALUE klass) { rb_subclass_entry_t *entry, *head; - if (super && super != Qundef) { - entry = ALLOC(rb_subclass_entry_t); - entry->klass = klass; - entry->next = NULL; - - head = RCLASS_SUBCLASSES(super); - if (head) { - entry->next = head; - RCLASS_PARENT_SUBCLASSES(head->klass) = &entry->next; - } + entry = ZALLOC(rb_subclass_entry_t); + entry->klass = klass; - RCLASS_SUBCLASSES(super) = entry; - RCLASS_PARENT_SUBCLASSES(klass) = &RCLASS_SUBCLASSES(super); + head = RCLASS_SUBCLASSES(super); + if (!head) { + head = ZALLOC(rb_subclass_entry_t); + RCLASS_SUBCLASSES(super) = head; + } + entry->next = head->next; + entry->prev = head; + + if (head->next) { + head->next->prev = entry; + } + head->next = entry; + + return entry; +} + +void +rb_class_subclass_add(VALUE super, VALUE klass) +{ + if (super && super != Qundef) { + rb_subclass_entry_t *entry = push_subclass_entry_to_list(super, klass); + RCLASS_SUBCLASS_ENTRY(klass) = entry; } } static void rb_module_add_to_subclasses_list(VALUE module, VALUE iclass) { - rb_subclass_entry_t *entry, *head; + rb_subclass_entry_t *entry = push_subclass_entry_to_list(module, iclass); + RCLASS_MODULE_SUBCLASS_ENTRY(iclass) = entry; +} - entry = ALLOC(rb_subclass_entry_t); - entry->klass = iclass; - entry->next = NULL; +void +rb_class_remove_subclass_head(VALUE klass) +{ + rb_subclass_entry_t *head = RCLASS_SUBCLASSES(klass); - head = RCLASS_SUBCLASSES(module); if (head) { - entry->next = head; - RCLASS_MODULE_SUBCLASSES(head->klass) = &entry->next; + if (head->next) { + head->next->prev = NULL; + } + RCLASS_SUBCLASSES(klass) = NULL; + xfree(head); } - - RCLASS_SUBCLASSES(module) = entry; - RCLASS_MODULE_SUBCLASSES(iclass) = &RCLASS_SUBCLASSES(module); } void rb_class_remove_from_super_subclasses(VALUE klass) { - rb_subclass_entry_t **prev = RCLASS_PARENT_SUBCLASSES(klass); + rb_subclass_entry_t *entry = RCLASS_SUBCLASS_ENTRY(klass); - if (prev) { - rb_subclass_entry_t *entry = *prev, *next = entry->next; + if (entry) { + rb_subclass_entry_t *prev = entry->prev, *next = entry->next; + + if (prev) { + prev->next = next; + } + if (next) { + next->prev = prev; + } - *prev = next; - if (next) { - RCLASS_PARENT_SUBCLASSES(next->klass) = prev; - } xfree(entry); } - RCLASS_PARENT_SUBCLASSES(klass) = NULL; + RCLASS_SUBCLASS_ENTRY(klass) = NULL; } void rb_class_remove_from_module_subclasses(VALUE klass) { - rb_subclass_entry_t **prev = RCLASS_MODULE_SUBCLASSES(klass); + rb_subclass_entry_t *entry = RCLASS_MODULE_SUBCLASS_ENTRY(klass); - if (prev) { - rb_subclass_entry_t *entry = *prev, *next = entry->next; + if (entry) { + rb_subclass_entry_t *prev = entry->prev, *next = entry->next; - *prev = next; + if (prev) { + prev->next = next; + } if (next) { - RCLASS_MODULE_SUBCLASSES(next->klass) = prev; + next->prev = prev; } xfree(entry); } - RCLASS_MODULE_SUBCLASSES(klass) = NULL; + RCLASS_MODULE_SUBCLASS_ENTRY(klass) = NULL; } void rb_class_foreach_subclass(VALUE klass, void (*f)(VALUE, VALUE), VALUE arg) { + // RCLASS_SUBCLASSES should always point to our head element which has NULL klass rb_subclass_entry_t *cur = RCLASS_SUBCLASSES(klass); + // if we have a subclasses list, then the head is a placeholder with no valid + // class. So ignore it and use the next element in the list (if one exists) + if (cur) { + RUBY_ASSERT(!cur->klass); + cur = cur->next; + } /* do not be tempted to simplify this loop into a for loop, the order of operations is important here if `f` modifies the linked list */ @@ -963,6 +989,12 @@ rb_include_module(VALUE klass, VALUE module) https://github.com/ruby/ruby/blob/trunk/class.c#L989 if (RB_TYPE_P(klass, T_MODULE)) { rb_subclass_entry_t *iclass = RCLASS_SUBCLASSES(klass); + // skip the placeholder subclass entry at the head of the list + if (iclass && iclass->next) { + RUBY_ASSERT(!iclass->klass); + iclass = iclass->next; + } + int do_include = 1; while (iclass) { VALUE check_class = iclass->klass; @@ -1202,6 +1234,12 @@ rb_prepend_module(VALUE klass, VALUE module) https://github.com/ruby/ruby/blob/trunk/class.c#L1234 } if (RB_TYPE_P(klass, T_MODULE)) { rb_subclass_entry_t *iclass = RCLASS_SUBCLASSES(klass); + // skip the placeholder subclass entry at the head of the list if it exists + if (iclass && iclass->next) { + RUBY_ASSERT(!iclass->klass); + iclass = iclass->next; + } + VALUE klass_origin = RCLASS_ORIGIN(klass); struct rb_id_table *klass_m_tbl = RCLASS_M_TBL(klass); struct rb_id_table *klass_origin_m_tbl = RCLASS_M_TBL(klass_origin); diff --git a/gc.c b/gc.c index 60387d2ab3b..b36688979e8 100644 --- a/gc.c +++ b/gc.c @@ -3134,15 +3134,7 @@ obj_free(rb_objspace_t *objspace, VALUE obj) https://github.com/ruby/ruby/blob/trunk/gc.c#L3134 rb_id_table_foreach_values(RCLASS_CVC_TBL(obj), cvar_table_free_i, NULL); rb_id_table_free(RCLASS_CVC_TBL(obj)); } - if (RCLASS_SUBCLASSES(obj)) { - if (BUILTIN_TYPE(obj) == T_MODULE) { - rb_class_detach_module_subclasses(obj); - } - else { - rb_class_detach_subclasses(obj); - } - RCLASS_SUBCLASSES(obj) = NULL; - } + rb_class_remove_subclass_head(obj); rb_class_remove_from_module_subclasses(obj); rb_class_remove_from_super_subclasses(obj); #if !USE_RVARGC @@ -3307,10 +3299,7 @@ obj_free(rb_objspace_t *objspace, VALUE obj) https://github.com/ruby/ruby/blob/trunk/gc.c#L3299 if (RCLASS_CALLABLE_M_TBL(obj) != NULL) { rb_id_table_free(RCLASS_CALLABLE_M_TBL(obj)); } - if (RCLASS_SUBCLASSES(obj)) { - rb_class_detach_subclasses(obj); - RCLASS_SUBCLASSES(obj) = NULL; - } + rb_class_remove_subclass_head(obj); cc_table_free(objspace, obj, FALSE); rb_class_remove_from_module_subclasses(obj); rb_class_remove_from_super_subclasses(obj); diff --git a/internal/class.h b/internal/class.h index ee36ad1967f..9edc821701d 100644 --- a/internal/class.h +++ b/internal/class.h @@ -22,6 +22,7 @@ https://github.com/ruby/ruby/blob/trunk/internal/class.h#L22 struct rb_subclass_entry { VALUE klass; struct rb_subclass_entry *next; + struct rb_subclass_entry *prev; }; struct rb_iv_index_tbl_entry { @@ -47,13 +48,13 @@ struct rb_classext_struct { https://github.com/ruby/ruby/blob/trunk/internal/class.h#L48 struct rb_id_table *cc_tbl; /* ID -> [[ci, cc1], cc2, ...] */ struct rb_id_table *cvc_tbl; struct rb_subclass_entry *subclasses; - struct rb_subclass_entry **parent_subclasses; + struct rb_subclass_entry *subclass_entry; /** * In the case that this is an `ICLASS`, `module_subclasses` points to the link * in the module's `subclasses` list that indicates that the klass has been * included. Hopefully that makes sense. */ - struct rb_subclass_entry **module_subclasses; + struct rb_subclass_entry *module_subclass_entry; #if SIZEOF_SERIAL_T != SIZEOF_VALUE /* otherwise class_serial is in struct RClass */ rb_serial_t class_serial; #endif @@ -105,8 +106,8 @@ typedef struct rb_classext_struct rb_classext_t; https://github.com/ruby/ruby/blob/trunk/internal/class.h#L106 # define RCLASS_SERIAL(c) (RCLASS_EXT(c)->class_serial) #endif #define RCLASS_INCLUDER(c) (RCLASS_EXT(c)->includer) -#define RCLASS_PARENT_SUBCLASSES(c) (RCLASS_EXT(c)->parent_subclasses) -#define RCLASS_MODULE_SUBCLASSES(c) (RCLASS_EXT(c)->module_subclasses) +#define RCLASS_SUBCLASS_ENTRY(c) (RCLASS_EXT(c)->subclass_entry) +#define RCLASS_MODULE_SUBCLASS_ENTRY(c) (RCLASS_EXT(c)->module_subclass_entry) #define RCLASS_ALLOCATOR(c) (RCLASS_EXT(c)->allocator) #define RCLASS_SUBCLASSES(c) (RCLASS_EXT(c)->subclasses) @@ -117,6 +118,7 @@ typedef struct rb_classext_struct rb_classext_t; https://github.com/ruby/ruby/blob/trunk/internal/class.h#L118 /* class.c */ void rb_class_subclass_add(VALUE super, VALUE klass); void rb_class_remove_from_super_subclasses(VALUE); +void rb_class_remove_subclass_head(VALUE); int rb_singleton_class_internal_p(VALUE sklass); VALUE rb_class_boot(VALUE); VALUE rb_class_s_alloc(VALUE klass); -- cgit v1.2.1 -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/