gcc/ggc-simple.c

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