mono/utils/lock-free-queue.c

   1 /*
   2  * lock-free-queue.c: Lock free queue.
   3  *
   4  * (C) Copyright 2011 Novell, Inc
   5  *
   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:
  13  *
  14  * The above copyright notice and this permission notice shall be
  15  * included in all copies or substantial portions of the Software.
  16  *
  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.
  24  */
  25
  26 /*
  27  * This is an implementation of a lock-free queue, as described in
  28  *
  29  * Simple, Fast, and Practical Non-Blocking and Blocking
  30  *   Concurrent Queue Algorithms
  31  * Maged M. Michael, Michael L. Scott
  32  * 1995
  33  *
  34  * A few slight modifications have been made:
  35  *
  36  * We use hazard pointers to rule out the ABA problem, instead of the
  37  * counter as in the paper.
  38  *
  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.
  42  *
  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.
  47  */
  48
  49 #include <stdlib.h>
  50 #include <unistd.h>
  51
  52 #include <mono/utils/mono-membar.h>
  53 #include <mono/utils/hazard-pointer.h>
  54 #include <mono/io-layer/io-layer.h>
  55
  56 #include <mono/utils/lock-free-queue.h>
  57
  58 #define INVALID_NEXT    ((void*)-1)
  59 #define END_MARKER      ((void*)-2)
  60 #define FREE_NEXT       ((void*)-3)
  61
  62 void
  63 mono_lock_free_queue_init (MonoLockFreeQueue *q)
  64 {
  65         int i;
  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;
  69 #ifdef QUEUE_DEBUG
  70                 q->dummies [i].node.in_queue = i == 0 ? TRUE : FALSE;
  71 #endif
  72         }
  73
  74         q->head = q->tail = &q->dummies [0].node;
  75         q->has_dummy = 1;
  76 }
  77
  78 void
  79 mono_lock_free_queue_node_init (MonoLockFreeQueueNode *node, gboolean to_be_freed)
  80 {
  81         node->next = to_be_freed ? INVALID_NEXT : FREE_NEXT;
  82 #ifdef QUEUE_DEBUG
  83         node->in_queue = FALSE;
  84 #endif
  85 }
  86
  87 void
  88 mono_lock_free_queue_node_free (MonoLockFreeQueueNode *node)
  89 {
  90         g_assert (node->next == INVALID_NEXT);
  91 #ifdef QUEUE_DEBUG
  92         g_assert (!node->in_queue);
  93 #endif
  94         node->next = FREE_NEXT;
  95 }
  96
  97 void
  98 mono_lock_free_queue_enqueue (MonoLockFreeQueue *q, MonoLockFreeQueueNode *node)
  99 {
 100         MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
 101         MonoLockFreeQueueNode *tail;
 102
 103 #ifdef QUEUE_DEBUG
 104         g_assert (!node->in_queue);
 105         node->in_queue = TRUE;
 106         mono_memory_write_barrier ();
 107 #endif
 108
 109         g_assert (node->next == FREE_NEXT);
 110         node->next = END_MARKER;
 111         for (;;) {
 112                 MonoLockFreeQueueNode *next;
 113
 114                 tail = get_hazardous_pointer ((gpointer volatile*)&q->tail, hp, 0);
 115                 mono_memory_read_barrier ();
 116                 /*
 117                  * We never dereference next so we don't need a
 118                  * hazardous load.
 119                  */
 120                 next = tail->next;
 121                 mono_memory_read_barrier ();
 122
 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);
 127
 128                         if (next == END_MARKER) {
 129                                 /*
 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.
 135                                  */
 136                                 if (InterlockedCompareExchangePointer ((gpointer volatile*)&tail->next, node, END_MARKER) == END_MARKER)
 137                                         break;
 138                         } else {
 139                                 /* Try to advance tail */
 140                                 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, next, tail);
 141                         }
 142                 }
 143
 144                 mono_memory_write_barrier ();
 145                 mono_hazard_pointer_clear (hp, 0);
 146         }
 147
 148         /* Try to advance tail */
 149         InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, node, tail);
 150
 151         mono_memory_write_barrier ();
 152         mono_hazard_pointer_clear (hp, 0);
 153 }
 154
 155 static void
 156 free_dummy (gpointer _dummy)
 157 {
 158         MonoLockFreeQueueDummy *dummy = _dummy;
 159         mono_lock_free_queue_node_free (&dummy->node);
 160         g_assert (dummy->in_use);
 161         mono_memory_write_barrier ();
 162         dummy->in_use = 0;
 163 }
 164
 165 static MonoLockFreeQueueDummy*
 166 get_dummy (MonoLockFreeQueue *q)
 167 {
 168         int i;
 169         for (i = 0; i < MONO_LOCK_FREE_QUEUE_NUM_DUMMIES; ++i) {
 170                 MonoLockFreeQueueDummy *dummy = &q->dummies [i];
 171
 172                 if (dummy->in_use)
 173                         continue;
 174
 175                 if (InterlockedCompareExchange (&dummy->in_use, 1, 0) == 0)
 176                         return dummy;
 177         }
 178         return NULL;
 179 }
 180
 181 static gboolean
 182 is_dummy (MonoLockFreeQueue *q, MonoLockFreeQueueNode *n)
 183 {
 184         return n >= &q->dummies [0].node && n < &q->dummies [MONO_LOCK_FREE_QUEUE_NUM_DUMMIES].node;
 185 }
 186
 187 static gboolean
 188 try_reenqueue_dummy (MonoLockFreeQueue *q)
 189 {
 190         MonoLockFreeQueueDummy *dummy;
 191
 192         if (q->has_dummy)
 193                 return FALSE;
 194
 195         dummy = get_dummy (q);
 196         if (!dummy)
 197                 return FALSE;
 198
 199         if (InterlockedCompareExchange (&q->has_dummy, 1, 0) != 0) {
 200                 dummy->in_use = 0;
 201                 return FALSE;
 202         }
 203
 204         mono_lock_free_queue_enqueue (q, &dummy->node);
 205
 206         return TRUE;
 207 }
 208
 209 MonoLockFreeQueueNode*
 210 mono_lock_free_queue_dequeue (MonoLockFreeQueue *q)
 211 {
 212         MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
 213         MonoLockFreeQueueNode *head;
 214
 215  retry:
 216         for (;;) {
 217                 MonoLockFreeQueueNode *tail, *next;
 218
 219                 head = get_hazardous_pointer ((gpointer volatile*)&q->head, hp, 0);
 220                 tail = (MonoLockFreeQueueNode*)q->tail;
 221                 mono_memory_read_barrier ();
 222                 next = head->next;
 223                 mono_memory_read_barrier ();
 224
 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);
 229
 230                         /* Is queue empty or tail behind? */
 231                         if (head == tail) {
 232                                 if (next == END_MARKER) {
 233                                         /* Queue is empty */
 234                                         mono_hazard_pointer_clear (hp, 0);
 235
 236                                         /*
 237                                          * We only continue if we
 238                                          * reenqueue the dummy
 239                                          * ourselves, so as not to
 240                                          * wait for threads that might
 241                                          * not actually run.
 242                                          */
 243                                         if (!is_dummy (q, head) && try_reenqueue_dummy (q))
 244                                                 continue;
 245
 246                                         return NULL;
 247                                 }
 248
 249                                 /* Try to advance tail */
 250                                 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, next, tail);
 251                         } else {
 252                                 g_assert (next != END_MARKER);
 253                                 /* Try to dequeue head */
 254                                 if (InterlockedCompareExchangePointer ((gpointer volatile*)&q->head, next, head) == head)
 255                                         break;
 256                         }
 257                 }
 258
 259                 mono_memory_write_barrier ();
 260                 mono_hazard_pointer_clear (hp, 0);
 261         }
 262
 263         /*
 264          * The head is dequeued now, so we know it's this thread's
 265          * responsibility to free it - no other thread can.
 266          */
 267         mono_memory_write_barrier ();
 268         mono_hazard_pointer_clear (hp, 0);
 269
 270         g_assert (head->next);
 271         /*
 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.
 275          */
 276         head->next = INVALID_NEXT;
 277 #if QUEUE_DEBUG
 278         g_assert (head->in_queue);
 279         head->in_queue = FALSE;
 280         mono_memory_write_barrier ();
 281 #endif
 282
 283         if (is_dummy (q, head)) {
 284                 g_assert (q->has_dummy);
 285                 q->has_dummy = 0;
 286                 mono_memory_write_barrier ();
 287                 mono_thread_hazardous_free_or_queue (head, free_dummy);
 288                 if (try_reenqueue_dummy (q))
 289                         goto retry;
 290                 return NULL;
 291         }
 292
 293         /* The caller must hazardously free the node. */
 294         return head;
 295 }