[BACK]Return to alloc.c CVS log [TXT][DIR] Up to [local] / OpenXM_contrib2 / asir2000 / gc

Annotation of OpenXM_contrib2/asir2000/gc/alloc.c, Revision 1.7

1.1       noro        1: /*
                      2:  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
1.2       noro        3:  * Copyright (c) 1991-1996 by Xerox Corporation.  All rights reserved.
1.1       noro        4:  * Copyright (c) 1998 by Silicon Graphics.  All rights reserved.
1.2       noro        5:  * Copyright (c) 1999 by Hewlett-Packard Company. All rights reserved.
1.1       noro        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:
1.4       noro       19: # include "private/gc_priv.h"
1.1       noro       20:
                     21: # include <stdio.h>
1.4       noro       22: # if !defined(MACOS) && !defined(MSWINCE)
1.1       noro       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 MAXOBJSZ.
                     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
1.4       noro       63:   int GC_incremental = 0;  /* By default, stop the world.      */
1.1       noro       64: #endif
                     65:
1.4       noro       66: int GC_parallel = FALSE;   /* By default, parallel GC is off.  */
                     67:
1.2       noro       68: int GC_full_freq = 19;    /* Every 20th collection is a full   */
                     69:                           /* collection, whether we need it    */
                     70:                           /* or not.                           */
                     71:
                     72: GC_bool GC_need_full_gc = FALSE;
                     73:                           /* Need full GC do to heap growth.   */
                     74:
                     75: word GC_used_heap_size_after_full = 0;
1.1       noro       76:
                     77: char * GC_copyright[] =
                     78: {"Copyright 1988,1989 Hans-J. Boehm and Alan J. Demers ",
                     79: "Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved. ",
                     80: "Copyright (c) 1996-1998 by Silicon Graphics.  All rights reserved. ",
1.6       noro       81: "Copyright (c) 1999-2001 by Hewlett-Packard Company.  All rights reserved. ",
1.1       noro       82: "THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY",
                     83: " EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.",
                     84: "See source code for details." };
                     85:
                     86: # include "version.h"
                     87:
                     88: /* some more variables */
                     89:
                     90: extern signed_word GC_mem_found;  /* Number of reclaimed longwords     */
                     91:                                  /* after garbage collection           */
                     92:
                     93: GC_bool GC_dont_expand = 0;
                     94:
                     95: word GC_free_space_divisor = 3;
1.7     ! noro       96: word GC_free_space_numerator = 1;
1.1       noro       97:
                     98: extern GC_bool GC_collection_in_progress();
                     99:                /* Collection is in progress, or was abandoned. */
                    100:
1.6       noro      101: extern GC_bool GC_print_back_height;
                    102:
1.1       noro      103: int GC_never_stop_func GC_PROTO((void)) { return(0); }
                    104:
1.6       noro      105: unsigned long GC_time_limit = TIME_LIMIT;
                    106:
1.1       noro      107: CLOCK_TYPE GC_start_time;      /* Time at which we stopped world.      */
                    108:                                /* used only in GC_timeout_stop_func.   */
                    109:
                    110: int GC_n_attempts = 0;         /* Number of attempts at finishing      */
1.6       noro      111:                                /* collection within GC_time_limit.     */
1.1       noro      112:
1.6       noro      113: #if defined(SMALL_CONFIG) || defined(NO_CLOCK)
1.1       noro      114: #   define GC_timeout_stop_func GC_never_stop_func
                    115: #else
                    116:   int GC_timeout_stop_func GC_PROTO((void))
                    117:   {
                    118:     CLOCK_TYPE current_time;
                    119:     static unsigned count = 0;
                    120:     unsigned long time_diff;
                    121:
                    122:     if ((count++ & 3) != 0) return(0);
                    123:     GET_TIME(current_time);
                    124:     time_diff = MS_TIME_DIFF(current_time,GC_start_time);
1.6       noro      125:     if (time_diff >= GC_time_limit) {
1.4       noro      126: #      ifdef CONDPRINT
                    127:          if (GC_print_stats) {
1.1       noro      128:            GC_printf0("Abandoning stopped marking after ");
                    129:            GC_printf1("%lu msecs", (unsigned long)time_diff);
                    130:            GC_printf1("(attempt %d)\n", (unsigned long) GC_n_attempts);
1.4       noro      131:          }
1.1       noro      132: #      endif
                    133:        return(1);
                    134:     }
                    135:     return(0);
                    136:   }
                    137: #endif /* !SMALL_CONFIG */
                    138:
                    139: /* Return the minimum number of words that must be allocated between   */
                    140: /* collections to amortize the collection cost.                                */
                    141: static word min_words_allocd()
                    142: {
                    143: #   ifdef THREADS
                    144:        /* We punt, for now. */
                    145:        register signed_word stack_size = 10000;
                    146: #   else
                    147:         int dummy;
                    148:         register signed_word stack_size = (ptr_t)(&dummy) - GC_stackbottom;
                    149: #   endif
                    150:     word total_root_size;          /* includes double stack size,      */
                    151:                                    /* since the stack is expensive     */
                    152:                                    /* to scan.                         */
                    153:     word scan_size;            /* Estimate of memory to be scanned     */
                    154:                                /* during normal GC.                    */
                    155:
                    156:     if (stack_size < 0) stack_size = -stack_size;
                    157:     total_root_size = 2 * stack_size + GC_root_size;
                    158:     scan_size = BYTES_TO_WORDS(GC_heapsize - GC_large_free_bytes
                    159:                               + (GC_large_free_bytes >> 2)
                    160:                                   /* use a bit more of large empty heap */
                    161:                               + total_root_size);
1.6       noro      162:     if (TRUE_INCREMENTAL) {
1.7     ! noro      163:         return scan_size * GC_free_space_numerator / (2 * GC_free_space_divisor);
1.1       noro      164:     } else {
1.7     ! noro      165:         return scan_size * GC_free_space_numerator / GC_free_space_divisor;
1.1       noro      166:     }
                    167: }
                    168:
                    169: /* Return the number of words allocated, adjusted for explicit storage */
                    170: /* management, etc..  This number is used in deciding when to trigger  */
                    171: /* collections.                                                                */
                    172: word GC_adj_words_allocd()
                    173: {
                    174:     register signed_word result;
                    175:     register signed_word expl_managed =
                    176:                BYTES_TO_WORDS((long)GC_non_gc_bytes
                    177:                                - (long)GC_non_gc_bytes_at_gc);
                    178:
                    179:     /* Don't count what was explicitly freed, or newly allocated for   */
                    180:     /* explicit management.  Note that deallocating an explicitly      */
                    181:     /* managed object should not alter result, assuming the client     */
                    182:     /* is playing by the rules.                                                */
                    183:     result = (signed_word)GC_words_allocd
1.6       noro      184:             - (signed_word)GC_mem_freed
                    185:             + (signed_word)GC_finalizer_mem_freed - expl_managed;
1.1       noro      186:     if (result > (signed_word)GC_words_allocd) {
                    187:         result = GC_words_allocd;
                    188:        /* probably client bug or unfortunate scheduling */
                    189:     }
                    190:     result += GC_words_finalized;
                    191:        /* We count objects enqueued for finalization as though they    */
                    192:        /* had been reallocated this round. Finalization is user        */
                    193:        /* visible progress.  And if we don't count this, we have       */
                    194:        /* stability problems for programs that finalize all objects.   */
                    195:     result += GC_words_wasted;
                    196:        /* This doesn't reflect useful work.  But if there is lots of   */
                    197:        /* new fragmentation, the same is probably true of the heap,    */
                    198:        /* and the collection will be correspondingly cheaper.          */
                    199:     if (result < (signed_word)(GC_words_allocd >> 3)) {
                    200:        /* Always count at least 1/8 of the allocations.  We don't want */
                    201:        /* to collect too infrequently, since that would inhibit        */
                    202:        /* coalescing of free storage blocks.                           */
                    203:        /* This also makes us partially robust against client bugs.     */
                    204:         return(GC_words_allocd >> 3);
                    205:     } else {
                    206:         return(result);
                    207:     }
                    208: }
                    209:
                    210:
                    211: /* Clear up a few frames worth of garbage left at the top of the stack.        */
                    212: /* This is used to prevent us from accidentally treating garbade left  */
                    213: /* on the stack by other parts of the collector as roots.  This        */
                    214: /* differs from the code in misc.c, which actually tries to keep the   */
                    215: /* stack clear of long-lived, client-generated garbage.                        */
                    216: void GC_clear_a_few_frames()
                    217: {
                    218: #   define NWORDS 64
                    219:     word frames[NWORDS];
                    220:     register int i;
                    221:
                    222:     for (i = 0; i < NWORDS; i++) frames[i] = 0;
                    223: }
                    224:
                    225: /* Have we allocated enough to amortize a collection? */
                    226: GC_bool GC_should_collect()
                    227: {
                    228:     return(GC_adj_words_allocd() >= min_words_allocd());
                    229: }
                    230:
1.2       noro      231:
1.1       noro      232: void GC_notify_full_gc()
                    233: {
1.4       noro      234:     if (GC_start_call_back != (void (*) GC_PROTO((void)))0) {
1.1       noro      235:        (*GC_start_call_back)();
                    236:     }
                    237: }
                    238:
1.2       noro      239: GC_bool GC_is_full_gc = FALSE;
                    240:
1.1       noro      241: /*
                    242:  * Initiate a garbage collection if appropriate.
                    243:  * Choose judiciously
                    244:  * between partial, full, and stop-world collections.
                    245:  * Assumes lock held, signals disabled.
                    246:  */
                    247: void GC_maybe_gc()
                    248: {
                    249:     static int n_partial_gcs = 0;
                    250:
                    251:     if (GC_should_collect()) {
                    252:         if (!GC_incremental) {
                    253:            GC_notify_full_gc();
                    254:             GC_gcollect_inner();
                    255:             n_partial_gcs = 0;
                    256:             return;
1.6       noro      257:         } else {
                    258: #        ifdef PARALLEL_MARK
                    259:            GC_wait_for_reclaim();
                    260: #        endif
                    261:          if (GC_need_full_gc || n_partial_gcs >= GC_full_freq) {
1.4       noro      262: #          ifdef CONDPRINT
                    263:              if (GC_print_stats) {
                    264:                GC_printf2(
                    265:                  "***>Full mark for collection %lu after %ld allocd bytes\n",
                    266:                  (unsigned long) GC_gc_no+1,
                    267:                  (long)WORDS_TO_BYTES(GC_words_allocd));
                    268:              }
1.1       noro      269: #           endif
                    270:            GC_promote_black_lists();
                    271:            (void)GC_reclaim_all((GC_stop_func)0, TRUE);
                    272:            GC_clear_marks();
                    273:             n_partial_gcs = 0;
                    274:            GC_notify_full_gc();
1.2       noro      275:            GC_is_full_gc = TRUE;
1.6       noro      276:           } else {
1.1       noro      277:             n_partial_gcs++;
1.6       noro      278:           }
                    279:        }
1.1       noro      280:         /* We try to mark with the world stopped.      */
                    281:         /* If we run out of time, this turns into      */
                    282:         /* incremental marking.                        */
1.6       noro      283: #      ifndef NO_CLOCK
                    284:           if (GC_time_limit != GC_TIME_UNLIMITED) { GET_TIME(GC_start_time); }
                    285: #      endif
                    286:         if (GC_stopped_mark(GC_time_limit == GC_TIME_UNLIMITED?
                    287:                            GC_never_stop_func : GC_timeout_stop_func)) {
1.1       noro      288: #           ifdef SAVE_CALL_CHAIN
                    289:                 GC_save_callers(GC_last_stack);
                    290: #           endif
                    291:             GC_finish_collection();
                    292:         } else {
1.2       noro      293:            if (!GC_is_full_gc) {
1.1       noro      294:                /* Count this as the first attempt */
                    295:                GC_n_attempts++;
                    296:            }
                    297:        }
                    298:     }
                    299: }
                    300:
                    301:
                    302: /*
                    303:  * Stop the world garbage collection.  Assumes lock held, signals disabled.
                    304:  * If stop_func is not GC_never_stop_func, then abort if stop_func returns TRUE.
                    305:  */
                    306: GC_bool GC_try_to_collect_inner(stop_func)
                    307: GC_stop_func stop_func;
                    308: {
1.6       noro      309: #   ifdef CONDPRINT
                    310:         CLOCK_TYPE start_time, current_time;
                    311: #   endif
1.1       noro      312:     if (GC_incremental && GC_collection_in_progress()) {
1.4       noro      313: #   ifdef CONDPRINT
                    314:       if (GC_print_stats) {
1.1       noro      315:        GC_printf0(
                    316:            "GC_try_to_collect_inner: finishing collection in progress\n");
1.4       noro      317:       }
                    318: #   endif /* CONDPRINT */
1.1       noro      319:       /* Just finish collection already in progress.   */
                    320:        while(GC_collection_in_progress()) {
                    321:            if (stop_func()) return(FALSE);
                    322:            GC_collect_a_little_inner(1);
                    323:        }
                    324:     }
1.4       noro      325: #   ifdef CONDPRINT
                    326:       if (GC_print_stats) {
1.6       noro      327:         if (GC_print_stats) GET_TIME(start_time);
1.1       noro      328:        GC_printf2(
                    329:           "Initiating full world-stop collection %lu after %ld allocd bytes\n",
                    330:           (unsigned long) GC_gc_no+1,
                    331:           (long)WORDS_TO_BYTES(GC_words_allocd));
1.4       noro      332:       }
1.1       noro      333: #   endif
                    334:     GC_promote_black_lists();
                    335:     /* Make sure all blocks have been reclaimed, so sweep routines     */
                    336:     /* don't see cleared mark bits.                                    */
                    337:     /* If we're guaranteed to finish, then this is unnecessary.                */
1.3       noro      338:     /* In the find_leak case, we have to finish to guarantee that      */
                    339:     /* previously unmarked objects are not reported as leaks.          */
1.4       noro      340: #       ifdef PARALLEL_MARK
                    341:            GC_wait_for_reclaim();
                    342: #       endif
                    343:        if ((GC_find_leak || stop_func != GC_never_stop_func)
1.1       noro      344:            && !GC_reclaim_all(stop_func, FALSE)) {
                    345:            /* Aborted.  So far everything is still consistent. */
                    346:            return(FALSE);
                    347:        }
                    348:     GC_invalidate_mark_state();  /* Flush mark stack.  */
                    349:     GC_clear_marks();
                    350: #   ifdef SAVE_CALL_CHAIN
                    351:         GC_save_callers(GC_last_stack);
                    352: #   endif
1.2       noro      353:     GC_is_full_gc = TRUE;
1.1       noro      354:     if (!GC_stopped_mark(stop_func)) {
                    355:       if (!GC_incremental) {
                    356:        /* We're partially done and have no way to complete or use      */
                    357:        /* current work.  Reestablish invariants as cheaply as          */
                    358:        /* possible.                                                    */
                    359:        GC_invalidate_mark_state();
                    360:        GC_unpromote_black_lists();
                    361:       } /* else we claim the world is already still consistent.  We'll         */
                    362:         /* finish incrementally.                                       */
                    363:       return(FALSE);
                    364:     }
                    365:     GC_finish_collection();
1.6       noro      366: #   if defined(CONDPRINT)
                    367:       if (GC_print_stats) {
                    368:         GET_TIME(current_time);
                    369:         GC_printf1("Complete collection took %lu msecs\n",
                    370:                    MS_TIME_DIFF(current_time,start_time));
                    371:       }
                    372: #   endif
1.1       noro      373:     return(TRUE);
                    374: }
                    375:
                    376:
                    377:
                    378: /*
                    379:  * Perform n units of garbage collection work.  A unit is intended to touch
                    380:  * roughly GC_RATE pages.  Every once in a while, we do more than that.
                    381:  * This needa to be a fairly large number with our current incremental
                    382:  * GC strategy, since otherwise we allocate too much during GC, and the
                    383:  * cleanup gets expensive.
                    384:  */
                    385: # define GC_RATE 10
                    386: # define MAX_PRIOR_ATTEMPTS 1
                    387:        /* Maximum number of prior attempts at world stop marking       */
1.6       noro      388:        /* A value of 1 means that we finish the second time, no matter */
1.1       noro      389:        /* how long it takes.  Doesn't count the initial root scan      */
                    390:        /* for a full GC.                                               */
                    391:
                    392: int GC_deficit = 0;    /* The number of extra calls to GC_mark_some    */
                    393:                        /* that we have made.                           */
                    394:
                    395: void GC_collect_a_little_inner(n)
                    396: int n;
                    397: {
                    398:     register int i;
                    399:
                    400:     if (GC_incremental && GC_collection_in_progress()) {
                    401:        for (i = GC_deficit; i < GC_RATE*n; i++) {
                    402:            if (GC_mark_some((ptr_t)0)) {
                    403:                /* Need to finish a collection */
                    404: #              ifdef SAVE_CALL_CHAIN
                    405:                    GC_save_callers(GC_last_stack);
                    406: #              endif
1.6       noro      407: #              ifdef PARALLEL_MARK
                    408:                    GC_wait_for_reclaim();
                    409: #              endif
                    410:                if (GC_n_attempts < MAX_PRIOR_ATTEMPTS
                    411:                    && GC_time_limit != GC_TIME_UNLIMITED) {
1.1       noro      412:                  GET_TIME(GC_start_time);
                    413:                  if (!GC_stopped_mark(GC_timeout_stop_func)) {
                    414:                    GC_n_attempts++;
                    415:                    break;
                    416:                  }
                    417:                } else {
                    418:                  (void)GC_stopped_mark(GC_never_stop_func);
                    419:                }
                    420:                GC_finish_collection();
                    421:                break;
                    422:            }
                    423:        }
                    424:        if (GC_deficit > 0) GC_deficit -= GC_RATE*n;
                    425:        if (GC_deficit < 0) GC_deficit = 0;
                    426:     } else {
                    427:         GC_maybe_gc();
                    428:     }
                    429: }
                    430:
                    431: int GC_collect_a_little GC_PROTO(())
                    432: {
                    433:     int result;
                    434:     DCL_LOCK_STATE;
                    435:
                    436:     DISABLE_SIGNALS();
                    437:     LOCK();
                    438:     GC_collect_a_little_inner(1);
                    439:     result = (int)GC_collection_in_progress();
                    440:     UNLOCK();
                    441:     ENABLE_SIGNALS();
1.6       noro      442:     if (!result && GC_debugging_started) GC_print_all_smashed();
1.1       noro      443:     return(result);
                    444: }
                    445:
                    446: /*
                    447:  * Assumes lock is held, signals are disabled.
                    448:  * We stop the world.
                    449:  * If stop_func() ever returns TRUE, we may fail and return FALSE.
                    450:  * Increment GC_gc_no if we succeed.
                    451:  */
                    452: GC_bool GC_stopped_mark(stop_func)
                    453: GC_stop_func stop_func;
                    454: {
                    455:     register int i;
                    456:     int dummy;
1.6       noro      457: #   if defined(PRINTTIMES) || defined(CONDPRINT)
1.1       noro      458:        CLOCK_TYPE start_time, current_time;
                    459: #   endif
                    460:
1.4       noro      461: #   ifdef PRINTTIMES
1.1       noro      462:        GET_TIME(start_time);
1.4       noro      463: #   endif
1.6       noro      464: #   if defined(CONDPRINT) && !defined(PRINTTIMES)
                    465:        if (GC_print_stats) GET_TIME(start_time);
                    466: #   endif
1.7     ! noro      467:     GC_timerstart();
1.6       noro      468:     STOP_WORLD();
1.4       noro      469: #   ifdef CONDPRINT
                    470:       if (GC_print_stats) {
1.1       noro      471:        GC_printf1("--> Marking for collection %lu ",
                    472:                   (unsigned long) GC_gc_no + 1);
                    473:        GC_printf2("after %lu allocd bytes + %lu wasted bytes\n",
                    474:                   (unsigned long) WORDS_TO_BYTES(GC_words_allocd),
                    475:                   (unsigned long) WORDS_TO_BYTES(GC_words_wasted));
1.4       noro      476:       }
1.1       noro      477: #   endif
1.6       noro      478: #   ifdef MAKE_BACK_GRAPH
                    479:       if (GC_print_back_height) {
                    480:         GC_build_back_graph();
                    481:       }
                    482: #   endif
1.1       noro      483:
                    484:     /* Mark from all roots.  */
                    485:         /* Minimize junk left in my registers and on the stack */
                    486:             GC_clear_a_few_frames();
                    487:             GC_noop(0,0,0,0,0,0);
                    488:        GC_initiate_gc();
                    489:        for(i = 0;;i++) {
                    490:            if ((*stop_func)()) {
1.4       noro      491: #                  ifdef CONDPRINT
                    492:                      if (GC_print_stats) {
1.1       noro      493:                        GC_printf0("Abandoned stopped marking after ");
                    494:                        GC_printf1("%lu iterations\n",
                    495:                                   (unsigned long)i);
1.4       noro      496:                      }
1.1       noro      497: #                  endif
                    498:                    GC_deficit = i; /* Give the mutator a chance. */
                    499:                    START_WORLD();
1.7     ! noro      500:                        GC_timerstop();
1.1       noro      501:                    return(FALSE);
                    502:            }
                    503:            if (GC_mark_some((ptr_t)(&dummy))) break;
                    504:        }
                    505:
                    506:     GC_gc_no++;
                    507: #   ifdef PRINTSTATS
                    508:       GC_printf2("Collection %lu reclaimed %ld bytes",
                    509:                  (unsigned long) GC_gc_no - 1,
                    510:                  (long)WORDS_TO_BYTES(GC_mem_found));
1.4       noro      511: #   else
                    512: #     ifdef CONDPRINT
                    513:         if (GC_print_stats) {
                    514:          GC_printf1("Collection %lu finished", (unsigned long) GC_gc_no - 1);
                    515:        }
                    516: #     endif
                    517: #   endif /* !PRINTSTATS */
                    518: #   ifdef CONDPRINT
                    519:       if (GC_print_stats) {
                    520:         GC_printf1(" ---> heapsize = %lu bytes\n",
                    521:                   (unsigned long) GC_heapsize);
                    522:         /* Printf arguments may be pushed in funny places.  Clear the  */
                    523:         /* space.                                                      */
                    524:         GC_printf0("");
                    525:       }
                    526: #   endif  /* CONDPRINT  */
1.1       noro      527:
                    528:     /* Check all debugged objects for consistency */
                    529:         if (GC_debugging_started) {
                    530:             (*GC_check_heap)();
                    531:         }
                    532:
1.6       noro      533:     START_WORLD();
1.7     ! noro      534:     GC_timerstop();
1.1       noro      535: #   ifdef PRINTTIMES
                    536:        GET_TIME(current_time);
                    537:        GC_printf1("World-stopped marking took %lu msecs\n",
                    538:                   MS_TIME_DIFF(current_time,start_time));
1.6       noro      539: #   else
                    540: #     ifdef CONDPRINT
                    541:        if (GC_print_stats) {
                    542:          GET_TIME(current_time);
                    543:          GC_printf1("World-stopped marking took %lu msecs\n",
                    544:                     MS_TIME_DIFF(current_time,start_time));
                    545:        }
                    546: #     endif
1.1       noro      547: #   endif
                    548:     return(TRUE);
                    549: }
                    550:
1.6       noro      551: /* Set all mark bits for the free list whose first entry is q  */
                    552: #ifdef __STDC__
                    553:   void GC_set_fl_marks(ptr_t q)
                    554: #else
                    555:   void GC_set_fl_marks(q)
                    556:   ptr_t q;
                    557: #endif
                    558: {
                    559:    ptr_t p;
                    560:    struct hblk * h, * last_h = 0;
                    561:    hdr *hhdr;
                    562:    int word_no;
                    563:
                    564:    for (p = q; p != 0; p = obj_link(p)){
                    565:        h = HBLKPTR(p);
                    566:        if (h != last_h) {
                    567:          last_h = h;
                    568:          hhdr = HDR(h);
                    569:        }
                    570:        word_no = (((word *)p) - ((word *)h));
                    571:        set_mark_bit_from_hdr(hhdr, word_no);
                    572:    }
                    573: }
                    574:
                    575: /* Clear all mark bits for the free list whose first entry is q        */
                    576: /* Decrement GC_mem_found by number of words on free list.     */
                    577: #ifdef __STDC__
                    578:   void GC_clear_fl_marks(ptr_t q)
                    579: #else
                    580:   void GC_clear_fl_marks(q)
                    581:   ptr_t q;
                    582: #endif
                    583: {
                    584:    ptr_t p;
                    585:    struct hblk * h, * last_h = 0;
                    586:    hdr *hhdr;
                    587:    int word_no;
                    588:
                    589:    for (p = q; p != 0; p = obj_link(p)){
                    590:        h = HBLKPTR(p);
                    591:        if (h != last_h) {
                    592:          last_h = h;
                    593:          hhdr = HDR(h);
                    594:        }
                    595:        word_no = (((word *)p) - ((word *)h));
                    596:        clear_mark_bit_from_hdr(hhdr, word_no);
                    597: #      ifdef GATHERSTATS
                    598:            GC_mem_found -= hhdr -> hb_sz;
                    599: #      endif
                    600:    }
                    601: }
1.1       noro      602:
                    603: /* Finish up a collection.  Assumes lock is held, signals are disabled,        */
                    604: /* but the world is otherwise running.                                 */
                    605: void GC_finish_collection()
                    606: {
                    607: #   ifdef PRINTTIMES
                    608:        CLOCK_TYPE start_time;
                    609:        CLOCK_TYPE finalize_time;
                    610:        CLOCK_TYPE done_time;
                    611:
                    612:        GET_TIME(start_time);
                    613:        finalize_time = start_time;
                    614: #   endif
1.7     ! noro      615:        GC_timerstart();
1.1       noro      616:
                    617: #   ifdef GATHERSTATS
                    618:         GC_mem_found = 0;
                    619: #   endif
1.4       noro      620: #   if defined(LINUX) && defined(__ELF__) && !defined(SMALL_CONFIG)
                    621:        if (getenv("GC_PRINT_ADDRESS_MAP") != 0) {
                    622:          GC_print_address_map();
                    623:        }
                    624: #   endif
1.2       noro      625:     if (GC_find_leak) {
1.1       noro      626:       /* Mark all objects on the free list.  All objects should be */
                    627:       /* marked when we're done.                                  */
                    628:        {
                    629:          register word size;           /* current object size          */
                    630:          int kind;
1.6       noro      631:          ptr_t q;
1.1       noro      632:
                    633:          for (kind = 0; kind < GC_n_kinds; kind++) {
                    634:            for (size = 1; size <= MAXOBJSZ; size++) {
1.6       noro      635:              q = GC_obj_kinds[kind].ok_freelist[size];
                    636:              if (q != 0) GC_set_fl_marks(q);
1.1       noro      637:            }
                    638:          }
                    639:        }
                    640:        GC_start_reclaim(TRUE);
1.2       noro      641:          /* The above just checks; it doesn't really reclaim anything. */
                    642:     }
                    643:
                    644:     GC_finalize();
                    645: #   ifdef STUBBORN_ALLOC
                    646:       GC_clean_changing_list();
                    647: #   endif
                    648:
                    649: #   ifdef PRINTTIMES
                    650:       GET_TIME(finalize_time);
                    651: #   endif
1.1       noro      652:
1.6       noro      653:     if (GC_print_back_height) {
                    654: #     ifdef MAKE_BACK_GRAPH
                    655:        GC_traverse_back_graph();
                    656: #     else
                    657: #      ifndef SMALL_CONFIG
                    658:          GC_err_printf0("Back height not available: "
                    659:                         "Rebuild collector with -DMAKE_BACK_GRAPH\n");
                    660: #      endif
                    661: #     endif
                    662:     }
                    663:
1.2       noro      664:     /* Clear free list mark bits, in case they got accidentally marked   */
1.6       noro      665:     /* (or GC_find_leak is set and they were intentionally marked).     */
1.2       noro      666:     /* Also subtract memory remaining from GC_mem_found count.           */
                    667:     /* Note that composite objects on free list are cleared.             */
                    668:     /* Thus accidentally marking a free list is not a problem;  only     */
                    669:     /* objects on the list itself will be marked, and that's fixed here. */
1.1       noro      670:       {
                    671:        register word size;             /* current object size          */
1.6       noro      672:        register ptr_t q;       /* pointer to current object    */
1.1       noro      673:        int kind;
                    674:
                    675:        for (kind = 0; kind < GC_n_kinds; kind++) {
                    676:          for (size = 1; size <= MAXOBJSZ; size++) {
1.6       noro      677:            q = GC_obj_kinds[kind].ok_freelist[size];
                    678:            if (q != 0) GC_clear_fl_marks(q);
1.1       noro      679:          }
                    680:        }
                    681:       }
                    682:
                    683:
1.2       noro      684: #   ifdef PRINTSTATS
1.1       noro      685:        GC_printf1("Bytes recovered before sweep - f.l. count = %ld\n",
                    686:                  (long)WORDS_TO_BYTES(GC_mem_found));
1.2       noro      687: #   endif
1.1       noro      688:     /* Reconstruct free lists to contain everything not marked */
1.2       noro      689:         GC_start_reclaim(FALSE);
                    690:         if (GC_is_full_gc)  {
                    691:            GC_used_heap_size_after_full = USED_HEAP_SIZE;
                    692:            GC_need_full_gc = FALSE;
                    693:        } else {
                    694:            GC_need_full_gc =
                    695:                 BYTES_TO_WORDS(USED_HEAP_SIZE - GC_used_heap_size_after_full)
                    696:                 > min_words_allocd();
                    697:        }
1.1       noro      698:
                    699: #   ifdef PRINTSTATS
                    700:        GC_printf2(
                    701:                  "Immediately reclaimed %ld bytes in heap of size %lu bytes",
                    702:                  (long)WORDS_TO_BYTES(GC_mem_found),
                    703:                  (unsigned long)GC_heapsize);
                    704: #      ifdef USE_MUNMAP
                    705:          GC_printf1("(%lu unmapped)", GC_unmapped_bytes);
                    706: #      endif
                    707:        GC_printf2(
                    708:                "\n%lu (atomic) + %lu (composite) collectable bytes in use\n",
                    709:                (unsigned long)WORDS_TO_BYTES(GC_atomic_in_use),
                    710:                (unsigned long)WORDS_TO_BYTES(GC_composite_in_use));
                    711: #   endif
                    712:
                    713:       GC_n_attempts = 0;
1.2       noro      714:       GC_is_full_gc = FALSE;
1.1       noro      715:     /* Reset or increment counters for next cycle */
                    716:       GC_words_allocd_before_gc += GC_words_allocd;
                    717:       GC_non_gc_bytes_at_gc = GC_non_gc_bytes;
                    718:       GC_words_allocd = 0;
                    719:       GC_words_wasted = 0;
                    720:       GC_mem_freed = 0;
1.6       noro      721:       GC_finalizer_mem_freed = 0;
1.1       noro      722:
                    723: #   ifdef USE_MUNMAP
                    724:       GC_unmap_old();
                    725: #   endif
                    726: #   ifdef PRINTTIMES
                    727:        GET_TIME(done_time);
                    728:        GC_printf2("Finalize + initiate sweep took %lu + %lu msecs\n",
                    729:                   MS_TIME_DIFF(finalize_time,start_time),
                    730:                   MS_TIME_DIFF(done_time,finalize_time));
                    731: #   endif
1.7     ! noro      732:        GC_timerstop();
1.1       noro      733: }
                    734:
                    735: /* Externally callable routine to invoke full, stop-world collection */
                    736: # if defined(__STDC__) || defined(__cplusplus)
                    737:     int GC_try_to_collect(GC_stop_func stop_func)
                    738: # else
                    739:     int GC_try_to_collect(stop_func)
                    740:     GC_stop_func stop_func;
                    741: # endif
                    742: {
                    743:     int result;
                    744:     DCL_LOCK_STATE;
                    745:
1.6       noro      746:     if (GC_debugging_started) GC_print_all_smashed();
1.1       noro      747:     GC_INVOKE_FINALIZERS();
                    748:     DISABLE_SIGNALS();
                    749:     LOCK();
                    750:     ENTER_GC();
                    751:     if (!GC_is_initialized) GC_init_inner();
                    752:     /* Minimize junk left in my registers */
                    753:       GC_noop(0,0,0,0,0,0);
                    754:     result = (int)GC_try_to_collect_inner(stop_func);
                    755:     EXIT_GC();
                    756:     UNLOCK();
                    757:     ENABLE_SIGNALS();
1.6       noro      758:     if(result) {
                    759:         if (GC_debugging_started) GC_print_all_smashed();
                    760:         GC_INVOKE_FINALIZERS();
                    761:     }
1.1       noro      762:     return(result);
                    763: }
                    764:
                    765: void GC_gcollect GC_PROTO(())
                    766: {
                    767:     GC_notify_full_gc();
                    768:     (void)GC_try_to_collect(GC_never_stop_func);
                    769: }
                    770:
                    771: word GC_n_heap_sects = 0;      /* Number of sections currently in heap. */
                    772:
                    773: /*
                    774:  * Use the chunk of memory starting at p of size bytes as part of the heap.
                    775:  * Assumes p is HBLKSIZE aligned, and bytes is a multiple of HBLKSIZE.
                    776:  */
                    777: void GC_add_to_heap(p, bytes)
                    778: struct hblk *p;
                    779: word bytes;
                    780: {
                    781:     word words;
                    782:     hdr * phdr;
                    783:
                    784:     if (GC_n_heap_sects >= MAX_HEAP_SECTS) {
                    785:        ABORT("Too many heap sections: Increase MAXHINCR or MAX_HEAP_SECTS");
                    786:     }
1.3       noro      787:     phdr = GC_install_header(p);
                    788:     if (0 == phdr) {
1.1       noro      789:        /* This is extremely unlikely. Can't add it.  This will         */
                    790:        /* almost certainly result in a 0 return from the allocator,    */
                    791:        /* which is entirely appropriate.                               */
                    792:        return;
                    793:     }
                    794:     GC_heap_sects[GC_n_heap_sects].hs_start = (ptr_t)p;
                    795:     GC_heap_sects[GC_n_heap_sects].hs_bytes = bytes;
                    796:     GC_n_heap_sects++;
1.4       noro      797:     words = BYTES_TO_WORDS(bytes);
1.1       noro      798:     phdr -> hb_sz = words;
1.4       noro      799:     phdr -> hb_map = (unsigned char *)1;   /* A value != GC_invalid_map        */
1.1       noro      800:     phdr -> hb_flags = 0;
                    801:     GC_freehblk(p);
                    802:     GC_heapsize += bytes;
1.4       noro      803:     if ((ptr_t)p <= (ptr_t)GC_least_plausible_heap_addr
1.1       noro      804:         || GC_least_plausible_heap_addr == 0) {
1.4       noro      805:         GC_least_plausible_heap_addr = (GC_PTR)((ptr_t)p - sizeof(word));
1.1       noro      806:                /* Making it a little smaller than necessary prevents   */
                    807:                /* us from getting a false hit from the variable        */
                    808:                /* itself.  There's some unintentional reflection       */
                    809:                /* here.                                                */
                    810:     }
1.4       noro      811:     if ((ptr_t)p + bytes >= (ptr_t)GC_greatest_plausible_heap_addr) {
                    812:         GC_greatest_plausible_heap_addr = (GC_PTR)((ptr_t)p + bytes);
1.1       noro      813:     }
                    814: }
                    815:
                    816: # if !defined(NO_DEBUGGING)
                    817: void GC_print_heap_sects()
                    818: {
                    819:     register unsigned i;
                    820:
                    821:     GC_printf1("Total heap size: %lu\n", (unsigned long) GC_heapsize);
                    822:     for (i = 0; i < GC_n_heap_sects; i++) {
                    823:         unsigned long start = (unsigned long) GC_heap_sects[i].hs_start;
                    824:         unsigned long len = (unsigned long) GC_heap_sects[i].hs_bytes;
                    825:         struct hblk *h;
                    826:         unsigned nbl = 0;
                    827:
                    828:        GC_printf3("Section %ld from 0x%lx to 0x%lx ", (unsigned long)i,
                    829:                   start, (unsigned long)(start + len));
                    830:        for (h = (struct hblk *)start; h < (struct hblk *)(start + len); h++) {
                    831:            if (GC_is_black_listed(h, HBLKSIZE)) nbl++;
                    832:        }
                    833:        GC_printf2("%lu/%lu blacklisted\n", (unsigned long)nbl,
                    834:                   (unsigned long)(len/HBLKSIZE));
                    835:     }
                    836: }
                    837: # endif
                    838:
1.4       noro      839: GC_PTR GC_least_plausible_heap_addr = (GC_PTR)ONES;
                    840: GC_PTR GC_greatest_plausible_heap_addr = 0;
1.1       noro      841:
                    842: ptr_t GC_max(x,y)
                    843: ptr_t x, y;
                    844: {
                    845:     return(x > y? x : y);
                    846: }
                    847:
                    848: ptr_t GC_min(x,y)
                    849: ptr_t x, y;
                    850: {
                    851:     return(x < y? x : y);
                    852: }
                    853:
                    854: # if defined(__STDC__) || defined(__cplusplus)
                    855:     void GC_set_max_heap_size(GC_word n)
                    856: # else
                    857:     void GC_set_max_heap_size(n)
                    858:     GC_word n;
                    859: # endif
                    860: {
                    861:     GC_max_heapsize = n;
                    862: }
                    863:
                    864: GC_word GC_max_retries = 0;
                    865:
                    866: /*
                    867:  * this explicitly increases the size of the heap.  It is used
                    868:  * internally, but may also be invoked from GC_expand_hp by the user.
                    869:  * The argument is in units of HBLKSIZE.
                    870:  * Tiny values of n are rounded up.
                    871:  * Returns FALSE on failure.
                    872:  */
                    873: GC_bool GC_expand_hp_inner(n)
                    874: word n;
                    875: {
                    876:     word bytes;
                    877:     struct hblk * space;
                    878:     word expansion_slop;       /* Number of bytes by which we expect the */
                    879:                                /* heap to expand soon.                   */
                    880:
                    881:     if (n < MINHINCR) n = MINHINCR;
                    882:     bytes = n * HBLKSIZE;
                    883:     /* Make sure bytes is a multiple of GC_page_size */
                    884:       {
                    885:        word mask = GC_page_size - 1;
                    886:        bytes += mask;
                    887:        bytes &= ~mask;
                    888:       }
                    889:
                    890:     if (GC_max_heapsize != 0 && GC_heapsize + bytes > GC_max_heapsize) {
                    891:         /* Exceeded self-imposed limit */
                    892:         return(FALSE);
                    893:     }
                    894:     space = GET_MEM(bytes);
                    895:     if( space == 0 ) {
1.4       noro      896: #      ifdef CONDPRINT
                    897:          if (GC_print_stats) {
                    898:            GC_printf1("Failed to expand heap by %ld bytes\n",
                    899:                       (unsigned long)bytes);
                    900:          }
                    901: #       endif
1.1       noro      902:        return(FALSE);
                    903:     }
1.4       noro      904: #   ifdef CONDPRINT
                    905:       if (GC_print_stats) {
1.1       noro      906:        GC_printf2("Increasing heap size by %lu after %lu allocated bytes\n",
                    907:                   (unsigned long)bytes,
                    908:                   (unsigned long)WORDS_TO_BYTES(GC_words_allocd));
                    909: #      ifdef UNDEFINED
                    910:          GC_printf1("Root size = %lu\n", GC_root_size);
                    911:          GC_print_block_list(); GC_print_hblkfreelist();
                    912:          GC_printf0("\n");
                    913: #      endif
1.4       noro      914:       }
1.1       noro      915: #   endif
                    916:     expansion_slop = 8 * WORDS_TO_BYTES(min_words_allocd());
                    917:     if (5 * HBLKSIZE * MAXHINCR > expansion_slop) {
                    918:         expansion_slop = 5 * HBLKSIZE * MAXHINCR;
                    919:     }
                    920:     if (GC_last_heap_addr == 0 && !((word)space & SIGNB)
                    921:         || GC_last_heap_addr != 0 && GC_last_heap_addr < (ptr_t)space) {
                    922:         /* Assume the heap is growing up */
                    923:         GC_greatest_plausible_heap_addr =
                    924:             GC_max(GC_greatest_plausible_heap_addr,
                    925:                    (ptr_t)space + bytes + expansion_slop);
                    926:     } else {
                    927:         /* Heap is growing down */
                    928:         GC_least_plausible_heap_addr =
                    929:             GC_min(GC_least_plausible_heap_addr,
                    930:                    (ptr_t)space - expansion_slop);
                    931:     }
                    932:     GC_prev_heap_addr = GC_last_heap_addr;
                    933:     GC_last_heap_addr = (ptr_t)space;
                    934:     GC_add_to_heap(space, bytes);
                    935:     return(TRUE);
                    936: }
                    937:
                    938: /* Really returns a bool, but it's externally visible, so that's clumsy. */
                    939: /* Arguments is in bytes.                                              */
                    940: # if defined(__STDC__) || defined(__cplusplus)
                    941:   int GC_expand_hp(size_t bytes)
                    942: # else
                    943:   int GC_expand_hp(bytes)
                    944:   size_t bytes;
                    945: # endif
                    946: {
                    947:     int result;
                    948:     DCL_LOCK_STATE;
                    949:
                    950:     DISABLE_SIGNALS();
                    951:     LOCK();
                    952:     if (!GC_is_initialized) GC_init_inner();
                    953:     result = (int)GC_expand_hp_inner(divHBLKSZ((word)bytes));
1.3       noro      954:     if (result) GC_requested_heapsize += bytes;
1.1       noro      955:     UNLOCK();
                    956:     ENABLE_SIGNALS();
                    957:     return(result);
                    958: }
                    959:
                    960: unsigned GC_fail_count = 0;
                    961:                        /* How many consecutive GC/expansion failures?  */
                    962:                        /* Reset by GC_allochblk.                       */
                    963:
                    964: GC_bool GC_collect_or_expand(needed_blocks, ignore_off_page)
                    965: word needed_blocks;
                    966: GC_bool ignore_off_page;
                    967: {
1.3       noro      968:     if (!GC_incremental && !GC_dont_gc &&
                    969:        (GC_dont_expand && GC_words_allocd > 0 || GC_should_collect())) {
1.1       noro      970:       GC_notify_full_gc();
                    971:       GC_gcollect_inner();
                    972:     } else {
1.6       noro      973:       word blocks_to_get = GC_heapsize/(HBLKSIZE*GC_free_space_divisor)
1.1       noro      974:                           + needed_blocks;
                    975:
                    976:       if (blocks_to_get > MAXHINCR) {
                    977:           word slop;
                    978:
                    979:           if (ignore_off_page) {
                    980:               slop = 4;
                    981:           } else {
                    982:              slop = 2*divHBLKSZ(BL_LIMIT);
                    983:              if (slop > needed_blocks) slop = needed_blocks;
                    984:          }
                    985:           if (needed_blocks + slop > MAXHINCR) {
                    986:               blocks_to_get = needed_blocks + slop;
                    987:           } else {
                    988:               blocks_to_get = MAXHINCR;
                    989:           }
                    990:       }
                    991:       if (!GC_expand_hp_inner(blocks_to_get)
                    992:         && !GC_expand_hp_inner(needed_blocks)) {
                    993:        if (GC_fail_count++ < GC_max_retries) {
                    994:            WARN("Out of Memory!  Trying to continue ...\n", 0);
                    995:            GC_notify_full_gc();
                    996:            GC_gcollect_inner();
                    997:        } else {
1.4       noro      998: #          if !defined(AMIGA) || !defined(GC_AMIGA_FASTALLOC)
                    999:              WARN("Out of Memory!  Returning NIL!\n", 0);
                   1000: #          endif
1.1       noro     1001:            return(FALSE);
                   1002:        }
                   1003:       } else {
1.4       noro     1004: #        ifdef CONDPRINT
                   1005:             if (GC_fail_count && GC_print_stats) {
1.1       noro     1006:              GC_printf0("Memory available again ...\n");
                   1007:            }
                   1008: #        endif
                   1009:       }
                   1010:     }
                   1011:     return(TRUE);
                   1012: }
                   1013:
                   1014: /*
                   1015:  * Make sure the object free list for sz is not empty.
                   1016:  * Return a pointer to the first object on the free list.
                   1017:  * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
                   1018:  * Assumes we hold the allocator lock and signals are disabled.
                   1019:  *
                   1020:  */
                   1021: ptr_t GC_allocobj(sz, kind)
                   1022: word sz;
                   1023: int kind;
                   1024: {
1.6       noro     1025:     ptr_t * flh = &(GC_obj_kinds[kind].ok_freelist[sz]);
                   1026:     GC_bool tried_minor = FALSE;
1.1       noro     1027:
                   1028:     if (sz == 0) return(0);
                   1029:
                   1030:     while (*flh == 0) {
                   1031:       ENTER_GC();
                   1032:       /* Do our share of marking work */
1.6       noro     1033:         if(TRUE_INCREMENTAL && !GC_dont_gc) GC_collect_a_little_inner(1);
1.1       noro     1034:       /* Sweep blocks for objects of this size */
1.6       noro     1035:         GC_continue_reclaim(sz, kind);
1.1       noro     1036:       EXIT_GC();
                   1037:       if (*flh == 0) {
                   1038:         GC_new_hblk(sz, kind);
                   1039:       }
                   1040:       if (*flh == 0) {
                   1041:         ENTER_GC();
1.6       noro     1042:        if (GC_incremental && GC_time_limit == GC_TIME_UNLIMITED
                   1043:            && ! tried_minor ) {
                   1044:            GC_collect_a_little_inner(1);
                   1045:            tried_minor = TRUE;
                   1046:        } else {
                   1047:           if (!GC_collect_or_expand((word)1,FALSE)) {
1.1       noro     1048:            EXIT_GC();
                   1049:            return(0);
1.6       noro     1050:          }
1.1       noro     1051:        }
                   1052:        EXIT_GC();
                   1053:       }
                   1054:     }
                   1055:
                   1056:     return(*flh);
                   1057: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>