runtime/gc/dfs-mark.c

   1 /* Copyright (C) 2012,2016 Matthew Fluet.
   2  * Copyright (C) 1999-2007 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 /*                       Depth-first Marking                        */
  12 /* ---------------------------------------------------------------- */
  13
  14 bool isPointerMarked (pointer p) {
  15   return MARK_MASK & getHeader (p);
  16 }
  17
  18 bool isPointerMarkedByMode (pointer p, GC_markMode m) {
  19   switch (m) {
  20   case MARK_MODE:
  21     return isPointerMarked (p);
  22   case UNMARK_MODE:
  23     return not isPointerMarked (p);
  24   default:
  25     die ("bad mark mode %u", m);
  26   }
  27 }
  28
  29 /* dfsMarkByMode (s, r, m, shc, slw)
  30  *
  31  * Sets all the mark bits in the object graph pointed to by r.
  32  *
  33  * If m is MARK_MODE, it sets the bits to 1.
  34  * If m is UNMARK_MODE, it sets the bits to 0.
  35  *
  36  * If shc, it hash-conses the objects marked.
  37  *
  38  * If slw, it links the weak objects marked.
  39  *
  40  * It returns the total size in bytes of the objects marked.
  41  */
  42 size_t dfsMarkByMode (GC_state s, pointer root,
  43                       GC_markMode mode,
  44                       bool shouldHashCons,
  45                       bool shouldLinkWeaks) {
  46   GC_header mark; /* Used to set or clear the mark bit. */
  47   size_t size; /* Total number of bytes marked. */
  48   pointer cur; /* The current object being marked. */
  49   pointer prev; /* The previous object on the mark stack. */
  50   pointer next; /* The next object to mark. */
  51   pointer todo; /* A pointer to the pointer in cur to next. */
  52   GC_header header;
  53   GC_header* headerp;
  54   uint16_t bytesNonObjptrs;
  55   uint16_t numObjptrs;
  56   GC_objectTypeTag tag;
  57   uint32_t objptrIndex; /* The i'th pointer in the object (element) being marked. */
  58   GC_header nextHeader;
  59   GC_header* nextHeaderp;
  60   GC_arrayCounter arrayIndex;
  61   pointer top; /* The top of the next stack frame to mark. */
  62   GC_returnAddress returnAddress;
  63   GC_frameLayout frameLayout;
  64   GC_frameOffsets frameOffsets;
  65
  66   if (isPointerMarkedByMode (root, mode))
  67     /* Object has already been marked. */
  68     return 0;
  69   mark = (MARK_MODE == mode) ? MARK_MASK : 0;
  70   size = 0;
  71   cur = root;
  72   prev = NULL;
  73   headerp = getHeaderp (cur);
  74   header = *headerp;
  75   goto mark;
  76 markNext:
  77   /* cur is the object that was being marked.
  78    * prev is the mark stack.
  79    * next is the unmarked object to be marked.
  80    * nextHeaderp points to the header of next.
  81    * nextHeader is the header of next.
  82    * todo is a pointer to the pointer inside cur that points to next.
  83    */
  84   if (DEBUG_DFS_MARK)
  85     fprintf (stderr,
  86              "markNext"
  87              "  cur = "FMTPTR"  next = "FMTPTR
  88              "  prev = "FMTPTR"  todo = "FMTPTR"\n",
  89              (uintptr_t)cur, (uintptr_t)next,
  90              (uintptr_t)prev, (uintptr_t)todo);
  91   assert (not isPointerMarkedByMode (next, mode));
  92   assert (nextHeaderp == getHeaderp (next));
  93   assert (nextHeader == getHeader (next));
  94   // assert (*(pointer*) todo == next);
  95   assert (fetchObjptrToPointer (todo, s->heap.start) == next);
  96   headerp = nextHeaderp;
  97   header = nextHeader;
  98   // *(pointer*)todo = prev;
  99   storeObjptrFromPointer (todo, prev, s->heap.start);
 100   prev = cur;
 101   cur = next;
 102 mark:
 103   if (DEBUG_DFS_MARK)
 104     fprintf (stderr, "mark  cur = "FMTPTR"  prev = "FMTPTR"  mode = %s\n",
 105              (uintptr_t)cur, (uintptr_t)prev,
 106              (mode == MARK_MODE) ? "mark" : "unmark");
 107   /* cur is the object to mark.
 108    * prev is the mark stack.
 109    * headerp points to the header of cur.
 110    * header is the header of cur.
 111    */
 112   assert (not isPointerMarkedByMode (cur, mode));
 113   assert (header == getHeader (cur));
 114   assert (headerp == getHeaderp (cur));
 115   header ^= MARK_MASK;
 116   /* Store the mark.  In the case of an object that contains a pointer to
 117    * itself, it is essential that we store the marked header before marking
 118    * the internal pointers (markInNormal below).  If we didn't, then we
 119    * would see the object as unmarked and traverse it again.
 120    */
 121   *headerp = header;
 122   splitHeader (s, header, &tag, NULL, &bytesNonObjptrs, &numObjptrs);
 123   if (NORMAL_TAG == tag) {
 124     size +=
 125       GC_NORMAL_METADATA_SIZE
 126       + bytesNonObjptrs
 127       + (numObjptrs * OBJPTR_SIZE);
 128     if (0 == numObjptrs) {
 129       /* There is nothing to mark. */
 130 normalDone:
 131       if (shouldHashCons)
 132         cur = hashConsPointer (s, cur, TRUE);
 133       goto ret;
 134     }
 135     todo = cur + bytesNonObjptrs;
 136     objptrIndex = 0;
 137 markInNormal:
 138     if (DEBUG_DFS_MARK)
 139       fprintf (stderr, "markInNormal  objptrIndex = %"PRIu32"\n", objptrIndex);
 140     assert (objptrIndex < numObjptrs);
 141     // next = *(pointer*)todo;
 142     next = fetchObjptrToPointer (todo, s->heap.start);
 143     if (not isPointer (next)) {
 144 markNextInNormal:
 145       assert (objptrIndex < numObjptrs);
 146       objptrIndex++;
 147       if (objptrIndex == numObjptrs) {
 148         /* Done.  Clear out the counters and return. */
 149         *headerp = header & ~COUNTER_MASK;
 150         goto normalDone;
 151       }
 152       todo += OBJPTR_SIZE;
 153       goto markInNormal;
 154     }
 155     nextHeaderp = getHeaderp (next);
 156     nextHeader = *nextHeaderp;
 157     if (mark == (nextHeader & MARK_MASK)) {
 158       if (shouldHashCons)
 159         shareObjptr (s, (objptr*)todo);
 160       goto markNextInNormal;
 161     }
 162     *headerp = (header & ~COUNTER_MASK) | (objptrIndex << COUNTER_SHIFT);
 163     goto markNext;
 164   } else if (WEAK_TAG == tag) {
 165     /* Store the marked header and don't follow any pointers. */
 166     if (shouldLinkWeaks) {
 167       GC_weak w;
 168
 169       w = (GC_weak)(cur + offsetofWeak (s));
 170       if (DEBUG_WEAK)
 171         fprintf (stderr, "marking weak "FMTPTR" ",
 172                  (uintptr_t)w);
 173       if (isObjptr (w->objptr)) {
 174         if (DEBUG_WEAK)
 175           fprintf (stderr, "linking\n");
 176         w->link = s->weaks;
 177         s->weaks = w;
 178       } else {
 179         if (DEBUG_WEAK)
 180           fprintf (stderr, "not linking\n");
 181       }
 182     }
 183     goto ret;
 184   } else if (ARRAY_TAG == tag) {
 185     /* When marking arrays:
 186      *   arrayIndex is the index of the element to mark.
 187      *   cur is the pointer to the array.
 188      *   objptrIndex is the index of the pointer within the element
 189      *     (i.e. the i'th pointer is at index i).
 190      *   todo is the start of the element.
 191      */
 192     size +=
 193       GC_ARRAY_METADATA_SIZE
 194       + sizeofArrayNoMetaData (s, getArrayLength (cur), bytesNonObjptrs, numObjptrs);
 195     if (0 == numObjptrs or 0 == getArrayLength (cur)) {
 196       /* There is nothing to mark. */
 197 arrayDone:
 198       if (shouldHashCons)
 199         cur = hashConsPointer (s, cur, TRUE);
 200       goto ret;
 201     }
 202     /* Begin marking first element. */
 203     arrayIndex = 0;
 204     todo = cur;
 205 markArrayElt:
 206     assert (arrayIndex < getArrayLength (cur));
 207     objptrIndex = 0;
 208     /* Skip to the first pointer. */
 209     todo += bytesNonObjptrs;
 210 markInArray:
 211     if (DEBUG_DFS_MARK)
 212       fprintf (stderr, "markInArray arrayIndex = %"PRIxARRCTR" objptrIndex = %"PRIu32"\n",
 213                arrayIndex, objptrIndex);
 214     assert (arrayIndex < getArrayLength (cur));
 215     assert (objptrIndex < numObjptrs);
 216     assert (todo == indexArrayAtObjptrIndex (s, cur, arrayIndex, objptrIndex));
 217     // next = *(pointer*)todo;
 218     next = fetchObjptrToPointer (todo, s->heap.start);
 219     if (not (isPointer(next))) {
 220 markNextInArray:
 221       assert (arrayIndex < getArrayLength (cur));
 222       assert (objptrIndex < numObjptrs);
 223       assert (todo == indexArrayAtObjptrIndex (s, cur, arrayIndex, objptrIndex));
 224       todo += OBJPTR_SIZE;
 225       objptrIndex++;
 226       if (objptrIndex < numObjptrs)
 227         goto markInArray;
 228       arrayIndex++;
 229       if (arrayIndex < getArrayLength (cur))
 230         goto markArrayElt;
 231       /* Done.  Clear out the counters and return. */
 232       *getArrayCounterp (cur) = 0;
 233       *headerp = header & ~COUNTER_MASK;
 234       goto arrayDone;
 235     }
 236     nextHeaderp = getHeaderp (next);
 237     nextHeader = *nextHeaderp;
 238     if (mark == (nextHeader & MARK_MASK)) {
 239       if (shouldHashCons)
 240         shareObjptr (s, (objptr*)todo);
 241       goto markNextInArray;
 242     }
 243     /* Recur and mark next. */
 244     *getArrayCounterp (cur) = arrayIndex;
 245     *headerp = (header & ~COUNTER_MASK) | (objptrIndex << COUNTER_SHIFT);
 246     goto markNext;
 247   } else {
 248     assert (STACK_TAG == tag);
 249     size +=
 250       GC_STACK_METADATA_SIZE
 251       + sizeof (struct GC_stack) + ((GC_stack)cur)->reserved;
 252     top = getStackTop (s, (GC_stack)cur);
 253     assert (((GC_stack)cur)->used <= ((GC_stack)cur)->reserved);
 254 markInStack:
 255     /* Invariant: top points just past the return address of the frame
 256      * to be marked.
 257      */
 258     assert (getStackBottom (s, (GC_stack)cur) <= top);
 259     if (DEBUG_DFS_MARK)
 260       fprintf (stderr, "markInStack  top = %"PRIuMAX"\n",
 261                (uintmax_t)(top - getStackBottom (s, (GC_stack)cur)));
 262     if (top == getStackBottom (s, (GC_stack)(cur)))
 263       goto ret;
 264     objptrIndex = 0;
 265     returnAddress = *(GC_returnAddress*) (top - GC_RETURNADDRESS_SIZE);
 266     frameLayout = getFrameLayoutFromReturnAddress (s, returnAddress);
 267     frameOffsets = frameLayout->offsets;
 268     ((GC_stack)cur)->markTop = top;
 269 markInFrame:
 270     if (objptrIndex == frameOffsets [0]) {
 271       top -= frameLayout->size;
 272       goto markInStack;
 273     }
 274     todo = top - frameLayout->size + frameOffsets [objptrIndex + 1];
 275     // next = *(pointer*)todo;
 276     next = fetchObjptrToPointer (todo, s->heap.start);
 277     if (DEBUG_DFS_MARK)
 278       fprintf (stderr,
 279                "    offset %u  todo "FMTPTR"  next = "FMTPTR"\n",
 280                frameOffsets [objptrIndex + 1],
 281                (uintptr_t)todo, (uintptr_t)next);
 282     if (not isPointer (next)) {
 283       objptrIndex++;
 284       goto markInFrame;
 285     }
 286     nextHeaderp = getHeaderp (next);
 287     nextHeader = *nextHeaderp;
 288     if (mark == (nextHeader & MARK_MASK)) {
 289       objptrIndex++;
 290       if (shouldHashCons)
 291         shareObjptr (s, (objptr*)todo);
 292       goto markInFrame;
 293     }
 294     ((GC_stack)cur)->markIndex = objptrIndex;
 295     goto markNext;
 296   }
 297   assert (FALSE);
 298 ret:
 299   /* Done marking cur, continue with prev.
 300    * Need to set the pointer in the prev object that pointed to cur
 301    * to point back to prev, and restore prev.
 302    */
 303   if (DEBUG_DFS_MARK)
 304     fprintf (stderr, "return  cur = "FMTPTR"  prev = "FMTPTR"\n",
 305              (uintptr_t)cur, (uintptr_t)prev);
 306   assert (isPointerMarkedByMode (cur, mode));
 307   if (NULL == prev)
 308     return size;
 309   next = cur;
 310   cur = prev;
 311   headerp = getHeaderp (cur);
 312   header = *headerp;
 313   splitHeader (s, header, &tag, NULL, &bytesNonObjptrs, &numObjptrs);
 314   /* It's impossible to get a WEAK_TAG here, since we would never
 315    * follow the weak object pointer.
 316    */
 317   assert (WEAK_TAG != tag);
 318   if (NORMAL_TAG == tag) {
 319     todo = cur + bytesNonObjptrs;
 320     objptrIndex = (header & COUNTER_MASK) >> COUNTER_SHIFT;
 321     todo += objptrIndex * OBJPTR_SIZE;
 322     // prev = *(pointer*)todo;
 323     prev = fetchObjptrToPointer (todo, s->heap.start);
 324     // *(pointer*)todo = next;
 325     storeObjptrFromPointer (todo, next, s->heap.start);
 326     if (shouldHashCons)
 327       markIntergenerationalPointer (s, (pointer*)todo);
 328     goto markNextInNormal;
 329   } else if (ARRAY_TAG == tag) {
 330     arrayIndex = getArrayCounter (cur);
 331     todo = cur + arrayIndex * (bytesNonObjptrs + (numObjptrs * OBJPTR_SIZE));
 332     objptrIndex = (header & COUNTER_MASK) >> COUNTER_SHIFT;
 333     todo += bytesNonObjptrs + objptrIndex * OBJPTR_SIZE;
 334     // prev = *(pointer*)todo;
 335     prev = fetchObjptrToPointer (todo, s->heap.start);
 336     // *(pointer*)todo = next;
 337     storeObjptrFromPointer (todo, next, s->heap.start);
 338     if (shouldHashCons)
 339       markIntergenerationalPointer (s, (pointer*)todo);
 340     goto markNextInArray;
 341   } else {
 342     assert (STACK_TAG == tag);
 343     objptrIndex = ((GC_stack)cur)->markIndex;
 344     top = ((GC_stack)cur)->markTop;
 345     /* Invariant: top points just past a "return address". */
 346     returnAddress = *(GC_returnAddress*) (top - GC_RETURNADDRESS_SIZE);
 347     frameLayout = getFrameLayoutFromReturnAddress (s, returnAddress);
 348     frameOffsets = frameLayout->offsets;
 349     todo = top - frameLayout->size + frameOffsets [objptrIndex + 1];
 350     // prev = *(pointer*)todo;
 351     prev = fetchObjptrToPointer (todo, s->heap.start);
 352     // *(pointer*)todo = next;
 353     storeObjptrFromPointer (todo, next, s->heap.start);
 354     if (shouldHashCons)
 355       markIntergenerationalPointer (s, (pointer*)todo);
 356     objptrIndex++;
 357     goto markInFrame;
 358   }
 359   assert (FALSE);
 360 }
 361
 362 void dfsMarkWithHashConsWithLinkWeaks (GC_state s, objptr *opp) {
 363   pointer p;
 364
 365   p = objptrToPointer (*opp, s->heap.start);
 366   dfsMarkByMode (s, p, MARK_MODE, TRUE, TRUE);
 367 }
 368
 369 void dfsMarkWithoutHashConsWithLinkWeaks (GC_state s, objptr *opp) {
 370   pointer p;
 371
 372   p = objptrToPointer (*opp, s->heap.start);
 373   dfsMarkByMode (s, p, MARK_MODE, FALSE, TRUE);
 374 }