boehm-gc/gc_mark.h

   1 /*
   2  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
   3  *
   4  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   5  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   6  *
   7  * Permission is hereby granted to use or copy this program
   8  * for any purpose,  provided the above notices are retained on all copies.
   9  * Permission to modify the code and to distribute modified code is granted,
  10  * provided the above notices are retained, and a notice that the code was
  11  * modified is included with the above copyright notice.
  12  *
  13  */
  14 /* Boehm, November 7, 1994 4:56 pm PST */
  15
  16 /*
  17  * Declarations of mark stack.  Needed by marker and client supplied mark
  18  * routines.  To be included after gc_priv.h.
  19  */
  20 #ifndef GC_MARK_H
  21 # define GC_MARK_H
  22
  23 /* A client supplied mark procedure.  Returns new mark stack pointer.   */
  24 /* Primary effect should be to push new entries on the mark stack.      */
  25 /* Mark stack pointer values are passed and returned explicitly.        */
  26 /* Global variables decribing mark stack are not necessarily valid.     */
  27 /* (This usually saves a few cycles by keeping things in registers.)    */
  28 /* Assumed to scan about PROC_BYTES on average.  If it needs to do      */
  29 /* much more work than that, it should do it in smaller pieces by       */
  30 /* pushing itself back on the mark stack.                               */
  31 /* Note that it should always do some work (defined as marking some     */
  32 /* objects) before pushing more than one entry on the mark stack.       */
  33 /* This is required to ensure termination in the event of mark stack    */
  34 /* overflows.                                                           */
  35 /* This procedure is always called with at least one empty entry on the */
  36 /* mark stack.                                                          */
  37 /* Currently we require that mark procedures look for pointers in a     */
  38 /* subset of the places the conservative marker would.  It must be safe */
  39 /* to invoke the normal mark procedure instead.                         */
  40 # define PROC_BYTES 100
  41 typedef struct ms_entry * (*mark_proc)(/* word * addr, mark_stack_ptr,
  42                                           mark_stack_limit, env */);
  43
  44 # define LOG_MAX_MARK_PROCS 6
  45 # define MAX_MARK_PROCS (1 << LOG_MAX_MARK_PROCS)
  46 extern mark_proc GC_mark_procs[MAX_MARK_PROCS];
  47 extern word GC_n_mark_procs;
  48
  49 /* Object descriptors on mark stack or in objects.  Low order two       */
  50 /* bits are tags distinguishing among the following 4 possibilities     */
  51 /* for the high order 30 bits.                                          */
  52 #define DS_TAG_BITS 2
  53 #define DS_TAGS   ((1 << DS_TAG_BITS) - 1)
  54 #define DS_LENGTH 0     /* The entire word is a length in bytes that    */
  55                         /* must be a multiple of 4.                     */
  56 #define DS_BITMAP 1     /* 30 bits are a bitmap describing pointer      */
  57                         /* fields.  The msb is 1 iff the first word     */
  58                         /* is a pointer.                                */
  59                         /* (This unconventional ordering sometimes      */
  60                         /* makes the marker slightly faster.)           */
  61                         /* Zeroes indicate definite nonpointers.  Ones  */
  62                         /* indicate possible pointers.                  */
  63                         /* Only usable if pointers are word aligned.    */
  64 #   define BITMAP_BITS (WORDSZ - DS_TAG_BITS)
  65 #define DS_PROC   2
  66                         /* The objects referenced by this object can be */
  67                         /* pushed on the mark stack by invoking         */
  68                         /* PROC(descr).  ENV(descr) is passed as the    */
  69                         /* last argument.                               */
  70 #   define PROC(descr) \
  71                 (GC_mark_procs[((descr) >> DS_TAG_BITS) & (MAX_MARK_PROCS-1)])
  72 #   define ENV(descr) \
  73                 ((descr) >> (DS_TAG_BITS + LOG_MAX_MARK_PROCS))
  74 #   define MAX_ENV \
  75               (((word)1 << (WORDSZ - DS_TAG_BITS - LOG_MAX_MARK_PROCS)) - 1)
  76 #   define MAKE_PROC(proc_index, env) \
  77             (((((env) << LOG_MAX_MARK_PROCS) | (proc_index)) << DS_TAG_BITS) \
  78             | DS_PROC)
  79 #define DS_PER_OBJECT 3 /* The real descriptor is at the                */
  80                         /* byte displacement from the beginning of the  */
  81                         /* object given by descr & ~DS_TAGS             */
  82
  83 typedef struct ms_entry {
  84     word * mse_start;   /* First word of object */
  85     word mse_descr;     /* Descriptor; low order two bits are tags,     */
  86                         /* identifying the upper 30 bits as one of the  */
  87                         /* following:                                   */
  88 } mse;
  89
  90 extern word GC_mark_stack_size;
  91
  92 extern mse * GC_mark_stack_top;
  93
  94 extern mse * GC_mark_stack;
  95
  96 word GC_find_start();
  97
  98 mse * GC_signal_mark_stack_overflow();
  99
 100 # ifdef GATHERSTATS
 101 #   define ADD_TO_ATOMIC(sz) GC_atomic_in_use += (sz)
 102 #   define ADD_TO_COMPOSITE(sz) GC_composite_in_use += (sz)
 103 # else
 104 #   define ADD_TO_ATOMIC(sz)
 105 #   define ADD_TO_COMPOSITE(sz)
 106 # endif
 107
 108 /* Push the object obj with corresponding heap block header hhdr onto   */
 109 /* the mark stack.                                                      */
 110 # define PUSH_OBJ(obj, hhdr, mark_stack_top, mark_stack_limit) \
 111 { \
 112     register word _descr = (hhdr) -> hb_descr; \
 113         \
 114     if (_descr == 0) { \
 115         ADD_TO_ATOMIC((hhdr) -> hb_sz); \
 116     } else { \
 117         ADD_TO_COMPOSITE((hhdr) -> hb_sz); \
 118         mark_stack_top++; \
 119         if (mark_stack_top >= mark_stack_limit) { \
 120           mark_stack_top = GC_signal_mark_stack_overflow(mark_stack_top); \
 121         } \
 122         mark_stack_top -> mse_start = (obj); \
 123         mark_stack_top -> mse_descr = _descr; \
 124     } \
 125 }
 126
 127 #ifdef PRINT_BLACK_LIST
 128 #   define GC_FIND_START(current, hhdr, source) \
 129         GC_find_start(current, hhdr, source)
 130 #else
 131 #   define GC_FIND_START(current, hhdr, source) \
 132         GC_find_start(current, hhdr)
 133 #endif
 134
 135 /* Push the contents of current onto the mark stack if it is a valid    */
 136 /* ptr to a currently unmarked object.  Mark it.                        */
 137 /* If we assumed a standard-conforming compiler, we could probably      */
 138 /* generate the exit_label transparently.                               */
 139 # define PUSH_CONTENTS(current, mark_stack_top, mark_stack_limit, \
 140                        source, exit_label) \
 141 { \
 142     register int displ;  /* Displacement in block; first bytes, then words */ \
 143     register hdr * hhdr; \
 144     register map_entry_type map_entry; \
 145     \
 146     GET_HDR(current,hhdr); \
 147     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { \
 148          current = GC_FIND_START(current, hhdr, (word)source); \
 149          if (current == 0) goto exit_label; \
 150          hhdr = HDR(current); \
 151     } \
 152     displ = HBLKDISPL(current); \
 153     map_entry = MAP_ENTRY((hhdr -> hb_map), displ); \
 154     if (map_entry == OBJ_INVALID) { \
 155         GC_ADD_TO_BLACK_LIST_NORMAL(current, source); goto exit_label; \
 156     } \
 157     displ = BYTES_TO_WORDS(displ); \
 158     displ -= map_entry; \
 159         \
 160     { \
 161         register word * mark_word_addr = hhdr -> hb_marks + divWORDSZ(displ); \
 162         register word mark_word = *mark_word_addr; \
 163         register word mark_bit = (word)1 << modWORDSZ(displ); \
 164           \
 165         if (mark_word & mark_bit) { \
 166               /* Mark bit is already set */ \
 167               goto exit_label; \
 168         } \
 169         *mark_word_addr = mark_word | mark_bit; \
 170     } \
 171     PUSH_OBJ(((word *)(HBLKPTR(current)) + displ), hhdr, \
 172              mark_stack_top, mark_stack_limit) \
 173   exit_label: ; \
 174 }
 175
 176
 177 /*
 178  * Push a single value onto mark stack. Mark from the object pointed to by p.
 179  * GC_push_one is normally called by GC_push_regs, and thus must be defined.
 180  * P is considered valid even if it is an interior pointer.
 181  * Previously marked objects are not pushed.  Hence we make progress even
 182  * if the mark stack overflows.
 183  */
 184 # define GC_PUSH_ONE_STACK(p) \
 185     if ((ptr_t)(p) >= GC_least_plausible_heap_addr      \
 186          && (ptr_t)(p) < GC_greatest_plausible_heap_addr) {     \
 187          GC_push_one_checked(p,TRUE);   \
 188     }
 189
 190 /*
 191  * As above, but interior pointer recognition as for
 192  * normal for heap pointers.
 193  */
 194 # ifdef ALL_INTERIOR_POINTERS
 195 #   define AIP TRUE
 196 # else
 197 #   define AIP FALSE
 198 # endif
 199 # define GC_PUSH_ONE_HEAP(p) \
 200     if ((ptr_t)(p) >= GC_least_plausible_heap_addr      \
 201          && (ptr_t)(p) < GC_greatest_plausible_heap_addr) {     \
 202          GC_push_one_checked(p,AIP);    \
 203     }
 204
 205 /*
 206  * Mark from one finalizable object using the specified
 207  * mark proc. May not mark the object pointed to by
 208  * real_ptr. That is the job of the caller, if appropriate
 209  */
 210 # define GC_MARK_FO(real_ptr, mark_proc) \
 211 { \
 212     (*(mark_proc))(real_ptr); \
 213     while (!GC_mark_stack_empty()) GC_mark_from_mark_stack(); \
 214     if (GC_mark_state != MS_NONE) { \
 215         GC_set_mark_bit(real_ptr); \
 216         while (!GC_mark_some()); \
 217     } \
 218 }
 219
 220 extern GC_bool GC_mark_stack_too_small;
 221                                 /* We need a larger mark stack.  May be */
 222                                 /* set by client supplied mark routines.*/
 223
 224 typedef int mark_state_t;       /* Current state of marking, as follows:*/
 225                                 /* Used to remember where we are during */
 226                                 /* concurrent marking.                  */
 227
 228                                 /* We say something is dirty if it was  */
 229                                 /* written since the last time we       */
 230                                 /* retrieved dirty bits.  We say it's   */
 231                                 /* grungy if it was marked dirty in the */
 232                                 /* last set of bits we retrieved.       */
 233
 234                                 /* Invariant I: all roots and marked    */
 235                                 /* objects p are either dirty, or point */
 236                                 /* objects q that are either marked or  */
 237                                 /* a pointer to q appears in a range    */
 238                                 /* on the mark stack.                   */
 239
 240 # define MS_NONE 0              /* No marking in progress. I holds.     */
 241                                 /* Mark stack is empty.                 */
 242
 243 # define MS_PUSH_RESCUERS 1     /* Rescuing objects are currently       */
 244                                 /* being pushed.  I holds, except       */
 245                                 /* that grungy roots may point to       */
 246                                 /* unmarked objects, as may marked      */
 247                                 /* grungy objects above scan_ptr.       */
 248
 249 # define MS_PUSH_UNCOLLECTABLE 2
 250                                 /* I holds, except that marked          */
 251                                 /* uncollectable objects above scan_ptr */
 252                                 /* may point to unmarked objects.       */
 253                                 /* Roots may point to unmarked objects  */
 254
 255 # define MS_ROOTS_PUSHED 3      /* I holds, mark stack may be nonempty  */
 256
 257 # define MS_PARTIALLY_INVALID 4 /* I may not hold, e.g. because of M.S. */
 258                                 /* overflow.  However marked heap       */
 259                                 /* objects below scan_ptr point to      */
 260                                 /* marked or stacked objects.           */
 261
 262 # define MS_INVALID 5           /* I may not hold.                      */
 263
 264 extern mark_state_t GC_mark_state;
 265
 266 #endif  /* GC_MARK_H */
 267