1 /*
2 * Copyright (c) 2005, 2024, 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 package nsk.share.gc;
25
26 import nsk.share.test.LocalRandom;
27 import java.io.PrintStream;
28 import nsk.share.gc.gp.GarbageProducer;
29 import nsk.share.gc.tree.*;
30 import nsk.share.gc.gp.MemoryStrategy;
31 import nsk.share.log.Log;
32
33 /**
34 * Different utility methods to work with memory objects.
35 */
36 public final class Memory {
37 private static int bits = 0;
38 private static int referenceSize = 0;
39 private static int objectExtraSize = 0;
40
41 private Memory() {
42 }
43
44 private static int getBits() {
45 if (bits == 0)
46 bits = Integer.parseInt(System.getProperty("sun.arch.data.model"));
47 return bits;
48 }
49
50 /**
51 * Get size of one object reference.
52 *
53 * TODO: somehow determine the real value
54 */
55 public static int getReferenceSize() {
56 if (referenceSize == 0)
57 referenceSize = (getBits() == 64) ? 8 : 4;
58 return referenceSize;
59 }
60
61 /**
62 * Get size of primitive type int.
63 */
64 public static int getIntSize() {
65 return 4;
66 }
67
68 /**
69 * Get size of primitive type boolean.
70 */
71 public static int getBooleanSize() {
72 return 1;
73 }
74
75 /**
76 * Get size of primitive type byte.
77 */
78 public static int getByteSize() {
79 return 1;
80 }
81
82 /**
83 * Get size of primitive type char.
84 */
85 public static int getCharSize() {
86 return 2;
87 }
88
89 /**
90 * Get size of primitive type short.
91 */
92 public static int getShortSize() {
93 return 2;
94 }
95
96 /**
97 * Get size of primitive type long.
98 */
99 public static int getLongSize() {
100 return 8;
101 }
102
103 /**
104 * Get size of primitive type float.
105 */
106 public static int getFloatSize() {
107 return 4;
108 }
109
110 /**
111 * Get size of primitive type double.
112 */
113 public static int getDoubleSize() {
114 return 8;
115 }
116
117 /**
118 * Get how many extra bytes an object occupies in the heap
119 * compared to sum of it's fields.
120 *
121 * TODO: somehow determine the real value
122 */
123 public static int getObjectExtraSize() {
124 if (objectExtraSize == 0)
125 objectExtraSize = 2 * getReferenceSize();
126 return objectExtraSize;
127 }
128 /**
129 * Get how many extra bytes an array occupies in the heap
130 * compared to sum of it's fields.
131 *
132 * TODO: somehow determine the real value
133 */
134 public static int getArrayExtraSize() {
135 return getObjectExtraSize();
136 }
137
138 /**
139 * Return size of reference object (SoftReference, WeakReference, PhantomReference)
140 */
141 public static int getReferenceObjectSize() {
142 return getReferenceSize() + getObjectExtraSize();
143 }
144
145 /**
146 * Get an approximate length of array that will occupy a given memory.
147 *
148 * @param memory size of memory
149 * @param objectSize size of each object in array
150 * @return length of array
151 */
152 public static int getArrayLength(long memory, long objectSize) {
153 int arrayExtraSize = getArrayExtraSize();
154 return (int) Math.min((memory - arrayExtraSize) / objectSize,
155 Integer.MAX_VALUE);
156 }
157
158 /**
159 * Get an approximate size of array of given length and object size.
160 *
161 * @param length length of arary
162 * @param objectSize size of object in array
163 * @return size of array
164 */
165 public static long getArraySize(int length, long objectSize) {
166 return getArrayExtraSize() + length * objectSize;
167 }
168
169 /**
170 * Calculate approximate size of biggest of MemoryObjects.
171 */
172 public static long getMemoryObjectSize(long size) {
173 return size + 2 * getReferenceSize() + getObjectExtraSize();
174 }
175
176 /**
177 * Calculate approximate size of linked list in memory.
178 *
179 * @param length length of list
180 * @param size size of object
181 * @return size
182 */
183 public static long getListSize(int length, int size) {
184 return getObjectExtraSize() + length * (getReferenceSize() + getMemoryObjectSize(size));
185 }
186
187 /**
188 * Calculate length of linear or circular linked list.
189 *
190 * @param mobj head of list
191 * @return length of list
192 */
193 public static int getListLength(LinkedMemoryObject mobj) {
194 LinkedMemoryObject tobj = mobj;
195 int length = 0;
196 do {
197 ++length;
198 tobj = tobj.getNext();
199 } while (tobj != null && tobj != mobj);
200 return length;
201 }
202
203 /**
204 * Calculate length of array of linear or circular linked lists.
205 *
206 * @param mobjs array containting heads of lists
207 * @return length of all lists
208 */
209 public static int getListsLength(LinkedMemoryObject[] mobjs) {
210 int length = 0;
211 for (int i = 0; i < mobjs.length; ++i) {
212 LinkedMemoryObject mobj = mobjs[i];
213 if (mobj != null)
214 length += getListLength(mobj);
215 }
216 return length;
217 }
218
219 /**
220 * Calculate size of all objects in linear or circular linked list.
221 *
222 * @param mobj head of list
223 * @return size of list
224 */
225 public static long getListSize(LinkedMemoryObject mobj) {
226 LinkedMemoryObject tobj = mobj;
227 long size = 0;
228 do {
229 size += tobj.getSize();
230 tobj = tobj.getNext();
231 } while (tobj != null && tobj != mobj);
232 return size;
233 }
234
235 /**
236 * Calculate size of array of linear or circular linked lists.
237 *
238 * @param mobjs array containting heads of lists
239 * @return size of all lists
240 */
241 public static long getListsSize(LinkedMemoryObject[] mobjs) {
242 long size = 0;
243 for (int i = 0; i < mobjs.length; ++i) {
244 LinkedMemoryObject mobj = mobjs[i];
245 if (mobj != null)
246 size += getListSize(mobj);
247 }
248 return size;
249 }
250
251 /**
252 * Create singly linked linear list of objects of fixed size.
253 *
254 * @param depth length of list
255 * @param size size of each object
256 * @return head of created list or null if depth = 0
257 */
258 public static LinkedMemoryObject makeLinearList(int depth, int size) {
259 LinkedMemoryObject mobj = null;
260 for (int i = 0; i < depth; ++i)
261 mobj = new LinkedMemoryObject(size, mobj);
262 return mobj;
263 }
264
265 /**
266 * Create singly linked linear list of objects of varying size.
267 *
268 * @param depth length of list
269 * @param size maximum size of each object
270 * @return head of created list or null if depth = 0
271 */
272 public static LinkedMemoryObject makeRandomLinearList(int depth, int size) {
273 if (depth == 0)
274 return null;
275 LinkedMemoryObject mobj = new LinkedMemoryObject(size);
276 for (int i = 0; i < depth - 1; ++i)
277 mobj = new LinkedMemoryObject(LocalRandom.nextInt(size), mobj);
278 return mobj;
279 }
280
281 /**
282 * Create singly linked circular linear list of objects of fixed size.
283 *
284 * @param depth length of list
285 * @param size size of each object
286 * @return head of created list or null if depth = 0
287 */
288 public static LinkedMemoryObject makeCircularList(int depth, int size) {
289 if (depth == 0)
290 return null;
291 LinkedMemoryObject mobj = new LinkedMemoryObject(size);
292 LinkedMemoryObject tmpobj = mobj;
293 for (int i = 1; i < depth; i++)
294 mobj = new LinkedMemoryObject(size, mobj);
295 tmpobj.setNext(mobj);
296 return tmpobj;
297 }
298
299 /**
300 * Create singly linked circular linear list of objects of varying size.
301 *
302 * @param depth length of list
303 * @param size maximum size of each object
304 * @return head of created list or null if depth = 0
305 */
306 public static LinkedMemoryObject makeRandomCircularList(int depth, int size) {
307 if (depth == 0)
308 return null;
309 LinkedMemoryObject mobj = new LinkedMemoryObject(size);
310 LinkedMemoryObject tmpobj = mobj;
311 for (int i = 0; i < depth - 1; i++)
312 mobj = new LinkedMemoryObject(LocalRandom.nextInt(size), mobj);
313 tmpobj.setNext(mobj);
314 return tmpobj;
315 }
316
317 /**
318 * Create new nonbranchy binary tree.
319 *
320 * Each node in the tree except leaves always has left son. A node
321 * will have right son with probability branchiness.
322 *
323 * @param numberOfNodes number of nodes
324 * @param branchiness branchiness
325 * @param size size of each node
326 * @return root of created tree
327 */
328 public static LinkedMemoryObject makeNonbranchyTree(int numberOfNodes, float branchiness, int size) {
329 LinkedMemoryObject root = null;
330 LinkedMemoryObject current = null;
331 if (numberOfNodes == 0)
332 return null;
333 else if (numberOfNodes == 1)
334 return new LinkedMemoryObject(size);
335 else if (numberOfNodes == 2)
336 return new LinkedMemoryObject(size, makeNonbranchyTree(1, branchiness, size));
337 else {
338 if (LocalRandom.nextFloat() < branchiness) {
339 int numberOfLeftNodes = LocalRandom.nextInt(1, numberOfNodes - 1);
340 int numberOfRightNodes = numberOfNodes - 1 - numberOfLeftNodes;
341 return new LinkedMemoryObject(
342 size,
343 makeNonbranchyTree(numberOfLeftNodes, branchiness, size),
344 makeNonbranchyTree(numberOfRightNodes, branchiness, size)
345 );
346 } else {
347 return new LinkedMemoryObject(size, makeNonbranchyTree(numberOfNodes - 1, branchiness, size));
348 }
349 }
350 }
351
352 /**
353 * Create a balanced tree of given height.
354 *
355 * @param height height of the tree
356 * @param size size of each node
357 * @return created tree
358 */
359 public static Tree makeBalancedTree(int height, long size) {
360 return new Tree(makeBalancedTreeNode(height, size));
361 }
362
363 /**
364 * Get a number of nodes in balanced tree of given height.
365 *
366 * @param heigh height of the tree
367 * @return number of nodes
368 */
369 public static int balancedTreeNodes(int height) {
370 if (height == 0)
371 return 0;
372 int n = 1;
373 while (height > 1) {
374 n *= 2;
375 height--;
376 }
377 return n * 2 - 1;
378 }
379
380 /**
381 * Get approximate memory size occupied by balanced tree
382 * of given height and given node size.
383 *
384 * @param height height of the tree
385 * @param nodeSize size of each node
386 * @return memory size
387 */
388 public static long balancedTreeSize(int height, long nodeSize) {
389 return balancedTreeNodes(height) * nodeSize;
390 }
391
392 /**
393 * Get a height of balanced tree with given number of nodes.
394 *
395 * @param nodes number of nodes
396 * @return height of the tree
397 */
398 public static int balancedTreeHeightFromNodes(int nodes) {
399 if (nodes == 0)
400 return 0;
401 int h = 1;
402 long n = 1;
403 while (n + n - 1 <= nodes) {
404 n = n + n;
405 h = h + 1;
406 }
407 return h - 1;
408 }
409
410 /**
411 * Get approximate height of balanced tree which will occupy
412 * given memory with given node size.
413 *
414 * @param memory memory size
415 * @param nodeSize size of each node
416 * @return approximate height of the tree
417 */
418 public static int balancedTreeHeightFromMemory(long memory, long nodeSize) {
419 return balancedTreeHeightFromNodes((int) (memory / nodeSize));
420 }
421
422 /**
423 * Create balanced tree of given height and node size.
424 *
425 * @param height height of the tree
426 * @param size size of each node
427 * @return root of created tree
428 */
429 public static TreeNode makeBalancedTreeNode(int height, long size) {
430 if (height == 0)
431 return null;
432 else
433 return new TreeNode(size, makeBalancedTreeNode(height - 1, size), makeBalancedTreeNode(height - 1, size));
434 }
435
436 /**
437 * Create balanced tree of given height and node size.
438 *
439 * @param height height of the tree
440 * @param size size of each node
441 * @return root of created tree
442 */
443 public static TreeNode makeBalancedTreeNode(int height, long size, GarbageProducer gp) {
444 if (height == 0)
445 return null;
446 else
447 return new TreeNode(size, gp, makeBalancedTreeNode(height - 1, size), makeBalancedTreeNode(height - 1, size));
448 }
449
450 /**
451 * Determine if given tree is a balanced tree.
452 *
453 * @param tree tree
454 * @return true if tree is balanced
455 */
456 public static boolean isBalancedTree(TreeNode tree) {
457 return
458 tree.getActualHeight() == tree.getHeight() &&
459 tree.getShortestPath() == tree.getHeight();
460 }
461
462 /**
463 * Fill an array of MemoryObject's with new objects of given size.
464 *
465 * @param array array
466 * @param count number of objects to create
467 * @param size size of each object
468 */
469 public static void fillArray(MemoryObject[] array, int count, int size) {
470 for (int i = 0; i < count; ++i)
471 array[i] = new MemoryObject(size);
472 }
473
474 /**
475 * Fill an array of MemoryObject's with new objects of random size.
476 *
477 * @param array array
478 * @param count number of objects to create
479 * @param size maximum size of each object
480 */
481 public static void fillArrayRandom(MemoryObject[] array, int count, int size) {
482 for (int i = 0; i < count; ++i)
483 array[i] = new MemoryObject(LocalRandom.nextInt(size));
484 }
485
486 /**
487 * Fill an array of MemoryObject's with new objects of random size.
488 *
489 * @param array array
490 * @param count number of objects to create
491 * @param size maximum size of each object
492 */
493 public static void fillArrayRandom(LinkedMemoryObject[] array, int count, int size) {
494 for (int i = 0; i < count; ++i)
495 array[i] = new LinkedMemoryObject(LocalRandom.nextInt(size));
496 }
497
498 public static void dumpStatistics(PrintStream out) {
499 out.println(Runtime.getRuntime().freeMemory());
500 out.flush();
501 }
502
503 public static void dumpStatistics(Log log) {
504 log.info(Runtime.getRuntime().freeMemory());
505 }
506
507 public static void dumpStatistics() {
508 dumpStatistics(System.out);
509 }
510 }