mark_rts.c 29.9 KB
Newer Older
1
/*
eg's avatar
eg committed
2 3 4 5 6 7 8 9 10 11 12 13 14
 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
 * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
 *
 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
 * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
 *
 * Permission is hereby granted to use or copy this program
 * for any purpose,  provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 */

15 16 17 18 19 20 21 22
#include "private/gc_priv.h"

#include <stdio.h>

/* Data structure for list of root sets.                                */
/* We keep a hash table, so that we can filter out duplicate additions. */
/* Under Win32, we need to do a better job of filtering overlaps, so    */
/* we resort to sequential search, and pay the price.                   */
eg's avatar
eg committed
23 24
/* This is really declared in gc_priv.h:
struct roots {
25 26 27 28 29 30 31
        ptr_t r_start;
        ptr_t r_end;
#       if !defined(MSWIN32) && !defined(MSWINCE) && !defined(CYGWIN32)
          struct roots * r_next;
#       endif
        GC_bool r_tmp;
                -- Delete before registering new dynamic libraries
eg's avatar
eg committed
32 33 34 35 36
};

struct roots GC_static_roots[MAX_ROOT_SETS];
*/

37
int GC_no_dls = 0;      /* Register dynamic library data segments.      */
eg's avatar
eg committed
38 39

static int n_root_sets = 0;
40
        /* GC_static_roots[0..n_root_sets) contains the valid root sets. */
eg's avatar
eg committed
41

42 43 44 45 46 47
#if !defined(NO_DEBUGGING) || defined(GC_ASSERTIONS)
  /* Should return the same value as GC_root_size.      */
  GC_INNER word GC_compute_root_size(void)
  {
    int i;
    word size = 0;
eg's avatar
eg committed
48 49

    for (i = 0; i < n_root_sets; i++) {
50
      size += GC_static_roots[i].r_end - GC_static_roots[i].r_start;
eg's avatar
eg committed
51
    }
52 53 54 55 56 57 58 59 60 61
    return size;
  }
#endif /* !NO_DEBUGGING || GC_ASSERTIONS */

#if !defined(NO_DEBUGGING)
  /* For debugging:     */
  void GC_print_static_roots(void)
  {
    int i;
    word size;
eg's avatar
eg committed
62

63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
    for (i = 0; i < n_root_sets; i++) {
        GC_printf("From %p to %p%s\n",
                  (void *)GC_static_roots[i].r_start,
                  (void *)GC_static_roots[i].r_end,
                  GC_static_roots[i].r_tmp ? " (temporary)" : "");
    }
    GC_printf("GC_root_size: %lu\n", (unsigned long)GC_root_size);

    if ((size = GC_compute_root_size()) != GC_root_size)
      GC_err_printf("GC_root_size incorrect!! Should be: %lu\n",
                    (unsigned long)size);
  }
#endif /* !NO_DEBUGGING */

#ifndef THREADS
  /* Primarily for debugging support:     */
  /* Is the address p in one of the registered static root sections?      */
  GC_INNER GC_bool GC_is_static_root(ptr_t p)
  {
eg's avatar
eg committed
82
    static int last_root_set = MAX_ROOT_SETS;
83 84
    int i;

eg's avatar
eg committed
85
    if (last_root_set < n_root_sets
86 87 88
        && (word)p >= (word)GC_static_roots[last_root_set].r_start
        && (word)p < (word)GC_static_roots[last_root_set].r_end)
      return(TRUE);
eg's avatar
eg committed
89
    for (i = 0; i < n_root_sets; i++) {
90 91 92 93
        if ((word)p >= (word)GC_static_roots[i].r_start
            && (word)p < (word)GC_static_roots[i].r_end) {
          last_root_set = i;
          return(TRUE);
eg's avatar
eg committed
94 95 96
        }
    }
    return(FALSE);
97 98
  }
#endif /* !THREADS */
eg's avatar
eg committed
99

100 101
#if !defined(MSWIN32) && !defined(MSWINCE) && !defined(CYGWIN32)
/*
eg's avatar
eg committed
102 103 104 105
#   define LOG_RT_SIZE 6
#   define RT_SIZE (1 << LOG_RT_SIZE)  -- Power of 2, may be != MAX_ROOT_SETS

    struct roots * GC_root_index[RT_SIZE];
106 107 108
        -- Hash table header.  Used only to check whether a range is
        -- already present.
        -- really defined in gc_priv.h
eg's avatar
eg committed
109 110
*/

111 112
  GC_INLINE int rt_hash(ptr_t addr)
  {
eg's avatar
eg committed
113 114
    word result = (word) addr;
#   if CPP_WORDSZ > 8*LOG_RT_SIZE
115
        result ^= result >> 8*LOG_RT_SIZE;
eg's avatar
eg committed
116 117
#   endif
#   if CPP_WORDSZ > 4*LOG_RT_SIZE
118
        result ^= result >> 4*LOG_RT_SIZE;
eg's avatar
eg committed
119 120 121 122 123
#   endif
    result ^= result >> 2*LOG_RT_SIZE;
    result ^= result >> LOG_RT_SIZE;
    result &= (RT_SIZE-1);
    return(result);
124
  }
eg's avatar
eg committed
125

126 127 128 129
  /* Is a range starting at b already in the table? If so return a      */
  /* pointer to it, else NULL.                                          */
  GC_INNER void * GC_roots_present(ptr_t b)
  {
eg's avatar
eg committed
130 131
    int h = rt_hash(b);
    struct roots *p = GC_root_index[h];
132

eg's avatar
eg committed
133 134 135 136
    while (p != 0) {
        if (p -> r_start == (ptr_t)b) return(p);
        p = p -> r_next;
    }
137 138
    return NULL;
  }
eg's avatar
eg committed
139

140 141 142
  /* Add the given root structure to the index. */
  GC_INLINE void add_roots_to_index(struct roots *p)
  {
eg's avatar
eg committed
143
    int h = rt_hash(p -> r_start);
144

eg's avatar
eg committed
145 146
    p -> r_next = GC_root_index[h];
    GC_root_index[h] = p;
147 148
  }
#endif /* !MSWIN32 && !MSWINCE && !CYGWIN32 */
eg's avatar
eg committed
149

150
GC_INNER word GC_root_size = 0;
eg's avatar
eg committed
151

152
GC_API void GC_CALL GC_add_roots(void *b, void *e)
eg's avatar
eg committed
153 154
{
    DCL_LOCK_STATE;
155 156

    if (!EXPECT(GC_is_initialized, TRUE)) GC_init();
eg's avatar
eg committed
157
    LOCK();
eg's avatar
eg committed
158
    GC_add_roots_inner((ptr_t)b, (ptr_t)e, FALSE);
eg's avatar
eg committed
159 160 161 162
    UNLOCK();
}


163 164 165 166 167 168
/* Add [b,e) to the root set.  Adding the same interval a second time   */
/* is a moderately fast no-op, and hence benign.  We do not handle      */
/* different but overlapping intervals efficiently.  (We do handle      */
/* them correctly.)                                                     */
/* Tmp specifies that the interval may be deleted before                */
/* re-registering dynamic libraries.                                    */
eg's avatar
eg committed
169
void GC_add_roots_inner(ptr_t b, ptr_t e, GC_bool tmp)
eg's avatar
eg committed
170
{
171 172 173 174 175 176 177 178 179 180 181 182 183 184
    GC_ASSERT((word)b <= (word)e);
    b = (ptr_t)(((word)b + (sizeof(word) - 1)) & ~(word)(sizeof(word) - 1));
                                        /* round b up to word boundary */
    e = (ptr_t)((word)e & ~(word)(sizeof(word) - 1));
                                        /* round e down to word boundary */
    if ((word)b >= (word)e) return; /* nothing to do */

#   if defined(MSWIN32) || defined(MSWINCE) || defined(CYGWIN32)
      /* Spend the time to ensure that there are no overlapping */
      /* or adjacent intervals.                                 */
      /* This could be done faster with e.g. a                  */
      /* balanced tree.  But the execution time here is         */
      /* virtually guaranteed to be dominated by the time it    */
      /* takes to scan the roots.                               */
eg's avatar
eg committed
185 186
      {
        register int i;
187 188
        struct roots * old = NULL; /* initialized to prevent warning. */

eg's avatar
eg committed
189 190
        for (i = 0; i < n_root_sets; i++) {
            old = GC_static_roots + i;
191 192 193 194
            if ((word)b <= (word)old->r_end
                 && (word)e >= (word)old->r_start) {
                if ((word)b < (word)old->r_start) {
                    GC_root_size += old->r_start - b;
eg's avatar
eg committed
195
                    old -> r_start = b;
eg's avatar
eg committed
196
                }
197 198
                if ((word)e > (word)old->r_end) {
                    GC_root_size += e - old->r_end;
eg's avatar
eg committed
199
                    old -> r_end = e;
eg's avatar
eg committed
200 201 202 203 204 205 206 207
                }
                old -> r_tmp &= tmp;
                break;
            }
        }
        if (i < n_root_sets) {
          /* merge other overlapping intervals */
            struct roots *other;
208

eg's avatar
eg committed
209 210
            for (i++; i < n_root_sets; i++) {
              other = GC_static_roots + i;
eg's avatar
eg committed
211 212
              b = other -> r_start;
              e = other -> r_end;
213 214 215 216
              if ((word)b <= (word)old->r_end
                  && (word)e >= (word)old->r_start) {
                if ((word)b < (word)old->r_start) {
                    GC_root_size += old->r_start - b;
eg's avatar
eg committed
217
                    old -> r_start = b;
eg's avatar
eg committed
218
                }
219 220
                if ((word)e > (word)old->r_end) {
                    GC_root_size += e - old->r_end;
eg's avatar
eg committed
221
                    old -> r_end = e;
eg's avatar
eg committed
222 223 224 225 226 227
                }
                old -> r_tmp &= other -> r_tmp;
                /* Delete this entry. */
                  GC_root_size -= (other -> r_end - other -> r_start);
                  other -> r_start = GC_static_roots[n_root_sets-1].r_start;
                  other -> r_end = GC_static_roots[n_root_sets-1].r_end;
eg's avatar
eg committed
228
                  n_root_sets--;
eg's avatar
eg committed
229 230 231 232 233 234
              }
            }
          return;
        }
      }
#   else
235 236 237 238 239 240 241 242 243 244 245
      {
        struct roots * old = (struct roots *)GC_roots_present(b);

        if (old != 0) {
          if ((word)e <= (word)old->r_end)
            return; /* already there */
          /* else extend */
          GC_root_size += e - old -> r_end;
          old -> r_end = e;
          return;
        }
eg's avatar
eg committed
246 247 248
      }
#   endif
    if (n_root_sets == MAX_ROOT_SETS) {
249
        ABORT("Too many root sets");
eg's avatar
eg committed
250
    }
251 252 253 254 255 256

#   ifdef DEBUG_ADD_DEL_ROOTS
      GC_log_printf("Adding data root section %d: %p .. %p%s\n",
                    n_root_sets, (void *)b, (void *)e,
                    tmp ? " (temporary)" : "");
#   endif
eg's avatar
eg committed
257 258 259
    GC_static_roots[n_root_sets].r_start = (ptr_t)b;
    GC_static_roots[n_root_sets].r_end = (ptr_t)e;
    GC_static_roots[n_root_sets].r_tmp = tmp;
260
#   if !defined(MSWIN32) && !defined(MSWINCE) && !defined(CYGWIN32)
eg's avatar
eg committed
261
      GC_static_roots[n_root_sets].r_next = 0;
262
      add_roots_to_index(GC_static_roots + n_root_sets);
eg's avatar
eg committed
263
#   endif
eg's avatar
eg committed
264
    GC_root_size += e - b;
eg's avatar
eg committed
265 266 267 268 269
    n_root_sets++;
}

static GC_bool roots_were_cleared = FALSE;

270
GC_API void GC_CALL GC_clear_roots(void)
eg's avatar
eg committed
271 272
{
    DCL_LOCK_STATE;
273 274

    if (!EXPECT(GC_is_initialized, TRUE)) GC_init();
eg's avatar
eg committed
275 276 277 278
    LOCK();
    roots_were_cleared = TRUE;
    n_root_sets = 0;
    GC_root_size = 0;
279 280 281 282 283
#   if !defined(MSWIN32) && !defined(MSWINCE) && !defined(CYGWIN32)
      BZERO(GC_root_index, RT_SIZE * sizeof(void *));
#   endif
#   ifdef DEBUG_ADD_DEL_ROOTS
      GC_log_printf("Clear all data root sections\n");
eg's avatar
eg committed
284 285 286 287
#   endif
    UNLOCK();
}

288 289
/* Internal use only; lock held.        */
STATIC void GC_remove_root_at_pos(int i)
eg's avatar
eg committed
290
{
291 292 293 294 295 296
#   ifdef DEBUG_ADD_DEL_ROOTS
      GC_log_printf("Remove data root section at %d: %p .. %p%s\n",
                    i, (void *)GC_static_roots[i].r_start,
                    (void *)GC_static_roots[i].r_end,
                    GC_static_roots[i].r_tmp ? " (temporary)" : "");
#   endif
eg's avatar
eg committed
297 298 299 300 301 302 303
    GC_root_size -= (GC_static_roots[i].r_end - GC_static_roots[i].r_start);
    GC_static_roots[i].r_start = GC_static_roots[n_root_sets-1].r_start;
    GC_static_roots[i].r_end = GC_static_roots[n_root_sets-1].r_end;
    GC_static_roots[i].r_tmp = GC_static_roots[n_root_sets-1].r_tmp;
    n_root_sets--;
}

304 305 306
#if !defined(MSWIN32) && !defined(MSWINCE) && !defined(CYGWIN32)
  STATIC void GC_rebuild_root_index(void)
  {
eg's avatar
eg committed
307
    int i;
308
    BZERO(GC_root_index, RT_SIZE * sizeof(void *));
eg's avatar
eg committed
309
    for (i = 0; i < n_root_sets; i++)
310 311
        add_roots_to_index(GC_static_roots + i);
  }
eg's avatar
eg committed
312 313
#endif

314
#if defined(DYNAMIC_LOADING) || defined(MSWIN32) || defined(MSWINCE) \
315 316
     || defined(PCR) || defined(CYGWIN32)
/* Internal use only; lock held.        */
317
STATIC void GC_remove_tmp_roots(void)
eg's avatar
eg committed
318 319
{
    int i;
320

eg's avatar
eg committed
321
    for (i = 0; i < n_root_sets; ) {
322
        if (GC_static_roots[i].r_tmp) {
eg's avatar
eg committed
323
            GC_remove_root_at_pos(i);
324 325 326
        } else {
            i++;
        }
eg's avatar
eg committed
327
    }
328
#   if !defined(MSWIN32) && !defined(MSWINCE) && !defined(CYGWIN32)
329 330
      GC_rebuild_root_index();
#   endif
eg's avatar
eg committed
331
}
332
#endif
eg's avatar
eg committed
333

334 335 336 337 338
#if !defined(MSWIN32) && !defined(MSWINCE) && !defined(CYGWIN32)
  STATIC void GC_remove_roots_inner(ptr_t b, ptr_t e);

  GC_API void GC_CALL GC_remove_roots(void *b, void *e)
  {
eg's avatar
eg committed
339
    DCL_LOCK_STATE;
340 341 342 343 344 345

    /* Quick check whether has nothing to do */
    if ((((word)b + (sizeof(word) - 1)) & ~(word)(sizeof(word) - 1)) >=
        ((word)e & ~(word)(sizeof(word) - 1)))
      return;

eg's avatar
eg committed
346 347 348
    LOCK();
    GC_remove_roots_inner((ptr_t)b, (ptr_t)e);
    UNLOCK();
349
  }
eg's avatar
eg committed
350

351 352 353
  /* Should only be called when the lock is held */
  STATIC void GC_remove_roots_inner(ptr_t b, ptr_t e)
  {
eg's avatar
eg committed
354 355
    int i;
    for (i = 0; i < n_root_sets; ) {
356 357
        if ((word)GC_static_roots[i].r_start >= (word)b
            && (word)GC_static_roots[i].r_end <= (word)e) {
eg's avatar
eg committed
358
            GC_remove_root_at_pos(i);
359 360 361
        } else {
            i++;
        }
eg's avatar
eg committed
362 363
    }
    GC_rebuild_root_index();
364 365 366 367 368 369 370 371 372
  }
#endif /* !defined(MSWIN32) && !defined(MSWINCE) && !defined(CYGWIN32) */

#if !defined(NO_DEBUGGING)
  /* For the debugging purpose only.                                    */
  /* Workaround for the OS mapping and unmapping behind our back:       */
  /* Is the address p in one of the temporary static root sections?     */
  GC_API int GC_CALL GC_is_tmp_root(void *p)
  {
eg's avatar
eg committed
373 374
    static int last_root_set = MAX_ROOT_SETS;
    register int i;
375

eg's avatar
eg committed
376
    if (last_root_set < n_root_sets
377 378 379
        && (word)p >= (word)GC_static_roots[last_root_set].r_start
        && (word)p < (word)GC_static_roots[last_root_set].r_end)
        return GC_static_roots[last_root_set].r_tmp;
eg's avatar
eg committed
380
    for (i = 0; i < n_root_sets; i++) {
381 382
        if ((word)p >= (word)GC_static_roots[i].r_start
            && (word)p < (word)GC_static_roots[i].r_end) {
eg's avatar
eg committed
383 384 385 386 387
            last_root_set = i;
            return GC_static_roots[i].r_tmp;
        }
    }
    return(FALSE);
388 389
  }
#endif /* !NO_DEBUGGING */
eg's avatar
eg committed
390

391
GC_INNER ptr_t GC_approx_sp(void)
eg's avatar
eg committed
392
{
393
    volatile word sp;
394 395 396 397 398 399 400 401
#   if defined(__GNUC__) && (__GNUC__ >= 4)
        sp = (word)__builtin_frame_address(0);
#   else
        sp = (word)&sp;
#   endif
                /* Also force stack to grow if necessary. Otherwise the */
                /* later accesses might cause the kernel to think we're */
                /* doing something wrong.                               */
402
    return((ptr_t)sp);
eg's avatar
eg committed
403 404 405 406 407 408 409 410 411 412 413 414
}

/*
 * Data structure for excluded static roots.
 * Real declaration is in gc_priv.h.

struct exclusion {
    ptr_t e_start;
    ptr_t e_end;
};

struct exclusion GC_excl_table[MAX_EXCLUSIONS];
415 416
                                        -- Array of exclusions, ascending
                                        -- address order.
eg's avatar
eg committed
417 418
*/

419
STATIC size_t GC_excl_table_entries = 0;/* Number of entries in use.      */
eg's avatar
eg committed
420 421

/* Return the first exclusion range that includes an address >= start_addr */
422 423
/* Assumes the exclusion table contains at least one entry (namely the     */
/* GC data structures).                                                    */
424
STATIC struct exclusion * GC_next_exclusion(ptr_t start_addr)
eg's avatar
eg committed
425 426 427 428 429
{
    size_t low = 0;
    size_t high = GC_excl_table_entries - 1;

    while (high > low) {
430 431 432 433 434 435 436 437
        size_t mid = (low + high) >> 1;

        /* low <= mid < high    */
        if ((word) GC_excl_table[mid].e_end <= (word) start_addr) {
            low = mid + 1;
        } else {
            high = mid;
        }
eg's avatar
eg committed
438 439 440 441 442
    }
    if ((word) GC_excl_table[low].e_end <= (word) start_addr) return 0;
    return GC_excl_table + low;
}

443 444 445
/* Should only be called when the lock is held.  The range boundaries   */
/* should be properly aligned and valid.                                */
GC_INNER void GC_exclude_static_roots_inner(void *start, void *finish)
eg's avatar
eg committed
446 447
{
    struct exclusion * next;
448 449 450 451
    size_t next_index;

    GC_ASSERT((word)start % sizeof(word) == 0);
    GC_ASSERT((word)start < (word)finish);
eg's avatar
eg committed
452 453

    if (0 == GC_excl_table_entries) {
454
        next = 0;
eg's avatar
eg committed
455
    } else {
456
        next = GC_next_exclusion(start);
eg's avatar
eg committed
457 458
    }
    if (0 != next) {
459 460
      size_t i;

eg's avatar
eg committed
461
      if ((word)(next -> e_start) < (word) finish) {
462 463 464
        /* incomplete error check. */
        ABORT("Exclusion ranges overlap");
      }
eg's avatar
eg committed
465
      if ((word)(next -> e_start) == (word) finish) {
466
        /* extend old range backwards   */
eg's avatar
eg committed
467
          next -> e_start = (ptr_t)start;
468
          return;
eg's avatar
eg committed
469 470 471
      }
      next_index = next - GC_excl_table;
      for (i = GC_excl_table_entries; i > next_index; --i) {
472
        GC_excl_table[i] = GC_excl_table[i-1];
eg's avatar
eg committed
473 474 475 476 477 478 479 480 481 482
      }
    } else {
      next_index = GC_excl_table_entries;
    }
    if (GC_excl_table_entries == MAX_EXCLUSIONS) ABORT("Too many exclusions");
    GC_excl_table[next_index].e_start = (ptr_t)start;
    GC_excl_table[next_index].e_end = (ptr_t)finish;
    ++GC_excl_table_entries;
}

483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517
GC_API void GC_CALL GC_exclude_static_roots(void *b, void *e)
{
    DCL_LOCK_STATE;

    if (b == e) return;  /* nothing to exclude? */

    /* Round boundaries (in direction reverse to that of GC_add_roots). */
    b = (void *)((word)b & ~(word)(sizeof(word) - 1));
    e = (void *)(((word)e + (sizeof(word) - 1)) & ~(word)(sizeof(word) - 1));
    if (NULL == e)
      e = (void *)(~(word)(sizeof(word) - 1)); /* handle overflow */

    LOCK();
    GC_exclude_static_roots_inner(b, e);
    UNLOCK();
}

#if defined(WRAP_MARK_SOME) && defined(PARALLEL_MARK)
  /* GC_mark_local does not handle memory protection faults yet.  So,   */
  /* the static data regions are scanned immediately by GC_push_roots.  */
  GC_INNER void GC_push_conditional_eager(ptr_t bottom, ptr_t top,
                                          GC_bool all);
# define GC_PUSH_CONDITIONAL(b, t, all) \
                (GC_parallel \
                    ? GC_push_conditional_eager(b, t, all) \
                    : GC_push_conditional((ptr_t)(b), (ptr_t)(t), all))
#elif defined(GC_DISABLE_INCREMENTAL)
# define GC_PUSH_CONDITIONAL(b, t, all) GC_push_all((ptr_t)(b), (ptr_t)(t))
#else
# define GC_PUSH_CONDITIONAL(b, t, all) \
                GC_push_conditional((ptr_t)(b), (ptr_t)(t), all)
                        /* Do either of GC_push_all or GC_push_selected */
                        /* depending on the third arg.                  */
#endif

eg's avatar
eg committed
518
/* Invoke push_conditional on ranges that are not excluded. */
519
STATIC void GC_push_conditional_with_exclusions(ptr_t bottom, ptr_t top,
520
                                                GC_bool all GC_ATTR_UNUSED)
eg's avatar
eg committed
521
{
522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576
    while ((word)bottom < (word)top) {
        struct exclusion *next = GC_next_exclusion(bottom);
        ptr_t excl_start;

        if (0 == next
            || (word)(excl_start = next -> e_start) >= (word)top) {
          GC_PUSH_CONDITIONAL(bottom, top, all);
          break;
        }
        if ((word)excl_start > (word)bottom)
          GC_PUSH_CONDITIONAL(bottom, excl_start, all);
        bottom = next -> e_end;
    }
}

#ifdef IA64
  /* Similar to GC_push_all_stack_sections() but for IA-64 registers store. */
  GC_INNER void GC_push_all_register_sections(ptr_t bs_lo, ptr_t bs_hi,
                  int eager, struct GC_traced_stack_sect_s *traced_stack_sect)
  {
    while (traced_stack_sect != NULL) {
        ptr_t frame_bs_lo = traced_stack_sect -> backing_store_end;
        GC_ASSERT((word)frame_bs_lo <= (word)bs_hi);
        if (eager) {
            GC_push_all_eager(frame_bs_lo, bs_hi);
        } else {
            GC_push_all_stack(frame_bs_lo, bs_hi);
        }
        bs_hi = traced_stack_sect -> saved_backing_store_ptr;
        traced_stack_sect = traced_stack_sect -> prev;
    }
    GC_ASSERT((word)bs_lo <= (word)bs_hi);
    if (eager) {
        GC_push_all_eager(bs_lo, bs_hi);
    } else {
        GC_push_all_stack(bs_lo, bs_hi);
    }
  }
#endif /* IA64 */

#ifdef THREADS

GC_INNER void GC_push_all_stack_sections(ptr_t lo, ptr_t hi,
                        struct GC_traced_stack_sect_s *traced_stack_sect)
{
    while (traced_stack_sect != NULL) {
        GC_ASSERT((word)lo HOTTER_THAN (word)traced_stack_sect);
#       ifdef STACK_GROWS_UP
            GC_push_all_stack((ptr_t)traced_stack_sect, lo);
#       else /* STACK_GROWS_DOWN */
            GC_push_all_stack(lo, (ptr_t)traced_stack_sect);
#       endif
        lo = traced_stack_sect -> saved_stack_ptr;
        GC_ASSERT(lo != NULL);
        traced_stack_sect = traced_stack_sect -> prev;
577
    }
578 579 580 581 582 583 584
    GC_ASSERT(!((word)hi HOTTER_THAN (word)lo));
#   ifdef STACK_GROWS_UP
        /* We got them backwards! */
        GC_push_all_stack(hi, lo);
#   else /* STACK_GROWS_DOWN */
        GC_push_all_stack(lo, hi);
#   endif
585 586
}

587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681
#else /* !THREADS */

# ifdef TRACE_BUF
    /* Defined in mark.c.       */
    void GC_add_trace_entry(char *kind, word arg1, word arg2);
# endif

                        /* Similar to GC_push_all_eager, but only the   */
                        /* part hotter than cold_gc_frame is scanned    */
                        /* immediately.  Needed to ensure that callee-  */
                        /* save registers are not missed.               */
/*
 * A version of GC_push_all that treats all interior pointers as valid
 * and scans part of the area immediately, to make sure that saved
 * register values are not lost.
 * Cold_gc_frame delimits the stack section that must be scanned
 * eagerly.  A zero value indicates that no eager scanning is needed.
 * We don't need to worry about the MANUAL_VDB case here, since this
 * is only called in the single-threaded case.  We assume that we
 * cannot collect between an assignment and the corresponding
 * GC_dirty() call.
 */
STATIC void GC_push_all_stack_partially_eager(ptr_t bottom, ptr_t top,
                                              ptr_t cold_gc_frame)
{
#ifndef NEED_FIXUP_POINTER
  if (GC_all_interior_pointers) {
    /* Push the hot end of the stack eagerly, so that register values   */
    /* saved inside GC frames are marked before they disappear.         */
    /* The rest of the marking can be deferred until later.             */
    if (0 == cold_gc_frame) {
        GC_push_all_stack(bottom, top);
        return;
    }
    GC_ASSERT((word)bottom <= (word)cold_gc_frame
              && (word)cold_gc_frame <= (word)top);
#   ifdef STACK_GROWS_DOWN
        GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
        GC_push_all_eager(bottom, cold_gc_frame);
#   else /* STACK_GROWS_UP */
        GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
        GC_push_all_eager(cold_gc_frame, top);
#   endif /* STACK_GROWS_UP */
  } else
#endif
  /* else */ {
    GC_push_all_eager(bottom, top);
  }
# ifdef TRACE_BUF
    GC_add_trace_entry("GC_push_all_stack", (word)bottom, (word)top);
# endif
}

/* Similar to GC_push_all_stack_sections() but also uses cold_gc_frame. */
STATIC void GC_push_all_stack_part_eager_sections(ptr_t lo, ptr_t hi,
        ptr_t cold_gc_frame, struct GC_traced_stack_sect_s *traced_stack_sect)
{
    GC_ASSERT(traced_stack_sect == NULL || cold_gc_frame == NULL ||
              (word)cold_gc_frame HOTTER_THAN (word)traced_stack_sect);

    while (traced_stack_sect != NULL) {
        GC_ASSERT((word)lo HOTTER_THAN (word)traced_stack_sect);
#       ifdef STACK_GROWS_UP
            GC_push_all_stack_partially_eager((ptr_t)traced_stack_sect, lo,
                                              cold_gc_frame);
#       else /* STACK_GROWS_DOWN */
            GC_push_all_stack_partially_eager(lo, (ptr_t)traced_stack_sect,
                                              cold_gc_frame);
#       endif
        lo = traced_stack_sect -> saved_stack_ptr;
        GC_ASSERT(lo != NULL);
        traced_stack_sect = traced_stack_sect -> prev;
        cold_gc_frame = NULL; /* Use at most once.      */
    }

    GC_ASSERT(!((word)hi HOTTER_THAN (word)lo));
#   ifdef STACK_GROWS_UP
        /* We got them backwards! */
        GC_push_all_stack_partially_eager(hi, lo, cold_gc_frame);
#   else /* STACK_GROWS_DOWN */
        GC_push_all_stack_partially_eager(lo, hi, cold_gc_frame);
#   endif
}

#endif /* !THREADS */

                        /* Push enough of the current stack eagerly to  */
                        /* ensure that callee-save registers saved in   */
                        /* GC frames are scanned.                       */
                        /* In the non-threads case, schedule entire     */
                        /* stack for scanning.                          */
                        /* The second argument is a pointer to the      */
                        /* (possibly null) thread context, for          */
                        /* (currently hypothetical) more precise        */
                        /* stack scanning.                              */
eg's avatar
eg committed
682 683 684 685 686
/*
 * In the absence of threads, push the stack contents.
 * In the presence of threads, push enough of the current stack
 * to ensure that callee-save registers saved in collector frames have been
 * seen.
eg's avatar
eg committed
687
 * FIXME: Merge with per-thread stuff.
eg's avatar
eg committed
688
 */
689 690
STATIC void GC_push_current_stack(ptr_t cold_gc_frame,
                                  void * context GC_ATTR_UNUSED)
eg's avatar
eg committed
691 692
{
#   if defined(THREADS)
693
        if (0 == cold_gc_frame) return;
eg's avatar
eg committed
694
#       ifdef STACK_GROWS_DOWN
695 696 697
          GC_push_all_eager(GC_approx_sp(), cold_gc_frame);
          /* For IA64, the register stack backing store is handled      */
          /* in the thread-specific code.                               */
eg's avatar
eg committed
698
#       else
699
          GC_push_all_eager(cold_gc_frame, GC_approx_sp());
eg's avatar
eg committed
700 701
#       endif
#   else
702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731
        GC_push_all_stack_part_eager_sections(GC_approx_sp(), GC_stackbottom,
                                        cold_gc_frame, GC_traced_stack_sect);
#       ifdef IA64
              /* We also need to push the register stack backing store. */
              /* This should really be done in the same way as the      */
              /* regular stack.  For now we fudge it a bit.             */
              /* Note that the backing store grows up, so we can't use  */
              /* GC_push_all_stack_partially_eager.                     */
              {
                ptr_t bsp = GC_save_regs_ret_val;
                ptr_t cold_gc_bs_pointer = bsp - 2048;
                if (GC_all_interior_pointers
                    && (word)cold_gc_bs_pointer > (word)BACKING_STORE_BASE) {
                  /* Adjust cold_gc_bs_pointer if below our innermost   */
                  /* "traced stack section" in backing store.           */
                  if (GC_traced_stack_sect != NULL
                      && (word)cold_gc_bs_pointer
                          < (word)GC_traced_stack_sect->backing_store_end)
                    cold_gc_bs_pointer =
                                GC_traced_stack_sect->backing_store_end;
                  GC_push_all_register_sections(BACKING_STORE_BASE,
                        cold_gc_bs_pointer, FALSE, GC_traced_stack_sect);
                  GC_push_all_eager(cold_gc_bs_pointer, bsp);
                } else {
                  GC_push_all_register_sections(BACKING_STORE_BASE, bsp,
                                TRUE /* eager */, GC_traced_stack_sect);
                }
                /* All values should be sufficiently aligned that we    */
                /* don't have to worry about the boundary.              */
              }
eg's avatar
eg committed
732 733 734 735
#       endif
#   endif /* !THREADS */
}

736
GC_INNER void (*GC_push_typed_structures)(void) = 0;
737

738 739 740 741 742
                        /* Push GC internal roots.  These are normally  */
                        /* included in the static data segment, and     */
                        /* Thus implicitly pushed.  But we must do this */
                        /* explicitly if normal root processing is      */
                        /* disabled.                                    */
eg's avatar
eg committed
743 744 745 746
/*
 * Push GC internal roots.  Only called if there is some reason to believe
 * these would not otherwise get registered.
 */
747
STATIC void GC_push_gc_structures(void)
eg's avatar
eg committed
748
{
749 750 751
#   ifndef GC_NO_FINALIZATION
      GC_push_finalizer_structures();
#   endif
eg's avatar
eg committed
752 753 754
#   if defined(THREADS)
      GC_push_thread_structures();
#   endif
755 756
    if( GC_push_typed_structures )
      GC_push_typed_structures();
eg's avatar
eg committed
757 758
}

759
GC_INNER void GC_cond_register_dynamic_libraries(void)
eg's avatar
eg committed
760 761
{
# if defined(DYNAMIC_LOADING) || defined(MSWIN32) || defined(MSWINCE) \
762
     || defined(CYGWIN32) || defined(PCR)
eg's avatar
eg committed
763 764 765 766 767 768 769
    GC_remove_tmp_roots();
    if (!GC_no_dls) GC_register_dynamic_libraries();
# else
    GC_no_dls = TRUE;
# endif
}

770 771 772 773 774
STATIC void GC_push_regs_and_stack(ptr_t cold_gc_frame)
{
    GC_with_callee_saves_pushed(GC_push_current_stack, cold_gc_frame);
}

eg's avatar
eg committed
775
/*
776 777 778
 * Call the mark routines (GC_push_one for a single pointer,
 * GC_push_conditional on groups of pointers) on every top level
 * accessible pointer.
eg's avatar
eg committed
779 780 781 782 783 784
 * If all is FALSE, arrange to push only possibly altered values.
 * Cold_gc_frame is an address inside a GC frame that
 * remains valid until all marking is complete.
 * A zero value indicates that it's OK to miss some
 * register values.
 */
785
GC_INNER void GC_push_roots(GC_bool all, ptr_t cold_gc_frame GC_ATTR_UNUSED)
eg's avatar
eg committed
786
{
eg's avatar
eg committed
787
    int i;
788
    unsigned kind;
eg's avatar
eg committed
789 790 791 792 793

    /*
     * Next push static data.  This must happen early on, since it's
     * not robust against mark stack overflow.
     */
794 795 796 797 798
     /* Re-register dynamic libraries, in case one got added.           */
     /* There is some argument for doing this as late as possible,      */
     /* especially on win32, where it can change asynchronously.        */
     /* In those cases, we do it here.  But on other platforms, it's    */
     /* not safe with the world stopped, so we do it earlier.           */
eg's avatar
eg committed
799 800
#      if !defined(REGISTER_LIBRARIES_EARLY)
         GC_cond_register_dynamic_libraries();
eg's avatar
eg committed
801 802 803 804 805
#      endif

     /* Mark everything in static data areas                             */
       for (i = 0; i < n_root_sets; i++) {
         GC_push_conditional_with_exclusions(
806 807
                             GC_static_roots[i].r_start,
                             GC_static_roots[i].r_end, all);
eg's avatar
eg committed
808 809
       }

810 811 812 813 814
     /* Mark all free list header blocks, if those were allocated from  */
     /* the garbage collected heap.  This makes sure they don't         */
     /* disappear if we are not marking from static data.  It also      */
     /* saves us the trouble of scanning them, and possibly that of     */
     /* marking the freelists.                                          */
eg's avatar
eg committed
815
       for (kind = 0; kind < GC_n_kinds; kind++) {
816 817 818 819
         void *base = GC_base(GC_obj_kinds[kind].ok_freelist);
         if (0 != base) {
           GC_set_mark_bit(base);
         }
eg's avatar
eg committed
820
       }
821 822 823

     /* Mark from GC internal roots if those might otherwise have       */
     /* been excluded.                                                  */
eg's avatar
eg committed
824
       if (GC_no_dls || roots_were_cleared) {
825
           GC_push_gc_structures();
eg's avatar
eg committed
826 827
       }

828 829 830 831 832
     /* Mark thread local free lists, even if their mark        */
     /* descriptor excludes the link field.                     */
     /* If the world is not stopped, this is unsafe.  It is     */
     /* also unnecessary, since we will do this again with the  */
     /* world stopped.                                          */
eg's avatar
eg committed
833 834
#      if defined(THREAD_LOCAL_ALLOC)
         if (GC_world_stopped) GC_mark_thread_local_free_lists();
eg's avatar
eg committed
835 836 837 838 839 840
#      endif

    /*
     * Now traverse stacks, and mark from register contents.
     * These must be done last, since they can legitimately overflow
     * the mark stack.
eg's avatar
eg committed
841 842
     * This is usually done by saving the current context on the
     * stack, and then just tracing from the stack.
eg's avatar
eg committed
843
     */
844 845 846
#    ifndef STACK_NOT_SCANNED
       GC_push_regs_and_stack(cold_gc_frame);
#    endif
eg's avatar
eg committed
847

eg's avatar
eg committed
848
    if (GC_push_other_roots != 0) (*GC_push_other_roots)();
849 850 851 852
        /* In the threads case, this also pushes thread stacks. */
        /* Note that without interior pointer recognition lots  */
        /* of stuff may have been pushed already, and this      */
        /* should be careful about mark stack overflows.        */
eg's avatar
eg committed
853
}