5 * Copyright (C) 2015 Xamarin Inc
7 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
13 #include "mono/sgen/sgen-gc.h"
14 #include "mono/sgen/sgen-client.h"
15 #include "mono/sgen/sgen-array-list.h"
16 #include "mono/utils/mono-membar.h"
18 #ifdef HEAVY_STATISTICS
19 static volatile guint32 stat_gc_handles_allocated = 0;
20 static volatile guint32 stat_gc_handles_max_allocated = 0;
24 * A table of GC handle data, implementing a simple lock-free bitmap allocator.
26 * Each entry in a bucket is a pointer with two tag bits: if
27 * 'GC_HANDLE_OCCUPIED' returns true for a slot, then the slot is occupied; if
28 * so, then 'GC_HANDLE_VALID' gives whether the entry refers to a valid (1) or
29 * NULL (0) object reference. If the reference is valid, then the pointer is an
30 * object pointer. If the reference is NULL, and 'GC_HANDLE_TYPE_IS_WEAK' is
31 * true for 'type', then the pointer is a metadata pointer--this allows us to
32 * retrieve the domain ID of an expired weak reference in Mono.
36 SgenArrayList entries_array;
41 protocol_gchandle_update (int handle_type, gpointer link, gpointer old_value, gpointer new_value)
43 gboolean old = MONO_GC_HANDLE_IS_OBJECT_POINTER (old_value);
44 gboolean new_ = MONO_GC_HANDLE_IS_OBJECT_POINTER (new_value);
45 gboolean track = handle_type == HANDLE_WEAK_TRACK;
47 if (!MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type))
51 binary_protocol_dislink_add (link, MONO_GC_REVEAL_POINTER (new_value, TRUE), track);
52 else if (old && !new_)
53 binary_protocol_dislink_remove (link, track);
54 else if (old && new_ && old_value != new_value)
55 binary_protocol_dislink_update (link, MONO_GC_REVEAL_POINTER (new_value, TRUE), track);
58 /* Returns the new value in the slot, or NULL if the CAS failed. */
59 static inline gpointer
60 try_set_slot (volatile gpointer *slot, GCObject *obj, gpointer old, GCHandleType type)
64 new_ = MONO_GC_HANDLE_OBJECT_POINTER (obj, GC_HANDLE_TYPE_IS_WEAK (type));
66 new_ = MONO_GC_HANDLE_METADATA_POINTER (sgen_client_default_metadata (), GC_HANDLE_TYPE_IS_WEAK (type));
67 SGEN_ASSERT (0, new_, "Why is the occupied bit not set?");
68 if (InterlockedCompareExchangePointer (slot, new_, old) == old) {
69 protocol_gchandle_update (type, (gpointer)slot, old, new_);
75 static inline gboolean
76 is_slot_set (volatile gpointer *slot)
78 gpointer entry = *slot;
79 if (MONO_GC_HANDLE_OCCUPIED (entry))
84 /* Try to claim a slot by setting its occupied bit. */
85 static inline gboolean
86 try_occupy_slot (volatile gpointer *slot, gpointer obj, int data)
88 if (is_slot_set (slot))
90 return try_set_slot (slot, (GCObject *)obj, NULL, (GCHandleType)data) != NULL;
94 bucket_alloc_callback (gpointer *bucket, guint32 new_bucket_size, gboolean alloc)
97 sgen_register_root ((char *)bucket, new_bucket_size, SGEN_DESCRIPTOR_NULL, ROOT_TYPE_PINNED, MONO_ROOT_SOURCE_GC_HANDLE, "pinned gc handles");
99 sgen_deregister_root ((char *)bucket);
102 static HandleData gc_handles [] = {
103 { SGEN_ARRAY_LIST_INIT (NULL, is_slot_set, try_occupy_slot, -1), (HANDLE_WEAK) },
104 { SGEN_ARRAY_LIST_INIT (NULL, is_slot_set, try_occupy_slot, -1), (HANDLE_WEAK_TRACK) },
105 { SGEN_ARRAY_LIST_INIT (NULL, is_slot_set, try_occupy_slot, -1), (HANDLE_NORMAL) },
106 { SGEN_ARRAY_LIST_INIT (bucket_alloc_callback, is_slot_set, try_occupy_slot, -1), (HANDLE_PINNED) }
110 gc_handles_for_type (GCHandleType type)
112 return type < HANDLE_TYPE_MAX ? &gc_handles [type] : NULL;
115 /* This assumes that the world is stopped. */
117 sgen_mark_normal_gc_handles (void *addr, SgenUserMarkFunc mark_func, void *gc_data)
119 HandleData *handles = gc_handles_for_type (HANDLE_NORMAL);
120 SgenArrayList *array = &handles->entries_array;
121 volatile gpointer *slot;
122 gpointer hidden, revealed;
124 SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
126 revealed = MONO_GC_REVEAL_POINTER (hidden, FALSE);
127 if (!MONO_GC_HANDLE_IS_OBJECT_POINTER (hidden))
129 mark_func ((MonoObject **)&revealed, gc_data);
131 *slot = MONO_GC_HANDLE_OBJECT_POINTER (revealed, FALSE);
132 } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
137 alloc_handle (HandleData *handles, GCObject *obj, gboolean track)
140 SgenArrayList *array = &handles->entries_array;
143 * If a GC happens shortly after a new bucket is allocated, the entire
144 * bucket could be scanned even though it's mostly empty. To avoid this,
145 * we track the maximum index seen so far, so that we can skip the empty
148 * Note that we update `next_slot` before we even try occupying the
149 * slot. If we did it the other way around and a GC happened in
150 * between, the GC wouldn't know that the slot was occupied. This is
151 * not a huge deal since `obj` is on the stack and thus pinned anyway,
152 * but hopefully some day it won't be anymore.
154 index = sgen_array_list_add (array, obj, handles->type, TRUE);
155 #ifdef HEAVY_STATISTICS
156 InterlockedIncrement ((volatile gint32 *)&stat_gc_handles_allocated);
157 if (stat_gc_handles_allocated > stat_gc_handles_max_allocated)
158 stat_gc_handles_max_allocated = stat_gc_handles_allocated;
160 /* Ensure that a GC handle cannot be given to another thread without the slot having been set. */
161 mono_memory_write_barrier ();
162 res = MONO_GC_HANDLE (index, handles->type);
163 sgen_client_gchandle_created (handles->type, obj, res);
168 object_older_than (GCObject *object, int generation)
170 return generation == GENERATION_NURSERY && !sgen_ptr_in_nursery (object);
174 * Maps a function over all GC handles.
175 * This assumes that the world is stopped!
178 sgen_gchandle_iterate (GCHandleType handle_type, int max_generation, SgenGCHandleIterateCallback callback, gpointer user)
180 HandleData *handle_data = gc_handles_for_type (handle_type);
181 SgenArrayList *array = &handle_data->entries_array;
182 gpointer hidden, result, occupied;
183 volatile gpointer *slot;
185 /* If a new bucket has been allocated, but the capacity has not yet been
186 * increased, nothing can yet have been allocated in the bucket because the
187 * world is stopped, so we shouldn't miss any handles during iteration.
189 SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
191 occupied = (gpointer) MONO_GC_HANDLE_OCCUPIED (hidden);
192 g_assert (hidden ? !!occupied : !occupied);
195 result = callback (hidden, handle_type, max_generation, user);
197 SGEN_ASSERT (0, MONO_GC_HANDLE_OCCUPIED (result), "Why did the callback return an unoccupied entry?");
199 HEAVY_STAT (InterlockedDecrement ((volatile gint32 *)&stat_gc_handles_allocated));
200 protocol_gchandle_update (handle_type, (gpointer)slot, hidden, result);
202 } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
206 sgen_gchandle_new (GCObject *obj, gboolean pinned)
208 return alloc_handle (gc_handles_for_type (pinned ? HANDLE_PINNED : HANDLE_NORMAL), obj, FALSE);
212 sgen_gchandle_new_weakref (GCObject *obj, gboolean track_resurrection)
214 return alloc_handle (gc_handles_for_type (track_resurrection ? HANDLE_WEAK_TRACK : HANDLE_WEAK), obj, track_resurrection);
218 link_get (volatile gpointer *link_addr, gboolean is_weak)
220 void *volatile *link_addr_volatile;
224 link_addr_volatile = link_addr;
225 ptr = (void*)*link_addr_volatile;
227 * At this point we have a hidden pointer. If the GC runs
228 * here, it will not recognize the hidden pointer as a
229 * reference, and if the object behind it is not referenced
230 * elsewhere, it will be freed. Once the world is restarted
231 * we reveal the pointer, giving us a pointer to a freed
232 * object. To make sure we don't return it, we load the
233 * hidden pointer again. If it's still the same, we can be
234 * sure the object reference is valid.
236 if (ptr && MONO_GC_HANDLE_IS_OBJECT_POINTER (ptr))
237 obj = (GCObject *)MONO_GC_REVEAL_POINTER (ptr, is_weak);
243 * If a GC happens here, obj needs to be on the stack or in a
244 * register, so we need to prevent this from being reordered
247 sgen_dummy_use (obj);
248 mono_memory_barrier ();
251 sgen_client_ensure_weak_gchandles_accessible ();
253 if ((void*)*link_addr_volatile != ptr)
260 sgen_gchandle_get_target (guint32 gchandle)
262 guint index = MONO_GC_HANDLE_SLOT (gchandle);
263 GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
264 HandleData *handles = gc_handles_for_type (type);
265 /* Invalid handles are possible; accessing one should produce NULL. (#34276) */
268 return link_get (sgen_array_list_get_slot (&handles->entries_array, index), MONO_GC_HANDLE_TYPE_IS_WEAK (type));
272 sgen_gchandle_set_target (guint32 gchandle, GCObject *obj)
274 guint32 index = MONO_GC_HANDLE_SLOT (gchandle);
275 GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
276 HandleData *handles = gc_handles_for_type (type);
277 volatile gpointer *slot;
283 slot = sgen_array_list_get_slot (&handles->entries_array, index);
287 SGEN_ASSERT (0, MONO_GC_HANDLE_OCCUPIED (entry), "Why are we setting the target on an unoccupied slot?");
288 } while (!try_set_slot (slot, obj, entry, (GCHandleType)handles->type));
292 mono_gchandle_slot_metadata (volatile gpointer *slot, gboolean is_weak)
298 if (!MONO_GC_HANDLE_OCCUPIED (entry))
300 if (MONO_GC_HANDLE_IS_OBJECT_POINTER (entry)) {
301 GCObject *obj = (GCObject *)MONO_GC_REVEAL_POINTER (entry, is_weak);
302 /* See note [dummy use]. */
303 sgen_dummy_use (obj);
305 * FIXME: The compiler could technically not carry a reference to obj around
306 * at this point and recompute it later, in which case we would still use
311 return sgen_client_metadata_for_object (obj);
313 metadata = MONO_GC_REVEAL_POINTER (entry, is_weak);
314 /* See note [dummy use]. */
315 sgen_dummy_use (metadata);
322 sgen_gchandle_get_metadata (guint32 gchandle)
324 guint32 index = MONO_GC_HANDLE_SLOT (gchandle);
325 GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
326 HandleData *handles = gc_handles_for_type (type);
327 volatile gpointer *slot;
331 if (index >= handles->entries_array.capacity)
334 slot = sgen_array_list_get_slot (&handles->entries_array, index);
336 return mono_gchandle_slot_metadata (slot, MONO_GC_HANDLE_TYPE_IS_WEAK (type));
340 sgen_gchandle_free (guint32 gchandle)
342 guint32 index = MONO_GC_HANDLE_SLOT (gchandle);
343 GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
344 HandleData *handles = gc_handles_for_type (type);
345 volatile gpointer *slot;
350 slot = sgen_array_list_get_slot (&handles->entries_array, index);
353 if (index < handles->entries_array.capacity && MONO_GC_HANDLE_OCCUPIED (entry)) {
355 protocol_gchandle_update (handles->type, (gpointer)slot, entry, NULL);
356 HEAVY_STAT (InterlockedDecrement ((volatile gint32 *)&stat_gc_handles_allocated));
358 /* print a warning? */
360 sgen_client_gchandle_destroyed (handles->type, gchandle);
364 * Returns whether to remove the link from its hash.
367 null_link_if_necessary (gpointer hidden, GCHandleType handle_type, int max_generation, gpointer user)
369 const gboolean is_weak = GC_HANDLE_TYPE_IS_WEAK (handle_type);
370 ScanCopyContext *ctx = (ScanCopyContext *)user;
374 if (!MONO_GC_HANDLE_VALID (hidden))
377 obj = (GCObject *)MONO_GC_REVEAL_POINTER (hidden, MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type));
378 SGEN_ASSERT (0, obj, "Why is the hidden pointer NULL?");
380 if (object_older_than (obj, max_generation))
383 if (major_collector.is_object_live (obj))
386 /* Clear link if object is ready for finalization. This check may be redundant wrt is_object_live(). */
387 if (sgen_gc_is_object_ready_for_finalization (obj))
388 return MONO_GC_HANDLE_METADATA_POINTER (sgen_client_metadata_for_object (obj), is_weak);
391 ctx->ops->copy_or_mark_object (©, ctx->queue);
392 SGEN_ASSERT (0, copy, "Why couldn't we copy the object?");
393 /* Update link if object was moved. */
394 return MONO_GC_HANDLE_OBJECT_POINTER (copy, is_weak);
397 /* LOCKING: requires that the GC lock is held */
399 sgen_null_link_in_range (int generation, ScanCopyContext ctx, gboolean track)
401 sgen_gchandle_iterate (track ? HANDLE_WEAK_TRACK : HANDLE_WEAK, generation, null_link_if_necessary, &ctx);
405 SgenObjectPredicateFunc predicate;
407 } WeakLinkAlivePredicateClosure;
410 null_link_if (gpointer hidden, GCHandleType handle_type, int max_generation, gpointer user)
412 WeakLinkAlivePredicateClosure *closure = (WeakLinkAlivePredicateClosure *)user;
415 if (!MONO_GC_HANDLE_VALID (hidden))
418 obj = (GCObject *)MONO_GC_REVEAL_POINTER (hidden, MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type));
419 SGEN_ASSERT (0, obj, "Why is the hidden pointer NULL?");
421 if (object_older_than (obj, max_generation))
424 if (closure->predicate (obj, closure->data))
425 return MONO_GC_HANDLE_METADATA_POINTER (sgen_client_default_metadata (), GC_HANDLE_TYPE_IS_WEAK (handle_type));
430 /* LOCKING: requires that the GC lock is held */
432 sgen_null_links_if (SgenObjectPredicateFunc predicate, void *data, int generation, gboolean track)
434 WeakLinkAlivePredicateClosure closure = { predicate, data };
435 sgen_gchandle_iterate (track ? HANDLE_WEAK_TRACK : HANDLE_WEAK, generation, null_link_if, &closure);
439 sgen_init_gchandles (void)
441 #ifdef HEAVY_STATISTICS
442 mono_counters_register ("GC handles allocated", MONO_COUNTER_GC | MONO_COUNTER_UINT, (void *)&stat_gc_handles_allocated);
443 mono_counters_register ("max GC handles allocated", MONO_COUNTER_GC | MONO_COUNTER_UINT, (void *)&stat_gc_handles_max_allocated);