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