lib/librte_stack/rte_stack_lf_c11.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2019 Intel Corporation
   3  */
   4
   5 #ifndef _RTE_STACK_LF_C11_H_
   6 #define _RTE_STACK_LF_C11_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)__atomic_load_n(&s->stack_lf.used.len,
  30                                              __ATOMIC_RELAXED);
  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                 /* Use an acquire fence to establish a synchronized-with
  48                  * relationship between the list->head load and store-release
  49                  * operations (as part of the rte_atomic128_cmp_exchange()).
  50                  */
  51                 __atomic_thread_fence(__ATOMIC_ACQUIRE);
  52
  53                 /* Swing the top pointer to the first element in the list and
  54                  * make the last element point to the old top.
  55                  */
  56                 new_head.top = first;
  57                 new_head.cnt = old_head.cnt + 1;
  58
  59                 last->next = old_head.top;
  60
  61                 /* Use the release memmodel to ensure the writes to the LF LIFO
  62                  * elements are visible before the head pointer write.
  63                  */
  64                 success = rte_atomic128_cmp_exchange(
  65                                 (rte_int128_t *)&list->head,
  66                                 (rte_int128_t *)&old_head,
  67                                 (rte_int128_t *)&new_head,
  68                                 1, __ATOMIC_RELEASE,
  69                                 __ATOMIC_RELAXED);
  70         } while (success == 0);
  71
  72         /* Ensure the stack modifications are not reordered with respect
  73          * to the LIFO len update.
  74          */
  75         __atomic_add_fetch(&list->len, num, __ATOMIC_RELEASE);
  76 }
  77
  78 static __rte_always_inline struct rte_stack_lf_elem *
  79 __rte_stack_lf_pop_elems(struct rte_stack_lf_list *list,
  80                          unsigned int num,
  81                          void **obj_table,
  82                          struct rte_stack_lf_elem **last)
  83 {
  84         struct rte_stack_lf_head old_head;
  85         uint64_t len;
  86         int success;
  87
  88         /* Reserve num elements, if available */
  89         len = __atomic_load_n(&list->len, __ATOMIC_ACQUIRE);
  90
  91         while (1) {
  92                 /* Does the list contain enough elements? */
  93                 if (unlikely(len < num))
  94                         return NULL;
  95
  96                 /* len is updated on failure */
  97                 if (__atomic_compare_exchange_n(&list->len,
  98                                                 &len, len - num,
  99                                                 0, __ATOMIC_ACQUIRE,
 100                                                 __ATOMIC_ACQUIRE))
 101                         break;
 102         }
 103
 104         /* If a torn read occurs, the CAS will fail and set old_head to the
 105          * correct/latest value.
 106          */
 107         old_head = list->head;
 108
 109         /* Pop num elements */
 110         do {
 111                 struct rte_stack_lf_head new_head;
 112                 struct rte_stack_lf_elem *tmp;
 113                 unsigned int i;
 114
 115                 /* Use the acquire memmodel to ensure the reads to the LF LIFO
 116                  * elements are properly ordered with respect to the head
 117                  * pointer read.
 118                  */
 119                 __atomic_thread_fence(__ATOMIC_ACQUIRE);
 120
 121                 rte_prefetch0(old_head.top);
 122
 123                 tmp = old_head.top;
 124
 125                 /* Traverse the list to find the new head. A next pointer will
 126                  * either point to another element or NULL; if a thread
 127                  * encounters a pointer that has already been popped, the CAS
 128                  * will fail.
 129                  */
 130                 for (i = 0; i < num && tmp != NULL; i++) {
 131                         rte_prefetch0(tmp->next);
 132                         if (obj_table)
 133                                 obj_table[i] = tmp->data;
 134                         if (last)
 135                                 *last = tmp;
 136                         tmp = tmp->next;
 137                 }
 138
 139                 /* If NULL was encountered, the list was modified while
 140                  * traversing it. Retry.
 141                  */
 142                 if (i != num)
 143                         continue;
 144
 145                 new_head.top = tmp;
 146                 new_head.cnt = old_head.cnt + 1;
 147
 148                 success = rte_atomic128_cmp_exchange(
 149                                 (rte_int128_t *)&list->head,
 150                                 (rte_int128_t *)&old_head,
 151                                 (rte_int128_t *)&new_head,
 152                                 1, __ATOMIC_RELEASE,
 153                                 __ATOMIC_RELAXED);
 154         } while (success == 0);
 155
 156         return old_head.top;
 157 }
 158
 159 #endif /* _RTE_STACK_LF_C11_H_ */