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