File D:\maven-qcr-plugin-testsunitaires\qcr4java\jenkins-master\target\site\qc\core\src\main\java\hudson\model\queue\MappingWorksheet.java.html

1 /*
2 * The MIT License
3 *
4 * Copyright (c) 2010, InfraDNA, Inc.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22 * THE SOFTWARE.
23 */
24 package hudson.model.queue;
25
26 import com.google.common.collect.ImmutableList;
27 import com.google.common.collect.Iterables;
28 import hudson.model.Computer;
29 import hudson.model.Executor;
30 import hudson.model.Label;
31 import hudson.model.LoadBalancer;
32 import hudson.model.Node;
33 import hudson.model.Queue.BuildableItem;
34 import hudson.model.Queue.Executable;
35 import hudson.model.Queue.JobOffer;
36 import hudson.model.Queue.Task;
37 import hudson.model.labels.LabelAssignmentAction;
38
39 import java.util.AbstractList;
40 import java.util.ArrayList;
41 import java.util.Collection;
42 import java.util.HashMap;
43 import java.util.LinkedHashMap;
44 import java.util.List;
45 import java.util.Map;
46 import java.util.Map.Entry;
47
48 import static java.lang.Math.*;
49
50 /**
51 * Defines a mapping problem for answering "where do we execute this task?"
52 *
53 * <p>
54 * The heart of the placement problem is a mapping problem. We are given a {@link Task},
55 * (which in the general case consists of a set of {@link SubTask}s), and we are also given a number
56 * of idle {@link Executor}s, and our goal is to find a mapping from the former to the latter,
57 * which determines where each {@link SubTask} gets executed.
58 *
59 * <p>
60 * This mapping is done under two constraints:
61 *
62 * <ul>
63 * <li>
64 * "Same node" constraint. Some of the subtasks need to be co-located on the same node.
65 * See {@link SubTask#getSameNodeConstraint()}
66 * <li>
67 * Label constraint. {@link SubTask}s can specify that it can be only run on nodes that has the label.
68 * </ul>
69 *
70 * <p>
71 * We first fold the former constraint into the problem definition. That is, we now consider
72 * a set of {@link SubTask}s that need to be co-located as a single {@link WorkChunk}. Similarly,
73 * we consider a set of all {@link Executor}s from the same node as {@link ExecutorChunk}.
74 * Now, the problem becomes the weighted matching problem from {@link WorkChunk} to {@link ExecutorChunk}.
75 *
76 * <p>
77 * An instance of {@link MappingWorksheet} captures a problem definition, plus which
78 * {@link ExecutorChunk} and {@link WorkChunk} are compatible. The purpose of this class
79 * (and {@link ExecutorChunk} and {@link WorkChunk}) are to expose a lot of convenience methods
80 * to assist various algorithms that produce the solution of this mapping problem,
81 * which is represented as {@link Mapping}.
82 *
83 * @see LoadBalancer#map(Task, MappingWorksheet)
84 * @author Kohsuke Kawaguchi
85 */
86 public class MappingWorksheet {
87 public final List<ExecutorChunk> executors;
88 public final List<WorkChunk> works;
89 /**
90 * {@link BuildableItem} for which we are trying to figure out the execution plan. Never null.
91 */
92 public final BuildableItem item;
93
94 private static class ReadOnlyList<E> extends AbstractList<E> {
95 protected final List<E> base;
96
97 ReadOnlyList(List<E> base) {
98 this.base = base;
99 }
100
101 public E get(int index) {
102 return base.get(index);
103 }
104
105 public int size() {
106 return base.size();
107 }
108 }
109
110 public final class ExecutorChunk extends ReadOnlyList<ExecutorSlot> {
111 public final int index;
112 public final Computer computer;
113 public final Node node;
114
115 private ExecutorChunk(List<ExecutorSlot> base, int index) {
116 super(base);
117 this.index = index;
118 assert !base.isEmpty();
119 computer = base.get(0).getExecutor().getOwner();
120 node = computer.getNode();
121 }
122
123 /**
124 * Is this executor chunk and the given work chunk compatible? Can the latter be run on the former?
125 */
126 public boolean canAccept(WorkChunk c) {
127 return this.size() >= c.size()
128 && (c.assignedLabel==null || c.assignedLabel.contains(node));
129 }
130
131 /**
132 * Node name.
133 */
134 public String getName() {
135 return node.getNodeName();
136 }
137
138 /**
139 * Number of executors in this chunk.
140 * Alias for size but more readable.
141 */
142 public int capacity() {
143 return size();
144 }
145
146 private void execute(WorkChunk wc, WorkUnitContext wuc) {
147 assert capacity() >= wc.size();
148 int e = 0;
149 for (SubTask s : wc) {
150 while (!get(e).isAvailable())
151 e++;
152 get(e++).set(wuc.createWorkUnit(s));
153 }
154 }
155 }
156
157 public class WorkChunk extends ReadOnlyList<SubTask> {
158 public final int index;
159
160 // the main should be always at position 0
161 // /**
162 // * This chunk includes {@linkplain WorkUnit#isMainWork() the main work unit}.
163 // */
164 // public final boolean isMain;
165
166 /**
167 * If this task needs to be run on a node with a particular label,
168 * return that {@link Label}. Otherwise null, indicating
169 * it can run on anywhere.
170 */
171 public final Label assignedLabel;
172
173 /**
174 * If the previous execution of this task run on a certain node
175 * and this task prefers to run on the same node, return that.
176 * Otherwise null.
177 */
178 public final ExecutorChunk lastBuiltOn;
179
180
181 private WorkChunk(List<SubTask> base, int index) {
182 super(base);
183 assert !base.isEmpty();
184 this.index = index;
185 this.assignedLabel = getAssignedLabel(base.get(0));
186
187 Node lbo = base.get(0).getLastBuiltOn();
188 for (ExecutorChunk ec : executors) {
189 if (ec.node==lbo) {
190 lastBuiltOn = ec;
191 return;
192 }
193 }
194 lastBuiltOn = null;
195 }
196
197 private Label getAssignedLabel(SubTask task) {
198 for (LabelAssignmentAction laa : item.getActions(LabelAssignmentAction.class)) {
199 Label l = laa.getAssignedLabel(task);
200 if (l!=null) return l;
201 }
202 return task.getAssignedLabel();
203 }
204
205 public List<ExecutorChunk> applicableExecutorChunks() {
206 List<ExecutorChunk> r = new ArrayList<ExecutorChunk>(executors.size());
207 for (ExecutorChunk e : executors) {
208 if (e.canAccept(this))
209 r.add(e);
210 }
211 return r;
212 }
213 }
214
215 /**
216 * Represents the solution to the mapping problem.
217 * It's a mapping from every {@link WorkChunk} to {@link ExecutorChunk}
218 * that satisfies the constraints.
219 */
220 public final class Mapping {
221 // for each WorkChunk, identify ExecutorChunk where it is assigned to.
222 private final ExecutorChunk[] mapping = new ExecutorChunk[works.size()];
223
224 /**
225 * {@link ExecutorChunk} assigned to the n-th work chunk.
226 */
227 public ExecutorChunk assigned(int n) {
228 return mapping[n];
229 }
230
231 /**
232 * n-th {@link WorkChunk}.
233 */
234 public WorkChunk get(int n) {
235 return works.get(n);
236 }
237
238 /**
239 * Update the mapping to execute n-th {@link WorkChunk} on the specified {@link ExecutorChunk}.
240 */
241 public ExecutorChunk assign(int index, ExecutorChunk element) {
242 ExecutorChunk o = mapping[index];
243 mapping[index] = element;
244 return o;
245 }
246
247 /**
248 * Number of {@link WorkUnit}s that require assignments.
249 */
250 public int size() {
251 return mapping.length;
252 }
253
254 /**
255 * Returns the assignment as a map.
256 */
257 public Map<WorkChunk,ExecutorChunk> toMap() {
258 Map<WorkChunk,ExecutorChunk> r = new HashMap<WorkChunk,ExecutorChunk>();
259 for (int i=0; i<size(); i++)
260 r.put(get(i),assigned(i));
261 return r;
262 }
263
264 /**
265 * Checks if the assignments made thus far are valid an within the constraints.
266 */
267 public boolean isPartiallyValid() {
268 int[] used = new int[executors.size()];
269 for (int i=0; i<mapping.length; i++) {
270 ExecutorChunk ec = mapping[i];
271 if (ec==null) continue;
272 if (!ec.canAccept(works(i)))
273 return false; // invalid assignment
274 if ((used[ec.index] += works(i).size()) > ec.capacity())
275 return false;
276 }
277 return true;
278 }
279
280 /**
281 * Makes sure that all the assignments are made and it is within the constraints.
282 */
283 public boolean isCompletelyValid() {
284 for (ExecutorChunk ec : mapping)
285 if (ec==null) return false; // unassigned
286 return isPartiallyValid();
287 }
288
289 /**
290 * Executes this mapping by handing over {@link Executable}s to {@link JobOffer}
291 * as defined by the mapping.
292 */
293 public void execute(WorkUnitContext wuc) {
294 if (!isCompletelyValid())
295 throw new IllegalStateException();
296
297 for (int i=0; i<size(); i++)
298 assigned(i).execute(get(i),wuc);
299 }
300 }
301
302 public MappingWorksheet(BuildableItem item, List<? extends ExecutorSlot> offers) {
303 this(item,offers,LoadPredictor.all());
304 }
305
306 public MappingWorksheet(BuildableItem item, List<? extends ExecutorSlot> offers, Collection<? extends LoadPredictor> loadPredictors) {
307 this.item = item;
308
309 // group executors by their computers
310 Map<Computer,List<ExecutorSlot>> j = new HashMap<Computer, List<ExecutorSlot>>();
311 for (ExecutorSlot o : offers) {
312 Computer c = o.getExecutor().getOwner();
313 List<ExecutorSlot> l = j.get(c);
314 if (l==null)
315 j.put(c,l=new ArrayList<ExecutorSlot>());
316 l.add(o);
317 }
318
319 {// take load prediction into account and reduce the available executor pool size accordingly
320 long duration = item.task.getEstimatedDuration();
321 if (duration > 0) {
322 long now = System.currentTimeMillis();
323 for (Entry<Computer, List<ExecutorSlot>> e : j.entrySet()) {
324 final List<ExecutorSlot> list = e.getValue();
325 final int max = e.getKey().countExecutors();
326
327 // build up the prediction model. cut the chase if we hit the max.
328 Timeline timeline = new Timeline();
329 int peak = 0;
330 OUTER:
331 for (LoadPredictor lp : loadPredictors) {
332 for (FutureLoad fl : Iterables.limit(lp.predict(this,e.getKey(), now, now + duration),100)) {
333 peak = max(peak,timeline.insert(fl.startTime, fl.startTime+fl.duration, fl.numExecutors));
334 if (peak>=max) break OUTER;
335 }
336 }
337
338 int minIdle = max-peak; // minimum number of idle nodes during this time period
339 // total predicted load could exceed available executors [JENKINS-8882]
340 if (minIdle<0) {
341 // Should we toss a warning/info message?
342 minIdle = 0;
343 }
344 if (minIdle<list.size())
345 e.setValue(list.subList(0,minIdle));
346 }
347 }
348 }
349
350 // build into the final shape
351 List<ExecutorChunk> executors = new ArrayList<ExecutorChunk>();
352 for (List<ExecutorSlot> group : j.values()) {
353 if (group.isEmpty()) continue; // evict empty group
354 ExecutorChunk ec = new ExecutorChunk(group, executors.size());
355 if (ec.node==null) continue; // evict out of sync node
356 executors.add(ec);
357 }
358 this.executors = ImmutableList.copyOf(executors);
359
360 // group execution units into chunks. use of LinkedHashMap ensures that the main work comes at the top
361 Map<Object,List<SubTask>> m = new LinkedHashMap<Object,List<SubTask>>();
362 for (SubTask meu : Tasks.getSubTasksOf(item.task)) {
363 Object c = Tasks.getSameNodeConstraintOf(meu);
364 if (c==null) c = new Object();
365
366 List<SubTask> l = m.get(c);
367 if (l==null)
368 m.put(c,l= new ArrayList<SubTask>());
369 l.add(meu);
370 }
371
372 // build into the final shape
373 List<WorkChunk> works = new ArrayList<WorkChunk>();
374 for (List<SubTask> group : m.values()) {
375 works.add(new WorkChunk(group,works.size()));
376 }
377 this.works = ImmutableList.copyOf(works);
378 }
379
380 public WorkChunk works(int index) {
381 return works.get(index);
382 }
383
384 public ExecutorChunk executors(int index) {
385 return executors.get(index);
386 }
387
388 public static abstract class ExecutorSlot {
389 public abstract Executor getExecutor();
390
391 public abstract boolean isAvailable();
392
393 protected abstract void set(WorkUnit p) throws UnsupportedOperationException;
394 }
395 }
396