1 /*
2 * Copyright (c) 2010, 2020, 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 }