• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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."""
7from __future__ import print_function
8
9import math
10import argparse
11import os
12import re
13import sys
14import tempfile
15
16from cros_utils import command_executer
17from cros_utils import logger
18
19verbose = True
20
21
22def _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
33def 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
61class 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
70class 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
130class 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
272class 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
282class 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
320class 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
402class 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
441def 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
511if __name__ == '__main__':
512  Main(sys.argv[1:])
513