From 658609667c42fe4fa12e6eb7d9a61ee66f1f9d1b Mon Sep 17 00:00:00 2001 From: Hans Boehm Date: Fri, 23 Jul 1999 00:00:00 +0000 Subject: [PATCH] gc5.0alpha2 tarball import --- Makefile | 11 +++- README | 12 +++- allchblk.c | 2 +- backptr.h | 56 ++++++++++++++++++ cord/gc.h | 1 + dbg_mlc.c | 144 ++++++++++++++++++++++++++++++++++++++++++++- finalize.c | 1 + gc.h | 1 + gc_mark.h | 2 + gc_priv.h | 10 ++++ gcconfig.h | 2 +- include/backptr.h | 56 ++++++++++++++++++ include/gc.h | 1 + include/private/gc_priv.h | 10 ++++ include/private/gcconfig.h | 2 +- mark.c | 3 +- os_dep.c | 3 +- test.c | 2 +- version.h | 2 +- 19 files changed, 306 insertions(+), 15 deletions(-) create mode 100644 backptr.h create mode 100644 include/backptr.h diff --git a/Makefile b/Makefile index 4d0d352..10d47a2 100644 --- a/Makefile +++ b/Makefile @@ -120,10 +120,15 @@ CFLAGS= -O -DATOMIC_UNCOLLECTABLE -DNO_SIGNALS -DNO_EXECUTE_PERMISSION -DALL_INT # for debugging of the garbage collector itself, but could also # occasionally be useful for debugging of client code. Slows down the # collector somewhat, but not drastically. +# -DKEEP_BACK_PTRS Add code to save back pointers in debugging headers +# for objects allocated with the debugging allocator. If all objects +# through GC_MALLOC with GC_DEBUG defined, this allows the client +# to determine how particular or randomly chosen objects are reachable +# for debugging/profiling purposes. The backptr.h interface is +# implemented only if this is defined. # - LIBGC_CFLAGS= -O -DNO_SIGNALS -DSILENT \ -DREDIRECT_MALLOC=GC_malloc_uncollectable \ -DDONT_ADD_BYTE_AT_END -DALL_INTERIOR_POINTERS @@ -154,7 +159,7 @@ SRCS= $(CSRCS) mips_sgi_mach_dep.s rs6000_mach_dep.s alpha_mach_dep.s \ threadlibs.c if_mach.c if_not_there.c gc_cpp.cc gc_cpp.h weakpointer.h \ gcc_support.c mips_ultrix_mach_dep.s include/gc_alloc.h gc_alloc.h \ include/new_gc_alloc.h include/javaxfc.h sparc_sunos4_mach_dep.s \ - solaris_threads.h $(CORD_SRCS) + solaris_threads.h backptr.h $(CORD_SRCS) OTHER_FILES= Makefile PCR-Makefile OS2_MAKEFILE NT_MAKEFILE BCC_MAKEFILE \ README test.c test_cpp.cc setjmp_t.c SMakefile.amiga \ @@ -162,7 +167,7 @@ OTHER_FILES= Makefile PCR-Makefile OS2_MAKEFILE NT_MAKEFILE BCC_MAKEFILE \ cord/gc.h include/gc.h include/gc_typed.h include/cord.h \ include/ec.h include/private/cord_pos.h include/private/gcconfig.h \ include/private/gc_hdrs.h include/private/gc_priv.h \ - include/gc_cpp.h README.rs6000 \ + include/gc_cpp.h README.rs6000 include/backptr.h \ include/weakpointer.h README.QUICK callprocs pc_excludes \ barrett_diagram README.OS2 README.Mac MacProjects.sit.hqx \ MacOS.c EMX_MAKEFILE makefile.depend README.debugging \ diff --git a/README b/README index 4c3dfe2..fbca757 100644 --- a/README +++ b/README @@ -11,7 +11,7 @@ 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. -This is version 5.0alpha1 of a conservative garbage collector for C and C++. +This is version 5.0alpha2 of a conservative garbage collector for C and C++. You might find a more recent version of this at @@ -1451,7 +1451,7 @@ Since 4.14alpha1 Since 4.14alpha2 - changed STACKBOTTOM for DJGPP (Thanks to Salvador Eduardo Tropea). - + Since 4.14 - Reworked large block allocator. Now uses multiple doubly linked free lists to approximate best fit. @@ -1481,7 +1481,13 @@ Since 4.14 in such large stacks. And the dirty bit implementation does not guarantee that none of them will be accessed. - Integrated Martin Tauchmann's Amiga changes. - - Inetgrated James Dominy's OpenBSD/SPARC port. + - Integrated James Dominy's OpenBSD/SPARC port. + +Since 5.0alpha1 + - Fixed bugs introduced in alpha1 (OpenBSD & large block initialization). + + - Added -DKEEP_BACK_PTRS and backptr.h interface. (The implementation + idea came from Al Demers.) To do: - Very large root set sizes (> 16 MB or so) could cause the collector diff --git a/allchblk.c b/allchblk.c index d03afa9..f49240c 100644 --- a/allchblk.c +++ b/allchblk.c @@ -650,7 +650,7 @@ int n; /* Clear block if necessary */ if (GC_debugging_started || sz > MAXOBJSZ && GC_obj_kinds[kind].ok_init) { - BZERO(thishbp + HDR_BYTES, size_needed - HDR_BYTES); + BZERO(hbp + HDR_BYTES, size_needed - HDR_BYTES); } /* We just successfully allocated a block. Restart count of */ diff --git a/backptr.h b/backptr.h new file mode 100644 index 0000000..d34224e --- /dev/null +++ b/backptr.h @@ -0,0 +1,56 @@ +/* + * This is a simple API to implement pointer back tracing, i.e. + * to answer questions such as "who is pointing to this" or + * "why is this object being retained by the collector" + * + * This API assumes that we have an ANSI C compiler. + * + * Most of these calls yield useful information on only after + * a garbage collection. Usually the client will first force + * a full collection and then gather information, preferably + * before much intervening allocation. + * + * The implementation of the interface is only about 99.9999% + * correct. It is intended to be good enough for profiling, + * but is not intended to be used with production code. + * + * Results are likely to be much more useful if all allocation is + * accomplished through the debugging allocators. + * + * The implementation idea is due to A. Demers. + */ + +/* Store information about the object referencing dest in *base_p */ +/* and *offset_p. */ +/* If multiple objects or roots point to dest, the one reported */ +/* will be the last on used by the garbage collector to trace the */ +/* object. */ +/* source is root ==> *base_p = address, *offset_p = 0 */ +/* source is heap object ==> *base_p != 0, *offset_p = offset */ +/* Returns 1 on success, 0 if source couldn't be determined. */ +/* Dest can be any address within a heap object. */ +typedef enum { GC_UNREFERENCED, /* No refence info available. */ + GC_NO_SPACE, /* Dest not allocated with debug alloc */ + GC_REFD_FROM_ROOT, /* Referenced directly by root *base_p */ + GC_REFD_FROM_HEAP, /* Referenced from another heap obj. */ + GC_FINALIZER_REFD /* Finalizable and hence accessible. */ +} GC_ref_kind; + +GC_ref_kind GC_get_back_ptr_info(void *dest, void **base_p, size_t *offset_p); + +/* Generate a random heap address. */ +/* The resulting address is in the heap, but */ +/* not necessarily inside a valid object. */ +void * GC_generate_random_heap_address(void); + +/* Generate a random address inside a valid marked heap object. */ +void * GC_generate_random_valid_address(void); + +/* Force a garbage collection and generate a backtrace from a */ +/* random heap address. */ +/* This uses the GC logging mechanism (GC_printf) to produce */ +/* output. It can often be called from a debugger. The */ +/* source in dbg_mlc.c also serves as a sample client. */ +void GC_generate_random_backtrace(void); + + diff --git a/cord/gc.h b/cord/gc.h index ceabb02..7c734c8 100644 --- a/cord/gc.h +++ b/cord/gc.h @@ -692,6 +692,7 @@ GC_API void (*GC_is_visible_print_proc) /* This returns a list of objects, linked through their first */ /* word. Its use can greatly reduce lock contention problems, since */ /* the allocation lock can be acquired and released many fewer times. */ +/* lb must be large enough to hold the pointer field. */ GC_PTR GC_malloc_many(size_t lb); #define GC_NEXT(p) (*(GC_PTR *)(p)) /* Retrieve the next element */ /* in returned list. */ diff --git a/dbg_mlc.c b/dbg_mlc.c index 930ab3e..670cc53 100644 --- a/dbg_mlc.c +++ b/dbg_mlc.c @@ -12,8 +12,11 @@ * provided the above notices are retained, and a notice that the code was * modified is included with the above copyright notice. */ -/* Boehm, October 9, 1995 1:16 pm PDT */ +# define I_HIDE_POINTERS # include "gc_priv.h" +# ifdef KEEP_BACK_PTRS +# include "backptr.h" +# endif void GC_default_print_heap_obj_proc(); GC_API void GC_register_finalizer_no_order @@ -31,6 +34,14 @@ GC_API void GC_register_finalizer_no_order /* Object header */ typedef struct { +# ifdef KEEP_BACK_PTRS + ptr_t oh_back_ptr; +# define MARKED_FOR_FINALIZATION (ptr_t)(-1) + /* Object was marked because it is finalizable. */ +# ifdef ALIGN_DOUBLE + word oh_dummy; +# endif +# endif char * oh_string; /* object descriptor string */ word oh_int; /* object descriptor integers */ # ifdef NEED_CALLINFO @@ -85,6 +96,134 @@ ptr_t p; return(FALSE); } +#ifdef KEEP_BACK_PTRS + /* Store back pointer to source in dest, if that appears to be possible. */ + /* This is not completely safe, since we may mistakenly conclude that */ + /* dest has a debugging wrapper. But the error probability is very */ + /* small, and this shouldn't be used in production code. */ + /* We assume that dest is the real base pointer. Source will usually */ + /* be a pointer to the interior of an object. */ + void GC_store_back_pointer(ptr_t source, ptr_t dest) + { + if (GC_has_debug_info(dest)) { + ((oh *)dest) -> oh_back_ptr = (ptr_t)HIDE_POINTER(source); + } + } + + void GC_marked_for_finalization(ptr_t dest) { + GC_store_back_pointer(MARKED_FOR_FINALIZATION, dest); + } + + /* Store information about the object referencing dest in *base_p */ + /* and *offset_p. */ + /* source is root ==> *base_p = 0, *offset_p = address */ + /* source is heap object ==> *base_p != 0, *offset_p = offset */ + /* Returns 1 on success, 0 if source couldn't be determined. */ + /* Dest can be any address within a heap object. */ + GC_ref_kind GC_get_back_ptr_info(void *dest, void **base_p, size_t *offset_p) + { + oh * hdr = (oh *)GC_base(dest); + ptr_t bp; + ptr_t bp_base; + if (!GC_has_debug_info((ptr_t) hdr)) return GC_NO_SPACE; + bp = hdr -> oh_back_ptr; + if (MARKED_FOR_FINALIZATION == bp) return GC_FINALIZER_REFD; + if (0 == bp) return GC_UNREFERENCED; + bp = REVEAL_POINTER(bp); + bp_base = GC_base(bp); + if (0 == bp_base) { + *base_p = bp; + *offset_p = 0; + return GC_REFD_FROM_ROOT; + } else { + if (GC_has_debug_info(bp_base)) bp_base += sizeof(oh); + *base_p = bp_base; + *offset_p = bp - bp_base; + return GC_REFD_FROM_HEAP; + } + } + + /* Generate a random heap address. */ + /* The resulting address is in the heap, but */ + /* not necessarily inside a valid object. */ + void *GC_generate_random_heap_address(void) + { + int i; + int heap_offset = random() % GC_heapsize; + for (i = 0; i < GC_n_heap_sects; ++ i) { + int size = GC_heap_sects[i].hs_bytes; + if (heap_offset < size) { + return GC_heap_sects[i].hs_start + heap_offset; + } else { + heap_offset -= size; + } + } + ABORT("GC_generate_random_heap_address: size inconsistency"); + /*NOTREACHED*/ + return 0; + } + + /* Generate a random address inside a valid marked heap object. */ + void *GC_generate_random_valid_address(void) + { + ptr_t result; + ptr_t base; + for (;;) { + result = GC_generate_random_heap_address(); + base = GC_base(result); + if (0 == base) continue; + if (!GC_is_marked(base)) continue; + return result; + } + } + + /* Force a garbage collection and generate a backtrace from a */ + /* random heap address. */ + void GC_generate_random_backtrace(void) + { + void * current; + int i; + void * base; + size_t offset; + GC_ref_kind source; + GC_gcollect(); + current = GC_generate_random_valid_address(); + GC_printf1("Chose address 0x%lx in object\n", (unsigned long)current); + GC_print_heap_obj(GC_base(current)); + GC_err_printf0("\n"); + for (i = 0; ; ++i) { + source = GC_get_back_ptr_info(current, &base, &offset); + if (GC_UNREFERENCED == source) { + GC_err_printf0("Reference could not be found\n"); + goto out; + } + if (GC_NO_SPACE == source) { + GC_err_printf0("No debug info in object: Can't find reference\n"); + goto out; + } + GC_err_printf1("Reachable via %d levels of pointers from ", + (unsigned long)i); + switch(source) { + case GC_REFD_FROM_ROOT: + GC_err_printf1("root at 0x%lx\n", (unsigned long)base); + goto out; + case GC_FINALIZER_REFD: + GC_err_printf0("list of finalizable objects\n"); + goto out; + case GC_REFD_FROM_HEAP: + GC_err_printf1("offset %ld in object:\n", (unsigned long)offset); + /* Take GC_base(base) to get real base, i.e. header. */ + GC_print_heap_obj(GC_base(base)); + GC_err_printf0("\n"); + break; + } + current = base; + } + out:; + } + +#endif /* KEEP_BACK_PTRS */ + /* Store debugging info into p. Return displaced pointer. */ /* Assumes we don't hold allocation lock. */ ptr_t GC_store_debug_info(p, sz, string, integer) @@ -100,6 +239,9 @@ word integer; /* But that's expensive. And this way things should only appear */ /* inconsistent while we're in the handler. */ LOCK(); +# ifdef KEEP_BACK_PTRS + ((oh *)p) -> oh_back_ptr = 0; +# endif ((oh *)p) -> oh_string = string; ((oh *)p) -> oh_int = integer; ((oh *)p) -> oh_sz = sz; diff --git a/finalize.c b/finalize.c index f33ae73..29856f0 100644 --- a/finalize.c +++ b/finalize.c @@ -505,6 +505,7 @@ void GC_finalize() for (curr_fo = fo_head[i]; curr_fo != 0; curr_fo = fo_next(curr_fo)) { real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base); if (!GC_is_marked(real_ptr)) { + GC_MARKED_FOR_FINALIZATION(real_ptr); GC_MARK_FO(real_ptr, curr_fo -> fo_mark_proc); if (GC_is_marked(real_ptr)) { WARN("Finalization cycle involving %lx\n", real_ptr); diff --git a/gc.h b/gc.h index ceabb02..7c734c8 100644 --- a/gc.h +++ b/gc.h @@ -692,6 +692,7 @@ GC_API void (*GC_is_visible_print_proc) /* This returns a list of objects, linked through their first */ /* word. Its use can greatly reduce lock contention problems, since */ /* the allocation lock can be acquired and released many fewer times. */ +/* lb must be large enough to hold the pointer field. */ GC_PTR GC_malloc_many(size_t lb); #define GC_NEXT(p) (*(GC_PTR *)(p)) /* Retrieve the next element */ /* in returned list. */ diff --git a/gc_mark.h b/gc_mark.h index 8b57c31..4628323 100644 --- a/gc_mark.h +++ b/gc_mark.h @@ -171,6 +171,8 @@ mse * GC_signal_mark_stack_overflow(); /* Mark bit is already set */ \ goto exit_label; \ } \ + GC_STORE_BACK_PTR((ptr_t)source, (ptr_t)HBLKPTR(current) \ + + WORDS_TO_BYTES(displ)); \ *mark_word_addr = mark_word | mark_bit; \ } \ PUSH_OBJ(((word *)(HBLKPTR(current)) + displ), hhdr, \ diff --git a/gc_priv.h b/gc_priv.h index 83eb84a..5ce52a7 100644 --- a/gc_priv.h +++ b/gc_priv.h @@ -1676,6 +1676,16 @@ void GC_print_heap_sects(); void GC_print_static_roots(); void GC_dump(); +#ifdef KEEP_BACK_PTRS + void GC_store_back_pointer(ptr_t source, ptr_t dest); + void GC_marked_for_finalization(ptr_t dest); +# define GC_STORE_BACK_PTR(source, dest) GC_store_back_pointer(source, dest) +# define GC_MARKED_FOR_FINALIZATION(dest) GC_marked_for_finalization(dest) +#else +# define GC_STORE_BACK_PTR(source, dest) +# define GC_MARKED_FOR_FINALIZATION(dest) +#endif + /* Make arguments appear live to compiler */ # ifdef __WATCOMC__ void GC_noop(void*, ...); diff --git a/gcconfig.h b/gcconfig.h index 94407e1..c38c575 100644 --- a/gcconfig.h +++ b/gcconfig.h @@ -43,7 +43,7 @@ # define OPENBSD # define mach_type_known # endif -# if defined(__OpenBSD__) && defined(sparc) +# if defined(__OpenBSD__) && defined(__sparc__) # define SPARC # define OPENBSD # define mach_type_known diff --git a/include/backptr.h b/include/backptr.h new file mode 100644 index 0000000..d34224e --- /dev/null +++ b/include/backptr.h @@ -0,0 +1,56 @@ +/* + * This is a simple API to implement pointer back tracing, i.e. + * to answer questions such as "who is pointing to this" or + * "why is this object being retained by the collector" + * + * This API assumes that we have an ANSI C compiler. + * + * Most of these calls yield useful information on only after + * a garbage collection. Usually the client will first force + * a full collection and then gather information, preferably + * before much intervening allocation. + * + * The implementation of the interface is only about 99.9999% + * correct. It is intended to be good enough for profiling, + * but is not intended to be used with production code. + * + * Results are likely to be much more useful if all allocation is + * accomplished through the debugging allocators. + * + * The implementation idea is due to A. Demers. + */ + +/* Store information about the object referencing dest in *base_p */ +/* and *offset_p. */ +/* If multiple objects or roots point to dest, the one reported */ +/* will be the last on used by the garbage collector to trace the */ +/* object. */ +/* source is root ==> *base_p = address, *offset_p = 0 */ +/* source is heap object ==> *base_p != 0, *offset_p = offset */ +/* Returns 1 on success, 0 if source couldn't be determined. */ +/* Dest can be any address within a heap object. */ +typedef enum { GC_UNREFERENCED, /* No refence info available. */ + GC_NO_SPACE, /* Dest not allocated with debug alloc */ + GC_REFD_FROM_ROOT, /* Referenced directly by root *base_p */ + GC_REFD_FROM_HEAP, /* Referenced from another heap obj. */ + GC_FINALIZER_REFD /* Finalizable and hence accessible. */ +} GC_ref_kind; + +GC_ref_kind GC_get_back_ptr_info(void *dest, void **base_p, size_t *offset_p); + +/* Generate a random heap address. */ +/* The resulting address is in the heap, but */ +/* not necessarily inside a valid object. */ +void * GC_generate_random_heap_address(void); + +/* Generate a random address inside a valid marked heap object. */ +void * GC_generate_random_valid_address(void); + +/* Force a garbage collection and generate a backtrace from a */ +/* random heap address. */ +/* This uses the GC logging mechanism (GC_printf) to produce */ +/* output. It can often be called from a debugger. The */ +/* source in dbg_mlc.c also serves as a sample client. */ +void GC_generate_random_backtrace(void); + + diff --git a/include/gc.h b/include/gc.h index ceabb02..7c734c8 100644 --- a/include/gc.h +++ b/include/gc.h @@ -692,6 +692,7 @@ GC_API void (*GC_is_visible_print_proc) /* This returns a list of objects, linked through their first */ /* word. Its use can greatly reduce lock contention problems, since */ /* the allocation lock can be acquired and released many fewer times. */ +/* lb must be large enough to hold the pointer field. */ GC_PTR GC_malloc_many(size_t lb); #define GC_NEXT(p) (*(GC_PTR *)(p)) /* Retrieve the next element */ /* in returned list. */ diff --git a/include/private/gc_priv.h b/include/private/gc_priv.h index 83eb84a..5ce52a7 100644 --- a/include/private/gc_priv.h +++ b/include/private/gc_priv.h @@ -1676,6 +1676,16 @@ void GC_print_heap_sects(); void GC_print_static_roots(); void GC_dump(); +#ifdef KEEP_BACK_PTRS + void GC_store_back_pointer(ptr_t source, ptr_t dest); + void GC_marked_for_finalization(ptr_t dest); +# define GC_STORE_BACK_PTR(source, dest) GC_store_back_pointer(source, dest) +# define GC_MARKED_FOR_FINALIZATION(dest) GC_marked_for_finalization(dest) +#else +# define GC_STORE_BACK_PTR(source, dest) +# define GC_MARKED_FOR_FINALIZATION(dest) +#endif + /* Make arguments appear live to compiler */ # ifdef __WATCOMC__ void GC_noop(void*, ...); diff --git a/include/private/gcconfig.h b/include/private/gcconfig.h index 94407e1..c38c575 100644 --- a/include/private/gcconfig.h +++ b/include/private/gcconfig.h @@ -43,7 +43,7 @@ # define OPENBSD # define mach_type_known # endif -# if defined(__OpenBSD__) && defined(sparc) +# if defined(__OpenBSD__) && defined(__sparc__) # define SPARC # define OPENBSD # define mach_type_known diff --git a/mark.c b/mark.c index 15c4876..34db472 100644 --- a/mark.c +++ b/mark.c @@ -681,7 +681,7 @@ word p; # endif /* As above, but argument passed preliminary test. */ -# ifdef PRINT_BLACK_LIST +# if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS) void GC_push_one_checked(p, interior_ptrs, source) ptr_t source; # else @@ -744,6 +744,7 @@ register GC_bool interior_ptrs; } else { if (!mark_bit_from_hdr(hhdr, displ)) { set_mark_bit_from_hdr(hhdr, displ); + GC_STORE_BACK_PTR(source, (ptr_t)r); PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top, &(GC_mark_stack[GC_mark_stack_size])); } diff --git a/os_dep.c b/os_dep.c index e08a936..81f74f3 100644 --- a/os_dep.c +++ b/os_dep.c @@ -72,7 +72,7 @@ # define NEED_FIND_LIMIT # endif -# if defined(LINUX) && (defined(POWERPC) || defined(SPARC)) +# if defined(LINUX) && (defined(POWERPC) || defined(SPARC) || defined(ALPHA)) # define NEED_FIND_LIMIT # endif @@ -2412,7 +2412,6 @@ struct hblk *h; # else # include # endif -# include # endif # endif # if NARGS > 6 diff --git a/test.c b/test.c index 0fdb030..c67856c 100644 --- a/test.c +++ b/test.c @@ -930,7 +930,7 @@ void check_heap_stats() int late_finalize_count = 0; if (sizeof(char *) > 4) { - max_heap_sz = 13000000; + max_heap_sz = 15000000; } else { max_heap_sz = 11000000; } diff --git a/version.h b/version.h index 8466409..2e96c13 100644 --- a/version.h +++ b/version.h @@ -1,6 +1,6 @@ #define GC_VERSION_MAJOR 5 #define GC_VERSION_MINOR 0 -#define GC_ALPHA_VERSION 1 +#define GC_ALPHA_VERSION 2 # define GC_NOT_ALPHA 0xff -- 2.7.4