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 | * | |
40 | * Inspired from half-wait-free/half-blocking queue implementation done by | |
41 | * Paul E. McKenney. | |
42 | */ | |
43 | ||
44 | struct cds_wfcq_node { | |
45 | struct cds_wfcq_node *next; | |
46 | }; | |
47 | ||
48 | /* | |
49 | * Do not put head and tail on the same cache-line if concurrent | |
50 | * enqueue/dequeue are expected from many CPUs. This eliminates | |
51 | * false-sharing between enqueue and dequeue. | |
52 | */ | |
53 | struct cds_wfcq_head { | |
54 | struct cds_wfcq_node node; | |
55 | pthread_mutex_t lock; | |
56 | }; | |
57 | ||
58 | struct cds_wfcq_tail { | |
59 | struct cds_wfcq_node *p; | |
60 | }; | |
61 | ||
62 | #ifdef _LGPL_SOURCE | |
63 | ||
64 | #include <urcu/static/wfcqueue.h> | |
65 | ||
66 | #define cds_wfcq_node_init _cds_wfcq_node_init | |
67 | #define cds_wfcq_init _cds_wfcq_init | |
68 | #define cds_wfcq_empty _cds_wfcq_empty | |
69 | #define cds_wfcq_enqueue _cds_wfcq_enqueue | |
70 | ||
71 | /* Dequeue locking */ | |
72 | #define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock | |
73 | #define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock | |
74 | ||
75 | /* Locking performed within cds_wfcq calls. */ | |
76 | #define cds_wfcq_dequeue_blocking _cds_wfcq_dequeue_blocking | |
77 | #define cds_wfcq_splice_blocking _cds_wfcq_splice_blocking | |
78 | #define cds_wfcq_first_blocking _cds_wfcq_first_blocking | |
79 | #define cds_wfcq_next_blocking _cds_wfcq_next_blocking | |
80 | ||
81 | /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */ | |
82 | #define __cds_wfcq_dequeue_blocking ___cds_wfcq_dequeue_blocking | |
83 | #define __cds_wfcq_splice_blocking ___cds_wfcq_splice_blocking | |
84 | #define __cds_wfcq_first_blocking ___cds_wfcq_first_blocking | |
85 | #define __cds_wfcq_next_blocking ___cds_wfcq_next_blocking | |
86 | ||
87 | #else /* !_LGPL_SOURCE */ | |
88 | ||
89 | /* | |
90 | * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API | |
91 | * | |
92 | * Unless otherwise stated, the caller must ensure mutual exclusion of | |
93 | * queue update operations "dequeue" and "splice" (for source queue). | |
f94061a3 MD |
94 | * Queue read operations "first" and "next", which are used by |
95 | * "for_each" iterations, need to be protected against concurrent | |
96 | * "dequeue" and "splice" (for source queue) by the caller. | |
8ad4ce58 MD |
97 | * "enqueue", "splice" (for destination queue), and "empty" are the only |
98 | * operations that can be used without any mutual exclusion. | |
99 | * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock(). | |
100 | * | |
101 | * For convenience, cds_wfcq_dequeue_blocking() and | |
102 | * cds_wfcq_splice_blocking() hold the dequeue lock. | |
103 | */ | |
104 | ||
105 | /* | |
106 | * cds_wfcq_node_init: initialize wait-free queue node. | |
107 | */ | |
108 | extern void cds_wfcq_node_init(struct cds_wfcq_node *node); | |
109 | ||
110 | /* | |
111 | * cds_wfcq_init: initialize wait-free queue. | |
112 | */ | |
113 | extern void cds_wfcq_init(struct cds_wfcq_head *head, | |
114 | struct cds_wfcq_tail *tail); | |
115 | ||
116 | /* | |
117 | * cds_wfcq_empty: return whether wait-free queue is empty. | |
118 | * | |
119 | * No memory barrier is issued. No mutual exclusion is required. | |
120 | */ | |
121 | extern bool cds_wfcq_empty(struct cds_wfcq_head *head, | |
122 | struct cds_wfcq_tail *tail); | |
123 | ||
124 | /* | |
125 | * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock. | |
126 | */ | |
127 | extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head, | |
128 | struct cds_wfcq_tail *tail); | |
129 | ||
130 | /* | |
131 | * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock. | |
132 | */ | |
133 | extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head, | |
134 | struct cds_wfcq_tail *tail); | |
135 | ||
136 | /* | |
137 | * cds_wfcq_enqueue: enqueue a node into a wait-free queue. | |
138 | * | |
139 | * Issues a full memory barrier before enqueue. No mutual exclusion is | |
140 | * required. | |
141 | */ | |
142 | extern void cds_wfcq_enqueue(struct cds_wfcq_head *head, | |
143 | struct cds_wfcq_tail *tail, | |
144 | struct cds_wfcq_node *node); | |
145 | ||
146 | /* | |
147 | * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue. | |
148 | * | |
149 | * Content written into the node before enqueue is guaranteed to be | |
150 | * consistent, but no other memory ordering is ensured. | |
151 | * It is valid to reuse and free a dequeued node immediately. | |
152 | * Mutual exlusion with dequeuers is ensured internally. | |
153 | */ | |
154 | extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking( | |
155 | struct cds_wfcq_head *head, | |
156 | struct cds_wfcq_tail *tail); | |
157 | ||
158 | /* | |
159 | * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. | |
160 | * | |
161 | * Dequeue all nodes from src_q. | |
162 | * dest_q must be already initialized. | |
163 | * Content written into the node before enqueue is guaranteed to be | |
164 | * consistent, but no other memory ordering is ensured. | |
165 | * Mutual exlusion with dequeuers is ensured internally. | |
166 | */ | |
167 | extern void cds_wfcq_splice_blocking( | |
168 | struct cds_wfcq_head *dest_q_head, | |
169 | struct cds_wfcq_tail *dest_q_tail, | |
170 | struct cds_wfcq_head *src_q_head, | |
171 | struct cds_wfcq_tail *src_q_tail); | |
172 | ||
173 | /* | |
174 | * __cds_wfcq_dequeue_blocking: | |
175 | * | |
176 | * Content written into the node before enqueue is guaranteed to be | |
177 | * consistent, but no other memory ordering is ensured. | |
178 | * It is valid to reuse and free a dequeued node immediately. | |
179 | * Should be called with cds_wfcq_dequeue_lock() held. | |
180 | */ | |
181 | extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking( | |
182 | struct cds_wfcq_head *head, | |
183 | struct cds_wfcq_tail *tail); | |
184 | ||
185 | /* | |
186 | * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. | |
187 | * | |
188 | * Dequeue all nodes from src_q. | |
189 | * dest_q must be already initialized. | |
190 | * Content written into the node before enqueue is guaranteed to be | |
191 | * consistent, but no other memory ordering is ensured. | |
192 | * Should be called with cds_wfcq_dequeue_lock() held. | |
193 | */ | |
194 | extern void __cds_wfcq_splice_blocking( | |
195 | struct cds_wfcq_head *dest_q_head, | |
196 | struct cds_wfcq_tail *dest_q_tail, | |
197 | struct cds_wfcq_head *src_q_head, | |
198 | struct cds_wfcq_tail *src_q_tail); | |
199 | ||
200 | /* | |
201 | * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing. | |
202 | * | |
203 | * Content written into the node before enqueue is guaranteed to be | |
204 | * consistent, but no other memory ordering is ensured. | |
205 | * Should be called with cds_wfcq_dequeue_lock() held. | |
f94061a3 MD |
206 | * |
207 | * Used by for-like iteration macros: | |
208 | * __cds_wfcq_for_each_blocking() | |
209 | * __cds_wfcq_for_each_blocking_safe() | |
8ad4ce58 MD |
210 | */ |
211 | extern struct cds_wfcq_node *__cds_wfcq_first_blocking( | |
212 | struct cds_wfcq_head *head, | |
213 | struct cds_wfcq_tail *tail); | |
214 | ||
215 | /* | |
216 | * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing. | |
217 | * | |
218 | * Content written into the node before enqueue is guaranteed to be | |
219 | * consistent, but no other memory ordering is ensured. | |
220 | * Should be called with cds_wfcq_dequeue_lock() held. | |
f94061a3 MD |
221 | * |
222 | * Used by for-like iteration macros: | |
223 | * __cds_wfcq_for_each_blocking() | |
224 | * __cds_wfcq_for_each_blocking_safe() | |
8ad4ce58 MD |
225 | */ |
226 | extern struct cds_wfcq_node *__cds_wfcq_next_blocking( | |
227 | struct cds_wfcq_head *head, | |
228 | struct cds_wfcq_tail *tail, | |
229 | struct cds_wfcq_node *node); | |
230 | ||
231 | #endif /* !_LGPL_SOURCE */ | |
232 | ||
233 | /* | |
234 | * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue, | |
235 | * without dequeuing them. | |
236 | * @head: head of the queue (struct cds_wfcq_head pointer). | |
237 | * @tail: tail of the queue (struct cds_wfcq_tail pointer). | |
238 | * @node: iterator on the queue (struct cds_wfcq_node pointer). | |
239 | * | |
240 | * Content written into each node before enqueue is guaranteed to be | |
241 | * consistent, but no other memory ordering is ensured. | |
242 | * Should be called with cds_wfcq_dequeue_lock() held. | |
243 | */ | |
244 | #define __cds_wfcq_for_each_blocking(head, tail, node) \ | |
245 | for (node = __cds_wfcq_first_blocking(head, tail); \ | |
246 | node != NULL; \ | |
247 | node = __cds_wfcq_next_blocking(head, tail, node)) | |
248 | ||
249 | /* | |
250 | * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue, | |
251 | * without dequeuing them. Safe against deletion. | |
252 | * @head: head of the queue (struct cds_wfcq_head pointer). | |
253 | * @tail: tail of the queue (struct cds_wfcq_tail pointer). | |
254 | * @node: iterator on the queue (struct cds_wfcq_node pointer). | |
255 | * @n: struct cds_wfcq_node pointer holding the next pointer (used | |
256 | * internally). | |
257 | * | |
258 | * Content written into each node before enqueue is guaranteed to be | |
259 | * consistent, but no other memory ordering is ensured. | |
260 | * Should be called with cds_wfcq_dequeue_lock() held. | |
261 | */ | |
262 | #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \ | |
263 | for (node = __cds_wfcq_first_blocking(head, tail), \ | |
264 | n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \ | |
265 | node != NULL; \ | |
266 | node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL)) | |
267 | ||
268 | #ifdef __cplusplus | |
269 | } | |
270 | #endif | |
271 | ||
272 | #endif /* _URCU_WFCQUEUE_H */ |