Annotation of OpenXM_contrib2/asir2000/gc5.3/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 = GC_RESERVED_MARK_PROCS;
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: /* The incremental collector actually likes a larger */
91: /* size, since it want to push all marked dirty objs */
92: /* before marking anything new. Currently we let it */
93: /* grow dynamically. */
94: # endif
95:
96: /*
97: * Limits of stack for GC_mark routine.
98: * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
99: * need to be marked from.
100: */
101:
102: word GC_n_rescuing_pages; /* Number of dirty pages we marked from */
103: /* excludes ptrfree pages, etc. */
104:
105: mse * GC_mark_stack;
106:
107: word GC_mark_stack_size = 0;
108:
109: mse * GC_mark_stack_top;
110:
111: static struct hblk * scan_ptr;
112:
113: mark_state_t GC_mark_state = MS_NONE;
114:
115: GC_bool GC_mark_stack_too_small = FALSE;
116:
117: GC_bool GC_objects_are_marked = FALSE; /* Are there collectable marked */
118: /* objects in the heap? */
119:
120: /* Is a collection in progress? Note that this can return true in the */
121: /* nonincremental case, if a collection has been abandoned and the */
122: /* mark state is now MS_INVALID. */
123: GC_bool GC_collection_in_progress()
124: {
125: return(GC_mark_state != MS_NONE);
126: }
127:
128: /* clear all mark bits in the header */
129: void GC_clear_hdr_marks(hhdr)
130: register hdr * hhdr;
131: {
132: BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
133: }
134:
135: /* Set all mark bits in the header. Used for uncollectable blocks. */
136: void GC_set_hdr_marks(hhdr)
137: register hdr * hhdr;
138: {
139: register int i;
140:
141: for (i = 0; i < MARK_BITS_SZ; ++i) {
142: hhdr -> hb_marks[i] = ONES;
143: }
144: }
145:
146: /*
147: * Clear all mark bits associated with block h.
148: */
149: /*ARGSUSED*/
150: static void clear_marks_for_block(h, dummy)
151: struct hblk *h;
152: word dummy;
153: {
154: register hdr * hhdr = HDR(h);
155:
156: if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return;
157: /* Mark bit for these is cleared only once the object is */
158: /* explicitly deallocated. This either frees the block, or */
159: /* the bit is cleared once the object is on the free list. */
160: GC_clear_hdr_marks(hhdr);
161: }
162:
163: /* Slow but general routines for setting/clearing/asking about mark bits */
164: void GC_set_mark_bit(p)
165: ptr_t p;
166: {
167: register struct hblk *h = HBLKPTR(p);
168: register hdr * hhdr = HDR(h);
169: register int word_no = (word *)p - (word *)h;
170:
171: set_mark_bit_from_hdr(hhdr, word_no);
172: }
173:
174: void GC_clear_mark_bit(p)
175: ptr_t p;
176: {
177: register struct hblk *h = HBLKPTR(p);
178: register hdr * hhdr = HDR(h);
179: register int word_no = (word *)p - (word *)h;
180:
181: clear_mark_bit_from_hdr(hhdr, word_no);
182: }
183:
184: GC_bool GC_is_marked(p)
185: ptr_t p;
186: {
187: register struct hblk *h = HBLKPTR(p);
188: register hdr * hhdr = HDR(h);
189: register int word_no = (word *)p - (word *)h;
190:
191: return(mark_bit_from_hdr(hhdr, word_no));
192: }
193:
194:
195: /*
196: * Clear mark bits in all allocated heap blocks. This invalidates
197: * the marker invariant, and sets GC_mark_state to reflect this.
198: * (This implicitly starts marking to reestablish the invariant.)
199: */
200: void GC_clear_marks()
201: {
202: GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
203: GC_objects_are_marked = FALSE;
204: GC_mark_state = MS_INVALID;
205: scan_ptr = 0;
206: # ifdef GATHERSTATS
207: /* Counters reflect currently marked objects: reset here */
208: GC_composite_in_use = 0;
209: GC_atomic_in_use = 0;
210: # endif
211:
212: }
213:
214: /* Initiate a garbage collection. Initiates a full collection if the */
215: /* mark state is invalid. */
216: /*ARGSUSED*/
217: void GC_initiate_gc()
218: {
219: if (GC_dirty_maintained) GC_read_dirty();
220: # ifdef STUBBORN_ALLOC
221: GC_read_changed();
222: # endif
223: # ifdef CHECKSUMS
224: {
225: extern void GC_check_dirty();
226:
227: if (GC_dirty_maintained) GC_check_dirty();
228: }
229: # endif
230: # ifdef GATHERSTATS
231: GC_n_rescuing_pages = 0;
232: # endif
233: if (GC_mark_state == MS_NONE) {
234: GC_mark_state = MS_PUSH_RESCUERS;
235: } else if (GC_mark_state != MS_INVALID) {
236: ABORT("unexpected state");
237: } /* else this is really a full collection, and mark */
238: /* bits are invalid. */
239: scan_ptr = 0;
240: }
241:
242:
243: static void alloc_mark_stack();
244:
245: /* Perform a small amount of marking. */
246: /* We try to touch roughly a page of memory. */
247: /* Return TRUE if we just finished a mark phase. */
248: /* Cold_gc_frame is an address inside a GC frame that */
249: /* remains valid until all marking is complete. */
250: /* A zero value indicates that it's OK to miss some */
251: /* register values. */
252: GC_bool GC_mark_some(cold_gc_frame)
253: ptr_t cold_gc_frame;
254: {
255: #ifdef MSWIN32
256: /* Windows 98 appears to asynchronously create and remove writable */
257: /* memory mappings, for reasons we haven't yet understood. Since */
258: /* we look for writable regions to determine the root set, we may */
259: /* try to mark from an address range that disappeared since we */
260: /* started the collection. Thus we have to recover from faults here. */
261: /* This code does not appear to be necessary for Windows 95/NT/2000. */
262: /* Note that this code should never generate an incremental GC write */
263: /* fault. */
264: __try {
265: #endif
266: switch(GC_mark_state) {
267: case MS_NONE:
268: return(FALSE);
269:
270: case MS_PUSH_RESCUERS:
271: if (GC_mark_stack_top
272: >= GC_mark_stack + GC_mark_stack_size
273: - INITIAL_MARK_STACK_SIZE/2) {
274: /* Go ahead and mark, even though that might cause us to */
275: /* see more marked dirty objects later on. Avoid this */
276: /* in the future. */
277: GC_mark_stack_too_small = TRUE;
278: GC_mark_from_mark_stack();
279: return(FALSE);
280: } else {
281: scan_ptr = GC_push_next_marked_dirty(scan_ptr);
282: if (scan_ptr == 0) {
283: # ifdef PRINTSTATS
284: GC_printf1("Marked from %lu dirty pages\n",
285: (unsigned long)GC_n_rescuing_pages);
286: # endif
287: GC_push_roots(FALSE, cold_gc_frame);
288: GC_objects_are_marked = TRUE;
289: if (GC_mark_state != MS_INVALID) {
290: GC_mark_state = MS_ROOTS_PUSHED;
291: }
292: }
293: }
294: return(FALSE);
295:
296: case MS_PUSH_UNCOLLECTABLE:
297: if (GC_mark_stack_top
298: >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
299: GC_mark_from_mark_stack();
300: return(FALSE);
301: } else {
302: scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
303: if (scan_ptr == 0) {
304: GC_push_roots(TRUE, cold_gc_frame);
305: GC_objects_are_marked = TRUE;
306: if (GC_mark_state != MS_INVALID) {
307: GC_mark_state = MS_ROOTS_PUSHED;
308: }
309: }
310: }
311: return(FALSE);
312:
313: case MS_ROOTS_PUSHED:
314: if (GC_mark_stack_top >= GC_mark_stack) {
315: GC_mark_from_mark_stack();
316: return(FALSE);
317: } else {
318: GC_mark_state = MS_NONE;
319: if (GC_mark_stack_too_small) {
320: alloc_mark_stack(2*GC_mark_stack_size);
321: }
322: return(TRUE);
323: }
324:
325: case MS_INVALID:
326: case MS_PARTIALLY_INVALID:
327: if (!GC_objects_are_marked) {
328: GC_mark_state = MS_PUSH_UNCOLLECTABLE;
329: return(FALSE);
330: }
331: if (GC_mark_stack_top >= GC_mark_stack) {
332: GC_mark_from_mark_stack();
333: return(FALSE);
334: }
335: if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {
336: /* About to start a heap scan for marked objects. */
337: /* Mark stack is empty. OK to reallocate. */
338: if (GC_mark_stack_too_small) {
339: alloc_mark_stack(2*GC_mark_stack_size);
340: }
341: GC_mark_state = MS_PARTIALLY_INVALID;
342: }
343: scan_ptr = GC_push_next_marked(scan_ptr);
344: if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
345: GC_push_roots(TRUE, cold_gc_frame);
346: GC_objects_are_marked = TRUE;
347: if (GC_mark_state != MS_INVALID) {
348: GC_mark_state = MS_ROOTS_PUSHED;
349: }
350: }
351: return(FALSE);
352: default:
353: ABORT("GC_mark_some: bad state");
354: return(FALSE);
355: }
356: #ifdef MSWIN32
357: } __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?
358: EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) {
359: # ifdef PRINTSTATS
360: GC_printf0("Caught ACCESS_VIOLATION in marker. "
361: "Memory mapping disappeared.\n");
362: # endif /* PRINTSTATS */
363: /* We have bad roots on the stack. Discard mark stack. */
364: /* Rescan from marked objects. Redetermine roots. */
365: GC_invalidate_mark_state();
366: scan_ptr = 0;
367: return FALSE;
368: }
369: #endif /* MSWIN32 */
370: }
371:
372:
373: GC_bool GC_mark_stack_empty()
374: {
375: return(GC_mark_stack_top < GC_mark_stack);
376: }
377:
378: #ifdef PROF_MARKER
379: word GC_prof_array[10];
380: # define PROF(n) GC_prof_array[n]++
381: #else
382: # define PROF(n)
383: #endif
384:
385: /* Given a pointer to someplace other than a small object page or the */
386: /* first page of a large object, return a pointer either to the */
387: /* start of the large object or NIL. */
388: /* In the latter case black list the address current. */
389: /* Returns NIL without black listing if current points to a block */
390: /* with IGNORE_OFF_PAGE set. */
391: /*ARGSUSED*/
392: # ifdef PRINT_BLACK_LIST
393: ptr_t GC_find_start(current, hhdr, source)
394: word source;
395: # else
396: ptr_t GC_find_start(current, hhdr)
397: # define source 0
398: # endif
399: register ptr_t current;
400: register hdr * hhdr;
401: {
402: # ifdef ALL_INTERIOR_POINTERS
403: if (hhdr != 0) {
404: register ptr_t orig = current;
405:
406: current = (ptr_t)HBLKPTR(current) + HDR_BYTES;
407: do {
408: current = current - HBLKSIZE*(word)hhdr;
409: hhdr = HDR(current);
410: } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
411: /* current points to the start of the large object */
412: if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
413: if ((word *)orig - (word *)current
414: >= (ptrdiff_t)(hhdr->hb_sz)) {
415: /* Pointer past the end of the block */
416: GC_ADD_TO_BLACK_LIST_NORMAL(orig, source);
417: return(0);
418: }
419: return(current);
420: } else {
421: GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
422: return(0);
423: }
424: # else
425: GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
426: return(0);
427: # endif
428: # undef source
429: }
430:
431: void GC_invalidate_mark_state()
432: {
433: GC_mark_state = MS_INVALID;
434: GC_mark_stack_top = GC_mark_stack-1;
435: }
436:
437: mse * GC_signal_mark_stack_overflow(msp)
438: mse * msp;
439: {
440: GC_mark_state = MS_INVALID;
441: GC_mark_stack_too_small = TRUE;
442: # ifdef PRINTSTATS
443: GC_printf1("Mark stack overflow; current size = %lu entries\n",
444: GC_mark_stack_size);
445: # endif
446: return(msp-INITIAL_MARK_STACK_SIZE/8);
447: }
448:
449:
450: /*
451: * Mark objects pointed to by the regions described by
452: * mark stack entries between GC_mark_stack and GC_mark_stack_top,
453: * inclusive. Assumes the upper limit of a mark stack entry
454: * is never 0. A mark stack entry never has size 0.
455: * We try to traverse on the order of a hblk of memory before we return.
456: * Caller is responsible for calling this until the mark stack is empty.
457: * Note that this is the most performance critical routine in the
458: * collector. Hence it contains all sorts of ugly hacks to speed
459: * things up. In particular, we avoid procedure calls on the common
460: * path, we take advantage of peculiarities of the mark descriptor
461: * encoding, we optionally maintain a cache for the block address to
462: * header mapping, we prefetch when an object is "grayed", etc.
463: */
464: void GC_mark_from_mark_stack()
465: {
466: mse * GC_mark_stack_reg = GC_mark_stack;
467: mse * GC_mark_stack_top_reg = GC_mark_stack_top;
468: mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
469: int credit = HBLKSIZE; /* Remaining credit for marking work */
470: register word * current_p; /* Pointer to current candidate ptr. */
471: register word current; /* Candidate pointer. */
472: register word * limit; /* (Incl) limit of current candidate */
473: /* range */
474: register word descr;
475: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
476: register ptr_t least_ha = GC_least_plausible_heap_addr;
477: DECLARE_HDR_CACHE;
478:
479: # define SPLIT_RANGE_WORDS 128 /* Must be power of 2. */
480:
481: GC_objects_are_marked = TRUE;
482: INIT_HDR_CACHE;
483: # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
484: while (GC_mark_stack_top_reg >= GC_mark_stack_reg && credit >= 0) {
485: # else
486: while ((((ptr_t)GC_mark_stack_top_reg - (ptr_t)GC_mark_stack_reg) | credit)
487: >= 0) {
488: # endif
489: current_p = GC_mark_stack_top_reg -> mse_start;
490: descr = GC_mark_stack_top_reg -> mse_descr;
491: retry:
492: /* current_p and descr describe the current object. */
493: /* *GC_mark_stack_top_reg is vacant. */
494: /* The following is 0 only for small objects described by a simple */
495: /* length descriptor. For many applications this is the common */
496: /* case, so we try to detect it quickly. */
497: if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | DS_TAGS)) {
498: word tag = descr & DS_TAGS;
499:
500: switch(tag) {
501: case DS_LENGTH:
502: /* Large length. */
503: /* Process part of the range to avoid pushing too much on the */
504: /* stack. */
505: GC_mark_stack_top_reg -> mse_start =
506: limit = current_p + SPLIT_RANGE_WORDS-1;
507: GC_mark_stack_top_reg -> mse_descr =
508: descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
509: /* Make sure that pointers overlapping the two ranges are */
510: /* considered. */
511: limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
512: break;
513: case DS_BITMAP:
514: GC_mark_stack_top_reg--;
515: descr &= ~DS_TAGS;
516: credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
517: while (descr != 0) {
518: if ((signed_word)descr < 0) {
519: current = *current_p;
520: if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
521: PREFETCH(current);
522: HC_PUSH_CONTENTS((ptr_t)current, GC_mark_stack_top_reg,
523: mark_stack_limit, current_p, exit1);
524: }
525: }
526: descr <<= 1;
527: ++ current_p;
528: }
529: continue;
530: case DS_PROC:
531: GC_mark_stack_top_reg--;
532: credit -= PROC_BYTES;
533: GC_mark_stack_top_reg =
534: (*PROC(descr))
535: (current_p, GC_mark_stack_top_reg,
536: mark_stack_limit, ENV(descr));
537: continue;
538: case DS_PER_OBJECT:
539: if ((signed_word)descr >= 0) {
540: /* Descriptor is in the object. */
541: descr = *(word *)((ptr_t)current_p + descr - DS_PER_OBJECT);
542: } else {
543: /* Descriptor is in type descriptor pointed to by first */
544: /* word in object. */
545: ptr_t type_descr = *(ptr_t *)current_p;
546: /* type_descr is either a valid pointer to the descriptor */
547: /* structure, or this object was on a free list. If it */
548: /* it was anything but the last object on the free list, */
549: /* we will misinterpret the next object on the free list as */
550: /* the type descriptor, and get a 0 GC descriptor, which */
551: /* is ideal. Unfortunately, we need to check for the last */
552: /* object case explicitly. */
553: if (0 == type_descr) {
554: /* Rarely executed. */
555: GC_mark_stack_top_reg--;
556: continue;
557: }
558: descr = *(word *)(type_descr
559: - (descr - (DS_PER_OBJECT - INDIR_PER_OBJ_BIAS)));
560: }
561: if (0 == descr) {
562: GC_mark_stack_top_reg--;
563: continue;
564: }
565: goto retry;
566: }
567: } else /* Small object with length descriptor */ {
568: GC_mark_stack_top_reg--;
569: limit = (word *)(((ptr_t)current_p) + (word)descr);
570: }
571: /* The simple case in which we're scanning a range. */
572: credit -= (ptr_t)limit - (ptr_t)current_p;
573: limit -= 1;
574: {
575: # define PREF_DIST 4
576:
577: # ifndef SMALL_CONFIG
578: word deferred;
579:
580: /* Try to prefetch the next pointer to be examined asap. */
581: /* Empirically, this also seems to help slightly without */
582: /* prefetches, at least on linux/X86. Presumably this loop */
583: /* ends up with less register pressure, and gcc thus ends up */
584: /* generating slightly better code. Overall gcc code quality */
585: /* for this loop is still not great. */
586: for(;;) {
587: PREFETCH((ptr_t)limit - PREF_DIST*CACHE_LINE_SIZE);
588: deferred = *limit;
589: limit = (word *)((char *)limit - ALIGNMENT);
590: if ((ptr_t)deferred >= least_ha && (ptr_t)deferred < greatest_ha) {
591: PREFETCH(deferred);
592: break;
593: }
594: if (current_p > limit) goto next_object;
595: /* Unroll once, so we don't do too many of the prefetches */
596: /* based on limit. */
597: deferred = *limit;
598: limit = (word *)((char *)limit - ALIGNMENT);
599: if ((ptr_t)deferred >= least_ha && (ptr_t)deferred < greatest_ha) {
600: PREFETCH(deferred);
601: break;
602: }
603: if (current_p > limit) goto next_object;
604: }
605: # endif
606:
607: while (current_p <= limit) {
608: /* Empirically, unrolling this loop doesn't help a lot. */
609: /* Since HC_PUSH_CONTENTS expands to a lot of code, */
610: /* we don't. */
611: current = *current_p;
612: PREFETCH((ptr_t)current_p + PREF_DIST*CACHE_LINE_SIZE);
613: if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
614: /* Prefetch the contents of the object we just pushed. It's */
615: /* likely we will need them soon. */
616: PREFETCH(current);
617: HC_PUSH_CONTENTS((ptr_t)current, GC_mark_stack_top_reg,
618: mark_stack_limit, current_p, exit2);
619: }
620: current_p = (word *)((char *)current_p + ALIGNMENT);
621: }
622:
623: # ifndef SMALL_CONFIG
624: /* We still need to mark the entry we previously prefetched. */
625: /* We alrady know that it passes the preliminary pointer */
626: /* validity test. */
627: HC_PUSH_CONTENTS((ptr_t)deferred, GC_mark_stack_top_reg,
628: mark_stack_limit, current_p, exit4);
629: next_object:;
630: # endif
631: }
632: }
633: GC_mark_stack_top = GC_mark_stack_top_reg;
634: }
635:
636: /* Allocate or reallocate space for mark stack of size s words */
637: /* May silently fail. */
638: static void alloc_mark_stack(n)
639: word n;
640: {
641: mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct ms_entry));
642:
643: GC_mark_stack_too_small = FALSE;
644: if (GC_mark_stack_size != 0) {
645: if (new_stack != 0) {
646: word displ = (word)GC_mark_stack & (GC_page_size - 1);
647: signed_word size = GC_mark_stack_size * sizeof(struct ms_entry);
648:
649: /* Recycle old space */
650: if (0 != displ) displ = GC_page_size - displ;
651: size = (size - displ) & ~(GC_page_size - 1);
652: if (size > 0) {
653: GC_add_to_heap((struct hblk *)
654: ((word)GC_mark_stack + displ), (word)size);
655: }
656: GC_mark_stack = new_stack;
657: GC_mark_stack_size = n;
658: # ifdef PRINTSTATS
659: GC_printf1("Grew mark stack to %lu frames\n",
660: (unsigned long) GC_mark_stack_size);
661: # endif
662: } else {
663: # ifdef PRINTSTATS
664: GC_printf1("Failed to grow mark stack to %lu frames\n",
665: (unsigned long) n);
666: # endif
667: }
668: } else {
669: if (new_stack == 0) {
670: GC_err_printf0("No space for mark stack\n");
671: EXIT();
672: }
673: GC_mark_stack = new_stack;
674: GC_mark_stack_size = n;
675: }
676: GC_mark_stack_top = GC_mark_stack-1;
677: }
678:
679: void GC_mark_init()
680: {
681: alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
682: }
683:
684: /*
685: * Push all locations between b and t onto the mark stack.
686: * b is the first location to be checked. t is one past the last
687: * location to be checked.
688: * Should only be used if there is no possibility of mark stack
689: * overflow.
690: */
691: void GC_push_all(bottom, top)
692: ptr_t bottom;
693: ptr_t top;
694: {
695: register word length;
696:
697: bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
698: top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
699: if (top == 0 || bottom == top) return;
700: GC_mark_stack_top++;
701: if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
702: ABORT("unexpected mark stack overflow");
703: }
704: length = top - bottom;
705: # if DS_TAGS > ALIGNMENT - 1
706: length += DS_TAGS;
707: length &= ~DS_TAGS;
708: # endif
709: GC_mark_stack_top -> mse_start = (word *)bottom;
710: GC_mark_stack_top -> mse_descr = length;
711: }
712:
713: /*
714: * Analogous to the above, but push only those pages that may have been
715: * dirtied. A block h is assumed dirty if dirty_fn(h) != 0.
716: * We use push_fn to actually push the block.
717: * Will not overflow mark stack if push_fn pushes a small fixed number
718: * of entries. (This is invoked only if push_fn pushes a single entry,
719: * or if it marks each object before pushing it, thus ensuring progress
720: * in the event of a stack overflow.)
721: */
722: void GC_push_dirty(bottom, top, dirty_fn, push_fn)
723: ptr_t bottom;
724: ptr_t top;
725: int (*dirty_fn)(/* struct hblk * h */);
726: void (*push_fn)(/* ptr_t bottom, ptr_t top */);
727: {
728: register struct hblk * h;
729:
730: bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
731: top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
732:
733: if (top == 0 || bottom == top) return;
734: h = HBLKPTR(bottom + HBLKSIZE);
735: if (top <= (ptr_t) h) {
736: if ((*dirty_fn)(h-1)) {
737: (*push_fn)(bottom, top);
738: }
739: return;
740: }
741: if ((*dirty_fn)(h-1)) {
742: (*push_fn)(bottom, (ptr_t)h);
743: }
744: while ((ptr_t)(h+1) <= top) {
745: if ((*dirty_fn)(h)) {
746: if ((word)(GC_mark_stack_top - GC_mark_stack)
747: > 3 * GC_mark_stack_size / 4) {
748: /* Danger of mark stack overflow */
749: (*push_fn)((ptr_t)h, top);
750: return;
751: } else {
752: (*push_fn)((ptr_t)h, (ptr_t)(h+1));
753: }
754: }
755: h++;
756: }
757: if ((ptr_t)h != top) {
758: if ((*dirty_fn)(h)) {
759: (*push_fn)((ptr_t)h, top);
760: }
761: }
762: if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
763: ABORT("unexpected mark stack overflow");
764: }
765: }
766:
767: # ifndef SMALL_CONFIG
768: void GC_push_conditional(bottom, top, all)
769: ptr_t bottom;
770: ptr_t top;
771: int all;
772: {
773: if (all) {
774: if (GC_dirty_maintained) {
775: # ifdef PROC_VDB
776: /* Pages that were never dirtied cannot contain pointers */
777: GC_push_dirty(bottom, top, GC_page_was_ever_dirty, GC_push_all);
778: # else
779: GC_push_all(bottom, top);
780: # endif
781: } else {
782: GC_push_all(bottom, top);
783: }
784: } else {
785: GC_push_dirty(bottom, top, GC_page_was_dirty, GC_push_all);
786: }
787: }
788: #endif
789:
790: # ifdef MSWIN32
791: void __cdecl GC_push_one(p)
792: # else
793: void GC_push_one(p)
794: # endif
795: word p;
796: {
797: # ifdef NURSERY
798: if (0 != GC_push_proc) {
799: GC_push_proc(p);
800: return;
801: }
802: # endif
803: GC_PUSH_ONE_STACK(p, MARKED_FROM_REGISTER);
804: }
805:
806: # ifdef __STDC__
807: # define BASE(p) (word)GC_base((void *)(p))
808: # else
809: # define BASE(p) (word)GC_base((char *)(p))
810: # endif
811:
812: /* As above, but argument passed preliminary test. */
813: # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
814: void GC_push_one_checked(p, interior_ptrs, source)
815: ptr_t source;
816: # else
817: void GC_push_one_checked(p, interior_ptrs)
818: # define source 0
819: # endif
820: register word p;
821: register GC_bool interior_ptrs;
822: {
823: register word r;
824: register hdr * hhdr;
825: register int displ;
826:
827: GET_HDR(p, hhdr);
828: if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
829: if (hhdr != 0 && interior_ptrs) {
830: r = BASE(p);
831: hhdr = HDR(r);
832: displ = BYTES_TO_WORDS(HBLKDISPL(r));
833: } else {
834: hhdr = 0;
835: }
836: } else {
837: register map_entry_type map_entry;
838:
839: displ = HBLKDISPL(p);
840: map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
841: if (map_entry == OBJ_INVALID) {
842: # ifndef ALL_INTERIOR_POINTERS
843: if (interior_ptrs) {
844: r = BASE(p);
845: displ = BYTES_TO_WORDS(HBLKDISPL(r));
846: if (r == 0) hhdr = 0;
847: } else {
848: hhdr = 0;
849: }
850: # else
851: /* map already reflects interior pointers */
852: hhdr = 0;
853: # endif
854: } else {
855: displ = BYTES_TO_WORDS(displ);
856: displ -= map_entry;
857: r = (word)((word *)(HBLKPTR(p)) + displ);
858: }
859: }
860: /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
861: /* displ is the word index within the block. */
862: if (hhdr == 0) {
863: if (interior_ptrs) {
864: # ifdef PRINT_BLACK_LIST
865: GC_add_to_black_list_stack(p, source);
866: # else
867: GC_add_to_black_list_stack(p);
868: # endif
869: } else {
870: GC_ADD_TO_BLACK_LIST_NORMAL(p, source);
871: # undef source /* In case we had to define it. */
872: }
873: } else {
874: if (!mark_bit_from_hdr(hhdr, displ)) {
875: set_mark_bit_from_hdr(hhdr, displ);
876: GC_STORE_BACK_PTR(source, (ptr_t)r);
877: PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
878: &(GC_mark_stack[GC_mark_stack_size]));
879: }
880: }
881: }
882:
883: # ifdef TRACE_BUF
884:
885: # define TRACE_ENTRIES 1000
886:
887: struct trace_entry {
888: char * kind;
889: word gc_no;
890: word words_allocd;
891: word arg1;
892: word arg2;
893: } GC_trace_buf[TRACE_ENTRIES];
894:
895: int GC_trace_buf_ptr = 0;
896:
897: void GC_add_trace_entry(char *kind, word arg1, word arg2)
898: {
899: GC_trace_buf[GC_trace_buf_ptr].kind = kind;
900: GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
901: GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
902: GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
903: GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
904: GC_trace_buf_ptr++;
905: if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
906: }
907:
908: void GC_print_trace(word gc_no, GC_bool lock)
909: {
910: int i;
911: struct trace_entry *p;
912:
913: if (lock) LOCK();
914: for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
915: if (i < 0) i = TRACE_ENTRIES-1;
916: p = GC_trace_buf + i;
917: if (p -> gc_no < gc_no || p -> kind == 0) return;
918: printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
919: p -> kind, p -> gc_no, p -> words_allocd,
920: (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
921: }
922: printf("Trace incomplete\n");
923: if (lock) UNLOCK();
924: }
925:
926: # endif /* TRACE_BUF */
927:
928: /*
929: * A version of GC_push_all that treats all interior pointers as valid
930: * and scans the entire region immediately, in case the contents
931: * change.
932: */
933: void GC_push_all_eager(bottom, top)
934: ptr_t bottom;
935: ptr_t top;
936: {
937: word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
938: word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
939: register word *p;
940: register word q;
941: register word *lim;
942: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
943: register ptr_t least_ha = GC_least_plausible_heap_addr;
944: # define GC_greatest_plausible_heap_addr greatest_ha
945: # define GC_least_plausible_heap_addr least_ha
946:
947: if (top == 0) return;
948: /* check all pointers in range and put in push if they appear */
949: /* to be valid. */
950: lim = t - 1 /* longword */;
951: for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
952: q = *p;
953: GC_PUSH_ONE_STACK(q, p);
954: }
955: # undef GC_greatest_plausible_heap_addr
956: # undef GC_least_plausible_heap_addr
957: }
958:
959: #ifndef THREADS
960: /*
961: * A version of GC_push_all that treats all interior pointers as valid
962: * and scans part of the area immediately, to make sure that saved
963: * register values are not lost.
964: * Cold_gc_frame delimits the stack section that must be scanned
965: * eagerly. A zero value indicates that no eager scanning is needed.
966: */
967: void GC_push_all_stack_partially_eager(bottom, top, cold_gc_frame)
968: ptr_t bottom;
969: ptr_t top;
970: ptr_t cold_gc_frame;
971: {
972: # ifdef ALL_INTERIOR_POINTERS
973: # define EAGER_BYTES 1024
974: /* Push the hot end of the stack eagerly, so that register values */
975: /* saved inside GC frames are marked before they disappear. */
976: /* The rest of the marking can be deferred until later. */
977: if (0 == cold_gc_frame) {
978: GC_push_all_stack(bottom, top);
979: return;
980: }
981: # ifdef STACK_GROWS_DOWN
982: GC_push_all_eager(bottom, cold_gc_frame);
983: GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
984: # else /* STACK_GROWS_UP */
985: GC_push_all_eager(cold_gc_frame, top);
986: GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
987: # endif /* STACK_GROWS_UP */
988: # else
989: GC_push_all_eager(bottom, top);
990: # endif
991: # ifdef TRACE_BUF
992: GC_add_trace_entry("GC_push_all_stack", bottom, top);
993: # endif
994: }
995: #endif /* !THREADS */
996:
997: void GC_push_all_stack(bottom, top)
998: ptr_t bottom;
999: ptr_t top;
1000: {
1001: # ifdef ALL_INTERIOR_POINTERS
1002: GC_push_all(bottom, top);
1003: # else
1004: GC_push_all_eager(bottom, top);
1005: # endif
1006: }
1007:
1008: #ifndef SMALL_CONFIG
1009: /* Push all objects reachable from marked objects in the given block */
1010: /* of size 1 objects. */
1011: void GC_push_marked1(h, hhdr)
1012: struct hblk *h;
1013: register hdr * hhdr;
1014: {
1015: word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
1016: register word *p;
1017: word *plim;
1018: register int i;
1019: register word q;
1020: register word mark_word;
1021: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1022: register ptr_t least_ha = GC_least_plausible_heap_addr;
1023: # define GC_greatest_plausible_heap_addr greatest_ha
1024: # define GC_least_plausible_heap_addr least_ha
1025:
1026: p = (word *)(h->hb_body);
1027: plim = (word *)(((word)h) + HBLKSIZE);
1028:
1029: /* go through all words in block */
1030: while( p < plim ) {
1031: mark_word = *mark_word_addr++;
1032: i = 0;
1033: while(mark_word != 0) {
1034: if (mark_word & 1) {
1035: q = p[i];
1036: GC_PUSH_ONE_HEAP(q, p + i);
1037: }
1038: i++;
1039: mark_word >>= 1;
1040: }
1041: p += WORDSZ;
1042: }
1043: # undef GC_greatest_plausible_heap_addr
1044: # undef GC_least_plausible_heap_addr
1045: }
1046:
1047:
1048: #ifndef UNALIGNED
1049:
1050: /* Push all objects reachable from marked objects in the given block */
1051: /* of size 2 objects. */
1052: void GC_push_marked2(h, hhdr)
1053: struct hblk *h;
1054: register hdr * hhdr;
1055: {
1056: word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
1057: register word *p;
1058: word *plim;
1059: register int i;
1060: register word q;
1061: register word mark_word;
1062: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1063: register ptr_t least_ha = GC_least_plausible_heap_addr;
1064: # define GC_greatest_plausible_heap_addr greatest_ha
1065: # define GC_least_plausible_heap_addr least_ha
1066:
1067: p = (word *)(h->hb_body);
1068: plim = (word *)(((word)h) + HBLKSIZE);
1069:
1070: /* go through all words in block */
1071: while( p < plim ) {
1072: mark_word = *mark_word_addr++;
1073: i = 0;
1074: while(mark_word != 0) {
1075: if (mark_word & 1) {
1076: q = p[i];
1077: GC_PUSH_ONE_HEAP(q, p + i);
1078: q = p[i+1];
1079: GC_PUSH_ONE_HEAP(q, p + i);
1080: }
1081: i += 2;
1082: mark_word >>= 2;
1083: }
1084: p += WORDSZ;
1085: }
1086: # undef GC_greatest_plausible_heap_addr
1087: # undef GC_least_plausible_heap_addr
1088: }
1089:
1090: /* Push all objects reachable from marked objects in the given block */
1091: /* of size 4 objects. */
1092: /* There is a risk of mark stack overflow here. But we handle that. */
1093: /* And only unmarked objects get pushed, so it's not very likely. */
1094: void GC_push_marked4(h, hhdr)
1095: struct hblk *h;
1096: register hdr * hhdr;
1097: {
1098: word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
1099: register word *p;
1100: word *plim;
1101: register int i;
1102: register word q;
1103: register word mark_word;
1104: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1105: register ptr_t least_ha = GC_least_plausible_heap_addr;
1106: # define GC_greatest_plausible_heap_addr greatest_ha
1107: # define GC_least_plausible_heap_addr least_ha
1108:
1109: p = (word *)(h->hb_body);
1110: plim = (word *)(((word)h) + HBLKSIZE);
1111:
1112: /* go through all words in block */
1113: while( p < plim ) {
1114: mark_word = *mark_word_addr++;
1115: i = 0;
1116: while(mark_word != 0) {
1117: if (mark_word & 1) {
1118: q = p[i];
1119: GC_PUSH_ONE_HEAP(q, p + i);
1120: q = p[i+1];
1121: GC_PUSH_ONE_HEAP(q, p + i + 1);
1122: q = p[i+2];
1123: GC_PUSH_ONE_HEAP(q, p + i + 2);
1124: q = p[i+3];
1125: GC_PUSH_ONE_HEAP(q, p + i + 3);
1126: }
1127: i += 4;
1128: mark_word >>= 4;
1129: }
1130: p += WORDSZ;
1131: }
1132: # undef GC_greatest_plausible_heap_addr
1133: # undef GC_least_plausible_heap_addr
1134: }
1135:
1136: #endif /* UNALIGNED */
1137:
1138: #endif /* SMALL_CONFIG */
1139:
1140: /* Push all objects reachable from marked objects in the given block */
1141: void GC_push_marked(h, hhdr)
1142: struct hblk *h;
1143: register hdr * hhdr;
1144: {
1145: register int sz = hhdr -> hb_sz;
1146: register int descr = hhdr -> hb_descr;
1147: register word * p;
1148: register int word_no;
1149: register word * lim;
1150: register mse * GC_mark_stack_top_reg;
1151: register mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
1152:
1153: /* Some quick shortcuts: */
1154: if ((0 | DS_LENGTH) == descr) return;
1155: if (GC_block_empty(hhdr)/* nothing marked */) return;
1156: # ifdef GATHERSTATS
1157: GC_n_rescuing_pages++;
1158: # endif
1159: GC_objects_are_marked = TRUE;
1160: if (sz > MAXOBJSZ) {
1161: lim = (word *)h + HDR_WORDS;
1162: } else {
1163: lim = (word *)(h + 1) - sz;
1164: }
1165:
1166: switch(sz) {
1167: # if !defined(SMALL_CONFIG)
1168: case 1:
1169: GC_push_marked1(h, hhdr);
1170: break;
1171: # endif
1172: # if !defined(SMALL_CONFIG) && !defined(UNALIGNED)
1173: case 2:
1174: GC_push_marked2(h, hhdr);
1175: break;
1176: case 4:
1177: GC_push_marked4(h, hhdr);
1178: break;
1179: # endif
1180: default:
1181: GC_mark_stack_top_reg = GC_mark_stack_top;
1182: for (p = (word *)h + HDR_WORDS, word_no = HDR_WORDS; p <= lim;
1183: p += sz, word_no += sz) {
1184: if (mark_bit_from_hdr(hhdr, word_no)) {
1185: /* Mark from fields inside the object */
1186: PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
1187: # ifdef GATHERSTATS
1188: /* Subtract this object from total, since it was */
1189: /* added in twice. */
1190: GC_composite_in_use -= sz;
1191: # endif
1192: }
1193: }
1194: GC_mark_stack_top = GC_mark_stack_top_reg;
1195: }
1196: }
1197:
1198: #ifndef SMALL_CONFIG
1199: /* Test whether any page in the given block is dirty */
1200: GC_bool GC_block_was_dirty(h, hhdr)
1201: struct hblk *h;
1202: register hdr * hhdr;
1203: {
1204: register int sz = hhdr -> hb_sz;
1205:
1206: if (sz < MAXOBJSZ) {
1207: return(GC_page_was_dirty(h));
1208: } else {
1209: register ptr_t p = (ptr_t)h;
1210: sz += HDR_WORDS;
1211: sz = WORDS_TO_BYTES(sz);
1212: while (p < (ptr_t)h + sz) {
1213: if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
1214: p += HBLKSIZE;
1215: }
1216: return(FALSE);
1217: }
1218: }
1219: #endif /* SMALL_CONFIG */
1220:
1221: /* Similar to GC_push_next_marked, but return address of next block */
1222: struct hblk * GC_push_next_marked(h)
1223: struct hblk *h;
1224: {
1225: register hdr * hhdr;
1226:
1227: h = GC_next_used_block(h);
1228: if (h == 0) return(0);
1229: hhdr = HDR(h);
1230: GC_push_marked(h, hhdr);
1231: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1232: }
1233:
1234: #ifndef SMALL_CONFIG
1235: /* Identical to above, but mark only from dirty pages */
1236: struct hblk * GC_push_next_marked_dirty(h)
1237: struct hblk *h;
1238: {
1239: register hdr * hhdr;
1240:
1241: if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
1242: for (;;) {
1243: h = GC_next_used_block(h);
1244: if (h == 0) return(0);
1245: hhdr = HDR(h);
1246: # ifdef STUBBORN_ALLOC
1247: if (hhdr -> hb_obj_kind == STUBBORN) {
1248: if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
1249: break;
1250: }
1251: } else {
1252: if (GC_block_was_dirty(h, hhdr)) break;
1253: }
1254: # else
1255: if (GC_block_was_dirty(h, hhdr)) break;
1256: # endif
1257: h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1258: }
1259: GC_push_marked(h, hhdr);
1260: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1261: }
1262: #endif
1263:
1264: /* Similar to above, but for uncollectable pages. Needed since we */
1265: /* do not clear marks for such pages, even for full collections. */
1266: struct hblk * GC_push_next_marked_uncollectable(h)
1267: struct hblk *h;
1268: {
1269: register hdr * hhdr = HDR(h);
1270:
1271: for (;;) {
1272: h = GC_next_used_block(h);
1273: if (h == 0) return(0);
1274: hhdr = HDR(h);
1275: if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
1276: h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1277: }
1278: GC_push_marked(h, hhdr);
1279: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1280: }
1281:
1282:
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 / gc5.3