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