[dpdk-dev] [PATCH 3/6] hash: add new lookup_bulk_with_hash function
Pablo de Lara
pablo.de.lara.guarch at intel.com
Fri Jun 5 16:33:21 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 test as well.
Signed-off-by: Pablo de Lara <pablo.de.lara.guarch at intel.com>
---
app/test/test_hash.c | 19 ++-
lib/librte_hash/rte_hash.c | 226 ++++++++++++++++++++++++++++++++++-
lib/librte_hash/rte_hash.h | 26 ++++
lib/librte_hash/rte_hash_version.map | 8 ++
4 files changed, 275 insertions(+), 4 deletions(-)
diff --git a/app/test/test_hash.c b/app/test/test_hash.c
index 4ef99ee..5d22cb9 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_hash.c b/lib/librte_hash/rte_hash.c
index cbfe17e..9599413 100644
--- a/lib/librte_hash/rte_hash.c
+++ b/lib/librte_hash/rte_hash.c
@@ -615,6 +615,25 @@ 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,
+ uint64_t *primary_hash, uint64_t *secondary_hash,
+ const hash_sig_t *hash_vals, const struct rte_hash *h)
+{
+ *idx = __builtin_ctzl(*lookup_mask);
+ if (*lookup_mask == 0)
+ *idx = 0;
+
+ *primary_hash = hash_vals[*idx];
+ *secondary_hash = rte_hash_secondary_hash(*primary_hash);
+
+ *primary_hash |= h->sig_msb;
+
+ *secondary_hash |= h->sig_msb;
+ *secondary_hash |= h->sig_secondary;
+ *lookup_mask &= ~(1llu << *idx);
+}
/* Lookup bulk stage 1: Prefetch primary/secondary buckets */
static inline void
@@ -631,7 +650,7 @@ lookup_stage1(uint64_t primary_hash, uint64_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
@@ -880,6 +899,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;
+ uint64_t primary_hash00, primary_hash01;
+ uint64_t secondary_hash00, secondary_hash01;
+ uint64_t primary_hash10, primary_hash11;
+ uint64_t secondary_hash10, secondary_hash11;
+ uint64_t primary_hash20, primary_hash21;
+ uint64_t secondary_hash20, secondary_hash21;
+
+ if (num_keys == RTE_HASH_LOOKUP_BULK_MAX)
+ lookup_mask = 0xffffffffffffffff;
+ else
+ lookup_mask = (1 << num_keys) - 1;
+
+ lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
+ &secondary_hash00, hash_vals, h);
+ lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
+ &secondary_hash01, hash_vals, h);
+
+ 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, h);
+ lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
+ &secondary_hash01, hash_vals, h);
+ 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, h);
+ lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
+ &secondary_hash01, hash_vals, h);
+ 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, h);
+ lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
+ &secondary_hash01, hash_vals, h);
+ 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)
@@ -890,3 +1101,16 @@ 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);
+}
diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
index 4088ac4..b364a43 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -270,6 +270,7 @@ int32_t
rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
#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.
*
@@ -292,6 +293,31 @@ 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 number of hits.
+ */
+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);
+
static inline hash_sig_t
hash_alt(const uint32_t primary_hash) {
uint32_t tag = primary_hash >> RTE_HASH_ALT_BITS_SHIFT;
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