2 * sgen-gchandles.c: SGen GC handles.
4 * Copyright (C) 2015 Xamarin Inc
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License 2.0 as published by the Free Software Foundation;
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
15 * You should have received a copy of the GNU Library General Public
16 * License 2.0 along with this library; if not, write to the Free
17 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 #include "mono/sgen/sgen-gc.h"
24 #include "mono/sgen/sgen-client.h"
25 #include "mono/utils/mono-membar.h"
27 #ifdef HEAVY_STATISTICS
28 static volatile guint32 stat_gc_handles_allocated = 0;
29 static volatile guint32 stat_gc_handles_max_allocated = 0;
32 #define BUCKETS (32 - MONO_GC_HANDLE_TYPE_SHIFT)
33 #define MIN_BUCKET_BITS (5)
34 #define MIN_BUCKET_SIZE (1 << MIN_BUCKET_BITS)
37 * A table of GC handle data, implementing a simple lock-free bitmap allocator.
39 * 'entries' is an array of pointers to buckets of increasing size. The first
40 * bucket has size 'MIN_BUCKET_SIZE', and each bucket is twice the size of the
43 * |-------|-- MIN_BUCKET_SIZE
45 * [1] -> xxxxxxxxxxxxxxxx
46 * [2] -> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
49 * The size of the spine, 'BUCKETS', is chosen so that the maximum number of
50 * entries is no less than the maximum index value of a GC handle.
52 * Each entry in a bucket is a pointer with two tag bits: if
53 * 'GC_HANDLE_OCCUPIED' returns true for a slot, then the slot is occupied; if
54 * so, then 'GC_HANDLE_VALID' gives whether the entry refers to a valid (1) or
55 * NULL (0) object reference. If the reference is valid, then the pointer is an
56 * object pointer. If the reference is NULL, and 'GC_HANDLE_TYPE_IS_WEAK' is
57 * true for 'type', then the pointer is a metadata pointer--this allows us to
58 * retrieve the domain ID of an expired weak reference in Mono.
60 * Finally, 'slot_hint' denotes the position of the last allocation, so that the
61 * whole array needn't be searched on every allocation.
65 volatile gpointer *volatile entries [BUCKETS];
66 volatile guint32 capacity;
67 volatile guint32 slot_hint;
68 volatile guint32 max_index;
73 bucket_size (guint index)
75 return 1 << (index + MIN_BUCKET_BITS);
78 /* Computes floor(log2(index + MIN_BUCKET_SIZE)) - 1, giving the index
79 * of the bucket containing a slot.
82 index_bucket (guint index)
85 return CHAR_BIT * sizeof (index) - __builtin_clz (index + MIN_BUCKET_SIZE) - 1 - MIN_BUCKET_BITS;
88 index += MIN_BUCKET_SIZE;
93 return count - 1 - MIN_BUCKET_BITS;
98 bucketize (guint index, guint *bucket, guint *offset)
100 *bucket = index_bucket (index);
101 *offset = index - bucket_size (*bucket) + MIN_BUCKET_SIZE;
105 protocol_gchandle_update (int handle_type, gpointer link, gpointer old_value, gpointer new_value)
107 gboolean old = MONO_GC_HANDLE_IS_OBJECT_POINTER (old_value);
108 gboolean new_ = MONO_GC_HANDLE_IS_OBJECT_POINTER (new_value);
109 gboolean track = handle_type == HANDLE_WEAK_TRACK;
111 if (!MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type))
115 binary_protocol_dislink_add (link, MONO_GC_REVEAL_POINTER (new_value, TRUE), track);
116 else if (old && !new_)
117 binary_protocol_dislink_remove (link, track);
118 else if (old && new_ && old_value != new_value)
119 binary_protocol_dislink_update (link, MONO_GC_REVEAL_POINTER (new_value, TRUE), track);
122 /* Returns the new value in the slot, or NULL if the CAS failed. */
123 static inline gpointer
124 try_set_slot (volatile gpointer *slot, GCObject *obj, gpointer old, GCHandleType type)
128 new_ = MONO_GC_HANDLE_OBJECT_POINTER (obj, GC_HANDLE_TYPE_IS_WEAK (type));
130 new_ = MONO_GC_HANDLE_METADATA_POINTER (sgen_client_default_metadata (), GC_HANDLE_TYPE_IS_WEAK (type));
131 SGEN_ASSERT (0, new_, "Why is the occupied bit not set?");
132 if (InterlockedCompareExchangePointer (slot, new_, old) == old) {
133 protocol_gchandle_update (type, (gpointer)slot, old, new_);
139 /* Try to claim a slot by setting its occupied bit. */
140 static inline gboolean
141 try_occupy_slot (HandleData *handles, guint bucket, guint offset, GCObject *obj, gboolean track)
143 volatile gpointer *link_addr = &(handles->entries [bucket] [offset]);
144 if (MONO_GC_HANDLE_OCCUPIED (*link_addr))
146 return try_set_slot (link_addr, obj, NULL, (GCHandleType)handles->type) != NULL;
149 static HandleData gc_handles [] = {
150 { { NULL }, 0, 0, 0, (HANDLE_WEAK) },
151 { { NULL }, 0, 0, 0, (HANDLE_WEAK_TRACK) },
152 { { NULL }, 0, 0, 0, (HANDLE_NORMAL) },
153 { { NULL }, 0, 0, 0, (HANDLE_PINNED) }
157 gc_handles_for_type (GCHandleType type)
159 return type < HANDLE_TYPE_MAX ? &gc_handles [type] : NULL;
162 /* This assumes that the world is stopped. */
164 sgen_mark_normal_gc_handles (void *addr, SgenUserMarkFunc mark_func, void *gc_data)
166 HandleData *handles = gc_handles_for_type (HANDLE_NORMAL);
167 size_t bucket, offset;
168 const guint max_bucket = index_bucket (handles->capacity);
170 const guint32 max_index = handles->max_index;
171 for (bucket = 0; bucket < max_bucket; ++bucket) {
172 volatile gpointer *entries = handles->entries [bucket];
173 for (offset = 0; offset < bucket_size (bucket); ++offset, ++index) {
174 volatile gpointer *entry;
175 gpointer hidden, revealed;
176 /* No need to iterate beyond the largest index ever allocated. */
177 if (index > max_index)
179 entry = &entries [offset];
181 revealed = MONO_GC_REVEAL_POINTER (hidden, FALSE);
182 if (!MONO_GC_HANDLE_IS_OBJECT_POINTER (hidden))
184 mark_func ((MonoObject **)&revealed, gc_data);
186 *entry = MONO_GC_HANDLE_OBJECT_POINTER (revealed, FALSE);
192 handle_data_find_unset (HandleData *handles, guint32 begin, guint32 end)
195 gint delta = begin < end ? +1 : -1;
196 for (index = begin; index < end; index += delta) {
197 guint bucket, offset;
198 volatile gpointer *entries;
199 bucketize (index, &bucket, &offset);
200 entries = handles->entries [bucket];
202 if (!MONO_GC_HANDLE_OCCUPIED (entries [offset]))
208 /* Adds a bucket if necessary and possible. */
210 handle_data_grow (HandleData *handles, guint32 old_capacity)
212 const guint new_bucket = index_bucket (old_capacity);
213 const guint32 growth = bucket_size (new_bucket);
214 const guint32 new_capacity = old_capacity + growth;
216 const size_t new_bucket_size = sizeof (**handles->entries) * growth;
217 if (handles->capacity >= new_capacity)
219 entries = (gpointer *)g_malloc0 (new_bucket_size);
220 if (handles->type == HANDLE_PINNED)
221 sgen_register_root ((char *)entries, new_bucket_size, SGEN_DESCRIPTOR_NULL, ROOT_TYPE_PINNED, MONO_ROOT_SOURCE_GC_HANDLE, "pinned gc handles");
222 /* The zeroing of the newly allocated bucket must be complete before storing
223 * the new bucket pointer.
225 mono_memory_write_barrier ();
226 if (InterlockedCompareExchangePointer ((volatile gpointer *)&handles->entries [new_bucket], entries, NULL) == NULL) {
227 /* It must not be the case that we succeeded in setting the bucket
228 * pointer, while someone else succeeded in changing the capacity.
230 if (InterlockedCompareExchange ((volatile gint32 *)&handles->capacity, new_capacity, old_capacity) != old_capacity)
231 g_assert_not_reached ();
232 handles->slot_hint = old_capacity;
235 /* Someone beat us to the allocation. */
236 if (handles->type == HANDLE_PINNED)
237 sgen_deregister_root ((char *)entries);
242 alloc_handle (HandleData *handles, GCObject *obj, gboolean track)
246 guint bucket, offset;
250 if (!handles->capacity)
251 handle_data_grow (handles, 0);
253 capacity = handles->capacity;
254 slot_hint = handles->slot_hint;
255 index = handle_data_find_unset (handles, slot_hint, capacity);
257 index = handle_data_find_unset (handles, 0, slot_hint);
259 handle_data_grow (handles, capacity);
262 handles->slot_hint = index;
265 * If a GC happens shortly after a new bucket is allocated, the entire
266 * bucket could be scanned even though it's mostly empty. To avoid this,
267 * we track the maximum index seen so far, so that we can skip the empty
270 * Note that we update `max_index` before we even try occupying the
271 * slot. If we did it the other way around and a GC happened in
272 * between, the GC wouldn't know that the slot was occupied. This is
273 * not a huge deal since `obj` is on the stack and thus pinned anyway,
274 * but hopefully some day it won't be anymore.
277 max_index = handles->max_index;
278 if (index <= max_index)
280 } while (InterlockedCompareExchange ((volatile gint32 *)&handles->max_index, index, max_index) != max_index);
282 bucketize (index, &bucket, &offset);
283 if (!try_occupy_slot (handles, bucket, offset, obj, track))
285 #ifdef HEAVY_STATISTICS
286 InterlockedIncrement ((volatile gint32 *)&stat_gc_handles_allocated);
287 if (stat_gc_handles_allocated > stat_gc_handles_max_allocated)
288 stat_gc_handles_max_allocated = stat_gc_handles_allocated;
290 /* Ensure that a GC handle cannot be given to another thread without the slot having been set. */
291 mono_memory_write_barrier ();
292 res = MONO_GC_HANDLE (index, handles->type);
293 sgen_client_gchandle_created (handles->type, obj, res);
298 object_older_than (GCObject *object, int generation)
300 return generation == GENERATION_NURSERY && !sgen_ptr_in_nursery (object);
304 * Maps a function over all GC handles.
305 * This assumes that the world is stopped!
308 sgen_gchandle_iterate (GCHandleType handle_type, int max_generation, SgenGCHandleIterateCallback callback, gpointer user)
310 HandleData *handle_data = gc_handles_for_type (handle_type);
311 size_t bucket, offset;
312 guint max_bucket = index_bucket (handle_data->capacity);
314 guint32 max_index = handle_data->max_index;
315 /* If a new bucket has been allocated, but the capacity has not yet been
316 * increased, nothing can yet have been allocated in the bucket because the
317 * world is stopped, so we shouldn't miss any handles during iteration.
319 for (bucket = 0; bucket < max_bucket; ++bucket) {
320 volatile gpointer *entries = handle_data->entries [bucket];
321 for (offset = 0; offset < bucket_size (bucket); ++offset, ++index) {
324 /* Table must contain no garbage pointers. */
326 /* No need to iterate beyond the largest index ever allocated. */
327 if (index > max_index)
329 hidden = entries [offset];
330 occupied = MONO_GC_HANDLE_OCCUPIED (hidden);
331 g_assert (hidden ? occupied : !occupied);
334 result = callback (hidden, handle_type, max_generation, user);
336 SGEN_ASSERT (0, MONO_GC_HANDLE_OCCUPIED (result), "Why did the callback return an unoccupied entry?");
338 HEAVY_STAT (InterlockedDecrement ((volatile gint32 *)&stat_gc_handles_allocated));
339 protocol_gchandle_update (handle_type, (gpointer)&entries [offset], hidden, result);
340 entries [offset] = result;
347 * @obj: managed object to get a handle for
348 * @pinned: whether the object should be pinned
350 * This returns a handle that wraps the object, this is used to keep a
351 * reference to a managed object from the unmanaged world and preventing the
352 * object from being disposed.
354 * If @pinned is false the address of the object can not be obtained, if it is
355 * true the address of the object can be obtained. This will also pin the
356 * object so it will not be possible by a moving garbage collector to move the
359 * Returns: a handle that can be used to access the object from
363 mono_gchandle_new (GCObject *obj, gboolean pinned)
365 return alloc_handle (gc_handles_for_type (pinned ? HANDLE_PINNED : HANDLE_NORMAL), obj, FALSE);
369 * mono_gchandle_new_weakref:
370 * @obj: managed object to get a handle for
371 * @track_resurrection: Determines how long to track the object, if this is set to TRUE, the object is tracked after finalization, if FALSE, the object is only tracked up until the point of finalization.
373 * This returns a weak handle that wraps the object, this is used to
374 * keep a reference to a managed object from the unmanaged world.
375 * Unlike the mono_gchandle_new the object can be reclaimed by the
376 * garbage collector. In this case the value of the GCHandle will be
379 * If @track_resurrection is TRUE the object will be tracked through
380 * finalization and if the object is resurrected during the execution
381 * of the finalizer, then the returned weakref will continue to hold
382 * a reference to the object. If @track_resurrection is FALSE, then
383 * the weak reference's target will become NULL as soon as the object
384 * is passed on to the finalizer.
386 * Returns: a handle that can be used to access the object from
390 mono_gchandle_new_weakref (GCObject *obj, gboolean track_resurrection)
392 return alloc_handle (gc_handles_for_type (track_resurrection ? HANDLE_WEAK_TRACK : HANDLE_WEAK), obj, track_resurrection);
396 link_get (volatile gpointer *link_addr, gboolean is_weak)
398 void *volatile *link_addr_volatile;
402 link_addr_volatile = link_addr;
403 ptr = (void*)*link_addr_volatile;
405 * At this point we have a hidden pointer. If the GC runs
406 * here, it will not recognize the hidden pointer as a
407 * reference, and if the object behind it is not referenced
408 * elsewhere, it will be freed. Once the world is restarted
409 * we reveal the pointer, giving us a pointer to a freed
410 * object. To make sure we don't return it, we load the
411 * hidden pointer again. If it's still the same, we can be
412 * sure the object reference is valid.
414 if (ptr && MONO_GC_HANDLE_IS_OBJECT_POINTER (ptr))
415 obj = (GCObject *)MONO_GC_REVEAL_POINTER (ptr, is_weak);
421 * If a GC happens here, obj needs to be on the stack or in a
422 * register, so we need to prevent this from being reordered
425 sgen_dummy_use (obj);
426 mono_memory_barrier ();
429 sgen_client_ensure_weak_gchandles_accessible ();
431 if ((void*)*link_addr_volatile != ptr)
438 * mono_gchandle_get_target:
439 * @gchandle: a GCHandle's handle.
441 * The handle was previously created by calling `mono_gchandle_new` or
442 * `mono_gchandle_new_weakref`.
444 * Returns a pointer to the `MonoObject*` represented by the handle or
445 * NULL for a collected object if using a weakref handle.
448 mono_gchandle_get_target (guint32 gchandle)
450 guint index = MONO_GC_HANDLE_SLOT (gchandle);
451 GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
452 HandleData *handles = gc_handles_for_type (type);
453 /* Invalid handles are possible; accessing one should produce NULL. (#34276) */
456 guint bucket, offset;
457 g_assert (index < handles->capacity);
458 bucketize (index, &bucket, &offset);
459 return link_get (&handles->entries [bucket] [offset], MONO_GC_HANDLE_TYPE_IS_WEAK (type));
463 sgen_gchandle_set_target (guint32 gchandle, GCObject *obj)
465 guint index = MONO_GC_HANDLE_SLOT (gchandle);
466 GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
467 HandleData *handles = gc_handles_for_type (type);
470 guint bucket, offset;
473 g_assert (index < handles->capacity);
474 bucketize (index, &bucket, &offset);
477 slot = handles->entries [bucket] [offset];
478 SGEN_ASSERT (0, MONO_GC_HANDLE_OCCUPIED (slot), "Why are we setting the target on an unoccupied slot?");
479 } while (!try_set_slot (&handles->entries [bucket] [offset], obj, slot, (GCHandleType)handles->type));
483 mono_gchandle_slot_metadata (volatile gpointer *slot_addr, gboolean is_weak)
489 if (!MONO_GC_HANDLE_OCCUPIED (slot))
491 if (MONO_GC_HANDLE_IS_OBJECT_POINTER (slot)) {
492 GCObject *obj = (GCObject *)MONO_GC_REVEAL_POINTER (slot, is_weak);
493 /* See note [dummy use]. */
494 sgen_dummy_use (obj);
496 * FIXME: The compiler could technically not carry a reference to obj around
497 * at this point and recompute it later, in which case we would still use
500 if (*slot_addr != slot)
502 return sgen_client_metadata_for_object (obj);
504 metadata = MONO_GC_REVEAL_POINTER (slot, is_weak);
505 /* See note [dummy use]. */
506 sgen_dummy_use (metadata);
507 if (*slot_addr != slot)
513 sgen_gchandle_get_metadata (guint32 gchandle)
515 guint index = MONO_GC_HANDLE_SLOT (gchandle);
516 GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
517 HandleData *handles = gc_handles_for_type (type);
520 guint bucket, offset;
521 if (index >= handles->capacity)
523 bucketize (index, &bucket, &offset);
524 return mono_gchandle_slot_metadata (&handles->entries [bucket] [offset], MONO_GC_HANDLE_TYPE_IS_WEAK (type));
528 * mono_gchandle_free:
529 * @gchandle: a GCHandle's handle.
531 * Frees the @gchandle handle. If there are no outstanding
532 * references, the garbage collector can reclaim the memory of the
536 mono_gchandle_free (guint32 gchandle)
538 guint index = MONO_GC_HANDLE_SLOT (gchandle);
539 GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
540 HandleData *handles = gc_handles_for_type (type);
543 guint bucket, offset;
545 bucketize (index, &bucket, &offset);
546 slot = handles->entries [bucket] [offset];
547 if (index < handles->capacity && MONO_GC_HANDLE_OCCUPIED (slot)) {
548 handles->entries [bucket] [offset] = NULL;
549 protocol_gchandle_update (handles->type, (gpointer)&handles->entries [bucket] [offset], slot, NULL);
550 HEAVY_STAT (InterlockedDecrement ((volatile gint32 *)&stat_gc_handles_allocated));
552 /* print a warning? */
554 sgen_client_gchandle_destroyed (handles->type, gchandle);
558 * Returns whether to remove the link from its hash.
561 null_link_if_necessary (gpointer hidden, GCHandleType handle_type, int max_generation, gpointer user)
563 const gboolean is_weak = GC_HANDLE_TYPE_IS_WEAK (handle_type);
564 ScanCopyContext *ctx = (ScanCopyContext *)user;
568 if (!MONO_GC_HANDLE_VALID (hidden))
571 obj = (GCObject *)MONO_GC_REVEAL_POINTER (hidden, MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type));
572 SGEN_ASSERT (0, obj, "Why is the hidden pointer NULL?");
574 if (object_older_than (obj, max_generation))
577 if (major_collector.is_object_live (obj))
580 /* Clear link if object is ready for finalization. This check may be redundant wrt is_object_live(). */
581 if (sgen_gc_is_object_ready_for_finalization (obj))
582 return MONO_GC_HANDLE_METADATA_POINTER (sgen_client_metadata_for_object (obj), is_weak);
585 ctx->ops->copy_or_mark_object (©, ctx->queue);
586 SGEN_ASSERT (0, copy, "Why couldn't we copy the object?");
587 /* Update link if object was moved. */
588 return MONO_GC_HANDLE_OBJECT_POINTER (copy, is_weak);
591 /* LOCKING: requires that the GC lock is held */
593 sgen_null_link_in_range (int generation, ScanCopyContext ctx, gboolean track)
595 sgen_gchandle_iterate (track ? HANDLE_WEAK_TRACK : HANDLE_WEAK, generation, null_link_if_necessary, &ctx);
599 SgenObjectPredicateFunc predicate;
601 } WeakLinkAlivePredicateClosure;
604 null_link_if (gpointer hidden, GCHandleType handle_type, int max_generation, gpointer user)
606 WeakLinkAlivePredicateClosure *closure = (WeakLinkAlivePredicateClosure *)user;
609 if (!MONO_GC_HANDLE_VALID (hidden))
612 obj = (GCObject *)MONO_GC_REVEAL_POINTER (hidden, MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type));
613 SGEN_ASSERT (0, obj, "Why is the hidden pointer NULL?");
615 if (object_older_than (obj, max_generation))
618 if (closure->predicate (obj, closure->data))
624 /* LOCKING: requires that the GC lock is held */
626 sgen_null_links_if (SgenObjectPredicateFunc predicate, void *data, int generation, gboolean track)
628 WeakLinkAlivePredicateClosure closure = { predicate, data };
629 sgen_gchandle_iterate (track ? HANDLE_WEAK_TRACK : HANDLE_WEAK, generation, null_link_if, &closure);
633 sgen_init_gchandles (void)
635 #ifdef HEAVY_STATISTICS
636 mono_counters_register ("GC handles allocated", MONO_COUNTER_GC | MONO_COUNTER_UINT, (void *)&stat_gc_handles_allocated);
637 mono_counters_register ("max GC handles allocated", MONO_COUNTER_GC | MONO_COUNTER_UINT, (void *)&stat_gc_handles_max_allocated);