1# -*- coding: utf-8 -*- 2# Copyright 2015 The Chromium OS Authors. All rights reserved. 3# Use of this source code is governed by a BSD-style license that can be 4# found in the LICENSE file. 5 6"""MachineImageManager allocates images to duts.""" 7 8from __future__ import print_function 9 10import functools 11 12 13class MachineImageManager(object): 14 """Management of allocating images to duts. 15 16 * Data structure we have - 17 18 duts_ - list of duts, for each duts, we assume the following 2 properties 19 exist - label_ (the current label the duts_ carries or None, if it has an 20 alien image) and name (a string) 21 22 labels_ - a list of labels, for each label, we assume these properties 23 exist - remote (a set/vector/list of dut names (not dut object), to each 24 of which this image is compatible), remote could be none, which means 25 universal compatible. 26 27 label_duts_ - for each label, we maintain a list of duts, onto which the 28 label is imaged. Note this is an array of lists. Each element of each list 29 is an integer which is dut oridnal. We access this array using label 30 ordinal. 31 32 allocate_log_ - a list of allocation record. For example, if we allocate 33 l1 to d1, then l2 to d2, then allocate_log_ would be [(1, 1), (2, 2)]. 34 This is used for debug/log, etc. All tuples in the list are integer pairs 35 (label_ordinal, dut_ordinal). 36 37 n_duts_ - number of duts. 38 39 n_labels_ - number of labels. 40 41 dut_name_ordinal_ - mapping from dut name (a string) to an integer, 42 starting from 0. So that duts_[dut_name_ordinal_[a_dut.name]]= a_dut. 43 44 * Problem abstraction - 45 46 Assume we have the following matrix - label X machine (row X col). A 'X' 47 in (i, j) in the matrix means machine and lable is not compatible, or that 48 we cannot image li to Mj. 49 50 M1 M2 M3 51 L1 X 52 53 L2 X 54 55 L3 X X 56 57 Now that we'll try to find a way to fill Ys in the matrix so that - 58 59 a) - each row at least get a Y, this ensures that each label get imaged 60 at least once, an apparent prerequiste. 61 62 b) - each column get at most N Ys. This make sure we can successfully 63 finish all tests by re-image each machine at most N times. That being 64 said, we could *OPTIONALLY* reimage some machines more than N times to 65 *accelerate* the test speed. 66 67 How to choose initial N for b) - 68 If number of duts (nd) is equal to or more than that of labels (nl), we 69 start from N == 1. Else we start from N = nl - nd + 1. 70 71 We will begin the search with pre-defined N, if we fail to find such a 72 solution for such N, we increase N by 1 and continue the search till we 73 get N == nl, at this case we fails. 74 75 Such a solution ensures minimal number of reimages. 76 77 * Solution representation 78 79 The solution will be placed inside the matrix, like below 80 81 M1 M2 M3 M4 82 L1 X X Y 83 84 L2 Y X 85 86 L3 X Y X 87 88 * Allocation algorithm 89 90 When Mj asks for a image, we check column j, pick the first cell that 91 contains a 'Y', and mark the cell '_'. If no such 'Y' exists (like M4 in 92 the above solution matrix), we just pick an image that the minimal reimage 93 number. 94 95 After allocate for M3 96 M1 M2 M3 M4 97 L1 X X _ 98 99 L2 Y X 100 101 L3 X Y X 102 103 After allocate for M4 104 M1 M2 M3 M4 105 L1 X X _ 106 107 L2 Y X _ 108 109 L3 X Y X 110 111 After allocate for M2 112 M1 M2 M3 M4 113 L1 X X _ 114 115 L2 Y X _ 116 117 L3 X _ X 118 119 After allocate for M1 120 M1 M2 M3 M4 121 L1 X X _ 122 123 L2 _ X _ 124 125 L3 X _ X 126 127 After allocate for M2 128 M1 M2 M3 M4 129 L1 X X _ 130 131 L2 _ _ X _ 132 133 L3 X _ X 134 135 If we try to allocate for M1 or M2 or M3 again, we get None. 136 137 * Special / common case to handle seperately 138 139 We have only 1 dut or if we have only 1 label, that's simple enough. 140 """ 141 142 def __init__(self, labels, duts): 143 self.labels_ = labels 144 self.duts_ = duts 145 self.n_labels_ = len(labels) 146 self.n_duts_ = len(duts) 147 self.dut_name_ordinal_ = dict() 148 for idx, dut in enumerate(self.duts_): 149 self.dut_name_ordinal_[dut.name] = idx 150 151 # Generate initial matrix containg 'X' or ' '. 152 self.matrix_ = [['X' if l.remote else ' ' 153 for _ in range(self.n_duts_)] 154 for l in self.labels_] 155 for ol, l in enumerate(self.labels_): 156 if l.remote: 157 for r in l.remote: 158 self.matrix_[ol][self.dut_name_ordinal_[r]] = ' ' 159 160 self.label_duts_ = [[] for _ in range(self.n_labels_)] 161 self.allocate_log_ = [] 162 163 def compute_initial_allocation(self): 164 """Compute the initial label-dut allocation. 165 166 This method finds the most efficient way that every label gets imaged at 167 least once. 168 169 Returns: 170 False, only if not all labels could be imaged to a certain machine, 171 otherwise True. 172 """ 173 174 if self.n_duts_ == 1: 175 for i, v in self.matrix_vertical_generator(0): 176 if v != 'X': 177 self.matrix_[i][0] = 'Y' 178 return 179 180 if self.n_labels_ == 1: 181 for j, v in self.matrix_horizontal_generator(0): 182 if v != 'X': 183 self.matrix_[0][j] = 'Y' 184 return 185 186 if self.n_duts_ >= self.n_labels_: 187 n = 1 188 else: 189 n = self.n_labels_ - self.n_duts_ + 1 190 while n <= self.n_labels_: 191 if self._compute_initial_allocation_internal(0, n): 192 break 193 n += 1 194 195 return n <= self.n_labels_ 196 197 def _record_allocate_log(self, label_i, dut_j): 198 self.allocate_log_.append((label_i, dut_j)) 199 self.label_duts_[label_i].append(dut_j) 200 201 def allocate(self, dut, schedv2=None): 202 """Allocate a label for dut. 203 204 Args: 205 dut: the dut that asks for a new image. 206 schedv2: the scheduling instance, we need the benchmark run 207 information with schedv2 for a better allocation. 208 209 Returns: 210 a label to image onto the dut or None if no more available images for 211 the dut. 212 """ 213 j = self.dut_name_ordinal_[dut.name] 214 # 'can_' prefix means candidate label's. 215 can_reimage_number = 999 216 can_i = 999 217 can_label = None 218 can_pending_br_num = 0 219 for i, v in self.matrix_vertical_generator(j): 220 label = self.labels_[i] 221 222 # 2 optimizations here regarding allocating label to dut. 223 # Note schedv2 might be None in case we do not need this 224 # optimization or we are in testing mode. 225 if schedv2 is not None: 226 pending_br_num = len(schedv2.get_label_map()[label]) 227 if pending_br_num == 0: 228 # (A) - we have finished all br of this label, 229 # apparently, we do not want to reimaeg dut to 230 # this label. 231 continue 232 else: 233 # In case we do not have a schedv2 instance, mark 234 # pending_br_num as 0, so pending_br_num >= 235 # can_pending_br_num is always True. 236 pending_br_num = 0 237 238 # For this time being, I just comment this out until we have a 239 # better estimation how long each benchmarkrun takes. 240 # if (pending_br_num <= 5 and 241 # len(self.label_duts_[i]) >= 1): 242 # # (B) this is heuristic - if there are just a few test cases 243 # # (say <5) left undone for this label, and there is at least 244 # # 1 other machine working on this lable, we probably not want 245 # # to bother to reimage this dut to help with these 5 test 246 # # cases 247 # continue 248 249 if v == 'Y': 250 self.matrix_[i][j] = '_' 251 self._record_allocate_log(i, j) 252 return label 253 if v == ' ': 254 label_reimage_number = len(self.label_duts_[i]) 255 if ((can_label is None) or 256 (label_reimage_number < can_reimage_number or 257 (label_reimage_number == can_reimage_number and 258 pending_br_num >= can_pending_br_num))): 259 can_reimage_number = label_reimage_number 260 can_i = i 261 can_label = label 262 can_pending_br_num = pending_br_num 263 264 # All labels are marked either '_' (already taken) or 'X' (not 265 # compatible), so return None to notify machine thread to quit. 266 if can_label is None: 267 return None 268 269 # At this point, we don't find any 'Y' for the machine, so we go the 270 # 'min' approach. 271 self.matrix_[can_i][j] = '_' 272 self._record_allocate_log(can_i, j) 273 return can_label 274 275 def matrix_vertical_generator(self, col): 276 """Iterate matrix vertically at column 'col'. 277 278 Yield row number i and value at matrix_[i][col]. 279 """ 280 for i, _ in enumerate(self.labels_): 281 yield i, self.matrix_[i][col] 282 283 def matrix_horizontal_generator(self, row): 284 """Iterate matrix horizontally at row 'row'. 285 286 Yield col number j and value at matrix_[row][j]. 287 """ 288 for j, _ in enumerate(self.duts_): 289 yield j, self.matrix_[row][j] 290 291 def _compute_initial_allocation_internal(self, level, N): 292 """Search matrix for d with N.""" 293 294 if level == self.n_labels_: 295 return True 296 297 for j, v in self.matrix_horizontal_generator(level): 298 if v == ' ': 299 # Before we put a 'Y', we check how many Y column 'j' has. 300 # Note y[0] is row idx, y[1] is the cell value. 301 ny = functools.reduce(lambda x, y: x + 1 if (y[1] == 'Y') else x, 302 self.matrix_vertical_generator(j), 0) 303 if ny < N: 304 self.matrix_[level][j] = 'Y' 305 if self._compute_initial_allocation_internal(level + 1, N): 306 return True 307 self.matrix_[level][j] = ' ' 308 309 return False 310