Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/16285/?format=api
{ "id": 16285, "url": "http://patches.dpdk.org/api/patches/16285/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/1475221136-213246-3-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": "<1475221136-213246-3-git-send-email-pablo.de.lara.guarch@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1475221136-213246-3-git-send-email-pablo.de.lara.guarch@intel.com", "date": "2016-09-30T07:38:54", "name": "[dpdk-dev,v4,2/4] hash: reorganize bucket structure", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "11bfe3f5485a9f40f9fd36d29c722cf8a57bdc46", "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/1475221136-213246-3-git-send-email-pablo.de.lara.guarch@intel.com/mbox/", "series": [], "comments": "http://patches.dpdk.org/api/patches/16285/comments/", "check": "pending", "checks": "http://patches.dpdk.org/api/patches/16285/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 76C556943;\n\tFri, 30 Sep 2016 09:38:13 +0200 (CEST)", "from mga01.intel.com (mga01.intel.com [192.55.52.88])\n\tby dpdk.org (Postfix) with ESMTP id 479BE5922\n\tfor <dev@dpdk.org>; Fri, 30 Sep 2016 09:37:58 +0200 (CEST)", "from orsmga004.jf.intel.com ([10.7.209.38])\n\tby fmsmga101.fm.intel.com with ESMTP; 30 Sep 2016 00:37:47 -0700", "from sie-lab-214-036.ir.intel.com (HELO\n\tsilpixa00394365.ir.intel.com) ([10.237.214.36])\n\tby orsmga004.jf.intel.com with ESMTP; 30 Sep 2016 00:37:46 -0700" ], "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.31,271,1473145200\"; d=\"scan'208\";a=\"15322663\"", "From": "Pablo de Lara <pablo.de.lara.guarch@intel.com>", "To": "dev@dpdk.org", "Cc": "bruce.richardson@intel.com, Byron Marohn <byron.marohn@intel.com>,\n\tSaikrishna Edupuganti <saikrishna.edupuganti@intel.com>", "Date": "Fri, 30 Sep 2016 08:38:54 +0100", "Message-Id": "<1475221136-213246-3-git-send-email-pablo.de.lara.guarch@intel.com>", "X-Mailer": "git-send-email 2.7.4", "In-Reply-To": "<1475221136-213246-1-git-send-email-pablo.de.lara.guarch@intel.com>", "References": "<1473190397-120741-1-git-send-email-pablo.de.lara.guarch@intel.com>\n\t<1475221136-213246-1-git-send-email-pablo.de.lara.guarch@intel.com>", "Subject": "[dpdk-dev] [PATCH v4 2/4] hash: reorganize bucket structure", "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\nMove current signatures of all entries together in the bucket\nand same with all alternative signatures, instead of having\ncurrent and alternative signatures together per entry in the bucket.\nThis will be benefitial in the next commits, where a vectorized\ncomparison will be performed, achieving better performance.\n\nThe alternative signatures have been moved away from\nthe current signatures, to make the key indices be consecutive\nto the current signatures, as these two fields are used by lookup,\nso they are in the same cache line.\n\nSigned-off-by: Byron Marohn <byron.marohn@intel.com>\nSigned-off-by: Saikrishna Edupuganti <saikrishna.edupuganti@intel.com>\n---\n lib/librte_hash/rte_cuckoo_hash.c | 43 ++++++++++++++++++-----------------\n lib/librte_hash/rte_cuckoo_hash.h | 17 ++++----------\n lib/librte_hash/rte_cuckoo_hash_x86.h | 20 ++++++++--------\n 3 files changed, 37 insertions(+), 43 deletions(-)", "diff": "diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c\nindex 4de4422..a7ee2b9 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.c\n+++ b/lib/librte_hash/rte_cuckoo_hash.c\n@@ -421,7 +421,7 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)\n \t */\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n \t\t/* Search for space in alternative locations */\n-\t\tnext_bucket_idx = bkt->signatures[i].alt & h->bucket_bitmask;\n+\t\tnext_bucket_idx = bkt->sig_alt[i] & h->bucket_bitmask;\n \t\tnext_bkt[i] = &h->buckets[next_bucket_idx];\n \t\tfor (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) {\n \t\t\tif (next_bkt[i]->key_idx[j] == EMPTY_SLOT)\n@@ -434,8 +434,8 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)\n \n \t/* Alternative location has spare room (end of recursive function) */\n \tif (i != RTE_HASH_BUCKET_ENTRIES) {\n-\t\tnext_bkt[i]->signatures[j].alt = bkt->signatures[i].current;\n-\t\tnext_bkt[i]->signatures[j].current = bkt->signatures[i].alt;\n+\t\tnext_bkt[i]->sig_alt[j] = bkt->sig_current[i];\n+\t\tnext_bkt[i]->sig_current[j] = bkt->sig_alt[i];\n \t\tnext_bkt[i]->key_idx[j] = bkt->key_idx[i];\n \t\treturn i;\n \t}\n@@ -461,8 +461,8 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)\n \t */\n \tbkt->flag[i] = 0;\n \tif (ret >= 0) {\n-\t\tnext_bkt[i]->signatures[ret].alt = bkt->signatures[i].current;\n-\t\tnext_bkt[i]->signatures[ret].current = bkt->signatures[i].alt;\n+\t\tnext_bkt[i]->sig_alt[ret] = bkt->sig_current[i];\n+\t\tnext_bkt[i]->sig_current[ret] = bkt->sig_alt[i];\n \t\tnext_bkt[i]->key_idx[ret] = bkt->key_idx[i];\n \t\treturn i;\n \t} else\n@@ -544,8 +544,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \n \t/* Check if key is already inserted in primary location */\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n-\t\tif (prim_bkt->signatures[i].current == sig &&\n-\t\t\t\tprim_bkt->signatures[i].alt == alt_hash) {\n+\t\tif (prim_bkt->sig_current[i] == sig &&\n+\t\t\t\tprim_bkt->sig_alt[i] == alt_hash) {\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tprim_bkt->key_idx[i] * h->key_entry_size);\n \t\t\tif (rte_hash_cmp_eq(key, k->key, h) == 0) {\n@@ -564,8 +564,8 @@ __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 (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n-\t\tif (sec_bkt->signatures[i].alt == sig &&\n-\t\t\t\tsec_bkt->signatures[i].current == alt_hash) {\n+\t\tif (sec_bkt->sig_alt[i] == sig &&\n+\t\t\t\tsec_bkt->sig_current[i] == alt_hash) {\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tsec_bkt->key_idx[i] * h->key_entry_size);\n \t\t\tif (rte_hash_cmp_eq(key, k->key, h) == 0) {\n@@ -611,8 +611,8 @@ __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(prim_bkt->key_idx[i] == EMPTY_SLOT)) {\n-\t\t\t\tprim_bkt->signatures[i].current = sig;\n-\t\t\t\tprim_bkt->signatures[i].alt = alt_hash;\n+\t\t\t\tprim_bkt->sig_current[i] = sig;\n+\t\t\t\tprim_bkt->sig_alt[i] = alt_hash;\n \t\t\t\tprim_bkt->key_idx[i] = new_idx;\n \t\t\t\tbreak;\n \t\t\t}\n@@ -632,8 +632,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \t\t */\n \t\tret = make_space_bucket(h, prim_bkt);\n \t\tif (ret >= 0) {\n-\t\t\tprim_bkt->signatures[ret].current = sig;\n-\t\t\tprim_bkt->signatures[ret].alt = alt_hash;\n+\t\t\tprim_bkt->sig_current[ret] = sig;\n+\t\t\tprim_bkt->sig_alt[ret] = alt_hash;\n \t\t\tprim_bkt->key_idx[ret] = new_idx;\n \t\t\tif (h->add_key == ADD_KEY_MULTIWRITER)\n \t\t\t\trte_spinlock_unlock(h->multiwriter_lock);\n@@ -707,7 +707,7 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,\n \n \t/* Check if key is in primary location */\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n-\t\tif (bkt->signatures[i].current == sig &&\n+\t\tif (bkt->sig_current[i] == sig &&\n \t\t\t\tbkt->key_idx[i] != EMPTY_SLOT) {\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tbkt->key_idx[i] * h->key_entry_size);\n@@ -730,8 +730,8 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,\n \n \t/* Check if key is in secondary location */\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n-\t\tif (bkt->signatures[i].current == alt_hash &&\n-\t\t\t\tbkt->signatures[i].alt == sig) {\n+\t\tif (bkt->sig_current[i] == alt_hash &&\n+\t\t\t\tbkt->sig_alt[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@@ -785,7 +785,8 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)\n \tunsigned lcore_id, n_slots;\n \tstruct lcore_cache *cached_free_slots;\n \n-\tbkt->signatures[i].sig = NULL_SIGNATURE;\n+\tbkt->sig_current[i] = NULL_SIGNATURE;\n+\tbkt->sig_alt[i] = NULL_SIGNATURE;\n \tif (h->hw_trans_mem_support) {\n \t\tlcore_id = rte_lcore_id();\n \t\tcached_free_slots = &h->local_free_slots[lcore_id];\n@@ -823,7 +824,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,\n \n \t/* Check if key is in primary location */\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n-\t\tif (bkt->signatures[i].current == sig &&\n+\t\tif (bkt->sig_current[i] == sig &&\n \t\t\t\tbkt->key_idx[i] != EMPTY_SLOT) {\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tbkt->key_idx[i] * h->key_entry_size);\n@@ -848,7 +849,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,\n \n \t/* Check if key is in secondary location */\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n-\t\tif (bkt->signatures[i].current == alt_hash &&\n+\t\tif (bkt->sig_current[i] == alt_hash &&\n \t\t\t\tbkt->key_idx[i] != EMPTY_SLOT) {\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tbkt->key_idx[i] * h->key_entry_size);\n@@ -957,8 +958,8 @@ lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash,\n \tprim_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;\n \tsec_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n-\t\tprim_hash_matches |= ((prim_hash == prim_bkt->signatures[i].current) << i);\n-\t\tsec_hash_matches |= ((sec_hash == sec_bkt->signatures[i].current) << i);\n+\t\tprim_hash_matches |= ((prim_hash == prim_bkt->sig_current[i]) << i);\n+\t\tsec_hash_matches |= ((sec_hash == sec_bkt->sig_current[i]) << i);\n \t}\n \n \tkey_idx = prim_bkt->key_idx[__builtin_ctzl(prim_hash_matches)];\ndiff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h\nindex 5a32ea6..24f8437 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.h\n+++ b/lib/librte_hash/rte_cuckoo_hash.h\n@@ -151,17 +151,6 @@ struct lcore_cache {\n \tvoid *objs[LCORE_CACHE_SIZE]; /**< Cache objects */\n } __rte_cache_aligned;\n \n-/* Structure storing both primary and secondary hashes */\n-struct rte_hash_signatures {\n-\tunion {\n-\t\tstruct {\n-\t\t\thash_sig_t current;\n-\t\t\thash_sig_t alt;\n-\t\t};\n-\t\tuint64_t sig;\n-\t};\n-};\n-\n /* Structure that stores key-value pair */\n struct rte_hash_key {\n \tunion {\n@@ -174,9 +163,13 @@ struct rte_hash_key {\n \n /** Bucket structure */\n struct rte_hash_bucket {\n-\tstruct rte_hash_signatures signatures[RTE_HASH_BUCKET_ENTRIES];\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+\n+\thash_sig_t sig_alt[RTE_HASH_BUCKET_ENTRIES];\n+\n \tuint8_t flag[RTE_HASH_BUCKET_ENTRIES];\n } __rte_cache_aligned;\n \ndiff --git a/lib/librte_hash/rte_cuckoo_hash_x86.h b/lib/librte_hash/rte_cuckoo_hash_x86.h\nindex e16d69c..494c160 100644\n--- a/lib/librte_hash/rte_cuckoo_hash_x86.h\n+++ b/lib/librte_hash/rte_cuckoo_hash_x86.h\n@@ -54,8 +54,8 @@ rte_hash_cuckoo_insert_mw_tm(struct rte_hash_bucket *prim_bkt,\n \t\t\tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n \t\t\t\t/* Check if slot is available */\n \t\t\t\tif (likely(prim_bkt->key_idx == EMPTY_SLOT)) {\n-\t\t\t\t\tprim_bkt->signatures[i].current = sig;\n-\t\t\t\t\tprim_bkt->signatures[i].alt = alt_hash;\n+\t\t\t\t\tprim_bkt->sig_current[i] = sig;\n+\t\t\t\t\tprim_bkt->sig_alt[i] = alt_hash;\n \t\t\t\t\tprim_bkt->key_idx[i] = new_idx;\n \t\t\t\t\tbreak;\n \t\t\t\t}\n@@ -101,7 +101,7 @@ rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h,\n \t\t\t\tprev_slot = curr_node->prev_slot;\n \n \t\t\t\tprev_alt_bkt_idx\n-\t\t\t\t\t= prev_bkt->signatures[prev_slot].alt\n+\t\t\t\t\t= prev_bkt->sig_alt[prev_slot]\n \t\t\t\t\t & h->bucket_bitmask;\n \n \t\t\t\tif (unlikely(&h->buckets[prev_alt_bkt_idx]\n@@ -113,10 +113,10 @@ rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h,\n \t\t\t\t * Cuckoo insert to move elements back to its\n \t\t\t\t * primary bucket if available\n \t\t\t\t */\n-\t\t\t\tcurr_bkt->signatures[curr_slot].alt =\n-\t\t\t\t prev_bkt->signatures[prev_slot].current;\n-\t\t\t\tcurr_bkt->signatures[curr_slot].current =\n-\t\t\t\t prev_bkt->signatures[prev_slot].alt;\n+\t\t\t\tcurr_bkt->sig_alt[curr_slot] =\n+\t\t\t\t prev_bkt->sig_current[prev_slot];\n+\t\t\t\tcurr_bkt->sig_current[curr_slot] =\n+\t\t\t\t prev_bkt->sig_alt[prev_slot];\n \t\t\t\tcurr_bkt->key_idx[curr_slot]\n \t\t\t\t = prev_bkt->key_idx[prev_slot];\n \n@@ -125,8 +125,8 @@ rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h,\n \t\t\t\tcurr_bkt = curr_node->bkt;\n \t\t\t}\n \n-\t\t\tcurr_bkt->signatures[curr_slot].current = sig;\n-\t\t\tcurr_bkt->signatures[curr_slot].alt = alt_hash;\n+\t\t\tcurr_bkt->sig_current[curr_slot] = sig;\n+\t\t\tcurr_bkt->sig_alt[curr_slot] = alt_hash;\n \t\t\tcurr_bkt->key_idx[curr_slot] = new_idx;\n \n \t\t\trte_xend();\n@@ -178,7 +178,7 @@ rte_hash_cuckoo_make_space_mw_tm(const struct rte_hash *h,\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->signatures[i].alt\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\thead->bkt = alt_bkt;\n \t\t\thead->prev = tail;\n", "prefixes": [ "dpdk-dev", "v4", "2/4" ] }