runtime/gc/mark-compact.c

   1 /* Copyright (C) 2010,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 /* ---------------------------------------------------------------- */
  11 /*                 Jonkers Mark-compact Collection                  */
  12 /* ---------------------------------------------------------------- */
  13
  14 void copyForThreadInternal (pointer dst, pointer src) {
  15   if (FALSE)
  16     fprintf (stderr,
  17              "copyForThreadInternal dst = "FMTPTR"  src = "FMTPTR"\n",
  18              (uintptr_t)dst, (uintptr_t)src);
  19   if (OBJPTR_SIZE > GC_HEADER_SIZE) {
  20     size_t count;
  21
  22     assert (0 == (OBJPTR_SIZE % GC_HEADER_SIZE));
  23     count = (OBJPTR_SIZE - GC_HEADER_SIZE) / GC_HEADER_SIZE;
  24     src = src + GC_HEADER_SIZE * count;
  25
  26     for (size_t i = 0; i <= count; i++) {
  27       *((GC_header*)dst) = *((GC_header*)src);
  28       dst += GC_HEADER_SIZE;
  29       src -= GC_HEADER_SIZE;
  30     }
  31   } else if (GC_HEADER_SIZE > OBJPTR_SIZE) {
  32     size_t count;
  33
  34     assert (0 == (GC_HEADER_SIZE % OBJPTR_SIZE));
  35     count = (GC_HEADER_SIZE - OBJPTR_SIZE) / OBJPTR_SIZE;
  36     dst = dst + OBJPTR_SIZE * count;
  37
  38     for (size_t i = 0; i <= count; i++) {
  39       *((objptr*)dst) = *((objptr*)src);
  40       dst -= OBJPTR_SIZE;
  41       src += OBJPTR_SIZE;
  42     }
  43   } else /* (GC_HEADER_SIZE == OBJPTR_SIZE) */ {
  44     *((GC_header*)dst) = *((GC_header*)src);
  45   }
  46 }
  47
  48 void threadInternalObjptr (GC_state s, objptr *opp) {
  49   objptr opop;
  50   pointer p;
  51   GC_header *headerp;
  52
  53   opop = pointerToObjptr ((pointer)opp, s->heap.start);
  54   p = objptrToPointer (*opp, s->heap.start);
  55   if (FALSE)
  56     fprintf (stderr,
  57              "threadInternal opp = "FMTPTR"  p = "FMTPTR"  header = "FMTHDR"\n",
  58              (uintptr_t)opp, (uintptr_t)p, getHeader (p));
  59   headerp = getHeaderp (p);
  60   copyForThreadInternal ((pointer)(opp), (pointer)(headerp));
  61   copyForThreadInternal ((pointer)(headerp), (pointer)(&opop));
  62 }
  63
  64 /* If the object pointer is valid, and points to an unmarked object,
  65  * then clear the object pointer.
  66  */
  67 void updateWeaksForMarkCompact (GC_state s) {
  68   pointer p;
  69   GC_weak w;
  70
  71   for (w = s->weaks; w != NULL; w = w->link) {
  72     assert (BOGUS_OBJPTR != w->objptr);
  73
  74     if (DEBUG_WEAK)
  75       fprintf (stderr, "updateWeaksForMarkCompact  w = "FMTPTR"  ", (uintptr_t)w);
  76     p = objptrToPointer(w->objptr, s->heap.start);
  77     /* If it's unmarked, clear the weak pointer. */
  78     if (isPointerMarked(p)) {
  79       if (DEBUG_WEAK)
  80         fprintf (stderr, "not cleared\n");
  81     } else {
  82       if (DEBUG_WEAK)
  83         fprintf (stderr, "cleared\n");
  84       *(getHeaderp((pointer)w - offsetofWeak (s))) = GC_WEAK_GONE_HEADER | MARK_MASK;
  85       w->objptr = BOGUS_OBJPTR;
  86     }
  87   }
  88   s->weaks = NULL;
  89 }
  90
  91 void updateForwardPointersForMarkCompact (GC_state s, GC_stack currentStack) {
  92   pointer back;
  93   pointer endOfLastMarked;
  94   pointer front;
  95   size_t gap;
  96   GC_header header;
  97   GC_header *headerp;
  98   pointer p;
  99   size_t size, skipFront, skipGap;
 100
 101   if (DEBUG_MARK_COMPACT)
 102     fprintf (stderr, "Update forward pointers.\n");
 103   front = alignFrontier (s, s->heap.start);
 104   back = s->heap.start + s->heap.oldGenSize;
 105   gap = 0;
 106   endOfLastMarked = front;
 107 updateObject:
 108   if (DEBUG_MARK_COMPACT)
 109     fprintf (stderr, "updateObject  front = "FMTPTR"  back = "FMTPTR"\n",
 110              (uintptr_t)front, (uintptr_t)back);
 111   if (front == back)
 112     goto done;
 113   p = advanceToObjectData (s, front);
 114   headerp = getHeaderp (p);
 115   header = *headerp;
 116   if (GC_VALID_HEADER_MASK & header) {
 117     /* It's a header */
 118     if (MARK_MASK & header) {
 119       /* It is marked, but has no forward pointers.
 120        * Thread internal pointers.
 121        */
 122 thread:
 123       assert (GC_VALID_HEADER_MASK & header);
 124       assert (MARK_MASK & header);
 125
 126       size_t metaDataBytes, objectBytes;
 127       GC_objectTypeTag tag;
 128       uint16_t bytesNonObjptrs, numObjptrs;
 129
 130       assert (header == getHeader (p));
 131       splitHeader(s, header, &tag, NULL, &bytesNonObjptrs, &numObjptrs);
 132
 133       /* Compute the space taken by the header and object body. */
 134       if ((NORMAL_TAG == tag) or (WEAK_TAG == tag)) { /* Fixed size object. */
 135         metaDataBytes = GC_NORMAL_METADATA_SIZE;
 136         objectBytes = bytesNonObjptrs + (numObjptrs * OBJPTR_SIZE);
 137         skipFront = 0;
 138         skipGap = 0;
 139       } else if (ARRAY_TAG == tag) {
 140         metaDataBytes = GC_ARRAY_METADATA_SIZE;
 141         objectBytes = sizeofArrayNoMetaData (s, getArrayLength (p),
 142                                              bytesNonObjptrs, numObjptrs);
 143         skipFront = 0;
 144         skipGap = 0;
 145       } else { /* Stack. */
 146         bool current;
 147         size_t reservedNew, reservedOld;
 148         GC_stack stack;
 149
 150         assert (STACK_TAG == tag);
 151         metaDataBytes = GC_STACK_METADATA_SIZE;
 152         stack = (GC_stack)p;
 153         current = currentStack == stack;
 154
 155         reservedOld = stack->reserved;
 156         reservedNew = sizeofStackShrinkReserved (s, stack, current);
 157         objectBytes = sizeof (struct GC_stack) + stack->used;
 158         skipFront = reservedOld - stack->used;
 159         skipGap = reservedOld - reservedNew;
 160       }
 161       size = metaDataBytes + objectBytes;
 162       if (DEBUG_MARK_COMPACT)
 163         fprintf (stderr, "threading "FMTPTR" of size %"PRIuMAX"\n",
 164                  (uintptr_t)p, (uintmax_t)size);
 165       if ((size_t)(front - endOfLastMarked) >= GC_ARRAY_METADATA_SIZE) {
 166         pointer newArray = endOfLastMarked;
 167         /* Compress all of the unmarked into one vector.  We require
 168          * GC_ARRAY_METADATA_SIZE space to be available because that is
 169          * the smallest possible array.
 170          */
 171         if (DEBUG_MARK_COMPACT)
 172           fprintf (stderr, "compressing from "FMTPTR" to "FMTPTR" (length = %"PRIuMAX")\n",
 173                    (uintptr_t)endOfLastMarked, (uintptr_t)front,
 174                    (uintmax_t)(front - endOfLastMarked));
 175         *((GC_arrayCounter*)(newArray)) = 0;
 176         newArray += GC_ARRAY_COUNTER_SIZE;
 177         *((GC_arrayLength*)(newArray)) =
 178           ((size_t)(front - endOfLastMarked)) - GC_ARRAY_METADATA_SIZE;
 179         newArray += GC_ARRAY_LENGTH_SIZE;
 180         *((GC_header*)(newArray)) = GC_WORD8_VECTOR_HEADER;
 181       }
 182       gap += skipGap;
 183       front += size + skipFront;
 184       endOfLastMarked = front;
 185       foreachObjptrInObject (s, p, threadInternalObjptr, FALSE);
 186       goto updateObject;
 187     } else {
 188       /* It's not marked. */
 189       size = sizeofObject (s, p);
 190       gap += size;
 191       front += size;
 192       goto updateObject;
 193     }
 194   } else {
 195     pointer new;
 196     objptr newObjptr;
 197
 198     assert (not (GC_VALID_HEADER_MASK & header));
 199     /* It's a pointer.  This object must be live.  Fix all the forward
 200      * pointers to it, store its header, then thread its internal
 201      * pointers.
 202      */
 203     new = p - gap;
 204     newObjptr = pointerToObjptr (new, s->heap.start);
 205     do {
 206       pointer cur;
 207       objptr curObjptr;
 208
 209       copyForThreadInternal ((pointer)(&curObjptr), (pointer)headerp);
 210       cur = objptrToPointer (curObjptr, s->heap.start);
 211
 212       copyForThreadInternal ((pointer)headerp, cur);
 213       *((objptr*)cur) = newObjptr;
 214
 215       header = *headerp;
 216     } while (0 == (1 & header));
 217     goto thread;
 218   }
 219   assert (FALSE);
 220 done:
 221   return;
 222 }
 223
 224 void updateBackwardPointersAndSlideForMarkCompact (GC_state s, GC_stack currentStack) {
 225   pointer back;
 226   pointer front;
 227   size_t gap;
 228   GC_header header;
 229   GC_header *headerp;
 230   pointer p;
 231   size_t size, skipFront, skipGap;
 232
 233   if (DEBUG_MARK_COMPACT)
 234     fprintf (stderr, "Update backward pointers and slide.\n");
 235   front = alignFrontier (s, s->heap.start);
 236   back = s->heap.start + s->heap.oldGenSize;
 237   gap = 0;
 238 updateObject:
 239   if (DEBUG_MARK_COMPACT)
 240     fprintf (stderr, "updateObject  front = "FMTPTR"  back = "FMTPTR"\n",
 241              (uintptr_t)front, (uintptr_t)back);
 242   if (front == back)
 243     goto done;
 244   p = advanceToObjectData (s, front);
 245   headerp = getHeaderp (p);
 246   header = *headerp;
 247   if (GC_VALID_HEADER_MASK & header) {
 248     /* It's a header */
 249     if (MARK_MASK & header) {
 250       /* It is marked, but has no backward pointers to it.
 251        * Unmark it.
 252        */
 253 unmark:
 254       assert (GC_VALID_HEADER_MASK & header);
 255       assert (MARK_MASK & header);
 256
 257       size_t metaDataBytes, objectBytes;
 258       GC_objectTypeTag tag;
 259       uint16_t bytesNonObjptrs, numObjptrs;
 260
 261       assert (header == getHeader (p));
 262       splitHeader(s, header, &tag, NULL, &bytesNonObjptrs, &numObjptrs);
 263
 264       /* Compute the space taken by the header and object body. */
 265       if ((NORMAL_TAG == tag) or (WEAK_TAG == tag)) { /* Fixed size object. */
 266         metaDataBytes = GC_NORMAL_METADATA_SIZE;
 267         objectBytes = bytesNonObjptrs + (numObjptrs * OBJPTR_SIZE);
 268         skipFront = 0;
 269         skipGap = 0;
 270       } else if (ARRAY_TAG == tag) {
 271         metaDataBytes = GC_ARRAY_METADATA_SIZE;
 272         objectBytes = sizeofArrayNoMetaData (s, getArrayLength (p),
 273                                              bytesNonObjptrs, numObjptrs);
 274         skipFront = 0;
 275         skipGap = 0;
 276       } else { /* Stack. */
 277         bool current;
 278         size_t reservedNew, reservedOld;
 279         GC_stack stack;
 280
 281         assert (STACK_TAG == tag);
 282         metaDataBytes = GC_STACK_METADATA_SIZE;
 283         stack = (GC_stack)p;
 284         current = currentStack == stack;
 285
 286         reservedOld = stack->reserved;
 287         reservedNew = sizeofStackShrinkReserved (s, stack, current);
 288         if (reservedNew < stack->reserved) {
 289           if (DEBUG_STACKS or s->controls.messages)
 290             fprintf (stderr,
 291                      "[GC: Shrinking stack of size %s bytes to size %s bytes, using %s bytes.]\n",
 292                      uintmaxToCommaString(stack->reserved),
 293                      uintmaxToCommaString(reservedNew),
 294                      uintmaxToCommaString(stack->used));
 295           stack->reserved = reservedNew;
 296         }
 297         objectBytes = sizeof (struct GC_stack) + stack->used;
 298         skipFront = reservedOld - stack->used;
 299         skipGap = reservedOld - reservedNew;
 300       }
 301       size = metaDataBytes + objectBytes;
 302       /* unmark */
 303       if (DEBUG_MARK_COMPACT)
 304         fprintf (stderr, "unmarking "FMTPTR" of size %"PRIuMAX"\n",
 305                  (uintptr_t)p, (uintmax_t)size);
 306       *headerp = header & ~MARK_MASK;
 307       /* slide */
 308       if (DEBUG_MARK_COMPACT)
 309         fprintf (stderr, "sliding "FMTPTR" down %"PRIuMAX" to "FMTPTR"\n",
 310                  (uintptr_t)front, (uintmax_t)gap, (uintptr_t)(front - gap));
 311       GC_memmove (front, front - gap, size);
 312       gap += skipGap;
 313       front += size + skipFront;
 314       goto updateObject;
 315     } else {
 316       /* It's not marked. */
 317       size = sizeofObject (s, p);
 318       if (DEBUG_MARK_COMPACT)
 319         fprintf (stderr, "skipping "FMTPTR" of size %"PRIuMAX"\n",
 320                  (uintptr_t)p, (uintmax_t)size);
 321       gap += size;
 322       front += size;
 323       goto updateObject;
 324     }
 325   } else {
 326     pointer new;
 327     objptr newObjptr;
 328
 329     assert (not (GC_VALID_HEADER_MASK & header));
 330     /* It's a pointer.  This object must be live.  Fix all the
 331      * backward pointers to it.  Then unmark it.
 332      */
 333     new = p - gap;
 334     newObjptr = pointerToObjptr (new, s->heap.start);
 335     do {
 336       pointer cur;
 337       objptr curObjptr;
 338
 339       copyForThreadInternal ((pointer)(&curObjptr), (pointer)headerp);
 340       cur = objptrToPointer (curObjptr, s->heap.start);
 341
 342       copyForThreadInternal ((pointer)headerp, cur);
 343       *((objptr*)cur) = newObjptr;
 344
 345       header = *headerp;
 346     } while (0 == (1 & header));
 347     /* The unmarked header will be stored by unmark. */
 348     goto unmark;
 349   }
 350   assert (FALSE);
 351 done:
 352   s->heap.oldGenSize = (size_t)((front - gap) - s->heap.start);
 353   if (DEBUG_MARK_COMPACT)
 354     fprintf (stderr, "oldGenSize = %"PRIuMAX"\n",
 355              (uintmax_t)s->heap.oldGenSize);
 356   return;
 357 }
 358
 359 void majorMarkCompactGC (GC_state s) {
 360   size_t bytesHashConsed;
 361   size_t bytesMarkCompacted;
 362   GC_stack currentStack;
 363   struct rusage ru_start;
 364
 365   if (detailedGCTime (s))
 366     startTiming (&ru_start);
 367   s->cumulativeStatistics.numMarkCompactGCs++;
 368   if (DEBUG or s->controls.messages) {
 369     fprintf (stderr,
 370              "[GC: Starting major mark-compact;]\n");
 371     fprintf (stderr,
 372              "[GC:\theap at "FMTPTR" of size %s bytes.]\n",
 373              (uintptr_t)(s->heap.start),
 374              uintmaxToCommaString(s->heap.size));
 375   }
 376   currentStack = getStackCurrent (s);
 377   if (s->hashConsDuringGC) {
 378     s->lastMajorStatistics.bytesHashConsed = 0;
 379     s->cumulativeStatistics.numHashConsGCs++;
 380     s->objectHashTable = allocHashTable (s);
 381     foreachGlobalObjptr (s, dfsMarkWithHashConsWithLinkWeaks);
 382     freeHashTable (s->objectHashTable);
 383   } else {
 384     foreachGlobalObjptr (s, dfsMarkWithoutHashConsWithLinkWeaks);
 385   }
 386   updateWeaksForMarkCompact (s);
 387   foreachGlobalObjptr (s, threadInternalObjptr);
 388   updateForwardPointersForMarkCompact (s, currentStack);
 389   updateBackwardPointersAndSlideForMarkCompact (s, currentStack);
 390   bytesHashConsed = s->lastMajorStatistics.bytesHashConsed;
 391   s->cumulativeStatistics.bytesHashConsed += bytesHashConsed;
 392   bytesMarkCompacted = s->heap.oldGenSize;
 393   s->cumulativeStatistics.bytesMarkCompacted += bytesMarkCompacted;
 394   s->lastMajorStatistics.kind = GC_MARK_COMPACT;
 395   if (detailedGCTime (s))
 396     stopTiming (&ru_start, &s->cumulativeStatistics.ru_gcMarkCompact);
 397   if (DEBUG or s->controls.messages) {
 398     fprintf (stderr,
 399              "[GC: Finished major mark-compact; mark compacted %s bytes.]\n",
 400              uintmaxToCommaString(bytesMarkCompacted));
 401     if (s->hashConsDuringGC)
 402       printBytesHashConsedMessage(bytesHashConsed,
 403                                   bytesHashConsed + bytesMarkCompacted);
 404   }
 405 }