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"""The binary search wrapper.""" 8 9 10import argparse 11import contextlib 12import errno 13import math 14import os 15import pickle 16import re 17import shutil 18import sys 19import tempfile 20import time 21 22# Adds cros_utils to PYTHONPATH 23from binary_search_tool import binary_search_perforce 24from binary_search_tool import common 25from binary_search_tool import pass_mapping 26 27# Now we do import from cros_utils 28from cros_utils import command_executer 29from cros_utils import logger 30 31 32GOOD_SET_VAR = "BISECT_GOOD_SET" 33BAD_SET_VAR = "BISECT_BAD_SET" 34 35STATE_FILE = "%s.state" % sys.argv[0] 36HIDDEN_STATE_FILE = os.path.join( 37 os.path.dirname(STATE_FILE), ".%s" % os.path.basename(STATE_FILE) 38) 39 40 41@contextlib.contextmanager 42def SetFile(env_var, items): 43 """Generate set files that can be used by switch/test scripts. 44 45 Generate temporary set file (good/bad) holding contents of good/bad items for 46 the current binary search iteration. Store the name of each file as an 47 environment variable so all child processes can access it. 48 49 This function is a contextmanager, meaning it's meant to be used with the 50 "with" statement in Python. This is so cleanup and setup happens automatically 51 and cleanly. Execution of the outer "with" statement happens at the "yield" 52 statement. 53 54 Args: 55 env_var: What environment variable to store the file name in. 56 items: What items are in this set. 57 """ 58 with tempfile.NamedTemporaryFile("w", encoding="utf-8") as f: 59 os.environ[env_var] = f.name 60 f.write("\n".join(items)) 61 f.flush() 62 yield 63 64 65class BinarySearchState(object): 66 """The binary search state class.""" 67 68 def __init__( 69 self, 70 get_initial_items, 71 switch_to_good, 72 switch_to_bad, 73 test_setup_script, 74 test_script, 75 incremental, 76 prune, 77 pass_bisect, 78 ir_diff, 79 iterations, 80 prune_iterations, 81 verify, 82 file_args, 83 verbose, 84 ): 85 """BinarySearchState constructor, see Run for full args documentation.""" 86 self.get_initial_items = get_initial_items 87 self.switch_to_good = switch_to_good 88 self.switch_to_bad = switch_to_bad 89 self.test_setup_script = test_setup_script 90 self.test_script = test_script 91 self.incremental = incremental 92 self.prune = prune 93 self.pass_bisect = pass_bisect 94 self.ir_diff = ir_diff 95 self.iterations = iterations 96 self.prune_iterations = prune_iterations 97 self.verify = verify 98 self.file_args = file_args 99 self.verbose = verbose 100 101 self.l = logger.GetLogger() 102 self.ce = command_executer.GetCommandExecuter() 103 104 self.resumed = False 105 self.prune_cycles = 0 106 self.search_cycles = 0 107 self.binary_search = None 108 self.all_items = None 109 self.cmd_script = None 110 self.mode = None 111 self.PopulateItemsUsingCommand(self.get_initial_items) 112 self.currently_good_items = set() 113 self.currently_bad_items = set() 114 self.found_items = set() 115 self.known_good = set() 116 117 self.start_time = time.time() 118 119 def SwitchToGood(self, item_list): 120 """Switch given items to "good" set.""" 121 if self.incremental: 122 self.l.LogOutput( 123 "Incremental set. Wanted to switch %s to good" % str(item_list), 124 print_to_console=self.verbose, 125 ) 126 incremental_items = [ 127 item 128 for item in item_list 129 if item not in self.currently_good_items 130 ] 131 item_list = incremental_items 132 self.l.LogOutput( 133 "Incremental set. Actually switching %s to good" 134 % str(item_list), 135 print_to_console=self.verbose, 136 ) 137 138 if not item_list: 139 return 140 141 self.l.LogOutput( 142 "Switching %s to good" % str(item_list), 143 print_to_console=self.verbose, 144 ) 145 self.RunSwitchScript(self.switch_to_good, item_list) 146 self.currently_good_items = self.currently_good_items.union( 147 set(item_list) 148 ) 149 self.currently_bad_items.difference_update(set(item_list)) 150 151 def SwitchToBad(self, item_list): 152 """Switch given items to "bad" set.""" 153 if self.incremental: 154 self.l.LogOutput( 155 "Incremental set. Wanted to switch %s to bad" % str(item_list), 156 print_to_console=self.verbose, 157 ) 158 incremental_items = [ 159 item 160 for item in item_list 161 if item not in self.currently_bad_items 162 ] 163 item_list = incremental_items 164 self.l.LogOutput( 165 "Incremental set. Actually switching %s to bad" 166 % str(item_list), 167 print_to_console=self.verbose, 168 ) 169 170 if not item_list: 171 return 172 173 self.l.LogOutput( 174 "Switching %s to bad" % str(item_list), 175 print_to_console=self.verbose, 176 ) 177 self.RunSwitchScript(self.switch_to_bad, item_list) 178 self.currently_bad_items = self.currently_bad_items.union( 179 set(item_list) 180 ) 181 self.currently_good_items.difference_update(set(item_list)) 182 183 def RunSwitchScript(self, switch_script, item_list): 184 """Pass given items to switch script. 185 186 Args: 187 switch_script: path to switch script 188 item_list: list of all items to be switched 189 """ 190 if self.file_args: 191 with tempfile.NamedTemporaryFile("w", encoding="utf-8") as f: 192 f.write("\n".join(item_list)) 193 f.flush() 194 command = "%s %s" % (switch_script, f.name) 195 ret, _, _ = self.ce.RunCommandWExceptionCleanup( 196 command, print_to_console=self.verbose 197 ) 198 else: 199 command = "%s %s" % (switch_script, " ".join(item_list)) 200 try: 201 ret, _, _ = self.ce.RunCommandWExceptionCleanup( 202 command, print_to_console=self.verbose 203 ) 204 except OSError as e: 205 if e.errno == errno.E2BIG: 206 raise RuntimeError( 207 "Too many arguments for switch script! Use " 208 "--file_args" 209 ) 210 assert ret == 0, "Switch script %s returned %d" % (switch_script, ret) 211 212 def TestScript(self): 213 """Run test script and return exit code from script.""" 214 command = self.test_script 215 ret, _, _ = self.ce.RunCommandWExceptionCleanup(command) 216 return ret 217 218 def TestSetupScript(self): 219 """Run test setup script and return exit code from script.""" 220 if not self.test_setup_script: 221 return 0 222 223 command = self.test_setup_script 224 ret, _, _ = self.ce.RunCommandWExceptionCleanup(command) 225 return ret 226 227 def GenerateBadCommandScript(self, bad_items): 228 """Generate command line script for building bad item.""" 229 assert not self.prune, "Prune must be false if pass_bisect is set." 230 assert len(bad_items) == 1, ( 231 "Pruning is off, but number of bad " "items found was not 1." 232 ) 233 item = list(bad_items)[0] 234 command = "%s %s" % (self.pass_bisect, item) 235 ret, _, _ = self.ce.RunCommandWExceptionCleanup( 236 command, print_to_console=self.verbose 237 ) 238 return ret 239 240 def DoVerify(self): 241 """Verify correctness of test environment. 242 243 Verify that a "good" set of items produces a "good" result and that a "bad" 244 set of items produces a "bad" result. To be run directly before running 245 DoSearch. If verify is False this step is skipped. 246 """ 247 if not self.verify: 248 return 249 250 self.l.LogOutput("VERIFICATION") 251 self.l.LogOutput("Beginning tests to verify good/bad sets\n") 252 253 self._OutputProgress("Verifying items from GOOD set\n") 254 with SetFile(GOOD_SET_VAR, self.all_items), SetFile(BAD_SET_VAR, []): 255 self.l.LogOutput("Resetting all items to good to verify.") 256 self.SwitchToGood(self.all_items) 257 status = self.TestSetupScript() 258 assert status == 0, "When reset_to_good, test setup should succeed." 259 status = self.TestScript() 260 assert status == 0, "When reset_to_good, status should be 0." 261 262 self._OutputProgress("Verifying items from BAD set\n") 263 with SetFile(GOOD_SET_VAR, []), SetFile(BAD_SET_VAR, self.all_items): 264 self.l.LogOutput("Resetting all items to bad to verify.") 265 self.SwitchToBad(self.all_items) 266 status = self.TestSetupScript() 267 # The following assumption is not true; a bad image might not 268 # successfully push onto a device. 269 # assert status == 0, 'When reset_to_bad, test setup should succeed.' 270 if status == 0: 271 status = self.TestScript() 272 assert status == 1, "When reset_to_bad, status should be 1." 273 274 def DoSearchBadItems(self): 275 """Perform full search for bad items. 276 277 Perform full search until prune_iterations number of bad items are found. 278 """ 279 while ( 280 True 281 and len(self.all_items) > 1 282 and self.prune_cycles < self.prune_iterations 283 ): 284 terminated = self.DoBinarySearchBadItems() 285 self.prune_cycles += 1 286 if not terminated: 287 break 288 # Prune is set. 289 prune_index = self.binary_search.current 290 291 # If found item is last item, no new items can be found 292 if prune_index == len(self.all_items) - 1: 293 self.l.LogOutput("First bad item is the last item. Breaking.") 294 self.l.LogOutput("Bad items are: %s" % self.all_items[-1]) 295 self.found_items.add(self.all_items[-1]) 296 break 297 298 # If already seen item we have no new bad items to find, finish up 299 if self.all_items[prune_index] in self.found_items: 300 self.l.LogOutput( 301 "Found item already found before: %s." 302 % self.all_items[prune_index], 303 print_to_console=self.verbose, 304 ) 305 self.l.LogOutput("No more bad items remaining. Done searching.") 306 self.l.LogOutput( 307 "Bad items are: %s" % " ".join(self.found_items) 308 ) 309 break 310 311 new_all_items = list(self.all_items) 312 # Move prune item to the end of the list. 313 new_all_items.append(new_all_items.pop(prune_index)) 314 self.found_items.add(new_all_items[-1]) 315 316 # Everything below newly found bad item is now known to be a good item. 317 # Take these good items out of the equation to save time on the next 318 # search. We save these known good items so they are still sent to the 319 # switch_to_good script. 320 if prune_index: 321 self.known_good.update(new_all_items[:prune_index]) 322 new_all_items = new_all_items[prune_index:] 323 324 self.l.LogOutput( 325 "Old list: %s. New list: %s" 326 % (str(self.all_items), str(new_all_items)), 327 print_to_console=self.verbose, 328 ) 329 330 if not self.prune: 331 self.l.LogOutput("Not continuning further, --prune is not set") 332 break 333 # FIXME: Do we need to Convert the currently good items to bad 334 self.PopulateItemsUsingList(new_all_items) 335 336 # If pass level bisecting is set, generate a script which contains command 337 # line options to rebuild bad item. 338 if self.pass_bisect: 339 status = self.GenerateBadCommandScript(self.found_items) 340 if status == 0: 341 self.cmd_script = os.path.join( 342 os.path.dirname(self.pass_bisect), "cmd_script.sh" 343 ) 344 self.l.LogOutput( 345 "Command script generated at %s." % self.cmd_script 346 ) 347 else: 348 raise RuntimeError("Error while generating command script.") 349 350 def DoBinarySearchBadItems(self): 351 """Perform single iteration of binary search.""" 352 # If in resume mode don't reset search_cycles 353 if not self.resumed: 354 self.search_cycles = 0 355 else: 356 self.resumed = False 357 358 terminated = False 359 while self.search_cycles < self.iterations and not terminated: 360 self.SaveState() 361 self.OutputIterationProgressBadItem() 362 363 self.search_cycles += 1 364 [bad_items, good_items] = self.GetNextItems() 365 366 with SetFile(GOOD_SET_VAR, good_items), SetFile( 367 BAD_SET_VAR, bad_items 368 ): 369 # TODO: bad_items should come first. 370 self.SwitchToGood(good_items) 371 self.SwitchToBad(bad_items) 372 status = self.TestSetupScript() 373 if status == 0: 374 status = self.TestScript() 375 terminated = self.binary_search.SetStatus(status) 376 377 if terminated: 378 self.l.LogOutput("Terminated!", print_to_console=self.verbose) 379 if not terminated: 380 self.l.LogOutput("Ran out of iterations searching...") 381 self.l.LogOutput(str(self), print_to_console=self.verbose) 382 return terminated 383 384 def CollectPassName(self, pass_info): 385 """Mapping opt-bisect output of pass info to debugcounter name.""" 386 self.l.LogOutput( 387 "Pass info: %s" % pass_info, print_to_console=self.verbose 388 ) 389 390 for desc in pass_mapping.pass_name: 391 if desc in pass_info: 392 return pass_mapping.pass_name[desc] 393 394 # If pass not found, return None 395 return None 396 397 def BuildWithPassLimit(self, limit, generate_ir=False): 398 """Rebuild bad item with pass level bisect limit 399 400 Run command line script generated by GenerateBadCommandScript(), with 401 pass level limit flags. 402 403 Returns: 404 pass_num: current number of the pass, or total number of passes if 405 limit set to -1. 406 pass_name: The debugcounter name of current limit pass. 407 """ 408 os.environ["LIMIT_FLAGS"] = "-mllvm -opt-bisect-limit=" + str(limit) 409 if generate_ir: 410 os.environ["LIMIT_FLAGS"] += " -S -emit-llvm" 411 self.l.LogOutput( 412 "Limit flags: %s" % os.environ["LIMIT_FLAGS"], 413 print_to_console=self.verbose, 414 ) 415 command = self.cmd_script 416 _, _, msg = self.ce.RunCommandWOutput(command, print_to_console=False) 417 418 # Massages we get will be like this: 419 # BISECT: running pass (9) <Pass Description> on <function> (<file>) 420 # BISECT: running pass (10) <Pass Description> on <module> (<file>) 421 # BISECT: NOT running pass (11) <Pass Description> on <SCG> (<file>) 422 # BISECT: NOT running pass (12) <Pass Description> on <SCG> (<file>) 423 # We want to get the pass description of last running pass, to have 424 # transformation level bisect on it. 425 if "BISECT: " not in msg: 426 raise RuntimeError( 427 "No bisect info printed, OptBisect may not be " 428 "supported by the compiler." 429 ) 430 431 lines = msg.split("\n") 432 pass_num = 0 433 last_pass = "" 434 for l in lines: 435 if "running pass" in l: 436 # For situation of limit==-1, we want the total number of passes 437 if limit != -1 and "BISECT: NOT " in l: 438 break 439 pass_num += 1 440 last_pass = l 441 if limit not in (-1, pass_num): 442 raise ValueError( 443 "[Error] While building, limit number does not match." 444 ) 445 return pass_num, self.CollectPassName(last_pass) 446 447 def BuildWithTransformLimit( 448 self, limit, pass_name=None, pass_limit=-1, generate_ir=False 449 ): 450 """Rebuild bad item with transformation level bisect limit 451 452 Run command line script generated by GenerateBadCommandScript(), with 453 pass level limit flags and transformation level limit flags. 454 455 Args: 456 limit: transformation level limit for bad item. 457 pass_name: name of bad pass debugcounter from pass level bisect result. 458 pass_limit: pass level limit from pass level bisect result. 459 generate_ir: Whether to generate IR comparison. 460 461 Returns: 462 Total number of transformations if limit set to -1, else return 0. 463 """ 464 counter_name = pass_name 465 466 os.environ["LIMIT_FLAGS"] = ( 467 "-mllvm -opt-bisect-limit=" 468 + str(pass_limit) 469 + " -mllvm -debug-counter=" 470 + counter_name 471 + "-count=" 472 + str(limit) 473 + " -mllvm -print-debug-counter" 474 ) 475 if generate_ir: 476 os.environ["LIMIT_FLAGS"] += " -S -emit-llvm" 477 self.l.LogOutput( 478 "Limit flags: %s" % os.environ["LIMIT_FLAGS"], 479 print_to_console=self.verbose, 480 ) 481 command = self.cmd_script 482 _, _, msg = self.ce.RunCommandWOutput(command, print_to_console=False) 483 484 if "Counters and values:" not in msg: 485 # Print pass level IR diff only if transformation level bisection does 486 # not work. 487 if self.ir_diff: 488 self.PrintIRDiff(pass_limit) 489 raise RuntimeError( 490 "No bisect info printed, DebugCounter may not be " 491 "supported by the compiler." 492 ) 493 494 # With debugcounter enabled, there will be DebugCounter counting info in 495 # the output. 496 lines = msg.split("\n") 497 for l in lines: 498 if pass_name in l: 499 # Output of debugcounter will be like: 500 # instcombine-visit: {10, 0, 20} 501 # dce-transform: {1, 0, -1} 502 # which indicates {Count, Skip, StopAfter}. 503 # The last number should be the limit we set. 504 # We want the first number as the total transformation count. 505 # Split each line by ,|{|} and we can get l_list as: 506 # ['instcombine: ', '10', '0', '20', ''] 507 # and we will need the second item in it. 508 l_list = re.split(",|{|}", l) 509 count = int(l_list[1]) 510 if limit == -1: 511 return count 512 # The returned value is only useful when limit == -1, which shows total 513 # transformation count. 514 return 0 515 516 def PrintIRDiff(self, pass_index, pass_name=None, trans_index=-1): 517 bad_item = list(self.found_items)[0] 518 self.l.LogOutput( 519 "IR difference before and after bad pass/transformation:", 520 print_to_console=self.verbose, 521 ) 522 523 if trans_index == -1: 524 # Pass level IR diff 525 self.BuildWithPassLimit(pass_index, self.ir_diff) 526 good_ir = os.path.join(tempfile.tempdir, "good.s") 527 shutil.copyfile(bad_item, good_ir) 528 pass_index += 1 529 self.BuildWithPassLimit(pass_index, self.ir_diff) 530 else: 531 # Transformation level IR diff 532 self.BuildWithTransformLimit( 533 trans_index, pass_name, pass_index, self.ir_diff 534 ) 535 good_ir = os.path.join(tempfile.tempdir, "good.s") 536 shutil.copyfile(bad_item, good_ir) 537 trans_index += 1 538 self.BuildWithTransformLimit( 539 trans_index, pass_name, pass_index, self.ir_diff 540 ) 541 542 bad_ir = os.path.join(tempfile.tempdir, "bad.s") 543 shutil.copyfile(bad_item, bad_ir) 544 545 command = "diff %s %s" % (good_ir, bad_ir) 546 _, _, _ = self.ce.RunCommandWOutput( 547 command, print_to_console=self.verbose 548 ) 549 550 def DoSearchBadPass(self): 551 """Perform full search for bad pass of bad item.""" 552 logger.GetLogger().LogOutput( 553 "Starting to bisect bad pass for bad item." 554 ) 555 556 # Pass level bisection 557 self.mode = "pass" 558 self.binary_search = binary_search_perforce.BinarySearcherForPass( 559 logger_to_set=self.l 560 ) 561 self.binary_search.total, _ = self.BuildWithPassLimit(-1) 562 logger.GetLogger().LogOutput( 563 "Total %s number: %d" % (self.mode, self.binary_search.total) 564 ) 565 566 pass_index, pass_name = self.DoBinarySearchBadPass() 567 568 if not pass_name and pass_index == 0: 569 raise ValueError("Bisecting passes cannot reproduce good result.") 570 logger.GetLogger().LogOutput("Bad pass found: %s." % pass_name) 571 572 # Transformation level bisection. 573 logger.GetLogger().LogOutput( 574 "Starting to bisect at transformation level." 575 ) 576 577 self.mode = "transform" 578 self.binary_search = binary_search_perforce.BinarySearcherForPass( 579 logger_to_set=self.l 580 ) 581 self.binary_search.total = self.BuildWithTransformLimit( 582 -1, pass_name, pass_index 583 ) 584 logger.GetLogger().LogOutput( 585 "Total %s number: %d" % (self.mode, self.binary_search.total) 586 ) 587 588 trans_index, _ = self.DoBinarySearchBadPass(pass_index, pass_name) 589 if trans_index == 0: 590 raise ValueError( 591 "Bisecting %s cannot reproduce good result." % pass_name 592 ) 593 594 if self.ir_diff: 595 self.PrintIRDiff(pass_index, pass_name, trans_index) 596 597 logger.GetLogger().LogOutput( 598 "Bisection result for bad item %s:\n" 599 "Bad pass: %s at number %d\n" 600 "Bad transformation number: %d" 601 % (self.found_items, pass_name, pass_index, trans_index) 602 ) 603 604 def DoBinarySearchBadPass(self, pass_index=-1, pass_name=None): 605 """Perform single iteration of binary search at pass level 606 607 Args: 608 pass_index: Works for transformation level bisection, indicates the limit 609 number of pass from pass level bisecting result. 610 pass_name: Works for transformation level bisection, indicates 611 DebugCounter name of the bad pass from pass level bisecting 612 result. 613 614 Returns: 615 index: Index of problematic pass/transformation. 616 pass_name: Works for pass level bisection, returns DebugCounter name for 617 bad pass. 618 """ 619 # If in resume mode don't reset search_cycles 620 if not self.resumed: 621 self.search_cycles = 0 622 else: 623 self.resumed = False 624 625 terminated = False 626 index = 0 627 while self.search_cycles < self.iterations and not terminated: 628 self.SaveState() 629 self.OutputIterationProgressBadPass() 630 631 self.search_cycles += 1 632 current = self.binary_search.GetNext() 633 634 if self.mode == "pass": 635 index, pass_name = self.BuildWithPassLimit(current) 636 else: 637 self.BuildWithTransformLimit(current, pass_name, pass_index) 638 index = current 639 640 # TODO: Newly generated object should not directly replace original 641 # one, need to put it somewhere and symbol link original one to it. 642 # Will update cmd_script to do it. 643 644 status = self.TestSetupScript() 645 assert status == 0, "Test setup should succeed." 646 status = self.TestScript() 647 terminated = self.binary_search.SetStatus(status) 648 649 if terminated: 650 self.l.LogOutput("Terminated!", print_to_console=self.verbose) 651 if not terminated: 652 self.l.LogOutput("Ran out of iterations searching...") 653 self.l.LogOutput(str(self), print_to_console=self.verbose) 654 return index, pass_name 655 656 def PopulateItemsUsingCommand(self, command): 657 """Update all_items and binary search logic from executable. 658 659 This method is mainly required for enumerating the initial list of items 660 from the get_initial_items script. 661 662 Args: 663 command: path to executable that will enumerate items. 664 """ 665 ce = command_executer.GetCommandExecuter() 666 _, out, _ = ce.RunCommandWExceptionCleanup( 667 command, return_output=True, print_to_console=self.verbose 668 ) 669 all_items = out.split() 670 self.PopulateItemsUsingList(all_items) 671 672 def PopulateItemsUsingList(self, all_items): 673 """Update all_items and binary searching logic from list. 674 675 Args: 676 all_items: new list of all_items 677 """ 678 self.all_items = all_items 679 self.binary_search = binary_search_perforce.BinarySearcher( 680 logger_to_set=self.l 681 ) 682 self.binary_search.SetSortedList(self.all_items) 683 684 def SaveState(self): 685 """Save state to STATE_FILE. 686 687 SaveState will create a new unique, hidden state file to hold data from 688 object. Then atomically overwrite the STATE_FILE symlink to point to the 689 new data. 690 691 Raises: 692 OSError if STATE_FILE already exists but is not a symlink. 693 """ 694 ce, l = self.ce, self.l 695 self.ce, self.l, self.binary_search.logger = None, None, None 696 old_state = None 697 698 _, path = tempfile.mkstemp(prefix=HIDDEN_STATE_FILE, dir=".") 699 with open(path, "wb") as f: 700 pickle.dump(self, f) 701 702 if os.path.exists(STATE_FILE): 703 if os.path.islink(STATE_FILE): 704 old_state = os.readlink(STATE_FILE) 705 else: 706 raise OSError( 707 ( 708 "%s already exists and is not a symlink!\n" 709 "State file saved to %s" % (STATE_FILE, path) 710 ) 711 ) 712 713 # Create new link and atomically overwrite old link 714 temp_link = "%s.link" % HIDDEN_STATE_FILE 715 os.symlink(path, temp_link) 716 os.rename(temp_link, STATE_FILE) 717 718 if old_state: 719 os.remove(old_state) 720 721 self.ce, self.l, self.binary_search.logger = ce, l, l 722 723 @classmethod 724 def LoadState(cls): 725 """Create BinarySearchState object from STATE_FILE.""" 726 if not os.path.isfile(STATE_FILE): 727 return None 728 try: 729 with open(STATE_FILE, "rb") as f: 730 bss = pickle.load(f) 731 bss.l = logger.GetLogger() 732 bss.ce = command_executer.GetCommandExecuter() 733 bss.binary_search.logger = bss.l 734 bss.start_time = time.time() 735 736 # Set resumed to be True so we can enter DoBinarySearch without the 737 # method resetting our current search_cycles to 0. 738 bss.resumed = True 739 740 # Set currently_good_items and currently_bad_items to empty so that the 741 # first iteration after resuming will always be non-incremental. This 742 # is just in case the environment changes, the user makes manual 743 # changes, or a previous switch_script corrupted the environment. 744 bss.currently_good_items = set() 745 bss.currently_bad_items = set() 746 747 binary_search_perforce.verbose = bss.verbose 748 return bss 749 except Exception: 750 return None 751 752 def RemoveState(self): 753 """Remove STATE_FILE and its symlinked data from file system.""" 754 if os.path.exists(STATE_FILE): 755 if os.path.islink(STATE_FILE): 756 real_file = os.readlink(STATE_FILE) 757 os.remove(real_file) 758 os.remove(STATE_FILE) 759 760 def GetNextItems(self): 761 """Get next items for binary search based on result of the last test run.""" 762 border_item = self.binary_search.GetNext() 763 index = self.all_items.index(border_item) 764 765 next_bad_items = self.all_items[: index + 1] 766 next_good_items = self.all_items[index + 1 :] + list(self.known_good) 767 768 return [next_bad_items, next_good_items] 769 770 def ElapsedTimeString(self): 771 """Return h m s format of elapsed time since execution has started.""" 772 diff = int(time.time() - self.start_time) 773 seconds = diff % 60 774 minutes = (diff // 60) % 60 775 hours = diff // (60 * 60) 776 777 seconds = str(seconds).rjust(2) 778 minutes = str(minutes).rjust(2) 779 hours = str(hours).rjust(2) 780 781 return "%sh %sm %ss" % (hours, minutes, seconds) 782 783 def _OutputProgress(self, progress_text): 784 """Output current progress of binary search to console and logs. 785 786 Args: 787 progress_text: The progress to display to the user. 788 """ 789 progress = ( 790 "\n***** PROGRESS (elapsed time: %s) *****\n" 791 "%s" 792 "************************************************" 793 ) 794 progress = progress % (self.ElapsedTimeString(), progress_text) 795 self.l.LogOutput(progress) 796 797 def OutputIterationProgressBadItem(self): 798 out = ( 799 "Search %d of estimated %d.\n" 800 "Prune %d of max %d.\n" 801 "Current bad items found:\n" 802 "%s\n" 803 ) 804 out = out % ( 805 self.search_cycles + 1, 806 math.ceil(math.log(len(self.all_items), 2)), 807 self.prune_cycles + 1, 808 self.prune_iterations, 809 ", ".join(self.found_items), 810 ) 811 self._OutputProgress(out) 812 813 def OutputIterationProgressBadPass(self): 814 out = "Search %d of estimated %d.\n" "Current limit: %s\n" 815 out = out % ( 816 self.search_cycles + 1, 817 math.ceil(math.log(self.binary_search.total, 2)), 818 self.binary_search.current, 819 ) 820 self._OutputProgress(out) 821 822 def __str__(self): 823 ret = "" 824 ret += "all: %s\n" % str(self.all_items) 825 ret += "currently_good: %s\n" % str(self.currently_good_items) 826 ret += "currently_bad: %s\n" % str(self.currently_bad_items) 827 ret += str(self.binary_search) 828 return ret 829 830 831class MockBinarySearchState(BinarySearchState): 832 """Mock class for BinarySearchState.""" 833 834 def __init__(self, **kwargs): 835 # Initialize all arguments to None 836 default_kwargs = { 837 "get_initial_items": 'echo "1"', 838 "switch_to_good": None, 839 "switch_to_bad": None, 840 "test_setup_script": None, 841 "test_script": None, 842 "incremental": True, 843 "prune": False, 844 "pass_bisect": None, 845 "ir_diff": False, 846 "iterations": 50, 847 "prune_iterations": 100, 848 "verify": True, 849 "file_args": False, 850 "verbose": False, 851 } 852 default_kwargs.update(kwargs) 853 super(MockBinarySearchState, self).__init__(**default_kwargs) 854 855 856def _CanonicalizeScript(script_name): 857 """Return canonical path to script. 858 859 Args: 860 script_name: Relative or absolute path to script 861 862 Returns: 863 Canonicalized script path 864 """ 865 script_name = os.path.expanduser(script_name) 866 if not script_name.startswith("/"): 867 return os.path.join(".", script_name) 868 869 870def Run( 871 get_initial_items, 872 switch_to_good, 873 switch_to_bad, 874 test_script, 875 test_setup_script=None, 876 iterations=50, 877 prune=False, 878 pass_bisect=None, 879 ir_diff=False, 880 noincremental=False, 881 file_args=False, 882 verify=True, 883 prune_iterations=100, 884 verbose=False, 885 resume=False, 886): 887 """Run binary search tool. 888 889 Equivalent to running through terminal. 890 891 Args: 892 get_initial_items: Script to enumerate all items being binary searched 893 switch_to_good: Script that will take items as input and switch them to good 894 set 895 switch_to_bad: Script that will take items as input and switch them to bad 896 set 897 test_script: Script that will determine if the current combination of good 898 and bad items make a "good" or "bad" result. 899 test_setup_script: Script to do necessary setup (building, compilation, 900 etc.) for test_script. 901 iterations: How many binary search iterations to run before exiting. 902 prune: If False the binary search tool will stop when the first bad item is 903 found. Otherwise then binary search tool will continue searching until all 904 bad items are found (or prune_iterations is reached). 905 pass_bisect: Script that takes single bad item from POPULATE_BAD and returns 906 the compiler command used to generate the bad item. This will turn on 907 pass/ transformation level bisection for the bad item. Requires that 908 'prune' be set to False, and needs support of `-opt-bisect-limit`(pass) 909 and `-print-debug-counter`(transformation) from LLVM. 910 ir_diff: Whether to print IR differences before and after bad 911 pass/transformation to verbose output. Defaults to False, only works when 912 pass_bisect is enabled. 913 noincremental: Whether to send "diffs" of good/bad items to switch scripts. 914 file_args: If True then arguments to switch scripts will be a file name 915 containing a newline separated list of the items to switch. 916 verify: If True, run tests to ensure initial good/bad sets actually produce 917 a good/bad result. 918 prune_iterations: Max number of bad items to search for. 919 verbose: If True will print extra debug information to user. 920 resume: If True will resume using STATE_FILE. 921 922 Returns: 923 0 for success, error otherwise 924 """ 925 # Notice that all the argument checks are in the Run() function rather than 926 # in the Main() function. It is not common to do so but some wrappers are 927 # going to call Run() directly and bypass checks in Main() function. 928 if resume: 929 logger.GetLogger().LogOutput("Resuming from %s" % STATE_FILE) 930 bss = BinarySearchState.LoadState() 931 if not bss: 932 logger.GetLogger().LogOutput( 933 "%s is not a valid binary_search_tool state file, cannot resume!" 934 % STATE_FILE 935 ) 936 return 1 937 logger.GetLogger().LogOutput( 938 "Note: resuming from previous state, " 939 "ignoring given options and loading saved " 940 "options instead." 941 ) 942 else: 943 if not ( 944 get_initial_items 945 and switch_to_good 946 and switch_to_bad 947 and test_script 948 ): 949 logger.GetLogger().LogOutput( 950 "The following options are required: " "[-i, -g, -b, -t] | [-r]" 951 ) 952 return 1 953 if pass_bisect and prune: 954 logger.GetLogger().LogOutput( 955 '"--pass_bisect" only works when ' 956 '"--prune" is set to be False.' 957 ) 958 return 1 959 if not pass_bisect and ir_diff: 960 logger.GetLogger().LogOutput( 961 '"--ir_diff" only works when ' '"--pass_bisect" is enabled.' 962 ) 963 964 switch_to_good = _CanonicalizeScript(switch_to_good) 965 switch_to_bad = _CanonicalizeScript(switch_to_bad) 966 if test_setup_script: 967 test_setup_script = _CanonicalizeScript(test_setup_script) 968 if pass_bisect: 969 pass_bisect = _CanonicalizeScript(pass_bisect) 970 test_script = _CanonicalizeScript(test_script) 971 get_initial_items = _CanonicalizeScript(get_initial_items) 972 incremental = not noincremental 973 974 binary_search_perforce.verbose = verbose 975 976 bss = BinarySearchState( 977 get_initial_items, 978 switch_to_good, 979 switch_to_bad, 980 test_setup_script, 981 test_script, 982 incremental, 983 prune, 984 pass_bisect, 985 ir_diff, 986 iterations, 987 prune_iterations, 988 verify, 989 file_args, 990 verbose, 991 ) 992 bss.DoVerify() 993 994 bss.DoSearchBadItems() 995 if pass_bisect: 996 bss.DoSearchBadPass() 997 bss.RemoveState() 998 logger.GetLogger().LogOutput( 999 "Total execution time: %s" % bss.ElapsedTimeString() 1000 ) 1001 1002 return 0 1003 1004 1005def Main(argv): 1006 """The main function.""" 1007 # Common initializations 1008 1009 parser = argparse.ArgumentParser() 1010 common.BuildArgParser(parser) 1011 logger.GetLogger().LogOutput(" ".join(argv)) 1012 options = parser.parse_args(argv) 1013 1014 # Get dictionary of all options 1015 args = vars(options) 1016 return Run(**args) 1017 1018 1019if __name__ == "__main__": 1020 sys.exit(Main(sys.argv[1:])) 1021