From e03b68c761b870fd9e4c165bfe2358f5df82e49c Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 13 Jun 2022 21:48:19 +0930 Subject: [PATCH] htable: fix vanishing entries properly. A hash table entry consists of the pointer, but we mask out bits which are common to all pointers, and replace them with hash bits. The entry values 0 and 1 are special, meaning "empty" and "deleted" respectively. However, if a hash has mainly zero bits, and an pointer's non-shared bits are all zero, we can create an entry which looks empty or deleted. The solution in this case is to share another bit (there must be some bit which is not zero, since we don't allow 0 and 1 as pointers in the hash table). It's unusual, so I put this in a cold function: it shares code with the existing "oh, we need to reduce the common bits, since this new pointer doesn't look like the previous ones" case. Signed-off-by: Rusty Russell --- ccan/htable/htable.c | 99 ++++++++++++++++++++++++++++-------- ccan/htable/htable.h | 2 +- ccan/htable/test/run-clash.c | 1 + 3 files changed, 81 insertions(+), 21 deletions(-) diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index 283ba3d7..3247bea0 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -201,6 +201,77 @@ void *htable_prev_(const struct htable *ht, struct htable_iter *i) } } +/* Another bit currently in mask needs to be exposed, so that a bucket with p in + * it won't appear invalid */ +static COLD void unset_another_common_bit(struct htable *ht, + uintptr_t *maskdiff, + const void *p) +{ + size_t i; + + for (i = sizeof(uintptr_t) * CHAR_BIT - 1; i > 0; i--) { + if (((uintptr_t)p & ((uintptr_t)1 << i)) + && ht->common_mask & ~*maskdiff & ((uintptr_t)1 << i)) + break; + } + /* There must have been one, right? */ + assert(i > 0); + + *maskdiff |= ((uintptr_t)1 << i); +} + +/* We want to change the common mask: this fixes up the table */ +static COLD void fixup_table_common(struct htable *ht, uintptr_t maskdiff) +{ + size_t i; + uintptr_t bitsdiff; + +again: + bitsdiff = ht->common_bits & maskdiff; + + for (i = 0; i < (size_t)1 << ht->bits; i++) { + uintptr_t e; + if (!entry_is_valid(e = ht->table[i])) + continue; + + /* Clear the bits no longer in the mask, set them as + * expected. */ + e &= ~maskdiff; + e |= bitsdiff; + /* If this made it invalid, restart with more exposed */ + if (!entry_is_valid(e)) { + unset_another_common_bit(ht, &maskdiff, get_raw_ptr(ht, e)); + goto again; + } + ht->table[i] = e; + } + + /* Take away those bits from our mask, bits and perfect bit. */ + ht->common_mask &= ~maskdiff; + ht->common_bits &= ~maskdiff; + if (ht_perfect_mask(ht) & maskdiff) + ht->perfect_bitnum = NO_PERFECT_BIT; +} + +/* Limited recursion */ +static void ht_add(struct htable *ht, const void *new, size_t h); + +/* We tried to add this entry, but it looked invalid! We need to + * let another pointer bit through mask */ +static COLD void update_common_fix_invalid(struct htable *ht, const void *p, size_t h) +{ + uintptr_t maskdiff; + + assert(ht->elems != 0); + + maskdiff = 0; + unset_another_common_bit(ht, &maskdiff, p); + fixup_table_common(ht, maskdiff); + + /* Now won't recurse */ + ht_add(ht, p, h); +} + /* This does not expand the hash table, that's up to caller. */ static void ht_add(struct htable *ht, const void *new, size_t h) { @@ -214,6 +285,8 @@ static void ht_add(struct htable *ht, const void *new, size_t h) i = (i + 1) & ((1 << ht->bits)-1); } ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect); + if (!entry_is_valid(ht->table[i])) + update_common_fix_invalid(ht, new, h); } static COLD bool double_table(struct htable *ht) @@ -283,8 +356,7 @@ static COLD void rehash_table(struct htable *ht) /* We stole some bits, now we need to put them back... */ static COLD void update_common(struct htable *ht, const void *p) { - unsigned int i; - uintptr_t maskdiff, bitsdiff; + uintptr_t maskdiff; if (ht->elems == 0) { ht->common_mask = -1; @@ -297,33 +369,20 @@ static COLD void update_common(struct htable *ht, const void *p) /* Find bits which are unequal to old common set. */ maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask); - /* These are the bits which go there in existing entries. */ - bitsdiff = ht->common_bits & maskdiff; - - for (i = 0; i < (size_t)1 << ht->bits; i++) { - if (!entry_is_valid(ht->table[i])) - continue; - /* Clear the bits no longer in the mask, set them as - * expected. */ - ht->table[i] &= ~maskdiff; - ht->table[i] |= bitsdiff; - } - - /* Take away those bits from our mask, bits and perfect bit. */ - ht->common_mask &= ~maskdiff; - ht->common_bits &= ~maskdiff; - if (ht_perfect_mask(ht) & maskdiff) - ht->perfect_bitnum = NO_PERFECT_BIT; + fixup_table_common(ht, maskdiff); (void)htable_debug(ht, HTABLE_LOC); } bool htable_add_(struct htable *ht, size_t hash, const void *p) { + /* Cannot insert NULL, or (void *)1. */ + assert(p); + assert(entry_is_valid((uintptr_t)p)); + if (ht->elems+1 > ht_max(ht) && !double_table(ht)) return false; if (ht->elems+1 + ht->deleted > ht_max_with_deleted(ht)) rehash_table(ht); - assert(p); if (((uintptr_t)p & ht->common_mask) != ht->common_bits) update_common(ht, p); diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h index eac57e37..faaf541b 100644 --- a/ccan/htable/htable.h +++ b/ccan/htable/htable.h @@ -132,7 +132,7 @@ bool htable_copy_(struct htable *dst, const struct htable *src); * htable_add - add a pointer into a hash table. * @ht: the htable * @hash: the hash value of the object - * @p: the non-NULL pointer + * @p: the non-NULL pointer (also cannot be (void *)1). * * Also note that this can only fail due to allocation failure. Otherwise, it * returns true. diff --git a/ccan/htable/test/run-clash.c b/ccan/htable/test/run-clash.c index 0328c352..a4e5d38a 100644 --- a/ccan/htable/test/run-clash.c +++ b/ccan/htable/test/run-clash.c @@ -24,6 +24,7 @@ int main(void) htable_add(&ht, hash((void *)i, NULL), (void *)i); htable_add(&ht, hash((void *)j, NULL), (void *)j); ok1(htable_check(&ht, "test")); + htable_clear(&ht); } } return exit_status(); -- 2.39.5