Back to index

plt-scheme  4.2.1
gc_mark.h
Go to the documentation of this file.
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