Commit | Line | Data |
---|---|---|
8ad4ce58 MD |
1 | #ifndef _URCU_WFCQUEUE_H |
2 | #define _URCU_WFCQUEUE_H | |
3 | ||
4 | /* | |
5 | * wfcqueue.h | |
6 | * | |
7 | * Userspace RCU library - Concurrent Queue with Wait-Free Enqueue/Blocking Dequeue | |
8 | * | |
9 | * Copyright 2010-2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
10 | * Copyright 2011-2012 - Lai Jiangshan <laijs@cn.fujitsu.com> | |
11 | * | |
12 | * This library is free software; you can redistribute it and/or | |
13 | * modify it under the terms of the GNU Lesser General Public | |
14 | * License as published by the Free Software Foundation; either | |
15 | * version 2.1 of the License, or (at your option) any later version. | |
16 | * | |
17 | * This library is distributed in the hope that it will be useful, | |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
20 | * Lesser General Public License for more details. | |
21 | * | |
22 | * You should have received a copy of the GNU Lesser General Public | |
23 | * License along with this library; if not, write to the Free Software | |
24 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
25 | */ | |
26 | ||
27 | #include <pthread.h> | |
28 | #include <assert.h> | |
29 | #include <stdbool.h> | |
30 | #include <urcu/compiler.h> | |
31 | #include <urcu/arch.h> | |
32 | ||
33 | #ifdef __cplusplus | |
34 | extern "C" { | |
35 | #endif | |
36 | ||
37 | /* | |
38 | * Concurrent queue with wait-free enqueue/blocking dequeue. | |
39 | * | |
ebfd2673 MD |
40 | * This queue has been designed and implemented collaboratively by |
41 | * Mathieu Desnoyers and Lai Jiangshan. Inspired from | |
42 | * half-wait-free/half-blocking queue implementation done by Paul E. | |
43 | * McKenney. | |
8ad4ce58 MD |
44 | */ |
45 | ||
46 | struct cds_wfcq_node { | |
47 | struct cds_wfcq_node *next; | |
48 | }; | |
49 | ||
50 | /* | |
51 | * Do not put head and tail on the same cache-line if concurrent | |
52 | * enqueue/dequeue are expected from many CPUs. This eliminates | |
53 | * false-sharing between enqueue and dequeue. | |
54 | */ | |
55 | struct cds_wfcq_head { | |
56 | struct cds_wfcq_node node; | |
57 | pthread_mutex_t lock; | |
58 | }; | |
59 | ||
60 | struct cds_wfcq_tail { | |
61 | struct cds_wfcq_node *p; | |
62 | }; | |
63 | ||
64 | #ifdef _LGPL_SOURCE | |
65 | ||
66 | #include <urcu/static/wfcqueue.h> | |
67 | ||
68 | #define cds_wfcq_node_init _cds_wfcq_node_init | |
69 | #define cds_wfcq_init _cds_wfcq_init | |
70 | #define cds_wfcq_empty _cds_wfcq_empty | |
71 | #define cds_wfcq_enqueue _cds_wfcq_enqueue | |
72 | ||
73 | /* Dequeue locking */ | |
74 | #define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock | |
75 | #define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock | |
76 | ||
77 | /* Locking performed within cds_wfcq calls. */ | |
78 | #define cds_wfcq_dequeue_blocking _cds_wfcq_dequeue_blocking | |
79 | #define cds_wfcq_splice_blocking _cds_wfcq_splice_blocking | |
80 | #define cds_wfcq_first_blocking _cds_wfcq_first_blocking | |
81 | #define cds_wfcq_next_blocking _cds_wfcq_next_blocking | |
82 | ||
83 | /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */ | |
84 | #define __cds_wfcq_dequeue_blocking ___cds_wfcq_dequeue_blocking | |
85 | #define __cds_wfcq_splice_blocking ___cds_wfcq_splice_blocking | |
86 | #define __cds_wfcq_first_blocking ___cds_wfcq_first_blocking | |
87 | #define __cds_wfcq_next_blocking ___cds_wfcq_next_blocking | |
88 | ||
89 | #else /* !_LGPL_SOURCE */ | |
90 | ||
91 | /* | |
92 | * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API | |
93 | * | |
94 | * Unless otherwise stated, the caller must ensure mutual exclusion of | |
95 | * queue update operations "dequeue" and "splice" (for source queue). | |
f94061a3 MD |
96 | * Queue read operations "first" and "next", which are used by |
97 | * "for_each" iterations, need to be protected against concurrent | |
98 | * "dequeue" and "splice" (for source queue) by the caller. | |
8ad4ce58 MD |
99 | * "enqueue", "splice" (for destination queue), and "empty" are the only |
100 | * operations that can be used without any mutual exclusion. | |
101 | * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock(). | |
102 | * | |
103 | * For convenience, cds_wfcq_dequeue_blocking() and | |
104 | * cds_wfcq_splice_blocking() hold the dequeue lock. | |
105 | */ | |
106 | ||
107 | /* | |
108 | * cds_wfcq_node_init: initialize wait-free queue node. | |
109 | */ | |
110 | extern void cds_wfcq_node_init(struct cds_wfcq_node *node); | |
111 | ||
112 | /* | |
113 | * cds_wfcq_init: initialize wait-free queue. | |
114 | */ | |
115 | extern void cds_wfcq_init(struct cds_wfcq_head *head, | |
116 | struct cds_wfcq_tail *tail); | |
117 | ||
118 | /* | |
119 | * cds_wfcq_empty: return whether wait-free queue is empty. | |
120 | * | |
121 | * No memory barrier is issued. No mutual exclusion is required. | |
122 | */ | |
123 | extern bool cds_wfcq_empty(struct cds_wfcq_head *head, | |
124 | struct cds_wfcq_tail *tail); | |
125 | ||
126 | /* | |
127 | * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock. | |
128 | */ | |
129 | extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head, | |
130 | struct cds_wfcq_tail *tail); | |
131 | ||
132 | /* | |
133 | * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock. | |
134 | */ | |
135 | extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head, | |
136 | struct cds_wfcq_tail *tail); | |
137 | ||
138 | /* | |
139 | * cds_wfcq_enqueue: enqueue a node into a wait-free queue. | |
140 | * | |
141 | * Issues a full memory barrier before enqueue. No mutual exclusion is | |
142 | * required. | |
143 | */ | |
144 | extern void cds_wfcq_enqueue(struct cds_wfcq_head *head, | |
145 | struct cds_wfcq_tail *tail, | |
146 | struct cds_wfcq_node *node); | |
147 | ||
148 | /* | |
149 | * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue. | |
150 | * | |
151 | * Content written into the node before enqueue is guaranteed to be | |
152 | * consistent, but no other memory ordering is ensured. | |
153 | * It is valid to reuse and free a dequeued node immediately. | |
154 | * Mutual exlusion with dequeuers is ensured internally. | |
155 | */ | |
156 | extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking( | |
157 | struct cds_wfcq_head *head, | |
158 | struct cds_wfcq_tail *tail); | |
159 | ||
160 | /* | |
161 | * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. | |
162 | * | |
163 | * Dequeue all nodes from src_q. | |
164 | * dest_q must be already initialized. | |
165 | * Content written into the node before enqueue is guaranteed to be | |
166 | * consistent, but no other memory ordering is ensured. | |
167 | * Mutual exlusion with dequeuers is ensured internally. | |
168 | */ | |
169 | extern void cds_wfcq_splice_blocking( | |
170 | struct cds_wfcq_head *dest_q_head, | |
171 | struct cds_wfcq_tail *dest_q_tail, | |
172 | struct cds_wfcq_head *src_q_head, | |
173 | struct cds_wfcq_tail *src_q_tail); | |
174 | ||
175 | /* | |
176 | * __cds_wfcq_dequeue_blocking: | |
177 | * | |
178 | * Content written into the node before enqueue is guaranteed to be | |
179 | * consistent, but no other memory ordering is ensured. | |
180 | * It is valid to reuse and free a dequeued node immediately. | |
181 | * Should be called with cds_wfcq_dequeue_lock() held. | |
182 | */ | |
183 | extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking( | |
184 | struct cds_wfcq_head *head, | |
185 | struct cds_wfcq_tail *tail); | |
186 | ||
187 | /* | |
188 | * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. | |
189 | * | |
190 | * Dequeue all nodes from src_q. | |
191 | * dest_q must be already initialized. | |
192 | * Content written into the node before enqueue is guaranteed to be | |
193 | * consistent, but no other memory ordering is ensured. | |
194 | * Should be called with cds_wfcq_dequeue_lock() held. | |
195 | */ | |
196 | extern void __cds_wfcq_splice_blocking( | |
197 | struct cds_wfcq_head *dest_q_head, | |
198 | struct cds_wfcq_tail *dest_q_tail, | |
199 | struct cds_wfcq_head *src_q_head, | |
200 | struct cds_wfcq_tail *src_q_tail); | |
201 | ||
202 | /* | |
203 | * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing. | |
204 | * | |
205 | * Content written into the node before enqueue is guaranteed to be | |
206 | * consistent, but no other memory ordering is ensured. | |
207 | * Should be called with cds_wfcq_dequeue_lock() held. | |
f94061a3 MD |
208 | * |
209 | * Used by for-like iteration macros: | |
210 | * __cds_wfcq_for_each_blocking() | |
211 | * __cds_wfcq_for_each_blocking_safe() | |
8ad4ce58 MD |
212 | */ |
213 | extern struct cds_wfcq_node *__cds_wfcq_first_blocking( | |
214 | struct cds_wfcq_head *head, | |
215 | struct cds_wfcq_tail *tail); | |
216 | ||
217 | /* | |
218 | * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing. | |
219 | * | |
220 | * Content written into the node before enqueue is guaranteed to be | |
221 | * consistent, but no other memory ordering is ensured. | |
222 | * Should be called with cds_wfcq_dequeue_lock() held. | |
f94061a3 MD |
223 | * |
224 | * Used by for-like iteration macros: | |
225 | * __cds_wfcq_for_each_blocking() | |
226 | * __cds_wfcq_for_each_blocking_safe() | |
8ad4ce58 MD |
227 | */ |
228 | extern struct cds_wfcq_node *__cds_wfcq_next_blocking( | |
229 | struct cds_wfcq_head *head, | |
230 | struct cds_wfcq_tail *tail, | |
231 | struct cds_wfcq_node *node); | |
232 | ||
233 | #endif /* !_LGPL_SOURCE */ | |
234 | ||
235 | /* | |
236 | * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue, | |
237 | * without dequeuing them. | |
238 | * @head: head of the queue (struct cds_wfcq_head pointer). | |
239 | * @tail: tail of the queue (struct cds_wfcq_tail pointer). | |
240 | * @node: iterator on the queue (struct cds_wfcq_node pointer). | |
241 | * | |
242 | * Content written into each node before enqueue is guaranteed to be | |
243 | * consistent, but no other memory ordering is ensured. | |
244 | * Should be called with cds_wfcq_dequeue_lock() held. | |
245 | */ | |
246 | #define __cds_wfcq_for_each_blocking(head, tail, node) \ | |
247 | for (node = __cds_wfcq_first_blocking(head, tail); \ | |
248 | node != NULL; \ | |
249 | node = __cds_wfcq_next_blocking(head, tail, node)) | |
250 | ||
251 | /* | |
252 | * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue, | |
253 | * without dequeuing them. Safe against deletion. | |
254 | * @head: head of the queue (struct cds_wfcq_head pointer). | |
255 | * @tail: tail of the queue (struct cds_wfcq_tail pointer). | |
256 | * @node: iterator on the queue (struct cds_wfcq_node pointer). | |
257 | * @n: struct cds_wfcq_node pointer holding the next pointer (used | |
258 | * internally). | |
259 | * | |
260 | * Content written into each node before enqueue is guaranteed to be | |
261 | * consistent, but no other memory ordering is ensured. | |
262 | * Should be called with cds_wfcq_dequeue_lock() held. | |
263 | */ | |
264 | #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \ | |
265 | for (node = __cds_wfcq_first_blocking(head, tail), \ | |
266 | n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \ | |
267 | node != NULL; \ | |
268 | node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL)) | |
269 | ||
270 | #ifdef __cplusplus | |
271 | } | |
272 | #endif | |
273 | ||
274 | #endif /* _URCU_WFCQUEUE_H */ |