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