From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga03.intel.com (mga03.intel.com [134.134.136.65]) by dpdk.org (Postfix) with ESMTP id 5B8E8C320 for ; Fri, 5 Jun 2015 16:33:27 +0200 (CEST) Received: from fmsmga001.fm.intel.com ([10.253.24.23]) by orsmga103.jf.intel.com with ESMTP; 05 Jun 2015 07:33:26 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,559,1427785200"; d="scan'208";a="721388702" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by fmsmga001.fm.intel.com with ESMTP; 05 Jun 2015 07:33:25 -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 t55EXOSH003757 for ; Fri, 5 Jun 2015 15:33:24 +0100 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t55EXOVe007130 for ; Fri, 5 Jun 2015 15:33:24 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t55EXOvI007126 for dev@dpdk.org; Fri, 5 Jun 2015 15:33:24 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Fri, 5 Jun 2015 15:33:21 +0100 Message-Id: <1433514804-7075-4-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH 3/6] 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: Fri, 05 Jun 2015 14:33:28 -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_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