2 * sgen-gray.h: Gray queue management.
4 * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
5 * Copyright (C) 2012 Xamarin Inc
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Library General Public
9 * License 2.0 as published by the Free Software Foundation;
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
16 * You should have received a copy of the GNU Library General Public
17 * License 2.0 along with this library; if not, write to the Free
18 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 #ifndef __MONO_SGEN_GRAY_H__
21 #define __MONO_SGEN_GRAY_H__
23 #include "mono/sgen/sgen-protocol.h"
26 * This gray queue has to be as optimized as possible, because it is in the core of
27 * the mark/copy phase of the garbage collector. The memory access has then to be as
28 * cache friendly as possible. That's why we use a cursor based implementation.
30 * This simply consist in maintaining a pointer to the current element in the
31 * queue. In addition to using this cursor, we use a simple linked list of arrays,
32 * called sections, so that we have the cache friendliness of arrays without having
33 * the cost of memory reallocation of a dynaic array, not the cost of memory
34 * indirection of a linked list.
36 * This implementation also allows the dequeuing of a whole section at a time. This is
37 * for example used in the parallel GC because it would be too costly to take one element
38 * at a time. This imply the main constraint that, because we don't carry the cursor
39 * with the section, we still have to store the index of the last element. This is done
40 * through the 'size' field on the section, which default value is it's maximum value
41 * SGEN_GRAY_QUEUE_SECTION_SIZE. This field is updated in multiple cases :
42 * - section allocation : default value
43 * - object push : default value if we fill the current queue first
44 * - section dequeue : position of the cursor in the dequeued section
45 * - section enqueue : position of the cursor in the previously first section in the queue
47 * The previous implementation was an index based access where we would store the index
48 * of the last element in the section. This was less efficient because we would have
49 * to make 1 memory access for the index value, 1 for the base address of the objects
50 * array and another 1 for the actual value in the array.
53 /* SGEN_GRAY_QUEUE_HEADER_SIZE is number of machine words */
54 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
55 #define SGEN_GRAY_QUEUE_HEADER_SIZE 4
57 #define SGEN_GRAY_QUEUE_HEADER_SIZE 2
60 #define SGEN_GRAY_QUEUE_SECTION_SIZE (128 - SGEN_GRAY_QUEUE_HEADER_SIZE)
62 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
64 GRAY_QUEUE_SECTION_STATE_FLOATING,
65 GRAY_QUEUE_SECTION_STATE_ENQUEUED,
66 GRAY_QUEUE_SECTION_STATE_FREE_LIST,
67 GRAY_QUEUE_SECTION_STATE_FREED
68 } GrayQueueSectionState;
71 typedef struct _GrayQueueEntry GrayQueueEntry;
72 struct _GrayQueueEntry {
77 #define SGEN_GRAY_QUEUE_ENTRY(obj,desc) { (obj), (desc) }
80 * This is a stack now instead of a queue, so the most recently added items are removed
81 * first, improving cache locality, and keeping the stack size manageable.
83 typedef struct _GrayQueueSection GrayQueueSection;
84 struct _GrayQueueSection {
85 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
87 * The dummy is here so that the state doesn't get overwritten
88 * by the internal allocator once the section is freed.
91 GrayQueueSectionState state;
94 GrayQueueSection *next;
95 GrayQueueEntry entries [SGEN_GRAY_QUEUE_SECTION_SIZE];
98 typedef struct _SgenGrayQueue SgenGrayQueue;
100 typedef void (*GrayQueueAllocPrepareFunc) (SgenGrayQueue*);
101 typedef void (*GrayQueueEnqueueCheckFunc) (GCObject*);
103 struct _SgenGrayQueue {
104 GrayQueueEntry *cursor;
105 GrayQueueSection *first;
106 GrayQueueSection *free_list;
107 GrayQueueAllocPrepareFunc alloc_prepare_func;
108 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
109 GrayQueueEnqueueCheckFunc enqueue_check_func;
111 void *alloc_prepare_data;
114 typedef struct _SgenSectionGrayQueue SgenSectionGrayQueue;
116 struct _SgenSectionGrayQueue {
117 GrayQueueSection *first;
120 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
121 GrayQueueEnqueueCheckFunc enqueue_check_func;
125 #define GRAY_LAST_CURSOR_POSITION(s) ((s)->entries + SGEN_GRAY_QUEUE_SECTION_SIZE - 1)
126 #define GRAY_FIRST_CURSOR_POSITION(s) ((s)->entries)
128 #ifdef HEAVY_STATISTICS
129 extern guint64 stat_gray_queue_section_alloc;
130 extern guint64 stat_gray_queue_section_free;
131 extern guint64 stat_gray_queue_enqueue_fast_path;
132 extern guint64 stat_gray_queue_dequeue_fast_path;
133 extern guint64 stat_gray_queue_enqueue_slow_path;
134 extern guint64 stat_gray_queue_dequeue_slow_path;
137 void sgen_init_gray_queues (void);
139 void sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, mword desc);
140 GrayQueueEntry sgen_gray_object_dequeue (SgenGrayQueue *queue);
141 GrayQueueSection* sgen_gray_object_dequeue_section (SgenGrayQueue *queue);
142 void sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section);
143 void sgen_gray_object_queue_trim_free_list (SgenGrayQueue *queue);
144 void sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func);
145 void sgen_gray_object_queue_init_invalid (SgenGrayQueue *queue);
146 void sgen_gray_queue_set_alloc_prepare (SgenGrayQueue *queue, GrayQueueAllocPrepareFunc alloc_prepare_func, void *data);
147 void sgen_gray_object_queue_init_with_alloc_prepare (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func,
148 GrayQueueAllocPrepareFunc func, void *data);
149 void sgen_gray_object_queue_deinit (SgenGrayQueue *queue);
150 void sgen_gray_object_queue_disable_alloc_prepare (SgenGrayQueue *queue);
151 void sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue);
152 void sgen_gray_object_free_queue_section (GrayQueueSection *section);
154 void sgen_section_gray_queue_init (SgenSectionGrayQueue *queue, gboolean locked,
155 GrayQueueEnqueueCheckFunc enqueue_check_func);
156 gboolean sgen_section_gray_queue_is_empty (SgenSectionGrayQueue *queue);
157 GrayQueueSection* sgen_section_gray_queue_dequeue (SgenSectionGrayQueue *queue);
158 void sgen_section_gray_queue_enqueue (SgenSectionGrayQueue *queue, GrayQueueSection *section);
160 gboolean sgen_gray_object_fill_prefetch (SgenGrayQueue *queue);
162 static inline gboolean
163 sgen_gray_object_queue_is_empty (SgenGrayQueue *queue)
165 return queue->first == NULL;
168 static inline MONO_ALWAYS_INLINE void
169 GRAY_OBJECT_ENQUEUE (SgenGrayQueue *queue, GCObject *obj, mword desc)
171 #if SGEN_MAX_DEBUG_LEVEL >= 9
172 sgen_gray_object_enqueue (queue, obj, desc);
174 if (G_UNLIKELY (!queue->first || queue->cursor == GRAY_LAST_CURSOR_POSITION (queue->first))) {
175 sgen_gray_object_enqueue (queue, obj, desc);
177 GrayQueueEntry entry = SGEN_GRAY_QUEUE_ENTRY (obj, desc);
179 HEAVY_STAT (stat_gray_queue_enqueue_fast_path ++);
181 *++queue->cursor = entry;
182 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
183 binary_protocol_gray_enqueue (queue, queue->cursor, obj);
189 static inline MONO_ALWAYS_INLINE void
190 GRAY_OBJECT_DEQUEUE (SgenGrayQueue *queue, GCObject** obj, mword *desc)
192 GrayQueueEntry entry;
193 #if SGEN_MAX_DEBUG_LEVEL >= 9
194 entry = sgen_gray_object_dequeue (queue);
199 HEAVY_STAT (stat_gray_queue_dequeue_fast_path ++);
202 } else if (G_UNLIKELY (queue->cursor == GRAY_FIRST_CURSOR_POSITION (queue->first))) {
203 entry = sgen_gray_object_dequeue (queue);
207 HEAVY_STAT (stat_gray_queue_dequeue_fast_path ++);
209 entry = *queue->cursor--;
212 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
213 binary_protocol_gray_dequeue (queue, queue->cursor + 1, *obj);