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       code = Execute(arch, mode, args, options, suites, workspace)
 323       exit_code = exit_code or code
 324   return exit_code
 325
 326
 327 def CalculateNTests(m, options):
 328   """Calculates the number of tests from m deopt points with exponential
 329   coverage.
 330   The coverage is expected to be between 0.0 and 1.0.
 331   The 'coverage lift' lifts the coverage for tests with smaller m values.
 332   """
 333   c = float(options.coverage)
 334   l = float(options.coverage_lift)
 335   return int(math.pow(m, (m * c + l) / (m + l)))
 336
 337
 338 def Execute(arch, mode, args, options, suites, workspace):
 339   print(">>> Running tests for %s.%s" % (arch, mode))
 340
 341   dist = Distribution(options)
 342
 343   shell_dir = options.shell_dir
 344   if not shell_dir:
 345     if options.buildbot:
 346       shell_dir = os.path.join(workspace, options.outdir, mode)
 347       mode = mode.lower()
 348     else:
 349       shell_dir = os.path.join(workspace, options.outdir,
 350                                "%s.%s" % (arch, mode))
 351   shell_dir = os.path.relpath(shell_dir)
 352
 353   # Populate context object.
 354   mode_flags = MODE_FLAGS[mode]
 355   timeout = options.timeout
 356   if timeout == -1:
 357     # Simulators are slow, therefore allow a longer default timeout.
 358     if arch in SLOW_ARCHS:
 359       timeout = 2 * TIMEOUT_DEFAULT;
 360     else:
 361       timeout = TIMEOUT_DEFAULT;
 362
 363   timeout *= TIMEOUT_SCALEFACTOR[mode]
 364   ctx = context.Context(arch, mode, shell_dir,
 365                         mode_flags, options.verbose,
 366                         timeout, options.isolates,
 367                         options.command_prefix,
 368                         options.extra_flags,
 369                         False,
 370                         options.random_seed)
 371
 372   # Find available test suites and read test cases from them.
 373   variables = {
 374     "arch": arch,
 375     "asan": options.asan,
 376     "deopt_fuzzer": True,
 377     "gc_stress": False,
 378     "isolates": options.isolates,
 379     "mode": mode,
 380     "no_i18n": False,
 381     "no_snap": False,
 382     "simulator": utils.UseSimulator(arch),
 383     "system": utils.GuessOS(),
 384   }
 385   all_tests = []
 386   num_tests = 0
 387   test_id = 0
 388
 389   # Remember test case prototypes for the fuzzing phase.
 390   test_backup = dict((s, []) for s in suites)
 391
 392   for s in suites:
 393     s.ReadStatusFile(variables)
 394     s.ReadTestCases(ctx)
 395     if len(args) > 0:
 396       s.FilterTestCasesByArgs(args)
 397     all_tests += s.tests
 398     s.FilterTestCasesByStatus(False)
 399     test_backup[s] = s.tests
 400     analysis_flags = ["--deopt-every-n-times", "%d" % MAX_DEOPT,
 401                       "--print-deopt-stress"]
 402     s.tests = [ t.CopyAddingFlags(analysis_flags) for t in s.tests ]
 403     num_tests += len(s.tests)
 404     for t in s.tests:
 405       t.id = test_id
 406       test_id += 1
 407
 408   if num_tests == 0:
 409     print "No tests to run."
 410     return 0
 411
 412   try:
 413     print(">>> Collection phase")
 414     progress_indicator = progress.PROGRESS_INDICATORS[options.progress]()
 415     runner = execution.Runner(suites, progress_indicator, ctx)
 416
 417     exit_code = runner.Run(options.j)
 418     if runner.terminate:
 419       return exit_code
 420
 421   except KeyboardInterrupt:
 422     return 1
 423
 424   print(">>> Analysis phase")
 425   num_tests = 0
 426   test_id = 0
 427   for s in suites:
 428     test_results = {}
 429     for t in s.tests:
 430       for line in t.output.stdout.splitlines():
 431         if line.startswith("=== Stress deopt counter: "):
 432           test_results[t.path] = MAX_DEOPT - int(line.split(" ")[-1])
 433     for t in s.tests:
 434       if t.path not in test_results:
 435         print "Missing results for %s" % t.path
 436     if options.dump_results_file:
 437       results_dict = dict((t.path, n) for (t, n) in test_results.iteritems())
 438       with file("%s.%d.txt" % (dump_results_file, time.time()), "w") as f:
 439         f.write(json.dumps(results_dict))
 440
 441     # Reset tests and redistribute the prototypes from the collection phase.
 442     s.tests = []
 443     if options.verbose:
 444       print "Test distributions:"
 445     for t in test_backup[s]:
 446       max_deopt = test_results.get(t.path, 0)
 447       if max_deopt == 0:
 448         continue
 449       n_deopt = CalculateNTests(max_deopt, options)
 450       distribution = dist.Distribute(n_deopt, max_deopt)
 451       if options.verbose:
 452         print "%s %s" % (t.path, distribution)
 453       for i in distribution:
 454         fuzzing_flags = ["--deopt-every-n-times", "%d" % i]
 455         s.tests.append(t.CopyAddingFlags(fuzzing_flags))
 456     num_tests += len(s.tests)
 457     for t in s.tests:
 458       t.id = test_id
 459       test_id += 1
 460
 461   if num_tests == 0:
 462     print "No tests to run."
 463     return 0
 464
 465   try:
 466     print(">>> Deopt fuzzing phase (%d test cases)" % num_tests)
 467     progress_indicator = progress.PROGRESS_INDICATORS[options.progress]()
 468     runner = execution.Runner(suites, progress_indicator, ctx)
 469
 470     exit_code = runner.Run(options.j)
 471     if runner.terminate:
 472       return exit_code
 473
 474   except KeyboardInterrupt:
 475     return 1
 476
 477   return exit_code
 478
 479
 480 if __name__ == "__main__":
 481   sys.exit(Main())