| #!/usr/bin/env python3 |
| # -*- coding: utf-8 -*- |
| # Copyright 2020 The ChromiumOS Authors |
| # Use of this source code is governed by a BSD-style license that can be |
| # found in the LICENSE file. |
| |
| """Module of binary serch for perforce.""" |
| |
| import argparse |
| import math |
| import os |
| import re |
| import sys |
| import tempfile |
| |
| from cros_utils import command_executer |
| from cros_utils import logger |
| |
| |
| verbose = True |
| |
| |
| def _GetP4ClientSpec(client_name, p4_paths): |
| p4_string = "" |
| for p4_path in p4_paths: |
| if " " not in p4_path: |
| p4_string += " -a %s" % p4_path |
| else: |
| p4_string += ( |
| ' -a "' + (" //" + client_name + "/").join(p4_path) + '"' |
| ) |
| |
| return p4_string |
| |
| |
| def GetP4Command(client_name, p4_port, p4_paths, checkoutdir, p4_snapshot=""): |
| command = "" |
| |
| if p4_snapshot: |
| command += "mkdir -p " + checkoutdir |
| for p4_path in p4_paths: |
| real_path = p4_path[1] |
| if real_path.endswith("..."): |
| real_path = real_path.replace("/...", "") |
| command += ( |
| "; mkdir -p " |
| + checkoutdir |
| + "/" |
| + os.path.dirname(real_path) |
| ) |
| command += ( |
| "&& rsync -lr " |
| + p4_snapshot |
| + "/" |
| + real_path |
| + " " |
| + checkoutdir |
| + "/" |
| + os.path.dirname(real_path) |
| ) |
| return command |
| |
| command += " export P4CONFIG=.p4config" |
| command += " && mkdir -p " + checkoutdir |
| command += " && cd " + checkoutdir |
| command += " && cp ${HOME}/.p4config ." |
| command += " && chmod u+w .p4config" |
| command += ' && echo "P4PORT=' + p4_port + '" >> .p4config' |
| command += ' && echo "P4CLIENT=' + client_name + '" >> .p4config' |
| command += " && g4 client " + _GetP4ClientSpec(client_name, p4_paths) |
| command += " && g4 sync " |
| command += " && cd -" |
| return command |
| |
| |
| class BinarySearchPoint(object): |
| """Class of binary search point.""" |
| |
| def __init__(self, revision, status, tag=None): |
| self.revision = revision |
| self.status = status |
| self.tag = tag |
| |
| |
| class BinarySearcherForPass(object): |
| """Class of pass level binary searcher.""" |
| |
| def __init__(self, logger_to_set=None): |
| self.current = 0 |
| self.lo = 0 |
| self.hi = 0 |
| self.total = 0 |
| if logger_to_set is not None: |
| self.logger = logger_to_set |
| else: |
| self.logger = logger.GetLogger() |
| |
| def GetNext(self): |
| # For the first run, update self.hi with total pass/transformation count |
| if self.hi == 0: |
| self.hi = self.total |
| self.current = (self.hi + self.lo) // 2 |
| message = "Bisecting between: (%d, %d)" % (self.lo, self.hi) |
| self.logger.LogOutput(message, print_to_console=verbose) |
| message = "Current limit number: %d" % self.current |
| self.logger.LogOutput(message, print_to_console=verbose) |
| return self.current |
| |
| def SetStatus(self, status): |
| """Set lo/hi status based on test script result |
| |
| If status == 0, it means that runtime error is not introduced until current |
| pass/transformation, so we need to increase lower bound for binary search. |
| |
| If status == 1, it means that runtime error still happens with current pass/ |
| transformation, so we need to decrease upper bound for binary search. |
| |
| Returns: |
| True if we find the bad pass/transformation, or cannot find bad one after |
| decreasing to the first pass/transformation. Otherwise False. |
| """ |
| assert status in (0, 1, 125), status |
| |
| if self.current == 0: |
| message = ( |
| "Runtime error occurs before first pass/transformation. " |
| "Stop binary searching." |
| ) |
| self.logger.LogOutput(message, print_to_console=verbose) |
| return True |
| |
| if status == 0: |
| message = "Runtime error is not reproduced, increasing lower bound." |
| self.logger.LogOutput(message, print_to_console=verbose) |
| self.lo = self.current + 1 |
| elif status == 1: |
| message = "Runtime error is reproduced, decreasing upper bound.." |
| self.logger.LogOutput(message, print_to_console=verbose) |
| self.hi = self.current |
| |
| if self.lo >= self.hi: |
| return True |
| |
| return False |
| |
| |
| class BinarySearcher(object): |
| """Class of binary searcher.""" |
| |
| def __init__(self, logger_to_set=None): |
| self.sorted_list = [] |
| self.index_log = [] |
| self.status_log = [] |
| self.skipped_indices = [] |
| self.current = 0 |
| self.points = {} |
| self.lo = 0 |
| self.hi = 0 |
| if logger_to_set is not None: |
| self.logger = logger_to_set |
| else: |
| self.logger = logger.GetLogger() |
| |
| def SetSortedList(self, sorted_list): |
| assert sorted_list |
| self.sorted_list = sorted_list |
| self.index_log = [] |
| self.hi = len(sorted_list) - 1 |
| self.lo = 0 |
| self.points = {} |
| for i in range(len(self.sorted_list)): |
| bsp = BinarySearchPoint(self.sorted_list[i], -1, "Not yet done.") |
| self.points[i] = bsp |
| |
| def SetStatus(self, status, tag=None): |
| message = "Revision: %s index: %d returned: %d" % ( |
| self.sorted_list[self.current], |
| self.current, |
| status, |
| ) |
| self.logger.LogOutput(message, print_to_console=verbose) |
| assert status in (0, 1, 125), status |
| self.index_log.append(self.current) |
| self.status_log.append(status) |
| bsp = BinarySearchPoint(self.sorted_list[self.current], status, tag) |
| self.points[self.current] = bsp |
| |
| if status == 125: |
| self.skipped_indices.append(self.current) |
| |
| if status in (0, 1): |
| if status == 0: |
| self.lo = self.current + 1 |
| elif status == 1: |
| self.hi = self.current |
| self.logger.LogOutput("lo: %d hi: %d\n" % (self.lo, self.hi)) |
| self.current = (self.lo + self.hi) // 2 |
| |
| if self.lo == self.hi: |
| message = ( |
| "Search complete. First bad version: %s" |
| " at index: %d" |
| % ( |
| self.sorted_list[self.current], |
| self.lo, |
| ) |
| ) |
| self.logger.LogOutput(message) |
| return True |
| |
| for index in range(self.lo, self.hi): |
| if index not in self.skipped_indices: |
| return False |
| self.logger.LogOutput( |
| "All skipped indices between: %d and %d\n" % (self.lo, self.hi), |
| print_to_console=verbose, |
| ) |
| return True |
| |
| # Does a better job with chromeos flakiness. |
| def GetNextFlakyBinary(self): |
| t = (self.lo, self.current, self.hi) |
| q = [t] |
| while q: |
| element = q.pop(0) |
| if element[1] in self.skipped_indices: |
| # Go top |
| to_add = ( |
| element[0], |
| (element[0] + element[1]) // 2, |
| element[1], |
| ) |
| q.append(to_add) |
| # Go bottom |
| to_add = ( |
| element[1], |
| (element[1] + element[2]) // 2, |
| element[2], |
| ) |
| q.append(to_add) |
| else: |
| self.current = element[1] |
| return |
| assert q, "Queue should never be 0-size!" |
| |
| def GetNextFlakyLinear(self): |
| current_hi = self.current |
| current_lo = self.current |
| while True: |
| if current_hi < self.hi and current_hi not in self.skipped_indices: |
| self.current = current_hi |
| break |
| if current_lo >= self.lo and current_lo not in self.skipped_indices: |
| self.current = current_lo |
| break |
| if current_lo < self.lo and current_hi >= self.hi: |
| break |
| |
| current_hi += 1 |
| current_lo -= 1 |
| |
| def GetNext(self): |
| self.current = (self.hi + self.lo) // 2 |
| # Try going forward if current is skipped. |
| if self.current in self.skipped_indices: |
| self.GetNextFlakyBinary() |
| |
| # TODO: Add an estimated time remaining as well. |
| message = "Estimated tries: min: %d max: %d\n" % ( |
| 1 + math.log(self.hi - self.lo, 2), |
| self.hi - self.lo - len(self.skipped_indices), |
| ) |
| self.logger.LogOutput(message, print_to_console=verbose) |
| message = "lo: %d hi: %d current: %d version: %s\n" % ( |
| self.lo, |
| self.hi, |
| self.current, |
| self.sorted_list[self.current], |
| ) |
| self.logger.LogOutput(message, print_to_console=verbose) |
| self.logger.LogOutput(str(self), print_to_console=verbose) |
| return self.sorted_list[self.current] |
| |
| def SetLoRevision(self, lo_revision): |
| self.lo = self.sorted_list.index(lo_revision) |
| |
| def SetHiRevision(self, hi_revision): |
| self.hi = self.sorted_list.index(hi_revision) |
| |
| def GetAllPoints(self): |
| to_return = "" |
| for i in range(len(self.sorted_list)): |
| to_return += "%d %d %s\n" % ( |
| self.points[i].status, |
| i, |
| self.points[i].revision, |
| ) |
| |
| return to_return |
| |
| def __str__(self): |
| to_return = "" |
| to_return += "Current: %d\n" % self.current |
| to_return += str(self.index_log) + "\n" |
| revision_log = [] |
| for index in self.index_log: |
| revision_log.append(self.sorted_list[index]) |
| to_return += str(revision_log) + "\n" |
| to_return += str(self.status_log) + "\n" |
| to_return += "Skipped indices:\n" |
| to_return += str(self.skipped_indices) + "\n" |
| to_return += self.GetAllPoints() |
| return to_return |
| |
| |
| class RevisionInfo(object): |
| """Class of reversion info.""" |
| |
| def __init__(self, date, client, description): |
| self.date = date |
| self.client = client |
| self.description = description |
| self.status = -1 |
| |
| |
| class VCSBinarySearcher(object): |
| """Class of VCS binary searcher.""" |
| |
| def __init__(self): |
| self.bs = BinarySearcher() |
| self.rim = {} |
| self.current_ce = None |
| self.checkout_dir = None |
| self.current_revision = None |
| |
| def Initialize(self): |
| pass |
| |
| def GetNextRevision(self): |
| pass |
| |
| def CheckoutRevision(self, current_revision): |
| pass |
| |
| def SetStatus(self, status): |
| pass |
| |
| def Cleanup(self): |
| pass |
| |
| def SetGoodRevision(self, revision): |
| if revision is None: |
| return |
| assert revision in self.bs.sorted_list |
| self.bs.SetLoRevision(revision) |
| |
| def SetBadRevision(self, revision): |
| if revision is None: |
| return |
| assert revision in self.bs.sorted_list |
| self.bs.SetHiRevision(revision) |
| |
| |
| class P4BinarySearcher(VCSBinarySearcher): |
| """Class of P4 binary searcher.""" |
| |
| def __init__(self, p4_port, p4_paths, test_command): |
| VCSBinarySearcher.__init__(self) |
| self.p4_port = p4_port |
| self.p4_paths = p4_paths |
| self.test_command = test_command |
| self.checkout_dir = tempfile.mkdtemp() |
| self.ce = command_executer.GetCommandExecuter() |
| self.client_name = "binary-searcher-$HOSTNAME-$USER" |
| self.job_log_root = "/home/asharif/www/coreboot_triage/" |
| self.changes = None |
| |
| def Initialize(self): |
| self.Cleanup() |
| command = GetP4Command( |
| self.client_name, self.p4_port, self.p4_paths, 1, self.checkout_dir |
| ) |
| self.ce.RunCommand(command) |
| command = "cd %s && g4 changes ..." % self.checkout_dir |
| _, out, _ = self.ce.RunCommandWOutput(command) |
| self.changes = re.findall(r"Change (\d+)", out) |
| change_infos = re.findall( |
| r"Change (\d+) on ([\d/]+) by " r"([^\s]+) ('[^']*')", out |
| ) |
| for change_info in change_infos: |
| ri = RevisionInfo(change_info[1], change_info[2], change_info[3]) |
| self.rim[change_info[0]] = ri |
| # g4 gives changes in reverse chronological order. |
| self.changes.reverse() |
| self.bs.SetSortedList(self.changes) |
| |
| def SetStatus(self, status): |
| self.rim[self.current_revision].status = status |
| return self.bs.SetStatus(status) |
| |
| def GetNextRevision(self): |
| next_revision = self.bs.GetNext() |
| self.current_revision = next_revision |
| return next_revision |
| |
| def CleanupCLs(self): |
| if not os.path.isfile(self.checkout_dir + "/.p4config"): |
| command = "cd %s" % self.checkout_dir |
| command += " && cp ${HOME}/.p4config ." |
| command += ' && echo "P4PORT=' + self.p4_port + '" >> .p4config' |
| command += ( |
| ' && echo "P4CLIENT=' + self.client_name + '" >> .p4config' |
| ) |
| self.ce.RunCommand(command) |
| command = "cd %s" % self.checkout_dir |
| command += "; g4 changes -c %s" % self.client_name |
| _, out, _ = self.ce.RunCommandWOutput(command) |
| changes = re.findall(r"Change (\d+)", out) |
| if changes: |
| command = "cd %s" % self.checkout_dir |
| for change in changes: |
| command += "; g4 revert -c %s" % change |
| self.ce.RunCommand(command) |
| |
| def CleanupClient(self): |
| command = "cd %s" % self.checkout_dir |
| command += "; g4 revert ..." |
| command += "; g4 client -d %s" % self.client_name |
| self.ce.RunCommand(command) |
| |
| def Cleanup(self): |
| self.CleanupCLs() |
| self.CleanupClient() |
| |
| def __str__(self): |
| to_return = "" |
| for change in self.changes: |
| ri = self.rim[change] |
| if ri.status == -1: |
| to_return = "%s\t%d\n" % (change, ri.status) |
| else: |
| to_return += "%s\t%d\t%s\t%s\t%s\t%s\t%s\t%s\n" % ( |
| change, |
| ri.status, |
| ri.date, |
| ri.client, |
| ri.description, |
| self.job_log_root + change + ".cmd", |
| self.job_log_root + change + ".out", |
| self.job_log_root + change + ".err", |
| ) |
| return to_return |
| |
| |
| class P4GCCBinarySearcher(P4BinarySearcher): |
| """Class of P4 gcc binary searcher.""" |
| |
| # TODO: eventually get these patches from g4 instead of creating them manually |
| def HandleBrokenCLs(self, current_revision): |
| cr = int(current_revision) |
| problematic_ranges = [] |
| problematic_ranges.append([44528, 44539]) |
| problematic_ranges.append([44528, 44760]) |
| problematic_ranges.append([44335, 44882]) |
| command = "pwd" |
| for pr in problematic_ranges: |
| if cr in range(pr[0], pr[1]): |
| patch_file = "/home/asharif/triage_tool/%d-%d.patch" % ( |
| pr[0], |
| pr[1], |
| ) |
| with open(patch_file, encoding="utf-8") as f: |
| patch = f.read() |
| files = re.findall("--- (//.*)", patch) |
| command += "; cd %s" % self.checkout_dir |
| for f in files: |
| command += "; g4 open %s" % f |
| command += "; patch -p2 < %s" % patch_file |
| self.current_ce.RunCommand(command) |
| |
| def CheckoutRevision(self, current_revision): |
| job_logger = logger.Logger( |
| self.job_log_root, current_revision, True, subdir="" |
| ) |
| self.current_ce = command_executer.GetCommandExecuter(job_logger) |
| |
| self.CleanupCLs() |
| # Change the revision of only the gcc part of the toolchain. |
| command = ( |
| "cd %s/gcctools/google_vendor_src_branch/gcc " |
| "&& g4 revert ...; g4 sync @%s" |
| % (self.checkout_dir, current_revision) |
| ) |
| self.current_ce.RunCommand(command) |
| |
| self.HandleBrokenCLs(current_revision) |
| |
| |
| def Main(argv): |
| """The main function.""" |
| # Common initializations |
| ### command_executer.InitCommandExecuter(True) |
| ce = command_executer.GetCommandExecuter() |
| |
| parser = argparse.ArgumentParser() |
| parser.add_argument( |
| "-n", |
| "--num_tries", |
| dest="num_tries", |
| default="100", |
| help="Number of tries.", |
| ) |
| parser.add_argument( |
| "-g", |
| "--good_revision", |
| dest="good_revision", |
| help="Last known good revision.", |
| ) |
| parser.add_argument( |
| "-b", |
| "--bad_revision", |
| dest="bad_revision", |
| help="Last known bad revision.", |
| ) |
| parser.add_argument( |
| "-s", "--script", dest="script", help="Script to run for every version." |
| ) |
| options = parser.parse_args(argv) |
| # First get all revisions |
| p4_paths = [ |
| "//depot2/gcctools/google_vendor_src_branch/gcc/gcc-4.4.3/...", |
| "//depot2/gcctools/google_vendor_src_branch/binutils/" |
| "binutils-2.20.1-mobile/...", |
| "//depot2/gcctools/google_vendor_src_branch/" |
| "binutils/binutils-20100303/...", |
| ] |
| p4gccbs = P4GCCBinarySearcher("perforce2:2666", p4_paths, "") |
| |
| # Main loop: |
| terminated = False |
| num_tries = int(options.num_tries) |
| script = os.path.expanduser(options.script) |
| |
| try: |
| p4gccbs.Initialize() |
| p4gccbs.SetGoodRevision(options.good_revision) |
| p4gccbs.SetBadRevision(options.bad_revision) |
| while not terminated and num_tries > 0: |
| current_revision = p4gccbs.GetNextRevision() |
| |
| # Now run command to get the status |
| ce = command_executer.GetCommandExecuter() |
| command = "%s %s" % (script, p4gccbs.checkout_dir) |
| status = ce.RunCommand(command) |
| message = "Revision: %s produced: %d status\n" % ( |
| current_revision, |
| status, |
| ) |
| logger.GetLogger().LogOutput(message, print_to_console=verbose) |
| terminated = p4gccbs.SetStatus(status) |
| num_tries -= 1 |
| logger.GetLogger().LogOutput(str(p4gccbs), print_to_console=verbose) |
| |
| if not terminated: |
| logger.GetLogger().LogOutput( |
| "Tries: %d expired." % num_tries, print_to_console=verbose |
| ) |
| logger.GetLogger().LogOutput(str(p4gccbs.bs), print_to_console=verbose) |
| except (KeyboardInterrupt, SystemExit): |
| logger.GetLogger().LogOutput("Cleaning up...") |
| finally: |
| logger.GetLogger().LogOutput(str(p4gccbs.bs), print_to_console=verbose) |
| p4gccbs.Cleanup() |
| |
| |
| if __name__ == "__main__": |
| Main(sys.argv[1:]) |
