[dpdk-dev] [PATCH v5 1/7] hash: replace existing hash library with cuckoo hash implementation
Pablo de Lara
pablo.de.lara.guarch at intel.com
Fri Jul 10 23:57:41 CEST 2015
This patch replaces the existing hash library with another approach,
using the Cuckoo Hash method to resolve collisions (open addressing),
which pushes items from a full bucket when a new entry tries
to be added in it, storing the evicted entry in an alternative location,
using a secondary hash function.
This gives the user the ability to store more entries when a bucket
is full, in comparison with the previous implementation.
Therefore, the unit test has been updated, as some scenarios have changed
(such as the previous removed restriction).
Also note that the API has not been changed, although new fields
have been added in the rte_hash structure (structure is internal now).
The main change when creating a new table is that the number of entries
per bucket is fixed now, so its parameter is ignored now
(still there to maintain the same parameters structure).
The hash unit test has been updated to reflect these changes.
As a last note, the maximum burst size in lookup_burst function
hash been increased to 64, to improve performance.
Signed-off-by: Pablo de Lara <pablo.de.lara.guarch at intel.com>
---
app/test/test_hash.c | 119 ++---
app/test/test_hash_perf.c | 79 ++-
lib/librte_hash/Makefile | 8 +-
lib/librte_hash/rte_cuckoo_hash.c | 1027 +++++++++++++++++++++++++++++++++++++
lib/librte_hash/rte_hash.c | 499 ------------------
lib/librte_hash/rte_hash.h | 69 +--
6 files changed, 1138 insertions(+), 663 deletions(-)
create mode 100644 lib/librte_hash/rte_cuckoo_hash.c
delete mode 100644 lib/librte_hash/rte_hash.c
diff --git a/app/test/test_hash.c b/app/test/test_hash.c
index 7c71ed6..e70d859 100644
--- a/app/test/test_hash.c
+++ b/app/test/test_hash.c
@@ -169,7 +169,6 @@ static struct flow_key keys[5] = { {
/* Parameters used for hash table in unit test functions. Name set later. */
static struct rte_hash_parameters ut_params = {
.entries = 64,
- .bucket_entries = 4,
.key_len = sizeof(struct flow_key), /* 13 */
.hash_func = rte_jhash,
.hash_func_init_val = 0,
@@ -516,9 +515,18 @@ static int test_five_keys(void)
pos[i] = rte_hash_lookup(handle, &keys[i]);
print_key_info("Lkp", &keys[i], pos[i]);
RETURN_IF_ERROR(pos[i] != -ENOENT,
- "failed to find key (pos[%u]=%d)", i, pos[i]);
+ "found non-existent key (pos[%u]=%d)", i, pos[i]);
}
+ /* Lookup multi */
+ ret = rte_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos);
+ if (ret == 0)
+ for (i = 0; i < 5; i++) {
+ print_key_info("Lkp", key_array[i], pos[i]);
+ RETURN_IF_ERROR(pos[i] != -ENOENT,
+ "found not-existent key (pos[%u]=%d)", i, pos[i]);
+ }
+
rte_hash_free(handle);
return 0;
@@ -527,21 +535,18 @@ static int test_five_keys(void)
/*
* Add keys to the same bucket until bucket full.
* - add 5 keys to the same bucket (hash created with 4 keys per bucket):
- * first 4 successful, 5th unsuccessful
- * - lookup the 5 keys: 4 hits, 1 miss
- * - add the 5 keys again: 4 OK, one error as bucket is full
- * - lookup the 5 keys: 4 hits (updated data), 1 miss
- * - delete the 5 keys: 5 OK (even if the 5th is not in the table)
+ * first 4 successful, 5th successful, pushing existing item in bucket
+ * - lookup the 5 keys: 5 hits
+ * - add the 5 keys again: 5 OK
+ * - lookup the 5 keys: 5 hits (updated data)
+ * - delete the 5 keys: 5 OK
* - lookup the 5 keys: 5 misses
- * - add the 5th key: OK
- * - lookup the 5th key: hit
*/
static int test_full_bucket(void)
{
struct rte_hash_parameters params_pseudo_hash = {
.name = "test4",
.entries = 64,
- .bucket_entries = 4,
.key_len = sizeof(struct flow_key), /* 13 */
.hash_func = pseudo_hash,
.hash_func_init_val = 0,
@@ -555,7 +560,7 @@ static int test_full_bucket(void)
handle = rte_hash_create(¶ms_pseudo_hash);
RETURN_IF_ERROR(handle == NULL, "hash creation failed");
- /* Fill bucket*/
+ /* Fill bucket */
for (i = 0; i < 4; i++) {
pos[i] = rte_hash_add_key(handle, &keys[i]);
print_key_info("Add", &keys[i], pos[i]);
@@ -563,47 +568,39 @@ static int test_full_bucket(void)
"failed to add key (pos[%u]=%d)", i, pos[i]);
expected_pos[i] = pos[i];
}
- /* This shouldn't work because the bucket is full */
+ /*
+ * This should work and will push one of the items
+ * in the bucket because it is full
+ */
pos[4] = rte_hash_add_key(handle, &keys[4]);
print_key_info("Add", &keys[4], pos[4]);
- RETURN_IF_ERROR(pos[4] != -ENOSPC,
- "fail: added key to full bucket (pos[4]=%d)", pos[4]);
+ RETURN_IF_ERROR(pos[4] < 0,
+ "failed to add key (pos[4]=%d)", pos[4]);
+ expected_pos[4] = pos[4];
/* Lookup */
- for (i = 0; i < 4; i++) {
+ for (i = 0; i < 5; i++) {
pos[i] = rte_hash_lookup(handle, &keys[i]);
print_key_info("Lkp", &keys[i], pos[i]);
RETURN_IF_ERROR(pos[i] != expected_pos[i],
"failed to find key (pos[%u]=%d)", i, pos[i]);
}
- pos[4] = rte_hash_lookup(handle, &keys[4]);
- print_key_info("Lkp", &keys[4], pos[4]);
- RETURN_IF_ERROR(pos[4] != -ENOENT,
- "fail: found non-existent key (pos[4]=%d)", pos[4]);
/* Add - update */
- for (i = 0; i < 4; i++) {
+ for (i = 0; i < 5; i++) {
pos[i] = rte_hash_add_key(handle, &keys[i]);
print_key_info("Add", &keys[i], pos[i]);
RETURN_IF_ERROR(pos[i] != expected_pos[i],
"failed to add key (pos[%u]=%d)", i, pos[i]);
}
- pos[4] = rte_hash_add_key(handle, &keys[4]);
- print_key_info("Add", &keys[4], pos[4]);
- RETURN_IF_ERROR(pos[4] != -ENOSPC,
- "fail: added key to full bucket (pos[4]=%d)", pos[4]);
/* Lookup */
- for (i = 0; i < 4; i++) {
+ for (i = 0; i < 5; i++) {
pos[i] = rte_hash_lookup(handle, &keys[i]);
print_key_info("Lkp", &keys[i], pos[i]);
RETURN_IF_ERROR(pos[i] != expected_pos[i],
"failed to find key (pos[%u]=%d)", i, pos[i]);
}
- pos[4] = rte_hash_lookup(handle, &keys[4]);
- print_key_info("Lkp", &keys[4], pos[4]);
- RETURN_IF_ERROR(pos[4] != -ENOENT,
- "fail: found non-existent key (pos[4]=%d)", pos[4]);
/* Delete 1 key, check other keys are still found */
pos[1] = rte_hash_del_key(handle, &keys[1]);
@@ -623,35 +620,21 @@ static int test_full_bucket(void)
RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]);
/* Delete */
- for (i = 0; i < 4; i++) {
+ for (i = 0; i < 5; i++) {
pos[i] = rte_hash_del_key(handle, &keys[i]);
print_key_info("Del", &keys[i], pos[i]);
RETURN_IF_ERROR(pos[i] != expected_pos[i],
"failed to delete key (pos[%u]=%d)", i, pos[i]);
}
- pos[4] = rte_hash_del_key(handle, &keys[4]);
- print_key_info("Del", &keys[4], pos[4]);
- RETURN_IF_ERROR(pos[4] != -ENOENT,
- "fail: deleted non-existent key (pos[4]=%d)", pos[4]);
/* Lookup */
- for (i = 0; i < 4; i++) {
+ for (i = 0; i < 5; i++) {
pos[i] = rte_hash_lookup(handle, &keys[i]);
print_key_info("Lkp", &keys[i], pos[i]);
RETURN_IF_ERROR(pos[i] != -ENOENT,
"fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
}
- /* Add and lookup the 5th key */
- pos[4] = rte_hash_add_key(handle, &keys[4]);
- print_key_info("Add", &keys[4], pos[4]);
- RETURN_IF_ERROR(pos[4] < 0, "failed to add key (pos[4]=%d)", pos[4]);
- expected_pos[4] = pos[4];
- pos[4] = rte_hash_lookup(handle, &keys[4]);
- print_key_info("Lkp", &keys[4], pos[4]);
- RETURN_IF_ERROR(pos[4] != expected_pos[4],
- "failed to find key (pos[4]=%d)", pos[4]);
-
rte_hash_free(handle);
/* Cover the NULL case. */
@@ -991,6 +974,7 @@ static int test_fbk_hash_find_existing(void)
return 0;
}
+#define BUCKET_ENTRIES 4
/*
* Do tests for hash creation with bad parameters.
*/
@@ -1017,18 +1001,8 @@ static int test_hash_creation_with_bad_parameters(void)
}
memcpy(¶ms, &ut_params, sizeof(params));
- params.name = "creation_with_bad_parameters_1";
- params.bucket_entries = RTE_HASH_BUCKET_ENTRIES_MAX + 1;
- handle = rte_hash_create(¶ms);
- if (handle != NULL) {
- rte_hash_free(handle);
- printf("Impossible creating hash sucessfully with bucket_entries in parameter exceeded\n");
- return -1;
- }
-
- memcpy(¶ms, &ut_params, sizeof(params));
params.name = "creation_with_bad_parameters_2";
- params.entries = params.bucket_entries - 1;
+ params.entries = BUCKET_ENTRIES - 1;
handle = rte_hash_create(¶ms);
if (handle != NULL) {
rte_hash_free(handle);
@@ -1038,26 +1012,6 @@ static int test_hash_creation_with_bad_parameters(void)
memcpy(¶ms, &ut_params, sizeof(params));
params.name = "creation_with_bad_parameters_3";
- params.entries = params.entries - 1;
- handle = rte_hash_create(¶ms);
- if (handle != NULL) {
- rte_hash_free(handle);
- printf("Impossible creating hash sucessfully if entries in parameter is not power of 2\n");
- return -1;
- }
-
- memcpy(¶ms, &ut_params, sizeof(params));
- params.name = "creation_with_bad_parameters_4";
- params.bucket_entries = params.bucket_entries - 1;
- handle = rte_hash_create(¶ms);
- if (handle != NULL) {
- rte_hash_free(handle);
- printf("Impossible creating hash sucessfully if bucket_entries in parameter is not power of 2\n");
- return -1;
- }
-
- memcpy(¶ms, &ut_params, sizeof(params));
- params.name = "creation_with_bad_parameters_5";
params.key_len = 0;
handle = rte_hash_create(¶ms);
if (handle != NULL) {
@@ -1067,17 +1021,7 @@ static int test_hash_creation_with_bad_parameters(void)
}
memcpy(¶ms, &ut_params, sizeof(params));
- params.name = "creation_with_bad_parameters_6";
- params.key_len = RTE_HASH_KEY_LENGTH_MAX + 1;
- handle = rte_hash_create(¶ms);
- if (handle != NULL) {
- rte_hash_free(handle);
- printf("Impossible creating hash sucessfully if key_len is greater than the maximum\n");
- return -1;
- }
-
- memcpy(¶ms, &ut_params, sizeof(params));
- params.name = "creation_with_bad_parameters_7";
+ params.name = "creation_with_bad_parameters_4";
params.socket_id = RTE_MAX_NUMA_NODES + 1;
handle = rte_hash_create(¶ms);
if (handle != NULL) {
@@ -1214,7 +1158,6 @@ static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,
static struct rte_hash_parameters hash_params_ex = {
.name = NULL,
.entries = 64,
- .bucket_entries = 4,
.key_len = 0,
.hash_func = NULL,
.hash_func_init_val = 0,
diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c
index a3876c1..a54f3c1 100644
--- a/app/test/test_hash_perf.c
+++ b/app/test/test_hash_perf.c
@@ -162,7 +162,7 @@ shuffle_input_keys(unsigned table_index)
* ALL can fit in hash table (no errors)
*/
static int
-get_input_keys(unsigned table_index)
+get_input_keys(unsigned with_pushes, unsigned table_index)
{
unsigned i, j;
unsigned bucket_idx, incr, success = 1;
@@ -216,9 +216,14 @@ get_input_keys(unsigned table_index)
success = 0;
signatures[i] = rte_hash_hash(h[table_index], keys[i]);
bucket_idx = signatures[i] & bucket_bitmask;
- /* If bucket is full, do not try to insert the key */
- if (buckets[bucket_idx] == BUCKET_SIZE)
- continue;
+ /*
+ * If we are not inserting keys in secondary location,
+ * when bucket is full, do not try to insert the key
+ */
+ if (with_pushes == 0)
+ if (buckets[bucket_idx] == BUCKET_SIZE)
+ continue;
+
/* If key can be added, leave in successful key arrays "keys" */
ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
signatures[i]);
@@ -388,9 +393,9 @@ reset_table(unsigned table_index)
}
static int
-run_all_tbl_perf_tests(void)
+run_all_tbl_perf_tests(unsigned with_pushes)
{
- unsigned i, j;
+ unsigned i, j, with_hash;
printf("Measuring performance, please wait");
fflush(stdout);
@@ -398,46 +403,32 @@ run_all_tbl_perf_tests(void)
if (create_table(i) < 0)
return -1;
- if (get_input_keys(i) < 0)
- return -1;
-
- if (timed_adds(0, i) < 0)
- return -1;
-
- for (j = 0; j < NUM_SHUFFLES; j++)
- shuffle_input_keys(i);
-
- if (timed_lookups(0, i) < 0)
- return -1;
-
- if (timed_lookups_multi(i) < 0)
- return -1;
-
- if (timed_deletes(0, i) < 0)
+ if (get_input_keys(with_pushes, i) < 0)
return -1;
+ for (with_hash = 0; with_hash <= 1; with_hash++) {
+ if (timed_adds(with_hash, i) < 0)
+ return -1;
- /* Print a dot to show progress on operations */
- printf(".");
- fflush(stdout);
+ for (j = 0; j < NUM_SHUFFLES; j++)
+ shuffle_input_keys(i);
- if (reset_table(i) < 0)
- return -1;
+ if (timed_lookups(with_hash, i) < 0)
+ return -1;
- if (timed_adds(1, i) < 0)
- return -1;
+ if (timed_lookups_multi(i) < 0)
+ return -1;
- for (j = 0; j < NUM_SHUFFLES; j++)
- shuffle_input_keys(i);
+ if (timed_deletes(with_hash, i) < 0)
+ return -1;
- if (timed_lookups(1, i) < 0)
- return -1;
+ if (reset_table(i) < 0)
+ return -1;
- if (timed_deletes(1, i) < 0)
- return -1;
+ /* Print a dot to show progress on operations */
+ printf(".");
+ fflush(stdout);
- /* Print a dot to show progress on operations */
- printf(".");
- fflush(stdout);
+ }
free_table(i);
}
@@ -551,8 +542,16 @@ fbk_hash_perf_test(void)
static int
test_hash_perf(void)
{
- if (run_all_tbl_perf_tests() < 0)
- return -1;
+ unsigned with_pushes;
+
+ for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
+ if (with_pushes == 0)
+ printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
+ else
+ printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
+ if (run_all_tbl_perf_tests(with_pushes) < 0)
+ return -1;
+ }
if (fbk_hash_perf_test() < 0)
return -1;
diff --git a/lib/librte_hash/Makefile b/lib/librte_hash/Makefile
index 981230b..039da46 100644
--- a/lib/librte_hash/Makefile
+++ b/lib/librte_hash/Makefile
@@ -1,6 +1,6 @@
# BSD LICENSE
#
-# Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+# Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
@@ -42,7 +42,7 @@ EXPORT_MAP := rte_hash_version.map
LIBABIVER := 1
# all source are stored in SRCS-y
-SRCS-$(CONFIG_RTE_LIBRTE_HASH) := rte_hash.c
+SRCS-$(CONFIG_RTE_LIBRTE_HASH) := rte_cuckoo_hash.c
SRCS-$(CONFIG_RTE_LIBRTE_HASH) += rte_fbk_hash.c
# install this header file
@@ -52,7 +52,7 @@ SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_jhash.h
SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_thash.h
SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_fbk_hash.h
-# this lib needs eal
-DEPDIRS-$(CONFIG_RTE_LIBRTE_HASH) += lib/librte_eal lib/librte_malloc
+# this lib needs eal and ring
+DEPDIRS-$(CONFIG_RTE_LIBRTE_HASH) += lib/librte_eal lib/librte_malloc lib/librte_ring
include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
new file mode 100644
index 0000000..50e3acd
--- /dev/null
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -0,0 +1,1027 @@
+/*-
+ * BSD LICENSE
+ *
+ * Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ * * Neither the name of Intel Corporation nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <string.h>
+#include <stdint.h>
+#include <errno.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include <sys/queue.h>
+
+#include <rte_common.h>
+#include <rte_memory.h> /* for definition of RTE_CACHE_LINE_SIZE */
+#include <rte_log.h>
+#include <rte_memcpy.h>
+#include <rte_prefetch.h>
+#include <rte_branch_prediction.h>
+#include <rte_memzone.h>
+#include <rte_malloc.h>
+#include <rte_eal.h>
+#include <rte_eal_memconfig.h>
+#include <rte_per_lcore.h>
+#include <rte_errno.h>
+#include <rte_string_fns.h>
+#include <rte_cpuflags.h>
+#include <rte_log.h>
+#include <rte_rwlock.h>
+#include <rte_spinlock.h>
+#include <rte_ring.h>
+
+#include "rte_hash.h"
+
+TAILQ_HEAD(rte_hash_list, rte_tailq_entry);
+
+static struct rte_tailq_elem rte_hash_tailq = {
+ .name = "RTE_HASH",
+};
+EAL_REGISTER_TAILQ(rte_hash_tailq)
+
+/* Macro to enable/disable run-time checking of function parameters */
+#if defined(RTE_LIBRTE_HASH_DEBUG)
+#define RETURN_IF_TRUE(cond, retval) do { \
+ if (cond) \
+ return retval; \
+} while (0)
+#else
+#define RETURN_IF_TRUE(cond, retval)
+#endif
+
+/* Hash function used if none is specified */
+#ifdef RTE_MACHINE_CPUFLAG_SSE4_2
+#include <rte_hash_crc.h>
+#define DEFAULT_HASH_FUNC rte_hash_crc
+#else
+#include <rte_jhash.h>
+#define DEFAULT_HASH_FUNC rte_jhash
+#endif
+
+/** Number of items per bucket. */
+#define RTE_HASH_BUCKET_ENTRIES 4
+
+#define NULL_SIGNATURE 0
+
+typedef int (*rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t key_len);
+static int rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t key_len);
+static int rte_hash_k32_cmp_eq(const void *key1, const void *key2, size_t key_len);
+static int rte_hash_k48_cmp_eq(const void *key1, const void *key2, size_t key_len);
+static int rte_hash_k64_cmp_eq(const void *key1, const void *key2, size_t key_len);
+static int rte_hash_k80_cmp_eq(const void *key1, const void *key2, size_t key_len);
+static int rte_hash_k96_cmp_eq(const void *key1, const void *key2, size_t key_len);
+static int rte_hash_k112_cmp_eq(const void *key1, const void *key2, size_t key_len);
+static int rte_hash_k128_cmp_eq(const void *key1, const void *key2, size_t key_len);
+
+/** A hash table structure. */
+struct rte_hash {
+ char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */
+ uint32_t entries; /**< Total table entries. */
+ uint32_t num_buckets; /**< Number of buckets in table. */
+ uint32_t key_len; /**< Length of hash key. */
+ rte_hash_function hash_func; /**< Function used to calculate hash. */
+ rte_hash_cmp_eq_t rte_hash_cmp_eq; /**< Function used to compare keys. */
+ uint32_t hash_func_init_val; /**< Init value used by hash_func. */
+ uint32_t bucket_bitmask; /**< Bitmask for getting bucket index
+ from hash signature. */
+ uint32_t key_entry_size; /**< Size of each key entry. */
+
+ struct rte_ring *free_slots; /**< Ring that stores all indexes
+ of the free slots in the key table */
+ void *key_store; /**< Table storing all keys and data */
+ struct rte_hash_bucket *buckets; /**< Table with buckets storing all the
+ hash values and key indexes
+ to the key table*/
+} __rte_cache_aligned;
+
+/* Structure storing both primary and secondary hashes */
+struct rte_hash_signatures {
+ union {
+ struct {
+ hash_sig_t current;
+ hash_sig_t alt;
+ };
+ uint64_t sig;
+ };
+};
+
+/** Bucket structure */
+struct rte_hash_bucket {
+ struct rte_hash_signatures signatures[RTE_HASH_BUCKET_ENTRIES];
+ /* Includes dummy key index that always contains index 0 */
+ uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES + 1];
+ uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
+} __rte_cache_aligned;
+
+struct rte_hash *
+rte_hash_find_existing(const char *name)
+{
+ struct rte_hash *h = NULL;
+ struct rte_tailq_entry *te;
+ struct rte_hash_list *hash_list;
+
+ hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
+
+ rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
+ TAILQ_FOREACH(te, hash_list, next) {
+ h = (struct rte_hash *) te->data;
+ if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0)
+ break;
+ }
+ rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+ if (te == NULL) {
+ rte_errno = ENOENT;
+ return NULL;
+ }
+ return h;
+}
+
+struct rte_hash *
+rte_hash_create(const struct rte_hash_parameters *params)
+{
+ struct rte_hash *h = NULL;
+ struct rte_tailq_entry *te = NULL;
+ struct rte_hash_list *hash_list;
+ struct rte_ring *r = NULL;
+ char hash_name[RTE_HASH_NAMESIZE];
+ void *ptr, *k = NULL;
+ void *buckets = NULL;
+ char ring_name[RTE_RING_NAMESIZE];
+ unsigned i;
+
+ hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
+
+ if (params == NULL) {
+ RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n");
+ return NULL;
+ }
+
+ /* Check for valid parameters */
+ if ((params->entries > RTE_HASH_ENTRIES_MAX) ||
+ (params->entries < RTE_HASH_BUCKET_ENTRIES) ||
+ !rte_is_power_of_2(RTE_HASH_BUCKET_ENTRIES) ||
+ (params->key_len == 0)) {
+ rte_errno = EINVAL;
+ RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
+ return NULL;
+ }
+
+ snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
+
+ /* Guarantee there's no existing */
+ h = rte_hash_find_existing(params->name);
+ if (h != NULL)
+ return h;
+
+ te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
+ if (te == NULL) {
+ RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
+ goto err;
+ }
+
+ h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash),
+ RTE_CACHE_LINE_SIZE, params->socket_id);
+
+ if (h == NULL) {
+ RTE_LOG(ERR, HASH, "memory allocation failed\n");
+ goto err;
+ }
+
+ const uint32_t num_buckets = rte_align32pow2(params->entries)
+ / RTE_HASH_BUCKET_ENTRIES;
+
+ buckets = rte_zmalloc_socket(NULL,
+ num_buckets * sizeof(struct rte_hash_bucket),
+ RTE_CACHE_LINE_SIZE, params->socket_id);
+
+ if (buckets == NULL) {
+ RTE_LOG(ERR, HASH, "memory allocation failed\n");
+ goto err;
+ }
+
+ const uint32_t key_entry_size = params->key_len;
+ /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */
+ const uint64_t key_tbl_size = key_entry_size * (params->entries + 1);
+
+ k = rte_zmalloc_socket(NULL, key_tbl_size,
+ RTE_CACHE_LINE_SIZE, params->socket_id);
+
+ if (k == NULL) {
+ RTE_LOG(ERR, HASH, "memory allocation failed\n");
+ goto err;
+ }
+
+ /* Select function to compare keys */
+ switch (params->key_len) {
+ case 16:
+ h->rte_hash_cmp_eq = rte_hash_k16_cmp_eq;
+ break;
+ case 32:
+ h->rte_hash_cmp_eq = rte_hash_k32_cmp_eq;
+ break;
+ case 48:
+ h->rte_hash_cmp_eq = rte_hash_k48_cmp_eq;
+ break;
+ case 64:
+ h->rte_hash_cmp_eq = rte_hash_k64_cmp_eq;
+ break;
+ case 80:
+ h->rte_hash_cmp_eq = rte_hash_k80_cmp_eq;
+ break;
+ case 96:
+ h->rte_hash_cmp_eq = rte_hash_k96_cmp_eq;
+ break;
+ case 112:
+ h->rte_hash_cmp_eq = rte_hash_k112_cmp_eq;
+ break;
+ case 128:
+ h->rte_hash_cmp_eq = rte_hash_k128_cmp_eq;
+ break;
+ default:
+ /* If key is not multiple of 16, use generic memcmp */
+ h->rte_hash_cmp_eq = memcmp;
+ }
+
+ snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
+ r = rte_ring_lookup(ring_name);
+ if (r != NULL) {
+ /* clear the free ring */
+ while (rte_ring_dequeue(r, &ptr) == 0)
+ rte_pause();
+ } else
+ r = rte_ring_create(ring_name, rte_align32pow2(params->entries + 1),
+ params->socket_id, 0);
+ if (r == NULL) {
+ RTE_LOG(ERR, HASH, "memory allocation failed\n");
+ goto err;
+ }
+
+ /* Setup hash context */
+ snprintf(h->name, sizeof(h->name), "%s", params->name);
+ h->entries = params->entries;
+ h->key_len = params->key_len;
+ h->key_entry_size = key_entry_size;
+ h->hash_func_init_val = params->hash_func_init_val;
+
+ h->num_buckets = num_buckets;
+ h->bucket_bitmask = h->num_buckets - 1;
+ h->buckets = buckets;
+ h->hash_func = (params->hash_func == NULL) ?
+ DEFAULT_HASH_FUNC : params->hash_func;
+
+ h->key_store = k;
+ h->free_slots = r;
+
+ /* populate the free slots ring. Entry zero is reserved for key misses */
+ for (i = 1; i < params->entries + 1; i++)
+ rte_ring_sp_enqueue(r, (void *)((uintptr_t) i));
+
+ rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+ te->data = (void *) h;
+ TAILQ_INSERT_TAIL(hash_list, te, next);
+ rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+ return h;
+err:
+ rte_free(te);
+ rte_free(h);
+ rte_free(buckets);
+ rte_free(k);
+ return NULL;
+}
+
+void
+rte_hash_free(struct rte_hash *h)
+{
+ struct rte_tailq_entry *te;
+ struct rte_hash_list *hash_list;
+
+ if (h == NULL)
+ return;
+
+ hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
+
+ rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+
+ /* find out tailq entry */
+ TAILQ_FOREACH(te, hash_list, next) {
+ if (te->data == (void *) h)
+ break;
+ }
+
+ if (te == NULL) {
+ rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+ return;
+ }
+
+ TAILQ_REMOVE(hash_list, te, next);
+
+ rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+ rte_free(h->key_store);
+ rte_free(h->buckets);
+ rte_free(h);
+ rte_free(te);
+}
+
+hash_sig_t
+rte_hash_hash(const struct rte_hash *h, const void *key)
+{
+ /* calc hash result by key */
+ return h->hash_func(key, h->key_len, h->hash_func_init_val);
+}
+
+/* Calc the secondary hash value from the primary hash value of a given key */
+static inline hash_sig_t
+rte_hash_secondary_hash(const hash_sig_t primary_hash)
+{
+ static const unsigned all_bits_shift = 12;
+ static const unsigned alt_bits_xor = 0x5bd1e995;
+
+ uint32_t tag = primary_hash >> all_bits_shift;
+
+ return (primary_hash ^ ((tag + 1) * alt_bits_xor));
+}
+
+/* Search for an entry that can be pushed to its alternative location */
+static inline int
+make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
+{
+ unsigned i, j;
+ int ret;
+ uint32_t next_bucket_idx;
+ struct rte_hash_bucket *next_bkt[RTE_HASH_BUCKET_ENTRIES];
+
+ /*
+ * Push existing item (search for bucket with space in
+ * alternative locations) to its alternative location
+ */
+ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
+ /* Search for space in alternative locations */
+ next_bucket_idx = bkt->signatures[i].alt & h->bucket_bitmask;
+ next_bkt[i] = &h->buckets[next_bucket_idx];
+ for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) {
+ if (next_bkt[i]->signatures[j].sig == NULL_SIGNATURE)
+ break;
+ }
+
+ if (j != RTE_HASH_BUCKET_ENTRIES)
+ break;
+ }
+
+ /* Alternative location has spare room (end of recursive function) */
+ if (i != RTE_HASH_BUCKET_ENTRIES) {
+ next_bkt[i]->signatures[j].alt = bkt->signatures[i].current;
+ next_bkt[i]->signatures[j].current = bkt->signatures[i].alt;
+ next_bkt[i]->key_idx[j] = bkt->key_idx[i];
+ return i;
+ }
+
+ /* Pick entry that has not been pushed yet */
+ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++)
+ if (bkt->flag[i] == 0)
+ break;
+
+ /* All entries have been pushed, so entry cannot be added */
+ if (i == RTE_HASH_BUCKET_ENTRIES) {
+ /* Reset flag */
+ bkt->flag[i] = 0;
+ return -ENOSPC;
+ }
+
+ /* Set flag to indicate that this entry is going to be pushed */
+ bkt->flag[i] = 1;
+ /* Need room in alternative bucket to insert the pushed entry */
+ ret = make_space_bucket(h, next_bkt[i]);
+ /*
+ * After recursive function.
+ * Clear flags and insert the pushed entry
+ * in its alternative location if successful,
+ * or return error
+ */
+ bkt->flag[i] = 0;
+ if (ret >= 0) {
+ next_bkt[i]->signatures[ret].alt = bkt->signatures[i].current;
+ next_bkt[i]->signatures[ret].current = bkt->signatures[i].alt;
+ next_bkt[i]->key_idx[ret] = bkt->key_idx[i];
+ return i;
+ } else
+ return ret;
+
+}
+
+static inline int32_t
+__rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
+ hash_sig_t sig)
+{
+ hash_sig_t alt_hash;
+ uint32_t prim_bucket_idx, sec_bucket_idx;
+ unsigned i;
+ struct rte_hash_bucket *prim_bkt, *sec_bkt;
+ void *new_k, *k, *keys = h->key_store;
+ void *slot_id;
+ uint32_t new_idx;
+ int ret;
+
+ prim_bucket_idx = sig & h->bucket_bitmask;
+ prim_bkt = &h->buckets[prim_bucket_idx];
+ rte_prefetch0(prim_bkt);
+
+ alt_hash = rte_hash_secondary_hash(sig);
+ sec_bucket_idx = alt_hash & h->bucket_bitmask;
+ sec_bkt = &h->buckets[sec_bucket_idx];
+ rte_prefetch0(sec_bkt);
+
+ /* Get a new slot for storing the new key */
+ if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0)
+ return -ENOSPC;
+ new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);
+ rte_prefetch0(new_k);
+ new_idx = (uint32_t)((uintptr_t) slot_id);
+
+ /* Check if key is already inserted in primary location */
+ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
+ if (prim_bkt->signatures[i].current == sig &&
+ prim_bkt->signatures[i].alt == alt_hash) {
+ k = (char *)keys + prim_bkt->key_idx[i] * h->key_entry_size;
+ if (h->rte_hash_cmp_eq(key, k, h->key_len) == 0) {
+ rte_ring_sp_enqueue(h->free_slots, &slot_id);
+ /*
+ * Return index where key is stored,
+ * substracting the first dummy index
+ */
+ return (prim_bkt->key_idx[i] - 1);
+ }
+ }
+ }
+
+ /* Check if key is already inserted in secondary location */
+ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
+ if (sec_bkt->signatures[i].alt == sig &&
+ sec_bkt->signatures[i].current == alt_hash) {
+ k = (char *)keys + sec_bkt->key_idx[i] * h->key_entry_size;
+ if (h->rte_hash_cmp_eq(key, k, h->key_len) == 0) {
+ rte_ring_sp_enqueue(h->free_slots, &slot_id);
+ /*
+ * Return index where key is stored,
+ * substracting the first dummy index
+ */
+ return (sec_bkt->key_idx[i] - 1);
+ }
+ }
+ }
+
+ /* Copy key */
+ rte_memcpy(new_k, key, h->key_len);
+
+ /* Insert new entry is there is room in the primary bucket */
+ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
+ /* Check if slot is available */
+ if (likely(prim_bkt->signatures[i].sig == NULL_SIGNATURE)) {
+ prim_bkt->signatures[i].current = sig;
+ prim_bkt->signatures[i].alt = alt_hash;
+ prim_bkt->key_idx[i] = new_idx;
+ return new_idx - 1;
+ }
+ }
+
+ /* Primary bucket is full, so we need to make space for new entry */
+ ret = make_space_bucket(h, prim_bkt);
+ /*
+ * After recursive function.
+ * Insert the new entry in the position of the pushed entry
+ * if successful or return error and
+ * store the new slot back in the ring
+ */
+ if (ret >= 0) {
+ prim_bkt->signatures[ret].current = sig;
+ prim_bkt->signatures[ret].alt = alt_hash;
+ prim_bkt->key_idx[ret] = new_idx;
+ return (new_idx - 1);
+ }
+
+ /* Error in addition, store new slot back in the ring and return error */
+ rte_ring_sp_enqueue(h->free_slots,
+ (void *)((uintptr_t) new_idx));
+ return ret;
+
+}
+
+int32_t
+rte_hash_add_key_with_hash(const struct rte_hash *h,
+ const void *key, hash_sig_t sig)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_add_key_with_hash(h, key, sig);
+}
+
+int32_t
+rte_hash_add_key(const struct rte_hash *h, const void *key)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key));
+}
+
+static inline int32_t
+__rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
+ hash_sig_t sig)
+{
+ uint32_t bucket_idx;
+ hash_sig_t alt_hash;
+ unsigned i;
+ struct rte_hash_bucket *bkt;
+ void *k, *keys = h->key_store;
+
+ bucket_idx = sig & h->bucket_bitmask;
+ bkt = &h->buckets[bucket_idx];
+
+ /* Check if key is in primary location */
+ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
+ if (bkt->signatures[i].current == sig &&
+ bkt->signatures[i].sig != NULL_SIGNATURE) {
+ k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
+ if (h->rte_hash_cmp_eq(key, k, h->key_len) == 0)
+ /*
+ * Return index where key is stored,
+ * substracting the first dummy index
+ */
+ return (bkt->key_idx[i] - 1);
+ }
+ }
+
+ /* Calculate secondary hash */
+ alt_hash = rte_hash_secondary_hash(sig);
+ bucket_idx = alt_hash & h->bucket_bitmask;
+ bkt = &h->buckets[bucket_idx];
+
+ /* Check if key is in secondary location */
+ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
+ if (bkt->signatures[i].current == alt_hash &&
+ bkt->signatures[i].alt == sig) {
+ k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
+ if (h->rte_hash_cmp_eq(key, k, h->key_len) == 0)
+ /*
+ * Return index where key is stored,
+ * substracting the first dummy index
+ */
+ return (bkt->key_idx[i] - 1);
+ }
+ }
+
+ return -ENOENT;
+}
+
+int32_t
+rte_hash_lookup_with_hash(const struct rte_hash *h,
+ const void *key, hash_sig_t sig)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_lookup_with_hash(h, key, sig);
+}
+
+int32_t
+rte_hash_lookup(const struct rte_hash *h, const void *key)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key));
+}
+
+static inline int32_t
+__rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
+ hash_sig_t sig)
+{
+ uint32_t bucket_idx;
+ hash_sig_t alt_hash;
+ unsigned i;
+ struct rte_hash_bucket *bkt;
+ void *k, *keys = h->key_store;
+
+ bucket_idx = sig & h->bucket_bitmask;
+ bkt = &h->buckets[bucket_idx];
+
+ /* Check if key is in primary location */
+ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
+ if (bkt->signatures[i].current == sig &&
+ bkt->signatures[i].sig != NULL_SIGNATURE) {
+ k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
+ if (h->rte_hash_cmp_eq(key, k, h->key_len) == 0) {
+ bkt->signatures[i].sig = NULL_SIGNATURE;
+ rte_ring_sp_enqueue(h->free_slots,
+ (void *)((uintptr_t)bkt->key_idx[i]));
+ /*
+ * Return index where key is stored,
+ * substracting the first dummy index
+ */
+ return (bkt->key_idx[i] - 1);
+ }
+ }
+ }
+
+ /* Calculate secondary hash */
+ alt_hash = rte_hash_secondary_hash(sig);
+ bucket_idx = alt_hash & h->bucket_bitmask;
+ bkt = &h->buckets[bucket_idx];
+
+ /* Check if key is in secondary location */
+ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
+ if (bkt->signatures[i].current == alt_hash &&
+ bkt->signatures[i].sig != NULL_SIGNATURE) {
+ k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
+ if (h->rte_hash_cmp_eq(key, k, h->key_len) == 0) {
+ bkt->signatures[i].sig = NULL_SIGNATURE;
+ rte_ring_sp_enqueue(h->free_slots,
+ (void *)((uintptr_t)bkt->key_idx[i]));
+ /*
+ * Return index where key is stored,
+ * substracting the first dummy index
+ */
+ return (bkt->key_idx[i] - 1);
+ }
+ }
+ }
+
+ return -ENOENT;
+}
+
+int32_t
+rte_hash_del_key_with_hash(const struct rte_hash *h,
+ const void *key, hash_sig_t sig)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_del_key_with_hash(h, key, sig);
+}
+
+int32_t
+rte_hash_del_key(const struct rte_hash *h, const void *key)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
+}
+
+/* Lookup bulk stage 0: Prefetch input key */
+static inline void
+lookup_stage0(unsigned *idx, uint64_t *lookup_mask,
+ const void * const *keys)
+{
+ *idx = __builtin_ctzl(*lookup_mask);
+ if (*lookup_mask == 0)
+ *idx = 0;
+
+ rte_prefetch0(keys[*idx]);
+ *lookup_mask &= ~(1llu << *idx);
+}
+
+/*
+ * Lookup bulk stage 1: Calculate primary/secondary hashes
+ * and prefetch primary/secondary buckets
+ */
+static inline void
+lookup_stage1(unsigned idx, hash_sig_t *prim_hash, hash_sig_t *sec_hash,
+ const struct rte_hash_bucket **primary_bkt,
+ const struct rte_hash_bucket **secondary_bkt,
+ hash_sig_t *hash_vals, const void * const *keys,
+ const struct rte_hash *h)
+{
+ *prim_hash = rte_hash_hash(h, keys[idx]);
+ hash_vals[idx] = *prim_hash;
+ *sec_hash = rte_hash_secondary_hash(*prim_hash);
+
+ *primary_bkt = &h->buckets[*prim_hash & h->bucket_bitmask];
+ *secondary_bkt = &h->buckets[*sec_hash & h->bucket_bitmask];
+
+ rte_prefetch0(*primary_bkt);
+ rte_prefetch0(*secondary_bkt);
+}
+
+/*
+ * Lookup bulk stage 2: Search for match hashes in primary/secondary locations
+ * and prefetch first key slot
+ */
+static inline void
+lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash,
+ const struct rte_hash_bucket *prim_bkt,
+ const struct rte_hash_bucket *sec_bkt,
+ const void **key_slot, int32_t *positions,
+ uint64_t *extra_hits_mask, const void *keys,
+ const struct rte_hash *h)
+{
+ unsigned prim_hash_matches, sec_hash_matches, key_idx, i;
+ unsigned total_hash_matches;
+
+ prim_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;
+ sec_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;
+ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
+ prim_hash_matches |= ((prim_hash == prim_bkt->signatures[i].current) << i);
+ sec_hash_matches |= ((sec_hash == sec_bkt->signatures[i].current) << i);
+ }
+
+ key_idx = prim_bkt->key_idx[__builtin_ctzl(prim_hash_matches)];
+ if (key_idx == 0)
+ key_idx = sec_bkt->key_idx[__builtin_ctzl(sec_hash_matches)];
+
+ total_hash_matches = (prim_hash_matches |
+ (sec_hash_matches << (RTE_HASH_BUCKET_ENTRIES + 1)));
+ *key_slot = (const char *)keys + key_idx * h->key_entry_size;
+
+ rte_prefetch0(*key_slot);
+ /*
+ * Return index where key is stored,
+ * substracting the first dummy index
+ */
+ positions[idx] = (key_idx - 1);
+
+ *extra_hits_mask |= (uint64_t)(__builtin_popcount(total_hash_matches) > 3) << idx;
+
+}
+
+
+/* Lookup bulk stage 3: Check if key matches, update hit mask */
+static inline void
+lookup_stage3(unsigned idx, const void *key_slot, const void * const *keys,
+ uint64_t *hits, const struct rte_hash *h)
+{
+ unsigned hit;
+
+ hit = !h->rte_hash_cmp_eq(key_slot, keys[idx], h->key_len);
+ *hits |= (uint64_t)(hit) << idx;
+}
+
+static inline void
+__rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
+ uint32_t num_keys, int32_t *positions)
+{
+ uint64_t hits = 0;
+ uint64_t extra_hits_mask = 0;
+ uint64_t lookup_mask, miss_mask;
+ unsigned idx;
+ const void *key_store = h->key_store;
+ hash_sig_t hash_vals[RTE_HASH_LOOKUP_BULK_MAX];
+
+ unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31;
+ const struct rte_hash_bucket *primary_bkt10, *primary_bkt11;
+ const struct rte_hash_bucket *secondary_bkt10, *secondary_bkt11;
+ const struct rte_hash_bucket *primary_bkt20, *primary_bkt21;
+ const struct rte_hash_bucket *secondary_bkt20, *secondary_bkt21;
+ const void *k_slot20, *k_slot21, *k_slot30, *k_slot31;
+ hash_sig_t primary_hash10, primary_hash11;
+ hash_sig_t secondary_hash10, secondary_hash11;
+ hash_sig_t primary_hash20, primary_hash21;
+ hash_sig_t secondary_hash20, secondary_hash21;
+
+ lookup_mask = (uint64_t) -1 >> (64 - num_keys);
+ miss_mask = lookup_mask;
+
+ lookup_stage0(&idx00, &lookup_mask, keys);
+ lookup_stage0(&idx01, &lookup_mask, keys);
+
+ idx10 = idx00, idx11 = idx01;
+
+ lookup_stage0(&idx00, &lookup_mask, keys);
+ lookup_stage0(&idx01, &lookup_mask, keys);
+ lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
+ &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
+ lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
+ &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
+
+ primary_bkt20 = primary_bkt10;
+ primary_bkt21 = primary_bkt11;
+ secondary_bkt20 = secondary_bkt10;
+ secondary_bkt21 = secondary_bkt11;
+ primary_hash20 = primary_hash10;
+ primary_hash21 = primary_hash11;
+ secondary_hash20 = secondary_hash10;
+ secondary_hash21 = secondary_hash11;
+ idx20 = idx10, idx21 = idx11;
+ idx10 = idx00, idx11 = idx01;
+
+ lookup_stage0(&idx00, &lookup_mask, keys);
+ lookup_stage0(&idx01, &lookup_mask, keys);
+ lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
+ &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
+ lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
+ &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
+ lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
+ secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
+ key_store, h);
+ lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
+ secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
+ key_store, h);
+
+ while (lookup_mask) {
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ primary_bkt20 = primary_bkt10;
+ primary_bkt21 = primary_bkt11;
+ secondary_bkt20 = secondary_bkt10;
+ secondary_bkt21 = secondary_bkt11;
+ primary_hash20 = primary_hash10;
+ primary_hash21 = primary_hash11;
+ secondary_hash20 = secondary_hash10;
+ secondary_hash21 = secondary_hash11;
+ idx20 = idx10, idx21 = idx11;
+ idx10 = idx00, idx11 = idx01;
+
+ lookup_stage0(&idx00, &lookup_mask, keys);
+ lookup_stage0(&idx01, &lookup_mask, keys);
+ lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
+ &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
+ lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
+ &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
+ lookup_stage2(idx20, primary_hash20, secondary_hash20,
+ primary_bkt20, secondary_bkt20, &k_slot20, positions,
+ &extra_hits_mask, key_store, h);
+ lookup_stage2(idx21, primary_hash21, secondary_hash21,
+ primary_bkt21, secondary_bkt21, &k_slot21, positions,
+ &extra_hits_mask, key_store, h);
+ lookup_stage3(idx30, k_slot30, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, &hits, h);
+ }
+
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ primary_bkt20 = primary_bkt10;
+ primary_bkt21 = primary_bkt11;
+ secondary_bkt20 = secondary_bkt10;
+ secondary_bkt21 = secondary_bkt11;
+ primary_hash20 = primary_hash10;
+ primary_hash21 = primary_hash11;
+ secondary_hash20 = secondary_hash10;
+ secondary_hash21 = secondary_hash11;
+ idx20 = idx10, idx21 = idx11;
+ idx10 = idx00, idx11 = idx01;
+
+ lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
+ &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
+ lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
+ &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
+ lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
+ secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
+ key_store, h);
+ lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
+ secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
+ key_store, h);
+ lookup_stage3(idx30, k_slot30, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, &hits, h);
+
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ primary_bkt20 = primary_bkt10;
+ primary_bkt21 = primary_bkt11;
+ secondary_bkt20 = secondary_bkt10;
+ secondary_bkt21 = secondary_bkt11;
+ primary_hash20 = primary_hash10;
+ primary_hash21 = primary_hash11;
+ secondary_hash20 = secondary_hash10;
+ secondary_hash21 = secondary_hash11;
+ idx20 = idx10, idx21 = idx11;
+
+ lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
+ secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
+ key_store, h);
+ lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
+ secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
+ key_store, h);
+ lookup_stage3(idx30, k_slot30, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, &hits, h);
+
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+
+ lookup_stage3(idx30, k_slot30, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, &hits, h);
+
+ /* ignore any items we have already found */
+ extra_hits_mask &= ~hits;
+
+ if (unlikely(extra_hits_mask)) {
+ /* run a single search for each remaining item */
+ do {
+ idx = __builtin_ctzl(extra_hits_mask);
+ positions[idx] = rte_hash_lookup_with_hash(h, keys[idx],
+ hash_vals[idx]);
+ extra_hits_mask &= ~(1llu << idx);
+ if (positions[idx] >= 0)
+ hits |= 1llu << idx;
+ } while (extra_hits_mask);
+ }
+
+ miss_mask &= ~hits;
+ if (unlikely(miss_mask)) {
+ do {
+ idx = __builtin_ctzl(miss_mask);
+ positions[idx] = -ENOENT;
+ miss_mask &= ~(1llu << idx);
+ } while (miss_mask);
+ }
+}
+
+int
+rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
+ uint32_t num_keys, int32_t *positions)
+{
+ RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
+ (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
+ (positions == NULL)), -EINVAL);
+
+ __rte_hash_lookup_bulk(h, keys, num_keys, positions);
+ return 0;
+}
+
+/* Functions to compare multiple of 16 byte keys (up to 128 bytes) */
+static int
+rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
+{
+ const __m128i k1 = _mm_loadu_si128((const __m128i *) key1);
+ const __m128i k2 = _mm_loadu_si128((const __m128i *) key2);
+ const __m128i x = _mm_xor_si128(k1, k2);
+
+ return !_mm_test_all_zeros(x, x);
+}
+
+static int
+rte_hash_k32_cmp_eq(const void *key1, const void *key2, size_t key_len)
+{
+ return rte_hash_k16_cmp_eq(key1, key2, key_len) ||
+ rte_hash_k16_cmp_eq((const char *) key1 + 16,
+ (const char *) key2 + 16, key_len);
+}
+
+static int
+rte_hash_k48_cmp_eq(const void *key1, const void *key2, size_t key_len)
+{
+ return rte_hash_k16_cmp_eq(key1, key2, key_len) ||
+ rte_hash_k16_cmp_eq((const char *) key1 + 16,
+ (const char *) key2 + 16, key_len) ||
+ rte_hash_k16_cmp_eq((const char *) key1 + 32,
+ (const char *) key2 + 32, key_len);
+}
+
+static int
+rte_hash_k64_cmp_eq(const void *key1, const void *key2, size_t key_len)
+{
+ return rte_hash_k32_cmp_eq(key1, key2, key_len) ||
+ rte_hash_k32_cmp_eq((const char *) key1 + 32,
+ (const char *) key2 + 32, key_len);
+}
+
+static int
+rte_hash_k80_cmp_eq(const void *key1, const void *key2, size_t key_len)
+{
+ return rte_hash_k64_cmp_eq(key1, key2, key_len) ||
+ rte_hash_k16_cmp_eq((const char *) key1 + 64,
+ (const char *) key2 + 64, key_len);
+}
+
+static int
+rte_hash_k96_cmp_eq(const void *key1, const void *key2, size_t key_len)
+{
+ return rte_hash_k64_cmp_eq(key1, key2, key_len) ||
+ rte_hash_k32_cmp_eq((const char *) key1 + 64,
+ (const char *) key2 + 64, key_len);
+}
+
+static int
+rte_hash_k112_cmp_eq(const void *key1, const void *key2, size_t key_len)
+{
+ return rte_hash_k64_cmp_eq(key1, key2, key_len) ||
+ rte_hash_k32_cmp_eq((const char *) key1 + 64,
+ (const char *) key2 + 64, key_len) ||
+ rte_hash_k16_cmp_eq((const char *) key1 + 96,
+ (const char *) key2 + 96, key_len);
+}
+
+static int
+rte_hash_k128_cmp_eq(const void *key1, const void *key2, size_t key_len)
+{
+ return rte_hash_k64_cmp_eq(key1, key2, key_len) ||
+ rte_hash_k64_cmp_eq((const char *) key1 + 64,
+ (const char *) key2 + 64, key_len);
+}
diff --git a/lib/librte_hash/rte_hash.c b/lib/librte_hash/rte_hash.c
deleted file mode 100644
index 5100a75..0000000
--- a/lib/librte_hash/rte_hash.c
+++ /dev/null
@@ -1,499 +0,0 @@
-/*-
- * BSD LICENSE
- *
- * Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- * * Neither the name of Intel Corporation nor the names of its
- * contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#include <string.h>
-#include <stdint.h>
-#include <errno.h>
-#include <stdio.h>
-#include <stdarg.h>
-#include <sys/queue.h>
-
-#include <rte_common.h>
-#include <rte_memory.h> /* for definition of RTE_CACHE_LINE_SIZE */
-#include <rte_log.h>
-#include <rte_memcpy.h>
-#include <rte_prefetch.h>
-#include <rte_branch_prediction.h>
-#include <rte_memzone.h>
-#include <rte_malloc.h>
-#include <rte_eal.h>
-#include <rte_eal_memconfig.h>
-#include <rte_per_lcore.h>
-#include <rte_errno.h>
-#include <rte_string_fns.h>
-#include <rte_cpuflags.h>
-#include <rte_log.h>
-#include <rte_rwlock.h>
-#include <rte_spinlock.h>
-
-#include "rte_hash.h"
-
-TAILQ_HEAD(rte_hash_list, rte_tailq_entry);
-
-static struct rte_tailq_elem rte_hash_tailq = {
- .name = "RTE_HASH",
-};
-EAL_REGISTER_TAILQ(rte_hash_tailq)
-
-/* Macro to enable/disable run-time checking of function parameters */
-#if defined(RTE_LIBRTE_HASH_DEBUG)
-#define RETURN_IF_TRUE(cond, retval) do { \
- if (cond) return (retval); \
-} while (0)
-#else
-#define RETURN_IF_TRUE(cond, retval)
-#endif
-
-/* Hash function used if none is specified */
-#ifdef RTE_MACHINE_CPUFLAG_SSE4_2
-#include <rte_hash_crc.h>
-#define DEFAULT_HASH_FUNC rte_hash_crc
-#else
-#include <rte_jhash.h>
-#define DEFAULT_HASH_FUNC rte_jhash
-#endif
-
-/* Signature bucket size is a multiple of this value */
-#define SIG_BUCKET_ALIGNMENT 16
-
-/* Stoered key size is a multiple of this value */
-#define KEY_ALIGNMENT 16
-
-/* The high bit is always set in real signatures */
-#define NULL_SIGNATURE 0
-
-struct rte_hash {
- char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */
- uint32_t entries; /**< Total table entries. */
- uint32_t bucket_entries; /**< Bucket entries. */
- uint32_t key_len; /**< Length of hash key. */
- rte_hash_function hash_func; /**< Function used to calculate hash. */
- uint32_t hash_func_init_val; /**< Init value used by hash_func. */
- uint32_t num_buckets; /**< Number of buckets in table. */
- uint32_t bucket_bitmask; /**< Bitmask for getting bucket index
- from hash signature. */
- hash_sig_t sig_msb; /**< MSB is always set in valid signatures. */
- uint8_t *sig_tbl; /**< Flat array of hash signature buckets. */
- uint32_t sig_tbl_bucket_size; /**< Signature buckets may be padded for
- alignment reasons, and this is the
- bucket size used by sig_tbl. */
- uint8_t *key_tbl; /**< Flat array of key value buckets. */
- uint32_t key_tbl_key_size; /**< Keys may be padded for alignment
- reasons, and this is the key size
- used by key_tbl. */
-};
-
-/* Returns a pointer to the first signature in specified bucket. */
-static inline hash_sig_t *
-get_sig_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index)
-{
- return RTE_PTR_ADD(h->sig_tbl, (bucket_index *
- h->sig_tbl_bucket_size));
-}
-
-/* Returns a pointer to the first key in specified bucket. */
-static inline uint8_t *
-get_key_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index)
-{
- return RTE_PTR_ADD(h->key_tbl, (bucket_index * h->bucket_entries *
- h->key_tbl_key_size));
-}
-
-/* Returns a pointer to a key at a specific position in a specified bucket. */
-static inline void *
-get_key_from_bucket(const struct rte_hash *h, uint8_t *bkt, uint32_t pos)
-{
- return RTE_PTR_ADD(bkt, pos * h->key_tbl_key_size);
-}
-
-/* Does integer division with rounding-up of result. */
-static inline uint32_t
-div_roundup(uint32_t numerator, uint32_t denominator)
-{
- return (numerator + denominator - 1) / denominator;
-}
-
-/* Increases a size (if needed) to a multiple of alignment. */
-static inline uint32_t
-align_size(uint32_t val, uint32_t alignment)
-{
- return alignment * div_roundup(val, alignment);
-}
-
-/* Returns the index into the bucket of the first occurrence of a signature. */
-static inline int
-find_first(uint32_t sig, const uint32_t *sig_bucket, uint32_t num_sigs)
-{
- uint32_t i;
- for (i = 0; i < num_sigs; i++) {
- if (sig == sig_bucket[i])
- return i;
- }
- return -1;
-}
-
-struct rte_hash *
-rte_hash_find_existing(const char *name)
-{
- struct rte_hash *h = NULL;
- struct rte_tailq_entry *te;
- struct rte_hash_list *hash_list;
-
- hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
-
- rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
- TAILQ_FOREACH(te, hash_list, next) {
- h = (struct rte_hash *) te->data;
- if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0)
- break;
- }
- rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
-
- if (te == NULL) {
- rte_errno = ENOENT;
- return NULL;
- }
- return h;
-}
-
-struct rte_hash *
-rte_hash_create(const struct rte_hash_parameters *params)
-{
- struct rte_hash *h = NULL;
- struct rte_tailq_entry *te;
- uint32_t num_buckets, sig_bucket_size, key_size,
- hash_tbl_size, sig_tbl_size, key_tbl_size, mem_size;
- char hash_name[RTE_HASH_NAMESIZE];
- struct rte_hash_list *hash_list;
-
- hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
-
- /* Check for valid parameters */
- if ((params == NULL) ||
- (params->entries > RTE_HASH_ENTRIES_MAX) ||
- (params->bucket_entries > RTE_HASH_BUCKET_ENTRIES_MAX) ||
- (params->entries < params->bucket_entries) ||
- !rte_is_power_of_2(params->entries) ||
- !rte_is_power_of_2(params->bucket_entries) ||
- (params->key_len == 0) ||
- (params->key_len > RTE_HASH_KEY_LENGTH_MAX)) {
- rte_errno = EINVAL;
- RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
- return NULL;
- }
-
- snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
-
- /* Calculate hash dimensions */
- num_buckets = params->entries / params->bucket_entries;
- sig_bucket_size = align_size(params->bucket_entries *
- sizeof(hash_sig_t), SIG_BUCKET_ALIGNMENT);
- key_size = align_size(params->key_len, KEY_ALIGNMENT);
-
- hash_tbl_size = align_size(sizeof(struct rte_hash), RTE_CACHE_LINE_SIZE);
- sig_tbl_size = align_size(num_buckets * sig_bucket_size,
- RTE_CACHE_LINE_SIZE);
- key_tbl_size = align_size(num_buckets * key_size *
- params->bucket_entries, RTE_CACHE_LINE_SIZE);
-
- /* Total memory required for hash context */
- mem_size = hash_tbl_size + sig_tbl_size + key_tbl_size;
-
- rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
-
- /* guarantee there's no existing */
- TAILQ_FOREACH(te, hash_list, next) {
- h = (struct rte_hash *) te->data;
- if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0)
- break;
- }
- if (te != NULL)
- goto exit;
-
- te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
- if (te == NULL) {
- RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
- goto exit;
- }
-
- h = (struct rte_hash *)rte_zmalloc_socket(hash_name, mem_size,
- RTE_CACHE_LINE_SIZE, params->socket_id);
- if (h == NULL) {
- RTE_LOG(ERR, HASH, "memory allocation failed\n");
- rte_free(te);
- goto exit;
- }
-
- /* Setup hash context */
- snprintf(h->name, sizeof(h->name), "%s", params->name);
- h->entries = params->entries;
- h->bucket_entries = params->bucket_entries;
- h->key_len = params->key_len;
- h->hash_func_init_val = params->hash_func_init_val;
- h->num_buckets = num_buckets;
- h->bucket_bitmask = h->num_buckets - 1;
- h->sig_msb = 1 << (sizeof(hash_sig_t) * 8 - 1);
- h->sig_tbl = (uint8_t *)h + hash_tbl_size;
- h->sig_tbl_bucket_size = sig_bucket_size;
- h->key_tbl = h->sig_tbl + sig_tbl_size;
- h->key_tbl_key_size = key_size;
- h->hash_func = (params->hash_func == NULL) ?
- DEFAULT_HASH_FUNC : params->hash_func;
-
- te->data = (void *) h;
-
- TAILQ_INSERT_TAIL(hash_list, te, next);
-
-exit:
- rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
-
- return h;
-}
-
-void
-rte_hash_free(struct rte_hash *h)
-{
- struct rte_tailq_entry *te;
- struct rte_hash_list *hash_list;
-
- if (h == NULL)
- return;
-
- hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
-
- rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
-
- /* find out tailq entry */
- TAILQ_FOREACH(te, hash_list, next) {
- if (te->data == (void *) h)
- break;
- }
-
- if (te == NULL) {
- rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
- return;
- }
-
- TAILQ_REMOVE(hash_list, te, next);
-
- rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
-
- rte_free(h);
- rte_free(te);
-}
-
-hash_sig_t
-rte_hash_hash(const struct rte_hash *h, const void *key)
-{
- /* calc hash result by key */
- return h->hash_func(key, h->key_len, h->hash_func_init_val);
-}
-
-static inline int32_t
-__rte_hash_add_key_with_hash(const struct rte_hash *h,
- const void *key, hash_sig_t sig)
-{
- hash_sig_t *sig_bucket;
- uint8_t *key_bucket;
- uint32_t bucket_index, i;
- int32_t pos;
-
- /* Get the hash signature and bucket index */
- sig |= h->sig_msb;
- bucket_index = sig & h->bucket_bitmask;
- sig_bucket = get_sig_tbl_bucket(h, bucket_index);
- key_bucket = get_key_tbl_bucket(h, bucket_index);
-
- /* Check if key is already present in the hash */
- for (i = 0; i < h->bucket_entries; i++) {
- if ((sig == sig_bucket[i]) &&
- likely(memcmp(key, get_key_from_bucket(h, key_bucket, i),
- h->key_len) == 0)) {
- return bucket_index * h->bucket_entries + i;
- }
- }
-
- /* Check if any free slot within the bucket to add the new key */
- pos = find_first(NULL_SIGNATURE, sig_bucket, h->bucket_entries);
-
- if (unlikely(pos < 0))
- return -ENOSPC;
-
- /* Add the new key to the bucket */
- sig_bucket[pos] = sig;
- rte_memcpy(get_key_from_bucket(h, key_bucket, pos), key, h->key_len);
- return bucket_index * h->bucket_entries + pos;
-}
-
-int32_t
-rte_hash_add_key_with_hash(const struct rte_hash *h,
- const void *key, hash_sig_t sig)
-{
- RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_add_key_with_hash(h, key, sig);
-}
-
-int32_t
-rte_hash_add_key(const struct rte_hash *h, const void *key)
-{
- RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key));
-}
-
-static inline int32_t
-__rte_hash_del_key_with_hash(const struct rte_hash *h,
- const void *key, hash_sig_t sig)
-{
- hash_sig_t *sig_bucket;
- uint8_t *key_bucket;
- uint32_t bucket_index, i;
-
- /* Get the hash signature and bucket index */
- sig = sig | h->sig_msb;
- bucket_index = sig & h->bucket_bitmask;
- sig_bucket = get_sig_tbl_bucket(h, bucket_index);
- key_bucket = get_key_tbl_bucket(h, bucket_index);
-
- /* Check if key is already present in the hash */
- for (i = 0; i < h->bucket_entries; i++) {
- if ((sig == sig_bucket[i]) &&
- likely(memcmp(key, get_key_from_bucket(h, key_bucket, i),
- h->key_len) == 0)) {
- sig_bucket[i] = NULL_SIGNATURE;
- return bucket_index * h->bucket_entries + i;
- }
- }
-
- return -ENOENT;
-}
-
-int32_t
-rte_hash_del_key_with_hash(const struct rte_hash *h,
- const void *key, hash_sig_t sig)
-{
- RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_del_key_with_hash(h, key, sig);
-}
-
-int32_t
-rte_hash_del_key(const struct rte_hash *h, const void *key)
-{
- RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
-}
-
-static inline int32_t
-__rte_hash_lookup_with_hash(const struct rte_hash *h,
- const void *key, hash_sig_t sig)
-{
- hash_sig_t *sig_bucket;
- uint8_t *key_bucket;
- uint32_t bucket_index, i;
-
- /* Get the hash signature and bucket index */
- sig |= h->sig_msb;
- bucket_index = sig & h->bucket_bitmask;
- sig_bucket = get_sig_tbl_bucket(h, bucket_index);
- key_bucket = get_key_tbl_bucket(h, bucket_index);
-
- /* Check if key is already present in the hash */
- for (i = 0; i < h->bucket_entries; i++) {
- if ((sig == sig_bucket[i]) &&
- likely(memcmp(key, get_key_from_bucket(h, key_bucket, i),
- h->key_len) == 0)) {
- return bucket_index * h->bucket_entries + i;
- }
- }
-
- return -ENOENT;
-}
-
-int32_t
-rte_hash_lookup_with_hash(const struct rte_hash *h,
- const void *key, hash_sig_t sig)
-{
- RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_lookup_with_hash(h, key, sig);
-}
-
-int32_t
-rte_hash_lookup(const struct rte_hash *h, const void *key)
-{
- RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key));
-}
-
-int
-rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
- uint32_t num_keys, int32_t *positions)
-{
- uint32_t i, j, bucket_index;
- hash_sig_t sigs[RTE_HASH_LOOKUP_BULK_MAX];
-
- RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
- (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
- (positions == NULL)), -EINVAL);
-
- /* Get the hash signature and bucket index */
- for (i = 0; i < num_keys; i++) {
- sigs[i] = h->hash_func(keys[i], h->key_len,
- h->hash_func_init_val) | h->sig_msb;
- bucket_index = sigs[i] & h->bucket_bitmask;
-
- /* Pre-fetch relevant buckets */
- rte_prefetch1((void *) get_sig_tbl_bucket(h, bucket_index));
- rte_prefetch1((void *) get_key_tbl_bucket(h, bucket_index));
- }
-
- /* Check if key is already present in the hash */
- for (i = 0; i < num_keys; i++) {
- bucket_index = sigs[i] & h->bucket_bitmask;
- hash_sig_t *sig_bucket = get_sig_tbl_bucket(h, bucket_index);
- uint8_t *key_bucket = get_key_tbl_bucket(h, bucket_index);
-
- positions[i] = -ENOENT;
-
- for (j = 0; j < h->bucket_entries; j++) {
- if ((sigs[i] == sig_bucket[j]) &&
- likely(memcmp(keys[i],
- get_key_from_bucket(h, key_bucket, j),
- h->key_len) == 0)) {
- positions[i] = bucket_index *
- h->bucket_entries + j;
- break;
- }
- }
- }
-
- return 0;
-}
diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
index da0a00a..936d170 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -47,21 +47,21 @@ extern "C" {
#endif
/** Maximum size of hash table that can be created. */
-#define RTE_HASH_ENTRIES_MAX (1 << 26)
+#define RTE_HASH_ENTRIES_MAX (1 << 30)
-/** Maximum bucket size that can be created. */
-#define RTE_HASH_BUCKET_ENTRIES_MAX 16
+/** @deprecated Maximum bucket size that can be created. */
+#define RTE_HASH_BUCKET_ENTRIES_MAX 4
-/** Maximum length of key that can be used. */
+/** @deprecated Maximum length of key that can be used. */
#define RTE_HASH_KEY_LENGTH_MAX 64
-/** Max number of keys that can be searched for using rte_hash_lookup_multi. */
-#define RTE_HASH_LOOKUP_BULK_MAX 16
-#define RTE_HASH_LOOKUP_MULTI_MAX RTE_HASH_LOOKUP_BULK_MAX
-
-/** Max number of characters in hash name.*/
+/** Maximum number of characters in hash name.*/
#define RTE_HASH_NAMESIZE 32
+/** Maximum number of keys that can be searched for using rte_hash_lookup_bulk. */
+#define RTE_HASH_LOOKUP_BULK_MAX 64
+#define RTE_HASH_LOOKUP_MULTI_MAX RTE_HASH_LOOKUP_BULK_MAX
+
/** Signature of key that is stored internally. */
typedef uint32_t hash_sig_t;
@@ -70,15 +70,14 @@ typedef uint32_t (*rte_hash_function)(const void *key, uint32_t key_len,
uint32_t init_val);
/**
- * Parameters used when creating the hash table. The total table entries and
- * bucket entries must be a power of 2.
+ * Parameters used when creating the hash table.
*/
struct rte_hash_parameters {
const char *name; /**< Name of the hash. */
uint32_t entries; /**< Total hash table entries. */
- uint32_t bucket_entries; /**< Bucket entries. */
+ uint32_t bucket_entries; /**< Bucket entries. */
uint32_t key_len; /**< Length of hash key. */
- rte_hash_function hash_func; /**< Function used to calculate hash. */
+ rte_hash_function hash_func; /**< Primary Hash function used to calculate hash. */
uint32_t hash_func_init_val; /**< Init value used by hash_func. */
int socket_id; /**< NUMA Socket ID for memory. */
};
@@ -86,6 +85,7 @@ struct rte_hash_parameters {
/** @internal A hash table structure. */
struct rte_hash;
+
/**
* Create a new hash table.
*
@@ -106,7 +106,6 @@ struct rte_hash;
struct rte_hash *
rte_hash_create(const struct rte_hash_parameters *params);
-
/**
* Find an existing hash table object and return a pointer to it.
*
@@ -129,7 +128,8 @@ void
rte_hash_free(struct rte_hash *h);
/**
- * Add a key to an existing hash table. This operation is not multi-thread safe
+ * Add a key to an existing hash table.
+ * This operation is not multi-thread safe
* and should only be called from one thread.
*
* @param h
@@ -146,7 +146,8 @@ int32_t
rte_hash_add_key(const struct rte_hash *h, const void *key);
/**
- * Add a key to an existing hash table. This operation is not multi-thread safe
+ * Add a key to an existing hash table.
+ * This operation is not multi-thread safe
* and should only be called from one thread.
*
* @param h
@@ -154,7 +155,7 @@ rte_hash_add_key(const struct rte_hash *h, const void *key);
* @param key
* Key to add to the hash table.
* @param sig
- * Hash value to add to the hash table.
+ * Precomputed hash value for 'key'.
* @return
* - -EINVAL if the parameters are invalid.
* - -ENOSPC if there is no space in the hash for this key.
@@ -162,12 +163,12 @@ rte_hash_add_key(const struct rte_hash *h, const void *key);
* array of user data. This value is unique for this key.
*/
int32_t
-rte_hash_add_key_with_hash(const struct rte_hash *h,
- const void *key, hash_sig_t sig);
+rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
/**
- * Remove a key from an existing hash table. This operation is not multi-thread
- * safe and should only be called from one thread.
+ * Remove a key from an existing hash table.
+ * This operation is not multi-thread safe
+ * and should only be called from one thread.
*
* @param h
* Hash table to remove the key from.
@@ -184,15 +185,16 @@ int32_t
rte_hash_del_key(const struct rte_hash *h, const void *key);
/**
- * Remove a key from an existing hash table. This operation is not multi-thread
- * safe and should only be called from one thread.
+ * Remove a key from an existing hash table.
+ * This operation is not multi-thread safe
+ * and should only be called from one thread.
*
* @param h
* Hash table to remove the key from.
* @param key
* Key to remove from the hash table.
* @param sig
- * Hash value to remove from the hash table.
+ * Precomputed hash value for 'key'.
* @return
* - -EINVAL if the parameters are invalid.
* - -ENOENT if the key is not found.
@@ -201,12 +203,11 @@ rte_hash_del_key(const struct rte_hash *h, const void *key);
* value that was returned when the key was added.
*/
int32_t
-rte_hash_del_key_with_hash(const struct rte_hash *h,
- const void *key, hash_sig_t sig);
-
+rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
/**
- * Find a key in the hash table. This operation is multi-thread safe.
+ * Find a key in the hash table.
+ * This operation is multi-thread safe.
*
* @param h
* Hash table to look in.
@@ -223,14 +224,15 @@ int32_t
rte_hash_lookup(const struct rte_hash *h, const void *key);
/**
- * Find a key in the hash table. This operation is multi-thread safe.
+ * Find a key in the hash table.
+ * This operation is multi-thread safe.
*
* @param h
* Hash table to look in.
* @param key
* Key to find.
* @param sig
- * Hash value to find.
+ * Hash value to remove from the hash table.
* @return
* - -EINVAL if the parameters are invalid.
* - -ENOENT if the key is not found.
@@ -243,7 +245,8 @@ rte_hash_lookup_with_hash(const struct rte_hash *h,
const void *key, hash_sig_t sig);
/**
- * Calc a hash value by key. This operation is not multi-process safe.
+ * Calc a hash value by key.
+ * This operation is not multi-thread safe.
*
* @param h
* Hash table to look in.
@@ -257,7 +260,8 @@ rte_hash_hash(const struct rte_hash *h, const void *key);
#define rte_hash_lookup_multi rte_hash_lookup_bulk
/**
- * Find multiple keys in the hash table. This operation is multi-thread safe.
+ * Find multiple keys in the hash table.
+ * This operation is multi-thread safe.
*
* @param h
* Hash table to look in.
@@ -277,6 +281,7 @@ rte_hash_hash(const struct rte_hash *h, const void *key);
int
rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
uint32_t num_keys, int32_t *positions);
+
#ifdef __cplusplus
}
#endif
--
2.4.3
More information about the dev
mailing list