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