mark_rts.c raw
1 /*
2 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
3 * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
4 * Copyright (c) 2009-2022 Ivan Maidanski
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 #include "private/gc_priv.h"
17
18 #if defined(E2K) && !defined(THREADS)
19 # include <alloca.h>
20 #endif
21
22 /*
23 * Data structure for list of root sets.
24 * We keep a hash table, so that we can filter out duplicate additions.
25 * Under Win32, we need to do a better job of filtering overlaps, so
26 * we resort to sequential search, and pay the price.
27 */
28
29 /* Register dynamic library data segments. */
30 int GC_no_dls = 0;
31
32 #if !defined(NO_DEBUGGING) || defined(GC_ASSERTIONS)
33 GC_INNER word
34 GC_compute_root_size(void)
35 {
36 size_t i;
37 word size = 0;
38
39 for (i = 0; i < n_root_sets; i++) {
40 size += (word)(GC_static_roots[i].r_end - GC_static_roots[i].r_start);
41 }
42 return size;
43 }
44 #endif /* !NO_DEBUGGING || GC_ASSERTIONS */
45
46 #if !defined(NO_DEBUGGING)
47 /* For the debugging purpose. */
48 void
49 GC_print_static_roots(void)
50 {
51 size_t i;
52 word size;
53
54 for (i = 0; i < n_root_sets; i++) {
55 GC_printf("From %p to %p%s\n", (void *)GC_static_roots[i].r_start,
56 (void *)GC_static_roots[i].r_end,
57 GC_static_roots[i].r_tmp ? " (temporary)" : "");
58 }
59 GC_printf("GC_root_size= %lu\n", (unsigned long)GC_root_size);
60
61 if ((size = GC_compute_root_size()) != GC_root_size)
62 GC_err_printf("GC_root_size incorrect!! Should be: %lu\n",
63 (unsigned long)size);
64 }
65 #endif /* !NO_DEBUGGING */
66
67 #ifndef ANY_MSWIN
68 GC_INLINE size_t
69 rt_hash(ptr_t addr)
70 {
71 word val = ADDR(addr);
72
73 # if CPP_WORDSZ > 4 * LOG_RT_SIZE
74 # if CPP_WORDSZ > 8 * LOG_RT_SIZE
75 val ^= val >> (8 * LOG_RT_SIZE);
76 # endif
77 val ^= val >> (4 * LOG_RT_SIZE);
78 # endif
79 val ^= val >> (2 * LOG_RT_SIZE);
80 return (size_t)((val >> LOG_RT_SIZE) ^ val) & (RT_SIZE - 1);
81 }
82
83 GC_INNER void *
84 GC_roots_present(ptr_t b)
85 {
86 size_t h;
87 struct roots *p;
88
89 GC_ASSERT(I_HOLD_READER_LOCK());
90 h = rt_hash(b);
91 for (p = GC_root_index[h]; p != NULL; p = p->r_next) {
92 if (p->r_start == (ptr_t)b)
93 break;
94 }
95 return p;
96 }
97
98 /* Add the given root structure to the index. */
99 GC_INLINE void
100 add_roots_to_index(struct roots *p)
101 {
102 size_t h = rt_hash(p->r_start);
103
104 p->r_next = GC_root_index[h];
105 GC_root_index[h] = p;
106 }
107 #endif /* !ANY_MSWIN */
108
109 GC_INNER word GC_root_size = 0;
110
111 GC_API void GC_CALL
112 GC_add_roots(void *b, void *e)
113 {
114 if (UNLIKELY(!GC_is_initialized))
115 GC_init();
116 LOCK();
117 GC_add_roots_inner((ptr_t)b, (ptr_t)e, FALSE);
118 UNLOCK();
119 }
120
121 GC_INNER void
122 GC_add_roots_inner(ptr_t b, ptr_t e, GC_bool tmp)
123 {
124 GC_ASSERT(I_HOLD_LOCK());
125 GC_ASSERT(ADDR_GE(e, b));
126 b = PTR_ALIGN_UP(b, ALIGNMENT);
127 e = PTR_ALIGN_DOWN(e, ALIGNMENT);
128 if (ADDR_GE(b, e)) {
129 /* Nothing to do. */
130 return;
131 }
132
133 #ifdef ANY_MSWIN
134 /*
135 * Spend the time to ensure that there are no overlapping or adjacent
136 * intervals. This could be done faster with e.g. a balanced tree.
137 * But the execution time here is virtually guaranteed to be dominated
138 * by the time it takes to scan the roots.
139 */
140 {
141 size_t i;
142 struct roots *old = NULL; /*< initialized to prevent warning */
143
144 for (i = 0; i < n_root_sets; i++) {
145 old = GC_static_roots + i;
146 if (ADDR_GE(old->r_end, b) && ADDR_GE(e, old->r_start)) {
147 if (ADDR_LT(b, old->r_start)) {
148 GC_root_size += (word)(old->r_start - b);
149 old->r_start = b;
150 }
151 if (ADDR_LT(old->r_end, e)) {
152 GC_root_size += (word)(e - old->r_end);
153 old->r_end = e;
154 }
155 old->r_tmp &= tmp;
156 break;
157 }
158 }
159 if (i < n_root_sets) {
160 /* Merge other overlapping intervals. */
161 struct roots *other;
162
163 for (i++; i < n_root_sets; i++) {
164 other = GC_static_roots + i;
165 b = other->r_start;
166 e = other->r_end;
167 if (ADDR_GE(old->r_end, b) && ADDR_GE(e, old->r_start)) {
168 if (ADDR_LT(b, old->r_start)) {
169 GC_root_size += (word)(old->r_start - b);
170 old->r_start = b;
171 }
172 if (ADDR_LT(old->r_end, e)) {
173 GC_root_size += (word)(e - old->r_end);
174 old->r_end = e;
175 }
176 old->r_tmp &= other->r_tmp;
177 /* Delete this entry. */
178 GC_root_size -= (word)(other->r_end - other->r_start);
179 other->r_start = GC_static_roots[n_root_sets - 1].r_start;
180 other->r_end = GC_static_roots[n_root_sets - 1].r_end;
181 n_root_sets--;
182 }
183 }
184 return;
185 }
186 }
187 #else
188 {
189 struct roots *old = (struct roots *)GC_roots_present(b);
190
191 if (old != NULL) {
192 if (ADDR_GE(old->r_end, e)) {
193 old->r_tmp &= tmp;
194 /* Already there. */
195 return;
196 }
197 if (old->r_tmp == tmp || !tmp) {
198 /* Extend the existing root. */
199 GC_root_size += (word)(e - old->r_end);
200 old->r_end = e;
201 old->r_tmp = tmp;
202 return;
203 }
204 b = old->r_end;
205 }
206 }
207 #endif
208 if (n_root_sets == MAX_ROOT_SETS) {
209 ABORT("Too many root sets");
210 }
211
212 #ifdef DEBUG_ADD_DEL_ROOTS
213 GC_log_printf("Adding data root section %u: %p .. %p%s\n",
214 (unsigned)n_root_sets, (void *)b, (void *)e,
215 tmp ? " (temporary)" : "");
216 #endif
217 GC_static_roots[n_root_sets].r_start = (ptr_t)b;
218 GC_static_roots[n_root_sets].r_end = (ptr_t)e;
219 GC_static_roots[n_root_sets].r_tmp = tmp;
220 #ifndef ANY_MSWIN
221 GC_static_roots[n_root_sets].r_next = 0;
222 add_roots_to_index(GC_static_roots + n_root_sets);
223 #endif
224 GC_root_size += (word)(e - b);
225 n_root_sets++;
226 }
227
228 GC_API void GC_CALL
229 GC_clear_roots(void)
230 {
231 if (UNLIKELY(!GC_is_initialized))
232 GC_init();
233 LOCK();
234 #ifdef THREADS
235 GC_roots_were_cleared = TRUE;
236 #endif
237 n_root_sets = 0;
238 GC_root_size = 0;
239 #ifndef ANY_MSWIN
240 BZERO(GC_root_index, sizeof(GC_root_index));
241 #endif
242 #ifdef DEBUG_ADD_DEL_ROOTS
243 GC_log_printf("Clear all data root sections\n");
244 #endif
245 UNLOCK();
246 }
247
248 STATIC void
249 GC_remove_root_at_pos(size_t i)
250 {
251 GC_ASSERT(I_HOLD_LOCK());
252 GC_ASSERT(i < n_root_sets);
253 #ifdef DEBUG_ADD_DEL_ROOTS
254 GC_log_printf("Remove data root section at %u: %p .. %p%s\n", (unsigned)i,
255 (void *)GC_static_roots[i].r_start,
256 (void *)GC_static_roots[i].r_end,
257 GC_static_roots[i].r_tmp ? " (temporary)" : "");
258 #endif
259 GC_root_size
260 -= (word)(GC_static_roots[i].r_end - GC_static_roots[i].r_start);
261 GC_static_roots[i].r_start = GC_static_roots[n_root_sets - 1].r_start;
262 GC_static_roots[i].r_end = GC_static_roots[n_root_sets - 1].r_end;
263 GC_static_roots[i].r_tmp = GC_static_roots[n_root_sets - 1].r_tmp;
264 n_root_sets--;
265 }
266
267 #ifndef ANY_MSWIN
268 STATIC void
269 GC_rebuild_root_index(void)
270 {
271 size_t i;
272
273 BZERO(GC_root_index, sizeof(GC_root_index));
274 for (i = 0; i < n_root_sets; i++)
275 add_roots_to_index(GC_static_roots + i);
276 }
277 #endif /* !ANY_MSWIN */
278
279 #if defined(ANY_MSWIN) || defined(DYNAMIC_LOADING)
280 STATIC void
281 GC_remove_tmp_roots(void)
282 {
283 size_t i;
284 # ifndef ANY_MSWIN
285 size_t old_n_roots = n_root_sets;
286 # endif
287
288 GC_ASSERT(I_HOLD_LOCK());
289 for (i = 0; i < n_root_sets;) {
290 if (GC_static_roots[i].r_tmp) {
291 GC_remove_root_at_pos(i);
292 } else {
293 i++;
294 }
295 }
296 # ifndef ANY_MSWIN
297 if (n_root_sets < old_n_roots)
298 GC_rebuild_root_index();
299 # endif
300 }
301 #endif /* ANY_MSWIN || DYNAMIC_LOADING */
302
303 STATIC void GC_remove_roots_inner(ptr_t b, ptr_t e);
304
305 GC_API void GC_CALL
306 GC_remove_roots(void *b, void *e)
307 {
308 /* A quick check whether has nothing to do. */
309 if (ADDR_GE(PTR_ALIGN_UP((ptr_t)b, ALIGNMENT),
310 PTR_ALIGN_DOWN((ptr_t)e, ALIGNMENT)))
311 return;
312
313 LOCK();
314 GC_remove_roots_inner((ptr_t)b, (ptr_t)e);
315 UNLOCK();
316 }
317
318 STATIC void
319 GC_remove_roots_inner(ptr_t b, ptr_t e)
320 {
321 size_t i;
322 #ifndef ANY_MSWIN
323 size_t old_n_roots = n_root_sets;
324 #endif
325
326 GC_ASSERT(I_HOLD_LOCK());
327 for (i = 0; i < n_root_sets;) {
328 if (ADDR_GE(GC_static_roots[i].r_start, b)
329 && ADDR_GE(e, GC_static_roots[i].r_end)) {
330 GC_remove_root_at_pos(i);
331 } else {
332 i++;
333 }
334 }
335 #ifndef ANY_MSWIN
336 if (n_root_sets < old_n_roots)
337 GC_rebuild_root_index();
338 #endif
339 }
340
341 #ifdef USE_PROC_FOR_LIBRARIES
342 /*
343 * Exchange the elements of the roots table. Requires rebuild of the roots
344 * index table after the swap.
345 */
346 GC_INLINE void
347 swap_static_roots(size_t i, size_t j)
348 {
349 ptr_t r_start = GC_static_roots[i].r_start;
350 ptr_t r_end = GC_static_roots[i].r_end;
351 GC_bool r_tmp = GC_static_roots[i].r_tmp;
352
353 GC_static_roots[i].r_start = GC_static_roots[j].r_start;
354 GC_static_roots[i].r_end = GC_static_roots[j].r_end;
355 GC_static_roots[i].r_tmp = GC_static_roots[j].r_tmp;
356 /* No need to swap `r_next` values. */
357 GC_static_roots[j].r_start = r_start;
358 GC_static_roots[j].r_end = r_end;
359 GC_static_roots[j].r_tmp = r_tmp;
360 }
361
362 GC_INNER void
363 GC_remove_roots_subregion(ptr_t b, ptr_t e)
364 {
365 size_t i;
366 GC_bool rebuild = FALSE;
367
368 GC_ASSERT(I_HOLD_LOCK());
369 GC_ASSERT(ADDR(b) % ALIGNMENT == 0 && ADDR(e) % ALIGNMENT == 0);
370 for (i = 0; i < n_root_sets; i++) {
371 ptr_t r_start, r_end;
372
373 if (GC_static_roots[i].r_tmp) {
374 /* The remaining roots are skipped as they are all temporary. */
375 # ifdef GC_ASSERTIONS
376 size_t j;
377
378 for (j = i + 1; j < n_root_sets; j++) {
379 GC_ASSERT(GC_static_roots[j].r_tmp);
380 }
381 # endif
382 break;
383 }
384 r_start = GC_static_roots[i].r_start;
385 r_end = GC_static_roots[i].r_end;
386 if (ADDR_GE(r_start, e) || LIKELY(ADDR_GE(b, r_end)))
387 continue;
388
389 # ifdef DEBUG_ADD_DEL_ROOTS
390 GC_log_printf("Removing %p .. %p from root section %u (%p .. %p)\n",
391 (void *)b, (void *)e, (unsigned)i, (void *)r_start,
392 (void *)r_end);
393 # endif
394 if (ADDR_LT(r_start, b)) {
395 GC_root_size -= (word)(r_end - b);
396 GC_static_roots[i].r_end = b;
397 /* No need to rebuild as hash does not use `r_end` value. */
398 if (ADDR_LT(e, r_end)) {
399 size_t j;
400
401 if (rebuild) {
402 GC_rebuild_root_index();
403 rebuild = FALSE;
404 }
405 /* Note: updates `n_root_sets` as well. */
406 GC_add_roots_inner(e, r_end, FALSE);
407 for (j = i + 1; j < n_root_sets; j++)
408 if (GC_static_roots[j].r_tmp)
409 break;
410 if (j < n_root_sets - 1 && !GC_static_roots[n_root_sets - 1].r_tmp) {
411 /* Exchange the roots to have all temporary ones at the end. */
412 swap_static_roots(j, n_root_sets - 1);
413 rebuild = TRUE;
414 }
415 }
416 } else {
417 if (ADDR_LT(e, r_end)) {
418 GC_root_size -= (word)(e - r_start);
419 GC_static_roots[i].r_start = e;
420 } else {
421 GC_remove_root_at_pos(i);
422 if (i + 1 < n_root_sets && GC_static_roots[i].r_tmp
423 && !GC_static_roots[i + 1].r_tmp) {
424 size_t j;
425
426 for (j = i + 2; j < n_root_sets; j++)
427 if (GC_static_roots[j].r_tmp)
428 break;
429 /* Exchange the roots to have all temporary ones at the end. */
430 swap_static_roots(i, j - 1);
431 }
432 i--;
433 }
434 rebuild = TRUE;
435 }
436 }
437 if (rebuild)
438 GC_rebuild_root_index();
439 }
440 #endif /* USE_PROC_FOR_LIBRARIES */
441
442 #if !defined(NO_DEBUGGING)
443 GC_API int GC_CALL
444 GC_is_tmp_root(void *p)
445 {
446 # ifndef HAS_REAL_READER_LOCK
447 static size_t last_root_set; /*< initialized to 0; no shared access */
448 # elif defined(AO_HAVE_load) || defined(AO_HAVE_store)
449 static volatile AO_t last_root_set;
450 # else
451 /* Note: a race is acceptable, it is just a cached index. */
452 static volatile size_t last_root_set;
453 # endif
454 size_t i;
455 int res;
456
457 READER_LOCK();
458 /* First try the cached root. */
459 # if defined(AO_HAVE_load) && defined(HAS_REAL_READER_LOCK)
460 i = AO_load(&last_root_set);
461 # else
462 i = last_root_set;
463 # endif
464 if (i < n_root_sets
465 && ADDR_INSIDE((ptr_t)p, GC_static_roots[i].r_start,
466 GC_static_roots[i].r_end)) {
467 res = (int)GC_static_roots[i].r_tmp;
468 } else {
469 res = 0;
470 for (i = 0; i < n_root_sets; i++) {
471 if (ADDR_INSIDE((ptr_t)p, GC_static_roots[i].r_start,
472 GC_static_roots[i].r_end)) {
473 res = (int)GC_static_roots[i].r_tmp;
474 # if defined(AO_HAVE_store) && defined(HAS_REAL_READER_LOCK)
475 AO_store(&last_root_set, i);
476 # else
477 last_root_set = i;
478 # endif
479 break;
480 }
481 }
482 }
483 READER_UNLOCK();
484 return res;
485 }
486 #endif /* !NO_DEBUGGING */
487
488 GC_INNER ptr_t
489 GC_approx_sp(void)
490 {
491 volatile ptr_t sp;
492
493 /*
494 * This also forces stack to grow if necessary. Otherwise the later
495 * accesses might cause the kernel to think we are doing something wrong.
496 */
497 STORE_APPROX_SP_TO(sp);
498 return (/* no volatile */ ptr_t)sp;
499 }
500
501 GC_API void GC_CALL
502 GC_clear_exclusion_table(void)
503 {
504 #ifdef DEBUG_ADD_DEL_ROOTS
505 GC_log_printf("Clear static root exclusions (%u elements)\n",
506 (unsigned)GC_excl_table_entries);
507 #endif
508 GC_excl_table_entries = 0;
509 }
510
511 /*
512 * Return the first exclusion range that includes an address not lower
513 * than `start_addr`.
514 */
515 STATIC struct exclusion *
516 GC_next_exclusion(ptr_t start_addr)
517 {
518 size_t low = 0;
519 size_t high;
520
521 if (UNLIKELY(0 == GC_excl_table_entries))
522 return NULL;
523 high = GC_excl_table_entries - 1;
524 while (high > low) {
525 size_t mid = (low + high) >> 1;
526
527 /* `low` <= `mid` < `high`. */
528 if (ADDR_GE(start_addr, GC_excl_table[mid].e_end)) {
529 low = mid + 1;
530 } else {
531 high = mid;
532 }
533 }
534 if (ADDR_GE(start_addr, GC_excl_table[low].e_end))
535 return NULL;
536
537 return GC_excl_table + low;
538 }
539
540 GC_INNER void
541 GC_exclude_static_roots_inner(ptr_t start, ptr_t finish)
542 {
543 struct exclusion *next;
544 size_t next_index;
545
546 GC_ASSERT(I_HOLD_LOCK());
547 GC_ASSERT(ADDR(start) % ALIGNMENT == 0);
548 GC_ASSERT(ADDR_LT(start, finish));
549
550 next = GC_next_exclusion(start);
551 if (next != NULL) {
552 if (ADDR_LT(next->e_start, finish)) {
553 /* Incomplete error check. */
554 ABORT("Exclusion ranges overlap");
555 }
556 if (ADDR(next->e_start) == ADDR(finish)) {
557 /* Extend old range backwards. */
558 next->e_start = start;
559 #ifdef DEBUG_ADD_DEL_ROOTS
560 GC_log_printf("Updating static root exclusion to %p .. %p\n",
561 (void *)start, (void *)next->e_end);
562 #endif
563 return;
564 }
565 }
566
567 next_index = GC_excl_table_entries;
568 if (next_index >= MAX_EXCLUSIONS)
569 ABORT("Too many exclusions");
570 if (next != NULL) {
571 size_t i;
572
573 next_index = (size_t)(next - GC_excl_table);
574 for (i = GC_excl_table_entries; i > next_index; --i) {
575 GC_excl_table[i] = GC_excl_table[i - 1];
576 }
577 }
578 #ifdef DEBUG_ADD_DEL_ROOTS
579 GC_log_printf("Adding static root exclusion at %u: %p .. %p\n",
580 (unsigned)next_index, (void *)start, (void *)finish);
581 #endif
582 GC_excl_table[next_index].e_start = start;
583 GC_excl_table[next_index].e_end = finish;
584 ++GC_excl_table_entries;
585 }
586
587 GC_API void GC_CALL
588 GC_exclude_static_roots(void *b, void *e)
589 {
590 if (b == e) {
591 /* Nothing to exclude. */
592 return;
593 }
594
595 /* Round boundaries in direction reverse to that of `GC_add_roots`. */
596 #if ALIGNMENT > 1
597 b = PTR_ALIGN_DOWN((ptr_t)b, ALIGNMENT);
598 e = UNLIKELY(ADDR(e) > ~(word)(ALIGNMENT - 1))
599 ? PTR_ALIGN_DOWN((ptr_t)e, ALIGNMENT) /*< overflow */
600 : PTR_ALIGN_UP((ptr_t)e, ALIGNMENT);
601 #endif
602
603 LOCK();
604 GC_exclude_static_roots_inner((ptr_t)b, (ptr_t)e);
605 UNLOCK();
606 }
607
608 #if defined(WRAP_MARK_SOME) && defined(PARALLEL_MARK)
609 # define GC_PUSH_CONDITIONAL(b, t, all) \
610 (GC_parallel ? GC_push_conditional_eager(b, t, all) \
611 : GC_push_conditional_static(b, t, all))
612 #else
613 # define GC_PUSH_CONDITIONAL(b, t, all) GC_push_conditional_static(b, t, all)
614 #endif
615
616 /* Invoke `GC_push_conditional` on ranges that are not excluded. */
617 STATIC void
618 GC_push_conditional_with_exclusions(ptr_t bottom, ptr_t top, GC_bool all)
619 {
620 while (ADDR_LT(bottom, top)) {
621 struct exclusion *next = GC_next_exclusion(bottom);
622 ptr_t excl_start = top;
623
624 if (next != NULL) {
625 if (ADDR_GE(next->e_start, top)) {
626 next = NULL;
627 } else {
628 excl_start = next->e_start;
629 }
630 }
631 if (ADDR_LT(bottom, excl_start))
632 GC_PUSH_CONDITIONAL(bottom, excl_start, all);
633 if (NULL == next)
634 break;
635 bottom = next->e_end;
636 }
637 }
638
639 #ifdef IA64
640 GC_INNER void
641 GC_push_all_register_sections(ptr_t bs_lo, ptr_t bs_hi, GC_bool eager,
642 struct GC_traced_stack_sect_s *traced_stack_sect)
643 {
644 GC_ASSERT(I_HOLD_LOCK());
645 while (traced_stack_sect != NULL) {
646 ptr_t frame_bs_lo = traced_stack_sect->backing_store_end;
647
648 GC_ASSERT(ADDR_GE(bs_hi, frame_bs_lo));
649 if (eager) {
650 GC_push_all_eager(frame_bs_lo, bs_hi);
651 } else {
652 GC_push_all_stack(frame_bs_lo, bs_hi);
653 }
654 bs_hi = traced_stack_sect->saved_backing_store_ptr;
655 traced_stack_sect = traced_stack_sect->prev;
656 }
657 GC_ASSERT(ADDR_GE(bs_hi, bs_lo));
658 if (eager) {
659 GC_push_all_eager(bs_lo, bs_hi);
660 } else {
661 GC_push_all_stack(bs_lo, bs_hi);
662 }
663 }
664 #endif /* IA64 */
665
666 #ifdef THREADS
667
668 GC_INNER void
669 GC_push_all_stack_sections(ptr_t lo /* top */, ptr_t hi /* bottom */,
670 struct GC_traced_stack_sect_s *traced_stack_sect)
671 {
672 GC_ASSERT(I_HOLD_LOCK());
673 while (traced_stack_sect != NULL) {
674 GC_ASSERT(HOTTER_THAN(lo, (ptr_t)traced_stack_sect));
675 # ifdef STACK_GROWS_UP
676 GC_push_all_stack((ptr_t)traced_stack_sect, lo);
677 # else
678 GC_push_all_stack(lo, (ptr_t)traced_stack_sect);
679 # endif
680 lo = traced_stack_sect->saved_stack_ptr;
681 GC_ASSERT(lo != NULL);
682 traced_stack_sect = traced_stack_sect->prev;
683 }
684 GC_ASSERT(!HOTTER_THAN(hi, lo));
685 # ifdef STACK_GROWS_UP
686 /* We got them backwards! */
687 GC_push_all_stack(hi, lo);
688 # else
689 GC_push_all_stack(lo, hi);
690 # endif
691 }
692
693 #else /* !THREADS */
694
695 /*
696 * Similar to `GC_push_all_eager`, but only the part hotter than
697 * `cold_gc_frame` is scanned immediately. Needed to ensure that
698 * callee-save registers are not missed. Treats all interior pointers
699 * as valid and scans part of the area immediately, to make sure that
700 * saved register values are not lost. `cold_gc_frame` delimits the
701 * stack section that must be scanned eagerly. A zero value indicates
702 * that no eager scanning is needed. We do not need to worry about
703 * the manual VDB case here, since this is only called in the
704 * single-threaded case. We assume that we cannot collect between
705 * an assignment and the corresponding `GC_dirty()` call.
706 */
707 STATIC void
708 GC_push_all_stack_partially_eager(ptr_t bottom, ptr_t top, ptr_t cold_gc_frame)
709 {
710 # ifndef NEED_FIXUP_POINTER
711 if (GC_all_interior_pointers) {
712 /*
713 * Push the hot end of the stack eagerly, so that register values saved
714 * inside GC frames are marked before they disappear. The rest of the
715 * marking can be deferred until later.
716 */
717 if (0 == cold_gc_frame) {
718 GC_push_all_stack(bottom, top);
719 return;
720 }
721 GC_ASSERT(ADDR_GE(cold_gc_frame, bottom) && ADDR_GE(top, cold_gc_frame));
722 # ifdef STACK_GROWS_UP
723 GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
724 GC_push_all_eager(cold_gc_frame, top);
725 # else
726 GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
727 GC_push_all_eager(bottom, cold_gc_frame);
728 # endif
729 } else
730 # endif
731 /* else */ {
732 GC_push_all_eager(bottom, top);
733 }
734 # ifdef TRACE_BUF
735 GC_add_trace_entry("GC_push_all_stack", bottom, top);
736 # endif
737 }
738
739 /* Similar to `GC_push_all_stack_sections()` but also uses `cold_gc_frame`. */
740 STATIC void
741 GC_push_all_stack_part_eager_sections(
742 ptr_t lo /* top */, ptr_t hi /* bottom */, ptr_t cold_gc_frame,
743 struct GC_traced_stack_sect_s *traced_stack_sect)
744 {
745 GC_ASSERT(traced_stack_sect == NULL || cold_gc_frame == NULL
746 || HOTTER_THAN(cold_gc_frame, (ptr_t)traced_stack_sect));
747
748 while (traced_stack_sect != NULL) {
749 GC_ASSERT(HOTTER_THAN(lo, (ptr_t)traced_stack_sect));
750 # ifdef STACK_GROWS_UP
751 GC_push_all_stack_partially_eager((ptr_t)traced_stack_sect, lo,
752 cold_gc_frame);
753 # else
754 GC_push_all_stack_partially_eager(lo, (ptr_t)traced_stack_sect,
755 cold_gc_frame);
756 # endif
757 lo = traced_stack_sect->saved_stack_ptr;
758 GC_ASSERT(lo != NULL);
759 traced_stack_sect = traced_stack_sect->prev;
760 /* Note: use at most once. */
761 cold_gc_frame = NULL;
762 }
763
764 GC_ASSERT(!HOTTER_THAN(hi, lo));
765 # ifdef STACK_GROWS_UP
766 /* We got them backwards! */
767 GC_push_all_stack_partially_eager(hi, lo, cold_gc_frame);
768 # else
769 GC_push_all_stack_partially_eager(lo, hi, cold_gc_frame);
770 # endif
771 }
772
773 #endif /* !THREADS */
774
775 /*
776 * Push enough of the current stack eagerly to ensure that callee-save
777 * registers saved in GC frames are scanned. In the single-threaded case,
778 * schedule the entire stack for scanning. The 2nd argument (`context`)
779 * is a pointer to the (possibly `NULL`) thread context, for (currently
780 * hypothetical) more precise stack scanning. In the presence of threads,
781 * push enough of the current stack to ensure that callee-save registers
782 * saved in collector frames have been seen.
783 */
784 /* TODO: Merge it with per-thread stuff. */
785 STATIC void
786 GC_push_current_stack(ptr_t cold_gc_frame, void *context)
787 {
788 UNUSED_ARG(context);
789 GC_ASSERT(I_HOLD_LOCK());
790 #if defined(THREADS)
791 /* `cold_gc_frame` is non-`NULL`. */
792 # ifdef STACK_GROWS_UP
793 GC_push_all_eager(cold_gc_frame, GC_approx_sp());
794 # else
795 GC_push_all_eager(GC_approx_sp(), cold_gc_frame);
796 /*
797 * For IA-64, the register stack backing store is handled in the
798 * thread-specific code.
799 */
800 # endif
801 #else
802 GC_push_all_stack_part_eager_sections(GC_approx_sp(), GC_stackbottom,
803 cold_gc_frame, GC_traced_stack_sect);
804 # ifdef IA64
805 /*
806 * We also need to push the register stack backing store.
807 * This should really be done in the same way as the regular stack.
808 * For now we fudge it a bit. Note that the backing store grows up,
809 * so we cannot use `GC_push_all_stack_partially_eager`.
810 */
811 {
812 ptr_t bsp = GC_save_regs_ret_val;
813 ptr_t cold_gc_bs_pointer = bsp - 2048;
814 if (GC_all_interior_pointers
815 && ADDR_LT(GC_register_stackbottom, cold_gc_bs_pointer)) {
816 /*
817 * Adjust `cold_gc_bs_pointer` if below our innermost
818 * "traced stack section" in backing store.
819 */
820 if (GC_traced_stack_sect != NULL
821 && ADDR_LT(cold_gc_bs_pointer,
822 GC_traced_stack_sect->backing_store_end)) {
823 cold_gc_bs_pointer = GC_traced_stack_sect->backing_store_end;
824 }
825 GC_push_all_register_sections(GC_register_stackbottom,
826 cold_gc_bs_pointer, FALSE,
827 GC_traced_stack_sect);
828 GC_push_all_eager(cold_gc_bs_pointer, bsp);
829 } else {
830 GC_push_all_register_sections(GC_register_stackbottom, bsp,
831 TRUE /* `eager` */, GC_traced_stack_sect);
832 }
833 /*
834 * All values should be sufficiently aligned that we do not have to
835 * worry about the boundary.
836 */
837 }
838 # elif defined(E2K)
839 /* We also need to push procedure stack store. Procedure stack grows up. */
840 {
841 ptr_t bs_lo;
842 size_t stack_size;
843
844 /* TODO: Support `ps_ofs` here and in `GC_do_blocking_inner`. */
845 GET_PROCEDURE_STACK_LOCAL(0, &bs_lo, &stack_size);
846 GC_push_all_eager(bs_lo, bs_lo + stack_size);
847 }
848 # endif
849 #endif /* !THREADS */
850 }
851
852 GC_INNER void (*GC_push_typed_structures)(void) = 0;
853
854 GC_INNER void
855 GC_cond_register_dynamic_libraries(void)
856 {
857 GC_ASSERT(I_HOLD_LOCK());
858 #if defined(DYNAMIC_LOADING) && !defined(MSWIN_XBOX1) || defined(ANY_MSWIN)
859 GC_remove_tmp_roots();
860 if (!GC_no_dls)
861 GC_register_dynamic_libraries();
862 #else
863 GC_no_dls = TRUE;
864 #endif
865 }
866
867 STATIC void
868 GC_push_regs_and_stack(ptr_t cold_gc_frame)
869 {
870 GC_ASSERT(I_HOLD_LOCK());
871 #ifdef THREADS
872 if (NULL == cold_gc_frame) {
873 /* `GC_push_all_stacks` should push registers and stack. */
874 return;
875 }
876 #endif
877 GC_with_callee_saves_pushed(GC_push_current_stack, cold_gc_frame);
878 }
879
880 GC_INNER void
881 GC_push_roots(GC_bool all, ptr_t cold_gc_frame)
882 {
883 size_t i;
884 unsigned kind;
885
886 GC_ASSERT(I_HOLD_LOCK());
887
888 /* The initialization is needed for `GC_push_all_stacks`. */
889 GC_ASSERT(GC_is_initialized);
890
891 /*
892 * Next push static data. This must happen early on, since it is not
893 * robust against mark stack overflow. Re-register dynamic libraries,
894 * in case one got added. There is some argument for doing this as late
895 * as possible, especially on Win32, where it can change asynchronously.
896 * In those cases, we do it here. But on other platforms, it is not safe
897 * with the world stopped, so we do it earlier.
898 */
899 #if !defined(REGISTER_LIBRARIES_EARLY)
900 GC_cond_register_dynamic_libraries();
901 #endif
902
903 /* Mark everything in static data areas. */
904 for (i = 0; i < n_root_sets; i++) {
905 GC_push_conditional_with_exclusions(GC_static_roots[i].r_start,
906 GC_static_roots[i].r_end, all);
907 }
908
909 /*
910 * Mark all free-list header blocks, if those were allocated from
911 * the garbage-collected heap. This makes sure they do not disappear
912 * if we are not marking from static data. It also saves us the trouble
913 * of scanning them, and possibly that of marking the free lists.
914 */
915 for (kind = 0; kind < GC_n_kinds; kind++) {
916 const void *base = GC_base(GC_obj_kinds[kind].ok_freelist);
917
918 if (base != NULL) {
919 GC_set_mark_bit(base);
920 }
921 }
922
923 /*
924 * Mark from the collector internal roots if those might otherwise
925 * have been excluded.
926 */
927 #ifndef GC_NO_FINALIZATION
928 GC_push_finalizer_structures();
929 #endif
930 #ifdef THREADS
931 if (GC_no_dls || GC_roots_were_cleared)
932 GC_push_thread_structures();
933 #endif
934 if (GC_push_typed_structures) {
935 GC_push_typed_structures();
936 }
937
938 #if defined(THREAD_LOCAL_ALLOC)
939 /*
940 * Mark thread-local free lists, even if their mark descriptor excludes
941 * the link field. If the world is not stopped, this is unsafe.
942 * It is also unnecessary, since we will do this again with the world
943 * stopped.
944 */
945 if (GC_world_stopped) {
946 GC_mark_thread_local_free_lists();
947 }
948 #endif
949
950 /*
951 * Now traverse stacks, and mark from register contents.
952 * These must be done last, since they can legitimately overflow
953 * the mark stack. This is usually done by saving the current
954 * context on the stack, and then just tracing from the stack.
955 */
956 #ifdef STACK_NOT_SCANNED
957 UNUSED_ARG(cold_gc_frame);
958 #else
959 GC_push_regs_and_stack(cold_gc_frame);
960 #endif
961
962 if (GC_push_other_roots != 0) {
963 /*
964 * In the multi-threaded case, this also pushes thread stacks.
965 * Note that without the interior pointers recognition lots of stuff
966 * may have already been pushed, and this should be careful about
967 * mark stack overflows.
968 */
969 (*GC_push_other_roots)();
970 }
971 }
972