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(LINUX_THREADS) \
46 || defined(IRIX_JDK_THREADS)
47 pthread_t GC_lock_holder
= NO_THREAD
;
49 # if defined(HPUX_THREADS)
50 pthread_mutex_t GC_allocate_ml
= PTHREAD_MUTEX_INITIALIZER
;
52 --> declare allocator lock here
65 GC_FAR
struct _GC_arrays GC_arrays
/* = { 0 } */;
68 GC_bool GC_debugging_started
= FALSE
;
69 /* defined here so we don't have to load debug_malloc.o */
71 void (*GC_check_heap
)() = (void (*)())0;
73 void (*GC_start_call_back
)() = (void (*)())0;
75 ptr_t GC_stackbottom
= 0;
77 GC_bool GC_dont_gc
= 0;
88 GC_PTR GC_default_oom_fn
GC_PROTO((size_t bytes_requested
))
93 GC_PTR (*GC_oom_fn
) GC_PROTO((size_t bytes_requested
)) = GC_default_oom_fn
;
95 extern signed_word GC_mem_found
;
98 /* Set things up so that GC_size_map[i] >= words(i), */
99 /* but not too much bigger */
100 /* and so that size_map contains relatively few distinct entries */
101 /* This is stolen from Russ Atkinson's Cedar quantization */
102 /* alogrithm (but we precompute it). */
105 void GC_init_size_map()
109 /* Map size 0 to 1. This avoids problems at lower levels. */
111 /* One word objects don't have to be 2 word aligned. */
112 for (i
= 1; i
< sizeof(word
); i
++) {
115 GC_size_map
[sizeof(word
)] = ROUNDED_UP_WORDS(sizeof(word
));
116 for (i
= sizeof(word
) + 1; i
<= 8 * sizeof(word
); i
++) {
118 GC_size_map
[i
] = (ROUNDED_UP_WORDS(i
) + 1) & (~1);
120 GC_size_map
[i
] = ROUNDED_UP_WORDS(i
);
123 for (i
= 8*sizeof(word
) + 1; i
<= 16 * sizeof(word
); i
++) {
124 GC_size_map
[i
] = (ROUNDED_UP_WORDS(i
) + 1) & (~1);
126 /* We leave the rest of the array to be filled in on demand. */
129 /* Fill in additional entries in GC_size_map, including the ith one */
130 /* We assume the ith entry is currently 0. */
131 /* Note that a filled in section of the array ending at n always */
132 /* has length at least n/4. */
133 void GC_extend_size_map(i
)
136 word orig_word_sz
= ROUNDED_UP_WORDS(i
);
137 word word_sz
= orig_word_sz
;
138 register word byte_sz
= WORDS_TO_BYTES(word_sz
);
139 /* The size we try to preserve. */
140 /* Close to to i, unless this would */
141 /* introduce too many distinct sizes. */
142 word smaller_than_i
= byte_sz
- (byte_sz
>> 3);
143 word much_smaller_than_i
= byte_sz
- (byte_sz
>> 2);
144 register word low_limit
; /* The lowest indexed entry we */
148 if (GC_size_map
[smaller_than_i
] == 0) {
149 low_limit
= much_smaller_than_i
;
150 while (GC_size_map
[low_limit
] != 0) low_limit
++;
152 low_limit
= smaller_than_i
+ 1;
153 while (GC_size_map
[low_limit
] != 0) low_limit
++;
154 word_sz
= ROUNDED_UP_WORDS(low_limit
);
155 word_sz
+= word_sz
>> 3;
156 if (word_sz
< orig_word_sz
) word_sz
= orig_word_sz
;
162 if (word_sz
> MAXOBJSZ
) {
165 /* If we can fit the same number of larger objects in a block, */
168 size_t number_of_objs
= BODY_SZ
/word_sz
;
169 word_sz
= BODY_SZ
/number_of_objs
;
174 byte_sz
= WORDS_TO_BYTES(word_sz
);
175 # ifdef ADD_BYTE_AT_END
176 /* We need one extra byte; don't fill in GC_size_map[byte_sz] */
180 for (j
= low_limit
; j
<= byte_sz
; j
++) GC_size_map
[j
] = word_sz
;
186 * The following is a gross hack to deal with a problem that can occur
187 * on machines that are sloppy about stack frame sizes, notably SPARC.
188 * Bogus pointers may be written to the stack and not cleared for
189 * a LONG time, because they always fall into holes in stack frames
190 * that are not written. We partially address this by clearing
191 * sections of the stack whenever we get control.
193 word GC_stack_last_cleared
= 0; /* GC_no when we last did this */
195 # define CLEAR_SIZE 2048
197 # define CLEAR_SIZE 213
199 # define DEGRADE_RATE 50
201 word GC_min_sp
; /* Coolest stack pointer value from which we've */
202 /* already cleared the stack. */
204 # ifdef STACK_GROWS_DOWN
205 # define COOLER_THAN >
206 # define HOTTER_THAN <
207 # define MAKE_COOLER(x,y) if ((word)(x)+(y) > (word)(x)) {(x) += (y);} \
208 else {(x) = (word)ONES;}
209 # define MAKE_HOTTER(x,y) (x) -= (y)
211 # define COOLER_THAN <
212 # define HOTTER_THAN >
213 # define MAKE_COOLER(x,y) if ((word)(x)-(y) < (word)(x)) {(x) -= (y);} else {(x) = 0;}
214 # define MAKE_HOTTER(x,y) (x) += (y)
218 /* "hottest" stack pointer value we have seen */
219 /* recently. Degrades over time. */
221 word GC_words_allocd_at_reset
;
223 #if defined(ASM_CLEAR_CODE) && !defined(THREADS)
224 extern ptr_t
GC_clear_stack_inner();
227 #if !defined(ASM_CLEAR_CODE) && !defined(THREADS)
228 /* Clear the stack up to about limit. Return arg. */
230 ptr_t
GC_clear_stack_inner(arg
, limit
)
234 word dummy
[CLEAR_SIZE
];
236 BZERO(dummy
, CLEAR_SIZE
*sizeof(word
));
237 if ((word
)(dummy
) COOLER_THAN limit
) {
238 (void) GC_clear_stack_inner(arg
, limit
);
240 /* Make sure the recursive call is not a tail call, and the bzero */
241 /* call is not recognized as dead code. */
242 GC_noop1((word
)dummy
);
247 /* Clear some of the inaccessible part of the stack. Returns its */
248 /* argument, so it can be used in a tail call position, hence clearing */
250 ptr_t
GC_clear_stack(arg
)
253 register word sp
= (word
)GC_approx_sp(); /* Hotter than actual sp */
255 word dummy
[CLEAR_SIZE
];
261 /* Extra bytes we clear every time. This clears our own */
262 /* activation record, and should cause more frequent */
263 /* clearing near the cold end of the stack, a good thing. */
264 # define GC_SLOP 4000
265 /* We make GC_high_water this much hotter than we really saw */
266 /* saw it, to cover for GC noise etc. above our current frame. */
267 # define CLEAR_THRESHOLD 100000
268 /* We restart the clearing process after this many bytes of */
269 /* allocation. Otherwise very heavily recursive programs */
270 /* with sparse stacks may result in heaps that grow almost */
271 /* without bounds. As the heap gets larger, collection */
272 /* frequency decreases, thus clearing frequency would decrease, */
273 /* thus more junk remains accessible, thus the heap gets */
276 BZERO(dummy
, CLEAR_SIZE
*sizeof(word
));
278 if (GC_gc_no
> GC_stack_last_cleared
) {
279 /* Start things over, so we clear the entire stack again */
280 if (GC_stack_last_cleared
== 0) GC_high_water
= (word
) GC_stackbottom
;
281 GC_min_sp
= GC_high_water
;
282 GC_stack_last_cleared
= GC_gc_no
;
283 GC_words_allocd_at_reset
= GC_words_allocd
;
285 /* Adjust GC_high_water */
286 MAKE_COOLER(GC_high_water
, WORDS_TO_BYTES(DEGRADE_RATE
) + GC_SLOP
);
287 if (sp HOTTER_THAN GC_high_water
) {
290 MAKE_HOTTER(GC_high_water
, GC_SLOP
);
292 MAKE_HOTTER(limit
, SLOP
);
293 if (sp COOLER_THAN limit
) {
294 limit
&= ~0xf; /* Make it sufficiently aligned for assembly */
295 /* implementations of GC_clear_stack_inner. */
297 return(GC_clear_stack_inner(arg
, limit
));
298 } else if (WORDS_TO_BYTES(GC_words_allocd
- GC_words_allocd_at_reset
)
300 /* Restart clearing process, but limit how much clearing we do. */
302 MAKE_HOTTER(GC_min_sp
, CLEAR_THRESHOLD
/4);
303 if (GC_min_sp HOTTER_THAN GC_high_water
) GC_min_sp
= GC_high_water
;
304 GC_words_allocd_at_reset
= GC_words_allocd
;
311 /* Return a pointer to the base address of p, given a pointer to a */
312 /* an address within an object. Return 0 o.w. */
314 GC_PTR
GC_base(GC_PTR p
)
321 register struct hblk
*h
;
322 register bottom_index
*bi
;
323 register hdr
*candidate_hdr
;
327 if (!GC_is_initialized
) return 0;
330 candidate_hdr
= HDR_FROM_BI(bi
, r
);
331 if (candidate_hdr
== 0) return(0);
332 /* If it's a pointer to the middle of a large object, move it */
333 /* to the beginning. */
334 while (IS_FORWARDING_ADDR_OR_NIL(candidate_hdr
)) {
335 h
= FORWARDED_ADDR(h
,candidate_hdr
);
336 r
= (word
)h
+ HDR_BYTES
;
337 candidate_hdr
= HDR(h
);
339 if (candidate_hdr
-> hb_map
== GC_invalid_map
) return(0);
340 /* Make sure r points to the beginning of the object */
341 r
&= ~(WORDS_TO_BYTES(1) - 1);
343 register int offset
= (char *)r
- (char *)(HBLKPTR(r
));
344 register signed_word sz
= candidate_hdr
-> hb_sz
;
346 # ifdef ALL_INTERIOR_POINTERS
347 register map_entry_type map_entry
;
349 map_entry
= MAP_ENTRY((candidate_hdr
-> hb_map
), offset
);
350 if (map_entry
== OBJ_INVALID
) {
353 r
-= WORDS_TO_BYTES(map_entry
);
354 limit
= r
+ WORDS_TO_BYTES(sz
);
356 register int correction
;
358 offset
= BYTES_TO_WORDS(offset
- HDR_BYTES
);
359 correction
= offset
% sz
;
360 r
-= (WORDS_TO_BYTES(correction
));
361 limit
= r
+ WORDS_TO_BYTES(sz
);
362 if (limit
> (word
)(h
+ 1)
363 && sz
<= BYTES_TO_WORDS(HBLKSIZE
) - HDR_WORDS
) {
367 if ((word
)p
>= limit
) return(0);
373 /* Return the size of an object, given a pointer to its base. */
374 /* (For small obects this also happens to work from interior pointers, */
375 /* but that shouldn't be relied upon.) */
377 size_t GC_size(GC_PTR p
)
384 register hdr
* hhdr
= HDR(p
);
386 sz
= WORDS_TO_BYTES(hhdr
-> hb_sz
);
394 size_t GC_get_heap_size
GC_PROTO(())
396 return ((size_t) GC_heapsize
);
399 size_t GC_get_free_bytes
GC_PROTO(())
401 return ((size_t) GC_large_free_bytes
);
404 size_t GC_get_bytes_since_gc
GC_PROTO(())
406 return ((size_t) WORDS_TO_BYTES(GC_words_allocd
));
409 GC_bool GC_is_initialized
= FALSE
;
424 extern void GC_init_win32();
427 extern void GC_setpagesize();
435 if (GC_is_initialized
) return;
437 GC_exclude_static_roots(beginGC_arrays
, end_gc_area
);
439 if ((ptr_t
)endGC_arrays
!= (ptr_t
)(&GC_obj_kinds
)) {
440 GC_printf0("Reordering linker, didn't exclude obj_kinds\n");
446 # if defined(LINUX) && (defined(SPARC) || defined(IA64))
447 GC_init_linux_data_start();
449 # ifdef SOLARIS_THREADS
451 /* We need dirty bits in order to find live stack sections. */
454 # if defined(IRIX_THREADS) || defined(LINUX_THREADS) \
455 || defined(IRIX_JDK_THREADS) || defined(HPUX_THREADS)
458 # if !defined(THREADS) || defined(SOLARIS_THREADS) || defined(WIN32_THREADS) \
459 || defined(IRIX_THREADS) || defined(LINUX_THREADS) \
460 || defined(HPUX_THREADS)
461 if (GC_stackbottom
== 0) {
462 GC_stackbottom
= GC_get_stack_base();
465 if (sizeof (ptr_t
) != sizeof(word
)) {
466 ABORT("sizeof (ptr_t) != sizeof(word)\n");
468 if (sizeof (signed_word
) != sizeof(word
)) {
469 ABORT("sizeof (signed_word) != sizeof(word)\n");
471 if (sizeof (struct hblk
) != HBLKSIZE
) {
472 ABORT("sizeof (struct hblk) != HBLKSIZE\n");
475 # if defined(STACK_GROWS_UP) && defined(STACK_GROWS_DOWN)
477 "Only one of STACK_GROWS_UP and STACK_GROWS_DOWN should be defd\n");
479 # if !defined(STACK_GROWS_UP) && !defined(STACK_GROWS_DOWN)
481 "One of STACK_GROWS_UP and STACK_GROWS_DOWN should be defd\n");
483 # ifdef STACK_GROWS_DOWN
484 if ((word
)(&dummy
) > (word
)GC_stackbottom
) {
486 "STACK_GROWS_DOWN is defd, but stack appears to grow up\n");
487 # ifndef UTS4 /* Compiler bug workaround */
488 GC_err_printf2("sp = 0x%lx, GC_stackbottom = 0x%lx\n",
489 (unsigned long) (&dummy
),
490 (unsigned long) GC_stackbottom
);
492 ABORT("stack direction 3\n");
495 if ((word
)(&dummy
) < (word
)GC_stackbottom
) {
497 "STACK_GROWS_UP is defd, but stack appears to grow down\n");
498 GC_err_printf2("sp = 0x%lx, GC_stackbottom = 0x%lx\n",
499 (unsigned long) (&dummy
),
500 (unsigned long) GC_stackbottom
);
501 ABORT("stack direction 4");
505 # if !defined(_AUX_SOURCE) || defined(__GNUC__)
506 if ((word
)(-1) < (word
)0) {
507 GC_err_printf0("The type word should be an unsigned integer type\n");
508 GC_err_printf0("It appears to be signed\n");
512 if ((signed_word
)(-1) >= (signed_word
)0) {
514 "The type signed_word should be a signed integer type\n");
515 GC_err_printf0("It appears to be unsigned\n");
516 ABORT("signed_word");
519 /* Add initial guess of root sets. Do this first, since sbrk(0) */
521 GC_register_data_segments();
525 if (!GC_expand_hp_inner((word
)MINHINCR
)) {
526 GC_err_printf0("Can't start up: not enough memory\n");
529 /* Preallocate large object map. It's otherwise inconvenient to */
530 /* deal with failure. */
531 if (!GC_add_map_entry((word
)0)) {
532 GC_err_printf0("Can't start up: not enough memory\n");
535 GC_register_displacement_inner(0L);
540 if (PCR_IL_Lock(PCR_Bool_false
, PCR_allSigsBlocked
, PCR_waitForever
)
542 ABORT("Can't lock load state\n");
543 } else if (PCR_IL_Unlock() != PCR_ERes_okay
) {
544 ABORT("Can't unlock load state\n");
549 /* Get black list set up */
551 # ifdef STUBBORN_ALLOC
554 GC_is_initialized
= TRUE
;
555 /* Convince lint that some things are used */
558 extern char * GC_copyright
[];
559 extern int GC_read();
560 extern void GC_register_finalizer_no_order();
562 GC_noop(GC_copyright
, GC_find_header
,
563 GC_push_one
, GC_call_with_alloc_lock
, GC_read
,
565 # ifndef NO_DEBUGGING
568 GC_register_finalizer_no_order
);
573 void GC_enable_incremental
GC_PROTO(())
575 # if !defined(SMALL_CONFIG)
581 if (GC_incremental
) goto out
;
585 extern GC_bool
GC_is_win32s();
587 /* VirtualProtect is not functional under win32s. */
588 if (GC_is_win32s()) goto out
;
590 # endif /* MSWIN32 */
591 # ifndef SOLARIS_THREADS
594 if (!GC_is_initialized
) {
598 /* Can't easily do it. */
603 if (GC_words_allocd
> 0) {
604 /* There may be unmarked reachable objects */
606 } /* else we're OK in assuming everything's */
607 /* clean since nothing can point to an */
608 /* unmarked object. */
610 GC_incremental
= TRUE
;
620 # define LOG_FILE "gc.log"
622 HANDLE GC_stdout
= 0, GC_stderr
;
629 GC_stdout
= CreateFile(LOG_FILE
, GENERIC_WRITE
,
630 FILE_SHARE_READ
| FILE_SHARE_WRITE
,
631 NULL
, CREATE_ALWAYS
, FILE_FLAG_WRITE_THROUGH
,
633 if (INVALID_HANDLE_VALUE
== GC_stdout
) ABORT("Open of log file failed");
635 if (GC_stderr
== 0) {
636 GC_stderr
= GC_stdout
;
642 #if defined(OS2) || defined(MACOS)
643 FILE * GC_stdout
= NULL
;
644 FILE * GC_stderr
= NULL
;
645 int GC_tmp
; /* Should really be local ... */
649 if (GC_stdout
== NULL
) {
652 if (GC_stderr
== NULL
) {
658 #if !defined(OS2) && !defined(MACOS) && !defined(MSWIN32)
666 #if !defined(MSWIN32) && !defined(OS2) && !defined(MACOS) && !defined(ECOS)
667 int GC_write(fd
, buf
, len
)
672 register int bytes_written
= 0;
675 while (bytes_written
< len
) {
676 # ifdef SOLARIS_THREADS
677 result
= syscall(SYS_write
, fd
, buf
+ bytes_written
,
678 len
- bytes_written
);
680 result
= write(fd
, buf
+ bytes_written
, len
- bytes_written
);
682 if (-1 == result
) return(result
);
683 bytes_written
+= result
;
685 return(bytes_written
);
690 int GC_write(fd
, buf
, len
)
692 _Jv_diag_write (buf
, len
);
699 # define WRITE(f, buf, len) (GC_set_files(), \
700 GC_tmp = WriteFile((f), (buf), \
701 (len), &GC_junk, NULL),\
704 # if defined(OS2) || defined(MACOS)
705 # define WRITE(f, buf, len) (GC_set_files(), \
706 GC_tmp = fwrite((buf), 1, (len), (f)), \
709 # define WRITE(f, buf, len) GC_write((f), (buf), (len))
713 /* A version of printf that is unlikely to call malloc, and is thus safer */
714 /* to call from the collector in case malloc has been bound to GC_malloc. */
715 /* Assumes that no more than 1023 characters are written at once. */
716 /* Assumes that all arguments have been converted to something of the */
717 /* same size as long, and that the format conversions expect something */
719 void GC_printf(format
, a
, b
, c
, d
, e
, f
)
721 long a
, b
, c
, d
, e
, f
;
725 if (GC_quiet
) return;
727 (void) sprintf(buf
, format
, a
, b
, c
, d
, e
, f
);
728 if (buf
[1024] != 0x15) ABORT("GC_printf clobbered stack");
729 if (WRITE(GC_stdout
, buf
, strlen(buf
)) < 0) ABORT("write to stdout failed");
732 void GC_err_printf(format
, a
, b
, c
, d
, e
, f
)
734 long a
, b
, c
, d
, e
, f
;
739 (void) sprintf(buf
, format
, a
, b
, c
, d
, e
, f
);
740 if (buf
[1024] != 0x15) ABORT("GC_err_printf clobbered stack");
741 if (WRITE(GC_stderr
, buf
, strlen(buf
)) < 0) ABORT("write to stderr failed");
747 if (WRITE(GC_stderr
, s
, strlen(s
)) < 0) ABORT("write to stderr failed");
750 # if defined(__STDC__) || defined(__cplusplus)
751 void GC_default_warn_proc(char *msg
, GC_word arg
)
753 void GC_default_warn_proc(msg
, arg
)
758 GC_err_printf1(msg
, (unsigned long)arg
);
761 GC_warn_proc GC_current_warn_proc
= GC_default_warn_proc
;
763 # if defined(__STDC__) || defined(__cplusplus)
764 GC_warn_proc
GC_set_warn_proc(GC_warn_proc p
)
766 GC_warn_proc
GC_set_warn_proc(p
)
773 result
= GC_current_warn_proc
;
774 GC_current_warn_proc
= p
;
784 GC_err_printf1("%s\n", msg
);
791 void GC_print_callers (info
)
792 struct callinfo info
[NFRAMES
];
797 GC_err_printf0("\tCaller at allocation:\n");
799 GC_err_printf0("\tCall chain at allocation:\n");
801 for (i
= 0; i
< NFRAMES
; i
++) {
802 if (info
[i
].ci_pc
== 0) break;
807 GC_err_printf0("\t\targs: ");
808 for (j
= 0; j
< NARGS
; j
++) {
809 if (j
!= 0) GC_err_printf0(", ");
810 GC_err_printf2("%d (0x%X)", ~(info
[i
].ci_arg
[j
]),
811 ~(info
[i
].ci_arg
[j
]));
813 GC_err_printf0("\n");
816 GC_err_printf1("\t\t##PC##= 0x%X\n", info
[i
].ci_pc
);
820 #endif /* SAVE_CALL_CHAIN */
834 #if !defined(NO_DEBUGGING)
838 GC_printf0("***Static roots:\n");
839 GC_print_static_roots();
840 GC_printf0("\n***Heap sections:\n");
841 GC_print_heap_sects();
842 GC_printf0("\n***Free blocks:\n");
843 GC_print_hblkfreelist();
844 GC_printf0("\n***Blocks in use:\n");
845 GC_print_block_list();
848 # endif /* NO_DEBUGGING */