From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <dev-bounces@dpdk.org>
Received: from dpdk.org (dpdk.org [92.243.14.124])
by dpdk.space (Postfix) with ESMTP id ED8F5A00E6
for <public@inbox.dpdk.org>; Wed, 20 Mar 2019 10:47:10 +0100 (CET)
Received: from [92.243.14.124] (localhost [127.0.0.1])
by dpdk.org (Postfix) with ESMTP id 061E34C94;
Wed, 20 Mar 2019 10:47:10 +0100 (CET)
Received: from mga18.intel.com (mga18.intel.com [134.134.136.126])
by dpdk.org (Postfix) with ESMTP id BBE674C91
for <dev@dpdk.org>; Wed, 20 Mar 2019 10:47:07 +0100 (CET)
X-Amp-Result: SKIPPED(no attachment in message)
X-Amp-File-Uploaded: False
Received: from orsmga008.jf.intel.com ([10.7.209.65])
by orsmga106.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;
20 Mar 2019 02:47:06 -0700
X-ExtLoop1: 1
X-IronPort-AV: E=Sophos;i="5.60,248,1549958400"; d="scan'208";a="126997229"
Received: from irsmsx105.ger.corp.intel.com ([163.33.3.28])
by orsmga008.jf.intel.com with ESMTP; 20 Mar 2019 02:47:03 -0700
Received: from irsmsx156.ger.corp.intel.com (10.108.20.68) by
irsmsx105.ger.corp.intel.com (163.33.3.28) with Microsoft SMTP Server (TLS)
id 14.3.408.0; Wed, 20 Mar 2019 09:47:03 +0000
Received: from irsmsx105.ger.corp.intel.com ([169.254.7.210]) by
IRSMSX156.ger.corp.intel.com ([169.254.3.101]) with mapi id 14.03.0415.000;
Wed, 20 Mar 2019 09:47:02 +0000
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>
Thread-Topic: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to
improve fairness
Thread-Index: AQHU2vxlKpABH57hOkqA57tQE05+36YMpFOAgAYWZYCAAARN4IABQcUAgAAyNpA=
Date: Wed, 20 Mar 2019 09:47:01 +0000
Message-ID:
<2601191342CEEE43887BDE71AB977258013655DA5E@irsmsx105.ger.corp.intel.com>
References: <1547802943-18711-1-git-send-email-joyce.kong@arm.com>
<1552632988-80787-2-git-send-email-joyce.kong@arm.com>
<2601191342CEEE43887BDE71AB977258013655BF89@irsmsx105.ger.corp.intel.com>
<VI1PR08MB3167D105DA31E3643587F6698F400@VI1PR08MB3167.eurprd08.prod.outlook.com>
<2601191342CEEE43887BDE71AB977258013655D209@irsmsx105.ger.corp.intel.com>
<VI1PR08MB3167D370CC1452864E3A8C7A8F410@VI1PR08MB3167.eurprd08.prod.outlook.com>
In-Reply-To: <VI1PR08MB3167D370CC1452864E3A8C7A8F410@VI1PR08MB3167.eurprd08.prod.outlook.com>
Accept-Language: en-IE, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiMWIyOTExZmItNmU1Yi00MWMyLTk0MWUtODQzMmMxYjkyYTRjIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiNDYyQ2YzeVNXZ3paUG5vR2NLWEhyZmREaFJXVW1tc1FjS01pZTVISTh4U2NlM3Y3Qm1mVVYyTWVxNk5YTmZuMCJ9
x-ctpclassification: CTP_NT
dlp-product: dlpe-windows
dlp-version: 11.0.400.15
dlp-reaction: no-action
x-originating-ip: [163.33.239.181]
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: Re: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to
improve fairness
X-BeenThere: dev@dpdk.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <https://mails.dpdk.org/options/dev>,
<mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://mails.dpdk.org/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <https://mails.dpdk.org/listinfo/dev>,
<mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.org>
Message-ID: <20190320094701.d9mvus8YReoteYltv10lwknAjZanxwrWbJzTPMx5LZw@z>
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 wa=
iting
> > > > > + * thread a ticket and take the lock one by one, first come, fir=
st
> > > > > + * serviced.
> > > > > + *
> > > > > + * All locks must be initialised before use, and only initialise=
d 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 =3D __atomic_fetch_add(&tl->next, 1,
> > > > __ATOMIC_RELAXED);
> > > > > + while (__atomic_load_n(&tl->current, __ATOMIC_ACQUIRE) !=3D 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 =3D __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 =3D __atomic_load_n(&tl->next, __ATOMIC_RELAXED);
> > > > > + uint16_t cur =3D __atomic_load_n(&tl->current, __ATOMIC_RELAXED=
);
> > > > > + if (next =3D=3D cur) {
> > > >
> > > > Probably a na=EFve one:
> > > > Suppose next=3D=3Dcur=3D=3D1 here, then this thread will experience=
really long
> > > > context switch,
> > >
> > > By saying context switch, do you mean running to here, it is out of C=
PU 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=3D=3D0 (lock held).
> > > > I suppose this function will set tl->next=3D2 and will return a suc=
cess?
> > >
> > > If this thread was swapped out and another thread took/attempted to t=
ake
> > the lock, yes, tl->next =3D=3D 2 here,
> > > But as next =3D=3D 1 unchanged, so it would not return a success.
> >
> > I am not talking about situation when tl->next =3D=3D 2,tl->current=3D=
=3D1 (just one
> > lock() was executed by different thread).
> > I am talking about situation when this thread was out of cpu for signif=
icant
> > amount of cycles,
> > and in that period tl->next and tl->current were wrapped around (they b=
oth
> > reached UINT16_MAX, then 0).
> > i.e. UINT16_MAX lock/unlock were executed while this thread was away fr=
om
> > cpu.
> > After that another thread just did successful lock(), so tl->next=3D=3D=
1 and tl-
> > >current=3D=3D0.
> > Now this thread wakeups and continues with:
> > __atomic_compare_exchange_n(&tl->next, &next, next+1, ...)
> > As both tl->next=3D=3D1 and next=3D=3D1, 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 imposs=
ible 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 cycl=
es.
Then it would wrap around in ~6.5M cycles (~3ms on modern cpus).
>=20
> Anyway I made a patch, currently in internal review to fix this issue, th=
e 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 chang=
ed(or wrapped up and the lock released).
> I will submit the patch after internal review approved. Please let me kno=
w if you have more comments.
Ok, thanks
Konstantin