gcc/alloc-pool.c

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