diff options
Diffstat (limited to 'gc/backgraph.c')
| -rw-r--r-- | gc/backgraph.c | 447 |
1 files changed, 447 insertions, 0 deletions
diff --git a/gc/backgraph.c b/gc/backgraph.c new file mode 100644 index 0000000..01ab738 --- /dev/null +++ b/gc/backgraph.c @@ -0,0 +1,447 @@ +/* + * 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 */ |