From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mailout2.w1.samsung.com (mailout2.w1.samsung.com [210.118.77.12]) by dpdk.org (Postfix) with ESMTP id 631C31B1F3 for ; Thu, 22 Nov 2018 08:31:13 +0100 (CET) Received: from eucas1p1.samsung.com (unknown [182.198.249.206]) by mailout2.w1.samsung.com (KnoxPortal) with ESMTP id 20181122073111euoutp025030b0c007c34eff798feeec04bacc92~pYcr7Uuvs0565905659euoutp02t for ; Thu, 22 Nov 2018 07:31:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 mailout2.w1.samsung.com 20181122073111euoutp025030b0c007c34eff798feeec04bacc92~pYcr7Uuvs0565905659euoutp02t DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=samsung.com; s=mail20170921; t=1542871871; bh=CoNgO/lVqyZb9TvexXvOkXNfBkrE9i3aOPCYNda9F1o=; h=To:Subject:Cc:From:Date:In-Reply-To:References:From; b=Ml9hFHwbkJbgpiwxP4kQOEkh8oJ2G9Ac2BMK66mWnmHR1Hcsgpmt64qNwjk97UdLU gzSbndoGrD340V2c8rNRw2sg6pGFzR3k/gL7yXsT9O6BUH6c1ZobL9dwglpI2A4+K6 oC3Qfl4XoODwephKIy6cPB0J6UsZWgGS1N41z188= Received: from eusmges1new.samsung.com (unknown [203.254.199.242]) by eucas1p1.samsung.com (KnoxPortal) with ESMTP id 20181122073111eucas1p12205f97e1357cac2e54e80f0a602a7d6~pYcrZglEg1737817378eucas1p1x; Thu, 22 Nov 2018 07:31:11 +0000 (GMT) Received: from eucas1p1.samsung.com ( [182.198.249.206]) by eusmges1new.samsung.com (EUCPMTA) with SMTP id BF.EF.04441.E3B56FB5; Thu, 22 Nov 2018 07:31:10 +0000 (GMT) Received: from eusmtrp1.samsung.com (unknown [182.198.249.138]) by eucas1p1.samsung.com (KnoxPortal) with ESMTPA id 20181122073110eucas1p17592400af6c0b807dc87e90d136575af~pYcqnTCzS0979309793eucas1p1j; Thu, 22 Nov 2018 07:31:10 +0000 (GMT) Received: from eusmgms1.samsung.com (unknown [182.198.249.179]) by eusmtrp1.samsung.com (KnoxPortal) with ESMTP id 20181122073110eusmtrp1b7af57a0cbb6449b2f46d30e2d480669~pYcqXlZf01249912499eusmtrp1F; Thu, 22 Nov 2018 07:31:10 +0000 (GMT) X-AuditID: cbfec7f2-5c9ff70000001159-12-5bf65b3ed20c Received: from eusmtip2.samsung.com ( [203.254.199.222]) by eusmgms1.samsung.com (EUCPMTA) with SMTP id 75.D8.04284.E3B56FB5; Thu, 22 Nov 2018 07:31:10 +0000 (GMT) Received: from [106.109.129.180] (unknown [106.109.129.180]) by eusmtip2.samsung.com (KnoxPortal) with ESMTPA id 20181122073109eusmtip2024a53ac4f82052594aef9184abbe3f0~pYcqD5x5P1052210522eusmtip2E; Thu, 22 Nov 2018 07:31:09 +0000 (GMT) To: dev@dpdk.org Cc: Thomas Monjalon , Ferruh Yigit From: Ilya Maximets Message-ID: Date: Thu, 22 Nov 2018 10:31:08 +0300 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 MIME-Version: 1.0 In-Reply-To: <20181122033055.3431-1-honnappa.nagarahalli@arm.com> Content-Language: en-GB Content-Transfer-Encoding: 7bit X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFprGKsWRmVeSWpSXmKPExsWy7djPc7p20d+iDWauMrd492k7k8WdvafZ La60/2S3+PTgBIsDi8evBUtZPRbvecnkcezmNHaPvi2rGANYorhsUlJzMstSi/TtErgytj67 wV6ww75i451J7A2M/fpdjJwcEgImEt0bt7J2MXJxCAmsYJRYf+A9I4TzhVHixLo/TBDOZ0aJ Gz8escO0tHw6AWYLCSxnlOid7wpR9JFR4uSUmywgCREBAYnPnYvZQGxhAU+JK58WMYLYzAJB Emfut4LF2QR0JE6tPgIW5xWwk1ix/SHQUA4OFgFVia0LVUDCogIREh33V7NBlAhKnJz5BGw8 p4CjxOvr25ggRopLNH1ZyQphy0tsfzuHGeQeCYHJ7BIHP71jhjjaRWL/gxYmCFtY4tXxLVDP yEicntzDAmHXS9xveckI0dzBKDH90D+oBnuJLa/PgR3HLKApsX4XNOwcJaa9fA4WlhDgk7jx VhDiBj6JSdumM0OEeSU62oQgqlUkfh9cDnWNlMTNd5/ZJzAqzULy2Swk38xC8s0shL0LGFlW MYqnlhbnpqcWG+allusVJ+YWl+al6yXn525iBKaW0/+Of9rB+PVS0iFGAQ5GJR5ejciv0UKs iWXFlbmHGCU4mJVEeC87fosW4k1JrKxKLcqPLyrNSS0+xCjNwaIkzlvN8CBaSCA9sSQ1OzW1 ILUIJsvEwSnVwOgkuPVLh/DKw0sUFrY1TNCMeif9OFzY4kNRo+6MuNacin1+RZFKPWuZfkjK q/L1n+/65WLN+n2hguAu5nUMhVa/ZN4Zix7yl0qwF6/gLFY6E2W9e08yC6/4de3mreLbokyE EizuN8+S/7elZMOLtAlrvZvEbj6/+J/zxbyO0NBHPIJ8WrM8lViKMxINtZiLihMBou0fcykD AAA= X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrBIsWRmVeSWpSXmKPExsVy+t/xe7p20d+iDb4+ZbF492k7k8WdvafZ La60/2S3+PTgBIsDi8evBUtZPRbvecnkcezmNHaPvi2rGANYovRsivJLS1IVMvKLS2yVog0t jPQMLS30jEws9QyNzWOtjEyV9O1sUlJzMstSi/TtEvQytj67wV6ww75i451J7A2M/fpdjJwc EgImEi2fTrCD2EICSxklbv+qg4hLSfz4dYEVwhaW+HOti62LkQuo5j2jxMT/P1lAEiICAhKf OxezQTQ7SGye1QAWFxbwlLjyaREjiM0sECTx7s5RJhCbTUBH4tTqI2BxXgE7iRXbHwIt5uBg EVCV2LpQBSQsKhAhcfblOqgSQYmTM5+AjeQUcJR4fX0bE8RIdYk/8y4xQ9jiEk1fVrJC2PIS 29/OYZ7AKDQLSfssJC2zkLTMQtKygJFlFaNIamlxbnpusaFecWJucWleul5yfu4mRmAsbTv2 c/MOxksbgw8xCnAwKvHwakR+jRZiTSwrrsw9xCjBwawkwnvZ8Vu0EG9KYmVValF+fFFpTmrx IUZToN8mMkuJJucD4zyvJN7Q1NDcwtLQ3Njc2MxCSZz3vEFllJBAemJJanZqakFqEUwfEwen VANjmvUDFdXi04/PP3CffyQ+W3j7eTWRF0ZOCv/n3c0zucZ4u+aOO4Ol0r+FVTJ5x/Ovbph/ 4eP5uqv5exI4LHj2+GyM+W/xeXHbhYNGSconJy7Z/owvit+Owcv+flDW2SWvveP2BTK8vD/R 7utV8T0Pn69Zs65e+uY373a11A7NOTx3L3LOiejpVWIpzkg01GIuKk4EALJ+PfW7AgAA X-CMS-MailID: 20181122073110eucas1p17592400af6c0b807dc87e90d136575af X-Msg-Generator: CA Content-Type: text/plain; charset="utf-8" X-RootMTR: 20181122073110eucas1p17592400af6c0b807dc87e90d136575af X-EPHeader: CA CMS-TYPE: 201P X-CMS-RootMailID: 20181122073110eucas1p17592400af6c0b807dc87e90d136575af References: <20181122033055.3431-1-honnappa.nagarahalli@arm.com> Subject: Re: [dpdk-dev] [RFC 0/3] tqs: add thread quiescent state library 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: Thu, 22 Nov 2018 07:31:13 -0000 Hi. Is the any differentiation points with liburcu [1] ? Is there any profit having own implementation inside DPDK ? [1] http://liburcu.org/ https://lwn.net/Articles/573424/ Best regards, Ilya Maximets. > 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 simultaneously. 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 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: in this step, the writer returns the memory to the > memory allocator, only after knowing that all the readers have stopped > referencing the removed element. > > This library helps the writer determine when it is safe to free the > memory. > > This library makes use of Thread Quiescent State (TQS). TQS 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: > > Time --------------------------------------------------> > > | | > RT1 $++++****D1****+++***D2*|**+++|+++**D3*****++++$ > | | > RT2 $++++****D1****++|+**D2|***++++++**D3*****++++$ > | | > RT3 $++++****D1****+++***|D2***|++++++**D2*****++++$ > | | > |<--->| > Del | Free > | > Cannot free memory > during this period > > RTx - Reader thread > < and > - Start and end of while(1) loop > ***Dx*** - Reader thread is accessing the shared data structure Dx. > i.e. critical section. > +++ - Reader thread is not accessing any shared data structure. > i.e. non critical section or quiescent state. > Del - Point in time when the reference to the entry is removed using > atomic operation. > Free - Point in time when the writer can free the entry. > > As shown thread RT1 acesses data structures D1, D2 and D3. When it is > accessing D2, if the writer has to remove an element from D2, the > writer cannot return the memory associated with that element to the > allocator. The writer can return the memory to the allocator only after > the reader stops referencng D2. In other words, reader thread RT1 > has to enter a quiescent state. > > Similarly, since thread RT3 is also accessing D2, writer has to wait till > RT3 enters quiescent state as well. > > However, the writer does not need to wait for RT2 to enter quiescent state. > Thread RT2 was not accessing D2 when the delete operation happened. > So, RT2 will not get a reference to the deleted entry. > > It can be noted that, the critical sections for D2 and D3 are quiescent states > 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. > > For DPDK applications, the start and end of while(1) loop (where no shared > data structures are getting accessed) act as perfect quiescent states. This > will combine all the shared data structure accesses into a single critical > section and keeps the over head introduced by this library to the minimum. > > However, the length of the critical section and the number of reader threads > is proportional to the time taken to identify the end of critical section. > So, if the application desires, it should be possible to identify the end > of critical section for each data structure. > > To provide the required flexibility, this library has a concept of TQS > variable. The application can create one or more TQS variables to help it > track the end of one or more critical sections. > > The application can create a TQS variable using the API rte_tqs_alloc. > It takes a mask of lcore IDs that will report their quiescent states > using this variable. This mask can be empty to start with. > > rte_tqs_register_lcore API will register a reader thread to report its > quiescent state. This can be called from any control plane thread or from > the reader thread. The application can create a TQS variable with no reader > threads and add the threads dynamically using this API. > > The application can trigger the reader threads to report their quiescent > state status by calling the API rte_tqs_start. It is possible for multiple > writer threads to query the quiescent state status simultaneously. Hence, > rte_tqs_start returns a token to each caller. > > The application has to call rte_tqs_check API with the token to get the > current status. Option to block till all the threads enter the quiescent > state is provided. If this API indicates that all the threads have entered > the quiescent state, the application can free the deleted entry. > > The separation of triggering the reporting from querying the status provides > the writer threads flexibility to do useful work instead of waiting for the > reader threads to enter the quiescent state. > > rte_tqs_unregister_lcore API will remove a reader thread from reporting its > quiescent state using a TQS variable. The rte_tqs_check API will not wait > for this reader thread to report the quiescent state status anymore. > > Finally, a TQS variable can be deleted by calling rte_tqs_free API. > Application must make sure that the reader threads are not referencing the > TQS variable anymore before deleting it. > > The reader threads should call rte_tqs_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. > > Next Steps: > 1) Add more test cases > 2) Convert to patch > 3) Incorporate feedback from community > 4) Add documentation > > Dharmik Thakkar (1): > test/tqs: Add API and functional tests > > Honnappa Nagarahalli (2): > log: add TQS log type > tqs: add thread quiescent state library > > config/common_base | 6 + > lib/Makefile | 2 + > lib/librte_eal/common/include/rte_log.h | 1 + > lib/librte_tqs/Makefile | 23 + > lib/librte_tqs/meson.build | 5 + > lib/librte_tqs/rte_tqs.c | 249 +++++++++++ > lib/librte_tqs/rte_tqs.h | 352 +++++++++++++++ > lib/librte_tqs/rte_tqs_version.map | 16 + > lib/meson.build | 2 +- > mk/rte.app.mk | 1 + > test/test/Makefile | 2 + > test/test/autotest_data.py | 6 + > test/test/meson.build | 5 +- > test/test/test_tqs.c | 540 ++++++++++++++++++++++++ > 14 files changed, 1208 insertions(+), 2 deletions(-) > create mode 100644 lib/librte_tqs/Makefile > create mode 100644 lib/librte_tqs/meson.build > create mode 100644 lib/librte_tqs/rte_tqs.c > create mode 100644 lib/librte_tqs/rte_tqs.h > create mode 100644 lib/librte_tqs/rte_tqs_version.map > create mode 100644 test/test/test_tqs.c > > -- > 2.17.1