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.
7 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
8 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
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.
17 #include "private/gc_priv.h"
18 #include "gc_inline.h" /* for GC_malloc_kind */
21 * These are extra allocation routines which are likely to be less
22 * frequently used than those in malloc.c. They are separate in the
23 * hope that the .o file will be excluded from statically linked
24 * executables. We should probably break this up further.
31 # ifndef WIN32_LEAN_AND_MEAN
32 # define WIN32_LEAN_AND_MEAN 1
40 /* Some externally visible but unadvertised variables to allow access to */
41 /* free lists from inlined allocators without including gc_priv.h */
42 /* or introducing dependencies on internal data structure layouts. */
43 #include "gc_alloc_ptrs.h"
44 void ** const GC_objfreelist_ptr = GC_objfreelist;
45 void ** const GC_aobjfreelist_ptr = GC_aobjfreelist;
46 void ** const GC_uobjfreelist_ptr = GC_uobjfreelist;
47 # ifdef GC_ATOMIC_UNCOLLECTABLE
48 void ** const GC_auobjfreelist_ptr = GC_auobjfreelist;
51 GC_API int GC_CALL GC_get_kind_and_size(const void * p, size_t * psize)
56 *psize = (size_t)hhdr->hb_sz;
58 return hhdr -> hb_obj_kind;
61 GC_API GC_ATTR_MALLOC void * GC_CALL GC_generic_or_special_malloc(size_t lb,
67 return GC_malloc_kind(lb, knd);
69 # ifdef GC_ATOMIC_UNCOLLECTABLE
72 return GC_generic_malloc_uncollectable(lb, knd);
74 return GC_generic_malloc(lb, knd);
78 /* Change the size of the block pointed to by p to contain at least */
79 /* lb bytes. The object may be (and quite likely will be) moved. */
80 /* The kind (e.g. atomic) is the same as that of the old. */
81 /* Shrinking of large blocks is not implemented well. */
82 GC_API void * GC_CALL GC_realloc(void * p, size_t lb)
87 size_t sz; /* Current size in bytes */
88 size_t orig_sz; /* Original sz in bytes */
91 if (p == 0) return(GC_malloc(lb)); /* Required by ANSI */
92 if (0 == lb) /* and p != NULL */ {
100 sz = (size_t)hhdr->hb_sz;
101 obj_kind = hhdr -> hb_obj_kind;
104 if (sz > MAXOBJBYTES) {
105 /* Round it up to the next whole heap block */
106 word descr = GC_obj_kinds[obj_kind].ok_descriptor;
108 sz = (sz + HBLKSIZE-1) & ~HBLKMASK;
109 if (GC_obj_kinds[obj_kind].ok_relocate_descr)
111 /* GC_realloc might be changing the block size while */
112 /* GC_reclaim_block or GC_clear_hdr_marks is examining it. */
113 /* The change to the size field is benign, in that GC_reclaim */
114 /* (and GC_clear_hdr_marks) would work correctly with either */
115 /* value, since we are not changing the number of objects in */
116 /* the block. But seeing a half-updated value (though unlikely */
117 /* to occur in practice) could be probably bad. */
118 /* Using unordered atomic accesses on the size and hb_descr */
119 /* fields would solve the issue. (The alternate solution might */
120 /* be to initially overallocate large objects, so we do not */
121 /* have to adjust the size in GC_realloc, if they still fit. */
122 /* But that is probably more expensive, since we may end up */
123 /* scanning a bunch of zeros during GC.) */
124 # ifdef AO_HAVE_store
125 GC_STATIC_ASSERT(sizeof(hhdr->hb_sz) == sizeof(AO_t));
126 AO_store((volatile AO_t *)&hhdr->hb_sz, (AO_t)sz);
127 AO_store((volatile AO_t *)&hhdr->hb_descr, (AO_t)descr);
134 hhdr -> hb_descr = descr;
139 # ifdef MARK_BIT_PER_OBJ
140 GC_ASSERT(hhdr -> hb_inv_sz == LARGE_INV_SZ);
142 # ifdef MARK_BIT_PER_GRANULE
143 GC_ASSERT((hhdr -> hb_flags & LARGE_BLOCK) != 0
144 && hhdr -> hb_map[ANY_INDEX] == 1);
146 if (IS_UNCOLLECTABLE(obj_kind)) GC_non_gc_bytes += (sz - orig_sz);
147 /* Extra area is already cleared by GC_alloc_large_and_clear. */
149 if (ADD_SLOP(lb) <= sz) {
150 if (lb >= (sz >> 1)) {
152 /* Clear unneeded part of object to avoid bogus pointer */
154 BZERO(((ptr_t)p) + lb, orig_sz - lb);
161 result = GC_generic_or_special_malloc((word)lb, obj_kind);
162 if (result != NULL) {
163 /* In case of shrink, it could also return original object. */
164 /* But this gives the client warning of imminent disaster. */
165 BCOPY(p, result, sz);
173 # if defined(REDIRECT_MALLOC) && !defined(REDIRECT_REALLOC)
174 # define REDIRECT_REALLOC GC_realloc
177 # ifdef REDIRECT_REALLOC
179 /* As with malloc, avoid two levels of extra calls here. */
180 # define GC_debug_realloc_replacement(p, lb) \
181 GC_debug_realloc(p, lb, GC_DBG_EXTRAS)
183 # if !defined(REDIRECT_MALLOC_IN_HEADER)
184 void * realloc(void * p, size_t lb)
186 return(REDIRECT_REALLOC(p, lb));
190 # undef GC_debug_realloc_replacement
191 # endif /* REDIRECT_REALLOC */
193 /* Allocate memory such that only pointers to near the */
194 /* beginning of the object are considered. */
195 /* We avoid holding allocation lock while we clear the memory. */
196 GC_API GC_ATTR_MALLOC void * GC_CALL
197 GC_generic_malloc_ignore_off_page(size_t lb, int k)
207 return GC_generic_malloc(lb, k);
208 GC_ASSERT(k < MAXOBJKINDS);
209 lg = ROUNDED_UP_GRANULES(lb);
210 lb_rounded = GRANULES_TO_BYTES(lg);
211 n_blocks = OBJ_SZ_TO_BLOCKS(lb_rounded);
212 init = GC_obj_kinds[k].ok_init;
213 if (EXPECT(GC_have_errors, FALSE))
214 GC_print_all_errors();
215 GC_INVOKE_FINALIZERS();
216 GC_DBG_COLLECT_AT_MALLOC(lb);
218 result = (ptr_t)GC_alloc_large(ADD_SLOP(lb), k, IGNORE_OFF_PAGE);
219 if (NULL == result) {
220 GC_oom_func oom_fn = GC_oom_fn;
222 return (*oom_fn)(lb);
225 if (GC_debugging_started) {
226 BZERO(result, n_blocks * HBLKSIZE);
229 /* Clear any memory that might be used for GC descriptors */
230 /* before we release the lock. */
231 ((word *)result)[0] = 0;
232 ((word *)result)[1] = 0;
233 ((word *)result)[GRANULES_TO_WORDS(lg)-1] = 0;
234 ((word *)result)[GRANULES_TO_WORDS(lg)-2] = 0;
237 GC_bytes_allocd += lb_rounded;
239 if (init && !GC_debugging_started) {
240 BZERO(result, n_blocks * HBLKSIZE);
245 GC_API GC_ATTR_MALLOC void * GC_CALL GC_malloc_ignore_off_page(size_t lb)
247 return GC_generic_malloc_ignore_off_page(lb, NORMAL);
250 GC_API GC_ATTR_MALLOC void * GC_CALL
251 GC_malloc_atomic_ignore_off_page(size_t lb)
253 return GC_generic_malloc_ignore_off_page(lb, PTRFREE);
256 /* Increment GC_bytes_allocd from code that doesn't have direct access */
258 GC_API void GC_CALL GC_incr_bytes_allocd(size_t n)
260 GC_bytes_allocd += n;
263 /* The same for GC_bytes_freed. */
264 GC_API void GC_CALL GC_incr_bytes_freed(size_t n)
269 GC_API size_t GC_CALL GC_get_expl_freed_bytes_since_gc(void)
271 return (size_t)GC_bytes_freed;
274 # ifdef PARALLEL_MARK
275 STATIC volatile AO_t GC_bytes_allocd_tmp = 0;
276 /* Number of bytes of memory allocated since */
277 /* we released the GC lock. Instead of */
278 /* reacquiring the GC lock just to add this in, */
279 /* we add it in the next time we reacquire */
280 /* the lock. (Atomically adding it doesn't */
281 /* work, since we would have to atomically */
282 /* update it in GC_malloc, which is too */
284 # endif /* PARALLEL_MARK */
286 /* Return a list of 1 or more objects of the indicated size, linked */
287 /* through the first word in the object. This has the advantage that */
288 /* it acquires the allocation lock only once, and may greatly reduce */
289 /* time wasted contending for the allocation lock. Typical usage would */
290 /* be in a thread that requires many items of the same size. It would */
291 /* keep its own free list in thread-local storage, and call */
292 /* GC_malloc_many or friends to replenish it. (We do not round up */
293 /* object sizes, since a call indicates the intention to consume many */
294 /* objects of exactly this size.) */
295 /* We assume that the size is a multiple of GRANULE_BYTES. */
296 /* We return the free-list by assigning it to *result, since it is */
297 /* not safe to return, e.g. a linked list of pointer-free objects, */
298 /* since the collector would not retain the entire list if it were */
299 /* invoked just as we were returning. */
300 /* Note that the client should usually clear the link field. */
301 GC_API void GC_CALL GC_generic_malloc_many(size_t lb, int k, void **result)
306 size_t lw; /* Length in words. */
307 size_t lg; /* Length in granules. */
308 signed_word my_bytes_allocd = 0;
309 struct obj_kind * ok = &(GC_obj_kinds[k]);
313 GC_ASSERT(lb != 0 && (lb & (GRANULE_BYTES-1)) == 0);
316 /* Currently a single object is allocated. */
317 /* TODO: GC_dirty should be called for each linked object (but */
318 /* the last one) to support multiple objects allocation. */
322 op = GC_generic_malloc(lb, k);
323 if (EXPECT(0 != op, TRUE))
327 if (GC_is_heap_ptr(result)) {
329 REACHABLE_AFTER_DIRTY(op);
334 GC_ASSERT(k < MAXOBJKINDS);
335 lw = BYTES_TO_WORDS(lb);
336 lg = BYTES_TO_GRANULES(lb);
337 if (EXPECT(GC_have_errors, FALSE))
338 GC_print_all_errors();
339 GC_INVOKE_FINALIZERS();
340 GC_DBG_COLLECT_AT_MALLOC(lb);
341 if (!EXPECT(GC_is_initialized, TRUE)) GC_init();
343 /* Do our share of marking work */
344 if (GC_incremental && !GC_dont_gc) {
346 GC_collect_a_little_inner(1);
349 /* First see if we can reclaim a page of objects waiting to be */
351 rlh = ok -> ok_reclaim_list;
357 while ((hbp = *rlh) != 0) {
359 *rlh = hhdr -> hb_next;
360 GC_ASSERT(hhdr -> hb_sz == lb);
361 hhdr -> hb_last_reclaimed = (unsigned short) GC_gc_no;
362 # ifdef PARALLEL_MARK
364 signed_word my_bytes_allocd_tmp =
365 (signed_word)AO_load(&GC_bytes_allocd_tmp);
366 GC_ASSERT(my_bytes_allocd_tmp >= 0);
367 /* We only decrement it while holding the GC lock. */
368 /* Thus we can't accidentally adjust it down in more */
369 /* than one thread simultaneously. */
371 if (my_bytes_allocd_tmp != 0) {
372 (void)AO_fetch_and_add(&GC_bytes_allocd_tmp,
373 (AO_t)(-my_bytes_allocd_tmp));
374 GC_bytes_allocd += my_bytes_allocd_tmp;
376 GC_acquire_mark_lock();
377 ++ GC_fl_builder_count;
379 GC_release_mark_lock();
382 op = GC_reclaim_generic(hbp, hhdr, lb,
383 ok -> ok_init, 0, &my_bytes_allocd);
385 # ifdef PARALLEL_MARK
388 (void)AO_fetch_and_add(&GC_bytes_allocd_tmp,
389 (AO_t)my_bytes_allocd);
390 GC_acquire_mark_lock();
391 -- GC_fl_builder_count;
392 if (GC_fl_builder_count == 0) GC_notify_all_builder();
393 # ifdef THREAD_SANITIZER
394 GC_release_mark_lock();
396 GC_bytes_found += my_bytes_allocd;
399 GC_bytes_found += my_bytes_allocd;
400 /* The result may be inaccurate. */
401 GC_release_mark_lock();
403 (void) GC_clear_stack(0);
407 /* We also reclaimed memory, so we need to adjust */
409 GC_bytes_found += my_bytes_allocd;
410 GC_bytes_allocd += my_bytes_allocd;
413 # ifdef PARALLEL_MARK
415 GC_acquire_mark_lock();
416 -- GC_fl_builder_count;
417 if (GC_fl_builder_count == 0) GC_notify_all_builder();
418 GC_release_mark_lock();
420 /* GC lock is needed for reclaim list access. We */
421 /* must decrement fl_builder_count before reacquiring */
422 /* the lock. Hopefully this path is rare. */
427 /* Next try to use prefix of global free list if there is one. */
428 /* We don't refill it, but we need to use it up before allocating */
429 /* a new block ourselves. */
430 opp = &(GC_obj_kinds[k].ok_freelist[lg]);
431 if ( (op = *opp) != 0 ) {
434 for (p = op; p != 0; p = obj_link(p)) {
435 my_bytes_allocd += lb;
436 if ((word)my_bytes_allocd >= HBLKSIZE) {
442 GC_bytes_allocd += my_bytes_allocd;
445 /* Next try to allocate a new block worth of objects of this size. */
447 struct hblk *h = GC_allochblk(lb, k, 0);
449 if (IS_UNCOLLECTABLE(k)) GC_set_hdr_marks(HDR(h));
450 GC_bytes_allocd += HBLKSIZE - HBLKSIZE % lb;
451 # ifdef PARALLEL_MARK
453 GC_acquire_mark_lock();
454 ++ GC_fl_builder_count;
456 GC_release_mark_lock();
458 op = GC_build_fl(h, lw,
459 (ok -> ok_init || GC_debugging_started), 0);
462 GC_acquire_mark_lock();
463 -- GC_fl_builder_count;
464 if (GC_fl_builder_count == 0) GC_notify_all_builder();
465 GC_release_mark_lock();
466 (void) GC_clear_stack(0);
470 op = GC_build_fl(h, lw, (ok -> ok_init || GC_debugging_started), 0);
475 /* As a last attempt, try allocating a single object. Note that */
476 /* this may trigger a collection or expand the heap. */
477 op = GC_generic_malloc_inner(lb, k);
478 if (0 != op) obj_link(op) = 0;
483 (void) GC_clear_stack(0);
486 /* Note that the "atomic" version of this would be unsafe, since the */
487 /* links would not be seen by the collector. */
488 GC_API GC_ATTR_MALLOC void * GC_CALL GC_malloc_many(size_t lb)
492 /* Add EXTRA_BYTES and round up to a multiple of a granule. */
493 lb = SIZET_SAT_ADD(lb, EXTRA_BYTES + GRANULE_BYTES - 1)
494 & ~(GRANULE_BYTES - 1);
496 GC_generic_malloc_many(lb, NORMAL, &result);
502 /* Debug version is tricky and currently missing. */
503 GC_API GC_ATTR_MALLOC void * GC_CALL GC_memalign(size_t align, size_t lb)
509 if (align <= GRANULE_BYTES) return GC_malloc(lb);
510 if (align >= HBLKSIZE/2 || lb >= HBLKSIZE/2) {
511 if (align > HBLKSIZE) {
512 return (*GC_get_oom_fn())(LONG_MAX-1024); /* Fail */
514 return GC_malloc(lb <= HBLKSIZE? HBLKSIZE : lb);
515 /* Will be HBLKSIZE aligned. */
517 /* We could also try to make sure that the real rounded-up object size */
518 /* is a multiple of align. That would be correct up to HBLKSIZE. */
519 new_lb = SIZET_SAT_ADD(lb, align - 1);
520 result = (ptr_t)GC_malloc(new_lb);
521 /* It is OK not to check result for NULL as in that case */
522 /* GC_memalign returns NULL too since (0 + 0 % align) is 0. */
523 offset = (word)result % align;
525 offset = align - offset;
526 if (!GC_all_interior_pointers) {
527 GC_STATIC_ASSERT(VALID_OFFSET_SZ <= HBLKSIZE);
528 GC_ASSERT(offset < VALID_OFFSET_SZ);
529 GC_register_displacement(offset);
533 GC_ASSERT((word)result % align == 0);
537 /* This one exists largely to redirect posix_memalign for leaks finding. */
538 GC_API int GC_CALL GC_posix_memalign(void **memptr, size_t align, size_t lb)
540 /* Check alignment properly. */
541 size_t align_minus_one = align - 1; /* to workaround a cppcheck warning */
542 if (align < sizeof(void *) || (align_minus_one & align) != 0) {
544 return ERROR_INVALID_PARAMETER;
550 if ((*memptr = GC_memalign(align, lb)) == NULL) {
552 return ERROR_NOT_ENOUGH_MEMORY;
560 /* provide a version of strdup() that uses the collector to allocate the
561 copy of the string */
562 GC_API GC_ATTR_MALLOC char * GC_CALL GC_strdup(const char *s)
566 if (s == NULL) return NULL;
568 copy = (char *)GC_malloc_atomic(lb);
579 GC_API GC_ATTR_MALLOC char * GC_CALL GC_strndup(const char *str, size_t size)
582 size_t len = strlen(str); /* str is expected to be non-NULL */
585 copy = (char *)GC_malloc_atomic(len + 1);
592 if (EXPECT(len > 0, TRUE))
593 BCOPY(str, copy, len);
598 #ifdef GC_REQUIRE_WCSDUP
599 # include <wchar.h> /* for wcslen() */
601 GC_API GC_ATTR_MALLOC wchar_t * GC_CALL GC_wcsdup(const wchar_t *str)
603 size_t lb = (wcslen(str) + 1) * sizeof(wchar_t);
604 wchar_t *copy = (wchar_t *)GC_malloc_atomic(lb);
612 BCOPY(str, copy, lb);
615 #endif /* GC_REQUIRE_WCSDUP */
617 GC_API void * GC_CALL GC_malloc_stubborn(size_t lb)
619 return GC_malloc(lb);
622 GC_API void GC_CALL GC_change_stubborn(const void *p GC_ATTR_UNUSED)
627 GC_API void GC_CALL GC_end_stubborn_change(const void *p)
629 GC_dirty(p); /* entire object */
632 GC_API void GC_CALL GC_ptr_store_and_dirty(void *p, const void *q)
634 *(const void **)p = q;
636 REACHABLE_AFTER_DIRTY(q);