src/mm/boehm-gc/mallocx.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) 1996 by Silicon Graphics.  All rights reserved.
   5  * Copyright (c) 2000 by Hewlett-Packard Company.  All rights reserved.
   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  * These are extra allocation routines which are likely to be less
  19  * frequently used than those in malloc.c.  They are separate in the
  20  * hope that the .o file will be excluded from statically linked
  21  * executables.  We should probably break this up further.
  22  */
  23
  24 #include "config.h"
  25
  26 #include <stdio.h>
  27 #include "private/gc_priv.h"
  28
  29 extern ptr_t GC_clear_stack();  /* in misc.c, behaves like identity */
  30 void GC_extend_size_map();      /* in misc.c. */
  31 GC_bool GC_alloc_reclaim_list();        /* in malloc.c */
  32
  33 /* Some externally visible but unadvertised variables to allow access to */
  34 /* free lists from inlined allocators without including gc_priv.h        */
  35 /* or introducing dependencies on internal data structure layouts.       */
  36 void ** const GC_objfreelist_ptr = GC_objfreelist;
  37 void ** const GC_aobjfreelist_ptr = GC_aobjfreelist;
  38 void ** const GC_uobjfreelist_ptr = GC_uobjfreelist;
  39 # ifdef ATOMIC_UNCOLLECTABLE
  40     void ** const GC_auobjfreelist_ptr = GC_auobjfreelist;
  41 # endif
  42
  43
  44 void * GC_generic_or_special_malloc(size_t lb, int knd)
  45 {
  46     switch(knd) {
  47 #     ifdef STUBBORN_ALLOC
  48         case STUBBORN:
  49             return(GC_malloc_stubborn((size_t)lb));
  50 #     endif
  51         case PTRFREE:
  52             return(GC_malloc_atomic((size_t)lb));
  53         case NORMAL:
  54             return(GC_malloc((size_t)lb));
  55         case UNCOLLECTABLE:
  56             return(GC_malloc_uncollectable((size_t)lb));
  57 #       ifdef ATOMIC_UNCOLLECTABLE
  58           case AUNCOLLECTABLE:
  59             return(GC_malloc_atomic_uncollectable((size_t)lb));
  60 #       endif /* ATOMIC_UNCOLLECTABLE */
  61         default:
  62             return(GC_generic_malloc(lb,knd));
  63     }
  64 }
  65
  66
  67 /* Change the size of the block pointed to by p to contain at least   */
  68 /* lb bytes.  The object may be (and quite likely will be) moved.     */
  69 /* The kind (e.g. atomic) is the same as that of the old.             */
  70 /* Shrinking of large blocks is not implemented well.                 */
  71 void * GC_realloc(void * p, size_t lb)
  72 {
  73     struct hblk * h;
  74     hdr * hhdr;
  75     size_t sz;   /* Current size in bytes       */
  76     size_t orig_sz;      /* Original sz in bytes        */
  77     int obj_kind;
  78
  79     if (p == 0) return(GC_malloc(lb));  /* Required by ANSI */
  80     h = HBLKPTR(p);
  81     hhdr = HDR(h);
  82     sz = hhdr -> hb_sz;
  83     obj_kind = hhdr -> hb_obj_kind;
  84     orig_sz = sz;
  85
  86     if (sz > MAXOBJBYTES) {
  87         /* Round it up to the next whole heap block */
  88           register word descr;
  89
  90           sz = (sz+HBLKSIZE-1) & (~HBLKMASK);
  91           hhdr -> hb_sz = sz;
  92           descr = GC_obj_kinds[obj_kind].ok_descriptor;
  93           if (GC_obj_kinds[obj_kind].ok_relocate_descr) descr += sz;
  94           hhdr -> hb_descr = descr;
  95 #         ifdef MARK_BIT_PER_OBJ
  96             GC_ASSERT(hhdr -> hb_inv_sz == LARGE_INV_SZ);
  97 #         else
  98             GC_ASSERT(hhdr -> hb_large_block &&
  99                       hhdr -> hb_map[ANY_INDEX] == 1);
 100 #         endif
 101           if (IS_UNCOLLECTABLE(obj_kind)) GC_non_gc_bytes += (sz - orig_sz);
 102           /* Extra area is already cleared by GC_alloc_large_and_clear. */
 103     }
 104     if (ADD_SLOP(lb) <= sz) {
 105         if (lb >= (sz >> 1)) {
 106 #           ifdef STUBBORN_ALLOC
 107                 if (obj_kind == STUBBORN) GC_change_stubborn(p);
 108 #           endif
 109             if (orig_sz > lb) {
 110               /* Clear unneeded part of object to avoid bogus pointer */
 111               /* tracing.                                             */
 112               /* Safe for stubborn objects.                           */
 113                 BZERO(((ptr_t)p) + lb, orig_sz - lb);
 114             }
 115             return(p);
 116         } else {
 117             /* shrink */
 118               void * result =
 119                         GC_generic_or_special_malloc((word)lb, obj_kind);
 120
 121               if (result == 0) return(0);
 122                   /* Could also return original object.  But this       */
 123                   /* gives the client warning of imminent disaster.     */
 124               BCOPY(p, result, lb);
 125 #             ifndef IGNORE_FREE
 126                 GC_free(p);
 127 #             endif
 128               return(result);
 129         }
 130     } else {
 131         /* grow */
 132           void * result =
 133                 GC_generic_or_special_malloc((word)lb, obj_kind);
 134
 135           if (result == 0) return(0);
 136           BCOPY(p, result, sz);
 137 #         ifndef IGNORE_FREE
 138             GC_free(p);
 139 #         endif
 140           return(result);
 141     }
 142 }
 143
 144 # if defined(REDIRECT_MALLOC) && !defined(REDIRECT_REALLOC)
 145 #   define REDIRECT_REALLOC GC_realloc
 146 # endif
 147
 148 # ifdef REDIRECT_REALLOC
 149
 150 /* As with malloc, avoid two levels of extra calls here.        */
 151 # ifdef GC_ADD_CALLER
 152 #   define RA GC_RETURN_ADDR,
 153 # else
 154 #   define RA
 155 # endif
 156 # define GC_debug_realloc_replacement(p, lb) \
 157         GC_debug_realloc(p, lb, RA "unknown", 0)
 158
 159 void * realloc(void * p, size_t lb)
 160   {
 161     return(REDIRECT_REALLOC(p, lb));
 162   }
 163
 164 # undef GC_debug_realloc_replacement
 165 # endif /* REDIRECT_REALLOC */
 166
 167
 168 /* Allocate memory such that only pointers to near the          */
 169 /* beginning of the object are considered.                      */
 170 /* We avoid holding allocation lock while we clear memory.      */
 171 void * GC_generic_malloc_ignore_off_page(size_t lb, int k)
 172 {
 173     void *result;
 174     size_t lw;
 175     size_t lb_rounded;
 176     word n_blocks;
 177     GC_bool init;
 178     DCL_LOCK_STATE;
 179
 180     if (SMALL_OBJ(lb))
 181         return(GC_generic_malloc((word)lb, k));
 182     lw = ROUNDED_UP_WORDS(lb);
 183     lb_rounded = WORDS_TO_BYTES(lw);
 184     n_blocks = OBJ_SZ_TO_BLOCKS(lb_rounded);
 185     init = GC_obj_kinds[k].ok_init;
 186     if (GC_have_errors) GC_print_all_errors();
 187     GC_INVOKE_FINALIZERS();
 188     LOCK();
 189     result = (ptr_t)GC_alloc_large(ADD_SLOP(lb), k, IGNORE_OFF_PAGE);
 190     if (0 != result) {
 191         if (GC_debugging_started) {
 192             BZERO(result, n_blocks * HBLKSIZE);
 193         } else {
 194 #           ifdef THREADS
 195               /* Clear any memory that might be used for GC descriptors */
 196               /* before we release the lock.                          */
 197                 ((word *)result)[0] = 0;
 198                 ((word *)result)[1] = 0;
 199                 ((word *)result)[lw-1] = 0;
 200                 ((word *)result)[lw-2] = 0;
 201 #           endif
 202         }
 203     }
 204     GC_bytes_allocd += lb_rounded;
 205     UNLOCK();
 206     if (0 == result) {
 207         return((*GC_oom_fn)(lb));
 208     } else {
 209         if (init && !GC_debugging_started) {
 210             BZERO(result, n_blocks * HBLKSIZE);
 211         }
 212         return(result);
 213     }
 214 }
 215
 216 void * GC_malloc_ignore_off_page(size_t lb)
 217 {
 218     return((void *)GC_generic_malloc_ignore_off_page(lb, NORMAL));
 219 }
 220
 221 void * GC_malloc_atomic_ignore_off_page(size_t lb)
 222 {
 223     return((void *)GC_generic_malloc_ignore_off_page(lb, PTRFREE));
 224 }
 225
 226 /* Increment GC_bytes_allocd from code that doesn't have direct access  */
 227 /* to GC_arrays.                                                        */
 228 void GC_incr_bytes_allocd(size_t n)
 229 {
 230     GC_bytes_allocd += n;
 231 }
 232
 233 /* The same for GC_bytes_freed.                         */
 234 void GC_incr_bytes_freed(size_t n)
 235 {
 236     GC_bytes_freed += n;
 237 }
 238
 239 #if defined(THREADS)
 240
 241 extern signed_word GC_bytes_found;   /* Protected by GC lock.  */
 242
 243 #ifdef PARALLEL_MARK
 244 volatile signed_word GC_bytes_allocd_tmp = 0;
 245                         /* Number of bytes of memory allocated since    */
 246                         /* we released the GC lock.  Instead of         */
 247                         /* reacquiring the GC lock just to add this in, */
 248                         /* we add it in the next time we reacquire      */
 249                         /* the lock.  (Atomically adding it doesn't     */
 250                         /* work, since we would have to atomically      */
 251                         /* update it in GC_malloc, which is too         */
 252                         /* expensive.)                                   */
 253 #endif /* PARALLEL_MARK */
 254
 255 /* Return a list of 1 or more objects of the indicated size, linked     */
 256 /* through the first word in the object.  This has the advantage that   */
 257 /* it acquires the allocation lock only once, and may greatly reduce    */
 258 /* time wasted contending for the allocation lock.  Typical usage would */
 259 /* be in a thread that requires many items of the same size.  It would  */
 260 /* keep its own free list in thread-local storage, and call             */
 261 /* GC_malloc_many or friends to replenish it.  (We do not round up      */
 262 /* object sizes, since a call indicates the intention to consume many   */
 263 /* objects of exactly this size.)                                       */
 264 /* We assume that the size is a multiple of GRANULE_BYTES.              */
 265 /* We return the free-list by assigning it to *result, since it is      */
 266 /* not safe to return, e.g. a linked list of pointer-free objects,      */
 267 /* since the collector would not retain the entire list if it were      */
 268 /* invoked just as we were returning.                                   */
 269 /* Note that the client should usually clear the link field.            */
 270 void GC_generic_malloc_many(size_t lb, int k, void **result)
 271 {
 272 void *op;
 273 void *p;
 274 void **opp;
 275 size_t lw;      /* Length in words.     */
 276 size_t lg;      /* Length in granules.  */
 277 signed_word my_bytes_allocd = 0;
 278 struct obj_kind * ok = &(GC_obj_kinds[k]);
 279 DCL_LOCK_STATE;
 280
 281     GC_ASSERT((lb & (GRANULE_BYTES-1)) == 0);
 282     if (!SMALL_OBJ(lb)) {
 283         op = GC_generic_malloc(lb, k);
 284         if(0 != op) obj_link(op) = 0;
 285         *result = op;
 286         return;
 287     }
 288     lw = BYTES_TO_WORDS(lb);
 289     lg = BYTES_TO_GRANULES(lb);
 290     if (GC_have_errors) GC_print_all_errors();
 291     GC_INVOKE_FINALIZERS();
 292     LOCK();
 293     if (!GC_is_initialized) GC_init_inner();
 294     /* Do our share of marking work */
 295       if (GC_incremental && !GC_dont_gc) {
 296         ENTER_GC();
 297         GC_collect_a_little_inner(1);
 298         EXIT_GC();
 299       }
 300     /* First see if we can reclaim a page of objects waiting to be */
 301     /* reclaimed.                                                  */
 302     {
 303         struct hblk ** rlh = ok -> ok_reclaim_list;
 304         struct hblk * hbp;
 305         hdr * hhdr;
 306
 307         rlh += lg;
 308         while ((hbp = *rlh) != 0) {
 309             hhdr = HDR(hbp);
 310             *rlh = hhdr -> hb_next;
 311             GC_ASSERT(hhdr -> hb_sz == lb);
 312             hhdr -> hb_last_reclaimed = (unsigned short) GC_gc_no;
 313 #           ifdef PARALLEL_MARK
 314                 {
 315                   signed_word my_bytes_allocd_tmp = GC_bytes_allocd_tmp;
 316
 317                   GC_ASSERT(my_bytes_allocd_tmp >= 0);
 318                   /* We only decrement it while holding the GC lock.    */
 319                   /* Thus we can't accidentally adjust it down in more  */
 320                   /* than one thread simultaneously.                    */
 321                   if (my_bytes_allocd_tmp != 0) {
 322                     (void)AO_fetch_and_add(
 323                                 (volatile AO_t *)(&GC_bytes_allocd_tmp),
 324                                 (AO_t)(-my_bytes_allocd_tmp));
 325                     GC_bytes_allocd += my_bytes_allocd_tmp;
 326                   }
 327                 }
 328                 GC_acquire_mark_lock();
 329                 ++ GC_fl_builder_count;
 330                 UNLOCK();
 331                 GC_release_mark_lock();
 332 #           endif
 333             op = GC_reclaim_generic(hbp, hhdr, lb,
 334                                     ok -> ok_init, 0, &my_bytes_allocd);
 335             if (op != 0) {
 336               /* We also reclaimed memory, so we need to adjust         */
 337               /* that count.                                            */
 338               /* This should be atomic, so the results may be           */
 339               /* inaccurate.                                            */
 340               GC_bytes_found += my_bytes_allocd;
 341 #             ifdef PARALLEL_MARK
 342                 *result = op;
 343                 (void)AO_fetch_and_add(
 344                                 (volatile AO_t *)(&GC_bytes_allocd_tmp),
 345                                 (AO_t)(my_bytes_allocd));
 346                 GC_acquire_mark_lock();
 347                 -- GC_fl_builder_count;
 348                 if (GC_fl_builder_count == 0) GC_notify_all_builder();
 349                 GC_release_mark_lock();
 350                 (void) GC_clear_stack(0);
 351                 return;
 352 #             else
 353                 GC_bytes_allocd += my_bytes_allocd;
 354                 goto out;
 355 #             endif
 356             }
 357 #           ifdef PARALLEL_MARK
 358               GC_acquire_mark_lock();
 359               -- GC_fl_builder_count;
 360               if (GC_fl_builder_count == 0) GC_notify_all_builder();
 361               GC_release_mark_lock();
 362               LOCK();
 363               /* GC lock is needed for reclaim list access.     We      */
 364               /* must decrement fl_builder_count before reaquiring GC   */
 365               /* lock.  Hopefully this path is rare.                    */
 366 #           endif
 367         }
 368     }
 369     /* Next try to use prefix of global free list if there is one.      */
 370     /* We don't refill it, but we need to use it up before allocating   */
 371     /* a new block ourselves.                                           */
 372       opp = &(GC_obj_kinds[k].ok_freelist[lg]);
 373       if ( (op = *opp) != 0 ) {
 374         *opp = 0;
 375         my_bytes_allocd = 0;
 376         for (p = op; p != 0; p = obj_link(p)) {
 377           my_bytes_allocd += lb;
 378           if (my_bytes_allocd >= HBLKSIZE) {
 379             *opp = obj_link(p);
 380             obj_link(p) = 0;
 381             break;
 382           }
 383         }
 384         GC_bytes_allocd += my_bytes_allocd;
 385         goto out;
 386       }
 387     /* Next try to allocate a new block worth of objects of this size.  */
 388     {
 389         struct hblk *h = GC_allochblk(lb, k, 0);
 390         if (h != 0) {
 391           if (IS_UNCOLLECTABLE(k)) GC_set_hdr_marks(HDR(h));
 392           GC_bytes_allocd += HBLKSIZE - HBLKSIZE % lb;
 393 #         ifdef PARALLEL_MARK
 394             GC_acquire_mark_lock();
 395             ++ GC_fl_builder_count;
 396             UNLOCK();
 397             GC_release_mark_lock();
 398 #         endif
 399
 400           op = GC_build_fl(h, lw, ok -> ok_init, 0);
 401 #         ifdef PARALLEL_MARK
 402             *result = op;
 403             GC_acquire_mark_lock();
 404             -- GC_fl_builder_count;
 405             if (GC_fl_builder_count == 0) GC_notify_all_builder();
 406             GC_release_mark_lock();
 407             (void) GC_clear_stack(0);
 408             return;
 409 #         else
 410             goto out;
 411 #         endif
 412         }
 413     }
 414
 415     /* As a last attempt, try allocating a single object.  Note that    */
 416     /* this may trigger a collection or expand the heap.                */
 417       op = GC_generic_malloc_inner(lb, k);
 418       if (0 != op) obj_link(op) = 0;
 419
 420   out:
 421     *result = op;
 422     UNLOCK();
 423     (void) GC_clear_stack(0);
 424 }
 425
 426 void * GC_malloc_many(size_t lb)
 427 {
 428     void *result;
 429     GC_generic_malloc_many(((lb + EXTRA_BYTES + GRANULE_BYTES-1)
 430                            & ~(GRANULE_BYTES-1)),
 431                            NORMAL, &result);
 432     return result;
 433 }
 434
 435 /* Note that the "atomic" version of this would be unsafe, since the    */
 436 /* links would not be seen by the collector.                            */
 437 # endif
 438
 439 /* Allocate lb bytes of pointerful, traced, but not collectable data */
 440 void * GC_malloc_uncollectable(size_t lb)
 441 {
 442     void *op;
 443     void **opp;
 444     size_t lg;
 445     DCL_LOCK_STATE;
 446
 447     if( SMALL_OBJ(lb) ) {
 448         if (EXTRA_BYTES != 0 && lb != 0) lb--;
 449                   /* We don't need the extra byte, since this won't be  */
 450                   /* collected anyway.                                  */
 451         lg = GC_size_map[lb];
 452         opp = &(GC_uobjfreelist[lg]);
 453         LOCK();
 454         if( (op = *opp) != 0 ) {
 455             /* See above comment on signals.    */
 456             *opp = obj_link(op);
 457             obj_link(op) = 0;
 458             GC_bytes_allocd += GRANULES_TO_BYTES(lg);
 459             /* Mark bit ws already set on free list.  It will be        */
 460             /* cleared only temporarily during a collection, as a       */
 461             /* result of the normal free list mark bit clearing.        */
 462             GC_non_gc_bytes += GRANULES_TO_BYTES(lg);
 463             UNLOCK();
 464         } else {
 465             UNLOCK();
 466             op = (ptr_t)GC_generic_malloc((word)lb, UNCOLLECTABLE);
 467             /* For small objects, the free lists are completely marked. */
 468         }
 469         GC_ASSERT(0 == op || GC_is_marked(op));
 470         return((void *) op);
 471     } else {
 472         hdr * hhdr;
 473
 474         op = (ptr_t)GC_generic_malloc((word)lb, UNCOLLECTABLE);
 475         if (0 == op) return(0);
 476
 477         GC_ASSERT(((word)op & (HBLKSIZE - 1)) == 0); /* large block */
 478         hhdr = HDR((struct hbklk *)op);
 479         /* We don't need the lock here, since we have an undisguised    */
 480         /* pointer.  We do need to hold the lock while we adjust        */
 481         /* mark bits.                                                   */
 482         lb = hhdr -> hb_sz;
 483         LOCK();
 484         set_mark_bit_from_hdr(hhdr, 0); /* Only object. */
 485         GC_ASSERT(hhdr -> hb_n_marks == 0);
 486         hhdr -> hb_n_marks = 1;
 487         UNLOCK();
 488         return((void *) op);
 489     }
 490 }
 491
 492 /* Not well tested nor integrated.      */
 493 /* Debug version is tricky and currently missing.       */
 494 #include <limits.h>
 495
 496 void * GC_memalign(size_t align, size_t lb)
 497 {
 498     size_t new_lb;
 499     size_t offset;
 500     ptr_t result;
 501
 502     if (align <= GRANULE_BYTES) return GC_malloc(lb);
 503     if (align >= HBLKSIZE/2 || lb >= HBLKSIZE/2) {
 504         if (align > HBLKSIZE) return GC_oom_fn(LONG_MAX-1024) /* Fail */;
 505         return GC_malloc(lb <= HBLKSIZE? HBLKSIZE : lb);
 506             /* Will be HBLKSIZE aligned.        */
 507     }
 508     /* We could also try to make sure that the real rounded-up object size */
 509     /* is a multiple of align.  That would be correct up to HBLKSIZE.      */
 510     new_lb = lb + align - 1;
 511     result = GC_malloc(new_lb);
 512     offset = (word)result % align;
 513     if (offset != 0) {
 514         offset = align - offset;
 515         if (!GC_all_interior_pointers) {
 516             if (offset >= VALID_OFFSET_SZ) return GC_malloc(HBLKSIZE);
 517             GC_register_displacement(offset);
 518         }
 519     }
 520     result = (void *) ((ptr_t)result + offset);
 521     GC_ASSERT((word)result % align == 0);
 522     return result;
 523 }
 524
 525 # ifdef ATOMIC_UNCOLLECTABLE
 526 /* Allocate lb bytes of pointerfree, untraced, uncollectable data       */
 527 /* This is normally roughly equivalent to the system malloc.            */
 528 /* But it may be useful if malloc is redefined.                         */
 529 void * GC_malloc_atomic_uncollectable(size_t lb)
 530 {
 531     void *op;
 532     void **opp;
 533     size_t lg;
 534     DCL_LOCK_STATE;
 535
 536     if( SMALL_OBJ(lb) ) {
 537         if (EXTRA_BYTES != 0 && lb != 0) lb--;
 538                   /* We don't need the extra byte, since this won't be  */
 539                   /* collected anyway.                                  */
 540         lg = GC_size_map[lb];
 541         opp = &(GC_auobjfreelist[lg]);
 542         LOCK();
 543         if( (op = *opp) != 0 ) {
 544             /* See above comment on signals.    */
 545             *opp = obj_link(op);
 546             obj_link(op) = 0;
 547             GC_bytes_allocd += GRANULES_TO_BYTES(lg);
 548             /* Mark bit was already set while object was on free list. */
 549             GC_non_gc_bytes += GRANULES_TO_BYTES(lg);
 550             UNLOCK();
 551         } else {
 552             UNLOCK();
 553             op = (ptr_t)GC_generic_malloc(lb, AUNCOLLECTABLE);
 554         }
 555         GC_ASSERT(0 == op || GC_is_marked(op));
 556         return((void *) op);
 557     } else {
 558         hdr * hhdr;
 559
 560         op = (ptr_t)GC_generic_malloc(lb, AUNCOLLECTABLE);
 561         if (0 == op) return(0);
 562
 563         GC_ASSERT(((word)op & (HBLKSIZE - 1)) == 0);
 564         hhdr = HDR((struct hbklk *)op);
 565         lb = hhdr -> hb_sz;
 566
 567         LOCK();
 568         set_mark_bit_from_hdr(hhdr, 0); /* Only object. */
 569         GC_ASSERT(hhdr -> hb_n_marks == 0);
 570         hhdr -> hb_n_marks = 1;
 571         UNLOCK();
 572         return((void *) op);
 573     }
 574 }
 575
 576 #endif /* ATOMIC_UNCOLLECTABLE */