6 #include "internal/class.h"
7 #include "internal/error.h"
8 #include "internal/gc.h"
9 #include "internal/object.h"
10 #include "internal/symbol.h"
11 #include "internal/variable.h"
20 #define SHAPE_DEBUG (VM_CHECK_MODE > 0)
23 #if SIZEOF_SHAPE_T == 4
25 #define SHAPE_BUFFER_SIZE 0x8000
27 #define SHAPE_BUFFER_SIZE 0x80000
30 #define SHAPE_BUFFER_SIZE 0x8000
33 #define REDBLACK_CACHE_SIZE (SHAPE_BUFFER_SIZE * 32)
35 #define SINGLE_CHILD_TAG 0x1
36 #define TAG_SINGLE_CHILD(x) (struct rb_id_table *)((uintptr_t)x | SINGLE_CHILD_TAG)
37 #define SINGLE_CHILD_MASK (~((uintptr_t)SINGLE_CHILD_TAG))
38 #define SINGLE_CHILD_P(x) (((uintptr_t)x) & SINGLE_CHILD_TAG)
39 #define SINGLE_CHILD(x) (rb_shape_t *)((uintptr_t)x & SINGLE_CHILD_MASK)
40 #define ANCESTOR_CACHE_THRESHOLD 10
41 #define MAX_SHAPE_ID (SHAPE_BUFFER_SIZE - 1)
42 #define ANCESTOR_SEARCH_MAX_DEPTH 2
45 static ID id_t_object
;
51 static redblack_node_t
*
52 redblack_left(redblack_node_t
* node
)
54 if (node
->l
== LEAF
) {
58 RUBY_ASSERT(node
->l
< GET_SHAPE_TREE()->cache_size
);
59 redblack_node_t
* left
= &GET_SHAPE_TREE()->shape_cache
[node
->l
- 1];
64 static redblack_node_t
*
65 redblack_right(redblack_node_t
* node
)
67 if (node
->r
== LEAF
) {
71 RUBY_ASSERT(node
->r
< GET_SHAPE_TREE()->cache_size
);
72 redblack_node_t
* right
= &GET_SHAPE_TREE()->shape_cache
[node
->r
- 1];
77 static redblack_node_t
*
78 redblack_find(redblack_node_t
* tree
, ID key
)
84 RUBY_ASSERT(redblack_left(tree
) == LEAF
|| redblack_left(tree
)->key
< tree
->key
);
85 RUBY_ASSERT(redblack_right(tree
) == LEAF
|| redblack_right(tree
)->key
> tree
->key
);
87 if (tree
->key
== key
) {
91 if (key
< tree
->key
) {
92 return redblack_find(redblack_left(tree
), key
);
95 return redblack_find(redblack_right(tree
), key
);
102 redblack_color(redblack_node_t
* node
)
104 return node
&& ((uintptr_t)node
->value
& RED
);
108 redblack_red_p(redblack_node_t
* node
)
110 return redblack_color(node
) == RED
;
113 static inline rb_shape_t
*
114 redblack_value(redblack_node_t
* node
)
116 // Color is stored in the bottom bit of the shape pointer
117 // Mask away the bit so we get the actual pointer back
118 return (rb_shape_t
*)((uintptr_t)node
->value
& (((uintptr_t)-1) - 1));
123 redblack_id_for(redblack_node_t
* node
)
125 RUBY_ASSERT(node
|| node
== LEAF
);
130 redblack_node_t
* redblack_nodes
= GET_SHAPE_TREE()->shape_cache
;
131 redblack_id_t id
= (redblack_id_t
)(node
- redblack_nodes
);
136 static redblack_node_t
*
137 redblack_new(char color
, ID key
, rb_shape_t
* value
, redblack_node_t
* left
, redblack_node_t
* right
)
139 if (GET_SHAPE_TREE()->cache_size
+ 1 >= REDBLACK_CACHE_SIZE
) {
140 // We're out of cache, just quit
144 RUBY_ASSERT(left
== LEAF
|| left
->key
< key
);
145 RUBY_ASSERT(right
== LEAF
|| right
->key
> key
);
147 redblack_node_t
* redblack_nodes
= GET_SHAPE_TREE()->shape_cache
;
148 redblack_node_t
* node
= &redblack_nodes
[(GET_SHAPE_TREE()->cache_size
)++];
150 node
->value
= (rb_shape_t
*)((uintptr_t)value
| color
);
151 node
->l
= redblack_id_for(left
);
152 node
->r
= redblack_id_for(right
);
156 static redblack_node_t
*
157 redblack_balance(char color
, ID key
, rb_shape_t
* value
, redblack_node_t
* left
, redblack_node_t
* right
)
159 if (color
== BLACK
) {
160 ID new_key
, new_left_key
, new_right_key
;
161 rb_shape_t
*new_value
, *new_left_value
, *new_right_value
;
162 redblack_node_t
*new_left_left
, *new_left_right
, *new_right_left
, *new_right_right
;
164 if (redblack_red_p(left
) && redblack_red_p(redblack_left(left
))) {
166 new_right_value
= value
;
167 new_right_right
= right
;
170 new_value
= redblack_value(left
);
171 new_right_left
= redblack_right(left
);
173 new_left_key
= redblack_left(left
)->key
;
174 new_left_value
= redblack_value(redblack_left(left
));
176 new_left_left
= redblack_left(redblack_left(left
));
177 new_left_right
= redblack_right(redblack_left(left
));
179 else if (redblack_red_p(left
) && redblack_red_p(redblack_right(left
))) {
181 new_right_value
= value
;
182 new_right_right
= right
;
184 new_left_key
= left
->key
;
185 new_left_value
= redblack_value(left
);
186 new_left_left
= redblack_left(left
);
188 new_key
= redblack_right(left
)->key
;
189 new_value
= redblack_value(redblack_right(left
));
190 new_left_right
= redblack_left(redblack_right(left
));
191 new_right_left
= redblack_right(redblack_right(left
));
193 else if (redblack_red_p(right
) && redblack_red_p(redblack_left(right
))) {
195 new_left_value
= value
;
196 new_left_left
= left
;
198 new_right_key
= right
->key
;
199 new_right_value
= redblack_value(right
);
200 new_right_right
= redblack_right(right
);
202 new_key
= redblack_left(right
)->key
;
203 new_value
= redblack_value(redblack_left(right
));
204 new_left_right
= redblack_left(redblack_left(right
));
205 new_right_left
= redblack_right(redblack_left(right
));
207 else if (redblack_red_p(right
) && redblack_red_p(redblack_right(right
))) {
209 new_left_value
= value
;
210 new_left_left
= left
;
212 new_key
= right
->key
;
213 new_value
= redblack_value(right
);
214 new_left_right
= redblack_left(right
);
216 new_right_key
= redblack_right(right
)->key
;
217 new_right_value
= redblack_value(redblack_right(right
));
218 new_right_left
= redblack_left(redblack_right(right
));
219 new_right_right
= redblack_right(redblack_right(right
));
222 return redblack_new(color
, key
, value
, left
, right
);
225 RUBY_ASSERT(new_left_key
< new_key
);
226 RUBY_ASSERT(new_right_key
> new_key
);
227 RUBY_ASSERT(new_left_left
== LEAF
|| new_left_left
->key
< new_left_key
);
228 RUBY_ASSERT(new_left_right
== LEAF
|| new_left_right
->key
> new_left_key
);
229 RUBY_ASSERT(new_left_right
== LEAF
|| new_left_right
->key
< new_key
);
230 RUBY_ASSERT(new_right_left
== LEAF
|| new_right_left
->key
< new_right_key
);
231 RUBY_ASSERT(new_right_left
== LEAF
|| new_right_left
->key
> new_key
);
232 RUBY_ASSERT(new_right_right
== LEAF
|| new_right_right
->key
> new_right_key
);
235 RED
, new_key
, new_value
,
236 redblack_new(BLACK
, new_left_key
, new_left_value
, new_left_left
, new_left_right
),
237 redblack_new(BLACK
, new_right_key
, new_right_value
, new_right_left
, new_right_right
));
240 return redblack_new(color
, key
, value
, left
, right
);
243 static redblack_node_t
*
244 redblack_insert_aux(redblack_node_t
* tree
, ID key
, rb_shape_t
* value
)
247 return redblack_new(RED
, key
, value
, LEAF
, LEAF
);
250 redblack_node_t
*left
, *right
;
251 if (key
< tree
->key
) {
252 left
= redblack_insert_aux(redblack_left(tree
), key
, value
);
253 RUBY_ASSERT(left
!= LEAF
);
254 right
= redblack_right(tree
);
255 RUBY_ASSERT(right
== LEAF
|| right
->key
> tree
->key
);
257 else if (key
> tree
->key
) {
258 left
= redblack_left(tree
);
259 RUBY_ASSERT(left
== LEAF
|| left
->key
< tree
->key
);
260 right
= redblack_insert_aux(redblack_right(tree
), key
, value
);
261 RUBY_ASSERT(right
!= LEAF
);
267 return redblack_balance(
268 redblack_color(tree
),
270 redblack_value(tree
),
277 static redblack_node_t
*
278 redblack_force_black(redblack_node_t
* node
)
280 node
->value
= redblack_value(node
);
284 static redblack_node_t
*
285 redblack_insert(redblack_node_t
* tree
, ID key
, rb_shape_t
* value
)
287 redblack_node_t
* root
= redblack_insert_aux(tree
, key
, value
);
289 if (redblack_red_p(root
)) {
290 return redblack_force_black(root
);
298 rb_shape_tree_t
*rb_shape_tree_ptr
= NULL
;
304 rb_shape_get_root_shape(void)
306 return GET_SHAPE_TREE()->root_shape
;
310 rb_shape_id(rb_shape_t
* shape
)
312 return (shape_id_t
)(shape
- GET_SHAPE_TREE()->shape_list
);
316 rb_shape_each_shape(each_shape_callback callback
, void *data
)
318 rb_shape_t
*cursor
= rb_shape_get_root_shape();
319 rb_shape_t
*end
= rb_shape_get_shape_by_id(GET_SHAPE_TREE()->next_shape_id
);
320 while (cursor
< end
) {
321 callback(cursor
, data
);
326 RUBY_FUNC_EXPORTED rb_shape_t
*
327 rb_shape_get_shape_by_id(shape_id_t shape_id
)
329 RUBY_ASSERT(shape_id
!= INVALID_SHAPE_ID
);
331 rb_shape_t
*shape
= &GET_SHAPE_TREE()->shape_list
[shape_id
];
336 rb_shape_get_parent(rb_shape_t
* shape
)
338 return rb_shape_get_shape_by_id(shape
->parent_id
);
341 #if !SHAPE_IN_BASIC_FLAGS
342 shape_id_t
rb_generic_shape_id(VALUE obj
);
345 RUBY_FUNC_EXPORTED shape_id_t
346 rb_shape_get_shape_id(VALUE obj
)
348 if (RB_SPECIAL_CONST_P(obj
)) {
349 return SPECIAL_CONST_SHAPE_ID
;
352 #if SHAPE_IN_BASIC_FLAGS
353 return RBASIC_SHAPE_ID(obj
);
355 switch (BUILTIN_TYPE(obj
)) {
357 return ROBJECT_SHAPE_ID(obj
);
361 return RCLASS_SHAPE_ID(obj
);
363 return rb_generic_shape_id(obj
);
369 rb_shape_depth(rb_shape_t
* shape
)
373 while (shape
->parent_id
!= INVALID_SHAPE_ID
) {
375 shape
= rb_shape_get_parent(shape
);
382 rb_shape_get_shape(VALUE obj
)
384 return rb_shape_get_shape_by_id(rb_shape_get_shape_id(obj
));
390 shape_id_t shape_id
= GET_SHAPE_TREE()->next_shape_id
;
391 GET_SHAPE_TREE()->next_shape_id
++;
393 if (shape_id
== (MAX_SHAPE_ID
+ 1)) {
394 // TODO: Make an OutOfShapesError ??
395 rb_bug("Out of shapes");
398 return &GET_SHAPE_TREE()->shape_list
[shape_id
];
402 rb_shape_alloc_with_parent_id(ID edge_name
, shape_id_t parent_id
)
404 rb_shape_t
* shape
= shape_alloc();
406 shape
->edge_name
= edge_name
;
407 shape
->next_iv_index
= 0;
408 shape
->parent_id
= parent_id
;
415 rb_shape_alloc(ID edge_name
, rb_shape_t
* parent
, enum shape_type type
)
417 rb_shape_t
* shape
= rb_shape_alloc_with_parent_id(edge_name
, rb_shape_id(parent
));
418 shape
->type
= (uint8_t)type
;
419 shape
->size_pool_index
= parent
->size_pool_index
;
420 shape
->capacity
= parent
->capacity
;
426 static redblack_node_t
*
427 redblack_cache_ancestors(rb_shape_t
* shape
)
429 if (!(shape
->ancestor_index
|| shape
->parent_id
== INVALID_SHAPE_ID
)) {
430 redblack_node_t
* parent_index
;
432 parent_index
= redblack_cache_ancestors(rb_shape_get_parent(shape
));
434 if (shape
->type
== SHAPE_IVAR
) {
435 shape
->ancestor_index
= redblack_insert(parent_index
, shape
->edge_name
, shape
);
438 if (shape
->ancestor_index
) {
439 redblack_node_t
*inserted_node
= redblack_find(shape
->ancestor_index
, shape
->edge_name
);
440 RUBY_ASSERT(inserted_node
);
441 RUBY_ASSERT(redblack_value(inserted_node
) == shape
);
446 shape
->ancestor_index
= parent_index
;
450 return shape
->ancestor_index
;
453 static redblack_node_t
*
454 redblack_cache_ancestors(rb_shape_t
* shape
)
461 rb_shape_alloc_new_child(ID id
, rb_shape_t
* shape
, enum shape_type shape_type
)
463 rb_shape_t
* new_shape
= rb_shape_alloc(id
, shape
, shape_type
);
465 switch (shape_type
) {
467 if (UNLIKELY(shape
->next_iv_index
>= shape
->capacity
)) {
468 RUBY_ASSERT(shape
->next_iv_index
== shape
->capacity
);
469 new_shape
->capacity
= (uint32_t)rb_malloc_grow_capa(shape
->capacity
, sizeof(VALUE
));
471 RUBY_ASSERT(new_shape
->capacity
> shape
->next_iv_index
);
472 new_shape
->next_iv_index
= shape
->next_iv_index
+ 1;
473 if (new_shape
->next_iv_index
> ANCESTOR_CACHE_THRESHOLD
) {
474 redblack_cache_ancestors(new_shape
);
478 new_shape
->next_iv_index
= shape
->next_iv_index
;
480 case SHAPE_OBJ_TOO_COMPLEX
:
483 rb_bug("Unreachable");
491 get_next_shape_internal(rb_shape_t
* shape
, ID id
, enum shape_type shape_type
, bool * variation_created
, bool new_variations_allowed
)
493 rb_shape_t
*res
= NULL
;
495 // There should never be outgoing edges from "too complex"
496 RUBY_ASSERT(rb_shape_id(shape
) != OBJ_TOO_COMPLEX_SHAPE_ID
);
498 *variation_created
= false;
502 // If the current shape has children
504 // Check if it only has one child
505 if (SINGLE_CHILD_P(shape
->edges
)) {
506 rb_shape_t
* child
= SINGLE_CHILD(shape
->edges
);
507 // If the one child has a matching edge name, then great,
508 // we found what we want.
509 if (child
->edge_name
== id
) {
514 // If it has more than one child, do a hash lookup to find it.
516 if (rb_id_table_lookup(shape
->edges
, id
, &lookup_result
)) {
517 res
= (rb_shape_t
*)lookup_result
;
522 // If we didn't find the shape we're looking for we create it.
524 // If we're not allowed to create a new variation, of if we're out of shapes
525 // we return TOO_COMPLEX_SHAPE.
526 if (!new_variations_allowed
|| GET_SHAPE_TREE()->next_shape_id
> MAX_SHAPE_ID
) {
527 res
= rb_shape_get_shape_by_id(OBJ_TOO_COMPLEX_SHAPE_ID
);
530 rb_shape_t
* new_shape
= rb_shape_alloc_new_child(id
, shape
, shape_type
);
533 // If the shape had no edge yet, we can directly set the new child
534 shape
->edges
= TAG_SINGLE_CHILD(new_shape
);
537 // If the edge was single child we need to allocate a table.
538 if (SINGLE_CHILD_P(shape
->edges
)) {
539 rb_shape_t
* old_child
= SINGLE_CHILD(shape
->edges
);
540 shape
->edges
= rb_id_table_create(2);
541 rb_id_table_insert(shape
->edges
, old_child
->edge_name
, (VALUE
)old_child
);
544 rb_id_table_insert(shape
->edges
, new_shape
->edge_name
, (VALUE
)new_shape
);
545 *variation_created
= true;
558 rb_shape_frozen_shape_p(rb_shape_t
* shape
)
560 return SHAPE_FROZEN
== (enum shape_type
)shape
->type
;
564 remove_shape_recursive(rb_shape_t
*shape
, ID id
, rb_shape_t
**removed_shape
)
566 if (shape
->parent_id
== INVALID_SHAPE_ID
) {
567 // We've hit the top of the shape tree and couldn't find the
568 // IV we wanted to remove, so return NULL
572 if (shape
->type
== SHAPE_IVAR
&& shape
->edge_name
== id
) {
573 *removed_shape
= shape
;
575 return rb_shape_get_parent(shape
);
578 // This isn't the IV we want to remove, keep walking up.
579 rb_shape_t
*new_parent
= remove_shape_recursive(rb_shape_get_parent(shape
), id
, removed_shape
);
581 // We found a new parent. Create a child of the new parent that
582 // has the same attributes as this shape.
584 if (UNLIKELY(new_parent
->type
== SHAPE_OBJ_TOO_COMPLEX
)) {
589 rb_shape_t
*new_child
= get_next_shape_internal(new_parent
, shape
->edge_name
, shape
->type
, &dont_care
, true);
590 if (UNLIKELY(new_child
->type
== SHAPE_OBJ_TOO_COMPLEX
)) {
594 RUBY_ASSERT(new_child
->capacity
<= shape
->capacity
);
599 // We went all the way to the top of the shape tree and couldn't
600 // find an IV to remove, so return NULL
608 rb_shape_transition_shape_remove_ivar(VALUE obj
, ID id
, rb_shape_t
*shape
, VALUE
*removed
)
610 if (UNLIKELY(shape
->type
== SHAPE_OBJ_TOO_COMPLEX
)) {
614 rb_shape_t
*removed_shape
= NULL
;
615 rb_shape_t
*new_shape
= remove_shape_recursive(shape
, id
, &removed_shape
);
617 RUBY_ASSERT(removed_shape
!= NULL
);
619 if (UNLIKELY(new_shape
->type
== SHAPE_OBJ_TOO_COMPLEX
)) {
623 RUBY_ASSERT(new_shape
->next_iv_index
== shape
->next_iv_index
- 1);
626 switch(BUILTIN_TYPE(obj
)) {
629 ivptr
= RCLASS_IVPTR(obj
);
632 ivptr
= ROBJECT_IVPTR(obj
);
635 struct gen_ivtbl
*ivtbl
;
636 rb_gen_ivtbl_get(obj
, id
, &ivtbl
);
637 ivptr
= ivtbl
->as
.shape
.ivptr
;
642 *removed
= ivptr
[removed_shape
->next_iv_index
- 1];
644 memmove(&ivptr
[removed_shape
->next_iv_index
- 1], &ivptr
[removed_shape
->next_iv_index
],
645 ((new_shape
->next_iv_index
+ 1) - removed_shape
->next_iv_index
) * sizeof(VALUE
));
647 // Re-embed objects when instances become small enough
648 // This is necessary because YJIT assumes that objects with the same shape
649 // have the same embeddedness for efficiency (avoid extra checks)
650 if (BUILTIN_TYPE(obj
) == T_OBJECT
&&
651 !RB_FL_TEST_RAW(obj
, ROBJECT_EMBED
) &&
652 rb_obj_embedded_size(new_shape
->next_iv_index
) <= rb_gc_obj_slot_size(obj
)) {
653 RB_FL_SET_RAW(obj
, ROBJECT_EMBED
);
654 memcpy(ROBJECT_IVPTR(obj
), ivptr
, new_shape
->next_iv_index
* sizeof(VALUE
));
658 rb_shape_set_shape(obj
, new_shape
);
664 rb_shape_transition_shape_frozen(VALUE obj
)
666 rb_shape_t
* shape
= rb_shape_get_shape(obj
);
668 RUBY_ASSERT(RB_OBJ_FROZEN(obj
));
670 if (rb_shape_frozen_shape_p(shape
) || rb_shape_obj_too_complex(obj
)) {
674 rb_shape_t
* next_shape
;
676 if (shape
== rb_shape_get_root_shape()) {
677 return rb_shape_get_shape_by_id(SPECIAL_CONST_SHAPE_ID
);
681 next_shape
= get_next_shape_internal(shape
, (ID
)id_frozen
, SHAPE_FROZEN
, &dont_care
, true);
683 RUBY_ASSERT(next_shape
);
688 * This function is used for assertions where we don't want to increment
692 rb_shape_get_next_iv_shape(rb_shape_t
* shape
, ID id
)
694 RUBY_ASSERT(!is_instance_id(id
) || RTEST(rb_sym2str(ID2SYM(id
))));
696 return get_next_shape_internal(shape
, id
, SHAPE_IVAR
, &dont_care
, true);
699 static inline rb_shape_t
*
700 shape_get_next(rb_shape_t
*shape
, VALUE obj
, ID id
, bool emit_warnings
)
702 RUBY_ASSERT(!is_instance_id(id
) || RTEST(rb_sym2str(ID2SYM(id
))));
703 if (UNLIKELY(shape
->type
== SHAPE_OBJ_TOO_COMPLEX
)) {
709 if (rb_shape_get_iv_index(shape
, id
, &index
)) {
710 rb_bug("rb_shape_get_next: trying to create ivar that already exists at index %u", index
);
714 bool allow_new_shape
= true;
716 if (BUILTIN_TYPE(obj
) == T_OBJECT
) {
717 VALUE klass
= rb_obj_class(obj
);
718 allow_new_shape
= RCLASS_EXT(klass
)->variation_count
< SHAPE_MAX_VARIATIONS
;
721 bool variation_created
= false;
722 rb_shape_t
*new_shape
= get_next_shape_internal(shape
, id
, SHAPE_IVAR
, &variation_created
, allow_new_shape
);
724 // Check if we should update max_iv_count on the object's class
725 if (BUILTIN_TYPE(obj
) == T_OBJECT
) {
726 VALUE klass
= rb_obj_class(obj
);
727 if (new_shape
->next_iv_index
> RCLASS_EXT(klass
)->max_iv_count
) {
728 RCLASS_EXT(klass
)->max_iv_count
= new_shape
->next_iv_index
;
731 if (variation_created
) {
732 RCLASS_EXT(klass
)->variation_count
++;
733 if (emit_warnings
&& rb_warning_category_enabled_p(RB_WARN_CATEGORY_PERFORMANCE
)) {
734 if (RCLASS_EXT(klass
)->variation_count
>= SHAPE_MAX_VARIATIONS
) {
736 RB_WARN_CATEGORY_PERFORMANCE
,
737 "The class %"PRIsVALUE
" reached %d shape variations, instance variables accesses will be slower and memory usage increased.\n"
738 "It is recommended to define instance variables in a consistent order, for instance by eagerly defining them all in the #initialize method.",
739 rb_class_path(klass
),
751 rb_shape_get_next(rb_shape_t
*shape
, VALUE obj
, ID id
)
753 return shape_get_next(shape
, obj
, id
, true);
757 rb_shape_get_next_no_warnings(rb_shape_t
*shape
, VALUE obj
, ID id
)
759 return shape_get_next(shape
, obj
, id
, false);
762 // Same as rb_shape_get_iv_index, but uses a provided valid shape id and index
763 // to return a result faster if branches of the shape tree are closely related.
765 rb_shape_get_iv_index_with_hint(shape_id_t shape_id
, ID id
, attr_index_t
*value
, shape_id_t
*shape_id_hint
)
767 attr_index_t index_hint
= *value
;
768 rb_shape_t
*shape
= rb_shape_get_shape_by_id(shape_id
);
769 rb_shape_t
*initial_shape
= shape
;
771 if (*shape_id_hint
== INVALID_SHAPE_ID
) {
772 *shape_id_hint
= shape_id
;
773 return rb_shape_get_iv_index(shape
, id
, value
);
776 rb_shape_t
* shape_hint
= rb_shape_get_shape_by_id(*shape_id_hint
);
778 // We assume it's likely shape_id_hint and shape_id have a close common
779 // ancestor, so we check up to ANCESTOR_SEARCH_MAX_DEPTH ancestors before
780 // eventually using the index, as in case of a match it will be faster.
781 // However if the shape doesn't have an index, we walk the entire tree.
783 if (shape
->ancestor_index
&& shape
->next_iv_index
>= ANCESTOR_CACHE_THRESHOLD
) {
784 depth
= ANCESTOR_SEARCH_MAX_DEPTH
;
787 while (depth
> 0 && shape
->next_iv_index
> index_hint
) {
788 while (shape_hint
->next_iv_index
> shape
->next_iv_index
) {
789 shape_hint
= rb_shape_get_parent(shape_hint
);
792 if (shape_hint
== shape
) {
793 // We've found a common ancestor so use the index hint
795 *shape_id_hint
= rb_shape_id(shape
);
798 if (shape
->edge_name
== id
) {
799 // We found the matching id before a common ancestor
800 *value
= shape
->next_iv_index
- 1;
801 *shape_id_hint
= rb_shape_id(shape
);
805 shape
= rb_shape_get_parent(shape
);
809 // If the original shape had an index but its ancestor doesn't
810 // we switch back to the original one as it will be faster.
811 if (!shape
->ancestor_index
&& initial_shape
->ancestor_index
) {
812 shape
= initial_shape
;
814 *shape_id_hint
= shape_id
;
815 return rb_shape_get_iv_index(shape
, id
, value
);
819 shape_get_iv_index(rb_shape_t
*shape
, ID id
, attr_index_t
*value
)
821 while (shape
->parent_id
!= INVALID_SHAPE_ID
) {
822 if (shape
->edge_name
== id
) {
823 enum shape_type shape_type
;
824 shape_type
= (enum shape_type
)shape
->type
;
826 switch (shape_type
) {
828 RUBY_ASSERT(shape
->next_iv_index
> 0);
829 *value
= shape
->next_iv_index
- 1;
834 case SHAPE_OBJ_TOO_COMPLEX
:
836 rb_bug("Ivar should not exist on transition");
840 shape
= rb_shape_get_parent(shape
);
847 shape_cache_get_iv_index(rb_shape_t
*shape
, ID id
, attr_index_t
*value
)
849 if (shape
->ancestor_index
&& shape
->next_iv_index
>= ANCESTOR_CACHE_THRESHOLD
) {
850 redblack_node_t
*node
= redblack_find(shape
->ancestor_index
, id
);
852 rb_shape_t
*shape
= redblack_value(node
);
853 *value
= shape
->next_iv_index
- 1;
856 attr_index_t shape_tree_index
;
857 RUBY_ASSERT(shape_get_iv_index(shape
, id
, &shape_tree_index
));
858 RUBY_ASSERT(shape_tree_index
== *value
);
864 /* Verify the cache is correct by checking that this instance variable
865 * does not exist in the shape tree either. */
866 RUBY_ASSERT(!shape_get_iv_index(shape
, id
, value
));
873 rb_shape_get_iv_index(rb_shape_t
*shape
, ID id
, attr_index_t
*value
)
875 // It doesn't make sense to ask for the index of an IV that's stored
876 // on an object that is "too complex" as it uses a hash for storing IVs
877 RUBY_ASSERT(rb_shape_id(shape
) != OBJ_TOO_COMPLEX_SHAPE_ID
);
879 if (!shape_cache_get_iv_index(shape
, id
, value
)) {
880 // If it wasn't in the ancestor cache, then don't do a linear search
881 if (shape
->ancestor_index
&& shape
->next_iv_index
>= ANCESTOR_CACHE_THRESHOLD
) {
885 return shape_get_iv_index(shape
, id
, value
);
893 rb_shape_set_shape(VALUE obj
, rb_shape_t
* shape
)
895 rb_shape_set_shape_id(obj
, rb_shape_id(shape
));
899 rb_shape_id_offset(void)
901 return sizeof(uintptr_t) - SHAPE_ID_NUM_BITS
/ sizeof(uintptr_t);
905 rb_shape_traverse_from_new_root(rb_shape_t
*initial_shape
, rb_shape_t
*dest_shape
)
907 RUBY_ASSERT(initial_shape
->type
== SHAPE_T_OBJECT
);
908 rb_shape_t
*next_shape
= initial_shape
;
910 if (dest_shape
->type
!= initial_shape
->type
) {
911 next_shape
= rb_shape_traverse_from_new_root(initial_shape
, rb_shape_get_parent(dest_shape
));
917 switch ((enum shape_type
)dest_shape
->type
) {
920 if (!next_shape
->edges
) {
925 if (SINGLE_CHILD_P(next_shape
->edges
)) {
926 rb_shape_t
* child
= SINGLE_CHILD(next_shape
->edges
);
927 if (child
->edge_name
== dest_shape
->edge_name
) {
935 if (rb_id_table_lookup(next_shape
->edges
, dest_shape
->edge_name
, &lookup_result
)) {
936 next_shape
= (rb_shape_t
*)lookup_result
;
946 case SHAPE_OBJ_TOO_COMPLEX
:
947 rb_bug("Unreachable");
955 rb_shape_rebuild_shape(rb_shape_t
* initial_shape
, rb_shape_t
* dest_shape
)
957 RUBY_ASSERT(rb_shape_id(initial_shape
) != OBJ_TOO_COMPLEX_SHAPE_ID
);
958 RUBY_ASSERT(rb_shape_id(dest_shape
) != OBJ_TOO_COMPLEX_SHAPE_ID
);
960 rb_shape_t
* midway_shape
;
962 RUBY_ASSERT(initial_shape
->type
== SHAPE_T_OBJECT
);
964 if (dest_shape
->type
!= initial_shape
->type
) {
965 midway_shape
= rb_shape_rebuild_shape(initial_shape
, rb_shape_get_parent(dest_shape
));
966 if (UNLIKELY(rb_shape_id(midway_shape
) == OBJ_TOO_COMPLEX_SHAPE_ID
)) {
971 midway_shape
= initial_shape
;
974 switch ((enum shape_type
)dest_shape
->type
) {
976 midway_shape
= rb_shape_get_next_iv_shape(midway_shape
, dest_shape
->edge_name
);
982 case SHAPE_OBJ_TOO_COMPLEX
:
983 rb_bug("Unreachable");
990 RUBY_FUNC_EXPORTED
bool
991 rb_shape_obj_too_complex(VALUE obj
)
993 return rb_shape_get_shape_id(obj
) == OBJ_TOO_COMPLEX_SHAPE_ID
;
997 rb_shape_edges_count(rb_shape_t
*shape
)
1000 if (SINGLE_CHILD_P(shape
->edges
)) {
1004 return rb_id_table_size(shape
->edges
);
1011 rb_shape_memsize(rb_shape_t
*shape
)
1013 size_t memsize
= sizeof(rb_shape_t
);
1014 if (shape
->edges
&& !SINGLE_CHILD_P(shape
->edges
)) {
1015 memsize
+= rb_id_table_memsize(shape
->edges
);
1022 * Exposing Shape to Ruby via RubyVM.debug_shape
1027 rb_shape_too_complex(VALUE self
)
1030 shape
= rb_shape_get_shape_by_id(NUM2INT(rb_struct_getmember(self
, rb_intern("id"))));
1031 if (rb_shape_id(shape
) == OBJ_TOO_COMPLEX_SHAPE_ID
) {
1042 if (is_instance_id(key
)) {
1045 return LONG2NUM(key
);
1048 static VALUE
rb_shape_edge_name(rb_shape_t
* shape
);
1051 rb_shape_t_to_rb_cShape(rb_shape_t
*shape
)
1053 VALUE rb_cShape
= rb_const_get(rb_cRubyVM
, rb_intern("Shape"));
1055 VALUE obj
= rb_struct_new(rb_cShape
,
1056 INT2NUM(rb_shape_id(shape
)),
1057 INT2NUM(shape
->parent_id
),
1058 rb_shape_edge_name(shape
),
1059 INT2NUM(shape
->next_iv_index
),
1060 INT2NUM(shape
->size_pool_index
),
1061 INT2NUM(shape
->type
),
1062 INT2NUM(shape
->capacity
));
1067 static enum rb_id_table_iterator_result
1068 rb_edges_to_hash(ID key
, VALUE value
, void *ref
)
1070 rb_hash_aset(*(VALUE
*)ref
, parse_key(key
), rb_shape_t_to_rb_cShape((rb_shape_t
*)value
));
1071 return ID_TABLE_CONTINUE
;
1076 rb_shape_edges(VALUE self
)
1080 shape
= rb_shape_get_shape_by_id(NUM2INT(rb_struct_getmember(self
, rb_intern("id"))));
1082 VALUE hash
= rb_hash_new();
1085 if (SINGLE_CHILD_P(shape
->edges
)) {
1086 rb_shape_t
* child
= SINGLE_CHILD(shape
->edges
);
1087 rb_edges_to_hash(child
->edge_name
, (VALUE
)child
, &hash
);
1090 rb_id_table_foreach(shape
->edges
, rb_edges_to_hash
, &hash
);
1098 rb_shape_edge_name(rb_shape_t
* shape
)
1100 if (shape
->edge_name
) {
1101 if (is_instance_id(shape
->edge_name
)) {
1102 return ID2SYM(shape
->edge_name
);
1104 return INT2NUM(shape
->capacity
);
1111 rb_shape_export_depth(VALUE self
)
1114 shape
= rb_shape_get_shape_by_id(NUM2INT(rb_struct_getmember(self
, rb_intern("id"))));
1115 return SIZET2NUM(rb_shape_depth(shape
));
1120 rb_shape_parent(VALUE self
)
1123 shape
= rb_shape_get_shape_by_id(NUM2INT(rb_struct_getmember(self
, rb_intern("id"))));
1124 if (shape
->parent_id
!= INVALID_SHAPE_ID
) {
1125 return rb_shape_t_to_rb_cShape(rb_shape_get_parent(shape
));
1134 rb_shape_debug_shape(VALUE self
, VALUE obj
)
1136 return rb_shape_t_to_rb_cShape(rb_shape_get_shape(obj
));
1141 rb_shape_root_shape(VALUE self
)
1143 return rb_shape_t_to_rb_cShape(rb_shape_get_root_shape());
1148 rb_shape_shapes_available(VALUE self
)
1150 return INT2NUM(MAX_SHAPE_ID
- (GET_SHAPE_TREE()->next_shape_id
- 1));
1155 rb_shape_exhaust(int argc
, VALUE
*argv
, VALUE self
)
1157 rb_check_arity(argc
, 0, 1);
1158 int offset
= argc
== 1 ? NUM2INT(argv
[0]) : 0;
1159 GET_SHAPE_TREE()->next_shape_id
= MAX_SHAPE_ID
- offset
+ 1;
1163 VALUE
rb_obj_shape(rb_shape_t
* shape
);
1165 static enum rb_id_table_iterator_result
collect_keys_and_values(ID key
, VALUE value
, void *ref
)
1167 rb_hash_aset(*(VALUE
*)ref
, parse_key(key
), rb_obj_shape((rb_shape_t
*)value
));
1168 return ID_TABLE_CONTINUE
;
1171 static VALUE
edges(struct rb_id_table
* edges
)
1173 VALUE hash
= rb_hash_new();
1174 if (SINGLE_CHILD_P(edges
)) {
1175 rb_shape_t
* child
= SINGLE_CHILD(edges
);
1176 collect_keys_and_values(child
->edge_name
, (VALUE
)child
, &hash
);
1179 rb_id_table_foreach(edges
, collect_keys_and_values
, &hash
);
1186 rb_obj_shape(rb_shape_t
* shape
)
1188 VALUE rb_shape
= rb_hash_new();
1190 rb_hash_aset(rb_shape
, ID2SYM(rb_intern("id")), INT2NUM(rb_shape_id(shape
)));
1191 rb_hash_aset(rb_shape
, ID2SYM(rb_intern("edges")), edges(shape
->edges
));
1193 if (shape
== rb_shape_get_root_shape()) {
1194 rb_hash_aset(rb_shape
, ID2SYM(rb_intern("parent_id")), INT2NUM(ROOT_SHAPE_ID
));
1197 rb_hash_aset(rb_shape
, ID2SYM(rb_intern("parent_id")), INT2NUM(shape
->parent_id
));
1200 rb_hash_aset(rb_shape
, ID2SYM(rb_intern("edge_name")), rb_id2str(shape
->edge_name
));
1206 shape_transition_tree(VALUE self
)
1208 return rb_obj_shape(rb_shape_get_root_shape());
1213 rb_shape_find_by_id(VALUE mod
, VALUE id
)
1215 shape_id_t shape_id
= NUM2UINT(id
);
1216 if (shape_id
>= GET_SHAPE_TREE()->next_shape_id
) {
1217 rb_raise(rb_eArgError
, "Shape ID %d is out of bounds\n", shape_id
);
1219 return rb_shape_t_to_rb_cShape(rb_shape_get_shape_by_id(shape_id
));
1224 #include <sys/mman.h>
1228 Init_default_shapes(void)
1230 rb_shape_tree_ptr
= xcalloc(1, sizeof(rb_shape_tree_t
));
1233 rb_shape_tree_ptr
->shape_list
= (rb_shape_t
*)mmap(NULL
, rb_size_mul_or_raise(SHAPE_BUFFER_SIZE
, sizeof(rb_shape_t
), rb_eRuntimeError
),
1234 PROT_READ
| PROT_WRITE
, MAP_PRIVATE
| MAP_ANONYMOUS
, -1, 0);
1235 if (GET_SHAPE_TREE()->shape_list
== MAP_FAILED
) {
1236 GET_SHAPE_TREE()->shape_list
= 0;
1239 GET_SHAPE_TREE()->shape_list
= xcalloc(SHAPE_BUFFER_SIZE
, sizeof(rb_shape_t
));
1242 if (!GET_SHAPE_TREE()->shape_list
) {
1246 id_frozen
= rb_make_internal_id();
1247 id_t_object
= rb_make_internal_id();
1250 rb_shape_tree_ptr
->shape_cache
= (redblack_node_t
*)mmap(NULL
, rb_size_mul_or_raise(REDBLACK_CACHE_SIZE
, sizeof(redblack_node_t
), rb_eRuntimeError
),
1251 PROT_READ
| PROT_WRITE
, MAP_PRIVATE
| MAP_ANONYMOUS
, -1, 0);
1252 rb_shape_tree_ptr
->cache_size
= 0;
1254 // If mmap fails, then give up on the redblack tree cache.
1255 // We set the cache size such that the redblack node allocators think
1256 // the cache is full.
1257 if (GET_SHAPE_TREE()->shape_cache
== MAP_FAILED
) {
1258 GET_SHAPE_TREE()->shape_cache
= 0;
1259 GET_SHAPE_TREE()->cache_size
= REDBLACK_CACHE_SIZE
;
1264 rb_shape_t
*root
= rb_shape_alloc_with_parent_id(0, INVALID_SHAPE_ID
);
1266 root
->type
= SHAPE_ROOT
;
1267 root
->size_pool_index
= 0;
1268 GET_SHAPE_TREE()->root_shape
= root
;
1269 RUBY_ASSERT(rb_shape_id(GET_SHAPE_TREE()->root_shape
) == ROOT_SHAPE_ID
);
1272 // Special const shape
1274 rb_shape_t
*special_const_shape
=
1276 get_next_shape_internal(root
, (ID
)id_frozen
, SHAPE_FROZEN
, &dont_care
, true);
1277 RUBY_ASSERT(rb_shape_id(special_const_shape
) == SPECIAL_CONST_SHAPE_ID
);
1278 RUBY_ASSERT(SPECIAL_CONST_SHAPE_ID
== (GET_SHAPE_TREE()->next_shape_id
- 1));
1279 RUBY_ASSERT(rb_shape_frozen_shape_p(special_const_shape
));
1281 rb_shape_t
*too_complex_shape
= rb_shape_alloc_with_parent_id(0, ROOT_SHAPE_ID
);
1282 too_complex_shape
->type
= SHAPE_OBJ_TOO_COMPLEX
;
1283 too_complex_shape
->size_pool_index
= 0;
1284 RUBY_ASSERT(OBJ_TOO_COMPLEX_SHAPE_ID
== (GET_SHAPE_TREE()->next_shape_id
- 1));
1285 RUBY_ASSERT(rb_shape_id(too_complex_shape
) == OBJ_TOO_COMPLEX_SHAPE_ID
);
1287 // Make shapes for T_OBJECT
1288 size_t *sizes
= rb_gc_size_pool_sizes();
1289 for (int i
= 0; sizes
[i
] > 0; i
++) {
1290 rb_shape_t
*t_object_shape
= rb_shape_alloc_with_parent_id(0, INVALID_SHAPE_ID
);
1291 t_object_shape
->type
= SHAPE_T_OBJECT
;
1292 t_object_shape
->size_pool_index
= i
;
1293 t_object_shape
->capacity
= (uint32_t)((sizes
[i
] - offsetof(struct RObject
, as
.ary
)) / sizeof(VALUE
));
1294 t_object_shape
->edges
= rb_id_table_create(0);
1295 t_object_shape
->ancestor_index
= LEAF
;
1296 RUBY_ASSERT(rb_shape_id(t_object_shape
) == (shape_id_t
)(i
+ FIRST_T_OBJECT_SHAPE_ID
));
1304 VALUE rb_cShape
= rb_struct_define_under(rb_cRubyVM
, "Shape",
1314 rb_define_method(rb_cShape
, "parent", rb_shape_parent
, 0);
1315 rb_define_method(rb_cShape
, "edges", rb_shape_edges
, 0);
1316 rb_define_method(rb_cShape
, "depth", rb_shape_export_depth
, 0);
1317 rb_define_method(rb_cShape
, "too_complex?", rb_shape_too_complex
, 0);
1318 rb_define_const(rb_cShape
, "SHAPE_ROOT", INT2NUM(SHAPE_ROOT
));
1319 rb_define_const(rb_cShape
, "SHAPE_IVAR", INT2NUM(SHAPE_IVAR
));
1320 rb_define_const(rb_cShape
, "SHAPE_T_OBJECT", INT2NUM(SHAPE_T_OBJECT
));
1321 rb_define_const(rb_cShape
, "SHAPE_FROZEN", INT2NUM(SHAPE_FROZEN
));
1322 rb_define_const(rb_cShape
, "SHAPE_ID_NUM_BITS", INT2NUM(SHAPE_ID_NUM_BITS
));
1323 rb_define_const(rb_cShape
, "SHAPE_FLAG_SHIFT", INT2NUM(SHAPE_FLAG_SHIFT
));
1324 rb_define_const(rb_cShape
, "SPECIAL_CONST_SHAPE_ID", INT2NUM(SPECIAL_CONST_SHAPE_ID
));
1325 rb_define_const(rb_cShape
, "OBJ_TOO_COMPLEX_SHAPE_ID", INT2NUM(OBJ_TOO_COMPLEX_SHAPE_ID
));
1326 rb_define_const(rb_cShape
, "FIRST_T_OBJECT_SHAPE_ID", INT2NUM(FIRST_T_OBJECT_SHAPE_ID
));
1327 rb_define_const(rb_cShape
, "SHAPE_MAX_VARIATIONS", INT2NUM(SHAPE_MAX_VARIATIONS
));
1328 rb_define_const(rb_cShape
, "SIZEOF_RB_SHAPE_T", INT2NUM(sizeof(rb_shape_t
)));
1329 rb_define_const(rb_cShape
, "SIZEOF_REDBLACK_NODE_T", INT2NUM(sizeof(redblack_node_t
)));
1330 rb_define_const(rb_cShape
, "SHAPE_BUFFER_SIZE", INT2NUM(sizeof(rb_shape_t
) * SHAPE_BUFFER_SIZE
));
1331 rb_define_const(rb_cShape
, "REDBLACK_CACHE_SIZE", INT2NUM(sizeof(redblack_node_t
) * REDBLACK_CACHE_SIZE
));
1333 rb_define_singleton_method(rb_cShape
, "transition_tree", shape_transition_tree
, 0);
1334 rb_define_singleton_method(rb_cShape
, "find_by_id", rb_shape_find_by_id
, 1);
1335 rb_define_singleton_method(rb_cShape
, "of", rb_shape_debug_shape
, 1);
1336 rb_define_singleton_method(rb_cShape
, "root_shape", rb_shape_root_shape
, 0);
1337 rb_define_singleton_method(rb_cShape
, "shapes_available", rb_shape_shapes_available
, 0);
1338 rb_define_singleton_method(rb_cShape
, "exhaust_shapes", rb_shape_exhaust
, -1);