Back to index

plt-scheme  4.2.1
backgraph.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 2001 by Hewlett-Packard Company. All rights reserved.
00003  *
00004  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
00005  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
00006  *
00007  * Permission is hereby granted to use or copy this program
00008  * for any purpose,  provided the above notices are retained on all copies.
00009  * Permission to modify the code and to distribute modified code is granted,
00010  * provided the above notices are retained, and a notice that the code was
00011  * modified is included with the above copyright notice.
00012  *
00013  */
00014 
00015 /*
00016  * This implements a full, though not well-tuned, representation of the
00017  * backwards points-to graph.  This is used to test for non-GC-robust
00018  * data structures; the code is not used during normal garbage collection.
00019  *
00020  * One restriction is that we drop all back-edges from nodes with very
00021  * high in-degree, and simply add them add them to a list of such
00022  * nodes.  They are then treated as permanent roots.  Id this by itself
00023  * doesn't introduce a space leak, then such nodes can't contribute to
00024  * a growing space leak.
00025  */
00026 
00027 #ifdef MAKE_BACK_GRAPH
00028 
00029 #define MAX_IN       10     /* Maximum in-degree we handle directly */
00030 
00031 #include "private/dbg_mlc.h"
00032 #include <unistd.h>
00033 
00034 #if !defined(DBG_HDRS_ALL) || (ALIGNMENT != CPP_WORDSZ/8) || !defined(UNIX_LIKE)
00035 # error Configuration doesnt support MAKE_BACK_GRAPH
00036 #endif
00037 
00038 /* We store single back pointers directly in the object's oh_bg_ptr field.   */
00039 /* If there is more than one ptr to an object, we store q | FLAG_MANY,            */
00040 /* where q is a pointer to a back_edges object.                            */
00041 /* Every once in a while we use a back_edges object even for a single      */
00042 /* pointer, since we need the other fields in the back_edges structure to    */
00043 /* be present in some fraction of the objects.  Otherwise we get serious     */
00044 /* performance issues.                                                     */
00045 #define FLAG_MANY 2
00046 
00047 typedef struct back_edges_struct {
00048   word n_edges;      /* Number of edges, including those in continuation     */
00049               /* structures.                                          */
00050   unsigned short flags;
00051 #      define RETAIN 1      /* Directly points to a reachable object; */
00052                      /* retain for next GC.                           */
00053   unsigned short height_gc_no;
00054               /* If height > 0, then the GC_gc_no value when it       */
00055               /* was computed.  If it was computed this cycle, then   */
00056               /* it is current.  If it was computed during the */
00057               /* last cycle, then it represents the old height,       */
00058               /* which is only saved for live objects referenced by   */
00059               /* dead ones.  This may grow due to refs from newly     */
00060               /* dead objects.                                  */
00061   signed_word height;
00062               /* Longest path through unreachable nodes to this node  */
00063               /* that we found using depth first search.              */
00064   
00065 #   define HEIGHT_UNKNOWN ((signed_word)(-2))
00066 #   define HEIGHT_IN_PROGRESS ((signed_word)(-1))
00067   ptr_t edges[MAX_IN];
00068   struct back_edges_struct *cont;
00069               /* Pointer to continuation structure; we use only the   */
00070               /* edges field in the continuation.                     */
00071               /* also used as free list link.                         */
00072 } back_edges;
00073 
00074 /* Allocate a new back edge structure.  Should be more sophisticated  */
00075 /* if this were production code.                               */
00076 #define MAX_BACK_EDGE_STRUCTS 100000
00077 static back_edges *back_edge_space = 0;
00078 int GC_n_back_edge_structs = 0;    /* Serves as pointer to never used */
00079                             /* back_edges space.               */
00080 static back_edges *avail_back_edges = 0;
00081                             /* Pointer to free list of deallocated    */
00082                             /* back_edges structures.          */
00083 
00084 static back_edges * new_back_edges(void)
00085 {
00086   if (0 == back_edge_space) {
00087     back_edge_space = (back_edges *)
00088                      GET_MEM(MAX_BACK_EDGE_STRUCTS*sizeof(back_edges));
00089   }
00090   if (0 != avail_back_edges) {
00091     back_edges * result = avail_back_edges;
00092     avail_back_edges = result -> cont;
00093     result -> cont = 0;
00094     return result;
00095   }
00096   if (GC_n_back_edge_structs >= MAX_BACK_EDGE_STRUCTS - 1) {
00097     ABORT("needed too much space for back edges: adjust "
00098          "MAX_BACK_EDGE_STRUCTS");
00099   }
00100   return back_edge_space + (GC_n_back_edge_structs++);
00101 }
00102 
00103 /* Deallocate p and its associated continuation structures.    */
00104 static void deallocate_back_edges(back_edges *p)
00105 {
00106    back_edges *last = p;
00107 
00108    while (0 != last -> cont) last = last -> cont;
00109    last -> cont = avail_back_edges;
00110    avail_back_edges = p;
00111 }
00112 
00113 /* Table of objects that are currently on the depth-first search      */
00114 /* stack.  Only objects with in-degree one are in this table.         */
00115 /* Other objects are identified using HEIGHT_IN_PROGRESS.             */
00116 /* FIXME: This data structure NEEDS IMPROVEMENT.               */
00117 #define INITIAL_IN_PROGRESS 10000
00118 static ptr_t * in_progress_space = 0;
00119 static size_t in_progress_size = 0;
00120 static size_t n_in_progress = 0;
00121 
00122 static void push_in_progress(ptr_t p)
00123 {
00124   if (n_in_progress >= in_progress_size) 
00125     if (in_progress_size == 0) {
00126       in_progress_size = INITIAL_IN_PROGRESS;
00127       in_progress_space = (ptr_t *)GET_MEM(in_progress_size * sizeof(ptr_t));
00128     } else {
00129       ptr_t * new_in_progress_space;
00130       in_progress_size *= 2;
00131       new_in_progress_space = (ptr_t *)
00132                             GET_MEM(in_progress_size * sizeof(ptr_t));
00133       BCOPY(in_progress_space, new_in_progress_space,
00134            n_in_progress * sizeof(ptr_t));
00135       in_progress_space = new_in_progress_space;
00136       /* FIXME: This just drops the old space.   */
00137     }
00138   if (in_progress_space == 0)
00139       ABORT("MAKE_BACK_GRAPH: Out of in-progress space: "
00140            "Huge linear data structure?");
00141   in_progress_space[n_in_progress++] = p;
00142 }
00143 
00144 static GC_bool is_in_progress(ptr_t p)
00145 {
00146   int i;
00147   for (i = 0; i < n_in_progress; ++i) {
00148     if (in_progress_space[i] == p) return TRUE;
00149   }
00150   return FALSE;
00151 }
00152 
00153 static void pop_in_progress(ptr_t p)
00154 {
00155   --n_in_progress;
00156   GC_ASSERT(in_progress_space[n_in_progress] == p);
00157 }
00158 
00159 #define GET_OH_BG_PTR(p) \
00160               (ptr_t)REVEAL_POINTER(((oh *)(p)) -> oh_bg_ptr)
00161 #define SET_OH_BG_PTR(p,q) (((oh *)(p)) -> oh_bg_ptr) = HIDE_POINTER(q)
00162 
00163 /* Execute s once for each predecessor q of p in the points-to graph.        */
00164 /* s should be a bracketed statement.  We declare q.                  */
00165 #define FOR_EACH_PRED(q, p, s) \
00166   { \
00167     ptr_t q = GET_OH_BG_PTR(p); \
00168     if (!((word)q & FLAG_MANY)) { \
00169       if (q && !((word)q & 1)) s \
00170              /* !((word)q & 1) checks for a misnterpreted freelist link */ \
00171     } else { \
00172       back_edges *orig_be_ = (back_edges *)((word)q & ~FLAG_MANY); \
00173       back_edges *be_ = orig_be_; \
00174       int total_, local_; \
00175       int n_edges_ = be_ -> n_edges; \
00176       for (total_ = 0, local_ = 0; total_ < n_edges_; ++local_, ++total_) { \
00177          if (local_ == MAX_IN) { \
00178              be_ = be_ -> cont; \
00179              local_ = 0; \
00180          } \
00181          q = be_ -> edges[local_]; s \
00182       } \
00183     } \
00184   }
00185 
00186 /* Ensure that p has a back_edges structure associated with it.       */
00187 static void ensure_struct(ptr_t p)
00188 {
00189   ptr_t old_back_ptr = GET_OH_BG_PTR(p);
00190 
00191   if (!((word)old_back_ptr & FLAG_MANY)) {
00192     back_edges *be = new_back_edges();
00193     be -> flags = 0;
00194     if (0 == old_back_ptr) {
00195       be -> n_edges = 0;
00196     } else {
00197       be -> n_edges = 1;
00198       be -> edges[0] = old_back_ptr;
00199     }
00200     be -> height = HEIGHT_UNKNOWN;
00201     be -> height_gc_no = GC_gc_no - 1;
00202     GC_ASSERT(be >= back_edge_space);
00203     SET_OH_BG_PTR(p, (word)be | FLAG_MANY);
00204   }
00205 }
00206 
00207 /* Add the (forward) edge from p to q to the backward graph.  Both p  */
00208 /* q are pointers to the object base, i.e. pointers to an oh.         */
00209 static void add_edge(ptr_t p,  ptr_t q)
00210 {
00211     ptr_t old_back_ptr = GET_OH_BG_PTR(q);
00212     back_edges * be, *be_cont;
00213     word i;
00214     static unsigned random_number = 13;
00215 #   define GOT_LUCKY_NUMBER (((++random_number) & 0x7f) == 0)
00216       /* A not very random number we use to occasionally allocate a   */
00217       /* back_edges structure even for a single backward edge.  This  */
00218       /* prevents us from repeatedly tracing back through very long   */
00219       /* chains, since we will have some place to store height and    */
00220       /* in_progress flags along the way.                      */
00221 
00222     GC_ASSERT(p == GC_base(p) && q == GC_base(q));
00223     if (!GC_HAS_DEBUG_INFO(q) || !GC_HAS_DEBUG_INFO(p)) {
00224       /* This is really a misinterpreted free list link, since we saw */
00225       /* a pointer to a free list.  Dont overwrite it!               */
00226       return;
00227     }
00228     if (0 == old_back_ptr) {
00229        SET_OH_BG_PTR(q, p);
00230        if (GOT_LUCKY_NUMBER) ensure_struct(q);
00231        return;
00232     }
00233     /* Check whether it was already in the list of predecessors. */
00234       FOR_EACH_PRED(pred, q, { if (p == pred) return; });
00235     ensure_struct(q);
00236     old_back_ptr = GET_OH_BG_PTR(q);
00237     be = (back_edges *)((word)old_back_ptr & ~FLAG_MANY);
00238     for (i = be -> n_edges, be_cont = be; i > MAX_IN;
00239        be_cont = be_cont -> cont, i -= MAX_IN) {}
00240     if (i == MAX_IN) {
00241        be_cont -> cont = new_back_edges();
00242        be_cont = be_cont -> cont;
00243        i = 0;
00244     }
00245     be_cont -> edges[i] = p;
00246     be -> n_edges++;
00247     if (be -> n_edges == 100) {
00248 #       if 0
00249          if (GC_print_stats) {
00250            GC_err_printf0("The following object has in-degree >= 100:\n");
00251            GC_print_heap_obj(q);
00252          }
00253 #      endif
00254     }
00255 }
00256 
00257 typedef void (*per_object_func)(ptr_t p, word n_words, word gc_descr);
00258 
00259 static void per_object_helper(struct hblk *h, word fn)
00260 {
00261   hdr * hhdr = HDR(h);
00262   word sz = hhdr -> hb_sz;
00263   word descr = hhdr -> hb_descr;
00264   per_object_func f = (per_object_func)fn;
00265   int i = 0;
00266 
00267   do {
00268     f((ptr_t)(h -> hb_body + i), sz, descr);
00269     i += sz;
00270   } while (i + sz <= BYTES_TO_WORDS(HBLKSIZE));
00271 }
00272 
00273 void GC_apply_to_each_object(per_object_func f)
00274 {
00275   GC_apply_to_all_blocks(per_object_helper, (word)f);
00276 }
00277 
00278 static void reset_back_edge(ptr_t p, word n_words, word gc_descr)
00279 {
00280   /* Skip any free list links, or dropped blocks */
00281   if (GC_HAS_DEBUG_INFO(p)) {
00282     ptr_t old_back_ptr = GET_OH_BG_PTR(p);
00283     if ((word)old_back_ptr & FLAG_MANY) {
00284       back_edges *be = (back_edges *)((word)old_back_ptr & ~FLAG_MANY);
00285       if (!(be -> flags & RETAIN)) {
00286        deallocate_back_edges(be);
00287         SET_OH_BG_PTR(p, 0); 
00288       } else {
00289         word *currentp;
00290 
00291        GC_ASSERT(GC_is_marked(p));
00292 
00293        /* Back edges may point to objects that will not be retained.  */
00294        /* Delete them for now, but remember the height.        */
00295        /* Some will be added back at next GC.                         */
00296          be -> n_edges = 0;
00297          if (0 != be -> cont) {
00298            deallocate_back_edges(be -> cont);
00299            be -> cont = 0;
00300          }
00301 
00302        GC_ASSERT(GC_is_marked(p));
00303 
00304        /* We only retain things for one GC cycle at a time.           */
00305          be -> flags &= ~RETAIN;
00306       }
00307     } else /* Simple back pointer */ {
00308       /* Clear to avoid dangling pointer. */
00309       SET_OH_BG_PTR(p, 0);
00310     }
00311   }
00312 }
00313 
00314 static void add_back_edges(ptr_t p, word n_words, word gc_descr)
00315 {
00316   word *currentp = (word *)(p + sizeof(oh));
00317 
00318   /* For now, fix up non-length descriptors conservatively.    */
00319     if((gc_descr & GC_DS_TAGS) != GC_DS_LENGTH) {
00320       gc_descr = WORDS_TO_BYTES(n_words);
00321     }
00322   while (currentp < (word *)(p + gc_descr)) {
00323     word current = *currentp++;
00324     FIXUP_POINTER(current);
00325     if (current >= (word)GC_least_plausible_heap_addr && 
00326        current <= (word)GC_greatest_plausible_heap_addr) {
00327        ptr_t target = GC_base((GC_PTR)current);
00328        if (0 != target) {
00329         add_edge(p, target);
00330        }
00331     }
00332   }
00333 }
00334 
00335 /* Rebuild the representation of the backward reachability graph.     */
00336 /* Does not examine mark bits.  Can be called before GC.              */
00337 void GC_build_back_graph(void)
00338 {
00339   GC_apply_to_each_object(add_back_edges);
00340 }
00341 
00342 /* Return an approximation to the length of the longest simple path   */
00343 /* through unreachable objects to p.  We refer to this as the height  */
00344 /* of p.                                                       */
00345 static word backwards_height(ptr_t p)
00346 {
00347   word result;
00348   ptr_t back_ptr = GET_OH_BG_PTR(p);
00349   back_edges *be;
00350 
00351   if (0 == back_ptr) return 1;
00352   if (!((word)back_ptr & FLAG_MANY)) {
00353     if (is_in_progress(p)) return 0;  /* DFS back edge, i.e. we followed  */
00354                                   /* an edge to an object already       */
00355                                   /* on our stack: ignore               */
00356     push_in_progress(p);
00357     result = backwards_height(back_ptr)+1;
00358     pop_in_progress(p);
00359     return result;
00360   }
00361   be = (back_edges *)((word)back_ptr & ~FLAG_MANY);
00362   if (be -> height >= 0 && be -> height_gc_no == GC_gc_no)
00363       return be -> height;
00364   /* Ignore back edges in DFS */
00365     if (be -> height == HEIGHT_IN_PROGRESS) return 0;
00366   result = (be -> height > 0? be -> height : 1);
00367   be -> height = HEIGHT_IN_PROGRESS;
00368   FOR_EACH_PRED(q, p, {
00369     word this_height;
00370     if (GC_is_marked(q) && !(FLAG_MANY & (word)GET_OH_BG_PTR(p))) {
00371       if (GC_print_stats)
00372          GC_printf2("Found bogus pointer from 0x%lx to 0x%lx\n", q, p);
00373        /* Reachable object "points to" unreachable one.        */
00374        /* Could be caused by our lax treatment of GC descriptors.     */
00375       this_height = 1;
00376     } else {
00377         this_height = backwards_height(q);
00378     }
00379     if (this_height >= result) result = this_height + 1;
00380   });
00381   be -> height = result;
00382   be -> height_gc_no = GC_gc_no;
00383   return result;
00384 }
00385 
00386 word GC_max_height;
00387 ptr_t GC_deepest_obj;
00388 
00389 /* Compute the maximum height of every unreachable predecessor p of  a       */
00390 /* reachable object.  Arrange to save the heights of all such objects p      */
00391 /* so that they can be used in calculating the height of objects in the      */
00392 /* next GC.                                                    */
00393 /* Set GC_max_height to be the maximum height we encounter, and       */
00394 /* GC_deepest_obj to be the corresponding object.                     */
00395 static void update_max_height(ptr_t p, word n_words, word gc_descr)
00396 {
00397   if (GC_is_marked(p) && GC_HAS_DEBUG_INFO(p)) {
00398     int i;
00399     word p_height = 0;
00400     ptr_t p_deepest_obj = 0;
00401     ptr_t back_ptr;
00402     back_edges *be = 0;
00403 
00404     /* If we remembered a height last time, use it as a minimum.      */
00405     /* It may have increased due to newly unreachable chains pointing */
00406     /* to p, but it can't have decreased.                      */
00407     back_ptr = GET_OH_BG_PTR(p);
00408     if (0 != back_ptr && ((word)back_ptr & FLAG_MANY)) {
00409       be = (back_edges *)((word)back_ptr & ~FLAG_MANY);
00410       if (be -> height != HEIGHT_UNKNOWN) p_height = be -> height;
00411     }
00412     FOR_EACH_PRED(q, p, {
00413       if (!GC_is_marked(q) && GC_HAS_DEBUG_INFO(q)) {
00414         word q_height;
00415 
00416         q_height = backwards_height(q);
00417        if (q_height > p_height) {
00418          p_height = q_height;
00419          p_deepest_obj = q;
00420        }
00421       }
00422     });
00423     if (p_height > 0) {
00424       /* Remember the height for next time. */
00425        if (be == 0) {
00426          ensure_struct(p);
00427          back_ptr = GET_OH_BG_PTR(p);
00428          be = (back_edges *)((word)back_ptr & ~FLAG_MANY);
00429        }
00430        be -> flags |= RETAIN;
00431        be -> height = p_height;
00432        be -> height_gc_no = GC_gc_no;
00433     }
00434     if (p_height > GC_max_height) {
00435        GC_max_height = p_height;
00436        GC_deepest_obj = p_deepest_obj;
00437     }
00438   }
00439 }
00440 
00441 word GC_max_max_height = 0;
00442 
00443 void GC_traverse_back_graph(void)
00444 {
00445   GC_max_height = 0;
00446   GC_apply_to_each_object(update_max_height);
00447 }
00448 
00449 void GC_print_back_graph_stats(void)
00450 {
00451   GC_printf2("Maximum backwards height of reachable objects at GC %lu is %ld\n",
00452             (unsigned long) GC_gc_no, GC_max_height);
00453   if (GC_max_height > GC_max_max_height) {
00454     GC_max_max_height = GC_max_height;
00455     GC_printf0("The following unreachable object is last in a longest chain "
00456               "of unreachable objects:\n");
00457     GC_print_heap_obj(GC_deepest_obj);
00458   }
00459   if (GC_print_stats) {
00460     GC_printf1("Needed max total of %ld back-edge structs\n",
00461               GC_n_back_edge_structs);
00462   }
00463   GC_apply_to_each_object(reset_back_edge);
00464   GC_deepest_obj = 0;
00465 }
00466 
00467 #endif /* MAKE_BACK_GRAPH */