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 */ 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 */ 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 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 */ 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 */ 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 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 */ 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 */ 202 public void setStartingSampleCount(int sampleCount) 203 { 204 this.startingSampleCount = sampleCount; 205 } 206 207 /** 208 * sampleCount accessor. 209 */ 210 public int getStartingSampleCount() 211 { 212 return (startingSampleCount); 213 } 214 215 /** 216 * Stores the improvement, computed in a 217 * subclass-specific way. 218 */ 219 abstract public void setImprovementWithNewUtilization( 220 double newUtilization); 221 222 /** 223 * Allow subclasses to record the improvement. 224 */ 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 */ 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 */ 243 public final double getStartingUtilization() 244 { 245 return (startingUtilization); 246 } 247 248 public abstract int hashCode(); 249 public abstract boolean equals(Object o); 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 */ 257 public final int getUsage() 258 { 259 return (usage); 260 } 261 262 private final void incrementUsage() 263 { 264 usage++; 265 } 266 267 /** 268 * Returns the time this decision was created. 269 */ 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 */ 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 */ 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 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 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 400 public int hashCode() { 401 return (((((cpuid.hashCode() ^ 402 fromPsetName.hashCode()) ^ toPsetName.hashCode()) ^ 403 fromPsetComposition.hashCode()) ^ 404 toPsetComposition.hashCode()) ^ 405 utilizationClass.hashCode()); 406 } 407 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 */ 432 private String computeUtilizationClass( 433 double startingUtilization) 434 { 435 return "I"; 436 } 437 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 */ 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 */ 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 */ 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 */ 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 */ 522 public void sync(OutputStream os) throws IOException 523 { 524 new ObjectOutputStream(os).writeObject(this); 525 } 526 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 */ 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 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