From b680b632e5b88e4ea550de3f15cf6ef782efeb48 Mon Sep 17 00:00:00 2001 From: Matt Valentine-House 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 ++++++++++++++++++++++++++++++++++++++++++---------------------- 1 file changed, 76 insertions(+), 38 deletions(-) (limited to 'class.c') diff --git a/class.c b/class.c index 01939f5008..52750aad79 100644 --- a/class.c +++ b/class.c @@ -37,87 +37,113 @@ 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) 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) } 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); -- cgit v1.2.1