1#!/usr/bin/python2
2"""Module of binary serch for perforce."""
3from __future__ import print_function
4
5import math
6import argparse
7import os
8import re
9import sys
10import tempfile
11
12from cros_utils import command_executer
13from cros_utils import logger
14
15verbose = True
16
17
18def _GetP4ClientSpec(client_name, p4_paths):
19  p4_string = ''
20  for p4_path in p4_paths:
21    if ' ' not in p4_path:
22      p4_string += ' -a %s' % p4_path
23    else:
24      p4_string += " -a \"" + (' //' + client_name + '/').join(p4_path) + "\""
25
26  return p4_string
27
28
29def GetP4Command(client_name, p4_port, p4_paths, checkoutdir, p4_snapshot=''):
30  command = ''
31
32  if p4_snapshot:
33    command += 'mkdir -p ' + checkoutdir
34    for p4_path in p4_paths:
35      real_path = p4_path[1]
36      if real_path.endswith('...'):
37        real_path = real_path.replace('/...', '')
38        command += (
39            '; mkdir -p ' + checkoutdir + '/' + os.path.dirname(real_path))
40        command += ('&& rsync -lr ' + p4_snapshot + '/' + real_path + ' ' +
41                    checkoutdir + '/' + os.path.dirname(real_path))
42    return command
43
44  command += ' export P4CONFIG=.p4config'
45  command += ' && mkdir -p ' + checkoutdir
46  command += ' && cd ' + checkoutdir
47  command += ' && cp ${HOME}/.p4config .'
48  command += ' && chmod u+w .p4config'
49  command += " && echo \"P4PORT=" + p4_port + "\" >> .p4config"
50  command += " && echo \"P4CLIENT=" + client_name + "\" >> .p4config"
51  command += (' && g4 client ' + _GetP4ClientSpec(client_name, p4_paths))
52  command += ' && g4 sync '
53  command += ' && cd -'
54  return command
55
56
57class BinarySearchPoint(object):
58  """Class of binary search point."""
59
60  def __init__(self, revision, status, tag=None):
61    self.revision = revision
62    self.status = status
63    self.tag = tag
64
65
66class BinarySearcher(object):
67  """Class of binary searcher."""
68
69  def __init__(self, logger_to_set=None):
70    self.sorted_list = []
71    self.index_log = []
72    self.status_log = []
73    self.skipped_indices = []
74    self.current = 0
75    self.points = {}
76    self.lo = 0
77    self.hi = 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 SetSortedList(self, sorted_list):
84    assert len(sorted_list) > 0
85    self.sorted_list = sorted_list
86    self.index_log = []
87    self.hi = len(sorted_list) - 1
88    self.lo = 0
89    self.points = {}
90    for i in range(len(self.sorted_list)):
91      bsp = BinarySearchPoint(self.sorted_list[i], -1, 'Not yet done.')
92      self.points[i] = bsp
93
94  def SetStatus(self, status, tag=None):
95    message = ('Revision: %s index: %d returned: %d' %
96               (self.sorted_list[self.current], self.current, status))
97    self.logger.LogOutput(message, print_to_console=verbose)
98    assert status == 0 or status == 1 or status == 125
99    self.index_log.append(self.current)
100    self.status_log.append(status)
101    bsp = BinarySearchPoint(self.sorted_list[self.current], status, tag)
102    self.points[self.current] = bsp
103
104    if status == 125:
105      self.skipped_indices.append(self.current)
106
107    if status == 0 or status == 1:
108      if status == 0:
109        self.lo = self.current + 1
110      elif status == 1:
111        self.hi = self.current
112      self.logger.LogOutput('lo: %d hi: %d\n' % (self.lo, self.hi))
113      self.current = (self.lo + self.hi) / 2
114
115    if self.lo == self.hi:
116      message = ('Search complete. First bad version: %s'
117                 ' at index: %d' % (self.sorted_list[self.current], self.lo))
118      self.logger.LogOutput(message)
119      return True
120
121    for index in range(self.lo, self.hi):
122      if index not in self.skipped_indices:
123        return False
124    self.logger.LogOutput(
125        'All skipped indices between: %d and %d\n' % (self.lo, self.hi),
126        print_to_console=verbose)
127    return True
128
129  # Does a better job with chromeos flakiness.
130  def GetNextFlakyBinary(self):
131    t = (self.lo, self.current, self.hi)
132    q = [t]
133    while len(q):
134      element = q.pop(0)
135      if element[1] in self.skipped_indices:
136        # Go top
137        to_add = (element[0], (element[0] + element[1]) / 2, element[1])
138        q.append(to_add)
139        # Go bottom
140        to_add = (element[1], (element[1] + element[2]) / 2, element[2])
141        q.append(to_add)
142      else:
143        self.current = element[1]
144        return
145    assert len(q), 'Queue should never be 0-size!'
146
147  def GetNextFlakyLinear(self):
148    current_hi = self.current
149    current_lo = self.current
150    while True:
151      if current_hi < self.hi and current_hi not in self.skipped_indices:
152        self.current = current_hi
153        break
154      if current_lo >= self.lo and current_lo not in self.skipped_indices:
155        self.current = current_lo
156        break
157      if current_lo < self.lo and current_hi >= self.hi:
158        break
159
160      current_hi += 1
161      current_lo -= 1
162
163  def GetNext(self):
164    self.current = (self.hi + self.lo) / 2
165    # Try going forward if current is skipped.
166    if self.current in self.skipped_indices:
167      self.GetNextFlakyBinary()
168
169    # TODO: Add an estimated time remaining as well.
170    message = ('Estimated tries: min: %d max: %d\n' %
171               (1 + math.log(self.hi - self.lo, 2),
172                self.hi - self.lo - len(self.skipped_indices)))
173    self.logger.LogOutput(message, print_to_console=verbose)
174    message = ('lo: %d hi: %d current: %d version: %s\n' %
175               (self.lo, self.hi, self.current, self.sorted_list[self.current]))
176    self.logger.LogOutput(message, print_to_console=verbose)
177    self.logger.LogOutput(str(self), print_to_console=verbose)
178    return self.sorted_list[self.current]
179
180  def SetLoRevision(self, lo_revision):
181    self.lo = self.sorted_list.index(lo_revision)
182
183  def SetHiRevision(self, hi_revision):
184    self.hi = self.sorted_list.index(hi_revision)
185
186  def GetAllPoints(self):
187    to_return = ''
188    for i in range(len(self.sorted_list)):
189      to_return += ('%d %d %s\n' % (self.points[i].status, i,
190                                    self.points[i].revision))
191
192    return to_return
193
194  def __str__(self):
195    to_return = ''
196    to_return += 'Current: %d\n' % self.current
197    to_return += str(self.index_log) + '\n'
198    revision_log = []
199    for index in self.index_log:
200      revision_log.append(self.sorted_list[index])
201    to_return += str(revision_log) + '\n'
202    to_return += str(self.status_log) + '\n'
203    to_return += 'Skipped indices:\n'
204    to_return += str(self.skipped_indices) + '\n'
205    to_return += self.GetAllPoints()
206    return to_return
207
208
209class RevisionInfo(object):
210  """Class of reversion info."""
211
212  def __init__(self, date, client, description):
213    self.date = date
214    self.client = client
215    self.description = description
216    self.status = -1
217
218
219class VCSBinarySearcher(object):
220  """Class of VCS binary searcher."""
221
222  def __init__(self):
223    self.bs = BinarySearcher()
224    self.rim = {}
225    self.current_ce = None
226    self.checkout_dir = None
227    self.current_revision = None
228
229  def Initialize(self):
230    pass
231
232  def GetNextRevision(self):
233    pass
234
235  def CheckoutRevision(self, revision):
236    pass
237
238  def SetStatus(self, status):
239    pass
240
241  def Cleanup(self):
242    pass
243
244  def SetGoodRevision(self, revision):
245    if revision is None:
246      return
247    assert revision in self.bs.sorted_list
248    self.bs.SetLoRevision(revision)
249
250  def SetBadRevision(self, revision):
251    if revision is None:
252      return
253    assert revision in self.bs.sorted_list
254    self.bs.SetHiRevision(revision)
255
256
257class P4BinarySearcher(VCSBinarySearcher):
258  """Class of P4 binary searcher."""
259
260  def __init__(self, p4_port, p4_paths, test_command):
261    VCSBinarySearcher.__init__(self)
262    self.p4_port = p4_port
263    self.p4_paths = p4_paths
264    self.test_command = test_command
265    self.checkout_dir = tempfile.mkdtemp()
266    self.ce = command_executer.GetCommandExecuter()
267    self.client_name = 'binary-searcher-$HOSTNAME-$USER'
268    self.job_log_root = '/home/asharif/www/coreboot_triage/'
269    self.changes = None
270
271  def Initialize(self):
272    self.Cleanup()
273    command = GetP4Command(self.client_name, self.p4_port, self.p4_paths, 1,
274                           self.checkout_dir)
275    self.ce.RunCommand(command)
276    command = 'cd %s && g4 changes ...' % self.checkout_dir
277    _, out, _ = self.ce.RunCommandWOutput(command)
278    self.changes = re.findall(r'Change (\d+)', out)
279    change_infos = re.findall(r'Change (\d+) on ([\d/]+) by '
280                              r"([^\s]+) ('[^']*')", out)
281    for change_info in change_infos:
282      ri = RevisionInfo(change_info[1], change_info[2], change_info[3])
283      self.rim[change_info[0]] = ri
284    # g4 gives changes in reverse chronological order.
285    self.changes.reverse()
286    self.bs.SetSortedList(self.changes)
287
288  def SetStatus(self, status):
289    self.rim[self.current_revision].status = status
290    return self.bs.SetStatus(status)
291
292  def GetNextRevision(self):
293    next_revision = self.bs.GetNext()
294    self.current_revision = next_revision
295    return next_revision
296
297  def CleanupCLs(self):
298    if not os.path.isfile(self.checkout_dir + '/.p4config'):
299      command = 'cd %s' % self.checkout_dir
300      command += ' && cp ${HOME}/.p4config .'
301      command += " && echo \"P4PORT=" + self.p4_port + "\" >> .p4config"
302      command += " && echo \"P4CLIENT=" + self.client_name + "\" >> .p4config"
303      self.ce.RunCommand(command)
304    command = 'cd %s' % self.checkout_dir
305    command += '; g4 changes -c %s' % self.client_name
306    _, out, _ = self.ce.RunCommandWOUTPUOT(command)
307    changes = re.findall(r'Change (\d+)', out)
308    if len(changes) != 0:
309      command = 'cd %s' % self.checkout_dir
310      for change in changes:
311        command += '; g4 revert -c %s' % change
312      self.ce.RunCommand(command)
313
314  def CleanupClient(self):
315    command = 'cd %s' % self.checkout_dir
316    command += '; g4 revert ...'
317    command += '; g4 client -d %s' % self.client_name
318    self.ce.RunCommand(command)
319
320  def Cleanup(self):
321    self.CleanupCLs()
322    self.CleanupClient()
323
324  def __str__(self):
325    to_return = ''
326    for change in self.changes:
327      ri = self.rim[change]
328      if ri.status == -1:
329        to_return = '%s\t%d\n' % (change, ri.status)
330      else:
331        to_return += ('%s\t%d\t%s\t%s\t%s\t%s\t%s\t%s\n' %
332                      (change, ri.status, ri.date, ri.client, ri.description,
333                       self.job_log_root + change + '.cmd',
334                       self.job_log_root + change + '.out',
335                       self.job_log_root + change + '.err'))
336    return to_return
337
338
339class P4GCCBinarySearcher(P4BinarySearcher):
340  """Class of P4 gcc binary searcher."""
341
342  # TODO: eventually get these patches from g4 instead of creating them manually
343  def HandleBrokenCLs(self, current_revision):
344    cr = int(current_revision)
345    problematic_ranges = []
346    problematic_ranges.append([44528, 44539])
347    problematic_ranges.append([44528, 44760])
348    problematic_ranges.append([44335, 44882])
349    command = 'pwd'
350    for pr in problematic_ranges:
351      if cr in range(pr[0], pr[1]):
352        patch_file = '/home/asharif/triage_tool/%d-%d.patch' % (pr[0], pr[1])
353        f = open(patch_file)
354        patch = f.read()
355        f.close()
356        files = re.findall('--- (//.*)', patch)
357        command += '; cd %s' % self.checkout_dir
358        for f in files:
359          command += '; g4 open %s' % f
360        command += '; patch -p2 < %s' % patch_file
361    self.current_ce.RunCommand(command)
362
363  def CheckoutRevision(self, current_revision):
364    job_logger = logger.Logger(
365        self.job_log_root, current_revision, True, subdir='')
366    self.current_ce = command_executer.GetCommandExecuter(job_logger)
367
368    self.CleanupCLs()
369    # Change the revision of only the gcc part of the toolchain.
370    command = ('cd %s/gcctools/google_vendor_src_branch/gcc '
371               '&& g4 revert ...; g4 sync @%s' %
372               (self.checkout_dir, current_revision))
373    self.current_ce.RunCommand(command)
374
375    self.HandleBrokenCLs(current_revision)
376
377
378def Main(argv):
379  """The main function."""
380  # Common initializations
381  ###  command_executer.InitCommandExecuter(True)
382  ce = command_executer.GetCommandExecuter()
383
384  parser = argparse.ArgumentParser()
385  parser.add_argument(
386      '-n',
387      '--num_tries',
388      dest='num_tries',
389      default='100',
390      help='Number of tries.')
391  parser.add_argument(
392      '-g',
393      '--good_revision',
394      dest='good_revision',
395      help='Last known good revision.')
396  parser.add_argument(
397      '-b',
398      '--bad_revision',
399      dest='bad_revision',
400      help='Last known bad revision.')
401  parser.add_argument(
402      '-s', '--script', dest='script', help='Script to run for every version.')
403  options = parser.parse_args(argv)
404  # First get all revisions
405  p4_paths = ['//depot2/gcctools/google_vendor_src_branch/gcc/gcc-4.4.3/...',
406              '//depot2/gcctools/google_vendor_src_branch/binutils/'
407              'binutils-2.20.1-mobile/...',
408              '//depot2/gcctools/google_vendor_src_branch/'
409              'binutils/binutils-20100303/...']
410  p4gccbs = P4GCCBinarySearcher('perforce2:2666', p4_paths, '')
411
412  # Main loop:
413  terminated = False
414  num_tries = int(options.num_tries)
415  script = os.path.expanduser(options.script)
416
417  try:
418    p4gccbs.Initialize()
419    p4gccbs.SetGoodRevision(options.good_revision)
420    p4gccbs.SetBadRevision(options.bad_revision)
421    while not terminated and num_tries > 0:
422      current_revision = p4gccbs.GetNextRevision()
423
424      # Now run command to get the status
425      ce = command_executer.GetCommandExecuter()
426      command = '%s %s' % (script, p4gccbs.checkout_dir)
427      status = ce.RunCommand(command)
428      message = ('Revision: %s produced: %d status\n' %
429                 (current_revision, status))
430      logger.GetLogger().LogOutput(message, print_to_console=verbose)
431      terminated = p4gccbs.SetStatus(status)
432      num_tries -= 1
433      logger.GetLogger().LogOutput(str(p4gccbs), print_to_console=verbose)
434
435    if not terminated:
436      logger.GetLogger().LogOutput(
437          'Tries: %d expired.' % num_tries, print_to_console=verbose)
438    logger.GetLogger().LogOutput(str(p4gccbs.bs), print_to_console=verbose)
439  except (KeyboardInterrupt, SystemExit):
440    logger.GetLogger().LogOutput('Cleaning up...')
441  finally:
442    logger.GetLogger().LogOutput(str(p4gccbs.bs), print_to_console=verbose)
443    status = p4gccbs.Cleanup()
444
445
446if __name__ == '__main__':
447  Main(sys.argv[1:])
448