Debian Codegraph @

gc/mark.c

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