* sgen-bridge.c: Simple generational GC.
*
* Copyright 2011 Novell, Inc (http://www.novell.com)
+ * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
*
* THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
* OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
+#include "config.h"
+
#ifdef HAVE_SGEN_GC
#include <stdlib.h>
#include "sgen-gc.h"
#include "sgen-bridge.h"
+#include "utils/mono-logger-internal.h"
+#include "utils/mono-time.h"
+
typedef struct {
int size;
static void
dyn_array_ensure_capacity (DynArray *da, int capacity)
{
+ int old_capacity = da->capacity;
char *new_data;
- if (capacity <= da->capacity)
+ if (capacity <= old_capacity)
return;
if (da->capacity == 0)
new_data = mono_sgen_alloc_internal_dynamic (da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
memcpy (new_data, da->data, da->elem_size * da->size);
- mono_sgen_free_internal_dynamic (da->data, da->elem_size * da->size, INTERNAL_MEM_BRIDGE_DATA);
+ mono_sgen_free_internal_dynamic (da->data, da->elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
da->data = new_data;
}
*p = ptr;
}
+#define dyn_array_ptr_push dyn_array_ptr_add
+
+static void*
+dyn_array_ptr_pop (DynArray *da)
+{
+ void *p;
+ g_assert (da->size > 0);
+ p = DYN_ARRAY_PTR_REF (da, da->size - 1);
+ --da->size;
+ return p;
+}
+
static void
dyn_array_int_add (DynArray *da, int x)
{
return FALSE;
}
-static void
+static void G_GNUC_UNUSED
dyn_array_append (DynArray *dst, DynArray *src)
{
g_assert (dst->elem_size == src->elem_size);
dst->size += src->size;
}
+static DynArray merge_array;
+
+static void
+dyn_array_int_merge (DynArray *dst, DynArray *src)
+{
+ int i, j;
+
+ dyn_array_ensure_capacity (&merge_array, dst->size + src->size);
+ merge_array.size = 0;
+
+ for (i = j = 0; i < dst->size || j < src->size; ) {
+ if (i < dst->size && j < src->size) {
+ int a = DYN_ARRAY_INT_REF (dst, i);
+ int b = DYN_ARRAY_INT_REF (src, j);
+ if (a < b) {
+ dyn_array_int_add (&merge_array, a);
+ ++i;
+ } else if (a == b) {
+ dyn_array_int_add (&merge_array, a);
+ ++i;
+ ++j;
+ } else {
+ dyn_array_int_add (&merge_array, b);
+ ++j;
+ }
+ } else if (i < dst->size) {
+ dyn_array_int_add (&merge_array, DYN_ARRAY_INT_REF (dst, i));
+ ++i;
+ } else {
+ dyn_array_int_add (&merge_array, DYN_ARRAY_INT_REF (src, j));
+ ++j;
+ }
+ }
+
+ if (merge_array.size > dst->size) {
+ dyn_array_ensure_capacity (dst, merge_array.size);
+ memcpy (DYN_ARRAY_REF (dst, 0), DYN_ARRAY_REF (&merge_array, 0), merge_array.size * merge_array.elem_size);
+ dst->size = merge_array.size;
+ }
+}
+
+static void
+dyn_array_int_merge_one (DynArray *array, int value)
+{
+ int i;
+ int tmp;
+ int end = array->size;
+
+ for (i = 0; i < end; ++i) {
+ if (DYN_ARRAY_INT_REF (array, i) == value)
+ return;
+ else if (DYN_ARRAY_INT_REF (array, i) > value)
+ break;
+ }
+
+ dyn_array_ensure_capacity (array, array->size + 1);
+
+ if (i < end) {
+ tmp = DYN_ARRAY_INT_REF (array, i);
+ for (; i <= end; ++i) {
+ DYN_ARRAY_INT_REF (array, i) = value;
+ value = tmp;
+ tmp = DYN_ARRAY_INT_REF (array, i + 1);
+ }
+ DYN_ARRAY_INT_REF (array, end + 1) = tmp;
+ } else {
+ DYN_ARRAY_INT_REF (array, end) = value;
+ }
+ ++array->size;
+}
+
/*
* FIXME: Optimizations:
*
* just one source, so use the srcs pointer itself.
*/
typedef struct _HashEntry {
- MonoObject *obj;
+ MonoObject *obj; /* This is a duplicate - it's already stored in the hash table */
+
gboolean is_bridge;
gboolean is_visited;
DynArray srcs;
int scc_index;
-
- struct _HashEntry *next;
} HashEntry;
typedef struct _SCC {
DynArray xrefs; /* these are incoming, not outgoing */
} SCC;
-static int num_hash_entries = 0;
-static int hash_size = 0;
-static HashEntry **hash_table = NULL;
+static SgenHashTable hash_table = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_DATA, INTERNAL_MEM_BRIDGE_DATA, sizeof (HashEntry), mono_aligned_addr_hash, NULL);
static MonoGCBridgeCallbacks bridge_callbacks;
}
gboolean
-mono_sgen_need_bridge_processing (void)
+mono_sgen_is_bridge_object (MonoObject *obj)
{
- return bridge_callbacks.cross_references != NULL;
+ return bridge_callbacks.is_bridge_object (obj);
}
-static HashEntry**
-alloc_hash_table (int size)
-{
- HashEntry **table;
- table = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry*) * size, INTERNAL_MEM_BRIDGE_DATA);
- memset (table, 0, sizeof (HashEntry*) * size);
- return table;
-}
-
-static void
-rehash (void)
-{
- HashEntry **new_table;
- int new_size = hash_size << 1;
- int i;
-
- new_table = alloc_hash_table (new_size);
- for (i = 0; i < hash_size; ++i) {
- HashEntry *entry = hash_table [i];
- while (entry != NULL) {
- HashEntry *next = entry->next;
- int hash = ((mword)entry->obj >> 4) & (new_size - 1);
- entry->next = new_table [hash];
- new_table [hash] = entry;
- entry = next;
- }
- }
-
- mono_sgen_free_internal_dynamic (hash_table, sizeof (HashEntry*) * hash_size, INTERNAL_MEM_BRIDGE_DATA);
-
- hash_table = new_table;
- hash_size = new_size;
-}
-
-static HashEntry*
-lookup_hash_entry (MonoObject *obj)
+gboolean
+mono_sgen_need_bridge_processing (void)
{
- int hash = (mword)obj >> 4;
- HashEntry *entry;
-
- if (!hash_table) {
- g_assert (hash_size == 0 && num_hash_entries == 0);
- hash_size = 32;
- hash_table = alloc_hash_table (hash_size);
- }
-
- hash &= hash_size - 1;
- for (entry = hash_table [hash]; entry != NULL; entry = entry->next) {
- if (entry->obj == obj)
- return entry;
- }
-
- return NULL;
+ return bridge_callbacks.cross_references != NULL;
}
static HashEntry*
get_hash_entry (MonoObject *obj)
{
- HashEntry *entry = lookup_hash_entry (obj);
- int hash;
+ HashEntry *entry = mono_sgen_hash_table_lookup (&hash_table, obj);
+ HashEntry new_entry;
if (entry)
return entry;
- entry = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry), INTERNAL_MEM_BRIDGE_DATA);
- memset (entry, 0, sizeof (HashEntry));
-
- entry->obj = obj;
- dyn_array_ptr_init (&entry->srcs);
- entry->finishing_time = -1;
- entry->scc_index = -1;
+ memset (&new_entry, 0, sizeof (HashEntry));
- hash = ((mword)obj >> 4) & (hash_size - 1);
- entry->next = hash_table [hash];
- hash_table [hash] = entry;
+ new_entry.obj = obj;
+ dyn_array_ptr_init (&new_entry.srcs);
+ new_entry.finishing_time = -1;
+ new_entry.scc_index = -1;
- ++num_hash_entries;
+ mono_sgen_hash_table_replace (&hash_table, obj, &new_entry);
- if (num_hash_entries > hash_size >> 1)
- rehash ();
-
- return entry;
+ return mono_sgen_hash_table_lookup (&hash_table, obj);
}
static void
static void
free_data (void)
{
- int i;
+ MonoObject *obj;
+ HashEntry *entry;
int total_srcs = 0;
int max_srcs = 0;
- if (hash_table == NULL)
- return;
+ SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
+ total_srcs += entry->srcs.size;
+ if (entry->srcs.size > max_srcs)
+ max_srcs = entry->srcs.size;
+ dyn_array_uninit (&entry->srcs);
+ } SGEN_HASH_TABLE_FOREACH_END;
- for (i = 0; i < hash_size; ++i) {
- HashEntry *entry = hash_table [i];
- while (entry != NULL) {
- HashEntry *next = entry->next;
- total_srcs += entry->srcs.size;
- if (entry->srcs.size > max_srcs)
- max_srcs = entry->srcs.size;
- dyn_array_uninit (&entry->srcs);
- mono_sgen_free_internal_dynamic (entry, sizeof (HashEntry), INTERNAL_MEM_BRIDGE_DATA);
- entry = next;
- }
- }
-
- mono_sgen_free_internal_dynamic (hash_table, sizeof (HashEntry*) * hash_size, INTERNAL_MEM_BRIDGE_DATA);
-
- hash_size = 0;
- num_hash_entries = 0;
- hash_table = NULL;
+ mono_sgen_hash_table_clean (&hash_table);
+ dyn_array_uninit (&merge_array);
//g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
}
MonoObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
if (fwd) {
*objp = fwd;
- return lookup_hash_entry (fwd) == NULL;
+ return mono_sgen_hash_table_lookup (&hash_table, fwd) == NULL;
}
if (!mono_sgen_object_is_live (obj))
return FALSE;
- return lookup_hash_entry (obj) == NULL;
+ return mono_sgen_hash_table_lookup (&hash_table, obj) == NULL;
}
+static DynArray dfs_stack;
+
+static int dsf1_passes, dsf2_passes;
+
+
#undef HANDLE_PTR
#define HANDLE_PTR(ptr,obj) do { \
MonoObject *dst = (MonoObject*)*(ptr); \
- if (dst && !object_is_live (&dst)) \
- dfs1 (get_hash_entry (dst), obj_entry); \
+ if (dst && !object_is_live (&dst)) { \
+ dyn_array_ptr_push (&dfs_stack, obj_entry); \
+ dyn_array_ptr_push (&dfs_stack, get_hash_entry (dst)); \
+ } \
} while (0)
static void
dfs1 (HashEntry *obj_entry, HashEntry *src)
{
- MonoObject *obj = obj_entry->obj;
- char *start = (char*)obj;
+ g_assert (dfs_stack.size == 0);
- if (src) {
- //g_print ("link %s -> %s\n", mono_sgen_safe_name (src->obj), mono_sgen_safe_name (obj));
- add_source (obj_entry, src);
- } else {
- //g_print ("starting with %s\n", mono_sgen_safe_name (obj));
- }
+ dyn_array_ptr_push (&dfs_stack, src);
+ dyn_array_ptr_push (&dfs_stack, obj_entry);
- if (obj_entry->is_visited)
- return;
+ do {
+ MonoObject *obj;
+ char *start;
+ ++dsf1_passes;
- obj_entry->is_visited = TRUE;
+ obj_entry = dyn_array_ptr_pop (&dfs_stack);
+ if (obj_entry) {
+ src = dyn_array_ptr_pop (&dfs_stack);
+
+ obj = obj_entry->obj;
+ start = (char*)obj;
+
+ if (src) {
+ //g_print ("link %s -> %s\n", mono_sgen_safe_name (src->obj), mono_sgen_safe_name (obj));
+ add_source (obj_entry, src);
+ } else {
+ //g_print ("starting with %s\n", mono_sgen_safe_name (obj));
+ }
+
+ if (obj_entry->is_visited)
+ continue;
+
+ obj_entry->is_visited = TRUE;
+
+ dyn_array_ptr_push (&dfs_stack, obj_entry);
+ /* NULL marks that the next entry is to be finished */
+ dyn_array_ptr_push (&dfs_stack, NULL);
#include "sgen-scan-object.h"
+ } else {
+ obj_entry = dyn_array_ptr_pop (&dfs_stack);
- register_finishing_time (obj_entry, current_time++);
+ //g_print ("finish %s\n", mono_sgen_safe_name (obj_entry->obj));
+ register_finishing_time (obj_entry, current_time++);
+ }
+ } while (dfs_stack.size > 0);
}
static void
if (dyn_array_int_contains (&dst->xrefs, src->index))
return;
if (src->num_bridge_entries) {
- dyn_array_int_add (&dst->xrefs, src->index);
+ dyn_array_int_merge_one (&dst->xrefs, src->index);
} else {
int i;
- // FIXME: uniq here
- dyn_array_append (&dst->xrefs, &src->xrefs);
+ dyn_array_int_merge (&dst->xrefs, &src->xrefs);
for (i = 0; i < dst->xrefs.size; ++i)
g_assert (DYN_ARRAY_INT_REF (&dst->xrefs, i) != dst->index);
}
{
int i;
- if (entry->scc_index >= 0) {
- if (entry->scc_index != current_scc->index)
- scc_add_xref (DYN_ARRAY_REF (&sccs, entry->scc_index), current_scc);
- return;
- }
+ g_assert (dfs_stack.size == 0);
+
+ dyn_array_ptr_push (&dfs_stack, entry);
+
+ do {
+ entry = dyn_array_ptr_pop (&dfs_stack);
+ ++dsf2_passes;
+
+ if (entry->scc_index >= 0) {
+ if (entry->scc_index != current_scc->index)
+ scc_add_xref (DYN_ARRAY_REF (&sccs, entry->scc_index), current_scc);
+ continue;
+ }
- scc_add_entry (current_scc, entry);
+ scc_add_entry (current_scc, entry);
- for (i = 0; i < entry->srcs.size; ++i)
- dfs2 (DYN_ARRAY_PTR_REF (&entry->srcs, i));
+ for (i = 0; i < entry->srcs.size; ++i)
+ dyn_array_ptr_push (&dfs_stack, DYN_ARRAY_PTR_REF (&entry->srcs, i));
+ } while (dfs_stack.size > 0);
}
static int
return e2->finishing_time - e1->finishing_time;
}
+static unsigned long step_1, step_2, step_3, step_4, step_5, step_6, step_7, step_8;
+static int fist_pass_links, second_pass_links, sccs_links;
+static int max_sccs_links = 0;
+
void
-mono_sgen_bridge_processing (int num_objs, MonoObject **objs)
+mono_sgen_bridge_processing_start (int num_objs, MonoObject **objs)
{
- HashEntry **all_entries;
int j = 0;
- int num_sccs, num_xrefs;
- int max_entries, max_xrefs;
int i;
- MonoGCBridgeSCC **api_sccs;
- MonoGCBridgeXRef *api_xrefs;
+ SGEN_TV_DECLARE (atv);
+ SGEN_TV_DECLARE (btv);
+
+ fist_pass_links = second_pass_links = sccs_links = 0;
+ dsf1_passes = dsf2_passes = 0;
+ SGEN_TV_GETTIME (atv);
g_assert (mono_sgen_need_bridge_processing ());
}
num_objs = j;
+ SGEN_TV_GETTIME (btv);
+ step_1 = SGEN_TV_ELAPSED (atv, btv);
+
//g_print ("%d bridge objects\n", num_objs);
/* first DFS pass */
+ dyn_array_ptr_init (&dfs_stack);
+ dyn_array_int_init (&merge_array);
+
current_time = 0;
for (i = 0; i < num_objs; ++i)
dfs1 (get_hash_entry (objs [i]), NULL);
- //g_print ("%d entries - hash size %d\n", num_hash_entries, hash_size);
+ SGEN_TV_GETTIME (atv);
+ step_2 = SGEN_TV_ELAPSED (btv, atv);
+}
+
+void
+mono_sgen_bridge_processing_finish (int num_objs, MonoObject **objs)
+{
+ int i, j;
+ int num_sccs, num_xrefs;
+ int max_entries, max_xrefs;
+ int hash_table_size, sccs_size;
+ MonoObject *obj;
+ HashEntry *entry;
+ HashEntry **all_entries;
+ MonoGCBridgeSCC **api_sccs;
+ MonoGCBridgeXRef *api_xrefs;
+ SGEN_TV_DECLARE (atv);
+ SGEN_TV_DECLARE (btv);
+
+ SGEN_TV_GETTIME (atv);
/* alloc and fill array of all entries */
- all_entries = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry*) * num_hash_entries, INTERNAL_MEM_BRIDGE_DATA);
+ all_entries = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
j = 0;
- max_entries = 0;
- for (i = 0; i < hash_size; ++i) {
- HashEntry *entry;
- int length = 0;
- for (entry = hash_table [i]; entry != NULL; entry = entry->next) {
- g_assert (entry->finishing_time >= 0);
- all_entries [j++] = entry;
- ++length;
- }
- if (length > max_entries)
- max_entries = length;
- }
- g_assert (j == num_hash_entries);
-
- //g_print ("max hash bucket length %d\n", max_entries);
+ SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
+ g_assert (entry->finishing_time >= 0);
+ all_entries [j++] = entry;
+ fist_pass_links += entry->srcs.size;
+ } SGEN_HASH_TABLE_FOREACH_END;
+ g_assert (j == hash_table.num_entries);
+ hash_table_size = hash_table.num_entries;
/* sort array according to decreasing finishing time */
- qsort (all_entries, num_hash_entries, sizeof (HashEntry*), compare_hash_entries);
+ qsort (all_entries, hash_table.num_entries, sizeof (HashEntry*), compare_hash_entries);
+
+ SGEN_TV_GETTIME (btv);
+ step_3 = SGEN_TV_ELAPSED (atv, btv);
/* second DFS pass */
dyn_array_init (&sccs, sizeof (SCC));
- for (i = 0; i < num_hash_entries; ++i) {
+ for (i = 0; i < hash_table.num_entries; ++i) {
HashEntry *entry = all_entries [i];
if (entry->scc_index < 0) {
int index = sccs.size;
}
}
+ sccs_size = sccs.size;
+
+ for (i = 0; i < hash_table.num_entries; ++i) {
+ HashEntry *entry = all_entries [i];
+ second_pass_links += entry->srcs.size;
+ }
+
+ SGEN_TV_GETTIME (atv);
+ step_4 = SGEN_TV_ELAPSED (btv, atv);
+
//g_print ("%d sccs\n", sccs.size);
+ dyn_array_uninit (&dfs_stack);
+
/* init data for callback */
num_sccs = 0;
g_assert (scc->index == i);
if (scc->num_bridge_entries)
++num_sccs;
+ sccs_links += scc->xrefs.size;
+ max_sccs_links = MAX (max_sccs_links, scc->xrefs.size);
}
api_sccs = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
num_xrefs += scc->xrefs.size;
}
- for (i = 0; i < hash_size; ++i) {
- HashEntry *entry;
- for (entry = hash_table [i]; entry != NULL; entry = entry->next) {
- SCC *scc;
- if (!entry->is_bridge)
- continue;
- scc = DYN_ARRAY_REF (&sccs, entry->scc_index);
+ SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
+ if (entry->is_bridge) {
+ SCC *scc = DYN_ARRAY_REF (&sccs, entry->scc_index);
api_sccs [scc->api_index]->objs [scc->num_bridge_entries++] = entry->obj;
}
- }
+ } SGEN_HASH_TABLE_FOREACH_END;
api_xrefs = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
j = 0;
}
}
+ SGEN_TV_GETTIME (btv);
+ step_5 = SGEN_TV_ELAPSED (atv, btv);
+
/* free data */
j = 0;
}
dyn_array_uninit (&sccs);
- mono_sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * num_hash_entries, INTERNAL_MEM_BRIDGE_DATA);
+ mono_sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
free_data ();
+ SGEN_TV_GETTIME (atv);
+ step_6 = SGEN_TV_ELAPSED (btv, atv);
+
//g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
/* callback */
bridge_callbacks.cross_references (num_sccs, api_sccs, num_xrefs, api_xrefs);
+/*Release for finalization those objects we no longer care. */
+ SGEN_TV_GETTIME (btv);
+ step_7 = SGEN_TV_ELAPSED (atv, btv);
+
+ for (i = 0; i < num_sccs; ++i) {
+ if (!api_sccs [i]->objs [0])
+ continue;
+ for (j = 0; j < api_sccs [i]->num_objs; ++j)
+ mono_sgen_mark_bridge_object (api_sccs [i]->objs [j]);
+ }
+
/* free callback data */
for (i = 0; i < num_sccs; ++i) {
mono_sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
mono_sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
+
+ SGEN_TV_GETTIME (atv);
+ step_8 = SGEN_TV_ELAPSED (btv, atv);
+
+ mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_BRIDGE num-objects %d num_hash_entries %d sccs size %d init %.2fms df1 %.2fms sort %.2fms dfs2 %.2fms setup-cb %.2fms free-data %.2fms user-cb %.2fms clenanup %.2fms links %d/%d/%d/%d dfs passes %d/%d",
+ num_objs, hash_table_size, sccs.size,
+ step_1 / 1000.0f,
+ step_2 / 1000.0f,
+ step_3 / 1000.0f,
+ step_4 / 1000.0f,
+ step_5 / 1000.0f,
+ step_6 / 1000.0f,
+ step_7 / 1000.0f,
+ step_8 / 1000.f,
+ fist_pass_links, second_pass_links, sccs_links, max_sccs_links,
+ dsf1_passes, dsf2_passes);
+
}
static gboolean
projects / mono.git / blobdiff