]>
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 | ||
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++; | |
ff6fe7a1 | 310 | FIXUP_POINTER(current); |
c2206235 BM |
311 | if (current >= (word)GC_least_plausible_heap_addr && |
312 | current <= (word)GC_greatest_plausible_heap_addr) { | |
313 | ptr_t target = GC_base((GC_PTR)current); | |
314 | if (0 != target) { | |
315 | add_edge(p, target); | |
316 | } | |
317 | } | |
318 | } | |
319 | } | |
320 | ||
321 | /* Rebuild the reprentation of the backward reachability graph. */ | |
322 | /* Does not examine mark bits. Can be called before GC. */ | |
323 | void GC_build_back_graph(void) | |
324 | { | |
325 | GC_apply_to_each_object(add_back_edges); | |
326 | } | |
327 | ||
328 | /* Return an approximation to the length of the longest simple path */ | |
329 | /* through unreachable objects to p. We refer to this as the height */ | |
330 | /* of p. */ | |
331 | static word backwards_height(ptr_t p) | |
332 | { | |
333 | word result; | |
334 | ptr_t back_ptr = GET_OH_BG_PTR(p); | |
335 | back_edges *be; | |
336 | ||
337 | if (0 == back_ptr) return 1; | |
338 | if (!((word)back_ptr & FLAG_MANY)) { | |
339 | if (is_in_progress(p)) return 0; /* DFS back edge, i.e. we followed */ | |
340 | /* an edge to an object already */ | |
341 | /* on our stack: ignore */ | |
342 | push_in_progress(p); | |
343 | result = backwards_height(back_ptr)+1; | |
344 | pop_in_progress(p); | |
345 | return result; | |
346 | } | |
347 | be = (back_edges *)((word)back_ptr & ~FLAG_MANY); | |
348 | if (be -> height >= 0 && be -> height_gc_no == GC_gc_no) | |
349 | return be -> height; | |
350 | /* Ignore back edges in DFS */ | |
351 | if (be -> height == HEIGHT_IN_PROGRESS) return 0; | |
352 | result = (be -> height > 0? be -> height : 1); | |
353 | be -> height = HEIGHT_IN_PROGRESS; | |
354 | FOR_EACH_PRED(q, p, { | |
355 | word this_height; | |
356 | if (GC_is_marked(q) && !(FLAG_MANY & (word)GET_OH_BG_PTR(p))) { | |
357 | if (GC_print_stats) | |
358 | GC_printf2("Found bogus pointer from 0x%lx to 0x%lx\n", q, p); | |
359 | /* Reachable object "points to" unreachable one. */ | |
360 | /* Could be caused by our lax treatment of GC descriptors. */ | |
361 | this_height = 1; | |
362 | } else { | |
363 | this_height = backwards_height(q); | |
364 | } | |
365 | if (this_height >= result) result = this_height + 1; | |
366 | }); | |
367 | be -> height = result; | |
368 | be -> height_gc_no = GC_gc_no; | |
369 | return result; | |
370 | } | |
371 | ||
372 | word GC_max_height; | |
373 | ptr_t GC_deepest_obj; | |
374 | ||
375 | /* Compute the maximum height of every unreachable predecessor p of a */ | |
376 | /* reachable object. Arrange to save the heights of all such objects p */ | |
377 | /* so that they can be used in calculating the height of objects in the */ | |
378 | /* next GC. */ | |
379 | /* Set GC_max_height to be the maximum height we encounter, and */ | |
380 | /* GC_deepest_obj to be the corresponding object. */ | |
381 | static void update_max_height(ptr_t p, word n_words, word gc_descr) | |
382 | { | |
383 | if (GC_is_marked(p) && GC_HAS_DEBUG_INFO(p)) { | |
384 | int i; | |
385 | word p_height = 0; | |
386 | ptr_t p_deepest_obj = 0; | |
387 | ptr_t back_ptr; | |
388 | back_edges *be = 0; | |
389 | ||
390 | /* If we remembered a height last time, use it as a minimum. */ | |
391 | /* It may have increased due to newly unreachable chains pointing */ | |
392 | /* to p, but it can't have decreased. */ | |
393 | back_ptr = GET_OH_BG_PTR(p); | |
394 | if (0 != back_ptr && ((word)back_ptr & FLAG_MANY)) { | |
395 | be = (back_edges *)((word)back_ptr & ~FLAG_MANY); | |
396 | if (be -> height != HEIGHT_UNKNOWN) p_height = be -> height; | |
397 | } | |
398 | FOR_EACH_PRED(q, p, { | |
399 | if (!GC_is_marked(q) && GC_HAS_DEBUG_INFO(q)) { | |
400 | word q_height; | |
401 | ||
402 | q_height = backwards_height(q); | |
403 | if (q_height > p_height) { | |
404 | p_height = q_height; | |
405 | p_deepest_obj = q; | |
406 | } | |
407 | } | |
408 | }); | |
409 | if (p_height > 0) { | |
410 | /* Remember the height for next time. */ | |
411 | if (be == 0) { | |
412 | ensure_struct(p); | |
413 | back_ptr = GET_OH_BG_PTR(p); | |
414 | be = (back_edges *)((word)back_ptr & ~FLAG_MANY); | |
415 | } | |
416 | be -> flags |= RETAIN; | |
417 | be -> height = p_height; | |
418 | be -> height_gc_no = GC_gc_no; | |
419 | } | |
420 | if (p_height > GC_max_height) { | |
421 | GC_max_height = p_height; | |
422 | GC_deepest_obj = p_deepest_obj; | |
423 | } | |
424 | } | |
425 | } | |
426 | ||
427 | void GC_traverse_back_graph(void) | |
428 | { | |
429 | static word max_max_height = 0; | |
430 | GC_max_height = 0; | |
431 | GC_apply_to_each_object(update_max_height); | |
432 | GC_printf2("Maximum backwards height of reachable objects at GC %lu is %ld\n", | |
433 | (unsigned long) GC_gc_no, GC_max_height); | |
434 | if (GC_max_height > max_max_height) { | |
435 | max_max_height = GC_max_height; | |
436 | GC_printf0("The following unreachable object is last in a longest chain " | |
437 | "of unreachable objects:\n"); | |
438 | GC_print_heap_obj(GC_deepest_obj); | |
439 | } | |
440 | if (GC_print_stats) { | |
441 | GC_printf1("Needed max total of %ld back-edge structs\n", | |
442 | GC_n_back_edge_structs); | |
443 | } | |
444 | GC_apply_to_each_object(reset_back_edge); | |
445 | GC_deepest_obj = 0; | |
446 | } | |
447 | ||
448 | #endif /* MAKE_BACK_GRAPH */ |