src/mm/boehm-gc/malloc.c

   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-2004 Hewlett-Packard Development Company, L.P.
   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
  16 #include "private/gc_priv.h"
  17
  18 #include <stdio.h>
  19 #include <string.h>
  20 #ifndef MSWINCE
  21 # include <errno.h>
  22 #endif
  23
  24 GC_INNER void GC_extend_size_map(size_t); /* in misc.c */
  25
  26 /* Allocate reclaim list for kind:      */
  27 /* Return TRUE on success               */
  28 STATIC GC_bool GC_alloc_reclaim_list(struct obj_kind *kind)
  29 {
  30     struct hblk ** result = (struct hblk **)
  31                 GC_scratch_alloc((MAXOBJGRANULES+1) * sizeof(struct hblk *));
  32     if (result == 0) return(FALSE);
  33     BZERO(result, (MAXOBJGRANULES+1)*sizeof(struct hblk *));
  34     kind -> ok_reclaim_list = result;
  35     return(TRUE);
  36 }
  37
  38 GC_INNER GC_bool GC_collect_or_expand(word needed_blocks,
  39                                       GC_bool ignore_off_page,
  40                                       GC_bool retry); /* from alloc.c */
  41
  42 /* Allocate a large block of size lb bytes.     */
  43 /* The block is not cleared.                    */
  44 /* Flags is 0 or IGNORE_OFF_PAGE.               */
  45 /* We hold the allocation lock.                 */
  46 /* EXTRA_BYTES were already added to lb.        */
  47 GC_INNER ptr_t GC_alloc_large(size_t lb, int k, unsigned flags)
  48 {
  49     struct hblk * h;
  50     word n_blocks;
  51     ptr_t result;
  52     GC_bool retry = FALSE;
  53
  54     /* Round up to a multiple of a granule. */
  55       lb = (lb + GRANULE_BYTES - 1) & ~(GRANULE_BYTES - 1);
  56     n_blocks = OBJ_SZ_TO_BLOCKS(lb);
  57     if (!GC_is_initialized) GC_init();
  58     /* Do our share of marking work */
  59         if (GC_incremental && !GC_dont_gc)
  60             GC_collect_a_little_inner((int)n_blocks);
  61     h = GC_allochblk(lb, k, flags);
  62 #   ifdef USE_MUNMAP
  63         if (0 == h) {
  64             GC_merge_unmapped();
  65             h = GC_allochblk(lb, k, flags);
  66         }
  67 #   endif
  68     while (0 == h && GC_collect_or_expand(n_blocks, flags != 0, retry)) {
  69         h = GC_allochblk(lb, k, flags);
  70         retry = TRUE;
  71     }
  72     if (h == 0) {
  73         result = 0;
  74     } else {
  75         size_t total_bytes = n_blocks * HBLKSIZE;
  76         if (n_blocks > 1) {
  77             GC_large_allocd_bytes += total_bytes;
  78             if (GC_large_allocd_bytes > GC_max_large_allocd_bytes)
  79                 GC_max_large_allocd_bytes = GC_large_allocd_bytes;
  80         }
  81         result = h -> hb_body;
  82     }
  83     return result;
  84 }
  85
  86 /* Allocate a large block of size lb bytes.  Clear if appropriate.      */
  87 /* We hold the allocation lock.                                         */
  88 /* EXTRA_BYTES were already added to lb.                                */
  89 STATIC ptr_t GC_alloc_large_and_clear(size_t lb, int k, unsigned flags)
  90 {
  91     ptr_t result = GC_alloc_large(lb, k, flags);
  92     word n_blocks = OBJ_SZ_TO_BLOCKS(lb);
  93
  94     if (0 == result) return 0;
  95     if (GC_debugging_started || GC_obj_kinds[k].ok_init) {
  96         /* Clear the whole block, in case of GC_realloc call. */
  97         BZERO(result, n_blocks * HBLKSIZE);
  98     }
  99     return result;
 100 }
 101
 102 /* allocate lb bytes for an object of kind k.   */
 103 /* Should not be used to directly to allocate   */
 104 /* objects such as STUBBORN objects that        */
 105 /* require special handling on allocation.      */
 106 /* First a version that assumes we already      */
 107 /* hold lock:                                   */
 108 GC_INNER void * GC_generic_malloc_inner(size_t lb, int k)
 109 {
 110     void *op;
 111
 112     if(SMALL_OBJ(lb)) {
 113         struct obj_kind * kind = GC_obj_kinds + k;
 114         size_t lg = GC_size_map[lb];
 115         void ** opp = &(kind -> ok_freelist[lg]);
 116
 117         if( (op = *opp) == 0 ) {
 118             if (GC_size_map[lb] == 0) {
 119               if (!GC_is_initialized) GC_init();
 120               if (GC_size_map[lb] == 0) GC_extend_size_map(lb);
 121               return(GC_generic_malloc_inner(lb, k));
 122             }
 123             if (kind -> ok_reclaim_list == 0) {
 124                 if (!GC_alloc_reclaim_list(kind)) goto out;
 125             }
 126             op = GC_allocobj(lg, k);
 127             if (op == 0) goto out;
 128         }
 129         *opp = obj_link(op);
 130         obj_link(op) = 0;
 131         GC_bytes_allocd += GRANULES_TO_BYTES(lg);
 132     } else {
 133         op = (ptr_t)GC_alloc_large_and_clear(ADD_SLOP(lb), k, 0);
 134         GC_bytes_allocd += lb;
 135     }
 136
 137 out:
 138     return op;
 139 }
 140
 141 /* Allocate a composite object of size n bytes.  The caller guarantees  */
 142 /* that pointers past the first page are not relevant.  Caller holds    */
 143 /* allocation lock.                                                     */
 144 GC_INNER void * GC_generic_malloc_inner_ignore_off_page(size_t lb, int k)
 145 {
 146     word lb_adjusted;
 147     void * op;
 148
 149     if (lb <= HBLKSIZE)
 150         return(GC_generic_malloc_inner(lb, k));
 151     lb_adjusted = ADD_SLOP(lb);
 152     op = GC_alloc_large_and_clear(lb_adjusted, k, IGNORE_OFF_PAGE);
 153     GC_bytes_allocd += lb_adjusted;
 154     return op;
 155 }
 156
 157 GC_API void * GC_CALL GC_generic_malloc(size_t lb, int k)
 158 {
 159     void * result;
 160     DCL_LOCK_STATE;
 161
 162     if (GC_have_errors) GC_print_all_errors();
 163     GC_INVOKE_FINALIZERS();
 164     if (SMALL_OBJ(lb)) {
 165         LOCK();
 166         result = GC_generic_malloc_inner((word)lb, k);
 167         UNLOCK();
 168     } else {
 169         size_t lg;
 170         size_t lb_rounded;
 171         word n_blocks;
 172         GC_bool init;
 173         lg = ROUNDED_UP_GRANULES(lb);
 174         lb_rounded = GRANULES_TO_BYTES(lg);
 175         n_blocks = OBJ_SZ_TO_BLOCKS(lb_rounded);
 176         init = GC_obj_kinds[k].ok_init;
 177         LOCK();
 178         result = (ptr_t)GC_alloc_large(lb_rounded, k, 0);
 179         if (0 != result) {
 180           if (GC_debugging_started) {
 181             BZERO(result, n_blocks * HBLKSIZE);
 182           } else {
 183 #           ifdef THREADS
 184               /* Clear any memory that might be used for GC descriptors */
 185               /* before we release the lock.                          */
 186                 ((word *)result)[0] = 0;
 187                 ((word *)result)[1] = 0;
 188                 ((word *)result)[GRANULES_TO_WORDS(lg)-1] = 0;
 189                 ((word *)result)[GRANULES_TO_WORDS(lg)-2] = 0;
 190 #           endif
 191           }
 192         }
 193         GC_bytes_allocd += lb_rounded;
 194         UNLOCK();
 195         if (init && !GC_debugging_started && 0 != result) {
 196             BZERO(result, n_blocks * HBLKSIZE);
 197         }
 198     }
 199     if (0 == result) {
 200         return((*GC_get_oom_fn())(lb));
 201     } else {
 202         return(result);
 203     }
 204 }
 205
 206 /* Allocate lb bytes of atomic (pointerfree) data */
 207 #ifdef THREAD_LOCAL_ALLOC
 208   GC_INNER void * GC_core_malloc_atomic(size_t lb)
 209 #else
 210   GC_API void * GC_CALL GC_malloc_atomic(size_t lb)
 211 #endif
 212 {
 213     void *op;
 214     void ** opp;
 215     size_t lg;
 216     DCL_LOCK_STATE;
 217
 218     if(SMALL_OBJ(lb)) {
 219         lg = GC_size_map[lb];
 220         opp = &(GC_aobjfreelist[lg]);
 221         LOCK();
 222         if( EXPECT((op = *opp) == 0, 0) ) {
 223             UNLOCK();
 224             return(GENERAL_MALLOC((word)lb, PTRFREE));
 225         }
 226         *opp = obj_link(op);
 227         GC_bytes_allocd += GRANULES_TO_BYTES(lg);
 228         UNLOCK();
 229         return((void *) op);
 230    } else {
 231        return(GENERAL_MALLOC((word)lb, PTRFREE));
 232    }
 233 }
 234
 235 /* provide a version of strdup() that uses the collector to allocate the
 236    copy of the string */
 237 GC_API char * GC_CALL GC_strdup(const char *s)
 238 {
 239   char *copy;
 240   size_t lb;
 241   if (s == NULL) return NULL;
 242   lb = strlen(s) + 1;
 243   if ((copy = GC_malloc_atomic(lb)) == NULL) {
 244 #   ifndef MSWINCE
 245       errno = ENOMEM;
 246 #   endif
 247     return NULL;
 248   }
 249 # ifndef MSWINCE
 250     strcpy(copy, s);
 251 # else
 252     /* strcpy() is deprecated in WinCE */
 253     memcpy(copy, s, lb);
 254 # endif
 255   return copy;
 256 }
 257
 258 /* Allocate lb bytes of composite (pointerful) data */
 259 #ifdef THREAD_LOCAL_ALLOC
 260   GC_INNER void * GC_core_malloc(size_t lb)
 261 #else
 262   GC_API void * GC_CALL GC_malloc(size_t lb)
 263 #endif
 264 {
 265     void *op;
 266     void **opp;
 267     size_t lg;
 268     DCL_LOCK_STATE;
 269
 270     if(SMALL_OBJ(lb)) {
 271         lg = GC_size_map[lb];
 272         opp = (void **)&(GC_objfreelist[lg]);
 273         LOCK();
 274         if( EXPECT((op = *opp) == 0, 0) ) {
 275             UNLOCK();
 276             return(GENERAL_MALLOC((word)lb, NORMAL));
 277         }
 278         GC_ASSERT(0 == obj_link(op)
 279                   || ((word)obj_link(op)
 280                         <= (word)GC_greatest_plausible_heap_addr
 281                      && (word)obj_link(op)
 282                         >= (word)GC_least_plausible_heap_addr));
 283         *opp = obj_link(op);
 284         obj_link(op) = 0;
 285         GC_bytes_allocd += GRANULES_TO_BYTES(lg);
 286         UNLOCK();
 287         return op;
 288    } else {
 289        return(GENERAL_MALLOC(lb, NORMAL));
 290    }
 291 }
 292
 293 # ifdef REDIRECT_MALLOC
 294
 295 /* Avoid unnecessary nested procedure calls here, by #defining some     */
 296 /* malloc replacements.  Otherwise we end up saving a                   */
 297 /* meaningless return address in the object.  It also speeds things up, */
 298 /* but it is admittedly quite ugly.                                     */
 299 # ifdef GC_ADD_CALLER
 300 #   define RA GC_RETURN_ADDR,
 301 # else
 302 #   define RA
 303 # endif
 304 # define GC_debug_malloc_replacement(lb) \
 305                         GC_debug_malloc(lb, RA "unknown", 0)
 306
 307 void * malloc(size_t lb)
 308 {
 309     /* It might help to manually inline the GC_malloc call here.        */
 310     /* But any decent compiler should reduce the extra procedure call   */
 311     /* to at most a jump instruction in this case.                      */
 312 #   if defined(I386) && defined(GC_SOLARIS_THREADS)
 313       /*
 314        * Thread initialisation can call malloc before
 315        * we're ready for it.
 316        * It's not clear that this is enough to help matters.
 317        * The thread implementation may well call malloc at other
 318        * inopportune times.
 319        */
 320       if (!GC_is_initialized) return sbrk(lb);
 321 #   endif /* I386 && GC_SOLARIS_THREADS */
 322     return((void *)REDIRECT_MALLOC(lb));
 323 }
 324
 325 #if defined(GC_LINUX_THREADS) /* && !defined(USE_PROC_FOR_LIBRARIES) */
 326   STATIC ptr_t GC_libpthread_start = 0;
 327   STATIC ptr_t GC_libpthread_end = 0;
 328   STATIC ptr_t GC_libld_start = 0;
 329   STATIC ptr_t GC_libld_end = 0;
 330   GC_INNER GC_bool GC_text_mapping(char *nm, ptr_t *startp, ptr_t *endp);
 331                                                 /* From os_dep.c */
 332
 333   STATIC void GC_init_lib_bounds(void)
 334   {
 335     if (GC_libpthread_start != 0) return;
 336     if (!GC_text_mapping("libpthread-",
 337                          &GC_libpthread_start, &GC_libpthread_end)) {
 338         WARN("Failed to find libpthread.so text mapping: Expect crash\n", 0);
 339         /* This might still work with some versions of libpthread,      */
 340         /* so we don't abort.  Perhaps we should.                       */
 341         /* Generate message only once:                                  */
 342           GC_libpthread_start = (ptr_t)1;
 343     }
 344     if (!GC_text_mapping("ld-", &GC_libld_start, &GC_libld_end)) {
 345         WARN("Failed to find ld.so text mapping: Expect crash\n", 0);
 346     }
 347   }
 348 #endif
 349
 350 void * calloc(size_t n, size_t lb)
 351 {
 352 #   if defined(GC_LINUX_THREADS) /* && !defined(USE_PROC_FOR_LIBRARIES) */
 353         /* libpthread allocated some memory that is only pointed to by  */
 354         /* mmapped thread stacks.  Make sure it's not collectable.      */
 355         {
 356           static GC_bool lib_bounds_set = FALSE;
 357           ptr_t caller = (ptr_t)__builtin_return_address(0);
 358           /* This test does not need to ensure memory visibility, since */
 359           /* the bounds will be set when/if we create another thread.   */
 360           if (!lib_bounds_set) {
 361             GC_init_lib_bounds();
 362             lib_bounds_set = TRUE;
 363           }
 364           if (caller >= GC_libpthread_start && caller < GC_libpthread_end
 365               || (caller >= GC_libld_start && caller < GC_libld_end))
 366             return GC_malloc_uncollectable(n*lb);
 367           /* The two ranges are actually usually adjacent, so there may */
 368           /* be a way to speed this up.                                 */
 369         }
 370 #   endif
 371     return((void *)REDIRECT_MALLOC(n*lb));
 372 }
 373
 374 #ifndef strdup
 375 # include <string.h>
 376   char *strdup(const char *s)
 377   {
 378     size_t len = strlen(s) + 1;
 379     char * result = ((char *)REDIRECT_MALLOC(len+1));
 380     if (result == 0) {
 381       errno = ENOMEM;
 382       return 0;
 383     }
 384     BCOPY(s, result, len+1);
 385     return result;
 386   }
 387 #endif /* !defined(strdup) */
 388  /* If strdup is macro defined, we assume that it actually calls malloc, */
 389  /* and thus the right thing will happen even without overriding it.     */
 390  /* This seems to be true on most Linux systems.                         */
 391
 392 #undef GC_debug_malloc_replacement
 393
 394 # endif /* REDIRECT_MALLOC */
 395
 396 /* Explicitly deallocate an object p.                           */
 397 GC_API void GC_CALL GC_free(void * p)
 398 {
 399     struct hblk *h;
 400     hdr *hhdr;
 401     size_t sz; /* In bytes */
 402     size_t ngranules;   /* sz in granules */
 403     void **flh;
 404     int knd;
 405     struct obj_kind * ok;
 406     DCL_LOCK_STATE;
 407
 408     if (p == 0) return;
 409         /* Required by ANSI.  It's not my fault ...     */
 410 #   ifdef LOG_ALLOCS
 411       GC_err_printf("GC_free(%p): %lu\n", p, (unsigned long)GC_gc_no);
 412 #   endif
 413     h = HBLKPTR(p);
 414     hhdr = HDR(h);
 415 #   if defined(REDIRECT_MALLOC) && \
 416         (defined(GC_SOLARIS_THREADS) || defined(GC_LINUX_THREADS) \
 417          || defined(MSWIN32))
 418         /* For Solaris, we have to redirect malloc calls during         */
 419         /* initialization.  For the others, this seems to happen        */
 420         /* implicitly.                                                  */
 421         /* Don't try to deallocate that memory.                         */
 422         if (0 == hhdr) return;
 423 #   endif
 424     GC_ASSERT(GC_base(p) == p);
 425     sz = hhdr -> hb_sz;
 426     ngranules = BYTES_TO_GRANULES(sz);
 427     knd = hhdr -> hb_obj_kind;
 428     ok = &GC_obj_kinds[knd];
 429     if (EXPECT((ngranules <= MAXOBJGRANULES), 1)) {
 430         LOCK();
 431         GC_bytes_freed += sz;
 432         if (IS_UNCOLLECTABLE(knd)) GC_non_gc_bytes -= sz;
 433                 /* Its unnecessary to clear the mark bit.  If the       */
 434                 /* object is reallocated, it doesn't matter.  O.w. the  */
 435                 /* collector will do it, since it's on a free list.     */
 436         if (ok -> ok_init) {
 437             BZERO((word *)p + 1, sz-sizeof(word));
 438         }
 439         flh = &(ok -> ok_freelist[ngranules]);
 440         obj_link(p) = *flh;
 441         *flh = (ptr_t)p;
 442         UNLOCK();
 443     } else {
 444         size_t nblocks = OBJ_SZ_TO_BLOCKS(sz);
 445         LOCK();
 446         GC_bytes_freed += sz;
 447         if (IS_UNCOLLECTABLE(knd)) GC_non_gc_bytes -= sz;
 448         if (nblocks > 1) {
 449           GC_large_allocd_bytes -= nblocks * HBLKSIZE;
 450         }
 451         GC_freehblk(h);
 452         UNLOCK();
 453     }
 454 }
 455
 456 /* Explicitly deallocate an object p when we already hold lock.         */
 457 /* Only used for internally allocated objects, so we can take some      */
 458 /* shortcuts.                                                           */
 459 #ifdef THREADS
 460   GC_INNER void GC_free_inner(void * p)
 461   {
 462     struct hblk *h;
 463     hdr *hhdr;
 464     size_t sz; /* bytes */
 465     size_t ngranules;  /* sz in granules */
 466     void ** flh;
 467     int knd;
 468     struct obj_kind * ok;
 469     DCL_LOCK_STATE;
 470
 471     h = HBLKPTR(p);
 472     hhdr = HDR(h);
 473     knd = hhdr -> hb_obj_kind;
 474     sz = hhdr -> hb_sz;
 475     ngranules = BYTES_TO_GRANULES(sz);
 476     ok = &GC_obj_kinds[knd];
 477     if (ngranules <= MAXOBJGRANULES) {
 478         GC_bytes_freed += sz;
 479         if (IS_UNCOLLECTABLE(knd)) GC_non_gc_bytes -= sz;
 480         if (ok -> ok_init) {
 481             BZERO((word *)p + 1, sz-sizeof(word));
 482         }
 483         flh = &(ok -> ok_freelist[ngranules]);
 484         obj_link(p) = *flh;
 485         *flh = (ptr_t)p;
 486     } else {
 487         size_t nblocks = OBJ_SZ_TO_BLOCKS(sz);
 488         GC_bytes_freed += sz;
 489         if (IS_UNCOLLECTABLE(knd)) GC_non_gc_bytes -= sz;
 490         if (nblocks > 1) {
 491           GC_large_allocd_bytes -= nblocks * HBLKSIZE;
 492         }
 493         GC_freehblk(h);
 494     }
 495   }
 496 #endif /* THREADS */
 497
 498 #if defined(REDIRECT_MALLOC) && !defined(REDIRECT_FREE)
 499 # define REDIRECT_FREE GC_free
 500 #endif
 501
 502 #ifdef REDIRECT_FREE
 503   void free(void * p)
 504   {
 505 #   if defined(GC_LINUX_THREADS) && !defined(USE_PROC_FOR_LIBRARIES)
 506         {
 507           /* Don't bother with initialization checks.  If nothing       */
 508           /* has been initialized, the check fails, and that's safe,    */
 509           /* since we haven't allocated uncollectable objects either.   */
 510           ptr_t caller = (ptr_t)__builtin_return_address(0);
 511           /* This test does not need to ensure memory visibility, since */
 512           /* the bounds will be set when/if we create another thread.   */
 513           if (caller >= GC_libpthread_start && caller < GC_libpthread_end
 514               || (caller >= GC_libld_start && caller < GC_libld_end)) {
 515             GC_free(p);
 516             return;
 517           }
 518         }
 519 #   endif
 520 #   ifndef IGNORE_FREE
 521       REDIRECT_FREE(p);
 522 #   endif
 523   }
 524 #endif /* REDIRECT_FREE */