From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <i.maximets@samsung.com>
Received: from mailout2.w1.samsung.com (mailout2.w1.samsung.com
[210.118.77.12]) by dpdk.org (Postfix) with ESMTP id 631C31B1F3
for <dev@dpdk.org>; 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 <dev@dpdk.org>; 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 <thomas@monjalon.net>, Ferruh Yigit
<ferruh.yigit@intel.com>
From: Ilya Maximets <i.maximets@samsung.com>
Message-ID: <e6711e90-db18-58e1-a22d-f4fc96dd28df@samsung.com>
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>
<CGME20181122073110eucas1p17592400af6c0b807dc87e90d136575af@eucas1p1.samsung.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 <dev.dpdk.org>
List-Unsubscribe: <https://mails.dpdk.org/options/dev>,
<mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://mails.dpdk.org/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <https://mails.dpdk.org/listinfo/dev>,
<mailto:dev-request@dpdk.org?subject=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