Fix roslyn install with AOT disabled.
[mono-project.git] / mono / sgen / sgen-gray.h
blob2a872d7d2bf1816193f06f8dfebec7a035cfb4d1
1 /*
2 * sgen-gray.h: Gray queue management.
4 * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
5 * Copyright (C) 2012 Xamarin Inc
7 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
8 */
9 #ifndef __MONO_SGEN_GRAY_H__
10 #define __MONO_SGEN_GRAY_H__
12 #include "mono/sgen/sgen-protocol.h"
15 * This gray queue has to be as optimized as possible, because it is in the core of
16 * the mark/copy phase of the garbage collector. The memory access has then to be as
17 * cache friendly as possible. That's why we use a cursor based implementation.
19 * This simply consist in maintaining a pointer to the current element in the
20 * queue. In addition to using this cursor, we use a simple linked list of arrays,
21 * called sections, so that we have the cache friendliness of arrays without having
22 * the cost of memory reallocation of a dynaic array, not the cost of memory
23 * indirection of a linked list.
25 * This implementation also allows the dequeuing of a whole section at a time. This is
26 * for example used in the parallel GC because it would be too costly to take one element
27 * at a time. This imply the main constraint that, because we don't carry the cursor
28 * with the section, we still have to store the index of the last element. This is done
29 * through the 'size' field on the section, which default value is it's maximum value
30 * SGEN_GRAY_QUEUE_SECTION_SIZE. This field is updated in multiple cases :
31 * - section allocation : default value
32 * - object push : default value if we fill the current queue first
33 * - section dequeue : position of the cursor in the dequeued section
34 * - section enqueue : position of the cursor in the previously first section in the queue
36 * The previous implementation was an index based access where we would store the index
37 * of the last element in the section. This was less efficient because we would have
38 * to make 1 memory access for the index value, 1 for the base address of the objects
39 * array and another 1 for the actual value in the array.
42 /* SGEN_GRAY_QUEUE_HEADER_SIZE is number of machine words */
43 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
44 #define SGEN_GRAY_QUEUE_HEADER_SIZE 4
45 #else
46 #define SGEN_GRAY_QUEUE_HEADER_SIZE 2
47 #endif
49 #define SGEN_GRAY_QUEUE_SECTION_SIZE (128 - SGEN_GRAY_QUEUE_HEADER_SIZE)
51 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
52 typedef enum {
53 GRAY_QUEUE_SECTION_STATE_FLOATING,
54 GRAY_QUEUE_SECTION_STATE_ENQUEUED,
55 GRAY_QUEUE_SECTION_STATE_FREE_LIST,
56 GRAY_QUEUE_SECTION_STATE_FREED
57 } GrayQueueSectionState;
58 #endif
60 typedef struct _GrayQueueEntry GrayQueueEntry;
61 struct _GrayQueueEntry {
62 GCObject *obj;
63 SgenDescriptor desc;
66 #define SGEN_GRAY_QUEUE_ENTRY(obj,desc) { (obj), (desc) }
69 * This is a stack now instead of a queue, so the most recently added items are removed
70 * first, improving cache locality, and keeping the stack size manageable.
72 typedef struct _GrayQueueSection GrayQueueSection;
73 struct _GrayQueueSection {
74 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
76 * The dummy is here so that the state doesn't get overwritten
77 * by the internal allocator once the section is freed.
79 int dummy;
80 GrayQueueSectionState state;
81 #endif
82 int size;
83 GrayQueueSection *next;
84 GrayQueueEntry entries [SGEN_GRAY_QUEUE_SECTION_SIZE];
87 typedef struct _SgenGrayQueue SgenGrayQueue;
89 typedef void (*GrayQueueAllocPrepareFunc) (SgenGrayQueue*);
90 typedef void (*GrayQueueEnqueueCheckFunc) (GCObject*);
92 struct _SgenGrayQueue {
93 GrayQueueEntry *cursor;
94 GrayQueueSection *first;
95 GrayQueueSection *free_list;
96 GrayQueueAllocPrepareFunc alloc_prepare_func;
97 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
98 GrayQueueEnqueueCheckFunc enqueue_check_func;
99 #endif
102 typedef struct _SgenSectionGrayQueue SgenSectionGrayQueue;
104 struct _SgenSectionGrayQueue {
105 GrayQueueSection *first;
106 gboolean locked;
107 mono_mutex_t lock;
108 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
109 GrayQueueEnqueueCheckFunc enqueue_check_func;
110 #endif
113 #define GRAY_LAST_CURSOR_POSITION(s) ((s)->entries + SGEN_GRAY_QUEUE_SECTION_SIZE - 1)
114 #define GRAY_FIRST_CURSOR_POSITION(s) ((s)->entries)
116 #ifdef HEAVY_STATISTICS
117 extern guint64 stat_gray_queue_section_alloc;
118 extern guint64 stat_gray_queue_section_free;
119 extern guint64 stat_gray_queue_enqueue_fast_path;
120 extern guint64 stat_gray_queue_dequeue_fast_path;
121 extern guint64 stat_gray_queue_enqueue_slow_path;
122 extern guint64 stat_gray_queue_dequeue_slow_path;
123 #endif
125 void sgen_init_gray_queues (void);
127 void sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc);
128 GrayQueueEntry sgen_gray_object_dequeue (SgenGrayQueue *queue);
129 GrayQueueSection* sgen_gray_object_dequeue_section (SgenGrayQueue *queue);
130 void sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section);
131 void sgen_gray_object_queue_trim_free_list (SgenGrayQueue *queue);
132 void sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func, gboolean reuse_free_list);
133 void sgen_gray_object_queue_dispose (SgenGrayQueue *queue);
134 void sgen_gray_queue_set_alloc_prepare (SgenGrayQueue *queue, GrayQueueAllocPrepareFunc alloc_prepare_func);
135 void sgen_gray_object_queue_deinit (SgenGrayQueue *queue);
136 void sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue);
137 void sgen_gray_object_free_queue_section (GrayQueueSection *section);
139 void sgen_section_gray_queue_init (SgenSectionGrayQueue *queue, gboolean locked,
140 GrayQueueEnqueueCheckFunc enqueue_check_func);
141 gboolean sgen_section_gray_queue_is_empty (SgenSectionGrayQueue *queue);
142 GrayQueueSection* sgen_section_gray_queue_dequeue (SgenSectionGrayQueue *queue);
143 void sgen_section_gray_queue_enqueue (SgenSectionGrayQueue *queue, GrayQueueSection *section);
145 gboolean sgen_gray_object_fill_prefetch (SgenGrayQueue *queue);
147 static inline gboolean
148 sgen_gray_object_queue_is_empty (SgenGrayQueue *queue)
150 return queue->first == NULL;
153 static inline MONO_ALWAYS_INLINE void
154 GRAY_OBJECT_ENQUEUE (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc)
156 #if SGEN_MAX_DEBUG_LEVEL >= 9
157 sgen_gray_object_enqueue (queue, obj, desc);
158 #else
159 if (G_UNLIKELY (!queue->first || queue->cursor == GRAY_LAST_CURSOR_POSITION (queue->first))) {
160 sgen_gray_object_enqueue (queue, obj, desc);
161 } else {
162 GrayQueueEntry entry = SGEN_GRAY_QUEUE_ENTRY (obj, desc);
164 HEAVY_STAT (stat_gray_queue_enqueue_fast_path ++);
166 *++queue->cursor = entry;
167 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
168 binary_protocol_gray_enqueue (queue, queue->cursor, obj);
169 #endif
171 #endif
174 static inline MONO_ALWAYS_INLINE void
175 GRAY_OBJECT_DEQUEUE (SgenGrayQueue *queue, GCObject** obj, SgenDescriptor *desc)
177 GrayQueueEntry entry;
178 #if SGEN_MAX_DEBUG_LEVEL >= 9
179 entry = sgen_gray_object_dequeue (queue);
180 *obj = entry.obj;
181 *desc = entry.desc;
182 #else
183 if (!queue->first) {
184 HEAVY_STAT (stat_gray_queue_dequeue_fast_path ++);
186 *obj = NULL;
187 } else if (G_UNLIKELY (queue->cursor == GRAY_FIRST_CURSOR_POSITION (queue->first))) {
188 entry = sgen_gray_object_dequeue (queue);
189 *obj = entry.obj;
190 *desc = entry.desc;
191 } else {
192 HEAVY_STAT (stat_gray_queue_dequeue_fast_path ++);
194 entry = *queue->cursor--;
195 *obj = entry.obj;
196 *desc = entry.desc;
197 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
198 binary_protocol_gray_dequeue (queue, queue->cursor + 1, *obj);
199 #endif
201 #endif
204 #endif