3 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
4 * Copyright (c) 1991-1995 by Xerox Corporation. All rights reserved.
6 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
7 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
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.
22 /* We put this here to minimize the risk of inlining. */
25 void GC_noop(void *p
, ...) {}
30 /* Single argument version, robust against whole program analysis. */
34 static VOLATILE word sink
;
39 /* mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0} -- declared in gc_priv.h */
41 word GC_n_mark_procs
= 0;
43 /* Initialize GC_obj_kinds properly and standard free lists properly. */
44 /* This must be done statically since they may be accessed before */
45 /* GC_init is called. */
46 /* It's done here, since we need to deal with mark descriptors. */
47 struct obj_kind GC_obj_kinds
[MAXOBJKINDS
] = {
48 /* PTRFREE */ { &GC_aobjfreelist
[0], 0 /* filled in dynamically */,
49 0 | DS_LENGTH
, FALSE
, FALSE
},
50 /* NORMAL */ { &GC_objfreelist
[0], 0,
51 # if defined(ADD_BYTE_AT_END) && ALIGNMENT > DS_TAGS
52 (word
)(-ALIGNMENT
) | DS_LENGTH
,
56 TRUE
/* add length to descr */, TRUE
},
58 { &GC_uobjfreelist
[0], 0,
59 0 | DS_LENGTH
, TRUE
/* add length to descr */, TRUE
},
60 # ifdef ATOMIC_UNCOLLECTABLE
62 { &GC_auobjfreelist
[0], 0,
63 0 | DS_LENGTH
, FALSE
/* add length to descr */, FALSE
},
65 # ifdef STUBBORN_ALLOC
66 /*STUBBORN*/ { &GC_sobjfreelist
[0], 0,
67 0 | DS_LENGTH
, TRUE
/* add length to descr */, TRUE
},
71 # ifdef ATOMIC_UNCOLLECTABLE
72 # ifdef STUBBORN_ALLOC
78 # ifdef STUBBORN_ALLOC
86 # ifndef INITIAL_MARK_STACK_SIZE
87 # define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
88 /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a */
89 /* multiple of HBLKSIZE. */
90 /* The incremental collector actually likes a larger */
91 /* size, since it want to push all marked dirty objs */
92 /* before marking anything new. Currently we let it */
93 /* grow dynamically. */
97 * Limits of stack for GC_mark routine.
98 * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
99 * need to be marked from.
102 word GC_n_rescuing_pages
; /* Number of dirty pages we marked from */
103 /* excludes ptrfree pages, etc. */
107 word GC_mark_stack_size
= 0;
109 mse
* GC_mark_stack_top
;
111 static struct hblk
* scan_ptr
;
113 mark_state_t GC_mark_state
= MS_NONE
;
115 GC_bool GC_mark_stack_too_small
= FALSE
;
117 GC_bool GC_objects_are_marked
= FALSE
; /* Are there collectable marked */
118 /* objects in the heap? */
120 /* Is a collection in progress? Note that this can return true in the */
121 /* nonincremental case, if a collection has been abandoned and the */
122 /* mark state is now MS_INVALID. */
123 GC_bool
GC_collection_in_progress()
125 return(GC_mark_state
!= MS_NONE
);
128 /* clear all mark bits in the header */
129 void GC_clear_hdr_marks(hhdr
)
132 BZERO(hhdr
-> hb_marks
, MARK_BITS_SZ
*sizeof(word
));
135 /* Set all mark bits in the header. Used for uncollectable blocks. */
136 void GC_set_hdr_marks(hhdr
)
141 for (i
= 0; i
< MARK_BITS_SZ
; ++i
) {
142 hhdr
-> hb_marks
[i
] = ONES
;
147 * Clear all mark bits associated with block h.
150 static void clear_marks_for_block(h
, dummy
)
154 register hdr
* hhdr
= HDR(h
);
156 if (IS_UNCOLLECTABLE(hhdr
-> hb_obj_kind
)) return;
157 /* Mark bit for these is cleared only once the object is */
158 /* explicitly deallocated. This either frees the block, or */
159 /* the bit is cleared once the object is on the free list. */
160 GC_clear_hdr_marks(hhdr
);
163 /* Slow but general routines for setting/clearing/asking about mark bits */
164 void GC_set_mark_bit(p
)
167 register struct hblk
*h
= HBLKPTR(p
);
168 register hdr
* hhdr
= HDR(h
);
169 register int word_no
= (word
*)p
- (word
*)h
;
171 set_mark_bit_from_hdr(hhdr
, word_no
);
174 void GC_clear_mark_bit(p
)
177 register struct hblk
*h
= HBLKPTR(p
);
178 register hdr
* hhdr
= HDR(h
);
179 register int word_no
= (word
*)p
- (word
*)h
;
181 clear_mark_bit_from_hdr(hhdr
, word_no
);
184 GC_bool
GC_is_marked(p
)
187 register struct hblk
*h
= HBLKPTR(p
);
188 register hdr
* hhdr
= HDR(h
);
189 register int word_no
= (word
*)p
- (word
*)h
;
191 return(mark_bit_from_hdr(hhdr
, word_no
));
196 * Clear mark bits in all allocated heap blocks. This invalidates
197 * the marker invariant, and sets GC_mark_state to reflect this.
198 * (This implicitly starts marking to reestablish the invariant.)
200 void GC_clear_marks()
202 GC_apply_to_all_blocks(clear_marks_for_block
, (word
)0);
203 GC_objects_are_marked
= FALSE
;
204 GC_mark_state
= MS_INVALID
;
207 /* Counters reflect currently marked objects: reset here */
208 GC_composite_in_use
= 0;
209 GC_atomic_in_use
= 0;
214 /* Initiate a garbage collection. Initiates a full collection if the */
215 /* mark state is invalid. */
217 void GC_initiate_gc()
219 if (GC_dirty_maintained
) GC_read_dirty();
220 # ifdef STUBBORN_ALLOC
225 extern void GC_check_dirty();
227 if (GC_dirty_maintained
) GC_check_dirty();
231 GC_n_rescuing_pages
= 0;
233 if (GC_mark_state
== MS_NONE
) {
234 GC_mark_state
= MS_PUSH_RESCUERS
;
235 } else if (GC_mark_state
!= MS_INVALID
) {
236 ABORT("unexpected state");
237 } /* else this is really a full collection, and mark */
238 /* bits are invalid. */
243 static void alloc_mark_stack();
245 /* Perform a small amount of marking. */
246 /* We try to touch roughly a page of memory. */
247 /* Return TRUE if we just finished a mark phase. */
248 /* Cold_gc_frame is an address inside a GC frame that */
249 /* remains valid until all marking is complete. */
250 /* A zero value indicates that it's OK to miss some */
251 /* register values. */
252 GC_bool
GC_mark_some(cold_gc_frame
)
255 switch(GC_mark_state
) {
259 case MS_PUSH_RESCUERS
:
260 if (GC_mark_stack_top
261 >= GC_mark_stack
+ GC_mark_stack_size
262 - INITIAL_MARK_STACK_SIZE
/2) {
263 /* Go ahead and mark, even though that might cause us to */
264 /* see more marked dirty objects later on. Avoid this */
266 GC_mark_stack_too_small
= TRUE
;
267 GC_mark_from_mark_stack();
270 scan_ptr
= GC_push_next_marked_dirty(scan_ptr
);
273 GC_printf1("Marked from %lu dirty pages\n",
274 (unsigned long)GC_n_rescuing_pages
);
276 GC_push_roots(FALSE
, cold_gc_frame
);
277 GC_objects_are_marked
= TRUE
;
278 if (GC_mark_state
!= MS_INVALID
) {
279 GC_mark_state
= MS_ROOTS_PUSHED
;
285 case MS_PUSH_UNCOLLECTABLE
:
286 if (GC_mark_stack_top
287 >= GC_mark_stack
+ INITIAL_MARK_STACK_SIZE
/4) {
288 GC_mark_from_mark_stack();
291 scan_ptr
= GC_push_next_marked_uncollectable(scan_ptr
);
293 GC_push_roots(TRUE
, cold_gc_frame
);
294 GC_objects_are_marked
= TRUE
;
295 if (GC_mark_state
!= MS_INVALID
) {
296 GC_mark_state
= MS_ROOTS_PUSHED
;
302 case MS_ROOTS_PUSHED
:
303 if (GC_mark_stack_top
>= GC_mark_stack
) {
304 GC_mark_from_mark_stack();
307 GC_mark_state
= MS_NONE
;
308 if (GC_mark_stack_too_small
) {
309 alloc_mark_stack(2*GC_mark_stack_size
);
315 case MS_PARTIALLY_INVALID
:
316 if (!GC_objects_are_marked
) {
317 GC_mark_state
= MS_PUSH_UNCOLLECTABLE
;
320 if (GC_mark_stack_top
>= GC_mark_stack
) {
321 GC_mark_from_mark_stack();
324 if (scan_ptr
== 0 && GC_mark_state
== MS_INVALID
) {
325 /* About to start a heap scan for marked objects. */
326 /* Mark stack is empty. OK to reallocate. */
327 if (GC_mark_stack_too_small
) {
328 alloc_mark_stack(2*GC_mark_stack_size
);
330 GC_mark_state
= MS_PARTIALLY_INVALID
;
332 scan_ptr
= GC_push_next_marked(scan_ptr
);
333 if (scan_ptr
== 0 && GC_mark_state
== MS_PARTIALLY_INVALID
) {
334 GC_push_roots(TRUE
, cold_gc_frame
);
335 GC_objects_are_marked
= TRUE
;
336 if (GC_mark_state
!= MS_INVALID
) {
337 GC_mark_state
= MS_ROOTS_PUSHED
;
342 ABORT("GC_mark_some: bad state");
348 GC_bool
GC_mark_stack_empty()
350 return(GC_mark_stack_top
< GC_mark_stack
);
354 word GC_prof_array
[10];
355 # define PROF(n) GC_prof_array[n]++
360 /* Given a pointer to someplace other than a small object page or the */
361 /* first page of a large object, return a pointer either to the */
362 /* start of the large object or NIL. */
363 /* In the latter case black list the address current. */
364 /* Returns NIL without black listing if current points to a block */
365 /* with IGNORE_OFF_PAGE set. */
367 # ifdef PRINT_BLACK_LIST
368 word
GC_find_start(current
, hhdr
, source
)
371 word
GC_find_start(current
, hhdr
)
374 register word current
;
377 # ifdef ALL_INTERIOR_POINTERS
379 register word orig
= current
;
381 current
= (word
)HBLKPTR(current
) + HDR_BYTES
;
383 current
= current
- HBLKSIZE
*(word
)hhdr
;
385 } while(IS_FORWARDING_ADDR_OR_NIL(hhdr
));
386 /* current points to the start of the large object */
387 if (hhdr
-> hb_flags
& IGNORE_OFF_PAGE
) return(0);
388 if ((word
*)orig
- (word
*)current
389 >= (ptrdiff_t)(hhdr
->hb_sz
)) {
390 /* Pointer past the end of the block */
391 GC_ADD_TO_BLACK_LIST_NORMAL(orig
, source
);
396 GC_ADD_TO_BLACK_LIST_NORMAL(current
, source
);
400 GC_ADD_TO_BLACK_LIST_NORMAL(current
, source
);
406 void GC_invalidate_mark_state()
408 GC_mark_state
= MS_INVALID
;
409 GC_mark_stack_top
= GC_mark_stack
-1;
412 mse
* GC_signal_mark_stack_overflow(msp
)
415 GC_mark_state
= MS_INVALID
;
416 GC_mark_stack_too_small
= TRUE
;
418 GC_printf1("Mark stack overflow; current size = %lu entries\n",
421 return(msp
-INITIAL_MARK_STACK_SIZE
/8);
426 * Mark objects pointed to by the regions described by
427 * mark stack entries between GC_mark_stack and GC_mark_stack_top,
428 * inclusive. Assumes the upper limit of a mark stack entry
429 * is never 0. A mark stack entry never has size 0.
430 * We try to traverse on the order of a hblk of memory before we return.
431 * Caller is responsible for calling this until the mark stack is empty.
433 void GC_mark_from_mark_stack()
435 mse
* GC_mark_stack_reg
= GC_mark_stack
;
436 mse
* GC_mark_stack_top_reg
= GC_mark_stack_top
;
437 mse
* mark_stack_limit
= &(GC_mark_stack
[GC_mark_stack_size
]);
438 int credit
= HBLKSIZE
; /* Remaining credit for marking work */
439 register word
* current_p
; /* Pointer to current candidate ptr. */
440 register word current
; /* Candidate pointer. */
441 register word
* limit
; /* (Incl) limit of current candidate */
444 register ptr_t greatest_ha
= GC_greatest_plausible_heap_addr
;
445 register ptr_t least_ha
= GC_least_plausible_heap_addr
;
446 # define SPLIT_RANGE_WORDS 128 /* Must be power of 2. */
448 GC_objects_are_marked
= TRUE
;
449 # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
450 while (GC_mark_stack_top_reg
>= GC_mark_stack_reg
&& credit
>= 0) {
452 while ((((ptr_t
)GC_mark_stack_top_reg
- (ptr_t
)GC_mark_stack_reg
) | credit
)
455 current_p
= GC_mark_stack_top_reg
-> mse_start
;
457 descr
= GC_mark_stack_top_reg
-> mse_descr
;
458 if (descr
& ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS
) - 1)) | DS_TAGS
)) {
459 word tag
= descr
& DS_TAGS
;
464 /* Process part of the range to avoid pushing too much on the */
466 GC_mark_stack_top_reg
-> mse_start
=
467 limit
= current_p
+ SPLIT_RANGE_WORDS
-1;
468 GC_mark_stack_top_reg
-> mse_descr
-=
469 WORDS_TO_BYTES(SPLIT_RANGE_WORDS
-1);
470 /* Make sure that pointers overlapping the two ranges are */
472 limit
= (word
*)((char *)limit
+ sizeof(word
) - ALIGNMENT
);
475 GC_mark_stack_top_reg
--;
477 credit
-= WORDS_TO_BYTES(WORDSZ
/2); /* guess */
479 if ((signed_word
)descr
< 0) {
480 current
= *current_p
;
481 if ((ptr_t
)current
>= least_ha
&& (ptr_t
)current
< greatest_ha
) {
482 PUSH_CONTENTS(current
, GC_mark_stack_top_reg
, mark_stack_limit
,
491 GC_mark_stack_top_reg
--;
492 credit
-= PROC_BYTES
;
494 current_p
= GC_debug_object_start(current_p
);
496 GC_mark_stack_top_reg
=
498 (current_p
, GC_mark_stack_top_reg
,
499 mark_stack_limit
, ENV(descr
));
502 GC_mark_stack_top_reg
-> mse_descr
=
503 *(word
*)((ptr_t
)current_p
+ descr
- tag
);
507 GC_mark_stack_top_reg
--;
508 limit
= (word
*)(((ptr_t
)current_p
) + (word
)descr
);
510 /* The simple case in which we're scanning a range. */
511 credit
-= (ptr_t
)limit
- (ptr_t
)current_p
;
513 while (current_p
<= limit
) {
514 current
= *current_p
;
515 if ((ptr_t
)current
>= least_ha
&& (ptr_t
)current
< greatest_ha
) {
516 PUSH_CONTENTS(current
, GC_mark_stack_top_reg
,
517 mark_stack_limit
, current_p
, exit2
);
519 current_p
= (word
*)((char *)current_p
+ ALIGNMENT
);
522 GC_mark_stack_top
= GC_mark_stack_top_reg
;
525 /* Allocate or reallocate space for mark stack of size s words */
526 /* May silently fail. */
527 static void alloc_mark_stack(n
)
530 mse
* new_stack
= (mse
*)GC_scratch_alloc(n
* sizeof(struct ms_entry
));
532 GC_mark_stack_too_small
= FALSE
;
533 if (GC_mark_stack_size
!= 0) {
534 if (new_stack
!= 0) {
535 word displ
= (word
)GC_mark_stack
& (GC_page_size
- 1);
536 signed_word size
= GC_mark_stack_size
* sizeof(struct ms_entry
);
538 /* Recycle old space */
539 if (0 != displ
) displ
= GC_page_size
- displ
;
540 size
= (size
- displ
) & ~(GC_page_size
- 1);
542 GC_add_to_heap((struct hblk
*)
543 ((word
)GC_mark_stack
+ displ
), (word
)size
);
545 GC_mark_stack
= new_stack
;
546 GC_mark_stack_size
= n
;
548 GC_printf1("Grew mark stack to %lu frames\n",
549 (unsigned long) GC_mark_stack_size
);
553 GC_printf1("Failed to grow mark stack to %lu frames\n",
558 if (new_stack
== 0) {
559 GC_err_printf0("No space for mark stack\n");
562 GC_mark_stack
= new_stack
;
563 GC_mark_stack_size
= n
;
565 GC_mark_stack_top
= GC_mark_stack
-1;
570 alloc_mark_stack(INITIAL_MARK_STACK_SIZE
);
574 * Push all locations between b and t onto the mark stack.
575 * b is the first location to be checked. t is one past the last
576 * location to be checked.
577 * Should only be used if there is no possibility of mark stack
580 void GC_push_all(bottom
, top
)
584 register word length
;
586 bottom
= (ptr_t
)(((word
) bottom
+ ALIGNMENT
-1) & ~(ALIGNMENT
-1));
587 top
= (ptr_t
)(((word
) top
) & ~(ALIGNMENT
-1));
588 if (top
== 0 || bottom
== top
) return;
590 if (GC_mark_stack_top
>= GC_mark_stack
+ GC_mark_stack_size
) {
591 ABORT("unexpected mark stack overflow");
593 length
= top
- bottom
;
594 # if DS_TAGS > ALIGNMENT - 1
598 GC_mark_stack_top
-> mse_start
= (word
*)bottom
;
599 GC_mark_stack_top
-> mse_descr
= length
;
603 * Analogous to the above, but push only those pages that may have been
604 * dirtied. A block h is assumed dirty if dirty_fn(h) != 0.
605 * We use push_fn to actually push the block.
606 * Will not overflow mark stack if push_fn pushes a small fixed number
607 * of entries. (This is invoked only if push_fn pushes a single entry,
608 * or if it marks each object before pushing it, thus ensuring progress
609 * in the event of a stack overflow.)
611 void GC_push_dirty(bottom
, top
, dirty_fn
, push_fn
)
614 int (*dirty_fn
)(/* struct hblk * h */);
615 void (*push_fn
)(/* ptr_t bottom, ptr_t top */);
617 register struct hblk
* h
;
619 bottom
= (ptr_t
)(((long) bottom
+ ALIGNMENT
-1) & ~(ALIGNMENT
-1));
620 top
= (ptr_t
)(((long) top
) & ~(ALIGNMENT
-1));
622 if (top
== 0 || bottom
== top
) return;
623 h
= HBLKPTR(bottom
+ HBLKSIZE
);
624 if (top
<= (ptr_t
) h
) {
625 if ((*dirty_fn
)(h
-1)) {
626 (*push_fn
)(bottom
, top
);
630 if ((*dirty_fn
)(h
-1)) {
631 (*push_fn
)(bottom
, (ptr_t
)h
);
633 while ((ptr_t
)(h
+1) <= top
) {
634 if ((*dirty_fn
)(h
)) {
635 if ((word
)(GC_mark_stack_top
- GC_mark_stack
)
636 > 3 * GC_mark_stack_size
/ 4) {
637 /* Danger of mark stack overflow */
638 (*push_fn
)((ptr_t
)h
, top
);
641 (*push_fn
)((ptr_t
)h
, (ptr_t
)(h
+1));
646 if ((ptr_t
)h
!= top
) {
647 if ((*dirty_fn
)(h
)) {
648 (*push_fn
)((ptr_t
)h
, top
);
651 if (GC_mark_stack_top
>= GC_mark_stack
+ GC_mark_stack_size
) {
652 ABORT("unexpected mark stack overflow");
656 # ifndef SMALL_CONFIG
657 void GC_push_conditional(bottom
, top
, all
)
663 if (GC_dirty_maintained
) {
665 /* Pages that were never dirtied cannot contain pointers */
666 GC_push_dirty(bottom
, top
, GC_page_was_ever_dirty
, GC_push_all
);
668 GC_push_all(bottom
, top
);
671 GC_push_all(bottom
, top
);
674 GC_push_dirty(bottom
, top
, GC_page_was_dirty
, GC_push_all
);
680 void __cdecl
GC_push_one(p
)
687 if (0 != GC_push_proc
) {
692 GC_PUSH_ONE_STACK(p
, 0);
696 # define BASE(p) (word)GC_base((void *)(p))
698 # define BASE(p) (word)GC_base((char *)(p))
701 /* As above, but argument passed preliminary test. */
702 # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
703 void GC_push_one_checked(p
, interior_ptrs
, source
)
706 void GC_push_one_checked(p
, interior_ptrs
)
710 register GC_bool interior_ptrs
;
717 if (IS_FORWARDING_ADDR_OR_NIL(hhdr
)) {
718 if (hhdr
!= 0 && interior_ptrs
) {
721 displ
= BYTES_TO_WORDS(HBLKDISPL(r
));
726 register map_entry_type map_entry
;
728 displ
= HBLKDISPL(p
);
729 map_entry
= MAP_ENTRY((hhdr
-> hb_map
), displ
);
730 if (map_entry
== OBJ_INVALID
) {
731 # ifndef ALL_INTERIOR_POINTERS
734 displ
= BYTES_TO_WORDS(HBLKDISPL(r
));
735 if (r
== 0) hhdr
= 0;
740 /* map already reflects interior pointers */
744 displ
= BYTES_TO_WORDS(displ
);
746 r
= (word
)((word
*)(HBLKPTR(p
)) + displ
);
749 /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
750 /* displ is the word index within the block. */
753 # ifdef PRINT_BLACK_LIST
754 GC_add_to_black_list_stack(p
, source
);
756 GC_add_to_black_list_stack(p
);
759 GC_ADD_TO_BLACK_LIST_NORMAL(p
, source
);
760 # undef source /* In case we had to define it. */
763 if (!mark_bit_from_hdr(hhdr
, displ
)) {
764 set_mark_bit_from_hdr(hhdr
, displ
);
765 GC_STORE_BACK_PTR(source
, (ptr_t
)r
);
766 PUSH_OBJ((word
*)r
, hhdr
, GC_mark_stack_top
,
767 &(GC_mark_stack
[GC_mark_stack_size
]));
774 # define TRACE_ENTRIES 1000
782 } GC_trace_buf
[TRACE_ENTRIES
];
784 int GC_trace_buf_ptr
= 0;
786 void GC_add_trace_entry(char *kind
, word arg1
, word arg2
)
788 GC_trace_buf
[GC_trace_buf_ptr
].kind
= kind
;
789 GC_trace_buf
[GC_trace_buf_ptr
].gc_no
= GC_gc_no
;
790 GC_trace_buf
[GC_trace_buf_ptr
].words_allocd
= GC_words_allocd
;
791 GC_trace_buf
[GC_trace_buf_ptr
].arg1
= arg1
^ 0x80000000;
792 GC_trace_buf
[GC_trace_buf_ptr
].arg2
= arg2
^ 0x80000000;
794 if (GC_trace_buf_ptr
>= TRACE_ENTRIES
) GC_trace_buf_ptr
= 0;
797 void GC_print_trace(word gc_no
, GC_bool lock
)
800 struct trace_entry
*p
;
803 for (i
= GC_trace_buf_ptr
-1; i
!= GC_trace_buf_ptr
; i
--) {
804 if (i
< 0) i
= TRACE_ENTRIES
-1;
805 p
= GC_trace_buf
+ i
;
806 if (p
-> gc_no
< gc_no
|| p
-> kind
== 0) return;
807 printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
808 p
-> kind
, p
-> gc_no
, p
-> words_allocd
,
809 (p
-> arg1
) ^ 0x80000000, (p
-> arg2
) ^ 0x80000000);
811 printf("Trace incomplete\n");
815 # endif /* TRACE_BUF */
818 * A version of GC_push_all that treats all interior pointers as valid
819 * and scans the entire region immediately, in case the contents
822 void GC_push_all_eager(bottom
, top
)
826 word
* b
= (word
*)(((long) bottom
+ ALIGNMENT
-1) & ~(ALIGNMENT
-1));
827 word
* t
= (word
*)(((long) top
) & ~(ALIGNMENT
-1));
831 register ptr_t greatest_ha
= GC_greatest_plausible_heap_addr
;
832 register ptr_t least_ha
= GC_least_plausible_heap_addr
;
833 # define GC_greatest_plausible_heap_addr greatest_ha
834 # define GC_least_plausible_heap_addr least_ha
836 if (top
== 0) return;
837 /* check all pointers in range and put in push if they appear */
839 lim
= t
- 1 /* longword */;
840 for (p
= b
; p
<= lim
; p
= (word
*)(((char *)p
) + ALIGNMENT
)) {
842 GC_PUSH_ONE_STACK(q
, p
);
844 # undef GC_greatest_plausible_heap_addr
845 # undef GC_least_plausible_heap_addr
850 * A version of GC_push_all that treats all interior pointers as valid
851 * and scans part of the area immediately, to make sure that saved
852 * register values are not lost.
853 * Cold_gc_frame delimits the stack section that must be scanned
854 * eagerly. A zero value indicates that no eager scanning is needed.
856 void GC_push_all_stack_partially_eager(bottom
, top
, cold_gc_frame
)
861 # ifdef ALL_INTERIOR_POINTERS
862 # define EAGER_BYTES 1024
863 /* Push the hot end of the stack eagerly, so that register values */
864 /* saved inside GC frames are marked before they disappear. */
865 /* The rest of the marking can be deferred until later. */
866 if (0 == cold_gc_frame
) {
867 GC_push_all_stack(bottom
, top
);
870 # ifdef STACK_GROWS_DOWN
871 GC_push_all_eager(bottom
, cold_gc_frame
);
872 GC_push_all(cold_gc_frame
- sizeof(ptr_t
), top
);
873 # else /* STACK_GROWS_UP */
874 GC_push_all_eager(cold_gc_frame
, top
);
875 GC_push_all(bottom
, cold_gc_frame
+ sizeof(ptr_t
));
876 # endif /* STACK_GROWS_UP */
878 GC_push_all_eager(bottom
, top
);
881 GC_add_trace_entry("GC_push_all_stack", bottom
, top
);
884 #endif /* !THREADS */
886 void GC_push_all_stack(bottom
, top
)
890 # ifdef ALL_INTERIOR_POINTERS
891 GC_push_all(bottom
, top
);
893 GC_push_all_eager(bottom
, top
);
898 /* Push all objects reachable from marked objects in the given block */
899 /* of size 1 objects. */
900 void GC_push_marked1(h
, hhdr
)
904 word
* mark_word_addr
= &(hhdr
->hb_marks
[divWORDSZ(HDR_WORDS
)]);
909 register word mark_word
;
910 register ptr_t greatest_ha
= GC_greatest_plausible_heap_addr
;
911 register ptr_t least_ha
= GC_least_plausible_heap_addr
;
912 # define GC_greatest_plausible_heap_addr greatest_ha
913 # define GC_least_plausible_heap_addr least_ha
915 p
= (word
*)(h
->hb_body
);
916 plim
= (word
*)(((word
)h
) + HBLKSIZE
);
918 /* go through all words in block */
920 mark_word
= *mark_word_addr
++;
922 while(mark_word
!= 0) {
925 GC_PUSH_ONE_HEAP(q
, p
+ i
);
932 # undef GC_greatest_plausible_heap_addr
933 # undef GC_least_plausible_heap_addr
939 /* Push all objects reachable from marked objects in the given block */
940 /* of size 2 objects. */
941 void GC_push_marked2(h
, hhdr
)
945 word
* mark_word_addr
= &(hhdr
->hb_marks
[divWORDSZ(HDR_WORDS
)]);
950 register word mark_word
;
951 register ptr_t greatest_ha
= GC_greatest_plausible_heap_addr
;
952 register ptr_t least_ha
= GC_least_plausible_heap_addr
;
953 # define GC_greatest_plausible_heap_addr greatest_ha
954 # define GC_least_plausible_heap_addr least_ha
956 p
= (word
*)(h
->hb_body
);
957 plim
= (word
*)(((word
)h
) + HBLKSIZE
);
959 /* go through all words in block */
961 mark_word
= *mark_word_addr
++;
963 while(mark_word
!= 0) {
966 GC_PUSH_ONE_HEAP(q
, p
+ i
);
968 GC_PUSH_ONE_HEAP(q
, p
+ i
);
975 # undef GC_greatest_plausible_heap_addr
976 # undef GC_least_plausible_heap_addr
979 /* Push all objects reachable from marked objects in the given block */
980 /* of size 4 objects. */
981 /* There is a risk of mark stack overflow here. But we handle that. */
982 /* And only unmarked objects get pushed, so it's not very likely. */
983 void GC_push_marked4(h
, hhdr
)
987 word
* mark_word_addr
= &(hhdr
->hb_marks
[divWORDSZ(HDR_WORDS
)]);
992 register word mark_word
;
993 register ptr_t greatest_ha
= GC_greatest_plausible_heap_addr
;
994 register ptr_t least_ha
= GC_least_plausible_heap_addr
;
995 # define GC_greatest_plausible_heap_addr greatest_ha
996 # define GC_least_plausible_heap_addr least_ha
998 p
= (word
*)(h
->hb_body
);
999 plim
= (word
*)(((word
)h
) + HBLKSIZE
);
1001 /* go through all words in block */
1003 mark_word
= *mark_word_addr
++;
1005 while(mark_word
!= 0) {
1006 if (mark_word
& 1) {
1008 GC_PUSH_ONE_HEAP(q
, p
+ i
);
1010 GC_PUSH_ONE_HEAP(q
, p
+ i
+ 1);
1012 GC_PUSH_ONE_HEAP(q
, p
+ i
+ 2);
1014 GC_PUSH_ONE_HEAP(q
, p
+ i
+ 3);
1021 # undef GC_greatest_plausible_heap_addr
1022 # undef GC_least_plausible_heap_addr
1025 #endif /* UNALIGNED */
1027 #endif /* SMALL_CONFIG */
1029 /* Push all objects reachable from marked objects in the given block */
1030 void GC_push_marked(h
, hhdr
)
1032 register hdr
* hhdr
;
1034 register int sz
= hhdr
-> hb_sz
;
1036 register int word_no
;
1037 register word
* lim
;
1038 register mse
* GC_mark_stack_top_reg
;
1039 register mse
* mark_stack_limit
= &(GC_mark_stack
[GC_mark_stack_size
]);
1041 /* Some quick shortcuts: */
1043 struct obj_kind
*ok
= &(GC_obj_kinds
[hhdr
-> hb_obj_kind
]);
1044 if ((0 | DS_LENGTH
) == ok
-> ok_descriptor
1045 && FALSE
== ok
-> ok_relocate_descr
)
1048 if (GC_block_empty(hhdr
)/* nothing marked */) return;
1050 GC_n_rescuing_pages
++;
1052 GC_objects_are_marked
= TRUE
;
1053 if (sz
> MAXOBJSZ
) {
1054 lim
= (word
*)(h
+ 1);
1056 lim
= (word
*)(h
+ 1) - sz
;
1060 # if !defined(SMALL_CONFIG)
1062 GC_push_marked1(h
, hhdr
);
1065 # if !defined(SMALL_CONFIG) && !defined(UNALIGNED)
1067 GC_push_marked2(h
, hhdr
);
1070 GC_push_marked4(h
, hhdr
);
1074 GC_mark_stack_top_reg
= GC_mark_stack_top
;
1075 for (p
= (word
*)h
+ HDR_WORDS
, word_no
= HDR_WORDS
; p
<= lim
;
1076 p
+= sz
, word_no
+= sz
) {
1077 /* This ignores user specified mark procs. This currently */
1078 /* doesn't matter, since marking from the whole object */
1079 /* is always sufficient, and we will eventually use the user */
1080 /* mark proc to avoid any bogus pointers. */
1081 if (mark_bit_from_hdr(hhdr
, word_no
)) {
1082 /* Mark from fields inside the object */
1083 PUSH_OBJ((word
*)p
, hhdr
, GC_mark_stack_top_reg
, mark_stack_limit
);
1085 /* Subtract this object from total, since it was */
1086 /* added in twice. */
1087 GC_composite_in_use
-= sz
;
1091 GC_mark_stack_top
= GC_mark_stack_top_reg
;
1095 #ifndef SMALL_CONFIG
1096 /* Test whether any page in the given block is dirty */
1097 GC_bool
GC_block_was_dirty(h
, hhdr
)
1099 register hdr
* hhdr
;
1101 register int sz
= hhdr
-> hb_sz
;
1103 if (sz
< MAXOBJSZ
) {
1104 return(GC_page_was_dirty(h
));
1106 register ptr_t p
= (ptr_t
)h
;
1108 sz
= WORDS_TO_BYTES(sz
);
1109 while (p
< (ptr_t
)h
+ sz
) {
1110 if (GC_page_was_dirty((struct hblk
*)p
)) return(TRUE
);
1116 #endif /* SMALL_CONFIG */
1118 /* Similar to GC_push_next_marked, but return address of next block */
1119 struct hblk
* GC_push_next_marked(h
)
1122 register hdr
* hhdr
;
1124 h
= GC_next_used_block(h
);
1125 if (h
== 0) return(0);
1127 GC_push_marked(h
, hhdr
);
1128 return(h
+ OBJ_SZ_TO_BLOCKS(hhdr
-> hb_sz
));
1131 #ifndef SMALL_CONFIG
1132 /* Identical to above, but mark only from dirty pages */
1133 struct hblk
* GC_push_next_marked_dirty(h
)
1136 register hdr
* hhdr
;
1138 if (!GC_dirty_maintained
) { ABORT("dirty bits not set up"); }
1140 h
= GC_next_used_block(h
);
1141 if (h
== 0) return(0);
1143 # ifdef STUBBORN_ALLOC
1144 if (hhdr
-> hb_obj_kind
== STUBBORN
) {
1145 if (GC_page_was_changed(h
) && GC_block_was_dirty(h
, hhdr
)) {
1149 if (GC_block_was_dirty(h
, hhdr
)) break;
1152 if (GC_block_was_dirty(h
, hhdr
)) break;
1154 h
+= OBJ_SZ_TO_BLOCKS(hhdr
-> hb_sz
);
1156 GC_push_marked(h
, hhdr
);
1157 return(h
+ OBJ_SZ_TO_BLOCKS(hhdr
-> hb_sz
));
1161 /* Similar to above, but for uncollectable pages. Needed since we */
1162 /* do not clear marks for such pages, even for full collections. */
1163 struct hblk
* GC_push_next_marked_uncollectable(h
)
1166 register hdr
* hhdr
= HDR(h
);
1169 h
= GC_next_used_block(h
);
1170 if (h
== 0) return(0);
1172 if (hhdr
-> hb_obj_kind
== UNCOLLECTABLE
) break;
1173 h
+= OBJ_SZ_TO_BLOCKS(hhdr
-> hb_sz
);
1175 GC_push_marked(h
, hhdr
);
1176 return(h
+ OBJ_SZ_TO_BLOCKS(hhdr
-> hb_sz
));