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