From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR02-HE1-obe.outbound.protection.outlook.com (mail-eopbgr10043.outbound.protection.outlook.com [40.107.1.43]) by dpdk.org (Postfix) with ESMTP id EBDB21B552 for ; Fri, 22 Mar 2019 03:04:46 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=x7CRm9k5l6JpfF7Lq1l4IkHNRFFQzRvNryqlm3w+hvM=; b=XBzZGd34SUC7UrtwHkBHKxNeqXnG1BryvpaNIHsHo2exENgBzhu4Ug0jmY2nXvpXRx6GAPDTeuxIZynE5pydp37WbEC5fe39HCaiqlUc/zLEezsDN33MzlbTH96hYpMaj69KTRppe0+fBDF9nOqlvlhMrqA9ui7YVNbJ6k9KjhA= Received: from VI1PR08MB3167.eurprd08.prod.outlook.com (52.133.15.142) by VI1PR08MB4398.eurprd08.prod.outlook.com (20.179.28.140) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1709.15; Fri, 22 Mar 2019 02:04:45 +0000 Received: from VI1PR08MB3167.eurprd08.prod.outlook.com ([fe80::707a:b455:dcb2:9d40]) by VI1PR08MB3167.eurprd08.prod.outlook.com ([fe80::707a:b455:dcb2:9d40%2]) with mapi id 15.20.1709.017; Fri, 22 Mar 2019 02:04:45 +0000 From: "Gavin Hu (Arm Technology China)" To: "Ananyev, Konstantin" , "dev@dpdk.org" CC: nd , "stephen@networkplumber.org" , "jerin.jacob@caviumnetworks.com" , "thomas@monjalon.net" , Honnappa Nagarahalli , "Joyce Kong (Arm Technology China)" Thread-Topic: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve fairness Thread-Index: AQHU2y50NjKDkgnLuEu5XYE96pz4baYSpe8QgAAc7ACAATYMQIAAVHeAgAKhkfA= Date: Fri, 22 Mar 2019 02:04:44 +0000 Message-ID: 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> <2601191342CEEE43887BDE71AB977258013655D209@irsmsx105.ger.corp.intel.com> <2601191342CEEE43887BDE71AB977258013655DA5E@irsmsx105.ger.corp.intel.com> In-Reply-To: <2601191342CEEE43887BDE71AB977258013655DA5E@irsmsx105.ger.corp.intel.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Gavin.Hu@arm.com; x-originating-ip: [113.29.88.7] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: a38a21a3-40bd-498a-5816-08d6ae6ac147 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(5600127)(711020)(4605104)(4618075)(4534185)(7168020)(4627221)(201703031133081)(201702281549075)(8990200)(2017052603328)(7153060)(7193020); SRVR:VI1PR08MB4398; x-ms-traffictypediagnostic: VI1PR08MB4398: x-ld-processed: f34e5979-57d9-4aaa-ad4d-b122a662184d,ExtAddr nodisclaimer: True x-microsoft-antispam-prvs: x-forefront-prvs: 09840A4839 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(39860400002)(396003)(376002)(366004)(136003)(346002)(13464003)(199004)(189003)(478600001)(4326008)(3846002)(316002)(97736004)(9686003)(81156014)(66066001)(229853002)(14444005)(52536014)(81166006)(99286004)(54906003)(55016002)(476003)(6436002)(25786009)(486006)(72206003)(11346002)(71200400001)(71190400001)(446003)(110136005)(33656002)(93886005)(186003)(68736007)(7736002)(53546011)(305945005)(2501003)(2906002)(76176011)(86362001)(6116002)(6246003)(6506007)(55236004)(105586002)(26005)(256004)(102836004)(53936002)(14454004)(5660300002)(7696005)(74316002)(66574012)(106356001)(8936002); DIR:OUT; SFP:1101; SCL:1; SRVR:VI1PR08MB4398; H:VI1PR08MB3167.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-microsoft-antispam-message-info: ovJlwlWRmDTE8lgBj7MckU5I5gnZTQ/LQz9krY8+H2RSukNr9BV9Cfsx958KhOJzKbpTSJprFCVfmlb3cs9fQQW/cN+FFeqfn6jLNtRg/mqpf2aWtaWyhciY8ZlZriVU4w20MDOL/bLsHpZfUzrm7f4CywcS+m1coLgqtdi4kagZKhT2Or6Irl7DF5201/sigAxcl94ERUrz26Mi9dKEXO5L82C8HC6QsN+EB5tcoiTBmKPYXXqf5/ZYJhlyTsGxZtCzvapPznzZpthHZfUtdR5nd0Ckz8YxhULyg1v5Kkjzr3JSFiLV/NbMjPh/5/K9kFVM3nPZXC2I7cWFZtoJtbegkWIyuG/PYmOXwEzrnv01C+SvqwOpfiweNRM4TEcELsWcVIcyMHLaOhZ3MMk3NRAxVFc1VzrLUJpImQ/CruQ= Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: a38a21a3-40bd-498a-5816-08d6ae6ac147 X-MS-Exchange-CrossTenant-originalarrivaltime: 22 Mar 2019 02:04:45.0277 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR08MB4398 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 22 Mar 2019 02:04:47 -0000 Hi Konstantin,=20 > -----Original Message----- > From: Ananyev, Konstantin > Sent: Wednesday, March 20, 2019 5:47 PM > To: Gavin Hu (Arm Technology China) ; dev@dpdk.org > Cc: nd ; stephen@networkplumber.org; > jerin.jacob@caviumnetworks.com; thomas@monjalon.net; Honnappa > Nagarahalli ; Joyce Kong (Arm Technology > China) > Subject: RE: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to im= prove > fairness >=20 > Hi Gavin, > > > > > > > > > > > diff --git a/lib/librte_eal/common/include/generic/rte_ticketlo= ck.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, f= irst > > > > > > + * serviced. > > > > > > + * > > > > > > + * All locks must be initialised before use, and only initiali= sed once. > > > > > > + * > > > > > > + */ > > > > > > + > > > > > > +#ifdef __cplusplus > > > > > > +extern "C" { > > > > > > +#endif > > > > > > + > > > > > > +#include > > > > > > +#include > > > > > > +#include > > > > > > + > > > > > > +/** > > > > > > + * 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 experien= ce 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=3D=3D0 (lock held). > > > > > I suppose this function will set tl->next=3D2 and will return a s= uccess? > > > > > > > > If this thread was swapped out and another thread took/attempted to > take > > > 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 sign= ificant > > > 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=3D= =3D1 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 impo= ssible > 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. >=20 > 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 cy= cles. > Then it would wrap around in ~6.5M cycles (~3ms on modern cpus). >=20 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 k= now if > you have more comments. >=20 > Ok, thanks > Konstantin The fix was submitted into v7, 1/3, could you help review?=20 Thanks! Gavin From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by dpdk.space (Postfix) with ESMTP id 8FF07A00E6 for ; Fri, 22 Mar 2019 03:04:49 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 9D88A1B554; Fri, 22 Mar 2019 03:04:48 +0100 (CET) Received: from EUR02-HE1-obe.outbound.protection.outlook.com (mail-eopbgr10043.outbound.protection.outlook.com [40.107.1.43]) by dpdk.org (Postfix) with ESMTP id EBDB21B552 for ; Fri, 22 Mar 2019 03:04:46 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=x7CRm9k5l6JpfF7Lq1l4IkHNRFFQzRvNryqlm3w+hvM=; b=XBzZGd34SUC7UrtwHkBHKxNeqXnG1BryvpaNIHsHo2exENgBzhu4Ug0jmY2nXvpXRx6GAPDTeuxIZynE5pydp37WbEC5fe39HCaiqlUc/zLEezsDN33MzlbTH96hYpMaj69KTRppe0+fBDF9nOqlvlhMrqA9ui7YVNbJ6k9KjhA= Received: from VI1PR08MB3167.eurprd08.prod.outlook.com (52.133.15.142) by VI1PR08MB4398.eurprd08.prod.outlook.com (20.179.28.140) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1709.15; Fri, 22 Mar 2019 02:04:45 +0000 Received: from VI1PR08MB3167.eurprd08.prod.outlook.com ([fe80::707a:b455:dcb2:9d40]) by VI1PR08MB3167.eurprd08.prod.outlook.com ([fe80::707a:b455:dcb2:9d40%2]) with mapi id 15.20.1709.017; Fri, 22 Mar 2019 02:04:45 +0000 From: "Gavin Hu (Arm Technology China)" To: "Ananyev, Konstantin" , "dev@dpdk.org" CC: nd , "stephen@networkplumber.org" , "jerin.jacob@caviumnetworks.com" , "thomas@monjalon.net" , Honnappa Nagarahalli , "Joyce Kong (Arm Technology China)" Thread-Topic: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve fairness Thread-Index: AQHU2y50NjKDkgnLuEu5XYE96pz4baYSpe8QgAAc7ACAATYMQIAAVHeAgAKhkfA= Date: Fri, 22 Mar 2019 02:04:44 +0000 Message-ID: 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> <2601191342CEEE43887BDE71AB977258013655D209@irsmsx105.ger.corp.intel.com> <2601191342CEEE43887BDE71AB977258013655DA5E@irsmsx105.ger.corp.intel.com> In-Reply-To: <2601191342CEEE43887BDE71AB977258013655DA5E@irsmsx105.ger.corp.intel.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Gavin.Hu@arm.com; x-originating-ip: [113.29.88.7] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: a38a21a3-40bd-498a-5816-08d6ae6ac147 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(5600127)(711020)(4605104)(4618075)(4534185)(7168020)(4627221)(201703031133081)(201702281549075)(8990200)(2017052603328)(7153060)(7193020); SRVR:VI1PR08MB4398; x-ms-traffictypediagnostic: VI1PR08MB4398: x-ld-processed: f34e5979-57d9-4aaa-ad4d-b122a662184d,ExtAddr nodisclaimer: True x-microsoft-antispam-prvs: x-forefront-prvs: 09840A4839 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(39860400002)(396003)(376002)(366004)(136003)(346002)(13464003)(199004)(189003)(478600001)(4326008)(3846002)(316002)(97736004)(9686003)(81156014)(66066001)(229853002)(14444005)(52536014)(81166006)(99286004)(54906003)(55016002)(476003)(6436002)(25786009)(486006)(72206003)(11346002)(71200400001)(71190400001)(446003)(110136005)(33656002)(93886005)(186003)(68736007)(7736002)(53546011)(305945005)(2501003)(2906002)(76176011)(86362001)(6116002)(6246003)(6506007)(55236004)(105586002)(26005)(256004)(102836004)(53936002)(14454004)(5660300002)(7696005)(74316002)(66574012)(106356001)(8936002); DIR:OUT; SFP:1101; SCL:1; SRVR:VI1PR08MB4398; H:VI1PR08MB3167.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-microsoft-antispam-message-info: ovJlwlWRmDTE8lgBj7MckU5I5gnZTQ/LQz9krY8+H2RSukNr9BV9Cfsx958KhOJzKbpTSJprFCVfmlb3cs9fQQW/cN+FFeqfn6jLNtRg/mqpf2aWtaWyhciY8ZlZriVU4w20MDOL/bLsHpZfUzrm7f4CywcS+m1coLgqtdi4kagZKhT2Or6Irl7DF5201/sigAxcl94ERUrz26Mi9dKEXO5L82C8HC6QsN+EB5tcoiTBmKPYXXqf5/ZYJhlyTsGxZtCzvapPznzZpthHZfUtdR5nd0Ckz8YxhULyg1v5Kkjzr3JSFiLV/NbMjPh/5/K9kFVM3nPZXC2I7cWFZtoJtbegkWIyuG/PYmOXwEzrnv01C+SvqwOpfiweNRM4TEcELsWcVIcyMHLaOhZ3MMk3NRAxVFc1VzrLUJpImQ/CruQ= Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: a38a21a3-40bd-498a-5816-08d6ae6ac147 X-MS-Exchange-CrossTenant-originalarrivaltime: 22 Mar 2019 02:04:45.0277 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR08MB4398 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Message-ID: <20190322020444.LgyVwmR119ovBOOIQq-QFOYB1Vp6mLz8tJqIU4SLvPk@z> Hi Konstantin,=20 > -----Original Message----- > From: Ananyev, Konstantin > Sent: Wednesday, March 20, 2019 5:47 PM > To: Gavin Hu (Arm Technology China) ; dev@dpdk.org > Cc: nd ; stephen@networkplumber.org; > jerin.jacob@caviumnetworks.com; thomas@monjalon.net; Honnappa > Nagarahalli ; Joyce Kong (Arm Technology > China) > Subject: RE: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to im= prove > fairness >=20 > Hi Gavin, > > > > > > > > > > > diff --git a/lib/librte_eal/common/include/generic/rte_ticketlo= ck.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, f= irst > > > > > > + * serviced. > > > > > > + * > > > > > > + * All locks must be initialised before use, and only initiali= sed once. > > > > > > + * > > > > > > + */ > > > > > > + > > > > > > +#ifdef __cplusplus > > > > > > +extern "C" { > > > > > > +#endif > > > > > > + > > > > > > +#include > > > > > > +#include > > > > > > +#include > > > > > > + > > > > > > +/** > > > > > > + * 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 experien= ce 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=3D=3D0 (lock held). > > > > > I suppose this function will set tl->next=3D2 and will return a s= uccess? > > > > > > > > If this thread was swapped out and another thread took/attempted to > take > > > 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 sign= ificant > > > 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=3D= =3D1 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 impo= ssible > 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. >=20 > 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 cy= cles. > Then it would wrap around in ~6.5M cycles (~3ms on modern cpus). >=20 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 k= now if > you have more comments. >=20 > Ok, thanks > Konstantin The fix was submitted into v7, 1/3, could you help review?=20 Thanks! Gavin