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  * Note that this file is not "namespace-clean", i.e. it introduces names
  23  * not prefixed with GC_, which may collide with the client's names.  It
  24  * should be included only in those few places that directly provide
  25  * information to the collector.
  26  */
  27 #ifndef GC_MARK_H
  28 # define GC_MARK_H
  29
  30 # ifndef GC_H
  31 #   include "gc.h"
  32 # endif
  33
  34 /* A client supplied mark procedure.  Returns new mark stack pointer.   */
  35 /* Primary effect should be to push new entries on the mark stack.      */
  36 /* Mark stack pointer values are passed and returned explicitly.        */
  37 /* Global variables decribing mark stack are not necessarily valid.     */
  38 /* (This usually saves a few cycles by keeping things in registers.)    */
  39 /* Assumed to scan about GC_PROC_BYTES on average.  If it needs to do   */
  40 /* much more work than that, it should do it in smaller pieces by       */
  41 /* pushing itself back on the mark stack.                               */
  42 /* Note that it should always do some work (defined as marking some     */
  43 /* objects) before pushing more than one entry on the mark stack.       */
  44 /* This is required to ensure termination in the event of mark stack    */
  45 /* overflows.                                                           */
  46 /* This procedure is always called with at least one empty entry on the */
  47 /* mark stack.                                                          */
  48 /* Currently we require that mark procedures look for pointers in a     */
  49 /* subset of the places the conservative marker would.  It must be safe */
  50 /* to invoke the normal mark procedure instead.                         */
  51 /* WARNING: Such a mark procedure may be invoked on an unused object    */
  52 /* residing on a free list.  Such objects are cleared, except for a     */
  53 /* free list link field in the first word.  Thus mark procedures may    */
  54 /* not count on the presence of a type descriptor, and must handle this */
  55 /* case correctly somehow.                                              */
  56 # define GC_PROC_BYTES 100
  57 struct GC_ms_entry;
  58 typedef struct GC_ms_entry * (*GC_mark_proc) GC_PROTO((
  59                 GC_word * addr, struct GC_ms_entry * mark_stack_ptr,
  60                 struct GC_ms_entry * mark_stack_limit, GC_word env));
  61
  62 # define GC_LOG_MAX_MARK_PROCS 6
  63 # define GC_MAX_MARK_PROCS (1 << GC_LOG_MAX_MARK_PROCS)
  64
  65 /* In a few cases it's necessary to assign statically known indices to  */
  66 /* certain mark procs.  Thus we reserve a few for well known clients.   */
  67 /* (This is necessary if mark descriptors are compiler generated.)      */
  68 #define GC_RESERVED_MARK_PROCS 8
  69 #   define GC_GCJ_RESERVED_MARK_PROC_INDEX 0
  70
  71 /* Object descriptors on mark stack or in objects.  Low order two       */
  72 /* bits are tags distinguishing among the following 4 possibilities     */
  73 /* for the high order 30 bits.                                          */
  74 #define GC_DS_TAG_BITS 2
  75 #define GC_DS_TAGS   ((1 << GC_DS_TAG_BITS) - 1)
  76 #define GC_DS_LENGTH 0  /* The entire word is a length in bytes that    */
  77                         /* must be a multiple of 4.                     */
  78 #define GC_DS_BITMAP 1  /* 30 (62) bits are a bitmap describing pointer */
  79                         /* fields.  The msb is 1 iff the first word     */
  80                         /* is a pointer.                                */
  81                         /* (This unconventional ordering sometimes      */
  82                         /* makes the marker slightly faster.)           */
  83                         /* Zeroes indicate definite nonpointers.  Ones  */
  84                         /* indicate possible pointers.                  */
  85                         /* Only usable if pointers are word aligned.    */
  86 #define GC_DS_PROC   2
  87                         /* The objects referenced by this object can be */
  88                         /* pushed on the mark stack by invoking         */
  89                         /* PROC(descr).  ENV(descr) is passed as the    */
  90                         /* last argument.                               */
  91 #   define GC_MAKE_PROC(proc_index, env) \
  92             (((((env) << GC_LOG_MAX_MARK_PROCS) \
  93                | (proc_index)) << GC_DS_TAG_BITS) | GC_DS_PROC)
  94 #define GC_DS_PER_OBJECT 3  /* The real descriptor is at the            */
  95                         /* byte displacement from the beginning of the  */
  96                         /* object given by descr & ~DS_TAGS             */
  97                         /* If the descriptor is negative, the real      */
  98                         /* descriptor is at (*<object_start>) -         */
  99                         /* (descr & ~DS_TAGS) - GC_INDIR_PER_OBJ_BIAS   */
 100                         /* The latter alternative can be used if each   */
 101                         /* object contains a type descriptor in the     */
 102                         /* first word.                                  */
 103                         /* Note that in multithreaded environments      */
 104                         /* per object descriptors maust be located in   */
 105                         /* either the first two or last two words of    */
 106                         /* the object, since only those are guaranteed  */
 107                         /* to be cleared while the allocation lock is   */
 108                         /* held.                                        */
 109 #define GC_INDIR_PER_OBJ_BIAS 0x10
 110
 111 extern GC_PTR GC_least_plausible_heap_addr;
 112 extern GC_PTR GC_greatest_plausible_heap_addr;
 113                         /* Bounds on the heap.  Guaranteed valid        */
 114                         /* Likely to include future heap expansion.     */
 115
 116 /* Handle nested references in a custom mark procedure.                 */
 117 /* Check if obj is a valid object. If so, ensure that it is marked.     */
 118 /* If it was not previously marked, push its contents onto the mark     */
 119 /* stack for future scanning.  The object will then be scanned using    */
 120 /* its mark descriptor.                                                 */
 121 /* Returns the new mark stack pointer.                                  */
 122 /* Handles mark stack overflows correctly.                              */
 123 /* Since this marks first, it makes progress even if there are mark     */
 124 /* stack overflows.                                                     */
 125 /* Src is the address of the pointer to obj, which is used only         */
 126 /* for back pointer-based heap debugging.                               */
 127 /* It is strongly recommended that most objects be handled without mark */
 128 /* procedures, e.g. with bitmap descriptors, and that mark procedures   */
 129 /* be reserved for exceptional cases.  That will ensure that            */
 130 /* performance of this call is not extremely performance critical.      */
 131 /* (Otherwise we would need to inline GC_mark_and_push completely,      */
 132 /* which would tie the client code to a fixed colllector version.)      */
 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 #endif  /* GC_MARK_H */
 145