5 * (C) Copyright 2011 Novell, Inc
7 * Permission is hereby granted, free of charge, to any person obtaining
8 * a copy of this software and associated documentation files (the
9 * "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sublicense, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
28 * This is an implementation of a lock-free queue, as described in
30 * Simple, Fast, and Practical Non-Blocking and Blocking
31 * Concurrent Queue Algorithms
32 * Maged M. Michael, Michael L. Scott
35 * A few slight modifications have been made:
37 * We use hazard pointers to rule out the ABA problem, instead of the
38 * counter as in the paper.
40 * Memory management of the queue entries is done by the caller, not
41 * by the queue implementation. This implies that the dequeue
42 * function must return the queue entry, not just the data.
44 * Therefore, the dummy entry must never be returned. We do this by
45 * re-enqueuing a new dummy entry after we dequeue one and then
46 * retrying the dequeue. We need more than one dummy because they
47 * must be hazardly freed.
55 #include <mono/utils/mono-membar.h>
56 #include <mono/utils/hazard-pointer.h>
57 #include <mono/utils/atomic.h>
59 #include <mono/utils/lock-free-queue.h>
61 #define INVALID_NEXT ((MonoLockFreeQueueNode *volatile)-1)
62 #define END_MARKER ((MonoLockFreeQueueNode *volatile)-2)
63 #define FREE_NEXT ((MonoLockFreeQueueNode *volatile)-3)
66 * Initialize a lock-free queue in-place at @q.
69 mono_lock_free_queue_init (MonoLockFreeQueue *q)
72 for (i = 0; i < MONO_LOCK_FREE_QUEUE_NUM_DUMMIES; ++i) {
73 q->dummies [i].node.next = (i == 0) ? END_MARKER : FREE_NEXT;
74 q->dummies [i].in_use = i == 0 ? 1 : 0;
76 q->dummies [i].node.in_queue = i == 0 ? TRUE : FALSE;
80 q->head = q->tail = &q->dummies [0].node;
85 * Initialize @node's state. If @poison is TRUE, @node may not be enqueued to a
86 * queue - @mono_lock_free_queue_node_unpoison must be called first; otherwise,
87 * the node can be enqueued right away.
89 * The poisoning feature is mainly intended for ensuring correctness in complex
90 * lock-free code that uses the queue. For example, in some code that reuses
91 * nodes, nodes can be poisoned when they're dequeued, and then unpoisoned and
92 * enqueued in their hazard free callback.
95 mono_lock_free_queue_node_init (MonoLockFreeQueueNode *node, gboolean poison)
97 node->next = poison ? INVALID_NEXT : FREE_NEXT;
99 node->in_queue = FALSE;
104 * Unpoisons @node so that it may be enqueued.
107 mono_lock_free_queue_node_unpoison (MonoLockFreeQueueNode *node)
109 g_assert (node->next == INVALID_NEXT);
111 g_assert (!node->in_queue);
113 node->next = FREE_NEXT;
117 * Enqueue @node to @q. @node must have been initialized by a prior call to
118 * @mono_lock_free_queue_node_init, and must not be in a poisoned state.
121 mono_lock_free_queue_enqueue (MonoLockFreeQueue *q, MonoLockFreeQueueNode *node)
123 MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
124 MonoLockFreeQueueNode *tail;
127 g_assert (!node->in_queue);
128 node->in_queue = TRUE;
129 mono_memory_write_barrier ();
132 g_assert (node->next == FREE_NEXT);
133 node->next = END_MARKER;
135 MonoLockFreeQueueNode *next;
137 tail = (MonoLockFreeQueueNode *) mono_get_hazardous_pointer ((gpointer volatile*)&q->tail, hp, 0);
138 mono_memory_read_barrier ();
140 * We never dereference next so we don't need a
144 mono_memory_read_barrier ();
146 /* Are tail and next consistent? */
147 if (tail == q->tail) {
148 g_assert (next != INVALID_NEXT && next != FREE_NEXT);
149 g_assert (next != tail);
151 if (next == END_MARKER) {
153 * Here we require that nodes that
154 * have been dequeued don't have
155 * next==END_MARKER. If they did, we
156 * might append to a node that isn't
157 * in the queue anymore here.
159 if (InterlockedCompareExchangePointer ((gpointer volatile*)&tail->next, node, END_MARKER) == END_MARKER)
162 /* Try to advance tail */
163 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, next, tail);
167 mono_memory_write_barrier ();
168 mono_hazard_pointer_clear (hp, 0);
171 /* Try to advance tail */
172 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, node, tail);
174 mono_memory_write_barrier ();
175 mono_hazard_pointer_clear (hp, 0);
179 free_dummy (gpointer _dummy)
181 MonoLockFreeQueueDummy *dummy = (MonoLockFreeQueueDummy *) _dummy;
182 mono_lock_free_queue_node_unpoison (&dummy->node);
183 g_assert (dummy->in_use);
184 mono_memory_write_barrier ();
188 static MonoLockFreeQueueDummy*
189 get_dummy (MonoLockFreeQueue *q)
192 for (i = 0; i < MONO_LOCK_FREE_QUEUE_NUM_DUMMIES; ++i) {
193 MonoLockFreeQueueDummy *dummy = &q->dummies [i];
198 if (InterlockedCompareExchange (&dummy->in_use, 1, 0) == 0)
205 is_dummy (MonoLockFreeQueue *q, MonoLockFreeQueueNode *n)
207 return n >= &q->dummies [0].node && n <= &q->dummies [MONO_LOCK_FREE_QUEUE_NUM_DUMMIES-1].node;
211 try_reenqueue_dummy (MonoLockFreeQueue *q)
213 MonoLockFreeQueueDummy *dummy;
218 dummy = get_dummy (q);
222 if (InterlockedCompareExchange (&q->has_dummy, 1, 0) != 0) {
227 mono_lock_free_queue_enqueue (q, &dummy->node);
233 * Dequeues a node from @q. Returns NULL if no nodes are available. The returned
234 * node is hazardous and must be freed with @mono_thread_hazardous_try_free or
235 * @mono_thread_hazardous_queue_free - it must not be freed directly.
237 MonoLockFreeQueueNode*
238 mono_lock_free_queue_dequeue (MonoLockFreeQueue *q)
240 MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
241 MonoLockFreeQueueNode *head;
245 MonoLockFreeQueueNode *tail, *next;
247 head = (MonoLockFreeQueueNode *) mono_get_hazardous_pointer ((gpointer volatile*)&q->head, hp, 0);
248 tail = (MonoLockFreeQueueNode*)q->tail;
249 mono_memory_read_barrier ();
251 mono_memory_read_barrier ();
253 /* Are head, tail and next consistent? */
254 if (head == q->head) {
255 g_assert (next != INVALID_NEXT && next != FREE_NEXT);
256 g_assert (next != head);
258 /* Is queue empty or tail behind? */
260 if (next == END_MARKER) {
262 mono_hazard_pointer_clear (hp, 0);
265 * We only continue if we
266 * reenqueue the dummy
267 * ourselves, so as not to
268 * wait for threads that might
271 if (!is_dummy (q, head) && try_reenqueue_dummy (q))
277 /* Try to advance tail */
278 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, next, tail);
280 g_assert (next != END_MARKER);
281 /* Try to dequeue head */
282 if (InterlockedCompareExchangePointer ((gpointer volatile*)&q->head, next, head) == head)
287 mono_memory_write_barrier ();
288 mono_hazard_pointer_clear (hp, 0);
292 * The head is dequeued now, so we know it's this thread's
293 * responsibility to free it - no other thread can.
295 mono_memory_write_barrier ();
296 mono_hazard_pointer_clear (hp, 0);
298 g_assert (head->next);
300 * Setting next here isn't necessary for correctness, but we
301 * do it to make sure that we catch dereferencing next in a
302 * node that's not in the queue anymore.
304 head->next = INVALID_NEXT;
306 g_assert (head->in_queue);
307 head->in_queue = FALSE;
308 mono_memory_write_barrier ();
311 if (is_dummy (q, head)) {
312 g_assert (q->has_dummy);
314 mono_memory_write_barrier ();
315 mono_thread_hazardous_try_free (head, free_dummy);
316 if (try_reenqueue_dummy (q))
321 /* The caller must hazardously free the node. */