diff mbox

[dpdk-dev,v2] hash: fix incorrect eviction counter

Message ID 20170922042543.38362-1-pablo.de.lara.guarch@intel.com (mailing list archive)
State Accepted, archived
Headers

Checks

Context Check Description
ci/checkpatch success coding style OK
ci/Intel-compilation success Compilation OK

Commit Message

De Lara Guarch, Pablo Sept. 22, 2017, 4:25 a.m. UTC 
  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, the variable has been modified to be non-static.

Fixes: 243e93a5046f ("hash: fix unlimited cuckoo path")
Cc: stable@dpdk.org

Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---

Changes in v2:
- Used a non-static variable to store counter, instead of
  array in hash structure

 lib/librte_hash/rte_cuckoo_hash.c | 13 ++++++-------
 1 file changed, 6 insertions(+), 7 deletions(-)

Comments

Bruce Richardson Sept. 22, 2017, 1:46 p.m. UTC | #1 
On Fri, Sep 22, 2017 at 05:25:43AM +0100, Pablo de Lara wrote:
> 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, the variable has been modified to be non-static.
> 
> Fixes: 243e93a5046f ("hash: fix unlimited cuckoo path")
> Cc: stable@dpdk.org
> 
> Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
> ---
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
Thomas Monjalon Oct. 6, 2017, 10:10 p.m. UTC | #2 
22/09/2017 15:46, Bruce Richardson:
> On Fri, Sep 22, 2017 at 05:25:43AM +0100, Pablo de Lara wrote:
> > 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, the variable has been modified to be non-static.
> > 
> > Fixes: 243e93a5046f ("hash: fix unlimited cuckoo path")
> > Cc: stable@dpdk.org
> > 
> > Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
> > ---
> Acked-by: Bruce Richardson <bruce.richardson@intel.com>

Applied, thanks
diff mbox

Patch

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 87b25c0..e69b911 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -417,9 +417,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 +456,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 +471,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 +513,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);
@@ -648,7 +647,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;