From ad63b668e22e21c352b852f3119ae98a7acf99f1 Mon Sep 17 00:00:00 2001 From: Jemma Issroff Date: Mon, 3 Oct 2022 11:14:32 -0400 Subject: Revert "Revert "This commit implements the Object Shapes technique in CRuby."" This reverts commit 9a6803c90b817f70389cae10d60b50ad752da48f. --- shape.c | 523 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 523 insertions(+) create mode 100644 shape.c (limited to 'shape.c') diff --git a/shape.c b/shape.c new file mode 100644 index 0000000000..a6a5adf854 --- /dev/null +++ b/shape.c @@ -0,0 +1,523 @@ +#include "vm_core.h" +#include "vm_sync.h" +#include "shape.h" +#include "internal/class.h" +#include "internal/symbol.h" +#include "internal/variable.h" +#include + +/* + * Shape getters + */ +static rb_shape_t* +rb_shape_get_root_shape(void) { + return GET_VM()->root_shape; +} + +shape_id_t +rb_shape_id(rb_shape_t * shape) +{ + return (shape_id_t)(shape - GET_VM()->shape_list); +} + +static rb_shape_t* +rb_shape_get_frozen_root_shape(void) { + return GET_VM()->frozen_root_shape; +} + +bool +rb_shape_root_shape_p(rb_shape_t* shape) { + return shape == rb_shape_get_root_shape(); +} + +rb_shape_t* +rb_shape_get_shape_by_id(shape_id_t shape_id) +{ + RUBY_ASSERT(shape_id != INVALID_SHAPE_ID); + + rb_vm_t *vm = GET_VM(); + rb_shape_t *shape = &vm->shape_list[shape_id]; + return shape; +} + +rb_shape_t* +rb_shape_get_shape_by_id_without_assertion(shape_id_t shape_id) +{ + RUBY_ASSERT(shape_id != INVALID_SHAPE_ID); + + rb_vm_t *vm = GET_VM(); + rb_shape_t *shape = &vm->shape_list[shape_id]; + return shape; +} + +#if !SHAPE_IN_BASIC_FLAGS +static inline shape_id_t +RCLASS_SHAPE_ID(VALUE obj) +{ + return RCLASS_EXT(obj)->shape_id; +} + +shape_id_t rb_generic_shape_id(VALUE obj); +#endif + +shape_id_t +rb_shape_get_shape_id(VALUE obj) +{ + if (RB_SPECIAL_CONST_P(obj)) { + return FROZEN_ROOT_SHAPE_ID; + } + +#if SHAPE_IN_BASIC_FLAGS + return RBASIC_SHAPE_ID(obj); +#else + switch (BUILTIN_TYPE(obj)) { + case T_OBJECT: + return ROBJECT_SHAPE_ID(obj); + break; + case T_CLASS: + case T_MODULE: + return RCLASS_SHAPE_ID(obj); + default: + return rb_generic_shape_id(obj); + } +#endif +} + +rb_shape_t* +rb_shape_get_shape(VALUE obj) +{ + return rb_shape_get_shape_by_id(rb_shape_get_shape_id(obj)); +} + +static rb_shape_t * +rb_shape_lookup_id(rb_shape_t* shape, ID id, enum shape_type shape_type) { + while (shape->parent) { + if (shape->edge_name == id) { + // If the shape type is different, we don't + // want this to count as a "found" ID + if (shape_type == (enum shape_type)shape->type) { + return shape; + } + else { + return NULL; + } + } + shape = shape->parent; + } + return NULL; +} + +static rb_shape_t* +get_next_shape_internal(rb_shape_t* shape, ID id, VALUE obj, enum shape_type shape_type) +{ + rb_shape_t *res = NULL; + RUBY_ASSERT(SHAPE_FROZEN != (enum shape_type)shape->type); + RB_VM_LOCK_ENTER(); + { + if (rb_shape_lookup_id(shape, id, shape_type)) { + // If shape already contains the ivar that is being set, we'll return shape + res = shape; + } + else { + if (!shape->edges) { + shape->edges = rb_id_table_create(0); + } + + // Lookup the shape in edges - if there's already an edge and a corresponding shape for it, + // we can return that. Otherwise, we'll need to get a new shape + if (!rb_id_table_lookup(shape->edges, id, (VALUE *)&res)) { + // In this case, the shape exists, but the shape is garbage, so we need to recreate it + if (res) { + rb_id_table_delete(shape->edges, id); + res->parent = NULL; + } + + rb_shape_t * new_shape = rb_shape_alloc(id, shape); + + new_shape->type = (uint8_t)shape_type; + + switch(shape_type) { + case SHAPE_IVAR: + new_shape->iv_count = new_shape->parent->iv_count + 1; + + // Check if we should update max_iv_count on the object's class + if (BUILTIN_TYPE(obj) == T_OBJECT) { + VALUE klass = rb_obj_class(obj); + if (new_shape->iv_count > RCLASS_EXT(klass)->max_iv_count) { + RCLASS_EXT(klass)->max_iv_count = new_shape->iv_count; + } + } + break; + case SHAPE_IVAR_UNDEF: + case SHAPE_FROZEN: + new_shape->iv_count = new_shape->parent->iv_count; + break; + case SHAPE_ROOT: + rb_bug("Unreachable"); + break; + } + + rb_id_table_insert(shape->edges, id, (VALUE)new_shape); + + res = new_shape; + } + } + } + RB_VM_LOCK_LEAVE(); + return res; +} + +MJIT_FUNC_EXPORTED int +rb_shape_frozen_shape_p(rb_shape_t* shape) +{ + return SHAPE_FROZEN == (enum shape_type)shape->type; +} + +void +rb_shape_transition_shape_remove_ivar(VALUE obj, ID id, rb_shape_t *shape) +{ + rb_shape_t* next_shape = get_next_shape_internal(shape, id, obj, SHAPE_IVAR_UNDEF); + + if (shape == next_shape) { + return; + } + + rb_shape_set_shape(obj, next_shape); +} + +void +rb_shape_transition_shape_frozen(VALUE obj) +{ + rb_shape_t* shape = rb_shape_get_shape(obj); + RUBY_ASSERT(shape); + RUBY_ASSERT(RB_OBJ_FROZEN(obj)); + + if (rb_shape_frozen_shape_p(shape)) { + return; + } + + rb_shape_t* next_shape; + + if (shape == rb_shape_get_root_shape()) { + switch(BUILTIN_TYPE(obj)) { + case T_OBJECT: + case T_CLASS: + case T_MODULE: + break; + default: + return; + } + next_shape = rb_shape_get_frozen_root_shape(); + } + else { + static ID id_frozen; + if (!id_frozen) { + id_frozen = rb_make_internal_id(); + } + + next_shape = get_next_shape_internal(shape, (ID)id_frozen, obj, SHAPE_FROZEN); + } + + RUBY_ASSERT(next_shape); + rb_shape_set_shape(obj, next_shape); +} + +void +rb_shape_transition_shape(VALUE obj, ID id, rb_shape_t *shape) +{ + rb_shape_t* next_shape = rb_shape_get_next(shape, obj, id); + if (shape == next_shape) { + return; + } + rb_shape_set_shape(obj, next_shape); +} + +rb_shape_t* +rb_shape_get_next(rb_shape_t* shape, VALUE obj, ID id) +{ + return get_next_shape_internal(shape, id, obj, SHAPE_IVAR); +} + +bool +rb_shape_get_iv_index(rb_shape_t * shape, ID id, attr_index_t *value) { + while (shape->parent) { + if (shape->edge_name == id) { + enum shape_type shape_type; + shape_type = (enum shape_type)shape->type; + + switch(shape_type) { + case SHAPE_IVAR: + RUBY_ASSERT(shape->iv_count > 0); + *value = shape->iv_count - 1; + return true; + case SHAPE_IVAR_UNDEF: + case SHAPE_ROOT: + return false; + case SHAPE_FROZEN: + rb_bug("Ivar should not exist on frozen transition\n"); + } + } + shape = shape->parent; + } + return false; +} + +static rb_shape_t * +shape_alloc(void) +{ + rb_vm_t *vm = GET_VM(); + shape_id_t shape_id = vm->next_shape_id; + vm->next_shape_id++; + + if (shape_id == MAX_SHAPE_ID) { + // TODO: Make an OutOfShapesError ?? + rb_bug("Out of shapes\n"); + } + + return &GET_VM()->shape_list[shape_id]; +} + +rb_shape_t * +rb_shape_alloc(ID edge_name, rb_shape_t * parent) +{ + rb_shape_t * shape = shape_alloc(); + + shape->edge_name = edge_name; + shape->iv_count = 0; + shape->parent = parent; + + return shape; +} + +MJIT_FUNC_EXPORTED void +rb_shape_set_shape(VALUE obj, rb_shape_t* shape) +{ + rb_shape_set_shape_id(obj, rb_shape_id(shape)); +} + +VALUE rb_cShape; + +/* + * Exposing Shape to Ruby via RubyVM.debug_shape + */ +static const rb_data_type_t shape_data_type = { + "Shape", + {NULL, NULL, NULL,}, + 0, 0, RUBY_TYPED_FREE_IMMEDIATELY|RUBY_TYPED_WB_PROTECTED +}; + +static VALUE +rb_wrapped_shape_id(VALUE self) { + rb_shape_t * shape; + TypedData_Get_Struct(self, rb_shape_t, &shape_data_type, shape); + return INT2NUM(rb_shape_id(shape)); +} + +static VALUE +rb_shape_type(VALUE self) { + rb_shape_t * shape; + TypedData_Get_Struct(self, rb_shape_t, &shape_data_type, shape); + return INT2NUM(shape->type); +} + +static VALUE +rb_shape_parent_id(VALUE self) +{ + rb_shape_t * shape; + TypedData_Get_Struct(self, rb_shape_t, &shape_data_type, shape); + if (shape->parent) { + return INT2NUM(rb_shape_id(shape->parent)); + } + else { + return Qnil; + } +} + +static VALUE parse_key(ID key) { + if ((key & RUBY_ID_INTERNAL) == RUBY_ID_INTERNAL) { + return LONG2NUM(key); + } else { + return ID2SYM(key); + } +} + +static VALUE +rb_shape_t_to_rb_cShape(rb_shape_t *shape) { + union { const rb_shape_t *in; void *out; } deconst; + VALUE res; + deconst.in = shape; + res = TypedData_Wrap_Struct(rb_cShape, &shape_data_type, deconst.out); + + return res; +} + +static enum rb_id_table_iterator_result rb_edges_to_hash(ID key, VALUE value, void *ref) +{ + rb_hash_aset(*(VALUE *)ref, parse_key(key), rb_shape_t_to_rb_cShape((rb_shape_t*)value)); + return ID_TABLE_CONTINUE; +} + +static VALUE +rb_shape_edges(VALUE self) +{ + rb_shape_t* shape; + TypedData_Get_Struct(self, rb_shape_t, &shape_data_type, shape); + + VALUE hash = rb_hash_new(); + + if (shape->edges) { + rb_id_table_foreach(shape->edges, rb_edges_to_hash, &hash); + } + + return hash; +} + +static VALUE +rb_shape_edge_name(VALUE self) +{ + rb_shape_t* shape; + TypedData_Get_Struct(self, rb_shape_t, &shape_data_type, shape); + + if (shape->edge_name) { + return ID2SYM(shape->edge_name); + } + else { + return Qnil; + } +} + +static VALUE +rb_shape_iv_count(VALUE self) +{ + rb_shape_t* shape; + TypedData_Get_Struct(self, rb_shape_t, &shape_data_type, shape); + + return INT2NUM(shape->iv_count); +} + +static VALUE +rb_shape_export_depth(VALUE self) +{ + rb_shape_t* shape; + TypedData_Get_Struct(self, rb_shape_t, &shape_data_type, shape); + + unsigned int depth = 0; + while (shape->parent) { + depth++; + shape = shape->parent; + } + return INT2NUM(depth); +} + +static VALUE +rb_shape_parent(VALUE self) +{ + rb_shape_t * shape; + TypedData_Get_Struct(self, rb_shape_t, &shape_data_type, shape); + if (shape->parent) { + return rb_shape_t_to_rb_cShape(shape->parent); + } + else { + return Qnil; + } +} + +VALUE rb_shape_debug_shape(VALUE self, VALUE obj) { + return rb_shape_t_to_rb_cShape(rb_shape_get_shape(obj)); +} + +VALUE rb_shape_debug_root_shape(VALUE self) { + return rb_shape_t_to_rb_cShape(rb_shape_get_root_shape()); +} + +VALUE rb_shape_debug_frozen_root_shape(VALUE self) { + return rb_shape_t_to_rb_cShape(rb_shape_get_frozen_root_shape()); +} + +VALUE rb_obj_shape(rb_shape_t* shape); + +static enum rb_id_table_iterator_result collect_keys_and_values(ID key, VALUE value, void *ref) +{ + rb_hash_aset(*(VALUE *)ref, parse_key(key), rb_obj_shape((rb_shape_t*)value)); + return ID_TABLE_CONTINUE; +} + +static VALUE edges(struct rb_id_table* edges) +{ + VALUE hash = rb_hash_new(); + if (edges) + rb_id_table_foreach(edges, collect_keys_and_values, &hash); + return hash; +} + +VALUE rb_obj_shape(rb_shape_t* shape) { + VALUE rb_shape = rb_hash_new(); + + rb_hash_aset(rb_shape, ID2SYM(rb_intern("id")), INT2NUM(rb_shape_id(shape))); + rb_hash_aset(rb_shape, ID2SYM(rb_intern("edges")), edges(shape->edges)); + + if (shape == rb_shape_get_root_shape()) { + rb_hash_aset(rb_shape, ID2SYM(rb_intern("parent_id")), INT2NUM(ROOT_SHAPE_ID)); + } + else { + rb_hash_aset(rb_shape, ID2SYM(rb_intern("parent_id")), INT2NUM(rb_shape_id(shape->parent))); + } + + rb_hash_aset(rb_shape, ID2SYM(rb_intern("edge_name")), rb_id2str(shape->edge_name)); + return rb_shape; +} + +static VALUE shape_transition_tree(VALUE self) { + return rb_obj_shape(rb_shape_get_root_shape()); +} + +static VALUE shape_count(VALUE self) { + int shape_count = 0; + rb_vm_t *vm = GET_VM(); + for(shape_id_t i = 0; i < vm->next_shape_id; i++) { + if(rb_shape_get_shape_by_id_without_assertion(i)) { + shape_count++; + } + } + return INT2NUM(shape_count); +} + +static VALUE +shape_max_shape_count(VALUE self) +{ + return INT2NUM(GET_VM()->next_shape_id); +} + +VALUE +rb_shape_flags_mask(void) +{ + return SHAPE_FLAG_MASK; +} + +void +Init_shape(void) +{ + rb_cShape = rb_define_class_under(rb_cRubyVM, "Shape", rb_cObject); + rb_undef_alloc_func(rb_cShape); + + rb_define_method(rb_cShape, "parent_id", rb_shape_parent_id, 0); + rb_define_method(rb_cShape, "parent", rb_shape_parent, 0); + rb_define_method(rb_cShape, "edges", rb_shape_edges, 0); + rb_define_method(rb_cShape, "edge_name", rb_shape_edge_name, 0); + rb_define_method(rb_cShape, "iv_count", rb_shape_iv_count, 0); + rb_define_method(rb_cShape, "depth", rb_shape_export_depth, 0); + rb_define_method(rb_cShape, "id", rb_wrapped_shape_id, 0); + rb_define_method(rb_cShape, "type", rb_shape_type, 0); + rb_define_const(rb_cShape, "SHAPE_ROOT", INT2NUM(SHAPE_ROOT)); + rb_define_const(rb_cShape, "SHAPE_IVAR", INT2NUM(SHAPE_IVAR)); + rb_define_const(rb_cShape, "SHAPE_IVAR_UNDEF", INT2NUM(SHAPE_IVAR_UNDEF)); + rb_define_const(rb_cShape, "SHAPE_FROZEN", INT2NUM(SHAPE_FROZEN)); + rb_define_const(rb_cShape, "SHAPE_BITS", INT2NUM(SHAPE_BITS)); + + rb_define_module_function(rb_cRubyVM, "debug_shape_transition_tree", shape_transition_tree, 0); + rb_define_module_function(rb_cRubyVM, "debug_shape_count", shape_count, 0); + rb_define_singleton_method(rb_cRubyVM, "debug_shape", rb_shape_debug_shape, 1); + rb_define_singleton_method(rb_cRubyVM, "debug_max_shape_count", shape_max_shape_count, 0); + rb_define_singleton_method(rb_cRubyVM, "debug_root_shape", rb_shape_debug_root_shape, 0); + rb_define_singleton_method(rb_cRubyVM, "debug_frozen_root_shape", rb_shape_debug_frozen_root_shape, 0); +} -- cgit v1.2.3