runtime/gc/generational.c

   1 /* Copyright (C) 2009,2012 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 void displayGenerationalMaps (__attribute__ ((unused)) GC_state s,
  11                               struct GC_generationalMaps *generational,
  12                               FILE *stream) {
  13   fprintf(stream,
  14           "\t\tcardMap = "FMTPTR"\n"
  15           "\t\tcardMapAbsolute = "FMTPTR"\n"
  16           "\t\tcardMapLength = %"PRIuMAX"\n"
  17           "\t\tcrossMap = "FMTPTR"\n"
  18           "\t\tcrossMapLength = %"PRIuMAX"\n"
  19           "\t\tcrossMapValidSize = %"PRIuMAX"\n",
  20           (uintptr_t)generational->cardMap,
  21           (uintptr_t)generational->cardMapAbsolute,
  22           (uintmax_t)generational->cardMapLength,
  23           (uintptr_t)generational->crossMap,
  24           (uintmax_t)generational->crossMapLength,
  25           (uintmax_t)generational->crossMapValidSize);
  26   if (DEBUG_GENERATIONAL and DEBUG_DETAILED) {
  27     GC_crossMapIndex i;
  28
  29     fprintf (stderr, "crossMap trues\n");
  30     for (i = 0; i < generational->crossMapLength; i++)
  31       unless (CROSS_MAP_EMPTY == generational->crossMap[i])
  32         fprintf (stderr, "\t%"PRIuMAX"  "FMTCME"  %"PRIuMAX"\n",
  33                  (uintmax_t)i, generational->crossMap[i],
  34                  (uintmax_t)(CROSS_MAP_OFFSET_SCALE * generational->crossMap[i]));
  35     fprintf (stderr, "\n");
  36   }
  37 }
  38
  39 GC_cardMapIndex sizeToCardMapIndex (size_t z) {
  40   return (GC_cardMapIndex)z >> CARD_SIZE_LOG2;
  41 }
  42 size_t cardMapIndexToSize (GC_cardMapIndex i) {
  43   return (size_t)i << CARD_SIZE_LOG2;
  44 }
  45 GC_cardMapIndex pointerToCardMapIndexAbsolute (pointer p) {
  46   return (GC_cardMapIndex)p >> CARD_SIZE_LOG2;
  47 }
  48 GC_cardMapElem *pointerToCardMapAddr (GC_state s, pointer p) {
  49   GC_cardMapElem *res;
  50
  51   res = &s->generationalMaps.cardMapAbsolute[pointerToCardMapIndexAbsolute (p)];
  52   if (DEBUG_CARD_MARKING)
  53     fprintf (stderr, "pointerToCardMapAddr ("FMTPTR") = "FMTPTR"\n",
  54              (uintptr_t)p, (uintptr_t)res);
  55   return res;
  56 }
  57
  58 GC_crossMapIndex sizeToCrossMapIndex (size_t z) {
  59   return (GC_crossMapIndex)z >> CARD_SIZE_LOG2;
  60 }
  61
  62 #if ASSERT
  63 bool isCardMarked (GC_state s, pointer p) {
  64   return (*pointerToCardMapAddr (s, p) != 0x0);
  65 }
  66 #endif
  67
  68 void markCard (GC_state s, pointer p) {
  69   if (DEBUG_CARD_MARKING)
  70     fprintf (stderr, "markCard ("FMTPTR")\n", (uintptr_t)p);
  71   if (s->mutatorMarksCards)
  72     *(pointerToCardMapAddr (s, p)) = 0x1;
  73 }
  74
  75 void markIntergenerationalPointer (GC_state s, pointer *pp) {
  76   if (s->mutatorMarksCards
  77       and isPointerInOldGen (s, (pointer)pp)
  78       and isPointerInNursery (s, *pp))
  79     markCard (s, (pointer)pp);
  80 }
  81
  82 void markIntergenerationalObjptr (GC_state s, objptr *opp) {
  83   if (s->mutatorMarksCards
  84       and isPointerInOldGen (s, (pointer)opp)
  85       and isObjptrInNursery (s, *opp))
  86     markCard (s, (pointer)opp);
  87 }
  88
  89 void setCardMapAbsolute (GC_state s) {
  90   unless (s->mutatorMarksCards)
  91     return;
  92   /* It's OK if the subtraction below underflows because all the
  93    * subsequent additions to mark the cards will overflow and put us
  94    * in the right place.
  95    */
  96   s->generationalMaps.cardMapAbsolute =
  97     s->generationalMaps.cardMap
  98     - pointerToCardMapIndexAbsolute (s->heap.start);
  99   if (DEBUG_CARD_MARKING)
 100     fprintf (stderr, "setCardMapAbsolute = "FMTPTR"\n",
 101              (uintptr_t)s->generationalMaps.cardMapAbsolute);
 102 }
 103
 104 #if ASSERT
 105 pointer getCrossMapCardStart (GC_state s, pointer p) {
 106   /* The p - 1 is so that a pointer to the beginning of a card falls
 107    * into the index for the previous crossMap entry.
 108    */
 109   return
 110     (p == s->heap.start)
 111     ? s->heap.start
 112     : (p - 1) - ((uintptr_t)(p - 1) % CARD_SIZE);
 113 }
 114 #endif
 115
 116 size_t sizeofCardMap (GC_state s, size_t heapSize) {
 117   unless (s->mutatorMarksCards) {
 118     return 0;
 119   }
 120   assert (isAligned (heapSize, CARD_SIZE));
 121
 122   GC_cardMapIndex cardMapLength;
 123   size_t cardMapSize;
 124
 125   cardMapLength = sizeToCardMapIndex (heapSize);
 126   cardMapSize = align (cardMapLength * CARD_MAP_ELEM_SIZE, s->sysvals.pageSize);
 127
 128   return cardMapSize;
 129 }
 130
 131 GC_cardMapIndex lenofCardMap (ARG_USED_FOR_ASSERT GC_state s, size_t cardMapSize) {
 132   GC_cardMapIndex cardMapLength;
 133
 134   assert (isAligned (cardMapSize, s->sysvals.pageSize));
 135   assert (isAligned (cardMapSize, CARD_MAP_ELEM_SIZE));
 136
 137   cardMapLength = (GC_cardMapIndex)(cardMapSize / CARD_MAP_ELEM_SIZE);
 138
 139   return cardMapLength;
 140 }
 141
 142 size_t sizeofCrossMap (GC_state s, size_t heapSize) {
 143   unless (s->mutatorMarksCards) {
 144     return 0;
 145   }
 146   assert (isAligned (heapSize, CARD_SIZE));
 147
 148   GC_crossMapIndex crossMapLength;
 149   size_t crossMapSize;
 150
 151   crossMapLength = sizeToCrossMapIndex (heapSize);
 152   crossMapSize = align (crossMapLength * CROSS_MAP_ELEM_SIZE, s->sysvals.pageSize);
 153
 154   return crossMapSize;
 155 }
 156
 157 GC_crossMapIndex lenofCrossMap (ARG_USED_FOR_ASSERT GC_state s, size_t crossMapSize) {
 158   GC_crossMapIndex crossMapLength;
 159
 160   assert (isAligned (crossMapSize, s->sysvals.pageSize));
 161   assert (isAligned (crossMapSize, CROSS_MAP_ELEM_SIZE));
 162
 163   crossMapLength = (GC_crossMapIndex)(crossMapSize / CROSS_MAP_ELEM_SIZE);
 164
 165   return crossMapLength;
 166 }
 167
 168 void clearCardMap (GC_state s) {
 169   if (DEBUG_GENERATIONAL and DEBUG_DETAILED)
 170     fprintf (stderr, "clearCardMap ()\n");
 171   memset (s->generationalMaps.cardMap, 0,
 172           s->generationalMaps.cardMapLength * CARD_MAP_ELEM_SIZE);
 173 }
 174
 175 void clearCrossMap (GC_state s) {
 176   if (DEBUG_GENERATIONAL and DEBUG_DETAILED)
 177     fprintf (stderr, "clearCrossMap ()\n");
 178   s->generationalMaps.crossMapValidSize = 0;
 179   memset (s->generationalMaps.crossMap, CROSS_MAP_EMPTY,
 180           s->generationalMaps.crossMapLength * CROSS_MAP_ELEM_SIZE);
 181 }
 182
 183 void clearCardMapAndCrossMap (GC_state s) {
 184   clearCardMap (s);
 185   clearCrossMap (s);
 186 }
 187
 188 size_t sizeofCardMapAndCrossMap (GC_state s, size_t heapSize) {
 189   size_t totalMapSize;
 190
 191   totalMapSize = sizeofCardMap (s, heapSize) + sizeofCrossMap (s, heapSize);
 192
 193   assert (isAligned (totalMapSize, s->sysvals.pageSize));
 194
 195   return totalMapSize;
 196 }
 197
 198 /*
 199  * heapSize = invertSizeofCardMapAndCrossMap (s, heapWithMapsSize);
 200  * implies
 201  * heapSize + sizeofCardMapAndCrossMap (s, heapSize)
 202  *  <= heapWithMapsSize
 203  *  < (heapSize + s->sysvals.pageSize)
 204  *    + sizeofCardMapAndCrossMap (s, heapSize + s->sysvals.pageSize)
 205  */
 206 size_t invertSizeofCardMapAndCrossMap (GC_state s, size_t heapWithMapsSize) {
 207   unless (s->mutatorMarksCards) {
 208     return heapWithMapsSize;
 209   }
 210   assert (isAligned (heapWithMapsSize, s->sysvals.pageSize));
 211
 212   size_t minHeapSize;
 213   if (heapWithMapsSize <= 3 * s->sysvals.pageSize) {
 214     minHeapSize = 0;
 215   } else {
 216     double minHeapSizeD;
 217     minHeapSizeD =
 218       (((double)(CARD_SIZE)
 219         / (double)(CARD_SIZE + CARD_MAP_ELEM_SIZE + CROSS_MAP_ELEM_SIZE))
 220        * (double)(heapWithMapsSize - 3 * s->sysvals.pageSize)) -
 221       (((double)(CARD_MAP_ELEM_SIZE + CROSS_MAP_ELEM_SIZE)
 222         / (double)(CARD_SIZE + CARD_MAP_ELEM_SIZE + CROSS_MAP_ELEM_SIZE)) *
 223        (double)(s->sysvals.pageSize));
 224     minHeapSize = alignDown ((size_t)minHeapSizeD, s->sysvals.pageSize);
 225   }
 226
 227   size_t heapSize = minHeapSize;
 228   size_t nextHeapSize = heapSize + s->sysvals.pageSize;
 229   /* The termination condition is:
 230    *   heapWithMapsSize >= nextHeapSize + sizeofCardMapAndCrossMap (s, nextHeapSize)
 231    * However, nextHeapSize + sizeofCardMapAndCrossMap (s, nextHeapSize) may overflow.
 232    */
 233   while (heapWithMapsSize >= sizeofCardMapAndCrossMap (s, nextHeapSize) and
 234          heapWithMapsSize - sizeofCardMapAndCrossMap (s, nextHeapSize) >= nextHeapSize) {
 235     heapSize = nextHeapSize;
 236     nextHeapSize += s->sysvals.pageSize;
 237   }
 238
 239   assert (isAligned (heapSize, s->sysvals.pageSize));
 240   assert (heapSize + sizeofCardMapAndCrossMap (s, heapSize) <= heapWithMapsSize);
 241   assert (nextHeapSize == heapSize + s->sysvals.pageSize);
 242   assert (heapWithMapsSize < sizeofCardMapAndCrossMap (s, nextHeapSize) or
 243           heapWithMapsSize - sizeofCardMapAndCrossMap (s, nextHeapSize) < nextHeapSize);
 244
 245   if (DEBUG_DETAILED)
 246     fprintf (stderr, "invertSizeofCardMapAndCrossMap(%s) = %s\n",
 247              uintmaxToCommaString(heapWithMapsSize),
 248              uintmaxToCommaString(heapSize));
 249
 250   return heapSize;
 251 }
 252
 253 void setCardMapAndCrossMap (GC_state s) {
 254   unless (s->mutatorMarksCards) {
 255     s->generationalMaps.cardMapLength = 0;
 256     s->generationalMaps.cardMap = NULL;
 257     s->generationalMaps.cardMapAbsolute = NULL;
 258     s->generationalMaps.crossMapLength = 0;
 259     s->generationalMaps.crossMap = NULL;
 260     return;
 261   }
 262
 263   GC_cardMapIndex cardMapLength;
 264   size_t cardMapSize;
 265   GC_crossMapIndex crossMapLength;
 266   size_t crossMapSize;
 267
 268   cardMapSize = sizeofCardMap (s, s->heap.size);
 269   cardMapLength = lenofCardMap (s, cardMapSize);
 270   s->generationalMaps.cardMapLength = cardMapLength;
 271
 272   crossMapSize = sizeofCrossMap (s, s->heap.size);
 273   crossMapLength = lenofCrossMap (s, crossMapSize);
 274   s->generationalMaps.crossMapLength = crossMapLength;
 275
 276   /* The card map starts at the end of the heap. */
 277   assert (s->heap.withMapsSize == s->heap.size + cardMapSize + crossMapSize);
 278   s->generationalMaps.cardMap =
 279     (GC_cardMap) (s->heap.start + s->heap.size);
 280   s->generationalMaps.crossMap =
 281     (GC_crossMap) (s->heap.start + s->heap.size + cardMapSize);
 282   setCardMapAbsolute (s);
 283   clearCardMapAndCrossMap (s);
 284 }
 285
 286 #if ASSERT
 287 /* isCrossMapOk is a slower, but easier to understand, way of
 288  * computing the crossMap.  updateCrossMap (below) incrementally
 289  * updates the crossMap, checking only the part of the old generation
 290  * that it hasn't seen before.  isCrossMapOk simply walks through the
 291  * entire old generation.  It is useful to check that the incremental
 292  * update is working correctly.
 293  */
 294 bool isCrossMapOk (GC_state s) {
 295   static GC_crossMapElem *map;
 296   size_t mapSize;
 297
 298   pointer front, back;
 299   GC_cardMapIndex cardIndex;
 300   pointer cardStart;
 301
 302   if (DEBUG)
 303     fprintf (stderr, "isCrossMapOk ()\n");
 304   mapSize = s->generationalMaps.crossMapLength * CROSS_MAP_ELEM_SIZE;
 305   map = GC_mmapAnon_safe (NULL, mapSize);
 306   memset (map, CROSS_MAP_EMPTY, mapSize);
 307   back = s->heap.start + s->heap.oldGenSize;
 308   front = alignFrontier (s, s->heap.start);
 309 loopObjects:
 310   assert (front <= back);
 311   cardStart = getCrossMapCardStart (s, front);
 312   cardIndex = sizeToCardMapIndex ((size_t)(cardStart - s->heap.start));
 313   map[cardIndex] = (GC_crossMapElem)((front - cardStart) / CROSS_MAP_OFFSET_SCALE);
 314   if (front < back) {
 315     front += sizeofObject (s, advanceToObjectData (s, front));
 316     goto loopObjects;
 317   }
 318   for (size_t i = 0; i < cardIndex; ++i)
 319     assert (map[i] == s->generationalMaps.crossMap[i]);
 320   GC_release (map, mapSize);
 321   return TRUE;
 322 }
 323 #endif
 324
 325 void updateCrossMap (GC_state s) {
 326   GC_cardMapIndex cardIndex;
 327   pointer cardStart, cardEnd;
 328
 329   pointer nextObject, objectStart;
 330   pointer oldGenEnd;
 331
 332   if (DEBUG_GENERATIONAL) {
 333     fprintf (stderr, "updateCrossMap starting\n");
 334     displayGenerationalMaps (s, &s->generationalMaps, stderr);
 335   }
 336   assert (isAligned (s->alignment, CROSS_MAP_OFFSET_SCALE));
 337   if (s->generationalMaps.crossMapValidSize == s->heap.oldGenSize)
 338     goto done;
 339   oldGenEnd = s->heap.start + s->heap.oldGenSize;
 340   objectStart = s->heap.start + s->generationalMaps.crossMapValidSize;
 341   if (objectStart == s->heap.start) {
 342     cardIndex = 0;
 343     objectStart = alignFrontier (s, objectStart);
 344   } else
 345     cardIndex = sizeToCardMapIndex ((size_t)(objectStart - s->heap.start) - 1);
 346   cardStart = s->heap.start + cardMapIndexToSize (cardIndex);
 347   cardEnd = cardStart + CARD_SIZE;
 348 loopObjects:
 349   assert (objectStart < oldGenEnd);
 350   assert ((objectStart == s->heap.start or cardStart < objectStart)
 351           and objectStart <= cardEnd);
 352   nextObject = objectStart + sizeofObject (s, advanceToObjectData (s, objectStart));
 353   if (DEBUG_GENERATIONAL) {
 354     fprintf (stderr,
 355              "\tloopObjects:\n"
 356              "\t  cardIndex = %"PRIuMAX"\n"
 357              "\t  cardStart = "FMTPTR"\n"
 358              "\t    cardEnd = "FMTPTR"\n"
 359              "\tobjectStart = "FMTPTR"\n"
 360              "\t nextObject = "FMTPTR"\n",
 361              (uintmax_t)cardIndex, (uintptr_t)cardStart, (uintptr_t)cardEnd,
 362              (uintptr_t)objectStart, (uintptr_t)nextObject);
 363   }
 364   if (nextObject > cardEnd) {
 365     /* We're about to move to a new card, so we are looking at the
 366      * last object boundary in the current card.
 367      * Store it in the crossMap.
 368      */
 369     size_t offset;
 370
 371     offset = (size_t)(objectStart - cardStart) / CROSS_MAP_OFFSET_SCALE;
 372     assert (offset < CROSS_MAP_EMPTY);
 373     if (DEBUG_GENERATIONAL)
 374       fprintf (stderr, "crossMap[%"PRIuMAX"] = %"PRIuMAX"\n",
 375                (uintmax_t)cardIndex, (uintmax_t)offset);
 376     s->generationalMaps.crossMap[cardIndex] = (GC_crossMapElem)offset;
 377     cardIndex = sizeToCardMapIndex ((size_t)(nextObject - s->heap.start) - 1);
 378     cardStart = s->heap.start + cardMapIndexToSize (cardIndex);
 379     cardEnd = cardStart + CARD_SIZE;
 380   }
 381   objectStart = nextObject;
 382   if (objectStart < oldGenEnd)
 383     goto loopObjects;
 384   assert (objectStart == oldGenEnd);
 385   s->generationalMaps.crossMap[cardIndex] =
 386     (GC_crossMapElem)(oldGenEnd - cardStart) / CROSS_MAP_OFFSET_SCALE;
 387   s->generationalMaps.crossMapValidSize = s->heap.oldGenSize;
 388 done:
 389   assert (s->generationalMaps.crossMapValidSize == s->heap.oldGenSize);
 390   assert (isCrossMapOk (s));
 391   if (DEBUG_GENERATIONAL) {
 392     fprintf (stderr, "updateCrossMap finished\n");
 393     displayGenerationalMaps (s, &s->generationalMaps, stderr);
 394   }
 395 }