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 25916A05D3 for ; Mon, 25 Mar 2019 12:34:39 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 41F9E2BD3; Mon, 25 Mar 2019 12:34:38 +0100 (CET) Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by dpdk.org (Postfix) with ESMTP id 35E1F11A4 for ; Mon, 25 Mar 2019 12:34:35 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by fmsmga107.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 25 Mar 2019 04:34:35 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.60,256,1549958400"; d="scan'208";a="285655836" Received: from irsmsx105.ger.corp.intel.com ([163.33.3.28]) by orsmga004.jf.intel.com with ESMTP; 25 Mar 2019 04:34:33 -0700 Received: from irsmsx104.ger.corp.intel.com ([169.254.5.56]) by irsmsx105.ger.corp.intel.com ([169.254.7.210]) with mapi id 14.03.0415.000; Mon, 25 Mar 2019 11:34:31 +0000 From: "Kovacevic, Marko" To: Honnappa Nagarahalli , "Ananyev, Konstantin" , "stephen@networkplumber.org" , "paulmck@linux.ibm.com" , "dev@dpdk.org" CC: "gavin.hu@arm.com" , "dharmik.thakkar@arm.com" , "malvika.gupta@arm.com" Thread-Topic: [dpdk-dev] [PATCH 3/3] doc/rcu: add lib_rcu documentation Thread-Index: AQHU3g+7B4A6TJs65UuRl69bkYnnl6YcN6QA Date: Mon, 25 Mar 2019 11:34:31 +0000 Message-ID: <6DC05C7C5F25994B81B3F2F214251F66020AC33E@IRSMSX104.ger.corp.intel.com> References: <20181122033055.3431-1-honnappa.nagarahalli@arm.com> <20190319045228.46879-1-honnappa.nagarahalli@arm.com> <20190319045228.46879-4-honnappa.nagarahalli@arm.com> In-Reply-To: <20190319045228.46879-4-honnappa.nagarahalli@arm.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiYzI0YjRhYTYtZDlkYy00MDM0LThjMGQtOGM3MmRhZWIyOGVlIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoieUR1bjVmbGdSTXFNQzFXS3k4d2Uwa0t3elZvRTNYdGlGZTRvK2srUDduTWo5K2pDVjJ0Wm9sc2tSQk1JcmVLTSJ9 x-ctpclassification: CTP_NT x-originating-ip: [163.33.239.180] Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH 3/3] doc/rcu: add lib_rcu documentation 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: <20190325113431.fDT-s94cDlXpJVzSuN6qEZEQ_NA-d87JHEPigjUdIAw@z> > Subject: [dpdk-dev] [PATCH 3/3] doc/rcu: add lib_rcu documentation >=20 > Add lib_rcu QSBR API and programmer guide documentation. >=20 > Signed-off-by: Honnappa Nagarahalli >=20 > --- > doc/api/doxy-api-index.md | 3 +- > doc/api/doxy-api.conf.in | 1 + > .../prog_guide/img/rcu_general_info.svg | 494 ++++++++++++++++++ > doc/guides/prog_guide/index.rst | 1 + > doc/guides/prog_guide/rcu_lib.rst | 179 +++++++ > 5 files changed, 677 insertions(+), 1 deletion(-) create mode 100644 > doc/guides/prog_guide/img/rcu_general_info.svg > create mode 100644 doc/guides/prog_guide/rcu_lib.rst > =20 <...> > diff --git a/doc/guides/prog_guide/index.rst > b/doc/guides/prog_guide/index.rst index 6726b1e8d..6fb3fb921 100644 > --- a/doc/guides/prog_guide/index.rst > +++ b/doc/guides/prog_guide/index.rst > @@ -55,6 +55,7 @@ Programmer's Guide > metrics_lib > bpf_lib > ipsec_lib > + rcu_lib > source_org > dev_kit_build_system > dev_kit_root_make_help > diff --git a/doc/guides/prog_guide/rcu_lib.rst > b/doc/guides/prog_guide/rcu_lib.rst > new file mode 100644 > index 000000000..5155dd35c > --- /dev/null > +++ b/doc/guides/prog_guide/rcu_lib.rst > @@ -0,0 +1,179 @@ > +.. SPDX-License-Identifier: BSD-3-Clause > + Copyright(c) 2019 Arm Limited. > + > +.. _RCU_Library: > + > +RCU Library > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > + > +Lock-less data structures provide scalability and determinism. > +They enable use cases where locking may not be allowed (for ex: > +real-time applications). > + > +In the following paras, the term 'memory' refers to memory allocated by > +typical APIs like malloc or anything that is representative of memory, > +for ex: an index of a free element array. > + > +Since these data structures are lock less, the writers and readers are > +accessing the data structures concurrently. Hence, while removing an > +element from a data structure, the writers cannot return the memory to > +the allocator, without knowing that the readers are not referencing > +that element/memory anymore. Hence, it is required to separate the > +operation of removing an element into 2 steps: > + > +Delete: in this step, the writer removes the reference to the element > +from the data structure but does not return the associated memory to > +the allocator. This will ensure that new readers will not get a > +reference to the removed element. Removing the reference is an atomic > operation. > + > +Free(Reclaim): in this step, the writer returns the memory to the > +memory allocator, only after knowing that all the readers have stopped > +referencing the deleted element. > + > +This library helps the writer determine when it is safe to free the > +memory. > + > +This library makes use of thread Quiescent State (QS). > + > +What is Quiescent State > +----------------------- > +Quiescent State can be defined as 'any point in the thread execution > +where the thread does not hold a reference to shared memory'. It is > +upto the application to determine its quiescent state. > + > +Let us consider the following diagram: > + > +.. figure:: img/rcu_general_info.* > + > + > +As shown, reader thread 1 acesses data structures D1 and D2. When it is Spelling acesses / accesses=20 > +accessing D1, if the writer has to remove an element from D1, the > +writer cannot free the memory associated with that element immediately. > +The writer can return the memory to the allocator only after the reader > +stops referencng D1. In other words, reader thread RT1 has to enter a Spelling referencng / referencing=20 > +quiescent state. > + > +Similarly, since reader thread 2 is also accessing D1, writer has to > +wait till thread 2 enters quiescent state as well. > + > +However, the writer does not need to wait for reader thread 3 to enter > +quiescent state. Reader thread 3 was not accessing D1 when the delete > +operation happened. So, reader thread 1 will not have a reference to > +the deleted entry. > + > +It can be noted that, the critical sections for D2 is a quiescent state > +for D1. i.e. for a given data structure Dx, any point in the thread > +execution that does not reference Dx is a quiescent state. > + > +Since memory is not freed immediately, there might be a need for > +provisioning of additional memory, depending on the application > requirements. > + > +Factores affecting RCU mechanism > +--------------------------------- Spelling Factores/ Factors > + > +It is important to make sure that this library keeps the over head of =20 Over head / overhead=20 > +identifying the end of grace period and subsequent freeing of memory, > +to a minimum. The following paras explain how grace period and critical > +section affect this overhead. > + > +The writer has to poll the readers to identify the end of grace period. > +Polling introduces memory accesses and wastes CPU cycles. The memory is > +not available for reuse during grace period. Longer grace periods > +exasperate these conditions. > + > +The length of the critical section and the number of reader threads is > +proportional to the duration of the grace period. Keeping the critical > +sections smaller will keep the grace period smaller. However, keeping > +the critical sections smaller requires additional CPU cycles(due to > +additional > +reporting) in the readers. > + > +Hence, we need the characteristics of small grace period and large > +critical section. This library addresses this by allowing the writer to > +do other work without having to block till the readers report their > +quiescent state. > + > +RCU in DPDK > +----------- > + > +For DPDK applications, the start and end of while(1) loop (where no > +references to shared data structures are kept) act as perfect quiescent > +states. This will combine all the shared data structure accesses into a > +single, large critical section which helps keep the over head on the Over head / overhead > +reader side to a minimum. > + > +DPDK supports pipeline model of packet processing and service cores. > +In these use cases, a given data structure may not be used by all the > +workers in the application. The writer does not have to wait for all > +the workers to report their quiescent state. To provide the required > +flexibility, this library has a concept of QS variable. The application > +can create one QS variable per data structure to help it track the end > +of grace period for each data structure. This helps keep the grace > +period to a minimum. > + > +How to use this library > +----------------------- > + > +The application has to allocate memory and initialize a QS variable. > + Maybe instead of making the call below bold using `` `` might be better to = use **rte_rcu_qsbr_get_memsize** ``rte_rcu_qsbr_get_memsize`` =20 For all of them below > +Application can call **rte_rcu_qsbr_get_memsize** to calculate the size > +of memory to allocate. This API takes maximum number of reader threads, > +using this variable, as a parameter. Currently, a maximum of 1024 > +threads are supported. > + > +Further, the application can initialize a QS variable using the API > +**rte_rcu_qsbr_init**. > + > +Each reader thread is assumed to have a unique thread ID. Currently, > +the management of the thread ID (for ex: allocation/free) is left to > +the application. The thread ID should be in the range of 0 to maximum > +number of threads provided while creating the QS variable. > +The application could also use lcore_id as the thread ID where applicabl= e. > + > +**rte_rcu_qsbr_thread_register** API will register a reader thread to > +report its quiescent state. This can be called from a reader thread. > +A control plane thread can also call this on behalf of a reader thread. > +The reader thread must call **rte_rcu_qsbr_thread_online** API to start > +reporting its quiescent state. > + > +Some of the use cases might require the reader threads to make blocking > +API calls (for ex: while using eventdev APIs). The writer thread should > +not wait for such reader threads to enter quiescent state. > +The reader thread must call **rte_rcu_qsbr_thread_offline** API, before > +calling blocking APIs. It can call **rte_rcu_qsbr_thread_online** API > +once the blocking API call returns. > + > +The writer thread can trigger the reader threads to report their > +quiescent state by calling the API **rte_rcu_qsbr_start**. It is > +possible for multiple writer threads to query the quiescent state > +status simultaneously. Hence, > +**rte_rcu_qsbr_start** returns a token to each caller. > + > +The writer thread has to call **rte_rcu_qsbr_check** API with the token > +to get the current quiescent state status. Option to block till all the > +reader threads enter the quiescent state is provided. If this API > +indicates that all the reader threads have entered the quiescent state, > +the application can free the deleted entry. > + > +The APIs **rte_rcu_qsbr_start** and **rte_rcu_qsbr_check** are lock > free. > +Hence, they can be called concurrently from multiple writers even while > +running as worker threads. > + > +The separation of triggering the reporting from querying the status > +provides the writer threads flexibility to do useful work instead of > +blocking for the reader threads to enter the quiescent state or go > +offline. This reduces the memory accesses due to continuous polling for = the > status. > + > +**rte_rcu_qsbr_synchronize** API combines the functionality of > +**rte_rcu_qsbr_start** and blocking **rte_rcu_qsbr_check** into a single > API. > +This API triggers the reader threads to report their quiescent state > +and polls till all the readers enter the quiescent state or go offline. > +This API does not allow the writer to do useful work while waiting and > +also introduces additional memory accesses due to continuous polling. > + > +The reader thread must call **rte_rcu_qsbr_thread_offline** and > +**rte_rcu_qsbr_thread_unregister** APIs to remove itself from reporting > +its quiescent state. The **rte_rcu_qsbr_check** API will not wait for > +this reader thread to report the quiescent state status anymore. > + > +The reader threads should call **rte_rcu_qsbr_update** API to indicate > +that they entered a quiescent state. This API checks if a writer has > +triggered a quiescent state query and update the state accordingly. > -- If it's possible to enlarge the image a bit it would be good to be able to = read the lower text I need to enlarge it to 175% maybe I'm just blind but if it's possible it w= ould be great Reviewed-by: Marko Kovacevic