Commit 060193019a for openssl.org
commit 060193019ae75ca4dea1a8c14092502d48ea8500
Author: Neil Horman <nhorman@openssl.org>
Date: Sun Mar 1 15:18:30 2026 -0500
Add ability to extract computed hash from hashtable
One thing we can do to speed up hash table lookups is to cache/reuse
computed hash values when interrogating a hash table multiple times in
rapid succession.
We follow this pattern frequently when using hashtables:
value = lookup_hash(key)
if (value == NULL)
value = new_value()
insert_to_hash(key, value)
Note that we use the same key for the lookup and the insert. So if we
had a way to preserve the value this key hashed to, we can avoid having
to do a second hash computation during the lookup.
These new macros give us that. The HT_KEY structure now stores the
computed hash value in the key, which can be extracted and reused by the
caller with the HT_INIT_KEY_CACHED macro. When set, the cached hash
value is used, rather than needing to recompute the hash for any
subsequent operations
Reviewed-by: Paul Dale <paul.dale@oracle.com>
Reviewed-by: Saša Nedvědický <sashan@openssl.org>
MergeDate: Tue Mar 24 16:23:05 2026
(Merged from https://github.com/openssl/openssl/pull/30254)
diff --git a/crypto/hashtable/hashtable.c b/crypto/hashtable/hashtable.c
index af800c2cdf..065174feb7 100644
--- a/crypto/hashtable/hashtable.c
+++ b/crypto/hashtable/hashtable.c
@@ -700,12 +700,15 @@ int ossl_ht_insert(HT *h, HT_KEY *key, HT_VALUE *data, HT_VALUE **olddata)
if (newval == NULL)
goto out;
+ if (key->cached_hash)
+ hash = key->cached_hash;
+ else
+ hash = key->cached_hash = newval->value.key.cached_hash = h->config.ht_hash_fn(key);
+
/*
* we have to take our lock here to prevent other changes
* to the bucket list
*/
- hash = h->config.ht_hash_fn(key);
-
for (i = 0;
(rc = ossl_ht_insert_locked(h, hash, newval, olddata)) == -1
&& i < 4;
@@ -733,7 +736,10 @@ HT_VALUE *ossl_ht_get(HT *h, HT_KEY *key)
uint64_t ehash;
int lockless_reads = h->config.lockless_reads;
- hash = h->config.ht_hash_fn(key);
+ if (key->cached_hash)
+ hash = key->cached_hash;
+ else
+ hash = key->cached_hash = h->config.ht_hash_fn(key);
if (!h->config.no_rcu)
md = ossl_rcu_deref(&h->md);
@@ -792,7 +798,10 @@ int ossl_ht_delete(HT *h, HT_KEY *key)
if (h->config.lockless_reads)
return 0;
- hash = h->config.ht_hash_fn(key);
+ if (key->cached_hash)
+ hash = key->cached_hash;
+ else
+ hash = key->cached_hash = h->config.ht_hash_fn(key);
neigh_idx = hash & h->md->neighborhood_mask;
PREFETCH_NEIGHBORHOOD(h->md->neighborhoods[neigh_idx]);
diff --git a/include/internal/hashtable.h b/include/internal/hashtable.h
index 04b2d7f20a..320408bba4 100644
--- a/include/internal/hashtable.h
+++ b/include/internal/hashtable.h
@@ -23,6 +23,7 @@ typedef struct ht_internal_st HT;
* Represents a key to a hashtable
*/
typedef struct ht_key_header_st {
+ uint64_t cached_hash;
size_t keysize;
size_t bufsize;
uint8_t *keybuf;
@@ -169,10 +170,22 @@ static ossl_inline ossl_unused int ossl_key_raw_copy(HT_KEY *key, const uint8_t
(key)->keysize += tmplen; \
} while (0)
+#define HT_INIT_KEY_CACHED(key, hash) \
+ do { \
+ HT_INIT_KEY((key)); \
+ (key)->key_header.cached_hash = hash; \
+ } while (0)
+
+#define HT_KEY_GET_HASH(key) (key)->key_header.cached_hash
+
/*
* Resets a hash table key to a known state
*/
-#define HT_KEY_RESET(key) memset((key)->key_header.keybuf, 0, (key)->key_header.keysize)
+#define HT_KEY_RESET(key) \
+ do { \
+ memset((key)->key_header.keybuf, 0, (key)->key_header.keysize); \
+ (key)->key_header.cached_hash = 0; \
+ } while (0)
/*
* Sets a scalar field in a hash table key
diff --git a/test/lhash_test.c b/test/lhash_test.c
index 9f44ffb7ca..eae2999f4e 100644
--- a/test/lhash_test.c
+++ b/test/lhash_test.c
@@ -244,6 +244,7 @@ static int test_int_hashtable(int idx)
/* insert */
HT_INIT_KEY(&key);
for (i = 0; i < n_int_tests; i++) {
+ HT_KEY_RESET(&key);
HT_SET_KEY_FIELD(&key, mykey, int_tests[i]);
if (!TEST_int_eq(ossl_ht_test_int_insert(ht, TO_HT_KEY(&key),
&int_tests[i], NULL),
@@ -280,6 +281,7 @@ static int test_int_hashtable(int idx)
/* delete */
for (i = 0; i < n_dels; i++) {
+ HT_KEY_RESET(&key);
HT_SET_KEY_FIELD(&key, mykey, dels[i].data);
todel = ossl_ht_delete(ht, TO_HT_KEY(&key));
if (dels[i].should_del) {
@@ -439,6 +441,7 @@ static int test_hashtable_stress(int idx)
goto end;
}
*p = 3 * i + 1;
+ HT_KEY_RESET(&key);
HT_SET_KEY_FIELD(&key, mykey, *p);
if (!TEST_int_eq(ossl_ht_test_int_insert(h, TO_HT_KEY(&key),
p, NULL),
@@ -455,6 +458,7 @@ static int test_hashtable_stress(int idx)
/* delete or get in a different order */
for (i = 0; i < n; i++) {
const int j = (7 * i + 4) % n * 3 + 1;
+ HT_KEY_RESET(&key);
HT_SET_KEY_FIELD(&key, mykey, j);
switch (idx % 2) {