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