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