crosperf/machine_image_manager.py

# -*- coding: utf-8 -*-
# Copyright 2015 The Chromium OS Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

"""MachineImageManager allocates images to duts."""

from __future__ import print_function

import functools


class MachineImageManager(object):
  """Management of allocating images to duts.

    * Data structure we have -

      duts_ - list of duts, for each duts, we assume the following 2 properties
      exist - label_ (the current label the duts_ carries or None, if it has an
      alien image) and name (a string)

      labels_ - a list of labels, for each label, we assume these properties
      exist - remote (a set/vector/list of dut names (not dut object), to each
      of which this image is compatible), remote could be none, which means
      universal compatible.

      label_duts_ - for each label, we maintain a list of duts, onto which the
      label is imaged. Note this is an array of lists. Each element of each list
      is an integer which is dut oridnal. We access this array using label
      ordinal.

      allocate_log_ - a list of allocation record. For example, if we allocate
      l1 to d1, then l2 to d2, then allocate_log_ would be [(1, 1), (2, 2)].
      This is used for debug/log, etc. All tuples in the list are integer pairs
      (label_ordinal, dut_ordinal).

      n_duts_ - number of duts.

      n_labels_ - number of labels.

      dut_name_ordinal_ - mapping from dut name (a string) to an integer,
      starting from 0. So that duts_[dut_name_ordinal_[a_dut.name]]= a_dut.

    * Problem abstraction -

      Assume we have the following matrix - label X machine (row X col). A 'X'
      in (i, j) in the matrix means machine and lable is not compatible, or that
      we cannot image li to Mj.

           M1   M2   M3
      L1    X

      L2             X

      L3    X    X

      Now that we'll try to find a way to fill Ys in the matrix so that -

        a) - each row at least get a Y, this ensures that each label get imaged
        at least once, an apparent prerequiste.

        b) - each column get at most N Ys. This make sure we can successfully
        finish all tests by re-image each machine at most N times. That being
        said, we could *OPTIONALLY* reimage some machines more than N times to
        *accelerate* the test speed.

      How to choose initial N for b) -
      If number of duts (nd) is equal to or more than that of labels (nl), we
      start from N == 1. Else we start from N = nl - nd + 1.

      We will begin the search with pre-defined N, if we fail to find such a
      solution for such N, we increase N by 1 and continue the search till we
      get N == nl, at this case we fails.

      Such a solution ensures minimal number of reimages.

    * Solution representation

      The solution will be placed inside the matrix, like below

           M1   M2   M3   M4
      L1    X    X    Y

      L2    Y         X

      L3    X    Y    X

    * Allocation algorithm

      When Mj asks for a image, we check column j, pick the first cell that
      contains a 'Y', and mark the cell '_'. If no such 'Y' exists (like M4 in
      the above solution matrix), we just pick an image that the minimal reimage
      number.

      After allocate for M3
           M1   M2   M3   M4
      L1    X    X    _

      L2    Y         X

      L3    X    Y    X

      After allocate for M4
           M1   M2   M3   M4
      L1    X    X    _

      L2    Y         X    _

      L3    X    Y    X

      After allocate for M2
           M1   M2   M3   M4
      L1    X    X    _

      L2    Y         X    _

      L3    X    _    X

      After allocate for M1
           M1   M2   M3   M4
      L1    X    X    _

      L2    _         X    _

      L3    X    _    X

      After allocate for M2
           M1   M2   M3   M4
      L1    X    X    _

      L2    _    _    X    _

      L3    X    _    X

      If we try to allocate for M1 or M2 or M3 again, we get None.

    * Special / common case to handle seperately

      We have only 1 dut or if we have only 1 label, that's simple enough.
  """

  def __init__(self, labels, duts):
    self.labels_ = labels
    self.duts_ = duts
    self.n_labels_ = len(labels)
    self.n_duts_ = len(duts)
    self.dut_name_ordinal_ = dict()
    for idx, dut in enumerate(self.duts_):
      self.dut_name_ordinal_[dut.name] = idx

    # Generate initial matrix containg 'X' or ' '.
    self.matrix_ = [['X' if l.remote else ' '
                     for _ in range(self.n_duts_)]
                    for l in self.labels_]
    for ol, l in enumerate(self.labels_):
      if l.remote:
        for r in l.remote:
          self.matrix_[ol][self.dut_name_ordinal_[r]] = ' '

    self.label_duts_ = [[] for _ in range(self.n_labels_)]
    self.allocate_log_ = []

  def compute_initial_allocation(self):
    """Compute the initial label-dut allocation.

    This method finds the most efficient way that every label gets imaged at
    least once.

    Returns:
      False, only if not all labels could be imaged to a certain machine,
      otherwise True.
    """

    if self.n_duts_ == 1:
      for i, v in self.matrix_vertical_generator(0):
        if v != 'X':
          self.matrix_[i][0] = 'Y'
      return

    if self.n_labels_ == 1:
      for j, v in self.matrix_horizontal_generator(0):
        if v != 'X':
          self.matrix_[0][j] = 'Y'
      return

    if self.n_duts_ >= self.n_labels_:
      n = 1
    else:
      n = self.n_labels_ - self.n_duts_ + 1
    while n <= self.n_labels_:
      if self._compute_initial_allocation_internal(0, n):
        break
      n += 1

    return n <= self.n_labels_

  def _record_allocate_log(self, label_i, dut_j):
    self.allocate_log_.append((label_i, dut_j))
    self.label_duts_[label_i].append(dut_j)

  def allocate(self, dut, schedv2=None):
    """Allocate a label for dut.

    Args:
      dut: the dut that asks for a new image.
      schedv2: the scheduling instance, we need the benchmark run
               information with schedv2 for a better allocation.

    Returns:
      a label to image onto the dut or None if no more available images for
      the dut.
    """
    j = self.dut_name_ordinal_[dut.name]
    # 'can_' prefix means candidate label's.
    can_reimage_number = 999
    can_i = 999
    can_label = None
    can_pending_br_num = 0
    for i, v in self.matrix_vertical_generator(j):
      label = self.labels_[i]

      # 2 optimizations here regarding allocating label to dut.
      # Note schedv2 might be None in case we do not need this
      # optimization or we are in testing mode.
      if schedv2 is not None:
        pending_br_num = len(schedv2.get_label_map()[label])
        if pending_br_num == 0:
          # (A) - we have finished all br of this label,
          # apparently, we do not want to reimaeg dut to
          # this label.
          continue
      else:
        # In case we do not have a schedv2 instance, mark
        # pending_br_num as 0, so pending_br_num >=
        # can_pending_br_num is always True.
        pending_br_num = 0

      # For this time being, I just comment this out until we have a
      # better estimation how long each benchmarkrun takes.
      # if (pending_br_num <= 5 and
      #     len(self.label_duts_[i]) >= 1):
      #     # (B) this is heuristic - if there are just a few test cases
      #     # (say <5) left undone for this label, and there is at least
      #     # 1 other machine working on this lable, we probably not want
      #     # to bother to reimage this dut to help with these 5 test
      #     # cases
      #     continue

      if v == 'Y':
        self.matrix_[i][j] = '_'
        self._record_allocate_log(i, j)
        return label
      if v == ' ':
        label_reimage_number = len(self.label_duts_[i])
        if ((can_label is None) or
            (label_reimage_number < can_reimage_number or
             (label_reimage_number == can_reimage_number and
              pending_br_num >= can_pending_br_num))):
          can_reimage_number = label_reimage_number
          can_i = i
          can_label = label
          can_pending_br_num = pending_br_num

    # All labels are marked either '_' (already taken) or 'X' (not
    # compatible), so return None to notify machine thread to quit.
    if can_label is None:
      return None

    # At this point, we don't find any 'Y' for the machine, so we go the
    # 'min' approach.
    self.matrix_[can_i][j] = '_'
    self._record_allocate_log(can_i, j)
    return can_label

  def matrix_vertical_generator(self, col):
    """Iterate matrix vertically at column 'col'.

    Yield row number i and value at matrix_[i][col].
    """
    for i, _ in enumerate(self.labels_):
      yield i, self.matrix_[i][col]

  def matrix_horizontal_generator(self, row):
    """Iterate matrix horizontally at row 'row'.

    Yield col number j and value at matrix_[row][j].
    """
    for j, _ in enumerate(self.duts_):
      yield j, self.matrix_[row][j]

  def _compute_initial_allocation_internal(self, level, N):
    """Search matrix for d with N."""

    if level == self.n_labels_:
      return True

    for j, v in self.matrix_horizontal_generator(level):
      if v == ' ':
        # Before we put a 'Y', we check how many Y column 'j' has.
        # Note y[0] is row idx, y[1] is the cell value.
        ny = functools.reduce(lambda x, y: x + 1 if (y[1] == 'Y') else x,
                              self.matrix_vertical_generator(j), 0)
        if ny < N:
          self.matrix_[level][j] = 'Y'
          if self._compute_initial_allocation_internal(level + 1, N):
            return True
          self.matrix_[level][j] = ' '

    return False