DPDK patches and discussions
 help / color / mirror / Atom feed
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>
Subject: Re: [dpdk-dev] [PATCH v7 1/3] eal/ticketlock: ticket based to improve fairness
Date: Fri, 22 Mar 2019 10:56:31 +0000	[thread overview]
Message-ID: <2601191342CEEE43887BDE71AB977258013655EAF6@irsmsx105.ger.corp.intel.com> (raw)
Message-ID: <20190322105631.xZj0tonbdtu5YRDFEfKVqRG6Q65eE-y2E8BqqwFpc9Y@z> (raw)
In-Reply-To: <1553159755-206102-1-git-send-email-joyce.kong@arm.com>

Hi Joyce,

> 
> The spinlock implementation is unfair, some threads may take locks
> aggressively while leaving the other threads starving for long time.
> 
> 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.
> 
> 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
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 452b8eb..3521271 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -210,6 +210,10 @@ M: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
>  F: lib/librte_eal/common/include/rte_bitmap.h
>  F: app/test/test_bitmap.c
> 
> +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)
> 
>  - **CPU arch**:
>    [branch prediction]  (@ref rte_branch_prediction.h),
> diff --git a/lib/librte_eal/common/Makefile b/lib/librte_eal/common/Makefile
> index c487201..ac3305c 100644
> --- a/lib/librte_eal/common/Makefile
> +++ b/lib/librte_eal/common/Makefile
> @@ -20,7 +20,7 @@ INC += rte_bitmap.h rte_vfio.h rte_hypervisor.h rte_test.h
>  INC += rte_reciprocal.h rte_fbarray.h rte_uuid.h
> 
>  GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h
> -GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h
> +GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h rte_ticketlock.h
>  GENERIC_INC += rte_vect.h rte_pause.h rte_io.h
> 
>  # 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 = __atomic_fetch_add(&tl->s.next, 1, __ATOMIC_RELAXED);
> +	while (__atomic_load_n(&tl->s.current, __ATOMIC_ACQUIRE) != 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 = __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 = __atomic_load_n(&tl->tickets, __ATOMIC_RELAXED);
> +	new.tickets = __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 = old.tickets;

Apart from that:
Acked-by: Konstantin Ananyev <konstantin.ananyev@intel.com>


> +	new.s.next++;
> +	if (old.s.next == old.s.current) {
> +		if (__atomic_compare_exchange_n(&tl->tickets, &old.tickets,
> +		    new.tickets, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
> +			return 1;
> +	}
> +
> +	return 0;
> +}
> +

  parent reply	other threads:[~2019-03-22 10:56 UTC|newest]

Thread overview: 74+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-01-13 14:46 [dpdk-dev] [PATCH v1] ticketlock: " Gavin Hu
2019-01-14  7:59 ` [dpdk-dev] [EXT] " Jerin Jacob Kollanukkaran
2019-01-14 16:57   ` Gavin Hu (Arm Technology China)
2019-01-14 23:36 ` [dpdk-dev] " Honnappa Nagarahalli
2019-01-18  9:15 ` [dpdk-dev] [PATCH v2 1/2] " Joyce Kong
2019-01-25  8:37   ` [dpdk-dev] [PATCH v3 0/2] ticketlock: implement ticketlock and add test case Joyce Kong
2019-02-19 10:48     ` [dpdk-dev] [PATCH v4 " Joyce Kong
2019-03-11  5:52       ` [dpdk-dev] [PATCH v5 " Joyce Kong
2019-02-19 10:48     ` [dpdk-dev] [PATCH v4 1/2] ticketlock: ticket based to improve fairness Joyce Kong
2019-03-11  5:52       ` [dpdk-dev] [PATCH v5 1/2] eal/ticketlock: " Joyce Kong
2019-03-13  9:41         ` Jerin Jacob Kollanukkaran
2019-03-15  6:57           ` Joyce Kong (Arm Technology China)
2019-03-15  6:57             ` Joyce Kong (Arm Technology China)
2019-03-13 15:36         ` Jerin Jacob Kollanukkaran
2019-03-15  6:58           ` Joyce Kong (Arm Technology China)
2019-03-15  6:58             ` Joyce Kong (Arm Technology China)
2019-02-19 10:48     ` [dpdk-dev] [PATCH v4 2/2] test/ticketlock: add ticket lock test case Joyce Kong
2019-03-11  5:52       ` [dpdk-dev] [PATCH v5 " Joyce Kong
2019-03-13 13:31         ` Jerin Jacob Kollanukkaran
2019-03-15  6:57           ` Joyce Kong (Arm Technology China)
2019-03-15  6:57             ` Joyce Kong (Arm Technology China)
2019-01-25  8:37   ` [dpdk-dev] [PATCH v3 1/2] ticketlock: ticket based to improve fairness Joyce Kong
2019-01-25  8:37   ` [dpdk-dev] [PATCH v3 2/2] test/ticketlock: add ticket lock test case Joyce Kong
2019-03-15  6:56   ` [dpdk-dev] [PATCH v6 0/2] ticketlock: implement ticketlock and add " Joyce Kong
2019-03-15  6:56     ` Joyce Kong
2019-03-15  6:56   ` [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve fairness Joyce Kong
2019-03-15  6:56     ` Joyce Kong
2019-03-15 12:55     ` Ananyev, Konstantin
2019-03-15 12:55       ` Ananyev, Konstantin
2019-03-19  9:44       ` Gavin Hu (Arm Technology China)
2019-03-19  9:44         ` Gavin Hu (Arm Technology China)
2019-03-19 10:15         ` Ananyev, Konstantin
2019-03-19 10:15           ` Ananyev, Konstantin
2019-03-20  5:11           ` Gavin Hu (Arm Technology China)
2019-03-20  5:11             ` Gavin Hu (Arm Technology China)
2019-03-20  9:47             ` Ananyev, Konstantin
2019-03-20  9:47               ` Ananyev, Konstantin
2019-03-22  2:04               ` Gavin Hu (Arm Technology China)
2019-03-22  2:04                 ` Gavin Hu (Arm Technology China)
2019-03-15  6:56   ` [dpdk-dev] [PATCH v6 2/2] test/ticketlock: add ticket lock test case Joyce Kong
2019-03-15  6:56     ` Joyce Kong
2019-03-21  9:13   ` [dpdk-dev] [PATCH v7 0/3] ticketlock: implement ticketlock and add " Joyce Kong
2019-03-21  9:13     ` Joyce Kong
2019-03-21  9:13   ` [dpdk-dev] [PATCH v7 2/3] eal/ticketlock: enable generic ticketlock on all arch Joyce Kong
2019-03-21  9:13     ` Joyce Kong
2019-03-21  9:13   ` [dpdk-dev] [PATCH v7 3/3] test/ticketlock: add ticket lock test case Joyce Kong
2019-03-21  9:13     ` Joyce Kong
2019-03-22 11:38     ` Ananyev, Konstantin
2019-03-22 11:38       ` Ananyev, Konstantin
2019-03-25 10:25       ` Joyce Kong (Arm Technology China)
2019-03-25 10:25         ` Joyce Kong (Arm Technology China)
2019-03-21  9:15   ` [dpdk-dev] [PATCH v7 1/3] eal/ticketlock: ticket based to improve fairness Joyce Kong
2019-03-21  9:15     ` Joyce Kong
2019-03-22 10:56     ` Ananyev, Konstantin [this message]
2019-03-22 10:56       ` Ananyev, Konstantin
2019-03-25 11:11   ` [dpdk-dev] [PATCH v8 0/3] ticketlock: implement ticketlock and add test case Joyce Kong
2019-03-25 11:11     ` Joyce Kong
2019-03-27 11:20     ` Ananyev, Konstantin
2019-03-27 11:20       ` Ananyev, Konstantin
2019-03-28 14:02       ` Thomas Monjalon
2019-03-28 14:02         ` Thomas Monjalon
2019-03-25 11:11   ` [dpdk-dev] [PATCH v8 1/3] eal/ticketlock: ticket based to improve fairness Joyce Kong
2019-03-25 11:11     ` Joyce Kong
2019-03-25 11:11   ` [dpdk-dev] [PATCH v8 2/3] eal/ticketlock: enable generic ticketlock on all arch Joyce Kong
2019-03-25 11:11     ` Joyce Kong
2019-03-25 11:11   ` [dpdk-dev] [PATCH v8 3/3] test/ticketlock: add ticket lock test case Joyce Kong
2019-03-25 11:11     ` Joyce Kong
2019-04-08 20:18     ` David Marchand
2019-04-08 20:18       ` David Marchand
2019-04-14 20:37       ` Thomas Monjalon
2019-04-14 20:37         ` Thomas Monjalon
2019-04-15  9:07         ` Joyce Kong (Arm Technology China)
2019-04-15  9:07           ` Joyce Kong (Arm Technology China)
2019-01-18  9:15 ` [dpdk-dev] [PATCH v2 2/2] " Joyce Kong

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=2601191342CEEE43887BDE71AB977258013655EAF6@irsmsx105.ger.corp.intel.com \
    --to=konstantin.ananyev@intel.com \
    --cc=dev@dpdk.org \
    --cc=gavin.hu@arm.com \
    --cc=honnappa.nagarahalli@arm.com \
    --cc=jerin.jacob@caviumnetworks.com \
    --cc=joyce.kong@arm.com \
    --cc=nd@arm.com \
    --cc=stephen@networkplumber.org \
    --cc=thomas@monjalon.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).