DPDK patches and discussions
 help / color / mirror / Atom feed
From: "Gavin Hu (Arm Technology China)" <Gavin.Hu@arm.com>
To: "Ananyev, Konstantin" <konstantin.ananyev@intel.com>,
	"dev@dpdk.org" <dev@dpdk.org>
Cc: nd <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 <Honnappa.Nagarahalli@arm.com>,
	"Joyce Kong (Arm Technology China)" <Joyce.Kong@arm.com>
Subject: Re: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve	fairness
Date: Wed, 20 Mar 2019 05:11:32 +0000	[thread overview]
Message-ID: <VI1PR08MB3167D370CC1452864E3A8C7A8F410@VI1PR08MB3167.eurprd08.prod.outlook.com> (raw)
Message-ID: <20190320051132.mMIrSnjnzTgxzqo6_nmHXccnQ3oQnrFyQr3RCrsGWJY@z> (raw)
In-Reply-To: <2601191342CEEE43887BDE71AB977258013655D209@irsmsx105.ger.corp.intel.com>

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="UTF-8", Size: 7690 bytes --]

Hi Konstantin,

> -----Original Message-----
> From: Ananyev, Konstantin <konstantin.ananyev@intel.com>
> Sent: Tuesday, March 19, 2019 6:15 PM
> To: Gavin Hu (Arm Technology China) <Gavin.Hu@arm.com>; dev@dpdk.org
> Cc: nd <nd@arm.com>; stephen@networkplumber.org;
> jerin.jacob@caviumnetworks.com; thomas@monjalon.net; Honnappa
> Nagarahalli <Honnappa.Nagarahalli@arm.com>; Joyce Kong (Arm Technology
> China) <Joyce.Kong@arm.com>
> Subject: RE: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve
> fairness
> 
> 
> 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 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 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 = __atomic_fetch_add(&tl->next, 1,
> > > __ATOMIC_RELAXED);
> > > > +	while (__atomic_load_n(&tl->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->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 = __atomic_load_n(&tl->next, __ATOMIC_RELAXED);
> > > > +	uint16_t cur = __atomic_load_n(&tl->current, __ATOMIC_RELAXED);
> > > > +	if (next == cur) {
> > >
> > > Probably a naïve one:
> > > Suppose next==cur==1 here, then this thread will experience really long
> > > context switch,
> >
> > By saying context switch, do you mean running to here, it is out of CPU 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==0 (lock held).
> > > I suppose this function will set tl->next=2 and will return a success?
> >
> > If this thread was swapped out and another thread took/attempted to take
> the lock, yes, tl->next == 2 here,
> > But as next == 1 unchanged, so it would not return a success.
> 
> I am not talking about situation when tl->next == 2,tl->current==1 (just one
> lock() was executed by different thread).
> I am talking about situation when this thread was out of cpu for significant
> amount of cycles,
> and in that period tl->next and tl->current were wrapped around (they both
> reached UINT16_MAX, then 0).
> i.e. UINT16_MAX lock/unlock were executed while this thread was away from
> cpu.
> After that another thread just did successful lock(), so tl->next==1 and tl-
> >current==0.
> Now this thread wakeups and continues with:
> __atomic_compare_exchange_n(&tl->next, &next, next+1, ...)
> As both tl->next==1 and next==1, 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 impossible 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. 

Anyway I made a patch, currently in internal review to fix this issue, the 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 changed(or wrapped up and the lock released).
I will submit the patch after internal review approved. Please let me know if you have more comments.

> >
> > > Wouldn't be better here and in _is_locked_ to do load/store for
> > > next/current values in one go
> > > (using 32bit op)?
> > > Konstantin
> >
> > To load both in one go is feasible, but no necessary as we need to compare
> them.
> > We don't need store both as in this function tl->current is read only.
> > tl->next is read-update-store, I ever thought of combining the two if-
> statements to one __atomic_compare_exchange_n(&(&tl->next,&tl-
> > >current, tl->next+1, ...),
> > but tl->next+1 is out of atomicity and may be the old value and corrupt the
> ticket lock waiting chain.
> >
> > The current code works ok except it may fail spuriously(in case during
> context switch, the lock was taken and released by other threads,
> > moving tl->next forward, in this case
> > The lock is available but not obtained by this trylock).  Anyway, as the name
> suggests, it is a try/attempt, a spurious fail is not a big deal?
> > And in most cases, dpdk running on dedicated cores,
> > the context switch will not happen at all.
> >
> > Any more comments are welcome!
> > >
> > > > +		if (__atomic_compare_exchange_n(&tl->next, &next,
> > > next+1,
> > > > +		    0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
> > > > +			return 1;
> > > > +	}
> > > > +
> > > > +	return 0;
> > > > +}
> > > > +
> > > > +/**
> > > > + * 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_ACQUIRE) !=
> > > > +		__atomic_load_n(&tl->next, __ATOMIC_ACQUIRE));
> > > > +}
> > > > +

  parent reply	other threads:[~2019-03-20  5:11 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) [this message]
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=VI1PR08MB3167D370CC1452864E3A8C7A8F410@VI1PR08MB3167.eurprd08.prod.outlook.com \
    --to=gavin.hu@arm.com \
    --cc=Honnappa.Nagarahalli@arm.com \
    --cc=Joyce.Kong@arm.com \
    --cc=dev@dpdk.org \
    --cc=jerin.jacob@caviumnetworks.com \
    --cc=konstantin.ananyev@intel.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).