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 3 - (view) (download) (as text)
Original Path: sml/branches/SMLNJ/src/runtime/gc/major-gc.c

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

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