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