2 * sgen-gray.c: Gray queue management.
4 * Copyright 2001-2003 Ximian, Inc
5 * Copyright 2003-2010 Novell, Inc.
6 * Copyright (C) 2012 Xamarin Inc
8 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
13 #include "mono/sgen/sgen-gc.h"
14 #include "mono/sgen/sgen-protocol.h"
16 #ifdef HEAVY_STATISTICS
17 guint64 stat_gray_queue_section_alloc
;
18 guint64 stat_gray_queue_section_free
;
19 guint64 stat_gray_queue_enqueue_fast_path
;
20 guint64 stat_gray_queue_dequeue_fast_path
;
21 guint64 stat_gray_queue_enqueue_slow_path
;
22 guint64 stat_gray_queue_dequeue_slow_path
;
25 #define GRAY_QUEUE_LENGTH_LIMIT 64
27 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
28 #define STATE_TRANSITION(s,o,n) do { \
30 if (InterlockedCompareExchange ((volatile int*)&(s)->state, (n), __old) != __old) \
31 g_assert_not_reached (); \
33 #define STATE_SET(s,v) (s)->state = (v)
34 #define STATE_ASSERT(s,v) g_assert ((s)->state == (v))
36 #define STATE_TRANSITION(s,o,n)
37 #define STATE_SET(s,v)
38 #define STATE_ASSERT(s,v)
42 * Whenever we dispose a gray queue, we save its free list. Then, in the next collection,
43 * we reuse that free list for the new gray queue.
45 static GrayQueueSection
*last_gray_queue_free_list
;
48 sgen_gray_object_alloc_queue_section (SgenGrayQueue
*queue
)
50 GrayQueueSection
*section
;
52 if (queue
->alloc_prepare_func
)
53 queue
->alloc_prepare_func (queue
);
55 if (queue
->free_list
) {
56 /* Use the previously allocated queue sections if possible */
57 section
= queue
->free_list
;
58 queue
->free_list
= section
->next
;
59 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_FREE_LIST
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
61 HEAVY_STAT (stat_gray_queue_section_alloc
++);
63 /* Allocate a new section */
64 section
= (GrayQueueSection
*)sgen_alloc_internal (INTERNAL_MEM_GRAY_QUEUE
);
65 STATE_SET (section
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
68 section
->size
= SGEN_GRAY_QUEUE_SECTION_SIZE
;
70 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_FLOATING
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
);
72 /* Link it with the others */
73 section
->next
= queue
->first
;
74 queue
->first
= section
;
75 queue
->cursor
= section
->entries
- 1;
79 sgen_gray_object_free_queue_section (GrayQueueSection
*section
)
81 HEAVY_STAT (stat_gray_queue_section_free
++);
83 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_FLOATING
, GRAY_QUEUE_SECTION_STATE_FREED
);
84 sgen_free_internal (section
, INTERNAL_MEM_GRAY_QUEUE
);
88 * The following two functions are called in the inner loops of the
89 * collector, so they need to be as fast as possible. We have macros
90 * for them in sgen-gc.h.
94 sgen_gray_object_enqueue (SgenGrayQueue
*queue
, GCObject
*obj
, SgenDescriptor desc
)
96 GrayQueueEntry entry
= SGEN_GRAY_QUEUE_ENTRY (obj
, desc
);
98 HEAVY_STAT (stat_gray_queue_enqueue_slow_path
++);
100 SGEN_ASSERT (9, obj
, "enqueueing a null object");
101 //sgen_check_objref (obj);
103 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
104 if (queue
->enqueue_check_func
)
105 queue
->enqueue_check_func (obj
);
108 if (G_UNLIKELY (!queue
->first
|| queue
->cursor
== GRAY_LAST_CURSOR_POSITION (queue
->first
))) {
110 /* Set the current section size back to default, might have been changed by sgen_gray_object_dequeue_section */
111 queue
->first
->size
= SGEN_GRAY_QUEUE_SECTION_SIZE
;
114 sgen_gray_object_alloc_queue_section (queue
);
116 STATE_ASSERT (queue
->first
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
);
117 SGEN_ASSERT (9, queue
->cursor
<= GRAY_LAST_CURSOR_POSITION (queue
->first
), "gray queue %p overflow, first %p, cursor %p", queue
, queue
->first
, queue
->cursor
);
118 *++queue
->cursor
= entry
;
120 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
121 binary_protocol_gray_enqueue (queue
, queue
->cursor
, obj
);
126 sgen_gray_object_dequeue (SgenGrayQueue
*queue
)
128 GrayQueueEntry entry
;
130 HEAVY_STAT (stat_gray_queue_dequeue_slow_path
++);
132 if (sgen_gray_object_queue_is_empty (queue
)) {
137 STATE_ASSERT (queue
->first
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
);
138 SGEN_ASSERT (9, queue
->cursor
>= GRAY_FIRST_CURSOR_POSITION (queue
->first
), "gray queue %p underflow", queue
);
140 entry
= *queue
->cursor
--;
142 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
143 binary_protocol_gray_dequeue (queue
, queue
->cursor
+ 1, entry
.obj
);
146 if (G_UNLIKELY (queue
->cursor
< GRAY_FIRST_CURSOR_POSITION (queue
->first
))) {
147 GrayQueueSection
*section
= queue
->first
;
148 queue
->first
= section
->next
;
149 section
->next
= queue
->free_list
;
151 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
, GRAY_QUEUE_SECTION_STATE_FREE_LIST
);
153 queue
->free_list
= section
;
154 queue
->cursor
= queue
->first
? queue
->first
->entries
+ queue
->first
->size
- 1 : NULL
;
161 sgen_gray_object_dequeue_section (SgenGrayQueue
*queue
)
163 GrayQueueSection
*section
;
168 section
= queue
->first
;
169 queue
->first
= section
->next
;
171 section
->next
= NULL
;
172 section
->size
= queue
->cursor
- section
->entries
+ 1;
174 queue
->cursor
= queue
->first
? queue
->first
->entries
+ queue
->first
->size
- 1 : NULL
;
176 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
182 sgen_gray_object_enqueue_section (SgenGrayQueue
*queue
, GrayQueueSection
*section
)
184 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_FLOATING
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
);
187 queue
->first
->size
= queue
->cursor
- queue
->first
->entries
+ 1;
189 section
->next
= queue
->first
;
190 queue
->first
= section
;
191 queue
->cursor
= queue
->first
->entries
+ queue
->first
->size
- 1;
192 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
193 if (queue
->enqueue_check_func
) {
195 for (i
= 0; i
< section
->size
; ++i
)
196 queue
->enqueue_check_func (section
->entries
[i
].obj
);
202 sgen_gray_object_queue_trim_free_list (SgenGrayQueue
*queue
)
204 GrayQueueSection
*section
, *next
;
206 for (section
= queue
->free_list
; section
&& i
< GRAY_QUEUE_LENGTH_LIMIT
- 1; section
= section
->next
) {
207 STATE_ASSERT (section
, GRAY_QUEUE_SECTION_STATE_FREE_LIST
);
212 while (section
->next
) {
213 next
= section
->next
;
214 section
->next
= next
->next
;
215 STATE_TRANSITION (next
, GRAY_QUEUE_SECTION_STATE_FREE_LIST
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
216 sgen_gray_object_free_queue_section (next
);
221 sgen_gray_object_queue_init (SgenGrayQueue
*queue
, GrayQueueEnqueueCheckFunc enqueue_check_func
, gboolean reuse_free_list
)
223 memset (queue
, 0, sizeof (SgenGrayQueue
));
225 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
226 queue
->enqueue_check_func
= enqueue_check_func
;
229 if (reuse_free_list
) {
230 queue
->free_list
= last_gray_queue_free_list
;
231 last_gray_queue_free_list
= NULL
;
236 sgen_gray_object_queue_dispose (SgenGrayQueue
*queue
)
238 SGEN_ASSERT (0, sgen_gray_object_queue_is_empty (queue
), "Why are we disposing a gray queue that's not empty?");
240 /* Free the extra sections allocated during the last collection */
241 sgen_gray_object_queue_trim_free_list (queue
);
243 SGEN_ASSERT (0, !last_gray_queue_free_list
, "Are we disposing two gray queues after another?");
244 last_gray_queue_free_list
= queue
->free_list
;
246 /* just to make sure */
247 memset (queue
, 0, sizeof (SgenGrayQueue
));
251 sgen_gray_queue_set_alloc_prepare (SgenGrayQueue
*queue
, GrayQueueAllocPrepareFunc alloc_prepare_func
)
253 SGEN_ASSERT (0, !queue
->alloc_prepare_func
, "Can't set gray queue alloc-prepare twice");
254 queue
->alloc_prepare_func
= alloc_prepare_func
;
258 sgen_gray_object_queue_deinit (SgenGrayQueue
*queue
)
260 g_assert (!queue
->first
);
261 while (queue
->free_list
) {
262 GrayQueueSection
*next
= queue
->free_list
->next
;
263 STATE_TRANSITION (queue
->free_list
, GRAY_QUEUE_SECTION_STATE_FREE_LIST
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
264 sgen_gray_object_free_queue_section (queue
->free_list
);
265 queue
->free_list
= next
;
270 lock_section_queue (SgenSectionGrayQueue
*queue
)
275 mono_os_mutex_lock (&queue
->lock
);
279 unlock_section_queue (SgenSectionGrayQueue
*queue
)
284 mono_os_mutex_unlock (&queue
->lock
);
288 sgen_section_gray_queue_init (SgenSectionGrayQueue
*queue
, gboolean locked
, GrayQueueEnqueueCheckFunc enqueue_check_func
)
290 g_assert (sgen_section_gray_queue_is_empty (queue
));
292 queue
->locked
= locked
;
294 mono_os_mutex_init_recursive (&queue
->lock
);
297 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
298 queue
->enqueue_check_func
= enqueue_check_func
;
303 sgen_section_gray_queue_is_empty (SgenSectionGrayQueue
*queue
)
305 return !queue
->first
;
309 sgen_section_gray_queue_dequeue (SgenSectionGrayQueue
*queue
)
311 GrayQueueSection
*section
;
313 lock_section_queue (queue
);
316 section
= queue
->first
;
317 queue
->first
= section
->next
;
319 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
321 section
->next
= NULL
;
326 unlock_section_queue (queue
);
332 sgen_section_gray_queue_enqueue (SgenSectionGrayQueue
*queue
, GrayQueueSection
*section
)
334 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_FLOATING
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
);
336 lock_section_queue (queue
);
338 section
->next
= queue
->first
;
339 queue
->first
= section
;
340 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
341 if (queue
->enqueue_check_func
) {
343 for (i
= 0; i
< section
->size
; ++i
)
344 queue
->enqueue_check_func (section
->entries
[i
].obj
);
348 unlock_section_queue (queue
);
352 sgen_init_gray_queues (void)
354 #ifdef HEAVY_STATISTICS
355 mono_counters_register ("Gray Queue alloc section", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_section_alloc
);
356 mono_counters_register ("Gray Queue free section", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_section_free
);
357 mono_counters_register ("Gray Queue enqueue fast path", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_enqueue_fast_path
);
358 mono_counters_register ("Gray Queue dequeue fast path", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_dequeue_fast_path
);
359 mono_counters_register ("Gray Queue enqueue slow path", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_enqueue_slow_path
);
360 mono_counters_register ("Gray Queue dequeue slow path", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_dequeue_slow_path
);