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/branches/SMLNJ/src/runtime/gc/major-gc.c
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/runtime/gc/major-gc.c

Parent Directory Parent Directory | Revision Log Revision Log


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

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 :     break;
94 :     default:
95 : monnier 8 if (id != AID_UNMAPPED)
96 :     SayDebug ("** [%d/%d]: %#x --> %#x; strange object class %d\n",
97 :     gen, objKind, start, w, EXTRACT_OBJC(id));
98 : monnier 2 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 : monnier 8 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 : monnier 2 #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 : monnier 8 if (GCMessages) {
384 : monnier 2 long gcTime;
385 :     StopGCTimer (msp->ml_vproc, &gcTime);
386 :     SayDebug (" (%d ms)\n", gcTime);
387 :     }
388 : monnier 8 else
389 :     StopGCTimer (msp->ml_vproc, NIL(long *));
390 : monnier 2 #endif
391 :    
392 :     #ifdef VM_STATS
393 :     ReportVM (msp, 0);
394 :     #endif
395 :    
396 :     /* DEBUG CheckHeap(heap, maxSweptGen); */
397 :    
398 :     } /* end of MajorGC. */
399 :    
400 :    
401 :     /* MajorGC_ScanRoots:
402 :     */
403 :     PVT void MajorGC_ScanRoots (
404 :     ml_state_t *msp,
405 :     heap_t *heap,
406 :     ml_val_t **roots,
407 :     int maxCollectedGen)
408 :     {
409 :     bibop_t bibop = BIBOP;
410 :     aid_t maxAid = MAKE_MAX_AID(maxCollectedGen);
411 :     ml_val_t *rp;
412 :     int i;
413 :    
414 :     while ((rp = *roots++) != NIL(ml_val_t *)) {
415 :     MajorGC_CheckWord(heap, bibop, maxAid, rp);
416 :     }
417 :    
418 :     /* Scan the dirty cards in the older generations */
419 :     for (i = maxCollectedGen; i < heap->numGens; i++) {
420 :     gen_t *gen = heap->gen[i];
421 :     #ifdef COUNT_CARDS
422 :     #ifndef BIT_CARDS
423 :     /*CARD*/cardCnt1[i]=cardCnt2[i]=0;
424 :     #else
425 :     /*CARD*/cardCnt[i]=0;
426 :     #endif
427 :     #endif
428 :     if (isACTIVE(gen->arena[ARRAY_INDX])) {
429 :     card_map_t *cm = gen->dirty;
430 :     if (cm != NIL(card_map_t *)) {
431 :     ml_val_t *maxSweep = gen->arena[ARRAY_INDX]->sweep_nextw;
432 :     int card;
433 :     #if (!defined(BIT_CARDS) && defined(TOSPACE_ID))
434 :     FOR_DIRTY_CARD (cm, maxCollectedGen, card, {
435 :     ml_val_t *p = (cm->baseAddr + (card*CARD_SZW));
436 :     ml_val_t *q = p + CARD_SZW;
437 :     int mark = i+1;
438 :     COUNT_CARD1(i);
439 :     if (q > maxSweep)
440 :     /* don't sweep above the allocation high-water mark */
441 :     q = maxSweep;
442 :     for (; p < q; p++) {
443 :     ml_val_t w = *p;
444 :     if (isBOXED(w)) {
445 :     aid_t aid = ADDR_TO_PAGEID(bibop, w);
446 :     int targetGen;
447 :     IFBO_COUNT1(aid);
448 :     if (IS_FROM_SPACE(aid, maxAid)) {
449 :     /* this is a from-space object */
450 :     if (IS_BIGOBJ_AID(aid)) {
451 :     bigobj_desc_t *dp;
452 :     dp = MajorGC_ForwardBigObj (
453 :     heap, maxCollectedGen, w, aid);
454 :     targetGen = dp->gen;
455 :     }
456 :     else {
457 :     *p =
458 :     w = MajorGC_ForwardObj(heap, maxAid, w, aid);
459 :     aid = ADDR_TO_PAGEID(bibop, w);
460 :     if (IS_TOSPACE_AID(aid))
461 :     targetGen = TOSPACE_GEN(aid);
462 :     else
463 :     targetGen = EXTRACT_GEN(aid);
464 :     }
465 :     if (targetGen < mark)
466 :     mark = targetGen;
467 :     }
468 :     }
469 :     } /* end of for */
470 :     /* re-mark the card */
471 :     ASSERT(cm->map[card] <= mark);
472 :     if (mark <= i)
473 :     cm->map[card] = mark;
474 :     else if (i == maxCollectedGen)
475 :     cm->map[card] = CARD_CLEAN;
476 :     });
477 :     #elif (!defined(BIT_CARDS))
478 :     FOR_DIRTY_CARD (cm, maxCollectedGen, card, {
479 :     ml_val_t *p = (cm->baseAddr + (card*CARD_SZW));
480 :     ml_val_t *q = p + CARD_SZW;
481 :     int mark = i+1;
482 :     COUNT_CARD1(i);
483 :     if (q > maxSweep)
484 :     /* don't sweep above the allocation high-water mark */
485 :     q = maxSweep;
486 :     for (; p < q; p++) {
487 :     ml_val_t w = *p;
488 :     if (isBOXED(w)) {
489 :     aid_t aid = ADDR_TO_PAGEID(bibop, w);
490 :     int targetGen;
491 :     IFBO_COUNT1(aid);
492 :     if (IS_FROM_SPACE(aid, maxAid)) {
493 :     /* this is a from-space object */
494 :     COUNT_CARD2(i);
495 :     if (IS_BIGOBJ_AID(aid)) {
496 :     bigobj_desc_t *dp;
497 :     dp = MajorGC_ForwardBigObj (
498 :     heap, maxCollectedGen, w, aid);
499 :     targetGen = dp->gen;
500 :     }
501 :     else {
502 :     *p =
503 :     w = MajorGC_ForwardObj(heap, maxAid, w, aid);
504 :     targetGen = EXTRACT_GEN(ADDR_TO_PAGEID(bibop, w));
505 :     }
506 :     if (targetGen < mark)
507 :     mark = targetGen;
508 :     }
509 :     }
510 :     } /* end of for */
511 :     /* re-mark the card */
512 :     ASSERT(cm->map[card] <= mark);
513 :     if (mark <= i)
514 :     cm->map[card] = mark;
515 :     else if (i == maxCollectedGen)
516 :     cm->map[card] = CARD_CLEAN;
517 :     });
518 :     #else
519 :     FOR_DIRTY_CARD (cm, card, {
520 :     ml_val_t *p = (cm->baseAddr + (card*CARD_SZW));
521 :     ml_val_t *q = p + CARD_SZW;
522 :     COUNT_CARD(i);
523 :     if (q > maxSweep)
524 :     /* don't sweep above the allocation high-water mark */
525 :     q = maxSweep;
526 :     for (; p < q; p++) {
527 :     MajorGC_CheckWord (heap, bibop, maxAid, p);
528 :     }
529 :     });
530 :     #endif
531 :     }
532 :     }
533 :     } /* end of for */
534 :    
535 :     #ifdef COUNT_CARDS
536 :     /*CARD*/SayDebug ("\n[%d] SWEEP: ", maxCollectedGen);
537 :     /*CARD*/for(i = maxCollectedGen; i < heap->numGens; i++) {
538 :     /*CARD*/ card_map_t *cm = heap->gen[i]->dirty;
539 :     /*CARD*/ if (i > maxCollectedGen) SayDebug (", ");
540 :     #ifndef BIT_CARDS
541 :     /*CARD*/ SayDebug ("[%d] %d/%d/%d", i+1, cardCnt1[i], cardCnt2[i],
542 :     /*CARD*/ (cm != NIL(card_map_t*)) ? cm->numCards : 0);
543 :     #else
544 :     /*CARD*/ SayDebug ("[%d] %d/%d", i+1, cardCnt[i],
545 :     /*CARD*/ (cm != NIL(card_map_t*)) ? cm->numCards : 0);
546 :     #endif
547 :     /*CARD*/}
548 :     /*CARD*/SayDebug ("\n");
549 :     #endif
550 :    
551 :     } /* end of MajorGC_ScanRoots */
552 :    
553 :    
554 :     /* MajorGC_SweepToSpace:
555 :     * Sweep the to-space arenas. Because there are few references forward in time, we
556 :     * try to completely scavenge a younger generation before moving on to the
557 :     * next oldest.
558 :     */
559 :     PVT void MajorGC_SweepToSpace (heap_t *heap, int maxCollectedGen, int maxSweptGen)
560 :     {
561 :     int i;
562 :     bool_t swept;
563 :     bibop_t bibop = BIBOP;
564 :     aid_t maxAid = MAKE_MAX_AID(maxCollectedGen);
565 :    
566 :     #define SweepToSpArena(gen, indx) { \
567 :     arena_t *__ap = (gen)->arena[(indx)]; \
568 :     if (isACTIVE(__ap)) { \
569 :     ml_val_t *__p, *__q; \
570 :     __p = __ap->sweep_nextw; \
571 :     if (__p < __ap->nextw) { \
572 :     swept = TRUE; \
573 :     do { \
574 :     for (__q = __ap->nextw; __p < __q; __p++) { \
575 :     MajorGC_CheckWord(heap, bibop, maxAid, __p); \
576 :     } \
577 :     } while (__q != __ap->nextw); \
578 :     __ap->sweep_nextw = __q; \
579 :     } \
580 :     } \
581 :     } /* SweepToSpArena */
582 :    
583 :     do {
584 :     swept = FALSE;
585 :     for (i = 0; i < maxSweptGen; i++) {
586 :     gen_t *gen = heap->gen[i];
587 :    
588 :     /* Sweep the record and pair arenas */
589 :     SweepToSpArena(gen, RECORD_INDX);
590 :     SweepToSpArena(gen, PAIR_INDX);
591 :    
592 :     /* Sweep the array arena */
593 :     {
594 :     arena_t *ap = gen->arena[ARRAY_INDX];
595 :     if (isACTIVE(ap)
596 :     && MajorGC_SweepToSpArrays (heap, maxCollectedGen, ap, gen->dirty))
597 :     swept = TRUE;
598 :     }
599 :     }
600 :     } while (swept);
601 :    
602 :     }/* end of SweepToSpace */
603 :    
604 :    
605 :     /* MajorGC_SweepToSpArrays:
606 :     *
607 :     * Sweep the to-space of the array arena, returning true if any objects
608 :     * are actually swept.
609 :     */
610 :     PVT bool_t MajorGC_SweepToSpArrays (
611 :     heap_t *heap, int maxGen, arena_t *tosp, card_map_t *cm)
612 :     {
613 :     ml_val_t w, *p, *stop;
614 :     int thisGen;
615 :     Word_t cardMask = ~(CARD_SZB - 1);
616 :     aid_t *bibop = BIBOP;
617 :     aid_t maxAid = MAKE_MAX_AID(maxGen);
618 :     #ifndef BIT_CARDS
619 :     ml_val_t *cardStart;
620 :     int cardMark;
621 :     #endif
622 :    
623 :     /* Sweep a single card at a time, looking for references that need to
624 :     * be remembered.
625 :     */
626 :     thisGen = EXTRACT_GEN(tosp->id);
627 :     p = tosp->sweep_nextw;
628 :     if (p == tosp->nextw)
629 :     return FALSE;
630 :     while (p < tosp->nextw) {
631 :     stop = (ml_val_t *)(((Addr_t)p + CARD_SZB) & cardMask);
632 :     if (stop > tosp->nextw)
633 :     stop = tosp->nextw;
634 :     /* Sweep the next page until we see a reference to a younger generation */
635 :     #ifndef BIT_CARDS
636 :     cardStart = p;
637 :     cardMark = CARD(cm, cardStart);
638 :     #endif
639 :     while (p < stop) {
640 :     if (isBOXED(w = *p)) {
641 :     aid_t arena_id = ADDR_TO_PAGEID(bibop, w);
642 :     int targetGen;
643 :    
644 :     IFBO_COUNT1(arena_id);
645 :     if (IS_FROM_SPACE(arena_id, maxAid)) {
646 :     /* this is a from-space object */
647 :     if (IS_BIGOBJ_AID(arena_id)) {
648 :     bigobj_desc_t *dp;
649 :     dp = MajorGC_ForwardBigObj (heap, maxGen, w, arena_id);
650 :     targetGen = dp->gen;
651 :     }
652 :     else {
653 :     *p = w = MajorGC_ForwardObj(heap, maxAid, w, arena_id);
654 :     #ifdef TOSPACE_ID
655 :     { aid_t aid = ADDR_TO_PAGEID(bibop, w);
656 :     if (IS_TOSPACE_AID(aid))
657 :     targetGen = TOSPACE_GEN(aid);
658 :     else
659 :     targetGen = EXTRACT_GEN(aid);
660 :     }
661 :     #else
662 :     targetGen = EXTRACT_GEN(ADDR_TO_PAGEID(bibop, w));
663 :     #endif
664 :     }
665 :     #ifndef BIT_CARDS
666 :     if (targetGen < cardMark)
667 :     cardMark = targetGen;
668 :     #else
669 :     if (targetGen < thisGen) {
670 :     /* the forwarded object is in a younger generation */
671 :     MARK_CARD(cm, p);
672 :     /* finish the card up quickly */
673 :     for (p++; p < stop; p++) {
674 :     MajorGC_CheckWord(heap, bibop, maxAid, p);
675 :     }
676 :     break;
677 :     }
678 :     #endif
679 :     }
680 :     #ifdef TOSPACE_ID
681 :     else if (IS_TOSPACE_AID(arena_id)) {
682 :     Die ("Sweep Arrays: TOSPACE reference: %#x (%#x) --> %#x\n",
683 :     p, ADDR_TO_PAGEID(bibop, p), w);
684 :     }
685 :     #endif
686 :     }
687 :     p++;
688 :     } /* end of while */
689 :     #ifndef BIT_CARDS
690 :     if (cardMark < thisGen)
691 :     MARK_CARD(cm, cardStart, cardMark);
692 :     #endif
693 :     } /* end of while */
694 :     tosp->sweep_nextw = p;
695 :    
696 :     return TRUE;
697 :    
698 :     } /* end of MajorGC_SweepToSpArrays */
699 :    
700 :    
701 :     /* MajorGC_ForwardObj:
702 :     *
703 :     * Forward an object.
704 :     */
705 :     PVT ml_val_t MajorGC_ForwardObj (heap_t *heap, aid_t maxAid, ml_val_t v, aid_t id)
706 :     {
707 :     ml_val_t *obj = PTR_MLtoC(ml_val_t, v);
708 :     ml_val_t *obj_start, *new_obj;
709 :     ml_val_t desc;
710 :     Word_t len;
711 :     arena_t *arena;
712 :    
713 :     switch (EXTRACT_OBJC(id)) {
714 :     case OBJC_record: {
715 :     for (obj_start = obj; !isDESC(desc = obj_start[-1]); obj_start--)
716 :     continue;
717 :     if (desc == DESC_forwarded)
718 :     /* This object has already been forwarded */
719 :     return PTR_CtoML(FOLLOW_FWDOBJ(obj_start, obj));
720 :     len = GET_LEN(desc);
721 :     arena = heap->gen[EXTRACT_GEN(id)-1]->arena[RECORD_INDX];
722 :     if (isOLDER(arena, obj))
723 :     arena = arena->nextGen;
724 :     } break;
725 :    
726 :     case OBJC_pair: {
727 :     ml_val_t w;
728 :    
729 :     obj_start = (ml_val_t *)((Addr_t)obj & ~(PAIR_SZB-1)); /* in case obj is derived */
730 :     w = obj_start[0];
731 :     if (isDESC(w))
732 :     return PTR_CtoML(FOLLOW_FWDPAIR(w, obj_start, obj));
733 :     else {
734 :     /* forward the pair */
735 :     arena = heap->gen[EXTRACT_GEN(id)-1]->arena[PAIR_INDX];
736 :     if (isOLDER(arena, obj))
737 :     arena = arena->nextGen;
738 :     new_obj = arena->nextw;
739 :     arena->nextw += PAIR_SZW;
740 :     new_obj[0] = w;
741 :     new_obj[1] = obj_start[1];
742 :     /* setup the forward pointer in the old pair */
743 :     obj_start[0] = MAKE_PAIR_FP(new_obj);
744 :     return PTR_CtoML(new_obj + (obj - obj_start));
745 :     }
746 :     } break;
747 :    
748 :     case OBJC_string: {
749 :     #ifdef ALIGN_REALDS
750 :     int align = 0;
751 :     #endif
752 :     obj_start = obj;
753 :     desc = obj_start[-1];
754 :     switch (GET_TAG(desc)) {
755 :     case DTAG_forwarded:
756 :     return PTR_CtoML(FOLLOW_FWDOBJ(obj_start, obj));
757 :     case DTAG_string: {
758 :     int nChars = GET_LEN(desc);
759 :     len = BYTES_TO_WORDS(nChars);
760 :     /* include the 0 termination bytes */
761 :     if ((nChars & (WORD_SZB-1)) == 0) len++;
762 :     } break;
763 :     case DTAG_bytearray:
764 :     len = GET_STR_LEN(desc);
765 :     break;
766 :     case DTAG_reald:
767 :     len = REALD_SZW;
768 :     #ifdef ALIGN_REALDS
769 :     align = WORD_SZB;
770 :     #endif
771 :     break;
772 :     case DTAG_realdarray:
773 :     len = GET_REALDARR_LEN(desc);
774 :     #ifdef ALIGN_REALDS
775 :     align = WORD_SZB;
776 :     #endif
777 :     break;
778 :     default:
779 :     Die ("bad string tag %d, obj = %#x, desc = %#x",
780 :     GET_TAG(desc), obj, desc);
781 :     }
782 :     arena = heap->gen[EXTRACT_GEN(id)-1]->arena[STRING_INDX];
783 :     if (isOLDER(arena, obj))
784 :     arena = arena->nextGen;
785 :     #ifdef ALIGN_REALDS
786 :     arena->nextw = (ml_val_t *)(((Addr_t)arena->nextw) | align);
787 :     #endif
788 :     } break;
789 :    
790 :     case OBJC_bigobj: {
791 :     int i;
792 :     bigobj_region_t *region;
793 :     bigobj_desc_t *dp;
794 :     int gen;
795 :    
796 :     MajorGC_ForwardBigObj (heap, EXTRACT_GEN(maxAid), v, id);
797 :     return v;
798 :     }
799 :    
800 :     case OBJC_array: {
801 :     for (obj_start = obj; !isDESC(desc = obj_start[-1]); obj_start--)
802 :     continue;
803 :     switch (GET_TAG(desc)) {
804 :     case DTAG_forwarded:
805 :     /* This object has already been forwarded */
806 :     return PTR_CtoML(FOLLOW_FWDOBJ(obj_start, obj));
807 :     case DTAG_array:
808 :     len = GET_LEN(desc);
809 :     break;
810 :     case DTAG_special:
811 :     return MajorGC_FwdSpecial (heap, maxAid, obj, id, desc);
812 :     break;
813 :     default:
814 :     Die("unknown tag %#x @ %#x in array arena\n",
815 :     GET_TAG(desc), obj_start);
816 :     } /* end of switch */
817 :     arena = heap->gen[EXTRACT_GEN(id)-1]->arena[ARRAY_INDX];
818 :     if (isOLDER(arena, obj))
819 :     arena = arena->nextGen;
820 :     } break;
821 :    
822 :     default:
823 :     Die("unknown object class %d @ %#x", EXTRACT_OBJC(id), obj);
824 :     } /* end of switch */
825 :    
826 :     /* Allocate and initialize a to-space copy of the object */
827 :     new_obj = arena->nextw;
828 :     arena->nextw += (len + 1);
829 :     *new_obj++ = desc;
830 :     ASSERT(arena->nextw <= arena->tospTop);
831 :     COPYLOOP(obj_start, new_obj, len);
832 :    
833 :     /* set up the forward pointer, and return the new object. */
834 :     obj_start[-1] = DESC_forwarded;
835 :     obj_start[0] = (ml_val_t)(Addr_t)new_obj;
836 :     return PTR_CtoML(new_obj + (obj - obj_start));
837 :    
838 :     } /* end of MajorGC_ForwardObj */
839 :    
840 :    
841 :     /* MajorGC_ForwardBigObj:
842 :     *
843 :     * Forward a big-object obj, where id is the BIBOP entry for obj.
844 :     * Return the descriptor for obj.
845 :     */
846 :     PVT bigobj_desc_t *MajorGC_ForwardBigObj (
847 :     heap_t *heap, int maxGen, ml_val_t obj, aid_t id)
848 :     {
849 :     int i, gen;
850 :     bigobj_region_t *region;
851 :     bigobj_desc_t *dp;
852 :    
853 :     BO2_COUNT;
854 :     for (i = BIBOP_ADDR_TO_INDEX(obj); !BO_IS_HDR(id); id = BIBOP[--i])
855 :     continue;
856 :     region = (bigobj_region_t *)BIBOP_INDEX_TO_ADDR(i);
857 :     dp = ADDR_TO_BODESC(region, obj);
858 :     if ((dp->gen <= maxGen) && BO_IS_FROM_SPACE(dp)) {
859 :     BO3_COUNT;
860 :     /* forward the big-object; note that objects in the oldest generation
861 :     * will always be YOUNG, thus will never be promoted.
862 :     */
863 :     if (dp->state == BO_YOUNG)
864 :     dp->state = BO_FORWARD;
865 :     else
866 :     dp->state = BO_PROMOTE;
867 :     }
868 :    
869 :     return dp;
870 :    
871 :     } /* end of MajorGC_ForwardBigObj */
872 :    
873 :    
874 :     /* MajorGC_FwdSpecial:
875 :     *
876 :     * Forward a special object (suspension, weak pointer, ...).
877 :     */
878 :     PVT ml_val_t MajorGC_FwdSpecial (
879 :     heap_t *heap,
880 :     aid_t maxAid,
881 :     ml_val_t *obj,
882 :     aid_t id,
883 :     ml_val_t desc
884 :     )
885 :     {
886 :     gen_t *gen = heap->gen[EXTRACT_GEN(id)-1];
887 :     arena_t *arena = gen->arena[ARRAY_INDX];
888 :     ml_val_t *new_obj;
889 :    
890 :     if (isOLDER(arena, obj))
891 :     arena = arena->nextGen;
892 :    
893 :     /* allocate the new object */
894 :     new_obj = arena->nextw;
895 :     arena->nextw += SPECIAL_SZW; /* all specials are two words */
896 :    
897 :     switch (GET_LEN(desc)) {
898 :     case SPCL_evaled_susp:
899 :     case SPCL_unevaled_susp:
900 :     case SPCL_null_weak:
901 :     *new_obj++ = desc;
902 :     *new_obj = *obj;
903 :     break;
904 :     case SPCL_weak: {
905 :     ml_val_t v = *obj;
906 :     #ifdef DEBUG_WEAK_PTRS
907 :     SayDebug ("MajorGC: weak [%#x ==> %#x] --> %#x", obj, new_obj+1, v);
908 :     #endif
909 :     if (! isBOXED(v)) {
910 :     #ifdef DEBUG_WEAK_PTRS
911 :     SayDebug (" unboxed\n");
912 :     #endif
913 :     /* weak references to unboxed objects are never nullified */
914 :     *new_obj++ = DESC_weak;
915 :     *new_obj = v;
916 :     }
917 :     else {
918 :     aid_t aid = ADDR_TO_PAGEID(BIBOP, v);
919 :     ml_val_t *vp = PTR_MLtoC(ml_val_t, v);
920 :     ml_val_t *v_start, desc;
921 :    
922 :     if (IS_FROM_SPACE(aid, maxAid)) {
923 :     switch (EXTRACT_OBJC(aid)) {
924 :     case OBJC_record:
925 :     case OBJC_string:
926 :     case OBJC_array:
927 :     for (v_start = vp; !isDESC(desc = v_start[-1]); v_start--)
928 :     continue;
929 :     if (desc == DESC_forwarded) {
930 :     /* Reference to an object that has already been forwarded.
931 :     * NOTE: we have to put the pointer to the non-forwarded
932 :     * copy of the object (i.e, v) into the to-space copy
933 :     * of the weak pointer, since the GC has the invariant
934 :     * it never sees to-space pointers during sweeping.
935 :     */
936 :     #ifdef DEBUG_WEAK_PTRS
937 :     SayDebug (" already forwarded to %#x\n", FOLLOW_FWDOBJ(v_start, vp));
938 :     #endif
939 :     *new_obj++ = DESC_weak;
940 :     *new_obj = v;
941 :     }
942 :     else {
943 :     /* the forwarded version of weak objects are threaded
944 :     * via their descriptor fields. We mark the object
945 :     * reference field to make it look like an unboxed value,
946 :     * so that the to-space sweeper does not follow the weak
947 :     * reference.
948 :     */
949 :     #ifdef DEBUG_WEAK_PTRS
950 :     SayDebug (" forward (start = %#x)\n", v_start);
951 :     #endif
952 :     *new_obj = MARK_PTR(PTR_CtoML(gen->heap->weakList));
953 :     gen->heap->weakList = new_obj++;
954 :     *new_obj = MARK_PTR(vp);
955 :     }
956 :     break;
957 :     case OBJC_pair:
958 :     v_start = (ml_val_t *)((Addr_t)vp & ~(PAIR_SZB-1));
959 :     if (isDESC(desc = v_start[0])) {
960 :     /* Reference to a pair that has already been forwarded.
961 :     * NOTE: we have to put the pointer to the non-forwarded
962 :     * copy of the pair (i.e, v) into the to-space copy
963 :     * of the weak pointer, since the GC has the invariant
964 :     * it never sees to-space pointers during sweeping.
965 :     */
966 :     #ifdef DEBUG_WEAK_PTRS
967 :     SayDebug (" (pair) already forwarded to %#x\n", FOLLOW_FWDPAIR(desc, v_start, vp));
968 :     #endif
969 :     *new_obj++ = DESC_weak;
970 :     *new_obj = v;
971 :     }
972 :     else {
973 :     *new_obj = MARK_PTR(PTR_CtoML(gen->heap->weakList));
974 :     gen->heap->weakList = new_obj++;
975 :     *new_obj = MARK_PTR(vp);
976 :     }
977 :     break;
978 :     case OBJC_bigobj:
979 :     Die ("weak big object");
980 :     break;
981 :     }
982 :     }
983 :     else {
984 :     /* reference to an older object */
985 :     #ifdef DEBUG_WEAK_PTRS
986 :     SayDebug (" old object\n");
987 :     #endif
988 :     *new_obj++ = DESC_weak;
989 :     *new_obj = v;
990 :     }
991 :     }
992 :     } break;
993 :     default:
994 :     Die ("strange/unexpected special object @ %#x; desc = %#x\n", obj, desc);
995 :     } /* end of switch */
996 :    
997 :     obj[-1] = DESC_forwarded;
998 :     obj[0] = (ml_val_t)(Addr_t)new_obj;
999 :    
1000 :     return PTR_CtoML(new_obj);
1001 :    
1002 :     } /* end of MajorGC_FwdSpecial */

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