Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/runtime/gc/major-gc.c
ViewVC logotype

Annotation of /sml/trunk/src/runtime/gc/major-gc.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1247 - (view) (download) (as text)

1 : monnier 249 /* major-gc.c
2 :     *
3 :     * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.
4 :     *
5 :     * This is the regular garbage collector (for collecting the
6 :     * generations).
7 :     */
8 :    
9 :     #ifdef PAUSE_STATS /* GC pause statistics are UNIX dependent */
10 :     # include "ml-unixdep.h"
11 :     #endif
12 :    
13 :     #include "ml-base.h"
14 :     #include "ml-limits.h"
15 :     #include "ml-state.h"
16 :     #include "ml-values.h"
17 :     #include "ml-objects.h"
18 :     #include "memory.h"
19 :     #include "card-map.h"
20 :     #include "heap.h"
21 :     #include "tags.h"
22 :     #include "copy-loop.h"
23 :     #include "heap-monitor.h"
24 :     #include "ml-timer.h"
25 :     #include "gc-stats.h"
26 :    
27 :     #ifdef GC_STATS
28 :     long lastMinorGC = 0;
29 :     long numUpdates = 0;
30 :     long numBytesAlloc = 0;
31 :     long numBytesCopied = 0;
32 :     #endif
33 :    
34 :     #ifdef BO_REF_STATS
35 :     PVT long numBO1, numBO2, numBO3;
36 :     #define IFBO_COUNT1(aid) {if (IS_BIGOBJ_AID(aid)) numBO1++;}
37 :     #define BO2_COUNT (numBO2)++
38 :     #define BO3_COUNT (numBO3)++
39 :     #else
40 :     #define IFBO_COUNT1(aid) {}
41 :     #define BO2_COUNT {}
42 :     #define BO3_COUNT {}
43 :     #endif
44 :    
45 :     #ifdef COUNT_CARDS
46 :     #ifndef BIT_CARDS
47 :     PVT unsigned long cardCnt1[MAX_NUM_GENS], cardCnt2[MAX_NUM_GENS];
48 :     #define COUNT_CARD1(i) (cardCnt1[i]++)
49 :     #define COUNT_CARD2(i) (cardCnt2[i]++)
50 :     #else
51 :     PVT unsigned long cardCnt[MAX_NUM_GENS];
52 :     #define COUNT_CARD(i) (cardCnt[i]++)
53 :     #endif
54 :     #else
55 :     #define COUNT_CARD(i) {}
56 :     #define COUNT_CARD1(i) {}
57 :     #define COUNT_CARD2(i) {}
58 :     #endif
59 :    
60 :    
61 :     /** DEBUG **/
62 :     #ifdef BO_DEBUG
63 :     PVT void ScanMem (Word_t *start, Word_t *stop, int gen, int objKind)
64 :     {
65 :     bibop_t bibop = BIBOP;
66 :     Word_t w;
67 :     int indx;
68 :     aid_t aid;
69 :     bigobj_region_t *region;
70 :     bigobj_desc_t *dp;
71 :    
72 :     while (start < stop) {
73 :     w = *start;
74 :     if (isBOXED(w)) {
75 :     int indx = BIBOP_ADDR_TO_INDEX(w);
76 :     aid_t id = bibop[indx];
77 :     switch (EXTRACT_OBJC(id)) {
78 :     case OBJC_bigobj:
79 :     while (!BO_IS_HDR(id)) {
80 :     id = bibop[--indx];
81 :     }
82 :     region = (bigobj_region_t *)BIBOP_INDEX_TO_ADDR(indx);
83 :     dp = ADDR_TO_BODESC(region, w);
84 :     if (dp->state == BO_FREE) {
85 :     SayDebug ("** [%d/%d]: %#x --> %#x; unexpected free big-object\n",
86 :     gen, objKind, start, w);
87 :     }
88 :     break;
89 :     case OBJC_record:
90 :     case OBJC_pair:
91 :     case OBJC_string:
92 :     case OBJC_array:
93 :     break;
94 :     default:
95 :     if (id != AID_UNMAPPED)
96 :     SayDebug ("** [%d/%d]: %#x --> %#x; strange object class %d\n",
97 :     gen, objKind, start, w, EXTRACT_OBJC(id));
98 :     break;
99 :     }
100 :     }
101 :     start++;
102 :     }
103 :     }
104 :     #endif /** BO_DEBUG **/
105 :    
106 :     /* local routines */
107 :     PVT void MajorGC_ScanRoots (
108 :     ml_state_t *msp, heap_t *heap, ml_val_t **roots, int maxCollectedGen);
109 :     PVT void MajorGC_SweepToSpace (heap_t *heap, int maxCollectedGen, int maxSweptGen);
110 :     PVT bool_t MajorGC_SweepToSpArrays (
111 :     heap_t *heap, int maxGen, arena_t *tosp, card_map_t *cm);
112 :     PVT ml_val_t MajorGC_ForwardObj (
113 :     heap_t *heap, aid_t maxAid, ml_val_t obj, aid_t id);
114 :     PVT bigobj_desc_t *MajorGC_ForwardBigObj (
115 :     heap_t *heap, int maxGen, ml_val_t obj, aid_t id);
116 :     PVT ml_val_t MajorGC_FwdSpecial (
117 :     heap_t *heap, aid_t maxAid, ml_val_t *obj, aid_t id, ml_val_t desc);
118 : jhr 1247 PVT void TrimHeap (heap_t *heap, int maxCollectedGen);
119 : monnier 249
120 :     /* the symbolic names of the arenas */
121 :     char *ArenaName[NUM_ARENAS+1] = {
122 :     "new", "record", "pair", "string", "array"
123 :     };
124 :     /* DEBUG */PVT char *StateName[] = {"FREE", "YOUNG", "FORWARD", "OLD", "PROMOTE"};
125 :    
126 :     /* Check a word for a from-space reference */
127 :     #ifdef TOSPACE_ID
128 :     #define NO_GC_INLINE /* DEBUG */
129 :     #endif
130 :     #ifndef NO_GC_INLINE
131 :     #define MajorGC_CheckWord(heap,bibop,maxAid,p) { \
132 :     ml_val_t __w = *(p); \
133 :     if (isBOXED(__w)) { \
134 :     aid_t __aid = ADDR_TO_PAGEID(bibop, __w); \
135 :     IFBO_COUNT1(__aid); \
136 :     if (IS_FROM_SPACE(__aid,maxAid)) { \
137 :     *(p) = MajorGC_ForwardObj(heap, maxAid, __w, __aid); \
138 :     } \
139 :     } \
140 :     }
141 :     #else
142 :     PVT void MajorGC_CheckWord (heap_t *heap, bibop_t bibop, aid_t maxAid, ml_val_t *p)
143 :     {
144 :     ml_val_t w = *(p);
145 :     if (isBOXED(w)) {
146 :     aid_t arena_id = ADDR_TO_PAGEID(bibop, w);
147 :     IFBO_COUNT1(arena_id); \
148 :     if (IS_FROM_SPACE(arena_id, maxAid)) {
149 :     *(p) = MajorGC_ForwardObj(heap, maxAid, w, arena_id);
150 :     }
151 :     #ifdef TOSPACE_ID
152 :     else if (IS_TOSPACE_AID(arena_id)) {
153 :     Die ("CheckWord: TOSPACE reference: %#x (%#x) --> %#x\n",
154 :     p, ADDR_TO_PAGEID(bibop, p), w);
155 :     }
156 :     #endif
157 :     }
158 :     }
159 :     #endif
160 :    
161 :    
162 :     /* MajorGC:
163 :     *
164 :     * Do a garbage collection of (at least) the first level generations.
165 :     * By definition, level should be at least 1.
166 :     */
167 :     void MajorGC (ml_state_t *msp, ml_val_t **roots, int level)
168 :     {
169 :     heap_t *heap = msp->ml_heap;
170 :     bibop_t bibop = BIBOP;
171 :     int i, j;
172 :     int maxCollectedGen; /* the oldest generation being collected */
173 :     int maxSweptGen;
174 :     #ifdef GC_STATS
175 :     ml_val_t *tospTop[NUM_ARENAS]; /* for counting # of bytes forwarded */
176 :     #endif
177 :    
178 :     #ifndef PAUSE_STATS /* don't do timing when collecting pause data */
179 :     StartGCTimer(msp->ml_vproc);
180 :     #endif
181 :     #ifdef BO_REF_STATS
182 :     numBO1 = numBO2 = numBO3 = 0;
183 :     #endif
184 :    
185 :     /* Flip to-space and from-space */
186 :     maxCollectedGen = Flip (heap, level);
187 :     if (maxCollectedGen < heap->numGens) {
188 :     maxSweptGen = maxCollectedGen+1;
189 :     #ifdef GC_STATS
190 :     /* Remember the top of to-space for maxSweptGen */
191 :     for (i = 0; i < NUM_ARENAS; i++)
192 :     tospTop[i] = heap->gen[maxSweptGen-1]->arena[i]->nextw;
193 :     #endif /* GC_STATS */
194 :     }
195 :     else {
196 :     maxSweptGen = maxCollectedGen;
197 :     }
198 :     NUM_GC_GENS(maxCollectedGen); /* record pause info */
199 :    
200 :     #ifdef VM_STATS
201 :     ReportVM (msp, maxCollectedGen);
202 :     #endif
203 :    
204 :     #ifndef PAUSE_STATS /* don't do messages when collecting pause data */
205 :     if (GCMessages) {
206 :     SayDebug ("GC #");
207 :     for (i = heap->numGens-1; i >= 0; i--) {
208 :     SayDebug ("%d.", heap->gen[i]->numGCs);
209 :     }
210 :     SayDebug ("%d: ", heap->numMinorGCs);
211 :     }
212 :     #endif
213 :    
214 :     HeapMon_StartGC (heap, maxCollectedGen);
215 :    
216 :     /* Scan the roots */
217 :     MajorGC_ScanRoots (msp, heap, roots, maxCollectedGen);
218 :    
219 :     /* Sweep to-space */
220 :     MajorGC_SweepToSpace (heap, maxCollectedGen, maxSweptGen);
221 :    
222 :     /* Handle weak pointers */
223 :     if (heap->weakList != NIL(ml_val_t *))
224 :     ScanWeakPtrs (heap);
225 :    
226 :     /* reclaim from-space; we do this from oldest to youngest so that
227 :     * we can promote big objects.
228 :     */
229 :     for (i = maxCollectedGen; i > 0; i--) {
230 :     gen_t *gen = heap->gen[i-1], *promoteGen;
231 :     int forwardState, promoteState;
232 :    
233 :     FreeGeneration (heap, i-1);
234 :     #ifdef TOSPACE_ID
235 :     for (j = 0; j < NUM_ARENAS; j++) {
236 :     arena_t *ap = gen->arena[j];
237 :     if (isACTIVE(ap))
238 :     MarkRegion (bibop, ap->tospBase, ap->tospSizeB, ap->id);
239 :     }
240 :     #endif
241 :     /* NOTE: there should never be any big-objects in the oldest generation
242 :     * with the BO_PROMOTE tag.
243 :     */
244 :     if (i != heap->numGens) {
245 :     promoteGen = heap->gen[i];
246 :     forwardState = BO_OLD;
247 :     /* the objects promoted from generation i to generation i+1, when
248 :     * generation i+1 is also being collected, are "OLD", thus we need
249 :     * to mark the corresponding big objects as old so that they do not
250 :     * get out of sync. Since the oldest generation has only YOUNG
251 :     * objects, we have to check for that case too.
252 :     */
253 :     if ((i == maxCollectedGen) || (i == heap->numGens-1))
254 :     promoteState = BO_YOUNG;
255 :     else
256 :     promoteState = BO_OLD;
257 :     }
258 :     else {
259 :     /* oldest generation objects are promoted to the same generation */
260 :     promoteGen = heap->gen[i-1];
261 :     forwardState = BO_YOUNG; /* oldest gen has only YOUNG objects */
262 :     }
263 :     for (j = 0; j < NUM_BIGOBJ_KINDS; j++) {
264 :     bigobj_desc_t *dp, *dq, *forward, *promote;
265 :     promote = promoteGen->bigObjs[j];
266 :     forward = NIL(bigobj_desc_t *);
267 :     for (dp = gen->bigObjs[j]; dp != NIL(bigobj_desc_t *); ) {
268 :     dq = dp->next;
269 :     ASSERT(dp->gen == i);
270 :     switch (dp->state) {
271 :     case BO_YOUNG:
272 :     case BO_OLD:
273 :     BO_Free (heap, dp);
274 :     break;
275 :     case BO_FORWARD:
276 :     dp->state = forwardState;
277 :     dp->next = forward;
278 :     forward = dp;
279 :     break;
280 :     case BO_PROMOTE:
281 :     dp->state = promoteState;
282 :     dp->next = promote;
283 :     dp->gen++;
284 :     promote = dp;
285 :     break;
286 :     default:
287 :     Die ("strange bigobject state %d @ %#x in generation %d\n",
288 :     dp->state, dp, i);
289 :     } /* end switch */
290 :     dp = dq;
291 :     }
292 :     promoteGen->bigObjs[j] = promote; /* a nop for the oldest generation */
293 :     gen->bigObjs[j] = forward;
294 :     }
295 :     }
296 :     #ifdef BO_DEBUG
297 :     /** DEBUG **/
298 :     for (i = 0; i < heap->numGens; i++) {
299 :     gen_t *gen = heap->gen[i];
300 :     ScanMem((Word_t *)(gen->arena[RECORD_INDX]->tospBase), (Word_t *)(gen->arena[RECORD_INDX]->nextw), i+1, RECORD_INDX);
301 :     ScanMem((Word_t *)(gen->arena[PAIR_INDX]->tospBase), (Word_t *)(gen->arena[PAIR_INDX]->nextw), i+1, PAIR_INDX);
302 :     ScanMem((Word_t *)(gen->arena[ARRAY_INDX]->tospBase), (Word_t *)(gen->arena[ARRAY_INDX]->nextw), i+1, ARRAY_INDX);
303 :     }
304 :     /** DEBUG **/
305 :     #endif
306 :    
307 :     /* relabel BIBOP entries for big-object regions to reflect promotions */
308 :     {
309 :     bigobj_region_t *rp;
310 :     bigobj_desc_t *dp;
311 :     int min;
312 :    
313 :     for (rp = heap->bigRegions; rp != NIL(bigobj_region_t *); rp = rp->next) {
314 :     /* if the minimum generation of the region is less than or equal
315 :     * to maxCollectedGen, then it is possible that it has increased
316 :     * as a result of promotions or freeing of objects.
317 :     */
318 :     if (rp->minGen <= maxCollectedGen) {
319 :     min = MAX_NUM_GENS;
320 :     for (i = 0; i < rp->nPages; ) {
321 :     dp = rp->objMap[i];
322 :     if ((! BO_IS_FREE(dp)) && (dp->gen < min))
323 :     min = dp->gen;
324 :     i += BO_NUM_BOPAGES(dp);
325 :     }
326 :     if (rp->minGen != min) {
327 :     rp->minGen = min;
328 :     MarkRegion (bibop, (ml_val_t *)rp, MEMOBJ_SZB(rp->memObj),
329 :     AID_BIGOBJ(min));
330 :     bibop[BIBOP_ADDR_TO_INDEX(rp)] = AID_BIGOBJ_HDR(min);
331 :     }
332 :     }
333 :     } /* end for */
334 :     }
335 :    
336 :     /* remember the top of to-space in the collected generations */
337 :     for (i = 0; i < maxCollectedGen; i++) {
338 :     gen_t *g = heap->gen[i];
339 :     if (i == heap->numGens-1) {
340 :     /* the oldest generation has only "young" objects */
341 :     for (j = 0; j < NUM_ARENAS; j++) {
342 :     if (isACTIVE(g->arena[j]))
343 :     g->arena[j]->oldTop = g->arena[j]->tospBase;
344 :     else
345 :     g->arena[j]->oldTop = NIL(ml_val_t *);
346 :     }
347 :     }
348 :     else {
349 :     for (j = 0; j < NUM_ARENAS; j++) {
350 :     if (isACTIVE(g->arena[j]))
351 :     g->arena[j]->oldTop = g->arena[j]->nextw;
352 :     else
353 :     g->arena[j]->oldTop = NIL(ml_val_t *);
354 :     }
355 :     }
356 :     }
357 :    
358 :     HeapMon_UpdateHeap (heap, maxSweptGen);
359 :    
360 :     #ifdef GC_STATS
361 :     /* Count the number of forwarded bytes */
362 :     if (maxSweptGen != maxCollectedGen) {
363 :     gen_t *gen = heap->gen[maxSweptGen-1];
364 :     for (j = 0; j < NUM_ARENAS; j++) {
365 :     CNTR_INCR(&(heap->numCopied[maxSweptGen-1][j]),
366 :     gen->arena[j]->nextw - tospTop[j]);
367 :     }
368 :     }
369 :     for (i = 0; i < maxCollectedGen; i++) {
370 :     for (j = 0; j < NUM_ARENAS; j++) {
371 :     arena_t *ap = heap->gen[i]->arena[j];
372 :     if (isACTIVE(ap)) {
373 :     CNTR_INCR(&(heap->numCopied[i][j]), ap->nextw - tospTop[j]);
374 :     }
375 :     }
376 :     }
377 :     #endif
378 :    
379 :     #ifdef BO_REF_STATS
380 :     SayDebug ("bigobj stats: %d seen, %d lookups, %d forwarded\n",
381 :     numBO1, numBO2, numBO3);
382 :     #endif
383 :     #ifndef PAUSE_STATS /* don't do timing when collecting pause data */
384 :     if (GCMessages) {
385 :     long gcTime;
386 :     StopGCTimer (msp->ml_vproc, &gcTime);
387 :     SayDebug (" (%d ms)\n", gcTime);
388 :     }
389 :     else
390 :     StopGCTimer (msp->ml_vproc, NIL(long *));
391 :     #endif
392 :    
393 :     #ifdef VM_STATS
394 :     ReportVM (msp, 0);
395 :     #endif
396 :    
397 :     #ifdef CHECK_HEAP
398 :     CheckHeap(heap, maxSweptGen);
399 :     #endif
400 :    
401 : jhr 1247 TrimHeap (heap, maxCollectedGen);
402 :    
403 : monnier 249 } /* end of MajorGC. */
404 :    
405 :    
406 :     /* MajorGC_ScanRoots:
407 :     */
408 :     PVT void MajorGC_ScanRoots (
409 :     ml_state_t *msp,
410 :     heap_t *heap,
411 :     ml_val_t **roots,
412 :     int maxCollectedGen)
413 :     {
414 :     bibop_t bibop = BIBOP;
415 :     aid_t maxAid = MAKE_MAX_AID(maxCollectedGen);
416 :     ml_val_t *rp;
417 :     int i;
418 :    
419 :     while ((rp = *roots++) != NIL(ml_val_t *)) {
420 :     MajorGC_CheckWord(heap, bibop, maxAid, rp);
421 :     }
422 :    
423 :     /* Scan the dirty cards in the older generations */
424 :     for (i = maxCollectedGen; i < heap->numGens; i++) {
425 :     gen_t *gen = heap->gen[i];
426 :     #ifdef COUNT_CARDS
427 :     #ifndef BIT_CARDS
428 :     /*CARD*/cardCnt1[i]=cardCnt2[i]=0;
429 :     #else
430 :     /*CARD*/cardCnt[i]=0;
431 :     #endif
432 :     #endif
433 :     if (isACTIVE(gen->arena[ARRAY_INDX])) {
434 :     card_map_t *cm = gen->dirty;
435 :     if (cm != NIL(card_map_t *)) {
436 :     ml_val_t *maxSweep = gen->arena[ARRAY_INDX]->sweep_nextw;
437 :     int card;
438 :     #if (!defined(BIT_CARDS) && defined(TOSPACE_ID))
439 :     FOR_DIRTY_CARD (cm, maxCollectedGen, card, {
440 :     ml_val_t *p = (cm->baseAddr + (card*CARD_SZW));
441 :     ml_val_t *q = p + CARD_SZW;
442 :     int mark = i+1;
443 :     COUNT_CARD1(i);
444 :     if (q > maxSweep)
445 :     /* don't sweep above the allocation high-water mark */
446 :     q = maxSweep;
447 :     for (; p < q; p++) {
448 :     ml_val_t w = *p;
449 :     if (isBOXED(w)) {
450 :     aid_t aid = ADDR_TO_PAGEID(bibop, w);
451 :     int targetGen;
452 :     IFBO_COUNT1(aid);
453 :     if (IS_FROM_SPACE(aid, maxAid)) {
454 :     /* this is a from-space object */
455 :     if (IS_BIGOBJ_AID(aid)) {
456 :     bigobj_desc_t *dp;
457 :     dp = MajorGC_ForwardBigObj (
458 :     heap, maxCollectedGen, w, aid);
459 :     targetGen = dp->gen;
460 :     }
461 :     else {
462 :     *p =
463 :     w = MajorGC_ForwardObj(heap, maxAid, w, aid);
464 :     aid = ADDR_TO_PAGEID(bibop, w);
465 :     if (IS_TOSPACE_AID(aid))
466 :     targetGen = TOSPACE_GEN(aid);
467 :     else
468 :     targetGen = EXTRACT_GEN(aid);
469 :     }
470 :     if (targetGen < mark)
471 :     mark = targetGen;
472 :     }
473 :     }
474 :     } /* end of for */
475 :     /* re-mark the card */
476 :     ASSERT(cm->map[card] <= mark);
477 :     if (mark <= i)
478 :     cm->map[card] = mark;
479 :     else if (i == maxCollectedGen)
480 :     cm->map[card] = CARD_CLEAN;
481 :     });
482 :     #elif (!defined(BIT_CARDS))
483 :     FOR_DIRTY_CARD (cm, maxCollectedGen, card, {
484 :     ml_val_t *p = (cm->baseAddr + (card*CARD_SZW));
485 :     ml_val_t *q = p + CARD_SZW;
486 :     int mark = i+1;
487 :     COUNT_CARD1(i);
488 :     if (q > maxSweep)
489 :     /* don't sweep above the allocation high-water mark */
490 :     q = maxSweep;
491 :     for (; p < q; p++) {
492 :     ml_val_t w = *p;
493 :     if (isBOXED(w)) {
494 :     aid_t aid = ADDR_TO_PAGEID(bibop, w);
495 :     int targetGen;
496 :     IFBO_COUNT1(aid);
497 :     if (IS_FROM_SPACE(aid, maxAid)) {
498 :     /* this is a from-space object */
499 :     COUNT_CARD2(i);
500 :     if (IS_BIGOBJ_AID(aid)) {
501 :     bigobj_desc_t *dp;
502 :     dp = MajorGC_ForwardBigObj (
503 :     heap, maxCollectedGen, w, aid);
504 :     targetGen = dp->gen;
505 :     }
506 :     else {
507 :     *p =
508 :     w = MajorGC_ForwardObj(heap, maxAid, w, aid);
509 :     targetGen = EXTRACT_GEN(ADDR_TO_PAGEID(bibop, w));
510 :     }
511 :     if (targetGen < mark)
512 :     mark = targetGen;
513 :     }
514 :     }
515 :     } /* end of for */
516 :     /* re-mark the card */
517 :     ASSERT(cm->map[card] <= mark);
518 :     if (mark <= i)
519 :     cm->map[card] = mark;
520 :     else if (i == maxCollectedGen)
521 :     cm->map[card] = CARD_CLEAN;
522 :     });
523 :     #else
524 :     FOR_DIRTY_CARD (cm, card, {
525 :     ml_val_t *p = (cm->baseAddr + (card*CARD_SZW));
526 :     ml_val_t *q = p + CARD_SZW;
527 :     COUNT_CARD(i);
528 :     if (q > maxSweep)
529 :     /* don't sweep above the allocation high-water mark */
530 :     q = maxSweep;
531 :     for (; p < q; p++) {
532 :     MajorGC_CheckWord (heap, bibop, maxAid, p);
533 :     }
534 :     });
535 :     #endif
536 :     }
537 :     }
538 :     } /* end of for */
539 :    
540 :     #ifdef COUNT_CARDS
541 :     /*CARD*/SayDebug ("\n[%d] SWEEP: ", maxCollectedGen);
542 :     /*CARD*/for(i = maxCollectedGen; i < heap->numGens; i++) {
543 :     /*CARD*/ card_map_t *cm = heap->gen[i]->dirty;
544 :     /*CARD*/ if (i > maxCollectedGen) SayDebug (", ");
545 :     #ifndef BIT_CARDS
546 :     /*CARD*/ SayDebug ("[%d] %d/%d/%d", i+1, cardCnt1[i], cardCnt2[i],
547 :     /*CARD*/ (cm != NIL(card_map_t*)) ? cm->numCards : 0);
548 :     #else
549 :     /*CARD*/ SayDebug ("[%d] %d/%d", i+1, cardCnt[i],
550 :     /*CARD*/ (cm != NIL(card_map_t*)) ? cm->numCards : 0);
551 :     #endif
552 :     /*CARD*/}
553 :     /*CARD*/SayDebug ("\n");
554 :     #endif
555 :    
556 :     } /* end of MajorGC_ScanRoots */
557 :    
558 :    
559 :     /* MajorGC_SweepToSpace:
560 :     * Sweep the to-space arenas. Because there are few references forward in time, we
561 :     * try to completely scavenge a younger generation before moving on to the
562 :     * next oldest.
563 :     */
564 :     PVT void MajorGC_SweepToSpace (heap_t *heap, int maxCollectedGen, int maxSweptGen)
565 :     {
566 :     int i;
567 :     bool_t swept;
568 :     bibop_t bibop = BIBOP;
569 :     aid_t maxAid = MAKE_MAX_AID(maxCollectedGen);
570 :    
571 :     #define SweepToSpArena(gen, indx) { \
572 :     arena_t *__ap = (gen)->arena[(indx)]; \
573 :     if (isACTIVE(__ap)) { \
574 :     ml_val_t *__p, *__q; \
575 :     __p = __ap->sweep_nextw; \
576 :     if (__p < __ap->nextw) { \
577 :     swept = TRUE; \
578 :     do { \
579 :     for (__q = __ap->nextw; __p < __q; __p++) { \
580 :     MajorGC_CheckWord(heap, bibop, maxAid, __p); \
581 :     } \
582 :     } while (__q != __ap->nextw); \
583 :     __ap->sweep_nextw = __q; \
584 :     } \
585 :     } \
586 :     } /* SweepToSpArena */
587 :    
588 :     do {
589 :     swept = FALSE;
590 :     for (i = 0; i < maxSweptGen; i++) {
591 :     gen_t *gen = heap->gen[i];
592 :    
593 :     /* Sweep the record and pair arenas */
594 :     SweepToSpArena(gen, RECORD_INDX);
595 :     SweepToSpArena(gen, PAIR_INDX);
596 :    
597 :     /* Sweep the array arena */
598 :     {
599 :     arena_t *ap = gen->arena[ARRAY_INDX];
600 :     if (isACTIVE(ap)
601 :     && MajorGC_SweepToSpArrays (heap, maxCollectedGen, ap, gen->dirty))
602 :     swept = TRUE;
603 :     }
604 :     }
605 :     } while (swept);
606 :    
607 :     }/* end of SweepToSpace */
608 :    
609 :    
610 :     /* MajorGC_SweepToSpArrays:
611 :     *
612 :     * Sweep the to-space of the array arena, returning true if any objects
613 :     * are actually swept.
614 :     */
615 :     PVT bool_t MajorGC_SweepToSpArrays (
616 :     heap_t *heap, int maxGen, arena_t *tosp, card_map_t *cm)
617 :     {
618 :     ml_val_t w, *p, *stop;
619 :     int thisGen;
620 :     Word_t cardMask = ~(CARD_SZB - 1);
621 :     aid_t *bibop = BIBOP;
622 :     aid_t maxAid = MAKE_MAX_AID(maxGen);
623 :     #ifndef BIT_CARDS
624 :     ml_val_t *cardStart;
625 :     int cardMark;
626 :     #endif
627 :    
628 :     /* Sweep a single card at a time, looking for references that need to
629 :     * be remembered.
630 :     */
631 :     thisGen = EXTRACT_GEN(tosp->id);
632 :     p = tosp->sweep_nextw;
633 :     if (p == tosp->nextw)
634 :     return FALSE;
635 :     while (p < tosp->nextw) {
636 :     stop = (ml_val_t *)(((Addr_t)p + CARD_SZB) & cardMask);
637 :     if (stop > tosp->nextw)
638 :     stop = tosp->nextw;
639 :     /* Sweep the next page until we see a reference to a younger generation */
640 :     #ifndef BIT_CARDS
641 :     cardStart = p;
642 :     cardMark = CARD(cm, cardStart);
643 :     #endif
644 :     while (p < stop) {
645 :     if (isBOXED(w = *p)) {
646 :     aid_t arena_id = ADDR_TO_PAGEID(bibop, w);
647 :     int targetGen;
648 :    
649 :     IFBO_COUNT1(arena_id);
650 :     if (IS_FROM_SPACE(arena_id, maxAid)) {
651 :     /* this is a from-space object */
652 :     if (IS_BIGOBJ_AID(arena_id)) {
653 :     bigobj_desc_t *dp;
654 :     dp = MajorGC_ForwardBigObj (heap, maxGen, w, arena_id);
655 :     targetGen = dp->gen;
656 :     }
657 :     else {
658 :     *p = w = MajorGC_ForwardObj(heap, maxAid, w, arena_id);
659 :     #ifdef TOSPACE_ID
660 :     { aid_t aid = ADDR_TO_PAGEID(bibop, w);
661 :     if (IS_TOSPACE_AID(aid))
662 :     targetGen = TOSPACE_GEN(aid);
663 :     else
664 :     targetGen = EXTRACT_GEN(aid);
665 :     }
666 :     #else
667 :     targetGen = EXTRACT_GEN(ADDR_TO_PAGEID(bibop, w));
668 :     #endif
669 :     }
670 :     #ifndef BIT_CARDS
671 :     if (targetGen < cardMark)
672 :     cardMark = targetGen;
673 :     #else
674 :     if (targetGen < thisGen) {
675 :     /* the forwarded object is in a younger generation */
676 :     MARK_CARD(cm, p);
677 :     /* finish the card up quickly */
678 :     for (p++; p < stop; p++) {
679 :     MajorGC_CheckWord(heap, bibop, maxAid, p);
680 :     }
681 :     break;
682 :     }
683 :     #endif
684 :     }
685 :     #ifdef TOSPACE_ID
686 :     else if (IS_TOSPACE_AID(arena_id)) {
687 :     Die ("Sweep Arrays: TOSPACE reference: %#x (%#x) --> %#x\n",
688 :     p, ADDR_TO_PAGEID(bibop, p), w);
689 :     }
690 :     #endif
691 :     }
692 :     p++;
693 :     } /* end of while */
694 :     #ifndef BIT_CARDS
695 :     if (cardMark < thisGen)
696 :     MARK_CARD(cm, cardStart, cardMark);
697 :     #endif
698 :     } /* end of while */
699 :     tosp->sweep_nextw = p;
700 :    
701 :     return TRUE;
702 :    
703 :     } /* end of MajorGC_SweepToSpArrays */
704 :    
705 :    
706 :     /* MajorGC_ForwardObj:
707 :     *
708 :     * Forward an object.
709 :     */
710 :     PVT ml_val_t MajorGC_ForwardObj (heap_t *heap, aid_t maxAid, ml_val_t v, aid_t id)
711 :     {
712 :     ml_val_t *obj = PTR_MLtoC(ml_val_t, v);
713 :     ml_val_t *new_obj;
714 :     ml_val_t desc;
715 :     Word_t len;
716 :     arena_t *arena;
717 :    
718 :     switch (EXTRACT_OBJC(id)) {
719 :     case OBJC_record: {
720 :     desc = obj[-1];
721 :     switch (GET_TAG(desc)) {
722 :     case DTAG_vec_hdr:
723 :     case DTAG_arr_hdr:
724 :     len = 2;
725 :     break;
726 :     case DTAG_forward:
727 :     /* This object has already been forwarded */
728 :     return PTR_CtoML(FOLLOW_FWDOBJ(obj));
729 :     case DTAG_record:
730 :     len = GET_LEN(desc);
731 :     break;
732 :     default:
733 :     Die ("bad record tag %d, obj = %#x, desc = %#x",
734 :     GET_TAG(desc), obj, desc);
735 :     } /* end of switch */
736 :     arena = heap->gen[EXTRACT_GEN(id)-1]->arena[RECORD_INDX];
737 :     if (isOLDER(arena, obj))
738 :     arena = arena->nextGen;
739 :     } break;
740 :    
741 :     case OBJC_pair: {
742 :     ml_val_t w;
743 :    
744 :     w = obj[0];
745 :     if (isDESC(w))
746 :     return PTR_CtoML(FOLLOW_FWDPAIR(w, obj));
747 :     else {
748 :     /* forward the pair */
749 :     arena = heap->gen[EXTRACT_GEN(id)-1]->arena[PAIR_INDX];
750 :     if (isOLDER(arena, obj))
751 :     arena = arena->nextGen;
752 :     new_obj = arena->nextw;
753 :     arena->nextw += PAIR_SZW;
754 :     new_obj[0] = w;
755 :     new_obj[1] = obj[1];
756 :     /* setup the forward pointer in the old pair */
757 :     obj[0] = MAKE_PAIR_FP(new_obj);
758 :     return PTR_CtoML(new_obj);
759 :     }
760 :     } break;
761 :    
762 :     case OBJC_string: {
763 :     arena = heap->gen[EXTRACT_GEN(id)-1]->arena[STRING_INDX];
764 :     if (isOLDER(arena, obj))
765 :     arena = arena->nextGen;
766 :     desc = obj[-1];
767 :     switch (GET_TAG(desc)) {
768 :     case DTAG_forward:
769 :     return PTR_CtoML(FOLLOW_FWDOBJ(obj));
770 :     case DTAG_raw32:
771 :     len = GET_LEN(desc);
772 :     break;
773 :     case DTAG_raw64:
774 :     len = GET_LEN(desc);
775 :     #ifdef ALIGN_REALDS
776 :     # ifdef CHECK_HEAP
777 :     if (((Addr_t)arena->nextw & WORD_SZB) == 0) {
778 :     *(arena->nextw) = (ml_val_t)0;
779 :     arena->nextw++;
780 :     }
781 :     # else
782 :     arena->nextw = (ml_val_t *)(((Addr_t)arena->nextw) | WORD_SZB);
783 :     # endif
784 :     #endif
785 :     break;
786 :     default:
787 :     Die ("bad string tag %d, obj = %#x, desc = %#x",
788 :     GET_TAG(desc), obj, desc);
789 :     } /* end of switch */
790 :     } break;
791 :    
792 :     case OBJC_array: {
793 :     desc = obj[-1];
794 :     switch (GET_TAG(desc)) {
795 :     case DTAG_forward:
796 :     /* This object has already been forwarded */
797 :     return PTR_CtoML(FOLLOW_FWDOBJ(obj));
798 :     case DTAG_arr_data:
799 :     len = GET_LEN(desc);
800 :     break;
801 :     case DTAG_special:
802 :     return MajorGC_FwdSpecial (heap, maxAid, obj, id, desc);
803 :     default:
804 :     Die ("bad array tag %d, obj = %#x, desc = %#x",
805 :     GET_TAG(desc), obj, desc);
806 :     } /* end of switch */
807 :     arena = heap->gen[EXTRACT_GEN(id)-1]->arena[ARRAY_INDX];
808 :     if (isOLDER(arena, obj))
809 :     arena = arena->nextGen;
810 :     } break;
811 :    
812 :     case OBJC_bigobj:
813 :     MajorGC_ForwardBigObj (heap, EXTRACT_GEN(maxAid), v, id);
814 :     return v;
815 :    
816 :     default:
817 :     Die("unknown object class %d @ %#x", EXTRACT_OBJC(id), obj);
818 :     } /* end of switch */
819 :    
820 :     /* Allocate and initialize a to-space copy of the object */
821 :     new_obj = arena->nextw;
822 :     arena->nextw += (len + 1);
823 :     *new_obj++ = desc;
824 :     ASSERT(arena->nextw <= arena->tospTop);
825 :     COPYLOOP(obj, new_obj, len);
826 :    
827 :     /* set up the forward pointer, and return the new object. */
828 :     obj[-1] = DESC_forwarded;
829 :     obj[0] = (ml_val_t)(Addr_t)new_obj;
830 :    
831 :     return PTR_CtoML(new_obj);
832 :    
833 :     } /* end of MajorGC_ForwardObj */
834 :    
835 :    
836 :     /* MajorGC_ForwardBigObj:
837 :     *
838 :     * Forward a big-object obj, where id is the BIBOP entry for obj.
839 :     * Return the descriptor for obj.
840 :     */
841 :     PVT bigobj_desc_t *MajorGC_ForwardBigObj (
842 :     heap_t *heap, int maxGen, ml_val_t obj, aid_t id)
843 :     {
844 : blume 569 int i;
845 : monnier 249 bigobj_region_t *region;
846 :     bigobj_desc_t *dp;
847 :    
848 :     BO2_COUNT;
849 :     for (i = BIBOP_ADDR_TO_INDEX(obj); !BO_IS_HDR(id); id = BIBOP[--i])
850 :     continue;
851 :     region = (bigobj_region_t *)BIBOP_INDEX_TO_ADDR(i);
852 :     dp = ADDR_TO_BODESC(region, obj);
853 :     if ((dp->gen <= maxGen) && BO_IS_FROM_SPACE(dp)) {
854 :     BO3_COUNT;
855 :     /* forward the big-object; note that objects in the oldest generation
856 :     * will always be YOUNG, thus will never be promoted.
857 :     */
858 :     if (dp->state == BO_YOUNG)
859 :     dp->state = BO_FORWARD;
860 :     else
861 :     dp->state = BO_PROMOTE;
862 :     }
863 :    
864 :     return dp;
865 :    
866 :     } /* end of MajorGC_ForwardBigObj */
867 :    
868 :    
869 :     /* MajorGC_FwdSpecial:
870 :     *
871 :     * Forward a special object (suspension, weak pointer, ...).
872 :     */
873 :     PVT ml_val_t MajorGC_FwdSpecial (
874 :     heap_t *heap,
875 :     aid_t maxAid,
876 :     ml_val_t *obj,
877 :     aid_t id,
878 :     ml_val_t desc
879 :     )
880 :     {
881 :     gen_t *gen = heap->gen[EXTRACT_GEN(id)-1];
882 :     arena_t *arena = gen->arena[ARRAY_INDX];
883 :     ml_val_t *new_obj;
884 :    
885 :     if (isOLDER(arena, obj))
886 :     arena = arena->nextGen;
887 :    
888 :     /* allocate the new object */
889 :     new_obj = arena->nextw;
890 :     arena->nextw += SPECIAL_SZW; /* all specials are two words */
891 :    
892 :     switch (GET_LEN(desc)) {
893 :     case SPCL_evaled_susp:
894 :     case SPCL_unevaled_susp:
895 :     case SPCL_null_weak:
896 :     *new_obj++ = desc;
897 :     *new_obj = *obj;
898 :     break;
899 :     case SPCL_weak: {
900 :     ml_val_t v = *obj;
901 :     #ifdef DEBUG_WEAK_PTRS
902 :     SayDebug ("MajorGC: weak [%#x ==> %#x] --> %#x", obj, new_obj+1, v);
903 :     #endif
904 :     if (! isBOXED(v)) {
905 :     #ifdef DEBUG_WEAK_PTRS
906 :     SayDebug (" unboxed\n");
907 :     #endif
908 :     /* weak references to unboxed objects are never nullified */
909 :     *new_obj++ = DESC_weak;
910 :     *new_obj = v;
911 :     }
912 :     else {
913 :     aid_t aid = ADDR_TO_PAGEID(BIBOP, v);
914 :     ml_val_t *vp = PTR_MLtoC(ml_val_t, v);
915 :     ml_val_t desc;
916 :    
917 :     if (IS_FROM_SPACE(aid, maxAid)) {
918 :     switch (EXTRACT_OBJC(aid)) {
919 :     case OBJC_record:
920 :     case OBJC_string:
921 :     case OBJC_array:
922 :     desc = vp[-1];
923 :     if (desc == DESC_forwarded) {
924 :     /* Reference to an object that has already been forwarded.
925 :     * NOTE: we have to put the pointer to the non-forwarded
926 :     * copy of the object (i.e, v) into the to-space copy
927 :     * of the weak pointer, since the GC has the invariant
928 :     * it never sees to-space pointers during sweeping.
929 :     */
930 :     #ifdef DEBUG_WEAK_PTRS
931 :     SayDebug (" already forwarded to %#x\n", FOLLOW_FWDOBJ(vp));
932 :     #endif
933 :     *new_obj++ = DESC_weak;
934 :     *new_obj = v;
935 :     }
936 :     else {
937 :     /* the forwarded version of weak objects are threaded
938 :     * via their descriptor fields. We mark the object
939 :     * reference field to make it look like an unboxed value,
940 :     * so that the to-space sweeper does not follow the weak
941 :     * reference.
942 :     */
943 :     #ifdef DEBUG_WEAK_PTRS
944 :     SayDebug (" forward (start = %#x)\n", vp);
945 :     #endif
946 :     *new_obj = MARK_PTR(PTR_CtoML(gen->heap->weakList));
947 :     gen->heap->weakList = new_obj++;
948 :     *new_obj = MARK_PTR(vp);
949 :     }
950 :     break;
951 :     case OBJC_pair:
952 :     if (isDESC(desc = vp[0])) {
953 :     /* Reference to a pair that has already been forwarded.
954 :     * NOTE: we have to put the pointer to the non-forwarded
955 :     * copy of the pair (i.e, v) into the to-space copy
956 :     * of the weak pointer, since the GC has the invariant
957 :     * it never sees to-space pointers during sweeping.
958 :     */
959 :     #ifdef DEBUG_WEAK_PTRS
960 :     SayDebug (" (pair) already forwarded to %#x\n", FOLLOW_FWDPAIR(desc, vp));
961 :     #endif
962 :     *new_obj++ = DESC_weak;
963 :     *new_obj = v;
964 :     }
965 :     else {
966 :     *new_obj = MARK_PTR(PTR_CtoML(gen->heap->weakList));
967 :     gen->heap->weakList = new_obj++;
968 :     *new_obj = MARK_PTR(vp);
969 :     }
970 :     break;
971 :     case OBJC_bigobj:
972 :     Die ("weak big object");
973 :     break;
974 :     }
975 :     }
976 :     else {
977 :     /* reference to an older object */
978 :     #ifdef DEBUG_WEAK_PTRS
979 :     SayDebug (" old object\n");
980 :     #endif
981 :     *new_obj++ = DESC_weak;
982 :     *new_obj = v;
983 :     }
984 :     }
985 :     } break;
986 :     default:
987 :     Die ("strange/unexpected special object @ %#x; desc = %#x\n", obj, desc);
988 :     } /* end of switch */
989 :    
990 :     obj[-1] = DESC_forwarded;
991 :     obj[0] = (ml_val_t)(Addr_t)new_obj;
992 :    
993 :     return PTR_CtoML(new_obj);
994 :    
995 :     } /* end of MajorGC_FwdSpecial */
996 : jhr 1247
997 :    
998 :     /* TrimHeap:
999 :     *
1000 :     * After a major collection, trim any arenas that are over their maximum
1001 :     * size in allocated space, but under their maximum size in used space.
1002 :     */
1003 :     PVT void TrimHeap (heap_t *heap, int maxCollectedGen)
1004 :     {
1005 :     int i, j;
1006 :     gen_t *gen;
1007 :     arena_t *ap;
1008 :     Word_t minSzB, newSzB;
1009 :    
1010 :     for (i = 0; i < maxCollectedGen; i++) {
1011 :     gen = heap->gen[i];
1012 :     for (j = 0; j < NUM_ARENAS; j++) {
1013 :     ap = gen->arena[j];
1014 :     if (isACTIVE(ap) && (ap->tospSizeB > ap->maxSizeB)) {
1015 :     minSzB = (i == 0)
1016 :     ? heap->allocSzB
1017 :     : heap->gen[i-1]->arena[j]->tospSizeB;
1018 :     minSzB += (USED_SPACE(ap) + ap->reqSizeB);
1019 :     if (minSzB < ap->maxSizeB)
1020 :     newSzB = ap->maxSizeB;
1021 :     else {
1022 :     newSzB = RND_MEMOBJ_SZB(minSzB);
1023 :     /* the calculation of minSz here may return something bigger
1024 :     * that what flip.c computed!
1025 :     */
1026 :     if (newSzB > ap->tospSizeB)
1027 :     newSzB = ap->tospSizeB;
1028 :     }
1029 :     ap->tospSizeB = newSzB;
1030 :     ap->tospTop = (Addr_t)ap->tospBase + ap->tospSizeB;
1031 :     }
1032 :     }
1033 :     }
1034 :    
1035 :     } /* end of TrimHeap */

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0