gcc/ggc-common.c

   1 /* Simple garbage collection for the GNU compiler.
   2    Copyright (C) 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 under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 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 /* Generic garbage collection (GC) functions and data, not specific to
  22    any particular GC implementation.  */
  23
  24 #include "config.h"
  25 #include "system.h"
  26 #include "coretypes.h"
  27 #include "hashtab.h"
  28 #include "ggc.h"
  29 #include "toplev.h"
  30
  31 #ifdef HAVE_MMAP_FILE
  32 # include <sys/mman.h>
  33 #endif
  34
  35 #ifdef ENABLE_VALGRIND_CHECKING
  36 #include <valgrind.h>
  37 #else
  38 /* Avoid #ifdef:s when we can help it.  */
  39 #define VALGRIND_DISCARD(x)
  40 #endif
  41
  42 /* Statistics about the allocation.  */
  43 static ggc_statistics *ggc_stats;
  44
  45 struct traversal_state;
  46
  47 static int ggc_htab_delete PARAMS ((void **, void *));
  48 static hashval_t saving_htab_hash PARAMS ((const PTR));
  49 static int saving_htab_eq PARAMS ((const PTR, const PTR));
  50 static int call_count PARAMS ((void **, void *));
  51 static int call_alloc PARAMS ((void **, void *));
  52 static int compare_ptr_data PARAMS ((const void *, const void *));
  53 static void relocate_ptrs PARAMS ((void *, void *));
  54 static void write_pch_globals PARAMS ((const struct ggc_root_tab * const *tab,
  55                                        struct traversal_state *state));
  56
  57 /* Maintain global roots that are preserved during GC.  */
  58
  59 /* Process a slot of an htab by deleting it if it has not been marked.  */
  60
  61 static int
  62 ggc_htab_delete (slot, info)
  63      void **slot;
  64      void *info;
  65 {
  66   const struct ggc_cache_tab *r = (const struct ggc_cache_tab *) info;
  67
  68   if (! (*r->marked_p) (*slot))
  69     htab_clear_slot (*r->base, slot);
  70   else
  71     (*r->cb) (*slot);
  72
  73   return 1;
  74 }
  75
  76 /* Iterate through all registered roots and mark each element.  */
  77
  78 void
  79 ggc_mark_roots ()
  80 {
  81   const struct ggc_root_tab *const *rt;
  82   const struct ggc_root_tab *rti;
  83   const struct ggc_cache_tab *const *ct;
  84   const struct ggc_cache_tab *cti;
  85   size_t i;
  86
  87   for (rt = gt_ggc_deletable_rtab; *rt; rt++)
  88     for (rti = *rt; rti->base != NULL; rti++)
  89       memset (rti->base, 0, rti->stride);
  90
  91   for (rt = gt_ggc_rtab; *rt; rt++)
  92     for (rti = *rt; rti->base != NULL; rti++)
  93       for (i = 0; i < rti->nelt; i++)
  94         (*rti->cb)(*(void **)((char *)rti->base + rti->stride * i));
  95
  96   ggc_mark_stringpool ();
  97
  98   /* Now scan all hash tables that have objects which are to be deleted if
  99      they are not already marked.  */
 100   for (ct = gt_ggc_cache_rtab; *ct; ct++)
 101     for (cti = *ct; cti->base != NULL; cti++)
 102       if (*cti->base)
 103         {
 104           ggc_set_mark (*cti->base);
 105           htab_traverse (*cti->base, ggc_htab_delete, (PTR) cti);
 106           ggc_set_mark ((*cti->base)->entries);
 107         }
 108 }
 109
 110 /* Allocate a block of memory, then clear it.  */
 111 void *
 112 ggc_alloc_cleared (size)
 113      size_t size;
 114 {
 115   void *buf = ggc_alloc (size);
 116   memset (buf, 0, size);
 117   return buf;
 118 }
 119
 120 /* Resize a block of memory, possibly re-allocating it.  */
 121 void *
 122 ggc_realloc (x, size)
 123      void *x;
 124      size_t size;
 125 {
 126   void *r;
 127   size_t old_size;
 128
 129   if (x == NULL)
 130     return ggc_alloc (size);
 131
 132   old_size = ggc_get_size (x);
 133   if (size <= old_size)
 134     {
 135       /* Mark the unwanted memory as unaccessible.  We also need to make
 136          the "new" size accessible, since ggc_get_size returns the size of
 137          the pool, not the size of the individually allocated object, the
 138          size which was previously made accessible.  Unfortunately, we
 139          don't know that previously allocated size.  Without that
 140          knowledge we have to lose some initialization-tracking for the
 141          old parts of the object.  An alternative is to mark the whole
 142          old_size as reachable, but that would lose tracking of writes
 143          after the end of the object (by small offsets).  Discard the
 144          handle to avoid handle leak.  */
 145       VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS ((char *) x + size,
 146                                                 old_size - size));
 147       VALGRIND_DISCARD (VALGRIND_MAKE_READABLE (x, size));
 148       return x;
 149     }
 150
 151   r = ggc_alloc (size);
 152
 153   /* Since ggc_get_size returns the size of the pool, not the size of the
 154      individually allocated object, we'd access parts of the old object
 155      that were marked invalid with the memcpy below.  We lose a bit of the
 156      initialization-tracking since some of it may be uninitialized.  */
 157   VALGRIND_DISCARD (VALGRIND_MAKE_READABLE (x, old_size));
 158
 159   memcpy (r, x, old_size);
 160
 161   /* The old object is not supposed to be used anymore.  */
 162   VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (x, old_size));
 163
 164   return r;
 165 }
 166
 167 /* Like ggc_alloc_cleared, but performs a multiplication.  */
 168 void *
 169 ggc_calloc (s1, s2)
 170      size_t s1, s2;
 171 {
 172   return ggc_alloc_cleared (s1 * s2);
 173 }
 174
 175 /* These are for splay_tree_new_ggc.  */
 176 PTR
 177 ggc_splay_alloc (sz, nl)
 178      int sz;
 179      PTR nl;
 180 {
 181   if (nl != NULL)
 182     abort ();
 183   return ggc_alloc (sz);
 184 }
 185
 186 void
 187 ggc_splay_dont_free (x, nl)
 188      PTR x ATTRIBUTE_UNUSED;
 189      PTR nl;
 190 {
 191   if (nl != NULL)
 192     abort ();
 193 }
 194
 195 /* Print statistics that are independent of the collector in use.  */
 196 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 197                   ? (x) \
 198                   : ((x) < 1024*1024*10 \
 199                      ? (x) / 1024 \
 200                      : (x) / (1024*1024))))
 201 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 202
 203 void
 204 ggc_print_common_statistics (stream, stats)
 205      FILE *stream ATTRIBUTE_UNUSED;
 206      ggc_statistics *stats;
 207 {
 208   /* Set the pointer so that during collection we will actually gather
 209      the statistics.  */
 210   ggc_stats = stats;
 211
 212   /* Then do one collection to fill in the statistics.  */
 213   ggc_collect ();
 214
 215   /* At present, we don't really gather any interesting statistics.  */
 216
 217   /* Don't gather statistics any more.  */
 218   ggc_stats = NULL;
 219 }
 220 \f
 221 /* Functions for saving and restoring GCable memory to disk.  */
 222
 223 static htab_t saving_htab;
 224
 225 struct ptr_data
 226 {
 227   void *obj;
 228   void *note_ptr_cookie;
 229   gt_note_pointers note_ptr_fn;
 230   gt_handle_reorder reorder_fn;
 231   size_t size;
 232   void *new_addr;
 233 };
 234
 235 #define POINTER_HASH(x) (hashval_t)((long)x >> 3)
 236
 237 /* Register an object in the hash table.  */
 238
 239 int
 240 gt_pch_note_object (obj, note_ptr_cookie, note_ptr_fn)
 241      void *obj;
 242      void *note_ptr_cookie;
 243      gt_note_pointers note_ptr_fn;
 244 {
 245   struct ptr_data **slot;
 246
 247   if (obj == NULL || obj == (void *) 1)
 248     return 0;
 249
 250   slot = (struct ptr_data **)
 251     htab_find_slot_with_hash (saving_htab, obj, POINTER_HASH (obj),
 252                               INSERT);
 253   if (*slot != NULL)
 254     {
 255       if ((*slot)->note_ptr_fn != note_ptr_fn
 256           || (*slot)->note_ptr_cookie != note_ptr_cookie)
 257         abort ();
 258       return 0;
 259     }
 260
 261   *slot = xcalloc (sizeof (struct ptr_data), 1);
 262   (*slot)->obj = obj;
 263   (*slot)->note_ptr_fn = note_ptr_fn;
 264   (*slot)->note_ptr_cookie = note_ptr_cookie;
 265   if (note_ptr_fn == gt_pch_p_S)
 266     (*slot)->size = strlen (obj) + 1;
 267   else
 268     (*slot)->size = ggc_get_size (obj);
 269   return 1;
 270 }
 271
 272 /* Register an object in the hash table.  */
 273
 274 void
 275 gt_pch_note_reorder (obj, note_ptr_cookie, reorder_fn)
 276      void *obj;
 277      void *note_ptr_cookie;
 278      gt_handle_reorder reorder_fn;
 279 {
 280   struct ptr_data *data;
 281
 282   if (obj == NULL || obj == (void *) 1)
 283     return;
 284
 285   data = htab_find_with_hash (saving_htab, obj, POINTER_HASH (obj));
 286   if (data == NULL
 287       || data->note_ptr_cookie != note_ptr_cookie)
 288     abort ();
 289
 290   data->reorder_fn = reorder_fn;
 291 }
 292
 293 /* Hash and equality functions for saving_htab, callbacks for htab_create.  */
 294
 295 static hashval_t
 296 saving_htab_hash (p)
 297      const PTR p;
 298 {
 299   return POINTER_HASH (((struct ptr_data *)p)->obj);
 300 }
 301
 302 static int
 303 saving_htab_eq (p1, p2)
 304      const PTR p1;
 305      const PTR p2;
 306 {
 307   return ((struct ptr_data *)p1)->obj == p2;
 308 }
 309
 310 /* Handy state for the traversal functions.  */
 311
 312 struct traversal_state
 313 {
 314   FILE *f;
 315   struct ggc_pch_data *d;
 316   size_t count;
 317   struct ptr_data **ptrs;
 318   size_t ptrs_i;
 319 };
 320
 321 /* Callbacks for htab_traverse.  */
 322
 323 static int
 324 call_count (slot, state_p)
 325      void **slot;
 326      void *state_p;
 327 {
 328   struct ptr_data *d = (struct ptr_data *)*slot;
 329   struct traversal_state *state = (struct traversal_state *)state_p;
 330
 331   ggc_pch_count_object (state->d, d->obj, d->size);
 332   state->count++;
 333   return 1;
 334 }
 335
 336 static int
 337 call_alloc (slot, state_p)
 338      void **slot;
 339      void *state_p;
 340 {
 341   struct ptr_data *d = (struct ptr_data *)*slot;
 342   struct traversal_state *state = (struct traversal_state *)state_p;
 343
 344   d->new_addr = ggc_pch_alloc_object (state->d, d->obj, d->size);
 345   state->ptrs[state->ptrs_i++] = d;
 346   return 1;
 347 }
 348
 349 /* Callback for qsort.  */
 350
 351 static int
 352 compare_ptr_data (p1_p, p2_p)
 353      const void *p1_p;
 354      const void *p2_p;
 355 {
 356   struct ptr_data *p1 = *(struct ptr_data *const *)p1_p;
 357   struct ptr_data *p2 = *(struct ptr_data *const *)p2_p;
 358   return (((size_t)p1->new_addr > (size_t)p2->new_addr)
 359           - ((size_t)p1->new_addr < (size_t)p2->new_addr));
 360 }
 361
 362 /* Callbacks for note_ptr_fn.  */
 363
 364 static void
 365 relocate_ptrs (ptr_p, state_p)
 366      void *ptr_p;
 367      void *state_p;
 368 {
 369   void **ptr = (void **)ptr_p;
 370   struct traversal_state *state ATTRIBUTE_UNUSED
 371     = (struct traversal_state *)state_p;
 372   struct ptr_data *result;
 373
 374   if (*ptr == NULL || *ptr == (void *)1)
 375     return;
 376
 377   result = htab_find_with_hash (saving_htab, *ptr, POINTER_HASH (*ptr));
 378   if (result == NULL)
 379     abort ();
 380   *ptr = result->new_addr;
 381 }
 382
 383 /* Write out, after relocation, the pointers in TAB.  */
 384 static void
 385 write_pch_globals (tab, state)
 386      const struct ggc_root_tab * const *tab;
 387      struct traversal_state *state;
 388 {
 389   const struct ggc_root_tab *const *rt;
 390   const struct ggc_root_tab *rti;
 391   size_t i;
 392
 393   for (rt = tab; *rt; rt++)
 394     for (rti = *rt; rti->base != NULL; rti++)
 395       for (i = 0; i < rti->nelt; i++)
 396         {
 397           void *ptr = *(void **)((char *)rti->base + rti->stride * i);
 398           struct ptr_data *new_ptr;
 399           if (ptr == NULL || ptr == (void *)1)
 400             {
 401               if (fwrite (&ptr, sizeof (void *), 1, state->f)
 402                   != 1)
 403                 fatal_io_error ("can't write PCH file");
 404             }
 405           else
 406             {
 407               new_ptr = htab_find_with_hash (saving_htab, ptr,
 408                                              POINTER_HASH (ptr));
 409               if (fwrite (&new_ptr->new_addr, sizeof (void *), 1, state->f)
 410                   != 1)
 411                 fatal_io_error ("can't write PCH file");
 412             }
 413         }
 414 }
 415
 416 /* Hold the information we need to mmap the file back in.  */
 417
 418 struct mmap_info
 419 {
 420   size_t offset;
 421   size_t size;
 422   void *preferred_base;
 423 };
 424
 425 /* Write out the state of the compiler to F.  */
 426
 427 void
 428 gt_pch_save (f)
 429      FILE *f;
 430 {
 431   const struct ggc_root_tab *const *rt;
 432   const struct ggc_root_tab *rti;
 433   size_t i;
 434   struct traversal_state state;
 435   char *this_object = NULL;
 436   size_t this_object_size = 0;
 437   struct mmap_info mmi;
 438   size_t page_size = getpagesize();
 439
 440   gt_pch_save_stringpool ();
 441
 442   saving_htab = htab_create (50000, saving_htab_hash, saving_htab_eq, free);
 443
 444   for (rt = gt_ggc_rtab; *rt; rt++)
 445     for (rti = *rt; rti->base != NULL; rti++)
 446       for (i = 0; i < rti->nelt; i++)
 447         (*rti->pchw)(*(void **)((char *)rti->base + rti->stride * i));
 448
 449   for (rt = gt_pch_cache_rtab; *rt; rt++)
 450     for (rti = *rt; rti->base != NULL; rti++)
 451       for (i = 0; i < rti->nelt; i++)
 452         (*rti->pchw)(*(void **)((char *)rti->base + rti->stride * i));
 453
 454   /* Prepare the objects for writing, determine addresses and such.  */
 455   state.f = f;
 456   state.d = init_ggc_pch();
 457   state.count = 0;
 458   htab_traverse (saving_htab, call_count, &state);
 459
 460   mmi.size = ggc_pch_total_size (state.d);
 461
 462   /* Try to arrange things so that no relocation is necessary,
 463      but don't try very hard.  On most platforms, this will always work,
 464      and on the rest it's a lot of work to do better.  */
 465 #if HAVE_MMAP_FILE
 466   mmi.preferred_base = mmap (NULL, mmi.size,
 467                              PROT_READ | PROT_WRITE, MAP_PRIVATE,
 468                              fileno (state.f), 0);
 469   if (mmi.preferred_base == (void *)-1)
 470     mmi.preferred_base = NULL;
 471   else
 472     munmap (mmi.preferred_base, mmi.size);
 473 #else /* HAVE_MMAP_FILE */
 474   mmi.preferred_base = NULL;
 475 #endif /* HAVE_MMAP_FILE */
 476
 477   ggc_pch_this_base (state.d, mmi.preferred_base);
 478
 479   state.ptrs = xmalloc (state.count * sizeof (*state.ptrs));
 480   state.ptrs_i = 0;
 481   htab_traverse (saving_htab, call_alloc, &state);
 482   qsort (state.ptrs, state.count, sizeof (*state.ptrs), compare_ptr_data);
 483
 484   /* Write out all the scalar variables.  */
 485   for (rt = gt_pch_scalar_rtab; *rt; rt++)
 486     for (rti = *rt; rti->base != NULL; rti++)
 487       if (fwrite (rti->base, rti->stride, 1, f) != 1)
 488         fatal_io_error ("can't write PCH file");
 489
 490   /* Write out all the global pointers, after translation.  */
 491   write_pch_globals (gt_ggc_rtab, &state);
 492   write_pch_globals (gt_pch_cache_rtab, &state);
 493
 494   ggc_pch_prepare_write (state.d, state.f);
 495
 496   /* Pad the PCH file so that the mmaped area starts on a page boundary.  */
 497   {
 498     long o;
 499     o = ftell (state.f) + sizeof (mmi);
 500     if (o == -1)
 501       fatal_io_error ("can't get position in PCH file");
 502     mmi.offset = page_size - o % page_size;
 503     if (mmi.offset == page_size)
 504       mmi.offset = 0;
 505     mmi.offset += o;
 506   }
 507   if (fwrite (&mmi, sizeof (mmi), 1, state.f) != 1)
 508     fatal_io_error ("can't write PCH file");
 509   if (mmi.offset != 0
 510       && fseek (state.f, mmi.offset, SEEK_SET) != 0)
 511     fatal_io_error ("can't write padding to PCH file");
 512
 513   /* Actually write out the objects.  */
 514   for (i = 0; i < state.count; i++)
 515     {
 516       if (this_object_size < state.ptrs[i]->size)
 517         {
 518           this_object_size = state.ptrs[i]->size;
 519           this_object = xrealloc (this_object, this_object_size);
 520         }
 521       memcpy (this_object, state.ptrs[i]->obj, state.ptrs[i]->size);
 522       if (state.ptrs[i]->reorder_fn != NULL)
 523         state.ptrs[i]->reorder_fn (state.ptrs[i]->obj,
 524                                    state.ptrs[i]->note_ptr_cookie,
 525                                    relocate_ptrs, &state);
 526       state.ptrs[i]->note_ptr_fn (state.ptrs[i]->obj,
 527                                   state.ptrs[i]->note_ptr_cookie,
 528                                   relocate_ptrs, &state);
 529       ggc_pch_write_object (state.d, state.f, state.ptrs[i]->obj,
 530                             state.ptrs[i]->new_addr, state.ptrs[i]->size);
 531       if (state.ptrs[i]->note_ptr_fn != gt_pch_p_S)
 532         memcpy (state.ptrs[i]->obj, this_object, state.ptrs[i]->size);
 533     }
 534   ggc_pch_finish (state.d, state.f);
 535
 536   free (state.ptrs);
 537   htab_delete (saving_htab);
 538 }
 539
 540 /* Read the state of the compiler back in from F.  */
 541
 542 void
 543 gt_pch_restore (f)
 544      FILE *f;
 545 {
 546   const struct ggc_root_tab *const *rt;
 547   const struct ggc_root_tab *rti;
 548   size_t i;
 549   struct mmap_info mmi;
 550   void *addr;
 551
 552   /* Delete any deletable objects.  This makes ggc_pch_read much
 553      faster, as it can be sure that no GCable objects remain other
 554      than the ones just read in.  */
 555   for (rt = gt_ggc_deletable_rtab; *rt; rt++)
 556     for (rti = *rt; rti->base != NULL; rti++)
 557       memset (rti->base, 0, rti->stride);
 558
 559   /* Read in all the scalar variables.  */
 560   for (rt = gt_pch_scalar_rtab; *rt; rt++)
 561     for (rti = *rt; rti->base != NULL; rti++)
 562       if (fread (rti->base, rti->stride, 1, f) != 1)
 563         fatal_io_error ("can't read PCH file");
 564
 565   /* Read in all the global pointers, in 6 easy loops.  */
 566   for (rt = gt_ggc_rtab; *rt; rt++)
 567     for (rti = *rt; rti->base != NULL; rti++)
 568       for (i = 0; i < rti->nelt; i++)
 569         if (fread ((char *)rti->base + rti->stride * i,
 570                    sizeof (void *), 1, f) != 1)
 571           fatal_io_error ("can't read PCH file");
 572
 573   for (rt = gt_pch_cache_rtab; *rt; rt++)
 574     for (rti = *rt; rti->base != NULL; rti++)
 575       for (i = 0; i < rti->nelt; i++)
 576         if (fread ((char *)rti->base + rti->stride * i,
 577                    sizeof (void *), 1, f) != 1)
 578           fatal_io_error ("can't read PCH file");
 579
 580   if (fread (&mmi, sizeof (mmi), 1, f) != 1)
 581     fatal_io_error ("can't read PCH file");
 582
 583 #if HAVE_MMAP_FILE
 584   addr = mmap (mmi.preferred_base, mmi.size,
 585                PROT_READ | PROT_WRITE, MAP_PRIVATE,
 586                fileno (f), mmi.offset);
 587 #else
 588   addr = (void *)-1;
 589 #endif
 590   if (addr == (void *)-1)
 591     {
 592       addr = xmalloc (mmi.size);
 593       if (fseek (f, mmi.offset, SEEK_SET) != 0
 594           || fread (&mmi, mmi.size, 1, f) != 1)
 595         fatal_io_error ("can't read PCH file");
 596     }
 597   else if (fseek (f, mmi.offset + mmi.size, SEEK_SET) != 0)
 598     fatal_io_error ("can't read PCH file");
 599
 600   ggc_pch_read (f, addr);
 601
 602   if (addr != mmi.preferred_base)
 603     {
 604       for (rt = gt_ggc_rtab; *rt; rt++)
 605         for (rti = *rt; rti->base != NULL; rti++)
 606           for (i = 0; i < rti->nelt; i++)
 607             {
 608               char **ptr = (char **)((char *)rti->base + rti->stride * i);
 609               if (*ptr != NULL)
 610                 *ptr += (size_t)addr - (size_t)mmi.preferred_base;
 611             }
 612
 613       for (rt = gt_pch_cache_rtab; *rt; rt++)
 614         for (rti = *rt; rti->base != NULL; rti++)
 615           for (i = 0; i < rti->nelt; i++)
 616             {
 617               char **ptr = (char **)((char *)rti->base + rti->stride * i);
 618               if (*ptr != NULL)
 619                 *ptr += (size_t)addr - (size_t)mmi.preferred_base;
 620             }
 621
 622       sorry ("had to relocate PCH");
 623     }
 624
 625   gt_pch_restore_stringpool ();
 626 }