From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id 004442956 for ; Tue, 19 Mar 2019 11:15:05 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga101.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 19 Mar 2019 03:15:04 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.58,497,1544515200"; d="scan'208";a="283921224" Received: from irsmsx103.ger.corp.intel.com ([163.33.3.157]) by orsmga004.jf.intel.com with ESMTP; 19 Mar 2019 03:15:02 -0700 Received: from irsmsx105.ger.corp.intel.com ([169.254.7.210]) by IRSMSX103.ger.corp.intel.com ([169.254.3.152]) with mapi id 14.03.0415.000; Tue, 19 Mar 2019 10:15:01 +0000 From: "Ananyev, Konstantin" To: "Gavin Hu (Arm Technology China)" , "dev@dpdk.org" CC: nd , "stephen@networkplumber.org" , "jerin.jacob@caviumnetworks.com" , "thomas@monjalon.net" , Honnappa Nagarahalli , "Joyce Kong (Arm Technology China)" Thread-Topic: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve fairness Thread-Index: AQHU2vxlKpABH57hOkqA57tQE05+36YMpFOAgAYWZYCAAARN4A== Date: Tue, 19 Mar 2019 10:15:00 +0000 Message-ID: <2601191342CEEE43887BDE71AB977258013655D209@irsmsx105.ger.corp.intel.com> References: <1547802943-18711-1-git-send-email-joyce.kong@arm.com> <1552632988-80787-2-git-send-email-joyce.kong@arm.com> <2601191342CEEE43887BDE71AB977258013655BF89@irsmsx105.ger.corp.intel.com> In-Reply-To: Accept-Language: en-IE, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiYzAxNDA4ZjUtMzRkZS00YmJmLTk3Y2EtZWMwNTZkNTI0NGI0IiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiNFExZERnTmtlZ1RIT2JwTm5xVnMrcm1UT2UwT3UwYkJjYWxGRktuVU82R1oxbEhIdzFKUzhQYUo2eXhEK1doZCJ9 x-ctpclassification: CTP_NT dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-originating-ip: [163.33.239.180] Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve fairness 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: Tue, 19 Mar 2019 10:15:06 -0000 Hi Gavin, > > > > > diff --git a/lib/librte_eal/common/include/generic/rte_ticketlock.h > > b/lib/librte_eal/common/include/generic/rte_ticketlock.h > > > new file mode 100644 > > > index 0000000..d63aaaa > > > --- /dev/null > > > +++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h > > > @@ -0,0 +1,308 @@ > > > +/* SPDX-License-Identifier: BSD-3-Clause > > > + * Copyright(c) 2019 Arm Limited > > > + */ > > > + > > > +#ifndef _RTE_TICKETLOCK_H_ > > > +#define _RTE_TICKETLOCK_H_ > > > + > > > +/** > > > + * @file > > > + * > > > + * RTE ticket locks > > > + * > > > + * This file defines an API for ticket locks, which give each waitin= g > > > + * thread a ticket and take the lock one by one, first come, first > > > + * serviced. > > > + * > > > + * All locks must be initialised before use, and only initialised on= ce. > > > + * > > > + */ > > > + > > > +#ifdef __cplusplus > > > +extern "C" { > > > +#endif > > > + > > > +#include > > > +#include > > > +#include > > > + > > > +/** > > > + * The rte_ticketlock_t type. > > > + */ > > > +typedef struct { > > > + uint16_t current; > > > + uint16_t next; > > > +} rte_ticketlock_t; > > > + > > > +/** > > > + * A static ticketlock initializer. > > > + */ > > > +#define RTE_TICKETLOCK_INITIALIZER { 0 } > > > + > > > +/** > > > + * Initialize the ticketlock to an unlocked state. > > > + * > > > + * @param tl > > > + * A pointer to the ticketlock. > > > + */ > > > +static inline __rte_experimental void > > > +rte_ticketlock_init(rte_ticketlock_t *tl) > > > +{ > > > + __atomic_store_n(&tl->current, 0, __ATOMIC_RELAXED); > > > + __atomic_store_n(&tl->next, 0, __ATOMIC_RELAXED); > > > +} > > > + > > > +/** > > > + * Take the ticketlock. > > > + * > > > + * @param tl > > > + * A pointer to the ticketlock. > > > + */ > > > +static inline __rte_experimental void > > > +rte_ticketlock_lock(rte_ticketlock_t *tl) > > > +{ > > > + uint16_t me =3D __atomic_fetch_add(&tl->next, 1, > > __ATOMIC_RELAXED); > > > + while (__atomic_load_n(&tl->current, __ATOMIC_ACQUIRE) !=3D me) > > > + rte_pause(); > > > +} > > > + > > > +/** > > > + * Release the ticketlock. > > > + * > > > + * @param tl > > > + * A pointer to the ticketlock. > > > + */ > > > +static inline __rte_experimental void > > > +rte_ticketlock_unlock(rte_ticketlock_t *tl) > > > +{ > > > + uint16_t i =3D __atomic_load_n(&tl->current, __ATOMIC_RELAXED); > > > + __atomic_store_n(&tl->current, i+1, __ATOMIC_RELEASE); > > > +} > > > + > > > +/** > > > + * Try to take the lock. > > > + * > > > + * @param tl > > > + * A pointer to the ticketlock. > > > + * @return > > > + * 1 if the lock is successfully taken; 0 otherwise. > > > + */ > > > +static inline __rte_experimental int > > > +rte_ticketlock_trylock(rte_ticketlock_t *tl) > > > +{ > > > + uint16_t next =3D __atomic_load_n(&tl->next, __ATOMIC_RELAXED); > > > + uint16_t cur =3D __atomic_load_n(&tl->current, __ATOMIC_RELAXED); > > > + if (next =3D=3D cur) { > > > > Probably a na=EFve one: > > Suppose next=3D=3Dcur=3D=3D1 here, then this thread will experience rea= lly long > > context switch, >=20 > By saying context switch, do you mean running to here, it is out of CPU t= ime and starving for CPU? Yes. >=20 > > so next time it continues its execution tl->next value will wrap-up and= will > > be 1 again, and tl->current=3D=3D0 (lock held). > > I suppose this function will set tl->next=3D2 and will return a success= ? >=20 > If this thread was swapped out and another thread took/attempted to take = the lock, yes, tl->next =3D=3D 2 here, > But as next =3D=3D 1 unchanged, so it would not return a success. I am not talking about situation when tl->next =3D=3D 2,tl->current=3D=3D1 = (just one lock() was executed by different thread). I am talking about situation when this thread was out of cpu for significan= t amount of cycles, and in that period tl->next and tl->current were wrapped around (they both = reached UINT16_MAX, then 0). i.e. UINT16_MAX lock/unlock were executed while this thread was away from c= pu. After that another thread just did successful lock(), so tl->next=3D=3D1 an= d tl->current=3D=3D0. Now this thread wakeups and continues with: __atomic_compare_exchange_n(&tl->next, &next, next+1, ...) As both tl->next=3D=3D1 and next=3D=3D1, it will succeed. So we have 2 threads assuming they grabbed the lock successfully.=20 Konstantin >=20 > > Wouldn't be better here and in _is_locked_ to do load/store for > > next/current values in one go > > (using 32bit op)? > > Konstantin >=20 > To load both in one go is feasible, but no necessary as we need to compar= e them. > We don't need store both as in this function tl->current is read only. > tl->next is read-update-store, I ever thought of combining the two if-sta= tements to one __atomic_compare_exchange_n(&(&tl->next,&tl- > >current, tl->next+1, ...), > but tl->next+1 is out of atomicity and may be the old value and corrupt t= he ticket lock waiting chain. >=20 > The current code works ok except it may fail spuriously(in case during co= ntext switch, the lock was taken and released by other threads, > moving tl->next forward, in this case > The lock is available but not obtained by this trylock). Anyway, as the = name suggests, it is a try/attempt, a spurious fail is not a big deal? > And in most cases, dpdk running on dedicated cores, > the context switch will not happen at all. >=20 > Any more comments are welcome! > > > > > + if (__atomic_compare_exchange_n(&tl->next, &next, > > next+1, > > > + 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) > > > + return 1; > > > + } > > > + > > > + return 0; > > > +} > > > + > > > +/** > > > + * Test if the lock is taken. > > > + * > > > + * @param tl > > > + * A pointer to the ticketlock. > > > + * @return > > > + * 1 if the lock icurrently taken; 0 otherwise. > > > + */ > > > +static inline __rte_experimental int > > > +rte_ticketlock_is_locked(rte_ticketlock_t *tl) > > > +{ > > > + return (__atomic_load_n(&tl->current, __ATOMIC_ACQUIRE) !=3D > > > + __atomic_load_n(&tl->next, __ATOMIC_ACQUIRE)); > > > +} > > > + 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 7C6CAA00E6 for ; Tue, 19 Mar 2019 11:15:08 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 3BE5A2BAF; Tue, 19 Mar 2019 11:15:07 +0100 (CET) Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id 004442956 for ; Tue, 19 Mar 2019 11:15:05 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga101.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 19 Mar 2019 03:15:04 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.58,497,1544515200"; d="scan'208";a="283921224" Received: from irsmsx103.ger.corp.intel.com ([163.33.3.157]) by orsmga004.jf.intel.com with ESMTP; 19 Mar 2019 03:15:02 -0700 Received: from irsmsx105.ger.corp.intel.com ([169.254.7.210]) by IRSMSX103.ger.corp.intel.com ([169.254.3.152]) with mapi id 14.03.0415.000; Tue, 19 Mar 2019 10:15:01 +0000 From: "Ananyev, Konstantin" To: "Gavin Hu (Arm Technology China)" , "dev@dpdk.org" CC: nd , "stephen@networkplumber.org" , "jerin.jacob@caviumnetworks.com" , "thomas@monjalon.net" , Honnappa Nagarahalli , "Joyce Kong (Arm Technology China)" Thread-Topic: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve fairness Thread-Index: AQHU2vxlKpABH57hOkqA57tQE05+36YMpFOAgAYWZYCAAARN4A== Date: Tue, 19 Mar 2019 10:15:00 +0000 Message-ID: <2601191342CEEE43887BDE71AB977258013655D209@irsmsx105.ger.corp.intel.com> References: <1547802943-18711-1-git-send-email-joyce.kong@arm.com> <1552632988-80787-2-git-send-email-joyce.kong@arm.com> <2601191342CEEE43887BDE71AB977258013655BF89@irsmsx105.ger.corp.intel.com> In-Reply-To: Accept-Language: en-IE, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiYzAxNDA4ZjUtMzRkZS00YmJmLTk3Y2EtZWMwNTZkNTI0NGI0IiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiNFExZERnTmtlZ1RIT2JwTm5xVnMrcm1UT2UwT3UwYkJjYWxGRktuVU82R1oxbEhIdzFKUzhQYUo2eXhEK1doZCJ9 x-ctpclassification: CTP_NT dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-originating-ip: [163.33.239.180] Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve fairness 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: <20190319101500.GUEZoZSp6lrXp_eGP8LcGXOkAydcAZG9nKj1AYkDdqc@z> Hi Gavin, > > > > > diff --git a/lib/librte_eal/common/include/generic/rte_ticketlock.h > > b/lib/librte_eal/common/include/generic/rte_ticketlock.h > > > new file mode 100644 > > > index 0000000..d63aaaa > > > --- /dev/null > > > +++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h > > > @@ -0,0 +1,308 @@ > > > +/* SPDX-License-Identifier: BSD-3-Clause > > > + * Copyright(c) 2019 Arm Limited > > > + */ > > > + > > > +#ifndef _RTE_TICKETLOCK_H_ > > > +#define _RTE_TICKETLOCK_H_ > > > + > > > +/** > > > + * @file > > > + * > > > + * RTE ticket locks > > > + * > > > + * This file defines an API for ticket locks, which give each waitin= g > > > + * thread a ticket and take the lock one by one, first come, first > > > + * serviced. > > > + * > > > + * All locks must be initialised before use, and only initialised on= ce. > > > + * > > > + */ > > > + > > > +#ifdef __cplusplus > > > +extern "C" { > > > +#endif > > > + > > > +#include > > > +#include > > > +#include > > > + > > > +/** > > > + * The rte_ticketlock_t type. > > > + */ > > > +typedef struct { > > > + uint16_t current; > > > + uint16_t next; > > > +} rte_ticketlock_t; > > > + > > > +/** > > > + * A static ticketlock initializer. > > > + */ > > > +#define RTE_TICKETLOCK_INITIALIZER { 0 } > > > + > > > +/** > > > + * Initialize the ticketlock to an unlocked state. > > > + * > > > + * @param tl > > > + * A pointer to the ticketlock. > > > + */ > > > +static inline __rte_experimental void > > > +rte_ticketlock_init(rte_ticketlock_t *tl) > > > +{ > > > + __atomic_store_n(&tl->current, 0, __ATOMIC_RELAXED); > > > + __atomic_store_n(&tl->next, 0, __ATOMIC_RELAXED); > > > +} > > > + > > > +/** > > > + * Take the ticketlock. > > > + * > > > + * @param tl > > > + * A pointer to the ticketlock. > > > + */ > > > +static inline __rte_experimental void > > > +rte_ticketlock_lock(rte_ticketlock_t *tl) > > > +{ > > > + uint16_t me =3D __atomic_fetch_add(&tl->next, 1, > > __ATOMIC_RELAXED); > > > + while (__atomic_load_n(&tl->current, __ATOMIC_ACQUIRE) !=3D me) > > > + rte_pause(); > > > +} > > > + > > > +/** > > > + * Release the ticketlock. > > > + * > > > + * @param tl > > > + * A pointer to the ticketlock. > > > + */ > > > +static inline __rte_experimental void > > > +rte_ticketlock_unlock(rte_ticketlock_t *tl) > > > +{ > > > + uint16_t i =3D __atomic_load_n(&tl->current, __ATOMIC_RELAXED); > > > + __atomic_store_n(&tl->current, i+1, __ATOMIC_RELEASE); > > > +} > > > + > > > +/** > > > + * Try to take the lock. > > > + * > > > + * @param tl > > > + * A pointer to the ticketlock. > > > + * @return > > > + * 1 if the lock is successfully taken; 0 otherwise. > > > + */ > > > +static inline __rte_experimental int > > > +rte_ticketlock_trylock(rte_ticketlock_t *tl) > > > +{ > > > + uint16_t next =3D __atomic_load_n(&tl->next, __ATOMIC_RELAXED); > > > + uint16_t cur =3D __atomic_load_n(&tl->current, __ATOMIC_RELAXED); > > > + if (next =3D=3D cur) { > > > > Probably a na=EFve one: > > Suppose next=3D=3Dcur=3D=3D1 here, then this thread will experience rea= lly long > > context switch, >=20 > By saying context switch, do you mean running to here, it is out of CPU t= ime and starving for CPU? Yes. >=20 > > so next time it continues its execution tl->next value will wrap-up and= will > > be 1 again, and tl->current=3D=3D0 (lock held). > > I suppose this function will set tl->next=3D2 and will return a success= ? >=20 > If this thread was swapped out and another thread took/attempted to take = the lock, yes, tl->next =3D=3D 2 here, > But as next =3D=3D 1 unchanged, so it would not return a success. I am not talking about situation when tl->next =3D=3D 2,tl->current=3D=3D1 = (just one lock() was executed by different thread). I am talking about situation when this thread was out of cpu for significan= t amount of cycles, and in that period tl->next and tl->current were wrapped around (they both = reached UINT16_MAX, then 0). i.e. UINT16_MAX lock/unlock were executed while this thread was away from c= pu. After that another thread just did successful lock(), so tl->next=3D=3D1 an= d tl->current=3D=3D0. Now this thread wakeups and continues with: __atomic_compare_exchange_n(&tl->next, &next, next+1, ...) As both tl->next=3D=3D1 and next=3D=3D1, it will succeed. So we have 2 threads assuming they grabbed the lock successfully.=20 Konstantin >=20 > > Wouldn't be better here and in _is_locked_ to do load/store for > > next/current values in one go > > (using 32bit op)? > > Konstantin >=20 > To load both in one go is feasible, but no necessary as we need to compar= e them. > We don't need store both as in this function tl->current is read only. > tl->next is read-update-store, I ever thought of combining the two if-sta= tements to one __atomic_compare_exchange_n(&(&tl->next,&tl- > >current, tl->next+1, ...), > but tl->next+1 is out of atomicity and may be the old value and corrupt t= he ticket lock waiting chain. >=20 > The current code works ok except it may fail spuriously(in case during co= ntext switch, the lock was taken and released by other threads, > moving tl->next forward, in this case > The lock is available but not obtained by this trylock). Anyway, as the = name suggests, it is a try/attempt, a spurious fail is not a big deal? > And in most cases, dpdk running on dedicated cores, > the context switch will not happen at all. >=20 > Any more comments are welcome! > > > > > + if (__atomic_compare_exchange_n(&tl->next, &next, > > next+1, > > > + 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) > > > + return 1; > > > + } > > > + > > > + return 0; > > > +} > > > + > > > +/** > > > + * Test if the lock is taken. > > > + * > > > + * @param tl > > > + * A pointer to the ticketlock. > > > + * @return > > > + * 1 if the lock icurrently taken; 0 otherwise. > > > + */ > > > +static inline __rte_experimental int > > > +rte_ticketlock_is_locked(rte_ticketlock_t *tl) > > > +{ > > > + return (__atomic_load_n(&tl->current, __ATOMIC_ACQUIRE) !=3D > > > + __atomic_load_n(&tl->next, __ATOMIC_ACQUIRE)); > > > +} > > > +