1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2019 Intel Corporation
10 * librte_stack provides an API for configuration and use of a bounded stack of
11 * pointers. Push and pop operations are MT-safe, allowing concurrent access,
12 * and the interface supports pushing and popping multiple pointers at a time.
22 #include <rte_compat.h>
23 #include <rte_debug.h>
24 #include <rte_errno.h>
25 #include <rte_memzone.h>
26 #include <rte_spinlock.h>
28 #define RTE_TAILQ_STACK_NAME "RTE_STACK"
29 #define RTE_STACK_MZ_PREFIX "STK_"
30 /** The maximum length of a stack name. */
31 #define RTE_STACK_NAMESIZE (RTE_MEMZONE_NAMESIZE - \
32 sizeof(RTE_STACK_MZ_PREFIX) + 1)
34 struct rte_stack_lf_elem {
35 void *data; /**< Data pointer */
36 struct rte_stack_lf_elem *next; /**< Next pointer */
39 struct rte_stack_lf_head {
40 struct rte_stack_lf_elem *top; /**< Stack top */
41 uint64_t cnt; /**< Modification counter for avoiding ABA problem */
44 struct rte_stack_lf_list {
46 struct rte_stack_lf_head head __rte_aligned(16);
51 /* Structure containing two lock-free LIFO lists: the stack itself and a list
52 * of free linked-list elements.
55 /** LIFO list of elements */
56 struct rte_stack_lf_list used __rte_cache_aligned;
57 /** LIFO list of free elements */
58 struct rte_stack_lf_list free __rte_cache_aligned;
60 struct rte_stack_lf_elem elems[] __rte_cache_aligned;
63 /* Structure containing the LIFO, its current length, and a lock for mutual
66 struct rte_stack_std {
67 rte_spinlock_t lock; /**< LIFO lock */
68 uint32_t len; /**< LIFO len */
69 void *objs[]; /**< LIFO pointer table */
72 /* The RTE stack structure contains the LIFO structure itself, plus metadata
73 * such as its name and memzone pointer.
76 /** Name of the stack. */
77 char name[RTE_STACK_NAMESIZE] __rte_cache_aligned;
78 /** Memzone containing the rte_stack structure. */
79 const struct rte_memzone *memzone;
80 uint32_t capacity; /**< Usable size of the stack. */
81 uint32_t flags; /**< Flags supplied at creation. */
84 struct rte_stack_lf stack_lf; /**< Lock-free LIFO structure. */
85 struct rte_stack_std stack_std; /**< LIFO structure. */
87 } __rte_cache_aligned;
90 * The stack uses lock-free push and pop functions. This flag is only
91 * supported on x86_64 or arm64 platforms, currently.
93 #define RTE_STACK_F_LF 0x0001
95 #include "rte_stack_std.h"
96 #include "rte_stack_lf.h"
99 * Push several objects on the stack (MT-safe).
102 * A pointer to the stack structure.
104 * A pointer to a table of void * pointers (objects).
106 * The number of objects to push on the stack from the obj_table.
108 * Actual number of objects pushed (either 0 or *n*).
110 static __rte_always_inline unsigned int
111 rte_stack_push(struct rte_stack *s, void * const *obj_table, unsigned int n)
113 RTE_ASSERT(s != NULL);
114 RTE_ASSERT(obj_table != NULL);
116 if (s->flags & RTE_STACK_F_LF)
117 return __rte_stack_lf_push(s, obj_table, n);
119 return __rte_stack_std_push(s, obj_table, n);
123 * Pop several objects from the stack (MT-safe).
126 * A pointer to the stack structure.
128 * A pointer to a table of void * pointers (objects).
130 * The number of objects to pull from the stack.
132 * Actual number of objects popped (either 0 or *n*).
134 static __rte_always_inline unsigned int
135 rte_stack_pop(struct rte_stack *s, void **obj_table, unsigned int n)
137 RTE_ASSERT(s != NULL);
138 RTE_ASSERT(obj_table != NULL);
140 if (s->flags & RTE_STACK_F_LF)
141 return __rte_stack_lf_pop(s, obj_table, n);
143 return __rte_stack_std_pop(s, obj_table, n);
147 * Return the number of used entries in a stack.
150 * A pointer to the stack structure.
152 * The number of used entries in the stack.
154 static __rte_always_inline unsigned int
155 rte_stack_count(struct rte_stack *s)
157 RTE_ASSERT(s != NULL);
159 if (s->flags & RTE_STACK_F_LF)
160 return __rte_stack_lf_count(s);
162 return __rte_stack_std_count(s);
166 * Return the number of free entries in a stack.
169 * A pointer to the stack structure.
171 * The number of free entries in the stack.
173 static __rte_always_inline unsigned int
174 rte_stack_free_count(struct rte_stack *s)
176 RTE_ASSERT(s != NULL);
178 return s->capacity - rte_stack_count(s);
182 * Create a new stack named *name* in memory.
184 * This function uses ``memzone_reserve()`` to allocate memory for a stack of
185 * size *count*. The behavior of the stack is controlled by the *flags*.
188 * The name of the stack.
190 * The size of the stack.
192 * The *socket_id* argument is the socket identifier in case of
193 * NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA
194 * constraint for the reserved zone.
196 * An OR of the following:
197 * - RTE_STACK_F_LF: If this flag is set, the stack uses lock-free
198 * variants of the push and pop functions. Otherwise, it achieves
199 * thread-safety using a lock.
201 * On success, the pointer to the new allocated stack. NULL on error with
202 * rte_errno set appropriately. Possible errno values include:
203 * - ENOSPC - the maximum number of memzones has already been allocated
204 * - EEXIST - a stack with the same name already exists
205 * - ENOMEM - insufficient memory to create the stack
206 * - ENAMETOOLONG - name size exceeds RTE_STACK_NAMESIZE
207 * - ENOTSUP - platform does not support given flags combination.
210 rte_stack_create(const char *name, unsigned int count, int socket_id,
214 * Free all memory used by the stack.
220 rte_stack_free(struct rte_stack *s);
223 * Lookup a stack by its name.
226 * The name of the stack.
228 * The pointer to the stack matching the name, or NULL if not found,
229 * with rte_errno set appropriately. Possible rte_errno values include:
230 * - ENOENT - Stack with name *name* not found.
231 * - EINVAL - *name* pointer is NULL.
234 rte_stack_lookup(const char *name);
240 #endif /* _RTE_STACK_H_ */