DPDK patches and discussions
 help / color / mirror / Atom feed
From: "Ananyev, Konstantin" <konstantin.ananyev@intel.com>
To: "Gavin Hu (Arm Technology China)" <Gavin.Hu@arm.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 09:47:01 +0000	[thread overview]
Message-ID: <2601191342CEEE43887BDE71AB977258013655DA5E@irsmsx105.ger.corp.intel.com> (raw)
Message-ID: <20190320094701.d9mvus8YReoteYltv10lwknAjZanxwrWbJzTPMx5LZw@z> (raw)
In-Reply-To: <VI1PR08MB3167D370CC1452864E3A8C7A8F410@VI1PR08MB3167.eurprd08.prod.outlook.com>

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

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).

> 
> 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


  parent reply	other threads:[~2019-03-20  9:47 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 [this message]
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=2601191342CEEE43887BDE71AB977258013655DA5E@irsmsx105.ger.corp.intel.com \
    --to=konstantin.ananyev@intel.com \
    --cc=Gavin.Hu@arm.com \
    --cc=Honnappa.Nagarahalli@arm.com \
    --cc=Joyce.Kong@arm.com \
    --cc=dev@dpdk.org \
    --cc=jerin.jacob@caviumnetworks.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).