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