2 * lock-free-queue.c: Lock free queue.
4 * (C) Copyright 2011 Novell, Inc
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27 * This is an implementation of a lock-free queue, as described in
29 * Simple, Fast, and Practical Non-Blocking and Blocking
30 * Concurrent Queue Algorithms
31 * Maged M. Michael, Michael L. Scott
34 * A few slight modifications have been made:
36 * We use hazard pointers to rule out the ABA problem, instead of the
37 * counter as in the paper.
39 * Memory management of the queue entries is done by the caller, not
40 * by the queue implementation. This implies that the dequeue
41 * function must return the queue entry, not just the data.
43 * Therefore, the dummy entry must never be returned. We do this by
44 * re-enqueuing a new dummy entry after we dequeue one and then
45 * retrying the dequeue. We need more than one dummy because they
46 * must be hazardly freed.
52 #include <mono/utils/mono-membar.h>
53 #include <mono/utils/hazard-pointer.h>
54 #include <mono/io-layer/io-layer.h>
56 #include <mono/utils/lock-free-queue.h>
58 #define INVALID_NEXT ((void*)-1)
59 #define END_MARKER ((void*)-2)
60 #define FREE_NEXT ((void*)-3)
63 mono_lock_free_queue_init (MonoLockFreeQueue *q)
66 for (i = 0; i < MONO_LOCK_FREE_QUEUE_NUM_DUMMIES; ++i) {
67 q->dummies [i].node.next = (i == 0) ? END_MARKER : FREE_NEXT;
68 q->dummies [i].in_use = i == 0 ? 1 : 0;
70 q->dummies [i].node.in_queue = i == 0 ? TRUE : FALSE;
74 q->head = q->tail = &q->dummies [0].node;
79 mono_lock_free_queue_node_init (MonoLockFreeQueueNode *node, gboolean to_be_freed)
81 node->next = to_be_freed ? INVALID_NEXT : FREE_NEXT;
83 node->in_queue = FALSE;
88 mono_lock_free_queue_node_free (MonoLockFreeQueueNode *node)
90 g_assert (node->next == INVALID_NEXT);
92 g_assert (!node->in_queue);
94 node->next = FREE_NEXT;
98 mono_lock_free_queue_enqueue (MonoLockFreeQueue *q, MonoLockFreeQueueNode *node)
100 MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
101 MonoLockFreeQueueNode *tail;
104 g_assert (!node->in_queue);
105 node->in_queue = TRUE;
106 mono_memory_write_barrier ();
109 g_assert (node->next == FREE_NEXT);
110 node->next = END_MARKER;
112 MonoLockFreeQueueNode *next;
114 tail = get_hazardous_pointer ((gpointer volatile*)&q->tail, hp, 0);
115 mono_memory_read_barrier ();
117 * We never dereference next so we don't need a
121 mono_memory_read_barrier ();
123 /* Are tail and next consistent? */
124 if (tail == q->tail) {
125 g_assert (next != INVALID_NEXT && next != FREE_NEXT);
126 g_assert (next != tail);
128 if (next == END_MARKER) {
130 * Here we require that nodes that
131 * have been dequeued don't have
132 * next==END_MARKER. If they did, we
133 * might append to a node that isn't
134 * in the queue anymore here.
136 if (InterlockedCompareExchangePointer ((gpointer volatile*)&tail->next, node, END_MARKER) == END_MARKER)
139 /* Try to advance tail */
140 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, next, tail);
144 mono_memory_write_barrier ();
145 mono_hazard_pointer_clear (hp, 0);
148 /* Try to advance tail */
149 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, node, tail);
151 mono_memory_write_barrier ();
152 mono_hazard_pointer_clear (hp, 0);
156 free_dummy (gpointer _dummy)
158 MonoLockFreeQueueDummy *dummy = _dummy;
159 mono_lock_free_queue_node_free (&dummy->node);
160 g_assert (dummy->in_use);
161 mono_memory_write_barrier ();
165 static MonoLockFreeQueueDummy*
166 get_dummy (MonoLockFreeQueue *q)
169 for (i = 0; i < MONO_LOCK_FREE_QUEUE_NUM_DUMMIES; ++i) {
170 MonoLockFreeQueueDummy *dummy = &q->dummies [i];
175 if (InterlockedCompareExchange (&dummy->in_use, 1, 0) == 0)
182 is_dummy (MonoLockFreeQueue *q, MonoLockFreeQueueNode *n)
184 return n >= &q->dummies [0].node && n < &q->dummies [MONO_LOCK_FREE_QUEUE_NUM_DUMMIES].node;
188 try_reenqueue_dummy (MonoLockFreeQueue *q)
190 MonoLockFreeQueueDummy *dummy;
195 dummy = get_dummy (q);
199 if (InterlockedCompareExchange (&q->has_dummy, 1, 0) != 0) {
204 mono_lock_free_queue_enqueue (q, &dummy->node);
209 MonoLockFreeQueueNode*
210 mono_lock_free_queue_dequeue (MonoLockFreeQueue *q)
212 MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
213 MonoLockFreeQueueNode *head;
217 MonoLockFreeQueueNode *tail, *next;
219 head = get_hazardous_pointer ((gpointer volatile*)&q->head, hp, 0);
220 tail = (MonoLockFreeQueueNode*)q->tail;
221 mono_memory_read_barrier ();
223 mono_memory_read_barrier ();
225 /* Are head, tail and next consistent? */
226 if (head == q->head) {
227 g_assert (next != INVALID_NEXT && next != FREE_NEXT);
228 g_assert (next != head);
230 /* Is queue empty or tail behind? */
232 if (next == END_MARKER) {
234 mono_hazard_pointer_clear (hp, 0);
237 * We only continue if we
238 * reenqueue the dummy
239 * ourselves, so as not to
240 * wait for threads that might
243 if (!is_dummy (q, head) && try_reenqueue_dummy (q))
249 /* Try to advance tail */
250 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, next, tail);
252 g_assert (next != END_MARKER);
253 /* Try to dequeue head */
254 if (InterlockedCompareExchangePointer ((gpointer volatile*)&q->head, next, head) == head)
259 mono_memory_write_barrier ();
260 mono_hazard_pointer_clear (hp, 0);
264 * The head is dequeued now, so we know it's this thread's
265 * responsibility to free it - no other thread can.
267 mono_memory_write_barrier ();
268 mono_hazard_pointer_clear (hp, 0);
270 g_assert (head->next);
272 * Setting next here isn't necessary for correctness, but we
273 * do it to make sure that we catch dereferencing next in a
274 * node that's not in the queue anymore.
276 head->next = INVALID_NEXT;
278 g_assert (head->in_queue);
279 head->in_queue = FALSE;
280 mono_memory_write_barrier ();
283 if (is_dummy (q, head)) {
284 g_assert (q->has_dummy);
286 mono_memory_write_barrier ();
287 mono_thread_hazardous_free_or_queue (head, free_dummy);
288 if (try_reenqueue_dummy (q))
293 /* The caller must hazardously free the node. */