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