Skip to content

Replicate heap_index in shape_id flags. #13546

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 3 commits into from
Closed

Replicate heap_index in shape_id flags. #13546

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
fc9f38c
Replicate `heap_index` in shape_id flags.
byroot Jun 6, 2025
3d8cad4
Leave the shape_id_t highest bit unused to avoid crashing YJIT
byroot Jun 6, 2025
218241b
shape.c: ensure heap_index is consistent for complex shapes
byroot Jun 7, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
shape.c: ensure heap_index is consistent for complex shapes
  • Loading branch information
@byroot
byroot committed Jun 7, 2025
commit 218241b8186e640b9bfb81ac8d2c8c07737d886e
2 changes: 1 addition & 1 deletion internal/variable.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -52,7 +52,7 @@ int rb_gen_fields_tbl_get(VALUE obj, ID id, struct gen_fields_tbl **fields_tbl);
void rb_obj_copy_ivs_to_hash_table(VALUE obj, st_table *table);
void rb_obj_init_too_complex(VALUE obj, st_table *table);
void rb_evict_ivars_to_hash(VALUE obj);
void rb_evict_fields_to_hash(VALUE obj);
shape_id_t rb_evict_fields_to_hash(VALUE obj);
VALUE rb_obj_field_get(VALUE obj, shape_id_t target_shape_id);
void rb_ivar_set_internal(VALUE obj, ID id, VALUE val);
void rb_obj_field_set(VALUE obj, shape_id_t target_shape_id, VALUE val);
Expand Down
146 changes: 96 additions & 50 deletions shape.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -723,15 +723,67 @@ remove_shape_recursive(rb_shape_t *shape, ID id, rb_shape_t **removed_shape)
}
}


static shape_id_t
shape_transition_object_id(shape_id_t original_shape_id)
{
RUBY_ASSERT(!rb_shape_has_object_id(original_shape_id));

bool dont_care;
rb_shape_t *shape = get_next_shape_internal(RSHAPE(original_shape_id), ruby_internal_object_id, SHAPE_OBJ_ID, &dont_care, true);

RUBY_ASSERT(shape);

return shape_id(shape, original_shape_id) | SHAPE_ID_FL_HAS_OBJECT_ID;
}

shape_id_t
rb_shape_transition_object_id(VALUE obj)
{
return shape_transition_object_id(RBASIC_SHAPE_ID(obj));
}

shape_id_t
rb_shape_object_id(shape_id_t original_shape_id)
{
RUBY_ASSERT(rb_shape_has_object_id(original_shape_id));

rb_shape_t *shape = RSHAPE(original_shape_id);
while (shape->type != SHAPE_OBJ_ID) {
if (UNLIKELY(shape->parent_id == INVALID_SHAPE_ID)) {
rb_bug("Missing object_id in shape tree");
}
shape = RSHAPE(shape->parent_id);
}

return shape_id(shape, original_shape_id) | SHAPE_ID_FL_HAS_OBJECT_ID;
}

static inline shape_id_t
transition_complex(shape_id_t shape_id)
{
if (rb_shape_has_object_id(shape_id)) {
return ROOT_TOO_COMPLEX_WITH_OBJ_ID | (shape_id & SHAPE_ID_FLAGS_MASK);
uint8_t heap_index = RSHAPE(shape_id)->heap_index;
shape_id_t next_shape_id;

if (heap_index) {
next_shape_id = rb_shape_root(heap_index - 1) | SHAPE_ID_FL_TOO_COMPLEX;
if (rb_shape_has_object_id(shape_id)) {
next_shape_id = shape_transition_object_id(next_shape_id);
}
}
else {
if (rb_shape_has_object_id(shape_id)) {
next_shape_id = ROOT_TOO_COMPLEX_WITH_OBJ_ID | (shape_id & SHAPE_ID_FLAGS_MASK);
}
else {
next_shape_id = ROOT_TOO_COMPLEX_SHAPE_ID | (shape_id & SHAPE_ID_FLAGS_MASK);
}
}
return ROOT_TOO_COMPLEX_SHAPE_ID | (shape_id & SHAPE_ID_FLAGS_MASK);
}

RUBY_ASSERT(rb_shape_has_object_id(shape_id) == rb_shape_has_object_id(next_shape_id));

return next_shape_id;
}

shape_id_t
rb_shape_transition_remove_ivar(VALUE obj, ID id, shape_id_t *removed_shape_id)
Expand All @@ -754,7 +806,9 @@ rb_shape_transition_remove_ivar(VALUE obj, ID id, shape_id_t *removed_shape_id)
else if (removed_shape) {
// We found the shape to remove, but couldn't create a new variation.
// We must transition to TOO_COMPLEX.
return transition_complex(original_shape_id);
shape_id_t next_shape_id = transition_complex(original_shape_id);
RUBY_ASSERT(rb_shape_has_object_id(next_shape_id) == rb_shape_has_object_id(original_shape_id));
return next_shape_id;
}
return original_shape_id;
}
Expand All @@ -774,41 +828,6 @@ rb_shape_transition_complex(VALUE obj)
return transition_complex(RBASIC_SHAPE_ID(obj));
}

shape_id_t
rb_shape_transition_object_id(VALUE obj)
{
shape_id_t original_shape_id = RBASIC_SHAPE_ID(obj);

RUBY_ASSERT(!rb_shape_has_object_id(original_shape_id));

rb_shape_t *shape = NULL;
if (!rb_shape_too_complex_p(original_shape_id)) {
bool dont_care;
shape = get_next_shape_internal(RSHAPE(original_shape_id), ruby_internal_object_id, SHAPE_OBJ_ID, &dont_care, true);
}

if (!shape) {
shape = RSHAPE(ROOT_TOO_COMPLEX_WITH_OBJ_ID);
}
return shape_id(shape, original_shape_id) | SHAPE_ID_FL_HAS_OBJECT_ID;
}

shape_id_t
rb_shape_object_id(shape_id_t original_shape_id)
{
RUBY_ASSERT(rb_shape_has_object_id(original_shape_id));

rb_shape_t *shape = RSHAPE(original_shape_id);
while (shape->type != SHAPE_OBJ_ID) {
if (UNLIKELY(shape->parent_id == INVALID_SHAPE_ID)) {
rb_bug("Missing object_id in shape tree");
}
shape = RSHAPE(shape->parent_id);
}

return shape_id(shape, original_shape_id) | SHAPE_ID_FL_HAS_OBJECT_ID;
}

/*
* This function is used for assertions where we don't want to increment
* max_iv_count
Expand Down Expand Up @@ -918,7 +937,13 @@ rb_shape_transition_add_ivar(VALUE obj, ID id)
shape_id_t original_shape_id = RBASIC_SHAPE_ID(obj);
RUBY_ASSERT(!shape_frozen_p(original_shape_id));

return shape_id(shape_get_next(RSHAPE(original_shape_id), obj, id, true), original_shape_id);
rb_shape_t *next_shape = shape_get_next(RSHAPE(original_shape_id), obj, id, true);
if (next_shape) {
return shape_id(next_shape, original_shape_id);
}
else {
return transition_complex(original_shape_id);
}
}

shape_id_t
Expand All @@ -927,7 +952,13 @@ rb_shape_transition_add_ivar_no_warnings(VALUE obj, ID id)
shape_id_t original_shape_id = RBASIC_SHAPE_ID(obj);
RUBY_ASSERT(!shape_frozen_p(original_shape_id));

return shape_id(shape_get_next(RSHAPE(original_shape_id), obj, id, false), original_shape_id);
rb_shape_t *next_shape = shape_get_next(RSHAPE(original_shape_id), obj, id, false);
if (next_shape) {
return shape_id(next_shape, original_shape_id);
}
else {
return transition_complex(original_shape_id);
}
}

// Same as rb_shape_get_iv_index, but uses a provided valid shape id and index
Expand Down Expand Up @@ -1139,7 +1170,13 @@ rb_shape_rebuild(shape_id_t initial_shape_id, shape_id_t dest_shape_id)
RUBY_ASSERT(!rb_shape_too_complex_p(initial_shape_id));
RUBY_ASSERT(!rb_shape_too_complex_p(dest_shape_id));

return shape_id(shape_rebuild(RSHAPE(initial_shape_id), RSHAPE(dest_shape_id)), initial_shape_id);
rb_shape_t *next_shape = shape_rebuild(RSHAPE(initial_shape_id), RSHAPE(dest_shape_id));
if (next_shape) {
return shape_id(next_shape, initial_shape_id);
}
else {
return transition_complex(initial_shape_id | (dest_shape_id & SHAPE_ID_FL_HAS_OBJECT_ID));
}
}

void
Expand Down Expand Up @@ -1217,6 +1254,10 @@ rb_shape_memsize(shape_id_t shape_id)
bool
rb_shape_verify_consistency(VALUE obj, shape_id_t shape_id)
{
if (shape_id == INVALID_SHAPE_ID) {
rb_bug("Can't set INVALID_SHAPE_ID on an object");
}

rb_shape_t *shape = RSHAPE(shape_id);

bool has_object_id = false;
Expand All @@ -1241,12 +1282,9 @@ rb_shape_verify_consistency(VALUE obj, shape_id_t shape_id)
}
}

// All complex shape are in heap_index=0, it's a limitation
if (!rb_shape_too_complex_p(shape_id)) {
uint8_t flags_heap_index = rb_shape_heap_index(shape_id);
if (flags_heap_index != shape->heap_index) {
rb_bug("shape_id heap_index flags mismatch: flags=%u, transition=%u\n", flags_heap_index, shape->heap_index);
}
uint8_t flags_heap_index = rb_shape_heap_index(shape_id);
if (flags_heap_index != shape->heap_index) {
rb_bug("shape_id heap_index flags mismatch: flags=%u, transition=%u\n", flags_heap_index, shape->heap_index);
}

return true;
Expand Down Expand Up @@ -1537,7 +1575,8 @@ Init_default_shapes(void)

// Make shapes for T_OBJECT
size_t *sizes = rb_gc_heap_sizes();
for (int i = 0; sizes[i] > 0; i++) {
int i;
for (i = 0; sizes[i] > 0; i++) {
rb_shape_t *t_object_shape = rb_shape_alloc_with_parent_id(0, INVALID_SHAPE_ID);
t_object_shape->type = SHAPE_T_OBJECT;
t_object_shape->heap_index = i + 1;
Expand All @@ -1546,6 +1585,13 @@ Init_default_shapes(void)
t_object_shape->ancestor_index = LEAF;
RUBY_ASSERT(t_object_shape == RSHAPE(rb_shape_root(i)));
}

// Prebuild all ROOT + OBJ_ID shapes so that even when we run out of shape we can always transtion to
// COMPLEX + OBJ_ID.
bool dont_care;
for (i = 0; sizes[i] > 0; i++) {
get_next_shape_internal(RSHAPE(rb_shape_root(i)), ruby_internal_object_id, SHAPE_OBJ_ID, &dont_care, true);
}
}

void
Expand Down
30 changes: 17 additions & 13 deletions variable.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1611,7 +1611,7 @@ rb_attr_delete(VALUE obj, ID id)
return rb_ivar_delete(obj, id, Qnil);
}

static void
static shape_id_t
obj_transition_too_complex(VALUE obj, st_table *table)
{
RUBY_ASSERT(!rb_shape_obj_too_complex_p(obj));
Expand Down Expand Up @@ -1659,6 +1659,7 @@ obj_transition_too_complex(VALUE obj, st_table *table)
}

xfree(old_fields);
return shape_id;
}

void
Expand All @@ -1673,7 +1674,7 @@ rb_obj_init_too_complex(VALUE obj, st_table *table)
}

// Copy all object fields, including ivars and internal object_id, etc
void
shape_id_t
rb_evict_fields_to_hash(VALUE obj)
{
void rb_obj_copy_fields_to_hash_table(VALUE obj, st_table *table);
Expand All @@ -1682,9 +1683,10 @@ rb_evict_fields_to_hash(VALUE obj)

st_table *table = st_init_numtable_with_size(RSHAPE_LEN(RBASIC_SHAPE_ID(obj)));
rb_obj_copy_fields_to_hash_table(obj, table);
obj_transition_too_complex(obj, table);
shape_id_t new_shape_id = obj_transition_too_complex(obj, table);

RUBY_ASSERT(rb_shape_obj_too_complex_p(obj));
return new_shape_id;
}

void
Expand All @@ -1711,7 +1713,7 @@ general_ivar_set(VALUE obj, ID id, VALUE val, void *data,
VALUE *(*shape_fields_func)(VALUE, void *),
void (*shape_resize_fields_func)(VALUE, attr_index_t, attr_index_t, void *),
void (*set_shape_id_func)(VALUE, shape_id_t, void *),
void (*transition_too_complex_func)(VALUE, void *),
shape_id_t (*transition_too_complex_func)(VALUE, void *),
st_table *(*too_complex_table_func)(VALUE, void *))
{
struct general_ivar_set_result result = {
Expand All @@ -1736,7 +1738,7 @@ general_ivar_set(VALUE obj, ID id, VALUE val, void *data,

shape_id_t next_shape_id = rb_shape_transition_add_ivar(obj, id);
if (UNLIKELY(rb_shape_too_complex_p(next_shape_id))) {
transition_too_complex_func(obj, data);
current_shape_id = transition_too_complex_func(obj, data);
goto too_complex;
}
else if (UNLIKELY(RSHAPE_CAPACITY(next_shape_id) != RSHAPE_CAPACITY(current_shape_id))) {
Expand Down Expand Up @@ -1772,14 +1774,14 @@ general_field_set(VALUE obj, shape_id_t target_shape_id, VALUE val, void *data,
VALUE *(*shape_fields_func)(VALUE, void *),
void (*shape_resize_fields_func)(VALUE, attr_index_t, attr_index_t, void *),
void (*set_shape_id_func)(VALUE, shape_id_t, void *),
void (*transition_too_complex_func)(VALUE, void *),
shape_id_t (*transition_too_complex_func)(VALUE, void *),
st_table *(*too_complex_table_func)(VALUE, void *))
{
shape_id_t current_shape_id = RBASIC_SHAPE_ID(obj);

if (UNLIKELY(rb_shape_too_complex_p(target_shape_id))) {
if (UNLIKELY(!rb_shape_too_complex_p(current_shape_id))) {
transition_too_complex_func(obj, data);
current_shape_id = transition_too_complex_func(obj, data);
}

st_table *table = too_complex_table_func(obj, data);
Expand All @@ -1788,6 +1790,7 @@ general_field_set(VALUE obj, shape_id_t target_shape_id, VALUE val, void *data,
RBASIC_SET_SHAPE_ID(obj, target_shape_id);
}

RUBY_ASSERT(RSHAPE_EDGE_NAME(target_shape_id));
st_insert(table, (st_data_t)RSHAPE_EDGE_NAME(target_shape_id), (st_data_t)val);
RB_OBJ_WRITTEN(obj, Qundef, val);
}
Expand Down Expand Up @@ -1877,11 +1880,12 @@ generic_ivar_set_set_shape_id(VALUE obj, shape_id_t shape_id, void *data)
fields_lookup->shape_id = shape_id;
}

static void
static shape_id_t
generic_ivar_set_transition_too_complex(VALUE obj, void *_data)
{
rb_evict_fields_to_hash(obj);
shape_id_t new_shape_id = rb_evict_fields_to_hash(obj);
FL_SET_RAW(obj, FL_EXIVAR);
return new_shape_id;
}

static st_table *
Expand Down Expand Up @@ -1997,10 +2001,10 @@ obj_ivar_set_set_shape_id(VALUE obj, shape_id_t shape_id, void *_data)
rb_obj_set_shape_id(obj, shape_id);
}

static void
static shape_id_t
obj_ivar_set_transition_too_complex(VALUE obj, void *_data)
{
rb_evict_fields_to_hash(obj);
return rb_evict_fields_to_hash(obj);
}

static st_table *
Expand Down Expand Up @@ -4691,10 +4695,10 @@ class_ivar_set_set_shape_id(VALUE obj, shape_id_t shape_id, void *_data)
rb_obj_set_shape_id(obj, shape_id);
}

static void
static shape_id_t
class_ivar_set_transition_too_complex(VALUE obj, void *_data)
{
rb_evict_fields_to_hash(obj);
return rb_evict_fields_to_hash(obj);
}

static st_table *
Expand Down
Loading