/* * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers * Copyright (c) 1991-1995 by Xerox Corporation. All rights reserved. * * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. * * Permission is hereby granted to use or copy this program * for any purpose, provided the above notices are retained on all copies. * Permission to modify the code and to distribute modified code is granted, * provided the above notices are retained, and a notice that the code was * modified is included with the above copyright notice. * */ # include # include "gc_priv.h" # include "gc_mark.h" /* We put this here to minimize the risk of inlining. */ /*VARARGS*/ #ifdef __WATCOMC__ void GC_noop(void *p, ...) {} #else void GC_noop() {} #endif /* Single argument version, robust against whole program analysis. */ void GC_noop1(x) word x; { static VOLATILE word sink; sink = x; } /* mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0} -- declared in gc_priv.h */ word GC_n_mark_procs = 0; /* Initialize GC_obj_kinds properly and standard free lists properly. */ /* This must be done statically since they may be accessed before */ /* GC_init is called. */ /* It's done here, since we need to deal with mark descriptors. */ struct obj_kind GC_obj_kinds[MAXOBJKINDS] = { /* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */, 0 | DS_LENGTH, FALSE, FALSE }, /* NORMAL */ { &GC_objfreelist[0], 0, # if defined(ADD_BYTE_AT_END) && ALIGNMENT > DS_TAGS (word)(-ALIGNMENT) | DS_LENGTH, # else 0 | DS_LENGTH, # endif TRUE /* add length to descr */, TRUE }, /* UNCOLLECTABLE */ { &GC_uobjfreelist[0], 0, 0 | DS_LENGTH, TRUE /* add length to descr */, TRUE }, # ifdef ATOMIC_UNCOLLECTABLE /* AUNCOLLECTABLE */ { &GC_auobjfreelist[0], 0, 0 | DS_LENGTH, FALSE /* add length to descr */, FALSE }, # endif # ifdef STUBBORN_ALLOC /*STUBBORN*/ { &GC_sobjfreelist[0], 0, 0 | DS_LENGTH, TRUE /* add length to descr */, TRUE }, # endif }; # ifdef ATOMIC_UNCOLLECTABLE # ifdef STUBBORN_ALLOC int GC_n_kinds = 5; # else int GC_n_kinds = 4; # endif # else # ifdef STUBBORN_ALLOC int GC_n_kinds = 4; # else int GC_n_kinds = 3; # endif # endif # ifndef INITIAL_MARK_STACK_SIZE # define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE) /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a */ /* multiple of HBLKSIZE. */ /* The incremental collector actually likes a larger */ /* size, since it want to push all marked dirty objs */ /* before marking anything new. Currently we let it */ /* grow dynamically. */ # endif /* * Limits of stack for GC_mark routine. * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still * need to be marked from. */ word GC_n_rescuing_pages; /* Number of dirty pages we marked from */ /* excludes ptrfree pages, etc. */ mse * GC_mark_stack; word GC_mark_stack_size = 0; mse * GC_mark_stack_top; static struct hblk * scan_ptr; mark_state_t GC_mark_state = MS_NONE; GC_bool GC_mark_stack_too_small = FALSE; GC_bool GC_objects_are_marked = FALSE; /* Are there collectable marked */ /* objects in the heap? */ /* Is a collection in progress? Note that this can return true in the */ /* nonincremental case, if a collection has been abandoned and the */ /* mark state is now MS_INVALID. */ GC_bool GC_collection_in_progress() { return(GC_mark_state != MS_NONE); } /* clear all mark bits in the header */ void GC_clear_hdr_marks(hhdr) register hdr * hhdr; { BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word)); } /* Set all mark bits in the header. Used for uncollectable blocks. */ void GC_set_hdr_marks(hhdr) register hdr * hhdr; { register int i; for (i = 0; i < MARK_BITS_SZ; ++i) { hhdr -> hb_marks[i] = ONES; } } /* * Clear all mark bits associated with block h. */ /*ARGSUSED*/ static void clear_marks_for_block(h, dummy) struct hblk *h; word dummy; { register hdr * hhdr = HDR(h); if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return; /* Mark bit for these is cleared only once the object is */ /* explicitly deallocated. This either frees the block, or */ /* the bit is cleared once the object is on the free list. */ GC_clear_hdr_marks(hhdr); } /* Slow but general routines for setting/clearing/asking about mark bits */ void GC_set_mark_bit(p) ptr_t p; { register struct hblk *h = HBLKPTR(p); register hdr * hhdr = HDR(h); register int word_no = (word *)p - (word *)h; set_mark_bit_from_hdr(hhdr, word_no); } void GC_clear_mark_bit(p) ptr_t p; { register struct hblk *h = HBLKPTR(p); register hdr * hhdr = HDR(h); register int word_no = (word *)p - (word *)h; clear_mark_bit_from_hdr(hhdr, word_no); } GC_bool GC_is_marked(p) ptr_t p; { register struct hblk *h = HBLKPTR(p); register hdr * hhdr = HDR(h); register int word_no = (word *)p - (word *)h; return(mark_bit_from_hdr(hhdr, word_no)); } /* * Clear mark bits in all allocated heap blocks. This invalidates * the marker invariant, and sets GC_mark_state to reflect this. * (This implicitly starts marking to reestablish the invariant.) */ void GC_clear_marks() { GC_apply_to_all_blocks(clear_marks_for_block, (word)0); GC_objects_are_marked = FALSE; GC_mark_state = MS_INVALID; scan_ptr = 0; # ifdef GATHERSTATS /* Counters reflect currently marked objects: reset here */ GC_composite_in_use = 0; GC_atomic_in_use = 0; # endif } /* Initiate a garbage collection. Initiates a full collection if the */ /* mark state is invalid. */ /*ARGSUSED*/ void GC_initiate_gc() { if (GC_dirty_maintained) GC_read_dirty(); # ifdef STUBBORN_ALLOC GC_read_changed(); # endif # ifdef CHECKSUMS { extern void GC_check_dirty(); if (GC_dirty_maintained) GC_check_dirty(); } # endif # ifdef GATHERSTATS GC_n_rescuing_pages = 0; # endif if (GC_mark_state == MS_NONE) { GC_mark_state = MS_PUSH_RESCUERS; } else if (GC_mark_state != MS_INVALID) { ABORT("unexpected state"); } /* else this is really a full collection, and mark */ /* bits are invalid. */ scan_ptr = 0; } static void alloc_mark_stack(); /* Perform a small amount of marking. */ /* We try to touch roughly a page of memory. */ /* Return TRUE if we just finished a mark phase. */ /* Cold_gc_frame is an address inside a GC frame that */ /* remains valid until all marking is complete. */ /* A zero value indicates that it's OK to miss some */ /* register values. */ GC_bool GC_mark_some(cold_gc_frame) ptr_t cold_gc_frame; { switch(GC_mark_state) { case MS_NONE: return(FALSE); case MS_PUSH_RESCUERS: if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size - INITIAL_MARK_STACK_SIZE/2) { /* Go ahead and mark, even though that might cause us to */ /* see more marked dirty objects later on. Avoid this */ /* in the future. */ GC_mark_stack_too_small = TRUE; GC_mark_from_mark_stack(); return(FALSE); } else { scan_ptr = GC_push_next_marked_dirty(scan_ptr); if (scan_ptr == 0) { # ifdef PRINTSTATS GC_printf1("Marked from %lu dirty pages\n", (unsigned long)GC_n_rescuing_pages); # endif GC_push_roots(FALSE, cold_gc_frame); GC_objects_are_marked = TRUE; if (GC_mark_state != MS_INVALID) { GC_mark_state = MS_ROOTS_PUSHED; } } } return(FALSE); case MS_PUSH_UNCOLLECTABLE: if (GC_mark_stack_top >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) { GC_mark_from_mark_stack(); return(FALSE); } else { scan_ptr = GC_push_next_marked_uncollectable(scan_ptr); if (scan_ptr == 0) { GC_push_roots(TRUE, cold_gc_frame); GC_objects_are_marked = TRUE; if (GC_mark_state != MS_INVALID) { GC_mark_state = MS_ROOTS_PUSHED; } } } return(FALSE); case MS_ROOTS_PUSHED: if (GC_mark_stack_top >= GC_mark_stack) { GC_mark_from_mark_stack(); return(FALSE); } else { GC_mark_state = MS_NONE; if (GC_mark_stack_too_small) { alloc_mark_stack(2*GC_mark_stack_size); } return(TRUE); } case MS_INVALID: case MS_PARTIALLY_INVALID: if (!GC_objects_are_marked) { GC_mark_state = MS_PUSH_UNCOLLECTABLE; return(FALSE); } if (GC_mark_stack_top >= GC_mark_stack) { GC_mark_from_mark_stack(); return(FALSE); } if (scan_ptr == 0 && GC_mark_state == MS_INVALID) { /* About to start a heap scan for marked objects. */ /* Mark stack is empty. OK to reallocate. */ if (GC_mark_stack_too_small) { alloc_mark_stack(2*GC_mark_stack_size); } GC_mark_state = MS_PARTIALLY_INVALID; } scan_ptr = GC_push_next_marked(scan_ptr); if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) { GC_push_roots(TRUE, cold_gc_frame); GC_objects_are_marked = TRUE; if (GC_mark_state != MS_INVALID) { GC_mark_state = MS_ROOTS_PUSHED; } } return(FALSE); default: ABORT("GC_mark_some: bad state"); return(FALSE); } } GC_bool GC_mark_stack_empty() { return(GC_mark_stack_top < GC_mark_stack); } #ifdef PROF_MARKER word GC_prof_array[10]; # define PROF(n) GC_prof_array[n]++ #else # define PROF(n) #endif /* Given a pointer to someplace other than a small object page or the */ /* first page of a large object, return a pointer either to the */ /* start of the large object or NIL. */ /* In the latter case black list the address current. */ /* Returns NIL without black listing if current points to a block */ /* with IGNORE_OFF_PAGE set. */ /*ARGSUSED*/ # ifdef PRINT_BLACK_LIST word GC_find_start(current, hhdr, source) word source; # else word GC_find_start(current, hhdr) # define source 0 # endif register word current; register hdr * hhdr; { # ifdef ALL_INTERIOR_POINTERS if (hhdr != 0) { register word orig = current; current = (word)HBLKPTR(current) + HDR_BYTES; do { current = current - HBLKSIZE*(word)hhdr; hhdr = HDR(current); } while(IS_FORWARDING_ADDR_OR_NIL(hhdr)); /* current points to the start of the large object */ if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0); if ((word *)orig - (word *)current >= (ptrdiff_t)(hhdr->hb_sz)) { /* Pointer past the end of the block */ GC_ADD_TO_BLACK_LIST_NORMAL(orig, source); return(0); } return(current); } else { GC_ADD_TO_BLACK_LIST_NORMAL(current, source); return(0); } # else GC_ADD_TO_BLACK_LIST_NORMAL(current, source); return(0); # endif # undef source } void GC_invalidate_mark_state() { GC_mark_state = MS_INVALID; GC_mark_stack_top = GC_mark_stack-1; } mse * GC_signal_mark_stack_overflow(msp) mse * msp; { GC_mark_state = MS_INVALID; GC_mark_stack_too_small = TRUE; # ifdef PRINTSTATS GC_printf1("Mark stack overflow; current size = %lu entries\n", GC_mark_stack_size); # endif return(msp-INITIAL_MARK_STACK_SIZE/8); } /* * Mark objects pointed to by the regions described by * mark stack entries between GC_mark_stack and GC_mark_stack_top, * inclusive. Assumes the upper limit of a mark stack entry * is never 0. A mark stack entry never has size 0. * We try to traverse on the order of a hblk of memory before we return. * Caller is responsible for calling this until the mark stack is empty. */ void GC_mark_from_mark_stack() { mse * GC_mark_stack_reg = GC_mark_stack; mse * GC_mark_stack_top_reg = GC_mark_stack_top; mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]); int credit = HBLKSIZE; /* Remaining credit for marking work */ register word * current_p; /* Pointer to current candidate ptr. */ register word current; /* Candidate pointer. */ register word * limit; /* (Incl) limit of current candidate */ /* range */ register word descr; register ptr_t greatest_ha = GC_greatest_plausible_heap_addr; register ptr_t least_ha = GC_least_plausible_heap_addr; # define SPLIT_RANGE_WORDS 128 /* Must be power of 2. */ GC_objects_are_marked = TRUE; # ifdef OS2 /* Use untweaked version to circumvent compiler problem */ while (GC_mark_stack_top_reg >= GC_mark_stack_reg && credit >= 0) { # else while ((((ptr_t)GC_mark_stack_top_reg - (ptr_t)GC_mark_stack_reg) | credit) >= 0) { # endif current_p = GC_mark_stack_top_reg -> mse_start; retry: descr = GC_mark_stack_top_reg -> mse_descr; if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | DS_TAGS)) { word tag = descr & DS_TAGS; switch(tag) { case DS_LENGTH: /* Large length. */ /* Process part of the range to avoid pushing too much on the */ /* stack. */ GC_mark_stack_top_reg -> mse_start = limit = current_p + SPLIT_RANGE_WORDS-1; GC_mark_stack_top_reg -> mse_descr -= WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1); /* Make sure that pointers overlapping the two ranges are */ /* considered. */ limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT); break; case DS_BITMAP: GC_mark_stack_top_reg--; descr &= ~DS_TAGS; credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */ while (descr != 0) { if ((signed_word)descr < 0) { current = *current_p; if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) { PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit, current_p, exit1); } } descr <<= 1; ++ current_p; } continue; case DS_PROC: GC_mark_stack_top_reg--; credit -= PROC_BYTES; GC_mark_stack_top_reg = (*PROC(descr)) (current_p, GC_mark_stack_top_reg, mark_stack_limit, ENV(descr)); continue; case DS_PER_OBJECT: GC_mark_stack_top_reg -> mse_descr = *(word *)((ptr_t)current_p + descr - tag); goto retry; } } else { GC_mark_stack_top_reg--; limit = (word *)(((ptr_t)current_p) + (word)descr); } /* The simple case in which we're scanning a range. */ credit -= (ptr_t)limit - (ptr_t)current_p; limit -= 1; while (current_p <= limit) { current = *current_p; if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) { PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit, current_p, exit2); } current_p = (word *)((char *)current_p + ALIGNMENT); } } GC_mark_stack_top = GC_mark_stack_top_reg; } /* Allocate or reallocate space for mark stack of size s words */ /* May silently fail. */ static void alloc_mark_stack(n) word n; { mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct ms_entry)); GC_mark_stack_too_small = FALSE; if (GC_mark_stack_size != 0) { if (new_stack != 0) { word displ = (word)GC_mark_stack & (GC_page_size - 1); signed_word size = GC_mark_stack_size * sizeof(struct ms_entry); /* Recycle old space */ if (0 != displ) displ = GC_page_size - displ; size = (size - displ) & ~(GC_page_size - 1); if (size > 0) { GC_add_to_heap((struct hblk *) ((word)GC_mark_stack + displ), (word)size); } GC_mark_stack = new_stack; GC_mark_stack_size = n; # ifdef PRINTSTATS GC_printf1("Grew mark stack to %lu frames\n", (unsigned long) GC_mark_stack_size); # endif } else { # ifdef PRINTSTATS GC_printf1("Failed to grow mark stack to %lu frames\n", (unsigned long) n); # endif } } else { if (new_stack == 0) { GC_err_printf0("No space for mark stack\n"); EXIT(); } GC_mark_stack = new_stack; GC_mark_stack_size = n; } GC_mark_stack_top = GC_mark_stack-1; } void GC_mark_init() { alloc_mark_stack(INITIAL_MARK_STACK_SIZE); } /* * Push all locations between b and t onto the mark stack. * b is the first location to be checked. t is one past the last * location to be checked. * Should only be used if there is no possibility of mark stack * overflow. */ void GC_push_all(bottom, top) ptr_t bottom; ptr_t top; { register word length; bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1)); top = (ptr_t)(((word) top) & ~(ALIGNMENT-1)); if (top == 0 || bottom == top) return; GC_mark_stack_top++; if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) { ABORT("unexpected mark stack overflow"); } length = top - bottom; # if DS_TAGS > ALIGNMENT - 1 length += DS_TAGS; length &= ~DS_TAGS; # endif GC_mark_stack_top -> mse_start = (word *)bottom; GC_mark_stack_top -> mse_descr = length; } /* * Analogous to the above, but push only those pages that may have been * dirtied. A block h is assumed dirty if dirty_fn(h) != 0. * We use push_fn to actually push the block. * Will not overflow mark stack if push_fn pushes a small fixed number * of entries. (This is invoked only if push_fn pushes a single entry, * or if it marks each object before pushing it, thus ensuring progress * in the event of a stack overflow.) */ void GC_push_dirty(bottom, top, dirty_fn, push_fn) ptr_t bottom; ptr_t top; int (*dirty_fn)(/* struct hblk * h */); void (*push_fn)(/* ptr_t bottom, ptr_t top */); { register struct hblk * h; bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1)); top = (ptr_t)(((long) top) & ~(ALIGNMENT-1)); if (top == 0 || bottom == top) return; h = HBLKPTR(bottom + HBLKSIZE); if (top <= (ptr_t) h) { if ((*dirty_fn)(h-1)) { (*push_fn)(bottom, top); } return; } if ((*dirty_fn)(h-1)) { (*push_fn)(bottom, (ptr_t)h); } while ((ptr_t)(h+1) <= top) { if ((*dirty_fn)(h)) { if ((word)(GC_mark_stack_top - GC_mark_stack) > 3 * GC_mark_stack_size / 4) { /* Danger of mark stack overflow */ (*push_fn)((ptr_t)h, top); return; } else { (*push_fn)((ptr_t)h, (ptr_t)(h+1)); } } h++; } if ((ptr_t)h != top) { if ((*dirty_fn)(h)) { (*push_fn)((ptr_t)h, top); } } if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) { ABORT("unexpected mark stack overflow"); } } # ifndef SMALL_CONFIG void GC_push_conditional(bottom, top, all) ptr_t bottom; ptr_t top; int all; { if (all) { if (GC_dirty_maintained) { # ifdef PROC_VDB /* Pages that were never dirtied cannot contain pointers */ GC_push_dirty(bottom, top, GC_page_was_ever_dirty, GC_push_all); # else GC_push_all(bottom, top); # endif } else { GC_push_all(bottom, top); } } else { GC_push_dirty(bottom, top, GC_page_was_dirty, GC_push_all); } } #endif # ifdef MSWIN32 void __cdecl GC_push_one(p) # else void GC_push_one(p) # endif word p; { # ifdef NURSERY if (0 != GC_push_proc) { GC_push_proc(p); return; } # endif GC_PUSH_ONE_STACK(p, 0); } # ifdef __STDC__ # define BASE(p) (word)GC_base((void *)(p)) # else # define BASE(p) (word)GC_base((char *)(p)) # endif /* As above, but argument passed preliminary test. */ # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS) void GC_push_one_checked(p, interior_ptrs, source) ptr_t source; # else void GC_push_one_checked(p, interior_ptrs) # define source 0 # endif register word p; register GC_bool interior_ptrs; { register word r; register hdr * hhdr; register int displ; GET_HDR(p, hhdr); if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { if (hhdr != 0 && interior_ptrs) { r = BASE(p); hhdr = HDR(r); displ = BYTES_TO_WORDS(HBLKDISPL(r)); } else { hhdr = 0; } } else { register map_entry_type map_entry; displ = HBLKDISPL(p); map_entry = MAP_ENTRY((hhdr -> hb_map), displ); if (map_entry == OBJ_INVALID) { # ifndef ALL_INTERIOR_POINTERS if (interior_ptrs) { r = BASE(p); displ = BYTES_TO_WORDS(HBLKDISPL(r)); if (r == 0) hhdr = 0; } else { hhdr = 0; } # else /* map already reflects interior pointers */ hhdr = 0; # endif } else { displ = BYTES_TO_WORDS(displ); displ -= map_entry; r = (word)((word *)(HBLKPTR(p)) + displ); } } /* If hhdr != 0 then r == GC_base(p), only we did it faster. */ /* displ is the word index within the block. */ if (hhdr == 0) { if (interior_ptrs) { # ifdef PRINT_BLACK_LIST GC_add_to_black_list_stack(p, source); # else GC_add_to_black_list_stack(p); # endif } else { GC_ADD_TO_BLACK_LIST_NORMAL(p, source); # undef source /* In case we had to define it. */ } } else { if (!mark_bit_from_hdr(hhdr, displ)) { set_mark_bit_from_hdr(hhdr, displ); GC_STORE_BACK_PTR(source, (ptr_t)r); PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top, &(GC_mark_stack[GC_mark_stack_size])); } } } # ifdef TRACE_BUF # define TRACE_ENTRIES 1000 struct trace_entry { char * kind; word gc_no; word words_allocd; word arg1; word arg2; } GC_trace_buf[TRACE_ENTRIES]; int GC_trace_buf_ptr = 0; void GC_add_trace_entry(char *kind, word arg1, word arg2) { GC_trace_buf[GC_trace_buf_ptr].kind = kind; GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no; GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd; GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000; GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000; GC_trace_buf_ptr++; if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0; } void GC_print_trace(word gc_no, GC_bool lock) { int i; struct trace_entry *p; if (lock) LOCK(); for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) { if (i < 0) i = TRACE_ENTRIES-1; p = GC_trace_buf + i; if (p -> gc_no < gc_no || p -> kind == 0) return; printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n", p -> kind, p -> gc_no, p -> words_allocd, (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000); } printf("Trace incomplete\n"); if (lock) UNLOCK(); } # endif /* TRACE_BUF */ /* * A version of GC_push_all that treats all interior pointers as valid * and scans the entire region immediately, in case the contents * change. */ void GC_push_all_eager(bottom, top) ptr_t bottom; ptr_t top; { word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1)); word * t = (word *)(((long) top) & ~(ALIGNMENT-1)); register word *p; register word q; register word *lim; register ptr_t greatest_ha = GC_greatest_plausible_heap_addr; register ptr_t least_ha = GC_least_plausible_heap_addr; # define GC_greatest_plausible_heap_addr greatest_ha # define GC_least_plausible_heap_addr least_ha if (top == 0) return; /* check all pointers in range and put in push if they appear */ /* to be valid. */ lim = t - 1 /* longword */; for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) { q = *p; GC_PUSH_ONE_STACK(q, p); } # undef GC_greatest_plausible_heap_addr # undef GC_least_plausible_heap_addr } #ifndef THREADS /* * A version of GC_push_all that treats all interior pointers as valid * and scans part of the area immediately, to make sure that saved * register values are not lost. * Cold_gc_frame delimits the stack section that must be scanned * eagerly. A zero value indicates that no eager scanning is needed. */ void GC_push_all_stack_partially_eager(bottom, top, cold_gc_frame) ptr_t bottom; ptr_t top; ptr_t cold_gc_frame; { # ifdef ALL_INTERIOR_POINTERS # define EAGER_BYTES 1024 /* Push the hot end of the stack eagerly, so that register values */ /* saved inside GC frames are marked before they disappear. */ /* The rest of the marking can be deferred until later. */ if (0 == cold_gc_frame) { GC_push_all_stack(bottom, top); return; } # ifdef STACK_GROWS_DOWN GC_push_all_eager(bottom, cold_gc_frame); GC_push_all(cold_gc_frame - sizeof(ptr_t), top); # else /* STACK_GROWS_UP */ GC_push_all_eager(cold_gc_frame, top); GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t)); # endif /* STACK_GROWS_UP */ # else GC_push_all_eager(bottom, top); # endif # ifdef TRACE_BUF GC_add_trace_entry("GC_push_all_stack", bottom, top); # endif } #endif /* !THREADS */ void GC_push_all_stack(bottom, top) ptr_t bottom; ptr_t top; { # ifdef ALL_INTERIOR_POINTERS GC_push_all(bottom, top); # else GC_push_all_eager(bottom, top); # endif } #ifndef SMALL_CONFIG /* Push all objects reachable from marked objects in the given block */ /* of size 1 objects. */ void GC_push_marked1(h, hhdr) struct hblk *h; register hdr * hhdr; { word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]); register word *p; word *plim; register int i; register word q; register word mark_word; register ptr_t greatest_ha = GC_greatest_plausible_heap_addr; register ptr_t least_ha = GC_least_plausible_heap_addr; # define GC_greatest_plausible_heap_addr greatest_ha # define GC_least_plausible_heap_addr least_ha p = (word *)(h->hb_body); plim = (word *)(((word)h) + HBLKSIZE); /* go through all words in block */ while( p < plim ) { mark_word = *mark_word_addr++; i = 0; while(mark_word != 0) { if (mark_word & 1) { q = p[i]; GC_PUSH_ONE_HEAP(q, p + i); } i++; mark_word >>= 1; } p += WORDSZ; } # undef GC_greatest_plausible_heap_addr # undef GC_least_plausible_heap_addr } #ifndef UNALIGNED /* Push all objects reachable from marked objects in the given block */ /* of size 2 objects. */ void GC_push_marked2(h, hhdr) struct hblk *h; register hdr * hhdr; { word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]); register word *p; word *plim; register int i; register word q; register word mark_word; register ptr_t greatest_ha = GC_greatest_plausible_heap_addr; register ptr_t least_ha = GC_least_plausible_heap_addr; # define GC_greatest_plausible_heap_addr greatest_ha # define GC_least_plausible_heap_addr least_ha p = (word *)(h->hb_body); plim = (word *)(((word)h) + HBLKSIZE); /* go through all words in block */ while( p < plim ) { mark_word = *mark_word_addr++; i = 0; while(mark_word != 0) { if (mark_word & 1) { q = p[i]; GC_PUSH_ONE_HEAP(q, p + i); q = p[i+1]; GC_PUSH_ONE_HEAP(q, p + i); } i += 2; mark_word >>= 2; } p += WORDSZ; } # undef GC_greatest_plausible_heap_addr # undef GC_least_plausible_heap_addr } /* Push all objects reachable from marked objects in the given block */ /* of size 4 objects. */ /* There is a risk of mark stack overflow here. But we handle that. */ /* And only unmarked objects get pushed, so it's not very likely. */ void GC_push_marked4(h, hhdr) struct hblk *h; register hdr * hhdr; { word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]); register word *p; word *plim; register int i; register word q; register word mark_word; register ptr_t greatest_ha = GC_greatest_plausible_heap_addr; register ptr_t least_ha = GC_least_plausible_heap_addr; # define GC_greatest_plausible_heap_addr greatest_ha # define GC_least_plausible_heap_addr least_ha p = (word *)(h->hb_body); plim = (word *)(((word)h) + HBLKSIZE); /* go through all words in block */ while( p < plim ) { mark_word = *mark_word_addr++; i = 0; while(mark_word != 0) { if (mark_word & 1) { q = p[i]; GC_PUSH_ONE_HEAP(q, p + i); q = p[i+1]; GC_PUSH_ONE_HEAP(q, p + i + 1); q = p[i+2]; GC_PUSH_ONE_HEAP(q, p + i + 2); q = p[i+3]; GC_PUSH_ONE_HEAP(q, p + i + 3); } i += 4; mark_word >>= 4; } p += WORDSZ; } # undef GC_greatest_plausible_heap_addr # undef GC_least_plausible_heap_addr } #endif /* UNALIGNED */ #endif /* SMALL_CONFIG */ /* Push all objects reachable from marked objects in the given block */ void GC_push_marked(h, hhdr) struct hblk *h; register hdr * hhdr; { register int sz = hhdr -> hb_sz; register word * p; register int word_no; register word * lim; register mse * GC_mark_stack_top_reg; register mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]); /* Some quick shortcuts: */ { struct obj_kind *ok = &(GC_obj_kinds[hhdr -> hb_obj_kind]); if ((0 | DS_LENGTH) == ok -> ok_descriptor && FALSE == ok -> ok_relocate_descr) return; } if (GC_block_empty(hhdr)/* nothing marked */) return; # ifdef GATHERSTATS GC_n_rescuing_pages++; # endif GC_objects_are_marked = TRUE; if (sz > MAXOBJSZ) { lim = (word *)(h + 1); } else { lim = (word *)(h + 1) - sz; } switch(sz) { # if !defined(SMALL_CONFIG) case 1: GC_push_marked1(h, hhdr); break; # endif # if !defined(SMALL_CONFIG) && !defined(UNALIGNED) case 2: GC_push_marked2(h, hhdr); break; case 4: GC_push_marked4(h, hhdr); break; # endif default: GC_mark_stack_top_reg = GC_mark_stack_top; for (p = (word *)h + HDR_WORDS, word_no = HDR_WORDS; p <= lim; p += sz, word_no += sz) { /* This ignores user specified mark procs. This currently */ /* doesn't matter, since marking from the whole object */ /* is always sufficient, and we will eventually use the user */ /* mark proc to avoid any bogus pointers. */ if (mark_bit_from_hdr(hhdr, word_no)) { /* Mark from fields inside the object */ PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit); # ifdef GATHERSTATS /* Subtract this object from total, since it was */ /* added in twice. */ GC_composite_in_use -= sz; # endif } } GC_mark_stack_top = GC_mark_stack_top_reg; } } #ifndef SMALL_CONFIG /* Test whether any page in the given block is dirty */ GC_bool GC_block_was_dirty(h, hhdr) struct hblk *h; register hdr * hhdr; { register int sz = hhdr -> hb_sz; if (sz < MAXOBJSZ) { return(GC_page_was_dirty(h)); } else { register ptr_t p = (ptr_t)h; sz += HDR_WORDS; sz = WORDS_TO_BYTES(sz); while (p < (ptr_t)h + sz) { if (GC_page_was_dirty((struct hblk *)p)) return(TRUE); p += HBLKSIZE; } return(FALSE); } } #endif /* SMALL_CONFIG */ /* Similar to GC_push_next_marked, but return address of next block */ struct hblk * GC_push_next_marked(h) struct hblk *h; { register hdr * hhdr; h = GC_next_used_block(h); if (h == 0) return(0); hhdr = HDR(h); GC_push_marked(h, hhdr); return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz)); } #ifndef SMALL_CONFIG /* Identical to above, but mark only from dirty pages */ struct hblk * GC_push_next_marked_dirty(h) struct hblk *h; { register hdr * hhdr; if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); } for (;;) { h = GC_next_used_block(h); if (h == 0) return(0); hhdr = HDR(h); # ifdef STUBBORN_ALLOC if (hhdr -> hb_obj_kind == STUBBORN) { if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) { break; } } else { if (GC_block_was_dirty(h, hhdr)) break; } # else if (GC_block_was_dirty(h, hhdr)) break; # endif h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz); } GC_push_marked(h, hhdr); return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz)); } #endif /* Similar to above, but for uncollectable pages. Needed since we */ /* do not clear marks for such pages, even for full collections. */ struct hblk * GC_push_next_marked_uncollectable(h) struct hblk *h; { register hdr * hhdr = HDR(h); for (;;) { h = GC_next_used_block(h); if (h == 0) return(0); hhdr = HDR(h); if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break; h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz); } GC_push_marked(h, hhdr); return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz)); }