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  */

    36 

    37 import java.text.*;

    38 import java.util.Random;

    39 

    40 class TreeNode {

    41     public TreeNode left, right;

    42     public int val;                // will always be the height of the tree

    43 }

    44 

    45 

    46 /* Args:

    47    live-data-size: in megabytes (approximate, will be rounded down).

    48    work: units of mutator non-allocation work per byte allocated,

    49      (in unspecified units.  This will affect the promotion rate

    50       printed at the end of the run: more mutator work per step implies

    51       fewer steps per second implies fewer bytes promoted per second.)

    52    short/long ratio: ratio of short-lived bytes allocated to long-lived

    53       bytes allocated.

    54    pointer mutation rate: number of pointer mutations per step.

    55    steps: number of steps to do.

    56 */

    57 

    58 public class TestGCOld {

    59 

    60   // Command-line parameters.

    61 

    62   private static int size, workUnits, promoteRate, ptrMutRate, steps;

    63 

    64   // Constants.

    65 

    66   private static final int MEG = 1000000;

    67   private static final int INSIGNIFICANT = 999; // this many bytes don't matter

    68   private static final int BYTES_PER_WORD = 4;

    69   private static final int BYTES_PER_NODE = 20; // bytes per TreeNode

    70   private static final int WORDS_DEAD = 100;    // size of young garbage object

    71 

    72   private final static int treeHeight = 14;

    73   private final static long treeSize = heightToBytes(treeHeight);

    74 

    75   private static final String msg1

    76     = "Usage: java TestGCOld <size> <work> <ratio> <mutation> <steps>";

    77   private static final String msg2

    78     = "  where <size> is the live storage in megabytes";

    79   private static final String msg3

    80     = "        <work> is the mutator work per step (arbitrary units)";

    81   private static final String msg4

    82     = "        <ratio> is the ratio of short-lived to long-lived allocation";

    83   private static final String msg5

    84     = "        <mutation> is the mutations per step";

    85   private static final String msg6

    86     = "        <steps> is the number of steps";

    87 

    88   // Counters (and global variables that discourage optimization)

    89 

    90   private static long youngBytes = 0;    // total young bytes allocated

    91   private static long nodes = 0;         // total tree nodes allocated

    92   private static long actuallyMut = 0;   // pointer mutations in old trees

    93   private static long mutatorSum = 0;    // checksum to discourage optimization

    94   public static int[] aexport;           // exported array to discourage opt

    95 

    96   // Global variables.

    97 

    98   private static TreeNode[] trees;

    99   private static int where = 0;               // roving index into trees

   100   private static Random rnd = new Random();

   101 

   102   // Returns the height of the given tree.

   103 

   104   private static int height (TreeNode t) {

   105     if (t == null) {

   106       return 0;

   107     }

   108     else {

   109       return 1 + Math.max (height (t.left), height (t.right));

   110     }

   111   }

   112 

   113   // Returns the length of the shortest path in the given tree.

   114 

   115   private static int shortestPath (TreeNode t) {

   116     if (t == null) {

   117       return 0;

   118     }

   119     else {

   120       return 1 + Math.min (shortestPath (t.left), shortestPath (t.right));

   121     }

   122   }

   123 

   124   // Returns the number of nodes in a balanced tree of the given height.

   125 

   126   private static long heightToNodes (int h) {

   127     if (h == 0) {

   128       return 0;

   129     }

   130     else {

   131       long n = 1;

   132       while (h > 1) {

   133         n = n + n;

   134         h = h - 1;

   135       }

   136       return n + n - 1;

   137     }

   138   }

   139 

   140   // Returns the number of bytes in a balanced tree of the given height.

   141 

   142   private static long heightToBytes (int h) {

   143     return BYTES_PER_NODE * heightToNodes (h);

   144   }

   145 

   146   // Returns the height of the largest balanced tree

   147   // that has no more than the given number of nodes.

   148 

   149   private static int nodesToHeight (long nodes) {

   150     int h = 1;

   151     long n = 1;

   152     while (n + n - 1 <= nodes) {

   153       n = n + n;

   154       h = h + 1;

   155     }

   156     return h - 1;

   157   }

   158 

   159   // Returns the height of the largest balanced tree

   160   // that occupies no more than the given number of bytes.

   161 

   162   private static int bytesToHeight (long bytes) {

   163     return nodesToHeight (bytes / BYTES_PER_NODE);

   164   }

   165 

   166   // Returns a newly allocated balanced binary tree of height h.

   167 

   168   private static TreeNode makeTree(int h) {

   169     if (h == 0) return null;

   170     else {

   171       TreeNode res = new TreeNode();

   172       nodes++;

   173       res.left = makeTree(h-1);

   174       res.right = makeTree(h-1);

   175       res.val = h;

   176       return res;

   177     }

   178   }

   179 

   180   // Allocates approximately size megabytes of trees and stores

   181   // them into a global array.

   182 

   183   private static void init() {

   184     int ntrees = (int) ((size * MEG) / treeSize);

   185     trees = new TreeNode[ntrees];

   186 

   187     System.err.println("Allocating " + ntrees + " trees.");

   188     System.err.println("  (" + (ntrees * treeSize) + " bytes)");

   189     for (int i = 0; i < ntrees; i++) {

   190       trees[i] = makeTree(treeHeight);

   191       // doYoungGenAlloc(promoteRate*ntrees*treeSize, WORDS_DEAD);

   192     }

   193     System.err.println("  (" + nodes + " nodes)");

   194 

   195     /* Allow any in-progress GC to catch up... */

   196     // try { Thread.sleep(20000); } catch (InterruptedException x) {}

   197   }

   198 

   199   // Confirms that all trees are balanced and have the correct height.

   200 

   201   private static void checkTrees() {

   202     int ntrees = trees.length;

   203     for (int i = 0; i < ntrees; i++) {

   204       TreeNode t = trees[i];

   205       int h1 = height(t);

   206       int h2 = shortestPath(t);

   207       if ((h1 != treeHeight) || (h2 != treeHeight)) {

   208         System.err.println("*****BUG: " + h1 + " " + h2);

   209       }

   210     }

   211   }

   212 

   213   // Called only by replaceTree (below) and by itself.

   214 

   215   private static void replaceTreeWork(TreeNode full, TreeNode partial, boolean dir) {

   216     boolean canGoLeft = full.left != null && full.left.val > partial.val;

   217     boolean canGoRight = full.right != null && full.right.val > partial.val;

   218     if (canGoLeft && canGoRight) {

   219       if (dir)

   220         replaceTreeWork(full.left, partial, !dir);

   221       else

   222         replaceTreeWork(full.right, partial, !dir);

   223     } else if (!canGoLeft && !canGoRight) {

   224       if (dir)

   225         full.left = partial;

   226       else

   227         full.right = partial;

   228     } else if (!canGoLeft) {

   229       full.left = partial;

   230     } else {

   231       full.right = partial;

   232     }

   233   }

   234 

   235   // Given a balanced tree full and a smaller balanced tree partial,

   236   // replaces an appropriate subtree of full by partial, taking care

   237   // to preserve the shape of the full tree.

   238 

   239   private static void replaceTree(TreeNode full, TreeNode partial) {

   240     boolean dir = (partial.val % 2) == 0;

   241     actuallyMut++;

   242     replaceTreeWork(full, partial, dir);

   243   }

   244 

   245   // Allocates approximately n bytes of long-lived storage,

   246   // replacing oldest existing long-lived storage.

   247 

   248   private static void oldGenAlloc(long n) {

   249     int full = (int) (n / treeSize);

   250     long partial = n % treeSize;

   251     // System.out.println("In oldGenAlloc, doing " + full + " full trees "

   252     // + "and one partial tree of size " + partial);

   253     for (int i = 0; i < full; i++) {

   254       trees[where++] = makeTree(treeHeight);

   255       if (where == trees.length) where = 0;

   256     }

   257     while (partial > INSIGNIFICANT) {

   258       int h = bytesToHeight(partial);

   259       TreeNode newTree = makeTree(h);

   260       replaceTree(trees[where++], newTree);

   261       if (where == trees.length) where = 0;

   262       partial = partial - heightToBytes(h);

   263     }

   264   }

   265 

   266   // Interchanges two randomly selected subtrees (of same size and depth).

   267 

   268   private static void oldGenSwapSubtrees() {

   269     // Randomly pick:

   270     //   * two tree indices

   271     //   * A depth

   272     //   * A path to that depth.

   273     int index1 = rnd.nextInt(trees.length);

   274     int index2 = rnd.nextInt(trees.length);

   275     int depth = rnd.nextInt(treeHeight);

   276     int path = rnd.nextInt();

   277     TreeNode tn1 = trees[index1];

   278     TreeNode tn2 = trees[index2];

   279     for (int i = 0; i < depth; i++) {

   280       if ((path & 1) == 0) {

   281         tn1 = tn1.left;

   282         tn2 = tn2.left;

   283       } else {

   284         tn1 = tn1.right;

   285         tn2 = tn2.right;

   286       }

   287       path >>= 1;

   288     }

   289     TreeNode tmp;

   290     if ((path & 1) == 0) {

   291       tmp = tn1.left;

   292       tn1.left = tn2.left;

   293       tn2.left = tmp;

   294     } else {

   295       tmp = tn1.right;

   296       tn1.right = tn2.right;

   297       tn2.right = tmp;

   298     }

   299     actuallyMut += 2;

   300   }

   301 

   302   // Update "n" old-generation pointers.

   303 

   304   private static void oldGenMut(long n) {

   305     for (int i = 0; i < n/2; i++) {

   306       oldGenSwapSubtrees();

   307     }

   308   }

   309 

   310   // Does the amount of mutator work appropriate for n bytes of young-gen

   311   // garbage allocation.

   312 

   313   private static void doMutWork(long n) {

   314     int sum = 0;

   315     long limit = workUnits*n/10;

   316     for (long k = 0; k < limit; k++) sum++;

   317     // We don't want dead code elimination to eliminate the loop above.

   318     mutatorSum = mutatorSum + sum;

   319   }

   320 

   321   // Allocate n bytes of young-gen garbage, in units of "nwords"

   322   // words.

   323 

   324   private static void doYoungGenAlloc(long n, int nwords) {

   325     final int nbytes = nwords*BYTES_PER_WORD;

   326     int allocated = 0;

   327     while (allocated < n) {

   328       aexport = new int[nwords];

   329       /* System.err.println("Step"); */

   330       allocated += nbytes;

   331     }

   332     youngBytes = youngBytes + allocated;

   333   }

   334 

   335   // Allocate "n" bytes of young-gen data; and do the

   336   // corresponding amount of old-gen allocation and pointer

   337   // mutation.

   338 

   339   // oldGenAlloc may perform some mutations, so this code

   340   // takes those mutations into account.

   341 

   342   private static void doStep(long n) {

   343     long mutations = actuallyMut;

   344 

   345     doYoungGenAlloc(n, WORDS_DEAD);

   346     doMutWork(n);

   347     oldGenAlloc(n / promoteRate);

   348     oldGenMut(Math.max(0L, (mutations + ptrMutRate) - actuallyMut));

   349   }

   350 

   351   public static void main(String[] args) {

   352     if (args.length != 5) {

   353       System.err.println(msg1);

   354       System.err.println(msg2);

   355       System.err.println(msg3);

   356       System.err.println(msg4);

   357       System.err.println(msg5);

   358       System.err.println(msg6);

   359       return;

   360     }

   361 

   362     size = Integer.parseInt(args[0]);

   363     workUnits = Integer.parseInt(args[1]);

   364     promoteRate = Integer.parseInt(args[2]);

   365     ptrMutRate = Integer.parseInt(args[3]);

   366     steps = Integer.parseInt(args[4]);

   367 

   368     System.out.println(size + " megabytes of live storage");

   369     System.out.println(workUnits + " work units per step");

   370     System.out.println("promotion ratio is 1:" + promoteRate);

   371     System.out.println("pointer mutation rate is " + ptrMutRate);

   372     System.out.println(steps + " steps");

   373 

   374     init();

   375 //  checkTrees();

   376     youngBytes = 0;

   377     nodes = 0;

   378 

   379     System.err.println("Initialization complete...");

   380 

   381     long start = System.currentTimeMillis();

   382 

   383     for (int step = 0; step < steps; step++) {

   384       doStep(MEG);

   385     }

   386 

   387     long end = System.currentTimeMillis();

   388     float secs = ((float)(end-start))/1000.0F;

   389 

   390 //  checkTrees();

   391 

   392     NumberFormat nf = NumberFormat.getInstance();

   393     nf.setMaximumFractionDigits(1);

   394     System.out.println("\nTook " + nf.format(secs) + " sec in steady state.");

   395     nf.setMaximumFractionDigits(2);

   396     System.out.println("Allocated " + steps + " Mb of young gen garbage"

   397                        + " (= " + nf.format(((float)steps)/secs) +

   398                        " Mb/sec)");

   399     System.out.println("    (actually allocated " +

   400                        nf.format(((float) youngBytes)/MEG) + " megabytes)");

   401     float promoted = ((float)steps) / (float)promoteRate;

   402     System.out.println("Promoted " + promoted +

   403                        " Mb (= " + nf.format(promoted/secs) + " Mb/sec)");

   404     System.out.println("    (actually promoted " +

   405                        nf.format(((float) (nodes * BYTES_PER_NODE))/MEG) +

   406                        " megabytes)");

   407     if (ptrMutRate != 0) {

   408       System.out.println("Mutated " + actuallyMut +

   409                          " pointers (= " +

   410                          nf.format(actuallyMut/secs) + " ptrs/sec)");

   411 

   412     }

   413     // This output serves mainly to discourage optimization.

   414     System.out.println("Checksum = " + (mutatorSum + aexport.length));

   415 

   416   }

   417 }