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