| /* |
| * Copyright (c) 2010, 2018, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| package vm.gc.concurrent; |
| |
| import java.lang.management.ManagementFactory; |
| import java.lang.management.MemoryMXBean; |
| import java.lang.management.MemoryUsage; |
| import java.util.Random; |
| import java.util.concurrent.atomic.AtomicInteger; |
| import java.util.concurrent.locks.Lock; |
| import java.util.concurrent.locks.ReentrantLock; |
| import nsk.share.TestFailure; |
| import nsk.share.gc.GC; |
| import nsk.share.gc.Memory; |
| import nsk.share.gc.ThreadedGCTest; |
| import nsk.share.gc.gp.GarbageProducer; |
| import nsk.share.gc.gp.GarbageProducer1Aware; |
| import nsk.share.gc.gp.GarbageProducerAware; |
| import nsk.share.gc.gp.MemoryStrategy; |
| import nsk.share.gc.gp.MemoryStrategyAware; |
| import nsk.share.gc.tree.*; |
| import nsk.share.log.Log; |
| import nsk.share.test.ExecutionController; |
| |
| |
| class Forest { |
| |
| // the actual size of TreeNode in bytes in the memory calculated as occupied memory / count of nodes |
| static int nodeSize; |
| |
| static long treeSize; |
| |
| private static long allNodesCount; |
| |
| /* log from test */ |
| static Log log; |
| |
| |
| static int treeHeight; |
| |
| static long actuallyMut = 0; |
| private static Forest instance = new Forest(); |
| private Tree[] trees; |
| private Lock[] locks; |
| private static Random rnd = new Random(); |
| |
| private int nodeGarbageSize; |
| |
| private GarbageProducer gp; |
| /* |
| * Create array of trees occupyng given percent of heap |
| */ |
| static Forest createForest(long percent, int heightToSizeRatio, int nodeGarbageSize, GarbageProducer gp, Log _log) { |
| log = _log; |
| |
| long size = Runtime.getRuntime().maxMemory() * percent / 100; |
| treeHeight = Memory.balancedTreeHeightFromMemory(size, (int) new TreeNode(nodeGarbageSize).getTotalSize()); |
| int ntrees = 0; |
| while (treeHeight * heightToSizeRatio > ntrees) { |
| ntrees++; |
| treeHeight = Memory.balancedTreeHeightFromMemory(size / ntrees, (int) new TreeNode(nodeGarbageSize).getTotalSize()); |
| } |
| |
| log.debug("The expected forest paramteres: tree height = " + treeHeight + " number of trees = " + ntrees |
| + " size = " + new TreeNode(nodeGarbageSize).getTotalSize()); |
| Tree[] localTrees = new Tree[ntrees * 4]; |
| Lock[] localLocks = new Lock[ntrees * 4]; |
| for (int i = 0; i < ntrees * 4; i++) { |
| localTrees[i] = new Tree(Memory.makeBalancedTreeNode(treeHeight, nodeGarbageSize, gp)); |
| localLocks[i] = new ReentrantLock(); |
| |
| int numOfAttempts = 0; |
| if (Concurrent.getPercentInfoByMBeans() > percent) { |
| log.debug("Attempt to System.gc() before control check. (" + numOfAttempts++ + ")"); |
| System.gc(); |
| if (Concurrent.getPercentInfoByMBeans() > percent) { |
| instance.trees = new Tree[i]; |
| instance.locks = new Lock[i]; |
| for (int j = 0; j < i; j++) { |
| instance.trees[j] = localTrees[j]; |
| instance.locks[j] = localLocks[j]; |
| } |
| allNodesCount = Memory.balancedTreeNodes(treeHeight) * instance.trees.length; |
| nodeSize = (int) (ManagementFactory.getMemoryMXBean().getHeapMemoryUsage().getUsed() / allNodesCount); |
| treeSize = Memory.balancedTreeSize(treeHeight, nodeSize); |
| instance.where = new AtomicCycleInteger(instance.trees.length); |
| instance.nodeGarbageSize = nodeGarbageSize; |
| |
| log.debug("The forest real paramteres: tree height = " + treeHeight + " number of trees = " + instance.trees.length |
| + " number of nodes = " + allNodesCount); |
| log.debug("Approximate node size = " + nodeSize + " calc = " + instance.trees[0].getRoot().getSize()); |
| return instance; |
| } |
| } |
| } |
| throw new TestFailure("Should not reach here. The correct exit point is inside cycle"); |
| } |
| |
| |
| int treesCount() { |
| return trees.length; |
| } |
| |
| long nodesCount() { |
| return allNodesCount; |
| } |
| |
| |
| |
| // Confirms that all trees are balanced and have the correct height. |
| void checkTrees() { |
| for (int i = 0; i < trees.length; i++) { |
| locks[i].lock(); |
| checkTree(trees[i]); |
| locks[i].unlock(); |
| } |
| } |
| |
| private static void checkTree(Tree tree) { |
| TreeNode root = tree.getRoot(); |
| int h1 = root.getHeight(); |
| int h2 = root.getShortestPath(); |
| if ((h1 != treeHeight) || (h2 != treeHeight)) { |
| throw new TestFailure("The tree is not balanced expected " + treeHeight |
| + " value = " + h1 + " shortedtPath = " + h2); |
| } |
| } |
| |
| // Swap subtrees in 2 trees, the the path is used |
| // as sequence of 1-0 to select subtree (left-reight sequence) |
| static void swapSubtrees(Tree t1, Tree t2, int depth, int path) { |
| TreeNode tn1 = t1.getRoot(); |
| TreeNode tn2 = t2.getRoot(); |
| for (int i = 0; i < depth; i++) { |
| if ((path & 1) == 0) { |
| tn1 = tn1.getLeft(); |
| tn2 = tn2.getLeft(); |
| } else { |
| tn1 = tn1.getRight(); |
| tn2 = tn2.getRight(); |
| } |
| path >>= 1; |
| } |
| TreeNode tmp; |
| if ((path & 1) == 0) { |
| tmp = tn1.getLeft(); |
| tn1.setLeft(tn2.getLeft()); |
| tn2.setLeft(tmp); |
| } else { |
| tmp = tn1.getRight(); |
| tn1.setRight(tn2.getRight()); |
| tn2.setLeft(tmp); |
| } |
| } |
| |
| |
| // Interchanges two randomly selected subtrees (of same size and depth) several times |
| void swapSubtrees(long count) { |
| for (int i = 0; i < count; i++) { |
| int index1 = rnd.nextInt(trees.length); |
| int index2 = rnd.nextInt(trees.length); |
| int depth = rnd.nextInt(treeHeight); |
| int path = rnd.nextInt(); |
| locks[index1].lock(); |
| // Skip the round to avoid deadlocks |
| if (locks[index2].tryLock()) { |
| swapSubtrees(trees[index1], trees[index2], depth, path); |
| actuallyMut += 2; |
| locks[index2].unlock(); |
| } |
| locks[index1].unlock(); |
| |
| } |
| |
| } |
| |
| |
| static class AtomicCycleInteger extends AtomicInteger { |
| private int max; |
| public AtomicCycleInteger(int cycleLength) { |
| super(); |
| this.max = cycleLength - 1; |
| } |
| public int cycleIncrementAndGet() { |
| for (;;) { |
| int current = get(); |
| int next = (current == max ? 0 : current + 1); |
| if (compareAndSet(current, next)) { |
| return next; |
| } |
| } |
| } |
| } |
| |
| // the index in tree array which should be chnaged during next regeneration |
| AtomicCycleInteger where = null; |
| |
| // generate new full and partial trees in our forest |
| void regenerateTrees(long nodesCount) { |
| int full = (int) (nodesCount / Memory.balancedTreeNodes(treeHeight)) ; |
| int partial = (int) nodesCount % (Memory.balancedTreeNodes(treeHeight)); |
| for (int i = 0; i < full; i++) { |
| int idx = where.cycleIncrementAndGet(); |
| locks[idx].lock(); |
| trees[idx] = new Tree(Memory.makeBalancedTreeNode(treeHeight, nodeGarbageSize)); |
| locks[idx].unlock(); |
| } |
| while (partial > 0) { |
| int h = Memory.balancedTreeHeightFromNodes(partial); |
| Tree newTree = new Tree(Memory.makeBalancedTreeNode(h, nodeGarbageSize)); |
| int idx = where.cycleIncrementAndGet(); |
| locks[idx].lock(); |
| replaceTree(trees[idx], newTree); |
| locks[idx].unlock(); |
| partial = partial - Memory.balancedTreeNodes(h); |
| } |
| } |
| |
| |
| // Given a balanced tree full and a smaller balanced tree partial, |
| // replaces an appropriate subtree of full by partial, taking care |
| // to preserve the shape of the full tree. |
| private static void replaceTree(Tree full, Tree partial) { |
| boolean dir = (partial.getHeight() % 2) == 0; |
| actuallyMut++; |
| replaceTreeWork(full.getRoot(), partial.getRoot(), dir); |
| } |
| |
| // Called only by replaceTree (below) and by itself. |
| static void replaceTreeWork(TreeNode full, TreeNode partial, |
| boolean dir) { |
| boolean canGoLeft = full.getLeft() != null && full.getLeft().getHeight() > partial.getHeight(); |
| boolean canGoRight = full.getRight() != null && full.getRight().getHeight() > partial.getHeight(); |
| if (canGoLeft && canGoRight) { |
| if (dir) { |
| replaceTreeWork(full.getLeft(), partial, !dir); |
| } else { |
| replaceTreeWork(full.getRight(), partial, !dir); |
| } |
| } else if (!canGoLeft && !canGoRight) { |
| if (dir) { |
| full.setLeft(partial); |
| } else { |
| full.setRight(partial); |
| } |
| } else if (!canGoLeft) { |
| full.setLeft(partial); |
| } else { |
| full.setRight(partial); |
| } |
| } |
| |
| |
| |
| } |
| public class Concurrent extends ThreadedGCTest implements GarbageProducerAware, GarbageProducer1Aware, MemoryStrategyAware { |
| |
| // Heap as tree |
| Forest forest; |
| |
| // GP for old gargbage production |
| GarbageProducer gpOld; |
| |
| // GP for young gargbage production |
| GarbageProducer gpYoung; |
| |
| MemoryStrategy ms; |
| |
| private void printStatistics() { |
| log.debug("Actual mutations = " + forest.actuallyMut); |
| } |
| |
| private class Worker implements Runnable { |
| |
| private ExecutionController stresser; |
| |
| @Override |
| public void run() { |
| if (stresser == null) { |
| stresser = getExecutionController(); |
| } |
| while (stresser.continueExecution()) { |
| doStep(); |
| } |
| } |
| } |
| |
| @Override |
| public Runnable createRunnable(int i) { |
| return new Worker(); |
| } |
| |
| public static int getPercentInfoByMBeans() { |
| MemoryMXBean mbean = ManagementFactory.getMemoryMXBean(); |
| return (int) (100 * mbean.getHeapMemoryUsage().getUsed() / mbean.getHeapMemoryUsage().getMax()); |
| } |
| |
| private void printMem(long used, long max, String source) { |
| log.debug("The Memory after allocation (" + source + "): "); |
| log.debug("Used = " + used + " Max = " + max + " Percent = " + (100 * used / max)); |
| } |
| |
| // Command-line parameters. |
| // young garbage in percent and absolute |
| private static int youngPercent = 0; |
| long youngGarbageSize; |
| // mutation rate (parcent and absolute trees) |
| private static int ptrMutRate = 50; |
| long mutateTrees; |
| // percent of heap to occupy by forest (long live garbage) |
| private static int livePercent = 60; |
| // the minimum of which should be available for forest |
| // test fails if it is not possible to use 60% of heap |
| private static final int MIN_AVAILABLE_MEM = 60; |
| // percent of forest to reallocate each step |
| private static int reallocatePercent = 30; |
| long reallocateSizeInNodes; |
| // sleep time in ms |
| private static int sleepTime = 100; |
| |
| private void init(int longLivePercent) { |
| int numberOfThreads = runParams.getNumberOfThreads(); |
| forest = Forest.createForest(longLivePercent, numberOfThreads, |
| (int) Math.sqrt(ms.getSize(Runtime.getRuntime().maxMemory())), gpOld, log); |
| |
| youngGarbageSize = Runtime.getRuntime().maxMemory() * youngPercent / 100 / numberOfThreads; |
| reallocateSizeInNodes = forest.nodesCount() * reallocatePercent / 100 / numberOfThreads; |
| mutateTrees = forest.treesCount() * ptrMutRate / 100 / numberOfThreads / 2; |
| |
| log.debug("Young Gen = " + youngGarbageSize); |
| log.debug("Forest contains " + forest.treesCount() + " trees and " + forest.nodesCount() + " nodes."); |
| log.debug("Count of nodes to reallocate = " + reallocateSizeInNodes); |
| log.debug("Count of tree pairs to exchange nodes = " + mutateTrees); |
| log.debug("Sleep time = " + sleepTime); |
| |
| // print some info |
| MemoryUsage mbean = ManagementFactory.getMemoryMXBean().getHeapMemoryUsage(); |
| printMem(mbean.getUsed(), mbean.getMax(), "Beans"); |
| printMem(Runtime.getRuntime().maxMemory() - Runtime.getRuntime().freeMemory(), |
| Runtime.getRuntime().maxMemory(), "System"); |
| } |
| |
| @Override |
| public void run() { |
| try { |
| init(livePercent); |
| } catch (OutOfMemoryError oome) { |
| if (livePercent > MIN_AVAILABLE_MEM) { |
| log.debug("Unable to use " + livePercent + " use only " + MIN_AVAILABLE_MEM); |
| init(MIN_AVAILABLE_MEM); |
| } |
| } |
| super.run(); |
| printStatistics(); |
| } |
| |
| |
| |
| private void doStep() { |
| // allocate some young garbage |
| if (youngGarbageSize != 0) { |
| gpYoung.create(youngGarbageSize); |
| } |
| |
| // allocate some long-live garbage (attached to our trees) |
| forest.regenerateTrees(reallocateSizeInNodes); |
| |
| // mutate pointers |
| forest.swapSubtrees(mutateTrees); |
| |
| // sleep to give GC time for some concurrent actions |
| try { |
| Thread.sleep(sleepTime); |
| } catch (InterruptedException ie) { |
| } |
| |
| // verify trees, also read all pointers |
| forest.checkTrees(); |
| } |
| |
| public static void main(String[] args) { |
| init(args); |
| GC.runTest(new Concurrent(), args); |
| } |
| |
| public static void init(String[] args) { |
| for (int i = 0; i < args.length; ++i) { |
| if (args[i].equals("-lp")) { |
| // percent of long lived objects |
| livePercent = Integer.parseInt(args[++i]); |
| } else if (args[i].equals("-rp")) { |
| // percent of trees to reallocate |
| reallocatePercent = Integer.parseInt(args[++i]); |
| } else if (args[i].equals("-yp")) { |
| // percent of young objects |
| youngPercent = Integer.parseInt(args[++i]); |
| } else if (args[i].equals("-mr")) { |
| // percent of trees to exchange (mutate) |
| ptrMutRate = Integer.parseInt(args[++i]); |
| } else if (args[i].equals("-st")) { |
| // sleep time in ms |
| sleepTime = Integer.parseInt(args[++i]); |
| } |
| } |
| } |
| |
| @Override |
| public void setGarbageProducer(GarbageProducer gp) { |
| this.gpOld = gp; |
| } |
| |
| |
| @Override |
| public void setGarbageProducer1(GarbageProducer gpYoung) { |
| this.gpYoung = gpYoung; |
| } |
| |
| @Override |
| public void setMemoryStrategy(MemoryStrategy ms) { |
| this.ms = ms; |
| } |
| } |