Visitar URL original
hash.c: see a delete made from inside an eql? callback · mruby/mruby@db2f511 · GitHub
Skip to content

Commit db2f511

Browse files
matzclaude
authored and
mimaki
committed
hash.c: see a delete made from inside an eql? callback
Every lookup and store can re-enter Ruby through a key's `eql?` or `hash`, and H_CHECK_MODIFIED is what stands between that and an iterator reading a hash that has moved underneath it. It watched the capacity, the flag bits and the two pointers, all of which a reallocation moves. A delete moves none of them. `ar_delete` and `ht_delete` mark the slot's key undef and decrement the count, so a delete performed inside a callback was invisible. The scan had read the count once and was left walking for more entries than the hash still held: past the used entries, past the allocation, and the garbage it found there went to `eql?` as a key, back into the array by `ar_rehash`, or out of `Hash#shift`. The count goes on what the guard compares, which is what the delete actually changes. EA_EACH also takes the bound H_EACH has had since GHSA-jfmr-44fc-gfhg: the guard speaks only for a callback the loop body reached, while the bound holds for a count that disagrees with the array for any reason at all. Without it a rehash that lost entries mid-way reaches `mrb_assert(size == w_size)` instead of the exception. Reported as GHSA-2778-fvwg-5m8w. All five variants of the report now answer with "hash modified". Co-Authored-By: Claude Opus 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_014EUmgLgPoanCcuMZf8vFmY
1 parent 3cf73ee commit db2f511

2 files changed

Lines changed: 95 additions & 27 deletions

File tree

‎src/hash.c‎

Lines changed: 40 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -175,10 +175,23 @@ DEFINE_SWITCHER(ht, HT) /* h_ht_on h_ht
175175
entry_var < ea_end__; \
176176
entry_var++)
177177

178-
#define EA_EACH(ea, size, entry_var) \
178+
/* Visit the live count of entries, skipping deleted slots, with the skip
179+
bounded by the end of the entry allocation (ea + ea_capa). The live count
180+
is read once, and a callback reached from the loop body can delete entries
181+
ahead of the cursor: `size` and the slot's key are all a delete touches, so
182+
H_CHECK_MODIFIED, which watches the capacity and the pointers, does not see
183+
it and the count is left too high. The bound is what keeps the iterator
184+
inside the allocation then (GHSA-jfmr-44fc-gfhg and GHSA-2778-fvwg-5m8w,
185+
CWE-125). ea_capa is used rather than ea_n_used because the latter is
186+
transiently inconsistent with the entry positions while a rehash that
187+
raised mid-way is being observed; ea_capa always spans every entry. */
188+
#define EA_EACH(ea, ea_capa, size, entry_var) \
179189
for (uint32_t ea_size__ = (size); ea_size__; ea_size__ = 0) \
180-
for (hash_entry *entry_var = (ea); \
181-
ea_size__ && (entry_var = entry_skip_deleted(entry_var), TRUE); \
190+
for (hash_entry *entry_var = (ea), \
191+
*ea_end__ = (entry_var) + (ea_capa); \
192+
ea_size__ && \
193+
(entry_var = entry_skip_deleted_bounded(entry_var, ea_end__)) \
194+
< ea_end__; \
182195
entry_var++, ea_size__--)
183196

184197
#define IB_CYCLE_BY_KEY(mrb, h, key, it_var) \
@@ -296,6 +309,12 @@ struct h_check_modified {
296309
void *tbl;
297310
uint32_t ht_ea_capa;
298311
hash_entry *ht_ea;
312+
/* A delete touches the count and the slot's key and nothing else: it
313+
reallocates nothing, so every field above it is the same afterwards
314+
(GHSA-2778-fvwg-5m8w). The count is what tells such a change apart, and
315+
an iteration that has read it once is left walking a hash that no longer
316+
holds that many. */
317+
uint32_t size;
299318
};
300319

301320
#define H_CHECK_MODIFIED_FLAGS_MASK (MRB_HASH_HT | MRB_HASH_IB_BIT_MASK | MRB_HASH_AR_EA_CAPA_MASK)
@@ -310,6 +329,7 @@ h_check_modified_init(mrb_state *mrb, struct RHash *h)
310329
checker.tbl = h->hsh.ht;
311330
checker.ht_ea_capa = (H_CHECK_MODIFIED_USE_HT_EA_CAPA_FOR_AR || h_ht_p(h)) ? ht_ea_capa(h) : 0;
312331
checker.ht_ea = (H_CHECK_MODIFIED_USE_HT_EA_FOR_AR || h_ht_p(h)) ? ht_ea(h) : NULL;
332+
checker.size = h_size(h);
313333
return checker;
314334
}
315335

@@ -321,7 +341,8 @@ h_check_modified_validate(mrb_state *mrb, struct h_check_modified *checker, stru
321341
((H_CHECK_MODIFIED_USE_HT_EA_CAPA_FOR_AR || h_ht_p(h)) &&
322342
checker->ht_ea_capa != ht_ea_capa(h)) ||
323343
((H_CHECK_MODIFIED_USE_HT_EA_FOR_AR || h_ht_p(h)) &&
324-
checker->ht_ea != ht_ea(h))) {
344+
checker->ht_ea != ht_ea(h)) ||
345+
checker->size != h_size(h)) {
325346
mrb_raise(mrb, E_RUNTIME_ERROR, "hash modified");
326347
}
327348
}
@@ -441,18 +462,10 @@ entry_delete(hash_entry* entry)
441462
entry->key = mrb_undef_value();
442463
}
443464

444-
static hash_entry*
445-
entry_skip_deleted(hash_entry *e)
446-
{
447-
for (; entry_deleted_p(e); e++)
448-
;
449-
return e;
450-
}
451-
452-
/* Like entry_skip_deleted, but never advances past `end` (one past the last
453-
allocated entry slot). H_EACH uses this so that a callback which deletes
454-
entries ahead of the cursor mid-iteration cannot walk the iterator off the
455-
end of the allocation (GHSA-jfmr-44fc-gfhg, CWE-125). A realloc-causing
465+
/* Skip deleted slots without ever advancing past `end`, one past the last
466+
allocated entry slot, so that a callback which deletes entries ahead of the
467+
cursor mid-iteration cannot walk the iterator off the end of the allocation
468+
(GHSA-jfmr-44fc-gfhg and GHSA-2778-fvwg-5m8w, CWE-125). A realloc-causing
456469
mutation is still caught separately by H_CHECK_MODIFIED in the loop body. */
457470
static hash_entry*
458471
entry_skip_deleted_bounded(hash_entry *e, const hash_entry *end)
@@ -535,10 +548,10 @@ ea_dup(mrb_state *mrb, const hash_entry *ea, uint32_t capa)
535548
}
536549

537550
static hash_entry*
538-
ea_get_by_key(mrb_state *mrb, hash_entry *ea, uint32_t size, mrb_value key,
539-
struct RHash *h)
551+
ea_get_by_key(mrb_state *mrb, hash_entry *ea, uint32_t ea_capa, uint32_t size,
552+
mrb_value key, struct RHash *h)
540553
{
541-
EA_EACH(ea, size, entry) {
554+
EA_EACH(ea, ea_capa, size, entry) {
542555
if (obj_eql(mrb, key, entry->key, h)) return entry;
543556
}
544557
return NULL;
@@ -595,7 +608,7 @@ ar_compress(mrb_state *mrb, struct RHash *h)
595608
static mrb_bool
596609
ar_get(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
597610
{
598-
EA_EACH(ar_ea(h), ar_size(h), entry) {
611+
EA_EACH(ar_ea(h), ar_ea_capa(h), ar_size(h), entry) {
599612
if (!obj_eql(mrb, key, entry->key, h)) continue;
600613
*valp = entry->val;
601614
return TRUE;
@@ -608,7 +621,7 @@ ar_set(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value val)
608621
{
609622
uint32_t size = ar_size(h);
610623
hash_entry *entry;
611-
if ((entry = ea_get_by_key(mrb, ar_ea(h), size, key, h))) {
624+
if ((entry = ea_get_by_key(mrb, ar_ea(h), ar_ea_capa(h), size, key, h))) {
612625
entry->val = val;
613626
}
614627
else {
@@ -638,7 +651,7 @@ ar_set(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value val)
638651
static mrb_bool
639652
ar_delete(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
640653
{
641-
hash_entry *entry = ea_get_by_key(mrb, ar_ea(h), ar_size(h), key, h);
654+
hash_entry *entry = ea_get_by_key(mrb, ar_ea(h), ar_ea_capa(h), ar_size(h), key, h);
642655
if (!entry) return FALSE;
643656
*valp = entry->val;
644657
entry_delete(entry);
@@ -650,7 +663,7 @@ static void
650663
ar_shift(mrb_state *mrb, struct RHash *h, mrb_value *keyp, mrb_value *valp)
651664
{
652665
uint32_t size = ar_size(h);
653-
EA_EACH(ar_ea(h), size, entry) {
666+
EA_EACH(ar_ea(h), ar_ea_capa(h), size, entry) {
654667
*keyp = entry->key;
655668
*valp = entry->val;
656669
entry_delete(entry);
@@ -665,8 +678,8 @@ ar_rehash(mrb_state *mrb, struct RHash *h)
665678
/* see comments in `h_rehash` */
666679
uint32_t size = ar_size(h), w_size = 0, ea_capa = ar_ea_capa(h);
667680
hash_entry *ea = ar_ea(h), *w_entry;
668-
EA_EACH(ea, size, r_entry) {
669-
if ((w_entry = ea_get_by_key(mrb, ea, w_size, r_entry->key, h))) {
681+
EA_EACH(ea, ea_capa, size, r_entry) {
682+
if ((w_entry = ea_get_by_key(mrb, ea, ea_capa, w_size, r_entry->key, h))) {
670683
w_entry->val = r_entry->val;
671684
ar_set_size(h, --size);
672685
entry_delete(r_entry);
@@ -1018,7 +1031,7 @@ static void
10181031
ht_shift(mrb_state *mrb, struct RHash *h, mrb_value *keyp, mrb_value *valp)
10191032
{
10201033
hash_entry *ea = ht_ea(h);
1021-
EA_EACH(ea, ht_size(h), entry) {
1034+
EA_EACH(ea, ht_ea_capa(h), ht_size(h), entry) {
10221035
IB_CYCLE_BY_KEY(mrb, h, entry->key, it) {
10231036
if (ib_it_get(it) != U32(entry - ea)) continue;
10241037
*keyp = entry->key;
@@ -1046,7 +1059,7 @@ ht_rehash(mrb_state *mrb, struct RHash *h)
10461059
ht_init(mrb, h, 0, ea, ea_capa, h_ht(h), ib_bit_for(size));
10471060
ht_set_size(h, size);
10481061
ht_set_ea_n_used(h, ht_ea_n_used(h));
1049-
EA_EACH(ea, size, r_entry) {
1062+
EA_EACH(ea, ea_capa, size, r_entry) {
10501063
IB_CYCLE_BY_KEY(mrb, h, r_entry->key, it) {
10511064
if (ib_it_active_p(it)) {
10521065
if (!obj_eql(mrb, r_entry->key, ib_it_entry(it)->key, h)) continue;

‎test/t/hash.rb‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -973,6 +973,61 @@ def h.default(k); self[k] = 1; end
973973
assert_predicate(g, :empty?)
974974
end
975975

976+
assert('Hash lookup with entries deleted by an eql? callback') do
977+
# Regression for GHSA-2778-fvwg-5m8w: a delete touches the count and the
978+
# slot's key and nothing else, so it reallocates nothing and the reentry
979+
# guard, which watched the capacity and the pointers, did not see it. A
980+
# lookup that had already read the count then walked past the end of the
981+
# entry array and handed what it found there to eql? as a key. Each entry
982+
# below has to answer with the exception, never by reading out of bounds.
983+
evil = Class.new do
984+
def initialize(h, keys) @h, @keys = h, keys end
985+
def eql?(other) @keys.each { |k| @h.delete(k) }; false end
986+
def hash; 0 end
987+
end
988+
ar = lambda { {"k0" => 0, "k1" => 1, "k2" => 2, "k3" => 3, "k4" => 4} }
989+
ar_keys = ["k1", "k2", "k3", "k4"]
990+
991+
# Hash#[], and the two that reach the same scan through it.
992+
h = ar.call
993+
assert_raise(RuntimeError) { h[evil.new(h, ar_keys)] }
994+
h3 = ar.call
995+
assert_raise(RuntimeError) { h3.key?(evil.new(h3, ar_keys)) }
996+
997+
# A store reads the array the same way before it writes.
998+
h4 = ar.call
999+
assert_raise(RuntimeError) { h4[evil.new(h4, ar_keys)] = 9 }
1000+
1001+
# An HT-form hash reaches it too.
1002+
t = {}
1003+
20.times { |i| t["h#{i}"] = i }
1004+
assert_raise(RuntimeError) { t[evil.new(t, (1...20).map { |i| "h#{i}" })] }
1005+
1006+
# A delete and an add together leave the count where it was, which is what
1007+
# the guard reads, so the bound on the entry array is what has to answer for
1008+
# this one. Whether the add also moves the array, and so is seen by the
1009+
# guard after all, is up to the allocator, so the lookup is asked only to
1010+
# finish: either it raises or it answers, never reads past the end.
1011+
swapper = Class.new do
1012+
def initialize(h) @h = h end
1013+
def eql?(other) @h.delete("k1"); @h["zz"] = 99; false end
1014+
def hash; 0 end
1015+
end
1016+
m = ar.call
1017+
begin
1018+
assert_nil(m[swapper.new(m)])
1019+
rescue RuntimeError
1020+
# the guard saw the array move; either way nothing was read out of bounds
1021+
end
1022+
assert_true(m.size >= 4)
1023+
1024+
# A hash nothing touched during the lookup still answers.
1025+
q = {"a" => 1, "b" => 2}
1026+
assert_equal(1, q["a"])
1027+
assert_equal(2, q.size)
1028+
assert_equal(2, q.rehash.size)
1029+
end
1030+
9761031
assert('Hash#assoc, Hash#rassoc') do
9771032
h = {foo: 0, bar: 1, baz: 2}
9781033
assert_equal([:bar, 1], h.assoc(:bar))

0 commit comments

Comments
 (0)