2 using System.Diagnostics;
4 using System.Threading.Tasks;
6 using System.Text.RegularExpressions;
7 using System.Collections.Generic;
9 namespace crashbisector
12 const int timeout = 60;
14 public string MonoPath { get; set; }
15 public string OptName { get; set; }
16 public IEnumerable<string> Args { get; set; }
19 public BisectInfo () {
23 string Run (string bisectArg) {
26 if (bisectArg == null) {
27 args = new string[] { "-v" }.Concat (args);
29 args = new string[] { bisectArg }.Concat (args);
31 var startInfo = new ProcessStartInfo {
33 Arguments = string.Join (" ", args),
34 UseShellExecute = false,
35 RedirectStandardOutput = true,
36 RedirectStandardError = true
38 startInfo.EnvironmentVariables.Add ("MONO_DEBUG", "no-gdb-backtrace");
40 using (var process = Process.Start (startInfo)) {
41 var stdoutTask = Task.Factory.StartNew (() => new StreamReader (process.StandardOutput.BaseStream).ReadToEnd (), TaskCreationOptions.LongRunning);
42 var stderrTask = Task.Factory.StartNew (() => new StreamReader (process.StandardError.BaseStream).ReadToEnd (), TaskCreationOptions.LongRunning);
44 var success = process.WaitForExit (timeout < 0 ? -1 : (Math.Min (Int32.MaxValue / 1000, timeout) * 1000));
45 if (!success || process.ExitCode != 0) {
49 var stdout = stdoutTask.Result;
55 bool RunWithMethods (IEnumerable<string> methods) {
56 var path = Path.GetTempFileName ();
57 File.WriteAllLines (path, methods);
58 var stdout = Run (String.Format ("--bisect={0}:{1}", OptName, path));
60 return stdout != null;
63 IEnumerable<int> EliminationOrder (int numChunks) {
64 var chunks = new int [numChunks];
65 for (var i = 0; i < numChunks; ++i)
67 for (var i = 0; i < numChunks; ++i) {
68 var j = rand.Next (i, numChunks);
70 chunks [i] = chunks [j];
76 bool TryEliminate (IEnumerable<string> methods, int chunkSize) {
77 var count = methods.Count ();
78 if (chunkSize < 1 || chunkSize > count)
79 throw new Exception ("I can't do math.");
81 var numChunks = (count + chunkSize - 1) / chunkSize;
82 foreach (var i in EliminationOrder (numChunks)) {
83 var firstIndex = i * chunkSize;
84 var lastPlusOneIndex = (i + 1) * chunkSize;
85 var methodsLeft = methods.Take (firstIndex).Concat (methods.Skip (lastPlusOneIndex));
88 Console.WriteLine ("Running without method at position {0}", firstIndex);
90 Console.WriteLine ("Running without methods at positions {0} to {1}", firstIndex, lastPlusOneIndex - 1);
91 var success = RunWithMethods (methodsLeft);
92 Console.WriteLine ("Crashed: {0}", !success);
95 Console.WriteLine ("Eliminating further from {0} methods.", methodsLeft.Count ());
96 return EliminationStep (methodsLeft);
103 bool EliminationStep (IEnumerable<string> methods) {
104 var count = methods.Count ();
107 Console.WriteLine ("Can't eliminate further. Methods required to crash are:\n{0}",
108 string.Join ("\n", methods));
113 var chunkSize = (int)Math.Floor (Math.Sqrt (count));
114 Console.WriteLine ("Trying eliminating chunks of {0}.", chunkSize);
115 if (TryEliminate (methods, chunkSize))
117 Console.WriteLine ("Chunks didn't succeed, eliminating individual methods.");
120 if (TryEliminate (methods, 1))
123 Console.WriteLine ("Couldn't eliminate any method. Methods required to crash are:\n{0}",
124 string.Join ("\n", methods));
128 bool BisectStep (IEnumerable<string> methods) {
129 var count = methods.Count ();
132 Console.WriteLine ("Error: No methods left - what happened?");
136 Console.WriteLine ("Found the offending method: {0}", methods.First ());
140 var half = count / 2;
141 var firstHalf = methods.Take (half);
142 var secondHalf = methods.Skip (half);
143 Console.WriteLine ("Splitting into two halves: {0} and {1} methods.", firstHalf.Count (), secondHalf.Count ());
145 Console.WriteLine ("Running first half.");
146 var firstSuccess = RunWithMethods (firstHalf);
147 Console.WriteLine ("Crashed: {0}", !firstSuccess);
150 Console.WriteLine ("Continuing with first half.");
151 return BisectStep (firstHalf);
154 Console.WriteLine ("Running second half.");
155 var secondSuccess = RunWithMethods (secondHalf);
156 Console.WriteLine ("Crashed: {0}", !secondSuccess);
158 if (!secondSuccess) {
159 Console.WriteLine ("Continuing with second half.");
160 return BisectStep (secondHalf);
163 Console.WriteLine ("Error: Both halves succeeded, can't bisect. Trying elimination.");
164 return EliminationStep (methods);
167 public bool Bisect () {
168 Console.WriteLine ("Running to gather methods.");
169 var stdout = Run (null);
170 if (stdout == null) {
171 Console.Error.WriteLine ("Error: Failed to execute without optimization.");
172 Environment.Exit (1);
175 var regex = new Regex ("converting[^\n]* method ([^\n]+)\n");
176 var matches = regex.Matches (stdout);
177 var methods = new List<string> ();
178 foreach (Match match in matches) {
179 var method = match.Groups [1].Value;
180 methods.Add (method);
183 Console.WriteLine ("Bisecting {0} methods.", methods.Count);
185 Console.WriteLine ("Running with all methods, just to make sure.");
186 var success = RunWithMethods (methods);
188 Console.WriteLine ("Error: Ran successfully with all methods optimized. Nothing to bisect.");
191 Console.WriteLine ("Crashed. Bisecting.");
192 return BisectStep (methods);
198 static void UsageAndExit (int exitCode) {
199 Console.Error.WriteLine ("Usage: crash-bisector.exe --mono MONO-EXECUTABLE --opt OPTION-NAME -- MONO-ARG ...");
200 Environment.Exit (exitCode);
203 public static void Main (string[] args)
205 string monoPath = null;
206 string optName = null;
209 while (argIndex < args.Length) {
210 if (args [argIndex] == "--mono") {
211 monoPath = args [argIndex + 1];
213 } else if (args [argIndex] == "--opt") {
214 optName = args [argIndex + 1];
216 } else if (args [argIndex] == "--help") {
218 } else if (args [argIndex] == "--") {
226 if (monoPath == null || optName == null || argIndex == args.Length)
229 var bisectInfo = new BisectInfo {
232 Args = args.Skip (argIndex)
234 var success = bisectInfo.Bisect ();
235 Environment.Exit (success ? 0 : 1);