From patchwork Thu Sep 21 12:46:46 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "De Lara Guarch, Pablo" X-Patchwork-Id: 29072 Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 4A6911AEF5; Thu, 21 Sep 2017 22:46:40 +0200 (CEST) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id BC66C6D45; Thu, 21 Sep 2017 22:46:38 +0200 (CEST) Received: from fmsmga005.fm.intel.com ([10.253.24.32]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 21 Sep 2017 13:46:34 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.42,426,1500966000"; d="scan'208";a="154098796" Received: from silpixa00399464.ir.intel.com (HELO silpixa00399464.ger.corp.intel.com) ([10.237.222.157]) by fmsmga005.fm.intel.com with ESMTP; 21 Sep 2017 13:46:27 -0700 From: Pablo de Lara To: bruce.richardson@intel.com Cc: dev@dpdk.org, Pablo de Lara , stable@dpdk.org Date: Thu, 21 Sep 2017 13:46:46 +0100 Message-Id: <20170921124646.68253-1-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 2.9.4 Subject: [dpdk-dev] [PATCH] hash: fix incorrect eviction counter X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" When adding a new entry in a hash table, there is a maximum number of evictions that can be performed. When the counter of these evictions reaches this maximum, the entry cannot be added, as it is considered that the algorithm has encountered an infinite loop. The problem with the current implementation, is that this counter was declared as a static variable. If there are multiple threads adding entries in the same table or in different tables, they should access different counters, one per core and per table. Therefore, an array of counter has been added to the hash table structure. Fixes: 243e93a5046f ("hash: fix unlimited cuckoo path") Cc: stable@dpdk.org Signed-off-by: Pablo de Lara --- lib/librte_hash/rte_cuckoo_hash.c | 27 ++++++++++++++++++--------- lib/librte_hash/rte_cuckoo_hash.h | 4 ++++ 2 files changed, 22 insertions(+), 9 deletions(-) diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 87b25c0..6a0f2f5 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -121,6 +121,7 @@ rte_hash_create(const struct rte_hash_parameters *params) char hash_name[RTE_HASH_NAMESIZE]; void *k = NULL; void *buckets = NULL; + uint32_t *nr_cuckoo_pushes = NULL; char ring_name[RTE_RING_NAMESIZE]; unsigned num_key_slots; unsigned hw_trans_mem_support = 0; @@ -313,6 +314,14 @@ rte_hash_create(const struct rte_hash_parameters *params) for (i = 1; i < params->entries + 1; i++) rte_ring_sp_enqueue(r, (void *)((uintptr_t) i)); + nr_cuckoo_pushes = rte_zmalloc_socket(NULL, + sizeof(uint32_t) * RTE_MAX_LCORE, + 0, params->socket_id); + if (nr_cuckoo_pushes == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + goto err_unlock; + } + h->nr_cuckoo_pushes = nr_cuckoo_pushes; te->data = (void *) h; TAILQ_INSERT_TAIL(hash_list, te, next); rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); @@ -326,6 +335,7 @@ rte_hash_create(const struct rte_hash_parameters *params) rte_free(h); rte_free(buckets); rte_free(k); + rte_free(nr_cuckoo_pushes); return NULL; } @@ -417,9 +427,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, + uint32_t *nr_pushes) { - static unsigned int nr_pushes; unsigned i, j; int ret; uint32_t next_bucket_idx; @@ -456,15 +466,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 +481,7 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) * or return error */ bkt->flag[i] = 0; - nr_pushes = 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]; @@ -513,8 +522,9 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, uint32_t new_idx; int ret; unsigned n_slots; - unsigned lcore_id; + unsigned int lcore_id = rte_lcore_id(); struct lcore_cache *cached_free_slots = NULL; + uint32_t *nr_pushes = &(h->nr_cuckoo_pushes[lcore_id]); if (h->add_key == ADD_KEY_MULTIWRITER) rte_spinlock_lock(h->multiwriter_lock); @@ -530,7 +540,6 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, /* Get a new slot for storing the new key */ if (h->hw_trans_mem_support) { - lcore_id = rte_lcore_id(); cached_free_slots = &h->local_free_slots[lcore_id]; /* Try to get a free slot from the local cache */ if (cached_free_slots->len == 0) { @@ -648,7 +657,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; diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index f75392d..e302967 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -219,6 +219,10 @@ struct rte_hash { /**< Table with buckets storing all the hash values and key indexes * to the key table. */ + uint32_t *nr_cuckoo_pushes; + /**< Pointer to number of entries that have been evicted + * when adding a new entry, per lcore. + */ } __rte_cache_aligned; struct queue_node {