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