* [dpdk-dev] [PATCH 2/3] lib/librte_tshash: New Thread Safe Hash library for DPDK
2014-09-18 10:34 [dpdk-dev] [PATCH 0/3] New Thread Safe Hash Library Pablo de Lara
2014-09-18 10:34 ` [dpdk-dev] [PATCH 1/3] eal: add const in prefetch functions Pablo de Lara
@ 2014-09-18 10:34 ` Pablo de Lara
2014-09-18 10:34 ` [dpdk-dev] [PATCH 3/3] app/test: Added unit tests for Thread Safe Hash library Pablo de Lara
` (2 subsequent siblings)
4 siblings, 0 replies; 9+ messages in thread
From: Pablo de Lara @ 2014-09-18 10:34 UTC (permalink / raw)
To: dev
Added new hash library, as an alternative to the old hash
implementation. This new library allows the user to have
multiple threads reading and writing on the same hash
table at the same time.
Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
config/common_bsdapp | 6 +
config/common_linuxapp | 6 +
lib/Makefile | 1 +
lib/librte_eal/common/include/rte_log.h | 1 +
lib/librte_eal/common/include/rte_tailq_elem.h | 2 +
lib/librte_tshash/Makefile | 49 ++
lib/librte_tshash/rte_tshash.c | 580 ++++++++++++++++++++++++
lib/librte_tshash/rte_tshash.h | 533 ++++++++++++++++++++++
lib/librte_tshash/rte_vector_jhash.h | 332 ++++++++++++++
mk/rte.app.mk | 4 +
10 files changed, 1514 insertions(+), 0 deletions(-)
create mode 100644 lib/librte_tshash/Makefile
create mode 100644 lib/librte_tshash/rte_tshash.c
create mode 100644 lib/librte_tshash/rte_tshash.h
create mode 100644 lib/librte_tshash/rte_vector_jhash.h
diff --git a/config/common_bsdapp b/config/common_bsdapp
index bf6d8a0..90e2755 100644
--- a/config/common_bsdapp
+++ b/config/common_bsdapp
@@ -284,6 +284,12 @@ CONFIG_RTE_LIBRTE_HASH=y
CONFIG_RTE_LIBRTE_HASH_DEBUG=n
#
+# Compile librte_tshash
+#
+CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH=y
+CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH_STATS=y
+
+#
# Compile librte_lpm
#
CONFIG_RTE_LIBRTE_LPM=y
diff --git a/config/common_linuxapp b/config/common_linuxapp
index 9047975..1c8a3d5 100644
--- a/config/common_linuxapp
+++ b/config/common_linuxapp
@@ -312,6 +312,12 @@ CONFIG_RTE_LIBRTE_HASH=y
CONFIG_RTE_LIBRTE_HASH_DEBUG=n
#
+# Compile librte_tshash
+#
+CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH=y
+CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH_STATS=y
+
+#
# Compile librte_lpm
#
CONFIG_RTE_LIBRTE_LPM=y
diff --git a/lib/Makefile b/lib/Makefile
index 10c5bb3..728e6cf 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -51,6 +51,7 @@ DIRS-$(CONFIG_RTE_LIBRTE_VIRTIO_PMD) += librte_pmd_virtio
DIRS-$(CONFIG_RTE_LIBRTE_VMXNET3_PMD) += librte_pmd_vmxnet3
DIRS-$(CONFIG_RTE_LIBRTE_PMD_XENVIRT) += librte_pmd_xenvirt
DIRS-$(CONFIG_RTE_LIBRTE_HASH) += librte_hash
+DIRS-$(CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH) += librte_tshash
DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm
DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl
DIRS-$(CONFIG_RTE_LIBRTE_NET) += librte_net
diff --git a/lib/librte_eal/common/include/rte_log.h b/lib/librte_eal/common/include/rte_log.h
index 565415a..633b203 100644
--- a/lib/librte_eal/common/include/rte_log.h
+++ b/lib/librte_eal/common/include/rte_log.h
@@ -68,6 +68,7 @@ extern struct rte_logs rte_logs;
#define RTE_LOGTYPE_TIMER 0x00000010 /**< Log related to timers. */
#define RTE_LOGTYPE_PMD 0x00000020 /**< Log related to poll mode driver. */
#define RTE_LOGTYPE_HASH 0x00000040 /**< Log related to hash table. */
+#define RTE_LOGTYPE_TSHASH 0x00000040 /**< Log related to thread safe hash table. */
#define RTE_LOGTYPE_LPM 0x00000080 /**< Log related to LPM. */
#define RTE_LOGTYPE_KNI 0x00000100 /**< Log related to KNI. */
#define RTE_LOGTYPE_ACL 0x00000200 /**< Log related to ACL. */
diff --git a/lib/librte_eal/common/include/rte_tailq_elem.h b/lib/librte_eal/common/include/rte_tailq_elem.h
index f74fc7c..446e34b 100644
--- a/lib/librte_eal/common/include/rte_tailq_elem.h
+++ b/lib/librte_eal/common/include/rte_tailq_elem.h
@@ -72,6 +72,8 @@ rte_tailq_elem(RTE_TAILQ_RING, "RTE_RING")
rte_tailq_elem(RTE_TAILQ_HASH, "RTE_HASH")
+rte_tailq_elem(RTE_TAILQ_TSHASH, "RTE_TSHASH")
+
rte_tailq_elem(RTE_TAILQ_FBK_HASH, "RTE_FBK_HASH")
rte_tailq_elem(RTE_TAILQ_LPM, "RTE_LPM")
diff --git a/lib/librte_tshash/Makefile b/lib/librte_tshash/Makefile
new file mode 100644
index 0000000..193568d
--- /dev/null
+++ b/lib/librte_tshash/Makefile
@@ -0,0 +1,49 @@
+# BSD LICENSE
+#
+# Copyright(c) 2010-2014 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 $(RTE_SDK)/mk/rte.vars.mk
+
+# library name
+LIB = librte_tshash.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH) := rte_tshash.c
+
+# install this header file
+SYMLINK-$(CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH)-include := rte_tshash.h
+
+# this lib needs eal
+DEPDIRS-$(CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH) += lib/librte_eal lib/librte_malloc
+
+include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_tshash/rte_tshash.c b/lib/librte_tshash/rte_tshash.c
new file mode 100644
index 0000000..87fe400
--- /dev/null
+++ b/lib/librte_tshash/rte_tshash.c
@@ -0,0 +1,580 @@
+/**
+ * BSD LICENSE
+ *
+ * Copyright(c) 2010-2014 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 <x86intrin.h>
+
+#include <rte_tailq.h>
+#include <rte_malloc.h>
+#include <rte_memzone.h>
+#include <rte_eal_memconfig.h>
+#include <rte_common.h>
+#include <rte_string_fns.h>
+#include <rte_errno.h>
+#include <rte_memcpy.h>
+#include <rte_rwlock.h>
+#include <rte_log.h>
+
+#include "rte_tshash.h"
+
+#define DEFAULT_LOAD_FACTOR (0.5)
+
+/* Hash function used if none is specified */
+#ifdef RTE_MACHINE_CPUFLAG_SSE4_2
+#include <rte_hash_crc.h>
+#define DEFAULT_TSHASH_FUNC rte_hash_crc
+#else
+#include <rte_jhash.h>
+#define DEFAULT_TSHASH_FUNC rte_jhash
+#endif
+
+TAILQ_HEAD(rte_tshash_list, rte_tshash);
+
+static int rte_tshash_k16_cmp_eq(const void *key1, const void *key2,
+ __rte_unused uint8_t key_size);
+static int rte_tshash_k32_cmp_eq(const void *key1, const void *key2,
+ uint8_t key_size);
+static int rte_tshash_k48_cmp_eq(const void *key1, const void *key2,
+ uint8_t key_size);
+static int rte_tshash_k64_cmp_eq(const void *key1, const void *key2,
+ uint8_t key_size);
+static int rte_tshash_k96_cmp_eq(const void *key1, const void *key2,
+ uint8_t key_size);
+static int rte_tshash_k128_cmp_eq(const void *key1, const void *key2,
+ uint8_t key_size);
+
+struct rte_tshash *
+rte_tshash_create(const char *name, unsigned max_entries,
+ unsigned key_size, int socket_id,
+ const struct rte_tshash_extra_args *e_args)
+{
+ const int noflags = 0;
+ const unsigned anyalignment = 0;
+
+ struct rte_tshash *h = NULL;
+ struct rte_tshash_list *tshash_list;
+ void *k = NULL;
+ struct rte_ring *r = NULL;
+ char ring_name[RTE_RING_NAMESIZE];
+ unsigned use_malloc = 0;
+ unsigned update_add = 0;
+ double load_factor = DEFAULT_LOAD_FACTOR;
+ rte_tshash_cmp_eq_t tshash_cmp_eq_param = NULL;
+ rte_tshash_function_t tshash_func_param = NULL;
+
+ uint32_t num_hashes;
+ uint32_t num_buckets;
+ unsigned key_entry_size;
+ unsigned i;
+
+ RTE_BUILD_BUG_ON(sizeof(struct rte_tshash_bucket) != CACHE_LINE_SIZE);
+
+ if (name == NULL || max_entries < RTE_TSHASH_MIN_ENTRIES ||
+ socket_id >= RTE_MAX_NUMA_NODES)
+ goto param_err;
+
+ if (e_args != NULL) {
+ use_malloc = e_args->malloc_mem;
+ load_factor = e_args->max_load_factor;
+ tshash_cmp_eq_param = e_args->rte_tshash_cmp_eq;
+ tshash_func_param = e_args->hash_func;
+ update_add = e_args->update_add;
+
+ if (load_factor > RTE_TSHASH_MAXIMUM_LOAD_FACTOR)
+ goto param_err;
+ }
+
+ /* check the key-size is a supported value */
+ if (key_size != 16 && key_size != 32 && key_size != 48 &&
+ key_size != 64 && key_size != 96 && key_size != 128)
+ if (!tshash_cmp_eq_param)
+ goto param_err;
+
+ if (key_size == 0)
+ goto param_err;
+
+ /* check that we have an initialised tail queue */
+ tshash_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_TSHASH, rte_tshash_list);
+ if (tshash_list == NULL) {
+ rte_errno = E_RTE_NO_TAILQ;
+ return NULL;
+ }
+
+ /* calculate number of hash values entries to be used. Floating point
+ * can be inaccurate, so subtract a bit so that we don't accidently
+ * overflow a power of 2, and then scale up to the next one unnecessarily
+ */
+ num_hashes = ((double)max_entries / load_factor) - 2;
+ num_hashes = rte_align32pow2(num_hashes);
+ num_buckets = num_hashes / RTE_TSHASH_BUCKET_SIZE;
+
+
+ /* whatever number of entries for keys we want, we need 1 more as a dummy
+ * entry, which is used in case of a miss on a bucket scan.
+ */
+ max_entries++;
+
+ key_entry_size = sizeof(struct rte_tshash_key) + key_size;
+
+ if (use_malloc) {
+ h = rte_zmalloc_socket(NULL, sizeof(*h) +
+ (sizeof(h->bkts[1]) * num_buckets),
+ anyalignment, socket_id);
+ if (h == NULL)
+ goto memory_err;
+
+ k = rte_zmalloc_socket(NULL, key_entry_size * max_entries,
+ anyalignment, socket_id);
+ if (k == NULL)
+ goto memory_err;
+
+ } else {
+ char mz_name[RTE_MEMZONE_NAMESIZE];
+ char key_mz_name[RTE_MEMZONE_NAMESIZE];
+ const struct rte_memzone *mz;
+
+ snprintf(mz_name, sizeof(mz_name), "HSH_%s", name);
+ snprintf(key_mz_name, sizeof(key_mz_name), "HSH_KEYS_%s", name);
+
+ mz = rte_memzone_reserve(mz_name, sizeof(*h) +
+ (sizeof(h->bkts[1]) * num_buckets),
+ socket_id, noflags);
+ if (mz == NULL)
+ goto memory_err;
+ h = mz->addr;
+
+ mz = rte_memzone_reserve(key_mz_name, key_entry_size * max_entries,
+ socket_id, noflags);
+ if (mz == NULL)
+ goto memory_err;
+ k = mz->addr;
+ }
+ snprintf(ring_name, sizeof(ring_name), "HSH_%s", name);
+ r = rte_ring_create(ring_name, rte_align32pow2(max_entries), socket_id,
+ noflags);
+ if (r == NULL)
+ goto memory_err;
+
+ RTE_LOG(INFO, TSHASH, "Created Hash Table\n");
+ RTE_LOG(INFO, TSHASH, "-> Hash value slots: %u\n", num_hashes);
+ RTE_LOG(INFO, TSHASH, "-> Hash key slots : %u\n", max_entries);
+ RTE_LOG(INFO, TSHASH, "-> Free ring size : %u\n",
+ rte_align32pow2(max_entries + 1));
+ RTE_LOG(INFO, TSHASH, "-> Buckets : %u\n", num_buckets);
+
+ /* add the free slots ring to the hash table, and do other assignments */
+ h->free_slots = r;
+ h->key_store = k;
+ h->socket_id = socket_id;
+ h->bucket_mask = (num_buckets - 1);
+ h->key_entry_size = key_entry_size;
+ h->key_size = key_size;
+ h->max_items = max_entries;
+ h->rte_tshash_cmp_eq = tshash_cmp_eq_param;
+
+ if (h->rte_tshash_cmp_eq == NULL)
+ switch (h->key_size) {
+ case 16:
+ h->rte_tshash_cmp_eq = rte_tshash_k16_cmp_eq;
+ break;
+ case 32:
+ h->rte_tshash_cmp_eq = rte_tshash_k32_cmp_eq;
+ break;
+ case 48:
+ h->rte_tshash_cmp_eq = rte_tshash_k48_cmp_eq;
+ break;
+ case 64:
+ h->rte_tshash_cmp_eq = rte_tshash_k64_cmp_eq;
+ break;
+ case 96:
+ h->rte_tshash_cmp_eq = rte_tshash_k96_cmp_eq;
+ break;
+ case 128:
+ h->rte_tshash_cmp_eq = rte_tshash_k128_cmp_eq;
+ break;
+ }
+
+ if (tshash_func_param)
+ h->tshash_func = tshash_func_param;
+ else
+ h->tshash_func = DEFAULT_TSHASH_FUNC;
+
+ h->update_add = update_add;
+
+ snprintf(h->name, sizeof(h->name), "%s", name);
+
+ /* populate the free slots ring. Entry zero is reserved for key misses */
+ for (i = 1; i < max_entries; i++)
+ rte_ring_sp_enqueue(r, (void *)((uintptr_t)i));
+
+ TAILQ_INSERT_TAIL(tshash_list, h, next);
+ return h;
+
+param_err:
+ rte_errno = EINVAL;
+ return NULL;
+
+memory_err:
+ if (use_malloc) {
+ if (h != NULL)
+ rte_free(h);
+ if (k != NULL)
+ rte_free(k);
+ }
+ rte_errno = ENOMEM;
+ return NULL;
+}
+
+void
+rte_tshash_reset(struct rte_tshash *h)
+{
+ unsigned i;
+ void *ptr;
+ struct rte_tshash_bucket *next_bucket_to_delete, *bucket_to_delete;
+
+ /* first: rte_free the extra buckets */
+ for (i = 0; i < h->bucket_mask+1; i++) {
+ next_bucket_to_delete = h->bkts[i].next;
+ while (next_bucket_to_delete) {
+ bucket_to_delete = next_bucket_to_delete;
+ next_bucket_to_delete = bucket_to_delete->next;
+ rte_free(bucket_to_delete);
+ }
+ }
+ /* zero the buckets */
+ memset(h->bkts, 0, (h->bucket_mask+1)*sizeof(h->bkts[0]));
+
+ /* clear the free ring */
+ while (rte_ring_dequeue(h->free_slots, &ptr) == 0)
+ rte_pause();
+
+ /* zero key slots */
+ memset(h->key_store, 0, h->key_entry_size * h->max_items);
+ /* Repopulate the free ring. Entry zero is reserved for key misses */
+ for (i = 1; i < h->max_items; i++)
+ rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)i));
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ /* zero the stats */
+ h->stats.num_extra_buckets = h->stats.used_slots = 0;
+#endif
+}
+
+struct rte_tshash *
+rte_tshash_find_existing(const char *name)
+{
+ struct rte_tshash *h;
+ struct rte_tshash_list *tshash_list;
+
+ /* check that we have an initialised tail queue */
+ tshash_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_TSHASH, rte_tshash_list);
+ if (tshash_list == NULL) {
+ rte_errno = E_RTE_NO_TAILQ;
+ return NULL;
+ }
+
+ rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
+ TAILQ_FOREACH(h, tshash_list, next) {
+ if (strncmp(name, h->name, RTE_TSHASH_NAMESIZE) == 0)
+ break;
+ }
+ rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+ if (h == NULL)
+ rte_errno = ENOENT;
+ return h;
+}
+
+static int
+rte_tshash_k16_cmp_eq(const void *key1, const void *key2,
+ __rte_unused uint8_t key_size)
+{
+ const __m128i k1 = _mm_load_si128((const __m128i *) key1);
+ const __m128i k2 = _mm_load_si128((const __m128i *) key2);
+ const __m128i x = _mm_xor_si128(k1, k2);
+ return _mm_test_all_zeros(x, x);
+}
+
+static int
+rte_tshash_k32_cmp_eq(const void *key1, const void *key2, uint8_t key_size)
+{
+ return rte_tshash_k16_cmp_eq(key1, key2, key_size) &&
+ rte_tshash_k16_cmp_eq((const char *)key1+16,
+ (const char *)key2+16, key_size);
+}
+
+static int
+rte_tshash_k48_cmp_eq(const void *key1, const void *key2, uint8_t key_size)
+{
+ return rte_tshash_k16_cmp_eq(key1, key2, key_size) &&
+ rte_tshash_k16_cmp_eq((const char *)key1+16,
+ (const char *)key2+16, key_size) &&
+ rte_tshash_k16_cmp_eq((const char *)key1+32,
+ (const char *)key2+32, key_size);
+}
+
+static int
+rte_tshash_k64_cmp_eq(const void *key1, const void *key2, uint8_t key_size)
+{
+ return rte_tshash_k32_cmp_eq(key1, key2, key_size) &&
+ rte_tshash_k32_cmp_eq((const char *)key1+32,
+ (const char *)key2+32, key_size);
+}
+
+static int
+rte_tshash_k96_cmp_eq(const void *key1, const void *key2, uint8_t key_size)
+{
+ return rte_tshash_k64_cmp_eq(key1, key2, key_size) &&
+ rte_tshash_k32_cmp_eq((const char *)key1+64,
+ (const char *)key2+64, key_size);
+}
+
+static int
+rte_tshash_k128_cmp_eq(const void *key1, const void *key2, uint8_t key_size)
+{
+ return rte_tshash_k64_cmp_eq(key1, key2, key_size) &&
+ rte_tshash_k64_cmp_eq((const char *)key1+64,
+ (const char *)key2+64, key_size);
+}
+
+int
+rte_tshash_add_key_with_hash(struct rte_tshash *h, uint64_t hash_val,
+ const void *key, uintptr_t idata)
+{
+ struct rte_tshash_bucket *bkt = &h->bkts[hash_val & h->bucket_mask];
+ struct rte_tshash_bucket *add_bkt = NULL;
+ struct rte_tshash_key *key_slot, *keys = h->key_store;
+ void *slot_id;
+ unsigned pos = 0;
+ int free_pos = -1;
+
+ rte_prefetch0(bkt);
+
+ if (rte_ring_mc_dequeue(h->free_slots, &slot_id) != 0)
+ return -ENOSPC;
+
+ key_slot = (struct rte_tshash_key *)((char *)keys +
+ (uintptr_t)slot_id * h->key_entry_size);
+ rte_prefetch0(key_slot);
+
+ do {
+ for (pos = 0; pos < RTE_TSHASH_BUCKET_SIZE; pos++) {
+ /*
+ * If free slot has not been found yet and current one
+ * is empty, make it invalid for later use
+ */
+ if (free_pos == -1 && bkt->hash_val[pos] == RTE_TSHASH_EMPTY) {
+ if (__sync_bool_compare_and_swap(&bkt->hash_val[pos],
+ RTE_TSHASH_EMPTY, RTE_TSHASH_INVALID)) {
+ free_pos = pos;
+ add_bkt = bkt;
+ } else
+ continue;
+ } else if (bkt->hash_val[pos] == (hash_val | RTE_TSHASH_VALID)) {
+ /* check key for match */
+ struct rte_tshash_key *k = (struct rte_tshash_key *)
+ ((char *)keys + bkt->key_idx[pos] * h->key_entry_size);
+ if (h->rte_tshash_cmp_eq((const void *)k->key,
+ key, h->key_size)) {
+ rte_ring_mp_enqueue(h->free_slots, slot_id);
+ if (free_pos >= 0)
+ bkt->hash_val[free_pos] = RTE_TSHASH_EMPTY;
+ if (!h->update_add)
+ return -EEXIST;
+ /* Update just data */
+ rte_atomic64_set((rte_atomic64_t *)&k->idata, idata);
+ return 0;
+ }
+ }
+ }
+ if (pos == RTE_TSHASH_BUCKET_SIZE) {
+ if (bkt->next == NULL && free_pos < 0) {
+ void *new_bkt = rte_zmalloc(NULL,
+ sizeof(struct rte_tshash_bucket), 0);
+ if (new_bkt == NULL) {
+ rte_ring_mp_enqueue(h->free_slots, slot_id);
+ return -ENOMEM;
+ }
+ if (!__sync_bool_compare_and_swap(&bkt->next, NULL, new_bkt)) {
+ /* if we can't add the new bucket, tell user to retry */
+ rte_ring_mp_enqueue(h->free_slots, slot_id);
+ rte_free(new_bkt);
+ return -EAGAIN;
+ }
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ __sync_fetch_and_add(&h->stats.num_extra_buckets, 1);
+#endif
+ }
+ bkt = bkt->next;
+ rte_prefetch0(bkt);
+ pos = 0;
+ }
+ } while (bkt);
+
+ __sync_fetch_and_add(&key_slot->counter, 1);
+ rte_compiler_barrier();
+ rte_memcpy(key_slot->key, key, h->key_size);
+ key_slot->idata = idata;
+
+ add_bkt->key_idx[free_pos] = (uint32_t)((uintptr_t)slot_id);
+ add_bkt->counter[free_pos] = key_slot->counter;
+ rte_compiler_barrier();
+ add_bkt->hash_val[free_pos] = hash_val | RTE_TSHASH_VALID;
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ __sync_fetch_and_add(&h->stats.used_slots, 1);
+#endif
+ return 0;
+}
+
+int
+rte_tshash_add_key(struct rte_tshash *h, const void *key, uintptr_t idata)
+{
+ return rte_tshash_add_key_with_hash(h, rte_tshash_hash(h, key), key, idata);
+}
+
+int
+rte_tshash_del_key_with_hash(struct rte_tshash *h,
+ uint64_t hash_val, const void *key, uintptr_t *value)
+{
+ struct rte_tshash_key *keys[RTE_TSHASH_BUCKET_SIZE] = {0};
+ unsigned i;
+ struct rte_tshash_bucket *bkt = &h->bkts[hash_val & h->bucket_mask];
+ struct rte_tshash_key *key_store = h->key_store;
+ _mm_prefetch((const char *)bkt, 0);
+
+ do {
+ rte_prefetch0(bkt->next);
+
+ /* Check if there is a hash value match */
+ for (i = 0; i < RTE_TSHASH_BUCKET_SIZE; i++)
+ if (bkt->hash_val[i] == (hash_val | RTE_TSHASH_VALID)) {
+ keys[i] = (struct rte_tshash_key *)((char *)key_store +
+ (bkt->key_idx[i] * h->key_entry_size));
+ rte_prefetch0((const char *)&keys[i]);
+ }
+
+ for (i = 0; i < RTE_TSHASH_BUCKET_SIZE; i++) {
+ if (keys[i] != 0 && h->rte_tshash_cmp_eq((const void *) keys[i]->key,
+ key, h->key_size)) {
+ if (!__sync_bool_compare_and_swap(&bkt->hash_val[i],
+ hash_val | RTE_TSHASH_VALID, RTE_TSHASH_EMPTY))
+ /* Already deleted */
+ return 0;
+
+ rte_compiler_barrier();
+
+ /*
+ * If user wants to free the data associated to this entry,
+ * the pointer shall be returned
+ */
+ if (value != NULL)
+ *value = keys[i]->idata;
+
+ /* TODO: Remove bucket if all entries in it are empty */
+ rte_ring_mp_enqueue(h->free_slots,
+ (void *)((uintptr_t)bkt->key_idx[i]));
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ __sync_fetch_and_sub(&h->stats.used_slots, 1);
+#endif
+ return 0;
+ }
+ }
+
+ bkt = bkt->next;
+
+ } while (bkt);
+
+ /* No such key stored */
+ return -1;
+}
+
+int
+rte_tshash_del_key(struct rte_tshash *h, const void *key, uintptr_t *value)
+{
+ return rte_tshash_del_key_with_hash(h, rte_tshash_hash(h, key), key, value);
+}
+
+int
+rte_tshash_lookup_with_hash(const struct rte_tshash *h,
+ uint64_t hash_val, const void *key, uintptr_t *value)
+{
+ const struct rte_tshash_key *keys[RTE_TSHASH_BUCKET_SIZE] = {0};
+ unsigned num_slots;
+ unsigned i;
+ const struct rte_tshash_bucket *bkt = &h->bkts[hash_val & h->bucket_mask];
+ const struct rte_tshash_key *key_store = h->key_store;
+ uint8_t counters[RTE_TSHASH_BUCKET_SIZE] = {0};
+
+ rte_prefetch0((const char *)bkt);
+
+ do {
+ rte_prefetch0(bkt->next);
+ num_slots = 0;
+
+ /* Check if there is a hash value match */
+ for (i = 0; i < RTE_TSHASH_BUCKET_SIZE; i++)
+ if (bkt->hash_val[i] == (hash_val | RTE_TSHASH_VALID)) {
+ keys[num_slots] = (const struct rte_tshash_key *)
+ ((const char *)key_store +
+ (bkt->key_idx[i] * h->key_entry_size));
+ rte_prefetch0((const char *)&keys[num_slots]);
+ counters[num_slots] = bkt->counter[i];
+ num_slots++;
+ }
+
+ for (i = 0; i < num_slots; i++) {
+ if (h->rte_tshash_cmp_eq((const void *) keys[i]->key,
+ key, h->key_size)) {
+ *value = keys[i]->idata;
+ rte_compiler_barrier();
+ /* Check counter in key slot is same as counter in bucket */
+ if (unlikely(counters[i] != keys[i]->counter))
+ /* Tell user to retry */
+ return -EAGAIN;
+ return 0;
+ }
+ }
+
+ bkt = bkt->next;
+
+ } while (bkt);
+
+ return -1;
+}
+
+int
+rte_tshash_lookup(const struct rte_tshash *h, const void *key,
+ uintptr_t *value)
+{
+ return rte_tshash_lookup_with_hash(h, rte_tshash_hash(h, key), key, value);
+}
+
+
diff --git a/lib/librte_tshash/rte_tshash.h b/lib/librte_tshash/rte_tshash.h
new file mode 100644
index 0000000..2ea05b3
--- /dev/null
+++ b/lib/librte_tshash/rte_tshash.h
@@ -0,0 +1,533 @@
+/**
+ * BSD LICENSE
+ *
+ * Copyright(c) 2010-2014 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.
+ */
+
+#ifndef _RTE_RTE_TSHASH_H_
+#define _RTE_RTE_TSHASH_H_
+
+#include <stdint.h>
+
+#include <rte_memory.h>
+#include <rte_ring.h>
+#include <rte_prefetch.h>
+#include <rte_branch_prediction.h>
+#include <rte_malloc.h>
+#include <rte_memcpy.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/** Max number of characters in hash name.*/
+#define RTE_TSHASH_NAMESIZE 32
+
+/** Number of elements in each bucket */
+#define RTE_TSHASH_BUCKET_SIZE 4
+
+#define RTE_TSHASH_MAX_BURST 64
+#define RTE_TSHASH_MIN_ENTRIES 32
+
+#define RTE_TSHASH_MAXIMUM_LOAD_FACTOR (1.0)
+
+typedef uint32_t (*rte_tshash_function_t)(const void *key, uint32_t key_len,
+ uint32_t init_val);
+typedef int (*rte_tshash_cmp_eq_t)(const void *key1, const void *key2,
+ uint8_t key_len);
+
+enum {
+ RTE_TSHASH_EMPTY = 0,
+ RTE_TSHASH_INVALID = 1,
+ RTE_TSHASH_VALID = 3
+};
+
+struct rte_tshash_extra_args {
+ double max_load_factor;
+ unsigned malloc_mem;
+ rte_tshash_cmp_eq_t rte_tshash_cmp_eq;
+ rte_tshash_function_t hash_func;
+ unsigned update_add;
+};
+
+struct rte_tshash_bucket {
+ uint64_t hash_val[RTE_TSHASH_BUCKET_SIZE];
+ uint32_t key_idx[RTE_TSHASH_BUCKET_SIZE + 1]; /* have dummy entry on end,
+ always points to entry zero */
+
+ uint8_t counter[RTE_TSHASH_BUCKET_SIZE];
+
+ struct rte_tshash_bucket *next;
+} __rte_cache_aligned;
+
+struct rte_tshash_key {
+ union {
+ uintptr_t idata;
+ void *pdata;
+ };
+ uint8_t counter;
+ /* Variable key size */
+ char key[] __attribute__((aligned(16)));
+};
+
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+struct rte_tshash_stats {
+ unsigned used_slots;
+ unsigned num_extra_buckets;
+};
+#endif
+
+struct rte_tshash {
+ TAILQ_ENTRY(rte_tshash) next;/**< Next in list. */
+ char name[RTE_TSHASH_NAMESIZE];
+
+ unsigned key_size __rte_cache_aligned;
+ unsigned key_entry_size;
+ unsigned bucket_mask;
+ unsigned socket_id;
+ unsigned max_items;
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ struct rte_tshash_stats stats;
+#endif
+
+ struct rte_ring *free_slots;
+ void *key_store;
+
+ rte_tshash_cmp_eq_t rte_tshash_cmp_eq;
+ rte_tshash_function_t tshash_func;
+ uint32_t tshash_func_init_val;
+
+ unsigned update_add;
+
+ struct rte_tshash_bucket bkts[];
+} __rte_cache_aligned;
+
+
+struct rte_tshash *
+rte_tshash_create(const char *name, unsigned max_entries, unsigned key_size,
+ int socket_id, const struct rte_tshash_extra_args *e_args);
+
+struct rte_tshash *
+rte_tshash_find_existing(const char *name);
+
+void
+rte_tshash_reset(struct rte_tshash *h);
+
+static inline uint64_t
+rte_tshash_hash(const struct rte_tshash *h, const void *key)
+{
+ /* calc hash result by key */
+ return h->tshash_func(key, h->key_size, h->tshash_func_init_val);
+}
+
+int
+rte_tshash_add_key_with_hash(struct rte_tshash *h, uint64_t hash_val,
+ const void *key, uintptr_t idata);
+int
+rte_tshash_add_key(struct rte_tshash *h, const void *key, uintptr_t idata);
+
+int
+rte_tshash_del_key_with_hash(struct rte_tshash *h, uint64_t hash_val,
+ const void *key, uintptr_t *value);
+
+int
+rte_tshash_del_key(struct rte_tshash *h, const void *key, uintptr_t *value);
+
+int
+rte_tshash_lookup_with_hash(const struct rte_tshash *h,
+ uint64_t hash_val, const void *key, uintptr_t *value);
+
+int
+rte_tshash_lookup(const struct rte_tshash *h, const void *key, uintptr_t *value);
+
+
+/* Lookup bulk stage 0: Prefetch next hash value */
+static inline void
+lookup_stage0(unsigned *idx, uint64_t *lookup_mask,
+ uint64_t *const *hash_vals __rte_unused)
+{
+ *idx = __builtin_ctzl(*lookup_mask);
+ if (*lookup_mask == 0)
+ *idx = 0;
+ rte_prefetch0(hash_vals[*idx]);
+ *lookup_mask &= ~(1llu << *idx);
+}
+
+/* Lookup bulk stage 0: Calculate next hash value (from new key) */
+static inline void
+lookup_stage0_key(unsigned *idx, uint64_t *lookup_mask, uint64_t *calc_hash,
+ const void * const *keys, const struct rte_tshash *h)
+{
+ *idx = __builtin_ctzl(*lookup_mask);
+ if (*lookup_mask == 0)
+ *idx = 0;
+
+ *calc_hash = rte_tshash_hash(h, keys[*idx]);
+ *lookup_mask &= ~(1llu << *idx);
+}
+
+
+/* Lookup bulk stage 1: Get next hash value and prefetch associated bucket */
+static inline void
+lookup_stage1(unsigned idx, uint64_t *hash, const struct rte_tshash_bucket **bkt,
+ uint64_t *const *hash_vals, const struct rte_tshash *h)
+{
+ *hash = *hash_vals[idx];
+ *bkt = &h->bkts[*hash & h->bucket_mask];
+ rte_prefetch0(*bkt);
+
+ *hash |= RTE_TSHASH_VALID;
+}
+
+
+/* Lookup bulk stage 1: Prefetch associated bucket */
+static inline void
+lookup_stage1_key(uint64_t *hash, const struct rte_tshash_bucket **bkt,
+ const struct rte_tshash *h)
+{
+ *bkt = &h->bkts[*hash & h->bucket_mask];
+ rte_prefetch0(*bkt);
+
+ *hash |= RTE_TSHASH_VALID;
+}
+
+
+/*
+ * Lookup bulk stage 2: Store pointer to next bucket (if any). Search for match
+ * hashes in first level and prefetch first key slot
+ */
+static inline void
+lookup_stage2(unsigned idx, uint64_t hash, const struct rte_tshash_bucket *bkt,
+ const struct rte_tshash_key **key_slot, uint8_t *counter,
+ uint64_t *next_mask, uint64_t *extra_hits_mask,
+ const struct rte_tshash_bucket *next_bkts[],
+ const struct rte_tshash_key *key_store, const struct rte_tshash *h)
+{
+ unsigned hash_matches, i;
+
+ *next_mask |= (uint64_t)(!!bkt->next) << idx;
+ next_bkts[idx] = bkt->next;
+
+ hash_matches = 1 << RTE_TSHASH_BUCKET_SIZE;
+ for (i = 0; i < RTE_TSHASH_BUCKET_SIZE; i++)
+ hash_matches |= ((hash == bkt->hash_val[i]) << i);
+
+ unsigned key_idx = bkt->key_idx[__builtin_ctzl(hash_matches)];
+ *key_slot = (const struct rte_tshash_key *)((const char *)key_store +
+ key_idx * h->key_entry_size);
+ rte_prefetch0(*key_slot);
+ *counter = bkt->counter[__builtin_ctz(hash_matches)];
+
+ *extra_hits_mask |= (uint64_t)(__builtin_popcount(hash_matches) > 2) << idx;
+}
+
+
+/*
+ * Lookup bulk stage 3: Check if key matches, update hit mask
+ * and store data in values[]
+ */
+static inline void
+lookup_stage3(unsigned idx, const struct rte_tshash_key *key_slot,
+ uint8_t counter, uintptr_t values[], const void * const *keys,
+ uint64_t *hits, const struct rte_tshash *h)
+{
+ values[idx] = key_slot->idata;
+ unsigned hit = h->rte_tshash_cmp_eq((const void *)key_slot->key,
+ keys[idx], h->key_size);
+ rte_compiler_barrier();
+ *hits |= (uint64_t)(hit & (key_slot->counter == counter)) << idx;
+}
+
+
+static inline int
+rte_tshash_lookup_bulk_with_hash(const struct rte_tshash *h,
+ uint64_t lookup_mask, uint64_t *const *hash_vals,
+ const void * const *keys, uintptr_t values[], uint64_t *hit_mask)
+{
+ uint64_t hits = 0;
+ uint64_t next_mask = 0;
+ uint64_t extra_hits_mask = 0;
+ const struct rte_tshash_key *key_store = h->key_store;
+ const struct rte_tshash_bucket *next_bkts[RTE_TSHASH_MAX_BURST];
+
+ unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31;
+ const struct rte_tshash_bucket *bkt10, *bkt11, *bkt20, *bkt21;
+ const struct rte_tshash_key *k_slot20, *k_slot21, *k_slot30, *k_slot31;
+ uint64_t hash10, hash11, hash20, hash21;
+ uint8_t counter20, counter21, counter30, counter31;
+
+ lookup_stage0(&idx00, &lookup_mask, hash_vals);
+ lookup_stage0(&idx01, &lookup_mask, hash_vals);
+
+ idx10 = idx00, idx11 = idx01;
+ lookup_stage0(&idx00, &lookup_mask, hash_vals);
+ lookup_stage0(&idx01, &lookup_mask, hash_vals);
+ lookup_stage1(idx10, &hash10, &bkt10, hash_vals, h);
+ lookup_stage1(idx11, &hash11, &bkt11, hash_vals, h);
+
+ bkt20 = bkt10, bkt21 = bkt11;
+ hash20 = hash10, hash21 = hash11;
+ idx20 = idx10, idx21 = idx11;
+ idx10 = idx00, idx11 = idx01;
+
+ lookup_stage0(&idx00, &lookup_mask, hash_vals);
+ lookup_stage0(&idx01, &lookup_mask, hash_vals);
+ lookup_stage1(idx10, &hash10, &bkt10, hash_vals, h);
+ lookup_stage1(idx11, &hash11, &bkt11, hash_vals, h);
+ lookup_stage2(idx20, hash20, bkt20, &k_slot20, &counter20,
+ &next_mask, &extra_hits_mask,
+ next_bkts, key_store, h);
+ lookup_stage2(idx21, hash21, bkt21, &k_slot21, &counter21,
+ &next_mask, &extra_hits_mask,
+ next_bkts, key_store, h);
+
+ while (lookup_mask) {
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ counter30 = counter20, counter31 = counter21;
+ bkt20 = bkt10, bkt21 = bkt11;
+ hash20 = hash10, hash21 = hash11;
+ idx20 = idx10, idx21 = idx11;
+ idx10 = idx00, idx11 = idx01;
+
+ lookup_stage0(&idx00, &lookup_mask, hash_vals);
+ lookup_stage0(&idx01, &lookup_mask, hash_vals);
+ lookup_stage1(idx10, &hash10, &bkt10, hash_vals, h);
+ lookup_stage1(idx11, &hash11, &bkt11, hash_vals, h);
+ lookup_stage2(idx20, hash20, bkt20, &k_slot20, &counter20,
+ &next_mask, &extra_hits_mask, next_bkts, key_store, h);
+ lookup_stage2(idx21, hash21, bkt21, &k_slot21, &counter21,
+ &next_mask, &extra_hits_mask, next_bkts, key_store, h);
+ lookup_stage3(idx30, k_slot30, counter30, values, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, counter31, values, keys, &hits, h);
+ }
+
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ counter30 = counter20, counter31 = counter21;
+ bkt20 = bkt10, bkt21 = bkt11;
+ hash20 = hash10, hash21 = hash11;
+ idx20 = idx10, idx21 = idx11;
+ idx10 = idx00, idx11 = idx01;
+ lookup_stage1(idx10, &hash10, &bkt10, hash_vals, h);
+ lookup_stage1(idx11, &hash11, &bkt11, hash_vals, h);
+ lookup_stage2(idx20, hash20, bkt20,
+ &k_slot20, &counter20, &next_mask, &extra_hits_mask,
+ next_bkts, key_store, h);
+ lookup_stage2(idx21, hash21, bkt21,
+ &k_slot21, &counter21, &next_mask, &extra_hits_mask,
+ next_bkts, key_store, h);
+ lookup_stage3(idx30, k_slot30, counter30, values, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, counter31, values, keys, &hits, h);
+
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ counter30 = counter20, counter31 = counter21;
+ bkt20 = bkt10, bkt21 = bkt11;
+ hash20 = hash10, hash21 = hash11;
+ idx20 = idx10, idx21 = idx11;
+ lookup_stage2(idx20, hash20, bkt20, &k_slot20, &counter20, &next_mask,
+ &extra_hits_mask, next_bkts, key_store, h);
+ lookup_stage2(idx21, hash21, bkt21, &k_slot21, &counter21, &next_mask,
+ &extra_hits_mask, next_bkts, key_store, h);
+ lookup_stage3(idx30, k_slot30, counter30, values, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, counter31, values, keys, &hits, h);
+
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ counter30 = counter20, counter31 = counter21;
+ lookup_stage3(idx30, k_slot30, counter30, values, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, counter31, values, keys, &hits, h);
+
+ /* handle extra_hits_mask */
+ next_mask |= extra_hits_mask;
+
+ /* ignore any items we have already found */
+ next_mask &= ~hits;
+
+ if (unlikely(next_mask)) {
+ /* run a single search for each remaining item */
+ do {
+ unsigned idx = __builtin_ctzl(next_mask);
+ rte_prefetch0(next_bkts[idx]);
+ hits |= (uint64_t)(!rte_tshash_lookup_with_hash(h,
+ *hash_vals[idx], keys[idx], &values[idx])) << idx;
+ next_mask &= ~(1llu << idx);
+ } while (next_mask);
+ }
+
+ *hit_mask = hits;
+ return __builtin_popcountl(hits);
+}
+
+static inline int
+rte_tshash_lookup_bulk(const struct rte_tshash *h,
+ uint64_t lookup_mask, const void * const *keys,
+ uintptr_t values[], uint64_t *hit_mask)
+{
+ uint64_t hits = 0;
+ uint64_t next_mask = 0;
+ uint64_t extra_hits_mask = 0;
+ unsigned idx;
+
+ const struct rte_tshash_key *key_store = h->key_store;
+ const struct rte_tshash_bucket *next_bkts[RTE_TSHASH_MAX_BURST];
+
+ unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31;
+ const struct rte_tshash_bucket *bkt10, *bkt11, *bkt20, *bkt21;
+ const struct rte_tshash_key *k_slot20, *k_slot21, *k_slot30, *k_slot31;
+ uint64_t hash00, hash01, hash10, hash11, hash20, hash21;
+ uint8_t counter20, counter21, counter30, counter31;
+
+ lookup_stage0_key(&idx00, &lookup_mask, &hash00, keys, h);
+ lookup_stage0_key(&idx01, &lookup_mask, &hash01, keys, h);
+
+ hash10 = hash00, hash11 = hash01;
+ idx10 = idx00, idx11 = idx01;
+ lookup_stage0_key(&idx00, &lookup_mask, &hash00, keys, h);
+ lookup_stage0_key(&idx01, &lookup_mask, &hash01, keys, h);
+ lookup_stage1_key(&hash10, &bkt10, h);
+ lookup_stage1_key(&hash11, &bkt11, h);
+
+ bkt20 = bkt10, bkt21 = bkt11;
+ hash20 = hash10, hash21 = hash11;
+ idx20 = idx10, idx21 = idx11;
+ hash10 = hash00, hash11 = hash01;
+ idx10 = idx00, idx11 = idx01;
+
+ lookup_stage0_key(&idx00, &lookup_mask, &hash00, keys, h);
+ lookup_stage0_key(&idx01, &lookup_mask, &hash01, keys, h);
+ lookup_stage1_key(&hash10, &bkt10, h);
+ lookup_stage1_key(&hash11, &bkt11, h);
+ lookup_stage2(idx20, hash20, bkt20, &k_slot20, &counter20,
+ &next_mask, &extra_hits_mask,
+ next_bkts, key_store, h);
+ lookup_stage2(idx21, hash21, bkt21, &k_slot21, &counter21,
+ &next_mask, &extra_hits_mask,
+ next_bkts, key_store, h);
+
+ while (lookup_mask) {
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ counter30 = counter20, counter31 = counter21;
+ bkt20 = bkt10, bkt21 = bkt11;
+ hash20 = hash10, hash21 = hash11;
+ idx20 = idx10, idx21 = idx11;
+ hash10 = hash00, hash11 = hash01;
+ idx10 = idx00, idx11 = idx01;
+
+ lookup_stage0_key(&idx00, &lookup_mask, &hash00, keys, h);
+ lookup_stage0_key(&idx01, &lookup_mask, &hash01, keys, h);
+ lookup_stage1_key(&hash10, &bkt10, h);
+ lookup_stage1_key(&hash11, &bkt11, h);
+ lookup_stage2(idx20, hash20, bkt20, &k_slot20, &counter20,
+ &next_mask, &extra_hits_mask, next_bkts,
+ key_store, h);
+ lookup_stage2(idx21, hash21, bkt21, &k_slot21, &counter21,
+ &next_mask, &extra_hits_mask, next_bkts,
+ key_store, h);
+ lookup_stage3(idx30, k_slot30, counter30, values, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, counter31, values, keys, &hits, h);
+ }
+
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ counter30 = counter20, counter31 = counter21;
+ bkt20 = bkt10, bkt21 = bkt11;
+ hash20 = hash10, hash21 = hash11;
+ idx20 = idx10, idx21 = idx11;
+ hash10 = hash00, hash11 = hash01;
+ idx10 = idx00, idx11 = idx01;
+ lookup_stage1_key(&hash10, &bkt10, h);
+ lookup_stage1_key(&hash11, &bkt11, h);
+ lookup_stage2(idx20, hash20, bkt20,
+ &k_slot20, &counter20, &next_mask, &extra_hits_mask,
+ next_bkts, key_store, h);
+ lookup_stage2(idx21, hash21, bkt21,
+ &k_slot21, &counter21, &next_mask, &extra_hits_mask,
+ next_bkts, key_store, h);
+ lookup_stage3(idx30, k_slot30, counter30, values, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, counter31, values, keys, &hits, h);
+
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ counter30 = counter20, counter31 = counter21;
+ bkt20 = bkt10, bkt21 = bkt11;
+ hash20 = hash10, hash21 = hash11;
+ idx20 = idx10, idx21 = idx11;
+ lookup_stage2(idx20, hash20, bkt20, &k_slot20, &counter20, &next_mask,
+ &extra_hits_mask, next_bkts, key_store, h);
+ lookup_stage2(idx21, hash21, bkt21, &k_slot21, &counter21, &next_mask,
+ &extra_hits_mask, next_bkts, key_store, h);
+ lookup_stage3(idx30, k_slot30, counter30, values, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, counter31, values, keys, &hits, h);
+
+ k_slot30 = k_slot20, k_slot31 = k_slot21;
+ idx30 = idx20, idx31 = idx21;
+ counter30 = counter20, counter31 = counter21;
+ lookup_stage3(idx30, k_slot30, counter30, values, keys, &hits, h);
+ lookup_stage3(idx31, k_slot31, counter31, values, keys, &hits, h);
+
+ /* handle extra_hits_mask */
+ next_mask |= extra_hits_mask;
+
+ /* ignore any items we have already found */
+ next_mask &= ~hits;
+
+ if (unlikely(next_mask)) {
+ /* run a single search for each remaining item */
+ do {
+ idx = __builtin_ctzl(next_mask);
+ rte_prefetch0(next_bkts[idx]);
+ hits |= (uint64_t)(!rte_tshash_lookup(h, keys[idx],
+ &values[idx])) << idx;
+ next_mask &= ~(1llu << idx);
+ } while (next_mask);
+ }
+
+ *hit_mask = hits;
+ return __builtin_popcountl(hits);
+}
+
+
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+static inline const struct rte_tshash_stats *
+rte_tshash_get_stats(const struct rte_tshash *h)
+{ return &h->stats; }
+#endif
+
+
+
+#ifdef __cplusplus
+}
+#endif
+
+
+#endif
diff --git a/lib/librte_tshash/rte_vector_jhash.h b/lib/librte_tshash/rte_vector_jhash.h
new file mode 100644
index 0000000..17b194e
--- /dev/null
+++ b/lib/librte_tshash/rte_vector_jhash.h
@@ -0,0 +1,332 @@
+/**
+ * BSD LICENSE
+ *
+ * Copyright(c) 2010-2014 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.
+ */
+#ifndef _RTE_VJHASH_H
+#define _RTE_VJHASH_H
+
+#ifndef RTE_LIBRTE_HASH
+#error "Need librte_hash enabled"
+#endif
+
+/**
+ * @file
+ *
+ * jhash, vector versions functions.
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdint.h>
+#include <x86intrin.h>
+
+#include <rte_jhash.h>
+
+#define __rte_jhash_mix4(a, b, c) do { \
+ a = _mm_sub_epi32(a, b); a = _mm_sub_epi32(a, c); \
+ a = _mm_xor_si128(a, _mm_srli_epi32(c, 13)); \
+ b = _mm_sub_epi32(b, c); b = _mm_sub_epi32(b, a); \
+ b = _mm_xor_si128(b, _mm_slli_epi32(a, 8)); \
+ c = _mm_sub_epi32(c, a); c = _mm_sub_epi32(c, b); \
+ c = _mm_xor_si128(c, _mm_srli_epi32(b, 13)); \
+ a = _mm_sub_epi32(a, b); a = _mm_sub_epi32(a, c); \
+ a = _mm_xor_si128(a, _mm_srli_epi32(c, 12)); \
+ b = _mm_sub_epi32(b, c); b = _mm_sub_epi32(b, a); \
+ b = _mm_xor_si128(b, _mm_slli_epi32(a, 16)); \
+ c = _mm_sub_epi32(c, a); c = _mm_sub_epi32(c, b); \
+ c = _mm_xor_si128(c, _mm_srli_epi32(b, 5)); \
+ a = _mm_sub_epi32(a, b); a = _mm_sub_epi32(a, c); \
+ a = _mm_xor_si128(a, _mm_srli_epi32(c, 3)); \
+ b = _mm_sub_epi32(b, c); b = _mm_sub_epi32(b, a); \
+ b = _mm_xor_si128(b, _mm_slli_epi32(a, 10)); \
+ c = _mm_sub_epi32(c, a); c = _mm_sub_epi32(c, b); \
+ c = _mm_xor_si128(c, _mm_srli_epi32(b, 15)); \
+} while (0)
+
+#define BURST 4
+
+static inline void
+_jhash_do_burst(const void *key[], uint32_t key_length,
+ uint32_t initval, uint32_t results[])
+{
+ uint32_t i = 0, len = key_length;
+ const uint32_t **k32 = (void *)key;
+ __m128i a, b, c;
+ __m128i lens;
+
+ a = b = _mm_set1_epi32(RTE_JHASH_GOLDEN_RATIO);
+ c = _mm_set1_epi32(initval);
+ lens = _mm_set1_epi32(key_length);
+
+ while (len >= 12) {
+ const __m128i a1 = _mm_set_epi32(k32[3][i+0], k32[2][i+0],
+ k32[1][i+0], k32[0][i+0]);
+ const __m128i b1 = _mm_set_epi32(k32[3][i+1], k32[2][i+1],
+ k32[1][i+1], k32[0][i+1]);
+ const __m128i c1 = _mm_set_epi32(k32[3][i+2], k32[2][i+2],
+ k32[1][i+2], k32[0][i+2]);
+
+ a = _mm_add_epi32(a, a1);
+ b = _mm_add_epi32(b, b1);
+ c = _mm_add_epi32(c, c1);
+
+ __rte_jhash_mix4(a, b, c);
+
+ len -= 12, i += 3;
+ }
+
+ c = _mm_add_epi32(c, lens);
+
+ /* now switch based on remaining bits */
+
+ switch (len) {
+ case 1:
+ do {
+ const __m128i a1 = _mm_set_epi32((uint8_t)k32[3][i],
+ (uint8_t)k32[2][i],
+ (uint8_t)k32[1][i],
+ (uint8_t)k32[0][i]);
+ a = _mm_add_epi32(a, a1);
+ } while (0);
+ break;
+ case 2:
+ do {
+ const __m128i a1 = _mm_set_epi32((uint16_t)k32[3][i],
+ (uint16_t)k32[2][i],
+ (uint16_t)k32[1][i],
+ (uint16_t)k32[0][i]);
+ a = _mm_add_epi32(a, a1);
+ } while (0);
+ break;
+ case 3:
+ do {
+ const __m128i a1 = _mm_set_epi32(k32[3][i] & 0xFFFFFF,
+ k32[2][i] & 0xFFFFFF,
+ k32[1][i] & 0xFFFFFF,
+ k32[0][i] & 0xFFFFFF);
+ a = _mm_add_epi32(a, a1);
+ } while (0);
+ break;
+ case 4:
+ do {
+ const __m128i a1 = _mm_set_epi32(k32[3][i], k32[2][i],
+ k32[1][i], k32[0][i]);
+ a = _mm_add_epi32(a, a1);
+ } while (0);
+ break;
+ case 5:
+ do {
+ const __m128i a1 = _mm_set_epi32(k32[3][i], k32[2][i],
+ k32[1][i], k32[0][i]);
+ const __m128i b1 = _mm_set_epi32((uint8_t)k32[3][i+1],
+ (uint8_t)k32[2][i+1],
+ (uint8_t)k32[1][i+1],
+ (uint8_t)k32[0][i+1]);
+ a = _mm_add_epi32(a, a1);
+ b = _mm_add_epi32(b, b1);
+ } while (0);
+ break;
+ case 6:
+ do {
+ const __m128i a1 = _mm_set_epi32(k32[3][i], k32[2][i],
+ k32[1][i], k32[0][i]);
+ const __m128i b1 = _mm_set_epi32((uint16_t)k32[3][i+1],
+ (uint16_t)k32[2][i+1],
+ (uint16_t)k32[1][i+1],
+ (uint16_t)k32[0][i+1]);
+ a = _mm_add_epi32(a, a1);
+ b = _mm_add_epi32(b, b1);
+ } while (0);
+ break;
+ case 7:
+ do {
+ const __m128i a1 = _mm_set_epi32(k32[3][i], k32[2][i],
+ k32[1][i], k32[0][i]);
+ const __m128i b1 = _mm_set_epi32(k32[3][i+1] & 0xFFFFFF,
+ k32[2][i+1] & 0xFFFFFF,
+ k32[1][i+1] & 0xFFFFFF,
+ k32[0][i+1] & 0xFFFFFF);
+ a = _mm_add_epi32(a, a1);
+ b = _mm_add_epi32(b, b1);
+ } while (0);
+ break;
+ case 8:
+ do {
+ const __m128i a1 = _mm_set_epi32(k32[3][i], k32[2][i],
+ k32[1][i], k32[0][i]);
+ const __m128i b1 = _mm_set_epi32(k32[3][i+1], k32[2][i+1],
+ k32[1][i+1], k32[0][i+1]);
+ a = _mm_add_epi32(a, a1);
+ b = _mm_add_epi32(b, b1);
+ } while (0);
+ break;
+ case 9:
+ do {
+ const __m128i a1 = _mm_set_epi32(k32[3][i], k32[2][i],
+ k32[1][i], k32[0][i]);
+ const __m128i b1 = _mm_set_epi32(k32[3][i+1], k32[2][i+1],
+ k32[1][i+1], k32[0][i+1]);
+ const __m128i c1 = _mm_set_epi32((k32[3][i+2] & 0xFF) << 8,
+ (k32[2][i+2] & 0xFF) << 8,
+ (k32[1][i+2] & 0xFF) << 8,
+ (k32[0][i+2] & 0xFF) << 8);
+ a = _mm_add_epi32(a, a1);
+ b = _mm_add_epi32(b, b1);
+ c = _mm_add_epi32(c, c1);
+ } while (0);
+ break;
+ case 10:
+ do {
+ const __m128i a1 = _mm_set_epi32(k32[3][i], k32[2][i],
+ k32[1][i], k32[0][i]);
+ const __m128i b1 = _mm_set_epi32(k32[3][i+1], k32[2][i+1],
+ k32[1][i+1], k32[0][i+1]);
+ const __m128i c1 = _mm_set_epi32((k32[3][i+2] & 0xFFFF) << 8,
+ (k32[2][i+2] & 0xFFFF) << 8,
+ (k32[1][i+2] & 0xFFFF) << 8,
+ (k32[0][i+2] & 0xFFFF) << 8);
+ a = _mm_add_epi32(a, a1);
+ b = _mm_add_epi32(b, b1);
+ c = _mm_add_epi32(c, c1);
+ } while (0);
+ break;
+ case 11:
+ do {
+ const __m128i a1 = _mm_set_epi32(k32[3][i], k32[2][i],
+ k32[1][i], k32[0][i]);
+ const __m128i b1 = _mm_set_epi32(k32[3][i+1], k32[2][i+1],
+ k32[1][i+1], k32[0][i+1]);
+ const __m128i c1 = _mm_set_epi32((k32[3][i+2] & 0xFFFFFF) << 8,
+ (k32[2][i+2] & 0xFFFFFF) << 8,
+ (k32[1][i+2] & 0xFFFFFF) << 8,
+ (k32[0][i+2] & 0xFFFFFF) << 8);
+ a = _mm_add_epi32(a, a1);
+ b = _mm_add_epi32(b, b1);
+ c = _mm_add_epi32(c, c1);
+ } while (0);
+ break;
+ default:
+ break;
+ }
+
+ __rte_jhash_mix4(a, b, c);
+
+ _mm_storeu_si128((__m128i *)results, c);
+}
+
+static inline uint32_t
+rte_jhash_multi(const void *key[], uint32_t num_keys, uint32_t key_length,
+ uint32_t initval, uint32_t results[])
+{
+ uint32_t i;
+ for (i = 0; i < (num_keys & ~(BURST-1)); i += BURST)
+ _jhash_do_burst(&key[i], key_length, initval, &results[i]);
+
+ for (; i < num_keys; i++)
+ results[i] = rte_jhash(key[i], key_length, initval);
+ return 0;
+}
+
+static inline void
+_jhash2_do_burst(const uint32_t *k, const size_t buf_len,
+ const uint32_t key_len, const uint32_t initval, uint32_t results[])
+{
+ const uint32_t off0 = 0, off1 = buf_len,
+ off2 = buf_len * 2, off3 = buf_len * 3;
+ uint32_t len = key_len;
+ __m128i a, b, c;
+ __m128i lens;
+
+ a = b = _mm_set1_epi32(RTE_JHASH_GOLDEN_RATIO);
+ c = _mm_set1_epi32(initval);
+ lens = _mm_set1_epi32(key_len * sizeof(*k));
+
+ while (len >= 3) {
+ const __m128i a1 = _mm_set_epi32(k[off3], k[off2],
+ k[off1], k[off0]);
+ const __m128i b1 = _mm_set_epi32(k[off3+1], k[off2+1],
+ k[off1+1], k[off0+1]);
+ const __m128i c1 = _mm_set_epi32(k[off3+2], k[off2+2],
+ k[off1+2], k[off0+2]);
+
+ a = _mm_add_epi32(a, a1);
+ b = _mm_add_epi32(b, b1);
+ c = _mm_add_epi32(c, c1);
+
+ __rte_jhash_mix4(a, b, c);
+
+ len -= 3, k += 3;
+ }
+
+ c = _mm_add_epi32(c, lens);
+
+ switch (len) {
+ case 2: {
+ const __m128i b1 = _mm_set_epi32(k[off3+1], k[off2+1],
+ k[off1+1], k[off0+1]);
+ b = _mm_add_epi32(b, b1);
+ }
+ case 1: {
+ const __m128i a1 = _mm_set_epi32(k[off3], k[off2],
+ k[off1], k[off0]);
+ a = _mm_add_epi32(a, a1);
+ }
+ default:
+ break;
+ }
+
+ __rte_jhash_mix4(a, b, c);
+ _mm_storeu_si128((__m128i *)results, c);
+}
+
+static inline uint32_t
+rte_jhash2_multi(const uint32_t *key, size_t num_keys, size_t buf_len,
+ size_t key_len, uint32_t initval, uint32_t results[])
+{
+ uint32_t i;
+ for (i = 0; i < (num_keys & ~(BURST-1)); i += BURST)
+ _jhash2_do_burst(&key[i*buf_len], buf_len, key_len, initval,
+ &results[i]);
+ for (; i < num_keys; i++)
+ results[i] = rte_jhash2(&key[i*buf_len], key_len, initval);
+ return 0;
+}
+
+
+#undef BURST
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_VJHASH_H */
diff --git a/mk/rte.app.mk b/mk/rte.app.mk
index 34dff2a..dccd1e9 100644
--- a/mk/rte.app.mk
+++ b/mk/rte.app.mk
@@ -97,6 +97,10 @@ ifeq ($(CONFIG_RTE_LIBRTE_HASH),y)
LDLIBS += -lrte_hash
endif
+ifeq ($(CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH),y)
+LDLIBS += -lrte_tshash
+endif
+
ifeq ($(CONFIG_RTE_LIBRTE_LPM),y)
LDLIBS += -lrte_lpm
endif
--
1.7.7.6
^ permalink raw reply [flat|nested] 9+ messages in thread* [dpdk-dev] [PATCH 3/3] app/test: Added unit tests for Thread Safe Hash library
2014-09-18 10:34 [dpdk-dev] [PATCH 0/3] New Thread Safe Hash Library Pablo de Lara
2014-09-18 10:34 ` [dpdk-dev] [PATCH 1/3] eal: add const in prefetch functions Pablo de Lara
2014-09-18 10:34 ` [dpdk-dev] [PATCH 2/3] lib/librte_tshash: New Thread Safe Hash library for DPDK Pablo de Lara
@ 2014-09-18 10:34 ` Pablo de Lara
2014-09-18 12:21 ` [dpdk-dev] [PATCH 0/3] New Thread Safe Hash Library Neil Horman
2014-09-18 22:30 ` Stephen Hemminger
4 siblings, 0 replies; 9+ messages in thread
From: Pablo de Lara @ 2014-09-18 10:34 UTC (permalink / raw)
To: dev
Added 3 new unit tests:
- Functional unit test: Tests creation and handling of
a hash table with a single thread.
- Performance unit tests: Benchmark hash operations
add/delete/lookup, returning number of CPU cycles/operation.
- Multi thread unit tests: Checks there is no data corruption
due to multiple threads working on the same hash table.
Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
app/test/Makefile | 4 +
app/test/test_tshash_func.c | 1117 +++++++++++++++++++++++++++++++++++
app/test/test_tshash_multi_thread.c | 351 +++++++++++
app/test/test_tshash_perf.c | 631 ++++++++++++++++++++
4 files changed, 2103 insertions(+), 0 deletions(-)
create mode 100644 app/test/test_tshash_func.c
create mode 100644 app/test/test_tshash_multi_thread.c
create mode 100644 app/test/test_tshash_perf.c
diff --git a/app/test/Makefile b/app/test/Makefile
index 37a3772..71dd7c2 100644
--- a/app/test/Makefile
+++ b/app/test/Makefile
@@ -83,6 +83,10 @@ SRCS-y += test_memcpy_perf.c
SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash.c
SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_perf.c
+SRCS-$(CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH) += test_tshash_func.c
+SRCS-$(CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH) += test_tshash_perf.c
+SRCS-$(CONFIG_RTE_LIBRTE_THREAD_SAFE_HASH) += test_tshash_multi_thread.c
+
SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm6.c
diff --git a/app/test/test_tshash_func.c b/app/test/test_tshash_func.c
new file mode 100644
index 0000000..7ec2e12
--- /dev/null
+++ b/app/test/test_tshash_func.c
@@ -0,0 +1,1117 @@
+/*-
+ * BSD LICENSE
+ *
+ * Copyright(c) 2010-2014 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 <stdio.h>
+#include <stdint.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdarg.h>
+#include <errno.h>
+#include <sys/queue.h>
+
+#include <rte_common.h>
+#include <rte_malloc.h>
+#include <rte_cycles.h>
+#include <rte_random.h>
+#include <rte_memory.h>
+#include <rte_memzone.h>
+#include <rte_tailq.h>
+#include <rte_eal.h>
+#include <rte_ip.h>
+#include <rte_string_fns.h>
+#include <cmdline_parse.h>
+
+#include <rte_tshash.h>
+#include <rte_hash.h>
+#ifdef RTE_MACHINE_CPUFLAG_SSE4_2
+#include <rte_hash_crc.h>
+#endif
+#include <rte_jhash.h>
+
+#include "test.h"
+
+#define MAX_KEYS 1024
+#define NUM_KEYS 64
+
+#if defined RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+
+#ifdef RTE_MACHINE_CPUFLAG_SSE4_2
+static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
+static const char * const hash_func_strings[] = {"jhash", "crc"};
+#else
+static rte_hash_function hashtest_funcs[] = {rte_jhash};
+static const char * const hash_func_strings[] = {"jhash"};
+#endif
+
+
+/*
+ * Check condition and return an error if true.
+ */
+#define RETURN_IF_ERROR(cond, str, ...) do { \
+ if (cond) { \
+ printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
+ return -1; \
+ } \
+} while (0)
+
+/*
+ * Hash function that always returns the same value, to easily test what
+ * happens when a bucket is full.
+ */
+static uint32_t pseudo_hash(__attribute__((unused)) const void *keys,
+ __attribute__((unused)) uint32_t key_len,
+ __attribute__((unused)) uint32_t init_val)
+{
+ return 3;
+}
+
+static void *generate_key(uint8_t num_bytes)
+{
+ char *key = rte_zmalloc(NULL, num_bytes, 0);
+ unsigned i;
+
+ for (i = 0; i < num_bytes; i++)
+ key[i] = rand() % 255;
+
+ return (void *)key;
+}
+
+/* Parameters used for hash table in unit test functions. Name set later. */
+static struct rte_tshash_parameters {
+ char name[RTE_TSHASH_NAMESIZE];
+ unsigned max_entries;
+ unsigned key_len;
+ uint8_t socket_id;
+
+} ut_params;
+
+static uint8_t key_sizes[] = {16, 32, 48, 64, 96, 128};
+static struct rte_tshash *hash_tables[RTE_DIM(key_sizes)];
+static uint8_t burst_sizes[] = {13, 16, 32, 64};
+
+static struct rte_tshash_extra_args e_args = {
+ .malloc_mem = 0,
+ .max_load_factor = 0,
+ .rte_tshash_cmp_eq = NULL,
+ .hash_func = NULL
+
+};
+
+static int
+create_hash_tables(void)
+{
+ unsigned i;
+ for (i = 0; i < RTE_DIM(key_sizes); i++) {
+ hash_tables[i] = NULL;
+ sprintf(ut_params.name, "test_k%d", key_sizes[i]);
+ ut_params.max_entries = MAX_KEYS;
+ ut_params.key_len = key_sizes[i];
+ ut_params.socket_id = rte_socket_id();
+ hash_tables[i] = rte_tshash_find_existing(ut_params.name);
+ if (hash_tables[i] != NULL)
+ rte_tshash_reset(hash_tables[i]);
+ else
+ hash_tables[i] = rte_tshash_create(ut_params.name,
+ ut_params.max_entries, ut_params.key_len,
+ ut_params.socket_id, NULL);
+ RETURN_IF_ERROR(hash_tables[i] == NULL, "hash creation failed");
+ }
+ return 0;
+}
+/*
+ * Basic sequence of operations for a single key:
+ * - add
+ * - lookup (hit)
+ * - delete
+ * - lookup (miss)
+ */
+static int
+test_hash_add_lookup_delete(void)
+{
+ /* Test with standard add/lookup/delete functions */
+ unsigned i;
+ uint64_t hash_value, ret_data, data;
+ void *key;
+
+ for (i = 0; i < RTE_DIM(key_sizes); i++) {
+ key = generate_key(key_sizes[i]);
+ data = rte_rand();
+
+ if (0 != rte_tshash_add_key(hash_tables[i], key, data)) {
+ rte_free(key);
+ printf("Error: Failed to add key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 != rte_tshash_lookup(hash_tables[i], key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Failed to find key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+ if (ret_data != data) {
+ rte_free(key);
+ printf("Error: Data returned was not the one expected\n");
+ return -1;
+ }
+
+ if (0 != rte_tshash_del_key(hash_tables[i], key, NULL)) {
+ rte_free(key);
+ printf("Error: Failed to delete key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 == rte_tshash_lookup(hash_tables[i], key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Found key after deleting key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ rte_free(key);
+ rte_tshash_reset(hash_tables[i]);
+ }
+
+ /* Repeat test with precomputed hash values */
+ for (i = 0; i < RTE_DIM(key_sizes); i++) {
+ key = generate_key(key_sizes[i]);
+ hash_value = rte_rand() % MAX_KEYS;
+ data = rte_rand();
+
+ if (0 != rte_tshash_add_key_with_hash(hash_tables[i], hash_value, key, data)) {
+ rte_free(key);
+ printf("Error: Failed to add key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 != rte_tshash_lookup_with_hash(hash_tables[i], hash_value, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Failed to find key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+ if (ret_data != data) {
+ rte_free(key);
+ printf("Error: Data returned was not the one expected\n");
+ return -1;
+ }
+
+ if (0 != rte_tshash_del_key_with_hash(hash_tables[i], hash_value, key, NULL)) {
+ rte_free(key);
+ printf("Error: Failed to delete key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 == rte_tshash_lookup_with_hash(hash_tables[i], hash_value, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Found key after deleting key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ rte_free(key);
+ rte_tshash_reset(hash_tables[i]);
+ }
+
+ return 0;
+}
+
+/*
+ * Sequence of operations for a single key:
+ * - delete: miss
+ * - add
+ * - lookup: hit
+ * - add: miss
+ * - lookup: hit
+ * - delete: hit
+ * - delete: miss
+ * - lookup: miss
+ */
+static int
+test_hash_add_lookup_delete_miss(void)
+{
+ unsigned i;
+ uint64_t hash_value, ret_data, data;
+ void *key;
+
+ for (i = 0; i < RTE_DIM(key_sizes); i++) {
+ key = generate_key(key_sizes[i]);
+ hash_value = rte_rand() % MAX_KEYS;
+ data = rte_rand();
+
+ if (0 == rte_tshash_del_key_with_hash(hash_tables[i],
+ hash_value, key, NULL)) {
+ rte_free(key);
+ printf("Error: Deleted key of %d bytes that should not exist\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 != rte_tshash_add_key_with_hash(hash_tables[i],
+ hash_value, key, data)) {
+ rte_free(key);
+ printf("Error: Failed to add key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 != rte_tshash_lookup_with_hash(hash_tables[i],
+ hash_value, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Failed to lookup key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+ if (ret_data != data) {
+ rte_free(key);
+ printf("Error: Data returned was not the one expected\n");
+ return -1;
+ }
+
+ if (0 == rte_tshash_add_key_with_hash(hash_tables[i],
+ hash_value, key, data)) {
+ rte_free(key);
+ printf("Error: Added key of %d bytes that already existed\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 != rte_tshash_lookup_with_hash(hash_tables[i],
+ hash_value, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Failed to lookup key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+ if (ret_data != data) {
+ rte_free(key);
+ printf("Error: Data returned was not the one expected\n");
+ return -1;
+ }
+
+ if (0 != rte_tshash_del_key_with_hash(hash_tables[i],
+ hash_value, key, NULL)) {
+ rte_free(key);
+ printf("Error: Failed to delete key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 == rte_tshash_del_key_with_hash(hash_tables[i],
+ hash_value, key, NULL)) {
+ rte_free(key);
+ printf("Error: Deleted key of %d bytes that should not exist\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 == rte_tshash_lookup_with_hash(hash_tables[i],
+ hash_value, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Found key after deleting key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ rte_free(key);
+ rte_tshash_reset(hash_tables[i]);
+ }
+
+ return 0;
+}
+
+/*
+ * Sequence of operations for a single key:
+ * - add
+ * - lookup: hit
+ * - add: update
+ * - lookup: hit
+ * - delete: hit
+ * - lookup: miss
+ */
+static int
+test_hash_add_lookup_update_delete_miss(void)
+{
+ struct rte_tshash *hash_tables_update[RTE_DIM(key_sizes)];
+
+ ut_params.max_entries = MAX_KEYS;
+ ut_params.socket_id = 0;
+ e_args.malloc_mem = 0;
+ e_args.max_load_factor = 0.5;
+ e_args.rte_tshash_cmp_eq = NULL;
+ e_args.hash_func = NULL;
+ e_args.update_add = 1;
+
+ unsigned i;
+ uint64_t hash_value, ret_data, data;
+ void *key;
+
+ for (i = 0; i < RTE_DIM(key_sizes); i++) {
+ sprintf(ut_params.name, "test_k%d_update", key_sizes[i]);
+ ut_params.key_len = key_sizes[i];
+
+ hash_tables_update[i] = rte_tshash_find_existing(ut_params.name);
+ if (hash_tables_update[i] != NULL)
+ rte_tshash_reset(hash_tables_update[i]);
+ else
+ hash_tables_update[i] = rte_tshash_create(ut_params.name,
+ ut_params.max_entries,
+ ut_params.key_len,
+ ut_params.socket_id,
+ &e_args);
+ RETURN_IF_ERROR(hash_tables_update[i] == NULL, "hash creation failed");
+
+ key = generate_key(key_sizes[i]);
+ hash_value = rte_rand() % MAX_KEYS;
+ data = rte_rand();
+
+ if (0 != rte_tshash_add_key_with_hash(hash_tables_update[i],
+ hash_value, key, data)) {
+ rte_free(key);
+ printf("Error: Failed to add key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 != rte_tshash_lookup_with_hash(hash_tables_update[i],
+ hash_value, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Failed to lookup key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+ if (ret_data != data) {
+ rte_free(key);
+ printf("Error: Data returned was not the one expected\n");
+ return -1;
+ }
+
+ data = rte_rand() % MAX_KEYS;
+ if (0 != rte_tshash_add_key_with_hash(hash_tables_update[i],
+ hash_value, key, data)) {
+ rte_free(key);
+ printf("Error: Failed to update data of key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 != rte_tshash_lookup_with_hash(hash_tables_update[i], hash_value,
+ key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Failed to lookup key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+ if (ret_data != data) {
+ rte_free(key);
+ printf("Error: Data returned was not the one expected\n");
+ return -1;
+ }
+
+ if (0 != rte_tshash_del_key_with_hash(hash_tables_update[i], hash_value,
+ key, NULL)) {
+ rte_free(key);
+ printf("Error: Failed to delete key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ if (0 == rte_tshash_lookup_with_hash(hash_tables_update[i], hash_value,
+ key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Found key after deleting key of %d bytes\n", key_sizes[i]);
+ return -1;
+ }
+
+ rte_free(key);
+ rte_tshash_reset(hash_tables_update[i]);
+ }
+
+ return 0;
+}
+
+/*
+ * Sequence of operations for find existing hash table
+ *
+ * - find existing table: hit
+ * - find non-existing table: miss
+ *
+ */
+static int
+test_hash_find_existing(void)
+{
+ struct rte_tshash *result = NULL;
+ unsigned i;
+ char test_name[RTE_TSHASH_NAMESIZE];
+
+ for (i = 0; i < RTE_DIM(key_sizes); i++) {
+ /* Try to find existing hash table */
+ sprintf(test_name, "test_k%d", key_sizes[i]);
+ result = rte_tshash_find_existing(test_name);
+ RETURN_IF_ERROR(result != hash_tables[i], "could not find existing hash table");
+ }
+
+ /* Try to find non-existing hash table */
+ result = rte_tshash_find_existing("hash_find_non_existing");
+ RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
+
+ return 0;
+}
+
+/*
+ * Sequence of operations for 5 keys
+ * - add keys
+ * - lookup keys: hit
+ * - delete keys : hit
+ * - lookup keys: miss
+ */
+static int
+test_hash_burst(void)
+{
+ unsigned i, j, k;
+ void *keys[NUM_KEYS];
+ uint64_t data[NUM_KEYS];
+ uint64_t ret_data[NUM_KEYS];
+ uint64_t hash_values[NUM_KEYS];
+ uint64_t *hash_values_ptrs[NUM_KEYS];
+ uint64_t lookup_mask, hit_mask;
+ uint8_t hits;
+
+ for (i = 0; i < RTE_DIM(key_sizes); i++) {
+ for (j = 0; j < NUM_KEYS; j++) {
+ keys[j] = generate_key(key_sizes[i]);
+ data[j] = rte_rand();
+ if (0 != rte_tshash_add_key(hash_tables[i], keys[j], data[j])) {
+ printf("Error: Failed to add key of %d bytes\n", key_sizes[i]);
+ goto fail_burst;
+ }
+ }
+ for (j = 0; j < RTE_DIM(burst_sizes); j++) {
+ if (burst_sizes[j] == 64)
+ lookup_mask = 0xffffffffffffffff;
+ else
+ lookup_mask = (1llu << burst_sizes[j]) - 1;
+
+ hits = rte_tshash_lookup_bulk(hash_tables[i], lookup_mask,
+ (const void * const *)keys, ret_data,
+ &hit_mask);
+ if (hits != burst_sizes[j]) {
+ printf("Error: Failed to find %d key(s) of %d bytes\n",
+ burst_sizes[j] - hits, key_sizes[i]);
+ goto fail_burst;
+ }
+ for (k = 0; k < burst_sizes[j]; k++) {
+ if (unlikely(ret_data[j] != data[j])) {
+ printf("Error with value returned from lookup of key of %d bytes",
+ key_sizes[i]);
+ goto fail_burst;
+ }
+ }
+ }
+
+ for (j = 0; j < NUM_KEYS; j++) {
+ if (0 != rte_tshash_del_key(hash_tables[i], keys[j], NULL)) {
+ printf("Error: Failed to delete key of %d bytes\n", key_sizes[i]);
+ goto fail_burst;
+ }
+ }
+
+ lookup_mask = 0xffffffffffffffff;
+ hits = rte_tshash_lookup_bulk(hash_tables[i], lookup_mask,
+ (const void * const *)keys, ret_data,
+ &hit_mask);
+ if (0 != hits) {
+ printf("Error: Found %d key(s) of %d bytes that should not exist\n",
+ hits, key_sizes[i]);
+ goto fail_burst;
+ }
+
+ for (j = 0; j < NUM_KEYS; j++)
+ rte_free(keys[j]);
+ rte_tshash_reset(hash_tables[i]);
+ }
+
+ /* Repeat test with precomputed hash values */
+ for (i = 0; i < RTE_DIM(key_sizes); i++) {
+ for (j = 0; j < NUM_KEYS; j++) {
+ keys[j] = generate_key(key_sizes[i]);
+ hash_values[j] = rte_rand() % MAX_KEYS;
+ hash_values_ptrs[j] = &hash_values[j];
+ data[j] = rte_rand();
+ if (0 != rte_tshash_add_key_with_hash(hash_tables[i], hash_values[j],
+ keys[j], data[j])) {
+ printf("Error: Failed to add key of %d bytes\n", key_sizes[i]);
+ goto fail_burst;
+ }
+ }
+ for (j = 0; j < RTE_DIM(burst_sizes); j++) {
+ if (burst_sizes[j] == 64)
+ lookup_mask = 0xffffffffffffffff;
+ else
+ lookup_mask = (1llu << burst_sizes[j]) - 1;
+
+ hits = rte_tshash_lookup_bulk_with_hash(hash_tables[i], lookup_mask,
+ (uint64_t * const *)hash_values_ptrs,
+ (const void * const *)keys, ret_data,
+ &hit_mask);
+ if (hits != burst_sizes[j]) {
+ printf("Error: Failed to find %d key(s) of %d bytes\n",
+ burst_sizes[j] - hits, key_sizes[i]);
+ goto fail_burst;
+ }
+ for (k = 0; k < burst_sizes[j]; k++) {
+ if (unlikely(ret_data[j] != data[j])) {
+ printf("Error with value returned from lookup of key of %d bytes",
+ key_sizes[i]);
+ goto fail_burst;
+ }
+ }
+ }
+
+ for (j = 0; j < NUM_KEYS; j++) {
+ if (0 != rte_tshash_del_key_with_hash(hash_tables[i], hash_values[j],
+ keys[j], NULL)) {
+ printf("Error: Failed to delete key of %d bytes\n", key_sizes[i]);
+ goto fail_burst;
+ return -1;
+ }
+ }
+
+ lookup_mask = 0xffffffffffffffff;
+ hits = rte_tshash_lookup_bulk_with_hash(hash_tables[i], lookup_mask,
+ (uint64_t * const *)hash_values_ptrs,
+ (const void * const *)keys, ret_data,
+ &hit_mask);
+ if (0 != hits) {
+ printf("Error: Found %d key(s) of %d bytes that should not exist\n",
+ hits, key_sizes[i]);
+ goto fail_burst;
+ }
+
+ for (j = 0; j < NUM_KEYS; j++)
+ rte_free(keys[j]);
+ rte_tshash_reset(hash_tables[i]);
+ }
+
+ return 0;
+
+fail_burst:
+ for (j = 0; j < NUM_KEYS; j++)
+ rte_free(keys[j]);
+ return -1;
+}
+
+/*
+ * 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 in first level, 5th in second one
+ * - lookup the 5 keys: 4 hits in first level, 1 in second one
+ * - delete the 5 keys: 5 OK
+ * - lookup the 5 keys: 5 misses
+ */
+static int
+test_hash_full_bucket(void)
+{
+ struct rte_tshash *handle;
+ unsigned i;
+ void *keys[NUM_KEYS];
+ uint64_t data[NUM_KEYS];
+ uint64_t ret_data[NUM_KEYS];
+
+ ut_params.max_entries = MAX_KEYS;
+ ut_params.key_len = key_sizes[0];
+ ut_params.socket_id = 0;
+ sprintf(ut_params.name, "test_full_bucket");
+ e_args.max_load_factor = 0.5;
+ e_args.hash_func = pseudo_hash;
+
+ handle = rte_tshash_find_existing(ut_params.name);
+ if (handle != NULL)
+ rte_tshash_reset(handle);
+ else
+ handle = rte_tshash_create(ut_params.name, ut_params.max_entries,
+ ut_params.key_len, ut_params.socket_id, &e_args);
+ RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+
+
+ /* Fill bucket */
+ for (i = 0; i < RTE_TSHASH_BUCKET_SIZE; i++) {
+ keys[i] = generate_key(ut_params.key_len);
+ data[i] = rte_rand();
+
+ if (0 != rte_tshash_add_key(handle, keys[i], data[i])) {
+ printf("Error: Failed to add key of %d bytes\n", ut_params.key_len);
+ goto fail_burst;
+ }
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ const struct rte_tshash_stats *stats = rte_tshash_get_stats(handle);
+ if (stats->used_slots != (i+1) || stats->num_extra_buckets != 0) {
+ printf("Error: used_slots = %u, expected = %u; extra_buckets = %u"
+ " expected = 0 \n", stats->used_slots, i+1,
+ stats->num_extra_buckets);
+ goto fail_burst;
+ }
+#endif
+ }
+
+ /* This new entry should go to the next bucket */
+ keys[RTE_TSHASH_BUCKET_SIZE] = generate_key(ut_params.key_len);
+ data[RTE_TSHASH_BUCKET_SIZE] = rte_rand();
+
+ if (0 != rte_tshash_add_key(handle, keys[RTE_TSHASH_BUCKET_SIZE],
+ data[RTE_TSHASH_BUCKET_SIZE])) {
+ printf("Error: Failed to add key of %d bytes\n", ut_params.key_len);
+ goto fail_burst;
+ }
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ const struct rte_tshash_stats *stats = rte_tshash_get_stats(handle);
+ if (stats->used_slots != (RTE_TSHASH_BUCKET_SIZE+1)
+ || stats->num_extra_buckets != 1) {
+ printf("Error: used_slots = %u, expected = %u; extra_buckets = %u"
+ " expected = 1 \n", stats->used_slots, RTE_TSHASH_BUCKET_SIZE+1,
+ stats->num_extra_buckets);
+ goto fail_burst;
+ }
+#endif
+
+ /* Lookup */
+ for (i = 0; i < RTE_TSHASH_BUCKET_SIZE+1; i++) {
+ if (0 != rte_tshash_lookup(handle, keys[i], &ret_data[i])) {
+ printf("Error: Failed to find key of %d bytes\n", ut_params.key_len);
+ goto fail_burst;
+ }
+ if (ret_data[i] != data[i]) {
+ printf("Error: Data returned was not the one expected\n");
+ goto fail_burst;
+ }
+ }
+
+ /* Delete */
+ for (i = 0; i < RTE_TSHASH_BUCKET_SIZE+1; i++) {
+ if (0 != rte_tshash_del_key(handle, keys[i], NULL)) {
+ printf("Error: Failed to delete key of %d bytes\n", ut_params.key_len);
+ goto fail_burst;
+ }
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ const struct rte_tshash_stats *stats = rte_tshash_get_stats(handle);
+ if (stats->used_slots != (RTE_TSHASH_BUCKET_SIZE-i)
+ || stats->num_extra_buckets != 1) {
+ printf("Error: used_slots = %u, expected = %u; extra_buckets = %u"
+ " expected = 1 \n", stats->used_slots, RTE_TSHASH_BUCKET_SIZE-i,
+ stats->num_extra_buckets);
+ goto fail_burst;
+ }
+#endif
+ }
+
+ /* Lookup */
+ for (i = 0; i < RTE_TSHASH_BUCKET_SIZE; i++) {
+ if (0 == rte_tshash_lookup(handle, keys[i], &ret_data[i])) {
+ printf("Error: Found key after deleting key of %d bytes\n",
+ ut_params.key_len);
+ goto fail_burst;
+ }
+ }
+ for (i = 0; i < RTE_TSHASH_BUCKET_SIZE + 1; i++)
+ rte_free(keys[i]);
+
+ return 0;
+fail_burst:
+ for (i = 0; i < RTE_TSHASH_BUCKET_SIZE + 1; i++)
+ rte_free(keys[i]);
+ return -1;
+}
+
+
+/*
+ * Do tests for hash creation with bad parameters.
+ */
+static int
+test_hash_creation_with_bad_parameters(void)
+{
+ struct rte_tshash *handle;
+ ut_params.max_entries = MAX_KEYS;
+ ut_params.key_len = key_sizes[0];
+ ut_params.socket_id = 0;
+
+ handle = rte_tshash_create(NULL, ut_params.max_entries,
+ ut_params.key_len, ut_params.socket_id, NULL);
+
+ RETURN_IF_ERROR(handle != NULL,
+ "Impossible creating hash sucessfully without a name\n");
+
+ sprintf(ut_params.name, "creation_with_bad_parameters_0");
+ ut_params.max_entries = RTE_TSHASH_MIN_ENTRIES - 1;
+ handle = rte_tshash_create(ut_params.name, ut_params.max_entries,
+ ut_params.key_len, ut_params.socket_id, NULL);
+
+ RETURN_IF_ERROR(handle != NULL,
+ "Impossible creating hash sucessfully with maximum number of entries"
+ "less than minimum required\n");
+
+ sprintf(ut_params.name, "creation_with_bad_parameters_1");
+ ut_params.max_entries = MAX_KEYS;
+ e_args.max_load_factor = RTE_TSHASH_MAXIMUM_LOAD_FACTOR + 0.1;
+ e_args.malloc_mem = 0;
+ e_args.rte_tshash_cmp_eq = NULL;
+ e_args.hash_func = NULL;
+
+ handle = rte_tshash_create(ut_params.name, ut_params.max_entries,
+ ut_params.key_len, ut_params.socket_id, &e_args);
+
+ RETURN_IF_ERROR(handle != NULL,
+ "Impossible creating hash sucessfully with max_load_factor"
+ "in parameter exceeded\n");
+
+ sprintf(ut_params.name, "creation_with_bad_parameters_2");
+ e_args.max_load_factor = RTE_TSHASH_MAXIMUM_LOAD_FACTOR;
+ ut_params.key_len = 13;
+
+ handle = rte_tshash_create(ut_params.name, ut_params.max_entries,
+ ut_params.key_len, ut_params.socket_id, &e_args);
+
+ RETURN_IF_ERROR(handle != NULL,
+ "Impossible creating hash sucessfully wif key size is not multiple"
+ "of 16 and there is no user defined key compare function\n");
+
+ sprintf(ut_params.name, "creation_with_bad_parameters_3");
+ ut_params.key_len = 0;
+
+ handle = rte_tshash_create(ut_params.name, ut_params.max_entries,
+ ut_params.key_len, ut_params.socket_id, NULL);
+
+ RETURN_IF_ERROR(handle != NULL,
+ "Impossible creating hash sucessfully if key_len in parameter is zero\n");
+
+ sprintf(ut_params.name, "creation_with_bad_parameters_4");
+ ut_params.socket_id = RTE_MAX_NUMA_NODES;
+ ut_params.key_len = key_sizes[0];
+
+ handle = rte_tshash_create(ut_params.name, ut_params.max_entries,
+ ut_params.key_len, ut_params.socket_id, NULL);
+
+ RETURN_IF_ERROR(handle != NULL,
+ "Impossible creating hash sucessfully with invalid socket\n");
+
+ return 0;
+}
+
+/*
+ * Test the creation of a hash table with malloc function.
+ */
+static int
+test_hash_creation_with_malloc(void)
+{
+ struct rte_tshash *handle;
+
+ ut_params.max_entries = MAX_KEYS;
+ ut_params.key_len = key_sizes[0];
+ ut_params.socket_id = 0;
+ sprintf(ut_params.name, "test_malloc");
+ e_args.malloc_mem = 1;
+ e_args.max_load_factor = 0.5;
+ e_args.rte_tshash_cmp_eq = NULL;
+ e_args.hash_func = NULL;
+
+ handle = rte_tshash_find_existing(ut_params.name);
+ if (handle != NULL)
+ rte_tshash_reset(handle);
+ else
+ handle = rte_tshash_create(ut_params.name, ut_params.max_entries,
+ ut_params.key_len, ut_params.socket_id, &e_args);
+ RETURN_IF_ERROR(handle == NULL, "hash creation with malloc failed");
+
+ return 0;
+}
+
+static int
+generic_key_cmp(const void *key1, const void *key2, uint8_t key_size)
+{
+ return !memcmp(key1, key2, key_size);
+}
+
+/*
+ * Test add/lookup/delete functions with user-defined key compare function.
+ */
+static int
+test_hash_odd_key_size(void)
+{
+ struct rte_tshash *handle;
+ uint64_t hash_value, ret_data, data;
+ void *key;
+
+ ut_params.max_entries = MAX_KEYS;
+ ut_params.key_len = 26;
+ ut_params.socket_id = 0;
+ sprintf(ut_params.name, "test_odd_key_size");
+ e_args.max_load_factor = 0.5;
+ e_args.rte_tshash_cmp_eq = generic_key_cmp;
+
+ handle = rte_tshash_find_existing(ut_params.name);
+ if (handle != NULL)
+ rte_tshash_reset(handle);
+ else
+ handle = rte_tshash_create(ut_params.name, ut_params.max_entries,
+ ut_params.key_len, ut_params.socket_id,
+ &e_args);
+ RETURN_IF_ERROR(handle == NULL, "hash creation with malloc failed");
+
+ /* Test with standard add/lookup/delete functions */
+ key = generate_key(ut_params.key_len);
+ data = rte_rand();
+
+ if (0 != rte_tshash_add_key(handle, key, data)) {
+ rte_free(key);
+ printf("Error: Failed to add key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+
+ if (0 != rte_tshash_lookup(handle, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Failed to find key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+ if (ret_data != data) {
+ rte_free(key);
+ printf("Error: Data returned was not the one expected\n");
+ return -1;
+ }
+
+ if (0 != rte_tshash_del_key(handle, key, NULL)) {
+ rte_free(key);
+ printf("Error: Failed to delete key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+
+ if (0 == rte_tshash_lookup(handle, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Found key after deleting key of %d bytes\n",
+ ut_params.key_len);
+ return -1;
+ }
+
+ rte_free(key);
+ rte_tshash_reset(handle);
+
+ /* Repeat test with precomputed hash values */
+ key = generate_key(ut_params.key_len);
+ hash_value = rte_rand() % MAX_KEYS;
+ data = rte_rand();
+
+ if (0 != rte_tshash_add_key_with_hash(handle, hash_value, key, data)) {
+ rte_free(key);
+ printf("Error: Failed to add key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+
+ if (0 != rte_tshash_lookup_with_hash(handle, hash_value, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Failed to find key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+ if (ret_data != data) {
+ rte_free(key);
+ printf("Error: Data returned was not the one expected\n");
+ return -1;
+ }
+
+ if (0 != rte_tshash_del_key_with_hash(handle, hash_value, key, NULL)) {
+ rte_free(key);
+ printf("Error: Failed to delete key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+
+ if (0 == rte_tshash_lookup_with_hash(handle, hash_value, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Found key after deleting key of %d bytes\n",
+ ut_params.key_len);
+ return -1;
+ }
+
+ rte_free(key);
+ rte_tshash_reset(handle);
+
+ return 0;
+}
+
+/*
+ * Test add/lookup/delete functions with different hash functions (jhash and crc).
+ */
+static int
+test_hash_different_hash_functions(void)
+{
+ unsigned i;
+ struct rte_tshash *handle;
+ uint64_t hash_value, ret_data, data;
+ void *key;
+
+ for (i = 0; i < RTE_DIM(hashtest_funcs); i++) {
+ ut_params.max_entries = MAX_KEYS;
+ ut_params.key_len = key_sizes[0];
+ ut_params.socket_id = 0;
+ sprintf(ut_params.name, "test_tshash_%s", hash_func_strings[i]);
+ e_args.max_load_factor = 0.5;
+ e_args.rte_tshash_cmp_eq = NULL;
+ e_args.malloc_mem = 0;
+ e_args.hash_func = hashtest_funcs[i];
+
+ handle = rte_tshash_find_existing(ut_params.name);
+ if (handle != NULL)
+ rte_tshash_reset(handle);
+ else
+ handle = rte_tshash_create(ut_params.name, ut_params.max_entries,
+ ut_params.key_len, ut_params.socket_id,
+ &e_args);
+ RETURN_IF_ERROR(handle == NULL, "hash creation with %s hash function failed",
+ hash_func_strings[i]);
+
+ /* Test with standard add/lookup/delete functions */
+ key = generate_key(ut_params.key_len);
+ data = rte_rand();
+
+ if (0 != rte_tshash_add_key(handle, key, data)) {
+ rte_free(key);
+ printf("Error: Failed to add key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+
+ if (0 != rte_tshash_lookup(handle, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Failed to find key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+ if (ret_data != data) {
+ rte_free(key);
+ printf("Error: Data returned was not the one expected\n");
+ return -1;
+ }
+
+ if (0 != rte_tshash_del_key(handle, key, NULL)) {
+ rte_free(key);
+ printf("Error: Failed to delete key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+
+ if (0 == rte_tshash_lookup(handle, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Found key after deleting key of %d bytes\n",
+ ut_params.key_len);
+ return -1;
+ }
+
+ rte_free(key);
+ rte_tshash_reset(handle);
+
+ /* Repeat test with precomputed hash values */
+ key = generate_key(ut_params.key_len);
+ hash_value = rte_rand() % MAX_KEYS;
+ data = rte_rand();
+
+ if (0 != rte_tshash_add_key_with_hash(handle, hash_value, key, data)) {
+ rte_free(key);
+ printf("Error: Failed to add key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+
+ if (0 != rte_tshash_lookup_with_hash(handle, hash_value, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Failed to find key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+ if (ret_data != data) {
+ rte_free(key);
+ printf("Error: Data returned was not the one expected\n");
+ return -1;
+ }
+
+ if (0 != rte_tshash_del_key_with_hash(handle, hash_value, key, NULL)) {
+ rte_free(key);
+ printf("Error: Failed to delete key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+
+ if (0 == rte_tshash_lookup_with_hash(handle, hash_value, key, &ret_data)) {
+ rte_free(key);
+ printf("Error: Found key after deleting key of %d bytes\n", ut_params.key_len);
+ return -1;
+ }
+
+ rte_free(key);
+ rte_tshash_reset(handle);
+ }
+
+ return 0;
+}
+
+/*
+ * Do all unit tests.
+ */
+static int
+test_tshash(void)
+{
+ printf("\n-- Test 0: Creating hash tables --\n");
+ if (create_hash_tables() < 0)
+ return -1;
+ printf("\n-- Test1: add, lookup, delete --\n");
+ if (test_hash_add_lookup_delete() < 0)
+ return -1;
+ printf("\n-- Test2: find existing hash table --\n");
+ if (test_hash_find_existing() < 0)
+ return -1;
+ printf("\n-- Test3: add, lookup, delete misses --\n");
+ if (test_hash_add_lookup_delete_miss() < 0)
+ return -1;
+ printf("\n-- Test4: add, lookup, update, delete misses --\n");
+ if (test_hash_add_lookup_update_delete_miss() < 0)
+ return -1;
+ printf("\n-- Test5: lookup bulk --\n");
+ if (test_hash_burst() < 0)
+ return -1;
+ printf("\n-- Test6: full bucket --\n");
+ if (test_hash_full_bucket() < 0)
+ return -1;
+ printf("\n-- Test7: create hash table with bad parameters --\n");
+ if (test_hash_creation_with_bad_parameters() < 0)
+ return -1;
+ printf("\n-- Test8: create hash table with malloc --\n");
+ if (test_hash_creation_with_malloc() < 0)
+ return -1;
+ printf("\n-- Test9: add, lookup, delete with odd key size (not multiple of 16 --\n");
+ if (test_hash_odd_key_size() < 0)
+ return -1;
+ printf("\n-- Test10: use different hash functions (jhash and CRC) --\n");
+ if (test_hash_different_hash_functions() < 0)
+ return -1;
+
+ return 0;
+}
+#else /* RTE_LIBRTE_THREAD_SAFE_HASH_STATS */
+
+static int
+test_tshash(void)
+{
+ printf("The Thread Safe Hash library stats are not included in this build\n");
+ return 0;
+}
+
+#endif /* RTE_LIBRTE_THREAD_SAFE_HASH_STATS */
+
+static struct test_command tshash_cmd = {
+ .command = "thread_safe_hash_autotest",
+ .callback = test_tshash,
+};
+REGISTER_TEST_COMMAND(tshash_cmd);
+
diff --git a/app/test/test_tshash_multi_thread.c b/app/test/test_tshash_multi_thread.c
new file mode 100644
index 0000000..eacc5d5
--- /dev/null
+++ b/app/test/test_tshash_multi_thread.c
@@ -0,0 +1,351 @@
+/*-
+ * BSD LICENSE
+ *
+ * Copyright(c) 2010-2014 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 <stdio.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <unistd.h>
+#include <sys/queue.h>
+
+#include <cmdline_parse.h>
+
+#include <rte_common.h>
+#include <rte_memory.h>
+#include <rte_memzone.h>
+#include <rte_per_lcore.h>
+#include <rte_launch.h>
+#include <rte_atomic.h>
+#include <rte_tailq.h>
+#include <rte_eal.h>
+#include <rte_per_lcore.h>
+#include <rte_lcore.h>
+#include <rte_cycles.h>
+#include <rte_random.h>
+#include <rte_tshash.h>
+
+#include "test.h"
+
+#define TOTAL_ADDITIONS 300000
+
+#define MAX_KEYS 65536
+#define KEYSIZE 16
+#define MULTIPLIER 13
+
+/* Parameters used for hash table in unit test functions. Name set later. */
+static struct hash_parameters {
+ char name[RTE_TSHASH_NAMESIZE];
+ unsigned max_entries;
+ unsigned key_len;
+ uint8_t socket_id;
+} ut_params;
+
+static struct ops_stats {
+ unsigned retries_add;
+ unsigned not_enough_mem_add;
+ unsigned already_exist_add;
+ unsigned no_free_slots_add;
+ unsigned success_add;
+
+ unsigned retries_lookup;
+ unsigned errors_lookup;
+ unsigned misses_lookup;
+ unsigned success_lookup;
+
+ unsigned num_additions;
+ unsigned num_deletions;
+ unsigned num_lookups;
+} stats;
+
+static struct rte_tshash *hash_table;
+
+union hash_key {
+ uint64_t hashval;
+ char key[KEYSIZE];
+};
+
+unsigned num_sec_threads;
+unsigned finished_additions;
+
+#define RETURN_IF_ERROR(cond, str, ...) do { \
+ if (cond) { \
+ printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
+ return -1; \
+ } \
+} while (0)
+
+static int
+create_hash_table(void)
+{
+ unsigned i;
+ hash_table = NULL;
+ sprintf(ut_params.name, "test_k%d_multi_thread", KEYSIZE);
+ ut_params.max_entries = MAX_KEYS;
+ ut_params.key_len = KEYSIZE;
+ ut_params.socket_id = rte_socket_id();
+
+ hash_table = rte_tshash_find_existing(ut_params.name);
+ if (hash_table != NULL)
+ rte_tshash_reset(hash_table);
+ else
+ hash_table = rte_tshash_create(ut_params.name,
+ ut_params.max_entries, ut_params.key_len,
+ ut_params.socket_id, NULL);
+ RETURN_IF_ERROR(hash_table == NULL, "hash creation failed");
+
+ for (i = 0; i < MAX_KEYS; i++) {
+ union hash_key k = { .key = {0} };
+ k.hashval = i;
+ RETURN_IF_ERROR(rte_tshash_add_key_with_hash(hash_table,
+ k.hashval, (void *)k.key, k.hashval * MULTIPLIER) != 0,
+ "Error adding entry number %u\n", i);
+ }
+
+ return 0;
+}
+
+static int
+test_add_single(__attribute__((unused)) void *arg)
+{
+ printf("Core %u is performing additions\n", rte_lcore_id());
+ while (stats.num_additions < TOTAL_ADDITIONS) {
+ union hash_key k = { .key = {0} };
+ k.hashval = MAX_KEYS/2-1 + (rte_rand() % 2) * MAX_KEYS/2;
+ if (0 == rte_tshash_add_key_with_hash(hash_table, k.hashval,
+ (void *)k.key,
+ k.hashval * MULTIPLIER))
+ stats.num_additions++;
+ }
+
+ printf("Core %u has finished performing additions\n", rte_lcore_id());
+ finished_additions = 1;
+ return 0;
+}
+
+static int
+test_add_multi(__attribute__((unused)) void *arg)
+{
+ int ret;
+ unsigned i;
+
+ printf("Core %u is performing additions\n", rte_lcore_id());
+
+ for (i = 0; i < MAX_KEYS; i++) {
+ union hash_key k = { .key = {0} };
+ k.hashval = MAX_KEYS/2-1 + rte_rand() * MAX_KEYS/2;
+
+ ret = rte_tshash_add_key_with_hash(hash_table, k.hashval,
+ (void *)k.key, k.hashval * MULTIPLIER);
+
+ switch (ret) {
+ case -EEXIST:
+ __sync_fetch_and_add(&stats.already_exist_add, 1);
+ break;
+ case -EAGAIN:
+ __sync_fetch_and_add(&stats.retries_add, 1);
+ break;
+ case -ENOMEM:
+ __sync_fetch_and_add(&stats.not_enough_mem_add, 1);
+ break;
+ case -ENOSPC:
+ __sync_fetch_and_add(&stats.no_free_slots_add, 1);
+ break;
+ default:
+ __sync_fetch_and_add(&stats.success_add, 1);
+ __sync_fetch_and_add(&stats.num_additions, 1);
+ }
+ }
+ return 0;
+}
+
+static int
+test_lookup(__attribute__((unused)) void *arg)
+{
+ int ret;
+
+ printf("Core %u is performing lookups\n", rte_lcore_id());
+ while (finished_additions == 0) {
+ union hash_key k = { .key = {0} };
+ uintptr_t retval = 0;
+ k.hashval = MAX_KEYS-1;
+
+ ret = rte_tshash_lookup_with_hash(hash_table, k.hashval,
+ (void *)k.key, &retval);
+ __sync_fetch_and_add(&stats.num_lookups, 1);
+ switch (ret) {
+ /* Miss */
+ case -1:
+ __sync_fetch_and_add(&stats.misses_lookup, 1);
+ break;
+ /* Out of sync */
+ case -EAGAIN:
+ __sync_fetch_and_add(&stats.retries_lookup, 1);
+ break;
+ /* Hit */
+ default:
+ /* Corrupted data */
+ if (retval != k.hashval * MULTIPLIER) {
+ __sync_fetch_and_add(&stats.errors_lookup, 1);
+ printf("Data corrupted!\n!");
+ printf("Expected %"PRIx64" but got %"PRIx64"\n", k.hashval * MULTIPLIER, retval);
+ } else
+ __sync_fetch_and_add(&stats.success_lookup, 1);
+ }
+ }
+ printf("Core %u has finished performing lookups\n", rte_lcore_id());
+
+ return 0;
+}
+
+static int
+test_delete(__attribute__((unused)) void *arg)
+{
+ printf("Core %u is performing deletions\n", rte_lcore_id());
+ while (finished_additions == 0) {
+ union hash_key k = { .key = {0} };
+ k.hashval = MAX_KEYS/2-1 + (rte_rand() % 2) * MAX_KEYS/2;
+ rte_tshash_del_key_with_hash(hash_table, k.hashval, (void *)k.key, NULL);
+ }
+ printf("Core %u has finished performing deletions\n", rte_lcore_id());
+
+ return 0;
+}
+
+/* 1 thread adding entries, 1 thread deleting entries and rest looking up */
+static int
+test_multi_lookup(void) {
+ unsigned i, j;
+
+ do {
+ j = 0;
+ finished_additions = 0;
+ /* Reset operation stats */
+ memset(&stats, 0, sizeof(struct ops_stats));
+
+ RTE_LCORE_FOREACH_SLAVE(i) {
+ switch (j++) {
+ case 0:
+ rte_eal_remote_launch(test_add_single, NULL, i);
+ break;
+ case 1:
+ rte_eal_remote_launch(test_delete, NULL, i);
+ break;
+ default:
+ rte_eal_remote_launch(test_lookup, NULL, i);
+ }
+ }
+ rte_eal_mp_wait_lcore();
+ }
+ /* There must be at least one attempt of collision (very likely) */
+ while (stats.retries_lookup == 0);
+
+ printf("Retries on lookup op: %u/%u (%.7f%%)\n", stats.retries_lookup,
+ stats.num_lookups, ((double)stats.retries_lookup / stats.num_lookups * 100));
+ printf("Errors on lookup op: %u/%u (%.7f%%)\n", stats.errors_lookup,
+ stats.num_lookups, ((double)stats.errors_lookup / stats.num_lookups * 100));
+ printf("Misses on lookup op: %u/%u (%.7f%%)\n\n", stats.misses_lookup,
+ stats.num_lookups, ((double)stats.misses_lookup / stats.num_lookups * 100));
+ printf("Successes on lookup op: %u/%u (%.7f%%)\n\n", stats.success_lookup,
+ stats.num_lookups, ((double)stats.success_lookup / stats.num_lookups * 100));
+
+ RETURN_IF_ERROR(stats.errors_lookup != 0,
+ "There was at least one error while looking up");
+ return 0;
+
+}
+
+/* All threads (minimum 2) adding entries */
+static int
+test_multi_add(void) {
+ unsigned i;
+
+ do {
+ /* Reset operation stats */
+ rte_tshash_reset(hash_table);
+ memset(&stats, 0, sizeof(struct ops_stats));
+
+ RTE_LCORE_FOREACH_SLAVE(i) {
+ rte_eal_remote_launch(test_add_multi, NULL, i);
+ }
+ rte_eal_mp_wait_lcore();
+ }
+ /* There must be at least one attempt of collision (very likely) */
+ while (stats.retries_add == 0);
+
+ printf("\nRetries on add op: %u/%u (%.7f%%)\n", stats.retries_add,
+ (MAX_KEYS * num_sec_threads),
+ ((double)stats.retries_add / (MAX_KEYS * num_sec_threads) * 100));
+ printf("OOM on add op: %u/%u (%.7f%%)\n", stats.not_enough_mem_add,
+ (MAX_KEYS * num_sec_threads),
+ ((double)stats.not_enough_mem_add / (MAX_KEYS * num_sec_threads) * 100));
+ printf("Already existed on add op: %u/%u (%.7f%%)\n", stats.already_exist_add,
+ (MAX_KEYS * num_sec_threads),
+ ((double)stats.already_exist_add / (MAX_KEYS * num_sec_threads) * 100));
+ printf("No free slots on add op: %u/%u (%.7f%%)\n\n", stats.no_free_slots_add,
+ (MAX_KEYS * num_sec_threads),
+ ((double)stats.no_free_slots_add / (MAX_KEYS * num_sec_threads) * 100));
+ printf("Successes on add op: %u/%u (%.7f%%)\n\n", stats.success_add,
+ (MAX_KEYS * num_sec_threads),
+ ((double)stats.success_add / (MAX_KEYS * num_sec_threads) * 100));
+
+ return 0;
+}
+
+
+static int
+test_tshash_multi_thread(void)
+{
+
+ /* Master + 3 cores are needed (for add/lookup/delete) at least */
+ if (rte_lcore_count() < 4) {
+ printf("At least 4 cores are needed\n");
+ return -1;
+ }
+ num_sec_threads = rte_lcore_count() - 1;
+
+ if (create_hash_table() < 0)
+ return -1;
+
+ if (test_multi_lookup() < 0)
+ return -1;
+
+ if (test_multi_add() < 0)
+ return -1;
+
+ return 0;
+}
+
+static struct test_command tshash_multi_thread_cmd = {
+ .command = "thread_safe_hash_multi_thread_autotest",
+ .callback = test_tshash_multi_thread,
+};
+REGISTER_TEST_COMMAND(tshash_multi_thread_cmd);
diff --git a/app/test/test_tshash_perf.c b/app/test/test_tshash_perf.c
new file mode 100644
index 0000000..79235c1
--- /dev/null
+++ b/app/test/test_tshash_perf.c
@@ -0,0 +1,631 @@
+/*-
+ * BSD LICENSE
+ *
+ * Copyright(c) 2010-2014 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 <stdio.h>
+#include <inttypes.h>
+#include <rte_cycles.h>
+#include <rte_tshash.h>
+#include <rte_random.h>
+#include <rte_string_fns.h>
+#include "test.h"
+
+#define MAX_KEYS (1<<21)
+#define MULTIPLIER 13
+#define MAX_KEYSIZE 128
+#define NUM_KEYSIZES 6
+#define NUM_OPERATIONS 8
+
+#define NUM_LOOKUPS (1<<24)
+#define BURST_SIZE 64
+
+union hash_key {
+ uint64_t hashval;
+ char key[MAX_KEYSIZE];
+};
+
+unsigned key_sizes[] = {16, 32, 48, 64, 96, 128};
+struct rte_tshash *h[NUM_KEYSIZES];
+uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2];
+
+/*
+ * Set up the table so every flow fits in first level bucket
+ */
+static int
+setup_table(unsigned with_hash, unsigned table_index)
+{
+ unsigned i;
+ char name[RTE_TSHASH_NAMESIZE];
+ sprintf(name, "test_phash%d", key_sizes[table_index]);
+
+ h[table_index] = rte_tshash_find_existing(name);
+ if (h[table_index] == NULL) {
+ h[table_index] = rte_tshash_create(name, MAX_KEYS,
+ key_sizes[table_index],
+ rte_socket_id(), NULL);
+ if (h[table_index] == NULL) {
+ printf("Error creating table\n");
+ return -1;
+ } else {
+ }
+ } else
+ rte_tshash_reset(h[table_index]);
+
+ const uint64_t start_tsc = rte_rdtsc();
+
+ for (i = 0; i < MAX_KEYS; i++) {
+ union hash_key k = { .key = {0} };
+ k.hashval = i;
+ if (with_hash) {
+ if (rte_tshash_add_key_with_hash(h[table_index], k.hashval,
+ (const void *)k.key,
+ k.hashval * MULTIPLIER) != 0) {
+ printf("Error adding entry number %u\n", i);
+ return -1;
+ } else
+ continue;
+ } else {
+ if (rte_tshash_add_key(h[table_index], (const void *)k.key,
+ k.hashval * MULTIPLIER != 0)) {
+ printf("Error adding entry number %u\n", i);
+ return -1;
+ }
+ }
+ }
+
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+ cycles[table_index][0][with_hash] = time_taken/MAX_KEYS;
+
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ const struct rte_tshash_stats *stats = rte_tshash_get_stats(h[table_index]);
+ printf("used_slots = %u, extra_buckets = %u\n", stats->used_slots,
+ stats->num_extra_buckets);
+#endif
+
+ printf("\n%"PRIu64" adds in %f seconds\n", (uint64_t)MAX_KEYS,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per add\n",
+ cycles[table_index][0][with_hash]);
+ printf("Average %"PRIu64" adds per second\n", (MAX_KEYS * rte_get_tsc_hz())/time_taken);
+
+
+ return 0;
+}
+
+/*
+ * Set up table so half flows are in second level buckets
+ */
+static int
+setup_table_extd(unsigned with_hash, unsigned table_index)
+{
+ unsigned i, j;
+ char name[RTE_TSHASH_NAMESIZE];
+ sprintf(name, "test_phash%d", key_sizes[table_index]);
+
+ h[table_index] = rte_tshash_find_existing(name);
+ if (h[table_index] == NULL) {
+ h[table_index] = rte_tshash_create(name, MAX_KEYS,
+ key_sizes[table_index], rte_socket_id(), NULL);
+ if (h[table_index] == NULL) {
+ printf("Error creating table\n");
+ return -1;
+ } else {
+ }
+ } else
+ rte_tshash_reset(h[table_index]);
+
+ const uint64_t start_tsc = rte_rdtsc();
+ if (with_hash) {
+ for (i = 0; i < MAX_KEYS/8; i++) {
+ for (j = 0; j < 8; j++) {
+ union hash_key k = { .key = {0} };
+ k.hashval = i;
+ k.hashval |= (1lu<<(56+j));
+ k.key[key_sizes[table_index]-1] = j;
+ if (rte_tshash_add_key_with_hash(h[table_index], k.hashval,
+ (const void *)k.key,
+ k.hashval * MULTIPLIER) != 0) {
+ printf("Error adding entry number %u\n", i*7+j);
+ return -1;
+ }
+ }
+ }
+ } else {
+ for (i = 0; i < MAX_KEYS/8; i++) {
+ for (j = 0; j < 8; j++) {
+ union hash_key k = { .key = {0} };
+ k.hashval = i;
+ k.hashval |= (1lu<<(56+j));
+ k.key[key_sizes[table_index]-1] = j;
+ if (rte_tshash_add_key(h[table_index], (const void *)k.key,
+ k.hashval * MULTIPLIER) != 0) {
+ printf("Error adding entry number %u\n", i*7+j);
+ return -1;
+ }
+ }
+ }
+ }
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+ cycles[table_index][1][with_hash] = time_taken/MAX_KEYS;
+
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ const struct rte_tshash_stats *stats = rte_tshash_get_stats(h[table_index]);
+ printf("used_slots = %u, extra_buckets = %u\n", stats->used_slots,
+ stats->num_extra_buckets);
+#endif
+
+ printf("\n%"PRIu64" adds in %f seconds\n", (uint64_t) MAX_KEYS,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per add\n",
+ cycles[table_index][1][with_hash]);
+ printf("Average %"PRIu64" adds per second\n",
+ (MAX_KEYS * rte_get_tsc_hz())/time_taken);
+
+ return 0;
+}
+
+
+static int
+timed_lookups(unsigned with_hash, unsigned table_index)
+{
+ uint64_t i;
+ uintptr_t retval;
+ const uint64_t start_tsc = rte_rdtsc();
+
+ for (i = 0; i < NUM_LOOKUPS; i++) {
+ union hash_key k = { .key = {0} };
+
+ k.hashval = rte_rand() % MAX_KEYS;
+ if (with_hash) {
+ if (rte_tshash_lookup_with_hash(h[table_index], k.hashval,
+ (const void *)k.key, &retval) < 0) {
+ printf("Error lookup up hash key %"PRIu64"\n", k.hashval);
+ return -1;
+ } else
+ continue;
+ } else {
+ if (rte_tshash_lookup(h[table_index],
+ (const void *)k.key, &retval) < 0) {
+ printf("Error lookup up hash key %"PRIu64"\n", k.hashval);
+ return -1;
+ }
+ }
+ }
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+ cycles[table_index][2][with_hash] = time_taken/NUM_LOOKUPS;
+
+ printf("%"PRIu64" lookups in %f seconds\n", (uint64_t) NUM_LOOKUPS,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per lookup\n",
+ cycles[table_index][2][with_hash]);
+ printf("Average %"PRIu64" lookups per second\n",
+ (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken);
+ return 0;
+}
+
+static int
+timed_lookups_extd(unsigned with_hash, unsigned table_index)
+{
+ uint64_t i;
+ uintptr_t retval;
+ const uint64_t start_tsc = rte_rdtsc();
+ for (i = 0; i < NUM_LOOKUPS; i++) {
+ union hash_key k = { .key = {0} };
+ unsigned tmp = rte_rand() % 8;
+ k.hashval = rte_rand() % MAX_KEYS/8;
+ k.hashval |= (1llu << (tmp+56));
+ k.key[key_sizes[table_index]-1] = tmp;
+ if (with_hash) {
+ if (rte_tshash_lookup_with_hash(h[table_index], k.hashval,
+ (const void *)k.key, &retval) < 0) {
+ printf("Error lookup up hash key %"PRIu64"\n", k.hashval);
+ return -1;
+ } else
+ continue;
+ } else {
+ if (rte_tshash_lookup(h[table_index], (const void *)k.key,
+ &retval) < 0) {
+ printf("Error lookup up hash key %"PRIu64"\n", k.hashval);
+ return -1;
+ }
+ }
+ }
+
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+ cycles[table_index][3][with_hash] = time_taken/NUM_LOOKUPS;
+
+ printf("%"PRIu64" lookups in %f seconds\n", (uint64_t)NUM_LOOKUPS,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per lookup\n",
+ cycles[table_index][3][with_hash]);
+ printf("Average %"PRIu64" lookups per second\n",
+ (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken);
+ return 0;
+}
+
+static int
+timed_lookups_multi(unsigned with_hash, unsigned table_index)
+{
+ uint64_t i;
+#if BURST_SIZE == 64
+ const uint64_t lookup_mask = 0xffffffffffffffff;
+#else
+ const uint64_t lookup_mask = (1llu << BURST_SIZE) - 1;
+#endif
+ union hash_key ks[BURST_SIZE] = { { .key = {0} } };
+ const void *keys[BURST_SIZE];
+ uint64_t *h_ptrs[BURST_SIZE];
+
+ for (i = 0; i < BURST_SIZE; i++) {
+ keys[i] = (void *)ks[i].key;
+ h_ptrs[i] = &ks[i].hashval;
+ }
+
+ const uint64_t start_tsc = rte_rdtsc();
+ for (i = 0; i < NUM_LOOKUPS/BURST_SIZE; i++) {
+ unsigned j;
+ uint64_t hashes[BURST_SIZE];
+ uintptr_t retvals[BURST_SIZE];
+ int hitcount;
+ uint64_t hitmask;
+
+ for (j = 0; j < BURST_SIZE; j++) {
+ hashes[j] = rte_rand() % MAX_KEYS;
+ ks[j].hashval = hashes[j];
+ }
+ if (with_hash) {
+ hitcount = rte_tshash_lookup_bulk_with_hash(h[table_index], lookup_mask,
+ h_ptrs, keys, retvals,
+ &hitmask);
+ if (unlikely(hitcount != BURST_SIZE)) {
+ printf("Error lookup up hash keys. Expected retval = %u, got "
+ "%d\n", BURST_SIZE, hitcount);
+ printf("Hit mask = %"PRIx64"\n", hitmask);
+ return -1;
+ } else
+ continue;
+ } else {
+ hitcount = rte_tshash_lookup_bulk(h[table_index], lookup_mask,
+ keys, retvals, &hitmask);
+ if (unlikely(hitcount != BURST_SIZE)) {
+ printf("Error lookup up hash keys. Expected retval = %u, got "
+ "%d\n", BURST_SIZE, hitcount);
+ printf("Hit mask = %"PRIx64"\n", hitmask);
+ return -1;
+ }
+ }
+ }
+
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+ cycles[table_index][4][with_hash] = time_taken/NUM_LOOKUPS;
+
+ printf("%"PRIu64" lookups in %f seconds\n", (uint64_t)NUM_LOOKUPS,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per lookup\n",
+ cycles[table_index][4][with_hash]);
+ printf("Average %"PRIu64" lookups per second\n",
+ (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken);
+ return 0;
+}
+
+static int
+timed_lookups_multi_extd(unsigned with_hash, unsigned table_index)
+{
+ uint64_t i;
+#if BURST_SIZE == 64
+ const uint64_t lookup_mask = 0xffffffffffffffff;
+#else
+ const uint64_t lookup_mask = (1llu << BURST_SIZE) - 1;
+#endif
+ union hash_key ks[BURST_SIZE] = { { .key = {0} } };
+ const void *keys[BURST_SIZE];
+ uint64_t *h_ptrs[BURST_SIZE];
+
+ for (i = 0; i < BURST_SIZE; i++) {
+ keys[i] = (void *)ks[i].key;
+ h_ptrs[i] = &ks[i].hashval;
+ }
+
+ const uint64_t start_tsc = rte_rdtsc();
+ for (i = 0; i < NUM_LOOKUPS/BURST_SIZE; i++) {
+ unsigned j;
+ uint64_t hashes[BURST_SIZE];
+ uintptr_t retvals[BURST_SIZE];
+ int hitcount;
+ uint64_t hitmask;
+
+ for (j = 0; j < BURST_SIZE; j++) {
+ unsigned tmp = rte_rand() % 8;
+ hashes[j] = rte_rand() % MAX_KEYS/8;
+ hashes[j] |= (1lu << (56 + tmp));
+ ks[j].hashval = hashes[j];
+ ks[j].key[key_sizes[table_index] - 1] = tmp;
+ }
+ if (with_hash) {
+ hitcount = rte_tshash_lookup_bulk_with_hash(h[table_index], lookup_mask,
+ h_ptrs, keys, retvals,
+ &hitmask);
+ if (unlikely(hitcount != BURST_SIZE)) {
+ printf("Error lookup up hash keys. Expected retval = %u, got "
+ "%d\n", BURST_SIZE, hitcount);
+ printf("Hit mask = %"PRIx64"\n", hitmask);
+ return -1;
+ } else
+ continue;
+ } else {
+ hitcount = rte_tshash_lookup_bulk(h[table_index], lookup_mask,
+ keys, retvals, &hitmask);
+ if (unlikely(hitcount != BURST_SIZE)) {
+ printf("Error lookup up hash keys. Expected retval = %u, got "
+ "%d\n", BURST_SIZE, hitcount);
+ printf("Hit mask = %"PRIx64"\n", hitmask);
+ return -1;
+ }
+ }
+ }
+
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+ cycles[table_index][5][with_hash] = time_taken/NUM_LOOKUPS;
+
+ printf("%"PRIu64" lookups in %f seconds\n", (uint64_t) NUM_LOOKUPS,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per lookup\n",
+ cycles[table_index][5][with_hash]);
+ printf("Average %"PRIu64" lookups per second\n",
+ (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken);
+ return 0;
+}
+
+static int
+timed_deletes(unsigned with_hash, unsigned table_index)
+{
+ uint64_t i;
+ const uint64_t start_tsc = rte_rdtsc();
+ for (i = 0; i < MAX_KEYS; i++) {
+ union hash_key k = { .key = {0} };
+
+ k.hashval = i;
+ if (with_hash) {
+ if (rte_tshash_del_key_with_hash(h[table_index], k.hashval,
+ (const void *)k.key, NULL) < 0) {
+ printf("Error deleting hash key %"PRIu64"\n", k.hashval);
+ return -1;
+ } else
+ continue;
+ } else {
+ if (rte_tshash_del_key(h[table_index],
+ (const void *)k.key, NULL) < 0) {
+ printf("Error deleting hash key %"PRIu64"\n", k.hashval);
+ return -1;
+ }
+ }
+
+ }
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+ cycles[table_index][6][with_hash] = time_taken/MAX_KEYS;
+
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ const struct rte_tshash_stats *stats = rte_tshash_get_stats(h[table_index]);
+ printf("used_slots = %u, extra_buckets = %u\n", stats->used_slots,
+ stats->num_extra_buckets);
+#endif
+
+ printf("\n%"PRIu64" deletions in %f seconds\n", (uint64_t) MAX_KEYS,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per deletion\n",
+ cycles[table_index][6][with_hash]);
+ printf("Average %"PRIu64" deletions per second\n",
+ (MAX_KEYS * rte_get_tsc_hz())/time_taken);
+
+ return 0;
+}
+
+static int
+timed_deletes_extd(unsigned with_hash, unsigned table_index)
+{
+ uint64_t i, j;
+
+ const uint64_t start_tsc = rte_rdtsc();
+ for (i = 0; i < MAX_KEYS/8; i++) {
+ for (j = 0; j < 8; j++) {
+ union hash_key k = { .key = {0} };
+ k.hashval = i;
+ k.hashval |= (1lu<<(56+j));
+ k.key[key_sizes[table_index]-1] = j;
+ if (with_hash) {
+ if (rte_tshash_del_key_with_hash(h[table_index], k.hashval,
+ (const void *)k.key, NULL)
+ != 0) {
+ printf("Error deleting hash key %"PRIu64"\n", k.hashval);
+ return -1;
+ } else
+ continue;
+ } else {
+ if (rte_tshash_del_key(h[table_index], (const void *)k.key,
+ NULL) != 0) {
+ printf("Error deleting hash key %"PRIu64"\n", k.hashval);
+ return -1;
+ }
+ }
+ }
+ }
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+ cycles[table_index][7][with_hash] = time_taken/MAX_KEYS;
+
+#ifdef RTE_LIBRTE_THREAD_SAFE_HASH_STATS
+ const struct rte_tshash_stats *stats = rte_tshash_get_stats(h[table_index]);
+ printf("used_slots = %u, extra_buckets = %u\n", stats->used_slots,
+ stats->num_extra_buckets);
+#endif
+
+ printf("\n%"PRIu64" deletions in %f seconds\n", (uint64_t)MAX_KEYS,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per deletion\n",
+ cycles[table_index][7][with_hash]);
+ printf("Average %"PRIu64" deletions per second\n", (MAX_KEYS * rte_get_tsc_hz())/time_taken);
+
+ return 0;
+}
+
+static int
+reset_table(unsigned table_index) {
+
+ rte_tshash_reset(h[table_index]);
+ return 0;
+}
+
+static int
+test_tshash_perf(void)
+{
+ unsigned i, j;
+
+ for (i = 0; i < NUM_KEYSIZES; i++) {
+ printf("\n------ KEY SIZE = %u ----------\n\n", key_sizes[i]);
+ printf("\n ----- WITH PRECALCULATED HASH VALUES -----\n\n");
+ printf("Table with only first-level buckets used\n");
+ if (setup_table(1, i) < 0)
+ return -1;
+
+ printf("\nTimed lookups\n");
+ printf("------------------\n");
+ if (timed_lookups(1, i) < 0)
+ return -1;
+
+ printf("\nTimed lookups multi \n");
+ printf("------------------\n");
+ if (timed_lookups_multi(1, i) < 0)
+ return -1;
+
+ printf("\nTimed deletions \n");
+ printf("------------------\n");
+ if (timed_deletes(1, i) < 0)
+ return -1;
+
+ printf("\nResetting table to use extra buckets\n");
+ if (setup_table_extd(1, i) < 0)
+ return -1;
+
+ printf("\nTimed lookups extd\n");
+ printf("------------------\n");
+ if (timed_lookups_extd(1, i) < 0)
+ return -1;
+
+ printf("\nTimed lookups multi extd\n");
+ printf("------------------\n");
+ if (timed_lookups_multi_extd(1, i) < 0)
+ return -1;
+
+ printf("\nTimed deletions extd\n");
+ printf("------------------\n");
+ if (timed_deletes_extd(1, i) < 0)
+ return -1;
+
+ reset_table(i);
+
+ printf("\n ----- WITH JUST KEYS -----\n\n");
+
+ printf("Table with only first-level buckets used\n");
+ if (setup_table(0, i) < 0)
+ return -1;
+
+ printf("\nTimed lookups\n");
+ printf("------------------\n");
+ if (timed_lookups(0, i) < 0)
+ return -1;
+
+ printf("\nTimed lookups multi \n");
+ printf("------------------\n");
+ if (timed_lookups_multi(0, i) < 0)
+ return -1;
+
+ printf("\nTimed deletions \n");
+ printf("------------------\n");
+ if (timed_deletes(0, i) < 0)
+ return -1;
+
+ reset_table(i);
+
+ }
+ printf("\nResults (in CPU cycles/operation)\n");
+ printf("-----------------------------------\n");
+ printf("\nWith just keys (only 1st level buckets)\n");
+ printf("\n%-18s%-18s%-18s%-18s%-18s\n",
+ "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
+ for (i = 0; i < NUM_KEYSIZES; i++) {
+ printf("%-18d", key_sizes[i]);
+ for (j = 0; j < 8; j = j+2)
+ printf("%-18"PRIu64, cycles[i][j][0]);
+ printf("\n");
+ }
+
+ printf("\nWith precalculated hash (only 1st level buckets)\n");
+ printf("\n%-18s%-18s%-18s%-18s%-18s\n",
+ "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
+ for (i = 0; i < NUM_KEYSIZES; i++) {
+ printf("%-18d", key_sizes[i]);
+ for (j = 0; j < 8; j = j+2)
+ printf("%-18"PRIu64, cycles[i][j][1]);
+ printf("\n");
+ }
+ printf("\nWith precalculated hash (with extended buckets)\n");
+ printf("\n%-18s%-18s%-18s%-18s%-18s\n",
+ "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
+ for (i = 0; i < NUM_KEYSIZES; i++) {
+ printf("%-18d", key_sizes[i]);
+ for (j = 1; j < 8; j = j+2)
+ printf("%-18"PRIu64, cycles[i][j][1]);
+ printf("\n");
+ }
+ return 0;
+}
+
+static struct test_command tshash_perf_cmd = {
+ .command = "thread_safe_hash_perf_autotest",
+ .callback = test_tshash_perf,
+};
+REGISTER_TEST_COMMAND(tshash_perf_cmd);
--
1.7.7.6
^ permalink raw reply [flat|nested] 9+ messages in thread