tools/crash-bisector/Program.cs

   1 using System;
   2 using System.Diagnostics;
   3 using System.Linq;
   4 using System.Threading.Tasks;
   5 using System.IO;
   6 using System.Text.RegularExpressions;
   7 using System.Collections.Generic;
   8
   9 namespace crashbisector
  10 {
  11         class BisectInfo {
  12                 const int timeout = 60;
  13
  14                 public string MonoPath { get; set; }
  15                 public string OptName { get; set; }
  16                 public IEnumerable<string> Args { get; set; }
  17                 Random rand;
  18
  19                 public BisectInfo () {
  20                         rand = new Random ();
  21                 }
  22
  23                 string Run (string bisectArg) {
  24                         var args = Args;
  25
  26                         if (bisectArg == null) {
  27                                 args = new string[] { "-v" }.Concat (args);
  28                         } else {
  29                                 args = new string[] { bisectArg }.Concat (args);
  30                         }
  31                         var startInfo = new ProcessStartInfo {
  32                                 FileName = MonoPath,
  33                                 Arguments = string.Join (" ", args),
  34                                 UseShellExecute = false,
  35                                 RedirectStandardOutput = true,
  36                                 RedirectStandardError = true
  37                         };
  38                         startInfo.EnvironmentVariables.Add ("MONO_DEBUG", "no-gdb-backtrace");
  39
  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);
  43
  44                                 var success = process.WaitForExit (timeout < 0 ? -1 : (Math.Min (Int32.MaxValue / 1000, timeout) * 1000));
  45                                 if (!success || process.ExitCode != 0) {
  46                                         return null;
  47                                 }
  48
  49                                 var stdout = stdoutTask.Result;
  50
  51                                 return stdout;
  52                         }
  53                 }
  54
  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));
  59                         File.Delete (path);
  60                         return stdout != null;
  61                 }
  62
  63                 IEnumerable<int> EliminationOrder (int numChunks) {
  64                         var chunks = new int [numChunks];
  65                         for (var i = 0; i < numChunks; ++i)
  66                                 chunks [i] = i;
  67                         for (var i = 0; i < numChunks; ++i) {
  68                                 var j = rand.Next (i, numChunks);
  69                                 var tmp = chunks [i];
  70                                 chunks [i] = chunks [j];
  71                                 chunks [j] = tmp;
  72                         }
  73                         return chunks;
  74                 }
  75
  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.");
  80
  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));
  86
  87                                 if (chunkSize == 1)
  88                                         Console.WriteLine ("Running without method at position {0}", firstIndex);
  89                                 else
  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);
  93
  94                                 if (!success) {
  95                                         Console.WriteLine ("Eliminating further from {0} methods.", methodsLeft.Count ());
  96                                         return EliminationStep (methodsLeft);
  97                                 }
  98                         }
  99
 100                         return false;
 101                 }
 102
 103                 bool EliminationStep (IEnumerable<string> methods) {
 104                         var count = methods.Count ();
 105
 106                         if (count < 2) {
 107                                 Console.WriteLine ("Can't eliminate further.  Methods required to crash are:\n{0}",
 108                                         string.Join ("\n", methods));
 109                                 return true;
 110                         }
 111
 112                         if (count >= 9) {
 113                                 var chunkSize = (int)Math.Floor (Math.Sqrt (count));
 114                                 Console.WriteLine ("Trying eliminating chunks of {0}.", chunkSize);
 115                                 if (TryEliminate (methods, chunkSize))
 116                                         return true;
 117                                 Console.WriteLine ("Chunks didn't succeed, eliminating individual methods.");
 118                         }
 119
 120                         if (TryEliminate (methods, 1))
 121                                 return true;
 122
 123                         Console.WriteLine ("Couldn't eliminate any method.  Methods required to crash are:\n{0}",
 124                                 string.Join ("\n", methods));
 125                         return true;
 126                 }
 127
 128                 bool BisectStep (IEnumerable<string> methods) {
 129                         var count = methods.Count ();
 130
 131                         if (count == 0) {
 132                                 Console.WriteLine ("Error: No methods left - what happened?");
 133                                 return false;
 134                         }
 135                         if (count == 1) {
 136                                 Console.WriteLine ("Found the offending method: {0}", methods.First ());
 137                                 return true;
 138                         }
 139
 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 ());
 144
 145                         Console.WriteLine ("Running first half.");
 146                         var firstSuccess = RunWithMethods (firstHalf);
 147                         Console.WriteLine ("Crashed: {0}", !firstSuccess);
 148
 149                         if (!firstSuccess) {
 150                                 Console.WriteLine ("Continuing with first half.");
 151                                 return BisectStep (firstHalf);
 152                         }
 153
 154                         Console.WriteLine ("Running second half.");
 155                         var secondSuccess = RunWithMethods (secondHalf);
 156                         Console.WriteLine ("Crashed: {0}", !secondSuccess);
 157
 158                         if (!secondSuccess) {
 159                                 Console.WriteLine ("Continuing with second half.");
 160                                 return BisectStep (secondHalf);
 161                         }
 162
 163                         Console.WriteLine ("Error: Both halves succeeded, can't bisect.  Trying elimination.");
 164                         return EliminationStep (methods);
 165                 }
 166
 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);
 173                         }
 174
 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);
 181                         }
 182
 183                         Console.WriteLine ("Bisecting {0} methods.", methods.Count);
 184
 185                         Console.WriteLine ("Running with all methods, just to make sure.");
 186                         var success = RunWithMethods (methods);
 187                         if (success) {
 188                                 Console.WriteLine ("Error: Ran successfully with all methods optimized.  Nothing to bisect.");
 189                                 return false;
 190                         }
 191                         Console.WriteLine ("Crashed.  Bisecting.");
 192                         return BisectStep (methods);
 193                 }
 194         }
 195
 196         class MainClass
 197         {
 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);
 201                 }
 202
 203                 public static void Main (string[] args)
 204                 {
 205                         string monoPath = null;
 206                         string optName = null;
 207
 208                         var argIndex = 0;
 209                         while (argIndex < args.Length) {
 210                                 if (args [argIndex] == "--mono") {
 211                                         monoPath = args [argIndex + 1];
 212                                         argIndex += 2;
 213                                 } else if (args [argIndex] == "--opt") {
 214                                         optName = args [argIndex + 1];
 215                                         argIndex += 2;
 216                                 } else if (args [argIndex] == "--help") {
 217                                         UsageAndExit (0);
 218                                 } else if (args [argIndex] == "--") {
 219                                         argIndex += 1;
 220                                         break;
 221                                 } else {
 222                                         UsageAndExit (1);
 223                                 }
 224                         }
 225
 226                         if (monoPath == null || optName == null || argIndex == args.Length)
 227                                 UsageAndExit (1);
 228
 229                         var bisectInfo = new BisectInfo {
 230                                 MonoPath = monoPath,
 231                                 OptName = optName,
 232                                 Args = args.Skip (argIndex)
 233                         };
 234                         var success = bisectInfo.Bisect ();
 235                         Environment.Exit (success ? 0 : 1);
 236                 }
 237         }
 238 }