3 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
4 * Copyright (c) 1991-1995 by Xerox Corporation. All rights reserved.
5 * Copyright (c) 2000 by Hewlett-Packard Company. All rights reserved.
7 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
8 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
10 * Permission is hereby granted to use or copy this program
11 * for any purpose, provided the above notices are retained on all copies.
12 * Permission to modify the code and to distribute modified code is granted,
13 * provided the above notices are retained, and a notice that the code was
14 * modified is included with the above copyright notice.
20 # include "private/gc_pmark.h"
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
= GC_RESERVED_MARK_PROCS
;
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 | GC_DS_LENGTH
, FALSE
, FALSE
},
50 /* NORMAL */ { &GC_objfreelist
[0], 0,
51 0 | GC_DS_LENGTH
, /* Adjusted in GC_init_inner for EXTRA_BYTES */
52 TRUE
/* add length to descr */, TRUE
},
54 { &GC_uobjfreelist
[0], 0,
55 0 | GC_DS_LENGTH
, TRUE
/* add length to descr */, TRUE
},
56 # ifdef ATOMIC_UNCOLLECTABLE
58 { &GC_auobjfreelist
[0], 0,
59 0 | GC_DS_LENGTH
, FALSE
/* add length to descr */, FALSE
},
61 # ifdef STUBBORN_ALLOC
62 /*STUBBORN*/ { &GC_sobjfreelist
[0], 0,
63 0 | GC_DS_LENGTH
, TRUE
/* add length to descr */, TRUE
},
67 # ifdef ATOMIC_UNCOLLECTABLE
68 # ifdef STUBBORN_ALLOC
74 # ifdef STUBBORN_ALLOC
82 # ifndef INITIAL_MARK_STACK_SIZE
83 # define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
84 /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a */
85 /* multiple of HBLKSIZE. */
86 /* The incremental collector actually likes a larger */
87 /* size, since it want to push all marked dirty objs */
88 /* before marking anything new. Currently we let it */
89 /* grow dynamically. */
93 * Limits of stack for GC_mark routine.
94 * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
95 * need to be marked from.
98 word GC_n_rescuing_pages
; /* Number of dirty pages we marked from */
99 /* excludes ptrfree pages, etc. */
103 mse
* GC_mark_stack_limit
;
105 word GC_mark_stack_size
= 0;
108 mse
* VOLATILE GC_mark_stack_top
;
110 mse
* GC_mark_stack_top
;
113 static struct hblk
* scan_ptr
;
115 mark_state_t GC_mark_state
= MS_NONE
;
117 GC_bool GC_mark_stack_too_small
= FALSE
;
119 GC_bool GC_objects_are_marked
= FALSE
; /* Are there collectable marked */
120 /* objects in the heap? */
122 /* Is a collection in progress? Note that this can return true in the */
123 /* nonincremental case, if a collection has been abandoned and the */
124 /* mark state is now MS_INVALID. */
125 GC_bool
GC_collection_in_progress()
127 return(GC_mark_state
!= MS_NONE
);
130 /* clear all mark bits in the header */
131 void GC_clear_hdr_marks(hhdr
)
134 # ifdef USE_MARK_BYTES
135 BZERO(hhdr
-> hb_marks
, MARK_BITS_SZ
);
137 BZERO(hhdr
-> hb_marks
, MARK_BITS_SZ
*sizeof(word
));
141 /* Set all mark bits in the header. Used for uncollectable blocks. */
142 void GC_set_hdr_marks(hhdr
)
147 for (i
= 0; i
< MARK_BITS_SZ
; ++i
) {
148 # ifdef USE_MARK_BYTES
149 hhdr
-> hb_marks
[i
] = 1;
151 hhdr
-> hb_marks
[i
] = ONES
;
157 * Clear all mark bits associated with block h.
160 # if defined(__STDC__) || defined(__cplusplus)
161 static void clear_marks_for_block(struct hblk
*h
, word dummy
)
163 static void clear_marks_for_block(h
, dummy
)
168 register hdr
* hhdr
= HDR(h
);
170 if (IS_UNCOLLECTABLE(hhdr
-> hb_obj_kind
)) return;
171 /* Mark bit for these is cleared only once the object is */
172 /* explicitly deallocated. This either frees the block, or */
173 /* the bit is cleared once the object is on the free list. */
174 GC_clear_hdr_marks(hhdr
);
177 /* Slow but general routines for setting/clearing/asking about mark bits */
178 void GC_set_mark_bit(p
)
181 register struct hblk
*h
= HBLKPTR(p
);
182 register hdr
* hhdr
= HDR(h
);
183 register int word_no
= (word
*)p
- (word
*)h
;
185 set_mark_bit_from_hdr(hhdr
, word_no
);
188 void GC_clear_mark_bit(p
)
191 register struct hblk
*h
= HBLKPTR(p
);
192 register hdr
* hhdr
= HDR(h
);
193 register int word_no
= (word
*)p
- (word
*)h
;
195 clear_mark_bit_from_hdr(hhdr
, word_no
);
198 GC_bool
GC_is_marked(p
)
201 register struct hblk
*h
= HBLKPTR(p
);
202 register hdr
* hhdr
= HDR(h
);
203 register int word_no
= (word
*)p
- (word
*)h
;
205 return(mark_bit_from_hdr(hhdr
, word_no
));
210 * Clear mark bits in all allocated heap blocks. This invalidates
211 * the marker invariant, and sets GC_mark_state to reflect this.
212 * (This implicitly starts marking to reestablish the invariant.)
214 void GC_clear_marks()
216 GC_apply_to_all_blocks(clear_marks_for_block
, (word
)0);
217 GC_objects_are_marked
= FALSE
;
218 GC_mark_state
= MS_INVALID
;
221 /* Counters reflect currently marked objects: reset here */
222 GC_composite_in_use
= 0;
223 GC_atomic_in_use
= 0;
228 /* Initiate a garbage collection. Initiates a full collection if the */
229 /* mark state is invalid. */
231 void GC_initiate_gc()
233 if (GC_dirty_maintained
) GC_read_dirty();
234 # ifdef STUBBORN_ALLOC
239 extern void GC_check_dirty();
241 if (GC_dirty_maintained
) GC_check_dirty();
244 GC_n_rescuing_pages
= 0;
245 if (GC_mark_state
== MS_NONE
) {
246 GC_mark_state
= MS_PUSH_RESCUERS
;
247 } else if (GC_mark_state
!= MS_INVALID
) {
248 ABORT("unexpected state");
249 } /* else this is really a full collection, and mark */
250 /* bits are invalid. */
255 static void alloc_mark_stack();
257 /* Perform a small amount of marking. */
258 /* We try to touch roughly a page of memory. */
259 /* Return TRUE if we just finished a mark phase. */
260 /* Cold_gc_frame is an address inside a GC frame that */
261 /* remains valid until all marking is complete. */
262 /* A zero value indicates that it's OK to miss some */
263 /* register values. */
264 GC_bool
GC_mark_some(cold_gc_frame
)
267 #if defined(MSWIN32) && !defined(__GNUC__)
268 /* Windows 98 appears to asynchronously create and remove writable */
269 /* memory mappings, for reasons we haven't yet understood. Since */
270 /* we look for writable regions to determine the root set, we may */
271 /* try to mark from an address range that disappeared since we */
272 /* started the collection. Thus we have to recover from faults here. */
273 /* This code does not appear to be necessary for Windows 95/NT/2000. */
274 /* Note that this code should never generate an incremental GC write */
277 #endif /* defined(MSWIN32) && !defined(__GNUC__) */
278 switch(GC_mark_state
) {
282 case MS_PUSH_RESCUERS
:
283 if (GC_mark_stack_top
284 >= GC_mark_stack_limit
- INITIAL_MARK_STACK_SIZE
/2) {
285 /* Go ahead and mark, even though that might cause us to */
286 /* see more marked dirty objects later on. Avoid this */
288 GC_mark_stack_too_small
= TRUE
;
289 MARK_FROM_MARK_STACK();
292 scan_ptr
= GC_push_next_marked_dirty(scan_ptr
);
295 if (GC_print_stats
) {
296 GC_printf1("Marked from %lu dirty pages\n",
297 (unsigned long)GC_n_rescuing_pages
);
300 GC_push_roots(FALSE
, cold_gc_frame
);
301 GC_objects_are_marked
= TRUE
;
302 if (GC_mark_state
!= MS_INVALID
) {
303 GC_mark_state
= MS_ROOTS_PUSHED
;
309 case MS_PUSH_UNCOLLECTABLE
:
310 if (GC_mark_stack_top
311 >= GC_mark_stack
+ GC_mark_stack_size
/4) {
312 # ifdef PARALLEL_MARK
313 /* Avoid this, since we don't parallelize the marker */
315 if (GC_parallel
) GC_mark_stack_too_small
= TRUE
;
317 MARK_FROM_MARK_STACK();
320 scan_ptr
= GC_push_next_marked_uncollectable(scan_ptr
);
322 GC_push_roots(TRUE
, cold_gc_frame
);
323 GC_objects_are_marked
= TRUE
;
324 if (GC_mark_state
!= MS_INVALID
) {
325 GC_mark_state
= MS_ROOTS_PUSHED
;
331 case MS_ROOTS_PUSHED
:
332 # ifdef PARALLEL_MARK
333 /* In the incremental GC case, this currently doesn't */
334 /* quite do the right thing, since it runs to */
335 /* completion. On the other hand, starting a */
336 /* parallel marker is expensive, so perhaps it is */
337 /* the right thing? */
338 /* Eventually, incremental marking should run */
339 /* asynchronously in multiple threads, without grabbing */
340 /* the allocation lock. */
342 GC_do_parallel_mark();
343 GC_ASSERT(GC_mark_stack_top
< GC_first_nonempty
);
344 GC_mark_stack_top
= GC_mark_stack
- 1;
345 if (GC_mark_stack_too_small
) {
346 alloc_mark_stack(2*GC_mark_stack_size
);
348 if (GC_mark_state
== MS_ROOTS_PUSHED
) {
349 GC_mark_state
= MS_NONE
;
356 if (GC_mark_stack_top
>= GC_mark_stack
) {
357 MARK_FROM_MARK_STACK();
360 GC_mark_state
= MS_NONE
;
361 if (GC_mark_stack_too_small
) {
362 alloc_mark_stack(2*GC_mark_stack_size
);
368 case MS_PARTIALLY_INVALID
:
369 if (!GC_objects_are_marked
) {
370 GC_mark_state
= MS_PUSH_UNCOLLECTABLE
;
373 if (GC_mark_stack_top
>= GC_mark_stack
) {
374 MARK_FROM_MARK_STACK();
377 if (scan_ptr
== 0 && GC_mark_state
== MS_INVALID
) {
378 /* About to start a heap scan for marked objects. */
379 /* Mark stack is empty. OK to reallocate. */
380 if (GC_mark_stack_too_small
) {
381 alloc_mark_stack(2*GC_mark_stack_size
);
383 GC_mark_state
= MS_PARTIALLY_INVALID
;
385 scan_ptr
= GC_push_next_marked(scan_ptr
);
386 if (scan_ptr
== 0 && GC_mark_state
== MS_PARTIALLY_INVALID
) {
387 GC_push_roots(TRUE
, cold_gc_frame
);
388 GC_objects_are_marked
= TRUE
;
389 if (GC_mark_state
!= MS_INVALID
) {
390 GC_mark_state
= MS_ROOTS_PUSHED
;
395 ABORT("GC_mark_some: bad state");
398 #if defined(MSWIN32) && !defined(__GNUC__)
399 } __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION
?
400 EXCEPTION_EXECUTE_HANDLER
: EXCEPTION_CONTINUE_SEARCH
) {
402 if (GC_print_stats
) {
403 GC_printf0("Caught ACCESS_VIOLATION in marker. "
404 "Memory mapping disappeared.\n");
406 # endif /* CONDPRINT */
407 /* We have bad roots on the stack. Discard mark stack. */
408 /* Rescan from marked objects. Redetermine roots. */
409 GC_invalidate_mark_state();
413 #endif /* defined(MSWIN32) && !defined(__GNUC__) */
417 GC_bool
GC_mark_stack_empty()
419 return(GC_mark_stack_top
< GC_mark_stack
);
423 word GC_prof_array
[10];
424 # define PROF(n) GC_prof_array[n]++
429 /* Given a pointer to someplace other than a small object page or the */
430 /* first page of a large object, either: */
431 /* - return a pointer to somewhere in the first page of the large */
432 /* object, if current points to a large object. */
433 /* In this case *hhdr is replaced with a pointer to the header */
434 /* for the large object. */
435 /* - just return current if it does not point to a large object. */
437 ptr_t
GC_find_start(current
, hhdr
, new_hdr_p
)
438 register ptr_t current
;
439 register hdr
*hhdr
, **new_hdr_p
;
441 if (GC_all_interior_pointers
) {
443 register ptr_t orig
= current
;
445 current
= (ptr_t
)HBLKPTR(current
);
447 current
= current
- HBLKSIZE
*(word
)hhdr
;
449 } while(IS_FORWARDING_ADDR_OR_NIL(hhdr
));
450 /* current points to the start of the large object */
451 if (hhdr
-> hb_flags
& IGNORE_OFF_PAGE
) return(0);
452 if ((word
*)orig
- (word
*)current
453 >= (ptrdiff_t)(hhdr
->hb_sz
)) {
454 /* Pointer past the end of the block */
467 void GC_invalidate_mark_state()
469 GC_mark_state
= MS_INVALID
;
470 GC_mark_stack_top
= GC_mark_stack
-1;
473 mse
* GC_signal_mark_stack_overflow(msp
)
476 GC_mark_state
= MS_INVALID
;
477 GC_mark_stack_too_small
= TRUE
;
479 if (GC_print_stats
) {
480 GC_printf1("Mark stack overflow; current size = %lu entries\n",
484 return(msp
- GC_MARK_STACK_DISCARDS
);
488 * Mark objects pointed to by the regions described by
489 * mark stack entries between GC_mark_stack and GC_mark_stack_top,
490 * inclusive. Assumes the upper limit of a mark stack entry
491 * is never 0. A mark stack entry never has size 0.
492 * We try to traverse on the order of a hblk of memory before we return.
493 * Caller is responsible for calling this until the mark stack is empty.
494 * Note that this is the most performance critical routine in the
495 * collector. Hence it contains all sorts of ugly hacks to speed
496 * things up. In particular, we avoid procedure calls on the common
497 * path, we take advantage of peculiarities of the mark descriptor
498 * encoding, we optionally maintain a cache for the block address to
499 * header mapping, we prefetch when an object is "grayed", etc.
501 mse
* GC_mark_from(mark_stack_top
, mark_stack
, mark_stack_limit
)
502 mse
* mark_stack_top
;
504 mse
* mark_stack_limit
;
506 int credit
= HBLKSIZE
; /* Remaining credit for marking work */
507 register word
* current_p
; /* Pointer to current candidate ptr. */
508 register word current
; /* Candidate pointer. */
509 register word
* limit
; /* (Incl) limit of current candidate */
512 register ptr_t greatest_ha
= GC_greatest_plausible_heap_addr
;
513 register ptr_t least_ha
= GC_least_plausible_heap_addr
;
516 # define SPLIT_RANGE_WORDS 128 /* Must be power of 2. */
518 GC_objects_are_marked
= TRUE
;
520 # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
521 while (mark_stack_top
>= mark_stack
&& credit
>= 0) {
523 while ((((ptr_t
)mark_stack_top
- (ptr_t
)mark_stack
) | credit
)
526 current_p
= mark_stack_top
-> mse_start
;
527 descr
= mark_stack_top
-> mse_descr
;
529 /* current_p and descr describe the current object. */
530 /* *mark_stack_top is vacant. */
531 /* The following is 0 only for small objects described by a simple */
532 /* length descriptor. For many applications this is the common */
533 /* case, so we try to detect it quickly. */
534 if (descr
& ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS
) - 1)) | GC_DS_TAGS
)) {
535 word tag
= descr
& GC_DS_TAGS
;
540 /* Process part of the range to avoid pushing too much on the */
542 GC_ASSERT(descr
< (word
)GC_greatest_plausible_heap_addr
543 - (word
)GC_least_plausible_heap_addr
);
544 # ifdef PARALLEL_MARK
545 # define SHARE_BYTES 2048
546 if (descr
> SHARE_BYTES
&& GC_parallel
547 && mark_stack_top
< mark_stack_limit
- 1) {
548 int new_size
= (descr
/2) & ~(sizeof(word
)-1);
549 mark_stack_top
-> mse_start
= current_p
;
550 mark_stack_top
-> mse_descr
= new_size
+ sizeof(word
);
551 /* makes sure we handle */
552 /* misaligned pointers. */
554 current_p
= (word
*) ((char *)current_p
+ new_size
);
558 # endif /* PARALLEL_MARK */
559 mark_stack_top
-> mse_start
=
560 limit
= current_p
+ SPLIT_RANGE_WORDS
-1;
561 mark_stack_top
-> mse_descr
=
562 descr
- WORDS_TO_BYTES(SPLIT_RANGE_WORDS
-1);
563 /* Make sure that pointers overlapping the two ranges are */
565 limit
= (word
*)((char *)limit
+ sizeof(word
) - ALIGNMENT
);
569 descr
&= ~GC_DS_TAGS
;
570 credit
-= WORDS_TO_BYTES(WORDSZ
/2); /* guess */
572 if ((signed_word
)descr
< 0) {
573 current
= *current_p
;
574 FIXUP_POINTER(current
);
575 if ((ptr_t
)current
>= least_ha
&& (ptr_t
)current
< greatest_ha
) {
577 HC_PUSH_CONTENTS((ptr_t
)current
, mark_stack_top
,
578 mark_stack_limit
, current_p
, exit1
);
587 credit
-= GC_PROC_BYTES
;
590 (current_p
, mark_stack_top
,
591 mark_stack_limit
, ENV(descr
));
593 case GC_DS_PER_OBJECT
:
594 if ((signed_word
)descr
>= 0) {
595 /* Descriptor is in the object. */
596 descr
= *(word
*)((ptr_t
)current_p
+ descr
- GC_DS_PER_OBJECT
);
598 /* Descriptor is in type descriptor pointed to by first */
599 /* word in object. */
600 ptr_t type_descr
= *(ptr_t
*)current_p
;
601 /* type_descr is either a valid pointer to the descriptor */
602 /* structure, or this object was on a free list. If it */
603 /* it was anything but the last object on the free list, */
604 /* we will misinterpret the next object on the free list as */
605 /* the type descriptor, and get a 0 GC descriptor, which */
606 /* is ideal. Unfortunately, we need to check for the last */
607 /* object case explicitly. */
608 if (0 == type_descr
) {
609 /* Rarely executed. */
613 descr
= *(word
*)(type_descr
614 - (descr
- (GC_DS_PER_OBJECT
615 - GC_INDIR_PER_OBJ_BIAS
)));
618 /* Can happen either because we generated a 0 descriptor */
619 /* or we saw a pointer to a free object. */
625 } else /* Small object with length descriptor */ {
627 limit
= (word
*)(((ptr_t
)current_p
) + (word
)descr
);
629 /* The simple case in which we're scanning a range. */
630 GC_ASSERT(!((word
)current_p
& (ALIGNMENT
-1)));
631 credit
-= (ptr_t
)limit
- (ptr_t
)current_p
;
636 # ifndef SMALL_CONFIG
639 /* Try to prefetch the next pointer to be examined asap. */
640 /* Empirically, this also seems to help slightly without */
641 /* prefetches, at least on linux/X86. Presumably this loop */
642 /* ends up with less register pressure, and gcc thus ends up */
643 /* generating slightly better code. Overall gcc code quality */
644 /* for this loop is still not great. */
646 PREFETCH((ptr_t
)limit
- PREF_DIST
*CACHE_LINE_SIZE
);
647 GC_ASSERT(limit
>= current_p
);
649 FIXUP_POINTER(deferred
);
650 limit
= (word
*)((char *)limit
- ALIGNMENT
);
651 if ((ptr_t
)deferred
>= least_ha
&& (ptr_t
)deferred
< greatest_ha
) {
655 if (current_p
> limit
) goto next_object
;
656 /* Unroll once, so we don't do too many of the prefetches */
657 /* based on limit. */
659 FIXUP_POINTER(deferred
);
660 limit
= (word
*)((char *)limit
- ALIGNMENT
);
661 if ((ptr_t
)deferred
>= least_ha
&& (ptr_t
)deferred
< greatest_ha
) {
665 if (current_p
> limit
) goto next_object
;
669 while (current_p
<= limit
) {
670 /* Empirically, unrolling this loop doesn't help a lot. */
671 /* Since HC_PUSH_CONTENTS expands to a lot of code, */
673 current
= *current_p
;
674 FIXUP_POINTER(current
);
675 PREFETCH((ptr_t
)current_p
+ PREF_DIST
*CACHE_LINE_SIZE
);
676 if ((ptr_t
)current
>= least_ha
&& (ptr_t
)current
< greatest_ha
) {
677 /* Prefetch the contents of the object we just pushed. It's */
678 /* likely we will need them soon. */
680 HC_PUSH_CONTENTS((ptr_t
)current
, mark_stack_top
,
681 mark_stack_limit
, current_p
, exit2
);
683 current_p
= (word
*)((char *)current_p
+ ALIGNMENT
);
686 # ifndef SMALL_CONFIG
687 /* We still need to mark the entry we previously prefetched. */
688 /* We alrady know that it passes the preliminary pointer */
690 HC_PUSH_CONTENTS((ptr_t
)deferred
, mark_stack_top
,
691 mark_stack_limit
, current_p
, exit4
);
696 return mark_stack_top
;
701 /* We assume we have an ANSI C Compiler. */
702 GC_bool GC_help_wanted
= FALSE
;
703 unsigned GC_helper_count
= 0;
704 unsigned GC_active_count
= 0;
705 mse
* VOLATILE GC_first_nonempty
;
708 #define LOCAL_MARK_STACK_SIZE HBLKSIZE
709 /* Under normal circumstances, this is big enough to guarantee */
710 /* We don't overflow half of it in a single call to */
714 /* Steal mark stack entries starting at mse low into mark stack local */
715 /* until we either steal mse high, or we have max entries. */
716 /* Return a pointer to the top of the local mark stack. */
717 /* *next is replaced by a pointer to the next unscanned mark stack */
719 mse
* GC_steal_mark_stack(mse
* low
, mse
* high
, mse
* local
,
720 unsigned max
, mse
**next
)
723 mse
*top
= local
- 1;
726 /* Make sure that prior writes to the mark stack are visible. */
727 /* On some architectures, the fact that the reads are */
728 /* volatile should suffice. */
729 # if !defined(IA64) && !defined(HP_PA) && !defined(I386)
732 GC_ASSERT(high
>= low
-1 && high
- low
+ 1 <= GC_mark_stack_size
);
733 for (p
= low
; p
<= high
&& i
<= max
; ++p
) {
734 word descr
= *(volatile word
*) &(p
-> mse_descr
);
735 /* In the IA64 memory model, the following volatile store is */
736 /* ordered after this read of descr. Thus a thread must read */
737 /* the original nonzero value. HP_PA appears to be similar, */
738 /* and if I'm reading the P4 spec correctly, X86 is probably */
739 /* also OK. In some other cases we need a barrier. */
740 # if !defined(IA64) && !defined(HP_PA) && !defined(I386)
744 *(volatile word
*) &(p
-> mse_descr
) = 0;
745 /* More than one thread may get this entry, but that's only */
746 /* a minor performance problem. */
748 top
-> mse_descr
= descr
;
749 top
-> mse_start
= p
-> mse_start
;
750 GC_ASSERT( top
-> mse_descr
& GC_DS_TAGS
!= GC_DS_LENGTH
||
751 top
-> mse_descr
< GC_greatest_plausible_heap_addr
752 - GC_least_plausible_heap_addr
);
753 /* If this is a big object, count it as */
754 /* size/256 + 1 objects. */
756 if ((descr
& GC_DS_TAGS
) == GC_DS_LENGTH
) i
+= (descr
>> 8);
763 /* Copy back a local mark stack. */
764 /* low and high are inclusive bounds. */
765 void GC_return_mark_stack(mse
* low
, mse
* high
)
771 if (high
< low
) return;
772 stack_size
= high
- low
+ 1;
773 GC_acquire_mark_lock();
774 my_top
= GC_mark_stack_top
;
775 my_start
= my_top
+ 1;
776 if (my_start
- GC_mark_stack
+ stack_size
> GC_mark_stack_size
) {
778 if (GC_print_stats
) {
779 GC_printf0("No room to copy back mark stack.");
782 GC_mark_state
= MS_INVALID
;
783 GC_mark_stack_too_small
= TRUE
;
784 /* We drop the local mark stack. We'll fix things later. */
786 BCOPY(low
, my_start
, stack_size
* sizeof(mse
));
787 GC_ASSERT(GC_mark_stack_top
= my_top
);
788 # if !defined(IA64) && !defined(HP_PA)
791 /* On IA64, the volatile write acts as a release barrier. */
792 GC_mark_stack_top
= my_top
+ stack_size
;
794 GC_release_mark_lock();
795 GC_notify_all_marker();
798 /* Mark from the local mark stack. */
799 /* On return, the local mark stack is empty. */
800 /* But this may be achieved by copying the */
801 /* local mark stack back into the global one. */
802 void GC_do_local_mark(mse
*local_mark_stack
, mse
*local_top
)
805 # define N_LOCAL_ITERS 1
807 # ifdef GC_ASSERTIONS
808 /* Make sure we don't hold mark lock. */
809 GC_acquire_mark_lock();
810 GC_release_mark_lock();
813 for (n
= 0; n
< N_LOCAL_ITERS
; ++n
) {
814 local_top
= GC_mark_from(local_top
, local_mark_stack
,
815 local_mark_stack
+ LOCAL_MARK_STACK_SIZE
);
816 if (local_top
< local_mark_stack
) return;
817 if (local_top
- local_mark_stack
>= LOCAL_MARK_STACK_SIZE
/2) {
818 GC_return_mark_stack(local_mark_stack
, local_top
);
822 if (GC_mark_stack_top
< GC_first_nonempty
&&
823 GC_active_count
< GC_helper_count
824 && local_top
> local_mark_stack
+ 1) {
825 /* Try to share the load, since the main stack is empty, */
826 /* and helper threads are waiting for a refill. */
827 /* The entries near the bottom of the stack are likely */
828 /* to require more work. Thus we return those, eventhough */
831 mse
* new_bottom
= local_mark_stack
832 + (local_top
- local_mark_stack
)/2;
833 GC_ASSERT(new_bottom
> local_mark_stack
834 && new_bottom
< local_top
);
835 GC_return_mark_stack(local_mark_stack
, new_bottom
- 1);
836 memmove(local_mark_stack
, new_bottom
,
837 (local_top
- new_bottom
+ 1) * sizeof(mse
));
838 local_top
-= (new_bottom
- local_mark_stack
);
843 #define ENTRIES_TO_GET 5
845 long GC_markers
= 2; /* Normally changed by thread-library- */
846 /* -specific code. */
848 /* Mark using the local mark stack until the global mark stack is empty */
849 /* and there are no active workers. Update GC_first_nonempty to reflect */
851 /* Caller does not hold mark lock. */
852 /* Caller has already incremented GC_helper_count. We decrement it, */
853 /* and maintain GC_active_count. */
854 void GC_mark_local(mse
*local_mark_stack
, int id
)
856 mse
* my_first_nonempty
;
858 GC_acquire_mark_lock();
860 my_first_nonempty
= GC_first_nonempty
;
861 GC_ASSERT(GC_first_nonempty
>= GC_mark_stack
&&
862 GC_first_nonempty
<= GC_mark_stack_top
+ 1);
864 GC_printf1("Starting mark helper %lu\n", (unsigned long)id
);
866 GC_release_mark_lock();
873 mse
* global_first_nonempty
= GC_first_nonempty
;
875 GC_ASSERT(my_first_nonempty
>= GC_mark_stack
&&
876 my_first_nonempty
<= GC_mark_stack_top
+ 1);
877 GC_ASSERT(global_first_nonempty
>= GC_mark_stack
&&
878 global_first_nonempty
<= GC_mark_stack_top
+ 1);
879 if (my_first_nonempty
< global_first_nonempty
) {
880 my_first_nonempty
= global_first_nonempty
;
881 } else if (global_first_nonempty
< my_first_nonempty
) {
882 GC_compare_and_exchange((word
*)(&GC_first_nonempty
),
883 (word
) global_first_nonempty
,
884 (word
) my_first_nonempty
);
885 /* If this fails, we just go ahead, without updating */
886 /* GC_first_nonempty. */
888 /* Perhaps we should also update GC_first_nonempty, if it */
889 /* is less. But that would require using atomic updates. */
890 my_top
= GC_mark_stack_top
;
891 n_on_stack
= my_top
- my_first_nonempty
+ 1;
892 if (0 == n_on_stack
) {
893 GC_acquire_mark_lock();
894 my_top
= GC_mark_stack_top
;
895 n_on_stack
= my_top
- my_first_nonempty
+ 1;
896 if (0 == n_on_stack
) {
898 GC_ASSERT(GC_active_count
<= GC_helper_count
);
899 /* Other markers may redeposit objects */
901 if (0 == GC_active_count
) GC_notify_all_marker();
902 while (GC_active_count
> 0
903 && GC_first_nonempty
> GC_mark_stack_top
) {
904 /* We will be notified if either GC_active_count */
905 /* reaches zero, or if more objects are pushed on */
906 /* the global mark stack. */
909 if (GC_active_count
== 0 &&
910 GC_first_nonempty
> GC_mark_stack_top
) {
911 GC_bool need_to_notify
= FALSE
;
912 /* The above conditions can't be falsified while we */
913 /* hold the mark lock, since neither */
914 /* GC_active_count nor GC_mark_stack_top can */
915 /* change. GC_first_nonempty can only be */
916 /* incremented asynchronously. Thus we know that */
917 /* both conditions actually held simultaneously. */
919 if (0 == GC_helper_count
) need_to_notify
= TRUE
;
922 "Finished mark helper %lu\n", (unsigned long)id
);
924 GC_release_mark_lock();
925 if (need_to_notify
) GC_notify_all_marker();
928 /* else there's something on the stack again, or */
929 /* another helper may push something. */
931 GC_ASSERT(GC_active_count
> 0);
932 GC_release_mark_lock();
935 GC_release_mark_lock();
938 n_to_get
= ENTRIES_TO_GET
;
939 if (n_on_stack
< 2 * ENTRIES_TO_GET
) n_to_get
= 1;
940 local_top
= GC_steal_mark_stack(my_first_nonempty
, my_top
,
941 local_mark_stack
, n_to_get
,
943 GC_ASSERT(my_first_nonempty
>= GC_mark_stack
&&
944 my_first_nonempty
<= GC_mark_stack_top
+ 1);
945 GC_do_local_mark(local_mark_stack
, local_top
);
949 /* Perform Parallel mark. */
950 /* We hold the GC lock, not the mark lock. */
951 /* Currently runs until the mark stack is */
953 void GC_do_parallel_mark()
955 mse local_mark_stack
[LOCAL_MARK_STACK_SIZE
];
959 GC_acquire_mark_lock();
960 GC_ASSERT(I_HOLD_LOCK());
961 /* This could be a GC_ASSERT, but it seems safer to keep it on */
962 /* all the time, especially since it's cheap. */
963 if (GC_help_wanted
|| GC_active_count
!= 0 || GC_helper_count
!= 0)
964 ABORT("Tried to start parallel mark in bad state");
966 GC_printf1("Starting marking for mark phase number %lu\n",
967 (unsigned long)GC_mark_no
);
969 GC_first_nonempty
= GC_mark_stack
;
972 GC_help_wanted
= TRUE
;
973 GC_release_mark_lock();
974 GC_notify_all_marker();
975 /* Wake up potential helpers. */
976 GC_mark_local(local_mark_stack
, 0);
977 GC_acquire_mark_lock();
978 GC_help_wanted
= FALSE
;
979 /* Done; clean up. */
980 while (GC_helper_count
> 0) GC_wait_marker();
981 /* GC_helper_count cannot be incremented while GC_help_wanted == FALSE */
984 "Finished marking for mark phase number %lu\n",
985 (unsigned long)GC_mark_no
);
988 GC_release_mark_lock();
989 GC_notify_all_marker();
993 /* Try to help out the marker, if it's running. */
994 /* We do not hold the GC lock, but the requestor does. */
995 void GC_help_marker(word my_mark_no
)
997 mse local_mark_stack
[LOCAL_MARK_STACK_SIZE
];
999 mse
* my_first_nonempty
;
1001 if (!GC_parallel
) return;
1002 GC_acquire_mark_lock();
1003 while (GC_mark_no
< my_mark_no
1004 || !GC_help_wanted
&& GC_mark_no
== my_mark_no
) {
1007 my_id
= GC_helper_count
;
1008 if (GC_mark_no
!= my_mark_no
|| my_id
>= GC_markers
) {
1009 /* Second test is useful only if original threads can also */
1010 /* act as helpers. Under Linux they can't. */
1011 GC_release_mark_lock();
1014 GC_helper_count
= my_id
+ 1;
1015 GC_release_mark_lock();
1016 GC_mark_local(local_mark_stack
, my_id
);
1017 /* GC_mark_local decrements GC_helper_count. */
1020 #endif /* PARALLEL_MARK */
1022 /* Allocate or reallocate space for mark stack of size s words */
1023 /* May silently fail. */
1024 static void alloc_mark_stack(n
)
1027 mse
* new_stack
= (mse
*)GC_scratch_alloc(n
* sizeof(struct GC_ms_entry
));
1029 GC_mark_stack_too_small
= FALSE
;
1030 if (GC_mark_stack_size
!= 0) {
1031 if (new_stack
!= 0) {
1032 word displ
= (word
)GC_mark_stack
& (GC_page_size
- 1);
1033 signed_word size
= GC_mark_stack_size
* sizeof(struct GC_ms_entry
);
1035 /* Recycle old space */
1036 if (0 != displ
) displ
= GC_page_size
- displ
;
1037 size
= (size
- displ
) & ~(GC_page_size
- 1);
1039 GC_add_to_heap((struct hblk
*)
1040 ((word
)GC_mark_stack
+ displ
), (word
)size
);
1042 GC_mark_stack
= new_stack
;
1043 GC_mark_stack_size
= n
;
1044 GC_mark_stack_limit
= new_stack
+ n
;
1046 if (GC_print_stats
) {
1047 GC_printf1("Grew mark stack to %lu frames\n",
1048 (unsigned long) GC_mark_stack_size
);
1053 if (GC_print_stats
) {
1054 GC_printf1("Failed to grow mark stack to %lu frames\n",
1060 if (new_stack
== 0) {
1061 GC_err_printf0("No space for mark stack\n");
1064 GC_mark_stack
= new_stack
;
1065 GC_mark_stack_size
= n
;
1066 GC_mark_stack_limit
= new_stack
+ n
;
1068 GC_mark_stack_top
= GC_mark_stack
-1;
1073 alloc_mark_stack(INITIAL_MARK_STACK_SIZE
);
1077 * Push all locations between b and t onto the mark stack.
1078 * b is the first location to be checked. t is one past the last
1079 * location to be checked.
1080 * Should only be used if there is no possibility of mark stack
1083 void GC_push_all(bottom
, top
)
1087 register word length
;
1089 bottom
= (ptr_t
)(((word
) bottom
+ ALIGNMENT
-1) & ~(ALIGNMENT
-1));
1090 top
= (ptr_t
)(((word
) top
) & ~(ALIGNMENT
-1));
1091 if (top
== 0 || bottom
== top
) return;
1092 GC_mark_stack_top
++;
1093 if (GC_mark_stack_top
>= GC_mark_stack_limit
) {
1094 ABORT("unexpected mark stack overflow");
1096 length
= top
- bottom
;
1097 # if GC_DS_TAGS > ALIGNMENT - 1
1098 length
+= GC_DS_TAGS
;
1099 length
&= ~GC_DS_TAGS
;
1101 GC_mark_stack_top
-> mse_start
= (word
*)bottom
;
1102 GC_mark_stack_top
-> mse_descr
= length
;
1106 * Analogous to the above, but push only those pages h with dirty_fn(h) != 0.
1107 * We use push_fn to actually push the block.
1108 * Used both to selectively push dirty pages, or to push a block
1109 * in piecemeal fashion, to allow for more marking concurrency.
1110 * Will not overflow mark stack if push_fn pushes a small fixed number
1111 * of entries. (This is invoked only if push_fn pushes a single entry,
1112 * or if it marks each object before pushing it, thus ensuring progress
1113 * in the event of a stack overflow.)
1115 void GC_push_selected(bottom
, top
, dirty_fn
, push_fn
)
1118 int (*dirty_fn
) GC_PROTO((struct hblk
* h
));
1119 void (*push_fn
) GC_PROTO((ptr_t bottom
, ptr_t top
));
1121 register struct hblk
* h
;
1123 bottom
= (ptr_t
)(((long) bottom
+ ALIGNMENT
-1) & ~(ALIGNMENT
-1));
1124 top
= (ptr_t
)(((long) top
) & ~(ALIGNMENT
-1));
1126 if (top
== 0 || bottom
== top
) return;
1127 h
= HBLKPTR(bottom
+ HBLKSIZE
);
1128 if (top
<= (ptr_t
) h
) {
1129 if ((*dirty_fn
)(h
-1)) {
1130 (*push_fn
)(bottom
, top
);
1134 if ((*dirty_fn
)(h
-1)) {
1135 (*push_fn
)(bottom
, (ptr_t
)h
);
1137 while ((ptr_t
)(h
+1) <= top
) {
1138 if ((*dirty_fn
)(h
)) {
1139 if ((word
)(GC_mark_stack_top
- GC_mark_stack
)
1140 > 3 * GC_mark_stack_size
/ 4) {
1141 /* Danger of mark stack overflow */
1142 (*push_fn
)((ptr_t
)h
, top
);
1145 (*push_fn
)((ptr_t
)h
, (ptr_t
)(h
+1));
1150 if ((ptr_t
)h
!= top
) {
1151 if ((*dirty_fn
)(h
)) {
1152 (*push_fn
)((ptr_t
)h
, top
);
1155 if (GC_mark_stack_top
>= GC_mark_stack_limit
) {
1156 ABORT("unexpected mark stack overflow");
1160 # ifndef SMALL_CONFIG
1162 #ifdef PARALLEL_MARK
1163 /* Break up root sections into page size chunks to better spread */
1165 GC_bool
GC_true_func(struct hblk
*h
) { return TRUE
; }
1166 # define GC_PUSH_ALL(b,t) GC_push_selected(b,t,GC_true_func,GC_push_all);
1168 # define GC_PUSH_ALL(b,t) GC_push_all(b,t);
1172 void GC_push_conditional(bottom
, top
, all
)
1178 if (GC_dirty_maintained
) {
1180 /* Pages that were never dirtied cannot contain pointers */
1181 GC_push_selected(bottom
, top
, GC_page_was_ever_dirty
, GC_push_all
);
1183 GC_push_all(bottom
, top
);
1186 GC_push_all(bottom
, top
);
1189 GC_push_selected(bottom
, top
, GC_page_was_dirty
, GC_push_all
);
1194 # if defined(MSWIN32) || defined(MSWINCE)
1195 void __cdecl
GC_push_one(p
)
1201 GC_PUSH_ONE_STACK(p
, MARKED_FROM_REGISTER
);
1204 struct GC_ms_entry
*GC_mark_and_push(obj
, mark_stack_ptr
, mark_stack_limit
, src
)
1206 struct GC_ms_entry
* mark_stack_ptr
;
1207 struct GC_ms_entry
* mark_stack_limit
;
1211 PUSH_CONTENTS(obj
, mark_stack_ptr
/* modified */, mark_stack_limit
, src
,
1212 was_marked
/* internally generated exit label */);
1213 return mark_stack_ptr
;
1217 # define BASE(p) (word)GC_base((void *)(p))
1219 # define BASE(p) (word)GC_base((char *)(p))
1222 /* Mark and push (i.e. gray) a single object p onto the main */
1223 /* mark stack. Consider p to be valid if it is an interior */
1225 /* The object p has passed a preliminary pointer validity */
1226 /* test, but we do not definitely know whether it is valid. */
1227 /* Mark bits are NOT atomically updated. Thus this must be the */
1228 /* only thread setting them. */
1229 # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
1230 void GC_mark_and_push_stack(p
, source
)
1233 void GC_mark_and_push_stack(p
)
1239 register hdr
* hhdr
;
1243 if (IS_FORWARDING_ADDR_OR_NIL(hhdr
)) {
1247 displ
= BYTES_TO_WORDS(HBLKDISPL(r
));
1250 register map_entry_type map_entry
;
1252 displ
= HBLKDISPL(p
);
1253 map_entry
= MAP_ENTRY((hhdr
-> hb_map
), displ
);
1254 if (map_entry
>= MAX_OFFSET
) {
1255 if (map_entry
== OFFSET_TOO_BIG
|| !GC_all_interior_pointers
) {
1257 displ
= BYTES_TO_WORDS(HBLKDISPL(r
));
1258 if (r
== 0) hhdr
= 0;
1260 /* Offset invalid, but map reflects interior pointers */
1264 displ
= BYTES_TO_WORDS(displ
);
1266 r
= (word
)((word
*)(HBLKPTR(p
)) + displ
);
1269 /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
1270 /* displ is the word index within the block. */
1272 # ifdef PRINT_BLACK_LIST
1273 GC_add_to_black_list_stack(p
, source
);
1275 GC_add_to_black_list_stack(p
);
1277 # undef source /* In case we had to define it. */
1279 if (!mark_bit_from_hdr(hhdr
, displ
)) {
1280 set_mark_bit_from_hdr(hhdr
, displ
);
1281 GC_STORE_BACK_PTR(source
, (ptr_t
)r
);
1282 PUSH_OBJ((word
*)r
, hhdr
, GC_mark_stack_top
,
1283 GC_mark_stack_limit
);
1290 # define TRACE_ENTRIES 1000
1292 struct trace_entry
{
1298 } GC_trace_buf
[TRACE_ENTRIES
];
1300 int GC_trace_buf_ptr
= 0;
1302 void GC_add_trace_entry(char *kind
, word arg1
, word arg2
)
1304 GC_trace_buf
[GC_trace_buf_ptr
].kind
= kind
;
1305 GC_trace_buf
[GC_trace_buf_ptr
].gc_no
= GC_gc_no
;
1306 GC_trace_buf
[GC_trace_buf_ptr
].words_allocd
= GC_words_allocd
;
1307 GC_trace_buf
[GC_trace_buf_ptr
].arg1
= arg1
^ 0x80000000;
1308 GC_trace_buf
[GC_trace_buf_ptr
].arg2
= arg2
^ 0x80000000;
1310 if (GC_trace_buf_ptr
>= TRACE_ENTRIES
) GC_trace_buf_ptr
= 0;
1313 void GC_print_trace(word gc_no
, GC_bool lock
)
1316 struct trace_entry
*p
;
1319 for (i
= GC_trace_buf_ptr
-1; i
!= GC_trace_buf_ptr
; i
--) {
1320 if (i
< 0) i
= TRACE_ENTRIES
-1;
1321 p
= GC_trace_buf
+ i
;
1322 if (p
-> gc_no
< gc_no
|| p
-> kind
== 0) return;
1323 printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
1324 p
-> kind
, p
-> gc_no
, p
-> words_allocd
,
1325 (p
-> arg1
) ^ 0x80000000, (p
-> arg2
) ^ 0x80000000);
1327 printf("Trace incomplete\n");
1331 # endif /* TRACE_BUF */
1334 * A version of GC_push_all that treats all interior pointers as valid
1335 * and scans the entire region immediately, in case the contents
1338 void GC_push_all_eager(bottom
, top
)
1342 word
* b
= (word
*)(((long) bottom
+ ALIGNMENT
-1) & ~(ALIGNMENT
-1));
1343 word
* t
= (word
*)(((long) top
) & ~(ALIGNMENT
-1));
1347 register ptr_t greatest_ha
= GC_greatest_plausible_heap_addr
;
1348 register ptr_t least_ha
= GC_least_plausible_heap_addr
;
1349 # define GC_greatest_plausible_heap_addr greatest_ha
1350 # define GC_least_plausible_heap_addr least_ha
1352 if (top
== 0) return;
1353 /* check all pointers in range and push if they appear */
1355 lim
= t
- 1 /* longword */;
1356 for (p
= b
; p
<= lim
; p
= (word
*)(((char *)p
) + ALIGNMENT
)) {
1358 GC_PUSH_ONE_STACK(q
, p
);
1360 # undef GC_greatest_plausible_heap_addr
1361 # undef GC_least_plausible_heap_addr
1366 * A version of GC_push_all that treats all interior pointers as valid
1367 * and scans part of the area immediately, to make sure that saved
1368 * register values are not lost.
1369 * Cold_gc_frame delimits the stack section that must be scanned
1370 * eagerly. A zero value indicates that no eager scanning is needed.
1372 void GC_push_all_stack_partially_eager(bottom
, top
, cold_gc_frame
)
1375 ptr_t cold_gc_frame
;
1377 if (!NEED_FIXUP_POINTER
&& GC_all_interior_pointers
) {
1378 # define EAGER_BYTES 1024
1379 /* Push the hot end of the stack eagerly, so that register values */
1380 /* saved inside GC frames are marked before they disappear. */
1381 /* The rest of the marking can be deferred until later. */
1382 if (0 == cold_gc_frame
) {
1383 GC_push_all_stack(bottom
, top
);
1386 GC_ASSERT(bottom
<= cold_gc_frame
&& cold_gc_frame
<= top
);
1387 # ifdef STACK_GROWS_DOWN
1388 GC_push_all(cold_gc_frame
- sizeof(ptr_t
), top
);
1389 GC_push_all_eager(bottom
, cold_gc_frame
);
1390 # else /* STACK_GROWS_UP */
1391 GC_push_all(bottom
, cold_gc_frame
+ sizeof(ptr_t
));
1392 GC_push_all_eager(cold_gc_frame
, top
);
1393 # endif /* STACK_GROWS_UP */
1395 GC_push_all_eager(bottom
, top
);
1398 GC_add_trace_entry("GC_push_all_stack", bottom
, top
);
1401 #endif /* !THREADS */
1403 void GC_push_all_stack(bottom
, top
)
1407 if (!NEED_FIXUP_POINTER
&& GC_all_interior_pointers
) {
1408 GC_push_all(bottom
, top
);
1410 GC_push_all_eager(bottom
, top
);
1414 #if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
1415 /* Push all objects reachable from marked objects in the given block */
1416 /* of size 1 objects. */
1417 void GC_push_marked1(h
, hhdr
)
1419 register hdr
* hhdr
;
1421 word
* mark_word_addr
= &(hhdr
->hb_marks
[0]);
1426 register word mark_word
;
1427 register ptr_t greatest_ha
= GC_greatest_plausible_heap_addr
;
1428 register ptr_t least_ha
= GC_least_plausible_heap_addr
;
1429 register mse
* mark_stack_top
= GC_mark_stack_top
;
1430 register mse
* mark_stack_limit
= GC_mark_stack_limit
;
1431 # define GC_mark_stack_top mark_stack_top
1432 # define GC_mark_stack_limit mark_stack_limit
1433 # define GC_greatest_plausible_heap_addr greatest_ha
1434 # define GC_least_plausible_heap_addr least_ha
1436 p
= (word
*)(h
->hb_body
);
1437 plim
= (word
*)(((word
)h
) + HBLKSIZE
);
1439 /* go through all words in block */
1441 mark_word
= *mark_word_addr
++;
1443 while(mark_word
!= 0) {
1444 if (mark_word
& 1) {
1446 GC_PUSH_ONE_HEAP(q
, p
+ i
);
1453 # undef GC_greatest_plausible_heap_addr
1454 # undef GC_least_plausible_heap_addr
1455 # undef GC_mark_stack_top
1456 # undef GC_mark_stack_limit
1457 GC_mark_stack_top
= mark_stack_top
;
1463 /* Push all objects reachable from marked objects in the given block */
1464 /* of size 2 objects. */
1465 void GC_push_marked2(h
, hhdr
)
1467 register hdr
* hhdr
;
1469 word
* mark_word_addr
= &(hhdr
->hb_marks
[0]);
1474 register word mark_word
;
1475 register ptr_t greatest_ha
= GC_greatest_plausible_heap_addr
;
1476 register ptr_t least_ha
= GC_least_plausible_heap_addr
;
1477 register mse
* mark_stack_top
= GC_mark_stack_top
;
1478 register mse
* mark_stack_limit
= GC_mark_stack_limit
;
1479 # define GC_mark_stack_top mark_stack_top
1480 # define GC_mark_stack_limit mark_stack_limit
1481 # define GC_greatest_plausible_heap_addr greatest_ha
1482 # define GC_least_plausible_heap_addr least_ha
1484 p
= (word
*)(h
->hb_body
);
1485 plim
= (word
*)(((word
)h
) + HBLKSIZE
);
1487 /* go through all words in block */
1489 mark_word
= *mark_word_addr
++;
1491 while(mark_word
!= 0) {
1492 if (mark_word
& 1) {
1494 GC_PUSH_ONE_HEAP(q
, p
+ i
);
1496 GC_PUSH_ONE_HEAP(q
, p
+ i
);
1503 # undef GC_greatest_plausible_heap_addr
1504 # undef GC_least_plausible_heap_addr
1505 # undef GC_mark_stack_top
1506 # undef GC_mark_stack_limit
1507 GC_mark_stack_top
= mark_stack_top
;
1510 /* Push all objects reachable from marked objects in the given block */
1511 /* of size 4 objects. */
1512 /* There is a risk of mark stack overflow here. But we handle that. */
1513 /* And only unmarked objects get pushed, so it's not very likely. */
1514 void GC_push_marked4(h
, hhdr
)
1516 register hdr
* hhdr
;
1518 word
* mark_word_addr
= &(hhdr
->hb_marks
[0]);
1523 register word mark_word
;
1524 register ptr_t greatest_ha
= GC_greatest_plausible_heap_addr
;
1525 register ptr_t least_ha
= GC_least_plausible_heap_addr
;
1526 register mse
* mark_stack_top
= GC_mark_stack_top
;
1527 register mse
* mark_stack_limit
= GC_mark_stack_limit
;
1528 # define GC_mark_stack_top mark_stack_top
1529 # define GC_mark_stack_limit mark_stack_limit
1530 # define GC_greatest_plausible_heap_addr greatest_ha
1531 # define GC_least_plausible_heap_addr least_ha
1533 p
= (word
*)(h
->hb_body
);
1534 plim
= (word
*)(((word
)h
) + HBLKSIZE
);
1536 /* go through all words in block */
1538 mark_word
= *mark_word_addr
++;
1540 while(mark_word
!= 0) {
1541 if (mark_word
& 1) {
1543 GC_PUSH_ONE_HEAP(q
, p
+ i
);
1545 GC_PUSH_ONE_HEAP(q
, p
+ i
+ 1);
1547 GC_PUSH_ONE_HEAP(q
, p
+ i
+ 2);
1549 GC_PUSH_ONE_HEAP(q
, p
+ i
+ 3);
1556 # undef GC_greatest_plausible_heap_addr
1557 # undef GC_least_plausible_heap_addr
1558 # undef GC_mark_stack_top
1559 # undef GC_mark_stack_limit
1560 GC_mark_stack_top
= mark_stack_top
;
1563 #endif /* UNALIGNED */
1565 #endif /* SMALL_CONFIG */
1567 /* Push all objects reachable from marked objects in the given block */
1568 void GC_push_marked(h
, hhdr
)
1570 register hdr
* hhdr
;
1572 register int sz
= hhdr
-> hb_sz
;
1573 register int descr
= hhdr
-> hb_descr
;
1575 register int word_no
;
1576 register word
* lim
;
1577 register mse
* GC_mark_stack_top_reg
;
1578 register mse
* mark_stack_limit
= GC_mark_stack_limit
;
1580 /* Some quick shortcuts: */
1581 if ((0 | GC_DS_LENGTH
) == descr
) return;
1582 if (GC_block_empty(hhdr
)/* nothing marked */) return;
1583 GC_n_rescuing_pages
++;
1584 GC_objects_are_marked
= TRUE
;
1585 if (sz
> MAXOBJSZ
) {
1588 lim
= (word
*)(h
+ 1) - sz
;
1592 # if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
1594 GC_push_marked1(h
, hhdr
);
1597 # if !defined(SMALL_CONFIG) && !defined(UNALIGNED) && \
1598 !defined(USE_MARK_BYTES)
1600 GC_push_marked2(h
, hhdr
);
1603 GC_push_marked4(h
, hhdr
);
1607 GC_mark_stack_top_reg
= GC_mark_stack_top
;
1608 for (p
= (word
*)h
, word_no
= 0; p
<= lim
; p
+= sz
, word_no
+= sz
) {
1609 if (mark_bit_from_hdr(hhdr
, word_no
)) {
1610 /* Mark from fields inside the object */
1611 PUSH_OBJ((word
*)p
, hhdr
, GC_mark_stack_top_reg
, mark_stack_limit
);
1613 /* Subtract this object from total, since it was */
1614 /* added in twice. */
1615 GC_composite_in_use
-= sz
;
1619 GC_mark_stack_top
= GC_mark_stack_top_reg
;
1623 #ifndef SMALL_CONFIG
1624 /* Test whether any page in the given block is dirty */
1625 GC_bool
GC_block_was_dirty(h
, hhdr
)
1627 register hdr
* hhdr
;
1629 register int sz
= hhdr
-> hb_sz
;
1631 if (sz
< MAXOBJSZ
) {
1632 return(GC_page_was_dirty(h
));
1634 register ptr_t p
= (ptr_t
)h
;
1635 sz
= WORDS_TO_BYTES(sz
);
1636 while (p
< (ptr_t
)h
+ sz
) {
1637 if (GC_page_was_dirty((struct hblk
*)p
)) return(TRUE
);
1643 #endif /* SMALL_CONFIG */
1645 /* Similar to GC_push_next_marked, but return address of next block */
1646 struct hblk
* GC_push_next_marked(h
)
1649 register hdr
* hhdr
;
1651 h
= GC_next_used_block(h
);
1652 if (h
== 0) return(0);
1654 GC_push_marked(h
, hhdr
);
1655 return(h
+ OBJ_SZ_TO_BLOCKS(hhdr
-> hb_sz
));
1658 #ifndef SMALL_CONFIG
1659 /* Identical to above, but mark only from dirty pages */
1660 struct hblk
* GC_push_next_marked_dirty(h
)
1663 register hdr
* hhdr
;
1665 if (!GC_dirty_maintained
) { ABORT("dirty bits not set up"); }
1667 h
= GC_next_used_block(h
);
1668 if (h
== 0) return(0);
1670 # ifdef STUBBORN_ALLOC
1671 if (hhdr
-> hb_obj_kind
== STUBBORN
) {
1672 if (GC_page_was_changed(h
) && GC_block_was_dirty(h
, hhdr
)) {
1676 if (GC_block_was_dirty(h
, hhdr
)) break;
1679 if (GC_block_was_dirty(h
, hhdr
)) break;
1681 h
+= OBJ_SZ_TO_BLOCKS(hhdr
-> hb_sz
);
1683 GC_push_marked(h
, hhdr
);
1684 return(h
+ OBJ_SZ_TO_BLOCKS(hhdr
-> hb_sz
));
1688 /* Similar to above, but for uncollectable pages. Needed since we */
1689 /* do not clear marks for such pages, even for full collections. */
1690 struct hblk
* GC_push_next_marked_uncollectable(h
)
1693 register hdr
* hhdr
= HDR(h
);
1696 h
= GC_next_used_block(h
);
1697 if (h
== 0) return(0);
1699 if (hhdr
-> hb_obj_kind
== UNCOLLECTABLE
) break;
1700 h
+= OBJ_SZ_TO_BLOCKS(hhdr
-> hb_sz
);
1702 GC_push_marked(h
, hhdr
);
1703 return(h
+ OBJ_SZ_TO_BLOCKS(hhdr
-> hb_sz
));