| |
| # 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.""" |
| |
| 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 and len(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 = 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 |