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_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
