xref: /illumos-gate/usr/src/cmd/pools/poold/com/sun/solaris/domain/pools/Objective.java (revision 967a0a51c3e8ee257644dcad360e72dd4cf555f8)
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 (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2010 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  *
26  */
27 
28 package com.sun.solaris.domain.pools;
29 
30 import java.io.FileInputStream;
31 import java.io.IOException;
32 import java.lang.reflect.Field;
33 import java.text.DecimalFormat;
34 import java.util.*;
35 import java.util.logging.*;
36 
37 import com.sun.solaris.service.logging.Severity;
38 import com.sun.solaris.service.locality.*;
39 import com.sun.solaris.service.pools.*;
40 
41 
42 /**
43  * An objective interface. All classes which wish to contribute to the
44  * Objective Function (OF hence) calculation must implement this
45  * interface. This interface defines a strategy which can be used to
46  * make a contribution to the Objective Function calculation.
47  *
48  * The OF calculation (which is implemented by <code>Poold</code>)
49  * consists of determining all possible resource moves across all
50  * resources. Once all moves are known, all registered objectives
51  * (i.e. instances of this interface) are called and asked to value
52  * the move.
53  *
54  * Note, the output of this method is constrained to be between -1 and
55  * 1, representing minimum and maximum desirability of this move in
56  * terms of this objective. This is enforced by <code>Poold</code> and
57  * an <code>IllegalOFValueException</code> will be thrown if this
58  * constraint is broken.
59  */
60 interface Objective
61 {
62 	/**
63 	 * Return the contribution of this objective. The contribution
64 	 * is constrainted to be a value between -1 and +1 to ensure
65 	 * that no objective can make a disproportionate contribution
66 	 * to the total result.
67 	 *
68 	 * The more desirable this move appears in terms of this
69 	 * objective, the closer to +1 will be the value. A value of 0
70 	 * indicates that the move is neutral in terms of the
71 	 * objective. A negative value indicates that the move is
72 	 * undesirable.
73 	 *
74 	 * @param conf The configuration which is being examined
75 	 * @param move The move under consideration
76 	 * @param elem The element to which the objective applies
77 	 *
78 	 * @throws PoolsException if there is an error manipulating
79 	 * the configuration
80 	 */
calculate(Configuration conf, Move move, Element elem)81 	public double calculate(Configuration conf, Move move, Element elem)
82 	    throws PoolsException;
83 
84 	/**
85 	 * Set the objective's expression to the supplied parameter.
86 	 *
87 	 * @param exp An expression for this objective.
88 	 */
setExpression(Expression exp)89 	public void setExpression(Expression exp);
90 
91 	/**
92 	 * Get the objective's expression.
93 	 */
getExpression()94 	public Expression getExpression();
95 }
96 
97 /**
98  * This interface must be implemented by all Objectives which are
99  * workload dependent. The examine method is used by a Solver to
100  * determine if the objective is still being satisfied.
101  */
102 interface WorkloadDependentObjective extends Objective
103 {
104 	/**
105 	 * This method returns true if the Objective is no longer
106 	 * satisfied. If the objective is still satisfied, then return
107 	 * false.
108 	 *
109 	 * @param conf The configuration to be examined
110 	 * @param solver The solving interface used to get utilization
111 	 * information
112 	 * @param elem The element to which the objective belongs
113 	 *
114 	 * @throws PoolsException if there is an error examining the
115 	 * pool configuration
116 	 * @throws StaleMonitorException if there is an error accessing
117 	 * the element's ResourceMonitor
118 	 */
examine(Configuration conf, Solver solver, Element elem)119 	public boolean examine(Configuration conf, Solver solver,
120 	    Element elem) throws PoolsException, StaleMonitorException;
121 }
122 
123 /**
124  * This class provides a skeletal implementation of the
125  * <code>Objective</code> interface to minimize the effort required
126  * to implement this interface.
127  *
128  * To implement an objective, the programmer need only to extend this
129  * class and add the name of the class into the appropriate element
130  * objectives property in the <code>poold.properties</code> file.
131  */
132 abstract class AbstractObjective implements Objective
133 {
calculate(Configuration conf, Move move, Element elem)134 	abstract public double calculate(Configuration conf, Move move,
135 	    Element elem) throws PoolsException;
136 
137 	/**
138 	 * The objectives which are recognized by this class
139 	 */
140 	private static Map objectives;
141 
142 	/**
143 	 * The expression associated with this objective
144 	 */
145 	private Expression exp;
146 
147 	/**
148 	 * Set the objective's expression to the supplied parameter.
149 	 *
150 	 * @param exp An expression for this objective.
151 	 */
setExpression(Expression exp)152 	public void setExpression(Expression exp)
153 	{
154 		this.exp = exp;
155 	}
156 
157 	/**
158 	 * Get the objective's expression.
159 	 */
getExpression()160 	public Expression getExpression()
161 	{
162 		return (exp);
163 	}
164 
165 	/**
166 	 * A factory method which returns a created objective which is
167 	 * associated with the supplied expression. The type and the
168 	 * expression are used to identify valid types of objectives
169 	 * to which this expression may be applied. If an acceptable
170 	 * objective cannot be found for the supplied type, then an
171 	 * <code>IllegalArgumentException</code> will be thrown.
172 	 *
173 	 * @param type The element type for which an objective must be
174 	 * found
175 	 * @param exp The expression which will be associated with the
176 	 * objective
177 	 *
178 	 * @throws IllegalArgumentExcetion if the supplied expression
179 	 * cannot be associated with an objective of the supplied type
180 	 */
getInstance(String type, Expression exp)181 	public static Objective getInstance(String type, Expression exp)
182 	    throws IllegalArgumentException
183 	{
184 		Objective ret = null;
185 		Map typeObjs = null;
186 
187 		initMapIfNecessary();
188 		typeObjs = (Map)objectives.get(type);
189 		if (typeObjs != null) {
190 			Class objClass = (Class)typeObjs.get(exp.getName());
191 			if (objClass != null) {
192 				try {
193 					ret = (Objective) objClass.
194 					    newInstance();
195 				} catch (Exception e) {
196 					Poold.utility.die(Poold.OPT_LOG, e,
197 					    true);
198 				}
199 				ret.setExpression(exp);
200 			}
201 		}
202 		if (ret == null)
203 			throw new IllegalArgumentException(
204 			    "unrecognized objective name for " + type + ": " +
205 			    exp.toString());
206 		return (ret);
207 	}
208 
209 	/**
210 	 * Return a string representation of this objective.
211 	 */
toString()212 	public String toString()
213 	{
214 		return (exp.toString());
215 	}
216 
217 	/**
218 	 * Initialize the implementation map the first time it's
219 	 * called.
220 	 */
initMapIfNecessary()221 	private static void initMapIfNecessary()
222 	{
223 		/*
224 		 * Setup the objectives map for the known classes
225 		 */
226 		if (objectives == null) {
227 			objectives = new HashMap();
228 			Properties props = new Properties();
229 			try {
230 				props.load(
231 				    new FileInputStream(
232 				    Poold.POOLD_PROPERTIES_PATH));
233 			} catch (IOException ioe) {
234 				Poold.utility.die(Poold.CONF_LOG, ioe);
235 			}
236 			registerObjectives(props, objectives, "system");
237 			registerObjectives(props, objectives, "pset");
238 		}
239 	}
240 
241 	/**
242 	 * Add the objectives contained in the supplied properties to
243 	 * the set of valid objectives. The objectives are updated
244 	 * with objectives of the supplied type contained in the
245 	 * properties.
246 	 *
247 	 * @param props The properties containing the objectives
248 	 * @param objectives The objectives to be updated
249 	 * @param type The type of objectives to be added
250 	 */
registerObjectives(Properties props, Map objectives, String type)251 	private static void registerObjectives(Properties props,
252 	    Map objectives, String type)
253 	{
254 		Map typeObjs = new HashMap();
255 		String objs = props.getProperty(type + ".objectives");
256 		String objNames[] = objs.split(",");
257 		for (int i = 0; i < objNames.length; i++) {
258 			String objName = objNames[i].trim();
259 			try {
260 				Class clazz = Class.forName(objName);
261 				Field field = clazz.getDeclaredField("name");
262 				String key = (String) field.get(null);
263 				typeObjs.put(key, clazz);
264 			} catch (ClassNotFoundException cnfe) {
265 				Poold.utility.die(Poold.CONF_LOG, cnfe);
266 			} catch (NoSuchFieldException nsfe) {
267 				Poold.utility.die(Poold.CONF_LOG, nsfe);
268 			} catch (IllegalAccessException iae) {
269 				Poold.utility.die(Poold.CONF_LOG, iae);
270 			}
271 		}
272 		objectives.put(type, typeObjs);
273 	}
274 
275 	/**
276 	 * Indicates whether some other Objective is "equal to this
277 	 * one.
278 	 * @param o the reference object with which to compare.
279 	 * @return <code>true</code> if this object is the same as the
280 	 * o argument; <code>false</code> otherwise.
281 	 * @see	#hashCode()
282 	 */
equals(Object o)283 	public boolean equals(Object o)
284 	{
285 		if (o == this)
286 			return (true);
287 		if (!(o instanceof Objective))
288 			return (false);
289 		Objective other = (Objective) o;
290 
291 		return (getExpression().equals(other.getExpression()));
292 	}
293 
294 	/**
295 	 * Returns a hash code value for the object. This method is
296 	 * supported for the benefit of hashtables such as those provided by
297 	 * <code>java.util.Hashtable</code>.
298 	 *
299 	 * @return a hash code value for this object.
300 	 * @see	#equals(java.lang.Object)
301 	 * @see	java.util.Hashtable
302 	 */
hashCode()303 	public int hashCode()
304 	{
305 		return (getExpression().hashCode());
306 	}
307 }
308 
309 
310 /**
311  * The <code>WeightedLoadObjective</code> class implements a Weighted
312  * Load Objective for <code>Poold</code>.
313  *
314  * The goal is to allocate more resources to those resource partitions
315  * which are heavily loaded. The weighting is determined from the
316  * objective importance and the pool.importance.
317  */
318 final class WeightedLoadObjective extends AbstractObjective
319     implements WorkloadDependentObjective
320 {
321 	/**
322 	 * The name of the class.
323 	 */
324 	static final String name = "wt-load";
325 
326 	/**
327 	 * The map of calculations made during examination.
328 	 */
329 	Map calcMap;
330 
331 	/**
332 	 * Determine whether an objective is satisfied. If the
333 	 * objective is still satisfied, return false; otherwise
334 	 * return true.
335 	 *
336 	 * This objective examination determines if all resource sets
337 	 * are allocated the share of resources that their utilization
338 	 * would indicate they should be. This attempts to ensure that
339 	 * highly utilized resource sets recieve the greater
340 	 * proportion of available resources.
341 	 *
342 	 * @param conf The configuration to be examined
343 	 * @param solver The solving interface used to get utilization
344 	 * information
345 	 * @param elem The element to which the objective belongs
346 	 *
347 	 * @throws PoolsException if there is an error examining the
348 	 * pool configuration
349 	 * @throws StaleMonitorException if there is an error accessing
350 	 * the element's ResourceMonitor
351 	 */
examine(Configuration conf, Solver solver, Element elem)352 	public boolean examine(Configuration conf, Solver solver,
353 	    Element elem) throws PoolsException, StaleMonitorException
354 	{
355 		Monitor mon = solver.getMonitor();
356 		Value val = new Value("type", "pset");
357 		List valueList = new LinkedList();
358 		calcMap = new HashMap();
359 		valueList.add(val);
360 
361 		List resList = conf.getResources(valueList);
362 		val.close();
363 		Iterator itRes = resList.iterator();
364 
365 		Calculation.totalUtil = 0;
366 		Calculation.resQ = 0;
367 
368 		while (itRes.hasNext()) {
369 			Resource res = (Resource) itRes.next();
370 			List CPUs = res.getComponents(null);
371 
372 			try {
373 				Calculation calc = new Calculation(res, CPUs,
374 				    mon.getUtilization(res),
375 				    res.getLongProperty("pset.min"),
376 				    res.getLongProperty("pset.max"));
377 				calcMap.put(res, calc);
378 			} catch (StaleMonitorException sme) {
379 				Poold.MON_LOG.log(Severity.INFO,
380 				    res.toString() +
381 				    " not participating in " + toString() +
382 				    " calculatation as it has no " +
383 				    "available statistics.");
384 			}
385 		}
386 		Iterator itCalc = calcMap.values().iterator();
387 		while (itCalc.hasNext()) {
388 			Calculation calc = (Calculation) itCalc.next();
389 			if (calc.getShare() != calc.comp.size() &&
390 			    calc.getShare() >= calc.min) {
391 				Poold.MON_LOG.log(Severity.INFO,
392 				    elem.toString() +
393 				    " utilization objective not satisfied " +
394 				    toString() + " with desired share " +
395 				    calc.getShare() + " and actual share " +
396 				    calc.comp.size());
397 				return (true);
398 			}
399 		}
400 		return (false);
401 	}
402 
403 	/**
404 	 * Holds data about weighted load calculations. This class is
405 	 * basically a structure which holds information specific to a
406 	 * weighted-load calculation
407 	 */
408 	static class Calculation {
409 		/**
410 		 * The resource on which this calculation is based.
411 		 */
412 		Resource res;
413 
414 		/**
415 		 * The list of component resources held by this resource.
416 		 */
417 		List comp;
418 
419 		/**
420 		 * The utilization of this resource.
421 		 */
422 		double util;
423 
424 		/**
425 		 * The minimum value of this resource's size.
426 		 */
427 		long min;
428 
429 		/**
430 		 * The maximum value of this resource's size.
431 		 */
432 		long max;
433 
434 		/**
435 		 * The total utilization of all instances of this class.
436 		 */
437 		static double totalUtil;
438 
439 		/**
440 		 * The total quantity of resource for all instances of
441 		 * this class.
442 		 */
443 		static int resQ;
444 
445 		/**
446 		 * Constructor. The class is immutable and holds
447 		 * information specific to a set of calculations about
448 		 * load.
449 		 *
450 		 * @param res The resource set
451 		 * @param comp The resource components
452 		 * @param util The resource utilization
453 		 * @param min The minimum qty of resource for this set
454 		 * @param max The maximum qty of resource for this set
455 		 */
Calculation(Resource res, List comp, double util, long min, long max)456 		public Calculation(Resource res, List comp, double util,
457 		    long min, long max)
458 		{
459 			this.res = res;
460 			this.comp = comp;
461 			this.min = min;
462 			this.max = max;
463 			this.util = (util / 100) * comp.size();
464 			Calculation.totalUtil += this.util;
465 			Calculation.resQ += comp.size();
466 		}
467 
468 		/**
469 		 * Return the share of the total resource for this
470 		 * resource.
471 		 */
getShare()472 		long getShare()
473 		{
474 			if (util == 0)
475 				return (0);
476 			return (Math.round((util / totalUtil) * resQ));
477 		}
478 
toString()479 		public String toString()
480 		{
481 			StringBuffer buf = new StringBuffer();
482 			buf.append("res: " + res.toString());
483 			buf.append(" components: " + comp.toString());
484 			buf.append(" min: " + min);
485 			buf.append(" max: " + max);
486 			buf.append(" util: " + util);
487 			buf.append(" total resource: " + resQ);
488 			buf.append(" total utilization: " + totalUtil);
489 			buf.append(" share: " + getShare());
490 			return (buf.toString());
491 		}
492 	}
493 
494 	/**
495 	 * Calculates the value of a configuration in terms of this
496 	 * objective.
497 	 *
498 	 * In the examination step, calculations of each resource's
499 	 * current and desired share were made. The moves can thus be
500 	 * assessed in terms of their impact upon the desired
501 	 * share. The current difference from desired is already
502 	 * known, so each move will serve to reduce or increase that
503 	 * difference. Moves that increase the difference have a
504 	 * negative score, those that reduce it have a positive
505 	 * score. All scores are normalized to return a value between
506 	 * -1 and 1.
507 	 *
508 	 * @param conf Configuration to be scored.
509 	 * @param move Move to be scored.
510 	 * @param elem The element to which the objective applies
511 	 * @throws PoolsException If an there is an error in execution.
512 	 */
calculate(Configuration conf, Move move, Element elem)513 	public double calculate(Configuration conf, Move move, Element elem)
514 	    throws PoolsException
515 	{
516 		double ret = 0;
517 
518 		Poold.OPT_LOG.log(Severity.DEBUG,
519 		    "Calculating objective type: " + name);
520 		/*
521 		 * There shouldn't be any empty moves, but if there
522 		 * are they are rated at 0.
523 		 */
524 		if (move.getQty() == 0)
525 			return (0);
526 
527 		/*
528 		 * Find the calculations that represent the source and
529 		 * target of the move.
530 		 */
531 		Calculation src = (Calculation) calcMap.get(move.getFrom());
532 		Calculation tgt = (Calculation) calcMap.get(move.getTo());
533 
534 		/*
535 		 * Use the calculation details to determine the "gap"
536 		 * i.e. number of discrete resources (for a processor
537 		 * set these are CPUs), between the desired quantity in
538 		 * the set which the calculations represent. Do this
539 		 * both before and after the proposed move.
540 		 *
541 		 * The maximum possible improvement is equal to the
542 		 * total number of resources for each set participating
543 		 * in the calculation. Since there are two sets we
544 		 * know the maximum possible improvement is resQ * 2.
545 		 *
546 		 * Divide the aggregated change in gap across participating
547 		 * sets by the maximum possible improvement to obtain
548 		 * a value which scores the move and which is normalised
549 		 * between -1 <= ret <= 1.
550 		 */
551 		long oldGap = Math.abs(src.getShare() -
552 		    src.comp.size());
553 		long newGap = Math.abs(src.getShare() -
554 		    (src.comp.size() - move.getQty()));
555 		ret = oldGap - newGap;
556 		oldGap = Math.abs(tgt.getShare() -
557 		    tgt.comp.size());
558 		newGap = Math.abs(tgt.getShare() -
559 		    (tgt.comp.size() + move.getQty()));
560 		ret += oldGap - newGap;
561 		ret /= ((double) Calculation.resQ * 2);
562 
563 		Poold.MON_LOG.log(Severity.DEBUG, "ret: " + ret);
564 		return (ret);
565 	}
566 }
567 
568     /*
569      * The following LGroupData and Resulttuple and PSETData classes
570      * are used for the purposes of calculating and storing
571      * results sets for the LocalityObjective calculate method.
572      */
573 
574     /*
575      * To store data for a Localitygroup.
576      *
577      * The lgroup is the LocalityGroup.
578      * The numcpu is the number of cpu in the LocalityGroup.
579      * The factor is a value required in calculating the LocalityGroup quotient.
580      *
581      * The value of factor will always be a finite number
582      * because the LocalityGroup will never be empty.
583      */
584     final class LGroupData
585     {
586             private LocalityGroup lgroup;
587             private int numcpu = 0;
588             private double factor;
589 
LGroupData(LocalityGroup l)590             LGroupData(LocalityGroup l) {
591                 lgroup = l;
592                 int numcpuinlgroup = lgroup.getCPUIDs().length;
593                 factor = 2.0 / ((numcpuinlgroup * numcpuinlgroup)
594                         + numcpuinlgroup);
595             }
596 
getNumcpu()597             int getNumcpu() {
598                 return numcpu;
599             }
600 
getFactor()601             double getFactor() {
602                 return factor;
603             }
604 
incNumcpu()605             void incNumcpu() {
606                 numcpu++;
607             }
608     }
609 
610     /*
611      * Stores the results of caclulated locality quotients for a PSET.
612      *
613      * The AsIsResult is the quotient without any move.
614      * The FromResult is the quotient when a cpu is taken from it.
615      * The To result is the quotient when a cpu is added to it.
616      */
617     final class ResultTuple
618     {
619             private double AsIsResult = 0;
620             private double FromResult = 0;
621             private double ToResult = 0;
622 
ResultTuple(double a, double f, double t)623             ResultTuple(double a, double f, double t) {
624                 setAsIsResult(a);
625                 setFromResult(f);
626                 setToResult(t);
627             }
628 
getAsIsResult()629             double getAsIsResult() {
630                 return AsIsResult;
631             }
632 
getFromResult()633             double getFromResult() {
634                 return FromResult;
635             }
636 
getToResult()637             double getToResult() {
638                 return ToResult;
639             }
640 
setAsIsResult(double asis)641             void setAsIsResult(double asis) {
642                 AsIsResult = asis;
643             }
644 
setFromResult(double from)645             void setFromResult(double from) {
646                 FromResult = from;
647             }
648 
setToResult(double to)649             void setToResult(double to) {
650                 ToResult = to;
651             }
652     }
653 
654     /*
655      * The PSETData class enables storage and population of the data
656      * required for the LocalityObjective calculate() method.
657      *
658      * The lgroupdata HashMap stores LGroupData objects
659      * for each LGroup in the pset.
660      * The results HashMap stores resultsTuple objects for each LGroup.
661      * The countLgroups() method populates the lgroupdata HashMap.
662      * The calcQ() method calculates the quotient for any given
663      * value of intersection and lgroup size.
664      * The calcResults() method populates the results HashMap.
665      */
666     final class PSETData
667     {
668             private Resource pset;
669             private Map<LocalityGroup, LGroupData> lgroupdata
670                  = new HashMap<LocalityGroup, LGroupData>();
671             private Map<LocalityGroup, ResultTuple> results
672                  = new HashMap<LocalityGroup, ResultTuple>();
673             double AsIsTotal = 0;
674             int numlg = 0;
675 
getAsIsTotal()676             double getAsIsTotal() {
677                 return AsIsTotal;
678             }
679 
getResults()680             Map<LocalityGroup, ResultTuple> getResults() {
681                 return results;
682             }
683 
684             /*
685              * Count the number of cpu in each locality group in this pset
686              * and count the number of locality groups in this pset.
687              *
688              * @param allCPUData Map of all cpu and their LocalityGroup.
689              *
690              * @throws new PoolsException if no lgroups found, i.e numlg = 0;
691              */
countLgroups(Map allCPUData)692             private void countLgroups(Map allCPUData)
693                     throws PoolsException
694             {
695                 List cpuList = pset.getComponents(null);
696                 Iterator cpuIt = cpuList.iterator();
697                 while (cpuIt.hasNext()) {
698                     Component currentCPU = (Component) cpuIt.next();
699                     int cpuid = (int) currentCPU.getLongProperty("cpu.sys_id");
700                     if (allCPUData.containsKey(new Integer(cpuid))) {
701                         LocalityGroup lg =
702                             (LocalityGroup) allCPUData.get(new Integer(cpuid));
703                         if (lgroupdata.containsKey(lg)) {
704                             LGroupData cpulgp = (LGroupData) lgroupdata.get(lg);
705                             cpulgp.incNumcpu();
706                         }
707                     }
708                 }
709                 Set groups = lgroupdata.keySet();
710                 Iterator groupsIt = groups.iterator();
711                 while (groupsIt.hasNext()) {
712                     LocalityGroup lg = (LocalityGroup) groupsIt.next();
713                     LGroupData cpulgp = (LGroupData) lgroupdata.get(lg);
714                     if (cpulgp.getNumcpu() > 0) {
715                         numlg++;
716                     }
717                 }
718                 if (numlg == 0) {
719                     throw new PoolsException();
720                 }
721             }
722 
723             /**
724              * Calculate the final quotient with the given
725              * factor and intersection values.
726              *
727              * @param factor double value of factor for this move.
728              * @param intersection int value of intersection for this move.
729              */
calcQ(double factor, int intersection)730 	    private double calcQ(double factor, int intersection)
731             {
732                 double q = factor * ((intersection * intersection)
733                         + intersection) / 2.0;
734                 return (q);
735             }
736 
737             /*
738              * Calulate results for all locality groups for this pset.
739              *
740              * The logic considers all cases of pset populations;
741              * i) pset is empty; ii) pset has only one cpu;
742              * iii) pset more than one  cpu.
743              * numlg is never zero so we need not try and catch that here.
744              */
calcqA()745             private void calcqA()
746                     throws PoolsException
747             {
748                 Set allgroups = (Set) results.keySet();
749                 Iterator groupIt = (Iterator) allgroups.iterator();
750                 while (groupIt.hasNext()) {
751                     LocalityGroup lgroup = (LocalityGroup) groupIt.next();
752                     if (lgroupdata.containsKey(lgroup)) {
753                         LGroupData cpulgp =
754                                 (LGroupData) lgroupdata.get(lgroup);
755                         ResultTuple rst = (ResultTuple) results.get(lgroup);
756                         if (cpulgp.getNumcpu() == 0) {
757                             double toresult =
758                                     (AsIsTotal + rst.getToResult())/(numlg + 1);
759                             rst.setToResult(toresult);
760                         }
761                         if (cpulgp.getNumcpu() == 1) {
762                             double fromresult =
763                                     (AsIsTotal + rst.getFromResult())
764                                     /(numlg - 1);
765                             rst.setFromResult(fromresult);
766                         }
767                         if (cpulgp.getNumcpu() > 1) {
768                             double toresult = (AsIsTotal
769                                     - rst.getAsIsResult()
770                                     + rst.getToResult())/(numlg);
771                             rst.setToResult(toresult);
772                             double fromresult = (AsIsTotal
773                                     - rst.getAsIsResult()
774                                     + rst.getFromResult())/(numlg);
775                             rst.setFromResult(fromresult);
776                         }
777                         results.put(lgroup, rst);
778                     }
779                 }
780             }
781 
782             /*
783              * Populates the results map for each locality group.
784              *
785              * numlg is never zero so do not need to try and catch it.
786              *
787              * @param allLGroups Set of all Locality groups in this config.
788              */
calcResults(Set allLGroups)789             private void calcResults(Set allLGroups)
790                     throws PoolsException
791             {
792                 Iterator groupIt = (Iterator) allLGroups.iterator();
793                 while (groupIt.hasNext()) {
794                     int intersection = 0;
795                     double factor = 0;
796                     LocalityGroup lgroup = (LocalityGroup) groupIt.next();
797                     if (lgroup.getCPUIDs().length != 0) {
798                         if (lgroupdata.containsKey(lgroup)) {
799                             LGroupData cpulgp =
800                                     (LGroupData)lgroupdata.get(lgroup);
801                             intersection = cpulgp.getNumcpu();
802                             factor = cpulgp.getFactor();
803                         }
804                         ResultTuple thisresult = new ResultTuple(
805                             calcQ(factor, intersection),
806                             calcQ(factor, intersection-1),
807                             calcQ(factor, intersection+1));
808                         AsIsTotal += thisresult.getAsIsResult();
809                         results.put(lgroup, thisresult);
810                     }
811                 }
812                 calcqA();
813                 AsIsTotal /= numlg;
814             }
815 
816             /*
817              * Constructor for PSETData.
818              *
819              * @param allLGroups Set of all Locality groups in this config.
820              * @param allCPUData Map of all cpu and their locality group.
821              * @param p Resource (pset) for which the calculations are made.
822              *
823              * @throws PoolsException if accessing the supplied resource
824              * fails.
825              */
PSETData(Set allLGroups, Map allCPUData, Resource p)826             PSETData(Set allLGroups, Map allCPUData, Resource p)
827                     throws PoolsException
828             {
829                 pset = p;
830                 Iterator groupIt = (Iterator) allLGroups.iterator();
831                 while (groupIt.hasNext()) {
832                     LocalityGroup lgroup = (LocalityGroup) groupIt.next();
833                     if (lgroup.getCPUIDs().length != 0) {
834                         LGroupData cpulgp = new LGroupData(lgroup);
835                         lgroupdata.put(lgroup, cpulgp);
836                     }
837                 }
838                 countLgroups(allCPUData);
839                 calcResults(allLGroups);
840             }
841         }
842 
843 /**
844  * A locality based objective which will assess moves in terms of
845  * their impact on the locality of the sets of resources which are
846  * impacted.
847  *
848  * The objective will assess moves with respect to the type of
849  * locality specified in the objective:
850  *
851  * <ul>
852  * <li><p>
853  * tight - resource locality is sought
854  * <li><p>
855  * loose - resource locality is avoided
856  * <li><p>
857  * none - resource locality has no impact
858  * </ul>
859  */
860 final class LocalityObjective extends AbstractObjective
861 {
862 	/*
863 	 * The name of the class.
864 	 */
865 	static final String name = "locality";
866 
867 	/*
868 	 * The locality domain used to describe locality for this
869 	 * objective.
870 	 */
871 	private LocalityDomain ldom;
872 
873         /*
874          * The set of LocalityGroups in this ldom.
875          */
876         private Set allLGroups;
877 
878         /*
879          * Map of all cpu id and their locality groups
880          */
881         private Map<Integer, LocalityGroup> allCPUData
882                 = new HashMap<Integer, LocalityGroup>();
883 
884         /*
885          * Method to populate the allCPUData cpu locality map.
886          */
getCPUData()887         private void getCPUData()
888 	{
889             allLGroups = ldom.getGroups();
890             Iterator LGroupIt = allLGroups.iterator();
891             while (LGroupIt.hasNext()) {
892                 LocalityGroup lg = (LocalityGroup) LGroupIt.next();
893                 int cpu_ids[] = lg.getCPUIDs();
894                 for (int i = 0; i < cpu_ids.length; i++) {
895                     allCPUData.put(new Integer(cpu_ids[i]), lg);
896                 }
897             }
898 
899 	}
900 
901         /*
902          * Map to store all PSET LocalityGroup quotient results.
903          */
904         private Map<Resource, PSETData> allPSETData
905                 = new HashMap<Resource, PSETData>();
906 
907 	/**
908 	 * Prepare the calculation for this objective for the resource to
909 	 * which it applies.
910 	 *
911 	 * @param ldom LocalityDomain containing these resources.
912 	 * @param res Resource to which this objective is applied.
913 	 *
914 	 * @throws PoolsException if accessing the supplied resource
915 	 * fails.
916 	 */
prepare(LocalityDomain ldom, Resource res)917 	public void prepare(LocalityDomain ldom, Resource res)
918 	    throws PoolsException
919 	{
920 		this.ldom = ldom;
921 	}
922 
923 	/*
924 	 * Calculates the value of a configuration in terms of this
925 	 * objective.
926 	 *
927 	 * Firstly check to see if it is possible to short-cut the
928 	 * calculation. If not, then start to examine the disposition
929 	 * of CPUs and locality groups in relation to the processor
930 	 * set being evaluated. The objective scores moves in terms of
931 	 * their impact upon the quotient of cpus contained in each
932 	 * locality group.
933 	 *
934 	 * Moves which involve a cpu in the same locality group are equivalent.
935 	 * i.e for a given pset, the quotient calculation is the same
936 	 * for a move involving cpu x in localitygroup Z,
937 	 * as the calculation for cpu y in localitygroup Z,
938 	 * So we store the quotient calculation of the PSET
939 	 * i) as it is; ii) a cpu is added; iii) a cpu is removed;
940 	 *
941 	 * For each move we encounter, we store the quotient caclulations
942 	 * on a pset basis, holding a map of results for each pset we evaluate.
943 	 * The map contains results for each locality group in the system.
944 	 * The results contains the quotient value for a move of a cpu
945 	 * to, from and without any move.
946 	 *
947 	 * For a given configuration, for each cpu we make one JNI call
948 	 * to getLongProperty() (which is the most expensive call in this code)
949 	 * so the time spent in calculate() scales linearly with number of cpu.
950 	 *
951 	 * @param conf Configuration to be scored.
952 	 * @param move Move to be scored.
953 	 * @param elem The element to which the objective applies
954 	 * @throws Exception If an there is an error in execution.
955 	 */
calculate(Configuration conf, Move move, Element elem)956 	public double calculate(Configuration conf, Move move, Element elem)
957 	    throws PoolsException
958 	{
959 		KVExpression kve = (KVExpression) getExpression();
960 		double ret = 0;
961 		double qA = 0;
962 		double qB = 0;
963 		Resource pset = (Resource) elem;
964 		ComponentMove cm = (ComponentMove) move;
965 		Poold.MON_LOG.log(Severity.DEBUG,
966 		    "Calculating objective type: " + name + " for: " + elem);
967 
968 		/*
969 		 * If we are set to "none" then we don't care which
970 		 * configuration so just return 0.
971 		 */
972 		if (kve.getValue().compareTo("none") == 0)
973 			return (ret);
974 		/*
975 		 * If the maximum latency is 0, we don't care about
976 		 * latency.
977 		 */
978 		if (ldom.getMaxLatency() == 0)
979 			return (ret);
980 		/*
981 		 * If this element doesn't participate in the move, we
982 		 * should return 0.
983 		 */
984 		if (elem.equals(move.getFrom()) == false &&
985 		    elem.equals(move.getTo()) == false)
986 			return (ret);
987 
988                 /*
989                  * Populate the map of cpu - locality data if it is empty.
990                  */
991                 if (allCPUData.isEmpty()) {
992                     getCPUData();
993                 }
994 
995                 /*
996                  * Lookup in the pset results map if the pset entry exists.
997                  * If this pset entry exists then use it otherwise add it.
998                  */
999                 PSETData psetlg;
1000 
1001                 if (allPSETData.containsKey(pset))
1002                     psetlg = (PSETData) allPSETData.get(pset);
1003                 else {
1004                     psetlg = new PSETData(allLGroups, allCPUData, pset);
1005                     allPSETData.put(pset, psetlg);
1006                 }
1007 
1008                 /*
1009                  * Check the locality group of the cpu involved in this move.
1010                  * If it is a cpu from a locality group we have already seen,
1011                  * then we can retrieve the results from the pset results map.
1012                  */
1013                 List cpulist = (List) cm.getComponents();
1014                 Component cpu = (Component) cpulist.get(0);
1015 		int cpuid = (int) cpu.getLongProperty("cpu.sys_id");
1016                 LocalityGroup lgroup =
1017                         (LocalityGroup) allCPUData.get(new Integer(cpuid));
1018                 HashMap allresults = (HashMap) psetlg.getResults();
1019                 ResultTuple result = (ResultTuple) allresults.get(lgroup);
1020 
1021                 qB = psetlg.getAsIsTotal();
1022                 if (elem.equals(move.getFrom()))
1023                     qA = result.getFromResult();
1024                 else
1025                     qA = result.getToResult();
1026 
1027 		ret = qA - qB;
1028 
1029                 /*
1030                  * We return the value based on what locality objective
1031                  * we want to achieve - tight or loose. The calculations
1032                  * are based on tightness, so the value is reversed if the
1033                  * objective specified "loose" locality.
1034                  */
1035 		if (kve.getValue().compareTo("loose") == 0)
1036                     ret = 0 - ret;
1037                 Poold.MON_LOG.log(Severity.DEBUG, "ret: " + ret);
1038 		return (ret);
1039 	}
1040 }
1041 /**
1042  * A resource set utilization based objective which will assess moves
1043  * in terms of their (likely) impact on the future performance of a
1044  * resource set with respect to it's specified utilization objective.
1045  *
1046  * The utilization objective must be specified in terms of a
1047  * KVOpExpression, see the class definition for information about the
1048  * form of these expressions. The objective can be examined in terms
1049  * of it's compliance with the aid of a monitoring object. The actual
1050  * assessment of compliance is indicated by the associated monitoring
1051  * object, with this class simply acting as a co-ordinator of the
1052  * relevant information.
1053  */
1054 final class UtilizationObjective extends AbstractObjective
1055     implements WorkloadDependentObjective
1056 {
1057 	/**
1058 	 * The name of the class.
1059 	 */
1060 	static final String name = "utilization";
1061 
1062 	/**
1063 	 * Short run detection.
1064 	 */
1065 	private List zoneList = new LinkedList();
1066 
1067 	/**
1068 	 * Format for printing utilization.
1069 	 */
1070 	private static final DecimalFormat uf = new DecimalFormat("0.00");
1071 
1072 	/**
1073 	 * Solver used to calculate delta, i.e. gap, between target and
1074 	 * actual utilization values.
1075 	 */
1076 	private Solver gapSolver;
1077 
1078 	/**
1079 	 * Determine whether an objective is satisfied. If the
1080 	 * objective is still satisfied, return false; otherwise
1081 	 * return true.
1082 	 *
1083 	 * The assessment of control is made by the monitoring class
1084 	 * using the supplied Expression and resource.
1085 	 *
1086 	 * @param conf The configuration to be examined
1087 	 * @param solver The solving interface used to get utilization
1088 	 * information
1089 	 * @param elem The element to which the objective belongs
1090 	 *
1091 	 * @throws PoolsException if there is an error examining the
1092 	 * pool configuration
1093 	 * @throws StaleMonitorException if there is an error accessing
1094 	 * the element's ResourceMonitor
1095 	 */
examine(Configuration conf, Solver solver, Element elem)1096 	public boolean examine(Configuration conf, Solver solver,
1097 	    Element elem) throws PoolsException, StaleMonitorException
1098 	{
1099 		KVOpExpression kve = (KVOpExpression) getExpression();
1100 		ResourceMonitor mon;
1101 
1102 		/*
1103 		 * If there is no resource monitor, then we cannot
1104 		 * make an assessment of the objective's achievability.
1105 		 * Log a message to make clear that this objective is
1106 		 * not being assessed and then indicate that
1107 		 * the objective has been achieved.
1108 		 */
1109 		try {
1110 			mon = solver.getMonitor().get((Resource)elem);
1111 		} catch (StaleMonitorException sme) {
1112 			Poold.MON_LOG.log(Severity.INFO,
1113 			    elem.toString() +
1114 			    " utilization objective not measured " +
1115 			    toString() + " as there are no available " +
1116 			    "statistics.");
1117 			return (false);
1118 		}
1119 		gapSolver = solver;
1120 
1121 		double val = solver.getMonitor().getUtilization((Resource)elem);
1122 
1123 		StatisticList sl = (StatisticList) mon.get("utilization");
1124 		int zone = sl.getZone(kve, val);
1125 
1126 		if (zoneList.size() == 9) {
1127 			zoneList.remove(0);
1128 		}
1129 		zoneList.add(new Integer(sl.getZoneMean(val)));
1130 
1131 		/*
1132 		 * Evaluate whether or not this objective is under
1133 		 * control.
1134 		 */
1135 		if ((zone & StatisticOperations.ZONEZ) ==
1136 		    StatisticOperations.ZONEZ) {
1137 			/*
1138 			 * If the objective is GT or LT, then don't
1139 			 * return true as long as the objective is
1140 			 * satisfied.
1141 			 */
1142 			if (kve.getOp() == KVOpExpression.LT &&
1143 			    (zone & StatisticOperations.ZONET) ==
1144 			    StatisticOperations.ZONELT)
1145 				return (false);
1146 
1147 			if (kve.getOp() == KVOpExpression.GT &&
1148 			    (zone & StatisticOperations.ZONET) ==
1149 			    StatisticOperations.ZONEGT)
1150 				return (false);
1151 			Poold.MON_LOG.log(Severity.INFO,
1152 			    elem.toString() +
1153 			    " utilization objective not satisfied " +
1154 			    toString() + " with utilization " + uf.format(val) +
1155 			    " (control zone bounds exceeded)");
1156 			return (true);
1157 		}
1158 		/*
1159 		 * Check if our statistics need to be recalculated.
1160 		 */
1161 		checkShort(mon, elem, val);
1162 		return (false);
1163 	}
1164 
1165 	/**
1166 	 * Calculates the value of a configuration in terms of this
1167 	 * objective.
1168 	 *
1169 	 * Every set must be classified with a control zone when this
1170 	 * function is called. The move can be assessed in terms of
1171 	 * the control violation type. zone violations which are minor
1172 	 * are offered a lower contribution than more significant
1173 	 * violations.
1174 	 *
1175 	 * @param conf Configuration to be scored.
1176 	 * @param move Move to be scored.
1177 	 * @param elem The element to which the objective applies
1178 	 * @throws Exception If an there is an error in execution.
1179 	 */
calculate(Configuration conf, Move move, Element elem)1180 	public double calculate(Configuration conf, Move move, Element elem)
1181 	    throws PoolsException
1182 	{
1183 		KVOpExpression kve = (KVOpExpression) getExpression();
1184 		double ret;
1185 
1186 		/*
1187 		 * If the move is from the examined element, then
1188 		 * check to see if the recipient has any
1189 		 * objectives. If not, score the move poorly since we
1190 		 * should never want to transfer resources to a
1191 		 * recipient with no objectives. If there are
1192 		 * objectives, then return the delta between target
1193 		 * performance and actual performance for this
1194 		 * element.
1195 		 *
1196 		 * If the move is to the examined element, then check
1197 		 * to see if the donor has any objectives. If not,
1198 		 * score the move highly, since we want to favour
1199 		 * those resources with objectives. If there are
1200 		 * objectives, return the delta between actual and
1201 		 * target performance.
1202 		 *
1203 		 * If the element is neither the recipient or the
1204 		 * donor of this proposed move, then score the move
1205 		 * neutrally as 0.
1206 		 */
1207 		try {
1208 			double val, gap;
1209 			StatisticList sl;
1210 
1211 			if (elem.equals(move.getFrom())) {
1212 				val = gapSolver.getMonitor().
1213 				    getUtilization(move.getFrom());
1214 				sl = (StatisticList) gapSolver.getMonitor().
1215 				    get(move.getFrom()).get("utilization");
1216 				gap = sl.getGap(kve, val) / 100;
1217 
1218 				if (gapSolver.getObjectives(move.getTo()) ==
1219 				    null) {
1220 					/*
1221 					 * Moving to a resource with
1222 					 * no objectives should always
1223 					 * be viewed unfavourably. The
1224 					 * degree of favourability is
1225 					 * thus bound between 0 and
1226 					 * -1. If the source gap is
1227 					 * negative, then subtract it
1228 					 * from -1 to get the
1229 					 * score. If positive,
1230 					 * just return -1.
1231 					 */
1232 					    if (gap < 0) {
1233 						    ret = -1 - gap;
1234 					    } else {
1235 						    ret = -1;
1236 					    }
1237 				} else {
1238 					ret = 0 - gap;
1239 				}
1240 			} else if (elem.equals(move.getTo())) {
1241 				val = gapSolver.getMonitor().
1242 				    getUtilization(move.getTo());
1243 				sl = (StatisticList) gapSolver.getMonitor().
1244 				    get(move.getTo()).get("utilization");
1245 				gap = sl.getGap(kve, val) / 100;
1246 
1247 				if (gapSolver.getObjectives(move.getFrom()) ==
1248 				    null) {
1249 					/*
1250 					 * Moving from a resource with
1251 					 * no objectives should always
1252 					 * be viewed favourably. The
1253 					 * degree of favourability is
1254 					 * thus bound between 0 and
1255 					 * 1. If the destination gap
1256 					 * is negative, then add to 1
1257 					 * to get the score. If
1258 					 * positive, just return 1.
1259 					 */
1260 					if (gap < 0) {
1261 						ret = 0 - gap;
1262 					} else {
1263 						ret = 1;
1264 					}
1265 				} else {
1266 					ret = 0 + gap;
1267 				}
1268 			} else {
1269 				ret = 0;
1270 			}
1271 		} catch (StaleMonitorException sme) {
1272 			/*
1273 			 * We should always find a monitor,
1274 			 * but if we can't then just assume
1275 			 * this is a neutral move and return
1276 			 * 0.
1277 			 */
1278 			ret = 0;
1279 		}
1280 		Poold.MON_LOG.log(Severity.DEBUG, "ret: " + ret);
1281 		return (ret);
1282 	}
1283 
1284 	/**
1285 	 * Check whether or not a set's statistics are still useful
1286 	 * for making decision..
1287 	 *
1288 	 * Each set is controlled in terms of the zones of control
1289 	 * based in terms of standard deviations from a mean. If the
1290 	 * utilization of the set is not fluctuating normally around a
1291 	 * mean, these checks will cause the accumulated statistics to
1292 	 * be discarded and control suspended until a new sufficient
1293 	 * set of data is accumulated.
1294 	 *
1295 	 * @param mon Resource monitor to examine.
1296 	 * @param elem Element to which the resource monitor belongs.
1297 	 * @param val Latest monitored value.
1298 	 */
checkShort(ResourceMonitor mon, Element elem, double val)1299 	private void checkShort(ResourceMonitor mon, Element elem, double val)
1300 	{
1301 		boolean checkOne = true;
1302 		int checkOnePos = 0;
1303 		boolean doCheckOne = false;
1304 
1305 		Iterator itZones = zoneList.iterator();
1306 		while (itZones.hasNext()) {
1307 			int zone = ((Integer) itZones.next()).intValue();
1308 			if (doCheckOne) {
1309 				if (checkOne) {
1310 					if ((zone & StatisticOperations.ZONET)
1311 					    != checkOnePos) {
1312 						checkOne = false;
1313 					}
1314 				}
1315 			} else {
1316 				if (zoneList.size() >= 9) {
1317 					checkOnePos = zone &
1318 					    StatisticOperations.ZONET;
1319 					doCheckOne = true;
1320 				}
1321 			}
1322 		}
1323 		if (zoneList.size() >= 9 && checkOne) {
1324 			Poold.MON_LOG.log(Severity.INFO,
1325 			    elem.toString() +
1326 			    " utilization objective statistics reinitialized " +
1327 			    toString() + " with utilization " + uf.format(val) +
1328 			    " (nine points on same side of mean)");
1329 			mon.resetData("utilization");
1330 			zoneList.clear();
1331 		}
1332 	}
1333 }
1334