#include "tabledefs.h"
#include "utils/mono-logger-internals.h"
-typedef struct {
- int size;
- int capacity;
- char *data;
-} DynArray;
-
-/*Specializations*/
-
-typedef struct {
- DynArray array;
-} DynPtrArray;
-
-/* private */
-
-static void
-dyn_array_uninit (DynArray *da, int elem_size)
-{
- if (da->capacity <= 0)
- return;
+#include "sgen-dynarray.h"
- sgen_free_internal_dynamic (da->data, elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
- da->data = NULL;
-}
-
-static void
-dyn_array_ensure_capacity (DynArray *da, int capacity, int elem_size)
-{
- int old_capacity = da->capacity;
- char *new_data;
-
- if (capacity <= old_capacity)
- return;
-
- if (da->capacity == 0)
- da->capacity = 2;
- while (capacity > da->capacity)
- da->capacity *= 2;
-
- new_data = (char *)sgen_alloc_internal_dynamic (elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA, TRUE);
- if (da->data) {
- memcpy (new_data, da->data, elem_size * da->size);
- sgen_free_internal_dynamic (da->data, elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
- }
- da->data = new_data;
-}
-
-static void*
-dyn_array_add (DynArray *da, int elem_size)
-{
- void *p;
-
- dyn_array_ensure_capacity (da, da->size + 1, elem_size);
-
- p = da->data + da->size * elem_size;
- ++da->size;
- return p;
-}
-
-/* ptr */
-
-static void
-dyn_array_ptr_uninit (DynPtrArray *da)
-{
- dyn_array_uninit (&da->array, sizeof (void*));
-}
-
-static int
-dyn_array_ptr_size (DynPtrArray *da)
-{
- return da->array.size;
-}
-
-static void
-dyn_array_ptr_set_size (DynPtrArray *da, int size)
-{
- da->array.size = size;
-}
-
-static void*
-dyn_array_ptr_get (DynPtrArray *da, int x)
-{
- return ((void**)da->array.data)[x];
-}
-
-static void
-dyn_array_ptr_add (DynPtrArray *da, void *ptr)
-{
- void **p = (void **)dyn_array_add (&da->array, sizeof (void*));
- *p = ptr;
-}
-
-#define dyn_array_ptr_push dyn_array_ptr_add
-
-static void*
-dyn_array_ptr_pop (DynPtrArray *da)
-{
- void *p;
- int size = da->array.size;
- g_assert (size > 0);
- p = dyn_array_ptr_get (da, size - 1);
- --da->array.size;
- return p;
-}
-
-static void
-dyn_array_ptr_ensure_capacity (DynPtrArray *da, int capacity)
-{
- dyn_array_ensure_capacity (&da->array, capacity, sizeof (void*));
-}
-
-
-static void
-dyn_array_ptr_set_all (DynPtrArray *dst, DynPtrArray *src)
-{
- if (src->array.size > 0) {
- dyn_array_ptr_ensure_capacity (dst, src->array.size);
- memcpy (dst->array.data, src->array.data, src->array.size * sizeof (void*));
- }
- dst->array.size = src->array.size;
-}
+/*
+ * See comments in sgen-bridge.h
+ *
+ * This bridge implementation is based on the tarjan algorithm for strongly
+ * connected components. It has two elements:
+ *
+ * - Standard tarjan SCC algorithm to convert graph to SCC forest
+ *
+ * - "Colors": We reduce the SCC forest to bridged-SCCs-only by using a
+ * "color" algorithm devised by Kumpera. Consider the set of bridged SCCs
+ * which is reachable from a given object. We call each such unique set a
+ * "color". We compute the set of colors and which colors contain links to
+ * which colors. The color graph then becomes the reduced SCC graph.
+ */
static void
enable_accounting (void)
// hash_table = (SgenHashTable)SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_HASH_TABLE, INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY, sizeof (HashEntryWithAccounting), mono_aligned_addr_hash, NULL);
}
+// Is this class bridged or not, and should its dependencies be scanned or not?
+// The result of this callback will be cached for use by is_opaque_object later.
static MonoGCBridgeObjectKind
class_kind (MonoClass *klass)
{
return GC_BRIDGE_TRANSPARENT_CLASS;
}
-//enable unsage logging
+//enable usage logging
// #define DUMP_GRAPH 1
+// ScanData state
enum {
INITIAL,
SCANNED,
We can split this data structure in two, those with bridges and those without
*/
typedef struct {
+ // Colors (ColorDatas) linked to by objects with this color
DynPtrArray other_colors;
+ // Bridge objects (GCObjects) held by objects with this color
DynPtrArray bridges;
int api_index : 31;
unsigned visited : 1;
} ColorData;
-
-typedef struct {
- GCObject *obj; //XXX this can be eliminated.
+// Represents one managed object. Equivalent of new/old bridge "HashEntry"
+typedef struct _ScanData {
+ // FIXME this can be eliminated; if we have a ScanData we generally looked it up from its GCObject
+ GCObject *obj;
+ // We use the sgen lock_word in GCObject to store a pointer to the ScanData. Cache the original here to restore later:
mword lock_word;
ColorData *color;
+ // Tarjan algorithm index (order visited)
int index;
+ // Tarjan index of lowest-index object known reachable from here
int low_index : 27;
+ // See "ScanData state" enum above
unsigned state : 2;
unsigned is_bridge : 1;
+ // Similar to lock_word, we use these bits in the GCObject as scratch space then restore them when done
unsigned obj_state : 2;
} ScanData;
+// Stacks of ScanData objects used for tarjan algorithm.
+// The Tarjan algorithm is normally defined recursively; here scan_stack simulates the call stack of a recursive algorithm,
+// and loop_stack is the stack structure used by the algorithm itself.
+static DynPtrArray scan_stack, loop_stack;
-static DynPtrArray scan_stack, loop_stack, registered_bridges;
+// GCObjects on which register_finalized_object has been called
+static DynPtrArray registered_bridges;
+
+// ColorData objects
static DynPtrArray color_merge_array;
static int ignored_objects;
//ColorData buckets
#define NUM_COLOR_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ColorData))
+// Same as ObjectBucket except NUM_COLOR_ENTRIES and NUM_SCAN_ENTRIES differ
typedef struct _ColorBucket ColorBucket;
struct _ColorBucket {
ColorBucket *next;
res->obj = obj;
res->color = NULL;
res->index = res->low_index = -1;
+ res->state = INITIAL;
+ res->is_bridge = FALSE;
res->obj_state = o [0] & SGEN_VTABLE_BITS_MASK;
res->lock_word = o [1];
return FALSE;
}
+// Called during DFS; visits one child. If it is a candidate to be scanned, pushes it to the stacks.
static void
push_object (GCObject *obj)
{
if (dst) push_object (dst); \
} while (0)
+// dfs () function's queue-children-of-object operation.
static void
push_all (ScanData *data)
{
mword desc = sgen_obj_get_descriptor_safe (obj);
#if DUMP_GRAPH
- printf ("**scanning %p %s\n", obj, safe_name_bridge (obj));
+ printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->color);
#endif
#include "sgen/sgen-scan-object.h"
{
ScanData *other;
ColorData *cd;
- obj = bridge_object_forward (obj);
+ obj = bridge_object_forward (obj);
other = find_data (obj);
#if DUMP_GRAPH
#if DUMP_GRAPH
printf ("|SCC rooted in %s (%p) has bridge %d\n", safe_name_bridge (data->obj), data->obj, found_bridge);
printf ("\tpoints-to-colors: ");
- for (i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i)
+ for (int i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i)
printf ("%p ", dyn_array_ptr_get (&color_merge_array, i));
printf ("\n");
printf ("loop stack: ");
- for (i = 0; i < dyn_array_ptr_size (&loop_stack); ++i) {
+ for (int i = 0; i < dyn_array_ptr_size (&loop_stack); ++i) {
ScanData *other = dyn_array_ptr_get (&loop_stack, i);
printf ("(%d/%d)", other->index, other->low_index);
}
g_assert (cd->visited);
cd->visited = FALSE;
}
- dyn_array_ptr_set_size (&color_merge_array, 0);
+ dyn_array_ptr_empty (&color_merge_array);
found_bridge = FALSE;
}
g_assert (dyn_array_ptr_size (&scan_stack) == 1);
g_assert (dyn_array_ptr_size (&loop_stack) == 0);
- dyn_array_ptr_set_size (&color_merge_array, 0);
+ dyn_array_ptr_empty (&color_merge_array);
while (dyn_array_ptr_size (&scan_stack) > 0) {
ScanData *data = (ScanData *)dyn_array_ptr_pop (&scan_stack);
static void
reset_data (void)
{
- dyn_array_ptr_set_size (®istered_bridges, 0);
+ dyn_array_ptr_empty (®istered_bridges);
}
static void
cleanup (void)
{
- dyn_array_ptr_set_size (&scan_stack, 0);
- dyn_array_ptr_set_size (&loop_stack, 0);
- dyn_array_ptr_set_size (®istered_bridges, 0);
+ dyn_array_ptr_empty (&scan_stack);
+ dyn_array_ptr_empty (&loop_stack);
+ dyn_array_ptr_empty (®istered_bridges);
free_object_buckets ();
free_color_buckets ();
reset_cache ();
#if defined (DUMP_GRAPH)
printf ("----summary----\n");
printf ("bridges:\n");
- for (i = 0; i < bridge_count; ++i) {
+ for (int i = 0; i < bridge_count; ++i) {
ScanData *sd = find_data (dyn_array_ptr_get (®istered_bridges, i));
printf ("\t%s (%p) index %d color %p\n", safe_name_bridge (sd->obj), sd->obj, sd->index, sd->color);
}
if (!bridges)
continue;
- dyn_array_ptr_set_size (&color_merge_array, 0);
+ dyn_array_ptr_empty (&color_merge_array);
gather_xrefs (cd);
reset_xrefs (cd);
dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
#if defined (DUMP_GRAPH)
printf ("---xrefs:\n");
- for (i = 0; i < xref_count; ++i)
+ for (int i = 0; i < xref_count; ++i)
printf ("\t%d -> %d\n", api_xrefs [i].src_scc_index, api_xrefs [i].dst_scc_index);
#endif
projects / mono.git / blobdiff