1 /*
   2  * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /*
  25  * @test TestGCOld
  26  * @key gc
  27  * @key stress
  28  * @requires vm.gc=="null"
  29  * @summary Stress the GC by trying to make old objects more likely to be garbage than young objects.
  30  * @run main/othervm -Xmx384M -XX:+UseSerialGC TestGCOld 50 1 20 10 10000
  31  * @run main/othervm -Xmx384M -XX:+UseParallelGC TestGCOld 50 1 20 10 10000
  32  * @run main/othervm -Xmx384M -XX:+UseParallelGC -XX:-UseParallelOldGC TestGCOld 50 1 20 10 10000
  33  * @run main/othervm -Xmx384M -XX:+UseConcMarkSweepGC TestGCOld 50 1 20 10 10000
  34  * @run main/othervm -Xmx384M -XX:+UseG1GC TestGCOld 50 1 20 10 10000
  35  * @run main/othervm -Xms64m -Xmx128m -XX:+UseG1GC -XX:+UseDynamicNumberOfGCThreads -Xlog:gc,gc+task=trace TestGCOld 50 5 20 1 5000
  36  * @run main/othervm -Xms64m -Xmx128m -XX:+UseG1GC -XX:+UseDynamicNumberOfGCThreads  -XX:+UnlockDiagnosticVMOptions -XX:+InjectGCWorkerCreationFailure -Xlog:gc,gc+task=trace TestGCOld 50 5 20 1 5000
  37  */
  38 
  39 import java.text.*;
  40 import java.util.Random;
  41 
  42 class TreeNode {
  43     public TreeNode left, right;
  44     public int val;                // will always be the height of the tree
  45 }
  46 
  47 
  48 /* Args:
  49    live-data-size: in megabytes (approximate, will be rounded down).
  50    work: units of mutator non-allocation work per byte allocated,
  51      (in unspecified units.  This will affect the promotion rate
  52       printed at the end of the run: more mutator work per step implies
  53       fewer steps per second implies fewer bytes promoted per second.)
  54    short/long ratio: ratio of short-lived bytes allocated to long-lived
  55       bytes allocated.
  56    pointer mutation rate: number of pointer mutations per step.
  57    steps: number of steps to do.
  58 */
  59 
  60 public class TestGCOld {
  61 
  62   // Command-line parameters.
  63 
  64   private static int size, workUnits, promoteRate, ptrMutRate, steps;
  65 
  66   // Constants.
  67 
  68   private static final int MEG = 1000000;
  69   private static final int INSIGNIFICANT = 999; // this many bytes don't matter
  70   private static final int BYTES_PER_WORD = 4;
  71   private static final int BYTES_PER_NODE = 20; // bytes per TreeNode
  72   private static final int WORDS_DEAD = 100;    // size of young garbage object
  73 
  74   private final static int treeHeight = 14;
  75   private final static long treeSize = heightToBytes(treeHeight);
  76 
  77   private static final String msg1
  78     = "Usage: java TestGCOld <size> <work> <ratio> <mutation> <steps>";
  79   private static final String msg2
  80     = "  where <size> is the live storage in megabytes";
  81   private static final String msg3
  82     = "        <work> is the mutator work per step (arbitrary units)";
  83   private static final String msg4
  84     = "        <ratio> is the ratio of short-lived to long-lived allocation";
  85   private static final String msg5
  86     = "        <mutation> is the mutations per step";
  87   private static final String msg6
  88     = "        <steps> is the number of steps";
  89 
  90   // Counters (and global variables that discourage optimization)
  91 
  92   private static long youngBytes = 0;    // total young bytes allocated
  93   private static long nodes = 0;         // total tree nodes allocated
  94   private static long actuallyMut = 0;   // pointer mutations in old trees
  95   private static long mutatorSum = 0;    // checksum to discourage optimization
  96   public static int[] aexport;           // exported array to discourage opt
  97 
  98   // Global variables.
  99 
 100   private static TreeNode[] trees;
 101   private static int where = 0;               // roving index into trees
 102   private static Random rnd = new Random();
 103 
 104   // Returns the height of the given tree.
 105 
 106   private static int height (TreeNode t) {
 107     if (t == null) {
 108       return 0;
 109     }
 110     else {
 111       return 1 + Math.max (height (t.left), height (t.right));
 112     }
 113   }
 114 
 115   // Returns the length of the shortest path in the given tree.
 116 
 117   private static int shortestPath (TreeNode t) {
 118     if (t == null) {
 119       return 0;
 120     }
 121     else {
 122       return 1 + Math.min (shortestPath (t.left), shortestPath (t.right));
 123     }
 124   }
 125 
 126   // Returns the number of nodes in a balanced tree of the given height.
 127 
 128   private static long heightToNodes (int h) {
 129     if (h == 0) {
 130       return 0;
 131     }
 132     else {
 133       long n = 1;
 134       while (h > 1) {
 135         n = n + n;
 136         h = h - 1;
 137       }
 138       return n + n - 1;
 139     }
 140   }
 141 
 142   // Returns the number of bytes in a balanced tree of the given height.
 143 
 144   private static long heightToBytes (int h) {
 145     return BYTES_PER_NODE * heightToNodes (h);
 146   }
 147 
 148   // Returns the height of the largest balanced tree
 149   // that has no more than the given number of nodes.
 150 
 151   private static int nodesToHeight (long nodes) {
 152     int h = 1;
 153     long n = 1;
 154     while (n + n - 1 <= nodes) {
 155       n = n + n;
 156       h = h + 1;
 157     }
 158     return h - 1;
 159   }
 160 
 161   // Returns the height of the largest balanced tree
 162   // that occupies no more than the given number of bytes.
 163 
 164   private static int bytesToHeight (long bytes) {
 165     return nodesToHeight (bytes / BYTES_PER_NODE);
 166   }
 167 
 168   // Returns a newly allocated balanced binary tree of height h.
 169 
 170   private static TreeNode makeTree(int h) {
 171     if (h == 0) return null;
 172     else {
 173       TreeNode res = new TreeNode();
 174       nodes++;
 175       res.left = makeTree(h-1);
 176       res.right = makeTree(h-1);
 177       res.val = h;
 178       return res;
 179     }
 180   }
 181 
 182   // Allocates approximately size megabytes of trees and stores
 183   // them into a global array.
 184 
 185   private static void init() {
 186     int ntrees = (int) ((size * MEG) / treeSize);
 187     trees = new TreeNode[ntrees];
 188 
 189     System.err.println("Allocating " + ntrees + " trees.");
 190     System.err.println("  (" + (ntrees * treeSize) + " bytes)");
 191     for (int i = 0; i < ntrees; i++) {
 192       trees[i] = makeTree(treeHeight);
 193       // doYoungGenAlloc(promoteRate*ntrees*treeSize, WORDS_DEAD);
 194     }
 195     System.err.println("  (" + nodes + " nodes)");
 196 
 197     /* Allow any in-progress GC to catch up... */
 198     // try { Thread.sleep(20000); } catch (InterruptedException x) {}
 199   }
 200 
 201   // Confirms that all trees are balanced and have the correct height.
 202 
 203   private static void checkTrees() {
 204     int ntrees = trees.length;
 205     for (int i = 0; i < ntrees; i++) {
 206       TreeNode t = trees[i];
 207       int h1 = height(t);
 208       int h2 = shortestPath(t);
 209       if ((h1 != treeHeight) || (h2 != treeHeight)) {
 210         System.err.println("*****BUG: " + h1 + " " + h2);
 211       }
 212     }
 213   }
 214 
 215   // Called only by replaceTree (below) and by itself.
 216 
 217   private static void replaceTreeWork(TreeNode full, TreeNode partial, boolean dir) {
 218     boolean canGoLeft = full.left != null && full.left.val > partial.val;
 219     boolean canGoRight = full.right != null && full.right.val > partial.val;
 220     if (canGoLeft && canGoRight) {
 221       if (dir)
 222         replaceTreeWork(full.left, partial, !dir);
 223       else
 224         replaceTreeWork(full.right, partial, !dir);
 225     } else if (!canGoLeft && !canGoRight) {
 226       if (dir)
 227         full.left = partial;
 228       else
 229         full.right = partial;
 230     } else if (!canGoLeft) {
 231       full.left = partial;
 232     } else {
 233       full.right = partial;
 234     }
 235   }
 236 
 237   // Given a balanced tree full and a smaller balanced tree partial,
 238   // replaces an appropriate subtree of full by partial, taking care
 239   // to preserve the shape of the full tree.
 240 
 241   private static void replaceTree(TreeNode full, TreeNode partial) {
 242     boolean dir = (partial.val % 2) == 0;
 243     actuallyMut++;
 244     replaceTreeWork(full, partial, dir);
 245   }
 246 
 247   // Allocates approximately n bytes of long-lived storage,
 248   // replacing oldest existing long-lived storage.
 249 
 250   private static void oldGenAlloc(long n) {
 251     int full = (int) (n / treeSize);
 252     long partial = n % treeSize;
 253     // System.out.println("In oldGenAlloc, doing " + full + " full trees "
 254     // + "and one partial tree of size " + partial);
 255     for (int i = 0; i < full; i++) {
 256       trees[where++] = makeTree(treeHeight);
 257       if (where == trees.length) where = 0;
 258     }
 259     while (partial > INSIGNIFICANT) {
 260       int h = bytesToHeight(partial);
 261       TreeNode newTree = makeTree(h);
 262       replaceTree(trees[where++], newTree);
 263       if (where == trees.length) where = 0;
 264       partial = partial - heightToBytes(h);
 265     }
 266   }
 267 
 268   // Interchanges two randomly selected subtrees (of same size and depth).
 269 
 270   private static void oldGenSwapSubtrees() {
 271     // Randomly pick:
 272     //   * two tree indices
 273     //   * A depth
 274     //   * A path to that depth.
 275     int index1 = rnd.nextInt(trees.length);
 276     int index2 = rnd.nextInt(trees.length);
 277     int depth = rnd.nextInt(treeHeight);
 278     int path = rnd.nextInt();
 279     TreeNode tn1 = trees[index1];
 280     TreeNode tn2 = trees[index2];
 281     for (int i = 0; i < depth; i++) {
 282       if ((path & 1) == 0) {
 283         tn1 = tn1.left;
 284         tn2 = tn2.left;
 285       } else {
 286         tn1 = tn1.right;
 287         tn2 = tn2.right;
 288       }
 289       path >>= 1;
 290     }
 291     TreeNode tmp;
 292     if ((path & 1) == 0) {
 293       tmp = tn1.left;
 294       tn1.left = tn2.left;
 295       tn2.left = tmp;
 296     } else {
 297       tmp = tn1.right;
 298       tn1.right = tn2.right;
 299       tn2.right = tmp;
 300     }
 301     actuallyMut += 2;
 302   }
 303 
 304   // Update "n" old-generation pointers.
 305 
 306   private static void oldGenMut(long n) {
 307     for (int i = 0; i < n/2; i++) {
 308       oldGenSwapSubtrees();
 309     }
 310   }
 311 
 312   // Does the amount of mutator work appropriate for n bytes of young-gen
 313   // garbage allocation.
 314 
 315   private static void doMutWork(long n) {
 316     int sum = 0;
 317     long limit = workUnits*n/10;
 318     for (long k = 0; k < limit; k++) sum++;
 319     // We don't want dead code elimination to eliminate the loop above.
 320     mutatorSum = mutatorSum + sum;
 321   }
 322 
 323   // Allocate n bytes of young-gen garbage, in units of "nwords"
 324   // words.
 325 
 326   private static void doYoungGenAlloc(long n, int nwords) {
 327     final int nbytes = nwords*BYTES_PER_WORD;
 328     int allocated = 0;
 329     while (allocated < n) {
 330       aexport = new int[nwords];
 331       /* System.err.println("Step"); */
 332       allocated += nbytes;
 333     }
 334     youngBytes = youngBytes + allocated;
 335   }
 336 
 337   // Allocate "n" bytes of young-gen data; and do the
 338   // corresponding amount of old-gen allocation and pointer
 339   // mutation.
 340 
 341   // oldGenAlloc may perform some mutations, so this code
 342   // takes those mutations into account.
 343 
 344   private static void doStep(long n) {
 345     long mutations = actuallyMut;
 346 
 347     doYoungGenAlloc(n, WORDS_DEAD);
 348     doMutWork(n);
 349     oldGenAlloc(n / promoteRate);
 350     oldGenMut(Math.max(0L, (mutations + ptrMutRate) - actuallyMut));
 351   }
 352 
 353   public static void main(String[] args) {
 354     if (args.length != 5) {
 355       System.err.println(msg1);
 356       System.err.println(msg2);
 357       System.err.println(msg3);
 358       System.err.println(msg4);
 359       System.err.println(msg5);
 360       System.err.println(msg6);
 361       return;
 362     }
 363 
 364     size = Integer.parseInt(args[0]);
 365     workUnits = Integer.parseInt(args[1]);
 366     promoteRate = Integer.parseInt(args[2]);
 367     ptrMutRate = Integer.parseInt(args[3]);
 368     steps = Integer.parseInt(args[4]);
 369 
 370     System.out.println(size + " megabytes of live storage");
 371     System.out.println(workUnits + " work units per step");
 372     System.out.println("promotion ratio is 1:" + promoteRate);
 373     System.out.println("pointer mutation rate is " + ptrMutRate);
 374     System.out.println(steps + " steps");
 375 
 376     init();
 377 //  checkTrees();
 378     youngBytes = 0;
 379     nodes = 0;
 380 
 381     System.err.println("Initialization complete...");
 382 
 383     long start = System.currentTimeMillis();
 384 
 385     for (int step = 0; step < steps; step++) {
 386       doStep(MEG);
 387     }
 388 
 389     long end = System.currentTimeMillis();
 390     float secs = ((float)(end-start))/1000.0F;
 391 
 392 //  checkTrees();
 393 
 394     NumberFormat nf = NumberFormat.getInstance();
 395     nf.setMaximumFractionDigits(1);
 396     System.out.println("\nTook " + nf.format(secs) + " sec in steady state.");
 397     nf.setMaximumFractionDigits(2);
 398     System.out.println("Allocated " + steps + " Mb of young gen garbage"
 399                        + " (= " + nf.format(((float)steps)/secs) +
 400                        " Mb/sec)");
 401     System.out.println("    (actually allocated " +
 402                        nf.format(((float) youngBytes)/MEG) + " megabytes)");
 403     float promoted = ((float)steps) / (float)promoteRate;
 404     System.out.println("Promoted " + promoted +
 405                        " Mb (= " + nf.format(promoted/secs) + " Mb/sec)");
 406     System.out.println("    (actually promoted " +
 407                        nf.format(((float) (nodes * BYTES_PER_NODE))/MEG) +
 408                        " megabytes)");
 409     if (ptrMutRate != 0) {
 410       System.out.println("Mutated " + actuallyMut +
 411                          " pointers (= " +
 412                          nf.format(actuallyMut/secs) + " ptrs/sec)");
 413 
 414     }
 415     // This output serves mainly to discourage optimization.
 416     System.out.println("Checksum = " + (mutatorSum + aexport.length));
 417 
 418   }
 419 }