gcc/alloc-pool.c

   1 /* Functions to support a pool of allocatable objects.
   2    Copyright (C) 1987-2014 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 #include "hash-map.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       int64_t 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   /* 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 /* Hashtable mapping alloc_pool names to descriptors.  */
  86 static hash_map<const char *, alloc_pool_descriptor> *alloc_pool_hash;
  87
  88 /* For given name, return descriptor, create new if needed.  */
  89 static struct alloc_pool_descriptor *
  90 allocate_pool_descriptor (const char *name)
  91 {
  92   if (!alloc_pool_hash)
  93     alloc_pool_hash = new hash_map<const char *, alloc_pool_descriptor> (10);
  94
  95   return &alloc_pool_hash->get_or_insert (name);
  96 }
  97
  98 /* Create a pool of things of size SIZE, with NUM in each block we
  99    allocate.  */
 100
 101 alloc_pool
 102 create_alloc_pool (const char *name, size_t size, size_t num)
 103 {
 104   alloc_pool pool;
 105   size_t header_size;
 106
 107   gcc_checking_assert (name);
 108
 109   /* Make size large enough to store the list header.  */
 110   if (size < sizeof (alloc_pool_list))
 111     size = sizeof (alloc_pool_list);
 112
 113   /* Now align the size to a multiple of 4.  */
 114   size = align_eight (size);
 115
 116 #ifdef ENABLE_CHECKING
 117   /* Add the aligned size of ID.  */
 118   size += offsetof (allocation_object, u.data);
 119 #endif
 120
 121   /* Um, we can't really allocate 0 elements per block.  */
 122   gcc_checking_assert (num);
 123
 124   /* Allocate memory for the pool structure.  */
 125   pool = XNEW (struct alloc_pool_def);
 126
 127   /* Now init the various pieces of our pool structure.  */
 128   pool->name = /*xstrdup (name)*/name;
 129   pool->elt_size = size;
 130   pool->elts_per_block = num;
 131
 132   if (GATHER_STATISTICS)
 133     {
 134       struct alloc_pool_descriptor *desc = allocate_pool_descriptor (name);
 135       desc->elt_size = size;
 136       desc->created++;
 137     }
 138
 139   /* List header size should be a multiple of 8.  */
 140   header_size = align_eight (sizeof (struct alloc_pool_list_def));
 141
 142   pool->block_size = (size * num) + header_size;
 143   pool->returned_free_list = NULL;
 144   pool->virgin_free_list = NULL;
 145   pool->virgin_elts_remaining = 0;
 146   pool->elts_allocated = 0;
 147   pool->elts_free = 0;
 148   pool->blocks_allocated = 0;
 149   pool->block_list = NULL;
 150
 151 #ifdef ENABLE_CHECKING
 152   /* Increase the last used ID and use it for this pool.
 153      ID == 0 is used for free elements of pool so skip it.  */
 154   last_id++;
 155   if (last_id == 0)
 156     last_id++;
 157
 158   pool->id = last_id;
 159 #endif
 160
 161   return (pool);
 162 }
 163
 164 /* Free all memory allocated for the given memory pool.  */
 165 void
 166 empty_alloc_pool (alloc_pool pool)
 167 {
 168   alloc_pool_list block, next_block;
 169
 170   gcc_checking_assert (pool);
 171
 172   /* Free each block allocated to the pool.  */
 173   for (block = pool->block_list; block != NULL; block = next_block)
 174     {
 175       next_block = block->next;
 176       free (block);
 177     }
 178
 179   if (GATHER_STATISTICS)
 180     {
 181       struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name);
 182       desc->current -= (pool->elts_allocated - pool->elts_free) * pool->elt_size;
 183     }
 184
 185   pool->returned_free_list = NULL;
 186   pool->virgin_free_list = NULL;
 187   pool->virgin_elts_remaining = 0;
 188   pool->elts_allocated = 0;
 189   pool->elts_free = 0;
 190   pool->blocks_allocated = 0;
 191   pool->block_list = NULL;
 192 }
 193
 194 /* Free all memory allocated for the given memory pool and the pool itself.  */
 195 void
 196 free_alloc_pool (alloc_pool pool)
 197 {
 198   /* First empty the pool.  */
 199   empty_alloc_pool (pool);
 200 #ifdef ENABLE_CHECKING
 201   memset (pool, 0xaf, sizeof (*pool));
 202 #endif
 203   /* Lastly, free the pool.  */
 204   free (pool);
 205 }
 206
 207 /* Frees the alloc_pool, if it is empty and zero *POOL in this case.  */
 208 void
 209 free_alloc_pool_if_empty (alloc_pool *pool)
 210 {
 211   if ((*pool)->elts_free == (*pool)->elts_allocated)
 212     {
 213       free_alloc_pool (*pool);
 214       *pool = NULL;
 215     }
 216 }
 217
 218 /* Allocates one element from the pool specified.  */
 219 void *
 220 pool_alloc (alloc_pool pool)
 221 {
 222   alloc_pool_list header;
 223 #ifdef ENABLE_VALGRIND_ANNOTATIONS
 224   int size;
 225 #endif
 226
 227   if (GATHER_STATISTICS)
 228     {
 229       struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name);
 230
 231       desc->allocated += pool->elt_size;
 232       desc->current += pool->elt_size;
 233       if (desc->peak < desc->current)
 234         desc->peak = desc->current;
 235     }
 236
 237   gcc_checking_assert (pool);
 238 #ifdef ENABLE_VALGRIND_ANNOTATIONS
 239   size = pool->elt_size - offsetof (allocation_object, u.data);
 240 #endif
 241
 242   /* If there are no more free elements, make some more!.  */
 243   if (!pool->returned_free_list)
 244     {
 245       char *block;
 246       if (!pool->virgin_elts_remaining)
 247         {
 248           alloc_pool_list block_header;
 249
 250           /* Make the block.  */
 251           block = XNEWVEC (char, pool->block_size);
 252           block_header = (alloc_pool_list) block;
 253           block += align_eight (sizeof (struct alloc_pool_list_def));
 254
 255           /* Throw it on the block list.  */
 256           block_header->next = pool->block_list;
 257           pool->block_list = block_header;
 258
 259           /* Make the block available for allocation.  */
 260           pool->virgin_free_list = block;
 261           pool->virgin_elts_remaining = pool->elts_per_block;
 262
 263           /* Also update the number of elements we have free/allocated, and
 264              increment the allocated block count.  */
 265           pool->elts_allocated += pool->elts_per_block;
 266           pool->elts_free += pool->elts_per_block;
 267           pool->blocks_allocated += 1;
 268         }
 269
 270
 271       /* We now know that we can take the first elt off the virgin list and
 272          put it on the returned list. */
 273       block = pool->virgin_free_list;
 274       header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
 275       header->next = NULL;
 276 #ifdef ENABLE_CHECKING
 277       /* Mark the element to be free.  */
 278       ((allocation_object *) block)->id = 0;
 279 #endif
 280       VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (header,size));
 281       pool->returned_free_list = header;
 282       pool->virgin_free_list += pool->elt_size;
 283       pool->virgin_elts_remaining--;
 284
 285     }
 286
 287   /* Pull the first free element from the free list, and return it.  */
 288   header = pool->returned_free_list;
 289   VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (header, sizeof (*header)));
 290   pool->returned_free_list = header->next;
 291   pool->elts_free--;
 292
 293 #ifdef ENABLE_CHECKING
 294   /* Set the ID for element.  */
 295   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
 296 #endif
 297   VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (header, size));
 298
 299   return ((void *) header);
 300 }
 301
 302 /* Puts PTR back on POOL's free list.  */
 303 void
 304 pool_free (alloc_pool pool, void *ptr)
 305 {
 306   alloc_pool_list header;
 307 #if defined(ENABLE_VALGRIND_ANNOTATIONS) || defined(ENABLE_CHECKING)
 308   int size;
 309   size = pool->elt_size - offsetof (allocation_object, u.data);
 310 #endif
 311
 312 #ifdef ENABLE_CHECKING
 313   gcc_assert (ptr
 314               /* Check if we free more than we allocated, which is Bad (TM).  */
 315               && pool->elts_free < pool->elts_allocated
 316               /* Check whether the PTR was allocated from POOL.  */
 317               && pool->id == ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id);
 318
 319   memset (ptr, 0xaf, size);
 320
 321   /* Mark the element to be free.  */
 322   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
 323 #endif
 324
 325   header = (alloc_pool_list) ptr;
 326   header->next = pool->returned_free_list;
 327   pool->returned_free_list = header;
 328   VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (ptr, size));
 329   pool->elts_free++;
 330
 331   if (GATHER_STATISTICS)
 332     {
 333       struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name);
 334       desc->current -= pool->elt_size;
 335     }
 336 }
 337
 338 /* Output per-alloc_pool statistics.  */
 339
 340 /* Used to accumulate statistics about alloc_pool sizes.  */
 341 struct output_info
 342 {
 343   unsigned long total_created;
 344   unsigned long total_allocated;
 345 };
 346
 347 /* Called via hash_map.traverse.  Output alloc_pool descriptor pointed out by
 348    SLOT and update statistics.  */
 349 bool
 350 print_alloc_pool_statistics (const char *const &name,
 351                              const alloc_pool_descriptor &d,
 352                              struct output_info *i)
 353 {
 354   if (d.allocated)
 355     {
 356       fprintf (stderr,
 357                "%-22s %6d %10lu %10lu(%10lu) %10lu(%10lu) %10lu(%10lu)\n",
 358                name, d.elt_size, d.created, d.allocated,
 359                d.allocated / d.elt_size, d.peak, d.peak / d.elt_size,
 360                d.current, d.current / d.elt_size);
 361       i->total_allocated += d.allocated;
 362       i->total_created += d.created;
 363     }
 364   return 1;
 365 }
 366
 367 /* Output per-alloc_pool memory usage statistics.  */
 368 void
 369 dump_alloc_pool_statistics (void)
 370 {
 371   struct output_info info;
 372
 373   if (! GATHER_STATISTICS)
 374     return;
 375
 376   if (!alloc_pool_hash)
 377     return;
 378
 379   fprintf (stderr, "\nAlloc-pool Kind         Elt size  Pools  Allocated (elts)            Peak (elts)            Leak (elts)\n");
 380   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 381   info.total_created = 0;
 382   info.total_allocated = 0;
 383   alloc_pool_hash->traverse <struct output_info *,
 384                              print_alloc_pool_statistics> (&info);
 385   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 386   fprintf (stderr, "%-22s           %7lu %10lu\n",
 387            "Total", info.total_created, info.total_allocated);
 388   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 389 }