xref: /illumos-gate/usr/src/cmd/pools/poold/com/sun/solaris/domain/pools/DecisionHistory.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.util.*;
33 import java.text.SimpleDateFormat;
34 
35 import com.sun.solaris.service.logging.*;
36 import com.sun.solaris.service.pools.*;
37 
38 /**
39  * This class maintains history about previous decisions.  It can be
40  * used to ratify that a decision made on the basis of observed behavior
41  * over a limited time was historically shown to not degrade
42  * performance.  The class maintains historical data in a history file.
43  * The format of this data is project-private and very likely to change
44  * as the implementation improves.
45  */
46 public final class DecisionHistory implements Serializable {
47 	/**
48 	 * The number of samples which a decision will be remembered.
49 	 */
50 	public static final int DECISION_LIFETIME = 256;
51 
52 	/**
53 	 * Map of values of historical decisions.
54 	 */
55 	private HashMap decisions = new HashMap();
56 
57 	/**
58 	 * Map of resources to be monitored for improvement in
59 	 * utilization to the corresponding decision.  Maps Resources to
60 	 * their decision's key string.
61 	 */
62 	private transient HashMap resourcesAwaitingImprovement = new HashMap();
63 
64 	/**
65 	 * List of decisions, in order of creation, to manage expiry.
66 	 */
67 	private transient LinkedList decisionList = new LinkedList();
68 
69 	/**
70 	 * Constructor.
71 	 */
DecisionHistory()72 	public DecisionHistory()
73 	{
74 	}
75 
76 	/**
77 	 * Record a decision that's been made regarding a processor.
78 	 * Such a decision is a (cpuid, from-pset-name, to-pset-name,
79 	 * (from-pset-composition), (to-pset-composition),
80 	 * original-utilization-class) tuple.
81 	 */
recordProcessorMove(ComponentMove move, double startingUtilization, int sampleCount)82 	public void recordProcessorMove(ComponentMove move,
83 	    double startingUtilization, int sampleCount) throws PoolsException
84 	{
85 		Decision decision = Decision.forMove(move, startingUtilization);
86 		decision.setStartingSampleCount(sampleCount);
87 		Object o = decisions.put(decision.getKey(), decision);
88 		Poold.OPT_LOG.log(Severity.DEBUG, "recorded decision (" +
89 		    decision + ")" + (o == null ? "" : " (displaced " + o +
90 		    ")"));
91 
92 		/*
93 		 * Remember the most-recently-made decision regarding a
94 		 * resource until the next utilization sample is taken,
95 		 * so the next solve() may then reocrd the improvement.
96 		 * If another decision is made regarding this resource,
97 		 * the previous ones are forgotten, and their
98 		 * improvement fields are left 0.
99 		 */
100 		resourcesAwaitingImprovement.put(move.getTo(),
101 		    decision.getKey());
102 		decisionList.add(decision);
103 	}
104 
recordImprovementWithUtilization(Resource resource, double utilization)105 	private void recordImprovementWithUtilization(Resource resource,
106 	    double utilization)
107 	{
108 		String decisionKey = (String)resourcesAwaitingImprovement.get(
109 		    resource);
110 
111 		if (decisionKey != null) {
112 			Decision decision = (Decision)decisions.get(
113 			    decisionKey);
114 			if (decision != null) {
115 				decision.setImprovementWithNewUtilization(
116 				    utilization);
117 				Poold.OPT_LOG.log(Severity.DEBUG, resource +
118 				    " improvement measured for decision " +
119 				    decision.describe());
120 			}
121 		}
122 	}
123 
124 	/**
125 	 * A Decision boils down to a tuple describing the resource
126 	 * configuration involved before and after a particular resource
127 	 * is moved.  We use a textual representation to describe the
128 	 * decision, by value, to avoid holding references to any of the
129 	 * actual resources involved.
130 	 */
131 	private static abstract class Decision implements Serializable {
132 		/**
133 		 * Utilization of the resource before the move was made.
134 		 */
135 		private double startingUtilization = 0.0;
136 
137 		/**
138 		 * Improvement in utilization (-1..1) after the move was
139 		 * made, if the determination is made.
140 		 */
141 		private double improvement = 0.0;
142 
143 		/**
144 		 * Number of times this decision has been reexamined.
145 		 */
146 		private int usage = 0;
147 
148 		/**
149 		 * Monitor's sample count when the decision was made,
150 		 * used to expire this decision after DECISION_LIFETIME
151 		 * samples.
152 		 */
153 		private int startingSampleCount;
154 
155 		/**
156 		 * Decision's creation time.
157 		 */
158 		private Date date;
159 
160 		/**
161 		 * Returns a String key for this Decision.
162 		 */
getKey()163 		public abstract String getKey();
164 
165 		/**
166 		 * Returns a Decision corresponding to a given Move.
167 		 * @return a Decision corresponding to a given Move.
168 		 * @throws InvalidArgumentException if there is no
169 		 * Decision type corresponding to the move.
170 		 */
forMove(Move move, double startingUtilization)171 		public static final Decision forMove(Move move,
172 		    double startingUtilization)
173 		{
174 			if (move instanceof ComponentMove)
175 				return (new ComponentMoveDecision(
176 				    (ComponentMove)move, startingUtilization));
177 			else
178 				return (null);
179 		}
180 
Decision()181 		private Decision()
182 		{
183 			date = new Date();
184 		}
185 
186 		/**
187 		 * Invoked after construction, sets the utilization
188 		 * corresponding to the affected resource before the move
189 		 * was made.
190 		 */
setStartingUtilization( double startingUtilization)191 		public final void setStartingUtilization(
192 		    double startingUtilization)
193 		{
194 			this.startingUtilization = startingUtilization;
195 		}
196 
197 		/**
198 		 * Invoked after construction, sets the sampleCount from
199 		 * the monitor, used to expire this decision after
200 		 * DECISION_LIFETIME samples.
201 		 */
setStartingSampleCount(int sampleCount)202 		public void setStartingSampleCount(int sampleCount)
203 		{
204 			this.startingSampleCount = sampleCount;
205 		}
206 
207 		/**
208 		 * sampleCount accessor.
209 		 */
getStartingSampleCount()210 		public int getStartingSampleCount()
211 		{
212 			return (startingSampleCount);
213 		}
214 
215 		/**
216 		 * Stores the improvement, computed in a
217 		 * subclass-specific way.
218 		 */
setImprovementWithNewUtilization( double newUtilization)219 		abstract public void setImprovementWithNewUtilization(
220 		    double newUtilization);
221 
222 		/**
223 		 * Allow subclasses to record the improvement.
224 		 */
setImprovement(double improvement)225 		protected void setImprovement(double improvement)
226 		{
227 			this.improvement = improvement;
228 		}
229 
230 		/**
231 		 * Returns the improvement in utilization measured by
232 		 * the monitor after the move is made.
233 		 */
getImprovement()234 		public final double getImprovement()
235 		{
236 			return (improvement);
237 		}
238 
239 		/**
240 		 * Returns the utilization corresponding to the affected
241 		 * resource before the move was made.
242 		 */
getStartingUtilization()243 		public final double getStartingUtilization()
244 		{
245 			return (startingUtilization);
246 		}
247 
hashCode()248 		public abstract int hashCode();
equals(Object o)249 		public abstract boolean equals(Object o);
toString()250 		public abstract String toString();
251 
252 		private static final long serialVersionUID = 0x7860687;
253 
254 		/**
255 		 * Number of times this decision has been reexamined.
256 		 */
getUsage()257 		public final int getUsage()
258 		{
259 			return (usage);
260 		}
261 
incrementUsage()262 		private final void incrementUsage()
263 		{
264 			usage++;
265 		}
266 
267 		/**
268 		 * Returns the time this decision was created.
269 		 */
getDate()270 		public final Date getDate()
271 		{
272 			return date;
273 		}
274 
275 		/**
276 		 * Formatter for printing creation date.
277 		 */
278 		private static SimpleDateFormat dateFormatter;
279 
280 		/**
281 		 * Format for printing creation date.
282 		 */
283 		private final static String dateFormat = "MMM d kk:mm:ss";
284 
285 		/**
286 		 * Returns a more comprehensive textual representation
287 		 * of this devision than toString().
288 		 */
describe()289 		public final String describe()
290 		{
291 			if (dateFormatter == null)
292 				dateFormatter = new SimpleDateFormat(
293 				    dateFormat);
294 			return (toString() + " made at " +
295 			    dateFormatter.format(getDate()) +
296 			    " with improvement " + getImprovement() +
297 			    " used " + getUsage() + " times");
298 		}
299 	}
300 
301 	/**
302 	 * A Decision affecting the transfer of one CPU between
303 	 * processor sets.
304 	 */
305 	private static final class ComponentMoveDecision extends Decision {
306 		/**
307 		 * The CPU Id of the involved CPU.
308 		 */
309 		private String cpuid;
310 
311 		/**
312 		 * The name of the donating processor set.
313 		 */
314 		private String fromPsetName;
315 
316 		/**
317 		 * The name of the receiving processor set.
318 		 */
319 		private String toPsetName;
320 
321 		/**
322 		 * The string representation of the list of CPU IDs
323 		 * composing the donating set.
324 		 */
325 		private String fromPsetComposition;
326 
327 		/**
328 		 * The string representation of the list of CPU IDs
329 		 * composing the receiving set.
330 		 */
331 		private String toPsetComposition;
332 
333 		/**
334 		 * The number of CPUs in the receiving set, after the
335 		 * move is made.
336 		 */
337 		private int toPsetSize;
338 
339 		/**
340 		 * A Decision-subclass-specific utilization group.
341 		 */
342 		private String utilizationClass;
343 
344 		/**
345 		 * Constructs a ComponentMoveDecision based on the
346 		 * ComponentMove.
347 		 * @throws IllegalArgumentException if the ComponentMove
348 		 * can't be interpreted.
349 		 */
ComponentMoveDecision(ComponentMove move, double startingUtilization)350 		public ComponentMoveDecision(ComponentMove move,
351 		    double startingUtilization) throws IllegalArgumentException
352 		{
353 			try {
354 				cpuid = move.getComponents().toString();
355 				fromPsetName = move.getFrom().toString();
356 				toPsetName = move.getTo().toString();
357 				fromPsetComposition = move.getFrom()
358 				    .getComponents(null).toString();
359 				toPsetComposition = move.getTo()
360 				    .getComponents(null).toString();
361 				toPsetSize = move.getTo().getComponents(null)
362 				    .size();
363 				utilizationClass = computeUtilizationClass(
364 				    startingUtilization);
365 				setStartingUtilization(startingUtilization);
366 			} catch (PoolsException pe) {
367 				throw(IllegalArgumentException)(
368 				    new IllegalArgumentException().initCause(
369 				    pe));
370 			}
371 		}
372 
getKey()373 		public String getKey()
374 		{
375 			StringBuffer sb = new StringBuffer();
376 
377 			sb.append(cpuid);
378 			sb.append(", ");
379 			sb.append(fromPsetName);
380 			sb.append(", ");
381 			sb.append(toPsetName);
382 
383 			return (sb.toString());
384 		}
385 
setImprovementWithNewUtilization( double newUtilization)386 		public void setImprovementWithNewUtilization(
387 		    double newUtilization)
388 		{
389 			double sizeRatio = (double)(toPsetSize - 1) /
390 			    toPsetSize;
391 			double expectedUtilization = sizeRatio *
392 			    getStartingUtilization();
393 
394 			Poold.OPT_LOG.log(Severity.DEBUG,
395 			    "pset improvement calculation expected " +
396 			    expectedUtilization + ", got " + newUtilization);
397 			setImprovement(newUtilization - expectedUtilization);
398 		}
399 
hashCode()400 		public int hashCode() {
401 			return (((((cpuid.hashCode() ^
402 			    fromPsetName.hashCode()) ^ toPsetName.hashCode()) ^
403 			    fromPsetComposition.hashCode()) ^
404 			    toPsetComposition.hashCode()) ^
405 			    utilizationClass.hashCode());
406 		}
407 
equals(Object o)408 		public boolean equals(Object o) {
409 			if (!(o instanceof ComponentMoveDecision))
410 				return false;
411 			else {
412 				ComponentMoveDecision cmd =
413 				    (ComponentMoveDecision)o;
414 				return (cpuid.equals(cmd.cpuid) &&
415 				    fromPsetName.equals(cmd.fromPsetName) &&
416 				    toPsetName.equals(cmd.toPsetName) &&
417 				    fromPsetComposition.equals(
418 				    cmd.fromPsetComposition) &&
419 				    toPsetComposition.equals(
420 				    cmd.toPsetComposition) &&
421 				    utilizationClass.equals(
422 				    cmd.utilizationClass));
423 			}
424 		}
425 
426 		/**
427 		 * Returns the group that this decision's utilization
428 		 * falls into.  Presently, there is only one group, but
429 		 * ostensibly decisions will later be grouped (e.g.
430 		 * into control-zone-wide groups).
431 		 */
computeUtilizationClass( double startingUtilization)432 		private String computeUtilizationClass(
433 		    double startingUtilization)
434 		{
435 			return "I";
436 		}
437 
toString()438 		public String toString()
439 		{
440 			StringBuffer sb = new StringBuffer();
441 
442 			sb.append(cpuid.toString());
443 			sb.append(", ");
444 			sb.append(fromPsetName.toString());
445 			sb.append(", ");
446 			sb.append(toPsetName.toString());
447 			sb.append(", ");
448 			sb.append(fromPsetComposition.toString());
449 			sb.append(", ");
450 			sb.append(toPsetComposition.toString());
451 			sb.append(", ");
452 			sb.append(utilizationClass.toString());
453 
454 			return (sb.toString());
455 		}
456 
457 		private static final long serialVersionUID = 0xf7860687;
458 	}
459 
460 	/**
461 	 * Vetoes a Move only if there is a prior decision that showed a
462 	 * degradation in resource utilization.
463 	 */
veto(Move m, double utilization)464 	public boolean veto(Move m, double utilization)
465 	{
466 		Decision current = Decision.forMove(m, utilization);
467 		Decision past;
468 
469 		if (current != null) {
470 			past = (Decision)decisions.get(current.getKey());
471 			if (past != null)
472 				past.incrementUsage();
473 			if (past != null && past.getImprovement() < 0.0) {
474 				Poold.OPT_LOG.log(Severity.DEBUG, m +
475 				    " vetoed by decision " + past.describe());
476 				return true;
477 			}
478 		}
479 
480 		return false;
481 	}
482 
483 	private static final long serialVersionUID = 0xf7860687;
484 
485 	/**
486 	 * Synchronize the decision history with the persistent version.
487 	 */
loadFromFile(String path)488 	public static DecisionHistory loadFromFile(String path)
489 	    throws IOException, ClassNotFoundException
490 	{
491 		return (load(new FileInputStream(path)));
492 	}
493 
494 	/**
495 	 * Synchronize the persistent decision history with the present
496 	 * history.
497 	 */
syncToFile(String path)498 	public void syncToFile(String path) throws IOException
499 	{
500 		FileOutputStream fos = new FileOutputStream(path);
501 		sync(fos);
502 		fos.close();
503 	}
504 
505 	/**
506 	 * Synchronize the decision history with the persistent version,
507 	 * from the given stream.
508 	 */
load(InputStream is)509 	public static DecisionHistory load(InputStream is)
510 	    throws IOException, ClassNotFoundException
511 	{
512 		ObjectInputStream ois = new ObjectInputStream(is);
513 
514 		DecisionHistory dh = (DecisionHistory)ois.readObject();
515 		return (dh);
516 	}
517 
518 	/**
519 	 * Serialize the persistent decision history to the given
520 	 * stream.
521 	 */
sync(OutputStream os)522 	public void sync(OutputStream os) throws IOException
523 	{
524 		new ObjectOutputStream(os).writeObject(this);
525 	}
526 
toString()527 	public String toString()
528 	{
529 		StringBuffer sb = new StringBuffer();
530 
531 		sb.append(decisions.keySet().size() + " decisions {");
532 		Iterator it = decisions.keySet().iterator();
533 		while (it.hasNext()) {
534 			String dk = (String)it.next();
535 			Decision d = (Decision)decisions.get(dk);
536 
537 			sb.append("\t(");
538 			sb.append(d.describe());
539 			sb.append(")\n");
540 		}
541 		sb.append("}");
542 
543 		return (sb.toString());
544 	}
545 
546 	/**
547 	 * Measures the improvement in utilization of any resource for
548 	 * which a decision was recently made.
549 	 */
expireAndMeasureImprovements(Monitor mon)550 	public void expireAndMeasureImprovements(Monitor mon)
551 	{
552 		/*
553 		 * Measure the improvement in resources involved in
554 		 * recent decisions.
555 		 */
556 		if (mon.isValid()) {
557 			for (Iterator it = resourcesAwaitingImprovement.
558 			    keySet().iterator(); it.hasNext(); ) {
559 				Resource res = (Resource)it.next();
560 				try {
561 					double utilization = mon.
562 					    getUtilization(res);
563 					recordImprovementWithUtilization(res,
564 					    utilization);
565 				} catch (StaleMonitorException sme) {
566 					/*
567 					 * We can't access the utilization, so
568 					 * remove the decision.
569 					 */
570 					String decisionKey = (String)
571 					    resourcesAwaitingImprovement.
572 					    get(res);
573 					if (decisionKey != null)
574 						decisions.remove(decisionKey);
575 				}
576 				it.remove();
577 			}
578 		}
579 
580 		/*
581 		 * Expire decisions which have outlived
582 		 * DECISION_LIFETIME samples.
583 		 */
584 		int cutoff = mon.getSampleCount() - DECISION_LIFETIME;
585 		if (cutoff > 0) {
586 			Decision decision;
587 			ListIterator it = decisionList.listIterator(0);
588 			while (it.hasNext()) {
589 				decision = (Decision)it.next();
590 				int sc = decision.getStartingSampleCount();
591 				if (sc < cutoff) {
592 					if (sc > 0) {
593 						Poold.OPT_LOG.log(
594 						    Severity.DEBUG,
595 						    "expiring decision (" +
596 						    decision + ")");
597 						it.remove();
598 						decisions.remove(
599 						    decision.getKey());
600 					}
601 				} else
602 					break;
603 			}
604 		}
605 	}
606 
readObject(ObjectInputStream s)607 	private void readObject(ObjectInputStream s)
608 	    throws IOException, ClassNotFoundException
609 	{
610 		s.defaultReadObject();
611 
612 		resourcesAwaitingImprovement = new HashMap();
613 		decisionList = new LinkedList();
614 		for (Iterator it = decisions.keySet().iterator();
615 		    it.hasNext(); ) {
616 			String decisionKey = (String)it.next();
617 			Decision decision = (Decision)decisions.get(
618 			    decisionKey);
619 			decision.setStartingSampleCount(0);
620 			decisionList.add(decision);
621 		}
622 	}
623 }
624