gcc/ggc-simple.c

   1 /* Simple garbage collection for the GNU compiler.
   2    Copyright (C) 1998, 1999, 2000, 2001 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 /* Return the size of the gc-able object P.  */
 232
 233 size_t
 234 ggc_get_size (p)
 235      const void *p;
 236 {
 237   struct ggc_mem *x
 238     = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
 239   return x->size;
 240 }
 241
 242 /* Unmark all objects.  */
 243
 244 static void
 245 clear_marks (x)
 246      struct ggc_mem *x;
 247 {
 248   x->mark = 0;
 249   if (x->sub[0])
 250     clear_marks (x->sub[0]);
 251   if (x->sub[1])
 252     clear_marks (x->sub[1]);
 253 }
 254
 255 /* Free all objects in the current context that are not marked.  */
 256
 257 static void
 258 sweep_objs (root)
 259      struct ggc_mem **root;
 260 {
 261   struct ggc_mem *x = *root;
 262   if (!x)
 263     return;
 264
 265   sweep_objs (&x->sub[0]);
 266   sweep_objs (&x->sub[1]);
 267
 268   if (! x->mark && x->context >= G.context)
 269     {
 270       struct ggc_mem *l, *r;
 271
 272       l = x->sub[0];
 273       r = x->sub[1];
 274       if (!l)
 275         *root = r;
 276       else if (!r)
 277         *root = l;
 278       else if (!l->sub[1])
 279         {
 280           *root = l;
 281           l->sub[1] = r;
 282         }
 283       else if (!r->sub[0])
 284         {
 285           *root = r;
 286           r->sub[0] = l;
 287         }
 288       else
 289         {
 290           *root = l;
 291           do {
 292             root = &l->sub[1];
 293           } while ((l = *root) != NULL);
 294           *root = r;
 295         }
 296
 297 #ifdef GGC_POISON
 298       memset (&x->u, 0xA5, x->size);
 299 #endif
 300
 301       free (x);
 302     }
 303 }
 304
 305 /* The top level mark-and-sweep routine.  */
 306
 307 void
 308 ggc_collect ()
 309 {
 310 #ifndef GGC_ALWAYS_COLLECT
 311   if (G.allocated < GGC_MIN_EXPAND_FOR_GC * G.allocated_last_gc)
 312     return;
 313 #endif
 314
 315 #ifdef GGC_BALANCE
 316   debug_ggc_balance ();
 317 #endif
 318
 319   timevar_push (TV_GC);
 320   if (!quiet_flag)
 321     fprintf (stderr, " {GC %luk -> ", (unsigned long)G.allocated / 1024);
 322
 323   G.allocated = 0;
 324   G.objects = 0;
 325
 326   clear_marks (G.root);
 327   ggc_mark_roots ();
 328   sweep_objs (&G.root);
 329
 330   G.allocated_last_gc = G.allocated;
 331   if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED)
 332     G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
 333
 334   timevar_pop (TV_GC);
 335
 336   if (!quiet_flag)
 337     fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
 338
 339 #ifdef GGC_BALANCE
 340   debug_ggc_balance ();
 341 #endif
 342 }
 343
 344 /* Called once to initialize the garbage collector.  */
 345
 346 void
 347 init_ggc ()
 348 {
 349   G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
 350 }
 351
 352 /* Start a new GGC context.  Memory allocated in previous contexts
 353    will not be collected while the new context is active.  */
 354
 355 void
 356 ggc_push_context ()
 357 {
 358   G.context++;
 359
 360   /* We only allocated 7 bits in the node for the context.  This
 361      should be more than enough.  */
 362   if (G.context >= 128)
 363     abort ();
 364 }
 365
 366 /* Finish a GC context.  Any uncollected memory in the new context
 367    will be merged with the old context.  */
 368
 369 void
 370 ggc_pop_context ()
 371 {
 372   G.context--;
 373   if (G.root)
 374     ggc_pop_context_1 (G.root, G.context);
 375 }
 376
 377 static void
 378 ggc_pop_context_1 (x, c)
 379      struct ggc_mem *x;
 380      int c;
 381 {
 382   if (x->context > c)
 383     x->context = c;
 384   if (x->sub[0])
 385     ggc_pop_context_1 (x->sub[0], c);
 386   if (x->sub[1])
 387     ggc_pop_context_1 (x->sub[1], c);
 388 }
 389
 390 /* Dump a tree.  */
 391
 392 void
 393 debug_ggc_tree (p, indent)
 394      struct ggc_mem *p;
 395      int indent;
 396 {
 397   int i;
 398
 399   if (!p)
 400     {
 401       fputs ("(nil)\n", stderr);
 402       return;
 403     }
 404
 405   if (p->sub[0])
 406     debug_ggc_tree (p->sub[0], indent + 1);
 407
 408   for (i = 0; i < indent; ++i)
 409     putc (' ', stderr);
 410   fprintf (stderr, "%lx %p\n", (unsigned long)PTR_KEY (p), p);
 411
 412   if (p->sub[1])
 413     debug_ggc_tree (p->sub[1], indent + 1);
 414 }
 415
 416 #ifdef GGC_BALANCE
 417 /* Collect tree balance metrics  */
 418
 419 #include <math.h>
 420
 421 void
 422 debug_ggc_balance ()
 423 {
 424   size_t nleaf, sumdepth;
 425
 426   nleaf = sumdepth = 0;
 427   tally_leaves (G.root, 0, &nleaf, &sumdepth);
 428
 429   fprintf (stderr, " {B %.2f,%.1f,%.1f}",
 430            /* In a balanced tree, leaf/node should approach 1/2.  */
 431            (float)nleaf / (float)G.objects,
 432            /* In a balanced tree, average leaf depth should approach lg(n).  */
 433            (float)sumdepth / (float)nleaf,
 434            log ((double) G.objects) / M_LN2);
 435 }
 436 #endif
 437
 438 /* Used by debug_ggc_balance, and also by ggc_print_statistics.  */
 439 static void
 440 tally_leaves (x, depth, nleaf, sumdepth)
 441      struct ggc_mem *x;
 442      int depth;
 443      size_t *nleaf;
 444      size_t *sumdepth;
 445 {
 446   if (! x->sub[0] && !x->sub[1])
 447     {
 448       *nleaf += 1;
 449       *sumdepth += depth;
 450     }
 451   else
 452     {
 453       if (x->sub[0])
 454         tally_leaves (x->sub[0], depth + 1, nleaf, sumdepth);
 455       if (x->sub[1])
 456         tally_leaves (x->sub[1], depth + 1, nleaf, sumdepth);
 457     }
 458 }
 459
 460 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 461                   ? (x) \
 462                   : ((x) < 1024*1024*10 \
 463                      ? (x) / 1024 \
 464                      : (x) / (1024*1024))))
 465 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 466
 467 /* Report on GC memory usage.  */
 468 void
 469 ggc_print_statistics ()
 470 {
 471   struct ggc_statistics stats;
 472   size_t nleaf = 0, sumdepth = 0;
 473
 474   /* Clear the statistics.  */
 475   memset (&stats, 0, sizeof (stats));
 476
 477   /* Make sure collection will really occur.  */
 478   G.allocated_last_gc = 0;
 479
 480   /* Collect and print the statistics common across collectors.  */
 481   ggc_print_common_statistics (stderr, &stats);
 482
 483   /* Report on tree balancing.  */
 484   tally_leaves (G.root, 0, &nleaf, &sumdepth);
 485
 486   fprintf (stderr, "\n\
 487 Total internal data (bytes)\t%ld%c\n\
 488 Number of leaves in tree\t%d\n\
 489 Average leaf depth\t\t%.1f\n",
 490            SCALE(G.objects * offsetof (struct ggc_mem, u)),
 491            LABEL(G.objects * offsetof (struct ggc_mem, u)),
 492            nleaf, (double)sumdepth / (double)nleaf);
 493
 494   /* Report overall memory usage.  */
 495   fprintf (stderr, "\n\
 496 Total objects allocated\t\t%d\n\
 497 Total memory in GC arena\t%ld%c\n",
 498            G.objects,
 499            SCALE(G.allocated), LABEL(G.allocated));
 500 }