From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga18.intel.com (mga18.intel.com [134.134.136.126]) by dpdk.org (Postfix) with ESMTP id BBE674C91 for ; Wed, 20 Mar 2019 10:47:07 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga008.jf.intel.com ([10.7.209.65]) by orsmga106.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 20 Mar 2019 02:47:06 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.60,248,1549958400"; d="scan'208";a="126997229" Received: from irsmsx105.ger.corp.intel.com ([163.33.3.28]) by orsmga008.jf.intel.com with ESMTP; 20 Mar 2019 02:47:03 -0700 Received: from irsmsx156.ger.corp.intel.com (10.108.20.68) by irsmsx105.ger.corp.intel.com (163.33.3.28) with Microsoft SMTP Server (TLS) id 14.3.408.0; Wed, 20 Mar 2019 09:47:03 +0000 Received: from irsmsx105.ger.corp.intel.com ([169.254.7.210]) by IRSMSX156.ger.corp.intel.com ([169.254.3.101]) with mapi id 14.03.0415.000; Wed, 20 Mar 2019 09:47:02 +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+36YMpFOAgAYWZYCAAARN4IABQcUAgAAyNpA= Date: Wed, 20 Mar 2019 09:47:01 +0000 Message-ID: <2601191342CEEE43887BDE71AB977258013655DA5E@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> <2601191342CEEE43887BDE71AB977258013655D209@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: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiMWIyOTExZmItNmU1Yi00MWMyLTk0MWUtODQzMmMxYjkyYTRjIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiNDYyQ2YzeVNXZ3paUG5vR2NLWEhyZmREaFJXVW1tc1FjS01pZTVISTh4U2NlM3Y3Qm1mVVYyTWVxNk5YTmZuMCJ9 x-ctpclassification: CTP_NT dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-originating-ip: [163.33.239.181] 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: Wed, 20 Mar 2019 09:47:08 -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 wa= iting > > > > > + * thread a ticket and take the lock one by one, first come, fir= st > > > > > + * serviced. > > > > > + * > > > > > + * All locks must be initialised before use, and only initialise= d once. > > > > > + * > > > > > + */ > > > > > + > > > > > +#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= really long > > > > context switch, > > > > > > By saying context switch, do you mean running to here, it is out of C= PU time > > and starving for CPU? > > > > Yes. > > > > > > > > > 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 suc= cess? > > > > > > If this thread was swapped out and another thread took/attempted to t= ake > > 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 signif= icant > > amount of cycles, > > and in that period tl->next and tl->current were wrapped around (they b= oth > > reached UINT16_MAX, then 0). > > i.e. UINT16_MAX lock/unlock were executed while this thread was away fr= om > > cpu. > > After that another thread just did successful lock(), so tl->next=3D=3D= 1 and 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. > > Konstantin > > > Now I understood your points, but not sure if it is a rare or even imposs= ible case for this thread stalls for CPU and during this time, the other > threads have taken the lock for 2^16 times, to wrap up. I am agree it should be very rare, but I am not sure it is impossible. Let say thread is doing lock/unlock in a loop, with one iteration ~100 cycl= es. Then it would wrap around in ~6.5M cycles (~3ms on modern cpus). >=20 > Anyway I made a patch, currently in internal review to fix this issue, th= e basic idea is to compare not only the next, but also the current, and > update the next(+1 and take the lock) only if both of them were not chang= ed(or wrapped up and the lock released). > I will submit the patch after internal review approved. Please let me kno= w if you have more comments. Ok, thanks Konstantin 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 ED8F5A00E6 for ; Wed, 20 Mar 2019 10:47:10 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 061E34C94; Wed, 20 Mar 2019 10:47:10 +0100 (CET) Received: from mga18.intel.com (mga18.intel.com [134.134.136.126]) by dpdk.org (Postfix) with ESMTP id BBE674C91 for ; Wed, 20 Mar 2019 10:47:07 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga008.jf.intel.com ([10.7.209.65]) by orsmga106.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 20 Mar 2019 02:47:06 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.60,248,1549958400"; d="scan'208";a="126997229" Received: from irsmsx105.ger.corp.intel.com ([163.33.3.28]) by orsmga008.jf.intel.com with ESMTP; 20 Mar 2019 02:47:03 -0700 Received: from irsmsx156.ger.corp.intel.com (10.108.20.68) by irsmsx105.ger.corp.intel.com (163.33.3.28) with Microsoft SMTP Server (TLS) id 14.3.408.0; Wed, 20 Mar 2019 09:47:03 +0000 Received: from irsmsx105.ger.corp.intel.com ([169.254.7.210]) by IRSMSX156.ger.corp.intel.com ([169.254.3.101]) with mapi id 14.03.0415.000; Wed, 20 Mar 2019 09:47:02 +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+36YMpFOAgAYWZYCAAARN4IABQcUAgAAyNpA= Date: Wed, 20 Mar 2019 09:47:01 +0000 Message-ID: <2601191342CEEE43887BDE71AB977258013655DA5E@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> <2601191342CEEE43887BDE71AB977258013655D209@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: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiMWIyOTExZmItNmU1Yi00MWMyLTk0MWUtODQzMmMxYjkyYTRjIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiNDYyQ2YzeVNXZ3paUG5vR2NLWEhyZmREaFJXVW1tc1FjS01pZTVISTh4U2NlM3Y3Qm1mVVYyTWVxNk5YTmZuMCJ9 x-ctpclassification: CTP_NT dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-originating-ip: [163.33.239.181] 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: <20190320094701.d9mvus8YReoteYltv10lwknAjZanxwrWbJzTPMx5LZw@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 wa= iting > > > > > + * thread a ticket and take the lock one by one, first come, fir= st > > > > > + * serviced. > > > > > + * > > > > > + * All locks must be initialised before use, and only initialise= d once. > > > > > + * > > > > > + */ > > > > > + > > > > > +#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= really long > > > > context switch, > > > > > > By saying context switch, do you mean running to here, it is out of C= PU time > > and starving for CPU? > > > > Yes. > > > > > > > > > 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 suc= cess? > > > > > > If this thread was swapped out and another thread took/attempted to t= ake > > 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 signif= icant > > amount of cycles, > > and in that period tl->next and tl->current were wrapped around (they b= oth > > reached UINT16_MAX, then 0). > > i.e. UINT16_MAX lock/unlock were executed while this thread was away fr= om > > cpu. > > After that another thread just did successful lock(), so tl->next=3D=3D= 1 and 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. > > Konstantin > > > Now I understood your points, but not sure if it is a rare or even imposs= ible case for this thread stalls for CPU and during this time, the other > threads have taken the lock for 2^16 times, to wrap up. I am agree it should be very rare, but I am not sure it is impossible. Let say thread is doing lock/unlock in a loop, with one iteration ~100 cycl= es. Then it would wrap around in ~6.5M cycles (~3ms on modern cpus). >=20 > Anyway I made a patch, currently in internal review to fix this issue, th= e basic idea is to compare not only the next, but also the current, and > update the next(+1 and take the lock) only if both of them were not chang= ed(or wrapped up and the lock released). > I will submit the patch after internal review approved. Please let me kno= w if you have more comments. Ok, thanks Konstantin