1 /* 2 * Copyright (c) 2010, 2018, 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 package vm.gc.concurrent; 24 25 import java.lang.management.ManagementFactory; 26 import java.lang.management.MemoryMXBean; 27 import java.lang.management.MemoryUsage; 28 import java.util.concurrent.atomic.AtomicInteger; 29 import java.util.concurrent.locks.Lock; 30 import java.util.concurrent.locks.ReentrantLock; 31 import nsk.share.TestFailure; 32 import nsk.share.gc.GC; 33 import nsk.share.gc.Memory; 34 import nsk.share.gc.ThreadedGCTest; 35 import nsk.share.gc.gp.GarbageProducer; 36 import nsk.share.gc.gp.GarbageProducer1Aware; 37 import nsk.share.gc.gp.GarbageProducerAware; 38 import nsk.share.gc.gp.MemoryStrategy; 39 import nsk.share.gc.gp.MemoryStrategyAware; 40 import nsk.share.gc.tree.*; 41 import nsk.share.log.Log; 42 import nsk.share.test.ExecutionController; 43 import nsk.share.test.LocalRandom; 44 45 class Forest { 46 47 // the actual size of TreeNode in bytes in the memory calculated as occupied memory / count of nodes 48 static int nodeSize; 49 50 static long treeSize; 51 52 private static long allNodesCount; 53 54 /* log from test */ 55 static Log log; 56 57 58 static int treeHeight; 59 60 static long actuallyMut = 0; 61 private static Forest instance = new Forest(); 62 private Tree[] trees; 63 private Lock[] locks; 64 65 private int nodeGarbageSize; 66 67 private GarbageProducer gp; 68 /* 69 * Create array of trees occupyng given percent of heap 70 */ 71 static Forest createForest(long percent, int heightToSizeRatio, int nodeGarbageSize, GarbageProducer gp, Log _log) { 72 log = _log; 73 74 long size = Runtime.getRuntime().maxMemory() * percent / 100; 75 treeHeight = Memory.balancedTreeHeightFromMemory(size, (int) new TreeNode(nodeGarbageSize).getTotalSize()); 76 int ntrees = 0; 77 while (treeHeight * heightToSizeRatio > ntrees) { 78 ntrees++; 79 treeHeight = Memory.balancedTreeHeightFromMemory(size / ntrees, (int) new TreeNode(nodeGarbageSize).getTotalSize()); 80 } 81 82 log.debug("The expected forest paramteres: tree height = " + treeHeight + " number of trees = " + ntrees 83 + " size = " + new TreeNode(nodeGarbageSize).getTotalSize()); 84 Tree[] localTrees = new Tree[ntrees * 4]; 85 Lock[] localLocks = new Lock[ntrees * 4]; 86 for (int i = 0; i < ntrees * 4; i++) { 87 localTrees[i] = new Tree(Memory.makeBalancedTreeNode(treeHeight, nodeGarbageSize, gp)); 88 localLocks[i] = new ReentrantLock(); 89 90 int numOfAttempts = 0; 91 if (Concurrent.getPercentInfoByMBeans() > percent) { 92 log.debug("Attempt to System.gc() before control check. (" + numOfAttempts++ + ")"); 93 System.gc(); 94 if (Concurrent.getPercentInfoByMBeans() > percent) { 95 instance.trees = new Tree[i]; 96 instance.locks = new Lock[i]; 97 for (int j = 0; j < i; j++) { 98 instance.trees[j] = localTrees[j]; 99 instance.locks[j] = localLocks[j]; 100 } 101 allNodesCount = Memory.balancedTreeNodes(treeHeight) * instance.trees.length; 102 nodeSize = (int) (ManagementFactory.getMemoryMXBean().getHeapMemoryUsage().getUsed() / allNodesCount); 103 treeSize = Memory.balancedTreeSize(treeHeight, nodeSize); 104 instance.where = new AtomicCycleInteger(instance.trees.length); 105 instance.nodeGarbageSize = nodeGarbageSize; 106 107 log.debug("The forest real paramteres: tree height = " + treeHeight + " number of trees = " + instance.trees.length 108 + " number of nodes = " + allNodesCount); 109 log.debug("Approximate node size = " + nodeSize + " calc = " + instance.trees[0].getRoot().getSize()); 110 return instance; 111 } 112 } 113 } 114 throw new TestFailure("Should not reach here. The correct exit point is inside cycle"); 115 } 116 117 118 int treesCount() { 119 return trees.length; 120 } 121 122 long nodesCount() { 123 return allNodesCount; 124 } 125 126 127 128 // Confirms that all trees are balanced and have the correct height. 129 void checkTrees() { 130 for (int i = 0; i < trees.length; i++) { 131 locks[i].lock(); 132 checkTree(trees[i]); 133 locks[i].unlock(); 134 } 135 } 136 137 private static void checkTree(Tree tree) { 138 TreeNode root = tree.getRoot(); 139 int h1 = root.getHeight(); 140 int h2 = root.getShortestPath(); 141 if ((h1 != treeHeight) || (h2 != treeHeight)) { 142 throw new TestFailure("The tree is not balanced expected " + treeHeight 143 + " value = " + h1 + " shortedtPath = " + h2); 144 } 145 } 146 147 // Swap subtrees in 2 trees, the the path is used 148 // as sequence of 1-0 to select subtree (left-reight sequence) 149 static void swapSubtrees(Tree t1, Tree t2, int depth, int path) { 150 TreeNode tn1 = t1.getRoot(); 151 TreeNode tn2 = t2.getRoot(); 152 for (int i = 0; i < depth; i++) { 153 if ((path & 1) == 0) { 154 tn1 = tn1.getLeft(); 155 tn2 = tn2.getLeft(); 156 } else { 157 tn1 = tn1.getRight(); 158 tn2 = tn2.getRight(); 159 } 160 path >>= 1; 161 } 162 TreeNode tmp; 163 if ((path & 1) == 0) { 164 tmp = tn1.getLeft(); 165 tn1.setLeft(tn2.getLeft()); 166 tn2.setLeft(tmp); 167 } else { 168 tmp = tn1.getRight(); 169 tn1.setRight(tn2.getRight()); 170 tn2.setLeft(tmp); 171 } 172 } 173 174 175 // Interchanges two randomly selected subtrees (of same size and depth) several times 176 void swapSubtrees(long count) { 177 for (int i = 0; i < count; i++) { 178 int index1 = LocalRandom.nextInt(trees.length); 179 int index2 = LocalRandom.nextInt(trees.length); 180 int depth = LocalRandom.nextInt(treeHeight); 181 int path = LocalRandom.nextInt(); 182 locks[index1].lock(); 183 // Skip the round to avoid deadlocks 184 if (locks[index2].tryLock()) { 185 swapSubtrees(trees[index1], trees[index2], depth, path); 186 actuallyMut += 2; 187 locks[index2].unlock(); 188 } 189 locks[index1].unlock(); 190 191 } 192 193 } 194 195 196 static class AtomicCycleInteger extends AtomicInteger { 197 private int max; 198 public AtomicCycleInteger(int cycleLength) { 199 super(); 200 this.max = cycleLength - 1; 201 } 202 public int cycleIncrementAndGet() { 203 for (;;) { 204 int current = get(); 205 int next = (current == max ? 0 : current + 1); 206 if (compareAndSet(current, next)) { 207 return next; 208 } 209 } 210 } 211 } 212 213 // the index in tree array which should be chnaged during next regeneration 214 AtomicCycleInteger where = null; 215 216 // generate new full and partial trees in our forest 217 void regenerateTrees(long nodesCount) { 218 int full = (int) (nodesCount / Memory.balancedTreeNodes(treeHeight)) ; 219 int partial = (int) nodesCount % (Memory.balancedTreeNodes(treeHeight)); 220 for (int i = 0; i < full; i++) { 221 int idx = where.cycleIncrementAndGet(); 222 locks[idx].lock(); 223 trees[idx] = new Tree(Memory.makeBalancedTreeNode(treeHeight, nodeGarbageSize)); 224 locks[idx].unlock(); 225 } 226 while (partial > 0) { 227 int h = Memory.balancedTreeHeightFromNodes(partial); 228 Tree newTree = new Tree(Memory.makeBalancedTreeNode(h, nodeGarbageSize)); 229 int idx = where.cycleIncrementAndGet(); 230 locks[idx].lock(); 231 replaceTree(trees[idx], newTree); 232 locks[idx].unlock(); 233 partial = partial - Memory.balancedTreeNodes(h); 234 } 235 } 236 237 238 // Given a balanced tree full and a smaller balanced tree partial, 239 // replaces an appropriate subtree of full by partial, taking care 240 // to preserve the shape of the full tree. 241 private static void replaceTree(Tree full, Tree partial) { 242 boolean dir = (partial.getHeight() % 2) == 0; 243 actuallyMut++; 244 replaceTreeWork(full.getRoot(), partial.getRoot(), dir); 245 } 246 247 // Called only by replaceTree (below) and by itself. 248 static void replaceTreeWork(TreeNode full, TreeNode partial, 249 boolean dir) { 250 boolean canGoLeft = full.getLeft() != null && full.getLeft().getHeight() > partial.getHeight(); 251 boolean canGoRight = full.getRight() != null && full.getRight().getHeight() > partial.getHeight(); 252 if (canGoLeft && canGoRight) { 253 if (dir) { 254 replaceTreeWork(full.getLeft(), partial, !dir); 255 } else { 256 replaceTreeWork(full.getRight(), partial, !dir); 257 } 258 } else if (!canGoLeft && !canGoRight) { 259 if (dir) { 260 full.setLeft(partial); 261 } else { 262 full.setRight(partial); 263 } 264 } else if (!canGoLeft) { 265 full.setLeft(partial); 266 } else { 267 full.setRight(partial); 268 } 269 } 270 271 272 273 } 274 public class Concurrent extends ThreadedGCTest implements GarbageProducerAware, GarbageProducer1Aware, MemoryStrategyAware { 275 276 // Heap as tree 277 Forest forest; 278 279 // GP for old gargbage production 280 GarbageProducer gpOld; 281 282 // GP for young gargbage production 283 GarbageProducer gpYoung; 284 285 MemoryStrategy ms; 286 287 private void printStatistics() { 288 log.debug("Actual mutations = " + forest.actuallyMut); 289 } 290 291 private class Worker implements Runnable { 292 293 private ExecutionController stresser; 294 295 @Override 296 public void run() { 297 if (stresser == null) { 298 stresser = getExecutionController(); 299 } 300 while (stresser.continueExecution()) { 301 doStep(); 302 } 303 } 304 } 305 306 @Override 307 public Runnable createRunnable(int i) { 308 return new Worker(); 309 } 310 311 public static int getPercentInfoByMBeans() { 312 MemoryMXBean mbean = ManagementFactory.getMemoryMXBean(); 313 return (int) (100 * mbean.getHeapMemoryUsage().getUsed() / mbean.getHeapMemoryUsage().getMax()); 314 } 315 316 private void printMem(long used, long max, String source) { 317 log.debug("The Memory after allocation (" + source + "): "); 318 log.debug("Used = " + used + " Max = " + max + " Percent = " + (100 * used / max)); 319 } 320 321 // Command-line parameters. 322 // young garbage in percent and absolute 323 private static int youngPercent = 0; 324 long youngGarbageSize; 325 // mutation rate (parcent and absolute trees) 326 private static int ptrMutRate = 50; 327 long mutateTrees; 328 // percent of heap to occupy by forest (long live garbage) 329 private static int livePercent = 60; 330 // the minimum of which should be available for forest 331 // test fails if it is not possible to use 60% of heap 332 private static final int MIN_AVAILABLE_MEM = 60; 333 // percent of forest to reallocate each step 334 private static int reallocatePercent = 30; 335 long reallocateSizeInNodes; 336 // sleep time in ms 337 private static int sleepTime = 100; 338 339 private void init(int longLivePercent) { 340 int numberOfThreads = runParams.getNumberOfThreads(); 341 forest = Forest.createForest(longLivePercent, numberOfThreads, 342 (int) Math.sqrt(ms.getSize(Runtime.getRuntime().maxMemory())), gpOld, log); 343 344 youngGarbageSize = Runtime.getRuntime().maxMemory() * youngPercent / 100 / numberOfThreads; 345 reallocateSizeInNodes = forest.nodesCount() * reallocatePercent / 100 / numberOfThreads; 346 mutateTrees = forest.treesCount() * ptrMutRate / 100 / numberOfThreads / 2; 347 348 log.debug("Young Gen = " + youngGarbageSize); 349 log.debug("Forest contains " + forest.treesCount() + " trees and " + forest.nodesCount() + " nodes."); 350 log.debug("Count of nodes to reallocate = " + reallocateSizeInNodes); 351 log.debug("Count of tree pairs to exchange nodes = " + mutateTrees); 352 log.debug("Sleep time = " + sleepTime); 353 354 // print some info 355 MemoryUsage mbean = ManagementFactory.getMemoryMXBean().getHeapMemoryUsage(); 356 printMem(mbean.getUsed(), mbean.getMax(), "Beans"); 357 printMem(Runtime.getRuntime().maxMemory() - Runtime.getRuntime().freeMemory(), 358 Runtime.getRuntime().maxMemory(), "System"); 359 } 360 361 @Override 362 public void run() { 363 try { 364 init(livePercent); 365 } catch (OutOfMemoryError oome) { 366 if (livePercent > MIN_AVAILABLE_MEM) { 367 log.debug("Unable to use " + livePercent + " use only " + MIN_AVAILABLE_MEM); 368 init(MIN_AVAILABLE_MEM); 369 } 370 } 371 super.run(); 372 printStatistics(); 373 } 374 375 376 377 private void doStep() { 378 // allocate some young garbage 379 if (youngGarbageSize != 0) { 380 gpYoung.create(youngGarbageSize); 381 } 382 383 // allocate some long-live garbage (attached to our trees) 384 forest.regenerateTrees(reallocateSizeInNodes); 385 386 // mutate pointers 387 forest.swapSubtrees(mutateTrees); 388 389 // sleep to give GC time for some concurrent actions 390 try { 391 Thread.sleep(sleepTime); 392 } catch (InterruptedException ie) { 393 } 394 395 // verify trees, also read all pointers 396 forest.checkTrees(); 397 } 398 399 public static void main(String[] args) { 400 init(args); 401 GC.runTest(new Concurrent(), args); 402 } 403 404 public static void init(String[] args) { 405 for (int i = 0; i < args.length; ++i) { 406 if (args[i].equals("-lp")) { 407 // percent of long lived objects 408 livePercent = Integer.parseInt(args[++i]); 409 } else if (args[i].equals("-rp")) { 410 // percent of trees to reallocate 411 reallocatePercent = Integer.parseInt(args[++i]); 412 } else if (args[i].equals("-yp")) { 413 // percent of young objects 414 youngPercent = Integer.parseInt(args[++i]); 415 } else if (args[i].equals("-mr")) { 416 // percent of trees to exchange (mutate) 417 ptrMutRate = Integer.parseInt(args[++i]); 418 } else if (args[i].equals("-st")) { 419 // sleep time in ms 420 sleepTime = Integer.parseInt(args[++i]); 421 } 422 } 423 } 424 425 @Override 426 public void setGarbageProducer(GarbageProducer gp) { 427 this.gpOld = gp; 428 } 429 430 431 @Override 432 public void setGarbageProducer1(GarbageProducer gpYoung) { 433 this.gpYoung = gpYoung; 434 } 435 436 @Override 437 public void setMemoryStrategy(MemoryStrategy ms) { 438 this.ms = ms; 439 } 440 }