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 #ifdef HAVE_UNISTD_H
  51 #include <unistd.h>
  52 #endif
  53
  54 #include <mono/utils/mono-membar.h>
  55 #include <mono/utils/hazard-pointer.h>
  56 #include <mono/utils/atomic.h>
  57
  58 #include <mono/utils/lock-free-queue.h>
  59
  60 #define INVALID_NEXT    ((MonoLockFreeQueueNode *volatile)-1)
  61 #define END_MARKER      ((MonoLockFreeQueueNode *volatile)-2)
  62 #define FREE_NEXT       ((MonoLockFreeQueueNode *volatile)-3)
  63
  64 void
  65 mono_lock_free_queue_init (MonoLockFreeQueue *q)
  66 {
  67         int i;
  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;
  71 #ifdef QUEUE_DEBUG
  72                 q->dummies [i].node.in_queue = i == 0 ? TRUE : FALSE;
  73 #endif
  74         }
  75
  76         q->head = q->tail = &q->dummies [0].node;
  77         q->has_dummy = 1;
  78 }
  79
  80 void
  81 mono_lock_free_queue_node_init (MonoLockFreeQueueNode *node, gboolean to_be_freed)
  82 {
  83         node->next = to_be_freed ? INVALID_NEXT : FREE_NEXT;
  84 #ifdef QUEUE_DEBUG
  85         node->in_queue = FALSE;
  86 #endif
  87 }
  88
  89 void
  90 mono_lock_free_queue_node_free (MonoLockFreeQueueNode *node)
  91 {
  92         g_assert (node->next == INVALID_NEXT);
  93 #ifdef QUEUE_DEBUG
  94         g_assert (!node->in_queue);
  95 #endif
  96         node->next = FREE_NEXT;
  97 }
  98
  99 void
 100 mono_lock_free_queue_enqueue (MonoLockFreeQueue *q, MonoLockFreeQueueNode *node)
 101 {
 102         MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
 103         MonoLockFreeQueueNode *tail;
 104
 105 #ifdef QUEUE_DEBUG
 106         g_assert (!node->in_queue);
 107         node->in_queue = TRUE;
 108         mono_memory_write_barrier ();
 109 #endif
 110
 111         g_assert (node->next == FREE_NEXT);
 112         node->next = END_MARKER;
 113         for (;;) {
 114                 MonoLockFreeQueueNode *next;
 115
 116                 tail = (MonoLockFreeQueueNode *) get_hazardous_pointer ((gpointer volatile*)&q->tail, hp, 0);
 117                 mono_memory_read_barrier ();
 118                 /*
 119                  * We never dereference next so we don't need a
 120                  * hazardous load.
 121                  */
 122                 next = tail->next;
 123                 mono_memory_read_barrier ();
 124
 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);
 129
 130                         if (next == END_MARKER) {
 131                                 /*
 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.
 137                                  */
 138                                 if (InterlockedCompareExchangePointer ((gpointer volatile*)&tail->next, node, END_MARKER) == END_MARKER)
 139                                         break;
 140                         } else {
 141                                 /* Try to advance tail */
 142                                 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, next, tail);
 143                         }
 144                 }
 145
 146                 mono_memory_write_barrier ();
 147                 mono_hazard_pointer_clear (hp, 0);
 148         }
 149
 150         /* Try to advance tail */
 151         InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, node, tail);
 152
 153         mono_memory_write_barrier ();
 154         mono_hazard_pointer_clear (hp, 0);
 155 }
 156
 157 static void
 158 free_dummy (gpointer _dummy)
 159 {
 160         MonoLockFreeQueueDummy *dummy = (MonoLockFreeQueueDummy *) _dummy;
 161         mono_lock_free_queue_node_free (&dummy->node);
 162         g_assert (dummy->in_use);
 163         mono_memory_write_barrier ();
 164         dummy->in_use = 0;
 165 }
 166
 167 static MonoLockFreeQueueDummy*
 168 get_dummy (MonoLockFreeQueue *q)
 169 {
 170         int i;
 171         for (i = 0; i < MONO_LOCK_FREE_QUEUE_NUM_DUMMIES; ++i) {
 172                 MonoLockFreeQueueDummy *dummy = &q->dummies [i];
 173
 174                 if (dummy->in_use)
 175                         continue;
 176
 177                 if (InterlockedCompareExchange (&dummy->in_use, 1, 0) == 0)
 178                         return dummy;
 179         }
 180         return NULL;
 181 }
 182
 183 static gboolean
 184 is_dummy (MonoLockFreeQueue *q, MonoLockFreeQueueNode *n)
 185 {
 186         return n >= &q->dummies [0].node && n < &q->dummies [MONO_LOCK_FREE_QUEUE_NUM_DUMMIES].node;
 187 }
 188
 189 static gboolean
 190 try_reenqueue_dummy (MonoLockFreeQueue *q)
 191 {
 192         MonoLockFreeQueueDummy *dummy;
 193
 194         if (q->has_dummy)
 195                 return FALSE;
 196
 197         dummy = get_dummy (q);
 198         if (!dummy)
 199                 return FALSE;
 200
 201         if (InterlockedCompareExchange (&q->has_dummy, 1, 0) != 0) {
 202                 dummy->in_use = 0;
 203                 return FALSE;
 204         }
 205
 206         mono_lock_free_queue_enqueue (q, &dummy->node);
 207
 208         return TRUE;
 209 }
 210
 211 MonoLockFreeQueueNode*
 212 mono_lock_free_queue_dequeue (MonoLockFreeQueue *q)
 213 {
 214         MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
 215         MonoLockFreeQueueNode *head;
 216
 217  retry:
 218         for (;;) {
 219                 MonoLockFreeQueueNode *tail, *next;
 220
 221                 head = (MonoLockFreeQueueNode *) get_hazardous_pointer ((gpointer volatile*)&q->head, hp, 0);
 222                 tail = (MonoLockFreeQueueNode*)q->tail;
 223                 mono_memory_read_barrier ();
 224                 next = head->next;
 225                 mono_memory_read_barrier ();
 226
 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);
 231
 232                         /* Is queue empty or tail behind? */
 233                         if (head == tail) {
 234                                 if (next == END_MARKER) {
 235                                         /* Queue is empty */
 236                                         mono_hazard_pointer_clear (hp, 0);
 237
 238                                         /*
 239                                          * We only continue if we
 240                                          * reenqueue the dummy
 241                                          * ourselves, so as not to
 242                                          * wait for threads that might
 243                                          * not actually run.
 244                                          */
 245                                         if (!is_dummy (q, head) && try_reenqueue_dummy (q))
 246                                                 continue;
 247
 248                                         return NULL;
 249                                 }
 250
 251                                 /* Try to advance tail */
 252                                 InterlockedCompareExchangePointer ((gpointer volatile*)&q->tail, next, tail);
 253                         } else {
 254                                 g_assert (next != END_MARKER);
 255                                 /* Try to dequeue head */
 256                                 if (InterlockedCompareExchangePointer ((gpointer volatile*)&q->head, next, head) == head)
 257                                         break;
 258                         }
 259                 }
 260
 261                 mono_memory_write_barrier ();
 262                 mono_hazard_pointer_clear (hp, 0);
 263         }
 264
 265         /*
 266          * The head is dequeued now, so we know it's this thread's
 267          * responsibility to free it - no other thread can.
 268          */
 269         mono_memory_write_barrier ();
 270         mono_hazard_pointer_clear (hp, 0);
 271
 272         g_assert (head->next);
 273         /*
 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.
 277          */
 278         head->next = INVALID_NEXT;
 279 #if QUEUE_DEBUG
 280         g_assert (head->in_queue);
 281         head->in_queue = FALSE;
 282         mono_memory_write_barrier ();
 283 #endif
 284
 285         if (is_dummy (q, head)) {
 286                 g_assert (q->has_dummy);
 287                 q->has_dummy = 0;
 288                 mono_memory_write_barrier ();
 289                 mono_thread_hazardous_try_free (head, free_dummy);
 290                 if (try_reenqueue_dummy (q))
 291                         goto retry;
 292                 return NULL;
 293         }
 294
 295         /* The caller must hazardously free the node. */
 296         return head;
 297 }