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