Annotation of OpenXM_contrib2/asir2000/gc/backgraph.c, Revision 1.1
1.1 ! noro 1: /*
! 2: * Copyright (c) 2001 by Hewlett-Packard Company. All rights reserved.
! 3: *
! 4: * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
! 5: * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
! 6: *
! 7: * Permission is hereby granted to use or copy this program
! 8: * for any purpose, provided the above notices are retained on all copies.
! 9: * Permission to modify the code and to distribute modified code is granted,
! 10: * provided the above notices are retained, and a notice that the code was
! 11: * modified is included with the above copyright notice.
! 12: *
! 13: */
! 14:
! 15: /*
! 16: * This implements a full, though not well-tuned, representation of the
! 17: * backwards points-to graph. This is used to test for non-GC-robust
! 18: * data structures; the code is not used during normal garbage collection.
! 19: *
! 20: * One restriction is that we drop all back-edges from nodes with very
! 21: * high in-degree, and simply add them add them to a list of such
! 22: * nodes. They are then treated as permanent roots. Id this by itself
! 23: * doesn't introduce a space leak, then such nodes can't contribute to
! 24: * a growing space leak.
! 25: */
! 26:
! 27: #ifdef MAKE_BACK_GRAPH
! 28:
! 29: #define MAX_IN 10 /* Maximum in-degree we handle directly */
! 30:
! 31: #include "private/dbg_mlc.h"
! 32: #include <unistd.h>
! 33:
! 34: #if !defined(DBG_HDRS_ALL) || (ALIGNMENT != CPP_WORDSZ/8) || !defined(UNIX_LIKE)
! 35: # error Configuration doesnt support MAKE_BACK_GRAPH
! 36: #endif
! 37:
! 38: /* We store single back pointers directly in the object's oh_bg_ptr field. */
! 39: /* If there is more than one ptr to an object, we store q | FLAG_MANY, */
! 40: /* where q is a pointer to a back_edges object. */
! 41: /* Every once in a while we use a back_edges object even for a single */
! 42: /* pointer, since we need the other fields in the back_edges structure to */
! 43: /* be present in some fraction of the objects. Otherwise we get serious */
! 44: /* performance issues. */
! 45: #define FLAG_MANY 2
! 46:
! 47: typedef struct back_edges_struct {
! 48: word n_edges; /* Number of edges, including those in continuation */
! 49: /* structures. */
! 50: unsigned short flags;
! 51: # define RETAIN 1 /* Directly points to a reachable object; */
! 52: /* retain for next GC. */
! 53: unsigned short height_gc_no;
! 54: /* If height > 0, then the GC_gc_no value when it */
! 55: /* was computed. If it was computed this cycle, then */
! 56: /* it is current. If it was computed during the */
! 57: /* last cycle, then it represents the old height, */
! 58: /* which is only saved for live objects referenced by */
! 59: /* dead ones. This may grow due to refs from newly */
! 60: /* dead objects. */
! 61: signed_word height;
! 62: /* Longest path through unreachable nodes to this node */
! 63: /* that we found using depth first search. */
! 64:
! 65: # define HEIGHT_UNKNOWN ((signed_word)(-2))
! 66: # define HEIGHT_IN_PROGRESS ((signed_word)(-1))
! 67: ptr_t edges[MAX_IN];
! 68: struct back_edges_struct *cont;
! 69: /* Pointer to continuation structure; we use only the */
! 70: /* edges field in the continuation. */
! 71: /* also used as free list link. */
! 72: } back_edges;
! 73:
! 74: /* Allocate a new back edge structure. Should be more sophisticated */
! 75: /* if this were production code. */
! 76: #define MAX_BACK_EDGE_STRUCTS 100000
! 77: static back_edges *back_edge_space = 0;
! 78: int GC_n_back_edge_structs = 0; /* Serves as pointer to never used */
! 79: /* back_edges space. */
! 80: static back_edges *avail_back_edges = 0;
! 81: /* Pointer to free list of deallocated */
! 82: /* back_edges structures. */
! 83:
! 84: static back_edges * new_back_edges(void)
! 85: {
! 86: if (0 == back_edge_space) {
! 87: back_edge_space = (back_edges *)
! 88: sbrk(MAX_BACK_EDGE_STRUCTS*sizeof(back_edges));
! 89: }
! 90: if (0 != avail_back_edges) {
! 91: back_edges * result = avail_back_edges;
! 92: avail_back_edges = result -> cont;
! 93: result -> cont = 0;
! 94: return result;
! 95: }
! 96: if (GC_n_back_edge_structs >= MAX_BACK_EDGE_STRUCTS - 1) {
! 97: ABORT("needed too much space for back edges: adjust "
! 98: "MAX_BACK_EDGE_STRUCTS");
! 99: }
! 100: return back_edge_space + (GC_n_back_edge_structs++);
! 101: }
! 102:
! 103: /* Deallocate p and its associated continuation structures. */
! 104: static void deallocate_back_edges(back_edges *p)
! 105: {
! 106: back_edges *last = p;
! 107:
! 108: while (0 != last -> cont) last = last -> cont;
! 109: last -> cont = avail_back_edges;
! 110: avail_back_edges = p;
! 111: }
! 112:
! 113: /* Table of objects that are currently on the depth-first search */
! 114: /* stack. Only objects with in-degree one are in this table. */
! 115: /* Other objects are identified using HEIGHT_IN_PROGRESS. */
! 116: /* This data structure NEEDS IMPROVEMENT. */
! 117: #define MAX_IN_PROGRESS 10000
! 118: static ptr_t * in_progress_space = 0;
! 119: static int n_in_progress = 0;
! 120:
! 121: static void push_in_progress(ptr_t p)
! 122: {
! 123: if (in_progress_space == 0)
! 124: in_progress_space = sbrk(MAX_IN_PROGRESS * sizeof(ptr_t));
! 125: if (n_in_progress == MAX_IN_PROGRESS)
! 126: ABORT("Exceeded MAX_IN_PROGRESS");
! 127: in_progress_space[n_in_progress++] = p;
! 128: }
! 129:
! 130: static GC_bool is_in_progress(ptr_t p)
! 131: {
! 132: int i;
! 133: for (i = 0; i < n_in_progress; ++i) {
! 134: if (in_progress_space[i] == p) return TRUE;
! 135: }
! 136: return FALSE;
! 137: }
! 138:
! 139: static void pop_in_progress(ptr_t p)
! 140: {
! 141: --n_in_progress;
! 142: GC_ASSERT(in_progress_space[n_in_progress] == p);
! 143: }
! 144:
! 145: #define GET_OH_BG_PTR(p) \
! 146: (ptr_t)REVEAL_POINTER(((oh *)(p)) -> oh_bg_ptr)
! 147: #define SET_OH_BG_PTR(p,q) (((oh *)(p)) -> oh_bg_ptr) = HIDE_POINTER(q)
! 148:
! 149: /* Execute s once for each predecessor q of p in the points-to graph. */
! 150: /* s should be a bracketed statement. We declare q. */
! 151: #define FOR_EACH_PRED(q, p, s) \
! 152: { \
! 153: ptr_t q = GET_OH_BG_PTR(p); \
! 154: if (!((word)q & FLAG_MANY)) { \
! 155: if (q && !((word)q & 1)) s \
! 156: /* !((word)q & 1) checks for a misnterpreted freelist link */ \
! 157: } else { \
! 158: back_edges *orig_be_ = (back_edges *)((word)q & ~FLAG_MANY); \
! 159: back_edges *be_ = orig_be_; \
! 160: int total_, local_; \
! 161: int n_edges_ = be_ -> n_edges; \
! 162: for (total_ = 0, local_ = 0; total_ < n_edges_; ++local_, ++total_) { \
! 163: if (local_ == MAX_IN) { \
! 164: be_ = be_ -> cont; \
! 165: local_ = 0; \
! 166: } \
! 167: q = be_ -> edges[local_]; s \
! 168: } \
! 169: } \
! 170: }
! 171:
! 172: /* Ensure that p has a back_edges structure associated with it. */
! 173: static void ensure_struct(ptr_t p)
! 174: {
! 175: ptr_t old_back_ptr = GET_OH_BG_PTR(p);
! 176:
! 177: if (!((word)old_back_ptr & FLAG_MANY)) {
! 178: back_edges *be = new_back_edges();
! 179: be -> flags = 0;
! 180: if (0 == old_back_ptr) {
! 181: be -> n_edges = 0;
! 182: } else {
! 183: be -> n_edges = 1;
! 184: be -> edges[0] = old_back_ptr;
! 185: }
! 186: be -> height = HEIGHT_UNKNOWN;
! 187: be -> height_gc_no = GC_gc_no - 1;
! 188: GC_ASSERT(be >= back_edge_space);
! 189: SET_OH_BG_PTR(p, (word)be | FLAG_MANY);
! 190: }
! 191: }
! 192:
! 193: /* Add the (forward) edge from p to q to the backward graph. Both p */
! 194: /* q are pointers to the object base, i.e. pointers to an oh. */
! 195: static void add_edge(ptr_t p, ptr_t q)
! 196: {
! 197: ptr_t old_back_ptr = GET_OH_BG_PTR(q);
! 198: back_edges * be, *be_cont;
! 199: word i;
! 200: static unsigned random_number = 13;
! 201: # define GOT_LUCKY_NUMBER (((++random_number) & 0x7f) == 0)
! 202: /* A not very random number we use to occasionally allocate a */
! 203: /* back_edges structure even for a single backward edge. This */
! 204: /* prevents us from repeatedly tracing back through very long */
! 205: /* chains, since we will have some place to store height and */
! 206: /* in_progress flags along the way. */
! 207:
! 208: GC_ASSERT(p == GC_base(p) && q == GC_base(q));
! 209: if (!GC_HAS_DEBUG_INFO(q) || !GC_HAS_DEBUG_INFO(p)) {
! 210: /* This is really a misinterpreted free list link, since we saw */
! 211: /* a pointer to a free list. Dont overwrite it! */
! 212: return;
! 213: }
! 214: if (0 == old_back_ptr) {
! 215: SET_OH_BG_PTR(q, p);
! 216: if (GOT_LUCKY_NUMBER) ensure_struct(q);
! 217: return;
! 218: }
! 219: /* Check whether it was already in the list of predecessors. */
! 220: FOR_EACH_PRED(pred, q, { if (p == pred) return; });
! 221: ensure_struct(q);
! 222: old_back_ptr = GET_OH_BG_PTR(q);
! 223: be = (back_edges *)((word)old_back_ptr & ~FLAG_MANY);
! 224: for (i = be -> n_edges, be_cont = be; i > MAX_IN;
! 225: be_cont = be_cont -> cont, i -= MAX_IN) {}
! 226: if (i == MAX_IN) {
! 227: be_cont -> cont = new_back_edges();
! 228: be_cont = be_cont -> cont;
! 229: i = 0;
! 230: }
! 231: be_cont -> edges[i] = p;
! 232: be -> n_edges++;
! 233: if (be -> n_edges == 100) {
! 234: # if 0
! 235: if (GC_print_stats) {
! 236: GC_err_printf0("The following object has in-degree >= 100:\n");
! 237: GC_print_heap_obj(q);
! 238: }
! 239: # endif
! 240: }
! 241: }
! 242:
! 243: typedef void (*per_object_func)(ptr_t p, word n_words, word gc_descr);
! 244:
! 245: static void per_object_helper(struct hblk *h, word fn)
! 246: {
! 247: hdr * hhdr = HDR(h);
! 248: word sz = hhdr -> hb_sz;
! 249: word descr = hhdr -> hb_descr;
! 250: per_object_func f = (per_object_func)fn;
! 251: int i = 0;
! 252:
! 253: do {
! 254: f((ptr_t)(h -> hb_body + i), sz, descr);
! 255: i += sz;
! 256: } while (i + sz <= BYTES_TO_WORDS(HBLKSIZE));
! 257: }
! 258:
! 259: void GC_apply_to_each_object(per_object_func f)
! 260: {
! 261: GC_apply_to_all_blocks(per_object_helper, (word)f);
! 262: }
! 263:
! 264: static void reset_back_edge(ptr_t p, word n_words, word gc_descr)
! 265: {
! 266: /* Skip any free list links, or dropped blocks */
! 267: if (GC_HAS_DEBUG_INFO(p)) {
! 268: ptr_t old_back_ptr = GET_OH_BG_PTR(p);
! 269: if ((word)old_back_ptr & FLAG_MANY) {
! 270: back_edges *be = (back_edges *)((word)old_back_ptr & ~FLAG_MANY);
! 271: if (!(be -> flags & RETAIN)) {
! 272: deallocate_back_edges(be);
! 273: SET_OH_BG_PTR(p, 0);
! 274: } else {
! 275: word *currentp;
! 276:
! 277: GC_ASSERT(GC_is_marked(p));
! 278:
! 279: /* Back edges may point to objects that will not be retained. */
! 280: /* Delete them for now, but remember the height. */
! 281: /* Some will be added back at next GC. */
! 282: be -> n_edges = 0;
! 283: if (0 != be -> cont) {
! 284: deallocate_back_edges(be -> cont);
! 285: be -> cont = 0;
! 286: }
! 287:
! 288: GC_ASSERT(GC_is_marked(p));
! 289:
! 290: /* We only retain things for one GC cycle at a time. */
! 291: be -> flags &= ~RETAIN;
! 292: }
! 293: } else /* Simple back pointer */ {
! 294: /* Clear to avoid dangling pointer. */
! 295: SET_OH_BG_PTR(p, 0);
! 296: }
! 297: }
! 298: }
! 299:
! 300: static void add_back_edges(ptr_t p, word n_words, word gc_descr)
! 301: {
! 302: word *currentp = (word *)(p + sizeof(oh));
! 303:
! 304: /* For now, fix up non-length descriptors conservatively. */
! 305: if((gc_descr & GC_DS_TAGS) != GC_DS_LENGTH) {
! 306: gc_descr = WORDS_TO_BYTES(n_words);
! 307: }
! 308: while (currentp < (word *)(p + gc_descr)) {
! 309: word current = *currentp++;
! 310: if (current >= (word)GC_least_plausible_heap_addr &&
! 311: current <= (word)GC_greatest_plausible_heap_addr) {
! 312: ptr_t target = GC_base((GC_PTR)current);
! 313: if (0 != target) {
! 314: add_edge(p, target);
! 315: }
! 316: }
! 317: }
! 318: }
! 319:
! 320: /* Rebuild the reprentation of the backward reachability graph. */
! 321: /* Does not examine mark bits. Can be called before GC. */
! 322: void GC_build_back_graph(void)
! 323: {
! 324: GC_apply_to_each_object(add_back_edges);
! 325: }
! 326:
! 327: /* Return an approximation to the length of the longest simple path */
! 328: /* through unreachable objects to p. We refer to this as the height */
! 329: /* of p. */
! 330: static word backwards_height(ptr_t p)
! 331: {
! 332: word result;
! 333: ptr_t back_ptr = GET_OH_BG_PTR(p);
! 334: back_edges *be;
! 335:
! 336: if (0 == back_ptr) return 1;
! 337: if (!((word)back_ptr & FLAG_MANY)) {
! 338: if (is_in_progress(p)) return 0; /* DFS back edge, i.e. we followed */
! 339: /* an edge to an object already */
! 340: /* on our stack: ignore */
! 341: push_in_progress(p);
! 342: result = backwards_height(back_ptr)+1;
! 343: pop_in_progress(p);
! 344: return result;
! 345: }
! 346: be = (back_edges *)((word)back_ptr & ~FLAG_MANY);
! 347: if (be -> height >= 0 && be -> height_gc_no == GC_gc_no)
! 348: return be -> height;
! 349: /* Ignore back edges in DFS */
! 350: if (be -> height == HEIGHT_IN_PROGRESS) return 0;
! 351: result = (be -> height > 0? be -> height : 1);
! 352: be -> height = HEIGHT_IN_PROGRESS;
! 353: FOR_EACH_PRED(q, p, {
! 354: word this_height;
! 355: if (GC_is_marked(q) && !(FLAG_MANY & (word)GET_OH_BG_PTR(p))) {
! 356: if (GC_print_stats)
! 357: GC_printf2("Found bogus pointer from 0x%lx to 0x%lx\n", q, p);
! 358: /* Reachable object "points to" unreachable one. */
! 359: /* Could be caused by our lax treatment of GC descriptors. */
! 360: this_height = 1;
! 361: } else {
! 362: this_height = backwards_height(q);
! 363: }
! 364: if (this_height >= result) result = this_height + 1;
! 365: });
! 366: be -> height = result;
! 367: be -> height_gc_no = GC_gc_no;
! 368: return result;
! 369: }
! 370:
! 371: word GC_max_height;
! 372: ptr_t GC_deepest_obj;
! 373:
! 374: /* Compute the maximum height of every unreachable predecessor p of a */
! 375: /* reachable object. Arrange to save the heights of all such objects p */
! 376: /* so that they can be used in calculating the height of objects in the */
! 377: /* next GC. */
! 378: /* Set GC_max_height to be the maximum height we encounter, and */
! 379: /* GC_deepest_obj to be the corresponding object. */
! 380: static void update_max_height(ptr_t p, word n_words, word gc_descr)
! 381: {
! 382: if (GC_is_marked(p) && GC_HAS_DEBUG_INFO(p)) {
! 383: int i;
! 384: word p_height = 0;
! 385: ptr_t p_deepest_obj = 0;
! 386: ptr_t back_ptr;
! 387: back_edges *be = 0;
! 388:
! 389: /* If we remembered a height last time, use it as a minimum. */
! 390: /* It may have increased due to newly unreachable chains pointing */
! 391: /* to p, but it can't have decreased. */
! 392: back_ptr = GET_OH_BG_PTR(p);
! 393: if (0 != back_ptr && ((word)back_ptr & FLAG_MANY)) {
! 394: be = (back_edges *)((word)back_ptr & ~FLAG_MANY);
! 395: if (be -> height != HEIGHT_UNKNOWN) p_height = be -> height;
! 396: }
! 397: FOR_EACH_PRED(q, p, {
! 398: if (!GC_is_marked(q) && GC_HAS_DEBUG_INFO(q)) {
! 399: word q_height;
! 400:
! 401: q_height = backwards_height(q);
! 402: if (q_height > p_height) {
! 403: p_height = q_height;
! 404: p_deepest_obj = q;
! 405: }
! 406: }
! 407: });
! 408: if (p_height > 0) {
! 409: /* Remember the height for next time. */
! 410: if (be == 0) {
! 411: ensure_struct(p);
! 412: back_ptr = GET_OH_BG_PTR(p);
! 413: be = (back_edges *)((word)back_ptr & ~FLAG_MANY);
! 414: }
! 415: be -> flags |= RETAIN;
! 416: be -> height = p_height;
! 417: be -> height_gc_no = GC_gc_no;
! 418: }
! 419: if (p_height > GC_max_height) {
! 420: GC_max_height = p_height;
! 421: GC_deepest_obj = p_deepest_obj;
! 422: }
! 423: }
! 424: }
! 425:
! 426: void GC_traverse_back_graph(void)
! 427: {
! 428: static word max_max_height = 0;
! 429: GC_max_height = 0;
! 430: GC_apply_to_each_object(update_max_height);
! 431: GC_printf2("Maximum backwards height of reachable objects at GC %lu is %ld\n",
! 432: (unsigned long) GC_gc_no, GC_max_height);
! 433: if (GC_max_height > max_max_height) {
! 434: max_max_height = GC_max_height;
! 435: GC_printf0("The following unreachable object is last in a longest chain "
! 436: "of unreachable objects:\n");
! 437: GC_print_heap_obj(GC_deepest_obj);
! 438: }
! 439: if (GC_print_stats) {
! 440: GC_printf1("Needed max total of %ld back-edge structs\n",
! 441: GC_n_back_edge_structs);
! 442: }
! 443: GC_apply_to_each_object(reset_back_edge);
! 444: GC_deepest_obj = 0;
! 445: }
! 446:
! 447: #endif /* MAKE_BACK_GRAPH */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to backgraph.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / gc