1#!/usr/bin/env python2 2 3import argparse 4import math 5import os 6import re 7import signal 8import subprocess 9 10class Runner(object): 11 def __init__(self, input_cmd, timeout, comma_join, template, find_all): 12 self._input_cmd = input_cmd 13 self._timeout = timeout 14 self._num_tries = 0 15 self._comma_join = comma_join 16 self._template = template 17 self._find_all = find_all 18 19 def estimate(self, included_ranges): 20 result = 0 21 for i in included_ranges: 22 if isinstance(i, int): 23 result += 1 24 else: 25 if i[1] - i[0] > 2: 26 result += int(math.log(i[1] - i[0], 2)) 27 else: 28 result += (i[1] - i[0]) 29 if self._find_all: 30 return 2 * result 31 else: 32 return result 33 34 def Run(self, included_ranges): 35 def timeout_handler(signum, frame): 36 raise RuntimeError('Timeout') 37 38 self._num_tries += 1 39 cmd_addition = '' 40 for i in included_ranges: 41 if isinstance(i, int): 42 range_str = str(i) 43 else: 44 range_str = '{start}:{end}'.format(start=i[0], end=i[1]) 45 if self._comma_join: 46 cmd_addition += ',' + range_str 47 else: 48 cmd_addition += ' -i ' + range_str 49 50 if self._template: 51 cmd = cmd_addition.join(re.split(r'%i' ,self._input_cmd)) 52 else: 53 cmd = self._input_cmd + cmd_addition 54 55 print cmd 56 p = subprocess.Popen(cmd, shell = True, cwd = None, 57 stdout = subprocess.PIPE, stderr = subprocess.PIPE, env = None) 58 if self._timeout != -1: 59 signal.signal(signal.SIGALRM, timeout_handler) 60 signal.alarm(self._timeout) 61 62 try: 63 _, _ = p.communicate() 64 if self._timeout != -1: 65 signal.alarm(0) 66 except: 67 try: 68 os.kill(p.pid, signal.SIGKILL) 69 except OSError: 70 pass 71 print 'Timeout' 72 return -9 73 print '===Return Code===: ' + str(p.returncode) 74 print '===Remaining Steps (approx)===: ' \ 75 + str(self.estimate(included_ranges)) 76 return p.returncode 77 78def flatten(tree): 79 if isinstance(tree, list): 80 result = [] 81 for node in tree: 82 result.extend(flatten(node)) 83 return result 84 else: 85 return [tree] # leaf 86 87def find_failures(runner, current_interval, include_ranges, find_all): 88 if current_interval[0] == current_interval[1]: 89 return [] 90 mid = (current_interval[0] + current_interval[1]) / 2 91 92 first_half = (current_interval[0], mid) 93 second_half = (mid, current_interval[1]) 94 95 exit_code_2 = 0 96 97 exit_code_1 = runner.Run([first_half] + include_ranges) 98 if find_all or exit_code_1 == 0: 99 exit_code_2 = runner.Run([second_half] + include_ranges) 100 101 if exit_code_1 == 0 and exit_code_2 == 0: 102 # Whole range fails but both halves pass 103 # So, some conjunction of functions cause a failure, but none individually. 104 partial_result = flatten(find_failures(runner, first_half, [second_half] 105 + include_ranges, find_all)) 106 # Heavy list concatenation, but this is insignificant compared to the 107 # process run times 108 partial_result.extend(flatten(find_failures(runner, second_half, 109 partial_result + include_ranges, find_all))) 110 return [partial_result] 111 else: 112 result = [] 113 if exit_code_1 != 0: 114 if first_half[1] == first_half[0] + 1: 115 result.append(first_half[0]) 116 else: 117 result.extend(find_failures(runner, first_half, 118 include_ranges, find_all)) 119 if exit_code_2 != 0: 120 if second_half[1] == second_half[0] + 1: 121 result.append(second_half[0]) 122 else: 123 result.extend(find_failures(runner, second_half, 124 include_ranges, find_all)) 125 return result 126 127 128def main(): 129 ''' 130 Helper Script for Automating Bisection Debugging 131 132 Example Invocation: 133 bisection-tool.py --cmd 'bisection-test.py -c 2x3' --end 1000 --timeout 60 134 135 This will invoke 'bisection-test.py -c 2x3' starting with the range -i 0:1000 136 If that fails, it will subdivide the range (initially 0:500 and 500:1000) 137 recursively to pinpoint a combination of singletons that are needed to cause 138 the input to return a non zero exit code or timeout. 139 140 For investigating an error in the generated code: 141 bisection-tool.py --cmd './pydir/szbuild_spec2k.py --run 188.ammp' 142 143 For Subzero itself crashing, 144 bisection-tool.py --cmd 'pnacl-sz -translate-only=' --comma-join=1 145 The --comma-join flag ensures the ranges are formatted in the manner pnacl-sz 146 expects. 147 148 If the range specification is not to be appended on the input: 149 bisection-tool.py --cmd 'echo %i; cmd-main %i; cmd-post' --template=1 150 151 ''' 152 argparser = argparse.ArgumentParser(main.__doc__) 153 argparser.add_argument('--cmd', required=True, dest='cmd', 154 help='Runnable command') 155 156 argparser.add_argument('--start', dest='start', default=0, 157 help='Start of initial range') 158 159 argparser.add_argument('--end', dest='end', default=50000, 160 help='End of initial range') 161 162 argparser.add_argument('--timeout', dest='timeout', default=60, 163 help='Timeout for each invocation of the input') 164 165 argparser.add_argument('--all', type=int, choices=[0,1], default=1, 166 dest='all', help='Find all failures') 167 168 argparser.add_argument('--comma-join', type=int, choices=[0,1], default=0, 169 dest='comma_join', help='Use comma to join ranges') 170 171 argparser.add_argument('--template', type=int, choices=[0,1], default=0, 172 dest='template', 173 help='Replace %%i in the cmd string with the ranges') 174 175 176 args = argparser.parse_args() 177 178 fail_list = [] 179 180 initial_range = (int(args.start), int(args.end)) 181 timeout = int(args.timeout) 182 runner = Runner(args.cmd, timeout, args.comma_join, args.template, args.all) 183 if runner.Run([initial_range]) != 0: 184 fail_list = find_failures(runner, initial_range, [], args.all) 185 else: 186 print 'Pass' 187 # The whole input range works, maybe check subzero build flags? 188 # Also consider widening the initial range (control with --start and --end) 189 190 if fail_list: 191 print 'Failing Items:' 192 for fail in fail_list: 193 if isinstance(fail, list): 194 fail.sort() 195 print '[' + ','.join(str(x) for x in fail) + ']' 196 else: 197 print fail 198 print 'Number of tries: ' + str(runner._num_tries) 199 200if __name__ == '__main__': 201 main() 202