From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60060.outbound.protection.outlook.com [40.107.6.60]) by dpdk.org (Postfix) with ESMTP id CF7B15911 for ; Mon, 1 Apr 2019 20:08:40 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=qPv+JPNnUYToNDcnrcZRTp0lXzGI3O0L462JLS+IynA=; b=cR9D+H3oid+3Ws/dmkUpysHij6Ijj3s7EC7T8QoWEvpUY+uwri8qNizPtJQ2mL6g3pvKv9Cey4W3EE3dxAaJwSvltwcc2c/KFMJFlBRr0ViWjnOkTS03MGEc83kHujInQSWuWhRICQi10Cvf8Qh+ixgi97o3khv6VQRgnjnnGpo= Received: from VE1PR08MB5149.eurprd08.prod.outlook.com (20.179.30.152) by VE1PR08MB5215.eurprd08.prod.outlook.com (10.255.159.23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1750.17; Mon, 1 Apr 2019 18:08:37 +0000 Received: from VE1PR08MB5149.eurprd08.prod.outlook.com ([fe80::e0ae:ecad:ec5:8177]) by VE1PR08MB5149.eurprd08.prod.outlook.com ([fe80::e0ae:ecad:ec5:8177%2]) with mapi id 15.20.1750.017; Mon, 1 Apr 2019 18:08:37 +0000 From: Honnappa Nagarahalli To: Gage Eads , "dev@dpdk.org" CC: "olivier.matz@6wind.com" , "arybchenko@solarflare.com" , "bruce.richardson@intel.com" , "konstantin.ananyev@intel.com" , "Gavin Hu (Arm Technology China)" , nd , "thomas@monjalon.net" , nd Thread-Topic: [PATCH v5 5/8] stack: add lock-free stack implementation Thread-Index: AQHU6B+85eb+XpPR/Ea/DTqfHPp9H6YnmxrA Date: Mon, 1 Apr 2019 18:08:37 +0000 Message-ID: References: <20190328180015.13878-1-gage.eads@intel.com> <20190401001238.17625-1-gage.eads@intel.com> <20190401001238.17625-6-gage.eads@intel.com> In-Reply-To: <20190401001238.17625-6-gage.eads@intel.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: 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: 6fcdb81d-17eb-48ce-f932-08d6b6cd1028 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600139)(711020)(4605104)(4618075)(2017052603328)(7193020); SRVR:VE1PR08MB5215; x-ms-traffictypediagnostic: VE1PR08MB5215: x-ld-processed: f34e5979-57d9-4aaa-ad4d-b122a662184d,ExtAddr nodisclaimer: True x-microsoft-antispam-prvs: x-forefront-prvs: 0994F5E0C5 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(376002)(366004)(396003)(136003)(346002)(39860400002)(199004)(189003)(6246003)(55016002)(71190400001)(71200400001)(25786009)(476003)(6436002)(4326008)(14454004)(9686003)(446003)(486006)(53936002)(72206003)(229853002)(105586002)(106356001)(74316002)(2906002)(7736002)(86362001)(305945005)(99286004)(5660300002)(81156014)(8676002)(81166006)(33656002)(102836004)(26005)(2501003)(8936002)(6506007)(54906003)(76176011)(7696005)(52536014)(478600001)(3846002)(14444005)(256004)(68736007)(110136005)(66066001)(6116002)(11346002)(316002)(186003)(97736004); DIR:OUT; SFP:1101; SCL:1; SRVR:VE1PR08MB5215; 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: +V907APgCnxO9dvFelVo+PyYQji0a1x8e3m7gG6HMYxG8abRSYVcHlgRt6Wh5QcMsin22YAPfrq7mfnWPH6xrnafn4y4hU//p79bewfsDXARtC70YvHAcFcm3Ro31Wp6OuMLHrygzmm2bDa3T+nm02kGJFInm93R8tkR0QWUXqjh1NBtaPx8sPo2Znz96rhF08qDCl5fdlYHm9AsY/qZsj0Ev5vLZuMpm3vs63VhoRGa2iDC3IXnPDhoVlVMs7NLE5DrVR77hGQcJ/gZYY1uxKl0SYvLcZxKxbbI3p7GFMhkqg0pchKqPc006ODUwR1RFWVis5iOQ4NFXRxJ2obHXxKRstqC1vcuoY5j8SAUhRP9pFj2x5Ti5c6JlpNUzVP8DnNx7dyg6S0T87jELyquUoqI2SHpssSRt3nF/CkW2pE= Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: 6fcdb81d-17eb-48ce-f932-08d6b6cd1028 X-MS-Exchange-CrossTenant-originalarrivaltime: 01 Apr 2019 18:08:37.3904 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-Transport-CrossTenantHeadersStamped: VE1PR08MB5215 Subject: Re: [dpdk-dev] [PATCH v5 5/8] stack: add lock-free stack implementation 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: Mon, 01 Apr 2019 18:08:41 -0000 > Subject: [PATCH v5 5/8] stack: add lock-free stack implementation >=20 > This commit adds support for a lock-free (linked list based) stack to the= stack > API. This behavior is selected through a new rte_stack_create() flag, > RTE_STACK_F_LF. >=20 > The stack consists of a linked list of elements, each containing a data p= ointer > and a next pointer, and an atomic stack depth counter. >=20 > The lock-free push operation enqueues a linked list of pointers by pointi= ng > the tail of the list to the current stack head, and using a CAS to swing = the > stack head pointer to the head of the list. The operation retries if it i= s > unsuccessful (i.e. the list changed between reading the head and modifyin= g > it), else it adjusts the stack length and returns. >=20 > The lock-free pop operation first reserves num elements by adjusting the > stack length, to ensure the dequeue operation will succeed without blocki= ng. > It then dequeues pointers by walking the list -- starting from the head -= - then > swinging the head pointer (using a CAS as well). While walking the list, = the > data pointers are recorded in an object table. >=20 > This algorithm stack uses a 128-bit compare-and-swap instruction, which > atomically updates the stack top pointer and a modification counter, to > protect against the ABA problem. >=20 > The linked list elements themselves are maintained in a lock-free LIFO li= st, > and are allocated before stack pushes and freed after stack pops. > Since the stack has a fixed maximum depth, these elements do not need to > be dynamically created. >=20 > Signed-off-by: Gage Eads > Reviewed-by: Olivier Matz > --- Reviewed-by: Honnappa Nagarahalli 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 4853BA0679 for ; Mon, 1 Apr 2019 20:08:42 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 5DCF25B26; Mon, 1 Apr 2019 20:08:41 +0200 (CEST) Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60060.outbound.protection.outlook.com [40.107.6.60]) by dpdk.org (Postfix) with ESMTP id CF7B15911 for ; Mon, 1 Apr 2019 20:08:40 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=qPv+JPNnUYToNDcnrcZRTp0lXzGI3O0L462JLS+IynA=; b=cR9D+H3oid+3Ws/dmkUpysHij6Ijj3s7EC7T8QoWEvpUY+uwri8qNizPtJQ2mL6g3pvKv9Cey4W3EE3dxAaJwSvltwcc2c/KFMJFlBRr0ViWjnOkTS03MGEc83kHujInQSWuWhRICQi10Cvf8Qh+ixgi97o3khv6VQRgnjnnGpo= Received: from VE1PR08MB5149.eurprd08.prod.outlook.com (20.179.30.152) by VE1PR08MB5215.eurprd08.prod.outlook.com (10.255.159.23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1750.17; Mon, 1 Apr 2019 18:08:37 +0000 Received: from VE1PR08MB5149.eurprd08.prod.outlook.com ([fe80::e0ae:ecad:ec5:8177]) by VE1PR08MB5149.eurprd08.prod.outlook.com ([fe80::e0ae:ecad:ec5:8177%2]) with mapi id 15.20.1750.017; Mon, 1 Apr 2019 18:08:37 +0000 From: Honnappa Nagarahalli To: Gage Eads , "dev@dpdk.org" CC: "olivier.matz@6wind.com" , "arybchenko@solarflare.com" , "bruce.richardson@intel.com" , "konstantin.ananyev@intel.com" , "Gavin Hu (Arm Technology China)" , nd , "thomas@monjalon.net" , nd Thread-Topic: [PATCH v5 5/8] stack: add lock-free stack implementation Thread-Index: AQHU6B+85eb+XpPR/Ea/DTqfHPp9H6YnmxrA Date: Mon, 1 Apr 2019 18:08:37 +0000 Message-ID: References: <20190328180015.13878-1-gage.eads@intel.com> <20190401001238.17625-1-gage.eads@intel.com> <20190401001238.17625-6-gage.eads@intel.com> In-Reply-To: <20190401001238.17625-6-gage.eads@intel.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: 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: 6fcdb81d-17eb-48ce-f932-08d6b6cd1028 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600139)(711020)(4605104)(4618075)(2017052603328)(7193020); SRVR:VE1PR08MB5215; x-ms-traffictypediagnostic: VE1PR08MB5215: x-ld-processed: f34e5979-57d9-4aaa-ad4d-b122a662184d,ExtAddr nodisclaimer: True x-microsoft-antispam-prvs: x-forefront-prvs: 0994F5E0C5 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(376002)(366004)(396003)(136003)(346002)(39860400002)(199004)(189003)(6246003)(55016002)(71190400001)(71200400001)(25786009)(476003)(6436002)(4326008)(14454004)(9686003)(446003)(486006)(53936002)(72206003)(229853002)(105586002)(106356001)(74316002)(2906002)(7736002)(86362001)(305945005)(99286004)(5660300002)(81156014)(8676002)(81166006)(33656002)(102836004)(26005)(2501003)(8936002)(6506007)(54906003)(76176011)(7696005)(52536014)(478600001)(3846002)(14444005)(256004)(68736007)(110136005)(66066001)(6116002)(11346002)(316002)(186003)(97736004); DIR:OUT; SFP:1101; SCL:1; SRVR:VE1PR08MB5215; 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: +V907APgCnxO9dvFelVo+PyYQji0a1x8e3m7gG6HMYxG8abRSYVcHlgRt6Wh5QcMsin22YAPfrq7mfnWPH6xrnafn4y4hU//p79bewfsDXARtC70YvHAcFcm3Ro31Wp6OuMLHrygzmm2bDa3T+nm02kGJFInm93R8tkR0QWUXqjh1NBtaPx8sPo2Znz96rhF08qDCl5fdlYHm9AsY/qZsj0Ev5vLZuMpm3vs63VhoRGa2iDC3IXnPDhoVlVMs7NLE5DrVR77hGQcJ/gZYY1uxKl0SYvLcZxKxbbI3p7GFMhkqg0pchKqPc006ODUwR1RFWVis5iOQ4NFXRxJ2obHXxKRstqC1vcuoY5j8SAUhRP9pFj2x5Ti5c6JlpNUzVP8DnNx7dyg6S0T87jELyquUoqI2SHpssSRt3nF/CkW2pE= Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: 6fcdb81d-17eb-48ce-f932-08d6b6cd1028 X-MS-Exchange-CrossTenant-originalarrivaltime: 01 Apr 2019 18:08:37.3904 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-Transport-CrossTenantHeadersStamped: VE1PR08MB5215 Subject: Re: [dpdk-dev] [PATCH v5 5/8] stack: add lock-free stack implementation 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: <20190401180837.oVv5WyDH_xmvMqu4nAEIj15nd1J3WeeE9WpQ1Tt3EmE@z> > Subject: [PATCH v5 5/8] stack: add lock-free stack implementation >=20 > This commit adds support for a lock-free (linked list based) stack to the= stack > API. This behavior is selected through a new rte_stack_create() flag, > RTE_STACK_F_LF. >=20 > The stack consists of a linked list of elements, each containing a data p= ointer > and a next pointer, and an atomic stack depth counter. >=20 > The lock-free push operation enqueues a linked list of pointers by pointi= ng > the tail of the list to the current stack head, and using a CAS to swing = the > stack head pointer to the head of the list. The operation retries if it i= s > unsuccessful (i.e. the list changed between reading the head and modifyin= g > it), else it adjusts the stack length and returns. >=20 > The lock-free pop operation first reserves num elements by adjusting the > stack length, to ensure the dequeue operation will succeed without blocki= ng. > It then dequeues pointers by walking the list -- starting from the head -= - then > swinging the head pointer (using a CAS as well). While walking the list, = the > data pointers are recorded in an object table. >=20 > This algorithm stack uses a 128-bit compare-and-swap instruction, which > atomically updates the stack top pointer and a modification counter, to > protect against the ABA problem. >=20 > The linked list elements themselves are maintained in a lock-free LIFO li= st, > and are allocated before stack pushes and freed after stack pops. > Since the stack has a fixed maximum depth, these elements do not need to > be dynamically created. >=20 > Signed-off-by: Gage Eads > Reviewed-by: Olivier Matz > --- Reviewed-by: Honnappa Nagarahalli