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 * @warning 11 * @b EXPERIMENTAL: 12 * All functions in this file may be changed or removed without prior notice. 13 * 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. 17 */ 18 19 #ifndef _RTE_STACK_H_ 20 #define _RTE_STACK_H_ 21 22 #ifdef __cplusplus 23 extern "C" { 24 #endif 25 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> 32 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) 38 39 struct rte_stack_lf_elem { 40 void *data; /**< Data pointer */ 41 struct rte_stack_lf_elem *next; /**< Next pointer */ 42 }; 43 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 */ 47 }; 48 49 struct rte_stack_lf_list { 50 /** List head */ 51 struct rte_stack_lf_head head __rte_aligned(16); 52 /** List len */ 53 uint64_t len; 54 }; 55 56 /* Structure containing two lock-free LIFO lists: the stack itself and a list 57 * of free linked-list elements. 58 */ 59 struct rte_stack_lf { 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; 64 /** LIFO elements */ 65 struct rte_stack_lf_elem elems[] __rte_cache_aligned; 66 }; 67 68 /* Structure containing the LIFO, its current length, and a lock for mutual 69 * exclusion. 70 */ 71 struct rte_stack_std { 72 rte_spinlock_t lock; /**< LIFO lock */ 73 uint32_t len; /**< LIFO len */ 74 void *objs[]; /**< LIFO pointer table */ 75 }; 76 77 /* The RTE stack structure contains the LIFO structure itself, plus metadata 78 * such as its name and memzone pointer. 79 */ 80 struct rte_stack { 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. */ 87 RTE_STD_C11 88 union { 89 struct rte_stack_lf stack_lf; /**< Lock-free LIFO structure. */ 90 struct rte_stack_std stack_std; /**< LIFO structure. */ 91 }; 92 } __rte_cache_aligned; 93 94 /** 95 * The stack uses lock-free push and pop functions. This flag is only 96 * supported on x86_64 platforms, currently. 97 */ 98 #define RTE_STACK_F_LF 0x0001 99 100 #include "rte_stack_std.h" 101 #include "rte_stack_lf.h" 102 103 /** 104 * @warning 105 * @b EXPERIMENTAL: this API may change without prior notice 106 * 107 * Push several objects on the stack (MT-safe). 108 * 109 * @param s 110 * A pointer to the stack structure. 111 * @param obj_table 112 * A pointer to a table of void * pointers (objects). 113 * @param n 114 * The number of objects to push on the stack from the obj_table. 115 * @return 116 * Actual number of objects pushed (either 0 or *n*). 117 */ 118 __rte_experimental 119 static __rte_always_inline unsigned int 120 rte_stack_push(struct rte_stack *s, void * const *obj_table, unsigned int n) 121 { 122 RTE_ASSERT(s != NULL); 123 RTE_ASSERT(obj_table != NULL); 124 125 if (s->flags & RTE_STACK_F_LF) 126 return __rte_stack_lf_push(s, obj_table, n); 127 else 128 return __rte_stack_std_push(s, obj_table, n); 129 } 130 131 /** 132 * @warning 133 * @b EXPERIMENTAL: this API may change without prior notice 134 * 135 * Pop several objects from the stack (MT-safe). 136 * 137 * @param s 138 * A pointer to the stack structure. 139 * @param obj_table 140 * A pointer to a table of void * pointers (objects). 141 * @param n 142 * The number of objects to pull from the stack. 143 * @return 144 * Actual number of objects popped (either 0 or *n*). 145 */ 146 __rte_experimental 147 static __rte_always_inline unsigned int 148 rte_stack_pop(struct rte_stack *s, void **obj_table, unsigned int n) 149 { 150 RTE_ASSERT(s != NULL); 151 RTE_ASSERT(obj_table != NULL); 152 153 if (s->flags & RTE_STACK_F_LF) 154 return __rte_stack_lf_pop(s, obj_table, n); 155 else 156 return __rte_stack_std_pop(s, obj_table, n); 157 } 158 159 /** 160 * @warning 161 * @b EXPERIMENTAL: this API may change without prior notice 162 * 163 * Return the number of used entries in a stack. 164 * 165 * @param s 166 * A pointer to the stack structure. 167 * @return 168 * The number of used entries in the stack. 169 */ 170 __rte_experimental 171 static __rte_always_inline unsigned int 172 rte_stack_count(struct rte_stack *s) 173 { 174 RTE_ASSERT(s != NULL); 175 176 if (s->flags & RTE_STACK_F_LF) 177 return __rte_stack_lf_count(s); 178 else 179 return __rte_stack_std_count(s); 180 } 181 182 /** 183 * @warning 184 * @b EXPERIMENTAL: this API may change without prior notice 185 * 186 * Return the number of free entries in a stack. 187 * 188 * @param s 189 * A pointer to the stack structure. 190 * @return 191 * The number of free entries in the stack. 192 */ 193 __rte_experimental 194 static __rte_always_inline unsigned int 195 rte_stack_free_count(struct rte_stack *s) 196 { 197 RTE_ASSERT(s != NULL); 198 199 return s->capacity - rte_stack_count(s); 200 } 201 202 /** 203 * @warning 204 * @b EXPERIMENTAL: this API may change without prior notice 205 * 206 * Create a new stack named *name* in memory. 207 * 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*. 210 * 211 * @param name 212 * The name of the stack. 213 * @param count 214 * The size of the stack. 215 * @param socket_id 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. 219 * @param flags 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. 224 * @return 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 231 */ 232 __rte_experimental 233 struct rte_stack * 234 rte_stack_create(const char *name, unsigned int count, int socket_id, 235 uint32_t flags); 236 237 /** 238 * @warning 239 * @b EXPERIMENTAL: this API may change without prior notice 240 * 241 * Free all memory used by the stack. 242 * 243 * @param s 244 * Stack to free 245 */ 246 __rte_experimental 247 void 248 rte_stack_free(struct rte_stack *s); 249 250 /** 251 * @warning 252 * @b EXPERIMENTAL: this API may change without prior notice 253 * 254 * Lookup a stack by its name. 255 * 256 * @param name 257 * The name of the stack. 258 * @return 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. 263 */ 264 __rte_experimental 265 struct rte_stack * 266 rte_stack_lookup(const char *name); 267 268 #ifdef __cplusplus 269 } 270 #endif 271 272 #endif /* _RTE_STACK_H_ */ 273