*
* 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.
+ * Licensed under the MIT license. See LICENSE file in the project root for full license information.
*/
#include "config.h"
#include "mono/sgen/sgen-gc.h"
#include "mono/sgen/sgen-client.h"
+#include "mono/sgen/sgen-array-list.h"
#include "mono/utils/mono-membar.h"
#ifdef HEAVY_STATISTICS
static volatile guint32 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
* 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;
- volatile guint32 max_index;
+ SgenArrayList entries_array;
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 void
protocol_gchandle_update (int handle_type, gpointer link, gpointer old_value, gpointer new_value)
{
return NULL;
}
+static inline gboolean
+is_slot_set (volatile gpointer *slot)
+{
+ gpointer entry = *slot;
+ if (MONO_GC_HANDLE_OCCUPIED (entry))
+ return TRUE;
+ return FALSE;
+}
+
/* 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)
+try_occupy_slot (volatile gpointer *slot, gpointer obj, int data)
{
- volatile gpointer *link_addr = &(handles->entries [bucket] [offset]);
- if (MONO_GC_HANDLE_OCCUPIED (*link_addr))
+ if (is_slot_set (slot))
return FALSE;
- return try_set_slot (link_addr, obj, NULL, (GCHandleType)handles->type) != NULL;
+ return try_set_slot (slot, (GCObject *)obj, NULL, (GCHandleType)data) != NULL;
+}
+
+static void
+bucket_alloc_callback (gpointer *bucket, guint32 new_bucket_size, gboolean alloc)
+{
+ if (alloc)
+ sgen_register_root ((char *)bucket, new_bucket_size, SGEN_DESCRIPTOR_NULL, ROOT_TYPE_PINNED, MONO_ROOT_SOURCE_GC_HANDLE, "pinned gc handles");
+ else
+ sgen_deregister_root ((char *)bucket);
}
static HandleData gc_handles [] = {
- { { NULL }, 0, 0, 0, (HANDLE_WEAK) },
- { { NULL }, 0, 0, 0, (HANDLE_WEAK_TRACK) },
- { { NULL }, 0, 0, 0, (HANDLE_NORMAL) },
- { { NULL }, 0, 0, 0, (HANDLE_PINNED) }
+ { SGEN_ARRAY_LIST_INIT (NULL, is_slot_set, try_occupy_slot, -1), (HANDLE_WEAK) },
+ { SGEN_ARRAY_LIST_INIT (NULL, is_slot_set, try_occupy_slot, -1), (HANDLE_WEAK_TRACK) },
+ { SGEN_ARRAY_LIST_INIT (NULL, is_slot_set, try_occupy_slot, -1), (HANDLE_NORMAL) },
+ { SGEN_ARRAY_LIST_INIT (bucket_alloc_callback, is_slot_set, try_occupy_slot, -1), (HANDLE_PINNED) }
};
static HandleData *
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);
- guint32 index = 0;
- const guint32 max_index = handles->max_index;
- for (bucket = 0; bucket < max_bucket; ++bucket) {
- volatile gpointer *entries = handles->entries [bucket];
- for (offset = 0; offset < bucket_size (bucket); ++offset, ++index) {
- volatile gpointer *entry;
- gpointer hidden, revealed;
- /* No need to iterate beyond the largest index ever allocated. */
- if (index > max_index)
- return;
- entry = &entries [offset];
- hidden = *entry;
- 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;
+ SgenArrayList *array = &handles->entries_array;
+ volatile gpointer *slot;
+ gpointer hidden, revealed;
+
+ SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
+ hidden = *slot;
+ 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);
+ *slot = MONO_GC_HANDLE_OBJECT_POINTER (revealed, FALSE);
+ } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
}
-/* 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 = (gpointer *)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");
- /* The zeroing of the newly allocated bucket must be complete before storing
- * the new bucket pointer.
- */
- mono_memory_write_barrier ();
- if (InterlockedCompareExchangePointer ((volatile gpointer *)&handles->entries [new_bucket], entries, NULL) == NULL) {
- /* It must not be the case that we succeeded in setting the bucket
- * pointer, while someone else succeeded in changing the capacity.
- */
- if (InterlockedCompareExchange ((volatile gint32 *)&handles->capacity, new_capacity, old_capacity) != old_capacity)
- g_assert_not_reached ();
- handles->slot_hint = old_capacity;
- 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;
- guint32 max_index;
- 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;
+ guint32 res, index;
+ SgenArrayList *array = &handles->entries_array;
/*
* If a GC happens shortly after a new bucket is allocated, the entire
* we track the maximum index seen so far, so that we can skip the empty
* slots.
*
- * Note that we update `max_index` before we even try occupying the
+ * Note that we update `next_slot` before we even try occupying the
* slot. If we did it the other way around and a GC happened in
* between, the GC wouldn't know that the slot was occupied. This is
* not a huge deal since `obj` is on the stack and thus pinned anyway,
* but hopefully some day it won't be anymore.
*/
- do {
- max_index = handles->max_index;
- if (index <= max_index)
- break;
- } while (InterlockedCompareExchange ((volatile gint32 *)&handles->max_index, index, max_index) != max_index);
-
- bucketize (index, &bucket, &offset);
- if (!try_occupy_slot (handles, bucket, offset, obj, track))
- goto retry;
+ index = sgen_array_list_add (array, obj, handles->type, TRUE);
#ifdef HEAVY_STATISTICS
InterlockedIncrement ((volatile gint32 *)&stat_gc_handles_allocated);
if (stat_gc_handles_allocated > stat_gc_handles_max_allocated)
sgen_gchandle_iterate (GCHandleType handle_type, int max_generation, SgenGCHandleIterateCallback callback, gpointer user)
{
HandleData *handle_data = gc_handles_for_type (handle_type);
- size_t bucket, offset;
- guint max_bucket = index_bucket (handle_data->capacity);
- guint32 index = 0;
- guint32 max_index = handle_data->max_index;
+ SgenArrayList *array = &handle_data->entries_array;
+ gpointer hidden, result, occupied;
+ volatile gpointer *slot;
+
/* 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, ++index) {
- gpointer hidden;
- gpointer result;
- /* Table must contain no garbage pointers. */
- gboolean occupied;
- /* No need to iterate beyond the largest index ever allocated. */
- if (index > max_index)
- return;
- hidden = entries [offset];
- occupied = MONO_GC_HANDLE_OCCUPIED (hidden);
- g_assert (hidden ? occupied : !occupied);
- if (!occupied)
- 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?");
- else
- HEAVY_STAT (InterlockedDecrement ((volatile gint32 *)&stat_gc_handles_allocated));
- protocol_gchandle_update (handle_type, (gpointer)&entries [offset], hidden, result);
- entries [offset] = result;
- }
- }
+ SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
+ hidden = *slot;
+ occupied = (gpointer) MONO_GC_HANDLE_OCCUPIED (hidden);
+ g_assert (hidden ? !!occupied : !occupied);
+ if (!occupied)
+ 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?");
+ else
+ HEAVY_STAT (InterlockedDecrement ((volatile gint32 *)&stat_gc_handles_allocated));
+ protocol_gchandle_update (handle_type, (gpointer)slot, hidden, result);
+ *slot = result;
+ } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
}
/**
/* Invalid handles are possible; accessing one should produce NULL. (#34276) */
if (!handles)
return NULL;
- 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));
+ return link_get (sgen_array_list_get_slot (&handles->entries_array, index), MONO_GC_HANDLE_TYPE_IS_WEAK (type));
}
void
sgen_gchandle_set_target (guint32 gchandle, GCObject *obj)
{
- guint index = MONO_GC_HANDLE_SLOT (gchandle);
+ guint32 index = MONO_GC_HANDLE_SLOT (gchandle);
GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
HandleData *handles = gc_handles_for_type (type);
+ volatile gpointer *slot;
+ gpointer entry;
+
if (!handles)
return;
- guint bucket, offset;
- gpointer slot;
- g_assert (index < handles->capacity);
- bucketize (index, &bucket, &offset);
+ slot = sgen_array_list_get_slot (&handles->entries_array, index);
do {
- slot = handles->entries [bucket] [offset];
- SGEN_ASSERT (0, MONO_GC_HANDLE_OCCUPIED (slot), "Why are we setting the target on an unoccupied slot?");
- } while (!try_set_slot (&handles->entries [bucket] [offset], obj, slot, (GCHandleType)handles->type));
+ entry = *slot;
+ SGEN_ASSERT (0, MONO_GC_HANDLE_OCCUPIED (entry), "Why are we setting the target on an unoccupied slot?");
+ } while (!try_set_slot (slot, obj, entry, (GCHandleType)handles->type));
}
static gpointer
-mono_gchandle_slot_metadata (volatile gpointer *slot_addr, gboolean is_weak)
+mono_gchandle_slot_metadata (volatile gpointer *slot, gboolean is_weak)
{
- gpointer slot;
+ gpointer entry;
gpointer metadata;
retry:
- slot = *slot_addr;
- if (!MONO_GC_HANDLE_OCCUPIED (slot))
+ entry = *slot;
+ if (!MONO_GC_HANDLE_OCCUPIED (entry))
return NULL;
- if (MONO_GC_HANDLE_IS_OBJECT_POINTER (slot)) {
- GCObject *obj = (GCObject *)MONO_GC_REVEAL_POINTER (slot, is_weak);
+ if (MONO_GC_HANDLE_IS_OBJECT_POINTER (entry)) {
+ GCObject *obj = (GCObject *)MONO_GC_REVEAL_POINTER (entry, is_weak);
/* See note [dummy use]. */
sgen_dummy_use (obj);
/*
* at this point and recompute it later, in which case we would still use
* it.
*/
- if (*slot_addr != slot)
+ if (*slot != entry)
goto retry;
return sgen_client_metadata_for_object (obj);
}
- metadata = MONO_GC_REVEAL_POINTER (slot, is_weak);
+ metadata = MONO_GC_REVEAL_POINTER (entry, is_weak);
/* See note [dummy use]. */
sgen_dummy_use (metadata);
- if (*slot_addr != slot)
+ if (*slot != entry)
goto retry;
return metadata;
}
gpointer
sgen_gchandle_get_metadata (guint32 gchandle)
{
- guint index = MONO_GC_HANDLE_SLOT (gchandle);
+ guint32 index = MONO_GC_HANDLE_SLOT (gchandle);
GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
HandleData *handles = gc_handles_for_type (type);
+ volatile gpointer *slot;
+
if (!handles)
return NULL;
- guint bucket, offset;
- if (index >= handles->capacity)
+ if (index >= handles->entries_array.capacity)
return NULL;
- bucketize (index, &bucket, &offset);
- return mono_gchandle_slot_metadata (&handles->entries [bucket] [offset], MONO_GC_HANDLE_TYPE_IS_WEAK (type));
+
+ slot = sgen_array_list_get_slot (&handles->entries_array, index);
+
+ return mono_gchandle_slot_metadata (slot, MONO_GC_HANDLE_TYPE_IS_WEAK (type));
}
/**
void
mono_gchandle_free (guint32 gchandle)
{
- guint index = MONO_GC_HANDLE_SLOT (gchandle);
+ guint32 index = MONO_GC_HANDLE_SLOT (gchandle);
GCHandleType type = MONO_GC_HANDLE_TYPE (gchandle);
HandleData *handles = gc_handles_for_type (type);
+ volatile gpointer *slot;
+ gpointer entry;
if (!handles)
return;
- guint bucket, offset;
- gpointer slot;
- bucketize (index, &bucket, &offset);
- slot = handles->entries [bucket] [offset];
- if (index < handles->capacity && MONO_GC_HANDLE_OCCUPIED (slot)) {
- handles->entries [bucket] [offset] = NULL;
- protocol_gchandle_update (handles->type, (gpointer)&handles->entries [bucket] [offset], slot, NULL);
+
+ slot = sgen_array_list_get_slot (&handles->entries_array, index);
+ entry = *slot;
+
+ if (index < handles->entries_array.capacity && MONO_GC_HANDLE_OCCUPIED (entry)) {
+ *slot = NULL;
+ protocol_gchandle_update (handles->type, (gpointer)slot, entry, NULL);
HEAVY_STAT (InterlockedDecrement ((volatile gint32 *)&stat_gc_handles_allocated));
} else {
/* print a warning? */
return hidden;
if (closure->predicate (obj, closure->data))
- return NULL;
+ return MONO_GC_HANDLE_METADATA_POINTER (sgen_client_default_metadata (), GC_HANDLE_TYPE_IS_WEAK (handle_type));
return hidden;
}