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 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Library General Public
10 * License 2.0 as published by the Free Software Foundation;
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Library General Public License for more details.
17 * You should have received a copy of the GNU Library General Public
18 * License 2.0 along with this library; if not, write to the Free
19 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
24 #include "mono/sgen/sgen-gc.h"
25 #include "mono/sgen/sgen-protocol.h"
27 #ifdef HEAVY_STATISTICS
28 guint64 stat_gray_queue_section_alloc
;
29 guint64 stat_gray_queue_section_free
;
30 guint64 stat_gray_queue_enqueue_fast_path
;
31 guint64 stat_gray_queue_dequeue_fast_path
;
32 guint64 stat_gray_queue_enqueue_slow_path
;
33 guint64 stat_gray_queue_dequeue_slow_path
;
36 #define GRAY_QUEUE_LENGTH_LIMIT 64
38 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
39 #define STATE_TRANSITION(s,o,n) do { \
41 if (InterlockedCompareExchange ((volatile int*)&(s)->state, (n), __old) != __old) \
42 g_assert_not_reached (); \
44 #define STATE_SET(s,v) (s)->state = (v)
45 #define STATE_ASSERT(s,v) g_assert ((s)->state == (v))
47 #define STATE_TRANSITION(s,o,n)
48 #define STATE_SET(s,v)
49 #define STATE_ASSERT(s,v)
53 sgen_gray_object_alloc_queue_section (SgenGrayQueue
*queue
)
55 GrayQueueSection
*section
;
57 HEAVY_STAT (stat_gray_queue_section_alloc
++);
59 if (queue
->alloc_prepare_func
)
60 queue
->alloc_prepare_func (queue
);
62 if (queue
->free_list
) {
63 /* Use the previously allocated queue sections if possible */
64 section
= queue
->free_list
;
65 queue
->free_list
= section
->next
;
66 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_FREE_LIST
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
68 /* Allocate a new section */
69 section
= (GrayQueueSection
*)sgen_alloc_internal (INTERNAL_MEM_GRAY_QUEUE
);
70 STATE_SET (section
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
73 section
->size
= SGEN_GRAY_QUEUE_SECTION_SIZE
;
75 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_FLOATING
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
);
77 /* Link it with the others */
78 section
->next
= queue
->first
;
79 queue
->first
= section
;
80 queue
->cursor
= section
->entries
- 1;
84 sgen_gray_object_free_queue_section (GrayQueueSection
*section
)
86 HEAVY_STAT (stat_gray_queue_section_free
++);
88 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_FLOATING
, GRAY_QUEUE_SECTION_STATE_FREED
);
89 sgen_free_internal (section
, INTERNAL_MEM_GRAY_QUEUE
);
93 * The following two functions are called in the inner loops of the
94 * collector, so they need to be as fast as possible. We have macros
95 * for them in sgen-gc.h.
99 sgen_gray_object_enqueue (SgenGrayQueue
*queue
, GCObject
*obj
, SgenDescriptor desc
)
101 GrayQueueEntry entry
= SGEN_GRAY_QUEUE_ENTRY (obj
, desc
);
103 HEAVY_STAT (stat_gray_queue_enqueue_slow_path
++);
105 SGEN_ASSERT (9, obj
, "enqueueing a null object");
106 //sgen_check_objref (obj);
108 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
109 if (queue
->enqueue_check_func
)
110 queue
->enqueue_check_func (obj
);
113 if (G_UNLIKELY (!queue
->first
|| queue
->cursor
== GRAY_LAST_CURSOR_POSITION (queue
->first
))) {
115 /* Set the current section size back to default, might have been changed by sgen_gray_object_dequeue_section */
116 queue
->first
->size
= SGEN_GRAY_QUEUE_SECTION_SIZE
;
119 sgen_gray_object_alloc_queue_section (queue
);
121 STATE_ASSERT (queue
->first
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
);
122 SGEN_ASSERT (9, queue
->cursor
<= GRAY_LAST_CURSOR_POSITION (queue
->first
), "gray queue %p overflow, first %p, cursor %p", queue
, queue
->first
, queue
->cursor
);
123 *++queue
->cursor
= entry
;
125 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
126 binary_protocol_gray_enqueue (queue
, queue
->cursor
, obj
);
131 sgen_gray_object_dequeue (SgenGrayQueue
*queue
)
133 GrayQueueEntry entry
;
135 HEAVY_STAT (stat_gray_queue_dequeue_slow_path
++);
137 if (sgen_gray_object_queue_is_empty (queue
)) {
142 STATE_ASSERT (queue
->first
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
);
143 SGEN_ASSERT (9, queue
->cursor
>= GRAY_FIRST_CURSOR_POSITION (queue
->first
), "gray queue %p underflow", queue
);
145 entry
= *queue
->cursor
--;
147 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
148 binary_protocol_gray_dequeue (queue
, queue
->cursor
+ 1, entry
.obj
);
151 if (G_UNLIKELY (queue
->cursor
< GRAY_FIRST_CURSOR_POSITION (queue
->first
))) {
152 GrayQueueSection
*section
= queue
->first
;
153 queue
->first
= section
->next
;
154 section
->next
= queue
->free_list
;
156 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
, GRAY_QUEUE_SECTION_STATE_FREE_LIST
);
158 queue
->free_list
= section
;
159 queue
->cursor
= queue
->first
? queue
->first
->entries
+ queue
->first
->size
- 1 : NULL
;
166 sgen_gray_object_dequeue_section (SgenGrayQueue
*queue
)
168 GrayQueueSection
*section
;
173 section
= queue
->first
;
174 queue
->first
= section
->next
;
176 section
->next
= NULL
;
177 section
->size
= queue
->cursor
- section
->entries
+ 1;
179 queue
->cursor
= queue
->first
? queue
->first
->entries
+ queue
->first
->size
- 1 : NULL
;
181 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
187 sgen_gray_object_enqueue_section (SgenGrayQueue
*queue
, GrayQueueSection
*section
)
189 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_FLOATING
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
);
192 queue
->first
->size
= queue
->cursor
- queue
->first
->entries
+ 1;
194 section
->next
= queue
->first
;
195 queue
->first
= section
;
196 queue
->cursor
= queue
->first
->entries
+ queue
->first
->size
- 1;
197 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
198 if (queue
->enqueue_check_func
) {
200 for (i
= 0; i
< section
->size
; ++i
)
201 queue
->enqueue_check_func (section
->entries
[i
].obj
);
207 sgen_gray_object_queue_trim_free_list (SgenGrayQueue
*queue
)
209 GrayQueueSection
*section
, *next
;
211 for (section
= queue
->free_list
; section
&& i
< GRAY_QUEUE_LENGTH_LIMIT
- 1; section
= section
->next
) {
212 STATE_ASSERT (section
, GRAY_QUEUE_SECTION_STATE_FREE_LIST
);
217 while (section
->next
) {
218 next
= section
->next
;
219 section
->next
= next
->next
;
220 STATE_TRANSITION (next
, GRAY_QUEUE_SECTION_STATE_FREE_LIST
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
221 sgen_gray_object_free_queue_section (next
);
226 sgen_gray_object_queue_init (SgenGrayQueue
*queue
, GrayQueueEnqueueCheckFunc enqueue_check_func
)
228 g_assert (sgen_gray_object_queue_is_empty (queue
));
230 queue
->alloc_prepare_func
= NULL
;
231 queue
->alloc_prepare_data
= NULL
;
232 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
233 queue
->enqueue_check_func
= enqueue_check_func
;
236 /* Free the extra sections allocated during the last collection */
237 sgen_gray_object_queue_trim_free_list (queue
);
241 invalid_prepare_func (SgenGrayQueue
*queue
)
243 g_assert_not_reached ();
247 sgen_gray_object_queue_init_invalid (SgenGrayQueue
*queue
)
249 sgen_gray_object_queue_init (queue
, NULL
);
250 queue
->alloc_prepare_func
= invalid_prepare_func
;
251 queue
->alloc_prepare_data
= NULL
;
255 sgen_gray_queue_set_alloc_prepare (SgenGrayQueue
*queue
, GrayQueueAllocPrepareFunc alloc_prepare_func
, void *data
)
257 SGEN_ASSERT (0, !queue
->alloc_prepare_func
&& !queue
->alloc_prepare_data
, "Can't set gray queue alloc-prepare twice");
258 queue
->alloc_prepare_func
= alloc_prepare_func
;
259 queue
->alloc_prepare_data
= data
;
263 sgen_gray_object_queue_init_with_alloc_prepare (SgenGrayQueue
*queue
, GrayQueueEnqueueCheckFunc enqueue_check_func
,
264 GrayQueueAllocPrepareFunc alloc_prepare_func
, void *data
)
266 sgen_gray_object_queue_init (queue
, enqueue_check_func
);
267 sgen_gray_queue_set_alloc_prepare (queue
, alloc_prepare_func
, data
);
271 sgen_gray_object_queue_deinit (SgenGrayQueue
*queue
)
273 g_assert (!queue
->first
);
274 while (queue
->free_list
) {
275 GrayQueueSection
*next
= queue
->free_list
->next
;
276 STATE_TRANSITION (queue
->free_list
, GRAY_QUEUE_SECTION_STATE_FREE_LIST
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
277 sgen_gray_object_free_queue_section (queue
->free_list
);
278 queue
->free_list
= next
;
283 sgen_gray_object_queue_disable_alloc_prepare (SgenGrayQueue
*queue
)
285 queue
->alloc_prepare_func
= NULL
;
286 queue
->alloc_prepare_data
= NULL
;
290 lock_section_queue (SgenSectionGrayQueue
*queue
)
295 mono_os_mutex_lock (&queue
->lock
);
299 unlock_section_queue (SgenSectionGrayQueue
*queue
)
304 mono_os_mutex_unlock (&queue
->lock
);
308 sgen_section_gray_queue_init (SgenSectionGrayQueue
*queue
, gboolean locked
, GrayQueueEnqueueCheckFunc enqueue_check_func
)
310 g_assert (sgen_section_gray_queue_is_empty (queue
));
312 queue
->locked
= locked
;
314 mono_os_mutex_init_recursive (&queue
->lock
);
317 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
318 queue
->enqueue_check_func
= enqueue_check_func
;
323 sgen_section_gray_queue_is_empty (SgenSectionGrayQueue
*queue
)
325 return !queue
->first
;
329 sgen_section_gray_queue_dequeue (SgenSectionGrayQueue
*queue
)
331 GrayQueueSection
*section
;
333 lock_section_queue (queue
);
336 section
= queue
->first
;
337 queue
->first
= section
->next
;
339 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
, GRAY_QUEUE_SECTION_STATE_FLOATING
);
341 section
->next
= NULL
;
346 unlock_section_queue (queue
);
352 sgen_section_gray_queue_enqueue (SgenSectionGrayQueue
*queue
, GrayQueueSection
*section
)
354 STATE_TRANSITION (section
, GRAY_QUEUE_SECTION_STATE_FLOATING
, GRAY_QUEUE_SECTION_STATE_ENQUEUED
);
356 lock_section_queue (queue
);
358 section
->next
= queue
->first
;
359 queue
->first
= section
;
360 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
361 if (queue
->enqueue_check_func
) {
363 for (i
= 0; i
< section
->size
; ++i
)
364 queue
->enqueue_check_func (section
->entries
[i
].obj
);
368 unlock_section_queue (queue
);
372 sgen_init_gray_queues (void)
374 #ifdef HEAVY_STATISTICS
375 mono_counters_register ("Gray Queue alloc section", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_section_alloc
);
376 mono_counters_register ("Gray Queue free section", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_section_free
);
377 mono_counters_register ("Gray Queue enqueue fast path", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_enqueue_fast_path
);
378 mono_counters_register ("Gray Queue dequeue fast path", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_dequeue_fast_path
);
379 mono_counters_register ("Gray Queue enqueue slow path", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_enqueue_slow_path
);
380 mono_counters_register ("Gray Queue dequeue slow path", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_gray_queue_dequeue_slow_path
);