Refactor bloom filter logic not to be digest-specific.

Now the address-set code and the digest-set code share the same
backend.

Closes ticket 26510

2 files changed, 97 insertions, 53 deletions

diff --git a/src/lib/container/bloomfilt.c b/src/lib/container/bloomfilt.c
index 2133c280a5..1cab817e18 100644
--- a/src/lib/container/bloomfilt.c
+++ b/src/lib/container/bloomfilt.c
@@ -9,14 +9,75 @@
  **/
 
 #include <stdlib.h>
+
 #include "lib/malloc/util_malloc.h"
 #include "lib/container/bloomfilt.h"
 #include "lib/intmath/bits.h"
+#include "lib/log/util_bug.h"
+#include "siphash.h"
+
+/** How many bloom-filter bits we set per address. This is twice the
+ * BLOOMFILT_N_HASHES value, since we split the siphash output into two 32-bit
+ * values. */
+#define N_BITS_PER_ITEM (BLOOMFILT_N_HASHES * 2)
+
+struct bloomfilt_t {
+  /** siphash keys to make BLOOMFILT_N_HASHES independent hashes for each
+   * items. */
+  struct sipkey key[BLOOMFILT_N_HASHES];
+  bloomfilt_hash_fn hashfn; /**< Function used to generate hashes */
+  uint32_t mask; /**< One less than the number of bits in <b>ba</b>; always
+                  * one less than a power of two. */
+  bitarray_t *ba; /**< A bit array to implement the Bloom filter. */
+};
+
+#define BIT(set, n) ((n) & (set)->mask)
+
+/** Add the element <b>item</b> to <b>set</b>. */
+void
+bloomfilt_add(bloomfilt_t *set,
+              const void *item)
+{
+  int i;
+  for (i = 0; i < BLOOMFILT_N_HASHES; ++i) {
+    uint64_t h = set->hashfn(&set->key[i], item);
+    uint32_t high_bits = (uint32_t)(h >> 32);
+    uint32_t low_bits = (uint32_t)(h);
+    bitarray_set(set->ba, BIT(set, high_bits));
+    bitarray_set(set->ba, BIT(set, low_bits));
+  }
+}
 
-/** Return a newly allocated digestset_t, optimized to hold a total of
- * <b>max_elements</b> digests with a reasonably low false positive weight. */
-digestset_t *
-digestset_new(int max_elements)
+/** If <b>item</b> is in <b>set</b>, return nonzero.  Otherwise,
+ * <em>probably</em> return zero. */
+int
+bloomfilt_probably_contains(const bloomfilt_t *set,
+                            const void *item)
+{
+  int i, matches = 0;
+  for (i = 0; i < BLOOMFILT_N_HASHES; ++i) {
+    uint64_t h = set->hashfn(&set->key[i], item);
+    uint32_t high_bits = (uint32_t)(h >> 32);
+    uint32_t low_bits = (uint32_t)(h);
+    // Note that !! is necessary here, since bitarray_is_set does not
+    // necessarily return 1 on true.
+    matches += !! bitarray_is_set(set->ba, BIT(set, high_bits));
+    matches += !! bitarray_is_set(set->ba, BIT(set, low_bits));
+  }
+  return matches == N_BITS_PER_ITEM;
+}
+
+/** Return a newly allocated bloomfilt_t, optimized to hold a total of
+ * <b>max_elements</b> elements with a reasonably low false positive weight.
+ *
+ * Uses the siphash-based function <b>hashfn</b> to compute hard-to-collide
+ * functions of the items, and the key material <b>random_key</b> to
+ * key the hash.  There must be BLOOMFILT_KEY_LEN bytes in the supplied key.
+ **/
+bloomfilt_t *
+bloomfilt_new(int max_elements,
+              bloomfilt_hash_fn hashfn,
+              const uint8_t *random_key)
 {
   /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k
    * is the number of hash functions per entry, m is the bits in the array,
@@ -29,15 +90,21 @@ digestset_new(int max_elements)
    * conserve CPU, and k==13 is pretty big.
    */
   int n_bits = 1u << (tor_log2(max_elements)+5);
-  digestset_t *r = tor_malloc(sizeof(digestset_t));
+  bloomfilt_t *r = tor_malloc(sizeof(bloomfilt_t));
   r->mask = n_bits - 1;
   r->ba = bitarray_init_zero(n_bits);
+
+  tor_assert(sizeof(r->key) == BLOOMFILT_KEY_LEN);
+  memcpy(r->key, random_key, sizeof(r->key));
+
+  r->hashfn = hashfn;
+
   return r;
 }
 
 /** Free all storage held in <b>set</b>. */
 void
-digestset_free_(digestset_t *set)
+bloomfilt_free_(bloomfilt_t *set)
 {
   if (!set)
     return;
diff --git a/src/lib/container/bloomfilt.h b/src/lib/container/bloomfilt.h
index adcdb10fc3..577acf5e48 100644
--- a/src/lib/container/bloomfilt.h
+++ b/src/lib/container/bloomfilt.h
@@ -9,50 +9,27 @@
 #include "orconfig.h"
 #include "lib/cc/torint.h"
 #include "lib/container/bitarray.h"
-#include "siphash.h"
-
-/** A set of digests, implemented as a Bloom filter. */
-typedef struct {
-  int mask; /**< One less than the number of bits in <b>ba</b>; always one less
-             * than a power of two. */
-  bitarray_t *ba; /**< A bit array to implement the Bloom filter. */
-} digestset_t;
-
-#define BIT(n) ((n) & set->mask)
-/** Add the digest <b>digest</b> to <b>set</b>. */
-static inline void
-digestset_add(digestset_t *set, const char *digest)
-{
-  const uint64_t x = siphash24g(digest, 20);
-  const uint32_t d1 = (uint32_t) x;
-  const uint32_t d2 = (uint32_t)( (x>>16) + x);
-  const uint32_t d3 = (uint32_t)( (x>>32) + x);
-  const uint32_t d4 = (uint32_t)( (x>>48) + x);
-  bitarray_set(set->ba, BIT(d1));
-  bitarray_set(set->ba, BIT(d2));
-  bitarray_set(set->ba, BIT(d3));
-  bitarray_set(set->ba, BIT(d4));
-}
-
-/** If <b>digest</b> is in <b>set</b>, return nonzero.  Otherwise,
- * <em>probably</em> return zero. */
-static inline int
-digestset_contains(const digestset_t *set, const char *digest)
-{
-  const uint64_t x = siphash24g(digest, 20);
-  const uint32_t d1 = (uint32_t) x;
-  const uint32_t d2 = (uint32_t)( (x>>16) + x);
-  const uint32_t d3 = (uint32_t)( (x>>32) + x);
-  const uint32_t d4 = (uint32_t)( (x>>48) + x);
-  return bitarray_is_set(set->ba, BIT(d1)) &&
-         bitarray_is_set(set->ba, BIT(d2)) &&
-         bitarray_is_set(set->ba, BIT(d3)) &&
-         bitarray_is_set(set->ba, BIT(d4));
-}
-#undef BIT
-
-digestset_t *digestset_new(int max_elements);
-void digestset_free_(digestset_t* set);
-#define digestset_free(set) FREE_AND_NULL(digestset_t, digestset_free_, (set))
-
-#endif /* !defined(TOR_CONTAINER_H) */
+
+/** A set of elements, implemented as a Bloom filter. */
+typedef struct bloomfilt_t bloomfilt_t;
+
+/** How many 64-bit siphash values to extract per item. */
+#define BLOOMFILT_N_HASHES 2
+
+/** How much key material do we need to randomize hashes? */
+#define BLOOMFILT_KEY_LEN (BLOOMFILT_N_HASHES * 16)
+
+struct sipkey;
+typedef uint64_t (*bloomfilt_hash_fn)(const struct sipkey *key,
+                                      const void *item);
+
+void bloomfilt_add(bloomfilt_t *set, const void *item);
+int bloomfilt_probably_contains(const bloomfilt_t *set, const void *item);
+
+bloomfilt_t *bloomfilt_new(int max_elements,
+                           bloomfilt_hash_fn hashfn,
+                           const uint8_t *random_key);
+void bloomfilt_free_(bloomfilt_t* set);
+#define bloomfilt_free(set) FREE_AND_NULL(bloomfilt_t, bloomfilt_free_, (set))
+
+#endif /* !defined(TOR_BLOOMFILT_H) */