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