]>
Commit | Line | Data |
---|---|---|
05513b45 | 1 | /* Simple garbage collection for the GNU compiler. |
3915b59e | 2 | Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. |
05513b45 | 3 | |
f12b58b3 | 4 | This file is part of GCC. |
05513b45 | 5 | |
f12b58b3 | 6 | GCC is free software; you can redistribute it and/or modify it |
7 | under the terms of the GNU General Public License as published by | |
05513b45 | 8 | the Free Software Foundation; either version 2, or (at your option) |
9 | any later version. | |
10 | ||
f12b58b3 | 11 | GCC is distributed in the hope that it will be useful, but WITHOUT |
12 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
13 | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
14 | License for more details. | |
05513b45 | 15 | |
16 | You should have received a copy of the GNU General Public License | |
f12b58b3 | 17 | along with GCC; see the file COPYING. If not, write to the Free |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
05513b45 | 20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "rtl.h" | |
24 | #include "tree.h" | |
f8e15e8a | 25 | #include "tm_p.h" |
05513b45 | 26 | #include "flags.h" |
1bfd55c5 | 27 | #include "varray.h" |
f8e15e8a | 28 | #include "ggc.h" |
74d2af64 | 29 | #include "timevar.h" |
05513b45 | 30 | |
31 | /* Debugging flags. */ | |
5ae3ca64 | 32 | |
33 | /* Zap memory before freeing to catch dangling pointers. */ | |
05513b45 | 34 | #define GGC_POISON |
35 | ||
71661611 | 36 | /* Collect statistics on how bushy the search tree is. */ |
37 | #undef GGC_BALANCE | |
5ae3ca64 | 38 | |
71661611 | 39 | /* Perform collection every time ggc_collect is invoked. Otherwise, |
40 | collection is performed only when a significant amount of memory | |
41 | has been allocated since the last collection. */ | |
42 | #undef GGC_ALWAYS_COLLECT | |
c47fa274 | 43 | |
71661611 | 44 | /* Always verify that the to-be-marked memory is collectable. */ |
45 | #undef GGC_ALWAYS_VERIFY | |
c47fa274 | 46 | |
0c4e40c5 | 47 | #ifdef ENABLE_GC_CHECKING |
71661611 | 48 | #define GGC_POISON |
71661611 | 49 | #define GGC_ALWAYS_VERIFY |
50 | #endif | |
0c4e40c5 | 51 | #ifdef ENABLE_GC_ALWAYS_COLLECT |
52 | #define GGC_ALWAYS_COLLECT | |
53 | #endif | |
c47fa274 | 54 | |
71661611 | 55 | #ifndef HOST_BITS_PER_PTR |
56 | #define HOST_BITS_PER_PTR HOST_BITS_PER_LONG | |
57 | #endif | |
05513b45 | 58 | |
71661611 | 59 | /* We'd like a balanced tree, but we don't really want to pay for the |
60 | cost of keeping the tree balanced. We'll settle for the next best | |
61 | thing -- nearly balanced. | |
05513b45 | 62 | |
71661611 | 63 | In this context, the most natural key is the node pointer itself, |
64 | but due to the way memory managers work, we'd be virtually certain | |
65 | to wind up with a completely degenerate straight line. What's needed | |
66 | is to make something more variable, and yet predictable, be more | |
67 | significant in the comparison. | |
05513b45 | 68 | |
71661611 | 69 | The handiest source of variability is the low bits of the pointer |
70 | value itself. Any sort of bit/byte swap would do, but such machine | |
71 | specific operations are not handy, and we don't want to put that much | |
72 | effort into it. */ | |
05513b45 | 73 | |
71661611 | 74 | #define PTR_KEY(p) ((size_t)p << (HOST_BITS_PER_PTR - 8) \ |
75 | | ((size_t)p & 0xff00) << (HOST_BITS_PER_PTR - 24) \ | |
76 | | (size_t)p >> 16) | |
05513b45 | 77 | |
71661611 | 78 | /* GC'able memory; a node in a binary search tree. */ |
431270dd | 79 | |
71661611 | 80 | struct ggc_mem |
431270dd | 81 | { |
71661611 | 82 | /* A combination of the standard left/right nodes, indexable by `<'. */ |
83 | struct ggc_mem *sub[2]; | |
84 | ||
85 | unsigned int mark : 1; | |
86 | unsigned int context : 7; | |
87 | unsigned int size : 24; | |
431270dd | 88 | |
89 | /* Make sure the data is reasonably aligned. */ | |
90 | union { | |
71661611 | 91 | HOST_WIDEST_INT i; |
6a7488af | 92 | #ifdef HAVE_LONG_DOUBLE |
431270dd | 93 | long double d; |
6a7488af | 94 | #else |
95 | double d; | |
96 | #endif | |
431270dd | 97 | } u; |
98 | }; | |
99 | ||
71661611 | 100 | static struct globals |
c788feb1 | 101 | { |
71661611 | 102 | /* Root of the object tree. */ |
103 | struct ggc_mem *root; | |
c788feb1 | 104 | |
71661611 | 105 | /* Data bytes currently allocated. */ |
106 | size_t allocated; | |
05513b45 | 107 | |
71661611 | 108 | /* Data objects currently allocated. */ |
109 | size_t objects; | |
e3691812 | 110 | |
71661611 | 111 | /* Data bytes allocated at time of last GC. */ |
112 | size_t allocated_last_gc; | |
05513b45 | 113 | |
71661611 | 114 | /* Current context level. */ |
115 | int context; | |
116 | } G; | |
05513b45 | 117 | |
71661611 | 118 | /* Skip garbage collection if the current allocation is not at least |
119 | this factor times the allocation at the end of the last collection. | |
120 | In other words, total allocation must expand by (this factor minus | |
121 | one) before collection is performed. */ | |
122 | #define GGC_MIN_EXPAND_FOR_GC (1.3) | |
05513b45 | 123 | |
71661611 | 124 | /* Bound `allocated_last_gc' to 4MB, to prevent the memory expansion |
125 | test from triggering too often when the heap is small. */ | |
126 | #define GGC_MIN_LAST_ALLOCATED (4 * 1024 * 1024) | |
c47fa274 | 127 | |
71661611 | 128 | /* Local function prototypes. */ |
c788feb1 | 129 | |
38b9004f | 130 | static void tree_insert PARAMS ((struct ggc_mem *)); |
131 | static int tree_lookup PARAMS ((struct ggc_mem *)); | |
132 | static void clear_marks PARAMS ((struct ggc_mem *)); | |
133 | static void sweep_objs PARAMS ((struct ggc_mem **)); | |
134 | static void ggc_pop_context_1 PARAMS ((struct ggc_mem *, int)); | |
5ae3ca64 | 135 | |
2a8997e8 | 136 | /* For use from debugger. */ |
137 | extern void debug_ggc_tree PARAMS ((struct ggc_mem *, int)); | |
138 | ||
71661611 | 139 | #ifdef GGC_BALANCE |
38b9004f | 140 | extern void debug_ggc_balance PARAMS ((void)); |
5ae3ca64 | 141 | #endif |
2a8997e8 | 142 | static void tally_leaves PARAMS ((struct ggc_mem *, int, size_t *, size_t *)); |
0f4dbfb9 | 143 | |
71661611 | 144 | /* Insert V into the search tree. */ |
c788feb1 | 145 | |
71661611 | 146 | static inline void |
147 | tree_insert (v) | |
148 | struct ggc_mem *v; | |
c788feb1 | 149 | { |
71661611 | 150 | size_t v_key = PTR_KEY (v); |
151 | struct ggc_mem *p, **pp; | |
c788feb1 | 152 | |
71661611 | 153 | for (pp = &G.root, p = *pp; p ; p = *pp) |
c788feb1 | 154 | { |
71661611 | 155 | size_t p_key = PTR_KEY (p); |
156 | pp = &p->sub[v_key < p_key]; | |
c788feb1 | 157 | } |
71661611 | 158 | *pp = v; |
159 | } | |
c788feb1 | 160 | |
71661611 | 161 | /* Return true if V is in the tree. */ |
c788feb1 | 162 | |
71661611 | 163 | static inline int |
164 | tree_lookup (v) | |
165 | struct ggc_mem *v; | |
166 | { | |
167 | size_t v_key = PTR_KEY (v); | |
168 | struct ggc_mem *p = G.root; | |
c788feb1 | 169 | |
71661611 | 170 | while (p) |
e3691812 | 171 | { |
71661611 | 172 | size_t p_key = PTR_KEY (p); |
173 | if (p == v) | |
174 | return 1; | |
175 | p = p->sub[v_key < p_key]; | |
e3691812 | 176 | } |
177 | ||
71661611 | 178 | return 0; |
c788feb1 | 179 | } |
180 | ||
71661611 | 181 | /* Alloc SIZE bytes of GC'able memory. If ZERO, clear the memory. */ |
05513b45 | 182 | |
71661611 | 183 | void * |
791ceafe | 184 | ggc_alloc (size) |
71661611 | 185 | size_t size; |
05513b45 | 186 | { |
71661611 | 187 | struct ggc_mem *x; |
05513b45 | 188 | |
71661611 | 189 | x = (struct ggc_mem *) xmalloc (offsetof (struct ggc_mem, u) + size); |
190 | x->sub[0] = NULL; | |
191 | x->sub[1] = NULL; | |
192 | x->mark = 0; | |
193 | x->context = G.context; | |
194 | x->size = size; | |
05513b45 | 195 | |
e3c4633e | 196 | #ifdef GGC_POISON |
791ceafe | 197 | memset (&x->u, 0xaf, size); |
e3c4633e | 198 | #endif |
05513b45 | 199 | |
71661611 | 200 | tree_insert (x); |
201 | G.allocated += size; | |
202 | G.objects += 1; | |
05513b45 | 203 | |
71661611 | 204 | return &x->u; |
05513b45 | 205 | } |
206 | ||
71661611 | 207 | /* Mark a node. */ |
05513b45 | 208 | |
71661611 | 209 | int |
210 | ggc_set_mark (p) | |
9a356c3c | 211 | const void *p; |
05513b45 | 212 | { |
71661611 | 213 | struct ggc_mem *x; |
05513b45 | 214 | |
9a356c3c | 215 | x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u)); |
71661611 | 216 | #ifdef GGC_ALWAYS_VERIFY |
217 | if (! tree_lookup (x)) | |
218 | abort (); | |
05513b45 | 219 | #endif |
220 | ||
71661611 | 221 | if (x->mark) |
222 | return 1; | |
05513b45 | 223 | |
71661611 | 224 | x->mark = 1; |
225 | G.allocated += x->size; | |
226 | G.objects += 1; | |
05513b45 | 227 | |
71661611 | 228 | return 0; |
05513b45 | 229 | } |
230 | ||
15d769aa | 231 | /* Return 1 if P has been marked, zero otherwise. */ |
232 | ||
233 | int | |
234 | ggc_marked_p (p) | |
235 | const void *p; | |
236 | { | |
237 | struct ggc_mem *x; | |
238 | ||
239 | x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u)); | |
240 | #ifdef GGC_ALWAYS_VERIFY | |
241 | if (! tree_lookup (x)) | |
242 | abort (); | |
243 | #endif | |
244 | ||
245 | return x->mark; | |
246 | } | |
247 | ||
e3c4633e | 248 | /* Return the size of the gc-able object P. */ |
249 | ||
4e00b6fd | 250 | size_t |
251 | ggc_get_size (p) | |
9a356c3c | 252 | const void *p; |
4e00b6fd | 253 | { |
3cfec666 | 254 | struct ggc_mem *x |
9a356c3c | 255 | = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u)); |
4e00b6fd | 256 | return x->size; |
257 | } | |
258 | ||
e3c4633e | 259 | /* Unmark all objects. */ |
260 | ||
71661611 | 261 | static void |
262 | clear_marks (x) | |
263 | struct ggc_mem *x; | |
05513b45 | 264 | { |
71661611 | 265 | x->mark = 0; |
266 | if (x->sub[0]) | |
267 | clear_marks (x->sub[0]); | |
268 | if (x->sub[1]) | |
269 | clear_marks (x->sub[1]); | |
05513b45 | 270 | } |
271 | ||
e3c4633e | 272 | /* Free all objects in the current context that are not marked. */ |
273 | ||
71661611 | 274 | static void |
275 | sweep_objs (root) | |
276 | struct ggc_mem **root; | |
05513b45 | 277 | { |
71661611 | 278 | struct ggc_mem *x = *root; |
279 | if (!x) | |
280 | return; | |
05513b45 | 281 | |
71661611 | 282 | sweep_objs (&x->sub[0]); |
283 | sweep_objs (&x->sub[1]); | |
05513b45 | 284 | |
71661611 | 285 | if (! x->mark && x->context >= G.context) |
286 | { | |
287 | struct ggc_mem *l, *r; | |
288 | ||
289 | l = x->sub[0]; | |
290 | r = x->sub[1]; | |
291 | if (!l) | |
292 | *root = r; | |
293 | else if (!r) | |
294 | *root = l; | |
295 | else if (!l->sub[1]) | |
296 | { | |
297 | *root = l; | |
298 | l->sub[1] = r; | |
299 | } | |
300 | else if (!r->sub[0]) | |
301 | { | |
302 | *root = r; | |
303 | r->sub[0] = l; | |
304 | } | |
305 | else | |
306 | { | |
307 | *root = l; | |
308 | do { | |
309 | root = &l->sub[1]; | |
310 | } while ((l = *root) != NULL); | |
311 | *root = r; | |
312 | } | |
05513b45 | 313 | |
05513b45 | 314 | #ifdef GGC_POISON |
71661611 | 315 | memset (&x->u, 0xA5, x->size); |
05513b45 | 316 | #endif |
317 | ||
71661611 | 318 | free (x); |
319 | } | |
05513b45 | 320 | } |
321 | ||
71661611 | 322 | /* The top level mark-and-sweep routine. */ |
05513b45 | 323 | |
71661611 | 324 | void |
325 | ggc_collect () | |
05513b45 | 326 | { |
71661611 | 327 | #ifndef GGC_ALWAYS_COLLECT |
328 | if (G.allocated < GGC_MIN_EXPAND_FOR_GC * G.allocated_last_gc) | |
329 | return; | |
05513b45 | 330 | #endif |
331 | ||
71661611 | 332 | #ifdef GGC_BALANCE |
333 | debug_ggc_balance (); | |
334 | #endif | |
05513b45 | 335 | |
74d2af64 | 336 | timevar_push (TV_GC); |
71661611 | 337 | if (!quiet_flag) |
338 | fprintf (stderr, " {GC %luk -> ", (unsigned long)G.allocated / 1024); | |
c47fa274 | 339 | |
71661611 | 340 | G.allocated = 0; |
341 | G.objects = 0; | |
c47fa274 | 342 | |
71661611 | 343 | clear_marks (G.root); |
344 | ggc_mark_roots (); | |
345 | sweep_objs (&G.root); | |
c47fa274 | 346 | |
71661611 | 347 | G.allocated_last_gc = G.allocated; |
348 | if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED) | |
349 | G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED; | |
05513b45 | 350 | |
74d2af64 | 351 | timevar_pop (TV_GC); |
05513b45 | 352 | |
71661611 | 353 | if (!quiet_flag) |
74d2af64 | 354 | fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024); |
05513b45 | 355 | |
71661611 | 356 | #ifdef GGC_BALANCE |
357 | debug_ggc_balance (); | |
358 | #endif | |
40a038bc | 359 | } |
360 | ||
71661611 | 361 | /* Called once to initialize the garbage collector. */ |
e3691812 | 362 | |
3cfec666 | 363 | void |
71661611 | 364 | init_ggc () |
e3691812 | 365 | { |
71661611 | 366 | G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED; |
e3691812 | 367 | } |
368 | ||
71661611 | 369 | /* Start a new GGC context. Memory allocated in previous contexts |
370 | will not be collected while the new context is active. */ | |
371 | ||
05513b45 | 372 | void |
71661611 | 373 | ggc_push_context () |
05513b45 | 374 | { |
71661611 | 375 | G.context++; |
05513b45 | 376 | |
71661611 | 377 | /* We only allocated 7 bits in the node for the context. This |
378 | should be more than enough. */ | |
379 | if (G.context >= 128) | |
380 | abort (); | |
05513b45 | 381 | } |
382 | ||
71661611 | 383 | /* Finish a GC context. Any uncollected memory in the new context |
384 | will be merged with the old context. */ | |
e3691812 | 385 | |
3cfec666 | 386 | void |
71661611 | 387 | ggc_pop_context () |
e3691812 | 388 | { |
71661611 | 389 | G.context--; |
390 | if (G.root) | |
391 | ggc_pop_context_1 (G.root, G.context); | |
e3691812 | 392 | } |
393 | ||
71661611 | 394 | static void |
395 | ggc_pop_context_1 (x, c) | |
396 | struct ggc_mem *x; | |
397 | int c; | |
431270dd | 398 | { |
71661611 | 399 | if (x->context > c) |
400 | x->context = c; | |
401 | if (x->sub[0]) | |
402 | ggc_pop_context_1 (x->sub[0], c); | |
403 | if (x->sub[1]) | |
404 | ggc_pop_context_1 (x->sub[1], c); | |
431270dd | 405 | } |
406 | ||
71661611 | 407 | /* Dump a tree. */ |
05513b45 | 408 | |
409 | void | |
71661611 | 410 | debug_ggc_tree (p, indent) |
411 | struct ggc_mem *p; | |
412 | int indent; | |
05513b45 | 413 | { |
71661611 | 414 | int i; |
05513b45 | 415 | |
71661611 | 416 | if (!p) |
05513b45 | 417 | { |
71661611 | 418 | fputs ("(nil)\n", stderr); |
419 | return; | |
05513b45 | 420 | } |
05513b45 | 421 | |
71661611 | 422 | if (p->sub[0]) |
423 | debug_ggc_tree (p->sub[0], indent + 1); | |
431270dd | 424 | |
71661611 | 425 | for (i = 0; i < indent; ++i) |
426 | putc (' ', stderr); | |
2a8997e8 | 427 | fprintf (stderr, "%lx %p\n", (unsigned long)PTR_KEY (p), p); |
3cfec666 | 428 | |
71661611 | 429 | if (p->sub[1]) |
430 | debug_ggc_tree (p->sub[1], indent + 1); | |
431 | } | |
431270dd | 432 | |
71661611 | 433 | #ifdef GGC_BALANCE |
434 | /* Collect tree balance metrics */ | |
431270dd | 435 | |
71661611 | 436 | #include <math.h> |
431270dd | 437 | |
71661611 | 438 | void |
439 | debug_ggc_balance () | |
440 | { | |
441 | size_t nleaf, sumdepth; | |
431270dd | 442 | |
71661611 | 443 | nleaf = sumdepth = 0; |
444 | tally_leaves (G.root, 0, &nleaf, &sumdepth); | |
05513b45 | 445 | |
71661611 | 446 | fprintf (stderr, " {B %.2f,%.1f,%.1f}", |
447 | /* In a balanced tree, leaf/node should approach 1/2. */ | |
448 | (float)nleaf / (float)G.objects, | |
449 | /* In a balanced tree, average leaf depth should approach lg(n). */ | |
450 | (float)sumdepth / (float)nleaf, | |
451 | log ((double) G.objects) / M_LN2); | |
05513b45 | 452 | } |
2a8997e8 | 453 | #endif |
05513b45 | 454 | |
2a8997e8 | 455 | /* Used by debug_ggc_balance, and also by ggc_print_statistics. */ |
71661611 | 456 | static void |
457 | tally_leaves (x, depth, nleaf, sumdepth) | |
458 | struct ggc_mem *x; | |
459 | int depth; | |
460 | size_t *nleaf; | |
461 | size_t *sumdepth; | |
05513b45 | 462 | { |
71661611 | 463 | if (! x->sub[0] && !x->sub[1]) |
464 | { | |
465 | *nleaf += 1; | |
466 | *sumdepth += depth; | |
467 | } | |
468 | else | |
05513b45 | 469 | { |
71661611 | 470 | if (x->sub[0]) |
471 | tally_leaves (x->sub[0], depth + 1, nleaf, sumdepth); | |
472 | if (x->sub[1]) | |
473 | tally_leaves (x->sub[1], depth + 1, nleaf, sumdepth); | |
05513b45 | 474 | } |
05513b45 | 475 | } |
2a8997e8 | 476 | |
477 | #define SCALE(x) ((unsigned long) ((x) < 1024*10 \ | |
478 | ? (x) \ | |
479 | : ((x) < 1024*1024*10 \ | |
480 | ? (x) / 1024 \ | |
481 | : (x) / (1024*1024)))) | |
482 | #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M')) | |
483 | ||
484 | /* Report on GC memory usage. */ | |
485 | void | |
486 | ggc_print_statistics () | |
487 | { | |
488 | struct ggc_statistics stats; | |
489 | size_t nleaf = 0, sumdepth = 0; | |
490 | ||
491 | /* Clear the statistics. */ | |
492 | memset (&stats, 0, sizeof (stats)); | |
3cfec666 | 493 | |
2a8997e8 | 494 | /* Make sure collection will really occur. */ |
495 | G.allocated_last_gc = 0; | |
496 | ||
497 | /* Collect and print the statistics common across collectors. */ | |
498 | ggc_print_common_statistics (stderr, &stats); | |
499 | ||
500 | /* Report on tree balancing. */ | |
501 | tally_leaves (G.root, 0, &nleaf, &sumdepth); | |
502 | ||
503 | fprintf (stderr, "\n\ | |
504 | Total internal data (bytes)\t%ld%c\n\ | |
505 | Number of leaves in tree\t%d\n\ | |
506 | Average leaf depth\t\t%.1f\n", | |
507 | SCALE(G.objects * offsetof (struct ggc_mem, u)), | |
508 | LABEL(G.objects * offsetof (struct ggc_mem, u)), | |
509 | nleaf, (double)sumdepth / (double)nleaf); | |
510 | ||
511 | /* Report overall memory usage. */ | |
512 | fprintf (stderr, "\n\ | |
513 | Total objects allocated\t\t%d\n\ | |
514 | Total memory in GC arena\t%ld%c\n", | |
515 | G.objects, | |
516 | SCALE(G.allocated), LABEL(G.allocated)); | |
517 | } |