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