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