gcc/ggc-simple.c

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