From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga18.intel.com (mga18.intel.com [134.134.136.126]) by dpdk.org (Postfix) with ESMTP id B17845F14 for ; Tue, 15 Jan 2019 12:40:01 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by orsmga106.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 15 Jan 2019 03:39:56 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.56,481,1539673200"; d="scan'208";a="134753235" Received: from irsmsx152.ger.corp.intel.com ([163.33.192.66]) by fmsmga002.fm.intel.com with ESMTP; 15 Jan 2019 03:39:54 -0800 Received: from irsmsx155.ger.corp.intel.com (163.33.192.3) by IRSMSX152.ger.corp.intel.com (163.33.192.66) with Microsoft SMTP Server (TLS) id 14.3.408.0; Tue, 15 Jan 2019 11:39:53 +0000 Received: from irsmsx105.ger.corp.intel.com ([169.254.7.116]) by irsmsx155.ger.corp.intel.com ([169.254.14.157]) with mapi id 14.03.0415.000; Tue, 15 Jan 2019 11:39:53 +0000 From: "Ananyev, Konstantin" To: Honnappa Nagarahalli , "dev@dpdk.org" , "stephen@networkplumber.org" , "paulmck@linux.ibm.com" CC: "gavin.hu@arm.com" , "dharmik.thakkar@arm.com" , "nd@arm.com" Thread-Topic: [RFC v2 1/2] rcu: add RCU library supporting QSBR mechanism Thread-Index: AQHUmZwkA3lN9JDuXEiclvOGJBGOtKWwUixg Date: Tue, 15 Jan 2019 11:39:53 +0000 Message-ID: <2601191342CEEE43887BDE71AB977258010D904212@irsmsx105.ger.corp.intel.com> References: <20181122033055.3431-1-honnappa.nagarahalli@arm.com> <20181222021420.5114-1-honnappa.nagarahalli@arm.com> <20181222021420.5114-2-honnappa.nagarahalli@arm.com> In-Reply-To: <20181222021420.5114-2-honnappa.nagarahalli@arm.com> Accept-Language: en-IE, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiMDVhNTE1YjItOWFjMS00MDYzLTgzZWUtZTA1YWI5YTEyODUyIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiNmN3YjNLa1VQWjhhTUJnUzRCY1YrSmFEMmpGcXlBTmVZMkRGSUhhaWREVHBiZGN5Umpoa1ZVZjY2cWZjR0ZsYSJ9 x-ctpclassification: CTP_NT dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-originating-ip: [163.33.239.182] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 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 11:40:02 -0000 Hi Honnappa, =20 > Add RCU library supporting quiescent state based memory reclamation metho= d. > 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. >=20 > Signed-off-by: Honnappa Nagarahalli > Reviewed-by: Steve Capper > Reviewed-by: Gavin Hu > --- ... > 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. As I understand you decided to stick with neutral thread_id and let user de= fine what exactly thread_id is (lcore, syste, thread id, something else)? If so, can you probably get rid of RTE_RCU_MAX_THREADS limitation? I.E. struct rte_rcu_qsbr_cnt w[] and allow user at init time to define max 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]; \ } > + */ > +} __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 o= n > + * 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 safe. > + * 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 quiescent > + * state on the QS variable. > + */ > +static __rte_always_inline void __rte_experimental > +rte_rcu_qsbr_unregister_thread(struct rte_rcu_qsbr *v, unsigned int thre= ad_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 safe. > + * 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 entering > + * the quiescent state 'n' number of times > + * @return > + * - 0 if all reader threads have NOT passed through specified number > + * 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 > + } > + > + bmap &=3D ~(1UL << j); > + } > + > + i++; > + } while (i < RTE_QSBR_BIT_MAP_ELEMS); > + > + return 1; > +} > +