1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2019 Intel Corporation
7 * @b EXPERIMENTAL: this API may change without prior notice
11 * librte_stack provides an API for configuration and use of a bounded stack of
12 * pointers. Push and pop operations are MT-safe, allowing concurrent access,
13 * and the interface supports pushing and popping multiple pointers at a time.
23 #include <rte_atomic.h>
24 #include <rte_compat.h>
25 #include <rte_debug.h>
26 #include <rte_errno.h>
27 #include <rte_memzone.h>
28 #include <rte_spinlock.h>
30 #define RTE_TAILQ_STACK_NAME "RTE_STACK"
31 #define RTE_STACK_MZ_PREFIX "STK_"
32 /** The maximum length of a stack name. */
33 #define RTE_STACK_NAMESIZE (RTE_MEMZONE_NAMESIZE - \
34 sizeof(RTE_STACK_MZ_PREFIX) + 1)
36 struct rte_stack_lf_elem {
37 void *data; /**< Data pointer */
38 struct rte_stack_lf_elem *next; /**< Next pointer */
41 struct rte_stack_lf_head {
42 struct rte_stack_lf_elem *top; /**< Stack top */
43 uint64_t cnt; /**< Modification counter for avoiding ABA problem */
46 struct rte_stack_lf_list {
48 struct rte_stack_lf_head head __rte_aligned(16);
53 /* Structure containing two lock-free LIFO lists: the stack itself and a list
54 * of free linked-list elements.
57 /** LIFO list of elements */
58 struct rte_stack_lf_list used __rte_cache_aligned;
59 /** LIFO list of free elements */
60 struct rte_stack_lf_list free __rte_cache_aligned;
62 struct rte_stack_lf_elem elems[] __rte_cache_aligned;
65 /* Structure containing the LIFO, its current length, and a lock for mutual
68 struct rte_stack_std {
69 rte_spinlock_t lock; /**< LIFO lock */
70 uint32_t len; /**< LIFO len */
71 void *objs[]; /**< LIFO pointer table */
74 /* The RTE stack structure contains the LIFO structure itself, plus metadata
75 * such as its name and memzone pointer.
78 /** Name of the stack. */
79 char name[RTE_STACK_NAMESIZE] __rte_cache_aligned;
80 /** Memzone containing the rte_stack structure. */
81 const struct rte_memzone *memzone;
82 uint32_t capacity; /**< Usable size of the stack. */
83 uint32_t flags; /**< Flags supplied at creation. */
86 struct rte_stack_lf stack_lf; /**< Lock-free LIFO structure. */
87 struct rte_stack_std stack_std; /**< LIFO structure. */
89 } __rte_cache_aligned;
92 * The stack uses lock-free push and pop functions. This flag is only
93 * supported on x86_64 platforms, currently.
95 #define RTE_STACK_F_LF 0x0001
97 #include "rte_stack_std.h"
98 #include "rte_stack_lf.h"
102 * @b EXPERIMENTAL: this API may change without prior notice
104 * Push several objects on the stack (MT-safe).
107 * A pointer to the stack structure.
109 * A pointer to a table of void * pointers (objects).
111 * The number of objects to push on the stack from the obj_table.
113 * Actual number of objects pushed (either 0 or *n*).
115 static __rte_always_inline unsigned int __rte_experimental
116 rte_stack_push(struct rte_stack *s, void * const *obj_table, unsigned int n)
118 RTE_ASSERT(s != NULL);
119 RTE_ASSERT(obj_table != NULL);
121 if (s->flags & RTE_STACK_F_LF)
122 return __rte_stack_lf_push(s, obj_table, n);
124 return __rte_stack_std_push(s, obj_table, n);
129 * @b EXPERIMENTAL: this API may change without prior notice
131 * Pop several objects from the stack (MT-safe).
134 * A pointer to the stack structure.
136 * A pointer to a table of void * pointers (objects).
138 * The number of objects to pull from the stack.
140 * Actual number of objects popped (either 0 or *n*).
142 static __rte_always_inline unsigned int __rte_experimental
143 rte_stack_pop(struct rte_stack *s, void **obj_table, unsigned int n)
145 RTE_ASSERT(s != NULL);
146 RTE_ASSERT(obj_table != NULL);
148 if (s->flags & RTE_STACK_F_LF)
149 return __rte_stack_lf_pop(s, obj_table, n);
151 return __rte_stack_std_pop(s, obj_table, n);
156 * @b EXPERIMENTAL: this API may change without prior notice
158 * Return the number of used entries in a stack.
161 * A pointer to the stack structure.
163 * The number of used entries in the stack.
165 static __rte_always_inline unsigned int __rte_experimental
166 rte_stack_count(struct rte_stack *s)
168 RTE_ASSERT(s != NULL);
170 if (s->flags & RTE_STACK_F_LF)
171 return __rte_stack_lf_count(s);
173 return __rte_stack_std_count(s);
178 * @b EXPERIMENTAL: this API may change without prior notice
180 * Return the number of free entries in a stack.
183 * A pointer to the stack structure.
185 * The number of free entries in the stack.
187 static __rte_always_inline unsigned int __rte_experimental
188 rte_stack_free_count(struct rte_stack *s)
190 RTE_ASSERT(s != NULL);
192 return s->capacity - rte_stack_count(s);
197 * @b EXPERIMENTAL: this API may change without prior notice
199 * Create a new stack named *name* in memory.
201 * This function uses ``memzone_reserve()`` to allocate memory for a stack of
202 * size *count*. The behavior of the stack is controlled by the *flags*.
205 * The name of the stack.
207 * The size of the stack.
209 * The *socket_id* argument is the socket identifier in case of
210 * NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA
211 * constraint for the reserved zone.
213 * An OR of the following:
214 * - RTE_STACK_F_LF: If this flag is set, the stack uses lock-free
215 * variants of the push and pop functions. Otherwise, it achieves
216 * thread-safety using a lock.
218 * On success, the pointer to the new allocated stack. NULL on error with
219 * rte_errno set appropriately. Possible errno values include:
220 * - ENOSPC - the maximum number of memzones has already been allocated
221 * - EEXIST - a stack with the same name already exists
222 * - ENOMEM - insufficient memory to create the stack
223 * - ENAMETOOLONG - name size exceeds RTE_STACK_NAMESIZE
225 struct rte_stack *__rte_experimental
226 rte_stack_create(const char *name, unsigned int count, int socket_id,
231 * @b EXPERIMENTAL: this API may change without prior notice
233 * Free all memory used by the stack.
238 void __rte_experimental
239 rte_stack_free(struct rte_stack *s);
243 * @b EXPERIMENTAL: this API may change without prior notice
245 * Lookup a stack by its name.
248 * The name of the stack.
250 * The pointer to the stack matching the name, or NULL if not found,
251 * with rte_errno set appropriately. Possible rte_errno values include:
252 * - ENOENT - Stack with name *name* not found.
253 * - EINVAL - *name* pointer is NULL.
255 struct rte_stack * __rte_experimental
256 rte_stack_lookup(const char *name);
262 #endif /* _RTE_STACK_H_ */