From: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>
To: "Gavin Hu (Arm Technology China)" <Gavin.Hu@arm.com>,
"dev@dpdk.org" <dev@dpdk.org>
Cc: "thomas@monjalon.net" <thomas@monjalon.net>,
"jerinj@marvell.com" <jerinj@marvell.com>,
"hemant.agrawal@nxp.com" <hemant.agrawal@nxp.com>,
"stephen@networkplumber.org" <stephen@networkplumber.org>,
nd <nd@arm.com>,
"Gavin Hu (Arm Technology China)" <Gavin.Hu@arm.com>,
"Joyce Kong (Arm Technology China)" <Joyce.Kong@arm.com>,
nd <nd@arm.com>
Subject: Re: [dpdk-dev] [PATCH v1] ticketlock: ticket based to improve fairness
Date: Mon, 14 Jan 2019 23:36:45 +0000 [thread overview]
Message-ID: <AM6PR08MB3672713EEEDE7185028518D898800@AM6PR08MB3672.eurprd08.prod.outlook.com> (raw)
In-Reply-To: <20190113144631.23493-1-gavin.hu@arm.com>
> Subject: [PATCH v1] ticketlock: ticket based to improve fairness
>
> From: Joyce Kong <joyce.kong@arm.com>
>
> The spinlock implementation is unfair, some threads may take locks
> aggressively while leaving the other threads starving for long time. As shown
> in the following test, within same period of time, there are threads taking
> locks much more times than the others.
>
> The ticketlock 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.
>
> *** spinlock_autotest without this patch *** Core [0] count = 89 Core [1]
> count = 84 Core [2] count = 94 ...
> Core [208] count = 171
> Core [209] count = 152
> Core [210] count = 161
> Core [211] count = 187
>
> *** spinlock_autotest with this patch *** Core [0] count = 534 Core [1] count
> = 533 Core [2] count = 542 ...
> Core [208] count = 554
> Core [209] count = 556
> Core [210] count = 555
> Core [211] count = 551
>
> Signed-off-by: Joyce Kong <joyce.kong@arm.com>
> Signed-off-by: Gavin Hu <gavin.hu@arm.com>
> ---
> .../common/include/generic/rte_ticketlock.h | 203
> +++++++++++++++++++++
> lib/librte_eal/rte_eal_version.map | 8 +
> 2 files changed, 211 insertions(+)
> create mode 100644 lib/librte_eal/common/include/generic/rte_ticketlock.h
>
> 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 000000000..9d044bb31
> --- /dev/null
> +++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h
> @@ -0,0 +1,203 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2018-2019 Arm Corporation */
^^^^^^^^^^
Should be 'Limited'
> +
> +#ifndef _RTE_TICKETLOCK_H_
> +#define _RTE_TICKETLOCK_H_
> +
> +/**
> + * @file
> + *
> + * RTE ticketlocks
> + *
> + * This file defines an API for read-write locks, which are implemented
> + * in an architecture-specific way. This kind of lock simply waits in
> + * a loop repeatedly checking until the lock becomes available.
Needs update for ticket lock
> + *
> + * All locks must be initialised before use, and only initialised once.
> + *
> + */
> +
> +#include <rte_lcore.h>
> +#include <rte_common.h>
> +#include <rte_pause.h>
> +
> +/**
> + * The rte_ticketlock_t type.
> + */
> +typedef struct {
> + uint16_t current;
> + uint16_t next;
Any reason these are 16b?
Use 'volatile' for consistency with rte_spinlock_t? (though I do not prefer to use 'volatile' in general)
> +} 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);
> +
> +static inline __rte_experimental void
> +rte_ticketlock_lock(rte_ticketlock_t *tl) {
> + uint16_t me = __atomic_fetch_add(&tl->next, 1, __ATOMIC_RELAXED);
> + while (__atomic_load_n(&tl->current, __ATOMIC_ACQUIRE) != me)
> + rte_pause();
> +}
Do we need to place the APIs under RTE_FORCE_INTRINSICS flag? I see that x86 has implementation which does not use intrinsics (lib/librte_eal/common/include/arch/x86/rte_spinlock.h).
> +
> +/**
> + * Release the ticketlock.
> + *
> + * @param tl
> + * A pointer to the ticketlock.
> + */
> +static inline __rte_experimental void
> +rte_ticketlock_unlock(rte_ticketlock_t *tl);
> +
> +static inline __rte_experimental void
> +rte_ticketlock_unlock(rte_ticketlock_t *tl) {
> + uint16_t i = __atomic_load_n(&tl->current, __ATOMIC_RELAXED);
> + i++;
> + __atomic_store_n(&tl->current, i, __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 me = __atomic_fetch_add(&tl->next, 1, __ATOMIC_RELAXED);
> + while (__atomic_load_n(&tl->current, __ATOMIC_RELAXED) != me) {
What happens if other threads incremented 'tl->next' here?
> + __atomic_sub_fetch(&tl->next, 1, __ATOMIC_RELAXED);
> + return 0;
> + }
> +
> + return 1;
> +}
IMO, this implementation needs to be changed. We should try to take the lock if tl->next and tl->current are equal. Then tl->next should be incremented using a CAS (which makes sure no one else has taken the lock in the meanwhile)
> +
> +/**
> + * 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_RELAXED) !=
Load of tl->current should be __ATOMIC_ACQUIRE
> + __atomic_load_n(&tl->next, __ATOMIC_RELAXED)); }
> +
> +/**
> + * The rte_ticketlock_recursive_t type.
> + */
> +typedef struct {
> + rte_ticketlock_t tl; /**< the actual ticketlock */
> + volatile int user; /**< core id using lock, -1 for unused */
> + volatile int count; /**< count of time this lock has been called */ }
'count' can be 'unsigned int'?
> +rte_ticketlock_recursive_t;
> +
> +/**
> + * A static recursive ticketlock initializer.
> + */
> +#define RTE_TICKETLOCK_RECURSIVE_INITIALIZER
> +{RTE_TICKETLOCK_INITIALIZER, -1, 0}
> +
> +/**
> + * Initialize the recursive ticketlock to an unlocked state.
> + *
> + * @param tlr
> + * A pointer to the recursive ticketlock.
> + */
> +static inline __rte_experimental void rte_ticketlock_recursive_init(
> + rte_ticketlock_recursive_t *tlr)
> +{
> + rte_ticketlock_init(&tlr->tl);
> + tlr->user = -1;
> + tlr->count = 0;
> +}
> +
> +/**
> + * Take the recursive ticketlock.
> + *
> + * @param tlr
> + * A pointer to the recursive ticketlock.
> + */
> +static inline __rte_experimental void rte_ticketlock_recursive_lock(
> + rte_ticketlock_recursive_t *tlr)
> +{
> + int id = rte_gettid();
> +
> + if (tlr->user != id) {
> + rte_ticketlock_lock(&tlr->tl);
> + tlr->user = id;
> + }
> + tlr->count++;
> +}
> +/**
> + * Release the recursive ticketlock.
> + *
> + * @param tlr
> + * A pointer to the recursive ticketlock.
> + */
> +static inline __rte_experimental void rte_ticketlock_recursive_unlock(
> + rte_ticketlock_recursive_t *tlr)
> +{
> + if (--(tlr->count) == 0) {
> + tlr->user = -1;
> + rte_ticketlock_unlock(&tlr->tl);
> + }
> +
Minor comment. Extra line.
> +}
> +
> +/**
> + * Try to take the recursive lock.
> + *
> + * @param tlr
> + * A pointer to the recursive ticketlock.
> + * @return
> + * 1 if the lock is successfully taken; 0 otherwise.
> + */
> +static inline __rte_experimental int rte_ticketlock_recursive_trylock(
> + rte_ticketlock_recursive_t *tlr)
> +{
> + int id = rte_gettid();
> +
> + if (tlr->user != id) {
> + if (rte_ticketlock_trylock(&tlr->tl) == 0)
> + return 0;
> + tlr->user = id;
> + }
> + tlr->count++;
> + return 1;
> +}
> +
> +#endif /* _RTE_TICKETLOCK_H_ */
> diff --git a/lib/librte_eal/rte_eal_version.map
> b/lib/librte_eal/rte_eal_version.map
> index eb5f7b9cb..f1841effa 100644
> --- a/lib/librte_eal/rte_eal_version.map
> +++ b/lib/librte_eal/rte_eal_version.map
> @@ -364,4 +364,12 @@ EXPERIMENTAL {
> rte_service_may_be_active;
> rte_socket_count;
> rte_socket_id_by_idx;
> + rte_ticketlock_lock;
> + rte_ticketlock_unlock;
> + rte_ticketlock_islocked;
> + rte_ticketlock_trylock;
> + rte_ticketlock_recurrsive_lock;
> + rte_ticketlock_recurrsive_unlock;
> + rte_ticketlock_recurrsive_islocked;
> + rte_ticketlock_recurrsive_trylock;
These are all 'inline' functions, they do not need to be versioned.
> };
> --
> 2.11.0
next prev parent reply other threads:[~2019-01-14 23:36 UTC|newest]
Thread overview: 74+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-01-13 14:46 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 ` Honnappa Nagarahalli [this message]
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
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=AM6PR08MB3672713EEEDE7185028518D898800@AM6PR08MB3672.eurprd08.prod.outlook.com \
--to=honnappa.nagarahalli@arm.com \
--cc=Gavin.Hu@arm.com \
--cc=Joyce.Kong@arm.com \
--cc=dev@dpdk.org \
--cc=hemant.agrawal@nxp.com \
--cc=jerinj@marvell.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).