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