2 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
3 * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
4 * Copyright (c) 1999-2004 Hewlett-Packard Development Company, L.P.
6 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
7 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
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.
16 #include "private/gc_priv.h"
17 #include "gc_inline.h" /* for GC_malloc_kind */
22 /* Allocate reclaim list for kind: */
23 /* Return TRUE on success */
24 STATIC GC_bool GC_alloc_reclaim_list(struct obj_kind *kind)
26 struct hblk ** result = (struct hblk **)
27 GC_scratch_alloc((MAXOBJGRANULES+1) * sizeof(struct hblk *));
28 if (result == 0) return(FALSE);
29 BZERO(result, (MAXOBJGRANULES+1)*sizeof(struct hblk *));
30 kind -> ok_reclaim_list = result;
34 /* Allocate a large block of size lb bytes. */
35 /* The block is not cleared. */
36 /* Flags is 0 or IGNORE_OFF_PAGE. */
37 /* EXTRA_BYTES were already added to lb. */
38 GC_INNER ptr_t GC_alloc_large(size_t lb, int k, unsigned flags)
43 GC_bool retry = FALSE;
45 GC_ASSERT(I_HOLD_LOCK());
46 lb = ROUNDUP_GRANULE_SIZE(lb);
47 n_blocks = OBJ_SZ_TO_BLOCKS_CHECKED(lb);
48 if (!EXPECT(GC_is_initialized, TRUE)) {
50 UNLOCK(); /* just to unset GC_lock_holder */
54 /* Do our share of marking work */
55 if (GC_incremental && !GC_dont_gc) {
57 GC_collect_a_little_inner((int)n_blocks);
60 h = GC_allochblk(lb, k, flags);
64 h = GC_allochblk(lb, k, flags);
67 while (0 == h && GC_collect_or_expand(n_blocks, flags != 0, retry)) {
68 h = GC_allochblk(lb, k, flags);
74 size_t total_bytes = n_blocks * HBLKSIZE;
76 GC_large_allocd_bytes += total_bytes;
77 if (GC_large_allocd_bytes > GC_max_large_allocd_bytes)
78 GC_max_large_allocd_bytes = GC_large_allocd_bytes;
80 /* FIXME: Do we need some way to reset GC_max_large_allocd_bytes? */
81 result = h -> hb_body;
86 /* Allocate a large block of size lb bytes. Clear if appropriate. */
87 /* EXTRA_BYTES were already added to lb. */
88 STATIC ptr_t GC_alloc_large_and_clear(size_t lb, int k, unsigned flags)
92 GC_ASSERT(I_HOLD_LOCK());
93 result = GC_alloc_large(lb, k, flags);
95 && (GC_debugging_started || GC_obj_kinds[k].ok_init)) {
96 word n_blocks = OBJ_SZ_TO_BLOCKS(lb);
98 /* Clear the whole block, in case of GC_realloc call. */
99 BZERO(result, n_blocks * HBLKSIZE);
104 /* Fill in additional entries in GC_size_map, including the i-th one. */
105 /* Note that a filled in section of the array ending at n always */
106 /* has the length of at least n/4. */
107 STATIC void GC_extend_size_map(size_t i)
109 size_t orig_granule_sz = ROUNDED_UP_GRANULES(i);
111 size_t byte_sz = GRANULES_TO_BYTES(orig_granule_sz);
112 /* The size we try to preserve. */
113 /* Close to i, unless this would */
114 /* introduce too many distinct sizes. */
115 size_t smaller_than_i = byte_sz - (byte_sz >> 3);
116 size_t low_limit; /* The lowest indexed entry we initialize. */
117 size_t number_of_objs;
119 GC_ASSERT(I_HOLD_LOCK());
120 GC_ASSERT(0 == GC_size_map[i]);
121 if (0 == GC_size_map[smaller_than_i]) {
122 low_limit = byte_sz - (byte_sz >> 2); /* much smaller than i */
123 granule_sz = orig_granule_sz;
124 while (GC_size_map[low_limit] != 0)
127 low_limit = smaller_than_i + 1;
128 while (GC_size_map[low_limit] != 0)
131 granule_sz = ROUNDED_UP_GRANULES(low_limit);
132 granule_sz += granule_sz >> 3;
133 if (granule_sz < orig_granule_sz)
134 granule_sz = orig_granule_sz;
137 /* For these larger sizes, we use an even number of granules. */
138 /* This makes it easier to, e.g., construct a 16-byte-aligned */
139 /* allocator even if GRANULE_BYTES is 8. */
140 granule_sz = (granule_sz + 1) & ~1;
141 if (granule_sz > MAXOBJGRANULES)
142 granule_sz = MAXOBJGRANULES;
144 /* If we can fit the same number of larger objects in a block, do so. */
145 number_of_objs = HBLK_GRANULES / granule_sz;
146 GC_ASSERT(number_of_objs != 0);
147 granule_sz = (HBLK_GRANULES / number_of_objs) & ~1;
149 byte_sz = GRANULES_TO_BYTES(granule_sz) - EXTRA_BYTES;
150 /* We may need one extra byte; do not always */
151 /* fill in GC_size_map[byte_sz]. */
153 for (; low_limit <= byte_sz; low_limit++)
154 GC_size_map[low_limit] = granule_sz;
157 /* Allocate lb bytes for an object of kind k. */
158 /* Should not be used to directly to allocate objects */
159 /* that require special handling on allocation. */
160 GC_INNER void * GC_generic_malloc_inner(size_t lb, int k)
164 GC_ASSERT(I_HOLD_LOCK());
165 GC_ASSERT(k < MAXOBJKINDS);
167 struct obj_kind * kind = GC_obj_kinds + k;
168 size_t lg = GC_size_map[lb];
169 void ** opp = &(kind -> ok_freelist[lg]);
172 if (EXPECT(0 == op, FALSE)) {
174 if (!EXPECT(GC_is_initialized, TRUE)) {
176 UNLOCK(); /* just to unset GC_lock_holder */
179 lg = GC_size_map[lb];
182 GC_extend_size_map(lb);
183 lg = GC_size_map[lb];
187 opp = &(kind -> ok_freelist[lg]);
191 if (0 == kind -> ok_reclaim_list &&
192 !GC_alloc_reclaim_list(kind))
194 op = GC_allocobj(lg, k);
201 GC_bytes_allocd += GRANULES_TO_BYTES((word)lg);
203 op = (ptr_t)GC_alloc_large_and_clear(ADD_SLOP(lb), k, 0);
205 GC_bytes_allocd += lb;
211 #if defined(DBG_HDRS_ALL) || defined(GC_GCJ_SUPPORT) \
212 || !defined(GC_NO_FINALIZATION)
213 /* Allocate a composite object of size n bytes. The caller */
214 /* guarantees that pointers past the first page are not relevant. */
215 GC_INNER void * GC_generic_malloc_inner_ignore_off_page(size_t lb, int k)
220 GC_ASSERT(I_HOLD_LOCK());
222 return GC_generic_malloc_inner(lb, k);
223 GC_ASSERT(k < MAXOBJKINDS);
224 lb_adjusted = ADD_SLOP(lb);
225 op = GC_alloc_large_and_clear(lb_adjusted, k, IGNORE_OFF_PAGE);
227 GC_bytes_allocd += lb_adjusted;
232 #ifdef GC_COLLECT_AT_MALLOC
233 /* Parameter to force GC at every malloc of size greater or equal to */
234 /* the given value. This might be handy during debugging. */
235 # if defined(CPPCHECK)
236 size_t GC_dbg_collect_at_malloc_min_lb = 16*1024; /* e.g. */
238 size_t GC_dbg_collect_at_malloc_min_lb = (GC_COLLECT_AT_MALLOC);
242 GC_API GC_ATTR_MALLOC void * GC_CALL GC_generic_malloc(size_t lb, int k)
247 GC_ASSERT(k < MAXOBJKINDS);
248 if (EXPECT(GC_have_errors, FALSE))
249 GC_print_all_errors();
250 GC_INVOKE_FINALIZERS();
251 GC_DBG_COLLECT_AT_MALLOC(lb);
254 result = GC_generic_malloc_inner(lb, k);
262 lg = ROUNDED_UP_GRANULES(lb);
263 lb_rounded = GRANULES_TO_BYTES(lg);
264 n_blocks = OBJ_SZ_TO_BLOCKS(lb_rounded);
265 init = GC_obj_kinds[k].ok_init;
267 result = (ptr_t)GC_alloc_large(lb_rounded, k, 0);
269 if (GC_debugging_started) {
270 BZERO(result, n_blocks * HBLKSIZE);
273 /* Clear any memory that might be used for GC descriptors */
274 /* before we release the lock. */
275 ((word *)result)[0] = 0;
276 ((word *)result)[1] = 0;
277 ((word *)result)[GRANULES_TO_WORDS(lg)-1] = 0;
278 ((word *)result)[GRANULES_TO_WORDS(lg)-2] = 0;
281 GC_bytes_allocd += lb_rounded;
284 if (init && !GC_debugging_started && 0 != result) {
285 BZERO(result, n_blocks * HBLKSIZE);
289 return((*GC_get_oom_fn())(lb));
295 GC_API GC_ATTR_MALLOC void * GC_CALL GC_malloc_kind_global(size_t lb, int k)
297 GC_ASSERT(k < MAXOBJKINDS);
304 GC_DBG_COLLECT_AT_MALLOC(lb);
306 lg = GC_size_map[lb];
307 opp = &GC_obj_kinds[k].ok_freelist[lg];
309 if (EXPECT(op != NULL, TRUE)) {
313 GC_ASSERT(0 == obj_link(op)
314 || ((word)obj_link(op)
315 <= (word)GC_greatest_plausible_heap_addr
316 && (word)obj_link(op)
317 >= (word)GC_least_plausible_heap_addr));
321 GC_bytes_allocd += GRANULES_TO_BYTES((word)lg);
328 /* We make the GC_clear_stack() call a tail one, hoping to get more */
330 return GC_clear_stack(GC_generic_malloc(lb, k));
333 #if defined(THREADS) && !defined(THREAD_LOCAL_ALLOC)
334 GC_API GC_ATTR_MALLOC void * GC_CALL GC_malloc_kind(size_t lb, int k)
336 return GC_malloc_kind_global(lb, k);
340 /* Allocate lb bytes of atomic (pointer-free) data. */
341 GC_API GC_ATTR_MALLOC void * GC_CALL GC_malloc_atomic(size_t lb)
343 return GC_malloc_kind(lb, PTRFREE);
346 /* Allocate lb bytes of composite (pointerful) data. */
347 GC_API GC_ATTR_MALLOC void * GC_CALL GC_malloc(size_t lb)
349 return GC_malloc_kind(lb, NORMAL);
352 GC_API GC_ATTR_MALLOC void * GC_CALL GC_generic_malloc_uncollectable(
358 GC_ASSERT(k < MAXOBJKINDS);
363 GC_DBG_COLLECT_AT_MALLOC(lb);
364 if (EXTRA_BYTES != 0 && lb != 0) lb--;
365 /* We don't need the extra byte, since this won't be */
366 /* collected anyway. */
368 lg = GC_size_map[lb];
369 opp = &GC_obj_kinds[k].ok_freelist[lg];
371 if (EXPECT(op != NULL, TRUE)) {
374 GC_bytes_allocd += GRANULES_TO_BYTES((word)lg);
375 /* Mark bit was already set on free list. It will be */
376 /* cleared only temporarily during a collection, as a */
377 /* result of the normal free list mark bit clearing. */
378 GC_non_gc_bytes += GRANULES_TO_BYTES((word)lg);
382 op = GC_generic_malloc(lb, k);
383 /* For small objects, the free lists are completely marked. */
385 GC_ASSERT(0 == op || GC_is_marked(op));
387 op = GC_generic_malloc(lb, k);
388 if (op /* != NULL */) { /* CPPCHECK */
389 hdr * hhdr = HDR(op);
391 GC_ASSERT(((word)op & (HBLKSIZE - 1)) == 0); /* large block */
392 /* We don't need the lock here, since we have an undisguised */
393 /* pointer. We do need to hold the lock while we adjust */
396 set_mark_bit_from_hdr(hhdr, 0); /* Only object. */
398 GC_ASSERT(hhdr -> hb_n_marks == 0);
399 /* This is not guaranteed in the multi-threaded case */
400 /* because the counter could be updated before locking. */
402 hhdr -> hb_n_marks = 1;
409 /* Allocate lb bytes of pointerful, traced, but not collectible data. */
410 GC_API GC_ATTR_MALLOC void * GC_CALL GC_malloc_uncollectable(size_t lb)
412 return GC_generic_malloc_uncollectable(lb, UNCOLLECTABLE);
415 #ifdef GC_ATOMIC_UNCOLLECTABLE
416 /* Allocate lb bytes of pointer-free, untraced, uncollectible data */
417 /* This is normally roughly equivalent to the system malloc. */
418 /* But it may be useful if malloc is redefined. */
419 GC_API GC_ATTR_MALLOC void * GC_CALL
420 GC_malloc_atomic_uncollectable(size_t lb)
422 return GC_generic_malloc_uncollectable(lb, AUNCOLLECTABLE);
424 #endif /* GC_ATOMIC_UNCOLLECTABLE */
426 #if defined(REDIRECT_MALLOC) && !defined(REDIRECT_MALLOC_IN_HEADER)
432 /* Avoid unnecessary nested procedure calls here, by #defining some */
433 /* malloc replacements. Otherwise we end up saving a meaningless */
434 /* return address in the object. It also speeds things up, but it is */
435 /* admittedly quite ugly. */
436 # define GC_debug_malloc_replacement(lb) GC_debug_malloc(lb, GC_DBG_EXTRAS)
438 # if defined(CPPCHECK)
439 # define REDIRECT_MALLOC_F GC_malloc /* e.g. */
441 # define REDIRECT_MALLOC_F REDIRECT_MALLOC
444 void * malloc(size_t lb)
446 /* It might help to manually inline the GC_malloc call here. */
447 /* But any decent compiler should reduce the extra procedure call */
448 /* to at most a jump instruction in this case. */
449 # if defined(I386) && defined(GC_SOLARIS_THREADS)
450 /* Thread initialization can call malloc before we are ready for. */
451 /* It is not clear that this is enough to help matters. */
452 /* The thread implementation may well call malloc at other */
453 /* inopportune times. */
454 if (!EXPECT(GC_is_initialized, TRUE)) return sbrk(lb);
456 return (void *)REDIRECT_MALLOC_F(lb);
459 # if defined(GC_LINUX_THREADS)
460 STATIC ptr_t GC_libpthread_start = 0;
461 STATIC ptr_t GC_libpthread_end = 0;
462 STATIC ptr_t GC_libld_start = 0;
463 STATIC ptr_t GC_libld_end = 0;
465 STATIC void GC_init_lib_bounds(void)
467 IF_CANCEL(int cancel_state;)
469 if (GC_libpthread_start != 0) return;
470 DISABLE_CANCEL(cancel_state);
471 GC_init(); /* if not called yet */
472 if (!GC_text_mapping("libpthread-",
473 &GC_libpthread_start, &GC_libpthread_end)) {
474 WARN("Failed to find libpthread.so text mapping: Expect crash\n", 0);
475 /* This might still work with some versions of libpthread, */
476 /* so we don't abort. Perhaps we should. */
477 /* Generate message only once: */
478 GC_libpthread_start = (ptr_t)1;
480 if (!GC_text_mapping("ld-", &GC_libld_start, &GC_libld_end)) {
481 WARN("Failed to find ld.so text mapping: Expect crash\n", 0);
483 RESTORE_CANCEL(cancel_state);
485 # endif /* GC_LINUX_THREADS */
487 void * calloc(size_t n, size_t lb)
489 if ((lb | n) > GC_SQRT_SIZE_MAX /* fast initial test */
490 && lb && n > GC_SIZE_MAX / lb)
491 return (*GC_get_oom_fn())(GC_SIZE_MAX); /* n*lb overflow */
492 # if defined(GC_LINUX_THREADS)
493 /* libpthread allocated some memory that is only pointed to by */
494 /* mmapped thread stacks. Make sure it is not collectible. */
496 static GC_bool lib_bounds_set = FALSE;
497 ptr_t caller = (ptr_t)__builtin_return_address(0);
498 /* This test does not need to ensure memory visibility, since */
499 /* the bounds will be set when/if we create another thread. */
500 if (!EXPECT(lib_bounds_set, TRUE)) {
501 GC_init_lib_bounds();
502 lib_bounds_set = TRUE;
504 if (((word)caller >= (word)GC_libpthread_start
505 && (word)caller < (word)GC_libpthread_end)
506 || ((word)caller >= (word)GC_libld_start
507 && (word)caller < (word)GC_libld_end))
508 return GC_generic_malloc_uncollectable(n * lb, UNCOLLECTABLE);
509 /* The two ranges are actually usually adjacent, so there may */
510 /* be a way to speed this up. */
513 return (void *)REDIRECT_MALLOC_F(n * lb);
517 char *strdup(const char *s)
519 size_t lb = strlen(s) + 1;
520 char *result = (char *)REDIRECT_MALLOC_F(lb);
525 BCOPY(s, result, lb);
528 # endif /* !defined(strdup) */
529 /* If strdup is macro defined, we assume that it actually calls malloc, */
530 /* and thus the right thing will happen even without overriding it. */
531 /* This seems to be true on most Linux systems. */
534 /* This is similar to strdup(). */
535 char *strndup(const char *str, size_t size)
538 size_t len = strlen(str);
541 copy = (char *)REDIRECT_MALLOC_F(len + 1);
546 if (EXPECT(len > 0, TRUE))
547 BCOPY(str, copy, len);
551 # endif /* !strndup */
553 # undef GC_debug_malloc_replacement
555 #endif /* REDIRECT_MALLOC */
557 /* Explicitly deallocate an object p. */
558 GC_API void GC_CALL GC_free(void * p)
562 size_t sz; /* In bytes */
563 size_t ngranules; /* sz in granules */
565 struct obj_kind * ok;
568 if (p /* != NULL */) {
571 /* Required by ANSI. It's not my fault ... */
576 GC_log_printf("GC_free(%p) after GC #%lu\n",
577 p, (unsigned long)GC_gc_no);
581 # if defined(REDIRECT_MALLOC) && \
582 ((defined(NEED_CALLINFO) && defined(GC_HAVE_BUILTIN_BACKTRACE)) \
583 || defined(GC_SOLARIS_THREADS) || defined(GC_LINUX_THREADS) \
585 /* This might be called indirectly by GC_print_callers to free */
586 /* the result of backtrace_symbols. */
587 /* For Solaris, we have to redirect malloc calls during */
588 /* initialization. For the others, this seems to happen */
590 /* Don't try to deallocate that memory. */
591 if (0 == hhdr) return;
593 GC_ASSERT(GC_base(p) == p);
594 sz = (size_t)hhdr->hb_sz;
595 ngranules = BYTES_TO_GRANULES(sz);
596 knd = hhdr -> hb_obj_kind;
597 ok = &GC_obj_kinds[knd];
598 if (EXPECT(ngranules <= MAXOBJGRANULES, TRUE)) {
602 GC_bytes_freed += sz;
603 if (IS_UNCOLLECTABLE(knd)) GC_non_gc_bytes -= sz;
604 /* Its unnecessary to clear the mark bit. If the */
605 /* object is reallocated, it doesn't matter. O.w. the */
606 /* collector will do it, since it's on a free list. */
607 if (ok -> ok_init && EXPECT(sz > sizeof(word), TRUE)) {
608 BZERO((word *)p + 1, sz-sizeof(word));
610 flh = &(ok -> ok_freelist[ngranules]);
615 size_t nblocks = OBJ_SZ_TO_BLOCKS(sz);
618 GC_bytes_freed += sz;
619 if (IS_UNCOLLECTABLE(knd)) GC_non_gc_bytes -= sz;
621 GC_large_allocd_bytes -= nblocks * HBLKSIZE;
628 /* Explicitly deallocate an object p when we already hold lock. */
629 /* Only used for internally allocated objects, so we can take some */
632 GC_INNER void GC_free_inner(void * p)
636 size_t sz; /* bytes */
637 size_t ngranules; /* sz in granules */
639 struct obj_kind * ok;
643 knd = hhdr -> hb_obj_kind;
644 sz = (size_t)hhdr->hb_sz;
645 ngranules = BYTES_TO_GRANULES(sz);
646 ok = &GC_obj_kinds[knd];
647 if (ngranules <= MAXOBJGRANULES) {
650 GC_bytes_freed += sz;
651 if (IS_UNCOLLECTABLE(knd)) GC_non_gc_bytes -= sz;
652 if (ok -> ok_init && EXPECT(sz > sizeof(word), TRUE)) {
653 BZERO((word *)p + 1, sz-sizeof(word));
655 flh = &(ok -> ok_freelist[ngranules]);
659 size_t nblocks = OBJ_SZ_TO_BLOCKS(sz);
660 GC_bytes_freed += sz;
661 if (IS_UNCOLLECTABLE(knd)) GC_non_gc_bytes -= sz;
663 GC_large_allocd_bytes -= nblocks * HBLKSIZE;
670 #if defined(REDIRECT_MALLOC) && !defined(REDIRECT_FREE)
671 # define REDIRECT_FREE GC_free
674 #if defined(REDIRECT_FREE) && !defined(REDIRECT_MALLOC_IN_HEADER)
676 # if defined(CPPCHECK)
677 # define REDIRECT_FREE_F GC_free /* e.g. */
679 # define REDIRECT_FREE_F REDIRECT_FREE
685 # if defined(GC_LINUX_THREADS) && !defined(USE_PROC_FOR_LIBRARIES)
686 /* Don't bother with initialization checks. If nothing */
687 /* has been initialized, the check fails, and that's safe, */
688 /* since we have not allocated uncollectible objects neither. */
689 ptr_t caller = (ptr_t)__builtin_return_address(0);
690 /* This test does not need to ensure memory visibility, since */
691 /* the bounds will be set when/if we create another thread. */
692 if (((word)caller >= (word)GC_libpthread_start
693 && (word)caller < (word)GC_libpthread_end)
694 || ((word)caller >= (word)GC_libld_start
695 && (word)caller < (word)GC_libld_end)) {
703 #endif /* REDIRECT_FREE */