src/mm/boehm-gc/mark_rts.c

   1 /*
   2  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
   3  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
   4  *
   5  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   6  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   7  *
   8  * Permission is hereby granted to use or copy this program
   9  * for any purpose,  provided the above notices are retained on all copies.
  10  * Permission to modify the code and to distribute modified code is granted,
  11  * provided the above notices are retained, and a notice that the code was
  12  * modified is included with the above copyright notice.
  13  */
  14
  15 #include "private/gc_priv.h"
  16
  17 #include <stdio.h>
  18
  19 /* Data structure for list of root sets.                                */
  20 /* We keep a hash table, so that we can filter out duplicate additions. */
  21 /* Under Win32, we need to do a better job of filtering overlaps, so    */
  22 /* we resort to sequential search, and pay the price.                   */
  23 /* This is really declared in gc_priv.h:
  24 struct roots {
  25         ptr_t r_start;
  26         ptr_t r_end;
  27 #       if !defined(MSWIN32) && !defined(MSWINCE)
  28           struct roots * r_next;
  29 #       endif
  30         GC_bool r_tmp;
  31                 -- Delete before registering new dynamic libraries
  32 };
  33
  34 struct roots GC_static_roots[MAX_ROOT_SETS];
  35 */
  36
  37 int GC_no_dls = 0;      /* Register dynamic library data segments.      */
  38
  39 static int n_root_sets = 0;
  40         /* GC_static_roots[0..n_root_sets) contains the valid root sets. */
  41
  42 #if !defined(NO_DEBUGGING)
  43   /* For debugging:     */
  44   void GC_print_static_roots(void)
  45   {
  46     int i;
  47     size_t total = 0;
  48
  49     for (i = 0; i < n_root_sets; i++) {
  50         GC_printf("From %p to %p%s\n",
  51                   GC_static_roots[i].r_start,
  52                   GC_static_roots[i].r_end,
  53                   GC_static_roots[i].r_tmp ? " (temporary)" : "");
  54         total += GC_static_roots[i].r_end - GC_static_roots[i].r_start;
  55     }
  56     GC_printf("Total size: %ld\n", (unsigned long) total);
  57     if (GC_root_size != total) {
  58         GC_err_printf("GC_root_size incorrect: %ld!!\n",
  59                       (long) GC_root_size);
  60     }
  61   }
  62 #endif /* !NO_DEBUGGING */
  63
  64 #ifndef THREADS
  65   /* Primarily for debugging support:     */
  66   /* Is the address p in one of the registered static root sections?      */
  67   GC_INNER GC_bool GC_is_static_root(ptr_t p)
  68   {
  69     static int last_root_set = MAX_ROOT_SETS;
  70     int i;
  71
  72     if (last_root_set < n_root_sets
  73         && p >= GC_static_roots[last_root_set].r_start
  74         && p < GC_static_roots[last_root_set].r_end) return(TRUE);
  75     for (i = 0; i < n_root_sets; i++) {
  76         if (p >= GC_static_roots[i].r_start
  77             && p < GC_static_roots[i].r_end) {
  78             last_root_set = i;
  79             return(TRUE);
  80         }
  81     }
  82     return(FALSE);
  83   }
  84 #endif /* !THREADS */
  85
  86 #if !defined(MSWIN32) && !defined(MSWINCE)
  87 /*
  88 #   define LOG_RT_SIZE 6
  89 #   define RT_SIZE (1 << LOG_RT_SIZE)  -- Power of 2, may be != MAX_ROOT_SETS
  90
  91     struct roots * GC_root_index[RT_SIZE];
  92         -- Hash table header.  Used only to check whether a range is
  93         -- already present.
  94         -- really defined in gc_priv.h
  95 */
  96
  97   GC_INLINE int rt_hash(ptr_t addr)
  98   {
  99     word result = (word) addr;
 100 #   if CPP_WORDSZ > 8*LOG_RT_SIZE
 101         result ^= result >> 8*LOG_RT_SIZE;
 102 #   endif
 103 #   if CPP_WORDSZ > 4*LOG_RT_SIZE
 104         result ^= result >> 4*LOG_RT_SIZE;
 105 #   endif
 106     result ^= result >> 2*LOG_RT_SIZE;
 107     result ^= result >> LOG_RT_SIZE;
 108     result &= (RT_SIZE-1);
 109     return(result);
 110   }
 111
 112   /* Is a range starting at b already in the table? If so return a        */
 113   /* pointer to it, else NIL.                                             */
 114   GC_INNER struct roots * GC_roots_present(ptr_t b)
 115   {
 116     int h = rt_hash(b);
 117     struct roots *p = GC_root_index[h];
 118
 119     while (p != 0) {
 120         if (p -> r_start == (ptr_t)b) return(p);
 121         p = p -> r_next;
 122     }
 123     return(FALSE);
 124   }
 125
 126   /* Add the given root structure to the index. */
 127   GC_INLINE void add_roots_to_index(struct roots *p)
 128   {
 129     int h = rt_hash(p -> r_start);
 130
 131     p -> r_next = GC_root_index[h];
 132     GC_root_index[h] = p;
 133   }
 134 #endif /* !MSWIN32 */
 135
 136 GC_INNER word GC_root_size = 0;
 137
 138 GC_API void GC_CALL GC_add_roots(void *b, void *e)
 139 {
 140     DCL_LOCK_STATE;
 141
 142     if (!GC_is_initialized) GC_init();
 143     LOCK();
 144     GC_add_roots_inner((ptr_t)b, (ptr_t)e, FALSE);
 145     UNLOCK();
 146 }
 147
 148
 149 /* Add [b,e) to the root set.  Adding the same interval a second time   */
 150 /* is a moderately fast no-op, and hence benign.  We do not handle      */
 151 /* different but overlapping intervals efficiently.  (We do handle      */
 152 /* them correctly.)                                                     */
 153 /* Tmp specifies that the interval may be deleted before                */
 154 /* re-registering dynamic libraries.                                    */
 155 void GC_add_roots_inner(ptr_t b, ptr_t e, GC_bool tmp)
 156 {
 157     struct roots * old;
 158
 159     /* Adjust and check range boundaries for safety */
 160     GC_ASSERT((word)b % sizeof(word) == 0);
 161     e = (ptr_t)((word)e & ~(sizeof(word) - 1));
 162     GC_ASSERT(b <= e);
 163     if (b == e) return;  /* nothing to do? */
 164
 165 #   if defined(MSWIN32) || defined(MSWINCE)
 166       /* Spend the time to ensure that there are no overlapping */
 167       /* or adjacent intervals.                                 */
 168       /* This could be done faster with e.g. a                  */
 169       /* balanced tree.  But the execution time here is         */
 170       /* virtually guaranteed to be dominated by the time it    */
 171       /* takes to scan the roots.                               */
 172       {
 173         register int i;
 174         old = 0; /* initialized to prevent warning. */
 175         for (i = 0; i < n_root_sets; i++) {
 176             old = GC_static_roots + i;
 177             if (b <= old -> r_end && e >= old -> r_start) {
 178                 if (b < old -> r_start) {
 179                     old -> r_start = b;
 180                     GC_root_size += (old -> r_start - b);
 181                 }
 182                 if (e > old -> r_end) {
 183                     old -> r_end = e;
 184                     GC_root_size += (e - old -> r_end);
 185                 }
 186                 old -> r_tmp &= tmp;
 187                 break;
 188             }
 189         }
 190         if (i < n_root_sets) {
 191           /* merge other overlapping intervals */
 192             struct roots *other;
 193
 194             for (i++; i < n_root_sets; i++) {
 195               other = GC_static_roots + i;
 196               b = other -> r_start;
 197               e = other -> r_end;
 198               if (b <= old -> r_end && e >= old -> r_start) {
 199                 if (b < old -> r_start) {
 200                     old -> r_start = b;
 201                     GC_root_size += (old -> r_start - b);
 202                 }
 203                 if (e > old -> r_end) {
 204                     old -> r_end = e;
 205                     GC_root_size += (e - old -> r_end);
 206                 }
 207                 old -> r_tmp &= other -> r_tmp;
 208                 /* Delete this entry. */
 209                   GC_root_size -= (other -> r_end - other -> r_start);
 210                   other -> r_start = GC_static_roots[n_root_sets-1].r_start;
 211                   other -> r_end = GC_static_roots[n_root_sets-1].r_end;
 212                   n_root_sets--;
 213               }
 214             }
 215           return;
 216         }
 217       }
 218 #   else
 219       old = GC_roots_present(b);
 220       if (old != 0) {
 221         if (e <= old -> r_end) /* already there */ return;
 222         /* else extend */
 223         GC_root_size += e - old -> r_end;
 224         old -> r_end = e;
 225         return;
 226       }
 227 #   endif
 228     if (n_root_sets == MAX_ROOT_SETS) {
 229         ABORT("Too many root sets\n");
 230     }
 231     GC_static_roots[n_root_sets].r_start = (ptr_t)b;
 232     GC_static_roots[n_root_sets].r_end = (ptr_t)e;
 233     GC_static_roots[n_root_sets].r_tmp = tmp;
 234 #   if !defined(MSWIN32) && !defined(MSWINCE)
 235       GC_static_roots[n_root_sets].r_next = 0;
 236       add_roots_to_index(GC_static_roots + n_root_sets);
 237 #   endif
 238     GC_root_size += e - b;
 239     n_root_sets++;
 240 }
 241
 242 static GC_bool roots_were_cleared = FALSE;
 243
 244 GC_API void GC_CALL GC_clear_roots(void)
 245 {
 246     DCL_LOCK_STATE;
 247
 248     if (!GC_is_initialized) GC_init();
 249     LOCK();
 250     roots_were_cleared = TRUE;
 251     n_root_sets = 0;
 252     GC_root_size = 0;
 253 #   if !defined(MSWIN32) && !defined(MSWINCE)
 254       {
 255         int i;
 256         for (i = 0; i < RT_SIZE; i++) GC_root_index[i] = 0;
 257       }
 258 #   endif
 259     UNLOCK();
 260 }
 261
 262 /* Internal use only; lock held.        */
 263 STATIC void GC_remove_root_at_pos(int i)
 264 {
 265     GC_root_size -= (GC_static_roots[i].r_end - GC_static_roots[i].r_start);
 266     GC_static_roots[i].r_start = GC_static_roots[n_root_sets-1].r_start;
 267     GC_static_roots[i].r_end = GC_static_roots[n_root_sets-1].r_end;
 268     GC_static_roots[i].r_tmp = GC_static_roots[n_root_sets-1].r_tmp;
 269     n_root_sets--;
 270 }
 271
 272 #if !defined(MSWIN32) && !defined(MSWINCE)
 273   STATIC void GC_rebuild_root_index(void)
 274   {
 275     int i;
 276
 277     for (i = 0; i < RT_SIZE; i++) GC_root_index[i] = 0;
 278     for (i = 0; i < n_root_sets; i++)
 279         add_roots_to_index(GC_static_roots + i);
 280   }
 281 #endif
 282
 283 #if defined(DYNAMIC_LOADING) || defined(MSWIN32) || defined(MSWINCE) \
 284      || defined(PCR)
 285 /* Internal use only; lock held.        */
 286 STATIC void GC_remove_tmp_roots(void)
 287 {
 288     int i;
 289
 290     for (i = 0; i < n_root_sets; ) {
 291         if (GC_static_roots[i].r_tmp) {
 292             GC_remove_root_at_pos(i);
 293         } else {
 294             i++;
 295         }
 296     }
 297 #   if !defined(MSWIN32) && !defined(MSWINCE)
 298       GC_rebuild_root_index();
 299 #   endif
 300 }
 301 #endif
 302
 303 #if !defined(MSWIN32) && !defined(MSWINCE)
 304   STATIC void GC_remove_roots_inner(ptr_t b, ptr_t e);
 305
 306   GC_API void GC_CALL GC_remove_roots(void *b, void *e)
 307   {
 308     DCL_LOCK_STATE;
 309
 310     /* Quick check whether has nothing to do */
 311     if ((((word)b + (sizeof(word) - 1)) & ~(sizeof(word) - 1)) >=
 312         ((word)e & ~(sizeof(word) - 1)))
 313       return;
 314
 315     LOCK();
 316     GC_remove_roots_inner((ptr_t)b, (ptr_t)e);
 317     UNLOCK();
 318   }
 319
 320   /* Should only be called when the lock is held */
 321   STATIC void GC_remove_roots_inner(ptr_t b, ptr_t e)
 322   {
 323     int i;
 324     for (i = 0; i < n_root_sets; ) {
 325         if (GC_static_roots[i].r_start >= b
 326             && GC_static_roots[i].r_end <= e) {
 327             GC_remove_root_at_pos(i);
 328         } else {
 329             i++;
 330         }
 331     }
 332     GC_rebuild_root_index();
 333   }
 334 #endif /* !defined(MSWIN32) && !defined(MSWINCE) */
 335
 336 #if (defined(MSWIN32) || defined(MSWINCE)) && !defined(NO_DEBUGGING)
 337   /* Not used at present (except for, may be, debugging purpose).       */
 338   /* Workaround for the OS mapping and unmapping behind our back:       */
 339   /* Is the address p in one of the temporary static root sections?     */
 340   GC_bool GC_is_tmp_root(ptr_t p)
 341   {
 342     static int last_root_set = MAX_ROOT_SETS;
 343     register int i;
 344
 345     if (last_root_set < n_root_sets
 346         && p >= GC_static_roots[last_root_set].r_start
 347         && p < GC_static_roots[last_root_set].r_end)
 348         return GC_static_roots[last_root_set].r_tmp;
 349     for (i = 0; i < n_root_sets; i++) {
 350         if (p >= GC_static_roots[i].r_start
 351             && p < GC_static_roots[i].r_end) {
 352             last_root_set = i;
 353             return GC_static_roots[i].r_tmp;
 354         }
 355     }
 356     return(FALSE);
 357   }
 358 #endif /* MSWIN32 || MSWINCE */
 359
 360 GC_INNER ptr_t GC_approx_sp(void)
 361 {
 362     volatile word sp;
 363     sp = (word)&sp;
 364                 /* Also force stack to grow if necessary. Otherwise the */
 365                 /* later accesses might cause the kernel to think we're */
 366                 /* doing something wrong.                               */
 367     return((ptr_t)sp);
 368 }
 369
 370 /*
 371  * Data structure for excluded static roots.
 372  * Real declaration is in gc_priv.h.
 373
 374 struct exclusion {
 375     ptr_t e_start;
 376     ptr_t e_end;
 377 };
 378
 379 struct exclusion GC_excl_table[MAX_EXCLUSIONS];
 380                                         -- Array of exclusions, ascending
 381                                         -- address order.
 382 */
 383
 384 STATIC size_t GC_excl_table_entries = 0;/* Number of entries in use.      */
 385
 386 /* Return the first exclusion range that includes an address >= start_addr */
 387 /* Assumes the exclusion table contains at least one entry (namely the     */
 388 /* GC data structures).                                                    */
 389 STATIC struct exclusion * GC_next_exclusion(ptr_t start_addr)
 390 {
 391     size_t low = 0;
 392     size_t high = GC_excl_table_entries - 1;
 393     size_t mid;
 394
 395     while (high > low) {
 396         mid = (low + high) >> 1;
 397         /* low <= mid < high    */
 398         if ((word) GC_excl_table[mid].e_end <= (word) start_addr) {
 399             low = mid + 1;
 400         } else {
 401             high = mid;
 402         }
 403     }
 404     if ((word) GC_excl_table[low].e_end <= (word) start_addr) return 0;
 405     return GC_excl_table + low;
 406 }
 407
 408 /* Should only be called when the lock is held.  The range boundaries   */
 409 /* should be properly aligned and valid.                                */
 410 GC_INNER void GC_exclude_static_roots_inner(void *start, void *finish)
 411 {
 412     struct exclusion * next;
 413     size_t next_index, i;
 414
 415     GC_ASSERT((word)start % sizeof(word) == 0);
 416     GC_ASSERT(start < finish);
 417
 418     if (0 == GC_excl_table_entries) {
 419         next = 0;
 420     } else {
 421         next = GC_next_exclusion(start);
 422     }
 423     if (0 != next) {
 424       if ((word)(next -> e_start) < (word) finish) {
 425         /* incomplete error check. */
 426         ABORT("exclusion ranges overlap");
 427       }
 428       if ((word)(next -> e_start) == (word) finish) {
 429         /* extend old range backwards   */
 430           next -> e_start = (ptr_t)start;
 431           return;
 432       }
 433       next_index = next - GC_excl_table;
 434       for (i = GC_excl_table_entries; i > next_index; --i) {
 435         GC_excl_table[i] = GC_excl_table[i-1];
 436       }
 437     } else {
 438       next_index = GC_excl_table_entries;
 439     }
 440     if (GC_excl_table_entries == MAX_EXCLUSIONS) ABORT("Too many exclusions");
 441     GC_excl_table[next_index].e_start = (ptr_t)start;
 442     GC_excl_table[next_index].e_end = (ptr_t)finish;
 443     ++GC_excl_table_entries;
 444 }
 445
 446 GC_API void GC_CALL GC_exclude_static_roots(void *b, void *e)
 447 {
 448     DCL_LOCK_STATE;
 449
 450     /* Adjust the upper boundary for safety (round down) */
 451     e = (void *)((word)e & ~(sizeof(word) - 1));
 452
 453     if (b == e) return;  /* nothing to exclude? */
 454
 455     LOCK();
 456     GC_exclude_static_roots_inner(b, e);
 457     UNLOCK();
 458 }
 459
 460 /* Invoke push_conditional on ranges that are not excluded. */
 461 /*ARGSUSED*/
 462 STATIC void GC_push_conditional_with_exclusions(ptr_t bottom, ptr_t top,
 463                                                 GC_bool all)
 464 {
 465     struct exclusion * next;
 466     ptr_t excl_start;
 467
 468     while (bottom < top) {
 469         next = GC_next_exclusion(bottom);
 470         if (0 == next || (excl_start = next -> e_start) >= top) {
 471             GC_push_conditional(bottom, top, all);
 472             return;
 473         }
 474         if (excl_start > bottom) GC_push_conditional(bottom, excl_start, all);
 475         bottom = next -> e_end;
 476     }
 477 }
 478
 479 #ifdef IA64
 480   /* Similar to GC_push_all_stack_frames() but for IA-64 registers store. */
 481   GC_INNER void GC_push_all_register_frames(ptr_t bs_lo, ptr_t bs_hi,
 482                     int eager, struct GC_activation_frame_s *activation_frame)
 483   {
 484     while (activation_frame != NULL) {
 485         ptr_t frame_bs_lo = activation_frame -> backing_store_end;
 486         GC_ASSERT(frame_bs_lo <= bs_hi);
 487         if (eager) {
 488             GC_push_all_eager(frame_bs_lo, bs_hi);
 489         } else {
 490             GC_push_all_stack(frame_bs_lo, bs_hi);
 491         }
 492         bs_hi = activation_frame -> saved_backing_store_ptr;
 493         activation_frame = activation_frame -> prev;
 494     }
 495     GC_ASSERT(bs_lo <= bs_hi);
 496     if (eager) {
 497         GC_push_all_eager(bs_lo, bs_hi);
 498     } else {
 499         GC_push_all_stack(bs_lo, bs_hi);
 500     }
 501   }
 502 #endif /* IA64 */
 503
 504 #ifdef THREADS
 505
 506 GC_INNER void GC_push_all_stack_frames(ptr_t lo, ptr_t hi,
 507                         struct GC_activation_frame_s *activation_frame)
 508 {
 509     while (activation_frame != NULL) {
 510         GC_ASSERT(lo HOTTER_THAN (ptr_t)activation_frame);
 511 #       ifdef STACK_GROWS_UP
 512             GC_push_all_stack((ptr_t)activation_frame, lo);
 513 #       else /* STACK_GROWS_DOWN */
 514             GC_push_all_stack(lo, (ptr_t)activation_frame);
 515 #       endif
 516         lo = activation_frame -> saved_stack_ptr;
 517         GC_ASSERT(lo != NULL);
 518         activation_frame = activation_frame -> prev;
 519     }
 520     GC_ASSERT(!(hi HOTTER_THAN lo));
 521 #   ifdef STACK_GROWS_UP
 522         /* We got them backwards! */
 523         GC_push_all_stack(hi, lo);
 524 #   else /* STACK_GROWS_DOWN */
 525         GC_push_all_stack(lo, hi);
 526 #   endif
 527 }
 528
 529 #else /* !THREADS */
 530
 531 # ifdef TRACE_BUF
 532     /* Defined in mark.c.       */
 533     void GC_add_trace_entry(char *kind, word arg1, word arg2);
 534 # endif
 535
 536                         /* Similar to GC_push_all_eager, but only the   */
 537                         /* part hotter than cold_gc_frame is scanned    */
 538                         /* immediately.  Needed to ensure that callee-  */
 539                         /* save registers are not missed.               */
 540 /*
 541  * A version of GC_push_all that treats all interior pointers as valid
 542  * and scans part of the area immediately, to make sure that saved
 543  * register values are not lost.
 544  * Cold_gc_frame delimits the stack section that must be scanned
 545  * eagerly.  A zero value indicates that no eager scanning is needed.
 546  * We don't need to worry about the MANUAL_VDB case here, since this
 547  * is only called in the single-threaded case.  We assume that we
 548  * cannot collect between an assignment and the corresponding
 549  * GC_dirty() call.
 550  */
 551 STATIC void GC_push_all_stack_partially_eager(ptr_t bottom, ptr_t top,
 552                                               ptr_t cold_gc_frame)
 553 {
 554   if (!NEED_FIXUP_POINTER && GC_all_interior_pointers) {
 555     /* Push the hot end of the stack eagerly, so that register values   */
 556     /* saved inside GC frames are marked before they disappear.         */
 557     /* The rest of the marking can be deferred until later.             */
 558     if (0 == cold_gc_frame) {
 559         GC_push_all_stack(bottom, top);
 560         return;
 561     }
 562     GC_ASSERT(bottom <= cold_gc_frame && cold_gc_frame <= top);
 563 #   ifdef STACK_GROWS_DOWN
 564         GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
 565         GC_push_all_eager(bottom, cold_gc_frame);
 566 #   else /* STACK_GROWS_UP */
 567         GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
 568         GC_push_all_eager(cold_gc_frame, top);
 569 #   endif /* STACK_GROWS_UP */
 570   } else {
 571     GC_push_all_eager(bottom, top);
 572   }
 573 # ifdef TRACE_BUF
 574       GC_add_trace_entry("GC_push_all_stack", bottom, top);
 575 # endif
 576 }
 577
 578 /* Similar to GC_push_all_stack_frames() but also uses cold_gc_frame.   */
 579 STATIC void GC_push_all_stack_part_eager_frames(ptr_t lo, ptr_t hi,
 580         ptr_t cold_gc_frame, struct GC_activation_frame_s *activation_frame)
 581 {
 582     GC_ASSERT(activation_frame == NULL || cold_gc_frame == NULL ||
 583                 cold_gc_frame HOTTER_THAN (ptr_t)activation_frame);
 584
 585     while (activation_frame != NULL) {
 586         GC_ASSERT(lo HOTTER_THAN (ptr_t)activation_frame);
 587 #       ifdef STACK_GROWS_UP
 588             GC_push_all_stack_partially_eager((ptr_t)activation_frame, lo,
 589                                                 cold_gc_frame);
 590 #       else /* STACK_GROWS_DOWN */
 591             GC_push_all_stack_partially_eager(lo, (ptr_t)activation_frame,
 592                                                 cold_gc_frame);
 593 #       endif
 594         lo = activation_frame -> saved_stack_ptr;
 595         GC_ASSERT(lo != NULL);
 596         activation_frame = activation_frame -> prev;
 597         cold_gc_frame = NULL; /* Use at most once.      */
 598     }
 599
 600     GC_ASSERT(!(hi HOTTER_THAN lo));
 601 #   ifdef STACK_GROWS_UP
 602         /* We got them backwards! */
 603         GC_push_all_stack_partially_eager(hi, lo, cold_gc_frame);
 604 #   else /* STACK_GROWS_DOWN */
 605         GC_push_all_stack_partially_eager(lo, hi, cold_gc_frame);
 606 #   endif
 607 }
 608
 609 #endif /* !THREADS */
 610
 611                         /* Push enough of the current stack eagerly to  */
 612                         /* ensure that callee-save registers saved in   */
 613                         /* GC frames are scanned.                       */
 614                         /* In the non-threads case, schedule entire     */
 615                         /* stack for scanning.                          */
 616                         /* The second argument is a pointer to the      */
 617                         /* (possibly null) thread context, for          */
 618                         /* (currently hypothetical) more precise        */
 619                         /* stack scanning.                              */
 620 /*
 621  * In the absence of threads, push the stack contents.
 622  * In the presence of threads, push enough of the current stack
 623  * to ensure that callee-save registers saved in collector frames have been
 624  * seen.
 625  * FIXME: Merge with per-thread stuff.
 626  */
 627 /*ARGSUSED*/
 628 STATIC void GC_push_current_stack(ptr_t cold_gc_frame, void * context)
 629 {
 630 #   if defined(THREADS)
 631         if (0 == cold_gc_frame) return;
 632 #       ifdef STACK_GROWS_DOWN
 633           GC_push_all_eager(GC_approx_sp(), cold_gc_frame);
 634           /* For IA64, the register stack backing store is handled      */
 635           /* in the thread-specific code.                               */
 636 #       else
 637           GC_push_all_eager(cold_gc_frame, GC_approx_sp());
 638 #       endif
 639 #   else
 640         GC_push_all_stack_part_eager_frames(GC_approx_sp(), GC_stackbottom,
 641                                         cold_gc_frame, GC_activation_frame);
 642 #       ifdef IA64
 643               /* We also need to push the register stack backing store. */
 644               /* This should really be done in the same way as the      */
 645               /* regular stack.  For now we fudge it a bit.             */
 646               /* Note that the backing store grows up, so we can't use  */
 647               /* GC_push_all_stack_partially_eager.                     */
 648               {
 649                 ptr_t bsp = GC_save_regs_ret_val;
 650                 ptr_t cold_gc_bs_pointer = bsp - 2048;
 651                 if (GC_all_interior_pointers &&
 652                     cold_gc_bs_pointer > BACKING_STORE_BASE) {
 653                   /* Adjust cold_gc_bs_pointer if below our innermost   */
 654                   /* "activation frame" in backing store.               */
 655                   if (GC_activation_frame != NULL && cold_gc_bs_pointer <
 656                                 GC_activation_frame->backing_store_end)
 657                     cold_gc_bs_pointer =
 658                                 GC_activation_frame->backing_store_end;
 659                   GC_push_all_register_frames(BACKING_STORE_BASE,
 660                         cold_gc_bs_pointer, FALSE, GC_activation_frame);
 661                   GC_push_all_eager(cold_gc_bs_pointer, bsp);
 662                 } else {
 663                   GC_push_all_register_frames(BACKING_STORE_BASE, bsp,
 664                                 TRUE /* eager */, GC_activation_frame);
 665                 }
 666                 /* All values should be sufficiently aligned that we    */
 667                 /* don't have to worry about the boundary.              */
 668               }
 669 #       endif
 670 #   endif /* !THREADS */
 671 }
 672
 673 GC_INNER void (*GC_push_typed_structures)(void) = 0;
 674
 675                         /* Push GC internal roots.  These are normally  */
 676                         /* included in the static data segment, and     */
 677                         /* Thus implicitly pushed.  But we must do this */
 678                         /* explicitly if normal root processing is      */
 679                         /* disabled.                                    */
 680 /*
 681  * Push GC internal roots.  Only called if there is some reason to believe
 682  * these would not otherwise get registered.
 683  */
 684 STATIC void GC_push_gc_structures(void)
 685 {
 686     GC_push_finalizer_structures();
 687 #   if defined(THREADS)
 688       GC_push_thread_structures();
 689 #   endif
 690     if( GC_push_typed_structures )
 691       GC_push_typed_structures();
 692 }
 693
 694 #ifdef THREAD_LOCAL_ALLOC
 695   GC_INNER void GC_mark_thread_local_free_lists(void);
 696 #endif
 697
 698 GC_INNER void GC_cond_register_dynamic_libraries(void)
 699 {
 700 # if defined(DYNAMIC_LOADING) || defined(MSWIN32) || defined(MSWINCE) \
 701      || defined(PCR)
 702     GC_remove_tmp_roots();
 703     if (!GC_no_dls) GC_register_dynamic_libraries();
 704 # else
 705     GC_no_dls = TRUE;
 706 # endif
 707 }
 708
 709 STATIC void GC_push_regs_and_stack(ptr_t cold_gc_frame)
 710 {
 711     GC_with_callee_saves_pushed(GC_push_current_stack, cold_gc_frame);
 712 }
 713
 714 /*
 715  * Call the mark routines (GC_tl_push for a single pointer, GC_push_conditional
 716  * on groups of pointers) on every top level accessible pointer.
 717  * If all is FALSE, arrange to push only possibly altered values.
 718  * Cold_gc_frame is an address inside a GC frame that
 719  * remains valid until all marking is complete.
 720  * A zero value indicates that it's OK to miss some
 721  * register values.
 722  */
 723 GC_INNER void GC_push_roots(GC_bool all, ptr_t cold_gc_frame)
 724 {
 725     int i;
 726     unsigned kind;
 727
 728     /*
 729      * Next push static data.  This must happen early on, since it's
 730      * not robust against mark stack overflow.
 731      */
 732      /* Re-register dynamic libraries, in case one got added.           */
 733      /* There is some argument for doing this as late as possible,      */
 734      /* especially on win32, where it can change asynchronously.        */
 735      /* In those cases, we do it here.  But on other platforms, it's    */
 736      /* not safe with the world stopped, so we do it earlier.           */
 737 #      if !defined(REGISTER_LIBRARIES_EARLY)
 738          GC_cond_register_dynamic_libraries();
 739 #      endif
 740
 741      /* Mark everything in static data areas                             */
 742        for (i = 0; i < n_root_sets; i++) {
 743          GC_push_conditional_with_exclusions(
 744                              GC_static_roots[i].r_start,
 745                              GC_static_roots[i].r_end, all);
 746        }
 747
 748      /* Mark all free list header blocks, if those were allocated from  */
 749      /* the garbage collected heap.  This makes sure they don't         */
 750      /* disappear if we are not marking from static data.  It also      */
 751      /* saves us the trouble of scanning them, and possibly that of     */
 752      /* marking the freelists.                                          */
 753        for (kind = 0; kind < GC_n_kinds; kind++) {
 754          void *base = GC_base(GC_obj_kinds[kind].ok_freelist);
 755          if (0 != base) {
 756            GC_set_mark_bit(base);
 757          }
 758        }
 759
 760      /* Mark from GC internal roots if those might otherwise have       */
 761      /* been excluded.                                                  */
 762        if (GC_no_dls || roots_were_cleared) {
 763            GC_push_gc_structures();
 764        }
 765
 766      /* Mark thread local free lists, even if their mark        */
 767      /* descriptor excludes the link field.                     */
 768      /* If the world is not stopped, this is unsafe.  It is     */
 769      /* also unnecessary, since we will do this again with the  */
 770      /* world stopped.                                          */
 771 #      if defined(THREAD_LOCAL_ALLOC)
 772          if (GC_world_stopped) GC_mark_thread_local_free_lists();
 773 #      endif
 774
 775     /*
 776      * Now traverse stacks, and mark from register contents.
 777      * These must be done last, since they can legitimately overflow
 778      * the mark stack.
 779      * This is usually done by saving the current context on the
 780      * stack, and then just tracing from the stack.
 781      */
 782       GC_push_regs_and_stack(cold_gc_frame);
 783
 784     if (GC_push_other_roots != 0) (*GC_push_other_roots)();
 785         /* In the threads case, this also pushes thread stacks. */
 786         /* Note that without interior pointer recognition lots  */
 787         /* of stuff may have been pushed already, and this      */
 788         /* should be careful about mark stack overflows.        */
 789 }