X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mono%2Fsgen%2Fsgen-gchandles.c;h=6fc24a2151a8e4b464f94cb5724afe32af392a6e;hb=b9e6227efb697f121da8402ce96386d7735f31ce;hp=9d00c397b9d6fb996f780a454aa56eb8647c65c2;hpb=c1d81649cc1d16ee47bd6fb951e220d8aba6a1d0;p=mono.git diff --git a/mono/sgen/sgen-gchandles.c b/mono/sgen/sgen-gchandles.c index 9d00c397b9d..6fc24a2151a 100644 --- a/mono/sgen/sgen-gchandles.c +++ b/mono/sgen/sgen-gchandles.c @@ -3,18 +3,7 @@ * * 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" @@ -22,6 +11,7 @@ #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 @@ -29,26 +19,9 @@ static volatile guint32 stat_gc_handles_allocated = 0; 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 @@ -56,51 +29,13 @@ static volatile guint32 stat_gc_handles_max_allocated = 0; * 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) { @@ -136,21 +71,38 @@ try_set_slot (volatile gpointer *slot, GCObject *obj, gpointer old, GCHandleType 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 * @@ -164,102 +116,27 @@ 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); - 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 @@ -267,21 +144,13 @@ retry: * 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) @@ -308,38 +177,28 @@ void 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; } /** @@ -453,43 +312,40 @@ mono_gchandle_get_target (guint32 gchandle) /* 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); /* @@ -497,14 +353,14 @@ retry: * 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; } @@ -512,16 +368,19 @@ retry: 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)); } /** @@ -535,18 +394,20 @@ sgen_gchandle_get_metadata (guint32 gchandle) 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? */ @@ -616,7 +477,7 @@ null_link_if (gpointer hidden, GCHandleType handle_type, int max_generation, gpo 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; }