Signed-off-by: Peng <xnhp0...@icloud.com> --- helper/Makefile.am | 2 + helper/cuckoo_hash.c | 1117 +++++++++++++++++++++++++++++++ helper/include/odp/helper/cuckoo_hash.h | 435 ++++++++++++ helper/include/odp/helper/ring.h | 43 ++ helper/ring.c | 28 + helper/test/Makefile.am | 4 +- helper/test/odp_cuckoo_hash.c | 779 +++++++++++++++++++++ include/odp/api/hash.h | 16 +- 8 files changed, 2422 insertions(+), 2 deletions(-) create mode 100644 helper/cuckoo_hash.c create mode 100644 helper/include/odp/helper/cuckoo_hash.h create mode 100644 helper/test/odp_cuckoo_hash.c
diff --git a/helper/Makefile.am b/helper/Makefile.am index e72507e..e923aa8 100644 --- a/helper/Makefile.am +++ b/helper/Makefile.am @@ -18,6 +18,7 @@ helperinclude_HEADERS = \ $(srcdir)/include/odp/helper/ipsec.h\ $(srcdir)/include/odp/helper/tcp.h\ $(srcdir)/include/odp/helper/table.h\ + $(srcdir)/include/odp/helper/cuckoo_hash.h\ $(srcdir)/include/odp/helper/udp.h noinst_HEADERS = \ @@ -30,6 +31,7 @@ noinst_HEADERS = \ __LIB__libodphelper_la_SOURCES = \ linux.c \ ring.c \ + cuckoo_hash.c \ hashtable.c \ lineartable.c diff --git a/helper/cuckoo_hash.c b/helper/cuckoo_hash.c new file mode 100644 index 0000000..4a4b56b --- /dev/null +++ b/helper/cuckoo_hash.c @@ -0,0 +1,1117 @@ +/* Copyright (c) 2015, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +/*- + * BSD LICENSE + * + * Copyright(c) 2010-2015 Intel Corporation. All rights reserved. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include <string.h> +#include <stdint.h> +#include <errno.h> +#include <stdio.h> +#include <stdarg.h> +#include <sys/queue.h> + +#include <odp/helper/cuckoo_hash.h> +#include <odp/shared_memory.h> +#include <odp/spinlock.h> +#include <odp/align.h> +#include <odp/api/errno.h> +#include <odp/rwlock.h> +#include <odp/hints.h> +#include <odp/helper/ring.h> +#include "odph_debug.h" + +/* Macro to enable/disable run-time checking of function parameters */ +#define RETURN_IF_TRUE(cond, retval) do { \ + if (cond) \ + return retval; \ +} while (0) + +/* Hash function used if none is specified */ +#include <odp/hash.h> + +/** Number of items per bucket. */ +#define HASH_BUCKET_ENTRIES 4 +#define NULL_SIGNATURE 0 +#define KEY_ALIGNMENT 16 + +/** Maximum size of hash table that can be created. */ +#define HASH_ENTRIES_MAX 1048576 + +/** Maximum number of keys that can be + * searched for using odph_hash_lookup_bulk. */ +#define HASH_LOOKUP_BULK_MAX 64 +#define HASH_LOOKUP_MULTI_MAX HASH_LOOKUP_BULK_MAX + +/* Structure storing both primary and secondary hashes */ +struct cuckoo_hash_signatures { + union { + struct { + uint32_t current; + uint32_t alt; + }; + uint64_t sig; + }; +}; + +/* Structure that stores key-value pair */ +struct cuckoo_hash_key { + union { + uintptr_t idata; + void *pdata; + }; + /* Variable key size */ + char key[0]; +} ODP_ALIGNED(KEY_ALIGNMENT); + +/** Bucket structure */ +struct cuckoo_hash_bucket { + struct cuckoo_hash_signatures signatures[HASH_BUCKET_ENTRIES]; + /* Includes dummy key index that always contains index 0 */ + uint32_t key_idx[HASH_BUCKET_ENTRIES + 1]; + uint8_t flag[HASH_BUCKET_ENTRIES]; +} ODP_ALIGNED_CACHE; + +/** + * Aligns input parameter to the next power of 2 + * + * @param x + * The integer value to algin + * + * @return + * Input parameter aligned to the next power of 2 + */ +static inline uint32_t +align32pow2(uint32_t x) +{ + x--; + x |= x >> 1; + x |= x >> 2; + x |= x >> 4; + x |= x >> 8; + x |= x >> 16; + + return x + 1; +} + +/** + * Returns true if n is a power of 2 + * @param n + * Number to check + * @return 1 if true, 0 otherwise + */ +static inline int +is_power_of_2(uint32_t n) +{ + return n && !(n & (n - 1)); +} + +odph_cuckoo_hash_tbl_t * +odph_cuckoo_hash_find_existing(const char *name) +{ + odph_cuckoo_hash_tbl_t *h = NULL; + odp_shm_t shm = odp_shm_lookup(name); + + if (shm == ODP_SHM_INVALID) + return NULL; + + h = (odph_cuckoo_hash_tbl_t *)odp_shm_addr(shm); + return h; +} + +int +odph_cuckoo_hash_create(odph_cuckoo_hash_tbl_t **ht, + const odph_cuckoo_hash_param_t *params) +{ + odph_cuckoo_hash_tbl_t *h; + odph_ring_t *r = NULL; + odp_shm_t shm_h, shm_b, shm_k; + + char bucket_name[ODPH_CUCKOO_HASH_NAMESIZE + 2], + key_name[ODPH_CUCKOO_HASH_NAMESIZE + 2]; + + void *ptr, *k = NULL; + void *buckets = NULL; + char ring_name[ODPH_RING_NAMESIZE]; + unsigned i; + + if (params == NULL) { + ODPH_ERR("no parameters\n"); + *ht = NULL; + return -EINVAL; + } + + /* Check for valid parameters */ + if ( + (params->entries > HASH_ENTRIES_MAX) || + (params->entries < HASH_BUCKET_ENTRIES) || + (params->key_len == 0) || + (strlen(params->name) == 0)) { + ODPH_ERR("invalid parameters\n"); + *ht = NULL; + return -EINVAL; + } + + /* Guarantee there's no existing */ + h = odph_cuckoo_hash_find_existing(params->name); + if (h != NULL) { + ODPH_ERR("cuckoo hash table %s already exists\n", params->name); + *ht = h; + return -EEXIST; + } + + shm_h = odp_shm_reserve( + params->name, sizeof(odph_cuckoo_hash_tbl_t), + ODP_CACHE_LINE_SIZE, ODP_SHM_SW_ONLY); + + if (shm_h == ODP_SHM_INVALID) { + ODPH_ERR("shm allocation failed for odph_cuckoo_hash_tbl %s\n", + params->name); + *ht = NULL; + return -ENOMEM; + } + h = odp_shm_addr(shm_h); + + snprintf(bucket_name, sizeof(bucket_name), "B_%s", params->name); + const uint32_t num_buckets = + align32pow2(params->entries) / HASH_BUCKET_ENTRIES; + + shm_b = odp_shm_reserve( + bucket_name, + num_buckets * sizeof(struct cuckoo_hash_bucket), + ODP_CACHE_LINE_SIZE, ODP_SHM_SW_ONLY); + + if (shm_b == ODP_SHM_INVALID) { + ODPH_ERR("shm allocation failed for cuckoo_hash_bucket\n"); + odp_shm_free(shm_h); + *ht = NULL; + return -ENOMEM; + } + + buckets = odp_shm_addr(shm_b); + + snprintf(key_name, sizeof(key_name), "K_%s", params->name); + const uint32_t key_entry_size = + sizeof(struct cuckoo_hash_key) + 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); + + shm_k = odp_shm_reserve(key_name, key_tbl_size, ODP_CACHE_LINE_SIZE, + ODP_SHM_SW_ONLY); + if (shm_k == ODP_SHM_INVALID) { + ODPH_ERR("shm allocation failed for key_store\n"); + odp_shm_free(shm_b); + odp_shm_free(shm_h); + *ht = NULL; + return -ENOMEM; + } + k = odp_shm_addr(shm_k); + + snprintf(ring_name, sizeof(ring_name), "RI_%s", params->name); + r = odph_ring_lookup(ring_name); + if (r != NULL) { + /* clear the free ring */ + while (odph_ring_sc_dequeue(r, ptr) == 0) { + /* empty */ + } + } else { + r = odph_ring_create(ring_name, + align32pow2(params->entries + 1), 0); + } + + if (r == NULL) { + odp_shm_free(shm_k); + odp_shm_free(shm_b); + odp_shm_free(shm_h); + *ht = NULL; + return -ENOMEM; + } + + /* 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->hash_cmp_eq = memcmp; + + h->num_buckets = num_buckets; + h->bucket_bitmask = h->num_buckets - 1; + h->buckets = buckets; + + /*default hash function is CRC 32*/ + h->hash_func = (params->hash_func == NULL) ? + odp_hash_crc32c : params->hash_func; + + h->key_store = k; + h->free_slots = r; + + h->shm_bucket = shm_b; + h->shm_key = shm_k; + + /* populate the free slots ring. + * Entry zero is reserved for key misses + */ + for (i = 1; i < params->entries + 1; i++) + odph_ring_sp_enqueue(r, (void *)((uintptr_t)i)); + *ht = h; + return 0; +} + +void +odph_cuckoo_hash_destroy(odph_cuckoo_hash_tbl_t *h) +{ + if (h == NULL) + return; + + odph_ring_free(h->free_slots); + odp_shm_free(h->shm_key); + odp_shm_free(h->shm_bucket); + odp_shm_free(odp_shm_lookup(h->name)); +} + +static uint32_t hash(const odph_cuckoo_hash_tbl_t *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 uint32_t +hash_secondary(const uint32_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)); +} + +void +odph_cuckoo_hash_reset(odph_cuckoo_hash_tbl_t *h) +{ + void *ptr; + unsigned i; + + if (h == NULL) + return; + + memset(h->buckets, 0, + h->num_buckets * sizeof(struct cuckoo_hash_bucket)); + memset(h->key_store, 0, h->key_entry_size * (h->entries + 1)); + + /* clear the free ring */ + while (odph_ring_sc_dequeue(h->free_slots, ptr) == 0) { + /* empty */ + } + + /* Repopulate the free slots ring. + * Entry zero is reserved for key misses */ + for (i = 1; i < h->entries + 1; i++) + odph_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)i)); +} + +/* Search for an entry that can be pushed to its alternative location */ +static inline int +make_space_bucket(const odph_cuckoo_hash_tbl_t *h, + struct cuckoo_hash_bucket *bkt) +{ + unsigned i, j; + int ret; + uint32_t next_bucket_idx; + struct cuckoo_hash_bucket *next_bkt[HASH_BUCKET_ENTRIES]; + + /* + * Push existing item (search for bucket with space in + * alternative locations) to its alternative location + */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + /* Search for space in alternative locations */ + next_bucket_idx = bkt->signatures[i].alt & h->bucket_bitmask; + next_bkt[i] = &h->buckets[next_bucket_idx]; + for (j = 0; j < HASH_BUCKET_ENTRIES; j++) { + if (next_bkt[i]->signatures[j].sig == NULL_SIGNATURE) + break; + } + + if (j != HASH_BUCKET_ENTRIES) + break; + } + + /* Alternative location has spare room (end of recursive function) */ + if (i != HASH_BUCKET_ENTRIES) { + next_bkt[i]->signatures[j].alt = bkt->signatures[i].current; + next_bkt[i]->signatures[j].current = bkt->signatures[i].alt; + next_bkt[i]->key_idx[j] = bkt->key_idx[i]; + return i; + } + + /* Pick entry that has not been pushed yet */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) + if (bkt->flag[i] == 0) + break; + + /* All entries have been pushed, so entry cannot be added */ + if (i == HASH_BUCKET_ENTRIES) + return -ENOSPC; + + /* Set flag to indicate that this entry is going to be pushed */ + bkt->flag[i] = 1; + /* Need room in alternative bucket to insert the pushed entry */ + ret = make_space_bucket(h, next_bkt[i]); + /* + * After recursive function. + * Clear flags and insert the pushed entry + * in its alternative location if successful, + * or return error + */ + bkt->flag[i] = 0; + if (ret >= 0) { + next_bkt[i]->signatures[ret].alt = bkt->signatures[i].current; + next_bkt[i]->signatures[ret].current = bkt->signatures[i].alt; + next_bkt[i]->key_idx[ret] = bkt->key_idx[i]; + return i; + } + + return ret; +} + +static inline int32_t +cuckoo_hash_add_key_with_hash( + const odph_cuckoo_hash_tbl_t *h, const void *key, + uint32_t sig, void *data) +{ + uint32_t alt_hash; + uint32_t prim_bucket_idx, sec_bucket_idx; + unsigned i; + struct cuckoo_hash_bucket *prim_bkt, *sec_bkt; + struct cuckoo_hash_key *new_k, *k, *keys = h->key_store; + void *slot_id; + uint32_t new_idx; + int ret; + + prim_bucket_idx = sig & h->bucket_bitmask; + prim_bkt = &h->buckets[prim_bucket_idx]; + __builtin_prefetch((const void *)(uintptr_t)prim_bkt, 0, 3); + + alt_hash = hash_secondary(sig); + sec_bucket_idx = alt_hash & h->bucket_bitmask; + sec_bkt = &h->buckets[sec_bucket_idx]; + __builtin_prefetch((const void *)(uintptr_t)sec_bkt, 0, 3); + + /* Get a new slot for storing the new key */ + if (odph_ring_sc_dequeue_bulk(h->free_slots, &slot_id, 1) != 0) + return -ENOSPC; + new_k = (void *)((uintptr_t)(keys) + + ((uintptr_t)slot_id * h->key_entry_size)); + __builtin_prefetch((const void *)(uintptr_t)new_k, 0, 3); + new_idx = (uint32_t)((uintptr_t)slot_id); + + /* Check if key is already inseodpd in primary location */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + if ( + prim_bkt->signatures[i].current == sig && + prim_bkt->signatures[i].alt == alt_hash) { + k = (struct cuckoo_hash_key *)((char *)keys + + prim_bkt->key_idx[i] * h->key_entry_size); + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) { + odph_ring_sp_enqueue(h->free_slots, slot_id); + /* Update data */ + k->pdata = data; + /* + * Return index where key is stored, + * substracting the first dummy index + */ + return (prim_bkt->key_idx[i] - 1); + } + } + } + + /* Check if key is already inseodpd in secondary location */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + if ( + sec_bkt->signatures[i].alt == sig && + sec_bkt->signatures[i].current == alt_hash) { + k = (struct cuckoo_hash_key *)((char *)keys + + sec_bkt->key_idx[i] * h->key_entry_size); + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) { + odph_ring_sp_enqueue(h->free_slots, slot_id); + /* Update data */ + k->pdata = data; + /* + * Return index where key is stored, + * substracting the first dummy index + */ + return (sec_bkt->key_idx[i] - 1); + } + } + } + + /* Copy key */ + memcpy(new_k->key, key, h->key_len); + new_k->pdata = data; + + /* Insert new entry is there is room in the primary bucket */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + /* Check if slot is available */ + if (odp_likely(prim_bkt->signatures[i].sig == NULL_SIGNATURE)) { + prim_bkt->signatures[i].current = sig; + prim_bkt->signatures[i].alt = alt_hash; + prim_bkt->key_idx[i] = new_idx; + return new_idx - 1; + } + } + + /* Primary bucket is full, so we need to make space for new entry */ + ret = make_space_bucket(h, prim_bkt); + /* + * After recursive function. + * Insert the new entry in the position of the pushed entry + * if successful or return error and + * store the new slot back in the ring + */ + if (ret >= 0) { + prim_bkt->signatures[ret].current = sig; + prim_bkt->signatures[ret].alt = alt_hash; + prim_bkt->key_idx[ret] = new_idx; + return (new_idx - 1); + } + + /* Error in addition, store new slot back in the ring */ + odph_ring_sp_enqueue( + h->free_slots, (void *)((uintptr_t)new_idx)); + return ret; +} + +int32_t +odph_cuckoo_hash_add_key_with_hash( + const odph_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return cuckoo_hash_add_key_with_hash(h, key, sig, 0); +} + +int32_t +odph_cuckoo_hash_add_key(const odph_cuckoo_hash_tbl_t *h, const void *key) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return cuckoo_hash_add_key_with_hash( + h, key, hash(h, key), 0); +} + +int +odph_cuckoo_hash_add_key_with_hash_data( + const odph_cuckoo_hash_tbl_t *h, + const void *key, uint32_t sig, void *data) +{ + int ret; + + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + ret = cuckoo_hash_add_key_with_hash(h, key, sig, data); + if (ret >= 0) + return 0; + return ret; +} + +int +odph_cuckoo_hash_add_key_data(const odph_cuckoo_hash_tbl_t *h, + const void *key, void *data) +{ + int ret; + + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + + ret = cuckoo_hash_add_key_with_hash( + h, key, hash(h, key), data); + if (ret >= 0) + return 0; + return ret; +} + +static inline int32_t +cuckoo_hash_lookup_with_hash( + const odph_cuckoo_hash_tbl_t *h, const void *key, + uint32_t sig, void **data) +{ + uint32_t bucket_idx; + uint32_t alt_hash; + unsigned i; + struct cuckoo_hash_bucket *bkt; + struct cuckoo_hash_key *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 < HASH_BUCKET_ENTRIES; i++) { + if ( + bkt->signatures[i].current == sig && + bkt->signatures[i].sig != NULL_SIGNATURE) { + k = (void *)((uintptr_t)keys + + (bkt->key_idx[i] * h->key_entry_size)); + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) { + if (data != NULL) + *data = k->pdata; + /* + * Return index where key is stored, + * substracting the first dummy index + */ + return (bkt->key_idx[i] - 1); + } + } + } + + /* Calculate secondary hash */ + alt_hash = hash_secondary(sig); + bucket_idx = alt_hash & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in secondary location */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + if ( + bkt->signatures[i].current == alt_hash && + bkt->signatures[i].alt == sig) { + k = (struct cuckoo_hash_key *)((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) { + if (data != NULL) + *data = k->pdata; + /* + * Return index where key is stored, + * substracting the first dummy index + */ + return (bkt->key_idx[i] - 1); + } + } + } + + return -ENOENT; +} + +int32_t +odph_cuckoo_hash_lookup_with_hash( + const odph_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return cuckoo_hash_lookup_with_hash(h, key, sig, NULL); +} + +int32_t +odph_cuckoo_hash_lookup(const odph_cuckoo_hash_tbl_t *h, const void *key) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return cuckoo_hash_lookup_with_hash( + h, key, hash(h, key), NULL); +} + +int +odph_cuckoo_hash_lookup_with_hash_data( + const odph_cuckoo_hash_tbl_t *h, + const void *key, uint32_t sig, void **data) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return cuckoo_hash_lookup_with_hash(h, key, sig, data); +} + +int +odph_cuckoo_hash_lookup_data( + const odph_cuckoo_hash_tbl_t *h, + const void *key, void **data) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return cuckoo_hash_lookup_with_hash( + h, key, hash(h, key), data); +} + +static inline int32_t +cuckoo_hash_del_key_with_hash( + const odph_cuckoo_hash_tbl_t *h, + const void *key, uint32_t sig) +{ + uint32_t bucket_idx; + uint32_t alt_hash; + unsigned i; + struct cuckoo_hash_bucket *bkt; + struct cuckoo_hash_key *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 < HASH_BUCKET_ENTRIES; i++) { + if ( + bkt->signatures[i].current == sig && + bkt->signatures[i].sig != NULL_SIGNATURE) { + k = (struct cuckoo_hash_key *)((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) { + bkt->signatures[i].sig = NULL_SIGNATURE; + odph_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 = hash_secondary(sig); + bucket_idx = alt_hash & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in secondary location */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + if ( + bkt->signatures[i].current == alt_hash && + bkt->signatures[i].sig != NULL_SIGNATURE) { + k = (struct cuckoo_hash_key *)((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) { + bkt->signatures[i].sig = NULL_SIGNATURE; + odph_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 +odph_cuckoo_hash_del_key_with_hash( + const odph_cuckoo_hash_tbl_t *h, + const void *key, uint32_t sig) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return cuckoo_hash_del_key_with_hash(h, key, sig); +} + +int32_t +odph_cuckoo_hash_del_key(const odph_cuckoo_hash_tbl_t *h, const void *key) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return cuckoo_hash_del_key_with_hash( + h, key, hash(h, key)); +} + +/* Lookup bulk stage 0: Prefetch input key */ +static inline void +lookup_stage0( + unsigned *idx, uint64_t *lookup_mask, + const void * const *keys) +{ + *idx = __builtin_ctzl(*lookup_mask); + if (*lookup_mask == 0) + *idx = 0; + + __builtin_prefetch((const void *)(uintptr_t)(keys[*idx]), 0, 3); + *lookup_mask &= ~(1llu << *idx); +} + +/* + * Lookup bulk stage 1: Calculate primary/secondary hashes + * and prefetch primary/secondary buckets + */ +static inline void +lookup_stage1( + unsigned idx, uint32_t *prim_hash, uint32_t *sec_hash, + const struct cuckoo_hash_bucket **primary_bkt, + const struct cuckoo_hash_bucket **secondary_bkt, + uint32_t *hash_vals, const void * const *keys, + const odph_cuckoo_hash_tbl_t *h) +{ + *prim_hash = hash(h, keys[idx]); + hash_vals[idx] = *prim_hash; + *sec_hash = hash_secondary(*prim_hash); + + *primary_bkt = &h->buckets[*prim_hash & h->bucket_bitmask]; + *secondary_bkt = &h->buckets[*sec_hash & h->bucket_bitmask]; + + __builtin_prefetch((const void *)(uintptr_t)(*primary_bkt), 0, 3); + __builtin_prefetch((const void *)(uintptr_t)(*secondary_bkt), 0, 3); +} + +/* + * Lookup bulk stage 2: Search for match hashes in primary/secondary locations + * and prefetch first key slot + */ +static inline void +lookup_stage2( + unsigned idx, uint32_t prim_hash, uint32_t sec_hash, + const struct cuckoo_hash_bucket *prim_bkt, + const struct cuckoo_hash_bucket *sec_bkt, + const struct cuckoo_hash_key **key_slot, int32_t *positions, + uint64_t *extra_hits_mask, const void *keys, + const odph_cuckoo_hash_tbl_t *h) +{ + unsigned prim_hash_matches, sec_hash_matches, key_idx, i; + unsigned total_hash_matches; + + prim_hash_matches = 1 << HASH_BUCKET_ENTRIES; + sec_hash_matches = 1 << HASH_BUCKET_ENTRIES; + for (i = 0; i < 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 << + (HASH_BUCKET_ENTRIES + 1))); + *key_slot = (const struct cuckoo_hash_key *)((const char *)keys + + key_idx * h->key_entry_size); + + __builtin_prefetch((const void *)(uintptr_t)(*key_slot), 0, 3); + /* + * Return index where key is stored, + * substracting the first dummy index + */ + positions[idx] = (key_idx - 1); + + *extra_hits_mask |= (uint64_t) + (__builtin_popcount(total_hash_matches) > 3) << idx; +} + +/* Lookup bulk stage 3: Check if key matches, update hit mask and return data */ +static inline void +lookup_stage3( + unsigned idx, const struct cuckoo_hash_key *key_slot, + const void * const *keys, + void *data[], uint64_t *hits, const odph_cuckoo_hash_tbl_t *h) +{ + unsigned hit; + + hit = !h->hash_cmp_eq(key_slot->key, keys[idx], h->key_len); + if (data != NULL) + data[idx] = key_slot->pdata; + + *hits |= (uint64_t)(hit) << idx; +} + +static inline void +cuckoo_hash_lookup_bulk( + const odph_cuckoo_hash_tbl_t *h, const void **keys, + uint32_t num_keys, int32_t *positions, + uint64_t *hit_mask, void *data[]) +{ + uint64_t hits = 0; + uint64_t extra_hits_mask = 0; + uint64_t lookup_mask, miss_mask; + unsigned idx; + const void *key_store = h->key_store; + int ret; + uint32_t hash_vals[HASH_LOOKUP_BULK_MAX]; + + unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31; + const struct cuckoo_hash_bucket *primary_bkt10, *primary_bkt11; + const struct cuckoo_hash_bucket *secondary_bkt10, *secondary_bkt11; + const struct cuckoo_hash_bucket *primary_bkt20, *primary_bkt21; + const struct cuckoo_hash_bucket *secondary_bkt20, *secondary_bkt21; + const struct cuckoo_hash_key *k_slot20, *k_slot21, *k_slot30, *k_slot31; + uint32_t primary_hash10, primary_hash11; + uint32_t secondary_hash10, secondary_hash11; + uint32_t primary_hash20, primary_hash21; + uint32_t secondary_hash20, secondary_hash21; + + lookup_mask = (uint64_t)-1 >> (64 - num_keys); + miss_mask = lookup_mask; + + lookup_stage0(&idx00, &lookup_mask, keys); + lookup_stage0(&idx01, &lookup_mask, keys); + + idx10 = idx00, idx11 = idx01; + + lookup_stage0(&idx00, &lookup_mask, keys); + lookup_stage0(&idx01, &lookup_mask, keys); + lookup_stage1( + idx10, &primary_hash10, &secondary_hash10, + &primary_bkt10, &secondary_bkt10, hash_vals, keys, h); + lookup_stage1( + idx11, &primary_hash11, &secondary_hash11, + &primary_bkt11, &secondary_bkt11, hash_vals, keys, h); + + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + idx10 = idx00, idx11 = idx01; + + lookup_stage0(&idx00, &lookup_mask, keys); + lookup_stage0(&idx01, &lookup_mask, keys); + lookup_stage1( + idx10, &primary_hash10, &secondary_hash10, + &primary_bkt10, &secondary_bkt10, hash_vals, keys, h); + lookup_stage1( + idx11, &primary_hash11, &secondary_hash11, + &primary_bkt11, &secondary_bkt11, hash_vals, keys, h); + lookup_stage2( + idx20, primary_hash20, secondary_hash20, primary_bkt20, + secondary_bkt20, &k_slot20, positions, &extra_hits_mask, + key_store, h); + lookup_stage2( + idx21, primary_hash21, secondary_hash21, primary_bkt21, + secondary_bkt21, &k_slot21, positions, &extra_hits_mask, + key_store, h); + + while (lookup_mask) { + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + idx10 = idx00, idx11 = idx01; + + lookup_stage0(&idx00, &lookup_mask, keys); + lookup_stage0(&idx01, &lookup_mask, keys); + lookup_stage1( + idx10, &primary_hash10, &secondary_hash10, + &primary_bkt10, &secondary_bkt10, hash_vals, + keys, h); + lookup_stage1( + idx11, &primary_hash11, &secondary_hash11, + &primary_bkt11, &secondary_bkt11, hash_vals, + keys, h); + lookup_stage2( + idx20, primary_hash20, secondary_hash20, + primary_bkt20, secondary_bkt20, &k_slot20, + positions, &extra_hits_mask, key_store, h); + lookup_stage2( + idx21, primary_hash21, secondary_hash21, + primary_bkt21, secondary_bkt21, &k_slot21, + positions, &extra_hits_mask, key_store, h); + lookup_stage3(idx30, k_slot30, keys, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, &hits, h); + } + + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + idx10 = idx00, idx11 = idx01; + + lookup_stage1( + idx10, &primary_hash10, &secondary_hash10, + &primary_bkt10, &secondary_bkt10, hash_vals, keys, h); + lookup_stage1( + idx11, &primary_hash11, &secondary_hash11, + &primary_bkt11, &secondary_bkt11, hash_vals, keys, h); + lookup_stage2( + idx20, primary_hash20, secondary_hash20, primary_bkt20, + secondary_bkt20, &k_slot20, positions, &extra_hits_mask, + key_store, h); + lookup_stage2( + idx21, primary_hash21, secondary_hash21, primary_bkt21, + secondary_bkt21, &k_slot21, positions, &extra_hits_mask, + key_store, h); + lookup_stage3(idx30, k_slot30, keys, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, &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, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, &hits, h); + + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + + lookup_stage3(idx30, k_slot30, keys, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, &hits, h); + + /* ignore any items we have already found */ + extra_hits_mask &= ~hits; + + if (odp_unlikely(extra_hits_mask)) { + /* run a single search for each remaining item */ + do { + idx = __builtin_ctzl(extra_hits_mask); + if (data != NULL) { + ret = odph_cuckoo_hash_lookup_with_hash_data( + h, keys[idx], hash_vals[idx], + &data[idx]); + if (ret >= 0) + hits |= 1ULL << idx; + } else { + positions[idx] = + odph_cuckoo_hash_lookup_with_hash( + h, keys[idx], hash_vals[idx]); + if (positions[idx] >= 0) + hits |= 1llu << idx; + } + extra_hits_mask &= ~(1llu << idx); + } while (extra_hits_mask); + } + + miss_mask &= ~hits; + if (odp_unlikely(miss_mask)) { + do { + idx = __builtin_ctzl(miss_mask); + positions[idx] = -ENOENT; + miss_mask &= ~(1llu << idx); + } while (miss_mask); + } + + if (hit_mask != NULL) + *hit_mask = hits; +} + +int +odph_cuckoo_hash_lookup_bulk( + const odph_cuckoo_hash_tbl_t *h, const void **keys, + uint32_t num_keys, int32_t *positions) +{ + RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || + (num_keys > HASH_LOOKUP_BULK_MAX) || + (positions == NULL)), -EINVAL); + + cuckoo_hash_lookup_bulk( + h, keys, num_keys, positions, NULL, NULL); + return 0; +} + +int +odph_cuckoo_hash_lookup_bulk_data( + const odph_cuckoo_hash_tbl_t *h, const void **keys, + uint32_t num_keys, uint64_t *hit_mask, void *data[]) +{ + RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || + (num_keys > HASH_LOOKUP_BULK_MAX) || + (hit_mask == NULL)), -EINVAL); + + int32_t positions[num_keys]; + + cuckoo_hash_lookup_bulk( + h, keys, num_keys, positions, hit_mask, data); + + /* Return number of hits */ + return __builtin_popcountl(*hit_mask); +} + +int32_t +odph_cuckoo_hash_iterate( + const odph_cuckoo_hash_tbl_t *h, const void **key, + void **data, uint32_t *next) +{ + uint32_t bucket_idx, idx, position; + struct cuckoo_hash_key *next_key; + + RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL); + + const uint32_t total_entries = + h->num_buckets * HASH_BUCKET_ENTRIES; + /* Out of bounds */ + if (*next >= total_entries) + return -ENOENT; + + /* Calculate bucket and index of current iterator */ + bucket_idx = *next / HASH_BUCKET_ENTRIES; + idx = *next % HASH_BUCKET_ENTRIES; + + /* If current position is empty, go to the next one */ + while (h->buckets[bucket_idx].signatures[idx].sig == NULL_SIGNATURE) { + (*next)++; + /* End of table */ + if (*next == total_entries) + return -ENOENT; + bucket_idx = *next / HASH_BUCKET_ENTRIES; + idx = *next % HASH_BUCKET_ENTRIES; + } + + /* Get position of entry in key table */ + position = h->buckets[bucket_idx].key_idx[idx]; + next_key = (struct cuckoo_hash_key *)((char *)h->key_store + + position * h->key_entry_size); + /* Return key and data */ + *key = next_key->key; + *data = next_key->pdata; + + /* Increment iterator */ + (*next)++; + + return (position - 1); +} diff --git a/helper/include/odp/helper/cuckoo_hash.h b/helper/include/odp/helper/cuckoo_hash.h new file mode 100644 index 0000000..f21b8a2 --- /dev/null +++ b/helper/include/odp/helper/cuckoo_hash.h @@ -0,0 +1,435 @@ +/* Copyright (c) 2015, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +/*- + * 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. + */ + +#ifndef ODPH_CUCKOO_HASH_H_ +#define ODPH_CUCKOO_HASH_H_ + +#include <odp/shared_memory.h> +#include <odp/helper/ring.h> +#include <odp/hash.h> +#include <stdint.h> + +/** + * @file + * + * ODP Cuckoo Hash Table Implementation + */ + +#ifdef __cplusplus +extern "C" { +#endif + +/** Maximum number of characters in hash name.*/ +#define ODPH_CUCKOO_HASH_NAMESIZE 32 + +/** A hash table structure. */ +typedef struct odph_cuckoo_hash_tbl { + /**< Name of the hash. */ + char name[ODPH_CUCKOO_HASH_NAMESIZE]; + /**< Total table entries. */ + uint32_t entries; + /**< Number of buckets in table. */ + uint32_t num_buckets; + /**< Length of hash key. */ + uint32_t key_len; + /**< Function used to calculate hash. */ + odp_hash_function hash_func; + /**< Init value used by hash_func. */ + uint32_t hash_func_init_val; + /**< Function used to compare keys. */ + odp_hash_cmp_eq_t hash_cmp_eq; + /**< Bitmask for getting bucket index from hash signature. */ + uint32_t bucket_bitmask; + /**< Size of each key entry. */ + uint32_t key_entry_size; + /**< Ring that stores all indexes of the free slots in the key table */ + odph_ring_t *free_slots; + /**< Table storing all keys and data */ + void *key_store; + /** Table with buckets storing all the hash values and key indexes + to the key table*/ + struct cuckoo_hash_bucket *buckets; + /** memory used to store keys*/ + odp_shm_t shm_key; + /** memory used to store buckets*/ + odp_shm_t shm_bucket; +} odph_cuckoo_hash_tbl_t ODP_ALIGNED_CACHE; + +/** + * Parameters used when creating the cuckoo hash table. + */ +typedef struct odph_cuckoo_hash_param_t { + /**< Name of the hash table. */ + const char *name; + /**< Total hash table entries. */ + uint32_t entries; + /**< Length of hash key. */ + uint32_t key_len; + /**< Primary Hash function used to calculate hash. */ + odp_hash_function hash_func; + /**< Init value used by hash_func. */ + uint32_t hash_func_init_val; + /**< Indicate if additional parameters are present. */ + uint8_t extra_flag; +} odph_cuckoo_hash_param_t; + +/** + * Create a new cuckoo hash table. + * + * @param ht + * hash table if successful + * @param params + * Parameters used to create and initialise the hash table. + * @return + * 0 on success + * negative value on errors including: + * - -EINVAL - invalid parameter passed to function + * - -EEXIST - a hash table with the same name already exists + * - -ENOMEM - no appropriate memory area found in which to create memzone + */ +int +odph_cuckoo_hash_create(odph_cuckoo_hash_tbl_t **ht, + const odph_cuckoo_hash_param_t *params); + +/** + * Find an existing hash table object and return a pointer to it. + * + * @param name + * Name of the hash table as passed to odph_hash_create() + * @return + * Pointer to hash table or NULL if object not found + */ +odph_cuckoo_hash_tbl_t * +odph_cuckoo_hash_find_existing(const char *name); + +/** + * De-allocate all memory used by hash table. + * @param h + * Hash table to free + */ +void +odph_cuckoo_hash_destroy(odph_cuckoo_hash_tbl_t *h); + +/** + * Reset all hash structure, by zeroing all entries + * @param h + * Hash table to reset + */ +void +odph_cuckoo_hash_reset(odph_cuckoo_hash_tbl_t *h); + +/** + * Add a key-value pair to an existing hash table. + * This operation is not multi-thread safe + * and should only be called from one thread. + * + * @param h + * Hash table to add the key to. + * @param key + * Key to add to the hash table. + * @param data + * Data to add to the hash table. + * @return + * - 0 if added successfully + * - -EINVAL if the parameters are invalid. + * - -ENOSPC if there is no space in the hash for this key. + */ +int +odph_cuckoo_hash_add_key_data(const odph_cuckoo_hash_tbl_t *h, + const void *key, void *data); + +/** + * Add a key-value pair with a pre-computed hash value + * to an existing hash table. + * This operation is not multi-thread safe + * and should only be called from one thread. + * + * @param h + * Hash table to add the key to. + * @param key + * Key to add to the hash table. + * @param sig + * Precomputed hash value for 'key' + * @param data + * Data to add to the hash table. + * @return + * - 0 if added successfully + * - -EINVAL if the parameters are invalid. + * - -ENOSPC if there is no space in the hash for this key. + */ +int32_t +odph_cuckoo_hash_add_key_with_hash_data( + const odph_cuckoo_hash_tbl_t *h, const void *key, + uint32_t sig, void *data); + +/** + * 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 + * Hash table to add the key to. + * @param key + * Key to add to the hash table. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOSPC if there is no space in the hash for this key. + * - A positive value that can be used by the caller as an offset into an + * array of user data. This value is unique for this key. + */ +int32_t +odph_cuckoo_hash_add_key(const odph_cuckoo_hash_tbl_t *h, const void *key); + +/** + * 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 + * Hash table to add the key to. + * @param key + * Key to add to the hash table. + * @param sig + * Precomputed hash value for 'key'. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOSPC if there is no space in the hash for this key. + * - A positive value that can be used by the caller as an offset into an + * array of user data. This value is unique for this key. + */ +int32_t +odph_cuckoo_hash_add_key_with_hash( + const odph_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig); + +/** + * Remove a key from an existing hash table. + * This operation is not multi-thread safe + * and should only be called from one thread. + * + * @param h + * Hash table to remove the key from. + * @param key + * Key to remove from the hash table. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOENT if the key is not found. + * - A positive value that can be used by the caller as an offset into an + * array of user data. This value is unique for this key, and is the same + * value that was returned when the key was added. + */ +int32_t +odph_cuckoo_hash_del_key(const odph_cuckoo_hash_tbl_t *h, const void *key); + +/** + * Remove a key from an existing hash table. + * This operation is not multi-thread safe + * and should only be called from one thread. + * + * @param h + * Hash table to remove the key from. + * @param key + * Key to remove from the hash table. + * @param sig + * Precomputed hash value for 'key'. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOENT if the key is not found. + * - A positive value that can be used by the caller as an offset into an + * array of user data. This value is unique for this key, and is the same + * value that was returned when the key was added. + */ +int32_t +odph_cuckoo_hash_del_key_with_hash( + const odph_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig); + +/** + * Find a key-value pair in the hash table. + * This operation is multi-thread safe. + * + * @param h + * Hash table to look in. + * @param key + * Key to find. + * @param data + * Output with pointer to data returned from the hash table. + * @return + * 0 if successful lookup + * - EINVAL if the parameters are invalid. + * - ENOENT if the key is not found. + */ +int +odph_cukoo_hash_lookup_data( + const odph_cuckoo_hash_tbl_t *h, const void *key, void **data); + +/** + * Find a key-value pair with a pre-computed hash value + * to an existing hash table. + * This operation is multi-thread safe. + * + * @param h + * Hash table to look in. + * @param key + * Key to find. + * @param sig + * Precomputed hash value for 'key' + * @param data + * Output with pointer to data returned from the hash table. + * @return + * 0 if successful lookup + * - EINVAL if the parameters are invalid. + * - ENOENT if the key is not found. + */ +int +odph_cuckoo_hash_lookup_with_hash_data( + const odph_cuckoo_hash_tbl_t *h, const void *key, + uint32_t sig, void **data); + +/** + * 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. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOENT if the key is not found. + * - A positive value that can be used by the caller as an offset into an + * array of user data. This value is unique for this key, and is the same + * value that was returned when the key was added. + */ +int32_t +odph_cuckoo_hash_lookup(const odph_cuckoo_hash_tbl_t *h, const void *key); + +/** + * 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 remove from the hash table. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOENT if the key is not found. + * - A positive value that can be used by the caller as an offset into an + * array of user data. This value is unique for this key, and is the same + * value that was returned when the key was added. + */ +int32_t +odph_cuckoo_hash_lookup_with_hash( + const odph_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig); + +/** + * Find multiple keys in the hash table. + * This operation is multi-thread safe. + * + * @param h + * Hash table to look in. + * @param keys + * A pointer to a list of keys to look for. + * @param num_keys + * How many keys are in the keys list (less than ODPH_HASH_LOOKUP_BULK_MAX). + * @param hit_mask + * Output containing a bitmask with all successful lookups. + * @param data + * Output containing array of data returned from all the successful lookups. + * @return + * -EINVAL if there's an error, otherwise number of successful lookups. + */ +int +odph_cuckoo_hash_lookup_bulk_data( + const odph_cuckoo_hash_tbl_t *h, const void **keys, + uint32_t num_keys, uint64_t *hit_mask, void *data[]); + +/** + * Find multiple keys in the hash table. + * This operation is multi-thread safe. + * + * @param h + * Hash table to look in. + * @param keys + * A pointer to a list of keys to look for. + * @param num_keys + * How many keys are in the keys list (less than HASH_LOOKUP_BULK_MAX). + * @param positions + * Output containing a list of values, corresponding to the list of keys that + * can be used by the caller as an offset into an array of user data. These + * values are unique for each key, and are the same values that were returned + * when each key was added. If a key in the list was not found, then -ENOENT + * will be the value. + * @return + * -EINVAL if there's an error, otherwise 0. + */ +int +odph_cuckoo_hash_lookup_bulk( + const odph_cuckoo_hash_tbl_t *h, const void **keys, + uint32_t num_keys, int32_t *positions); + +/** + * Iterate through the hash table, returning key-value pairs. + * + * @param h + * Hash table to iterate + * @param key + * Output containing the key where current iterator + * was pointing at + * @param data + * Output containing the data associated with key. + * Returns NULL if data was not stored. + * @param next + * Pointer to iterator. Should be 0 to start iterating the hash table. + * Iterator is incremented after each call of this function. + * @return + * Position where key was stored, if successful. + * - -EINVAL if the parameters are invalid. + * - -ENOENT if end of the hash table. + */ +int32_t +odph_cuckoo_hash_iterate( + const odph_cuckoo_hash_tbl_t *h, + const void **key, void **data, uint32_t *next); + +#ifdef __cplusplus +} +#endif + +#endif /* ODPH_HASH_H_ */ diff --git a/helper/include/odp/helper/ring.h b/helper/include/odp/helper/ring.h index 65c32ad..3c1a3bf 100644 --- a/helper/include/odp/helper/ring.h +++ b/helper/include/odp/helper/ring.h @@ -132,6 +132,8 @@ typedef struct odph_ring { /** @private Flags supplied at creation. */ int flags; + odp_shm_t shm; + /** @private Producer */ struct prod { uint32_t watermark; /* Maximum items */ @@ -194,6 +196,18 @@ typedef struct odph_ring { odph_ring_t *odph_ring_create(const char *name, unsigned count, unsigned flags); +/** + * Free a ring in memory. + * + * This function uses odp_shm_reserve() to allocate memory. Its size is + * set to *count*, which must be a power of two. Water marking is + * disabled by default. Note that the real usable ring size is count-1 + * instead of count. + * + * @param r + * The pointer to the ring need to be free. + */ +void odph_ring_free(odph_ring_t *r); /** * Change the high water mark. @@ -372,6 +386,21 @@ int odph_ring_sp_enqueue_bulk(odph_ring_t *r, void * const *obj_table, unsigned n); /** + * Enqueue one object on a ring (NOT multi-producers safe). + * + * @param r + * A pointer to the ring structure. + * @param obj + * A pointer to the object to be added. + * @return + * - 0: Success; objects enqueued. + * - -EDQUOT: Quota exceeded. The objects have been enqueued, but the + * high water mark is exceeded. + * - -ENOBUFS: Not enough room in the ring to enqueue; no object is enqueued. + */ +int odph_ring_sp_enqueue(odph_ring_t *r, void *obj); + +/** * Dequeue several objects from a ring (multi-consumers safe). * * This function uses a "compare and set" instruction to move the @@ -408,6 +437,20 @@ int odph_ring_mc_dequeue_bulk(odph_ring_t *r, void **obj_table, unsigned n); int odph_ring_sc_dequeue_bulk(odph_ring_t *r, void **obj_table, unsigned n); /** + * Dequeue one object from a ring (NOT multi-consumers safe). + * + * @param r + * A pointer to the ring structure. + * @param obj_p + * A pointer to a void * pointer (object) that will be filled. + * @return + * - 0: Success; objects dequeued. + * - -ENOENT: Not enough entries in the ring to dequeue, no object is + * dequeued. + */ +int odph_ring_sc_dequeue(odph_ring_t *r, void *obj); + +/** * Test if a ring is full. * * @param r diff --git a/helper/ring.c b/helper/ring.c index 3122173..afd7244 100644 --- a/helper/ring.c +++ b/helper/ring.c @@ -174,12 +174,18 @@ odph_ring_create(const char *name, unsigned count, unsigned flags) /* reserve a memory zone for this ring.*/ shm = odp_shm_reserve(ring_name, ring_size, ODP_CACHE_LINE_SIZE, 0); + if (shm == ODP_SHM_INVALID) { + ODPH_ERR("shm allocation failed for ring %s\n", ring_name); + return NULL; + } + r = odp_shm_addr(shm); if (r != NULL) { /* init the ring structure */ snprintf(r->name, sizeof(r->name), "%s", name); r->flags = flags; + r->shm = shm; r->prod.watermark = count; r->prod.sp_enqueue = !!(flags & ODPH_RING_F_SP_ENQ); r->cons.sc_dequeue = !!(flags & ODPH_RING_F_SC_DEQ); @@ -201,6 +207,18 @@ odph_ring_create(const char *name, unsigned count, unsigned flags) return r; } +/* free a ring */ +void +odph_ring_free(odph_ring_t *r) +{ + odp_rwlock_write_lock(&qlock); + TAILQ_REMOVE(&odp_ring_list, r, next); + odp_rwlock_write_unlock(&qlock); + + if (r->shm != ODP_SHM_INVALID) + odp_shm_free(r->shm); +} + /* * change the high water mark. If *count* is 0, water marking is * disabled @@ -471,6 +489,11 @@ int odph_ring_sp_enqueue_bulk(odph_ring_t *r, void * const *obj_table, ODPH_RING_QUEUE_FIXED); } +int odph_ring_sp_enqueue(odph_ring_t *r, void *obj) +{ + return odph_ring_sp_enqueue_bulk(r, &obj, 1); +} + /** * Dequeue several objects from a ring (multi-consumers safe). */ @@ -489,6 +512,11 @@ int odph_ring_sc_dequeue_bulk(odph_ring_t *r, void **obj_table, unsigned n) ODPH_RING_QUEUE_FIXED); } +int odph_ring_sc_dequeue(odph_ring_t *r, void *obj) +{ + return odph_ring_sc_dequeue_bulk(r, &obj, 1); +} + /** * Test if a ring is full. */ diff --git a/helper/test/Makefile.am b/helper/test/Makefile.am index d6820e1..e358a87 100644 --- a/helper/test/Makefile.am +++ b/helper/test/Makefile.am @@ -9,7 +9,8 @@ EXECUTABLES = odp_chksum$(EXEEXT) \ odp_thread$(EXEEXT) \ odp_process$(EXEEXT)\ odph_pause$(EXEEXT)\ - odp_table$(EXEEXT) + odp_table$(EXEEXT)\ + odp_cuckoo_hash$(EXEEXT) COMPILE_ONLY = @@ -31,3 +32,4 @@ dist_odp_process_SOURCES = odp_process.c odp_process_LDADD = $(LIB)/libodphelper.la $(LIB)/libodp.la odph_pause_SOURCES = odph_pause.c dist_odp_table_SOURCES = odp_table.c +dist_odp_cuckoo_hash_SOURCES = odp_cuckoo_hash.c diff --git a/helper/test/odp_cuckoo_hash.c b/helper/test/odp_cuckoo_hash.c new file mode 100644 index 0000000..c51ba0a --- /dev/null +++ b/helper/test/odp_cuckoo_hash.c @@ -0,0 +1,779 @@ +/* Copyright (c) 2015, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +/*- + * 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 <stdio.h> +#include <stdint.h> +#include <string.h> +#include <stdlib.h> +#include <stdarg.h> +#include <errno.h> +#include <sys/queue.h> +#include <sys/time.h> +#include <time.h> + +#include <test_debug.h> +#include <odp.h> +#include <odp/helper/ring.h> +#include <odp/helper/cuckoo_hash.h> + +/******************************************************************************* + * Hash function performance test configuration section. Each performance test + * will be performed HASHTEST_ITERATIONS times. + * + * The five arrays below control what tests are performed. Every combination + * from the array entries is tested. + */ +odp_hash_function hashtest_funcs[] = {odp_hash_crc32c}; +/******************************************************************************/ + +/* + * Check condition and return an error if true. Assumes that "handle" is the + * name of the hash structure pointer to be freed. + */ +#define RETURN_IF_ERROR(cond, str, ...) do { \ + if (cond) { \ + printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ + if (handle) \ + odph_cuckoo_hash_destroy(handle); \ + return -1; \ + } \ +} while (0) + +/* 5-tuple key type */ +struct flow_key { + uint32_t ip_src; + uint32_t ip_dst; + uint16_t port_src; + uint16_t port_dst; + uint8_t proto; +} __packed; + +/* + * Print out result of unit test hash operation. + */ +static void print_key_info( + const char *msg, const struct flow_key *key, + int32_t pos) +{ + const uint8_t *p = (const uint8_t *)key; + unsigned i; + + printf("%s key:0x", msg); + for (i = 0; i < sizeof(struct flow_key); i++) + printf("%02X", p[i]); + printf(" @ pos %d\n", pos); +} + +static double get_time_diff(struct timeval *start, struct timeval *end) +{ + int sec = end->tv_sec - start->tv_sec; + int usec = end->tv_usec - start->tv_usec; + + if (usec < 0) { + sec--; + usec += 1000000; + } + double diff = sec + (double)usec / 1000000; + + return diff; +} + +/** Create IPv4 address */ +#define IPv4(a, b, c, d) ((uint32_t)(((a) & 0xff) << 24) | \ + (((b) & 0xff) << 16) | \ + (((c) & 0xff) << 8) | \ + ((d) & 0xff)) + +/* Keys used by unit test functions */ +static struct flow_key keys[5] = { { + .ip_src = IPv4(0x03, 0x02, 0x01, 0x00), + .ip_dst = IPv4(0x07, 0x06, 0x05, 0x04), + .port_src = 0x0908, + .port_dst = 0x0b0a, + .proto = 0x0c, +}, { + .ip_src = IPv4(0x13, 0x12, 0x11, 0x10), + .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14), + .port_src = 0x1918, + .port_dst = 0x1b1a, + .proto = 0x1c, +}, { + .ip_src = IPv4(0x23, 0x22, 0x21, 0x20), + .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24), + .port_src = 0x2928, + .port_dst = 0x2b2a, + .proto = 0x2c, +}, { + .ip_src = IPv4(0x33, 0x32, 0x31, 0x30), + .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34), + .port_src = 0x3938, + .port_dst = 0x3b3a, + .proto = 0x3c, +}, { + .ip_src = IPv4(0x43, 0x42, 0x41, 0x40), + .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44), + .port_src = 0x4948, + .port_dst = 0x4b4a, + .proto = 0x4c, +} }; + +/* Parameters used for hash table in unit test functions. Name set later. */ +static odph_cuckoo_hash_param_t ut_params = { + .entries = 64, + .key_len = sizeof(struct flow_key), /* 13 */ + .hash_func = odp_hash_crc32c, + .hash_func_init_val = 0, +}; + +#define CRC32_ITERATIONS 1048576 +#define CRC32_DWORDS 64 + +static uint32_t hash(const odph_cuckoo_hash_tbl_t *h, const void *key) +{ + /* calc hash result by key */ + return h->hash_func(key, h->key_len, h->hash_func_init_val); +} + +/* + * Basic sequence of operations for a single key: + * - add + * - lookup (hit) + * - delete + * - lookup (miss) + */ +static int test_add_delete(void) +{ + odph_cuckoo_hash_tbl_t *handle; + /* test with standard add/lookup/delete functions */ + int pos0, expected_pos0; + int ret; + + ut_params.name = "test1"; + ret = odph_cuckoo_hash_create(&handle, &ut_params); + RETURN_IF_ERROR(ret < 0, "cuckoo hash creation failed"); + + pos0 = odph_cuckoo_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos0); + RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0); + expected_pos0 = pos0; + + pos0 = odph_cuckoo_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expected_pos0, + "failed to find key (pos0=%d)", pos0); + + pos0 = odph_cuckoo_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expected_pos0, + "failed to delete key (pos0=%d)", pos0); + + pos0 = odph_cuckoo_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found key after deleting! (pos0=%d)", pos0); + + odph_cuckoo_hash_destroy(handle); + + /* repeat test with precomputed hash functions */ + uint32_t hash_value; + int pos1, expected_pos1; + + ret = odph_cuckoo_hash_create(&handle, &ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + hash_value = hash(handle, &keys[0]); + pos1 = odph_cuckoo_hash_add_key_with_hash(handle, &keys[0], hash_value); + print_key_info("Add", &keys[0], pos1); + RETURN_IF_ERROR(pos1 < 0, "failed to add key (pos1=%d)", pos1); + expected_pos1 = pos1; + + pos1 = odph_cuckoo_hash_lookup_with_hash(handle, &keys[0], hash_value); + print_key_info("Lkp", &keys[0], pos1); + RETURN_IF_ERROR(pos1 != expected_pos1, + "failed to find key (pos1=%d)", pos1); + + pos1 = odph_cuckoo_hash_del_key_with_hash(handle, &keys[0], hash_value); + print_key_info("Del", &keys[0], pos1); + RETURN_IF_ERROR(pos1 != expected_pos1, + "failed to delete key (pos1=%d)", pos1); + + pos1 = odph_cuckoo_hash_lookup_with_hash(handle, &keys[0], hash_value); + print_key_info("Lkp", &keys[0], pos1); + RETURN_IF_ERROR(pos1 != -ENOENT, + "fail: found key after deleting! (pos1=%d)", pos1); + + odph_cuckoo_hash_destroy(handle); + + return 0; +} + +/* + * Sequence of operations for a single key: + * - delete: miss + * - add + * - lookup: hit + * - add: update + * - lookup: hit (updated data) + * - delete: hit + * - delete: miss + * - lookup: miss + */ +static int test_add_update_delete(void) +{ + odph_cuckoo_hash_tbl_t *handle; + int pos0, expected_pos0; + int ret; + + ut_params.name = "test2"; + ret = odph_cuckoo_hash_create(&handle, &ut_params); + RETURN_IF_ERROR(ret < 0, "hash creation failed"); + + pos0 = odph_cuckoo_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found non-existent key (pos0=%d)", pos0); + + pos0 = odph_cuckoo_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos0); + RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0); + expected_pos0 = pos0; + + pos0 = odph_cuckoo_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expected_pos0, + "failed to find key (pos0=%d)", pos0); + + pos0 = odph_cuckoo_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expected_pos0, + "failed to re-add key (pos0=%d)", pos0); + + pos0 = odph_cuckoo_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expected_pos0, + "failed to find key (pos0=%d)", pos0); + + pos0 = odph_cuckoo_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expected_pos0, + "failed to delete key (pos0=%d)", pos0); + + pos0 = odph_cuckoo_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: deleted already deleted key (pos0=%d)", pos0); + + pos0 = odph_cuckoo_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found key after deleting! (pos0=%d)", pos0); + + odph_cuckoo_hash_destroy(handle); + return 0; +} + +/* + * Sequence of operations for find existing hash table + * + * - create table + * - find existing table: hit + * - find non-existing table: miss + * + */ +static int test_hash_find_existing(void) +{ + int ret; + odph_cuckoo_hash_tbl_t *handle = NULL, *result = NULL; + + /* Create hash table. */ + ut_params.name = "hash_find_existing"; + ret = odph_cuckoo_hash_create(&handle, &ut_params); + RETURN_IF_ERROR(ret < 0, "hash creation failed"); + + /* Try to find existing hash table */ + result = odph_cuckoo_hash_find_existing("hash_find_existing"); + RETURN_IF_ERROR(result != handle, "could not find existing hash table"); + + /* Try to find non-existing hash table */ + result = odph_cuckoo_hash_find_existing("hash_find_non_existing"); + RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist"); + + /* Cleanup. */ + odph_cuckoo_hash_destroy(handle); + + return 0; +} + +/* + * Sequence of operations for 5 keys + * - add keys + * - lookup keys: hit + * - add keys (update) + * - lookup keys: hit (updated data) + * - delete keys : hit + * - lookup keys: miss + */ +static int test_five_keys(void) +{ + odph_cuckoo_hash_tbl_t *handle; + const void *key_array[5] = {0}; + int pos[5]; + int expected_pos[5]; + unsigned i; + int ret; + + ut_params.name = "test3"; + ret = odph_cuckoo_hash_create(&handle, &ut_params); + RETURN_IF_ERROR(ret < 0, "hash creation failed"); + + /* Add */ + for (i = 0; i < 5; i++) { + pos[i] = odph_cuckoo_hash_add_key(handle, &keys[i]); + print_key_info("Add", &keys[i], pos[i]); + RETURN_IF_ERROR(pos[i] < 0, + "failed to add key (pos[%u]=%d)", i, pos[i]); + expected_pos[i] = pos[i]; + } + + /* Lookup */ + for (i = 0; i < 5; i++) + key_array[i] = &keys[i]; + + ret = odph_cuckoo_hash_lookup_bulk(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] != expected_pos[i], + "failed to find key (pos[%u]=%d)", + i, pos[i]); + } + + /* Add - update */ + for (i = 0; i < 5; i++) { + pos[i] = odph_cuckoo_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]); + } + + /* Lookup */ + for (i = 0; i < 5; i++) { + pos[i] = odph_cuckoo_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]); + } + + /* Delete */ + for (i = 0; i < 5; i++) { + pos[i] = odph_cuckoo_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]); + } + + /* Lookup */ + for (i = 0; i < 5; i++) { + pos[i] = odph_cuckoo_hash_lookup(handle, &keys[i]); + print_key_info("Lkp", &keys[i], pos[i]); + RETURN_IF_ERROR( + pos[i] != -ENOENT, + "found non-existent key (pos[%u]=%d)", + i, pos[i]); + } + + /* Lookup multi */ + ret = odph_cuckoo_hash_lookup_bulk(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]); + } + + odph_cuckoo_hash_destroy(handle); + return 0; +} + +#define BUCKET_ENTRIES 4 +#define HASH_ENTRIES_MAX 1048576 +/* + * Do tests for hash creation with bad parameters. + */ +static int test_hash_creation_with_bad_parameters(void) +{ + odph_cuckoo_hash_tbl_t *handle; + odph_cuckoo_hash_param_t params; + int ret; + + ret = odph_cuckoo_hash_create(&handle, NULL); + if (handle != NULL) { + odph_cuckoo_hash_destroy(handle); + printf("Impossible creating hash successfully without any parameter\n"); + return -1; + } + + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "creation_with_bad_parameters_0"; + params.entries = HASH_ENTRIES_MAX + 1; + ret = odph_cuckoo_hash_create(&handle, ¶ms); + if (handle != NULL) { + odph_cuckoo_hash_destroy(handle); + printf("Impossible creating hash successfully with entries in parameter exceeded\n"); + return -1; + } + + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "creation_with_bad_parameters_2"; + params.entries = BUCKET_ENTRIES - 1; + ret = odph_cuckoo_hash_create(&handle, ¶ms); + if (handle != NULL || ret == 0) { + odph_cuckoo_hash_destroy(handle); + printf("Impossible creating hash successfully if entries less than bucket_entries in parameter\n"); + return -1; + } + + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "creation_with_bad_parameters_3"; + params.key_len = 0; + ret = odph_cuckoo_hash_create(&handle, ¶ms); + if (handle != NULL) { + odph_cuckoo_hash_destroy(handle); + printf("Impossible creating hash successfully if key_len in parameter is zero\n"); + return -1; + } + + odph_cuckoo_hash_destroy(handle); + printf("# Test successful. No more errors expected\n"); + + return 0; +} + +/* + * Do tests for hash creation with parameters that look incorrect + * but are actually valid. + */ +static int +test_hash_creation_with_good_parameters(void) +{ + odph_cuckoo_hash_tbl_t *handle, *tmp; + odph_cuckoo_hash_param_t params; + int ret; + + /* create with null hash function - should choose DEFAULT_HASH_FUNC */ + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "same_name"; + params.hash_func = NULL; + ret = odph_cuckoo_hash_create(&handle, ¶ms); + if (handle == NULL || ret < 0) { + printf("Creating hash with null hash_func failed\n"); + return -1; + } + + /* this test is trying to create a hash with the same + * name as previous one. This should return a pointer + * to the hash we previously created. The previous hash + * isn't freed exactly for the purpose of it being in + * the hash list. + */ + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "same_name"; + ret = odph_cuckoo_hash_create(&tmp, ¶ms); + + /* check if the returned handle is actually + equal to the previous hash */ + if (handle != tmp) { + odph_cuckoo_hash_destroy(handle); + odph_cuckoo_hash_destroy(tmp); + printf("Creating hash with existing name was successful\n"); + return -1; + } + + /* try creating hash when there already are hashes in + * the list. The previous hash is not freed to have a + * non-empty hash list. The other hash that's in the + * list is still pointed to by "handle" var. + */ + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "different_name"; + ret = odph_cuckoo_hash_create(&tmp, ¶ms); + if (tmp == NULL) { + odph_cuckoo_hash_destroy(handle); + printf("Creating hash with valid parameters failed\n"); + return -1; + } + + odph_cuckoo_hash_destroy(tmp); + odph_cuckoo_hash_destroy(handle); + + return 0; +} + +#define ITERATIONS 50 +#define NUM_ENTRIES 1024 +#define HASH_KEY_LENGTH_MAX 64 +static int test_hash_iteration(void) +{ + odph_cuckoo_hash_tbl_t *handle; + unsigned i; + uint8_t keys[NUM_ENTRIES][HASH_KEY_LENGTH_MAX]; + const void *next_key; + void *next_data; + void *data[NUM_ENTRIES]; + unsigned added_keys; + uint32_t iter = 0; + int ret = 0; + + ut_params.entries = NUM_ENTRIES; + ut_params.name = "test_hash_iteration"; + ut_params.hash_func = odp_hash_crc32c; + ut_params.key_len = 16; + ret = odph_cuckoo_hash_create(&handle, &ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + /* Add random entries until key cannot be added */ + for (added_keys = 0; added_keys < NUM_ENTRIES; added_keys++) { + data[added_keys] = (void *)((uintptr_t)rand()); + for (i = 0; i < ut_params.key_len; i++) + keys[added_keys][i] = rand() % 255; + ret = odph_cuckoo_hash_add_key_data( + handle, keys[added_keys], data[added_keys]); + if (ret < 0) + break; + } + + /* Iterate through the hash table */ + while (odph_cuckoo_hash_iterate(handle, + &next_key, &next_data, &iter) >= 0) { + /* Search for the key in the list of keys added */ + for (i = 0; i < NUM_ENTRIES; i++) { + if (memcmp(next_key, keys[i], ut_params.key_len) == 0) { + if (next_data != data[i]) { + printf("Data found in the hash table is not"); + printf("The data added with the key\n"); + goto err; + } + added_keys--; + break; + } + } + if (i == NUM_ENTRIES) { + printf("Key found in the hash table was not added\n"); + goto err; + } + } + + /* Check if all keys have been iterated */ + if (added_keys != 0) { + printf("There were still %u keys to iterate\n", added_keys); + goto err; + } + + odph_cuckoo_hash_destroy(handle); + return 0; + +err: + odph_cuckoo_hash_destroy(handle); + return -1; +} + +#define ITERATIONS 50 +#define LOOKUP_TIMES 1000 +/* + * Test to see the average table utilization (entries added/max entries) + * before hitting a random entry that cannot be added + */ +static int test_average_table_utilization(void) +{ + odph_cuckoo_hash_tbl_t *handle; + uint8_t simple_key[HASH_KEY_LENGTH_MAX], + lookup_key[LOOKUP_TIMES][HASH_KEY_LENGTH_MAX]; + unsigned i, j; + unsigned added_keys, average_keys_added = 0; + int ret, pos_arr[LOOKUP_TIMES]; + struct timeval start, end; + const void *bulk_key[LOOKUP_TIMES] = {0}; + double add_time = 0, lookup_time = 0, bulk_time = 0; + + printf("\n# Running test to determine average utilization\n"); + printf(" before adding elements begins to fail\n"); + printf("Measuring performance, please wait"); + fflush(stdout); + ut_params.entries = 1 << 20; + ut_params.name = "test_average_utilization"; + ut_params.hash_func = odp_hash_crc32c; + ret = odph_cuckoo_hash_create(&handle, &ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + for (j = 0; j < ITERATIONS; j++) { + ret = 0; + unsigned added_one = 0; + + gettimeofday(&start, 0); + /* Add random entries until key cannot be added */ + for (added_keys = 0; ret >= 0; added_keys++) { + for (i = 0; i < ut_params.key_len; i++) { + simple_key[i] = rand() % 255; + if (added_one < LOOKUP_TIMES) { + lookup_key[added_one][i] + = simple_key[i]; + } + } + if (added_one < LOOKUP_TIMES) + bulk_key[added_one] = &lookup_key[added_one]; + ret = odph_cuckoo_hash_add_key(handle, simple_key); + added_one++; + } + gettimeofday(&end, 0); + add_time += get_time_diff(&start, &end); + if (ret != -ENOSPC) { + printf("Unexpected error when adding keys\n"); + odph_cuckoo_hash_destroy(handle); + return -1; + } + + gettimeofday(&start, 0); + for (i = 0; i < LOOKUP_TIMES; i++) + pos_arr[i] = odph_cuckoo_hash_lookup(handle, + lookup_key[i]); + gettimeofday(&end, 0); + lookup_time += get_time_diff(&start, &end); + + gettimeofday(&start, 0); + for (i = 0; i < LOOKUP_TIMES / 64; i++) { + odph_cuckoo_hash_lookup_bulk( + handle, &bulk_key[i * 64], + 64, &pos_arr[i * 64]); + } + gettimeofday(&end, 0); + + bulk_time += get_time_diff(&start, &end); + + average_keys_added += added_keys; + + odph_cuckoo_hash_reset(handle); + + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + } + + average_keys_added /= ITERATIONS; + + printf( + "\nAverage table utilization = %.2f%% (%u/%u)\n", + ((double)average_keys_added / ut_params.entries * 100), + average_keys_added, ut_params.entries); + printf( + "Average insert time = %lf,", (add_time / ITERATIONS)); + printf( + " lookup time = %lf, lookup_bulk time = %lf\n", + (lookup_time / ITERATIONS), (bulk_time / ITERATIONS)); + odph_cuckoo_hash_destroy(handle); + + return 0; +} + +/* + * Do all unit and performance tests. + */ +static int +test_cuckoo_hash_table(void) +{ + odph_ring_tailq_init(); + if (test_add_delete() < 0) + return -1; + if (test_hash_find_existing() < 0) + return -1; + if (test_add_update_delete() < 0) + return -1; + if (test_five_keys() < 0) + return -1; + if (test_hash_creation_with_bad_parameters() < 0) + return -1; + if (test_hash_creation_with_good_parameters() < 0) + return -1; + if (test_hash_iteration() < 0) + return -1; + if (test_average_table_utilization() < 0) + return -1; + + return 0; +} + +int main(int argc TEST_UNUSED, char *argv[] TEST_UNUSED) +{ + if (odp_init_global(NULL, NULL)) { + LOG_ERR("Error: ODP global init failed.\n"); + exit(EXIT_FAILURE); + } + + if (odp_init_local(ODP_THREAD_WORKER)) { + LOG_ERR("Error: ODP local init failed.\n"); + exit(EXIT_FAILURE); + } + + int val = test_cuckoo_hash_table(); + + if (val < 0) + printf("cuckoo hash test fail!!\n"); + else + printf("All Tests pass!!\n"); + + if (odp_term_local()) { + LOG_ERR("Error: ODP local term failed.\n"); + exit(EXIT_FAILURE); + } + + if (odp_term_global()) { + LOG_ERR("Error: ODP global term failed.\n"); + exit(EXIT_FAILURE); + } + + return val; +} + diff --git a/include/odp/api/hash.h b/include/odp/api/hash.h index 1b2a580..8fd826d 100644 --- a/include/odp/api/hash.h +++ b/include/odp/api/hash.h @@ -25,6 +25,20 @@ extern "C" { */ /** + * @typedef odp_hash_function + * odp hash function + */ +typedef uint32_t (*odp_hash_function)(const void *key, uint32_t data_len, + uint32_t init_val); + +/** + * @typedef odp_hash_cmp_eq_t + * odp hash compare function + */ +typedef int (*odp_hash_cmp_eq_t)(const void *key1, + const void *key2, size_t data_len); + +/** * Calculate CRC-32 * * Calculates CRC-32 over the data. The polynomial is 0x04c11db7. @@ -45,7 +59,7 @@ uint32_t odp_hash_crc32(const void *data, uint32_t data_len, uint32_t init_val); * * @param data Pointer to data * @param data_len Data length in bytes -* @param init_val CRC generator initialization value +* @param init_val CRC generator initialization nvalue * * @return CRC32C value */ -- 1.9.1 _______________________________________________ lng-odp mailing list lng-odp@lists.linaro.org https://lists.linaro.org/mailman/listinfo/lng-odp