lib/stack/rte_stack.h

   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
 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
 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
 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
 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_ */