DPDK  21.02.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 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  /* Swing the top pointer to the first element in the list and
48  * make the last element point to the old top.
49  */
50  new_head.top = first;
51  new_head.cnt = old_head.cnt + 1;
52 
53  last->next = old_head.top;
54 
55  /* Use the release memmodel to ensure the writes to the LF LIFO
56  * elements are visible before the head pointer write.
57  */
59  (rte_int128_t *)&list->head,
60  (rte_int128_t *)&old_head,
61  (rte_int128_t *)&new_head,
62  1, __ATOMIC_RELEASE,
63  __ATOMIC_RELAXED);
64  } while (success == 0);
65 
66  /* Ensure the stack modifications are not reordered with respect
67  * to the LIFO len update.
68  */
69  __atomic_add_fetch(&list->len, num, __ATOMIC_RELEASE);
70 }
71 
72 static __rte_always_inline struct rte_stack_lf_elem *
73 __rte_stack_lf_pop_elems(struct rte_stack_lf_list *list,
74  unsigned int num,
75  void **obj_table,
76  struct rte_stack_lf_elem **last)
77 {
78  struct rte_stack_lf_head old_head;
79  uint64_t len;
80  int success;
81 
82  /* Reserve num elements, if available */
83  len = __atomic_load_n(&list->len, __ATOMIC_RELAXED);
84 
85  while (1) {
86  /* Does the list contain enough elements? */
87  if (unlikely(len < num))
88  return NULL;
89 
90  /* len is updated on failure */
91  if (__atomic_compare_exchange_n(&list->len,
92  &len, len - num,
93  1, __ATOMIC_ACQUIRE,
94  __ATOMIC_RELAXED))
95  break;
96  }
97 
98  /* If a torn read occurs, the CAS will fail and set old_head to the
99  * correct/latest value.
100  */
101  old_head = list->head;
102 
103  /* Pop num elements */
104  do {
105  struct rte_stack_lf_head new_head;
106  struct rte_stack_lf_elem *tmp;
107  unsigned int i;
108 
109  /* Use the acquire memmodel to ensure the reads to the LF LIFO
110  * elements are properly ordered with respect to the head
111  * pointer read.
112  */
113  __atomic_thread_fence(__ATOMIC_ACQUIRE);
114 
115  rte_prefetch0(old_head.top);
116 
117  tmp = old_head.top;
118 
119  /* Traverse the list to find the new head. A next pointer will
120  * either point to another element or NULL; if a thread
121  * encounters a pointer that has already been popped, the CAS
122  * will fail.
123  */
124  for (i = 0; i < num && tmp != NULL; i++) {
125  rte_prefetch0(tmp->next);
126  if (obj_table)
127  obj_table[i] = tmp->data;
128  if (last)
129  *last = tmp;
130  tmp = tmp->next;
131  }
132 
133  /* If NULL was encountered, the list was modified while
134  * traversing it. Retry.
135  */
136  if (i != num) {
137  old_head = list->head;
138  continue;
139  }
140 
141  new_head.top = tmp;
142  new_head.cnt = old_head.cnt + 1;
143 
144  /*
145  * The CAS should have release semantics to ensure that
146  * items are read before the head is updated.
147  * But this function is internal, and items are read
148  * only when __rte_stack_lf_pop calls this function to
149  * pop items from used list.
150  * Then, those items are pushed to the free list.
151  * Push uses a CAS store-release on head, which makes
152  * sure that items are read before they are pushed to
153  * the free list, without need for a CAS release here.
154  * This CAS could also be used to ensure that the new
155  * length is visible before the head update, but
156  * acquire semantics on the length update is enough.
157  */
158  success = rte_atomic128_cmp_exchange(
159  (rte_int128_t *)&list->head,
160  (rte_int128_t *)&old_head,
161  (rte_int128_t *)&new_head,
162  0, __ATOMIC_RELAXED,
163  __ATOMIC_RELAXED);
164  } while (success == 0);
165 
166  return old_head.top;
167 }
168 
169 #endif /* _RTE_STACK_LF_C11_H_ */
#define __rte_always_inline
Definition: rte_common.h:226
#define unlikely(x)
static __rte_experimental 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)