[dpdk-dev] [PATCH v3 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 tests as well.

Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
 app/test/test_hash.c                 |  19 ++-
 app/test/test_hash_perf.c            |  24 +++-
 lib/librte_hash/rte_cuckoo_hash.c    | 222 ++++++++++++++++++++++++++++++++++-
 lib/librte_hash/rte_hash.h           |  27 +++++
 lib/librte_hash/rte_hash_version.map |   8 ++
 5 files changed, 291 insertions(+), 9 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/app/test/test_hash_perf.c b/app/test/test_hash_perf.c
index 978731c..86295b8 100644
--- a/app/test/test_hash_perf.c
+++ b/app/test/test_hash_perf.c
@@ -289,18 +289,27 @@ timed_lookups(unsigned with_hash, unsigned table_index)
 }
 
 static int
-timed_lookups_multi(unsigned table_index)
+timed_lookups_multi(unsigned with_hash, unsigned table_index)
 {
 	unsigned i, j, k;
 	int32_t positions_burst[BURST_SIZE];
 	const void *keys_burst[BURST_SIZE];
 	const uint64_t start_tsc = rte_rdtsc();
+	hash_sig_t *hash_array;
 
 	for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
 		for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) {
 			for (k = 0; k < BURST_SIZE; k++)
 				keys_burst[k] = keys[j * BURST_SIZE + k];
-			rte_hash_lookup_bulk(h[table_index],
+			if (with_hash) {
+				hash_array = &signatures[j * BURST_SIZE];
+				rte_hash_lookup_bulk_with_hash(h[table_index],
+						(const void **) keys_burst,
+						(const hash_sig_t *) hash_array,
+						BURST_SIZE,
+						positions_burst);
+			} else
+				rte_hash_lookup_bulk(h[table_index],
 						(const void **) keys_burst,
 						BURST_SIZE,
 						positions_burst);
@@ -311,12 +320,12 @@ timed_lookups_multi(unsigned table_index)
 	const uint64_t time_taken = end_tsc - start_tsc;
 	const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
 
-	cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS;
+	cycles[table_index][LOOKUP_MULTI][with_hash] = time_taken/NUM_LOOKUPS;
 
 	printf("%"PRIu64" lookups in %f seconds\n", (uint64_t)NUM_LOOKUPS,
 			seconds_taken);
 	printf("Average %"PRIu64" tsc ticks per lookup\n",
-			cycles[table_index][LOOKUP_MULTI][0]);
+			cycles[table_index][LOOKUP_MULTI][with_hash]);
 	printf("Average %"PRIu64" lookups per second\n",
 			(NUM_LOOKUPS * rte_get_tsc_hz())/time_taken);
 	return 0;
@@ -398,6 +407,11 @@ run_all_tbl_perf_tests(void)
 		if (timed_lookups(1, i) < 0)
 			return -1;
 
+		printf("\nTimed lookups multi\n");
+		printf("------------------\n");
+		if (timed_lookups_multi(1, i) < 0)
+			return -1;
+
 		printf("\nTimed deletions\n");
 		printf("------------------\n");
 		if (timed_deletes(1, i) < 0)
@@ -423,7 +437,7 @@ run_all_tbl_perf_tests(void)
 
 		printf("\nTimed lookups multi\n");
 		printf("------------------\n");
-		if (timed_lookups_multi(i) < 0)
+		if (timed_lookups_multi(0, i) < 0)
 			return -1;
 
 		printf("\nTimed deletions\n");
diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 10febdc..1e70069 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -711,6 +711,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
@@ -727,7 +742,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
@@ -973,6 +988,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)
@@ -984,6 +1191,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