From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id AD6A8A2EDB for ; Fri, 6 Sep 2019 21:44:38 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 539701F3F0; Fri, 6 Sep 2019 21:44:37 +0200 (CEST) Received: from EUR03-VE1-obe.outbound.protection.outlook.com (mail-eopbgr50058.outbound.protection.outlook.com [40.107.5.58]) by dpdk.org (Postfix) with ESMTP id E847B1F3EF for ; Fri, 6 Sep 2019 21:44:35 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=FOSz817t2Wy8+7KaQ+egQYWEghwV2kzP35Aan3RWtQU=; b=kzXsNZRIGGk1h0vw8EmoheewjW1vyMY1VU6aQMcKxb54MvUBrLmUAnXDidDwiqHeo1HQemj/vZnGc3HeePEHSHtXE72pBTHdBSX7f7TCa/j/HuGnoh9bbf4TEe3NgSC9cjlmDT/r53/ke6/q8AeZMHHiWsF5AOAd/9psoD/eDb0= Received: from VE1PR08CA0033.eurprd08.prod.outlook.com (2603:10a6:803:104::46) by AM0PR08MB5281.eurprd08.prod.outlook.com (2603:10a6:208:124::25) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2220.20; Fri, 6 Sep 2019 19:44:33 +0000 Received: from VE1EUR03FT060.eop-EUR03.prod.protection.outlook.com (2a01:111:f400:7e09::205) by VE1PR08CA0033.outlook.office365.com (2603:10a6:803:104::46) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.2241.14 via Frontend Transport; Fri, 6 Sep 2019 19:44:33 +0000 Authentication-Results: spf=temperror (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dpdk.org; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dpdk.org; dmarc=temperror action=none header.from=arm.com; Received-SPF: TempError (protection.outlook.com: error in processing during lookup of arm.com: DNS Timeout) Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by VE1EUR03FT060.mail.protection.outlook.com (10.152.19.187) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.2241.14 via Frontend Transport; Fri, 6 Sep 2019 19:44:32 +0000 Received: ("Tessian outbound a25c4e5fef41:v27"); Fri, 06 Sep 2019 19:44:27 +0000 X-CR-MTA-TID: 64aa7808 Received: from bafed53b096b.3 (cr-mta-lb-1.cr-mta-net [104.47.8.57]) by 64aa7808-outbound-1.mta.getcheckrecipient.com id FF6290DC-A39F-4A41-BCD3-B81E1F78DCCD.1; Fri, 06 Sep 2019 19:44:22 +0000 Received: from EUR03-AM5-obe.outbound.protection.outlook.com (mail-am5eur03lp2057.outbound.protection.outlook.com [104.47.8.57]) by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id bafed53b096b.3 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Fri, 06 Sep 2019 19:44:22 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=bO5JSNSE7JuCfXKbvV7mDhqJjsuo7WzkGhzlRCxrI7ggxWKuSX6CvIhp4KQTszv4ZMSL1HnAozulUDxzjCFXAOSKTdmWHKQD3QxdPDP75J9rNS89K0TrqZv5Hn/gmYtIHxNjFJ0mrJFN9wB3//56hEH0dMzBtopf4JjYhE+yS4HlErTLNY/cdlKMtup1U/C+DmD7ZBzdd9MprCsjTx7YWGrWvXLP/zQ6ryGKb4VBgE+ASV+h6WBXyQrJFxGoQe59gU3BaObkLE1I0Qj9SXm7FReiaqovKn21M5UP6IzIXfYzbJPyIcOImkhvR1tJhkMaQ4nl2dNTsXBIFbx+gJGO8w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=FOSz817t2Wy8+7KaQ+egQYWEghwV2kzP35Aan3RWtQU=; b=J5Wr438QIuy0GTxoOWz+cUxlTSBmFENvME2ovLWrVKSkuNyiSP3hosJbqYWNvpJfm/ykTB3ZyISdNfvGh4TnsRIFmdlVAd6Lkhb3EDvAph2LTHLRoYF1yrNL3/Qjm9E1i90cSspUoujxaGxJcBOlxXbVoEHaEyS5IJ3XhR13zP9OB/XnsjnA7j5M5E/cKZ0xqliSX4l0L3atCbd7G7qJXfodtXvaoVxILQeRUB5kxCatRVn/I3ytm86fxBrDRJotO3xLnk17KG5ebConuU+wwYBdpQmQ0mBwSpKcD5/yn4/OWIr4OcNVW/jTMvPxeNJ9/ksTk4+a+aUHxTvpoiBftA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=FOSz817t2Wy8+7KaQ+egQYWEghwV2kzP35Aan3RWtQU=; b=kzXsNZRIGGk1h0vw8EmoheewjW1vyMY1VU6aQMcKxb54MvUBrLmUAnXDidDwiqHeo1HQemj/vZnGc3HeePEHSHtXE72pBTHdBSX7f7TCa/j/HuGnoh9bbf4TEe3NgSC9cjlmDT/r53/ke6/q8AeZMHHiWsF5AOAd/9psoD/eDb0= Received: from VE1PR08MB5149.eurprd08.prod.outlook.com (20.179.30.152) by VE1PR08MB4976.eurprd08.prod.outlook.com (10.255.158.145) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2241.18; Fri, 6 Sep 2019 19:44:20 +0000 Received: from VE1PR08MB5149.eurprd08.prod.outlook.com ([fe80::a8af:a9b8:4597:4128]) by VE1PR08MB5149.eurprd08.prod.outlook.com ([fe80::a8af:a9b8:4597:4128%3]) with mapi id 15.20.2178.023; Fri, 6 Sep 2019 19:44:20 +0000 From: Honnappa Nagarahalli To: "Ruifeng Wang (Arm Technology China)" , "bruce.richardson@intel.com" , "vladimir.medvedkin@intel.com" , "olivier.matz@6wind.com" CC: "dev@dpdk.org" , "stephen@networkplumber.org" , "konstantin.ananyev@intel.com" , "Gavin Hu (Arm Technology China)" , Dharmik Thakkar , nd , "paulmck@linux.ibm.com" , nd Thread-Topic: [PATCH v2 1/6] doc/rcu: add RCU integration design details Thread-Index: AQHVZOt6OPXhISDKkk+CN+0bF/d6cQ== Date: Fri, 6 Sep 2019 19:44:20 +0000 Message-ID: References: <20190822063457.41596-1-ruifeng.wang@arm.com> <20190906094534.36060-1-ruifeng.wang@arm.com> <20190906094534.36060-2-ruifeng.wang@arm.com> In-Reply-To: <20190906094534.36060-2-ruifeng.wang@arm.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ts-tracking-id: 0e1685ed-eb5d-49b8-8d18-108108f53bbd.1 x-checkrecipientchecked: true Authentication-Results-Original: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email X-MS-Office365-Filtering-Correlation-Id: 88a22f72-b2b8-4dd3-7f1d-08d73302a384 X-MS-Office365-Filtering-HT: Tenant X-Microsoft-Antispam-Untrusted: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600166)(711020)(4605104)(1401327)(4618075)(2017052603328)(7193020); SRVR:VE1PR08MB4976; X-MS-TrafficTypeDiagnostic: VE1PR08MB4976:|VE1PR08MB4976:|AM0PR08MB5281: x-ms-exchange-transport-forked: True X-Microsoft-Antispam-PRVS: x-checkrecipientrouted: true x-ms-oob-tlc-oobclassifiers: OLM:7691;OLM:7691; x-forefront-prvs: 0152EBA40F X-Forefront-Antispam-Report-Untrusted: SFV:NSPM; SFS:(10009020)(4636009)(346002)(136003)(366004)(376002)(39860400002)(396003)(199004)(189003)(13464003)(4326008)(2201001)(86362001)(66066001)(5660300002)(25786009)(446003)(76176011)(11346002)(476003)(2501003)(486006)(14444005)(71200400001)(6246003)(71190400001)(14454004)(256004)(478600001)(99286004)(66476007)(7696005)(6506007)(53546011)(102836004)(52536014)(66946007)(64756008)(26005)(66446008)(186003)(53936002)(66556008)(55016002)(6436002)(81166006)(81156014)(8936002)(8676002)(74316002)(305945005)(110136005)(54906003)(3846002)(6116002)(2906002)(9686003)(76116006)(316002)(229853002)(33656002)(7736002); DIR:OUT; SFP:1101; SCL:1; SRVR:VE1PR08MB4976; H:VE1PR08MB5149.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-Original: ZxG7K1IngpcBZxumWy/33o8BM+WvvUILqLgK7lgDLg8zFhGfH4aN5r4B/dAbZcVnwMHpeANvF6MfuJnGvTndkNzTAlqXZPTSeL4d23kt19fEvR8zEgMJkduX1MovD+DeYpWrkBMOaXaGQu8QFtpeJQ20eJG9dMEXfZngw6MqW1/Utm5VwDxIvVRzHIuUmLznSOmw6w1rrthIf32/+fl2A6dXtBDGudeWbwas+IRrlvhi8UGKenCZG9AwHHCX5C9S4XgULYYct162kGg46iVZfJtOjFLL7sOw/igXDjlKF17Vz+jBkT62Aq9umf4LnpDCLnLCc+GrrFSl8mpf7iLeF+Wcl/xoReblKVxeocqwdmEZRZj9wWaSRhEHAxd/VB/ADW56Y+FQ6jq9pBsdCgbn0y8PcgThV92EMWOiCNHodao= Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: VE1PR08MB4976 Original-Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: VE1EUR03FT060.eop-EUR03.prod.protection.outlook.com X-Forefront-Antispam-Report: CIP:63.35.35.123; IPV:CAL; SCL:-1; CTRY:IE; EFV:NLI; SFV:NSPM; SFS:(10009020)(4636009)(396003)(346002)(39860400002)(376002)(136003)(2980300002)(13464003)(199004)(189003)(55016002)(76176011)(7696005)(9686003)(76130400001)(36906005)(478600001)(14444005)(186003)(316002)(4326008)(110136005)(6246003)(2201001)(14454004)(26826003)(2501003)(11346002)(47776003)(8746002)(8936002)(63350400001)(63370400001)(446003)(66066001)(336012)(81156014)(8676002)(33656002)(81166006)(5660300002)(126002)(476003)(486006)(22756006)(356004)(7736002)(102836004)(99286004)(23726003)(26005)(2906002)(70206006)(74316002)(50466002)(46406003)(97756001)(305945005)(3846002)(6116002)(25786009)(54906003)(53546011)(6506007)(70586007)(229853002)(52536014)(86362001); DIR:OUT; SFP:1101; SCL:1; SRVR:AM0PR08MB5281; H:64aa7808-outbound-1.mta.getcheckrecipient.com; FPR:; SPF:TempError; LANG:en; PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com; A:1; MX:1; X-MS-Office365-Filtering-Correlation-Id-Prvs: ad959017-b3cc-4832-a7e2-08d733029c99 X-Microsoft-Antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600166)(710020)(711020)(4605104)(1401327)(4618075)(2017052603328)(7193020); SRVR:AM0PR08MB5281; NoDisclaimer: True X-Forefront-PRVS: 0152EBA40F X-Microsoft-Antispam-Message-Info: 0E05B7xGwnDc6fJSacOl2uH8yf38CioBiEAaTimktZHF4VaZdyPV9B7tVA+nT2u3eN9jzHFRMTsHVY4lZA7mJxsZNOMPOsoTdqltane0IyeGkK3qePG9Qd8w0UK8vZ15r6mP86JURvUEcmHSwJaMTrQvqzVdDfA0QXlRIfLcLzNKDNwAUq8HMTdotb0odJEg4SVQ9CFeo+j+UykqZI89EXLVYZonWtvDuDetlvOx+/vhQ/NvLcY6LC7dwdE+R8ObUZnZ6+YHtLeQytj0Sep40yHeMx+N/0F4DYQuNZzfpCsTFg5HVGoEz7dwujuyRurJyRl0T7Js6l84Ez52LwTElCmgWiDcuuUJlfyNPHooU3zrlAZUEoJ/NJLuslx/nSru8DS3eu/QZLj+uJWEhv3bd2Khg03hasZU71AwEHNV8dA= X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 Sep 2019 19:44:32.1144 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 88a22f72-b2b8-4dd3-7f1d-08d73302a384 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[63.35.35.123]; Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM0PR08MB5281 Subject: Re: [dpdk-dev] [PATCH v2 1/6] doc/rcu: add RCU integration design details 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" Adding Paul for feedback on design > -----Original Message----- > From: Ruifeng Wang > Sent: Friday, September 6, 2019 4:45 AM > To: bruce.richardson@intel.com; vladimir.medvedkin@intel.com; > olivier.matz@6wind.com > Cc: dev@dpdk.org; stephen@networkplumber.org; > konstantin.ananyev@intel.com; Gavin Hu (Arm Technology China) > ; Honnappa Nagarahalli > ; Dharmik Thakkar > ; nd > Subject: [PATCH v2 1/6] doc/rcu: add RCU integration design details >=20 > From: Honnappa Nagarahalli >=20 > Add a section to describe a design to integrate QSBR RCU library with oth= er > libraries in DPDK. >=20 > Signed-off-by: Honnappa Nagarahalli > --- > doc/guides/prog_guide/rcu_lib.rst | 52 +++++++++++++++++++++++++++++++ > 1 file changed, 52 insertions(+) >=20 > diff --git a/doc/guides/prog_guide/rcu_lib.rst > b/doc/guides/prog_guide/rcu_lib.rst > index 8fe5b1f73..211948530 100644 > --- a/doc/guides/prog_guide/rcu_lib.rst > +++ b/doc/guides/prog_guide/rcu_lib.rst > @@ -186,3 +186,55 @@ However, when > ``CONFIG_RTE_LIBRTE_RCU_DEBUG`` is enabled, these APIs aid in debugging > issues. One can mark the access to shared data structures on the reader = side > using these APIs. The ``rte_rcu_qsbr_quiescent()`` will check if all the= locks are > unlocked. > + > +Integrating QSBR RCU with other libraries > +----------------------------------------- > + > +Lock-free algorithms place additional burden on the application to > +reclaim memory. Integrating memory reclamation mechanisms in the > +libraries help remove some of the burden. Though QSBR method presents > +flexibility to achieve performance, it presents challenges while integra= ting > with libraries. > + > +The memory reclamation process using QSBR can be split into 4 parts: > + > +#. Initialization > +#. Quiescent State Reporting > +#. Reclaiming Resources > +#. Shutdown > + > +The design proposed here assigns different parts of this process to clie= nt > libraries and applications. The term 'client library' refers to data stru= cture > libraries such at rte_hash, rte_lpm etc. in DPDK or similar libraries out= side of > DPDK. The term 'application' refers to the packet processing application = that > makes use of DPDK such as L3 Forwarding example application, OVS, VPP etc= .. > + > +The application has to handle 'Initialization' and 'Quiescent State > +Reporting'. So, > + > +* the application has to create the RCU variable and register the reader > threads to report their quiescent state. > +* the application has to register the same RCU variable with the client = library. > +* reader threads in the application have to report the quiescent state. = This > allows for the application to control the length of the critical section/= how > frequently the application wants to report the quiescent state. > + > +The client library will handle 'Reclaiming Resources' part of the > +process. The client libraries will make use of the writer thread > +context to execute the memory reclamation algorithm. So, > + > +* client library should provide an API to register a RCU variable that i= t will use. > +* client library should trigger the readers to report quiescent state st= atus > upon deleting the resources by calling ``rte_rcu_qsbr_start``. > + > +* client library should store the token and deleted resources for later = use to > free them after the readers have reported their quiescent state. Since th= e > readers will report the quiescent state status in the order of deletion, = the > library must store the tokens/resources in the order in which the resourc= es > were deleted. A FIFO data structure would achieve the desired results. Th= e > length of the FIFO would depend on the rate of deletion and the rate at w= hich > the readers report their quiescent state. In the worst case the length of= FIFO > would be equal to the maximum number of resources the data structure > supports. However, in most cases, the length will be much smaller. But, t= he > client library should not take the length of FIFO as an input from the > application. Instead, it should implement a data structure which should b= e able > to grow/shrink dynamically. Overhead introduced by such a data structure = on > delete operations should be considered as well. > + > +* client library should query the quiescent state and free the resources= . It > should make use of non-blocking ``rte_rcu_qsbr_check`` API to query the > quiescent state. This allows the application to do useful work while the = readers > report their quiescent state. If there are tokens/resources present in th= e FIFO > already, the delete API should peek the head of the FIFO and check the > quiescent state status. If the status is success, the token/resource shou= ld be > dequeued and the resource should be freed. This process can be repeated t= ill > the quiescent state status for a token returns failure indicating that > subsequent tokens will also fail quiescent state status query. The same p= rocess > can be incorporated while adding new entries in the data structure if the= client > library runs out of resources. > + > +The 'Shutdown' process needs to be shared between the application and > +the client library. > + > +* the application should make sure that the reader threads are not using= the > shared data structure, unregister the reader threads from the QSBR variab= le > before calling the client library's shutdown function. > + > +* client library should check the quiescent state status of all the toke= ns that > may be present in the FIFO and free the resources. It should make use of = non- > blocking ``rte_rcu_qsbr_check`` API to query the quiescent state. If any = of the > tokens do not pass the quiescent state check, the client library should p= rint an > error and stop the memory reclamation process. > + > +Integrating the resource reclamation with client libraries removes the > +burden from the application and makes it easy to use lock-free algorithm= s. > + > +This design has several advantages over currently known methods. > + > +#. Application does not need a dedicated thread to reclaim resources. > Memory > + reclamation happens as part of the writer thread with little impact o= n > + performance. > +#. The client library has better control over the resources. For ex: the= client > + library can attempt to reclaim when it has run out of resources. > -- > 2.17.1