From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR04-VI1-obe.outbound.protection.outlook.com (mail-eopbgr80054.outbound.protection.outlook.com [40.107.8.54]) by dpdk.org (Postfix) with ESMTP id 1B6535699 for ; Tue, 15 Jan 2019 00:36:48 +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=hetXL3Uo6wI5BUdWPq2ZBWdTjgwqRXvGIS+A0JpMgGY=; b=NcmK0vsdcoPYDBE9Q1xfdO1uLv5ewfv83mku7xzi/HZh5jMMvOWUl2504dUqVRzNfbdSxl0N5NU/RuA0u7Bkm3bykQb0ECrXBw7Mgrg4Rd/JYrXk7iqxqcKYnfwFyq38msaOyhOeDYtr9SXh2x+s1LoTvt2hFKZncYyr2XQzlzY= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.76) by AM6PR08MB3895.eurprd08.prod.outlook.com (20.178.91.20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1516.13; Mon, 14 Jan 2019 23:36:45 +0000 Received: from AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::25ec:2db7:d268:2b7b]) by AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::25ec:2db7:d268:2b7b%2]) with mapi id 15.20.1516.019; Mon, 14 Jan 2019 23:36:45 +0000 From: Honnappa Nagarahalli To: "Gavin Hu (Arm Technology China)" , "dev@dpdk.org" CC: "thomas@monjalon.net" , "jerinj@marvell.com" , "hemant.agrawal@nxp.com" , "stephen@networkplumber.org" , nd , "Gavin Hu (Arm Technology China)" , "Joyce Kong (Arm Technology China)" , nd Thread-Topic: [PATCH v1] ticketlock: ticket based to improve fairness Thread-Index: AQHUq07UrA7DfM4G1U2JsxmAjAxvOqWvFTFA Date: Mon, 14 Jan 2019 23:36:45 +0000 Message-ID: References: <20190113144631.23493-1-gavin.hu@arm.com> In-Reply-To: <20190113144631.23493-1-gavin.hu@arm.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=Honnappa.Nagarahalli@arm.com; x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3895; 6:TtBsITMd0DsjpHELg8HZnqMKXCqbllPXOorfL0HyQETVdWXeSG34FWm6gAqjSIxSiP6HnJSNhV7ivJbQCWbpMR85igsNco5P9PLxUmLiXfEMgUoexI+wzgXWuHbQIxBPJRGX+QnGYm09h/meyaaWm7JWT1+29ITYholOE0IGWgGcIGz/KIPIjGuY6m/LEntMbioyXMNdLT4Ze3WVeGuqr/6UcfrfGn9Vmht1j9P1s99TRsINmGyyaK3BN6uK8f5WT6tMxjVbTjYsummu9iXrNoJEtVWOPccJNs6WLIMrRJ/BXWO60O8htdfH0C4MkehVg7L6cBElCKa6Obh7KosUHP/p/3sFWVNRFZZyOk/q0RPLpoechaqIQgm2uFONToLUMkthWCa2PWkHlPhWTbQ6Rqgmqhec8uPwfWGwbTbwY+WwSMQVm70KKpGCmXGObhSa+oo6HrQIIfwKFTiW7g3pgA==; 5:/hMfscx4kyH/ftCiTNzkgo5jtHddd1SR8QagodiQEE5nPULxC0mKDUaT6NZp3Ax8WnORrBrEibBYaMktsCFrP5EyilgkGLomX5nXyIqDEeTyjYU2pEic2fkVfESU88sqohl1EztdElJrDzJy+PvLO69hyfRpZ5YQAyufWRiBXpIrKqHhL8D9M3cEaRKw1BNn3hhcVfwE+7SgRmcVGwCg0A==; 7:Y3NNmGo6NnmROLegN4evWrxNqHHlBagt5aV7MSP8IVPnOi0X2U0kenBh/6i1XSSn7UzBomGMx3VsxA5QTIIgiHFBmCFoeTDniniDWr1w5RaqTBQySSsiWY7v2N/3RwOsgEdN955WK6whg9YrpgoLqg== x-ms-exchange-antispam-srfa-diagnostics: SOS; x-ms-office365-filtering-correlation-id: 877188f2-7f72-4282-043b-08d67a79253e x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600109)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM6PR08MB3895; x-ms-traffictypediagnostic: AM6PR08MB3895: x-ld-processed: f34e5979-57d9-4aaa-ad4d-b122a662184d,ExtAddr nodisclaimer: True x-microsoft-antispam-prvs: x-forefront-prvs: 0917DFAC67 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(396003)(376002)(346002)(366004)(136003)(39860400002)(199004)(189003)(8936002)(6246003)(5660300001)(53936002)(71190400001)(2501003)(7696005)(76176011)(3846002)(110136005)(54906003)(316002)(6116002)(486006)(81156014)(99286004)(9686003)(81166006)(8676002)(25786009)(105586002)(4326008)(106356001)(68736007)(26005)(97736004)(7736002)(66066001)(14444005)(14454004)(2906002)(33656002)(229853002)(256004)(6436002)(72206003)(478600001)(6506007)(71200400001)(86362001)(305945005)(476003)(102836004)(446003)(55016002)(11346002)(186003)(74316002); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3895; H:AM6PR08MB3672.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: nhYedURfx8z2i7wAgOv6shpovXaOvnRoNKhr9/qBSLpU6blnfolCp4hY3Qn1fipE5niw167nXApzaCYaE3JYIvhpppQLLW1zBzD+4WnHSUBOmF9tgNCE+4MRW0mwUqfFMpXTQhgCs/feGD9vbk9ZQek+46FIPedgor3/31UhvgZHQSi6pWTysJHq+2sfJYwLx9WH+plcR/VIXpCWqrz5MMa3fpdKu9auYJPrGR1UEzqcT3rQbJY/ybo2jrhJyFvGRkk+rnrPokED9WyJ2B1Wis2QXQn040LBSfEzC6+m+4zIoq2ovIs7EgGnKx3HaAJ0XOYbOkk4Y900wVa8wZto6zPJh6zOfKEkdcDwBbfjyjvFVNs2cTBV80jLvcDER+bmRJuny1xGuiQuGsM8FaEegyyD0wbzOcl0PW4hgoy/lzw= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: 877188f2-7f72-4282-043b-08d67a79253e X-MS-Exchange-CrossTenant-originalarrivaltime: 14 Jan 2019 23:36:45.2785 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3895 Subject: Re: [dpdk-dev] [PATCH v1] 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: Mon, 14 Jan 2019 23:36:48 -0000 > Subject: [PATCH v1] ticketlock: ticket based to improve fairness >=20 > From: Joyce Kong >=20 > The spinlock implementation is unfair, some threads may take locks > aggressively while leaving the other threads starving for long time. As s= hown > in the following test, within same period of time, there are threads taki= ng > locks much more times than the others. >=20 > The ticketlock gives each waiting thread a ticket and they can take the l= ock > one by one, first come, first serviced, this avoids starvation for too lo= ng time > and is more predictable. >=20 > *** spinlock_autotest without this patch *** Core [0] count =3D 89 Core [= 1] > count =3D 84 Core [2] count =3D 94 ... > Core [208] count =3D 171 > Core [209] count =3D 152 > Core [210] count =3D 161 > Core [211] count =3D 187 >=20 > *** spinlock_autotest with this patch *** Core [0] count =3D 534 Core [1]= count > =3D 533 Core [2] count =3D 542 ... > Core [208] count =3D 554 > Core [209] count =3D 556 > Core [210] count =3D 555 > Core [211] count =3D 551 >=20 > Signed-off-by: Joyce Kong > Signed-off-by: Gavin Hu > --- > .../common/include/generic/rte_ticketlock.h | 203 > +++++++++++++++++++++ > lib/librte_eal/rte_eal_version.map | 8 + > 2 files changed, 211 insertions(+) > create mode 100644 lib/librte_eal/common/include/generic/rte_ticketlock.= h >=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 000000000..9d044bb31 > --- /dev/null > +++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h > @@ -0,0 +1,203 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2018-2019 Arm Corporation */ ^^^^^^^^^^ Should be 'Limited' > + > +#ifndef _RTE_TICKETLOCK_H_ > +#define _RTE_TICKETLOCK_H_ > + > +/** > + * @file > + * > + * RTE ticketlocks > + * > + * This file defines an API for read-write locks, which are implemented > + * in an architecture-specific way. This kind of lock simply waits in > + * a loop repeatedly checking until the lock becomes available. Needs update for ticket lock > + * > + * All locks must be initialised before use, and only initialised once. > + * > + */ > + > +#include > +#include > +#include > + > +/** > + * The rte_ticketlock_t type. > + */ > +typedef struct { > + uint16_t current; > + uint16_t next; Any reason these are 16b? Use 'volatile' for consistency with rte_spinlock_t? (though I do not prefer= to use 'volatile' in general) > +} 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); > + > +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(); > +} Do we need to place the APIs under RTE_FORCE_INTRINSICS flag? I see that x8= 6 has implementation which does not use intrinsics (lib/librte_eal/common/i= nclude/arch/x86/rte_spinlock.h). > + > +/** > + * Release the ticketlock. > + * > + * @param tl > + * A pointer to the ticketlock. > + */ > +static inline __rte_experimental void > +rte_ticketlock_unlock(rte_ticketlock_t *tl); > + > +static inline __rte_experimental void > +rte_ticketlock_unlock(rte_ticketlock_t *tl) { > + uint16_t i =3D __atomic_load_n(&tl->current, __ATOMIC_RELAXED); > + i++; > + __atomic_store_n(&tl->current, i, __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 me =3D __atomic_fetch_add(&tl->next, 1, __ATOMIC_RELAXED); > + while (__atomic_load_n(&tl->current, __ATOMIC_RELAXED) !=3D me) { What happens if other threads incremented 'tl->next' here? > + __atomic_sub_fetch(&tl->next, 1, __ATOMIC_RELAXED); > + return 0; > + } > + > + return 1; > +} IMO, this implementation needs to be changed. We should try to take the loc= k if tl->next and tl->current are equal. Then tl->next should be incremente= d using a CAS (which makes sure no one else has taken the lock in the meanw= hile) > + > +/** > + * 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_RELAXED) !=3D Load of tl->current should be __ATOMIC_ACQUIRE > + __atomic_load_n(&tl->next, __ATOMIC_RELAXED)); } > + > +/** > + * The rte_ticketlock_recursive_t type. > + */ > +typedef struct { > + rte_ticketlock_t tl; /**< the actual ticketlock */ > + volatile int user; /**< core id using lock, -1 for unused */ > + volatile int count; /**< count of time this lock has been called */ } 'count' can be 'unsigned int'? > +rte_ticketlock_recursive_t; > + > +/** > + * A static recursive ticketlock initializer. > + */ > +#define RTE_TICKETLOCK_RECURSIVE_INITIALIZER > +{RTE_TICKETLOCK_INITIALIZER, -1, 0} > + > +/** > + * Initialize the recursive ticketlock to an unlocked state. > + * > + * @param tlr > + * A pointer to the recursive ticketlock. > + */ > +static inline __rte_experimental void rte_ticketlock_recursive_init( > + rte_ticketlock_recursive_t *tlr) > +{ > + rte_ticketlock_init(&tlr->tl); > + tlr->user =3D -1; > + tlr->count =3D 0; > +} > + > +/** > + * Take the recursive ticketlock. > + * > + * @param tlr > + * A pointer to the recursive ticketlock. > + */ > +static inline __rte_experimental void rte_ticketlock_recursive_lock( > + rte_ticketlock_recursive_t *tlr) > +{ > + int id =3D rte_gettid(); > + > + if (tlr->user !=3D id) { > + rte_ticketlock_lock(&tlr->tl); > + tlr->user =3D id; > + } > + tlr->count++; > +} > +/** > + * Release the recursive ticketlock. > + * > + * @param tlr > + * A pointer to the recursive ticketlock. > + */ > +static inline __rte_experimental void rte_ticketlock_recursive_unlock( > + rte_ticketlock_recursive_t *tlr) > +{ > + if (--(tlr->count) =3D=3D 0) { > + tlr->user =3D -1; > + rte_ticketlock_unlock(&tlr->tl); > + } > + Minor comment. Extra line. > +} > + > +/** > + * Try to take the recursive lock. > + * > + * @param tlr > + * A pointer to the recursive ticketlock. > + * @return > + * 1 if the lock is successfully taken; 0 otherwise. > + */ > +static inline __rte_experimental int rte_ticketlock_recursive_trylock( > + rte_ticketlock_recursive_t *tlr) > +{ > + int id =3D rte_gettid(); > + > + if (tlr->user !=3D id) { > + if (rte_ticketlock_trylock(&tlr->tl) =3D=3D 0) > + return 0; > + tlr->user =3D id; > + } > + tlr->count++; > + return 1; > +} > + > +#endif /* _RTE_TICKETLOCK_H_ */ > diff --git a/lib/librte_eal/rte_eal_version.map > b/lib/librte_eal/rte_eal_version.map > index eb5f7b9cb..f1841effa 100644 > --- a/lib/librte_eal/rte_eal_version.map > +++ b/lib/librte_eal/rte_eal_version.map > @@ -364,4 +364,12 @@ EXPERIMENTAL { > rte_service_may_be_active; > rte_socket_count; > rte_socket_id_by_idx; > + rte_ticketlock_lock; > + rte_ticketlock_unlock; > + rte_ticketlock_islocked; > + rte_ticketlock_trylock; > + rte_ticketlock_recurrsive_lock; > + rte_ticketlock_recurrsive_unlock; > + rte_ticketlock_recurrsive_islocked; > + rte_ticketlock_recurrsive_trylock; These are all 'inline' functions, they do not need to be versioned. > }; > -- > 2.11.0