gcc/alloc-pool.c

   1 /* Functions to support a pool of allocatable objects.
   2    Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005, 2006,
   3    2007, 2008, 2010  Free Software Foundation, Inc.
   4    Contributed by Daniel Berlin <dan@cgsoftware.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "alloc-pool.h"
  25 #include "hash-table.h"
  26
  27 #define align_eight(x) (((x+7) >> 3) << 3)
  28
  29 /* The internal allocation object.  */
  30 typedef struct allocation_object_def
  31 {
  32 #ifdef ENABLE_CHECKING
  33   /* The ID of alloc pool which the object was allocated from.  */
  34   ALLOC_POOL_ID_TYPE id;
  35 #endif
  36
  37   union
  38     {
  39       /* The data of the object.  */
  40       char data[1];
  41
  42       /* Because we want any type of data to be well aligned after the ID,
  43          the following elements are here.  They are never accessed so
  44          the allocated object may be even smaller than this structure.
  45          We do not care about alignment for floating-point types.  */
  46       char *align_p;
  47       HOST_WIDEST_INT align_i;
  48     } u;
  49 } allocation_object;
  50
  51 /* Convert a pointer to allocation_object from a pointer to user data.  */
  52 #define ALLOCATION_OBJECT_PTR_FROM_USER_PTR(X)                          \
  53    ((allocation_object *) (((char *) (X))                               \
  54                            - offsetof (allocation_object, u.data)))
  55
  56 /* Convert a pointer to user data from a pointer to allocation_object.  */
  57 #define USER_PTR_FROM_ALLOCATION_OBJECT_PTR(X)                          \
  58    ((void *) (((allocation_object *) (X))->u.data))
  59
  60 #ifdef ENABLE_CHECKING
  61 /* Last used ID.  */
  62 static ALLOC_POOL_ID_TYPE last_id;
  63 #endif
  64
  65 /* Store information about each particular alloc_pool.  Note that this
  66    will underestimate the amount the amount of storage used by a small amount:
  67    1) The overhead in a pool is not accounted for.
  68    2) The unallocated elements in a block are not accounted for.  Note
  69    that this can at worst case be one element smaller that the block
  70    size for that pool.  */
  71 struct alloc_pool_descriptor
  72 {
  73   const char *name;
  74   /* Number of pools allocated.  */
  75   unsigned long created;
  76   /* Gross allocated storage.  */
  77   unsigned long allocated;
  78   /* Amount of currently active storage. */
  79   unsigned long current;
  80   /* Peak amount of storage used.  */
  81   unsigned long peak;
  82   /* Size of element in the pool.  */
  83   int elt_size;
  84 };
  85
  86 struct alloc_pool_hasher : typed_noop_remove <alloc_pool_descriptor>
  87 {
  88   typedef alloc_pool_descriptor value_type;
  89   typedef char compare_type;
  90   static inline hashval_t hash (const alloc_pool_descriptor *);
  91   static inline bool equal (const value_type *, const compare_type *);
  92 };
  93
  94 /* Hashtable mapping alloc_pool names to descriptors.  */
  95 static hash_table <alloc_pool_hasher>  alloc_pool_hash;
  96
  97 /* Hashtable helpers.  */
  98 inline hashval_t
  99 alloc_pool_hasher::hash (const value_type *d)
 100 {
 101   return htab_hash_pointer (d->name);
 102 }
 103
 104 inline bool
 105 alloc_pool_hasher::equal (const value_type *d,
 106                           const compare_type *p2)
 107 {
 108   return d->name == p2;
 109 }
 110
 111 /* For given name, return descriptor, create new if needed.  */
 112 static struct alloc_pool_descriptor *
 113 allocate_pool_descriptor (const char *name)
 114 {
 115   struct alloc_pool_descriptor **slot;
 116
 117   if (!alloc_pool_hash.is_created ())
 118     alloc_pool_hash.create (10);
 119
 120   slot = alloc_pool_hash.find_slot_with_hash (name,
 121                                               htab_hash_pointer (name), INSERT);
 122   if (*slot)
 123     return *slot;
 124   *slot = XCNEW (struct alloc_pool_descriptor);
 125   (*slot)->name = name;
 126   return *slot;
 127 }
 128
 129 /* Create a pool of things of size SIZE, with NUM in each block we
 130    allocate.  */
 131
 132 alloc_pool
 133 create_alloc_pool (const char *name, size_t size, size_t num)
 134 {
 135   alloc_pool pool;
 136   size_t header_size;
 137
 138   gcc_checking_assert (name);
 139
 140   /* Make size large enough to store the list header.  */
 141   if (size < sizeof (alloc_pool_list))
 142     size = sizeof (alloc_pool_list);
 143
 144   /* Now align the size to a multiple of 4.  */
 145   size = align_eight (size);
 146
 147 #ifdef ENABLE_CHECKING
 148   /* Add the aligned size of ID.  */
 149   size += offsetof (allocation_object, u.data);
 150 #endif
 151
 152   /* Um, we can't really allocate 0 elements per block.  */
 153   gcc_checking_assert (num);
 154
 155   /* Allocate memory for the pool structure.  */
 156   pool = XNEW (struct alloc_pool_def);
 157
 158   /* Now init the various pieces of our pool structure.  */
 159   pool->name = /*xstrdup (name)*/name;
 160   pool->elt_size = size;
 161   pool->elts_per_block = num;
 162
 163   if (GATHER_STATISTICS)
 164     {
 165       struct alloc_pool_descriptor *desc = allocate_pool_descriptor (name);
 166       desc->elt_size = size;
 167       desc->created++;
 168     }
 169
 170   /* List header size should be a multiple of 8.  */
 171   header_size = align_eight (sizeof (struct alloc_pool_list_def));
 172
 173   pool->block_size = (size * num) + header_size;
 174   pool->returned_free_list = NULL;
 175   pool->virgin_free_list = NULL;
 176   pool->virgin_elts_remaining = 0;
 177   pool->elts_allocated = 0;
 178   pool->elts_free = 0;
 179   pool->blocks_allocated = 0;
 180   pool->block_list = NULL;
 181
 182 #ifdef ENABLE_CHECKING
 183   /* Increase the last used ID and use it for this pool.
 184      ID == 0 is used for free elements of pool so skip it.  */
 185   last_id++;
 186   if (last_id == 0)
 187     last_id++;
 188
 189   pool->id = last_id;
 190 #endif
 191
 192   return (pool);
 193 }
 194
 195 /* Free all memory allocated for the given memory pool.  */
 196 void
 197 empty_alloc_pool (alloc_pool pool)
 198 {
 199   alloc_pool_list block, next_block;
 200
 201   gcc_checking_assert (pool);
 202
 203   /* Free each block allocated to the pool.  */
 204   for (block = pool->block_list; block != NULL; block = next_block)
 205     {
 206       next_block = block->next;
 207       free (block);
 208     }
 209
 210   if (GATHER_STATISTICS)
 211     {
 212       struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name);
 213       desc->current -= (pool->elts_allocated - pool->elts_free) * pool->elt_size;
 214     }
 215
 216   pool->returned_free_list = NULL;
 217   pool->virgin_free_list = NULL;
 218   pool->virgin_elts_remaining = 0;
 219   pool->elts_allocated = 0;
 220   pool->elts_free = 0;
 221   pool->blocks_allocated = 0;
 222   pool->block_list = NULL;
 223 }
 224
 225 /* Free all memory allocated for the given memory pool and the pool itself.  */
 226 void
 227 free_alloc_pool (alloc_pool pool)
 228 {
 229   /* First empty the pool.  */
 230   empty_alloc_pool (pool);
 231 #ifdef ENABLE_CHECKING
 232   memset (pool, 0xaf, sizeof (*pool));
 233 #endif
 234   /* Lastly, free the pool.  */
 235   free (pool);
 236 }
 237
 238 /* Frees the alloc_pool, if it is empty and zero *POOL in this case.  */
 239 void
 240 free_alloc_pool_if_empty (alloc_pool *pool)
 241 {
 242   if ((*pool)->elts_free == (*pool)->elts_allocated)
 243     {
 244       free_alloc_pool (*pool);
 245       *pool = NULL;
 246     }
 247 }
 248
 249 /* Allocates one element from the pool specified.  */
 250 void *
 251 pool_alloc (alloc_pool pool)
 252 {
 253   alloc_pool_list header;
 254 #ifdef ENABLE_VALGRIND_CHECKING
 255   int size;
 256 #endif
 257
 258   if (GATHER_STATISTICS)
 259     {
 260       struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name);
 261
 262       desc->allocated += pool->elt_size;
 263       desc->current += pool->elt_size;
 264       if (desc->peak < desc->current)
 265         desc->peak = desc->current;
 266     }
 267
 268   gcc_checking_assert (pool);
 269 #ifdef ENABLE_VALGRIND_CHECKING
 270   size = pool->elt_size - offsetof (allocation_object, u.data);
 271 #endif
 272
 273   /* If there are no more free elements, make some more!.  */
 274   if (!pool->returned_free_list)
 275     {
 276       char *block;
 277       if (!pool->virgin_elts_remaining)
 278         {
 279           alloc_pool_list block_header;
 280
 281           /* Make the block.  */
 282           block = XNEWVEC (char, pool->block_size);
 283           block_header = (alloc_pool_list) block;
 284           block += align_eight (sizeof (struct alloc_pool_list_def));
 285
 286           /* Throw it on the block list.  */
 287           block_header->next = pool->block_list;
 288           pool->block_list = block_header;
 289
 290           /* Make the block available for allocation.  */
 291           pool->virgin_free_list = block;
 292           pool->virgin_elts_remaining = pool->elts_per_block;
 293
 294           /* Also update the number of elements we have free/allocated, and
 295              increment the allocated block count.  */
 296           pool->elts_allocated += pool->elts_per_block;
 297           pool->elts_free += pool->elts_per_block;
 298           pool->blocks_allocated += 1;
 299         }
 300
 301
 302       /* We now know that we can take the first elt off the virgin list and
 303          put it on the returned list. */
 304       block = pool->virgin_free_list;
 305       header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
 306       header->next = NULL;
 307 #ifdef ENABLE_CHECKING
 308       /* Mark the element to be free.  */
 309       ((allocation_object *) block)->id = 0;
 310 #endif
 311       VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (header,size));
 312       pool->returned_free_list = header;
 313       pool->virgin_free_list += pool->elt_size;
 314       pool->virgin_elts_remaining--;
 315
 316     }
 317
 318   /* Pull the first free element from the free list, and return it.  */
 319   header = pool->returned_free_list;
 320   VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (header, sizeof(*header)));
 321   pool->returned_free_list = header->next;
 322   pool->elts_free--;
 323
 324 #ifdef ENABLE_CHECKING
 325   /* Set the ID for element.  */
 326   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
 327 #endif
 328   VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (header, size));
 329
 330   return ((void *) header);
 331 }
 332
 333 /* Puts PTR back on POOL's free list.  */
 334 void
 335 pool_free (alloc_pool pool, void *ptr)
 336 {
 337   alloc_pool_list header;
 338 #if defined(ENABLE_VALGRIND_CHECKING) || defined(ENABLE_CHECKING)
 339   int size;
 340   size = pool->elt_size - offsetof (allocation_object, u.data);
 341 #endif
 342
 343 #ifdef ENABLE_CHECKING
 344   gcc_assert (ptr
 345               /* Check if we free more than we allocated, which is Bad (TM).  */
 346               && pool->elts_free < pool->elts_allocated
 347               /* Check whether the PTR was allocated from POOL.  */
 348               && pool->id == ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id);
 349
 350   memset (ptr, 0xaf, size);
 351
 352   /* Mark the element to be free.  */
 353   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
 354 #endif
 355
 356   header = (alloc_pool_list) ptr;
 357   header->next = pool->returned_free_list;
 358   pool->returned_free_list = header;
 359   VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (ptr, size));
 360   pool->elts_free++;
 361
 362   if (GATHER_STATISTICS)
 363     {
 364       struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name);
 365       desc->current -= pool->elt_size;
 366     }
 367 }
 368
 369 /* Output per-alloc_pool statistics.  */
 370
 371 /* Used to accumulate statistics about alloc_pool sizes.  */
 372 struct output_info
 373 {
 374   unsigned long total_created;
 375   unsigned long total_allocated;
 376 };
 377
 378 /* Called via hash_table.traverse.  Output alloc_pool descriptor pointed out by
 379    SLOT and update statistics.  */
 380 int
 381 print_alloc_pool_statistics (alloc_pool_descriptor **slot,
 382                              struct output_info *i)
 383 {
 384   struct alloc_pool_descriptor *d = *slot;
 385
 386   if (d->allocated)
 387     {
 388       fprintf (stderr,
 389                "%-22s %6d %10lu %10lu(%10lu) %10lu(%10lu) %10lu(%10lu)\n",
 390                d->name, d->elt_size, d->created, d->allocated,
 391                d->allocated / d->elt_size, d->peak, d->peak / d->elt_size,
 392                d->current, d->current / d->elt_size);
 393       i->total_allocated += d->allocated;
 394       i->total_created += d->created;
 395     }
 396   return 1;
 397 }
 398
 399 /* Output per-alloc_pool memory usage statistics.  */
 400 void
 401 dump_alloc_pool_statistics (void)
 402 {
 403   struct output_info info;
 404
 405   if (! GATHER_STATISTICS)
 406     return;
 407
 408   if (!alloc_pool_hash.is_created ())
 409     return;
 410
 411   fprintf (stderr, "\nAlloc-pool Kind         Elt size  Pools  Allocated (elts)            Peak (elts)            Leak (elts)\n");
 412   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 413   info.total_created = 0;
 414   info.total_allocated = 0;
 415   alloc_pool_hash.traverse <struct output_info *,
 416                             print_alloc_pool_statistics> (&info);
 417   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 418   fprintf (stderr, "%-22s           %7lu %10lu\n",
 419            "Total", info.total_created, info.total_allocated);
 420   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 421 }