1 ****************************************************************************
3 The files SMevac.lc and SMscav.lhc contain the basic routines required
4 for two-space copying garbage collection.
6 Two files are required as the evac routines are conventional call/return
7 routines while the scavenge routines are continuation routines.
9 This file SMscav.lhc contains the scavenging routines ...
11 ****************************************************************************
14 All the routines are placed in the info tables of the appropriate closures.
17 Evacuation code: _Evacuate_...
19 USE: new = EVACUATE_CLOSURE(evac)
21 Evacuates a closure of size S words. Note the size excludes the info
22 and any other preceding fields (eg global address in Grip implementation)
23 Returns the address of the closures new location via the Evac register.
26 arg -- points to the closure
27 ToHp -- points to the last allocated word in to-space
29 ret -- points to the new address of the closure
30 ToHp -- points to the last allocated word in to-space
32 Example: Cons cell requires _Evacuate_2
34 Scavenging code: _Scavenge_S_N
36 Retrieved using SCAV_CODE(infoptr)
38 Scavenges a closure of size S words, with N pointers and returns.
39 If more closures are required to be scavenged the code to
40 scan the next closure can be called.
43 Scav -- points to the current closure
44 ToHp -- points to the last allocated word in to-space
46 OldGen -- Points to end of old generation (Appels collector only)
49 Scav -- points to the next closure
50 ToHp -- points to the (possibly new) location of the last allocated word
52 Example: Cons cell requires _Scavenge_2_2
55 The following registers are used by a two-space collection:
57 Scav -- Points to the current closure being scavenged
60 ToHp -- Points to the last word allocated in two-space
63 A copying pass is started by:
64 -- Setting ToHp to 1 before the start of to-space
65 -- Evacuating the roots pointing into from-space
66 -- root = EVACUATE_CLOSURE(root)
67 -- Setting Scav to point to the first closure in to-space
68 -- Execute while (Scav <= ToHp) (SCAV_CODE(INFO_PTR(Scav)))();
70 When Done ToHp will point to the last word allocated in to-space
74 /* The #define and #include come before the test because SMinternal.h
75 will suck in includes/SMinterface whcih defines (or doesn't)
76 _INFO_COPYING [ADR] */
79 #include "SMinternal.h"
81 #if defined(_INFO_COPYING)
83 RegisterTable ScavRegTable;
85 /* Moves Scav to point at the info pointer of the next closure to Scavenge */
86 #define NEXT_Scav(size) Scav += (size) + FIXED_HS
89 When doing a new generation copy collection for Appel's collector
90 only evacuate references that point to the new generation.
91 OldGen must be set to point to the end of old space.
96 #define DO_EVACUATE(closure, pos) \
97 { P_ evac = (P_) *(((P_)(closure))+(pos)); \
98 if (evac > OldGen) { \
99 *(((P_)(closure))+(pos)) = (W_) EVACUATE_CLOSURE(evac); \
105 #define DO_EVACUATE(closure, pos) \
106 { P_ evac = (P_) *(((P_)(closure))+(pos)); \
107 if (evac > OldGen) { \
108 *(((P_)(closure))+(pos)) = (W_) EVACUATE_CLOSURE(evac); \
111 #else /* ! GCgn && ! GCap */
113 #define DO_EVACUATE(closure, pos) \
114 { P_ evac = (P_) *(((P_)(closure))+(pos)); \
115 *(((P_)(closure))+(pos)) = (W_) EVACUATE_CLOSURE(evac); }
117 #endif /* ! GCgn && ! GCap */
121 /* Evacuate nth pointer in SPEC closure (starting at 1) */
122 #define SPEC_DO_EVACUATE(ptr) DO_EVACUATE(Scav, (SPEC_HS-1) + (ptr))
123 #define STKO_DO_EVACUATE(ptr) DO_EVACUATE(Scav, (STKO_HS-1) + (ptr))
126 /*** DEBUGGING MACROS ***/
128 #if defined(_GC_DEBUG)
130 #define DEBUG_SCAV(s,p) \
132 fprintf(stderr, "Scav: 0x%lx, info 0x%lx, size %ld, ptrs %ld\n", \
133 Scav, INFO_PTR(Scav), s, p)
135 #define DEBUG_SCAV_GEN(s,p) \
137 fprintf(stderr, "Scav: 0x%lx, Gen info 0x%lx, size %ld, ptrs %ld\n", \
138 Scav, INFO_PTR(Scav), s, p)
140 #define DEBUG_SCAV_DYN \
142 fprintf(stderr, "Scav: 0x%lx, Dyn info 0x%lx, size %ld, ptrs %ld\n", \
143 Scav, INFO_PTR(Scav), DYN_CLOSURE_SIZE(Scav), DYN_CLOSURE_NoPTRS(Scav))
145 #define DEBUG_SCAV_TUPLE \
147 fprintf(stderr, "Scav: 0x%lx, Tuple info 0x%lx, size %ld, ptrs %ld\n", \
148 Scav, INFO_PTR(Scav), TUPLE_CLOSURE_SIZE(Scav), TUPLE_CLOSURE_NoPTRS(Scav))
150 #define DEBUG_SCAV_MUTUPLE \
152 fprintf(stderr, "Scav: 0x%lx, MuTuple info 0x%lx, size %ld, ptrs %ld\n", \
153 Scav, INFO_PTR(Scav), MUTUPLE_CLOSURE_SIZE(Scav), MUTUPLE_CLOSURE_NoPTRS(Scav))
155 #define DEBUG_SCAV_DATA \
157 fprintf(stderr, "Scav: 0x%lx, Data info 0x%lx, size %ld\n", \
158 Scav, INFO_PTR(Scav), DATA_CLOSURE_SIZE(Scav))
160 #define DEBUG_SCAV_BH(s) \
162 fprintf(stderr, "Scav: 0x%lx, BH info 0x%lx, size %ld\n", \
163 Scav, INFO_PTR(Scav), s)
165 #define DEBUG_SCAV_IND \
167 fprintf(stderr, "Scav: 0x%lx, IND info 0x%lx, size %ld\n", \
168 Scav, INFO_PTR(Scav), IND_CLOSURE_SIZE(Scav))
170 #define DEBUG_SCAV_PERM_IND \
172 fprintf(stderr, "Scav: 0x%lx, PI info 0x%lx, size %ld\n", \
173 Scav, INFO_PTR(Scav), IND_CLOSURE_SIZE(Scav))
175 #define DEBUG_SCAV_OLDROOT(s) \
177 fprintf(stderr, "Scav: OLDROOT 0x%lx, info 0x%lx, size %ld\n", \
178 Scav, INFO_PTR(Scav), s)
181 #define DEBUG_SCAV_BQ \
183 fprintf(stderr, "Scav: 0x%lx, BQ info 0x%lx, size %ld, ptrs %ld\n", \
184 Scav, INFO_PTR(Scav), BQ_CLOSURE_SIZE(Scav), BQ_CLOSURE_NoPTRS(Scav))
186 #define DEBUG_SCAV_TSO \
188 fprintf(stderr, "Scav TSO: 0x%lx\n", \
191 #define DEBUG_SCAV_STKO \
193 fprintf(stderr, "Scav StkO: 0x%lx\n", \
197 # define DEBUG_SCAV_BF \
199 fprintf(stderr, "Scav: 0x%lx, BF info 0x%lx, size %ld, ptrs %ld\n", \
200 Scav, INFO_PTR(Scav), BF_CLOSURE_SIZE(dummy), 0)
206 #define DEBUG_SCAV(s,p)
207 #define DEBUG_SCAV_GEN(s,p)
208 #define DEBUG_SCAV_DYN
209 #define DEBUG_SCAV_TUPLE
210 #define DEBUG_SCAV_MUTUPLE
211 #define DEBUG_SCAV_DATA
212 #define DEBUG_SCAV_BH(s)
213 #define DEBUG_SCAV_IND
214 #define DEBUG_SCAV_PERM_IND
215 #define DEBUG_SCAV_OLDROOT(s)
218 # define DEBUG_SCAV_BQ
219 # define DEBUG_SCAV_TSO
220 # define DEBUG_SCAV_STKO
222 # define DEBUG_SCAV_BF
228 #define PROFILE_CLOSURE(closure,size) \
229 HEAP_PROFILE_CLOSURE(closure,size); \
230 LIFE_PROFILE_CLOSURE(closure,size)
232 /*** SPECIALISED CODE ***/
235 _Scavenge_1_0(STG_NO_ARGS)
238 PROFILE_CLOSURE(Scav,1);
239 NEXT_Scav(1); /* because "size" is defined to be 1 (size SPEC_VHS == 0) */
243 _Scavenge_2_0(STG_NO_ARGS)
246 PROFILE_CLOSURE(Scav,2);
251 _Scavenge_3_0(STG_NO_ARGS)
254 PROFILE_CLOSURE(Scav,3);
259 _Scavenge_4_0(STG_NO_ARGS)
262 PROFILE_CLOSURE(Scav,4);
267 _Scavenge_5_0(STG_NO_ARGS)
270 PROFILE_CLOSURE(Scav,5);
276 _Scavenge_2_1(STG_NO_ARGS)
279 PROFILE_CLOSURE(Scav,2);
286 _Scavenge_3_1(STG_NO_ARGS)
289 PROFILE_CLOSURE(Scav,3);
295 _Scavenge_3_2(STG_NO_ARGS)
298 PROFILE_CLOSURE(Scav,3);
306 _Scavenge_1_1(STG_NO_ARGS)
309 PROFILE_CLOSURE(Scav,1);
315 _Scavenge_2_2(STG_NO_ARGS)
318 PROFILE_CLOSURE(Scav,2);
325 _Scavenge_3_3(STG_NO_ARGS)
328 PROFILE_CLOSURE(Scav,3);
336 _Scavenge_4_4(STG_NO_ARGS)
339 PROFILE_CLOSURE(Scav,4);
348 _Scavenge_5_5(STG_NO_ARGS)
351 PROFILE_CLOSURE(Scav,5);
361 _Scavenge_6_6(STG_NO_ARGS)
364 PROFILE_CLOSURE(Scav,6);
375 _Scavenge_7_7(STG_NO_ARGS)
378 PROFILE_CLOSURE(Scav,7);
390 _Scavenge_8_8(STG_NO_ARGS)
393 PROFILE_CLOSURE(Scav,8);
406 _Scavenge_9_9(STG_NO_ARGS)
409 PROFILE_CLOSURE(Scav,9);
423 _Scavenge_10_10(STG_NO_ARGS)
426 PROFILE_CLOSURE(Scav,10);
436 SPEC_DO_EVACUATE(10);
441 _Scavenge_11_11(STG_NO_ARGS)
444 PROFILE_CLOSURE(Scav,11);
454 SPEC_DO_EVACUATE(10);
455 SPEC_DO_EVACUATE(11);
460 _Scavenge_12_12(STG_NO_ARGS)
463 PROFILE_CLOSURE(Scav,12);
473 SPEC_DO_EVACUATE(10);
474 SPEC_DO_EVACUATE(11);
475 SPEC_DO_EVACUATE(12);
481 The scavenge routines for revertible black holes with underlying @SPEC@
490 # define SCAVENGE_SPEC_RBH_N_1(n) \
492 CAT3(_Scavenge_RBH_,n,_1)(STG_NO_ARGS) \
498 DO_EVACUATE(save_Scav, SPEC_RBH_BQ_LOCN); \
500 PROFILE_CLOSURE(Scav,n); \
501 NEXT_Scav(n); /* ToDo: dodgy size WDP 95/07 */ \
504 # define SCAVENGE_SPEC_RBH_N_N(n) \
506 CAT4(_Scavenge_RBH_,n,_,n)(STG_NO_ARGS) \
513 for(i = 0; i < n - 1; i++) { \
514 DO_EVACUATE(save_Scav, SPEC_RBH_BQ_LOCN + i); \
517 PROFILE_CLOSURE(Scav,n); \
523 # define SCAVENGE_SPEC_RBH_N_1(n) \
525 CAT3(_Scavenge_RBH_,n,_1)(STG_NO_ARGS) \
528 DO_EVACUATE(Scav, SPEC_RBH_BQ_LOCN);\
529 PROFILE_CLOSURE(Scav,n); \
533 # define SCAVENGE_SPEC_RBH_N_N(n) \
535 CAT4(_Scavenge_RBH_,n,_,n)(STG_NO_ARGS) \
539 for(i = 0; i < n - 1; i++) { \
540 DO_EVACUATE(Scav, SPEC_RBH_BQ_LOCN + i); \
542 PROFILE_CLOSURE(Scav,n); \
548 SCAVENGE_SPEC_RBH_N_1(2)
550 SCAVENGE_SPEC_RBH_N_1(3)
551 SCAVENGE_SPEC_RBH_N_N(3)
553 SCAVENGE_SPEC_RBH_N_1(4)
554 SCAVENGE_SPEC_RBH_N_N(4)
556 SCAVENGE_SPEC_RBH_N_1(5)
557 SCAVENGE_SPEC_RBH_N_N(5)
559 SCAVENGE_SPEC_RBH_N_N(6)
560 SCAVENGE_SPEC_RBH_N_N(7)
561 SCAVENGE_SPEC_RBH_N_N(8)
562 SCAVENGE_SPEC_RBH_N_N(9)
563 SCAVENGE_SPEC_RBH_N_N(10)
564 SCAVENGE_SPEC_RBH_N_N(11)
565 SCAVENGE_SPEC_RBH_N_N(12)
574 /*** Malloc POINTER -- NOTHING TO SCAVENGE ***/
576 /* (The MallocPtrList is updated at the end of GC and any unevacuated
577 MallocPtrs reported to C World) [ADR]
581 _Scavenge_MallocPtr(STG_NO_ARGS)
583 DEBUG_SCAV(MallocPtr_SIZE,0);
584 PROFILE_CLOSURE(Scav,MallocPtr_SIZE);
585 NEXT_Scav(MallocPtr_SIZE);
590 /*** GENERAL CASE CODE ***/
593 _Scavenge_S_N(STG_NO_ARGS)
595 I_ count = GEN_HS - 1;
596 /* Offset of first ptr word, less 1 */
597 I_ ptrs = count + GEN_CLOSURE_NoPTRS(Scav);
598 /* Offset of last ptr word */
599 I_ size = GEN_CLOSURE_SIZE(Scav);
601 DEBUG_SCAV_GEN(size, GEN_CLOSURE_NoPTRS(Scav));
603 while (++count <= ptrs) {
604 DO_EVACUATE(Scav, count);
606 PROFILE_CLOSURE(Scav,size);
613 The scavenge code for revertible black holes with underlying @GEN@ closures
620 _Scavenge_RBH_N(STG_NO_ARGS)
626 I_ count = GEN_RBH_HS - 1; /* Offset of first ptr word, less 1 */
627 I_ ptrs = GEN_RBH_CLOSURE_NoPTRS(Scav);
628 I_ size = GEN_RBH_CLOSURE_SIZE(Scav);
631 * Get pointer count from original closure and adjust for one pointer
632 * in the first two words of the RBH.
639 ptrs += count; /* Offset of last ptr word */
641 DEBUG_SCAV_GEN(size, ptrs);
644 /* No old generation roots should be created for mutable */
645 /* pointer fields as they will be explicitly collected */
646 /* Ensure this by pointing Scav at the new generation */
650 while (++count <= ptrs) {
651 DO_EVACUATE(save_Scav, count);
655 while (++count <= ptrs) {
656 DO_EVACUATE(Scav, count);
660 PROFILE_CLOSURE(Scav,size);
671 /*** DYNAMIC CLOSURE -- SIZE & PTRS STORED IN CLOSURE ***/
674 _Scavenge_Dyn(STG_NO_ARGS)
676 I_ count = DYN_HS - 1;
677 /* Offset of first ptr word, less 1 */
678 I_ ptrs = count + DYN_CLOSURE_NoPTRS(Scav);
679 /* Offset of last ptr word */
680 I_ size = DYN_CLOSURE_SIZE(Scav);
683 while (++count <= ptrs) {
684 DO_EVACUATE(Scav, count);
686 PROFILE_CLOSURE(Scav,size);
691 /*** TUPLE CLOSURE -- NO PTRS STORED IN CLOSURE -- NO DATA ***/
694 _Scavenge_Tuple(STG_NO_ARGS)
696 I_ count = TUPLE_HS - 1;
697 /* Offset of first ptr word, less 1 */
698 I_ ptrs = count + TUPLE_CLOSURE_NoPTRS(Scav);
699 /* Offset of last ptr word */
700 I_ size = TUPLE_CLOSURE_SIZE(Scav);
703 while (++count <= ptrs) {
704 DO_EVACUATE(Scav, count);
706 PROFILE_CLOSURE(Scav,size);
711 /*** DATA CLOSURE -- SIZE STORED IN CLOSURE -- NO POINTERS ***/
714 _Scavenge_Data(STG_NO_ARGS)
716 I_ size = DATA_CLOSURE_SIZE(Scav);
719 PROFILE_CLOSURE(Scav,size);
724 /*** MUTUPLE CLOSURE -- ONLY PTRS STORED IN CLOSURE -- NO DATA ***/
725 /* Only if special GC treatment required */
727 #ifdef GC_MUT_REQUIRED
729 _Scavenge_MuTuple(STG_NO_ARGS)
734 I_ count = MUTUPLE_HS - 1;
735 /* Offset of first ptr word, less 1 */
736 I_ ptrs = count + MUTUPLE_CLOSURE_NoPTRS(Scav);
737 /* Offset of last ptr word */
738 I_ size = MUTUPLE_CLOSURE_SIZE(Scav);
743 /* No old generation roots should be created for mutable */
744 /* pointer fields as they will be explicitly collected */
745 /* Ensure this by pointing Scav at the new generation */
748 while (++count <= ptrs) {
749 DO_EVACUATE(save_Scav, count);
753 while (++count <= ptrs) {
754 DO_EVACUATE(Scav, count);
758 PROFILE_CLOSURE(Scav,size);
762 #endif /* something generational */
764 /*** BH CLOSURES -- NO POINTERS ***/
767 _Scavenge_BH_U(STG_NO_ARGS)
769 DEBUG_SCAV_BH(BH_U_SIZE);
770 PROFILE_CLOSURE(Scav,BH_U_SIZE);
771 NEXT_Scav(BH_U_SIZE);
776 _Scavenge_BH_N(STG_NO_ARGS)
778 DEBUG_SCAV_BH(BH_N_SIZE);
779 PROFILE_CLOSURE(Scav,BH_N_SIZE);
780 NEXT_Scav(BH_N_SIZE);
784 /* This is needed for scavenging the indirections on the OldMutables list */
787 _Scavenge_Ind(STG_NO_ARGS)
790 PROFILE_CLOSURE(Scav,IND_CLOSURE_SIZE(dummy));
791 DO_EVACUATE(Scav, IND_HS);
792 NEXT_Scav(IND_CLOSURE_SIZE(dummy));
797 _Scavenge_Caf(STG_NO_ARGS)
800 PROFILE_CLOSURE(Scav,IND_CLOSURE_SIZE(dummy));
801 DO_EVACUATE(Scav, IND_HS);
802 NEXT_Scav(IND_CLOSURE_SIZE(dummy));
806 #if defined(USE_COST_CENTRES)
808 /* Special permanent indirection for lexical scoping.
809 As for _Scavenge_Ind but no PROFILE_CLOSURE.
813 _Scavenge_PI(STG_NO_ARGS)
816 /* PROFILE_CLOSURE(Scav,IND_CLOSURE_SIZE(dummy)); */
817 DO_EVACUATE(Scav, IND_HS);
818 NEXT_Scav(IND_CLOSURE_SIZE(dummy));
821 #endif /* USE_COST_CENTRES */
826 _Scavenge_BQ(STG_NO_ARGS)
835 /* No old generation roots should be created for mutable */
836 /* pointer fields as they will be explicitly collected */
837 /* Ensure this by pointing Scav at the new generation */
840 DO_EVACUATE(save_Scav, BQ_HS);
843 DO_EVACUATE(Scav, BQ_HS);
846 PROFILE_CLOSURE(Scav,BQ_CLOSURE_SIZE(dummy));
847 NEXT_Scav(BQ_CLOSURE_SIZE(dummy));
852 _Scavenge_TSO(STG_NO_ARGS)
857 STGRegisterTable *r = TSO_INTERNAL_PTR(Scav);
858 W_ liveness = r->rLiveness;
864 /* No old generation roots should be created for mutable */
865 /* pointer fields as they will be explicitly collected */
866 /* Ensure this by pointing Scav at the new generation */
870 DO_EVACUATE(save_Scav, TSO_LINK_LOCN);
871 DO_EVACUATE(save_Scav, ((P_) &r->rStkO) - save_Scav);
872 for(i = 0; liveness != 0; liveness >>= 1, i++) {
874 DO_EVACUATE(save_Scav, ((P_) &r->rR[i].p) - save_Scav)
879 DO_EVACUATE(Scav, TSO_LINK_LOCN);
880 DO_EVACUATE(Scav, ((P_) &r->rStkO) - Scav);
881 for(i = 0; liveness != 0; liveness >>= 1, i++) {
883 DO_EVACUATE(Scav, ((P_) &r->rR[i].p) - Scav)
888 PROFILE_CLOSURE(Scav, TSO_VHS + TSO_CTS_SIZE)
889 NEXT_Scav(TSO_VHS + TSO_CTS_SIZE);
894 _Scavenge_StkO(STG_NO_ARGS)
900 I_ sub = STKO_SuB_OFFSET(Scav); /* Offset of first update frame in B stack */
905 /* No old generation roots should be created for mutable */
906 /* pointer fields as they will be explicitly collected */
907 /* Ensure this by pointing Scav at the new generation */
911 /* Evacuate the link */
912 DO_EVACUATE(save_Scav, STKO_LINK_LOCN);
914 /* Evacuate the locations in the A stack */
915 for (count = STKO_SpA_OFFSET(save_Scav);
916 count <= STKO_CLOSURE_CTS_SIZE(save_Scav); count++) {
917 STKO_DO_EVACUATE(count);
920 /* Now evacuate the updatees in the update stack */
924 STKO_DO_EVACUATE(sub + BREL(UF_UPDATEE));
925 subptr = GRAB_SuB(STKO_CLOSURE_ADDR(save_Scav,sub));
926 sub = STKO_CLOSURE_OFFSET(save_Scav, subptr);
930 /* Evacuate the link */
931 DO_EVACUATE(Scav, STKO_LINK_LOCN);
933 /* Evacuate the locations in the A stack */
934 for (count = STKO_SpA_OFFSET(Scav); count <= STKO_CLOSURE_CTS_SIZE(Scav); count++) {
935 STKO_DO_EVACUATE(count);
938 /* Now evacuate the updatees in the update stack */
942 STKO_DO_EVACUATE(sub + BREL(UF_UPDATEE));
943 subptr = GRAB_SuB(STKO_CLOSURE_ADDR(Scav,sub));
944 sub = STKO_CLOSURE_OFFSET(Scav, subptr);
947 PROFILE_CLOSURE(Scav, STKO_CLOSURE_SIZE(Scav))
948 NEXT_Scav(STKO_CLOSURE_SIZE(Scav));
955 _Scavenge_FetchMe(STG_NO_ARGS)
958 PROFILE_CLOSURE(Scav,2);
964 _Scavenge_BF(STG_NO_ARGS)
973 /* No old generation roots should be created for mutable */
974 /* pointer fields as they will be explicitly collected */
975 /* Ensure this by pointing Scav at the new generation */
979 DO_EVACUATE(save_Scav, BF_LINK_LOCN);
980 DO_EVACUATE(save_Scav, BF_NODE_LOCN);
983 DO_EVACUATE(Scav, BF_LINK_LOCN);
984 DO_EVACUATE(Scav, BF_NODE_LOCN);
987 PROFILE_CLOSURE(Scav, BF_CLOSURE_SIZE(dummy))
988 NEXT_Scav(BF_CLOSURE_SIZE(dummy));
993 #endif /* CONCURRENT */
997 /* Recently allocated old roots for promoted objects refernecing
998 the new generation will be scavenged -- Just move to the next
1002 _Scavenge_OldRoot(STG_NO_ARGS)
1004 DEBUG_SCAV_OLDROOT(MIN_UPD_SIZE); /* dodgy size (WDP 95/07) */
1005 NEXT_Scav(MIN_UPD_SIZE);
1010 _Evacuate_OldRoot(evac)
1013 fprintf(stderr,"Called _Evacuate_OldRoot: Closure %lx Info %lx\nShould never occur!\n",
1014 (W_) evac, (W_) INFO_PTR(evac));
1021 _Scavenge_Forward_Ref(STG_NO_ARGS)
1023 fprintf(stderr,"Called _Scavenge_Forward_Ref: Closure %lx Info %lx\nShould never occur!\n",
1024 (W_) Scav, (W_) INFO_PTR(Scav));
1029 #endif /* _INFO_COPYING */