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 440B6A0096 for ; Thu, 14 Mar 2019 09:01:29 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 1B4843572; Thu, 14 Mar 2019 09:01:29 +0100 (CET) Received: from mail.droids-corp.org (zoll.droids-corp.org [94.23.50.67]) by dpdk.org (Postfix) with ESMTP id D40C42C28 for ; Thu, 14 Mar 2019 09:01:27 +0100 (CET) Received: from lfbn-1-5920-128.w90-110.abo.wanadoo.fr ([90.110.126.128] helo=droids-corp.org) by mail.droids-corp.org with esmtpsa (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1h4LL8-0005ir-8M; Thu, 14 Mar 2019 09:03:47 +0100 Received: by droids-corp.org (sSMTP sendmail emulation); Thu, 14 Mar 2019 09:01:26 +0100 Date: Thu, 14 Mar 2019 09:01:26 +0100 From: Olivier Matz To: Gage Eads Cc: dev@dpdk.org, arybchenko@solarflare.com, bruce.richardson@intel.com, konstantin.ananyev@intel.com, gavin.hu@arm.com, Honnappa.Nagarahalli@arm.com, nd@arm.com, thomas@monjalon.net Message-ID: <20190314080126.vuvbznljcdm65ab5@platinum> References: <20190305164256.2367-1-gage.eads@intel.com> <20190306144559.391-1-gage.eads@intel.com> <20190306144559.391-6-gage.eads@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Disposition: inline In-Reply-To: <20190306144559.391-6-gage.eads@intel.com> User-Agent: NeoMutt/20170113 (1.7.2) Subject: Re: [dpdk-dev] [PATCH v3 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: <20190314080126.ge8ezZHkuSvQFm5zyIkfx7MDRW0dzbI_2prHmiDtoWg@z> On Wed, Mar 06, 2019 at 08:45:56AM -0600, Gage Eads wrote: > 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. > > The stack consists of a linked list of elements, each containing a data > pointer and a next pointer, and an atomic stack depth counter. > > The lock-free push operation enqueues a linked list of pointers by pointing > 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 > is unsuccessful (i.e. the list changed between reading the head and > modifying it), else it adjusts the stack length and returns. > > The lock-free pop operation first reserves num elements by adjusting the > stack length, to ensure the dequeue operation will succeed without > blocking. 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. > > 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. > > The linked list elements themselves are maintained in a lock-free LIFO > list, 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. > > Signed-off-by: Gage Eads Reviewed-by: Olivier Matz