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 union { 82 struct rte_stack_lf stack_lf; /**< Lock-free LIFO structure. */ 83 struct rte_stack_std stack_std; /**< LIFO structure. */ 84 }; 85 } __rte_cache_aligned; 86 87 /** 88 * The stack uses lock-free push and pop functions. This flag is only 89 * supported on x86_64 or arm64 platforms, currently. 90 */ 91 #define RTE_STACK_F_LF 0x0001 92 93 #include "rte_stack_std.h" 94 #include "rte_stack_lf.h" 95 96 /** 97 * Push several objects on the stack (MT-safe). 98 * 99 * @param s 100 * A pointer to the stack structure. 101 * @param obj_table 102 * A pointer to a table of void * pointers (objects). 103 * @param n 104 * The number of objects to push on the stack from the obj_table. 105 * @return 106 * Actual number of objects pushed (either 0 or *n*). 107 */ 108 static __rte_always_inline unsigned int 109 rte_stack_push(struct rte_stack *s, void * const *obj_table, unsigned int n) 110 { 111 RTE_ASSERT(s != NULL); 112 RTE_ASSERT(obj_table != NULL); 113 114 if (s->flags & RTE_STACK_F_LF) 115 return __rte_stack_lf_push(s, obj_table, n); 116 else 117 return __rte_stack_std_push(s, obj_table, n); 118 } 119 120 /** 121 * Pop several objects from the stack (MT-safe). 122 * 123 * @param s 124 * A pointer to the stack structure. 125 * @param obj_table 126 * A pointer to a table of void * pointers (objects). 127 * @param n 128 * The number of objects to pull from the stack. 129 * @return 130 * Actual number of objects popped (either 0 or *n*). 131 */ 132 static __rte_always_inline unsigned int 133 rte_stack_pop(struct rte_stack *s, void **obj_table, unsigned int n) 134 { 135 RTE_ASSERT(s != NULL); 136 RTE_ASSERT(obj_table != NULL); 137 138 if (s->flags & RTE_STACK_F_LF) 139 return __rte_stack_lf_pop(s, obj_table, n); 140 else 141 return __rte_stack_std_pop(s, obj_table, n); 142 } 143 144 /** 145 * Return the number of used entries in a stack. 146 * 147 * @param s 148 * A pointer to the stack structure. 149 * @return 150 * The number of used entries in the stack. 151 */ 152 static __rte_always_inline unsigned int 153 rte_stack_count(struct rte_stack *s) 154 { 155 RTE_ASSERT(s != NULL); 156 157 if (s->flags & RTE_STACK_F_LF) 158 return __rte_stack_lf_count(s); 159 else 160 return __rte_stack_std_count(s); 161 } 162 163 /** 164 * Return the number of free entries in a stack. 165 * 166 * @param s 167 * A pointer to the stack structure. 168 * @return 169 * The number of free entries in the stack. 170 */ 171 static __rte_always_inline unsigned int 172 rte_stack_free_count(struct rte_stack *s) 173 { 174 RTE_ASSERT(s != NULL); 175 176 return s->capacity - rte_stack_count(s); 177 } 178 179 /** 180 * Create a new stack named *name* in memory. 181 * 182 * This function uses ``memzone_reserve()`` to allocate memory for a stack of 183 * size *count*. The behavior of the stack is controlled by the *flags*. 184 * 185 * @param name 186 * The name of the stack. 187 * @param count 188 * The size of the stack. 189 * @param socket_id 190 * The *socket_id* argument is the socket identifier in case of 191 * NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA 192 * constraint for the reserved zone. 193 * @param flags 194 * An OR of the following: 195 * - RTE_STACK_F_LF: If this flag is set, the stack uses lock-free 196 * variants of the push and pop functions. Otherwise, it achieves 197 * thread-safety using a lock. 198 * @return 199 * On success, the pointer to the new allocated stack. NULL on error with 200 * rte_errno set appropriately. Possible errno values include: 201 * - ENOSPC - the maximum number of memzones has already been allocated 202 * - EEXIST - a stack with the same name already exists 203 * - ENOMEM - insufficient memory to create the stack 204 * - ENAMETOOLONG - name size exceeds RTE_STACK_NAMESIZE 205 * - ENOTSUP - platform does not support given flags combination. 206 */ 207 struct rte_stack * 208 rte_stack_create(const char *name, unsigned int count, int socket_id, 209 uint32_t flags); 210 211 /** 212 * Free all memory used by the stack. 213 * 214 * @param s 215 * Pointer to stack created with rte_stack_create(). 216 * If s is NULL, no operation is performed. 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