1 /* Copyright (C) 2009-2012 Matthew Fluet.
2 * Copyright (C) 2005-2008 Henry Cejtin, Matthew Fluet, Suresh
3 * Jagannathan, and Stephen Weeks.
5 * MLton is released under a BSD-style license.
6 * See the file MLton-LICENSE for details.
9 void displayHeap (__attribute__ ((unused
)) GC_state s
,
13 "\t\tnursery = "FMTPTR
"\n"
14 "\t\toldGenSize = %"PRIuMAX
"\n"
15 "\t\tsize = %"PRIuMAX
"\n"
16 "\t\tstart = "FMTPTR
"\n"
17 "\t\twithMapsSize = %"PRIuMAX
"\n",
18 (uintptr_t)heap
->nursery
,
19 (uintmax_t)heap
->oldGenSize
,
20 (uintmax_t)heap
->size
,
21 (uintptr_t)heap
->start
,
22 (uintmax_t)heap
->withMapsSize
);
26 void initHeap (__attribute__ ((unused
)) GC_state s
,
35 /* sizeofHeapDesired (s, l, cs)
37 * returns the desired heap size for a heap with l bytes live,
38 * given that the current heap size is cs.
40 size_t sizeofHeapDesired (GC_state s
, size_t liveSize
, size_t currentSize
) {
41 size_t liveMapsSize
, liveWithMapsSize
;
42 size_t currentMapsSize
, currentWithMapsSize
;
43 size_t resSize
, resWithMapsSize
;
44 size_t syslimSize
, syslimWithMapsSize
;
45 LOCAL_USED_FOR_ASSERT
size_t syslimMapsSize
;
48 syslimWithMapsSize
= alignDown (SIZE_MAX
, s
->sysvals
.pageSize
);
49 syslimSize
= invertSizeofCardMapAndCrossMap (s
, syslimWithMapsSize
);
50 syslimMapsSize
= sizeofCardMapAndCrossMap (s
, syslimSize
);
51 assert (syslimSize
+ syslimMapsSize
<= syslimWithMapsSize
);
53 liveSize
= align (liveSize
, s
->sysvals
.pageSize
);
54 if (syslimSize
< liveSize
)
55 die ("Out of memory with system-limit heap size %s.\n",
56 uintmaxToCommaString(syslimSize
));
57 liveMapsSize
= sizeofCardMapAndCrossMap (s
, liveSize
);
58 liveWithMapsSize
= liveSize
+ liveMapsSize
;
60 assert (isAligned (currentSize
, s
->sysvals
.pageSize
));
61 currentMapsSize
= sizeofCardMapAndCrossMap (s
, currentSize
);
62 currentWithMapsSize
= currentSize
+ currentMapsSize
;
64 ratio
= (double)s
->sysvals
.ram
/ (double)liveWithMapsSize
;
66 if (ratio
>= s
->controls
.ratios
.live
+ s
->controls
.ratios
.grow
) {
67 /* Cheney copying fits in RAM with desired ratios.live. */
68 resWithMapsSize
= (size_t)(liveWithMapsSize
* s
->controls
.ratios
.live
);
69 /* If the heap is currently close in size to what we want, leave
70 * it alone. Favor growing over shrinking.
72 if (0.5 * currentWithMapsSize
<= resWithMapsSize
73 and resWithMapsSize
<= 1.1 * currentWithMapsSize
) {
74 resWithMapsSize
= currentWithMapsSize
;
76 resWithMapsSize
= align (resWithMapsSize
, s
->sysvals
.pageSize
);
78 } else if (s
->controls
.ratios
.grow
>= s
->controls
.ratios
.copy
79 and ratio
>= 2.0 * s
->controls
.ratios
.copy
) {
80 /* Split RAM in half. Round down by pageSize so that the total
81 * amount of space taken isn't greater than RAM once rounding
82 * happens. This is so resizeHeapSecondary doesn't get confused
83 * and free a semispace in a misguided attempt to avoid paging.
85 resWithMapsSize
= alignDown (s
->sysvals
.ram
/ 2, s
->sysvals
.pageSize
);
86 } else if (ratio
>= s
->controls
.ratios
.copy
+ s
->controls
.ratios
.grow
) {
87 /* Cheney copying fits in RAM. */
88 resWithMapsSize
= s
->sysvals
.ram
- (size_t)(s
->controls
.ratios
.grow
* liveWithMapsSize
);
89 /* If the heap isn't too much smaller than what we want, leave it
90 * alone. On the other hand, if it is bigger we want to leave
91 * resWithMapsSize as is so that the heap is shrunk, to try to
94 if (1.0 * currentWithMapsSize
<= resWithMapsSize
95 and resWithMapsSize
<= 1.1 * currentWithMapsSize
) {
96 resWithMapsSize
= currentWithMapsSize
;
98 resWithMapsSize
= align (resWithMapsSize
, s
->sysvals
.pageSize
);
100 } else if (ratio
>= s
->controls
.ratios
.markCompact
) {
101 /* Mark compact fits in RAM. It doesn't matter what the current
102 * size is. If the heap is currently smaller, we are using
103 * copying and should switch to mark-compact. If the heap is
104 * currently bigger, we want to shrink back to RAM to avoid
107 resWithMapsSize
= s
->sysvals
.ram
;
108 } else { /* Required live ratio. */
109 double resWithMapsSizeD
= liveWithMapsSize
* (double)(s
->controls
.ratios
.markCompact
);
110 if (resWithMapsSizeD
> (double)syslimWithMapsSize
) {
111 resWithMapsSize
= syslimWithMapsSize
;
113 resWithMapsSize
= align ((size_t)resWithMapsSizeD
, s
->sysvals
.pageSize
);
115 /* If the current heap is bigger than resWithMapsSize, then
116 * shrinking always sounds like a good idea. However, depending
117 * on what pages the VM keeps around, growing could be very
118 * expensive, if it involves paging the entire heap. Hopefully
119 * the copy loop in growHeap will make the right thing happen.
122 if (s
->controls
.fixedHeap
> 0) {
123 if (resWithMapsSize
> s
->controls
.fixedHeap
/ 2)
124 resWithMapsSize
= s
->controls
.fixedHeap
;
126 resWithMapsSize
= s
->controls
.fixedHeap
/ 2;
127 if (resWithMapsSize
< liveWithMapsSize
)
128 die ("Out of memory with fixed heap size %s.",
129 uintmaxToCommaString(s
->controls
.fixedHeap
));
130 } else if (s
->controls
.maxHeap
> 0) {
131 if (resWithMapsSize
> s
->controls
.maxHeap
)
132 resWithMapsSize
= s
->controls
.maxHeap
;
133 if (resWithMapsSize
< liveWithMapsSize
)
134 die ("Out of memory with max heap size %s.",
135 uintmaxToCommaString(s
->controls
.maxHeap
));
137 resSize
= invertSizeofCardMapAndCrossMap (s
, resWithMapsSize
);
138 assert (isAligned (resSize
, s
->sysvals
.pageSize
));
140 fprintf (stderr
, "%s = sizeofHeapDesired (%s, %s)\n",
141 uintmaxToCommaString(resSize
),
142 uintmaxToCommaString(liveSize
),
143 uintmaxToCommaString(currentSize
));
144 assert (resSize
>= liveSize
);
148 void releaseHeap (GC_state s
, GC_heap h
) {
149 if (NULL
== h
->start
)
151 if (DEBUG
or s
->controls
.messages
)
153 "[GC: Releasing heap at "FMTPTR
" of size %s bytes (+ %s bytes card/cross map).]\n",
154 (uintptr_t)(h
->start
),
155 uintmaxToCommaString(h
->size
),
156 uintmaxToCommaString(h
->withMapsSize
- h
->size
));
157 GC_release (h
->start
, h
->withMapsSize
);
161 /* shrinkHeap (s, h, keepSize)
163 void shrinkHeap (GC_state s
, GC_heap h
, size_t keepSize
) {
164 assert (keepSize
<= h
->size
);
169 keepSize
= align (keepSize
, s
->sysvals
.pageSize
);
170 if (keepSize
< h
->size
) {
171 size_t keepWithMapsSize
;
172 keepWithMapsSize
= keepSize
+ sizeofCardMapAndCrossMap (s
, keepSize
);
173 if (DEBUG
or s
->controls
.messages
) {
175 "[GC: Shrinking heap at "FMTPTR
" of size %s bytes (+ %s bytes card/cross map)]\n",
176 (uintptr_t)(h
->start
),
177 uintmaxToCommaString(h
->size
),
178 uintmaxToCommaString(h
->withMapsSize
- h
->size
));
180 "[GC:\tto size %s bytes (+ %s bytes card/cross map).]\n",
181 uintmaxToCommaString(keepSize
),
182 uintmaxToCommaString(keepWithMapsSize
- keepSize
));
184 assert (isAligned (keepWithMapsSize
, s
->sysvals
.pageSize
));
185 assert (keepWithMapsSize
<= h
->withMapsSize
);
186 GC_release (h
->start
+ keepWithMapsSize
, h
->withMapsSize
- keepWithMapsSize
);
188 h
->withMapsSize
= keepWithMapsSize
;
192 /* createHeap (s, h, desiredSize, minSize)
194 * allocates a heap of the size necessary to work with desiredSize
195 * live data, and ensures that at least minSize is available. It
196 * returns TRUE if it is able to allocate the space, and returns FALSE
199 bool createHeap (GC_state s
, GC_heap h
,
203 size_t newWithMapsSize
;
206 fprintf (stderr
, "createHeap desired size = %s min size = %s\n",
207 uintmaxToCommaString(desiredSize
),
208 uintmaxToCommaString(minSize
));
209 if (desiredSize
< minSize
)
210 desiredSize
= minSize
;
211 minSize
= align (minSize
, s
->sysvals
.pageSize
);
212 desiredSize
= align (desiredSize
, s
->sysvals
.pageSize
);
213 assert (isHeapInit (h
) and NULL
== h
->start
);
214 /* Biased binary search (between minSize and desiredSize) for a
216 * Toggle back and forth between high and low addresses to decrease
217 * the chance of virtual memory fragmentation; important for large
219 * Always try a NULL address last.
222 const size_t maxFactor
= s
->sysvals
.pageSize
;
223 size_t lowSize
= minSize
;
224 size_t highSize
= desiredSize
;
226 unsigned int loopCount
= 0;
227 while (lowSize
<= highSize
) {
230 newWithMapsSize
= newSize
+ sizeofCardMapAndCrossMap (s
, newSize
);
232 assert (isAligned (newWithMapsSize
, s
->sysvals
.pageSize
));
234 const unsigned int addressCountLog2
= 5;
235 const unsigned int addressCount
= 0x1 << addressCountLog2
;
236 const size_t addressStep
= (size_t)0x1 << (ADDRESS_BITS
- addressCountLog2
);
237 #if ADDRESS_BITS == POINTER_BITS
238 const size_t addressHigh
= 0;
240 const size_t addressHigh
= (size_t)0x1 << ADDRESS_BITS
;
242 static bool addressScanDir
= TRUE
;
243 for (unsigned int i
= 1; i
<= addressCount
; i
++) {
244 size_t address
= (size_t)i
* addressStep
;
246 address
= addressHigh
- address
;
247 /* Always use 0 in the last step. */
248 if (i
== addressCount
)
251 newStart
= GC_mmapAnon ((pointer
)address
, newWithMapsSize
);
252 unless ((void*)-1 == newStart
) {
253 addressScanDir
= not addressScanDir
;
256 h
->withMapsSize
= newWithMapsSize
;
257 if (h
->size
> s
->cumulativeStatistics
.maxHeapSize
)
258 s
->cumulativeStatistics
.maxHeapSize
= h
->size
;
259 assert (minSize
<= h
->size
and h
->size
<= desiredSize
);
260 if (DEBUG
or s
->controls
.messages
)
262 "[GC: Created heap at "FMTPTR
" of size %s bytes (+ %s bytes card/cross map).]\n",
263 (uintptr_t)(h
->start
),
264 uintmaxToCommaString(h
->size
),
265 uintmaxToCommaString(h
->withMapsSize
- h
->size
));
269 size_t prevSize
= newSize
;
270 size_t prevWithMapsSize
= newWithMapsSize
;
271 highSize
= newSize
- s
->sysvals
.pageSize
;
272 newSize
= align((factor
-1) * (highSize
/ factor
) + (lowSize
/ factor
), s
->sysvals
.pageSize
);
273 if (s
->controls
.messages
) {
275 "[GC: Creating heap of size %s bytes (+ %s bytes card/cross map) cannot be satisfied,]\n",
276 uintmaxToCommaString (prevSize
),
277 uintmaxToCommaString (prevWithMapsSize
- prevSize
));
279 "[GC:\tbacking off by %s bytes with minimum size of %s bytes.]\n",
280 uintmaxToCommaString (prevSize
- newSize
),
281 uintmaxToCommaString (minSize
));
283 if (factor
< maxFactor
284 and ++loopCount
% 64 == 0) {
291 /* createHeapSecondary (s, desiredSize)
293 bool createHeapSecondary (GC_state s
, size_t desiredSize
) {
294 size_t desiredWithMapsSize
;
295 size_t minSize
, minWithMapsSize
;
296 desiredWithMapsSize
= desiredSize
+ sizeofCardMapAndCrossMap (s
, desiredSize
);
297 if ((s
->controls
.fixedHeap
> 0
298 and s
->heap
.withMapsSize
+ desiredWithMapsSize
> s
->controls
.fixedHeap
)
299 or (s
->controls
.maxHeap
> 0
300 and s
->heap
.withMapsSize
+ desiredWithMapsSize
> s
->controls
.maxHeap
))
302 minSize
= align (s
->heap
.oldGenSize
, s
->sysvals
.pageSize
);
303 minWithMapsSize
= minSize
+ sizeofCardMapAndCrossMap (s
, minSize
);
304 if (minWithMapsSize
> SIZE_MAX
- s
->heap
.withMapsSize
)
306 return createHeap (s
, &s
->secondaryHeap
, desiredSize
, s
->heap
.oldGenSize
);
309 /* remapHeap (s, h, desiredSize, minSize)
312 bool remapHeap (__attribute__ ((unused
)) GC_state s
,
313 __attribute__ ((unused
)) GC_heap h
,
314 __attribute__ ((unused
)) size_t desiredSize
,
315 __attribute__ ((unused
)) size_t minSize
) {
319 bool remapHeap (GC_state s
, GC_heap h
,
324 size_t newWithMapsSize
;
328 fprintf (stderr
, "remapHeap desired size = %s min size = %s\n",
329 uintmaxToCommaString(desiredSize
),
330 uintmaxToCommaString(minSize
));
331 assert (minSize
<= desiredSize
);
332 assert (desiredSize
>= h
->size
);
333 minSize
= align (minSize
, s
->sysvals
.pageSize
);
334 desiredSize
= align (desiredSize
, s
->sysvals
.pageSize
);
336 /* Biased binary search (between minSize and desiredSize) for a
340 size_t lowSize
= minSize
;
341 size_t highSize
= desiredSize
;
344 while (lowSize
<= highSize
) {
347 newWithMapsSize
= newSize
+ sizeofCardMapAndCrossMap (s
, newSize
);
349 assert (isAligned (newWithMapsSize
, s
->sysvals
.pageSize
));
351 newStart
= GC_mremap (h
->start
, h
->withMapsSize
, newWithMapsSize
);
352 if ((void*)-1 != newStart
) {
353 pointer origStart
= h
->start
;
354 size_t origSize
= h
->size
;
355 size_t origWithMapsSize
= h
->withMapsSize
;
358 h
->withMapsSize
= newWithMapsSize
;
359 if (h
->size
> s
->cumulativeStatistics
.maxHeapSize
)
360 s
->cumulativeStatistics
.maxHeapSize
= h
->size
;
361 assert (minSize
<= h
->size
and h
->size
<= desiredSize
);
362 if (DEBUG
or s
->controls
.messages
) {
364 "[GC: Remapped heap at "FMTPTR
" of size %s bytes (+ %s bytes card/cross map)]\n",
365 (uintptr_t)origStart
,
366 uintmaxToCommaString(origSize
),
367 uintmaxToCommaString(origWithMapsSize
- origSize
));
369 "[GC:\tto heap at "FMTPTR
" of size %s bytes (+ %s bytes card/cross map).]\n",
370 (uintptr_t)(h
->start
),
371 uintmaxToCommaString(h
->size
),
372 uintmaxToCommaString(h
->withMapsSize
- h
->size
));
374 lowSize
= newSize
+ s
->sysvals
.pageSize
;
375 newSize
= align((factor
-1) * (highSize
/ factor
) + (lowSize
/ factor
), s
->sysvals
.pageSize
);
378 size_t prevSize
= newSize
;
379 size_t prevWithMapsSize
= newWithMapsSize
;
380 highSize
= newSize
- s
->sysvals
.pageSize
;
381 newSize
= align((factor
-1) * (highSize
/ factor
) + (lowSize
/ factor
), s
->sysvals
.pageSize
);
382 if (s
->controls
.messages
) {
384 "[GC: Remapping heap at "FMTPTR
" of size %s bytes (+ %s bytes card/cross map)]\n",
385 (uintptr_t)(h
->start
),
386 uintmaxToCommaString (h
->size
),
387 uintmaxToCommaString (h
->withMapsSize
- h
->size
));
389 "[GC:\tto heap of size %s bytes (+ %s bytes card/cross map) cannot be satisfied,]\n",
390 uintmaxToCommaString (prevSize
),
391 uintmaxToCommaString (prevWithMapsSize
- prevSize
));
394 "[GC:\tbacking off by %s bytes.]\n",
395 uintmaxToCommaString (prevSize
- newSize
));
398 "[GC:\tbacking off by %s bytes with minimum size of %s bytes.]\n",
399 uintmaxToCommaString (prevSize
- newSize
),
400 uintmaxToCommaString (minSize
));
410 COPY_CHUNK_SIZE
= 0x2000000, /* 32M */
413 /* growHeap (s, desiredSize, minSize)
415 void growHeap (GC_state s
, size_t desiredSize
, size_t minSize
) {
417 struct GC_heap newHeap
;
424 assert (isAligned (desiredSize
, s
->sysvals
.pageSize
));
425 assert (isAligned (minSize
, s
->sysvals
.pageSize
));
426 assert (desiredSize
>= s
->heap
.size
);
427 if (DEBUG_RESIZING
or s
->controls
.messages
) {
429 "[GC: Growing heap at "FMTPTR
" of size %s bytes (+ %s bytes card/cross map),]\n",
430 (uintptr_t)s
->heap
.start
,
431 uintmaxToCommaString(s
->heap
.size
),
432 uintmaxToCommaString(s
->heap
.withMapsSize
- s
->heap
.size
));
434 "[GC:\tto desired size of %s bytes (+ %s bytes card/cross map)]\n",
435 uintmaxToCommaString(desiredSize
),
436 uintmaxToCommaString(sizeofCardMapAndCrossMap (s
, desiredSize
)));
438 "[GC:\tand minimum size of %s bytes (+ %s bytes card/cross map).]\n",
439 uintmaxToCommaString(minSize
),
440 uintmaxToCommaString(sizeofCardMapAndCrossMap (s
, minSize
)));
442 if (minSize
<= s
->heap
.size
) {
444 /* Demand proper growth from remapHeap and/or createHeap. */
445 minSize
= s
->heap
.size
+ s
->sysvals
.pageSize
;
451 origStart
= curHeapp
->start
;
452 liveSize
= curHeapp
->oldGenSize
;
453 assert (liveSize
<= curHeapp
->size
);
454 if (remapHeap (s
, curHeapp
, desiredSize
, minSize
)) {
458 shrinkHeap (s
, curHeapp
, liveSize
);
459 initHeap (s
, newHeapp
);
460 /* Allocate a space of the desired size. */
461 if (minSize
+ sizeofCardMapAndCrossMap (s
, minSize
) <= SIZE_MAX
- curHeapp
->withMapsSize
462 and createHeap (s
, newHeapp
, desiredSize
, minSize
)) {
467 from
= curHeapp
->start
+ liveSize
;
468 to
= newHeapp
->start
+ liveSize
;
469 remaining
= liveSize
;
470 shrinkHeap (s
, curHeapp
, remaining
);
472 assert (remaining
== (size_t)(from
- curHeapp
->start
)
473 and from
>= curHeapp
->start
474 and to
>= newHeapp
->start
);
475 if (remaining
< COPY_CHUNK_SIZE
) {
476 GC_memcpy (curHeapp
->start
, newHeapp
->start
, remaining
);
477 releaseHeap (s
, curHeapp
);
479 remaining
-= COPY_CHUNK_SIZE
;
480 from
-= COPY_CHUNK_SIZE
;
481 to
-= COPY_CHUNK_SIZE
;
482 GC_memcpy (from
, to
, COPY_CHUNK_SIZE
);
483 shrinkHeap (s
, curHeapp
, remaining
);
486 newHeapp
->oldGenSize
= liveSize
;
487 *curHeapp
= *newHeapp
;
488 } else if (useCurrent
) {
489 if (DEBUG_RESIZING
or s
->controls
.messages
) {
491 "[GC: Using heap at "FMTPTR
" of size %s bytes (+ %s bytes card/cross map).]\n",
492 (uintptr_t)s
->heap
.start
,
493 uintmaxToCommaString(s
->heap
.size
),
494 uintmaxToCommaString(s
->heap
.withMapsSize
- s
->heap
.size
));
496 } else if (s
->controls
.mayPageHeap
) {
497 /* Page the heap to disk and try again. */
500 if (DEBUG
or s
->controls
.messages
) {
502 "[GC: Writing heap at "FMTPTR
" of size %s bytes to disk.]\n",
503 (uintptr_t)curHeapp
->start
,
504 uintmaxToCommaString(liveSize
));
506 data
= GC_diskBack_write (curHeapp
->start
, liveSize
);
507 releaseHeap (s
, curHeapp
);
508 if (createHeap (s
, curHeapp
, desiredSize
, minSize
)) {
509 if (DEBUG
or s
->controls
.messages
) {
511 "[GC: Reading heap to "FMTPTR
" of size %s bytes from disk.]\n",
512 (uintptr_t)(curHeapp
->start
),
513 uintmaxToCommaString(liveSize
));
515 GC_diskBack_read (data
, curHeapp
->start
, liveSize
);
516 GC_diskBack_close (data
);
517 curHeapp
->oldGenSize
= liveSize
;
519 GC_diskBack_close (data
);
526 unless (origStart
== s
->heap
.start
) {
527 translateHeap (s
, origStart
, s
->heap
.start
, s
->heap
.oldGenSize
);
531 if (s
->controls
.messages
)
533 die ("Out of memory. Unable to allocate heap with %s bytes.\n",
534 uintmaxToCommaString(minSize
));
537 /* resizeHeap (s, minSize)
539 void resizeHeap (GC_state s
, size_t minSize
) {
543 fprintf (stderr
, "resizeHeap minSize = %s size = %s\n",
544 uintmaxToCommaString(minSize
),
545 uintmaxToCommaString(s
->heap
.size
));
546 desiredSize
= sizeofHeapDesired (s
, minSize
, s
->heap
.size
);
547 assert (isAligned (desiredSize
, s
->sysvals
.pageSize
));
548 assert (minSize
<= desiredSize
);
549 minSize
= align (minSize
, s
->sysvals
.pageSize
);
550 if (desiredSize
<= s
->heap
.size
) {
551 shrinkHeap (s
, &s
->heap
, desiredSize
);
553 releaseHeap (s
, &s
->secondaryHeap
);
554 growHeap (s
, desiredSize
, minSize
);
556 assert (s
->heap
.size
>= minSize
);
559 /* resizeHeapSecondary (s)
561 void resizeHeapSecondary (GC_state s
) {
562 size_t primarySize
, primaryWithMapsSize
;
563 size_t secondarySize
;
565 primarySize
= s
->heap
.size
;
566 primaryWithMapsSize
= s
->heap
.withMapsSize
;
567 secondarySize
= s
->secondaryHeap
.size
;
569 fprintf (stderr
, "secondaryHeapResize\n");
570 if (0 == secondarySize
)
572 if (2 * primaryWithMapsSize
> s
->sysvals
.ram
)
573 /* Holding on to secondaryHeap might cause paging. So don't. */
574 releaseHeap (s
, &s
->secondaryHeap
);
575 else if (secondarySize
< primarySize
) {
576 unless (remapHeap (s
, &s
->secondaryHeap
, primarySize
, primarySize
))
577 releaseHeap (s
, &s
->secondaryHeap
);
578 } else if (secondarySize
> primarySize
)
579 shrinkHeap (s
, &s
->secondaryHeap
, primarySize
);
580 assert (0 == s
->secondaryHeap
.size
581 or s
->heap
.size
== s
->secondaryHeap
.size
);