Annotation of OpenXM_contrib2/asir2000/gc/mark.c, Revision 1.4
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.
1.4 ! noro 5: * Copyright (c) 2000 by Hewlett-Packard Company. All rights reserved.
1.1 noro 6: *
7: * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
8: * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
9: *
10: * Permission is hereby granted to use or copy this program
11: * for any purpose, provided the above notices are retained on all copies.
12: * Permission to modify the code and to distribute modified code is granted,
13: * provided the above notices are retained, and a notice that the code was
14: * modified is included with the above copyright notice.
15: *
16: */
17:
18:
19: # include <stdio.h>
1.4 ! noro 20: # include "private/gc_pmark.h"
1.1 noro 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:
1.3 noro 41: word GC_n_mark_procs = GC_RESERVED_MARK_PROCS;
1.1 noro 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 */,
1.4 ! noro 49: 0 | GC_DS_LENGTH, FALSE, FALSE },
1.1 noro 50: /* NORMAL */ { &GC_objfreelist[0], 0,
1.4 ! noro 51: 0 | GC_DS_LENGTH, /* Adjusted in GC_init_inner for EXTRA_BYTES */
1.1 noro 52: TRUE /* add length to descr */, TRUE },
53: /* UNCOLLECTABLE */
54: { &GC_uobjfreelist[0], 0,
1.4 ! noro 55: 0 | GC_DS_LENGTH, TRUE /* add length to descr */, TRUE },
1.1 noro 56: # ifdef ATOMIC_UNCOLLECTABLE
57: /* AUNCOLLECTABLE */
58: { &GC_auobjfreelist[0], 0,
1.4 ! noro 59: 0 | GC_DS_LENGTH, FALSE /* add length to descr */, FALSE },
1.1 noro 60: # endif
61: # ifdef STUBBORN_ALLOC
62: /*STUBBORN*/ { &GC_sobjfreelist[0], 0,
1.4 ! noro 63: 0 | GC_DS_LENGTH, TRUE /* add length to descr */, TRUE },
1.1 noro 64: # endif
65: };
66:
67: # ifdef ATOMIC_UNCOLLECTABLE
68: # ifdef STUBBORN_ALLOC
69: int GC_n_kinds = 5;
70: # else
71: int GC_n_kinds = 4;
72: # endif
73: # else
74: # ifdef STUBBORN_ALLOC
75: int GC_n_kinds = 4;
76: # else
77: int GC_n_kinds = 3;
78: # endif
79: # endif
80:
81:
82: # ifndef INITIAL_MARK_STACK_SIZE
83: # define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
84: /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a */
85: /* multiple of HBLKSIZE. */
1.2 noro 86: /* The incremental collector actually likes a larger */
87: /* size, since it want to push all marked dirty objs */
88: /* before marking anything new. Currently we let it */
89: /* grow dynamically. */
1.1 noro 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:
1.4 ! noro 103: mse * GC_mark_stack_limit;
! 104:
1.1 noro 105: word GC_mark_stack_size = 0;
106:
1.4 ! noro 107: #ifdef PARALLEL_MARK
! 108: mse * VOLATILE GC_mark_stack_top;
! 109: #else
! 110: mse * GC_mark_stack_top;
! 111: #endif
1.1 noro 112:
113: static struct hblk * scan_ptr;
114:
115: mark_state_t GC_mark_state = MS_NONE;
116:
117: GC_bool GC_mark_stack_too_small = FALSE;
118:
119: GC_bool GC_objects_are_marked = FALSE; /* Are there collectable marked */
120: /* objects in the heap? */
121:
122: /* Is a collection in progress? Note that this can return true in the */
123: /* nonincremental case, if a collection has been abandoned and the */
124: /* mark state is now MS_INVALID. */
125: GC_bool GC_collection_in_progress()
126: {
127: return(GC_mark_state != MS_NONE);
128: }
129:
130: /* clear all mark bits in the header */
131: void GC_clear_hdr_marks(hhdr)
132: register hdr * hhdr;
133: {
1.4 ! noro 134: # ifdef USE_MARK_BYTES
! 135: BZERO(hhdr -> hb_marks, MARK_BITS_SZ);
! 136: # else
! 137: BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
! 138: # endif
1.1 noro 139: }
140:
141: /* Set all mark bits in the header. Used for uncollectable blocks. */
142: void GC_set_hdr_marks(hhdr)
143: register hdr * hhdr;
144: {
145: register int i;
146:
147: for (i = 0; i < MARK_BITS_SZ; ++i) {
1.4 ! noro 148: # ifdef USE_MARK_BYTES
! 149: hhdr -> hb_marks[i] = 1;
! 150: # else
1.1 noro 151: hhdr -> hb_marks[i] = ONES;
1.4 ! noro 152: # endif
1.1 noro 153: }
154: }
155:
156: /*
157: * Clear all mark bits associated with block h.
158: */
159: /*ARGSUSED*/
1.4 ! noro 160: # if defined(__STDC__) || defined(__cplusplus)
! 161: static void clear_marks_for_block(struct hblk *h, word dummy)
! 162: # else
! 163: static void clear_marks_for_block(h, dummy)
! 164: struct hblk *h;
! 165: word dummy;
! 166: # endif
1.1 noro 167: {
168: register hdr * hhdr = HDR(h);
169:
170: if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return;
171: /* Mark bit for these is cleared only once the object is */
172: /* explicitly deallocated. This either frees the block, or */
173: /* the bit is cleared once the object is on the free list. */
174: GC_clear_hdr_marks(hhdr);
175: }
176:
177: /* Slow but general routines for setting/clearing/asking about mark bits */
178: void GC_set_mark_bit(p)
179: ptr_t p;
180: {
181: register struct hblk *h = HBLKPTR(p);
182: register hdr * hhdr = HDR(h);
183: register int word_no = (word *)p - (word *)h;
184:
185: set_mark_bit_from_hdr(hhdr, word_no);
186: }
187:
188: void GC_clear_mark_bit(p)
189: ptr_t p;
190: {
191: register struct hblk *h = HBLKPTR(p);
192: register hdr * hhdr = HDR(h);
193: register int word_no = (word *)p - (word *)h;
194:
195: clear_mark_bit_from_hdr(hhdr, word_no);
196: }
197:
198: GC_bool GC_is_marked(p)
199: ptr_t p;
200: {
201: register struct hblk *h = HBLKPTR(p);
202: register hdr * hhdr = HDR(h);
203: register int word_no = (word *)p - (word *)h;
204:
205: return(mark_bit_from_hdr(hhdr, word_no));
206: }
207:
208:
209: /*
210: * Clear mark bits in all allocated heap blocks. This invalidates
211: * the marker invariant, and sets GC_mark_state to reflect this.
212: * (This implicitly starts marking to reestablish the invariant.)
213: */
214: void GC_clear_marks()
215: {
216: GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
217: GC_objects_are_marked = FALSE;
218: GC_mark_state = MS_INVALID;
219: scan_ptr = 0;
220: # ifdef GATHERSTATS
221: /* Counters reflect currently marked objects: reset here */
222: GC_composite_in_use = 0;
223: GC_atomic_in_use = 0;
224: # endif
225:
226: }
227:
228: /* Initiate a garbage collection. Initiates a full collection if the */
229: /* mark state is invalid. */
230: /*ARGSUSED*/
231: void GC_initiate_gc()
232: {
233: if (GC_dirty_maintained) GC_read_dirty();
234: # ifdef STUBBORN_ALLOC
235: GC_read_changed();
236: # endif
237: # ifdef CHECKSUMS
238: {
239: extern void GC_check_dirty();
240:
241: if (GC_dirty_maintained) GC_check_dirty();
242: }
243: # endif
1.4 ! noro 244: GC_n_rescuing_pages = 0;
1.1 noro 245: if (GC_mark_state == MS_NONE) {
246: GC_mark_state = MS_PUSH_RESCUERS;
247: } else if (GC_mark_state != MS_INVALID) {
248: ABORT("unexpected state");
249: } /* else this is really a full collection, and mark */
250: /* bits are invalid. */
251: scan_ptr = 0;
252: }
253:
254:
255: static void alloc_mark_stack();
256:
257: /* Perform a small amount of marking. */
258: /* We try to touch roughly a page of memory. */
259: /* Return TRUE if we just finished a mark phase. */
260: /* Cold_gc_frame is an address inside a GC frame that */
261: /* remains valid until all marking is complete. */
262: /* A zero value indicates that it's OK to miss some */
263: /* register values. */
264: GC_bool GC_mark_some(cold_gc_frame)
265: ptr_t cold_gc_frame;
266: {
1.3 noro 267: #ifdef MSWIN32
268: /* Windows 98 appears to asynchronously create and remove writable */
269: /* memory mappings, for reasons we haven't yet understood. Since */
270: /* we look for writable regions to determine the root set, we may */
271: /* try to mark from an address range that disappeared since we */
272: /* started the collection. Thus we have to recover from faults here. */
273: /* This code does not appear to be necessary for Windows 95/NT/2000. */
274: /* Note that this code should never generate an incremental GC write */
275: /* fault. */
276: __try {
277: #endif
1.1 noro 278: switch(GC_mark_state) {
279: case MS_NONE:
280: return(FALSE);
281:
282: case MS_PUSH_RESCUERS:
283: if (GC_mark_stack_top
1.4 ! noro 284: >= GC_mark_stack_limit - INITIAL_MARK_STACK_SIZE/2) {
1.2 noro 285: /* Go ahead and mark, even though that might cause us to */
286: /* see more marked dirty objects later on. Avoid this */
287: /* in the future. */
288: GC_mark_stack_too_small = TRUE;
1.4 ! noro 289: MARK_FROM_MARK_STACK();
1.1 noro 290: return(FALSE);
291: } else {
292: scan_ptr = GC_push_next_marked_dirty(scan_ptr);
293: if (scan_ptr == 0) {
1.4 ! noro 294: # ifdef CONDPRINT
! 295: if (GC_print_stats) {
1.1 noro 296: GC_printf1("Marked from %lu dirty pages\n",
297: (unsigned long)GC_n_rescuing_pages);
1.4 ! noro 298: }
1.1 noro 299: # endif
300: GC_push_roots(FALSE, cold_gc_frame);
301: GC_objects_are_marked = TRUE;
302: if (GC_mark_state != MS_INVALID) {
303: GC_mark_state = MS_ROOTS_PUSHED;
304: }
305: }
306: }
307: return(FALSE);
308:
309: case MS_PUSH_UNCOLLECTABLE:
310: if (GC_mark_stack_top
1.4 ! noro 311: >= GC_mark_stack + GC_mark_stack_size/4) {
! 312: # ifdef PARALLEL_MARK
! 313: /* Avoid this, since we don't parallelize the marker */
! 314: /* here. */
! 315: if (GC_parallel) GC_mark_stack_too_small = TRUE;
! 316: # endif
! 317: MARK_FROM_MARK_STACK();
1.1 noro 318: return(FALSE);
319: } else {
320: scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
321: if (scan_ptr == 0) {
322: GC_push_roots(TRUE, cold_gc_frame);
323: GC_objects_are_marked = TRUE;
324: if (GC_mark_state != MS_INVALID) {
325: GC_mark_state = MS_ROOTS_PUSHED;
326: }
327: }
328: }
329: return(FALSE);
330:
331: case MS_ROOTS_PUSHED:
1.4 ! noro 332: # ifdef PARALLEL_MARK
! 333: /* In the incremental GC case, this currently doesn't */
! 334: /* quite do the right thing, since it runs to */
! 335: /* completion. On the other hand, starting a */
! 336: /* parallel marker is expensive, so perhaps it is */
! 337: /* the right thing? */
! 338: /* Eventually, incremental marking should run */
! 339: /* asynchronously in multiple threads, without grabbing */
! 340: /* the allocation lock. */
! 341: if (GC_parallel) {
! 342: GC_do_parallel_mark();
! 343: GC_ASSERT(GC_mark_stack_top < GC_first_nonempty);
! 344: GC_mark_stack_top = GC_mark_stack - 1;
! 345: if (GC_mark_stack_too_small) {
! 346: alloc_mark_stack(2*GC_mark_stack_size);
! 347: }
! 348: if (GC_mark_state == MS_ROOTS_PUSHED) {
! 349: GC_mark_state = MS_NONE;
! 350: return(TRUE);
! 351: } else {
! 352: return(FALSE);
! 353: }
! 354: }
! 355: # endif
1.1 noro 356: if (GC_mark_stack_top >= GC_mark_stack) {
1.4 ! noro 357: MARK_FROM_MARK_STACK();
1.1 noro 358: return(FALSE);
359: } else {
360: GC_mark_state = MS_NONE;
361: if (GC_mark_stack_too_small) {
362: alloc_mark_stack(2*GC_mark_stack_size);
363: }
364: return(TRUE);
365: }
366:
367: case MS_INVALID:
368: case MS_PARTIALLY_INVALID:
369: if (!GC_objects_are_marked) {
370: GC_mark_state = MS_PUSH_UNCOLLECTABLE;
371: return(FALSE);
372: }
373: if (GC_mark_stack_top >= GC_mark_stack) {
1.4 ! noro 374: MARK_FROM_MARK_STACK();
1.1 noro 375: return(FALSE);
376: }
377: if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {
378: /* About to start a heap scan for marked objects. */
379: /* Mark stack is empty. OK to reallocate. */
380: if (GC_mark_stack_too_small) {
381: alloc_mark_stack(2*GC_mark_stack_size);
382: }
383: GC_mark_state = MS_PARTIALLY_INVALID;
384: }
385: scan_ptr = GC_push_next_marked(scan_ptr);
386: if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
387: GC_push_roots(TRUE, cold_gc_frame);
388: GC_objects_are_marked = TRUE;
389: if (GC_mark_state != MS_INVALID) {
390: GC_mark_state = MS_ROOTS_PUSHED;
391: }
392: }
393: return(FALSE);
394: default:
395: ABORT("GC_mark_some: bad state");
396: return(FALSE);
397: }
1.3 noro 398: #ifdef MSWIN32
399: } __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?
400: EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) {
1.4 ! noro 401: # ifdef CONDPRINT
! 402: if (GC_print_stats) {
1.3 noro 403: GC_printf0("Caught ACCESS_VIOLATION in marker. "
404: "Memory mapping disappeared.\n");
1.4 ! noro 405: }
! 406: # endif /* CONDPRINT */
1.3 noro 407: /* We have bad roots on the stack. Discard mark stack. */
408: /* Rescan from marked objects. Redetermine roots. */
409: GC_invalidate_mark_state();
410: scan_ptr = 0;
411: return FALSE;
412: }
413: #endif /* MSWIN32 */
1.1 noro 414: }
415:
416:
417: GC_bool GC_mark_stack_empty()
418: {
419: return(GC_mark_stack_top < GC_mark_stack);
420: }
421:
422: #ifdef PROF_MARKER
423: word GC_prof_array[10];
424: # define PROF(n) GC_prof_array[n]++
425: #else
426: # define PROF(n)
427: #endif
428:
429: /* Given a pointer to someplace other than a small object page or the */
430: /* first page of a large object, return a pointer either to the */
431: /* start of the large object or NIL. */
432: /* In the latter case black list the address current. */
433: /* Returns NIL without black listing if current points to a block */
434: /* with IGNORE_OFF_PAGE set. */
435: /*ARGSUSED*/
436: # ifdef PRINT_BLACK_LIST
1.3 noro 437: ptr_t GC_find_start(current, hhdr, source)
1.1 noro 438: word source;
439: # else
1.3 noro 440: ptr_t GC_find_start(current, hhdr)
1.1 noro 441: # define source 0
442: # endif
1.3 noro 443: register ptr_t current;
1.1 noro 444: register hdr * hhdr;
445: {
1.4 ! noro 446: if (GC_all_interior_pointers) {
1.1 noro 447: if (hhdr != 0) {
1.3 noro 448: register ptr_t orig = current;
1.1 noro 449:
1.4 ! noro 450: current = (ptr_t)HBLKPTR(current);
1.1 noro 451: do {
452: current = current - HBLKSIZE*(word)hhdr;
453: hhdr = HDR(current);
454: } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
455: /* current points to the start of the large object */
456: if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
457: if ((word *)orig - (word *)current
458: >= (ptrdiff_t)(hhdr->hb_sz)) {
459: /* Pointer past the end of the block */
1.4 ! noro 460: GC_ADD_TO_BLACK_LIST_NORMAL((word)orig, source);
1.1 noro 461: return(0);
462: }
463: return(current);
464: } else {
1.4 ! noro 465: GC_ADD_TO_BLACK_LIST_NORMAL((word)current, source);
1.1 noro 466: return(0);
467: }
1.4 ! noro 468: } else {
! 469: GC_ADD_TO_BLACK_LIST_NORMAL((word)current, source);
1.1 noro 470: return(0);
1.4 ! noro 471: }
1.1 noro 472: # undef source
473: }
474:
475: void GC_invalidate_mark_state()
476: {
477: GC_mark_state = MS_INVALID;
478: GC_mark_stack_top = GC_mark_stack-1;
479: }
480:
481: mse * GC_signal_mark_stack_overflow(msp)
482: mse * msp;
483: {
484: GC_mark_state = MS_INVALID;
485: GC_mark_stack_too_small = TRUE;
1.4 ! noro 486: # ifdef CONDPRINT
! 487: if (GC_print_stats) {
1.1 noro 488: GC_printf1("Mark stack overflow; current size = %lu entries\n",
489: GC_mark_stack_size);
1.4 ! noro 490: }
! 491: # endif
! 492: return(msp - GC_MARK_STACK_DISCARDS);
1.1 noro 493: }
494:
495: /*
496: * Mark objects pointed to by the regions described by
497: * mark stack entries between GC_mark_stack and GC_mark_stack_top,
498: * inclusive. Assumes the upper limit of a mark stack entry
499: * is never 0. A mark stack entry never has size 0.
500: * We try to traverse on the order of a hblk of memory before we return.
501: * Caller is responsible for calling this until the mark stack is empty.
1.3 noro 502: * Note that this is the most performance critical routine in the
503: * collector. Hence it contains all sorts of ugly hacks to speed
504: * things up. In particular, we avoid procedure calls on the common
505: * path, we take advantage of peculiarities of the mark descriptor
506: * encoding, we optionally maintain a cache for the block address to
507: * header mapping, we prefetch when an object is "grayed", etc.
1.1 noro 508: */
1.4 ! noro 509: mse * GC_mark_from(mark_stack_top, mark_stack, mark_stack_limit)
! 510: mse * mark_stack_top;
! 511: mse * mark_stack;
! 512: mse * mark_stack_limit;
1.1 noro 513: {
514: int credit = HBLKSIZE; /* Remaining credit for marking work */
515: register word * current_p; /* Pointer to current candidate ptr. */
516: register word current; /* Candidate pointer. */
517: register word * limit; /* (Incl) limit of current candidate */
518: /* range */
519: register word descr;
520: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
521: register ptr_t least_ha = GC_least_plausible_heap_addr;
1.3 noro 522: DECLARE_HDR_CACHE;
523:
1.1 noro 524: # define SPLIT_RANGE_WORDS 128 /* Must be power of 2. */
525:
526: GC_objects_are_marked = TRUE;
1.3 noro 527: INIT_HDR_CACHE;
1.1 noro 528: # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
1.4 ! noro 529: while (mark_stack_top >= mark_stack && credit >= 0) {
1.1 noro 530: # else
1.4 ! noro 531: while ((((ptr_t)mark_stack_top - (ptr_t)mark_stack) | credit)
1.1 noro 532: >= 0) {
533: # endif
1.4 ! noro 534: current_p = mark_stack_top -> mse_start;
! 535: descr = mark_stack_top -> mse_descr;
1.1 noro 536: retry:
1.3 noro 537: /* current_p and descr describe the current object. */
1.4 ! noro 538: /* *mark_stack_top is vacant. */
1.3 noro 539: /* The following is 0 only for small objects described by a simple */
540: /* length descriptor. For many applications this is the common */
541: /* case, so we try to detect it quickly. */
1.4 ! noro 542: if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | GC_DS_TAGS)) {
! 543: word tag = descr & GC_DS_TAGS;
1.1 noro 544:
545: switch(tag) {
1.4 ! noro 546: case GC_DS_LENGTH:
1.1 noro 547: /* Large length. */
548: /* Process part of the range to avoid pushing too much on the */
549: /* stack. */
1.4 ! noro 550: # ifdef PARALLEL_MARK
! 551: # define SHARE_BYTES 2048
! 552: if (descr > SHARE_BYTES && GC_parallel
! 553: && mark_stack_top < mark_stack_limit - 1) {
! 554: int new_size = (descr/2) & ~(sizeof(word)-1);
! 555: GC_ASSERT(descr < GC_greatest_plausible_heap_addr
! 556: - GC_least_plausible_heap_addr);
! 557: mark_stack_top -> mse_start = current_p;
! 558: mark_stack_top -> mse_descr = new_size + sizeof(word);
! 559: /* makes sure we handle */
! 560: /* misaligned pointers. */
! 561: mark_stack_top++;
! 562: current_p = (word *) ((char *)current_p + new_size);
! 563: descr -= new_size;
! 564: goto retry;
! 565: }
! 566: # endif /* PARALLEL_MARK */
! 567: mark_stack_top -> mse_start =
1.1 noro 568: limit = current_p + SPLIT_RANGE_WORDS-1;
1.4 ! noro 569: mark_stack_top -> mse_descr =
1.3 noro 570: descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
1.1 noro 571: /* Make sure that pointers overlapping the two ranges are */
572: /* considered. */
573: limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
574: break;
1.4 ! noro 575: case GC_DS_BITMAP:
! 576: mark_stack_top--;
! 577: descr &= ~GC_DS_TAGS;
1.1 noro 578: credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
579: while (descr != 0) {
580: if ((signed_word)descr < 0) {
581: current = *current_p;
582: if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
1.3 noro 583: PREFETCH(current);
1.4 ! noro 584: HC_PUSH_CONTENTS((ptr_t)current, mark_stack_top,
1.3 noro 585: mark_stack_limit, current_p, exit1);
1.1 noro 586: }
587: }
588: descr <<= 1;
589: ++ current_p;
590: }
591: continue;
1.4 ! noro 592: case GC_DS_PROC:
! 593: mark_stack_top--;
! 594: credit -= GC_PROC_BYTES;
! 595: mark_stack_top =
1.1 noro 596: (*PROC(descr))
1.4 ! noro 597: (current_p, mark_stack_top,
1.1 noro 598: mark_stack_limit, ENV(descr));
599: continue;
1.4 ! noro 600: case GC_DS_PER_OBJECT:
1.3 noro 601: if ((signed_word)descr >= 0) {
602: /* Descriptor is in the object. */
1.4 ! noro 603: descr = *(word *)((ptr_t)current_p + descr - GC_DS_PER_OBJECT);
1.3 noro 604: } else {
605: /* Descriptor is in type descriptor pointed to by first */
606: /* word in object. */
607: ptr_t type_descr = *(ptr_t *)current_p;
608: /* type_descr is either a valid pointer to the descriptor */
609: /* structure, or this object was on a free list. If it */
610: /* it was anything but the last object on the free list, */
611: /* we will misinterpret the next object on the free list as */
612: /* the type descriptor, and get a 0 GC descriptor, which */
613: /* is ideal. Unfortunately, we need to check for the last */
614: /* object case explicitly. */
615: if (0 == type_descr) {
616: /* Rarely executed. */
1.4 ! noro 617: mark_stack_top--;
1.3 noro 618: continue;
619: }
620: descr = *(word *)(type_descr
1.4 ! noro 621: - (descr - (GC_DS_PER_OBJECT
! 622: - GC_INDIR_PER_OBJ_BIAS)));
1.3 noro 623: }
624: if (0 == descr) {
1.4 ! noro 625: /* Can happen either because we generated a 0 descriptor */
! 626: /* or we saw a pointer to a free object. */
! 627: mark_stack_top--;
! 628: continue;
1.3 noro 629: }
1.1 noro 630: goto retry;
631: }
1.3 noro 632: } else /* Small object with length descriptor */ {
1.4 ! noro 633: mark_stack_top--;
1.1 noro 634: limit = (word *)(((ptr_t)current_p) + (word)descr);
635: }
636: /* The simple case in which we're scanning a range. */
1.4 ! noro 637: GC_ASSERT(!((word)current_p & (ALIGNMENT-1)));
1.1 noro 638: credit -= (ptr_t)limit - (ptr_t)current_p;
639: limit -= 1;
1.3 noro 640: {
641: # define PREF_DIST 4
642:
643: # ifndef SMALL_CONFIG
644: word deferred;
645:
646: /* Try to prefetch the next pointer to be examined asap. */
647: /* Empirically, this also seems to help slightly without */
648: /* prefetches, at least on linux/X86. Presumably this loop */
649: /* ends up with less register pressure, and gcc thus ends up */
650: /* generating slightly better code. Overall gcc code quality */
651: /* for this loop is still not great. */
652: for(;;) {
653: PREFETCH((ptr_t)limit - PREF_DIST*CACHE_LINE_SIZE);
1.4 ! noro 654: GC_ASSERT(limit >= current_p);
1.3 noro 655: deferred = *limit;
656: limit = (word *)((char *)limit - ALIGNMENT);
657: if ((ptr_t)deferred >= least_ha && (ptr_t)deferred < greatest_ha) {
658: PREFETCH(deferred);
659: break;
660: }
661: if (current_p > limit) goto next_object;
662: /* Unroll once, so we don't do too many of the prefetches */
663: /* based on limit. */
664: deferred = *limit;
665: limit = (word *)((char *)limit - ALIGNMENT);
666: if ((ptr_t)deferred >= least_ha && (ptr_t)deferred < greatest_ha) {
667: PREFETCH(deferred);
668: break;
669: }
670: if (current_p > limit) goto next_object;
671: }
672: # endif
673:
674: while (current_p <= limit) {
675: /* Empirically, unrolling this loop doesn't help a lot. */
676: /* Since HC_PUSH_CONTENTS expands to a lot of code, */
677: /* we don't. */
678: current = *current_p;
679: PREFETCH((ptr_t)current_p + PREF_DIST*CACHE_LINE_SIZE);
680: if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
681: /* Prefetch the contents of the object we just pushed. It's */
682: /* likely we will need them soon. */
683: PREFETCH(current);
1.4 ! noro 684: HC_PUSH_CONTENTS((ptr_t)current, mark_stack_top,
1.3 noro 685: mark_stack_limit, current_p, exit2);
686: }
687: current_p = (word *)((char *)current_p + ALIGNMENT);
1.1 noro 688: }
1.3 noro 689:
690: # ifndef SMALL_CONFIG
691: /* We still need to mark the entry we previously prefetched. */
692: /* We alrady know that it passes the preliminary pointer */
693: /* validity test. */
1.4 ! noro 694: HC_PUSH_CONTENTS((ptr_t)deferred, mark_stack_top,
1.3 noro 695: mark_stack_limit, current_p, exit4);
696: next_object:;
697: # endif
1.1 noro 698: }
699: }
1.4 ! noro 700: return mark_stack_top;
! 701: }
! 702:
! 703: #ifdef PARALLEL_MARK
! 704:
! 705: /* We assume we have an ANSI C Compiler. */
! 706: GC_bool GC_help_wanted = FALSE;
! 707: unsigned GC_helper_count = 0;
! 708: unsigned GC_active_count = 0;
! 709: mse * VOLATILE GC_first_nonempty;
! 710: word GC_mark_no = 0;
! 711:
! 712: #define LOCAL_MARK_STACK_SIZE HBLKSIZE
! 713: /* Under normal circumstances, this is big enough to guarantee */
! 714: /* We don't overflow half of it in a single call to */
! 715: /* GC_mark_from. */
! 716:
! 717:
! 718: /* Steal mark stack entries starting at mse low into mark stack local */
! 719: /* until we either steal mse high, or we have max entries. */
! 720: /* Return a pointer to the top of the local mark stack. */
! 721: /* *next is replaced by a pointer to the next unscanned mark stack */
! 722: /* entry. */
! 723: mse * GC_steal_mark_stack(mse * low, mse * high, mse * local,
! 724: unsigned max, mse **next)
! 725: {
! 726: mse *p;
! 727: mse *top = local - 1;
! 728: unsigned i = 0;
! 729:
! 730: GC_ASSERT(high >= low-1 && high - low + 1 <= GC_mark_stack_size);
! 731: for (p = low; p <= high && i <= max; ++p) {
! 732: word descr = *(volatile word *) &(p -> mse_descr);
! 733: if (descr != 0) {
! 734: *(volatile word *) &(p -> mse_descr) = 0;
! 735: ++top;
! 736: top -> mse_descr = descr;
! 737: top -> mse_start = p -> mse_start;
! 738: GC_ASSERT( top -> mse_descr & GC_DS_TAGS != GC_DS_LENGTH ||
! 739: top -> mse_descr < GC_greatest_plausible_heap_addr
! 740: - GC_least_plausible_heap_addr);
! 741: /* There is no synchronization here. We assume that at */
! 742: /* least one thread will see the original descriptor. */
! 743: /* Otherwise we need a barrier. */
! 744: /* More than one thread may get this entry, but that's only */
! 745: /* a minor performance problem. */
! 746: /* If this is a big object, count it as */
! 747: /* size/256 + 1 objects. */
! 748: ++i;
! 749: if ((descr & GC_DS_TAGS) == GC_DS_LENGTH) i += (descr >> 8);
! 750: }
! 751: }
! 752: *next = p;
! 753: return top;
! 754: }
! 755:
! 756: /* Copy back a local mark stack. */
! 757: /* low and high are inclusive bounds. */
! 758: void GC_return_mark_stack(mse * low, mse * high)
! 759: {
! 760: mse * my_top;
! 761: mse * my_start;
! 762: size_t stack_size;
! 763:
! 764: if (high < low) return;
! 765: stack_size = high - low + 1;
! 766: GC_acquire_mark_lock();
! 767: my_top = GC_mark_stack_top;
! 768: my_start = my_top + 1;
! 769: if (my_start - GC_mark_stack + stack_size > GC_mark_stack_size) {
! 770: # ifdef CONDPRINT
! 771: if (GC_print_stats) {
! 772: GC_printf0("No room to copy back mark stack.");
! 773: }
! 774: # endif
! 775: GC_mark_state = MS_INVALID;
! 776: GC_mark_stack_too_small = TRUE;
! 777: /* We drop the local mark stack. We'll fix things later. */
! 778: } else {
! 779: BCOPY(low, my_start, stack_size * sizeof(mse));
! 780: GC_ASSERT(GC_mark_stack_top = my_top);
! 781: # if !defined(IA64) && !defined(HP_PA)
! 782: GC_memory_write_barrier();
! 783: # endif
! 784: /* On IA64, the volatile write acts as a release barrier. */
! 785: GC_mark_stack_top = my_top + stack_size;
! 786: }
! 787: GC_release_mark_lock();
! 788: GC_notify_all_marker();
1.1 noro 789: }
790:
1.4 ! noro 791: /* Mark from the local mark stack. */
! 792: /* On return, the local mark stack is empty. */
! 793: /* But this may be achieved by copying the */
! 794: /* local mark stack back into the global one. */
! 795: void GC_do_local_mark(mse *local_mark_stack, mse *local_top)
! 796: {
! 797: unsigned n;
! 798: # define N_LOCAL_ITERS 1
! 799:
! 800: # ifdef GC_ASSERTIONS
! 801: /* Make sure we don't hold mark lock. */
! 802: GC_acquire_mark_lock();
! 803: GC_release_mark_lock();
! 804: # endif
! 805: for (;;) {
! 806: for (n = 0; n < N_LOCAL_ITERS; ++n) {
! 807: local_top = GC_mark_from(local_top, local_mark_stack,
! 808: local_mark_stack + LOCAL_MARK_STACK_SIZE);
! 809: if (local_top < local_mark_stack) return;
! 810: if (local_top - local_mark_stack >= LOCAL_MARK_STACK_SIZE/2) {
! 811: GC_return_mark_stack(local_mark_stack, local_top);
! 812: return;
! 813: }
! 814: }
! 815: if (GC_mark_stack_top < GC_first_nonempty &&
! 816: GC_active_count < GC_helper_count
! 817: && local_top > local_mark_stack + 1) {
! 818: /* Try to share the load, since the main stack is empty, */
! 819: /* and helper threads are waiting for a refill. */
! 820: /* The entries near the bottom of the stack are likely */
! 821: /* to require more work. Thus we return those, eventhough */
! 822: /* it's harder. */
! 823: mse * p;
! 824: mse * new_bottom = local_mark_stack
! 825: + (local_top - local_mark_stack)/2;
! 826: GC_ASSERT(new_bottom > local_mark_stack
! 827: && new_bottom < local_top);
! 828: GC_return_mark_stack(local_mark_stack, new_bottom - 1);
! 829: memmove(local_mark_stack, new_bottom,
! 830: (local_top - new_bottom + 1) * sizeof(mse));
! 831: local_top -= (new_bottom - local_mark_stack);
! 832: }
! 833: }
! 834: }
! 835:
! 836: #define ENTRIES_TO_GET 5
! 837:
! 838: long GC_markers = 2; /* Normally changed by thread-library- */
! 839: /* -specific code. */
! 840:
! 841: /* Mark using the local mark stack until the global mark stack is empty */
! 842: /* and ther are no active workers. Update GC_first_nonempty to reflect */
! 843: /* progress. */
! 844: /* Caller does not hold mark lock. */
! 845: /* Caller has already incremented GC_helper_count. We decrement it, */
! 846: /* and maintain GC_active_count. */
! 847: void GC_mark_local(mse *local_mark_stack, int id)
! 848: {
! 849: mse * my_first_nonempty;
! 850:
! 851: GC_acquire_mark_lock();
! 852: GC_active_count++;
! 853: my_first_nonempty = GC_first_nonempty;
! 854: GC_ASSERT(GC_first_nonempty >= GC_mark_stack &&
! 855: GC_first_nonempty <= GC_mark_stack_top + 1);
! 856: # ifdef PRINTSTATS
! 857: GC_printf1("Starting mark helper %lu\n", (unsigned long)id);
! 858: # endif
! 859: GC_release_mark_lock();
! 860: for (;;) {
! 861: size_t n_on_stack;
! 862: size_t n_to_get;
! 863: mse *next;
! 864: mse * my_top;
! 865: mse * local_top;
! 866: mse * global_first_nonempty = GC_first_nonempty;
! 867:
! 868: GC_ASSERT(my_first_nonempty >= GC_mark_stack &&
! 869: my_first_nonempty <= GC_mark_stack_top + 1);
! 870: GC_ASSERT(global_first_nonempty >= GC_mark_stack &&
! 871: global_first_nonempty <= GC_mark_stack_top + 1);
! 872: if (my_first_nonempty < global_first_nonempty) {
! 873: my_first_nonempty = global_first_nonempty;
! 874: } else if (global_first_nonempty < my_first_nonempty) {
! 875: GC_compare_and_exchange((word *)(&GC_first_nonempty),
! 876: (word) global_first_nonempty,
! 877: (word) my_first_nonempty);
! 878: /* If this fails, we just go ahead, without updating */
! 879: /* GC_first_nonempty. */
! 880: }
! 881: /* Perhaps we should also update GC_first_nonempty, if it */
! 882: /* is less. But that would require using atomic updates. */
! 883: my_top = GC_mark_stack_top;
! 884: n_on_stack = my_top - my_first_nonempty + 1;
! 885: if (0 == n_on_stack) {
! 886: GC_acquire_mark_lock();
! 887: my_top = GC_mark_stack_top;
! 888: n_on_stack = my_top - my_first_nonempty + 1;
! 889: if (0 == n_on_stack) {
! 890: GC_active_count--;
! 891: GC_ASSERT(GC_active_count <= GC_helper_count);
! 892: /* Other markers may redeposit objects */
! 893: /* on the stack. */
! 894: if (0 == GC_active_count) GC_notify_all_marker();
! 895: while (GC_active_count > 0
! 896: && GC_first_nonempty > GC_mark_stack_top) {
! 897: /* We will be notified if either GC_active_count */
! 898: /* reaches zero, or if more objects are pushed on */
! 899: /* the global mark stack. */
! 900: GC_wait_marker();
! 901: }
! 902: if (GC_active_count == 0 &&
! 903: GC_first_nonempty > GC_mark_stack_top) {
! 904: GC_bool need_to_notify = FALSE;
! 905: /* The above conditions can't be falsified while we */
! 906: /* hold the mark lock, since neither */
! 907: /* GC_active_count nor GC_mark_stack_top can */
! 908: /* change. GC_first_nonempty can only be */
! 909: /* incremented asynchronously. Thus we know that */
! 910: /* both conditions actually held simultaneously. */
! 911: GC_helper_count--;
! 912: if (0 == GC_helper_count) need_to_notify = TRUE;
! 913: # ifdef PRINTSTATS
! 914: GC_printf1(
! 915: "Finished mark helper %lu\n", (unsigned long)id);
! 916: # endif
! 917: GC_release_mark_lock();
! 918: if (need_to_notify) GC_notify_all_marker();
! 919: return;
! 920: }
! 921: /* else there's something on the stack again, or */
! 922: /* another help may push something. */
! 923: GC_active_count++;
! 924: GC_ASSERT(GC_active_count > 0);
! 925: GC_release_mark_lock();
! 926: continue;
! 927: } else {
! 928: GC_release_mark_lock();
! 929: }
! 930: }
! 931: n_to_get = ENTRIES_TO_GET;
! 932: if (n_on_stack < 2 * ENTRIES_TO_GET) n_to_get = 1;
! 933: local_top = GC_steal_mark_stack(my_first_nonempty, my_top,
! 934: local_mark_stack, n_to_get,
! 935: &my_first_nonempty);
! 936: GC_ASSERT(my_first_nonempty >= GC_mark_stack &&
! 937: my_first_nonempty <= GC_mark_stack_top + 1);
! 938: GC_do_local_mark(local_mark_stack, local_top);
! 939: }
! 940: }
! 941:
! 942: /* Perform Parallel mark. */
! 943: /* We hold the GC lock, not the mark lock. */
! 944: /* Currently runs until the mark stack is */
! 945: /* empty. */
! 946: void GC_do_parallel_mark()
! 947: {
! 948: mse local_mark_stack[LOCAL_MARK_STACK_SIZE];
! 949: mse * local_top;
! 950: mse * my_top;
! 951:
! 952: GC_acquire_mark_lock();
! 953: GC_ASSERT(I_HOLD_LOCK());
! 954: GC_ASSERT(!GC_help_wanted);
! 955: GC_ASSERT(GC_active_count == 0);
! 956: # ifdef PRINTSTATS
! 957: GC_printf1("Starting marking for mark phase number %lu\n",
! 958: (unsigned long)GC_mark_no);
! 959: # endif
! 960: GC_first_nonempty = GC_mark_stack;
! 961: GC_active_count = 0;
! 962: GC_helper_count = 1;
! 963: GC_help_wanted = TRUE;
! 964: GC_release_mark_lock();
! 965: GC_notify_all_marker();
! 966: /* Wake up potential helpers. */
! 967: GC_mark_local(local_mark_stack, 0);
! 968: GC_acquire_mark_lock();
! 969: GC_help_wanted = FALSE;
! 970: /* Done; clean up. */
! 971: while (GC_helper_count > 0) GC_wait_marker();
! 972: /* GC_helper_count cannot be incremented while GC_help_wanted == FALSE */
! 973: # ifdef PRINTSTATS
! 974: GC_printf1(
! 975: "Finished marking for mark phase number %lu\n",
! 976: (unsigned long)GC_mark_no);
! 977: # endif
! 978: GC_mark_no++;
! 979: GC_release_mark_lock();
! 980: GC_notify_all_marker();
! 981: }
! 982:
! 983:
! 984: /* Try to help out the marker, if it's running. */
! 985: /* We do not hold the GC lock, but the requestor does. */
! 986: void GC_help_marker(word my_mark_no)
! 987: {
! 988: mse local_mark_stack[LOCAL_MARK_STACK_SIZE];
! 989: unsigned my_id;
! 990: mse * my_first_nonempty;
! 991:
! 992: if (!GC_parallel) return;
! 993: GC_acquire_mark_lock();
! 994: while (GC_mark_no < my_mark_no
! 995: || !GC_help_wanted && GC_mark_no == my_mark_no) {
! 996: GC_wait_marker();
! 997: }
! 998: my_id = GC_helper_count;
! 999: if (GC_mark_no != my_mark_no || my_id >= GC_markers) {
! 1000: /* Second test is useful only if original threads can also */
! 1001: /* act as helpers. Under Linux they can't. */
! 1002: GC_release_mark_lock();
! 1003: return;
! 1004: }
! 1005: GC_helper_count = my_id + 1;
! 1006: GC_release_mark_lock();
! 1007: GC_mark_local(local_mark_stack, my_id);
! 1008: /* GC_mark_local decrements GC_helper_count. */
! 1009: }
! 1010:
! 1011: #endif /* PARALLEL_MARK */
! 1012:
1.1 noro 1013: /* Allocate or reallocate space for mark stack of size s words */
1014: /* May silently fail. */
1015: static void alloc_mark_stack(n)
1016: word n;
1017: {
1.4 ! noro 1018: mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct GC_ms_entry));
1.1 noro 1019:
1020: GC_mark_stack_too_small = FALSE;
1021: if (GC_mark_stack_size != 0) {
1022: if (new_stack != 0) {
1023: word displ = (word)GC_mark_stack & (GC_page_size - 1);
1.4 ! noro 1024: signed_word size = GC_mark_stack_size * sizeof(struct GC_ms_entry);
1.1 noro 1025:
1026: /* Recycle old space */
1027: if (0 != displ) displ = GC_page_size - displ;
1028: size = (size - displ) & ~(GC_page_size - 1);
1029: if (size > 0) {
1030: GC_add_to_heap((struct hblk *)
1031: ((word)GC_mark_stack + displ), (word)size);
1032: }
1033: GC_mark_stack = new_stack;
1034: GC_mark_stack_size = n;
1.4 ! noro 1035: GC_mark_stack_limit = new_stack + n;
! 1036: # ifdef CONDPRINT
! 1037: if (GC_print_stats) {
1.1 noro 1038: GC_printf1("Grew mark stack to %lu frames\n",
1039: (unsigned long) GC_mark_stack_size);
1.4 ! noro 1040: }
1.1 noro 1041: # endif
1042: } else {
1.4 ! noro 1043: # ifdef CONDPRINT
! 1044: if (GC_print_stats) {
1.1 noro 1045: GC_printf1("Failed to grow mark stack to %lu frames\n",
1046: (unsigned long) n);
1.4 ! noro 1047: }
1.1 noro 1048: # endif
1049: }
1050: } else {
1051: if (new_stack == 0) {
1052: GC_err_printf0("No space for mark stack\n");
1053: EXIT();
1054: }
1055: GC_mark_stack = new_stack;
1056: GC_mark_stack_size = n;
1.4 ! noro 1057: GC_mark_stack_limit = new_stack + n;
1.1 noro 1058: }
1059: GC_mark_stack_top = GC_mark_stack-1;
1060: }
1061:
1062: void GC_mark_init()
1063: {
1064: alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
1065: }
1066:
1067: /*
1068: * Push all locations between b and t onto the mark stack.
1069: * b is the first location to be checked. t is one past the last
1070: * location to be checked.
1071: * Should only be used if there is no possibility of mark stack
1072: * overflow.
1073: */
1074: void GC_push_all(bottom, top)
1075: ptr_t bottom;
1076: ptr_t top;
1077: {
1078: register word length;
1079:
1080: bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1081: top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
1082: if (top == 0 || bottom == top) return;
1083: GC_mark_stack_top++;
1.4 ! noro 1084: if (GC_mark_stack_top >= GC_mark_stack_limit) {
1.1 noro 1085: ABORT("unexpected mark stack overflow");
1086: }
1087: length = top - bottom;
1.4 ! noro 1088: # if GC_DS_TAGS > ALIGNMENT - 1
! 1089: length += GC_DS_TAGS;
! 1090: length &= ~GC_DS_TAGS;
1.1 noro 1091: # endif
1092: GC_mark_stack_top -> mse_start = (word *)bottom;
1093: GC_mark_stack_top -> mse_descr = length;
1094: }
1095:
1096: /*
1.4 ! noro 1097: * Analogous to the above, but push only those pages h with dirty_fn(h) != 0.
1.1 noro 1098: * We use push_fn to actually push the block.
1.4 ! noro 1099: * Used both to selectively push dirty pages, or to push a block
! 1100: * in piecemeal fashion, to allow for more marking concurrency.
1.1 noro 1101: * Will not overflow mark stack if push_fn pushes a small fixed number
1102: * of entries. (This is invoked only if push_fn pushes a single entry,
1103: * or if it marks each object before pushing it, thus ensuring progress
1104: * in the event of a stack overflow.)
1105: */
1.4 ! noro 1106: void GC_push_selected(bottom, top, dirty_fn, push_fn)
1.1 noro 1107: ptr_t bottom;
1108: ptr_t top;
1.4 ! noro 1109: int (*dirty_fn) GC_PROTO((struct hblk * h));
! 1110: void (*push_fn) GC_PROTO((ptr_t bottom, ptr_t top));
1.1 noro 1111: {
1112: register struct hblk * h;
1113:
1114: bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1115: top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
1116:
1117: if (top == 0 || bottom == top) return;
1118: h = HBLKPTR(bottom + HBLKSIZE);
1119: if (top <= (ptr_t) h) {
1120: if ((*dirty_fn)(h-1)) {
1121: (*push_fn)(bottom, top);
1122: }
1123: return;
1124: }
1125: if ((*dirty_fn)(h-1)) {
1126: (*push_fn)(bottom, (ptr_t)h);
1127: }
1128: while ((ptr_t)(h+1) <= top) {
1129: if ((*dirty_fn)(h)) {
1130: if ((word)(GC_mark_stack_top - GC_mark_stack)
1131: > 3 * GC_mark_stack_size / 4) {
1132: /* Danger of mark stack overflow */
1133: (*push_fn)((ptr_t)h, top);
1134: return;
1135: } else {
1136: (*push_fn)((ptr_t)h, (ptr_t)(h+1));
1137: }
1138: }
1139: h++;
1140: }
1141: if ((ptr_t)h != top) {
1142: if ((*dirty_fn)(h)) {
1143: (*push_fn)((ptr_t)h, top);
1144: }
1145: }
1.4 ! noro 1146: if (GC_mark_stack_top >= GC_mark_stack_limit) {
1.1 noro 1147: ABORT("unexpected mark stack overflow");
1148: }
1149: }
1150:
1151: # ifndef SMALL_CONFIG
1.4 ! noro 1152:
! 1153: #ifdef PARALLEL_MARK
! 1154: /* Break up root sections into page size chunks to better spread */
! 1155: /* out work. */
! 1156: GC_bool GC_true_func(struct hblk *h) { return TRUE; }
! 1157: # define GC_PUSH_ALL(b,t) GC_push_selected(b,t,GC_true_func,GC_push_all);
! 1158: #else
! 1159: # define GC_PUSH_ALL(b,t) GC_push_all(b,t);
! 1160: #endif
! 1161:
! 1162:
1.1 noro 1163: void GC_push_conditional(bottom, top, all)
1164: ptr_t bottom;
1165: ptr_t top;
1166: int all;
1167: {
1168: if (all) {
1169: if (GC_dirty_maintained) {
1170: # ifdef PROC_VDB
1171: /* Pages that were never dirtied cannot contain pointers */
1.4 ! noro 1172: GC_push_selected(bottom, top, GC_page_was_ever_dirty, GC_push_all);
1.1 noro 1173: # else
1174: GC_push_all(bottom, top);
1175: # endif
1176: } else {
1177: GC_push_all(bottom, top);
1178: }
1179: } else {
1.4 ! noro 1180: GC_push_selected(bottom, top, GC_page_was_dirty, GC_push_all);
1.1 noro 1181: }
1182: }
1183: #endif
1184:
1.4 ! noro 1185: # if defined(MSWIN32) || defined(MSWINCE)
1.1 noro 1186: void __cdecl GC_push_one(p)
1187: # else
1188: void GC_push_one(p)
1189: # endif
1190: word p;
1191: {
1.3 noro 1192: GC_PUSH_ONE_STACK(p, MARKED_FROM_REGISTER);
1.1 noro 1193: }
1194:
1.4 ! noro 1195: struct GC_ms_entry *GC_mark_and_push(obj, mark_stack_ptr, mark_stack_limit, src)
! 1196: GC_PTR obj;
! 1197: struct GC_ms_entry * mark_stack_ptr;
! 1198: struct GC_ms_entry * mark_stack_limit;
! 1199: GC_PTR *src;
! 1200: {
! 1201: PREFETCH(obj);
! 1202: PUSH_CONTENTS(obj, mark_stack_ptr /* modified */, mark_stack_limit, src,
! 1203: was_marked /* internally generated exit label */);
! 1204: return mark_stack_ptr;
! 1205: }
! 1206:
1.1 noro 1207: # ifdef __STDC__
1208: # define BASE(p) (word)GC_base((void *)(p))
1209: # else
1210: # define BASE(p) (word)GC_base((char *)(p))
1211: # endif
1212:
1.4 ! noro 1213: /* Mark and push (i.e. gray) a single object p onto the main */
! 1214: /* mark stack. Consider p to be valid if it is an interior */
! 1215: /* pointer. */
! 1216: /* The object p has passed a preliminary pointer validity */
! 1217: /* test, but we do not definitely know whether it is valid. */
! 1218: /* Mark bits are NOT atomically updated. Thus this must be the */
! 1219: /* only thread setting them. */
1.1 noro 1220: # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
1.4 ! noro 1221: void GC_mark_and_push_stack(p, source)
1.1 noro 1222: ptr_t source;
1223: # else
1.4 ! noro 1224: void GC_mark_and_push_stack(p)
1.1 noro 1225: # define source 0
1226: # endif
1227: register word p;
1228: {
1229: register word r;
1230: register hdr * hhdr;
1231: register int displ;
1232:
1233: GET_HDR(p, hhdr);
1234: if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
1.4 ! noro 1235: if (hhdr != 0) {
1.1 noro 1236: r = BASE(p);
1237: hhdr = HDR(r);
1238: displ = BYTES_TO_WORDS(HBLKDISPL(r));
1239: }
1240: } else {
1241: register map_entry_type map_entry;
1242:
1243: displ = HBLKDISPL(p);
1244: map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
1.4 ! noro 1245: if (map_entry >= MAX_OFFSET) {
! 1246: if (map_entry == OFFSET_TOO_BIG || !GC_all_interior_pointers) {
1.1 noro 1247: r = BASE(p);
1248: displ = BYTES_TO_WORDS(HBLKDISPL(r));
1249: if (r == 0) hhdr = 0;
1.4 ! noro 1250: } else {
! 1251: /* Offset invalid, but map reflects interior pointers */
1.1 noro 1252: hhdr = 0;
1.4 ! noro 1253: }
1.1 noro 1254: } else {
1255: displ = BYTES_TO_WORDS(displ);
1256: displ -= map_entry;
1257: r = (word)((word *)(HBLKPTR(p)) + displ);
1258: }
1259: }
1260: /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
1261: /* displ is the word index within the block. */
1262: if (hhdr == 0) {
1.4 ! noro 1263: # ifdef PRINT_BLACK_LIST
! 1264: GC_add_to_black_list_stack(p, source);
! 1265: # else
! 1266: GC_add_to_black_list_stack(p);
! 1267: # endif
! 1268: # undef source /* In case we had to define it. */
1.1 noro 1269: } else {
1270: if (!mark_bit_from_hdr(hhdr, displ)) {
1271: set_mark_bit_from_hdr(hhdr, displ);
1272: GC_STORE_BACK_PTR(source, (ptr_t)r);
1273: PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
1.4 ! noro 1274: GC_mark_stack_limit);
1.1 noro 1275: }
1276: }
1277: }
1278:
1279: # ifdef TRACE_BUF
1280:
1281: # define TRACE_ENTRIES 1000
1282:
1283: struct trace_entry {
1284: char * kind;
1285: word gc_no;
1286: word words_allocd;
1287: word arg1;
1288: word arg2;
1289: } GC_trace_buf[TRACE_ENTRIES];
1290:
1291: int GC_trace_buf_ptr = 0;
1292:
1293: void GC_add_trace_entry(char *kind, word arg1, word arg2)
1294: {
1295: GC_trace_buf[GC_trace_buf_ptr].kind = kind;
1296: GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
1297: GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
1298: GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
1299: GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
1300: GC_trace_buf_ptr++;
1301: if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
1302: }
1303:
1304: void GC_print_trace(word gc_no, GC_bool lock)
1305: {
1306: int i;
1307: struct trace_entry *p;
1308:
1309: if (lock) LOCK();
1310: for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
1311: if (i < 0) i = TRACE_ENTRIES-1;
1312: p = GC_trace_buf + i;
1313: if (p -> gc_no < gc_no || p -> kind == 0) return;
1314: printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
1315: p -> kind, p -> gc_no, p -> words_allocd,
1316: (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
1317: }
1318: printf("Trace incomplete\n");
1319: if (lock) UNLOCK();
1320: }
1321:
1322: # endif /* TRACE_BUF */
1323:
1324: /*
1325: * A version of GC_push_all that treats all interior pointers as valid
1326: * and scans the entire region immediately, in case the contents
1327: * change.
1328: */
1329: void GC_push_all_eager(bottom, top)
1330: ptr_t bottom;
1331: ptr_t top;
1332: {
1333: word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1334: word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
1335: register word *p;
1336: register word q;
1337: register word *lim;
1338: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1339: register ptr_t least_ha = GC_least_plausible_heap_addr;
1340: # define GC_greatest_plausible_heap_addr greatest_ha
1341: # define GC_least_plausible_heap_addr least_ha
1342:
1343: if (top == 0) return;
1344: /* check all pointers in range and put in push if they appear */
1345: /* to be valid. */
1346: lim = t - 1 /* longword */;
1347: for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
1348: q = *p;
1349: GC_PUSH_ONE_STACK(q, p);
1350: }
1351: # undef GC_greatest_plausible_heap_addr
1352: # undef GC_least_plausible_heap_addr
1353: }
1354:
1355: #ifndef THREADS
1356: /*
1357: * A version of GC_push_all that treats all interior pointers as valid
1358: * and scans part of the area immediately, to make sure that saved
1359: * register values are not lost.
1360: * Cold_gc_frame delimits the stack section that must be scanned
1361: * eagerly. A zero value indicates that no eager scanning is needed.
1362: */
1363: void GC_push_all_stack_partially_eager(bottom, top, cold_gc_frame)
1364: ptr_t bottom;
1365: ptr_t top;
1366: ptr_t cold_gc_frame;
1367: {
1.4 ! noro 1368: if (GC_all_interior_pointers) {
1.1 noro 1369: # define EAGER_BYTES 1024
1370: /* Push the hot end of the stack eagerly, so that register values */
1371: /* saved inside GC frames are marked before they disappear. */
1372: /* The rest of the marking can be deferred until later. */
1373: if (0 == cold_gc_frame) {
1374: GC_push_all_stack(bottom, top);
1375: return;
1376: }
1377: # ifdef STACK_GROWS_DOWN
1378: GC_push_all_eager(bottom, cold_gc_frame);
1379: GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
1380: # else /* STACK_GROWS_UP */
1381: GC_push_all_eager(cold_gc_frame, top);
1382: GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
1383: # endif /* STACK_GROWS_UP */
1.4 ! noro 1384: } else {
1.1 noro 1385: GC_push_all_eager(bottom, top);
1.4 ! noro 1386: }
1.1 noro 1387: # ifdef TRACE_BUF
1388: GC_add_trace_entry("GC_push_all_stack", bottom, top);
1389: # endif
1390: }
1391: #endif /* !THREADS */
1392:
1393: void GC_push_all_stack(bottom, top)
1394: ptr_t bottom;
1395: ptr_t top;
1396: {
1.4 ! noro 1397: if (GC_all_interior_pointers) {
1.1 noro 1398: GC_push_all(bottom, top);
1.4 ! noro 1399: } else {
1.1 noro 1400: GC_push_all_eager(bottom, top);
1.4 ! noro 1401: }
1.1 noro 1402: }
1403:
1.4 ! noro 1404: #if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
1.1 noro 1405: /* Push all objects reachable from marked objects in the given block */
1406: /* of size 1 objects. */
1407: void GC_push_marked1(h, hhdr)
1408: struct hblk *h;
1409: register hdr * hhdr;
1410: {
1.4 ! noro 1411: word * mark_word_addr = &(hhdr->hb_marks[0]);
1.1 noro 1412: register word *p;
1413: word *plim;
1414: register int i;
1415: register word q;
1416: register word mark_word;
1417: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1418: register ptr_t least_ha = GC_least_plausible_heap_addr;
1.4 ! noro 1419: register mse * mark_stack_top = GC_mark_stack_top;
! 1420: register mse * mark_stack_limit = GC_mark_stack_limit;
! 1421: # define GC_mark_stack_top mark_stack_top
! 1422: # define GC_mark_stack_limit mark_stack_limit
1.1 noro 1423: # define GC_greatest_plausible_heap_addr greatest_ha
1424: # define GC_least_plausible_heap_addr least_ha
1425:
1426: p = (word *)(h->hb_body);
1427: plim = (word *)(((word)h) + HBLKSIZE);
1428:
1429: /* go through all words in block */
1430: while( p < plim ) {
1431: mark_word = *mark_word_addr++;
1432: i = 0;
1433: while(mark_word != 0) {
1434: if (mark_word & 1) {
1435: q = p[i];
1436: GC_PUSH_ONE_HEAP(q, p + i);
1437: }
1438: i++;
1439: mark_word >>= 1;
1440: }
1441: p += WORDSZ;
1442: }
1443: # undef GC_greatest_plausible_heap_addr
1444: # undef GC_least_plausible_heap_addr
1.4 ! noro 1445: # undef GC_mark_stack_top
! 1446: # undef GC_mark_stack_limit
! 1447: GC_mark_stack_top = mark_stack_top;
1.1 noro 1448: }
1449:
1450:
1451: #ifndef UNALIGNED
1452:
1453: /* Push all objects reachable from marked objects in the given block */
1454: /* of size 2 objects. */
1455: void GC_push_marked2(h, hhdr)
1456: struct hblk *h;
1457: register hdr * hhdr;
1458: {
1.4 ! noro 1459: word * mark_word_addr = &(hhdr->hb_marks[0]);
1.1 noro 1460: register word *p;
1461: word *plim;
1462: register int i;
1463: register word q;
1464: register word mark_word;
1465: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1466: register ptr_t least_ha = GC_least_plausible_heap_addr;
1.4 ! noro 1467: register mse * mark_stack_top = GC_mark_stack_top;
! 1468: register mse * mark_stack_limit = GC_mark_stack_limit;
! 1469: # define GC_mark_stack_top mark_stack_top
! 1470: # define GC_mark_stack_limit mark_stack_limit
1.1 noro 1471: # define GC_greatest_plausible_heap_addr greatest_ha
1472: # define GC_least_plausible_heap_addr least_ha
1473:
1474: p = (word *)(h->hb_body);
1475: plim = (word *)(((word)h) + HBLKSIZE);
1476:
1477: /* go through all words in block */
1478: while( p < plim ) {
1479: mark_word = *mark_word_addr++;
1480: i = 0;
1481: while(mark_word != 0) {
1482: if (mark_word & 1) {
1483: q = p[i];
1484: GC_PUSH_ONE_HEAP(q, p + i);
1485: q = p[i+1];
1486: GC_PUSH_ONE_HEAP(q, p + i);
1487: }
1488: i += 2;
1489: mark_word >>= 2;
1490: }
1491: p += WORDSZ;
1492: }
1493: # undef GC_greatest_plausible_heap_addr
1494: # undef GC_least_plausible_heap_addr
1.4 ! noro 1495: # undef GC_mark_stack_top
! 1496: # undef GC_mark_stack_limit
! 1497: GC_mark_stack_top = mark_stack_top;
1.1 noro 1498: }
1499:
1500: /* Push all objects reachable from marked objects in the given block */
1501: /* of size 4 objects. */
1502: /* There is a risk of mark stack overflow here. But we handle that. */
1503: /* And only unmarked objects get pushed, so it's not very likely. */
1504: void GC_push_marked4(h, hhdr)
1505: struct hblk *h;
1506: register hdr * hhdr;
1507: {
1.4 ! noro 1508: word * mark_word_addr = &(hhdr->hb_marks[0]);
1.1 noro 1509: register word *p;
1510: word *plim;
1511: register int i;
1512: register word q;
1513: register word mark_word;
1514: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1515: register ptr_t least_ha = GC_least_plausible_heap_addr;
1.4 ! noro 1516: register mse * mark_stack_top = GC_mark_stack_top;
! 1517: register mse * mark_stack_limit = GC_mark_stack_limit;
! 1518: # define GC_mark_stack_top mark_stack_top
! 1519: # define GC_mark_stack_limit mark_stack_limit
1.1 noro 1520: # define GC_greatest_plausible_heap_addr greatest_ha
1521: # define GC_least_plausible_heap_addr least_ha
1522:
1523: p = (word *)(h->hb_body);
1524: plim = (word *)(((word)h) + HBLKSIZE);
1525:
1526: /* go through all words in block */
1527: while( p < plim ) {
1528: mark_word = *mark_word_addr++;
1529: i = 0;
1530: while(mark_word != 0) {
1531: if (mark_word & 1) {
1532: q = p[i];
1533: GC_PUSH_ONE_HEAP(q, p + i);
1534: q = p[i+1];
1535: GC_PUSH_ONE_HEAP(q, p + i + 1);
1536: q = p[i+2];
1537: GC_PUSH_ONE_HEAP(q, p + i + 2);
1538: q = p[i+3];
1539: GC_PUSH_ONE_HEAP(q, p + i + 3);
1540: }
1541: i += 4;
1542: mark_word >>= 4;
1543: }
1544: p += WORDSZ;
1545: }
1546: # undef GC_greatest_plausible_heap_addr
1547: # undef GC_least_plausible_heap_addr
1.4 ! noro 1548: # undef GC_mark_stack_top
! 1549: # undef GC_mark_stack_limit
! 1550: GC_mark_stack_top = mark_stack_top;
1.1 noro 1551: }
1552:
1553: #endif /* UNALIGNED */
1554:
1555: #endif /* SMALL_CONFIG */
1556:
1557: /* Push all objects reachable from marked objects in the given block */
1558: void GC_push_marked(h, hhdr)
1559: struct hblk *h;
1560: register hdr * hhdr;
1561: {
1562: register int sz = hhdr -> hb_sz;
1.3 noro 1563: register int descr = hhdr -> hb_descr;
1.1 noro 1564: register word * p;
1565: register int word_no;
1566: register word * lim;
1567: register mse * GC_mark_stack_top_reg;
1.4 ! noro 1568: register mse * mark_stack_limit = GC_mark_stack_limit;
1.1 noro 1569:
1570: /* Some quick shortcuts: */
1.4 ! noro 1571: if ((0 | GC_DS_LENGTH) == descr) return;
1.1 noro 1572: if (GC_block_empty(hhdr)/* nothing marked */) return;
1.4 ! noro 1573: GC_n_rescuing_pages++;
1.1 noro 1574: GC_objects_are_marked = TRUE;
1575: if (sz > MAXOBJSZ) {
1.4 ! noro 1576: lim = (word *)h;
1.1 noro 1577: } else {
1578: lim = (word *)(h + 1) - sz;
1579: }
1580:
1581: switch(sz) {
1.4 ! noro 1582: # if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
1.1 noro 1583: case 1:
1584: GC_push_marked1(h, hhdr);
1585: break;
1586: # endif
1.4 ! noro 1587: # if !defined(SMALL_CONFIG) && !defined(UNALIGNED) && \
! 1588: !defined(USE_MARK_BYTES)
1.1 noro 1589: case 2:
1590: GC_push_marked2(h, hhdr);
1591: break;
1592: case 4:
1593: GC_push_marked4(h, hhdr);
1594: break;
1595: # endif
1596: default:
1597: GC_mark_stack_top_reg = GC_mark_stack_top;
1.4 ! noro 1598: for (p = (word *)h, word_no = 0; p <= lim; p += sz, word_no += sz) {
1.1 noro 1599: if (mark_bit_from_hdr(hhdr, word_no)) {
1600: /* Mark from fields inside the object */
1601: PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
1602: # ifdef GATHERSTATS
1603: /* Subtract this object from total, since it was */
1604: /* added in twice. */
1605: GC_composite_in_use -= sz;
1606: # endif
1607: }
1608: }
1609: GC_mark_stack_top = GC_mark_stack_top_reg;
1610: }
1611: }
1612:
1613: #ifndef SMALL_CONFIG
1614: /* Test whether any page in the given block is dirty */
1615: GC_bool GC_block_was_dirty(h, hhdr)
1616: struct hblk *h;
1617: register hdr * hhdr;
1618: {
1619: register int sz = hhdr -> hb_sz;
1620:
1621: if (sz < MAXOBJSZ) {
1622: return(GC_page_was_dirty(h));
1623: } else {
1624: register ptr_t p = (ptr_t)h;
1625: sz = WORDS_TO_BYTES(sz);
1626: while (p < (ptr_t)h + sz) {
1627: if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
1628: p += HBLKSIZE;
1629: }
1630: return(FALSE);
1631: }
1632: }
1633: #endif /* SMALL_CONFIG */
1634:
1635: /* Similar to GC_push_next_marked, but return address of next block */
1636: struct hblk * GC_push_next_marked(h)
1637: struct hblk *h;
1638: {
1639: register hdr * hhdr;
1640:
1641: h = GC_next_used_block(h);
1642: if (h == 0) return(0);
1643: hhdr = HDR(h);
1644: GC_push_marked(h, hhdr);
1645: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1646: }
1647:
1648: #ifndef SMALL_CONFIG
1649: /* Identical to above, but mark only from dirty pages */
1650: struct hblk * GC_push_next_marked_dirty(h)
1651: struct hblk *h;
1652: {
1.2 noro 1653: register hdr * hhdr;
1.1 noro 1654:
1655: if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
1656: for (;;) {
1657: h = GC_next_used_block(h);
1658: if (h == 0) return(0);
1659: hhdr = HDR(h);
1660: # ifdef STUBBORN_ALLOC
1661: if (hhdr -> hb_obj_kind == STUBBORN) {
1662: if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
1663: break;
1664: }
1665: } else {
1666: if (GC_block_was_dirty(h, hhdr)) break;
1667: }
1668: # else
1669: if (GC_block_was_dirty(h, hhdr)) break;
1670: # endif
1671: h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1672: }
1673: GC_push_marked(h, hhdr);
1674: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1675: }
1676: #endif
1677:
1678: /* Similar to above, but for uncollectable pages. Needed since we */
1679: /* do not clear marks for such pages, even for full collections. */
1680: struct hblk * GC_push_next_marked_uncollectable(h)
1681: struct hblk *h;
1682: {
1683: register hdr * hhdr = HDR(h);
1684:
1685: for (;;) {
1686: h = GC_next_used_block(h);
1687: if (h == 0) return(0);
1688: hhdr = HDR(h);
1689: if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
1690: h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1691: }
1692: GC_push_marked(h, hhdr);
1693: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1694: }
1695:
1696:
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