home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / SYSTEM / GC / GC_MARK.H < prev    next >
C/C++ Source or Header  |  1994-11-07  |  9KB  |  241 lines
  1. /*
  2.  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
  3.  *
  4.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  5.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  6.  *
  7.  * Permission is hereby granted to use or copy this program
  8.  * for any purpose,  provided the above notices are retained on all copies.
  9.  * Permission to modify the code and to distribute modified code is granted,
  10.  * provided the above notices are retained, and a notice that the code was
  11.  * modified is included with the above copyright notice.
  12.  *
  13.  */
  14. /* Boehm, November 7, 1994 4:56 pm PST */
  15.  
  16. /*
  17.  * Declarations of mark stack.  Needed by marker and client supplied mark
  18.  * routines.  To be included after gc_priv.h.
  19.  */
  20. #ifndef GC_MARK_H
  21. # define GC_MARK_H
  22.  
  23. /* A client supplied mark procedure.  Returns new mark stack pointer.    */
  24. /* Primary effect should be to push new entries on the mark stack.    */
  25. /* Mark stack pointer values are passed and returned explicitly.    */
  26. /* Global variables decribing mark stack are not necessarily valid.    */
  27. /* (This usually saves a few cycles by keeping things in registers.)    */
  28. /* Assumed to scan about PROC_BYTES on average.  If it needs to do    */
  29. /* much more work than that, it should do it in smaller pieces by    */
  30. /* pushing itself back on the mark stack.                */
  31. /* Note that it should always do some work (defined as marking some    */
  32. /* objects) before pushing more than one entry on the mark stack.    */
  33. /* This is required to ensure termination in the event of mark stack    */
  34. /* overflows.                                */
  35. /* This procedure is always called with at least one empty entry on the */
  36. /* mark stack.                                */
  37. /* Currently we require that mark procedures look for pointers in a    */
  38. /* subset of the places the conservative marker would.  It must be safe    */
  39. /* to invoke the normal mark procedure instead.                */
  40. # define PROC_BYTES 100
  41. typedef struct ms_entry * (*mark_proc)(/* word * addr, mark_stack_ptr,
  42.                       mark_stack_limit, env */);
  43.                       
  44. # define LOG_MAX_MARK_PROCS 6
  45. # define MAX_MARK_PROCS (1 << LOG_MAX_MARK_PROCS)
  46. extern mark_proc GC_mark_procs[MAX_MARK_PROCS];
  47. extern word GC_n_mark_procs;
  48.  
  49. /* Object descriptors on mark stack or in objects.  Low order two    */
  50. /* bits are tags distinguishing among the following 4 possibilities    */
  51. /* for the high order 30 bits.                        */
  52. #define DS_TAG_BITS 2
  53. #define DS_TAGS   ((1 << DS_TAG_BITS) - 1)
  54. #define DS_LENGTH 0    /* The entire word is a length in bytes that    */
  55.             /* must be a multiple of 4.            */
  56. #define DS_BITMAP 1    /* 30 bits are a bitmap describing pointer    */
  57.             /* fields.  The msb is 1 iff the first word    */
  58.             /* is a pointer.                */
  59.             /* (This unconventional ordering sometimes    */
  60.             /* makes the marker slightly faster.)        */
  61.             /* Zeroes indicate definite nonpointers.  Ones    */
  62.             /* indicate possible pointers.            */
  63.             /* Only usable if pointers are word aligned.    */
  64. #   define BITMAP_BITS (WORDSZ - DS_TAG_BITS)
  65. #define DS_PROC   2
  66.             /* The objects referenced by this object can be */
  67.             /* pushed on the mark stack by invoking        */
  68.             /* PROC(descr).  ENV(descr) is passed as the    */
  69.             /* last argument.                */
  70. #   define PROC(descr) \
  71.         (GC_mark_procs[((descr) >> DS_TAG_BITS) & (MAX_MARK_PROCS-1)])
  72. #   define ENV(descr) \
  73.         ((descr) >> (DS_TAG_BITS + LOG_MAX_MARK_PROCS))
  74. #   define MAX_ENV \
  75.             (((word)1 << (WORDSZ - DS_TAG_BITS - LOG_MAX_MARK_PROCS)) - 1)
  76. #   define MAKE_PROC(proc_index, env) \
  77.         (((((env) << LOG_MAX_MARK_PROCS) | (proc_index)) << DS_TAG_BITS) \
  78.         | DS_PROC)
  79. #define DS_PER_OBJECT 3    /* The real descriptor is at the        */
  80.             /* byte displacement from the beginning of the    */
  81.             /* object given by descr & ~DS_TAGS        */
  82.             
  83. typedef struct ms_entry {
  84.     word * mse_start;   /* First word of object */
  85.     word mse_descr;    /* Descriptor; low order two bits are tags,    */
  86.                 /* identifying the upper 30 bits as one of the    */
  87.                 /* following:                    */
  88. } mse;
  89.  
  90. extern word GC_mark_stack_size;
  91.  
  92. extern mse * GC_mark_stack_top;
  93.  
  94. extern mse * GC_mark_stack;
  95.  
  96. word GC_find_start();
  97.  
  98. mse * GC_signal_mark_stack_overflow();
  99.  
  100. # ifdef GATHERSTATS
  101. #   define ADD_TO_ATOMIC(sz) GC_atomic_in_use += (sz)
  102. #   define ADD_TO_COMPOSITE(sz) GC_composite_in_use += (sz)
  103. # else
  104. #   define ADD_TO_ATOMIC(sz)
  105. #   define ADD_TO_COMPOSITE(sz)
  106. # endif
  107.  
  108. /* Push the object obj with corresponding heap block header hhdr onto     */
  109. /* the mark stack.                            */
  110. # define PUSH_OBJ(obj, hhdr, mark_stack_top, mark_stack_limit) \
  111. { \
  112.     register word _descr = (hhdr) -> hb_descr; \
  113.         \
  114.     if (_descr == 0) { \
  115.         ADD_TO_ATOMIC((hhdr) -> hb_sz); \
  116.     } else { \
  117.         ADD_TO_COMPOSITE((hhdr) -> hb_sz); \
  118.         mark_stack_top++; \
  119.         if (mark_stack_top >= mark_stack_limit) { \
  120.           mark_stack_top = GC_signal_mark_stack_overflow(mark_stack_top); \
  121.         } \
  122.         mark_stack_top -> mse_start = (obj); \
  123.         mark_stack_top -> mse_descr = _descr; \
  124.     } \
  125. }
  126.  
  127. /* Push the contenst of current onto the mark stack if it is a valid    */
  128. /* ptr to a currently unmarked object.  Mark it.            */
  129. # define PUSH_CONTENTS(current, mark_stack_top, mark_stack_limit) \
  130. { \
  131.     register int displ;  /* Displacement in block; first bytes, then words */ \
  132.     register hdr * hhdr; \
  133.     register map_entry_type map_entry; \
  134.     \
  135.     GET_HDR(current,hhdr); \
  136.     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { \
  137.          current = GC_find_start(current, hhdr); \
  138.          if (current == 0) continue; \
  139.          hhdr = HDR(current); \
  140.     } \
  141.     displ = HBLKDISPL(current); \
  142.     map_entry = MAP_ENTRY((hhdr -> hb_map), displ); \
  143.     if (map_entry == OBJ_INVALID) { \
  144.         GC_ADD_TO_BLACK_LIST_NORMAL(current); continue; \
  145.     } \
  146.     displ = BYTES_TO_WORDS(displ); \
  147.     displ -= map_entry; \
  148.     \
  149.     { \
  150.         register word * mark_word_addr = hhdr -> hb_marks + divWORDSZ(displ); \
  151.         register word mark_word = *mark_word_addr; \
  152.         register word mark_bit = (word)1 << modWORDSZ(displ); \
  153.           \
  154.         if (mark_word & mark_bit) { \
  155.           /* Mark bit is already set */ \
  156.           continue; \
  157.         } \
  158.         *mark_word_addr = mark_word | mark_bit; \
  159.     } \
  160.     PUSH_OBJ(((word *)(HBLKPTR(current)) + displ), hhdr, \
  161.              mark_stack_top, mark_stack_limit) \
  162. }
  163.  
  164. /*
  165.  * Push a single value onto mark stack. Mark from the object pointed to by p.
  166.  * GC_push_one is normally called by GC_push_regs, and thus must be defined.
  167.  * P is considered valid even if it is an interior pointer.
  168.  * Previously marked objects are not pushed.  Hence we make progress even
  169.  * if the mark stack overflows.
  170.  */
  171. # define GC_PUSH_ONE_STACK(p) \
  172.     if ((ptr_t)(p) >= GC_least_plausible_heap_addr     \
  173.      && (ptr_t)(p) < GC_greatest_plausible_heap_addr) {    \
  174.      GC_push_one_checked(p,TRUE);    \
  175.     }
  176.  
  177. /*
  178.  * As above, but interior pointer recognition as for
  179.  * normal for heap pointers.
  180.  */
  181. # ifdef ALL_INTERIOR_POINTERS
  182. #   define AIP TRUE
  183. # else
  184. #   define AIP FALSE
  185. # endif
  186. # define GC_PUSH_ONE_HEAP(p) \
  187.     if ((ptr_t)(p) >= GC_least_plausible_heap_addr     \
  188.      && (ptr_t)(p) < GC_greatest_plausible_heap_addr) {    \
  189.      GC_push_one_checked(p,AIP);    \
  190.     }
  191.  
  192.  
  193.  
  194. extern bool GC_mark_stack_too_small;
  195.                 /* We need a larger mark stack.  May be    */
  196.                 /* set by client supplied mark routines.*/
  197.  
  198. typedef int mark_state_t;    /* Current state of marking, as follows:*/
  199.                 /* Used to remember where we are during */
  200.                 /* concurrent marking.            */
  201.  
  202.                 /* We say something is dirty if it was    */
  203.                 /* written since the last time we    */
  204.                 /* retrieved dirty bits.  We say it's     */
  205.                 /* grungy if it was marked dirty in the    */
  206.                 /* last set of bits we retrieved.    */
  207.                 
  208.                 /* Invariant I: all roots and marked    */
  209.                 /* objects p are either dirty, or point */
  210.                 /* objects q that are either marked or    */
  211.                 /* a pointer to q appears in a range    */
  212.                 /* on the mark stack.            */
  213.  
  214. # define MS_NONE 0        /* No marking in progress. I holds.    */
  215.                 /* Mark stack is empty.            */
  216.  
  217. # define MS_PUSH_RESCUERS 1    /* Rescuing objects are currently     */
  218.                 /* being pushed.  I holds, except    */
  219.                 /* that grungy roots may point to     */
  220.                 /* unmarked objects, as may marked    */
  221.                 /* grungy objects above scan_ptr.    */
  222.  
  223. # define MS_PUSH_UNCOLLECTABLE 2
  224.                 /* I holds, except that marked         */
  225.                 /* uncollectable objects above scan_ptr */
  226.                 /* may point to unmarked objects.    */
  227.                 /* Roots may point to unmarked objects    */
  228.  
  229. # define MS_ROOTS_PUSHED 3    /* I holds, mark stack may be nonempty  */
  230.  
  231. # define MS_PARTIALLY_INVALID 4    /* I may not hold, e.g. because of M.S. */
  232.                 /* overflow.  However marked heap    */
  233.                 /* objects below scan_ptr point to    */
  234.                 /* marked or stacked objects.        */
  235.  
  236. # define MS_INVALID 5        /* I may not hold.            */
  237.  
  238. extern mark_state_t GC_mark_state;
  239.  
  240. #endif  /* GC_MARK_H */
  241.