1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2019 Intel Corporation
12 * All functions in this file may be changed or removed without prior notice.
14 * librte_stack provides an API for configuration and use of a bounded stack of
15 * pointers. Push and pop operations are MT-safe, allowing concurrent access,
16 * and the interface supports pushing and popping multiple pointers at a time.
26 #include <rte_atomic.h>
27 #include <rte_compat.h>
28 #include <rte_debug.h>
29 #include <rte_errno.h>
30 #include <rte_memzone.h>
31 #include <rte_spinlock.h>
33 #define RTE_TAILQ_STACK_NAME "RTE_STACK"
34 #define RTE_STACK_MZ_PREFIX "STK_"
35 /** The maximum length of a stack name. */
36 #define RTE_STACK_NAMESIZE (RTE_MEMZONE_NAMESIZE - \
37 sizeof(RTE_STACK_MZ_PREFIX) + 1)
39 struct rte_stack_lf_elem {
40 void *data; /**< Data pointer */
41 struct rte_stack_lf_elem *next; /**< Next pointer */
44 struct rte_stack_lf_head {
45 struct rte_stack_lf_elem *top; /**< Stack top */
46 uint64_t cnt; /**< Modification counter for avoiding ABA problem */
49 struct rte_stack_lf_list {
51 struct rte_stack_lf_head head __rte_aligned(16);
56 /* Structure containing two lock-free LIFO lists: the stack itself and a list
57 * of free linked-list elements.
60 /** LIFO list of elements */
61 struct rte_stack_lf_list used __rte_cache_aligned;
62 /** LIFO list of free elements */
63 struct rte_stack_lf_list free __rte_cache_aligned;
65 struct rte_stack_lf_elem elems[] __rte_cache_aligned;
68 /* Structure containing the LIFO, its current length, and a lock for mutual
71 struct rte_stack_std {
72 rte_spinlock_t lock; /**< LIFO lock */
73 uint32_t len; /**< LIFO len */
74 void *objs[]; /**< LIFO pointer table */
77 /* The RTE stack structure contains the LIFO structure itself, plus metadata
78 * such as its name and memzone pointer.
81 /** Name of the stack. */
82 char name[RTE_STACK_NAMESIZE] __rte_cache_aligned;
83 /** Memzone containing the rte_stack structure. */
84 const struct rte_memzone *memzone;
85 uint32_t capacity; /**< Usable size of the stack. */
86 uint32_t flags; /**< Flags supplied at creation. */
89 struct rte_stack_lf stack_lf; /**< Lock-free LIFO structure. */
90 struct rte_stack_std stack_std; /**< LIFO structure. */
92 } __rte_cache_aligned;
95 * The stack uses lock-free push and pop functions. This flag is only
96 * supported on x86_64 platforms, currently.
98 #define RTE_STACK_F_LF 0x0001
100 #include "rte_stack_std.h"
101 #include "rte_stack_lf.h"
105 * @b EXPERIMENTAL: this API may change without prior notice
107 * Push several objects on the stack (MT-safe).
110 * A pointer to the stack structure.
112 * A pointer to a table of void * pointers (objects).
114 * The number of objects to push on the stack from the obj_table.
116 * Actual number of objects pushed (either 0 or *n*).
119 static __rte_always_inline unsigned int
120 rte_stack_push(struct rte_stack *s, void * const *obj_table, unsigned int n)
122 RTE_ASSERT(s != NULL);
123 RTE_ASSERT(obj_table != NULL);
125 if (s->flags & RTE_STACK_F_LF)
126 return __rte_stack_lf_push(s, obj_table, n);
128 return __rte_stack_std_push(s, obj_table, n);
133 * @b EXPERIMENTAL: this API may change without prior notice
135 * Pop several objects from the stack (MT-safe).
138 * A pointer to the stack structure.
140 * A pointer to a table of void * pointers (objects).
142 * The number of objects to pull from the stack.
144 * Actual number of objects popped (either 0 or *n*).
147 static __rte_always_inline unsigned int
148 rte_stack_pop(struct rte_stack *s, void **obj_table, unsigned int n)
150 RTE_ASSERT(s != NULL);
151 RTE_ASSERT(obj_table != NULL);
153 if (s->flags & RTE_STACK_F_LF)
154 return __rte_stack_lf_pop(s, obj_table, n);
156 return __rte_stack_std_pop(s, obj_table, n);
161 * @b EXPERIMENTAL: this API may change without prior notice
163 * Return the number of used entries in a stack.
166 * A pointer to the stack structure.
168 * The number of used entries in the stack.
171 static __rte_always_inline unsigned int
172 rte_stack_count(struct rte_stack *s)
174 RTE_ASSERT(s != NULL);
176 if (s->flags & RTE_STACK_F_LF)
177 return __rte_stack_lf_count(s);
179 return __rte_stack_std_count(s);
184 * @b EXPERIMENTAL: this API may change without prior notice
186 * Return the number of free entries in a stack.
189 * A pointer to the stack structure.
191 * The number of free entries in the stack.
194 static __rte_always_inline unsigned int
195 rte_stack_free_count(struct rte_stack *s)
197 RTE_ASSERT(s != NULL);
199 return s->capacity - rte_stack_count(s);
204 * @b EXPERIMENTAL: this API may change without prior notice
206 * Create a new stack named *name* in memory.
208 * This function uses ``memzone_reserve()`` to allocate memory for a stack of
209 * size *count*. The behavior of the stack is controlled by the *flags*.
212 * The name of the stack.
214 * The size of the stack.
216 * The *socket_id* argument is the socket identifier in case of
217 * NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA
218 * constraint for the reserved zone.
220 * An OR of the following:
221 * - RTE_STACK_F_LF: If this flag is set, the stack uses lock-free
222 * variants of the push and pop functions. Otherwise, it achieves
223 * thread-safety using a lock.
225 * On success, the pointer to the new allocated stack. NULL on error with
226 * rte_errno set appropriately. Possible errno values include:
227 * - ENOSPC - the maximum number of memzones has already been allocated
228 * - EEXIST - a stack with the same name already exists
229 * - ENOMEM - insufficient memory to create the stack
230 * - ENAMETOOLONG - name size exceeds RTE_STACK_NAMESIZE
234 rte_stack_create(const char *name, unsigned int count, int socket_id,
239 * @b EXPERIMENTAL: this API may change without prior notice
241 * Free all memory used by the stack.
248 rte_stack_free(struct rte_stack *s);
252 * @b EXPERIMENTAL: this API may change without prior notice
254 * Lookup a stack by its name.
257 * The name of the stack.
259 * The pointer to the stack matching the name, or NULL if not found,
260 * with rte_errno set appropriately. Possible rte_errno values include:
261 * - ENOENT - Stack with name *name* not found.
262 * - EINVAL - *name* pointer is NULL.
266 rte_stack_lookup(const char *name);
272 #endif /* _RTE_STACK_H_ */