[MLton] card/cross map in heap

Matthew Fluet fluet at tti-c.org
Sat May 31 20:59:49 PDT 2008


Here is a patch that uses a much simpler management of the card/cross map.

The insight is that the resizeCardMapAndCrossMap function was a bit 
misleading, because it copies the contents of the old cross map to the new 
cross map.  However, the resizeCardMapAndCrossMap function is only ever 
called in the resizeHeap function, which, in turn, is only ever called in 
the majorGC function and the GC_unpack function.

After a major GC, the cross map must be cleared, because the major GC will 
have collected objects in the old generation, making the cross map 
invalid.  So, when resizing the heap (and, hence, resizing or moving the 
card/cross maps) after a major collection, it suffices to clear the 
resulting cross map, rather than clearing the cross map and then copying 
the cleared cross map to its new location.

It seems safe to assume that major garbage collections will be much more 
frequent than GC_unpack, so it makes sense to simplify the code for the 
common case.

This patch allocates space at the end of the ML object heap for the card 
and cross maps.

After creating, swapping, or resizing the heap, it uses 
setCardMapAndCrossMap to set gcState.generationalMaps appropriately 
(according to gcState.heap.start and gcState.heap.size) and clear the card 
and cross maps.  There is no complicated copying of card and cross maps 
when heaps are resized.

The only downside is that at a GC_unpack, after resizing the heap after a 
minor collection, we clear the cross map and, thus, are forced to 
recompute the cross map at the next minor collection.  (Note, however, 
that because the runtime does not always use generational collection, 
there may in fact have been no valid data in the cross map and there may 
be no minor collection before the next major collection.)

If this patch also eliminates the out of memory crashes, then I think it 
is preferable, since it has a simpler management of the card/cross map.
-------------- next part --------------
diff --git a/runtime/gc/cheney-copy.c b/runtime/gc/cheney-copy.c
index 40cad53..f671a8a 100644
--- a/runtime/gc/cheney-copy.c
+++ b/runtime/gc/cheney-copy.c
@@ -42,7 +42,7 @@ void swapHeapsForCheneyCopy (GC_state s) {
   tempHeap = s->secondaryHeap;
   s->secondaryHeap = s->heap;
   s->heap = tempHeap;
-  setCardMapAbsolute (s);
+  setCardMapAndCrossMap (s);
 }
 
 void majorCheneyCopyGC (GC_state s) {
@@ -85,7 +85,6 @@ void majorCheneyCopyGC (GC_state s) {
   bytesCopied = s->secondaryHeap.oldGenSize;
   s->cumulativeStatistics.bytesCopied += bytesCopied;
   swapHeapsForCheneyCopy (s);
-  clearCrossMap (s);
   s->lastMajorStatistics.kind = GC_COPYING;
   if (detailedGCTime (s))
     stopTiming (&ru_start, &s->cumulativeStatistics.ru_gcCopying);
diff --git a/runtime/gc/done.c b/runtime/gc/done.c
index ace8547..a7c1774 100644
--- a/runtime/gc/done.c
+++ b/runtime/gc/done.c
@@ -93,5 +93,4 @@ void GC_done (GC_state s) {
   }
   releaseHeap (s, &s->heap);
   releaseHeap (s, &s->secondaryHeap);
-  releaseCardMapAndCrossMap (s);
 }
diff --git a/runtime/gc/forward.c b/runtime/gc/forward.c
index 0a4a1f0..12ddb98 100644
--- a/runtime/gc/forward.c
+++ b/runtime/gc/forward.c
@@ -23,7 +23,6 @@ bool isObjptrInToSpace (GC_state s, objptr op) {
 /* forward (s, opp)
  * Forwards the object pointed to by *opp and updates *opp to point to
  * the new object.
- * It also updates the crossMap.
  */
 void forwardObjptr (GC_state s, objptr *opp) {
   objptr op;
diff --git a/runtime/gc/garbage-collection.c b/runtime/gc/garbage-collection.c
index 0f945dc..99086a6 100644
--- a/runtime/gc/garbage-collection.c
+++ b/runtime/gc/garbage-collection.c
@@ -41,8 +41,10 @@ void majorGC (GC_state s, size_t bytesRequested, bool mayResize) {
    * argument to createHeapSecondary above.  Above, it was an
    * estimate.  Here, it is exactly how much was live after the GC.
    */
-  if (mayResize)
+  if (mayResize) {
     resizeHeap (s, s->lastMajorStatistics.bytesLive + bytesRequested);
+    setCardMapAndCrossMap (s);
+  }
   resizeHeapSecondary (s);
   assert (s->heap.oldGenSize + bytesRequested <= s->heap.size);
 }
diff --git a/runtime/gc/generational.c b/runtime/gc/generational.c
index 12bce01..5217099 100644
--- a/runtime/gc/generational.c
+++ b/runtime/gc/generational.c
@@ -35,15 +35,15 @@ void displayGenerationalMaps (__attribute__ ((unused)) GC_state s,
   }
 }
 
-GC_cardMapIndex pointerToCardMapIndexAbsolute (pointer p) {
-  return (GC_cardMapIndex)p >> CARD_SIZE_LOG2;
-}
 GC_cardMapIndex sizeToCardMapIndex (size_t z) {
   return (GC_cardMapIndex)z >> CARD_SIZE_LOG2;
 }
 size_t cardMapIndexToSize (GC_cardMapIndex i) {
   return (size_t)i << CARD_SIZE_LOG2;
 }
+GC_cardMapIndex pointerToCardMapIndexAbsolute (pointer p) {
+  return (GC_cardMapIndex)p >> CARD_SIZE_LOG2;
+}
 GC_cardMapElem *pointerToCardMapAddr (GC_state s, pointer p) {
   GC_cardMapElem *res;
 
@@ -54,6 +54,10 @@ GC_cardMapElem *pointerToCardMapAddr (GC_state s, pointer p) {
   return res;
 }
 
+GC_crossMapIndex sizeToCrossMapIndex (size_t z) {
+  return (GC_crossMapIndex)z >> CARD_SIZE_LOG2;
+}
+
 bool isCardMarked (GC_state s, pointer p) {
   return (*pointerToCardMapAddr (s, p) != 0x0);
 }
@@ -104,6 +108,58 @@ pointer getCrossMapCardStart (GC_state s, pointer p) {
     : (p - 1) - ((uintptr_t)(p - 1) % CARD_SIZE);
 }
 
+size_t sizeofCardMap (GC_state s, size_t heapSize) {
+  unless (s->mutatorMarksCards) {
+    return 0;
+  }
+  assert (isAligned (heapSize, CARD_SIZE));
+
+  GC_cardMapIndex cardMapLength;
+  size_t cardMapSize;
+
+  cardMapLength = sizeToCardMapIndex (heapSize);
+  cardMapSize = align (cardMapLength * CARD_MAP_ELEM_SIZE, s->sysvals.pageSize);
+
+  return cardMapSize;
+}
+
+GC_cardMapIndex lenofCardMap (__attribute__ ((unused)) GC_state s, size_t cardMapSize) {
+  GC_cardMapIndex cardMapLength;
+
+  assert (isAligned (cardMapSize, s->sysvals.pageSize));
+  assert (isAligned (cardMapSize, CARD_MAP_ELEM_SIZE));
+
+  cardMapLength = (GC_cardMapIndex)(cardMapSize / CARD_MAP_ELEM_SIZE);
+
+  return cardMapLength;
+}
+
+size_t sizeofCrossMap (GC_state s, size_t heapSize) {
+  unless (s->mutatorMarksCards) {
+    return 0;
+  }
+  assert (isAligned (heapSize, CARD_SIZE));
+
+  GC_crossMapIndex crossMapLength;
+  size_t crossMapSize;
+
+  crossMapLength = sizeToCrossMapIndex (heapSize);
+  crossMapSize = align (crossMapLength * CROSS_MAP_ELEM_SIZE, s->sysvals.pageSize);
+
+  return crossMapSize;
+}
+
+GC_crossMapIndex lenofCrossMap (__attribute__ ((unused)) GC_state s, size_t crossMapSize) {
+  GC_crossMapIndex crossMapLength;
+
+  assert (isAligned (crossMapSize, s->sysvals.pageSize));
+  assert (isAligned (crossMapSize, CROSS_MAP_ELEM_SIZE));
+
+  crossMapLength = (GC_crossMapIndex)(crossMapSize / CROSS_MAP_ELEM_SIZE);
+
+  return crossMapLength;
+}
+
 void clearCardMap (GC_state s) {
   if (DEBUG_GENERATIONAL and DEBUG_DETAILED)
     fprintf (stderr, "clearCardMap ()\n");
@@ -119,7 +175,22 @@ void clearCrossMap (GC_state s) {
           s->generationalMaps.crossMapLength * CROSS_MAP_ELEM_SIZE);
 }
 
-void createCardMapAndCrossMap (GC_state s) {
+void clearCardMapAndCrossMap (GC_state s) {
+  clearCardMap (s);
+  clearCrossMap (s);
+}
+
+size_t sizeofCardMapAndCrossMap (GC_state s, size_t heapSize) {
+  size_t totalMapSize;
+
+  totalMapSize = sizeofCardMap (s, heapSize) + sizeofCrossMap (s, heapSize);
+
+  assert (isAligned (totalMapSize, s->sysvals.pageSize));
+
+  return totalMapSize;
+}
+
+void setCardMapAndCrossMap (GC_state s) {
   unless (s->mutatorMarksCards) {
     s->generationalMaps.cardMapLength = 0;
     s->generationalMaps.cardMap = NULL;
@@ -128,99 +199,30 @@ void createCardMapAndCrossMap (GC_state s) {
     s->generationalMaps.crossMap = NULL;
     return;
   }
-  assert (isAligned (s->heap.size, CARD_SIZE));
 
   GC_cardMapIndex cardMapLength;
   size_t cardMapSize;
   GC_crossMapIndex crossMapLength;
   size_t crossMapSize;
-  size_t totalMapSize;
 
-  cardMapLength = sizeToCardMapIndex (s->heap.size);
-  cardMapSize = align (cardMapLength * CARD_MAP_ELEM_SIZE, s->sysvals.pageSize);
-  cardMapLength = (GC_cardMapIndex)(cardMapSize / CARD_MAP_ELEM_SIZE);
+  cardMapSize = sizeofCardMap (s, s->heap.size);
+  cardMapLength = lenofCardMap (s, cardMapSize);
   s->generationalMaps.cardMapLength = cardMapLength;
 
-  crossMapLength = sizeToCardMapIndex (s->heap.size);
-  crossMapSize = align (crossMapLength * CROSS_MAP_ELEM_SIZE, s->sysvals.pageSize);
-  crossMapLength = (GC_crossMapIndex)(crossMapSize / CROSS_MAP_ELEM_SIZE);
+  crossMapSize = sizeofCrossMap (s, s->heap.size);
+  crossMapLength = lenofCrossMap (s, crossMapSize);
   s->generationalMaps.crossMapLength = crossMapLength;
 
-  totalMapSize = cardMapSize + crossMapSize;
+  /* The card map starts at the end of the heap. */
+  assert (s->heap.withMapsSize == s->heap.size + cardMapSize + crossMapSize);
   s->generationalMaps.cardMap =
-    GC_mmapAnon_safe (NULL, totalMapSize);
+    (GC_cardMap) (s->heap.start + s->heap.size);
   s->generationalMaps.crossMap =
-    (s->generationalMaps.cardMap + (cardMapSize / CARD_MAP_ELEM_SIZE));
-  if (DEBUG_MEM or s->controls.messages)
-    fprintf (stderr,
-             "[GC: Created card/cross map at "FMTPTR" of size %s bytes.]\n",
-             (uintptr_t)(s->generationalMaps.cardMap),
-             uintmaxToCommaString(totalMapSize));
-  if (DEBUG_CARD_MARKING)
-    fprintf (stderr, "cardMap = "FMTPTR"  crossMap = "FMTPTR"\n",
-             (uintptr_t)s->generationalMaps.cardMap,
-             (uintptr_t)s->generationalMaps.crossMap);
+    (GC_crossMap) (s->heap.start + s->heap.size + cardMapSize);
   setCardMapAbsolute (s);
-  clearCardMap (s);
-  clearCrossMap (s);
-}
-
-void releaseCardMapAndCrossMapAux (GC_state s,
-                                   GC_cardMap cardMap,
-                                   size_t cardMapSize,
-                                   __attribute__ ((unused)) GC_crossMap crossMap,
-                                   size_t crossMapSize) {
-
-  size_t totalMapSize;
-
-  assert (crossMap == cardMap + (cardMapSize / CARD_MAP_ELEM_SIZE));
-  totalMapSize = cardMapSize + crossMapSize;
-  if (DEBUG_MEM or s->controls.messages)
-    fprintf (stderr,
-             "[GC: Releasing card/cross map at "FMTPTR" of size %s bytes.]\n",
-             (uintptr_t)cardMap,
-             uintmaxToCommaString(totalMapSize));
-  GC_release (cardMap, totalMapSize);
+  clearCardMapAndCrossMap (s);
 }
 
-void releaseCardMapAndCrossMap (GC_state s) {
-  unless (s->mutatorMarksCards)
-    return;
-
-  GC_cardMap cardMap;
-  size_t cardMapSize;
-  GC_crossMap crossMap;
-  size_t crossMapSize;
-
-  cardMap = s->generationalMaps.cardMap;
-  cardMapSize = s->generationalMaps.cardMapLength * CARD_MAP_ELEM_SIZE;
-  crossMap = s->generationalMaps.crossMap;
-  crossMapSize = s->generationalMaps.crossMapLength * CROSS_MAP_ELEM_SIZE;
-  releaseCardMapAndCrossMapAux (s, cardMap, cardMapSize, crossMap, crossMapSize);
-}
-
-void resizeCardMapAndCrossMap (GC_state s) {
-  if (s->mutatorMarksCards
-      and (s->generationalMaps.cardMapLength * CARD_MAP_ELEM_SIZE)
-          != align (sizeToCardMapIndex (s->heap.size), s->sysvals.pageSize)) {
-    GC_cardMap oldCardMap;
-    size_t oldCardMapSize;
-    GC_crossMap oldCrossMap;
-    size_t oldCrossMapSize;
-
-    oldCardMap = s->generationalMaps.cardMap;
-    oldCardMapSize = s->generationalMaps.cardMapLength * CARD_MAP_ELEM_SIZE;
-    oldCrossMap = s->generationalMaps.crossMap;
-    oldCrossMapSize = s->generationalMaps.crossMapLength * CROSS_MAP_ELEM_SIZE;
-    createCardMapAndCrossMap (s);
-    GC_memcpy ((pointer)oldCrossMap, (pointer)s->generationalMaps.crossMap,
-               min (s->generationalMaps.crossMapLength * CROSS_MAP_ELEM_SIZE,
-                    oldCrossMapSize));
-    releaseCardMapAndCrossMapAux (s,
-                                  oldCardMap, oldCardMapSize,
-                                  oldCrossMap, oldCrossMapSize);
-  }
-}
 
 #if ASSERT
 /* isCrossMapOk is a slower, but easier to understand, way of
diff --git a/runtime/gc/generational.h b/runtime/gc/generational.h
index d42f6ad..270176a 100644
--- a/runtime/gc/generational.h
+++ b/runtime/gc/generational.h
@@ -61,11 +61,13 @@ static void displayGenerationalMaps (GC_state s,
                                      struct GC_generationalMaps *generational,
                                      FILE *stream);
 
-static inline GC_cardMapIndex pointerToCardMapIndexAbsolute (pointer p);
 static inline GC_cardMapIndex sizeToCardMapIndex (size_t z);
 static inline size_t cardMapIndexToSize (GC_cardMapIndex i);
+static inline GC_cardMapIndex pointerToCardMapIndexAbsolute (pointer p);
 static inline GC_cardMapElem *pointerToCardMapAddr (GC_state s, pointer p);
 
+static inline GC_crossMapIndex sizeToCrossMapIndex (size_t z);
+
 static inline bool isCardMarked (GC_state s, pointer p);
 static inline void markCard (GC_state s, pointer p);
 static inline void markIntergenerationalPointer (GC_state s, pointer *pp);
@@ -74,14 +76,16 @@ static inline void markIntergenerationalObjptr (GC_state s, objptr *opp);
 static inline void setCardMapAbsolute (GC_state s);
 static inline pointer getCrossMapCardStart (GC_state s, pointer p);
 
+static inline size_t sizeofCardMap (GC_state s, size_t heapSize);
+static inline GC_cardMapIndex lenofCardMap (GC_state s, size_t cardMapSize);
+static inline size_t sizeofCrossMap (GC_state s, size_t heapSize);
+static inline GC_crossMapIndex lenofCrossMap (GC_state s, size_t crossMapSize);
+static size_t sizeofCardMapAndCrossMap (GC_state s, size_t heapSize);
+
 static inline void clearCardMap (GC_state s);
 static inline void clearCrossMap (GC_state s);
-static void createCardMapAndCrossMap (GC_state s);
-static void releaseCardMapAndCrossMap (GC_state s);
-static void releaseCardMapAndCrossMapAux (GC_state s,
-                                          GC_cardMap cardMap, size_t cardMapSize,
-                                          GC_crossMap crossMap, size_t crossMapSize);
-static void resizeCardMapAndCrossMap (GC_state s);
+static inline void clearCardMapAndCrossMap (GC_state s);
+static void setCardMapAndCrossMap (GC_state s);
 
 #if ASSERT
 static bool isCrossMapOk (GC_state s);
diff --git a/runtime/gc/heap.c b/runtime/gc/heap.c
index 22e48fb..9440cbd 100644
--- a/runtime/gc/heap.c
+++ b/runtime/gc/heap.c
@@ -12,11 +12,13 @@ void displayHeap (__attribute__ ((unused)) GC_state s,
           "\t\tnursery = "FMTPTR"\n"
           "\t\toldGenSize = %"PRIuMAX"\n"
           "\t\tsize = %"PRIuMAX"\n"
-          "\t\tstart = "FMTPTR"\n",
+          "\t\tstart = "FMTPTR"\n"
+          "\t\twithMapsSize = %"PRIuMAX"\n",
           (uintptr_t)heap->nursery,
           (uintmax_t)heap->oldGenSize,
           (uintmax_t)heap->size,
-          (uintptr_t)heap->start);
+          (uintptr_t)heap->start,
+          (uintmax_t)heap->withMapsSize);
 }
 
 
@@ -26,6 +28,7 @@ void initHeap (__attribute__ ((unused)) GC_state s,
   h->oldGenSize = 0;
   h->size = 0;
   h->start = NULL;
+  h->withMapsSize = 0;
 }
 
 /* sizeofHeapDesired (s, l, cs)
@@ -114,26 +117,32 @@ void releaseHeap (GC_state s, GC_heap h) {
              "[GC: Releasing heap at "FMTPTR" of size %s bytes.]\n",
              (uintptr_t)(h->start),
              uintmaxToCommaString(h->size));
-  GC_release (h->start, h->size);
+  GC_release (h->start, h->withMapsSize);
   initHeap (s, h);
 }
 
-void shrinkHeap (GC_state s, GC_heap h, size_t keep) {
-  assert (keep <= h->size);
-  if (0 == keep) {
+/* shrinkHeap (s, h, keepSize)
+ */
+void shrinkHeap (GC_state s, GC_heap h, size_t keepSize) {
+  assert (keepSize <= h->size);
+  if (0 == keepSize) {
     releaseHeap (s, h);
     return;
   }
-  keep = align (keep, s->sysvals.pageSize);
-  if (keep < h->size) {
+  keepSize = align (keepSize, s->sysvals.pageSize);
+  if (keepSize < h->size) {
+    size_t keepWithMapsSize;
     if (DEBUG or s->controls.messages)
       fprintf (stderr,
                "[GC: Shrinking heap at "FMTPTR" of size %s bytes to size %s bytes.]\n",
                (uintptr_t)(h->start),
                uintmaxToCommaString(h->size),
-               uintmaxToCommaString(keep));
-    GC_decommit (h->start + keep, h->size - keep);
-    h->size = keep;
+               uintmaxToCommaString(keepSize));
+    keepWithMapsSize = keepSize + sizeofCardMapAndCrossMap (s, keepSize);
+    assert (keepWithMapsSize <= h->withMapsSize);
+    GC_decommit (h->start + keepWithMapsSize, h->withMapsSize - keepWithMapsSize);
+    h->size = keepSize;
+    h->withMapsSize = keepWithMapsSize;
   }
 }
 
@@ -148,6 +157,8 @@ bool createHeap (GC_state s, GC_heap h,
                  size_t desiredSize,
                  size_t minSize) {
   size_t backoff;
+  size_t newSize;
+  size_t newWithMapsSize;
 
   if (DEBUG_MEM)
     fprintf (stderr, "createHeap  desired size = %s  min size = %s\n",
@@ -159,7 +170,7 @@ bool createHeap (GC_state s, GC_heap h,
   minSize = align (minSize, s->sysvals.pageSize);
   desiredSize = align (desiredSize, s->sysvals.pageSize);
   assert (0 == h->size and NULL == h->start);
-  backoff = (desiredSize - minSize) / 20;
+  backoff = (desiredSize - minSize) / 16;
   if (0 == backoff)
     backoff = 1; /* enough to terminate the loop below */
   backoff = align (backoff, s->sysvals.pageSize);
@@ -168,7 +179,7 @@ bool createHeap (GC_state s, GC_heap h,
    * to fail.  This is important for large heaps.
    * Note that the loop always trys a NULL address last.
    */
-  h->size = desiredSize;
+  newSize = desiredSize;
   do {
     const unsigned int countLog2 = 5;
     const unsigned int count = 0x1 << countLog2;
@@ -182,9 +193,13 @@ bool createHeap (GC_state s, GC_heap h,
     static bool direction = TRUE;
     unsigned int i;
 
-    assert (isAligned (h->size, s->sysvals.pageSize));
+    newWithMapsSize = newSize + sizeofCardMapAndCrossMap (s, newSize);
+
+    assert (isAligned (newWithMapsSize, s->sysvals.pageSize));
+
     for (i = 1; i <= count; i++) {
       size_t address;
+      pointer newStart;
 
       address = (size_t)i * step;
       if (direction)
@@ -193,46 +208,39 @@ bool createHeap (GC_state s, GC_heap h,
       if (i == count)
         address = 0;
 
-      h->start = GC_mmapAnon ((pointer)address, h->size);
-      if ((void*)-1 == h->start)
-        h->start = (void*)NULL;
-      unless ((void*)NULL == h->start) {
+      newStart = GC_mmapAnon ((pointer)address, newWithMapsSize);
+      unless ((void*)-1 == newStart) {
         direction = not direction;
+        h->start = newStart;
+        h->size = newSize;
+        h->withMapsSize = newWithMapsSize;
         if (h->size > s->cumulativeStatistics.maxHeapSize)
           s->cumulativeStatistics.maxHeapSize = h->size;
+        assert (minSize <= h->size and h->size <= desiredSize);
         if (DEBUG or s->controls.messages)
           fprintf (stderr,
                    "[GC: Created heap at "FMTPTR" of size %s bytes.]\n",
                    (uintptr_t)(h->start),
                    uintmaxToCommaString(h->size));
-        assert (h->size >= minSize);
         return TRUE;
       }
     }
     if (s->controls.messages) {
       fprintf (stderr,
                "[GC: Creating heap of size %s bytes cannot be satisfied,]\n",
-               uintmaxToCommaString (h->size));
+               uintmaxToCommaString (newSize));
       fprintf (stderr,
                "[GC:\tbacking off by %s bytes with minimum size of %s bytes.]\n",
                uintmaxToCommaString (backoff),
                uintmaxToCommaString (minSize));
     }
-    if (h->size > minSize
-        and (h->size - backoff) < minSize) {
-      h->size = minSize;
-    } else {
-      h->size -= backoff;
-    }
-
-    size_t nextSize = h->size - backoff;
-    if (nextSize < minSize and minSize < h->size) {
-      h->size = minSize;
+    size_t nextSize = newSize - backoff;
+    if (nextSize < minSize and minSize < newSize) {
+      newSize = minSize;
     } else {
-      h->size = nextSize;
+      newSize = nextSize;
     }
-  } while (h->size >= minSize);
-  h->size = 0;
+  } while (newSize >= minSize);
   return FALSE;
 }
 
@@ -253,31 +261,67 @@ bool remapHeap (GC_state s, GC_heap h,
                 size_t desiredSize,
                 size_t minSize) {
   size_t backoff;
-  size_t size;
+  size_t newSize;
+  size_t newWithMapsSize;
+  size_t origSize;
+  size_t origWithMapsSize;
 
 #if not HAS_REMAP
   return FALSE;
 #endif
+  if (DEBUG_MEM)
+    fprintf (stderr, "remapHeap  desired size = %s  min size = %s\n",
+             uintmaxToCommaString(desiredSize),
+             uintmaxToCommaString(minSize));
   assert (minSize <= desiredSize);
   assert (desiredSize >= h->size);
+  minSize = align (minSize, s->sysvals.pageSize);
   desiredSize = align (desiredSize, s->sysvals.pageSize);
-  backoff = (desiredSize - minSize) / 20;
+  backoff = (desiredSize - minSize) / 16;
   if (0 == backoff)
     backoff = 1; /* enough to terminate the loop below */
   backoff = align (backoff, s->sysvals.pageSize);
-  for (size = desiredSize; size >= minSize; size -= backoff) {
-    pointer new;
+  origSize = h->size;
+  origWithMapsSize = origSize + sizeofCardMapAndCrossMap (s, origSize);
+  newSize = desiredSize;
+  do {
+    pointer newStart;
+
+    newWithMapsSize = newSize + sizeofCardMapAndCrossMap (s, newSize);
+
+    assert (isAligned (newWithMapsSize, s->sysvals.pageSize));
 
-    new = GC_mremap (h->start, h->size, size);
-    unless ((void*)-1 == new) {
-      h->start = new;
-      h->size = size;
+    newStart = GC_mremap (h->start, origWithMapsSize, newWithMapsSize);
+    unless ((void*)-1 == newStart) {
+      h->start = newStart;
+      h->size = newSize;
+      h->withMapsSize = newWithMapsSize;
       if (h->size > s->cumulativeStatistics.maxHeapSize)
         s->cumulativeStatistics.maxHeapSize = h->size;
       assert (minSize <= h->size and h->size <= desiredSize);
+      if (DEBUG or s->controls.messages)
+	fprintf (stderr,
+		 "[GC: Remapped heap at "FMTPTR" to size %s bytes.]\n",
+		 (uintptr_t)(h->start),
+		 uintmaxToCommaString(h->size));
       return TRUE;
     }
-  }
+    if (s->controls.messages) {
+      fprintf (stderr,
+               "[GC: Remapping heap to size %s bytes cannot be satisfied,]\n",
+               uintmaxToCommaString (newSize));
+      fprintf (stderr,
+               "[GC:\tbacking off by %s bytes with minimum size of %s bytes.]\n",
+               uintmaxToCommaString (backoff),
+               uintmaxToCommaString (minSize));
+    }
+    size_t nextSize = newSize - backoff;
+    if (nextSize < minSize and minSize < newSize) {
+      newSize = minSize;
+    } else {
+      newSize = nextSize;
+    }
+  } while (newSize > minSize);
   return FALSE;
 }
 
@@ -290,11 +334,15 @@ enum {
 void growHeap (GC_state s, size_t desiredSize, size_t minSize) {
   GC_heap curHeapp;
   struct GC_heap newHeap;
+  GC_heap newHeapp;
 
-  pointer orig;
+  pointer origStart;
   size_t size;
 
   assert (desiredSize >= s->heap.size);
+  /* If desiredSize >= s->heap.size, then don't shrink the heap. */
+  if (minSize < s->heap.size)
+    minSize = s->heap.size;
   if (DEBUG_RESIZING or s->controls.messages) {
     fprintf (stderr,
              "[GC: Growing heap at "FMTPTR" of size %s bytes,]\n",
@@ -306,28 +354,32 @@ void growHeap (GC_state s, size_t desiredSize, size_t minSize) {
              uintmaxToCommaString(minSize));
   }
   curHeapp = &s->heap;
-  orig = curHeapp->start;
+  newHeapp = &newHeap;
+  origStart = curHeapp->start;
   size = curHeapp->oldGenSize;
-  assert (size <= s->heap.size);
-  if (remapHeap (s, curHeapp, desiredSize, minSize))
+  assert (size <= curHeapp->size);
+  if (remapHeap (s, curHeapp, desiredSize, minSize)) {
     goto done;
+  }
   shrinkHeap (s, curHeapp, size);
-  initHeap (s, &newHeap);
+  initHeap (s, newHeapp);
   /* Allocate a space of the desired size. */
-  if (createHeap (s, &newHeap, desiredSize, minSize)) {
+  if (createHeap (s, newHeapp, desiredSize, minSize)) {
     pointer from;
     pointer to;
     size_t remaining;
 
     from = curHeapp->start + size;
-    to = newHeap.start + size;
+    to = newHeapp->start + size;
     remaining = size;
+    GC_decommit (origStart + curHeapp->size, sizeofCardMapAndCrossMap (s, curHeapp->size));
 copy:
     assert (remaining == (size_t)(from - curHeapp->start)
             and from >= curHeapp->start
-            and to >= newHeap.start);
+            and to >= newHeapp->start);
     if (remaining < COPY_CHUNK_SIZE) {
-      GC_memcpy (orig, newHeap.start, remaining);
+      GC_memcpy (origStart, newHeapp->start, remaining);
+      GC_release (origStart, curHeapp->size);
     } else {
       remaining -= COPY_CHUNK_SIZE;
       from -= COPY_CHUNK_SIZE;
@@ -336,9 +388,8 @@ copy:
       shrinkHeap (s, curHeapp, remaining);
       goto copy;
     }
-    releaseHeap (s, curHeapp);
-    newHeap.oldGenSize = size;
-    *curHeapp = newHeap;
+    newHeapp->oldGenSize = size;
+    *curHeapp = *newHeapp;
   } else if (s->controls.mayPageHeap) {
     /* Page the heap to disk and try again. */
     void *data;
@@ -346,26 +397,21 @@ copy:
     if (DEBUG or s->controls.messages) {
       fprintf (stderr,
                "[GC: Writing heap at "FMTPTR" of size %s bytes to disk.]\n",
-               (uintptr_t)orig,
+               (uintptr_t)origStart,
                uintmaxToCommaString(size));
     }
-    data = GC_diskBack_write (orig, size);
+    data = GC_diskBack_write (origStart, size);
     releaseHeap (s, curHeapp);
-    releaseCardMapAndCrossMap (s);
     if (createHeap (s, curHeapp, desiredSize, minSize)) {
       if (DEBUG or s->controls.messages) {
         fprintf (stderr,
-                 "[GC: Reading heap at "FMTPTR" of size %s bytes from disk.]\n",
-                 (uintptr_t)orig,
+                 "[GC: Reading heap to "FMTPTR" of size %s bytes from disk.]\n",
+                 (uintptr_t)(curHeapp->start),
                  uintmaxToCommaString(size));
       }
       GC_diskBack_read (data, curHeapp->start, size);
       GC_diskBack_close (data);
       curHeapp->oldGenSize = size;
-      if (s->mutatorMarksCards) {
-        createCardMapAndCrossMap (s);
-        updateCrossMap (s);
-      }
     } else {
       GC_diskBack_close (data);
       if (s->controls.messages)
@@ -380,9 +426,8 @@ copy:
          uintmaxToCommaString(minSize));
   }
 done:
-  unless (orig == s->heap.start) {
-    translateHeap (s, orig, s->heap.start, s->heap.oldGenSize);
-    setCardMapAbsolute (s);
+  unless (origStart == s->heap.start) {
+    translateHeap (s, origStart, s->heap.start, s->heap.oldGenSize);
   }
 }
 
@@ -397,13 +442,12 @@ void resizeHeap (GC_state s, size_t minSize) {
              uintmaxToCommaString(s->heap.size));
   desiredSize = sizeofHeapDesired (s, minSize, s->heap.size);
   assert (minSize <= desiredSize);
-  if (desiredSize <= s->heap.size)
+  if (desiredSize <= s->heap.size) {
     shrinkHeap (s, &s->heap, desiredSize);
-  else {
+  } else {
     releaseHeap (s, &s->secondaryHeap);
     growHeap (s, desiredSize, minSize);
   }
-  resizeCardMapAndCrossMap (s);
   assert (s->heap.size >= minSize);
 }
 
diff --git a/runtime/gc/heap.h b/runtime/gc/heap.h
index 80be37b..bb2baa4 100644
--- a/runtime/gc/heap.h
+++ b/runtime/gc/heap.h
@@ -12,13 +12,14 @@
  * All ML objects (including ML execution stacks) are allocated in a
  * contiguous heap.  The heap has the following general layout:
  * 
- *  ----------------------------------------------------
- *  |    old generation    |               |  nursery  |
- *  ----------------------------------------------------
+ *  -------------------------------------------------------------------------
+ *  |    old generation    |               |  nursery  | cardMap | crossMap |
+ *  -------------------------------------------------------------------------
  *  |------oldGenSize------|
  *  |-----------------------size-----------------------|
  *  ^                                      ^
  *  start                                  nursery
+ *  |------------------------------withMapsSize-----------------------------|
 */
 
 typedef struct GC_heap {
@@ -26,6 +27,7 @@ typedef struct GC_heap {
   size_t oldGenSize; /* size of old generation */
   size_t size; /* size of heap */
   pointer start; /* start of heap (and old generation) */
+  size_t withMapsSize; /* size of heap with card/cross maps */
 } *GC_heap;
 
 #define GC_HEAP_LIMIT_SLOP 512
@@ -51,7 +53,7 @@ static inline void initHeap (GC_state s, GC_heap h);
 static inline size_t sizeofHeapDesired (GC_state s, size_t live, size_t currentSize);
 
 static inline void releaseHeap (GC_state s, GC_heap h);
-static void shrinkHeap (GC_state s, GC_heap h, size_t keep);
+static void shrinkHeap (GC_state s, GC_heap h, size_t keepSize);
 static bool createHeap (GC_state s, GC_heap h, size_t desiredSize, size_t minSize);
 static bool createHeapSecondary (GC_state s, size_t desiredSize);
 static bool remapHeap (GC_state s, GC_heap h, size_t desiredSize, size_t minSize);
diff --git a/runtime/gc/init-world.c b/runtime/gc/init-world.c
index 7bb5ef4..7a50e97 100644
--- a/runtime/gc/init-world.c
+++ b/runtime/gc/init-world.c
@@ -144,7 +144,7 @@ void initWorld (GC_state s) {
   createHeap (s, &s->heap,
               sizeofHeapDesired (s, s->lastMajorStatistics.bytesLive, 0),
               s->lastMajorStatistics.bytesLive);
-  createCardMapAndCrossMap (s);
+  setCardMapAndCrossMap (s);
   start = alignFrontier (s, s->heap.start);
   s->frontier = start;
   s->limitPlusSlop = s->heap.start + s->heap.size;
diff --git a/runtime/gc/mark-compact.c b/runtime/gc/mark-compact.c
index 4bdf755..e4c98e0 100644
--- a/runtime/gc/mark-compact.c
+++ b/runtime/gc/mark-compact.c
@@ -391,7 +391,6 @@ void majorMarkCompactGC (GC_state s) {
   foreachGlobalObjptr (s, threadInternalObjptr);
   updateForwardPointersForMarkCompact (s, currentStack);
   updateBackwardPointersAndSlideForMarkCompact (s, currentStack);
-  clearCrossMap (s);
   bytesHashConsed = s->lastMajorStatistics.bytesHashConsed;
   s->cumulativeStatistics.bytesHashConsed += bytesHashConsed;
   bytesMarkCompacted = s->heap.oldGenSize;
diff --git a/runtime/gc/pack.c b/runtime/gc/pack.c
index e89cdf9..cd6cc0a 100644
--- a/runtime/gc/pack.c
+++ b/runtime/gc/pack.c
@@ -23,6 +23,7 @@ void GC_pack (GC_state s) {
   keep = s->heap.oldGenSize * 1.1;
   if (keep <= s->heap.size) {
     shrinkHeap (s, &s->heap, keep);
+    setCardMapAndCrossMap (s);
     setGCStateCurrentHeap (s, 0, 0);
     setGCStateCurrentThreadAndStack (s);
   }
@@ -49,6 +50,7 @@ void GC_unpack (GC_state s) {
   enterGC (s);
   minorGC (s);
   resizeHeap (s, s->heap.oldGenSize);
+  setCardMapAndCrossMap (s);
   resizeHeapSecondary (s);
   setGCStateCurrentHeap (s, 0, 0);
   setGCStateCurrentThreadAndStack (s);
diff --git a/runtime/gc/virtual-memory.c b/runtime/gc/virtual-memory.c
index 39e024b..9c0c44b 100644
--- a/runtime/gc/virtual-memory.c
+++ b/runtime/gc/virtual-memory.c
@@ -7,14 +7,15 @@
  */
 
 void *GC_mmapAnon_safe (void *p, size_t length) {
-        void *result;
+  void *result;
 
-        result = GC_mmapAnon (p, length);
-        if ((void*)-1 == result) {
-                GC_displayMem ();
-                die ("Out of memory.");
-        }
-        return result;
+  result = GC_mmapAnon (p, length);
+  if ((void*)-1 == result) {
+    GC_displayMem ();
+    die ("Out of memory.  Unable to allocate %s bytes.\n",
+         uintmaxToCommaString(length));
+  }
+  return result;
 }
 
 static inline void GC_memcpy (pointer src, pointer dst, size_t size) {
diff --git a/runtime/gc/world.c b/runtime/gc/world.c
index e5a65d6..3235b08 100644
--- a/runtime/gc/world.c
+++ b/runtime/gc/world.c
@@ -25,7 +25,7 @@ void loadWorldFromFILE (GC_state s, FILE *f) {
   createHeap (s, &s->heap,
               sizeofHeapDesired (s, s->heap.oldGenSize, 0),
               s->heap.oldGenSize);
-  createCardMapAndCrossMap (s);
+  setCardMapAndCrossMap (s);
   fread_safe (s->heap.start, 1, s->heap.oldGenSize, f);
   if ((*(s->loadGlobals)) (f) != 0) diee("couldn't load globals");
   // unless (EOF == fgetc (file))


More information about the MLton mailing list