Synopsis - Cross-Reference
File: /src/Synopsis/gc/backgraph.c1/* 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 47typedef 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 77static back_edges *back_edge_space = 0; 78int GC_n_back_edge_structs = 0; /* Serves as pointer to never used */ 79 /* back_edges space. */ 80static back_edges *avail_back_edges = 0; 81 /* Pointer to free list of deallocated */ 82 /* back_edges structures. */ 83 84static back_edges * new_back_edges(void) 85{ 86 if (0 == back_edge_space) { 87 back_edge_space = (back_edges *) 88 GET_MEM(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. */ 104static 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/* FIXME: This data structure NEEDS IMPROVEMENT. */ 117#define INITIAL_IN_PROGRESS 10000 118static ptr_t * in_progress_space = 0; 119static size_t in_progress_size = 0; 120static size_t n_in_progress = 0; 121 122static void push_in_progress(ptr_t p) 123{ 124 if (n_in_progress >= in_progress_size) 125 if (in_progress_size == 0) { 126 in_progress_size = INITIAL_IN_PROGRESS; 127 in_progress_space = (ptr_t *)GET_MEM(in_progress_size * sizeof(ptr_t)); 128 } else { 129 ptr_t * new_in_progress_space; 130 in_progress_size *= 2; 131 new_in_progress_space = (ptr_t *) 132 GET_MEM(in_progress_size * sizeof(ptr_t)); 133 BCOPY(in_progress_space, new_in_progress_space, 134 n_in_progress * sizeof(ptr_t)); 135 in_progress_space = new_in_progress_space; 136 /* FIXME: This just drops the old space. */ 137 } 138 if (in_progress_space == 0) 139 ABORT("MAKE_BACK_GRAPH: Out of in-progress space: " 140 "Huge linear data structure?"); 141 in_progress_space[n_in_progress++] = p; 142} 143 144static GC_bool is_in_progress(ptr_t p) 145{ 146 int i; 147 for (i = 0; i < n_in_progress; ++i) { 148 if (in_progress_space[i] == p) return TRUE; 149 } 150 return FALSE; 151} 152 153static void pop_in_progress(ptr_t p) 154{ 155 --n_in_progress; 156 GC_ASSERT(in_progress_space[n_in_progress] == p); 157} 158 159#define GET_OH_BG_PTR(p) \ 160 (ptr_t)REVEAL_POINTER(((oh *)(p)) -> oh_bg_ptr) 161#define SET_OH_BG_PTR(p,q) (((oh *)(p)) -> oh_bg_ptr) = HIDE_POINTER(q) 162 163/* Execute s once for each predecessor q of p in the points-to graph. */ 164/* s should be a bracketed statement. We declare q. */ 165#define FOR_EACH_PRED(q, p, s) \ 166 { \ 167 ptr_t q = GET_OH_BG_PTR(p); \ 168 if (!((word)q & FLAG_MANY)) { \ 169 if (q && !((word)q & 1)) s \ 170 /* !((word)q & 1) checks for a misnterpreted freelist link */ \ 171 } else { \ 172 back_edges *orig_be_ = (back_edges *)((word)q & ~FLAG_MANY); \ 173 back_edges *be_ = orig_be_; \ 174 int total_, local_; \ 175 int n_edges_ = be_ -> n_edges; \ 176 for (total_ = 0, local_ = 0; total_ < n_edges_; ++local_, ++total_) { \ 177 if (local_ == MAX_IN) { \ 178 be_ = be_ -> cont; \ 179 local_ = 0; \ 180 } \ 181 q = be_ -> edges[local_]; s \ 182 } \ 183 } \ 184 } 185 186/* Ensure that p has a back_edges structure associated with it. */ 187static void ensure_struct(ptr_t p) 188{ 189 ptr_t old_back_ptr = GET_OH_BG_PTR(p); 190 191 if (!((word)old_back_ptr & FLAG_MANY)) { 192 back_edges *be = new_back_edges(); 193 be -> flags = 0; 194 if (0 == old_back_ptr) { 195 be -> n_edges = 0; 196 } else { 197 be -> n_edges = 1; 198 be -> edges[0] = old_back_ptr; 199 } 200 be -> height = HEIGHT_UNKNOWN; 201 be -> height_gc_no = GC_gc_no - 1; 202 GC_ASSERT(be >= back_edge_space); 203 SET_OH_BG_PTR(p, (word)be | FLAG_MANY); 204 } 205} 206 207/* Add the (forward) edge from p to q to the backward graph. Both p */ 208/* q are pointers to the object base, i.e. pointers to an oh. */ 209static void add_edge(ptr_t p, ptr_t q) 210{ 211 ptr_t old_back_ptr = GET_OH_BG_PTR(q); 212 back_edges * be, *be_cont; 213 word i; 214 static unsigned random_number = 13; 215# define GOT_LUCKY_NUMBER (((++random_number) & 0x7f) == 0) 216 /* A not very random number we use to occasionally allocate a */ 217 /* back_edges structure even for a single backward edge. This */ 218 /* prevents us from repeatedly tracing back through very long */ 219 /* chains, since we will have some place to store height and */ 220 /* in_progress flags along the way. */ 221 222 GC_ASSERT(p == GC_base(p) && q == GC_base(q)); 223 if (!GC_HAS_DEBUG_INFO(q) || !GC_HAS_DEBUG_INFO(p)) { 224 /* This is really a misinterpreted free list link, since we saw */ 225 /* a pointer to a free list. Dont overwrite it! */ 226 return; 227 } 228 if (0 == old_back_ptr) { 229 SET_OH_BG_PTR(q, p); 230 if (GOT_LUCKY_NUMBER) ensure_struct(q); 231 return; 232 } 233 /* Check whether it was already in the list of predecessors. */ 234 FOR_EACH_PRED(pred, q, { if (p == pred) return; }); 235 ensure_struct(q); 236 old_back_ptr = GET_OH_BG_PTR(q); 237 be = (back_edges *)((word)old_back_ptr & ~FLAG_MANY); 238 for (i = be -> n_edges, be_cont = be; i > MAX_IN; 239 be_cont = be_cont -> cont, i -= MAX_IN) {} 240 if (i == MAX_IN) { 241 be_cont -> cont = new_back_edges(); 242 be_cont = be_cont -> cont; 243 i = 0; 244 } 245 be_cont -> edges[i] = p; 246 be -> n_edges++; 247 if (be -> n_edges == 100) { 248# if 0 249 if (GC_print_stats) { 250 GC_err_printf("The following object has in-degree >= 100:\n"); 251 GC_print_heap_obj(q); 252 } 253# endif 254 } 255} 256 257typedef void (*per_object_func)(ptr_t p, size_t n_bytes, word gc_descr); 258 259static void per_object_helper(struct hblk *h, word fn) 260{ 261 hdr * hhdr = HDR(h); 262 size_t sz = hhdr -> hb_sz; 263 word descr = hhdr -> hb_descr; 264 per_object_func f = (per_object_func)fn; 265 int i = 0; 266 267 do { 268 f((ptr_t)(h -> hb_body + i), sz, descr); 269 i += sz; 270 } while (i + sz <= BYTES_TO_WORDS(HBLKSIZE)); 271} 272 273void GC_apply_to_each_object(per_object_func f) 274{ 275 GC_apply_to_all_blocks(per_object_helper, (word)f); 276} 277 278static void reset_back_edge(ptr_t p, size_t n_bytes, word gc_descr) 279{ 280 /* Skip any free list links, or dropped blocks */ 281 if (GC_HAS_DEBUG_INFO(p)) { 282 ptr_t old_back_ptr = GET_OH_BG_PTR(p); 283 if ((word)old_back_ptr & FLAG_MANY) { 284 back_edges *be = (back_edges *)((word)old_back_ptr & ~FLAG_MANY); 285 if (!(be -> flags & RETAIN)) { 286 deallocate_back_edges(be); 287 SET_OH_BG_PTR(p, 0); 288 } else { 289 word *currentp; 290 291 GC_ASSERT(GC_is_marked(p)); 292 293 /* Back edges may point to objects that will not be retained. */ 294 /* Delete them for now, but remember the height. */ 295 /* Some will be added back at next GC. */ 296 be -> n_edges = 0; 297 if (0 != be -> cont) { 298 deallocate_back_edges(be -> cont); 299 be -> cont = 0; 300 } 301 302 GC_ASSERT(GC_is_marked(p)); 303 304 /* We only retain things for one GC cycle at a time. */ 305 be -> flags &= ~RETAIN; 306 } 307 } else /* Simple back pointer */ { 308 /* Clear to avoid dangling pointer. */ 309 SET_OH_BG_PTR(p, 0); 310 } 311 } 312} 313 314static void add_back_edges(ptr_t p, size_t n_bytes, word gc_descr) 315{ 316 word *currentp = (word *)(p + sizeof(oh)); 317 318 /* For now, fix up non-length descriptors conservatively. */ 319 if((gc_descr & GC_DS_TAGS) != GC_DS_LENGTH) { 320 gc_descr = n_bytes; 321 } 322 while (currentp < (word *)(p + gc_descr)) { 323 word current = *currentp++; 324 FIXUP_POINTER(current); 325 if (current >= (word)GC_least_plausible_heap_addr && 326 current <= (word)GC_greatest_plausible_heap_addr) { 327 ptr_t target = GC_base((void *)current); 328 if (0 != target) { 329 add_edge(p, target); 330 } 331 } 332 } 333} 334 335/* Rebuild the representation of the backward reachability graph. */ 336/* Does not examine mark bits. Can be called before GC. */ 337void GC_build_back_graph(void) 338{ 339 GC_apply_to_each_object(add_back_edges); 340} 341 342/* Return an approximation to the length of the longest simple path */ 343/* through unreachable objects to p. We refer to this as the height */ 344/* of p. */ 345static word backwards_height(ptr_t p) 346{ 347 word result; 348 ptr_t back_ptr = GET_OH_BG_PTR(p); 349 back_edges *be; 350 351 if (0 == back_ptr) return 1; 352 if (!((word)back_ptr & FLAG_MANY)) { 353 if (is_in_progress(p)) return 0; /* DFS back edge, i.e. we followed */ 354 /* an edge to an object already */ 355 /* on our stack: ignore */ 356 push_in_progress(p); 357 result = backwards_height(back_ptr)+1; 358 pop_in_progress(p); 359 return result; 360 } 361 be = (back_edges *)((word)back_ptr & ~FLAG_MANY); 362 if (be -> height >= 0 && be -> height_gc_no == GC_gc_no) 363 return be -> height; 364 /* Ignore back edges in DFS */ 365 if (be -> height == HEIGHT_IN_PROGRESS) return 0; 366 result = (be -> height > 0? be -> height : 1); 367 be -> height = HEIGHT_IN_PROGRESS; 368 FOR_EACH_PRED(q, p, { 369 word this_height; 370 if (GC_is_marked(q) && !(FLAG_MANY & (word)GET_OH_BG_PTR(p))) { 371 if (GC_print_stats) 372 GC_log_printf("Found bogus pointer from 0x%lx to 0x%lx\n", q, p); 373 /* Reachable object "points to" unreachable one. */ 374 /* Could be caused by our lax treatment of GC descriptors. */ 375 this_height = 1; 376 } else { 377 this_height = backwards_height(q); 378 } 379 if (this_height >= result) result = this_height + 1; 380 }); 381 be -> height = result; 382 be -> height_gc_no = GC_gc_no; 383 return result; 384} 385 386word GC_max_height; 387ptr_t GC_deepest_obj; 388 389/* Compute the maximum height of every unreachable predecessor p of a */ 390/* reachable object. Arrange to save the heights of all such objects p */ 391/* so that they can be used in calculating the height of objects in the */ 392/* next GC. */ 393/* Set GC_max_height to be the maximum height we encounter, and */ 394/* GC_deepest_obj to be the corresponding object. */ 395static void update_max_height(ptr_t p, size_t n_bytes, word gc_descr) 396{ 397 if (GC_is_marked(p) && GC_HAS_DEBUG_INFO(p)) { 398 int i; 399 word p_height = 0; 400 ptr_t p_deepest_obj = 0; 401 ptr_t back_ptr; 402 back_edges *be = 0; 403 404 /* If we remembered a height last time, use it as a minimum. */ 405 /* It may have increased due to newly unreachable chains pointing */ 406 /* to p, but it can't have decreased. */ 407 back_ptr = GET_OH_BG_PTR(p); 408 if (0 != back_ptr && ((word)back_ptr & FLAG_MANY)) { 409 be = (back_edges *)((word)back_ptr & ~FLAG_MANY); 410 if (be -> height != HEIGHT_UNKNOWN) p_height = be -> height; 411 } 412 FOR_EACH_PRED(q, p, { 413 if (!GC_is_marked(q) && GC_HAS_DEBUG_INFO(q)) { 414 word q_height; 415 416 q_height = backwards_height(q); 417 if (q_height > p_height) { 418 p_height = q_height; 419 p_deepest_obj = q; 420 } 421 } 422 }); 423 if (p_height > 0) { 424 /* Remember the height for next time. */ 425 if (be == 0) { 426 ensure_struct(p); 427 back_ptr = GET_OH_BG_PTR(p); 428 be = (back_edges *)((word)back_ptr & ~FLAG_MANY); 429 } 430 be -> flags |= RETAIN; 431 be -> height = p_height; 432 be -> height_gc_no = GC_gc_no; 433 } 434 if (p_height > GC_max_height) { 435 GC_max_height = p_height; 436 GC_deepest_obj = p_deepest_obj; 437 } 438 } 439} 440 441word GC_max_max_height = 0; 442 443void GC_traverse_back_graph(void) 444{ 445 GC_max_height = 0; 446 GC_apply_to_each_object(update_max_height); 447 if (0 != GC_deepest_obj) 448 GC_set_mark_bit(GC_deepest_obj); /* Keep it until we can print it. */ 449} 450 451void GC_print_back_graph_stats(void) 452{ 453 GC_printf("Maximum backwards height of reachable objects at GC %lu is %ld\n", 454 (unsigned long) GC_gc_no, (unsigned long)GC_max_height); 455 if (GC_max_height > GC_max_max_height) { 456 GC_max_max_height = GC_max_height; 457 GC_printf("The following unreachable object is last in a longest chain " 458 "of unreachable objects:\n"); 459 GC_print_heap_obj(GC_deepest_obj); 460 } 461 if (GC_print_stats) { 462 GC_log_printf("Needed max total of %ld back-edge structs\n", 463 GC_n_back_edge_structs); 464 } 465 GC_apply_to_each_object(reset_back_edge); 466 GC_deepest_obj = 0; 467} 468 469#endif /* MAKE_BACK_GRAPH */