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