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