diff mbox series

[1/3] lib/hash: use ordered loads only if signature matches

Message ID 20190625211520.43181-2-honnappa.nagarahalli@arm.com
State Superseded
Headers show
Series lib/hash: perf improvements for lock-free | expand

Commit Message

Honnappa Nagarahalli June 25, 2019, 9:15 p.m. UTC
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(-)

-- 
2.17.1

Comments

Wang, Yipeng1 June 28, 2019, 6:04 p.m. UTC | #1
>-----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>
diff mbox series

Patch

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.
+		 */
+		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;
+				}
 			}
 		}
 	}