runtime/gc/generational.h

   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 #if (defined (MLTON_GC_INTERNAL_TYPES))
  11
  12 /* must agree w/ cardSizeLog2 in ssa-to-rssa.fun */
  13 #define CARD_SIZE_LOG2 8
  14 #define CARD_SIZE TWOPOWER(CARD_SIZE_LOG2)
  15
  16 typedef uint8_t GC_cardMapElem;
  17 typedef uint8_t GC_crossMapElem;
  18
  19 typedef GC_cardMapElem *GC_cardMap;
  20 typedef GC_crossMapElem *GC_crossMap;
  21
  22 typedef size_t GC_cardMapIndex;
  23 typedef size_t GC_crossMapIndex;
  24 #define CARD_MAP_ELEM_SIZE sizeof(GC_cardMapElem)
  25 #define CROSS_MAP_ELEM_SIZE sizeof(GC_crossMapElem)
  26 #define CROSS_MAP_EMPTY ((GC_crossMapElem)255)
  27 #define CROSS_MAP_OFFSET_SCALE 4
  28 #define FMTCME "%"PRIu8
  29
  30 struct GC_generationalMaps {
  31   /* cardMap is an array with cardinality equal to the size of the
  32    * heap divided by card size.  Each element in the array is
  33    * interpreted as a boolean; true indicates that some mutable field
  34    * of some object in the corresponding card in the heap has been
  35    * written since the last minor GC; hence, the corresponding card
  36    * must be traced at the next minor GC.
  37    */
  38   GC_cardMap cardMap;
  39   GC_cardMap cardMapAbsolute;
  40   GC_cardMapIndex cardMapLength;
  41   /* crossMap is an array with cardinality equal to the size of the
  42    * heap divided by card size.  Each element in the array is
  43    * interpreted as a byte offset (scaled by CARD_MAP_OFFSET_SCALE);
  44    * the offset indicates the start of the last object in the
  45    * corresponding card from the start of the card.
  46    */
  47   GC_crossMap crossMap;
  48   GC_crossMapIndex crossMapLength;
  49   /* crossMapValidSize the size of the prefix of the old generation
  50    * for which the crossMap is valid.
  51    */
  52   size_t crossMapValidSize;
  53 };
  54
  55 #endif /* (defined (MLTON_GC_INTERNAL_TYPES)) */
  56
  57 #if (defined (MLTON_GC_INTERNAL_FUNCS))
  58
  59 static void displayGenerationalMaps (GC_state s,
  60                                      struct GC_generationalMaps *generational,
  61                                      FILE *stream);
  62
  63 static inline GC_cardMapIndex sizeToCardMapIndex (size_t z);
  64 static inline size_t cardMapIndexToSize (GC_cardMapIndex i);
  65 static inline GC_cardMapIndex pointerToCardMapIndexAbsolute (pointer p);
  66 static inline GC_cardMapElem *pointerToCardMapAddr (GC_state s, pointer p);
  67
  68 static inline GC_crossMapIndex sizeToCrossMapIndex (size_t z);
  69
  70 #if ASSERT
  71 static inline bool isCardMarked (GC_state s, pointer p);
  72 #endif
  73 static inline void markCard (GC_state s, pointer p);
  74 static inline void markIntergenerationalPointer (GC_state s, pointer *pp);
  75 static inline void markIntergenerationalObjptr (GC_state s, objptr *opp);
  76
  77 static inline void setCardMapAbsolute (GC_state s);
  78 #if ASSERT
  79 static inline pointer getCrossMapCardStart (GC_state s, pointer p);
  80 #endif
  81
  82 static inline size_t sizeofCardMap (GC_state s, size_t heapSize);
  83 static inline GC_cardMapIndex lenofCardMap (GC_state s, size_t cardMapSize);
  84 static inline size_t sizeofCrossMap (GC_state s, size_t heapSize);
  85 static inline GC_crossMapIndex lenofCrossMap (GC_state s, size_t crossMapSize);
  86 static size_t sizeofCardMapAndCrossMap (GC_state s, size_t heapSize);
  87 static size_t invertSizeofCardMapAndCrossMap (GC_state s, size_t heapWithMapsSize);
  88
  89 static inline void clearCardMap (GC_state s);
  90 static inline void clearCrossMap (GC_state s);
  91 static inline void clearCardMapAndCrossMap (GC_state s);
  92 static void setCardMapAndCrossMap (GC_state s);
  93
  94 #if ASSERT
  95 static bool isCrossMapOk (GC_state s);
  96 #endif
  97 static void updateCrossMap (GC_state s);
  98
  99 #endif /* (defined (MLTON_GC_INTERNAL_FUNCS)) */