granicus.if.org Git - gc/blob - 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  * Copyright (c) 2008-2019 Ivan Maidanski
   7  *
   8  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   9  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  10  *
  11  * Permission is hereby granted to use or copy this program
  12  * for any purpose,  provided the above notices are retained on all copies.
  13  * Permission to modify the code and to distribute modified code is granted,
  14  * provided the above notices are retained, and a notice that the code was
  15  * modified is included with the above copyright notice.
  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 # if !defined(SN_TARGET_ORBIS) && !defined(SN_TARGET_PSP2) \
  25      && !defined(__CC_ARM)
  26 #   include <sys/types.h>
  27 # endif
  28 #endif
  29
  30 /*
  31  * Separate free lists are maintained for different sized objects
  32  * up to MAXOBJBYTES.
  33  * The call GC_allocobj(i,k) ensures that the freelist for
  34  * kind k objects of size i points to a non-empty
  35  * free list. It returns a pointer to the first entry on the free list.
  36  * In a single-threaded world, GC_allocobj may be called to allocate
  37  * an object of small size lb (and NORMAL kind) as follows
  38  * (GC_generic_malloc_inner is a wrapper over GC_allocobj which also
  39  * fills in GC_size_map if needed):
  40  *
  41  *   lg = GC_size_map[lb];
  42  *   op = GC_objfreelist[lg];
  43  *   if (NULL == op) {
  44  *     op = GC_generic_malloc_inner(lb, NORMAL);
  45  *   } else {
  46  *     GC_objfreelist[lg] = obj_link(op);
  47  *     GC_bytes_allocd += GRANULES_TO_BYTES((word)lg);
  48  *   }
  49  *
  50  * Note that this is very fast if the free list is non-empty; it should
  51  * only involve the execution of 4 or 5 simple instructions.
  52  * All composite objects on freelists are cleared, except for
  53  * their first word.
  54  */
  55
  56 /*
  57  * The allocator uses GC_allochblk to allocate large chunks of objects.
  58  * These chunks all start on addresses which are multiples of
  59  * HBLKSZ.   Each allocated chunk has an associated header,
  60  * which can be located quickly based on the address of the chunk.
  61  * (See headers.c for details.)
  62  * This makes it possible to check quickly whether an
  63  * arbitrary address corresponds to an object administered by the
  64  * allocator.
  65  */
  66
  67 word GC_non_gc_bytes = 0;  /* Number of bytes not intended to be collected */
  68
  69 word GC_gc_no = 0;
  70
  71 #ifndef NO_CLOCK
  72   static unsigned long full_gc_total_time = 0; /* in ms, may wrap */
  73   static GC_bool measure_performance = FALSE;
  74                 /* Do performance measurements if set to true (e.g.,    */
  75                 /* accumulation of the total time of full collections). */
  76
  77   GC_API void GC_CALL GC_start_performance_measurement(void)
  78   {
  79     measure_performance = TRUE;
  80   }
  81
  82   GC_API unsigned long GC_CALL GC_get_full_gc_total_time(void)
  83   {
  84     return full_gc_total_time;
  85   }
  86 #endif /* !NO_CLOCK */
  87
  88 #ifndef GC_DISABLE_INCREMENTAL
  89   GC_INNER GC_bool GC_incremental = FALSE; /* By default, stop the world. */
  90 #endif
  91
  92 GC_API int GC_CALL GC_is_incremental_mode(void)
  93 {
  94   return (int)GC_incremental;
  95 }
  96
  97 #ifdef THREADS
  98   int GC_parallel = FALSE;      /* By default, parallel GC is off.      */
  99 #endif
 100
 101 #if defined(GC_FULL_FREQ) && !defined(CPPCHECK)
 102   int GC_full_freq = GC_FULL_FREQ;
 103 #else
 104   int GC_full_freq = 19;   /* Every 20th collection is a full   */
 105                            /* collection, whether we need it    */
 106                            /* or not.                           */
 107 #endif
 108
 109 STATIC GC_bool GC_need_full_gc = FALSE;
 110                            /* Need full GC do to heap growth.   */
 111
 112 #ifdef THREAD_LOCAL_ALLOC
 113   GC_INNER GC_bool GC_world_stopped = FALSE;
 114 #endif
 115
 116 STATIC word GC_used_heap_size_after_full = 0;
 117
 118 /* GC_copyright symbol is externally visible. */
 119 EXTERN_C_BEGIN
 120 extern const char * const GC_copyright[];
 121 EXTERN_C_END
 122 const char * const GC_copyright[] =
 123 {"Copyright 1988, 1989 Hans-J. Boehm and Alan J. Demers ",
 124 "Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved. ",
 125 "Copyright (c) 1996-1998 by Silicon Graphics.  All rights reserved. ",
 126 "Copyright (c) 1999-2009 by Hewlett-Packard Company.  All rights reserved. ",
 127 "Copyright (c) 2008-2019 Ivan Maidanski ",
 128 "THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY",
 129 " EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.",
 130 "See source code for details." };
 131
 132 /* Version macros are now defined in gc_version.h, which is included by */
 133 /* gc.h, which is included by gc_priv.h.                                */
 134 #ifndef GC_NO_VERSION_VAR
 135   EXTERN_C_BEGIN
 136   extern const unsigned GC_version;
 137   EXTERN_C_END
 138   const unsigned GC_version = ((GC_VERSION_MAJOR << 16) |
 139                         (GC_VERSION_MINOR << 8) | GC_VERSION_MICRO);
 140 #endif
 141
 142 GC_API unsigned GC_CALL GC_get_version(void)
 143 {
 144   return (GC_VERSION_MAJOR << 16) | (GC_VERSION_MINOR << 8) |
 145           GC_VERSION_MICRO;
 146 }
 147
 148 /* some more variables */
 149
 150 #ifdef GC_DONT_EXPAND
 151   int GC_dont_expand = TRUE;
 152 #else
 153   int GC_dont_expand = FALSE;
 154 #endif
 155
 156 #if defined(GC_FREE_SPACE_DIVISOR) && !defined(CPPCHECK)
 157   word GC_free_space_divisor = GC_FREE_SPACE_DIVISOR; /* must be > 0 */
 158 #else
 159   word GC_free_space_divisor = 3;
 160 #endif
 161
 162 GC_INNER int GC_CALLBACK GC_never_stop_func(void)
 163 {
 164   return(0);
 165 }
 166
 167 #if defined(GC_TIME_LIMIT) && !defined(CPPCHECK)
 168   unsigned long GC_time_limit = GC_TIME_LIMIT;
 169                            /* We try to keep pause times from exceeding  */
 170                            /* this by much. In milliseconds.             */
 171 #elif defined(PARALLEL_MARK)
 172   unsigned long GC_time_limit = GC_TIME_UNLIMITED;
 173                         /* The parallel marker cannot be interrupted for */
 174                         /* now, so the time limit is absent by default.  */
 175 #else
 176   unsigned long GC_time_limit = 50;
 177 #endif
 178
 179 #ifndef NO_CLOCK
 180   STATIC unsigned long GC_time_lim_nsec = 0;
 181                         /* The nanoseconds add-on to GC_time_limit      */
 182                         /* value.  Not updated by GC_set_time_limit().  */
 183                         /* Ignored if the value of GC_time_limit is     */
 184                         /* GC_TIME_UNLIMITED.                           */
 185
 186 # define TV_NSEC_LIMIT (1000UL * 1000) /* amount of nanoseconds in 1 ms */
 187
 188   GC_API void GC_CALL GC_set_time_limit_tv(struct GC_timeval_s tv)
 189   {
 190     GC_ASSERT(tv.tv_ms <= GC_TIME_UNLIMITED);
 191     GC_ASSERT(tv.tv_nsec < TV_NSEC_LIMIT);
 192     GC_time_limit = tv.tv_ms;
 193     GC_time_lim_nsec = tv.tv_nsec;
 194   }
 195
 196   GC_API struct GC_timeval_s GC_CALL GC_get_time_limit_tv(void)
 197   {
 198     struct GC_timeval_s tv;
 199
 200     tv.tv_ms = GC_time_limit;
 201     tv.tv_nsec = GC_time_lim_nsec;
 202     return tv;
 203   }
 204
 205   STATIC CLOCK_TYPE GC_start_time = CLOCK_TYPE_INITIALIZER;
 206                                 /* Time at which we stopped world.      */
 207                                 /* used only in GC_timeout_stop_func.   */
 208 #endif /* !NO_CLOCK */
 209
 210 STATIC int GC_n_attempts = 0;   /* Number of attempts at finishing      */
 211                                 /* collection within GC_time_limit.     */
 212
 213 STATIC GC_stop_func GC_default_stop_func = GC_never_stop_func;
 214                                 /* accessed holding the lock.           */
 215
 216 GC_API void GC_CALL GC_set_stop_func(GC_stop_func stop_func)
 217 {
 218   DCL_LOCK_STATE;
 219   GC_ASSERT(NONNULL_ARG_NOT_NULL(stop_func));
 220   LOCK();
 221   GC_default_stop_func = stop_func;
 222   UNLOCK();
 223 }
 224
 225 GC_API GC_stop_func GC_CALL GC_get_stop_func(void)
 226 {
 227   GC_stop_func stop_func;
 228   DCL_LOCK_STATE;
 229   LOCK();
 230   stop_func = GC_default_stop_func;
 231   UNLOCK();
 232   return stop_func;
 233 }
 234
 235 #if defined(GC_DISABLE_INCREMENTAL) || defined(NO_CLOCK)
 236 # define GC_timeout_stop_func GC_default_stop_func
 237 #else
 238   STATIC int GC_CALLBACK GC_timeout_stop_func (void)
 239   {
 240     CLOCK_TYPE current_time;
 241     static unsigned count = 0;
 242     unsigned long time_diff, nsec_diff;
 243
 244     if ((*GC_default_stop_func)())
 245       return(1);
 246
 247     if ((count++ & 3) != 0) return(0);
 248     GET_TIME(current_time);
 249     time_diff = MS_TIME_DIFF(current_time,GC_start_time);
 250     nsec_diff = NS_FRAC_TIME_DIFF(current_time, GC_start_time);
 251     if (time_diff >= GC_time_limit
 252         && (time_diff > GC_time_limit || nsec_diff >= GC_time_lim_nsec)) {
 253       GC_COND_LOG_PRINTF("Abandoning stopped marking after %lu ms %lu ns"
 254                          " (attempt %d)\n",
 255                          time_diff, nsec_diff, GC_n_attempts);
 256       return 1;
 257     }
 258     return(0);
 259   }
 260 #endif /* !GC_DISABLE_INCREMENTAL */
 261
 262 #ifdef THREADS
 263   GC_INNER word GC_total_stacksize = 0; /* updated on every push_all_stacks */
 264 #endif
 265
 266 static size_t min_bytes_allocd_minimum = 1;
 267                         /* The lowest value returned by min_bytes_allocd(). */
 268
 269 GC_API void GC_CALL GC_set_min_bytes_allocd(size_t value)
 270 {
 271     GC_ASSERT(value > 0);
 272     min_bytes_allocd_minimum = value;
 273 }
 274
 275 GC_API size_t GC_CALL GC_get_min_bytes_allocd(void)
 276 {
 277     return min_bytes_allocd_minimum;
 278 }
 279
 280 /* Return the minimum number of bytes that must be allocated between    */
 281 /* collections to amortize the collection cost.  Should be non-zero.    */
 282 static word min_bytes_allocd(void)
 283 {
 284     word result;
 285     word stack_size;
 286     word total_root_size;       /* includes double stack size,  */
 287                                 /* since the stack is expensive */
 288                                 /* to scan.                     */
 289     word scan_size;             /* Estimate of memory to be scanned     */
 290                                 /* during normal GC.                    */
 291
 292 #   ifdef THREADS
 293       if (GC_need_to_lock) {
 294         /* We are multi-threaded... */
 295         stack_size = GC_total_stacksize;
 296         /* For now, we just use the value computed during the latest GC. */
 297 #       ifdef DEBUG_THREADS
 298           GC_log_printf("Total stacks size: %lu\n",
 299                         (unsigned long)stack_size);
 300 #       endif
 301       } else
 302 #   endif
 303     /* else*/ {
 304 #     ifdef STACK_NOT_SCANNED
 305         stack_size = 0;
 306 #     elif defined(STACK_GROWS_UP)
 307         stack_size = GC_approx_sp() - GC_stackbottom;
 308 #     else
 309         stack_size = GC_stackbottom - GC_approx_sp();
 310 #     endif
 311     }
 312
 313     total_root_size = 2 * stack_size + GC_root_size;
 314     scan_size = 2 * GC_composite_in_use + GC_atomic_in_use / 4
 315                 + total_root_size;
 316     result = scan_size / GC_free_space_divisor;
 317     if (GC_incremental) {
 318       result /= 2;
 319     }
 320     return result > min_bytes_allocd_minimum
 321             ? result : min_bytes_allocd_minimum;
 322 }
 323
 324 STATIC word GC_non_gc_bytes_at_gc = 0;
 325                 /* Number of explicitly managed bytes of storage        */
 326                 /* at last collection.                                  */
 327
 328 /* Return the number of bytes allocated, adjusted for explicit storage  */
 329 /* management, etc..  This number is used in deciding when to trigger   */
 330 /* collections.                                                         */
 331 STATIC word GC_adj_bytes_allocd(void)
 332 {
 333     signed_word result;
 334     signed_word expl_managed = (signed_word)GC_non_gc_bytes
 335                                 - (signed_word)GC_non_gc_bytes_at_gc;
 336
 337     /* Don't count what was explicitly freed, or newly allocated for    */
 338     /* explicit management.  Note that deallocating an explicitly       */
 339     /* managed object should not alter result, assuming the client      */
 340     /* is playing by the rules.                                         */
 341     result = (signed_word)GC_bytes_allocd
 342              + (signed_word)GC_bytes_dropped
 343              - (signed_word)GC_bytes_freed
 344              + (signed_word)GC_finalizer_bytes_freed
 345              - expl_managed;
 346     if (result > (signed_word)GC_bytes_allocd) {
 347         result = GC_bytes_allocd;
 348         /* probably client bug or unfortunate scheduling */
 349     }
 350     result += GC_bytes_finalized;
 351         /* We count objects enqueued for finalization as though they    */
 352         /* had been reallocated this round. Finalization is user        */
 353         /* visible progress.  And if we don't count this, we have       */
 354         /* stability problems for programs that finalize all objects.   */
 355     if (result < (signed_word)(GC_bytes_allocd >> 3)) {
 356         /* Always count at least 1/8 of the allocations.  We don't want */
 357         /* to collect too infrequently, since that would inhibit        */
 358         /* coalescing of free storage blocks.                           */
 359         /* This also makes us partially robust against client bugs.     */
 360         return(GC_bytes_allocd >> 3);
 361     } else {
 362         return(result);
 363     }
 364 }
 365
 366
 367 /* Clear up a few frames worth of garbage left at the top of the stack. */
 368 /* This is used to prevent us from accidentally treating garbage left   */
 369 /* on the stack by other parts of the collector as roots.  This         */
 370 /* differs from the code in misc.c, which actually tries to keep the    */
 371 /* stack clear of long-lived, client-generated garbage.                 */
 372 STATIC void GC_clear_a_few_frames(void)
 373 {
 374 #   ifndef CLEAR_NWORDS
 375 #     define CLEAR_NWORDS 64
 376 #   endif
 377     volatile word frames[CLEAR_NWORDS];
 378     BZERO((word *)frames, CLEAR_NWORDS * sizeof(word));
 379 }
 380
 381 /* Heap size at which we need a collection to avoid expanding past      */
 382 /* limits used by blacklisting.                                         */
 383 STATIC word GC_collect_at_heapsize = GC_WORD_MAX;
 384
 385 /* Have we allocated enough to amortize a collection? */
 386 GC_INNER GC_bool GC_should_collect(void)
 387 {
 388     static word last_min_bytes_allocd;
 389     static word last_gc_no;
 390     if (last_gc_no != GC_gc_no) {
 391       last_min_bytes_allocd = min_bytes_allocd();
 392       last_gc_no = GC_gc_no;
 393     }
 394     return(GC_adj_bytes_allocd() >= last_min_bytes_allocd
 395            || GC_heapsize >= GC_collect_at_heapsize);
 396 }
 397
 398 /* STATIC */ GC_start_callback_proc GC_start_call_back = 0;
 399                         /* Called at start of full collections.         */
 400                         /* Not called if 0.  Called with the allocation */
 401                         /* lock held.  Not used by GC itself.           */
 402
 403 GC_API void GC_CALL GC_set_start_callback(GC_start_callback_proc fn)
 404 {
 405     DCL_LOCK_STATE;
 406     LOCK();
 407     GC_start_call_back = fn;
 408     UNLOCK();
 409 }
 410
 411 GC_API GC_start_callback_proc GC_CALL GC_get_start_callback(void)
 412 {
 413     GC_start_callback_proc fn;
 414     DCL_LOCK_STATE;
 415     LOCK();
 416     fn = GC_start_call_back;
 417     UNLOCK();
 418     return fn;
 419 }
 420
 421 GC_INLINE void GC_notify_full_gc(void)
 422 {
 423     if (GC_start_call_back != 0) {
 424         (*GC_start_call_back)();
 425     }
 426 }
 427
 428 STATIC GC_bool GC_is_full_gc = FALSE;
 429
 430 STATIC GC_bool GC_stopped_mark(GC_stop_func stop_func);
 431 STATIC void GC_finish_collection(void);
 432
 433 /*
 434  * Initiate a garbage collection if appropriate.
 435  * Choose judiciously
 436  * between partial, full, and stop-world collections.
 437  */
 438 STATIC void GC_maybe_gc(void)
 439 {
 440     GC_ASSERT(I_HOLD_LOCK());
 441     ASSERT_CANCEL_DISABLED();
 442     if (GC_should_collect()) {
 443         static int n_partial_gcs = 0;
 444
 445         if (!GC_incremental) {
 446             /* TODO: If possible, GC_default_stop_func should be used here */
 447             GC_try_to_collect_inner(GC_never_stop_func);
 448             n_partial_gcs = 0;
 449             return;
 450         } else {
 451 #         ifdef PARALLEL_MARK
 452             if (GC_parallel)
 453               GC_wait_for_reclaim();
 454 #         endif
 455           if (GC_need_full_gc || n_partial_gcs >= GC_full_freq) {
 456             GC_COND_LOG_PRINTF(
 457                 "***>Full mark for collection #%lu after %lu allocd bytes\n",
 458                 (unsigned long)GC_gc_no + 1, (unsigned long)GC_bytes_allocd);
 459             GC_promote_black_lists();
 460             (void)GC_reclaim_all((GC_stop_func)0, TRUE);
 461             GC_notify_full_gc();
 462             GC_clear_marks();
 463             n_partial_gcs = 0;
 464             GC_is_full_gc = TRUE;
 465           } else {
 466             n_partial_gcs++;
 467           }
 468         }
 469         /* We try to mark with the world stopped.       */
 470         /* If we run out of time, this turns into       */
 471         /* incremental marking.                         */
 472 #       ifndef NO_CLOCK
 473           if (GC_time_limit != GC_TIME_UNLIMITED) { GET_TIME(GC_start_time); }
 474 #       endif
 475         /* TODO: If possible, GC_default_stop_func should be    */
 476         /* used instead of GC_never_stop_func here.             */
 477         if (GC_stopped_mark(GC_time_limit == GC_TIME_UNLIMITED?
 478                             GC_never_stop_func : GC_timeout_stop_func)) {
 479 #           ifdef SAVE_CALL_CHAIN
 480                 GC_save_callers(GC_last_stack);
 481 #           endif
 482             GC_finish_collection();
 483         } else {
 484             if (!GC_is_full_gc) {
 485                 /* Count this as the first attempt */
 486                 GC_n_attempts++;
 487             }
 488         }
 489     }
 490 }
 491
 492 STATIC GC_on_collection_event_proc GC_on_collection_event = 0;
 493
 494 GC_API void GC_CALL GC_set_on_collection_event(GC_on_collection_event_proc fn)
 495 {
 496     /* fn may be 0 (means no event notifier). */
 497     DCL_LOCK_STATE;
 498     LOCK();
 499     GC_on_collection_event = fn;
 500     UNLOCK();
 501 }
 502
 503 GC_API GC_on_collection_event_proc GC_CALL GC_get_on_collection_event(void)
 504 {
 505     GC_on_collection_event_proc fn;
 506     DCL_LOCK_STATE;
 507     LOCK();
 508     fn = GC_on_collection_event;
 509     UNLOCK();
 510     return fn;
 511 }
 512
 513 /* Stop the world garbage collection.  If stop_func is not      */
 514 /* GC_never_stop_func then abort if stop_func returns TRUE.     */
 515 /* Return TRUE if we successfully completed the collection.     */
 516 GC_INNER GC_bool GC_try_to_collect_inner(GC_stop_func stop_func)
 517 {
 518 #   ifndef NO_CLOCK
 519       CLOCK_TYPE start_time = CLOCK_TYPE_INITIALIZER;
 520       GC_bool start_time_valid;
 521 #   endif
 522
 523     ASSERT_CANCEL_DISABLED();
 524     GC_ASSERT(I_HOLD_LOCK());
 525     if (GC_dont_gc || (*stop_func)()) return FALSE;
 526     if (GC_on_collection_event)
 527       GC_on_collection_event(GC_EVENT_START);
 528     if (GC_incremental && GC_collection_in_progress()) {
 529       GC_COND_LOG_PRINTF(
 530             "GC_try_to_collect_inner: finishing collection in progress\n");
 531       /* Just finish collection already in progress.    */
 532         while(GC_collection_in_progress()) {
 533             if ((*stop_func)()) {
 534               /* TODO: Notify GC_EVENT_ABANDON */
 535               return(FALSE);
 536             }
 537             ENTER_GC();
 538             GC_collect_a_little_inner(1);
 539             EXIT_GC();
 540         }
 541     }
 542     GC_notify_full_gc();
 543 #   ifndef NO_CLOCK
 544       start_time_valid = FALSE;
 545       if ((GC_print_stats | (int)measure_performance) != 0) {
 546         if (GC_print_stats)
 547           GC_log_printf("Initiating full world-stop collection!\n");
 548         start_time_valid = TRUE;
 549         GET_TIME(start_time);
 550       }
 551 #   endif
 552     GC_promote_black_lists();
 553     /* Make sure all blocks have been reclaimed, so sweep routines      */
 554     /* don't see cleared mark bits.                                     */
 555     /* If we're guaranteed to finish, then this is unnecessary.         */
 556     /* In the find_leak case, we have to finish to guarantee that       */
 557     /* previously unmarked objects are not reported as leaks.           */
 558 #       ifdef PARALLEL_MARK
 559           if (GC_parallel)
 560             GC_wait_for_reclaim();
 561 #       endif
 562         if ((GC_find_leak || stop_func != GC_never_stop_func)
 563             && !GC_reclaim_all(stop_func, FALSE)) {
 564             /* Aborted.  So far everything is still consistent. */
 565             /* TODO: Notify GC_EVENT_ABANDON */
 566             return(FALSE);
 567         }
 568     GC_invalidate_mark_state();  /* Flush mark stack.   */
 569     GC_clear_marks();
 570 #   ifdef SAVE_CALL_CHAIN
 571         GC_save_callers(GC_last_stack);
 572 #   endif
 573     GC_is_full_gc = TRUE;
 574     if (!GC_stopped_mark(stop_func)) {
 575       if (!GC_incremental) {
 576         /* We're partially done and have no way to complete or use      */
 577         /* current work.  Reestablish invariants as cheaply as          */
 578         /* possible.                                                    */
 579         GC_invalidate_mark_state();
 580         GC_unpromote_black_lists();
 581       } /* else we claim the world is already still consistent.  We'll  */
 582         /* finish incrementally.                                        */
 583       /* TODO: Notify GC_EVENT_ABANDON */
 584       return(FALSE);
 585     }
 586     GC_finish_collection();
 587 #   ifndef NO_CLOCK
 588       if (start_time_valid) {
 589         CLOCK_TYPE current_time;
 590         unsigned long time_diff;
 591
 592         GET_TIME(current_time);
 593         time_diff = MS_TIME_DIFF(current_time, start_time);
 594         if (measure_performance)
 595           full_gc_total_time += time_diff; /* may wrap */
 596         if (GC_print_stats)
 597           GC_log_printf("Complete collection took %lu ms %lu ns\n", time_diff,
 598                         NS_FRAC_TIME_DIFF(current_time, start_time));
 599       }
 600 #   endif
 601     if (GC_on_collection_event)
 602       GC_on_collection_event(GC_EVENT_END);
 603     return(TRUE);
 604 }
 605
 606 /*
 607  * Perform n units of garbage collection work.  A unit is intended to touch
 608  * roughly GC_rate pages.  Every once in a while, we do more than that.
 609  * This needs to be a fairly large number with our current incremental
 610  * GC strategy, since otherwise we allocate too much during GC, and the
 611  * cleanup gets expensive.
 612  */
 613 #ifndef GC_RATE
 614 # define GC_RATE 10
 615 #endif
 616
 617 #ifndef MAX_PRIOR_ATTEMPTS
 618 # define MAX_PRIOR_ATTEMPTS 1
 619 #endif
 620         /* Maximum number of prior attempts at world stop marking       */
 621         /* A value of 1 means that we finish the second time, no matter */
 622         /* how long it takes.  Doesn't count the initial root scan      */
 623         /* for a full GC.                                               */
 624
 625 STATIC int GC_deficit = 0;/* The number of extra calls to GC_mark_some  */
 626                           /* that we have made.                         */
 627
 628 STATIC int GC_rate = GC_RATE;
 629
 630 GC_API void GC_CALL GC_set_rate(int value)
 631 {
 632     GC_ASSERT(value > 0);
 633     GC_rate = value;
 634 }
 635
 636 GC_API int GC_CALL GC_get_rate(void)
 637 {
 638     return GC_rate;
 639 }
 640
 641 static int max_prior_attempts = MAX_PRIOR_ATTEMPTS;
 642
 643 GC_API void GC_CALL GC_set_max_prior_attempts(int value)
 644 {
 645     GC_ASSERT(value >= 0);
 646     max_prior_attempts = value;
 647 }
 648
 649 GC_API int GC_CALL GC_get_max_prior_attempts(void)
 650 {
 651     return max_prior_attempts;
 652 }
 653
 654 GC_INNER void GC_collect_a_little_inner(int n)
 655 {
 656     IF_CANCEL(int cancel_state;)
 657
 658     GC_ASSERT(I_HOLD_LOCK());
 659     if (GC_dont_gc) return;
 660
 661     DISABLE_CANCEL(cancel_state);
 662     if (GC_incremental && GC_collection_in_progress()) {
 663         int i;
 664         int max_deficit = GC_rate * n;
 665
 666 #       ifdef PARALLEL_MARK
 667             if (GC_time_limit != GC_TIME_UNLIMITED)
 668                 GC_parallel_mark_disabled = TRUE;
 669 #       endif
 670         for (i = GC_deficit; i < max_deficit; i++) {
 671             if (GC_mark_some(NULL))
 672                 break;
 673         }
 674 #       ifdef PARALLEL_MARK
 675             GC_parallel_mark_disabled = FALSE;
 676 #       endif
 677
 678         if (i < max_deficit) {
 679             /* Need to finish a collection.     */
 680 #           ifdef SAVE_CALL_CHAIN
 681                 GC_save_callers(GC_last_stack);
 682 #           endif
 683 #           ifdef PARALLEL_MARK
 684                 if (GC_parallel)
 685                     GC_wait_for_reclaim();
 686 #           endif
 687             if (GC_n_attempts < max_prior_attempts
 688                 && GC_time_limit != GC_TIME_UNLIMITED) {
 689 #               ifndef NO_CLOCK
 690                     GET_TIME(GC_start_time);
 691 #               endif
 692                 if (GC_stopped_mark(GC_timeout_stop_func)) {
 693                     GC_finish_collection();
 694                 } else {
 695                     GC_n_attempts++;
 696                 }
 697             } else {
 698                 /* TODO: If possible, GC_default_stop_func should be    */
 699                 /* used here.                                           */
 700                 (void)GC_stopped_mark(GC_never_stop_func);
 701                 GC_finish_collection();
 702             }
 703         }
 704         if (GC_deficit > 0) {
 705             GC_deficit -= max_deficit;
 706             if (GC_deficit < 0)
 707                 GC_deficit = 0;
 708         }
 709     } else {
 710         GC_maybe_gc();
 711     }
 712     RESTORE_CANCEL(cancel_state);
 713 }
 714
 715 GC_INNER void (*GC_check_heap)(void) = 0;
 716 GC_INNER void (*GC_print_all_smashed)(void) = 0;
 717
 718 GC_API int GC_CALL GC_collect_a_little(void)
 719 {
 720     int result;
 721     DCL_LOCK_STATE;
 722
 723     LOCK();
 724     ENTER_GC();
 725     GC_collect_a_little_inner(1);
 726     EXIT_GC();
 727     result = (int)GC_collection_in_progress();
 728     UNLOCK();
 729     if (!result && GC_debugging_started) GC_print_all_smashed();
 730     return(result);
 731 }
 732
 733 #ifndef NO_CLOCK
 734   /* Variables for world-stop average delay time statistic computation. */
 735   /* "divisor" is incremented every world-stop and halved when reached  */
 736   /* its maximum (or upon "total_time" overflow).                       */
 737   static unsigned world_stopped_total_time = 0;
 738   static unsigned world_stopped_total_divisor = 0;
 739 # ifndef MAX_TOTAL_TIME_DIVISOR
 740     /* We shall not use big values here (so "outdated" delay time       */
 741     /* values would have less impact on "average" delay time value than */
 742     /* newer ones).                                                     */
 743 #   define MAX_TOTAL_TIME_DIVISOR 1000
 744 # endif
 745 #endif /* !NO_CLOCK */
 746
 747 #ifdef USE_MUNMAP
 748 # define IF_USE_MUNMAP(x) x
 749 # define COMMA_IF_USE_MUNMAP(x) /* comma */, x
 750 #else
 751 # define IF_USE_MUNMAP(x) /* empty */
 752 # define COMMA_IF_USE_MUNMAP(x) /* empty */
 753 #endif
 754
 755 /*
 756  * We stop the world and mark from all roots.
 757  * If stop_func() ever returns TRUE, we may fail and return FALSE.
 758  * Increment GC_gc_no if we succeed.
 759  */
 760 STATIC GC_bool GC_stopped_mark(GC_stop_func stop_func)
 761 {
 762     int i;
 763 #   ifndef NO_CLOCK
 764       CLOCK_TYPE start_time = CLOCK_TYPE_INITIALIZER;
 765 #   endif
 766
 767     GC_ASSERT(I_HOLD_LOCK());
 768 #   if !defined(REDIRECT_MALLOC) && defined(USE_WINALLOC)
 769         GC_add_current_malloc_heap();
 770 #   endif
 771 #   if defined(REGISTER_LIBRARIES_EARLY)
 772         GC_cond_register_dynamic_libraries();
 773 #   endif
 774
 775 #   ifndef NO_CLOCK
 776       if (GC_PRINT_STATS_FLAG)
 777         GET_TIME(start_time);
 778 #   endif
 779
 780 #   if !defined(GC_NO_FINALIZATION) && !defined(GC_TOGGLE_REFS_NOT_NEEDED)
 781       GC_process_togglerefs();
 782 #   endif
 783 #   ifdef THREADS
 784       if (GC_on_collection_event)
 785         GC_on_collection_event(GC_EVENT_PRE_STOP_WORLD);
 786 #   endif
 787     STOP_WORLD();
 788 #   ifdef THREADS
 789       if (GC_on_collection_event)
 790         GC_on_collection_event(GC_EVENT_POST_STOP_WORLD);
 791 #   endif
 792
 793 #   ifdef THREAD_LOCAL_ALLOC
 794       GC_world_stopped = TRUE;
 795 #   endif
 796         /* Output blank line for convenience here */
 797     GC_COND_LOG_PRINTF(
 798               "\n--> Marking for collection #%lu after %lu allocated bytes\n",
 799               (unsigned long)GC_gc_no + 1, (unsigned long) GC_bytes_allocd);
 800 #   ifdef MAKE_BACK_GRAPH
 801       if (GC_print_back_height) {
 802         GC_build_back_graph();
 803       }
 804 #   endif
 805
 806     /* Mark from all roots.  */
 807         if (GC_on_collection_event)
 808           GC_on_collection_event(GC_EVENT_MARK_START);
 809
 810         /* Minimize junk left in my registers and on the stack */
 811             GC_clear_a_few_frames();
 812             GC_noop6(0,0,0,0,0,0);
 813
 814         GC_initiate_gc();
 815 #       ifdef PARALLEL_MARK
 816           if (stop_func != GC_never_stop_func)
 817             GC_parallel_mark_disabled = TRUE;
 818 #       endif
 819         for (i = 0; !(*stop_func)(); i++) {
 820           if (GC_mark_some(GC_approx_sp())) {
 821 #           ifdef PARALLEL_MARK
 822               if (GC_parallel && GC_parallel_mark_disabled) {
 823                 GC_COND_LOG_PRINTF("Stopped marking done after %d iterations"
 824                                    " with disabled parallel marker\n", i);
 825               }
 826 #           endif
 827             i = -1;
 828             break;
 829           }
 830         }
 831 #       ifdef PARALLEL_MARK
 832           GC_parallel_mark_disabled = FALSE;
 833 #       endif
 834
 835         if (i >= 0) {
 836           GC_COND_LOG_PRINTF("Abandoned stopped marking after"
 837                              " %d iterations\n", i);
 838           GC_deficit = i;       /* Give the mutator a chance.   */
 839 #         ifdef THREAD_LOCAL_ALLOC
 840             GC_world_stopped = FALSE;
 841 #         endif
 842
 843 #         ifdef THREADS
 844             if (GC_on_collection_event)
 845               GC_on_collection_event(GC_EVENT_PRE_START_WORLD);
 846 #         endif
 847
 848           START_WORLD();
 849
 850 #         ifdef THREADS
 851             if (GC_on_collection_event)
 852               GC_on_collection_event(GC_EVENT_POST_START_WORLD);
 853 #         endif
 854
 855           /* TODO: Notify GC_EVENT_MARK_ABANDON */
 856           return FALSE;
 857         }
 858
 859     GC_gc_no++;
 860     GC_DBGLOG_PRINTF("GC #%lu freed %ld bytes, heap %lu KiB"
 861                      IF_USE_MUNMAP(" (+ %lu KiB unmapped)") "\n",
 862                      (unsigned long)GC_gc_no, (long)GC_bytes_found,
 863                      TO_KiB_UL(GC_heapsize - GC_unmapped_bytes) /*, */
 864                      COMMA_IF_USE_MUNMAP(TO_KiB_UL(GC_unmapped_bytes)));
 865
 866     /* Check all debugged objects for consistency */
 867     if (GC_debugging_started) {
 868       (*GC_check_heap)();
 869     }
 870     if (GC_on_collection_event) {
 871       GC_on_collection_event(GC_EVENT_MARK_END);
 872 #     ifdef THREADS
 873         GC_on_collection_event(GC_EVENT_PRE_START_WORLD);
 874 #     endif
 875     }
 876 #   ifdef THREAD_LOCAL_ALLOC
 877       GC_world_stopped = FALSE;
 878 #   endif
 879
 880     START_WORLD();
 881
 882 #   ifdef THREADS
 883       if (GC_on_collection_event)
 884         GC_on_collection_event(GC_EVENT_POST_START_WORLD);
 885 #   endif
 886
 887 #   ifndef NO_CLOCK
 888       if (GC_PRINT_STATS_FLAG) {
 889         unsigned long time_diff;
 890         unsigned total_time, divisor;
 891         CLOCK_TYPE current_time;
 892
 893         GET_TIME(current_time);
 894         time_diff = MS_TIME_DIFF(current_time,start_time);
 895
 896         /* Compute new world-stop delay total time */
 897         total_time = world_stopped_total_time;
 898         divisor = world_stopped_total_divisor;
 899         if ((int)total_time < 0 || divisor >= MAX_TOTAL_TIME_DIVISOR) {
 900           /* Halve values if overflow occurs */
 901           total_time >>= 1;
 902           divisor >>= 1;
 903         }
 904         total_time += time_diff < (((unsigned)-1) >> 1) ?
 905                         (unsigned)time_diff : ((unsigned)-1) >> 1;
 906         /* Update old world_stopped_total_time and its divisor */
 907         world_stopped_total_time = total_time;
 908         world_stopped_total_divisor = ++divisor;
 909
 910         GC_ASSERT(divisor != 0);
 911         GC_log_printf("World-stopped marking took %lu ms %lu ns"
 912                       " (%u ms in average)\n",
 913                       time_diff, NS_FRAC_TIME_DIFF(current_time, start_time),
 914                       total_time / divisor);
 915       }
 916 #   endif
 917     return(TRUE);
 918 }
 919
 920 /* Set all mark bits for the free list whose first entry is q   */
 921 GC_INNER void GC_set_fl_marks(ptr_t q)
 922 {
 923     if (q /* != NULL */) { /* CPPCHECK */
 924       struct hblk *h = HBLKPTR(q);
 925       struct hblk *last_h = h;
 926       hdr *hhdr = HDR(h);
 927       IF_PER_OBJ(word sz = hhdr->hb_sz;)
 928
 929       for (;;) {
 930         word bit_no = MARK_BIT_NO((ptr_t)q - (ptr_t)h, sz);
 931
 932         if (!mark_bit_from_hdr(hhdr, bit_no)) {
 933           set_mark_bit_from_hdr(hhdr, bit_no);
 934           ++hhdr -> hb_n_marks;
 935         }
 936
 937         q = (ptr_t)obj_link(q);
 938         if (q == NULL)
 939           break;
 940
 941         h = HBLKPTR(q);
 942         if (h != last_h) {
 943           last_h = h;
 944           hhdr = HDR(h);
 945           IF_PER_OBJ(sz = hhdr->hb_sz;)
 946         }
 947       }
 948     }
 949 }
 950
 951 #if defined(GC_ASSERTIONS) && defined(THREAD_LOCAL_ALLOC)
 952   /* Check that all mark bits for the free list whose first entry is    */
 953   /* (*pfreelist) are set.  Check skipped if points to a special value. */
 954   void GC_check_fl_marks(void **pfreelist)
 955   {
 956     /* TODO: There is a data race with GC_FAST_MALLOC_GRANS (which does */
 957     /* not do atomic updates to the free-list).  The race seems to be   */
 958     /* harmless, and for now we just skip this check in case of TSan.   */
 959 #   if defined(AO_HAVE_load_acquire_read) && !defined(THREAD_SANITIZER)
 960       AO_t *list = (AO_t *)AO_load_acquire_read((AO_t *)pfreelist);
 961                 /* Atomic operations are used because the world is running. */
 962       AO_t *prev;
 963       AO_t *p;
 964
 965       if ((word)list <= HBLKSIZE) return;
 966
 967       prev = (AO_t *)pfreelist;
 968       for (p = list; p != NULL;) {
 969         AO_t *next;
 970
 971         if (!GC_is_marked(p)) {
 972           ABORT_ARG2("Unmarked local free list entry",
 973                      ": object %p on list %p", (void *)p, (void *)list);
 974         }
 975
 976         /* While traversing the free-list, it re-reads the pointer to   */
 977         /* the current node before accepting its next pointer and       */
 978         /* bails out if the latter has changed.  That way, it won't     */
 979         /* try to follow the pointer which might be been modified       */
 980         /* after the object was returned to the client.  It might       */
 981         /* perform the mark-check on the just allocated object but      */
 982         /* that should be harmless.                                     */
 983         next = (AO_t *)AO_load_acquire_read(p);
 984         if (AO_load(prev) != (AO_t)p)
 985           break;
 986         prev = p;
 987         p = next;
 988       }
 989 #   else
 990       /* FIXME: Not implemented (just skipped). */
 991       (void)pfreelist;
 992 #   endif
 993   }
 994 #endif /* GC_ASSERTIONS && THREAD_LOCAL_ALLOC */
 995
 996 /* Clear all mark bits for the free list whose first entry is q */
 997 /* Decrement GC_bytes_found by number of bytes on free list.    */
 998 STATIC void GC_clear_fl_marks(ptr_t q)
 999 {
1000       struct hblk *h = HBLKPTR(q);
1001       struct hblk *last_h = h;
1002       hdr *hhdr = HDR(h);
1003       word sz = hhdr->hb_sz; /* Normally set only once. */
1004
1005       for (;;) {
1006         word bit_no = MARK_BIT_NO((ptr_t)q - (ptr_t)h, sz);
1007
1008         if (mark_bit_from_hdr(hhdr, bit_no)) {
1009           size_t n_marks = hhdr -> hb_n_marks;
1010
1011           GC_ASSERT(n_marks != 0);
1012           clear_mark_bit_from_hdr(hhdr, bit_no);
1013           n_marks--;
1014 #         ifdef PARALLEL_MARK
1015             /* Appr. count, don't decrement to zero! */
1016             if (0 != n_marks || !GC_parallel) {
1017               hhdr -> hb_n_marks = n_marks;
1018             }
1019 #         else
1020             hhdr -> hb_n_marks = n_marks;
1021 #         endif
1022         }
1023         GC_bytes_found -= sz;
1024
1025         q = (ptr_t)obj_link(q);
1026         if (q == NULL)
1027           break;
1028
1029         h = HBLKPTR(q);
1030         if (h != last_h) {
1031           last_h = h;
1032           hhdr = HDR(h);
1033           sz = hhdr->hb_sz;
1034         }
1035       }
1036 }
1037
1038 #if defined(GC_ASSERTIONS) && defined(THREAD_LOCAL_ALLOC)
1039   void GC_check_tls(void);
1040 #endif
1041
1042 GC_on_heap_resize_proc GC_on_heap_resize = 0;
1043
1044 /* Used for logging only. */
1045 GC_INLINE int GC_compute_heap_usage_percent(void)
1046 {
1047   word used = GC_composite_in_use + GC_atomic_in_use;
1048   word heap_sz = GC_heapsize - GC_unmapped_bytes;
1049 # if defined(CPPCHECK)
1050     word limit = (GC_WORD_MAX >> 1) / 50; /* to avoid a false positive */
1051 # else
1052     const word limit = GC_WORD_MAX / 100;
1053 # endif
1054
1055   return used >= heap_sz ? 0 : used < limit ?
1056                 (int)((used * 100) / heap_sz) : (int)(used / (heap_sz / 100));
1057 }
1058
1059 /* Finish up a collection.  Assumes mark bits are consistent, lock is   */
1060 /* held, but the world is otherwise running.                            */
1061 STATIC void GC_finish_collection(void)
1062 {
1063 #   ifndef NO_CLOCK
1064       CLOCK_TYPE start_time = CLOCK_TYPE_INITIALIZER;
1065       CLOCK_TYPE finalize_time = CLOCK_TYPE_INITIALIZER;
1066 #   endif
1067
1068     GC_ASSERT(I_HOLD_LOCK());
1069 #   if defined(GC_ASSERTIONS) \
1070        && defined(THREAD_LOCAL_ALLOC) && !defined(DBG_HDRS_ALL)
1071         /* Check that we marked some of our own data.           */
1072         /* TODO: Add more checks. */
1073         GC_check_tls();
1074 #   endif
1075
1076 #   ifndef NO_CLOCK
1077       if (GC_print_stats)
1078         GET_TIME(start_time);
1079 #   endif
1080     if (GC_on_collection_event)
1081       GC_on_collection_event(GC_EVENT_RECLAIM_START);
1082
1083 #   ifndef GC_GET_HEAP_USAGE_NOT_NEEDED
1084       if (GC_bytes_found > 0)
1085         GC_reclaimed_bytes_before_gc += (word)GC_bytes_found;
1086 #   endif
1087     GC_bytes_found = 0;
1088 #   if defined(LINUX) && defined(__ELF__) && !defined(SMALL_CONFIG)
1089         if (GETENV("GC_PRINT_ADDRESS_MAP") != 0) {
1090           GC_print_address_map();
1091         }
1092 #   endif
1093     COND_DUMP;
1094     if (GC_find_leak) {
1095       /* Mark all objects on the free list.  All objects should be      */
1096       /* marked when we're done.                                        */
1097       word size;        /* current object size  */
1098       unsigned kind;
1099       ptr_t q;
1100
1101       for (kind = 0; kind < GC_n_kinds; kind++) {
1102         for (size = 1; size <= MAXOBJGRANULES; size++) {
1103           q = (ptr_t)GC_obj_kinds[kind].ok_freelist[size];
1104           if (q != NULL)
1105             GC_set_fl_marks(q);
1106         }
1107       }
1108       GC_start_reclaim(TRUE);
1109         /* The above just checks; it doesn't really reclaim anything.   */
1110     }
1111
1112 #   ifndef GC_NO_FINALIZATION
1113       GC_finalize();
1114 #   endif
1115 #   ifndef NO_CLOCK
1116       if (GC_print_stats)
1117         GET_TIME(finalize_time);
1118 #   endif
1119
1120     if (GC_print_back_height) {
1121 #     ifdef MAKE_BACK_GRAPH
1122         GC_traverse_back_graph();
1123 #     elif !defined(SMALL_CONFIG)
1124         GC_err_printf("Back height not available: "
1125                       "Rebuild collector with -DMAKE_BACK_GRAPH\n");
1126 #     endif
1127     }
1128
1129     /* Clear free list mark bits, in case they got accidentally marked   */
1130     /* (or GC_find_leak is set and they were intentionally marked).      */
1131     /* Also subtract memory remaining from GC_bytes_found count.         */
1132     /* Note that composite objects on free list are cleared.             */
1133     /* Thus accidentally marking a free list is not a problem;  only     */
1134     /* objects on the list itself will be marked, and that's fixed here. */
1135     {
1136       word size;        /* current object size          */
1137       ptr_t q;          /* pointer to current object    */
1138       unsigned kind;
1139
1140       for (kind = 0; kind < GC_n_kinds; kind++) {
1141         for (size = 1; size <= MAXOBJGRANULES; size++) {
1142           q = (ptr_t)GC_obj_kinds[kind].ok_freelist[size];
1143           if (q != NULL)
1144             GC_clear_fl_marks(q);
1145         }
1146       }
1147     }
1148
1149     GC_VERBOSE_LOG_PRINTF("Bytes recovered before sweep - f.l. count = %ld\n",
1150                           (long)GC_bytes_found);
1151
1152     /* Reconstruct free lists to contain everything not marked */
1153     GC_start_reclaim(FALSE);
1154     GC_DBGLOG_PRINTF("In-use heap: %d%% (%lu KiB pointers + %lu KiB other)\n",
1155                      GC_compute_heap_usage_percent(),
1156                      TO_KiB_UL(GC_composite_in_use),
1157                      TO_KiB_UL(GC_atomic_in_use));
1158     if (GC_is_full_gc) {
1159         GC_used_heap_size_after_full = USED_HEAP_SIZE;
1160         GC_need_full_gc = FALSE;
1161     } else {
1162         GC_need_full_gc = USED_HEAP_SIZE - GC_used_heap_size_after_full
1163                             > min_bytes_allocd();
1164     }
1165
1166     GC_VERBOSE_LOG_PRINTF("Immediately reclaimed %ld bytes, heapsize:"
1167                           " %lu bytes" IF_USE_MUNMAP(" (%lu unmapped)") "\n",
1168                           (long)GC_bytes_found,
1169                           (unsigned long)GC_heapsize /*, */
1170                           COMMA_IF_USE_MUNMAP((unsigned long)
1171                                               GC_unmapped_bytes));
1172
1173     /* Reset or increment counters for next cycle */
1174     GC_n_attempts = 0;
1175     GC_is_full_gc = FALSE;
1176     GC_bytes_allocd_before_gc += GC_bytes_allocd;
1177     GC_non_gc_bytes_at_gc = GC_non_gc_bytes;
1178     GC_bytes_allocd = 0;
1179     GC_bytes_dropped = 0;
1180     GC_bytes_freed = 0;
1181     GC_finalizer_bytes_freed = 0;
1182
1183     IF_USE_MUNMAP(GC_unmap_old());
1184
1185     if (GC_on_collection_event)
1186       GC_on_collection_event(GC_EVENT_RECLAIM_END);
1187 #   ifndef NO_CLOCK
1188       if (GC_print_stats) {
1189         CLOCK_TYPE done_time;
1190
1191         GET_TIME(done_time);
1192 #       if !defined(SMALL_CONFIG) && !defined(GC_NO_FINALIZATION)
1193           /* A convenient place to output finalization statistics.      */
1194           GC_print_finalization_stats();
1195 #       endif
1196         GC_log_printf("Finalize and initiate sweep took %lu ms %lu ns"
1197                       " + %lu ms %lu ns\n",
1198                       MS_TIME_DIFF(finalize_time, start_time),
1199                       NS_FRAC_TIME_DIFF(finalize_time, start_time),
1200                       MS_TIME_DIFF(done_time, finalize_time),
1201                       NS_FRAC_TIME_DIFF(done_time, finalize_time));
1202       }
1203 #   elif !defined(SMALL_CONFIG) && !defined(GC_NO_FINALIZATION)
1204       if (GC_print_stats)
1205         GC_print_finalization_stats();
1206 #   endif
1207 }
1208
1209 /* If stop_func == 0 then GC_default_stop_func is used instead.         */
1210 STATIC GC_bool GC_try_to_collect_general(GC_stop_func stop_func,
1211                                          GC_bool force_unmap GC_ATTR_UNUSED)
1212 {
1213     GC_bool result;
1214     IF_USE_MUNMAP(int old_unmap_threshold;)
1215     IF_CANCEL(int cancel_state;)
1216     DCL_LOCK_STATE;
1217
1218     if (!EXPECT(GC_is_initialized, TRUE)) GC_init();
1219     if (GC_debugging_started) GC_print_all_smashed();
1220     GC_INVOKE_FINALIZERS();
1221     LOCK();
1222     DISABLE_CANCEL(cancel_state);
1223 #   ifdef USE_MUNMAP
1224       old_unmap_threshold = GC_unmap_threshold;
1225       if (force_unmap ||
1226           (GC_force_unmap_on_gcollect && old_unmap_threshold > 0))
1227         GC_unmap_threshold = 1; /* unmap as much as possible */
1228 #   endif
1229     ENTER_GC();
1230     /* Minimize junk left in my registers */
1231       GC_noop6(0,0,0,0,0,0);
1232     result = GC_try_to_collect_inner(stop_func != 0 ? stop_func :
1233                                      GC_default_stop_func);
1234     EXIT_GC();
1235     IF_USE_MUNMAP(GC_unmap_threshold = old_unmap_threshold); /* restore */
1236     RESTORE_CANCEL(cancel_state);
1237     UNLOCK();
1238     if (result) {
1239         if (GC_debugging_started) GC_print_all_smashed();
1240         GC_INVOKE_FINALIZERS();
1241     }
1242     return(result);
1243 }
1244
1245 /* Externally callable routines to invoke full, stop-the-world collection. */
1246 GC_API int GC_CALL GC_try_to_collect(GC_stop_func stop_func)
1247 {
1248     GC_ASSERT(NONNULL_ARG_NOT_NULL(stop_func));
1249     return (int)GC_try_to_collect_general(stop_func, FALSE);
1250 }
1251
1252 GC_API void GC_CALL GC_gcollect(void)
1253 {
1254     /* 0 is passed as stop_func to get GC_default_stop_func value       */
1255     /* while holding the allocation lock (to prevent data races).       */
1256     (void)GC_try_to_collect_general(0, FALSE);
1257     if (GC_have_errors) GC_print_all_errors();
1258 }
1259
1260 STATIC word GC_heapsize_at_forced_unmap = 0;
1261
1262 GC_API void GC_CALL GC_gcollect_and_unmap(void)
1263 {
1264     /* Record current heap size to make heap growth more conservative   */
1265     /* afterwards (as if the heap is growing from zero size again).     */
1266     GC_heapsize_at_forced_unmap = GC_heapsize;
1267     /* Collect and force memory unmapping to OS. */
1268     (void)GC_try_to_collect_general(GC_never_stop_func, TRUE);
1269 }
1270
1271 GC_INNER word GC_n_heap_sects = 0;
1272                         /* Number of sections currently in heap. */
1273
1274 #ifdef USE_PROC_FOR_LIBRARIES
1275   GC_INNER word GC_n_memory = 0;
1276                         /* Number of GET_MEM allocated memory sections. */
1277 #endif
1278
1279 #ifdef USE_PROC_FOR_LIBRARIES
1280   /* Add HBLKSIZE aligned, GET_MEM-generated block to GC_our_memory. */
1281   /* Defined to do nothing if USE_PROC_FOR_LIBRARIES not set.       */
1282   GC_INNER void GC_add_to_our_memory(ptr_t p, size_t bytes)
1283   {
1284     if (0 == p) return;
1285     if (GC_n_memory >= MAX_HEAP_SECTS)
1286       ABORT("Too many GC-allocated memory sections: Increase MAX_HEAP_SECTS");
1287     GC_our_memory[GC_n_memory].hs_start = p;
1288     GC_our_memory[GC_n_memory].hs_bytes = bytes;
1289     GC_n_memory++;
1290   }
1291 #endif
1292
1293 /*
1294  * Use the chunk of memory starting at p of size bytes as part of the heap.
1295  * Assumes p is HBLKSIZE aligned, and bytes is a multiple of HBLKSIZE.
1296  */
1297 GC_INNER void GC_add_to_heap(struct hblk *p, size_t bytes)
1298 {
1299     hdr * phdr;
1300     word endp;
1301
1302     if (GC_n_heap_sects >= MAX_HEAP_SECTS) {
1303         ABORT("Too many heap sections: Increase MAXHINCR or MAX_HEAP_SECTS");
1304     }
1305     while ((word)p <= HBLKSIZE) {
1306         /* Can't handle memory near address zero. */
1307         ++p;
1308         bytes -= HBLKSIZE;
1309         if (0 == bytes) return;
1310     }
1311     endp = (word)p + bytes;
1312     if (endp <= (word)p) {
1313         /* Address wrapped. */
1314         bytes -= HBLKSIZE;
1315         if (0 == bytes) return;
1316         endp -= HBLKSIZE;
1317     }
1318     phdr = GC_install_header(p);
1319     if (0 == phdr) {
1320         /* This is extremely unlikely. Can't add it.  This will         */
1321         /* almost certainly result in a 0 return from the allocator,    */
1322         /* which is entirely appropriate.                               */
1323         return;
1324     }
1325     GC_ASSERT(endp > (word)p && endp == (word)p + bytes);
1326     GC_heap_sects[GC_n_heap_sects].hs_start = (ptr_t)p;
1327     GC_heap_sects[GC_n_heap_sects].hs_bytes = bytes;
1328     GC_n_heap_sects++;
1329     phdr -> hb_sz = bytes;
1330     phdr -> hb_flags = 0;
1331     GC_freehblk(p);
1332     GC_heapsize += bytes;
1333
1334     /* Normally the caller calculates a new GC_collect_at_heapsize,
1335      * but this is also called directly from alloc_mark_stack, so
1336      * adjust here. It will be recalculated when called from
1337      * GC_expand_hp_inner.
1338      */
1339     GC_collect_at_heapsize += bytes;
1340     if (GC_collect_at_heapsize < GC_heapsize /* wrapped */)
1341        GC_collect_at_heapsize = GC_WORD_MAX;
1342
1343     if ((word)p <= (word)GC_least_plausible_heap_addr
1344         || GC_least_plausible_heap_addr == 0) {
1345         GC_least_plausible_heap_addr = (void *)((ptr_t)p - sizeof(word));
1346                 /* Making it a little smaller than necessary prevents   */
1347                 /* us from getting a false hit from the variable        */
1348                 /* itself.  There's some unintentional reflection       */
1349                 /* here.                                                */
1350     }
1351     if ((word)p + bytes >= (word)GC_greatest_plausible_heap_addr) {
1352         GC_greatest_plausible_heap_addr = (void *)endp;
1353     }
1354 }
1355
1356 #if !defined(NO_DEBUGGING)
1357   void GC_print_heap_sects(void)
1358   {
1359     unsigned i;
1360
1361     GC_printf("Total heap size: %lu" IF_USE_MUNMAP(" (%lu unmapped)") "\n",
1362               (unsigned long)GC_heapsize /*, */
1363               COMMA_IF_USE_MUNMAP((unsigned long)GC_unmapped_bytes));
1364
1365     for (i = 0; i < GC_n_heap_sects; i++) {
1366       ptr_t start = GC_heap_sects[i].hs_start;
1367       size_t len = GC_heap_sects[i].hs_bytes;
1368       struct hblk *h;
1369       unsigned nbl = 0;
1370
1371       for (h = (struct hblk *)start; (word)h < (word)(start + len); h++) {
1372         if (GC_is_black_listed(h, HBLKSIZE)) nbl++;
1373       }
1374       GC_printf("Section %d from %p to %p %u/%lu blacklisted\n",
1375                 i, (void *)start, (void *)&start[len],
1376                 nbl, (unsigned long)divHBLKSZ(len));
1377     }
1378   }
1379 #endif
1380
1381 void * GC_least_plausible_heap_addr = (void *)GC_WORD_MAX;
1382 void * GC_greatest_plausible_heap_addr = 0;
1383
1384 GC_INLINE word GC_max(word x, word y)
1385 {
1386     return(x > y? x : y);
1387 }
1388
1389 GC_INLINE word GC_min(word x, word y)
1390 {
1391     return(x < y? x : y);
1392 }
1393
1394 STATIC word GC_max_heapsize = 0;
1395
1396 GC_API void GC_CALL GC_set_max_heap_size(GC_word n)
1397 {
1398     GC_max_heapsize = n;
1399 }
1400
1401 GC_word GC_max_retries = 0;
1402
1403 /* This explicitly increases the size of the heap.  It is used          */
1404 /* internally, but may also be invoked from GC_expand_hp by the user.   */
1405 /* The argument is in units of HBLKSIZE (tiny values are rounded up).   */
1406 /* Returns FALSE on failure.                                            */
1407 GC_INNER GC_bool GC_expand_hp_inner(word n)
1408 {
1409     size_t bytes;
1410     struct hblk * space;
1411     word expansion_slop;        /* Number of bytes by which we expect the */
1412                                 /* heap to expand soon.                   */
1413
1414     GC_ASSERT(I_HOLD_LOCK());
1415     if (n < MINHINCR) n = MINHINCR;
1416     bytes = ROUNDUP_PAGESIZE((size_t)n * HBLKSIZE);
1417     if (GC_max_heapsize != 0
1418         && (GC_max_heapsize < (word)bytes
1419             || GC_heapsize > GC_max_heapsize - (word)bytes)) {
1420         /* Exceeded self-imposed limit */
1421         return(FALSE);
1422     }
1423     space = GET_MEM(bytes);
1424     GC_add_to_our_memory((ptr_t)space, bytes);
1425     if (space == 0) {
1426         WARN("Failed to expand heap by %" WARN_PRIdPTR " bytes\n",
1427              (word)bytes);
1428         return(FALSE);
1429     }
1430     GC_INFOLOG_PRINTF("Grow heap to %lu KiB after %lu bytes allocated\n",
1431                       TO_KiB_UL(GC_heapsize + (word)bytes),
1432                       (unsigned long)GC_bytes_allocd);
1433     /* Adjust heap limits generously for blacklisting to work better.   */
1434     /* GC_add_to_heap performs minimal adjustment needed for            */
1435     /* correctness.                                                     */
1436     expansion_slop = min_bytes_allocd() + 4*MAXHINCR*HBLKSIZE;
1437     if ((GC_last_heap_addr == 0 && !((word)space & SIGNB))
1438         || (GC_last_heap_addr != 0
1439             && (word)GC_last_heap_addr < (word)space)) {
1440         /* Assume the heap is growing up */
1441         word new_limit = (word)space + (word)bytes + expansion_slop;
1442         if (new_limit > (word)space) {
1443           GC_greatest_plausible_heap_addr =
1444             (void *)GC_max((word)GC_greatest_plausible_heap_addr,
1445                            (word)new_limit);
1446         }
1447     } else {
1448         /* Heap is growing down */
1449         word new_limit = (word)space - expansion_slop;
1450         if (new_limit < (word)space) {
1451           GC_least_plausible_heap_addr =
1452             (void *)GC_min((word)GC_least_plausible_heap_addr,
1453                            (word)space - expansion_slop);
1454         }
1455     }
1456     GC_prev_heap_addr = GC_last_heap_addr;
1457     GC_last_heap_addr = (ptr_t)space;
1458     GC_add_to_heap(space, bytes);
1459     /* Force GC before we are likely to allocate past expansion_slop */
1460       GC_collect_at_heapsize =
1461          GC_heapsize + expansion_slop - 2*MAXHINCR*HBLKSIZE;
1462       if (GC_collect_at_heapsize < GC_heapsize /* wrapped */)
1463          GC_collect_at_heapsize = GC_WORD_MAX;
1464     if (GC_on_heap_resize)
1465       (*GC_on_heap_resize)(GC_heapsize);
1466
1467     return(TRUE);
1468 }
1469
1470 /* Really returns a bool, but it's externally visible, so that's clumsy. */
1471 /* Arguments is in bytes.  Includes GC_init() call.                      */
1472 GC_API int GC_CALL GC_expand_hp(size_t bytes)
1473 {
1474     int result;
1475     DCL_LOCK_STATE;
1476
1477     if (!EXPECT(GC_is_initialized, TRUE)) GC_init();
1478     LOCK();
1479     result = (int)GC_expand_hp_inner(divHBLKSZ((word)bytes));
1480     if (result) GC_requested_heapsize += bytes;
1481     UNLOCK();
1482     return(result);
1483 }
1484
1485 word GC_fo_entries = 0; /* used also in extra/MacOS.c */
1486
1487 GC_INNER unsigned GC_fail_count = 0;
1488                         /* How many consecutive GC/expansion failures?  */
1489                         /* Reset by GC_allochblk.                       */
1490
1491 static word last_fo_entries = 0;
1492 static word last_bytes_finalized = 0;
1493
1494 /* Collect or expand heap in an attempt make the indicated number of    */
1495 /* free blocks available.  Should be called until the blocks are        */
1496 /* available (setting retry value to TRUE unless this is the first call */
1497 /* in a loop) or until it fails by returning FALSE.                     */
1498 GC_INNER GC_bool GC_collect_or_expand(word needed_blocks,
1499                                       GC_bool ignore_off_page,
1500                                       GC_bool retry)
1501 {
1502     GC_bool gc_not_stopped = TRUE;
1503     word blocks_to_get;
1504     IF_CANCEL(int cancel_state;)
1505
1506     GC_ASSERT(I_HOLD_LOCK());
1507     DISABLE_CANCEL(cancel_state);
1508     if (!GC_incremental && !GC_dont_gc &&
1509         ((GC_dont_expand && GC_bytes_allocd > 0)
1510          || (GC_fo_entries > (last_fo_entries + 500)
1511              && (last_bytes_finalized | GC_bytes_finalized) != 0)
1512          || GC_should_collect())) {
1513       /* Try to do a full collection using 'default' stop_func (unless  */
1514       /* nothing has been allocated since the latest collection or heap */
1515       /* expansion is disabled).                                        */
1516       gc_not_stopped = GC_try_to_collect_inner(
1517                         GC_bytes_allocd > 0 && (!GC_dont_expand || !retry) ?
1518                         GC_default_stop_func : GC_never_stop_func);
1519       if (gc_not_stopped == TRUE || !retry) {
1520         /* Either the collection hasn't been aborted or this is the     */
1521         /* first attempt (in a loop).                                   */
1522         last_fo_entries = GC_fo_entries;
1523         last_bytes_finalized = GC_bytes_finalized;
1524         RESTORE_CANCEL(cancel_state);
1525         return(TRUE);
1526       }
1527     }
1528
1529     blocks_to_get = (GC_heapsize - GC_heapsize_at_forced_unmap)
1530                         / (HBLKSIZE * GC_free_space_divisor)
1531                     + needed_blocks;
1532     if (blocks_to_get > MAXHINCR) {
1533       word slop;
1534
1535       /* Get the minimum required to make it likely that we can satisfy */
1536       /* the current request in the presence of black-listing.          */
1537       /* This will probably be more than MAXHINCR.                      */
1538       if (ignore_off_page) {
1539         slop = 4;
1540       } else {
1541         slop = 2 * divHBLKSZ(BL_LIMIT);
1542         if (slop > needed_blocks) slop = needed_blocks;
1543       }
1544       if (needed_blocks + slop > MAXHINCR) {
1545         blocks_to_get = needed_blocks + slop;
1546       } else {
1547         blocks_to_get = MAXHINCR;
1548       }
1549       if (blocks_to_get > divHBLKSZ(GC_WORD_MAX))
1550         blocks_to_get = divHBLKSZ(GC_WORD_MAX);
1551     }
1552
1553     if (!GC_expand_hp_inner(blocks_to_get)
1554         && (blocks_to_get == needed_blocks
1555             || !GC_expand_hp_inner(needed_blocks))) {
1556       if (gc_not_stopped == FALSE) {
1557         /* Don't increment GC_fail_count here (and no warning).     */
1558         GC_gcollect_inner();
1559         GC_ASSERT(GC_bytes_allocd == 0);
1560       } else if (GC_fail_count++ < GC_max_retries) {
1561         WARN("Out of Memory!  Trying to continue...\n", 0);
1562         GC_gcollect_inner();
1563       } else {
1564 #       if !defined(AMIGA) || !defined(GC_AMIGA_FASTALLOC)
1565           WARN("Out of Memory! Heap size: %" WARN_PRIdPTR " MiB."
1566                " Returning NULL!\n", (GC_heapsize - GC_unmapped_bytes) >> 20);
1567 #       endif
1568         RESTORE_CANCEL(cancel_state);
1569         return(FALSE);
1570       }
1571     } else if (GC_fail_count) {
1572       GC_COND_LOG_PRINTF("Memory available again...\n");
1573     }
1574     RESTORE_CANCEL(cancel_state);
1575     return(TRUE);
1576 }
1577
1578 /*
1579  * Make sure the object free list for size gran (in granules) is not empty.
1580  * Return a pointer to the first object on the free list.
1581  * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
1582  */
1583 GC_INNER ptr_t GC_allocobj(size_t gran, int kind)
1584 {
1585     void ** flh = &(GC_obj_kinds[kind].ok_freelist[gran]);
1586     GC_bool tried_minor = FALSE;
1587     GC_bool retry = FALSE;
1588
1589     GC_ASSERT(I_HOLD_LOCK());
1590     if (gran == 0) return(0);
1591
1592     while (*flh == 0) {
1593       ENTER_GC();
1594 #     ifndef GC_DISABLE_INCREMENTAL
1595         if (GC_incremental && GC_time_limit != GC_TIME_UNLIMITED) {
1596           /* True incremental mode, not just generational.      */
1597           /* Do our share of marking work.                      */
1598           GC_collect_a_little_inner(1);
1599         }
1600 #     endif
1601       /* Sweep blocks for objects of this size */
1602         GC_ASSERT(!GC_is_full_gc
1603                   || NULL == GC_obj_kinds[kind].ok_reclaim_list
1604                   || NULL == GC_obj_kinds[kind].ok_reclaim_list[gran]);
1605         GC_continue_reclaim(gran, kind);
1606       EXIT_GC();
1607 #     if defined(CPPCHECK)
1608         GC_noop1((word)flh);
1609 #     endif
1610       if (NULL == *flh) {
1611         GC_new_hblk(gran, kind);
1612 #       if defined(CPPCHECK)
1613           GC_noop1((word)flh);
1614 #       endif
1615         if (NULL == *flh) {
1616           ENTER_GC();
1617           if (GC_incremental && GC_time_limit == GC_TIME_UNLIMITED
1618               && !tried_minor) {
1619             GC_collect_a_little_inner(1);
1620             tried_minor = TRUE;
1621           } else {
1622             if (!GC_collect_or_expand(1, FALSE, retry)) {
1623               EXIT_GC();
1624               return(0);
1625             }
1626             retry = TRUE;
1627           }
1628           EXIT_GC();
1629         }
1630       }
1631     }
1632     /* Successful allocation; reset failure count.      */
1633     GC_fail_count = 0;
1634
1635     return (ptr_t)(*flh);
1636 }