From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 4F7712A61 for ; Thu, 17 Sep 2015 11:04:24 +0200 (CEST) Received: from fmsmga001.fm.intel.com ([10.253.24.23]) by fmsmga102.fm.intel.com with ESMTP; 17 Sep 2015 02:04:20 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.17,545,1437462000"; d="scan'208";a="791565112" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by fmsmga001.fm.intel.com with ESMTP; 17 Sep 2015 02:04:19 -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 t8H94J2l015137; Thu, 17 Sep 2015 10:04:19 +0100 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t8H94I6v004786; Thu, 17 Sep 2015 10:04:18 +0100 Received: (from pdelarag@localhost) by sivswdev02.ir.intel.com with id t8H94I7J004780; Thu, 17 Sep 2015 10:04:18 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Thu, 17 Sep 2015 10:04:18 +0100 Message-Id: <1442480658-4741-1-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 Subject: [dpdk-dev] [PATCH] hash: fix incorrect lookup if key is all zero 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, 17 Sep 2015 09:04:25 -0000 If user has not added an all zero key in the hash table, and tries to look it up, it results in an incorrect hit, as dummy slot in the key table has all zero as well. Signed-off-by: Pablo de Lara --- doc/guides/rel_notes/release_2_2.rst | 5 +++++ lib/librte_hash/rte_cuckoo_hash.c | 27 +++++++++++++++++---------- 2 files changed, 22 insertions(+), 10 deletions(-) diff --git a/doc/guides/rel_notes/release_2_2.rst b/doc/guides/rel_notes/release_2_2.rst index 682f468..e4460f7 100644 --- a/doc/guides/rel_notes/release_2_2.rst +++ b/doc/guides/rel_notes/release_2_2.rst @@ -8,6 +8,11 @@ New Features Resolved Issues --------------- +* **hash: Fixed incorrect lookup if key is all zero. ** + +Fixed issue in hash library that occurred if an all zero +key was not added in the table and the key was looked up, +resulting in an incorrect hit. Known Issues ------------ diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 7019763..62d7143 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -861,15 +861,22 @@ lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash, /* Lookup bulk stage 3: Check if key matches, update hit mask and return data */ static inline void lookup_stage3(unsigned idx, const struct rte_hash_key *key_slot, const void * const *keys, - void *data[], uint64_t *hits, const struct rte_hash *h) + const int32_t *positions, void *data[], uint64_t *hits, + const struct rte_hash *h) { unsigned hit; + unsigned key_idx; hit = !h->rte_hash_cmp_eq(key_slot->key, keys[idx], h->key_len); if (data != NULL) data[idx] = key_slot->pdata; - *hits |= (uint64_t)(hit) << idx; + key_idx = positions[idx] + 1; + /* + * If key index is 0, force hit to be 0, in case key to be looked up + * is all zero (as in the dummy slot), which would result in a wrong hit + */ + *hits |= (uint64_t)(hit && !!key_idx) << idx; } static inline void @@ -961,8 +968,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, 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, data, &hits, h); - lookup_stage3(idx31, k_slot31, keys, data, &hits, h); + lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h); } k_slot30 = k_slot20, k_slot31 = k_slot21; @@ -988,8 +995,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, 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, data, &hits, h); - lookup_stage3(idx31, k_slot31, keys, data, &hits, h); + lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h); k_slot30 = k_slot20, k_slot31 = k_slot21; idx30 = idx20, idx31 = idx21; @@ -1009,14 +1016,14 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, 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, data, &hits, h); - lookup_stage3(idx31, k_slot31, keys, data, &hits, h); + lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h); k_slot30 = k_slot20, k_slot31 = k_slot21; idx30 = idx20, idx31 = idx21; - lookup_stage3(idx30, k_slot30, keys, data, &hits, h); - lookup_stage3(idx31, k_slot31, keys, data, &hits, h); + lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h); /* ignore any items we have already found */ extra_hits_mask &= ~hits; -- 2.4.2