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