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

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