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.SAV
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 250 - (view) (download)

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

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