ghc/runtime/storage/SMmarkDefs.lh

   1 %****************************************************************************
   2 %
   3 \section[SMmarkDefs.lh]{Definitions used by Pointer-Reversing Mark code}
   4 %
   5 % (c) P. Sansom, K. Hammond, Glasgow University, January 26th 1993.
   6 %
   7 %****************************************************************************
   8
   9 Describe how to set the mark bit for a closure.
  10
  11 \begin{code}
  12 #if defined(GCgn)
  13
  14 #define SET_MARK_BIT(closure)                                   \
  15     do {                                                        \
  16       if (closure <= HeapLim) /* tested heap range for GCgn */  \
  17         {                                                       \
  18           long _hp_word = ((P_)closure) - HeapBase;             \
  19           ASSERT(!IS_STATIC(INFO_PTR(closure)));                \
  20           DEBUG_SET_MARK(closure, _hp_word);                    \
  21           BitArray[_hp_word / BITS_IN(BitWord)] |=              \
  22                 1L << (_hp_word & (BITS_IN(BitWord) - 1));      \
  23         }                                                       \
  24     } while(0)
  25
  26 #define CLEAR_MARK_BIT(closure)                                 \
  27     do {                                                        \
  28         long _hp_word = ((P_)closure) - HeapBase;               \
  29         ASSERT(!IS_STATIC(INFO_PTR(closure)));                  \
  30         BitArray[_hp_word / BITS_IN(BitWord)] &=                \
  31                 ~(1L << (_hp_word & (BITS_IN(BitWord) - 1)));   \
  32     } while (0)
  33
  34 #else
  35
  36 #define SET_MARK_BIT(closure)                                   \
  37     do {                                                        \
  38         long _hp_word = ((P_)closure) - HeapBase;               \
  39         ASSERT(!IS_STATIC(INFO_PTR(closure)));                  \
  40         DEBUG_SET_MARK(closure, _hp_word);                      \
  41         BitArray[_hp_word / BITS_IN(BitWord)] |=                \
  42                 1L << (_hp_word & (BITS_IN(BitWord) - 1));      \
  43     } while (0)
  44
  45 #define CLEAR_MARK_BIT(closure)                                 \
  46     do {                                                        \
  47         long _hp_word = ((P_)closure) - HeapBase;               \
  48         ASSERT(!IS_STATIC(INFO_PTR(closure)));                  \
  49         BitArray[_hp_word / BITS_IN(BitWord)] &=                \
  50                 ~(1L << (_hp_word & (BITS_IN(BitWord) - 1)));   \
  51     } while (0)
  52
  53 \end{code}
  54
  55 Macros from hell for frobbing bits in the bit array while marking.  We
  56 maintain a counter after the mark bit that tells us which pointers
  57 we've visited in a closure.  The bits in this counter may span word
  58 boundaries, and require some considerable ickiness to get munged into
  59 one word so Mr C Programmer can use them.
  60
  61 Three variants follow.  The first is for closures which contain fewer
  62 pointers than there are bits in a word.
  63
  64 \begin{code}
  65
  66 #define GM_MASK(x) ((1L << (x)) - 1)
  67
  68 #define GET_MARKED_PTRS(dest,closure,ptrs)                      \
  69     do {                                                        \
  70         long hw = ((P_)(closure)) - HeapBase + 1;               \
  71         BitWord *bw = BitArray + (hw / BITS_IN(BitWord));       \
  72         int offset = hw & (BITS_IN(BitWord) - 1);               \
  73         int bat = BITS_IN(BitWord) - offset;                    \
  74                                                                 \
  75         ASSERT(!IS_STATIC(INFO_PTR(closure)));                  \
  76                                                                 \
  77         (dest) = (ptrs) <= bat ?                                \
  78             bw[0] >> offset & GM_MASK(ptrs) :                   \
  79             bw[0] >> offset |                                   \
  80                 (bw[1] & GM_MASK((ptrs) - bat)) << bat;         \
  81     } while (0)
  82
  83 /* hw is the offset in words of closure from HeapBase + 1.
  84
  85    bw points to the BitArray word containing the bit corresponding
  86         to the *second* word of the closure [hence +1 above]
  87         (the bit corresp first word is the mark bit)
  88
  89    offset is the offset (in bits, from LS end, zero indexed) within *bw
  90         of the first bit of value in *bw,
  91
  92    bat is offset from the other end of the word; that's the same
  93         as the number of bits available to store value in *bw.
  94
  95
  96 NOTA BENE: this code is awfully conservative.  In order to store a
  97 value which ranges 0--ptrs we use a field of ptrs bits wide.  We
  98 only need a field of log(ptrs) wide!
  99
 100 */
 101
 102 /* "ptrs" is actually used as the width of the bit-field
 103    in which we store "val". */
 104
 105 #define SET_MARKED_PTRS(closure,ptrs,val)                       \
 106     do {                                                        \
 107         long hw = ((P_)(closure)) - HeapBase + 1;               \
 108         BitWord *bw = BitArray + (hw / BITS_IN(BitWord));       \
 109         int offset = hw & (BITS_IN(BitWord) - 1);               \
 110         int bat = BITS_IN(BitWord) - offset;                    \
 111         BitWord bits;                                           \
 112                                                                 \
 113         ASSERT( (ptrs) < BITS_IN(BitWord) );                    \
 114         ASSERT(!IS_STATIC(INFO_PTR(closure)));                  \
 115                                                                 \
 116         bits = bw[0] & ~(GM_MASK(ptrs) << offset);              \
 117         bw[0] = bits | (val) << offset;                         \
 118         if ((ptrs) > bat) {                                     \
 119             bits = bw[1] & ~GM_MASK((ptrs) - bat);              \
 120             bw[1] = bits | ((val) >> bat);                      \
 121         }                                                       \
 122     } while (0)
 123 /* NB Since ptrs < BITS_IN(BitWord)
 124    we can be sure that the conditional will only happen if bat is strictly
 125    *smaller* than BITS_IN(BitWord), and hence the right shift in the
 126    last line is ok */
 127
 128 /*
 129  * These are for the GEN family, which may blow up the GM_MASK macro.
 130  */
 131
 132         /* If there are more ptrs than bits in a word, we still
 133            use just one word to store the value; value is bound to
 134            be < 2**(bits-in-word - 1) */
 135
 136 #define __MIN__(a,b) (((a) < (b)) ? (a) : (b))
 137
 138 #define GET_GEN_MARKED_PTRS(dest,closure,ptrs)                  \
 139         GET_MARKED_PTRS(dest,closure,__MIN__(ptrs,BITS_IN(BitWord)-1))
 140
 141 #define SET_GEN_MARKED_PTRS(closure,ptrs,val)                   \
 142         SET_MARKED_PTRS(closure,__MIN__(ptrs,BITS_IN(BitWord)-1),val)
 143
 144 /* Be very careful to use the following macro only for dynamic closures! */
 145
 146 #define IS_MARK_BIT_SET(closure)                                                \
 147         ((BitArray[(((P_)closure) - HeapBase) / BITS_IN(BitWord)] >>            \
 148          ((((P_)closure) - HeapBase) & (BITS_IN(BitWord) - 1))) & 0x1)
 149
 150 #endif
 151 \end{code}
 152
 153 Don't set the mark bit when changing to marking in the next pointer.
 154
 155 \begin{code}
 156 #define INIT_MARK_NODE(dbg,ptrs)                \
 157         do {                                    \
 158           DEBUG_PRSTART(dbg, ptrs);             \
 159           LINK_GLOBALADDRESS(Mark);             \
 160           SET_MARK_BIT(Mark);                   \
 161         } while (0)
 162
 163 #define CONTINUE_MARKING_NODE(dbg,pos)                          \
 164         do {                                                    \
 165           DEBUG_PRIN(dbg, pos);                 \
 166         } while (0)
 167 \end{code}
 168
 169 @JUMP_MARK@ and @JUMP_MARK_RETURN@ define how to jump to the marking
 170 entry code for a child closure (\tr{Mark}), or to the return code for
 171 its parent (\tr{MStack}), when marking's been completed.
 172
 173 \begin{code}
 174 #define JUMP_MARK                                               \
 175         JMP_(PRMARK_CODE(INFO_PTR(Mark)))
 176
 177 #define JUMP_MARK_RETURN                                        \
 178         JMP_(PRRETURN_CODE(INFO_PTR(MStack)))
 179 \end{code}
 180
 181 Initialise the marking stack to mark from the first pointer in the
 182 closure (as specified by \tr{first_ptr}).  The type of the closure is
 183 given by \tr{closure_ptr}.
 184
 185 \begin{code}
 186 #define INIT_MSTACK_FROM(closure_ptr,first_ptr)                 \
 187     do {                                                        \
 188         P_ temp = (P_) closure_ptr(Mark, first_ptr);            \
 189         closure_ptr(Mark, first_ptr) = (W_) MStack;             \
 190 /*fprintf(stderr,"first_ptr=%d;temp=%lx;Mark=%lx;MStack=%lx\n",first_ptr,temp,Mark,MStack);*/ \
 191         MStack = Mark;                                          \
 192         Mark = temp;                                            \
 193         JUMP_MARK;                                              \
 194     } while (0)
 195 \end{code}
 196
 197 Initialise the marking stack to mark from the first pointer in
 198 the closure.  The type of the closure is given by \tr{closure_ptr}.
 199
 200 \begin{code}
 201 #define INIT_MSTACK(closure_ptr)                                \
 202     INIT_MSTACK_FROM(closure_ptr,1)
 203 \end{code}
 204
 205 Move to the next pointer after \tr{pos} in the closure whose
 206 type is given by \tr{closure_ptr}.
 207
 208 \begin{code}
 209 #define MOVE_TO_NEXT_PTR(closure_ptr,pos)                       \
 210     do {                                                        \
 211         P_ temp = (P_) closure_ptr(MStack, pos+1);              \
 212         closure_ptr(MStack, pos+1) = closure_ptr(MStack, pos);  \
 213         closure_ptr(MStack, pos) = (W_) Mark;                   \
 214         Mark = temp;                                            \
 215         JUMP_MARK;                                              \
 216     } while(0)
 217 \end{code}
 218
 219 Pop the mark stack at \tr{pos}, having flushed all pointers in
 220 a closure.
 221
 222 \begin{code}
 223 #define POP_MSTACK(dbg,closure_ptr,pos)                         \
 224     do {                                                        \
 225         RESTORE_MSTACK(dbg,closure_ptr,pos);                    \
 226         JUMP_MARK_RETURN;                                       \
 227     } while (0)
 228
 229 #define RESTORE_MSTACK(dbg,closure_ptr,pos)                     \
 230     do {                                                        \
 231         P_ temp = Mark;                                         \
 232         DEBUG_PRLAST(dbg, pos);                                 \
 233         Mark = MStack;                                          \
 234         MStack = (P_) closure_ptr(Mark, pos);                   \
 235         closure_ptr(Mark, pos) = (W_) temp;                     \
 236     } while (0)
 237 \end{code}
 238
 239 Define some debugging macros.
 240
 241 \begin{code}
 242 #if defined(_GC_DEBUG)
 243
 244 #define DEBUG_PRSTART(type, ptrsvar) \
 245     if (SM_trace & 8)                         \
 246         fprintf(stderr, "PRMark Start (%s): 0x%lx, info 0x%lx ptrs %ld\n", \
 247                 type, Mark, INFO_PTR(Mark), ptrsvar)
 248
 249 #define DEBUG_PRIN(type, posvar) \
 250     if (SM_trace & 8)                     \
 251         fprintf(stderr, "PRRet  In    (%s): 0x%lx, info 0x%lx pos %ld\n", \
 252                 type, MStack, INFO_PTR(MStack), posvar)
 253
 254 #define DEBUG_PRLAST(type, ptrvar) \
 255     if (SM_trace & 8)                       \
 256         fprintf(stderr, "PRRet  Last  (%s): 0x%lx, info 0x%lx ptrs %ld\n", \
 257                 type, MStack, INFO_PTR(MStack), ptrvar)
 258
 259 #define DEBUG_PR_MARKED \
 260     if (SM_trace & 8)   \
 261         fprintf(stderr, "PRMark Marked      : 0x%lx, info 0x%lx\n", \
 262                 Mark, INFO_PTR(Mark))
 263
 264 #define DEBUG_PR_STAT \
 265     if (SM_trace & 8) \
 266         fprintf(stderr, "PRMark Static      : 0x%lx, info 0x%lx\n", \
 267                 Mark, INFO_PTR(Mark))
 268
 269 #define DEBUG_PR_IND  \
 270     if (SM_trace & 8) \
 271         fprintf(stderr, "PRMark Ind : 0x%lx -> PRMark(0x%lx), info 0x%lx\n", \
 272                 Mark, IND_CLOSURE_PTR(Mark), INFO_PTR(Mark))
 273
 274 #define DEBUG_PR_CAF  \
 275     if (SM_trace & 8) \
 276         fprintf(stderr, "PRMark Caf : 0x%lx -> PRMark(0x%lx), info 0x%lx\n", \
 277                 Mark, IND_CLOSURE_PTR(Mark), INFO_PTR(Mark))
 278
 279 #define DEBUG_PR_CONST \
 280     if (SM_trace & 8)  \
 281         fprintf(stderr, "PRMark Const : 0x%lx -> 0x%lx, info 0x%lx\n", \
 282                 Mark, CONST_STATIC_CLOSURE(INFO_PTR(Mark)), INFO_PTR(Mark))
 283
 284 #define DEBUG_PR_CHARLIKE \
 285     if (SM_trace & 8)  \
 286         fprintf(stderr, "PRMark CharLike (%lx) : 0x%lx -> 0x%lx, info 0x%lx\n", \
 287                 CHARLIKE_VALUE(Mark), Mark, CHARLIKE_CLOSURE(CHARLIKE_VALUE(Mark)), INFO_PTR(Mark))
 288
 289 #define DEBUG_PR_INTLIKE_TO_STATIC \
 290     if (SM_trace & 8)  \
 291         fprintf(stderr, "PRMark IntLike to Static (%ld) : 0x%lx -> 0x%lx, info 0x%lx\n", \
 292                 INTLIKE_VALUE(Mark), Mark, INTLIKE_CLOSURE(INTLIKE_VALUE(Mark)), INFO_PTR(Mark))
 293
 294 #define DEBUG_PR_INTLIKE_IN_HEAP \
 295     if (SM_trace & 8)  \
 296         fprintf(stderr, "PRMark IntLike in Heap   (%ld) : 0x%lx, info 0x%lx\n", \
 297                 INTLIKE_VALUE(Mark), Mark, INFO_PTR(Mark))
 298
 299 #define DEBUG_PR_OLDIND \
 300     if (SM_trace & 8) \
 301         fprintf(stderr, "PRMark OldRoot Ind : 0x%lx -> PRMark(0x%lx), info 0x%lx\n", \
 302                 Mark, IND_CLOSURE_PTR(Mark), INFO_PTR(Mark))
 303
 304 #else
 305
 306 #define DEBUG_PRSTART(type, ptrvar)
 307 #define DEBUG_PRIN(type, posvar)
 308 #define DEBUG_PRLAST(type, ptrvar)
 309 #define DEBUG_PR_MARKED
 310 #define DEBUG_PR_STAT
 311 #define DEBUG_PR_IND
 312 #define DEBUG_PR_CAF
 313 #define DEBUG_PR_CONST
 314 #define DEBUG_PR_CHARLIKE
 315 #define DEBUG_PR_INTLIKE_TO_STATIC
 316 #define DEBUG_PR_INTLIKE_IN_HEAP
 317 #define DEBUG_PR_OLDIND
 318
 319 #endif
 320
 321 \end{code}
 322