X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;ds=sidebyside;f=lib%2Flibrte_hash%2Frte_cuckoo_hash.c;h=a07543a29a522ecaa304c942db3103641ffddd36;hb=93723dd917f4e4131011d0f6c0f6b1ddc7c12e17;hp=645c0cfab5113fe84e5c1efa3b8a844d32c4f90a;hpb=ecaed092b677d09b4b8645a3ddc38aac0ea929f7;p=dpdk.git diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 645c0cfab5..a07543a29a 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); @@ -538,8 +515,10 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, n_slots = rte_ring_mc_dequeue_burst(h->free_slots, cached_free_slots->objs, LCORE_CACHE_SIZE, NULL); - if (n_slots == 0) - return -ENOSPC; + if (n_slots == 0) { + ret = -ENOSPC; + goto failure; + } cached_free_slots->len += n_slots; } @@ -548,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); @@ -569,9 +550,10 @@ __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; + ret = prim_bkt->key_idx[i] - 1; + goto failure; } } } @@ -589,9 +571,10 @@ __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; + ret = sec_bkt->key_idx[i] - 1; + goto failure; } } } @@ -644,7 +627,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; @@ -659,6 +642,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; @@ -730,7 +714,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; } @@ -753,7 +737,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; } @@ -847,7 +831,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; @@ -872,7 +856,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;