Line data Source code
1 : /*
2 : * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
3 : * Copyright (c) 1991-1995 by Xerox Corporation. All rights reserved.
4 : * Copyright (c) 2000 by Hewlett-Packard Company. All rights reserved.
5 : *
6 : * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
7 : * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
8 : *
9 : * Permission is hereby granted to use or copy this program
10 : * for any purpose, provided the above notices are retained on all copies.
11 : * Permission to modify the code and to distribute modified code is granted,
12 : * provided the above notices are retained, and a notice that the code was
13 : * modified is included with the above copyright notice.
14 : *
15 : */
16 :
17 : #include "private/gc_pmark.h"
18 :
19 : #include <stdio.h>
20 :
21 : #if defined(MSWIN32) && defined(__GNUC__)
22 : # include <excpt.h>
23 : #endif
24 :
25 : /* We put this here to minimize the risk of inlining. */
26 : /*VARARGS*/
27 : #if defined(__BORLANDC__) || defined(__WATCOMC__) || defined(__CC_ARM)
28 : /*ARGSUSED*/
29 : void GC_noop(void *p, ...) {}
30 : #else
31 : # ifdef __DMC__
32 : void GC_noop(...) {}
33 : # else
34 257 : void GC_noop() {}
35 : # endif
36 : #endif
37 :
38 : /* Single argument version, robust against whole program analysis. */
39 : volatile word GC_noop_sink;
40 40889 : GC_API void GC_CALL GC_noop1(word x)
41 : {
42 40889 : GC_noop_sink = x;
43 40889 : }
44 :
45 : /* mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0} -- declared in gc_priv.h */
46 :
47 : GC_INNER unsigned GC_n_mark_procs = GC_RESERVED_MARK_PROCS;
48 :
49 : /* Initialize GC_obj_kinds properly and standard free lists properly. */
50 : /* This must be done statically since they may be accessed before */
51 : /* GC_init is called. */
52 : /* It's done here, since we need to deal with mark descriptors. */
53 : GC_INNER struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
54 : /* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */,
55 : 0 | GC_DS_LENGTH, FALSE, FALSE },
56 : /* NORMAL */ { &GC_objfreelist[0], 0,
57 : 0 | GC_DS_LENGTH, /* Adjusted in GC_init for EXTRA_BYTES */
58 : TRUE /* add length to descr */, TRUE },
59 : /* UNCOLLECTABLE */
60 : { &GC_uobjfreelist[0], 0,
61 : 0 | GC_DS_LENGTH, TRUE /* add length to descr */, TRUE },
62 : # ifdef ATOMIC_UNCOLLECTABLE
63 : /* AUNCOLLECTABLE */
64 : { &GC_auobjfreelist[0], 0,
65 : 0 | GC_DS_LENGTH, FALSE /* add length to descr */, FALSE },
66 : # endif
67 : # ifdef STUBBORN_ALLOC
68 : /*STUBBORN*/ { (void **)&GC_sobjfreelist[0], 0,
69 : 0 | GC_DS_LENGTH, TRUE /* add length to descr */, TRUE },
70 : # endif
71 : };
72 :
73 : # ifdef ATOMIC_UNCOLLECTABLE
74 : # ifdef STUBBORN_ALLOC
75 : # define GC_N_KINDS_INITIAL_VALUE 5
76 : # else
77 : # define GC_N_KINDS_INITIAL_VALUE 4
78 : # endif
79 : # else
80 : # ifdef STUBBORN_ALLOC
81 : # define GC_N_KINDS_INITIAL_VALUE 4
82 : # else
83 : # define GC_N_KINDS_INITIAL_VALUE 3
84 : # endif
85 : # endif
86 :
87 : GC_INNER unsigned GC_n_kinds = GC_N_KINDS_INITIAL_VALUE;
88 :
89 : # ifndef INITIAL_MARK_STACK_SIZE
90 : # define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
91 : /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a */
92 : /* multiple of HBLKSIZE. */
93 : /* The incremental collector actually likes a larger */
94 : /* size, since it want to push all marked dirty objs */
95 : /* before marking anything new. Currently we let it */
96 : /* grow dynamically. */
97 : # endif
98 :
99 : /*
100 : * Limits of stack for GC_mark routine.
101 : * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
102 : * need to be marked from.
103 : */
104 :
105 : STATIC word GC_n_rescuing_pages = 0;
106 : /* Number of dirty pages we marked from */
107 : /* excludes ptrfree pages, etc. */
108 :
109 : GC_INNER mse * GC_mark_stack = NULL;
110 : GC_INNER mse * GC_mark_stack_limit = NULL;
111 : GC_INNER size_t GC_mark_stack_size = 0;
112 :
113 : #ifdef PARALLEL_MARK
114 : GC_INNER mse * volatile GC_mark_stack_top = NULL;
115 : /* Updated only with mark lock held, but read asynchronously. */
116 : STATIC volatile AO_t GC_first_nonempty = 0;
117 : /* Lowest entry on mark stack */
118 : /* that may be nonempty. */
119 : /* Updated only by initiating */
120 : /* thread. */
121 : #else
122 : GC_INNER mse * GC_mark_stack_top = NULL;
123 : #endif
124 :
125 : GC_INNER mark_state_t GC_mark_state = MS_NONE;
126 :
127 : GC_INNER GC_bool GC_mark_stack_too_small = FALSE;
128 :
129 : static struct hblk * scan_ptr;
130 :
131 : STATIC GC_bool GC_objects_are_marked = FALSE;
132 : /* Are there collectable marked objects in the heap? */
133 :
134 : /* Is a collection in progress? Note that this can return true in the */
135 : /* nonincremental case, if a collection has been abandoned and the */
136 : /* mark state is now MS_INVALID. */
137 0 : GC_INNER GC_bool GC_collection_in_progress(void)
138 : {
139 0 : return(GC_mark_state != MS_NONE);
140 : }
141 :
142 : /* clear all mark bits in the header */
143 124293 : GC_INNER void GC_clear_hdr_marks(hdr *hhdr)
144 : {
145 124293 : size_t last_bit = FINAL_MARK_BIT(hhdr -> hb_sz);
146 124293 : BZERO(hhdr -> hb_marks, sizeof(hhdr->hb_marks));
147 124293 : set_mark_bit_from_hdr(hhdr, last_bit);
148 124293 : hhdr -> hb_n_marks = 0;
149 124293 : }
150 :
151 : /* Set all mark bits in the header. Used for uncollectable blocks. */
152 4224 : GC_INNER void GC_set_hdr_marks(hdr *hhdr)
153 : {
154 : unsigned i;
155 4224 : size_t sz = hhdr -> hb_sz;
156 4224 : unsigned n_marks = (unsigned)FINAL_MARK_BIT(sz);
157 :
158 : # ifdef USE_MARK_BYTES
159 : for (i = 0; i <= n_marks; i += (unsigned)MARK_BIT_OFFSET(sz)) {
160 : hhdr -> hb_marks[i] = 1;
161 : }
162 : # else
163 21451 : for (i = 0; i < divWORDSZ(n_marks + WORDSZ); ++i) {
164 17227 : hhdr -> hb_marks[i] = ONES;
165 : }
166 : # endif
167 : # ifdef MARK_BIT_PER_OBJ
168 : hhdr -> hb_n_marks = n_marks - 1;
169 : # else
170 4224 : hhdr -> hb_n_marks = HBLK_OBJS(sz);
171 : # endif
172 4224 : }
173 :
174 : /*
175 : * Clear all mark bits associated with block h.
176 : */
177 : /*ARGSUSED*/
178 76399 : static void clear_marks_for_block(struct hblk *h, word dummy)
179 : {
180 76399 : register hdr * hhdr = HDR(h);
181 :
182 76399 : if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return;
183 : /* Mark bit for these is cleared only once the object is */
184 : /* explicitly deallocated. This either frees the block, or */
185 : /* the bit is cleared once the object is on the free list. */
186 72188 : GC_clear_hdr_marks(hhdr);
187 : }
188 :
189 : /* Slow but general routines for setting/clearing/asking about mark bits */
190 12541 : void GC_set_mark_bit(ptr_t p)
191 : {
192 12541 : struct hblk *h = HBLKPTR(p);
193 12541 : hdr * hhdr = HDR(h);
194 12541 : word bit_no = MARK_BIT_NO(p - (ptr_t)h, hhdr -> hb_sz);
195 :
196 12541 : if (!mark_bit_from_hdr(hhdr, bit_no)) {
197 662 : set_mark_bit_from_hdr(hhdr, bit_no);
198 662 : ++hhdr -> hb_n_marks;
199 : }
200 12541 : }
201 :
202 0 : void GC_clear_mark_bit(ptr_t p)
203 : {
204 0 : struct hblk *h = HBLKPTR(p);
205 0 : hdr * hhdr = HDR(h);
206 0 : word bit_no = MARK_BIT_NO(p - (ptr_t)h, hhdr -> hb_sz);
207 :
208 0 : if (mark_bit_from_hdr(hhdr, bit_no)) {
209 : size_t n_marks;
210 0 : clear_mark_bit_from_hdr(hhdr, bit_no);
211 0 : n_marks = hhdr -> hb_n_marks - 1;
212 : # ifdef PARALLEL_MARK
213 : if (n_marks != 0 || !GC_parallel)
214 : hhdr -> hb_n_marks = n_marks;
215 : /* Don't decrement to zero. The counts are approximate due to */
216 : /* concurrency issues, but we need to ensure that a count of */
217 : /* zero implies an empty block. */
218 : # else
219 0 : hhdr -> hb_n_marks = n_marks;
220 : # endif
221 : }
222 0 : }
223 :
224 115048 : GC_bool GC_is_marked(ptr_t p)
225 : {
226 115048 : struct hblk *h = HBLKPTR(p);
227 115048 : hdr * hhdr = HDR(h);
228 115048 : word bit_no = MARK_BIT_NO(p - (ptr_t)h, hhdr -> hb_sz);
229 :
230 115048 : return((GC_bool)mark_bit_from_hdr(hhdr, bit_no));
231 : }
232 :
233 :
234 : /*
235 : * Clear mark bits in all allocated heap blocks. This invalidates
236 : * the marker invariant, and sets GC_mark_state to reflect this.
237 : * (This implicitly starts marking to reestablish the invariant.)
238 : */
239 252 : GC_INNER void GC_clear_marks(void)
240 : {
241 252 : GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
242 252 : GC_objects_are_marked = FALSE;
243 252 : GC_mark_state = MS_INVALID;
244 252 : scan_ptr = 0;
245 252 : }
246 :
247 : #ifdef CHECKSUMS
248 : void GC_check_dirty(void);
249 : #endif
250 :
251 : /* Initiate a garbage collection. Initiates a full collection if the */
252 : /* mark state is invalid. */
253 252 : GC_INNER void GC_initiate_gc(void)
254 : {
255 : # ifndef GC_DISABLE_INCREMENTAL
256 252 : if (GC_dirty_maintained) GC_read_dirty();
257 : # endif
258 : # ifdef STUBBORN_ALLOC
259 : GC_read_changed();
260 : # endif
261 : # ifdef CHECKSUMS
262 : if (GC_dirty_maintained) GC_check_dirty();
263 : # endif
264 252 : GC_n_rescuing_pages = 0;
265 252 : if (GC_mark_state == MS_NONE) {
266 0 : GC_mark_state = MS_PUSH_RESCUERS;
267 252 : } else if (GC_mark_state != MS_INVALID) {
268 0 : ABORT("Unexpected state");
269 : } /* else this is really a full collection, and mark */
270 : /* bits are invalid. */
271 252 : scan_ptr = 0;
272 252 : }
273 :
274 : #ifdef PARALLEL_MARK
275 : STATIC void GC_do_parallel_mark(void); /* initiate parallel marking. */
276 : #endif /* PARALLEL_MARK */
277 :
278 : #ifdef GC_DISABLE_INCREMENTAL
279 : # define GC_push_next_marked_dirty(h) GC_push_next_marked(h)
280 : #else
281 : STATIC struct hblk * GC_push_next_marked_dirty(struct hblk *h);
282 : /* Invoke GC_push_marked on next dirty block above h. */
283 : /* Return a pointer just past the end of this block. */
284 : #endif /* !GC_DISABLE_INCREMENTAL */
285 : STATIC struct hblk * GC_push_next_marked(struct hblk *h);
286 : /* Ditto, but also mark from clean pages. */
287 : STATIC struct hblk * GC_push_next_marked_uncollectable(struct hblk *h);
288 : /* Ditto, but mark only from uncollectable pages. */
289 :
290 : static void alloc_mark_stack(size_t);
291 :
292 : # if (defined(MSWIN32) || defined(MSWINCE)) && !defined(__GNUC__) \
293 : || defined(MSWIN32) && defined(I386) /* for Win98 */ \
294 : || defined(USE_PROC_FOR_LIBRARIES) && defined(THREADS)
295 : /* Under rare conditions, we may end up marking from nonexistent memory. */
296 : /* Hence we need to be prepared to recover by running GC_mark_some */
297 : /* with a suitable handler in place. */
298 : /* FIXME: Should we really need it for WinCE? If yes then */
299 : /* WRAP_MARK_SOME should be also defined for CeGCC which requires */
300 : /* CPU/OS-specific code in mark_ex_handler() and GC_mark_some() */
301 : /* (for manual stack unwinding and exception handler installation). */
302 : # define WRAP_MARK_SOME
303 : # endif
304 :
305 : /* Perform a small amount of marking. */
306 : /* We try to touch roughly a page of memory. */
307 : /* Return TRUE if we just finished a mark phase. */
308 : /* Cold_gc_frame is an address inside a GC frame that */
309 : /* remains valid until all marking is complete. */
310 : /* A zero value indicates that it's OK to miss some */
311 : /* register values. */
312 : /* We hold the allocation lock. In the case of */
313 : /* incremental collection, the world may not be stopped.*/
314 : #ifdef WRAP_MARK_SOME
315 : /* For win32, this is called after we establish a structured */
316 : /* exception handler, in case Windows unmaps one of our root */
317 : /* segments. See below. In either case, we acquire the */
318 : /* allocator lock long before we get here. */
319 : STATIC GC_bool GC_mark_some_inner(ptr_t cold_gc_frame)
320 : #else
321 74573 : GC_INNER GC_bool GC_mark_some(ptr_t cold_gc_frame)
322 : #endif
323 : {
324 74573 : switch(GC_mark_state) {
325 : case MS_NONE:
326 0 : return(FALSE);
327 :
328 : case MS_PUSH_RESCUERS:
329 0 : if (GC_mark_stack_top
330 0 : >= GC_mark_stack_limit - INITIAL_MARK_STACK_SIZE/2) {
331 : /* Go ahead and mark, even though that might cause us to */
332 : /* see more marked dirty objects later on. Avoid this */
333 : /* in the future. */
334 0 : GC_mark_stack_too_small = TRUE;
335 0 : MARK_FROM_MARK_STACK();
336 0 : return(FALSE);
337 : } else {
338 0 : scan_ptr = GC_push_next_marked_dirty(scan_ptr);
339 0 : if (scan_ptr == 0) {
340 0 : if (GC_print_stats) {
341 0 : GC_log_printf("Marked from %lu dirty pages\n",
342 : (unsigned long)GC_n_rescuing_pages);
343 : }
344 0 : GC_push_roots(FALSE, cold_gc_frame);
345 0 : GC_objects_are_marked = TRUE;
346 0 : if (GC_mark_state != MS_INVALID) {
347 0 : GC_mark_state = MS_ROOTS_PUSHED;
348 : }
349 : }
350 : }
351 0 : return(FALSE);
352 :
353 : case MS_PUSH_UNCOLLECTABLE:
354 4570 : if (GC_mark_stack_top
355 4570 : >= GC_mark_stack + GC_mark_stack_size/4) {
356 : # ifdef PARALLEL_MARK
357 : /* Avoid this, since we don't parallelize the marker */
358 : /* here. */
359 : if (GC_parallel) GC_mark_stack_too_small = TRUE;
360 : # endif
361 107 : MARK_FROM_MARK_STACK();
362 107 : return(FALSE);
363 : } else {
364 4463 : scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
365 4463 : if (scan_ptr == 0) {
366 252 : GC_push_roots(TRUE, cold_gc_frame);
367 252 : GC_objects_are_marked = TRUE;
368 252 : if (GC_mark_state != MS_INVALID) {
369 252 : GC_mark_state = MS_ROOTS_PUSHED;
370 : }
371 : }
372 : }
373 4463 : return(FALSE);
374 :
375 : case MS_ROOTS_PUSHED:
376 : # ifdef PARALLEL_MARK
377 : /* In the incremental GC case, this currently doesn't */
378 : /* quite do the right thing, since it runs to */
379 : /* completion. On the other hand, starting a */
380 : /* parallel marker is expensive, so perhaps it is */
381 : /* the right thing? */
382 : /* Eventually, incremental marking should run */
383 : /* asynchronously in multiple threads, without grabbing */
384 : /* the allocation lock. */
385 : if (GC_parallel) {
386 : GC_do_parallel_mark();
387 : GC_ASSERT(GC_mark_stack_top < (mse *)GC_first_nonempty);
388 : GC_mark_stack_top = GC_mark_stack - 1;
389 : if (GC_mark_stack_too_small) {
390 : alloc_mark_stack(2*GC_mark_stack_size);
391 : }
392 : if (GC_mark_state == MS_ROOTS_PUSHED) {
393 : GC_mark_state = MS_NONE;
394 : return(TRUE);
395 : } else {
396 : return(FALSE);
397 : }
398 : }
399 : # endif
400 60246 : if (GC_mark_stack_top >= GC_mark_stack) {
401 59994 : MARK_FROM_MARK_STACK();
402 59994 : return(FALSE);
403 : } else {
404 252 : GC_mark_state = MS_NONE;
405 252 : if (GC_mark_stack_too_small) {
406 0 : alloc_mark_stack(2*GC_mark_stack_size);
407 : }
408 252 : return(TRUE);
409 : }
410 :
411 : case MS_INVALID:
412 : case MS_PARTIALLY_INVALID:
413 9757 : if (!GC_objects_are_marked) {
414 252 : GC_mark_state = MS_PUSH_UNCOLLECTABLE;
415 252 : return(FALSE);
416 : }
417 9505 : if (GC_mark_stack_top >= GC_mark_stack) {
418 4648 : MARK_FROM_MARK_STACK();
419 4648 : return(FALSE);
420 : }
421 4857 : if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {
422 : /* About to start a heap scan for marked objects. */
423 : /* Mark stack is empty. OK to reallocate. */
424 6 : if (GC_mark_stack_too_small) {
425 6 : alloc_mark_stack(2*GC_mark_stack_size);
426 : }
427 6 : GC_mark_state = MS_PARTIALLY_INVALID;
428 : }
429 4857 : scan_ptr = GC_push_next_marked(scan_ptr);
430 4857 : if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
431 6 : GC_push_roots(TRUE, cold_gc_frame);
432 6 : GC_objects_are_marked = TRUE;
433 6 : if (GC_mark_state != MS_INVALID) {
434 6 : GC_mark_state = MS_ROOTS_PUSHED;
435 : }
436 : }
437 4857 : return(FALSE);
438 : default:
439 0 : ABORT("GC_mark_some: bad state");
440 0 : return(FALSE);
441 : }
442 : }
443 :
444 : #ifdef WRAP_MARK_SOME
445 :
446 : # if (defined(MSWIN32) || defined(MSWINCE)) && defined(__GNUC__)
447 :
448 : typedef struct {
449 : EXCEPTION_REGISTRATION ex_reg;
450 : void *alt_path;
451 : } ext_ex_regn;
452 :
453 : static EXCEPTION_DISPOSITION mark_ex_handler(
454 : struct _EXCEPTION_RECORD *ex_rec,
455 : void *est_frame,
456 : struct _CONTEXT *context,
457 : void *disp_ctxt)
458 : {
459 : if (ex_rec->ExceptionCode == STATUS_ACCESS_VIOLATION) {
460 : ext_ex_regn *xer = (ext_ex_regn *)est_frame;
461 :
462 : /* Unwind from the inner function assuming the standard */
463 : /* function prologue. */
464 : /* Assumes code has not been compiled with */
465 : /* -fomit-frame-pointer. */
466 : context->Esp = context->Ebp;
467 : context->Ebp = *((DWORD *)context->Esp);
468 : context->Esp = context->Esp - 8;
469 :
470 : /* Resume execution at the "real" handler within the */
471 : /* wrapper function. */
472 : context->Eip = (DWORD )(xer->alt_path);
473 :
474 : return ExceptionContinueExecution;
475 :
476 : } else {
477 : return ExceptionContinueSearch;
478 : }
479 : }
480 : # endif /* __GNUC__ && MSWIN32 */
481 :
482 : #if defined(GC_WIN32_THREADS) && !defined(__GNUC__)
483 : GC_bool GC_started_thread_while_stopped(void);
484 : /* In win32_threads.c. Did we invalidate mark phase with an */
485 : /* unexpected thread start? */
486 : #endif
487 :
488 : GC_INNER GC_bool GC_mark_some(ptr_t cold_gc_frame)
489 : {
490 : GC_bool ret_val;
491 :
492 : # if defined(MSWIN32) || defined(MSWINCE)
493 : # ifndef __GNUC__
494 : /* Windows 98 appears to asynchronously create and remove */
495 : /* writable memory mappings, for reasons we haven't yet */
496 : /* understood. Since we look for writable regions to */
497 : /* determine the root set, we may try to mark from an */
498 : /* address range that disappeared since we started the */
499 : /* collection. Thus we have to recover from faults here. */
500 : /* This code does not appear to be necessary for Windows */
501 : /* 95/NT/2000+. Note that this code should never generate */
502 : /* an incremental GC write fault. */
503 : /* This code seems to be necessary for WinCE (at least in */
504 : /* the case we'd decide to add MEM_PRIVATE sections to */
505 : /* data roots in GC_register_dynamic_libraries()). */
506 : /* It's conceivable that this is the same issue with */
507 : /* terminating threads that we see with Linux and */
508 : /* USE_PROC_FOR_LIBRARIES. */
509 :
510 : __try {
511 : ret_val = GC_mark_some_inner(cold_gc_frame);
512 : } __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?
513 : EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) {
514 : goto handle_ex;
515 : }
516 : # ifdef GC_WIN32_THREADS
517 : /* With DllMain-based thread tracking, a thread may have */
518 : /* started while we were marking. This is logically equivalent */
519 : /* to the exception case; our results are invalid and we have */
520 : /* to start over. This cannot be prevented since we can't */
521 : /* block in DllMain. */
522 : if (GC_started_thread_while_stopped()) goto handle_ex;
523 : # endif
524 : rm_handler:
525 : return ret_val;
526 :
527 : # else /* __GNUC__ */
528 :
529 : /* Manually install an exception handler since GCC does */
530 : /* not yet support Structured Exception Handling (SEH) on */
531 : /* Win32. */
532 :
533 : ext_ex_regn er;
534 :
535 : er.alt_path = &&handle_ex;
536 : er.ex_reg.handler = mark_ex_handler;
537 : __asm__ __volatile__ ("movl %%fs:0, %0" : "=r" (er.ex_reg.prev));
538 : __asm__ __volatile__ ("movl %0, %%fs:0" : : "r" (&er));
539 : ret_val = GC_mark_some_inner(cold_gc_frame);
540 : /* Prevent GCC from considering the following code unreachable */
541 : /* and thus eliminating it. */
542 : if (er.alt_path == 0)
543 : goto handle_ex;
544 : rm_handler:
545 : /* Uninstall the exception handler */
546 : __asm__ __volatile__ ("mov %0, %%fs:0" : : "r" (er.ex_reg.prev));
547 : return ret_val;
548 :
549 : # endif /* __GNUC__ */
550 : # else /* !MSWIN32 */
551 : /* Here we are handling the case in which /proc is used for root */
552 : /* finding, and we have threads. We may find a stack for a */
553 : /* thread that is in the process of exiting, and disappears */
554 : /* while we are marking it. This seems extremely difficult to */
555 : /* avoid otherwise. */
556 : if (GC_incremental) {
557 : WARN("Incremental GC incompatible with /proc roots\n", 0);
558 : /* I'm not sure if this could still work ... */
559 : }
560 : GC_setup_temporary_fault_handler();
561 : if(SETJMP(GC_jmp_buf) != 0) goto handle_ex;
562 : ret_val = GC_mark_some_inner(cold_gc_frame);
563 : rm_handler:
564 : GC_reset_fault_handler();
565 : return ret_val;
566 :
567 : # endif /* !MSWIN32 */
568 :
569 : handle_ex:
570 : /* Exception handler starts here for all cases. */
571 : if (GC_print_stats) {
572 : GC_log_printf(
573 : "Caught ACCESS_VIOLATION in marker; memory mapping disappeared\n");
574 : }
575 :
576 : /* We have bad roots on the stack. Discard mark stack. */
577 : /* Rescan from marked objects. Redetermine roots. */
578 : GC_invalidate_mark_state();
579 : scan_ptr = 0;
580 :
581 : ret_val = FALSE;
582 : goto rm_handler; /* Back to platform-specific code. */
583 : }
584 : #endif /* WRAP_MARK_SOME */
585 :
586 49800 : GC_INNER GC_bool GC_mark_stack_empty(void)
587 : {
588 49800 : return(GC_mark_stack_top < GC_mark_stack);
589 : }
590 :
591 252 : GC_INNER void GC_invalidate_mark_state(void)
592 : {
593 252 : GC_mark_state = MS_INVALID;
594 252 : GC_mark_stack_top = GC_mark_stack-1;
595 252 : }
596 :
597 37 : GC_INNER mse * GC_signal_mark_stack_overflow(mse *msp)
598 : {
599 37 : GC_mark_state = MS_INVALID;
600 37 : GC_mark_stack_too_small = TRUE;
601 37 : if (GC_print_stats) {
602 0 : GC_log_printf("Mark stack overflow; current size = %lu entries\n",
603 : (unsigned long)GC_mark_stack_size);
604 : }
605 37 : return(msp - GC_MARK_STACK_DISCARDS);
606 : }
607 :
608 : /*
609 : * Mark objects pointed to by the regions described by
610 : * mark stack entries between mark_stack and mark_stack_top,
611 : * inclusive. Assumes the upper limit of a mark stack entry
612 : * is never 0. A mark stack entry never has size 0.
613 : * We try to traverse on the order of a hblk of memory before we return.
614 : * Caller is responsible for calling this until the mark stack is empty.
615 : * Note that this is the most performance critical routine in the
616 : * collector. Hence it contains all sorts of ugly hacks to speed
617 : * things up. In particular, we avoid procedure calls on the common
618 : * path, we take advantage of peculiarities of the mark descriptor
619 : * encoding, we optionally maintain a cache for the block address to
620 : * header mapping, we prefetch when an object is "grayed", etc.
621 : */
622 77281 : GC_INNER mse * GC_mark_from(mse *mark_stack_top, mse *mark_stack,
623 : mse *mark_stack_limit)
624 : {
625 77281 : signed_word credit = HBLKSIZE; /* Remaining credit for marking work */
626 : ptr_t current_p; /* Pointer to current candidate ptr. */
627 : word current; /* Candidate pointer. */
628 : ptr_t limit; /* (Incl) limit of current candidate */
629 : /* range */
630 : word descr;
631 77281 : ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
632 77281 : ptr_t least_ha = GC_least_plausible_heap_addr;
633 : DECLARE_HDR_CACHE;
634 :
635 : # define SPLIT_RANGE_WORDS 128 /* Must be power of 2. */
636 :
637 77281 : GC_objects_are_marked = TRUE;
638 77281 : INIT_HDR_CACHE;
639 : # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
640 : while (mark_stack_top >= mark_stack && credit >= 0)
641 : # else
642 1262609 : while ((((ptr_t)mark_stack_top - (ptr_t)mark_stack) | credit) >= 0)
643 : # endif
644 : {
645 1108047 : current_p = mark_stack_top -> mse_start;
646 1108047 : descr = mark_stack_top -> mse_descr;
647 : retry:
648 : /* current_p and descr describe the current object. */
649 : /* *mark_stack_top is vacant. */
650 : /* The following is 0 only for small objects described by a simple */
651 : /* length descriptor. For many applications this is the common */
652 : /* case, so we try to detect it quickly. */
653 1108047 : if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | GC_DS_TAGS)) {
654 156464 : word tag = descr & GC_DS_TAGS;
655 :
656 156464 : switch(tag) {
657 : case GC_DS_LENGTH:
658 : /* Large length. */
659 : /* Process part of the range to avoid pushing too much on the */
660 : /* stack. */
661 : GC_ASSERT(descr < (word)GC_greatest_plausible_heap_addr
662 : - (word)GC_least_plausible_heap_addr);
663 : # ifdef ENABLE_TRACE
664 : if (GC_trace_addr >= current_p
665 : && GC_trace_addr < current_p + descr) {
666 : GC_log_printf("GC:%u Large section; start %p len %lu\n",
667 : (unsigned)GC_gc_no, current_p, (unsigned long)descr);
668 : }
669 : # endif /* ENABLE_TRACE */
670 : # ifdef PARALLEL_MARK
671 : # define SHARE_BYTES 2048
672 : if (descr > SHARE_BYTES && GC_parallel
673 : && mark_stack_top < mark_stack_limit - 1) {
674 : int new_size = (descr/2) & ~(sizeof(word)-1);
675 : mark_stack_top -> mse_start = current_p;
676 : mark_stack_top -> mse_descr = new_size + sizeof(word);
677 : /* makes sure we handle */
678 : /* misaligned pointers. */
679 : mark_stack_top++;
680 : # ifdef ENABLE_TRACE
681 : if (GC_trace_addr >= current_p
682 : && GC_trace_addr < current_p + descr) {
683 : GC_log_printf("GC:%u Splitting (parallel) %p at %p\n",
684 : (unsigned)GC_gc_no, current_p, current_p + new_size);
685 : }
686 : # endif /* ENABLE_TRACE */
687 : current_p += new_size;
688 : descr -= new_size;
689 : goto retry;
690 : }
691 : # endif /* PARALLEL_MARK */
692 156464 : mark_stack_top -> mse_start =
693 : limit = current_p + WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
694 156464 : mark_stack_top -> mse_descr =
695 156464 : descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
696 : # ifdef ENABLE_TRACE
697 : if (GC_trace_addr >= current_p
698 : && GC_trace_addr < current_p + descr) {
699 : GC_log_printf("GC:%u Splitting %p at %p\n",
700 : (unsigned)GC_gc_no, current_p, limit);
701 : }
702 : # endif /* ENABLE_TRACE */
703 : /* Make sure that pointers overlapping the two ranges are */
704 : /* considered. */
705 156464 : limit += sizeof(word) - ALIGNMENT;
706 156464 : break;
707 : case GC_DS_BITMAP:
708 0 : mark_stack_top--;
709 : # ifdef ENABLE_TRACE
710 : if (GC_trace_addr >= current_p
711 : && GC_trace_addr < current_p + WORDS_TO_BYTES(WORDSZ-2)) {
712 : GC_log_printf("GC:%u Tracing from %p bitmap descr %lu\n",
713 : (unsigned)GC_gc_no, current_p, (unsigned long)descr);
714 : }
715 : # endif /* ENABLE_TRACE */
716 0 : descr &= ~GC_DS_TAGS;
717 0 : credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
718 0 : while (descr != 0) {
719 0 : if ((signed_word)descr < 0) {
720 0 : current = *(word *)current_p;
721 : FIXUP_POINTER(current);
722 0 : if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
723 0 : PREFETCH((ptr_t)current);
724 : # ifdef ENABLE_TRACE
725 : if (GC_trace_addr == current_p) {
726 : GC_log_printf("GC:%u Considering(3) %p -> %p\n",
727 : (unsigned)GC_gc_no, current_p, (ptr_t)current);
728 : }
729 : # endif /* ENABLE_TRACE */
730 0 : PUSH_CONTENTS((ptr_t)current, mark_stack_top,
731 : mark_stack_limit, current_p, exit1);
732 : }
733 : }
734 0 : descr <<= 1;
735 0 : current_p += sizeof(word);
736 : }
737 0 : continue;
738 : case GC_DS_PROC:
739 0 : mark_stack_top--;
740 : # ifdef ENABLE_TRACE
741 : if (GC_trace_addr >= current_p
742 : && GC_base(current_p) != 0
743 : && GC_base(current_p) == GC_base(GC_trace_addr)) {
744 : GC_log_printf("GC:%u Tracing from %p proc descr %lu\n",
745 : (unsigned)GC_gc_no, current_p, (unsigned long)descr);
746 : }
747 : # endif /* ENABLE_TRACE */
748 0 : credit -= GC_PROC_BYTES;
749 0 : mark_stack_top =
750 0 : (*PROC(descr))
751 : ((word *)current_p, mark_stack_top,
752 : mark_stack_limit, ENV(descr));
753 0 : continue;
754 : case GC_DS_PER_OBJECT:
755 0 : if ((signed_word)descr >= 0) {
756 : /* Descriptor is in the object. */
757 0 : descr = *(word *)(current_p + descr - GC_DS_PER_OBJECT);
758 : } else {
759 : /* Descriptor is in type descriptor pointed to by first */
760 : /* word in object. */
761 0 : ptr_t type_descr = *(ptr_t *)current_p;
762 : /* type_descr is either a valid pointer to the descriptor */
763 : /* structure, or this object was on a free list. If it */
764 : /* it was anything but the last object on the free list, */
765 : /* we will misinterpret the next object on the free list as */
766 : /* the type descriptor, and get a 0 GC descriptor, which */
767 : /* is ideal. Unfortunately, we need to check for the last */
768 : /* object case explicitly. */
769 0 : if (0 == type_descr) {
770 : /* Rarely executed. */
771 0 : mark_stack_top--;
772 0 : continue;
773 : }
774 0 : descr = *(word *)(type_descr
775 : - (descr + (GC_INDIR_PER_OBJ_BIAS
776 : - GC_DS_PER_OBJECT)));
777 : }
778 0 : if (0 == descr) {
779 : /* Can happen either because we generated a 0 descriptor */
780 : /* or we saw a pointer to a free object. */
781 0 : mark_stack_top--;
782 0 : continue;
783 : }
784 0 : goto retry;
785 : default:
786 : /* Can't happen. */
787 0 : limit = 0; /* initialized to prevent warning. */
788 : }
789 : } else /* Small object with length descriptor */ {
790 951583 : mark_stack_top--;
791 951583 : limit = current_p + (word)descr;
792 : }
793 : # ifdef ENABLE_TRACE
794 : if (GC_trace_addr >= current_p
795 : && GC_trace_addr < limit) {
796 : GC_log_printf("GC:%u Tracing from %p len %lu\n",
797 : (int)GC_gc_no, current_p, (unsigned long)descr);
798 : }
799 : # endif /* ENABLE_TRACE */
800 : /* The simple case in which we're scanning a range. */
801 : GC_ASSERT(!((word)current_p & (ALIGNMENT-1)));
802 1108047 : credit -= limit - current_p;
803 1108047 : limit -= sizeof(word);
804 : {
805 : # define PREF_DIST 4
806 :
807 : # ifndef SMALL_CONFIG
808 : word deferred;
809 :
810 : /* Try to prefetch the next pointer to be examined asap. */
811 : /* Empirically, this also seems to help slightly without */
812 : /* prefetches, at least on linux/X86. Presumably this loop */
813 : /* ends up with less register pressure, and gcc thus ends up */
814 : /* generating slightly better code. Overall gcc code quality */
815 : /* for this loop is still not great. */
816 : for(;;) {
817 16649290 : PREFETCH(limit - PREF_DIST*CACHE_LINE_SIZE);
818 : GC_ASSERT(limit >= current_p);
819 16649290 : deferred = *(word *)limit;
820 : FIXUP_POINTER(deferred);
821 16649290 : limit -= ALIGNMENT;
822 16649290 : if ((ptr_t)deferred >= least_ha && (ptr_t)deferred < greatest_ha) {
823 197529 : PREFETCH((ptr_t)deferred);
824 197529 : break;
825 : }
826 16451761 : if (current_p > limit) goto next_object;
827 : /* Unroll once, so we don't do too many of the prefetches */
828 : /* based on limit. */
829 16300190 : deferred = *(word *)limit;
830 : FIXUP_POINTER(deferred);
831 16300190 : limit -= ALIGNMENT;
832 16300190 : if ((ptr_t)deferred >= least_ha && (ptr_t)deferred < greatest_ha) {
833 308116 : PREFETCH((ptr_t)deferred);
834 308116 : break;
835 : }
836 15992074 : if (current_p > limit) goto next_object;
837 15541243 : }
838 : # endif
839 :
840 5263984 : while (current_p <= limit) {
841 : /* Empirically, unrolling this loop doesn't help a lot. */
842 : /* Since PUSH_CONTENTS expands to a lot of code, */
843 : /* we don't. */
844 4252694 : current = *(word *)current_p;
845 : FIXUP_POINTER(current);
846 4252694 : PREFETCH(current_p + PREF_DIST*CACHE_LINE_SIZE);
847 4252694 : if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
848 : /* Prefetch the contents of the object we just pushed. It's */
849 : /* likely we will need them soon. */
850 1955052 : PREFETCH((ptr_t)current);
851 : # ifdef ENABLE_TRACE
852 : if (GC_trace_addr == current_p) {
853 : GC_log_printf("GC:%u Considering(1) %p -> %p\n",
854 : (unsigned)GC_gc_no, current_p, (ptr_t)current);
855 : }
856 : # endif /* ENABLE_TRACE */
857 1955052 : PUSH_CONTENTS((ptr_t)current, mark_stack_top,
858 : mark_stack_limit, current_p, exit2);
859 : }
860 4252694 : current_p += ALIGNMENT;
861 : }
862 :
863 : # ifndef SMALL_CONFIG
864 : /* We still need to mark the entry we previously prefetched. */
865 : /* We already know that it passes the preliminary pointer */
866 : /* validity test. */
867 : # ifdef ENABLE_TRACE
868 : if (GC_trace_addr == current_p) {
869 : GC_log_printf("GC:%u Considering(2) %p -> %p\n",
870 : (unsigned)GC_gc_no, current_p, (ptr_t)deferred);
871 : }
872 : # endif /* ENABLE_TRACE */
873 505645 : PUSH_CONTENTS((ptr_t)deferred, mark_stack_top,
874 : mark_stack_limit, current_p, exit4);
875 : next_object:;
876 : # endif
877 : }
878 : }
879 77281 : return mark_stack_top;
880 : }
881 :
882 : #ifdef PARALLEL_MARK
883 :
884 : STATIC GC_bool GC_help_wanted = FALSE; /* Protected by mark lock */
885 : STATIC unsigned GC_helper_count = 0; /* Number of running helpers. */
886 : /* Protected by mark lock */
887 : STATIC unsigned GC_active_count = 0; /* Number of active helpers. */
888 : /* Protected by mark lock */
889 : /* May increase and decrease */
890 : /* within each mark cycle. But */
891 : /* once it returns to 0, it */
892 : /* stays zero for the cycle. */
893 :
894 : GC_INNER word GC_mark_no = 0;
895 :
896 : #define LOCAL_MARK_STACK_SIZE HBLKSIZE
897 : /* Under normal circumstances, this is big enough to guarantee */
898 : /* We don't overflow half of it in a single call to */
899 : /* GC_mark_from. */
900 :
901 :
902 : /* Steal mark stack entries starting at mse low into mark stack local */
903 : /* until we either steal mse high, or we have max entries. */
904 : /* Return a pointer to the top of the local mark stack. */
905 : /* *next is replaced by a pointer to the next unscanned mark stack */
906 : /* entry. */
907 : STATIC mse * GC_steal_mark_stack(mse * low, mse * high, mse * local,
908 : unsigned max, mse **next)
909 : {
910 : mse *p;
911 : mse *top = local - 1;
912 : unsigned i = 0;
913 :
914 : GC_ASSERT(high >= low-1 && (word)(high - low + 1) <= GC_mark_stack_size);
915 : for (p = low; p <= high && i <= max; ++p) {
916 : word descr = AO_load((volatile AO_t *) &(p -> mse_descr));
917 : if (descr != 0) {
918 : /* Must be ordered after read of descr: */
919 : AO_store_release_write((volatile AO_t *) &(p -> mse_descr), 0);
920 : /* More than one thread may get this entry, but that's only */
921 : /* a minor performance problem. */
922 : ++top;
923 : top -> mse_descr = descr;
924 : top -> mse_start = p -> mse_start;
925 : GC_ASSERT((top -> mse_descr & GC_DS_TAGS) != GC_DS_LENGTH ||
926 : top -> mse_descr < (word)GC_greatest_plausible_heap_addr
927 : - (word)GC_least_plausible_heap_addr);
928 : /* If this is a big object, count it as */
929 : /* size/256 + 1 objects. */
930 : ++i;
931 : if ((descr & GC_DS_TAGS) == GC_DS_LENGTH) i += (int)(descr >> 8);
932 : }
933 : }
934 : *next = p;
935 : return top;
936 : }
937 :
938 : /* Copy back a local mark stack. */
939 : /* low and high are inclusive bounds. */
940 : STATIC void GC_return_mark_stack(mse * low, mse * high)
941 : {
942 : mse * my_top;
943 : mse * my_start;
944 : size_t stack_size;
945 :
946 : if (high < low) return;
947 : stack_size = high - low + 1;
948 : GC_acquire_mark_lock();
949 : my_top = GC_mark_stack_top; /* Concurrent modification impossible. */
950 : my_start = my_top + 1;
951 : if (my_start - GC_mark_stack + stack_size > GC_mark_stack_size) {
952 : if (GC_print_stats) {
953 : GC_log_printf("No room to copy back mark stack\n");
954 : }
955 : GC_mark_state = MS_INVALID;
956 : GC_mark_stack_too_small = TRUE;
957 : /* We drop the local mark stack. We'll fix things later. */
958 : } else {
959 : BCOPY(low, my_start, stack_size * sizeof(mse));
960 : GC_ASSERT((mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top))
961 : == my_top);
962 : AO_store_release_write((volatile AO_t *)(&GC_mark_stack_top),
963 : (AO_t)(my_top + stack_size));
964 : /* Ensures visibility of previously written stack contents. */
965 : }
966 : GC_release_mark_lock();
967 : GC_notify_all_marker();
968 : }
969 :
970 : /* Mark from the local mark stack. */
971 : /* On return, the local mark stack is empty. */
972 : /* But this may be achieved by copying the */
973 : /* local mark stack back into the global one. */
974 : STATIC void GC_do_local_mark(mse *local_mark_stack, mse *local_top)
975 : {
976 : unsigned n;
977 : # define N_LOCAL_ITERS 1
978 :
979 : # ifdef GC_ASSERTIONS
980 : /* Make sure we don't hold mark lock. */
981 : GC_acquire_mark_lock();
982 : GC_release_mark_lock();
983 : # endif
984 : for (;;) {
985 : for (n = 0; n < N_LOCAL_ITERS; ++n) {
986 : local_top = GC_mark_from(local_top, local_mark_stack,
987 : local_mark_stack + LOCAL_MARK_STACK_SIZE);
988 : if (local_top < local_mark_stack) return;
989 : if ((word)(local_top - local_mark_stack)
990 : >= LOCAL_MARK_STACK_SIZE / 2) {
991 : GC_return_mark_stack(local_mark_stack, local_top);
992 : return;
993 : }
994 : }
995 : if ((mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top))
996 : < (mse *)AO_load(&GC_first_nonempty)
997 : && GC_active_count < GC_helper_count
998 : && local_top > local_mark_stack + 1) {
999 : /* Try to share the load, since the main stack is empty, */
1000 : /* and helper threads are waiting for a refill. */
1001 : /* The entries near the bottom of the stack are likely */
1002 : /* to require more work. Thus we return those, eventhough */
1003 : /* it's harder. */
1004 : mse * new_bottom = local_mark_stack
1005 : + (local_top - local_mark_stack)/2;
1006 : GC_ASSERT(new_bottom > local_mark_stack
1007 : && new_bottom < local_top);
1008 : GC_return_mark_stack(local_mark_stack, new_bottom - 1);
1009 : memmove(local_mark_stack, new_bottom,
1010 : (local_top - new_bottom + 1) * sizeof(mse));
1011 : local_top -= (new_bottom - local_mark_stack);
1012 : }
1013 : }
1014 : }
1015 :
1016 : #define ENTRIES_TO_GET 5
1017 :
1018 : GC_INNER long GC_markers = 2; /* Normally changed by thread-library- */
1019 : /* -specific code. */
1020 :
1021 : /* Mark using the local mark stack until the global mark stack is empty */
1022 : /* and there are no active workers. Update GC_first_nonempty to reflect */
1023 : /* progress. */
1024 : /* Caller does not hold mark lock. */
1025 : /* Caller has already incremented GC_helper_count. We decrement it, */
1026 : /* and maintain GC_active_count. */
1027 : STATIC void GC_mark_local(mse *local_mark_stack, int id)
1028 : {
1029 : mse * my_first_nonempty;
1030 :
1031 : GC_acquire_mark_lock();
1032 : GC_active_count++;
1033 : my_first_nonempty = (mse *)AO_load(&GC_first_nonempty);
1034 : GC_ASSERT((mse *)AO_load(&GC_first_nonempty) >= GC_mark_stack &&
1035 : (mse *)AO_load(&GC_first_nonempty) <=
1036 : (mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top)) + 1);
1037 : if (GC_print_stats == VERBOSE)
1038 : GC_log_printf("Starting mark helper %lu\n", (unsigned long)id);
1039 : GC_release_mark_lock();
1040 : for (;;) {
1041 : size_t n_on_stack;
1042 : unsigned n_to_get;
1043 : mse * my_top;
1044 : mse * local_top;
1045 : mse * global_first_nonempty = (mse *)AO_load(&GC_first_nonempty);
1046 :
1047 : GC_ASSERT(my_first_nonempty >= GC_mark_stack &&
1048 : my_first_nonempty <=
1049 : (mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top)) + 1);
1050 : GC_ASSERT(global_first_nonempty >= GC_mark_stack &&
1051 : global_first_nonempty <=
1052 : (mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top)) + 1);
1053 : if (my_first_nonempty < global_first_nonempty) {
1054 : my_first_nonempty = global_first_nonempty;
1055 : } else if (global_first_nonempty < my_first_nonempty) {
1056 : AO_compare_and_swap(&GC_first_nonempty,
1057 : (AO_t) global_first_nonempty,
1058 : (AO_t) my_first_nonempty);
1059 : /* If this fails, we just go ahead, without updating */
1060 : /* GC_first_nonempty. */
1061 : }
1062 : /* Perhaps we should also update GC_first_nonempty, if it */
1063 : /* is less. But that would require using atomic updates. */
1064 : my_top = (mse *)AO_load_acquire((volatile AO_t *)(&GC_mark_stack_top));
1065 : n_on_stack = my_top - my_first_nonempty + 1;
1066 : if (0 == n_on_stack) {
1067 : GC_acquire_mark_lock();
1068 : my_top = GC_mark_stack_top;
1069 : /* Asynchronous modification impossible here, */
1070 : /* since we hold mark lock. */
1071 : n_on_stack = my_top - my_first_nonempty + 1;
1072 : if (0 == n_on_stack) {
1073 : GC_active_count--;
1074 : GC_ASSERT(GC_active_count <= GC_helper_count);
1075 : /* Other markers may redeposit objects */
1076 : /* on the stack. */
1077 : if (0 == GC_active_count) GC_notify_all_marker();
1078 : while (GC_active_count > 0
1079 : && (mse *)AO_load(&GC_first_nonempty)
1080 : > GC_mark_stack_top) {
1081 : /* We will be notified if either GC_active_count */
1082 : /* reaches zero, or if more objects are pushed on */
1083 : /* the global mark stack. */
1084 : GC_wait_marker();
1085 : }
1086 : if (GC_active_count == 0 &&
1087 : (mse *)AO_load(&GC_first_nonempty) > GC_mark_stack_top) {
1088 : GC_bool need_to_notify = FALSE;
1089 : /* The above conditions can't be falsified while we */
1090 : /* hold the mark lock, since neither */
1091 : /* GC_active_count nor GC_mark_stack_top can */
1092 : /* change. GC_first_nonempty can only be */
1093 : /* incremented asynchronously. Thus we know that */
1094 : /* both conditions actually held simultaneously. */
1095 : GC_helper_count--;
1096 : if (0 == GC_helper_count) need_to_notify = TRUE;
1097 : if (GC_print_stats == VERBOSE)
1098 : GC_log_printf("Finished mark helper %lu\n",
1099 : (unsigned long)id);
1100 : GC_release_mark_lock();
1101 : if (need_to_notify) GC_notify_all_marker();
1102 : return;
1103 : }
1104 : /* else there's something on the stack again, or */
1105 : /* another helper may push something. */
1106 : GC_active_count++;
1107 : GC_ASSERT(GC_active_count > 0);
1108 : GC_release_mark_lock();
1109 : continue;
1110 : } else {
1111 : GC_release_mark_lock();
1112 : }
1113 : }
1114 : n_to_get = ENTRIES_TO_GET;
1115 : if (n_on_stack < 2 * ENTRIES_TO_GET) n_to_get = 1;
1116 : local_top = GC_steal_mark_stack(my_first_nonempty, my_top,
1117 : local_mark_stack, n_to_get,
1118 : &my_first_nonempty);
1119 : GC_ASSERT(my_first_nonempty >= GC_mark_stack &&
1120 : my_first_nonempty <=
1121 : (mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top)) + 1);
1122 : GC_do_local_mark(local_mark_stack, local_top);
1123 : }
1124 : }
1125 :
1126 : /* Perform Parallel mark. */
1127 : /* We hold the GC lock, not the mark lock. */
1128 : /* Currently runs until the mark stack is */
1129 : /* empty. */
1130 : STATIC void GC_do_parallel_mark(void)
1131 : {
1132 : mse local_mark_stack[LOCAL_MARK_STACK_SIZE];
1133 :
1134 : GC_acquire_mark_lock();
1135 : GC_ASSERT(I_HOLD_LOCK());
1136 : /* This could be a GC_ASSERT, but it seems safer to keep it on */
1137 : /* all the time, especially since it's cheap. */
1138 : if (GC_help_wanted || GC_active_count != 0 || GC_helper_count != 0)
1139 : ABORT("Tried to start parallel mark in bad state");
1140 : if (GC_print_stats == VERBOSE)
1141 : GC_log_printf("Starting marking for mark phase number %lu\n",
1142 : (unsigned long)GC_mark_no);
1143 : GC_first_nonempty = (AO_t)GC_mark_stack;
1144 : GC_active_count = 0;
1145 : GC_helper_count = 1;
1146 : GC_help_wanted = TRUE;
1147 : GC_release_mark_lock();
1148 : GC_notify_all_marker();
1149 : /* Wake up potential helpers. */
1150 : GC_mark_local(local_mark_stack, 0);
1151 : GC_acquire_mark_lock();
1152 : GC_help_wanted = FALSE;
1153 : /* Done; clean up. */
1154 : while (GC_helper_count > 0) GC_wait_marker();
1155 : /* GC_helper_count cannot be incremented while GC_help_wanted == FALSE */
1156 : if (GC_print_stats == VERBOSE)
1157 : GC_log_printf("Finished marking for mark phase number %lu\n",
1158 : (unsigned long)GC_mark_no);
1159 : GC_mark_no++;
1160 : GC_release_mark_lock();
1161 : GC_notify_all_marker();
1162 : }
1163 :
1164 :
1165 : /* Try to help out the marker, if it's running. */
1166 : /* We do not hold the GC lock, but the requestor does. */
1167 : GC_INNER void GC_help_marker(word my_mark_no)
1168 : {
1169 : mse local_mark_stack[LOCAL_MARK_STACK_SIZE];
1170 : unsigned my_id;
1171 :
1172 : if (!GC_parallel) return;
1173 : GC_acquire_mark_lock();
1174 : while (GC_mark_no < my_mark_no
1175 : || (!GC_help_wanted && GC_mark_no == my_mark_no)) {
1176 : GC_wait_marker();
1177 : }
1178 : my_id = GC_helper_count;
1179 : if (GC_mark_no != my_mark_no || my_id >= (unsigned)GC_markers) {
1180 : /* Second test is useful only if original threads can also */
1181 : /* act as helpers. Under Linux they can't. */
1182 : GC_release_mark_lock();
1183 : return;
1184 : }
1185 : GC_helper_count = my_id + 1;
1186 : GC_release_mark_lock();
1187 : GC_mark_local(local_mark_stack, my_id);
1188 : /* GC_mark_local decrements GC_helper_count. */
1189 : }
1190 :
1191 : #endif /* PARALLEL_MARK */
1192 :
1193 : /* Allocate or reallocate space for mark stack of size n entries. */
1194 : /* May silently fail. */
1195 169 : static void alloc_mark_stack(size_t n)
1196 : {
1197 169 : mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct GC_ms_entry));
1198 : # ifdef GWW_VDB
1199 : /* Don't recycle a stack segment obtained with the wrong flags. */
1200 : /* Win32 GetWriteWatch requires the right kind of memory. */
1201 : static GC_bool GC_incremental_at_stack_alloc = FALSE;
1202 : GC_bool recycle_old = (!GC_incremental || GC_incremental_at_stack_alloc);
1203 :
1204 : GC_incremental_at_stack_alloc = GC_incremental;
1205 : # else
1206 : # define recycle_old TRUE
1207 : # endif
1208 :
1209 169 : GC_mark_stack_too_small = FALSE;
1210 169 : if (GC_mark_stack_size != 0) {
1211 6 : if (new_stack != 0) {
1212 : if (recycle_old) {
1213 : /* Recycle old space */
1214 6 : size_t page_offset = (word)GC_mark_stack & (GC_page_size - 1);
1215 6 : size_t size = GC_mark_stack_size * sizeof(struct GC_ms_entry);
1216 6 : size_t displ = 0;
1217 :
1218 6 : if (0 != page_offset) displ = GC_page_size - page_offset;
1219 6 : size = (size - displ) & ~(GC_page_size - 1);
1220 6 : if (size > 0) {
1221 6 : GC_add_to_heap((struct hblk *)
1222 6 : ((word)GC_mark_stack + displ), (word)size);
1223 : }
1224 : }
1225 6 : GC_mark_stack = new_stack;
1226 6 : GC_mark_stack_size = n;
1227 6 : GC_mark_stack_limit = new_stack + n;
1228 6 : if (GC_print_stats) {
1229 0 : GC_log_printf("Grew mark stack to %lu frames\n",
1230 : (unsigned long) GC_mark_stack_size);
1231 : }
1232 : } else {
1233 0 : if (GC_print_stats) {
1234 0 : GC_log_printf("Failed to grow mark stack to %lu frames\n",
1235 : (unsigned long) n);
1236 : }
1237 : }
1238 : } else {
1239 163 : if (new_stack == 0) {
1240 0 : GC_err_printf("No space for mark stack\n");
1241 0 : EXIT();
1242 : }
1243 163 : GC_mark_stack = new_stack;
1244 163 : GC_mark_stack_size = n;
1245 163 : GC_mark_stack_limit = new_stack + n;
1246 : }
1247 169 : GC_mark_stack_top = GC_mark_stack-1;
1248 169 : }
1249 :
1250 163 : GC_INNER void GC_mark_init(void)
1251 : {
1252 163 : alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
1253 163 : }
1254 :
1255 : /*
1256 : * Push all locations between b and t onto the mark stack.
1257 : * b is the first location to be checked. t is one past the last
1258 : * location to be checked.
1259 : * Should only be used if there is no possibility of mark stack
1260 : * overflow.
1261 : */
1262 3779 : void GC_push_all(ptr_t bottom, ptr_t top)
1263 : {
1264 : register word length;
1265 :
1266 3779 : bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1267 3779 : top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
1268 3779 : if (bottom >= top) return;
1269 :
1270 3779 : GC_mark_stack_top++;
1271 3779 : if (GC_mark_stack_top >= GC_mark_stack_limit) {
1272 0 : ABORT("Unexpected mark stack overflow");
1273 : }
1274 3779 : length = top - bottom;
1275 : # if GC_DS_TAGS > ALIGNMENT - 1
1276 : length += GC_DS_TAGS;
1277 : length &= ~GC_DS_TAGS;
1278 : # endif
1279 3779 : GC_mark_stack_top -> mse_start = bottom;
1280 3779 : GC_mark_stack_top -> mse_descr = length;
1281 : }
1282 :
1283 : #ifndef GC_DISABLE_INCREMENTAL
1284 :
1285 : /* Analogous to the above, but push only those pages h with */
1286 : /* dirty_fn(h) != 0. We use GC_push_all to actually push the block. */
1287 : /* Used both to selectively push dirty pages, or to push a block in */
1288 : /* piecemeal fashion, to allow for more marking concurrency. */
1289 : /* Will not overflow mark stack if GC_push_all pushes a small fixed */
1290 : /* number of entries. (This is invoked only if GC_push_all pushes */
1291 : /* a single entry, or if it marks each object before pushing it, thus */
1292 : /* ensuring progress in the event of a stack overflow.) */
1293 0 : STATIC void GC_push_selected(ptr_t bottom, ptr_t top,
1294 : GC_bool (*dirty_fn)(struct hblk *))
1295 : {
1296 : struct hblk * h;
1297 :
1298 0 : bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1299 0 : top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
1300 0 : if (bottom >= top) return;
1301 :
1302 0 : h = HBLKPTR(bottom + HBLKSIZE);
1303 0 : if (top <= (ptr_t) h) {
1304 0 : if ((*dirty_fn)(h-1)) {
1305 0 : GC_push_all(bottom, top);
1306 : }
1307 0 : return;
1308 : }
1309 0 : if ((*dirty_fn)(h-1)) {
1310 0 : GC_push_all(bottom, (ptr_t)h);
1311 : }
1312 :
1313 0 : while ((ptr_t)(h+1) <= top) {
1314 0 : if ((*dirty_fn)(h)) {
1315 0 : if ((word)(GC_mark_stack_top - GC_mark_stack)
1316 0 : > 3 * GC_mark_stack_size / 4) {
1317 : /* Danger of mark stack overflow */
1318 0 : GC_push_all((ptr_t)h, top);
1319 0 : return;
1320 : } else {
1321 0 : GC_push_all((ptr_t)h, (ptr_t)(h+1));
1322 : }
1323 : }
1324 0 : h++;
1325 : }
1326 :
1327 0 : if ((ptr_t)h != top && (*dirty_fn)(h)) {
1328 0 : GC_push_all((ptr_t)h, top);
1329 : }
1330 0 : if (GC_mark_stack_top >= GC_mark_stack_limit) {
1331 0 : ABORT("Unexpected mark stack overflow");
1332 : }
1333 : }
1334 :
1335 3779 : void GC_push_conditional(ptr_t bottom, ptr_t top, GC_bool all)
1336 : {
1337 3779 : if (!all) {
1338 0 : GC_push_selected(bottom, top, GC_page_was_dirty);
1339 : } else {
1340 : # ifdef PROC_VDB
1341 : if (GC_dirty_maintained) {
1342 : /* Pages that were never dirtied cannot contain pointers. */
1343 : GC_push_selected(bottom, top, GC_page_was_ever_dirty);
1344 : } else
1345 : # endif
1346 : /* else */ {
1347 3779 : GC_push_all(bottom, top);
1348 : }
1349 : }
1350 3779 : }
1351 : #endif /* !GC_DISABLE_INCREMENTAL */
1352 :
1353 : #if defined(MSWIN32) || defined(MSWINCE)
1354 : void __cdecl GC_push_one(word p)
1355 : #else
1356 0 : void GC_push_one(word p)
1357 : #endif
1358 : {
1359 0 : GC_PUSH_ONE_STACK(p, MARKED_FROM_REGISTER);
1360 0 : }
1361 :
1362 : /*ARGSUSED*/
1363 254331 : GC_API struct GC_ms_entry * GC_CALL GC_mark_and_push(void *obj,
1364 : mse *mark_stack_ptr,
1365 : mse *mark_stack_limit,
1366 : void **src)
1367 : {
1368 : hdr * hhdr;
1369 :
1370 254331 : PREFETCH(obj);
1371 254331 : GET_HDR(obj, hhdr);
1372 254331 : if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr), FALSE)) {
1373 39291 : if (GC_all_interior_pointers) {
1374 0 : hhdr = GC_find_header(GC_base(obj));
1375 0 : if (hhdr == 0) {
1376 0 : GC_ADD_TO_BLACK_LIST_NORMAL(obj, (ptr_t)src);
1377 0 : return mark_stack_ptr;
1378 : }
1379 : } else {
1380 39291 : GC_ADD_TO_BLACK_LIST_NORMAL(obj, (ptr_t)src);
1381 39291 : return mark_stack_ptr;
1382 : }
1383 : }
1384 215040 : if (EXPECT(HBLK_IS_FREE(hhdr), FALSE)) {
1385 0 : GC_ADD_TO_BLACK_LIST_NORMAL(obj, (ptr_t)src);
1386 0 : return mark_stack_ptr;
1387 : }
1388 :
1389 215040 : PUSH_CONTENTS_HDR(obj, mark_stack_ptr /* modified */, mark_stack_limit,
1390 : (ptr_t)src, was_marked, hhdr, TRUE);
1391 : was_marked:
1392 215040 : return mark_stack_ptr;
1393 : }
1394 :
1395 : #if defined(MANUAL_VDB) && defined(THREADS)
1396 : void GC_dirty(ptr_t p);
1397 : #endif
1398 :
1399 : /* Mark and push (i.e. gray) a single object p onto the main */
1400 : /* mark stack. Consider p to be valid if it is an interior */
1401 : /* pointer. */
1402 : /* The object p has passed a preliminary pointer validity */
1403 : /* test, but we do not definitely know whether it is valid. */
1404 : /* Mark bits are NOT atomically updated. Thus this must be the */
1405 : /* only thread setting them. */
1406 : # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
1407 : GC_INNER void GC_mark_and_push_stack(ptr_t p, ptr_t source)
1408 : # else
1409 20445 : GC_INNER void GC_mark_and_push_stack(ptr_t p)
1410 : # define source ((ptr_t)0)
1411 : # endif
1412 : {
1413 : hdr * hhdr;
1414 20445 : ptr_t r = p;
1415 :
1416 20445 : PREFETCH(p);
1417 20445 : GET_HDR(p, hhdr);
1418 20445 : if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr), FALSE)) {
1419 5635 : if (hhdr != 0) {
1420 62 : r = GC_base(p);
1421 62 : hhdr = HDR(r);
1422 : }
1423 5635 : if (hhdr == 0) {
1424 5574 : GC_ADD_TO_BLACK_LIST_STACK(p, source);
1425 5574 : return;
1426 : }
1427 : }
1428 14871 : if (EXPECT(HBLK_IS_FREE(hhdr), FALSE)) {
1429 165 : GC_ADD_TO_BLACK_LIST_NORMAL(p, source);
1430 165 : return;
1431 : }
1432 : # if defined(MANUAL_VDB) && defined(THREADS)
1433 : /* Pointer is on the stack. We may have dirtied the object */
1434 : /* it points to, but not yet have called GC_dirty(); */
1435 : GC_dirty(p); /* Implicitly affects entire object. */
1436 : # endif
1437 14706 : PUSH_CONTENTS_HDR(r, GC_mark_stack_top, GC_mark_stack_limit,
1438 : source, mark_and_push_exit, hhdr, FALSE);
1439 : mark_and_push_exit: ;
1440 : /* We silently ignore pointers to near the end of a block, */
1441 : /* which is very mildly suboptimal. */
1442 : /* FIXME: We should probably add a header word to address */
1443 : /* this. */
1444 : }
1445 : # undef source
1446 :
1447 : # ifdef TRACE_BUF
1448 :
1449 : # define TRACE_ENTRIES 1000
1450 :
1451 : struct trace_entry {
1452 : char * kind;
1453 : word gc_no;
1454 : word bytes_allocd;
1455 : word arg1;
1456 : word arg2;
1457 : } GC_trace_buf[TRACE_ENTRIES];
1458 :
1459 : int GC_trace_buf_ptr = 0;
1460 :
1461 : void GC_add_trace_entry(char *kind, word arg1, word arg2)
1462 : {
1463 : GC_trace_buf[GC_trace_buf_ptr].kind = kind;
1464 : GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
1465 : GC_trace_buf[GC_trace_buf_ptr].bytes_allocd = GC_bytes_allocd;
1466 : GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
1467 : GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
1468 : GC_trace_buf_ptr++;
1469 : if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
1470 : }
1471 :
1472 : void GC_print_trace(word gc_no, GC_bool lock)
1473 : {
1474 : int i;
1475 : struct trace_entry *p;
1476 : DCL_LOCK_STATE;
1477 :
1478 : if (lock) LOCK();
1479 : for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
1480 : if (i < 0) i = TRACE_ENTRIES-1;
1481 : p = GC_trace_buf + i;
1482 : if (p -> gc_no < gc_no || p -> kind == 0) return;
1483 : printf("Trace:%s (gc:%u,bytes:%lu) 0x%X, 0x%X\n",
1484 : p -> kind, (unsigned)p -> gc_no,
1485 : (unsigned long)p -> bytes_allocd,
1486 : (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
1487 : }
1488 : printf("Trace incomplete\n");
1489 : if (lock) UNLOCK();
1490 : }
1491 :
1492 : # endif /* TRACE_BUF */
1493 :
1494 : /*
1495 : * A version of GC_push_all that treats all interior pointers as valid
1496 : * and scans the entire region immediately, in case the contents
1497 : * change.
1498 : */
1499 801 : GC_INNER void GC_push_all_eager(ptr_t bottom, ptr_t top)
1500 : {
1501 801 : word * b = (word *)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1502 801 : word * t = (word *)(((word) top) & ~(ALIGNMENT-1));
1503 : register word *p;
1504 : register word q;
1505 : register word *lim;
1506 801 : register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1507 801 : register ptr_t least_ha = GC_least_plausible_heap_addr;
1508 : # define GC_greatest_plausible_heap_addr greatest_ha
1509 : # define GC_least_plausible_heap_addr least_ha
1510 :
1511 801 : if (top == 0) return;
1512 : /* check all pointers in range and push if they appear */
1513 : /* to be valid. */
1514 801 : lim = t - 1 /* longword */;
1515 423948 : for (p = b; p <= lim; p = (word *)(((ptr_t)p) + ALIGNMENT)) {
1516 423147 : q = *p;
1517 423147 : GC_PUSH_ONE_STACK(q, p);
1518 : }
1519 : # undef GC_greatest_plausible_heap_addr
1520 : # undef GC_least_plausible_heap_addr
1521 : }
1522 :
1523 543 : GC_INNER void GC_push_all_stack(ptr_t bottom, ptr_t top)
1524 : {
1525 : # if defined(THREADS) && defined(MPROTECT_VDB)
1526 543 : GC_push_all_eager(bottom, top);
1527 : # else
1528 : if (!NEED_FIXUP_POINTER && GC_all_interior_pointers) {
1529 : GC_push_all(bottom, top);
1530 : } else {
1531 : GC_push_all_eager(bottom, top);
1532 : }
1533 : # endif
1534 543 : }
1535 :
1536 : #if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES) && \
1537 : defined(MARK_BIT_PER_GRANULE)
1538 : # if GC_GRANULE_WORDS == 1
1539 : # define USE_PUSH_MARKED_ACCELERATORS
1540 : # define PUSH_GRANULE(q) \
1541 : { word qcontents = (q)[0]; \
1542 : GC_PUSH_ONE_HEAP(qcontents, (q)); }
1543 : # elif GC_GRANULE_WORDS == 2
1544 : # define USE_PUSH_MARKED_ACCELERATORS
1545 : # define PUSH_GRANULE(q) \
1546 : { word qcontents = (q)[0]; \
1547 : GC_PUSH_ONE_HEAP(qcontents, (q)); \
1548 : qcontents = (q)[1]; \
1549 : GC_PUSH_ONE_HEAP(qcontents, (q)+1); }
1550 : # elif GC_GRANULE_WORDS == 4
1551 : # define USE_PUSH_MARKED_ACCELERATORS
1552 : # define PUSH_GRANULE(q) \
1553 : { word qcontents = (q)[0]; \
1554 : GC_PUSH_ONE_HEAP(qcontents, (q)); \
1555 : qcontents = (q)[1]; \
1556 : GC_PUSH_ONE_HEAP(qcontents, (q)+1); \
1557 : qcontents = (q)[2]; \
1558 : GC_PUSH_ONE_HEAP(qcontents, (q)+2); \
1559 : qcontents = (q)[3]; \
1560 : GC_PUSH_ONE_HEAP(qcontents, (q)+3); }
1561 : # endif
1562 : #endif /* !USE_MARK_BYTES && MARK_BIT_PER_GRANULE */
1563 :
1564 : #ifdef USE_PUSH_MARKED_ACCELERATORS
1565 : /* Push all objects reachable from marked objects in the given block */
1566 : /* containing objects of size 1 granule. */
1567 152 : STATIC void GC_push_marked1(struct hblk *h, hdr *hhdr)
1568 : {
1569 152 : word * mark_word_addr = &(hhdr->hb_marks[0]);
1570 : word *p;
1571 : word *plim;
1572 : word *q;
1573 : word mark_word;
1574 :
1575 : /* Allow registers to be used for some frequently acccessed */
1576 : /* global variables. Otherwise aliasing issues are likely */
1577 : /* to prevent that. */
1578 152 : ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1579 152 : ptr_t least_ha = GC_least_plausible_heap_addr;
1580 152 : mse * mark_stack_top = GC_mark_stack_top;
1581 152 : mse * mark_stack_limit = GC_mark_stack_limit;
1582 : # define GC_mark_stack_top mark_stack_top
1583 : # define GC_mark_stack_limit mark_stack_limit
1584 : # define GC_greatest_plausible_heap_addr greatest_ha
1585 : # define GC_least_plausible_heap_addr least_ha
1586 :
1587 152 : p = (word *)(h->hb_body);
1588 152 : plim = (word *)(((word)h) + HBLKSIZE);
1589 :
1590 : /* go through all words in block */
1591 912 : while (p < plim) {
1592 608 : mark_word = *mark_word_addr++;
1593 608 : q = p;
1594 31911 : while(mark_word != 0) {
1595 30695 : if (mark_word & 1) {
1596 28885 : PUSH_GRANULE(q);
1597 : }
1598 30695 : q += GC_GRANULE_WORDS;
1599 30695 : mark_word >>= 1;
1600 : }
1601 608 : p += WORDSZ*GC_GRANULE_WORDS;
1602 : }
1603 :
1604 : # undef GC_greatest_plausible_heap_addr
1605 : # undef GC_least_plausible_heap_addr
1606 : # undef GC_mark_stack_top
1607 : # undef GC_mark_stack_limit
1608 :
1609 152 : GC_mark_stack_top = mark_stack_top;
1610 152 : }
1611 :
1612 :
1613 : #ifndef UNALIGNED_PTRS
1614 :
1615 : /* Push all objects reachable from marked objects in the given block */
1616 : /* of size 2 (granules) objects. */
1617 173 : STATIC void GC_push_marked2(struct hblk *h, hdr *hhdr)
1618 : {
1619 173 : word * mark_word_addr = &(hhdr->hb_marks[0]);
1620 : word *p;
1621 : word *plim;
1622 : word *q;
1623 : word mark_word;
1624 :
1625 173 : ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1626 173 : ptr_t least_ha = GC_least_plausible_heap_addr;
1627 173 : mse * mark_stack_top = GC_mark_stack_top;
1628 173 : mse * mark_stack_limit = GC_mark_stack_limit;
1629 :
1630 : # define GC_mark_stack_top mark_stack_top
1631 : # define GC_mark_stack_limit mark_stack_limit
1632 : # define GC_greatest_plausible_heap_addr greatest_ha
1633 : # define GC_least_plausible_heap_addr least_ha
1634 :
1635 173 : p = (word *)(h->hb_body);
1636 173 : plim = (word *)(((word)h) + HBLKSIZE);
1637 :
1638 : /* go through all words in block */
1639 1038 : while (p < plim) {
1640 692 : mark_word = *mark_word_addr++;
1641 692 : q = p;
1642 19666 : while(mark_word != 0) {
1643 18282 : if (mark_word & 1) {
1644 4063 : PUSH_GRANULE(q);
1645 4063 : PUSH_GRANULE(q + GC_GRANULE_WORDS);
1646 : }
1647 18282 : q += 2 * GC_GRANULE_WORDS;
1648 18282 : mark_word >>= 2;
1649 : }
1650 692 : p += WORDSZ*GC_GRANULE_WORDS;
1651 : }
1652 :
1653 : # undef GC_greatest_plausible_heap_addr
1654 : # undef GC_least_plausible_heap_addr
1655 : # undef GC_mark_stack_top
1656 : # undef GC_mark_stack_limit
1657 :
1658 173 : GC_mark_stack_top = mark_stack_top;
1659 173 : }
1660 :
1661 : # if GC_GRANULE_WORDS < 4
1662 : /* Push all objects reachable from marked objects in the given block */
1663 : /* of size 4 (granules) objects. */
1664 : /* There is a risk of mark stack overflow here. But we handle that. */
1665 : /* And only unmarked objects get pushed, so it's not very likely. */
1666 610 : STATIC void GC_push_marked4(struct hblk *h, hdr *hhdr)
1667 : {
1668 610 : word * mark_word_addr = &(hhdr->hb_marks[0]);
1669 : word *p;
1670 : word *plim;
1671 : word *q;
1672 : word mark_word;
1673 :
1674 610 : ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1675 610 : ptr_t least_ha = GC_least_plausible_heap_addr;
1676 610 : mse * mark_stack_top = GC_mark_stack_top;
1677 610 : mse * mark_stack_limit = GC_mark_stack_limit;
1678 : # define GC_mark_stack_top mark_stack_top
1679 : # define GC_mark_stack_limit mark_stack_limit
1680 : # define GC_greatest_plausible_heap_addr greatest_ha
1681 : # define GC_least_plausible_heap_addr least_ha
1682 :
1683 610 : p = (word *)(h->hb_body);
1684 610 : plim = (word *)(((word)h) + HBLKSIZE);
1685 :
1686 : /* go through all words in block */
1687 3660 : while (p < plim) {
1688 2440 : mark_word = *mark_word_addr++;
1689 2440 : q = p;
1690 42870 : while(mark_word != 0) {
1691 37990 : if (mark_word & 1) {
1692 36828 : PUSH_GRANULE(q);
1693 36828 : PUSH_GRANULE(q + GC_GRANULE_WORDS);
1694 36828 : PUSH_GRANULE(q + 2*GC_GRANULE_WORDS);
1695 36828 : PUSH_GRANULE(q + 3*GC_GRANULE_WORDS);
1696 : }
1697 37990 : q += 4 * GC_GRANULE_WORDS;
1698 37990 : mark_word >>= 4;
1699 : }
1700 2440 : p += WORDSZ*GC_GRANULE_WORDS;
1701 : }
1702 : # undef GC_greatest_plausible_heap_addr
1703 : # undef GC_least_plausible_heap_addr
1704 : # undef GC_mark_stack_top
1705 : # undef GC_mark_stack_limit
1706 610 : GC_mark_stack_top = mark_stack_top;
1707 610 : }
1708 :
1709 : #endif /* GC_GRANULE_WORDS < 4 */
1710 :
1711 : #endif /* UNALIGNED_PTRS */
1712 :
1713 : #endif /* USE_PUSH_MARKED_ACCELERATORS */
1714 :
1715 : /* Push all objects reachable from marked objects in the given block */
1716 9062 : STATIC void GC_push_marked(struct hblk *h, hdr *hhdr)
1717 : {
1718 9062 : size_t sz = hhdr -> hb_sz;
1719 9062 : word descr = hhdr -> hb_descr;
1720 : ptr_t p;
1721 : word bit_no;
1722 : ptr_t lim;
1723 : mse * GC_mark_stack_top_reg;
1724 9062 : mse * mark_stack_limit = GC_mark_stack_limit;
1725 :
1726 : /* Some quick shortcuts: */
1727 9062 : if ((0 | GC_DS_LENGTH) == descr) return;
1728 7482 : if (GC_block_empty(hhdr)/* nothing marked */) return;
1729 6992 : GC_n_rescuing_pages++;
1730 6992 : GC_objects_are_marked = TRUE;
1731 6992 : if (sz > MAXOBJBYTES) {
1732 53 : lim = h -> hb_body;
1733 : } else {
1734 6939 : lim = (h + 1)->hb_body - sz;
1735 : }
1736 :
1737 6992 : switch(BYTES_TO_GRANULES(sz)) {
1738 : # if defined(USE_PUSH_MARKED_ACCELERATORS)
1739 : case 1:
1740 152 : GC_push_marked1(h, hhdr);
1741 152 : break;
1742 : # if !defined(UNALIGNED_PTRS)
1743 : case 2:
1744 173 : GC_push_marked2(h, hhdr);
1745 173 : break;
1746 : # if GC_GRANULE_WORDS < 4
1747 : case 4:
1748 610 : GC_push_marked4(h, hhdr);
1749 610 : break;
1750 : # endif
1751 : # endif
1752 : # endif
1753 : default:
1754 6057 : GC_mark_stack_top_reg = GC_mark_stack_top;
1755 160706 : for (p = h -> hb_body, bit_no = 0; p <= lim;
1756 148592 : p += sz, bit_no += MARK_BIT_OFFSET(sz)) {
1757 148592 : if (mark_bit_from_hdr(hhdr, bit_no)) {
1758 : /* Mark from fields inside the object */
1759 138717 : PUSH_OBJ(p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
1760 : }
1761 : }
1762 6057 : GC_mark_stack_top = GC_mark_stack_top_reg;
1763 : }
1764 : }
1765 :
1766 : #ifndef GC_DISABLE_INCREMENTAL
1767 : /* Test whether any page in the given block is dirty. */
1768 0 : STATIC GC_bool GC_block_was_dirty(struct hblk *h, hdr *hhdr)
1769 : {
1770 0 : size_t sz = hhdr -> hb_sz;
1771 :
1772 0 : if (sz <= MAXOBJBYTES) {
1773 0 : return(GC_page_was_dirty(h));
1774 : } else {
1775 0 : ptr_t p = (ptr_t)h;
1776 0 : while (p < (ptr_t)h + sz) {
1777 0 : if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
1778 0 : p += HBLKSIZE;
1779 : }
1780 0 : return(FALSE);
1781 : }
1782 : }
1783 : #endif /* GC_DISABLE_INCREMENTAL */
1784 :
1785 : /* Similar to GC_push_marked, but skip over unallocated blocks */
1786 : /* and return address of next plausible block. */
1787 4857 : STATIC struct hblk * GC_push_next_marked(struct hblk *h)
1788 : {
1789 4857 : hdr * hhdr = HDR(h);
1790 :
1791 4857 : if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr) || HBLK_IS_FREE(hhdr), FALSE)) {
1792 31 : h = GC_next_used_block(h);
1793 31 : if (h == 0) return(0);
1794 25 : hhdr = GC_find_header((ptr_t)h);
1795 : }
1796 4851 : GC_push_marked(h, hhdr);
1797 4851 : return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1798 : }
1799 :
1800 : #ifndef GC_DISABLE_INCREMENTAL
1801 : /* Identical to above, but mark only from dirty pages */
1802 0 : STATIC struct hblk * GC_push_next_marked_dirty(struct hblk *h)
1803 : {
1804 0 : hdr * hhdr = HDR(h);
1805 :
1806 0 : if (!GC_dirty_maintained) ABORT("Dirty bits not set up");
1807 : for (;;) {
1808 0 : if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr)
1809 : || HBLK_IS_FREE(hhdr), FALSE)) {
1810 0 : h = GC_next_used_block(h);
1811 0 : if (h == 0) return(0);
1812 0 : hhdr = GC_find_header((ptr_t)h);
1813 : }
1814 : # ifdef STUBBORN_ALLOC
1815 : if (hhdr -> hb_obj_kind == STUBBORN) {
1816 : if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
1817 : break;
1818 : }
1819 : } else {
1820 : if (GC_block_was_dirty(h, hhdr)) break;
1821 : }
1822 : # else
1823 0 : if (GC_block_was_dirty(h, hhdr)) break;
1824 : # endif
1825 0 : h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1826 0 : hhdr = HDR(h);
1827 0 : }
1828 0 : GC_push_marked(h, hhdr);
1829 0 : return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1830 : }
1831 : #endif /* !GC_DISABLE_INCREMENTAL */
1832 :
1833 : /* Similar to above, but for uncollectable pages. Needed since we */
1834 : /* do not clear marks for such pages, even for full collections. */
1835 4463 : STATIC struct hblk * GC_push_next_marked_uncollectable(struct hblk *h)
1836 : {
1837 4463 : hdr * hhdr = HDR(h);
1838 :
1839 : for (;;) {
1840 76651 : if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr)
1841 : || HBLK_IS_FREE(hhdr), FALSE)) {
1842 1084 : h = GC_next_used_block(h);
1843 1084 : if (h == 0) return(0);
1844 832 : hhdr = GC_find_header((ptr_t)h);
1845 : }
1846 76399 : if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
1847 72188 : h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1848 72188 : hhdr = HDR(h);
1849 72188 : }
1850 4211 : GC_push_marked(h, hhdr);
1851 4211 : return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1852 : }
|
