Back to index

lightning-sunbird  0.9+nobinonly
gc_mark.h
Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
00003  *
00004  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
00005  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
00006  *
00007  * Permission is hereby granted to use or copy this program
00008  * for any purpose,  provided the above notices are retained on all copies.
00009  * Permission to modify the code and to distribute modified code is granted,
00010  * provided the above notices are retained, and a notice that the code was
00011  * modified is included with the above copyright notice.
00012  *
00013  */
00014 /* Boehm, November 7, 1994 4:56 pm PST */
00015 
00016 /*
00017  * Declarations of mark stack.  Needed by marker and client supplied mark
00018  * routines.  To be included after gc_priv.h.
00019  */
00020 #ifndef GC_MARK_H
00021 # define GC_MARK_H
00022 
00023 /* A client supplied mark procedure.  Returns new mark stack pointer. */
00024 /* Primary effect should be to push new entries on the mark stack.    */
00025 /* Mark stack pointer values are passed and returned explicitly.      */
00026 /* Global variables decribing mark stack are not necessarily valid.   */
00027 /* (This usually saves a few cycles by keeping things in registers.)  */
00028 /* Assumed to scan about PROC_BYTES on average.  If it needs to do    */
00029 /* much more work than that, it should do it in smaller pieces by     */
00030 /* pushing itself back on the mark stack.                      */
00031 /* Note that it should always do some work (defined as marking some   */
00032 /* objects) before pushing more than one entry on the mark stack.     */
00033 /* This is required to ensure termination in the event of mark stack  */
00034 /* overflows.                                                  */
00035 /* This procedure is always called with at least one empty entry on the */
00036 /* mark stack.                                                        */
00037 /* Currently we require that mark procedures look for pointers in a   */
00038 /* subset of the places the conservative marker would.  It must be safe      */
00039 /* to invoke the normal mark procedure instead.                       */
00040 # define PROC_BYTES 100
00041 /* The real declarations of the following are in gc_priv.h, so that   */
00042 /* we can avoid scanning the following table.                         */
00043 /*
00044 typedef struct ms_entry * (*mark_proc)(   word * addr, mark_stack_ptr,
00045                                      mark_stack_limit, env   );
00046                                      
00047 # define LOG_MAX_MARK_PROCS 6
00048 # define MAX_MARK_PROCS (1 << LOG_MAX_MARK_PROCS)
00049 extern mark_proc GC_mark_procs[MAX_MARK_PROCS];
00050 */
00051 
00052 extern word GC_n_mark_procs;
00053 
00054 /* Object descriptors on mark stack or in objects.  Low order two     */
00055 /* bits are tags distinguishing among the following 4 possibilities   */
00056 /* for the high order 30 bits.                                        */
00057 #define DS_TAG_BITS 2
00058 #define DS_TAGS   ((1 << DS_TAG_BITS) - 1)
00059 #define DS_LENGTH 0  /* The entire word is a length in bytes that     */
00060                      /* must be a multiple of 4.               */
00061 #define DS_BITMAP 1  /* 30 bits are a bitmap describing pointer       */
00062                      /* fields.  The msb is 1 iff the first word      */
00063                      /* is a pointer.                          */
00064                      /* (This unconventional ordering sometimes       */
00065                      /* makes the marker slightly faster.)            */
00066                      /* Zeroes indicate definite nonpointers.  Ones   */
00067                      /* indicate possible pointers.                   */
00068                      /* Only usable if pointers are word aligned.     */
00069 #   define BITMAP_BITS (WORDSZ - DS_TAG_BITS)
00070 #define DS_PROC   2
00071                      /* The objects referenced by this object can be */
00072                      /* pushed on the mark stack by invoking          */
00073                      /* PROC(descr).  ENV(descr) is passed as the     */
00074                      /* last argument.                         */
00075 #   define PROC(descr) \
00076               (GC_mark_procs[((descr) >> DS_TAG_BITS) & (MAX_MARK_PROCS-1)])
00077 #   define ENV(descr) \
00078               ((descr) >> (DS_TAG_BITS + LOG_MAX_MARK_PROCS))
00079 #   define MAX_ENV \
00080              (((word)1 << (WORDSZ - DS_TAG_BITS - LOG_MAX_MARK_PROCS)) - 1)
00081 #   define MAKE_PROC(proc_index, env) \
00082            (((((env) << LOG_MAX_MARK_PROCS) | (proc_index)) << DS_TAG_BITS) \
00083            | DS_PROC)
00084 #define DS_PER_OBJECT 3     /* The real descriptor is at the          */
00085                      /* byte displacement from the beginning of the   */
00086                      /* object given by descr & ~DS_TAGS              */
00087                      
00088 typedef struct ms_entry {
00089     word * mse_start;   /* First word of object */
00090     word mse_descr;  /* Descriptor; low order two bits are tags,      */
00091                      /* identifying the upper 30 bits as one of the   */
00092                      /* following:                             */
00093 } mse;
00094 
00095 extern word GC_mark_stack_size;
00096 
00097 extern mse * GC_mark_stack_top;
00098 
00099 extern mse * GC_mark_stack;
00100 
00101 word GC_find_start();
00102 
00103 mse * GC_signal_mark_stack_overflow();
00104 
00105 # ifdef GATHERSTATS
00106 #   define ADD_TO_ATOMIC(sz) GC_atomic_in_use += (sz)
00107 #   define ADD_TO_COMPOSITE(sz) GC_composite_in_use += (sz)
00108 # else
00109 #   define ADD_TO_ATOMIC(sz)
00110 #   define ADD_TO_COMPOSITE(sz)
00111 # endif
00112 
00113 /* Push the object obj with corresponding heap block header hhdr onto        */
00114 /* the mark stack.                                             */
00115 # define PUSH_OBJ(obj, hhdr, mark_stack_top, mark_stack_limit) \
00116 { \
00117     register word _descr = (hhdr) -> hb_descr; \
00118         \
00119     if (_descr == 0) { \
00120        ADD_TO_ATOMIC((hhdr) -> hb_sz); \
00121     } else { \
00122         ADD_TO_COMPOSITE((hhdr) -> hb_sz); \
00123         mark_stack_top++; \
00124         if (mark_stack_top >= mark_stack_limit) { \
00125           mark_stack_top = GC_signal_mark_stack_overflow(mark_stack_top); \
00126         } \
00127         mark_stack_top -> mse_start = (obj); \
00128         mark_stack_top -> mse_descr = _descr; \
00129     } \
00130 }
00131 
00132 #ifdef PRINT_BLACK_LIST
00133 #   define GC_FIND_START(current, hhdr, source) \
00134        GC_find_start(current, hhdr, source)
00135 #else
00136 #   define GC_FIND_START(current, hhdr, source) \
00137        GC_find_start(current, hhdr)
00138 #endif
00139 
00140 /* Push the contents of current onto the mark stack if it is a valid  */
00141 /* ptr to a currently unmarked object.  Mark it.               */
00142 /* If we assumed a standard-conforming compiler, we could probably    */
00143 /* generate the exit_label transparently.                      */
00144 # define PUSH_CONTENTS(current, mark_stack_top, mark_stack_limit, \
00145                      source, exit_label) \
00146 { \
00147     register int displ;  /* Displacement in block; first bytes, then words */ \
00148     register hdr * hhdr; \
00149     register map_entry_type map_entry; \
00150     \
00151     GET_HDR(current,hhdr); \
00152     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { \
00153          current = GC_FIND_START(current, hhdr, (word)source); \
00154          if (current == 0) goto exit_label; \
00155          hhdr = HDR(current); \
00156     } \
00157     displ = HBLKDISPL(current); \
00158     map_entry = MAP_ENTRY((hhdr -> hb_map), displ); \
00159     if (map_entry == OBJ_INVALID) { \
00160         GC_ADD_TO_BLACK_LIST_NORMAL(current, source); goto exit_label; \
00161     } \
00162     displ = BYTES_TO_WORDS(displ); \
00163     displ -= map_entry; \
00164        \
00165     { \
00166         register word * mark_word_addr = hhdr -> hb_marks + divWORDSZ(displ); \
00167         register word mark_word = *mark_word_addr; \
00168         register word mark_bit = (word)1 << modWORDSZ(displ); \
00169           \
00170         if (mark_word & mark_bit) { \
00171              /* Mark bit is already set */ \
00172              goto exit_label; \
00173         } \
00174         *mark_word_addr = mark_word | mark_bit; \
00175     } \
00176     PUSH_OBJ(((word *)(HBLKPTR(current)) + displ), hhdr, \
00177             mark_stack_top, mark_stack_limit) \
00178   exit_label: ; \
00179 }
00180 
00181 #ifdef PRINT_BLACK_LIST
00182 #   define PUSH_ONE_CHECKED(p, ip, source) \
00183        GC_push_one_checked(p, ip, (ptr_t)(source))
00184 #else
00185 #   define PUSH_ONE_CHECKED(p, ip, source) \
00186        GC_push_one_checked(p, ip)
00187 #endif
00188 
00189 /*
00190  * Push a single value onto mark stack. Mark from the object pointed to by p.
00191  * P is considered valid even if it is an interior pointer.
00192  * Previously marked objects are not pushed.  Hence we make progress even
00193  * if the mark stack overflows.
00194  */
00195 # define GC_PUSH_ONE_STACK(p, source) \
00196     if ((ptr_t)(p) >= GC_least_plausible_heap_addr      \
00197         && (ptr_t)(p) < GC_greatest_plausible_heap_addr) {     \
00198         PUSH_ONE_CHECKED(p, TRUE, source);       \
00199     }
00200 
00201 /*
00202  * As above, but interior pointer recognition as for
00203  * normal for heap pointers.
00204  */
00205 # ifdef ALL_INTERIOR_POINTERS
00206 #   define AIP TRUE
00207 # else
00208 #   define AIP FALSE
00209 # endif
00210 # define GC_PUSH_ONE_HEAP(p,source) \
00211     if ((ptr_t)(p) >= GC_least_plausible_heap_addr      \
00212         && (ptr_t)(p) < GC_greatest_plausible_heap_addr) {     \
00213         PUSH_ONE_CHECKED(p,AIP,source);   \
00214     }
00215 
00216 /*
00217  * Mark from one finalizable object using the specified
00218  * mark proc. May not mark the object pointed to by 
00219  * real_ptr. That is the job of the caller, if appropriate
00220  */
00221 # define GC_MARK_FO(real_ptr, mark_proc) \
00222 { \
00223     (*(mark_proc))(real_ptr); \
00224     while (!GC_mark_stack_empty()) GC_mark_from_mark_stack(); \
00225     if (GC_mark_state != MS_NONE) { \
00226         GC_set_mark_bit(real_ptr); \
00227         while (!GC_mark_some((ptr_t)0)); \
00228     } \
00229 }
00230 
00231 extern GC_bool GC_mark_stack_too_small;
00232                             /* We need a larger mark stack.  May be   */
00233                             /* set by client supplied mark routines.*/
00234 
00235 typedef int mark_state_t;   /* Current state of marking, as follows:*/
00236                             /* Used to remember where we are during */
00237                             /* concurrent marking.                    */
00238 
00239                             /* We say something is dirty if it was    */
00240                             /* written since the last time we  */
00241                             /* retrieved dirty bits.  We say it's     */
00242                             /* grungy if it was marked dirty in the   */
00243                             /* last set of bits we retrieved.  */
00244                             
00245                             /* Invariant I: all roots and marked      */
00246                             /* objects p are either dirty, or point */
00247                             /* to objects q that are either marked    */
00248                             /* or a pointer to q appears in a range   */
00249                             /* on the mark stack.                     */
00250 
00251 # define MS_NONE 0          /* No marking in progress. I holds.       */
00252                             /* Mark stack is empty.                   */
00253 
00254 # define MS_PUSH_RESCUERS 1 /* Rescuing objects are currently  */
00255                             /* being pushed.  I holds, except  */
00256                             /* that grungy roots may point to  */
00257                             /* unmarked objects, as may marked */
00258                             /* grungy objects above scan_ptr.  */
00259 
00260 # define MS_PUSH_UNCOLLECTABLE 2
00261                             /* I holds, except that marked            */
00262                             /* uncollectable objects above scan_ptr */
00263                             /* may point to unmarked objects.  */
00264                             /* Roots may point to unmarked objects    */
00265 
00266 # define MS_ROOTS_PUSHED 3  /* I holds, mark stack may be nonempty  */
00267 
00268 # define MS_PARTIALLY_INVALID 4    /* I may not hold, e.g. because of M.S. */
00269                             /* overflow.  However marked heap  */
00270                             /* objects below scan_ptr point to */
00271                             /* marked or stacked objects.             */
00272 
00273 # define MS_INVALID 5              /* I may not hold.                 */
00274 
00275 extern mark_state_t GC_mark_state;
00276 
00277 #endif  /* GC_MARK_H */
00278