[dpdk-dev] [PATCH v3 5/8] stack: add lock-free stack implementation

Olivier Matz olivier.matz at 6wind.com
Thu Mar 14 09:01:26 CET 2019


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 <gage.eads at intel.com>

Reviewed-by: Olivier Matz <olivier.matz at 6wind.com>


More information about the dev mailing list