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