[dpdk-dev] [PATCH v3 06/11] hash: add new lookup_bulk_with_hash function
Pablo de Lara
pablo.de.lara.guarch at intel.com
Mon Jun 29 00:25:25 CEST 2015
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 at 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
More information about the dev
mailing list