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 #include "private/dbg_mlc.h"
15 16 /*
17 * This implements a full, though not well-tuned, representation of the
18 * backwards points-to graph. This is used to test for non-GC-robust
19 * data structures; the code is not used during normal garbage collection.
20 *
21 * One restriction is that we drop all back-edges from nodes with very
22 * high in-degree, and simply add them add them to a list of such
23 * nodes. They are then treated as permanent roots. If this by itself
24 * does not introduce a space leak, then such nodes cannot contribute to
25 * a growing space leak.
26 */
27 28 #ifdef MAKE_BACK_GRAPH
29 30 /* The maximum in-degree we handle directly. */
31 # define MAX_IN 10
32 33 # if (!defined(DBG_HDRS_ALL) \
34 || (ALIGNMENT != CPP_PTRSZ / 8) /* `|| !defined(UNIX_LIKE)` */) \
35 && !defined(CPPCHECK)
36 # error The configuration does not support MAKE_BACK_GRAPH
37 # endif
38 39 /*
40 * We store single back pointers directly in the object's `oh_bg_ptr` field.
41 * If there is more than one pointer to an object, we store `q` or'ed with
42 * `FLAG_MANY`, where `q` is a pointer to a `back_edges` object.
43 * Every once in a while we use a `back_edges` object even for a single
44 * pointer, since we need the other fields in the `back_edges` structure to
45 * be present in some fraction of the objects. Otherwise we get serious
46 * performance issues.
47 */
48 # define FLAG_MANY 2
49 50 typedef struct back_edges_struct {
51 /* Number of edges, including those in continuation structures. */
52 word n_edges;
53 54 unsigned short flags;
55 56 /* Directly points to a reachable object; retain for the next collection. */
57 # define RETAIN 1
58 59 /*
60 * If `height` is greater than zero, then keeps the `GC_gc_no` value
61 * when it was computed. If it was computed this cycle, then it is
62 * current. If it was computed during the last cycle, then it belongs
63 * to the old height, which is only saved for live objects referenced by
64 * dead ones. This may grow due to references from newly dead objects.
65 */
66 unsigned short height_gc_no;
67 68 /*
69 * Longest path through unreachable nodes to this node that we found
70 * using depth first search.
71 */
72 GC_signed_word height;
73 # define HEIGHT_UNKNOWN (-2)
74 # define HEIGHT_IN_PROGRESS (-1)
75 76 ptr_t edges[MAX_IN];
77 78 /*
79 * Pointer to continuation structure; we use only the edges field in
80 * the continuation. Also used as a free-list link.
81 */
82 struct back_edges_struct *cont;
83 } back_edges;
84 85 # define MAX_BACK_EDGE_STRUCTS 100000
86 static back_edges *back_edge_space = NULL;
87 88 /* Points to never-used `back_edges` space. */
89 STATIC int GC_n_back_edge_structs = 0;
90 91 /* Pointer to free list of deallocated `back_edges` structures. */
92 static back_edges *avail_back_edges = NULL;
93 94 /*
95 * Allocate a new back edge structure. Should be more sophisticated
96 * if this were production code.
97 */
98 static back_edges *
99 new_back_edges(void)
100 {
101 GC_ASSERT(I_HOLD_LOCK());
102 if (0 == back_edge_space) {
103 size_t bytes_to_get
104 = ROUNDUP_PAGESIZE_IF_MMAP(MAX_BACK_EDGE_STRUCTS * sizeof(back_edges));
105 106 GC_ASSERT(GC_page_size != 0);
107 back_edge_space = (back_edges *)GC_os_get_mem(bytes_to_get);
108 if (NULL == back_edge_space)
109 ABORT("Insufficient memory for back edges");
110 }
111 if (avail_back_edges != 0) {
112 back_edges *result = avail_back_edges;
113 avail_back_edges = result->cont;
114 result->cont = 0;
115 return result;
116 }
117 if (GC_n_back_edge_structs >= MAX_BACK_EDGE_STRUCTS - 1) {
118 ABORT("Needed too much space for back edges: adjust "
119 "MAX_BACK_EDGE_STRUCTS");
120 }
121 return back_edge_space + (GC_n_back_edge_structs++);
122 }
123 124 /* Deallocate `p` and its associated continuation structures. */
125 static void
126 deallocate_back_edges(back_edges *p)
127 {
128 back_edges *last;
129 130 for (last = p; last->cont != NULL;)
131 last = last->cont;
132 133 last->cont = avail_back_edges;
134 avail_back_edges = p;
135 }
136 137 /*
138 * Table of objects that are currently on the depth-first search stack.
139 * Only objects with in-degree one are in this table. Other objects are
140 * identified using `HEIGHT_IN_PROGRESS`.
141 */
142 /* FIXME: This data structure needs improvement. */
143 static ptr_t *in_progress_space = 0;
144 # define INITIAL_IN_PROGRESS 10000
145 static size_t in_progress_size = 0;
146 static size_t n_in_progress = 0;
147 148 static void
149 push_in_progress(ptr_t p)
150 {
151 GC_ASSERT(I_HOLD_LOCK());
152 if (n_in_progress >= in_progress_size) {
153 ptr_t *new_in_progress_space;
154 155 GC_ASSERT(GC_page_size != 0);
156 if (NULL == in_progress_space) {
157 in_progress_size
158 = ROUNDUP_PAGESIZE_IF_MMAP(INITIAL_IN_PROGRESS * sizeof(ptr_t))
159 / sizeof(ptr_t);
160 new_in_progress_space
161 = (ptr_t *)GC_os_get_mem(in_progress_size * sizeof(ptr_t));
162 } else {
163 in_progress_size *= 2;
164 new_in_progress_space
165 = (ptr_t *)GC_os_get_mem(in_progress_size * sizeof(ptr_t));
166 if (new_in_progress_space != NULL)
167 BCOPY(in_progress_space, new_in_progress_space,
168 n_in_progress * sizeof(ptr_t));
169 }
170 # ifndef GWW_VDB
171 GC_scratch_recycle_no_gww(in_progress_space,
172 n_in_progress * sizeof(ptr_t));
173 # elif defined(LINT2)
174 /* TODO: Implement GWW-aware recycling as in `alloc_mark_stack`. */
175 GC_noop1_ptr(in_progress_space);
176 # endif
177 in_progress_space = new_in_progress_space;
178 }
179 if (in_progress_space == 0)
180 ABORT("MAKE_BACK_GRAPH: Out of in-progress space: "
181 "Huge linear data structure?");
182 in_progress_space[n_in_progress++] = p;
183 }
184 185 static GC_bool
186 is_in_progress(const char *p)
187 {
188 size_t i;
189 for (i = 0; i < n_in_progress; ++i) {
190 if (in_progress_space[i] == p)
191 return TRUE;
192 }
193 return FALSE;
194 }
195 196 GC_INLINE void
197 pop_in_progress(ptr_t p)
198 {
199 # ifndef GC_ASSERTIONS
200 UNUSED_ARG(p);
201 # endif
202 --n_in_progress;
203 GC_ASSERT(in_progress_space[n_in_progress] == p);
204 }
205 206 # define GET_OH_BG_PTR(p) (ptr_t) GC_REVEAL_POINTER(((oh *)(p))->oh_bg_ptr)
207 # define SET_OH_BG_PTR(p, q) (((oh *)(p))->oh_bg_ptr = GC_HIDE_POINTER(q))
208 209 /* Ensure that `p` has a `back_edges` structure associated with it. */
210 static void
211 ensure_struct(ptr_t p)
212 {
213 ptr_t old_back_ptr = GET_OH_BG_PTR(p);
214 215 GC_ASSERT(I_HOLD_LOCK());
216 if ((ADDR(old_back_ptr) & FLAG_MANY) == 0) {
217 back_edges *be = new_back_edges();
218 219 be->flags = 0;
220 # if defined(CPPCHECK)
221 GC_noop1_ptr(&old_back_ptr);
222 /* Workaround a false positive that `old_back_ptr` cannot be `NULL`. */
223 # endif
224 if (NULL == old_back_ptr) {
225 be->n_edges = 0;
226 } else {
227 be->n_edges = 1;
228 be->edges[0] = old_back_ptr;
229 }
230 be->height = HEIGHT_UNKNOWN;
231 be->height_gc_no = (unsigned short)(GC_gc_no - 1);
232 GC_ASSERT(ADDR_GE((ptr_t)be, (ptr_t)back_edge_space));
233 SET_OH_BG_PTR(p, CPTR_SET_FLAGS(be, FLAG_MANY));
234 }
235 }
236 237 /*
238 * Add the (forward) edge from `p` to `q` to the backward graph. Both `p`
239 * and `q` are pointers to the object base, i.e. pointers to an `oh`.
240 */
241 static void
242 add_edge(ptr_t p, ptr_t q)
243 {
244 ptr_t pred = GET_OH_BG_PTR(q);
245 back_edges *be, *be_cont;
246 word i;
247 248 GC_ASSERT(p == GC_base(p) && q == GC_base(q));
249 GC_ASSERT(I_HOLD_LOCK());
250 if (!GC_HAS_DEBUG_INFO(q) || !GC_HAS_DEBUG_INFO(p)) {
251 /*
252 * This is really a misinterpreted free-list link, since we saw
253 * a pointer to a free list. Do not overwrite it!
254 */
255 return;
256 }
257 # if defined(CPPCHECK)
258 GC_noop1_ptr(&pred);
259 # endif
260 if (NULL == pred) {
261 /*
262 * A not very random number we use to occasionally allocate
263 * a `back_edges` structure even for a single backward edge.
264 * This prevents us from repeatedly tracing back through very long
265 * chains, since we will have some place to store `height` and
266 * `HEIGHT_IN_PROGRESS` flag along the way.
267 */
268 # define GOT_LUCKY_NUMBER (((++random_number) & 0x7f) == 0)
269 static unsigned random_number = 13;
270 271 SET_OH_BG_PTR(q, p);
272 if (GOT_LUCKY_NUMBER)
273 ensure_struct(q);
274 return;
275 }
276 277 /* Check whether it was already in the list of predecessors. */
278 {
279 back_edges *e = (back_edges *)CPTR_CLEAR_FLAGS(pred, FLAG_MANY);
280 word n_edges;
281 word total;
282 int local = 0;
283 284 if ((ADDR(pred) & FLAG_MANY) != 0) {
285 n_edges = e->n_edges;
286 } else if ((COVERT_DATAFLOW(ADDR(pred)) & 1) == 0) {
287 /* A misinterpreted free-list link. */
288 n_edges = 1;
289 local = -1;
290 } else {
291 n_edges = 0;
292 }
293 for (total = 0; total < n_edges; ++total) {
294 if (local == MAX_IN) {
295 e = e->cont;
296 local = 0;
297 }
298 if (local >= 0)
299 pred = e->edges[local++];
300 if (pred == p)
301 return;
302 }
303 }
304 305 ensure_struct(q);
306 be = (back_edges *)CPTR_CLEAR_FLAGS(GET_OH_BG_PTR(q), FLAG_MANY);
307 for (i = be->n_edges, be_cont = be; i > MAX_IN; i -= MAX_IN)
308 be_cont = be_cont->cont;
309 if (i == MAX_IN) {
310 be_cont->cont = new_back_edges();
311 be_cont = be_cont->cont;
312 i = 0;
313 }
314 be_cont->edges[i] = p;
315 be->n_edges++;
316 # ifdef DEBUG_PRINT_BIG_N_EDGES
317 if (GC_print_stats == VERBOSE && be->n_edges == 100) {
318 GC_err_printf("The following object has big in-degree:\n");
319 # ifdef THREADS
320 /*
321 * Note: we cannot call the debug variant of `GC_print_heap_obj` here
322 * because the allocator lock is held.
323 */
324 GC_default_print_heap_obj_proc(q);
325 # else
326 GC_print_heap_obj(q);
327 # endif
328 }
329 # endif
330 }
331 332 typedef void (*per_object_func)(ptr_t p, size_t sz, word descr);
333 334 static GC_CALLBACK void
335 per_object_helper(struct hblk *h, void *fn_ptr)
336 {
337 const hdr *hhdr = HDR(h);
338 word descr = hhdr->hb_descr;
339 per_object_func fn = *(per_object_func *)fn_ptr;
340 size_t sz = hhdr->hb_sz;
341 size_t i = 0;
342 343 do {
344 fn((ptr_t)(h->hb_body + i), sz, descr);
345 i += sz;
346 } while (i + sz <= HBLKSIZE);
347 }
348 349 GC_INLINE void
350 GC_apply_to_each_object(per_object_func fn)
351 {
352 GC_apply_to_all_blocks(per_object_helper, &fn);
353 }
354 355 static void
356 reset_back_edge(ptr_t p, size_t sz, word descr)
357 {
358 UNUSED_ARG(sz);
359 UNUSED_ARG(descr);
360 GC_ASSERT(I_HOLD_LOCK());
361 /* Skip any free-list links, or dropped blocks. */
362 if (GC_HAS_DEBUG_INFO(p)) {
363 ptr_t old_back_ptr = GET_OH_BG_PTR(p);
364 365 if ((ADDR(old_back_ptr) & FLAG_MANY) != 0) {
366 back_edges *be = (back_edges *)CPTR_CLEAR_FLAGS(old_back_ptr, FLAG_MANY);
367 368 if (!(be->flags & RETAIN)) {
369 deallocate_back_edges(be);
370 SET_OH_BG_PTR(p, NULL);
371 } else {
372 GC_ASSERT(GC_is_marked(p));
373 374 /*
375 * Back edges may point to objects that will not be retained.
376 * Delete them for now, but remember the height. Some will be
377 * added back at next collection.
378 */
379 be->n_edges = 0;
380 if (be->cont != NULL) {
381 deallocate_back_edges(be->cont);
382 be->cont = NULL;
383 }
384 385 GC_ASSERT(GC_is_marked(p));
386 /* We only retain things for one collection cycle at a time. */
387 be->flags &= (unsigned short)~RETAIN;
388 }
389 } else /* simple back pointer */ {
390 /* Clear to avoid dangling pointer. */
391 SET_OH_BG_PTR(p, NULL);
392 }
393 }
394 }
395 396 static void
397 add_back_edges(ptr_t p, size_t sz, word descr)
398 {
399 ptr_t current_p = p + sizeof(oh);
400 401 /* For now, fix up non-length descriptors conservatively. */
402 if ((descr & GC_DS_TAGS) != GC_DS_LENGTH) {
403 descr = sz;
404 }
405 406 for (; ADDR_LT(current_p, p + descr); current_p += sizeof(ptr_t)) {
407 ptr_t q;
408 409 LOAD_PTR_OR_CONTINUE(q, current_p);
410 FIXUP_POINTER(q);
411 if (GC_least_real_heap_addr < ADDR(q)
412 && ADDR(q) < GC_greatest_real_heap_addr) {
413 ptr_t target = (ptr_t)GC_base(q);
414 415 if (target != NULL)
416 add_edge(p, target);
417 }
418 }
419 }
420 421 GC_INNER void
422 GC_build_back_graph(void)
423 {
424 GC_ASSERT(I_HOLD_LOCK());
425 GC_apply_to_each_object(add_back_edges);
426 }
427 428 /*
429 * Return an approximation to the length of the longest simple path through
430 * unreachable objects to `p`. We refer to this as the height of `p`.
431 */
432 static word
433 backwards_height(ptr_t p)
434 {
435 word result;
436 ptr_t pred = GET_OH_BG_PTR(p);
437 back_edges *be;
438 439 GC_ASSERT(I_HOLD_LOCK());
440 # if defined(CPPCHECK)
441 GC_noop1_ptr(&pred);
442 # endif
443 if (NULL == pred)
444 return 1;
445 if ((ADDR(pred) & FLAG_MANY) == 0) {
446 if (is_in_progress(p)) {
447 /*
448 * DFS (depth-first search) back edge, i.e. we followed an edge to
449 * an object already on our stack. Ignore.
450 */
451 return 0;
452 }
453 push_in_progress(p);
454 result = backwards_height(pred) + 1;
455 pop_in_progress(p);
456 return result;
457 }
458 be = (back_edges *)CPTR_CLEAR_FLAGS(pred, FLAG_MANY);
459 if (be->height >= 0 && be->height_gc_no == (unsigned short)GC_gc_no)
460 return (word)be->height;
461 /* Ignore back edges in DFS. */
462 if (be->height == HEIGHT_IN_PROGRESS)
463 return 0;
464 465 result = be->height > 0 ? (word)be->height : 1U;
466 be->height = HEIGHT_IN_PROGRESS;
467 468 {
469 back_edges *e = be;
470 word n_edges;
471 word total;
472 int local = 0;
473 474 if ((ADDR(pred) & FLAG_MANY) != 0) {
475 n_edges = e->n_edges;
476 } else if ((ADDR(pred) & 1) == 0) {
477 /* A misinterpreted free-list link. */
478 n_edges = 1;
479 local = -1;
480 } else {
481 n_edges = 0;
482 }
483 for (total = 0; total < n_edges; ++total) {
484 word this_height;
485 if (local == MAX_IN) {
486 e = e->cont;
487 local = 0;
488 }
489 if (local >= 0)
490 pred = e->edges[local++];
491 492 /*
493 * Execute the following once for each predecessor `pred` of `p`
494 * in the points-to graph.
495 */
496 if (GC_is_marked(pred) && (ADDR(GET_OH_BG_PTR(p)) & FLAG_MANY) == 0) {
497 GC_COND_LOG_PRINTF("Found bogus pointer from %p to %p\n", (void *)pred,
498 (void *)p);
499 /*
500 * Reachable object "points to" unreachable one. Could be caused
501 * by our lax treatment of the collector descriptors.
502 */
503 this_height = 1;
504 } else {
505 this_height = backwards_height(pred);
506 }
507 if (this_height >= result)
508 result = this_height + 1;
509 }
510 }
511 512 be->height = (GC_signed_word)result;
513 be->height_gc_no = (unsigned short)GC_gc_no;
514 return result;
515 }
516 517 STATIC word GC_max_height = 0;
518 STATIC ptr_t GC_deepest_obj = NULL;
519 520 /*
521 * Compute the maximum height of every unreachable predecessor `p` of
522 * a reachable object. Arrange to save the heights of all such objects
523 * `p` so that they can be used in calculating the height of objects in
524 * the next collection. Set `GC_max_height` to be the maximum height
525 * we encounter, and `GC_deepest_obj` to be the corresponding object.
526 */
527 static void
528 update_max_height(ptr_t p, size_t sz, word descr)
529 {
530 UNUSED_ARG(sz);
531 UNUSED_ARG(descr);
532 GC_ASSERT(I_HOLD_LOCK());
533 if (GC_is_marked(p) && GC_HAS_DEBUG_INFO(p)) {
534 word p_height = 0;
535 ptr_t p_deepest_obj = 0;
536 ptr_t back_ptr;
537 back_edges *be = 0;
538 539 /*
540 * If we remembered a height last time, use it as a minimum.
541 * It may have increased due to newly unreachable chains pointing
542 * to `p`, but it cannot have decreased.
543 */
544 back_ptr = GET_OH_BG_PTR(p);
545 # if defined(CPPCHECK)
546 GC_noop1_ptr(&back_ptr);
547 # endif
548 if (back_ptr != NULL && (ADDR(back_ptr) & FLAG_MANY) != 0) {
549 be = (back_edges *)CPTR_CLEAR_FLAGS(back_ptr, FLAG_MANY);
550 if (be->height != HEIGHT_UNKNOWN)
551 p_height = (word)be->height;
552 }
553 554 {
555 ptr_t pred = back_ptr;
556 back_edges *e = (back_edges *)CPTR_CLEAR_FLAGS(pred, FLAG_MANY);
557 word n_edges;
558 word total;
559 int local = 0;
560 561 if ((ADDR(pred) & FLAG_MANY) != 0) {
562 n_edges = e->n_edges;
563 } else if (pred != NULL && (ADDR(pred) & 1) == 0) {
564 /* A misinterpreted free-list link. */
565 n_edges = 1;
566 local = -1;
567 } else {
568 n_edges = 0;
569 }
570 for (total = 0; total < n_edges; ++total) {
571 if (local == MAX_IN) {
572 e = e->cont;
573 local = 0;
574 }
575 if (local >= 0)
576 pred = e->edges[local++];
577 578 /*
579 * Execute the following once for each predecessor `pred` of `p`
580 * in the points-to graph.
581 */
582 if (!GC_is_marked(pred) && GC_HAS_DEBUG_INFO(pred)) {
583 word this_height = backwards_height(pred);
584 585 if (this_height > p_height) {
586 p_height = this_height;
587 p_deepest_obj = pred;
588 }
589 }
590 }
591 }
592 593 if (p_height > 0) {
594 /* Remember the height for next time. */
595 if (NULL == be) {
596 ensure_struct(p);
597 back_ptr = GET_OH_BG_PTR(p);
598 be = (back_edges *)CPTR_CLEAR_FLAGS(back_ptr, FLAG_MANY);
599 }
600 be->flags |= RETAIN;
601 be->height = (GC_signed_word)p_height;
602 be->height_gc_no = (unsigned short)GC_gc_no;
603 }
604 if (p_height > GC_max_height) {
605 GC_max_height = p_height;
606 GC_deepest_obj = p_deepest_obj;
607 }
608 }
609 }
610 611 STATIC word GC_max_max_height = 0;
612 613 GC_INNER void
614 GC_traverse_back_graph(void)
615 {
616 GC_ASSERT(I_HOLD_LOCK());
617 GC_max_height = 0;
618 GC_apply_to_each_object(update_max_height);
619 if (GC_deepest_obj != NULL) {
620 /* Keep the pointer until we can print it. */
621 GC_set_mark_bit(GC_deepest_obj);
622 }
623 }
624 625 void
626 GC_print_back_graph_stats(void)
627 {
628 GC_ASSERT(I_HOLD_LOCK());
629 GC_printf("Maximum backwards height of reachable objects"
630 " at GC #%lu is %lu\n",
631 (unsigned long)GC_gc_no, (unsigned long)GC_max_height);
632 if (GC_max_height > GC_max_max_height) {
633 ptr_t obj = GC_deepest_obj;
634 635 GC_max_max_height = GC_max_height;
636 UNLOCK();
637 GC_err_printf(
638 "The following unreachable object is last in a longest chain "
639 "of unreachable objects:\n");
640 GC_print_heap_obj(obj);
641 LOCK();
642 }
643 GC_COND_LOG_PRINTF("Needed max total of %d back-edge structs\n",
644 GC_n_back_edge_structs);
645 GC_apply_to_each_object(reset_back_edge);
646 GC_deepest_obj = NULL;
647 }
648 649 #endif /* MAKE_BACK_GRAPH */
650