gc_mark.h

00001 /*
00002  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
00003  * Copyright (c) 2001 by Hewlett-Packard Company. All rights reserved.
00004  *
00005  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
00006  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
00007  *
00008  * Permission is hereby granted to use or copy this program
00009  * for any purpose,  provided the above notices are retained on all copies.
00010  * Permission to modify the code and to distribute modified code is granted,
00011  * provided the above notices are retained, and a notice that the code was
00012  * modified is included with the above copyright notice.
00013  *
00014  */
00015 
00016 /*
00017  * This contains interfaces to the GC marker that are likely to be useful to
00018  * clients that provide detailed heap layout information to the collector.
00019  * This interface should not be used by normal C or C++ clients.
00020  * It will be useful to runtimes for other languages.
00021  * 
00022  * This is an experts-only interface!  There are many ways to break the
00023  * collector in subtle ways by using this functionality.
00024  */
00025 #ifndef GC_MARK_H
00026 # define GC_MARK_H
00027 
00028 # ifndef GC_H
00029 #   include "gc.h"
00030 # endif
00031 
00032 /* A client supplied mark procedure.  Returns new mark stack pointer.   */
00033 /* Primary effect should be to push new entries on the mark stack.  */
00034 /* Mark stack pointer values are passed and returned explicitly.    */
00035 /* Global variables decribing mark stack are not necessarily valid. */
00036 /* (This usually saves a few cycles by keeping things in registers.)    */
00037 /* Assumed to scan about GC_PROC_BYTES on average.  If it needs to do   */
00038 /* much more work than that, it should do it in smaller pieces by   */
00039 /* pushing itself back on the mark stack.               */
00040 /* Note that it should always do some work (defined as marking some */
00041 /* objects) before pushing more than one entry on the mark stack.   */
00042 /* This is required to ensure termination in the event of mark stack    */
00043 /* overflows.                               */
00044 /* This procedure is always called with at least one empty entry on the */
00045 /* mark stack.                              */
00046 /* Currently we require that mark procedures look for pointers in a */
00047 /* subset of the places the conservative marker would.  It must be safe */
00048 /* to invoke the normal mark procedure instead.             */
00049 /* WARNING: Such a mark procedure may be invoked on an unused object    */
00050 /* residing on a free list.  Such objects are cleared, except for a */
00051 /* free list link field in the first word.  Thus mark procedures may    */
00052 /* not count on the presence of a type descriptor, and must handle this */
00053 /* case correctly somehow.                      */
00054 # define GC_PROC_BYTES 100
00055 struct GC_ms_entry;
00056 typedef struct GC_ms_entry * (*GC_mark_proc) GC_PROTO((
00057         GC_word * addr, struct GC_ms_entry * mark_stack_ptr,
00058         struct GC_ms_entry * mark_stack_limit, GC_word env));
00059 
00060 # define GC_LOG_MAX_MARK_PROCS 6
00061 # define GC_MAX_MARK_PROCS (1 << GC_LOG_MAX_MARK_PROCS)
00062 
00063 /* In a few cases it's necessary to assign statically known indices to  */
00064 /* certain mark procs.  Thus we reserve a few for well known clients.   */
00065 /* (This is necessary if mark descriptors are compiler generated.)  */
00066 #define GC_RESERVED_MARK_PROCS 8
00067 #   define GC_GCJ_RESERVED_MARK_PROC_INDEX 0
00068 
00069 /* Object descriptors on mark stack or in objects.  Low order two   */
00070 /* bits are tags distinguishing among the following 4 possibilities */
00071 /* for the high order 30 bits.                      */
00072 #define GC_DS_TAG_BITS 2
00073 #define GC_DS_TAGS   ((1 << GC_DS_TAG_BITS) - 1)
00074 #define GC_DS_LENGTH 0  /* The entire word is a length in bytes that    */
00075             /* must be a multiple of 4.         */
00076 #define GC_DS_BITMAP 1  /* 30 (62) bits are a bitmap describing pointer */
00077             /* fields.  The msb is 1 iff the first word */
00078             /* is a pointer.                */
00079             /* (This unconventional ordering sometimes  */
00080             /* makes the marker slightly faster.)       */
00081             /* Zeroes indicate definite nonpointers.  Ones  */
00082             /* indicate possible pointers.          */
00083             /* Only usable if pointers are word aligned.    */
00084 #define GC_DS_PROC   2
00085             /* The objects referenced by this object can be */
00086             /* pushed on the mark stack by invoking     */
00087             /* PROC(descr).  ENV(descr) is passed as the    */
00088             /* last argument.               */
00089 #   define GC_MAKE_PROC(proc_index, env) \
00090         (((((env) << GC_LOG_MAX_MARK_PROCS) \
00091            | (proc_index)) << GC_DS_TAG_BITS) | GC_DS_PROC)
00092 #define GC_DS_PER_OBJECT 3  /* The real descriptor is at the        */
00093             /* byte displacement from the beginning of the  */
00094             /* object given by descr & ~DS_TAGS     */
00095             /* If the descriptor is negative, the real  */
00096             /* descriptor is at (*<object_start>) -     */
00097             /* (descr & ~DS_TAGS) - GC_INDIR_PER_OBJ_BIAS   */
00098             /* The latter alternative can be used if each   */
00099             /* object contains a type descriptor in the */
00100             /* first word.                  */
00101             /* Note that in multithreaded environments  */
00102             /* per object descriptors maust be located in   */
00103             /* either the first two or last two words of    */
00104             /* the object, since only those are guaranteed  */
00105             /* to be cleared while the allocation lock is   */
00106             /* held.                    */
00107 #define GC_INDIR_PER_OBJ_BIAS 0x10
00108             
00109 extern GC_PTR GC_least_plausible_heap_addr;
00110 extern GC_PTR GC_greatest_plausible_heap_addr;
00111             /* Bounds on the heap.  Guaranteed valid    */
00112             /* Likely to include future heap expansion. */
00113 
00114 /* Handle nested references in a custom mark procedure.         */
00115 /* Check if obj is a valid object. If so, ensure that it is marked. */
00116 /* If it was not previously marked, push its contents onto the mark     */
00117 /* stack for future scanning.  The object will then be scanned using    */
00118 /* its mark descriptor.                         */
00119 /* Returns the new mark stack pointer.                  */
00120 /* Handles mark stack overflows correctly.              */
00121 /* Since this marks first, it makes progress even if there are mark */
00122 /* stack overflows.                         */
00123 /* Src is the address of the pointer to obj, which is used only     */
00124 /* for back pointer-based heap debugging.               */
00125 /* It is strongly recommended that most objects be handled without mark */
00126 /* procedures, e.g. with bitmap descriptors, and that mark procedures   */
00127 /* be reserved for exceptional cases.  That will ensure that        */
00128 /* performance of this call is not extremely performance critical.  */
00129 /* (Otherwise we would need to inline GC_mark_and_push completely,  */
00130 /* which would tie the client code to a fixed collector version.)   */
00131 /* Note that mark procedures should explicitly call FIXUP_POINTER() */
00132 /* if required.                             */
00133 struct GC_ms_entry *GC_mark_and_push
00134         GC_PROTO((GC_PTR obj,
00135               struct GC_ms_entry * mark_stack_ptr,
00136                   struct GC_ms_entry * mark_stack_limit, GC_PTR *src));
00137 
00138 #define GC_MARK_AND_PUSH(obj, msp, lim, src) \
00139     (((GC_word)obj >= (GC_word)GC_least_plausible_heap_addr && \
00140       (GC_word)obj <= (GC_word)GC_greatest_plausible_heap_addr)? \
00141       GC_mark_and_push(obj, msp, lim, src) : \
00142       msp)
00143 
00144 extern size_t GC_debug_header_size;
00145        /* The size of the header added to objects allocated through    */
00146        /* the GC_debug routines.                                       */
00147        /* Defined as a variable so that client mark procedures don't   */
00148        /* need to be recompiled for collector version changes.         */
00149 #define GC_USR_PTR_FROM_BASE(p) ((GC_PTR)((char *)(p) + GC_debug_header_size))
00150 
00151 /* And some routines to support creation of new "kinds", e.g. with  */
00152 /* custom mark procedures, by language runtimes.            */
00153 /* The _inner versions assume the caller holds the allocation lock. */
00154 
00155 /* Return a new free list array.    */
00156 void ** GC_new_free_list GC_PROTO((void));
00157 void ** GC_new_free_list_inner GC_PROTO((void));
00158 
00159 /* Return a new kind, as specified. */
00160 int GC_new_kind GC_PROTO((void **free_list, GC_word mark_descriptor_template,
00161                   int add_size_to_descriptor, int clear_new_objects));
00162         /* The last two parameters must be zero or one. */
00163 int GC_new_kind_inner GC_PROTO((void **free_list,
00164                 GC_word mark_descriptor_template,
00165                         int add_size_to_descriptor,
00166                 int clear_new_objects));
00167 
00168 /* Return a new mark procedure identifier, suitable for use as  */
00169 /* the first argument in GC_MAKE_PROC.              */
00170 int GC_new_proc GC_PROTO((GC_mark_proc));
00171 int GC_new_proc_inner GC_PROTO((GC_mark_proc));
00172 
00173 /* Allocate an object of a given kind.  Note that in multithreaded  */
00174 /* contexts, this is usually unsafe for kinds that have the descriptor  */
00175 /* in the object itself, since there is otherwise a window in which */
00176 /* the descriptor is not correct.  Even in the single-threaded case,    */
00177 /* we need to be sure that cleared objects on a free list don't     */
00178 /* cause a GC crash if they are accidentally traced.            */
00179 /* ptr_t */char * GC_generic_malloc GC_PROTO((GC_word lb, int k));
00180 
00181 /* FIXME - Should return void *, but that requires other changes.   */
00182 
00183 typedef void (*GC_describe_type_fn) GC_PROTO((void *p, char *out_buf));
00184                 /* A procedure which            */
00185                 /* produces a human-readable        */
00186                 /* description of the "type" of object  */
00187                 /* p into the buffer out_buf of length  */
00188                 /* GC_TYPE_DESCR_LEN.  This is used by  */
00189                 /* the debug support when printing  */
00190                 /* objects.             */ 
00191                 /* These functions should be as robust  */
00192                 /* as possible, though we do avoid  */
00193                 /* invoking them on objects on the  */
00194                 /* global free list.            */
00195 #   define GC_TYPE_DESCR_LEN 40
00196 
00197 void GC_register_describe_type_fn GC_PROTO((int kind, GC_describe_type_fn knd));
00198                 /* Register a describe_type function    */
00199                 /* to be used when printing objects */
00200                 /* of a particular kind.        */
00201 
00202 #endif  /* GC_MARK_H */
00203