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 9EDB9A00E6 for ; Tue, 19 Mar 2019 10:44:32 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 6BC4B4CA7; Tue, 19 Mar 2019 10:44:32 +0100 (CET) Received: from EUR04-HE1-obe.outbound.protection.outlook.com (mail-eopbgr70085.outbound.protection.outlook.com [40.107.7.85]) by dpdk.org (Postfix) with ESMTP id D81EF4CA0 for ; Tue, 19 Mar 2019 10:44:30 +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=mukxGPdo/rvQfdLxbgbX6sWG7gUbkcX5VfXz62s4FOg=; b=MzUF0EJqWYnhtRxpg4dPTctBn+P5vMxrILU41a6R5cWeR4u4VS/8+YuHDRHd5G3ihTQWbPbqkTK7sAmC8zX2lL/F1eYM8pinAjM4cEZDWbX9IKbuwFnX4usPhXGCMDEg1Hm9ASDQP0ydzFzM+r+mxoOKZpJKj34woiVTsWlgXVs= Received: from VI1PR08MB3167.eurprd08.prod.outlook.com (52.133.15.142) by VI1PR08MB3424.eurprd08.prod.outlook.com (20.177.59.14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1709.13; Tue, 19 Mar 2019 09:44:29 +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; Tue, 19 Mar 2019 09:44:29 +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)" , "Gavin Hu (Arm Technology China)" Thread-Topic: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve fairness Thread-Index: AQHU2y50NjKDkgnLuEu5XYE96pz4baYSpe8Q Date: Tue, 19 Mar 2019 09:44:29 +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> In-Reply-To: <2601191342CEEE43887BDE71AB977258013655BF89@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: af0f6f3e-35d3-47f9-6fcc-08d6ac4f7b83 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:VI1PR08MB3424; x-ms-traffictypediagnostic: VI1PR08MB3424: x-ld-processed: f34e5979-57d9-4aaa-ad4d-b122a662184d,ExtAddr nodisclaimer: True x-microsoft-antispam-prvs: x-forefront-prvs: 0981815F2F x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(376002)(39860400002)(366004)(136003)(346002)(396003)(199004)(189003)(13464003)(52314003)(105586002)(7696005)(71190400001)(55236004)(66574012)(71200400001)(106356001)(186003)(3846002)(7736002)(102836004)(76176011)(6506007)(53546011)(305945005)(25786009)(99286004)(14454004)(74316002)(4326008)(6116002)(229853002)(86362001)(486006)(52536014)(478600001)(5660300002)(9686003)(54906003)(316002)(6436002)(6246003)(53936002)(33656002)(110136005)(81156014)(66066001)(81166006)(446003)(72206003)(55016002)(97736004)(11346002)(26005)(68736007)(2501003)(8936002)(14444005)(2906002)(256004)(476003); DIR:OUT; SFP:1101; SCL:1; SRVR:VI1PR08MB3424; 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: 1PJQsTDCu7H9s/JQJGTvJgUz0NzTuHDzF5bth3mNkr0hv2bcc1HSRmuCgLtjulujb9XUt/UDBTYhPH2ABRKRk+rrdOhDzSz7cCA3f6MNzJaEgVXPlLSODENpfe527EEr0xFkuGH0Q+PRyvpt0aUxWv5qGp2g4dJ2eyLIZz5Mu0SmQGi8mVhPIr5z6KwN+t1D8xr5RHzoZr9vbCt7/9Y4Qb6ZXwi7rZtqJMZRBHJHQFqbEK7aWdrfB6gsAi14f9LudZhed6CrPNUb0X5s9ImaBKE9XbFax3mKSqP6tpI4t9Frww16U7wg8+Xt1bZ+1h1IPkCB8Ey0iD7YeMfT69VWrFIpx+iO/C2rdThqPDEqCpZIdLlJ9h8ULy/61l0N3e2k02gTo6oTleyrx/5cWW84VBO5eSPKqcHXV0BAmMkMpqU= 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: af0f6f3e-35d3-47f9-6fcc-08d6ac4f7b83 X-MS-Exchange-CrossTenant-originalarrivaltime: 19 Mar 2019 09:44:29.2277 (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: VI1PR08MB3424 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: <20190319094429.2THnCZ60TPNtcYGaTcTtSZ7GzPAkRwWd6KSIpgO5tN0@z> Hi Konstantin,=20 > -----Original Message----- > From: Ananyev, Konstantin > Sent: Friday, March 15, 2019 8:56 PM > To: Joyce Kong (Arm Technology China) ; > dev@dpdk.org > Cc: nd ; stephen@networkplumber.org; > jerin.jacob@caviumnetworks.com; thomas@monjalon.net; Honnappa > Nagarahalli ; Gavin Hu (Arm > Technology China) > Subject: RE: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to > improve fairness >=20 > Hi, >=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 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 > > +#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) { >=20 > Probably a na=EFve one: > Suppose next=3D=3Dcur=3D=3D1 here, then this thread will experience reall= y long > context switch, By saying context switch, do you mean running to here, it is out of CPU tim= e and starving for CPU?=20 > so next time it continues its execution tl->next value will wrap-up and w= ill > be 1 again, and tl->current=3D=3D0 (lock held). > I suppose this function will set tl->next=3D2 and will return a success? If this thread was swapped out and another thread took/attempted to take th= e lock, yes, tl->next =3D=3D 2 here, But as next =3D=3D 1 unchanged, so it would not return a success.=20 > 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 compare = them.=20 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-state= ments 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.=20 The current code works ok except it may fail spuriously(in case during cont= ext switch, the lock was taken and released by other threads, moving tl->ne= xt forward, in this case The lock is available but not obtained by this trylock). Anyway, as the na= me 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.=20 Any more comments are welcome! >=20 > > + 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)); > > +} > > +