2 * mono-wsq.c: work-stealing queue
5 * Gonzalo Paniagua Javier (gonzalo@novell.com)
7 * Copyright (c) 2010 Novell, Inc (http://www.novell.com)
11 #include <mono/metadata/object.h>
12 #include <mono/metadata/mono-wsq.h>
13 #include <mono/utils/mono-semaphore.h>
15 #define INITIAL_LENGTH 32
16 #define WSQ_DEBUG(...)
17 //#define WSQ_DEBUG(...) g_message(__VA_ARGS__)
27 static guint32 wsq_tlskey
= -1;
32 wsq_tlskey
= TlsAlloc ();
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
);
64 mono_wsq_destroy (MonoWSQ
*wsq
)
66 if (wsq
== NULL
|| wsq
->queue
== NULL
)
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
));
79 mono_wsq_count (MonoWSQ
*wsq
)
83 return ((wsq
->tail
- wsq
->head
) & wsq
->mask
);
87 mono_wsq_local_push (void *obj
)
94 if (obj
== NULL
|| wsq_tlskey
== -1)
97 wsq
= (MonoWSQ
*) TlsGetValue (wsq_tlskey
);
99 WSQ_DEBUG ("local_push: no wsq\n");
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
);
111 MONO_SEM_WAIT (&wsq
->lock
);
113 count
= wsq
->tail
- wsq
->head
;
114 if (count
>= wsq
->mask
) {
115 MonoArray
*new_array
;
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
));
124 memset (mono_array_addr (wsq
->queue
, MonoObject
*, 0), 0, sizeof (MonoObject
*) * length
);
125 wsq
->queue
= new_array
;
127 wsq
->tail
= tail
= count
;
128 wsq
->mask
= (wsq
->mask
<< 1) | 1;
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
);
138 mono_wsq_local_pop (void **ptr
)
144 if (ptr
== NULL
|| wsq_tlskey
== -1)
147 wsq
= (MonoWSQ
*) TlsGetValue (wsq_tlskey
);
149 WSQ_DEBUG ("local_pop: no wsq\n");
154 if (wsq
->head
>= tail
) {
155 WSQ_DEBUG ("local_pop: empty\n");
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
);
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
);
173 wsq
->tail
= tail
+ 1;
176 MONO_SEM_POST (&wsq
->lock
);
177 WSQ_DEBUG ("local_pop: LOCK %d %p %p\n", res
, wsq
, *ptr
);
182 mono_wsq_try_steal (MonoWSQ
*wsq
, void **ptr
, guint32 ms_timeout
)
184 if (wsq
== NULL
|| ptr
== NULL
|| *ptr
!= NULL
|| wsq_tlskey
== -1)
187 if (TlsGetValue (wsq_tlskey
) == wsq
)
190 if (MONO_SEM_TIMEDWAIT (&wsq
->lock
, ms_timeout
)) {
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
);
202 MONO_SEM_POST (&wsq
->lock
);