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