[dpdk-dev] [PATCH v2 06/11] hash: add new lookup_bulk_with_hash function

[Pablo de Lara <pablo.de.lara.guarch@intel.com>]

Previous implementation was lacking a function
to look up a burst of entries, given precalculated hash values.
This patch implements such function, quite useful for
looking up keys from packets that have precalculated hash values
from a 5-tuple key.

Added the function in the hash unit test as well.

Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
 app/test/test_hash.c                 |  19 ++-
 lib/librte_hash/rte_cuckoo_hash.c    | 222 ++++++++++++++++++++++++++++++++++-
 lib/librte_hash/rte_hash.h           |  27 +++++
 lib/librte_hash/rte_hash_version.map |   8 ++
 4 files changed, 272 insertions(+), 4 deletions(-)

diff --git a/app/test/test_hash.c b/app/test/test_hash.c
index 0176219..52de1bd 100644
--- a/app/test/test_hash.c
+++ b/app/test/test_hash.c
@@ -456,6 +456,7 @@ static int test_five_keys(void)
 {
 	struct rte_hash *handle;
 	const void *key_array[5] = {0};
+	hash_sig_t hashes[5];
 	int pos[5];
 	int expected_pos[5];
 	unsigned i;
@@ -475,12 +476,24 @@ static int test_five_keys(void)
 	}
 
 	/* Lookup */
-	for(i = 0; i < 5; i++)
+	for (i = 0; i < 5; i++) {
 		key_array[i] = &keys[i];
+		hashes[i] = rte_hash_hash(handle, &keys[i]);
+	}
 
 	ret = rte_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos);
-	if(ret == 0)
-		for(i = 0; i < 5; i++) {
+	if (ret == 0)
+		for (i = 0; i < 5; i++) {
+			print_key_info("Lkp", key_array[i], pos[i]);
+			RETURN_IF_ERROR(pos[i] != expected_pos[i],
+					"failed to find key (pos[%u]=%d)", i, pos[i]);
+		}
+
+	/* Lookup with precalculated hashes */
+	ret = rte_hash_lookup_multi_with_hash(handle, &key_array[0], hashes,
+					5, (int32_t *)pos);
+	if (ret == 0)
+		for (i = 0; i < 5; i++) {
 			print_key_info("Lkp", key_array[i], pos[i]);
 			RETURN_IF_ERROR(pos[i] != expected_pos[i],
 					"failed to find key (pos[%u]=%d)", i, pos[i]);
diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index e19b179..f1b6df0 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -709,6 +709,21 @@ lookup_stage0(unsigned *idx, uint64_t *lookup_mask,
 	*lookup_mask &= ~(1llu << *idx);
 }
 
+/* Lookup bulk stage 0: Get primary hash value and calculate secondary hash value */
+static inline void
+lookup_stage0_with_hash(unsigned *idx, uint64_t *lookup_mask,
+		hash_sig_t *primary_hash, hash_sig_t *secondary_hash,
+		const hash_sig_t *hash_vals)
+{
+	*idx = __builtin_ctzl(*lookup_mask);
+	if (*lookup_mask == 0)
+		*idx = 0;
+
+	*primary_hash = hash_vals[*idx];
+	*secondary_hash = rte_hash_secondary_hash(*primary_hash);
+
+	*lookup_mask &= ~(1llu << *idx);
+}
 
 /* Lookup bulk stage 1: Prefetch primary/secondary buckets */
 static inline void
@@ -725,7 +740,7 @@ lookup_stage1(hash_sig_t primary_hash, hash_sig_t secondary_hash,
 }
 
 /*
- * Lookup bulk stage 2:  Search for match hashes in primary/secondary locations
+ * Lookup bulk stage 2: Search for match hashes in primary/secondary locations
  * and prefetch first key slot
  */
 static inline void
@@ -971,6 +986,198 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
 	return 0;
 }
 
+static inline int
+__rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys,
+			const hash_sig_t *hash_vals, uint32_t num_keys,
+			int32_t *positions)
+{
+	uint64_t hits = 0;
+	uint64_t next_mask = 0;
+	uint64_t extra_hits_mask = 0;
+	uint64_t lookup_mask;
+	unsigned idx;
+	const void *key_store = h->key_store;
+
+	unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31;
+	const struct rte_hash_bucket *primary_bkt10, *primary_bkt11;
+	const struct rte_hash_bucket *secondary_bkt10, *secondary_bkt11;
+	const struct rte_hash_bucket *primary_bkt20, *primary_bkt21;
+	const struct rte_hash_bucket *secondary_bkt20, *secondary_bkt21;
+	const void *k_slot20, *k_slot21, *k_slot30, *k_slot31;
+	hash_sig_t primary_hash00, primary_hash01;
+	hash_sig_t secondary_hash00, secondary_hash01;
+	hash_sig_t primary_hash10, primary_hash11;
+	hash_sig_t secondary_hash10, secondary_hash11;
+	hash_sig_t primary_hash20, primary_hash21;
+	hash_sig_t secondary_hash20, secondary_hash21;
+
+	if (num_keys == RTE_HASH_LOOKUP_BULK_MAX)
+		lookup_mask = 0xffffffffffffffff;
+	else
+		lookup_mask = (1ULL << num_keys) - 1;
+
+	lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
+			&secondary_hash00, hash_vals);
+	lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
+			&secondary_hash01, hash_vals);
+
+	primary_hash10 = primary_hash00;
+	primary_hash11 = primary_hash01;
+	secondary_hash10 = secondary_hash00;
+	secondary_hash11 = secondary_hash01;
+	idx10 = idx00, idx11 = idx01;
+
+	lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
+			&secondary_hash00, hash_vals);
+	lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
+			&secondary_hash01, hash_vals);
+	lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10,
+		&secondary_bkt10, h);
+	lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11,
+		&secondary_bkt11, h);
+
+	primary_bkt20 = primary_bkt10;
+	primary_bkt21 = primary_bkt11;
+	secondary_bkt20 = secondary_bkt10;
+	secondary_bkt21 = secondary_bkt11;
+	primary_hash20 = primary_hash10;
+	primary_hash21 = primary_hash11;
+	secondary_hash20 = secondary_hash10;
+	secondary_hash21 = secondary_hash11;
+	idx20 = idx10, idx21 = idx11;
+	primary_hash10 = primary_hash00;
+	primary_hash11 = primary_hash01;
+	secondary_hash10 = secondary_hash00;
+	secondary_hash11 = secondary_hash01;
+	idx10 = idx00, idx11 = idx01;
+
+	lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
+			&secondary_hash00, hash_vals);
+	lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
+			&secondary_hash01, hash_vals);
+	lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10,
+		&secondary_bkt10, h);
+	lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11,
+		&secondary_bkt11, h);
+	lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
+		secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
+		key_store, h);
+	lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
+		secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
+		key_store, h);
+
+	while (lookup_mask) {
+		k_slot30 = k_slot20, k_slot31 = k_slot21;
+		idx30 = idx20, idx31 = idx21;
+		primary_bkt20 = primary_bkt10;
+		primary_bkt21 = primary_bkt11;
+		secondary_bkt20 = secondary_bkt10;
+		secondary_bkt21 = secondary_bkt11;
+		primary_hash20 = primary_hash10;
+		primary_hash21 = primary_hash11;
+		secondary_hash20 = secondary_hash10;
+		secondary_hash21 = secondary_hash11;
+		idx20 = idx10, idx21 = idx11;
+		primary_hash10 = primary_hash00;
+		primary_hash11 = primary_hash01;
+		secondary_hash10 = secondary_hash00;
+		secondary_hash11 = secondary_hash01;
+		idx10 = idx00, idx11 = idx01;
+
+		lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
+				&secondary_hash00, hash_vals);
+		lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
+				&secondary_hash01, hash_vals);
+		lookup_stage1(primary_hash10, secondary_hash10,
+			&primary_bkt10, &secondary_bkt10, h);
+		lookup_stage1(primary_hash11, secondary_hash11,
+			&primary_bkt11, &secondary_bkt11, h);
+		lookup_stage2(idx20, primary_hash20, secondary_hash20,
+			primary_bkt20, secondary_bkt20, &k_slot20, positions,
+			&extra_hits_mask, key_store, h);
+		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, positions, &hits, h);
+		lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+	}
+
+	k_slot30 = k_slot20, k_slot31 = k_slot21;
+	idx30 = idx20, idx31 = idx21;
+	primary_bkt20 = primary_bkt10;
+	primary_bkt21 = primary_bkt11;
+	secondary_bkt20 = secondary_bkt10;
+	secondary_bkt21 = secondary_bkt11;
+	primary_hash20 = primary_hash10;
+	primary_hash21 = primary_hash11;
+	secondary_hash20 = secondary_hash10;
+	secondary_hash21 = secondary_hash11;
+	idx20 = idx10, idx21 = idx11;
+	primary_hash10 = primary_hash00;
+	primary_hash11 = primary_hash01;
+	secondary_hash10 = secondary_hash00;
+	secondary_hash11 = secondary_hash01;
+	idx10 = idx00, idx11 = idx01;
+
+	lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10,
+		&secondary_bkt10, h);
+	lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11,
+		&secondary_bkt11, h);
+	lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
+		secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
+		key_store, h);
+	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, positions, &hits, h);
+	lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+
+	k_slot30 = k_slot20, k_slot31 = k_slot21;
+	idx30 = idx20, idx31 = idx21;
+	primary_bkt20 = primary_bkt10;
+	primary_bkt21 = primary_bkt11;
+	secondary_bkt20 = secondary_bkt10;
+	secondary_bkt21 = secondary_bkt11;
+	primary_hash20 = primary_hash10;
+	primary_hash21 = primary_hash11;
+	secondary_hash20 = secondary_hash10;
+	secondary_hash21 = secondary_hash11;
+	idx20 = idx10, idx21 = idx11;
+
+	lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
+		secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
+		key_store, h);
+	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, positions, &hits, h);
+	lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+
+	k_slot30 = k_slot20, k_slot31 = k_slot21;
+	idx30 = idx20, idx31 = idx21;
+
+	lookup_stage3(idx30, k_slot30, keys, positions, &hits, h);
+	lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+
+	/* handle extra_hits_mask */
+	next_mask |= extra_hits_mask;
+
+	/* ignore any items we have already found */
+	next_mask &= ~hits;
+
+	if (unlikely(next_mask)) {
+		/* run a single search for each remaining item */
+		do {
+			idx = __builtin_ctzl(next_mask);
+			positions[idx] = rte_hash_lookup_with_hash(h, keys[idx],
+								hash_vals[idx]);
+			next_mask &= ~(1llu << idx);
+		} while (next_mask);
+	}
+
+	return 0;
+}
+
 int
 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
 		      uint32_t num_keys, int32_t *positions)
@@ -982,6 +1189,19 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
 	return __rte_hash_lookup_bulk(h, keys, num_keys, positions);
 }
 
+int
+rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys,
+			const hash_sig_t *hash_vals, uint32_t num_keys,
+			int32_t *positions)
+{
+	RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
+			(num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
+			(positions == NULL)), -EINVAL);
+
+	return __rte_hash_lookup_bulk_with_hash(h, keys, hash_vals, num_keys,
+					positions);
+}
+
 /* Functions to compare multiple of 16 byte keys (up to 128 bytes) */
 static int
 rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
index 13fad73..7f7e75f 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -263,6 +263,7 @@ hash_sig_t
 rte_hash_hash(const struct rte_hash *h, const void *key);
 
 #define rte_hash_lookup_multi rte_hash_lookup_bulk
+#define rte_hash_lookup_multi_with_hash rte_hash_lookup_bulk_with_hash
 /**
  * Find multiple keys in the hash table.
  * This operation is multi-thread safe.
@@ -286,6 +287,32 @@ int
 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
 		      uint32_t num_keys, int32_t *positions);
 
+/**
+ * Find multiple keys in the hash table.
+ * This operation is multi-thread safe.
+ *
+ * @param h
+ *   Hash table to look in.
+ * @param keys
+ *   A pointer to a list of keys to look for.
+ * @param hash_vals
+ *   A pointer to a list of pre-calculated hash values.
+ * @param num_keys
+ *   How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX).
+ * @param positions
+ *   Output containing a list of values, corresponding to the list of keys that
+ *   can be used by the caller as an offset into an array of user data. These
+ *   values are unique for each key, and are the same values that were returned
+ *   when each key was added. If a key in the list was not found, then -ENOENT
+ *   will be the value.
+ * @return
+ *   -EINVAL if there's an error, otherwise 0.
+ */
+int
+rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys,
+				const hash_sig_t *hash_vals, uint32_t num_keys,
+				int32_t *positions);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map
index 0b749e8..fd92def 100644
--- a/lib/librte_hash/rte_hash_version.map
+++ b/lib/librte_hash/rte_hash_version.map
@@ -17,3 +17,11 @@ DPDK_2.0 {
 
 	local: *;
 };
+
+DPDK_2.1 {
+	global:
+
+	rte_hash_lookup_bulk_with_hash;
+
+	local: *;
+} DPDK_2.0;
-- 
2.4.2