From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id BC07AC5BC for ; Mon, 29 Jun 2015 00:25:34 +0200 (CEST) Received: from fmsmga001.fm.intel.com ([10.253.24.23]) by orsmga101.jf.intel.com with ESMTP; 28 Jun 2015 15:25:32 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,695,1427785200"; d="scan'208";a="736499440" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by fmsmga001.fm.intel.com with ESMTP; 28 Jun 2015 15:25:31 -0700 Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com [10.237.217.46]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id t5SMPUaH030618; Sun, 28 Jun 2015 23:25:30 +0100 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t5SMPUUN010202; Sun, 28 Jun 2015 23:25:30 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t5SMPUug010197; Sun, 28 Jun 2015 23:25:30 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Sun, 28 Jun 2015 23:25:24 +0100 Message-Id: <1435530330-10132-6-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1435269919-7007-1-git-send-email-pablo.de.lara.guarch@intel.com> <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH v3 05/11] hash: replace existing hash library with cuckoo hash implementation X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 28 Jun 2015 22:25:36 -0000 This patch replaces the existing hash library with another approach, using the Cuckoo Hash method to resolve collisions (open addressing), which pushes items from a full bucket when a new entry tries to be added in it, storing the evicted entry in an alternative location, using a secondary hash function. This gives the user the ability to store more entries when a bucket is full, in comparison with the previous implementation. Therefore, the unit test has been updated, as some scenarios have changed (such as the previous removed restriction). Also note that the API has not been changed, although new fields have been added in the rte_hash structure (structure is internal now). The main change when creating a new table is that the number of entries per bucket is fixed now, so its parameter is ignored now (still there to maintain the same parameters structure). The hash unit test has been updated to reflect these changes. As a last note, the maximum burst size in lookup_burst function hash been increased to 64, to improve performance. Signed-off-by: Pablo de Lara --- app/test/test_hash.c | 106 +--- lib/librte_hash/Makefile | 8 +- lib/librte_hash/rte_cuckoo_hash.c | 1056 +++++++++++++++++++++++++++++++++++++ lib/librte_hash/rte_hash.c | 499 ------------------ lib/librte_hash/rte_hash.h | 67 ++- 5 files changed, 1128 insertions(+), 608 deletions(-) create mode 100644 lib/librte_hash/rte_cuckoo_hash.c delete mode 100644 lib/librte_hash/rte_hash.c diff --git a/app/test/test_hash.c b/app/test/test_hash.c index 46174db..0176219 100644 --- a/app/test/test_hash.c +++ b/app/test/test_hash.c @@ -169,7 +169,6 @@ static struct flow_key keys[5] = { { /* Parameters used for hash table in unit test functions. Name set later. */ static struct rte_hash_parameters ut_params = { .entries = 64, - .bucket_entries = 4, .key_len = sizeof(struct flow_key), /* 13 */ .hash_func = rte_jhash, .hash_func_init_val = 0, @@ -516,9 +515,18 @@ static int test_five_keys(void) pos[i] = rte_hash_lookup(handle, &keys[i]); print_key_info("Lkp", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != -ENOENT, - "failed to find key (pos[%u]=%d)", i, pos[i]); + "found non-existent key (pos[%u]=%d)", i, pos[i]); } + /* Lookup multi */ + ret = rte_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos); + if (ret == 0) + for (i = 0; i < 5; i++) { + print_key_info("Lkp", key_array[i], pos[i]); + RETURN_IF_ERROR(pos[i] != -ENOENT, + "found not-existent key (pos[%u]=%d)", i, pos[i]); + } + rte_hash_free(handle); return 0; @@ -527,21 +535,18 @@ static int test_five_keys(void) /* * Add keys to the same bucket until bucket full. * - add 5 keys to the same bucket (hash created with 4 keys per bucket): - * first 4 successful, 5th unsuccessful - * - lookup the 5 keys: 4 hits, 1 miss - * - add the 5 keys again: 4 OK, one error as bucket is full - * - lookup the 5 keys: 4 hits (updated data), 1 miss - * - delete the 5 keys: 5 OK (even if the 5th is not in the table) + * first 4 successful, 5th successful, pushing existing item in bucket + * - lookup the 5 keys: 5 hits + * - add the 5 keys again: 5 OK + * - lookup the 5 keys: 5 hits (updated data) + * - delete the 5 keys: 5 OK * - lookup the 5 keys: 5 misses - * - add the 5th key: OK - * - lookup the 5th key: hit */ static int test_full_bucket(void) { struct rte_hash_parameters params_pseudo_hash = { .name = "test4", .entries = 64, - .bucket_entries = 4, .key_len = sizeof(struct flow_key), /* 13 */ .hash_func = pseudo_hash, .hash_func_init_val = 0, @@ -555,7 +560,7 @@ static int test_full_bucket(void) handle = rte_hash_create(¶ms_pseudo_hash); RETURN_IF_ERROR(handle == NULL, "hash creation failed"); - /* Fill bucket*/ + /* Fill bucket */ for (i = 0; i < 4; i++) { pos[i] = rte_hash_add_key(handle, &keys[i]); print_key_info("Add", &keys[i], pos[i]); @@ -563,47 +568,39 @@ static int test_full_bucket(void) "failed to add key (pos[%u]=%d)", i, pos[i]); expected_pos[i] = pos[i]; } - /* This shouldn't work because the bucket is full */ + /* + * This should work and will push one of the items + * in the bucket because it is full + */ pos[4] = rte_hash_add_key(handle, &keys[4]); print_key_info("Add", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != -ENOSPC, - "fail: added key to full bucket (pos[4]=%d)", pos[4]); + RETURN_IF_ERROR(pos[4] < 0, + "failed to add key (pos[4]=%d)", pos[4]); + expected_pos[4] = pos[4]; /* Lookup */ - for (i = 0; i < 4; i++) { + for (i = 0; i < 5; i++) { pos[i] = rte_hash_lookup(handle, &keys[i]); print_key_info("Lkp", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to find key (pos[%u]=%d)", i, pos[i]); } - pos[4] = rte_hash_lookup(handle, &keys[4]); - print_key_info("Lkp", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != -ENOENT, - "fail: found non-existent key (pos[4]=%d)", pos[4]); /* Add - update */ - for (i = 0; i < 4; i++) { + for (i = 0; i < 5; i++) { pos[i] = rte_hash_add_key(handle, &keys[i]); print_key_info("Add", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to add key (pos[%u]=%d)", i, pos[i]); } - pos[4] = rte_hash_add_key(handle, &keys[4]); - print_key_info("Add", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != -ENOSPC, - "fail: added key to full bucket (pos[4]=%d)", pos[4]); /* Lookup */ - for (i = 0; i < 4; i++) { + for (i = 0; i < 5; i++) { pos[i] = rte_hash_lookup(handle, &keys[i]); print_key_info("Lkp", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to find key (pos[%u]=%d)", i, pos[i]); } - pos[4] = rte_hash_lookup(handle, &keys[4]); - print_key_info("Lkp", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != -ENOENT, - "fail: found non-existent key (pos[4]=%d)", pos[4]); /* Delete 1 key, check other keys are still found */ pos[1] = rte_hash_del_key(handle, &keys[1]); @@ -623,35 +620,21 @@ static int test_full_bucket(void) RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]); /* Delete */ - for (i = 0; i < 4; i++) { + for (i = 0; i < 5; i++) { pos[i] = rte_hash_del_key(handle, &keys[i]); print_key_info("Del", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to delete key (pos[%u]=%d)", i, pos[i]); } - pos[4] = rte_hash_del_key(handle, &keys[4]); - print_key_info("Del", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != -ENOENT, - "fail: deleted non-existent key (pos[4]=%d)", pos[4]); /* Lookup */ - for (i = 0; i < 4; i++) { + for (i = 0; i < 5; i++) { pos[i] = rte_hash_lookup(handle, &keys[i]); print_key_info("Lkp", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != -ENOENT, "fail: found non-existent key (pos[%u]=%d)", i, pos[i]); } - /* Add and lookup the 5th key */ - pos[4] = rte_hash_add_key(handle, &keys[4]); - print_key_info("Add", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] < 0, "failed to add key (pos[4]=%d)", pos[4]); - expected_pos[4] = pos[4]; - pos[4] = rte_hash_lookup(handle, &keys[4]); - print_key_info("Lkp", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != expected_pos[4], - "failed to find key (pos[4]=%d)", pos[4]); - rte_hash_free(handle); /* Cover the NULL case. */ @@ -1017,18 +1000,8 @@ static int test_hash_creation_with_bad_parameters(void) } memcpy(¶ms, &ut_params, sizeof(params)); - params.name = "creation_with_bad_parameters_1"; - params.bucket_entries = RTE_HASH_BUCKET_ENTRIES_MAX + 1; - handle = rte_hash_create(¶ms); - if (handle != NULL) { - rte_hash_free(handle); - printf("Impossible creating hash sucessfully with bucket_entries in parameter exceeded\n"); - return -1; - } - - memcpy(¶ms, &ut_params, sizeof(params)); params.name = "creation_with_bad_parameters_2"; - params.entries = params.bucket_entries - 1; + params.entries = RTE_HASH_BUCKET_ENTRIES - 1; handle = rte_hash_create(¶ms); if (handle != NULL) { rte_hash_free(handle); @@ -1048,16 +1021,6 @@ static int test_hash_creation_with_bad_parameters(void) memcpy(¶ms, &ut_params, sizeof(params)); params.name = "creation_with_bad_parameters_4"; - params.bucket_entries = params.bucket_entries - 1; - handle = rte_hash_create(¶ms); - if (handle != NULL) { - rte_hash_free(handle); - printf("Impossible creating hash sucessfully if bucket_entries in parameter is not power of 2\n"); - return -1; - } - - memcpy(¶ms, &ut_params, sizeof(params)); - params.name = "creation_with_bad_parameters_5"; params.key_len = 0; handle = rte_hash_create(¶ms); if (handle != NULL) { @@ -1068,16 +1031,6 @@ static int test_hash_creation_with_bad_parameters(void) memcpy(¶ms, &ut_params, sizeof(params)); params.name = "creation_with_bad_parameters_6"; - params.key_len = RTE_HASH_KEY_LENGTH_MAX + 1; - handle = rte_hash_create(¶ms); - if (handle != NULL) { - rte_hash_free(handle); - printf("Impossible creating hash sucessfully if key_len is greater than the maximum\n"); - return -1; - } - - memcpy(¶ms, &ut_params, sizeof(params)); - params.name = "creation_with_bad_parameters_7"; params.socket_id = RTE_MAX_NUMA_NODES + 1; handle = rte_hash_create(¶ms); if (handle != NULL) { @@ -1211,7 +1164,6 @@ static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, static struct rte_hash_parameters hash_params_ex = { .name = NULL, .entries = 64, - .bucket_entries = 4, .key_len = 0, .hash_func = NULL, .hash_func_init_val = 0, diff --git a/lib/librte_hash/Makefile b/lib/librte_hash/Makefile index 3696cb1..1dc8a9c 100644 --- a/lib/librte_hash/Makefile +++ b/lib/librte_hash/Makefile @@ -1,6 +1,6 @@ # BSD LICENSE # -# Copyright(c) 2010-2014 Intel Corporation. All rights reserved. +# Copyright(c) 2010-2015 Intel Corporation. All rights reserved. # All rights reserved. # # Redistribution and use in source and binary forms, with or without @@ -42,7 +42,7 @@ EXPORT_MAP := rte_hash_version.map LIBABIVER := 1 # all source are stored in SRCS-y -SRCS-$(CONFIG_RTE_LIBRTE_HASH) := rte_hash.c +SRCS-$(CONFIG_RTE_LIBRTE_HASH) := rte_cuckoo_hash.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += rte_fbk_hash.c # install this header file @@ -51,7 +51,7 @@ SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_hash_crc.h SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_jhash.h SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_fbk_hash.h -# this lib needs eal -DEPDIRS-$(CONFIG_RTE_LIBRTE_HASH) += lib/librte_eal lib/librte_malloc +# this lib needs eal, malloc and ring +DEPDIRS-$(CONFIG_RTE_LIBRTE_HASH) += lib/librte_eal lib/librte_malloc lib/librte_ring include $(RTE_SDK)/mk/rte.lib.mk diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c new file mode 100644 index 0000000..10febdc --- /dev/null +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -0,0 +1,1056 @@ +/*- + * BSD LICENSE + * + * Copyright(c) 2010-2015 Intel Corporation. All rights reserved. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include +#include +#include +#include +#include + +#include +#include /* for definition of RTE_CACHE_LINE_SIZE */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "rte_hash.h" + +TAILQ_HEAD(rte_hash_list, rte_tailq_entry); + +static struct rte_tailq_elem rte_hash_tailq = { + .name = "RTE_HASH", +}; +EAL_REGISTER_TAILQ(rte_hash_tailq) + +/* Macro to enable/disable run-time checking of function parameters */ +#if defined(RTE_LIBRTE_HASH_DEBUG) +#define RETURN_IF_TRUE(cond, retval) do { \ + if (cond) \ + return retval; \ +} while (0) +#else +#define RETURN_IF_TRUE(cond, retval) +#endif + +/* Hash function used if none is specified */ +#ifdef RTE_MACHINE_CPUFLAG_SSE4_2 +#include +#define DEFAULT_HASH_FUNC rte_hash_crc +#else +#include +#define DEFAULT_HASH_FUNC rte_jhash +#endif + +#define NULL_SIGNATURE 0 + +typedef int (*rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t key_len); +static int rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t key_len); +static int rte_hash_k32_cmp_eq(const void *key1, const void *key2, size_t key_len); +static int rte_hash_k48_cmp_eq(const void *key1, const void *key2, size_t key_len); +static int rte_hash_k64_cmp_eq(const void *key1, const void *key2, size_t key_len); +static int rte_hash_k80_cmp_eq(const void *key1, const void *key2, size_t key_len); +static int rte_hash_k96_cmp_eq(const void *key1, const void *key2, size_t key_len); +static int rte_hash_k112_cmp_eq(const void *key1, const void *key2, size_t key_len); +static int rte_hash_k128_cmp_eq(const void *key1, const void *key2, size_t key_len); + +/** A hash table structure. */ +struct rte_hash { + char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */ + uint32_t entries; /**< Total table entries. */ + uint16_t key_len; /**< Length of hash key. */ + rte_hash_function hash_func; /**< Function used to calculate hash. */ + rte_hash_cmp_eq_t rte_hash_cmp_eq; /**< Function used to compare keys. */ + uint32_t hash_func_init_val; /**< Init value used by hash_func. */ + uint32_t num_buckets; /**< Number of buckets in table. */ + uint32_t bucket_bitmask; /**< Bitmask for getting bucket index + from hash signature. */ + uint32_t key_entry_size; /**< Size of each key entry. */ + + struct rte_ring *free_slots; /**< Ring that stores all indexes + of the free slots in the key table */ + void *key_store; /**< Table storing all keys and data */ + struct rte_hash_bucket *buckets; /**< Table with buckets storing all the + hash values and key indexes + to the key table*/ +} __rte_cache_aligned; + +/* Structure storing both primary and secondary hashes */ +struct rte_hash_signatures { + union { + struct { + hash_sig_t current; + hash_sig_t alt; + }; + uint64_t sig; + }; +}; + +/** Bucket structure */ +struct rte_hash_bucket { + struct rte_hash_signatures signatures[RTE_HASH_BUCKET_ENTRIES]; + /* Includes dummy key index that always contains index 0 */ + uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES + 1]; +} __rte_cache_aligned; + +struct rte_hash * +rte_hash_find_existing(const char *name) +{ + struct rte_hash *h = NULL; + struct rte_tailq_entry *te; + struct rte_hash_list *hash_list; + + hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); + + rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK); + TAILQ_FOREACH(te, hash_list, next) { + h = (struct rte_hash *) te->data; + if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0) + break; + } + rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK); + + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + return h; +} + +struct rte_hash * +rte_hash_create(const struct rte_hash_parameters *params) +{ + struct rte_hash *h = NULL; + struct rte_tailq_entry *te = NULL; + struct rte_hash_list *hash_list; + struct rte_ring *r = NULL; + char hash_name[RTE_HASH_NAMESIZE]; + void *ptr, *k = NULL; + char ring_name[RTE_RING_NAMESIZE]; + unsigned i; + + hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); + + if (params == NULL) { + RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n"); + return NULL; + } + + /* Check for valid parameters */ + if ((params->entries > RTE_HASH_ENTRIES_MAX) || + (params->entries < RTE_HASH_BUCKET_ENTRIES) || + !rte_is_power_of_2(params->entries) || + !rte_is_power_of_2(RTE_HASH_BUCKET_ENTRIES) || + (params->key_len == 0)) { + rte_errno = EINVAL; + RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n"); + return NULL; + } + + snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name); + + /* Guarantee there's no existing */ + h = rte_hash_find_existing(params->name); + if (h != NULL) + return h; + + /* Calculate hash dimensions */ + const uint32_t num_buckets = params->entries / RTE_HASH_BUCKET_ENTRIES; + + /* Total memory required for hash context */ + const uint32_t mem_size = sizeof(struct rte_hash) + + num_buckets * sizeof(struct rte_hash_bucket); + const uint32_t key_entry_size = params->key_len; + /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ + const uint64_t key_tbl_size = key_entry_size * (params->entries + 1); + + te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, HASH, "tailq entry allocation failed\n"); + goto err; + } + + h = (struct rte_hash *)rte_zmalloc_socket(hash_name, mem_size, + RTE_CACHE_LINE_SIZE, params->socket_id); + + if (h == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + goto err; + } + + k = rte_zmalloc_socket(NULL, key_tbl_size, + RTE_CACHE_LINE_SIZE, params->socket_id); + + if (k == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + goto err; + } + + /* Select function to compare keys */ + switch (params->key_len) { + case 16: + h->rte_hash_cmp_eq = rte_hash_k16_cmp_eq; + break; + case 32: + h->rte_hash_cmp_eq = rte_hash_k32_cmp_eq; + break; + case 48: + h->rte_hash_cmp_eq = rte_hash_k48_cmp_eq; + break; + case 64: + h->rte_hash_cmp_eq = rte_hash_k64_cmp_eq; + break; + case 80: + h->rte_hash_cmp_eq = rte_hash_k80_cmp_eq; + break; + case 96: + h->rte_hash_cmp_eq = rte_hash_k96_cmp_eq; + break; + case 112: + h->rte_hash_cmp_eq = rte_hash_k112_cmp_eq; + break; + case 128: + h->rte_hash_cmp_eq = rte_hash_k128_cmp_eq; + break; + default: + /* If key is not multiple of 16, use generic memcmp */ + h->rte_hash_cmp_eq = memcmp; + } + + snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name); + r = rte_ring_lookup(ring_name); + if (r != NULL) { + /* clear the free ring */ + while (rte_ring_dequeue(r, &ptr) == 0) + rte_pause(); + } else + r = rte_ring_create(ring_name, rte_align32pow2(params->entries + 1), + params->socket_id, 0); + if (r == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + goto err; + } + + /* Setup hash context */ + snprintf(h->name, sizeof(h->name), "%s", params->name); + h->entries = params->entries; + h->key_len = params->key_len; + h->key_entry_size = key_entry_size; + h->hash_func_init_val = params->hash_func_init_val; + + h->num_buckets = num_buckets; + h->bucket_bitmask = h->num_buckets - 1; + h->buckets = (void *) &h[1]; + h->hash_func = (params->hash_func == NULL) ? + DEFAULT_HASH_FUNC : params->hash_func; + + h->key_store = k; + h->free_slots = r; + te->data = (void *) h; + + /* populate the free slots ring. Entry zero is reserved for key misses */ + for (i = 1; i < params->entries + 1; i++) + rte_ring_sp_enqueue(r, (void *)((uintptr_t) i)); + + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); + TAILQ_INSERT_TAIL(hash_list, te, next); + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + + return h; +err: + rte_free(te); + rte_free(h); + rte_free(k); + return NULL; +} + +void +rte_hash_free(struct rte_hash *h) +{ + struct rte_tailq_entry *te; + struct rte_hash_list *hash_list; + + if (h == NULL) + return; + + hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); + + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); + + /* find out tailq entry */ + TAILQ_FOREACH(te, hash_list, next) { + if (te->data == (void *) h) + break; + } + + if (te == NULL) { + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + return; + } + + TAILQ_REMOVE(hash_list, te, next); + + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + + rte_free(h->key_store); + rte_free(h); + rte_free(te); +} + +hash_sig_t +rte_hash_hash(const struct rte_hash *h, const void *key) +{ + /* calc hash result by key */ + return h->hash_func(key, h->key_len, h->hash_func_init_val); +} + +/* Calc the secondary hash value from the primary hash value of a given key */ +static inline hash_sig_t +rte_hash_secondary_hash(const hash_sig_t primary_hash) +{ + static const unsigned all_bits_shift = 12; + static const unsigned alt_bits_xor = 0x5bd1e995; + + uint32_t tag = primary_hash >> all_bits_shift; + + return (primary_hash ^ ((tag + 1) * alt_bits_xor)); +} + +/* + * Try to insert a new entry. If bucket has space, hash value and key index + * to the key table are copied. + * If bucket is full, one of the entries in the bucket is evicted to + * its alternative location, based on the entry that has space + * in its alternative location. + * If none of the entries has space in its alternative location, + * we pick the last one to be pushed. + * Algorithm finishes when the entry has been successfully added. + * If we are trying to add AGAIN the same entry, + * entry cannot be added. + */ +static inline int32_t +run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, + uint32_t key_idx, hash_sig_t current_hash, + hash_sig_t alt_hash, hash_sig_t original_hash, + const void *original_key) +{ + static unsigned number_pushes; + void *k, *keys = h->key_store; + unsigned i, j; + + hash_sig_t current_hash_stored, alt_hash_stored; + uint32_t key_idx_stored; + uint32_t bucket_stored_idx; + struct rte_hash_bucket *bkt_stored; + + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + /* Check if slot is available */ + if (likely(bkt->signatures[i].sig == NULL_SIGNATURE)) { + bkt->signatures[i].current = current_hash; + bkt->signatures[i].alt = alt_hash; + bkt->key_idx[i] = key_idx; + number_pushes = 0; + return 0; + } + } + + /* + * If the entry that has been just evicted (hash) is the entry + * that is trying to be added in the hash table, + * we just entered in a loop and key cannot be added + */ + if (++number_pushes > 1 && current_hash == original_hash) { + k = (char *)keys + key_idx * h->key_entry_size; + if (!h->rte_hash_cmp_eq(k, original_key, h->key_len)) { + rte_ring_sp_enqueue(h->free_slots, + (void *)((uintptr_t)key_idx)); + number_pushes = 0; + return -ENOSPC; + } + } + + /* + * Push existing item (search for bucket with space in + * alternative locations) to its alternative location + */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + key_idx_stored = bkt->key_idx[i]; + current_hash_stored = bkt->signatures[i].current; + alt_hash_stored = bkt->signatures[i].alt; + + /* Search for space in alternative locations */ + bucket_stored_idx = alt_hash_stored & h->bucket_bitmask; + bkt_stored = &h->buckets[bucket_stored_idx]; + + for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) { + if (bkt_stored->signatures[j].sig == NULL_SIGNATURE) + break; + } + + if (j != RTE_HASH_BUCKET_ENTRIES) + break; + } + + /* Push existing item (if all alternative buckets are full, pick the last one) */ + if (i == RTE_HASH_BUCKET_ENTRIES) + i -= 1; + + /* Replace evicted entry with new entry */ + bkt->signatures[i].current = current_hash; + bkt->signatures[i].alt = alt_hash; + bkt->key_idx[i] = key_idx; + + /* There is an empty slot in the alternative bucket */ + if (j != RTE_HASH_BUCKET_ENTRIES) { + /* + * Swap current and alt hashes as we have pushed the item + * to its alternative location + */ + bkt_stored->signatures[j].current = alt_hash_stored; + bkt_stored->signatures[j].alt = current_hash_stored; + bkt_stored->key_idx[j] = key_idx_stored; + number_pushes = 0; + return 0; + } else + return run_cuckoo(h, bkt_stored, key_idx_stored, alt_hash_stored, + current_hash_stored, original_hash, original_key); +} + +static inline int32_t +__rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, + hash_sig_t sig) +{ + hash_sig_t hash0, hash1; + uint32_t bucket_idx0, bucket_idx1; + unsigned i; + struct rte_hash_bucket *bkt0, *bkt1; + void *new_k, *k, *keys = h->key_store; + void *slot_id; + int ret; + + /* Get a new slot for storing the new key */ + if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) + return -ENOSPC; + new_k = (char *)keys + (uintptr_t)slot_id * h->key_entry_size; + rte_prefetch0(new_k); + + hash0 = sig; + bucket_idx0 = hash0 & h->bucket_bitmask; + bkt0 = &h->buckets[bucket_idx0]; + + hash1 = rte_hash_secondary_hash(hash0); + bucket_idx1 = hash1 & h->bucket_bitmask; + bkt1 = &h->buckets[bucket_idx1]; + rte_prefetch0(bkt1); + + /* Check if key is already inserted in primary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt0->signatures[i].current == hash0 && + bkt0->signatures[i].alt == hash1) { + k = (char *)keys + bkt0->key_idx[i] * h->key_entry_size; + if (!h->rte_hash_cmp_eq(key, k, h->key_len)) { + rte_ring_sp_enqueue(h->free_slots, &slot_id); + /* + * Return index where key is stored, + * substracting the first dummy index + */ + return (bkt0->key_idx[i] - 1); + } + } + } + + /* Check if key is already inserted in secondary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt1->signatures[i].alt == hash0 && + bkt1->signatures[i].current == hash1) { + k = (char *)keys + bkt1->key_idx[i] * h->key_entry_size; + if (!h->rte_hash_cmp_eq(key, k, h->key_len)) { + rte_ring_sp_enqueue(h->free_slots, &slot_id); + /* + * Return index where key is stored, + * substracting the first dummy index + */ + return (bkt1->key_idx[i] - 1); + } + } + } + + /* Copy key */ + rte_memcpy(new_k, key, h->key_len); + + /* + * Run cuckoo algorithm + * Notice that for the first call of run_cuckoo, + * 4th and 5th parameter are the same (hash0), + * but this will change in next calls (recursive function), + * since the 4th parameter is the hash value we are currently trying + * to insert in the current bucket (NOT NEW in next calls) + * and the 5th parameter is the NEW hash value + * we are trying to add in the hash table + */ + ret = run_cuckoo(h, bkt0, (uint32_t)((uintptr_t) slot_id), hash0, + hash1, hash0, key); + + /* + * Return index where key is stored, + * substracting the first dummy index + * or error + */ + if (ret == 0) + return (int32_t)((uintptr_t) slot_id - 1); + else + return ret; +} + +int32_t +rte_hash_add_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_add_key_with_hash(h, key, sig); +} + +int32_t +rte_hash_add_key(const struct rte_hash *h, const void *key) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key)); +} + +static inline int32_t +__rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, + hash_sig_t sig) +{ + uint32_t bucket_idx; + hash_sig_t alt_hash; + unsigned i; + struct rte_hash_bucket *bkt; + void *k, *keys = h->key_store; + + bucket_idx = sig & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in primary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt->signatures[i].current == sig && + bkt->signatures[i].sig != NULL_SIGNATURE) { + k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; + if (!h->rte_hash_cmp_eq(key, k, h->key_len)) + /* + * Return index where key is stored, + * substracting the first dummy index + */ + return (bkt->key_idx[i] - 1); + } + } + + /* Calculate secondary hash */ + alt_hash = rte_hash_secondary_hash(sig); + bucket_idx = alt_hash & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in secondary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt->signatures[i].current == alt_hash && + bkt->signatures[i].alt == sig) { + k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; + if (!h->rte_hash_cmp_eq(key, k, h->key_len)) + /* + * Return index where key is stored, + * substracting the first dummy index + */ + return (bkt->key_idx[i] - 1); + } + } + + return -ENOENT; +} + +int32_t +rte_hash_lookup_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_lookup_with_hash(h, key, sig); +} + +int32_t +rte_hash_lookup(const struct rte_hash *h, const void *key) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key)); +} + +static inline int32_t +__rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, + hash_sig_t sig) +{ + uint32_t bucket_idx; + hash_sig_t alt_hash; + unsigned i; + struct rte_hash_bucket *bkt; + void *k, *keys = h->key_store; + + bucket_idx = sig & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in primary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt->signatures[i].current == sig && + bkt->signatures[i].sig != NULL_SIGNATURE) { + k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; + if (!h->rte_hash_cmp_eq(key, k, h->key_len)) { + bkt->signatures[i].sig = NULL_SIGNATURE; + rte_ring_sp_enqueue(h->free_slots, + (void *)((uintptr_t)bkt->key_idx[i])); + /* + * Return index where key is stored, + * substracting the first dummy index + */ + return (bkt->key_idx[i] - 1); + } + } + } + + /* Calculate secondary hash */ + alt_hash = rte_hash_secondary_hash(sig); + bucket_idx = alt_hash & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in secondary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt->signatures[i].current == alt_hash && + bkt->signatures[i].sig != NULL_SIGNATURE) { + k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; + if (!h->rte_hash_cmp_eq(key, k, h->key_len)) { + bkt->signatures[i].sig = NULL_SIGNATURE; + rte_ring_sp_enqueue(h->free_slots, + (void *)((uintptr_t)bkt->key_idx[i])); + /* + * Return index where key is stored, + * substracting the first dummy index + */ + return (bkt->key_idx[i] - 1); + } + } + } + + return -ENOENT; +} + +int32_t +rte_hash_del_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_del_key_with_hash(h, key, sig); +} + +int32_t +rte_hash_del_key(const struct rte_hash *h, const void *key) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key)); +} + +/* Lookup bulk stage 0: Calculate next primary/secondary hash value (from new key) */ +static inline void +lookup_stage0(unsigned *idx, uint64_t *lookup_mask, + hash_sig_t *primary_hash, hash_sig_t *secondary_hash, + const void * const *keys, const struct rte_hash *h) +{ + *idx = __builtin_ctzl(*lookup_mask); + if (*lookup_mask == 0) + *idx = 0; + + *primary_hash = rte_hash_hash(h, keys[*idx]); + *secondary_hash = rte_hash_secondary_hash(*primary_hash); + + *lookup_mask &= ~(1llu << *idx); +} + + +/* Lookup bulk stage 1: Prefetch primary/secondary buckets */ +static inline void +lookup_stage1(hash_sig_t primary_hash, hash_sig_t secondary_hash, + const struct rte_hash_bucket **primary_bkt, + const struct rte_hash_bucket **secondary_bkt, + const struct rte_hash *h) +{ + *primary_bkt = &h->buckets[primary_hash & h->bucket_bitmask]; + *secondary_bkt = &h->buckets[secondary_hash & h->bucket_bitmask]; + + rte_prefetch0(*primary_bkt); + rte_prefetch0(*secondary_bkt); +} + +/* + * Lookup bulk stage 2: Search for match hashes in primary/secondary locations + * and prefetch first key slot + */ +static inline void +lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash, + const struct rte_hash_bucket *prim_bkt, + const struct rte_hash_bucket *sec_bkt, + const void **key_slot, int32_t *positions, + uint64_t *extra_hits_mask, const void *keys, + const struct rte_hash *h) +{ + unsigned prim_hash_matches, sec_hash_matches, key_idx, i; + unsigned total_hash_matches; + + prim_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES; + sec_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES; + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + prim_hash_matches |= ((prim_hash == prim_bkt->signatures[i].current) << i); + sec_hash_matches |= ((sec_hash == sec_bkt->signatures[i].current) << i); + } + + key_idx = prim_bkt->key_idx[__builtin_ctzl(prim_hash_matches)]; + if (key_idx == 0) + key_idx = sec_bkt->key_idx[__builtin_ctzl(sec_hash_matches)]; + + total_hash_matches = (prim_hash_matches | + (sec_hash_matches << (RTE_HASH_BUCKET_ENTRIES + 1))); + *key_slot = (const char *)keys + key_idx * h->key_entry_size; + + rte_prefetch0(*key_slot); + /* + * Return index where key is stored, + * substracting the first dummy index + */ + positions[idx] = (key_idx - 1); + + *extra_hits_mask |= (uint64_t)(__builtin_popcount(prim_hash_matches) > 2) << idx; + *extra_hits_mask |= (uint64_t)(__builtin_popcount(sec_hash_matches) > 2) << idx; + *extra_hits_mask |= (uint64_t)(__builtin_popcount(total_hash_matches) > 3) << idx; + +} + + +/* Lookup bulk stage 3: Check if key matches, update hit mask */ +static inline void +lookup_stage3(unsigned idx, const void *key_slot, + const void * const *keys, int32_t *positions, + uint64_t *hits, const struct rte_hash *h) +{ + unsigned hit; + + hit = !h->rte_hash_cmp_eq(key_slot, keys[idx], h->key_len); + if (unlikely(hit == 0)) + positions[idx] = -ENOENT; + *hits = (uint64_t)(hit) << idx; +} + +static inline int +__rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, + uint32_t num_keys, int32_t *positions) { + + uint64_t hits = 0; + uint64_t next_mask = 0; + uint64_t extra_hits_mask = 0; + uint64_t lookup_mask; + unsigned idx; + const void *key_store = h->key_store; + + unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31; + const struct rte_hash_bucket *primary_bkt10, *primary_bkt11; + const struct rte_hash_bucket *secondary_bkt10, *secondary_bkt11; + const struct rte_hash_bucket *primary_bkt20, *primary_bkt21; + const struct rte_hash_bucket *secondary_bkt20, *secondary_bkt21; + const void *k_slot20, *k_slot21, *k_slot30, *k_slot31; + hash_sig_t primary_hash00, primary_hash01; + hash_sig_t secondary_hash00, secondary_hash01; + hash_sig_t primary_hash10, primary_hash11; + hash_sig_t secondary_hash10, secondary_hash11; + hash_sig_t primary_hash20, primary_hash21; + hash_sig_t secondary_hash20, secondary_hash21; + + if (num_keys == RTE_HASH_LOOKUP_BULK_MAX) + lookup_mask = 0xffffffffffffffff; + else + lookup_mask = (1ULL << num_keys) - 1; + + lookup_stage0(&idx00, &lookup_mask, &primary_hash00, + &secondary_hash00, keys, h); + lookup_stage0(&idx01, &lookup_mask, &primary_hash01, + &secondary_hash01, keys, h); + + primary_hash10 = primary_hash00; + primary_hash11 = primary_hash01; + secondary_hash10 = secondary_hash00; + secondary_hash11 = secondary_hash01; + idx10 = idx00, idx11 = idx01; + + lookup_stage0(&idx00, &lookup_mask, &primary_hash00, + &secondary_hash00, keys, h); + lookup_stage0(&idx01, &lookup_mask, &primary_hash01, + &secondary_hash01, keys, h); + lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, + &secondary_bkt10, h); + lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11, + &secondary_bkt11, h); + + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + primary_hash10 = primary_hash00; + primary_hash11 = primary_hash01; + secondary_hash10 = secondary_hash00; + secondary_hash11 = secondary_hash01; + idx10 = idx00, idx11 = idx01; + + lookup_stage0(&idx00, &lookup_mask, &primary_hash00, + &secondary_hash00, keys, h); + lookup_stage0(&idx01, &lookup_mask, &primary_hash01, + &secondary_hash01, keys, h); + lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, + &secondary_bkt10, h); + lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11, + &secondary_bkt11, h); + lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20, + secondary_bkt20, &k_slot20, positions, &extra_hits_mask, + key_store, h); + lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21, + secondary_bkt21, &k_slot21, positions, &extra_hits_mask, + key_store, h); + + while (lookup_mask) { + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + primary_hash10 = primary_hash00; + primary_hash11 = primary_hash01; + secondary_hash10 = secondary_hash00; + secondary_hash11 = secondary_hash01; + idx10 = idx00, idx11 = idx01; + + lookup_stage0(&idx00, &lookup_mask, &primary_hash00, + &secondary_hash00, keys, h); + lookup_stage0(&idx01, &lookup_mask, &primary_hash01, + &secondary_hash01, keys, h); + lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, + &secondary_bkt10, h); + lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11, + &secondary_bkt11, h); + lookup_stage2(idx20, primary_hash20, secondary_hash20, + primary_bkt20, secondary_bkt20, &k_slot20, positions, + &extra_hits_mask, key_store, h); + lookup_stage2(idx21, primary_hash21, secondary_hash21, + primary_bkt21, secondary_bkt21, &k_slot21, positions, + &extra_hits_mask, key_store, h); + lookup_stage3(idx30, k_slot30, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, &hits, h); + } + + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + primary_hash10 = primary_hash00; + primary_hash11 = primary_hash01; + secondary_hash10 = secondary_hash00; + secondary_hash11 = secondary_hash01; + idx10 = idx00, idx11 = idx01; + lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, + &secondary_bkt10, h); + lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11, + &secondary_bkt11, h); + lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20, + secondary_bkt20, &k_slot20, positions, &extra_hits_mask, + key_store, h); + lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21, + secondary_bkt21, &k_slot21, positions, &extra_hits_mask, + key_store, h); + lookup_stage3(idx30, k_slot30, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, &hits, h); + + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + + lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20, + secondary_bkt20, &k_slot20, positions, &extra_hits_mask, + key_store, h); + lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21, + secondary_bkt21, &k_slot21, positions, &extra_hits_mask, + key_store, h); + lookup_stage3(idx30, k_slot30, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, &hits, h); + + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + + lookup_stage3(idx30, k_slot30, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, &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); + positions[idx] = rte_hash_lookup(h, keys[idx]); + next_mask &= ~(1llu << idx); + } while (next_mask); + } + + return 0; +} + +int +rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, + uint32_t num_keys, int32_t *positions) +{ + RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || + (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || + (positions == NULL)), -EINVAL); + + return __rte_hash_lookup_bulk(h, keys, num_keys, positions); +} + +/* Functions to compare multiple of 16 byte keys (up to 128 bytes) */ +static int +rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused) +{ + const __m128i k1 = _mm_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_hash_k32_cmp_eq(const void *key1, const void *key2, size_t key_len) +{ + return rte_hash_k16_cmp_eq(key1, key2, key_len) || + rte_hash_k16_cmp_eq((const char *) key1 + 16, + (const char *) key2 + 16, key_len); +} + +static int +rte_hash_k48_cmp_eq(const void *key1, const void *key2, size_t key_len) +{ + return rte_hash_k16_cmp_eq(key1, key2, key_len) || + rte_hash_k16_cmp_eq((const char *) key1 + 16, + (const char *) key2 + 16, key_len) || + rte_hash_k16_cmp_eq((const char *) key1 + 32, + (const char *) key2 + 32, key_len); +} + +static int +rte_hash_k64_cmp_eq(const void *key1, const void *key2, size_t key_len) +{ + return rte_hash_k32_cmp_eq(key1, key2, key_len) || + rte_hash_k32_cmp_eq((const char *) key1 + 32, + (const char *) key2 + 32, key_len); +} + +static int +rte_hash_k80_cmp_eq(const void *key1, const void *key2, size_t key_len) +{ + return rte_hash_k64_cmp_eq(key1, key2, key_len) || + rte_hash_k16_cmp_eq((const char *) key1 + 64, + (const char *) key2 + 64, key_len); +} + +static int +rte_hash_k96_cmp_eq(const void *key1, const void *key2, size_t key_len) +{ + return rte_hash_k64_cmp_eq(key1, key2, key_len) || + rte_hash_k32_cmp_eq((const char *) key1 + 64, + (const char *) key2 + 64, key_len); +} + +static int +rte_hash_k112_cmp_eq(const void *key1, const void *key2, size_t key_len) +{ + return rte_hash_k64_cmp_eq(key1, key2, key_len) || + rte_hash_k32_cmp_eq((const char *) key1 + 64, + (const char *) key2 + 64, key_len) || + rte_hash_k16_cmp_eq((const char *) key1 + 96, + (const char *) key2 + 96, key_len); +} + +static int +rte_hash_k128_cmp_eq(const void *key1, const void *key2, size_t key_len) +{ + return rte_hash_k64_cmp_eq(key1, key2, key_len) || + rte_hash_k64_cmp_eq((const char *) key1 + 64, + (const char *) key2 + 64, key_len); +} diff --git a/lib/librte_hash/rte_hash.c b/lib/librte_hash/rte_hash.c deleted file mode 100644 index 5100a75..0000000 --- a/lib/librte_hash/rte_hash.c +++ /dev/null @@ -1,499 +0,0 @@ -/*- - * BSD LICENSE - * - * Copyright(c) 2010-2015 Intel Corporation. All rights reserved. - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in - * the documentation and/or other materials provided with the - * distribution. - * * Neither the name of Intel Corporation nor the names of its - * contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#include -#include -#include -#include -#include -#include - -#include -#include /* for definition of RTE_CACHE_LINE_SIZE */ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include "rte_hash.h" - -TAILQ_HEAD(rte_hash_list, rte_tailq_entry); - -static struct rte_tailq_elem rte_hash_tailq = { - .name = "RTE_HASH", -}; -EAL_REGISTER_TAILQ(rte_hash_tailq) - -/* Macro to enable/disable run-time checking of function parameters */ -#if defined(RTE_LIBRTE_HASH_DEBUG) -#define RETURN_IF_TRUE(cond, retval) do { \ - if (cond) return (retval); \ -} while (0) -#else -#define RETURN_IF_TRUE(cond, retval) -#endif - -/* Hash function used if none is specified */ -#ifdef RTE_MACHINE_CPUFLAG_SSE4_2 -#include -#define DEFAULT_HASH_FUNC rte_hash_crc -#else -#include -#define DEFAULT_HASH_FUNC rte_jhash -#endif - -/* Signature bucket size is a multiple of this value */ -#define SIG_BUCKET_ALIGNMENT 16 - -/* Stoered key size is a multiple of this value */ -#define KEY_ALIGNMENT 16 - -/* The high bit is always set in real signatures */ -#define NULL_SIGNATURE 0 - -struct rte_hash { - char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */ - uint32_t entries; /**< Total table entries. */ - uint32_t bucket_entries; /**< Bucket entries. */ - uint32_t key_len; /**< Length of hash key. */ - rte_hash_function hash_func; /**< Function used to calculate hash. */ - uint32_t hash_func_init_val; /**< Init value used by hash_func. */ - uint32_t num_buckets; /**< Number of buckets in table. */ - uint32_t bucket_bitmask; /**< Bitmask for getting bucket index - from hash signature. */ - hash_sig_t sig_msb; /**< MSB is always set in valid signatures. */ - uint8_t *sig_tbl; /**< Flat array of hash signature buckets. */ - uint32_t sig_tbl_bucket_size; /**< Signature buckets may be padded for - alignment reasons, and this is the - bucket size used by sig_tbl. */ - uint8_t *key_tbl; /**< Flat array of key value buckets. */ - uint32_t key_tbl_key_size; /**< Keys may be padded for alignment - reasons, and this is the key size - used by key_tbl. */ -}; - -/* Returns a pointer to the first signature in specified bucket. */ -static inline hash_sig_t * -get_sig_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index) -{ - return RTE_PTR_ADD(h->sig_tbl, (bucket_index * - h->sig_tbl_bucket_size)); -} - -/* Returns a pointer to the first key in specified bucket. */ -static inline uint8_t * -get_key_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index) -{ - return RTE_PTR_ADD(h->key_tbl, (bucket_index * h->bucket_entries * - h->key_tbl_key_size)); -} - -/* Returns a pointer to a key at a specific position in a specified bucket. */ -static inline void * -get_key_from_bucket(const struct rte_hash *h, uint8_t *bkt, uint32_t pos) -{ - return RTE_PTR_ADD(bkt, pos * h->key_tbl_key_size); -} - -/* Does integer division with rounding-up of result. */ -static inline uint32_t -div_roundup(uint32_t numerator, uint32_t denominator) -{ - return (numerator + denominator - 1) / denominator; -} - -/* Increases a size (if needed) to a multiple of alignment. */ -static inline uint32_t -align_size(uint32_t val, uint32_t alignment) -{ - return alignment * div_roundup(val, alignment); -} - -/* Returns the index into the bucket of the first occurrence of a signature. */ -static inline int -find_first(uint32_t sig, const uint32_t *sig_bucket, uint32_t num_sigs) -{ - uint32_t i; - for (i = 0; i < num_sigs; i++) { - if (sig == sig_bucket[i]) - return i; - } - return -1; -} - -struct rte_hash * -rte_hash_find_existing(const char *name) -{ - struct rte_hash *h = NULL; - struct rte_tailq_entry *te; - struct rte_hash_list *hash_list; - - hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); - - rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK); - TAILQ_FOREACH(te, hash_list, next) { - h = (struct rte_hash *) te->data; - if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0) - break; - } - rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK); - - if (te == NULL) { - rte_errno = ENOENT; - return NULL; - } - return h; -} - -struct rte_hash * -rte_hash_create(const struct rte_hash_parameters *params) -{ - struct rte_hash *h = NULL; - struct rte_tailq_entry *te; - uint32_t num_buckets, sig_bucket_size, key_size, - hash_tbl_size, sig_tbl_size, key_tbl_size, mem_size; - char hash_name[RTE_HASH_NAMESIZE]; - struct rte_hash_list *hash_list; - - hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); - - /* Check for valid parameters */ - if ((params == NULL) || - (params->entries > RTE_HASH_ENTRIES_MAX) || - (params->bucket_entries > RTE_HASH_BUCKET_ENTRIES_MAX) || - (params->entries < params->bucket_entries) || - !rte_is_power_of_2(params->entries) || - !rte_is_power_of_2(params->bucket_entries) || - (params->key_len == 0) || - (params->key_len > RTE_HASH_KEY_LENGTH_MAX)) { - rte_errno = EINVAL; - RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n"); - return NULL; - } - - snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name); - - /* Calculate hash dimensions */ - num_buckets = params->entries / params->bucket_entries; - sig_bucket_size = align_size(params->bucket_entries * - sizeof(hash_sig_t), SIG_BUCKET_ALIGNMENT); - key_size = align_size(params->key_len, KEY_ALIGNMENT); - - hash_tbl_size = align_size(sizeof(struct rte_hash), RTE_CACHE_LINE_SIZE); - sig_tbl_size = align_size(num_buckets * sig_bucket_size, - RTE_CACHE_LINE_SIZE); - key_tbl_size = align_size(num_buckets * key_size * - params->bucket_entries, RTE_CACHE_LINE_SIZE); - - /* Total memory required for hash context */ - mem_size = hash_tbl_size + sig_tbl_size + key_tbl_size; - - rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); - - /* guarantee there's no existing */ - TAILQ_FOREACH(te, hash_list, next) { - h = (struct rte_hash *) te->data; - if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0) - break; - } - if (te != NULL) - goto exit; - - te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0); - if (te == NULL) { - RTE_LOG(ERR, HASH, "tailq entry allocation failed\n"); - goto exit; - } - - h = (struct rte_hash *)rte_zmalloc_socket(hash_name, mem_size, - RTE_CACHE_LINE_SIZE, params->socket_id); - if (h == NULL) { - RTE_LOG(ERR, HASH, "memory allocation failed\n"); - rte_free(te); - goto exit; - } - - /* Setup hash context */ - snprintf(h->name, sizeof(h->name), "%s", params->name); - h->entries = params->entries; - h->bucket_entries = params->bucket_entries; - h->key_len = params->key_len; - h->hash_func_init_val = params->hash_func_init_val; - h->num_buckets = num_buckets; - h->bucket_bitmask = h->num_buckets - 1; - h->sig_msb = 1 << (sizeof(hash_sig_t) * 8 - 1); - h->sig_tbl = (uint8_t *)h + hash_tbl_size; - h->sig_tbl_bucket_size = sig_bucket_size; - h->key_tbl = h->sig_tbl + sig_tbl_size; - h->key_tbl_key_size = key_size; - h->hash_func = (params->hash_func == NULL) ? - DEFAULT_HASH_FUNC : params->hash_func; - - te->data = (void *) h; - - TAILQ_INSERT_TAIL(hash_list, te, next); - -exit: - rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); - - return h; -} - -void -rte_hash_free(struct rte_hash *h) -{ - struct rte_tailq_entry *te; - struct rte_hash_list *hash_list; - - if (h == NULL) - return; - - hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); - - rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); - - /* find out tailq entry */ - TAILQ_FOREACH(te, hash_list, next) { - if (te->data == (void *) h) - break; - } - - if (te == NULL) { - rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); - return; - } - - TAILQ_REMOVE(hash_list, te, next); - - rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); - - rte_free(h); - rte_free(te); -} - -hash_sig_t -rte_hash_hash(const struct rte_hash *h, const void *key) -{ - /* calc hash result by key */ - return h->hash_func(key, h->key_len, h->hash_func_init_val); -} - -static inline int32_t -__rte_hash_add_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) -{ - hash_sig_t *sig_bucket; - uint8_t *key_bucket; - uint32_t bucket_index, i; - int32_t pos; - - /* Get the hash signature and bucket index */ - sig |= h->sig_msb; - bucket_index = sig & h->bucket_bitmask; - sig_bucket = get_sig_tbl_bucket(h, bucket_index); - key_bucket = get_key_tbl_bucket(h, bucket_index); - - /* Check if key is already present in the hash */ - for (i = 0; i < h->bucket_entries; i++) { - if ((sig == sig_bucket[i]) && - likely(memcmp(key, get_key_from_bucket(h, key_bucket, i), - h->key_len) == 0)) { - return bucket_index * h->bucket_entries + i; - } - } - - /* Check if any free slot within the bucket to add the new key */ - pos = find_first(NULL_SIGNATURE, sig_bucket, h->bucket_entries); - - if (unlikely(pos < 0)) - return -ENOSPC; - - /* Add the new key to the bucket */ - sig_bucket[pos] = sig; - rte_memcpy(get_key_from_bucket(h, key_bucket, pos), key, h->key_len); - return bucket_index * h->bucket_entries + pos; -} - -int32_t -rte_hash_add_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) -{ - RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_add_key_with_hash(h, key, sig); -} - -int32_t -rte_hash_add_key(const struct rte_hash *h, const void *key) -{ - RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key)); -} - -static inline int32_t -__rte_hash_del_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) -{ - hash_sig_t *sig_bucket; - uint8_t *key_bucket; - uint32_t bucket_index, i; - - /* Get the hash signature and bucket index */ - sig = sig | h->sig_msb; - bucket_index = sig & h->bucket_bitmask; - sig_bucket = get_sig_tbl_bucket(h, bucket_index); - key_bucket = get_key_tbl_bucket(h, bucket_index); - - /* Check if key is already present in the hash */ - for (i = 0; i < h->bucket_entries; i++) { - if ((sig == sig_bucket[i]) && - likely(memcmp(key, get_key_from_bucket(h, key_bucket, i), - h->key_len) == 0)) { - sig_bucket[i] = NULL_SIGNATURE; - return bucket_index * h->bucket_entries + i; - } - } - - return -ENOENT; -} - -int32_t -rte_hash_del_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) -{ - RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_del_key_with_hash(h, key, sig); -} - -int32_t -rte_hash_del_key(const struct rte_hash *h, const void *key) -{ - RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key)); -} - -static inline int32_t -__rte_hash_lookup_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) -{ - hash_sig_t *sig_bucket; - uint8_t *key_bucket; - uint32_t bucket_index, i; - - /* Get the hash signature and bucket index */ - sig |= h->sig_msb; - bucket_index = sig & h->bucket_bitmask; - sig_bucket = get_sig_tbl_bucket(h, bucket_index); - key_bucket = get_key_tbl_bucket(h, bucket_index); - - /* Check if key is already present in the hash */ - for (i = 0; i < h->bucket_entries; i++) { - if ((sig == sig_bucket[i]) && - likely(memcmp(key, get_key_from_bucket(h, key_bucket, i), - h->key_len) == 0)) { - return bucket_index * h->bucket_entries + i; - } - } - - return -ENOENT; -} - -int32_t -rte_hash_lookup_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) -{ - RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_lookup_with_hash(h, key, sig); -} - -int32_t -rte_hash_lookup(const struct rte_hash *h, const void *key) -{ - RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key)); -} - -int -rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, - uint32_t num_keys, int32_t *positions) -{ - uint32_t i, j, bucket_index; - hash_sig_t sigs[RTE_HASH_LOOKUP_BULK_MAX]; - - RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || - (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || - (positions == NULL)), -EINVAL); - - /* Get the hash signature and bucket index */ - for (i = 0; i < num_keys; i++) { - sigs[i] = h->hash_func(keys[i], h->key_len, - h->hash_func_init_val) | h->sig_msb; - bucket_index = sigs[i] & h->bucket_bitmask; - - /* Pre-fetch relevant buckets */ - rte_prefetch1((void *) get_sig_tbl_bucket(h, bucket_index)); - rte_prefetch1((void *) get_key_tbl_bucket(h, bucket_index)); - } - - /* Check if key is already present in the hash */ - for (i = 0; i < num_keys; i++) { - bucket_index = sigs[i] & h->bucket_bitmask; - hash_sig_t *sig_bucket = get_sig_tbl_bucket(h, bucket_index); - uint8_t *key_bucket = get_key_tbl_bucket(h, bucket_index); - - positions[i] = -ENOENT; - - for (j = 0; j < h->bucket_entries; j++) { - if ((sigs[i] == sig_bucket[j]) && - likely(memcmp(keys[i], - get_key_from_bucket(h, key_bucket, j), - h->key_len) == 0)) { - positions[i] = bucket_index * - h->bucket_entries + j; - break; - } - } - } - - return 0; -} diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index 79827a6..13fad73 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -40,26 +40,31 @@ * RTE Hash Table */ +#include + #ifdef __cplusplus extern "C" { #endif /** Maximum size of hash table that can be created. */ -#define RTE_HASH_ENTRIES_MAX (1 << 26) +#define RTE_HASH_ENTRIES_MAX (1 << 30) -/** Maximum bucket size that can be created. */ -#define RTE_HASH_BUCKET_ENTRIES_MAX 16 +/** @deprecated Maximum bucket size that can be created. */ +#define RTE_HASH_BUCKET_ENTRIES_MAX 4 -/** Maximum length of key that can be used. */ -#define RTE_HASH_KEY_LENGTH_MAX 64 +/** Number of items per bucket. */ +#define RTE_HASH_BUCKET_ENTRIES 4 -/** Max number of keys that can be searched for using rte_hash_lookup_multi. */ -#define RTE_HASH_LOOKUP_BULK_MAX 16 -#define RTE_HASH_LOOKUP_MULTI_MAX RTE_HASH_LOOKUP_BULK_MAX +/** @deprecated Maximum length of key that can be used. */ +#define RTE_HASH_KEY_LENGTH_MAX 64 -/** Max number of characters in hash name.*/ +/** Maximum number of characters in hash name.*/ #define RTE_HASH_NAMESIZE 32 +/** Maximum number of keys that can be searched for using rte_hash_lookup_bulk. */ +#define RTE_HASH_LOOKUP_BULK_MAX 64 +#define RTE_HASH_LOOKUP_MULTI_MAX RTE_HASH_LOOKUP_BULK_MAX + /** Signature of key that is stored internally. */ typedef uint32_t hash_sig_t; @@ -74,9 +79,9 @@ typedef uint32_t (*rte_hash_function)(const void *key, uint32_t key_len, struct rte_hash_parameters { const char *name; /**< Name of the hash. */ uint32_t entries; /**< Total hash table entries. */ - uint32_t bucket_entries; /**< Bucket entries. */ + uint32_t bucket_entries; /**< Bucket entries. */ uint32_t key_len; /**< Length of hash key. */ - rte_hash_function hash_func; /**< Function used to calculate hash. */ + rte_hash_function hash_func; /**< Primary Hash function used to calculate hash. */ uint32_t hash_func_init_val; /**< Init value used by hash_func. */ int socket_id; /**< NUMA Socket ID for memory. */ }; @@ -84,6 +89,7 @@ struct rte_hash_parameters { /** @internal A hash table structure. */ struct rte_hash; + /** * Create a new hash table. * @@ -104,7 +110,6 @@ struct rte_hash; struct rte_hash * rte_hash_create(const struct rte_hash_parameters *params); - /** * Find an existing hash table object and return a pointer to it. * @@ -127,7 +132,8 @@ void rte_hash_free(struct rte_hash *h); /** - * Add a key to an existing hash table. This operation is not multi-thread safe + * Add a key to an existing hash table. + * This operation is not multi-thread safe * and should only be called from one thread. * * @param h @@ -144,7 +150,8 @@ int32_t rte_hash_add_key(const struct rte_hash *h, const void *key); /** - * Add a key to an existing hash table. This operation is not multi-thread safe + * Add a key to an existing hash table. + * This operation is not multi-thread safe * and should only be called from one thread. * * @param h @@ -152,7 +159,7 @@ rte_hash_add_key(const struct rte_hash *h, const void *key); * @param key * Key to add to the hash table. * @param sig - * Hash value to add to the hash table. + * Precomputed hash value for 'key'. * @return * - -EINVAL if the parameters are invalid. * - -ENOSPC if there is no space in the hash for this key. @@ -160,11 +167,11 @@ rte_hash_add_key(const struct rte_hash *h, const void *key); * array of user data. This value is unique for this key. */ int32_t -rte_hash_add_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig); +rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); /** - * Remove a key from an existing hash table. This operation is not multi-thread + * Remove a key from an existing hash table. + * This operation is not multi-thread * safe and should only be called from one thread. * * @param h @@ -182,7 +189,8 @@ int32_t rte_hash_del_key(const struct rte_hash *h, const void *key); /** - * Remove a key from an existing hash table. This operation is not multi-thread + * Remove a key from an existing hash table. + * This operation is not multi-thread * safe and should only be called from one thread. * * @param h @@ -190,7 +198,7 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); * @param key * Key to remove from the hash table. * @param sig - * Hash value to remove from the hash table. + * Precomputed hash value for 'key'. * @return * - -EINVAL if the parameters are invalid. * - -ENOENT if the key is not found. @@ -199,12 +207,11 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); * value that was returned when the key was added. */ int32_t -rte_hash_del_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig); - +rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); /** - * Find a key in the hash table. This operation is multi-thread safe. + * Find a key in the hash table. + * This operation is multi-thread safe. * * @param h * Hash table to look in. @@ -221,14 +228,15 @@ int32_t rte_hash_lookup(const struct rte_hash *h, const void *key); /** - * Find a key in the hash table. This operation is multi-thread safe. + * Find a key in the hash table. + * This operation is multi-thread safe. * * @param h * Hash table to look in. * @param key * Key to find. * @param sig - * Hash value to find. + * Hash value to remove from the hash table. * @return * - -EINVAL if the parameters are invalid. * - -ENOENT if the key is not found. @@ -241,7 +249,8 @@ rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); /** - * Calc a hash value by key. This operation is not multi-process safe. + * Calc a hash value by key. + * This operation is not multi-process safe. * * @param h * Hash table to look in. @@ -255,7 +264,8 @@ rte_hash_hash(const struct rte_hash *h, const void *key); #define rte_hash_lookup_multi rte_hash_lookup_bulk /** - * Find multiple keys in the hash table. This operation is multi-thread safe. + * Find multiple keys in the hash table. + * This operation is multi-thread safe. * * @param h * Hash table to look in. @@ -275,6 +285,7 @@ rte_hash_hash(const struct rte_hash *h, const void *key); int rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, uint32_t num_keys, int32_t *positions); + #ifdef __cplusplus } #endif -- 2.4.2