From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga04.intel.com (mga04.intel.com [192.55.52.120]) by dpdk.org (Postfix) with ESMTP id 1BDD42C28 for ; Fri, 29 Mar 2019 20:25:22 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga001.jf.intel.com ([10.7.209.18]) by fmsmga104.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 29 Mar 2019 12:25:22 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.60,285,1549958400"; d="scan'208";a="218839730" Received: from fmsmsx105.amr.corp.intel.com ([10.18.124.203]) by orsmga001.jf.intel.com with ESMTP; 29 Mar 2019 12:25:21 -0700 Received: from fmsmsx155.amr.corp.intel.com (10.18.116.71) by FMSMSX105.amr.corp.intel.com (10.18.124.203) with Microsoft SMTP Server (TLS) id 14.3.408.0; Fri, 29 Mar 2019 12:25:21 -0700 Received: from fmsmsx108.amr.corp.intel.com ([169.254.9.216]) by FMSMSX155.amr.corp.intel.com ([169.254.5.16]) with mapi id 14.03.0415.000; Fri, 29 Mar 2019 12:25:21 -0700 From: "Eads, Gage" To: Honnappa Nagarahalli , "dev@dpdk.org" CC: "olivier.matz@6wind.com" , "arybchenko@solarflare.com" , "Richardson, Bruce" , "Ananyev, Konstantin" , "Gavin Hu (Arm Technology China)" , nd , "thomas@monjalon.net" , nd , Thomas Monjalon Thread-Topic: [PATCH v3 5/8] stack: add lock-free stack implementation Thread-Index: AQHU1CtXemjpCfhXh0aG8vUsBJcLcaYgpWeQgAJt6ZA= Date: Fri, 29 Mar 2019 19:25:20 +0000 Message-ID: <9184057F7FC11744A2107296B6B8EB1E5420D94F@FMSMSX108.amr.corp.intel.com> References: <20190305164256.2367-1-gage.eads@intel.com> <20190306144559.391-1-gage.eads@intel.com> <20190306144559.391-6-gage.eads@intel.com> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiOGNiMDBmYzUtNzMyZi00MDhkLWJkOGItNzg3ZTQwMmZlYmYzIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiT1ljQjExUUV2cksrbDh6eWxPXC80Y3kxQzlDc0w5RERUd1hOUkFNdmNMN3NWNFpxYTM5NFFBMm5aNXVianpSREYifQ== x-ctpclassification: CTP_NT dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-originating-ip: [10.1.200.108] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH v3 5/8] stack: add lock-free stack implementation X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 29 Mar 2019 19:25:23 -0000 > -----Original Message----- > From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] > Sent: Thursday, March 28, 2019 6:27 PM > To: Eads, Gage ; dev@dpdk.org > Cc: olivier.matz@6wind.com; arybchenko@solarflare.com; Richardson, Bruce > ; Ananyev, Konstantin > ; Gavin Hu (Arm Technology China) > ; nd ; thomas@monjalon.net; nd > > Subject: RE: [PATCH v3 5/8] stack: add lock-free stack implementation >=20 > >=20 > > diff --git a/lib/librte_stack/rte_stack.c > > b/lib/librte_stack/rte_stack.c index > > 96dffdf44..8f0361ea1 100644 > > --- a/lib/librte_stack/rte_stack.c > > +++ b/lib/librte_stack/rte_stack.c >=20 > >=20 > > @@ -63,9 +81,16 @@ rte_stack_create(const char *name, unsigned int > > count, int socket_id, > > unsigned int sz; > > int ret; > > > > - RTE_SET_USED(flags); > > +#ifdef RTE_ARCH_X86_64 > > + RTE_BUILD_BUG_ON(sizeof(struct rte_stack_lf_head) !=3D 16); > This check should be independent of the platform. Good catch. Will change the ifdef to RTE_ARCH_64. [snip] > > +/** > > + * @internal Push several objects on the lock-free stack (MT-safe). > > + * > > + * @param s > > + * A pointer to the stack structure. > > + * @param obj_table > > + * A pointer to a table of void * pointers (objects). > > + * @param n > > + * The number of objects to push on the stack from the obj_table. > > + * @return > > + * Actual number of objects enqueued. > > + */ > > +static __rte_always_inline unsigned int __rte_experimental > This is an internal function. Is '__rte_experimental' tag required? (appl= ies to > other instances in this patch)=20 (Addressed in comments to patch 1/8) [snip] =20 > > > > /** > > @@ -225,7 +339,10 @@ rte_stack_free_count(struct rte_stack *s) > > * NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA > > * constraint for the reserved zone. > > * @param flags > > - * Reserved for future use. > > + * An OR of the following: > > + * - RTE_STACK_F_LF: If this flag is set, the stack uses lock-free > > + * variants of the push and pop functions. Otherwise, it achieves > > + * thread-safety using a lock. > > * @return > > * On success, the pointer to the new allocated stack. NULL on error= with > > * rte_errno set appropriately. Possible errno values include: > > diff --git a/lib/librte_stack/rte_stack_generic.h > > b/lib/librte_stack/rte_stack_generic.h > > new file mode 100644 > > index 000000000..5e4cbc38e > > --- /dev/null > > +++ b/lib/librte_stack/rte_stack_generic.h > The name "...stack_generic.h" is confusing. It is implementing LF algorit= hm. > IMO, the code should be re-organized differently. > rte_stack.h, rte_stack.c - Contain the APIs (calling std or LF based on t= he flag) > and top level structure definition rte_stack_std.c, rte_stack_std.h - Con= tain > the standard implementation rte_stack_lf.c, rte_stack_lf.h - Contain the = LF > implementation rte_stack_lf_c11.h - Contain the LF C11 implementation >=20 'generic' here refers to the "generic API for atomic operations" (generic/r= te_atomic.h:12), but I see how that can be misleading. Yeah, I like this proposal, but with one tweak: use three lock-free header = files: rte_stack_lf.h (common inline lock-free functions like rte_stack_lf_= pop()), rte_stack_lf_c11.h (C11 implementation), rte_stack_lf_generic.h (ge= neric atomic implementation). Since the name is *_lf_generic.h, it should b= e clear that it implements the lock-free functions, and this naming matches= rte ring's (easier to pick up for those already used to the ring organizat= ion). [snip] > > + /* old_head is updated on failure */ > > + success =3D rte_atomic128_cmp_exchange( > > + (rte_int128_t *)&list->head, > > + (rte_int128_t *)&old_head, > > + (rte_int128_t *)&new_head, > > + 1, __ATOMIC_ACQUIRE, > > + __ATOMIC_ACQUIRE); > Just wondering if 'rte_atomic128_cmp_exchange' for x86 should have > compiler barriers based on the memory order passed? > C++11 memory model is getting mixed with barrier based model. I think thi= s > is something that needs to be discussed at a wider level. The x86 implementation uses a compiler barrier (i.e. the inline assembly cl= obber list contains "memory") regardless of the memory order, so we're (con= servatively) adhering to the C11 model, which guarantees ordering at both t= he compiler and processor levels. Whether/how we relax the x86 implementati= on (e.g. no compiler barrier if ordering =3D=3D relaxed) is an interesting = question. Thanks, Gage From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by dpdk.space (Postfix) with ESMTP id AF905A05D3 for ; Fri, 29 Mar 2019 20:25:25 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 884A13572; Fri, 29 Mar 2019 20:25:25 +0100 (CET) Received: from mga04.intel.com (mga04.intel.com [192.55.52.120]) by dpdk.org (Postfix) with ESMTP id 1BDD42C28 for ; Fri, 29 Mar 2019 20:25:22 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga001.jf.intel.com ([10.7.209.18]) by fmsmga104.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 29 Mar 2019 12:25:22 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.60,285,1549958400"; d="scan'208";a="218839730" Received: from fmsmsx105.amr.corp.intel.com ([10.18.124.203]) by orsmga001.jf.intel.com with ESMTP; 29 Mar 2019 12:25:21 -0700 Received: from fmsmsx155.amr.corp.intel.com (10.18.116.71) by FMSMSX105.amr.corp.intel.com (10.18.124.203) with Microsoft SMTP Server (TLS) id 14.3.408.0; Fri, 29 Mar 2019 12:25:21 -0700 Received: from fmsmsx108.amr.corp.intel.com ([169.254.9.216]) by FMSMSX155.amr.corp.intel.com ([169.254.5.16]) with mapi id 14.03.0415.000; Fri, 29 Mar 2019 12:25:21 -0700 From: "Eads, Gage" To: Honnappa Nagarahalli , "dev@dpdk.org" CC: "olivier.matz@6wind.com" , "arybchenko@solarflare.com" , "Richardson, Bruce" , "Ananyev, Konstantin" , "Gavin Hu (Arm Technology China)" , nd , "thomas@monjalon.net" , nd , Thomas Monjalon Thread-Topic: [PATCH v3 5/8] stack: add lock-free stack implementation Thread-Index: AQHU1CtXemjpCfhXh0aG8vUsBJcLcaYgpWeQgAJt6ZA= Date: Fri, 29 Mar 2019 19:25:20 +0000 Message-ID: <9184057F7FC11744A2107296B6B8EB1E5420D94F@FMSMSX108.amr.corp.intel.com> References: <20190305164256.2367-1-gage.eads@intel.com> <20190306144559.391-1-gage.eads@intel.com> <20190306144559.391-6-gage.eads@intel.com> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiOGNiMDBmYzUtNzMyZi00MDhkLWJkOGItNzg3ZTQwMmZlYmYzIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiT1ljQjExUUV2cksrbDh6eWxPXC80Y3kxQzlDc0w5RERUd1hOUkFNdmNMN3NWNFpxYTM5NFFBMm5aNXVianpSREYifQ== x-ctpclassification: CTP_NT dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-originating-ip: [10.1.200.108] Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH v3 5/8] stack: add lock-free stack implementation X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Message-ID: <20190329192520.lFQaYQoLEhBBhXPaM60h4C2KfUrN4CbwCSNTW3Cijeg@z> > -----Original Message----- > From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] > Sent: Thursday, March 28, 2019 6:27 PM > To: Eads, Gage ; dev@dpdk.org > Cc: olivier.matz@6wind.com; arybchenko@solarflare.com; Richardson, Bruce > ; Ananyev, Konstantin > ; Gavin Hu (Arm Technology China) > ; nd ; thomas@monjalon.net; nd > > Subject: RE: [PATCH v3 5/8] stack: add lock-free stack implementation >=20 > >=20 > > diff --git a/lib/librte_stack/rte_stack.c > > b/lib/librte_stack/rte_stack.c index > > 96dffdf44..8f0361ea1 100644 > > --- a/lib/librte_stack/rte_stack.c > > +++ b/lib/librte_stack/rte_stack.c >=20 > >=20 > > @@ -63,9 +81,16 @@ rte_stack_create(const char *name, unsigned int > > count, int socket_id, > > unsigned int sz; > > int ret; > > > > - RTE_SET_USED(flags); > > +#ifdef RTE_ARCH_X86_64 > > + RTE_BUILD_BUG_ON(sizeof(struct rte_stack_lf_head) !=3D 16); > This check should be independent of the platform. Good catch. Will change the ifdef to RTE_ARCH_64. [snip] > > +/** > > + * @internal Push several objects on the lock-free stack (MT-safe). > > + * > > + * @param s > > + * A pointer to the stack structure. > > + * @param obj_table > > + * A pointer to a table of void * pointers (objects). > > + * @param n > > + * The number of objects to push on the stack from the obj_table. > > + * @return > > + * Actual number of objects enqueued. > > + */ > > +static __rte_always_inline unsigned int __rte_experimental > This is an internal function. Is '__rte_experimental' tag required? (appl= ies to > other instances in this patch)=20 (Addressed in comments to patch 1/8) [snip] =20 > > > > /** > > @@ -225,7 +339,10 @@ rte_stack_free_count(struct rte_stack *s) > > * NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA > > * constraint for the reserved zone. > > * @param flags > > - * Reserved for future use. > > + * An OR of the following: > > + * - RTE_STACK_F_LF: If this flag is set, the stack uses lock-free > > + * variants of the push and pop functions. Otherwise, it achieves > > + * thread-safety using a lock. > > * @return > > * On success, the pointer to the new allocated stack. NULL on error= with > > * rte_errno set appropriately. Possible errno values include: > > diff --git a/lib/librte_stack/rte_stack_generic.h > > b/lib/librte_stack/rte_stack_generic.h > > new file mode 100644 > > index 000000000..5e4cbc38e > > --- /dev/null > > +++ b/lib/librte_stack/rte_stack_generic.h > The name "...stack_generic.h" is confusing. It is implementing LF algorit= hm. > IMO, the code should be re-organized differently. > rte_stack.h, rte_stack.c - Contain the APIs (calling std or LF based on t= he flag) > and top level structure definition rte_stack_std.c, rte_stack_std.h - Con= tain > the standard implementation rte_stack_lf.c, rte_stack_lf.h - Contain the = LF > implementation rte_stack_lf_c11.h - Contain the LF C11 implementation >=20 'generic' here refers to the "generic API for atomic operations" (generic/r= te_atomic.h:12), but I see how that can be misleading. Yeah, I like this proposal, but with one tweak: use three lock-free header = files: rte_stack_lf.h (common inline lock-free functions like rte_stack_lf_= pop()), rte_stack_lf_c11.h (C11 implementation), rte_stack_lf_generic.h (ge= neric atomic implementation). Since the name is *_lf_generic.h, it should b= e clear that it implements the lock-free functions, and this naming matches= rte ring's (easier to pick up for those already used to the ring organizat= ion). [snip] > > + /* old_head is updated on failure */ > > + success =3D rte_atomic128_cmp_exchange( > > + (rte_int128_t *)&list->head, > > + (rte_int128_t *)&old_head, > > + (rte_int128_t *)&new_head, > > + 1, __ATOMIC_ACQUIRE, > > + __ATOMIC_ACQUIRE); > Just wondering if 'rte_atomic128_cmp_exchange' for x86 should have > compiler barriers based on the memory order passed? > C++11 memory model is getting mixed with barrier based model. I think thi= s > is something that needs to be discussed at a wider level. The x86 implementation uses a compiler barrier (i.e. the inline assembly cl= obber list contains "memory") regardless of the memory order, so we're (con= servatively) adhering to the C11 model, which guarantees ordering at both t= he compiler and processor levels. Whether/how we relax the x86 implementati= on (e.g. no compiler barrier if ordering =3D=3D relaxed) is an interesting = question. Thanks, Gage