1 /*
2 Title: heapsizing.cpp - parameters to adjust heap size
3
4 Copyright (c) Copyright David C.J. Matthews 2012, 2015, 2017
5
6 This library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License version 2.1 as published by the Free Software Foundation.
9
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with this library; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18
19 */
20
21 /*
22 This module is intended to deal with heap sizing based on measurements of the time taken
23 in the GC compared with the application code. Currently it is very basic.
24 This also provides GC timing information to the ML code as well as statistics and
25 debugging.
26 */
27
28 #ifdef HAVE_CONFIG_H
29 #include "config.h"
30 #elif defined(_WIN32)
31 #include "winconfig.h"
32 #else
33 #error "No configuration file"
34 #endif
35
36 #ifdef HAVE_WINDOWS_H
37 #include <windows.h>
38 #endif
39
40 #ifdef HAVE_STRING_H
41 #include <string.h>
42 #endif
43
44 #ifdef HAVE_UNISTD_H
45 #include <unistd.h> // For sysconf
46 #endif
47
48 #ifdef HAVE_SYS_TYPES_H
49 #include <sys/types.h>
50 #endif
51
52 #ifdef HAVE_SYS_SYSCTL_H
53 #include <sys/sysctl.h>
54 #endif
55
56 #ifdef HAVE_FLOAT_H
57 #include <float.h>
58 #endif
59
60 #ifdef HAVE_MATH_H
61 #include <math.h>
62 #endif
63
64 #ifdef HAVE_ASSERT_H
65 #include <assert.h>
66 #define ASSERT(x) assert(x)
67 #else
68 #define ASSERT(x)
69 #endif
70
71 #include "globals.h"
72 #include "arb.h"
73 #include "diagnostics.h"
74 #include "rts_module.h"
75 #include "timing.h"
76 #include "heapsizing.h"
77 #include "statistics.h"
78 #include "memmgr.h"
79
80 // The one and only parameter object
81 HeapSizeParameters gHeapSizeParameters;
82
83 #ifdef HAVE_WINDOWS_H
84 // There's no (documented) way to get the per-process hard page
85 // count in Windows. Cygwin uses GetProcessMemoryInfo to return the
86 // value in ru_majflt but this is actually incorrect because it returns
87 // the soft page count not the hard page count. We previously used the
88 // undocumented NtQuerySystemInformation call.
GetPaging(long)89 static long GetPaging(long)
90 {
91 return 0;
92 }
93 #else
GetPaging(long rusagePage)94 inline long GetPaging(long rusagePage)
95 {
96 return rusagePage;
97 }
98 #endif
99
HeapSizeParameters()100 HeapSizeParameters::HeapSizeParameters()
101 {
102 startPF = GetPaging(0);
103 fullGCNextTime = false;
104 performSharingPass = false;
105 lastAllocationSucceeded = true;
106 allocationFailedBeforeLastMajorGC = false;
107 minHeapSize = 0;
108 maxHeapSize = 0; // Unlimited
109 lastFreeSpace = 0;
110 pagingLimitSize = 0;
111 highWaterMark = 0;
112 sharingWordsRecovered = 0;
113 cumulativeSharingSaving = 0;
114 // Initial values until we've actually done a sharing pass.
115 sharingRecoveryRate = 0.5; // The structure sharing recovers half the heap.
116 sharingCostFactor = 2; // It doubles the cost
117 }
118
119 // These macros were originally in globals.h and used more generally.
120 // Since only K_to_words is used now this can be greatly simplified.
121 #define BITSPERWORD (sizeof(PolyWord)*8)
122 #define ROUNDUP_UNITS(m,n) (((m) + (n) - 1) / (n))
123 #define ROUNDUP(m,n) (ROUNDUP_UNITS(m,n) * (n))
124 #define K_to_words(k) ROUNDUP((k) * (1024 / sizeof(PolyWord)),BITSPERWORD)
125
126 // Returns physical memory size in bytes
127 static size_t GetPhysicalMemorySize(void);
128
129 // These are the maximum values for the number of words.
130 #if (SIZEOF_VOIDP == 4)
131 # define MAXIMUMADDRESS 0x3fffffff /* 4Gbytes as words */
132 #elif defined(POLYML32IN64)
133 # define MAXIMUMADDRESS 0xffffffff /* 16Gbytes as words */
134 #else
135 # define MAXIMUMADDRESS 0x1fffffffffffffff
136 #endif
137
138 // Set the initial size based on any parameters specified on the command line.
139 // Any of these can be zero indicating they should default.
SetHeapParameters(uintptr_t minsize,uintptr_t maxsize,uintptr_t initialsize,unsigned percent)140 void HeapSizeParameters::SetHeapParameters(uintptr_t minsize, uintptr_t maxsize, uintptr_t initialsize, unsigned percent)
141 {
142 minHeapSize = K_to_words(minsize); // If these overflow assume the result will be zero
143 maxHeapSize = K_to_words(maxsize);
144 uintptr_t initialSize = K_to_words(initialsize);
145
146 uintptr_t memsize = GetPhysicalMemorySize() / sizeof(PolyWord);
147
148 // If no maximum is given default it to 80% of the physical memory.
149 // This allows some space for the OS and other things.
150 // We now check maxsize so it should never exceed the maximum.
151 if (maxHeapSize == 0 || maxHeapSize > MAXIMUMADDRESS)
152 {
153 if (memsize != 0)
154 maxHeapSize = memsize - memsize / 5;
155 else maxHeapSize = MAXIMUMADDRESS;
156 // But if this must not be smaller than the minimum size.
157 if (maxHeapSize < minHeapSize) maxHeapSize = minHeapSize;
158 if (maxHeapSize < initialSize) maxHeapSize = initialSize;
159 }
160
161 // The default minimum is zero; in practice the live data size.
162
163 // The default initial size is the minimum if that has been provided,
164 // otherwise 8M words. There are applications that only require a small
165 // heap and if we set the heap large to begin with we'll never do a
166 // full GC and reduce it.
167 if (initialSize == 0)
168 {
169 if (minHeapSize != 0)
170 initialSize = minHeapSize;
171 else initialSize = 8 * gMem.DefaultSpaceSize();
172 // But not more than the maximum
173 if (initialSize > maxHeapSize) initialSize = maxHeapSize;
174 }
175 // Together with the constraints on user settings that ensures this holds.
176 ASSERT(initialSize >= minHeapSize && initialSize <= maxHeapSize);
177
178 // Initially we divide the space equally between the major and
179 // minor heaps. That means that there will definitely be space
180 // for the first minor GC to copy its data. This division can be
181 // changed later on.
182 gMem.SetSpaceForHeap(initialSize);
183 gMem.SetSpaceBeforeMinorGC(initialSize/2);
184 lastFreeSpace = initialSize;
185 highWaterMark = initialSize;
186
187 if (percent == 0)
188 userGCRatio = 1.0 / 9.0; // Default to 10% GC to 90% application
189 else
190 userGCRatio = (float)percent / (float)(100 - percent);
191
192 predictedRatio = lastMajorGCRatio = userGCRatio;
193
194 if (debugOptions & DEBUG_HEAPSIZE)
195 {
196 Log("Heap: Initial settings: Initial heap ");
197 LogSize(initialSize);
198 Log(" minimum ");
199 LogSize(minHeapSize);
200 Log(" maximum ");
201 LogSize(maxHeapSize);
202 Log(" target ratio %f\n", userGCRatio);
203 }
204 }
205
SetReservation(uintptr_t rsize)206 void HeapSizeParameters::SetReservation(uintptr_t rsize)
207 {
208 gMem.SetReservation(K_to_words(rsize));
209 }
210
211 // Called in the minor GC if a GC thread needs to grow the heap.
212 // Returns zero if the heap cannot be grown. "space" is the space required for the
213 // object (and length field) in case this is larger than the default size.
AddSpaceInMinorGC(uintptr_t space,bool isMutable)214 LocalMemSpace *HeapSizeParameters::AddSpaceInMinorGC(uintptr_t space, bool isMutable)
215 {
216 // See how much space is allocated to the major heap.
217 uintptr_t spaceAllocated = gMem.CurrentHeapSize() - gMem.CurrentAllocSpace();
218
219 // The new segment is either the default size or as large as
220 // necessary for the object.
221 uintptr_t spaceSize = gMem.DefaultSpaceSize();
222 #ifdef POLYML32IN64
223 // When we allocate a space in NewLocalSpace we take one word to ensure
224 // the that the first length word is on an odd-word boundary.
225 // We need to add one here to ensure there is sufficient space to do that.
226 // See AllocHeapSpace
227 space++;
228 #endif
229 if (space > spaceSize) spaceSize = space;
230
231 // We allow for extension if the total heap size after extending it
232 // plus one allocation area of the default size would not be more
233 // than the allowed heap size.
234 if (spaceAllocated + spaceSize + gMem.DefaultSpaceSize() <= gMem.SpaceForHeap())
235 {
236 LocalMemSpace *sp = gMem.NewLocalSpace(spaceSize, isMutable); // Return the space or zero if it failed
237 // If this is the first time the allocation failed report it.
238 if (sp == 0 && (debugOptions & DEBUG_HEAPSIZE) && lastAllocationSucceeded)
239 {
240 Log("Heap: Allocation of new heap segment size ");
241 LogSize(spaceSize);
242 Log(" failed. Limit reached?\n");
243 }
244 lastAllocationSucceeded = sp != 0;
245 return sp;
246 }
247 return 0; // Insufficient space
248 }
249
250 // Called in the major GC before the copy phase if the heap is more than
251 // 90% full. This should improve the efficiency of copying.
AddSpaceBeforeCopyPhase(bool isMutable)252 LocalMemSpace *HeapSizeParameters::AddSpaceBeforeCopyPhase(bool isMutable)
253 {
254 LocalMemSpace *sp = gMem.NewLocalSpace(gMem.DefaultSpaceSize(), isMutable);
255 if (sp == 0 && (debugOptions & DEBUG_HEAPSIZE) && lastAllocationSucceeded)
256 Log("Heap: Allocation of new heap segment failed. Limit reached?\n");
257 lastAllocationSucceeded = sp != 0;
258 return sp;
259 }
260
261 // The steepness of the curve.
262 #define PAGINGCOSTSTEEPNESS 20.0
263 // The additional cost at the boundary
264 #define PAGINGCOSTFACTOR 3.0
265 // The number of pages at the boundary
266 #define PAGINGCOUNTFACTOR 1000.0
267
268 // Called at the end of collection. This is where we should do the
269 // fine adjustment of the heap size to minimise the GC time.
270 // Growing the heap is just a matter of adjusting the limits. We
271 // don't actually need to allocate the space here.
272 // See also adjustHeapSizeAfterMinorGC for adjustments after a minor GC.
AdjustSizeAfterMajorGC(uintptr_t wordsRequired)273 void HeapSizeParameters::AdjustSizeAfterMajorGC(uintptr_t wordsRequired)
274 {
275 // Cumulative times since the last major GC
276 TIMEDATA gc, nonGc;
277 gc.add(majorGCSystemCPU);
278 gc.add(majorGCUserCPU);
279 nonGc.add(majorNonGCSystemCPU);
280 nonGc.add(majorNonGCUserCPU);
281
282 if (highWaterMark < heapSizeAtStart) highWaterMark = heapSizeAtStart;
283
284 uintptr_t heapSpace = gMem.SpaceForHeap() < highWaterMark ? gMem.SpaceForHeap() : highWaterMark;
285 currentSpaceUsed = wordsRequired;
286 for (std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++)
287 {
288 currentSpaceUsed += (*i)->allocatedSpace();
289 }
290 // N.B. Normally currentSpaceUsed will be less than the size of the heap
291 // except if wordsRequired is very large.
292
293 // The times for all the minor GCs up to this. The cost of this (major) GC
294 // is actually in minorGCUserCPU/minorGCSystemCPU.
295 TIMEDATA minorGC;
296 minorGC.add(gc);
297 minorGC.sub(minorGCUserCPU);
298 minorGC.sub(minorGCSystemCPU);
299
300 if (performSharingPass)
301 {
302 // We ran the sharing pass last time: calculate the actual recovery rate.
303 uintptr_t originalSpaceUsed = currentSpaceUsed + sharingWordsRecovered;
304 sharingRecoveryRate = (double)sharingWordsRecovered / (double)originalSpaceUsed;
305 if (debugOptions & DEBUG_HEAPSIZE)
306 Log("Heap: Sharing recovery rate was %0.3f and cost %0.3f seconds (%0.3f%% of total).\n",
307 sharingRecoveryRate, sharingCPU.toSeconds(), sharingCPU.toSeconds() / gc.toSeconds());
308 // The cost factor is the ratio of the cost of sharing to the cost without.
309 sharingCostFactor = sharingCPU.toSeconds() / (gc.toSeconds() - sharingCPU.toSeconds());
310 // Subtract the sharing cost from the GC cost because the initial estimate is
311 // the cost without running the sharing pass.
312 gc.sub(sharingCPU);
313 }
314
315 if (gc.toSeconds() != 0.0 && nonGc.toSeconds() != 0.0)
316 lastMajorGCRatio = gc.toSeconds() / nonGc.toSeconds();
317
318 if (debugOptions & DEBUG_HEAPSIZE)
319 {
320 uintptr_t currentFreeSpace = currentSpaceUsed < heapSpace ? 0: heapSpace - currentSpaceUsed;
321 Log("Heap: GC cpu time %2.3f non-gc time %2.3f ratio %0.3f for free space ",
322 gc.toSeconds(), nonGc.toSeconds(), lastMajorGCRatio);
323 LogSize((lastFreeSpace + currentFreeSpace)/2);
324 Log("\n");
325 Log("Heap: GC real time %2.3f non-gc time %2.3f ratio %0.3f\n",
326 majorGCReal.toSeconds(), majorNonGCReal.toSeconds(), majorGCReal.toSeconds()/majorNonGCReal.toSeconds());
327 Log("Heap: Total of minor GCs %2.3f, %2.3f of total\n", minorGC.toSeconds(), minorGC.toSeconds() / gc.toSeconds());
328 }
329
330 // Calculate the paging threshold.
331 if (pagingLimitSize != 0 && majorGCPageFaults == 0)
332 {
333 if (debugOptions & DEBUG_HEAPSIZE)
334 Log("No paging seen so resetting pageLimitSize\n");
335 pagingLimitSize = 0;
336 }
337 else if (pagingLimitSize != 0 || majorGCPageFaults != 0)
338 {
339 if (majorGCPageFaults == 0) majorGCPageFaults = 1; // Less than one
340 // Some paging detected. The expression here is the inverse of the one used to
341 // compute the paging contribution in the cost function.
342 double scaleFactor = 1.0 + log((double)majorGCPageFaults / PAGINGCOUNTFACTOR) / PAGINGCOSTSTEEPNESS;
343 ASSERT(scaleFactor > 0.0);
344 uintptr_t newLimit = (uintptr_t)((double)heapSpace / scaleFactor);
345 if (pagingLimitSize == 0)
346 pagingLimitSize = newLimit;
347 else
348 pagingLimitSize = (newLimit + pagingLimitSize) / 2;
349 }
350 if (allocationFailedBeforeLastMajorGC)
351 {
352 // If the last allocation failed then we may well have reached the
353 // maximum available memory. Set the paging limit to be the current
354 // heap size. We want to avoid hitting the limit because typically
355 // that happens when we try to extend the major heap in a minor GC
356 // resulting in the minor GC failing and a major GC starting.
357 if (pagingLimitSize == 0 || heapSizeAtStart < pagingLimitSize)
358 pagingLimitSize = heapSizeAtStart;
359 }
360 if (pagingLimitSize != 0 && (debugOptions & DEBUG_HEAPSIZE))
361 {
362 Log("Heap: Paging threshold adjusted to ");
363 LogSize(pagingLimitSize);
364 Log(" with %ld page faults\n", majorGCPageFaults);
365 }
366
367 // Calculate the new heap size and the predicted cost.
368 uintptr_t newHeapSize;
369 double cost;
370 bool atTarget = getCostAndSize(newHeapSize, cost, false);
371 // If we have been unable to allocate any more memory we may already
372 // be at the limit.
373 if (allocationFailedBeforeLastMajorGC && newHeapSize > heapSizeAtStart)
374 {
375 cost = costFunction(heapSizeAtStart, false, true);
376 atTarget = false;
377 }
378
379 if (atTarget)
380 {
381 // We are at the target level. We don't want to attempt sharing.
382 performSharingPass = false;
383 cumulativeSharingSaving = 0;
384 }
385 else
386 {
387 uintptr_t newHeapSizeWithSharing;
388 double costWithSharing;
389 // Get the cost and heap size if sharing was enabled. If we are at the
390 // limit, though, we need to work using the size we can achieve.
391 if (! allocationFailedBeforeLastMajorGC)
392 (void)getCostAndSize(newHeapSizeWithSharing, costWithSharing, true);
393 else
394 {
395 newHeapSizeWithSharing = heapSizeAtStart;
396 costWithSharing = costFunction(heapSizeAtStart, true, true);
397 }
398 // Run the sharing pass if that would give a lower cost.
399 // Subtract the cumulative saving that would have been made if the
400 // sharing had been run before. This is an estimate and depends on the
401 // extent to which a reduction in the heap earlier would be carried through
402 // to later GCs.
403 cumulativeSharingSaving =
404 cumulativeSharingSaving * ((double)currentSpaceUsed / (double)heapSpace);
405 if (debugOptions & DEBUG_HEAPSIZE)
406 Log("Heap: Cumulative sharing saving %0.2f\n", cumulativeSharingSaving);
407 if (costWithSharing - cumulativeSharingSaving < cost)
408 {
409 // Run the sharing pass next time.
410 performSharingPass = true;
411 cumulativeSharingSaving = 0;
412 }
413 else
414 {
415 // Don't run the sharing pass next time
416 performSharingPass = false;
417 // Running a sharing pass reduces the heap for subsequent
418 // runs. Add this into the cost.
419 double freeSharingCost = costFunction(newHeapSizeWithSharing, true, false);
420 if (freeSharingCost < cost && freeSharingCost > userGCRatio)
421 {
422 if (debugOptions & DEBUG_HEAPSIZE)
423 Log("Heap: Previous sharing would have saved %0.2f\n", cost - freeSharingCost);
424 cumulativeSharingSaving += cost - freeSharingCost;
425 }
426 }
427 }
428
429 if (debugOptions & DEBUG_HEAPSIZE)
430 {
431 if (performSharingPass)
432 Log("Heap: Next full GC will enable the sharing pass\n");
433 Log("Heap: Resizing from ");
434 LogSize(gMem.SpaceForHeap());
435 Log(" to ");
436 LogSize(newHeapSize);
437 Log(". Estimated ratio %2.2f\n", cost);
438 }
439 // Set the sizes.
440 gMem.SetSpaceForHeap(newHeapSize);
441 // Set the minor space size. It can potentially use the whole of the
442 // rest of the available heap but there could be a problem if that exceeds
443 // the available memory and causes paging. We need to raise the limit carefully.
444 // Also, if we use the whole of the heap we may not then be able to allocate
445 // new areas in the major heap without going over the limit. Restrict it to
446 // half of the available heap.
447 uintptr_t nextLimit = highWaterMark + highWaterMark / 32;
448 if (nextLimit > newHeapSize) nextLimit = newHeapSize;
449 // gMem.CurrentHeapSize() is the live space size.
450 if (gMem.CurrentHeapSize() > nextLimit)
451 gMem.SetSpaceBeforeMinorGC(0); // Run out of space
452 else gMem.SetSpaceBeforeMinorGC((nextLimit-gMem.CurrentHeapSize())/2);
453
454 lastFreeSpace = newHeapSize - currentSpaceUsed;
455 predictedRatio = cost;
456 }
457
458 // Called after a minor GC. Currently does nothing.
459 // See also adjustHeapSize for adjustments after a major GC.
AdjustSizeAfterMinorGC(uintptr_t spaceAfterGC,uintptr_t spaceBeforeGC)460 bool HeapSizeParameters::AdjustSizeAfterMinorGC(uintptr_t spaceAfterGC, uintptr_t spaceBeforeGC)
461 {
462 uintptr_t spaceCopiedOut = spaceAfterGC-spaceBeforeGC;
463 TIMEDATA gc, nonGC;
464 minorGCsSinceMajor++;
465 // Work out the ratio of GC to non-GC time since the last major GC. We can only adjust the heap size
466 // at a major GC. If we're now spending too much time in minor GCs we may need a major GC to adjust
467 // the size.
468 gc.add(minorGCSystemCPU);
469 gc.add(minorGCUserCPU);
470 nonGC.add(minorNonGCSystemCPU);
471 nonGC.add(minorNonGCUserCPU);
472 float g = gc.toSeconds() / nonGC.toSeconds();
473
474 if (debugOptions & DEBUG_HEAPSIZE)
475 {
476 Log("Heap: Space before ");
477 LogSize(spaceBeforeGC);
478 Log(", space after ");
479 LogSize(spaceAfterGC);
480 Log("\n");
481 Log("Heap: Minor resizing factors g = %f, recent pf = %ld, cumulative pf = %ld\n",
482 g, minorGCPageFaults, majorGCPageFaults);
483 }
484
485 if (highWaterMark < gMem.CurrentHeapSize()) highWaterMark = gMem.CurrentHeapSize();
486
487 uintptr_t nextLimit = highWaterMark + highWaterMark / 32;
488 if (nextLimit > gMem.SpaceForHeap()) nextLimit = gMem.SpaceForHeap();
489
490 // Set the space available for the allocation area to be the difference between the
491 // total heap size and the allowed heap size together with as much space as we copied
492 // on this GC. That allows for the next minor GC to copy the same amount without
493 // extending the heap. If the next minor GC adds more than this the heap will be
494 // extended and a corresponding amount deducted so that the heap shrinks again.
495 uintptr_t currHeap = gMem.CurrentHeapSize();
496 uintptr_t currAlloc = gMem.CurrentAllocSpace();
497 uintptr_t nonAlloc = currHeap - currAlloc + spaceCopiedOut;
498 // TODO: If we have limited the space to the high water mark + 1/32 but that is less
499 // than we really need we should increase it further.
500 uintptr_t allowedAlloc = nonAlloc >= nextLimit ? 0 : nextLimit - nonAlloc;
501 // Normally the allocation area will be empty but if we've failed to copy
502 // everything out, especially a big object, it may not be.
503 uintptr_t allocatedInAlloc = gMem.AllocatedInAlloc();
504
505 // If we hit the limit at the last major GC we have to be much more careful.
506 // If the minor GC cannot allocate a major GC space when it needs it the minor
507 // GC will fail immediately and a major GC will be started. It's better to
508 // risk doing more minor GCs than we need by making the allocation area smaller
509 // rather than run out of space.
510 if (allocationFailedBeforeLastMajorGC)
511 allowedAlloc = allowedAlloc / 2;
512 if (gMem.CurrentAllocSpace() - allocatedInAlloc != allowedAlloc)
513 {
514 if (debugOptions & DEBUG_HEAPSIZE)
515 {
516 Log("Heap: Adjusting space for allocation area from ");
517 LogSize(gMem.SpaceBeforeMinorGC());
518 Log(" to ");
519 LogSize(allowedAlloc);
520 Log("\n");
521 }
522 gMem.SetSpaceBeforeMinorGC(allowedAlloc);
523 if (allowedAlloc < gMem.DefaultSpaceSize() * 2 || minorGCPageFaults > 100)
524 return false; // Trigger full GC immediately.
525 }
526
527 // Trigger a full GC if the live data is very large or if we have exceeeded
528 // the target ratio over several GCs (this smooths out small variations).
529 if ((minorGCsSinceMajor > 4 && g > predictedRatio*0.8) || majorGCPageFaults > 100)
530 fullGCNextTime = true;
531 return true;
532 }
533
534 // Estimate the GC cost for a given heap size. The result is the ratio of
535 // GC time to application time.
536 // This is really guesswork.
costFunction(uintptr_t heapSize,bool withSharing,bool withSharingCost)537 double HeapSizeParameters::costFunction(uintptr_t heapSize, bool withSharing, bool withSharingCost)
538 {
539 uintptr_t heapSpace = gMem.SpaceForHeap() < highWaterMark ? gMem.SpaceForHeap() : highWaterMark;
540 uintptr_t currentFreeSpace = heapSpace < currentSpaceUsed ? 0: heapSpace - currentSpaceUsed;
541 uintptr_t averageFree = (lastFreeSpace + currentFreeSpace) / 2;
542 uintptr_t spaceUsed = currentSpaceUsed; // N.B. currentSpaceUsed includes the new space we want
543 if (heapSize <= currentSpaceUsed)
544 return 1.0E6;
545 // If we run the sharing pass the live space will be smaller.
546 if (withSharing)
547 spaceUsed -= (uintptr_t)((double)currentSpaceUsed * sharingRecoveryRate);
548 uintptr_t estimatedFree = heapSize - spaceUsed;
549 // The cost scales as the inverse of the amount of free space.
550 double result = lastMajorGCRatio * (double)averageFree / (double)estimatedFree;
551 // If we run the sharing pass the GC cost will increase.
552 if (withSharing && withSharingCost)
553 result += result*sharingCostFactor;
554
555 // The paging contribution depends on the page limit
556 double pagingCost = 0.0;
557 if (pagingLimitSize != 0)
558 {
559 double factor = ((double)heapSize - (double)pagingLimitSize) / (double)pagingLimitSize * PAGINGCOSTSTEEPNESS;
560 pagingCost = PAGINGCOSTFACTOR * exp(factor);
561 result += pagingCost;
562 }
563
564 if (debugOptions & DEBUG_HEAPSIZE)
565 {
566 Log("Heap: Cost for heap of size ");
567 LogSize(heapSize);
568 Log(" is %2.2f with paging contributing %2.2f with%s sharing pass.\n", result, pagingCost, withSharing ? "" : "out");
569 }
570 return result;
571 }
572
573 // Calculate the size for the minimum cost. Returns true if this is bounded by
574 // the user GC ratio and false if we minimised the cost
575 // TODO: This could definitely be improved although it's not likely to contribute much to
576 // the overall cost of a GC.
getCostAndSize(uintptr_t & heapSize,double & cost,bool withSharing)577 bool HeapSizeParameters::getCostAndSize(uintptr_t &heapSize, double &cost, bool withSharing)
578 {
579 bool isBounded = false;
580 uintptr_t heapSpace = gMem.SpaceForHeap() < highWaterMark ? gMem.SpaceForHeap() : highWaterMark;
581 // Calculate a new heap size. We allow a maximum doubling or halving of size.
582 // It's probably more important to limit the increase in case we hit paging.
583 uintptr_t sizeMax = heapSpace * 2;
584 if (sizeMax > maxHeapSize) sizeMax = maxHeapSize;
585 uintptr_t sizeMin = heapSpace / 2;
586 if (sizeMin < minHeapSize) sizeMin = minHeapSize;
587 // We mustn't reduce the heap size too far. If the application does a lot
588 // of work with few allocations and particularly if it calls PolyML.fullGC
589 // explicitly we could attempt to shrink the heap below the current live data size.
590 // Add 3*space size here. We require 2* after a minor GC. Add 1 for rounding.
591 uintptr_t minForAllocation = gMem.CurrentHeapSize() + gMem.DefaultSpaceSize() * 3;
592 if (minForAllocation > maxHeapSize) minForAllocation = maxHeapSize;
593 if (sizeMin < minForAllocation) sizeMin = minForAllocation;
594
595 double costMin = costFunction(sizeMin, withSharing, true);
596 if (costMin <= userGCRatio)
597 // If the cost of the minimum is below or at the target we
598 // use that and don't need to look further.
599 isBounded = true;
600 else
601 {
602 double costMax = costFunction(sizeMax, withSharing, true);
603 while (sizeMax > sizeMin + gMem.DefaultSpaceSize())
604 {
605 uintptr_t sizeNext = (sizeMin + sizeMax) / 2;
606 double cost = costFunction(sizeNext, withSharing, true);
607 if (cost < userGCRatio)
608 isBounded = true;
609 if (cost < userGCRatio || (costMax > costMin && costMax > userGCRatio))
610 {
611 sizeMax = sizeNext;
612 costMax = cost;
613 }
614 else
615 {
616 sizeMin = sizeNext;
617 costMin = cost;
618 }
619 ASSERT(costMin >= userGCRatio);
620 }
621 }
622 ASSERT(sizeMin >= minHeapSize && sizeMin <= maxHeapSize);
623 // If we are bounded by the user GC ratio we actually return the size and cost
624 // that is slightly above the user ratio.
625 heapSize = sizeMin;
626 cost = costMin;
627 return isBounded;
628 }
629
RunMajorGCImmediately()630 bool HeapSizeParameters::RunMajorGCImmediately()
631 {
632 if (fullGCNextTime)
633 {
634 fullGCNextTime = false;
635 return true;
636 }
637 return false;
638 }
639
640
GetLastStats(TIMEDATA & userTime,TIMEDATA & systemTime,TIMEDATA & realTime,long & pageCount)641 static bool GetLastStats(TIMEDATA &userTime, TIMEDATA &systemTime, TIMEDATA &realTime, long &pageCount)
642 {
643 #if (defined(_WIN32))
644 FILETIME kt, ut;
645 FILETIME ct, et; // Unused
646 FILETIME rt;
647 GetProcessTimes(GetCurrentProcess(), &ct, &et, &kt, &ut);
648 GetSystemTimeAsFileTime(&rt);
649 userTime = ut;
650 systemTime = kt;
651 realTime = rt;
652 pageCount = GetPaging(0);
653 #else
654 struct rusage rusage;
655 if (getrusage(RUSAGE_SELF, &rusage) != 0)
656 return false;
657 userTime = rusage.ru_utime;
658 systemTime = rusage.ru_stime;
659 struct timeval tv;
660 if (gettimeofday(&tv, NULL) != 0)
661 return false;
662 realTime = tv;
663 pageCount = GetPaging(rusage.ru_majflt);
664 #endif
665 return true;
666 }
667
RecordAtStartOfMajorGC()668 void HeapSizeParameters::RecordAtStartOfMajorGC()
669 {
670 heapSizeAtStart = gMem.CurrentHeapSize();
671 allocationFailedBeforeLastMajorGC = !lastAllocationSucceeded;
672 }
673
674 // This function is called at the beginning and end of garbage
675 // collection to record the time used.
676 // This also reports the GC time if GC debugging is enabled.
RecordGCTime(gcTime isEnd,const char * stage)677 void HeapSizeParameters::RecordGCTime(gcTime isEnd, const char *stage)
678 {
679 switch (isEnd)
680 {
681 case GCTimeStart:
682 {
683 // Start of GC
684 TIMEDATA userTime, systemTime, realTime;
685 long pageCount;
686 if (! GetLastStats(userTime, systemTime, realTime, pageCount))
687 break;
688 lastUsageU = userTime;
689 lastUsageS = systemTime;
690 lastRTime = realTime;
691 userTime.sub(startUsageU); // Times since the start
692 systemTime.sub(startUsageS);
693 realTime.sub(startRTime);
694 if (debugOptions & DEBUG_GC)
695 Log("GC: Non-GC time: CPU user: %0.3f system: %0.3f real: %0.3f page faults: %ld\n",
696 userTime.toSeconds(), systemTime.toSeconds(), realTime.toSeconds(), pageCount - startPF);
697 minorNonGCUserCPU.add(userTime);
698 majorNonGCUserCPU.add(userTime);
699 minorNonGCSystemCPU.add(systemTime);
700 majorNonGCSystemCPU.add(systemTime);
701 minorNonGCReal.add(realTime);
702 majorNonGCReal.add(realTime);
703 startUsageU = lastUsageU;
704 startUsageS = lastUsageS;
705 startRTime = lastRTime;
706 // Page faults in the application are included
707 minorGCPageFaults += pageCount - startPF;
708 majorGCPageFaults += pageCount - startPF;
709 startPF = pageCount;
710 break;
711 }
712
713 case GCTimeIntermediate:
714 // Report intermediate GC time for debugging
715 if (debugOptions & DEBUG_GC)
716 {
717 TIMEDATA userTime, systemTime, realTime;
718 long pageCount;
719 if (! GetLastStats(userTime, systemTime, realTime, pageCount))
720 break;
721 TIMEDATA nextU = userTime, nextS = systemTime, nextR = realTime;
722 userTime.sub(lastUsageU);
723 systemTime.sub(lastUsageS);
724 realTime.sub(lastRTime);
725
726 Log("GC: (%s) CPU user: %0.3f system: %0.3f real: %0.3f speed up %0.1f\n", stage, userTime.toSeconds(),
727 systemTime.toSeconds(), realTime.toSeconds(),
728 realTime.toSeconds() == 0.0 ? 0.0 : (userTime.toSeconds() + systemTime.toSeconds()) / realTime.toSeconds());
729 lastUsageU = nextU;
730 lastUsageS = nextS;
731 lastRTime = nextR;
732 }
733 break;
734
735 case GCTimeEnd: // End of GC.
736 {
737 TIMEDATA userTime, systemTime, realTime;
738 long pageCount;
739 if (! GetLastStats(userTime, systemTime, realTime, pageCount))
740 break;
741 lastUsageU = userTime;
742 lastUsageS = systemTime;
743 lastRTime = realTime;
744
745 userTime.sub(startUsageU); // Times since the start
746 systemTime.sub(startUsageS);
747 realTime.sub(startRTime);
748
749 totalGCUserCPU.add(userTime);
750 totalGCSystemCPU.add(systemTime);
751 totalGCReal.add(realTime);
752
753 if (debugOptions & DEBUG_GC)
754 {
755 Log("GC: CPU user: %0.3f system: %0.3f real: %0.3f speed up %0.1f page faults %ld\n", userTime.toSeconds(),
756 systemTime.toSeconds(), realTime.toSeconds(),
757 realTime.toSeconds() == 0.0 ? 0.0 : (userTime.toSeconds() + systemTime.toSeconds()) / realTime.toSeconds(),
758 pageCount - startPF);
759 }
760 minorGCUserCPU.add(userTime);
761 majorGCUserCPU.add(userTime);
762 minorGCSystemCPU.add(systemTime);
763 majorGCSystemCPU.add(systemTime);
764 minorGCReal.add(realTime);
765 majorGCReal.add(realTime);
766 startUsageU = lastUsageU;
767 startUsageS = lastUsageS;
768 startRTime = lastRTime;
769 minorGCPageFaults += pageCount - startPF;
770 majorGCPageFaults += pageCount - startPF;
771 startPF = pageCount;
772 globalStats.copyGCTimes(totalGCUserCPU, totalGCSystemCPU, totalGCReal);
773 }
774 break;
775 }
776 }
777
778 // Record the recovery rate and cost after running the GC sharing pass.
779 // TODO: We should probably average these because if we've run a full
780 // sharing pass and then a full GC after the recovery rate will be zero.
RecordSharingData(POLYUNSIGNED recovery)781 void HeapSizeParameters::RecordSharingData(POLYUNSIGNED recovery)
782 {
783 sharingWordsRecovered = recovery;
784 TIMEDATA userTime, systemTime, realTime;
785 long pageCount;
786 if (! GetLastStats(userTime, systemTime, realTime, pageCount))
787 return;
788 userTime.sub(startUsageU); // Times since the start
789 systemTime.sub(startUsageS);
790 sharingCPU = userTime;
791 sharingCPU.add(systemTime);
792 }
793
getGCUtime(TaskData * taskData) const794 Handle HeapSizeParameters::getGCUtime(TaskData *taskData) const
795 {
796 #if (defined(_WIN32))
797 return Make_arb_from_Filetime(taskData, totalGCUserCPU);
798 #else
799 return Make_arb_from_pair_scaled(taskData, ((struct timeval)totalGCUserCPU).tv_sec, ((struct timeval)totalGCUserCPU).tv_usec, 1000000);
800 #endif
801 }
802
getGCStime(TaskData * taskData) const803 Handle HeapSizeParameters::getGCStime(TaskData *taskData) const
804 {
805 #if (defined(_WIN32))
806 return Make_arb_from_Filetime(taskData, totalGCSystemCPU);
807 #else
808 return Make_arb_from_pair_scaled(taskData, ((struct timeval)totalGCSystemCPU).tv_sec, ((struct timeval)totalGCSystemCPU).tv_usec, 1000000);
809 #endif
810 }
811
Init()812 void HeapSizeParameters::Init()
813 {
814 #if (defined(_WIN32))
815 // Record an initial time of day to use as the basis of real timing
816 FILETIME s;
817 GetSystemTimeAsFileTime(&s);
818 #else
819 struct timeval s;
820 gettimeofday(&s, NULL);
821 #endif
822 startTime = s; // Overall start time
823 startRTime = startTime; // Start of this non-gc phase
824
825 resetMajorTimingData();
826 #if (defined(_WIN32))
827 startPF = GetPaging(0);
828 #else
829 startPF = GetPaging(0);
830 #endif
831 }
832
Final()833 void HeapSizeParameters::Final()
834 {
835 // Print the overall statistics
836 if (debugOptions & (DEBUG_GC|DEBUG_HEAPSIZE))
837 {
838 TIMEDATA userTime, systemTime, realTime;
839 #if (defined(_WIN32))
840 FILETIME kt, ut;
841 FILETIME ct, et; // Unused
842 FILETIME rt;
843 GetProcessTimes(GetCurrentProcess(), &ct, &et, &kt, &ut);
844 GetSystemTimeAsFileTime(&rt);
845 userTime.add(ut);
846 systemTime.add(kt);
847 realTime.add(rt);
848 #else
849 struct rusage rusage;
850 struct timeval tv;
851 if (getrusage(RUSAGE_SELF, &rusage) != 0 || gettimeofday(&tv, NULL) != 0)
852 return;
853 userTime.add(rusage.ru_utime);
854 systemTime.add(rusage.ru_stime);
855 realTime.add(tv);
856 #endif
857 realTime.sub(startTime);
858 userTime.sub(totalGCUserCPU);
859 systemTime.sub(totalGCSystemCPU);
860 realTime.sub(totalGCReal);
861 if (debugOptions & DEBUG_GC)
862 {
863 Log("GC (Total): Non-GC time: CPU user: %0.3f system: %0.3f real: %0.3f\n",
864 userTime.toSeconds(), systemTime.toSeconds(), realTime.toSeconds());
865 Log("GC (Total): GC time: CPU user: %0.3f system: %0.3f real: %0.3f\n",
866 totalGCUserCPU.toSeconds(), totalGCSystemCPU.toSeconds(), totalGCReal.toSeconds());
867 }
868 if (debugOptions & DEBUG_HEAPSIZE)
869 {
870 TIMEDATA gc, nonGc;
871 gc.add(totalGCUserCPU);
872 gc.add(totalGCSystemCPU);
873 nonGc.add(userTime);
874 nonGc.add(systemTime);
875 Log("Heap: Total CPU GC time %0.3fsecs, Non-GC %0.3fsecs, ratio %0.3f\n",
876 gc.toSeconds(), nonGc.toSeconds(), gc.toSeconds() / nonGc.toSeconds());
877 }
878 }
879 }
880
881
resetMinorTimingData(void)882 void HeapSizeParameters::resetMinorTimingData(void)
883 {
884 minorNonGCUserCPU.fromSeconds(0);
885 minorNonGCSystemCPU.fromSeconds(0);
886 minorNonGCReal.fromSeconds(0);
887 minorGCUserCPU.fromSeconds(0);
888 minorGCSystemCPU.fromSeconds(0);
889 minorGCReal.fromSeconds(0);
890 minorGCPageFaults = 0;
891 }
892
resetMajorTimingData(void)893 void HeapSizeParameters::resetMajorTimingData(void)
894 {
895 resetMinorTimingData();
896 majorNonGCUserCPU.fromSeconds(0);
897 majorNonGCSystemCPU.fromSeconds(0);
898 majorNonGCReal.fromSeconds(0);
899 majorGCUserCPU.fromSeconds(0);
900 majorGCSystemCPU.fromSeconds(0);
901 majorGCReal.fromSeconds(0);
902 majorGCPageFaults = 0;
903 minorGCsSinceMajor = 0;
904 }
905
906
907 class HeapSizing: public RtsModule
908 {
909 public:
910 virtual void Init(void);
911 virtual void Stop(void);
912 };
913
914 // Declare this. It will be automatically added to the table.
915 static HeapSizing heapSizeModule;
916
Init(void)917 void HeapSizing::Init(void)
918 {
919 gHeapSizeParameters.Init();
920 }
921
Stop()922 void HeapSizing::Stop()
923 {
924 gHeapSizeParameters.Final();
925 }
926
GetPhysicalMemorySize(void)927 static size_t GetPhysicalMemorySize(void)
928 {
929 size_t maxMem = (size_t)0-1; // Maximum unsigned value.
930 #if defined(HAVE_WINDOWS_H) // Windows including Cygwin
931 {
932 MEMORYSTATUSEX memStatEx;
933 memset(&memStatEx, 0, sizeof(memStatEx));
934 memStatEx.dwLength = sizeof(memStatEx);
935 if (! GlobalMemoryStatusEx(&memStatEx))
936 memStatEx.ullTotalPhys = 0; // Clobber any rubbish since it says it failed.
937 if (memStatEx.ullTotalPhys) // If it's non-zero assume it succeeded
938 {
939 DWORDLONG dwlMax = maxMem;
940 if (memStatEx.ullTotalPhys > dwlMax)
941 return maxMem;
942 else
943 return (size_t)memStatEx.ullTotalPhys;
944 }
945 }
946
947 #endif
948 #if defined(_SC_PHYS_PAGES) && defined(_SC_PAGESIZE)
949 {
950 // Linux and Solaris. This gives a silly value in Cygwin.
951 long physPages = sysconf(_SC_PHYS_PAGES);
952 long physPagesize = sysconf(_SC_PAGESIZE);
953 if (physPages != -1 && physPagesize != -1)
954 {
955 unsigned long maxPages = maxMem / physPagesize;
956 if ((unsigned long)physPages > maxPages)
957 return maxMem;
958 else // We've checked it won't overflow.
959 return physPages*physPagesize;
960 }
961 }
962 #endif
963 #if defined(HAVE_SYSCTL) && defined(CTL_HW)
964 // FreeBSD and Mac OS X. It seems HW_MEMSIZE has been added to
965 // Max OS X to return a 64-bit value.
966 #ifdef HW_MEMSIZE
967 {
968 static int mib[2] = { CTL_HW, HW_MEMSIZE };
969 uint64_t physMem = 0;
970 size_t len = sizeof(physMem);
971 if (sysctl(mib, 2, &physMem, &len, NULL, 0) == 0 && len == sizeof(physMem))
972 {
973 if (physMem > (uint64_t)maxMem)
974 return maxMem;
975 else
976 return (size_t)physMem;
977 }
978 }
979 #endif
980 #ifdef HW_PHYSMEM
981 // If HW_MEMSIZE isn't there or the call failed try this.
982 {
983 static int mib[2] = { CTL_HW, HW_PHYSMEM };
984 unsigned int physMem = 0;
985 size_t len = sizeof(physMem);
986 if (sysctl(mib, 2, &physMem, &len, NULL, 0) == 0 && len == sizeof(physMem))
987 {
988 if (physMem > maxMem)
989 return maxMem;
990 else
991 return physMem;
992 }
993 }
994 #endif
995 #endif
996 return 0; // Unable to determine
997 }
998
999