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). | |
94 | * Queue read operations "first" and "next" need to be protected against | |
95 | * concurrent "dequeue" and "splice" (for source queue) by the caller. | |
96 | * "enqueue", "splice" (for destination queue), and "empty" are the only | |
97 | * operations that can be used without any mutual exclusion. | |
98 | * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock(). | |
99 | * | |
100 | * For convenience, cds_wfcq_dequeue_blocking() and | |
101 | * cds_wfcq_splice_blocking() hold the dequeue lock. | |
102 | */ | |
103 | ||
104 | /* | |
105 | * cds_wfcq_node_init: initialize wait-free queue node. | |
106 | */ | |
107 | extern void cds_wfcq_node_init(struct cds_wfcq_node *node); | |
108 | ||
109 | /* | |
110 | * cds_wfcq_init: initialize wait-free queue. | |
111 | */ | |
112 | extern void cds_wfcq_init(struct cds_wfcq_head *head, | |
113 | struct cds_wfcq_tail *tail); | |
114 | ||
115 | /* | |
116 | * cds_wfcq_empty: return whether wait-free queue is empty. | |
117 | * | |
118 | * No memory barrier is issued. No mutual exclusion is required. | |
119 | */ | |
120 | extern bool cds_wfcq_empty(struct cds_wfcq_head *head, | |
121 | struct cds_wfcq_tail *tail); | |
122 | ||
123 | /* | |
124 | * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock. | |
125 | */ | |
126 | extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head, | |
127 | struct cds_wfcq_tail *tail); | |
128 | ||
129 | /* | |
130 | * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock. | |
131 | */ | |
132 | extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head, | |
133 | struct cds_wfcq_tail *tail); | |
134 | ||
135 | /* | |
136 | * cds_wfcq_enqueue: enqueue a node into a wait-free queue. | |
137 | * | |
138 | * Issues a full memory barrier before enqueue. No mutual exclusion is | |
139 | * required. | |
140 | */ | |
141 | extern void cds_wfcq_enqueue(struct cds_wfcq_head *head, | |
142 | struct cds_wfcq_tail *tail, | |
143 | struct cds_wfcq_node *node); | |
144 | ||
145 | /* | |
146 | * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue. | |
147 | * | |
148 | * Content written into the node before enqueue is guaranteed to be | |
149 | * consistent, but no other memory ordering is ensured. | |
150 | * It is valid to reuse and free a dequeued node immediately. | |
151 | * Mutual exlusion with dequeuers is ensured internally. | |
152 | */ | |
153 | extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking( | |
154 | struct cds_wfcq_head *head, | |
155 | struct cds_wfcq_tail *tail); | |
156 | ||
157 | /* | |
158 | * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. | |
159 | * | |
160 | * Dequeue all nodes from src_q. | |
161 | * dest_q must be already initialized. | |
162 | * Content written into the node before enqueue is guaranteed to be | |
163 | * consistent, but no other memory ordering is ensured. | |
164 | * Mutual exlusion with dequeuers is ensured internally. | |
165 | */ | |
166 | extern void cds_wfcq_splice_blocking( | |
167 | struct cds_wfcq_head *dest_q_head, | |
168 | struct cds_wfcq_tail *dest_q_tail, | |
169 | struct cds_wfcq_head *src_q_head, | |
170 | struct cds_wfcq_tail *src_q_tail); | |
171 | ||
172 | /* | |
173 | * __cds_wfcq_dequeue_blocking: | |
174 | * | |
175 | * Content written into the node before enqueue is guaranteed to be | |
176 | * consistent, but no other memory ordering is ensured. | |
177 | * It is valid to reuse and free a dequeued node immediately. | |
178 | * Should be called with cds_wfcq_dequeue_lock() held. | |
179 | */ | |
180 | extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking( | |
181 | struct cds_wfcq_head *head, | |
182 | struct cds_wfcq_tail *tail); | |
183 | ||
184 | /* | |
185 | * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. | |
186 | * | |
187 | * Dequeue all nodes from src_q. | |
188 | * dest_q must be already initialized. | |
189 | * Content written into the node before enqueue is guaranteed to be | |
190 | * consistent, but no other memory ordering is ensured. | |
191 | * Should be called with cds_wfcq_dequeue_lock() held. | |
192 | */ | |
193 | extern void __cds_wfcq_splice_blocking( | |
194 | struct cds_wfcq_head *dest_q_head, | |
195 | struct cds_wfcq_tail *dest_q_tail, | |
196 | struct cds_wfcq_head *src_q_head, | |
197 | struct cds_wfcq_tail *src_q_tail); | |
198 | ||
199 | /* | |
200 | * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing. | |
201 | * | |
202 | * Content written into the node before enqueue is guaranteed to be | |
203 | * consistent, but no other memory ordering is ensured. | |
204 | * Should be called with cds_wfcq_dequeue_lock() held. | |
205 | */ | |
206 | extern struct cds_wfcq_node *__cds_wfcq_first_blocking( | |
207 | struct cds_wfcq_head *head, | |
208 | struct cds_wfcq_tail *tail); | |
209 | ||
210 | /* | |
211 | * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing. | |
212 | * | |
213 | * Content written into the node before enqueue is guaranteed to be | |
214 | * consistent, but no other memory ordering is ensured. | |
215 | * Should be called with cds_wfcq_dequeue_lock() held. | |
216 | */ | |
217 | extern struct cds_wfcq_node *__cds_wfcq_next_blocking( | |
218 | struct cds_wfcq_head *head, | |
219 | struct cds_wfcq_tail *tail, | |
220 | struct cds_wfcq_node *node); | |
221 | ||
222 | #endif /* !_LGPL_SOURCE */ | |
223 | ||
224 | /* | |
225 | * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue, | |
226 | * without dequeuing them. | |
227 | * @head: head of the queue (struct cds_wfcq_head pointer). | |
228 | * @tail: tail of the queue (struct cds_wfcq_tail pointer). | |
229 | * @node: iterator on the queue (struct cds_wfcq_node pointer). | |
230 | * | |
231 | * Content written into each node before enqueue is guaranteed to be | |
232 | * consistent, but no other memory ordering is ensured. | |
233 | * Should be called with cds_wfcq_dequeue_lock() held. | |
234 | */ | |
235 | #define __cds_wfcq_for_each_blocking(head, tail, node) \ | |
236 | for (node = __cds_wfcq_first_blocking(head, tail); \ | |
237 | node != NULL; \ | |
238 | node = __cds_wfcq_next_blocking(head, tail, node)) | |
239 | ||
240 | /* | |
241 | * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue, | |
242 | * without dequeuing them. Safe against deletion. | |
243 | * @head: head of the queue (struct cds_wfcq_head pointer). | |
244 | * @tail: tail of the queue (struct cds_wfcq_tail pointer). | |
245 | * @node: iterator on the queue (struct cds_wfcq_node pointer). | |
246 | * @n: struct cds_wfcq_node pointer holding the next pointer (used | |
247 | * internally). | |
248 | * | |
249 | * Content written into each node before enqueue is guaranteed to be | |
250 | * consistent, but no other memory ordering is ensured. | |
251 | * Should be called with cds_wfcq_dequeue_lock() held. | |
252 | */ | |
253 | #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \ | |
254 | for (node = __cds_wfcq_first_blocking(head, tail), \ | |
255 | n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \ | |
256 | node != NULL; \ | |
257 | node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL)) | |
258 | ||
259 | #ifdef __cplusplus | |
260 | } | |
261 | #endif | |
262 | ||
263 | #endif /* _URCU_WFCQUEUE_H */ |