xref: /illumos-gate/usr/src/cmd/pools/poold/com/sun/solaris/domain/pools/SystemSolver.java (revision 55fea89dcaa64928bed4327112404dcb3e07b79f)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  *
26  * ident	"%Z%%M%	%I%	%E% SMI"
27  */
28 
29 package com.sun.solaris.domain.pools;
30 
31 import java.io.*;
32 import java.nio.*;
33 import java.nio.channels.*;
34 import java.util.*;
35 import java.util.regex.*;
36 import java.text.DecimalFormat;
37 
38 import com.sun.solaris.service.locality.*;
39 import com.sun.solaris.service.logging.*;
40 import com.sun.solaris.service.pools.*;
41 import com.sun.solaris.service.exception.*;
42 
43 /**
44  * The <code>SystemSolver</code> class implements a dynamic resource
45  * allocation solver. The Solver takes a configuration and "solves"
46  * the resource allocation problem.
47  *
48  * This class operates upon a configuration which is suppplied during
49  * initialization. Its responsibilities include:
50  * <ul>
51  * <li><p>
52  * Maintaining decision history
53  * <li><p>
54  * Maintaining information about the locality domain
55  * <li><p>
56  * Maintaining a map of all elements and their associated set of objectives
57  * <li><p>
58  * Identifying objective expressions with a configuration
59  * </ul>
60  */
61 class SystemSolver implements Solver {
62 	/**
63 	 * The default location of this history file.
64 	 */
65 	public static final String DH_FILE_DEF_PATH =
66 	    "/var/adm/pool/history";
67 
68 	/**
69 	 * The property overriding the default decision history path.
70 	 */
71 	public static final String DH_FILE_PROP_NAME =
72 	    "system.poold.history-file";
73 
74 	/**
75 	 * The LocalityDomain extracted from the configuration.
76 	 */
77 	private LocalityDomain ldom;
78 
79 	/**
80 	 * The objective map used to link all elements with their set
81 	 * of objectives.
82 	 */
83 	private Map objMap;
84 
85 	/**
86 	 * The pattern used to identify objective expressions.
87 	 */
88 	private static final Pattern p0 = Pattern.compile(";");
89 
90 	/**
91 	 * The configuration for which this solver is "solving".
92 	 */
93 	private Configuration conf;
94 
95 	/**
96 	 * Monitor providing statistics for this solver.
97 	 */
98 	private final Monitor monitor;
99 
100 	/**
101 	 * The decision history maintainer.
102 	 */
103 	private DecisionHistory dh;
104 
105 	/**
106 	 * The path to the decision history file.
107 	 */
108 	private String dhPath;
109 
110 	/**
111 	 * The number of CPUs on the system.
112 	 */
113 	private int cpuCount;
114 
115 	/**
116 	 * The number of locality triggered examinations made.
117 	 */
118 	private int examineCount;
119 
120 	/**
121 	 * Constructs a solver which initialises a decision history
122 	 * maintainer.  The decision history is be used during operation
123 	 * to veto historically-poor decisions output from the objective
124 	 * function.
125 	 */
SystemSolver(Monitor monitor)126 	SystemSolver(Monitor monitor)
127 	{
128 		/*
129 		 * Create a HashMap to store all objectives.
130 		 */
131 		objMap = new HashMap();
132 		this.monitor = monitor;
133 	}
134 
135 	/**
136 	 * Initialize the solver for operation upon the supplied
137 	 * configuration. Possible objective expressions set upon
138 	 * target elements are identified and stored in an objective
139 	 * map which associates elements with the set of their
140 	 * objectives.
141 	 *
142 	 * @param conf The configuration to be manipulated.
143 	 * @throws PoolsException If the initialization fails.
144 	 */
initialize(Configuration conf)145 	public void initialize(Configuration conf) throws PoolsException
146 	{
147 		String oString = null;
148 		String exps[];
149 
150 		this.conf = conf;
151 		/*
152 		 * Count the CPUs in the system, this is used to
153 		 * control locality objective processing in the
154 		 * examine() method.
155 		 */
156 		cpuCount = conf.getComponents(null).size();
157 		examineCount = 0;
158 		/*
159 		 * Remove any old objectives
160 		 */
161 		objMap.clear();
162 
163 		/*
164 		 * Extract any configuration objectives
165 		 */
166 		try {
167 			oString = conf.getStringProperty(
168 			    "system.poold.objectives");
169 			if (oString.length() > 0) {
170 				Set oSet = new HashSet();
171 				objMap.put(conf, oSet);
172 				Poold.CONF_LOG.log(Severity.DEBUG,
173 				    "adding configuration objective " +
174 				    oString);
175 				exps = p0.split(oString);
176 				for (int i = 0; i < exps.length; i++) {
177 					try {
178 						Expression exp =
179 						    Expression.valueOf(
180 						    exps[i]);
181 						addObjective(oSet, "system",
182 						    exp);
183 					} catch (IllegalArgumentException iae) {
184 						Poold.utility.warn(
185 						    Poold.CONF_LOG, iae, false);
186 					}
187 				}
188 			}
189 		} catch (PoolsException pe) {
190 			/*
191 			 * Ignore as this means there is no objective
192 			 * property
193 			 */
194 		}
195 		/*
196 		 * Now extract all pset objectives
197 		 */
198 		Value typeProp = new Value("type", "pset");
199 		List valueList = new LinkedList();
200 		valueList.add(typeProp);
201 		Iterator resIt = conf.getResources(valueList).iterator();
202 		typeProp.close();
203 		while (resIt.hasNext()) {
204 			Resource resource = (Resource)resIt.next();
205 
206 			try {
207 				oString = resource.getStringProperty(
208 				    "pset.poold.objectives");
209 				if (oString.length() > 0) {
210 					Set oSet = new HashSet();
211 					objMap.put(resource, oSet);
212 					Poold.CONF_LOG.log(Severity.DEBUG,
213 					    "adding " +
214 					    resource.getStringProperty(
215 					    "pset.name") +
216 					    " objective \"" + oString + "\"");
217 					exps = p0.split(oString);
218 					for (int i = 0; i < exps.length; i++) {
219 						Expression exp = null;
220 						try {
221 							exp = Expression.
222 							    valueOf(exps[i]);
223 							addObjective(oSet,
224 							    "pset", exp);
225 						} catch
226 						    (IllegalArgumentException e)
227 						{
228 							Poold.utility.warn(
229 							    Poold.CONF_LOG, e,
230 							    false);
231 						}
232 					}
233 				}
234 			} catch (PoolsException pe) {
235 				continue;
236 			}
237 		}
238 		Poold.CONF_LOG.log(Severity.DEBUG, "objective map: " +
239 		    objMap.toString());
240 
241 		/*
242 		 * Capture the LocalityDomain details.
243 		 */
244 		if (ldom != null) {
245 			ldom.close();
246 		}
247 		try {
248 			ldom = new LocalityDomain(LocalityDomain.LGRP_VIEW_OS);
249 		} catch (Exception e) {
250 			Poold.utility.die(Poold.OPT_LOG, e);
251 		}
252 
253 		/*
254 		 * Load or create the decision history.
255 		 */
256 		String newDhPath;
257 		try {
258 			newDhPath = conf.getStringProperty(
259 			    DH_FILE_PROP_NAME);
260 		} catch (PoolsException pe) {
261 			newDhPath = DH_FILE_DEF_PATH;
262 		}
263 
264 		if (!newDhPath.equals(dhPath)) {
265 			try {
266 				dh = DecisionHistory.loadFromFile(newDhPath);
267 				Poold.CONF_LOG.log(Severity.DEBUG,
268 				    "loaded history file " + newDhPath);
269 			} catch (Exception e) {
270 				if (!(e instanceof FileNotFoundException)) {
271 					Poold.CONF_LOG.log(Severity.WARNING,
272 					    newDhPath +
273 					    ": contents unusable; ignoring");
274 					Poold.CONF_LOG.log(Severity.DEBUG,
275 					    newDhPath + ": contents unusable",
276 					    e);
277 				}
278 				/*
279 				 * Use current DecisionHistory instead,
280 				 * if any.
281 				 */
282 				if (dh == null)
283 					dh = new DecisionHistory();
284 			}
285 
286 			/*
287 			 * Try using the new path.
288 			 */
289 			try {
290 				dh.syncToFile(newDhPath);
291 			} catch (Exception e) {
292 				Poold.utility.die(Poold.CONF_LOG,
293 				    new PooldException(newDhPath +
294 				    ": couldn't synchronize history file")
295 				    .initCause(e), false);
296 			}
297 			dhPath = newDhPath;
298 		}
299 	}
300 
301 	/**
302 	 * Determine if the given resource has non-workload-dependent
303 	 * objectives.
304 	 * @param elem The element to examine.
305 	 */
hasNonWorkloadDependentObjectives(Element elem)306 	private boolean hasNonWorkloadDependentObjectives(Element elem)
307 	{
308 		Set elemObj = (Set)objMap.get(elem);
309 
310 		/*
311 		 * This code relies upon the fact that an element with
312 		 * no objectives will not have an empty set, but rather
313 		 * no value in the objMap.
314 		 */
315 
316 		if (elemObj == null)
317 			return (false);
318 
319 		Iterator elemObjIt = elemObj.iterator();
320 		while (elemObjIt.hasNext())
321 			if (elemObjIt.next() instanceof
322 			    WorkloadDependentObjective)
323 				return (false);
324 
325 		return (true);
326 	}
327 
328 	/**
329 	 * Determine if the given resource has workload-dependent
330 	 * objectives.
331 	 * @param elem The element to examine.
332 	 */
hasWorkloadDependentObjectives(Element elem)333 	private boolean hasWorkloadDependentObjectives(Element elem)
334 	{
335 		Set elemObj = (Set)objMap.get(elem);
336 
337 		/*
338 		 * This code relies upon the fact that an element with
339 		 * no objectives will not have an empty set, but rather
340 		 * no value in the objMap.
341 		 */
342 
343 		if (elemObj == null)
344 			return (false);
345 
346 		Iterator elemObjIt = elemObj.iterator();
347 		while (elemObjIt.hasNext())
348 			if (elemObjIt.next() instanceof
349 			    WorkloadDependentObjective)
350 				return (true);
351 
352 		return (false);
353 	}
354 
355 	/**
356 	 * Return true if the monitored configuration should be
357 	 * reconfigured. All workload-dependent objectives are
358 	 * examined to determine if the configuration is still
359 	 * satisfying all specified objectives on all elements. If any
360 	 * objectives are failing, then this method will return true.
361 	 *
362 	 * @param mon The monitoring object used to assess objective
363 	 * compliance.
364 	 */
examine(Monitor mon)365 	public boolean examine(Monitor mon) throws PoolsException,
366 	    StaleMonitorException
367 	{
368 		/*
369 		 * Take advantage of the guaranteed-valid monitor data
370 		 * for measuring the improvement of any past decisions.
371 		 */
372 		dh.expireAndMeasureImprovements(mon);
373 
374 		Iterator objIt = objMap.keySet().iterator();
375 		boolean ret = false;
376 		boolean hasLocalityObjectives = false;
377 		boolean isMonitorValid = true;
378 
379 		/*
380 		 * All objectives are examined, even though failure
381 		 * could be detected earlier. This is because logging
382 		 * of all objectives is required and the information
383 		 * about failure can be stored and used during
384 		 * solving.
385 		 */
386 		while (objIt.hasNext()) {
387 			Element elem = (Element) objIt.next();
388 			Set elemObj = (Set) objMap.get(elem);
389 			Iterator elemObjIt = elemObj.iterator();
390 			while (elemObjIt.hasNext()) {
391 				Objective obj = (Objective) elemObjIt.next();
392 				Poold.OPT_LOG.log(Severity.DEBUG,
393 				    "checking objective " + obj);
394 				if (obj instanceof WorkloadDependentObjective) {
395 					if (isValid()) {
396 						/*
397 						 * If any objectives
398 						 * are violated, then
399 						 * we must
400 						 * reconfigure, so
401 						 * check them all in
402 						 * turn.
403 						 */
404 					ret = ((WorkloadDependentObjective)
405 					    obj).examine(conf, this, elem) ||
406 					    ret;
407 					} else
408 						isMonitorValid = false;
409 				}
410 			}
411 
412 			/*
413 			 * Check if this is the first element, seen in
414 			 * this pass, that has locality objectives.
415 			 */
416 			if (!hasLocalityObjectives &&
417 			    hasNonWorkloadDependentObjectives(elem))
418 				hasLocalityObjectives = true;
419 		}
420 		if (isMonitorValid == false) {
421 			Poold.MON_LOG.log(Severity.INFO,
422 			    "not evaluating workload-dependent objectives " +
423 			    "until sufficient statistics are collected");
424 		}
425 		/*
426 		 * If we don't have locality objectives, we don't force
427 		 * the reexamination.  This is controlled by
428 		 * hasLocalityObjectives.
429 		 *
430 		 * So that we don't continually trigger
431 		 * reconfiguration examinations for locality
432 		 * objectives we stop forcing recalculations when we
433 		 * reach cpuCount / 2. This should be enough moves to
434 		 * get good locality for those configurations which
435 		 * have no WorkloadDependentObjectives.
436 		 */
437 		return (ret || (hasLocalityObjectives && (examineCount++ <
438 		    cpuCount / 2)));
439 	}
440 
441 	/**
442 	 * Reallocate resources in a configuration to achieve user
443 	 * specified objectives. Return true if the configuration has
444 	 * been updated, false otherwise.
445 	 *
446 	 * This method should only be invoked if a previous
447 	 * examination of the configuration which is monitored
448 	 * indicates that objectives are failing. The monitored
449 	 * configuration is re-opened for editing, locking that
450 	 * configuration for the duration of this operation.
451 	 *
452 	 * @throws Exception If the solve fails.
453 	 */
solve()454 	public boolean solve() throws Exception
455 	{
456 		boolean madeMove = false;
457 		/*
458 		 * All solving operations must be done in an
459 		 * "editable" context, so create a new modifiable
460 		 * configuration which is at the same location as the
461 		 * monitored configuration
462 		 */
463 		Configuration rwConf = new Configuration(conf.getLocation(),
464 		    PoolInternal.PO_RDWR);
465 
466 		try {
467 			/*
468 			 * Build a resource set importance map for use
469 			 * when propagating pool importance to each
470 			 * possible solution. Use the same logic as
471 			 * libpool and let a resource take the highest
472 			 * importance value from all pools associated
473 			 * with the set.
474 			 */
475 			Map resImp = new HashMap();
476 			List poolList = rwConf.getPools(null);
477 			Iterator itPool = poolList.iterator();
478 			while (itPool.hasNext()) {
479 				Pool pool = (Pool) itPool.next();
480 				long newImp = pool.
481 				    getLongProperty("pool.importance");
482 				List resList = pool.getResources(null);
483 				Iterator itRes = resList.iterator();
484 				while (itRes.hasNext()) {
485 					Resource res = (Resource) itRes.next();
486 					if (resImp.containsKey(res)) {
487 						Long imp = (Long) resImp.
488 						    get(res);
489 						if (newImp > imp.longValue())
490 							resImp.put(res,
491 							    new Long(newImp));
492 					} else
493 						resImp.put(res,
494 						    new Long(newImp));
495 				}
496 			}
497 			/*
498 			 * Consider all possible alternative
499 			 * configurations.  This list is generated as a
500 			 * series of moves.  Administrative constraints
501 			 * are applied to the moves to prune the list of
502 			 * possible configurations.
503 			 */
504 			Value val = new Value("type", "pset");
505 			List valueList = new LinkedList();
506 			valueList.add(val);
507 
508 
509 			List resList = rwConf.getResources(valueList);
510 			val.close();
511 			List donors = getDonors(resList);
512 			List receivers = getRecipients(resList);
513 			Poold.OPT_LOG.log(Severity.DEBUG, "donors: " +
514 			    donors);
515 			Poold.OPT_LOG.log(Severity.DEBUG, "receivers: " +
516 			    receivers);
517 			Iterator itDonor = donors.iterator();
518 			List moves = new ArrayList();
519 			while (itDonor.hasNext()) {
520 				Resource donor = (Resource) itDonor.next();
521 				List processors = getProcessors(donor);
522 				Poold.OPT_LOG.log(Severity.DEBUG,
523 				    "donor processors: " + processors);
524 				Iterator itProcessor = processors.iterator();
525 				while (itProcessor.hasNext()) {
526 					Component cpu = (Component) itProcessor.
527 					    next();
528 					Iterator itReceiver = receivers.
529 					    iterator();
530 					while (itReceiver.hasNext()) {
531 						Resource receiver =
532 						    (Resource) itReceiver.
533 						    next();
534 						/*
535 						 * Can't move to yourself
536 						 */
537 						if (receiver == donor)
538 							continue;
539 						moves.add(new ComponentMove(
540 						      donor, receiver, cpu));
541 					}
542 				}
543 			}
544 			Poold.OPT_LOG.log(Severity.DEBUG,
545 			    "potential moves: " + moves);
546 			/*
547 			 * Now that we have our alternative configurations,
548 			 * score each configuration by applying all objectives
549 			 * to each configuration. Hold the scores in the
550 			 * score set.
551 			 */
552 			HashSet scores = new HashSet();
553 			Iterator itMoves = moves.iterator();
554 			while (itMoves.hasNext()) {
555 				double totalContrib = 0;
556 				Move move = (Move) itMoves.next();
557 				Iterator objIt = objMap.keySet().iterator();
558 				while (objIt.hasNext()) {
559 					Element elem = (Element) objIt.next();
560 					Set elemObj = (Set) objMap.get(elem);
561 					Iterator elemObjIt = elemObj.iterator();
562 					while (elemObjIt.hasNext()) {
563 						Objective obj =
564 						    (Objective)elemObjIt.next();
565 						if (obj instanceof
566 						    LocalityObjective)
567 							((LocalityObjective)obj)
568 							    .prepare(ldom,
569 							    (Resource)elem);
570 						/*
571 						 * If the monitor is
572 						 * invalid, do not
573 						 * process
574 						 * WorkloadDependentObjectives
575 						 * since they have an
576 						 * implicit dependency
577 						 * on the monitor
578 						 * data.
579 						 */
580 						if (obj instanceof
581 						    WorkloadDependentObjective)
582 							if (!isValid())
583 								continue;
584 						double contrib = obj.calculate(
585 						    rwConf, move, elem);
586 						if (contrib < -1 || contrib > 1)
587 							throw new
588 							IllegalOFValueException(
589 						        "x: " + contrib +
590 							" is invalid, legal " +
591 							"range is -1 <= x <= " +
592 							"1");
593 						/*
594 						 * Modify the basic
595 						 * score by the
596 						 * importance of the
597 						 * objective and (if
598 						 * appropriate) the
599 						 * importance of an
600 						 * associated pool.
601 						 */
602 						if (resImp.containsKey(elem)) {
603 							contrib *= ((Long)
604 							    resImp.get(elem)).
605 							    longValue();
606 						}
607 
608 						totalContrib += contrib *
609 						    obj.getExpression().
610 						    getImportance();
611 					}
612 				}
613 				Poold.OPT_LOG.log(Severity.DEBUG,
614 				    "scored move (" + move + ") " +
615 				    totalContrib);
616 				scores.add(new ScoreMove(move, totalContrib));
617 			}
618 			if (scores.size() != 0) {
619 				/*
620 				 * Try to find a move to apply which
621 				 * yields a positive contribution.
622 				 */
623 				Object scoresArray[] = scores.toArray();
624 				Arrays.sort(scoresArray,
625 				    Collections.reverseOrder());
626 				if ((madeMove = processMoves(rwConf,
627 				    scoresArray, false)) == false)
628 					madeMove = processMoves(rwConf,
629 					    scoresArray, true);
630 			} else
631 				Poold.OPT_LOG.log(Severity.INFO,
632 				    "no moves found");
633 			rwConf.close();
634 			Poold.OPT_LOG.log(Severity.DEBUG,
635 			    "synchronizing decision history");
636 			dh.syncToFile(dhPath);
637 		} catch (Exception ex) {
638 			rwConf.close();
639 			throw ex;
640 		}
641 		return (madeMove);
642 	}
643 
644 	/*
645 	 * Process the supplied array of scored moves, trying to find
646 	 * a move to apply. Return true if a move could be applied,
647 	 * false otherwise.
648 	 *
649 	 * @param conf The configuration to be modified.
650 	 * @param scores The areay of scored moves to be tried.
651 	 * @param ignoreDH Ignore Decision History details.
652 	 */
processMoves(Configuration rwConf, Object scores[], boolean ignoreDH)653 	private boolean processMoves(Configuration rwConf, Object scores[],
654 	    boolean ignoreDH) throws PoolsException, StaleMonitorException
655 	{
656 		boolean madeMove = false;
657 
658 		for (int i = 0; i < scores.length; i++) {
659 			ScoreMove move = (ScoreMove) scores[i];
660 			if (move.getScore() <= 0) {
661 				if (ignoreDH)
662 					Poold.OPT_LOG.log(Severity.INFO,
663 					    move + " not applied as " +
664 					    "benefit not significant");
665 				break;
666 			}
667 			if ((madeMove = applyMove(rwConf, move, ignoreDH)) ==
668 			    true)
669 				break;
670 		}
671 		return (madeMove);
672 	}
673 
674 	/*
675 	 * Attempt to apply the supplied move to the
676 	 * configuration. Return true if the move could be applied,
677 	 * false otherwise.
678 	 *
679 	 * @param conf The configuration to be modified.
680 	 * @param move The move to be applied.
681 	 * @param ignoreDH Ignore Decision History details.
682 	 */
applyMove(Configuration conf, ScoreMove move, boolean ignoreDH)683 	private boolean applyMove(Configuration conf, ScoreMove move,
684 	    boolean ignoreDH)
685 	    throws PoolsException, StaleMonitorException
686 	{
687 		boolean madeMove = false;
688 		boolean wdpInvolved = false;
689 		double utilization = 0.0;
690 
691 		Poold.OPT_LOG.log(Severity.DEBUG, "selected " + move);
692 		if (hasWorkloadDependentObjectives(move.getMove().getTo()) ||
693 		    hasWorkloadDependentObjectives(conf)) {
694 			Poold.OPT_LOG.log(Severity.DEBUG,
695 			    "Attempting to retrieve utilization for:" + move
696 			    .getMove().getTo());
697 			utilization = monitor.getUtilization(move
698 			    .getMove().getTo());
699 			wdpInvolved = true;
700 		}
701 
702 		/*
703 		 * Unless a move can be vetoed (i.e. decision history
704 		 * is effective and there are is a workload-dependent
705 		 * involved), the move should alwways be applied.
706 		 */
707 		if (ignoreDH || !wdpInvolved || !dh.veto(move.getMove(),
708 		    utilization)) {
709 			Poold.OPT_LOG.log(Severity.INFO,
710 			    "applying move " + move.getMove());
711 			move.getMove().apply();
712 			ResourceMonitor mon = getMonitor().get(move.getMove().
713 			    getFrom());
714 			mon.resetData("utilization");
715 			mon = getMonitor().get(move.getMove().getTo());
716 			mon.resetData("utilization");
717 			try {
718 				Poold.OPT_LOG.log(Severity.DEBUG,
719 				    "committing configuration");
720 				conf.commit(0);
721 				try {
722 					if (move.getMove() instanceof
723 					    ComponentMove)
724 						if (wdpInvolved)
725 							dh.recordProcessorMove(
726 							    (ComponentMove)move
727 							    .getMove(),
728 							    utilization,
729 							    monitor
730 							    .getSampleCount());
731 						else
732 							Poold.OPT_LOG.log(
733 							    Severity.DEBUG,
734 							    "decision not " +
735 							    "recorded due to " +
736 							    "lack of workload-"
737 							    + "dependent " +
738 							    "objectives");
739 				} catch (Exception e) {
740 					Poold.OPT_LOG.log(Severity.INFO,
741 					    "couldn't update " +
742 					    "decision history (" +
743 					    e.toString() + ")");
744 				}
745 				madeMove = true;
746 			} catch (PoolsException pe) {
747 				conf.rollback();
748 				Poold.OPT_LOG.log(Severity.INFO,
749 				    "move failed, possibly due to a " +
750 				    "bound process in a 1-processor " +
751 				    "set");
752 			}
753 		} else {
754 			/*
755 			 * Move was vetoed.
756 			 */
757 			if (!ignoreDH && wdpInvolved)
758 				Poold.OPT_LOG.log(Severity.INFO,
759 				    move.getMove() + " not applied due to " +
760 				    "poor past results");
761 		}
762 		return (madeMove);
763 	}
764 
765 	/**
766 	 * Add an objective based on the supplied expression to the
767 	 * supplied set of objectives.
768 	 *
769 	 * @param oSet Set of objectives to be extended
770 	 * @param type Type of element to which the expression is applied
771 	 * @param exp Expression to be used in the objective
772 	 * @throws IllegalArgumentException If a duplicate objective
773 	 * is identified or an invalid expression is supplied for this
774 	 * type of element
775 	 */
addObjective(Set oSet, String type, Expression exp)776 	private void addObjective(Set oSet, String type, Expression exp)
777 	    throws IllegalArgumentException
778 	{
779 		Objective o = AbstractObjective.getInstance(type, exp);
780 		Poold.CONF_LOG.log(Severity.DEBUG, "parsed objective " + o);
781 		/*
782 		 * Check the set of objectives and find contradictions.
783 		 */
784 		Iterator itObjs = oSet.iterator();
785 		while (itObjs.hasNext()) {
786 			Objective other = (Objective) itObjs.next();
787 			if (o.getExpression().contradicts(
788 			    other.getExpression()))
789 				throw new IllegalArgumentException(
790 				    "contradictory objectives:" + other +
791 				    ", " + o);
792 		}
793 
794 		if (oSet.add(o) != true)
795 			throw new IllegalArgumentException(
796 			    "duplicate objective:" + o);
797 	}
798 
799 	/**
800 	 * Return a list of resource sets prepared to receive
801 	 * resources
802 	 *
803 	 * The list consists of all resource setss (of the supplied
804 	 * type) whose size is < their max constraint.
805 	 *
806 	 * @param resList The list of all resource sets from which
807 	 * recipients will be chosen
808 	 * @throws PoolsException if there is an error manipulation
809 	 * the pool resources
810 	 */
getRecipients(List resList)811 	private List getRecipients(List resList) throws PoolsException
812 	{
813 		List recipientList = new ArrayList();
814 		long size, max;
815 		for (int i = 0; i < resList.size(); i++) {
816 			Resource res;
817 			res = (Resource)resList.get(i);
818 			String type = res.getStringProperty("type");
819 			size = res.getLongProperty(type+".size");
820 			max = res.getLongProperty(type+".max");
821 			if (size < max)
822 				recipientList.add(res);
823 		}
824 		return (recipientList);
825 	}
826 
827 	/**
828 	 * Return a list of resource sets prepared to donate resources
829 	 *
830 	 * The list consists of all resource sets (of the supplied
831 	 * type) whose size (minus the number of pinned resources
832 	 * where applicable) is > their min constraint.
833 	 *
834 	 * @param resList The list of all resource sets from which
835 	 * recipients will be chosen
836 	 * @throws PoolsException if there is an error manipulation
837 	 * the pool resources
838 	 */
getDonors(List resList)839 	private List getDonors(List resList) throws PoolsException
840 	{
841 		List donorList = new ArrayList();
842 		long size, min;
843 		for (int i = 0; i < resList.size(); i++) {
844 			Value bValue;
845 			Resource res;
846 			List pinned;
847 			ArrayList valueList = new ArrayList();
848 
849 			res = (Resource)resList.get(i);
850 			String type = res.getStringProperty("type");
851 			size = res.getLongProperty(type+".size");
852 			bValue = new Value("cpu.pinned", true);
853 			valueList.add(bValue);
854 			pinned = res.getComponents(valueList);
855 			bValue.close();
856 			min = res.getLongProperty(type+".min");
857 			if (pinned.size() > min)
858 				size -= pinned.size() - min;
859 			if (size > min)
860 				donorList.add(res);
861 		}
862 		return (donorList);
863 	}
864 
865 	/**
866 	 * Return a list of Processors for the supplied resource.
867 	 *
868 	 * The list consists of all Processors (excluding the pinned
869 	 * Processors) in the set.
870 	 *
871 	 * @param set The resource for which Processors should be found
872 	 * @throws PoolsException if there is an error manipulation
873 	 * the pool resources
874 	 */
getProcessors(Resource set)875 	private List getProcessors(Resource set) throws PoolsException
876 	{
877 		Iterator it = set.getComponents(null).iterator();
878 		List ret = new ArrayList();
879 
880 		while (it.hasNext()) {
881 			Component cpu = (Component) it.next();
882 			try
883 			{
884 				if (cpu.getBoolProperty("cpu.pinned") == false)
885 					ret.add(cpu);
886 			} catch (PoolsException pe)
887 			{
888 				ret.add(cpu);
889 			}
890 		}
891 		return (ret);
892 	}
893 
894 	/**
895 	 * Return true if the solver is capable of working with
896 	 * statistically valid data.
897 	 */
isValid()898 	public boolean isValid()
899 	{
900 		return (monitor.isValid());
901 	}
902 
903 	/**
904 	 * Return the monitor used by this solver.
905 	 */
getMonitor()906 	public Monitor getMonitor()
907 	{
908 		return (monitor);
909 	}
910 
911 	/**
912 	 * Return the set of objectives associated with the supplied
913 	 * element.
914 	 *
915 	 * @param elem Retrieve objectives for this element.
916 	 */
getObjectives(Element elem)917 	public Set getObjectives(Element elem)
918 	{
919 		return ((Set)objMap.get(elem));
920 	}
921 
922 	/**
923 	 * Holds details about the score of a proposed configuration
924 	 * move. Each move must be scored so that they can ranked in
925 	 * terms of increasing desirability
926 	 */
927 	static class ScoreMove implements Comparable {
928 		/**
929 		 * The move which is being scored.
930 		 */
931 		private final Move m;
932 
933 		/**
934 		 * The score of the move.
935 		 */
936 		private final double score;
937 
938 		/**
939 		 * Score formatter.
940 		 */
941 		private static final DecimalFormat scoreFormat =
942 		    new DecimalFormat("0.00");
943 
944 		/**
945 		 * Constructor.
946 		 *
947 		 * @param m The move under consideration.
948 		 * @param score The score of the move.
949 		 */
ScoreMove(Move m, double score)950 		public ScoreMove(Move m, double score)
951 		{
952 			this.m = m;
953 			this.score = score;
954 		}
955 
compareTo(Object o)956 		public int compareTo(Object o)
957 		{
958 			ScoreMove other = (ScoreMove) o;
959 
960 			return ((score < other.getScore()) ? -1 :
961 			    (score > other.getScore()) ? 1 : 0);
962 		}
963 
toString()964 		public String toString()
965 		{
966 			return ("move (" + m + ") score "
967 			    + scoreFormat.format(score));
968 		}
969 
970 		/**
971 		 * Return the score.
972 		 */
getScore()973 		double getScore()
974 		{
975 			return (score);
976 		}
977 
978 		/**
979 		 * Return the move.
980 		 */
getMove()981 		Move getMove()
982 		{
983 			return (m);
984 		}
985 	}
986 }
987