Patch Detail

HTTP 200 OK
Allow: GET, PUT, PATCH, HEAD, OPTIONS
Content-Type: application/json
Vary: Accept

{
    "id": 15603,
    "url": "http://patches.dpdk.org/api/patches/15603/?format=api",
    "web_url": "http://patches.dpdk.org/project/dpdk/patch/1472856999-31028-5-git-send-email-pablo.de.lara.guarch@intel.com/",
    "project": {
        "id": 1,
        "url": "http://patches.dpdk.org/api/projects/1/?format=api",
        "name": "DPDK",
        "link_name": "dpdk",
        "list_id": "dev.dpdk.org",
        "list_email": "dev@dpdk.org",
        "web_url": "http://core.dpdk.org",
        "scm_url": "git://dpdk.org/dpdk",
        "webscm_url": "http://git.dpdk.org/dpdk",
        "list_archive_url": "https://inbox.dpdk.org/dev",
        "list_archive_url_format": "https://inbox.dpdk.org/dev/{}",
        "commit_url_format": ""
    },
    "msgid": "<1472856999-31028-5-git-send-email-pablo.de.lara.guarch@intel.com>",
    "list_archive_url": "https://inbox.dpdk.org/dev/1472856999-31028-5-git-send-email-pablo.de.lara.guarch@intel.com",
    "date": "2016-09-02T22:56:39",
    "name": "[dpdk-dev,v2,4/4] hash: modify lookup bulk pipeline",
    "commit_ref": null,
    "pull_url": null,
    "state": "superseded",
    "archived": true,
    "hash": "de33d5e78e38dabb62cc3c35cb8d4a6756fad5fe",
    "submitter": {
        "id": 9,
        "url": "http://patches.dpdk.org/api/people/9/?format=api",
        "name": "De Lara Guarch, Pablo",
        "email": "pablo.de.lara.guarch@intel.com"
    },
    "delegate": null,
    "mbox": "http://patches.dpdk.org/project/dpdk/patch/1472856999-31028-5-git-send-email-pablo.de.lara.guarch@intel.com/mbox/",
    "series": [],
    "comments": "http://patches.dpdk.org/api/patches/15603/comments/",
    "check": "pending",
    "checks": "http://patches.dpdk.org/api/patches/15603/checks/",
    "tags": {},
    "related": [],
    "headers": {
        "Return-Path": "<dev-bounces@dpdk.org>",
        "X-Original-To": "patchwork@dpdk.org",
        "Delivered-To": "patchwork@dpdk.org",
        "Received": [
            "from [92.243.14.124] (localhost [IPv6:::1])\n\tby dpdk.org (Postfix) with ESMTP id B5650567A;\n\tSat,  3 Sep 2016 00:56:03 +0200 (CEST)",
            "from mga05.intel.com (mga05.intel.com [192.55.52.43])\n\tby dpdk.org (Postfix) with ESMTP id B49F4559A\n\tfor <dev@dpdk.org>; Sat,  3 Sep 2016 00:56:00 +0200 (CEST)",
            "from orsmga002.jf.intel.com ([10.7.209.21])\n\tby fmsmga105.fm.intel.com with ESMTP; 02 Sep 2016 15:56:00 -0700",
            "from sie-lab-214-036.ir.intel.com (HELO\n\tsilpixa00394365.ir.intel.com) ([10.237.214.36])\n\tby orsmga002.jf.intel.com with ESMTP; 02 Sep 2016 15:55:59 -0700"
        ],
        "X-ExtLoop1": "1",
        "X-IronPort-AV": "E=Sophos; i=\"5.30,273,1470726000\"; d=\"scan'208\";\n\ta=\"1045084215\"",
        "From": "Pablo de Lara <pablo.de.lara.guarch@intel.com>",
        "To": "dev@dpdk.org",
        "Cc": "bruce.richarson@intel.com, Byron Marohn <byron.marohn@intel.com>,\n\tSaikrishna Edupuganti <saikrishna.edupuganti@intel.com>,\n\tPablo de Lara <pablo.de.lara.guarch@intel.com>",
        "Date": "Fri,  2 Sep 2016 23:56:39 +0100",
        "Message-Id": "<1472856999-31028-5-git-send-email-pablo.de.lara.guarch@intel.com>",
        "X-Mailer": "git-send-email 2.7.4",
        "In-Reply-To": "<1472856999-31028-1-git-send-email-pablo.de.lara.guarch@intel.com>",
        "References": "<1472247287-167011-1-git-send-email-pablo.de.lara.guarch@intel.com>\n\t<1472856999-31028-1-git-send-email-pablo.de.lara.guarch@intel.com>",
        "Subject": "[dpdk-dev] [PATCH v2 4/4] hash: modify lookup bulk pipeline",
        "X-BeenThere": "dev@dpdk.org",
        "X-Mailman-Version": "2.1.15",
        "Precedence": "list",
        "List-Id": "patches and discussions about DPDK <dev.dpdk.org>",
        "List-Unsubscribe": "<http://dpdk.org/ml/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>",
        "List-Archive": "<http://dpdk.org/ml/archives/dev/>",
        "List-Post": "<mailto:dev@dpdk.org>",
        "List-Help": "<mailto:dev-request@dpdk.org?subject=help>",
        "List-Subscribe": "<http://dpdk.org/ml/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>",
        "Errors-To": "dev-bounces@dpdk.org",
        "Sender": "\"dev\" <dev-bounces@dpdk.org>"
    },
    "content": "From: Byron Marohn <byron.marohn@intel.com>\n\nThis patch replaces the pipelined rte_hash lookup mechanism with a\nloop-and-jump model, which performs significantly better,\nespecially for smaller table sizes and smaller table occupancies.\n\nSigned-off-by: Byron Marohn <byron.marohn@intel.com>\nSigned-off-by: Saikrishna Edupuganti <saikrishna.edupuganti@intel.com>\nSigned-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>\n---\n lib/librte_hash/rte_cuckoo_hash.c | 377 ++++++++++++--------------------------\n lib/librte_hash/rte_cuckoo_hash.h |   3 +-\n 2 files changed, 117 insertions(+), 263 deletions(-)",
    "diff": "diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c\nindex eab28a1..47b5beb 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.c\n+++ b/lib/librte_hash/rte_cuckoo_hash.c\n@@ -913,43 +913,8 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,\n \treturn 0;\n }\n \n-/* Lookup bulk stage 0: Prefetch input key */\n static inline void\n-lookup_stage0(unsigned *idx, uint64_t *lookup_mask,\n-\t\tconst void * const *keys)\n-{\n-\t*idx = __builtin_ctzl(*lookup_mask);\n-\tif (*lookup_mask == 0)\n-\t\t*idx = 0;\n-\n-\trte_prefetch0(keys[*idx]);\n-\t*lookup_mask &= ~(1llu << *idx);\n-}\n-\n-/*\n- * Lookup bulk stage 1: Calculate primary/secondary hashes\n- * and prefetch primary/secondary buckets\n- */\n-static inline void\n-lookup_stage1(unsigned idx, hash_sig_t *prim_hash, hash_sig_t *sec_hash,\n-\t\tconst struct rte_hash_bucket **primary_bkt,\n-\t\tconst struct rte_hash_bucket **secondary_bkt,\n-\t\thash_sig_t *hash_vals, const void * const *keys,\n-\t\tconst struct rte_hash *h)\n-{\n-\t*prim_hash = rte_hash_hash(h, keys[idx]);\n-\thash_vals[idx] = *prim_hash;\n-\t*sec_hash = rte_hash_secondary_hash(*prim_hash);\n-\n-\t*primary_bkt = &h->buckets[*prim_hash & h->bucket_bitmask];\n-\t*secondary_bkt = &h->buckets[*sec_hash & h->bucket_bitmask];\n-\n-\trte_prefetch0(*primary_bkt);\n-\trte_prefetch0(*secondary_bkt);\n-}\n-\n-static inline void\n-compare_signatures(unsigned *prim_hash_matches, unsigned *sec_hash_matches,\n+compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,\n \t\t\t\tconst struct rte_hash_bucket *prim_bkt,\n \t\t\t\tconst struct rte_hash_bucket *sec_bkt,\n \t\t\t\thash_sig_t prim_hash, hash_sig_t sec_hash,\n@@ -960,11 +925,11 @@ compare_signatures(unsigned *prim_hash_matches, unsigned *sec_hash_matches,\n \tswitch (sig_cmp_fn) {\n #ifdef RTE_MACHINE_CPUFLAG_AVX2\n \tcase RTE_HASH_COMPARE_AVX2:\n-\t\t*prim_hash_matches |= _mm256_movemask_ps((__m256)_mm256_cmpeq_epi32(\n+\t\t*prim_hash_matches = _mm256_movemask_ps((__m256)_mm256_cmpeq_epi32(\n \t\t\t\t_mm256_load_si256(\n \t\t\t\t\t(__m256i const *)prim_bkt->sig_current),\n \t\t\t\t_mm256_set1_epi32(prim_hash)));\n-\t\t*sec_hash_matches |= _mm256_movemask_ps((__m256)_mm256_cmpeq_epi32(\n+\t\t*sec_hash_matches = _mm256_movemask_ps((__m256)_mm256_cmpeq_epi32(\n \t\t\t\t_mm256_load_si256(\n \t\t\t\t\t(__m256i const *)sec_bkt->sig_current),\n \t\t\t\t_mm256_set1_epi32(sec_hash)));\n@@ -973,7 +938,7 @@ compare_signatures(unsigned *prim_hash_matches, unsigned *sec_hash_matches,\n #ifdef RTE_MACHINE_CPUFLAG_SSE2\n \tcase RTE_HASH_COMPARE_SSE:\n \t\t/* Compare the first 4 signatures in the bucket */\n-\t\t*prim_hash_matches |= _mm_movemask_ps((__m128)_mm_cmpeq_epi16(\n+\t\t*prim_hash_matches = _mm_movemask_ps((__m128)_mm_cmpeq_epi16(\n \t\t\t\t_mm_load_si128(\n \t\t\t\t\t(__m128i const *)prim_bkt->sig_current),\n \t\t\t\t_mm_set1_epi32(prim_hash)));\n@@ -982,7 +947,7 @@ compare_signatures(unsigned *prim_hash_matches, unsigned *sec_hash_matches,\n \t\t\t\t\t(__m128i const *)&prim_bkt->sig_current[4]),\n \t\t\t\t_mm_set1_epi32(prim_hash)))) << 4;\n \t\t/* Compare the first 4 signatures in the bucket */\n-\t\t*sec_hash_matches |= _mm_movemask_ps((__m128)_mm_cmpeq_epi16(\n+\t\t*sec_hash_matches = _mm_movemask_ps((__m128)_mm_cmpeq_epi16(\n \t\t\t\t_mm_load_si128(\n \t\t\t\t\t(__m128i const *)sec_bkt->sig_current),\n \t\t\t\t_mm_set1_epi32(sec_hash)));\n@@ -1003,244 +968,134 @@ compare_signatures(unsigned *prim_hash_matches, unsigned *sec_hash_matches,\n \n }\n \n-/*\n- * Lookup bulk stage 2:  Search for match hashes in primary/secondary locations\n- * and prefetch first key slot\n- */\n+#define PREFETCH_OFFSET 4\n static inline void\n-lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash,\n-\t\tconst struct rte_hash_bucket *prim_bkt,\n-\t\tconst struct rte_hash_bucket *sec_bkt,\n-\t\tconst struct rte_hash_key **key_slot, int32_t *positions,\n-\t\tuint64_t *extra_hits_mask, const void *keys,\n-\t\tconst struct rte_hash *h)\n+__rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n+\t\t\tint32_t num_keys, int32_t *positions,\n+\t\t\tuint64_t *hit_mask, void *data[])\n {\n-\tunsigned prim_hash_matches, sec_hash_matches, key_idx;\n-\tunsigned total_hash_matches;\n+\tuint64_t hits = 0;\n+\tint32_t i;\n+\tuint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];\n+\tuint32_t sec_hash[RTE_HASH_LOOKUP_BULK_MAX];\n+\tconst struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];\n+\tconst struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];\n+\tuint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};\n+\tuint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};\n+\n+\t/* Prefetch first keys */\n+\tfor (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)\n+\t\trte_prefetch0(keys[i]);\n \n-\tprim_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;\n-\tsec_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;\n+\t/*\n+\t * Prefetch rest of the keys, calculate primary and\n+\t * secondary bucket and prefetch them\n+\t */\n+\tfor (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {\n+\t\trte_prefetch0(keys[i + PREFETCH_OFFSET]);\n \n-\tcompare_signatures(&prim_hash_matches, &sec_hash_matches, prim_bkt,\n-\t\t\t\tsec_bkt, prim_hash, sec_hash, h->sig_cmp_fn);\n+\t\tprim_hash[i] = rte_hash_hash(h, keys[i]);\n+\t\tsec_hash[i] = rte_hash_secondary_hash(prim_hash[i]);\n \n-\tkey_idx = prim_bkt->key_idx[__builtin_ctzl(prim_hash_matches)];\n-\tif (key_idx == 0)\n-\t\tkey_idx = sec_bkt->key_idx[__builtin_ctzl(sec_hash_matches)];\n+\t\tprimary_bkt[i] = &h->buckets[prim_hash[i] & h->bucket_bitmask];\n+\t\tsecondary_bkt[i] = &h->buckets[sec_hash[i] & h->bucket_bitmask];\n \n-\ttotal_hash_matches = (prim_hash_matches |\n-\t\t\t\t(sec_hash_matches << (RTE_HASH_BUCKET_ENTRIES + 1)));\n-\t*key_slot = (const struct rte_hash_key *) ((const char *)keys +\n-\t\t\t\t\tkey_idx * h->key_entry_size);\n+\t\trte_prefetch0(primary_bkt[i]);\n+\t\trte_prefetch0(secondary_bkt[i]);\n+\t}\n \n-\trte_prefetch0(*key_slot);\n-\t/*\n-\t * Return index where key is stored,\n-\t * substracting the first dummy index\n-\t */\n-\tpositions[idx] = (key_idx - 1);\n+\t/* Calculate and prefetch rest of the buckets */\n+\tfor (; i < num_keys; i++) {\n+\t\tprim_hash[i] = rte_hash_hash(h, keys[i]);\n+\t\tsec_hash[i] = rte_hash_secondary_hash(prim_hash[i]);\n \n-\t*extra_hits_mask |= (uint64_t)(__builtin_popcount(total_hash_matches) > 3) << idx;\n+\t\tprimary_bkt[i] = &h->buckets[prim_hash[i] & h->bucket_bitmask];\n+\t\tsecondary_bkt[i] = &h->buckets[sec_hash[i] & h->bucket_bitmask];\n \n-}\n+\t\trte_prefetch0(primary_bkt[i]);\n+\t\trte_prefetch0(secondary_bkt[i]);\n+\t}\n \n+\t/* Compare signatures and prefetch key slot of first hit */\n+\tfor (i = 0; i < num_keys; i++) {\n+\t\tcompare_signatures(&prim_hitmask[i], &sec_hitmask[i],\n+\t\t\t\tprimary_bkt[i], secondary_bkt[i],\n+\t\t\t\tprim_hash[i], sec_hash[i], h->sig_cmp_fn);\n+\n+\t\tif (prim_hitmask[i]) {\n+\t\t\tuint32_t first_hit = __builtin_ctzl(prim_hitmask[i]);\n+\t\t\tuint32_t key_idx = primary_bkt[i]->key_idx[first_hit];\n+\t\t\tconst struct rte_hash_key *key_slot =\n+\t\t\t\t(const struct rte_hash_key *)(\n+\t\t\t\t(const char *)h->key_store +\n+\t\t\t\tkey_idx * h->key_entry_size);\n+\t\t\trte_prefetch0(key_slot);\n+\t\t\tcontinue;\n+\t\t}\n \n-/* Lookup bulk stage 3: Check if key matches, update hit mask and return data */\n-static inline void\n-lookup_stage3(unsigned idx, const struct rte_hash_key *key_slot, const void * const *keys,\n-\t\tconst int32_t *positions, void *data[], uint64_t *hits,\n-\t\tconst struct rte_hash *h)\n-{\n-\tunsigned hit;\n-\tunsigned key_idx;\n+\t\tif (sec_hitmask[i]) {\n+\t\t\tuint32_t first_hit = __builtin_ctzl(sec_hitmask[i]);\n+\t\t\tuint32_t key_idx = secondary_bkt[i]->key_idx[first_hit];\n+\t\t\tconst struct rte_hash_key *key_slot =\n+\t\t\t\t(const struct rte_hash_key *)(\n+\t\t\t\t(const char *)h->key_store +\n+\t\t\t\tkey_idx * h->key_entry_size);\n+\t\t\trte_prefetch0(key_slot);\n+\t\t}\n+\t}\n \n-\thit = !rte_hash_cmp_eq(key_slot->key, keys[idx], h);\n-\tif (data != NULL)\n-\t\tdata[idx] = key_slot->pdata;\n+\t/* Compare keys, first hits in primary first */\n+\tfor (i = 0; i < num_keys; i++) {\n+\t\tpositions[i] = -ENOENT;\n+\t\twhile (prim_hitmask[i]) {\n+\t\t\tuint32_t hit_index = __builtin_ctzl(prim_hitmask[i]);\n+\n+\t\t\tuint32_t key_idx = primary_bkt[i]->key_idx[hit_index];\n+\t\t\tconst struct rte_hash_key *key_slot =\n+\t\t\t\t(const struct rte_hash_key *)(\n+\t\t\t\t(const char *)h->key_store +\n+\t\t\t\tkey_idx * h->key_entry_size);\n+\t\t\t/*\n+\t\t\t * If key index is 0, do not compare key,\n+\t\t\t * as it is checking the dummy slot\n+\t\t\t */\n+\t\t\tif (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) {\n+\t\t\t\tif (data != NULL)\n+\t\t\t\t\tdata[i] = key_slot->pdata;\n \n-\tkey_idx = positions[idx] + 1;\n-\t/*\n-\t * If key index is 0, force hit to be 0, in case key to be looked up\n-\t * is all zero (as in the dummy slot), which would result in a wrong hit\n-\t */\n-\t*hits |= (uint64_t)(hit && !!key_idx)  << idx;\n-}\n+\t\t\t\thits |= 1ULL << i;\n+\t\t\t\tpositions[i] = key_idx - 1;\n+\t\t\t\tgoto next_key;\n+\t\t\t}\n+\t\t\tprim_hitmask[i] &= ~(1 << (hit_index));\n+\t\t}\n \n-static inline void\n-__rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n-\t\t\tuint32_t num_keys, int32_t *positions,\n-\t\t\tuint64_t *hit_mask, void *data[])\n-{\n-\tuint64_t hits = 0;\n-\tuint64_t extra_hits_mask = 0;\n-\tuint64_t lookup_mask, miss_mask;\n-\tunsigned idx;\n-\tconst void *key_store = h->key_store;\n-\tint ret;\n-\thash_sig_t hash_vals[RTE_HASH_LOOKUP_BULK_MAX];\n-\n-\tunsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31;\n-\tconst struct rte_hash_bucket *primary_bkt10, *primary_bkt11;\n-\tconst struct rte_hash_bucket *secondary_bkt10, *secondary_bkt11;\n-\tconst struct rte_hash_bucket *primary_bkt20, *primary_bkt21;\n-\tconst struct rte_hash_bucket *secondary_bkt20, *secondary_bkt21;\n-\tconst struct rte_hash_key *k_slot20, *k_slot21, *k_slot30, *k_slot31;\n-\thash_sig_t primary_hash10, primary_hash11;\n-\thash_sig_t secondary_hash10, secondary_hash11;\n-\thash_sig_t primary_hash20, primary_hash21;\n-\thash_sig_t secondary_hash20, secondary_hash21;\n-\n-\tlookup_mask = (uint64_t) -1 >> (64 - num_keys);\n-\tmiss_mask = lookup_mask;\n-\n-\tlookup_stage0(&idx00, &lookup_mask, keys);\n-\tlookup_stage0(&idx01, &lookup_mask, keys);\n-\n-\tidx10 = idx00, idx11 = idx01;\n-\n-\tlookup_stage0(&idx00, &lookup_mask, keys);\n-\tlookup_stage0(&idx01, &lookup_mask, keys);\n-\tlookup_stage1(idx10, &primary_hash10, &secondary_hash10,\n-\t\t\t&primary_bkt10, &secondary_bkt10, hash_vals, keys, h);\n-\tlookup_stage1(idx11, &primary_hash11, &secondary_hash11,\n-\t\t\t&primary_bkt11,\t&secondary_bkt11, hash_vals, keys, h);\n-\n-\tprimary_bkt20 = primary_bkt10;\n-\tprimary_bkt21 = primary_bkt11;\n-\tsecondary_bkt20 = secondary_bkt10;\n-\tsecondary_bkt21 = secondary_bkt11;\n-\tprimary_hash20 = primary_hash10;\n-\tprimary_hash21 = primary_hash11;\n-\tsecondary_hash20 = secondary_hash10;\n-\tsecondary_hash21 = secondary_hash11;\n-\tidx20 = idx10, idx21 = idx11;\n-\tidx10 = idx00, idx11 = idx01;\n-\n-\tlookup_stage0(&idx00, &lookup_mask, keys);\n-\tlookup_stage0(&idx01, &lookup_mask, keys);\n-\tlookup_stage1(idx10, &primary_hash10, &secondary_hash10,\n-\t\t\t&primary_bkt10, &secondary_bkt10, hash_vals, keys, h);\n-\tlookup_stage1(idx11, &primary_hash11, &secondary_hash11,\n-\t\t\t&primary_bkt11,\t&secondary_bkt11, hash_vals, keys, h);\n-\tlookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,\n-\t\t\tsecondary_bkt20, &k_slot20, positions, &extra_hits_mask,\n-\t\t\tkey_store, h);\n-\tlookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,\n-\t\t\tsecondary_bkt21, &k_slot21, positions, &extra_hits_mask,\n-\t\t\tkey_store, h);\n-\n-\twhile (lookup_mask) {\n-\t\tk_slot30 = k_slot20, k_slot31 = k_slot21;\n-\t\tidx30 = idx20, idx31 = idx21;\n-\t\tprimary_bkt20 = primary_bkt10;\n-\t\tprimary_bkt21 = primary_bkt11;\n-\t\tsecondary_bkt20 = secondary_bkt10;\n-\t\tsecondary_bkt21 = secondary_bkt11;\n-\t\tprimary_hash20 = primary_hash10;\n-\t\tprimary_hash21 = primary_hash11;\n-\t\tsecondary_hash20 = secondary_hash10;\n-\t\tsecondary_hash21 = secondary_hash11;\n-\t\tidx20 = idx10, idx21 = idx11;\n-\t\tidx10 = idx00, idx11 = idx01;\n-\n-\t\tlookup_stage0(&idx00, &lookup_mask, keys);\n-\t\tlookup_stage0(&idx01, &lookup_mask, keys);\n-\t\tlookup_stage1(idx10, &primary_hash10, &secondary_hash10,\n-\t\t\t&primary_bkt10, &secondary_bkt10, hash_vals, keys, h);\n-\t\tlookup_stage1(idx11, &primary_hash11, &secondary_hash11,\n-\t\t\t&primary_bkt11,\t&secondary_bkt11, hash_vals, keys, h);\n-\t\tlookup_stage2(idx20, primary_hash20, secondary_hash20,\n-\t\t\tprimary_bkt20, secondary_bkt20, &k_slot20, positions,\n-\t\t\t&extra_hits_mask, key_store, h);\n-\t\tlookup_stage2(idx21, primary_hash21, secondary_hash21,\n-\t\t\tprimary_bkt21, secondary_bkt21,\t&k_slot21, positions,\n-\t\t\t&extra_hits_mask, key_store, h);\n-\t\tlookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);\n-\t\tlookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);\n-\t}\n+\t\twhile (sec_hitmask[i]) {\n+\t\t\tuint32_t hit_index = __builtin_ctzl(sec_hitmask[i]);\n+\n+\t\t\tuint32_t key_idx = secondary_bkt[i]->key_idx[hit_index];\n+\t\t\tconst struct rte_hash_key *key_slot =\n+\t\t\t\t(const struct rte_hash_key *)(\n+\t\t\t\t(const char *)h->key_store +\n+\t\t\t\tkey_idx * h->key_entry_size);\n+\t\t\t/*\n+\t\t\t * If key index is 0, do not compare key,\n+\t\t\t * as it is checking the dummy slot\n+\t\t\t */\n+\n+\t\t\tif (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) {\n+\t\t\t\tif (data != NULL)\n+\t\t\t\t\tdata[i] = key_slot->pdata;\n \n-\tk_slot30 = k_slot20, k_slot31 = k_slot21;\n-\tidx30 = idx20, idx31 = idx21;\n-\tprimary_bkt20 = primary_bkt10;\n-\tprimary_bkt21 = primary_bkt11;\n-\tsecondary_bkt20 = secondary_bkt10;\n-\tsecondary_bkt21 = secondary_bkt11;\n-\tprimary_hash20 = primary_hash10;\n-\tprimary_hash21 = primary_hash11;\n-\tsecondary_hash20 = secondary_hash10;\n-\tsecondary_hash21 = secondary_hash11;\n-\tidx20 = idx10, idx21 = idx11;\n-\tidx10 = idx00, idx11 = idx01;\n-\n-\tlookup_stage1(idx10, &primary_hash10, &secondary_hash10,\n-\t\t&primary_bkt10, &secondary_bkt10, hash_vals, keys, h);\n-\tlookup_stage1(idx11, &primary_hash11, &secondary_hash11,\n-\t\t&primary_bkt11,\t&secondary_bkt11, hash_vals, keys, h);\n-\tlookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,\n-\t\tsecondary_bkt20, &k_slot20, positions, &extra_hits_mask,\n-\t\tkey_store, h);\n-\tlookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,\n-\t\tsecondary_bkt21, &k_slot21, positions, &extra_hits_mask,\n-\t\tkey_store, h);\n-\tlookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);\n-\tlookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);\n-\n-\tk_slot30 = k_slot20, k_slot31 = k_slot21;\n-\tidx30 = idx20, idx31 = idx21;\n-\tprimary_bkt20 = primary_bkt10;\n-\tprimary_bkt21 = primary_bkt11;\n-\tsecondary_bkt20 = secondary_bkt10;\n-\tsecondary_bkt21 = secondary_bkt11;\n-\tprimary_hash20 = primary_hash10;\n-\tprimary_hash21 = primary_hash11;\n-\tsecondary_hash20 = secondary_hash10;\n-\tsecondary_hash21 = secondary_hash11;\n-\tidx20 = idx10, idx21 = idx11;\n-\n-\tlookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,\n-\t\tsecondary_bkt20, &k_slot20, positions, &extra_hits_mask,\n-\t\tkey_store, h);\n-\tlookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,\n-\t\tsecondary_bkt21, &k_slot21, positions, &extra_hits_mask,\n-\t\tkey_store, h);\n-\tlookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);\n-\tlookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);\n-\n-\tk_slot30 = k_slot20, k_slot31 = k_slot21;\n-\tidx30 = idx20, idx31 = idx21;\n-\n-\tlookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);\n-\tlookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);\n-\n-\t/* ignore any items we have already found */\n-\textra_hits_mask &= ~hits;\n-\n-\tif (unlikely(extra_hits_mask)) {\n-\t\t/* run a single search for each remaining item */\n-\t\tdo {\n-\t\t\tidx = __builtin_ctzl(extra_hits_mask);\n-\t\t\tif (data != NULL) {\n-\t\t\t\tret = rte_hash_lookup_with_hash_data(h,\n-\t\t\t\t\t\tkeys[idx], hash_vals[idx], &data[idx]);\n-\t\t\t\tif (ret >= 0)\n-\t\t\t\t\thits |= 1ULL << idx;\n-\t\t\t} else {\n-\t\t\t\tpositions[idx] = rte_hash_lookup_with_hash(h,\n-\t\t\t\t\t\t\tkeys[idx], hash_vals[idx]);\n-\t\t\t\tif (positions[idx] >= 0)\n-\t\t\t\t\thits |= 1llu << idx;\n+\t\t\t\thits |= 1ULL << i;\n+\t\t\t\tpositions[i] = key_idx - 1;\n+\t\t\t\tgoto next_key;\n \t\t\t}\n-\t\t\textra_hits_mask &= ~(1llu << idx);\n-\t\t} while (extra_hits_mask);\n-\t}\n+\t\t\tsec_hitmask[i] &= ~(1 << (hit_index));\n+\t\t}\n \n-\tmiss_mask &= ~hits;\n-\tif (unlikely(miss_mask)) {\n-\t\tdo {\n-\t\t\tidx = __builtin_ctzl(miss_mask);\n-\t\t\tpositions[idx] = -ENOENT;\n-\t\t\tmiss_mask &= ~(1llu << idx);\n-\t\t} while (miss_mask);\n+next_key:\n+\t\tcontinue;\n \t}\n \n \tif (hit_mask != NULL)\ndiff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h\nindex 8ffc146..986596f 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.h\n+++ b/lib/librte_hash/rte_cuckoo_hash.h\n@@ -173,8 +173,7 @@ enum rte_hash_sig_compare_function {\n struct rte_hash_bucket {\n \thash_sig_t sig_current[RTE_HASH_BUCKET_ENTRIES];\n \n-\t/* Includes dummy key index that always contains index 0 */\n-\tuint32_t key_idx[RTE_HASH_BUCKET_ENTRIES + 1];\n+\tuint32_t key_idx[RTE_HASH_BUCKET_ENTRIES];\n \n \tuint8_t flag[RTE_HASH_BUCKET_ENTRIES];\n \n",
    "prefixes": [
        "dpdk-dev",
        "v2",
        "4/4"
    ]
}