1 ***************************************************************************
3 COMPACTING GARBAGE COLLECTION
5 Global heap requirements as for 1s and 2s collectors.
7 ***************************************************************************
9 ToDo: soft heap limits.
16 #include "SMinternal.h"
17 #include "SMcopying.h"
18 #include "SMcompacting.h"
23 dualmodeData dualmodeInfo = {TWO_SPACE_BOT,
24 DEFAULT_RESID_TO_COMPACT,
25 DEFAULT_RESID_FROM_COMPACT,
28 {0,0,0,"compacting"}},
32 P_ heap_space = 0; /* Address of first word of slab
33 of memory allocated for heap */
35 P_ hp_start; /* Value of Hp when reduction was resumed */
40 if (heap_space == 0) { /* allocates if it doesn't already exist */
42 I_ semispaceSize = RTSflags.GcFlags.heapSize / 2;
44 /* Allocate the roots space */
45 sm->roots = (P_ *) stgMallocWords(SM_MAXROOTS, "initHeap (roots)");
47 /* Allocate the heap */
48 heap_space = (P_) stgMallocWords(RTSflags.GcFlags.heapSize + EXTRA_HEAP_WORDS,
51 dualmodeInfo.modeinfo[TWO_SPACE_BOT].heap_words =
52 dualmodeInfo.modeinfo[TWO_SPACE_TOP].heap_words = RTSflags.GcFlags.heapSize;
54 dualmodeInfo.modeinfo[TWO_SPACE_BOT].base =
55 HEAP_FRAME_BASE(heap_space, semispaceSize);
56 dualmodeInfo.modeinfo[TWO_SPACE_BOT].lim =
57 HEAP_FRAME_LIMIT(heap_space, semispaceSize);
58 dualmodeInfo.modeinfo[TWO_SPACE_TOP].base =
59 HEAP_FRAME_BASE(heap_space + semispaceSize, semispaceSize);
60 dualmodeInfo.modeinfo[TWO_SPACE_TOP].lim =
61 HEAP_FRAME_LIMIT(heap_space + semispaceSize, semispaceSize);
63 dualmodeInfo.bit_words = (RTSflags.GcFlags.heapSize + BITS_IN(BitWord) - 1) / BITS_IN(BitWord);
64 dualmodeInfo.bits = (BitWord *)(heap_space + RTSflags.GcFlags.heapSize) - dualmodeInfo.bit_words;
66 dualmodeInfo.modeinfo[COMPACTING].heap_words =
67 RTSflags.GcFlags.heapSize - dualmodeInfo.bit_words;
68 dualmodeInfo.modeinfo[COMPACTING].base =
69 HEAP_FRAME_BASE(heap_space, RTSflags.GcFlags.heapSize - dualmodeInfo.bit_words);
70 dualmodeInfo.modeinfo[COMPACTING].lim =
71 HEAP_FRAME_LIMIT(heap_space, RTSflags.GcFlags.heapSize - dualmodeInfo.bit_words);
73 stat_init("DUALMODE", "Collection", " Mode ");
76 sm->hp = hp_start = dualmodeInfo.modeinfo[dualmodeInfo.mode].base - 1;
79 sm->hplim = sm->hp + SM_alloc_size;
81 RTSflags.GcFlags.minAllocAreaSize = 0; /* specified size takes precedence */
83 if (sm->hplim > dualmodeInfo.modeinfo[dualmodeInfo.mode].lim) {
84 fprintf(stderr, "Not enough heap for requested alloc size\n");
88 sm->hplim = dualmodeInfo.modeinfo[dualmodeInfo.mode].lim;
97 if (RTSflags.GcFlags.trace) {
98 fprintf(stderr, "DUALMODE Heap: TS base, TS lim, TS base, TS lim, CM base, CM lim, CM bits, bit words\n 0x%lx, 0x%lx, 0x%lx, 0x%lx, 0x%lx, 0x%lx, 0x%lx, 0x%lx\n",
99 (W_) dualmodeInfo.modeinfo[TWO_SPACE_BOT].base,
100 (W_) dualmodeInfo.modeinfo[TWO_SPACE_BOT].lim,
101 (W_) dualmodeInfo.modeinfo[TWO_SPACE_TOP].base,
102 (W_) dualmodeInfo.modeinfo[TWO_SPACE_TOP].lim,
103 (W_) dualmodeInfo.modeinfo[COMPACTING].base,
104 (W_) dualmodeInfo.modeinfo[COMPACTING].lim,
105 (W_) dualmodeInfo.bits, dualmodeInfo.bit_words);
106 fprintf(stderr, "DUALMODE Initial: mode %ld, base 0x%lx, lim 0x%lx\n hp 0x%lx, hplim 0x%lx, free %lu\n",
107 (W_) dualmodeInfo.mode,
108 (W_) dualmodeInfo.modeinfo[dualmodeInfo.mode].base,
109 (W_) dualmodeInfo.modeinfo[dualmodeInfo.mode].lim,
110 (W_) sm->hp, (W_) sm->hplim, (W_) (sm->hplim - sm->hp) * sizeof(W_));
113 return rtsTrue; /* OK */
117 collectHeap(reqsize, sm, do_full_collection)
120 rtsBool do_full_collection;
124 I_ free_space, /* No of words of free space following GC */
125 alloc, /* Number of words allocated since last GC */
126 resident, /* Number of words remaining after GC */
127 bstk_roots; /* Number of update frames on B stack */
128 StgFloat residency; /* % Words remaining after GC */
130 fflush(stdout); /* Flush stdout at start of GC */
131 SAVE_REGS(&ScavRegDump); /* Save registers */
133 if (RTSflags.GcFlags.trace)
134 fprintf(stderr, "DUALMODE Start: mode %ld, base 0x%lx, lim 0x%lx\n hp 0x%lx, hplim 0x%lx, req %lu\n",
136 (W_) dualmodeInfo.modeinfo[dualmodeInfo.mode].base,
137 (W_) dualmodeInfo.modeinfo[dualmodeInfo.mode].lim,
138 (W_) sm->hp, (W_) sm->hplim, (W_) (reqsize * sizeof(W_)));
140 alloc = sm->hp - hp_start;
143 start_mode = dualmodeInfo.mode;
144 if (start_mode == COMPACTING) {
146 /* PERFORM COMPACTING COLLECTION */
148 /* bracket use of MARK_REG_MAP with RESTORE/SAVE of SCAV_REG_MAP */
149 RESTORE_REGS(&ScavRegDump);
151 markHeapRoots(sm, sm->CAFlist, 0,
152 dualmodeInfo.modeinfo[COMPACTING].base,
153 dualmodeInfo.modeinfo[COMPACTING].lim,
156 SAVE_REGS(&ScavRegDump);
160 sweepUpDeadMallocPtrs(sm->MallocPtrList,
161 dualmodeInfo.modeinfo[COMPACTING].base,
164 LinkCAFs(sm->CAFlist);
166 LinkRoots( sm->roots, sm->rootno );
171 LinkLiveGAs(dualmodeInfo.modeinfo[COMPACTING].base, dualmodeInfo.bits);
173 DEBUG_STRING("Linking Stable Pointer Table:");
174 LINK_LOCATION_TO_CLOSURE(&sm->StablePointerTable);
175 LinkAStack( MAIN_SpA, stackInfo.botA );
176 LinkBStack( MAIN_SuB, stackInfo.botB );
179 /* Do Inplace Compaction */
180 /* Returns start of next closure, -1 gives last allocated word */
182 sm->hp = Inplace_Compaction(dualmodeInfo.modeinfo[COMPACTING].base,
183 dualmodeInfo.modeinfo[COMPACTING].lim,
186 dualmodeInfo.bit_words
188 ,&(sm->MallocPtrList)
194 /* COPYING COLLECTION */
196 dualmodeInfo.mode = NEXT_SEMI_SPACE(start_mode);
197 ToHp = dualmodeInfo.modeinfo[dualmodeInfo.mode].base - 1;
198 Scav = dualmodeInfo.modeinfo[dualmodeInfo.mode].base;
199 /* Point to (info field of) first closure */
201 SetCAFInfoTables( sm->CAFlist );
202 EvacuateCAFs( sm->CAFlist );
204 EvacuateLocalGAs(rtsTrue);
208 EvacuateRoots( sm->roots, sm->rootno );
213 EvacuateAStack( MAIN_SpA, stackInfo.botA );
214 EvacuateBStack( MAIN_SuB, stackInfo.botB, &bstk_roots );
220 RebuildGAtables(rtsTrue);
222 reportDeadMallocPtrs(sm->MallocPtrList, NULL, &(sm->MallocPtrList) );
225 sm->hp = hp_start = ToHp; /* Last allocated word */
228 /* Use residency to determine if a change in mode is required */
230 resident = sm->hp - (dualmodeInfo.modeinfo[dualmodeInfo.mode].base - 1);
231 residency = resident / (StgFloat) RTSflags.GcFlags.heapSize;
232 DO_MAX_RESIDENCY(resident); /* stats only */
234 if ((start_mode == TWO_SPACE_TOP) &&
235 (residency > dualmodeInfo.resid_to_compact)) {
236 DEBUG_STRING("Changed Mode: Two Space => Compacting");
237 dualmodeInfo.mode = COMPACTING;
239 /* Zero bit vector for marking phase at next collection */
240 { BitWord *ptr = dualmodeInfo.bits,
241 *end = dualmodeInfo.bits + dualmodeInfo.bit_words;
242 while (ptr < end) { *(ptr++) = 0; };
245 } else if ((start_mode == COMPACTING) &&
246 (residency < dualmodeInfo.resid_from_compact)) {
247 DEBUG_STRING("Changed Mode: Compacting => Two Space");
248 dualmodeInfo.mode = TWO_SPACE_BOT;
252 sm->hplim = sm->hp + SM_alloc_size;
253 if (sm->hplim > dualmodeInfo.modeinfo[dualmodeInfo.mode].lim) {
256 free_space = SM_alloc_size;
259 sm->hplim = dualmodeInfo.modeinfo[dualmodeInfo.mode].lim;
260 free_space = sm->hplim - sm->hp;
265 stat_endGC(alloc, dualmodeInfo.modeinfo[start_mode].heap_words,
266 resident, dualmodeInfo.modeinfo[start_mode].name);
268 if (RTSflags.GcFlags.trace)
269 fprintf(stderr, "DUALMODE Done: mode %ld, base 0x%lx, lim 0x%lx\n hp 0x%lx, hplim 0x%lx, free %lu\n",
271 (W_) dualmodeInfo.modeinfo[dualmodeInfo.mode].base,
272 (W_) dualmodeInfo.modeinfo[dualmodeInfo.mode].lim,
273 (W_) sm->hp, (W_) sm->hplim, (W_) ((sm->hplim - sm->hp) * sizeof(W_)));
276 /* To help flush out bugs, we trash the part of the heap from
277 which we're about to start allocating. */
278 TrashMem(sm->hp+1, sm->hplim);
281 RESTORE_REGS(&ScavRegDump); /* Restore Registers */
283 if (free_space < RTSflags.GcFlags.minAllocAreaSize || free_space < reqsize)
284 return GC_HARD_LIMIT_EXCEEDED; /* Heap exhausted */
286 return GC_SUCCESS; /* Heap OK */