From d1106970f76e955b0a5fa19b566e97bba98d4c9b Mon Sep 17 00:00:00 2001 From: Arne Schwabe Date: Thu, 6 Aug 2026 12:29:21 +0200 Subject: [PATCH] Change hash iv to a be a fixed sized array 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 Acked-by: Frank Lichtenheld Gerrit URL: https://gerrit.openvpn.net/c/openvpn/+/1571 Message-Id: <20260806102926.28206-1-gert@greenie.muc.de> URL: https://www.mail-archive.com/openvpn-devel@lists.sourceforge.net/msg38162.html Signed-off-by: Gert Doering --- src/openvpn/list.c | 11 ++++++++--- src/openvpn/list.h | 15 ++++++++++----- src/openvpn/mroute.c | 4 ++-- src/openvpn/mroute.h | 2 +- src/openvpn/multi.c | 14 +++++++------- tests/unit_tests/openvpn/test_misc.c | 9 ++++----- 6 files changed, 32 insertions(+), 23 deletions(-) diff --git a/src/openvpn/list.c b/src/openvpn/list.c index c07e764f2..e52c77861 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 @@ hash_init(const uint32_t n_buckets, const uint32_t iv, 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 06377c6ce..cbf1abf36 100644 --- a/src/openvpn/list.h +++ b/src/openvpn/list.h @@ -49,19 +49,24 @@ struct hash_bucket 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 @@ uint64_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval); 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 78c689e3d..a5179d00f 100644 --- a/src/openvpn/mroute.c +++ b/src/openvpn/mroute.c @@ -355,10 +355,10 @@ mroute_addr_mask_host_bits(struct mroute_addr *ma) * 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 2f5d01931..639281bef 100644 --- a/src/openvpn/mroute.h +++ b/src/openvpn/mroute.h @@ -144,7 +144,7 @@ bool mroute_extract_openvpn_sockaddr(struct mroute_addr *addr, 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 fe2badbfd..a4e9c1c80 100644 --- a/src/openvpn/multi.c +++ b/src/openvpn/multi.c @@ -229,7 +229,7 @@ reap_buckets_per_pass(uint32_t n_buckets) #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 @@ static uint64_t /* * 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 @@ multi_init(struct context *t) * 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 @@ multi_init(struct context *t) * 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 4d046ceb4..3ebbfc159 100644 --- a/tests/unit_tests/openvpn/test_misc.c +++ b/tests/unit_tests/openvpn/test_misc.c @@ -131,11 +131,11 @@ struct word 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 @@ -170,10 +170,9 @@ test_list(void **state) * 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); -- 2.47.3