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