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