X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;f=lib%2Flibrte_hash%2Frte_cuckoo_hash.c;h=9b1387b5e817edb28faefa9835a6aca2fe6b61e6;hb=f3eeed27ffe3b8521d45940df587385c50069056;hp=51db006a9613c1a6770444a9dce6d379294808ad;hpb=243e93a5046ff61658a0f5905ded49634c5ab205;p=dpdk.git diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 51db006a96..9b1387b5e8 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -1,34 +1,5 @@ -/*- - * BSD LICENSE - * - * Copyright(c) 2010-2016 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. +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2010-2016 Intel Corporation */ #include @@ -44,7 +15,6 @@ #include #include #include -#include #include #include #include @@ -52,11 +22,11 @@ #include #include #include -#include #include #include #include #include +#include #include "rte_hash.h" #include "rte_cuckoo_hash.h" @@ -125,6 +95,7 @@ rte_hash_create(const struct rte_hash_parameters *params) unsigned num_key_slots; unsigned hw_trans_mem_support = 0; unsigned i; + rte_hash_function default_hash_func = (rte_hash_function)rte_jhash; hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); @@ -268,6 +239,13 @@ rte_hash_create(const struct rte_hash_parameters *params) RTE_CACHE_LINE_SIZE, params->socket_id); } + /* Default hash function */ +#if defined(RTE_ARCH_X86) + default_hash_func = (rte_hash_function)rte_hash_crc; +#elif defined(RTE_ARCH_ARM64) + if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_CRC32)) + default_hash_func = (rte_hash_function)rte_hash_crc; +#endif /* Setup hash context */ snprintf(h->name, sizeof(h->name), "%s", params->name); h->entries = params->entries; @@ -279,7 +257,7 @@ rte_hash_create(const struct rte_hash_parameters *params) h->bucket_bitmask = h->num_buckets - 1; h->buckets = buckets; h->hash_func = (params->hash_func == NULL) ? - DEFAULT_HASH_FUNC : params->hash_func; + default_hash_func : params->hash_func; h->key_store = k; h->free_slots = r; h->hw_trans_mem_support = hw_trans_mem_support; @@ -417,9 +395,9 @@ rte_hash_reset(struct rte_hash *h) /* Search for an entry that can be pushed to its alternative location */ static inline int -make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) +make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt, + unsigned int *nr_pushes) { - static unsigned int nr_pushes; unsigned i, j; int ret; uint32_t next_bucket_idx; @@ -456,15 +434,14 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) break; /* All entries have been pushed, so entry cannot be added */ - if (i == RTE_HASH_BUCKET_ENTRIES || nr_pushes > RTE_HASH_MAX_PUSHES) + if (i == RTE_HASH_BUCKET_ENTRIES || ++(*nr_pushes) > RTE_HASH_MAX_PUSHES) return -ENOSPC; /* Set flag to indicate that this entry is going to be pushed */ bkt->flag[i] = 1; - nr_pushes++; /* Need room in alternative bucket to insert the pushed entry */ - ret = make_space_bucket(h, next_bkt[i]); + ret = make_space_bucket(h, next_bkt[i], nr_pushes); /* * After recursive function. * Clear flags and insert the pushed entry @@ -472,7 +449,6 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) * or return error */ bkt->flag[i] = 0; - nr_pushes = 0; if (ret >= 0) { next_bkt[i]->sig_alt[ret] = bkt->sig_current[i]; next_bkt[i]->sig_current[ret] = bkt->sig_alt[i]; @@ -515,6 +491,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, unsigned n_slots; unsigned lcore_id; struct lcore_cache *cached_free_slots = NULL; + unsigned int nr_pushes = 0; if (h->add_key == ADD_KEY_MULTIWRITER) rte_spinlock_lock(h->multiwriter_lock); @@ -536,9 +513,12 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, if (cached_free_slots->len == 0) { /* Need to get another burst of free slots from global ring */ n_slots = rte_ring_mc_dequeue_burst(h->free_slots, - cached_free_slots->objs, LCORE_CACHE_SIZE); - if (n_slots == 0) - return -ENOSPC; + cached_free_slots->objs, + LCORE_CACHE_SIZE, NULL); + if (n_slots == 0) { + ret = -ENOSPC; + goto failure; + } cached_free_slots->len += n_slots; } @@ -547,8 +527,10 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, cached_free_slots->len--; slot_id = cached_free_slots->objs[cached_free_slots->len]; } else { - if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) - return -ENOSPC; + if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) { + ret = -ENOSPC; + goto failure; + } } new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size); @@ -568,7 +550,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, k->pdata = data; /* * Return index where key is stored, - * substracting the first dummy index + * subtracting the first dummy index */ return prim_bkt->key_idx[i] - 1; } @@ -588,7 +570,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, k->pdata = data; /* * Return index where key is stored, - * substracting the first dummy index + * subtracting the first dummy index */ return sec_bkt->key_idx[i] - 1; } @@ -643,7 +625,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, * if successful or return error and * store the new slot back in the ring */ - ret = make_space_bucket(h, prim_bkt); + ret = make_space_bucket(h, prim_bkt, &nr_pushes); if (ret >= 0) { prim_bkt->sig_current[ret] = sig; prim_bkt->sig_alt[ret] = alt_hash; @@ -658,6 +640,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, /* Error in addition, store new slot back in the ring and return error */ enqueue_slot_back(h, cached_free_slots, (void *)((uintptr_t) new_idx)); +failure: if (h->add_key == ADD_KEY_MULTIWRITER) rte_spinlock_unlock(h->multiwriter_lock); return ret; @@ -729,7 +712,7 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, *data = k->pdata; /* * Return index where key is stored, - * substracting the first dummy index + * subtracting the first dummy index */ return bkt->key_idx[i] - 1; } @@ -752,7 +735,7 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, *data = k->pdata; /* * Return index where key is stored, - * substracting the first dummy index + * subtracting the first dummy index */ return bkt->key_idx[i] - 1; } @@ -808,7 +791,7 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) /* Need to enqueue the free slots in global ring. */ n_slots = rte_ring_mp_enqueue_burst(h->free_slots, cached_free_slots->objs, - LCORE_CACHE_SIZE); + LCORE_CACHE_SIZE, NULL); cached_free_slots->len -= n_slots; } /* Put index of new free slot in cache. */ @@ -846,7 +829,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* * Return index where key is stored, - * substracting the first dummy index + * subtracting the first dummy index */ ret = bkt->key_idx[i] - 1; bkt->key_idx[i] = EMPTY_SLOT; @@ -871,7 +854,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* * Return index where key is stored, - * substracting the first dummy index + * subtracting the first dummy index */ ret = bkt->key_idx[i] - 1; bkt->key_idx[i] = EMPTY_SLOT;