Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/133936/?format=api
{ "id": 133936, "url": "http://patches.dpdk.org/api/patches/133936/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/20231107121845.2758454-2-yoan.picchi@arm.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": "<20231107121845.2758454-2-yoan.picchi@arm.com>", "list_archive_url": "https://inbox.dpdk.org/dev/20231107121845.2758454-2-yoan.picchi@arm.com", "date": "2023-11-07T12:18:42", "name": "[v3,1/4] hash: pack the hitmask for hash in bulk lookup", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "aa83dadc052f43ce1dce9429d320028246381c89", "submitter": { "id": 3196, "url": "http://patches.dpdk.org/api/people/3196/?format=api", "name": "Yoan Picchi", "email": "yoan.picchi@arm.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/20231107121845.2758454-2-yoan.picchi@arm.com/mbox/", "series": [ { "id": 30183, "url": "http://patches.dpdk.org/api/series/30183/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=30183", "date": "2023-11-07T12:18:41", "name": "hash: add SVE support for bulk key lookup", "version": 3, "mbox": "http://patches.dpdk.org/series/30183/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/133936/comments/", "check": "warning", "checks": "http://patches.dpdk.org/api/patches/133936/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@inbox.dpdk.org", "Delivered-To": "patchwork@inbox.dpdk.org", "Received": [ "from mails.dpdk.org (mails.dpdk.org [217.70.189.124])\n\tby inbox.dpdk.org (Postfix) with ESMTP id 2F6B3432C7;\n\tTue, 7 Nov 2023 14:05:11 +0100 (CET)", "from mails.dpdk.org (localhost [127.0.0.1])\n\tby mails.dpdk.org (Postfix) with ESMTP id 16C68410E6;\n\tTue, 7 Nov 2023 14:05:00 +0100 (CET)", "from foss.arm.com (foss.arm.com [217.140.110.172])\n by mails.dpdk.org (Postfix) with ESMTP id 6FD4740ED2\n for <dev@dpdk.org>; Tue, 7 Nov 2023 13:19:00 +0100 (CET)", "from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14])\n by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 90FDC1476;\n Tue, 7 Nov 2023 04:19:44 -0800 (PST)", "from ampere-altra-2-2.usa.Arm.com (unknown [10.118.91.160])\n by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id D3AD53F766;\n Tue, 7 Nov 2023 04:18:59 -0800 (PST)" ], "From": "Yoan Picchi <yoan.picchi@arm.com>", "To": "Thomas Monjalon <thomas@monjalon.net>,\n Yipeng Wang <yipeng1.wang@intel.com>,\n Sameh Gobriel <sameh.gobriel@intel.com>,\n Bruce Richardson <bruce.richardson@intel.com>,\n Vladimir Medvedkin <vladimir.medvedkin@intel.com>", "Cc": "Nathan Brown <nathan.brown@arm.com>, Ruifeng Wang <ruifeng.wang@arm.com>,\n dev@dpdk.org, Yoan Picchi <yoan.picchi@arm.com>", "Subject": "[PATCH v3 1/4] hash: pack the hitmask for hash in bulk lookup", "Date": "Tue, 7 Nov 2023 12:18:42 +0000", "Message-Id": "<20231107121845.2758454-2-yoan.picchi@arm.com>", "X-Mailer": "git-send-email 2.25.1", "In-Reply-To": "<20231107121845.2758454-1-yoan.picchi@arm.com>", "References": "<20231107121845.2758454-1-yoan.picchi@arm.com>", "MIME-Version": "1.0", "Content-Transfer-Encoding": "8bit", "X-Mailman-Approved-At": "Tue, 07 Nov 2023 14:04:56 +0100", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.29", "Precedence": "list", "List-Id": "DPDK patches and discussions <dev.dpdk.org>", "List-Unsubscribe": "<https://mails.dpdk.org/options/dev>,\n <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 <mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org" }, "content": "Current hitmask includes padding due to Intel's SIMD\nimplementation detail. This patch allows non Intel SIMD\nimplementations to benefit from a dense hitmask.\n\nSigned-off-by: Yoan Picchi <yoan.picchi@arm.com>\nReviewed-by: Ruifeng Wang <ruifeng.wang@arm.com>\nReviewed-by: Nathan Brown <nathan.brown@arm.com>\n---\n .mailmap | 2 +\n lib/hash/rte_cuckoo_hash.c | 118 ++++++++++++++++++++++++++-----------\n 2 files changed, 86 insertions(+), 34 deletions(-)", "diff": "diff --git a/.mailmap b/.mailmap\nindex 3f5bab26a8..b9c49aa7f6 100644\n--- a/.mailmap\n+++ b/.mailmap\n@@ -485,6 +485,7 @@ Hari Kumar Vemula <hari.kumarx.vemula@intel.com>\n Harini Ramakrishnan <harini.ramakrishnan@microsoft.com>\n Hariprasad Govindharajan <hariprasad.govindharajan@intel.com>\n Harish Patil <harish.patil@cavium.com> <harish.patil@qlogic.com>\n+Harjot Singh <harjot.singh@arm.com>\n Harman Kalra <hkalra@marvell.com>\n Harneet Singh <harneet.singh@intel.com>\n Harold Huang <baymaxhuang@gmail.com>\n@@ -1602,6 +1603,7 @@ Yixue Wang <yixue.wang@intel.com>\n Yi Yang <yangyi01@inspur.com> <yi.y.yang@intel.com>\n Yi Zhang <zhang.yi75@zte.com.cn>\n Yoann Desmouceaux <ydesmouc@cisco.com>\n+Yoan Picchi <yoan.picchi@arm.com>\n Yogesh Jangra <yogesh.jangra@intel.com>\n Yogev Chaimovich <yogev@cgstowernetworks.com>\n Yongjie Gu <yongjiex.gu@intel.com>\ndiff --git a/lib/hash/rte_cuckoo_hash.c b/lib/hash/rte_cuckoo_hash.c\nindex 19b23f2a97..2aa96eb862 100644\n--- a/lib/hash/rte_cuckoo_hash.c\n+++ b/lib/hash/rte_cuckoo_hash.c\n@@ -1850,8 +1850,50 @@ rte_hash_free_key_with_position(const struct rte_hash *h,\n \n }\n \n+#if defined(__ARM_NEON)\n+\n+static inline void\n+compare_signatures_dense(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\tuint16_t sig,\n+\t\t\tenum rte_hash_sig_compare_function sig_cmp_fn)\n+{\n+\tunsigned int i;\n+\n+\t/* For match mask every bits indicates the match */\n+\tswitch (sig_cmp_fn) {\n+\tcase RTE_HASH_COMPARE_NEON: {\n+\t\tuint16x8_t vmat, vsig, x;\n+\t\tint16x8_t shift = {0, 1, 2, 3, 4, 5, 6, 7};\n+\n+\t\tvsig = vld1q_dup_u16((uint16_t const *)&sig);\n+\t\t/* Compare all signatures in the primary bucket */\n+\t\tvmat = vceqq_u16(vsig,\n+\t\t\tvld1q_u16((uint16_t const *)prim_bkt->sig_current));\n+\t\tx = vshlq_u16(vandq_u16(vmat, vdupq_n_u16(0x0001)), shift);\n+\t\t*prim_hash_matches = (uint32_t)(vaddvq_u16(x));\n+\t\t/* Compare all signatures in the secondary bucket */\n+\t\tvmat = vceqq_u16(vsig,\n+\t\t\tvld1q_u16((uint16_t const *)sec_bkt->sig_current));\n+\t\tx = vshlq_u16(vandq_u16(vmat, vdupq_n_u16(0x0001)), shift);\n+\t\t*sec_hash_matches = (uint32_t)(vaddvq_u16(x));\n+\t\t}\n+\t\tbreak;\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((sig == prim_bkt->sig_current[i]) << i);\n+\t\t\t*sec_hash_matches |=\n+\t\t\t\t((sig == sec_bkt->sig_current[i]) << i);\n+\t\t}\n+\t}\n+}\n+\n+#else\n+\n static inline void\n-compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,\n+compare_signatures_sparse(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\tuint16_t sig,\n@@ -1878,25 +1920,7 @@ compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,\n \t\t/* Extract the even-index bits only */\n \t\t*sec_hash_matches &= 0x5555;\n \t\tbreak;\n-#elif defined(__ARM_NEON)\n-\tcase RTE_HASH_COMPARE_NEON: {\n-\t\tuint16x8_t vmat, vsig, x;\n-\t\tint16x8_t shift = {-15, -13, -11, -9, -7, -5, -3, -1};\n-\n-\t\tvsig = vld1q_dup_u16((uint16_t const *)&sig);\n-\t\t/* Compare all signatures in the primary bucket */\n-\t\tvmat = vceqq_u16(vsig,\n-\t\t\tvld1q_u16((uint16_t const *)prim_bkt->sig_current));\n-\t\tx = vshlq_u16(vandq_u16(vmat, vdupq_n_u16(0x8000)), shift);\n-\t\t*prim_hash_matches = (uint32_t)(vaddvq_u16(x));\n-\t\t/* Compare all signatures in the secondary bucket */\n-\t\tvmat = vceqq_u16(vsig,\n-\t\t\tvld1q_u16((uint16_t const *)sec_bkt->sig_current));\n-\t\tx = vshlq_u16(vandq_u16(vmat, vdupq_n_u16(0x8000)), shift);\n-\t\t*sec_hash_matches = (uint32_t)(vaddvq_u16(x));\n-\t\t}\n-\t\tbreak;\n-#endif\n+#endif /* defined(__SSE2__) */\n \tdefault:\n \t\tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n \t\t\t*prim_hash_matches |=\n@@ -1907,6 +1931,8 @@ compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,\n \t}\n }\n \n+#endif /* defined(__ARM_NEON) */\n+\n static inline void\n __bulk_lookup_l(const struct rte_hash *h, const void **keys,\n \t\tconst struct rte_hash_bucket **primary_bkt,\n@@ -1921,18 +1947,30 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys,\n \tuint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};\n \tstruct rte_hash_bucket *cur_bkt, *next_bkt;\n \n+#if defined(__ARM_NEON)\n+\tconst int hitmask_padding = 0;\n+#else\n+\tconst int hitmask_padding = 1;\n+#endif\n+\n \t__hash_rw_reader_lock(h);\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+#if defined(__ARM_NEON)\n+\t\tcompare_signatures_dense(&prim_hitmask[i], &sec_hitmask[i],\n+\t\t\tprimary_bkt[i], secondary_bkt[i],\n+\t\t\tsig[i], h->sig_cmp_fn);\n+#else\n+\t\tcompare_signatures_sparse(&prim_hitmask[i], &sec_hitmask[i],\n \t\t\tprimary_bkt[i], secondary_bkt[i],\n \t\t\tsig[i], h->sig_cmp_fn);\n+#endif\n \n \t\tif (prim_hitmask[i]) {\n \t\t\tuint32_t first_hit =\n \t\t\t\t\t__builtin_ctzl(prim_hitmask[i])\n-\t\t\t\t\t>> 1;\n+\t\t\t\t\t>> hitmask_padding;\n \t\t\tuint32_t key_idx =\n \t\t\t\tprimary_bkt[i]->key_idx[first_hit];\n \t\t\tconst struct rte_hash_key *key_slot =\n@@ -1946,7 +1984,7 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys,\n \t\tif (sec_hitmask[i]) {\n \t\t\tuint32_t first_hit =\n \t\t\t\t\t__builtin_ctzl(sec_hitmask[i])\n-\t\t\t\t\t>> 1;\n+\t\t\t\t\t>> hitmask_padding;\n \t\t\tuint32_t key_idx =\n \t\t\t\tsecondary_bkt[i]->key_idx[first_hit];\n \t\t\tconst struct rte_hash_key *key_slot =\n@@ -1963,7 +2001,7 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys,\n \t\twhile (prim_hitmask[i]) {\n \t\t\tuint32_t hit_index =\n \t\t\t\t\t__builtin_ctzl(prim_hitmask[i])\n-\t\t\t\t\t>> 1;\n+\t\t\t\t\t>> hitmask_padding;\n \t\t\tuint32_t key_idx =\n \t\t\t\tprimary_bkt[i]->key_idx[hit_index];\n \t\t\tconst struct rte_hash_key *key_slot =\n@@ -1985,13 +2023,13 @@ __bulk_lookup_l(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] &= ~(3ULL << (hit_index << 1));\n+\t\t\tprim_hitmask[i] &= ~(1 << (hit_index << hitmask_padding));\n \t\t}\n \n \t\twhile (sec_hitmask[i]) {\n \t\t\tuint32_t hit_index =\n \t\t\t\t\t__builtin_ctzl(sec_hitmask[i])\n-\t\t\t\t\t>> 1;\n+\t\t\t\t\t>> hitmask_padding;\n \t\t\tuint32_t key_idx =\n \t\t\t\tsecondary_bkt[i]->key_idx[hit_index];\n \t\t\tconst struct rte_hash_key *key_slot =\n@@ -2014,7 +2052,7 @@ __bulk_lookup_l(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] &= ~(3ULL << (hit_index << 1));\n+\t\t\tsec_hitmask[i] &= ~(1 << (hit_index << hitmask_padding));\n \t\t}\n next_key:\n \t\tcontinue;\n@@ -2069,6 +2107,12 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,\n \tstruct rte_hash_bucket *cur_bkt, *next_bkt;\n \tuint32_t cnt_b, cnt_a;\n \n+#if defined(__ARM_NEON)\n+\tconst int hitmask_padding = 0;\n+#else\n+\tconst int hitmask_padding = 1;\n+#endif\n+\n \tfor (i = 0; i < num_keys; i++)\n \t\tpositions[i] = -ENOENT;\n \n@@ -2082,14 +2126,20 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,\n \n \t\t/* Compare signatures and prefetch key slot of first hit */\n \t\tfor (i = 0; i < num_keys; i++) {\n-\t\t\tcompare_signatures(&prim_hitmask[i], &sec_hitmask[i],\n+#if defined(__ARM_NEON)\n+\t\t\tcompare_signatures_dense(&prim_hitmask[i], &sec_hitmask[i],\n \t\t\t\tprimary_bkt[i], secondary_bkt[i],\n \t\t\t\tsig[i], h->sig_cmp_fn);\n+#else\n+\t\t\tcompare_signatures_sparse(&prim_hitmask[i], &sec_hitmask[i],\n+\t\t\t\tprimary_bkt[i], secondary_bkt[i],\n+\t\t\t\tsig[i], h->sig_cmp_fn);\n+#endif\n \n \t\t\tif (prim_hitmask[i]) {\n \t\t\t\tuint32_t first_hit =\n \t\t\t\t\t\t__builtin_ctzl(prim_hitmask[i])\n-\t\t\t\t\t\t>> 1;\n+\t\t\t\t\t\t>> hitmask_padding;\n \t\t\t\tuint32_t key_idx =\n \t\t\t\t\tprimary_bkt[i]->key_idx[first_hit];\n \t\t\t\tconst struct rte_hash_key *key_slot =\n@@ -2103,7 +2153,7 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,\n \t\t\tif (sec_hitmask[i]) {\n \t\t\t\tuint32_t first_hit =\n \t\t\t\t\t\t__builtin_ctzl(sec_hitmask[i])\n-\t\t\t\t\t\t>> 1;\n+\t\t\t\t\t\t>> hitmask_padding;\n \t\t\t\tuint32_t key_idx =\n \t\t\t\t\tsecondary_bkt[i]->key_idx[first_hit];\n \t\t\t\tconst struct rte_hash_key *key_slot =\n@@ -2119,7 +2169,7 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,\n \t\t\twhile (prim_hitmask[i]) {\n \t\t\t\tuint32_t hit_index =\n \t\t\t\t\t\t__builtin_ctzl(prim_hitmask[i])\n-\t\t\t\t\t\t>> 1;\n+\t\t\t\t\t\t>> hitmask_padding;\n \t\t\t\tuint32_t key_idx =\n \t\t\t\t__atomic_load_n(\n \t\t\t\t\t&primary_bkt[i]->key_idx[hit_index],\n@@ -2145,13 +2195,13 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,\n \t\t\t\t\tpositions[i] = key_idx - 1;\n \t\t\t\t\tgoto next_key;\n \t\t\t\t}\n-\t\t\t\tprim_hitmask[i] &= ~(3ULL << (hit_index << 1));\n+\t\t\t\tprim_hitmask[i] &= ~(1 << (hit_index << hitmask_padding));\n \t\t\t}\n \n \t\t\twhile (sec_hitmask[i]) {\n \t\t\t\tuint32_t hit_index =\n \t\t\t\t\t\t__builtin_ctzl(sec_hitmask[i])\n-\t\t\t\t\t\t>> 1;\n+\t\t\t\t\t\t>> hitmask_padding;\n \t\t\t\tuint32_t key_idx =\n \t\t\t\t__atomic_load_n(\n \t\t\t\t\t&secondary_bkt[i]->key_idx[hit_index],\n@@ -2178,7 +2228,7 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,\n \t\t\t\t\tpositions[i] = key_idx - 1;\n \t\t\t\t\tgoto next_key;\n \t\t\t\t}\n-\t\t\t\tsec_hitmask[i] &= ~(3ULL << (hit_index << 1));\n+\t\t\t\tsec_hitmask[i] &= ~(1 << (hit_index << hitmask_padding));\n \t\t\t}\n next_key:\n \t\t\tcontinue;\n", "prefixes": [ "v3", "1/4" ] }