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: Fri, 22 Mar 2019 02:04:44 +0000	[thread overview]
Message-ID: <VI1PR08MB31673F3727C9CD1F402E3E448F430@VI1PR08MB3167.eurprd08.prod.outlook.com> (raw)
In-Reply-To: <2601191342CEEE43887BDE71AB977258013655DA5E@irsmsx105.ger.corp.intel.com>

Hi Konstantin, 

> -----Original Message-----
> From: Ananyev, Konstantin <konstantin.ananyev@intel.com>
> Sent: Wednesday, March 20, 2019 5:47 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.
> 
> I am agree it should be very rare, but I am not sure it is impossible.
> Let say thread is doing lock/unlock in a loop, with one iteration ~100 cycles.
> Then it would wrap around in ~6.5M cycles (~3ms on modern cpus).
> 

Thanks, agree, your quantitative way of analysis  helped me understand the issue.

> >
> > 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.
> 
> Ok, thanks
> Konstantin

The fix was submitted into v7, 1/3, could you help review? 

Thanks!
Gavin

  parent reply	other threads:[~2019-03-22  2:04 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) [this message]
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=VI1PR08MB31673F3727C9CD1F402E3E448F430@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).