[dpdk-dev] [PATCH] hash: fix incorrect eviction counter

[Pablo de Lara]

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 at dpdk.org

Signed-off-by: Pablo de Lara <pablo.de.lara.guarch at 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