[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.3

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

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