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
 251   if (GATHER_STATISTICS)
 252     {
 253       struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 254
 255       desc->allocated += pool->elt_size;
 256       desc->current += pool->elt_size;
 257       if (desc->peak < desc->current)
 258         desc->peak = desc->current;
 259     }
 260
 261   gcc_checking_assert (pool);
 262
 263   /* If there are no more free elements, make some more!.  */
 264   if (!pool->returned_free_list)
 265     {
 266       char *block;
 267       if (!pool->virgin_elts_remaining)
 268         {
 269           alloc_pool_list block_header;
 270
 271           /* Make the block.  */
 272           block = XNEWVEC (char, pool->block_size);
 273           block_header = (alloc_pool_list) block;
 274           block += align_eight (sizeof (struct alloc_pool_list_def));
 275
 276           /* Throw it on the block list.  */
 277           block_header->next = pool->block_list;
 278           pool->block_list = block_header;
 279
 280           /* Make the block available for allocation.  */
 281           pool->virgin_free_list = block;
 282           pool->virgin_elts_remaining = pool->elts_per_block;
 283
 284           /* Also update the number of elements we have free/allocated, and
 285              increment the allocated block count.  */
 286           pool->elts_allocated += pool->elts_per_block;
 287           pool->elts_free += pool->elts_per_block;
 288           pool->blocks_allocated += 1;
 289         }
 290
 291
 292       /* We now know that we can take the first elt off the virgin list and
 293          put it on the returned list. */
 294       block = pool->virgin_free_list;
 295       header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
 296       header->next = NULL;
 297 #ifdef ENABLE_CHECKING
 298       /* Mark the element to be free.  */
 299       ((allocation_object *) block)->id = 0;
 300 #endif
 301       pool->returned_free_list = header;
 302       pool->virgin_free_list += pool->elt_size;
 303       pool->virgin_elts_remaining--;
 304
 305     }
 306
 307   /* Pull the first free element from the free list, and return it.  */
 308   header = pool->returned_free_list;
 309   pool->returned_free_list = header->next;
 310   pool->elts_free--;
 311
 312 #ifdef ENABLE_CHECKING
 313   /* Set the ID for element.  */
 314   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
 315 #endif
 316
 317   return ((void *) header);
 318 }
 319
 320 /* Puts PTR back on POOL's free list.  */
 321 void
 322 pool_free (alloc_pool pool, void *ptr)
 323 {
 324   alloc_pool_list header;
 325
 326 #ifdef ENABLE_CHECKING
 327   gcc_assert (ptr
 328               /* Check if we free more than we allocated, which is Bad (TM).  */
 329               && pool->elts_free < pool->elts_allocated
 330               /* Check whether the PTR was allocated from POOL.  */
 331               && pool->id == ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id);
 332
 333   memset (ptr, 0xaf, pool->elt_size - offsetof (allocation_object, u.data));
 334
 335   /* Mark the element to be free.  */
 336   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
 337 #endif
 338
 339   header = (alloc_pool_list) ptr;
 340   header->next = pool->returned_free_list;
 341   pool->returned_free_list = header;
 342   pool->elts_free++;
 343
 344   if (GATHER_STATISTICS)
 345     {
 346       struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 347       desc->current -= pool->elt_size;
 348     }
 349 }
 350
 351 /* Output per-alloc_pool statistics.  */
 352
 353 /* Used to accumulate statistics about alloc_pool sizes.  */
 354 struct output_info
 355 {
 356   unsigned long total_created;
 357   unsigned long total_allocated;
 358 };
 359
 360 /* Called via htab_traverse.  Output alloc_pool descriptor pointed out by SLOT
 361    and update statistics.  */
 362 static int
 363 print_statistics (void **slot, void *b)
 364 {
 365   struct alloc_pool_descriptor *d = (struct alloc_pool_descriptor *) *slot;
 366   struct output_info *i = (struct output_info *) b;
 367
 368   if (d->allocated)
 369     {
 370       fprintf (stderr, "%-22s %6d %10lu %10lu(%10lu) %10lu(%10lu) %10lu(%10lu)\n", d->name,
 371                d->elt_size, d->created, d->allocated, d->allocated / d->elt_size,
 372                d->peak, d->peak / d->elt_size,
 373                d->current, d->current / d->elt_size);
 374       i->total_allocated += d->allocated;
 375       i->total_created += d->created;
 376     }
 377   return 1;
 378 }
 379
 380 /* Output per-alloc_pool memory usage statistics.  */
 381 void
 382 dump_alloc_pool_statistics (void)
 383 {
 384   struct output_info info;
 385
 386   if (! GATHER_STATISTICS)
 387     return;
 388
 389   if (!alloc_pool_hash)
 390     return;
 391
 392   fprintf (stderr, "\nAlloc-pool Kind         Elt size  Pools  Allocated (elts)            Peak (elts)            Leak (elts)\n");
 393   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 394   info.total_created = 0;
 395   info.total_allocated = 0;
 396   htab_traverse (alloc_pool_hash, print_statistics, &info);
 397   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 398   fprintf (stderr, "%-22s           %7lu %10lu\n",
 399            "Total", info.total_created, info.total_allocated);
 400   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 401 }