home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / SYSTEM / GC / MARK.C < prev    next >
Text File  |  1995-01-28  |  31KB  |  1,057 lines
  1.  
  2. /*
  3.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  4.  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
  5.  *
  6.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  7.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  8.  *
  9.  * Permission is hereby granted to use or copy this program
  10.  * for any purpose,  provided the above notices are retained on all copies.
  11.  * Permission to modify the code and to distribute modified code is granted,
  12.  * provided the above notices are retained, and a notice that the code was
  13.  * modified is included with the above copyright notice.
  14.  *
  15.  */
  16.  
  17.  
  18. # include <stdio.h>
  19. # include "gc_priv.h"
  20. # include "gc_mark.h"
  21.  
  22. /* We put this here to minimize the risk of inlining. */
  23. /*VARARGS*/
  24. void GC_noop() {}
  25.  
  26. mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0};
  27. word GC_n_mark_procs = 0;
  28.  
  29. /* Initialize GC_obj_kinds properly and standard free lists properly.      */
  30. /* This must be done statically since they may be accessed before     */
  31. /* GC_init is called.                            */
  32. /* It's done here, since we need to deal with mark descriptors.        */
  33. struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
  34. /* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */,
  35.         0 | DS_LENGTH, FALSE, FALSE },
  36. /* NORMAL  */ { &GC_objfreelist[0], 0,
  37. #        ifdef ADD_BYTE_AT_END
  38.         (word)(WORDS_TO_BYTES(-1)) | DS_LENGTH,
  39. #        else
  40.         0 | DS_LENGTH,
  41. #        endif
  42.         TRUE /* add length to descr */, TRUE },
  43. /* UNCOLLECTABLE */
  44.           { &GC_uobjfreelist[0], 0,
  45.         0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
  46. # ifdef STUBBORN_ALLOC
  47. /*STUBBORN*/ { &GC_sobjfreelist[0], 0,
  48.         0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
  49. # endif
  50. };
  51.  
  52. # ifdef STUBBORN_ALLOC
  53.   int GC_n_kinds = 4;
  54. # else
  55.   int GC_n_kinds = 3;
  56. # endif
  57.  
  58.  
  59. # define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
  60.         /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a     */
  61.         /* multiple of HBLKSIZE.                */
  62.  
  63. /*
  64.  * Limits of stack for GC_mark routine.
  65.  * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
  66.  * need to be marked from.
  67.  */
  68.  
  69. word GC_n_rescuing_pages;    /* Number of dirty pages we marked from */
  70.                 /* excludes ptrfree pages, etc.        */
  71.  
  72. mse * GC_mark_stack;
  73.  
  74. word GC_mark_stack_size = 0;
  75.  
  76. mse * GC_mark_stack_top;
  77.  
  78. static struct hblk * scan_ptr;
  79.  
  80. mark_state_t GC_mark_state = MS_NONE;
  81.  
  82. bool GC_mark_stack_too_small = FALSE;
  83.  
  84. bool GC_objects_are_marked = FALSE;    /* Are there collectable marked    */
  85.                     /* objects in the heap?        */
  86.  
  87. bool GC_collection_in_progress()
  88. {
  89.     return(GC_mark_state != MS_NONE);
  90. }
  91.  
  92. /* clear all mark bits in the header */
  93. void GC_clear_hdr_marks(hhdr)
  94. register hdr * hhdr;
  95. {
  96.     BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
  97. }
  98.  
  99. /*
  100.  * Clear all mark bits associated with block h.
  101.  */
  102. /*ARGSUSED*/
  103. static void clear_marks_for_block(h, dummy)
  104. struct hblk *h;
  105. word dummy;
  106. {
  107.     register hdr * hhdr = HDR(h);
  108.     
  109.     if (hhdr -> hb_obj_kind == UNCOLLECTABLE) return;
  110.         /* Mark bit for these is cleared only once the object is     */
  111.         /* explicitly deallocated.  This either frees the block, or    */
  112.         /* the bit is cleared once the object is on the free list.    */
  113.     GC_clear_hdr_marks(hhdr);
  114. }
  115.  
  116. /* Slow but general routines for setting/clearing/asking about mark bits */
  117. void GC_set_mark_bit(p)
  118. ptr_t p;
  119. {
  120.     register struct hblk *h = HBLKPTR(p);
  121.     register hdr * hhdr = HDR(h);
  122.     register int word_no = (word *)p - (word *)h;
  123.     
  124.     set_mark_bit_from_hdr(hhdr, word_no);
  125. }
  126.  
  127. void GC_clear_mark_bit(p)
  128. ptr_t p;
  129. {
  130.     register struct hblk *h = HBLKPTR(p);
  131.     register hdr * hhdr = HDR(h);
  132.     register int word_no = (word *)p - (word *)h;
  133.     
  134.     clear_mark_bit_from_hdr(hhdr, word_no);
  135. }
  136.  
  137. bool GC_is_marked(p)
  138. ptr_t p;
  139. {
  140.     register struct hblk *h = HBLKPTR(p);
  141.     register hdr * hhdr = HDR(h);
  142.     register int word_no = (word *)p - (word *)h;
  143.     
  144.     return(mark_bit_from_hdr(hhdr, word_no));
  145. }
  146.  
  147.  
  148. /*
  149.  * Clear mark bits in all allocated heap blocks.  This invalidates
  150.  * the marker invariant, and sets GC_mark_state to reflect this.
  151.  * (This implicitly starts marking to reestablish the
  152.  */
  153. void GC_clear_marks()
  154. {
  155.     GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
  156.     GC_objects_are_marked = FALSE;
  157.     GC_mark_state = MS_INVALID;
  158.     scan_ptr = 0;
  159. #   ifdef GATHERSTATS
  160.     /* Counters reflect currently marked objects: reset here */
  161.         GC_composite_in_use = 0;
  162.         GC_atomic_in_use = 0;
  163. #   endif
  164.  
  165. }
  166.  
  167. /* Initiate full marking.    */
  168. void GC_initiate_full()
  169. {
  170. #   ifdef PRINTSTATS
  171.     GC_printf2("***>Full mark for collection %lu after %ld allocd bytes\n",
  172.           (unsigned long) GC_gc_no+1,
  173.              (long)WORDS_TO_BYTES(GC_words_allocd));
  174. #   endif
  175.     GC_promote_black_lists();
  176.     GC_reclaim_or_delete_all();
  177.     GC_clear_marks();
  178.     GC_read_dirty();
  179. #   ifdef STUBBORN_ALLOC
  180.         GC_read_changed();
  181. #   endif
  182. #   ifdef CHECKSUMS
  183.     {
  184.         extern void GC_check_dirty();
  185.         
  186.         GC_check_dirty();
  187.     }
  188. #   endif
  189. #   ifdef GATHERSTATS
  190.     GC_n_rescuing_pages = 0;
  191. #   endif
  192. }
  193.  
  194. /* Initiate partial marking.    */
  195. /*ARGSUSED*/
  196. void GC_initiate_partial()
  197. {
  198.     if (GC_dirty_maintained) GC_read_dirty();
  199. #   ifdef STUBBORN_ALLOC
  200.         GC_read_changed();
  201. #   endif
  202. #   ifdef CHECKSUMS
  203.     {
  204.         extern void GC_check_dirty();
  205.         
  206.         if (GC_dirty_maintained) GC_check_dirty();
  207.     }
  208. #   endif
  209. #   ifdef GATHERSTATS
  210.     GC_n_rescuing_pages = 0;
  211. #   endif
  212.     if (GC_mark_state == MS_NONE) {
  213.         GC_mark_state = MS_PUSH_RESCUERS;
  214.     } else if (GC_mark_state != MS_INVALID) {
  215.         ABORT("unexpected state");
  216.     } /* else this is really a full collection, and mark    */
  217.       /* bits are invalid.                    */
  218.     scan_ptr = 0;
  219. }
  220.  
  221.  
  222. static void alloc_mark_stack();
  223.  
  224. /* Perform a small amount of marking.            */
  225. /* We try to touch roughly a page of memory.        */
  226. /* Return TRUE if we just finished a mark phase.    */
  227. bool GC_mark_some()
  228. {
  229.     switch(GC_mark_state) {
  230.         case MS_NONE:
  231.             return(FALSE);
  232.             
  233.         case MS_PUSH_RESCUERS:
  234.             if (GC_mark_stack_top
  235.                 >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
  236.                 GC_mark_from_mark_stack();
  237.                 return(FALSE);
  238.             } else {
  239.                 scan_ptr = GC_push_next_marked_dirty(scan_ptr);
  240.                 if (scan_ptr == 0) {
  241. #            ifdef PRINTSTATS
  242.             GC_printf1("Marked from %lu dirty pages\n",
  243.                    (unsigned long)GC_n_rescuing_pages);
  244. #            endif
  245.                     GC_push_roots(FALSE);
  246.                     GC_objects_are_marked = TRUE;
  247.                     if (GC_mark_state != MS_INVALID) {
  248.                         GC_mark_state = MS_ROOTS_PUSHED;
  249.                     }
  250.                 }
  251.             }
  252.             return(FALSE);
  253.         
  254.         case MS_PUSH_UNCOLLECTABLE:
  255.             if (GC_mark_stack_top
  256.                 >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
  257.                 GC_mark_from_mark_stack();
  258.                 return(FALSE);
  259.             } else {
  260.                 scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
  261.                 if (scan_ptr == 0) {
  262.                     GC_push_roots(TRUE);
  263.                     GC_objects_are_marked = TRUE;
  264.                     if (GC_mark_state != MS_INVALID) {
  265.                         GC_mark_state = MS_ROOTS_PUSHED;
  266.                     }
  267.                 }
  268.             }
  269.             return(FALSE);
  270.         
  271.         case MS_ROOTS_PUSHED:
  272.             if (GC_mark_stack_top >= GC_mark_stack) {
  273.                 GC_mark_from_mark_stack();
  274.                 return(FALSE);
  275.             } else {
  276.                 GC_mark_state = MS_NONE;
  277.                 if (GC_mark_stack_too_small) {
  278.                     alloc_mark_stack(2*GC_mark_stack_size);
  279.                 }
  280.                 return(TRUE);
  281.             }
  282.             
  283.         case MS_INVALID:
  284.         case MS_PARTIALLY_INVALID:
  285.         if (!GC_objects_are_marked) {
  286.         GC_mark_state = MS_PUSH_UNCOLLECTABLE;
  287.         return(FALSE);
  288.         }
  289.             if (GC_mark_stack_top >= GC_mark_stack) {
  290.                 GC_mark_from_mark_stack();
  291.                 return(FALSE);
  292.             }
  293.             if (scan_ptr == 0
  294.                 && (GC_mark_state == MS_INVALID || GC_mark_stack_too_small)) {
  295.                 alloc_mark_stack(2*GC_mark_stack_size);
  296.         GC_mark_state = MS_PARTIALLY_INVALID;
  297.             }
  298.             scan_ptr = GC_push_next_marked(scan_ptr);
  299.             if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
  300.                 GC_push_roots(TRUE);
  301.                 GC_objects_are_marked = TRUE;
  302.                 if (GC_mark_state != MS_INVALID) {
  303.                     GC_mark_state = MS_ROOTS_PUSHED;
  304.                 }
  305.             }
  306.             return(FALSE);
  307.         default:
  308.             ABORT("GC_mark_some: bad state");
  309.             return(FALSE);
  310.     }
  311. }
  312.  
  313.  
  314. bool GC_mark_stack_empty()
  315. {
  316.     return(GC_mark_stack_top < GC_mark_stack);
  317. }    
  318.  
  319. #ifdef PROF_MARKER
  320.     word GC_prof_array[10];
  321. #   define PROF(n) GC_prof_array[n]++
  322. #else
  323. #   define PROF(n)
  324. #endif
  325.  
  326. /* Given a pointer to someplace other than a small object page or the    */
  327. /* first page of a large object, return a pointer either to the        */
  328. /* start of the large object or NIL.                    */
  329. /* In the latter case black list the address current.            */
  330. /* Returns NIL without black listing if current points to a block    */
  331. /* with IGNORE_OFF_PAGE set.                        */
  332. /*ARGSUSED*/
  333. word GC_find_start(current, hhdr)
  334. register word current;
  335. register hdr * hhdr;
  336. {
  337. #   ifdef ALL_INTERIOR_POINTERS
  338.     if (hhdr != 0) {
  339.         register word orig = current;
  340.         
  341.         current = (word)HBLKPTR(current) + HDR_BYTES;
  342.         do {
  343.           current = current - HBLKSIZE*(word)hhdr;
  344.           hhdr = HDR(current);
  345.         } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
  346.         /* current points to the start of the large object */
  347.         if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
  348.         if ((word *)orig - (word *)current
  349.              >= (ptrdiff_t)(hhdr->hb_sz)) {
  350.             /* Pointer past the end of the block */
  351.             GC_ADD_TO_BLACK_LIST_NORMAL(orig);
  352.             return(0);
  353.         }
  354.         return(current);
  355.     } else {
  356.         GC_ADD_TO_BLACK_LIST_NORMAL(current);
  357.         return(0);
  358.         }
  359. #   else
  360.         GC_ADD_TO_BLACK_LIST_NORMAL(current);
  361.         return(0);
  362. #   endif
  363. }
  364.  
  365. mse * GC_signal_mark_stack_overflow(msp)
  366. mse * msp;
  367. {
  368.     GC_mark_state = MS_INVALID;
  369. #   ifdef PRINTSTATS
  370.     GC_printf1("Mark stack overflow; current size = %lu entries\n",
  371.                 GC_mark_stack_size);
  372. #    endif
  373.      return(msp-INITIAL_MARK_STACK_SIZE/8);
  374. }
  375.  
  376.  
  377. /*
  378.  * Mark objects pointed to by the regions described by
  379.  * mark stack entries between GC_mark_stack and GC_mark_stack_top,
  380.  * inclusive.  Assumes the upper limit of a mark stack entry
  381.  * is never 0.  A mark stack entry never has size 0.
  382.  * We try to traverse on the order of a hblk of memory before we return.
  383.  * Caller is responsible for calling this until the mark stack is empty.
  384.  */
  385. void GC_mark_from_mark_stack()
  386. {
  387.   mse * GC_mark_stack_reg = GC_mark_stack;
  388.   mse * GC_mark_stack_top_reg = GC_mark_stack_top;
  389.   mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
  390.   int credit = HBLKSIZE;    /* Remaining credit for marking work    */
  391.   register word * current_p;    /* Pointer to current candidate ptr.    */
  392.   register word current;    /* Candidate pointer.            */
  393.   register word * limit;    /* (Incl) limit of current candidate     */
  394.                   /* range                */
  395.   register word descr;
  396.   register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  397.   register ptr_t least_ha = GC_least_plausible_heap_addr;
  398. # define SPLIT_RANGE_WORDS 128  /* Must be power of 2.        */
  399.  
  400.   GC_objects_are_marked = TRUE;
  401. # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
  402.   while (GC_mark_stack_top_reg >= GC_mark_stack_reg && credit >= 0) {
  403. # else
  404.   while ((((ptr_t)GC_mark_stack_top_reg - (ptr_t)GC_mark_stack_reg) | credit)
  405.       >= 0) {
  406. # endif
  407.     current_p = GC_mark_stack_top_reg -> mse_start;
  408.     descr = GC_mark_stack_top_reg -> mse_descr;
  409.   retry:  
  410.     if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | DS_TAGS)) {
  411.       word tag = descr & DS_TAGS;
  412.       
  413.       switch(tag) {
  414.         case DS_LENGTH:
  415.           /* Large length.                            */
  416.           /* Process part of the range to avoid pushing too much on the    */
  417.           /* stack.                            */
  418.           GC_mark_stack_top_reg -> mse_start =
  419.              limit = current_p + SPLIT_RANGE_WORDS-1;
  420.           GC_mark_stack_top_reg -> mse_descr -=
  421.                   WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
  422.           /* Make sure that pointers overlapping the two ranges are    */
  423.           /* considered.                         */
  424.           limit += sizeof(word) - ALIGNMENT;
  425.           break;
  426.         case DS_BITMAP:
  427.           GC_mark_stack_top_reg--;
  428.           descr &= ~DS_TAGS;
  429.           credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
  430.           while (descr != 0) {
  431.             if ((signed_word)descr < 0) {
  432.               current = *current_p++;
  433.               descr <<= 1;
  434.               if ((ptr_t)current < least_ha) continue;
  435.               if ((ptr_t)current >= greatest_ha) continue;
  436.               PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit);
  437.             } else {
  438.               descr <<= 1;
  439.               current_p++;
  440.             }
  441.           }
  442.           continue;
  443.         case DS_PROC:
  444.           GC_mark_stack_top_reg--;
  445.           credit -= PROC_BYTES;
  446.           GC_mark_stack_top_reg =
  447.               (*PROC(descr))
  448.                       (current_p, GC_mark_stack_top_reg,
  449.                       mark_stack_limit, ENV(descr));
  450.           continue;
  451.         case DS_PER_OBJECT:
  452.           descr = *(word *)((ptr_t)current_p + descr - tag);
  453.           goto retry;
  454.       }
  455.     } else {
  456.       GC_mark_stack_top_reg--;
  457.       limit = (word *)(((ptr_t)current_p) + (word)descr);
  458.     }
  459.     /* The simple case in which we're scanning a range.    */
  460.     credit -= (ptr_t)limit - (ptr_t)current_p;
  461.     limit -= 1;
  462.     while (current_p <= limit) {
  463.       current = *current_p;
  464.       current_p = (word *)((char *)current_p + ALIGNMENT);
  465.       if ((ptr_t)current < least_ha) continue;
  466.       if ((ptr_t)current >= greatest_ha) continue;
  467.       PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit);
  468.     }
  469.   }
  470.   GC_mark_stack_top = GC_mark_stack_top_reg;
  471. }
  472.  
  473. /* Allocate or reallocate space for mark stack of size s words  */
  474. /* May silently fail.                        */
  475. static void alloc_mark_stack(n)
  476. word n;
  477. {
  478.     mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct ms_entry));
  479.     
  480.     GC_mark_stack_too_small = FALSE;
  481.     if (GC_mark_stack_size != 0) {
  482.         if (new_stack != 0) {
  483.           word displ = HBLKDISPL(GC_mark_stack);
  484.           word size = GC_mark_stack_size * sizeof(struct ms_entry);
  485.           
  486.           /* Recycle old space */
  487.             if (displ == 0) {
  488.               GC_add_to_heap((struct hblk *)GC_mark_stack, size);
  489.         } else {
  490.           GC_add_to_heap((struct hblk *)
  491.                       ((word)GC_mark_stack - displ + HBLKSIZE),
  492.                        size - HBLKSIZE);
  493.         }
  494.           GC_mark_stack = new_stack;
  495.           GC_mark_stack_size = n;
  496. #      ifdef PRINTSTATS
  497.           GC_printf1("Grew mark stack to %lu frames\n",
  498.                  (unsigned long) GC_mark_stack_size);
  499. #      endif
  500.         } else {
  501. #      ifdef PRINTSTATS
  502.           GC_printf1("Failed to grow mark stack to %lu frames\n",
  503.                  (unsigned long) n);
  504. #      endif
  505.         }
  506.     } else {
  507.         if (new_stack == 0) {
  508.             GC_err_printf0("No space for mark stack\n");
  509.             EXIT();
  510.         }
  511.         GC_mark_stack = new_stack;
  512.         GC_mark_stack_size = n;
  513.     }
  514.     GC_mark_stack_top = GC_mark_stack-1;
  515. }
  516.  
  517. void GC_mark_init()
  518. {
  519.     alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
  520. }
  521.  
  522. /*
  523.  * Push all locations between b and t onto the mark stack.
  524.  * b is the first location to be checked. t is one past the last
  525.  * location to be checked.
  526.  * Should only be used if there is no possibility of mark stack
  527.  * overflow.
  528.  */
  529. void GC_push_all(bottom, top)
  530. ptr_t bottom;
  531. ptr_t top;
  532. {
  533.     register word length;
  534.     
  535.     bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
  536.     top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
  537.     if (top == 0 || bottom == top) return;
  538.     GC_mark_stack_top++;
  539.     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
  540.     ABORT("unexpected mark stack overflow");
  541.     }
  542.     length = top - bottom;
  543. #   if DS_TAGS > ALIGNMENT - 1
  544.     length += DS_TAGS;
  545.     length &= ~DS_TAGS;
  546. #   endif
  547.     GC_mark_stack_top -> mse_start = (word *)bottom;
  548.     GC_mark_stack_top -> mse_descr = length;
  549. }
  550.  
  551. /*
  552.  * Analogous to the above, but push only those pages that may have been
  553.  * dirtied.  A block h is assumed dirty if dirty_fn(h) != 0.
  554.  * We use push_fn to actually push the block.
  555.  * Will not overflow mark stack if push_fn pushes a small fixed number
  556.  * of entries.  (This is invoked only if push_fn pushes a single entry,
  557.  * or if it marks each object before pushing it, thus ensuring progress
  558.  * in the event of a stack overflow.)
  559.  */
  560. void GC_push_dirty(bottom, top, dirty_fn, push_fn)
  561. ptr_t bottom;
  562. ptr_t top;
  563. int (*dirty_fn)(/* struct hblk * h */);
  564. void (*push_fn)(/* ptr_t bottom, ptr_t top */);
  565. {
  566.     register struct hblk * h;
  567.  
  568.     bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
  569.     top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
  570.  
  571.     if (top == 0 || bottom == top) return;
  572.     h = HBLKPTR(bottom + HBLKSIZE);
  573.     if (top <= (ptr_t) h) {
  574.       if ((*dirty_fn)(h-1)) {
  575.         (*push_fn)(bottom, top);
  576.     }
  577.     return;
  578.     }
  579.     if ((*dirty_fn)(h-1)) {
  580.         (*push_fn)(bottom, (ptr_t)h);
  581.     }
  582.     while ((ptr_t)(h+1) <= top) {
  583.     if ((*dirty_fn)(h)) {
  584.         if ((word)(GC_mark_stack_top - GC_mark_stack)
  585.         > 3 * GC_mark_stack_size / 4) {
  586.          /* Danger of mark stack overflow */
  587.         (*push_fn)((ptr_t)h, top);
  588.         return;
  589.         } else {
  590.         (*push_fn)((ptr_t)h, (ptr_t)(h+1));
  591.         }
  592.     }
  593.     h++;
  594.     }
  595.     if ((ptr_t)h != top) {
  596.     if ((*dirty_fn)(h)) {
  597.             (*push_fn)((ptr_t)h, top);
  598.         }
  599.     }
  600.     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
  601.         ABORT("unexpected mark stack overflow");
  602.     }
  603. }
  604.  
  605. # ifndef SMALL_CONFIG
  606. void GC_push_conditional(bottom, top, all)
  607. ptr_t bottom;
  608. ptr_t top;
  609. {
  610.     if (all) {
  611.       if (GC_dirty_maintained) {
  612. #    ifdef PROC_VDB
  613.         /* Pages that were never dirtied cannot contain pointers    */
  614.         GC_push_dirty(bottom, top, GC_page_was_ever_dirty, GC_push_all);
  615. #    else
  616.         GC_push_all(bottom, top);
  617. #    endif
  618.       } else {
  619.           GC_push_all(bottom, top);
  620.       }
  621.     } else {
  622.     GC_push_dirty(bottom, top, GC_page_was_dirty, GC_push_all);
  623.     }
  624. }
  625. #endif
  626.  
  627. # ifdef MSWIN32
  628.   void __cdecl GC_push_one(p)
  629. # else
  630.   void GC_push_one(p)
  631. # endif
  632. word p;
  633. {
  634.     GC_PUSH_ONE_STACK(p);
  635. }
  636.  
  637. # ifdef __STDC__
  638. #   define BASE(p) (word)GC_base((void *)(p))
  639. # else
  640. #   define BASE(p) (word)GC_base((char *)(p))
  641. # endif
  642.  
  643. /* As above, but argument passed preliminary test. */
  644. void GC_push_one_checked(p, interior_ptrs)
  645. register word p;
  646. register bool interior_ptrs;
  647. {
  648.     register word r;
  649.     register hdr * hhdr; 
  650.     register int displ;
  651.   
  652.     GET_HDR(p, hhdr);
  653.     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
  654.         if (hhdr != 0 && interior_ptrs) {
  655.           r = BASE(p);
  656.       hhdr = HDR(r);
  657.       displ = BYTES_TO_WORDS(HBLKDISPL(r));
  658.     } else {
  659.       hhdr = 0;
  660.     }
  661.     } else {
  662.         register map_entry_type map_entry;
  663.         
  664.         displ = HBLKDISPL(p);
  665.         map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
  666.         if (map_entry == OBJ_INVALID) {
  667.           if (interior_ptrs) {
  668.             r = BASE(p);
  669.         displ = BYTES_TO_WORDS(HBLKDISPL(r));
  670.         if (r == 0) hhdr = 0;
  671.           } else {
  672.             hhdr = 0;
  673.           }
  674.         } else {
  675.           displ = BYTES_TO_WORDS(displ);
  676.           displ -= map_entry;
  677.           r = (word)((word *)(HBLKPTR(p)) + displ);
  678.         }
  679.     }
  680.     /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
  681.     /* displ is the word index within the block.         */
  682.     if (hhdr == 0) {
  683.         if (interior_ptrs) {
  684.         GC_add_to_black_list_stack(p);
  685.     } else {
  686.         GC_ADD_TO_BLACK_LIST_NORMAL(p);
  687.     }
  688.     } else {
  689.     if (!mark_bit_from_hdr(hhdr, displ)) {
  690.         set_mark_bit_from_hdr(hhdr, displ);
  691.         PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
  692.                  &(GC_mark_stack[GC_mark_stack_size]));
  693.     }
  694.     }
  695. }
  696.  
  697. # ifdef TRACE_BUF
  698.  
  699. # define TRACE_ENTRIES 1000
  700.  
  701. struct trace_entry {
  702.     char * kind;
  703.     word gc_no;
  704.     word words_allocd;
  705.     word arg1;
  706.     word arg2;
  707. } GC_trace_buf[TRACE_ENTRIES];
  708.  
  709. int GC_trace_buf_ptr = 0;
  710.  
  711. void GC_add_trace_entry(char *kind, word arg1, word arg2)
  712. {
  713.     GC_trace_buf[GC_trace_buf_ptr].kind = kind;
  714.     GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
  715.     GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
  716.     GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
  717.     GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
  718.     GC_trace_buf_ptr++;
  719.     if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
  720. }
  721.  
  722. void GC_print_trace(word gc_no, bool lock)
  723. {
  724.     int i;
  725.     struct trace_entry *p;
  726.     
  727.     if (lock) LOCK();
  728.     for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
  729.         if (i < 0) i = TRACE_ENTRIES-1;
  730.         p = GC_trace_buf + i;
  731.         if (p -> gc_no < gc_no || p -> kind == 0) return;
  732.         printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
  733.             p -> kind, p -> gc_no, p -> words_allocd,
  734.             (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
  735.     }
  736.     printf("Trace incomplete\n");
  737.     if (lock) UNLOCK();
  738. }
  739.  
  740. # endif /* TRACE_BUF */
  741.  
  742. /*
  743.  * A version of GC_push_all that treats all interior pointers as valid
  744.  */
  745. void GC_push_all_stack(bottom, top)
  746. ptr_t bottom;
  747. ptr_t top;
  748. {
  749. # ifdef ALL_INTERIOR_POINTERS
  750.     GC_push_all(bottom, top);
  751. #   ifdef TRACE_BUF
  752.         GC_add_trace_entry("GC_push_all_stack", bottom, top);
  753. #   endif
  754. # else
  755.     word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
  756.     word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
  757.     register word *p;
  758.     register word q;
  759.     register word *lim;
  760.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  761.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  762. #   define GC_greatest_plausible_heap_addr greatest_ha
  763. #   define GC_least_plausible_heap_addr least_ha
  764.  
  765.     if (top == 0) return;
  766.     /* check all pointers in range and put in push if they appear */
  767.     /* to be valid.                          */
  768.       lim = t - 1 /* longword */;
  769.       for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
  770.     q = *p;
  771.     GC_PUSH_ONE_STACK(q);
  772.       }
  773. #   undef GC_greatest_plausible_heap_addr
  774. #   undef GC_least_plausible_heap_addr
  775. # endif
  776. }
  777.  
  778. #ifndef SMALL_CONFIG
  779. /* Push all objects reachable from marked objects in the given block */
  780. /* of size 1 objects.                             */
  781. void GC_push_marked1(h, hhdr)
  782. struct hblk *h;
  783. register hdr * hhdr;
  784. {
  785.     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
  786.     register word *p;
  787.     word *plim;
  788.     register int i;
  789.     register word q;
  790.     register word mark_word;
  791.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  792.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  793. #   define GC_greatest_plausible_heap_addr greatest_ha
  794. #   define GC_least_plausible_heap_addr least_ha
  795.     
  796.     p = (word *)(h->hb_body);
  797.     plim = (word *)(((word)h) + HBLKSIZE);
  798.  
  799.     /* go through all words in block */
  800.     while( p < plim )  {
  801.         mark_word = *mark_word_addr++;
  802.         i = 0;
  803.         while(mark_word != 0) {
  804.           if (mark_word & 1) {
  805.               q = p[i];
  806.               GC_PUSH_ONE_HEAP(q);
  807.           }
  808.           i++;
  809.           mark_word >>= 1;
  810.         }
  811.         p += WORDSZ;
  812.     }
  813. #   undef GC_greatest_plausible_heap_addr
  814. #   undef GC_least_plausible_heap_addr        
  815. }
  816.  
  817.  
  818. #ifndef UNALIGNED
  819.  
  820. /* Push all objects reachable from marked objects in the given block */
  821. /* of size 2 objects.                             */
  822. void GC_push_marked2(h, hhdr)
  823. struct hblk *h;
  824. register hdr * hhdr;
  825. {
  826.     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
  827.     register word *p;
  828.     word *plim;
  829.     register int i;
  830.     register word q;
  831.     register word mark_word;
  832.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  833.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  834. #   define GC_greatest_plausible_heap_addr greatest_ha
  835. #   define GC_least_plausible_heap_addr least_ha
  836.     
  837.     p = (word *)(h->hb_body);
  838.     plim = (word *)(((word)h) + HBLKSIZE);
  839.  
  840.     /* go through all words in block */
  841.     while( p < plim )  {
  842.         mark_word = *mark_word_addr++;
  843.         i = 0;
  844.         while(mark_word != 0) {
  845.           if (mark_word & 1) {
  846.               q = p[i];
  847.               GC_PUSH_ONE_HEAP(q);
  848.               q = p[i+1];
  849.               GC_PUSH_ONE_HEAP(q);
  850.           }
  851.           i += 2;
  852.           mark_word >>= 2;
  853.         }
  854.         p += WORDSZ;
  855.     }
  856. #   undef GC_greatest_plausible_heap_addr
  857. #   undef GC_least_plausible_heap_addr        
  858. }
  859.  
  860. /* Push all objects reachable from marked objects in the given block */
  861. /* of size 4 objects.                             */
  862. /* There is a risk of mark stack overflow here.  But we handle that. */
  863. /* And only unmarked objects get pushed, so it's not very likely.    */
  864. void GC_push_marked4(h, hhdr)
  865. struct hblk *h;
  866. register hdr * hhdr;
  867. {
  868.     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
  869.     register word *p;
  870.     word *plim;
  871.     register int i;
  872.     register word q;
  873.     register word mark_word;
  874.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  875.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  876. #   define GC_greatest_plausible_heap_addr greatest_ha
  877. #   define GC_least_plausible_heap_addr least_ha
  878.     
  879.     p = (word *)(h->hb_body);
  880.     plim = (word *)(((word)h) + HBLKSIZE);
  881.  
  882.     /* go through all words in block */
  883.     while( p < plim )  {
  884.         mark_word = *mark_word_addr++;
  885.         i = 0;
  886.         while(mark_word != 0) {
  887.           if (mark_word & 1) {
  888.               q = p[i];
  889.               GC_PUSH_ONE_HEAP(q);
  890.               q = p[i+1];
  891.               GC_PUSH_ONE_HEAP(q);
  892.               q = p[i+2];
  893.               GC_PUSH_ONE_HEAP(q);
  894.               q = p[i+3];
  895.               GC_PUSH_ONE_HEAP(q);
  896.           }
  897.           i += 4;
  898.           mark_word >>= 4;
  899.         }
  900.         p += WORDSZ;
  901.     }
  902. #   undef GC_greatest_plausible_heap_addr
  903. #   undef GC_least_plausible_heap_addr        
  904. }
  905.  
  906. /* #endif UNALIGNED                                                             -- NLP */
  907. #endif  /* UNALIGNED */                                                      /* -- NLP */
  908.  
  909. #endif /* SMALL_CONFIG */
  910.  
  911. /* Push all objects reachable from marked objects in the given block */
  912. void GC_push_marked(h, hhdr)
  913. struct hblk *h;
  914. register hdr * hhdr;
  915. {
  916.     register int sz = hhdr -> hb_sz;
  917.     register word * p;
  918.     register int word_no;
  919.     register word * lim;
  920.     register mse * GC_mark_stack_top_reg;
  921.     register mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
  922.     
  923.     /* Some quick shortcuts: */
  924.         if (hhdr -> hb_obj_kind == PTRFREE) return;
  925.         if (GC_block_empty(hhdr)/* nothing marked */) return;
  926. #   ifdef GATHERSTATS
  927.         GC_n_rescuing_pages++;
  928. #   endif
  929.     GC_objects_are_marked = TRUE;
  930.     if (sz > MAXOBJSZ) {
  931.         lim = (word *)(h + 1);
  932.     } else {
  933.         lim = (word *)(h + 1) - sz;
  934.     }
  935.     
  936.     switch(sz) {
  937. #   if !defined(SMALL_CONFIG)    
  938.      case 1:
  939.        GC_push_marked1(h, hhdr);
  940.        break;
  941. #   endif
  942. #   if !defined(SMALL_CONFIG) && !defined(UNALIGNED)
  943.      case 2:
  944.        GC_push_marked2(h, hhdr);
  945.        break;
  946.      case 4:
  947.        GC_push_marked4(h, hhdr);
  948.        break;
  949. #   endif       
  950.      default:
  951.       GC_mark_stack_top_reg = GC_mark_stack_top;
  952.       for (p = (word *)h + HDR_WORDS, word_no = HDR_WORDS; p <= lim;
  953.          p += sz, word_no += sz) {
  954.          /* This ignores user specified mark procs.  This currently    */
  955.          /* doesn't matter, since marking from the whole object        */
  956.          /* is always sufficient, and we will eventually use the user    */
  957.          /* mark proc to avoid any bogus pointers.            */
  958.          if (mark_bit_from_hdr(hhdr, word_no)) {
  959.            /* Mark from fields inside the object */
  960.              PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
  961. #         ifdef GATHERSTATS
  962.         /* Subtract this object from total, since it was    */
  963.         /* added in twice.                    */
  964.         GC_composite_in_use -= sz;
  965. #         endif
  966.          }
  967.       }
  968.       GC_mark_stack_top = GC_mark_stack_top_reg;
  969.     }
  970. }
  971.  
  972. #ifndef SMALL_CONFIG
  973. /* Test whether any page in the given block is dirty    */
  974. bool GC_block_was_dirty(h, hhdr)
  975. struct hblk *h;
  976. register hdr * hhdr;
  977. {
  978.     register int sz = hhdr -> hb_sz;
  979.     
  980.     if (sz < MAXOBJSZ) {
  981.          return(GC_page_was_dirty(h));
  982.     } else {
  983.          register ptr_t p = (ptr_t)h;
  984.          sz += HDR_WORDS;
  985.          sz = WORDS_TO_BYTES(sz);
  986.          while (p < (ptr_t)h + sz) {
  987.              if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
  988.              p += HBLKSIZE;
  989.          }
  990.          return(FALSE);
  991.     }
  992. }
  993. #endif /* SMALL_CONFIG */
  994.  
  995. /* Similar to GC_push_next_marked, but return address of next block    */
  996. struct hblk * GC_push_next_marked(h)
  997. struct hblk *h;
  998. {
  999.     register hdr * hhdr;
  1000.     
  1001.     h = GC_next_block(h);
  1002.     if (h == 0) return(0);
  1003.     hhdr = HDR(h);
  1004.     GC_push_marked(h, hhdr);
  1005.     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
  1006. }
  1007.  
  1008. #ifndef SMALL_CONFIG
  1009. /* Identical to above, but mark only from dirty pages    */
  1010. struct hblk * GC_push_next_marked_dirty(h)
  1011. struct hblk *h;
  1012. {
  1013.     register hdr * hhdr = HDR(h);
  1014.     
  1015.     if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
  1016.     for (;;) {
  1017.         h = GC_next_block(h);
  1018.         if (h == 0) return(0);
  1019.         hhdr = HDR(h);
  1020. #    ifdef STUBBORN_ALLOC
  1021.           if (hhdr -> hb_obj_kind == STUBBORN) {
  1022.             if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
  1023.                 break;
  1024.             }
  1025.           } else {
  1026.             if (GC_block_was_dirty(h, hhdr)) break;
  1027.           }
  1028. #    else
  1029.       if (GC_block_was_dirty(h, hhdr)) break;
  1030. #    endif
  1031.         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
  1032.     }
  1033.     GC_push_marked(h, hhdr);
  1034.     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
  1035. }
  1036. #endif
  1037.  
  1038. /* Similar to above, but for uncollectable pages.  Needed since we    */
  1039. /* do not clear marks for such pages, even for full collections.    */
  1040. struct hblk * GC_push_next_marked_uncollectable(h)
  1041. struct hblk *h;
  1042. {
  1043.     register hdr * hhdr = HDR(h);
  1044.     
  1045.     for (;;) {
  1046.         h = GC_next_block(h);
  1047.         if (h == 0) return(0);
  1048.         hhdr = HDR(h);
  1049.     if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
  1050.         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
  1051.     }
  1052.     GC_push_marked(h, hhdr);
  1053.     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
  1054. }
  1055.  
  1056.  
  1057.