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 43ADCA2F6B for ; Wed, 9 Oct 2019 06:25:57 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 382E61C0AF; Wed, 9 Oct 2019 06:25:56 +0200 (CEST) Received: from EUR03-DB5-obe.outbound.protection.outlook.com (mail-eopbgr40055.outbound.protection.outlook.com [40.107.4.55]) by dpdk.org (Postfix) with ESMTP id B2D111C0AE for ; Wed, 9 Oct 2019 06:25:54 +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=7KMfWmTMdLciEhkL90P66fafu5nn9pTiw5qelhI3WGk=; b=HJ7yK8xpu7LpSp1S3afrZ0I1bm49GjLj6QfRV/5d7RPj9OKnpMeK93d52f0/BHBEAVtQxgpezD5mPfrIJucRhznjAXbav+SjpSR+e0yIWaAA9ESSBu61Ei4f3M8rqYfRJR8UKhjsueVISAHg2h8tX5R0EFgWQ+c0rrWKU5VrWCw= Received: from DB7PR08CA0029.eurprd08.prod.outlook.com (2603:10a6:5:16::42) by AM5PR0801MB1859.eurprd08.prod.outlook.com (2603:10a6:203:49::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2327.24; Wed, 9 Oct 2019 04:25:52 +0000 Received: from VE1EUR03FT054.eop-EUR03.prod.protection.outlook.com (2a01:111:f400:7e09::203) by DB7PR08CA0029.outlook.office365.com (2603:10a6:5:16::42) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.2284.20 via Frontend Transport; Wed, 9 Oct 2019 04:25:51 +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=none 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 VE1EUR03FT054.mail.protection.outlook.com (10.152.19.64) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.2305.15 via Frontend Transport; Wed, 9 Oct 2019 04:25:50 +0000 Received: ("Tessian outbound 3fba803f6da3:v33"); Wed, 09 Oct 2019 04:25:45 +0000 X-CR-MTA-TID: 64aa7808 Received: from 8cb1e3ecd78f.2 (ip-172-16-0-2.eu-west-1.compute.internal [104.47.12.53]) by 64aa7808-outbound-1.mta.getcheckrecipient.com id 665FD306-AAB8-4D6A-B63D-B64A7F09665A.1; Wed, 09 Oct 2019 04:25:39 +0000 Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-db3eur04lp2053.outbound.protection.outlook.com [104.47.12.53]) by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 8cb1e3ecd78f.2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384); Wed, 09 Oct 2019 04:25:39 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=MJi/aFSCMr5W2Bhj1ClMuU8hi2O7Re8137gxIfGjfNjfJ80nwUXSkriSTTFSLUnBpH0xPn1XAzNgxVbe+otNs/GTQBXoBtjwYY9meVDHdiprT1hek8352xDPaWKUPgOXoyTRC3mAbkHXdmK0/lf7LOnLW9i3IZhl3CJUFVzpjvYJcg1fxMFBvtLgz1ymncivJtnUjxlStOmWvlG6a5hlln2E5T4qbqYkzlLDogNBYg3FqrPWXqWVcE3CEoBB6fcW1am3CV/cSID5kJxbhyd035APc1CLL5isNYpyJDA/yRD1xuzcZ50q+GOla8XHDdAtHChatXyrXrhBET+M0YSUvg== 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=7KMfWmTMdLciEhkL90P66fafu5nn9pTiw5qelhI3WGk=; b=lcfikTn6GQFZu5tbxIwSSlBSrfnitWFNwLd7L2dRaLnnE1ntZ+L8m63U/Jx6lOnm5MDdoI7ECXbAOVYALl8+00xZBCWIucZqGU0RUR1cax1l7OlPyUPYsqjrZ1Jse34/uZTS9lCcPBKUOAQ2a0/NQDIrrUQ5OlYA61V3aj0n/Vg8nq28Cu2IdgTR0vez7Wq4wjI6qdWKGDB2o7tnI/3y5DlnUmN2cKVbpJsPoJwJJlF9oSIZafQz37Agsb6UDG1BbJeCBQoXDqaLtiLLQVRxqGvqJVuvrjQHnHIm5l4DLL1zD5PxXPitKBOpntemkjz7cVRPWkHHtPBr3BrekMiJlA== 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=7KMfWmTMdLciEhkL90P66fafu5nn9pTiw5qelhI3WGk=; b=HJ7yK8xpu7LpSp1S3afrZ0I1bm49GjLj6QfRV/5d7RPj9OKnpMeK93d52f0/BHBEAVtQxgpezD5mPfrIJucRhznjAXbav+SjpSR+e0yIWaAA9ESSBu61Ei4f3M8rqYfRJR8UKhjsueVISAHg2h8tX5R0EFgWQ+c0rrWKU5VrWCw= Received: from VE1PR08MB5149.eurprd08.prod.outlook.com (20.179.30.27) by VE1PR08MB5230.eurprd08.prod.outlook.com (10.255.113.213) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2327.24; Wed, 9 Oct 2019 04:25:38 +0000 Received: from VE1PR08MB5149.eurprd08.prod.outlook.com ([fe80::8c82:8d9c:c78d:22a6]) by VE1PR08MB5149.eurprd08.prod.outlook.com ([fe80::8c82:8d9c:c78d:22a6%7]) with mapi id 15.20.2327.026; Wed, 9 Oct 2019 04:25:38 +0000 From: Honnappa Nagarahalli To: "Ananyev, Konstantin" , "stephen@networkplumber.org" , "paulmck@linux.ibm.com" CC: "Wang, Yipeng1" , "Medvedkin, Vladimir" , "Ruifeng Wang (Arm Technology China)" , Dharmik Thakkar , "dev@dpdk.org" , Honnappa Nagarahalli , nd , nd Thread-Topic: [PATCH v3 1/3] lib/ring: add peek API Thread-Index: AQHVeVEbQBVWnKnBNky5vPA5w4G8vadIeNrQgAZwDgCAAs5McA== Date: Wed, 9 Oct 2019 04:25:37 +0000 Message-ID: References: <20190906094534.36060-1-ruifeng.wang@arm.com> <20191001062917.35578-1-honnappa.nagarahalli@arm.com> <20191001062917.35578-2-honnappa.nagarahalli@arm.com> <2601191342CEEE43887BDE71AB9772580191970014@irsmsx105.ger.corp.intel.com> <2601191342CEEE43887BDE71AB9772580191971EBE@irsmsx105.ger.corp.intel.com> In-Reply-To: <2601191342CEEE43887BDE71AB9772580191971EBE@irsmsx105.ger.corp.intel.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ts-tracking-id: 72941e53-712f-4b91-ae8c-818bb1473dd9.0 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: c59e4fa6-08d9-4c80-4053-08d74c70c423 X-MS-Office365-Filtering-HT: Tenant X-MS-TrafficTypeDiagnostic: VE1PR08MB5230:|VE1PR08MB5230:|AM5PR0801MB1859: x-ms-exchange-transport-forked: True X-Microsoft-Antispam-PRVS: x-checkrecipientrouted: true x-ms-oob-tlc-oobclassifiers: OLM:1728;OLM:1728; x-forefront-prvs: 018577E36E X-Forefront-Antispam-Report-Untrusted: SFV:NSPM; SFS:(10009020)(4636009)(396003)(39860400002)(366004)(136003)(346002)(376002)(189003)(199004)(64756008)(66066001)(76116006)(8936002)(66446008)(66946007)(5660300002)(81166006)(81156014)(8676002)(256004)(2906002)(6116002)(3846002)(6506007)(2201001)(71200400001)(86362001)(66556008)(52536014)(66476007)(4326008)(14444005)(71190400001)(476003)(446003)(486006)(186003)(14454004)(7736002)(11346002)(2501003)(33656002)(6246003)(305945005)(6436002)(229853002)(102836004)(478600001)(26005)(76176011)(7696005)(74316002)(99286004)(54906003)(110136005)(25786009)(316002)(55016002)(9686003); DIR:OUT; SFP:1101; SCL:1; SRVR:VE1PR08MB5230; H:VE1PR08MB5149.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) X-MS-Exchange-SenderADCheck: 1 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: 28zW7wi8xAAxkyAqlszcugMrDUETyV662QvmbnWRw/Vy95jhH5BrS30YSVOoOgkVHLM9cWIZCt19/vcdfJXcKPQP4Akrp+dvFqVja0O2HejbOQgpYZvCtty1X2CWzz5v6GAYefltHvWlxYOwBY5NsKik4IJMOh3KhXlO3GVl7H/Pkd8+P6/Y3jazixdptGg0LjHRFPn/MBTQZsQGjVuPr96T5wb9+A/ILt/MdFbVobVgDtHzgtFRRiL+M2KTStQmPeoBXfAmCcvocntFMU8pMGvYhS70R2Jc0FcEHwoHTuxWljuUF8ZuOgZE/evUxsrVF8KXAAKVNuSHpphyjO2BsLT+9bSGJHWYnVY2S5yAmb+gJTAAWJTp4RmJoWAYDBwoFpMea0/8lv5dg0OS1ZrE8Ot5/6zaK7fxr3KWqkXR+LM= Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: VE1PR08MB5230 Original-Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: VE1EUR03FT054.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)(39860400002)(376002)(346002)(136003)(199004)(189003)(26005)(478600001)(23726003)(26826003)(126002)(8936002)(70206006)(81166006)(7736002)(356004)(8746002)(14444005)(76130400001)(6116002)(3846002)(9686003)(2201001)(336012)(14454004)(8676002)(186003)(66066001)(11346002)(4326008)(446003)(486006)(47776003)(476003)(81156014)(86362001)(229853002)(33656002)(63350400001)(6246003)(2906002)(7696005)(76176011)(99286004)(25786009)(102836004)(70586007)(36906005)(5660300002)(6506007)(305945005)(74316002)(22756006)(46406003)(110136005)(52536014)(55016002)(50466002)(54906003)(316002)(97756001)(2501003); DIR:OUT; SFP:1101; SCL:1; SRVR:AM5PR0801MB1859; 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: c63b4422-9d68-4a76-43c0-08d74c70bcac NoDisclaimer: True X-Forefront-PRVS: 018577E36E X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: CCKK+6itJY2j/hEMJAsBueGJ3xhJEwKWGZNynO1BSpkhdfy2IEwpJjlr7xuy4UtzHc748fXIWA5Va+yXSbHVXL9t/dQzAS9BR0VgCclFVCOtrDJNydKYLuwAahtwSr3E2C+u5NfJJRPhtZ8OD6Hj72u1sHD3RL61wlWd8L4GYtqKwdSct/cZab5gVtJ3d1Z5wP+zUmBSjjP0aY1m3H/O9JyVOgzJ/vGScSY5Z6SbVf1X1gEaOCe51ZbKEM0zXCCIZecrgJZnaF8qKl5mhG4QF0+e9W9aH1I6fQ3HMU9Wj6Qtu7+bAPgJb5u3xxihrr3GXCmJzflkTQPx8biUNTjFzcTgO+XPJeemYSmua11qmYq34HUYgTIOqJ4IfuRXs5PWuDniAFbEGeFIo5s4UYfb/JjEIg1BOUEV18JPz7JShWc= X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 09 Oct 2019 04:25:50.5496 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: c59e4fa6-08d9-4c80-4053-08d74c70c423 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: AM5PR0801MB1859 Subject: Re: [dpdk-dev] [PATCH v3 1/3] lib/ring: add peek API 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" >=20 > > > > > > Subject: [PATCH v3 1/3] lib/ring: add peek API > > > > > > > > From: Ruifeng Wang > > > > > > > > The peek API allows fetching the next available object in the ring > > > > without dequeuing it. This helps in scenarios where dequeuing of > > > > objects depend on their value. > > > > > > > > Signed-off-by: Dharmik Thakkar > > > > Signed-off-by: Ruifeng Wang > > > > Reviewed-by: Honnappa Nagarahalli > > > > Reviewed-by: Gavin Hu > > > > --- > > > > lib/librte_ring/rte_ring.h | 30 ++++++++++++++++++++++++++++++ > > > > 1 file changed, 30 insertions(+) > > > > > > > > diff --git a/lib/librte_ring/rte_ring.h > > > > b/lib/librte_ring/rte_ring.h index 2a9f768a1..d3d0d5e18 100644 > > > > --- a/lib/librte_ring/rte_ring.h > > > > +++ b/lib/librte_ring/rte_ring.h > > > > @@ -953,6 +953,36 @@ rte_ring_dequeue_burst(struct rte_ring *r, > > > > void > > > **obj_table, > > > > r->cons.single, available); > > > > } > > > > > > > > +/** > > > > + * Peek one object from a ring. > > > > + * > > > > + * The peek API allows fetching the next available object in the > > > > +ring > > > > + * without dequeuing it. This API is not multi-thread safe with > > > > +respect > > > > + * to other consumer threads. > > > > + * > > > > + * @param r > > > > + * A pointer to the ring structure. > > > > + * @param obj_p > > > > + * A pointer to a void * pointer (object) that will be filled. > > > > + * @return > > > > + * - 0: Success, object available > > > > + * - -ENOENT: Not enough entries in the ring. > > > > + */ > > > > +__rte_experimental > > > > +static __rte_always_inline int > > > > +rte_ring_peek(struct rte_ring *r, void **obj_p) > > > > > > As it is not MT safe, then I think we need _sc_ in the name, to > > > follow other rte_ring functions naming conventions > > > (rte_ring_sc_peek() or so). > > Agree > > > > > > > > As a better alternative what do you think about introducing a > > > serialized versions of DPDK rte_ring dequeue functions? > > > Something like that: > > > > > > /* same as original ring dequeue, but: > > > * 1) move cons.head only if cons.head =3D=3D const.tail > > > * 2) don't update cons.tail > > > */ > > > unsigned int > > > rte_ring_serial_dequeue_bulk(struct rte_ring *r, void **obj_table, > > > unsigned int n, > > > unsigned int *available); > > > > > > /* sets both cons.head and cons.tail to cons.head + num */ void > > > rte_ring_serial_dequeue_finish(struct rte_ring *r, uint32_t num); > > > > > > /* resets cons.head to const.tail value */ void > > > rte_ring_serial_dequeue_abort(struct rte_ring *r); > > > > > > Then your dq_reclaim cycle function will look like that: > > > > > > const uint32_t nb_elt =3D dq->elt_size/8 + 1; uint32_t avl, n; > > > uintptr_t elt[nb_elt]; ... > > > > > > do { > > > > > > /* read next elem from the queue */ > > > n =3D rte_ring_serial_dequeue_bulk(dq->r, elt, nb_elt, &avl); > > > if (n =3D=3D 0) > > > break; > > > > > > /* wrong period, keep elem in the queue */ if > > > (rte_rcu_qsbr_check(dr->v, > > > elt[0]) !=3D 1) { > > > rte_ring_serial_dequeue_abort(dq->r); > > > break; > > > } > > > > > > /* can reclaim, remove elem from the queue */ > > > rte_ring_serial_dequeue_finish(dr->q, nb_elt); > > > > > > /*call reclaim function */ > > > dr->f(dr->p, elt); > > > > > > } while (avl >=3D nb_elt); > > > > > > That way, I think even rte_rcu_qsbr_dq_reclaim() can be MT safe. > > > As long as actual reclamation callback itself is MT safe of course. > > > > I think it is a great idea. The other writers would still be polling > > for the current writer to update the tail or update the head. This make= s it a > blocking solution. >=20 > Yep, it is a blocking one. >=20 > > We can make the other threads not poll i.e. they will quit reclaiming i= f they > see that other writers are dequeuing from the queue. >=20 > Actually didn't think about that possibility, but yes should be possible = to have > _try_ semantics too. >=20 > >The other way is to use per thread queues. > > > > The other requirement I see is to support unbounded-size data > > structures where in the data structures do not have a pre-determined > > number of entries. Also, currently the defer queue size is equal to the= total > number of entries in a given data structure. There are plans to support > dynamically resizable defer queue. This means, memory allocation which wi= ll > affect the lock-free-ness of the solution. > > > > So, IMO: > > 1) The API should provide the capability to support different algorithm= s - > may be through some flags? > > 2) The requirements for the ring are pretty unique to the problem we > > have here (for ex: move the cons-head only if cons-tail is also the sam= e, skip > polling). So, we should probably implement a ring with-in the RCU library= ? >=20 > Personally, I think such serialization ring API would be useful for other= cases > too. > There are few cases when user need to read contents of the queue without > removing elements from it. > Let say we do use similar approach inside TLDK to implement TCP transmit > queue. > If such API would exist in DPDK we can just use it straightway, without > maintaining a separate one. ok >=20 > > > > From the timeline perspective, adding all these capabilities would be > > difficult to get done with in 19.11 timeline. What I have here > > satisfies my current needs. I suggest that we make provisions in APIs n= ow to > support all these features, but do the implementation in the coming relea= ses. > Does this sound ok for you? >=20 > Not sure I understand your suggestion here... > Could you explain it a bit more - how new API will look like and what wou= ld > be left for the future. For this patch, I suggest we do not add any more complexity. If someone wan= ts a lock-free/block-free mechanism, it is available by creating per thread= defer queues. We push the following to the future: 1) Dynamically size adjustable defer queue. IMO, with this, the lock-free/b= lock-free reclamation will not be available (memory allocation requires loc= king). The memory for the defer queue will be allocated/freed in chunks of = 'size' elements as the queue grows/shrinks. 2) Constant size defer queue with lock-free and block-free reclamation (sin= gle option). The defer queue will be of fixed length 'size'. If the queue g= ets full an error is returned. The user could provide a 'size' equal to the= number of elements in a data structure to ensure queue never gets full. I would add a 'flags' field in rte_rcu_qsbr_dq_parameters and provide 2 #de= fines, one for dynamically variable size defer queue and the other for cons= tant size defer queue. However, IMO, using per thread defer queue is a much simpler way to achieve= 2. It does not add any significant burden to the user either. >=20 > > > > > > > > > +{ > > > > + uint32_t prod_tail =3D r->prod.tail; > > > > + uint32_t cons_head =3D r->cons.head; > > > > + uint32_t count =3D (prod_tail - cons_head) & r->mask; > > > > + unsigned int n =3D 1; > > > > + if (count) { > > > > + DEQUEUE_PTRS(r, &r[1], cons_head, obj_p, n, void *); > > > > + return 0; > > > > + } > > > > + return -ENOENT; > > > > +} > > > > + > > > > #ifdef __cplusplus > > > > } > > > > #endif > > > > -- > > > > 2.17.1