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 #ifndef HOST_BITS_PER_PTR
  56 #define HOST_BITS_PER_PTR  HOST_BITS_PER_LONG
  57 #endif
  58
  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.
  62
  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.
  68
  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.  */
  73
  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)
  77
  78 /* GC'able memory; a node in a binary search tree.  */
  79
  80 struct ggc_mem
  81 {
  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;
  88
  89   /* Make sure the data is reasonably aligned.  */
  90   union {
  91     HOST_WIDEST_INT i;
  92 #ifdef HAVE_LONG_DOUBLE
  93     long double d;
  94 #else
  95     double d;
  96 #endif
  97   } u;
  98 };
  99
 100 static struct globals
 101 {
 102   /* Root of the object tree.  */
 103   struct ggc_mem *root;
 104
 105   /* Data bytes currently allocated.  */
 106   size_t allocated;
 107
 108   /* Data objects currently allocated.  */
 109   size_t objects;
 110
 111   /* Data bytes allocated at time of last GC.  */
 112   size_t allocated_last_gc;
 113
 114   /* Current context level.  */
 115   int context;
 116 } G;
 117
 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)
 123
 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)
 127
 128 /* Local function prototypes.  */
 129
 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));
 135
 136 /* For use from debugger.  */
 137 extern void debug_ggc_tree PARAMS ((struct ggc_mem *, int));
 138
 139 #ifdef GGC_BALANCE
 140 extern void debug_ggc_balance PARAMS ((void));
 141 #endif
 142 static void tally_leaves PARAMS ((struct ggc_mem *, int, size_t *, size_t *));
 143
 144 /* Insert V into the search tree.  */
 145
 146 static inline void
 147 tree_insert (v)
 148      struct ggc_mem *v;
 149 {
 150   size_t v_key = PTR_KEY (v);
 151   struct ggc_mem *p, **pp;
 152
 153   for (pp = &G.root, p = *pp; p ; p = *pp)
 154     {
 155       size_t p_key = PTR_KEY (p);
 156       pp = &p->sub[v_key < p_key];
 157     }
 158   *pp = v;
 159 }
 160
 161 /* Return true if V is in the tree.  */
 162
 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;
 169
 170   while (p)
 171     {
 172       size_t p_key = PTR_KEY (p);
 173       if (p == v)
 174         return 1;
 175       p = p->sub[v_key < p_key];
 176     }
 177
 178   return 0;
 179 }
 180
 181 /* Alloc SIZE bytes of GC'able memory.  If ZERO, clear the memory.  */
 182
 183 void *
 184 ggc_alloc (size)
 185      size_t size;
 186 {
 187   struct ggc_mem *x;
 188
 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;
 195
 196 #ifdef GGC_POISON
 197   memset (&x->u, 0xaf, size);
 198 #endif
 199
 200   tree_insert (x);
 201   G.allocated += size;
 202   G.objects += 1;
 203
 204   return &x->u;
 205 }
 206
 207 /* Mark a node.  */
 208
 209 int
 210 ggc_set_mark (p)
 211      const void *p;
 212 {
 213   struct ggc_mem *x;
 214
 215   x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
 216 #ifdef GGC_ALWAYS_VERIFY
 217   if (! tree_lookup (x))
 218     abort ();
 219 #endif
 220
 221   if (x->mark)
 222     return 1;
 223
 224   x->mark = 1;
 225   G.allocated += x->size;
 226   G.objects += 1;
 227
 228   return 0;
 229 }
 230
 231 /* Mark a node, but check first to see that it's really gc-able memory.  */
 232
 233 void
 234 ggc_mark_if_gcable (p)
 235      const void *p;
 236 {
 237   struct ggc_mem *x;
 238
 239   if (p == NULL)
 240     return;
 241
 242   x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
 243   if (! tree_lookup (x))
 244     return;
 245
 246   if (x->mark)
 247     return;
 248
 249   x->mark = 1;
 250   G.allocated += x->size;
 251   G.objects += 1;
 252 }
 253
 254 /* Return the size of the gc-able object P.  */
 255
 256 size_t
 257 ggc_get_size (p)
 258      const void *p;
 259 {
 260   struct ggc_mem *x
 261     = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
 262   return x->size;
 263 }
 264
 265 /* Unmark all objects.  */
 266
 267 static void
 268 clear_marks (x)
 269      struct ggc_mem *x;
 270 {
 271   x->mark = 0;
 272   if (x->sub[0])
 273     clear_marks (x->sub[0]);
 274   if (x->sub[1])
 275     clear_marks (x->sub[1]);
 276 }
 277
 278 /* Free all objects in the current context that are not marked.  */
 279
 280 static void
 281 sweep_objs (root)
 282      struct ggc_mem **root;
 283 {
 284   struct ggc_mem *x = *root;
 285   if (!x)
 286     return;
 287
 288   sweep_objs (&x->sub[0]);
 289   sweep_objs (&x->sub[1]);
 290
 291   if (! x->mark && x->context >= G.context)
 292     {
 293       struct ggc_mem *l, *r;
 294
 295       l = x->sub[0];
 296       r = x->sub[1];
 297       if (!l)
 298         *root = r;
 299       else if (!r)
 300         *root = l;
 301       else if (!l->sub[1])
 302         {
 303           *root = l;
 304           l->sub[1] = r;
 305         }
 306       else if (!r->sub[0])
 307         {
 308           *root = r;
 309           r->sub[0] = l;
 310         }
 311       else
 312         {
 313           *root = l;
 314           do {
 315             root = &l->sub[1];
 316           } while ((l = *root) != NULL);
 317           *root = r;
 318         }
 319
 320 #ifdef GGC_POISON
 321       memset (&x->u, 0xA5, x->size);
 322 #endif
 323
 324       free (x);
 325     }
 326 }
 327
 328 /* The top level mark-and-sweep routine.  */
 329
 330 void
 331 ggc_collect ()
 332 {
 333 #ifndef GGC_ALWAYS_COLLECT
 334   if (G.allocated < GGC_MIN_EXPAND_FOR_GC * G.allocated_last_gc)
 335     return;
 336 #endif
 337
 338 #ifdef GGC_BALANCE
 339   debug_ggc_balance ();
 340 #endif
 341
 342   timevar_push (TV_GC);
 343   if (!quiet_flag)
 344     fprintf (stderr, " {GC %luk -> ", (unsigned long)G.allocated / 1024);
 345
 346   G.allocated = 0;
 347   G.objects = 0;
 348
 349   clear_marks (G.root);
 350   ggc_mark_roots ();
 351   sweep_objs (&G.root);
 352
 353   G.allocated_last_gc = G.allocated;
 354   if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED)
 355     G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
 356
 357   timevar_pop (TV_GC);
 358
 359   if (!quiet_flag)
 360     fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
 361
 362 #ifdef GGC_BALANCE
 363   debug_ggc_balance ();
 364 #endif
 365 }
 366
 367 /* Called once to initialize the garbage collector.  */
 368
 369 void
 370 init_ggc ()
 371 {
 372   G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
 373 }
 374
 375 /* Start a new GGC context.  Memory allocated in previous contexts
 376    will not be collected while the new context is active.  */
 377
 378 void
 379 ggc_push_context ()
 380 {
 381   G.context++;
 382
 383   /* We only allocated 7 bits in the node for the context.  This
 384      should be more than enough.  */
 385   if (G.context >= 128)
 386     abort ();
 387 }
 388
 389 /* Finish a GC context.  Any uncollected memory in the new context
 390    will be merged with the old context.  */
 391
 392 void
 393 ggc_pop_context ()
 394 {
 395   G.context--;
 396   if (G.root)
 397     ggc_pop_context_1 (G.root, G.context);
 398 }
 399
 400 static void
 401 ggc_pop_context_1 (x, c)
 402      struct ggc_mem *x;
 403      int c;
 404 {
 405   if (x->context > c)
 406     x->context = c;
 407   if (x->sub[0])
 408     ggc_pop_context_1 (x->sub[0], c);
 409   if (x->sub[1])
 410     ggc_pop_context_1 (x->sub[1], c);
 411 }
 412
 413 /* Dump a tree.  */
 414
 415 void
 416 debug_ggc_tree (p, indent)
 417      struct ggc_mem *p;
 418      int indent;
 419 {
 420   int i;
 421
 422   if (!p)
 423     {
 424       fputs ("(nil)\n", stderr);
 425       return;
 426     }
 427
 428   if (p->sub[0])
 429     debug_ggc_tree (p->sub[0], indent + 1);
 430
 431   for (i = 0; i < indent; ++i)
 432     putc (' ', stderr);
 433   fprintf (stderr, "%lx %p\n", (unsigned long)PTR_KEY (p), p);
 434
 435   if (p->sub[1])
 436     debug_ggc_tree (p->sub[1], indent + 1);
 437 }
 438
 439 #ifdef GGC_BALANCE
 440 /* Collect tree balance metrics  */
 441
 442 #include <math.h>
 443
 444 void
 445 debug_ggc_balance ()
 446 {
 447   size_t nleaf, sumdepth;
 448
 449   nleaf = sumdepth = 0;
 450   tally_leaves (G.root, 0, &nleaf, &sumdepth);
 451
 452   fprintf (stderr, " {B %.2f,%.1f,%.1f}",
 453            /* In a balanced tree, leaf/node should approach 1/2.  */
 454            (float)nleaf / (float)G.objects,
 455            /* In a balanced tree, average leaf depth should approach lg(n).  */
 456            (float)sumdepth / (float)nleaf,
 457            log ((double) G.objects) / M_LN2);
 458 }
 459 #endif
 460
 461 /* Used by debug_ggc_balance, and also by ggc_print_statistics.  */
 462 static void
 463 tally_leaves (x, depth, nleaf, sumdepth)
 464      struct ggc_mem *x;
 465      int depth;
 466      size_t *nleaf;
 467      size_t *sumdepth;
 468 {
 469   if (! x->sub[0] && !x->sub[1])
 470     {
 471       *nleaf += 1;
 472       *sumdepth += depth;
 473     }
 474   else
 475     {
 476       if (x->sub[0])
 477         tally_leaves (x->sub[0], depth + 1, nleaf, sumdepth);
 478       if (x->sub[1])
 479         tally_leaves (x->sub[1], depth + 1, nleaf, sumdepth);
 480     }
 481 }
 482
 483 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 484                   ? (x) \
 485                   : ((x) < 1024*1024*10 \
 486                      ? (x) / 1024 \
 487                      : (x) / (1024*1024))))
 488 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 489
 490 /* Report on GC memory usage.  */
 491 void
 492 ggc_print_statistics ()
 493 {
 494   struct ggc_statistics stats;
 495   size_t nleaf = 0, sumdepth = 0;
 496
 497   /* Clear the statistics.  */
 498   memset (&stats, 0, sizeof (stats));
 499
 500   /* Make sure collection will really occur.  */
 501   G.allocated_last_gc = 0;
 502
 503   /* Collect and print the statistics common across collectors.  */
 504   ggc_print_common_statistics (stderr, &stats);
 505
 506   /* Report on tree balancing.  */
 507   tally_leaves (G.root, 0, &nleaf, &sumdepth);
 508
 509   fprintf (stderr, "\n\
 510 Total internal data (bytes)\t%ld%c\n\
 511 Number of leaves in tree\t%d\n\
 512 Average leaf depth\t\t%.1f\n",
 513            SCALE(G.objects * offsetof (struct ggc_mem, u)),
 514            LABEL(G.objects * offsetof (struct ggc_mem, u)),
 515            nleaf, (double)sumdepth / (double)nleaf);
 516
 517   /* Report overall memory usage.  */
 518   fprintf (stderr, "\n\
 519 Total objects allocated\t\t%d\n\
 520 Total memory in GC arena\t%ld%c\n",
 521            G.objects,
 522            SCALE(G.allocated), LABEL(G.allocated));
 523 }