From: Pablo de Lara <pablo.de.lara.guarch@intel.com>
To: dev@dpdk.org
Cc: bruce.richardson@intel.com,
Pablo de Lara <pablo.de.lara.guarch@intel.com>
Subject: [dpdk-dev] [PATCH 2/3] hash: fix false zero signature key hit lookup
Date: Fri, 26 Aug 2016 22:30:08 +0100 [thread overview]
Message-ID: <1472247009-166860-3-git-send-email-pablo.de.lara.guarch@intel.com> (raw)
In-Reply-To: <1472247009-166860-1-git-send-email-pablo.de.lara.guarch@intel.com>
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
next prev parent reply other threads:[~2016-08-26 21:29 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-08-26 21:30 [dpdk-dev] [PATCH 0/3] Hash library fixes Pablo de Lara
2016-08-26 21:30 ` [dpdk-dev] [PATCH 1/3] hash: fix ring size Pablo de Lara
2016-08-26 21:30 ` Pablo de Lara [this message]
2016-08-26 21:30 ` [dpdk-dev] [PATCH 3/3] hash: check if slot is empty with key index Pablo de Lara
2016-08-29 6:58 ` [dpdk-dev] [PATCH 0/3] Hash library fixes Christian Ehrhardt
2016-09-27 22:34 ` Edupuganti, Saikrishna
2016-09-29 19:52 ` Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1472247009-166860-3-git-send-email-pablo.de.lara.guarch@intel.com \
--to=pablo.de.lara.guarch@intel.com \
--cc=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).