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__); \
+
+ 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");
