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