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     "mode": mode,
 367     "arch": arch,
 368     "system": utils.GuessOS(),
 369     "isolates": options.isolates,
 370     "deopt_fuzzer": True,
 371     "no_i18n": False,
 372   }
 373   all_tests = []
 374   num_tests = 0
 375   test_id = 0
 376
 377   # Remember test case prototypes for the fuzzing phase.
 378   test_backup = dict((s, []) for s in suites)
 379
 380   for s in suites:
 381     s.ReadStatusFile(variables)
 382     s.ReadTestCases(ctx)
 383     if len(args) > 0:
 384       s.FilterTestCasesByArgs(args)
 385     all_tests += s.tests
 386     s.FilterTestCasesByStatus(False)
 387     test_backup[s] = s.tests
 388     analysis_flags = ["--deopt-every-n-times", "%d" % MAX_DEOPT,
 389                       "--print-deopt-stress"]
 390     s.tests = [ t.CopyAddingFlags(analysis_flags) for t in s.tests ]
 391     num_tests += len(s.tests)
 392     for t in s.tests:
 393       t.id = test_id
 394       test_id += 1
 395
 396   if num_tests == 0:
 397     print "No tests to run."
 398     return 0
 399
 400   try:
 401     print(">>> Collection phase")
 402     progress_indicator = progress.PROGRESS_INDICATORS[options.progress]()
 403     runner = execution.Runner(suites, progress_indicator, ctx)
 404
 405     exit_code = runner.Run(options.j)
 406     if runner.terminate:
 407       return exit_code
 408
 409   except KeyboardInterrupt:
 410     return 1
 411
 412   print(">>> Analysis phase")
 413   num_tests = 0
 414   test_id = 0
 415   for s in suites:
 416     test_results = {}
 417     for t in s.tests:
 418       for line in t.output.stdout.splitlines():
 419         if line.startswith("=== Stress deopt counter: "):
 420           test_results[t.path] = MAX_DEOPT - int(line.split(" ")[-1])
 421     for t in s.tests:
 422       if t.path not in test_results:
 423         print "Missing results for %s" % t.path
 424     if options.dump_results_file:
 425       results_dict = dict((t.path, n) for (t, n) in test_results.iteritems())
 426       with file("%s.%d.txt" % (dump_results_file, time.time()), "w") as f:
 427         f.write(json.dumps(results_dict))
 428
 429     # Reset tests and redistribute the prototypes from the collection phase.
 430     s.tests = []
 431     if options.verbose:
 432       print "Test distributions:"
 433     for t in test_backup[s]:
 434       max_deopt = test_results.get(t.path, 0)
 435       if max_deopt == 0:
 436         continue
 437       n_deopt = CalculateNTests(max_deopt, options)
 438       distribution = dist.Distribute(n_deopt, max_deopt)
 439       if options.verbose:
 440         print "%s %s" % (t.path, distribution)
 441       for i in distribution:
 442         fuzzing_flags = ["--deopt-every-n-times", "%d" % i]
 443         s.tests.append(t.CopyAddingFlags(fuzzing_flags))
 444     num_tests += len(s.tests)
 445     for t in s.tests:
 446       t.id = test_id
 447       test_id += 1
 448
 449   if num_tests == 0:
 450     print "No tests to run."
 451     return 0
 452
 453   try:
 454     print(">>> Deopt fuzzing phase (%d test cases)" % num_tests)
 455     progress_indicator = progress.PROGRESS_INDICATORS[options.progress]()
 456     runner = execution.Runner(suites, progress_indicator, ctx)
 457
 458     exit_code = runner.Run(options.j)
 459     if runner.terminate:
 460       return exit_code
 461
 462   except KeyboardInterrupt:
 463     return 1
 464
 465   return exit_code
 466
 467
 468 if __name__ == "__main__":
 469   sys.exit(Main())