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 (size)
 186      size_t size;
 187 {
 188   struct ggc_mem *x;
 189
 190   x = (struct ggc_mem *) xmalloc (offsetof (struct ggc_mem, u) + size);
 191   x->sub[0] = NULL;
 192   x->sub[1] = NULL;
 193   x->mark = 0;
 194   x->context = G.context;
 195   x->size = size;
 196
 197 #ifdef GGC_POISON
 198   memset (&x->u, 0xaf, size);
 199 #endif
 200
 201   tree_insert (x);
 202   G.allocated += size;
 203   G.objects += 1;
 204
 205   return &x->u;
 206 }
 207
 208 /* Mark a node.  */
 209
 210 int
 211 ggc_set_mark (p)
 212      const void *p;
 213 {
 214   struct ggc_mem *x;
 215
 216   x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
 217 #ifdef GGC_ALWAYS_VERIFY
 218   if (! tree_lookup (x))
 219     abort ();
 220 #endif
 221
 222   if (x->mark)
 223     return 1;
 224
 225   x->mark = 1;
 226   G.allocated += x->size;
 227   G.objects += 1;
 228
 229   return 0;
 230 }
 231
 232 /* Mark a node, but check first to see that it's really gc-able memory.  */
 233
 234 void
 235 ggc_mark_if_gcable (p)
 236      const void *p;
 237 {
 238   struct ggc_mem *x;
 239
 240   if (p == NULL)
 241     return;
 242
 243   x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
 244   if (! tree_lookup (x))
 245     return;
 246
 247   if (x->mark)
 248     return;
 249
 250   x->mark = 1;
 251   G.allocated += x->size;
 252   G.objects += 1;
 253 }
 254
 255 /* Return the size of the gc-able object P.  */
 256
 257 size_t
 258 ggc_get_size (p)
 259      const void *p;
 260 {
 261   struct ggc_mem *x
 262     = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
 263   return x->size;
 264 }
 265
 266 /* Unmark all objects.  */
 267
 268 static void
 269 clear_marks (x)
 270      struct ggc_mem *x;
 271 {
 272   x->mark = 0;
 273   if (x->sub[0])
 274     clear_marks (x->sub[0]);
 275   if (x->sub[1])
 276     clear_marks (x->sub[1]);
 277 }
 278
 279 /* Free all objects in the current context that are not marked.  */
 280
 281 static void
 282 sweep_objs (root)
 283      struct ggc_mem **root;
 284 {
 285   struct ggc_mem *x = *root;
 286   if (!x)
 287     return;
 288
 289   sweep_objs (&x->sub[0]);
 290   sweep_objs (&x->sub[1]);
 291
 292   if (! x->mark && x->context >= G.context)
 293     {
 294       struct ggc_mem *l, *r;
 295
 296       l = x->sub[0];
 297       r = x->sub[1];
 298       if (!l)
 299         *root = r;
 300       else if (!r)
 301         *root = l;
 302       else if (!l->sub[1])
 303         {
 304           *root = l;
 305           l->sub[1] = r;
 306         }
 307       else if (!r->sub[0])
 308         {
 309           *root = r;
 310           r->sub[0] = l;
 311         }
 312       else
 313         {
 314           *root = l;
 315           do {
 316             root = &l->sub[1];
 317           } while ((l = *root) != NULL);
 318           *root = r;
 319         }
 320
 321 #ifdef GGC_POISON
 322       memset (&x->u, 0xA5, x->size);
 323 #endif
 324
 325       free (x);
 326     }
 327 }
 328
 329 /* The top level mark-and-sweep routine.  */
 330
 331 void
 332 ggc_collect ()
 333 {
 334 #ifndef GGC_ALWAYS_COLLECT
 335   if (G.allocated < GGC_MIN_EXPAND_FOR_GC * G.allocated_last_gc)
 336     return;
 337 #endif
 338
 339 #ifdef GGC_BALANCE
 340   debug_ggc_balance ();
 341 #endif
 342
 343   timevar_push (TV_GC);
 344   if (!quiet_flag)
 345     fprintf (stderr, " {GC %luk -> ", (unsigned long)G.allocated / 1024);
 346
 347   G.allocated = 0;
 348   G.objects = 0;
 349
 350   clear_marks (G.root);
 351   ggc_mark_roots ();
 352   sweep_objs (&G.root);
 353
 354   G.allocated_last_gc = G.allocated;
 355   if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED)
 356     G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
 357
 358   timevar_pop (TV_GC);
 359
 360   if (!quiet_flag)
 361     fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
 362
 363 #ifdef GGC_BALANCE
 364   debug_ggc_balance ();
 365 #endif
 366 }
 367
 368 /* Called once to initialize the garbage collector.  */
 369
 370 void
 371 init_ggc ()
 372 {
 373   G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
 374
 375   empty_string = ggc_alloc_string ("", 0);
 376   ggc_add_string_root (&empty_string, 1);
 377 }
 378
 379 /* Start a new GGC context.  Memory allocated in previous contexts
 380    will not be collected while the new context is active.  */
 381
 382 void
 383 ggc_push_context ()
 384 {
 385   G.context++;
 386
 387   /* We only allocated 7 bits in the node for the context.  This
 388      should be more than enough.  */
 389   if (G.context >= 128)
 390     abort ();
 391 }
 392
 393 /* Finish a GC context.  Any uncollected memory in the new context
 394    will be merged with the old context.  */
 395
 396 void
 397 ggc_pop_context ()
 398 {
 399   G.context--;
 400   if (G.root)
 401     ggc_pop_context_1 (G.root, G.context);
 402 }
 403
 404 static void
 405 ggc_pop_context_1 (x, c)
 406      struct ggc_mem *x;
 407      int c;
 408 {
 409   if (x->context > c)
 410     x->context = c;
 411   if (x->sub[0])
 412     ggc_pop_context_1 (x->sub[0], c);
 413   if (x->sub[1])
 414     ggc_pop_context_1 (x->sub[1], c);
 415 }
 416
 417 /* Dump a tree.  */
 418
 419 void
 420 debug_ggc_tree (p, indent)
 421      struct ggc_mem *p;
 422      int indent;
 423 {
 424   int i;
 425
 426   if (!p)
 427     {
 428       fputs ("(nil)\n", stderr);
 429       return;
 430     }
 431
 432   if (p->sub[0])
 433     debug_ggc_tree (p->sub[0], indent + 1);
 434
 435   for (i = 0; i < indent; ++i)
 436     putc (' ', stderr);
 437   fprintf (stderr, "%lx %p\n", PTR_KEY (p), p);
 438
 439   if (p->sub[1])
 440     debug_ggc_tree (p->sub[1], indent + 1);
 441 }
 442
 443 #ifdef GGC_BALANCE
 444 /* Collect tree balance metrics  */
 445
 446 #include <math.h>
 447
 448 void
 449 debug_ggc_balance ()
 450 {
 451   size_t nleaf, sumdepth;
 452
 453   nleaf = sumdepth = 0;
 454   tally_leaves (G.root, 0, &nleaf, &sumdepth);
 455
 456   fprintf (stderr, " {B %.2f,%.1f,%.1f}",
 457            /* In a balanced tree, leaf/node should approach 1/2.  */
 458            (float)nleaf / (float)G.objects,
 459            /* In a balanced tree, average leaf depth should approach lg(n).  */
 460            (float)sumdepth / (float)nleaf,
 461            log ((double) G.objects) / M_LN2);
 462 }
 463
 464 static void
 465 tally_leaves (x, depth, nleaf, sumdepth)
 466      struct ggc_mem *x;
 467      int depth;
 468      size_t *nleaf;
 469      size_t *sumdepth;
 470 {
 471   if (! x->sub[0] && !x->sub[1])
 472     {
 473       *nleaf += 1;
 474       *sumdepth += depth;
 475     }
 476   else
 477     {
 478       if (x->sub[0])
 479         tally_leaves (x->sub[0], depth + 1, nleaf, sumdepth);
 480       if (x->sub[1])
 481         tally_leaves (x->sub[1], depth + 1, nleaf, sumdepth);
 482     }
 483 }
 484 #endif