-/*
- * sgen-tarjan-bridge.c: Tarjan-based bridge implementation.
+/**
+ * \file
+ * Tarjan-based bridge implementation.
*
* Copyright 2011 Novell, Inc (http://www.novell.com)
* Copyright 2014 Xamarin Inc (http://www.xamarin.com)
* which colors. The color graph then becomes the reduced SCC graph.
*/
-static void
-enable_accounting (void)
-{
- // bridge_accounting_enabled = TRUE;
- // 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
/* FIXME the bridge check can be quite expensive, cache it at the class level. */
/* An array of a sealed type that is not a bridge will never get to a bridge */
- if ((elem_class->flags & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
+ if ((mono_class_get_flags (elem_class) & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
SGEN_LOG (6, "class %s is opaque\n", klass->name);
return GC_BRIDGE_OPAQUE_CLASS;
}
//enable usage logging
// #define DUMP_GRAPH 1
+/* Used in bridgeless_color_is_heavy:
+ * The idea here is as long as the reference fanin and fanout on a node are both 2 or greater, then
+ * removing that node will result in a net increase in edge count. So the question is which node
+ * removals are counterproductive (i.e., how many edges saved balances out one node added).
+ * The number of edges saved by preserving a node is (fanin*fanout - fanin - fanout).
+ *
+ * With all that in mind:
+ *
+ * - HEAVY_REFS_MIN is the number that *both* fanin and fanout must meet to preserve the node.
+ * - HEAVY_COMBINED_REFS_MIN is the number (fanin*fanout) must meet to preserve the node.
+ *
+ * Note HEAVY_COMBINED_REFS_MIN must be <= 2*INCOMING_COLORS_MAX, or we won't know the true fanin.
+ */
+
+#define HEAVY_REFS_MIN 2
+#define HEAVY_COMBINED_REFS_MIN 60
+
+/* Used in ColorData:
+ * The higher INCOMING_COLORS_BITS is the higher HEAVY_COMBINED_REFS_MIN can be (see above).
+ * However, API_INDEX_BITS + INCOMING_COLORS_BITS must be equal to 31, and if API_INDEX_BITS is too
+ * low then terrible things will happen if too many colors are generated. (The number of colors we
+ * will ever attempt to generate is currently naturally limited by the JNI GREF limit.)
+ */
+
+#define API_INDEX_BITS 26
+#define INCOMING_COLORS_BITS 5
+
+#define API_INDEX_MAX ((1<<API_INDEX_BITS)-1)
+#define INCOMING_COLORS_MAX ((1<<INCOMING_COLORS_BITS)-1)
+
// ScanData state
enum {
INITIAL,
We can split this data structure in two, those with bridges and those without
(and only bridgeless need to record incoming_colors)
*/
-#define API_INDEX_BITS 26
-#define INCOMING_COLORS_BITS 5
-#define API_INDEX_MAX ((1<<API_INDEX_BITS)-1)
-#define INCOMING_COLORS_MAX ((1<<INCOMING_COLORS_BITS)-1)
typedef struct {
- // Colors (ColorDatas) linked to by objects with this color
+ // Colors (ColorDatas) linked to by objects with this color
DynPtrArray other_colors;
- // Bridge objects (GCObjects) held by objects with this color
+ // Bridge objects (GCObjects) held by objects with this color
DynPtrArray bridges;
- // Index of this color's MonoGCBridgeSCC in the array passed to the client (or -1 for none)
+ // Index of this color's MonoGCBridgeSCC in the array passed to the client (or -1 for none)
signed api_index : API_INDEX_BITS;
- // Count of colors that list this color in their other_colors
+ // Count of colors that list this color in their other_colors
unsigned incoming_colors : INCOMING_COLORS_BITS;
unsigned visited : 1;
} ColorData;
unsigned obj_state : 2;
} ScanData;
-#define HEAVY_REFS_MIN 2
-#define HEAVY_COMBINED_REFS_MIN 60
-
/* Should color be made visible to client even though it has no bridges?
- * If fanin and fanout are both greater than 2, then returning TRUE here will add one node to
- * the final graph and reduce the total number of edges by some number. Return true if we
- * estimate the number of reduced edges to be enough to justify the new node.
- * Notice fanout is capped at INCOMING_COLORS_MAX so we can't know its exact true value.
+ * True if we predict the number of reduced edges to be enough to justify the extra node.
*/
-static inline gboolean bridgeless_color_is_heavy (ColorData *data) {
- int fanin = data->incoming_colors;
- int fanout = dyn_array_ptr_size (&data->other_colors);
- return fanin > HEAVY_REFS_MIN && fanout > HEAVY_REFS_MIN
- && fanin*fanout >= HEAVY_COMBINED_REFS_MIN;
+static inline gboolean
+bridgeless_color_is_heavy (ColorData *data) {
+ int fanin = data->incoming_colors;
+ int fanout = dyn_array_ptr_size (&data->other_colors);
+ return fanin > HEAVY_REFS_MIN && fanout > HEAVY_REFS_MIN
+ && fanin*fanout >= HEAVY_COMBINED_REFS_MIN;
}
// Should color be made visible to client?
-static inline gboolean color_visible_to_client (ColorData *data) {
- return dyn_array_ptr_size (&data->bridges) || bridgeless_color_is_heavy (data);
+static inline gboolean
+color_visible_to_client (ColorData *data) {
+ return dyn_array_ptr_size (&data->bridges) || bridgeless_color_is_heavy (data);
}
// Stacks of ScanData objects used for tarjan algorithm.
// GCObjects on which register_finalized_object has been called
static DynPtrArray registered_bridges;
-// ColorData objects
+// As we traverse the graph, which ColorData objects are accessible from our current position?
static DynPtrArray color_merge_array;
+// Running hash of the contents of the color_merge_array.
+static unsigned int color_merge_array_hash;
+
+static void color_merge_array_empty (void)
+{
+ dyn_array_ptr_empty (&color_merge_array);
+ color_merge_array_hash = 0;
+}
static int ignored_objects;
static int object_index;
//----------
typedef struct {
ColorData *color;
- int hash;
+ unsigned int hash;
} HashEntry;
/*
#define ELEMENTS_PER_BUCKET 8
#define COLOR_CACHE_SIZE 128
static HashEntry merge_cache [COLOR_CACHE_SIZE][ELEMENTS_PER_BUCKET];
+static unsigned int hash_perturb;
-static int
-mix_hash (size_t hash)
+// If true, disable an optimization where sometimes SCC nodes are merged without a perfect check
+static gboolean scc_precise_merge;
+
+static unsigned int
+mix_hash (uintptr_t source)
{
- return (int)(((hash * 215497) >> 16) ^ ((hash * 1823231) + hash));
+ unsigned int hash = source;
+
+ // The full hash determines whether two colors can be merged-- sometimes exclusively.
+ // This value changes every GC, so XORing it in before performing the hash will make the
+ // chance that two different colors will produce the same hash on successive GCs very low.
+ hash = hash ^ hash_perturb;
+
+ // Actual hash
+ hash = (((hash * 215497) >> 16) ^ ((hash * 1823231) + hash));
+
+ // Mix in highest bits on 64-bit systems only
+ if (sizeof (source) > 4)
+ hash = hash ^ (source >> 32);
+
+ return hash;
}
static void
reset_cache (void)
{
memset (merge_cache, 0, sizeof (merge_cache));
+
+ // When using the precise merge debug option, we do not want the inconsistency caused by hash_perturb.
+ if (!scc_precise_merge)
+ ++hash_perturb;
}
return FALSE;
}
+static gboolean
+match_colors_estimate (DynPtrArray *a, DynPtrArray *b)
+{
+ return dyn_array_ptr_size (a) == dyn_array_ptr_size (b);
+}
+
+
static gboolean
match_colors (DynPtrArray *a, DynPtrArray *b)
{
return TRUE;
}
-static int cache_hits, cache_misses, cache_abstains;
+// If scc_precise_merge, "semihits" refers to find_in_cache calls aborted because the merge array was too large.
+// Otherwise "semihits" refers to cache hits where the match was only estimated.
+static int cache_hits, cache_semihits, cache_misses;
// The cache contains only non-bridged colors.
static ColorData*
find_in_cache (int *insert_index)
{
HashEntry *bucket;
- int i, hash, size, index;
+ int i, size, index;
size = dyn_array_ptr_size (&color_merge_array);
- /* Cache checking is very ineficient with a lot of elements*/
- if (size > 3) {
- ++cache_abstains;
+
+ /* Color equality checking is very expensive with a lot of elements, so when there are many
+ * elements we switch to a cheap comparison method which allows false positives. When false
+ * positives occur the worst that can happen is two items will be inappropriately merged
+ * and memory will be retained longer than it should be. We assume that will correct itself
+ * on the next GC (the hash_perturb mechanism increases the probability of this).
+ *
+ * Because this has *some* potential to create problems, if the user set the debug option
+ * 'enable-tarjan-precise-merge' we bail out early (and never merge SCCs with >3 colors).
+ */
+ gboolean color_merge_array_large = size > 3;
+ if (scc_precise_merge && color_merge_array_large) {
+ ++cache_semihits;
return NULL;
}
- hash = 0;
- for (i = 0 ; i < size; ++i)
- hash += mix_hash ((size_t)dyn_array_ptr_get (&color_merge_array, i));
- if (!hash)
+ unsigned int hash = color_merge_array_hash;
+ if (!hash) // 0 is used to indicate an empty bucket entry
hash = 1;
index = hash & (COLOR_CACHE_SIZE - 1);
for (i = 0; i < ELEMENTS_PER_BUCKET; ++i) {
if (bucket [i].hash != hash)
continue;
- if (match_colors (&bucket [i].color->other_colors, &color_merge_array)) {
- ++cache_hits;
- return bucket [i].color;
+
+ if (color_merge_array_large) {
+ if (match_colors_estimate (&bucket [i].color->other_colors, &color_merge_array)) {
+ ++cache_semihits;
+ return bucket [i].color;
+ }
+ } else {
+ if (match_colors (&bucket [i].color->other_colors, &color_merge_array)) {
+ ++cache_hits;
+ return bucket [i].color;
+ }
}
}
cd = other->color;
if (!cd->visited) {
+ color_merge_array_hash += mix_hash ((uintptr_t) other->color);
dyn_array_ptr_add (&color_merge_array, other->color);
cd->visited = TRUE;
}
g_assert (cd->visited);
cd->visited = FALSE;
}
- dyn_array_ptr_empty (&color_merge_array);
+ color_merge_array_empty ();
found_bridge = FALSE;
}
g_assert (dyn_array_ptr_size (&scan_stack) == 1);
g_assert (dyn_array_ptr_size (&loop_stack) == 0);
- dyn_array_ptr_empty (&color_merge_array);
+ color_merge_array_empty ();
while (dyn_array_ptr_size (&scan_stack) > 0) {
ScanData *data = (ScanData *)dyn_array_ptr_pop (&scan_stack);
if (!color_visible_to_client (cd))
continue;
- dyn_array_ptr_empty (&color_merge_array);
+ color_merge_array_empty ();
gather_xrefs (cd);
reset_xrefs (cd);
dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
cleanup_time = step_timer (&curtime);
- mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_TAR_BRIDGE bridges %d objects %d opaque %d colors %d colors-bridged %d colors-visible %d xref %d cache %d/%d/%d setup %.2fms tarjan %.2fms scc-setup %.2fms gather-xref %.2fms xref-setup %.2fms cleanup %.2fms",
+ mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_TAR_BRIDGE bridges %d objects %d opaque %d colors %d colors-bridged %d colors-visible %d xref %d cache-hit %d cache-%s %d cache-miss %d setup %.2fms tarjan %.2fms scc-setup %.2fms gather-xref %.2fms xref-setup %.2fms cleanup %.2fms",
bridge_count, object_count, ignored_objects,
color_count, colors_with_bridges_count, num_sccs, xref_count,
- cache_hits, cache_misses, cache_abstains,
+ cache_hits, (scc_precise_merge ? "abstain" : "semihit"), cache_semihits, cache_misses,
setup_time / 10000.0f,
tarjan_time / 10000.0f,
scc_setup_time / 10000.0f,
xref_setup_time / 10000.0f,
cleanup_time / 10000.0f);
- cache_hits = cache_misses = cache_abstains = 0;
+ cache_hits = cache_semihits = cache_misses = 0;
ignored_objects = 0;
}
// printf (" is visited: %d\n", (int)entry->is_visited);
}
+static void
+set_config (const SgenBridgeProcessorConfig *config)
+{
+ if (config->scc_precise_merge) {
+ hash_perturb = 0;
+ scc_precise_merge = TRUE;
+ }
+}
+
void
sgen_tarjan_bridge_init (SgenBridgeProcessor *collector)
{
collector->class_kind = class_kind;
collector->register_finalized_object = register_finalized_object;
collector->describe_pointer = describe_pointer;
- collector->enable_accounting = enable_accounting;
- // collector->set_dump_prefix = set_dump_prefix;
+ collector->set_config = set_config;
sgen_register_fixed_internal_mem_type (INTERNAL_MEM_TARJAN_OBJ_BUCKET, BUCKET_SIZE);
g_assert (sizeof (ObjectBucket) <= BUCKET_SIZE);
g_assert (sizeof (ColorBucket) <= BUCKET_SIZE);
+ g_assert (API_INDEX_BITS + INCOMING_COLORS_BITS <= 31);
bridge_processor = collector;
}
projects / mono.git / blobdiff