boehm-gc/include/gc_mark.h

   1 /*
   2  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
   3  * Copyright (c) 2001 by Hewlett-Packard Company. All rights reserved.
   4  *
   5  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   6  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   7  *
   8  * Permission is hereby granted to use or copy this program
   9  * for any purpose,  provided the above notices are retained on all copies.
  10  * Permission to modify the code and to distribute modified code is granted,
  11  * provided the above notices are retained, and a notice that the code was
  12  * modified is included with the above copyright notice.
  13  *
  14  */
  15
  16 /*
  17  * This contains interfaces to the GC marker that are likely to be useful to
  18  * clients that provide detailed heap layout information to the collector.
  19  * This interface should not be used by normal C or C++ clients.
  20  * It will be useful to runtimes for other languages.
  21  *
  22  * This is an experts-only interface!  There are many ways to break the
  23  * collector in subtle ways by using this functionality.
  24  */
  25 #ifndef GC_MARK_H
  26 # define GC_MARK_H
  27
  28 # ifndef GC_H
  29 #   include "gc.h"
  30 # endif
  31
  32 /* A client supplied mark procedure.  Returns new mark stack pointer.   */
  33 /* Primary effect should be to push new entries on the mark stack.      */
  34 /* Mark stack pointer values are passed and returned explicitly.        */
  35 /* Global variables decribing mark stack are not necessarily valid.     */
  36 /* (This usually saves a few cycles by keeping things in registers.)    */
  37 /* Assumed to scan about GC_PROC_BYTES on average.  If it needs to do   */
  38 /* much more work than that, it should do it in smaller pieces by       */
  39 /* pushing itself back on the mark stack.                               */
  40 /* Note that it should always do some work (defined as marking some     */
  41 /* objects) before pushing more than one entry on the mark stack.       */
  42 /* This is required to ensure termination in the event of mark stack    */
  43 /* overflows.                                                           */
  44 /* This procedure is always called with at least one empty entry on the */
  45 /* mark stack.                                                          */
  46 /* Currently we require that mark procedures look for pointers in a     */
  47 /* subset of the places the conservative marker would.  It must be safe */
  48 /* to invoke the normal mark procedure instead.                         */
  49 /* WARNING: Such a mark procedure may be invoked on an unused object    */
  50 /* residing on a free list.  Such objects are cleared, except for a     */
  51 /* free list link field in the first word.  Thus mark procedures may    */
  52 /* not count on the presence of a type descriptor, and must handle this */
  53 /* case correctly somehow.                                              */
  54 # define GC_PROC_BYTES 100
  55 struct GC_ms_entry;
  56 typedef struct GC_ms_entry * (*GC_mark_proc) GC_PROTO((
  57                 GC_word * addr, struct GC_ms_entry * mark_stack_ptr,
  58                 struct GC_ms_entry * mark_stack_limit, GC_word env));
  59
  60 # define GC_LOG_MAX_MARK_PROCS 6
  61 # define GC_MAX_MARK_PROCS (1 << GC_LOG_MAX_MARK_PROCS)
  62
  63 /* In a few cases it's necessary to assign statically known indices to  */
  64 /* certain mark procs.  Thus we reserve a few for well known clients.   */
  65 /* (This is necessary if mark descriptors are compiler generated.)      */
  66 #define GC_RESERVED_MARK_PROCS 8
  67 #   define GC_GCJ_RESERVED_MARK_PROC_INDEX 0
  68
  69 /* Object descriptors on mark stack or in objects.  Low order two       */
  70 /* bits are tags distinguishing among the following 4 possibilities     */
  71 /* for the high order 30 bits.                                          */
  72 #define GC_DS_TAG_BITS 2
  73 #define GC_DS_TAGS   ((1 << GC_DS_TAG_BITS) - 1)
  74 #define GC_DS_LENGTH 0  /* The entire word is a length in bytes that    */
  75                         /* must be a multiple of 4.                     */
  76 #define GC_DS_BITMAP 1  /* 30 (62) bits are a bitmap describing pointer */
  77                         /* fields.  The msb is 1 iff the first word     */
  78                         /* is a pointer.                                */
  79                         /* (This unconventional ordering sometimes      */
  80                         /* makes the marker slightly faster.)           */
  81                         /* Zeroes indicate definite nonpointers.  Ones  */
  82                         /* indicate possible pointers.                  */
  83                         /* Only usable if pointers are word aligned.    */
  84 #define GC_DS_PROC   2
  85                         /* The objects referenced by this object can be */
  86                         /* pushed on the mark stack by invoking         */
  87                         /* PROC(descr).  ENV(descr) is passed as the    */
  88                         /* last argument.                               */
  89 #   define GC_MAKE_PROC(proc_index, env) \
  90             (((((env) << GC_LOG_MAX_MARK_PROCS) \
  91                | (proc_index)) << GC_DS_TAG_BITS) | GC_DS_PROC)
  92 #define GC_DS_PER_OBJECT 3  /* The real descriptor is at the            */
  93                         /* byte displacement from the beginning of the  */
  94                         /* object given by descr & ~DS_TAGS             */
  95                         /* If the descriptor is negative, the real      */
  96                         /* descriptor is at (*<object_start>) -         */
  97                         /* (descr & ~DS_TAGS) - GC_INDIR_PER_OBJ_BIAS   */
  98                         /* The latter alternative can be used if each   */
  99                         /* object contains a type descriptor in the     */
 100                         /* first word.                                  */
 101                         /* Note that in multithreaded environments      */
 102                         /* per object descriptors maust be located in   */
 103                         /* either the first two or last two words of    */
 104                         /* the object, since only those are guaranteed  */
 105                         /* to be cleared while the allocation lock is   */
 106                         /* held.                                        */
 107 #define GC_INDIR_PER_OBJ_BIAS 0x10
 108
 109 extern GC_PTR GC_least_plausible_heap_addr;
 110 extern GC_PTR GC_greatest_plausible_heap_addr;
 111                         /* Bounds on the heap.  Guaranteed valid        */
 112                         /* Likely to include future heap expansion.     */
 113
 114 /* Handle nested references in a custom mark procedure.                 */
 115 /* Check if obj is a valid object. If so, ensure that it is marked.     */
 116 /* If it was not previously marked, push its contents onto the mark     */
 117 /* stack for future scanning.  The object will then be scanned using    */
 118 /* its mark descriptor.                                                 */
 119 /* Returns the new mark stack pointer.                                  */
 120 /* Handles mark stack overflows correctly.                              */
 121 /* Since this marks first, it makes progress even if there are mark     */
 122 /* stack overflows.                                                     */
 123 /* Src is the address of the pointer to obj, which is used only         */
 124 /* for back pointer-based heap debugging.                               */
 125 /* It is strongly recommended that most objects be handled without mark */
 126 /* procedures, e.g. with bitmap descriptors, and that mark procedures   */
 127 /* be reserved for exceptional cases.  That will ensure that            */
 128 /* performance of this call is not extremely performance critical.      */
 129 /* (Otherwise we would need to inline GC_mark_and_push completely,      */
 130 /* which would tie the client code to a fixed collector version.)       */
 131 /* Note that mark procedures should explicitly call FIXUP_POINTER()     */
 132 /* if required.                                                         */
 133 struct GC_ms_entry *GC_mark_and_push
 134                 GC_PROTO((GC_PTR obj,
 135                           struct GC_ms_entry * mark_stack_ptr,
 136                           struct GC_ms_entry * mark_stack_limit, GC_PTR *src));
 137
 138 #define GC_MARK_AND_PUSH(obj, msp, lim, src) \
 139         (((GC_word)obj >= (GC_word)GC_least_plausible_heap_addr && \
 140           (GC_word)obj <= (GC_word)GC_greatest_plausible_heap_addr)? \
 141           GC_mark_and_push(obj, msp, lim, src) : \
 142           msp)
 143
 144 extern size_t GC_debug_header_size;
 145        /* The size of the header added to objects allocated through    */
 146        /* the GC_debug routines.                                       */
 147        /* Defined as a variable so that client mark procedures don't   */
 148        /* need to be recompiled for collector version changes.         */
 149 #define GC_USR_PTR_FROM_BASE(p) ((GC_PTR)((char *)(p) + GC_debug_header_size))
 150
 151 /* And some routines to support creation of new "kinds", e.g. with      */
 152 /* custom mark procedures, by language runtimes.                        */
 153 /* The _inner versions assume the caller holds the allocation lock.     */
 154
 155 /* Return a new free list array.        */
 156 void ** GC_new_free_list GC_PROTO((void));
 157 void ** GC_new_free_list_inner GC_PROTO((void));
 158
 159 /* Return a new kind, as specified. */
 160 int GC_new_kind GC_PROTO((void **free_list, GC_word mark_descriptor_template,
 161                           int add_size_to_descriptor, int clear_new_objects));
 162                 /* The last two parameters must be zero or one. */
 163 int GC_new_kind_inner GC_PROTO((void **free_list,
 164                                 GC_word mark_descriptor_template,
 165                                 int add_size_to_descriptor,
 166                                 int clear_new_objects));
 167
 168 /* Return a new mark procedure identifier, suitable for use as  */
 169 /* the first argument in GC_MAKE_PROC.                          */
 170 int GC_new_proc GC_PROTO((GC_mark_proc));
 171 int GC_new_proc_inner GC_PROTO((GC_mark_proc));
 172
 173 /* Allocate an object of a given kind.  Note that in multithreaded      */
 174 /* contexts, this is usually unsafe for kinds that have the descriptor  */
 175 /* in the object itself, since there is otherwise a window in which     */
 176 /* the descriptor is not correct.  Even in the single-threaded case,    */
 177 /* we need to be sure that cleared objects on a free list don't         */
 178 /* cause a GC crash if they are accidentally traced.                    */
 179 /* ptr_t */char * GC_generic_malloc GC_PROTO((GC_word lb, int k));
 180
 181 /* FIXME - Should return void *, but that requires other changes.       */
 182
 183 typedef void (*GC_describe_type_fn) GC_PROTO((void *p, char *out_buf));
 184                                 /* A procedure which                    */
 185                                 /* produces a human-readable            */
 186                                 /* description of the "type" of object  */
 187                                 /* p into the buffer out_buf of length  */
 188                                 /* GC_TYPE_DESCR_LEN.  This is used by  */
 189                                 /* the debug support when printing      */
 190                                 /* objects.                             */
 191                                 /* These functions should be as robust  */
 192                                 /* as possible, though we do avoid      */
 193                                 /* invoking them on objects on the      */
 194                                 /* global free list.                    */
 195 #       define GC_TYPE_DESCR_LEN 40
 196
 197 void GC_register_describe_type_fn GC_PROTO((int kind, GC_describe_type_fn knd));
 198                                 /* Register a describe_type function    */
 199                                 /* to be used when printing objects     */
 200                                 /* of a particular kind.                */
 201
 202 #endif  /* GC_MARK_H */
 203