sgen-fin-weak-hash.c \
sgen-gc.c \
sgen-gc.h \
+ sgen-gchandles.c \
sgen-gray.c \
sgen-gray.h \
sgen-hash-table.c \
} SGEN_HASH_TABLE_FOREACH_END;
}
-/* GC Handles */
-
-#ifdef HEAVY_STATISTICS
-static volatile guint64 stat_gc_handles_allocated = 0;
-static volatile guint64 stat_gc_handles_max_allocated = 0;
-#endif
-
-#define BUCKETS (32 - MONO_GC_HANDLE_TYPE_SHIFT)
-#define MIN_BUCKET_BITS (5)
-#define MIN_BUCKET_SIZE (1 << MIN_BUCKET_BITS)
-
-/*
- * A table of GC handle data, implementing a simple lock-free bitmap allocator.
- *
- * 'entries' is an array of pointers to buckets of increasing size. The first
- * bucket has size 'MIN_BUCKET_SIZE', and each bucket is twice the size of the
- * previous, i.e.:
- *
- * |-------|-- MIN_BUCKET_SIZE
- * [0] -> xxxxxxxx
- * [1] -> xxxxxxxxxxxxxxxx
- * [2] -> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
- * ...
- *
- * The size of the spine, 'BUCKETS', is chosen so that the maximum number of
- * entries is no less than the maximum index value of a GC handle.
- *
- * Each entry in a bucket is a pointer with two tag bits: if
- * 'GC_HANDLE_OCCUPIED' returns true for a slot, then the slot is occupied; if
- * so, then 'GC_HANDLE_VALID' gives whether the entry refers to a valid (1) or
- * NULL (0) object reference. If the reference is valid, then the pointer is an
- * object pointer. If the reference is NULL, and 'GC_HANDLE_TYPE_IS_WEAK' is
- * true for 'type', then the pointer is a metadata pointer--this allows us to
- * retrieve the domain ID of an expired weak reference in Mono.
- *
- * Finally, 'slot_hint' denotes the position of the last allocation, so that the
- * whole array needn't be searched on every allocation.
- */
-
-typedef struct {
- volatile gpointer *volatile entries [BUCKETS];
- volatile guint32 capacity;
- volatile guint32 slot_hint;
- guint8 type;
-} HandleData;
-
-static inline guint
-bucket_size (guint index)
-{
- return 1 << (index + MIN_BUCKET_BITS);
-}
-
-/* Computes floor(log2(index + MIN_BUCKET_SIZE)) - 1, giving the index
- * of the bucket containing a slot.
- */
-static inline guint
-index_bucket (guint index)
-{
-#ifdef __GNUC__
- return CHAR_BIT * sizeof (index) - __builtin_clz (index + MIN_BUCKET_SIZE) - 1 - MIN_BUCKET_BITS;
-#else
- guint count = 0;
- index += MIN_BUCKET_SIZE;
- while (index) {
- ++count;
- index >>= 1;
- }
- return count - 1 - MIN_BUCKET_BITS;
-#endif
-}
-
-static inline void
-bucketize (guint index, guint *bucket, guint *offset)
-{
- *bucket = index_bucket (index);
- *offset = index - bucket_size (*bucket) + MIN_BUCKET_SIZE;
-}
-
-static inline gboolean
-try_set_slot (volatile gpointer *slot, GCObject *obj, gpointer old, GCHandleType type)
-{
- if (obj)
- return InterlockedCompareExchangePointer (slot, MONO_GC_HANDLE_OBJECT_POINTER (obj, GC_HANDLE_TYPE_IS_WEAK (type)), old) == old;
- return InterlockedCompareExchangePointer (slot, MONO_GC_HANDLE_METADATA_POINTER (sgen_client_default_metadata (), GC_HANDLE_TYPE_IS_WEAK (type)), old) == old;
-}
-
-/* Try to claim a slot by setting its occupied bit. */
-static inline gboolean
-try_occupy_slot (HandleData *handles, guint bucket, guint offset, GCObject *obj, gboolean track)
-{
- volatile gpointer *link_addr = &(handles->entries [bucket] [offset]);
- if (MONO_GC_HANDLE_OCCUPIED (*link_addr))
- return FALSE;
- return try_set_slot (link_addr, obj, NULL, handles->type);
-}
-
-#define EMPTY_HANDLE_DATA(type) { { NULL }, 0, 0, (type) }
-
-/* weak and weak-track arrays will be allocated in malloc memory
- */
-static HandleData gc_handles [] = {
- EMPTY_HANDLE_DATA (HANDLE_WEAK),
- EMPTY_HANDLE_DATA (HANDLE_WEAK_TRACK),
- EMPTY_HANDLE_DATA (HANDLE_NORMAL),
- EMPTY_HANDLE_DATA (HANDLE_PINNED)
-};
-
-static HandleData *
-gc_handles_for_type (GCHandleType type)
-{
- g_assert (type < HANDLE_TYPE_MAX);
- return &gc_handles [type];
-}
-
-/* This assumes that the world is stopped. */
-void
-sgen_mark_normal_gc_handles (void *addr, SgenUserMarkFunc mark_func, void *gc_data)
-{
- HandleData *handles = gc_handles_for_type (HANDLE_NORMAL);
- size_t bucket, offset;
- const guint max_bucket = index_bucket (handles->capacity);
- for (bucket = 0; bucket < max_bucket; ++bucket) {
- volatile gpointer *entries = handles->entries [bucket];
- for (offset = 0; offset < bucket_size (bucket); ++offset) {
- volatile gpointer *entry = &entries [offset];
- gpointer hidden = *entry;
- gpointer revealed = MONO_GC_REVEAL_POINTER (hidden, FALSE);
- if (!MONO_GC_HANDLE_IS_OBJECT_POINTER (hidden))
- continue;
- mark_func ((MonoObject **)&revealed, gc_data);
- g_assert (revealed);
- *entry = MONO_GC_HANDLE_OBJECT_POINTER (revealed, FALSE);
- }
- }
-}
-
-static guint
-handle_data_find_unset (HandleData *handles, guint32 begin, guint32 end)
-{
- guint index;
- gint delta = begin < end ? +1 : -1;
- for (index = begin; index < end; index += delta) {
- guint bucket, offset;
- volatile gpointer *entries;
- bucketize (index, &bucket, &offset);
- entries = handles->entries [bucket];
- g_assert (entries);
- if (!MONO_GC_HANDLE_OCCUPIED (entries [offset]))
- return index;
- }
- return -1;
-}
-
-/* Adds a bucket if necessary and possible. */
-static void
-handle_data_grow (HandleData *handles, guint32 old_capacity)
-{
- const guint new_bucket = index_bucket (old_capacity);
- const guint32 growth = bucket_size (new_bucket);
- const guint32 new_capacity = old_capacity + growth;
- gpointer *entries;
- const size_t new_bucket_size = sizeof (**handles->entries) * growth;
- if (handles->capacity >= new_capacity)
- return;
- entries = g_malloc0 (new_bucket_size);
- if (handles->type == HANDLE_PINNED)
- sgen_register_root ((char *)entries, new_bucket_size, SGEN_DESCRIPTOR_NULL, ROOT_TYPE_PINNED, MONO_ROOT_SOURCE_GC_HANDLE, "pinned gc handles");
- if (InterlockedCompareExchangePointer ((volatile gpointer *)&handles->entries [new_bucket], entries, NULL) == NULL) {
- if (InterlockedCompareExchange ((volatile gint32 *)&handles->capacity, new_capacity, old_capacity) != old_capacity)
- g_assert_not_reached ();
- handles->slot_hint = old_capacity;
- mono_memory_write_barrier ();
- return;
- }
- /* Someone beat us to the allocation. */
- if (handles->type == HANDLE_PINNED)
- sgen_deregister_root ((char *)entries);
- g_free (entries);
-}
-
-static guint32
-alloc_handle (HandleData *handles, GCObject *obj, gboolean track)
-{
- guint index;
- guint32 res;
- guint bucket, offset;
- guint32 capacity;
- guint32 slot_hint;
- if (!handles->capacity)
- handle_data_grow (handles, 0);
-retry:
- capacity = handles->capacity;
- slot_hint = handles->slot_hint;
- index = handle_data_find_unset (handles, slot_hint, capacity);
- if (index == -1)
- index = handle_data_find_unset (handles, 0, slot_hint);
- if (index == -1) {
- handle_data_grow (handles, capacity);
- goto retry;
- }
- handles->slot_hint = index;
- bucketize (index, &bucket, &offset);
- if (!try_occupy_slot (handles, bucket, offset, obj, track))
- goto retry;
-#ifdef HEAVY_STATISTICS
- InterlockedIncrement64 ((volatile gint64 *)&stat_gc_handles_allocated);
- if (stat_gc_handles_allocated > stat_gc_handles_max_allocated)
- stat_gc_handles_max_allocated = stat_gc_handles_allocated;
-#endif
- if (obj && MONO_GC_HANDLE_TYPE_IS_WEAK (handles->type))
- binary_protocol_dislink_add ((gpointer)&handles->entries [bucket] [offset], obj, track);
- /* Ensure that a GC handle cannot be given to another thread without the slot having been set. */
- mono_memory_write_barrier ();
- res = MONO_GC_HANDLE (index, handles->type);
- sgen_client_gchandle_created (handles->type, obj, res);
- return res;
-}
-
-static gboolean
-object_older_than (GCObject *object, int generation)
-{
- return generation == GENERATION_NURSERY && !sgen_ptr_in_nursery (object);
-}
-
-/*
- * Maps a function over all GC handles.
- * This assumes that the world is stopped!
- */
-void
-sgen_gchandle_iterate (GCHandleType handle_type, int max_generation, gpointer callback(gpointer, GCHandleType, int, gpointer), gpointer user)
-{
- HandleData *handle_data = gc_handles_for_type (handle_type);
- size_t bucket, offset;
- guint max_bucket = index_bucket (handle_data->capacity);
- /* If a new bucket has been allocated, but the capacity has not yet been
- * increased, nothing can yet have been allocated in the bucket because the
- * world is stopped, so we shouldn't miss any handles during iteration.
- */
- for (bucket = 0; bucket < max_bucket; ++bucket) {
- volatile gpointer *entries = handle_data->entries [bucket];
- for (offset = 0; offset < bucket_size (bucket); ++offset) {
- gpointer hidden = entries [offset];
- gpointer result;
- /* Table must contain no garbage pointers. */
- gboolean occupied = MONO_GC_HANDLE_OCCUPIED (hidden);
- g_assert (hidden ? occupied : !occupied);
- if (!occupied) // || !MONO_GC_HANDLE_VALID (hidden))
- continue;
- result = callback (hidden, handle_type, max_generation, user);
- if (result) {
- SGEN_ASSERT (0, MONO_GC_HANDLE_OCCUPIED (result), "Why did the callback return an unoccupied entry?");
- // FIXME: add the dislink_update protocol call here
- } else {
- // FIXME: enable this for weak links
- //binary_protocol_dislink_remove ((gpointer)&handles->entries [bucket] [offset], handles->type == HANDLE_WEAK_TRACK);
- HEAVY_STAT (InterlockedDecrement64 ((volatile gint64 *)&stat_gc_handles_allocated));
- }
- entries [offset] = result;
- }
- }
-}
-
-/**
- * mono_gchandle_new:
- * @obj: managed object to get a handle for
- * @pinned: whether the object should be pinned
- *
- * This returns a handle that wraps the object, this is used to keep a
- * reference to a managed object from the unmanaged world and preventing the
- * object from being disposed.
- *
- * If @pinned is false the address of the object can not be obtained, if it is
- * true the address of the object can be obtained. This will also pin the
- * object so it will not be possible by a moving garbage collector to move the
- * object.
- *
- * Returns: a handle that can be used to access the object from
- * unmanaged code.
- */
-guint32
-mono_gchandle_new (GCObject *obj, gboolean pinned)
-{
- return alloc_handle (gc_handles_for_type (pinned ? HANDLE_PINNED : HANDLE_NORMAL), obj, FALSE);
-}
-
-/**
- * mono_gchandle_new_weakref:
- * @obj: managed object to get a handle for
- * @pinned: whether the object should be pinned
- *
- * This returns a weak handle that wraps the object, this is used to
- * keep a reference to a managed object from the unmanaged world.
- * Unlike the mono_gchandle_new the object can be reclaimed by the
- * garbage collector. In this case the value of the GCHandle will be
- * set to zero.
- *
- * If @pinned is false the address of the object can not be obtained, if it is
- * true the address of the object can be obtained. This will also pin the
- * object so it will not be possible by a moving garbage collector to move the
- * object.
- *
- * Returns: a handle that can be used to access the object from
- * unmanaged code.
- */
-guint32
-mono_gchandle_new_weakref (GCObject *obj, gboolean track_resurrection)
-{
- return alloc_handle (gc_handles_for_type (track_resurrection ? HANDLE_WEAK_TRACK : HANDLE_WEAK), obj, track_resurrection);
-}
-
-static GCObject *
-link_get (volatile gpointer *link_addr, gboolean is_weak)
-{
- void *volatile *link_addr_volatile;
- void *ptr;
- GCObject *obj;
-retry:
- link_addr_volatile = link_addr;
- ptr = (void*)*link_addr_volatile;
- /*
- * At this point we have a hidden pointer. If the GC runs
- * here, it will not recognize the hidden pointer as a
- * reference, and if the object behind it is not referenced
- * elsewhere, it will be freed. Once the world is restarted
- * we reveal the pointer, giving us a pointer to a freed
- * object. To make sure we don't return it, we load the
- * hidden pointer again. If it's still the same, we can be
- * sure the object reference is valid.
- */
- if (ptr && MONO_GC_HANDLE_IS_OBJECT_POINTER (ptr))
- obj = (GCObject *)MONO_GC_REVEAL_POINTER (ptr, is_weak);
- else
- return NULL;
-
- /* Note [dummy use]:
- *
- * If a GC happens here, obj needs to be on the stack or in a
- * register, so we need to prevent this from being reordered
- * wrt the check.
- */
- mono_gc_dummy_use (obj);
- mono_memory_barrier ();
-
- if (is_weak)
- sgen_client_ensure_weak_gchandles_accessible ();
-
- if ((void*)*link_addr_volatile != ptr)
- goto retry;
-
- return obj;
-}
-
-/**
- * mono_gchandle_get_target:
- * @gchandle: a GCHandle's handle.
- *
- * The handle was previously created by calling mono_gchandle_new or
- * mono_gchandle_new_weakref.
- *
- * Returns a pointer to the MonoObject represented by the handle or
- * NULL for a collected object if using a weakref handle.
- */
-GCObject*
-mono_gchandle_get_target (guint32 gchandle)
-{
- guint index = MONO_GC_HANDLE_SLOT (gchandle);
- guint type = MONO_GC_HANDLE_TYPE (gchandle);
- HandleData *handles = gc_handles_for_type (type);
- guint bucket, offset;
- g_assert (index < handles->capacity);
- bucketize (index, &bucket, &offset);
- return link_get (&handles->entries [bucket] [offset], MONO_GC_HANDLE_TYPE_IS_WEAK (type));
-}
-
-void
-sgen_gchandle_set_target (guint32 gchandle, GCObject *obj)
-{
- guint index = MONO_GC_HANDLE_SLOT (gchandle);
- guint type = MONO_GC_HANDLE_TYPE (gchandle);
- HandleData *handles = gc_handles_for_type (type);
- gboolean track = handles->type == HANDLE_WEAK_TRACK;
- guint bucket, offset;
- gpointer slot;
-
- g_assert (index < handles->capacity);
- bucketize (index, &bucket, &offset);
-
-retry:
- slot = handles->entries [bucket] [offset];
- g_assert (MONO_GC_HANDLE_OCCUPIED (slot));
- if (!try_set_slot (&handles->entries [bucket] [offset], obj, slot, MONO_GC_HANDLE_TYPE_IS_WEAK (handles->type)))
- goto retry;
- if (MONO_GC_HANDLE_IS_OBJECT_POINTER (slot))
- binary_protocol_dislink_remove ((gpointer)&handles->entries [bucket] [offset], track);
- if (obj)
- binary_protocol_dislink_add ((gpointer)&handles->entries [bucket] [offset], obj, track);
-}
-
-static gpointer
-mono_gchandle_slot_metadata (volatile gpointer *slot_addr, gboolean is_weak)
-{
- gpointer slot;
- gpointer metadata;
-retry:
- slot = *slot_addr;
- if (!MONO_GC_HANDLE_OCCUPIED (slot))
- return NULL;
- if (MONO_GC_HANDLE_IS_OBJECT_POINTER (slot)) {
- GCObject *obj = MONO_GC_REVEAL_POINTER (slot, is_weak);
- /* See note [dummy use]. */
- mono_gc_dummy_use (obj);
- /*
- * FIXME: The compiler could technically not carry a reference to obj around
- * at this point and recompute it later, in which case we would still use
- * it.
- */
- if (*slot_addr != slot)
- goto retry;
- return sgen_client_metadata_for_object (obj);
- }
- metadata = MONO_GC_REVEAL_POINTER (slot, is_weak);
- /* See note [dummy use]. */
- mono_gc_dummy_use (metadata);
- if (*slot_addr != slot)
- goto retry;
- return metadata;
-}
-
-gpointer
-sgen_gchandle_get_metadata (guint32 gchandle)
-{
- guint index = MONO_GC_HANDLE_SLOT (gchandle);
- guint type = MONO_GC_HANDLE_TYPE (gchandle);
- HandleData *handles = gc_handles_for_type (type);
- guint bucket, offset;
- if (index >= handles->capacity)
- return NULL;
- bucketize (index, &bucket, &offset);
- return mono_gchandle_slot_metadata (&handles->entries [bucket] [offset], MONO_GC_HANDLE_TYPE_IS_WEAK (type));
-}
-
-/**
- * mono_gchandle_free:
- * @gchandle: a GCHandle's handle.
- *
- * Frees the @gchandle handle. If there are no outstanding
- * references, the garbage collector can reclaim the memory of the
- * object wrapped.
- */
-void
-mono_gchandle_free (guint32 gchandle)
-{
- guint index = MONO_GC_HANDLE_SLOT (gchandle);
- guint type = MONO_GC_HANDLE_TYPE (gchandle);
- HandleData *handles = gc_handles_for_type (type);
- guint bucket, offset;
- bucketize (index, &bucket, &offset);
- if (index < handles->capacity && MONO_GC_HANDLE_OCCUPIED (handles->entries [bucket] [offset])) {
- if (MONO_GC_HANDLE_TYPE_IS_WEAK (handles->type))
- binary_protocol_dislink_remove ((gpointer)&handles->entries [bucket] [offset], handles->type == HANDLE_WEAK_TRACK);
- handles->entries [bucket] [offset] = NULL;
- HEAVY_STAT (InterlockedDecrement64 ((volatile gint64 *)&stat_gc_handles_allocated));
- } else {
- /* print a warning? */
- }
- sgen_client_gchandle_destroyed (handles->type, gchandle);
-}
-
-/*
- * Returns whether to remove the link from its hash.
- */
-static gpointer
-null_link_if_necessary (gpointer hidden, GCHandleType handle_type, int max_generation, gpointer user)
-{
- const gboolean is_weak = GC_HANDLE_TYPE_IS_WEAK (handle_type);
- ScanCopyContext *ctx = (ScanCopyContext *)user;
- GCObject *obj;
- GCObject *copy;
-
- if (!MONO_GC_HANDLE_VALID (hidden))
- return hidden;
-
- obj = MONO_GC_REVEAL_POINTER (hidden, MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type));
- SGEN_ASSERT (0, obj, "Why is the hidden pointer NULL?");
-
- if (object_older_than (obj, max_generation))
- return hidden;
-
- if (major_collector.is_object_live (obj))
- return hidden;
-
- /* Clear link if object is ready for finalization. This check may be redundant wrt is_object_live(). */
- if (sgen_gc_is_object_ready_for_finalization (obj))
- return MONO_GC_HANDLE_METADATA_POINTER (sgen_client_metadata_for_object (obj), is_weak);
-
- ctx->ops->copy_or_mark_object (©, ctx->queue);
- g_assert (copy);
- /* binary_protocol_dislink_update (hidden_entry, copy, handle_type == HANDLE_WEAK_TRACK); */
-
- copy = obj;
- ctx->ops->copy_or_mark_object (©, ctx->queue);
- SGEN_ASSERT (0, copy, "Why couldn't we copy the object?");
- /* Update link if object was moved. */
- return MONO_GC_HANDLE_OBJECT_POINTER (copy, is_weak);
-}
-
-/* LOCKING: requires that the GC lock is held */
-void
-sgen_null_link_in_range (int generation, ScanCopyContext ctx, gboolean track)
-{
- sgen_gchandle_iterate (track ? HANDLE_WEAK_TRACK : HANDLE_WEAK, generation, null_link_if_necessary, &ctx);
-}
-
-typedef struct {
- SgenObjectPredicateFunc predicate;
- gpointer data;
-} WeakLinkAlivePredicateClosure;
-
-static gpointer
-null_link_if (gpointer hidden, GCHandleType handle_type, int max_generation, gpointer user)
-{
- /* Strictly speaking, function pointers are not guaranteed to have the same size as data pointers. */
- WeakLinkAlivePredicateClosure *closure = (WeakLinkAlivePredicateClosure *)user;
- GCObject *obj;
-
- if (!MONO_GC_HANDLE_VALID (hidden))
- return hidden;
-
- obj = MONO_GC_REVEAL_POINTER (hidden, MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type));
- SGEN_ASSERT (0, obj, "Why is the hidden pointer NULL?");
-
- if (object_older_than (obj, max_generation))
- return hidden;
-
- if (closure->predicate (obj, closure->data))
- return NULL;
-
- return hidden;
-}
-
-/* LOCKING: requires that the GC lock is held */
-void
-sgen_null_links_if (SgenObjectPredicateFunc predicate, void *data, int generation, gboolean track)
-{
- WeakLinkAlivePredicateClosure closure = { predicate, data };
- sgen_gchandle_iterate (track ? HANDLE_WEAK_TRACK : HANDLE_WEAK, generation, null_link_if, &closure);
-}
-
void
sgen_init_fin_weak_hash (void)
{
mono_counters_register ("FinWeak Increment other thread", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_increment_other_thread);
mono_counters_register ("FinWeak Index decremented", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_index_decremented);
mono_counters_register ("FinWeak Entry invalidated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_entry_invalidated);
-
- mono_counters_register ("GC handles allocated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gc_handles_allocated);
- mono_counters_register ("max GC handles allocated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gc_handles_max_allocated);
#endif
}
int sgen_gc_invoke_finalizers (void);
+/* GC handles */
+
+void sgen_init_gchandles (void);
+
+void sgen_null_links_if (SgenObjectPredicateFunc predicate, void *data, int generation, gboolean track);
+
+void sgen_gchandle_set_target (guint32 gchandle, GCObject *obj);
+void sgen_mark_normal_gc_handles (void *addr, SgenUserMarkFunc mark_func, void *gc_data);
+gpointer sgen_gchandle_get_metadata (guint32 gchandle);
+void sgen_gchandle_iterate (GCHandleType handle_type, int max_generation, gpointer callback(gpointer, GCHandleType, int, gpointer), gpointer user);
+
/* Other globals */
extern GCMemSection *nursery_section;
g_warning ("CORRUPT CANARY:\naddr->%p\ntype->%s\nexcepted->'%s'\nfound->'%s'\n", (char*) addr, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE ((addr))), CANARY_STRING, canary_copy); \
} }
-void sgen_gchandle_set_target (guint32 gchandle, GCObject *obj);
-void sgen_mark_normal_gc_handles (void *addr, SgenUserMarkFunc mark_func, void *gc_data);
-gpointer sgen_gchandle_get_metadata (guint32 gchandle);
-void sgen_gchandle_iterate (GCHandleType handle_type, int max_generation, gpointer callback(gpointer, GCHandleType, int, gpointer), gpointer user);
-
#endif /* HAVE_SGEN_GC */
#endif /* __MONO_SGENGC_H__ */
--- /dev/null
+/*
+ * sgen-gchandles.c: SGen GC handles.
+ *
+ * Copyright (C) 2015 Xamarin Inc
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License 2.0 as published by the Free Software Foundation;
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License 2.0 along with this library; if not, write to the Free
+ * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include "config.h"
+#ifdef HAVE_SGEN_GC
+
+#include "mono/sgen/sgen-gc.h"
+#include "mono/sgen/sgen-client.h"
+#include "mono/utils/mono-membar.h"
+
+#ifdef HEAVY_STATISTICS
+static volatile guint64 stat_gc_handles_allocated = 0;
+static volatile guint64 stat_gc_handles_max_allocated = 0;
+#endif
+
+#define BUCKETS (32 - MONO_GC_HANDLE_TYPE_SHIFT)
+#define MIN_BUCKET_BITS (5)
+#define MIN_BUCKET_SIZE (1 << MIN_BUCKET_BITS)
+
+/*
+ * A table of GC handle data, implementing a simple lock-free bitmap allocator.
+ *
+ * 'entries' is an array of pointers to buckets of increasing size. The first
+ * bucket has size 'MIN_BUCKET_SIZE', and each bucket is twice the size of the
+ * previous, i.e.:
+ *
+ * |-------|-- MIN_BUCKET_SIZE
+ * [0] -> xxxxxxxx
+ * [1] -> xxxxxxxxxxxxxxxx
+ * [2] -> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
+ * ...
+ *
+ * The size of the spine, 'BUCKETS', is chosen so that the maximum number of
+ * entries is no less than the maximum index value of a GC handle.
+ *
+ * Each entry in a bucket is a pointer with two tag bits: if
+ * 'GC_HANDLE_OCCUPIED' returns true for a slot, then the slot is occupied; if
+ * so, then 'GC_HANDLE_VALID' gives whether the entry refers to a valid (1) or
+ * NULL (0) object reference. If the reference is valid, then the pointer is an
+ * object pointer. If the reference is NULL, and 'GC_HANDLE_TYPE_IS_WEAK' is
+ * true for 'type', then the pointer is a metadata pointer--this allows us to
+ * retrieve the domain ID of an expired weak reference in Mono.
+ *
+ * Finally, 'slot_hint' denotes the position of the last allocation, so that the
+ * whole array needn't be searched on every allocation.
+ */
+
+typedef struct {
+ volatile gpointer *volatile entries [BUCKETS];
+ volatile guint32 capacity;
+ volatile guint32 slot_hint;
+ guint8 type;
+} HandleData;
+
+static inline guint
+bucket_size (guint index)
+{
+ return 1 << (index + MIN_BUCKET_BITS);
+}
+
+/* Computes floor(log2(index + MIN_BUCKET_SIZE)) - 1, giving the index
+ * of the bucket containing a slot.
+ */
+static inline guint
+index_bucket (guint index)
+{
+#ifdef __GNUC__
+ return CHAR_BIT * sizeof (index) - __builtin_clz (index + MIN_BUCKET_SIZE) - 1 - MIN_BUCKET_BITS;
+#else
+ guint count = 0;
+ index += MIN_BUCKET_SIZE;
+ while (index) {
+ ++count;
+ index >>= 1;
+ }
+ return count - 1 - MIN_BUCKET_BITS;
+#endif
+}
+
+static inline void
+bucketize (guint index, guint *bucket, guint *offset)
+{
+ *bucket = index_bucket (index);
+ *offset = index - bucket_size (*bucket) + MIN_BUCKET_SIZE;
+}
+
+static inline gboolean
+try_set_slot (volatile gpointer *slot, GCObject *obj, gpointer old, GCHandleType type)
+{
+ if (obj)
+ return InterlockedCompareExchangePointer (slot, MONO_GC_HANDLE_OBJECT_POINTER (obj, GC_HANDLE_TYPE_IS_WEAK (type)), old) == old;
+ return InterlockedCompareExchangePointer (slot, MONO_GC_HANDLE_METADATA_POINTER (sgen_client_default_metadata (), GC_HANDLE_TYPE_IS_WEAK (type)), old) == old;
+}
+
+/* Try to claim a slot by setting its occupied bit. */
+static inline gboolean
+try_occupy_slot (HandleData *handles, guint bucket, guint offset, GCObject *obj, gboolean track)
+{
+ volatile gpointer *link_addr = &(handles->entries [bucket] [offset]);
+ if (MONO_GC_HANDLE_OCCUPIED (*link_addr))
+ return FALSE;
+ return try_set_slot (link_addr, obj, NULL, handles->type);
+}
+
+#define EMPTY_HANDLE_DATA(type) { { NULL }, 0, 0, (type) }
+
+/* weak and weak-track arrays will be allocated in malloc memory
+ */
+static HandleData gc_handles [] = {
+ EMPTY_HANDLE_DATA (HANDLE_WEAK),
+ EMPTY_HANDLE_DATA (HANDLE_WEAK_TRACK),
+ EMPTY_HANDLE_DATA (HANDLE_NORMAL),
+ EMPTY_HANDLE_DATA (HANDLE_PINNED)
+};
+
+static HandleData *
+gc_handles_for_type (GCHandleType type)
+{
+ g_assert (type < HANDLE_TYPE_MAX);
+ return &gc_handles [type];
+}
+
+/* This assumes that the world is stopped. */
+void
+sgen_mark_normal_gc_handles (void *addr, SgenUserMarkFunc mark_func, void *gc_data)
+{
+ HandleData *handles = gc_handles_for_type (HANDLE_NORMAL);
+ size_t bucket, offset;
+ const guint max_bucket = index_bucket (handles->capacity);
+ for (bucket = 0; bucket < max_bucket; ++bucket) {
+ volatile gpointer *entries = handles->entries [bucket];
+ for (offset = 0; offset < bucket_size (bucket); ++offset) {
+ volatile gpointer *entry = &entries [offset];
+ gpointer hidden = *entry;
+ gpointer revealed = MONO_GC_REVEAL_POINTER (hidden, FALSE);
+ if (!MONO_GC_HANDLE_IS_OBJECT_POINTER (hidden))
+ continue;
+ mark_func ((MonoObject **)&revealed, gc_data);
+ g_assert (revealed);
+ *entry = MONO_GC_HANDLE_OBJECT_POINTER (revealed, FALSE);
+ }
+ }
+}
+
+static guint
+handle_data_find_unset (HandleData *handles, guint32 begin, guint32 end)
+{
+ guint index;
+ gint delta = begin < end ? +1 : -1;
+ for (index = begin; index < end; index += delta) {
+ guint bucket, offset;
+ volatile gpointer *entries;
+ bucketize (index, &bucket, &offset);
+ entries = handles->entries [bucket];
+ g_assert (entries);
+ if (!MONO_GC_HANDLE_OCCUPIED (entries [offset]))
+ return index;
+ }
+ return -1;
+}
+
+/* Adds a bucket if necessary and possible. */
+static void
+handle_data_grow (HandleData *handles, guint32 old_capacity)
+{
+ const guint new_bucket = index_bucket (old_capacity);
+ const guint32 growth = bucket_size (new_bucket);
+ const guint32 new_capacity = old_capacity + growth;
+ gpointer *entries;
+ const size_t new_bucket_size = sizeof (**handles->entries) * growth;
+ if (handles->capacity >= new_capacity)
+ return;
+ entries = g_malloc0 (new_bucket_size);
+ if (handles->type == HANDLE_PINNED)
+ sgen_register_root ((char *)entries, new_bucket_size, SGEN_DESCRIPTOR_NULL, ROOT_TYPE_PINNED, MONO_ROOT_SOURCE_GC_HANDLE, "pinned gc handles");
+ if (InterlockedCompareExchangePointer ((volatile gpointer *)&handles->entries [new_bucket], entries, NULL) == NULL) {
+ if (InterlockedCompareExchange ((volatile gint32 *)&handles->capacity, new_capacity, old_capacity) != old_capacity)
+ g_assert_not_reached ();
+ handles->slot_hint = old_capacity;
+ mono_memory_write_barrier ();
+ return;
+ }
+ /* Someone beat us to the allocation. */
+ if (handles->type == HANDLE_PINNED)
+ sgen_deregister_root ((char *)entries);
+ g_free (entries);
+}
+
+static guint32
+alloc_handle (HandleData *handles, GCObject *obj, gboolean track)
+{
+ guint index;
+ guint32 res;
+ guint bucket, offset;
+ guint32 capacity;
+ guint32 slot_hint;
+ if (!handles->capacity)
+ handle_data_grow (handles, 0);
+retry:
+ capacity = handles->capacity;
+ slot_hint = handles->slot_hint;
+ index = handle_data_find_unset (handles, slot_hint, capacity);
+ if (index == -1)
+ index = handle_data_find_unset (handles, 0, slot_hint);
+ if (index == -1) {
+ handle_data_grow (handles, capacity);
+ goto retry;
+ }
+ handles->slot_hint = index;
+ bucketize (index, &bucket, &offset);
+ if (!try_occupy_slot (handles, bucket, offset, obj, track))
+ goto retry;
+#ifdef HEAVY_STATISTICS
+ InterlockedIncrement64 ((volatile gint64 *)&stat_gc_handles_allocated);
+ if (stat_gc_handles_allocated > stat_gc_handles_max_allocated)
+ stat_gc_handles_max_allocated = stat_gc_handles_allocated;
+#endif
+ if (obj && MONO_GC_HANDLE_TYPE_IS_WEAK (handles->type))
+ binary_protocol_dislink_add ((gpointer)&handles->entries [bucket] [offset], obj, track);
+ /* Ensure that a GC handle cannot be given to another thread without the slot having been set. */
+ mono_memory_write_barrier ();
+ res = MONO_GC_HANDLE (index, handles->type);
+ sgen_client_gchandle_created (handles->type, obj, res);
+ return res;
+}
+
+static gboolean
+object_older_than (GCObject *object, int generation)
+{
+ return generation == GENERATION_NURSERY && !sgen_ptr_in_nursery (object);
+}
+
+/*
+ * Maps a function over all GC handles.
+ * This assumes that the world is stopped!
+ */
+void
+sgen_gchandle_iterate (GCHandleType handle_type, int max_generation, gpointer callback(gpointer, GCHandleType, int, gpointer), gpointer user)
+{
+ HandleData *handle_data = gc_handles_for_type (handle_type);
+ size_t bucket, offset;
+ guint max_bucket = index_bucket (handle_data->capacity);
+ /* If a new bucket has been allocated, but the capacity has not yet been
+ * increased, nothing can yet have been allocated in the bucket because the
+ * world is stopped, so we shouldn't miss any handles during iteration.
+ */
+ for (bucket = 0; bucket < max_bucket; ++bucket) {
+ volatile gpointer *entries = handle_data->entries [bucket];
+ for (offset = 0; offset < bucket_size (bucket); ++offset) {
+ gpointer hidden = entries [offset];
+ gpointer result;
+ /* Table must contain no garbage pointers. */
+ gboolean occupied = MONO_GC_HANDLE_OCCUPIED (hidden);
+ g_assert (hidden ? occupied : !occupied);
+ if (!occupied) // || !MONO_GC_HANDLE_VALID (hidden))
+ continue;
+ result = callback (hidden, handle_type, max_generation, user);
+ if (result) {
+ SGEN_ASSERT (0, MONO_GC_HANDLE_OCCUPIED (result), "Why did the callback return an unoccupied entry?");
+ // FIXME: add the dislink_update protocol call here
+ } else {
+ // FIXME: enable this for weak links
+ //binary_protocol_dislink_remove ((gpointer)&handles->entries [bucket] [offset], handles->type == HANDLE_WEAK_TRACK);
+ HEAVY_STAT (InterlockedDecrement64 ((volatile gint64 *)&stat_gc_handles_allocated));
+ }
+ entries [offset] = result;
+ }
+ }
+}
+
+/**
+ * mono_gchandle_new:
+ * @obj: managed object to get a handle for
+ * @pinned: whether the object should be pinned
+ *
+ * This returns a handle that wraps the object, this is used to keep a
+ * reference to a managed object from the unmanaged world and preventing the
+ * object from being disposed.
+ *
+ * If @pinned is false the address of the object can not be obtained, if it is
+ * true the address of the object can be obtained. This will also pin the
+ * object so it will not be possible by a moving garbage collector to move the
+ * object.
+ *
+ * Returns: a handle that can be used to access the object from
+ * unmanaged code.
+ */
+guint32
+mono_gchandle_new (GCObject *obj, gboolean pinned)
+{
+ return alloc_handle (gc_handles_for_type (pinned ? HANDLE_PINNED : HANDLE_NORMAL), obj, FALSE);
+}
+
+/**
+ * mono_gchandle_new_weakref:
+ * @obj: managed object to get a handle for
+ * @pinned: whether the object should be pinned
+ *
+ * This returns a weak handle that wraps the object, this is used to
+ * keep a reference to a managed object from the unmanaged world.
+ * Unlike the mono_gchandle_new the object can be reclaimed by the
+ * garbage collector. In this case the value of the GCHandle will be
+ * set to zero.
+ *
+ * If @pinned is false the address of the object can not be obtained, if it is
+ * true the address of the object can be obtained. This will also pin the
+ * object so it will not be possible by a moving garbage collector to move the
+ * object.
+ *
+ * Returns: a handle that can be used to access the object from
+ * unmanaged code.
+ */
+guint32
+mono_gchandle_new_weakref (GCObject *obj, gboolean track_resurrection)
+{
+ return alloc_handle (gc_handles_for_type (track_resurrection ? HANDLE_WEAK_TRACK : HANDLE_WEAK), obj, track_resurrection);
+}
+
+static GCObject *
+link_get (volatile gpointer *link_addr, gboolean is_weak)
+{
+ void *volatile *link_addr_volatile;
+ void *ptr;
+ GCObject *obj;
+retry:
+ link_addr_volatile = link_addr;
+ ptr = (void*)*link_addr_volatile;
+ /*
+ * At this point we have a hidden pointer. If the GC runs
+ * here, it will not recognize the hidden pointer as a
+ * reference, and if the object behind it is not referenced
+ * elsewhere, it will be freed. Once the world is restarted
+ * we reveal the pointer, giving us a pointer to a freed
+ * object. To make sure we don't return it, we load the
+ * hidden pointer again. If it's still the same, we can be
+ * sure the object reference is valid.
+ */
+ if (ptr && MONO_GC_HANDLE_IS_OBJECT_POINTER (ptr))
+ obj = (GCObject *)MONO_GC_REVEAL_POINTER (ptr, is_weak);
+ else
+ return NULL;
+
+ /* Note [dummy use]:
+ *
+ * If a GC happens here, obj needs to be on the stack or in a
+ * register, so we need to prevent this from being reordered
+ * wrt the check.
+ */
+ mono_gc_dummy_use (obj);
+ mono_memory_barrier ();
+
+ if (is_weak)
+ sgen_client_ensure_weak_gchandles_accessible ();
+
+ if ((void*)*link_addr_volatile != ptr)
+ goto retry;
+
+ return obj;
+}
+
+/**
+ * mono_gchandle_get_target:
+ * @gchandle: a GCHandle's handle.
+ *
+ * The handle was previously created by calling mono_gchandle_new or
+ * mono_gchandle_new_weakref.
+ *
+ * Returns a pointer to the MonoObject represented by the handle or
+ * NULL for a collected object if using a weakref handle.
+ */
+GCObject*
+mono_gchandle_get_target (guint32 gchandle)
+{
+ guint index = MONO_GC_HANDLE_SLOT (gchandle);
+ guint type = MONO_GC_HANDLE_TYPE (gchandle);
+ HandleData *handles = gc_handles_for_type (type);
+ guint bucket, offset;
+ g_assert (index < handles->capacity);
+ bucketize (index, &bucket, &offset);
+ return link_get (&handles->entries [bucket] [offset], MONO_GC_HANDLE_TYPE_IS_WEAK (type));
+}
+
+void
+sgen_gchandle_set_target (guint32 gchandle, GCObject *obj)
+{
+ guint index = MONO_GC_HANDLE_SLOT (gchandle);
+ guint type = MONO_GC_HANDLE_TYPE (gchandle);
+ HandleData *handles = gc_handles_for_type (type);
+ gboolean track = handles->type == HANDLE_WEAK_TRACK;
+ guint bucket, offset;
+ gpointer slot;
+
+ g_assert (index < handles->capacity);
+ bucketize (index, &bucket, &offset);
+
+retry:
+ slot = handles->entries [bucket] [offset];
+ g_assert (MONO_GC_HANDLE_OCCUPIED (slot));
+ if (!try_set_slot (&handles->entries [bucket] [offset], obj, slot, MONO_GC_HANDLE_TYPE_IS_WEAK (handles->type)))
+ goto retry;
+ if (MONO_GC_HANDLE_IS_OBJECT_POINTER (slot))
+ binary_protocol_dislink_remove ((gpointer)&handles->entries [bucket] [offset], track);
+ if (obj)
+ binary_protocol_dislink_add ((gpointer)&handles->entries [bucket] [offset], obj, track);
+}
+
+static gpointer
+mono_gchandle_slot_metadata (volatile gpointer *slot_addr, gboolean is_weak)
+{
+ gpointer slot;
+ gpointer metadata;
+retry:
+ slot = *slot_addr;
+ if (!MONO_GC_HANDLE_OCCUPIED (slot))
+ return NULL;
+ if (MONO_GC_HANDLE_IS_OBJECT_POINTER (slot)) {
+ GCObject *obj = MONO_GC_REVEAL_POINTER (slot, is_weak);
+ /* See note [dummy use]. */
+ mono_gc_dummy_use (obj);
+ /*
+ * FIXME: The compiler could technically not carry a reference to obj around
+ * at this point and recompute it later, in which case we would still use
+ * it.
+ */
+ if (*slot_addr != slot)
+ goto retry;
+ return sgen_client_metadata_for_object (obj);
+ }
+ metadata = MONO_GC_REVEAL_POINTER (slot, is_weak);
+ /* See note [dummy use]. */
+ mono_gc_dummy_use (metadata);
+ if (*slot_addr != slot)
+ goto retry;
+ return metadata;
+}
+
+gpointer
+sgen_gchandle_get_metadata (guint32 gchandle)
+{
+ guint index = MONO_GC_HANDLE_SLOT (gchandle);
+ guint type = MONO_GC_HANDLE_TYPE (gchandle);
+ HandleData *handles = gc_handles_for_type (type);
+ guint bucket, offset;
+ if (index >= handles->capacity)
+ return NULL;
+ bucketize (index, &bucket, &offset);
+ return mono_gchandle_slot_metadata (&handles->entries [bucket] [offset], MONO_GC_HANDLE_TYPE_IS_WEAK (type));
+}
+
+/**
+ * mono_gchandle_free:
+ * @gchandle: a GCHandle's handle.
+ *
+ * Frees the @gchandle handle. If there are no outstanding
+ * references, the garbage collector can reclaim the memory of the
+ * object wrapped.
+ */
+void
+mono_gchandle_free (guint32 gchandle)
+{
+ guint index = MONO_GC_HANDLE_SLOT (gchandle);
+ guint type = MONO_GC_HANDLE_TYPE (gchandle);
+ HandleData *handles = gc_handles_for_type (type);
+ guint bucket, offset;
+ bucketize (index, &bucket, &offset);
+ if (index < handles->capacity && MONO_GC_HANDLE_OCCUPIED (handles->entries [bucket] [offset])) {
+ if (MONO_GC_HANDLE_TYPE_IS_WEAK (handles->type))
+ binary_protocol_dislink_remove ((gpointer)&handles->entries [bucket] [offset], handles->type == HANDLE_WEAK_TRACK);
+ handles->entries [bucket] [offset] = NULL;
+ HEAVY_STAT (InterlockedDecrement64 ((volatile gint64 *)&stat_gc_handles_allocated));
+ } else {
+ /* print a warning? */
+ }
+ sgen_client_gchandle_destroyed (handles->type, gchandle);
+}
+
+/*
+ * Returns whether to remove the link from its hash.
+ */
+static gpointer
+null_link_if_necessary (gpointer hidden, GCHandleType handle_type, int max_generation, gpointer user)
+{
+ const gboolean is_weak = GC_HANDLE_TYPE_IS_WEAK (handle_type);
+ ScanCopyContext *ctx = (ScanCopyContext *)user;
+ GCObject *obj;
+ GCObject *copy;
+
+ if (!MONO_GC_HANDLE_VALID (hidden))
+ return hidden;
+
+ obj = MONO_GC_REVEAL_POINTER (hidden, MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type));
+ SGEN_ASSERT (0, obj, "Why is the hidden pointer NULL?");
+
+ if (object_older_than (obj, max_generation))
+ return hidden;
+
+ if (major_collector.is_object_live (obj))
+ return hidden;
+
+ /* Clear link if object is ready for finalization. This check may be redundant wrt is_object_live(). */
+ if (sgen_gc_is_object_ready_for_finalization (obj))
+ return MONO_GC_HANDLE_METADATA_POINTER (sgen_client_metadata_for_object (obj), is_weak);
+
+ copy = obj;
+ ctx->ops->copy_or_mark_object (©, ctx->queue);
+ SGEN_ASSERT (0, copy, "Why couldn't we copy the object?");
+ /* Update link if object was moved. */
+ return MONO_GC_HANDLE_OBJECT_POINTER (copy, is_weak);
+}
+
+/* LOCKING: requires that the GC lock is held */
+void
+sgen_null_link_in_range (int generation, ScanCopyContext ctx, gboolean track)
+{
+ sgen_gchandle_iterate (track ? HANDLE_WEAK_TRACK : HANDLE_WEAK, generation, null_link_if_necessary, &ctx);
+}
+
+typedef struct {
+ SgenObjectPredicateFunc predicate;
+ gpointer data;
+} WeakLinkAlivePredicateClosure;
+
+static gpointer
+null_link_if (gpointer hidden, GCHandleType handle_type, int max_generation, gpointer user)
+{
+ /* Strictly speaking, function pointers are not guaranteed to have the same size as data pointers. */
+ WeakLinkAlivePredicateClosure *closure = (WeakLinkAlivePredicateClosure *)user;
+ GCObject *obj;
+
+ if (!MONO_GC_HANDLE_VALID (hidden))
+ return hidden;
+
+ obj = MONO_GC_REVEAL_POINTER (hidden, MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type));
+ SGEN_ASSERT (0, obj, "Why is the hidden pointer NULL?");
+
+ if (object_older_than (obj, max_generation))
+ return hidden;
+
+ if (closure->predicate (obj, closure->data))
+ return NULL;
+
+ return hidden;
+}
+
+/* LOCKING: requires that the GC lock is held */
+void
+sgen_null_links_if (SgenObjectPredicateFunc predicate, void *data, int generation, gboolean track)
+{
+ WeakLinkAlivePredicateClosure closure = { predicate, data };
+ sgen_gchandle_iterate (track ? HANDLE_WEAK_TRACK : HANDLE_WEAK, generation, null_link_if, &closure);
+}
+
+void
+sgen_init_gchandles (void)
+{
+#ifdef HEAVY_STATISTICS
+ mono_counters_register ("GC handles allocated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gc_handles_allocated);
+ mono_counters_register ("max GC handles allocated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gc_handles_max_allocated);
+#endif
+}
+
+#endif