[PATCH v5 5/7] hash: add support for common small key sizes

Stephen Hemminger
2026-01-30T20:24:04Z

Add new compare functions for common small key sizes.

Fill in more key sizes to ensure more complete coverage of
special cases.

Bugzilla ID: 1775
Reported-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Suggested-by: Morten Brørup <mb@smartsharesystems.com>

Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
Acked-by: Morten Brørup <mb@smartsharesystems.com>
---
app/test/test_hash.c | 12 +-
lib/hash/rte_cuckoo_hash.c | 233 +++++++++++++++++++++++++++----------
2 files changed, 179 insertions(+), 66 deletions(-)

diff --git a/app/test/test_hash.c b/app/test/test_hash.c
index a70e2620c0..1d140ec2cc 100644
--- a/app/test/test_hash.c
+++ b/app/test/test_hash.c
@@ -35,8 +35,16 @@
*/
static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
static uint32_t hashtest_initvals[] = {0};
-static uint32_t hashtest_key_lens[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64};
-#define MAX_KEYSIZE 64
+
+/*
+ * Test common hash key lengths. Make sure and cover all the special cases
+ * in the cmp_jump_table.
+ */
+static uint32_t hashtest_key_lens[] = {
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18, 20,
+ 21, 31, 32, 33, 36, 48, 63, 64, 80, 96, 112, 128, 254
+};
+#define MAX_KEYSIZE 256
/******************************************************************************/
#define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)

diff --git a/lib/hash/rte_cuckoo_hash.c b/lib/hash/rte_cuckoo_hash.c
index ce66308c5e..e8e625b369 100644
--- a/lib/hash/rte_cuckoo_hash.c
+++ b/lib/hash/rte_cuckoo_hash.c
@@ -49,9 +49,20 @@ RTE_LOG_REGISTER_DEFAULT(hash_logtype, INFO);
* Not in rte_cuckoo_hash.h to avoid ABI issues.
*/
enum cmp_jump_table_case {
- KEY_CUSTOM = 0,
+ KEY_CUSTOM,
+ KEY_2_BYTES,
+ KEY_3_BYTES,
+ KEY_4_BYTES,
+ KEY_5_BYTES,
+ KEY_6_BYTES,
+ KEY_8_BYTES,
+ KEY_10_BYTES,
+ KEY_12_BYTES,
+ KEY_14_BYTES,
KEY_16_BYTES,
+ KEY_20_BYTES,
KEY_32_BYTES,
+ KEY_36_BYTES,
KEY_48_BYTES,
KEY_64_BYTES,
KEY_80_BYTES,
@@ -62,6 +73,17 @@ enum cmp_jump_table_case {
NUM_KEY_CMP_CASES,
};

+/* Table of custom key sizes. */
+static const unsigned int cmp_jump_key_size[] = {
+ 0, /* Custom */
+ 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, 20,
+ 32, 36, 48, 64, 80, 96, 112, 128,
+ UINT32_MAX /* Other */
+};
+
+static_assert(RTE_DIM(cmp_jump_key_size) == NUM_KEY_CMP_CASES,
+ "cmp_jump_key_size table mismatch");
+
/*
* Comparison functions for different key sizes.
* Each function is only called with a specific fixed key size.
@@ -85,56 +107,154 @@ enum cmp_jump_table_case {
#include "rte_cmp_generic.h"
#endif

+static inline int
+rte_hash_k2_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ const unaligned_uint16_t *k1 = key1;
+ const unaligned_uint16_t *k2 = key2;
+
+ return !!(k1[0] ^ k2[0]);
+}
+
+static int
+rte_hash_k3_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ return rte_hash_k2_cmp_eq(key1, key2, 2)
+ | (((const uint8_t *)key1)[2] ^ ((const uint8_t *)key2)[2]);
+}
+
+static inline int
+rte_hash_k4_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ const unaligned_uint32_t *k1 = key1;
+ const unaligned_uint32_t *k2 = key2;
+
+ return !!(k1[0] ^ k2[0]);
+}
+
+static int
+rte_hash_k5_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ const uint8_t *k1 = key1;
+ const uint8_t *k2 = key2;
+
+ return rte_hash_k4_cmp_eq(key1, key2, 4) | (k1[4] ^ k2[4]);
+}
+
+static int
+rte_hash_k6_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ const unaligned_uint16_t *k1 = key1;
+ const unaligned_uint16_t *k2 = key2;
+
+ return !!((k1[0] ^ k2[0]) | (k1[1] ^ k2[1]) | (k1[2] ^ k2[2]));
+}
+
+static inline int
+rte_hash_k8_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+#ifdef RTE_ARCH_64
+ const unaligned_uint64_t *k1 = key1;
+ const unaligned_uint64_t *k2 = key2;
+
+ return !!(k1[0] ^ k2[0]);
+#else
+ const unaligned_uint32_t *k1 = key1;
+ const unaligned_uint32_t *k2 = key2;
+
+ return (k1[0] ^ k2[0]) | (k1[1] ^ k2[1]);
+#endif
+}
+
+static int
+rte_hash_k10_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ return rte_hash_k8_cmp_eq(key1, key2, 8) |
+ rte_hash_k2_cmp_eq((const uint8_t *)key1 + 8,
+ (const uint8_t *)key2 + 8, 2);
+}
+
static int
-rte_hash_k48_cmp_eq(const void *key1, const void *key2, size_t key_len)
+rte_hash_k12_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
{
- return rte_hash_k16_cmp_eq(key1, key2, key_len) |
- rte_hash_k16_cmp_eq((const uint8_t *) key1 + 16,
- (const uint8_t *) key2 + 16, key_len) |
- rte_hash_k16_cmp_eq((const uint8_t *) key1 + 32,
- (const uint8_t *) key2 + 32, key_len);
+ const unaligned_uint32_t *k1 = key1;
+ const unaligned_uint32_t *k2 = key2;
+
+ return !!((k1[0] ^ k2[0]) | (k1[1] ^ k2[1]) | (k1[2] ^ k2[2]));
}

static int
-rte_hash_k64_cmp_eq(const void *key1, const void *key2, size_t key_len)
+rte_hash_k14_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
{
- return rte_hash_k32_cmp_eq(key1, key2, key_len) |
- rte_hash_k32_cmp_eq((const uint8_t *) key1 + 32,
- (const uint8_t *) key2 + 32, key_len);
+ return rte_hash_k8_cmp_eq(key1, key2, 8) |
+ rte_hash_k6_cmp_eq((const uint8_t *)key1 + 8,
+ (const uint8_t *)key2 + 8, 6);
}

static int
-rte_hash_k80_cmp_eq(const void *key1, const void *key2, size_t key_len)
+rte_hash_k20_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
{
- return rte_hash_k64_cmp_eq(key1, key2, key_len) |
- rte_hash_k16_cmp_eq((const uint8_t *) key1 + 64,
- (const uint8_t *) key2 + 64, key_len);
+ return rte_hash_k16_cmp_eq(key1, key2, 16) |
+ rte_hash_k4_cmp_eq((const uint8_t *)key1 + 16,
+ (const uint8_t *)key2 + 16, 4);
}

static int
-rte_hash_k96_cmp_eq(const void *key1, const void *key2, size_t key_len)
+rte_hash_k36_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
{
- return rte_hash_k64_cmp_eq(key1, key2, key_len) |
- rte_hash_k32_cmp_eq((const uint8_t *) key1 + 64,
- (const uint8_t *) key2 + 64, key_len);
+ return rte_hash_k32_cmp_eq(key1, key2, 32) |
+ rte_hash_k4_cmp_eq((const uint8_t *)key1 + 32,
+ (const uint8_t *)key2 + 32, 4);
}

static int
-rte_hash_k112_cmp_eq(const void *key1, const void *key2, size_t key_len)
+rte_hash_k48_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ return rte_hash_k32_cmp_eq(key1, key2, 32) |
+ rte_hash_k16_cmp_eq((const uint8_t *)key1 + 32,
+ (const uint8_t *)key2 + 32, 16);
+}
+
+static inline int
+rte_hash_k64_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
{
- return rte_hash_k64_cmp_eq(key1, key2, key_len) |
- rte_hash_k32_cmp_eq((const uint8_t *) key1 + 64,
- (const uint8_t *) key2 + 64, key_len) |
- rte_hash_k16_cmp_eq((const uint8_t *) key1 + 96,
- (const uint8_t *) key2 + 96, key_len);
+ return rte_hash_k32_cmp_eq(key1, key2, 32) |
+ rte_hash_k32_cmp_eq((const uint8_t *)key1 + 32,
+ (const uint8_t *)key2 + 32, 32);
}

static int
-rte_hash_k128_cmp_eq(const void *key1, const void *key2, size_t key_len)
+rte_hash_k80_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
{
- return rte_hash_k64_cmp_eq(key1, key2, key_len) |
- rte_hash_k64_cmp_eq((const uint8_t *) key1 + 64,
- (const uint8_t *) key2 + 64, key_len);
+ return rte_hash_k64_cmp_eq(key1, key2, 64) |
+ rte_hash_k16_cmp_eq((const uint8_t *)key1 + 64,
+ (const uint8_t *)key2 + 64, 64);
+}
+
+static int
+rte_hash_k96_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ return rte_hash_k64_cmp_eq(key1, key2, 64) |
+ rte_hash_k32_cmp_eq((const uint8_t *)key1 + 64,
+ (const uint8_t *)key2 + 64, 32);
+}
+
+static int
+rte_hash_k112_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ return rte_hash_k64_cmp_eq(key1, key2, 64) |
+ rte_hash_k32_cmp_eq((const uint8_t *)key1 + 64,
+ (const uint8_t *)key2 + 64, 32) |
+ rte_hash_k16_cmp_eq((const uint8_t *)key1 + 96,
+ (const uint8_t *)key2 + 96, 16);
+}
+
+static int
+rte_hash_k128_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ return rte_hash_k64_cmp_eq(key1, key2, 64) |
+ rte_hash_k64_cmp_eq((const uint8_t *)key1 + 64,
+ (const uint8_t *)key2 + 64, 64);
}

/* Enum used to select the implementation of the signature comparison function to use
@@ -226,8 +346,19 @@ void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func)
*/
static const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
[KEY_CUSTOM] = NULL,
+ [KEY_2_BYTES] = rte_hash_k2_cmp_eq,
+ [KEY_3_BYTES] = rte_hash_k3_cmp_eq,
+ [KEY_4_BYTES] = rte_hash_k4_cmp_eq,
+ [KEY_5_BYTES] = rte_hash_k5_cmp_eq,
+ [KEY_6_BYTES] = rte_hash_k6_cmp_eq,
+ [KEY_8_BYTES] = rte_hash_k8_cmp_eq,
+ [KEY_10_BYTES] = rte_hash_k10_cmp_eq,
+ [KEY_12_BYTES] = rte_hash_k12_cmp_eq,
+ [KEY_14_BYTES] = rte_hash_k14_cmp_eq,
[KEY_16_BYTES] = rte_hash_k16_cmp_eq,
+ [KEY_20_BYTES] = rte_hash_k20_cmp_eq,
[KEY_32_BYTES] = rte_hash_k32_cmp_eq,
+ [KEY_36_BYTES] = rte_hash_k36_cmp_eq,
[KEY_48_BYTES] = rte_hash_k48_cmp_eq,
[KEY_64_BYTES] = rte_hash_k64_cmp_eq,
[KEY_80_BYTES] = rte_hash_k80_cmp_eq,
@@ -510,41 +641,15 @@ rte_hash_create(const struct rte_hash_parameters *params)
goto err_unlock;
}

- /* Select function to compare keys */
- switch (params->key_len) {
-#if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
- /*
- * If x86 architecture is used, select appropriate compare function,
- * which may use x86 intrinsics, otherwise use memcmp
- */
- case 16:
- h->cmp_jump_table_idx = KEY_16_BYTES;
- break;
- case 32:
- h->cmp_jump_table_idx = KEY_32_BYTES;
- break;
- case 48:
- h->cmp_jump_table_idx = KEY_48_BYTES;
- break;
- case 64:
- h->cmp_jump_table_idx = KEY_64_BYTES;
- break;
- case 80:
- h->cmp_jump_table_idx = KEY_80_BYTES;
- break;
- case 96:
- h->cmp_jump_table_idx = KEY_96_BYTES;
- break;
- case 112:
- h->cmp_jump_table_idx = KEY_112_BYTES;
- break;
- case 128:
- h->cmp_jump_table_idx = KEY_128_BYTES;
- break;
-#endif
- default:
- /* If key is not multiple of 16, use generic memcmp */
- h->cmp_jump_table_idx = KEY_OTHER_BYTES;
+ /* fallback if no special case */
+ h->cmp_jump_table_idx = KEY_OTHER_BYTES;
+
+ /* Search table of enum values, 0 is reserved for custom */
+ for (unsigned int key_idx = KEY_2_BYTES; key_idx < KEY_OTHER_BYTES; key_idx++) {
+ if (params->key_len == cmp_jump_key_size[key_idx]) {
+ h->cmp_jump_table_idx = key_idx;
+ break;
+ }
}

if (use_local_cache) {
--
2.51.0