src/mm/boehm-gc/alloc.c

   1 /*
   2  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
   3  * Copyright (c) 1991-1996 by Xerox Corporation.  All rights reserved.
   4  * Copyright (c) 1998 by Silicon Graphics.  All rights reserved.
   5  * Copyright (c) 1999-2004 Hewlett-Packard Development Company, L.P.
   6  *
   7  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   8  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   9  *
  10  * Permission is hereby granted to use or copy this program
  11  * for any purpose,  provided the above notices are retained on all copies.
  12  * Permission to modify the code and to distribute modified code is granted,
  13  * provided the above notices are retained, and a notice that the code was
  14  * modified is included with the above copyright notice.
  15  *
  16  */
  17
  18
  19 # include "private/gc_priv.h"
  20
  21 # include <stdio.h>
  22 # if !defined(MACOS) && !defined(MSWINCE)
  23 #   include <signal.h>
  24 #   include <sys/types.h>
  25 # endif
  26
  27 /*
  28  * Separate free lists are maintained for different sized objects
  29  * up to MAXOBJBYTES.
  30  * The call GC_allocobj(i,k) ensures that the freelist for
  31  * kind k objects of size i points to a non-empty
  32  * free list. It returns a pointer to the first entry on the free list.
  33  * In a single-threaded world, GC_allocobj may be called to allocate
  34  * an object of (small) size i as follows:
  35  *
  36  *            opp = &(GC_objfreelist[i]);
  37  *            if (*opp == 0) GC_allocobj(i, NORMAL);
  38  *            ptr = *opp;
  39  *            *opp = obj_link(ptr);
  40  *
  41  * Note that this is very fast if the free list is non-empty; it should
  42  * only involve the execution of 4 or 5 simple instructions.
  43  * All composite objects on freelists are cleared, except for
  44  * their first word.
  45  */
  46
  47 /*
  48  *  The allocator uses GC_allochblk to allocate large chunks of objects.
  49  * These chunks all start on addresses which are multiples of
  50  * HBLKSZ.   Each allocated chunk has an associated header,
  51  * which can be located quickly based on the address of the chunk.
  52  * (See headers.c for details.)
  53  * This makes it possible to check quickly whether an
  54  * arbitrary address corresponds to an object administered by the
  55  * allocator.
  56  */
  57
  58 word GC_non_gc_bytes = 0;  /* Number of bytes not intended to be collected */
  59
  60 word GC_gc_no = 0;
  61
  62 #ifndef SMALL_CONFIG
  63   int GC_incremental = 0;  /* By default, stop the world.       */
  64 #endif
  65
  66 int GC_parallel = FALSE;   /* By default, parallel GC is off.   */
  67
  68 #ifndef GC_FULL_FREQ
  69 # define GC_FULL_FREQ 19   /* Every 20th collection is a full   */
  70                            /* collection, whether we need it    */
  71                            /* or not.                           */
  72 #endif
  73
  74 int GC_full_freq = GC_FULL_FREQ;
  75
  76 STATIC GC_bool GC_need_full_gc = FALSE;
  77                            /* Need full GC do to heap growth.   */
  78
  79 #ifdef THREADS
  80   GC_bool GC_world_stopped = FALSE;
  81 # define IF_THREADS(x) x
  82 #else
  83 # define IF_THREADS(x)
  84 #endif
  85
  86 STATIC word GC_used_heap_size_after_full = 0;
  87
  88 char * GC_copyright[] =
  89 {"Copyright 1988,1989 Hans-J. Boehm and Alan J. Demers ",
  90 "Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved. ",
  91 "Copyright (c) 1996-1998 by Silicon Graphics.  All rights reserved. ",
  92 "Copyright (c) 1999-2009 by Hewlett-Packard Company.  All rights reserved. ",
  93 "THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY",
  94 " EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.",
  95 "See source code for details." };
  96
  97 /* Version macros are now defined in gc_version.h, which is included by */
  98 /* gc.h, which is included by gc_priv.h".                               */
  99
 100 #ifndef GC_NO_VERSION_VAR
 101
 102 unsigned GC_version = ((GC_VERSION_MAJOR << 16) | (GC_VERSION_MINOR << 8) | GC_TMP_ALPHA_VERSION);
 103
 104 #endif /* GC_NO_VERSION_VAR */
 105
 106 /* some more variables */
 107
 108 extern signed_word GC_bytes_found; /* Number of reclaimed bytes         */
 109                                   /* after garbage collection           */
 110
 111 #ifdef GC_DONT_EXPAND
 112   GC_bool GC_dont_expand = TRUE;
 113 #else
 114   GC_bool GC_dont_expand = FALSE;
 115 #endif
 116
 117 #ifndef GC_FREE_SPACE_DIVISOR
 118 # define GC_FREE_SPACE_DIVISOR 3 /* must be > 0 */
 119 #endif
 120
 121 word GC_free_space_divisor = GC_FREE_SPACE_DIVISOR;
 122
 123 extern GC_bool GC_collection_in_progress(void);
 124                 /* Collection is in progress, or was abandoned. */
 125
 126 int GC_CALLBACK GC_never_stop_func (void) { return(0); }
 127
 128 #ifndef GC_TIME_LIMIT
 129 # define GC_TIME_LIMIT 50  /* We try to keep pause times from exceeding  */
 130                            /* this by much. In milliseconds.             */
 131 #endif
 132
 133 unsigned long GC_time_limit = GC_TIME_LIMIT;
 134
 135 #ifndef NO_CLOCK
 136 STATIC CLOCK_TYPE GC_start_time;/* Time at which we stopped world.      */
 137                                 /* used only in GC_timeout_stop_func.   */
 138 #endif
 139
 140 STATIC int GC_n_attempts = 0;   /* Number of attempts at finishing      */
 141                                 /* collection within GC_time_limit.     */
 142
 143 #if defined(SMALL_CONFIG) || defined(NO_CLOCK)
 144 #   define GC_timeout_stop_func GC_never_stop_func
 145 #else
 146   STATIC int GC_CALLBACK GC_timeout_stop_func (void)
 147   {
 148     CLOCK_TYPE current_time;
 149     static unsigned count = 0;
 150     unsigned long time_diff;
 151
 152     if ((count++ & 3) != 0) return(0);
 153     GET_TIME(current_time);
 154     time_diff = MS_TIME_DIFF(current_time,GC_start_time);
 155     if (time_diff >= GC_time_limit) {
 156         if (GC_print_stats) {
 157             GC_log_printf(
 158                 "Abandoning stopped marking after %lu msecs (attempt %d)\n",
 159                 time_diff, GC_n_attempts);
 160         }
 161         return(1);
 162     }
 163     return(0);
 164   }
 165 #endif /* !SMALL_CONFIG */
 166
 167 /* Return the minimum number of words that must be allocated between    */
 168 /* collections to amortize the collection cost.                         */
 169 static word min_bytes_allocd(void)
 170 {
 171 #   ifdef THREADS
 172         /* We punt, for now. */
 173         signed_word stack_size = 10000;
 174 #   else
 175         int dummy;
 176         signed_word stack_size = (ptr_t)(&dummy) - GC_stackbottom;
 177 #   endif
 178     word total_root_size;           /* includes double stack size,      */
 179                                     /* since the stack is expensive     */
 180                                     /* to scan.                         */
 181     word scan_size;             /* Estimate of memory to be scanned     */
 182                                 /* during normal GC.                    */
 183
 184     if (stack_size < 0) stack_size = -stack_size;
 185     total_root_size = 2 * stack_size + GC_root_size;
 186     scan_size = 2 * GC_composite_in_use + GC_atomic_in_use/4
 187                 + total_root_size;
 188     if (TRUE_INCREMENTAL) {
 189         return scan_size / (2 * GC_free_space_divisor);
 190     } else {
 191         return scan_size / GC_free_space_divisor;
 192     }
 193 }
 194
 195 /* Return the number of bytes allocated, adjusted for explicit storage  */
 196 /* management, etc..  This number is used in deciding when to trigger   */
 197 /* collections.                                                         */
 198 STATIC word GC_adj_bytes_allocd(void)
 199 {
 200     signed_word result;
 201     signed_word expl_managed =
 202                 (signed_word)GC_non_gc_bytes
 203                 - (signed_word)GC_non_gc_bytes_at_gc;
 204
 205     /* Don't count what was explicitly freed, or newly allocated for    */
 206     /* explicit management.  Note that deallocating an explicitly       */
 207     /* managed object should not alter result, assuming the client      */
 208     /* is playing by the rules.                                         */
 209     result = (signed_word)GC_bytes_allocd
 210              + (signed_word)GC_bytes_dropped
 211              - (signed_word)GC_bytes_freed
 212              + (signed_word)GC_finalizer_bytes_freed
 213              - expl_managed;
 214     if (result > (signed_word)GC_bytes_allocd) {
 215         result = GC_bytes_allocd;
 216         /* probably client bug or unfortunate scheduling */
 217     }
 218     result += GC_bytes_finalized;
 219         /* We count objects enqueued for finalization as though they    */
 220         /* had been reallocated this round. Finalization is user        */
 221         /* visible progress.  And if we don't count this, we have       */
 222         /* stability problems for programs that finalize all objects.   */
 223     if (result < (signed_word)(GC_bytes_allocd >> 3)) {
 224         /* Always count at least 1/8 of the allocations.  We don't want */
 225         /* to collect too infrequently, since that would inhibit        */
 226         /* coalescing of free storage blocks.                           */
 227         /* This also makes us partially robust against client bugs.     */
 228         return(GC_bytes_allocd >> 3);
 229     } else {
 230         return(result);
 231     }
 232 }
 233
 234
 235 /* Clear up a few frames worth of garbage left at the top of the stack. */
 236 /* This is used to prevent us from accidentally treating garbage left   */
 237 /* on the stack by other parts of the collector as roots.  This         */
 238 /* differs from the code in misc.c, which actually tries to keep the    */
 239 /* stack clear of long-lived, client-generated garbage.                 */
 240 STATIC void GC_clear_a_few_frames(void)
 241 {
 242 #   ifndef CLEAR_NWORDS
 243 #     define CLEAR_NWORDS 64
 244 #   endif
 245     volatile word frames[CLEAR_NWORDS];
 246     int i;
 247
 248     for (i = 0; i < CLEAR_NWORDS; i++) frames[i] = 0;
 249 }
 250
 251 /* Heap size at which we need a collection to avoid expanding past      */
 252 /* limits used by blacklisting.                                         */
 253 static word GC_collect_at_heapsize = (word)(-1);
 254
 255 /* Have we allocated enough to amortize a collection? */
 256 GC_bool GC_should_collect(void)
 257 {
 258     static word last_min_bytes_allocd;
 259     static word last_gc_no;
 260     if (last_gc_no != GC_gc_no) {
 261       last_gc_no = GC_gc_no;
 262       last_min_bytes_allocd = min_bytes_allocd();
 263     }
 264     return(GC_adj_bytes_allocd() >= last_min_bytes_allocd
 265            || GC_heapsize >= GC_collect_at_heapsize);
 266 }
 267
 268
 269 STATIC void GC_notify_full_gc(void)
 270 {
 271     if (GC_start_call_back != (void (*) (void))0) {
 272         (*GC_start_call_back)();
 273     }
 274 }
 275
 276 STATIC GC_bool GC_is_full_gc = FALSE;
 277
 278 STATIC GC_bool GC_stopped_mark(GC_stop_func stop_func);
 279 STATIC void GC_finish_collection(void);
 280
 281 /*
 282  * Initiate a garbage collection if appropriate.
 283  * Choose judiciously
 284  * between partial, full, and stop-world collections.
 285  */
 286 STATIC void GC_maybe_gc(void)
 287 {
 288     static int n_partial_gcs = 0;
 289
 290     GC_ASSERT(I_HOLD_LOCK());
 291     if (GC_should_collect()) {
 292         if (!GC_incremental) {
 293             GC_gcollect_inner();
 294             n_partial_gcs = 0;
 295             return;
 296         } else {
 297 #         ifdef PARALLEL_MARK
 298             if (GC_parallel)
 299               GC_wait_for_reclaim();
 300 #         endif
 301           if (GC_need_full_gc || n_partial_gcs >= GC_full_freq) {
 302             if (GC_print_stats) {
 303                 GC_log_printf(
 304                   "***>Full mark for collection %lu after %ld allocd bytes\n",
 305                   (unsigned long)GC_gc_no+1,
 306                   (long)GC_bytes_allocd);
 307             }
 308             GC_promote_black_lists();
 309             (void)GC_reclaim_all((GC_stop_func)0, TRUE);
 310             GC_clear_marks();
 311             n_partial_gcs = 0;
 312             GC_notify_full_gc();
 313             GC_is_full_gc = TRUE;
 314           } else {
 315             n_partial_gcs++;
 316           }
 317         }
 318         /* We try to mark with the world stopped.       */
 319         /* If we run out of time, this turns into       */
 320         /* incremental marking.                 */
 321 #       ifndef NO_CLOCK
 322           if (GC_time_limit != GC_TIME_UNLIMITED) { GET_TIME(GC_start_time); }
 323 #       endif
 324         if (GC_stopped_mark(GC_time_limit == GC_TIME_UNLIMITED?
 325                             GC_never_stop_func : GC_timeout_stop_func)) {
 326 #           ifdef SAVE_CALL_CHAIN
 327                 GC_save_callers(GC_last_stack);
 328 #           endif
 329             GC_finish_collection();
 330         } else {
 331             if (!GC_is_full_gc) {
 332                 /* Count this as the first attempt */
 333                 GC_n_attempts++;
 334             }
 335         }
 336     }
 337 }
 338
 339
 340 /*
 341  * Stop the world garbage collection.  Assumes lock held. If stop_func is
 342  * not GC_never_stop_func then abort if stop_func returns TRUE.
 343  * Return TRUE if we successfully completed the collection.
 344  */
 345 GC_bool GC_try_to_collect_inner(GC_stop_func stop_func)
 346 {
 347 #   ifndef SMALL_CONFIG
 348       CLOCK_TYPE start_time = 0; /* initialized to prevent warning. */
 349       CLOCK_TYPE current_time;
 350 #   endif
 351     if (GC_dont_gc) return FALSE;
 352     if (GC_incremental && GC_collection_in_progress()) {
 353       if (GC_print_stats) {
 354         GC_log_printf(
 355             "GC_try_to_collect_inner: finishing collection in progress\n");
 356       }
 357       /* Just finish collection already in progress.    */
 358         while(GC_collection_in_progress()) {
 359             if (stop_func()) return(FALSE);
 360             GC_collect_a_little_inner(1);
 361         }
 362     }
 363     if (stop_func == GC_never_stop_func) GC_notify_full_gc();
 364 #   ifndef SMALL_CONFIG
 365       if (GC_print_stats) {
 366         GET_TIME(start_time);
 367         GC_log_printf("Initiating full world-stop collection!\n");
 368       }
 369 #   endif
 370     GC_promote_black_lists();
 371     /* Make sure all blocks have been reclaimed, so sweep routines      */
 372     /* don't see cleared mark bits.                                     */
 373     /* If we're guaranteed to finish, then this is unnecessary.         */
 374     /* In the find_leak case, we have to finish to guarantee that       */
 375     /* previously unmarked objects are not reported as leaks.           */
 376 #       ifdef PARALLEL_MARK
 377           if (GC_parallel)
 378             GC_wait_for_reclaim();
 379 #       endif
 380         if ((GC_find_leak || stop_func != GC_never_stop_func)
 381             && !GC_reclaim_all(stop_func, FALSE)) {
 382             /* Aborted.  So far everything is still consistent. */
 383             return(FALSE);
 384         }
 385     GC_invalidate_mark_state();  /* Flush mark stack.   */
 386     GC_clear_marks();
 387 #   ifdef SAVE_CALL_CHAIN
 388         GC_save_callers(GC_last_stack);
 389 #   endif
 390     GC_is_full_gc = TRUE;
 391     if (!GC_stopped_mark(stop_func)) {
 392       if (!GC_incremental) {
 393         /* We're partially done and have no way to complete or use      */
 394         /* current work.  Reestablish invariants as cheaply as          */
 395         /* possible.                                                    */
 396         GC_invalidate_mark_state();
 397         GC_unpromote_black_lists();
 398       } /* else we claim the world is already still consistent.  We'll  */
 399         /* finish incrementally.                                        */
 400       return(FALSE);
 401     }
 402     GC_finish_collection();
 403 #   ifndef SMALL_CONFIG
 404       if (GC_print_stats) {
 405         GET_TIME(current_time);
 406         GC_log_printf("Complete collection took %lu msecs\n",
 407                   MS_TIME_DIFF(current_time,start_time));
 408       }
 409 #   endif
 410     return(TRUE);
 411 }
 412
 413
 414
 415 /*
 416  * Perform n units of garbage collection work.  A unit is intended to touch
 417  * roughly GC_RATE pages.  Every once in a while, we do more than that.
 418  * This needs to be a fairly large number with our current incremental
 419  * GC strategy, since otherwise we allocate too much during GC, and the
 420  * cleanup gets expensive.
 421  */
 422 #ifndef GC_RATE
 423 # define GC_RATE 10
 424 #endif
 425 #ifndef MAX_PRIOR_ATTEMPTS
 426 # define MAX_PRIOR_ATTEMPTS 1
 427 #endif
 428         /* Maximum number of prior attempts at world stop marking       */
 429         /* A value of 1 means that we finish the second time, no matter */
 430         /* how long it takes.  Doesn't count the initial root scan      */
 431         /* for a full GC.                                               */
 432
 433 STATIC int GC_deficit = 0;/* The number of extra calls to GC_mark_some  */
 434                           /* that we have made.                         */
 435
 436 void GC_collect_a_little_inner(int n)
 437 {
 438     int i;
 439
 440     if (GC_dont_gc) return;
 441     if (GC_incremental && GC_collection_in_progress()) {
 442         for (i = GC_deficit; i < GC_RATE*n; i++) {
 443             if (GC_mark_some((ptr_t)0)) {
 444                 /* Need to finish a collection */
 445 #               ifdef SAVE_CALL_CHAIN
 446                     GC_save_callers(GC_last_stack);
 447 #               endif
 448 #               ifdef PARALLEL_MARK
 449                     if (GC_parallel)
 450                       GC_wait_for_reclaim();
 451 #               endif
 452                 if (GC_n_attempts < MAX_PRIOR_ATTEMPTS
 453                     && GC_time_limit != GC_TIME_UNLIMITED) {
 454 #                 ifndef NO_CLOCK
 455                     GET_TIME(GC_start_time);
 456 #                 endif
 457                   if (!GC_stopped_mark(GC_timeout_stop_func)) {
 458                     GC_n_attempts++;
 459                     break;
 460                   }
 461                 } else {
 462                   (void)GC_stopped_mark(GC_never_stop_func);
 463                 }
 464                 GC_finish_collection();
 465                 break;
 466             }
 467         }
 468         if (GC_deficit > 0) GC_deficit -= GC_RATE*n;
 469         if (GC_deficit < 0) GC_deficit = 0;
 470     } else {
 471         GC_maybe_gc();
 472     }
 473 }
 474
 475 GC_API int GC_CALL GC_collect_a_little(void)
 476 {
 477     int result;
 478     DCL_LOCK_STATE;
 479
 480     LOCK();
 481     GC_collect_a_little_inner(1);
 482     result = (int)GC_collection_in_progress();
 483     UNLOCK();
 484     if (!result && GC_debugging_started) GC_print_all_smashed();
 485     return(result);
 486 }
 487
 488 # if !defined(REDIRECT_MALLOC) && (defined(MSWIN32) || defined(MSWINCE))
 489   void GC_add_current_malloc_heap(void);
 490 # endif
 491 #ifdef MAKE_BACK_GRAPH
 492   void GC_build_back_graph(void);
 493 #endif
 494
 495 #ifndef SMALL_CONFIG
 496   /* Variables for world-stop average delay time statistic computation. */
 497   /* "divisor" is incremented every world-stop and halved when reached  */
 498   /* its maximum (or upon "total_time" oveflow).                        */
 499   STATIC unsigned world_stopped_total_time = 0;
 500   STATIC unsigned world_stopped_total_divisor = 0;
 501 # ifndef MAX_TOTAL_TIME_DIVISOR
 502     /* We shall not use big values here (so "outdated" delay time       */
 503     /* values would have less impact on "average" delay time value than */
 504     /* newer ones).                                                     */
 505 #   define MAX_TOTAL_TIME_DIVISOR 1000
 506 # endif
 507 #endif
 508
 509 /*
 510  * Assumes lock is held.  We stop the world and mark from all roots.
 511  * If stop_func() ever returns TRUE, we may fail and return FALSE.
 512  * Increment GC_gc_no if we succeed.
 513  */
 514 STATIC GC_bool GC_stopped_mark(GC_stop_func stop_func)
 515 {
 516     unsigned i;
 517     int dummy;
 518 #   ifndef SMALL_CONFIG
 519       CLOCK_TYPE start_time = 0; /* initialized to prevent warning. */
 520       CLOCK_TYPE current_time;
 521 #   endif
 522
 523 #   if !defined(REDIRECT_MALLOC) && (defined(MSWIN32) || defined(MSWINCE))
 524         GC_add_current_malloc_heap();
 525 #   endif
 526 #   if defined(REGISTER_LIBRARIES_EARLY)
 527         GC_cond_register_dynamic_libraries();
 528 #   endif
 529
 530 #   ifndef SMALL_CONFIG
 531       if (GC_print_stats)
 532         GET_TIME(start_time);
 533 #   endif
 534
 535     STOP_WORLD();
 536     IF_THREADS(GC_world_stopped = TRUE);
 537     if (GC_print_stats) {
 538         /* Output blank line for convenience here */
 539         GC_log_printf(
 540               "\n--> Marking for collection %lu after %lu allocated bytes\n",
 541               (unsigned long)GC_gc_no + 1, (unsigned long) GC_bytes_allocd);
 542     }
 543 #   ifdef MAKE_BACK_GRAPH
 544       if (GC_print_back_height) {
 545         GC_build_back_graph();
 546       }
 547 #   endif
 548
 549     /* Mark from all roots.  */
 550         /* Minimize junk left in my registers and on the stack */
 551             GC_clear_a_few_frames();
 552             GC_noop(0,0,0,0,0,0);
 553         GC_initiate_gc();
 554         for(i = 0;;i++) {
 555             if ((*stop_func)()) {
 556                     if (GC_print_stats) {
 557                         GC_log_printf("Abandoned stopped marking after "
 558                                 "%u iterations\n", i);
 559                     }
 560                     GC_deficit = i; /* Give the mutator a chance. */
 561                     IF_THREADS(GC_world_stopped = FALSE);
 562                     START_WORLD();
 563                     return(FALSE);
 564             }
 565             if (GC_mark_some((ptr_t)(&dummy))) break;
 566         }
 567
 568     GC_gc_no++;
 569     if (GC_print_stats) {
 570       GC_log_printf(
 571              "Collection %lu reclaimed %ld bytes ---> heapsize = %lu bytes\n",
 572              (unsigned long)(GC_gc_no - 1), (long)GC_bytes_found,
 573              (unsigned long)GC_heapsize);
 574         /* Printf arguments may be pushed in funny places.  Clear the   */
 575         /* space.                                                       */
 576       GC_log_printf("");
 577     }
 578
 579     /* Check all debugged objects for consistency */
 580         if (GC_debugging_started) {
 581             (*GC_check_heap)();
 582         }
 583
 584     IF_THREADS(GC_world_stopped = FALSE);
 585     START_WORLD();
 586 #   ifndef SMALL_CONFIG
 587       if (GC_print_stats) {
 588         unsigned long time_diff;
 589         unsigned total_time, divisor;
 590         GET_TIME(current_time);
 591         time_diff = MS_TIME_DIFF(current_time,start_time);
 592
 593         /* Compute new world-stop delay total time */
 594         total_time = world_stopped_total_time;
 595         divisor = world_stopped_total_divisor;
 596         if ((int)total_time < 0 || divisor >= MAX_TOTAL_TIME_DIVISOR) {
 597           /* Halve values if overflow occurs */
 598           total_time >>= 1;
 599           divisor >>= 1;
 600         }
 601         total_time += time_diff < (((unsigned)-1) >> 1) ?
 602                         (unsigned)time_diff : ((unsigned)-1) >> 1;
 603         /* Update old world_stopped_total_time and its divisor */
 604         world_stopped_total_time = total_time;
 605         world_stopped_total_divisor = ++divisor;
 606
 607         GC_ASSERT(divisor != 0);
 608         GC_log_printf(
 609                 "World-stopped marking took %lu msecs (%lu in average)\n",
 610                 time_diff, total_time / divisor);
 611       }
 612 #   endif
 613     return(TRUE);
 614 }
 615
 616 /* Set all mark bits for the free list whose first entry is q   */
 617 void GC_set_fl_marks(ptr_t q)
 618 {
 619    ptr_t p;
 620    struct hblk * h, * last_h = 0;
 621    hdr *hhdr;  /* gcc "might be uninitialized" warning is bogus. */
 622    IF_PER_OBJ(size_t sz;)
 623    unsigned bit_no;
 624
 625    for (p = q; p != 0; p = obj_link(p)){
 626         h = HBLKPTR(p);
 627         if (h != last_h) {
 628           last_h = h;
 629           hhdr = HDR(h);
 630           IF_PER_OBJ(sz = hhdr->hb_sz;)
 631         }
 632         bit_no = MARK_BIT_NO((ptr_t)p - (ptr_t)h, sz);
 633         if (!mark_bit_from_hdr(hhdr, bit_no)) {
 634           set_mark_bit_from_hdr(hhdr, bit_no);
 635           ++hhdr -> hb_n_marks;
 636         }
 637    }
 638 }
 639
 640 #ifdef GC_ASSERTIONS
 641 /* Check that all mark bits for the free list whose first entry is q    */
 642 /* are set.                                                             */
 643 void GC_check_fl_marks(ptr_t q)
 644 {
 645    ptr_t p;
 646
 647    for (p = q; p != 0; p = obj_link(p)){
 648         if (!GC_is_marked(p)) {
 649             GC_err_printf("Unmarked object %p on list %p\n", p, q);
 650             ABORT("Unmarked local free list entry.");
 651         }
 652    }
 653 }
 654 #endif
 655
 656 /* Clear all mark bits for the free list whose first entry is q */
 657 /* Decrement GC_bytes_found by number of bytes on free list.    */
 658 STATIC void GC_clear_fl_marks(ptr_t q)
 659 {
 660    ptr_t p;
 661    struct hblk * h, * last_h = 0;
 662    hdr *hhdr;
 663    size_t sz;
 664    unsigned bit_no;
 665
 666    for (p = q; p != 0; p = obj_link(p)){
 667         h = HBLKPTR(p);
 668         if (h != last_h) {
 669           last_h = h;
 670           hhdr = HDR(h);
 671           sz = hhdr->hb_sz;  /* Normally set only once. */
 672         }
 673         bit_no = MARK_BIT_NO((ptr_t)p - (ptr_t)h, sz);
 674         if (mark_bit_from_hdr(hhdr, bit_no)) {
 675           size_t n_marks = hhdr -> hb_n_marks - 1;
 676           clear_mark_bit_from_hdr(hhdr, bit_no);
 677 #         ifdef PARALLEL_MARK
 678             /* Appr. count, don't decrement to zero! */
 679             if (0 != n_marks || !GC_parallel) {
 680               hhdr -> hb_n_marks = n_marks;
 681             }
 682 #         else
 683             hhdr -> hb_n_marks = n_marks;
 684 #         endif
 685         }
 686         GC_bytes_found -= sz;
 687    }
 688 }
 689
 690 #if defined(GC_ASSERTIONS) && defined(THREADS) && defined(THREAD_LOCAL_ALLOC)
 691 extern void GC_check_tls(void);
 692 #endif
 693
 694 #ifdef MAKE_BACK_GRAPH
 695 void GC_traverse_back_graph(void);
 696 #endif
 697
 698 /* Finish up a collection.  Assumes mark bits are consistent, lock is   */
 699 /* held, but the world is otherwise running.                            */
 700 STATIC void GC_finish_collection(void)
 701 {
 702 #   ifndef SMALL_CONFIG
 703       CLOCK_TYPE start_time = 0; /* initialized to prevent warning. */
 704       CLOCK_TYPE finalize_time = 0;
 705       CLOCK_TYPE done_time;
 706 #   endif
 707
 708 #   if defined(GC_ASSERTIONS) && defined(THREADS) \
 709        && defined(THREAD_LOCAL_ALLOC) && !defined(DBG_HDRS_ALL)
 710         /* Check that we marked some of our own data.           */
 711         /* FIXME: Add more checks.                              */
 712         GC_check_tls();
 713 #   endif
 714
 715 #   ifndef SMALL_CONFIG
 716       if (GC_print_stats)
 717         GET_TIME(start_time);
 718 #   endif
 719
 720     GC_bytes_found = 0;
 721 #   if defined(LINUX) && defined(__ELF__) && !defined(SMALL_CONFIG)
 722         if (getenv("GC_PRINT_ADDRESS_MAP") != 0) {
 723           GC_print_address_map();
 724         }
 725 #   endif
 726     COND_DUMP;
 727     if (GC_find_leak) {
 728       /* Mark all objects on the free list.  All objects should be */
 729       /* marked when we're done.                                   */
 730         {
 731           word size;            /* current object size          */
 732           unsigned kind;
 733           ptr_t q;
 734
 735           for (kind = 0; kind < GC_n_kinds; kind++) {
 736             for (size = 1; size <= MAXOBJGRANULES; size++) {
 737               q = GC_obj_kinds[kind].ok_freelist[size];
 738               if (q != 0) GC_set_fl_marks(q);
 739             }
 740           }
 741         }
 742         GC_start_reclaim(TRUE);
 743           /* The above just checks; it doesn't really reclaim anything. */
 744     }
 745
 746     GC_finalize();
 747 #   ifdef STUBBORN_ALLOC
 748       GC_clean_changing_list();
 749 #   endif
 750
 751 #   ifndef SMALL_CONFIG
 752       if (GC_print_stats)
 753         GET_TIME(finalize_time);
 754 #   endif
 755
 756     if (GC_print_back_height) {
 757 #     ifdef MAKE_BACK_GRAPH
 758         GC_traverse_back_graph();
 759 #     else
 760 #       ifndef SMALL_CONFIG
 761           GC_err_printf("Back height not available: "
 762                         "Rebuild collector with -DMAKE_BACK_GRAPH\n");
 763 #       endif
 764 #     endif
 765     }
 766
 767     /* Clear free list mark bits, in case they got accidentally marked   */
 768     /* (or GC_find_leak is set and they were intentionally marked).      */
 769     /* Also subtract memory remaining from GC_bytes_found count.         */
 770     /* Note that composite objects on free list are cleared.             */
 771     /* Thus accidentally marking a free list is not a problem;  only     */
 772     /* objects on the list itself will be marked, and that's fixed here. */
 773       {
 774         word size;              /* current object size          */
 775         ptr_t q;        /* pointer to current object    */
 776         unsigned kind;
 777
 778         for (kind = 0; kind < GC_n_kinds; kind++) {
 779           for (size = 1; size <= MAXOBJGRANULES; size++) {
 780             q = GC_obj_kinds[kind].ok_freelist[size];
 781             if (q != 0) GC_clear_fl_marks(q);
 782           }
 783         }
 784       }
 785
 786
 787     if (GC_print_stats == VERBOSE)
 788         GC_log_printf("Bytes recovered before sweep - f.l. count = %ld\n",
 789                   (long)GC_bytes_found);
 790
 791     /* Reconstruct free lists to contain everything not marked */
 792         GC_start_reclaim(FALSE);
 793         if (GC_print_stats) {
 794           GC_log_printf("Heap contains %lu pointer-containing "
 795                         "+ %lu pointer-free reachable bytes\n",
 796                         (unsigned long)GC_composite_in_use,
 797                         (unsigned long)GC_atomic_in_use);
 798         }
 799         if (GC_is_full_gc)  {
 800             GC_used_heap_size_after_full = USED_HEAP_SIZE;
 801             GC_need_full_gc = FALSE;
 802         } else {
 803             GC_need_full_gc =
 804                  USED_HEAP_SIZE - GC_used_heap_size_after_full
 805                  > min_bytes_allocd();
 806         }
 807
 808     if (GC_print_stats == VERBOSE) {
 809 #       ifdef USE_MUNMAP
 810           GC_log_printf("Immediately reclaimed %ld bytes in heap"
 811                         " of size %lu bytes (%lu unmapped)\n",
 812                         (long)GC_bytes_found, (unsigned long)GC_heapsize,
 813                         (unsigned long)GC_unmapped_bytes);
 814 #       else
 815           GC_log_printf("Immediately reclaimed %ld bytes in heap"
 816                         " of size %lu bytes\n",
 817                         (long)GC_bytes_found, (unsigned long)GC_heapsize);
 818 #       endif
 819     }
 820
 821     /* Reset or increment counters for next cycle */
 822       GC_n_attempts = 0;
 823       GC_is_full_gc = FALSE;
 824       GC_bytes_allocd_before_gc += GC_bytes_allocd;
 825       GC_non_gc_bytes_at_gc = GC_non_gc_bytes;
 826       GC_bytes_allocd = 0;
 827       GC_bytes_dropped = 0;
 828       GC_bytes_freed = 0;
 829       GC_finalizer_bytes_freed = 0;
 830
 831 #   ifdef USE_MUNMAP
 832       GC_unmap_old();
 833 #   endif
 834
 835 #   ifndef SMALL_CONFIG
 836       if (GC_print_stats) {
 837         GET_TIME(done_time);
 838         GC_log_printf("Finalize + initiate sweep took %lu + %lu msecs\n",
 839                       MS_TIME_DIFF(finalize_time,start_time),
 840                       MS_TIME_DIFF(done_time,finalize_time));
 841       }
 842 #   endif
 843 }
 844
 845 /* Externally callable routine to invoke full, stop-world collection */
 846 GC_API int GC_CALL GC_try_to_collect(GC_stop_func stop_func)
 847 {
 848     int result;
 849     DCL_LOCK_STATE;
 850
 851     if (!GC_is_initialized) GC_init();
 852     GC_ASSERT(stop_func != 0);
 853     if (GC_debugging_started) GC_print_all_smashed();
 854     GC_INVOKE_FINALIZERS();
 855     LOCK();
 856     ENTER_GC();
 857     /* Minimize junk left in my registers */
 858       GC_noop(0,0,0,0,0,0);
 859     result = (int)GC_try_to_collect_inner(stop_func);
 860     EXIT_GC();
 861     UNLOCK();
 862     if(result) {
 863         if (GC_debugging_started) GC_print_all_smashed();
 864         GC_INVOKE_FINALIZERS();
 865     }
 866     return(result);
 867 }
 868
 869 GC_API void GC_CALL GC_gcollect(void)
 870 {
 871     (void)GC_try_to_collect(GC_never_stop_func);
 872     if (GC_have_errors) GC_print_all_errors();
 873 }
 874
 875 word GC_n_heap_sects = 0;       /* Number of sections currently in heap. */
 876
 877 #ifdef USE_PROC_FOR_LIBRARIES
 878   word GC_n_memory = 0;         /* Number of GET_MEM allocated memory   */
 879                                 /* sections.                            */
 880 #endif
 881
 882 #ifdef USE_PROC_FOR_LIBRARIES
 883   /* Add HBLKSIZE aligned, GET_MEM-generated block to GC_our_memory. */
 884   /* Defined to do nothing if USE_PROC_FOR_LIBRARIES not set.       */
 885   void GC_add_to_our_memory(ptr_t p, size_t bytes)
 886   {
 887     if (0 == p) return;
 888     GC_our_memory[GC_n_memory].hs_start = p;
 889     GC_our_memory[GC_n_memory].hs_bytes = bytes;
 890     GC_n_memory++;
 891   }
 892 #endif
 893 /*
 894  * Use the chunk of memory starting at p of size bytes as part of the heap.
 895  * Assumes p is HBLKSIZE aligned, and bytes is a multiple of HBLKSIZE.
 896  */
 897 void GC_add_to_heap(struct hblk *p, size_t bytes)
 898 {
 899     hdr * phdr;
 900     word endp;
 901
 902     if (GC_n_heap_sects >= MAX_HEAP_SECTS) {
 903         ABORT("Too many heap sections: Increase MAXHINCR or MAX_HEAP_SECTS");
 904     }
 905     while ((word)p <= HBLKSIZE) {
 906         /* Can't handle memory near address zero. */
 907         ++p;
 908         bytes -= HBLKSIZE;
 909         if (0 == bytes) return;
 910     }
 911     endp = (word)p + bytes;
 912     if (endp <= (word)p) {
 913         /* Address wrapped. */
 914         bytes -= HBLKSIZE;
 915         if (0 == bytes) return;
 916         endp -= HBLKSIZE;
 917     }
 918     phdr = GC_install_header(p);
 919     if (0 == phdr) {
 920         /* This is extremely unlikely. Can't add it.  This will         */
 921         /* almost certainly result in a 0 return from the allocator,    */
 922         /* which is entirely appropriate.                               */
 923         return;
 924     }
 925     GC_ASSERT(endp > (word)p && endp == (word)p + bytes);
 926     GC_heap_sects[GC_n_heap_sects].hs_start = (ptr_t)p;
 927     GC_heap_sects[GC_n_heap_sects].hs_bytes = bytes;
 928     GC_n_heap_sects++;
 929     phdr -> hb_sz = bytes;
 930     phdr -> hb_flags = 0;
 931     GC_freehblk(p);
 932     GC_heapsize += bytes;
 933     if ((ptr_t)p <= (ptr_t)GC_least_plausible_heap_addr
 934         || GC_least_plausible_heap_addr == 0) {
 935         GC_least_plausible_heap_addr = (void *)((ptr_t)p - sizeof(word));
 936                 /* Making it a little smaller than necessary prevents   */
 937                 /* us from getting a false hit from the variable        */
 938                 /* itself.  There's some unintentional reflection       */
 939                 /* here.                                                */
 940     }
 941     if ((ptr_t)p + bytes >= (ptr_t)GC_greatest_plausible_heap_addr) {
 942         GC_greatest_plausible_heap_addr = (void *)endp;
 943     }
 944 }
 945
 946 # if !defined(NO_DEBUGGING)
 947 void GC_print_heap_sects(void)
 948 {
 949     unsigned i;
 950
 951     GC_printf("Total heap size: %lu\n", (unsigned long) GC_heapsize);
 952     for (i = 0; i < GC_n_heap_sects; i++) {
 953         ptr_t start = GC_heap_sects[i].hs_start;
 954         size_t len = GC_heap_sects[i].hs_bytes;
 955         struct hblk *h;
 956         unsigned nbl = 0;
 957
 958         for (h = (struct hblk *)start; h < (struct hblk *)(start + len); h++) {
 959             if (GC_is_black_listed(h, HBLKSIZE)) nbl++;
 960         }
 961         GC_printf("Section %d from %p to %p %lu/%lu blacklisted\n",
 962                   i, start, start + len,
 963                   (unsigned long)nbl, (unsigned long)(len/HBLKSIZE));
 964     }
 965 }
 966 # endif
 967
 968 void * GC_least_plausible_heap_addr = (void *)ONES;
 969 void * GC_greatest_plausible_heap_addr = 0;
 970
 971 static INLINE word GC_max(word x, word y)
 972 {
 973     return(x > y? x : y);
 974 }
 975
 976 static INLINE word GC_min(word x, word y)
 977 {
 978     return(x < y? x : y);
 979 }
 980
 981 GC_API void GC_CALL GC_set_max_heap_size(GC_word n)
 982 {
 983     GC_max_heapsize = n;
 984 }
 985
 986 GC_word GC_max_retries = 0;
 987
 988 /*
 989  * this explicitly increases the size of the heap.  It is used
 990  * internally, but may also be invoked from GC_expand_hp by the user.
 991  * The argument is in units of HBLKSIZE.
 992  * Tiny values of n are rounded up.
 993  * Returns FALSE on failure.
 994  */
 995 GC_bool GC_expand_hp_inner(word n)
 996 {
 997     word bytes;
 998     struct hblk * space;
 999     word expansion_slop;        /* Number of bytes by which we expect the */
1000                                 /* heap to expand soon.                   */
1001
1002     if (n < MINHINCR) n = MINHINCR;
1003     bytes = n * HBLKSIZE;
1004     /* Make sure bytes is a multiple of GC_page_size */
1005       {
1006         word mask = GC_page_size - 1;
1007         bytes += mask;
1008         bytes &= ~mask;
1009       }
1010
1011     if (GC_max_heapsize != 0 && GC_heapsize + bytes > GC_max_heapsize) {
1012         /* Exceeded self-imposed limit */
1013         return(FALSE);
1014     }
1015     space = GET_MEM(bytes);
1016     GC_add_to_our_memory((ptr_t)space, bytes);
1017     if( space == 0 ) {
1018         if (GC_print_stats) {
1019             GC_log_printf("Failed to expand heap by %ld bytes\n",
1020                           (unsigned long)bytes);
1021         }
1022         return(FALSE);
1023     }
1024     if (GC_print_stats) {
1025         GC_log_printf("Increasing heap size by %lu after %lu allocated bytes\n",
1026                       (unsigned long)bytes,
1027                       (unsigned long)GC_bytes_allocd);
1028     }
1029     /* Adjust heap limits generously for blacklisting to work better.   */
1030     /* GC_add_to_heap performs minimal adjustment needed for            */
1031     /* correctness.                                                     */
1032     expansion_slop = min_bytes_allocd() + 4*MAXHINCR*HBLKSIZE;
1033     if ((GC_last_heap_addr == 0 && !((word)space & SIGNB))
1034         || (GC_last_heap_addr != 0 && GC_last_heap_addr < (ptr_t)space)) {
1035         /* Assume the heap is growing up */
1036         word new_limit = (word)space + bytes + expansion_slop;
1037         if (new_limit > (word)space) {
1038           GC_greatest_plausible_heap_addr =
1039             (void *)GC_max((word)GC_greatest_plausible_heap_addr,
1040                            (word)new_limit);
1041         }
1042     } else {
1043         /* Heap is growing down */
1044         word new_limit = (word)space - expansion_slop;
1045         if (new_limit < (word)space) {
1046           GC_least_plausible_heap_addr =
1047             (void *)GC_min((word)GC_least_plausible_heap_addr,
1048                            (word)space - expansion_slop);
1049         }
1050     }
1051     GC_prev_heap_addr = GC_last_heap_addr;
1052     GC_last_heap_addr = (ptr_t)space;
1053     GC_add_to_heap(space, bytes);
1054     /* Force GC before we are likely to allocate past expansion_slop */
1055       GC_collect_at_heapsize =
1056          GC_heapsize + expansion_slop - 2*MAXHINCR*HBLKSIZE;
1057 #     if defined(LARGE_CONFIG)
1058         if (GC_collect_at_heapsize < GC_heapsize /* wrapped */)
1059          GC_collect_at_heapsize = (word)(-1);
1060 #     endif
1061     return(TRUE);
1062 }
1063
1064 /* Really returns a bool, but it's externally visible, so that's clumsy. */
1065 /* Arguments is in bytes.                                               */
1066 GC_API int GC_CALL GC_expand_hp(size_t bytes)
1067 {
1068     int result;
1069     DCL_LOCK_STATE;
1070
1071     LOCK();
1072     if (!GC_is_initialized) GC_init_inner();
1073     result = (int)GC_expand_hp_inner(divHBLKSZ((word)bytes));
1074     if (result) GC_requested_heapsize += bytes;
1075     UNLOCK();
1076     return(result);
1077 }
1078
1079 unsigned GC_fail_count = 0;
1080                         /* How many consecutive GC/expansion failures?  */
1081                         /* Reset by GC_allochblk.                       */
1082
1083 GC_bool GC_collect_or_expand(word needed_blocks, GC_bool ignore_off_page)
1084 {
1085     if (!GC_incremental && !GC_dont_gc &&
1086         ((GC_dont_expand && GC_bytes_allocd > 0) || GC_should_collect())) {
1087       GC_gcollect_inner();
1088     } else {
1089       word blocks_to_get = GC_heapsize/(HBLKSIZE*GC_free_space_divisor)
1090                            + needed_blocks;
1091
1092       if (blocks_to_get > MAXHINCR) {
1093           word slop;
1094
1095           /* Get the minimum required to make it likely that we         */
1096           /* can satisfy the current request in the presence of black-  */
1097           /* listing.  This will probably be more than MAXHINCR.        */
1098           if (ignore_off_page) {
1099               slop = 4;
1100           } else {
1101               slop = 2*divHBLKSZ(BL_LIMIT);
1102               if (slop > needed_blocks) slop = needed_blocks;
1103           }
1104           if (needed_blocks + slop > MAXHINCR) {
1105               blocks_to_get = needed_blocks + slop;
1106           } else {
1107               blocks_to_get = MAXHINCR;
1108           }
1109       }
1110       if (!GC_expand_hp_inner(blocks_to_get)
1111         && !GC_expand_hp_inner(needed_blocks)) {
1112         if (GC_fail_count++ < GC_max_retries) {
1113             WARN("Out of Memory!  Trying to continue ...\n", 0);
1114             GC_gcollect_inner();
1115         } else {
1116 #           if !defined(AMIGA) || !defined(GC_AMIGA_FASTALLOC)
1117               WARN("Out of Memory!  Returning NIL!\n", 0);
1118 #           endif
1119             return(FALSE);
1120         }
1121       } else {
1122           if (GC_fail_count && GC_print_stats) {
1123               GC_printf("Memory available again ...\n");
1124           }
1125       }
1126     }
1127     return(TRUE);
1128 }
1129
1130 /*
1131  * Make sure the object free list for size gran (in granules) is not empty.
1132  * Return a pointer to the first object on the free list.
1133  * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
1134  * Assumes we hold the allocator lock.
1135  */
1136 ptr_t GC_allocobj(size_t gran, int kind)
1137 {
1138     void ** flh = &(GC_obj_kinds[kind].ok_freelist[gran]);
1139     GC_bool tried_minor = FALSE;
1140
1141     if (gran == 0) return(0);
1142
1143     while (*flh == 0) {
1144       ENTER_GC();
1145       /* Do our share of marking work */
1146         if(TRUE_INCREMENTAL) GC_collect_a_little_inner(1);
1147       /* Sweep blocks for objects of this size */
1148         GC_continue_reclaim(gran, kind);
1149       EXIT_GC();
1150       if (*flh == 0) {
1151         GC_new_hblk(gran, kind);
1152       }
1153       if (*flh == 0) {
1154         ENTER_GC();
1155         if (GC_incremental && GC_time_limit == GC_TIME_UNLIMITED
1156             && ! tried_minor ) {
1157             GC_collect_a_little_inner(1);
1158             tried_minor = TRUE;
1159         } else {
1160           if (!GC_collect_or_expand((word)1,FALSE)) {
1161             EXIT_GC();
1162             return(0);
1163           }
1164         }
1165         EXIT_GC();
1166       }
1167     }
1168     /* Successful allocation; reset failure count.      */
1169     GC_fail_count = 0;
1170
1171     return(*flh);
1172 }