hash: add bulk lookup with signatures array
authorVladimir Medvedkin <vladimir.medvedkin@intel.com>
Thu, 16 Apr 2020 15:07:19 +0000 (16:07 +0100)
committerThomas Monjalon <thomas@monjalon.net>
Sat, 25 Apr 2020 17:26:47 +0000 (19:26 +0200)
Implement rte_hash_lookup_with_hash_bulk_data() and
rte_hash_lookup_with_hash_bulk() - bulk lookup
functions with precomputed hash signatures.
Add these two functions into performance tests.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
Acked-by: Yipeng Wang <yipeng1.wang@intel.com>
app/test/test_hash_perf.c
lib/librte_hash/rte_cuckoo_hash.c
lib/librte_hash/rte_hash.h
lib/librte_hash/rte_hash_version.map

index a438eae..76cdac5 100644 (file)
@@ -391,8 +391,8 @@ timed_lookups(unsigned int with_hash, unsigned int with_data,
 }
 
 static int
-timed_lookups_multi(unsigned int with_data, unsigned int table_index,
-                                                       unsigned int ext)
+timed_lookups_multi(unsigned int with_hash, unsigned int with_data,
+               unsigned int table_index, unsigned int ext)
 {
        unsigned i, j, k;
        int32_t positions_burst[BURST_SIZE];
@@ -417,7 +417,7 @@ timed_lookups_multi(unsigned int with_data, unsigned int table_index,
                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];
-                       if (with_data) {
+                       if (!with_hash && with_data) {
                                ret = rte_hash_lookup_bulk_data(h[table_index],
                                        (const void **) keys_burst,
                                        BURST_SIZE,
@@ -442,6 +442,55 @@ timed_lookups_multi(unsigned int with_data, unsigned int table_index,
                                                return -1;
                                        }
                                }
+                       } else if (with_hash && with_data) {
+                               ret = rte_hash_lookup_with_hash_bulk_data(
+                                       h[table_index],
+                                       (const void **)keys_burst,
+                                       &signatures[j * BURST_SIZE],
+                                       BURST_SIZE, &hit_mask, ret_data);
+                               if (ret != BURST_SIZE) {
+                                       printf("Expect to find %u keys,"
+                                              " but found %d\n",
+                                               BURST_SIZE, ret);
+                                       return -1;
+                               }
+                               for (k = 0; k < BURST_SIZE; k++) {
+                                       if ((hit_mask & (1ULL << k))  == 0) {
+                                               printf("Key number %u"
+                                                       " not found\n",
+                                                       j * BURST_SIZE + k);
+                                               return -1;
+                                       }
+                                       expected_data[k] =
+                                               (void *)((uintptr_t)signatures[
+                                               j * BURST_SIZE + k]);
+                                       if (ret_data[k] != expected_data[k]) {
+                                               printf("Data returned for key"
+                                                       " number %u is %p,"
+                                                       " but should be %p\n",
+                                                       j * BURST_SIZE + k,
+                                                       ret_data[k],
+                                                       expected_data[k]);
+                                               return -1;
+                                       }
+                               }
+                       } else if (with_hash && !with_data) {
+                               ret = rte_hash_lookup_with_hash_bulk(
+                                       h[table_index],
+                                       (const void **)keys_burst,
+                                       &signatures[j * BURST_SIZE],
+                                       BURST_SIZE, positions_burst);
+                               for (k = 0; k < BURST_SIZE; k++) {
+                                       if (positions_burst[k] !=
+                                                       positions[j *
+                                                       BURST_SIZE + k]) {
+                                               printf("Key looked up in %d, should be in %d\n",
+                                                       positions_burst[k],
+                                                       positions[j *
+                                                       BURST_SIZE + k]);
+                                               return -1;
+                                       }
+                               }
                        } else {
                                rte_hash_lookup_bulk(h[table_index],
                                                (const void **) keys_burst,
@@ -462,7 +511,8 @@ timed_lookups_multi(unsigned int with_data, unsigned int table_index,
        const uint64_t end_tsc = rte_rdtsc();
        const uint64_t time_taken = end_tsc - start_tsc;
 
-       cycles[table_index][LOOKUP_MULTI][0][with_data] = time_taken/num_lookups;
+       cycles[table_index][LOOKUP_MULTI][with_hash][with_data] =
+               time_taken/num_lookups;
 
        return 0;
 }
@@ -543,7 +593,8 @@ run_all_tbl_perf_tests(unsigned int with_pushes, unsigned int with_locks,
                                if (timed_lookups(with_hash, with_data, i, ext) < 0)
                                        return -1;
 
-                               if (timed_lookups_multi(with_data, i, ext) < 0)
+                               if (timed_lookups_multi(with_hash, with_data,
+                                               i, ext) < 0)
                                        return -1;
 
                                if (timed_deletes(with_hash, with_data, i, ext) < 0)
index 6af8ca4..38767a8 100644 (file)
@@ -1711,64 +1711,20 @@ compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,
        }
 }
 
-#define PREFETCH_OFFSET 4
 static inline void
-__rte_hash_lookup_bulk_l(const struct rte_hash *h, const void **keys,
-                       int32_t num_keys, int32_t *positions,
-                       uint64_t *hit_mask, void *data[])
+__bulk_lookup_l(const struct rte_hash *h, const void **keys,
+               const struct rte_hash_bucket **primary_bkt,
+               const struct rte_hash_bucket **secondary_bkt,
+               uint16_t *sig, int32_t num_keys, int32_t *positions,
+               uint64_t *hit_mask, void *data[])
 {
        uint64_t hits = 0;
        int32_t i;
        int32_t ret;
-       uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
-       uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
-       uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
-       uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
-       const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
-       const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
        uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
        uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
        struct rte_hash_bucket *cur_bkt, *next_bkt;
 
-       /* Prefetch first keys */
-       for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
-               rte_prefetch0(keys[i]);
-
-       /*
-        * Prefetch rest of the keys, calculate primary and
-        * secondary bucket and prefetch them
-        */
-       for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
-               rte_prefetch0(keys[i + PREFETCH_OFFSET]);
-
-               prim_hash[i] = rte_hash_hash(h, keys[i]);
-
-               sig[i] = get_short_sig(prim_hash[i]);
-               prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
-               sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
-
-               primary_bkt[i] = &h->buckets[prim_index[i]];
-               secondary_bkt[i] = &h->buckets[sec_index[i]];
-
-               rte_prefetch0(primary_bkt[i]);
-               rte_prefetch0(secondary_bkt[i]);
-       }
-
-       /* Calculate and prefetch rest of the buckets */
-       for (; i < num_keys; i++) {
-               prim_hash[i] = rte_hash_hash(h, keys[i]);
-
-               sig[i] = get_short_sig(prim_hash[i]);
-               prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
-               sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
-
-               primary_bkt[i] = &h->buckets[prim_index[i]];
-               secondary_bkt[i] = &h->buckets[sec_index[i]];
-
-               rte_prefetch0(primary_bkt[i]);
-               rte_prefetch0(secondary_bkt[i]);
-       }
-
        __hash_rw_reader_lock(h);
 
        /* Compare signatures and prefetch key slot of first hit */
@@ -1903,63 +1859,20 @@ next_key:
 }
 
 static inline void
-__rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,
-                       int32_t num_keys, int32_t *positions,
-                       uint64_t *hit_mask, void *data[])
+__bulk_lookup_lf(const struct rte_hash *h, const void **keys,
+               const struct rte_hash_bucket **primary_bkt,
+               const struct rte_hash_bucket **secondary_bkt,
+               uint16_t *sig, int32_t num_keys, int32_t *positions,
+               uint64_t *hit_mask, void *data[])
 {
        uint64_t hits = 0;
        int32_t i;
        int32_t ret;
-       uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
-       uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
-       uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
-       uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
-       const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
-       const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
        uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
        uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
        struct rte_hash_bucket *cur_bkt, *next_bkt;
        uint32_t cnt_b, cnt_a;
 
-       /* Prefetch first keys */
-       for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
-               rte_prefetch0(keys[i]);
-
-       /*
-        * Prefetch rest of the keys, calculate primary and
-        * secondary bucket and prefetch them
-        */
-       for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
-               rte_prefetch0(keys[i + PREFETCH_OFFSET]);
-
-               prim_hash[i] = rte_hash_hash(h, keys[i]);
-
-               sig[i] = get_short_sig(prim_hash[i]);
-               prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
-               sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
-
-               primary_bkt[i] = &h->buckets[prim_index[i]];
-               secondary_bkt[i] = &h->buckets[sec_index[i]];
-
-               rte_prefetch0(primary_bkt[i]);
-               rte_prefetch0(secondary_bkt[i]);
-       }
-
-       /* Calculate and prefetch rest of the buckets */
-       for (; i < num_keys; i++) {
-               prim_hash[i] = rte_hash_hash(h, keys[i]);
-
-               sig[i] = get_short_sig(prim_hash[i]);
-               prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
-               sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
-
-               primary_bkt[i] = &h->buckets[prim_index[i]];
-               secondary_bkt[i] = &h->buckets[sec_index[i]];
-
-               rte_prefetch0(primary_bkt[i]);
-               rte_prefetch0(secondary_bkt[i]);
-       }
-
        for (i = 0; i < num_keys; i++)
                positions[i] = -ENOENT;
 
@@ -2124,6 +2037,92 @@ next_key:
                *hit_mask = hits;
 }
 
+#define PREFETCH_OFFSET 4
+static inline void
+__bulk_lookup_prefetching_loop(const struct rte_hash *h,
+       const void **keys, int32_t num_keys,
+       uint16_t *sig,
+       const struct rte_hash_bucket **primary_bkt,
+       const struct rte_hash_bucket **secondary_bkt)
+{
+       int32_t i;
+       uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
+       uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
+       uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
+
+       /* Prefetch first keys */
+       for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
+               rte_prefetch0(keys[i]);
+
+       /*
+        * Prefetch rest of the keys, calculate primary and
+        * secondary bucket and prefetch them
+        */
+       for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
+               rte_prefetch0(keys[i + PREFETCH_OFFSET]);
+
+               prim_hash[i] = rte_hash_hash(h, keys[i]);
+
+               sig[i] = get_short_sig(prim_hash[i]);
+               prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
+               sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
+
+               primary_bkt[i] = &h->buckets[prim_index[i]];
+               secondary_bkt[i] = &h->buckets[sec_index[i]];
+
+               rte_prefetch0(primary_bkt[i]);
+               rte_prefetch0(secondary_bkt[i]);
+       }
+
+       /* Calculate and prefetch rest of the buckets */
+       for (; i < num_keys; i++) {
+               prim_hash[i] = rte_hash_hash(h, keys[i]);
+
+               sig[i] = get_short_sig(prim_hash[i]);
+               prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
+               sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
+
+               primary_bkt[i] = &h->buckets[prim_index[i]];
+               secondary_bkt[i] = &h->buckets[sec_index[i]];
+
+               rte_prefetch0(primary_bkt[i]);
+               rte_prefetch0(secondary_bkt[i]);
+       }
+}
+
+
+static inline void
+__rte_hash_lookup_bulk_l(const struct rte_hash *h, const void **keys,
+                       int32_t num_keys, int32_t *positions,
+                       uint64_t *hit_mask, void *data[])
+{
+       uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
+       const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
+       const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
+
+       __bulk_lookup_prefetching_loop(h, keys, num_keys, sig,
+               primary_bkt, secondary_bkt);
+
+       __bulk_lookup_l(h, keys, primary_bkt, secondary_bkt, sig, num_keys,
+               positions, hit_mask, data);
+}
+
+static inline void
+__rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,
+                       int32_t num_keys, int32_t *positions,
+                       uint64_t *hit_mask, void *data[])
+{
+       uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
+       const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
+       const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
+
+       __bulk_lookup_prefetching_loop(h, keys, num_keys, sig,
+               primary_bkt, secondary_bkt);
+
+       __bulk_lookup_lf(h, keys, primary_bkt, secondary_bkt, sig, num_keys,
+               positions, hit_mask, data);
+}
+
 static inline void
 __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
                        int32_t num_keys, int32_t *positions,
@@ -2165,6 +2164,123 @@ rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
        return __builtin_popcountl(*hit_mask);
 }
 
+
+static inline void
+__rte_hash_lookup_with_hash_bulk_l(const struct rte_hash *h,
+                       const void **keys, hash_sig_t *prim_hash,
+                       int32_t num_keys, int32_t *positions,
+                       uint64_t *hit_mask, void *data[])
+{
+       int32_t i;
+       uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
+       uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
+       uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
+       const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
+       const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
+
+       /*
+        * Prefetch keys, calculate primary and
+        * secondary bucket and prefetch them
+        */
+       for (i = 0; i < num_keys; i++) {
+               rte_prefetch0(keys[i]);
+
+               sig[i] = get_short_sig(prim_hash[i]);
+               prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
+               sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
+
+               primary_bkt[i] = &h->buckets[prim_index[i]];
+               secondary_bkt[i] = &h->buckets[sec_index[i]];
+
+               rte_prefetch0(primary_bkt[i]);
+               rte_prefetch0(secondary_bkt[i]);
+       }
+
+       __bulk_lookup_l(h, keys, primary_bkt, secondary_bkt, sig, num_keys,
+               positions, hit_mask, data);
+}
+
+static inline void
+__rte_hash_lookup_with_hash_bulk_lf(const struct rte_hash *h,
+                       const void **keys, hash_sig_t *prim_hash,
+                       int32_t num_keys, int32_t *positions,
+                       uint64_t *hit_mask, void *data[])
+{
+       int32_t i;
+       uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
+       uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
+       uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
+       const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
+       const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
+
+       /*
+        * Prefetch keys, calculate primary and
+        * secondary bucket and prefetch them
+        */
+       for (i = 0; i < num_keys; i++) {
+               rte_prefetch0(keys[i]);
+
+               sig[i] = get_short_sig(prim_hash[i]);
+               prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
+               sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
+
+               primary_bkt[i] = &h->buckets[prim_index[i]];
+               secondary_bkt[i] = &h->buckets[sec_index[i]];
+
+               rte_prefetch0(primary_bkt[i]);
+               rte_prefetch0(secondary_bkt[i]);
+       }
+
+       __bulk_lookup_lf(h, keys, primary_bkt, secondary_bkt, sig, num_keys,
+               positions, hit_mask, data);
+}
+
+static inline void
+__rte_hash_lookup_with_hash_bulk(const struct rte_hash *h, const void **keys,
+                       hash_sig_t *prim_hash, int32_t num_keys,
+                       int32_t *positions, uint64_t *hit_mask, void *data[])
+{
+       if (h->readwrite_concur_lf_support)
+               __rte_hash_lookup_with_hash_bulk_lf(h, keys, prim_hash,
+                               num_keys, positions, hit_mask, data);
+       else
+               __rte_hash_lookup_with_hash_bulk_l(h, keys, prim_hash,
+                               num_keys, positions, hit_mask, data);
+}
+
+int
+rte_hash_lookup_with_hash_bulk(const struct rte_hash *h, const void **keys,
+               hash_sig_t *sig, uint32_t num_keys, int32_t *positions)
+{
+       RETURN_IF_TRUE(((h == NULL) || (keys == NULL) ||
+                       (sig == NULL) || (num_keys == 0) ||
+                       (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
+                       (positions == NULL)), -EINVAL);
+
+       __rte_hash_lookup_with_hash_bulk(h, keys, sig, num_keys,
+               positions, NULL, NULL);
+       return 0;
+}
+
+int
+rte_hash_lookup_with_hash_bulk_data(const struct rte_hash *h,
+               const void **keys, hash_sig_t *sig,
+               uint32_t num_keys, uint64_t *hit_mask, void *data[])
+{
+       RETURN_IF_TRUE(((h == NULL) || (keys == NULL) ||
+                       (sig == NULL) || (num_keys == 0) ||
+                       (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
+                       (hit_mask == NULL)), -EINVAL);
+
+       int32_t positions[num_keys];
+
+       __rte_hash_lookup_with_hash_bulk(h, keys, sig, num_keys,
+                       positions, hit_mask, data);
+
+       /* Return number of hits */
+       return __builtin_popcountl(*hit_mask);
+}
+
 int32_t
 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next)
 {
index ed0673b..bff4025 100644 (file)
@@ -518,6 +518,67 @@ int
 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
                      uint32_t num_keys, uint64_t *hit_mask, void *data[]);
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Find multiple keys in the hash table with precomputed hash value array.
+ * This operation is multi-thread safe with regarding to other lookup threads.
+ * Read-write concurrency can be enabled by setting flag during
+ * table creation.
+ *
+ * @param h
+ *   Hash table to look in.
+ * @param keys
+ *   A pointer to a list of keys to look for.
+ * @param sig
+ *   A pointer to a list of precomputed hash values for keys.
+ * @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.
+ */
+__rte_experimental
+int
+rte_hash_lookup_with_hash_bulk(const struct rte_hash *h, const void **keys,
+               hash_sig_t *sig, uint32_t num_keys, int32_t *positions);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Find multiple keys in the hash table with precomputed hash value array.
+ * This operation is multi-thread safe with regarding to other lookup threads.
+ * Read-write concurrency can be enabled by setting flag during
+ * table creation.
+ *
+ * @param h
+ *   Hash table to look in.
+ * @param keys
+ *   A pointer to a list of keys to look for.
+ * @param sig
+ *   A pointer to a list of precomputed hash values for keys.
+ * @param num_keys
+ *   How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX).
+ * @param hit_mask
+ *   Output containing a bitmask with all successful lookups.
+ * @param data
+ *   Output containing array of data returned from all the successful lookups.
+ * @return
+ *   -EINVAL if there's an error, otherwise number of successful lookups.
+ */
+__rte_experimental
+int
+rte_hash_lookup_with_hash_bulk_data(const struct rte_hash *h,
+               const void **keys, hash_sig_t *sig,
+               uint32_t num_keys, uint64_t *hit_mask, void *data[]);
+
 /**
  * Find multiple keys in the hash table.
  * This operation is multi-thread safe with regarding to other lookup threads.
index a8fbbc3..c2a9094 100644 (file)
@@ -33,6 +33,8 @@ EXPERIMENTAL {
        global:
 
        rte_hash_free_key_with_position;
+       rte_hash_lookup_with_hash_bulk;
+       rte_hash_lookup_with_hash_bulk_data;
        rte_hash_max_key_id;
 
 };