gcc/ggc-simple.c

   1 /* Simple garbage collection for the GNU compiler.
   2    Copyright (C) 1998, 1999, 2000, 2001, 2002 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 "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "tree.h"
  27 #include "tm_p.h"
  28 #include "flags.h"
  29 #include "varray.h"
  30 #include "ggc.h"
  31 #include "toplev.h"
  32 #include "timevar.h"
  33 #include "params.h"
  34
  35 /* Debugging flags.  */
  36
  37 /* Zap memory before freeing to catch dangling pointers.  */
  38 #undef GGC_POISON
  39
  40 /* Collect statistics on how bushy the search tree is.  */
  41 #undef GGC_BALANCE
  42
  43 /* Always verify that the to-be-marked memory is collectable.  */
  44 #undef GGC_ALWAYS_VERIFY
  45
  46 #ifdef ENABLE_GC_CHECKING
  47 #define GGC_POISON
  48 #define GGC_ALWAYS_VERIFY
  49 #endif
  50
  51 #ifndef HOST_BITS_PER_PTR
  52 #define HOST_BITS_PER_PTR  HOST_BITS_PER_LONG
  53 #endif
  54
  55 /* We'd like a balanced tree, but we don't really want to pay for the
  56    cost of keeping the tree balanced.  We'll settle for the next best
  57    thing -- nearly balanced.
  58
  59    In this context, the most natural key is the node pointer itself,
  60    but due to the way memory managers work, we'd be virtually certain
  61    to wind up with a completely degenerate straight line.  What's needed
  62    is to make something more variable, and yet predictable, be more
  63    significant in the comparison.
  64
  65    The handiest source of variability is the low bits of the pointer
  66    value itself.  Any sort of bit/byte swap would do, but such machine
  67    specific operations are not handy, and we don't want to put that much
  68    effort into it.  */
  69
  70 #define PTR_KEY(p)      ((size_t)p << (HOST_BITS_PER_PTR - 8)               \
  71                          | ((size_t)p & 0xff00) << (HOST_BITS_PER_PTR - 24) \
  72                          | (size_t)p >> 16)
  73
  74 /* GC'able memory; a node in a binary search tree.  */
  75
  76 struct ggc_mem
  77 {
  78   /* A combination of the standard left/right nodes, indexable by `<'.  */
  79   struct ggc_mem *sub[2];
  80
  81   unsigned int mark : 1;
  82   unsigned int context : 7;
  83   unsigned int size : 24;
  84
  85   /* Make sure the data is reasonably aligned.  */
  86   union {
  87     HOST_WIDEST_INT i;
  88 #ifdef HAVE_LONG_DOUBLE
  89     long double d;
  90 #else
  91     double d;
  92 #endif
  93   } u;
  94 };
  95
  96 static struct globals
  97 {
  98   /* Root of the object tree.  */
  99   struct ggc_mem *root;
 100
 101   /* Data bytes currently allocated.  */
 102   size_t allocated;
 103
 104   /* Data objects currently allocated.  */
 105   size_t objects;
 106
 107   /* Data bytes allocated at time of last GC.  */
 108   size_t allocated_last_gc;
 109
 110   /* Current context level.  */
 111   int context;
 112 } G;
 113
 114 /* Local function prototypes.  */
 115
 116 static void tree_insert PARAMS ((struct ggc_mem *));
 117 static int tree_lookup PARAMS ((struct ggc_mem *));
 118 static void clear_marks PARAMS ((struct ggc_mem *));
 119 static void sweep_objs PARAMS ((struct ggc_mem **));
 120 static void ggc_pop_context_1 PARAMS ((struct ggc_mem *, int));
 121
 122 /* For use from debugger.  */
 123 extern void debug_ggc_tree PARAMS ((struct ggc_mem *, int));
 124
 125 #ifdef GGC_BALANCE
 126 extern void debug_ggc_balance PARAMS ((void));
 127 #endif
 128 static void tally_leaves PARAMS ((struct ggc_mem *, int, size_t *, size_t *));
 129
 130 /* Insert V into the search tree.  */
 131
 132 static inline void
 133 tree_insert (v)
 134      struct ggc_mem *v;
 135 {
 136   size_t v_key = PTR_KEY (v);
 137   struct ggc_mem *p, **pp;
 138
 139   for (pp = &G.root, p = *pp; p ; p = *pp)
 140     {
 141       size_t p_key = PTR_KEY (p);
 142       pp = &p->sub[v_key < p_key];
 143     }
 144   *pp = v;
 145 }
 146
 147 /* Return true if V is in the tree.  */
 148
 149 static inline int
 150 tree_lookup (v)
 151      struct ggc_mem *v;
 152 {
 153   size_t v_key = PTR_KEY (v);
 154   struct ggc_mem *p = G.root;
 155
 156   while (p)
 157     {
 158       size_t p_key = PTR_KEY (p);
 159       if (p == v)
 160         return 1;
 161       p = p->sub[v_key < p_key];
 162     }
 163
 164   return 0;
 165 }
 166
 167 /* Alloc SIZE bytes of GC'able memory.  If ZERO, clear the memory.  */
 168
 169 void *
 170 ggc_alloc (size)
 171      size_t size;
 172 {
 173   struct ggc_mem *x;
 174
 175   x = (struct ggc_mem *) xmalloc (offsetof (struct ggc_mem, u) + size);
 176   x->sub[0] = NULL;
 177   x->sub[1] = NULL;
 178   x->mark = 0;
 179   x->context = G.context;
 180   x->size = size;
 181
 182 #ifdef GGC_POISON
 183   memset (&x->u, 0xaf, size);
 184 #endif
 185
 186   tree_insert (x);
 187   G.allocated += size;
 188   G.objects += 1;
 189
 190   return &x->u;
 191 }
 192
 193 /* Mark a node.  */
 194
 195 int
 196 ggc_set_mark (p)
 197      const void *p;
 198 {
 199   struct ggc_mem *x;
 200
 201   x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
 202 #ifdef GGC_ALWAYS_VERIFY
 203   if (! tree_lookup (x))
 204     abort ();
 205 #endif
 206
 207   if (x->mark)
 208     return 1;
 209
 210   x->mark = 1;
 211   G.allocated += x->size;
 212   G.objects += 1;
 213
 214   return 0;
 215 }
 216
 217 /* Return 1 if P has been marked, zero otherwise.  */
 218
 219 int
 220 ggc_marked_p (p)
 221      const void *p;
 222 {
 223   struct ggc_mem *x;
 224
 225   x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
 226 #ifdef GGC_ALWAYS_VERIFY
 227   if (! tree_lookup (x))
 228     abort ();
 229 #endif
 230
 231    return x->mark;
 232 }
 233
 234 /* Return the size of the gc-able object P.  */
 235
 236 size_t
 237 ggc_get_size (p)
 238      const void *p;
 239 {
 240   struct ggc_mem *x
 241     = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
 242   return x->size;
 243 }
 244
 245 /* Unmark all objects.  */
 246
 247 static void
 248 clear_marks (x)
 249      struct ggc_mem *x;
 250 {
 251   x->mark = 0;
 252   if (x->sub[0])
 253     clear_marks (x->sub[0]);
 254   if (x->sub[1])
 255     clear_marks (x->sub[1]);
 256 }
 257
 258 /* Free all objects in the current context that are not marked.  */
 259
 260 static void
 261 sweep_objs (root)
 262      struct ggc_mem **root;
 263 {
 264   struct ggc_mem *x = *root;
 265   if (!x)
 266     return;
 267
 268   sweep_objs (&x->sub[0]);
 269   sweep_objs (&x->sub[1]);
 270
 271   if (! x->mark && x->context >= G.context)
 272     {
 273       struct ggc_mem *l, *r;
 274
 275       l = x->sub[0];
 276       r = x->sub[1];
 277       if (!l)
 278         *root = r;
 279       else if (!r)
 280         *root = l;
 281       else if (!l->sub[1])
 282         {
 283           *root = l;
 284           l->sub[1] = r;
 285         }
 286       else if (!r->sub[0])
 287         {
 288           *root = r;
 289           r->sub[0] = l;
 290         }
 291       else
 292         {
 293           *root = l;
 294           do {
 295             root = &l->sub[1];
 296           } while ((l = *root) != NULL);
 297           *root = r;
 298         }
 299
 300 #ifdef GGC_POISON
 301       memset (&x->u, 0xA5, x->size);
 302 #endif
 303
 304       free (x);
 305     }
 306 }
 307
 308 /* The top level mark-and-sweep routine.  */
 309
 310 void
 311 ggc_collect ()
 312 {
 313   /* Avoid frequent unnecessary work by skipping collection if the
 314      total allocations haven't expanded much since the last
 315      collection.  */
 316   size_t allocated_last_gc =
 317     MAX (G.allocated_last_gc, (size_t)PARAM_VALUE (GGC_MIN_HEAPSIZE) * 1024);
 318
 319   size_t min_expand = allocated_last_gc * PARAM_VALUE (GGC_MIN_EXPAND) / 100;
 320
 321   if (G.allocated < allocated_last_gc + min_expand)
 322     return;
 323
 324 #ifdef GGC_BALANCE
 325   debug_ggc_balance ();
 326 #endif
 327
 328   timevar_push (TV_GC);
 329   if (!quiet_flag)
 330     fprintf (stderr, " {GC %luk -> ", (unsigned long)G.allocated / 1024);
 331
 332   G.allocated = 0;
 333   G.objects = 0;
 334
 335   clear_marks (G.root);
 336   ggc_mark_roots ();
 337   sweep_objs (&G.root);
 338
 339   G.allocated_last_gc = G.allocated;
 340
 341   timevar_pop (TV_GC);
 342
 343   if (!quiet_flag)
 344     fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
 345
 346 #ifdef GGC_BALANCE
 347   debug_ggc_balance ();
 348 #endif
 349 }
 350
 351 /* Called once to initialize the garbage collector.  */
 352
 353 void
 354 init_ggc ()
 355 {
 356 }
 357
 358 /* Start a new GGC context.  Memory allocated in previous contexts
 359    will not be collected while the new context is active.  */
 360
 361 void
 362 ggc_push_context ()
 363 {
 364   G.context++;
 365
 366   /* We only allocated 7 bits in the node for the context.  This
 367      should be more than enough.  */
 368   if (G.context >= 128)
 369     abort ();
 370 }
 371
 372 /* Finish a GC context.  Any uncollected memory in the new context
 373    will be merged with the old context.  */
 374
 375 void
 376 ggc_pop_context ()
 377 {
 378   G.context--;
 379   if (G.root)
 380     ggc_pop_context_1 (G.root, G.context);
 381 }
 382
 383 static void
 384 ggc_pop_context_1 (x, c)
 385      struct ggc_mem *x;
 386      int c;
 387 {
 388   if (x->context > c)
 389     x->context = c;
 390   if (x->sub[0])
 391     ggc_pop_context_1 (x->sub[0], c);
 392   if (x->sub[1])
 393     ggc_pop_context_1 (x->sub[1], c);
 394 }
 395
 396 /* Dump a tree.  */
 397
 398 void
 399 debug_ggc_tree (p, indent)
 400      struct ggc_mem *p;
 401      int indent;
 402 {
 403   int i;
 404
 405   if (!p)
 406     {
 407       fputs ("(nil)\n", stderr);
 408       return;
 409     }
 410
 411   if (p->sub[0])
 412     debug_ggc_tree (p->sub[0], indent + 1);
 413
 414   for (i = 0; i < indent; ++i)
 415     putc (' ', stderr);
 416   fprintf (stderr, "%lx %p\n", (unsigned long)PTR_KEY (p), (PTR) p);
 417
 418   if (p->sub[1])
 419     debug_ggc_tree (p->sub[1], indent + 1);
 420 }
 421
 422 #ifdef GGC_BALANCE
 423 /* Collect tree balance metrics  */
 424
 425 #include <math.h>
 426
 427 void
 428 debug_ggc_balance ()
 429 {
 430   size_t nleaf, sumdepth;
 431
 432   nleaf = sumdepth = 0;
 433   tally_leaves (G.root, 0, &nleaf, &sumdepth);
 434
 435   fprintf (stderr, " {B %.2f,%.1f,%.1f}",
 436            /* In a balanced tree, leaf/node should approach 1/2.  */
 437            (float)nleaf / (float)G.objects,
 438            /* In a balanced tree, average leaf depth should approach lg(n).  */
 439            (float)sumdepth / (float)nleaf,
 440            log ((double) G.objects) / M_LN2);
 441 }
 442 #endif
 443
 444 /* Used by debug_ggc_balance, and also by ggc_print_statistics.  */
 445 static void
 446 tally_leaves (x, depth, nleaf, sumdepth)
 447      struct ggc_mem *x;
 448      int depth;
 449      size_t *nleaf;
 450      size_t *sumdepth;
 451 {
 452   if (! x->sub[0] && !x->sub[1])
 453     {
 454       *nleaf += 1;
 455       *sumdepth += depth;
 456     }
 457   else
 458     {
 459       if (x->sub[0])
 460         tally_leaves (x->sub[0], depth + 1, nleaf, sumdepth);
 461       if (x->sub[1])
 462         tally_leaves (x->sub[1], depth + 1, nleaf, sumdepth);
 463     }
 464 }
 465
 466 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 467                   ? (x) \
 468                   : ((x) < 1024*1024*10 \
 469                      ? (x) / 1024 \
 470                      : (x) / (1024*1024))))
 471 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 472
 473 /* Report on GC memory usage.  */
 474 void
 475 ggc_print_statistics ()
 476 {
 477   struct ggc_statistics stats;
 478   size_t nleaf = 0, sumdepth = 0;
 479
 480   /* Clear the statistics.  */
 481   memset (&stats, 0, sizeof (stats));
 482
 483   /* Make sure collection will really occur.  */
 484   G.allocated_last_gc = 0;
 485
 486   /* Collect and print the statistics common across collectors.  */
 487   ggc_print_common_statistics (stderr, &stats);
 488
 489   /* Report on tree balancing.  */
 490   tally_leaves (G.root, 0, &nleaf, &sumdepth);
 491
 492   fprintf (stderr, "\n\
 493 Total internal data (bytes)\t%ld%c\n\
 494 Number of leaves in tree\t%lu\n\
 495 Average leaf depth\t\t%.1f\n",
 496            SCALE(G.objects * offsetof (struct ggc_mem, u)),
 497            LABEL(G.objects * offsetof (struct ggc_mem, u)),
 498            (unsigned long)nleaf, (double)sumdepth / (double)nleaf);
 499
 500   /* Report overall memory usage.  */
 501   fprintf (stderr, "\n\
 502 Total objects allocated\t\t%ld\n\
 503 Total memory in GC arena\t%ld%c\n",
 504            (unsigned long)G.objects,
 505            SCALE(G.allocated), LABEL(G.allocated));
 506 }
 507 \f
 508 struct ggc_pch_data *
 509 init_ggc_pch ()
 510 {
 511   sorry ("Generating PCH files is not supported when using ggc-simple.c");
 512   /* It could be supported, but the code is not yet written.  */
 513   return NULL;
 514 }
 515
 516 void
 517 ggc_pch_count_object (d, x, size)
 518      struct ggc_pch_data *d ATTRIBUTE_UNUSED;
 519      void *x ATTRIBUTE_UNUSED;
 520      size_t size ATTRIBUTE_UNUSED;
 521 {
 522 }
 523
 524 size_t
 525 ggc_pch_total_size (d)
 526      struct ggc_pch_data *d ATTRIBUTE_UNUSED;
 527 {
 528   return 0;
 529 }
 530
 531 void
 532 ggc_pch_this_base (d, base)
 533      struct ggc_pch_data *d ATTRIBUTE_UNUSED;
 534      void *base ATTRIBUTE_UNUSED;
 535 {
 536 }
 537
 538
 539 char *
 540 ggc_pch_alloc_object (d, x, size)
 541      struct ggc_pch_data *d ATTRIBUTE_UNUSED;
 542      void *x ATTRIBUTE_UNUSED;
 543      size_t size ATTRIBUTE_UNUSED;
 544 {
 545   return NULL;
 546 }
 547
 548 void
 549 ggc_pch_prepare_write (d, f)
 550      struct ggc_pch_data * d ATTRIBUTE_UNUSED;
 551      FILE * f ATTRIBUTE_UNUSED;
 552 {
 553 }
 554
 555 void
 556 ggc_pch_write_object (d, f, x, newx, size)
 557      struct ggc_pch_data * d ATTRIBUTE_UNUSED;
 558      FILE *f ATTRIBUTE_UNUSED;
 559      void *x ATTRIBUTE_UNUSED;
 560      void *newx ATTRIBUTE_UNUSED;
 561      size_t size ATTRIBUTE_UNUSED;
 562 {
 563 }
 564
 565 void
 566 ggc_pch_finish (d, f)
 567      struct ggc_pch_data * d ATTRIBUTE_UNUSED;
 568      FILE *f ATTRIBUTE_UNUSED;
 569 {
 570 }
 571
 572 void
 573 ggc_pch_read (f, addr)
 574      FILE *f ATTRIBUTE_UNUSED;
 575      void *addr ATTRIBUTE_UNUSED;
 576 {
 577   /* This should be impossible, since we won't generate any valid PCH
 578      files for this configuration.  */
 579   abort ();
 580 }