From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60079.outbound.protection.outlook.com [40.107.6.79]) by dpdk.org (Postfix) with ESMTP id 062CF2BA3 for ; Tue, 15 Jan 2019 21:43: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=5iuoW/5IgXgqZN0z2W0cr7fKTJvd9zmANetkflwRNZM=; b=js8HMP/MEUTn5ywWUTGlUH1IvI+bFP7LgXvxr60TenzNzCMOztu9TCIwtfbfpcVehgZupR7Q6dAw2p9YquJ2KLRDZuedh5gHyx1+jAahYB9ekpB/tU/91fxeiEzvah320MmI84TcCuPGaAKhExXTgVs0kXFXdnQxpvfKlM3phi4= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.76) by AM6PR08MB3014.eurprd08.prod.outlook.com (52.135.163.31) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1516.13; Tue, 15 Jan 2019 20:43: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; Tue, 15 Jan 2019 20:43:45 +0000 From: Honnappa Nagarahalli To: "Ananyev, Konstantin" , "dev@dpdk.org" , "stephen@networkplumber.org" , "paulmck@linux.ibm.com" CC: "Gavin Hu (Arm Technology China)" , Dharmik Thakkar , nd , Honnappa Nagarahalli , nd Thread-Topic: [RFC v2 1/2] rcu: add RCU library supporting QSBR mechanism Thread-Index: AQHUmZwkA3lN9JDuXEiclvOGJBGOtKWwUixggACXpdA= Date: Tue, 15 Jan 2019 20:43:45 +0000 Message-ID: References: <20181122033055.3431-1-honnappa.nagarahalli@arm.com> <20181222021420.5114-1-honnappa.nagarahalli@arm.com> <20181222021420.5114-2-honnappa.nagarahalli@arm.com> <2601191342CEEE43887BDE71AB977258010D904212@irsmsx105.ger.corp.intel.com> In-Reply-To: <2601191342CEEE43887BDE71AB977258010D904212@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=Honnappa.Nagarahalli@arm.com; x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3014; 6:jchhVDVMQeJMVTL+tyrF6YAjWZI1oNgsSx7GHPA4JT1rRpAdIgNfLTUKlg526x5/LNiMoIV8sS5KMQowezrRqrZ7ZZOFFc3BUGBSpyGiqQdDaIOAh21Wi3KANhtzvgln9JRJ3Eh5elwbidAFA94WwIFcEXbKhVwbGkiryCxU2PSoYtguNKPPeXTI0Ca4jkkMMi5Xp5xuKa92sKibMalm+QdGUMcKwFu70Pcpx3J5TbCM/h2Fpox6MSAUC9ZU/dB6XWNCBtXa2/N9VqCnL1gyHJKWp7mI0Df33PeXNjTVg5Bsu1rVQ026GMoau52UPGZRhBjaJsRwfN9XxXPqZ/fgi3AJnpIfv/Q8P/aIymIfKR4cP6aXhCciVS58vdYzelHTkLG1NNnKPHnKFlQ54o8/okppISa8Yy/6bEXtf1ugoYFFlUs1F73xECWSlGoySLAhitScx9jci26EwM1a0pDeUg==; 5:FDFPZWqXcRXwR/KRIck9jELU3qcR1x/COf6m6fue3jvMVouiQzwdtonnnh+jvx50g0wRUpI50W9kC7CndNhYugNgA7VEnz970mpyVxiHYUgcTPSFjLh8p3Hf+svCXJKSDyxfxSMxT6avYg8S8vU8KwvuLQN9Bdw2GjDof2rWv8NAG2OekhZ1Ga3OU5pjEZ+3fa+jN8nyXhbHF4TQYm/6sA==; 7:SGypauIyCXNv8KxYEVtbEU27OeHEv9Sm13Vh8EtqX8lqd6zTy3p96FLV2X+F1Yw3Ji6N97l/A463eb+Fw6KrHUUOmZnHGM90dssFQQVH5E/XsGW+ur/EI1A1NYSaJyTdgiX85wegyPGiehzczflZOA== x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: 3b4f48ec-78bb-4404-8202-08d67b2a24a4 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:AM6PR08MB3014; x-ms-traffictypediagnostic: AM6PR08MB3014: nodisclaimer: True x-microsoft-antispam-prvs: x-forefront-prvs: 0918748D70 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(136003)(376002)(346002)(366004)(39860400002)(396003)(199004)(189003)(53936002)(9686003)(6116002)(3846002)(110136005)(316002)(93886005)(81166006)(81156014)(8676002)(4326008)(2906002)(8936002)(71190400001)(99286004)(4744004)(26005)(68736007)(186003)(71200400001)(102836004)(14444005)(256004)(54906003)(30864003)(6506007)(76176011)(7696005)(486006)(7736002)(305945005)(66066001)(55016002)(6436002)(2201001)(86362001)(5660300001)(229853002)(74316002)(11346002)(476003)(446003)(25786009)(478600001)(6246003)(33656002)(97736004)(105586002)(106356001)(72206003)(2501003)(14454004); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3014; 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: fV4goZ6R6xpWQogxbloeQdx/YTlyk4TgKPW4nvv6Yu54LBKKQjWN3cGQofGmK1zlXr5f5KTPVZOawKJD125bMIa0miYfnevum70eL6SDgmMnzROAfjPyUpP9R9giZFOaWNiAtF39A46vpqZlBl77OceWF6v/XYVbYIuP6ciPoiHGu2deZMzn9TiRCTGBizKxQ0OpWyOHQZqezkSz6gN7YtngC+Ws0tA/UobVDdtftAeomo7+agotRJPWkAnRWn4Nn+RohjRMtI0m+BuDz0smlTfH67Oq/M4yoSS9SobcC03icSCXksya01H2SA30okOiZhcX5UgIr7M6qrkST+wLODmk1vpkhtTRq7ez1a5FwYLM4uUc5zM5AIIW0aF1dgUa42GPJPsiYQ429Gl9+faQj2T3ogy9sdxKn+mm4kUIitQ= 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: 3b4f48ec-78bb-4404-8202-08d67b2a24a4 X-MS-Exchange-CrossTenant-originalarrivaltime: 15 Jan 2019 20:43:45.1986 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3014 Subject: Re: [dpdk-dev] [RFC v2 1/2] rcu: add RCU library supporting QSBR mechanism 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: Tue, 15 Jan 2019 20:43:47 -0000 > Hi Honnappa, >=20 >=20 > > Add RCU library supporting quiescent state based memory reclamation > method. > > This library helps identify the quiescent state of the reader threads > > so that the writers can free the memory associated with the lock less > > data structures. > > > > Signed-off-by: Honnappa Nagarahalli > > Reviewed-by: Steve Capper > > Reviewed-by: Gavin Hu > > --- > ... >=20 > > diff --git a/lib/librte_rcu/rte_rcu_qsbr.h > > b/lib/librte_rcu/rte_rcu_qsbr.h new file mode 100644 index > > 000000000..c818e77fd > > --- /dev/null > > +++ b/lib/librte_rcu/rte_rcu_qsbr.h > > @@ -0,0 +1,321 @@ > > +/* SPDX-License-Identifier: BSD-3-Clause > > + * Copyright (c) 2018 Arm Limited > > + */ > > + > > +#ifndef _RTE_RCU_QSBR_H_ > > +#define _RTE_RCU_QSBR_H_ > > + > > +/** > > + * @file > > + * RTE Quiescent State Based Reclamation (QSBR) > > + * > > + * Quiescent State (QS) is any point in the thread execution > > + * where the thread does not hold a reference to shared memory. > > + * A critical section for a data structure can be a quiescent state > > +for > > + * another data structure. > > + * > > + * This library provides the ability to identify quiescent state. > > + */ > > + > > +#ifdef __cplusplus > > +extern "C" { > > +#endif > > + > > +#include > > +#include > > +#include > > +#include > > +#include > > +#include > > +#include > > + > > +/**< Maximum number of reader threads supported. */ #define > > +RTE_RCU_MAX_THREADS 128 > > + > > +#if !RTE_IS_POWER_OF_2(RTE_RCU_MAX_THREADS) > > +#error RTE_RCU_MAX_THREADS must be a power of 2 #endif > > + > > +/**< Number of array elements required for the bit-map */ #define > > +RTE_QSBR_BIT_MAP_ELEMS (RTE_RCU_MAX_THREADS/(sizeof(uint64_t) > * 8)) > > + > > +/* Thread IDs are stored as a bitmap of 64b element array. Given > > +thread id > > + * needs to be converted to index into the array and the id within > > + * the array element. > > + */ > > +#define RTE_QSBR_THR_INDEX_SHIFT 6 > > +#define RTE_QSBR_THR_ID_MASK 0x3f > > + > > +/* Worker thread counter */ > > +struct rte_rcu_qsbr_cnt { > > + uint64_t cnt; /**< Quiescent state counter. */ } > > +__rte_cache_aligned; > > + > > +/** > > + * RTE thread Quiescent State structure. > > + */ > > +struct rte_rcu_qsbr { > > + uint64_t reg_thread_id[RTE_QSBR_BIT_MAP_ELEMS] > __rte_cache_aligned; > > + /**< Registered reader thread IDs - reader threads reporting > > + * on this QS variable represented in a bit map. > > + */ > > + > > + uint64_t token __rte_cache_aligned; > > + /**< Counter to allow for multiple simultaneous QS queries */ > > + > > + struct rte_rcu_qsbr_cnt w[RTE_RCU_MAX_THREADS] > __rte_cache_aligned; > > + /**< QS counter for each reader thread, counts upto > > + * current value of token. >=20 > As I understand you decided to stick with neutral thread_id and let user > define what exactly thread_id is (lcore, syste, thread id, something else= )? Yes, that is correct. I will reply to the other thread to continue the disc= ussion. > If so, can you probably get rid of RTE_RCU_MAX_THREADS limitation? I am not seeing this as a limitation. The user can change this if required.= May be I should change it as follows: #ifndef RTE_RCU_MAX_THREADS #define RTE_RCU_MAX_THREADS 128 #endif > I.E. struct rte_rcu_qsbr_cnt w[] and allow user at init time to define ma= x > number of threads allowed. > Or something like: > #define RTE_RCU_QSBR_DEF(name, max_thread) struct name { \ > uint64_t reg_thread_id[ALIGN_CEIL(max_thread, 64) >> 6]; \ > ... > struct rte_rcu_qsbr_cnt w[max_thread]; \ } I am trying to understand this. I am not following why 'name' is required? = Would the user call 'RTE_RCU_QSBR_DEF' in the application header file? >=20 >=20 > > + */ > > +} __rte_cache_aligned; > > + > > +/** > > + * @warning > > + * @b EXPERIMENTAL: this API may change without prior notice > > + * > > + * Initialize a Quiescent State (QS) variable. > > + * > > + * @param v > > + * QS variable > > + * > > + */ > > +void __rte_experimental > > +rte_rcu_qsbr_init(struct rte_rcu_qsbr *v); > > + > > +/** > > + * @warning > > + * @b EXPERIMENTAL: this API may change without prior notice > > + * > > + * Add a reader thread, to the list of threads reporting their > > +quiescent > > + * state on a QS variable. > > + * > > + * This is implemented as a lock-free function. It is multi-thread > > + * safe. > > + * Any reader thread that wants to report its quiescent state must > > + * call this API before calling rte_rcu_qsbr_update. This can be > > +called > > + * during initialization or as part of the packet processing loop. > > + * Any ongoing QS queries may wait for the status from this > > +registered > > + * thread. > > + * > > + * @param v > > + * QS variable > > + * @param thread_id > > + * Reader thread with this thread ID will report its quiescent state= on > > + * the QS variable. > > + */ > > +static __rte_always_inline void __rte_experimental > > +rte_rcu_qsbr_register_thread(struct rte_rcu_qsbr *v, unsigned int > > +thread_id) { > > + unsigned int i, id; > > + > > + RTE_ASSERT(v =3D=3D NULL || thread_id >=3D RTE_RCU_MAX_THREADS); > > + > > + id =3D thread_id & RTE_QSBR_THR_ID_MASK; > > + i =3D thread_id >> RTE_QSBR_THR_INDEX_SHIFT; > > + > > + /* Worker thread has to count the quiescent states > > + * only from the current value of token. > > + * __atomic_store_n(cnt, __ATOMIC_RELAXED) is used to ensure > > + * 'cnt' (64b) is accessed atomically. > > + */ > > + __atomic_store_n(&v->w[thread_id].cnt, > > + __atomic_load_n(&v->token, __ATOMIC_ACQUIRE), > > + __ATOMIC_RELAXED); > > + > > + /* Release the store to initial TQS count so that readers > > + * can use it immediately after this function returns. > > + */ > > + __atomic_fetch_or(&v->reg_thread_id[i], 1UL << id, > > +__ATOMIC_RELEASE); } > > + > > +/** > > + * @warning > > + * @b EXPERIMENTAL: this API may change without prior notice > > + * > > + * Remove a reader thread, from the list of threads reporting their > > + * quiescent state on a QS variable. > > + * > > + * This is implemented as a lock-free function. It is multi-thread saf= e. > > + * This API can be called from the reader threads during shutdown. > > + * Ongoing QS queries will stop waiting for the status from this > > + * unregistered reader thread. > > + * > > + * @param v > > + * QS variable > > + * @param thread_id > > + * Reader thread with this thread ID will stop reporting its quiesce= nt > > + * state on the QS variable. > > + */ > > +static __rte_always_inline void __rte_experimental > > +rte_rcu_qsbr_unregister_thread(struct rte_rcu_qsbr *v, unsigned int > > +thread_id) { > > + unsigned int i, id; > > + > > + RTE_ASSERT(v =3D=3D NULL || thread_id >=3D RTE_RCU_MAX_THREADS); > > + > > + id =3D thread_id & RTE_QSBR_THR_ID_MASK; > > + i =3D thread_id >> RTE_QSBR_THR_INDEX_SHIFT; > > + > > + /* Make sure the removal of the thread from the list of > > + * reporting threads is visible before the thread > > + * does anything else. > > + */ > > + __atomic_fetch_and(&v->reg_thread_id[i], > > + ~(1UL << id), __ATOMIC_RELEASE); > > +} > > + > > +/** > > + * @warning > > + * @b EXPERIMENTAL: this API may change without prior notice > > + * > > + * Trigger the reader threads to report the quiescent state > > + * status. > > + * > > + * This is implemented as a lock-free function. It is multi-thread > > + * safe and can be called from worker threads. > > + * > > + * @param v > > + * TQS variable > > + * @param n > > + * Expected number of times the quiescent state is entered > > + * @param t > > + * - If successful, this is the token for this call of the API. > > + * This should be passed to rte_rcu_qsbr_check API. > > + */ > > +static __rte_always_inline void __rte_experimental > > +rte_rcu_qsbr_start(struct rte_rcu_qsbr *v, unsigned int n, uint64_t > > +*t) { > > + RTE_ASSERT(v =3D=3D NULL || t =3D=3D NULL); > > + > > + /* This store release will ensure that changes to any data > > + * structure are visible to the workers before the token > > + * update is visible. > > + */ > > + *t =3D __atomic_add_fetch(&v->token, n, __ATOMIC_RELEASE); } > > + > > +/** > > + * @warning > > + * @b EXPERIMENTAL: this API may change without prior notice > > + * > > + * Update quiescent state for a reader thread. > > + * > > + * This is implemented as a lock-free function. It is multi-thread saf= e. > > + * All the reader threads registered to report their quiescent state > > + * on the QS variable must call this API. > > + * > > + * @param v > > + * QS variable > > + */ > > +static __rte_always_inline void __rte_experimental > > +rte_rcu_qsbr_update(struct rte_rcu_qsbr *v, unsigned int thread_id) { > > + uint64_t t; > > + > > + RTE_ASSERT(v =3D=3D NULL || thread_id >=3D RTE_RCU_MAX_THREADS); > > + > > + /* Load the token before the reader thread loads any other > > + * (lock-free) data structure. This ensures that updates > > + * to the data structures are visible if the update > > + * to token is visible. > > + */ > > + t =3D __atomic_load_n(&v->token, __ATOMIC_ACQUIRE); > > + > > + /* Relaxed load/store on the counter is enough as we are > > + * reporting an already completed quiescent state. > > + * __atomic_load_n(cnt, __ATOMIC_RELAXED) is used as 'cnt' (64b) > > + * is accessed atomically. > > + * Copy the current token value. This will end grace period > > + * of multiple concurrent writers. > > + */ > > + if (__atomic_load_n(&v->w[thread_id].cnt, __ATOMIC_RELAXED) !=3D t) > > + __atomic_store_n(&v->w[thread_id].cnt, t, > __ATOMIC_RELAXED); } > > + > > +/** > > + * @warning > > + * @b EXPERIMENTAL: this API may change without prior notice > > + * > > + * Checks if all the reader threads have entered the quiescent state > > + * 'n' number of times. 'n' is provided in rte_rcu_qsbr_start API. > > + * > > + * This is implemented as a lock-free function. It is multi-thread > > + * safe and can be called from the worker threads as well. > > + * > > + * @param v > > + * QS variable > > + * @param t > > + * Token returned by rte_rcu_qsbr_start API > > + * @param wait > > + * If true, block till all the reader threads have completed enterin= g > > + * the quiescent state 'n' number of times > > + * @return > > + * - 0 if all reader threads have NOT passed through specified numbe= r > > + * of quiescent states. > > + * - 1 if all reader threads have passed through specified number > > + * of quiescent states. > > + */ > > +static __rte_always_inline int __rte_experimental > > +rte_rcu_qsbr_check(struct rte_rcu_qsbr *v, uint64_t t, bool wait) { > > + uint32_t i, j, id; > > + uint64_t bmap; > > + > > + RTE_ASSERT(v =3D=3D NULL); > > + > > + i =3D 0; > > + do { > > + /* Load the current registered thread bit map before > > + * loading the reader thread quiescent state counters. > > + */ > > + bmap =3D __atomic_load_n(&v->reg_thread_id[i], > __ATOMIC_ACQUIRE); > > + id =3D i << RTE_QSBR_THR_INDEX_SHIFT; > > + > > + while (bmap) { > > + j =3D __builtin_ctzl(bmap); > > + > > + /* __atomic_store_n(cnt, __ATOMIC_RELAXED) > > + * is used to ensure 'cnt' (64b) is accessed > > + * atomically. > > + */ > > + if (unlikely(__atomic_load_n(&v->w[id + j].cnt, > > + __ATOMIC_RELAXED) < t)) { > > + /* This thread is not in QS */ > > + if (!wait) > > + return 0; > > + > > + /* Loop till this thread enters QS */ > > + rte_pause(); > > + continue; > Shouldn't you re-read reg_thread_id[i] here? > Konstantin Yes, you are right. I will try to add a test case as well to address this. > > + } > > + > > + bmap &=3D ~(1UL << j); > > + } > > + > > + i++; > > + } while (i < RTE_QSBR_BIT_MAP_ELEMS); > > + > > + return 1; > > +} > > +