Branch data     Line data    Source code

       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   [ +  +  +  +  :     407670 :         if (s->flags & RTE_STACK_F_LF)
                   +  + ]
     117                 :          0 :                 return __rte_stack_lf_push(s, obj_table, n);
     118                 :            :         else
     119                 :       1057 :                 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   [ +  +  +  +  :     407796 :         if (s->flags & RTE_STACK_F_LF)
             +  +  #  # ]
     141                 :          0 :                 return __rte_stack_lf_pop(s, obj_table, n);
     142                 :            :         else
     143                 :       1086 :                 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   [ +  +  -  -  :      16906 :         if (s->flags & RTE_STACK_F_LF)
          -  -  +  +  -  
          -  -  -  +  +  
             -  -  -  - ]
     160                 :      16898 :                 return __rte_stack_lf_count(s);
     161                 :            :         else
     162                 :      16906 :                 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   [ +  +  -  +  :      33796 :         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_ */