2 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
3 * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
5 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
6 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
8 * Permission is hereby granted to use or copy this program
9 * for any purpose, provided the above notices are retained on all copies.
10 * Permission to modify the code and to distribute modified code is granted,
11 * provided the above notices are retained, and a notice that the code was
12 * modified is included with the above copyright notice.
14 /* Boehm, July 31, 1995 5:02 pm PDT */
20 #define I_HIDE_POINTERS /* To make GC_call_with_alloc_lock visible */
23 #ifdef SOLARIS_THREADS
24 # include <sys/syscall.h>
32 # include "il/PCR_IL.h"
33 PCR_Th_ML GC_allocate_ml
;
36 /* Critical section counter is defined in the M3 runtime */
37 /* That's all we use. */
39 # ifdef SOLARIS_THREADS
40 mutex_t GC_allocate_ml
; /* Implicitly initialized. */
43 GC_API CRITICAL_SECTION GC_allocate_ml
;
45 # if defined(IRIX_THREADS) || defined(IRIX_JDK_THREADS) \
46 || (defined(LINUX_THREADS) && defined(USE_SPIN_LOCK))
47 pthread_t GC_lock_holder
= NO_THREAD
;
49 # if defined(HPUX_THREADS) \
50 || defined(LINUX_THREADS) && !defined(USE_SPIN_LOCK)
51 pthread_mutex_t GC_allocate_ml
= PTHREAD_MUTEX_INITIALIZER
;
53 --> declare allocator lock here
66 GC_FAR
struct _GC_arrays GC_arrays
/* = { 0 } */;
69 GC_bool GC_debugging_started
= FALSE
;
70 /* defined here so we don't have to load debug_malloc.o */
72 void (*GC_check_heap
)() = (void (*)())0;
74 void (*GC_start_call_back
)() = (void (*)())0;
76 ptr_t GC_stackbottom
= 0;
78 GC_bool GC_dont_gc
= 0;
89 GC_PTR GC_default_oom_fn
GC_PROTO((size_t bytes_requested
))
94 GC_PTR (*GC_oom_fn
) GC_PROTO((size_t bytes_requested
)) = GC_default_oom_fn
;
96 extern signed_word GC_mem_found
;
99 /* Set things up so that GC_size_map[i] >= words(i), */
100 /* but not too much bigger */
101 /* and so that size_map contains relatively few distinct entries */
102 /* This is stolen from Russ Atkinson's Cedar quantization */
103 /* alogrithm (but we precompute it). */
106 void GC_init_size_map()
110 /* Map size 0 to 1. This avoids problems at lower levels. */
112 /* One word objects don't have to be 2 word aligned. */
113 for (i
= 1; i
< sizeof(word
); i
++) {
116 GC_size_map
[sizeof(word
)] = ROUNDED_UP_WORDS(sizeof(word
));
117 for (i
= sizeof(word
) + 1; i
<= 8 * sizeof(word
); i
++) {
119 GC_size_map
[i
] = (ROUNDED_UP_WORDS(i
) + 1) & (~1);
121 GC_size_map
[i
] = ROUNDED_UP_WORDS(i
);
124 for (i
= 8*sizeof(word
) + 1; i
<= 16 * sizeof(word
); i
++) {
125 GC_size_map
[i
] = (ROUNDED_UP_WORDS(i
) + 1) & (~1);
127 # ifdef GC_GCJ_SUPPORT
128 /* Make all sizes up to 32 words predictable, so that a */
129 /* compiler can statically perform the same computation, */
130 /* or at least a computation that results in similar size */
132 for (i
= 16*sizeof(word
) + 1; i
<= 32 * sizeof(word
); i
++) {
133 GC_size_map
[i
] = (ROUNDED_UP_WORDS(i
) + 3) & (~3);
136 /* We leave the rest of the array to be filled in on demand. */
139 /* Fill in additional entries in GC_size_map, including the ith one */
140 /* We assume the ith entry is currently 0. */
141 /* Note that a filled in section of the array ending at n always */
142 /* has length at least n/4. */
143 void GC_extend_size_map(i
)
146 word orig_word_sz
= ROUNDED_UP_WORDS(i
);
147 word word_sz
= orig_word_sz
;
148 register word byte_sz
= WORDS_TO_BYTES(word_sz
);
149 /* The size we try to preserve. */
150 /* Close to to i, unless this would */
151 /* introduce too many distinct sizes. */
152 word smaller_than_i
= byte_sz
- (byte_sz
>> 3);
153 word much_smaller_than_i
= byte_sz
- (byte_sz
>> 2);
154 register word low_limit
; /* The lowest indexed entry we */
158 if (GC_size_map
[smaller_than_i
] == 0) {
159 low_limit
= much_smaller_than_i
;
160 while (GC_size_map
[low_limit
] != 0) low_limit
++;
162 low_limit
= smaller_than_i
+ 1;
163 while (GC_size_map
[low_limit
] != 0) low_limit
++;
164 word_sz
= ROUNDED_UP_WORDS(low_limit
);
165 word_sz
+= word_sz
>> 3;
166 if (word_sz
< orig_word_sz
) word_sz
= orig_word_sz
;
172 if (word_sz
> MAXOBJSZ
) {
175 /* If we can fit the same number of larger objects in a block, */
178 size_t number_of_objs
= BODY_SZ
/word_sz
;
179 word_sz
= BODY_SZ
/number_of_objs
;
184 byte_sz
= WORDS_TO_BYTES(word_sz
);
185 # ifdef ADD_BYTE_AT_END
186 /* We need one extra byte; don't fill in GC_size_map[byte_sz] */
190 for (j
= low_limit
; j
<= byte_sz
; j
++) GC_size_map
[j
] = word_sz
;
196 * The following is a gross hack to deal with a problem that can occur
197 * on machines that are sloppy about stack frame sizes, notably SPARC.
198 * Bogus pointers may be written to the stack and not cleared for
199 * a LONG time, because they always fall into holes in stack frames
200 * that are not written. We partially address this by clearing
201 * sections of the stack whenever we get control.
203 word GC_stack_last_cleared
= 0; /* GC_no when we last did this */
205 # define CLEAR_SIZE 2048
207 # define CLEAR_SIZE 213
209 # define DEGRADE_RATE 50
211 word GC_min_sp
; /* Coolest stack pointer value from which we've */
212 /* already cleared the stack. */
214 # ifdef STACK_GROWS_DOWN
215 # define COOLER_THAN >
216 # define HOTTER_THAN <
217 # define MAKE_COOLER(x,y) if ((word)(x)+(y) > (word)(x)) {(x) += (y);} \
218 else {(x) = (word)ONES;}
219 # define MAKE_HOTTER(x,y) (x) -= (y)
221 # define COOLER_THAN <
222 # define HOTTER_THAN >
223 # define MAKE_COOLER(x,y) if ((word)(x)-(y) < (word)(x)) {(x) -= (y);} else {(x) = 0;}
224 # define MAKE_HOTTER(x,y) (x) += (y)
228 /* "hottest" stack pointer value we have seen */
229 /* recently. Degrades over time. */
231 word GC_words_allocd_at_reset
;
233 #if defined(ASM_CLEAR_CODE) && !defined(THREADS)
234 extern ptr_t
GC_clear_stack_inner();
237 #if !defined(ASM_CLEAR_CODE) && !defined(THREADS)
238 /* Clear the stack up to about limit. Return arg. */
240 ptr_t
GC_clear_stack_inner(arg
, limit
)
244 word dummy
[CLEAR_SIZE
];
246 BZERO(dummy
, CLEAR_SIZE
*sizeof(word
));
247 if ((word
)(dummy
) COOLER_THAN limit
) {
248 (void) GC_clear_stack_inner(arg
, limit
);
250 /* Make sure the recursive call is not a tail call, and the bzero */
251 /* call is not recognized as dead code. */
252 GC_noop1((word
)dummy
);
257 /* Clear some of the inaccessible part of the stack. Returns its */
258 /* argument, so it can be used in a tail call position, hence clearing */
260 ptr_t
GC_clear_stack(arg
)
263 register word sp
= (word
)GC_approx_sp(); /* Hotter than actual sp */
265 word dummy
[CLEAR_SIZE
];
271 /* Extra bytes we clear every time. This clears our own */
272 /* activation record, and should cause more frequent */
273 /* clearing near the cold end of the stack, a good thing. */
274 # define GC_SLOP 4000
275 /* We make GC_high_water this much hotter than we really saw */
276 /* saw it, to cover for GC noise etc. above our current frame. */
277 # define CLEAR_THRESHOLD 100000
278 /* We restart the clearing process after this many bytes of */
279 /* allocation. Otherwise very heavily recursive programs */
280 /* with sparse stacks may result in heaps that grow almost */
281 /* without bounds. As the heap gets larger, collection */
282 /* frequency decreases, thus clearing frequency would decrease, */
283 /* thus more junk remains accessible, thus the heap gets */
286 BZERO(dummy
, CLEAR_SIZE
*sizeof(word
));
288 if (GC_gc_no
> GC_stack_last_cleared
) {
289 /* Start things over, so we clear the entire stack again */
290 if (GC_stack_last_cleared
== 0) GC_high_water
= (word
) GC_stackbottom
;
291 GC_min_sp
= GC_high_water
;
292 GC_stack_last_cleared
= GC_gc_no
;
293 GC_words_allocd_at_reset
= GC_words_allocd
;
295 /* Adjust GC_high_water */
296 MAKE_COOLER(GC_high_water
, WORDS_TO_BYTES(DEGRADE_RATE
) + GC_SLOP
);
297 if (sp HOTTER_THAN GC_high_water
) {
300 MAKE_HOTTER(GC_high_water
, GC_SLOP
);
302 MAKE_HOTTER(limit
, SLOP
);
303 if (sp COOLER_THAN limit
) {
304 limit
&= ~0xf; /* Make it sufficiently aligned for assembly */
305 /* implementations of GC_clear_stack_inner. */
307 return(GC_clear_stack_inner(arg
, limit
));
308 } else if (WORDS_TO_BYTES(GC_words_allocd
- GC_words_allocd_at_reset
)
310 /* Restart clearing process, but limit how much clearing we do. */
312 MAKE_HOTTER(GC_min_sp
, CLEAR_THRESHOLD
/4);
313 if (GC_min_sp HOTTER_THAN GC_high_water
) GC_min_sp
= GC_high_water
;
314 GC_words_allocd_at_reset
= GC_words_allocd
;
321 /* Return a pointer to the base address of p, given a pointer to a */
322 /* an address within an object. Return 0 o.w. */
324 GC_PTR
GC_base(GC_PTR p
)
331 register struct hblk
*h
;
332 register bottom_index
*bi
;
333 register hdr
*candidate_hdr
;
337 if (!GC_is_initialized
) return 0;
340 candidate_hdr
= HDR_FROM_BI(bi
, r
);
341 if (candidate_hdr
== 0) return(0);
342 /* If it's a pointer to the middle of a large object, move it */
343 /* to the beginning. */
344 while (IS_FORWARDING_ADDR_OR_NIL(candidate_hdr
)) {
345 h
= FORWARDED_ADDR(h
,candidate_hdr
);
346 r
= (word
)h
+ HDR_BYTES
;
347 candidate_hdr
= HDR(h
);
349 if (candidate_hdr
-> hb_map
== GC_invalid_map
) return(0);
350 /* Make sure r points to the beginning of the object */
351 r
&= ~(WORDS_TO_BYTES(1) - 1);
353 register int offset
= (char *)r
- (char *)(HBLKPTR(r
));
354 register signed_word sz
= candidate_hdr
-> hb_sz
;
356 # ifdef ALL_INTERIOR_POINTERS
357 register map_entry_type map_entry
;
359 map_entry
= MAP_ENTRY((candidate_hdr
-> hb_map
), offset
);
360 if (map_entry
== OBJ_INVALID
) {
363 r
-= WORDS_TO_BYTES(map_entry
);
364 limit
= r
+ WORDS_TO_BYTES(sz
);
366 register int correction
;
368 offset
= BYTES_TO_WORDS(offset
- HDR_BYTES
);
369 correction
= offset
% sz
;
370 r
-= (WORDS_TO_BYTES(correction
));
371 limit
= r
+ WORDS_TO_BYTES(sz
);
372 if (limit
> (word
)(h
+ 1)
373 && sz
<= BYTES_TO_WORDS(HBLKSIZE
) - HDR_WORDS
) {
377 if ((word
)p
>= limit
) return(0);
383 /* Return the size of an object, given a pointer to its base. */
384 /* (For small obects this also happens to work from interior pointers, */
385 /* but that shouldn't be relied upon.) */
387 size_t GC_size(GC_PTR p
)
394 register hdr
* hhdr
= HDR(p
);
396 sz
= WORDS_TO_BYTES(hhdr
-> hb_sz
);
404 size_t GC_get_heap_size
GC_PROTO(())
406 return ((size_t) GC_heapsize
);
409 size_t GC_get_free_bytes
GC_PROTO(())
411 return ((size_t) GC_large_free_bytes
);
414 size_t GC_get_bytes_since_gc
GC_PROTO(())
416 return ((size_t) WORDS_TO_BYTES(GC_words_allocd
));
419 GC_bool GC_is_initialized
= FALSE
;
434 extern void GC_init_win32();
437 extern void GC_setpagesize();
445 if (GC_is_initialized
) return;
447 GC_exclude_static_roots(beginGC_arrays
, end_gc_area
);
449 if ((ptr_t
)endGC_arrays
!= (ptr_t
)(&GC_obj_kinds
)) {
450 GC_printf0("Reordering linker, didn't exclude obj_kinds\n");
456 # if defined(SEARCH_FOR_DATA_START)
457 /* This doesn't really work if the collector is in a shared library. */
458 GC_init_linux_data_start();
460 # ifdef SOLARIS_THREADS
462 /* We need dirty bits in order to find live stack sections. */
465 # if defined(IRIX_THREADS) || defined(LINUX_THREADS) \
466 || defined(IRIX_JDK_THREADS) || defined(HPUX_THREADS)
469 # if !defined(THREADS) || defined(SOLARIS_THREADS) || defined(WIN32_THREADS) \
470 || defined(IRIX_THREADS) || defined(LINUX_THREADS) \
471 || defined(HPUX_THREADS)
472 if (GC_stackbottom
== 0) {
473 GC_stackbottom
= GC_get_stack_base();
476 if (sizeof (ptr_t
) != sizeof(word
)) {
477 ABORT("sizeof (ptr_t) != sizeof(word)\n");
479 if (sizeof (signed_word
) != sizeof(word
)) {
480 ABORT("sizeof (signed_word) != sizeof(word)\n");
482 if (sizeof (struct hblk
) != HBLKSIZE
) {
483 ABORT("sizeof (struct hblk) != HBLKSIZE\n");
486 # if defined(STACK_GROWS_UP) && defined(STACK_GROWS_DOWN)
488 "Only one of STACK_GROWS_UP and STACK_GROWS_DOWN should be defd\n");
490 # if !defined(STACK_GROWS_UP) && !defined(STACK_GROWS_DOWN)
492 "One of STACK_GROWS_UP and STACK_GROWS_DOWN should be defd\n");
494 # ifdef STACK_GROWS_DOWN
495 if ((word
)(&dummy
) > (word
)GC_stackbottom
) {
497 "STACK_GROWS_DOWN is defd, but stack appears to grow up\n");
498 # ifndef UTS4 /* Compiler bug workaround */
499 GC_err_printf2("sp = 0x%lx, GC_stackbottom = 0x%lx\n",
500 (unsigned long) (&dummy
),
501 (unsigned long) GC_stackbottom
);
503 ABORT("stack direction 3\n");
506 if ((word
)(&dummy
) < (word
)GC_stackbottom
) {
508 "STACK_GROWS_UP is defd, but stack appears to grow down\n");
509 GC_err_printf2("sp = 0x%lx, GC_stackbottom = 0x%lx\n",
510 (unsigned long) (&dummy
),
511 (unsigned long) GC_stackbottom
);
512 ABORT("stack direction 4");
516 # if !defined(_AUX_SOURCE) || defined(__GNUC__)
517 if ((word
)(-1) < (word
)0) {
518 GC_err_printf0("The type word should be an unsigned integer type\n");
519 GC_err_printf0("It appears to be signed\n");
523 if ((signed_word
)(-1) >= (signed_word
)0) {
525 "The type signed_word should be a signed integer type\n");
526 GC_err_printf0("It appears to be unsigned\n");
527 ABORT("signed_word");
530 /* Add initial guess of root sets. Do this first, since sbrk(0) */
532 GC_register_data_segments();
536 if (!GC_expand_hp_inner((word
)MINHINCR
)) {
537 GC_err_printf0("Can't start up: not enough memory\n");
540 /* Preallocate large object map. It's otherwise inconvenient to */
541 /* deal with failure. */
542 if (!GC_add_map_entry((word
)0)) {
543 GC_err_printf0("Can't start up: not enough memory\n");
546 GC_register_displacement_inner(0L);
551 if (PCR_IL_Lock(PCR_Bool_false
, PCR_allSigsBlocked
, PCR_waitForever
)
553 ABORT("Can't lock load state\n");
554 } else if (PCR_IL_Unlock() != PCR_ERes_okay
) {
555 ABORT("Can't unlock load state\n");
560 /* Get black list set up */
562 # ifdef STUBBORN_ALLOC
565 GC_is_initialized
= TRUE
;
566 /* Convince lint that some things are used */
569 extern char * GC_copyright
[];
570 extern int GC_read();
571 extern void GC_register_finalizer_no_order();
573 GC_noop(GC_copyright
, GC_find_header
,
574 GC_push_one
, GC_call_with_alloc_lock
, GC_read
,
576 # ifndef NO_DEBUGGING
579 GC_register_finalizer_no_order
);
584 void GC_enable_incremental
GC_PROTO(())
586 # if !defined(SMALL_CONFIG)
592 if (GC_incremental
) goto out
;
596 extern GC_bool
GC_is_win32s();
598 /* VirtualProtect is not functional under win32s. */
599 if (GC_is_win32s()) goto out
;
601 # endif /* MSWIN32 */
602 # ifndef SOLARIS_THREADS
605 if (!GC_is_initialized
) {
609 /* Can't easily do it. */
614 if (GC_words_allocd
> 0) {
615 /* There may be unmarked reachable objects */
617 } /* else we're OK in assuming everything's */
618 /* clean since nothing can point to an */
619 /* unmarked object. */
621 GC_incremental
= TRUE
;
631 # define LOG_FILE "gc.log"
633 HANDLE GC_stdout
= 0, GC_stderr
;
640 GC_stdout
= CreateFile(LOG_FILE
, GENERIC_WRITE
,
641 FILE_SHARE_READ
| FILE_SHARE_WRITE
,
642 NULL
, CREATE_ALWAYS
, FILE_FLAG_WRITE_THROUGH
,
644 if (INVALID_HANDLE_VALUE
== GC_stdout
) ABORT("Open of log file failed");
646 if (GC_stderr
== 0) {
647 GC_stderr
= GC_stdout
;
653 #if defined(OS2) || defined(MACOS)
654 FILE * GC_stdout
= NULL
;
655 FILE * GC_stderr
= NULL
;
656 int GC_tmp
; /* Should really be local ... */
660 if (GC_stdout
== NULL
) {
663 if (GC_stderr
== NULL
) {
669 #if !defined(OS2) && !defined(MACOS) && !defined(MSWIN32)
677 #if !defined(MSWIN32) && !defined(OS2) && !defined(MACOS) && !defined(ECOS)
678 int GC_write(fd
, buf
, len
)
683 register int bytes_written
= 0;
686 while (bytes_written
< len
) {
687 # ifdef SOLARIS_THREADS
688 result
= syscall(SYS_write
, fd
, buf
+ bytes_written
,
689 len
- bytes_written
);
691 result
= write(fd
, buf
+ bytes_written
, len
- bytes_written
);
693 if (-1 == result
) return(result
);
694 bytes_written
+= result
;
696 return(bytes_written
);
701 int GC_write(fd
, buf
, len
)
703 _Jv_diag_write (buf
, len
);
710 # define WRITE(f, buf, len) (GC_set_files(), \
711 GC_tmp = WriteFile((f), (buf), \
712 (len), &GC_junk, NULL),\
715 # if defined(OS2) || defined(MACOS)
716 # define WRITE(f, buf, len) (GC_set_files(), \
717 GC_tmp = fwrite((buf), 1, (len), (f)), \
720 # define WRITE(f, buf, len) GC_write((f), (buf), (len))
724 /* A version of printf that is unlikely to call malloc, and is thus safer */
725 /* to call from the collector in case malloc has been bound to GC_malloc. */
726 /* Assumes that no more than 1023 characters are written at once. */
727 /* Assumes that all arguments have been converted to something of the */
728 /* same size as long, and that the format conversions expect something */
730 void GC_printf(format
, a
, b
, c
, d
, e
, f
)
732 long a
, b
, c
, d
, e
, f
;
736 if (GC_quiet
) return;
738 (void) sprintf(buf
, format
, a
, b
, c
, d
, e
, f
);
739 if (buf
[1024] != 0x15) ABORT("GC_printf clobbered stack");
740 if (WRITE(GC_stdout
, buf
, strlen(buf
)) < 0) ABORT("write to stdout failed");
743 void GC_err_printf(format
, a
, b
, c
, d
, e
, f
)
745 long a
, b
, c
, d
, e
, f
;
750 (void) sprintf(buf
, format
, a
, b
, c
, d
, e
, f
);
751 if (buf
[1024] != 0x15) ABORT("GC_err_printf clobbered stack");
752 if (WRITE(GC_stderr
, buf
, strlen(buf
)) < 0) ABORT("write to stderr failed");
758 if (WRITE(GC_stderr
, s
, strlen(s
)) < 0) ABORT("write to stderr failed");
761 # if defined(__STDC__) || defined(__cplusplus)
762 void GC_default_warn_proc(char *msg
, GC_word arg
)
764 void GC_default_warn_proc(msg
, arg
)
769 GC_err_printf1(msg
, (unsigned long)arg
);
772 GC_warn_proc GC_current_warn_proc
= GC_default_warn_proc
;
774 # if defined(__STDC__) || defined(__cplusplus)
775 GC_warn_proc
GC_set_warn_proc(GC_warn_proc p
)
777 GC_warn_proc
GC_set_warn_proc(p
)
784 result
= GC_current_warn_proc
;
785 GC_current_warn_proc
= p
;
795 GC_err_printf1("%s\n", msg
);
802 void GC_print_callers (info
)
803 struct callinfo info
[NFRAMES
];
808 GC_err_printf0("\tCaller at allocation:\n");
810 GC_err_printf0("\tCall chain at allocation:\n");
812 for (i
= 0; i
< NFRAMES
; i
++) {
813 if (info
[i
].ci_pc
== 0) break;
818 GC_err_printf0("\t\targs: ");
819 for (j
= 0; j
< NARGS
; j
++) {
820 if (j
!= 0) GC_err_printf0(", ");
821 GC_err_printf2("%d (0x%X)", ~(info
[i
].ci_arg
[j
]),
822 ~(info
[i
].ci_arg
[j
]));
824 GC_err_printf0("\n");
827 GC_err_printf1("\t\t##PC##= 0x%X\n", info
[i
].ci_pc
);
831 #endif /* SAVE_CALL_CHAIN */
833 /* Needed by SRC_M3, gcj, and should perhaps be the official interface */
845 #if !defined(NO_DEBUGGING)
849 GC_printf0("***Static roots:\n");
850 GC_print_static_roots();
851 GC_printf0("\n***Heap sections:\n");
852 GC_print_heap_sects();
853 GC_printf0("\n***Free blocks:\n");
854 GC_print_hblkfreelist();
855 GC_printf0("\n***Blocks in use:\n");
856 GC_print_block_list();
859 # endif /* NO_DEBUGGING */