Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/44371/?format=api
{ "id": 44371, "url": "http://patches.dpdk.org/api/patches/44371/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/1536253745-133104-6-git-send-email-yipeng1.wang@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": "<1536253745-133104-6-git-send-email-yipeng1.wang@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1536253745-133104-6-git-send-email-yipeng1.wang@intel.com", "date": "2018-09-06T17:09:05", "name": "[v1,5/5] hash: use partial-key hashing", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "6eee0dc71513589f8bcb3ab11b66013e79d91cec", "submitter": { "id": 754, "url": "http://patches.dpdk.org/api/people/754/?format=api", "name": "Wang, Yipeng1", "email": "yipeng1.wang@intel.com" }, "delegate": { "id": 1, "url": "http://patches.dpdk.org/api/users/1/?format=api", "username": "tmonjalo", "first_name": "Thomas", "last_name": "Monjalon", "email": "thomas@monjalon.net" }, "mbox": "http://patches.dpdk.org/project/dpdk/patch/1536253745-133104-6-git-send-email-yipeng1.wang@intel.com/mbox/", "series": [ { "id": 1216, "url": "http://patches.dpdk.org/api/series/1216/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=1216", "date": "2018-09-06T17:09:00", "name": "hash: add extendable bucket and partial-key hashing", "version": 1, "mbox": "http://patches.dpdk.org/series/1216/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/44371/comments/", "check": "success", "checks": "http://patches.dpdk.org/api/patches/44371/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 [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id B0AC25689;\n\tFri, 7 Sep 2018 02:13:58 +0200 (CEST)", "from mga04.intel.com (mga04.intel.com [192.55.52.120])\n\tby dpdk.org (Postfix) with ESMTP id 8E6AF4C77\n\tfor <dev@dpdk.org>; Fri, 7 Sep 2018 02:13:50 +0200 (CEST)", "from orsmga005.jf.intel.com ([10.7.209.41])\n\tby fmsmga104.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t06 Sep 2018 17:13:47 -0700", "from skx-yipeng.jf.intel.com ([10.54.81.175])\n\tby orsmga005.jf.intel.com with ESMTP; 06 Sep 2018 17:13:47 -0700" ], "X-Amp-Result": "SKIPPED(no attachment in message)", "X-Amp-File-Uploaded": "False", "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.53,340,1531810800\"; d=\"scan'208\";a=\"255176893\"", "From": "Yipeng Wang <yipeng1.wang@intel.com>", "To": "pablo.de.lara.guarch@intel.com,\n\tbruce.richardson@intel.com", "Cc": "dev@dpdk.org, yipeng1.wang@intel.com, michel@digirati.com.br,\n\thonnappa.nagarahalli@arm.com", "Date": "Thu, 6 Sep 2018 10:09:05 -0700", "Message-Id": "<1536253745-133104-6-git-send-email-yipeng1.wang@intel.com>", "X-Mailer": "git-send-email 2.7.4", "In-Reply-To": "<1536253745-133104-1-git-send-email-yipeng1.wang@intel.com>", "References": "<1536253745-133104-1-git-send-email-yipeng1.wang@intel.com>", "Subject": "[dpdk-dev] [PATCH v1 5/5] hash: use partial-key hashing", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "DPDK patches and discussions <dev.dpdk.org>", "List-Unsubscribe": "<https://mails.dpdk.org/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://mails.dpdk.org/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<https://mails.dpdk.org/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "This commit changes the hashing mechanism to \"partial-key\nhashing\" to calculate bucket index and signature of key.\n\nThis is proposed in Bin Fan, et al's paper\n\"MemC3: Compact and Concurrent MemCache with Dumber Caching\nand Smarter Hashing\". Bascially the idea is to use \"xor\" to\nderive alternative bucket from current bucket index and\nsignature.\n\nWith \"partial-key hashing\", it reduces the bucket memory\nrequirement from two cache lines to one cache line, which\nimproves the memory efficiency and thus the lookup speed.\n\nSigned-off-by: Yipeng Wang <yipeng1.wang@intel.com>\n---\n lib/librte_hash/rte_cuckoo_hash.c | 225 ++++++++++++++++++--------------------\n lib/librte_hash/rte_cuckoo_hash.h | 6 +-\n 2 files changed, 108 insertions(+), 123 deletions(-)", "diff": "diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c\nindex ff380bb..ace47ad 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.c\n+++ b/lib/librte_hash/rte_cuckoo_hash.c\n@@ -92,6 +92,26 @@ rte_hash_cmp_eq(const void *key1, const void *key2, const struct rte_hash *h)\n \t\treturn cmp_jump_table[h->cmp_jump_table_idx](key1, key2, h->key_len);\n }\n \n+static inline void\n+get_buckets_index(const struct rte_hash *h, const hash_sig_t hash,\n+\t\tuint32_t *prim_bkt, uint32_t *sec_bkt, uint16_t *sig)\n+{\n+\t/*\n+\t * We use higher 16 bits of hash as the signature value stored in table.\n+\t * We use the lower bits for the primary bucket\n+\t * location. Then we xor primary bucket location and the signature\n+\t * to get the secondary bucket location. This is same as\n+\t * proposed in paper\" B. Fan, et al's paper\n+\t * \"Cuckoo Filter: Practically Better Than Bloom\". The benefit to use\n+\t * xor is that one could derive the alternative bucket location\n+\t * by only using the current bucket location and the signature.\n+\t */\n+\t*sig = hash >> 16;\n+\n+\t*prim_bkt = hash & h->bucket_bitmask;\n+\t*sec_bkt = (*prim_bkt ^ *sig) & h->bucket_bitmask;\n+}\n+\n struct rte_hash *\n rte_hash_create(const struct rte_hash_parameters *params)\n {\n@@ -329,9 +349,7 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \th->ext_table_support = ext_table_support;\n \n #if defined(RTE_ARCH_X86)\n-\tif (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2))\n-\t\th->sig_cmp_fn = RTE_HASH_COMPARE_AVX2;\n-\telse if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2))\n+\tif (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2))\n \t\th->sig_cmp_fn = RTE_HASH_COMPARE_SSE;\n \telse\n #endif\n@@ -418,18 +436,6 @@ rte_hash_hash(const struct rte_hash *h, const void *key)\n \treturn h->hash_func(key, h->key_len, h->hash_func_init_val);\n }\n \n-/* Calc the secondary hash value from the primary hash value of a given key */\n-static inline hash_sig_t\n-rte_hash_secondary_hash(const hash_sig_t primary_hash)\n-{\n-\tstatic const unsigned all_bits_shift = 12;\n-\tstatic const unsigned alt_bits_xor = 0x5bd1e995;\n-\n-\tuint32_t tag = primary_hash >> all_bits_shift;\n-\n-\treturn primary_hash ^ ((tag + 1) * alt_bits_xor);\n-}\n-\n int32_t\n rte_hash_count(const struct rte_hash *h)\n {\n@@ -561,14 +567,13 @@ enqueue_slot_back(const struct rte_hash *h,\n /* Search a key from bucket and update its data */\n static inline int32_t\n search_and_update(const struct rte_hash *h, void *data, const void *key,\n-\tstruct rte_hash_bucket *bkt, hash_sig_t sig, hash_sig_t alt_hash)\n+\tstruct rte_hash_bucket *bkt, uint16_t sig)\n {\n \tint i;\n \tstruct rte_hash_key *k, *keys = h->key_store;\n \n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n-\t\tif (bkt->sig_current[i] == sig &&\n-\t\t\t\tbkt->sig_alt[i] == alt_hash) {\n+\t\tif (bkt->sig_current[i] == sig) {\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tbkt->key_idx[i] * h->key_entry_size);\n \t\t\tif (rte_hash_cmp_eq(key, k->key, h) == 0) {\n@@ -595,7 +600,7 @@ rte_hash_cuckoo_insert_mw(const struct rte_hash *h,\n \t\tstruct rte_hash_bucket *prim_bkt,\n \t\tstruct rte_hash_bucket *sec_bkt,\n \t\tconst struct rte_hash_key *key, void *data,\n-\t\thash_sig_t sig, hash_sig_t alt_hash, uint32_t new_idx,\n+\t\tuint16_t sig, uint32_t new_idx,\n \t\tint32_t *ret_val)\n {\n \tunsigned int i;\n@@ -606,7 +611,7 @@ rte_hash_cuckoo_insert_mw(const struct rte_hash *h,\n \t/* Check if key was inserted after last check but before this\n \t * protected region in case of inserting duplicated keys.\n \t */\n-\tret = search_and_update(h, data, key, prim_bkt, sig, alt_hash);\n+\tret = search_and_update(h, data, key, prim_bkt, sig);\n \tif (ret != -1) {\n \t\t__hash_rw_writer_unlock(h);\n \t\t*ret_val = ret;\n@@ -614,7 +619,7 @@ rte_hash_cuckoo_insert_mw(const struct rte_hash *h,\n \t}\n \n \tFOR_EACH_BUCKET(cur_bkt, sec_bkt) {\n-\t\tret = search_and_update(h, data, key, cur_bkt, alt_hash, sig);\n+\t\tret = search_and_update(h, data, key, cur_bkt, sig);\n \t\tif (ret != -1) {\n \t\t\t__hash_rw_writer_unlock(h);\n \t\t\t*ret_val = ret;\n@@ -629,7 +634,6 @@ rte_hash_cuckoo_insert_mw(const struct rte_hash *h,\n \t\t/* Check if slot is available */\n \t\tif (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {\n \t\t\tprim_bkt->sig_current[i] = sig;\n-\t\t\tprim_bkt->sig_alt[i] = alt_hash;\n \t\t\tprim_bkt->key_idx[i] = new_idx;\n \t\t\tbreak;\n \t\t}\n@@ -654,7 +658,7 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,\n \t\t\tstruct rte_hash_bucket *alt_bkt,\n \t\t\tconst struct rte_hash_key *key, void *data,\n \t\t\tstruct queue_node *leaf, uint32_t leaf_slot,\n-\t\t\thash_sig_t sig, hash_sig_t alt_hash, uint32_t new_idx,\n+\t\t\tuint16_t sig, uint32_t new_idx,\n \t\t\tint32_t *ret_val)\n {\n \tuint32_t prev_alt_bkt_idx;\n@@ -675,7 +679,7 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,\n \t/* Check if key was inserted after last check but before this\n \t * protected region.\n \t */\n-\tret = search_and_update(h, data, key, bkt, sig, alt_hash);\n+\tret = search_and_update(h, data, key, bkt, sig);\n \tif (ret != -1) {\n \t\t__hash_rw_writer_unlock(h);\n \t\t*ret_val = ret;\n@@ -683,7 +687,7 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,\n \t}\n \n \tFOR_EACH_BUCKET(cur_bkt, alt_bkt) {\n-\t\tret = search_and_update(h, data, key, cur_bkt, alt_hash, sig);\n+\t\tret = search_and_update(h, data, key, cur_bkt, sig);\n \t\tif (ret != -1) {\n \t\t\t__hash_rw_writer_unlock(h);\n \t\t\t*ret_val = ret;\n@@ -696,8 +700,9 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,\n \t\tprev_bkt = prev_node->bkt;\n \t\tprev_slot = curr_node->prev_slot;\n \n-\t\tprev_alt_bkt_idx =\n-\t\t\tprev_bkt->sig_alt[prev_slot] & h->bucket_bitmask;\n+\t\tprev_alt_bkt_idx = (prev_node->cur_bkt_idx ^\n+\t\t\t\tprev_bkt->sig_current[prev_slot]) &\n+\t\t\t\th->bucket_bitmask;\n \n \t\tif (unlikely(&h->buckets[prev_alt_bkt_idx]\n \t\t\t\t!= curr_bkt)) {\n@@ -711,10 +716,8 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,\n \t\t * Cuckoo insert to move elements back to its\n \t\t * primary bucket if available\n \t\t */\n-\t\tcurr_bkt->sig_alt[curr_slot] =\n-\t\t\t prev_bkt->sig_current[prev_slot];\n \t\tcurr_bkt->sig_current[curr_slot] =\n-\t\t\tprev_bkt->sig_alt[prev_slot];\n+\t\t\tprev_bkt->sig_current[prev_slot];\n \t\tcurr_bkt->key_idx[curr_slot] =\n \t\t\tprev_bkt->key_idx[prev_slot];\n \n@@ -724,7 +727,6 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,\n \t}\n \n \tcurr_bkt->sig_current[curr_slot] = sig;\n-\tcurr_bkt->sig_alt[curr_slot] = alt_hash;\n \tcurr_bkt->key_idx[curr_slot] = new_idx;\n \n \t__hash_rw_writer_unlock(h);\n@@ -742,39 +744,44 @@ rte_hash_cuckoo_make_space_mw(const struct rte_hash *h,\n \t\t\tstruct rte_hash_bucket *bkt,\n \t\t\tstruct rte_hash_bucket *sec_bkt,\n \t\t\tconst struct rte_hash_key *key, void *data,\n-\t\t\thash_sig_t sig, hash_sig_t alt_hash,\n+\t\t\tuint16_t sig, uint32_t bucket_idx,\n \t\t\tuint32_t new_idx, int32_t *ret_val)\n {\n \tunsigned int i;\n \tstruct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];\n \tstruct queue_node *tail, *head;\n \tstruct rte_hash_bucket *curr_bkt, *alt_bkt;\n+\tuint32_t cur_idx, alt_idx;\n \n \ttail = queue;\n \thead = queue + 1;\n \ttail->bkt = bkt;\n \ttail->prev = NULL;\n \ttail->prev_slot = -1;\n+\ttail->cur_bkt_idx = bucket_idx;\n \n \t/* Cuckoo bfs Search */\n \twhile (likely(tail != head && head <\n \t\t\t\t\tqueue + RTE_HASH_BFS_QUEUE_MAX_LEN -\n \t\t\t\t\tRTE_HASH_BUCKET_ENTRIES)) {\n \t\tcurr_bkt = tail->bkt;\n+\t\tcur_idx = tail->cur_bkt_idx;\n \t\tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n \t\t\tif (curr_bkt->key_idx[i] == EMPTY_SLOT) {\n \t\t\t\tint32_t ret = rte_hash_cuckoo_move_insert_mw(h,\n \t\t\t\t\t\tbkt, sec_bkt, key, data,\n-\t\t\t\t\t\ttail, i, sig, alt_hash,\n+\t\t\t\t\t\ttail, i, sig,\n \t\t\t\t\t\tnew_idx, ret_val);\n \t\t\t\tif (likely(ret != -1))\n \t\t\t\t\treturn ret;\n \t\t\t}\n \n \t\t\t/* Enqueue new node and keep prev node info */\n-\t\t\talt_bkt = &(h->buckets[curr_bkt->sig_alt[i]\n-\t\t\t\t\t\t & h->bucket_bitmask]);\n+\t\t\talt_idx = (curr_bkt->sig_current[i] ^ cur_idx) &\n+\t\t\t\t\t\t\th->bucket_bitmask;\n+\t\t\talt_bkt = &(h->buckets[alt_idx]);\n \t\t\thead->bkt = alt_bkt;\n+\t\t\thead->cur_bkt_idx = alt_idx;\n \t\t\thead->prev = tail;\n \t\t\thead->prev_slot = i;\n \t\t\thead++;\n@@ -789,7 +796,7 @@ static inline int32_t\n __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \t\t\t\t\t\thash_sig_t sig, void *data)\n {\n-\thash_sig_t alt_hash;\n+\tuint16_t short_sig;\n \tuint32_t prim_bucket_idx, sec_bucket_idx;\n \tstruct rte_hash_bucket *prim_bkt, *sec_bkt, *cur_bkt;\n \tstruct rte_hash_key *new_k, *keys = h->key_store;\n@@ -804,18 +811,15 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \tint32_t ret_val;\n \tstruct rte_hash_bucket *last;\n \n-\tprim_bucket_idx = sig & h->bucket_bitmask;\n+\tget_buckets_index(h, sig, &prim_bucket_idx, &sec_bucket_idx, &short_sig);\n \tprim_bkt = &h->buckets[prim_bucket_idx];\n-\trte_prefetch0(prim_bkt);\n-\n-\talt_hash = rte_hash_secondary_hash(sig);\n-\tsec_bucket_idx = alt_hash & h->bucket_bitmask;\n \tsec_bkt = &h->buckets[sec_bucket_idx];\n+\trte_prefetch0(prim_bkt);\n \trte_prefetch0(sec_bkt);\n \n \t/* Check if key is already inserted in primary location */\n \t__hash_rw_writer_lock(h);\n-\tret = search_and_update(h, data, key, prim_bkt, sig, alt_hash);\n+\tret = search_and_update(h, data, key, prim_bkt, short_sig);\n \tif (ret != -1) {\n \t\t__hash_rw_writer_unlock(h);\n \t\treturn ret;\n@@ -823,12 +827,13 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \n \t/* Check if key is already inserted in secondary location */\n \tFOR_EACH_BUCKET(cur_bkt, sec_bkt) {\n-\t\tret = search_and_update(h, data, key, cur_bkt, alt_hash, sig);\n+\t\tret = search_and_update(h, data, key, cur_bkt, short_sig);\n \t\tif (ret != -1) {\n \t\t\t__hash_rw_writer_unlock(h);\n \t\t\treturn ret;\n \t\t}\n \t}\n+\n \t__hash_rw_writer_unlock(h);\n \n \t/* Did not find a match, so get a new slot for storing the new key */\n@@ -866,7 +871,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \n \t/* Find an empty slot and insert */\n \tret = rte_hash_cuckoo_insert_mw(h, prim_bkt, sec_bkt, key, data,\n-\t\t\t\t\tsig, alt_hash, new_idx, &ret_val);\n+\t\t\t\t\tshort_sig, new_idx, &ret_val);\n \tif (ret == 0)\n \t\treturn new_idx - 1;\n \telse if (ret == 1) {\n@@ -876,7 +881,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \n \t/* Primary bucket full, need to make space for new entry */\n \tret = rte_hash_cuckoo_make_space_mw(h, prim_bkt, sec_bkt, key, data,\n-\t\t\t\t\tsig, alt_hash, new_idx, &ret_val);\n+\t\t\t\tshort_sig, prim_bucket_idx, new_idx, &ret_val);\n \tif (ret == 0)\n \t\treturn new_idx - 1;\n \telse if (ret == 1) {\n@@ -886,7 +891,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \n \t/* Also search secondary bucket to get better occupancy */\n \tret = rte_hash_cuckoo_make_space_mw(h, sec_bkt, prim_bkt, key, data,\n-\t\t\t\t\talt_hash, sig, new_idx, &ret_val);\n+\t\t\t\tshort_sig, sec_bucket_idx, new_idx, &ret_val);\n \n \tif (ret == 0)\n \t\treturn new_idx - 1;\n@@ -907,14 +912,14 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \t__hash_rw_writer_lock(h);\n \t/* We check of duplicates again since could be added before the lock */\n \t/* Check if key is already inserted in primary location */\n-\tret = search_and_update(h, data, key, prim_bkt, sig, alt_hash);\n+\tret = search_and_update(h, data, key, prim_bkt, short_sig);\n \tif (ret != -1) {\n \t\tenqueue_slot_back(h, cached_free_slots, slot_id);\n \t\tgoto failure;\n \t}\n \n \tFOR_EACH_BUCKET(cur_bkt, sec_bkt) {\n-\t\tret = search_and_update(h, data, key, cur_bkt, alt_hash, sig);\n+\t\tret = search_and_update(h, data, key, cur_bkt, short_sig);\n \t\tif (ret != -1) {\n \t\t\tenqueue_slot_back(h, cached_free_slots, slot_id);\n \t\t\tgoto failure;\n@@ -927,8 +932,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \t\tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n \t\t\t/* Check if slot is available */\n \t\t\tif (likely(cur_bkt->key_idx[i] == EMPTY_SLOT)) {\n-\t\t\t\tcur_bkt->sig_current[i] = alt_hash;\n-\t\t\t\tcur_bkt->sig_alt[i] = sig;\n+\t\t\t\tcur_bkt->sig_current[i] = short_sig;\n \t\t\t\tcur_bkt->key_idx[i] = new_idx;\n \t\t\t\t__hash_rw_writer_unlock(h);\n \t\t\t\treturn new_idx - 1;\n@@ -946,8 +950,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \n \tbkt_id = (uint32_t)((uintptr_t) ext_bkt_id) - 1;\n \t/* Use the first location of the new bucket */\n-\t(h->buckets_ext[bkt_id]).sig_current[0] = alt_hash;\n-\t(h->buckets_ext[bkt_id]).sig_alt[0] = sig;\n+\t(h->buckets_ext[bkt_id]).sig_current[0] = short_sig;\n \t(h->buckets_ext[bkt_id]).key_idx[0] = new_idx;\n \t/* Link the new bucket to sec bucket linked list */\n \tlast = rte_hash_get_last_bkt(sec_bkt);\n@@ -1006,7 +1009,7 @@ rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data)\n \n /* Search one bucket to find the match key */\n static inline int32_t\n-search_one_bucket(const struct rte_hash *h, const void *key, hash_sig_t sig,\n+search_one_bucket(const struct rte_hash *h, const void *key, uint16_t sig,\n \t\t\tvoid **data, const struct rte_hash_bucket *bkt)\n {\n \tint i;\n@@ -1035,31 +1038,29 @@ static inline int32_t\n __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,\n \t\t\t\t\thash_sig_t sig, void **data)\n {\n-\tuint32_t bucket_idx;\n-\thash_sig_t alt_hash;\n+\tuint32_t prim_bucket_idx, sec_bucket_idx;\n \tstruct rte_hash_bucket *bkt, *cur_bkt;\n \tint ret;\n+\tuint16_t short_sig;\n \n-\tbucket_idx = sig & h->bucket_bitmask;\n-\tbkt = &h->buckets[bucket_idx];\n+\tget_buckets_index(h, sig, &prim_bucket_idx, &sec_bucket_idx, &short_sig);\n+\tbkt = &h->buckets[prim_bucket_idx];\n \n \t__hash_rw_reader_lock(h);\n \n \t/* Check if key is in primary location */\n-\tret = search_one_bucket(h, key, sig, data, bkt);\n+\tret = search_one_bucket(h, key, short_sig, data, bkt);\n \tif (ret != -1) {\n \t\t__hash_rw_reader_unlock(h);\n \t\treturn ret;\n \t}\n \n \t/* Calculate secondary hash */\n-\talt_hash = rte_hash_secondary_hash(sig);\n-\tbucket_idx = alt_hash & h->bucket_bitmask;\n-\tbkt = &h->buckets[bucket_idx];\n+\tbkt = &h->buckets[sec_bucket_idx];\n \n \t/* Check if key is in secondary location */\n \tFOR_EACH_BUCKET(cur_bkt, bkt) {\n-\t\tret = search_one_bucket(h, key, alt_hash, data, cur_bkt);\n+\t\tret = search_one_bucket(h, key, short_sig, data, cur_bkt);\n \t\tif (ret != -1) {\n \t\t\t__hash_rw_reader_unlock(h);\n \t\t\treturn ret;\n@@ -1106,7 +1107,6 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)\n \tstruct lcore_cache *cached_free_slots;\n \n \tbkt->sig_current[i] = NULL_SIGNATURE;\n-\tbkt->sig_alt[i] = NULL_SIGNATURE;\n \tif (h->multi_writer_support) {\n \t\tlcore_id = rte_lcore_id();\n \t\tcached_free_slots = &h->local_free_slots[lcore_id];\n@@ -1131,7 +1131,7 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)\n /* Search one bucket and remove the matched key */\n static inline int32_t\n search_and_remove(const struct rte_hash *h, const void *key,\n-\t\t\tstruct rte_hash_bucket *bkt, hash_sig_t sig)\n+\t\t\tstruct rte_hash_bucket *bkt, uint16_t sig)\n {\n \tstruct rte_hash_key *k, *keys = h->key_store;\n \tunsigned int i;\n@@ -1163,31 +1163,29 @@ static inline int32_t\n __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,\n \t\t\t\t\t\thash_sig_t sig)\n {\n-\tuint32_t bucket_idx;\n-\thash_sig_t alt_hash;\n+\tuint32_t prim_bucket_idx, sec_bucket_idx;\n \tstruct rte_hash_bucket *prim_bkt, *sec_bkt;\n \tstruct rte_hash_bucket *cur_bkt, *prev_bkt, *next_bkt;\n \tint32_t ret, i;\n \tstruct rte_hash_bucket *tobe_removed_bkt = NULL;\n+\tuint16_t short_sig;\n \n-\tbucket_idx = sig & h->bucket_bitmask;\n-\tprim_bkt = &h->buckets[bucket_idx];\n+\tget_buckets_index(h, sig, &prim_bucket_idx, &sec_bucket_idx, &short_sig);\n+\tprim_bkt = &h->buckets[prim_bucket_idx];\n \n \t__hash_rw_writer_lock(h);\n \t/* look for key in primary bucket */\n-\tret = search_and_remove(h, key, prim_bkt, sig);\n+\tret = search_and_remove(h, key, prim_bkt, short_sig);\n \tif (ret != -1) {\n \t\t__hash_rw_writer_unlock(h);\n \t\treturn ret;\n \t}\n \n \t/* Calculate secondary hash */\n-\talt_hash = rte_hash_secondary_hash(sig);\n-\tbucket_idx = alt_hash & h->bucket_bitmask;\n-\tsec_bkt = &h->buckets[bucket_idx];\n+\tsec_bkt = &h->buckets[sec_bucket_idx];\n \n \t/* look for key in secondary bucket */\n-\tret = search_and_remove(h, key, sec_bkt, alt_hash);\n+\tret = search_and_remove(h, key, sec_bkt, short_sig);\n \tif (ret != -1) {\n \t\t__hash_rw_writer_unlock(h);\n \t\treturn ret;\n@@ -1197,7 +1195,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,\n \tif (h->ext_table_support) {\n \t\tnext_bkt = sec_bkt->next;\n \t\tFOR_EACH_BUCKET(cur_bkt, next_bkt) {\n-\t\t\tret = search_and_remove(h, key, cur_bkt, alt_hash);\n+\t\t\tret = search_and_remove(h, key, cur_bkt, short_sig);\n \t\t\tif (ret != -1)\n \t\t\t\tgoto return_bkt;\n \t\t}\n@@ -1272,52 +1270,32 @@ static inline void\n compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,\n \t\t\tconst struct rte_hash_bucket *prim_bkt,\n \t\t\tconst struct rte_hash_bucket *sec_bkt,\n-\t\t\thash_sig_t prim_hash, hash_sig_t sec_hash,\n+\t\t\tuint16_t sig,\n \t\t\tenum rte_hash_sig_compare_function sig_cmp_fn)\n {\n \tunsigned int i;\n \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\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\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-\t\tbreak;\n-#endif\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/* Compare all signatures in the bucket */\n+\t\t*prim_hash_matches = _mm_movemask_epi8(_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-\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[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\t\t_mm_set1_epi16(sig)));\n+\t\t/* Compare all signatures in the bucket */\n+\t\t*sec_hash_matches = _mm_movemask_epi8(_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-\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[4]),\n-\t\t\t\t_mm_set1_epi32(sec_hash)))) << 4;\n+\t\t\t\t_mm_set1_epi16(sig)));\n \t\tbreak;\n #endif\n \tdefault:\n \t\tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n \t\t\t*prim_hash_matches |=\n-\t\t\t\t((prim_hash == prim_bkt->sig_current[i]) << i);\n+\t\t\t\t((sig == prim_bkt->sig_current[i]) << (i << 1));\n \t\t\t*sec_hash_matches |=\n-\t\t\t\t((sec_hash == sec_bkt->sig_current[i]) << i);\n+\t\t\t\t((sig == sec_bkt->sig_current[i]) << (i << 1));\n \t\t}\n \t}\n \n@@ -1333,7 +1311,9 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n \tint32_t i;\n \tint32_t ret;\n \tuint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];\n-\tuint32_t sec_hash[RTE_HASH_LOOKUP_BULK_MAX];\n+\tuint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];\n+\tuint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];\n+\tuint16_t sig[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@@ -1351,10 +1331,11 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n \t\trte_prefetch0(keys[i + PREFETCH_OFFSET]);\n \n \t\tprim_hash[i] = rte_hash_hash(h, keys[i]);\n-\t\tsec_hash[i] = rte_hash_secondary_hash(prim_hash[i]);\n+\t\tget_buckets_index(h, prim_hash[i],\n+\t\t\t\t&prim_index[i], &sec_index[i], &sig[i]);\n \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+\t\tprimary_bkt[i] = &h->buckets[prim_index[i]];\n+\t\tsecondary_bkt[i] = &h->buckets[sec_index[i]];\n \n \t\trte_prefetch0(primary_bkt[i]);\n \t\trte_prefetch0(secondary_bkt[i]);\n@@ -1363,10 +1344,12 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\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\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+\t\tget_buckets_index(h, prim_hash[i],\n+\t\t\t\t&prim_index[i], &sec_index[i], &sig[i]);\n+\n+\t\tprimary_bkt[i] = &h->buckets[prim_index[i]];\n+\t\tsecondary_bkt[i] = &h->buckets[sec_index[i]];\n \n \t\trte_prefetch0(primary_bkt[i]);\n \t\trte_prefetch0(secondary_bkt[i]);\n@@ -1377,10 +1360,11 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\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+\t\t\t\tsig[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 first_hit =\n+\t\t\t\t\t__builtin_ctzl(prim_hitmask[i]) >> 1;\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@@ -1391,7 +1375,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n \t\t}\n \n \t\tif (sec_hitmask[i]) {\n-\t\t\tuint32_t first_hit = __builtin_ctzl(sec_hitmask[i]);\n+\t\t\tuint32_t first_hit =\n+\t\t\t\t\t__builtin_ctzl(sec_hitmask[i]) >> 1;\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@@ -1405,7 +1390,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\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+\t\t\tuint32_t hit_index =\n+\t\t\t\t\t__builtin_ctzl(prim_hitmask[i]) >> 1;\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@@ -1424,11 +1410,12 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\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\tprim_hitmask[i] &= ~(3ULL << (hit_index << 1));\n \t\t}\n \n \t\twhile (sec_hitmask[i]) {\n-\t\t\tuint32_t hit_index = __builtin_ctzl(sec_hitmask[i]);\n+\t\t\tuint32_t hit_index =\n+\t\t\t\t\t__builtin_ctzl(sec_hitmask[i]) >> 1;\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@@ -1448,7 +1435,7 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n \t\t\t\tpositions[i] = key_idx - 1;\n \t\t\t\tgoto next_key;\n \t\t\t}\n-\t\t\tsec_hitmask[i] &= ~(1 << (hit_index));\n+\t\t\tsec_hitmask[i] &= ~(3ULL << (hit_index << 1));\n \t\t}\n \n next_key:\n@@ -1472,10 +1459,10 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n \t\tFOR_EACH_BUCKET(cur_bkt, next_bkt) {\n \t\t\tif (data != NULL)\n \t\t\t\tret = search_one_bucket(h, keys[i],\n-\t\t\t\t\t\tsec_hash[i], &data[i], cur_bkt);\n+\t\t\t\t\t\tsig[i], &data[i], cur_bkt);\n \t\t\telse\n \t\t\t\tret = search_one_bucket(h, keys[i],\n-\t\t\t\t\t\tsec_hash[i], NULL, cur_bkt);\n+\t\t\t\t\t\tsig[i], NULL, cur_bkt);\n \t\t\tif (ret != -1) {\n \t\t\t\tpositions[i] = ret;\n \t\t\t\thits |= 1ULL << i;\ndiff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h\nindex f190b04..775b93f 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.h\n+++ b/lib/librte_hash/rte_cuckoo_hash.h\n@@ -131,18 +131,15 @@ struct rte_hash_key {\n enum rte_hash_sig_compare_function {\n \tRTE_HASH_COMPARE_SCALAR = 0,\n \tRTE_HASH_COMPARE_SSE,\n-\tRTE_HASH_COMPARE_AVX2,\n \tRTE_HASH_COMPARE_NUM\n };\n \n /** Bucket structure */\n struct rte_hash_bucket {\n-\thash_sig_t sig_current[RTE_HASH_BUCKET_ENTRIES];\n+\tuint16_t sig_current[RTE_HASH_BUCKET_ENTRIES];\n \n \tuint32_t key_idx[RTE_HASH_BUCKET_ENTRIES];\n \n-\thash_sig_t sig_alt[RTE_HASH_BUCKET_ENTRIES];\n-\n \tuint8_t flag[RTE_HASH_BUCKET_ENTRIES];\n \n \tvoid *next;\n@@ -195,6 +192,7 @@ struct rte_hash {\n \n struct queue_node {\n \tstruct rte_hash_bucket *bkt; /* Current bucket on the bfs search */\n+\tuint32_t cur_bkt_idx;\n \n \tstruct queue_node *prev; /* Parent(bucket) in search path */\n \tint prev_slot; /* Parent(slot) in search path */\n", "prefixes": [ "v1", "5/5" ] }