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.
54 #include <mono/utils/mono-membar.h>
55 #include <mono/utils/hazard-pointer.h>
56 #include <mono/io-layer/io-layer.h>
58 #include <mono/utils/lock-free-queue.h>
60 #define INVALID_NEXT ((void*)-1)
61 #define END_MARKER ((void*)-2)
62 #define FREE_NEXT ((void*)-3)
65 mono_lock_free_queue_init (MonoLockFreeQueue *q)
68 for (i = 0; i < MONO_LOCK_FREE_QUEUE_NUM_DUMMIES; ++i) {
69 q->dummies [i].node.next = (i == 0) ? END_MARKER : FREE_NEXT;
70 q->dummies [i].in_use = i == 0 ? 1 : 0;
72 q->dummies [i].node.in_queue = i == 0 ? TRUE : FALSE;
76 q->head = q->tail = &q->dummies [0].node;
81 mono_lock_free_queue_node_init (MonoLockFreeQueueNode *node, gboolean to_be_freed)
83 node->next = to_be_freed ? INVALID_NEXT : FREE_NEXT;
85 node->in_queue = FALSE;
90 mono_lock_free_queue_node_free (MonoLockFreeQueueNode *node)
92 g_assert (node->next == INVALID_NEXT);
94 g_assert (!node->in_queue);
96 node->next = FREE_NEXT;
100 mono_lock_free_queue_enqueue (MonoLockFreeQueue *q, MonoLockFreeQueueNode *node)
102 MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
103 MonoLockFreeQueueNode *tail;
106 g_assert (!node->in_queue);
107 node->in_queue = TRUE;
108 mono_memory_write_barrier ();
111 g_assert (node->next == FREE_NEXT);
112 node->next = END_MARKER;
114 MonoLockFreeQueueNode *next;
116 tail = get_hazardous_pointer ((gpointer volatile*)&q->tail, hp, 0);
117 mono_memory_read_barrier ();
119 * We never dereference next so we don't need a
123 mono_memory_read_barrier ();
125 /* Are tail and next consistent? */
126 if (tail == q->tail) {
127 g_assert (next != INVALID_NEXT && next != FREE_NEXT);
128 g_assert (next != tail);
130 if (next == END_MARKER) {
132 * Here we require that nodes that
133 * have been dequeued don't have
134 * next==END_MARKER. If they did, we
135 * might append to a node that isn't
136 * in the queue anymore here.
138 if (InterlockedCompareExchangePointer ((gpointer volatile*)&tail->next, node, END_MARKER) == END_MARKER)
141 /* Try to advance tail */
142 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, next, tail);
146 mono_memory_write_barrier ();
147 mono_hazard_pointer_clear (hp, 0);
150 /* Try to advance tail */
151 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, node, tail);
153 mono_memory_write_barrier ();
154 mono_hazard_pointer_clear (hp, 0);
158 free_dummy (gpointer _dummy)
160 MonoLockFreeQueueDummy *dummy = _dummy;
161 mono_lock_free_queue_node_free (&dummy->node);
162 g_assert (dummy->in_use);
163 mono_memory_write_barrier ();
167 static MonoLockFreeQueueDummy*
168 get_dummy (MonoLockFreeQueue *q)
171 for (i = 0; i < MONO_LOCK_FREE_QUEUE_NUM_DUMMIES; ++i) {
172 MonoLockFreeQueueDummy *dummy = &q->dummies [i];
177 if (InterlockedCompareExchange (&dummy->in_use, 1, 0) == 0)
184 is_dummy (MonoLockFreeQueue *q, MonoLockFreeQueueNode *n)
186 return n >= &q->dummies [0].node && n < &q->dummies [MONO_LOCK_FREE_QUEUE_NUM_DUMMIES].node;
190 try_reenqueue_dummy (MonoLockFreeQueue *q)
192 MonoLockFreeQueueDummy *dummy;
197 dummy = get_dummy (q);
201 if (InterlockedCompareExchange (&q->has_dummy, 1, 0) != 0) {
206 mono_lock_free_queue_enqueue (q, &dummy->node);
211 MonoLockFreeQueueNode*
212 mono_lock_free_queue_dequeue (MonoLockFreeQueue *q)
214 MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
215 MonoLockFreeQueueNode *head;
219 MonoLockFreeQueueNode *tail, *next;
221 head = get_hazardous_pointer ((gpointer volatile*)&q->head, hp, 0);
222 tail = (MonoLockFreeQueueNode*)q->tail;
223 mono_memory_read_barrier ();
225 mono_memory_read_barrier ();
227 /* Are head, tail and next consistent? */
228 if (head == q->head) {
229 g_assert (next != INVALID_NEXT && next != FREE_NEXT);
230 g_assert (next != head);
232 /* Is queue empty or tail behind? */
234 if (next == END_MARKER) {
236 mono_hazard_pointer_clear (hp, 0);
239 * We only continue if we
240 * reenqueue the dummy
241 * ourselves, so as not to
242 * wait for threads that might
245 if (!is_dummy (q, head) && try_reenqueue_dummy (q))
251 /* Try to advance tail */
252 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, next, tail);
254 g_assert (next != END_MARKER);
255 /* Try to dequeue head */
256 if (InterlockedCompareExchangePointer ((gpointer volatile*)&q->head, next, head) == head)
261 mono_memory_write_barrier ();
262 mono_hazard_pointer_clear (hp, 0);
266 * The head is dequeued now, so we know it's this thread's
267 * responsibility to free it - no other thread can.
269 mono_memory_write_barrier ();
270 mono_hazard_pointer_clear (hp, 0);
272 g_assert (head->next);
274 * Setting next here isn't necessary for correctness, but we
275 * do it to make sure that we catch dereferencing next in a
276 * node that's not in the queue anymore.
278 head->next = INVALID_NEXT;
280 g_assert (head->in_queue);
281 head->in_queue = FALSE;
282 mono_memory_write_barrier ();
285 if (is_dummy (q, head)) {
286 g_assert (q->has_dummy);
288 mono_memory_write_barrier ();
289 mono_thread_hazardous_free_or_queue (head, free_dummy, FALSE, TRUE);
290 if (try_reenqueue_dummy (q))
295 /* The caller must hazardously free the node. */