Home | History | Annotate | Download | only in bisection_search 
      1 #!/usr/bin/env python3.4
      2 #
      3 # Copyright (C) 2016 The Android Open Source Project
      4 #
      5 # Licensed under the Apache License, Version 2.0 (the "License");
      6 # you may not use this file except in compliance with the License.
      7 # You may obtain a copy of the License at
      8 #
      9 #   http://www.apache.org/licenses/LICENSE-2.0
     10 #
     11 # Unless required by applicable law or agreed to in writing, software
     12 # distributed under the License is distributed on an "AS IS" BASIS,
     13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     14 # See the License for the specific language governing permissions and
     15 # limitations under the License.
     16 
     17 """Performs bisection bug search on methods and optimizations.
     18 
     19 See README.md.
     20 
     21 Example usage:
     22 ./bisection-search.py -cp classes.dex --expected-output output Test
     23 """
     24 
     25 import abc
     26 import argparse
     27 import os
     28 import re
     29 import shlex
     30 import sys
     31 
     32 from subprocess import call
     33 from tempfile import NamedTemporaryFile
     34 
     35 sys.path.append(os.path.dirname(os.path.dirname(
     36         os.path.realpath(__file__))))
     37 
     38 from common.common import DeviceTestEnv
     39 from common.common import FatalError
     40 from common.common import GetEnvVariableOrError
     41 from common.common import HostTestEnv
     42 from common.common import LogSeverity
     43 from common.common import RetCode
     44 
     45 
     46 # Passes that are never disabled during search process because disabling them
     47 # would compromise correctness.
     48 MANDATORY_PASSES = ['dex_cache_array_fixups_arm',
     49                     'dex_cache_array_fixups_mips',
     50                     'instruction_simplifier$before_codegen',
     51                     'pc_relative_fixups_x86',
     52                     'pc_relative_fixups_mips',
     53                     'x86_memory_operand_generation']
     54 
     55 # Passes that show up as optimizations in compiler verbose output but aren't
     56 # driven by run-passes mechanism. They are mandatory and will always run, we
     57 # never pass them to --run-passes.
     58 NON_PASSES = ['builder', 'prepare_for_register_allocation',
     59               'liveness', 'register']
     60 
     61 # If present in raw cmd, this tag will be replaced with runtime arguments
     62 # controlling the bisection search. Otherwise arguments will be placed on second
     63 # position in the command.
     64 RAW_CMD_RUNTIME_ARGS_TAG = '{ARGS}'
     65 
     66 # Default core image path relative to ANDROID_HOST_OUT.
     67 DEFAULT_IMAGE_RELATIVE_PATH = '/framework/core.art'
     68 
     69 class Dex2OatWrapperTestable(object):
     70   """Class representing a testable compilation.
     71 
     72   Accepts filters on compiled methods and optimization passes.
     73   """
     74 
     75   def __init__(self, base_cmd, test_env, expected_retcode=None,
     76                output_checker=None, verbose=False):
     77     """Constructor.
     78 
     79     Args:
     80       base_cmd: list of strings, base command to run.
     81       test_env: ITestEnv.
     82       expected_retcode: RetCode, expected normalized return code.
     83       output_checker: IOutputCheck, output checker.
     84       verbose: bool, enable verbose output.
     85     """
     86     self._base_cmd = base_cmd
     87     self._test_env = test_env
     88     self._expected_retcode = expected_retcode
     89     self._output_checker = output_checker
     90     self._compiled_methods_path = self._test_env.CreateFile('compiled_methods')
     91     self._passes_to_run_path = self._test_env.CreateFile('run_passes')
     92     self._verbose = verbose
     93     if RAW_CMD_RUNTIME_ARGS_TAG in self._base_cmd:
     94       self._arguments_position = self._base_cmd.index(RAW_CMD_RUNTIME_ARGS_TAG)
     95       self._base_cmd.pop(self._arguments_position)
     96     else:
     97       self._arguments_position = 1
     98 
     99   def Test(self, compiled_methods, passes_to_run=None):
    100     """Tests compilation with compiled_methods and run_passes switches active.
    101 
    102     If compiled_methods is None then compiles all methods.
    103     If passes_to_run is None then runs default passes.
    104 
    105     Args:
    106       compiled_methods: list of strings representing methods to compile or None.
    107       passes_to_run: list of strings representing passes to run or None.
    108 
    109     Returns:
    110       True if test passes with given settings. False otherwise.
    111     """
    112     if self._verbose:
    113       print('Testing methods: {0} passes: {1}.'.format(
    114           compiled_methods, passes_to_run))
    115     cmd = self._PrepareCmd(compiled_methods=compiled_methods,
    116                            passes_to_run=passes_to_run)
    117     (output, ret_code) = self._test_env.RunCommand(
    118         cmd, LogSeverity.ERROR)
    119     res = True
    120     if self._expected_retcode:
    121       res = self._expected_retcode == ret_code
    122     if self._output_checker:
    123       res = res and self._output_checker.Check(output)
    124     if self._verbose:
    125       print('Test passed: {0}.'.format(res))
    126     return res
    127 
    128   def GetAllMethods(self):
    129     """Get methods compiled during the test.
    130 
    131     Returns:
    132       List of strings representing methods compiled during the test.
    133 
    134     Raises:
    135       FatalError: An error occurred when retrieving methods list.
    136     """
    137     cmd = self._PrepareCmd()
    138     (output, _) = self._test_env.RunCommand(cmd, LogSeverity.INFO)
    139     match_methods = re.findall(r'Building ([^\n]+)\n', output)
    140     if not match_methods:
    141       raise FatalError('Failed to retrieve methods list. '
    142                        'Not recognized output format.')
    143     return match_methods
    144 
    145   def GetAllPassesForMethod(self, compiled_method):
    146     """Get all optimization passes ran for a method during the test.
    147 
    148     Args:
    149       compiled_method: string representing method to compile.
    150 
    151     Returns:
    152       List of strings representing passes ran for compiled_method during test.
    153 
    154     Raises:
    155       FatalError: An error occurred when retrieving passes list.
    156     """
    157     cmd = self._PrepareCmd(compiled_methods=[compiled_method])
    158     (output, _) = self._test_env.RunCommand(cmd, LogSeverity.INFO)
    159     match_passes = re.findall(r'Starting pass: ([^\n]+)\n', output)
    160     if not match_passes:
    161       raise FatalError('Failed to retrieve passes list. '
    162                        'Not recognized output format.')
    163     return [p for p in match_passes if p not in NON_PASSES]
    164 
    165   def _PrepareCmd(self, compiled_methods=None, passes_to_run=None):
    166     """Prepare command to run."""
    167     cmd = self._base_cmd[0:self._arguments_position]
    168     # insert additional arguments before the first argument
    169     if compiled_methods is not None:
    170       self._test_env.WriteLines(self._compiled_methods_path, compiled_methods)
    171       cmd += ['-Xcompiler-option', '--compiled-methods={0}'.format(
    172           self._compiled_methods_path)]
    173     if passes_to_run is not None:
    174       self._test_env.WriteLines(self._passes_to_run_path, passes_to_run)
    175       cmd += ['-Xcompiler-option', '--run-passes={0}'.format(
    176           self._passes_to_run_path)]
    177     cmd += ['-Xcompiler-option', '--runtime-arg', '-Xcompiler-option',
    178             '-verbose:compiler', '-Xcompiler-option', '-j1']
    179     cmd += self._base_cmd[self._arguments_position:]
    180     return cmd
    181 
    182 
    183 class IOutputCheck(object):
    184   """Abstract output checking class.
    185 
    186   Checks if output is correct.
    187   """
    188   __meta_class__ = abc.ABCMeta
    189 
    190   @abc.abstractmethod
    191   def Check(self, output):
    192     """Check if output is correct.
    193 
    194     Args:
    195       output: string, output to check.
    196 
    197     Returns:
    198       boolean, True if output is correct, False otherwise.
    199     """
    200 
    201 
    202 class EqualsOutputCheck(IOutputCheck):
    203   """Concrete output checking class checking for equality to expected output."""
    204 
    205   def __init__(self, expected_output):
    206     """Constructor.
    207 
    208     Args:
    209       expected_output: string, expected output.
    210     """
    211     self._expected_output = expected_output
    212 
    213   def Check(self, output):
    214     """See base class."""
    215     return self._expected_output == output
    216 
    217 
    218 class ExternalScriptOutputCheck(IOutputCheck):
    219   """Concrete output checking class calling an external script.
    220 
    221   The script should accept two arguments, path to expected output and path to
    222   program output. It should exit with 0 return code if outputs are equivalent
    223   and with different return code otherwise.
    224   """
    225 
    226   def __init__(self, script_path, expected_output_path, logfile):
    227     """Constructor.
    228 
    229     Args:
    230       script_path: string, path to checking script.
    231       expected_output_path: string, path to file with expected output.
    232       logfile: file handle, logfile.
    233     """
    234     self._script_path = script_path
    235     self._expected_output_path = expected_output_path
    236     self._logfile = logfile
    237 
    238   def Check(self, output):
    239     """See base class."""
    240     ret_code = None
    241     with NamedTemporaryFile(mode='w', delete=False) as temp_file:
    242       temp_file.write(output)
    243       temp_file.flush()
    244       ret_code = call(
    245           [self._script_path, self._expected_output_path, temp_file.name],
    246           stdout=self._logfile, stderr=self._logfile, universal_newlines=True)
    247     return ret_code == 0
    248 
    249 
    250 def BinarySearch(start, end, test):
    251   """Binary search integers using test function to guide the process."""
    252   while start < end:
    253     mid = (start + end) // 2
    254     if test(mid):
    255       start = mid + 1
    256     else:
    257       end = mid
    258   return start
    259 
    260 
    261 def FilterPasses(passes, cutoff_idx):
    262   """Filters passes list according to cutoff_idx but keeps mandatory passes."""
    263   return [opt_pass for idx, opt_pass in enumerate(passes)
    264           if opt_pass in MANDATORY_PASSES or idx < cutoff_idx]
    265 
    266 
    267 def BugSearch(testable):
    268   """Find buggy (method, optimization pass) pair for a given testable.
    269 
    270   Args:
    271     testable: Dex2OatWrapperTestable.
    272 
    273   Returns:
    274     (string, string) tuple. First element is name of method which when compiled
    275     exposes test failure. Second element is name of optimization pass such that
    276     for aforementioned method running all passes up to and excluding the pass
    277     results in test passing but running all passes up to and including the pass
    278     results in test failing.
    279 
    280     (None, None) if test passes when compiling all methods.
    281     (string, None) if a method is found which exposes the failure, but the
    282       failure happens even when running just mandatory passes.
    283 
    284   Raises:
    285     FatalError: Testable fails with no methods compiled.
    286     AssertionError: Method failed for all passes when bisecting methods, but
    287     passed when bisecting passes. Possible sporadic failure.
    288   """
    289   all_methods = testable.GetAllMethods()
    290   faulty_method_idx = BinarySearch(
    291       0,
    292       len(all_methods) + 1,
    293       lambda mid: testable.Test(all_methods[0:mid]))
    294   if faulty_method_idx == len(all_methods) + 1:
    295     return (None, None)
    296   if faulty_method_idx == 0:
    297     raise FatalError('Testable fails with no methods compiled.')
    298   faulty_method = all_methods[faulty_method_idx - 1]
    299   all_passes = testable.GetAllPassesForMethod(faulty_method)
    300   faulty_pass_idx = BinarySearch(
    301       0,
    302       len(all_passes) + 1,
    303       lambda mid: testable.Test([faulty_method],
    304                                 FilterPasses(all_passes, mid)))
    305   if faulty_pass_idx == 0:
    306     return (faulty_method, None)
    307   assert faulty_pass_idx != len(all_passes) + 1, ('Method must fail for some '
    308                                                   'passes.')
    309   faulty_pass = all_passes[faulty_pass_idx - 1]
    310   return (faulty_method, faulty_pass)
    311 
    312 
    313 def PrepareParser():
    314   """Prepares argument parser."""
    315   parser = argparse.ArgumentParser(
    316       description='Tool for finding compiler bugs. Either --raw-cmd or both '
    317                   '-cp and --class are required.')
    318   command_opts = parser.add_argument_group('dalvikvm command options')
    319   command_opts.add_argument('-cp', '--classpath', type=str, help='classpath')
    320   command_opts.add_argument('--class', dest='classname', type=str,
    321                             help='name of main class')
    322   command_opts.add_argument('--lib', type=str, default='libart.so',
    323                             help='lib to use, default: libart.so')
    324   command_opts.add_argument('--dalvikvm-option', dest='dalvikvm_opts',
    325                             metavar='OPT', nargs='*', default=[],
    326                             help='additional dalvikvm option')
    327   command_opts.add_argument('--arg', dest='test_args', nargs='*', default=[],
    328                             metavar='ARG', help='argument passed to test')
    329   command_opts.add_argument('--image', type=str, help='path to image')
    330   command_opts.add_argument('--raw-cmd', type=str,
    331                             help='bisect with this command, ignore other '
    332                                  'command options')
    333   bisection_opts = parser.add_argument_group('bisection options')
    334   bisection_opts.add_argument('--64', dest='x64', action='store_true',
    335                               default=False, help='x64 mode')
    336   bisection_opts.add_argument(
    337       '--device', action='store_true', default=False, help='run on device')
    338   bisection_opts.add_argument(
    339       '--device-serial', help='device serial number, implies --device')
    340   bisection_opts.add_argument('--expected-output', type=str,
    341                               help='file containing expected output')
    342   bisection_opts.add_argument(
    343       '--expected-retcode', type=str, help='expected normalized return code',
    344       choices=[RetCode.SUCCESS.name, RetCode.TIMEOUT.name, RetCode.ERROR.name])
    345   bisection_opts.add_argument(
    346       '--check-script', type=str,
    347       help='script comparing output and expected output')
    348   bisection_opts.add_argument(
    349       '--logfile', type=str, help='custom logfile location')
    350   bisection_opts.add_argument('--cleanup', action='store_true',
    351                               default=False, help='clean up after bisecting')
    352   bisection_opts.add_argument('--timeout', type=int, default=60,
    353                               help='if timeout seconds pass assume test failed')
    354   bisection_opts.add_argument('--verbose', action='store_true',
    355                               default=False, help='enable verbose output')
    356   return parser
    357 
    358 
    359 def PrepareBaseCommand(args, classpath):
    360   """Prepares base command used to run test."""
    361   if args.raw_cmd:
    362     return shlex.split(args.raw_cmd)
    363   else:
    364     base_cmd = ['dalvikvm64'] if args.x64 else ['dalvikvm32']
    365     if not args.device:
    366       base_cmd += ['-XXlib:{0}'.format(args.lib)]
    367       if not args.image:
    368         image_path = (GetEnvVariableOrError('ANDROID_HOST_OUT') +
    369                       DEFAULT_IMAGE_RELATIVE_PATH)
    370       else:
    371         image_path = args.image
    372       base_cmd += ['-Ximage:{0}'.format(image_path)]
    373     if args.dalvikvm_opts:
    374       base_cmd += args.dalvikvm_opts
    375     base_cmd += ['-cp', classpath, args.classname] + args.test_args
    376   return base_cmd
    377 
    378 
    379 def main():
    380   # Parse arguments
    381   parser = PrepareParser()
    382   args = parser.parse_args()
    383   if not args.raw_cmd and (not args.classpath or not args.classname):
    384     parser.error('Either --raw-cmd or both -cp and --class are required')
    385   if args.device_serial:
    386     args.device = True
    387   if args.expected_retcode:
    388     args.expected_retcode = RetCode[args.expected_retcode]
    389   if not args.expected_retcode and not args.check_script:
    390     args.expected_retcode = RetCode.SUCCESS
    391 
    392   # Prepare environment
    393   classpath = args.classpath
    394   if args.device:
    395     test_env = DeviceTestEnv(
    396         'bisection_search_', args.cleanup, args.logfile, args.timeout,
    397         args.device_serial)
    398     if classpath:
    399       classpath = test_env.PushClasspath(classpath)
    400   else:
    401     test_env = HostTestEnv(
    402         'bisection_search_', args.cleanup, args.logfile, args.timeout, args.x64)
    403   base_cmd = PrepareBaseCommand(args, classpath)
    404   output_checker = None
    405   if args.expected_output:
    406     if args.check_script:
    407       output_checker = ExternalScriptOutputCheck(
    408           args.check_script, args.expected_output, test_env.logfile)
    409     else:
    410       with open(args.expected_output, 'r') as expected_output_file:
    411         output_checker = EqualsOutputCheck(expected_output_file.read())
    412 
    413   # Perform the search
    414   try:
    415     testable = Dex2OatWrapperTestable(base_cmd, test_env, args.expected_retcode,
    416                                       output_checker, args.verbose)
    417     if testable.Test(compiled_methods=[]):
    418       (method, opt_pass) = BugSearch(testable)
    419     else:
    420       print('Testable fails with no methods compiled.')
    421       sys.exit(1)
    422   except Exception as e:
    423     print('Error occurred.\nLogfile: {0}'.format(test_env.logfile.name))
    424     test_env.logfile.write('Exception: {0}\n'.format(e))
    425     raise
    426 
    427   # Report results
    428   if method is None:
    429     print('Couldn\'t find any bugs.')
    430   elif opt_pass is None:
    431     print('Faulty method: {0}. Fails with just mandatory passes.'.format(
    432         method))
    433   else:
    434     print('Faulty method and pass: {0}, {1}.'.format(method, opt_pass))
    435   print('Logfile: {0}'.format(test_env.logfile.name))
    436   sys.exit(0)
    437 
    438 
    439 if __name__ == '__main__':
    440   main()
    441