[1/3] lib/hash: use ordered loads only if signature matches
Checks
Commit Message
Relaxed signature comparison is done first. Further ordered loads
are done only if the signature matches. Any false positives are
caught by the full key comparison.
Fixes: e605a1d36 ("hash: add lock-free r/w concurrency")
Cc: stable@dpdk.org
Signed-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
Reviewed-by: Gavin Hu <gavin.hu@arm.com>
Tested-by: Ruifeng Wang <ruifeng.wang@arm.com>
---
lib/librte_hash/rte_cuckoo_hash.c | 35 ++++++++++++++++++-------------
1 file changed, 21 insertions(+), 14 deletions(-)
Comments
>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:honnappa.nagarahalli@arm.com]
>Sent: Tuesday, June 25, 2019 2:15 PM
>To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; Richardson, Bruce
><bruce.richardson@intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>; honnappa.nagarahalli@arm.com
>Cc: gavin.hu@arm.com; ruifeng.wang@arm.com; dev@dpdk.org; nd@arm.com; stable@dpdk.org
>Subject: [PATCH 1/3] lib/hash: use ordered loads only if signature matches
>
>Relaxed signature comparison is done first. Further ordered loads
>are done only if the signature matches. Any false positives are
>caught by the full key comparison.
[Wang, Yipeng] add: This commit improves lookup performance.
>
>Fixes: e605a1d36 ("hash: add lock-free r/w concurrency")
>Cc: stable@dpdk.org
>
>Signed-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
>Reviewed-by: Gavin Hu <gavin.hu@arm.com>
>Tested-by: Ruifeng Wang <ruifeng.wang@arm.com>
>---
> lib/librte_hash/rte_cuckoo_hash.c | 35 ++++++++++++++++++-------------
> 1 file changed, 21 insertions(+), 14 deletions(-)
>
>diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
>index 953928f27..f37f6957d 100644
>--- a/lib/librte_hash/rte_cuckoo_hash.c
>+++ b/lib/librte_hash/rte_cuckoo_hash.c
>@@ -1188,22 +1188,29 @@ search_one_bucket_lf(const struct rte_hash *h, const void *key, uint16_t sig,
> struct rte_hash_key *k, *keys = h->key_store;
>
> for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
>- key_idx = __atomic_load_n(&bkt->key_idx[i],
>+ /* Signature comparison is done before the acquire-load
>+ * of the key index to achieve better performance.
>+ * Any false positives will be caught in full comparison
>+ * of the key.
>+ */
[Wang, Yipeng]
A bit more explanation would be helpful for future understanding of the code:
"Signature comparison is done ... performance.
Although this could accidentally cause the reader to read an old signature while the key_idx
is updated to a new key's, any false positive will be .... of the key."
Otherwise:
Acked-by: Yipeng Wang <yipeng1.wang@intel.com>
@@ -1188,22 +1188,29 @@ search_one_bucket_lf(const struct rte_hash *h, const void *key, uint16_t sig,
struct rte_hash_key *k, *keys = h->key_store;
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
- key_idx = __atomic_load_n(&bkt->key_idx[i],
+ /* Signature comparison is done before the acquire-load
+ * of the key index to achieve better performance.
+ * Any false positives will be caught in full comparison
+ * of the key.
+ */
+ if (bkt->sig_current[i] == sig) {
+ key_idx = __atomic_load_n(&bkt->key_idx[i],
__ATOMIC_ACQUIRE);
- if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) {
- k = (struct rte_hash_key *) ((char *)keys +
- key_idx * h->key_entry_size);
- pdata = __atomic_load_n(&k->pdata,
- __ATOMIC_ACQUIRE);
+ if (key_idx != EMPTY_SLOT) {
+ k = (struct rte_hash_key *) ((char *)keys +
+ key_idx * h->key_entry_size);
+ pdata = __atomic_load_n(&k->pdata,
+ __ATOMIC_ACQUIRE);
- if (rte_hash_cmp_eq(key, k->key, h) == 0) {
- if (data != NULL)
- *data = pdata;
- /*
- * Return index where key is stored,
- * subtracting the first dummy index
- */
- return key_idx - 1;
+ if (rte_hash_cmp_eq(key, k->key, h) == 0) {
+ if (data != NULL)
+ *data = pdata;
+ /*
+ * Return index where key is stored,
+ * subtracting the first dummy index
+ */
+ return key_idx - 1;
+ }
}
}
}