Back to index

lightning-sunbird  0.9+nobinonly
mark.c
Go to the documentation of this file.
00001 
00002 /*
00003  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
00004  * Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved.
00005  *
00006  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
00007  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
00008  *
00009  * Permission is hereby granted to use or copy this program
00010  * for any purpose,  provided the above notices are retained on all copies.
00011  * Permission to modify the code and to distribute modified code is granted,
00012  * provided the above notices are retained, and a notice that the code was
00013  * modified is included with the above copyright notice.
00014  *
00015  */
00016 
00017 
00018 # include <stdio.h>
00019 # include "gc_priv.h"
00020 # include "gc_mark.h"
00021 
00022 /* We put this here to minimize the risk of inlining. */
00023 /*VARARGS*/
00024 #ifdef __WATCOMC__
00025   void GC_noop(void *p, ...) {}
00026 #else
00027   void GC_noop() {}
00028 #endif
00029 
00030 /* Single argument version, robust against whole program analysis. */
00031 void GC_noop1(x)
00032 word x;
00033 {
00034     static VOLATILE word sink;
00035 
00036     sink = x;
00037 }
00038 
00039 /* mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0} -- declared in gc_priv.h */
00040 
00041 word GC_n_mark_procs = 0;
00042 
00043 /* Initialize GC_obj_kinds properly and standard free lists properly.        */
00044 /* This must be done statically since they may be accessed before     */
00045 /* GC_init is called.                                                 */
00046 /* It's done here, since we need to deal with mark descriptors.              */
00047 struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
00048 /* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */,
00049               0 | DS_LENGTH, FALSE, FALSE },
00050 /* NORMAL  */ { &GC_objfreelist[0], 0,
00051 #             if defined(ADD_BYTE_AT_END) && ALIGNMENT > DS_TAGS
00052               (word)(-ALIGNMENT) | DS_LENGTH,
00053 #             else
00054               0 | DS_LENGTH,
00055 #             endif
00056               TRUE /* add length to descr */, TRUE },
00057 /* UNCOLLECTABLE */
00058              { &GC_uobjfreelist[0], 0,
00059               0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
00060 # ifdef ATOMIC_UNCOLLECTABLE
00061    /* AUNCOLLECTABLE */
00062              { &GC_auobjfreelist[0], 0,
00063               0 | DS_LENGTH, FALSE /* add length to descr */, FALSE },
00064 # endif
00065 # ifdef STUBBORN_ALLOC
00066 /*STUBBORN*/ { &GC_sobjfreelist[0], 0,
00067               0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
00068 # endif
00069 };
00070 
00071 # ifdef ATOMIC_UNCOLLECTABLE
00072 #   ifdef STUBBORN_ALLOC
00073       int GC_n_kinds = 5;
00074 #   else
00075       int GC_n_kinds = 4;
00076 #   endif
00077 # else
00078 #   ifdef STUBBORN_ALLOC
00079       int GC_n_kinds = 4;
00080 #   else
00081       int GC_n_kinds = 3;
00082 #   endif
00083 # endif
00084 
00085 
00086 # ifndef INITIAL_MARK_STACK_SIZE
00087 #   define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
00088               /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a    */
00089               /* multiple of HBLKSIZE.                         */
00090 # endif
00091 
00092 /*
00093  * Limits of stack for GC_mark routine.
00094  * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
00095  * need to be marked from.
00096  */
00097 
00098 word GC_n_rescuing_pages;   /* Number of dirty pages we marked from */
00099                             /* excludes ptrfree pages, etc.           */
00100 
00101 mse * GC_mark_stack;
00102 
00103 word GC_mark_stack_size = 0;
00104  
00105 mse * GC_mark_stack_top;
00106 
00107 static struct hblk * scan_ptr;
00108 
00109 mark_state_t GC_mark_state = MS_NONE;
00110 
00111 GC_bool GC_mark_stack_too_small = FALSE;
00112 
00113 GC_bool GC_objects_are_marked = FALSE;    /* Are there collectable marked    */
00114                                    /* objects in the heap?            */
00115 
00116 /* Is a collection in progress?  Note that this can return true in the       */
00117 /* nonincremental case, if a collection has been abandoned and the    */
00118 /* mark state is now MS_INVALID.                               */
00119 GC_bool GC_collection_in_progress()
00120 {
00121     return(GC_mark_state != MS_NONE);
00122 }
00123 
00124 /* clear all mark bits in the header */
00125 void GC_clear_hdr_marks(hhdr)
00126 register hdr * hhdr;
00127 {
00128     BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
00129 }
00130 
00131 /* Set all mark bits in the header.  Used for uncollectable blocks. */
00132 void GC_set_hdr_marks(hhdr)
00133 register hdr * hhdr;
00134 {
00135     register int i;
00136 
00137     for (i = 0; i < MARK_BITS_SZ; ++i) {
00138        hhdr -> hb_marks[i] = ONES;
00139     }
00140 }
00141 
00142 /*
00143  * Clear all mark bits associated with block h.
00144  */
00145 /*ARGSUSED*/
00146 static void clear_marks_for_block(h, dummy)
00147 struct hblk *h;
00148 word dummy;
00149 {
00150     register hdr * hhdr = HDR(h);
00151     
00152     if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return;
00153         /* Mark bit for these is cleared only once the object is      */
00154         /* explicitly deallocated.  This either frees the block, or   */
00155         /* the bit is cleared once the object is on the free list.    */
00156     GC_clear_hdr_marks(hhdr);
00157 }
00158 
00159 /* Slow but general routines for setting/clearing/asking about mark bits */
00160 void GC_set_mark_bit(p)
00161 ptr_t p;
00162 {
00163     register struct hblk *h = HBLKPTR(p);
00164     register hdr * hhdr = HDR(h);
00165     register int word_no = (word *)p - (word *)h;
00166     
00167     set_mark_bit_from_hdr(hhdr, word_no);
00168 }
00169 
00170 void GC_clear_mark_bit(p)
00171 ptr_t p;
00172 {
00173     register struct hblk *h = HBLKPTR(p);
00174     register hdr * hhdr = HDR(h);
00175     register int word_no = (word *)p - (word *)h;
00176     
00177     clear_mark_bit_from_hdr(hhdr, word_no);
00178 }
00179 
00180 GC_bool GC_is_marked(p)
00181 ptr_t p;
00182 {
00183     register struct hblk *h = HBLKPTR(p);
00184     register hdr * hhdr = HDR(h);
00185     register int word_no = (word *)p - (word *)h;
00186     
00187     return(mark_bit_from_hdr(hhdr, word_no));
00188 }
00189 
00190 
00191 /*
00192  * Clear mark bits in all allocated heap blocks.  This invalidates
00193  * the marker invariant, and sets GC_mark_state to reflect this.
00194  * (This implicitly starts marking to reestablish the invariant.)
00195  */
00196 void GC_clear_marks()
00197 {
00198     GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
00199     GC_objects_are_marked = FALSE;
00200     GC_mark_state = MS_INVALID;
00201     scan_ptr = 0;
00202 #   ifdef GATHERSTATS
00203        /* Counters reflect currently marked objects: reset here */
00204         GC_composite_in_use = 0;
00205         GC_atomic_in_use = 0;
00206 #   endif
00207 
00208 }
00209 
00210 /* Initiate a garbage collection.  Initiates a full collection if the */
00211 /* mark       state is invalid.                                       */
00212 /*ARGSUSED*/
00213 void GC_initiate_gc()
00214 {
00215     if (GC_dirty_maintained) GC_read_dirty();
00216 #   ifdef STUBBORN_ALLOC
00217        GC_read_changed();
00218 #   endif
00219 #   ifdef CHECKSUMS
00220        {
00221            extern void GC_check_dirty();
00222            
00223            if (GC_dirty_maintained) GC_check_dirty();
00224        }
00225 #   endif
00226 #   ifdef GATHERSTATS
00227        GC_n_rescuing_pages = 0;
00228 #   endif
00229     if (GC_mark_state == MS_NONE) {
00230         GC_mark_state = MS_PUSH_RESCUERS;
00231     } else if (GC_mark_state != MS_INVALID) {
00232        ABORT("unexpected state");
00233     } /* else this is really a full collection, and mark       */
00234       /* bits are invalid.                              */
00235     scan_ptr = 0;
00236 }
00237 
00238 
00239 static void alloc_mark_stack();
00240 
00241 /* Perform a small amount of marking.                   */
00242 /* We try to touch roughly a page of memory.            */
00243 /* Return TRUE if we just finished a mark phase. */
00244 /* Cold_gc_frame is an address inside a GC frame that   */
00245 /* remains valid until all marking is complete.         */
00246 /* A zero value indicates that it's OK to miss some     */
00247 /* register values.                              */
00248 GC_bool GC_mark_some(cold_gc_frame)
00249 ptr_t cold_gc_frame;
00250 {
00251     switch(GC_mark_state) {
00252        case MS_NONE:
00253            return(FALSE);
00254            
00255        case MS_PUSH_RESCUERS:
00256            if (GC_mark_stack_top
00257                >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
00258                GC_mark_from_mark_stack();
00259                return(FALSE);
00260            } else {
00261                scan_ptr = GC_push_next_marked_dirty(scan_ptr);
00262                if (scan_ptr == 0) {
00263 #                 ifdef PRINTSTATS
00264                      GC_printf1("Marked from %lu dirty pages\n",
00265                                (unsigned long)GC_n_rescuing_pages);
00266 #                 endif
00267                   GC_push_roots(FALSE, cold_gc_frame);
00268                   GC_objects_are_marked = TRUE;
00269                   if (GC_mark_state != MS_INVALID) {
00270                       GC_mark_state = MS_ROOTS_PUSHED;
00271                   }
00272               }
00273            }
00274            return(FALSE);
00275        
00276        case MS_PUSH_UNCOLLECTABLE:
00277            if (GC_mark_stack_top
00278                >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
00279                GC_mark_from_mark_stack();
00280                return(FALSE);
00281            } else {
00282                scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
00283                if (scan_ptr == 0) {
00284                   GC_push_roots(TRUE, cold_gc_frame);
00285                   GC_objects_are_marked = TRUE;
00286                   if (GC_mark_state != MS_INVALID) {
00287                       GC_mark_state = MS_ROOTS_PUSHED;
00288                   }
00289               }
00290            }
00291            return(FALSE);
00292        
00293        case MS_ROOTS_PUSHED:
00294            if (GC_mark_stack_top >= GC_mark_stack) {
00295                GC_mark_from_mark_stack();
00296                return(FALSE);
00297            } else {
00298                GC_mark_state = MS_NONE;
00299                if (GC_mark_stack_too_small) {
00300                    alloc_mark_stack(2*GC_mark_stack_size);
00301                }
00302                return(TRUE);
00303            }
00304            
00305        case MS_INVALID:
00306        case MS_PARTIALLY_INVALID:
00307            if (!GC_objects_are_marked) {
00308               GC_mark_state = MS_PUSH_UNCOLLECTABLE;
00309               return(FALSE);
00310            }
00311            if (GC_mark_stack_top >= GC_mark_stack) {
00312                GC_mark_from_mark_stack();
00313                return(FALSE);
00314            }
00315            if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {
00316               /* About to start a heap scan for marked objects. */
00317               /* Mark stack is empty.  OK to reallocate.         */
00318               if (GC_mark_stack_too_small) {
00319                    alloc_mark_stack(2*GC_mark_stack_size);
00320               }
00321               GC_mark_state = MS_PARTIALLY_INVALID;
00322            }
00323            scan_ptr = GC_push_next_marked(scan_ptr);
00324            if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
00325               GC_push_roots(TRUE, cold_gc_frame);
00326               GC_objects_are_marked = TRUE;
00327               if (GC_mark_state != MS_INVALID) {
00328                   GC_mark_state = MS_ROOTS_PUSHED;
00329               }
00330            }
00331            return(FALSE);
00332        default:
00333            ABORT("GC_mark_some: bad state");
00334            return(FALSE);
00335     }
00336 }
00337 
00338 
00339 GC_bool GC_mark_stack_empty()
00340 {
00341     return(GC_mark_stack_top < GC_mark_stack);
00342 }      
00343 
00344 #ifdef PROF_MARKER
00345     word GC_prof_array[10];
00346 #   define PROF(n) GC_prof_array[n]++
00347 #else
00348 #   define PROF(n)
00349 #endif
00350 
00351 /* Given a pointer to someplace other than a small object page or the */
00352 /* first page of a large object, return a pointer either to the              */
00353 /* start of the large object or NIL.                                  */
00354 /* In the latter case black list the address current.                 */
00355 /* Returns NIL without black listing if current points to a block     */
00356 /* with IGNORE_OFF_PAGE set.                                          */
00357 /*ARGSUSED*/
00358 # ifdef PRINT_BLACK_LIST
00359   word GC_find_start(current, hhdr, source)
00360   word source;
00361 # else
00362   word GC_find_start(current, hhdr)
00363 # define source 0
00364 # endif
00365 register word current;
00366 register hdr * hhdr;
00367 {
00368 #   ifdef ALL_INTERIOR_POINTERS
00369        if (hhdr != 0) {
00370            register word orig = current;
00371            
00372            current = (word)HBLKPTR(current) + HDR_BYTES;
00373            do {
00374              current = current - HBLKSIZE*(word)hhdr;
00375              hhdr = HDR(current);
00376            } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
00377            /* current points to the start of the large object */
00378            if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
00379            if ((word *)orig - (word *)current
00380                 >= (ptrdiff_t)(hhdr->hb_sz)) {
00381                /* Pointer past the end of the block */
00382                GC_ADD_TO_BLACK_LIST_NORMAL(orig, source);
00383                return(0);
00384            }
00385            return(current);
00386        } else {
00387            GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
00388            return(0);
00389         }
00390 #   else
00391         GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
00392         return(0);
00393 #   endif
00394 #   undef source
00395 }
00396 
00397 void GC_invalidate_mark_state()
00398 {
00399     GC_mark_state = MS_INVALID;
00400     GC_mark_stack_top = GC_mark_stack-1;
00401 }
00402 
00403 mse * GC_signal_mark_stack_overflow(msp)
00404 mse * msp;
00405 {
00406     GC_mark_state = MS_INVALID;
00407     GC_mark_stack_too_small = TRUE;
00408 #   ifdef PRINTSTATS
00409        GC_printf1("Mark stack overflow; current size = %lu entries\n",
00410                   GC_mark_stack_size);
00411 #    endif
00412      return(msp-INITIAL_MARK_STACK_SIZE/8);
00413 }
00414 
00415 
00416 /*
00417  * Mark objects pointed to by the regions described by
00418  * mark stack entries between GC_mark_stack and GC_mark_stack_top,
00419  * inclusive.  Assumes the upper limit of a mark stack entry
00420  * is never 0.  A mark stack entry never has size 0.
00421  * We try to traverse on the order of a hblk of memory before we return.
00422  * Caller is responsible for calling this until the mark stack is empty.
00423  */
00424 void GC_mark_from_mark_stack()
00425 {
00426   mse * GC_mark_stack_reg = GC_mark_stack;
00427   mse * GC_mark_stack_top_reg = GC_mark_stack_top;
00428   mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
00429   int credit = HBLKSIZE;    /* Remaining credit for marking work      */
00430   register word * current_p;       /* Pointer to current candidate ptr.      */
00431   register word current;    /* Candidate pointer.                     */
00432   register word * limit;    /* (Incl) limit of current candidate      */
00433                             /* range                           */
00434   register word descr;
00435   register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
00436   register ptr_t least_ha = GC_least_plausible_heap_addr;
00437 # define SPLIT_RANGE_WORDS 128  /* Must be power of 2.         */
00438 
00439   GC_objects_are_marked = TRUE;
00440 # if defined(OS2) /* Use untweaked version to circumvent compiler problem */
00441   while (GC_mark_stack_top_reg >= GC_mark_stack_reg && credit >= 0) {
00442 # else
00443   while ((((ptr_t)GC_mark_stack_top_reg - (ptr_t)GC_mark_stack_reg) | credit)
00444        >= 0) {
00445 # endif
00446     current_p = GC_mark_stack_top_reg -> mse_start;
00447   retry:
00448     descr = GC_mark_stack_top_reg -> mse_descr;
00449     if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | DS_TAGS)) {
00450       word tag = descr & DS_TAGS;
00451       
00452       switch(tag) {
00453         case DS_LENGTH:
00454           /* Large length.                                      */
00455           /* Process part of the range to avoid pushing too much on the      */
00456           /* stack.                                            */
00457           GC_mark_stack_top_reg -> mse_start =
00458               limit = current_p + SPLIT_RANGE_WORDS-1;
00459           GC_mark_stack_top_reg -> mse_descr -=
00460                      WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
00461           /* Make sure that pointers overlapping the two ranges are   */
00462           /* considered.                                       */
00463           limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
00464           break;
00465         case DS_BITMAP:
00466           GC_mark_stack_top_reg--;
00467           descr &= ~DS_TAGS;
00468           credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
00469           while (descr != 0) {
00470             if ((signed_word)descr < 0) {
00471               current = *current_p;
00472              if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
00473                 PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit,
00474                            current_p, exit1);
00475              }
00476             }
00477            descr <<= 1;
00478            ++ current_p;
00479           }
00480           continue;
00481         case DS_PROC:
00482           GC_mark_stack_top_reg--;
00483           credit -= PROC_BYTES;
00484           GC_mark_stack_top_reg =
00485               (*PROC(descr))
00486                          (current_p, GC_mark_stack_top_reg,
00487                          mark_stack_limit, ENV(descr));
00488           continue;
00489         case DS_PER_OBJECT:
00490           GC_mark_stack_top_reg -> mse_descr =
00491                      *(word *)((ptr_t)current_p + descr - tag);
00492           goto retry;
00493       }
00494     } else {
00495       GC_mark_stack_top_reg--;
00496       limit = (word *)(((ptr_t)current_p) + (word)descr);
00497     }
00498     /* The simple case in which we're scanning a range. */
00499     credit -= (ptr_t)limit - (ptr_t)current_p;
00500     limit -= 1;
00501     while (current_p <= limit) {
00502       current = *current_p;
00503       if ((ptr_t)current >= least_ha && (ptr_t)current <  greatest_ha) {
00504         PUSH_CONTENTS(current, GC_mark_stack_top_reg,
00505                     mark_stack_limit, current_p, exit2);
00506       }
00507       current_p = (word *)((char *)current_p + ALIGNMENT);
00508     }
00509   }
00510   GC_mark_stack_top = GC_mark_stack_top_reg;
00511 }
00512 
00513 /* Allocate or reallocate space for mark stack of size s words  */
00514 /* May silently fail.                                          */
00515 static void alloc_mark_stack(n)
00516 word n;
00517 {
00518     mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct ms_entry));
00519     
00520     GC_mark_stack_too_small = FALSE;
00521     if (GC_mark_stack_size != 0) {
00522         if (new_stack != 0) {
00523           word displ = (word)GC_mark_stack & (GC_page_size - 1);
00524           signed_word size = GC_mark_stack_size * sizeof(struct ms_entry);
00525           
00526           /* Recycle old space */
00527              if (0 != displ) displ = GC_page_size - displ;
00528              size = (size - displ) & ~(GC_page_size - 1);
00529              if (size > 0) {
00530                GC_add_to_heap((struct hblk *)
00531                             ((word)GC_mark_stack + displ), (word)size);
00532              }
00533           GC_mark_stack = new_stack;
00534           GC_mark_stack_size = n;
00535 #        ifdef PRINTSTATS
00536              GC_printf1("Grew mark stack to %lu frames\n",
00537                       (unsigned long) GC_mark_stack_size);
00538 #        endif
00539         } else {
00540 #        ifdef PRINTSTATS
00541              GC_printf1("Failed to grow mark stack to %lu frames\n",
00542                       (unsigned long) n);
00543 #        endif
00544         }
00545     } else {
00546         if (new_stack == 0) {
00547             GC_err_printf0("No space for mark stack\n");
00548             EXIT();
00549         }
00550         GC_mark_stack = new_stack;
00551         GC_mark_stack_size = n;
00552     }
00553     GC_mark_stack_top = GC_mark_stack-1;
00554 }
00555 
00556 void GC_mark_init()
00557 {
00558     alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
00559 }
00560 
00561 /*
00562  * Push all locations between b and t onto the mark stack.
00563  * b is the first location to be checked. t is one past the last
00564  * location to be checked.
00565  * Should only be used if there is no possibility of mark stack
00566  * overflow.
00567  */
00568 void GC_push_all(bottom, top)
00569 ptr_t bottom;
00570 ptr_t top;
00571 {
00572     register word length;
00573     
00574     bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
00575     top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
00576     if (top == 0 || bottom == top) return;
00577     GC_mark_stack_top++;
00578     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
00579        ABORT("unexpected mark stack overflow");
00580     }
00581     length = top - bottom;
00582 #   if DS_TAGS > ALIGNMENT - 1
00583        length += DS_TAGS;
00584        length &= ~DS_TAGS;
00585 #   endif
00586     GC_mark_stack_top -> mse_start = (word *)bottom;
00587     GC_mark_stack_top -> mse_descr = length;
00588 }
00589 
00590 /*
00591  * Analogous to the above, but push only those pages that may have been
00592  * dirtied.  A block h is assumed dirty if dirty_fn(h) != 0.
00593  * We use push_fn to actually push the block.
00594  * Will not overflow mark stack if push_fn pushes a small fixed number
00595  * of entries.  (This is invoked only if push_fn pushes a single entry,
00596  * or if it marks each object before pushing it, thus ensuring progress
00597  * in the event of a stack overflow.)
00598  */
00599 void GC_push_dirty(bottom, top, dirty_fn, push_fn)
00600 ptr_t bottom;
00601 ptr_t top;
00602 int (*dirty_fn)(/* struct hblk * h */);
00603 void (*push_fn)(/* ptr_t bottom, ptr_t top */);
00604 {
00605     register struct hblk * h;
00606 
00607     bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
00608     top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
00609 
00610     if (top == 0 || bottom == top) return;
00611     h = HBLKPTR(bottom + HBLKSIZE);
00612     if (top <= (ptr_t) h) {
00613        if ((*dirty_fn)(h-1)) {
00614            (*push_fn)(bottom, top);
00615        }
00616        return;
00617     }
00618     if ((*dirty_fn)(h-1)) {
00619         (*push_fn)(bottom, (ptr_t)h);
00620     }
00621     while ((ptr_t)(h+1) <= top) {
00622        if ((*dirty_fn)(h)) {
00623            if ((word)(GC_mark_stack_top - GC_mark_stack)
00624               > 3 * GC_mark_stack_size / 4) {
00625               /* Danger of mark stack overflow */
00626               (*push_fn)((ptr_t)h, top);
00627               return;
00628            } else {
00629               (*push_fn)((ptr_t)h, (ptr_t)(h+1));
00630            }
00631        }
00632        h++;
00633     }
00634     if ((ptr_t)h != top) {
00635        if ((*dirty_fn)(h)) {
00636             (*push_fn)((ptr_t)h, top);
00637         }
00638     }
00639     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
00640         ABORT("unexpected mark stack overflow");
00641     }
00642 }
00643 
00644 # ifndef SMALL_CONFIG
00645 void GC_push_conditional(bottom, top, all)
00646 ptr_t bottom;
00647 ptr_t top;
00648 int all;
00649 {
00650     if (all) {
00651       if (GC_dirty_maintained) {
00652 #      ifdef PROC_VDB
00653            /* Pages that were never dirtied cannot contain pointers   */
00654            GC_push_dirty(bottom, top, GC_page_was_ever_dirty, GC_push_all);
00655 #      else
00656            GC_push_all(bottom, top);
00657 #      endif
00658       } else {
00659        GC_push_all(bottom, top);
00660       }
00661     } else {
00662        GC_push_dirty(bottom, top, GC_page_was_dirty, GC_push_all);
00663     }
00664 }
00665 #endif
00666 
00667 # ifdef MSWIN32
00668   void __cdecl GC_push_one(p)
00669 # else
00670   void GC_push_one(p)
00671 # endif
00672 word p;
00673 {
00674     GC_PUSH_ONE_STACK(p, 0);
00675 }
00676 
00677 # ifdef __STDC__
00678 #   define BASE(p) (word)GC_base((void *)(p))
00679 # else
00680 #   define BASE(p) (word)GC_base((char *)(p))
00681 # endif
00682 
00683 /* As above, but argument passed preliminary test. */
00684 # ifdef PRINT_BLACK_LIST
00685     void GC_push_one_checked(p, interior_ptrs, source)
00686     ptr_t source;
00687 # else
00688     void GC_push_one_checked(p, interior_ptrs)
00689 #   define source 0
00690 # endif
00691 register word p;
00692 register GC_bool interior_ptrs;
00693 {
00694     register word r;
00695     register hdr * hhdr; 
00696     register int displ;
00697   
00698     GET_HDR(p, hhdr);
00699     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
00700         if (hhdr != 0 && interior_ptrs) {
00701           r = BASE(p);
00702          hhdr = HDR(r);
00703          displ = BYTES_TO_WORDS(HBLKDISPL(r));
00704        } else {
00705          hhdr = 0;
00706        }
00707     } else {
00708         register map_entry_type map_entry;
00709         
00710         displ = HBLKDISPL(p);
00711         map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
00712         if (map_entry == OBJ_INVALID) {
00713 #        ifndef ALL_INTERIOR_POINTERS
00714             if (interior_ptrs) {
00715               r = BASE(p);
00716              displ = BYTES_TO_WORDS(HBLKDISPL(r));
00717              if (r == 0) hhdr = 0;
00718             } else {
00719               hhdr = 0;
00720             }
00721 #        else
00722            /* map already reflects interior pointers */
00723            hhdr = 0;
00724 #        endif
00725         } else {
00726           displ = BYTES_TO_WORDS(displ);
00727           displ -= map_entry;
00728           r = (word)((word *)(HBLKPTR(p)) + displ);
00729         }
00730     }
00731     /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
00732     /* displ is the word index within the block.         */
00733     if (hhdr == 0) {
00734        if (interior_ptrs) {
00735 #          ifdef PRINT_BLACK_LIST
00736              GC_add_to_black_list_stack(p, source);
00737 #          else
00738              GC_add_to_black_list_stack(p);
00739 #          endif
00740        } else {
00741            GC_ADD_TO_BLACK_LIST_NORMAL(p, source);
00742 #          undef source  /* In case we had to define it. */
00743        }
00744     } else {
00745        if (!mark_bit_from_hdr(hhdr, displ)) {
00746            set_mark_bit_from_hdr(hhdr, displ);
00747            PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
00748                     &(GC_mark_stack[GC_mark_stack_size]));
00749        }
00750     }
00751 }
00752 
00753 # ifdef TRACE_BUF
00754 
00755 # define TRACE_ENTRIES 1000
00756 
00757 struct trace_entry {
00758     char * kind;
00759     word gc_no;
00760     word words_allocd;
00761     word arg1;
00762     word arg2;
00763 } GC_trace_buf[TRACE_ENTRIES];
00764 
00765 int GC_trace_buf_ptr = 0;
00766 
00767 void GC_add_trace_entry(char *kind, word arg1, word arg2)
00768 {
00769     GC_trace_buf[GC_trace_buf_ptr].kind = kind;
00770     GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
00771     GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
00772     GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
00773     GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
00774     GC_trace_buf_ptr++;
00775     if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
00776 }
00777 
00778 void GC_print_trace(word gc_no, GC_bool lock)
00779 {
00780     int i;
00781     struct trace_entry *p;
00782     
00783     if (lock) LOCK();
00784     for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
00785        if (i < 0) i = TRACE_ENTRIES-1;
00786        p = GC_trace_buf + i;
00787        if (p -> gc_no < gc_no || p -> kind == 0) return;
00788        printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
00789               p -> kind, p -> gc_no, p -> words_allocd,
00790               (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
00791     }
00792     printf("Trace incomplete\n");
00793     if (lock) UNLOCK();
00794 }
00795 
00796 # endif /* TRACE_BUF */
00797 
00798 /*
00799  * A version of GC_push_all that treats all interior pointers as valid
00800  * and scans the entire region immediately, in case the contents
00801  * change.
00802  */
00803 void GC_push_all_eager(bottom, top)
00804 ptr_t bottom;
00805 ptr_t top;
00806 {
00807     word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
00808     word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
00809     register word *p;
00810     register word q;
00811     register word *lim;
00812     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
00813     register ptr_t least_ha = GC_least_plausible_heap_addr;
00814 #   define GC_greatest_plausible_heap_addr greatest_ha
00815 #   define GC_least_plausible_heap_addr least_ha
00816 
00817     if (top == 0) return;
00818     /* check all pointers in range and put in push if they appear */
00819     /* to be valid.                                       */
00820       lim = t - 1 /* longword */;
00821       for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
00822        q = *p;
00823        GC_PUSH_ONE_STACK(q, p);
00824       }
00825 #   undef GC_greatest_plausible_heap_addr
00826 #   undef GC_least_plausible_heap_addr
00827 }
00828 
00829 #ifndef THREADS
00830 /*
00831  * A version of GC_push_all that treats all interior pointers as valid
00832  * and scans part of the area immediately, to make sure that saved
00833  * register values are not lost.
00834  * Cold_gc_frame delimits the stack section that must be scanned
00835  * eagerly.  A zero value indicates that no eager scanning is needed.
00836  */
00837 void GC_push_all_stack_partially_eager(bottom, top, cold_gc_frame)
00838 ptr_t bottom;
00839 ptr_t top;
00840 ptr_t cold_gc_frame;
00841 {
00842 # ifdef ALL_INTERIOR_POINTERS
00843 #   define EAGER_BYTES 1024
00844     /* Push the hot end of the stack eagerly, so that register values   */
00845     /* saved inside GC frames are marked before they disappear.              */
00846     /* The rest of the marking can be deferred until later.           */
00847     if (0 == cold_gc_frame) {
00848        GC_push_all_stack(bottom, top);
00849        return;
00850     }
00851 #   ifdef STACK_GROWS_DOWN
00852        GC_push_all_eager(bottom, cold_gc_frame);
00853        GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
00854 #   else /* STACK_GROWS_UP */
00855        GC_push_all_eager(cold_gc_frame, top);
00856        GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
00857 #   endif /* STACK_GROWS_UP */
00858 # else
00859     GC_push_all_eager(bottom, top);
00860 # endif
00861 # ifdef TRACE_BUF
00862       GC_add_trace_entry("GC_push_all_stack", bottom, top);
00863 # endif
00864 }
00865 #endif /* !THREADS */
00866 
00867 void GC_push_all_stack(bottom, top)
00868 ptr_t bottom;
00869 ptr_t top;
00870 {
00871 # ifdef ALL_INTERIOR_POINTERS
00872     GC_push_all(bottom, top);
00873 # else
00874     GC_push_all_eager(bottom, top);
00875 # endif
00876 }
00877 
00878 #ifndef SMALL_CONFIG
00879 /* Push all objects reachable from marked objects in the given block */
00880 /* of size 1 objects.                                               */
00881 void GC_push_marked1(h, hhdr)
00882 struct hblk *h;
00883 register hdr * hhdr;
00884 {
00885     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
00886     register word *p;
00887     word *plim;
00888     register int i;
00889     register word q;
00890     register word mark_word;
00891     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
00892     register ptr_t least_ha = GC_least_plausible_heap_addr;
00893 #   define GC_greatest_plausible_heap_addr greatest_ha
00894 #   define GC_least_plausible_heap_addr least_ha
00895     
00896     p = (word *)(h->hb_body);
00897     plim = (word *)(((word)h) + HBLKSIZE);
00898 
00899     /* go through all words in block */
00900        while( p < plim )  {
00901            mark_word = *mark_word_addr++;
00902            i = 0;
00903            while(mark_word != 0) {
00904              if (mark_word & 1) {
00905                  q = p[i];
00906                  GC_PUSH_ONE_HEAP(q, p + i);
00907              }
00908              i++;
00909              mark_word >>= 1;
00910            }
00911            p += WORDSZ;
00912        }
00913 #   undef GC_greatest_plausible_heap_addr
00914 #   undef GC_least_plausible_heap_addr        
00915 }
00916 
00917 
00918 #ifndef UNALIGNED
00919 
00920 /* Push all objects reachable from marked objects in the given block */
00921 /* of size 2 objects.                                               */
00922 void GC_push_marked2(h, hhdr)
00923 struct hblk *h;
00924 register hdr * hhdr;
00925 {
00926     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
00927     register word *p;
00928     word *plim;
00929     register int i;
00930     register word q;
00931     register word mark_word;
00932     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
00933     register ptr_t least_ha = GC_least_plausible_heap_addr;
00934 #   define GC_greatest_plausible_heap_addr greatest_ha
00935 #   define GC_least_plausible_heap_addr least_ha
00936     
00937     p = (word *)(h->hb_body);
00938     plim = (word *)(((word)h) + HBLKSIZE);
00939 
00940     /* go through all words in block */
00941        while( p < plim )  {
00942            mark_word = *mark_word_addr++;
00943            i = 0;
00944            while(mark_word != 0) {
00945              if (mark_word & 1) {
00946                  q = p[i];
00947                  GC_PUSH_ONE_HEAP(q, p + i);
00948                  q = p[i+1];
00949                  GC_PUSH_ONE_HEAP(q, p + i);
00950              }
00951              i += 2;
00952              mark_word >>= 2;
00953            }
00954            p += WORDSZ;
00955        }
00956 #   undef GC_greatest_plausible_heap_addr
00957 #   undef GC_least_plausible_heap_addr        
00958 }
00959 
00960 /* Push all objects reachable from marked objects in the given block */
00961 /* of size 4 objects.                                               */
00962 /* There is a risk of mark stack overflow here.  But we handle that. */
00963 /* And only unmarked objects get pushed, so it's not very likely.    */
00964 void GC_push_marked4(h, hhdr)
00965 struct hblk *h;
00966 register hdr * hhdr;
00967 {
00968     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
00969     register word *p;
00970     word *plim;
00971     register int i;
00972     register word q;
00973     register word mark_word;
00974     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
00975     register ptr_t least_ha = GC_least_plausible_heap_addr;
00976 #   define GC_greatest_plausible_heap_addr greatest_ha
00977 #   define GC_least_plausible_heap_addr least_ha
00978     
00979     p = (word *)(h->hb_body);
00980     plim = (word *)(((word)h) + HBLKSIZE);
00981 
00982     /* go through all words in block */
00983        while( p < plim )  {
00984            mark_word = *mark_word_addr++;
00985            i = 0;
00986            while(mark_word != 0) {
00987              if (mark_word & 1) {
00988                  q = p[i];
00989                  GC_PUSH_ONE_HEAP(q, p + i);
00990                  q = p[i+1];
00991                  GC_PUSH_ONE_HEAP(q, p + i + 1);
00992                  q = p[i+2];
00993                  GC_PUSH_ONE_HEAP(q, p + i + 2);
00994                  q = p[i+3];
00995                  GC_PUSH_ONE_HEAP(q, p + i + 3);
00996              }
00997              i += 4;
00998              mark_word >>= 4;
00999            }
01000            p += WORDSZ;
01001        }
01002 #   undef GC_greatest_plausible_heap_addr
01003 #   undef GC_least_plausible_heap_addr        
01004 }
01005 
01006 #endif /* UNALIGNED */
01007 
01008 #endif /* SMALL_CONFIG */
01009 
01010 /* Push all objects reachable from marked objects in the given block */
01011 void GC_push_marked(h, hhdr)
01012 struct hblk *h;
01013 register hdr * hhdr;
01014 {
01015     register int sz = hhdr -> hb_sz;
01016     register word * p;
01017     register int word_no;
01018     register word * lim;
01019     register mse * GC_mark_stack_top_reg;
01020     register mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
01021     
01022     /* Some quick shortcuts: */
01023        { 
01024            struct obj_kind *ok = &(GC_obj_kinds[hhdr -> hb_obj_kind]);
01025            if ((0 | DS_LENGTH) == ok -> ok_descriptor
01026               && FALSE == ok -> ok_relocate_descr)
01027               return;
01028        }
01029         if (GC_block_empty(hhdr)/* nothing marked */) return;
01030 #   ifdef GATHERSTATS
01031         GC_n_rescuing_pages++;
01032 #   endif
01033     GC_objects_are_marked = TRUE;
01034     if (sz > MAXOBJSZ) {
01035         lim = (word *)(h + 1);
01036     } else {
01037         lim = (word *)(h + 1) - sz;
01038     }
01039     
01040     switch(sz) {
01041 #   if !defined(SMALL_CONFIG)    
01042      case 1:
01043        GC_push_marked1(h, hhdr);
01044        break;
01045 #   endif
01046 #   if !defined(SMALL_CONFIG) && !defined(UNALIGNED)
01047      case 2:
01048        GC_push_marked2(h, hhdr);
01049        break;
01050      case 4:
01051        GC_push_marked4(h, hhdr);
01052        break;
01053 #   endif       
01054      default:
01055       GC_mark_stack_top_reg = GC_mark_stack_top;
01056       for (p = (word *)h + HDR_WORDS, word_no = HDR_WORDS; p <= lim;
01057          p += sz, word_no += sz) {
01058          /* This ignores user specified mark procs.  This currently   */
01059          /* doesn't matter, since marking from the whole object              */
01060          /* is always sufficient, and we will eventually use the user */
01061          /* mark proc to avoid any bogus pointers.                    */
01062          if (mark_bit_from_hdr(hhdr, word_no)) {
01063            /* Mark from fields inside the object */
01064              PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
01065 #           ifdef GATHERSTATS
01066               /* Subtract this object from total, since it was */
01067               /* added in twice.                               */
01068               GC_composite_in_use -= sz;
01069 #           endif
01070          }
01071       }
01072       GC_mark_stack_top = GC_mark_stack_top_reg;
01073     }
01074 }
01075 
01076 #ifndef SMALL_CONFIG
01077 /* Test whether any page in the given block is dirty    */
01078 GC_bool GC_block_was_dirty(h, hhdr)
01079 struct hblk *h;
01080 register hdr * hhdr;
01081 {
01082     register int sz = hhdr -> hb_sz;
01083     
01084     if (sz < MAXOBJSZ) {
01085          return(GC_page_was_dirty(h));
01086     } else {
01087         register ptr_t p = (ptr_t)h;
01088          sz += HDR_WORDS;
01089          sz = WORDS_TO_BYTES(sz);
01090          while (p < (ptr_t)h + sz) {
01091              if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
01092              p += HBLKSIZE;
01093          }
01094          return(FALSE);
01095     }
01096 }
01097 #endif /* SMALL_CONFIG */
01098 
01099 /* Similar to GC_push_next_marked, but return address of next block   */
01100 struct hblk * GC_push_next_marked(h)
01101 struct hblk *h;
01102 {
01103     register hdr * hhdr;
01104     
01105     h = GC_next_block(h);
01106     if (h == 0) return(0);
01107     hhdr = HDR(h);
01108     GC_push_marked(h, hhdr);
01109     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
01110 }
01111 
01112 #ifndef SMALL_CONFIG
01113 /* Identical to above, but mark only from dirty pages   */
01114 struct hblk * GC_push_next_marked_dirty(h)
01115 struct hblk *h;
01116 {
01117     register hdr * hhdr = HDR(h);
01118     
01119     if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
01120     for (;;) {
01121         h = GC_next_block(h);
01122         if (h == 0) return(0);
01123         hhdr = HDR(h);
01124 #      ifdef STUBBORN_ALLOC
01125           if (hhdr -> hb_obj_kind == STUBBORN) {
01126             if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
01127                 break;
01128             }
01129           } else {
01130             if (GC_block_was_dirty(h, hhdr)) break;
01131           }
01132 #      else
01133          if (GC_block_was_dirty(h, hhdr)) break;
01134 #      endif
01135         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
01136     }
01137     GC_push_marked(h, hhdr);
01138     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
01139 }
01140 #endif
01141 
01142 /* Similar to above, but for uncollectable pages.  Needed since we    */
01143 /* do not clear marks for such pages, even for full collections.      */
01144 struct hblk * GC_push_next_marked_uncollectable(h)
01145 struct hblk *h;
01146 {
01147     register hdr * hhdr = HDR(h);
01148     
01149     for (;;) {
01150         h = GC_next_block(h);
01151         if (h == 0) return(0);
01152         hhdr = HDR(h);
01153        if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
01154         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
01155     }
01156     GC_push_marked(h, hhdr);
01157     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
01158 }
01159 
01160