* [dpdk-dev] [PATCH] hash: fix incorrect lookup if key is all zero
@ 2015-09-17 9:04 Pablo de Lara
2015-09-17 10:14 ` Thomas Monjalon
2015-09-17 10:30 ` [dpdk-dev] [PATCH v2] " Pablo de Lara
0 siblings, 2 replies; 5+ messages in thread
From: Pablo de Lara @ 2015-09-17 9:04 UTC (permalink / raw)
To: dev
If user has not added an all zero key in the hash table,
and tries to look it up, it results in an incorrect hit,
as dummy slot in the key table has all zero as well.
Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
doc/guides/rel_notes/release_2_2.rst | 5 +++++
lib/librte_hash/rte_cuckoo_hash.c | 27 +++++++++++++++++----------
2 files changed, 22 insertions(+), 10 deletions(-)
diff --git a/doc/guides/rel_notes/release_2_2.rst b/doc/guides/rel_notes/release_2_2.rst
index 682f468..e4460f7 100644
--- a/doc/guides/rel_notes/release_2_2.rst
+++ b/doc/guides/rel_notes/release_2_2.rst
@@ -8,6 +8,11 @@ New Features
Resolved Issues
---------------
+* **hash: Fixed incorrect lookup if key is all zero. **
+
+Fixed issue in hash library that occurred if an all zero
+key was not added in the table and the key was looked up,
+resulting in an incorrect hit.
Known Issues
------------
diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 7019763..62d7143 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -861,15 +861,22 @@ lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash,
/* Lookup bulk stage 3: Check if key matches, update hit mask and return data */
static inline void
lookup_stage3(unsigned idx, const struct rte_hash_key *key_slot, const void * const *keys,
- void *data[], uint64_t *hits, const struct rte_hash *h)
+ const int32_t *positions, void *data[], uint64_t *hits,
+ const struct rte_hash *h)
{
unsigned hit;
+ unsigned key_idx;
hit = !h->rte_hash_cmp_eq(key_slot->key, keys[idx], h->key_len);
if (data != NULL)
data[idx] = key_slot->pdata;
- *hits |= (uint64_t)(hit) << idx;
+ key_idx = positions[idx] + 1;
+ /*
+ * If key index is 0, force hit to be 0, in case key to be looked up
+ * is all zero (as in the dummy slot), which would result in a wrong hit
+ */
+ *hits |= (uint64_t)(hit && !!key_idx) << idx;
}
static inline void
@@ -961,8 +968,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
lookup_stage2(idx21, primary_hash21, secondary_hash21,
primary_bkt21, secondary_bkt21, &k_slot21, positions,
&extra_hits_mask, key_store, h);
- lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
+ lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
}
k_slot30 = k_slot20, k_slot31 = k_slot21;
@@ -988,8 +995,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
key_store, h);
- lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
+ lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
k_slot30 = k_slot20, k_slot31 = k_slot21;
idx30 = idx20, idx31 = idx21;
@@ -1009,14 +1016,14 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
key_store, h);
- lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
+ lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
k_slot30 = k_slot20, k_slot31 = k_slot21;
idx30 = idx20, idx31 = idx21;
- lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
+ lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
/* ignore any items we have already found */
extra_hits_mask &= ~hits;
--
2.4.2
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [dpdk-dev] [PATCH] hash: fix incorrect lookup if key is all zero
2015-09-17 9:04 [dpdk-dev] [PATCH] hash: fix incorrect lookup if key is all zero Pablo de Lara
@ 2015-09-17 10:14 ` Thomas Monjalon
2015-09-17 10:30 ` [dpdk-dev] [PATCH v2] " Pablo de Lara
1 sibling, 0 replies; 5+ messages in thread
From: Thomas Monjalon @ 2015-09-17 10:14 UTC (permalink / raw)
To: Pablo de Lara; +Cc: dev
Hi Pablo,
2015-09-17 10:04, Pablo de Lara:
> If user has not added an all zero key in the hash table,
> and tries to look it up, it results in an incorrect hit,
> as dummy slot in the key table has all zero as well.
>
> Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
Please try to remember to use "Fixes:" tag.
^ permalink raw reply [flat|nested] 5+ messages in thread
* [dpdk-dev] [PATCH v2] hash: fix incorrect lookup if key is all zero
2015-09-17 9:04 [dpdk-dev] [PATCH] hash: fix incorrect lookup if key is all zero Pablo de Lara
2015-09-17 10:14 ` Thomas Monjalon
@ 2015-09-17 10:30 ` Pablo de Lara
2015-09-28 10:29 ` Bruce Richardson
1 sibling, 1 reply; 5+ messages in thread
From: Pablo de Lara @ 2015-09-17 10:30 UTC (permalink / raw)
To: dev
If user has not added an all zero key in the hash table,
and tries to look it up, it results in an incorrect hit,
as dummy slot in the key table has all zero as well.
Fixes: 48a399119619 ("hash: replace with cuckoo hash implementation")
Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
Changes in v2:
- Include Fixes: tag in commit message
doc/guides/rel_notes/release_2_2.rst | 5 +++++
lib/librte_hash/rte_cuckoo_hash.c | 27 +++++++++++++++++----------
2 files changed, 22 insertions(+), 10 deletions(-)
diff --git a/doc/guides/rel_notes/release_2_2.rst b/doc/guides/rel_notes/release_2_2.rst
index 682f468..e4460f7 100644
--- a/doc/guides/rel_notes/release_2_2.rst
+++ b/doc/guides/rel_notes/release_2_2.rst
@@ -8,6 +8,11 @@ New Features
Resolved Issues
---------------
+* **hash: Fixed incorrect lookup if key is all zero. **
+
+Fixed issue in hash library that occurred if an all zero
+key was not added in the table and the key was looked up,
+resulting in an incorrect hit.
Known Issues
------------
diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 7019763..62d7143 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -861,15 +861,22 @@ lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash,
/* Lookup bulk stage 3: Check if key matches, update hit mask and return data */
static inline void
lookup_stage3(unsigned idx, const struct rte_hash_key *key_slot, const void * const *keys,
- void *data[], uint64_t *hits, const struct rte_hash *h)
+ const int32_t *positions, void *data[], uint64_t *hits,
+ const struct rte_hash *h)
{
unsigned hit;
+ unsigned key_idx;
hit = !h->rte_hash_cmp_eq(key_slot->key, keys[idx], h->key_len);
if (data != NULL)
data[idx] = key_slot->pdata;
- *hits |= (uint64_t)(hit) << idx;
+ key_idx = positions[idx] + 1;
+ /*
+ * If key index is 0, force hit to be 0, in case key to be looked up
+ * is all zero (as in the dummy slot), which would result in a wrong hit
+ */
+ *hits |= (uint64_t)(hit && !!key_idx) << idx;
}
static inline void
@@ -961,8 +968,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
lookup_stage2(idx21, primary_hash21, secondary_hash21,
primary_bkt21, secondary_bkt21, &k_slot21, positions,
&extra_hits_mask, key_store, h);
- lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
+ lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
}
k_slot30 = k_slot20, k_slot31 = k_slot21;
@@ -988,8 +995,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
key_store, h);
- lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
+ lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
k_slot30 = k_slot20, k_slot31 = k_slot21;
idx30 = idx20, idx31 = idx21;
@@ -1009,14 +1016,14 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
key_store, h);
- lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
+ lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
k_slot30 = k_slot20, k_slot31 = k_slot21;
idx30 = idx20, idx31 = idx21;
- lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
+ lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
+ lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
/* ignore any items we have already found */
extra_hits_mask &= ~hits;
--
2.4.2
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [dpdk-dev] [PATCH v2] hash: fix incorrect lookup if key is all zero
2015-09-17 10:30 ` [dpdk-dev] [PATCH v2] " Pablo de Lara
@ 2015-09-28 10:29 ` Bruce Richardson
2015-11-04 0:07 ` Thomas Monjalon
0 siblings, 1 reply; 5+ messages in thread
From: Bruce Richardson @ 2015-09-28 10:29 UTC (permalink / raw)
To: Pablo de Lara; +Cc: dev
On Thu, Sep 17, 2015 at 11:30:48AM +0100, Pablo de Lara wrote:
> If user has not added an all zero key in the hash table,
> and tries to look it up, it results in an incorrect hit,
> as dummy slot in the key table has all zero as well.
>
> Fixes: 48a399119619 ("hash: replace with cuckoo hash implementation")
>
> Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
> ---
> Changes in v2:
> - Include Fixes: tag in commit message
>
> doc/guides/rel_notes/release_2_2.rst | 5 +++++
> lib/librte_hash/rte_cuckoo_hash.c | 27 +++++++++++++++++----------
> 2 files changed, 22 insertions(+), 10 deletions(-)
>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [dpdk-dev] [PATCH v2] hash: fix incorrect lookup if key is all zero
2015-09-28 10:29 ` Bruce Richardson
@ 2015-11-04 0:07 ` Thomas Monjalon
0 siblings, 0 replies; 5+ messages in thread
From: Thomas Monjalon @ 2015-11-04 0:07 UTC (permalink / raw)
To: Pablo de Lara; +Cc: dev
2015-09-28 11:29, Bruce Richardson:
> On Thu, Sep 17, 2015 at 11:30:48AM +0100, Pablo de Lara wrote:
> > If user has not added an all zero key in the hash table,
> > and tries to look it up, it results in an incorrect hit,
> > as dummy slot in the key table has all zero as well.
> >
> > Fixes: 48a399119619 ("hash: replace with cuckoo hash implementation")
> >
> > 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] 5+ messages in thread
end of thread, other threads:[~2015-11-04 0:08 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-09-17 9:04 [dpdk-dev] [PATCH] hash: fix incorrect lookup if key is all zero Pablo de Lara
2015-09-17 10:14 ` Thomas Monjalon
2015-09-17 10:30 ` [dpdk-dev] [PATCH v2] " Pablo de Lara
2015-09-28 10:29 ` Bruce Richardson
2015-11-04 0:07 ` Thomas Monjalon
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).