gcc/alloc-pool.c

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