From: Arne Schwabe <[email protected]> While for our own hash function, always using an uint32_t works well, it does not work very well if we move to another hash function like siphash that requires a larger key.
To avoid allocating a specific context, change the API to be a fixed size array of size 4. This define allows use to easily change it to a larger value if we use hash functions that require larger keys. Change-Id: If47c7d920b2fa4047b7db03fcde821899839324d Signed-off-by: Arne Schwabe <[email protected]> Acked-by: Frank Lichtenheld <[email protected]> Gerrit URL: https://gerrit.openvpn.net/c/openvpn/+/1571 --- This change was reviewed on Gerrit and approved by at least one developer. I request to merge it to master. Gerrit URL: https://gerrit.openvpn.net/c/openvpn/+/1571 This mail reflects revision 21 of this Change. Acked-by according to Gerrit (reflected above): Frank Lichtenheld <[email protected]> diff --git a/src/openvpn/list.c b/src/openvpn/list.c index c07e764..e52c778 100644 --- a/src/openvpn/list.c +++ b/src/openvpn/list.c @@ -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) { diff --git a/src/openvpn/list.h b/src/openvpn/list.h index 06377c6..cbf1abf 100644 --- a/src/openvpn/list.h +++ b/src/openvpn/list.h @@ -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 diff --git a/src/openvpn/mroute.c b/src/openvpn/mroute.c index 78c689e..a5179d0 100644 --- a/src/openvpn/mroute.c +++ b/src/openvpn/mroute.c @@ -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 diff --git a/src/openvpn/mroute.h b/src/openvpn/mroute.h index 2f5d019..639281b 100644 --- a/src/openvpn/mroute.h +++ b/src/openvpn/mroute.h @@ -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); diff --git a/src/openvpn/multi.c b/src/openvpn/multi.c index f823f5b..cfa2ad8 100644 --- a/src/openvpn/multi.c +++ b/src/openvpn/multi.c @@ -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 /* diff --git a/tests/unit_tests/openvpn/test_misc.c b/tests/unit_tests/openvpn/test_misc.c index fc9840a..501286c 100644 --- a/tests/unit_tests/openvpn/test_misc.c +++ b/tests/unit_tests/openvpn/test_misc.c @@ -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); _______________________________________________ Openvpn-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/openvpn-devel
