From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <dev-bounces@dpdk.org>
Received: from dpdk.org (dpdk.org [92.243.14.124])
by dpdk.space (Postfix) with ESMTP id 69DE9A00E6
for <public@inbox.dpdk.org>; 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 <dev@dpdk.org>; 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" <konstantin.ananyev@intel.com>
To: Joyce Kong <joyce.kong@arm.com>, "dev@dpdk.org" <dev@dpdk.org>
CC: "nd@arm.com" <nd@arm.com>, "stephen@networkplumber.org"
<stephen@networkplumber.org>, "jerin.jacob@caviumnetworks.com"
<jerin.jacob@caviumnetworks.com>, "thomas@monjalon.net"
<thomas@monjalon.net>, "honnappa.nagarahalli@arm.com"
<honnappa.nagarahalli@arm.com>, "gavin.hu@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 <dev.dpdk.org>
List-Unsubscribe: <https://mails.dpdk.org/options/dev>,
<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>,
<mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.org>
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 <jerinj@marvell.com>
> Signed-off-by: Joyce Kong <joyce.kong@arm.com>
> Reviewed-by: Gavin Hu <gavin.hu@arm.com>
> Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>
> Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
> ---
> 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 <cristian.dumitrescu@intel.co=
m>
> F: lib/librte_eal/common/include/rte_bitmap.h
> F: app/test/test_bitmap.c
>=20
> +Ticketlock
> +M: Joyce Kong <joyce.kong@arm.com>
> +F: lib/librte_eal/common/include/generic/rte_ticketlock.h
> +
> ARM v7
> M: Jan Viktorin <viktorin@rehivetech.com>
> M: Gavin Hu <gavin.hu@arm.com>
> 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 <rte_common.h>
> +#include <rte_lcore.h>
> +#include <rte_pause.h>
> +
> +/**
> + * 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 <konstantin.ananyev@intel.com>
> + 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;
> +}
> +