bisection_search.py revision f68312d0aa5d32e720077118995669c63b04f89d 
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
19See README.md.
20
21Example usage:
22./bisection-search.py -cp classes.dex --expected-output output Test
23"""
24
25import abc
26import argparse
27import os
28import re
29import shlex
30import sys
31
32from subprocess import call
33from tempfile import NamedTemporaryFile
34
35sys.path.append(os.path.dirname(os.path.dirname(
36        os.path.realpath(__file__))))
37
38from common.common import DeviceTestEnv
39from common.common import FatalError
40from common.common import GetEnvVariableOrError
41from common.common import HostTestEnv
42from common.common import LogSeverity
43from common.common import RetCode
44
45
46# Passes that are never disabled during search process because disabling them
47# would compromise correctness.
48MANDATORY_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.
58NON_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.
64RAW_CMD_RUNTIME_ARGS_TAG = '{ARGS}'
65
66# Default core image path relative to ANDROID_HOST_OUT.
67DEFAULT_IMAGE_RELATIVE_PATH = '/framework/core.art'
68
69class 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
183class 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
202class 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
218class 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
250def 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
261def 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
267def 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
313def 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
359def 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
379def 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
439if __name__ == '__main__':
440  main()
441