> Subject: [PATCH v5 5/8] stack: add lock-free stack implementation
>
> 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.e...@intel.com>
> Reviewed-by: Olivier Matz <olivier.m...@6wind.com>
> ---
Reviewed-by: Honnappa Nagarahalli <honnappa.nagaraha...@arm.com>
