[2020-02] Avoid following invalid pointers in mono_w32process_get_modules on Darwin...

[mono-project.git] / mono / tests / sgen-bridge-pathologies.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Threading;

public class Bridge {
        public int __test;
        public List<object> Links = new List<object> ();
        public static int fin_count;
        ~Bridge () {
                ++fin_count;
                Links = null;
        }
}

public class NonBridge
{
        public object Link;
}

class Driver {
        const int OBJ_COUNT = 200 * 1000;
        const int LINK_COUNT = 2;
        const int EXTRAS_COUNT = 0;
        const double survival_rate = 0.6;

        /*
         * Pathological case for the original old algorithm.  Goes
         * away when merging is replaced by appending with flag
         * checking.
         */
        static void SetupLinks () {
                var list = new List<Bridge> ();
                for (int i = 0; i < OBJ_COUNT; ++i) {
                        var bridge = new Bridge ();
                        list.Add (bridge);
                }

                var r = new Random (100);
                for (int i = 0; i < OBJ_COUNT; ++i) {
                        var n = list [i];
                        for (int j = 0; j < LINK_COUNT; ++j)
                                n.Links.Add (list [r.Next (OBJ_COUNT)]);
                        for (int j = 0; j < EXTRAS_COUNT; ++j)
                                n.Links.Add (j);
                        if (r.NextDouble () <= survival_rate)
                                n.__test = 1;
                }
                Console.WriteLine ("-setup done-");
        }

        const int LIST_LENGTH = 20000;
        const int FAN_OUT = 20000;

        /*
         * Pathological case for the new algorithm.  Goes away with
         * the single-node elimination optimization, but will still
         * persist if modified by using a ladder instead of the single
         * list.
         */
        static void SetupLinkedFan ()
        {
                var head = new Bridge ();
                var tail = new NonBridge ();
                head.Links.Add (tail);
                for (int i = 0; i < LIST_LENGTH; ++i)
                {
                        var obj = new NonBridge ();
                        tail.Link = obj;
                        tail = obj;
                }
                var list = new List<Bridge> ();
                tail.Link = list;
                for (int i = 0; i < FAN_OUT; ++i)
                        list.Add (new Bridge ());
                Console.WriteLine ("-linked fan done-");
        }

        /*
         * Pathological case for the improved old algorithm.  Goes
         * away with copy-on-write DynArrays, but will still persist
         * if modified by using a ladder instead of the single list.
         */
        static void SetupInverseFan ()
        {
                var tail = new Bridge ();
                object list = tail;
                for (int i = 0; i < LIST_LENGTH; ++i)
                {
                        var obj = new NonBridge ();
                        obj.Link = list;
                        list = obj;
                }
                var heads = new Bridge [FAN_OUT];
                for (int i = 0; i < FAN_OUT; ++i)
                {
                        var obj = new Bridge ();
                        obj.Links.Add (list);
                        heads [i] = obj;
                }
                Console.WriteLine ("-inverse fan done-");
        }

        /*
         * Pathological case for the bridge in general.  We generate
         * 2*FAN_OUT bridge objects here, but the output of the bridge
         * is a graph with FAN_OUT^2 edges.
         */
        static void SetupDoubleFan ()
        {
                var heads = new Bridge [FAN_OUT];
                for (int i = 0; i < FAN_OUT; ++i)
                        heads [i] = new Bridge ();

                // We make five identical multiplexers to verify Tarjan-bridge can merge them together correctly.
                var MULTIPLEXER_COUNT = 5;
                Bridge[] multiplexer0 = null;
                for(int m = 0; m < MULTIPLEXER_COUNT; m++) {
                        var multiplexer = new Bridge [FAN_OUT];
                        if (m == 0) {
                                multiplexer0 = multiplexer;
                                for (int i = 0; i < FAN_OUT; ++i)
                                {
                                        heads [i].Links.Add (multiplexer);
                                        multiplexer [i] = new Bridge ();
                                }
                        } else {
                                for (int i = 0; i < FAN_OUT; ++i)
                                {
                                        heads [i].Links.Add (multiplexer);
                                        multiplexer [i] = multiplexer0 [i];
                                }
                        }
                }

                Console.WriteLine ("-double fan x5 done-");
        }

        /*
         * Not necessarily a pathology, but a special case of where we
         * generate lots of "dead" SCCs.  A non-bridge object that
         * can't reach a bridge object can safely be removed from the
         * graph.  In this special case it's a linked list hanging off
         * a bridge object.  We can handle this by "forwarding" edges
         * going to non-bridge nodes that have only a single outgoing
         * edge.  That collapses the whole list into a single node.
         * We could remove that node, too, by removing non-bridge
         * nodes with no outgoing edges.
         */
        static void SetupDeadList ()
        {
                var head = new Bridge ();
                var tail = new NonBridge ();
                head.Links.Add (tail);
                for (int i = 0; i < LIST_LENGTH; ++i)
                {
                        var obj = new NonBridge ();
                        tail.Link = obj;
                        tail = obj;
                }
        }

        /*
         * Triggered a bug in the forwarding mechanic.
         */
        static void SetupSelfLinks ()
        {
                var head = new Bridge ();
                var tail = new NonBridge ();
                head.Links.Add (tail);
                tail.Link = tail;
        }

        const int L0_COUNT = 100000;
        const int L1_COUNT = 100000;
        const int EXTRA_LEVELS = 4;

        /*
        Set a complex graph from one bridge to a couple.
        The graph is designed to expose naive coloring on
        tarjan and SCC explosion on classic.
        */
        static void Spider () {
                Bridge a = new Bridge ();
                Bridge b = new Bridge ();

                var l1 = new List<object> ();
                for (int i = 0; i < L0_COUNT; ++i) {
                        var l0 = new List<object> ();
                        l0.Add (a);
                        l0.Add (b);
                        l1.Add (l0);
                }
                var last_level = l1;
                for (int l = 0; l < EXTRA_LEVELS; ++l) {
                        int j = 0;
                        var l2 = new List<object> ();
                        for (int i = 0; i < L1_COUNT; ++i) {
                                var tmp = new List<object> ();
                                tmp.Add (last_level [j++ % last_level.Count]);
                                tmp.Add (last_level [j++ % last_level.Count]);
                                l2.Add (tmp);
                        }
                        last_level = l2;
                }
                Bridge c = new Bridge ();
                c.Links.Add (last_level);
        }

        static void RunTest (ThreadStart setup)
        {
                var t = new Thread (setup);
                t.Start ();
                t.Join ();

                for (int i = 0; i < 5; ++i) {
                        Console.WriteLine("-GC {0}/5-", i);
                        GC.Collect ();
                        GC.WaitForPendingFinalizers ();
                }

                Console.WriteLine ("-GCs done- {0}", Bridge.fin_count);
        }

        static int Main ()
        {
                RunTest (SetupLinks);
                RunTest (SetupLinkedFan);
                RunTest (SetupInverseFan);
                RunTest (SetupDoubleFan);
                RunTest (SetupDeadList);
                RunTest (SetupSelfLinks);
                RunTest (Spider);

                for (int i = 0; i < 0; ++i) {
                        GC.Collect ();
                        GC.WaitForPendingFinalizers ();
                        Console.WriteLine ("-Cleanup GC- {0}", Bridge.fin_count);
                }
                return 0;
        }
}