126
133
/* Is a collection in progress? Note that this can return true in the */
127
134
/* nonincremental case, if a collection has been abandoned and the */
128
135
/* mark state is now MS_INVALID. */
129
GC_bool GC_collection_in_progress()
136
GC_bool GC_collection_in_progress(void)
131
138
return(GC_mark_state != MS_NONE);
134
141
/* clear all mark bits in the header */
135
void GC_clear_hdr_marks(hhdr)
142
void GC_clear_hdr_marks(hdr *hhdr)
144
size_t last_bit = FINAL_MARK_BIT(hhdr -> hb_sz);
138
146
# ifdef USE_MARK_BYTES
139
147
BZERO(hhdr -> hb_marks, MARK_BITS_SZ);
148
hhdr -> hb_marks[last_bit] = 1;
141
150
BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
151
set_mark_bit_from_hdr(hhdr, last_bit);
153
hhdr -> hb_n_marks = 0;
145
156
/* Set all mark bits in the header. Used for uncollectable blocks. */
146
void GC_set_hdr_marks(hhdr)
157
void GC_set_hdr_marks(hdr *hhdr)
160
size_t sz = hhdr -> hb_sz;
161
size_t n_marks = FINAL_MARK_BIT(sz);
151
for (i = 0; i < MARK_BITS_SZ; ++i) {
152
# ifdef USE_MARK_BYTES
163
# ifdef USE_MARK_BYTES
164
for (i = 0; i <= n_marks; i += MARK_BIT_OFFSET(sz)) {
153
165
hhdr -> hb_marks[i] = 1;
168
for (i = 0; i < divWORDSZ(n_marks + WORDSZ); ++i) {
155
169
hhdr -> hb_marks[i] = ONES;
172
# ifdef MARK_BIT_PER_OBJ
173
hhdr -> hb_n_marks = n_marks - 1;
175
hhdr -> hb_n_marks = HBLK_OBJS(sz);
161
180
* Clear all mark bits associated with block h.
164
# if defined(__STDC__) || defined(__cplusplus)
165
static void clear_marks_for_block(struct hblk *h, word dummy)
167
static void clear_marks_for_block(h, dummy)
183
static void clear_marks_for_block(struct hblk *h, word dummy)
172
185
register hdr * hhdr = HDR(h);
181
194
/* Slow but general routines for setting/clearing/asking about mark bits */
182
void GC_set_mark_bit(p)
185
register struct hblk *h = HBLKPTR(p);
186
register hdr * hhdr = HDR(h);
187
register int word_no = (word *)p - (word *)h;
189
set_mark_bit_from_hdr(hhdr, word_no);
192
void GC_clear_mark_bit(p)
195
register struct hblk *h = HBLKPTR(p);
196
register hdr * hhdr = HDR(h);
197
register int word_no = (word *)p - (word *)h;
199
clear_mark_bit_from_hdr(hhdr, word_no);
202
GC_bool GC_is_marked(p)
205
register struct hblk *h = HBLKPTR(p);
206
register hdr * hhdr = HDR(h);
207
register int word_no = (word *)p - (word *)h;
209
return(mark_bit_from_hdr(hhdr, word_no));
195
void GC_set_mark_bit(ptr_t p)
197
struct hblk *h = HBLKPTR(p);
199
word bit_no = MARK_BIT_NO(p - (ptr_t)h, hhdr -> hb_sz);
201
if (!mark_bit_from_hdr(hhdr, bit_no)) {
202
set_mark_bit_from_hdr(hhdr, bit_no);
203
++hhdr -> hb_n_marks;
207
void GC_clear_mark_bit(ptr_t p)
209
struct hblk *h = HBLKPTR(p);
211
word bit_no = MARK_BIT_NO(p - (ptr_t)h, hhdr -> hb_sz);
213
if (mark_bit_from_hdr(hhdr, bit_no)) {
215
clear_mark_bit_from_hdr(hhdr, bit_no);
216
n_marks = hhdr -> hb_n_marks - 1;
217
# ifdef PARALLEL_MARK
219
hhdr -> hb_n_marks = n_marks;
220
/* Don't decrement to zero. The counts are approximate due to */
221
/* concurrency issues, but we need to ensure that a count of */
222
/* zero implies an empty block. */
224
hhdr -> hb_n_marks = n_marks;
229
GC_bool GC_is_marked(ptr_t p)
231
struct hblk *h = HBLKPTR(p);
233
word bit_no = MARK_BIT_NO(p - (ptr_t)h, hhdr -> hb_sz);
235
return((GC_bool)mark_bit_from_hdr(hhdr, bit_no));
457
484
/* This code does not appear to be necessary for Windows */
458
485
/* 95/NT/2000. Note that this code should never generate */
459
486
/* an incremental GC write fault. */
487
/* It's conceivable that this is the same issue with */
488
/* terminating threads that we see with Linux and */
489
/* USE_PROC_FOR_LIBRARIES. */
492
ret_val = GC_mark_some_inner(cold_gc_frame);
493
} __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?
494
EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) {
497
# ifdef GC_WIN32_THREADS
498
/* With DllMain-based thread tracking, a thread may have */
499
/* started while we were marking. This is logically equivalent */
500
/* to the exception case; our results are invalid and we have */
501
/* to start over. This cannot be prevented since we can't */
502
/* block in DllMain. */
503
if (GC_started_thread_while_stopped()) goto handle_ex;
463
# else /* __GNUC__ */
508
# else /* __GNUC__ */
465
510
/* Manually install an exception handler since GCC does */
466
511
/* not yet support Structured Exception Handling (SEH) on */
472
517
er.ex_reg.handler = mark_ex_handler;
473
518
asm volatile ("movl %%fs:0, %0" : "=r" (er.ex_reg.prev));
474
519
asm volatile ("movl %0, %%fs:0" : : "r" (&er));
476
# endif /* __GNUC__ */
478
ret_val = GC_mark_some_inner(cold_gc_frame);
482
} __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?
483
EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) {
485
# else /* __GNUC__ */
487
/* Prevent GCC from considering the following code unreachable */
488
/* and thus eliminating it. */
489
if (er.alt_path != 0)
493
/* Execution resumes from here on an access violation. */
495
# endif /* __GNUC__ */
498
if (GC_print_stats) {
499
GC_printf0("Caught ACCESS_VIOLATION in marker. "
500
"Memory mapping disappeared.\n");
502
# endif /* CONDPRINT */
504
/* We have bad roots on the stack. Discard mark stack. */
505
/* Rescan from marked objects. Redetermine roots. */
506
GC_invalidate_mark_state();
515
# else /* __GNUC__ */
520
ret_val = GC_mark_some_inner(cold_gc_frame);
521
/* Prevent GCC from considering the following code unreachable */
522
/* and thus eliminating it. */
523
if (er.alt_path == 0)
518
526
/* Uninstall the exception handler */
519
527
asm volatile ("mov %0, %%fs:0" : : "r" (er.ex_reg.prev));
521
# endif /* __GNUC__ */
530
# endif /* __GNUC__ */
531
# else /* !MSWIN32 */
532
/* Here we are handling the case in which /proc is used for root */
533
/* finding, and we have threads. We may find a stack for a */
534
/* thread that is in the process of exiting, and disappears */
535
/* while we are marking it. This seems extremely difficult to */
536
/* avoid otherwise. */
538
WARN("Incremental GC incompatible with /proc roots\n", 0);
539
/* I'm not sure if this could still work ... */
540
GC_setup_temporary_fault_handler();
541
if(SETJMP(GC_jmp_buf) != 0) goto handle_ex;
542
ret_val = GC_mark_some_inner(cold_gc_frame);
544
GC_reset_fault_handler();
547
# endif /* !MSWIN32 */
550
/* Exception handler starts here for all cases. */
551
if (GC_print_stats) {
552
GC_log_printf("Caught ACCESS_VIOLATION in marker. "
553
"Memory mapping disappeared.\n");
556
/* We have bad roots on the stack. Discard mark stack. */
557
/* Rescan from marked objects. Redetermine roots. */
558
GC_invalidate_mark_state();
562
goto rm_handler; // Back to platform-specific code.
528
GC_bool GC_mark_stack_empty()
564
#endif /* WRAP_MARK_SOME */
567
GC_bool GC_mark_stack_empty(void)
530
569
return(GC_mark_stack_top < GC_mark_stack);
534
word GC_prof_array[10];
535
# define PROF(n) GC_prof_array[n]++
540
/* Given a pointer to someplace other than a small object page or the */
541
/* first page of a large object, either: */
542
/* - return a pointer to somewhere in the first page of the large */
543
/* object, if current points to a large object. */
544
/* In this case *hhdr is replaced with a pointer to the header */
545
/* for the large object. */
546
/* - just return current if it does not point to a large object. */
548
ptr_t GC_find_start(current, hhdr, new_hdr_p)
549
register ptr_t current;
550
register hdr *hhdr, **new_hdr_p;
552
if (GC_all_interior_pointers) {
554
register ptr_t orig = current;
556
current = (ptr_t)HBLKPTR(current);
558
current = current - HBLKSIZE*(word)hhdr;
560
} while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
561
/* current points to near the start of the large object */
562
if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(orig);
563
if ((word *)orig - (word *)current
564
>= (ptrdiff_t)(hhdr->hb_sz)) {
565
/* Pointer past the end of the block */
578
void GC_invalidate_mark_state()
572
void GC_invalidate_mark_state(void)
580
574
GC_mark_state = MS_INVALID;
581
575
GC_mark_stack_top = GC_mark_stack-1;
584
mse * GC_signal_mark_stack_overflow(msp)
578
mse * GC_signal_mark_stack_overflow(mse *msp)
587
580
GC_mark_state = MS_INVALID;
588
581
GC_mark_stack_too_small = TRUE;
590
if (GC_print_stats) {
591
GC_printf1("Mark stack overflow; current size = %lu entries\n",
582
if (GC_print_stats) {
583
GC_log_printf("Mark stack overflow; current size = %lu entries\n",
595
586
return(msp - GC_MARK_STACK_DISCARDS);
599
590
* Mark objects pointed to by the regions described by
600
* mark stack entries between GC_mark_stack and GC_mark_stack_top,
591
* mark stack entries between mark_stack and mark_stack_top,
601
592
* inclusive. Assumes the upper limit of a mark stack entry
602
593
* is never 0. A mark stack entry never has size 0.
603
594
* We try to traverse on the order of a hblk of memory before we return.
609
600
* encoding, we optionally maintain a cache for the block address to
610
601
* header mapping, we prefetch when an object is "grayed", etc.
612
mse * GC_mark_from(mark_stack_top, mark_stack, mark_stack_limit)
613
mse * mark_stack_top;
615
mse * mark_stack_limit;
603
mse * GC_mark_from(mse *mark_stack_top, mse *mark_stack, mse *mark_stack_limit)
617
int credit = HBLKSIZE; /* Remaining credit for marking work */
618
register word * current_p; /* Pointer to current candidate ptr. */
619
register word current; /* Candidate pointer. */
620
register word * limit; /* (Incl) limit of current candidate */
605
signed_word credit = HBLKSIZE; /* Remaining credit for marking work */
606
ptr_t current_p; /* Pointer to current candidate ptr. */
607
word current; /* Candidate pointer. */
608
ptr_t limit; /* (Incl) limit of current candidate */
623
register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
624
register ptr_t least_ha = GC_least_plausible_heap_addr;
611
ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
612
ptr_t least_ha = GC_least_plausible_heap_addr;
625
613
DECLARE_HDR_CACHE;
627
615
# define SPLIT_RANGE_WORDS 128 /* Must be power of 2. */
662
657
/* makes sure we handle */
663
658
/* misaligned pointers. */
664
659
mark_stack_top++;
665
current_p = (word *) ((char *)current_p + new_size);
661
if (GC_trace_addr >= current_p
662
&& GC_trace_addr < current_p + descr) {
663
GC_log_printf("GC:%d splitting (parallel) %p at %p\n",
664
GC_gc_no, current_p, current_p + new_size);
666
# endif /* ENABLE_TRACE */
667
current_p += new_size;
666
668
descr -= new_size;
669
671
# endif /* PARALLEL_MARK */
670
672
mark_stack_top -> mse_start =
671
limit = current_p + SPLIT_RANGE_WORDS-1;
673
limit = current_p + WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
672
674
mark_stack_top -> mse_descr =
673
675
descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
677
if (GC_trace_addr >= current_p
678
&& GC_trace_addr < current_p + descr) {
679
GC_log_printf("GC:%d splitting %p at %p\n",
680
GC_gc_no, current_p, limit);
682
# endif /* ENABLE_TRACE */
674
683
/* Make sure that pointers overlapping the two ranges are */
675
684
/* considered. */
676
limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
685
limit += sizeof(word) - ALIGNMENT;
678
687
case GC_DS_BITMAP:
679
688
mark_stack_top--;
690
if (GC_trace_addr >= current_p
691
&& GC_trace_addr < current_p + WORDS_TO_BYTES(WORDSZ-2)) {
692
GC_log_printf("GC:%d Tracing from %p bitmap descr %lu\n",
693
GC_gc_no, current_p, (unsigned long) descr);
695
# endif /* ENABLE_TRACE */
680
696
descr &= ~GC_DS_TAGS;
681
697
credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
682
698
while (descr != 0) {
683
699
if ((signed_word)descr < 0) {
684
current = *current_p;
700
current = *(word *)current_p;
685
701
FIXUP_POINTER(current);
686
702
if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
687
703
PREFETCH((ptr_t)current);
688
HC_PUSH_CONTENTS((ptr_t)current, mark_stack_top,
705
if (GC_trace_addr == current_p) {
706
GC_log_printf("GC:%d Considering(3) %p -> %p\n",
707
GC_gc_no, current_p, (ptr_t) current);
709
# endif /* ENABLE_TRACE */
710
PUSH_CONTENTS((ptr_t)current, mark_stack_top,
689
711
mark_stack_limit, current_p, exit1);
715
current_p += sizeof(word);
697
719
mark_stack_top--;
721
if (GC_trace_addr >= current_p
722
&& GC_base(current_p) != 0
723
&& GC_base(current_p) == GC_base(GC_trace_addr)) {
724
GC_log_printf("GC:%d Tracing from %p proc descr %lu\n",
725
GC_gc_no, current_p, (unsigned long) descr);
727
# endif /* ENABLE_TRACE */
698
728
credit -= GC_PROC_BYTES;
701
(current_p, mark_stack_top,
731
((word *)current_p, mark_stack_top,
702
732
mark_stack_limit, ENV(descr));
704
734
case GC_DS_PER_OBJECT:
705
735
if ((signed_word)descr >= 0) {
706
736
/* Descriptor is in the object. */
707
descr = *(word *)((ptr_t)current_p + descr - GC_DS_PER_OBJECT);
737
descr = *(word *)(current_p + descr - GC_DS_PER_OBJECT);
709
739
/* Descriptor is in type descriptor pointed to by first */
710
740
/* word in object. */
780
817
while (current_p <= limit) {
781
818
/* Empirically, unrolling this loop doesn't help a lot. */
782
/* Since HC_PUSH_CONTENTS expands to a lot of code, */
819
/* Since PUSH_CONTENTS expands to a lot of code, */
784
current = *current_p;
821
current = *(word *)current_p;
785
822
FIXUP_POINTER(current);
786
PREFETCH((ptr_t)current_p + PREF_DIST*CACHE_LINE_SIZE);
823
PREFETCH(current_p + PREF_DIST*CACHE_LINE_SIZE);
787
824
if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
788
825
/* Prefetch the contents of the object we just pushed. It's */
789
826
/* likely we will need them soon. */
790
827
PREFETCH((ptr_t)current);
791
HC_PUSH_CONTENTS((ptr_t)current, mark_stack_top,
829
if (GC_trace_addr == current_p) {
830
GC_log_printf("GC:%d Considering(1) %p -> %p\n",
831
GC_gc_no, current_p, (ptr_t) current);
833
# endif /* ENABLE_TRACE */
834
PUSH_CONTENTS((ptr_t)current, mark_stack_top,
792
835
mark_stack_limit, current_p, exit2);
794
current_p = (word *)((char *)current_p + ALIGNMENT);
837
current_p += ALIGNMENT;
797
840
# ifndef SMALL_CONFIG
798
841
/* We still need to mark the entry we previously prefetched. */
799
/* We alrady know that it passes the preliminary pointer */
842
/* We already know that it passes the preliminary pointer */
800
843
/* validity test. */
801
HC_PUSH_CONTENTS((ptr_t)deferred, mark_stack_top,
845
if (GC_trace_addr == current_p) {
846
GC_log_printf("GC:%d Considering(2) %p -> %p\n",
847
GC_gc_no, current_p, (ptr_t) deferred);
849
# endif /* ENABLE_TRACE */
850
PUSH_CONTENTS((ptr_t)deferred, mark_stack_top,
802
851
mark_stack_limit, current_p, exit4);
834
882
mse *top = local - 1;
837
/* Make sure that prior writes to the mark stack are visible. */
838
/* On some architectures, the fact that the reads are */
839
/* volatile should suffice. */
840
# if !defined(IA64) && !defined(HP_PA) && !defined(I386)
843
885
GC_ASSERT(high >= low-1 && high - low + 1 <= GC_mark_stack_size);
844
886
for (p = low; p <= high && i <= max; ++p) {
845
word descr = *(volatile word *) &(p -> mse_descr);
846
/* In the IA64 memory model, the following volatile store is */
847
/* ordered after this read of descr. Thus a thread must read */
848
/* the original nonzero value. HP_PA appears to be similar, */
849
/* and if I'm reading the P4 spec correctly, X86 is probably */
850
/* also OK. In some other cases we need a barrier. */
851
# if !defined(IA64) && !defined(HP_PA) && !defined(I386)
887
word descr = AO_load((volatile AO_t *) &(p -> mse_descr));
854
888
if (descr != 0) {
855
*(volatile word *) &(p -> mse_descr) = 0;
889
/* Must be ordered after read of descr: */
890
AO_store_release_write((volatile AO_t *) &(p -> mse_descr), 0);
856
891
/* More than one thread may get this entry, but that's only */
857
892
/* a minor performance problem. */
859
894
top -> mse_descr = descr;
860
895
top -> mse_start = p -> mse_start;
861
GC_ASSERT( (top -> mse_descr & GC_DS_TAGS) != GC_DS_LENGTH ||
862
top -> mse_descr < (ptr_t)GC_greatest_plausible_heap_addr
863
- (ptr_t)GC_least_plausible_heap_addr);
896
GC_ASSERT((top -> mse_descr & GC_DS_TAGS) != GC_DS_LENGTH ||
897
top -> mse_descr < (ptr_t)GC_greatest_plausible_heap_addr
898
- (ptr_t)GC_least_plausible_heap_addr);
864
899
/* If this is a big object, count it as */
865
900
/* size/256 + 1 objects. */
882
917
if (high < low) return;
883
918
stack_size = high - low + 1;
884
919
GC_acquire_mark_lock();
885
my_top = GC_mark_stack_top;
920
my_top = GC_mark_stack_top; /* Concurrent modification impossible. */
886
921
my_start = my_top + 1;
887
922
if (my_start - GC_mark_stack + stack_size > GC_mark_stack_size) {
889
if (GC_print_stats) {
890
GC_printf0("No room to copy back mark stack.");
923
if (GC_print_stats) {
924
GC_log_printf("No room to copy back mark stack.");
893
926
GC_mark_state = MS_INVALID;
894
927
GC_mark_stack_too_small = TRUE;
895
928
/* We drop the local mark stack. We'll fix things later. */
897
930
BCOPY(low, my_start, stack_size * sizeof(mse));
898
GC_ASSERT(GC_mark_stack_top = my_top);
899
# if !defined(IA64) && !defined(HP_PA)
902
/* On IA64, the volatile write acts as a release barrier. */
903
GC_mark_stack_top = my_top + stack_size;
931
GC_ASSERT((mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top))
933
AO_store_release_write((volatile AO_t *)(&GC_mark_stack_top),
934
(AO_t)(my_top + stack_size));
935
/* Ensures visibility of previously written stack contents. */
905
937
GC_release_mark_lock();
906
938
GC_notify_all_marker();
933
if (GC_mark_stack_top < GC_first_nonempty &&
934
GC_active_count < GC_helper_count
965
if ((mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top))
966
< (mse *)AO_load(&GC_first_nonempty)
967
&& GC_active_count < GC_helper_count
935
968
&& local_top > local_mark_stack + 1) {
936
969
/* Try to share the load, since the main stack is empty, */
937
970
/* and helper threads are waiting for a refill. */
938
971
/* The entries near the bottom of the stack are likely */
939
972
/* to require more work. Thus we return those, eventhough */
940
973
/* it's harder. */
942
974
mse * new_bottom = local_mark_stack
943
975
+ (local_top - local_mark_stack)/2;
944
976
GC_ASSERT(new_bottom > local_mark_stack
969
1001
GC_acquire_mark_lock();
970
1002
GC_active_count++;
971
my_first_nonempty = GC_first_nonempty;
972
GC_ASSERT(GC_first_nonempty >= GC_mark_stack &&
973
GC_first_nonempty <= GC_mark_stack_top + 1);
975
GC_printf1("Starting mark helper %lu\n", (unsigned long)id);
1003
my_first_nonempty = (mse *)AO_load(&GC_first_nonempty);
1004
GC_ASSERT((mse *)AO_load(&GC_first_nonempty) >= GC_mark_stack &&
1005
(mse *)AO_load(&GC_first_nonempty) <=
1006
(mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top)) + 1);
1007
if (GC_print_stats == VERBOSE)
1008
GC_log_printf("Starting mark helper %lu\n", (unsigned long)id);
977
1009
GC_release_mark_lock();
979
1011
size_t n_on_stack;
980
1012
size_t n_to_get;
983
1014
mse * local_top;
984
mse * global_first_nonempty = GC_first_nonempty;
1015
mse * global_first_nonempty = (mse *)AO_load(&GC_first_nonempty);
986
1017
GC_ASSERT(my_first_nonempty >= GC_mark_stack &&
987
my_first_nonempty <= GC_mark_stack_top + 1);
1018
my_first_nonempty <=
1019
(mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top)) + 1);
988
1020
GC_ASSERT(global_first_nonempty >= GC_mark_stack &&
989
global_first_nonempty <= GC_mark_stack_top + 1);
1021
global_first_nonempty <=
1022
(mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top)) + 1);
990
1023
if (my_first_nonempty < global_first_nonempty) {
991
1024
my_first_nonempty = global_first_nonempty;
992
1025
} else if (global_first_nonempty < my_first_nonempty) {
993
GC_compare_and_exchange((word *)(&GC_first_nonempty),
994
(word) global_first_nonempty,
995
(word) my_first_nonempty);
1026
AO_compare_and_swap(&GC_first_nonempty,
1027
(AO_t) global_first_nonempty,
1028
(AO_t) my_first_nonempty);
996
1029
/* If this fails, we just go ahead, without updating */
997
1030
/* GC_first_nonempty. */
999
1032
/* Perhaps we should also update GC_first_nonempty, if it */
1000
1033
/* is less. But that would require using atomic updates. */
1001
my_top = GC_mark_stack_top;
1034
my_top = (mse *)AO_load_acquire((volatile AO_t *)(&GC_mark_stack_top));
1002
1035
n_on_stack = my_top - my_first_nonempty + 1;
1003
1036
if (0 == n_on_stack) {
1004
1037
GC_acquire_mark_lock();
1005
1038
my_top = GC_mark_stack_top;
1039
/* Asynchronous modification impossible here, */
1040
/* since we hold mark lock. */
1006
1041
n_on_stack = my_top - my_first_nonempty + 1;
1007
1042
if (0 == n_on_stack) {
1008
1043
GC_active_count--;
1011
1046
/* on the stack. */
1012
1047
if (0 == GC_active_count) GC_notify_all_marker();
1013
1048
while (GC_active_count > 0
1014
&& GC_first_nonempty > GC_mark_stack_top) {
1049
&& (mse *)AO_load(&GC_first_nonempty)
1050
> GC_mark_stack_top) {
1015
1051
/* We will be notified if either GC_active_count */
1016
1052
/* reaches zero, or if more objects are pushed on */
1017
1053
/* the global mark stack. */
1018
1054
GC_wait_marker();
1020
1056
if (GC_active_count == 0 &&
1021
GC_first_nonempty > GC_mark_stack_top) {
1057
(mse *)AO_load(&GC_first_nonempty) > GC_mark_stack_top) {
1022
1058
GC_bool need_to_notify = FALSE;
1023
1059
/* The above conditions can't be falsified while we */
1024
1060
/* hold the mark lock, since neither */
1131
1162
#endif /* PARALLEL_MARK */
1133
/* Allocate or reallocate space for mark stack of size s words */
1134
/* May silently fail. */
1135
static void alloc_mark_stack(n)
1164
/* Allocate or reallocate space for mark stack of size n entries. */
1165
/* May silently fail. */
1166
static void alloc_mark_stack(size_t n)
1138
1168
mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct GC_ms_entry));
1170
/* Don't recycle a stack segment obtained with the wrong flags. */
1171
/* Win32 GetWriteWatch requires the right kind of memory. */
1172
static GC_bool GC_incremental_at_stack_alloc = 0;
1173
GC_bool recycle_old = (!GC_incremental || GC_incremental_at_stack_alloc);
1175
GC_incremental_at_stack_alloc = GC_incremental;
1177
# define recycle_old 1
1140
1180
GC_mark_stack_too_small = FALSE;
1141
1181
if (GC_mark_stack_size != 0) {
1142
1182
if (new_stack != 0) {
1143
word displ = (word)GC_mark_stack & (GC_page_size - 1);
1144
signed_word size = GC_mark_stack_size * sizeof(struct GC_ms_entry);
1184
/* Recycle old space */
1185
size_t page_offset = (word)GC_mark_stack & (GC_page_size - 1);
1186
size_t size = GC_mark_stack_size * sizeof(struct GC_ms_entry);
1146
/* Recycle old space */
1147
if (0 != displ) displ = GC_page_size - displ;
1189
if (0 != page_offset) displ = GC_page_size - page_offset;
1148
1190
size = (size - displ) & ~(GC_page_size - 1);
1149
1191
if (size > 0) {
1150
1192
GC_add_to_heap((struct hblk *)
1151
1193
((word)GC_mark_stack + displ), (word)size);
1153
1196
GC_mark_stack = new_stack;
1154
1197
GC_mark_stack_size = n;
1155
1198
GC_mark_stack_limit = new_stack + n;
1157
if (GC_print_stats) {
1158
GC_printf1("Grew mark stack to %lu frames\n",
1159
(unsigned long) GC_mark_stack_size);
1199
if (GC_print_stats) {
1200
GC_log_printf("Grew mark stack to %lu frames\n",
1201
(unsigned long) GC_mark_stack_size);
1164
if (GC_print_stats) {
1165
GC_printf1("Failed to grow mark stack to %lu frames\n",
1204
if (GC_print_stats) {
1205
GC_log_printf("Failed to grow mark stack to %lu frames\n",
1171
1210
if (new_stack == 0) {
1172
GC_err_printf0("No space for mark stack\n");
1211
GC_err_printf("No space for mark stack\n");
1175
1214
GC_mark_stack = new_stack;
1223
1260
* or if it marks each object before pushing it, thus ensuring progress
1224
1261
* in the event of a stack overflow.)
1226
void GC_push_selected(bottom, top, dirty_fn, push_fn)
1229
int (*dirty_fn) GC_PROTO((struct hblk * h));
1230
void (*push_fn) GC_PROTO((ptr_t bottom, ptr_t top));
1263
void GC_push_selected(ptr_t bottom, ptr_t top,
1264
int (*dirty_fn) (struct hblk *),
1265
void (*push_fn) (ptr_t, ptr_t))
1232
register struct hblk * h;
1234
bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1235
top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
1269
bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1270
top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
1237
1272
if (top == 0 || bottom == top) return;
1238
1273
h = HBLKPTR(bottom + HBLKSIZE);
1305
1337
# if defined(MSWIN32) || defined(MSWINCE)
1306
void __cdecl GC_push_one(p)
1312
GC_PUSH_ONE_STACK(p, MARKED_FROM_REGISTER);
1315
struct GC_ms_entry *GC_mark_and_push(obj, mark_stack_ptr, mark_stack_limit, src)
1317
struct GC_ms_entry * mark_stack_ptr;
1318
struct GC_ms_entry * mark_stack_limit;
1322
PUSH_CONTENTS(obj, mark_stack_ptr /* modified */, mark_stack_limit, src,
1323
was_marked /* internally generated exit label */);
1324
return mark_stack_ptr;
1328
# define BASE(p) (word)GC_base((void *)(p))
1330
# define BASE(p) (word)GC_base((char *)(p))
1338
void __cdecl GC_push_one(word p)
1340
void GC_push_one(word p)
1343
GC_PUSH_ONE_STACK((ptr_t)p, MARKED_FROM_REGISTER);
1346
struct GC_ms_entry *GC_mark_and_push(void *obj,
1347
mse *mark_stack_ptr,
1348
mse *mark_stack_limit,
1355
if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr),FALSE)) {
1356
if (GC_all_interior_pointers) {
1357
hhdr = GC_find_header(GC_base(obj));
1359
GC_ADD_TO_BLACK_LIST_NORMAL(obj, src);
1360
return mark_stack_ptr;
1363
GC_ADD_TO_BLACK_LIST_NORMAL(obj, src);
1364
return mark_stack_ptr;
1367
if (EXPECT(HBLK_IS_FREE(hhdr),0)) {
1368
GC_ADD_TO_BLACK_LIST_NORMAL(obj, src);
1369
return mark_stack_ptr;
1372
PUSH_CONTENTS_HDR(obj, mark_stack_ptr /* modified */, mark_stack_limit,
1373
src, was_marked, hhdr, TRUE);
1375
return mark_stack_ptr;
1333
1378
/* Mark and push (i.e. gray) a single object p onto the main */
1334
1379
/* mark stack. Consider p to be valid if it is an interior */
1338
1383
/* Mark bits are NOT atomically updated. Thus this must be the */
1339
1384
/* only thread setting them. */
1340
1385
# if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
1341
void GC_mark_and_push_stack(p, source)
1386
void GC_mark_and_push_stack(ptr_t p, ptr_t source)
1344
void GC_mark_and_push_stack(p)
1388
void GC_mark_and_push_stack(ptr_t p)
1345
1389
# define source 0
1350
register hdr * hhdr;
1353
1396
GET_HDR(p, hhdr);
1354
if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
1397
if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr),FALSE)) {
1355
1398
if (hhdr != 0) {
1358
displ = BYTES_TO_WORDS(HBLKDISPL(r));
1361
register map_entry_type map_entry;
1363
displ = HBLKDISPL(p);
1364
map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
1365
if (map_entry >= MAX_OFFSET) {
1366
if (map_entry == OFFSET_TOO_BIG || !GC_all_interior_pointers) {
1368
displ = BYTES_TO_WORDS(HBLKDISPL(r));
1369
if (r == 0) hhdr = 0;
1371
/* Offset invalid, but map reflects interior pointers */
1375
displ = BYTES_TO_WORDS(displ);
1377
r = (word)((word *)(HBLKPTR(p)) + displ);
1380
/* If hhdr != 0 then r == GC_base(p), only we did it faster. */
1381
/* displ is the word index within the block. */
1383
# ifdef PRINT_BLACK_LIST
1384
GC_add_to_black_list_stack(p, source);
1386
GC_add_to_black_list_stack(p);
1388
# undef source /* In case we had to define it. */
1390
if (!mark_bit_from_hdr(hhdr, displ)) {
1391
set_mark_bit_from_hdr(hhdr, displ);
1392
GC_STORE_BACK_PTR(source, (ptr_t)r);
1393
PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
1394
GC_mark_stack_limit);
1403
GC_ADD_TO_BLACK_LIST_STACK(p, source);
1407
if (EXPECT(HBLK_IS_FREE(hhdr),0)) {
1408
GC_ADD_TO_BLACK_LIST_NORMAL(p, src);
1411
# if defined(MANUAL_VDB) && defined(THREADS)
1412
/* Pointer is on the stack. We may have dirtied the object */
1413
/* it points to, but not yet have called GC_dirty(); */
1414
GC_dirty(p); /* Implicitly affects entire object. */
1416
PUSH_CONTENTS_HDR(r, GC_mark_stack_top, GC_mark_stack_limit,
1417
source, mark_and_push_exit, hhdr, FALSE);
1418
mark_and_push_exit: ;
1419
/* We silently ignore pointers to near the end of a block, */
1420
/* which is very mildly suboptimal. */
1421
/* FIXME: We should probably add a header word to address */
1399
1425
# ifdef TRACE_BUF
1511
1537
#endif /* !THREADS */
1513
void GC_push_all_stack(bottom, top)
1539
void GC_push_all_stack(ptr_t bottom, ptr_t top)
1517
if (!NEED_FIXUP_POINTER && GC_all_interior_pointers) {
1518
GC_push_all(bottom, top);
1541
# if defined(THREADS) && defined(MPROTECT_VDB)
1520
1542
GC_push_all_eager(bottom, top);
1544
if (!NEED_FIXUP_POINTER && GC_all_interior_pointers) {
1545
GC_push_all(bottom, top);
1547
GC_push_all_eager(bottom, top);
1524
#if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
1552
#if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES) && \
1553
defined(MARK_BIT_PER_GRANULE)
1554
# if GC_GRANULE_WORDS == 1
1555
# define USE_PUSH_MARKED_ACCELERATORS
1556
# define PUSH_GRANULE(q) \
1557
{ ptr_t qcontents = (ptr_t)((q)[0]); \
1558
GC_PUSH_ONE_HEAP(qcontents, (q)); }
1559
# elif GC_GRANULE_WORDS == 2
1560
# define USE_PUSH_MARKED_ACCELERATORS
1561
# define PUSH_GRANULE(q) \
1562
{ ptr_t qcontents = (ptr_t)((q)[0]); \
1563
GC_PUSH_ONE_HEAP(qcontents, (q)); \
1564
qcontents = (ptr_t)((q)[1]); \
1565
GC_PUSH_ONE_HEAP(qcontents, (q)+1); }
1566
# elif GC_GRANULE_WORDS == 4
1567
# define USE_PUSH_MARKED_ACCELERATORS
1568
# define PUSH_GRANULE(q) \
1569
{ ptr_t qcontents = (ptr_t)((q)[0]); \
1570
GC_PUSH_ONE_HEAP(qcontents, (q)); \
1571
qcontents = (ptr_t)((q)[1]); \
1572
GC_PUSH_ONE_HEAP(qcontents, (q)+1); \
1573
qcontents = (ptr_t)((q)[2]); \
1574
GC_PUSH_ONE_HEAP(qcontents, (q)+2); \
1575
qcontents = (ptr_t)((q)[3]); \
1576
GC_PUSH_ONE_HEAP(qcontents, (q)+3); }
1580
#ifdef USE_PUSH_MARKED_ACCELERATORS
1525
1581
/* Push all objects reachable from marked objects in the given block */
1526
/* of size 1 objects. */
1527
void GC_push_marked1(h, hhdr)
1529
register hdr * hhdr;
1582
/* containing objects of size 1 granule. */
1583
void GC_push_marked1(struct hblk *h, hdr *hhdr)
1531
1585
word * mark_word_addr = &(hhdr->hb_marks[0]);
1536
register word mark_word;
1537
register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1538
register ptr_t least_ha = GC_least_plausible_heap_addr;
1539
register mse * mark_stack_top = GC_mark_stack_top;
1540
register mse * mark_stack_limit = GC_mark_stack_limit;
1591
/* Allow registers to be used for some frequently acccessed */
1592
/* global variables. Otherwise aliasing issues are likely */
1593
/* to prevent that. */
1594
ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1595
ptr_t least_ha = GC_least_plausible_heap_addr;
1596
mse * mark_stack_top = GC_mark_stack_top;
1597
mse * mark_stack_limit = GC_mark_stack_limit;
1541
1598
# define GC_mark_stack_top mark_stack_top
1542
1599
# define GC_mark_stack_limit mark_stack_limit
1543
1600
# define GC_greatest_plausible_heap_addr greatest_ha
1571
1629
#ifndef UNALIGNED
1573
1631
/* Push all objects reachable from marked objects in the given block */
1574
/* of size 2 objects. */
1575
void GC_push_marked2(h, hhdr)
1577
register hdr * hhdr;
1632
/* of size 2 (granules) objects. */
1633
void GC_push_marked2(struct hblk *h, hdr *hhdr)
1579
1635
word * mark_word_addr = &(hhdr->hb_marks[0]);
1584
register word mark_word;
1585
register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1586
register ptr_t least_ha = GC_least_plausible_heap_addr;
1587
register mse * mark_stack_top = GC_mark_stack_top;
1588
register mse * mark_stack_limit = GC_mark_stack_limit;
1641
ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1642
ptr_t least_ha = GC_least_plausible_heap_addr;
1643
mse * mark_stack_top = GC_mark_stack_top;
1644
mse * mark_stack_limit = GC_mark_stack_limit;
1589
1646
# define GC_mark_stack_top mark_stack_top
1590
1647
# define GC_mark_stack_limit mark_stack_limit
1591
1648
# define GC_greatest_plausible_heap_addr greatest_ha
1597
1654
/* go through all words in block */
1598
1655
while( p < plim ) {
1599
1656
mark_word = *mark_word_addr++;
1601
1658
while(mark_word != 0) {
1602
1659
if (mark_word & 1) {
1604
GC_PUSH_ONE_HEAP(q, p + i);
1606
GC_PUSH_ONE_HEAP(q, p + i);
1661
PUSH_GRANULE(q + GC_GRANULE_WORDS);
1663
q += 2 * GC_GRANULE_WORDS;
1609
1664
mark_word >>= 2;
1666
p += WORDSZ*GC_GRANULE_WORDS;
1613
1669
# undef GC_greatest_plausible_heap_addr
1614
1670
# undef GC_least_plausible_heap_addr
1615
1671
# undef GC_mark_stack_top
1616
1672
# undef GC_mark_stack_limit
1617
1674
GC_mark_stack_top = mark_stack_top;
1677
# if GC_GRANULE_WORDS < 4
1620
1678
/* Push all objects reachable from marked objects in the given block */
1621
/* of size 4 objects. */
1679
/* of size 4 (granules) objects. */
1622
1680
/* There is a risk of mark stack overflow here. But we handle that. */
1623
1681
/* And only unmarked objects get pushed, so it's not very likely. */
1624
void GC_push_marked4(h, hhdr)
1626
register hdr * hhdr;
1682
void GC_push_marked4(struct hblk *h, hdr *hhdr)
1628
1684
word * mark_word_addr = &(hhdr->hb_marks[0]);
1633
register word mark_word;
1634
register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1635
register ptr_t least_ha = GC_least_plausible_heap_addr;
1636
register mse * mark_stack_top = GC_mark_stack_top;
1637
register mse * mark_stack_limit = GC_mark_stack_limit;
1690
ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1691
ptr_t least_ha = GC_least_plausible_heap_addr;
1692
mse * mark_stack_top = GC_mark_stack_top;
1693
mse * mark_stack_limit = GC_mark_stack_limit;
1638
1694
# define GC_mark_stack_top mark_stack_top
1639
1695
# define GC_mark_stack_limit mark_stack_limit
1640
1696
# define GC_greatest_plausible_heap_addr greatest_ha
1646
1702
/* go through all words in block */
1647
1703
while( p < plim ) {
1648
1704
mark_word = *mark_word_addr++;
1650
1706
while(mark_word != 0) {
1651
1707
if (mark_word & 1) {
1653
GC_PUSH_ONE_HEAP(q, p + i);
1655
GC_PUSH_ONE_HEAP(q, p + i + 1);
1657
GC_PUSH_ONE_HEAP(q, p + i + 2);
1659
GC_PUSH_ONE_HEAP(q, p + i + 3);
1709
PUSH_GRANULE(q + GC_GRANULE_WORDS);
1710
PUSH_GRANULE(q + 2*GC_GRANULE_WORDS);
1711
PUSH_GRANULE(q + 3*GC_GRANULE_WORDS);
1713
q += 4 * GC_GRANULE_WORDS;
1662
1714
mark_word >>= 4;
1716
p += WORDSZ*GC_GRANULE_WORDS;
1666
1718
# undef GC_greatest_plausible_heap_addr
1667
1719
# undef GC_least_plausible_heap_addr
1670
1722
GC_mark_stack_top = mark_stack_top;
1725
#endif /* GC_GRANULE_WORDS < 4 */
1673
1727
#endif /* UNALIGNED */
1675
#endif /* SMALL_CONFIG */
1729
#endif /* USE_PUSH_MARKED_ACCELERATORS */
1677
1731
/* Push all objects reachable from marked objects in the given block */
1678
void GC_push_marked(h, hhdr)
1680
register hdr * hhdr;
1732
void GC_push_marked(struct hblk *h, hdr *hhdr)
1682
register int sz = hhdr -> hb_sz;
1683
register int descr = hhdr -> hb_descr;
1685
register int word_no;
1686
register word * lim;
1687
register mse * GC_mark_stack_top_reg;
1688
register mse * mark_stack_limit = GC_mark_stack_limit;
1734
size_t sz = hhdr -> hb_sz;
1735
word descr = hhdr -> hb_descr;
1739
mse * GC_mark_stack_top_reg;
1740
mse * mark_stack_limit = GC_mark_stack_limit;
1690
1742
/* Some quick shortcuts: */
1691
1743
if ((0 | GC_DS_LENGTH) == descr) return;
1692
1744
if (GC_block_empty(hhdr)/* nothing marked */) return;
1693
1745
GC_n_rescuing_pages++;
1694
1746
GC_objects_are_marked = TRUE;
1695
if (sz > MAXOBJSZ) {
1747
if (sz > MAXOBJBYTES) {
1698
lim = (word *)(h + 1) - sz;
1750
lim = (h + 1)->hb_body - sz;
1702
# if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
1753
switch(BYTES_TO_GRANULES(sz)) {
1754
# if defined(USE_PUSH_MARKED_ACCELERATORS)
1704
1756
GC_push_marked1(h, hhdr);
1707
# if !defined(SMALL_CONFIG) && !defined(UNALIGNED) && \
1708
!defined(USE_MARK_BYTES)
1710
GC_push_marked2(h, hhdr);
1713
GC_push_marked4(h, hhdr);
1758
# if !defined(UNALIGNED)
1760
GC_push_marked2(h, hhdr);
1762
# if GC_GRANULE_WORDS < 4
1764
GC_push_marked4(h, hhdr);
1717
1770
GC_mark_stack_top_reg = GC_mark_stack_top;
1718
for (p = (word *)h, word_no = 0; p <= lim; p += sz, word_no += sz) {
1719
if (mark_bit_from_hdr(hhdr, word_no)) {
1771
for (p = h -> hb_body, bit_no = 0; p <= lim;
1772
p += sz, bit_no += MARK_BIT_OFFSET(sz)) {
1773
if (mark_bit_from_hdr(hhdr, bit_no)) {
1720
1774
/* Mark from fields inside the object */
1721
PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
1723
/* Subtract this object from total, since it was */
1724
/* added in twice. */
1725
GC_composite_in_use -= sz;
1775
PUSH_OBJ(p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
1729
1778
GC_mark_stack_top = GC_mark_stack_top_reg;
1753
1799
#endif /* SMALL_CONFIG */
1755
/* Similar to GC_push_next_marked, but return address of next block */
1756
struct hblk * GC_push_next_marked(h)
1801
/* Similar to GC_push_marked, but skip over unallocated blocks */
1802
/* and return address of next plausible block. */
1803
struct hblk * GC_push_next_marked(struct hblk *h)
1759
register hdr * hhdr;
1805
hdr * hhdr = HDR(h);
1761
h = GC_next_used_block(h);
1762
if (h == 0) return(0);
1807
if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr), FALSE)) {
1808
h = GC_next_used_block(h);
1809
if (h == 0) return(0);
1810
hhdr = GC_find_header((ptr_t)h);
1764
1812
GC_push_marked(h, hhdr);
1765
1813
return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1768
1816
#ifndef SMALL_CONFIG
1769
1817
/* Identical to above, but mark only from dirty pages */
1770
struct hblk * GC_push_next_marked_dirty(h)
1818
struct hblk * GC_push_next_marked_dirty(struct hblk *h)
1773
register hdr * hhdr;
1820
hdr * hhdr = HDR(h);
1775
1822
if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
1777
h = GC_next_used_block(h);
1778
if (h == 0) return(0);
1824
if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr), FALSE)) {
1825
h = GC_next_used_block(h);
1826
if (h == 0) return(0);
1827
hhdr = GC_find_header((ptr_t)h);
1780
1829
# ifdef STUBBORN_ALLOC
1781
1830
if (hhdr -> hb_obj_kind == STUBBORN) {
1782
1831
if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
added
removed
mark.c
