Annotation of OpenXM_contrib2/asir2000/gc/mark.c, Revision 1.1.1.1
1.1 noro 1:
2: /*
3: * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
4: * Copyright (c) 1991-1995 by Xerox Corporation. All rights reserved.
5: *
6: * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
7: * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
8: *
9: * Permission is hereby granted to use or copy this program
10: * for any purpose, provided the above notices are retained on all copies.
11: * Permission to modify the code and to distribute modified code is granted,
12: * provided the above notices are retained, and a notice that the code was
13: * modified is included with the above copyright notice.
14: *
15: */
16:
17:
18: # include <stdio.h>
19: # include "gc_priv.h"
20: # include "gc_mark.h"
21:
22: /* We put this here to minimize the risk of inlining. */
23: /*VARARGS*/
24: #ifdef __WATCOMC__
25: void GC_noop(void *p, ...) {}
26: #else
27: void GC_noop() {}
28: #endif
29:
30: /* Single argument version, robust against whole program analysis. */
31: void GC_noop1(x)
32: word x;
33: {
34: static VOLATILE word sink;
35:
36: sink = x;
37: }
38:
39: /* mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0} -- declared in gc_priv.h */
40:
41: word GC_n_mark_procs = 0;
42:
43: /* Initialize GC_obj_kinds properly and standard free lists properly. */
44: /* This must be done statically since they may be accessed before */
45: /* GC_init is called. */
46: /* It's done here, since we need to deal with mark descriptors. */
47: struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
48: /* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */,
49: 0 | DS_LENGTH, FALSE, FALSE },
50: /* NORMAL */ { &GC_objfreelist[0], 0,
51: # if defined(ADD_BYTE_AT_END) && ALIGNMENT > DS_TAGS
52: (word)(-ALIGNMENT) | DS_LENGTH,
53: # else
54: 0 | DS_LENGTH,
55: # endif
56: TRUE /* add length to descr */, TRUE },
57: /* UNCOLLECTABLE */
58: { &GC_uobjfreelist[0], 0,
59: 0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
60: # ifdef ATOMIC_UNCOLLECTABLE
61: /* AUNCOLLECTABLE */
62: { &GC_auobjfreelist[0], 0,
63: 0 | DS_LENGTH, FALSE /* add length to descr */, FALSE },
64: # endif
65: # ifdef STUBBORN_ALLOC
66: /*STUBBORN*/ { &GC_sobjfreelist[0], 0,
67: 0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
68: # endif
69: };
70:
71: # ifdef ATOMIC_UNCOLLECTABLE
72: # ifdef STUBBORN_ALLOC
73: int GC_n_kinds = 5;
74: # else
75: int GC_n_kinds = 4;
76: # endif
77: # else
78: # ifdef STUBBORN_ALLOC
79: int GC_n_kinds = 4;
80: # else
81: int GC_n_kinds = 3;
82: # endif
83: # endif
84:
85:
86: # ifndef INITIAL_MARK_STACK_SIZE
87: # define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
88: /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a */
89: /* multiple of HBLKSIZE. */
90: # endif
91:
92: /*
93: * Limits of stack for GC_mark routine.
94: * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
95: * need to be marked from.
96: */
97:
98: word GC_n_rescuing_pages; /* Number of dirty pages we marked from */
99: /* excludes ptrfree pages, etc. */
100:
101: mse * GC_mark_stack;
102:
103: word GC_mark_stack_size = 0;
104:
105: mse * GC_mark_stack_top;
106:
107: static struct hblk * scan_ptr;
108:
109: mark_state_t GC_mark_state = MS_NONE;
110:
111: GC_bool GC_mark_stack_too_small = FALSE;
112:
113: GC_bool GC_objects_are_marked = FALSE; /* Are there collectable marked */
114: /* objects in the heap? */
115:
116: /* Is a collection in progress? Note that this can return true in the */
117: /* nonincremental case, if a collection has been abandoned and the */
118: /* mark state is now MS_INVALID. */
119: GC_bool GC_collection_in_progress()
120: {
121: return(GC_mark_state != MS_NONE);
122: }
123:
124: /* clear all mark bits in the header */
125: void GC_clear_hdr_marks(hhdr)
126: register hdr * hhdr;
127: {
128: BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
129: }
130:
131: /* Set all mark bits in the header. Used for uncollectable blocks. */
132: void GC_set_hdr_marks(hhdr)
133: register hdr * hhdr;
134: {
135: register int i;
136:
137: for (i = 0; i < MARK_BITS_SZ; ++i) {
138: hhdr -> hb_marks[i] = ONES;
139: }
140: }
141:
142: /*
143: * Clear all mark bits associated with block h.
144: */
145: /*ARGSUSED*/
146: static void clear_marks_for_block(h, dummy)
147: struct hblk *h;
148: word dummy;
149: {
150: register hdr * hhdr = HDR(h);
151:
152: if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return;
153: /* Mark bit for these is cleared only once the object is */
154: /* explicitly deallocated. This either frees the block, or */
155: /* the bit is cleared once the object is on the free list. */
156: GC_clear_hdr_marks(hhdr);
157: }
158:
159: /* Slow but general routines for setting/clearing/asking about mark bits */
160: void GC_set_mark_bit(p)
161: ptr_t p;
162: {
163: register struct hblk *h = HBLKPTR(p);
164: register hdr * hhdr = HDR(h);
165: register int word_no = (word *)p - (word *)h;
166:
167: set_mark_bit_from_hdr(hhdr, word_no);
168: }
169:
170: void GC_clear_mark_bit(p)
171: ptr_t p;
172: {
173: register struct hblk *h = HBLKPTR(p);
174: register hdr * hhdr = HDR(h);
175: register int word_no = (word *)p - (word *)h;
176:
177: clear_mark_bit_from_hdr(hhdr, word_no);
178: }
179:
180: GC_bool GC_is_marked(p)
181: ptr_t p;
182: {
183: register struct hblk *h = HBLKPTR(p);
184: register hdr * hhdr = HDR(h);
185: register int word_no = (word *)p - (word *)h;
186:
187: return(mark_bit_from_hdr(hhdr, word_no));
188: }
189:
190:
191: /*
192: * Clear mark bits in all allocated heap blocks. This invalidates
193: * the marker invariant, and sets GC_mark_state to reflect this.
194: * (This implicitly starts marking to reestablish the invariant.)
195: */
196: void GC_clear_marks()
197: {
198: GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
199: GC_objects_are_marked = FALSE;
200: GC_mark_state = MS_INVALID;
201: scan_ptr = 0;
202: # ifdef GATHERSTATS
203: /* Counters reflect currently marked objects: reset here */
204: GC_composite_in_use = 0;
205: GC_atomic_in_use = 0;
206: # endif
207:
208: }
209:
210: /* Initiate a garbage collection. Initiates a full collection if the */
211: /* mark state is invalid. */
212: /*ARGSUSED*/
213: void GC_initiate_gc()
214: {
215: if (GC_dirty_maintained) GC_read_dirty();
216: # ifdef STUBBORN_ALLOC
217: GC_read_changed();
218: # endif
219: # ifdef CHECKSUMS
220: {
221: extern void GC_check_dirty();
222:
223: if (GC_dirty_maintained) GC_check_dirty();
224: }
225: # endif
226: # ifdef GATHERSTATS
227: GC_n_rescuing_pages = 0;
228: # endif
229: if (GC_mark_state == MS_NONE) {
230: GC_mark_state = MS_PUSH_RESCUERS;
231: } else if (GC_mark_state != MS_INVALID) {
232: ABORT("unexpected state");
233: } /* else this is really a full collection, and mark */
234: /* bits are invalid. */
235: scan_ptr = 0;
236: }
237:
238:
239: static void alloc_mark_stack();
240:
241: /* Perform a small amount of marking. */
242: /* We try to touch roughly a page of memory. */
243: /* Return TRUE if we just finished a mark phase. */
244: /* Cold_gc_frame is an address inside a GC frame that */
245: /* remains valid until all marking is complete. */
246: /* A zero value indicates that it's OK to miss some */
247: /* register values. */
248: GC_bool GC_mark_some(cold_gc_frame)
249: ptr_t cold_gc_frame;
250: {
251: switch(GC_mark_state) {
252: case MS_NONE:
253: return(FALSE);
254:
255: case MS_PUSH_RESCUERS:
256: if (GC_mark_stack_top
257: >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
258: GC_mark_from_mark_stack();
259: return(FALSE);
260: } else {
261: scan_ptr = GC_push_next_marked_dirty(scan_ptr);
262: if (scan_ptr == 0) {
263: # ifdef PRINTSTATS
264: GC_printf1("Marked from %lu dirty pages\n",
265: (unsigned long)GC_n_rescuing_pages);
266: # endif
267: GC_push_roots(FALSE, cold_gc_frame);
268: GC_objects_are_marked = TRUE;
269: if (GC_mark_state != MS_INVALID) {
270: GC_mark_state = MS_ROOTS_PUSHED;
271: }
272: }
273: }
274: return(FALSE);
275:
276: case MS_PUSH_UNCOLLECTABLE:
277: if (GC_mark_stack_top
278: >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
279: GC_mark_from_mark_stack();
280: return(FALSE);
281: } else {
282: scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
283: if (scan_ptr == 0) {
284: GC_push_roots(TRUE, cold_gc_frame);
285: GC_objects_are_marked = TRUE;
286: if (GC_mark_state != MS_INVALID) {
287: GC_mark_state = MS_ROOTS_PUSHED;
288: }
289: }
290: }
291: return(FALSE);
292:
293: case MS_ROOTS_PUSHED:
294: if (GC_mark_stack_top >= GC_mark_stack) {
295: GC_mark_from_mark_stack();
296: return(FALSE);
297: } else {
298: GC_mark_state = MS_NONE;
299: if (GC_mark_stack_too_small) {
300: alloc_mark_stack(2*GC_mark_stack_size);
301: }
302: return(TRUE);
303: }
304:
305: case MS_INVALID:
306: case MS_PARTIALLY_INVALID:
307: if (!GC_objects_are_marked) {
308: GC_mark_state = MS_PUSH_UNCOLLECTABLE;
309: return(FALSE);
310: }
311: if (GC_mark_stack_top >= GC_mark_stack) {
312: GC_mark_from_mark_stack();
313: return(FALSE);
314: }
315: if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {
316: /* About to start a heap scan for marked objects. */
317: /* Mark stack is empty. OK to reallocate. */
318: if (GC_mark_stack_too_small) {
319: alloc_mark_stack(2*GC_mark_stack_size);
320: }
321: GC_mark_state = MS_PARTIALLY_INVALID;
322: }
323: scan_ptr = GC_push_next_marked(scan_ptr);
324: if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
325: GC_push_roots(TRUE, cold_gc_frame);
326: GC_objects_are_marked = TRUE;
327: if (GC_mark_state != MS_INVALID) {
328: GC_mark_state = MS_ROOTS_PUSHED;
329: }
330: }
331: return(FALSE);
332: default:
333: ABORT("GC_mark_some: bad state");
334: return(FALSE);
335: }
336: }
337:
338:
339: GC_bool GC_mark_stack_empty()
340: {
341: return(GC_mark_stack_top < GC_mark_stack);
342: }
343:
344: #ifdef PROF_MARKER
345: word GC_prof_array[10];
346: # define PROF(n) GC_prof_array[n]++
347: #else
348: # define PROF(n)
349: #endif
350:
351: /* Given a pointer to someplace other than a small object page or the */
352: /* first page of a large object, return a pointer either to the */
353: /* start of the large object or NIL. */
354: /* In the latter case black list the address current. */
355: /* Returns NIL without black listing if current points to a block */
356: /* with IGNORE_OFF_PAGE set. */
357: /*ARGSUSED*/
358: # ifdef PRINT_BLACK_LIST
359: word GC_find_start(current, hhdr, source)
360: word source;
361: # else
362: word GC_find_start(current, hhdr)
363: # define source 0
364: # endif
365: register word current;
366: register hdr * hhdr;
367: {
368: # ifdef ALL_INTERIOR_POINTERS
369: if (hhdr != 0) {
370: register word orig = current;
371:
372: current = (word)HBLKPTR(current) + HDR_BYTES;
373: do {
374: current = current - HBLKSIZE*(word)hhdr;
375: hhdr = HDR(current);
376: } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
377: /* current points to the start of the large object */
378: if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
379: if ((word *)orig - (word *)current
380: >= (ptrdiff_t)(hhdr->hb_sz)) {
381: /* Pointer past the end of the block */
382: GC_ADD_TO_BLACK_LIST_NORMAL(orig, source);
383: return(0);
384: }
385: return(current);
386: } else {
387: GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
388: return(0);
389: }
390: # else
391: GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
392: return(0);
393: # endif
394: # undef source
395: }
396:
397: void GC_invalidate_mark_state()
398: {
399: GC_mark_state = MS_INVALID;
400: GC_mark_stack_top = GC_mark_stack-1;
401: }
402:
403: mse * GC_signal_mark_stack_overflow(msp)
404: mse * msp;
405: {
406: GC_mark_state = MS_INVALID;
407: GC_mark_stack_too_small = TRUE;
408: # ifdef PRINTSTATS
409: GC_printf1("Mark stack overflow; current size = %lu entries\n",
410: GC_mark_stack_size);
411: # endif
412: return(msp-INITIAL_MARK_STACK_SIZE/8);
413: }
414:
415:
416: /*
417: * Mark objects pointed to by the regions described by
418: * mark stack entries between GC_mark_stack and GC_mark_stack_top,
419: * inclusive. Assumes the upper limit of a mark stack entry
420: * is never 0. A mark stack entry never has size 0.
421: * We try to traverse on the order of a hblk of memory before we return.
422: * Caller is responsible for calling this until the mark stack is empty.
423: */
424: void GC_mark_from_mark_stack()
425: {
426: mse * GC_mark_stack_reg = GC_mark_stack;
427: mse * GC_mark_stack_top_reg = GC_mark_stack_top;
428: mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
429: int credit = HBLKSIZE; /* Remaining credit for marking work */
430: register word * current_p; /* Pointer to current candidate ptr. */
431: register word current; /* Candidate pointer. */
432: register word * limit; /* (Incl) limit of current candidate */
433: /* range */
434: register word descr;
435: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
436: register ptr_t least_ha = GC_least_plausible_heap_addr;
437: # define SPLIT_RANGE_WORDS 128 /* Must be power of 2. */
438:
439: GC_objects_are_marked = TRUE;
440: # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
441: while (GC_mark_stack_top_reg >= GC_mark_stack_reg && credit >= 0) {
442: # else
443: while ((((ptr_t)GC_mark_stack_top_reg - (ptr_t)GC_mark_stack_reg) | credit)
444: >= 0) {
445: # endif
446: current_p = GC_mark_stack_top_reg -> mse_start;
447: retry:
448: descr = GC_mark_stack_top_reg -> mse_descr;
449: if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | DS_TAGS)) {
450: word tag = descr & DS_TAGS;
451:
452: switch(tag) {
453: case DS_LENGTH:
454: /* Large length. */
455: /* Process part of the range to avoid pushing too much on the */
456: /* stack. */
457: GC_mark_stack_top_reg -> mse_start =
458: limit = current_p + SPLIT_RANGE_WORDS-1;
459: GC_mark_stack_top_reg -> mse_descr -=
460: WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
461: /* Make sure that pointers overlapping the two ranges are */
462: /* considered. */
463: limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
464: break;
465: case DS_BITMAP:
466: GC_mark_stack_top_reg--;
467: descr &= ~DS_TAGS;
468: credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
469: while (descr != 0) {
470: if ((signed_word)descr < 0) {
471: current = *current_p;
472: if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
473: PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit,
474: current_p, exit1);
475: }
476: }
477: descr <<= 1;
478: ++ current_p;
479: }
480: continue;
481: case DS_PROC:
482: GC_mark_stack_top_reg--;
483: credit -= PROC_BYTES;
484: GC_mark_stack_top_reg =
485: (*PROC(descr))
486: (current_p, GC_mark_stack_top_reg,
487: mark_stack_limit, ENV(descr));
488: continue;
489: case DS_PER_OBJECT:
490: GC_mark_stack_top_reg -> mse_descr =
491: *(word *)((ptr_t)current_p + descr - tag);
492: goto retry;
493: }
494: } else {
495: GC_mark_stack_top_reg--;
496: limit = (word *)(((ptr_t)current_p) + (word)descr);
497: }
498: /* The simple case in which we're scanning a range. */
499: credit -= (ptr_t)limit - (ptr_t)current_p;
500: limit -= 1;
501: while (current_p <= limit) {
502: current = *current_p;
503: if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
504: PUSH_CONTENTS(current, GC_mark_stack_top_reg,
505: mark_stack_limit, current_p, exit2);
506: }
507: current_p = (word *)((char *)current_p + ALIGNMENT);
508: }
509: }
510: GC_mark_stack_top = GC_mark_stack_top_reg;
511: }
512:
513: /* Allocate or reallocate space for mark stack of size s words */
514: /* May silently fail. */
515: static void alloc_mark_stack(n)
516: word n;
517: {
518: mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct ms_entry));
519:
520: GC_mark_stack_too_small = FALSE;
521: if (GC_mark_stack_size != 0) {
522: if (new_stack != 0) {
523: word displ = (word)GC_mark_stack & (GC_page_size - 1);
524: signed_word size = GC_mark_stack_size * sizeof(struct ms_entry);
525:
526: /* Recycle old space */
527: if (0 != displ) displ = GC_page_size - displ;
528: size = (size - displ) & ~(GC_page_size - 1);
529: if (size > 0) {
530: GC_add_to_heap((struct hblk *)
531: ((word)GC_mark_stack + displ), (word)size);
532: }
533: GC_mark_stack = new_stack;
534: GC_mark_stack_size = n;
535: # ifdef PRINTSTATS
536: GC_printf1("Grew mark stack to %lu frames\n",
537: (unsigned long) GC_mark_stack_size);
538: # endif
539: } else {
540: # ifdef PRINTSTATS
541: GC_printf1("Failed to grow mark stack to %lu frames\n",
542: (unsigned long) n);
543: # endif
544: }
545: } else {
546: if (new_stack == 0) {
547: GC_err_printf0("No space for mark stack\n");
548: EXIT();
549: }
550: GC_mark_stack = new_stack;
551: GC_mark_stack_size = n;
552: }
553: GC_mark_stack_top = GC_mark_stack-1;
554: }
555:
556: void GC_mark_init()
557: {
558: alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
559: }
560:
561: /*
562: * Push all locations between b and t onto the mark stack.
563: * b is the first location to be checked. t is one past the last
564: * location to be checked.
565: * Should only be used if there is no possibility of mark stack
566: * overflow.
567: */
568: void GC_push_all(bottom, top)
569: ptr_t bottom;
570: ptr_t top;
571: {
572: register word length;
573:
574: bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
575: top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
576: if (top == 0 || bottom == top) return;
577: GC_mark_stack_top++;
578: if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
579: ABORT("unexpected mark stack overflow");
580: }
581: length = top - bottom;
582: # if DS_TAGS > ALIGNMENT - 1
583: length += DS_TAGS;
584: length &= ~DS_TAGS;
585: # endif
586: GC_mark_stack_top -> mse_start = (word *)bottom;
587: GC_mark_stack_top -> mse_descr = length;
588: }
589:
590: /*
591: * Analogous to the above, but push only those pages that may have been
592: * dirtied. A block h is assumed dirty if dirty_fn(h) != 0.
593: * We use push_fn to actually push the block.
594: * Will not overflow mark stack if push_fn pushes a small fixed number
595: * of entries. (This is invoked only if push_fn pushes a single entry,
596: * or if it marks each object before pushing it, thus ensuring progress
597: * in the event of a stack overflow.)
598: */
599: void GC_push_dirty(bottom, top, dirty_fn, push_fn)
600: ptr_t bottom;
601: ptr_t top;
602: int (*dirty_fn)(/* struct hblk * h */);
603: void (*push_fn)(/* ptr_t bottom, ptr_t top */);
604: {
605: register struct hblk * h;
606:
607: bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
608: top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
609:
610: if (top == 0 || bottom == top) return;
611: h = HBLKPTR(bottom + HBLKSIZE);
612: if (top <= (ptr_t) h) {
613: if ((*dirty_fn)(h-1)) {
614: (*push_fn)(bottom, top);
615: }
616: return;
617: }
618: if ((*dirty_fn)(h-1)) {
619: (*push_fn)(bottom, (ptr_t)h);
620: }
621: while ((ptr_t)(h+1) <= top) {
622: if ((*dirty_fn)(h)) {
623: if ((word)(GC_mark_stack_top - GC_mark_stack)
624: > 3 * GC_mark_stack_size / 4) {
625: /* Danger of mark stack overflow */
626: (*push_fn)((ptr_t)h, top);
627: return;
628: } else {
629: (*push_fn)((ptr_t)h, (ptr_t)(h+1));
630: }
631: }
632: h++;
633: }
634: if ((ptr_t)h != top) {
635: if ((*dirty_fn)(h)) {
636: (*push_fn)((ptr_t)h, top);
637: }
638: }
639: if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
640: ABORT("unexpected mark stack overflow");
641: }
642: }
643:
644: # ifndef SMALL_CONFIG
645: void GC_push_conditional(bottom, top, all)
646: ptr_t bottom;
647: ptr_t top;
648: int all;
649: {
650: if (all) {
651: if (GC_dirty_maintained) {
652: # ifdef PROC_VDB
653: /* Pages that were never dirtied cannot contain pointers */
654: GC_push_dirty(bottom, top, GC_page_was_ever_dirty, GC_push_all);
655: # else
656: GC_push_all(bottom, top);
657: # endif
658: } else {
659: GC_push_all(bottom, top);
660: }
661: } else {
662: GC_push_dirty(bottom, top, GC_page_was_dirty, GC_push_all);
663: }
664: }
665: #endif
666:
667: # ifdef MSWIN32
668: void __cdecl GC_push_one(p)
669: # else
670: void GC_push_one(p)
671: # endif
672: word p;
673: {
674: GC_PUSH_ONE_STACK(p, 0);
675: }
676:
677: # ifdef __STDC__
678: # define BASE(p) (word)GC_base((void *)(p))
679: # else
680: # define BASE(p) (word)GC_base((char *)(p))
681: # endif
682:
683: /* As above, but argument passed preliminary test. */
684: # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
685: void GC_push_one_checked(p, interior_ptrs, source)
686: ptr_t source;
687: # else
688: void GC_push_one_checked(p, interior_ptrs)
689: # define source 0
690: # endif
691: register word p;
692: register GC_bool interior_ptrs;
693: {
694: register word r;
695: register hdr * hhdr;
696: register int displ;
697:
698: GET_HDR(p, hhdr);
699: if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
700: if (hhdr != 0 && interior_ptrs) {
701: r = BASE(p);
702: hhdr = HDR(r);
703: displ = BYTES_TO_WORDS(HBLKDISPL(r));
704: } else {
705: hhdr = 0;
706: }
707: } else {
708: register map_entry_type map_entry;
709:
710: displ = HBLKDISPL(p);
711: map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
712: if (map_entry == OBJ_INVALID) {
713: # ifndef ALL_INTERIOR_POINTERS
714: if (interior_ptrs) {
715: r = BASE(p);
716: displ = BYTES_TO_WORDS(HBLKDISPL(r));
717: if (r == 0) hhdr = 0;
718: } else {
719: hhdr = 0;
720: }
721: # else
722: /* map already reflects interior pointers */
723: hhdr = 0;
724: # endif
725: } else {
726: displ = BYTES_TO_WORDS(displ);
727: displ -= map_entry;
728: r = (word)((word *)(HBLKPTR(p)) + displ);
729: }
730: }
731: /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
732: /* displ is the word index within the block. */
733: if (hhdr == 0) {
734: if (interior_ptrs) {
735: # ifdef PRINT_BLACK_LIST
736: GC_add_to_black_list_stack(p, source);
737: # else
738: GC_add_to_black_list_stack(p);
739: # endif
740: } else {
741: GC_ADD_TO_BLACK_LIST_NORMAL(p, source);
742: # undef source /* In case we had to define it. */
743: }
744: } else {
745: if (!mark_bit_from_hdr(hhdr, displ)) {
746: set_mark_bit_from_hdr(hhdr, displ);
747: GC_STORE_BACK_PTR(source, (ptr_t)r);
748: PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
749: &(GC_mark_stack[GC_mark_stack_size]));
750: }
751: }
752: }
753:
754: # ifdef TRACE_BUF
755:
756: # define TRACE_ENTRIES 1000
757:
758: struct trace_entry {
759: char * kind;
760: word gc_no;
761: word words_allocd;
762: word arg1;
763: word arg2;
764: } GC_trace_buf[TRACE_ENTRIES];
765:
766: int GC_trace_buf_ptr = 0;
767:
768: void GC_add_trace_entry(char *kind, word arg1, word arg2)
769: {
770: GC_trace_buf[GC_trace_buf_ptr].kind = kind;
771: GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
772: GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
773: GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
774: GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
775: GC_trace_buf_ptr++;
776: if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
777: }
778:
779: void GC_print_trace(word gc_no, GC_bool lock)
780: {
781: int i;
782: struct trace_entry *p;
783:
784: if (lock) LOCK();
785: for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
786: if (i < 0) i = TRACE_ENTRIES-1;
787: p = GC_trace_buf + i;
788: if (p -> gc_no < gc_no || p -> kind == 0) return;
789: printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
790: p -> kind, p -> gc_no, p -> words_allocd,
791: (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
792: }
793: printf("Trace incomplete\n");
794: if (lock) UNLOCK();
795: }
796:
797: # endif /* TRACE_BUF */
798:
799: /*
800: * A version of GC_push_all that treats all interior pointers as valid
801: * and scans the entire region immediately, in case the contents
802: * change.
803: */
804: void GC_push_all_eager(bottom, top)
805: ptr_t bottom;
806: ptr_t top;
807: {
808: word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
809: word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
810: register word *p;
811: register word q;
812: register word *lim;
813: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
814: register ptr_t least_ha = GC_least_plausible_heap_addr;
815: # define GC_greatest_plausible_heap_addr greatest_ha
816: # define GC_least_plausible_heap_addr least_ha
817:
818: if (top == 0) return;
819: /* check all pointers in range and put in push if they appear */
820: /* to be valid. */
821: lim = t - 1 /* longword */;
822: for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
823: q = *p;
824: GC_PUSH_ONE_STACK(q, p);
825: }
826: # undef GC_greatest_plausible_heap_addr
827: # undef GC_least_plausible_heap_addr
828: }
829:
830: #ifndef THREADS
831: /*
832: * A version of GC_push_all that treats all interior pointers as valid
833: * and scans part of the area immediately, to make sure that saved
834: * register values are not lost.
835: * Cold_gc_frame delimits the stack section that must be scanned
836: * eagerly. A zero value indicates that no eager scanning is needed.
837: */
838: void GC_push_all_stack_partially_eager(bottom, top, cold_gc_frame)
839: ptr_t bottom;
840: ptr_t top;
841: ptr_t cold_gc_frame;
842: {
843: # ifdef ALL_INTERIOR_POINTERS
844: # define EAGER_BYTES 1024
845: /* Push the hot end of the stack eagerly, so that register values */
846: /* saved inside GC frames are marked before they disappear. */
847: /* The rest of the marking can be deferred until later. */
848: if (0 == cold_gc_frame) {
849: GC_push_all_stack(bottom, top);
850: return;
851: }
852: # ifdef STACK_GROWS_DOWN
853: GC_push_all_eager(bottom, cold_gc_frame);
854: GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
855: # else /* STACK_GROWS_UP */
856: GC_push_all_eager(cold_gc_frame, top);
857: GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
858: # endif /* STACK_GROWS_UP */
859: # else
860: GC_push_all_eager(bottom, top);
861: # endif
862: # ifdef TRACE_BUF
863: GC_add_trace_entry("GC_push_all_stack", bottom, top);
864: # endif
865: }
866: #endif /* !THREADS */
867:
868: void GC_push_all_stack(bottom, top)
869: ptr_t bottom;
870: ptr_t top;
871: {
872: # ifdef ALL_INTERIOR_POINTERS
873: GC_push_all(bottom, top);
874: # else
875: GC_push_all_eager(bottom, top);
876: # endif
877: }
878:
879: #ifndef SMALL_CONFIG
880: /* Push all objects reachable from marked objects in the given block */
881: /* of size 1 objects. */
882: void GC_push_marked1(h, hhdr)
883: struct hblk *h;
884: register hdr * hhdr;
885: {
886: word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
887: register word *p;
888: word *plim;
889: register int i;
890: register word q;
891: register word mark_word;
892: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
893: register ptr_t least_ha = GC_least_plausible_heap_addr;
894: # define GC_greatest_plausible_heap_addr greatest_ha
895: # define GC_least_plausible_heap_addr least_ha
896:
897: p = (word *)(h->hb_body);
898: plim = (word *)(((word)h) + HBLKSIZE);
899:
900: /* go through all words in block */
901: while( p < plim ) {
902: mark_word = *mark_word_addr++;
903: i = 0;
904: while(mark_word != 0) {
905: if (mark_word & 1) {
906: q = p[i];
907: GC_PUSH_ONE_HEAP(q, p + i);
908: }
909: i++;
910: mark_word >>= 1;
911: }
912: p += WORDSZ;
913: }
914: # undef GC_greatest_plausible_heap_addr
915: # undef GC_least_plausible_heap_addr
916: }
917:
918:
919: #ifndef UNALIGNED
920:
921: /* Push all objects reachable from marked objects in the given block */
922: /* of size 2 objects. */
923: void GC_push_marked2(h, hhdr)
924: struct hblk *h;
925: register hdr * hhdr;
926: {
927: word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
928: register word *p;
929: word *plim;
930: register int i;
931: register word q;
932: register word mark_word;
933: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
934: register ptr_t least_ha = GC_least_plausible_heap_addr;
935: # define GC_greatest_plausible_heap_addr greatest_ha
936: # define GC_least_plausible_heap_addr least_ha
937:
938: p = (word *)(h->hb_body);
939: plim = (word *)(((word)h) + HBLKSIZE);
940:
941: /* go through all words in block */
942: while( p < plim ) {
943: mark_word = *mark_word_addr++;
944: i = 0;
945: while(mark_word != 0) {
946: if (mark_word & 1) {
947: q = p[i];
948: GC_PUSH_ONE_HEAP(q, p + i);
949: q = p[i+1];
950: GC_PUSH_ONE_HEAP(q, p + i);
951: }
952: i += 2;
953: mark_word >>= 2;
954: }
955: p += WORDSZ;
956: }
957: # undef GC_greatest_plausible_heap_addr
958: # undef GC_least_plausible_heap_addr
959: }
960:
961: /* Push all objects reachable from marked objects in the given block */
962: /* of size 4 objects. */
963: /* There is a risk of mark stack overflow here. But we handle that. */
964: /* And only unmarked objects get pushed, so it's not very likely. */
965: void GC_push_marked4(h, hhdr)
966: struct hblk *h;
967: register hdr * hhdr;
968: {
969: word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
970: register word *p;
971: word *plim;
972: register int i;
973: register word q;
974: register word mark_word;
975: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
976: register ptr_t least_ha = GC_least_plausible_heap_addr;
977: # define GC_greatest_plausible_heap_addr greatest_ha
978: # define GC_least_plausible_heap_addr least_ha
979:
980: p = (word *)(h->hb_body);
981: plim = (word *)(((word)h) + HBLKSIZE);
982:
983: /* go through all words in block */
984: while( p < plim ) {
985: mark_word = *mark_word_addr++;
986: i = 0;
987: while(mark_word != 0) {
988: if (mark_word & 1) {
989: q = p[i];
990: GC_PUSH_ONE_HEAP(q, p + i);
991: q = p[i+1];
992: GC_PUSH_ONE_HEAP(q, p + i + 1);
993: q = p[i+2];
994: GC_PUSH_ONE_HEAP(q, p + i + 2);
995: q = p[i+3];
996: GC_PUSH_ONE_HEAP(q, p + i + 3);
997: }
998: i += 4;
999: mark_word >>= 4;
1000: }
1001: p += WORDSZ;
1002: }
1003: # undef GC_greatest_plausible_heap_addr
1004: # undef GC_least_plausible_heap_addr
1005: }
1006:
1007: #endif /* UNALIGNED */
1008:
1009: #endif /* SMALL_CONFIG */
1010:
1011: /* Push all objects reachable from marked objects in the given block */
1012: void GC_push_marked(h, hhdr)
1013: struct hblk *h;
1014: register hdr * hhdr;
1015: {
1016: register int sz = hhdr -> hb_sz;
1017: register word * p;
1018: register int word_no;
1019: register word * lim;
1020: register mse * GC_mark_stack_top_reg;
1021: register mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
1022:
1023: /* Some quick shortcuts: */
1024: {
1025: struct obj_kind *ok = &(GC_obj_kinds[hhdr -> hb_obj_kind]);
1026: if ((0 | DS_LENGTH) == ok -> ok_descriptor
1027: && FALSE == ok -> ok_relocate_descr)
1028: return;
1029: }
1030: if (GC_block_empty(hhdr)/* nothing marked */) return;
1031: # ifdef GATHERSTATS
1032: GC_n_rescuing_pages++;
1033: # endif
1034: GC_objects_are_marked = TRUE;
1035: if (sz > MAXOBJSZ) {
1036: lim = (word *)(h + 1);
1037: } else {
1038: lim = (word *)(h + 1) - sz;
1039: }
1040:
1041: switch(sz) {
1042: # if !defined(SMALL_CONFIG)
1043: case 1:
1044: GC_push_marked1(h, hhdr);
1045: break;
1046: # endif
1047: # if !defined(SMALL_CONFIG) && !defined(UNALIGNED)
1048: case 2:
1049: GC_push_marked2(h, hhdr);
1050: break;
1051: case 4:
1052: GC_push_marked4(h, hhdr);
1053: break;
1054: # endif
1055: default:
1056: GC_mark_stack_top_reg = GC_mark_stack_top;
1057: for (p = (word *)h + HDR_WORDS, word_no = HDR_WORDS; p <= lim;
1058: p += sz, word_no += sz) {
1059: /* This ignores user specified mark procs. This currently */
1060: /* doesn't matter, since marking from the whole object */
1061: /* is always sufficient, and we will eventually use the user */
1062: /* mark proc to avoid any bogus pointers. */
1063: if (mark_bit_from_hdr(hhdr, word_no)) {
1064: /* Mark from fields inside the object */
1065: PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
1066: # ifdef GATHERSTATS
1067: /* Subtract this object from total, since it was */
1068: /* added in twice. */
1069: GC_composite_in_use -= sz;
1070: # endif
1071: }
1072: }
1073: GC_mark_stack_top = GC_mark_stack_top_reg;
1074: }
1075: }
1076:
1077: #ifndef SMALL_CONFIG
1078: /* Test whether any page in the given block is dirty */
1079: GC_bool GC_block_was_dirty(h, hhdr)
1080: struct hblk *h;
1081: register hdr * hhdr;
1082: {
1083: register int sz = hhdr -> hb_sz;
1084:
1085: if (sz < MAXOBJSZ) {
1086: return(GC_page_was_dirty(h));
1087: } else {
1088: register ptr_t p = (ptr_t)h;
1089: sz += HDR_WORDS;
1090: sz = WORDS_TO_BYTES(sz);
1091: while (p < (ptr_t)h + sz) {
1092: if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
1093: p += HBLKSIZE;
1094: }
1095: return(FALSE);
1096: }
1097: }
1098: #endif /* SMALL_CONFIG */
1099:
1100: /* Similar to GC_push_next_marked, but return address of next block */
1101: struct hblk * GC_push_next_marked(h)
1102: struct hblk *h;
1103: {
1104: register hdr * hhdr;
1105:
1106: h = GC_next_used_block(h);
1107: if (h == 0) return(0);
1108: hhdr = HDR(h);
1109: GC_push_marked(h, hhdr);
1110: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1111: }
1112:
1113: #ifndef SMALL_CONFIG
1114: /* Identical to above, but mark only from dirty pages */
1115: struct hblk * GC_push_next_marked_dirty(h)
1116: struct hblk *h;
1117: {
1118: register hdr * hhdr = HDR(h);
1119:
1120: if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
1121: for (;;) {
1122: h = GC_next_used_block(h);
1123: if (h == 0) return(0);
1124: hhdr = HDR(h);
1125: # ifdef STUBBORN_ALLOC
1126: if (hhdr -> hb_obj_kind == STUBBORN) {
1127: if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
1128: break;
1129: }
1130: } else {
1131: if (GC_block_was_dirty(h, hhdr)) break;
1132: }
1133: # else
1134: if (GC_block_was_dirty(h, hhdr)) break;
1135: # endif
1136: h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1137: }
1138: GC_push_marked(h, hhdr);
1139: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1140: }
1141: #endif
1142:
1143: /* Similar to above, but for uncollectable pages. Needed since we */
1144: /* do not clear marks for such pages, even for full collections. */
1145: struct hblk * GC_push_next_marked_uncollectable(h)
1146: struct hblk *h;
1147: {
1148: register hdr * hhdr = HDR(h);
1149:
1150: for (;;) {
1151: h = GC_next_used_block(h);
1152: if (h == 0) return(0);
1153: hhdr = HDR(h);
1154: if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
1155: h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1156: }
1157: GC_push_marked(h, hhdr);
1158: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1159: }
1160:
1161:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to mark.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / gc