@@ -29,13 +29,15 @@
#include "integer.h"
#include "list.h"
+
+#include "crypto.h"
#include "misc.h"
#include "memdbg.h"
struct hash *
-hash_init(const uint32_t n_buckets, const uint32_t iv,
- uint64_t (*hash_function)(const void *key, uint32_t iv),
+hash_init(const uint32_t n_buckets,
+ uint64_t (*hash_function)(const void *key, const uint8_t hash_key[HASH_KEY_LEN]),
bool (*compare_function)(const void *key1, const void *key2))
{
struct hash *h;
@@ -46,7 +48,10 @@
h->mask = h->n_buckets - 1;
h->hash_function = hash_function;
h->compare_function = compare_function;
- h->iv = iv;
+
+ /* create random hash key */
+ prng_bytes(h->hash_key, sizeof(h->hash_key));
+
ALLOC_ARRAY(h->buckets, struct hash_bucket, h->n_buckets);
for (uint32_t i = 0; i < h->n_buckets; ++i)
{
@@ -49,19 +49,24 @@
struct hash_element *list;
};
+
+#define HASH_KEY_LEN 4
+
struct hash
{
uint32_t n_buckets;
uint32_t n_elements;
uint32_t mask;
- uint32_t iv;
- uint64_t (*hash_function)(const void *key, uint32_t iv);
+ /** key/iv used for the hash function. No to be confused with the (key, value)
+ * keys for the actual hash map entries */
+ uint8_t hash_key[HASH_KEY_LEN];
+ uint64_t (*hash_function)(const void *key, const uint8_t hash_key[HASH_KEY_LEN]);
bool (*compare_function)(const void *key1, const void *key2); /* return true if equal */
struct hash_bucket *buckets;
};
-struct hash *hash_init(const uint32_t n_buckets, const uint32_t iv,
- uint64_t (*hash_function)(const void *key, uint32_t iv),
+struct hash *hash_init(const uint32_t n_buckets,
+ uint64_t (*hash_function)(const void *key, const uint8_t hash_key[HASH_KEY_LEN]),
bool (*compare_function)(const void *key1, const void *key2));
void hash_free(struct hash *hash);
@@ -103,7 +108,7 @@
static inline uint64_t
hash_value(const struct hash *hash, const void *key)
{
- return (*hash->hash_function)(key, hash->iv);
+ return (*hash->hash_function)(key, hash->hash_key);
}
static inline uint32_t
@@ -355,10 +355,10 @@
* and the actual address.
*/
uint64_t
-mroute_addr_hash_function(const void *key, uint32_t iv)
+mroute_addr_hash_function(const void *key, const uint8_t hash_key[HASH_KEY_LEN])
{
return hash_func(mroute_addr_hash_ptr((const struct mroute_addr *)key),
- mroute_addr_hash_len((const struct mroute_addr *)key), iv);
+ mroute_addr_hash_len((const struct mroute_addr *)key), *(uint32_t *)hash_key);
}
bool
@@ -144,7 +144,7 @@
bool mroute_learnable_address(const struct mroute_addr *addr, struct gc_arena *gc);
-uint64_t mroute_addr_hash_function(const void *key, uint32_t iv);
+uint64_t mroute_addr_hash_function(const void *key, const uint8_t hash_key[HASH_KEY_LEN]);
bool mroute_addr_compare_function(const void *key1, const void *key2);
@@ -229,7 +229,7 @@
#ifdef ENABLE_MANAGEMENT
static uint64_t
-cid_hash_function(const void *key, uint32_t iv)
+cid_hash_function(const void *key, const uint8_t hash_key[HASH_KEY_LEN])
{
const unsigned long *k = (const unsigned long *)key;
return (uint64_t)*k;
@@ -250,7 +250,7 @@
/*
* inotify watcher descriptors are used as hash value
*/
-int_hash_function(const void *key, uint32_t iv)
+int_hash_function(const void *key, const uint8_t hash_key[HASH_KEY_LEN])
{
return (uintptr_t)key;
}
@@ -290,18 +290,18 @@
* to determine which client sent an incoming packet
* which is seen on the TCP/UDP socket.
*/
- m->hash = hash_init(t->options.real_hash_size, (uint32_t)get_random(),
+ m->hash = hash_init(t->options.real_hash_size,
mroute_addr_hash_function, mroute_addr_compare_function);
/*
* Virtual address hash table. Used to determine
* which client to route a packet to.
*/
- m->vhash = hash_init(t->options.virtual_hash_size, (uint32_t)get_random(),
+ m->vhash = hash_init(t->options.virtual_hash_size,
mroute_addr_hash_function, mroute_addr_compare_function);
#ifdef ENABLE_MANAGEMENT
- m->cid_hash = hash_init(t->options.real_hash_size, 0, cid_hash_function, cid_compare_function);
+ m->cid_hash = hash_init(t->options.real_hash_size, cid_hash_function, cid_compare_function);
#endif
#ifdef ENABLE_ASYNC_PUSH
@@ -309,8 +309,8 @@
* Mapping between inotify watch descriptors and
* multi_instances.
*/
- m->inotify_watchers = hash_init(t->options.real_hash_size, (uint32_t)get_random(),
- int_hash_function, int_compare_function);
+ m->inotify_watchers =
+ hash_init(t->options.real_hash_size, int_hash_function, int_compare_function);
#endif
/*
@@ -128,11 +128,11 @@
static uint64_t
-word_hash_function(const void *key, uint32_t iv)
+word_hash_function(const void *key, const uint8_t hash_key[HASH_KEY_LEN])
{
const char *str = (const char *)key;
const uint32_t len = (uint32_t)strlen(str);
- return hash_func((const uint8_t *)str, len, iv);
+ return hash_func((const uint8_t *)str, len, *(uint32_t *)(hash_key));
}
static bool
@@ -174,10 +174,9 @@
* Test the hash code by implementing a simple
* word frequency algorithm.
*/
-
struct gc_arena gc = gc_new();
- struct hash *hash = hash_init(10000, get_random(), word_hash_function, word_compare_function);
- struct hash *nhash = hash_init(256, get_random(), word_hash_function, word_compare_function);
+ struct hash *hash = hash_init(10000, word_hash_function, word_compare_function);
+ struct hash *nhash = hash_init(256, word_hash_function, word_compare_function);
printf("hash_init n_buckets=%u mask=0x%08x\n", hash->n_buckets, hash->mask);