From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 1CBC4C502 for ; Mon, 29 Jun 2015 00:25:32 +0200 (CEST) Received: from orsmga003.jf.intel.com ([10.7.209.27]) by orsmga102.jf.intel.com with ESMTP; 28 Jun 2015 15:25:32 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,695,1427785200"; d="scan'208";a="596347842" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by orsmga003.jf.intel.com with ESMTP; 28 Jun 2015 15:25:31 -0700 Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com [10.237.217.46]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id t5SMPUqh030621; Sun, 28 Jun 2015 23:25:30 +0100 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t5SMPUAl010209; Sun, 28 Jun 2015 23:25:30 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t5SMPUlx010205; Sun, 28 Jun 2015 23:25:30 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Sun, 28 Jun 2015 23:25:25 +0100 Message-Id: <1435530330-10132-7-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1435269919-7007-1-git-send-email-pablo.de.lara.guarch@intel.com> <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH v3 06/11] hash: add new lookup_bulk_with_hash function X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 28 Jun 2015 22:25:34 -0000 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 --- 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