src/v8/tools/run-deopt-fuzzer.py

   1 #!/usr/bin/env python
   2 #
   3 # Copyright 2012 the V8 project authors. All rights reserved.
   4 # Redistribution and use in source and binary forms, with or without
   5 # modification, are permitted provided that the following conditions are
   6 # met:
   7 #
   8 #     * Redistributions of source code must retain the above copyright
   9 #       notice, this list of conditions and the following disclaimer.
  10 #     * Redistributions in binary form must reproduce the above
  11 #       copyright notice, this list of conditions and the following
  12 #       disclaimer in the documentation and/or other materials provided
  13 #       with the distribution.
  14 #     * Neither the name of Google Inc. nor the names of its
  15 #       contributors may be used to endorse or promote products derived
  16 #       from this software without specific prior written permission.
  17 #
  18 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29
  30
  31 import json
  32 import math
  33 import multiprocessing
  34 import optparse
  35 import os
  36 from os.path import join
  37 import random
  38 import shlex
  39 import subprocess
  40 import sys
  41 import time
  42
  43 from testrunner.local import execution
  44 from testrunner.local import progress
  45 from testrunner.local import testsuite
  46 from testrunner.local import utils
  47 from testrunner.local import verbose
  48 from testrunner.objects import context
  49
  50
  51 ARCH_GUESS = utils.DefaultArch()
  52 DEFAULT_TESTS = ["mjsunit", "webkit"]
  53 TIMEOUT_DEFAULT = 60
  54 TIMEOUT_SCALEFACTOR = {"debug"   : 4,
  55                        "release" : 1 }
  56
  57 MODE_FLAGS = {
  58     "debug"   : ["--nobreak-on-abort", "--nodead-code-elimination",
  59                  "--nofold-constants", "--enable-slow-asserts",
  60                  "--debug-code", "--verify-heap",
  61                  "--noconcurrent-recompilation"],
  62     "release" : ["--nobreak-on-abort", "--nodead-code-elimination",
  63                  "--nofold-constants", "--noconcurrent-recompilation"]}
  64
  65 SUPPORTED_ARCHS = ["android_arm",
  66                    "android_ia32",
  67                    "arm",
  68                    "ia32",
  69                    "mipsel",
  70                    "nacl_ia32",
  71                    "nacl_x64",
  72                    "x64"]
  73 # Double the timeout for these:
  74 SLOW_ARCHS = ["android_arm",
  75               "android_ia32",
  76               "arm",
  77               "mipsel",
  78               "nacl_ia32",
  79               "nacl_x64"]
  80 MAX_DEOPT = 1000000000
  81 DISTRIBUTION_MODES = ["smooth", "random"]
  82
  83
  84 class RandomDistribution:
  85   def __init__(self, seed=None):
  86     seed = seed or random.randint(1, sys.maxint)
  87     print "Using random distribution with seed %d" % seed
  88     self._random = random.Random(seed)
  89
  90   def Distribute(self, n, m):
  91     if n > m:
  92       n = m
  93     return self._random.sample(xrange(1, m + 1), n)
  94
  95
  96 class SmoothDistribution:
  97   """Distribute n numbers into the interval [1:m].
  98   F1: Factor of the first derivation of the distribution function.
  99   F2: Factor of the second derivation of the distribution function.
 100   With F1 and F2 set to 0, the distribution will be equal.
 101   """
 102   def __init__(self, factor1=2.0, factor2=0.2):
 103     self._factor1 = factor1
 104     self._factor2 = factor2
 105
 106   def Distribute(self, n, m):
 107     if n > m:
 108       n = m
 109     if n <= 1:
 110       return [ 1 ]
 111
 112     result = []
 113     x = 0.0
 114     dx = 1.0
 115     ddx = self._factor1
 116     dddx = self._factor2
 117     for i in range(0, n):
 118       result += [ x ]
 119       x += dx
 120       dx += ddx
 121       ddx += dddx
 122
 123     # Project the distribution into the interval [0:M].
 124     result = [ x * m / result[-1] for x in result ]
 125
 126     # Equalize by n. The closer n is to m, the more equal will be the
 127     # distribution.
 128     for (i, x) in enumerate(result):
 129       # The value of x if it was equally distributed.
 130       equal_x = i / float(n - 1) * float(m - 1) + 1
 131
 132       # Difference factor between actual and equal distribution.
 133       diff = 1 - (x / equal_x)
 134
 135       # Equalize x dependent on the number of values to distribute.
 136       result[i] = int(x + (i + 1) * diff)
 137     return result
 138
 139
 140 def Distribution(options):
 141   if options.distribution_mode == "random":
 142     return RandomDistribution(options.seed)
 143   if options.distribution_mode == "smooth":
 144     return SmoothDistribution(options.distribution_factor1,
 145                               options.distribution_factor2)
 146
 147
 148 def BuildOptions():
 149   result = optparse.OptionParser()
 150   result.add_option("--arch",
 151                     help=("The architecture to run tests for, "
 152                           "'auto' or 'native' for auto-detect"),
 153                     default="ia32,x64,arm")
 154   result.add_option("--arch-and-mode",
 155                     help="Architecture and mode in the format 'arch.mode'",
 156                     default=None)
 157   result.add_option("--buildbot",
 158                     help="Adapt to path structure used on buildbots",
 159                     default=False, action="store_true")
 160   result.add_option("--command-prefix",
 161                     help="Prepended to each shell command used to run a test",
 162                     default="")
 163   result.add_option("--coverage", help=("Exponential test coverage "
 164                     "(range 0.0, 1.0) -- 0.0: one test, 1.0 all tests (slow)"),
 165                     default=0.4, type="float")
 166   result.add_option("--coverage-lift", help=("Lifts test coverage for tests "
 167                     "with a small number of deopt points (range 0, inf)"),
 168                     default=20, type="int")
 169   result.add_option("--download-data", help="Download missing test suite data",
 170                     default=False, action="store_true")
 171   result.add_option("--distribution-factor1", help=("Factor of the first "
 172                     "derivation of the distribution function"), default=2.0,
 173                     type="float")
 174   result.add_option("--distribution-factor2", help=("Factor of the second "
 175                     "derivation of the distribution function"), default=0.7,
 176                     type="float")
 177   result.add_option("--distribution-mode", help=("How to select deopt points "
 178                     "for a given test (smooth|random)"),
 179                     default="smooth")
 180   result.add_option("--dump-results-file", help=("Dump maximum number of "
 181                     "deopt points per test to a file"))
 182   result.add_option("--extra-flags",
 183                     help="Additional flags to pass to each test command",
 184                     default="")
 185   result.add_option("--isolates", help="Whether to test isolates",
 186                     default=False, action="store_true")
 187   result.add_option("-j", help="The number of parallel tasks to run",
 188                     default=0, type="int")
 189   result.add_option("-m", "--mode",
 190                     help="The test modes in which to run (comma-separated)",
 191                     default="release,debug")
 192   result.add_option("--outdir", help="Base directory with compile output",
 193                     default="out")
 194   result.add_option("-p", "--progress",
 195                     help=("The style of progress indicator"
 196                           " (verbose, dots, color, mono)"),
 197                     choices=progress.PROGRESS_INDICATORS.keys(),
 198                     default="mono")
 199   result.add_option("--shard-count",
 200                     help="Split testsuites into this number of shards",
 201                     default=1, type="int")
 202   result.add_option("--shard-run",
 203                     help="Run this shard from the split up tests.",
 204                     default=1, type="int")
 205   result.add_option("--shell-dir", help="Directory containing executables",
 206                     default="")
 207   result.add_option("--seed", help="The seed for the random distribution",
 208                     type="int")
 209   result.add_option("-t", "--timeout", help="Timeout in seconds",
 210                     default= -1, type="int")
 211   result.add_option("-v", "--verbose", help="Verbose output",
 212                     default=False, action="store_true")
 213   return result
 214
 215
 216 def ProcessOptions(options):
 217   global VARIANT_FLAGS
 218
 219   # Architecture and mode related stuff.
 220   if options.arch_and_mode:
 221     tokens = options.arch_and_mode.split(".")
 222     options.arch = tokens[0]
 223     options.mode = tokens[1]
 224   options.mode = options.mode.split(",")
 225   for mode in options.mode:
 226     if not mode.lower() in ["debug", "release"]:
 227       print "Unknown mode %s" % mode
 228       return False
 229   if options.arch in ["auto", "native"]:
 230     options.arch = ARCH_GUESS
 231   options.arch = options.arch.split(",")
 232   for arch in options.arch:
 233     if not arch in SUPPORTED_ARCHS:
 234       print "Unknown architecture %s" % arch
 235       return False
 236
 237   # Special processing of other options, sorted alphabetically.
 238   options.command_prefix = shlex.split(options.command_prefix)
 239   options.extra_flags = shlex.split(options.extra_flags)
 240   if options.j == 0:
 241     options.j = multiprocessing.cpu_count()
 242   if not options.distribution_mode in DISTRIBUTION_MODES:
 243     print "Unknown distribution mode %s" % options.distribution_mode
 244     return False
 245   if options.distribution_factor1 < 0.0:
 246     print ("Distribution factor1 %s is out of range. Defaulting to 0.0"
 247         % options.distribution_factor1)
 248     options.distribution_factor1 = 0.0
 249   if options.distribution_factor2 < 0.0:
 250     print ("Distribution factor2 %s is out of range. Defaulting to 0.0"
 251         % options.distribution_factor2)
 252     options.distribution_factor2 = 0.0
 253   if options.coverage < 0.0 or options.coverage > 1.0:
 254     print ("Coverage %s is out of range. Defaulting to 0.4"
 255         % options.coverage)
 256     options.coverage = 0.4
 257   if options.coverage_lift < 0:
 258     print ("Coverage lift %s is out of range. Defaulting to 0"
 259         % options.coverage_lift)
 260     options.coverage_lift = 0
 261   return True
 262
 263
 264 def ShardTests(tests, shard_count, shard_run):
 265   if shard_count < 2:
 266     return tests
 267   if shard_run < 1 or shard_run > shard_count:
 268     print "shard-run not a valid number, should be in [1:shard-count]"
 269     print "defaulting back to running all tests"
 270     return tests
 271   count = 0
 272   shard = []
 273   for test in tests:
 274     if count % shard_count == shard_run - 1:
 275       shard.append(test)
 276     count += 1
 277   return shard
 278
 279
 280 def Main():
 281   parser = BuildOptions()
 282   (options, args) = parser.parse_args()
 283   if not ProcessOptions(options):
 284     parser.print_help()
 285     return 1
 286
 287   exit_code = 0
 288   workspace = os.path.abspath(join(os.path.dirname(sys.argv[0]), ".."))
 289
 290   suite_paths = utils.GetSuitePaths(join(workspace, "test"))
 291
 292   if len(args) == 0:
 293     suite_paths = [ s for s in suite_paths if s in DEFAULT_TESTS ]
 294   else:
 295     args_suites = set()
 296     for arg in args:
 297       suite = arg.split(os.path.sep)[0]
 298       if not suite in args_suites:
 299         args_suites.add(suite)
 300     suite_paths = [ s for s in suite_paths if s in args_suites ]
 301
 302   suites = []
 303   for root in suite_paths:
 304     suite = testsuite.TestSuite.LoadTestSuite(
 305         os.path.join(workspace, "test", root))
 306     if suite:
 307       suites.append(suite)
 308
 309   if options.download_data:
 310     for s in suites:
 311       s.DownloadData()
 312
 313   for mode in options.mode:
 314     for arch in options.arch:
 315       code = Execute(arch, mode, args, options, suites, workspace)
 316       exit_code = exit_code or code
 317   return exit_code
 318
 319
 320 def CalculateNTests(m, options):
 321   """Calculates the number of tests from m deopt points with exponential
 322   coverage.
 323   The coverage is expected to be between 0.0 and 1.0.
 324   The 'coverage lift' lifts the coverage for tests with smaller m values.
 325   """
 326   c = float(options.coverage)
 327   l = float(options.coverage_lift)
 328   return int(math.pow(m, (m * c + l) / (m + l)))
 329
 330
 331 def Execute(arch, mode, args, options, suites, workspace):
 332   print(">>> Running tests for %s.%s" % (arch, mode))
 333
 334   dist = Distribution(options)
 335
 336   shell_dir = options.shell_dir
 337   if not shell_dir:
 338     if options.buildbot:
 339       shell_dir = os.path.join(workspace, options.outdir, mode)
 340       mode = mode.lower()
 341     else:
 342       shell_dir = os.path.join(workspace, options.outdir,
 343                                "%s.%s" % (arch, mode))
 344   shell_dir = os.path.relpath(shell_dir)
 345
 346   # Populate context object.
 347   mode_flags = MODE_FLAGS[mode]
 348   timeout = options.timeout
 349   if timeout == -1:
 350     # Simulators are slow, therefore allow a longer default timeout.
 351     if arch in SLOW_ARCHS:
 352       timeout = 2 * TIMEOUT_DEFAULT;
 353     else:
 354       timeout = TIMEOUT_DEFAULT;
 355
 356   timeout *= TIMEOUT_SCALEFACTOR[mode]
 357   ctx = context.Context(arch, mode, shell_dir,
 358                         mode_flags, options.verbose,
 359                         timeout, options.isolates,
 360                         options.command_prefix,
 361                         options.extra_flags,
 362                         False)
 363
 364   # Find available test suites and read test cases from them.
 365   variables = {
 366     "arch": arch,
 367     "deopt_fuzzer": True,
 368     "gc_stress": False,
 369     "isolates": options.isolates,
 370     "mode": mode,
 371     "no_i18n": False,
 372     "system": utils.GuessOS(),
 373   }
 374   all_tests = []
 375   num_tests = 0
 376   test_id = 0
 377
 378   # Remember test case prototypes for the fuzzing phase.
 379   test_backup = dict((s, []) for s in suites)
 380
 381   for s in suites:
 382     s.ReadStatusFile(variables)
 383     s.ReadTestCases(ctx)
 384     if len(args) > 0:
 385       s.FilterTestCasesByArgs(args)
 386     all_tests += s.tests
 387     s.FilterTestCasesByStatus(False)
 388     test_backup[s] = s.tests
 389     analysis_flags = ["--deopt-every-n-times", "%d" % MAX_DEOPT,
 390                       "--print-deopt-stress"]
 391     s.tests = [ t.CopyAddingFlags(analysis_flags) for t in s.tests ]
 392     num_tests += len(s.tests)
 393     for t in s.tests:
 394       t.id = test_id
 395       test_id += 1
 396
 397   if num_tests == 0:
 398     print "No tests to run."
 399     return 0
 400
 401   try:
 402     print(">>> Collection phase")
 403     progress_indicator = progress.PROGRESS_INDICATORS[options.progress]()
 404     runner = execution.Runner(suites, progress_indicator, ctx)
 405
 406     exit_code = runner.Run(options.j)
 407     if runner.terminate:
 408       return exit_code
 409
 410   except KeyboardInterrupt:
 411     return 1
 412
 413   print(">>> Analysis phase")
 414   num_tests = 0
 415   test_id = 0
 416   for s in suites:
 417     test_results = {}
 418     for t in s.tests:
 419       for line in t.output.stdout.splitlines():
 420         if line.startswith("=== Stress deopt counter: "):
 421           test_results[t.path] = MAX_DEOPT - int(line.split(" ")[-1])
 422     for t in s.tests:
 423       if t.path not in test_results:
 424         print "Missing results for %s" % t.path
 425     if options.dump_results_file:
 426       results_dict = dict((t.path, n) for (t, n) in test_results.iteritems())
 427       with file("%s.%d.txt" % (dump_results_file, time.time()), "w") as f:
 428         f.write(json.dumps(results_dict))
 429
 430     # Reset tests and redistribute the prototypes from the collection phase.
 431     s.tests = []
 432     if options.verbose:
 433       print "Test distributions:"
 434     for t in test_backup[s]:
 435       max_deopt = test_results.get(t.path, 0)
 436       if max_deopt == 0:
 437         continue
 438       n_deopt = CalculateNTests(max_deopt, options)
 439       distribution = dist.Distribute(n_deopt, max_deopt)
 440       if options.verbose:
 441         print "%s %s" % (t.path, distribution)
 442       for i in distribution:
 443         fuzzing_flags = ["--deopt-every-n-times", "%d" % i]
 444         s.tests.append(t.CopyAddingFlags(fuzzing_flags))
 445     num_tests += len(s.tests)
 446     for t in s.tests:
 447       t.id = test_id
 448       test_id += 1
 449
 450   if num_tests == 0:
 451     print "No tests to run."
 452     return 0
 453
 454   try:
 455     print(">>> Deopt fuzzing phase (%d test cases)" % num_tests)
 456     progress_indicator = progress.PROGRESS_INDICATORS[options.progress]()
 457     runner = execution.Runner(suites, progress_indicator, ctx)
 458
 459     exit_code = runner.Run(options.j)
 460     if runner.terminate:
 461       return exit_code
 462
 463   except KeyboardInterrupt:
 464     return 1
 465
 466   return exit_code
 467
 468
 469 if __name__ == "__main__":
 470   sys.exit(Main())