Commit 039fa4958e for openssl.org
commit 039fa4958efc7acee16e9896103cbfdd249a10df
Author: Daniel Kubec <kubec@openssl.foundation>
Date: Sat Oct 31 15:45:37 2026 +0100
QUIC: mix the hashes of the SRTM, LCIDM and stream map tables
OPENSSL_LHASH takes a bucket as the hash modulo a power of two
(getrn() in crypto/lhash/lhash.c), without mixing, so a hash callback
must spread its low bits itself. Three QUIC tables did not:
- quic_srtm.c items_fwd_hash() and quic_lcidm.c lcidm_conn_hash()
returned the connection's opaque pointer as is. A pointer's low bits
are its allocation alignment, and QUIC_CHANNEL objects of one size come
from the allocator at a fixed stride (1728 bytes for the 1720-byte
channel of this tree, 64 low zero bits of six), so the connections of a
port shared one bucket in 64 and every add, remove, retire and cull
walked a chain that grew with the connection count: 4x the cost of a
spread hash at 4096 connections, and worse at larger strides (a page
stride puts every connection in one bucket).
- quic_stream_map.c hash_stream() returned the stream ID as is. The low
two bits of an ID are its initiator and direction, so a map holding
mostly one kind of stream (an HTTP/3 connection's request streams) used
a quarter of its buckets and its chains were four times as long.
Mix the pointers with the splitmix64 finaliser, added to
internal/hashfunc.h as ossl_hash_mix64() with LHASH-typed wrappers
ossl_lh_hash_u64() and ossl_lh_hash_ptr(), and fold a stream ID's
sequence bits into its type bits with id ^ (id >> 2): a bijection on each
block of 16 IDs, so a dense sequence stays dense whether it comes from
one stream type or from all four, which a general mix would spread at
random and cost on the interleaved pattern.
measure (ns/op) before after
SRTM add, 1728 B stride 1066 272
SRTM add, 4096 B stride 15551 271
LCIDM enrol, 1728 B 1440 666
LCIDM enrol, 4096 B 18461 664
After the change the SRTM and LCIDM costs no longer depend on the
pointer stride, and the stream map no longer depends on which stream
types a connection uses.
Co-authored-by: Mounir IDRASSI <mounir.idrassi@amcrypto.jp>
Assisted-by: Claude:claude-fable-5-1
Reviewed-by: Mounir Idrassi <mounir.idrassi@idrix.fr>
Reviewed-by: Saša Nedvědický <sashan@openssl.org>
Reviewed-by: Nikola Pajkovsky <nikolap@openssl.org>
Reviewed-by: Eugene Syromiatnikov <esyr@openssl.org>
Merge-date: Tue Nov 3 13:12:11 2026
Merged-from: https://github.com/openssl/openssl/pull/33466
diff --git a/include/internal/hashfunc.h b/include/internal/hashfunc.h
index 78d7c859d5..a8f66cf8e7 100644
--- a/include/internal/hashfunc.h
+++ b/include/internal/hashfunc.h
@@ -12,9 +12,47 @@
#include <openssl/e_os2.h>
#include <stddef.h>
+#include <limits.h>
+
/**
* Generalized fnv1a 64 bit hash function
*/
ossl_unused uint64_t ossl_fnv1a_hash(uint8_t *key, size_t len);
+/*
+ * Mix a 64-bit value so that every bit of the result depends on every bit
+ * of the input (the splitmix64 finaliser). An LHASH bucket is the hash
+ * modulo a power of two, so a hash that is a raw integer or pointer must be
+ * mixed first: a pointer's low bits are its allocation alignment, and
+ * objects of one size from the allocator sit at a fixed stride, so without
+ * mixing they share a handful of buckets and the chains grow with the
+ * number of objects. Likewise an integer whose low bits are a type tag.
+ */
+static ossl_unused ossl_inline uint64_t ossl_hash_mix64(uint64_t x)
+{
+ x ^= x >> 30;
+ x *= 0xbf58476d1ce4e5b9ULL;
+ x ^= x >> 27;
+ x *= 0x94d049bb133111ebULL;
+ x ^= x >> 31;
+ return x;
+}
+
+/* A 64-bit value, mixed, as an LHASH hash value. */
+static ossl_unused ossl_inline unsigned long ossl_lh_hash_u64(uint64_t x)
+{
+ x = ossl_hash_mix64(x);
+#if ULONG_MAX > 0xFFFFFFFFUL
+ return (unsigned long)x;
+#else
+ return (unsigned long)(x ^ (x >> 32));
+#endif
+}
+
+/* A pointer's identity, mixed, as an LHASH hash value. */
+static ossl_unused ossl_inline unsigned long ossl_lh_hash_ptr(const void *p)
+{
+ return ossl_lh_hash_u64((uint64_t)(uintptr_t)p);
+}
+
#endif
diff --git a/ssl/quic/quic_lcidm.c b/ssl/quic/quic_lcidm.c
index 89ee95055d..e56a93dffc 100644
--- a/ssl/quic/quic_lcidm.c
+++ b/ssl/quic/quic_lcidm.c
@@ -11,6 +11,7 @@
#include "internal/quic_types.h"
#include "internal/quic_vlint.h"
#include "internal/common.h"
+#include "internal/hashfunc.h"
#include "crypto/siphash.h"
#include <openssl/lhash.h>
#include <openssl/rand.h>
@@ -100,7 +101,7 @@ static int lcid_comp(const QUIC_LCID *a, const QUIC_LCID *b)
static unsigned long lcidm_conn_hash(const QUIC_LCIDM_CONN *conn)
{
- return (unsigned long)(uintptr_t)conn->opaque;
+ return ossl_lh_hash_ptr(conn->opaque);
}
static int lcidm_conn_comp(const QUIC_LCIDM_CONN *a, const QUIC_LCIDM_CONN *b)
diff --git a/ssl/quic/quic_srtm.c b/ssl/quic/quic_srtm.c
index e17433a6aa..02a67e3de4 100644
--- a/ssl/quic/quic_srtm.c
+++ b/ssl/quic/quic_srtm.c
@@ -9,6 +9,7 @@
#include "internal/quic_srtm.h"
#include "internal/common.h"
+#include "internal/hashfunc.h"
#include <openssl/lhash.h>
#include <openssl/core_names.h>
#include <openssl/rand.h>
@@ -68,7 +69,7 @@ struct quic_srtm_st {
static unsigned long items_fwd_hash(const SRTM_ITEM *item)
{
- return (unsigned long)(uintptr_t)item->opaque;
+ return ossl_lh_hash_ptr(item->opaque);
}
static int items_fwd_cmp(const SRTM_ITEM *a, const SRTM_ITEM *b)
diff --git a/ssl/quic/quic_stream_map.c b/ssl/quic/quic_stream_map.c
index 2d58d08a80..832b3ae996 100644
--- a/ssl/quic/quic_stream_map.c
+++ b/ssl/quic/quic_stream_map.c
@@ -74,7 +74,14 @@ static QUIC_STREAM *list_next(QUIC_STREAM_LIST_NODE *l, QUIC_STREAM_LIST_NODE *n
static unsigned long hash_stream(const QUIC_STREAM *s)
{
- return (unsigned long)s->id;
+ /*
+ * The low two bits of a stream ID identify its initiator and direction.
+ * Folding in bits from the stream ordinal improves bucket use for
+ * consecutive IDs of one type. With mixed stream types, this can produce
+ * longer chains than the original hash at some intermediate table sizes
+ * while LHASH expands.
+ */
+ return (unsigned long)(s->id ^ (s->id >> 2));
}
static int cmp_stream(const QUIC_STREAM *a, const QUIC_STREAM *b)