mono/metadata/mono-wsq.c

   1 /*
   2  * mono-wsq.c: work-stealing queue
   3  *
   4  * Authors:
   5  *   Gonzalo Paniagua Javier (gonzalo@novell.com)
   6  *
   7  * Copyright (c) 2010 Novell, Inc (http://www.novell.com)
   8  * Copyright 2011 Xamarin, Inc (http://www.xamarin.com)
   9  */
  10
  11 #include <string.h>
  12 #include <mono/metadata/object.h>
  13 #include <mono/metadata/mono-wsq.h>
  14 #include <mono/utils/mono-semaphore.h>
  15 #include <mono/utils/mono-tls.h>
  16 #include <mono/utils/atomic.h>
  17
  18 #define INITIAL_LENGTH  32
  19 #define WSQ_DEBUG(...)
  20 //#define WSQ_DEBUG(...) g_message(__VA_ARGS__)
  21
  22 struct _MonoWSQ {
  23         volatile gint head;
  24         volatile gint tail;
  25         MonoArray *queue;
  26         gint32 mask;
  27         MonoSemType lock;
  28 };
  29
  30 #define NO_KEY ((guint32) -1)
  31 static MonoNativeTlsKey wsq_tlskey;
  32 static gboolean wsq_tlskey_inited = FALSE;
  33
  34 void
  35 mono_wsq_init ()
  36 {
  37         if (wsq_tlskey_inited)
  38                 return;
  39
  40         mono_native_tls_alloc (&wsq_tlskey, NULL);
  41         wsq_tlskey_inited = TRUE;
  42 }
  43
  44 void
  45 mono_wsq_cleanup ()
  46 {
  47         if (!wsq_tlskey_inited)
  48                 return;
  49         mono_native_tls_free (wsq_tlskey);
  50         wsq_tlskey_inited = FALSE;
  51 }
  52
  53 MonoWSQ *
  54 mono_wsq_create ()
  55 {
  56         MonoWSQ *wsq;
  57         MonoDomain *root;
  58
  59         if (!wsq_tlskey_inited)
  60                 return NULL;
  61
  62         wsq = g_new0 (MonoWSQ, 1);
  63         wsq->mask = INITIAL_LENGTH - 1;
  64         MONO_GC_REGISTER_ROOT_SINGLE (wsq->queue);
  65         root = mono_get_root_domain ();
  66         wsq->queue = mono_array_new_cached (root, mono_defaults.object_class, INITIAL_LENGTH);
  67         MONO_SEM_INIT (&wsq->lock, 1);
  68         if (!mono_native_tls_set_value (wsq_tlskey, wsq)) {
  69                 mono_wsq_destroy (wsq);
  70                 wsq = NULL;
  71         }
  72         return wsq;
  73 }
  74
  75 void
  76 mono_wsq_destroy (MonoWSQ *wsq)
  77 {
  78         if (wsq == NULL || wsq->queue == NULL)
  79                 return;
  80
  81         g_assert (mono_wsq_count (wsq) == 0);
  82         MONO_GC_UNREGISTER_ROOT (wsq->queue);
  83         MONO_SEM_DESTROY (&wsq->lock);
  84         memset (wsq, 0, sizeof (MonoWSQ));
  85         if (wsq_tlskey_inited && mono_native_tls_get_value (wsq_tlskey) == wsq)
  86                 mono_native_tls_set_value (wsq_tlskey, NULL);
  87         g_free (wsq);
  88 }
  89
  90 gint
  91 mono_wsq_count (MonoWSQ *wsq)
  92 {
  93         if (!wsq)
  94                 return 0;
  95         return ((wsq->tail - wsq->head) & wsq->mask);
  96 }
  97
  98 gboolean
  99 mono_wsq_local_push (void *obj)
 100 {
 101         int tail;
 102         int head;
 103         int count;
 104         MonoWSQ *wsq;
 105
 106         if (obj == NULL || !wsq_tlskey_inited)
 107                 return FALSE;
 108
 109         wsq = (MonoWSQ *) mono_native_tls_get_value (wsq_tlskey);
 110         if (wsq == NULL) {
 111                 WSQ_DEBUG ("local_push: no wsq\n");
 112                 return FALSE;
 113         }
 114
 115         tail = wsq->tail;
 116         if (tail < wsq->head + wsq->mask) {
 117                 mono_array_setref (wsq->queue, tail & wsq->mask, (MonoObject *) obj);
 118                 wsq->tail = tail + 1;
 119                 WSQ_DEBUG ("local_push: OK %p %p\n", wsq, obj);
 120                 return TRUE;
 121         }
 122
 123         MONO_SEM_WAIT (&wsq->lock);
 124         head = wsq->head;
 125         count = wsq->tail - wsq->head;
 126         if (count >= wsq->mask) {
 127                 MonoArray *new_array;
 128                 int length;
 129                 int i;
 130
 131                 length = mono_array_length (wsq->queue);
 132                 new_array = mono_array_new_cached (mono_get_root_domain (), mono_defaults.object_class, length * 2);
 133                 for (i = 0; i < length; i++)
 134                         mono_array_setref (new_array, i, mono_array_get (wsq->queue, MonoObject*, (i + head) & wsq->mask));
 135
 136                 mono_gc_bzero_aligned (mono_array_addr (wsq->queue, MonoObject *, 0), sizeof (MonoObject*) * length);
 137                 wsq->queue = new_array;
 138                 wsq->head = 0;
 139                 wsq->tail = tail = count;
 140                 wsq->mask = (wsq->mask << 1) | 1;
 141         }
 142         mono_array_setref (wsq->queue, tail & wsq->mask, obj);
 143         wsq->tail = tail + 1;
 144         MONO_SEM_POST (&wsq->lock);
 145         WSQ_DEBUG ("local_push: LOCK %p  %p\n", wsq, obj);
 146         return TRUE;
 147 }
 148
 149 gboolean
 150 mono_wsq_local_pop (void **ptr)
 151 {
 152         int tail;
 153         gboolean res;
 154         MonoWSQ *wsq;
 155
 156         if (ptr == NULL || !wsq_tlskey_inited)
 157                 return FALSE;
 158
 159         wsq = (MonoWSQ *) mono_native_tls_get_value (wsq_tlskey);
 160         if (wsq == NULL) {
 161                 WSQ_DEBUG ("local_pop: no wsq\n");
 162                 return FALSE;
 163         }
 164
 165         tail = wsq->tail;
 166         if (wsq->head >= tail) {
 167                 WSQ_DEBUG ("local_pop: empty\n");
 168                 return FALSE;
 169         }
 170         tail--;
 171         InterlockedExchange (&wsq->tail, tail);
 172         if (wsq->head <= tail) {
 173                 *ptr = mono_array_get (wsq->queue, void *, tail & wsq->mask);
 174                 mono_array_set (wsq->queue, void *, tail & wsq->mask, NULL);
 175                 WSQ_DEBUG ("local_pop: GOT ONE %p %p\n", wsq, *ptr);
 176                 return TRUE;
 177         }
 178
 179         MONO_SEM_WAIT (&wsq->lock);
 180         if (wsq->head <= tail) {
 181                 *ptr = mono_array_get (wsq->queue, void *, tail & wsq->mask);
 182                 mono_array_set (wsq->queue, void *, tail & wsq->mask, NULL);
 183                 res = TRUE;
 184         } else {
 185                 wsq->tail = tail + 1;
 186                 res = FALSE;
 187         }
 188         MONO_SEM_POST (&wsq->lock);
 189         WSQ_DEBUG ("local_pop: LOCK %d %p %p\n", res, wsq, *ptr);
 190         return res;
 191 }
 192
 193 void
 194 mono_wsq_try_steal (MonoWSQ *wsq, void **ptr, guint32 ms_timeout)
 195 {
 196         if (wsq == NULL || ptr == NULL || *ptr != NULL || !wsq_tlskey_inited)
 197                 return;
 198
 199         if (mono_native_tls_get_value (wsq_tlskey) == wsq)
 200                 return;
 201
 202         if (mono_sem_timedwait (&wsq->lock, ms_timeout, FALSE) == 0) {
 203                 int head;
 204
 205                 head = wsq->head;
 206                 InterlockedExchange (&wsq->head, head + 1);
 207                 if (head < wsq->tail) {
 208                         *ptr = mono_array_get (wsq->queue, void *, head & wsq->mask);
 209                         mono_array_set (wsq->queue, void *, head & wsq->mask, NULL);
 210                         WSQ_DEBUG ("STEAL %p %p\n", wsq, *ptr);
 211                 } else {
 212                         wsq->head = head;
 213                 }
 214                 MONO_SEM_POST (&wsq->lock);
 215         }
 216 }
 217