lib/librte_stack/rte_stack_lf_generic.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2019 Intel Corporation
   3  */
   4
   5 #ifndef _RTE_STACK_LF_GENERIC_H_
   6 #define _RTE_STACK_LF_GENERIC_H_
   7
   8 #include <rte_branch_prediction.h>
   9 #include <rte_prefetch.h>
  10
  11 static __rte_always_inline unsigned int
  12 __rte_stack_lf_count(struct rte_stack *s)
  13 {
  14         /* stack_lf_push() and stack_lf_pop() do not update the list's contents
  15          * and stack_lf->len atomically, which can cause the list to appear
  16          * shorter than it actually is if this function is called while other
  17          * threads are modifying the list.
  18          *
  19          * However, given the inherently approximate nature of the get_count
  20          * callback -- even if the list and its size were updated atomically,
  21          * the size could change between when get_count executes and when the
  22          * value is returned to the caller -- this is acceptable.
  23          *
  24          * The stack_lf->len updates are placed such that the list may appear to
  25          * have fewer elements than it does, but will never appear to have more
  26          * elements. If the mempool is near-empty to the point that this is a
  27          * concern, the user should consider increasing the mempool size.
  28          */
  29         return (unsigned int)rte_atomic64_read((rte_atomic64_t *)
  30                         &s->stack_lf.used.len);
  31 }
  32
  33 static __rte_always_inline void
  34 __rte_stack_lf_push_elems(struct rte_stack_lf_list *list,
  35                           struct rte_stack_lf_elem *first,
  36                           struct rte_stack_lf_elem *last,
  37                           unsigned int num)
  38 {
  39         struct rte_stack_lf_head old_head;
  40         int success;
  41
  42         old_head = list->head;
  43
  44         do {
  45                 struct rte_stack_lf_head new_head;
  46
  47                 /* An acquire fence (or stronger) is needed for weak memory
  48                  * models to establish a synchronized-with relationship between
  49                  * the list->head load and store-release operations (as part of
  50                  * the rte_atomic128_cmp_exchange()).
  51                  */
  52                 rte_smp_mb();
  53
  54                 /* Swing the top pointer to the first element in the list and
  55                  * make the last element point to the old top.
  56                  */
  57                 new_head.top = first;
  58                 new_head.cnt = old_head.cnt + 1;
  59
  60                 last->next = old_head.top;
  61
  62                 /* old_head is updated on failure */
  63                 success = rte_atomic128_cmp_exchange(
  64                                 (rte_int128_t *)&list->head,
  65                                 (rte_int128_t *)&old_head,
  66                                 (rte_int128_t *)&new_head,
  67                                 1, __ATOMIC_RELEASE,
  68                                 __ATOMIC_RELAXED);
  69         } while (success == 0);
  70
  71         rte_atomic64_add((rte_atomic64_t *)&list->len, num);
  72 }
  73
  74 static __rte_always_inline struct rte_stack_lf_elem *
  75 __rte_stack_lf_pop_elems(struct rte_stack_lf_list *list,
  76                          unsigned int num,
  77                          void **obj_table,
  78                          struct rte_stack_lf_elem **last)
  79 {
  80         struct rte_stack_lf_head old_head;
  81         int success;
  82
  83         /* Reserve num elements, if available */
  84         while (1) {
  85                 uint64_t len = rte_atomic64_read((rte_atomic64_t *)&list->len);
  86
  87                 /* Does the list contain enough elements? */
  88                 if (unlikely(len < num))
  89                         return NULL;
  90
  91                 if (rte_atomic64_cmpset((volatile uint64_t *)&list->len,
  92                                         len, len - num))
  93                         break;
  94         }
  95
  96         old_head = list->head;
  97
  98         /* Pop num elements */
  99         do {
 100                 struct rte_stack_lf_head new_head;
 101                 struct rte_stack_lf_elem *tmp;
 102                 unsigned int i;
 103
 104                 /* An acquire fence (or stronger) is needed for weak memory
 105                  * models to ensure the LF LIFO element reads are properly
 106                  * ordered with respect to the head pointer read.
 107                  */
 108                 rte_smp_mb();
 109
 110                 rte_prefetch0(old_head.top);
 111
 112                 tmp = old_head.top;
 113
 114                 /* Traverse the list to find the new head. A next pointer will
 115                  * either point to another element or NULL; if a thread
 116                  * encounters a pointer that has already been popped, the CAS
 117                  * will fail.
 118                  */
 119                 for (i = 0; i < num && tmp != NULL; i++) {
 120                         rte_prefetch0(tmp->next);
 121                         if (obj_table)
 122                                 obj_table[i] = tmp->data;
 123                         if (last)
 124                                 *last = tmp;
 125                         tmp = tmp->next;
 126                 }
 127
 128                 /* If NULL was encountered, the list was modified while
 129                  * traversing it. Retry.
 130                  */
 131                 if (i != num)
 132                         continue;
 133
 134                 new_head.top = tmp;
 135                 new_head.cnt = old_head.cnt + 1;
 136
 137                 /* old_head is updated on failure */
 138                 success = rte_atomic128_cmp_exchange(
 139                                 (rte_int128_t *)&list->head,
 140                                 (rte_int128_t *)&old_head,
 141                                 (rte_int128_t *)&new_head,
 142                                 1, __ATOMIC_RELEASE,
 143                                 __ATOMIC_RELAXED);
 144         } while (success == 0);
 145
 146         return old_head.top;
 147 }
 148
 149 #endif /* _RTE_STACK_LF_GENERIC_H_ */