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.e...@intel.com>
Reviewed-by: Olivier Matz <olivier.m...@6wind.com>
