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