diff options
Diffstat (limited to 'graphics/asymptote/gc/mallocx.c')
-rw-r--r-- | graphics/asymptote/gc/mallocx.c | 643 |
1 files changed, 643 insertions, 0 deletions
diff --git a/graphics/asymptote/gc/mallocx.c b/graphics/asymptote/gc/mallocx.c new file mode 100644 index 0000000000..21c35e317d --- /dev/null +++ b/graphics/asymptote/gc/mallocx.c @@ -0,0 +1,643 @@ +/* + * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers + * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved. + * Copyright (c) 1996 by Silicon Graphics. All rights reserved. + * Copyright (c) 2000 by Hewlett-Packard Company. All rights reserved. + * Copyright (c) 2009-2021 Ivan Maidanski + * + * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED + * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. + * + * Permission is hereby granted to use or copy this program + * for any purpose, provided the above notices are retained on all copies. + * Permission to modify the code and to distribute modified code is granted, + * provided the above notices are retained, and a notice that the code was + * modified is included with the above copyright notice. + */ + +#include "private/gc_priv.h" +#include "gc_inline.h" /* for GC_malloc_kind */ + +/* + * These are extra allocation routines which are likely to be less + * frequently used than those in malloc.c. They are separate in the + * hope that the .o file will be excluded from statically linked + * executables. We should probably break this up further. + */ + +#include <stdio.h> +#include <string.h> + +#ifndef MSWINCE +# include <errno.h> +#endif + +/* Some externally visible but unadvertised variables to allow access to */ +/* free lists from inlined allocators without including gc_priv.h */ +/* or introducing dependencies on internal data structure layouts. */ +#include "private/gc_alloc_ptrs.h" +void ** const GC_objfreelist_ptr = GC_objfreelist; +void ** const GC_aobjfreelist_ptr = GC_aobjfreelist; +void ** const GC_uobjfreelist_ptr = GC_uobjfreelist; +# ifdef GC_ATOMIC_UNCOLLECTABLE + void ** const GC_auobjfreelist_ptr = GC_auobjfreelist; +# endif + +GC_API int GC_CALL GC_get_kind_and_size(const void * p, size_t * psize) +{ + hdr * hhdr = HDR(p); + + if (psize != NULL) { + *psize = (size_t)hhdr->hb_sz; + } + return hhdr -> hb_obj_kind; +} + +GC_API GC_ATTR_MALLOC void * GC_CALL GC_generic_or_special_malloc(size_t lb, + int knd) +{ + switch(knd) { + case PTRFREE: + case NORMAL: + return GC_malloc_kind(lb, knd); + case UNCOLLECTABLE: +# ifdef GC_ATOMIC_UNCOLLECTABLE + case AUNCOLLECTABLE: +# endif + return GC_generic_malloc_uncollectable(lb, knd); + default: + return GC_generic_malloc(lb, knd); + } +} + +/* Change the size of the block pointed to by p to contain at least */ +/* lb bytes. The object may be (and quite likely will be) moved. */ +/* The kind (e.g. atomic) is the same as that of the old. */ +/* Shrinking of large blocks is not implemented well. */ +GC_API void * GC_CALL GC_realloc(void * p, size_t lb) +{ + struct hblk * h; + hdr * hhdr; + void * result; +# if defined(_FORTIFY_SOURCE) && defined(__GNUC__) && !defined(__clang__) + volatile /* Use cleared_p instead of p as a workaround to avoid */ + /* passing alloc_size(lb) attribute associated with p */ + /* to memset (including memset call inside GC_free). */ +# endif + word cleared_p = (word)p; + size_t sz; /* Current size in bytes */ + size_t orig_sz; /* Original sz in bytes */ + int obj_kind; + + if (p == 0) return(GC_malloc(lb)); /* Required by ANSI */ + if (0 == lb) /* and p != NULL */ { +# ifndef IGNORE_FREE + GC_free(p); +# endif + return NULL; + } + h = HBLKPTR(p); + hhdr = HDR(h); + sz = (size_t)hhdr->hb_sz; + obj_kind = hhdr -> hb_obj_kind; + orig_sz = sz; + + if (sz > MAXOBJBYTES) { + /* Round it up to the next whole heap block */ + word descr = GC_obj_kinds[obj_kind].ok_descriptor; + + sz = (sz + HBLKSIZE-1) & ~HBLKMASK; + if (GC_obj_kinds[obj_kind].ok_relocate_descr) + descr += sz; + /* GC_realloc might be changing the block size while */ + /* GC_reclaim_block or GC_clear_hdr_marks is examining it. */ + /* The change to the size field is benign, in that GC_reclaim */ + /* (and GC_clear_hdr_marks) would work correctly with either */ + /* value, since we are not changing the number of objects in */ + /* the block. But seeing a half-updated value (though unlikely */ + /* to occur in practice) could be probably bad. */ + /* Using unordered atomic accesses on the size and hb_descr */ + /* fields would solve the issue. (The alternate solution might */ + /* be to initially overallocate large objects, so we do not */ + /* have to adjust the size in GC_realloc, if they still fit. */ + /* But that is probably more expensive, since we may end up */ + /* scanning a bunch of zeros during GC.) */ +# ifdef AO_HAVE_store + GC_STATIC_ASSERT(sizeof(hhdr->hb_sz) == sizeof(AO_t)); + AO_store((volatile AO_t *)&hhdr->hb_sz, (AO_t)sz); + AO_store((volatile AO_t *)&hhdr->hb_descr, (AO_t)descr); +# else + { + DCL_LOCK_STATE; + + LOCK(); + hhdr -> hb_sz = sz; + hhdr -> hb_descr = descr; + UNLOCK(); + } +# endif + +# ifdef MARK_BIT_PER_OBJ + GC_ASSERT(hhdr -> hb_inv_sz == LARGE_INV_SZ); +# endif +# ifdef MARK_BIT_PER_GRANULE + GC_ASSERT((hhdr -> hb_flags & LARGE_BLOCK) != 0 + && hhdr -> hb_map[ANY_INDEX] == 1); +# endif + if (IS_UNCOLLECTABLE(obj_kind)) GC_non_gc_bytes += (sz - orig_sz); + /* Extra area is already cleared by GC_alloc_large_and_clear. */ + } + if (ADD_SLOP(lb) <= sz) { + if (lb >= (sz >> 1)) { + if (orig_sz > lb) { + /* Clear unneeded part of object to avoid bogus pointer */ + /* tracing. */ + BZERO((ptr_t)cleared_p + lb, orig_sz - lb); + } + return(p); + } + /* shrink */ + sz = lb; + } + result = GC_generic_or_special_malloc((word)lb, obj_kind); + if (result != NULL) { + /* In case of shrink, it could also return original object. */ + /* But this gives the client warning of imminent disaster. */ + BCOPY(p, result, sz); +# ifndef IGNORE_FREE + GC_free((ptr_t)cleared_p); +# endif + } + return result; +} + +# if defined(REDIRECT_MALLOC) && !defined(REDIRECT_REALLOC) +# define REDIRECT_REALLOC GC_realloc +# endif + +# ifdef REDIRECT_REALLOC + +/* As with malloc, avoid two levels of extra calls here. */ +# define GC_debug_realloc_replacement(p, lb) \ + GC_debug_realloc(p, lb, GC_DBG_EXTRAS) + +# if !defined(REDIRECT_MALLOC_IN_HEADER) + void * realloc(void * p, size_t lb) + { + return(REDIRECT_REALLOC(p, lb)); + } +# endif + +# undef GC_debug_realloc_replacement +# endif /* REDIRECT_REALLOC */ + +/* Allocate memory such that only pointers to near the */ +/* beginning of the object are considered. */ +/* We avoid holding allocation lock while we clear the memory. */ +GC_API GC_ATTR_MALLOC void * GC_CALL + GC_generic_malloc_ignore_off_page(size_t lb, int k) +{ + void *result; + size_t lg; + size_t lb_rounded; + word n_blocks; + GC_bool init; + DCL_LOCK_STATE; + + if (SMALL_OBJ(lb)) + return GC_generic_malloc(lb, k); + GC_ASSERT(k < MAXOBJKINDS); + lg = ROUNDED_UP_GRANULES(lb); + lb_rounded = GRANULES_TO_BYTES(lg); + n_blocks = OBJ_SZ_TO_BLOCKS(lb_rounded); + init = GC_obj_kinds[k].ok_init; + if (EXPECT(get_have_errors(), FALSE)) + GC_print_all_errors(); + GC_INVOKE_FINALIZERS(); + GC_DBG_COLLECT_AT_MALLOC(lb); + LOCK(); + result = (ptr_t)GC_alloc_large(ADD_SLOP(lb), k, IGNORE_OFF_PAGE); + if (NULL == result) { + GC_oom_func oom_fn = GC_oom_fn; + UNLOCK(); + return (*oom_fn)(lb); + } + + if (GC_debugging_started) { + BZERO(result, n_blocks * HBLKSIZE); + } else { +# ifdef THREADS + /* Clear any memory that might be used for GC descriptors */ + /* before we release the lock. */ + ((word *)result)[0] = 0; + ((word *)result)[1] = 0; + ((word *)result)[GRANULES_TO_WORDS(lg)-1] = 0; + ((word *)result)[GRANULES_TO_WORDS(lg)-2] = 0; +# endif + } + GC_bytes_allocd += lb_rounded; + UNLOCK(); + if (init && !GC_debugging_started) { + BZERO(result, n_blocks * HBLKSIZE); + } + return(result); +} + +GC_API GC_ATTR_MALLOC void * GC_CALL GC_malloc_ignore_off_page(size_t lb) +{ + return GC_generic_malloc_ignore_off_page(lb, NORMAL); +} + +GC_API GC_ATTR_MALLOC void * GC_CALL + GC_malloc_atomic_ignore_off_page(size_t lb) +{ + return GC_generic_malloc_ignore_off_page(lb, PTRFREE); +} + +/* Increment GC_bytes_allocd from code that doesn't have direct access */ +/* to GC_arrays. */ +void GC_CALL GC_incr_bytes_allocd(size_t n) +{ + GC_bytes_allocd += n; +} + +/* The same for GC_bytes_freed. */ +void GC_CALL GC_incr_bytes_freed(size_t n) +{ + GC_bytes_freed += n; +} + +GC_API size_t GC_CALL GC_get_expl_freed_bytes_since_gc(void) +{ + return (size_t)GC_bytes_freed; +} + +# ifdef PARALLEL_MARK + STATIC volatile AO_t GC_bytes_allocd_tmp = 0; + /* Number of bytes of memory allocated since */ + /* we released the GC lock. Instead of */ + /* reacquiring the GC lock just to add this in, */ + /* we add it in the next time we reacquire */ + /* the lock. (Atomically adding it doesn't */ + /* work, since we would have to atomically */ + /* update it in GC_malloc, which is too */ + /* expensive.) */ +# endif /* PARALLEL_MARK */ + +/* Return a list of 1 or more objects of the indicated size, linked */ +/* through the first word in the object. This has the advantage that */ +/* it acquires the allocation lock only once, and may greatly reduce */ +/* time wasted contending for the allocation lock. Typical usage would */ +/* be in a thread that requires many items of the same size. It would */ +/* keep its own free list in thread-local storage, and call */ +/* GC_malloc_many or friends to replenish it. (We do not round up */ +/* object sizes, since a call indicates the intention to consume many */ +/* objects of exactly this size.) */ +/* We assume that the size is non-zero and a multiple of */ +/* GRANULE_BYTES, and that it already includes EXTRA_BYTES value. */ +/* We return the free-list by assigning it to *result, since it is */ +/* not safe to return, e.g. a linked list of pointer-free objects, */ +/* since the collector would not retain the entire list if it were */ +/* invoked just as we were returning. */ +/* Note that the client should usually clear the link field. */ +GC_API void GC_CALL GC_generic_malloc_many(size_t lb, int k, void **result) +{ + void *op; + void *p; + void **opp; + size_t lw; /* Length in words. */ + size_t lg; /* Length in granules. */ + signed_word my_bytes_allocd = 0; + struct obj_kind * ok = &(GC_obj_kinds[k]); + struct hblk ** rlh; + DCL_LOCK_STATE; + + GC_ASSERT(lb != 0 && (lb & (GRANULE_BYTES-1)) == 0); + /* Currently a single object is always allocated if manual VDB. */ + /* TODO: GC_dirty should be called for each linked object (but */ + /* the last one) to support multiple objects allocation. */ + if (!EXPECT(lb <= MAXOBJBYTES, TRUE) || GC_manual_vdb) { + op = GC_generic_malloc(lb - EXTRA_BYTES, k); + if (EXPECT(0 != op, TRUE)) + obj_link(op) = 0; + *result = op; +# ifndef GC_DISABLE_INCREMENTAL + if (GC_manual_vdb && GC_is_heap_ptr(result)) { + GC_dirty_inner(result); + REACHABLE_AFTER_DIRTY(op); + } +# endif + return; + } + GC_ASSERT(k < MAXOBJKINDS); + lw = BYTES_TO_WORDS(lb); + lg = BYTES_TO_GRANULES(lb); + if (EXPECT(get_have_errors(), FALSE)) + GC_print_all_errors(); + GC_INVOKE_FINALIZERS(); + GC_DBG_COLLECT_AT_MALLOC(lb - EXTRA_BYTES); + if (!EXPECT(GC_is_initialized, TRUE)) GC_init(); + LOCK(); + /* Do our share of marking work */ + if (GC_incremental && !GC_dont_gc) { + ENTER_GC(); + GC_collect_a_little_inner(1); + EXIT_GC(); + } + /* First see if we can reclaim a page of objects waiting to be */ + /* reclaimed. */ + rlh = ok -> ok_reclaim_list; + if (rlh != NULL) { + struct hblk * hbp; + hdr * hhdr; + + while ((hbp = rlh[lg]) != NULL) { + hhdr = HDR(hbp); + rlh[lg] = hhdr -> hb_next; + GC_ASSERT(hhdr -> hb_sz == lb); + hhdr -> hb_last_reclaimed = (unsigned short) GC_gc_no; +# ifdef PARALLEL_MARK + if (GC_parallel) { + signed_word my_bytes_allocd_tmp = + (signed_word)AO_load(&GC_bytes_allocd_tmp); + GC_ASSERT(my_bytes_allocd_tmp >= 0); + /* We only decrement it while holding the GC lock. */ + /* Thus we can't accidentally adjust it down in more */ + /* than one thread simultaneously. */ + + if (my_bytes_allocd_tmp != 0) { + (void)AO_fetch_and_add(&GC_bytes_allocd_tmp, + (AO_t)(-my_bytes_allocd_tmp)); + GC_bytes_allocd += my_bytes_allocd_tmp; + } + GC_acquire_mark_lock(); + ++ GC_fl_builder_count; + UNLOCK(); + GC_release_mark_lock(); + } +# endif + op = GC_reclaim_generic(hbp, hhdr, lb, + ok -> ok_init, 0, &my_bytes_allocd); + if (op != 0) { +# ifdef PARALLEL_MARK + if (GC_parallel) { + *result = op; + (void)AO_fetch_and_add(&GC_bytes_allocd_tmp, + (AO_t)my_bytes_allocd); + GC_acquire_mark_lock(); + -- GC_fl_builder_count; + if (GC_fl_builder_count == 0) GC_notify_all_builder(); +# ifdef THREAD_SANITIZER + GC_release_mark_lock(); + LOCK(); + GC_bytes_found += my_bytes_allocd; + UNLOCK(); +# else + GC_bytes_found += my_bytes_allocd; + /* The result may be inaccurate. */ + GC_release_mark_lock(); +# endif + (void) GC_clear_stack(0); + return; + } +# endif + /* We also reclaimed memory, so we need to adjust */ + /* that count. */ + GC_bytes_found += my_bytes_allocd; + GC_bytes_allocd += my_bytes_allocd; + goto out; + } +# ifdef PARALLEL_MARK + if (GC_parallel) { + GC_acquire_mark_lock(); + -- GC_fl_builder_count; + if (GC_fl_builder_count == 0) GC_notify_all_builder(); + GC_release_mark_lock(); + LOCK(); + /* GC lock is needed for reclaim list access. We */ + /* must decrement fl_builder_count before reacquiring */ + /* the lock. Hopefully this path is rare. */ + + rlh = ok -> ok_reclaim_list; /* reload rlh after locking */ + if (NULL == rlh) break; + } +# endif + } + } + /* Next try to use prefix of global free list if there is one. */ + /* We don't refill it, but we need to use it up before allocating */ + /* a new block ourselves. */ + opp = &(GC_obj_kinds[k].ok_freelist[lg]); + if ( (op = *opp) != 0 ) { + *opp = 0; + my_bytes_allocd = 0; + for (p = op; p != 0; p = obj_link(p)) { + my_bytes_allocd += lb; + if ((word)my_bytes_allocd >= HBLKSIZE) { + *opp = obj_link(p); + obj_link(p) = 0; + break; + } + } + GC_bytes_allocd += my_bytes_allocd; + goto out; + } + /* Next try to allocate a new block worth of objects of this size. */ + { + struct hblk *h = GC_allochblk(lb, k, 0); + if (h /* != NULL */) { /* CPPCHECK */ + if (IS_UNCOLLECTABLE(k)) GC_set_hdr_marks(HDR(h)); + GC_bytes_allocd += HBLKSIZE - HBLKSIZE % lb; +# ifdef PARALLEL_MARK + if (GC_parallel) { + GC_acquire_mark_lock(); + ++ GC_fl_builder_count; + UNLOCK(); + GC_release_mark_lock(); + + op = GC_build_fl(h, lw, + (ok -> ok_init || GC_debugging_started), 0); + + *result = op; + GC_acquire_mark_lock(); + -- GC_fl_builder_count; + if (GC_fl_builder_count == 0) GC_notify_all_builder(); + GC_release_mark_lock(); + (void) GC_clear_stack(0); + return; + } +# endif + op = GC_build_fl(h, lw, (ok -> ok_init || GC_debugging_started), 0); + goto out; + } + } + + /* As a last attempt, try allocating a single object. Note that */ + /* this may trigger a collection or expand the heap. */ + op = GC_generic_malloc_inner(lb - EXTRA_BYTES, k); + if (0 != op) obj_link(op) = 0; + + out: + *result = op; + UNLOCK(); + (void) GC_clear_stack(0); +} + +/* Note that the "atomic" version of this would be unsafe, since the */ +/* links would not be seen by the collector. */ +GC_API GC_ATTR_MALLOC void * GC_CALL GC_malloc_many(size_t lb) +{ + void *result; + + /* Add EXTRA_BYTES and round up to a multiple of a granule. */ + lb = SIZET_SAT_ADD(lb, EXTRA_BYTES + GRANULE_BYTES - 1) + & ~(GRANULE_BYTES - 1); + + GC_generic_malloc_many(lb, NORMAL, &result); + return result; +} + +#include <limits.h> + +/* Debug version is tricky and currently missing. */ +GC_API GC_ATTR_MALLOC void * GC_CALL GC_memalign(size_t align, size_t lb) +{ + size_t new_lb; + size_t offset; + ptr_t result; + + if (align <= GRANULE_BYTES) return GC_malloc(lb); + if (align >= HBLKSIZE/2 || lb >= HBLKSIZE/2) { + if (align > HBLKSIZE) { + return (*GC_get_oom_fn())(LONG_MAX-1024); /* Fail */ + } + return GC_malloc(lb <= HBLKSIZE? HBLKSIZE : lb); + /* Will be HBLKSIZE aligned. */ + } + /* We could also try to make sure that the real rounded-up object size */ + /* is a multiple of align. That would be correct up to HBLKSIZE. */ + new_lb = SIZET_SAT_ADD(lb, align - 1); + result = (ptr_t)GC_malloc(new_lb); + /* It is OK not to check result for NULL as in that case */ + /* GC_memalign returns NULL too since (0 + 0 % align) is 0. */ + offset = (word)result % align; + if (offset != 0) { + offset = align - offset; + if (!GC_all_interior_pointers) { + GC_STATIC_ASSERT(VALID_OFFSET_SZ <= HBLKSIZE); + GC_ASSERT(offset < VALID_OFFSET_SZ); + GC_register_displacement(offset); + } + } + result += offset; + GC_ASSERT((word)result % align == 0); + return result; +} + +/* This one exists largely to redirect posix_memalign for leaks finding. */ +GC_API int GC_CALL GC_posix_memalign(void **memptr, size_t align, size_t lb) +{ + void *p; + size_t align_minus_one = align - 1; /* to workaround a cppcheck warning */ + + /* Check alignment properly. */ + if (align < sizeof(void *) || (align_minus_one & align) != 0) { +# ifdef MSWINCE + return ERROR_INVALID_PARAMETER; +# else + return EINVAL; +# endif + } + + p = GC_memalign(align, lb); + if (EXPECT(NULL == p, FALSE)) { +# ifdef MSWINCE + return ERROR_NOT_ENOUGH_MEMORY; +# else + return ENOMEM; +# endif + } + *memptr = p; + return 0; /* success */ +} + +/* provide a version of strdup() that uses the collector to allocate the + copy of the string */ +GC_API GC_ATTR_MALLOC char * GC_CALL GC_strdup(const char *s) +{ + char *copy; + size_t lb; + if (s == NULL) return NULL; + lb = strlen(s) + 1; + copy = (char *)GC_malloc_atomic(lb); + if (NULL == copy) { +# ifndef MSWINCE + errno = ENOMEM; +# endif + return NULL; + } + BCOPY(s, copy, lb); + return copy; +} + +GC_API GC_ATTR_MALLOC char * GC_CALL GC_strndup(const char *str, size_t size) +{ + char *copy; + size_t len = strlen(str); /* str is expected to be non-NULL */ + if (len > size) + len = size; + copy = (char *)GC_malloc_atomic(len + 1); + if (copy == NULL) { +# ifndef MSWINCE + errno = ENOMEM; +# endif + return NULL; + } + if (EXPECT(len > 0, TRUE)) + BCOPY(str, copy, len); + copy[len] = '\0'; + return copy; +} + +#ifdef GC_REQUIRE_WCSDUP +# include <wchar.h> /* for wcslen() */ + + GC_API GC_ATTR_MALLOC wchar_t * GC_CALL GC_wcsdup(const wchar_t *str) + { + size_t lb = (wcslen(str) + 1) * sizeof(wchar_t); + wchar_t *copy = (wchar_t *)GC_malloc_atomic(lb); + + if (copy == NULL) { +# ifndef MSWINCE + errno = ENOMEM; +# endif + return NULL; + } + BCOPY(str, copy, lb); + return copy; + } +#endif /* GC_REQUIRE_WCSDUP */ + +#ifndef CPPCHECK + GC_API void * GC_CALL GC_malloc_stubborn(size_t lb) + { + return GC_malloc(lb); + } + + GC_API void GC_CALL GC_change_stubborn(const void *p GC_ATTR_UNUSED) + { + /* Empty. */ + } +#endif /* !CPPCHECK */ + +GC_API void GC_CALL GC_end_stubborn_change(const void *p) +{ + GC_dirty(p); /* entire object */ +} + +GC_API void GC_CALL GC_ptr_store_and_dirty(void *p, const void *q) +{ + *(const void **)p = q; + GC_dirty(p); + REACHABLE_AFTER_DIRTY(q); +} |