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