runtime/gc/forward.c

   1 /* Copyright (C) 2012,2016 Matthew Fluet.
   2  * Copyright (C) 1999-2008 Henry Cejtin, Matthew Fluet, Suresh
   3  *    Jagannathan, and Stephen Weeks.
   4  * Copyright (C) 1997-2000 NEC Research Institute.
   5  *
   6  * MLton is released under a BSD-style license.
   7  * See the file MLton-LICENSE for details.
   8  */
   9
  10 #if ASSERT
  11 bool isPointerInToSpace (GC_state s, pointer p) {
  12   return (not (isPointer (p))
  13           or (s->forwardState.toStart <= p and p < s->forwardState.toLimit));
  14 }
  15
  16 bool isObjptrInToSpace (GC_state s, objptr op) {
  17   pointer p;
  18
  19   if (not (isObjptr (op)))
  20     return TRUE;
  21   p = objptrToPointer (op, s->forwardState.toStart);
  22   return isPointerInToSpace (s, p);
  23 }
  24 #endif
  25
  26 /* getFwdPtrp (p)
  27  *
  28  * Returns a pointer to the forwarding pointer for the object pointed to by p.
  29  */
  30 objptr* getFwdPtrp (pointer p) {
  31   return (objptr*)(getHeaderp(p));
  32 }
  33
  34 /* getFwdPtr (p)
  35  *
  36  * Returns the forwarding pointer for the object pointed to by p.
  37  */
  38 objptr getFwdPtr (pointer p) {
  39   return *(getFwdPtrp(p));
  40 }
  41
  42 /* hasFwdPtr (p)
  43  *
  44  * Returns true if the object pointed to by p has a valid forwarding pointer.
  45  */
  46 bool hasFwdPtr (pointer p) {
  47   return (not (GC_VALID_HEADER_MASK & getHeader(p)));
  48 }
  49
  50 /* forward (s, opp)
  51  * Forwards the object pointed to by *opp and updates *opp to point to
  52  * the new object.
  53  */
  54 void forwardObjptr (GC_state s, objptr *opp) {
  55   objptr op;
  56   pointer p;
  57
  58   op = *opp;
  59   p = objptrToPointer (op, s->heap.start);
  60   if (DEBUG_DETAILED)
  61     fprintf (stderr,
  62              "forwardObjptr  opp = "FMTPTR"  op = "FMTOBJPTR"  p = "FMTPTR"\n",
  63              (uintptr_t)opp, op, (uintptr_t)p);
  64   assert (isObjptrInFromSpace (s, *opp));
  65   if (DEBUG_DETAILED and hasFwdPtr(p))
  66     fprintf (stderr, "  already FORWARDED\n");
  67   if (not (hasFwdPtr(p))) { /* forward the object */
  68     size_t size, skip;
  69
  70     size_t metaDataBytes, objectBytes;
  71     GC_objectTypeTag tag;
  72     uint16_t bytesNonObjptrs, numObjptrs;
  73
  74     splitHeader(s, getHeader(p), &tag, NULL, &bytesNonObjptrs, &numObjptrs);
  75
  76     /* Compute the space taken by the header and object body. */
  77     if ((NORMAL_TAG == tag) or (WEAK_TAG == tag)) { /* Fixed size object. */
  78       metaDataBytes = GC_NORMAL_METADATA_SIZE;
  79       objectBytes = bytesNonObjptrs + (numObjptrs * OBJPTR_SIZE);
  80       skip = 0;
  81     } else if (ARRAY_TAG == tag) {
  82       metaDataBytes = GC_ARRAY_METADATA_SIZE;
  83       objectBytes = sizeofArrayNoMetaData (s, getArrayLength (p),
  84                                            bytesNonObjptrs, numObjptrs);
  85       skip = 0;
  86     } else { /* Stack. */
  87       bool current;
  88       size_t reservedNew;
  89       GC_stack stack;
  90
  91       assert (STACK_TAG == tag);
  92       metaDataBytes = GC_STACK_METADATA_SIZE;
  93       stack = (GC_stack)p;
  94       current = getStackCurrent(s) == stack;
  95
  96       reservedNew = sizeofStackShrinkReserved (s, stack, current);
  97       if (reservedNew < stack->reserved) {
  98         if (DEBUG_STACKS or s->controls.messages)
  99           fprintf (stderr,
 100                    "[GC: Shrinking stack of size %s bytes to size %s bytes, using %s bytes.]\n",
 101                    uintmaxToCommaString(stack->reserved),
 102                    uintmaxToCommaString(reservedNew),
 103                    uintmaxToCommaString(stack->used));
 104         stack->reserved = reservedNew;
 105       }
 106       objectBytes = sizeof (struct GC_stack) + stack->used;
 107       skip = stack->reserved - stack->used;
 108     }
 109     size = metaDataBytes + objectBytes;
 110     assert (s->forwardState.back + size + skip <= s->forwardState.toLimit);
 111     /* Copy the object. */
 112     GC_memcpy (p - metaDataBytes, s->forwardState.back, size);
 113     /* If the object has a valid weak pointer, link it into the weaks
 114      * for update after the copying GC is done.
 115      */
 116     if ((WEAK_TAG == tag) and (numObjptrs == 1)) {
 117       GC_weak w;
 118
 119       w = (GC_weak)(s->forwardState.back + GC_NORMAL_METADATA_SIZE + offsetofWeak (s));
 120       if (DEBUG_WEAK)
 121         fprintf (stderr, "forwarding weak "FMTPTR" ",
 122                  (uintptr_t)w);
 123       if (isObjptr (w->objptr)
 124           and (not s->forwardState.amInMinorGC
 125                or isObjptrInNursery (s, w->objptr))) {
 126         if (DEBUG_WEAK)
 127           fprintf (stderr, "linking\n");
 128         w->link = s->weaks;
 129         s->weaks = w;
 130       } else {
 131         if (DEBUG_WEAK)
 132           fprintf (stderr, "not linking\n");
 133       }
 134     }
 135     /* Store the forwarding pointer in the old object header. */
 136     *(getFwdPtrp(p)) = pointerToObjptr (s->forwardState.back + metaDataBytes,
 137                                         s->forwardState.toStart);
 138     assert (hasFwdPtr(p));
 139     /* Update the back of the queue. */
 140     s->forwardState.back += size + skip;
 141     assert (isAligned ((size_t)s->forwardState.back + GC_NORMAL_METADATA_SIZE,
 142                        s->alignment));
 143   }
 144   *opp = getFwdPtr(p);
 145   if (DEBUG_DETAILED)
 146     fprintf (stderr,
 147              "forwardObjptr --> *opp = "FMTPTR"\n",
 148              (uintptr_t)*opp);
 149   assert (isObjptrInToSpace (s, *opp));
 150 }
 151
 152 void forwardObjptrIfInNursery (GC_state s, objptr *opp) {
 153   objptr op;
 154   pointer p;
 155
 156   op = *opp;
 157   p = objptrToPointer (op, s->heap.start);
 158   if (p < s->heap.nursery)
 159     return;
 160   if (DEBUG_GENERATIONAL)
 161     fprintf (stderr,
 162              "forwardObjptrIfInNursery  opp = "FMTPTR"  op = "FMTOBJPTR"  p = "FMTPTR"\n",
 163              (uintptr_t)opp, op, (uintptr_t)p);
 164   assert (s->heap.nursery <= p and p < s->limitPlusSlop);
 165   forwardObjptr (s, opp);
 166 }
 167
 168 /* Walk through all the cards and forward all intergenerational pointers. */
 169 void forwardInterGenerationalObjptrs (GC_state s) {
 170   GC_cardMapElem *cardMap;
 171   GC_crossMapElem *crossMap;
 172   pointer oldGenStart, oldGenEnd;
 173
 174   size_t cardIndex, maxCardIndex;
 175   pointer cardStart, cardEnd;
 176   pointer objectStart;
 177
 178   if (DEBUG_GENERATIONAL)
 179     fprintf (stderr, "Forwarding inter-generational pointers.\n");
 180   updateCrossMap (s);
 181   /* Constants. */
 182   cardMap = s->generationalMaps.cardMap;
 183   crossMap = s->generationalMaps.crossMap;
 184   maxCardIndex = sizeToCardMapIndex (align (s->heap.oldGenSize, CARD_SIZE));
 185   oldGenStart = s->heap.start;
 186   oldGenEnd = oldGenStart + s->heap.oldGenSize;
 187   /* Loop variables*/
 188   objectStart = alignFrontier (s, s->heap.start);
 189   cardIndex = 0;
 190   cardStart = oldGenStart;
 191 checkAll:
 192   assert (cardIndex <= maxCardIndex);
 193   assert (isFrontierAligned (s, objectStart));
 194   if (cardIndex == maxCardIndex)
 195     goto done;
 196 checkCard:
 197   if (DEBUG_GENERATIONAL)
 198     fprintf (stderr, "checking card %"PRIuMAX"  objectStart = "FMTPTR"\n",
 199              (uintmax_t)cardIndex, (uintptr_t)objectStart);
 200   assert (objectStart < oldGenStart + cardMapIndexToSize (cardIndex + 1));
 201   if (cardMap[cardIndex]) {
 202     pointer lastObject;
 203
 204     s->cumulativeStatistics.numCardsMarked++;
 205     if (DEBUG_GENERATIONAL)
 206       fprintf (stderr, "card %"PRIuMAX" is marked  objectStart = "FMTPTR"\n",
 207                (uintmax_t)cardIndex, (uintptr_t)objectStart);
 208     assert (isFrontierAligned (s, objectStart));
 209     cardEnd = cardStart + CARD_SIZE;
 210     if (oldGenEnd < cardEnd)
 211       cardEnd = oldGenEnd;
 212     assert (objectStart < cardEnd);
 213     lastObject = objectStart;
 214     /* If we ever add Weak.set, then there could be intergenerational
 215      * weak pointers, in which case we would need to link the weak
 216      * objects into s->weaks.  But for now, since there is no
 217      * Weak.set, the foreachObjptrInRange will do the right thing on
 218      * weaks, since the weak pointer will never be into the nursery.
 219      */
 220     objectStart = foreachObjptrInRange (s, objectStart, &cardEnd,
 221                                         forwardObjptrIfInNursery, FALSE);
 222     s->cumulativeStatistics.bytesScannedMinor += (uintmax_t)(objectStart - lastObject);
 223     if (objectStart == oldGenEnd)
 224       goto done;
 225     cardIndex = sizeToCardMapIndex ((size_t)(objectStart - oldGenStart));
 226     cardStart = oldGenStart + cardMapIndexToSize (cardIndex);
 227     goto checkCard;
 228   } else {
 229     unless (CROSS_MAP_EMPTY == crossMap[cardIndex])
 230       objectStart = cardStart + (size_t)(crossMap[cardIndex] * CROSS_MAP_OFFSET_SCALE);
 231     if (DEBUG_GENERATIONAL)
 232       fprintf (stderr,
 233                "card %"PRIuMAX" is not marked"
 234                "  crossMap[%"PRIuMAX"] == %"PRIuMAX""
 235                "  objectStart = "FMTPTR"\n",
 236                (uintmax_t)cardIndex, (uintmax_t)cardIndex,
 237                (uintmax_t)(crossMap[cardIndex] * CROSS_MAP_OFFSET_SCALE),
 238                (uintptr_t)objectStart);
 239     cardIndex++;
 240     cardStart += CARD_SIZE;
 241     goto checkAll;
 242   }
 243   assert (FALSE);
 244 done:
 245   if (DEBUG_GENERATIONAL)
 246     fprintf (stderr, "Forwarding inter-generational pointers done.\n");
 247 }