1: /* 
    2:  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
    3:  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
    4:  * Copyright (c) 1999-2001 by Hewlett-Packard Company. All rights reserved.
    5:  *
    6:  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
    7:  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
    8:  *
    9:  * Permission is hereby granted to use or copy this program
   10:  * for any purpose,  provided the above notices are retained on all copies.
   11:  * Permission to modify the code and to distribute modified code is granted,
   12:  * provided the above notices are retained, and a notice that the code was
   13:  * modified is included with the above copyright notice.
   14:  */
   15: /* Boehm, July 31, 1995 5:02 pm PDT */
   16: 
   17: 
   18: #include <stdio.h>
   19: #include <limits.h>
   20: #ifndef _WIN32_WCE
   21: #include <signal.h>
   22: #endif
   23: 
   24: #define I_HIDE_POINTERS /* To make GC_call_with_alloc_lock visible */
   25: #include "private/gc_pmark.h"
   26: 
   27: #ifdef GC_SOLARIS_THREADS
   28: # include <sys/syscall.h>
   29: #endif
   30: #if defined(MSWIN32) || defined(MSWINCE)
   31: # define WIN32_LEAN_AND_MEAN
   32: # define NOSERVICE
   33: # include <windows.h>
   34: # include <tchar.h>
   35: #endif
   36: 
   37: #ifdef NONSTOP
   38: # include <floss.h>
   39: #endif
   40: 
   41: # ifdef THREADS
   42: #   ifdef PCR
   43: #     include "il/PCR_IL.h"
   44:       PCR_Th_ML GC_allocate_ml;
   45: #   else
   46: #     ifdef SRC_M3
   47:         /* Critical section counter is defined in the M3 runtime       */
   48:         /* That's all we use.                                          */
   49: #     else
   50: #       ifdef GC_SOLARIS_THREADS
   51:           mutex_t GC_allocate_ml;      /* Implicitly initialized.   */
   52: #       else
   53: #          if defined(GC_WIN32_THREADS) 
   54: #             if defined(GC_PTHREADS)
   55:                   pthread_mutex_t GC_allocate_ml = PTHREAD_MUTEX_INITIALIZER;
   56: #             elif defined(GC_DLL)
   57:                  __declspec(dllexport) CRITICAL_SECTION GC_allocate_ml;
   58: #             else
   59:                  CRITICAL_SECTION GC_allocate_ml;
   60: #             endif
   61: #          else
   62: #             if defined(GC_PTHREADS) && !defined(GC_SOLARIS_THREADS)
   63: #               if defined(USE_SPIN_LOCK)
   64:                   pthread_t GC_lock_holder = NO_THREAD;
   65: #               else
   66:                   pthread_mutex_t GC_allocate_ml = PTHREAD_MUTEX_INITIALIZER;
   67:                   pthread_t GC_lock_holder = NO_THREAD;
   68:                         /* Used only for assertions, and to prevent   */
   69:                         /* recursive reentry in the system call wrapper. */
   70: #               endif 
   71: #             else
   72:                   --> declare allocator lock here
   73: #             endif
   74: #          endif
   75: #       endif
   76: #     endif
   77: #   endif
   78: # endif
   79: 
   80: #if defined(NOSYS) || defined(ECOS)
   81: #undef STACKBASE
   82: #endif
   83: 
   84: /* Dont unnecessarily call GC_register_main_static_data() in case       */
   85: /* dyn_load.c isn't linked in.                                          */
   86: #ifdef DYNAMIC_LOADING
   87: # define GC_REGISTER_MAIN_STATIC_DATA() GC_register_main_static_data()
   88: #else
   89: # define GC_REGISTER_MAIN_STATIC_DATA() TRUE
   90: #endif
   91: 
   92: GC_FAR struct _GC_arrays GC_arrays /* = { 0 } */;
   93: 
   94: 
   95: GC_bool GC_debugging_started = FALSE;
   96:         /* defined here so we don't have to load debug_malloc.o */
   97: 
   98: void (*GC_check_heap) GC_PROTO((void)) = (void (*) GC_PROTO((void)))0;
   99: void (*GC_print_all_smashed) GC_PROTO((void)) = (void (*) GC_PROTO((void)))0;
  100: 
  101: void (*GC_start_call_back) GC_PROTO((void)) = (void (*) GC_PROTO((void)))0;
  102: 
  103: ptr_t GC_stackbottom = 0;
  104: 
  105: #ifdef IA64
  106:   ptr_t GC_register_stackbottom = 0;
  107: #endif
  108: 
  109: GC_bool GC_dont_gc = 0;
  110: 
  111: GC_bool GC_dont_precollect = 0;
  112: 
  113: GC_bool GC_quiet = 0;
  114: 
  115: GC_bool GC_print_stats = 0;
  116: 
  117: GC_bool GC_print_back_height = 0;
  118: 
  119: #ifndef NO_DEBUGGING
  120:   GC_bool GC_dump_regularly = 0;  /* Generate regular debugging dumps. */
  121: #endif
  122: 
  123: #ifdef KEEP_BACK_PTRS
  124:   long GC_backtraces = 0;       /* Number of random backtraces to     */
  125:                                 /* generate for each GC.          */
  126: #endif
  127: 
  128: #ifdef FIND_LEAK
  129:   int GC_find_leak = 1;
  130: #else
  131:   int GC_find_leak = 0;
  132: #endif
  133: 
  134: #ifdef ALL_INTERIOR_POINTERS
  135:   int GC_all_interior_pointers = 1;
  136: #else
  137:   int GC_all_interior_pointers = 0;
  138: #endif
  139: 
  140: long GC_large_alloc_warn_interval = 5;
  141:         /* Interval between unsuppressed warnings.     */
  142: 
  143: long GC_large_alloc_warn_suppressed = 0;
  144:         /* Number of warnings suppressed so far.       */
  145: 
  146: /*ARGSUSED*/
  147: GC_PTR GC_default_oom_fn GC_PROTO((size_t bytes_requested))
  148: {
  149:     return(0);
  150: }
  151: 
  152: GC_PTR (*GC_oom_fn) GC_PROTO((size_t bytes_requested)) = GC_default_oom_fn;
  153: 
  154: extern signed_word GC_mem_found;
  155: 
  156: void * GC_project2(arg1, arg2)
  157: void *arg1;
  158: void *arg2;
  159: {
  160:   return arg2;
  161: }
  162: 
  163: # ifdef MERGE_SIZES
  164:     /* Set things up so that GC_size_map[i] >= words(i),                */
  165:     /* but not too much bigger                                          */
  166:     /* and so that size_map contains relatively few distinct entries    */
  167:     /* This is stolen from Russ Atkinson's Cedar quantization           */
  168:     /* alogrithm (but we precompute it).                                */
  169: 
  170: 
  171:     void GC_init_size_map()
  172:     {
  173:         register unsigned i;
  174: 
  175:         /* Map size 0 to something bigger.                     */
  176:         /* This avoids problems at lower levels.               */
  177:         /* One word objects don't have to be 2 word aligned,   */
  178:         /* unless we're using mark bytes.                   */
  179:           for (i = 0; i < sizeof(word); i++) {
  180:               GC_size_map[i] = MIN_WORDS;
  181:           }
  182: #         if MIN_WORDS > 1
  183:             GC_size_map[sizeof(word)] = MIN_WORDS;
  184: #         else
  185:             GC_size_map[sizeof(word)] = ROUNDED_UP_WORDS(sizeof(word));
  186: #         endif
  187:         for (i = sizeof(word) + 1; i <= 8 * sizeof(word); i++) {
  188:             GC_size_map[i] = ALIGNED_WORDS(i);
  189:         }
  190:         for (i = 8*sizeof(word) + 1; i <= 16 * sizeof(word); i++) {
  191:               GC_size_map[i] = (ROUNDED_UP_WORDS(i) + 1) & (~1);
  192:         }
  193: #       ifdef GC_GCJ_SUPPORT
  194:            /* Make all sizes up to 32 words predictable, so that a     */
  195:            /* compiler can statically perform the same computation,    */
  196:            /* or at least a computation that results in similar size   */
  197:            /* classes.                                                 */
  198:            for (i = 16*sizeof(word) + 1; i <= 32 * sizeof(word); i++) {
  199:               GC_size_map[i] = (ROUNDED_UP_WORDS(i) + 3) & (~3);
  200:            }
  201: #       endif
  202:         /* We leave the rest of the array to be filled in on demand. */
  203:     }
  204:     
  205:     /* Fill in additional entries in GC_size_map, including the ith one */
  206:     /* We assume the ith entry is currently 0.                          */
  207:     /* Note that a filled in section of the array ending at n always    */
  208:     /* has length at least n/4.                                         */
  209:     void GC_extend_size_map(i)
  210:     word i;
  211:     {
  212:         word orig_word_sz = ROUNDED_UP_WORDS(i);
  213:         word word_sz = orig_word_sz;
  214:         register word byte_sz = WORDS_TO_BYTES(word_sz);
  215:                                 /* The size we try to preserve.         */
  216:                                 /* Close to to i, unless this would     */
  217:                                 /* introduce too many distinct sizes.   */
  218:         word smaller_than_i = byte_sz - (byte_sz >> 3);
  219:         word much_smaller_than_i = byte_sz - (byte_sz >> 2);
  220:         register word low_limit;   /* The lowest indexed entry we    */
  221:                                         /* initialize.                 */
  222:         register word j;
  223:         
  224:         if (GC_size_map[smaller_than_i] == 0) {
  225:             low_limit = much_smaller_than_i;
  226:             while (GC_size_map[low_limit] != 0) low_limit++;
  227:         } else {
  228:             low_limit = smaller_than_i + 1;
  229:             while (GC_size_map[low_limit] != 0) low_limit++;
  230:             word_sz = ROUNDED_UP_WORDS(low_limit);
  231:             word_sz += word_sz >> 3;
  232:             if (word_sz < orig_word_sz) word_sz = orig_word_sz;
  233:         }
  234: #       ifdef ALIGN_DOUBLE
  235:             word_sz += 1;
  236:             word_sz &= ~1;
  237: #       endif
  238:         if (word_sz > MAXOBJSZ) {
  239:             word_sz = MAXOBJSZ;
  240:         }
  241:         /* If we can fit the same number of larger objects in a block, */
  242:         /* do so.                                                      */ 
  243:         {
  244:             size_t number_of_objs = BODY_SZ/word_sz;
  245:             word_sz = BODY_SZ/number_of_objs;
  246: #           ifdef ALIGN_DOUBLE
  247:                 word_sz &= ~1;
  248: #           endif
  249:         }
  250:         byte_sz = WORDS_TO_BYTES(word_sz);
  251:         if (GC_all_interior_pointers) {
  252:             /* We need one extra byte; don't fill in GC_size_map[byte_sz] */
  253:             byte_sz -= EXTRA_BYTES;
  254:         }
  255: 
  256:         for (j = low_limit; j <= byte_sz; j++) GC_size_map[j] = word_sz;  
  257:     }
  258: # endif
  259: 
  260: 
  261: /*
  262:  * The following is a gross hack to deal with a problem that can occur
  263:  * on machines that are sloppy about stack frame sizes, notably SPARC.
  264:  * Bogus pointers may be written to the stack and not cleared for
  265:  * a LONG time, because they always fall into holes in stack frames
  266:  * that are not written.  We partially address this by clearing
  267:  * sections of the stack whenever we get control.
  268:  */
  269: word GC_stack_last_cleared = 0; /* GC_no when we last did this */
  270: # ifdef THREADS
  271: #   define BIG_CLEAR_SIZE 2048  /* Clear this much now and then. */
  272: #   define SMALL_CLEAR_SIZE 256 /* Clear this much every time.          */
  273: # endif
  274: # define CLEAR_SIZE 213  /* Granularity for GC_clear_stack_inner */
  275: # define DEGRADE_RATE 50
  276: 
  277: word GC_min_sp;         /* Coolest stack pointer value from which we've */
  278:                         /* already cleared the stack.                        */
  279:                         
  280: word GC_high_water;
  281:                         /* "hottest" stack pointer value we have seen        */
  282:                         /* recently.  Degrades over time.            */
  283: 
  284: word GC_words_allocd_at_reset;
  285: 
  286: #if defined(ASM_CLEAR_CODE)
  287:   extern ptr_t GC_clear_stack_inner();
  288: #else  
  289: /* Clear the stack up to about limit.  Return arg. */
  290: /*ARGSUSED*/
  291: ptr_t GC_clear_stack_inner(arg, limit)
  292: ptr_t arg;
  293: word limit;
  294: {
  295:     word dummy[CLEAR_SIZE];
  296:     
  297:     BZERO(dummy, CLEAR_SIZE*sizeof(word));
  298:     if ((word)(dummy) COOLER_THAN limit) {
  299:         (void) GC_clear_stack_inner(arg, limit);
  300:     }
  301:     /* Make sure the recursive call is not a tail call, and the bzero   */
  302:     /* call is not recognized as dead code.                             */
  303:     GC_noop1((word)dummy);
  304:     return(arg);
  305: }
  306: #endif
  307: 
  308: /* Clear some of the inaccessible part of the stack.  Returns its       */
  309: /* argument, so it can be used in a tail call position, hence clearing  */
  310: /* another frame.                                                       */
  311: ptr_t GC_clear_stack(arg)
  312: ptr_t arg;
  313: {
  314:     register word sp = (word)GC_approx_sp();  /* Hotter than actual sp */
  315: #   ifdef THREADS
  316:         word dummy[SMALL_CLEAR_SIZE];
  317:         static unsigned random_no = 0;
  318:                                /* Should be more random than it is ... */
  319:                                  /* Used to occasionally clear a bigger      */
  320:                                  /* chunk.                           */
  321: #   endif
  322:     register word limit;
  323:     
  324: #   define SLOP 400
  325:         /* Extra bytes we clear every time.  This clears our own       */
  326:         /* activation record, and should cause more frequent           */
  327:         /* clearing near the cold end of the stack, a good thing.      */
  328: #   define GC_SLOP 4000
  329:         /* We make GC_high_water this much hotter than we really saw           */
  330:         /* saw it, to cover for GC noise etc. above our current frame. */
  331: #   define CLEAR_THRESHOLD 100000
  332:         /* We restart the clearing process after this many bytes of    */
  333:         /* allocation.  Otherwise very heavily recursive programs      */
  334:         /* with sparse stacks may result in heaps that grow almost     */
  335:         /* without bounds.  As the heap gets larger, collection        */
  336:         /* frequency decreases, thus clearing frequency would decrease, */
  337:         /* thus more junk remains accessible, thus the heap gets       */
  338:         /* larger ...                                                  */
  339: # ifdef THREADS
  340:     if (++random_no % 13 == 0) {
  341:         limit = sp;
  342:         MAKE_HOTTER(limit, BIG_CLEAR_SIZE*sizeof(word));
  343:         limit &= ~0xf;  /* Make it sufficiently aligned for assembly     */
  344:                         /* implementations of GC_clear_stack_inner.   */
  345:         return GC_clear_stack_inner(arg, limit);
  346:     } else {
  347:         BZERO(dummy, SMALL_CLEAR_SIZE*sizeof(word));
  348:         return arg;
  349:     }
  350: # else
  351:     if (GC_gc_no > GC_stack_last_cleared) {
  352:         /* Start things over, so we clear the entire stack again */
  353:         if (GC_stack_last_cleared == 0) GC_high_water = (word) GC_stackbottom;
  354:         GC_min_sp = GC_high_water;
  355:         GC_stack_last_cleared = GC_gc_no;
  356:         GC_words_allocd_at_reset = GC_words_allocd;
  357:     }
  358:     /* Adjust GC_high_water */
  359:         MAKE_COOLER(GC_high_water, WORDS_TO_BYTES(DEGRADE_RATE) + GC_SLOP);
  360:         if (sp HOTTER_THAN GC_high_water) {
  361:             GC_high_water = sp;
  362:         }
  363:         MAKE_HOTTER(GC_high_water, GC_SLOP);
  364:     limit = GC_min_sp;
  365:     MAKE_HOTTER(limit, SLOP);
  366:     if (sp COOLER_THAN limit) {
  367:         limit &= ~0xf;  /* Make it sufficiently aligned for assembly     */
  368:                         /* implementations of GC_clear_stack_inner.   */
  369:         GC_min_sp = sp;
  370:         return(GC_clear_stack_inner(arg, limit));
  371:     } else if (WORDS_TO_BYTES(GC_words_allocd - GC_words_allocd_at_reset)
  372:                > CLEAR_THRESHOLD) {
  373:         /* Restart clearing process, but limit how much clearing we do. */
  374:         GC_min_sp = sp;
  375:         MAKE_HOTTER(GC_min_sp, CLEAR_THRESHOLD/4);
  376:         if (GC_min_sp HOTTER_THAN GC_high_water) GC_min_sp = GC_high_water;
  377:         GC_words_allocd_at_reset = GC_words_allocd;
  378:     }  
  379:     return(arg);
  380: # endif
  381: }
  382: 
  383: 
  384: /* Return a pointer to the base address of p, given a pointer to a      */
  385: /* an address within an object.  Return 0 o.w.                          */
  386: # ifdef __STDC__
  387:     GC_PTR GC_base(GC_PTR p)
  388: # else
  389:     GC_PTR GC_base(p)
  390:     GC_PTR p;
  391: # endif
  392: {
  393:     register word r;
  394:     register struct hblk *h;
  395:     register bottom_index *bi;
  396:     register hdr *candidate_hdr;
  397:     register word limit;
  398:     
  399:     r = (word)p;
  400:     if (!GC_is_initialized) return 0;
  401:     h = HBLKPTR(r);
  402:     GET_BI(r, bi);
  403:     candidate_hdr = HDR_FROM_BI(bi, r);
  404:     if (candidate_hdr == 0) return(0);
  405:     /* If it's a pointer to the middle of a large object, move it       */
  406:     /* to the beginning.                                                */
  407:         while (IS_FORWARDING_ADDR_OR_NIL(candidate_hdr)) {
  408:            h = FORWARDED_ADDR(h,candidate_hdr);
  409:            r = (word)h;
  410:            candidate_hdr = HDR(h);
  411:         }
  412:     if (candidate_hdr -> hb_map == GC_invalid_map) return(0);
  413:     /* Make sure r points to the beginning of the object */
  414:         r &= ~(WORDS_TO_BYTES(1) - 1);
  415:         {
  416:             register int offset = HBLKDISPL(r);
  417:             register signed_word sz = candidate_hdr -> hb_sz;
  418:             register signed_word map_entry;
  419:               
  420:             map_entry = MAP_ENTRY((candidate_hdr -> hb_map), offset);
  421:             if (map_entry > CPP_MAX_OFFSET) {
  422:                 map_entry = (signed_word)(BYTES_TO_WORDS(offset)) % sz;
  423:             }
  424:             r -= WORDS_TO_BYTES(map_entry);
  425:             limit = r + WORDS_TO_BYTES(sz);
  426:             if (limit > (word)(h + 1)
  427:                 && sz <= BYTES_TO_WORDS(HBLKSIZE)) {
  428:                 return(0);
  429:             }
  430:             if ((word)p >= limit) return(0);
  431:         }
  432:     return((GC_PTR)r);
  433: }
  434: 
  435: 
  436: /* Return the size of an object, given a pointer to its base.           */
  437: /* (For small obects this also happens to work from interior pointers,  */
  438: /* but that shouldn't be relied upon.)                                  */
  439: # ifdef __STDC__
  440:     size_t GC_size(GC_PTR p)
  441: # else
  442:     size_t GC_size(p)
  443:     GC_PTR p;
  444: # endif
  445: {
  446:     register int sz;
  447:     register hdr * hhdr = HDR(p);
  448:     
  449:     sz = WORDS_TO_BYTES(hhdr -> hb_sz);
  450:     return(sz);
  451: }
  452: 
  453: size_t GC_get_heap_size GC_PROTO(())
  454: {
  455:     return ((size_t) GC_heapsize);
  456: }
  457: 
  458: size_t GC_get_free_bytes GC_PROTO(())
  459: {
  460:     return ((size_t) GC_large_free_bytes);
  461: }
  462: 
  463: size_t GC_get_bytes_since_gc GC_PROTO(())
  464: {
  465:     return ((size_t) WORDS_TO_BYTES(GC_words_allocd));
  466: }
  467: 
  468: size_t GC_get_total_bytes GC_PROTO(())
  469: {
  470:     return ((size_t) WORDS_TO_BYTES(GC_words_allocd+GC_words_allocd_before_gc));
  471: }
  472: 
  473: GC_bool GC_is_initialized = FALSE;
  474: 
  475: void GC_init()
  476: {
  477:     DCL_LOCK_STATE;
  478:     
  479:     DISABLE_SIGNALS();
  480: 
  481: #if defined(GC_WIN32_THREADS) && !defined(GC_PTHREADS)
  482:     if (!GC_is_initialized) {
  483:       BOOL (WINAPI *pfn) (LPCRITICAL_SECTION, DWORD) = NULL;
  484:       HMODULE hK32 = GetModuleHandleA("kernel32.dll");
  485:       if (hK32)
  486:           pfn = (BOOL (WINAPI *) (LPCRITICAL_SECTION, DWORD))
  487:                 GetProcAddress (hK32,
  488:                                 "InitializeCriticalSectionAndSpinCount");
  489:       if (pfn)
  490:           pfn(&GC_allocate_ml, 4000);
  491:       else
  492:           InitializeCriticalSection (&GC_allocate_ml);
  493:     }
  494: #endif /* MSWIN32 */
  495: 
  496:     LOCK();
  497:     GC_init_inner();
  498:     UNLOCK();
  499:     ENABLE_SIGNALS();
  500: 
  501: #   if defined(PARALLEL_MARK) || defined(THREAD_LOCAL_ALLOC)
  502:         /* Make sure marker threads and started and thread local */
  503:         /* allocation is initialized, in case we didn't get     */
  504:         /* called from GC_init_parallel();                      */
  505:         {
  506:           extern void GC_init_parallel(void);
  507:           GC_init_parallel();
  508:         }
  509: #   endif /* PARALLEL_MARK || THREAD_LOCAL_ALLOC */
  510: 
  511: #   if defined(DYNAMIC_LOADING) && defined(DARWIN)
  512:     {
  513:         /* This must be called WITHOUT the allocation lock held
  514:         and before any threads are created */
  515:         extern void GC_init_dyld();
  516:         GC_init_dyld();
  517:     }
  518: #   endif
  519: }
  520: 
  521: #if defined(MSWIN32) || defined(MSWINCE)
  522:     CRITICAL_SECTION GC_write_cs;
  523: #endif
  524: 
  525: #ifdef MSWIN32
  526:     extern void GC_init_win32 GC_PROTO((void));
  527: #endif
  528: 
  529: extern void GC_setpagesize();
  530: 
  531: 
  532: #ifdef MSWIN32
  533: extern GC_bool GC_no_win32_dlls;
  534: #else
  535: # define GC_no_win32_dlls FALSE
  536: #endif
  537: 
  538: void GC_exit_check GC_PROTO((void))
  539: {
  540:    GC_gcollect();
  541: }
  542: 
  543: #ifdef SEARCH_FOR_DATA_START
  544:   extern void GC_init_linux_data_start GC_PROTO((void));
  545: #endif
  546: 
  547: #ifdef UNIX_LIKE
  548: 
  549: extern void GC_set_and_save_fault_handler GC_PROTO((void (*handler)(int)));
  550: 
  551: static void looping_handler(sig)
  552: int sig;
  553: {
  554:     GC_err_printf1("Caught signal %d: looping in handler\n", sig);
  555:     for(;;);
  556: }
  557: 
  558: static GC_bool installed_looping_handler = FALSE;
  559: 
  560: static void maybe_install_looping_handler()
  561: {
  562:     /* Install looping handler before the write fault handler, so we    */
  563:     /* handle write faults correctly.                                   */
  564:       if (!installed_looping_handler && 0 != GETENV("GC_LOOP_ON_ABORT")) {
  565:         GC_set_and_save_fault_handler(looping_handler);
  566:         installed_looping_handler = TRUE;
  567:       }
  568: }
  569: 
  570: #<