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__)
30 #define NO_KEY ((guint32) -1)
31 static MonoNativeTlsKey wsq_tlskey
;
32 static gboolean wsq_tlskey_inited
= FALSE
;
37 if (wsq_tlskey_inited
)
40 mono_native_tls_alloc (&wsq_tlskey
, NULL
);
41 wsq_tlskey_inited
= TRUE
;
47 if (!wsq_tlskey_inited
)
49 mono_native_tls_free (wsq_tlskey
);
50 wsq_tlskey_inited
= FALSE
;
59 if (!wsq_tlskey_inited
)
62 wsq
= g_new0 (MonoWSQ
, 1);
63 wsq
->mask
= INITIAL_LENGTH
- 1;
64 MONO_GC_REGISTER_ROOT_SINGLE (wsq
->queue
);
65 root
= mono_get_root_domain ();
66 wsq
->queue
= mono_array_new_cached (root
, mono_defaults
.object_class
, INITIAL_LENGTH
);
67 MONO_SEM_INIT (&wsq
->lock
, 1);
68 if (!mono_native_tls_set_value (wsq_tlskey
, wsq
)) {
69 mono_wsq_destroy (wsq
);
76 mono_wsq_destroy (MonoWSQ
*wsq
)
78 if (wsq
== NULL
|| wsq
->queue
== NULL
)
81 g_assert (mono_wsq_count (wsq
) == 0);
82 MONO_GC_UNREGISTER_ROOT (wsq
->queue
);
83 MONO_SEM_DESTROY (&wsq
->lock
);
84 memset (wsq
, 0, sizeof (MonoWSQ
));
85 if (wsq_tlskey_inited
&& mono_native_tls_get_value (wsq_tlskey
) == wsq
)
86 mono_native_tls_set_value (wsq_tlskey
, NULL
);
91 mono_wsq_count (MonoWSQ
*wsq
)
95 return ((wsq
->tail
- wsq
->head
) & wsq
->mask
);
99 mono_wsq_local_push (void *obj
)
106 if (obj
== NULL
|| !wsq_tlskey_inited
)
109 wsq
= (MonoWSQ
*) mono_native_tls_get_value (wsq_tlskey
);
111 WSQ_DEBUG ("local_push: no wsq\n");
116 if (tail
< wsq
->head
+ wsq
->mask
) {
117 mono_array_setref (wsq
->queue
, tail
& wsq
->mask
, (MonoObject
*) obj
);
118 wsq
->tail
= tail
+ 1;
119 WSQ_DEBUG ("local_push: OK %p %p\n", wsq
, obj
);
123 MONO_SEM_WAIT (&wsq
->lock
);
125 count
= wsq
->tail
- wsq
->head
;
126 if (count
>= wsq
->mask
) {
127 MonoArray
*new_array
;
131 length
= mono_array_length (wsq
->queue
);
132 new_array
= mono_array_new_cached (mono_get_root_domain (), mono_defaults
.object_class
, length
* 2);
133 for (i
= 0; i
< length
; i
++)
134 mono_array_setref (new_array
, i
, mono_array_get (wsq
->queue
, MonoObject
*, (i
+ head
) & wsq
->mask
));
136 mono_gc_bzero_aligned (mono_array_addr (wsq
->queue
, MonoObject
*, 0), sizeof (MonoObject
*) * length
);
137 wsq
->queue
= new_array
;
139 wsq
->tail
= tail
= count
;
140 wsq
->mask
= (wsq
->mask
<< 1) | 1;
142 mono_array_setref (wsq
->queue
, tail
& wsq
->mask
, obj
);
143 wsq
->tail
= tail
+ 1;
144 MONO_SEM_POST (&wsq
->lock
);
145 WSQ_DEBUG ("local_push: LOCK %p %p\n", wsq
, obj
);
150 mono_wsq_local_pop (void **ptr
)
156 if (ptr
== NULL
|| !wsq_tlskey_inited
)
159 wsq
= (MonoWSQ
*) mono_native_tls_get_value (wsq_tlskey
);
161 WSQ_DEBUG ("local_pop: no wsq\n");
166 if (wsq
->head
>= tail
) {
167 WSQ_DEBUG ("local_pop: empty\n");
171 InterlockedExchange (&wsq
->tail
, tail
);
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 WSQ_DEBUG ("local_pop: GOT ONE %p %p\n", wsq
, *ptr
);
179 MONO_SEM_WAIT (&wsq
->lock
);
180 if (wsq
->head
<= tail
) {
181 *ptr
= mono_array_get (wsq
->queue
, void *, tail
& wsq
->mask
);
182 mono_array_set (wsq
->queue
, void *, tail
& wsq
->mask
, NULL
);
185 wsq
->tail
= tail
+ 1;
188 MONO_SEM_POST (&wsq
->lock
);
189 WSQ_DEBUG ("local_pop: LOCK %d %p %p\n", res
, wsq
, *ptr
);
194 mono_wsq_try_steal (MonoWSQ
*wsq
, void **ptr
, guint32 ms_timeout
)
196 if (wsq
== NULL
|| ptr
== NULL
|| *ptr
!= NULL
|| !wsq_tlskey_inited
)
199 if (mono_native_tls_get_value (wsq_tlskey
) == wsq
)
202 if (mono_sem_timedwait (&wsq
->lock
, ms_timeout
, FALSE
) == 0) {
206 InterlockedExchange (&wsq
->head
, head
+ 1);
207 if (head
< wsq
->tail
) {
208 *ptr
= mono_array_get (wsq
->queue
, void *, head
& wsq
->mask
);
209 mono_array_set (wsq
->queue
, void *, head
& wsq
->mask
, NULL
);
210 WSQ_DEBUG ("STEAL %p %p\n", wsq
, *ptr
);
214 MONO_SEM_POST (&wsq
->lock
);