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