OSDN Git Service

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