Merged GC 5.0alpha4 with local changes, plus:

	* Makefile.in: Rebuilt.
	* Makefile.am (gctest_LDADD): Added THREADLIB.
	(TESTS): New macro.
	* configure: Rebuilt.
	* configure.in (INCLUDES): New subst.

From-SVN: r30332

1 files changed, 235 insertions, 59 deletions

diff --git a/boehm-gc/reclaim.c b/boehm-gc/reclaim.c
index 407b4c6..6e0f53b 100644
--- a/boehm-gc/reclaim.c
+++ b/boehm-gc/reclaim.c
@@ -1,6 +1,8 @@
 /* 
  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
- * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
+ * Copyright (c) 1991-1996 by Xerox Corporation.  All rights reserved.
+ * Copyright (c) 1996-1999 by Silicon Graphics.  All rights reserved.
+ * Copyright (c) 1999 by Hewlett-Packard Company. All rights reserved.
  *
  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
@@ -11,7 +13,6 @@
  * provided the above notices are retained, and a notice that the code was
  * modified is included with the above copyright notice.
  */
-/* Boehm, February 15, 1996 2:41 pm PST */
 
 #include <stdio.h>
 #include "gc_priv.h"
@@ -19,7 +20,6 @@
 signed_word GC_mem_found = 0;
 			/* Number of words of memory reclaimed     */
 
-# ifdef FIND_LEAK
 static void report_leak(p, sz)
 ptr_t p;
 word sz;
@@ -39,13 +39,10 @@ word sz;
 }
 
 #   define FOUND_FREE(hblk, word_no) \
-      if (abort_if_found) { \
+      { \
          report_leak((ptr_t)hblk + WORDS_TO_BYTES(word_no), \
          	     HDR(hblk) -> hb_sz); \
       }
-# else
-#   define FOUND_FREE(hblk, word_no)
-# endif
 
 /*
  * reclaim phase
@@ -71,6 +68,139 @@ register hdr * hhdr;
     return(TRUE);
 }
 
+/* The following functions sometimes return a DONT_KNOW value. */
+#define DONT_KNOW  2
+
+#ifdef SMALL_CONFIG
+# define GC_block_nearly_full1(hhdr, pat1) DONT_KNOW
+# define GC_block_nearly_full3(hhdr, pat1, pat2) DONT_KNOW
+# define GC_block_nearly_full(hhdr) DONT_KNOW
+#else
+
+/*
+ * Test whether nearly all of the mark words consist of the same
+ * repeating pattern.
+ */
+#define FULL_THRESHOLD (MARK_BITS_SZ/16)
+
+GC_bool GC_block_nearly_full1(hhdr, pat1)
+hdr *hhdr;
+word pat1;
+{
+    unsigned i;
+    unsigned misses = 0;
+    GC_ASSERT((MARK_BITS_SZ & 1) == 0);
+    for (i = 0; i < MARK_BITS_SZ; ++i) {
+	if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
+	    if (++misses > FULL_THRESHOLD) return FALSE;
+	}
+    }
+    return TRUE;
+}
+
+/*
+ * Test whether the same repeating 3 word pattern occurs in nearly
+ * all the mark bit slots.
+ * This is used as a heuristic, so we're a bit sloppy and ignore
+ * the last one or two words.
+ */
+GC_bool GC_block_nearly_full3(hhdr, pat1, pat2, pat3)
+hdr *hhdr;
+word pat1, pat2, pat3;
+{
+    unsigned i;
+    unsigned misses = 0;
+
+    if (MARK_BITS_SZ < 4) {
+      return DONT_KNOW;
+    }
+    for (i = 0; i < MARK_BITS_SZ - 2; i += 3) {
+	if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
+	    if (++misses > FULL_THRESHOLD) return FALSE;
+	}
+	if ((hhdr -> hb_marks[i+1] | ~pat2) != ONES) {
+	    if (++misses > FULL_THRESHOLD) return FALSE;
+	}
+	if ((hhdr -> hb_marks[i+2] | ~pat3) != ONES) {
+	    if (++misses > FULL_THRESHOLD) return FALSE;
+	}
+    }
+    return TRUE;
+}
+
+/* Check whether a small object block is nearly full by looking at only */
+/* the mark bits.							*/
+/* We manually precomputed the mark bit patterns that need to be 	*/
+/* checked for, and we give up on the ones that are unlikely to occur,	*/
+/* or have period > 3.							*/
+/* This would be a lot easier with a mark bit per object instead of per	*/
+/* word, but that would rewuire computing object numbers in the mark	*/
+/* loop, which would require different data structures ...		*/
+GC_bool GC_block_nearly_full(hhdr)
+hdr *hhdr;
+{
+    int sz = hhdr -> hb_sz;
+
+#   if CPP_WORDSZ != 32 && CPP_WORDSZ != 64
+      return DONT_KNOW;	/* Shouldn't be used in any standard config.	*/
+#   endif
+    if (0 != HDR_WORDS) return DONT_KNOW;
+	/* Also shouldn't happen */
+#   if CPP_WORDSZ == 32
+      switch(sz) {
+        case 1:
+	  return GC_block_nearly_full1(hhdr, 0xffffffffl);
+	case 2:
+	  return GC_block_nearly_full1(hhdr, 0x55555555l);
+	case 4:
+	  return GC_block_nearly_full1(hhdr, 0x11111111l);
+	case 6:
+	  return GC_block_nearly_full3(hhdr, 0x41041041l,
+					      0x10410410l,
+					       0x04104104l);
+	case 8:
+	  return GC_block_nearly_full1(hhdr, 0x01010101l);
+	case 12:
+	  return GC_block_nearly_full3(hhdr, 0x01001001l,
+					      0x10010010l,
+					       0x00100100l);
+	case 16:
+	  return GC_block_nearly_full1(hhdr, 0x00010001l);
+	case 32:
+	  return GC_block_nearly_full1(hhdr, 0x00000001l);
+	default:
+	  return DONT_KNOW;
+      }
+#   endif
+#   if CPP_WORDSZ == 64
+      switch(sz) {
+        case 1:
+	  return GC_block_nearly_full1(hhdr, 0xffffffffffffffffl);
+	case 2:
+	  return GC_block_nearly_full1(hhdr, 0x5555555555555555l);
+	case 4:
+	  return GC_block_nearly_full1(hhdr, 0x1111111111111111l);
+	case 6:
+	  return GC_block_nearly_full3(hhdr, 0x1041041041041041l,
+					       0x4104104104104104l,
+					         0x0410410410410410l);
+	case 8:
+	  return GC_block_nearly_full1(hhdr, 0x0101010101010101l);
+	case 12:
+	  return GC_block_nearly_full3(hhdr, 0x1001001001001001l,
+					       0x0100100100100100l,
+					         0x0010010010010010l);
+	case 16:
+	  return GC_block_nearly_full1(hhdr, 0x0001000100010001l);
+	case 32:
+	  return GC_block_nearly_full1(hhdr, 0x0000000100000001l);
+	default:
+	  return DONT_KNOW;
+      }
+#   endif
+}
+#endif /* !SMALL_CONFIG */
+
 # ifdef GATHERSTATS
 #   define INCR_WORDS(sz) n_words_found += (sz)
 # else
@@ -82,10 +212,9 @@ register hdr * hhdr;
  * Clears unmarked objects.
  */
 /*ARGSUSED*/
-ptr_t GC_reclaim_clear(hbp, hhdr, sz, list, abort_if_found)
+ptr_t GC_reclaim_clear(hbp, hhdr, sz, list)
 register struct hblk *hbp;	/* ptr to current heap block		*/
 register hdr * hhdr;
-GC_bool abort_if_found;		/* Abort if a reclaimable object is found */
 register ptr_t list;
 register word sz;
 {
@@ -105,7 +234,6 @@ register word sz;
 	    if( mark_bit_from_hdr(hhdr, word_no) ) {
 		p += sz;
 	    } else {
-		FOUND_FREE(hbp, word_no);
 		INCR_WORDS(sz);
 		/* object is available - put on list */
 		    obj_link(p) = list;
@@ -131,10 +259,9 @@ register word sz;
  * A special case for 2 word composite objects (e.g. cons cells):
  */
 /*ARGSUSED*/
-ptr_t GC_reclaim_clear2(hbp, hhdr, list, abort_if_found)
+ptr_t GC_reclaim_clear2(hbp, hhdr, list)
 register struct hblk *hbp;	/* ptr to current heap block		*/
 hdr * hhdr;
-GC_bool abort_if_found;		/* Abort if a reclaimable object is found */
 register ptr_t list;
 {
     register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
@@ -146,7 +273,6 @@ register ptr_t list;
     register int i;
 #   define DO_OBJ(start_displ) \
 	if (!(mark_word & ((word)1 << start_displ))) { \
-	    FOUND_FREE(hbp, p - (word *)hbp + start_displ); \
 	    p[start_displ] = (word)list; \
 	    list = (ptr_t)(p+start_displ); \
 	    p[start_displ+1] = 0; \
@@ -179,10 +305,9 @@ register ptr_t list;
  * Another special case for 4 word composite objects:
  */
 /*ARGSUSED*/
-ptr_t GC_reclaim_clear4(hbp, hhdr, list, abort_if_found)
+ptr_t GC_reclaim_clear4(hbp, hhdr, list)
 register struct hblk *hbp;	/* ptr to current heap block		*/
 hdr * hhdr;
-GC_bool abort_if_found;		/* Abort if a reclaimable object is found */
 register ptr_t list;
 {
     register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
@@ -193,7 +318,6 @@ register ptr_t list;
     register word mark_word;
 #   define DO_OBJ(start_displ) \
 	if (!(mark_word & ((word)1 << start_displ))) { \
-	    FOUND_FREE(hbp, p - (word *)hbp + start_displ); \
 	    p[start_displ] = (word)list; \
 	    list = (ptr_t)(p+start_displ); \
 	    p[start_displ+1] = 0; \
@@ -239,10 +363,9 @@ register ptr_t list;
 
 /* The same thing, but don't clear objects: */
 /*ARGSUSED*/
-ptr_t GC_reclaim_uninit(hbp, hhdr, sz, list, abort_if_found)
+ptr_t GC_reclaim_uninit(hbp, hhdr, sz, list)
 register struct hblk *hbp;	/* ptr to current heap block		*/
 register hdr * hhdr;
-GC_bool abort_if_found;		/* Abort if a reclaimable object is found */
 register ptr_t list;
 register word sz;
 {
@@ -260,7 +383,6 @@ register word sz;
     /* go through all words in block */
 	while( p <= plim )  {
 	    if( !mark_bit_from_hdr(hhdr, word_no) ) {
-		FOUND_FREE(hbp, word_no);
 		INCR_WORDS(sz);
 		/* object is available - put on list */
 		    obj_link(p) = list;
@@ -275,15 +397,42 @@ register word sz;
     return(list);
 }
 
+/* Don't really reclaim objects, just check for unmarked ones: */
+/*ARGSUSED*/
+void GC_reclaim_check(hbp, hhdr, sz)
+register struct hblk *hbp;	/* ptr to current heap block		*/
+register hdr * hhdr;
+register word sz;
+{
+    register int word_no;
+    register word *p, *plim;
+#   ifdef GATHERSTATS
+        register int n_words_found = 0;
+#   endif
+    
+    p = (word *)(hbp->hb_body);
+    word_no = HDR_WORDS;
+    plim = (word *)((((word)hbp) + HBLKSIZE)
+		   - WORDS_TO_BYTES(sz));
+
+    /* go through all words in block */
+	while( p <= plim )  {
+	    if( !mark_bit_from_hdr(hhdr, word_no) ) {
+		FOUND_FREE(hbp, word_no);
+	    }
+	    p += sz;
+	    word_no += sz;
+	}
+}
+
 #ifndef SMALL_CONFIG
 /*
  * Another special case for 2 word atomic objects:
  */
 /*ARGSUSED*/
-ptr_t GC_reclaim_uninit2(hbp, hhdr, list, abort_if_found)
+ptr_t GC_reclaim_uninit2(hbp, hhdr, list)
 register struct hblk *hbp;	/* ptr to current heap block		*/
 hdr * hhdr;
-GC_bool abort_if_found;		/* Abort if a reclaimable object is found */
 register ptr_t list;
 {
     register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
@@ -295,7 +444,6 @@ register ptr_t list;
     register int i;
 #   define DO_OBJ(start_displ) \
 	if (!(mark_word & ((word)1 << start_displ))) { \
-	    FOUND_FREE(hbp, p - (word *)hbp + start_displ); \
 	    p[start_displ] = (word)list; \
 	    list = (ptr_t)(p+start_displ); \
 	    INCR_WORDS(2); \
@@ -327,10 +475,9 @@ register ptr_t list;
  * Another special case for 4 word atomic objects:
  */
 /*ARGSUSED*/
-ptr_t GC_reclaim_uninit4(hbp, hhdr, list, abort_if_found)
+ptr_t GC_reclaim_uninit4(hbp, hhdr, list)
 register struct hblk *hbp;	/* ptr to current heap block		*/
 hdr * hhdr;
-GC_bool abort_if_found;		/* Abort if a reclaimable object is found */
 register ptr_t list;
 {
     register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
@@ -341,7 +488,6 @@ register ptr_t list;
     register word mark_word;
 #   define DO_OBJ(start_displ) \
 	if (!(mark_word & ((word)1 << start_displ))) { \
-	    FOUND_FREE(hbp, p - (word *)hbp + start_displ); \
 	    p[start_displ] = (word)list; \
 	    list = (ptr_t)(p+start_displ); \
 	    INCR_WORDS(4); \
@@ -382,10 +528,9 @@ register ptr_t list;
 
 /* Finally the one word case, which never requires any clearing: */
 /*ARGSUSED*/
-ptr_t GC_reclaim1(hbp, hhdr, list, abort_if_found)
+ptr_t GC_reclaim1(hbp, hhdr, list)
 register struct hblk *hbp;	/* ptr to current heap block		*/
 hdr * hhdr;
-GC_bool abort_if_found;		/* Abort if a reclaimable object is found */
 register ptr_t list;
 {
     register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
@@ -397,7 +542,6 @@ register ptr_t list;
     register int i;
 #   define DO_OBJ(start_displ) \
 	if (!(mark_word & ((word)1 << start_displ))) { \
-	    FOUND_FREE(hbp, p - (word *)hbp + start_displ); \
 	    p[start_displ] = (word)list; \
 	    list = (ptr_t)(p+start_displ); \
 	    INCR_WORDS(1); \
@@ -433,15 +577,16 @@ register ptr_t list;
  * If entirely empty blocks are to be completely deallocated, then
  * caller should perform that check.
  */
-void GC_reclaim_small_nonempty_block(hbp, abort_if_found)
+void GC_reclaim_small_nonempty_block(hbp, report_if_found)
 register struct hblk *hbp;	/* ptr to current heap block		*/
-int abort_if_found;		/* Abort if a reclaimable object is found */
+int report_if_found;		/* Abort if a reclaimable object is found */
 {
     hdr * hhdr;
-    register word sz;		/* size of objects in current block	*/
-    register struct obj_kind * ok;
-    register ptr_t * flh;
-    register int kind;
+    word sz;		/* size of objects in current block	*/
+    struct obj_kind * ok;
+    ptr_t * flh;
+    int kind;
+    GC_bool full;
     
     hhdr = HDR(hbp);
     sz = hhdr -> hb_sz;
@@ -449,43 +594,70 @@ int abort_if_found;		/* Abort if a reclaimable object is found */
     kind = hhdr -> hb_obj_kind;
     ok = &GC_obj_kinds[kind];
     flh = &(ok -> ok_freelist[sz]);
-    GC_write_hint(hbp);
 
-    if (ok -> ok_init) {
+    if (report_if_found) {
+	GC_reclaim_check(hbp, hhdr, sz);
+    } else if (ok -> ok_init) {
       switch(sz) {
 #      ifndef SMALL_CONFIG
         case 1:
-            *flh = GC_reclaim1(hbp, hhdr, *flh, abort_if_found);
+	    full = GC_block_nearly_full1(hhdr, 0xffffffffl);
+	    if (TRUE == full) goto out;
+	    if (FALSE == full) GC_write_hint(hbp);
+	    /* In the DONT_KNOW case, we let reclaim fault.	*/
+            *flh = GC_reclaim1(hbp, hhdr, *flh);
             break;
         case 2:
-            *flh = GC_reclaim_clear2(hbp, hhdr, *flh, abort_if_found);
+	    full = GC_block_nearly_full1(hhdr, 0x55555555l);
+	    if (TRUE == full) goto out;
+	    if (FALSE == full) GC_write_hint(hbp);
+            *flh = GC_reclaim_clear2(hbp, hhdr, *flh);
             break;
         case 4:
-            *flh = GC_reclaim_clear4(hbp, hhdr, *flh, abort_if_found);
+	    full = GC_block_nearly_full1(hhdr, 0x11111111l);
+	    if (TRUE == full) goto out;
+	    if (FALSE == full) GC_write_hint(hbp);
+            *flh = GC_reclaim_clear4(hbp, hhdr, *flh);
             break;
 #      endif
         default:
-            *flh = GC_reclaim_clear(hbp, hhdr, sz, *flh, abort_if_found);
+	    full = GC_block_nearly_full(hhdr);
+	    if (TRUE == full) goto out;
+	    if (FALSE == full) GC_write_hint(hbp);
+            *flh = GC_reclaim_clear(hbp, hhdr, sz, *flh);
             break;
       }
     } else {
       switch(sz) {
 #      ifndef SMALL_CONFIG
         case 1:
-            *flh = GC_reclaim1(hbp, hhdr, *flh, abort_if_found);
+	    full = GC_block_nearly_full1(hhdr, 0xffffffffl);
+	    if (TRUE == full) goto out;
+	    if (FALSE == full) GC_write_hint(hbp);
+            *flh = GC_reclaim1(hbp, hhdr, *flh);
             break;
         case 2:
-            *flh = GC_reclaim_uninit2(hbp, hhdr, *flh, abort_if_found);
+	    full = GC_block_nearly_full1(hhdr, 0x55555555l);
+	    if (TRUE == full) goto out;
+	    if (FALSE == full) GC_write_hint(hbp);
+            *flh = GC_reclaim_uninit2(hbp, hhdr, *flh);
             break;
         case 4:
-            *flh = GC_reclaim_uninit4(hbp, hhdr, *flh, abort_if_found);
+	    full = GC_block_nearly_full1(hhdr, 0x11111111l);
+	    if (TRUE == full) goto out;
+	    if (FALSE == full) GC_write_hint(hbp);
+            *flh = GC_reclaim_uninit4(hbp, hhdr, *flh);
             break;
 #      endif
         default:
-            *flh = GC_reclaim_uninit(hbp, hhdr, sz, *flh, abort_if_found);
+	    full = GC_block_nearly_full(hhdr);
+	    if (TRUE == full) goto out;
+	    if (FALSE == full) GC_write_hint(hbp);
+            *flh = GC_reclaim_uninit(hbp, hhdr, sz, *flh);
             break;
       }
     } 
+out:
     if (IS_UNCOLLECTABLE(kind)) GC_set_hdr_marks(hhdr);
 }
 
@@ -494,11 +666,12 @@ int abort_if_found;		/* Abort if a reclaimable object is found */
  * to the heap block free list.
  * Otherwise enqueue the block for later processing
  * by GC_reclaim_small_nonempty_block.
- * If abort_if_found is TRUE, then process any block immediately.
+ * If report_if_found is TRUE, then process any block immediately, and
+ * simply report free objects; do not actually reclaim them.
  */
-void GC_reclaim_block(hbp, abort_if_found)
+void GC_reclaim_block(hbp, report_if_found)
 register struct hblk *hbp;	/* ptr to current heap block		*/
-word abort_if_found;		/* Abort if a reclaimable object is found */
+word report_if_found;		/* Abort if a reclaimable object is found */
 {
     register hdr * hhdr;
     register word sz;		/* size of objects in current block	*/
@@ -511,16 +684,19 @@ word abort_if_found;		/* Abort if a reclaimable object is found */
 
     if( sz > MAXOBJSZ ) {  /* 1 big object */
         if( !mark_bit_from_hdr(hhdr, HDR_WORDS) ) {
-	    FOUND_FREE(hbp, HDR_WORDS);
-#	    ifdef GATHERSTATS
+	    if (report_if_found) {
+	      FOUND_FREE(hbp, HDR_WORDS);
+	    } else {
+#	      ifdef GATHERSTATS
 	        GC_mem_found += sz;
-#	    endif
-	    GC_freehblk(hbp);
+#	      endif
+	      GC_freehblk(hbp);
+	    }
 	}
     } else {
         GC_bool empty = GC_block_empty(hhdr);
-        if (abort_if_found) {
-    	  GC_reclaim_small_nonempty_block(hbp, (int)abort_if_found);
+        if (report_if_found) {
+    	  GC_reclaim_small_nonempty_block(hbp, (int)report_if_found);
         } else if (empty) {
 #	  ifdef GATHERSTATS
             GC_mem_found += BYTES_TO_WORDS(HBLKSIZE);
@@ -600,11 +776,11 @@ void GC_print_block_list()
 #endif /* NO_DEBUGGING */
 
 /*
- * Do the same thing on the entire heap, after first clearing small object
- * free lists (if we are not just looking for leaks).
+ * Perform GC_reclaim_block on the entire heap, after first clearing
+ * small object free lists (if we are not just looking for leaks).
  */
-void GC_start_reclaim(abort_if_found)
-int abort_if_found;		/* Abort if a GC_reclaimable object is found */
+void GC_start_reclaim(report_if_found)
+int report_if_found;		/* Abort if a GC_reclaimable object is found */
 {
     int kind;
     
@@ -617,7 +793,7 @@ int abort_if_found;		/* Abort if a GC_reclaimable object is found */
         register struct hblk ** rlist = GC_obj_kinds[kind].ok_reclaim_list;
         
         if (rlist == 0) continue;	/* This kind not used.	*/
-        if (!abort_if_found) {
+        if (!report_if_found) {
             lim = &(GC_obj_kinds[kind].ok_freelist[MAXOBJSZ+1]);
 	    for( fop = GC_obj_kinds[kind].ok_freelist; fop < lim; fop++ ) {
 	      *fop = 0;
@@ -637,7 +813,7 @@ int abort_if_found;		/* Abort if a GC_reclaimable object is found */
 
   /* Go through all heap blocks (in hblklist) and reclaim unmarked objects */
   /* or enqueue the block for later processing.				   */
-    GC_apply_to_all_blocks(GC_reclaim_block, (word)abort_if_found);
+    GC_apply_to_all_blocks(GC_reclaim_block, (word)report_if_found);
     
 }