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_compat.h>
  23 #include <rte_debug.h>
  24 #include <rte_errno.h>
  25 #include <rte_memzone.h>
  26 #include <rte_spinlock.h>
  27
  28 #define RTE_TAILQ_STACK_NAME "RTE_STACK"
  29 #define RTE_STACK_MZ_PREFIX "STK_"
  30 /** The maximum length of a stack name. */
  31 #define RTE_STACK_NAMESIZE (RTE_MEMZONE_NAMESIZE - \
  32                            sizeof(RTE_STACK_MZ_PREFIX) + 1)
  33
  34 struct rte_stack_lf_elem {
  35         void *data;                     /**< Data pointer */
  36         struct rte_stack_lf_elem *next; /**< Next pointer */
  37 };
  38
  39 struct rte_stack_lf_head {
  40         struct rte_stack_lf_elem *top; /**< Stack top */
  41         uint64_t cnt; /**< Modification counter for avoiding ABA problem */
  42 };
  43
  44 struct rte_stack_lf_list {
  45         /** List head */
  46         struct rte_stack_lf_head head __rte_aligned(16);
  47         /** List len */
  48         uint64_t len;
  49 };
  50
  51 /* Structure containing two lock-free LIFO lists: the stack itself and a list
  52  * of free linked-list elements.
  53  */
  54 struct rte_stack_lf {
  55         /** LIFO list of elements */
  56         struct rte_stack_lf_list used __rte_cache_aligned;
  57         /** LIFO list of free elements */
  58         struct rte_stack_lf_list free __rte_cache_aligned;
  59         /** LIFO elements */
  60         struct rte_stack_lf_elem elems[] __rte_cache_aligned;
  61 };
  62
  63 /* Structure containing the LIFO, its current length, and a lock for mutual
  64  * exclusion.
  65  */
  66 struct rte_stack_std {
  67         rte_spinlock_t lock; /**< LIFO lock */
  68         uint32_t len; /**< LIFO len */
  69         void *objs[]; /**< LIFO pointer table */
  70 };
  71
  72 /* The RTE stack structure contains the LIFO structure itself, plus metadata
  73  * such as its name and memzone pointer.
  74  */
  75 struct rte_stack {
  76         /** Name of the stack. */
  77         char name[RTE_STACK_NAMESIZE] __rte_cache_aligned;
  78         /** Memzone containing the rte_stack structure. */
  79         const struct rte_memzone *memzone;
  80         uint32_t capacity; /**< Usable size of the stack. */
  81         uint32_t flags; /**< Flags supplied at creation. */
  82         RTE_STD_C11
  83         union {
  84                 struct rte_stack_lf stack_lf; /**< Lock-free LIFO structure. */
  85                 struct rte_stack_std stack_std; /**< LIFO structure. */
  86         };
  87 } __rte_cache_aligned;
  88
  89 /**
  90  * The stack uses lock-free push and pop functions. This flag is only
  91  * supported on x86_64 or arm64 platforms, currently.
  92  */
  93 #define RTE_STACK_F_LF 0x0001
  94
  95 #include "rte_stack_std.h"
  96 #include "rte_stack_lf.h"
  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  *   Stack to free
 218  */
 219 void
 220 rte_stack_free(struct rte_stack *s);
 221
 222 /**
 223  * Lookup a stack by its name.
 224  *
 225  * @param name
 226  *   The name of the stack.
 227  * @return
 228  *   The pointer to the stack matching the name, or NULL if not found,
 229  *   with rte_errno set appropriately. Possible rte_errno values include:
 230  *    - ENOENT - Stack with name *name* not found.
 231  *    - EINVAL - *name* pointer is NULL.
 232  */
 233 struct rte_stack *
 234 rte_stack_lookup(const char *name);
 235
 236 #ifdef __cplusplus
 237 }
 238 #endif
 239
 240 #endif /* _RTE_STACK_H_ */