gcc/ggc-simple.c

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