[dpdk-dev] [PATCH 0/3] Hash library fixes

[dpdk-dev] [PATCH 0/3] Hash library fixes

[Pablo de Lara]

This patchset includes some minor fixes to the hash library,
plus a small improvement in checking for an empty slot
when performing different hash operations.

Pablo de Lara (3):
  hash: fix ring size
  hash: fix false zero signature key hit lookup
  hash: check if slot is empty with key index

 lib/librte_hash/rte_cuckoo_hash.c     | 24 +++++++++++++++---------
 lib/librte_hash/rte_cuckoo_hash.h     |  2 ++
 lib/librte_hash/rte_cuckoo_hash_x86.h |  5 ++---
 3 files changed, 19 insertions(+), 12 deletions(-)

-- 
2.7.4

[dpdk-dev] [PATCH 1/3] hash: fix ring size

[Pablo de Lara]

Ring stores the free slots available to be used in the key table.
The ring size was being increased by 1, because of the dummy slot,
used for key misses, but this is not actually stored in the ring,
so there is no need to increase it.

Fixes: 5915699153d7 ("hash: fix scaling by reducing contention")

Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
 lib/librte_hash/rte_cuckoo_hash.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 26e54f6..63fa036 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -159,7 +159,8 @@ rte_hash_create(const struct rte_hash_parameters *params)
 		num_key_slots = params->entries + 1;
 
 	snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
-	r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots),
+	/* Create ring (Dummy slot index is not enqueued) */
+	r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots - 1),
 			params->socket_id, 0);
 	if (r == NULL) {
 		RTE_LOG(ERR, HASH, "memory allocation failed\n");
-- 
2.7.4

[dpdk-dev] [PATCH 2/3] hash: fix false zero signature key hit lookup

[Pablo de Lara]

This commit fixes a corner case scenario. When a key is deleted,
its signature in the hash table gets clear, which should prevent
a lookup of that same key, unless the signature of the key is all zeroes.

In that case, there will be a match, and key would be compared against
the key that is in the table (which does not get cleared,
as the performance penalty would be high), resulting in a wrong hit.

To prevent this from happening, the key index associated to that entry
should be set to zero when deleting it, so in case that same key
is looked up just after a deletion, it will point to the dummy key slot,
which guarantees a miss.

Fixes: 48a399119619 ("hash: replace with cuckoo hash implementation")

Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
 lib/librte_hash/rte_cuckoo_hash.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 63fa036..be1490a 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -815,6 +815,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
 	unsigned i;
 	struct rte_hash_bucket *bkt;
 	struct rte_hash_key *k, *keys = h->key_store;
+	int32_t ret;
 
 	bucket_idx = sig & h->bucket_bitmask;
 	bkt = &h->buckets[bucket_idx];
@@ -832,7 +833,9 @@ __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
 				 */
-				return bkt->key_idx[i] - 1;
+				ret = bkt->key_idx[i] - 1;
+				bkt->key_idx[i] = 0;
+				return ret;
 			}
 		}
 	}
@@ -855,7 +858,9 @@ __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
 				 */
-				return bkt->key_idx[i] - 1;
+				ret = bkt->key_idx[i] - 1;
+				bkt->key_idx[i] = 0;
+				return ret;
 			}
 		}
 	}
-- 
2.7.4

[dpdk-dev] [PATCH 3/3] hash: check if slot is empty with key index

[Pablo de Lara]

Instead of checking if the current and alternative signatures are 0,
it is faster to check if the key index associated to an entry
is 0, meaning that the slot is empty.

Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
 lib/librte_hash/rte_cuckoo_hash.c     | 16 ++++++++--------
 lib/librte_hash/rte_cuckoo_hash.h     |  2 ++
 lib/librte_hash/rte_cuckoo_hash_x86.h |  5 ++---
 3 files changed, 12 insertions(+), 11 deletions(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index be1490a..dd0290f 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -423,7 +423,7 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
 		next_bucket_idx = bkt->signatures[i].alt & h->bucket_bitmask;
 		next_bkt[i] = &h->buckets[next_bucket_idx];
 		for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) {
-			if (next_bkt[i]->signatures[j].sig == NULL_SIGNATURE)
+			if (next_bkt[i]->key_idx[j] == EMPTY_SLOT)
 				break;
 		}
 
@@ -609,7 +609,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
 #endif
 		for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 			/* Check if slot is available */
-			if (likely(prim_bkt->signatures[i].sig == NULL_SIGNATURE)) {
+			if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {
 				prim_bkt->signatures[i].current = sig;
 				prim_bkt->signatures[i].alt = alt_hash;
 				prim_bkt->key_idx[i] = new_idx;
@@ -707,7 +707,7 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
 	/* Check if key is in primary location */
 	for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 		if (bkt->signatures[i].current == sig &&
-				bkt->signatures[i].sig != NULL_SIGNATURE) {
+				bkt->key_idx[i] != EMPTY_SLOT) {
 			k = (struct rte_hash_key *) ((char *)keys +
 					bkt->key_idx[i] * h->key_entry_size);
 			if (rte_hash_cmp_eq(key, k->key, h) == 0) {
@@ -823,7 +823,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
 	/* Check if key is in primary location */
 	for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 		if (bkt->signatures[i].current == sig &&
-				bkt->signatures[i].sig != NULL_SIGNATURE) {
+				bkt->key_idx[i] != EMPTY_SLOT) {
 			k = (struct rte_hash_key *) ((char *)keys +
 					bkt->key_idx[i] * h->key_entry_size);
 			if (rte_hash_cmp_eq(key, k->key, h) == 0) {
@@ -834,7 +834,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
 				 * substracting the first dummy index
 				 */
 				ret = bkt->key_idx[i] - 1;
-				bkt->key_idx[i] = 0;
+				bkt->key_idx[i] = EMPTY_SLOT;
 				return ret;
 			}
 		}
@@ -848,7 +848,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
 	/* Check if key is in secondary location */
 	for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 		if (bkt->signatures[i].current == alt_hash &&
-				bkt->signatures[i].sig != NULL_SIGNATURE) {
+				bkt->key_idx[i] != EMPTY_SLOT) {
 			k = (struct rte_hash_key *) ((char *)keys +
 					bkt->key_idx[i] * h->key_entry_size);
 			if (rte_hash_cmp_eq(key, k->key, h) == 0) {
@@ -859,7 +859,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
 				 * substracting the first dummy index
 				 */
 				ret = bkt->key_idx[i] - 1;
-				bkt->key_idx[i] = 0;
+				bkt->key_idx[i] = EMPTY_SLOT;
 				return ret;
 			}
 		}
@@ -1229,7 +1229,7 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32
 	idx = *next % RTE_HASH_BUCKET_ENTRIES;
 
 	/* If current position is empty, go to the next one */
-	while (h->buckets[bucket_idx].signatures[idx].sig == NULL_SIGNATURE) {
+	while (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) {
 		(*next)++;
 		/* End of table */
 		if (*next == total_entries)
diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h
index 6c76700..e290dab 100644
--- a/lib/librte_hash/rte_cuckoo_hash.h
+++ b/lib/librte_hash/rte_cuckoo_hash.h
@@ -134,6 +134,8 @@ enum add_key_case {
 
 #define NULL_SIGNATURE			0
 
+#define EMPTY_SLOT			0
+
 #define KEY_ALIGNMENT			16
 
 #define LCORE_CACHE_SIZE		64
diff --git a/lib/librte_hash/rte_cuckoo_hash_x86.h b/lib/librte_hash/rte_cuckoo_hash_x86.h
index fa5630b..e16d69c 100644
--- a/lib/librte_hash/rte_cuckoo_hash_x86.h
+++ b/lib/librte_hash/rte_cuckoo_hash_x86.h
@@ -53,8 +53,7 @@ rte_hash_cuckoo_insert_mw_tm(struct rte_hash_bucket *prim_bkt,
 			*/
 			for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 				/* Check if slot is available */
-				if (likely(prim_bkt->signatures[i].sig ==
-						NULL_SIGNATURE)) {
+				if (likely(prim_bkt->key_idx == EMPTY_SLOT)) {
 					prim_bkt->signatures[i].current = sig;
 					prim_bkt->signatures[i].alt = alt_hash;
 					prim_bkt->key_idx[i] = new_idx;
@@ -171,7 +170,7 @@ rte_hash_cuckoo_make_space_mw_tm(const struct rte_hash *h,
 					queue + RTE_HASH_BFS_QUEUE_MAX_LEN - 4)) {
 		curr_bkt = tail->bkt;
 		for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
-			if (curr_bkt->signatures[i].sig == NULL_SIGNATURE) {
+			if (curr_bkt->key_idx[i] == EMPTY_SLOT) {
 				if (likely(rte_hash_cuckoo_move_insert_mw_tm(h,
 						tail, i, sig,
 						alt_hash, new_idx) == 0))
-- 
2.7.4

Re: [dpdk-dev] [PATCH 0/3] Hash library fixes

[Christian Ehrhardt]

On Fri, Aug 26, 2016 at 11:30 PM, Pablo de Lara <
pablo.de.lara.guarch@intel.com> wrote:

> Pablo de Lara (3):
>   hash: fix ring size
>   hash: fix false zero signature key hit lookup
>   hash: check if slot is empty with key index
>

Thanks Pablo,
I'd suggest to include #1 and #2 for stable as well once discussed and
applied to master - opinions?.


-- 
Christian Ehrhardt
Software Engineer, Ubuntu Server
Canonical Ltd

Re: [dpdk-dev] [PATCH 0/3] Hash library fixes

[Edupuganti, Saikrishna]

> -----Original Message-----
> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Pablo de Lara
> Sent: Friday, August 26, 2016 2:30 PM
> To: dev@dpdk.org
> Cc: Richardson, Bruce <bruce.richardson@intel.com>; De Lara Guarch, Pablo
> <pablo.de.lara.guarch@intel.com>
> Subject: [dpdk-dev] [PATCH 0/3] Hash library fixes
> 
> This patchset includes some minor fixes to the hash library, plus a small
> improvement in checking for an empty slot when performing different hash
> operations.
> 
> Pablo de Lara (3):
>   hash: fix ring size
>   hash: fix false zero signature key hit lookup
>   hash: check if slot is empty with key index
> 
>  lib/librte_hash/rte_cuckoo_hash.c     | 24 +++++++++++++++---------
>  lib/librte_hash/rte_cuckoo_hash.h     |  2 ++
>  lib/librte_hash/rte_cuckoo_hash_x86.h |  5 ++---
>  3 files changed, 19 insertions(+), 12 deletions(-)
> 
> --
> 2.7.4

Series-acked-by: Saikrishna Edupuganti <saikrishna.edupuganti@intel.com>

Re: [dpdk-dev] [PATCH 0/3] Hash library fixes

[Thomas Monjalon]

> > This patchset includes some minor fixes to the hash library, plus a small
> > improvement in checking for an empty slot when performing different hash
> > operations.
> > 
> > Pablo de Lara (3):
> >   hash: fix ring size
> >   hash: fix false zero signature key hit lookup
> >   hash: check if slot is empty with key index
> 
> Series-acked-by: Saikrishna Edupuganti <saikrishna.edupuganti@intel.com>

Applied, thanks