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 <rusty@rustcorp.com.au>

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index 283ba3d7f1f41855370518c355d785f948794bc3..3247bea0879af34e2db5f47e1a3c5f9ac8a9fa9f 100644 (file)
--- 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 eac57e37a326612226f6cd7907c04bcbc589c360..faaf541bd8ce8c5ee5f5ea64eab3649e1462fade 100644 (file)
--- 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 0328c352341667ae37dd7d305b8133227ecaf3a3..a4e5d38a2bc066ecfa50d7609cd129aa9fab245c 100644 (file)
--- 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();