From c6b3e5d0df205fd77bb1a547633b23db22f08b18 Mon Sep 17 00:00:00 2001 From: Vlad Brezae Date: Tue, 7 Jan 2020 16:31:49 +0200 Subject: [PATCH] [sgen] Fix xref computation with tarjan bridge (mono/mono#18239) * [sgen] Include also derived classes as bridges When using `MONO_GC_DEBUG=bridge=` debug option * [sgen] Fix xref computation with tarjan bridge Between C# and java (on android) there are objects that live on both worlds. This means that there exists a C# object with a corresponding java object. The relationship between them is strong, meaning if C# object is alive then java object must stay alive, and vice-versa. We keep java bridge objects always alive through a GCHandle (on the java gc). When doing a C# collection we select all bridge objects that appear to be dead on the C# side. These objects are candidates for collection, assuming the java side has nothing against it. Before triggering a collection on the java side (following the mono gc) we switch all the strong gchandles to the java objects to be weak (for these objects that are candidate to be collected) and we recreate the reference graph from the C# side to the java side (if C# Bridge1 can reference C# Bridge2 then, on the java side, we add a reference from Java Bridge1 to Java Bridge2; this is done by adding to an array of references inside Java Bridge1). In order to minimize the amount of work that needs to be done on the java side, we compute the minimal amount of references that need to be added, by computing the strongly connected components of the object graph. An optimized way to construct the SCCs and the xrefs is by using the tarjan algorithm (https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm). Our algorithm is non recursive (scan_stack emulates the recursive order of traversal in a dfs algorithm, while loop_stack is the stack used by the algorithm). A color represents an SCC. We have some optimizations in place where we might merge colors if they don't contain bridges, since the client only cares about SCCs containing bridge objects and the links between them. color_merge_array is used to keep track of all neighbors of a node until we are creating the scc for that node. It is populated when scanning all the refs inside an object (compute_low). All the colors in the color_merge_array will be cross references with that scc. Before this commit we were only clearing the color_merge_array when creating an SCC. This is problematic because we could end up with xrefs inside of an SCC that belong to another SCC. Consider the simple graph of nodes 0,1,2,3 where 0 <=> 2, 0->1, 2->3. Assume we start scanning with node 0. When creating the SCC for node 3 the followed path is 0 -> 2 -> 3, while the loop stack will contain (0,1,2,3). After creating SCC for node 3, we will finish scanning node 2 which would detect the xref to Bridge3, which would have been added to the color_merge_array. Because node 2 is not the root of the SCC it belongs to (its lowlink points towards node 0 which has a lower index), we are not creating an SCC with it, and the link to node 3 remains in color_merge_array. Because the next node from the scan_stack is node 1, which is also the root of the SCC that it belongs to, we will create an SCC for it and wrongly add the node 3 reference from color_merge_array to it. In order to fix this issue, we will always clear the color_merge_array once we finished scanning the xrefs for a node. If the node in question is not the root of an scc, then we will remember them as xrefs pointing out from this object. When we finally reach node 0 (which will be the root of the SCC containing nodes 0 and 2), we will then know that all xrefs for this color are the union of the xrefs of all objects belonging to this color (which represents the objects that we are popping from the loop_stack until we encounter the root node). Even though this change adds required bookeeping for xrefs, I didn't notice any change in performance on the bridge tests that we have in mono/tests. * [sgen] Some logging improvements in tarjan bridge * [sgen] Disable optimization when comparing bridge outputs When this optimization is enabled, the tarjan bridge will create more SCCs in order to reduce amount of xrefs in the graph. This would render the `bridge-compare-to` debug flag unusable with tarjan bridge. Commit migrated from https://github.com/mono/mono/commit/376c46bcf3bc101fba85a402914d60c6bda70e75 --- src/mono/mono/metadata/sgen-bridge-internals.h | 3 + src/mono/mono/metadata/sgen-bridge.c | 6 +- src/mono/mono/metadata/sgen-tarjan-bridge.c | 102 ++++++++++++++++--------- 3 files changed, 75 insertions(+), 36 deletions(-) diff --git a/src/mono/mono/metadata/sgen-bridge-internals.h b/src/mono/mono/metadata/sgen-bridge-internals.h index e66455b..763c385 100644 --- a/src/mono/mono/metadata/sgen-bridge-internals.h +++ b/src/mono/mono/metadata/sgen-bridge-internals.h @@ -42,6 +42,9 @@ typedef struct { char *dump_prefix; gboolean accounting; gboolean scc_precise_merge; // Used by Tarjan + // Disables reporting SCCs with no bridge objects on tarjan. Used when comparing outputs + // of two bridge processors, in order to keep consistency. + gboolean disable_non_bridge_scc; } SgenBridgeProcessorConfig; typedef struct { diff --git a/src/mono/mono/metadata/sgen-bridge.c b/src/mono/mono/metadata/sgen-bridge.c index 558a073..2b4c662 100644 --- a/src/mono/mono/metadata/sgen-bridge.c +++ b/src/mono/mono/metadata/sgen-bridge.c @@ -319,7 +319,7 @@ dump_processor_state (SgenBridgeProcessor *p) printf ("\tSCC %d:", i); for (j = 0; j < scc->num_objs; ++j) { MonoObject *obj = scc->objs [j]; - printf (" %p", obj); + printf (" %p(%s)", obj, SGEN_LOAD_VTABLE (obj)->klass->name); } printf ("\n"); } @@ -516,7 +516,8 @@ static const char *bridge_class; static MonoGCBridgeObjectKind bridge_test_bridge_class_kind (MonoClass *klass) { - if (!strcmp (bridge_class, m_class_get_name (klass))) + if (!strcmp (bridge_class, m_class_get_name (klass)) || + (m_class_get_parent (klass) && !strcmp (bridge_class, m_class_get_name (m_class_get_parent (klass))))) return GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS; return GC_BRIDGE_TRANSPARENT_CLASS; } @@ -708,6 +709,7 @@ sgen_bridge_handle_gc_debug (const char *opt) if (selection != BRIDGE_PROCESSOR_INVALID) { // Compare processor doesn't get config init_bridge_processor (&compare_to_bridge_processor, selection); + bridge_processor_config.disable_non_bridge_scc = TRUE; } else { g_warning ("Invalid bridge implementation to compare against - ignoring."); } diff --git a/src/mono/mono/metadata/sgen-tarjan-bridge.c b/src/mono/mono/metadata/sgen-tarjan-bridge.c index 36cfbc1..2d26e68 100644 --- a/src/mono/mono/metadata/sgen-tarjan-bridge.c +++ b/src/mono/mono/metadata/sgen-tarjan-bridge.c @@ -138,6 +138,10 @@ typedef struct _ScanData { mword lock_word; ColorData *color; + // If this object isn't the scc root, we still need to store the xref colors on it, after computing + // low index, so we can add them to the scc that this object is part of. + DynPtrArray xrefs; + // Tarjan algorithm index (order visited) int index; // Tarjan index of lowest-index object known reachable from here @@ -150,11 +154,16 @@ typedef struct _ScanData { unsigned obj_state : 2; } ScanData; +// If true, disable an optimization where sometimes SCC nodes don't contain any bridge objects, in order to reduce total xrefs. +static gboolean disable_non_bridge_scc; + /* Should color be made visible to client even though it has no bridges? * True if we predict the number of reduced edges to be enough to justify the extra node. */ static gboolean bridgeless_color_is_heavy (ColorData *data) { + if (disable_non_bridge_scc) + return FALSE; int fanin = data->incoming_colors; int fanout = dyn_array_ptr_size (&data->other_colors); return fanin > HEAVY_REFS_MIN && fanout > HEAVY_REFS_MIN @@ -553,6 +562,18 @@ find_in_cache (int *insert_index) return NULL; } +// Populate other_colors for a give color (other_colors represent the xrefs for this color) +static void +add_other_colors (ColorData *color, DynPtrArray *other_colors) +{ + for (int i = 0; i < dyn_array_ptr_size (other_colors); ++i) { + ColorData *points_to = (ColorData *)dyn_array_ptr_get (other_colors, i); + dyn_array_ptr_add (&color->other_colors, points_to); + // Inform targets + points_to->incoming_colors = MIN (points_to->incoming_colors + 1, INCOMING_COLORS_MAX); + } +} + // A color is needed for an SCC. If the SCC has bridges, the color MUST be newly allocated. // If the SCC lacks bridges, the allocator MAY use the cache to merge it with an existing one. static ColorData* @@ -569,13 +590,8 @@ new_color (gboolean has_bridges) cd = alloc_color_data (); cd->api_index = -1; - dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array); - // Inform targets - for (int i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i) { - ColorData *points_to = (ColorData *)dyn_array_ptr_get (&color_merge_array, i); - points_to->incoming_colors = MIN (points_to->incoming_colors + 1, INCOMING_COLORS_MAX); - } + add_other_colors (cd, &color_merge_array); /* if cacheSlot >= 0, it means we prepared a given slot to receive the new color */ if (cacheSlot >= 0) @@ -683,7 +699,7 @@ compute_low_index (ScanData *data, GCObject *obj) other = find_data (obj); #if DUMP_GRAPH - printf ("\tcompute low %p ->%p (%s) %p (%d / %d)\n", data->obj, obj, safe_name_bridge (obj), other, other ? other->index : -2, other ? other->low_index : -2); + printf ("\tcompute low %p ->%p (%s) %p (%d / %d, color %p)\n", data->obj, obj, safe_name_bridge (obj), other, other ? other->index : -2, other ? other->low_index : -2, other->color); #endif if (!other) return; @@ -698,8 +714,15 @@ compute_low_index (ScanData *data, GCObject *obj) return; cd = other->color; + + // The scc for the referenced object was already created, meaning this is an xref. + // Add it to the color merge array so we can handle it later when creating the scc + // for the current object (data) if (!cd->visited) { color_merge_array_hash += mix_hash ((uintptr_t) other->color); +#if DUMP_GRAPH + printf ("\t\tadd color %p to color_merge_array\n", other->color); +#endif dyn_array_ptr_add (&color_merge_array, other->color); cd->visited = TRUE; } @@ -760,14 +783,15 @@ create_scc (ScanData *data) break; } + if (found_bridge) { + color_data = new_color (TRUE); + ++num_colors_with_bridges; + } else { + color_data = reduce_color (); + } #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 (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: "); + printf ("|SCC %p rooted in %s (%p) has bridge %d\n", color_data, safe_name_bridge (data->obj), data->obj, found_bridge); + printf ("\tloop stack: "); 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); @@ -775,13 +799,6 @@ create_scc (ScanData *data) printf ("\n"); #endif - if (found_bridge) { - color_data = new_color (TRUE); - ++num_colors_with_bridges; - } else { - color_data = reduce_color (); - } - while (dyn_array_ptr_size (&loop_stack) > 0) { ScanData *other = (ScanData *)dyn_array_ptr_pop (&loop_stack); @@ -803,6 +820,12 @@ create_scc (ScanData *data) if (other->is_bridge) dyn_array_ptr_add (&color_data->bridges, other->obj); + // Maybe we should make sure we are not adding duplicates here. It is not really a problem + // since we will get rid of duplicates before submitting the SCCs to the client in gather_xrefs + if (color_data) + add_other_colors (color_data, &other->xrefs); + dyn_array_ptr_uninit (&other->xrefs); + if (other == data) { found = TRUE; break; @@ -810,13 +833,12 @@ create_scc (ScanData *data) } g_assert (found); - for (i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i) { - ColorData *cd = (ColorData *)dyn_array_ptr_get (&color_merge_array, i); - g_assert (cd->visited); - cd->visited = FALSE; - } - color_merge_array_empty (); - found_bridge = FALSE; +#if DUMP_GRAPH + printf ("\tpoints-to-colors: "); + for (int i = 0; i < dyn_array_ptr_size (&color_data->other_colors); i++) + printf ("%p ", dyn_array_ptr_get (&color_data->other_colors, i)); + printf ("\n"); +#endif } static void @@ -840,8 +862,8 @@ dfs (void) * We start scanning from A and push C before B. So, after the first iteration, the scan stack will have: A C B. * We then visit B, which will find C in its initial state and push again. * Finally after finish with C and B, the stack will be left with "A C" and at this point C should be ignored. - * - * The above explains FINISHED_ON_STACK, to explain FINISHED_OFF_STACK, consider if the root was D, which pointed + * + * The above explains FINISHED_ON_STACK, to explain FINISHED_OFF_STACK, consider if the root was D, which pointed * to A and C. A is processed first, leaving C on stack after that in the mentioned state. */ if (data->state == FINISHED_ON_STACK || data->state == FINISHED_OFF_STACK) @@ -856,9 +878,6 @@ dfs (void) dyn_array_ptr_push (&scan_stack, data); dyn_array_ptr_push (&loop_stack, data); -#if DUMP_GRAPH - printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->color); -#endif /*push all refs */ push_all (data); } else { @@ -876,8 +895,21 @@ dfs (void) printf ("-finished %s (%p) index %d low-index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->low_index, data->color); #endif //SCC root - if (data->index == data->low_index) + if (data->index == data->low_index) { create_scc (data); + } else { + // We need to clear colo_merge_array from all xrefs. We flush them to the current color + // and will add them to the scc when we reach the root of the scc. + g_assert (dyn_array_ptr_size (&data->xrefs) == 0); + dyn_array_ptr_set_all (&data->xrefs, &color_merge_array); + } + // We populated color_merge_array while scanning the object with each neighbor color. Clear it now + for (int i = 0; i < dyn_array_ptr_size (&color_merge_array); i++) { + ColorData *cd = (ColorData *)dyn_array_ptr_get (&color_merge_array, i); + g_assert (cd->visited); + cd->visited = FALSE; + } + color_merge_array_empty (); } } } @@ -1213,6 +1245,8 @@ set_config (const SgenBridgeProcessorConfig *config) hash_perturb = 0; scc_precise_merge = TRUE; } + if (config->disable_non_bridge_scc) + disable_non_bridge_scc = TRUE; } void -- 2.7.4