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