Home | History | Annotate | Download | only in binary_search_tool 
      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