2 * mono-wsq.c: work-stealing queue
5 * Gonzalo Paniagua Javier (gonzalo@novell.com)
7 * Copyright (c) 2010 Novell, Inc (http://www.novell.com)
8 * Copyright 2011 Xamarin, Inc (http://www.xamarin.com)
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 #include <mono/utils/atomic.h>
18 #define INITIAL_LENGTH 32
19 #define WSQ_DEBUG(...)
20 //#define WSQ_DEBUG(...) g_message(__VA_ARGS__)
31 #define NO_KEY ((guint32) -1)
32 static MonoNativeTlsKey wsq_tlskey;
33 static gboolean wsq_tlskey_inited = FALSE;
38 if (wsq_tlskey_inited)
41 mono_native_tls_alloc (&wsq_tlskey, NULL);
42 wsq_tlskey_inited = TRUE;
48 if (!wsq_tlskey_inited)
50 mono_native_tls_free (wsq_tlskey);
51 wsq_tlskey_inited = FALSE;
60 if (!wsq_tlskey_inited)
63 wsq = g_new0 (MonoWSQ, 1);
64 wsq->mask = INITIAL_LENGTH - 1;
66 MONO_GC_REGISTER_ROOT_SINGLE (wsq->queue);
67 root = mono_get_root_domain ();
68 wsq->queue = mono_array_new_cached (root, mono_defaults.object_class, INITIAL_LENGTH);
69 MONO_SEM_INIT (&wsq->lock, 1);
70 if (!mono_native_tls_set_value (wsq_tlskey, wsq)) {
71 mono_wsq_destroy (wsq);
78 mono_wsq_suspend (MonoWSQ *wsq)
80 return InterlockedCompareExchange (&wsq->suspended, 1, 0) == 0;
84 mono_wsq_destroy (MonoWSQ *wsq)
86 if (wsq == NULL || wsq->queue == NULL)
89 g_assert (mono_wsq_count (wsq) == 0);
90 MONO_GC_UNREGISTER_ROOT (wsq->queue);
91 MONO_SEM_DESTROY (&wsq->lock);
92 memset (wsq, 0, sizeof (MonoWSQ));
93 if (wsq_tlskey_inited && mono_native_tls_get_value (wsq_tlskey) == wsq)
94 mono_native_tls_set_value (wsq_tlskey, NULL);
99 mono_wsq_count (MonoWSQ *wsq)
103 return ((wsq->tail - wsq->head) & wsq->mask);
107 mono_wsq_local_push (void *obj)
114 if (obj == NULL || !wsq_tlskey_inited)
117 wsq = (MonoWSQ *) mono_native_tls_get_value (wsq_tlskey);
119 WSQ_DEBUG ("local_push: no wsq\n");
123 if (wsq->suspended) {
124 WSQ_DEBUG ("local_push: wsq suspended\n");
129 if (tail < wsq->head + wsq->mask) {
130 mono_array_setref (wsq->queue, tail & wsq->mask, (MonoObject *) obj);
131 wsq->tail = tail + 1;
132 WSQ_DEBUG ("local_push: OK %p %p\n", wsq, obj);
136 MONO_SEM_WAIT (&wsq->lock);
138 count = wsq->tail - wsq->head;
139 if (count >= wsq->mask) {
140 MonoArray *new_array;
144 length = mono_array_length (wsq->queue);
145 new_array = mono_array_new_cached (mono_get_root_domain (), mono_defaults.object_class, length * 2);
146 for (i = 0; i < length; i++)
147 mono_array_setref (new_array, i, mono_array_get (wsq->queue, MonoObject*, (i + head) & wsq->mask));
149 mono_gc_bzero_aligned (mono_array_addr (wsq->queue, MonoObject *, 0), sizeof (MonoObject*) * length);
150 wsq->queue = new_array;
152 wsq->tail = tail = count;
153 wsq->mask = (wsq->mask << 1) | 1;
155 mono_array_setref (wsq->queue, tail & wsq->mask, obj);
156 wsq->tail = tail + 1;
157 MONO_SEM_POST (&wsq->lock);
158 WSQ_DEBUG ("local_push: LOCK %p %p\n", wsq, obj);
163 mono_wsq_local_pop (void **ptr)
169 if (ptr == NULL || !wsq_tlskey_inited)
172 wsq = (MonoWSQ *) mono_native_tls_get_value (wsq_tlskey);
174 WSQ_DEBUG ("local_pop: no wsq\n");
179 if (wsq->head >= tail) {
180 WSQ_DEBUG ("local_pop: empty\n");
184 InterlockedExchange (&wsq->tail, tail);
185 if (wsq->head <= tail) {
186 *ptr = mono_array_get (wsq->queue, void *, tail & wsq->mask);
187 mono_array_set (wsq->queue, void *, tail & wsq->mask, NULL);
188 WSQ_DEBUG ("local_pop: GOT ONE %p %p\n", wsq, *ptr);
192 MONO_SEM_WAIT (&wsq->lock);
193 if (wsq->head <= tail) {
194 *ptr = mono_array_get (wsq->queue, void *, tail & wsq->mask);
195 mono_array_set (wsq->queue, void *, tail & wsq->mask, NULL);
198 wsq->tail = tail + 1;
201 MONO_SEM_POST (&wsq->lock);
202 WSQ_DEBUG ("local_pop: LOCK %d %p %p\n", res, wsq, *ptr);
207 mono_wsq_try_steal (MonoWSQ *wsq, void **ptr, guint32 ms_timeout)
209 if (wsq == NULL || ptr == NULL || *ptr != NULL || !wsq_tlskey_inited)
212 if (mono_native_tls_get_value (wsq_tlskey) == wsq)
215 if (mono_sem_timedwait (&wsq->lock, ms_timeout, FALSE) == 0) {
219 InterlockedExchange (&wsq->head, head + 1);
220 if (head < wsq->tail) {
221 *ptr = mono_array_get (wsq->queue, void *, head & wsq->mask);
222 mono_array_set (wsq->queue, void *, head & wsq->mask, NULL);
223 WSQ_DEBUG ("STEAL %p %p\n", wsq, *ptr);
227 MONO_SEM_POST (&wsq->lock);