From ebd398ac5a4147a1e652d6943c39a29a62f12e66 Mon Sep 17 00:00:00 2001 From: Koichi Sasada Date: Wed, 16 Jan 2019 10:48:30 +0000 Subject: remove RHash::iter_lev. iter_lev is used to detect the hash is iterating or not. Usually, iter_lev should be very small number (1 or 2) so `int` is overkill. This patch introduce iter_lev in flags (7 bits, FL13 to FL19) and if iter_lev exceeds this range, save it in hidden attribute. We can get 1 word in RHash. We can't modify frozen objects. Therefore I added new internal API `rb_ivar_set_internal()` which allows us to set an attribute even if the target object is frozen if the name is hidden ivar (the name without `@` prefix). --- hash.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++-- internal.h | 22 +++++++++++------- test/ruby/test_hash.rb | 25 +++++++++++++++++++++ variable.c | 25 ++++++++++++++++----- 4 files changed, 117 insertions(+), 15 deletions(-) diff --git a/hash.c b/hash.c index f458fd71aa..fc65e4cc7d 100644 --- a/hash.c +++ b/hash.c @@ -1252,16 +1252,72 @@ hash_foreach_iter(st_data_t key, st_data_t value, st_data_t argp, int error) return ST_CHECK; } +static int +iter_lev_in_ivar(VALUE hash) +{ + VALUE levval = rb_ivar_get(hash, rb_intern("hash_iter_lev")); + HASH_ASSERT(FIXNUM_P(levval)); + return FIX2INT(levval); +} + +void rb_ivar_set_internal(VALUE obj, ID id, VALUE val); + +static void +iter_lev_in_ivar_set(VALUE hash, int lev) +{ + rb_ivar_set_internal(hash, rb_intern("hash_iter_lev"), INT2FIX(lev)); +} + +static int +iter_lev_in_flags(VALUE hash) +{ + unsigned int u = (unsigned int)(RBASIC(hash)->flags & (unsigned int)RHASH_LEV_MASK) >> RHASH_LEV_SHIFT; + return (int)u; +} + +static int +RHASH_ITER_LEV(VALUE hash) +{ + int lev = iter_lev_in_flags(hash); + + if (lev == RHASH_LEV_MAX) { + return iter_lev_in_ivar(hash); + } + else { + return lev; + } +} + static void hash_iter_lev_inc(VALUE hash) { - *((int *)&RHASH(hash)->iter_lev) = RHASH_ITER_LEV(hash) + 1; + int lev = iter_lev_in_flags(hash); + if (lev == RHASH_LEV_MAX) { + lev = iter_lev_in_ivar(hash); + iter_lev_in_ivar_set(hash, lev+1); + } + else { + lev += 1; + RBASIC(hash)->flags = ((RBASIC(hash)->flags & ~RHASH_LEV_MASK) | (lev << RHASH_LEV_SHIFT)); + if (lev == RHASH_LEV_MAX) { + iter_lev_in_ivar_set(hash, lev); + } + } } static void hash_iter_lev_dec(VALUE hash) { - *((int *)&RHASH(hash)->iter_lev) = RHASH_ITER_LEV(hash) - 1; + int lev = iter_lev_in_flags(hash); + if (lev == RHASH_LEV_MAX) { + lev = iter_lev_in_ivar(hash); + HASH_ASSERT(lev > 0); + iter_lev_in_ivar_set(hash, lev-1); + } + else { + HASH_ASSERT(lev > 0); + RBASIC(hash)->flags = ((RBASIC(hash)->flags & ~RHASH_LEV_MASK) | ((lev-1) << RHASH_LEV_SHIFT)); + } } static VALUE diff --git a/internal.h b/internal.h index 0c6341aad5..0c148bfe3b 100644 --- a/internal.h +++ b/internal.h @@ -815,13 +815,22 @@ struct RComplex { #define RCOMPLEX_SET_IMAG(cmp, i) RB_OBJ_WRITE((cmp), &((struct RComplex *)(cmp))->imag,(i)) enum ruby_rhash_flags { - RHASH_ST_TABLE_FLAG = FL_USER3, + RHASH_ST_TABLE_FLAG = FL_USER3, /* FL 3 */ RHASH_AR_TABLE_MAX_SIZE = 8, - RHASH_AR_TABLE_SIZE_MASK = (FL_USER4|FL_USER5|FL_USER6|FL_USER7), + RHASH_AR_TABLE_SIZE_MASK = (FL_USER4|FL_USER5|FL_USER6|FL_USER7), /* FL 4..7 */ RHASH_AR_TABLE_SIZE_SHIFT = (FL_USHIFT+4), - RHASH_AR_TABLE_BOUND_MASK = (FL_USER8|FL_USER9|FL_USER10|FL_USER11), + RHASH_AR_TABLE_BOUND_MASK = (FL_USER8|FL_USER9|FL_USER10|FL_USER11), /* FL 8..11 */ RHASH_AR_TABLE_BOUND_SHIFT = (FL_USHIFT+8), +#if USE_TRANSIENT_HEAP + RHASH_TRANSIENT_FLAG = FL_USER12, /* FL 12 */ +#endif + + RHASH_LEV_MASK = (FL_USER13 | FL_USER14 | FL_USER15 | /* FL 13..19 */ + FL_USER16 | FL_USER17 | FL_USER18 | FL_USER19), + RHASH_LEV_SHIFT = (FL_USHIFT + 13), + RHASH_LEV_MAX = 127, /* 7 bits */ + RHASH_ENUM_END }; @@ -856,7 +865,6 @@ void rb_hash_st_table_set(VALUE hash, st_table *st); #define RHASH_AR_TABLE_BOUND_SHIFT RHASH_AR_TABLE_BOUND_SHIFT #if USE_TRANSIENT_HEAP -#define RHASH_TRANSIENT_FLAG FL_USER14 #define RHASH_TRANSIENT_P(hash) FL_TEST_RAW((hash), RHASH_TRANSIENT_FLAG) #define RHASH_SET_TRANSIENT_FLAG(h) FL_SET_RAW(h, RHASH_TRANSIENT_FLAG) #define RHASH_UNSET_TRANSIENT_FLAG(h) FL_UNSET_RAW(h, RHASH_TRANSIENT_FLAG) @@ -872,16 +880,14 @@ struct RHash { st_table *st; struct ar_table_struct *ar; /* possibly 0 */ } as; - int iter_lev; const VALUE ifnone; + const VALUE reserved; }; -#ifdef RHASH_ITER_LEV -# undef RHASH_ITER_LEV +#ifdef RHASH_IFNONE # undef RHASH_IFNONE # undef RHASH_SIZE -# define RHASH_ITER_LEV(h) (RHASH(h)->iter_lev) # define RHASH_IFNONE(h) (RHASH(h)->ifnone) # define RHASH_SIZE(h) (RHASH_AR_TABLE_P(h) ? RHASH_AR_TABLE_SIZE_RAW(h) : RHASH_ST_SIZE(h)) #endif /* #ifdef RHASH_ITER_LEV */ diff --git a/test/ruby/test_hash.rb b/test/ruby/test_hash.rb index 243cad8d43..d973b1f763 100644 --- a/test/ruby/test_hash.rb +++ b/test/ruby/test_hash.rb @@ -1720,6 +1720,31 @@ class TestHash < Test::Unit::TestCase assert_equal(keys, h.keys.map(&:hash), msg) end + def hrec h, n, &b + if n > 0 + h.each{hrec(h, n-1, &b)} + else + yield + end + end + + def test_huge_iter_level + h = @cls[a: 1] + assert_raise(RuntimeError){ + hrec(h, 1000){ h[:c] = 3 } + } + + h = @cls[a: 1] + hrec(h, 1000){} + h[:c] = 3 + assert_equal(3, h[:c]) + + h = @cls[a: 1] + h.freeze # set hidden attribute for a frozen object + hrec(h, 1000){} + assert_equal(1, h.size) + end + class TestSubHash < TestHash class SubHash < Hash def reject(*) diff --git a/variable.c b/variable.c index 7d6905f390..b839f3067b 100644 --- a/variable.c +++ b/variable.c @@ -1340,16 +1340,15 @@ obj_ivar_set(VALUE obj, ID id, VALUE val) return val; } -VALUE -rb_ivar_set(VALUE obj, ID id, VALUE val) +static void +ivar_set(VALUE obj, ID id, VALUE val) { RB_DEBUG_COUNTER_INC(ivar_set_base); - rb_check_frozen(obj); - switch (BUILTIN_TYPE(obj)) { case T_OBJECT: - return obj_ivar_set(obj, id, val); + obj_ivar_set(obj, id, val); + break; case T_CLASS: case T_MODULE: if (!RCLASS_IV_TBL(obj)) RCLASS_IV_TBL(obj) = st_init_numtable(); @@ -1359,9 +1358,25 @@ rb_ivar_set(VALUE obj, ID id, VALUE val) generic_ivar_set(obj, id, val); break; } +} + +VALUE +rb_ivar_set(VALUE obj, ID id, VALUE val) +{ + rb_check_frozen(obj); + ivar_set(obj, id, val); return val; } +void +rb_ivar_set_internal(VALUE obj, ID id, VALUE val) +{ + // should be internal instance variable name (no @ prefix) + VM_ASSERT(!rb_is_instance_id(id)); + + ivar_set(obj, id, val); +} + VALUE rb_ivar_defined(VALUE obj, ID id) { -- cgit v1.2.3