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