mono/utils/lock-free-array-queue.c

   1 /**
   2  * \file
   3  * A lock-free somewhat-queue that doesn't
   4  * require hazard pointers.
   5  *
   6  * (C) Copyright 2011 Xamarin Inc.
   7  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   8  */
   9
  10 /*
  11  * The queue is a linked list of arrays (chunks).  Chunks are never
  12  * removed from the list, only added to the end, in a lock-free manner.
  13  *
  14  * Adding or removing an entry in the queue is only possible at the
  15  * end.  To do so, the thread first has to increment or decrement
  16  * q->num_used_entries.  The entry thus added or removed now "belongs"
  17  * to that thread.  It first CASes the state to BUSY, writes/reads the
  18  * entry data, and then sets the state to USED or FREE.
  19  */
  20
  21 #include <string.h>
  22
  23 #include <mono/utils/atomic.h>
  24 #include <mono/utils/mono-membar.h>
  25 #ifdef SGEN_WITHOUT_MONO
  26 #include <mono/sgen/sgen-gc.h>
  27 #include <mono/sgen/sgen-client.h>
  28 #else
  29 #include <mono/utils/mono-mmap.h>
  30 #endif
  31
  32 #include <mono/utils/lock-free-array-queue.h>
  33
  34 struct _MonoLockFreeArrayChunk {
  35         MonoLockFreeArrayChunk *next;
  36         gint32 num_entries;
  37         char entries [MONO_ZERO_LEN_ARRAY];
  38 };
  39
  40 typedef MonoLockFreeArrayChunk Chunk;
  41
  42 #define CHUNK_NTH(arr,chunk,index)      ((chunk)->entries + (index) * (arr)->entry_size)
  43
  44 static Chunk*
  45 alloc_chunk (MonoLockFreeArray *arr)
  46 {
  47         int size = mono_pagesize ();
  48         int num_entries = (size - (sizeof (Chunk) - arr->entry_size * MONO_ZERO_LEN_ARRAY)) / arr->entry_size;
  49         Chunk *chunk = (Chunk *) mono_valloc (NULL, size, MONO_MMAP_READ | MONO_MMAP_WRITE, arr->account_type);
  50         g_assert (chunk);
  51         chunk->num_entries = num_entries;
  52         return chunk;
  53 }
  54
  55 static void
  56 free_chunk (Chunk *chunk, MonoMemAccountType type)
  57 {
  58         mono_vfree (chunk, mono_pagesize (), type);
  59 }
  60
  61 gpointer
  62 mono_lock_free_array_nth (MonoLockFreeArray *arr, int index)
  63 {
  64         Chunk *chunk;
  65
  66         g_assert (index >= 0);
  67
  68         if (!arr->chunk_list) {
  69                 chunk = alloc_chunk (arr);
  70                 mono_memory_write_barrier ();
  71                 if (InterlockedCompareExchangePointer ((volatile gpointer *)&arr->chunk_list, chunk, NULL) != NULL)
  72                         free_chunk (chunk, arr->account_type);
  73         }
  74
  75         chunk = arr->chunk_list;
  76         g_assert (chunk);
  77
  78         while (index >= chunk->num_entries) {
  79                 Chunk *next = chunk->next;
  80                 if (!next) {
  81                         next = alloc_chunk (arr);
  82                         mono_memory_write_barrier ();
  83                         if (InterlockedCompareExchangePointer ((volatile gpointer *) &chunk->next, next, NULL) != NULL) {
  84                                 free_chunk (next, arr->account_type);
  85                                 next = chunk->next;
  86                                 g_assert (next);
  87                         }
  88                 }
  89                 index -= chunk->num_entries;
  90                 chunk = next;
  91         }
  92
  93         return CHUNK_NTH (arr, chunk, index);
  94 }
  95
  96 gpointer
  97 mono_lock_free_array_iterate (MonoLockFreeArray *arr, MonoLockFreeArrayIterateFunc func, gpointer user_data)
  98 {
  99         Chunk *chunk;
 100         for (chunk = arr->chunk_list; chunk; chunk = chunk->next) {
 101                 int i;
 102                 for (i = 0; i < chunk->num_entries; ++i) {
 103                         gpointer result = func (i, CHUNK_NTH (arr, chunk, i), user_data);
 104                         if (result)
 105                                 return result;
 106                 }
 107         }
 108         return NULL;
 109 }
 110
 111 void
 112 mono_lock_free_array_cleanup (MonoLockFreeArray *arr)
 113 {
 114         Chunk *chunk;
 115
 116         chunk = arr->chunk_list;
 117         arr->chunk_list = NULL;
 118         while (chunk) {
 119                 Chunk *next = chunk->next;
 120                 free_chunk (chunk, arr->account_type);
 121                 chunk = next;
 122         }
 123 }
 124
 125 enum {
 126         STATE_FREE,
 127         STATE_USED,
 128         STATE_BUSY
 129 };
 130
 131 typedef struct {
 132         gint32 state;
 133         gpointer data [MONO_ZERO_LEN_ARRAY];
 134 } Entry;
 135
 136 typedef MonoLockFreeArrayQueue Queue;
 137
 138 /* The queue's entry size, calculated from the array's. */
 139 #define ENTRY_SIZE(q)   ((q)->array.entry_size - sizeof (gpointer))
 140
 141 void
 142 mono_lock_free_array_queue_push (MonoLockFreeArrayQueue *q, gpointer entry_data_ptr)
 143 {
 144         int index, num_used;
 145         Entry *entry;
 146
 147         do {
 148                 index = InterlockedIncrement (&q->num_used_entries) - 1;
 149                 entry = (Entry *) mono_lock_free_array_nth (&q->array, index);
 150         } while (InterlockedCompareExchange (&entry->state, STATE_BUSY, STATE_FREE) != STATE_FREE);
 151
 152         mono_memory_write_barrier ();
 153
 154         memcpy (entry->data, entry_data_ptr, ENTRY_SIZE (q));
 155
 156         mono_memory_write_barrier ();
 157
 158         entry->state = STATE_USED;
 159
 160         mono_memory_barrier ();
 161
 162         do {
 163                 num_used = q->num_used_entries;
 164                 if (num_used > index)
 165                         break;
 166         } while (InterlockedCompareExchange (&q->num_used_entries, index + 1, num_used) != num_used);
 167
 168         mono_memory_write_barrier ();
 169 }
 170
 171 gboolean
 172 mono_lock_free_array_queue_pop (MonoLockFreeArrayQueue *q, gpointer entry_data_ptr)
 173 {
 174         int index;
 175         Entry *entry;
 176
 177         do {
 178                 do {
 179                         index = q->num_used_entries;
 180                         if (index == 0)
 181                                 return FALSE;
 182                 } while (InterlockedCompareExchange (&q->num_used_entries, index - 1, index) != index);
 183
 184                 entry = (Entry *) mono_lock_free_array_nth (&q->array, index - 1);
 185         } while (InterlockedCompareExchange (&entry->state, STATE_BUSY, STATE_USED) != STATE_USED);
 186
 187         /* Reading the item must happen before CASing the state. */
 188         mono_memory_barrier ();
 189
 190         memcpy (entry_data_ptr, entry->data, ENTRY_SIZE (q));
 191
 192         mono_memory_barrier ();
 193
 194         entry->state = STATE_FREE;
 195
 196         mono_memory_write_barrier ();
 197
 198         return TRUE;
 199 }
 200
 201 void
 202 mono_lock_free_array_queue_cleanup (MonoLockFreeArrayQueue *q)
 203 {
 204         mono_lock_free_array_cleanup (&q->array);
 205         q->num_used_entries = 0;
 206 }