Annotation of OpenXM_contrib2/asir2000/gc/mark.c, Revision 1.6
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.6 ! noro 267: #if defined(MSWIN32) && !defined(__GNUC__)
1.3 noro 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 {
1.6 ! noro 277: #endif /* defined(MSWIN32) && !defined(__GNUC__) */
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.6 ! noro 398: #if defined(MSWIN32) && !defined(__GNUC__)
1.3 noro 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: }
1.6 ! noro 413: #endif /* defined(MSWIN32) && !defined(__GNUC__) */
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 */
1.6 ! noro 430: /* first page of a large object, either: */
! 431: /* - return a pointer to somewhere in the first page of the large */
! 432: /* object, if current points to a large object. */
! 433: /* In this case *hhdr is replaced with a pointer to the header */
! 434: /* for the large object. */
! 435: /* - just return current if it does not point to a large object. */
1.1 noro 436: /*ARGSUSED*/
1.6 ! noro 437: ptr_t GC_find_start(current, hhdr, new_hdr_p)
1.3 noro 438: register ptr_t current;
1.6 ! noro 439: register hdr *hhdr, **new_hdr_p;
1.1 noro 440: {
1.4 noro 441: if (GC_all_interior_pointers) {
1.1 noro 442: if (hhdr != 0) {
1.3 noro 443: register ptr_t orig = current;
1.1 noro 444:
1.4 noro 445: current = (ptr_t)HBLKPTR(current);
1.1 noro 446: do {
447: current = current - HBLKSIZE*(word)hhdr;
448: hhdr = HDR(current);
449: } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
450: /* current points to the start of the large object */
451: if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
452: if ((word *)orig - (word *)current
453: >= (ptrdiff_t)(hhdr->hb_sz)) {
454: /* Pointer past the end of the block */
1.6 ! noro 455: return(orig);
1.1 noro 456: }
1.6 ! noro 457: *new_hdr_p = hhdr;
1.1 noro 458: return(current);
459: } else {
1.6 ! noro 460: return(current);
1.1 noro 461: }
1.4 noro 462: } else {
1.6 ! noro 463: return(current);
1.4 noro 464: }
1.1 noro 465: }
466:
467: void GC_invalidate_mark_state()
468: {
469: GC_mark_state = MS_INVALID;
470: GC_mark_stack_top = GC_mark_stack-1;
471: }
472:
473: mse * GC_signal_mark_stack_overflow(msp)
474: mse * msp;
475: {
476: GC_mark_state = MS_INVALID;
477: GC_mark_stack_too_small = TRUE;
1.4 noro 478: # ifdef CONDPRINT
479: if (GC_print_stats) {
1.1 noro 480: GC_printf1("Mark stack overflow; current size = %lu entries\n",
481: GC_mark_stack_size);
1.4 noro 482: }
483: # endif
484: return(msp - GC_MARK_STACK_DISCARDS);
1.1 noro 485: }
486:
487: /*
488: * Mark objects pointed to by the regions described by
489: * mark stack entries between GC_mark_stack and GC_mark_stack_top,
490: * inclusive. Assumes the upper limit of a mark stack entry
491: * is never 0. A mark stack entry never has size 0.
492: * We try to traverse on the order of a hblk of memory before we return.
493: * Caller is responsible for calling this until the mark stack is empty.
1.3 noro 494: * Note that this is the most performance critical routine in the
495: * collector. Hence it contains all sorts of ugly hacks to speed
496: * things up. In particular, we avoid procedure calls on the common
497: * path, we take advantage of peculiarities of the mark descriptor
498: * encoding, we optionally maintain a cache for the block address to
499: * header mapping, we prefetch when an object is "grayed", etc.
1.1 noro 500: */
1.4 noro 501: mse * GC_mark_from(mark_stack_top, mark_stack, mark_stack_limit)
502: mse * mark_stack_top;
503: mse * mark_stack;
504: mse * mark_stack_limit;
1.1 noro 505: {
506: int credit = HBLKSIZE; /* Remaining credit for marking work */
507: register word * current_p; /* Pointer to current candidate ptr. */
508: register word current; /* Candidate pointer. */
509: register word * limit; /* (Incl) limit of current candidate */
510: /* range */
511: register word descr;
512: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
513: register ptr_t least_ha = GC_least_plausible_heap_addr;
1.3 noro 514: DECLARE_HDR_CACHE;
515:
1.1 noro 516: # define SPLIT_RANGE_WORDS 128 /* Must be power of 2. */
517:
518: GC_objects_are_marked = TRUE;
1.3 noro 519: INIT_HDR_CACHE;
1.1 noro 520: # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
1.4 noro 521: while (mark_stack_top >= mark_stack && credit >= 0) {
1.1 noro 522: # else
1.4 noro 523: while ((((ptr_t)mark_stack_top - (ptr_t)mark_stack) | credit)
1.1 noro 524: >= 0) {
525: # endif
1.4 noro 526: current_p = mark_stack_top -> mse_start;
527: descr = mark_stack_top -> mse_descr;
1.1 noro 528: retry:
1.3 noro 529: /* current_p and descr describe the current object. */
1.4 noro 530: /* *mark_stack_top is vacant. */
1.3 noro 531: /* The following is 0 only for small objects described by a simple */
532: /* length descriptor. For many applications this is the common */
533: /* case, so we try to detect it quickly. */
1.4 noro 534: if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | GC_DS_TAGS)) {
535: word tag = descr & GC_DS_TAGS;
1.1 noro 536:
537: switch(tag) {
1.4 noro 538: case GC_DS_LENGTH:
1.1 noro 539: /* Large length. */
540: /* Process part of the range to avoid pushing too much on the */
541: /* stack. */
1.6 ! noro 542: GC_ASSERT(descr < GC_greatest_plausible_heap_addr
! 543: - GC_least_plausible_heap_addr);
1.4 noro 544: # ifdef PARALLEL_MARK
545: # define SHARE_BYTES 2048
546: if (descr > SHARE_BYTES && GC_parallel
547: && mark_stack_top < mark_stack_limit - 1) {
548: int new_size = (descr/2) & ~(sizeof(word)-1);
549: mark_stack_top -> mse_start = current_p;
550: mark_stack_top -> mse_descr = new_size + sizeof(word);
551: /* makes sure we handle */
552: /* misaligned pointers. */
553: mark_stack_top++;
554: current_p = (word *) ((char *)current_p + new_size);
555: descr -= new_size;
556: goto retry;
557: }
558: # endif /* PARALLEL_MARK */
559: mark_stack_top -> mse_start =
1.1 noro 560: limit = current_p + SPLIT_RANGE_WORDS-1;
1.4 noro 561: mark_stack_top -> mse_descr =
1.3 noro 562: descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
1.1 noro 563: /* Make sure that pointers overlapping the two ranges are */
564: /* considered. */
565: limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
566: break;
1.4 noro 567: case GC_DS_BITMAP:
568: mark_stack_top--;
569: descr &= ~GC_DS_TAGS;
1.1 noro 570: credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
571: while (descr != 0) {
572: if ((signed_word)descr < 0) {
573: current = *current_p;
574: if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
1.3 noro 575: PREFETCH(current);
1.4 noro 576: HC_PUSH_CONTENTS((ptr_t)current, mark_stack_top,
1.3 noro 577: mark_stack_limit, current_p, exit1);
1.1 noro 578: }
579: }
580: descr <<= 1;
581: ++ current_p;
582: }
583: continue;
1.4 noro 584: case GC_DS_PROC:
585: mark_stack_top--;
586: credit -= GC_PROC_BYTES;
587: mark_stack_top =
1.1 noro 588: (*PROC(descr))
1.4 noro 589: (current_p, mark_stack_top,
1.1 noro 590: mark_stack_limit, ENV(descr));
591: continue;
1.4 noro 592: case GC_DS_PER_OBJECT:
1.3 noro 593: if ((signed_word)descr >= 0) {
594: /* Descriptor is in the object. */
1.4 noro 595: descr = *(word *)((ptr_t)current_p + descr - GC_DS_PER_OBJECT);
1.3 noro 596: } else {
597: /* Descriptor is in type descriptor pointed to by first */
598: /* word in object. */
599: ptr_t type_descr = *(ptr_t *)current_p;
600: /* type_descr is either a valid pointer to the descriptor */
601: /* structure, or this object was on a free list. If it */
602: /* it was anything but the last object on the free list, */
603: /* we will misinterpret the next object on the free list as */
604: /* the type descriptor, and get a 0 GC descriptor, which */
605: /* is ideal. Unfortunately, we need to check for the last */
606: /* object case explicitly. */
607: if (0 == type_descr) {
608: /* Rarely executed. */
1.4 noro 609: mark_stack_top--;
1.3 noro 610: continue;
611: }
612: descr = *(word *)(type_descr
1.4 noro 613: - (descr - (GC_DS_PER_OBJECT
614: - GC_INDIR_PER_OBJ_BIAS)));
1.3 noro 615: }
616: if (0 == descr) {
1.4 noro 617: /* Can happen either because we generated a 0 descriptor */
618: /* or we saw a pointer to a free object. */
619: mark_stack_top--;
620: continue;
1.3 noro 621: }
1.1 noro 622: goto retry;
623: }
1.3 noro 624: } else /* Small object with length descriptor */ {
1.4 noro 625: mark_stack_top--;
1.1 noro 626: limit = (word *)(((ptr_t)current_p) + (word)descr);
627: }
628: /* The simple case in which we're scanning a range. */
1.4 noro 629: GC_ASSERT(!((word)current_p & (ALIGNMENT-1)));
1.1 noro 630: credit -= (ptr_t)limit - (ptr_t)current_p;
631: limit -= 1;
1.3 noro 632: {
633: # define PREF_DIST 4
634:
635: # ifndef SMALL_CONFIG
636: word deferred;
637:
638: /* Try to prefetch the next pointer to be examined asap. */
639: /* Empirically, this also seems to help slightly without */
640: /* prefetches, at least on linux/X86. Presumably this loop */
641: /* ends up with less register pressure, and gcc thus ends up */
642: /* generating slightly better code. Overall gcc code quality */
643: /* for this loop is still not great. */
644: for(;;) {
645: PREFETCH((ptr_t)limit - PREF_DIST*CACHE_LINE_SIZE);
1.4 noro 646: GC_ASSERT(limit >= current_p);
1.3 noro 647: deferred = *limit;
648: limit = (word *)((char *)limit - ALIGNMENT);
649: if ((ptr_t)deferred >= least_ha && (ptr_t)deferred < greatest_ha) {
650: PREFETCH(deferred);
651: break;
652: }
653: if (current_p > limit) goto next_object;
654: /* Unroll once, so we don't do too many of the prefetches */
655: /* based on limit. */
656: deferred = *limit;
657: limit = (word *)((char *)limit - ALIGNMENT);
658: if ((ptr_t)deferred >= least_ha && (ptr_t)deferred < greatest_ha) {
659: PREFETCH(deferred);
660: break;
661: }
662: if (current_p > limit) goto next_object;
663: }
664: # endif
665:
666: while (current_p <= limit) {
667: /* Empirically, unrolling this loop doesn't help a lot. */
668: /* Since HC_PUSH_CONTENTS expands to a lot of code, */
669: /* we don't. */
670: current = *current_p;
671: PREFETCH((ptr_t)current_p + PREF_DIST*CACHE_LINE_SIZE);
672: if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
673: /* Prefetch the contents of the object we just pushed. It's */
674: /* likely we will need them soon. */
675: PREFETCH(current);
1.4 noro 676: HC_PUSH_CONTENTS((ptr_t)current, mark_stack_top,
1.3 noro 677: mark_stack_limit, current_p, exit2);
678: }
679: current_p = (word *)((char *)current_p + ALIGNMENT);
1.1 noro 680: }
1.3 noro 681:
682: # ifndef SMALL_CONFIG
683: /* We still need to mark the entry we previously prefetched. */
684: /* We alrady know that it passes the preliminary pointer */
685: /* validity test. */
1.4 noro 686: HC_PUSH_CONTENTS((ptr_t)deferred, mark_stack_top,
1.3 noro 687: mark_stack_limit, current_p, exit4);
688: next_object:;
689: # endif
1.1 noro 690: }
691: }
1.4 noro 692: return mark_stack_top;
693: }
694:
695: #ifdef PARALLEL_MARK
696:
697: /* We assume we have an ANSI C Compiler. */
698: GC_bool GC_help_wanted = FALSE;
699: unsigned GC_helper_count = 0;
700: unsigned GC_active_count = 0;
701: mse * VOLATILE GC_first_nonempty;
702: word GC_mark_no = 0;
703:
704: #define LOCAL_MARK_STACK_SIZE HBLKSIZE
705: /* Under normal circumstances, this is big enough to guarantee */
706: /* We don't overflow half of it in a single call to */
707: /* GC_mark_from. */
708:
709:
710: /* Steal mark stack entries starting at mse low into mark stack local */
711: /* until we either steal mse high, or we have max entries. */
712: /* Return a pointer to the top of the local mark stack. */
713: /* *next is replaced by a pointer to the next unscanned mark stack */
714: /* entry. */
715: mse * GC_steal_mark_stack(mse * low, mse * high, mse * local,
716: unsigned max, mse **next)
717: {
718: mse *p;
719: mse *top = local - 1;
720: unsigned i = 0;
721:
722: GC_ASSERT(high >= low-1 && high - low + 1 <= GC_mark_stack_size);
723: for (p = low; p <= high && i <= max; ++p) {
724: word descr = *(volatile word *) &(p -> mse_descr);
725: if (descr != 0) {
726: *(volatile word *) &(p -> mse_descr) = 0;
727: ++top;
728: top -> mse_descr = descr;
729: top -> mse_start = p -> mse_start;
730: GC_ASSERT( top -> mse_descr & GC_DS_TAGS != GC_DS_LENGTH ||
731: top -> mse_descr < GC_greatest_plausible_heap_addr
732: - GC_least_plausible_heap_addr);
733: /* There is no synchronization here. We assume that at */
734: /* least one thread will see the original descriptor. */
735: /* Otherwise we need a barrier. */
736: /* More than one thread may get this entry, but that's only */
737: /* a minor performance problem. */
738: /* If this is a big object, count it as */
739: /* size/256 + 1 objects. */
740: ++i;
741: if ((descr & GC_DS_TAGS) == GC_DS_LENGTH) i += (descr >> 8);
742: }
743: }
744: *next = p;
745: return top;
746: }
747:
748: /* Copy back a local mark stack. */
749: /* low and high are inclusive bounds. */
750: void GC_return_mark_stack(mse * low, mse * high)
751: {
752: mse * my_top;
753: mse * my_start;
754: size_t stack_size;
755:
756: if (high < low) return;
757: stack_size = high - low + 1;
758: GC_acquire_mark_lock();
759: my_top = GC_mark_stack_top;
760: my_start = my_top + 1;
761: if (my_start - GC_mark_stack + stack_size > GC_mark_stack_size) {
762: # ifdef CONDPRINT
763: if (GC_print_stats) {
764: GC_printf0("No room to copy back mark stack.");
765: }
766: # endif
767: GC_mark_state = MS_INVALID;
768: GC_mark_stack_too_small = TRUE;
769: /* We drop the local mark stack. We'll fix things later. */
770: } else {
771: BCOPY(low, my_start, stack_size * sizeof(mse));
772: GC_ASSERT(GC_mark_stack_top = my_top);
773: # if !defined(IA64) && !defined(HP_PA)
774: GC_memory_write_barrier();
775: # endif
776: /* On IA64, the volatile write acts as a release barrier. */
777: GC_mark_stack_top = my_top + stack_size;
778: }
779: GC_release_mark_lock();
780: GC_notify_all_marker();
1.1 noro 781: }
782:
1.4 noro 783: /* Mark from the local mark stack. */
784: /* On return, the local mark stack is empty. */
785: /* But this may be achieved by copying the */
786: /* local mark stack back into the global one. */
787: void GC_do_local_mark(mse *local_mark_stack, mse *local_top)
788: {
789: unsigned n;
790: # define N_LOCAL_ITERS 1
791:
792: # ifdef GC_ASSERTIONS
793: /* Make sure we don't hold mark lock. */
794: GC_acquire_mark_lock();
795: GC_release_mark_lock();
796: # endif
797: for (;;) {
798: for (n = 0; n < N_LOCAL_ITERS; ++n) {
799: local_top = GC_mark_from(local_top, local_mark_stack,
800: local_mark_stack + LOCAL_MARK_STACK_SIZE);
801: if (local_top < local_mark_stack) return;
802: if (local_top - local_mark_stack >= LOCAL_MARK_STACK_SIZE/2) {
803: GC_return_mark_stack(local_mark_stack, local_top);
804: return;
805: }
806: }
807: if (GC_mark_stack_top < GC_first_nonempty &&
808: GC_active_count < GC_helper_count
809: && local_top > local_mark_stack + 1) {
810: /* Try to share the load, since the main stack is empty, */
811: /* and helper threads are waiting for a refill. */
812: /* The entries near the bottom of the stack are likely */
813: /* to require more work. Thus we return those, eventhough */
814: /* it's harder. */
815: mse * p;
816: mse * new_bottom = local_mark_stack
817: + (local_top - local_mark_stack)/2;
818: GC_ASSERT(new_bottom > local_mark_stack
819: && new_bottom < local_top);
820: GC_return_mark_stack(local_mark_stack, new_bottom - 1);
821: memmove(local_mark_stack, new_bottom,
822: (local_top - new_bottom + 1) * sizeof(mse));
823: local_top -= (new_bottom - local_mark_stack);
824: }
825: }
826: }
827:
828: #define ENTRIES_TO_GET 5
829:
830: long GC_markers = 2; /* Normally changed by thread-library- */
831: /* -specific code. */
832:
833: /* Mark using the local mark stack until the global mark stack is empty */
1.6 ! noro 834: /* and there are no active workers. Update GC_first_nonempty to reflect */
1.4 noro 835: /* progress. */
836: /* Caller does not hold mark lock. */
837: /* Caller has already incremented GC_helper_count. We decrement it, */
838: /* and maintain GC_active_count. */
839: void GC_mark_local(mse *local_mark_stack, int id)
840: {
841: mse * my_first_nonempty;
842:
843: GC_acquire_mark_lock();
844: GC_active_count++;
845: my_first_nonempty = GC_first_nonempty;
846: GC_ASSERT(GC_first_nonempty >= GC_mark_stack &&
847: GC_first_nonempty <= GC_mark_stack_top + 1);
848: # ifdef PRINTSTATS
849: GC_printf1("Starting mark helper %lu\n", (unsigned long)id);
850: # endif
851: GC_release_mark_lock();
852: for (;;) {
853: size_t n_on_stack;
854: size_t n_to_get;
855: mse *next;
856: mse * my_top;
857: mse * local_top;
858: mse * global_first_nonempty = GC_first_nonempty;
859:
860: GC_ASSERT(my_first_nonempty >= GC_mark_stack &&
861: my_first_nonempty <= GC_mark_stack_top + 1);
862: GC_ASSERT(global_first_nonempty >= GC_mark_stack &&
863: global_first_nonempty <= GC_mark_stack_top + 1);
864: if (my_first_nonempty < global_first_nonempty) {
865: my_first_nonempty = global_first_nonempty;
866: } else if (global_first_nonempty < my_first_nonempty) {
867: GC_compare_and_exchange((word *)(&GC_first_nonempty),
868: (word) global_first_nonempty,
869: (word) my_first_nonempty);
870: /* If this fails, we just go ahead, without updating */
871: /* GC_first_nonempty. */
872: }
873: /* Perhaps we should also update GC_first_nonempty, if it */
874: /* is less. But that would require using atomic updates. */
875: my_top = GC_mark_stack_top;
876: n_on_stack = my_top - my_first_nonempty + 1;
877: if (0 == n_on_stack) {
878: GC_acquire_mark_lock();
879: my_top = GC_mark_stack_top;
880: n_on_stack = my_top - my_first_nonempty + 1;
881: if (0 == n_on_stack) {
882: GC_active_count--;
883: GC_ASSERT(GC_active_count <= GC_helper_count);
884: /* Other markers may redeposit objects */
885: /* on the stack. */
886: if (0 == GC_active_count) GC_notify_all_marker();
887: while (GC_active_count > 0
888: && GC_first_nonempty > GC_mark_stack_top) {
889: /* We will be notified if either GC_active_count */
890: /* reaches zero, or if more objects are pushed on */
891: /* the global mark stack. */
892: GC_wait_marker();
893: }
894: if (GC_active_count == 0 &&
895: GC_first_nonempty > GC_mark_stack_top) {
896: GC_bool need_to_notify = FALSE;
897: /* The above conditions can't be falsified while we */
898: /* hold the mark lock, since neither */
899: /* GC_active_count nor GC_mark_stack_top can */
900: /* change. GC_first_nonempty can only be */
901: /* incremented asynchronously. Thus we know that */
902: /* both conditions actually held simultaneously. */
903: GC_helper_count--;
904: if (0 == GC_helper_count) need_to_notify = TRUE;
905: # ifdef PRINTSTATS
906: GC_printf1(
907: "Finished mark helper %lu\n", (unsigned long)id);
908: # endif
909: GC_release_mark_lock();
910: if (need_to_notify) GC_notify_all_marker();
911: return;
912: }
913: /* else there's something on the stack again, or */
1.6 ! noro 914: /* another helper may push something. */
1.4 noro 915: GC_active_count++;
916: GC_ASSERT(GC_active_count > 0);
917: GC_release_mark_lock();
918: continue;
919: } else {
920: GC_release_mark_lock();
921: }
922: }
923: n_to_get = ENTRIES_TO_GET;
924: if (n_on_stack < 2 * ENTRIES_TO_GET) n_to_get = 1;
925: local_top = GC_steal_mark_stack(my_first_nonempty, my_top,
926: local_mark_stack, n_to_get,
927: &my_first_nonempty);
928: GC_ASSERT(my_first_nonempty >= GC_mark_stack &&
929: my_first_nonempty <= GC_mark_stack_top + 1);
930: GC_do_local_mark(local_mark_stack, local_top);
931: }
932: }
933:
934: /* Perform Parallel mark. */
935: /* We hold the GC lock, not the mark lock. */
936: /* Currently runs until the mark stack is */
937: /* empty. */
938: void GC_do_parallel_mark()
939: {
940: mse local_mark_stack[LOCAL_MARK_STACK_SIZE];
941: mse * local_top;
942: mse * my_top;
943:
944: GC_acquire_mark_lock();
945: GC_ASSERT(I_HOLD_LOCK());
1.6 ! noro 946: /* This could be a GC_ASSERT, but it seems safer to keep it on */
! 947: /* all the time, especially since it's cheap. */
! 948: if (GC_help_wanted || GC_active_count != 0 || GC_helper_count != 0)
! 949: ABORT("Tried to start parallel mark in bad state");
1.4 noro 950: # ifdef PRINTSTATS
951: GC_printf1("Starting marking for mark phase number %lu\n",
952: (unsigned long)GC_mark_no);
953: # endif
954: GC_first_nonempty = GC_mark_stack;
955: GC_active_count = 0;
956: GC_helper_count = 1;
957: GC_help_wanted = TRUE;
958: GC_release_mark_lock();
959: GC_notify_all_marker();
960: /* Wake up potential helpers. */
961: GC_mark_local(local_mark_stack, 0);
962: GC_acquire_mark_lock();
963: GC_help_wanted = FALSE;
964: /* Done; clean up. */
965: while (GC_helper_count > 0) GC_wait_marker();
966: /* GC_helper_count cannot be incremented while GC_help_wanted == FALSE */
967: # ifdef PRINTSTATS
968: GC_printf1(
969: "Finished marking for mark phase number %lu\n",
970: (unsigned long)GC_mark_no);
971: # endif
972: GC_mark_no++;
973: GC_release_mark_lock();
974: GC_notify_all_marker();
975: }
976:
977:
978: /* Try to help out the marker, if it's running. */
979: /* We do not hold the GC lock, but the requestor does. */
980: void GC_help_marker(word my_mark_no)
981: {
982: mse local_mark_stack[LOCAL_MARK_STACK_SIZE];
983: unsigned my_id;
984: mse * my_first_nonempty;
985:
986: if (!GC_parallel) return;
987: GC_acquire_mark_lock();
988: while (GC_mark_no < my_mark_no
989: || !GC_help_wanted && GC_mark_no == my_mark_no) {
990: GC_wait_marker();
991: }
992: my_id = GC_helper_count;
993: if (GC_mark_no != my_mark_no || my_id >= GC_markers) {
994: /* Second test is useful only if original threads can also */
995: /* act as helpers. Under Linux they can't. */
996: GC_release_mark_lock();
997: return;
998: }
999: GC_helper_count = my_id + 1;
1000: GC_release_mark_lock();
1001: GC_mark_local(local_mark_stack, my_id);
1002: /* GC_mark_local decrements GC_helper_count. */
1003: }
1004:
1005: #endif /* PARALLEL_MARK */
1006:
1.1 noro 1007: /* Allocate or reallocate space for mark stack of size s words */
1008: /* May silently fail. */
1009: static void alloc_mark_stack(n)
1010: word n;
1011: {
1.4 noro 1012: mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct GC_ms_entry));
1.1 noro 1013:
1014: GC_mark_stack_too_small = FALSE;
1015: if (GC_mark_stack_size != 0) {
1016: if (new_stack != 0) {
1017: word displ = (word)GC_mark_stack & (GC_page_size - 1);
1.4 noro 1018: signed_word size = GC_mark_stack_size * sizeof(struct GC_ms_entry);
1.1 noro 1019:
1020: /* Recycle old space */
1021: if (0 != displ) displ = GC_page_size - displ;
1022: size = (size - displ) & ~(GC_page_size - 1);
1023: if (size > 0) {
1024: GC_add_to_heap((struct hblk *)
1025: ((word)GC_mark_stack + displ), (word)size);
1026: }
1027: GC_mark_stack = new_stack;
1028: GC_mark_stack_size = n;
1.4 noro 1029: GC_mark_stack_limit = new_stack + n;
1030: # ifdef CONDPRINT
1031: if (GC_print_stats) {
1.1 noro 1032: GC_printf1("Grew mark stack to %lu frames\n",
1033: (unsigned long) GC_mark_stack_size);
1.4 noro 1034: }
1.1 noro 1035: # endif
1036: } else {
1.4 noro 1037: # ifdef CONDPRINT
1038: if (GC_print_stats) {
1.1 noro 1039: GC_printf1("Failed to grow mark stack to %lu frames\n",
1040: (unsigned long) n);
1.4 noro 1041: }
1.1 noro 1042: # endif
1043: }
1044: } else {
1045: if (new_stack == 0) {
1046: GC_err_printf0("No space for mark stack\n");
1047: EXIT();
1048: }
1049: GC_mark_stack = new_stack;
1050: GC_mark_stack_size = n;
1.4 noro 1051: GC_mark_stack_limit = new_stack + n;
1.1 noro 1052: }
1053: GC_mark_stack_top = GC_mark_stack-1;
1054: }
1055:
1056: void GC_mark_init()
1057: {
1058: alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
1059: }
1060:
1061: /*
1062: * Push all locations between b and t onto the mark stack.
1063: * b is the first location to be checked. t is one past the last
1064: * location to be checked.
1065: * Should only be used if there is no possibility of mark stack
1066: * overflow.
1067: */
1068: void GC_push_all(bottom, top)
1069: ptr_t bottom;
1070: ptr_t top;
1071: {
1072: register word length;
1073:
1074: bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1075: top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
1076: if (top == 0 || bottom == top) return;
1077: GC_mark_stack_top++;
1.4 noro 1078: if (GC_mark_stack_top >= GC_mark_stack_limit) {
1.1 noro 1079: ABORT("unexpected mark stack overflow");
1080: }
1081: length = top - bottom;
1.4 noro 1082: # if GC_DS_TAGS > ALIGNMENT - 1
1083: length += GC_DS_TAGS;
1084: length &= ~GC_DS_TAGS;
1.1 noro 1085: # endif
1086: GC_mark_stack_top -> mse_start = (word *)bottom;
1087: GC_mark_stack_top -> mse_descr = length;
1088: }
1089:
1090: /*
1.4 noro 1091: * Analogous to the above, but push only those pages h with dirty_fn(h) != 0.
1.1 noro 1092: * We use push_fn to actually push the block.
1.4 noro 1093: * Used both to selectively push dirty pages, or to push a block
1094: * in piecemeal fashion, to allow for more marking concurrency.
1.1 noro 1095: * Will not overflow mark stack if push_fn pushes a small fixed number
1096: * of entries. (This is invoked only if push_fn pushes a single entry,
1097: * or if it marks each object before pushing it, thus ensuring progress
1098: * in the event of a stack overflow.)
1099: */
1.4 noro 1100: void GC_push_selected(bottom, top, dirty_fn, push_fn)
1.1 noro 1101: ptr_t bottom;
1102: ptr_t top;
1.4 noro 1103: int (*dirty_fn) GC_PROTO((struct hblk * h));
1104: void (*push_fn) GC_PROTO((ptr_t bottom, ptr_t top));
1.1 noro 1105: {
1106: register struct hblk * h;
1107:
1108: bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1109: top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
1110:
1111: if (top == 0 || bottom == top) return;
1112: h = HBLKPTR(bottom + HBLKSIZE);
1113: if (top <= (ptr_t) h) {
1114: if ((*dirty_fn)(h-1)) {
1115: (*push_fn)(bottom, top);
1116: }
1117: return;
1118: }
1119: if ((*dirty_fn)(h-1)) {
1120: (*push_fn)(bottom, (ptr_t)h);
1121: }
1122: while ((ptr_t)(h+1) <= top) {
1123: if ((*dirty_fn)(h)) {
1124: if ((word)(GC_mark_stack_top - GC_mark_stack)
1125: > 3 * GC_mark_stack_size / 4) {
1126: /* Danger of mark stack overflow */
1127: (*push_fn)((ptr_t)h, top);
1128: return;
1129: } else {
1130: (*push_fn)((ptr_t)h, (ptr_t)(h+1));
1131: }
1132: }
1133: h++;
1134: }
1135: if ((ptr_t)h != top) {
1136: if ((*dirty_fn)(h)) {
1137: (*push_fn)((ptr_t)h, top);
1138: }
1139: }
1.4 noro 1140: if (GC_mark_stack_top >= GC_mark_stack_limit) {
1.1 noro 1141: ABORT("unexpected mark stack overflow");
1142: }
1143: }
1144:
1145: # ifndef SMALL_CONFIG
1.4 noro 1146:
1147: #ifdef PARALLEL_MARK
1148: /* Break up root sections into page size chunks to better spread */
1149: /* out work. */
1150: GC_bool GC_true_func(struct hblk *h) { return TRUE; }
1151: # define GC_PUSH_ALL(b,t) GC_push_selected(b,t,GC_true_func,GC_push_all);
1152: #else
1153: # define GC_PUSH_ALL(b,t) GC_push_all(b,t);
1154: #endif
1155:
1156:
1.1 noro 1157: void GC_push_conditional(bottom, top, all)
1158: ptr_t bottom;
1159: ptr_t top;
1160: int all;
1161: {
1162: if (all) {
1163: if (GC_dirty_maintained) {
1164: # ifdef PROC_VDB
1165: /* Pages that were never dirtied cannot contain pointers */
1.4 noro 1166: GC_push_selected(bottom, top, GC_page_was_ever_dirty, GC_push_all);
1.1 noro 1167: # else
1168: GC_push_all(bottom, top);
1169: # endif
1170: } else {
1171: GC_push_all(bottom, top);
1172: }
1173: } else {
1.4 noro 1174: GC_push_selected(bottom, top, GC_page_was_dirty, GC_push_all);
1.1 noro 1175: }
1176: }
1177: #endif
1178:
1.4 noro 1179: # if defined(MSWIN32) || defined(MSWINCE)
1.1 noro 1180: void __cdecl GC_push_one(p)
1181: # else
1182: void GC_push_one(p)
1183: # endif
1184: word p;
1185: {
1.3 noro 1186: GC_PUSH_ONE_STACK(p, MARKED_FROM_REGISTER);
1.1 noro 1187: }
1188:
1.4 noro 1189: struct GC_ms_entry *GC_mark_and_push(obj, mark_stack_ptr, mark_stack_limit, src)
1190: GC_PTR obj;
1191: struct GC_ms_entry * mark_stack_ptr;
1192: struct GC_ms_entry * mark_stack_limit;
1193: GC_PTR *src;
1194: {
1195: PREFETCH(obj);
1196: PUSH_CONTENTS(obj, mark_stack_ptr /* modified */, mark_stack_limit, src,
1197: was_marked /* internally generated exit label */);
1198: return mark_stack_ptr;
1199: }
1200:
1.1 noro 1201: # ifdef __STDC__
1202: # define BASE(p) (word)GC_base((void *)(p))
1203: # else
1204: # define BASE(p) (word)GC_base((char *)(p))
1205: # endif
1206:
1.4 noro 1207: /* Mark and push (i.e. gray) a single object p onto the main */
1208: /* mark stack. Consider p to be valid if it is an interior */
1209: /* pointer. */
1210: /* The object p has passed a preliminary pointer validity */
1211: /* test, but we do not definitely know whether it is valid. */
1212: /* Mark bits are NOT atomically updated. Thus this must be the */
1213: /* only thread setting them. */
1.1 noro 1214: # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
1.4 noro 1215: void GC_mark_and_push_stack(p, source)
1.1 noro 1216: ptr_t source;
1217: # else
1.4 noro 1218: void GC_mark_and_push_stack(p)
1.1 noro 1219: # define source 0
1220: # endif
1221: register word p;
1222: {
1223: register word r;
1224: register hdr * hhdr;
1225: register int displ;
1226:
1227: GET_HDR(p, hhdr);
1228: if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
1.4 noro 1229: if (hhdr != 0) {
1.1 noro 1230: r = BASE(p);
1231: hhdr = HDR(r);
1232: displ = BYTES_TO_WORDS(HBLKDISPL(r));
1233: }
1234: } else {
1235: register map_entry_type map_entry;
1236:
1237: displ = HBLKDISPL(p);
1238: map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
1.4 noro 1239: if (map_entry >= MAX_OFFSET) {
1240: if (map_entry == OFFSET_TOO_BIG || !GC_all_interior_pointers) {
1.1 noro 1241: r = BASE(p);
1242: displ = BYTES_TO_WORDS(HBLKDISPL(r));
1243: if (r == 0) hhdr = 0;
1.4 noro 1244: } else {
1245: /* Offset invalid, but map reflects interior pointers */
1.1 noro 1246: hhdr = 0;
1.4 noro 1247: }
1.1 noro 1248: } else {
1249: displ = BYTES_TO_WORDS(displ);
1250: displ -= map_entry;
1251: r = (word)((word *)(HBLKPTR(p)) + displ);
1252: }
1253: }
1254: /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
1255: /* displ is the word index within the block. */
1256: if (hhdr == 0) {
1.4 noro 1257: # ifdef PRINT_BLACK_LIST
1258: GC_add_to_black_list_stack(p, source);
1259: # else
1260: GC_add_to_black_list_stack(p);
1261: # endif
1262: # undef source /* In case we had to define it. */
1.1 noro 1263: } else {
1264: if (!mark_bit_from_hdr(hhdr, displ)) {
1265: set_mark_bit_from_hdr(hhdr, displ);
1266: GC_STORE_BACK_PTR(source, (ptr_t)r);
1267: PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
1.4 noro 1268: GC_mark_stack_limit);
1.1 noro 1269: }
1270: }
1271: }
1272:
1273: # ifdef TRACE_BUF
1274:
1275: # define TRACE_ENTRIES 1000
1276:
1277: struct trace_entry {
1278: char * kind;
1279: word gc_no;
1280: word words_allocd;
1281: word arg1;
1282: word arg2;
1283: } GC_trace_buf[TRACE_ENTRIES];
1284:
1285: int GC_trace_buf_ptr = 0;
1286:
1287: void GC_add_trace_entry(char *kind, word arg1, word arg2)
1288: {
1289: GC_trace_buf[GC_trace_buf_ptr].kind = kind;
1290: GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
1291: GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
1292: GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
1293: GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
1294: GC_trace_buf_ptr++;
1295: if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
1296: }
1297:
1298: void GC_print_trace(word gc_no, GC_bool lock)
1299: {
1300: int i;
1301: struct trace_entry *p;
1302:
1303: if (lock) LOCK();
1304: for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
1305: if (i < 0) i = TRACE_ENTRIES-1;
1306: p = GC_trace_buf + i;
1307: if (p -> gc_no < gc_no || p -> kind == 0) return;
1308: printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
1309: p -> kind, p -> gc_no, p -> words_allocd,
1310: (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
1311: }
1312: printf("Trace incomplete\n");
1313: if (lock) UNLOCK();
1314: }
1315:
1316: # endif /* TRACE_BUF */
1317:
1318: /*
1319: * A version of GC_push_all that treats all interior pointers as valid
1320: * and scans the entire region immediately, in case the contents
1321: * change.
1322: */
1323: void GC_push_all_eager(bottom, top)
1324: ptr_t bottom;
1325: ptr_t top;
1326: {
1327: word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1328: word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
1329: register word *p;
1330: register word q;
1331: register word *lim;
1332: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1333: register ptr_t least_ha = GC_least_plausible_heap_addr;
1334: # define GC_greatest_plausible_heap_addr greatest_ha
1335: # define GC_least_plausible_heap_addr least_ha
1336:
1337: if (top == 0) return;
1338: /* check all pointers in range and put in push if they appear */
1339: /* to be valid. */
1340: lim = t - 1 /* longword */;
1341: for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
1342: q = *p;
1343: GC_PUSH_ONE_STACK(q, p);
1344: }
1345: # undef GC_greatest_plausible_heap_addr
1346: # undef GC_least_plausible_heap_addr
1347: }
1348:
1349: #ifndef THREADS
1350: /*
1351: * A version of GC_push_all that treats all interior pointers as valid
1352: * and scans part of the area immediately, to make sure that saved
1353: * register values are not lost.
1354: * Cold_gc_frame delimits the stack section that must be scanned
1355: * eagerly. A zero value indicates that no eager scanning is needed.
1356: */
1357: void GC_push_all_stack_partially_eager(bottom, top, cold_gc_frame)
1358: ptr_t bottom;
1359: ptr_t top;
1360: ptr_t cold_gc_frame;
1361: {
1.4 noro 1362: if (GC_all_interior_pointers) {
1.1 noro 1363: # define EAGER_BYTES 1024
1364: /* Push the hot end of the stack eagerly, so that register values */
1365: /* saved inside GC frames are marked before they disappear. */
1366: /* The rest of the marking can be deferred until later. */
1367: if (0 == cold_gc_frame) {
1368: GC_push_all_stack(bottom, top);
1369: return;
1370: }
1371: # ifdef STACK_GROWS_DOWN
1.6 ! noro 1372: GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
1.1 noro 1373: GC_push_all_eager(bottom, cold_gc_frame);
1374: # else /* STACK_GROWS_UP */
1.6 ! noro 1375: GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
1.1 noro 1376: GC_push_all_eager(cold_gc_frame, top);
1377: # endif /* STACK_GROWS_UP */
1.4 noro 1378: } else {
1.1 noro 1379: GC_push_all_eager(bottom, top);
1.4 noro 1380: }
1.1 noro 1381: # ifdef TRACE_BUF
1382: GC_add_trace_entry("GC_push_all_stack", bottom, top);
1383: # endif
1384: }
1385: #endif /* !THREADS */
1386:
1387: void GC_push_all_stack(bottom, top)
1388: ptr_t bottom;
1389: ptr_t top;
1390: {
1.4 noro 1391: if (GC_all_interior_pointers) {
1.1 noro 1392: GC_push_all(bottom, top);
1.4 noro 1393: } else {
1.1 noro 1394: GC_push_all_eager(bottom, top);
1.4 noro 1395: }
1.1 noro 1396: }
1397:
1.4 noro 1398: #if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
1.1 noro 1399: /* Push all objects reachable from marked objects in the given block */
1400: /* of size 1 objects. */
1401: void GC_push_marked1(h, hhdr)
1402: struct hblk *h;
1403: register hdr * hhdr;
1404: {
1.4 noro 1405: word * mark_word_addr = &(hhdr->hb_marks[0]);
1.1 noro 1406: register word *p;
1407: word *plim;
1408: register int i;
1409: register word q;
1410: register word mark_word;
1411: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1412: register ptr_t least_ha = GC_least_plausible_heap_addr;
1.4 noro 1413: register mse * mark_stack_top = GC_mark_stack_top;
1414: register mse * mark_stack_limit = GC_mark_stack_limit;
1415: # define GC_mark_stack_top mark_stack_top
1416: # define GC_mark_stack_limit mark_stack_limit
1.1 noro 1417: # define GC_greatest_plausible_heap_addr greatest_ha
1418: # define GC_least_plausible_heap_addr least_ha
1419:
1420: p = (word *)(h->hb_body);
1421: plim = (word *)(((word)h) + HBLKSIZE);
1422:
1423: /* go through all words in block */
1424: while( p < plim ) {
1425: mark_word = *mark_word_addr++;
1426: i = 0;
1427: while(mark_word != 0) {
1428: if (mark_word & 1) {
1429: q = p[i];
1430: GC_PUSH_ONE_HEAP(q, p + i);
1431: }
1432: i++;
1433: mark_word >>= 1;
1434: }
1435: p += WORDSZ;
1436: }
1437: # undef GC_greatest_plausible_heap_addr
1438: # undef GC_least_plausible_heap_addr
1.4 noro 1439: # undef GC_mark_stack_top
1440: # undef GC_mark_stack_limit
1441: GC_mark_stack_top = mark_stack_top;
1.1 noro 1442: }
1443:
1444:
1445: #ifndef UNALIGNED
1446:
1447: /* Push all objects reachable from marked objects in the given block */
1448: /* of size 2 objects. */
1449: void GC_push_marked2(h, hhdr)
1450: struct hblk *h;
1451: register hdr * hhdr;
1452: {
1.4 noro 1453: word * mark_word_addr = &(hhdr->hb_marks[0]);
1.1 noro 1454: register word *p;
1455: word *plim;
1456: register int i;
1457: register word q;
1458: register word mark_word;
1459: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1460: register ptr_t least_ha = GC_least_plausible_heap_addr;
1.4 noro 1461: register mse * mark_stack_top = GC_mark_stack_top;
1462: register mse * mark_stack_limit = GC_mark_stack_limit;
1463: # define GC_mark_stack_top mark_stack_top
1464: # define GC_mark_stack_limit mark_stack_limit
1.1 noro 1465: # define GC_greatest_plausible_heap_addr greatest_ha
1466: # define GC_least_plausible_heap_addr least_ha
1467:
1468: p = (word *)(h->hb_body);
1469: plim = (word *)(((word)h) + HBLKSIZE);
1470:
1471: /* go through all words in block */
1472: while( p < plim ) {
1473: mark_word = *mark_word_addr++;
1474: i = 0;
1475: while(mark_word != 0) {
1476: if (mark_word & 1) {
1477: q = p[i];
1478: GC_PUSH_ONE_HEAP(q, p + i);
1479: q = p[i+1];
1480: GC_PUSH_ONE_HEAP(q, p + i);
1481: }
1482: i += 2;
1483: mark_word >>= 2;
1484: }
1485: p += WORDSZ;
1486: }
1487: # undef GC_greatest_plausible_heap_addr
1488: # undef GC_least_plausible_heap_addr
1.4 noro 1489: # undef GC_mark_stack_top
1490: # undef GC_mark_stack_limit
1491: GC_mark_stack_top = mark_stack_top;
1.1 noro 1492: }
1493:
1494: /* Push all objects reachable from marked objects in the given block */
1495: /* of size 4 objects. */
1496: /* There is a risk of mark stack overflow here. But we handle that. */
1497: /* And only unmarked objects get pushed, so it's not very likely. */
1498: void GC_push_marked4(h, hhdr)
1499: struct hblk *h;
1500: register hdr * hhdr;
1501: {
1.4 noro 1502: word * mark_word_addr = &(hhdr->hb_marks[0]);
1.1 noro 1503: register word *p;
1504: word *plim;
1505: register int i;
1506: register word q;
1507: register word mark_word;
1508: register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1509: register ptr_t least_ha = GC_least_plausible_heap_addr;
1.4 noro 1510: register mse * mark_stack_top = GC_mark_stack_top;
1511: register mse * mark_stack_limit = GC_mark_stack_limit;
1512: # define GC_mark_stack_top mark_stack_top
1513: # define GC_mark_stack_limit mark_stack_limit
1.1 noro 1514: # define GC_greatest_plausible_heap_addr greatest_ha
1515: # define GC_least_plausible_heap_addr least_ha
1516:
1517: p = (word *)(h->hb_body);
1518: plim = (word *)(((word)h) + HBLKSIZE);
1519:
1520: /* go through all words in block */
1521: while( p < plim ) {
1522: mark_word = *mark_word_addr++;
1523: i = 0;
1524: while(mark_word != 0) {
1525: if (mark_word & 1) {
1526: q = p[i];
1527: GC_PUSH_ONE_HEAP(q, p + i);
1528: q = p[i+1];
1529: GC_PUSH_ONE_HEAP(q, p + i + 1);
1530: q = p[i+2];
1531: GC_PUSH_ONE_HEAP(q, p + i + 2);
1532: q = p[i+3];
1533: GC_PUSH_ONE_HEAP(q, p + i + 3);
1534: }
1535: i += 4;
1536: mark_word >>= 4;
1537: }
1538: p += WORDSZ;
1539: }
1540: # undef GC_greatest_plausible_heap_addr
1541: # undef GC_least_plausible_heap_addr
1.4 noro 1542: # undef GC_mark_stack_top
1543: # undef GC_mark_stack_limit
1544: GC_mark_stack_top = mark_stack_top;
1.1 noro 1545: }
1546:
1547: #endif /* UNALIGNED */
1548:
1549: #endif /* SMALL_CONFIG */
1550:
1551: /* Push all objects reachable from marked objects in the given block */
1552: void GC_push_marked(h, hhdr)
1553: struct hblk *h;
1554: register hdr * hhdr;
1555: {
1556: register int sz = hhdr -> hb_sz;
1.3 noro 1557: register int descr = hhdr -> hb_descr;
1.1 noro 1558: register word * p;
1559: register int word_no;
1560: register word * lim;
1561: register mse * GC_mark_stack_top_reg;
1.4 noro 1562: register mse * mark_stack_limit = GC_mark_stack_limit;
1.1 noro 1563:
1564: /* Some quick shortcuts: */
1.4 noro 1565: if ((0 | GC_DS_LENGTH) == descr) return;
1.1 noro 1566: if (GC_block_empty(hhdr)/* nothing marked */) return;
1.4 noro 1567: GC_n_rescuing_pages++;
1.1 noro 1568: GC_objects_are_marked = TRUE;
1569: if (sz > MAXOBJSZ) {
1.4 noro 1570: lim = (word *)h;
1.1 noro 1571: } else {
1572: lim = (word *)(h + 1) - sz;
1573: }
1574:
1575: switch(sz) {
1.4 noro 1576: # if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
1.1 noro 1577: case 1:
1578: GC_push_marked1(h, hhdr);
1579: break;
1580: # endif
1.4 noro 1581: # if !defined(SMALL_CONFIG) && !defined(UNALIGNED) && \
1582: !defined(USE_MARK_BYTES)
1.1 noro 1583: case 2:
1584: GC_push_marked2(h, hhdr);
1585: break;
1586: case 4:
1587: GC_push_marked4(h, hhdr);
1588: break;
1589: # endif
1590: default:
1591: GC_mark_stack_top_reg = GC_mark_stack_top;
1.4 noro 1592: for (p = (word *)h, word_no = 0; p <= lim; p += sz, word_no += sz) {
1.1 noro 1593: if (mark_bit_from_hdr(hhdr, word_no)) {
1594: /* Mark from fields inside the object */
1595: PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
1596: # ifdef GATHERSTATS
1597: /* Subtract this object from total, since it was */
1598: /* added in twice. */
1599: GC_composite_in_use -= sz;
1600: # endif
1601: }
1602: }
1603: GC_mark_stack_top = GC_mark_stack_top_reg;
1604: }
1605: }
1606:
1607: #ifndef SMALL_CONFIG
1608: /* Test whether any page in the given block is dirty */
1609: GC_bool GC_block_was_dirty(h, hhdr)
1610: struct hblk *h;
1611: register hdr * hhdr;
1612: {
1613: register int sz = hhdr -> hb_sz;
1614:
1615: if (sz < MAXOBJSZ) {
1616: return(GC_page_was_dirty(h));
1617: } else {
1618: register ptr_t p = (ptr_t)h;
1619: sz = WORDS_TO_BYTES(sz);
1620: while (p < (ptr_t)h + sz) {
1621: if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
1622: p += HBLKSIZE;
1623: }
1624: return(FALSE);
1625: }
1626: }
1627: #endif /* SMALL_CONFIG */
1628:
1629: /* Similar to GC_push_next_marked, but return address of next block */
1630: struct hblk * GC_push_next_marked(h)
1631: struct hblk *h;
1632: {
1633: register hdr * hhdr;
1634:
1635: h = GC_next_used_block(h);
1636: if (h == 0) return(0);
1637: hhdr = HDR(h);
1638: GC_push_marked(h, hhdr);
1639: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1640: }
1641:
1642: #ifndef SMALL_CONFIG
1643: /* Identical to above, but mark only from dirty pages */
1644: struct hblk * GC_push_next_marked_dirty(h)
1645: struct hblk *h;
1646: {
1.2 noro 1647: register hdr * hhdr;
1.1 noro 1648:
1649: if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
1650: for (;;) {
1651: h = GC_next_used_block(h);
1652: if (h == 0) return(0);
1653: hhdr = HDR(h);
1654: # ifdef STUBBORN_ALLOC
1655: if (hhdr -> hb_obj_kind == STUBBORN) {
1656: if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
1657: break;
1658: }
1659: } else {
1660: if (GC_block_was_dirty(h, hhdr)) break;
1661: }
1662: # else
1663: if (GC_block_was_dirty(h, hhdr)) break;
1664: # endif
1665: h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1666: }
1667: GC_push_marked(h, hhdr);
1668: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1669: }
1670: #endif
1671:
1672: /* Similar to above, but for uncollectable pages. Needed since we */
1673: /* do not clear marks for such pages, even for full collections. */
1674: struct hblk * GC_push_next_marked_uncollectable(h)
1675: struct hblk *h;
1676: {
1677: register hdr * hhdr = HDR(h);
1678:
1679: for (;;) {
1680: h = GC_next_used_block(h);
1681: if (h == 0) return(0);
1682: hhdr = HDR(h);
1683: if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
1684: h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1685: }
1686: GC_push_marked(h, hhdr);
1687: return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1688: }
1689:
1690:
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