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