From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id 0A515C766 for ; Fri, 26 Jun 2015 00:08:33 +0200 (CEST) Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by orsmga101.jf.intel.com with ESMTP; 25 Jun 2015 15:08:31 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,680,1427785200"; d="scan'208";a="750578488" Received: from msvmon001.ims.intel.com ([10.125.148.15]) by fmsmga002.fm.intel.com with ESMTP; 25 Jun 2015 15:08:30 -0700 Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com [10.237.217.46]) by msvmon001.ims.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id t5PM8TLX028738; Fri, 26 Jun 2015 01:08:29 +0300 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t5PM5K2O007089; Thu, 25 Jun 2015 23:05:20 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t5PM5KM2007085; Thu, 25 Jun 2015 23:05:20 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Thu, 25 Jun 2015 23:05:14 +0100 Message-Id: <1435269919-7007-7-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1435269919-7007-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> <1435269919-7007-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH v2 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: Thu, 25 Jun 2015 22:08: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 test as well. Signed-off-by: Pablo de Lara --- 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