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/minor-gc.c
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


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

1 : monnier 2 /* minor-gc.c
2 :     *
3 :     * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.
4 :     *
5 :     * This is the code for doing minor collections (i.e., collecting the
6 :     * allocation arena).
7 :     */
8 :    
9 :     #include "ml-base.h"
10 :     #include "ml-limits.h"
11 :     #include "ml-state.h"
12 :     #include "ml-values.h"
13 :     #include "ml-objects.h"
14 :     #include "card-map.h"
15 :     #include "heap.h"
16 :     #include "tags.h"
17 :     #include "copy-loop.h"
18 :     #ifdef MP_SUPPORT
19 :     #include "vproc-state.h"
20 :     #endif
21 :    
22 :     #ifdef GC_STATS
23 :     extern long numUpdates;
24 :     extern long numBytesAlloc;
25 :     extern long numBytesCopied;
26 :     #endif
27 :    
28 :     /** store list operations */
29 :     #define STL_nil ML_unit
30 :     #define STL_hd(p) REC_SELPTR(ml_val_t, p, 0)
31 :     #define STL_tl(p) REC_SEL(p, 1)
32 :    
33 :     /* local routines */
34 :     PVT void MinorGC_ScanStoreList (heap_t *heap, ml_val_t stl);
35 :     PVT void MinorGC_SweepToSpace (gen_t *gen1);
36 :     PVT ml_val_t MinorGC_ForwardObj (gen_t *gen1, ml_val_t v);
37 :     PVT ml_val_t MinorGC_FwdSpecial (gen_t *gen1, ml_val_t *obj, ml_val_t desc);
38 :    
39 :     #ifdef VERBOSE
40 :     extern char *ArenaName[];
41 :     #endif
42 :    
43 :     /* Check a word for a allocation space reference */
44 :     #ifndef NO_GC_INLINE
45 :     #define MinorGC_CheckWord(bibop, g1, p) { \
46 :     ml_val_t __w = *(p); \
47 :     if (isBOXED(__w) && (ADDR_TO_PAGEID(bibop, __w) == AID_NEW)) \
48 :     *(p) = MinorGC_ForwardObj(g1, __w); \
49 :     }
50 :     #else
51 :     PVT void MinorGC_CheckWord (bibop_t bibop, gen_t *g1, ml_val_t *p)
52 :     {
53 :     ml_val_t w = *(p);
54 :     if (isBOXED(w)) {
55 :     aid_t aid = ADDR_TO_PAGEID(bibop, w);
56 :     if (aid == AID_NEW)
57 :     *(p) = MinorGC_ForwardObj(g1, w);
58 :     }
59 :     }
60 :     #endif
61 :    
62 :    
63 :     /* MinorGC:
64 :     *
65 :     * Do a collection of the allocation space.
66 :     */
67 :     void MinorGC (ml_state_t *msp, ml_val_t **roots)
68 :     {
69 :     heap_t *heap = msp->ml_heap;
70 :     gen_t *gen1 = heap->gen[0];
71 :     #ifdef GC_STATS
72 :     long nbytesAlloc, nbytesCopied, nUpdates=numUpdates;
73 :     Addr_t gen1Top[NUM_ARENAS];
74 :     int i;
75 :     {
76 :     nbytesAlloc = (Addr_t)(msp->ml_allocPtr) - (Addr_t)(heap->allocBase);
77 :     CNTR_INCR(&(heap->numAlloc), nbytesAlloc);
78 :     for (i = 0; i < NUM_ARENAS; i++)
79 :     gen1Top[i] = (Addr_t)(gen1->arena[i]->nextw);
80 :     }
81 :     #elif defined(VM_STATS)
82 :     {
83 :     Addr_t nbytesAlloc;
84 :     nbytesAlloc = ((Addr_t)(msp->ml_allocPtr) - (Addr_t)(heap->allocBase));
85 :     CNTR_INCR(&(heap->numAlloc), nbytesAlloc);
86 :     }
87 :     #endif
88 :    
89 :     #ifdef VERBOSE
90 :     {
91 :     int i;
92 :     SayDebug ("Generation 1 before MinorGC:\n");
93 :     for (i = 0; i < NUM_ARENAS; i++) {
94 :     SayDebug (" %s: base = %#x, oldTop = %#x, nextw = %#x\n",
95 :     ArenaName[i+1], gen1->arena[i]->tospBase,
96 :     gen1->arena[i]->oldTop, gen1->arena[i]->nextw);
97 :     }
98 :     }
99 :     #endif
100 :    
101 :     /* scan the standard roots */
102 :     {
103 :     ml_val_t *rp;
104 :     bibop_t bibop = BIBOP;
105 :    
106 :     while ((rp = *roots++) != NIL(ml_val_t *)) {
107 :     MinorGC_CheckWord(bibop, gen1, rp);
108 :     }
109 :     }
110 :    
111 :     /* Scan the store list */
112 :     #ifdef MP_SUPPORT
113 :     {
114 :     ml_val_t stl;
115 :     int i;
116 :     ml_state_t *msp;
117 :     vproc_state_t *vsp;
118 :    
119 :     for (i = 0; i < MAX_NUM_PROCS; i++) {
120 :     vsp = VProc[i];
121 :     msp = vsp->vp_state;
122 :     if ((vsp->vp_mpState == MP_PROC_RUNNING)
123 :     && ((stl = msp->ml_storePtr) != STL_nil)) {
124 :     MinorGC_ScanStoreList (heap, stl);
125 :     msp->ml_storePtr = STL_nil;
126 :     }
127 :     }
128 :     }
129 :     #else
130 :     {
131 :     ml_val_t stl = msp->ml_storePtr;
132 :     if (stl != STL_nil) {
133 :     MinorGC_ScanStoreList (heap, stl);
134 :     msp->ml_storePtr = STL_nil;
135 :     }
136 :     }
137 :     #endif
138 :    
139 :     /* Sweep the first generation to-space */
140 :     MinorGC_SweepToSpace (gen1);
141 :     heap->numMinorGCs++;
142 :    
143 :     /* Handle weak pointers */
144 :     if (heap->weakList != NIL(ml_val_t *))
145 :     ScanWeakPtrs (heap);
146 :    
147 :     #ifdef VERBOSE
148 :     {
149 :     int i;
150 :     SayDebug ("Generation 1 after MinorGC:\n");
151 :     for (i = 0; i < NUM_ARENAS; i++) {
152 :     SayDebug (" %s: base = %#x, oldTop = %#x, nextw = %#x\n",
153 :     ArenaName[i+1], gen1->arena[i]->tospBase,
154 :     gen1->arena[i]->oldTop, gen1->arena[i]->nextw);
155 :     }
156 :     }
157 :     #endif
158 :    
159 :     #ifdef GC_STATS
160 :     {
161 :     int nbytes;
162 :    
163 :     nbytesCopied = 0;
164 :     for (i = 0; i < NUM_ARENAS; i++) {
165 :     nbytes = ((Word_t)(gen1->arena[i]->nextw) - gen1Top[i]);
166 :     nbytesCopied += nbytes;
167 :     CNTR_INCR(&(heap->numCopied[0][i]), nbytes);
168 :     }
169 :    
170 :     numBytesAlloc += nbytesAlloc;
171 :     numBytesCopied += nbytesCopied;
172 :     #ifdef XXX
173 :     SayDebug ("Minor GC: %d/%d (%5.2f%%) bytes copied; %d updates\n",
174 :     nbytesCopied, nbytesAlloc,
175 :     (nbytesAlloc ? (double)(100*nbytesCopied)/(double)nbytesAlloc : 0.0),
176 :     numUpdates-nUpdates);
177 :     #endif
178 :     }
179 :     #endif
180 :    
181 : monnier 223 #ifdef CHECK_HEAP
182 :     CheckHeap(heap, 1);
183 :     #endif
184 :    
185 : monnier 2 } /* end of MinorGC. */
186 :    
187 :    
188 :     /* MinorGC_ScanStoreList:
189 :     *
190 :     * Scan the store list. The store list pointer (stl) is guaranteed to
191 :     * be non-null.
192 :     */
193 :     PVT void MinorGC_ScanStoreList (heap_t *heap, ml_val_t stl)
194 :     {
195 :     ml_val_t *addr, w;
196 :     gen_t *gen1 = heap->gen[0];
197 :     bibop_t bibop = BIBOP;
198 :     #ifdef GC_STATS
199 :     int nUpdates = 0;
200 :     #endif
201 :    
202 :     /* Scan the store list */
203 :     do {
204 :     #ifdef GC_STATS
205 :     nUpdates++;
206 :     #endif
207 :     addr = STL_hd(stl);
208 :     stl = STL_tl(stl);
209 :     w = *addr;
210 :     if (isBOXED(w)) {
211 :     aid_t srcId = ADDR_TO_PAGEID(bibop, addr);
212 :     /* We can ignore updates to objects in new-space, and to references
213 :     * in the runtime system references (ie, UNMAPPED)
214 :     */
215 :     if ((srcId != AID_NEW) && (! isUNMAPPED(srcId))) {
216 :     /* srcGen is the generation of the updated cell; dstGen is the
217 :     * generation of the object that the cell points to.
218 :     */
219 :     int srcGen = EXTRACT_GEN(srcId);
220 :     aid_t dstId = ADDR_TO_PAGEID(bibop, w);
221 :     int dstGen = EXTRACT_GEN(dstId);
222 :    
223 :     if (IS_BIGOBJ_AID(dstId)) {
224 :     int i;
225 :     bigobj_region_t *region;
226 :     bigobj_desc_t *dp;
227 :     if (dstGen >= srcGen)
228 :     continue;
229 :     for (i = BIBOP_ADDR_TO_INDEX(w); !BO_IS_HDR(dstId); dstId = BIBOP[--i])
230 :     continue;
231 :     region = (bigobj_region_t *)BIBOP_INDEX_TO_ADDR(i);
232 :     dp = ADDR_TO_BODESC(region, w);
233 :     dstGen = dp->gen;
234 :     }
235 :     else {
236 :     if (dstGen == ALLOC_GEN) {
237 :     /* The refered to object is in allocation space, and will be
238 :     * forwarded to the first generation.
239 :     */
240 :     dstGen = 1;
241 :     *addr = MinorGC_ForwardObj(gen1, w);
242 :     }
243 :     }
244 :     if (srcGen > dstGen) {
245 :     /* mark the card containing "addr" */
246 :     #ifndef BIT_CARDS
247 :     MARK_CARD(heap->gen[srcGen-1]->dirty, addr, dstGen);
248 :     #else
249 :     MARK_CARD(heap->gen[srcGen-1]->dirty, addr);
250 :     #endif
251 :     }
252 :     }
253 :     }
254 :     } while (stl != STL_nil);
255 :    
256 :     #ifdef GC_STATS
257 :     numUpdates += nUpdates;
258 :     #endif
259 :    
260 :     } /* end MinorGC_ScanStoreList */
261 :    
262 :    
263 :     /* MinorGC_SweepToSpace:
264 :     *
265 :     * Sweep the first generation's to-space. Note, that since there are
266 :     * no younger objects, we don't have to do anything special for the
267 :     * array space.
268 :     */
269 :     PVT void MinorGC_SweepToSpace (gen_t *gen1)
270 :     {
271 :     bibop_t bibop = BIBOP;
272 :     bool_t swept;
273 :    
274 :     #define MinorGC_SweepToSpArena(indx) { \
275 :     arena_t *__ap = gen1->arena[(indx)]; \
276 :     ml_val_t *__p, *__q; \
277 :     __p = __ap->sweep_nextw; \
278 :     if (__p < __ap->nextw) { \
279 :     swept = TRUE; \
280 :     do { \
281 :     for (__q = __ap->nextw; __p < __q; __p++) \
282 :     MinorGC_CheckWord(bibop, gen1, __p); \
283 :     } while (__q != __ap->nextw); \
284 :     __ap->sweep_nextw = __q; \
285 :     } \
286 :     } /* MinorGC_SweepToSpArena */
287 :    
288 :     do {
289 :     swept = FALSE;
290 :    
291 :     /* Sweep the record, pair and array arenas */
292 :     MinorGC_SweepToSpArena(RECORD_INDX);
293 :     MinorGC_SweepToSpArena(PAIR_INDX);
294 :     MinorGC_SweepToSpArena(ARRAY_INDX);
295 :    
296 :     } while (swept);
297 :    
298 :     } /* end of MinorGC_SweepToSpace. */
299 :    
300 :     /* MinorGC_ForwardObj:
301 :     *
302 :     * Forward an object from the allocation space to the first generation.
303 :     */
304 :     PVT ml_val_t MinorGC_ForwardObj (gen_t *gen1, ml_val_t v)
305 :     {
306 :     ml_val_t *obj = PTR_MLtoC(ml_val_t, v);
307 : monnier 223 ml_val_t *new_obj, desc;
308 : monnier 2 Word_t len;
309 :     arena_t *arena;
310 :    
311 : monnier 223 desc = obj[-1];
312 : monnier 2 switch (GET_TAG(desc)) {
313 :     case DTAG_record:
314 :     len = GET_LEN(desc);
315 :     #ifdef NO_PAIR_STRIP
316 :     arena = gen1->arena[RECORD_INDX];
317 :     #else
318 : monnier 223 if (len == 2) {
319 :     arena = gen1->arena[PAIR_INDX];
320 :     new_obj = arena->nextw;
321 :     arena->nextw += 2;
322 :     new_obj[0] = obj[0];
323 :     new_obj[1] = obj[1];
324 :     /* setup the forward pointer in the old pair */
325 :     obj[-1] = DESC_forwarded;
326 :     obj[0] = (ml_val_t)(Addr_t)new_obj;
327 :     return PTR_CtoML(new_obj);
328 :     }
329 :     else
330 :     arena = gen1->arena[RECORD_INDX];
331 : monnier 2 #endif
332 : monnier 223 break;
333 :     case DTAG_vec_hdr:
334 :     case DTAG_arr_hdr:
335 :     len = 2;
336 :     arena = gen1->arena[RECORD_INDX];
337 :     break;
338 :     case DTAG_arr_data:
339 : monnier 2 len = GET_LEN(desc);
340 :     arena = gen1->arena[ARRAY_INDX];
341 :     break;
342 : monnier 223 case DTAG_raw32:
343 :     len = GET_LEN(desc);
344 : monnier 2 arena = gen1->arena[STRING_INDX];
345 :     break;
346 : monnier 223 case DTAG_raw64:
347 :     len = GET_LEN(desc);
348 : monnier 2 arena = gen1->arena[STRING_INDX];
349 :     #ifdef ALIGN_REALDS
350 : monnier 223 # ifdef CHECK_HEAP
351 :     if (((Addr_t)arena->nextw & WORD_SZB) == 0) {
352 :     *(arena->nextw) = (ml_val_t)0;
353 :     arena->nextw++;
354 :     }
355 :     # else
356 : monnier 2 arena->nextw = (ml_val_t *)(((Addr_t)arena->nextw) | WORD_SZB);
357 : monnier 223 # endif
358 : monnier 2 #endif
359 :     break;
360 : monnier 223 case DTAG_special:
361 :     return MinorGC_FwdSpecial (gen1, obj, desc);
362 :     case DTAG_forward:
363 :     return PTR_CtoML(FOLLOW_FWDOBJ(obj));
364 : monnier 2 default:
365 : monnier 223 Die ("bad object tag %d, obj = %#x, desc = %#x", GET_TAG(desc), obj, desc);
366 : monnier 2 } /* end of switch */
367 :    
368 :     /* Allocate and initialize a to-space copy of the object */
369 :     new_obj = arena->nextw;
370 :     arena->nextw += (len + 1);
371 :     *new_obj++ = desc;
372 :     ASSERT(arena->nextw <= arena->tospTop);
373 :    
374 : monnier 223 COPYLOOP(obj, new_obj, len);
375 : monnier 2
376 :     /* set up the forward pointer, and return the new object. */
377 : monnier 223 obj[-1] = DESC_forwarded;
378 :     obj[0] = (ml_val_t)(Addr_t)new_obj;
379 :    
380 : monnier 106 return PTR_CtoML(new_obj);
381 : monnier 2
382 :     } /* end of MinorGC_ForwardObj */
383 :    
384 :    
385 :     /* MinorGC_FwdSpecial:
386 :     *
387 :     * Forward a special object (suspension, weak pointer, ...).
388 :     */
389 :     PVT ml_val_t MinorGC_FwdSpecial (gen_t *gen1, ml_val_t *obj, ml_val_t desc)
390 :     {
391 :     arena_t *arena = gen1->arena[ARRAY_INDX];
392 :     ml_val_t *new_obj = arena->nextw;
393 :    
394 :     arena->nextw += SPECIAL_SZW; /* all specials are two words */
395 :    
396 :     switch (GET_LEN(desc)) {
397 :     case SPCL_evaled_susp:
398 :     case SPCL_unevaled_susp:
399 :     *new_obj++ = desc;
400 :     *new_obj = *obj;
401 :     break;
402 :     case SPCL_weak: {
403 :     ml_val_t v = *obj;
404 :     #ifdef DEBUG_WEAK_PTRS
405 :     SayDebug ("MinorGC: weak [%#x ==> %#x] --> %#x", obj, new_obj+1, v);
406 :     #endif
407 :     if (! isBOXED(v)) {
408 :     #ifdef DEBUG_WEAK_PTRS
409 :     SayDebug (" unboxed\n");
410 :     #endif
411 :     /* weak references to unboxed objects are never nullified */
412 :     *new_obj++ = DESC_weak;
413 :     *new_obj = v;
414 :     }
415 :     else {
416 :     aid_t aid = ADDR_TO_PAGEID(BIBOP, v);
417 :     ml_val_t *vp = PTR_MLtoC(ml_val_t, v);
418 : monnier 223 ml_val_t desc;
419 : monnier 2
420 :     if (aid == AID_NEW) {
421 : monnier 223 if (vp[-1] == DESC_forwarded) {
422 : monnier 2 /* Reference to an object that has already been forwarded.
423 :     * NOTE: we have to put the pointer to the non-forwarded
424 :     * copy of the object (i.e, v) into the to-space copy
425 :     * of the weak pointer, since the GC has the invariant
426 :     * it never sees to-space pointers during sweeping.
427 :     */
428 :     #ifdef DEBUG_WEAK_PTRS
429 : monnier 223 SayDebug (" already forwarded to %#x\n", PTR_CtoML(FOLLOW_FWDOBJ(vp)));
430 : monnier 2 #endif
431 :     *new_obj++ = DESC_weak;
432 :     *new_obj = v;
433 :     }
434 :     else {
435 :     /* the forwarded version of weak objects are threaded
436 :     * via their descriptor fields. We mark the object
437 :     * reference field to make it look like an unboxed value,
438 :     * so that the to-space sweeper does not follow the weak
439 :     * reference.
440 :     */
441 :     #ifdef DEBUG_WEAK_PTRS
442 :     SayDebug (" forward\n");
443 :     #endif
444 :     *new_obj = MARK_PTR(PTR_CtoML(gen1->heap->weakList));
445 :     gen1->heap->weakList = new_obj++;
446 :     *new_obj = MARK_PTR(vp);
447 :     }
448 :     }
449 :     else {
450 :     /* reference to an older object */
451 :     #ifdef DEBUG_WEAK_PTRS
452 :     SayDebug (" old object\n");
453 :     #endif
454 :     *new_obj++ = DESC_weak;
455 :     *new_obj = v;
456 :     }
457 :     }
458 :     } break;
459 :     case SPCL_null_weak: /* shouldn't happen in the allocation arena */
460 :     default:
461 :     Die ("strange/unexpected special object @ %#x; desc = %#x\n", obj, desc);
462 :     } /* end of switch */
463 :    
464 :     obj[-1] = DESC_forwarded;
465 :     obj[0] = (ml_val_t)(Addr_t)new_obj;
466 :    
467 :     return PTR_CtoML(new_obj);
468 :    
469 :     } /* end of MinorGC_FwdSpecial */

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