All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH] hash: fix incorrect eviction counter
@ 2017-09-21 12:46 Pablo de Lara
  2017-09-22  4:25 ` [PATCH v2] " Pablo de Lara
  2017-09-22  8:35 ` [PATCH] " Bruce Richardson
  0 siblings, 2 replies; 6+ messages in thread
From: Pablo de Lara @ 2017-09-21 12:46 UTC (permalink / raw)
  To: bruce.richardson; +Cc: dev, Pablo de Lara, stable

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 <pablo.de.lara.guarch@intel.com>
---
 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 {
-- 
2.9.4

^ permalink raw reply related	[flat|nested] 6+ messages in thread
* [PATCH v2] hash: fix incorrect eviction counter
  2017-09-21 12:46 [PATCH] hash: fix incorrect eviction counter Pablo de Lara
@ 2017-09-22  4:25 ` Pablo de Lara
  2017-09-22 13:46   ` Bruce Richardson
  2017-09-22  8:35 ` [PATCH] " Bruce Richardson
  1 sibling, 1 reply; 6+ messages in thread
From: Pablo de Lara @ 2017-09-22  4:25 UTC (permalink / raw)
  To: bruce.richardson; +Cc: dev, Pablo de Lara, stable

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(-)

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;
-- 
2.9.4

^ permalink raw reply related	[flat|nested] 6+ messages in thread
* Re: [PATCH] hash: fix incorrect eviction counter
  2017-09-21 12:46 [PATCH] hash: fix incorrect eviction counter Pablo de Lara
  2017-09-22  4:25 ` [PATCH v2] " Pablo de Lara
@ 2017-09-22  8:35 ` Bruce Richardson
  2017-09-22 10:40   ` De Lara Guarch, Pablo
  1 sibling, 1 reply; 6+ messages in thread
From: Bruce Richardson @ 2017-09-22  8:35 UTC (permalink / raw)
  To: Pablo de Lara; +Cc: dev, stable

On Thu, Sep 21, 2017 at 01:46:46PM +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, 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 <pablo.de.lara.guarch@intel.com>
> ---
Since you appear to be passing this counter through the different
function calls as parameter, and it gets reset to zero at the start, do
you even need an array. Can you not just have a non-static local
variable in the function?

/Bruce

^ permalink raw reply	[flat|nested] 6+ messages in thread
* Re: [PATCH] hash: fix incorrect eviction counter
  2017-09-22  8:35 ` [PATCH] " Bruce Richardson
@ 2017-09-22 10:40   ` De Lara Guarch, Pablo
  0 siblings, 0 replies; 6+ messages in thread
From: De Lara Guarch, Pablo @ 2017-09-22 10:40 UTC (permalink / raw)
  To: Richardson, Bruce; +Cc: dev, stable



> -----Original Message-----
> From: Richardson, Bruce
> Sent: Friday, September 22, 2017 9:36 AM
> To: De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>
> Cc: dev@dpdk.org; stable@dpdk.org
> Subject: Re: [PATCH] hash: fix incorrect eviction counter
> 
> On Thu, Sep 21, 2017 at 01:46:46PM +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, 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 <pablo.de.lara.guarch@intel.com>
> > ---
> Since you appear to be passing this counter through the different function
> calls as parameter, and it gets reset to zero at the start, do you even need
> an array. Can you not just have a non-static local variable in the function?
> 
> /Bruce

Right, I clearly overthought here... Will send a v2 with your much simpler approach.

Thanks!
Pablo

^ permalink raw reply	[flat|nested] 6+ messages in thread
* Re: [PATCH v2] hash: fix incorrect eviction counter
  2017-09-22  4:25 ` [PATCH v2] " Pablo de Lara
@ 2017-09-22 13:46   ` Bruce Richardson
  2017-10-06 22:10     ` Thomas Monjalon
  0 siblings, 1 reply; 6+ messages in thread
From: Bruce Richardson @ 2017-09-22 13:46 UTC (permalink / raw)
  To: Pablo de Lara; +Cc: dev, stable

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>

^ permalink raw reply	[flat|nested] 6+ messages in thread
* Re: [PATCH v2] hash: fix incorrect eviction counter
  2017-09-22 13:46   ` Bruce Richardson
@ 2017-10-06 22:10     ` Thomas Monjalon
  0 siblings, 0 replies; 6+ messages in thread
From: Thomas Monjalon @ 2017-10-06 22:10 UTC (permalink / raw)
  To: Pablo de Lara; +Cc: dev, Bruce Richardson, stable

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

^ permalink raw reply	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2017-10-06 22:10 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-09-21 12:46 [PATCH] hash: fix incorrect eviction counter Pablo de Lara
2017-09-22  4:25 ` [PATCH v2] " Pablo de Lara
2017-09-22 13:46   ` Bruce Richardson
2017-10-06 22:10     ` Thomas Monjalon
2017-09-22  8:35 ` [PATCH] " Bruce Richardson
2017-09-22 10:40   ` De Lara Guarch, Pablo

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.