1 #!/usr/bin/env python2 2 3 # Copyright 2018 The Chromium OS Authors. All rights reserved. 4 # Use of this source code is governed by a BSD-style license that can be 5 # found in the LICENSE file. 6 """Module of binary serch for perforce.""" 7 from __future__ import print_function 8 9 import math 10 import argparse 11 import os 12 import re 13 import sys 14 import tempfile 15 16 from cros_utils import command_executer 17 from cros_utils import logger 18 19 verbose = True 20 21 22 def _GetP4ClientSpec(client_name, p4_paths): 23 p4_string = '' 24 for p4_path in p4_paths: 25 if ' ' not in p4_path: 26 p4_string += ' -a %s' % p4_path 27 else: 28 p4_string += " -a \"" + (' //' + client_name + '/').join(p4_path) + "\"" 29 30 return p4_string 31 32 33 def GetP4Command(client_name, p4_port, p4_paths, checkoutdir, p4_snapshot=''): 34 command = '' 35 36 if p4_snapshot: 37 command += 'mkdir -p ' + checkoutdir 38 for p4_path in p4_paths: 39 real_path = p4_path[1] 40 if real_path.endswith('...'): 41 real_path = real_path.replace('/...', '') 42 command += ( 43 '; mkdir -p ' + checkoutdir + '/' + os.path.dirname(real_path)) 44 command += ('&& rsync -lr ' + p4_snapshot + '/' + real_path + ' ' + 45 checkoutdir + '/' + os.path.dirname(real_path)) 46 return command 47 48 command += ' export P4CONFIG=.p4config' 49 command += ' && mkdir -p ' + checkoutdir 50 command += ' && cd ' + checkoutdir 51 command += ' && cp ${HOME}/.p4config .' 52 command += ' && chmod u+w .p4config' 53 command += " && echo \"P4PORT=" + p4_port + "\" >> .p4config" 54 command += " && echo \"P4CLIENT=" + client_name + "\" >> .p4config" 55 command += (' && g4 client ' + _GetP4ClientSpec(client_name, p4_paths)) 56 command += ' && g4 sync ' 57 command += ' && cd -' 58 return command 59 60 61 class BinarySearchPoint(object): 62 """Class of binary search point.""" 63 64 def __init__(self, revision, status, tag=None): 65 self.revision = revision 66 self.status = status 67 self.tag = tag 68 69 70 class BinarySearcherForPass(object): 71 """Class of pass level binary searcher.""" 72 73 def __init__(self, logger_to_set=None): 74 self.current = 0 75 self.lo = 0 76 self.hi = 0 77 self.total = 0 78 if logger_to_set is not None: 79 self.logger = logger_to_set 80 else: 81 self.logger = logger.GetLogger() 82 83 def GetNext(self): 84 # For the first run, update self.hi with total pass/transformation count 85 if self.hi == 0: 86 self.hi = self.total 87 self.current = (self.hi + self.lo) / 2 88 message = ('Bisecting between: (%d, %d)' % (self.lo, self.hi)) 89 self.logger.LogOutput(message, print_to_console=verbose) 90 message = ('Current limit number: %d' % self.current) 91 self.logger.LogOutput(message, print_to_console=verbose) 92 return self.current 93 94 def SetStatus(self, status): 95 """Set lo/hi status based on test script result 96 97 If status == 0, it means that runtime error is not introduced until current 98 pass/transformation, so we need to increase lower bound for binary search. 99 100 If status == 1, it means that runtime error still happens with current pass/ 101 transformation, so we need to decrease upper bound for binary search. 102 103 Return: 104 True if we find the bad pass/transformation, or cannot find bad one after 105 decreasing to the first pass/transformation. Otherwise False. 106 """ 107 assert status == 0 or status == 1 or status == 125 108 109 if self.current == 0: 110 message = ('Runtime error occurs before first pass/transformation. ' 111 'Stop binary searching.') 112 self.logger.LogOutput(message, print_to_console=verbose) 113 return True 114 115 if status == 0: 116 message = ('Runtime error is not reproduced, increasing lower bound.') 117 self.logger.LogOutput(message, print_to_console=verbose) 118 self.lo = self.current + 1 119 elif status == 1: 120 message = ('Runtime error is reproduced, decreasing upper bound..') 121 self.logger.LogOutput(message, print_to_console=verbose) 122 self.hi = self.current 123 124 if self.lo >= self.hi: 125 return True 126 127 return False 128 129 130 class BinarySearcher(object): 131 """Class of binary searcher.""" 132 133 def __init__(self, logger_to_set=None): 134 self.sorted_list = [] 135 self.index_log = [] 136 self.status_log = [] 137 self.skipped_indices = [] 138 self.current = 0 139 self.points = {} 140 self.lo = 0 141 self.hi = 0 142 if logger_to_set is not None: 143 self.logger = logger_to_set 144 else: 145 self.logger = logger.GetLogger() 146 147 def SetSortedList(self, sorted_list): 148 assert len(sorted_list) > 0 149 self.sorted_list = sorted_list 150 self.index_log = [] 151 self.hi = len(sorted_list) - 1 152 self.lo = 0 153 self.points = {} 154 for i in range(len(self.sorted_list)): 155 bsp = BinarySearchPoint(self.sorted_list[i], -1, 'Not yet done.') 156 self.points[i] = bsp 157 158 def SetStatus(self, status, tag=None): 159 message = ('Revision: %s index: %d returned: %d' % 160 (self.sorted_list[self.current], self.current, status)) 161 self.logger.LogOutput(message, print_to_console=verbose) 162 assert status == 0 or status == 1 or status == 125 163 self.index_log.append(self.current) 164 self.status_log.append(status) 165 bsp = BinarySearchPoint(self.sorted_list[self.current], status, tag) 166 self.points[self.current] = bsp 167 168 if status == 125: 169 self.skipped_indices.append(self.current) 170 171 if status == 0 or status == 1: 172 if status == 0: 173 self.lo = self.current + 1 174 elif status == 1: 175 self.hi = self.current 176 self.logger.LogOutput('lo: %d hi: %d\n' % (self.lo, self.hi)) 177 self.current = (self.lo + self.hi) / 2 178 179 if self.lo == self.hi: 180 message = ('Search complete. First bad version: %s' 181 ' at index: %d' % (self.sorted_list[self.current], self.lo)) 182 self.logger.LogOutput(message) 183 return True 184 185 for index in range(self.lo, self.hi): 186 if index not in self.skipped_indices: 187 return False 188 self.logger.LogOutput( 189 'All skipped indices between: %d and %d\n' % (self.lo, self.hi), 190 print_to_console=verbose) 191 return True 192 193 # Does a better job with chromeos flakiness. 194 def GetNextFlakyBinary(self): 195 t = (self.lo, self.current, self.hi) 196 q = [t] 197 while len(q): 198 element = q.pop(0) 199 if element[1] in self.skipped_indices: 200 # Go top 201 to_add = (element[0], (element[0] + element[1]) / 2, element[1]) 202 q.append(to_add) 203 # Go bottom 204 to_add = (element[1], (element[1] + element[2]) / 2, element[2]) 205 q.append(to_add) 206 else: 207 self.current = element[1] 208 return 209 assert len(q), 'Queue should never be 0-size!' 210 211 def GetNextFlakyLinear(self): 212 current_hi = self.current 213 current_lo = self.current 214 while True: 215 if current_hi < self.hi and current_hi not in self.skipped_indices: 216 self.current = current_hi 217 break 218 if current_lo >= self.lo and current_lo not in self.skipped_indices: 219 self.current = current_lo 220 break 221 if current_lo < self.lo and current_hi >= self.hi: 222 break 223 224 current_hi += 1 225 current_lo -= 1 226 227 def GetNext(self): 228 self.current = (self.hi + self.lo) / 2 229 # Try going forward if current is skipped. 230 if self.current in self.skipped_indices: 231 self.GetNextFlakyBinary() 232 233 # TODO: Add an estimated time remaining as well. 234 message = ('Estimated tries: min: %d max: %d\n' % (1 + math.log( 235 self.hi - self.lo, 2), self.hi - self.lo - len(self.skipped_indices))) 236 self.logger.LogOutput(message, print_to_console=verbose) 237 message = ('lo: %d hi: %d current: %d version: %s\n' % 238 (self.lo, self.hi, self.current, self.sorted_list[self.current])) 239 self.logger.LogOutput(message, print_to_console=verbose) 240 self.logger.LogOutput(str(self), print_to_console=verbose) 241 return self.sorted_list[self.current] 242 243 def SetLoRevision(self, lo_revision): 244 self.lo = self.sorted_list.index(lo_revision) 245 246 def SetHiRevision(self, hi_revision): 247 self.hi = self.sorted_list.index(hi_revision) 248 249 def GetAllPoints(self): 250 to_return = '' 251 for i in range(len(self.sorted_list)): 252 to_return += ( 253 '%d %d %s\n' % (self.points[i].status, i, self.points[i].revision)) 254 255 return to_return 256 257 def __str__(self): 258 to_return = '' 259 to_return += 'Current: %d\n' % self.current 260 to_return += str(self.index_log) + '\n' 261 revision_log = [] 262 for index in self.index_log: 263 revision_log.append(self.sorted_list[index]) 264 to_return += str(revision_log) + '\n' 265 to_return += str(self.status_log) + '\n' 266 to_return += 'Skipped indices:\n' 267 to_return += str(self.skipped_indices) + '\n' 268 to_return += self.GetAllPoints() 269 return to_return 270 271 272 class RevisionInfo(object): 273 """Class of reversion info.""" 274 275 def __init__(self, date, client, description): 276 self.date = date 277 self.client = client 278 self.description = description 279 self.status = -1 280 281 282 class VCSBinarySearcher(object): 283 """Class of VCS binary searcher.""" 284 285 def __init__(self): 286 self.bs = BinarySearcher() 287 self.rim = {} 288 self.current_ce = None 289 self.checkout_dir = None 290 self.current_revision = None 291 292 def Initialize(self): 293 pass 294 295 def GetNextRevision(self): 296 pass 297 298 def CheckoutRevision(self, revision): 299 pass 300 301 def SetStatus(self, status): 302 pass 303 304 def Cleanup(self): 305 pass 306 307 def SetGoodRevision(self, revision): 308 if revision is None: 309 return 310 assert revision in self.bs.sorted_list 311 self.bs.SetLoRevision(revision) 312 313 def SetBadRevision(self, revision): 314 if revision is None: 315 return 316 assert revision in self.bs.sorted_list 317 self.bs.SetHiRevision(revision) 318 319 320 class P4BinarySearcher(VCSBinarySearcher): 321 """Class of P4 binary searcher.""" 322 323 def __init__(self, p4_port, p4_paths, test_command): 324 VCSBinarySearcher.__init__(self) 325 self.p4_port = p4_port 326 self.p4_paths = p4_paths 327 self.test_command = test_command 328 self.checkout_dir = tempfile.mkdtemp() 329 self.ce = command_executer.GetCommandExecuter() 330 self.client_name = 'binary-searcher-$HOSTNAME-$USER' 331 self.job_log_root = '/home/asharif/www/coreboot_triage/' 332 self.changes = None 333 334 def Initialize(self): 335 self.Cleanup() 336 command = GetP4Command(self.client_name, self.p4_port, self.p4_paths, 1, 337 self.checkout_dir) 338 self.ce.RunCommand(command) 339 command = 'cd %s && g4 changes ...' % self.checkout_dir 340 _, out, _ = self.ce.RunCommandWOutput(command) 341 self.changes = re.findall(r'Change (\d+)', out) 342 change_infos = re.findall( 343 r'Change (\d+) on ([\d/]+) by ' 344 r"([^\s]+) ('[^']*')", out) 345 for change_info in change_infos: 346 ri = RevisionInfo(change_info[1], change_info[2], change_info[3]) 347 self.rim[change_info[0]] = ri 348 # g4 gives changes in reverse chronological order. 349 self.changes.reverse() 350 self.bs.SetSortedList(self.changes) 351 352 def SetStatus(self, status): 353 self.rim[self.current_revision].status = status 354 return self.bs.SetStatus(status) 355 356 def GetNextRevision(self): 357 next_revision = self.bs.GetNext() 358 self.current_revision = next_revision 359 return next_revision 360 361 def CleanupCLs(self): 362 if not os.path.isfile(self.checkout_dir + '/.p4config'): 363 command = 'cd %s' % self.checkout_dir 364 command += ' && cp ${HOME}/.p4config .' 365 command += " && echo \"P4PORT=" + self.p4_port + "\" >> .p4config" 366 command += " && echo \"P4CLIENT=" + self.client_name + "\" >> .p4config" 367 self.ce.RunCommand(command) 368 command = 'cd %s' % self.checkout_dir 369 command += '; g4 changes -c %s' % self.client_name 370 _, out, _ = self.ce.RunCommandWOUTPUOT(command) 371 changes = re.findall(r'Change (\d+)', out) 372 if len(changes) != 0: 373 command = 'cd %s' % self.checkout_dir 374 for change in changes: 375 command += '; g4 revert -c %s' % change 376 self.ce.RunCommand(command) 377 378 def CleanupClient(self): 379 command = 'cd %s' % self.checkout_dir 380 command += '; g4 revert ...' 381 command += '; g4 client -d %s' % self.client_name 382 self.ce.RunCommand(command) 383 384 def Cleanup(self): 385 self.CleanupCLs() 386 self.CleanupClient() 387 388 def __str__(self): 389 to_return = '' 390 for change in self.changes: 391 ri = self.rim[change] 392 if ri.status == -1: 393 to_return = '%s\t%d\n' % (change, ri.status) 394 else: 395 to_return += ('%s\t%d\t%s\t%s\t%s\t%s\t%s\t%s\n' % 396 (change, ri.status, ri.date, ri.client, ri.description, 397 self.job_log_root + change + '.cmd', self.job_log_root + 398 change + '.out', self.job_log_root + change + '.err')) 399 return to_return 400 401 402 class P4GCCBinarySearcher(P4BinarySearcher): 403 """Class of P4 gcc binary searcher.""" 404 405 # TODO: eventually get these patches from g4 instead of creating them manually 406 def HandleBrokenCLs(self, current_revision): 407 cr = int(current_revision) 408 problematic_ranges = [] 409 problematic_ranges.append([44528, 44539]) 410 problematic_ranges.append([44528, 44760]) 411 problematic_ranges.append([44335, 44882]) 412 command = 'pwd' 413 for pr in problematic_ranges: 414 if cr in range(pr[0], pr[1]): 415 patch_file = '/home/asharif/triage_tool/%d-%d.patch' % (pr[0], pr[1]) 416 f = open(patch_file) 417 patch = f.read() 418 f.close() 419 files = re.findall('--- (//.*)', patch) 420 command += '; cd %s' % self.checkout_dir 421 for f in files: 422 command += '; g4 open %s' % f 423 command += '; patch -p2 < %s' % patch_file 424 self.current_ce.RunCommand(command) 425 426 def CheckoutRevision(self, current_revision): 427 job_logger = logger.Logger( 428 self.job_log_root, current_revision, True, subdir='') 429 self.current_ce = command_executer.GetCommandExecuter(job_logger) 430 431 self.CleanupCLs() 432 # Change the revision of only the gcc part of the toolchain. 433 command = ( 434 'cd %s/gcctools/google_vendor_src_branch/gcc ' 435 '&& g4 revert ...; g4 sync @%s' % (self.checkout_dir, current_revision)) 436 self.current_ce.RunCommand(command) 437 438 self.HandleBrokenCLs(current_revision) 439 440 441 def Main(argv): 442 """The main function.""" 443 # Common initializations 444 ### command_executer.InitCommandExecuter(True) 445 ce = command_executer.GetCommandExecuter() 446 447 parser = argparse.ArgumentParser() 448 parser.add_argument( 449 '-n', 450 '--num_tries', 451 dest='num_tries', 452 default='100', 453 help='Number of tries.') 454 parser.add_argument( 455 '-g', 456 '--good_revision', 457 dest='good_revision', 458 help='Last known good revision.') 459 parser.add_argument( 460 '-b', 461 '--bad_revision', 462 dest='bad_revision', 463 help='Last known bad revision.') 464 parser.add_argument( 465 '-s', '--script', dest='script', help='Script to run for every version.') 466 options = parser.parse_args(argv) 467 # First get all revisions 468 p4_paths = [ 469 '//depot2/gcctools/google_vendor_src_branch/gcc/gcc-4.4.3/...', 470 '//depot2/gcctools/google_vendor_src_branch/binutils/' 471 'binutils-2.20.1-mobile/...', 472 '//depot2/gcctools/google_vendor_src_branch/' 473 'binutils/binutils-20100303/...' 474 ] 475 p4gccbs = P4GCCBinarySearcher('perforce2:2666', p4_paths, '') 476 477 # Main loop: 478 terminated = False 479 num_tries = int(options.num_tries) 480 script = os.path.expanduser(options.script) 481 482 try: 483 p4gccbs.Initialize() 484 p4gccbs.SetGoodRevision(options.good_revision) 485 p4gccbs.SetBadRevision(options.bad_revision) 486 while not terminated and num_tries > 0: 487 current_revision = p4gccbs.GetNextRevision() 488 489 # Now run command to get the status 490 ce = command_executer.GetCommandExecuter() 491 command = '%s %s' % (script, p4gccbs.checkout_dir) 492 status = ce.RunCommand(command) 493 message = ( 494 'Revision: %s produced: %d status\n' % (current_revision, status)) 495 logger.GetLogger().LogOutput(message, print_to_console=verbose) 496 terminated = p4gccbs.SetStatus(status) 497 num_tries -= 1 498 logger.GetLogger().LogOutput(str(p4gccbs), print_to_console=verbose) 499 500 if not terminated: 501 logger.GetLogger().LogOutput( 502 'Tries: %d expired.' % num_tries, print_to_console=verbose) 503 logger.GetLogger().LogOutput(str(p4gccbs.bs), print_to_console=verbose) 504 except (KeyboardInterrupt, SystemExit): 505 logger.GetLogger().LogOutput('Cleaning up...') 506 finally: 507 logger.GetLogger().LogOutput(str(p4gccbs.bs), print_to_console=verbose) 508 status = p4gccbs.Cleanup() 509 510 511 if __name__ == '__main__': 512 Main(sys.argv[1:]) 513