1 /**
2 * \file
3 * The pin queue.
4 *
5 * Copyright 2001-2003 Ximian, Inc
6 * Copyright 2003-2010 Novell, Inc.
7 * Copyright (C) 2012 Xamarin Inc
8 *
9 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
10 */
11
12 #include "config.h"
13 #ifdef HAVE_SGEN_GC
14
15 #include <string.h>
16
17 #include "mono/sgen/sgen-gc.h"
18 #include "mono/sgen/sgen-pinning.h"
19 #include "mono/sgen/sgen-protocol.h"
20 #include "mono/sgen/sgen-pointer-queue.h"
21 #include "mono/sgen/sgen-client.h"
22
23 static SgenPointerQueue pin_queue;
24 static size_t last_num_pinned = 0;
25 /*
26 * While we hold the pin_queue_mutex, all objects in pin_queue_objs will
27 * stay pinned, which means they can't move, therefore they can be scanned.
28 */
29 static SgenPointerQueue pin_queue_objs;
30 static mono_mutex_t pin_queue_mutex;
31
32 #define PIN_HASH_SIZE 1024
33 static void *pin_hash_filter [PIN_HASH_SIZE];
34
35 void
sgen_pinning_init(void)36 sgen_pinning_init (void)
37 {
38 mono_os_mutex_init (&pin_queue_mutex);
39 }
40
41 void
sgen_init_pinning(void)42 sgen_init_pinning (void)
43 {
44 memset (pin_hash_filter, 0, sizeof (pin_hash_filter));
45 pin_queue.mem_type = INTERNAL_MEM_PIN_QUEUE;
46 }
47
48 void
sgen_init_pinning_for_conc(void)49 sgen_init_pinning_for_conc (void)
50 {
51 mono_os_mutex_lock (&pin_queue_mutex);
52 sgen_pointer_queue_clear (&pin_queue_objs);
53 }
54
55 void
sgen_finish_pinning(void)56 sgen_finish_pinning (void)
57 {
58 last_num_pinned = pin_queue.next_slot;
59 sgen_pointer_queue_clear (&pin_queue);
60 }
61
62 void
sgen_finish_pinning_for_conc(void)63 sgen_finish_pinning_for_conc (void)
64 {
65 mono_os_mutex_unlock (&pin_queue_mutex);
66 }
67
68 void
sgen_pinning_register_pinned_in_nursery(GCObject * obj)69 sgen_pinning_register_pinned_in_nursery (GCObject *obj)
70 {
71 sgen_pointer_queue_add (&pin_queue_objs, obj);
72 }
73
74 void
sgen_scan_pin_queue_objects(ScanCopyContext ctx)75 sgen_scan_pin_queue_objects (ScanCopyContext ctx)
76 {
77 int i;
78 ScanObjectFunc scan_func = ctx.ops->scan_object;
79
80 mono_os_mutex_lock (&pin_queue_mutex);
81 for (i = 0; i < pin_queue_objs.next_slot; ++i) {
82 GCObject *obj = (GCObject *)pin_queue_objs.data [i];
83 scan_func (obj, sgen_obj_get_descriptor_safe (obj), ctx.queue);
84 }
85 mono_os_mutex_unlock (&pin_queue_mutex);
86 }
87
88 void
sgen_pin_stage_ptr(void * ptr)89 sgen_pin_stage_ptr (void *ptr)
90 {
91 /*very simple multiplicative hash function, tons better than simple and'ng */
92 int hash_idx = ((mword)ptr * 1737350767) & (PIN_HASH_SIZE - 1);
93 if (pin_hash_filter [hash_idx] == ptr)
94 return;
95
96 pin_hash_filter [hash_idx] = ptr;
97
98 sgen_pointer_queue_add (&pin_queue, ptr);
99 }
100
101 gboolean
sgen_find_optimized_pin_queue_area(void * start,void * end,size_t * first_out,size_t * last_out)102 sgen_find_optimized_pin_queue_area (void *start, void *end, size_t *first_out, size_t *last_out)
103 {
104 size_t first = sgen_pointer_queue_search (&pin_queue, start);
105 size_t last = sgen_pointer_queue_search (&pin_queue, end);
106 SGEN_ASSERT (0, last == pin_queue.next_slot || pin_queue.data [last] >= end, "Pin queue search gone awry");
107 *first_out = first;
108 *last_out = last;
109 return first != last;
110 }
111
112 void**
sgen_pinning_get_entry(size_t index)113 sgen_pinning_get_entry (size_t index)
114 {
115 SGEN_ASSERT (0, index <= pin_queue.next_slot, "Pin queue entry out of range");
116 return &pin_queue.data [index];
117 }
118
119 void
sgen_find_section_pin_queue_start_end(GCMemSection * section)120 sgen_find_section_pin_queue_start_end (GCMemSection *section)
121 {
122 SGEN_LOG (6, "Pinning from section %p (%p-%p)", section, section->data, section->end_data);
123
124 sgen_find_optimized_pin_queue_area (section->data, section->end_data,
125 §ion->pin_queue_first_entry, §ion->pin_queue_last_entry);
126
127 SGEN_LOG (6, "Found %zd pinning addresses in section %p",
128 section->pin_queue_last_entry - section->pin_queue_first_entry, section);
129 }
130
131 /*This will setup the given section for the while pin queue. */
132 void
sgen_pinning_setup_section(GCMemSection * section)133 sgen_pinning_setup_section (GCMemSection *section)
134 {
135 section->pin_queue_first_entry = 0;
136 section->pin_queue_last_entry = pin_queue.next_slot;
137 }
138
139 void
sgen_pinning_trim_queue_to_section(GCMemSection * section)140 sgen_pinning_trim_queue_to_section (GCMemSection *section)
141 {
142 SGEN_ASSERT (0, section->pin_queue_first_entry == 0, "Pin queue trimming assumes the whole pin queue is used by the nursery");
143 pin_queue.next_slot = section->pin_queue_last_entry;
144 }
145
146 /*
147 * This is called when we've run out of memory during a major collection.
148 *
149 * After collecting potential pin entries and sorting the array, this is what it looks like:
150 *
151 * +--------------------+---------------------------------------------+--------------------+
152 * | major heap entries | nursery entries | major heap entries |
153 * +--------------------+---------------------------------------------+--------------------+
154 *
155 * Of course there might not be major heap entries before and/or after the nursery entries,
156 * depending on where the major heap sections are in the address space, and whether there
157 * were any potential pointers there.
158 *
159 * When we pin nursery objects, we compact the nursery part of the pin array, which leaves
160 * discarded entries after the ones that actually pointed to nursery objects:
161 *
162 * +--------------------+-----------------+---------------------------+--------------------+
163 * | major heap entries | nursery entries | discarded nursery entries | major heap entries |
164 * +--------------------+-----------------+---------------------------+--------------------+
165 *
166 * When, due to being out of memory, we late pin more objects, the pin array looks like
167 * this:
168 *
169 * +--------------------+-----------------+---------------------------+--------------------+--------------+
170 * | major heap entries | nursery entries | discarded nursery entries | major heap entries | late entries |
171 * +--------------------+-----------------+---------------------------+--------------------+--------------+
172 *
173 * This function gets rid of the discarded nursery entries by nulling them out. Note that
174 * we can late pin objects not only in the nursery but also in the major heap, which happens
175 * when evacuation fails.
176 */
177 void
sgen_pin_queue_clear_discarded_entries(GCMemSection * section,size_t max_pin_slot)178 sgen_pin_queue_clear_discarded_entries (GCMemSection *section, size_t max_pin_slot)
179 {
180 void **start = sgen_pinning_get_entry (section->pin_queue_last_entry);
181 void **end = sgen_pinning_get_entry (max_pin_slot);
182 void *addr;
183
184 for (; start < end; ++start) {
185 addr = *start;
186 if ((char*)addr < section->data || (char*)addr > section->end_data)
187 break;
188 *start = NULL;
189 }
190 }
191
192 /* reduce the info in the pin queue, removing duplicate pointers and sorting them */
193 void
sgen_optimize_pin_queue(void)194 sgen_optimize_pin_queue (void)
195 {
196 sgen_pointer_queue_sort_uniq (&pin_queue);
197 }
198
199 size_t
sgen_get_pinned_count(void)200 sgen_get_pinned_count (void)
201 {
202 return pin_queue.next_slot;
203 }
204
205 void
sgen_dump_pin_queue(void)206 sgen_dump_pin_queue (void)
207 {
208 int i;
209
210 for (i = 0; i < last_num_pinned; ++i) {
211 GCObject *ptr = (GCObject *)pin_queue.data [i];
212 SGEN_LOG (3, "Bastard pinning obj %p (%s), size: %zd", ptr, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (ptr)), sgen_safe_object_get_size (ptr));
213 }
214 }
215
216 typedef struct _CementHashEntry CementHashEntry;
217 struct _CementHashEntry {
218 GCObject *obj;
219 unsigned int count;
220 gboolean forced; /* if it should stay cemented after the finishing pause */
221 };
222
223 static CementHashEntry cement_hash [SGEN_CEMENT_HASH_SIZE];
224
225 static gboolean cement_enabled = TRUE;
226
227 void
sgen_cement_init(gboolean enabled)228 sgen_cement_init (gboolean enabled)
229 {
230 cement_enabled = enabled;
231 }
232
233 void
sgen_cement_reset(void)234 sgen_cement_reset (void)
235 {
236 int i;
237 for (i = 0; i < SGEN_CEMENT_HASH_SIZE; i++) {
238 if (cement_hash [i].forced) {
239 cement_hash [i].forced = FALSE;
240 } else {
241 cement_hash [i].obj = NULL;
242 cement_hash [i].count = 0;
243 }
244 }
245 binary_protocol_cement_reset ();
246 }
247
248
249 /*
250 * The pin_queue should be full and sorted, without entries from the cemented
251 * objects. We traverse the cement hash and check if each object is pinned in
252 * the pin_queue (the pin_queue contains entries between obj and obj+obj_len)
253 */
254 void
sgen_cement_force_pinned(void)255 sgen_cement_force_pinned (void)
256 {
257 int i;
258
259 if (!cement_enabled)
260 return;
261
262 for (i = 0; i < SGEN_CEMENT_HASH_SIZE; i++) {
263 GCObject *obj = cement_hash [i].obj;
264 size_t index;
265 if (!obj)
266 continue;
267 if (cement_hash [i].count < SGEN_CEMENT_THRESHOLD)
268 continue;
269 SGEN_ASSERT (0, !cement_hash [i].forced, "Why do we have a forced cemented object before forcing ?");
270
271 /* Returns the index of the target or of the first element greater than it */
272 index = sgen_pointer_queue_search (&pin_queue, obj);
273 if (index == pin_queue.next_slot)
274 continue;
275 SGEN_ASSERT (0, pin_queue.data [index] >= (gpointer)obj, "Binary search should return a pointer greater than the search target");
276 if (pin_queue.data [index] < (gpointer)((char*)obj + sgen_safe_object_get_size (obj)))
277 cement_hash [i].forced = TRUE;
278 }
279 }
280
281 gboolean
sgen_cement_is_forced(GCObject * obj)282 sgen_cement_is_forced (GCObject *obj)
283 {
284 guint hv = sgen_aligned_addr_hash (obj);
285 int i = SGEN_CEMENT_HASH (hv);
286
287 SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Looking up cementing for non-nursery objects makes no sense");
288
289 if (!cement_enabled)
290 return FALSE;
291
292 if (!cement_hash [i].obj)
293 return FALSE;
294 if (cement_hash [i].obj != obj)
295 return FALSE;
296
297 return cement_hash [i].forced;
298 }
299
300 gboolean
sgen_cement_lookup(GCObject * obj)301 sgen_cement_lookup (GCObject *obj)
302 {
303 guint hv = sgen_aligned_addr_hash (obj);
304 int i = SGEN_CEMENT_HASH (hv);
305
306 SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Looking up cementing for non-nursery objects makes no sense");
307
308 if (!cement_enabled)
309 return FALSE;
310
311 if (!cement_hash [i].obj)
312 return FALSE;
313 if (cement_hash [i].obj != obj)
314 return FALSE;
315
316 return cement_hash [i].count >= SGEN_CEMENT_THRESHOLD;
317 }
318
319 gboolean
sgen_cement_lookup_or_register(GCObject * obj)320 sgen_cement_lookup_or_register (GCObject *obj)
321 {
322 guint hv;
323 int i;
324 CementHashEntry *hash = cement_hash;
325
326 if (!cement_enabled)
327 return FALSE;
328
329 hv = sgen_aligned_addr_hash (obj);
330 i = SGEN_CEMENT_HASH (hv);
331
332 SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Can only cement pointers to nursery objects");
333
334 if (!hash [i].obj) {
335 GCObject *old_obj;
336 old_obj = mono_atomic_cas_ptr ((gpointer*)&hash [i].obj, obj, NULL);
337 /* Check if the slot was occupied by some other object */
338 if (old_obj != NULL && old_obj != obj)
339 return FALSE;
340 } else if (hash [i].obj != obj) {
341 return FALSE;
342 }
343
344 if (hash [i].count >= SGEN_CEMENT_THRESHOLD)
345 return TRUE;
346
347 if (mono_atomic_inc_i32 ((gint32*)&hash [i].count) == SGEN_CEMENT_THRESHOLD) {
348 SGEN_ASSERT (9, sgen_get_current_collection_generation () >= 0, "We can only cement objects when we're in a collection pause.");
349 SGEN_ASSERT (9, SGEN_OBJECT_IS_PINNED (obj), "Can only cement pinned objects");
350 SGEN_CEMENT_OBJECT (obj);
351
352 binary_protocol_cement (obj, (gpointer)SGEN_LOAD_VTABLE (obj),
353 (int)sgen_safe_object_get_size (obj));
354 }
355
356 return FALSE;
357 }
358
359 static void
pin_from_hash(CementHashEntry * hash,gboolean has_been_reset)360 pin_from_hash (CementHashEntry *hash, gboolean has_been_reset)
361 {
362 int i;
363 for (i = 0; i < SGEN_CEMENT_HASH_SIZE; ++i) {
364 if (!hash [i].count)
365 continue;
366
367 if (has_been_reset)
368 SGEN_ASSERT (5, hash [i].count >= SGEN_CEMENT_THRESHOLD, "Cementing hash inconsistent");
369
370 sgen_pin_stage_ptr (hash [i].obj);
371 binary_protocol_cement_stage (hash [i].obj);
372 /* FIXME: do pin stats if enabled */
373
374 SGEN_CEMENT_OBJECT (hash [i].obj);
375 }
376 }
377
378 void
sgen_pin_cemented_objects(void)379 sgen_pin_cemented_objects (void)
380 {
381 pin_from_hash (cement_hash, TRUE);
382 }
383
384 void
sgen_cement_clear_below_threshold(void)385 sgen_cement_clear_below_threshold (void)
386 {
387 int i;
388 for (i = 0; i < SGEN_CEMENT_HASH_SIZE; ++i) {
389 if (cement_hash [i].count < SGEN_CEMENT_THRESHOLD) {
390 cement_hash [i].obj = NULL;
391 cement_hash [i].count = 0;
392 }
393 }
394 }
395
396 #endif /* HAVE_SGEN_GC */
397