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