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