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