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"   : ["--nohard-abort", "--nodead-code-elimination",
  59                  "--nofold-constants", "--enable-slow-asserts",
  60                  "--debug-code", "--verify-heap",
  61                  "--noconcurrent-recompilation"],
  62     "release" : ["--nohard-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("--asan",
 158                     help="Regard test expectations for ASAN",
 159                     default=False, action="store_true")
 160   result.add_option("--buildbot",
 161                     help="Adapt to path structure used on buildbots",
 162                     default=False, action="store_true")
 163   result.add_option("--command-prefix",
 164                     help="Prepended to each shell command used to run a test",
 165                     default="")
 166   result.add_option("--coverage", help=("Exponential test coverage "
 167                     "(range 0.0, 1.0) -- 0.0: one test, 1.0 all tests (slow)"),
 168                     default=0.4, type="float")
 169   result.add_option("--coverage-lift", help=("Lifts test coverage for tests "
 170                     "with a small number of deopt points (range 0, inf)"),
 171                     default=20, type="int")
 172   result.add_option("--download-data", help="Download missing test suite data",
 173                     default=False, action="store_true")
 174   result.add_option("--distribution-factor1", help=("Factor of the first "
 175                     "derivation of the distribution function"), default=2.0,
 176                     type="float")
 177   result.add_option("--distribution-factor2", help=("Factor of the second "
 178                     "derivation of the distribution function"), default=0.7,
 179                     type="float")
 180   result.add_option("--distribution-mode", help=("How to select deopt points "
 181                     "for a given test (smooth|random)"),
 182                     default="smooth")
 183   result.add_option("--dump-results-file", help=("Dump maximum number of "
 184                     "deopt points per test to a file"))
 185   result.add_option("--extra-flags",
 186                     help="Additional flags to pass to each test command",
 187                     default="")
 188   result.add_option("--isolates", help="Whether to test isolates",
 189                     default=False, action="store_true")
 190   result.add_option("-j", help="The number of parallel tasks to run",
 191                     default=0, type="int")
 192   result.add_option("-m", "--mode",
 193                     help="The test modes in which to run (comma-separated)",
 194                     default="release,debug")
 195   result.add_option("--outdir", help="Base directory with compile output",
 196                     default="out")
 197   result.add_option("-p", "--progress",
 198                     help=("The style of progress indicator"
 199                           " (verbose, dots, color, mono)"),
 200                     choices=progress.PROGRESS_INDICATORS.keys(),
 201                     default="mono")
 202   result.add_option("--shard-count",
 203                     help="Split testsuites into this number of shards",
 204                     default=1, type="int")
 205   result.add_option("--shard-run",
 206                     help="Run this shard from the split up tests.",
 207                     default=1, type="int")
 208   result.add_option("--shell-dir", help="Directory containing executables",
 209                     default="")
 210   result.add_option("--seed", help="The seed for the random distribution",
 211                     type="int")
 212   result.add_option("-t", "--timeout", help="Timeout in seconds",
 213                     default= -1, type="int")
 214   result.add_option("-v", "--verbose", help="Verbose output",
 215                     default=False, action="store_true")
 216   result.add_option("--random-seed", default=0, dest="random_seed",
 217                     help="Default seed for initializing random generator")
 218   return result
 219
 220
 221 def ProcessOptions(options):
 222   global VARIANT_FLAGS
 223
 224   # Architecture and mode related stuff.
 225   if options.arch_and_mode:
 226     tokens = options.arch_and_mode.split(".")
 227     options.arch = tokens[0]
 228     options.mode = tokens[1]
 229   options.mode = options.mode.split(",")
 230   for mode in options.mode:
 231     if not mode.lower() in ["debug", "release"]:
 232       print "Unknown mode %s" % mode
 233       return False
 234   if options.arch in ["auto", "native"]:
 235     options.arch = ARCH_GUESS
 236   options.arch = options.arch.split(",")
 237   for arch in options.arch:
 238     if not arch in SUPPORTED_ARCHS:
 239       print "Unknown architecture %s" % arch
 240       return False
 241
 242   # Special processing of other options, sorted alphabetically.
 243   options.command_prefix = shlex.split(options.command_prefix)
 244   options.extra_flags = shlex.split(options.extra_flags)
 245   if options.j == 0:
 246     options.j = multiprocessing.cpu_count()
 247   while options.random_seed == 0:
 248     options.random_seed = random.SystemRandom().randint(-2147483648, 2147483647)
 249   if not options.distribution_mode in DISTRIBUTION_MODES:
 250     print "Unknown distribution mode %s" % options.distribution_mode
 251     return False
 252   if options.distribution_factor1 < 0.0:
 253     print ("Distribution factor1 %s is out of range. Defaulting to 0.0"
 254         % options.distribution_factor1)
 255     options.distribution_factor1 = 0.0
 256   if options.distribution_factor2 < 0.0:
 257     print ("Distribution factor2 %s is out of range. Defaulting to 0.0"
 258         % options.distribution_factor2)
 259     options.distribution_factor2 = 0.0
 260   if options.coverage < 0.0 or options.coverage > 1.0:
 261     print ("Coverage %s is out of range. Defaulting to 0.4"
 262         % options.coverage)
 263     options.coverage = 0.4
 264   if options.coverage_lift < 0:
 265     print ("Coverage lift %s is out of range. Defaulting to 0"
 266         % options.coverage_lift)
 267     options.coverage_lift = 0
 268   return True
 269
 270
 271 def ShardTests(tests, shard_count, shard_run):
 272   if shard_count < 2:
 273     return tests
 274   if shard_run < 1 or shard_run > shard_count:
 275     print "shard-run not a valid number, should be in [1:shard-count]"
 276     print "defaulting back to running all tests"
 277     return tests
 278   count = 0
 279   shard = []
 280   for test in tests:
 281     if count % shard_count == shard_run - 1:
 282       shard.append(test)
 283     count += 1
 284   return shard
 285
 286
 287 def Main():
 288   parser = BuildOptions()
 289   (options, args) = parser.parse_args()
 290   if not ProcessOptions(options):
 291     parser.print_help()
 292     return 1
 293
 294   exit_code = 0
 295   workspace = os.path.abspath(join(os.path.dirname(sys.argv[0]), ".."))
 296
 297   suite_paths = utils.GetSuitePaths(join(workspace, "test"))
 298
 299   if len(args) == 0:
 300     suite_paths = [ s for s in suite_paths if s in DEFAULT_TESTS ]
 301   else:
 302     args_suites = set()
 303     for arg in args:
 304       suite = arg.split(os.path.sep)[0]
 305       if not suite in args_suites:
 306         args_suites.add(suite)
 307     suite_paths = [ s for s in suite_paths if s in args_suites ]
 308
 309   suites = []
 310   for root in suite_paths:
 311     suite = testsuite.TestSuite.LoadTestSuite(
 312         os.path.join(workspace, "test", root))
 313     if suite:
 314       suites.append(suite)
 315
 316   if options.download_data:
 317     for s in suites:
 318       s.DownloadData()
 319
 320   for mode in options.mode:
 321     for arch in options.arch:
 322       try:
 323         code = Execute(arch, mode, args, options, suites, workspace)
 324         exit_code = exit_code or code
 325       except KeyboardInterrupt:
 326         return 2
 327   return exit_code
 328
 329
 330 def CalculateNTests(m, options):
 331   """Calculates the number of tests from m deopt points with exponential
 332   coverage.
 333   The coverage is expected to be between 0.0 and 1.0.
 334   The 'coverage lift' lifts the coverage for tests with smaller m values.
 335   """
 336   c = float(options.coverage)
 337   l = float(options.coverage_lift)
 338   return int(math.pow(m, (m * c + l) / (m + l)))
 339
 340
 341 def Execute(arch, mode, args, options, suites, workspace):
 342   print(">>> Running tests for %s.%s" % (arch, mode))
 343
 344   dist = Distribution(options)
 345
 346   shell_dir = options.shell_dir
 347   if not shell_dir:
 348     if options.buildbot:
 349       shell_dir = os.path.join(workspace, options.outdir, mode)
 350       mode = mode.lower()
 351     else:
 352       shell_dir = os.path.join(workspace, options.outdir,
 353                                "%s.%s" % (arch, mode))
 354   shell_dir = os.path.relpath(shell_dir)
 355
 356   # Populate context object.
 357   mode_flags = MODE_FLAGS[mode]
 358   timeout = options.timeout
 359   if timeout == -1:
 360     # Simulators are slow, therefore allow a longer default timeout.
 361     if arch in SLOW_ARCHS:
 362       timeout = 2 * TIMEOUT_DEFAULT;
 363     else:
 364       timeout = TIMEOUT_DEFAULT;
 365
 366   timeout *= TIMEOUT_SCALEFACTOR[mode]
 367   ctx = context.Context(arch, mode, shell_dir,
 368                         mode_flags, options.verbose,
 369                         timeout, options.isolates,
 370                         options.command_prefix,
 371                         options.extra_flags,
 372                         False,  # Keep i18n on by default.
 373                         options.random_seed,
 374                         True,  # No sorting of test cases.
 375                         0,  # Don't rerun failing tests.
 376                         0,  # No use of a rerun-failing-tests maximum.
 377                         False)  # No predictable mode.
 378
 379   # Find available test suites and read test cases from them.
 380   variables = {
 381     "arch": arch,
 382     "asan": options.asan,
 383     "deopt_fuzzer": True,
 384     "gc_stress": False,
 385     "isolates": options.isolates,
 386     "mode": mode,
 387     "no_i18n": False,
 388     "no_snap": False,
 389     "simulator": utils.UseSimulator(arch),
 390     "system": utils.GuessOS(),
 391     "tsan": False,
 392     "msan": False,
 393   }
 394   all_tests = []
 395   num_tests = 0
 396   test_id = 0
 397
 398   # Remember test case prototypes for the fuzzing phase.
 399   test_backup = dict((s, []) for s in suites)
 400
 401   for s in suites:
 402     s.ReadStatusFile(variables)
 403     s.ReadTestCases(ctx)
 404     if len(args) > 0:
 405       s.FilterTestCasesByArgs(args)
 406     all_tests += s.tests
 407     s.FilterTestCasesByStatus(False)
 408     test_backup[s] = s.tests
 409     analysis_flags = ["--deopt-every-n-times", "%d" % MAX_DEOPT,
 410                       "--print-deopt-stress"]
 411     s.tests = [ t.CopyAddingFlags(analysis_flags) for t in s.tests ]
 412     num_tests += len(s.tests)
 413     for t in s.tests:
 414       t.id = test_id
 415       test_id += 1
 416
 417   if num_tests == 0:
 418     print "No tests to run."
 419     return 0
 420
 421   print(">>> Collection phase")
 422   progress_indicator = progress.PROGRESS_INDICATORS[options.progress]()
 423   runner = execution.Runner(suites, progress_indicator, ctx)
 424
 425   exit_code = runner.Run(options.j)
 426
 427   print(">>> Analysis phase")
 428   num_tests = 0
 429   test_id = 0
 430   for s in suites:
 431     test_results = {}
 432     for t in s.tests:
 433       for line in t.output.stdout.splitlines():
 434         if line.startswith("=== Stress deopt counter: "):
 435           test_results[t.path] = MAX_DEOPT - int(line.split(" ")[-1])
 436     for t in s.tests:
 437       if t.path not in test_results:
 438         print "Missing results for %s" % t.path
 439     if options.dump_results_file:
 440       results_dict = dict((t.path, n) for (t, n) in test_results.iteritems())
 441       with file("%s.%d.txt" % (dump_results_file, time.time()), "w") as f:
 442         f.write(json.dumps(results_dict))
 443
 444     # Reset tests and redistribute the prototypes from the collection phase.
 445     s.tests = []
 446     if options.verbose:
 447       print "Test distributions:"
 448     for t in test_backup[s]:
 449       max_deopt = test_results.get(t.path, 0)
 450       if max_deopt == 0:
 451         continue
 452       n_deopt = CalculateNTests(max_deopt, options)
 453       distribution = dist.Distribute(n_deopt, max_deopt)
 454       if options.verbose:
 455         print "%s %s" % (t.path, distribution)
 456       for i in distribution:
 457         fuzzing_flags = ["--deopt-every-n-times", "%d" % i]
 458         s.tests.append(t.CopyAddingFlags(fuzzing_flags))
 459     num_tests += len(s.tests)
 460     for t in s.tests:
 461       t.id = test_id
 462       test_id += 1
 463
 464   if num_tests == 0:
 465     print "No tests to run."
 466     return 0
 467
 468   print(">>> Deopt fuzzing phase (%d test cases)" % num_tests)
 469   progress_indicator = progress.PROGRESS_INDICATORS[options.progress]()
 470   runner = execution.Runner(suites, progress_indicator, ctx)
 471
 472   code = runner.Run(options.j)
 473   return exit_code or code
 474
 475
 476 if __name__ == "__main__":
 477   sys.exit(Main())