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 850F1A00E6 for ; Wed, 20 Mar 2019 06:11:37 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 8BF4A2C60; Wed, 20 Mar 2019 06:11:36 +0100 (CET) Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60073.outbound.protection.outlook.com [40.107.6.73]) by dpdk.org (Postfix) with ESMTP id 78BAF5A for ; Wed, 20 Mar 2019 06:11:34 +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=iOgOM8JRtRXta0C0Hso40G5PfSBOAyqocLg3oKtiUn0=; b=mlNY5EtCSyXnlqYtbPQY6FBXP6CLpAWoz9bMOXDK89qVN7YVrL6MQaAS2y9187TAkzob9EOQ9vfK7dZmJ/kfoacTXMal98uFxlBR66fpuzdCr8CcbnFYy/njdbb0nwvhbgTJbFR1G12lizAUJNJSUer/5gC3L7Nx2DYCQkBEIxs= Received: from VI1PR08MB3167.eurprd08.prod.outlook.com (52.133.15.142) by VI1PR08MB2912.eurprd08.prod.outlook.com (10.170.239.156) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1709.14; Wed, 20 Mar 2019 05:11:33 +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.015; Wed, 20 Mar 2019 05:11:33 +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: AQHU2y50NjKDkgnLuEu5XYE96pz4baYSpe8QgAAc7ACAATYMQA== Date: Wed, 20 Mar 2019 05:11:32 +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> In-Reply-To: <2601191342CEEE43887BDE71AB977258013655D209@irsmsx105.ger.corp.intel.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [113.29.88.7] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 764e7a67-e7a6-4c88-9d1f-08d6acf284da x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(7168020)(4627221)(201703031133081)(201702281549075)(8990200)(5600127)(711020)(4605104)(4618075)(2017052603328)(7153060)(7193020); SRVR:VI1PR08MB2912; x-ms-traffictypediagnostic: VI1PR08MB2912: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Gavin.Hu@arm.com; x-ld-processed: f34e5979-57d9-4aaa-ad4d-b122a662184d,ExtAddr nodisclaimer: True x-microsoft-antispam-prvs: x-forefront-prvs: 098291215C x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(346002)(396003)(366004)(376002)(136003)(39860400002)(13464003)(189003)(199004)(52314003)(476003)(478600001)(53546011)(71190400001)(72206003)(11346002)(81156014)(66066001)(256004)(229853002)(71200400001)(4326008)(486006)(81166006)(446003)(14444005)(93886005)(3846002)(6116002)(53936002)(9686003)(8936002)(305945005)(33656002)(316002)(55016002)(14454004)(74316002)(2906002)(54906003)(6436002)(110136005)(68736007)(55236004)(7736002)(99286004)(2501003)(5660300002)(186003)(66574012)(6246003)(106356001)(105586002)(102836004)(6506007)(86362001)(26005)(97736004)(76176011)(25786009)(7696005)(52536014); DIR:OUT; SFP:1101; SCL:1; SRVR:VI1PR08MB2912; H:VI1PR08MB3167.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A: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: meH8J3UlNqVJz/BICLKjll4c4JWEfB1OQduUw8zkh6XZDPWCCdw8/NEdDN4iF/Ti9TZFViWqwT3w0gjGbhN/Cj05M64F9yFiFH6I/gfrX8hJ3+H6iCP9A+6Y/dQTewo9g5B78z+Xml8jbdrddW09OffTLeEK9LStwb0g6TRTcwdTwo/hABVv79EiOqPhMYlfeaErN1XnSerRrPHwIHUaKOILMOq6JK9EbiYhsFAykw6i3rgdwFcQBn1vx+RtaZFVg7m7y1YNdHzRC0Du2hQ2m86Zdu+FNr+YXTavuQs6F4xhCFfpfHO/s1gLfO/tXIL0t1kZyhdpiTj10IHEKt5GBcINHQkIN9RO0ZL6q5cmIB+gL5t74FNJHvdHztdA7UJD2YoCZI6NrfVMK7415+zeFi7I/Go/yEvphtyNUSyzYFQ= 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: 764e7a67-e7a6-4c88-9d1f-08d6acf284da X-MS-Exchange-CrossTenant-originalarrivaltime: 20 Mar 2019 05:11:32.9015 (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: VI1PR08MB2912 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: <20190320051132.mMIrSnjnzTgxzqo6_nmHXccnQ3oQnrFyQr3RCrsGWJY@z> Hi Konstantin, > -----Original Message----- > From: Ananyev, Konstantin > Sent: Tuesday, March 19, 2019 6:15 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 >=20 > Hi Gavin, >=20 > > > > > > > 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 wait= ing > > > > + * 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 > > > > +#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 experience r= eally long > > > context switch, > > > > By saying context switch, do you mean running to here, it is out of CPU= time > and starving for CPU? >=20 > Yes. >=20 > > > > > so next time it continues its execution tl->next value will wrap-up a= nd will > > > be 1 again, and tl->current=3D=3D0 (lock held). > > > I suppose this function will set tl->next=3D2 and will return a succe= ss? > > > > If this thread was swapped out and another thread took/attempted to tak= e > the lock, yes, tl->next =3D=3D 2 here, > > But as next =3D=3D 1 unchanged, so it would not return a success. >=20 > I am not talking about situation when tl->next =3D=3D 2,tl->current=3D=3D= 1 (just one > lock() was executed by different thread). > I am talking about situation when this thread was out of cpu for signific= ant > amount of cycles, > and in that period tl->next and tl->current were wrapped around (they bot= h > 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 >=20 Now I understood your points, but not sure if it is a rare or even impossib= le case for this thread stalls for CPU and during this time, the other thre= ads have taken the lock for 2^16 times, to wrap up.=20 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 updat= e the next(+1 and take the lock) only if both of them were not changed(or w= rapped 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 comp= are > 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 th= e 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) !=3D > > > > + __atomic_load_n(&tl->next, __ATOMIC_ACQUIRE)); > > > > +} > > > > +