DPDK  25.03.0
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 
9 #include <rte_prefetch.h>
10 
11 #ifdef RTE_TOOLCHAIN_MSVC
12 
21 static inline int
22 rte_atomic128_cmp_exchange(rte_int128_t *dst,
23  rte_int128_t *exp,
24  const rte_int128_t *src,
25  unsigned int weak,
26  int success,
27  int failure)
28 {
29  return (int)_InterlockedCompareExchange128(
30  (int64_t volatile *) dst,
31  src->val[1], /* exchange high */
32  src->val[0], /* exchange low */
33  (int64_t *) exp /* comparand result */
34  );
35 }
36 #endif /* RTE_TOOLCHAIN_MSVC */
37 
38 static __rte_always_inline unsigned int
39 __rte_stack_lf_count(struct rte_stack *s)
40 {
41  /* stack_lf_push() and stack_lf_pop() do not update the list's contents
42  * and stack_lf->len atomically, which can cause the list to appear
43  * shorter than it actually is if this function is called while other
44  * threads are modifying the list.
45  *
46  * However, given the inherently approximate nature of the get_count
47  * callback -- even if the list and its size were updated atomically,
48  * the size could change between when get_count executes and when the
49  * value is returned to the caller -- this is acceptable.
50  *
51  * The stack_lf->len updates are placed such that the list may appear to
52  * have fewer elements than it does, but will never appear to have more
53  * elements. If the mempool is near-empty to the point that this is a
54  * concern, the user should consider increasing the mempool size.
55  */
56  return (unsigned int)rte_atomic_load_explicit(&s->stack_lf.used.len,
57  rte_memory_order_relaxed);
58 }
59 
60 static __rte_always_inline void
61 __rte_stack_lf_push_elems(struct rte_stack_lf_list *list,
62  struct rte_stack_lf_elem *first,
63  struct rte_stack_lf_elem *last,
64  unsigned int num)
65 {
66  struct rte_stack_lf_head old_head;
67  int success;
68 
69  old_head = list->head;
70 
71  do {
72  struct rte_stack_lf_head new_head;
73 
74  /* Swing the top pointer to the first element in the list and
75  * make the last element point to the old top.
76  */
77  new_head.top = first;
78  new_head.cnt = old_head.cnt + 1;
79 
80  last->next = old_head.top;
81 
82  /* Use the release memmodel to ensure the writes to the LF LIFO
83  * elements are visible before the head pointer write.
84  */
86  (rte_int128_t *)&list->head,
87  (rte_int128_t *)&old_head,
88  (rte_int128_t *)&new_head,
89  1, rte_memory_order_release,
90  rte_memory_order_relaxed);
91  } while (success == 0);
92 
93  /* Ensure the stack modifications are not reordered with respect
94  * to the LIFO len update.
95  */
96  rte_atomic_fetch_add_explicit(&list->len, num, rte_memory_order_release);
97 }
98 
99 static __rte_always_inline struct rte_stack_lf_elem *
100 __rte_stack_lf_pop_elems(struct rte_stack_lf_list *list,
101  unsigned int num,
102  void **obj_table,
103  struct rte_stack_lf_elem **last)
104 {
105  struct rte_stack_lf_head old_head;
106  uint64_t len;
107  int success = 0;
108 
109  /* Reserve num elements, if available */
110  len = rte_atomic_load_explicit(&list->len, rte_memory_order_relaxed);
111 
112  while (1) {
113  /* Does the list contain enough elements? */
114  if (unlikely(len < num))
115  return NULL;
116 
117  /* len is updated on failure */
118  if (rte_atomic_compare_exchange_weak_explicit(&list->len,
119  &len, len - num,
120  rte_memory_order_acquire,
121  rte_memory_order_relaxed))
122  break;
123  }
124 
125  /* If a torn read occurs, the CAS will fail and set old_head to the
126  * correct/latest value.
127  */
128  old_head = list->head;
129 
130  /* Pop num elements */
131  do {
132  struct rte_stack_lf_head new_head;
133  struct rte_stack_lf_elem *tmp;
134  unsigned int i;
135 
136  /* Use the acquire memmodel to ensure the reads to the LF LIFO
137  * elements are properly ordered with respect to the head
138  * pointer read.
139  */
140  rte_atomic_thread_fence(rte_memory_order_acquire);
141 
142  rte_prefetch0(old_head.top);
143 
144  tmp = old_head.top;
145 
146  /* Traverse the list to find the new head. A next pointer will
147  * either point to another element or NULL; if a thread
148  * encounters a pointer that has already been popped, the CAS
149  * will fail.
150  */
151  for (i = 0; i < num && tmp != NULL; i++) {
152  rte_prefetch0(tmp->next);
153  if (obj_table)
154  obj_table[i] = tmp->data;
155  if (last)
156  *last = tmp;
157  tmp = tmp->next;
158  }
159 
160  /* If NULL was encountered, the list was modified while
161  * traversing it. Retry.
162  */
163  if (i != num) {
164  old_head = list->head;
165  continue;
166  }
167 
168  new_head.top = tmp;
169  new_head.cnt = old_head.cnt + 1;
170 
171  /*
172  * The CAS should have release semantics to ensure that
173  * items are read before the head is updated.
174  * But this function is internal, and items are read
175  * only when __rte_stack_lf_pop calls this function to
176  * pop items from used list.
177  * Then, those items are pushed to the free list.
178  * Push uses a CAS store-release on head, which makes
179  * sure that items are read before they are pushed to
180  * the free list, without need for a CAS release here.
181  * This CAS could also be used to ensure that the new
182  * length is visible before the head update, but
183  * acquire semantics on the length update is enough.
184  */
185  success = rte_atomic128_cmp_exchange(
186  (rte_int128_t *)&list->head,
187  (rte_int128_t *)&old_head,
188  (rte_int128_t *)&new_head,
189  0, rte_memory_order_relaxed,
190  rte_memory_order_relaxed);
191  } while (success == 0);
192 
193  return old_head.top;
194 }
195 
196 #endif /* _RTE_STACK_LF_C11_H_ */
#define __rte_always_inline
Definition: rte_common.h:456
#define unlikely(x)
static void rte_atomic_thread_fence(rte_memory_order memorder)
static int rte_atomic128_cmp_exchange(rte_int128_t *dst, rte_int128_t *exp, const rte_int128_t *src, unsigned int weak, int success, int failure)
static void rte_prefetch0(const volatile void *p)