From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 222EA1B59D for ; Fri, 22 Mar 2019 11:56:35 +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 fmsmga102.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 22 Mar 2019 03:56:35 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.60,256,1549958400"; d="scan'208";a="127681732" Received: from irsmsx151.ger.corp.intel.com ([163.33.192.59]) by orsmga008.jf.intel.com with ESMTP; 22 Mar 2019 03:56:32 -0700 Received: from irsmsx105.ger.corp.intel.com ([169.254.7.210]) by IRSMSX151.ger.corp.intel.com ([169.254.4.91]) with mapi id 14.03.0415.000; Fri, 22 Mar 2019 10:56:32 +0000 From: "Ananyev, Konstantin" To: Joyce Kong , "dev@dpdk.org" CC: "nd@arm.com" , "stephen@networkplumber.org" , "jerin.jacob@caviumnetworks.com" , "thomas@monjalon.net" , "honnappa.nagarahalli@arm.com" , "gavin.hu@arm.com" Thread-Topic: [PATCH v7 1/3] eal/ticketlock: ticket based to improve fairness Thread-Index: AQHU38bX3gbbqY1av0Wro5aW+hYhd6YXe0Wg Date: Fri, 22 Mar 2019 10:56:31 +0000 Message-ID: <2601191342CEEE43887BDE71AB977258013655EAF6@irsmsx105.ger.corp.intel.com> References: <1547802943-18711-1-git-send-email-joyce.kong@arm.com> <1553159755-206102-1-git-send-email-joyce.kong@arm.com> In-Reply-To: <1553159755-206102-1-git-send-email-joyce.kong@arm.com> Accept-Language: en-IE, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiZGNkMTNlNDQtMTg5MS00NGY2LWI1YjYtYmE1NWUxN2NlMGQ3IiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiYmtqZ1dZZWZWSzY2OUlcLzVXVG9jU2Nhc0JINDE4N0JEWlltWU1NWHBUZDNpS3N4QTlLVDJwQjdIVmhwVlVRN0IifQ== 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="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH v7 1/3] 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: Fri, 22 Mar 2019 10:56:36 -0000 Hi Joyce, >=20 > The spinlock implementation is unfair, some threads may take locks > aggressively while leaving the other threads starving for long time. >=20 > This patch introduces ticketlock which gives each waiting thread a > ticket and they can take the lock one by one. First come, first serviced. > This avoids starvation for too long time and is more predictable. >=20 > Suggested-by: Jerin Jacob > Signed-off-by: Joyce Kong > Reviewed-by: Gavin Hu > Reviewed-by: Ola Liljedahl > Reviewed-by: Honnappa Nagarahalli > --- > MAINTAINERS | 4 + > doc/api/doxy-api-index.md | 1 + > lib/librte_eal/common/Makefile | 2 +- > .../common/include/generic/rte_ticketlock.h | 215 +++++++++++++++= ++++++ > lib/librte_eal/common/meson.build | 1 + > 5 files changed, 222 insertions(+), 1 deletion(-) > create mode 100644 lib/librte_eal/common/include/generic/rte_ticketlock.= h >=20 > diff --git a/MAINTAINERS b/MAINTAINERS > index 452b8eb..3521271 100644 > --- a/MAINTAINERS > +++ b/MAINTAINERS > @@ -210,6 +210,10 @@ M: Cristian Dumitrescu > F: lib/librte_eal/common/include/rte_bitmap.h > F: app/test/test_bitmap.c >=20 > +Ticketlock > +M: Joyce Kong > +F: lib/librte_eal/common/include/generic/rte_ticketlock.h > + > ARM v7 > M: Jan Viktorin > M: Gavin Hu > diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md > index d95ad56..aacc66b 100644 > --- a/doc/api/doxy-api-index.md > +++ b/doc/api/doxy-api-index.md > @@ -65,6 +65,7 @@ The public API headers are grouped by topics: > [atomic] (@ref rte_atomic.h), > [rwlock] (@ref rte_rwlock.h), > [spinlock] (@ref rte_spinlock.h) > + [ticketlock] (@ref rte_ticketlock.h) >=20 > - **CPU arch**: > [branch prediction] (@ref rte_branch_prediction.h), > diff --git a/lib/librte_eal/common/Makefile b/lib/librte_eal/common/Makef= ile > index c487201..ac3305c 100644 > --- a/lib/librte_eal/common/Makefile > +++ b/lib/librte_eal/common/Makefile > @@ -20,7 +20,7 @@ INC +=3D rte_bitmap.h rte_vfio.h rte_hypervisor.h rte_t= est.h > INC +=3D rte_reciprocal.h rte_fbarray.h rte_uuid.h >=20 > GENERIC_INC :=3D rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.= h > -GENERIC_INC +=3D rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h > +GENERIC_INC +=3D rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h= rte_ticketlock.h > GENERIC_INC +=3D rte_vect.h rte_pause.h rte_io.h >=20 > # defined in mk/arch/$(RTE_ARCH)/rte.vars.mk > 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..c5203cb > --- /dev/null > +++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h > @@ -0,0 +1,215 @@ > +/* 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 waiting > + * thread a ticket and take the lock one by one, first come, first > + * serviced. > + * > + * All locks must be initialised before use, and only initialised once. > + * > + */ > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +#include > +#include > +#include > + > +/** > + * The rte_ticketlock_t type. > + */ > +typedef union { > + uint32_t tickets; > + struct { > + uint16_t current; > + uint16_t next; > + } s; > +} 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->tickets, 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->s.next, 1, __ATOMIC_RELAXED); > + while (__atomic_load_n(&tl->s.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->s.current, __ATOMIC_RELAXED); > + __atomic_store_n(&tl->s.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) > +{ > + rte_ticketlock_t old, new; > + old.tickets =3D __atomic_load_n(&tl->tickets, __ATOMIC_RELAXED); > + new.tickets =3D __atomic_load_n(&tl->tickets, __ATOMIC_RELAXED); As a nit: from my point, there is no need for second load, we can just do: new.tickets =3D old.tickets; Apart from that: Acked-by: Konstantin Ananyev > + new.s.next++; > + if (old.s.next =3D=3D old.s.current) { > + if (__atomic_compare_exchange_n(&tl->tickets, &old.tickets, > + new.tickets, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) > + return 1; > + } > + > + return 0; > +} > + 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 69DE9A00E6 for ; Fri, 22 Mar 2019 11:56:38 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 179E21B5AA; Fri, 22 Mar 2019 11:56:38 +0100 (CET) Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 222EA1B59D for ; Fri, 22 Mar 2019 11:56:35 +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 fmsmga102.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 22 Mar 2019 03:56:35 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.60,256,1549958400"; d="scan'208";a="127681732" Received: from irsmsx151.ger.corp.intel.com ([163.33.192.59]) by orsmga008.jf.intel.com with ESMTP; 22 Mar 2019 03:56:32 -0700 Received: from irsmsx105.ger.corp.intel.com ([169.254.7.210]) by IRSMSX151.ger.corp.intel.com ([169.254.4.91]) with mapi id 14.03.0415.000; Fri, 22 Mar 2019 10:56:32 +0000 From: "Ananyev, Konstantin" To: Joyce Kong , "dev@dpdk.org" CC: "nd@arm.com" , "stephen@networkplumber.org" , "jerin.jacob@caviumnetworks.com" , "thomas@monjalon.net" , "honnappa.nagarahalli@arm.com" , "gavin.hu@arm.com" Thread-Topic: [PATCH v7 1/3] eal/ticketlock: ticket based to improve fairness Thread-Index: AQHU38bX3gbbqY1av0Wro5aW+hYhd6YXe0Wg Date: Fri, 22 Mar 2019 10:56:31 +0000 Message-ID: <2601191342CEEE43887BDE71AB977258013655EAF6@irsmsx105.ger.corp.intel.com> References: <1547802943-18711-1-git-send-email-joyce.kong@arm.com> <1553159755-206102-1-git-send-email-joyce.kong@arm.com> In-Reply-To: <1553159755-206102-1-git-send-email-joyce.kong@arm.com> Accept-Language: en-IE, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiZGNkMTNlNDQtMTg5MS00NGY2LWI1YjYtYmE1NWUxN2NlMGQ3IiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiYmtqZ1dZZWZWSzY2OUlcLzVXVG9jU2Nhc0JINDE4N0JEWlltWU1NWHBUZDNpS3N4QTlLVDJwQjdIVmhwVlVRN0IifQ== 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 v7 1/3] 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: <20190322105631.xZj0tonbdtu5YRDFEfKVqRG6Q65eE-y2E8BqqwFpc9Y@z> Hi Joyce, >=20 > The spinlock implementation is unfair, some threads may take locks > aggressively while leaving the other threads starving for long time. >=20 > This patch introduces ticketlock which gives each waiting thread a > ticket and they can take the lock one by one. First come, first serviced. > This avoids starvation for too long time and is more predictable. >=20 > Suggested-by: Jerin Jacob > Signed-off-by: Joyce Kong > Reviewed-by: Gavin Hu > Reviewed-by: Ola Liljedahl > Reviewed-by: Honnappa Nagarahalli > --- > MAINTAINERS | 4 + > doc/api/doxy-api-index.md | 1 + > lib/librte_eal/common/Makefile | 2 +- > .../common/include/generic/rte_ticketlock.h | 215 +++++++++++++++= ++++++ > lib/librte_eal/common/meson.build | 1 + > 5 files changed, 222 insertions(+), 1 deletion(-) > create mode 100644 lib/librte_eal/common/include/generic/rte_ticketlock.= h >=20 > diff --git a/MAINTAINERS b/MAINTAINERS > index 452b8eb..3521271 100644 > --- a/MAINTAINERS > +++ b/MAINTAINERS > @@ -210,6 +210,10 @@ M: Cristian Dumitrescu > F: lib/librte_eal/common/include/rte_bitmap.h > F: app/test/test_bitmap.c >=20 > +Ticketlock > +M: Joyce Kong > +F: lib/librte_eal/common/include/generic/rte_ticketlock.h > + > ARM v7 > M: Jan Viktorin > M: Gavin Hu > diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md > index d95ad56..aacc66b 100644 > --- a/doc/api/doxy-api-index.md > +++ b/doc/api/doxy-api-index.md > @@ -65,6 +65,7 @@ The public API headers are grouped by topics: > [atomic] (@ref rte_atomic.h), > [rwlock] (@ref rte_rwlock.h), > [spinlock] (@ref rte_spinlock.h) > + [ticketlock] (@ref rte_ticketlock.h) >=20 > - **CPU arch**: > [branch prediction] (@ref rte_branch_prediction.h), > diff --git a/lib/librte_eal/common/Makefile b/lib/librte_eal/common/Makef= ile > index c487201..ac3305c 100644 > --- a/lib/librte_eal/common/Makefile > +++ b/lib/librte_eal/common/Makefile > @@ -20,7 +20,7 @@ INC +=3D rte_bitmap.h rte_vfio.h rte_hypervisor.h rte_t= est.h > INC +=3D rte_reciprocal.h rte_fbarray.h rte_uuid.h >=20 > GENERIC_INC :=3D rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.= h > -GENERIC_INC +=3D rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h > +GENERIC_INC +=3D rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h= rte_ticketlock.h > GENERIC_INC +=3D rte_vect.h rte_pause.h rte_io.h >=20 > # defined in mk/arch/$(RTE_ARCH)/rte.vars.mk > 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..c5203cb > --- /dev/null > +++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h > @@ -0,0 +1,215 @@ > +/* 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 waiting > + * thread a ticket and take the lock one by one, first come, first > + * serviced. > + * > + * All locks must be initialised before use, and only initialised once. > + * > + */ > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +#include > +#include > +#include > + > +/** > + * The rte_ticketlock_t type. > + */ > +typedef union { > + uint32_t tickets; > + struct { > + uint16_t current; > + uint16_t next; > + } s; > +} 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->tickets, 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->s.next, 1, __ATOMIC_RELAXED); > + while (__atomic_load_n(&tl->s.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->s.current, __ATOMIC_RELAXED); > + __atomic_store_n(&tl->s.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) > +{ > + rte_ticketlock_t old, new; > + old.tickets =3D __atomic_load_n(&tl->tickets, __ATOMIC_RELAXED); > + new.tickets =3D __atomic_load_n(&tl->tickets, __ATOMIC_RELAXED); As a nit: from my point, there is no need for second load, we can just do: new.tickets =3D old.tickets; Apart from that: Acked-by: Konstantin Ananyev > + new.s.next++; > + if (old.s.next =3D=3D old.s.current) { > + if (__atomic_compare_exchange_n(&tl->tickets, &old.tickets, > + new.tickets, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) > + return 1; > + } > + > + return 0; > +} > +