1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
5 // Basic test for dependent handles.
7 // Note that though this test uses ConditionalWeakTable it is not a test for that class. This is a stress
8 // test that utilizes ConditionalWeakTable features, which would be used heavily if Dynamic Language Runtime
11 // Basic test overview:
12 // * Allocate an array of objects (we call these Nodes) with finalizers.
13 // * Create a set of dependent handles that reference these objects as primary and secondary members (this is
14 // where ConditionalWeakTable comes in, adding a key/value pair to such a table creates a dependent handle
15 // with the primary set to the key and the secondary set to the value).
16 // * Null out selected objects from the array in various patterns. This removes the only normal strong root
17 // for such objects (leaving only the dependent handles to provide additional roots).
18 // * Perform a full GC and wait for it and finalization to complete. Each object which is collected will use
19 // its finalizer to inform the test that it's been disposed of.
20 // * Run our own reachability analysis (a simple mark array approach) to build a picture of which objects in
21 // the array should have been collected or not.
22 // * Validate that the actual set of live objects matches our computed live set exactly.
24 // Test variations include the number of objects allocated, the relationship between the primary and secondary
25 // in each handle we allocate and the pattern with which we null out object references in the array.
27 // Additionally this test stresses substantially more complex code paths in the GC if server mode is enabled.
28 // This can be achieved by setting the environment variable COMPlus_BuildFlavor=svr prior to executing the
31 // Note that we don't go to any lengths to ensure that dependent handle ownership is spread over multiple cpus
32 // on a server GC/MP test run. For large node counts (e.g. 100000) this happens naturally since initialization
33 // takes a while with multiple thread/CPU switches involved. We could be more explicit here (allocate handles
34 // using CPU affinitized threads) but if we do that we'd probably better look into different patterns of node
35 // ownership to avoid unintentionally restricting our test coverage.
37 // Another area into which we could look deeper is trying to force mark stack overflows in the GC (presumably
38 // by allocating complex object graphs with lots of interconnections, though I don't the specifics of the best
39 // way to force this). Causing mark stack overflows should open up a class of bug the old dependent handle
40 // implementation was subject to without requiring server GC mode or multiple CPUs.
44 using System.Runtime.CompilerServices;
46 // How we assign nodes to dependent handles.
49 Unconnected, // The primary and secondary handles are assigned completely disjoint objects
50 ForwardLinked, // The primary of each handle is the secondary of the previous handle
51 BackwardLinked, // The primary of each handle is the secondary of the next handle
52 Random // The primaries are each object in sequence, the secondaries are selected randomly from
56 // How we choose object references in the array to null out (and thus potentially become collected).
59 None, // Don't null out any (nothing should be collected)
60 All, // Null them all out (any remaining live objects should be collected)
61 Alternate, // Null out every second reference
62 Random // Null out each entry with a 50% probability
65 // We report errors by throwing an exception. Define our own Exception subclass so we can identify these
66 // errors unambiguously.
67 class TestException : Exception
69 // We just supply a simple message string on error.
70 public TestException(string message) : base(message)
75 // Class encapsulating test runs over a set of objects/handles allocated with the specified TableStyle.
78 // Create a new test with the given table style and object count.
79 public TestSet(TableStyle ts, int count)
81 // Use one random number generator for the life of the test. Could support explicit seeds for
82 // reproducible tests here.
85 // Remember our parameters.
90 m_nodes = new Node[count]; // The array of objects
91 m_collected = new bool[count]; // Records whether each object has been collected (entries are set by
92 // the finalizer on Node)
93 m_marks = new bool[count]; // Array used during individual test runs to calculate whether each
94 // object should still be alive (allocated once here to avoid
95 // injecting further garbage collections at run time)
97 // Allocate each object (Node). Each knows its own unique ID (the index into the node array) and has a
98 // back pointer to this test object (so it can phone home to report its own collection at finalization
100 for (int i = 0; i < count; i++)
101 m_nodes[i] = new Node(this, i);
103 // Determine how many handles we need to allocate given the number of nodes. This varies based on the
107 case TableStyle.Unconnected:
108 // Primaries and secondaries are completely different objects so we split our nodes in half and
109 // allocate that many handles.
110 m_handleCount = count / 2;
113 case TableStyle.ForwardLinked:
114 // Nodes are primaries in one handle and secondary in another except one that falls off the end.
115 // So we have as many handles as nodes - 1.
116 m_handleCount = count - 1;
119 case TableStyle.BackwardLinked:
120 // Nodes are primaries in one handle and secondary in another except one that falls off the end.
121 // So we have as many handles as nodes - 1.
122 m_handleCount = count - 1;
125 case TableStyle.Random:
126 // Each node is a primary in some handle (secondaries are selected from amongst all the same nodes
127 // randomly). So we have as many nodes as handles.
128 m_handleCount = count;
132 // Allocate an array of HandleSpecs. These aren't the real handles, just structures that allow us
133 // remember what's in each handle (in terms of the node index number for the primary and secondary).
134 // We need to track this information separately because we can't access the real handles directly
135 // (ConditionalWeakTable hides them) and we need to recall exactly what the primary and secondary of
136 // each handle is so we can compute our own notion of object liveness later.
137 m_handles = new HandleSpec[m_handleCount];
139 // Initialize the handle specs to assign objects to handles based on the table style.
140 for (int i = 0; i < m_handleCount; i++)
142 int primary = -1, secondary = -1;
146 case TableStyle.Unconnected:
147 // Assign adjacent nodes to the primary and secondary of each handle.
149 secondary = (i * 2) + 1;
152 case TableStyle.ForwardLinked:
153 // Primary of each handle is the secondary of the last handle.
158 case TableStyle.BackwardLinked:
159 // Primary of each handle is the secondary of the next handle.
164 case TableStyle.Random:
165 // Primary is each node in sequence, secondary is any of the nodes randomly.
167 secondary = m_rng.Next(m_handleCount);
171 m_handles[i].Set(primary, secondary);
174 // Allocate a ConditionalWeakTable mapping Node keys to Node values.
175 m_table = new ConditionalWeakTable<Node, Node>();
177 // Using our handle specs computed above add each primary/secondary node pair to the
178 // ConditionalWeakTable in turn. This causes the ConditionalWeakTable to allocate a dependent handle
179 // for each entry with the primary and secondary objects we specified as keys and values (note that
180 // this scheme prevents us from creating multiple handles with the same primary though if this is
181 // desired we could achieve it by allocating multiple ConditionalWeakTables).
182 for (int i = 0; i < m_handleCount; i++)
183 m_table.Add(m_nodes[m_handles[i].m_primary], m_nodes[m_handles[i].m_secondary]);
186 // Call this method to indicate a test error with a given message. This will terminate the test
188 void Error(string message)
190 throw new TestException(message);
193 // Run a single test pass on the node set. Null out node references according to the given CollectStyle,
194 // run a garbage collection and then verify that each node is either live or dead as we predict. Take care
195 // of the order in which test runs are made against a single TestSet: e.g. running a CollectStyle.All will
196 // collect all nodes, rendering further runs relatively uninteresting.
197 public void Run(CollectStyle cs)
199 Console.WriteLine("Running test TS:{0} CS:{1} {2} entries...",
200 Enum.GetName(typeof(TableStyle), m_style),
201 Enum.GetName(typeof(CollectStyle), cs),
204 // Iterate over the array of nodes deciding for each whether to sever the reference (null out the
206 for (int i = 0; i < m_count; i++)
211 case CollectStyle.All:
212 // Sever all references.
216 case CollectStyle.None:
217 // Don't sever any references.
220 case CollectStyle.Alternate:
221 // Sever every second reference (starting with the first).
226 case CollectStyle.Random:
227 // Sever any reference with a 50% probability.
228 if (m_rng.Next(100) > 50)
237 // Initialize a full GC and wait for all finalizers to complete (so we get an accurate picture of
238 // which nodes were collected).
240 GC.WaitForPendingFinalizers();
242 // Calculate our own view of which nodes should be alive or dead. Use a simple mark array for this.
243 // Once the algorithm is complete a true value at a given index in the array indicates a node that
244 // should still be alive, otherwise the node should have been collected.
246 // Initialize the mark array. Set true for nodes we still have a strong reference to from the array
247 // (these should definitely not have been collected yet). Set false for the other nodes (we assume
248 // they must have been collected until we prove otherwise).
249 for (int i = 0; i < m_count; i++)
250 m_marks[i] = m_nodes[i] != null;
252 // Perform multiple passes over the handles we allocated (or our recorded version of the handles at
253 // least). If we find a handle with a marked (live) primary where the secondary is not yet marked then
254 // go ahead and mark that secondary (dependent handles are defined to do this: primaries act as if
255 // they have a strong reference to the secondary up until the point they are collected). Repeat this
256 // until we manage a scan over the entire table without marking any additional nodes as live. At this
257 // point the marks array should reflect which objects are still live.
260 // Assume we're not going any further nodes to mark as live.
263 // Look at each handle in turn.
264 for (int i = 0; i < m_handleCount; i++)
266 if (m_marks[m_handles[i].m_primary])
269 if (!m_marks[m_handles[i].m_secondary])
271 // Secondary wasn't marked as live yet. Do so and remember that we marked at least
272 // node as live this pass (so we need to loop again since this secondary could be the
273 // same as a primary earlier in the table).
274 m_marks[m_handles[i].m_secondary] = true;
279 // Terminate the loop if we scanned the entire table without marking any additional nodes as live
280 // (since additional scans can't make any difference).
285 // Validate our view of node liveness (m_marks) correspond to reality (m_nodes and m_collected).
286 for (int i = 0; i < m_count; i++)
288 // Catch nodes which still have strong references but have collected anyway. This is stricly a
289 // subset of the next test but it would be a very interesting bug to call out.
290 if (m_nodes[i] != null && m_collected[i])
291 Error(String.Format("Node {0} was collected while it still had a strong root", i));
293 // Catch nodes which we compute as alive but have been collected.
294 if (m_marks[i] && m_collected[i])
295 Error(String.Format("Node {0} was collected while it was still reachable", i));
297 // Catch nodes which we compute as dead but haven't been collected.
298 if (!m_marks[i] && !m_collected[i])
299 Error(String.Format("Node {0} wasn't collected even though it was unreachable", i));
303 // Method called by nodes when they're finalized (i.e. the node has been collected).
304 public void Collected(int id)
306 // Catch nodes which are collected twice.
308 Error(String.Format("Node {0} collected twice", id));
310 m_collected[id] = true;
313 // Structure used to record the primary and secondary nodes in every dependent handle we allocated. Nodes
314 // are identified by ID (their index into the node array).
317 public int m_primary;
318 public int m_secondary;
320 public void Set(int primary, int secondary)
323 m_secondary = secondary;
327 int m_count; // Count of nodes in array
328 TableStyle m_style; // Style of handle creation
329 Node[] m_nodes; // Array of nodes
330 bool[] m_collected; // Array indicating which nodes have been collected
331 bool[] m_marks; // Array indicating which nodes should be live
332 ConditionalWeakTable<Node, Node> m_table; // Table that creates and holds our dependent handles
333 int m_handleCount; // Number of handles we create
334 HandleSpec[] m_handles; // Array of descriptions of each handle
335 Random m_rng; // Random number generator
338 // The type of object we reference from our dependent handles. Doesn't do much except report its own garbage
339 // collection to the owning TestSet.
342 // Allocate a node and remember our owner (TestSet) and ID (index into node array).
343 public Node(TestSet owner, int id)
349 // On finalization report our collection to the owner TestSet.
352 m_owner.Collected(m_id);
355 TestSet m_owner; // TestSet which created us
356 int m_id; // Our index into above TestSet's node array
359 // The test class itself.
363 public static int Main()
365 // The actual test runs are controlled from RunTest. True is returned if all succeeded, false
367 if (new DhTest1().RunTest())
369 Console.WriteLine("Test PASS");
374 Console.WriteLine("Test FAIL");
379 // Run a series of tests with different table and collection styles.
382 // Number of nodes we'll allocate in each run (we could take this as an argument instead).
383 int numNodes = 10000;
385 // Run everything under an exception handler since test errors are reported as exceptions.
388 // Run a pass with each table style. For each style run through the collection styles in the order
389 // None, Alternate, Random and All. This sequence is carefully selected to remove progressively
390 // more nodes from the array (since, within a given TestSet instance, once a node has actually
391 // been collected it won't be resurrected for future runs).
393 TestSet ts1 = new TestSet(TableStyle.Unconnected, numNodes);
394 ts1.Run(CollectStyle.None);
395 ts1.Run(CollectStyle.Alternate);
396 ts1.Run(CollectStyle.Random);
397 ts1.Run(CollectStyle.All);
399 TestSet ts2 = new TestSet(TableStyle.ForwardLinked, numNodes);
400 ts2.Run(CollectStyle.None);
401 ts2.Run(CollectStyle.Alternate);
402 ts2.Run(CollectStyle.Random);
403 ts2.Run(CollectStyle.All);
405 TestSet ts3 = new TestSet(TableStyle.BackwardLinked, numNodes);
406 ts3.Run(CollectStyle.None);
407 ts3.Run(CollectStyle.Alternate);
408 ts3.Run(CollectStyle.Random);
409 ts3.Run(CollectStyle.All);
411 TestSet ts4 = new TestSet(TableStyle.Random, numNodes);
412 ts4.Run(CollectStyle.None);
413 ts4.Run(CollectStyle.Alternate);
414 ts4.Run(CollectStyle.Random);
415 ts4.Run(CollectStyle.All);
417 catch (TestException te)
419 // "Expected" errors.
420 Console.WriteLine("TestError: {0}", te.Message);
425 // Totally unexpected errors (probably shouldn't see these unless there's a test bug).
426 Console.WriteLine("Unexpected exception: {0}", e.GetType().Name);
430 // If we get as far as here the test succeeded.