1.. SPDX-License-Identifier: BSD-3-Clause 2 Copyright(c) 2019 Intel Corporation. 3 4Stack Library 5============= 6 7DPDK's stack library provides an API for configuration and use of a bounded 8stack of pointers. 9 10The stack library provides the following basic operations: 11 12* Create a uniquely named stack of a user-specified size and using a 13 user-specified socket, with either standard (lock-based) or lock-free 14 behavior. 15 16* Push and pop a burst of one or more stack objects (pointers). These function 17 are multi-threading safe. 18 19* Free a previously created stack. 20 21* Lookup a pointer to a stack by its name. 22 23* Query a stack's current depth and number of free entries. 24 25Implementation 26~~~~~~~~~~~~~~ 27 28The library supports two types of stacks: standard (lock-based) and lock-free. 29Both types use the same set of interfaces, but their implementations differ. 30 31.. _Stack_Library_Std_Stack: 32 33Lock-based Stack 34---------------- 35 36The lock-based stack consists of a contiguous array of pointers, a current 37index, and a spinlock. Accesses to the stack are made multi-thread safe by the 38spinlock. 39 40.. _Stack_Library_LF_Stack: 41 42Lock-free Stack 43------------------ 44 45The lock-free stack consists of a linked list of elements, each containing a 46data pointer and a next pointer, and an atomic stack depth counter. The 47lock-free property means that multiple threads can push and pop simultaneously, 48and one thread being preempted/delayed in a push or pop operation will not 49impede the forward progress of any other thread. 50 51The lock-free push operation enqueues a linked list of pointers by pointing the 52list's tail to the current stack head, and using a CAS to swing the stack head 53pointer to the head of the list. The operation retries if it is unsuccessful 54(i.e. the list changed between reading the head and modifying it), else it 55adjusts the stack length and returns. 56 57The lock-free pop operation first reserves one or more list elements by 58adjusting the stack length, to ensure the dequeue operation will succeed 59without blocking. It then dequeues pointers by walking the list -- starting 60from the head -- then swinging the head pointer (using a CAS as well). While 61walking the list, the data pointers are recorded in an object table. 62 63The linked list elements themselves are maintained in a lock-free LIFO, and are 64allocated before stack pushes and freed after stack pops. Since the stack has a 65fixed maximum depth, these elements do not need to be dynamically created. 66 67The lock-free behavior is selected by passing the *RTE_STACK_F_LF* flag to 68rte_stack_create(). 69 70Preventing the ABA Problem 71^^^^^^^^^^^^^^^^^^^^^^^^^^ 72 73To prevent the ABA problem, this algorithm stack uses a 128-bit 74compare-and-swap instruction to atomically update both the stack top pointer 75and a modification counter. The ABA problem can occur without a modification 76counter if, for example: 77 781. Thread A reads head pointer X and stores the pointed-to list element. 792. Other threads modify the list such that the head pointer is once again X, 80 but its pointed-to data is different than what thread A read. 813. Thread A changes the head pointer with a compare-and-swap and succeeds. 82 83In this case thread A would not detect that the list had changed, and would 84both pop stale data and incorrect change the head pointer. By adding a 85modification counter that is updated on every push and pop as part of the 86compare-and-swap, the algorithm can detect when the list changes even if the 87head pointer remains the same. 88