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