remove gc

1 files changed, 0 insertions, 447 deletions

diff --git a/gc/backgraph.c b/gc/backgraph.c
deleted file mode 100644
index 01ab738..0000000
--- a/gc/backgraph.c
+++ /dev/null
@@ -1,447 +0,0 @@
-/*
- * Copyright (c) 2001 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.
- *
- * Permission is hereby granted to use or copy this program
- * for any purpose,  provided the above notices are retained on all copies.
- * 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 implements a full, though not well-tuned, representation of the
- * backwards points-to graph.  This is used to test for non-GC-robust
- * data structures; the code is not used during normal garbage collection.
- *
- * One restriction is that we drop all back-edges from nodes with very
- * high in-degree, and simply add them add them to a list of such
- * nodes.  They are then treated as permanent roots.  Id this by itself
- * doesn't introduce a space leak, then such nodes can't contribute to
- * a growing space leak.
- */
-
-#ifdef MAKE_BACK_GRAPH
-
-#define MAX_IN	10	/* Maximum in-degree we handle directly */
-
-#include "private/dbg_mlc.h"
-#include <unistd.h>
-
-#if !defined(DBG_HDRS_ALL) || (ALIGNMENT != CPP_WORDSZ/8) || !defined(UNIX_LIKE)
-# error Configuration doesnt support MAKE_BACK_GRAPH
-#endif
-
-/* We store single back pointers directly in the object's oh_bg_ptr field.   */
-/* If there is more than one ptr to an object, we store q | FLAG_MANY, 	     */
-/* where q is a pointer to a back_edges object.				     */
-/* Every once in a while we use a back_edges object even for a single	     */
-/* pointer, since we need the other fields in the back_edges structure to    */
-/* be present in some fraction of the objects.  Otherwise we get serious     */
-/* performance issues.							     */
-#define FLAG_MANY 2
-
-typedef struct back_edges_struct {
-  word n_edges;	/* Number of edges, including those in continuation	*/
-  		/* structures.						*/
-  unsigned short flags;
-#	define RETAIN 1	/* Directly points to a reachable object;	*/
-  			/* retain for next GC.				*/
-  unsigned short height_gc_no;
-  		/* If height > 0, then the GC_gc_no value when it	*/
-  		/* was computed.  If it was computed this cycle, then	*/
-  		/* it is current.  If it was computed during the	*/
-  		/* last cycle, then it represents the old height,	*/
-  		/* which is only saved for live objects referenced by	*/
-  		/* dead ones.  This may grow due to refs from newly	*/
-		/* dead objects.				        */
-  signed_word height;
-  		/* Longest path through unreachable nodes to this node	*/
-  		/* that we found using depth first search.		*/
-  
-#   define HEIGHT_UNKNOWN ((signed_word)(-2))
-#   define HEIGHT_IN_PROGRESS ((signed_word)(-1))
-  ptr_t edges[MAX_IN];
-  struct back_edges_struct *cont;
-  		/* Pointer to continuation structure; we use only the	*/
-  		/* edges field in the continuation.			*/
-  		/* also used as free list link.				*/
-} back_edges;
-
-/* Allocate a new back edge structure.  Should be more sophisticated	*/
-/* if this were production code.					*/
-#define MAX_BACK_EDGE_STRUCTS 100000
-static back_edges *back_edge_space = 0;
-int GC_n_back_edge_structs = 0;	/* Serves as pointer to never used	*/
-				/* back_edges space.			*/
-static back_edges *avail_back_edges = 0;
-				/* Pointer to free list of deallocated	*/
-				/* back_edges structures.		*/
-
-static back_edges * new_back_edges(void)
-{
-  if (0 == back_edge_space) {
-    back_edge_space = (back_edges *)
-	    		sbrk(MAX_BACK_EDGE_STRUCTS*sizeof(back_edges));
-  }
-  if (0 != avail_back_edges) {
-    back_edges * result = avail_back_edges;
-    avail_back_edges = result -> cont;
-    result -> cont = 0;
-    return result;
-  }
-  if (GC_n_back_edge_structs >= MAX_BACK_EDGE_STRUCTS - 1) {
-    ABORT("needed too much space for back edges: adjust "
-	  "MAX_BACK_EDGE_STRUCTS");
-  }
-  return back_edge_space + (GC_n_back_edge_structs++);
-}
-
-/* Deallocate p and its associated continuation structures.	*/
-static void deallocate_back_edges(back_edges *p)
-{
-   back_edges *last = p;
-
-   while (0 != last -> cont) last = last -> cont;
-   last -> cont = avail_back_edges;
-   avail_back_edges = p;
-}
-
-/* Table of objects that are currently on the depth-first search	*/
-/* stack.  Only objects with in-degree one are in this table.		*/
-/* Other objects are identified using HEIGHT_IN_PROGRESS.		*/
-/* This data structure NEEDS IMPROVEMENT.				*/
-#define MAX_IN_PROGRESS 10000
-static ptr_t * in_progress_space = 0;
-static int n_in_progress = 0;
-
-static void push_in_progress(ptr_t p)
-{
-  if (in_progress_space == 0)
-      in_progress_space = sbrk(MAX_IN_PROGRESS * sizeof(ptr_t));
-  if (n_in_progress == MAX_IN_PROGRESS)
-      ABORT("Exceeded MAX_IN_PROGRESS");
-  in_progress_space[n_in_progress++] = p;
-}
-
-static GC_bool is_in_progress(ptr_t p)
-{
-  int i;
-  for (i = 0; i < n_in_progress; ++i) {
-    if (in_progress_space[i] == p) return TRUE;
-  }
-  return FALSE;
-}
-
-static void pop_in_progress(ptr_t p)
-{
-  --n_in_progress;
-  GC_ASSERT(in_progress_space[n_in_progress] == p);
-}
-
-#define GET_OH_BG_PTR(p) \
-		(ptr_t)REVEAL_POINTER(((oh *)(p)) -> oh_bg_ptr)
-#define SET_OH_BG_PTR(p,q) (((oh *)(p)) -> oh_bg_ptr) = HIDE_POINTER(q)
-
-/* Execute s once for each predecessor q of p in the points-to graph. 	*/
-/* s should be a bracketed statement.  We declare q.			*/
-#define FOR_EACH_PRED(q, p, s) \
-  { \
-    ptr_t q = GET_OH_BG_PTR(p); \
-    if (!((word)q & FLAG_MANY)) { \
-      if (q && !((word)q & 1)) s \
-	      /* !((word)q & 1) checks for a misnterpreted freelist link */ \
-    } else { \
-      back_edges *orig_be_ = (back_edges *)((word)q & ~FLAG_MANY); \
-      back_edges *be_ = orig_be_; \
-      int total_, local_; \
-      int n_edges_ = be_ -> n_edges; \
-      for (total_ = 0, local_ = 0; total_ < n_edges_; ++local_, ++total_) { \
-	  if (local_ == MAX_IN) { \
-	      be_ = be_ -> cont; \
-	      local_ = 0; \
-	  } \
-	  q = be_ -> edges[local_]; s \
-      } \
-    } \
-  }
-
-/* Ensure that p has a back_edges structure associated with it.	*/
-static void ensure_struct(ptr_t p)
-{
-  ptr_t old_back_ptr = GET_OH_BG_PTR(p);
-
-  if (!((word)old_back_ptr & FLAG_MANY)) {
-    back_edges *be = new_back_edges();
-    be -> flags = 0;
-    if (0 == old_back_ptr) {
-      be -> n_edges = 0;
-    } else {
-      be -> n_edges = 1;
-      be -> edges[0] = old_back_ptr;
-    }
-    be -> height = HEIGHT_UNKNOWN;
-    be -> height_gc_no = GC_gc_no - 1;
-    GC_ASSERT(be >= back_edge_space);
-    SET_OH_BG_PTR(p, (word)be | FLAG_MANY);
-  }
-}
-
-/* Add the (forward) edge from p to q to the backward graph.  Both p	*/
-/* q are pointers to the object base, i.e. pointers to an oh.		*/
-static void add_edge(ptr_t p,  ptr_t q)
-{
-    ptr_t old_back_ptr = GET_OH_BG_PTR(q);
-    back_edges * be, *be_cont;
-    word i;
-    static unsigned random_number = 13;
-#   define GOT_LUCKY_NUMBER (((++random_number) & 0x7f) == 0)
-      /* A not very random number we use to occasionally allocate a	*/
-      /* back_edges structure even for a single backward edge.  This	*/
-      /* prevents us from repeatedly tracing back through very long	*/
-      /* chains, since we will have some place to store height and	*/
-      /* in_progress flags along the way.				*/
-
-    GC_ASSERT(p == GC_base(p) && q == GC_base(q));
-    if (!GC_HAS_DEBUG_INFO(q) || !GC_HAS_DEBUG_INFO(p)) {
-      /* This is really a misinterpreted free list link, since we saw */
-      /* a pointer to a free list.  Dont overwrite it!		      */
-      return;
-    }
-    if (0 == old_back_ptr) {
-	SET_OH_BG_PTR(q, p);
-	if (GOT_LUCKY_NUMBER) ensure_struct(q);
-	return;
-    }
-    /* Check whether it was already in the list of predecessors. */
-      FOR_EACH_PRED(pred, q, { if (p == pred) return; });
-    ensure_struct(q);
-    old_back_ptr = GET_OH_BG_PTR(q);
-    be = (back_edges *)((word)old_back_ptr & ~FLAG_MANY);
-    for (i = be -> n_edges, be_cont = be; i > MAX_IN;
-	be_cont = be_cont -> cont, i -= MAX_IN) {}
-    if (i == MAX_IN) {
-	be_cont -> cont = new_back_edges();
-	be_cont = be_cont -> cont;
-	i = 0;
-    }
-    be_cont -> edges[i] = p;
-    be -> n_edges++;
-    if (be -> n_edges == 100) {
-#       if 0
-	  if (GC_print_stats) {
-	    GC_err_printf0("The following object has in-degree >= 100:\n");
-	    GC_print_heap_obj(q);
-	  }
-#	endif
-    }
-}
-
-typedef void (*per_object_func)(ptr_t p, word n_words, word gc_descr);
-
-static void per_object_helper(struct hblk *h, word fn)
-{
-  hdr * hhdr = HDR(h);
-  word sz = hhdr -> hb_sz;
-  word descr = hhdr -> hb_descr;
-  per_object_func f = (per_object_func)fn;
-  int i = 0;
-
-  do {
-    f((ptr_t)(h -> hb_body + i), sz, descr);
-    i += sz;
-  } while (i + sz <= BYTES_TO_WORDS(HBLKSIZE));
-}
-
-void GC_apply_to_each_object(per_object_func f)
-{
-  GC_apply_to_all_blocks(per_object_helper, (word)f);
-}
-
-static void reset_back_edge(ptr_t p, word n_words, word gc_descr)
-{
-  /* Skip any free list links, or dropped blocks */
-  if (GC_HAS_DEBUG_INFO(p)) {
-    ptr_t old_back_ptr = GET_OH_BG_PTR(p);
-    if ((word)old_back_ptr & FLAG_MANY) {
-      back_edges *be = (back_edges *)((word)old_back_ptr & ~FLAG_MANY);
-      if (!(be -> flags & RETAIN)) {
-	deallocate_back_edges(be);
-        SET_OH_BG_PTR(p, 0); 
-      } else {
-        word *currentp;
-
-	GC_ASSERT(GC_is_marked(p));
-
-	/* Back edges may point to objects that will not be retained. 	*/
-	/* Delete them for now, but remember the height.		*/
-	/* Some will be added back at next GC.				*/
-	  be -> n_edges = 0;
-	  if (0 != be -> cont) {
-	    deallocate_back_edges(be -> cont);
-	    be -> cont = 0;
-	  }
-
-	GC_ASSERT(GC_is_marked(p));
-
-	/* We only retain things for one GC cycle at a time.		*/
-	  be -> flags &= ~RETAIN;
-      }
-    } else /* Simple back pointer */ {
-      /* Clear to avoid dangling pointer. */
-      SET_OH_BG_PTR(p, 0);
-    }
-  }
-}
-
-static void add_back_edges(ptr_t p, word n_words, word gc_descr)
-{
-  word *currentp = (word *)(p + sizeof(oh));
-
-  /* For now, fix up non-length descriptors conservatively.	*/
-    if((gc_descr & GC_DS_TAGS) != GC_DS_LENGTH) {
-      gc_descr = WORDS_TO_BYTES(n_words);
-    }
-  while (currentp < (word *)(p + gc_descr)) {
-    word current = *currentp++;
-    if (current >= (word)GC_least_plausible_heap_addr && 
-	current <= (word)GC_greatest_plausible_heap_addr) {
-       ptr_t target = GC_base((GC_PTR)current);
-       if (0 != target) {
-	 add_edge(p, target);
-       }
-    }
-  }
-}
-
-/* Rebuild the reprentation of the backward reachability graph.	*/
-/* Does not examine mark bits.  Can be called before GC.	*/
-void GC_build_back_graph(void)
-{
-  GC_apply_to_each_object(add_back_edges);
-}
-
-/* Return an approximation to the length of the longest simple path	*/
-/* through unreachable objects to p.  We refer to this as the height	*/
-/* of p.								*/
-static word backwards_height(ptr_t p)
-{
-  word result;
-  ptr_t back_ptr = GET_OH_BG_PTR(p);
-  back_edges *be;
-
-  if (0 == back_ptr) return 1;
-  if (!((word)back_ptr & FLAG_MANY)) {
-    if (is_in_progress(p)) return 0;  /* DFS back edge, i.e. we followed  */
-    				      /* an edge to an object already	  */
-    				      /* on our stack: ignore		  */
-    push_in_progress(p);
-    result = backwards_height(back_ptr)+1;
-    pop_in_progress(p);
-    return result;
-  }
-  be = (back_edges *)((word)back_ptr & ~FLAG_MANY);
-  if (be -> height >= 0 && be -> height_gc_no == GC_gc_no)
-      return be -> height;
-  /* Ignore back edges in DFS */
-    if (be -> height == HEIGHT_IN_PROGRESS) return 0;
-  result = (be -> height > 0? be -> height : 1);
-  be -> height = HEIGHT_IN_PROGRESS;
-  FOR_EACH_PRED(q, p, {
-    word this_height;
-    if (GC_is_marked(q) && !(FLAG_MANY & (word)GET_OH_BG_PTR(p))) {
-      if (GC_print_stats)
-	  GC_printf2("Found bogus pointer from 0x%lx to 0x%lx\n", q, p);
-	/* Reachable object "points to" unreachable one.		*/
-	/* Could be caused by our lax treatment of GC descriptors.	*/
-      this_height = 1;
-    } else {
-        this_height = backwards_height(q);
-    }
-    if (this_height >= result) result = this_height + 1;
-  });
-  be -> height = result;
-  be -> height_gc_no = GC_gc_no;
-  return result;
-}
-
-word GC_max_height;
-ptr_t GC_deepest_obj;
-
-/* Compute the maximum height of every unreachable predecessor p of  a 	*/
-/* reachable object.  Arrange to save the heights of all such objects p	*/
-/* so that they can be used in calculating the height of objects in the	*/
-/* next GC.								*/
-/* Set GC_max_height to be the maximum height we encounter, and 	*/
-/* GC_deepest_obj to be the corresponding object.			*/
-static void update_max_height(ptr_t p, word n_words, word gc_descr)
-{
-  if (GC_is_marked(p) && GC_HAS_DEBUG_INFO(p)) {
-    int i;
-    word p_height = 0;
-    ptr_t p_deepest_obj = 0;
-    ptr_t back_ptr;
-    back_edges *be = 0;
-
-    /* If we remembered a height last time, use it as a minimum.	*/
-    /* It may have increased due to newly unreachable chains pointing	*/
-    /* to p, but it can't have decreased.				*/
-    back_ptr = GET_OH_BG_PTR(p);
-    if (0 != back_ptr && ((word)back_ptr & FLAG_MANY)) {
-      be = (back_edges *)((word)back_ptr & ~FLAG_MANY);
-      if (be -> height != HEIGHT_UNKNOWN) p_height = be -> height;
-    }
-    FOR_EACH_PRED(q, p, {
-      if (!GC_is_marked(q) && GC_HAS_DEBUG_INFO(q)) {
-        word q_height;
-
-        q_height = backwards_height(q);
-	if (q_height > p_height) {
-	  p_height = q_height;
-	  p_deepest_obj = q;
-	}
-      }
-    });
-    if (p_height > 0) {
-      /* Remember the height for next time. */
-	if (be == 0) {
-    	  ensure_struct(p);
-    	  back_ptr = GET_OH_BG_PTR(p);
-  	  be = (back_edges *)((word)back_ptr & ~FLAG_MANY);
-	}
-	be -> flags |= RETAIN;
-	be -> height = p_height;
-	be -> height_gc_no = GC_gc_no;
-    }
-    if (p_height > GC_max_height) {
-	GC_max_height = p_height;
-	GC_deepest_obj = p_deepest_obj;
-    }
-  }
-}
-
-void GC_traverse_back_graph(void)
-{
-  static word max_max_height = 0;
-  GC_max_height = 0;
-  GC_apply_to_each_object(update_max_height);
-  GC_printf2("Maximum backwards height of reachable objects at GC %lu is %ld\n",
-	     (unsigned long) GC_gc_no, GC_max_height);
-  if (GC_max_height > max_max_height) {
-    max_max_height = GC_max_height;
-    GC_printf0("The following unreachable object is last in a longest chain "
-	       "of unreachable objects:\n");
-    GC_print_heap_obj(GC_deepest_obj);
-  }
-  if (GC_print_stats) {
-    GC_printf1("Needed max total of %ld back-edge structs\n",
-	       GC_n_back_edge_structs);
-  }
-  GC_apply_to_each_object(reset_back_edge);
-  GC_deepest_obj = 0;
-}
-
-#endif /* MAKE_BACK_GRAPH */