001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.mmtk.utility.heap;
014
015 import org.mmtk.plan.Plan;
016 import org.mmtk.utility.*;
017 import org.mmtk.utility.options.Options;
018
019 import org.mmtk.vm.VM;
020
021 import org.vmmagic.pragma.*;
022 import org.vmmagic.unboxed.*;
023
024 /**
025 * This class is responsible for growing and shrinking the
026 * heap size by observing heap utilization and GC load.
027 */
028 @Uninterruptible public abstract class HeapGrowthManager implements Constants {
029
030 /**
031 * The initial heap size (-Xms) in bytes
032 */
033 private static Extent initialHeapSize;
034
035 /**
036 * The maximum heap size (-Xms) in bytes
037 */
038 private static Extent maxHeapSize;
039
040 /**
041 * The current heap size in bytes
042 */
043 private static Extent currentHeapSize;
044
045
046 private static final double[][] generationalFunction = {{0.00, 0.00, 0.10, 0.30, 0.60, 0.80, 1.00},
047 { 0.00, 0.90, 0.90, 0.95, 1.00, 1.00, 1.00 },
048 { 0.01, 0.90, 0.90, 0.95, 1.00, 1.00, 1.00 },
049 { 0.02, 0.95, 0.95, 1.00, 1.00, 1.00, 1.00 },
050 { 0.07, 1.00, 1.00, 1.10, 1.15, 1.20, 1.20 },
051 { 0.15, 1.00, 1.00, 1.20, 1.25, 1.35, 1.30 },
052 { 0.40, 1.00, 1.00, 1.25, 1.30, 1.50, 1.50 },
053 { 1.00, 1.00, 1.00, 1.25, 1.30, 1.50, 1.50 } };
054
055 private static final double[][] nongenerationalFunction = {{0.00, 0.00, 0.10, 0.30, 0.60, 0.80, 1.00},
056 { 0.00, 0.90, 0.90, 0.95, 1.00, 1.00, 1.00 },
057 { 0.02, 0.90, 0.90, 0.95, 1.00, 1.00, 1.00 },
058 { 0.05, 0.95, 0.95, 1.00, 1.00, 1.00, 1.00 },
059 { 0.15, 1.00, 1.00, 1.10, 1.15, 1.20, 1.20 },
060 { 0.30, 1.00, 1.00, 1.20, 1.25, 1.35, 1.30 },
061 { 0.50, 1.00, 1.00, 1.25, 1.30, 1.50, 1.50 },
062 { 1.00, 1.00, 1.00, 1.25, 1.30, 1.50, 1.50 } };
063
064 /**
065 * An encoding of the function used to manage heap size.
066 * The xaxis represents the live ratio at the end of a major collection.
067 * The yaxis represents the GC load (GC time/total time).
068 * The interior of the matrix represents a ratio to shrink or grow
069 * the heap for a given pair of live ratio and GC load.
070 * The constraints on the matrix are:
071 * <ul>
072 * <li> function[0][0] is ignored.
073 * <li> All numbers in the first row must monotonically increase and
074 * must be in the range from 0 to 1 inclusive.</li>
075 * <li> All numbers in the first column must monotonically increase
076 * and must be in the range from 0 to 1 inclusive.</li>
077 * <li> There must be 0 and 1 values specified in both dimensions.
078 * <li> For all interior points in the matrix, the value must be
079 * greater than the liveRatio for that column.</li>
080 * </ul>
081 */
082 private static final double[][] function =
083 VM.activePlan.constraints().generational() ? generationalFunction : nongenerationalFunction;
084
085 private static long endLastMajorGC;
086 private static double accumulatedGCTime;
087
088 /**
089 * Initialize heap size parameters and the mechanisms
090 * used to adaptively change heap size.
091 */
092 public static void boot(Extent initial, Extent max) {
093 initialHeapSize = initial;
094 maxHeapSize = max;
095 if (initialHeapSize.GT(maxHeapSize))
096 maxHeapSize = initialHeapSize;
097 currentHeapSize = initialHeapSize;
098 VM.events.heapSizeChanged(currentHeapSize);
099 if (VM.VERIFY_ASSERTIONS) sanityCheck();
100 endLastMajorGC = VM.statistics.nanoTime();
101 }
102
103 /**
104 * @return the current heap size in bytes
105 */
106 public static Extent getCurrentHeapSize() {
107 return currentHeapSize;
108 }
109
110 /**
111 * Return the max heap size in bytes (as set by -Xmx).
112 *
113 * @return The max heap size in bytes (as set by -Xmx).
114 */
115 public static Extent getMaxHeapSize() {
116 return maxHeapSize;
117 }
118
119 /**
120 * Return the initial heap size in bytes (as set by -Xms).
121 *
122 * @return The initial heap size in bytes (as set by -Xms).
123 */
124 public static Extent getInitialHeapSize() {
125 return initialHeapSize;
126 }
127
128 /**
129 * Forcibly grow the heap by the given number of bytes.
130 * Used to provide headroom when handling an OutOfMemory
131 * situation.
132 * @param size number of bytes to grow the heap
133 */
134 public static void overrideGrowHeapSize(Extent size) {
135 currentHeapSize = currentHeapSize.plus(size);
136 VM.events.heapSizeChanged(currentHeapSize);
137 }
138
139 /**
140 * Record the time taken by the current GC;
141 * used to compute gc load, one of the inputs
142 * into the heap size management function
143 */
144 public static void recordGCTime(double time) {
145 accumulatedGCTime += time;
146 }
147
148 /**
149 * Reset timers used to compute gc load
150 */
151 public static void reset() {
152 endLastMajorGC = VM.statistics.nanoTime();
153 accumulatedGCTime = 0;
154 }
155
156 /**
157 * Decide how to grow/shrink the heap to respond
158 * to application's memory usage.
159 * @return {@code true} if heap size was changed, {@code false} otherwise
160 */
161 public static boolean considerHeapSize() {
162 Extent oldSize = currentHeapSize;
163 Extent reserved = Plan.reservedMemory();
164 double liveRatio = reserved.toLong() / ((double) currentHeapSize.toLong());
165 double ratio = computeHeapChangeRatio(liveRatio);
166 Extent newSize = Word.fromIntSignExtend((int)(ratio * (oldSize.toLong()>>LOG_BYTES_IN_MBYTE))).lsh(LOG_BYTES_IN_MBYTE).toExtent(); // do arith in MB to avoid overflow
167 if (newSize.LT(reserved)) newSize = reserved;
168 newSize = newSize.plus(BYTES_IN_MBYTE - 1).toWord().rshl(LOG_BYTES_IN_MBYTE).lsh(LOG_BYTES_IN_MBYTE).toExtent(); // round to next megabyte
169 if (newSize.GT(maxHeapSize)) newSize = maxHeapSize;
170 if (newSize.NE(oldSize) && newSize.GT(Extent.zero())) {
171 // Heap size is going to change
172 currentHeapSize = newSize;
173 if (Options.verbose.getValue() >= 2) {
174 Log.write("GC Message: Heap changed from "); Log.writeDec(oldSize.toWord().rshl(LOG_BYTES_IN_KBYTE));
175 Log.write("KB to "); Log.writeDec(newSize.toWord().rshl(LOG_BYTES_IN_KBYTE));
176 Log.writeln("KB");
177 }
178 VM.events.heapSizeChanged(currentHeapSize);
179 return true;
180 } else {
181 return false;
182 }
183 }
184
185 private static double computeHeapChangeRatio(double liveRatio) {
186 // (1) compute GC load.
187 long totalNanos = VM.statistics.nanoTime() - endLastMajorGC;
188 double totalTime = VM.statistics.nanosToMillis(totalNanos);
189 double gcLoad = accumulatedGCTime / totalTime;
190
191 if (liveRatio > 1) {
192 // Perhaps indicates bad bookkeeping in MMTk?
193 Log.write("GCWarning: Live ratio greater than 1: ");
194 Log.writeln(liveRatio);
195 liveRatio = 1;
196 }
197 if (gcLoad > 1) {
198 if (gcLoad > 1.0001) {
199 Log.write("GC Error: GC load was greater than 1!! ");
200 Log.writeln(gcLoad);
201 Log.write("GC Error:\ttotal time (ms) "); Log.writeln(totalTime);
202 Log.write("GC Error:\tgc time (ms) "); Log.writeln(accumulatedGCTime);
203 }
204 gcLoad = 1;
205 }
206 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(liveRatio >= 0);
207 if (VM.VERIFY_ASSERTIONS && gcLoad < -0.0) {
208 Log.write("gcLoad computed to be "); Log.writeln(gcLoad);
209 Log.write("\taccumulateGCTime was (ms) "); Log.writeln(accumulatedGCTime);
210 Log.write("\ttotalTime was (ms) "); Log.writeln(totalTime);
211 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(false);
212 }
213
214 if (Options.verbose.getValue() > 2) {
215 Log.write("Live ratio "); Log.writeln(liveRatio);
216 Log.write("GCLoad "); Log.writeln(gcLoad);
217 }
218
219 // (2) Find the 4 points surrounding gcLoad and liveRatio
220 int liveRatioUnder = 1;
221 int liveRatioAbove = function[0].length - 1;
222 int gcLoadUnder = 1;
223 int gcLoadAbove = function.length - 1;
224 if (liveRatio >= 1.0) {
225 // liveRatio has maxed out
226 liveRatioUnder = liveRatioAbove;
227 } else {
228 while (true) {
229 if (function[0][liveRatioUnder+1] > liveRatio) break;
230 liveRatioUnder++;
231 }
232 while (true) {
233 if (function[0][liveRatioAbove-1] <= liveRatio) break;
234 liveRatioAbove--;
235 }
236 }
237 if (gcLoad >= 1.0) {
238 // gcRatio has maxed out
239 gcLoadUnder = gcLoadAbove;
240 } else {
241 while (true) {
242 if (function[gcLoadUnder+1][0] > gcLoad) break;
243 gcLoadUnder++;
244 }
245 while (true) {
246 if (function[gcLoadAbove-1][0] <= gcLoad) break;
247 gcLoadAbove--;
248 }
249 }
250
251 // (3) Compute the heap change ratio
252 double factor = function[gcLoadUnder][liveRatioUnder];
253 if (liveRatioUnder != liveRatioAbove) {
254 // interpolate for liveRatio values in between two specified values in function table
255 double liveRatioFraction =
256 (liveRatio - function[0][liveRatioUnder]) /
257 (function[0][liveRatioAbove] - function[0][liveRatioUnder]);
258 double liveRatioDelta =
259 function[gcLoadUnder][liveRatioAbove] - function[gcLoadUnder][liveRatioUnder];
260 factor += (liveRatioFraction * liveRatioDelta);
261 }
262 if (gcLoadUnder != gcLoadAbove) {
263 // interpolate for gcLoad values in between two specified values in function table
264 double gcLoadFraction =
265 (gcLoad - function[gcLoadUnder][0]) /
266 (function[gcLoadAbove][0] - function[gcLoadUnder][0]);
267 double gcLoadDelta =
268 function[gcLoadAbove][liveRatioUnder] - function[gcLoadUnder][liveRatioUnder];
269 factor += (gcLoadFraction * gcLoadDelta);
270 }
271 if (Options.verbose.getValue() > 2) {
272 Log.write("Heap adjustment factor is ");
273 Log.writeln(factor);
274 }
275 return factor;
276 }
277
278 /**
279 * Check that function satisfies the invariants
280 */
281 private static void sanityCheck() {
282 // Check live ratio
283 double[] liveRatio = function[0];
284 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(liveRatio[1] == 0);
285 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(liveRatio[liveRatio.length-1] == 1);
286 for (int i = 2; i < liveRatio.length; i++) {
287 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(liveRatio[i-1] < liveRatio[i]);
288 for (int j = 1; j < function.length; j++) {
289 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(function[j][i] >= 1 || function[j][i] > liveRatio[i]);
290 }
291 }
292
293 // Check GC load
294 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(function[1][0] == 0);
295 int len = function.length;
296 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(function[len-1][0] == 1);
297 for (int i = 2; i < len; i++) {
298 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(function[i-1][0] < function[i][0]);
299 }
300
301 // Check that we have a rectangular matrix
302 for (int i = 1; i < function.length; i++) {
303 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(function[i-1].length == function[i].length);
304 }
305 }
306 }