1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2019 Intel Corporation
3 */
4
5 /**
6 * @file rte_stack.h
7 *
8 * RTE Stack.
9 *
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.
13 */
14
15 #ifndef _RTE_STACK_H_
16 #define _RTE_STACK_H_
17
18 #ifdef __cplusplus
19 extern "C" {
20 #endif
21
22 #include <rte_debug.h>
23 #include <rte_errno.h>
24 #include <rte_memzone.h>
25 #include <rte_spinlock.h>
26
27 #define RTE_TAILQ_STACK_NAME "RTE_STACK"
28 #define RTE_STACK_MZ_PREFIX "STK_"
29 /** The maximum length of a stack name. */
30 #define RTE_STACK_NAMESIZE (RTE_MEMZONE_NAMESIZE - \
31 sizeof(RTE_STACK_MZ_PREFIX) + 1)
32
33 struct rte_stack_lf_elem {
34 void *data; /**< Data pointer */
35 struct rte_stack_lf_elem *next; /**< Next pointer */
36 };
37
38 struct rte_stack_lf_head {
39 struct rte_stack_lf_elem *top; /**< Stack top */
40 uint64_t cnt; /**< Modification counter for avoiding ABA problem */
41 };
42
43 struct rte_stack_lf_list {
44 /** List head */
45 struct rte_stack_lf_head head __rte_aligned(16);
46 /** List len */
47 uint64_t len;
48 };
49
50 /* Structure containing two lock-free LIFO lists: the stack itself and a list
51 * of free linked-list elements.
52 */
53 struct rte_stack_lf {
54 /** LIFO list of elements */
55 struct rte_stack_lf_list used __rte_cache_aligned;
56 /** LIFO list of free elements */
57 struct rte_stack_lf_list free __rte_cache_aligned;
58 /** LIFO elements */
59 struct rte_stack_lf_elem elems[] __rte_cache_aligned;
60 };
61
62 /* Structure containing the LIFO, its current length, and a lock for mutual
63 * exclusion.
64 */
65 struct rte_stack_std {
66 rte_spinlock_t lock; /**< LIFO lock */
67 uint32_t len; /**< LIFO len */
68 void *objs[]; /**< LIFO pointer table */
69 };
70
71 /* The RTE stack structure contains the LIFO structure itself, plus metadata
72 * such as its name and memzone pointer.
73 */
74 struct rte_stack {
75 /** Name of the stack. */
76 char name[RTE_STACK_NAMESIZE] __rte_cache_aligned;
77 /** Memzone containing the rte_stack structure. */
78 const struct rte_memzone *memzone;
79 uint32_t capacity; /**< Usable size of the stack. */
80 uint32_t flags; /**< Flags supplied at creation. */
81 RTE_STD_C11
82 union {
83 struct rte_stack_lf stack_lf; /**< Lock-free LIFO structure. */
84 struct rte_stack_std stack_std; /**< LIFO structure. */
85 };
86 } __rte_cache_aligned;
87
88 /**
89 * The stack uses lock-free push and pop functions. This flag is only
90 * supported on x86_64 or arm64 platforms, currently.
91 */
92 #define RTE_STACK_F_LF 0x0001
93
94 #include "rte_stack_std.h"
95 #include "rte_stack_lf.h"
96
97 /**
98 * Push several objects on the stack (MT-safe).
99 *
100 * @param s
101 * A pointer to the stack structure.
102 * @param obj_table
103 * A pointer to a table of void * pointers (objects).
104 * @param n
105 * The number of objects to push on the stack from the obj_table.
106 * @return
107 * Actual number of objects pushed (either 0 or *n*).
108 */
109 static __rte_always_inline unsigned int
rte_stack_push(struct rte_stack * s,void * const * obj_table,unsigned int n)110 rte_stack_push(struct rte_stack *s, void * const *obj_table, unsigned int n)
111 {
112 RTE_ASSERT(s != NULL);
113 RTE_ASSERT(obj_table != NULL);
114
115 if (s->flags & RTE_STACK_F_LF)
116 return __rte_stack_lf_push(s, obj_table, n);
117 else
118 return __rte_stack_std_push(s, obj_table, n);
119 }
120
121 /**
122 * Pop several objects from the stack (MT-safe).
123 *
124 * @param s
125 * A pointer to the stack structure.
126 * @param obj_table
127 * A pointer to a table of void * pointers (objects).
128 * @param n
129 * The number of objects to pull from the stack.
130 * @return
131 * Actual number of objects popped (either 0 or *n*).
132 */
133 static __rte_always_inline unsigned int
rte_stack_pop(struct rte_stack * s,void ** obj_table,unsigned int n)134 rte_stack_pop(struct rte_stack *s, void **obj_table, unsigned int n)
135 {
136 RTE_ASSERT(s != NULL);
137 RTE_ASSERT(obj_table != NULL);
138
139 if (s->flags & RTE_STACK_F_LF)
140 return __rte_stack_lf_pop(s, obj_table, n);
141 else
142 return __rte_stack_std_pop(s, obj_table, n);
143 }
144
145 /**
146 * Return the number of used entries in a stack.
147 *
148 * @param s
149 * A pointer to the stack structure.
150 * @return
151 * The number of used entries in the stack.
152 */
153 static __rte_always_inline unsigned int
rte_stack_count(struct rte_stack * s)154 rte_stack_count(struct rte_stack *s)
155 {
156 RTE_ASSERT(s != NULL);
157
158 if (s->flags & RTE_STACK_F_LF)
159 return __rte_stack_lf_count(s);
160 else
161 return __rte_stack_std_count(s);
162 }
163
164 /**
165 * Return the number of free entries in a stack.
166 *
167 * @param s
168 * A pointer to the stack structure.
169 * @return
170 * The number of free entries in the stack.
171 */
172 static __rte_always_inline unsigned int
rte_stack_free_count(struct rte_stack * s)173 rte_stack_free_count(struct rte_stack *s)
174 {
175 RTE_ASSERT(s != NULL);
176
177 return s->capacity - rte_stack_count(s);
178 }
179
180 /**
181 * Create a new stack named *name* in memory.
182 *
183 * This function uses ``memzone_reserve()`` to allocate memory for a stack of
184 * size *count*. The behavior of the stack is controlled by the *flags*.
185 *
186 * @param name
187 * The name of the stack.
188 * @param count
189 * The size of the stack.
190 * @param socket_id
191 * The *socket_id* argument is the socket identifier in case of
192 * NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA
193 * constraint for the reserved zone.
194 * @param flags
195 * An OR of the following:
196 * - RTE_STACK_F_LF: If this flag is set, the stack uses lock-free
197 * variants of the push and pop functions. Otherwise, it achieves
198 * thread-safety using a lock.
199 * @return
200 * On success, the pointer to the new allocated stack. NULL on error with
201 * rte_errno set appropriately. Possible errno values include:
202 * - ENOSPC - the maximum number of memzones has already been allocated
203 * - EEXIST - a stack with the same name already exists
204 * - ENOMEM - insufficient memory to create the stack
205 * - ENAMETOOLONG - name size exceeds RTE_STACK_NAMESIZE
206 * - ENOTSUP - platform does not support given flags combination.
207 */
208 struct rte_stack *
209 rte_stack_create(const char *name, unsigned int count, int socket_id,
210 uint32_t flags);
211
212 /**
213 * Free all memory used by the stack.
214 *
215 * @param s
216 * Stack to free
217 */
218 void
219 rte_stack_free(struct rte_stack *s);
220
221 /**
222 * Lookup a stack by its name.
223 *
224 * @param name
225 * The name of the stack.
226 * @return
227 * The pointer to the stack matching the name, or NULL if not found,
228 * with rte_errno set appropriately. Possible rte_errno values include:
229 * - ENOENT - Stack with name *name* not found.
230 * - EINVAL - *name* pointer is NULL.
231 */
232 struct rte_stack *
233 rte_stack_lookup(const char *name);
234
235 #ifdef __cplusplus
236 }
237 #endif
238
239 #endif /* _RTE_STACK_H_ */
240